最適輸送問題を0.3秒で解く NTTが新手法を開発：生成AI処理の高速化に貢献

NTTは2024年4月5日、実世界のデータに潜む巡回対称性を利用することで、「最適輸送問題」をベースとした大規模データ間の類似度や対応関係を高速かつ高精度に計算する技術を開発したと発表した。

[半田翔希，EE Times Japan]

　NTTは2024年4月5日、最適輸送問題に対して、巡回対称性を利用することで、従来方法と完全に同等な解を高速に計算できるアルゴリズムを提案し、その効果を理論的／実験的に「世界で初めて」（NTT）示したと発表した。今後、生成AI（人工知能）のリアルタイム処理の高速化などへの応用が期待できるという。

　最適輸送問題とは、データ間の輸送コストが最小となる最適経路を求める問題だ。データの類似度や対応関係を高精度に求めるために利用されていて、近年では、画像や音声、生成AIなど広い範囲で用いられている。一方で、解を導き出すために多くの計算時間がかかるという課題がある。また、巡回対称性とは、歯車や雪の結晶など、回転や反転してもその構造が変わらない性質を指す。巡回対称性を持つ対象（今回は画像）は、同じ画像を「n個」組み合わせてできたものと考えられる。なお、nを「巡回対称性の高さ（次元）」と呼ぶ。

最適輸送問題の概要［クリックで拡大］ 出所：NTT

　今回NTTが提案したアルゴリズムは、まず、巡回対称性を持つ最適輸送問題について、極めて少数の変数で構成された別の最適化問題（小さな最適化問題）に帰着させる。この小さな最適化問題を解き、元の最適輸送問題の解を復元する仕組みだ。具体的には、対称性を持つブロックを1つのブロックとして計算し、復元することで、計算時間の短縮を実現した。実験では、4次元の巡回対称性を持つ画像を用いて最適輸送問題を解いた。結果、目標間数値（精度）は従来法と完全に同等の水準を出しながら、計算時間を33.660±3.238秒から0.329±0.034秒に短縮した。

　NTTの担当者は、短縮できる計算時間について「PCの性能などに影響されるものの、理論上はn³分の1まで短縮できる」と説明し、「今回の結果は、巡回対称性を持つと分かっている最適輸送問題に適応できるものだ。巡回対称性の有無を判断する技術は既に開発されていて、それを活用する必要がある」と補足した。

今回発表した巡回対称性を持つ最適輸送問題に対する提案手法［クリックで拡大］ 出所：NTT

　NTTは、人の能力拡張を目指し、実世界の本質的な変化や違いを見極める視覚認知（視覚環世界）を伝承し、人の視覚認知能力を向上させるための技術（視覚環世界誇張表現技術）を研究している。視覚環世界誇張表現技術の実現には、実世界の大規模データ間の変化や違いを高精度かつ高速に検出する基礎技術が必要で、その一環として、最適輸送問題などの研究を行っている。

　今回の研究成果は、人工知能／機械学習の国際会議「Association for the Advancement of Artificial Intelligence （AAAI） 2024」（2024年2月20〜27日）で発表されたものだ。