| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 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 |
|
| 研究会情報 | |
| 研究会 | IBISML |
| 開催期間 | 2022-12-22 - 2022-12-23 |
| 開催地（和） | 京都大学 |
| 開催地（英） | Kyoto University |
| テーマ（和） | 機械学習一般 |
| テーマ（英） | Machine Learning, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | IBISML |
| 会議コード | 2022-12-IBISML |
| 本文の言語 | 日本語 |
| タイトル（和） | 木構造を用いたワッサースタイン重心問題の高速な解法 |
| サブタイトル（和） | |
| タイトル（英） | Fixed Support Tree-Sliced Wasserstein Barycenter |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 最適輸送 / Wasserstein Distance |
| キーワード(2)（和/英） | ワッサースタイン重心 / Wasserstein Barycenter |
| キーワード(3)（和/英） | / Optimal Transport |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 竹澤 祐貴 / Yuki Takezawa / タケザワ ユウキ |
| 第1著者 所属（和/英） | 京都大学/理研AIP (略称： 京大/理研) Kyoto University/RIKEN AIP (略称： Kyoto Univ./RIKEN AIP) |
| 第2著者 氏名（和/英/ヨミ） | 佐藤 竜馬 / Ryoma Sato / サトウ リョウマ |
| 第2著者 所属（和/英） | 京都大学/理研AIP (略称： 京大/理研) Kyoto University/RIKEN AIP (略称： Kyoto Univ./RIKEN AIP) |
| 第3著者 氏名（和/英/ヨミ） | Zornitsa Kozareva / Zornitsa Kozareva / Zornitsa Kozareva |
| 第3著者 所属（和/英） | Meta AI (略称： Meta AI) Meta AI (略称： Meta AI) |
| 第4著者 氏名（和/英/ヨミ） | Sujith Ravi / Sujith Ravi / Sujith Ravi |
| 第4著者 所属（和/英） | SliceX AI (略称： SliceX AI) SliceX AI (略称： SliceX AI) |
| 第5著者 氏名（和/英/ヨミ） | 山田 誠 / Makoto Yamada / Makoto Yamada |
| 第5著者 所属（和/英） | 京都大学/理研AIP/沖縄先端科学技術大学 (略称： 京大/理研/沖縄科技大) Kyoto University/RIKEN AIP/OIST (略称： Kyoto University/RIKEN AIP/OIST) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2022-12-23 15:10:00 |
| 発表時間 | 20分 |
| 申込先研究会 | IBISML |
| 資料番号 | IBISML2022-63 |
| 巻番号（vol） | vol.122 |
| 号番号（no） | no.325 |
| ページ範囲 | pp.142-149 |
| ページ数 | 8 |
| 発行日 | 2022-12-15 (IBISML) |
[研究会発表申込システムのトップページに戻る]