講演抄録/キーワード |
講演名 |
2022-12-23 15:10
木構造を用いたワッサースタイン重心問題の高速な解法 ○竹澤祐貴・佐藤竜馬(京大/理研)・Zornitsa Kozareva(Meta AI)・Sujith Ravi(SliceX AI)・山田 誠(京大/理研/沖縄科技大) IBISML2022-63 |
抄録 |
(和) |
ワッサースタイン重心は、自然言語処理、コンピュータビジョンなどの様々な分野で広く研究されている。しかし、ワッサースタイン距離の計算にはサポート数$N$に対して$O(N^2)$の計算量を必要とするため、ワッサースタイン重心問題を解くには高い計算コストがかかる。これに対し、木上のワッサースタイン距離は、$O(N)$で計算することができ、多数の分布を高速に比較することができる。本研究では、木上のワッサースタイン距離の下での重心FS-TWBとその拡張版であるFS-TSWBを提案する。具体的には、FS-TWBとFS-TSWBが凸最適化問題であり、射影劣勾配降下法を用いて解くことができることを示す。さらに、これらの問題の性質を利用して、より効率的に劣勾配と目的関数値を計算するアルゴリズムを提案する。実験では、提案手法を用いることで、FS-TWBとFS-TSWBは従来のワッサースタイン重心問題よりも約100倍高速に解くことができることを示した。 |
(英) |
The Wasserstein barycenter has been widely studied in various fields, including natural language processing, and computer vision. However, it requires a high computational cost to solve the Wasserstein barycenter problem because the computation of the Wasserstein distance requires a quadratic time with respect to the number of supports. By contrast, the Wasserstein distance on a tree, called the tree-Wasserstein distance, can be computed in linear time and allows for the fast comparison of a large number of distributions. In this study, we propose a barycenter under the tree-Wasserstein distance, called the fixed support tree-Wasserstein barycenter (FS-TWB) and its extension, called the fixed support tree-sliced Wasserstein barycenter (FS-TSWB). More specifically, we first show that the FS-TWB and FS-TSWB problems are convex optimization problems and can be solved by using the projected subgradient descent. Moreover, we propose a more efficient algorithm to compute the subgradient and objective function value by using the properties of tree-Wasserstein barycenter problems. Through real-world experiments, we show that, by using the proposed algorithm, the FS-TWB and FS-TSWB can be solved two orders of magnitude faster than the original Wasserstein barycenter. |
キーワード |
(和) |
最適輸送 / ワッサースタイン重心 / / / / / / |
(英) |
Wasserstein Distance / Wasserstein Barycenter / Optimal Transport / / / / / |
文献情報 |
信学技報, vol. 122, no. 325, IBISML2022-63, pp. 142-149, 2022年12月. |
資料番号 |
IBISML2022-63 |
発行日 |
2022-12-15 (IBISML) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IBISML2022-63 |