新しいアルゴリズムにより計算時間を桁違いに削減

• 新しいアルゴリズムは、問題を解決するために必要な反復回数を大幅に減らすことで、計算を飛躍的に高速化します。
• ソーシャル メディア分析や遺伝データのクラスタリングなどの大規模なデータセットに対して、従来の（逐次）アルゴリズムよりもはるかに優れたパフォーマンスを発揮します。 

利益に対するリスクを最小限に抑えるために株式に資金を割り当てる、ワークフローと従業員の統計担当者を最大化するために従業員を空いているオフィスに割り当てるなど、何千もの最適化問題 (すべての実行可能なソリューションから最適なソリューションを見つける問題) は、逐次アルゴリズムに大きく依存しています。

これらのアルゴリズムの基本的な動作パターンは、1970 年代初頭に初めて確立されて以来、変更 (強化) されていません。特定の問題を「n」個のステップで順番に解決します。

ステップの数は、問題のサイズによって異なります (アルゴリズムに入力として特定の値が提供されます)。この種の方法では、通常、計算上のボトルネックが発生します。各反復からの相対ゲインは、アルゴリズムが進行するにつれてますます小さくなります。

アルゴリズムが問題を解決するために何千もの小さなステップを踏むのではなく、数回のジャンプを実行できるとしたらどうなるでしょうか?今日広く使用されている大規模なアルゴリズムの動作を飛躍的に高速化できたらどうなるでしょうか?私たちが話しているのは、新薬の発見や渋滞の回避に役立つアルゴリズムについてです。

これを可能にするために、ハーバード大学の研究者らは、問題を解くのに必要な反復回数を大幅に減らすことで計算を飛躍的に高速化する、彼らが「ブレークスルー」と呼ぶ新しいタイプのアルゴリズムを考案しました。

情報抽出、オークション設計、マシン ビジョン、計算生物学、ネットワーク分析など、さまざまな分野にわたる幅広い問題の計算を高速化します。

開発者によると、以前は数日から数週間かかっていた大規模な計算を数秒で実行できるそうです。これにより、新しい大規模な並列化アプローチへの扉が開かれ、実用的な要約プロセスを例外的な規模で構築できるようになります。

仕組みは?

逐次アルゴリズムは、実行可能な解決策の数を一度に 1 ステップずつ絞り込むことによって機能します。一方、新しいアルゴリズムでは、さまざまな方向を並行してサンプリングし、関連性の低い方向を削除して、解決策に到達するために最も好ましい (価値の高い) 方向を選択します。今後の反復で無視される値を選択的に破棄します。

画期的なアルゴリズムは適応サンプリングを使用します。研究者提供

より具体的には、アルゴリズムは O (log n) の連続ステップを必要とし、任意に 1/3 に近い近似値に達します。並列化を有効にすると、アルゴリズムは既存のサブモジュラー最大化手法よりも指数関数的に速く定数係数近似に到達します。

参照:ハーバード大学 SEAS | ハーバード大学の出版物

たとえば、タスクがスター ウォーズに似た映画を推奨することである場合、従来のアルゴリズムでは、スター ウォーズと同様の属性 (アクション、アドベンチャー、ファンタジー) を持つ映画を各ステップに 1 つ追加します。

一方、新しく開発されたアルゴリズムは、一連の映画をランダムにサンプリングし、スター・ウォーズにまったく一致しないものを削除します。これにより、スター ウォーズに似た映画の多様なコレクションが得られます (もちろん、スーパーマン映画を 10 個もおすすめに含める必要はありません)。

アルゴリズムは、推奨する十分な項目が得られるまで、各ステップでさまざまな映画を追加し続けます。あらゆる段階で価値ある決定を下すための鍵は、適応サンプリング プロセスにあります。

問題を解決するためにシーケンシャル (黒) アルゴリズムとブレークスルー (赤) アルゴリズムによって実行されるステップの数

テストとアプリケーション

研究者らは、6,000 人のユーザーからの 4,000 本の映画に対する 100 万件の評価を含む大規模なデータセットで適応サンプリング アルゴリズムをテストしました。従来のアルゴリズムより 20 倍の速さで、パーソナライズされたさまざまな映画を個人に推奨することに成功しました。

彼らはまた、このアルゴリズムをタクシー配車の問題にも適用しました。つまり、限られたタクシーで最大数の顧客にサービスを提供するのに最適な場所を選択するということです。 200 万回のタクシー乗車において、アルゴリズムは最先端のものよりも 6 倍高速に動作しました。

ソーシャル メディア分析や遺伝データのクラスタリングなど、大規模なデータセットでははるかに優れた結果が得られます。  これ以外にも、このアルゴリズムは、複数の疾患の臨床試験の開発、医療画像用のセンサー アレイ、薬物間の相互作用の検出にも適用できます。

読む:新しい自動運転車の検索アルゴリズムで積極的に車線変更が可能

現在、深層学習ネットワークをトレーニングするために、何百万もの画像/ビデオから効果的なデータのサブセットを見つけることは、困難な作業になっています。この研究は、貴重なサブセットを迅速に抽出するのに役立ち、大規模なデータ要約問題に大きな影響を与える可能性があります。