最適輸送理論のための最適化手法と機械学習への応用

最佳运输理论的优化方法及其在机器学习中的应用

• 批准号: 22K12175
• 负责人: 笠井 裕之
• 金额: $ 2.75万
• 依托单位: Waseda University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2022
• 资助国家: 日本
• 起止时间: 2022-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22K12175/
• 关键词: 最適輸送理論; 緩和最適輸送問題; 非構造データ; メッセージ・パッシング; グラフ分類; 機械学習; 最適化; 最適輸送

機械学習に代表される高知能データ処理技術を利用したシステムの社会実装が精力的に進められている．そのような中，大規模・高次元データを効率良く処理可能な高知能データ処理技術への期待は高い．ここで，データ間距離の定義や距離を用いた機械学習モデルの構築手法，またそれらの計算方法である最適化手法については従前の手法にとらわれない挑戦的な考え方や手法の確立が必要である．本応募では，近年，機械学習の分野で着目されている最適輸送理論に着目し，その最適化手法と機械学習への応用について研究する．本年度は，まず，質量保存制約の緩和最適輸送問題における高速最適化手法について，一部の制約を緩和した半緩和最適輸送問題について検討した．具体的には，エントロピー正則化が存在する場合についてブロック座標Frank-Wolfeアルゴリズムに基づく最適化手法を提案した．具体的には，半緩和問題の変数ブロックを直接利用し，要求誤差最適性に対する反復計算量を，次元/半緩和正則化係数/要求誤差にのみに依存した形で導出した．さらに，(ii)フェンシェル線形化双対ギャップがラグランジュ双対ギャップと一致することを明らかにした．一方，エントロピー正則化が存在する場合の半緩和最適輸送問題についてアルゴリズム構築および理論的収束証明を与えた．次に，非構造データの一つであるグラフ構造を対象として，最適輸送距離による非構造データのデータ表現について検討し，グラフノードのマッチングと最適輸送の類似性に着目し最適輸送の概念を導入した部分構造間距離の検討を行った．特に，メッセージ・パッシング手法で得られた特徴量について木編集距離を用いてノード間距離を定義し，またその効率的な計算方法を提案した．最後に，グラフ分類精度向上に関する数値実験結果を得た．

使用高智能数据处理技术（例如机器学习）对系统的社会实施正在积极进行。在这种情况下，人们对高智能数据处理技术的期望很高，该技术可以有效地处理大规模的高维数据。在这里，有必要建立具有挑战性的思想和方法，这些思想和方法不受以前的方法来定义数据之间的距离，使用距离构建机器学习模型和优化方法的距离，即计算方法。该应用程序专注于最佳运输理论，该理论近年来一直集中在机器学习领域，并研究了其在机器学习中的优化方法和应用。今年，我们首先研究了缓解质量保护限制的最佳运输问题的高速优化方法以及半积极的最佳运输问题，从而放松了一些限制。具体而言，我们提出了一种基于熵正则化的情况的块坐标的Frank-Wolfe算法的优化方法。具体而言，我们直接利用了半释放问题的变量块，并以仅取决于尺寸/半屏障正规化系数/请求误差的方式得出了迭代计算，以使请求误差的最优性得出最佳性。此外，我们已经透露（ii）Fenshell线性化的双隙与Lagrange Dual Gap一致。另一方面，在存在熵正则化的情况下，我们为半积极的最佳运输问题提供了算法结构和理论收敛证明。接下来，我们根据最佳传输距离检查了非结构化数据的数据表示，重点是图节点匹配和最佳传输之间的相似性，并检查了子结构之间的距离，并引入了最佳传输概念。特别是，我们定义了通过使用树编辑距离通过消息传递技术获得的特征数量的节点之间的距离，并提出了一种有效的计算方法。最后，获得了提高图分类精度的数值实验结果。

项目成果

Auto-weighted Sequential Wasserstein Distance and Application to Sequence Matching

• DOI: 10.23919/eusipco55093.2022.9909780
• 发表时间: 2022-08
• 期刊: 2022 30th European Signal Processing Conference (EUSIPCO)
• 作者: Mitsuhiko Horie;Hiroyuki Kasai

Block-coordinate Frank-Wolfe algorithm and convergence analysis for semi-relaxed OT problem

半松弛OT问题的块坐标Frank-Wolfe算法及收敛性分析

• DOI: 10.1109/icassp43922.2022.9746032
• 发表时间: 2021
• 期刊: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
• 作者: Takumi Fukunaga and Hiroyuki Kasai