| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2025-01-29 10:45 Sinkhornアルゴリズムのスパース化手法であるSPAR-SINKの改善 ○伊藤尚紀・前田 煌・西山 悠（電通大）  NC2024-53 |
|
| 抄録 | （和） | Sinkhornアルゴリズムはエントロピー正則化付き最適輸送問題を一回の更新毎の計算量$O(n^2)$で解く手法として知られる．しかし実用的応用は制限され計算量削減の研究がされている．textsc{Spar-Sink} (M. Li et al., JMLR 2023) は，ギブスカーネル行列を確率的にスパース化することで，収束に必要な反復回数を維持したまま一回の更新毎の計算量を$O(mathrm{nnz})$（$mathrm{nnz}$はスパース化したギブスカーネル行列の非ゼロ成分の個数で$O(n^2)$より小さい）に削減した．しかしtextsc{Spar-Sink}は輸送コストを考慮せずにサンプリングしており近似性能が不十分である．本研究ではtextsc{Spar-Sink}の改善として，コスト行列の情報をギブスカーネル行列のスパース化に取り入れることを提案する．また，サンプリング確率における累乗の一般化を提案する．textsc{Spar-Sink}との比較実験では，コストを考慮することで安定性と精度が改善したことを確かめた．また，累乗を変えることで安定性と精度が改善する場合があることも確かめた． |
| （英） | The Sinkhorn algorithm enables solving the entropic optimal transport problem with a computational cost of $O(n^2)$ per iteration. However, for practical applications, further reduction in computational cost is essential. As one approach, textsc{Spar-Sink} (M. Li et al., JMLR 2023) introduces stochastic sparsification of the Gibbs kernel matrix, reducing the complexity of each iteration to $O(mathrm{nnz})$, where $mathrm{nnz}$ denotes the number of non-zero entries in the sparsified kernel matrix which is smaller order than $O(n^2)$. Despite its computational efficiency, this method appears to underutilize its potential approximation capacity, as it primarily focuses on the input and target transport measures while neglecting the intrinsic structure of the approximated matrix itself. In this study, we propose an improvement by incorporating the information of the original Gibbs kernel matrix into its stochastic approximation. Specifically, we generalize the sparsification process by introducing an exponent hyperparameter that adjusts the sparsification mechanism. Numerical experiments demonstrate that the proposed method achieves superior stability and enhanced precision compared to textsc{Spar-Sink}. Furthermore, we observed additional improvements in performance when experimenting with different values of the exponent hyperparameter. | |
| キーワード | （和） | 最適輸送 / エントロピー正則化付き最適輸送 / Sinkhornアルゴリズム / textsc{Spar-Sink} / スパース化 / / / |
| （英） | optimal transport / entropic optimal transport / Sinkhorn algorithm / textsc{Spar-Sink} / sparsification / / / | |
| 文献情報 | 信学技報, vol. 124, no. 363, NC2024-53, pp. 66-71, 2025年1月. | |
| 資料番号 | NC2024-53 | |
| 発行日 | 2025-01-21 (NC) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | NC2024-53 |
|
| 研究会情報 | |
| 研究会 | NC NLP |
| 開催期間 | 2025-01-28 - 2025-01-29 |
| 開催地（和） | 大阪大学 |
| 開催地（英） | |
| テーマ（和） | NC, NLP, 一般 |
| テーマ（英） | NC, NLP, General |
| 講演論文情報の詳細 | |
| 申込み研究会 | NC |
| 会議コード | 2025-01-NC-NLP |
| 本文の言語 | 日本語 |
| タイトル（和） | Sinkhornアルゴリズムのスパース化手法であるSPAR-SINKの改善 |
| サブタイトル（和） | |
| タイトル（英） | Improvement of SPAR-SINK, a Sparsification Method for the Sinkhorn Algorithm |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 最適輸送 / optimal transport |
| キーワード(2)（和/英） | エントロピー正則化付き最適輸送 / entropic optimal transport |
| キーワード(3)（和/英） | Sinkhornアルゴリズム / Sinkhorn algorithm |
| キーワード(4)（和/英） | textsc{Spar-Sink} / textsc{Spar-Sink} |
| キーワード(5)（和/英） | スパース化 / sparsification |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 伊藤 尚紀 / Naoki Ito / イトウ ナオキ |
| 第1著者 所属（和/英） | 電気通信大学大学院 (略称： 電通大) The University of Electro-Communications (略称： UEC) |
| 第2著者 氏名（和/英/ヨミ） | 前田 煌 / Kira Maeda / マエダ キラ |
| 第2著者 所属（和/英） | 電気通信大学 (略称： 電通大) The University of Electro-Communications (略称： UEC) |
| 第3著者 氏名（和/英/ヨミ） | 西山 悠 / Yu Nishiyama / ニシヤマ ユウ |
| 第3著者 所属（和/英） | 電気通信大学大学院 (略称： 電通大) The University of Electro-Communications (略称： UEC) |
| 講演者 | 第1著者 |
| 発表日時 | 2025-01-29 10:45:00 |
| 発表時間 | 25分 |
| 申込先研究会 | NC |
| 資料番号 | NC2024-53 |
| 巻番号（vol） | vol.124 |
| 号番号（no） | no.363 |
| ページ範囲 | pp.66-71 |
| ページ数 | 6 |
| 発行日 | 2025-01-21 (NC) |
[研究会発表申込システムのトップページに戻る]