お知らせ 2023年度・2024年度 学生員 会費割引キャンペーン実施中です
お知らせ 技術研究報告と和文論文誌Cの同時投稿施策(掲載料1割引き)について
お知らせ 電子情報通信学会における研究会開催について
お知らせ NEW 参加費の返金について
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2022-12-23 15:10
木構造を用いたワッサースタイン重心問題の高速な解法
竹澤祐貴佐藤竜馬京大/理研)・Zornitsa KozarevaMeta AI)・Sujith RaviSliceX 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著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者 第1著者 
発表日時 2022-12-23 15:10:00 
発表時間 20分 
申込先研究会 IBISML 
資料番号 IBISML2022-63 
巻番号(vol) vol.122 
号番号(no) no.325 
ページ範囲 pp.142-149 
ページ数
発行日 2022-12-15 (IBISML) 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会