組合せ最適化から機械学習へ

機械学習における組合せ最適化, 特に近似アルゴリズムを解説した, 初めての和書.古典的な結果をしっかりと踏まえつつ, 最新の結果までスムーズに到達できるよう, トピックや具体例を配置した.
本書の概要 / 組合せ最適化の基礎 / 劣モジュラ最大化 / グラフマイニング / 本書のまとめと展望 / 基の同時交換公理の証明 / 凸解析の基礎 / 線形回帰の基礎

『組合せ最適化から機械学習へ 劣モジュラ最適化とグラフマイニング』 (相馬 輔、藤井 海斗、宮内 敦史 著、サイエンス社、2022 年 6 月刊) は、機械学習の中に現れる組合せ最適化問題と、それを解くための近似アルゴリズムを、劣モジュラ最大化とグラフマイニングの二つを軸に解説した教科書です。シリーズ「AI/データサイエンスライブラリ 基礎から応用へ」の第 1 巻にあたり、版元は難易度を中級と示し、機械学習における組合せ最適化、特に近似アルゴリズムを解説した初めての和書と紹介しています。

全 5 章と付録 3 本、集合関数の基礎から影響最大化まで

第 1 章で本書の概要と必要な知識、読み進め方のチャートを示したあと、第 2 章で組合せ最適化の基礎として、集合関数と劣モジュラ関数、集合族とマトロイド、厳密アルゴリズムと近似アルゴリズムの違い、線形計画と整数計画を整理します。中心となる第 3 章の劣モジュラ最大化では、機械学習における具体例を挙げたうえで、組合せ型と連続型のアルゴリズム、整数格子点上の劣モジュラ最大化、劣モジュラ比、適応的劣モジュラ最大化へと進みます。第 4 章のグラフマイニングは、密グラフ抽出、相関クラスタリング、影響最大化の三つの問題を扱い、第 5 章でまとめと発展的な話題への参考文献を示します。付録には基の同時交換公理の証明、凸解析の基礎、線形回帰の基礎が収められており、本文で使う道具立てを補えるようになっています。

劣モジュラ性と近似保証、機械学習で組合せ最適化が要る場面

劣モジュラ関数は、集合に要素を一つ加えたときの増え方が、すでに選んだ集合が大きいほど小さくなる性質、いわゆる限界効用の逓減を持つ集合関数です。特徴量の選択、センサーの配置、文書の要約、学習データの部分集合の選択など、たくさんの候補から有用なものを決められた数だけ選ぶ問題の多くがこの性質を持ちます。こうした問題は一般に厳密に解くのが難しい一方、劣モジュラ性があれば、毎回いちばん効く要素を足していく単純な貪欲法でも最適値に対する一定の割合を保証できることが知られています。どの条件の下でどこまでの保証が得られるのかを、計算量 の考え方とあわせて理解できると、ヒューリスティックで済ませていた選択の処理に根拠を与えられるようになります。

グラフマイニングの三つの問題と、読むための前提知識

第 4 章の題材は、いずれもネットワークのデータ分析で繰り返し現れる問題です。密グラフ抽出はつながりの濃い頂点の集まりを見つける問題、相関クラスタリングは頂点どうしの似ている、似ていないという情報からまとまりを作る問題、影響最大化は情報の広がりを最大にする起点の頂点を選ぶ問題で、グラフを対象とするアルゴリズム の中でも最適化の性格が強い領域です。本書は第 1 章で必要な知識を示し、凸解析と線形回帰の基礎を付録で補っていますが、この分野の議論は集合の記法と線形代数、アルゴリズムの基本的な考え方を前提に進むのが普通です。数式を追う体力に不安があれば、機械学習に必要な数学の本 で足場を固めてから手に取ると負担が軽くなります。

向いている読者、理論の裏づけを求める研究者とエンジニア

本書はアルゴリズムの近似保証という数理を扱う教科書で、ライブラリの使い方やコードの書き方を手早く知りたい人の期待には沿いません。深層学習のモデル設計や実装を学びたい場合も、目的が別の本を選ぶほうが早道です。一方で、推薦や広告配信、データの選別、ネットワーク分析などで「たくさんの候補から少数を選ぶ」処理を扱っていて、その手法がなぜ効くのか、どこまでなら保証できるのかを説明したいエンジニアや、劣モジュラ最適化やグラフマイニングの研究に入ろうとする大学院生にとって、日本語で全体を見通せる本書は、論文を読み始める前の確かな入口になります。