組合せ最適化から機械学習へ の商品レビュー

相馬輔(著者),藤井海斗(著者),宮内敦史(著者)

2025/09/04

機械学習における組合せ最適化の中で、劣モジュラ最大化とグラフマイニングに焦点を当てた本。最初に劣モジュラ関数の定義が出てくるが、あくまで数式上なので、その意味するところを理解したい。連続最適化から組合せ最適化の近似解を導く方法を連続緩和法という。線形計画問題の顕著な性質としての双対定理。値オラクルは意外とそうとは知らず、以前書いた論文で使ってたかも…。最大集合被覆問題はサイズ制約付き単調劣モジュラ最大化問題。この問題は、適応的劣モジュラ性と適応的単調性を満たすため、適応的貪欲法が最適解の(1-1/e)近似を導く。その証明もあり。半正定値計画問題。