ハクソク

世界を動かす技術を、日本語で。

X X^tはより高速にできる

374日前原文(arxiv.org)

概要

  • RXTXは、行列とその転置の積$XX^t$を計算する新しいアルゴリズムを提案。
  • 既存の最先端手法より 5%少ない乗算 と 5%少ない総演算回数 を実現。
  • この高速化は 大規模行列 だけでなく、 小規模行列 （例: $n=4$）にも有効。
  • アルゴリズムは 機械学習ベースの探索 と 組合せ最適化 の組み合わせにより発見。
  • 対象分野は データ構造・アルゴリズム、人工知能、機械学習、記号計算。

RXTX: 行列と転置の積を効率化する新アルゴリズム

アルゴリズムの特徴

  • RXTXは、$X\in \mathbb{R}^{n\times m}$に対して$XX^t$の計算を 効率化 することを目的とするアルゴリズム。
  • 乗算回数と総演算回数 （加算・乗算）を、従来の最先端手法より 約5%削減 することを実現。
  • 大規模な$n$ に対する漸近的な高速化だけでなく、 $n=4$のような小規模行列 にも効果を発揮することを確認。

技術的背景と発見方法

  • RXTXは、 機械学習ベースの探索手法 と 組合せ最適化技術 を組み合わせることにより発見。
  • 探索アルゴリズム が、従来見落とされていた計算パターンを発見することに寄与。
  • 計算複雑性理論 や アルゴリズム最適化 の分野へ新たな提案となることを確認。

実用・応用分野

  • RXTXは、 データ構造とアルゴリズム（cs.DS）、 人工知能（cs.AI）、 機械学習（cs.LG）、 記号計算（cs.SC） の分野で有用性を発揮。
  • 大規模データ解析 や ニューラルネットワークの前処理 など、行列計算がボトルネックとなる場面での利用を提案。
  • 計算資源の削減 や 処理時間の短縮 に貢献することを期待。

参考・引用情報

  • 論文タイトル: RXTX
  • 著者: Dmitry Rybin
  • arXiv: arXiv:2505.09814
  • 対象MSCクラス: 68Q25, 68T20
  • 対象ACMクラス: F.2.1, I.1.2
  • 提出日: 2025年5月14日（v1）、2025年5月16日（v2）

今後の展望

  • 他の行列演算 への適用可能性を調査すること。
  • さらなる最適化 や 異なる計算環境 での性能検証を進めること。
  • 機械学習によるアルゴリズム設計 の発展に寄与することを期待。

Hackerたちの意見

じゃあ、AI企業がクラスタに50億ドル使ったら、この最適化は2.5億ドルの価値があるの？

└

そうは思わないな。これは行列とその転置を掛ける最適化であって、一般的な行列乗算のためのものじゃないよ。

└

この特定の問題を解くのにそんなにコストはかからなかったよ（そのコストはクラスターの存在期間にわたって償却される）。赤肉を食べる学者たちのCO2と比べると、これは風力発電と石炭の比較みたいに、ずっと環境に優しいよ。

すぐに思いつくアプリケーションはないけど、正方行列の近似固有ベクトルを見つけるための反復行列乗算くらいかな。でも、実際に固有ベクトルを見つけるために何が使われてるのかは分からない。

└

それは結構一般的な操作だよ。ベクトル値の確率変数のサンプル共分散はXX^t/Nだね。

└

いろんな多変量統計手法ではかなり基本的なものだよ。もしXの行が多変量観測値なら、XX’はグラム行列（内積の行列）になる。これはクラスタリングや回帰に使えるよ。もしXの列が（中心化された）多変量観測値なら、XX’はサンプル共分散行列のスカラー倍になる。これはPCAに使われるけど、大規模なアプリケーションではXX’を保存するのは望ましくないかもしれなくて、代わりにXX’vの形の積をその場で計算することに興味があるかもね。

└

SVDをやるときにも役立つかもね（ただ、実際にはX’XじゃなくてX’Xvが欲しいんだけど…）。

└

特に興味深い結果の一つは、数値線形代数のための優れたアルゴリズムが実際に存在していて、人工知能によって見つけられるってことだと思う。XX^Tは、Xのベクトルのすべての区分的ドット積の行列で、他の人たちが指摘しているように正当な応用があるんだ。例えば、未定義の線形システムを最小二乗問題に変換することとか。

└

共分散。

└

このアルゴリズムか似たようなものがX^tXにも効果があると期待してるよ。面白い事実として、その操作は一般的すぎて、あるトレーディング会社がそれにちなんで名付けられたんだ：XTXマーケッツ。

なんとかメモリキャッシュの動きをモデル化できたらよかったのに。分析が難しくなるけど、大きな行列アルゴリズムはキャッシュフレンドリーなメモリアクセスパターンによって生死が決まることが多いからね。4x4のブロックに分けるのは通常すごく良いけど、実際のランタイムにはあまり関係ないかも。

└

キャッシュ分析がもっと広く知られるようになればいいなと思う。関わる人たちはみんな理解しているし、考え方も知っているみたいだけど、ベストプラクティスは多くのヒューリスティックに wrapped されている感じがする。システムのプロファイリングにハードウェアカウンタを使えることは知っているけど、もっと細かいレベルで何が起こっているのかが隠されているように感じる... それとも、まだ適切な参考資料を見つけていないのかもしれない。

これはカラツバアルゴリズムみたいなもので、理論的には速いけど実際のハードウェアで動かすと速くないってこと？ちなみに、結果が対称になることが分かっているなら（例えばX * X^Tの場合）、もっと速くできるよ。例えばcuBLASでは、cublas*syrk（結果が対称のときに最適化されたバリアント）は、私の経験ではgemmより速くないから、代わりに小さな乗算をして一方の三角形を少しずつ埋めてから、その三角形をもう一方にコピーするって方法があるよ。

└

[フラグ]

└

理論的には速いけど、実際のハードウェアで動かすとそうでもない、いわゆる銀河アルゴリズム: https://en.wikipedia.org/wiki/Galactic_algorithm

└

彼らはBLASのプリミティブと比較して、ハードウェア上では自分たちの方が速いことを発見した。

└

これは2x2だから、これを実行できるSIMD命令がある（または2つのSIMDドット積を使う）し、CPUでも各GPUコアの中でもできるよ。だから、現在のハードウェアでは手動で書く方が速いってことはないよ。

└

要約に5%の改善と小さな行列について言及されてるから、直感的に言うと（まだ実際の論文は読んでないけど）、おそらく実用的なタイプのアルゴリズムだと思う。

└

約256x256以上の行列に対しては速いけど、ハードウェアによるね。

└

カラツバは実用的なサイズでは確実に学校の教科書に載ってる掛け算より速いよ。おそらくストラッセンのことを言ってるんだろうね。

これらのアルゴリズムを加速させつつ、結果の最大精度を保つことに興味がある研究者はいるのかな？この最適化や他の最適化は、少ない乗算で多くの加算を行うことをトレードオフにしているけど、私の知っている限りでは、浮動小数点の加算と減算は精度的にリスクがある一方で、乗算は無害なんだよね。それに、FMA（融合乗算加算）操作を使うのも有益だと思う。

└

アルゴリズムの安定性の問題は面白いけど、論文ではあまり触れられてないみたい。確かに、アルゴリズムが異なる結果を出すことを期待すべきだよね。>この最適化や他の最適化は、少ない乗算で多くの加算を行うことをトレードオフにしているけど、私の知っている限りでは、浮動小数点の加算と減算は精度的にリスクがある一方で、乗算は無害ってのは全然違うよ。一般的に異なるオーダーの大きさは問題だし、乗算や除算ではこれがより深刻な問題になる。なぜなら、これらは大きさの変化を引き起こすからだけど、これも一般化だね。

└

結果の最大精度を保ちながら これらの論文やアルゴリズムはすべてMLの流行に乗ってるものだよ。MLアルゴリズムはそもそも近似的なものだから、絶対的な精度なんて誰も気にしてない。全体のパイプラインの精度だけが重要で（クラスラベルは変わらないべき、少なくともあまり変わらない）、多くの論文や技術がパフォーマンスのために8ビットや4ビットに量子化されることもある（そう、時にはトレーニング中でもね）。この研究分野は「近似計算」みたいな名前に変えた方がいいと思う。そうすれば人々が古典的な数値解析と混同しないから。

└

これを見てみて: https://arxiv.org/abs/1507.00687 。MathOverflowにもこの回答があるよ ( https://mathoverflow.net/a/421380 )。強い数値安定性を求めるなら、立方時間以上の効率は無理だってさ。

└

足し算は大丈夫だけど、引き算は値が近いときが危険なんだよね。

一般的なヒントとして：X^-1は行列を逆にする必要があるって意味じゃないよ。これは「システムを解ける」っていう表記の省略形であることが多い。同じことがX^tにも言える。新しい行列を作る必要はなくて、持ってる行列を違う使い方をするだけだよ。これを科学者たちが間違って解釈して、パフォーマンスが悪いって文句言ってるのを見たことがある。

└

コンピュータプログラマーでも間違えることがあるし、その間違いを面接の質問にまでしてしまうこともあるよね。「配列を逆にする方法は？」っていうよくある質問の正解は、実は逆にしないことなんだ。後ろから読むだけ。言語によって細かいところは違うけど、イテレータを使う言語だと特に簡単にできる。でも、面接官にとってはこれが「正しい」答えじゃないことが多いんだよね。結局、すべてのデータ構造は関数なんだ。学術的な応用は難しく感じるかもしれないけど、実際の応用としては、逆の配列や木構造が欲しいなら、配列を逆にしたかのようにデータを返す読み取り/イテレーションの「関数」があればいいんだ。行列は転置を読むだけで「転置」できるしね。（キャッシュや他の影響でメモリに展開することを選ぶかもしれないけど、最初から賢く保存されていたり、一度だけ読むだけなら、再構築するために読むのと同じくらいのコストになるから、特に理由はないよね。）配列は、インデックスに対して置換をかけることでランダムに順列を生成できるし、メモリに展開する必要もないんだ。

└

グラフィックスではこれをよく見るんだけど、例えばビュー行列を作るにはまずカメラの変換を作ってからそれを逆にするって言う人が多い。でも、実際には逆行列を直接構築する方がいいんだよね。フルの4x4/3x3の変換を逆にする理由はほとんどないのに、いつもこれを見かけるんだ。

ニュースは「小さいサイズ向け」って部分だと思う。

乗算の下では、行が列に変わるんだよね。だから、転置すると行が（元々は）行とドット積を取ることになる：[ a b ] [ a c ] = [ (a b) . (a b) (a b) . (c d) ] = [ |(a b)|^2 (a b) . (c d) ] [ c d ] [ b d ] [ (c d) . (a b) (c d) . (c d) ] [ (c d) . (a b) |(c d)|^2 ] 対角線上には (a b) と (c d) のノルムの二乗があって、これは面白いし、何かに使えるかもしれない。上三角と下三角の間には重複した値があって、(a b) . (c d) は (c d) . (a b) と同じだから、ドット積は可換なんだよね。対して、行列を単に二乗するだけだと：[ a b ] [ a b ] = [ (a b) . (a c) (a b) . (b d) ] [ c d ] [ c d ] [ (c d) . (a c) (c d) . (b d) ] すべてのドット積はユニークなんだ。だから、すぐに X X^t について面白いことがわかるし、明らかなショートカットがあるね。

これに対してAIはどれくらい役立ったの？論文は詳細が少ないけど、エージェントが一種のシードセット（ランク1の二次元積）を生成して、それが次のステップに使われたって書いてある。明らかにこのアイデアは成功したみたいだね。ここにいる誰かが、これが一般的な技術なのか、エージェントの出力がランダムや同じことを試みるシンプルなヒューリスティックと比べてどうなるのかについて知見を持っているか気になる。また、最終的なタスクがエージェントが生成したものから数ステップ下流にあるから、トレーニングの目的がどう定義されるのかも興味があるな。