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

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

• 批准号: 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 线性化对偶能隙与拉格朗日对偶能隙一致。另一方面，我们构建了一种算法，并给出了熵正则化存在下的半松弛最优传输问题的理论收敛性证明。接下来，我们关注图结构这种非结构化数据，研究了使用最优传输距离的非结构化数据的数据表示，并通过关注图节点匹配和最优传输之间的相似性引入了最优传输的概念。我们研究了子结构之间的距离。特别是，我们使用消息传递方法获得的特征的树编辑距离来定义节点间距离，并提出了一种有效的计算方法。最后，我们获得了提高图分类精度的数值实验结果。

项目成果

Auto-weighted Sequential Wasserstein Distance and Application to Sequence Matching

自动加权序列 Wasserstein 距离及其在序列匹配中的应用

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

Wasserstein Graph Distance based on L1-Approximated Tree Edit Distance between Weisfeiler-Lehman Subtrees

基于 Weisfeiler-Lehman 子树之间的 L1 近似树编辑距离的 Wasserstein 图距离

• DOI: 10.48550/arxiv.2207.04216
• 发表时间: 2022-07-09
• 期刊: ArXiv
• 作者: Zhongxi Fang;Jianming Huang;Xun Su;Hiroyuki Kasai
• 通讯作者: 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
• 作者: Takumi Fukunaga;Hiroyuki Kasai
• 通讯作者: Hiroyuki Kasai