2023 年のコンピューター サイエンスにおける 7 つの大きなブレークスルー! 「PとNP」は過去50年間の古典的な問題です。大規模なモデルがリストに大量に登場しています。

毎年恒例の年末総括の時期がやってきました！

2023年、誰もがコンピュータサイエンスの分野で大きな出来事について話すことができます。インターネット全体で人気のある大規模なモデルのChatGPTシリーズ、AIペイントアーティファクトMidjourney、AIビデオ世代Gen-2、Pikaの急速な反復...

研究者たちは、「P と NP」という最も古典的な問題に関して、微妙だが重要な進歩を遂げました。

量子コンピューティングのキラーアプリであるショアのアルゴリズムが、約30年ぶりに大幅なアップグレードを果たした。そして研究者たちはついに、一般的なタイプのネットワークを通る最短経路を理論的にできるだけ早く見つける方法を習得した。

さらに、暗号学者は、機械学習モデルと機械生成コンテンツが AI と予期しない接続を形成する際に、隠れた脆弱性やメッセージにも対処しなければならないことを示しています。

トップ 1: 50 年前の P と NP の問題、「メタ複雑性」理論が道を開く

50 年にわたって、コンピューター科学者たちは、その分野で最大の未解決問題である「P 対 NP」の解決に取り組んできました。

簡単に言えば、「P と NP」は、既知の困難な計算問題とその難しさ、そしてより効率的なアルゴリズムがあるかどうかを調査することです。

しかし、50年間この問題の解決に取り組んできた科学者たちは全員失敗しました。

多くの科学者が画期的な成果を成し遂げようとしていると感じたまさにそのとき、彼らは自分たちの方法がうまくいかないことを証明する、乗り越えられない障害に遭遇する。

時間が経つにつれて、科学者たちは、問題が「困難」であることを証明することがなぜそれほど難しいのか疑問に思い始めました。

こうした内省的な疑問に答えようとする取り組みの中で、メタ複雑性理論という新たな分野が生まれました。これは、この問題に関する現時点での最良の洞察を提供します。

8月に、Quantaは「メタ複雑性」の概念と科学者が始めた探究について記事で紹介した。

3人の数学者は数学的推論の限界について意見が一致しない

「P と NP」問題を解読すると、無数のログ問題が解決され、すべての暗号化が無意味になり、人間が知ることができるものの本質が明らかになることさえあります。

簡単に言えば、P は文字を順番に並べるなど、簡単に解決できる問題です。 NP は、数独のように、解答の確認が容易な問題です。

解決しやすい問題はすべてチェックも簡単なので、P の問題は NP にも当てはまります。

しかし、NP 問題の中には非常に難しいものもあり、多くの可能性を試してみなければ、直感的に数独パズルの解を導き出すことはできません。

研究者たちは、これらの内省的な質問を研究することで、計算上の難しさを証明することの難しさは、一見無関係に思える根本的な問題と密接に関係していることを知りました。

一見ランダムなデータの中に隠れたパターンを見つけるのはどれほど難しいでしょうか?本当に難しい問題がある場合、それはどのくらいの頻度で発生しますか?

「メタ複雑性が物事の核心にあることは明らかだ」とテキサス大学オースティン校の複雑性理論家スコット・アーロンソン氏は言う。

「P と NP」の問題は、研究者を「メタ複雑性」理論の困難な道へと導きました。

しかし、メタ複雑性の研究者にとっては、未知の領域へのこの旅自体が報酬なのです。

トップ2：ビッグモデルが登場、ブラックボックスを開けられるのは誰か

大型モデルの分野では、「Emergence」が今年のホットワードになるかもしれません。

OpenAIチームは2022年の論文で「出現」を次のように定義しました。

この能力が小さいパラメータを持つモデルには存在しないが、大きいパラメータを持つモデルには存在する場合、それは出現です。

たとえば、大きなモデルにいくつかの絵文字を与えて、これが何の映画を表しているかを尋ねます。 LLM は既存の知識に基づいて次のトークンを予測し、最終的に答えを出します。

答え: ファインディング・ニモ

それだけでなく、この小型モデルは、掛け算から実行可能なコンピュータコードの生成、そしてどうやら絵文字に基づいた映画の解読まで、テキストの解析とはほとんど関係のないタスクを多く実行できなかった。

この OpenAI の調査では、一部のタスクと一部のモデルには複雑さの閾値があり、それを超えるとモデルの機能が急速に向上することも示されています。

しかし、LLM の機能が拡大し続けるにつれて、新たな懸念が生じていることを認識する必要があります。

これらの強力な AI システムは、嘘をでっち上げて社会的偏見を生み出すだけでなく、人間の言語の最も基本的な要素の一部さえ処理することができません。

最も重要なのは、これらの AI はまだブラックボックスであり、内部の推論ロジックは不明であるということです。

しかし、AIの「ブラックボックス」を公開する研究も登場している。たとえば、OpenAI チームは GPT-4 を使用して 30 万個の GPT-2 ニューロンを説明し、最新の研究では GPT-2 を使用して GPT-4 を監督することさえ提案しました。

全体として、大きなモデルの内部の仕組みを解明するには、まだ長い道のりが残っています。

トップ3: 最短経路を見つける40年前のアルゴリズム

コンピューター科学者は、2 つの都市を結ぶ有料道路など、接続にコストがかかるグラフ ネットワーク (エッジで接続されたノードのネットワーク) をすばやく横断できるアルゴリズムについて長い間知っていました。

しかし何十年もの間、科学者たちは、経路を取るコストと報酬だけを考慮した場合に最短経路を決定する高速アルゴリズムを見つけることができませんでした。

昨年末、ラトガース大学の3人の研究者が実現可能なアルゴリズムを提案した。

彼らの新しいアルゴリズムは、グラフ内の特定の「ソース」ノードから他のすべてのノードまでの最短パスを見つけます。これは、かなり昔に正の重みアルゴリズムによって達成された速度とほぼ同等です。

論文アドレス: https://arxiv.org/abs/2203.03456

ダイクストラ アルゴリズムは、1956 年にオランダのコンピューター科学者エドガー ダイクストラによって開発されたことは特筆に値します。これは、正の重みのみを持つグラフ上で最短経路を見つけることができる高速アルゴリズムです。

これに対して研究者たちは考え方を逆転させ、負の重みを持つグラフの最短経路アルゴリズムを提案しました。

今年3月、シカゴ大学の中国人コンピューター科学者、シャオルイ・サン氏は、群同型問題の最も難しい例をより高速に解く、より高速なアルゴリズムを提案した。

論文アドレス: https://arxiv.org/abs/2303.15412

グループと呼ばれる 2 つの数学的オブジェクトが同じかどうかを正確に判断できます。

さらに、今年のアルゴリズムに関するその他の主要なニュースには、ランダムな方法と決定論的な方法を組み合わせて素数を計算する新しい方法があり、これは限られた情報によるアルゴリズムのパフォーマンスに関する長年の推測を反証しました。

機械学習プログラムやその他の分野で広く使用されている勾配降下アルゴリズムのパフォーマンスを、直感に反するアイデアがどのように向上させるかを示す分析。

トップ4：AI生成画像は非常に人気があり、その背後にある技術は長年にわたって蓄積されてきました

今年は、DALL·E、Midjourney、Stable Diffusionなどの画像生成ツールが人気です。

テキストプロンプトを入力するだけで、AI が要件に応じてアート作品を作成できます。

しかし、これらの AI アーティストの背後にあるテクノロジーは、実際には何年もの蓄積を経てきました。

拡散モデルは、物理学における流体拡散の原理に基づいています。コーヒーの中のよく混ざったクリームを分離して透明な形に戻すのと同じように、ぼやけたノイズを鮮明な画像に効果的に変換できます。

AIツールは既存の画像の鮮明度を向上させる技術も進歩しているが、警察官がテレビドラマで「鮮明化！」と連呼するシーンにはまだまだ遠い。

最近、研究者たちは機械生成画像を生成する新しい方法を見つけるために、拡散以外の物理的プロセスを調査し始めています。

新しい方法の 1 つは、電気力が距離によってどのように変化するかを記述するポアソン方程式に基づいています。このアプローチは、エラーの処理においてより効率的であり、場合によっては拡散モデルよりもトレーニングが容易であることが示されています。

トップ5: 30年後、量子因数分解の速度が急上昇

数十年にわたり、ショアのアルゴリズムは量子コンピューターの威力の象徴と見なされてきた。

1994 年にピーター・ショアによって開発されたこのアルゴリズムにより、量子コンピュータは量子物理学の特性を利用して、従来のコンピュータよりも高速に大きな数を因数分解できるようになります。これは、現在のほとんどのインターネット セキュリティ システムにとって潜在的な脅威となります。

2023年8月、コンピューター科学者がショアのアルゴリズムのより高速な変種を開発しました。これは、アルゴリズムが発明されて以来初の大きな改良です。

それにもかかわらず、真に実用的な量子コンピュータは未だ実現できていません。

実際のアプリケーションでは、小さなエラーが急速に蓄積され、計算結果が破損し、量子コンピューティングによってもたらされるすべての利点が失われる可能性があります。

実際、昨年末、コンピューター科学者のチームは、特定の問題に対して、古典的なアルゴリズムが、エラーを含む量子アルゴリズムとほぼ同じパフォーマンスを発揮することを示しました。

しかし、希望はある。8月の研究では、低密度パリティ検査符号と呼ばれる特定の誤り訂正符号が、現在の標準よりも少なくとも10倍効率的であることが示された。

トップ 6: 暗号化 + AI の隠された秘密

暗号と人工知能の交差点における珍しい研究。

最近、コンピューター科学者のチームが、機械学習モデルにバックドアを埋め込むことが可能であり、それが事実上検出不可能なだけでなく、その隠蔽が現代の最先端の暗号化技術と同様のロジックによって裏付けられていることを実証しました。

しかし、研究チームは主に単純なモデルを研究したため、この研究結果が今日の AI 技術で使用されているより複雑なモデルにも当てはまるかどうかはまだ明らかではない。

しかし、これらの研究結果は、将来のシステムがこのようなセキュリティの脆弱性をどのように防御できるかについての方向性を示しています。

まさにこうしたセキュリティ上の問題があるため、シンシア・ルーディンは、機械学習アルゴリズムの内部の仕組みをより深く理解するために、解釈可能なモデルを使用することを強く推奨しています。

一方、ヤエル・タウマン・カライ氏のような研究者は、今後の量子技術にとって極めて重要なセキュリティとプライバシーの分野で進歩を遂げています。

関連分野であるステガノグラフィーでは、機械生成メディアに情報を完全に安全な方法で隠す方法が研究によって示されています。

トップ 7: ベクトル注入セマンティクスにより LLM 推論がより効率的になる

AI が強力になったとはいえ、ほとんどの最新システムの基盤となっている人工ニューラル ネットワークには、2 つの大きな問題があります。

1. トレーニングと運営には多くのリソースが必要

2. 理解不能な「ブラックボックス」になりやすい

そのため、多くの研究者は、新たなアプローチを取る時期が来ているのではないかと考えています。

概念は、人工ニューロンを使用して個々の特徴や特性を検出するのではなく、何千もの超次元ベクトルを通じて表現されます。

このシステムは汎用性が高く、エラーを処理する能力が優れており、計算効率もはるかに優れています。

さらに、研究者はモデルによって考慮されたアイデアや関係を直接操作して、その推論に対するより深い洞察を得ることができます。

今年 3 月、チューリッヒの IBM リサーチのチームが、ニューラル ネットワークによる超次元コンピューティングを使用して、抽象視覚推論における古典的な問題である「Rave の漸進的マトリックス」を解決しました。

幾何学的オブジェクトの画像を 3x3 グリッドでレンダリングします。グリッド内の 1 つの位置は空のままになっており、被験者は候補画像のセットから空のスペースに最もよく合う画像を選択する必要があります。

超次元コンピューティングを使用してこの問題を解決するために、チームはまず、各画像内のオブジェクトを表すハイパーベクトルの辞書を作成しました。

辞書内の各ハイパーベクトルは、オブジェクトとその属性の組み合わせを表します。

次に研究チームはニューラル ネットワークをトレーニングして、画像を調べ、辞書内のスーパーベクトルの重ね合わせに可能な限り近い、1 つの要素が +1 または -1 のいずれかである双極性スーパーベクトルを生成しました。

したがって、生成されたスーパーベクトルには、画像内のすべてのオブジェクトとその属性に関する情報が含まれます。

彼らが提案した方法は、一連の問題に対して約 88 パーセントの精度を達成しましたが、ニューラル ネットワークのみを使用したソリューションの精度は 61 パーセント未満でした。

超次元コンピューティングはまだ初期段階ですが、より大規模なテストが進むにつれて、この新しいアプローチがその可能性を示し始めるかもしれません。