新アルゴリズム「Breakthrough」が計算時間を桁違いに短縮、大規模データで威力発揮

ハーバード大学の研究者たちが開発した新アルゴリズム「Breakthrough」は、問題解決に必要な反復回数を劇的に減らし、計算を指数関数的に高速化します。ソーシャルメディア分析や遺伝子データクラスタリングなど大規模データセットで、従来の逐次アルゴリズムを大きく上回る性能を発揮します。

逐次アルゴリズムの限界

ポートフォリオ最適化や従業員配置など、最適解を探す無数の最適化問題は、1970年代初期以来変わらない逐次アルゴリズムに依存してきました。問題サイズに応じて「n」ステップで順次解くため、アルゴリズムが進行するにつれ各反復の相対的利得が減少し、計算ボトルネックになっていました。

Breakthroughの仕組み：適応的サンプリング

逐次アルゴリズムが一歩ずつ実行可能解を絞り込むのに対し、Breakthroughは複数方向を並列サンプリングし、低関連方向を除外、高価値方向を選択して解に到達します。将来の反復で無視される値を選択的に破棄します。

具体的には、O(log n)ステップで1/3に任意に近い近似に到達。並列化を有効にすると、サブモジュラ最大化において既存手法より指数関数的に高速に定数因子近似に到達します。

映画推薦の例では、従来法が「スター・ウォーズ」に類似した属性の映画を1本ずつ追加するのに対し、新アルゴリズムはランダムに映画群をサンプリングし、全く無関係なものを刈り込み、多様な推薦リストを効率的に構築します。鍵は適応的サンプリングプロセスにあります。

実証実験と応用

100万件の評価、4,000本の映画、6,000人のユーザーデータでテストし、従来法の20倍高速にパーソナライズされた多様な推薦を実現。200万件のタクシー配車問題でも、最先端手法の6倍高速でした。ソーシャルメディア分析、遺伝子データクラスタリング、臨床試験設計、医療画像センサーアレイ、薬物相互作用検出などへの応用が期待されます。大量の画像・動画から深層学習訓練用の有効サブセットを高速抽出するなど、大規模データ要約問題へのインパクトも大きいです。

AI駆動の量子技術で磁力計感度を6倍に向上、標準量子限界を突破 DARPA、AI活用で次世代バッテリーと爆発物の開発を加速──「Make-It」プログラム

産業技術