Multi-objective optimization on networks and its applications to machine learning

网络多目标优化及其在机器学习中的应用

基本信息

批准号：
18J23034
负责人：
黒木祐子
金额：
$ 1.41万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2018
资助国家：
日本
起止时间：
2018-04-25 至 2021-03-31
项目状态：
已结题

项目摘要

今年度は機械学習の重要な分野の一つである逐次的意思決定問題に取り組んだ．具体的には「限られた観測に基づく密グラフ抽出に対するバンディットアルゴリズム」に関する研究を行なった：実ネットワーク上の密な部分構造の抽出は, グラフマイニングにおける重要な操作の一つである．本研究では，（重みが未知の）枝集合からの限られた観測に基づく密グラフ抽出を考え，バンディット問題としての定式化と二つのアルゴリズムを提案した．この研究成果は機械学習の難関国際会議であるICML2020に採択されている．また上記の研究をさらに発展させる一般的な枠組みを提案する研究として，報酬関数がリプシッツ連続性を満たす任意の場合に対するアルゴリズムの提案と理論解析を与えた．この結果は人工知能の難関国際会議であるAAAI2021に採択された. さらに，選択した行動を構成する各要素( e.g. ネットワークにおける枝)が観測として得られる場合に対しては，情報論的下界と一致する最適なアルゴリズムを提案した．また，非線形関数の特殊ケースとして，選択した行動を構成する要素のうち最も報酬が小さいもので全体の報酬が定義されるbottleneck rewardという重要な設定に対してはよりタイトな理論保証を持つアルゴリズムを設計した．これらの結果をまとめた論文は機械学習の国際会議に投稿中である．今年度は本課題のまとめとしても，国際的にインパクトのある研究成果を出すことができた．本研究の総括を基に，さらなる実社会への汎用性の高いアルゴリズム設計とその理論解析を目指す予定である．

今年，我们解决了连续决策问题，这是机器学习的重要领域之一。具体而言，我们对“基于有限的观察值提取密集图提取密集图的匪徒算法”进行了一项研究：在真实网络上提取密集的子结构是图挖掘中的重要操作之一。在这项研究中，我们考虑基于分支集（未知权重）的有限观察结果提取密集图，并提出两种算法作为匪徒问题。这项研究发现已在国际机器学习会议ICML2020上采用。此外，我们提供了提出的算法和理论分析，任何情况下奖励功能都满足Lipschitz的连续性，作为一项研究，该研究提出了一个一般框架，以进一步开发上述研究。该结果在人工智能国际会议的AAAI2021上通过。此外，当构成所选动作的每个元素（例如网络）作为观测值时，提出了与信息区域黑社会一致的最佳算法。此外，作为非线性功能的特殊情况，算法对于瓶颈奖励的重要设置具有更严格的理论保证，该奖励定义了整体奖励，这是构成所选动作的最小元素。目前，一份汇总这些结果的论文正在提交国际机器学习会议。今年，我们能够产生对国际水平影响此问题的研究结果。根据这项研究的摘要，我们计划旨在对其算法进行更广泛的算法设计和理论分析。

项目成果

期刊论文数量（0）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Approximation algorithm for star-star hub-and-spoke network design problems,

星星轮辐网络设计问题的近似算法，

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
Yuko Kuroki
通讯作者：
Yuko Kuroki

Non-zero-sum Stackelberg Budget Allocation Game for Computational Advertising

计算广告的非零和Stackelberg预算分配博弈

DOI：
发表时间：
2019
期刊：
影响因子：
0
作者：
Daisuke Hatano;Yuko Kuroki;Yasushi Kawase;Hanna Sumita;Naonori Kakimura;Ken-ichi Kawarabayashi
通讯作者：
Ken-ichi Kawarabayashi

Polynomial-Time Algorithms for Multiple-Arm Identification with Full-Bandit Feedback