離散最適化特論

Advanced Discrete Optimization

994G27G

46CSALC502

池辺　淑子

Yoshiko IKEBE

2026年度前期

2026年度

①First semester

水曜3限

3rd period, Wednesday

工学研究科　情報工学専攻

Department of Information and Computer Technology, Graduate School of Engineering

2.00単位

講義 Lecture

-

① [対面]対面授業/ [On-site] On-site class

列モジュラ関数は離散最適化において，古くから知られている性質の良い関数であるが近年，機械学習においても，その有用性が認識されるようになった．本講義では列モジュラ最適化に関する基礎事項を習得したのち，機械学習における応用について学ぶ．

Submodular functions are a class of discrete functions possessing many theoretically nice properties, and are well known in the field of discrete optimization. In recent years, their importance has risen, as their usefulness in the field of machine learning has been recognized. In this class we will first focus on basic properties of submodular optimization, then learn about their applications to machine learning.

情報工学分野に応じた高度な専門知識の修得において，離散最適化の機械学習分野における応用に関する知識を身に着ける．

We aim to master techniques of applying discrete optimization to machine learning, in conformity with the departmental aim of acquisition of advanced expertise.

列モジュラ関するに関する基礎事項を理解したうえで機械学習における代表的な応用について修得し，さらに応用する力を身に着ける．

We aim to (a): grasp fundamentals of submodular functions, (b): understand how submodular optimization can be applied to machine learning, and (c): learn how they can be applied to various real-world problems.

毎回出席して，積極的に授業に参加すること．

Attendance is mandatory, active participation is also expected.

-

-

毎回，授業の終了前にその回の復習事項と次回の予習範囲を示す．

Instructions on topics for preparation and review will be given in class.

出席および毎回の演習課題提出による．

Will be based on attendance and the results of homework exercises.

・S：到達目標を十分に達成し、極めて優秀な成果を収めている
・A：到達目標を十分に達成している
・B：到達目標を達成している
・C：到達目標を最低限達成している
・D：到達目標を達成していない
・-：学修成果の評価を判断する要件を欠格している

・S：Achieved outcomes, excellent result
・A：Achieved outcomes, good result
・B：Achieved outcomes
・C：Minimally achieved outcomes
・D：Did not achieve outcomes
・-：Failed to meet even the minimal requirements for evaluation

Y

「組合せ最適化から機械学習へ」相馬輔・藤井海斗・宮内敦史著，サイエンス社
「劣モジュラ最適化と機械学習」河原吉伸・永野清仁著，講談社

教科書および一部の参考書は、MyKiTS (教科書販売サイト) から検索・購入可能です。
​https://gomykits.kinokuniya.co.jp/tokyorika/​​​

It is possible to search for and purchase textbooks and certain reference materials at MyKiTS (online textbook store).
​​https://gomykits.kinokuniya.co.jp/tokyorika/

第１回：組合せ最適化の基礎（１）
　集合関数と劣モジュラ関数について学ぶ．

第２回：組合せ最適化の基礎（２）
　劣モジュラ関数の性質について学ぶ．

第３回：組合せ最適化の基礎（３）
　劣モジュラ多面体について学ぶ．
　
第４回：組合せ最最適化の基礎（４）
　劣モジュラ関数の最小化アルゴリズムについて学ぶ．

第５回：組合せ最最適化の基礎（５）
　集合族とマトロイドについて学ぶ．

第６回：劣モジュラ最大化（１）
　機械学習における劣モジュラ最大化の例について学ぶ．

第７回：劣モジュラ最大化（２）
　劣モジュラ最大化に対する組合せ型アルゴリズムについて学ぶ．

第８回：劣モジュラ最大化（３）
　劣モジュラ最大化に対する連続型アルゴリズムについて学ぶ．

第９回：劣モジュラ最大化（４）
　整数格子点上の劣モジュラ最大化と劣モジュラ比について学ぶ．

第１０回：劣モジュラ最大化（５）
　適応的劣モジュラ最大化について学ぶ．

第１１回：グラフマイニング（１）
　密グラフ抽出問題とそのアルゴリズムについて学ぶ．

第１２回：グラフマイニング（２）
　密グラフ抽出問題に対する発展的アルゴリズムについて学ぶ．

第１３回：グラフマイニング（３）
　相関クラスタリング問題について学ぶ．

第１４回：グラフマイニング（４）
　影響最大化問題について学ぶ．

第１５回：授業のふりかえり
　授業の総括を行う．

1:  Fundamentals of combinatorial optimization(1)
We will learn about set functions and submodular functions.

2:  Fundamentals of combinatorial optimization(2)
We will learn about basic properties of submodular functions.

3:  Fundamentals of combinatorial optimization(3)
We will learn about submodular polyhedra.

4:  Fundamentals of combinatorial optimization(4)
We will learn about algorithms for submodular optimization.

5:  Fundamentals of combinatorial optimization(5)
We will learn about set families and matroids.

6: Submodular maximization(1)
We will learn about examples of submodular maximization arising in machine learning.

7: Submodular maximization(2)
We will learn about combinatorial algorithms for submodular maximization.

8: Submodular maximization(3)
We will learn about continuous algorithms for submodular maximization.

9: Submodular maximization(4)
We will learn about submodular maximization on integer lattice points.

10: Submodular maximization(5)
We will learn about adaptive submodular maximization.

11: Graph mining(1)
We will learn about algorithms for dense subgraph discovery.

12: Graph mining(2)
We will learn about advanced algorithms for dense subgraph discovery.

13: Graph mining(3)
We will learn about correlation clustering.

14: Graph mining(4)
We will learn about influence maximization.

15: Summing up

-

-

-

なし

None