組合せ最適化から機械学習へ 劣モジュラ最適化とグラフマイニング AI/データサイエンスライブラリ“基礎から応用へ"

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

• 販売会社／発売会社: サイエンス社
• 発売年月日: 2022/06/27
• JAN: 9784781915456

商品レビュー

2025/08/29

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