Computing with traceable tensor networks

パズルを解こうとしている場面を想像してみてください。新しいピースを一つ追加するたびに、全体の並べ方の数が爆発的に増えていくのです。これは、科学や工学における「高次元」問題という悪夢です。複雑な材料の中を熱がどのように広がるかをモデル化したり、流体中の粒子の動きを予測したり、あるいは量子系の挙動をシミュレーションしたりする場合、数学はあっという間に厄介なものになります。変数が数個であれば、ノートパソコンで解くことができます。しかし、変数が10個、20個、あるいは100個になると、必要なデータの保存量は膨大になり、世界最大のスーパーコンピュータであっても、最初のステップを完了する前にメモリが底をついてしまうでしょう。それは、新しい通りが描くスピードよりも速く街に新しい道が増え続ける都市の中で、あらゆるルートを地図に書き込もうとするようなものです。

これに対処するため、科学者たちは「テンソルネットワーク」と呼ばれる巧妙なトリックを使っています。テンソルとは、多次元の巨大なスプレッドシートのようなものだと考えてください。このスプレッドシート全体を保存することは不可能なので、これらの手法は、データを小さく相互に連結された塊へと分解します。まるで、作業員たちが互いにメモを回し合っているチームのようなものです。これまでに最も普及していたチームは、「テンソル・トレイン（Tensor Train）」と呼ばれる直線状の構成、あるいは「階層的タッカー（Hierarchical Tucker）」と呼ばれる樹形構造でした。これらのチームはデータを小さく保つことには長けていますが、硬直的でもあります。それらは特定の形状でしか機能しません。もし解こうとしている問題が、自然と異なる形状（例えば、円やループ、あるいは複雑なウェブのような形）を持っている場合、それを直線や樹形に無理やり押し込めるのは、丸い杭を四角い穴に打ち込もうとするようなものです。機能はしますが、多くのスペースとエネルギーを無駄にしてしまいます。

ここで、カリフォルニア大学サンタクルーズ校のサラ・エルワインとダニエレ・ヴェントゥリによる新しい研究が登場します。彼らは、これらのデータチームが、効率を失うことなく、ループや複雑なウェブを含む「あらゆる形状」で活動できる方法を考案しました。彼らはこの手法を「グラフ・テンソル・ネットワーク（GTN）」と呼んでいます。論文の中で彼らは、データがより自然な円形のパターンで流れるようにすることで、従来のメソッドよりもはるかに少ないリソースで困難な数学的問題を解決できることを示しました。彼らは、粒子がどのように移動し拡散するかを記述する方程式（フォッカー・プランク方程式）を含む非常にトリッキーな方程式でテストを行い、新しい「グラフ」アプローチが、従来の直線型や樹形型の方法よりも、精度を維持したまま、多くの場合で遥かに高速で、かつメモリ使用量も大幅に少なかったことを明らかにしました。

形を変えるパズルの物語

何百万もの小さなレゴブロックで作られた、巨大で複雑な3D彫刻を描写しようとしている場面を想像してください。もし、すべてのブロックの位置をリストアップしようとすれば、そのリストはインターネット全体の長さよりも長くなってしまうでしょう。これが高次元データが抱える問題です。これを解決するために、科学者は「低ランク」戦略を用います。つまり、すべてのブロックをリストアップする代わりに、それらが組み合わさって一体となる、より小さく単純なブロックの集合体として描写するのです。

長い間、これらのブロックを組み合わせる唯一の方法は、直線状（列車のよう）か、枝分かれした樹形（ツリー）でした。これらの形状は管理しやすいのですが、必ずしも最適とは限りません。データが円形や複雑なウェブを形成したい場合もあります。円形の問題を直線に無理やり押し込めるのは、長い直線の棒を持ちながら円を描いて歩こうとするようなものです。結局、非常に非効率な足取りになってしまいます。

エルワインとヴェントゥリは、シンプルな問いを投げかけました。「もし、接続のマップさえあれば、ブロックを好きな形に組み合わせていいとしたらどうだろうか？」

彼らは、GTN-SVDと呼ばれる新しいアルゴリズムを開発しました。これは、巨大で乱雑なデータの塊を取り込み、あなたが選んだ形状（線、リング、星型、あるいは奇妙でぐにゃぐにゃした塊など）に配置された小さな断片のネットワークへと分解する「ユニバーサル翻訳機」のようなものです。鍵となるのは「ランク隣接行列」であり、これは単にどのパーツがどのパーツと接続されているかを示す地図を描くための高度な方法です。もし二つのパーツが接続されていない場合、マップはその接続を「リンクなし」と伝え、アルゴリズムはその接続を無視してスペースを節約します。

しかし、データを分解することは戦いの半分に過ぎません。時間の経過とともに変化する問題（流体の流れなど）を解くには、新しい情報を追加し続け、その後、データを小さく保つために「掃除（整理）」を行う必要があります。ここが、この論文の真に巧妙な部分です。

従来の「直線型」の手法では、新しい情報を追加するのは簡単でした。古いブロックの隣に新しいブロックを置くだけだからです。しかし、円形やウェブ状のネットワークでは、新しいブロックを追加すると接続が絡まり合い、サイズが再び爆発してしまう可能性があります。著者たちは、もしネットワークに「追跡可能な経路（traceable path）」、つまりループに陥ることなくすべてのブロックを正確に一度だけ訪れるルートがあれば、整理を行う目的においてのみ、ネットワークを列車のように扱えることに気づきました。

彼らは新しい「ローディング（rounding）」手順を考案しました。イメージとしては、乱雑な紐のウェブがある状態です。もし特定の順序（この追跡可能な経路に従って）で紐を引けば、ウェブを壊すことなく、結び目を締め、端の部分を切り取ることができます。彼らの手法はまさにこれを行います。ネットワークを掃引（スイープ）し、接続を締め、不要なデータを切り落とすことで、サイズを小さく保ちつつ、精度を高く維持するのです。

結果：よりスマートに、より速く、よりスマートに

彼らのアイデアが実際に機能するかどうかを確認するため、著者らはいくつかのテストを実施しました。単なる推測ではなく、現実世界のシナリオをシミュレートしました。

まず、非常に複雑でうねりのある数学関数を近似するテストを行いました。彼らは、新しい「バーベル（Barbell）」形状（二つのループが橋でつながったグラフ）を、従来の直線型および樹形型の手法と比較しました。結果は驚くべきものでした。同じレベルの精度を得るために、新しいグラフ手法は、ある精度レベルにおいて直線型の手法よりも382倍少ない「自由度（データの断片数）」しか必要とせず、さらに高い精度レベルでは498倍少ないものでした。平たく言えば、新しい手法は、同じ量の情報を保持する上で、従来よりも数百倍効率的だったのです。

次に、彼らは有名な物理学の問題であるフォッカー・プランク方程式に取り組みました。この方程式は、粒子がどのように移動し、時間の経過とともにどのように拡散していくか（水にインクを落とした時の動きのようなもの）を記述しています。彼らはこれを4次元空間（可視化するのは難しいですが、超複雑なバージョンの部屋だと考えてください）でシミュレートしました。

彼らは、ステップごとにシミュレーションを長時間実行しました。

• 「風がない」シナリオ（粒子がランダムに拡散する場合）では、新しいグラフ手法は開始時に直線型の手法よりも166倍少ないメモリを使用しました。シミュレーションが進むにつれて、グラフ手法は効率的な状態を維持しましたが、旧来の手法は苦戦しました。グラフ手法は全シミュレーションを1,460秒で完了しましたが、直線型の手法は2,737秒かかりました。これは、ほぼ2倍の速度差です。
• 「風がある」シナリオ（粒子が複雑な流れによって押し流される場合）でも、グラフ手法は直線型の手法よりも10倍以上少ないメモリを使用しました。時間の差はさらに大きく、グラフ手法は1ステップあたり約1.16秒であったのに対し、直線型の手法は13.6秒を要しました。

著者らは、彼らの手法がすべてを完璧に解決する魔法の杖ではないことも慎重に注記しています。「風がある」テストでは、最終的な精度において直線型の手法の方がわずかに高かったものの、直線型ははるかに遅く、より多くのメモリを消費していました。著者らは、一部の問題においては旧来の手法が依然として優れている可能性があるとしつつも、多くの問題において、新しいグラフ・アプローチが大きな勝利をもたらすと示唆しています。

なぜこれが重要なのか

大きな教訓は、私たちはもうデータを直線に押し付ける必要はないということです。データが問題に適合する形状（ループやウェブなど）で流れるようにすることで、以前は処理が極めて高コスト、あるいは低速であった高次元のパズルを解くことができるようになります。

著者らは、これらの柔軟なグラフ形状を使用することで、従来のメソッドと同等の答えを得つつ、コンピュータの計算資源をわずかな分量に抑えられることを示しました。それは、地点Aから地点Bへ移動するために、長く曲がりくねった道を作る必要はないと気づくようなものです。時には、直通の橋や円形の経路の方が、はるかに速く、アスファルトの使用量も少なく済みます。これは、物理学、化学、工学におけるより複雑なシステムのシミュレーションへの扉を開き、都市規模のスーパーコンピュータを必要とすることなく、薬が体内でどのように動くかから、星がどのように誕生するかに至るまで、あらゆる事象の理解を助ける可能性を秘めています。