最適化本自分用メモ1章

Optimization for Machine Learning

Optimization本の自分用メモを少しずつ書いていこうと思います．各章に何が書いていたかを自分なりに纏めることで，後で見なおした時に過去に理解したことを復元するための種みたいなものとする事がこのメモの目的です．他の人が読んだ時に少しでも参考になる部分があれば幸いです．

1. Introduction

  • 最適化は機械学習において重要な位置を占める．
  • 本章では，機械学習で頻繁に用いられるSVMと正則化項付き最適化の２つの問題とその求解法を概観し，機械学習における最適化技術の役割を俯瞰する．

1.1 SVM

SVMの定式化．マージン最大化を達成するように重みベクトルを求めることが目的となる．SVMには，主問題の他に双対問題への変形，ソフトマージンと呼ばれる亜種が存在し，目的に応じて使い分けられる．SVMで解きたい問題となるのは，凸２次計画問題．この問題を如何に解くかに注目が集まっており，様々な最適化手法が提案されてきた．

  • 双対問題に対してのSMO・内点法が代表的な手法として知られている．
  • また，SVMは入力ベクトルを線形分離可能な空間へ写像する操作をカーネルによって実現可能である．
  • 双対問題において，写像後の入力ベクトルを陽に扱うことなく特徴空間における最適化を可能にする性質（カーネルトリック）を持つ．
  • データが大規模な場合，確率的勾配降下法による主問題の求解という方法も．
SVMに関係する章
  • 内点法，特に2次計画問題に対する内点法(3,12章)
  • SGDその他大規模データに対する最適化(13章)
  • その他 (11, 14章)

1.2 正則化項付き最適化

モデルを理想とする構造に近づけるため正則化項を最適化問題に導入する．正則化項を導入した最適化問題を正則化項付き最適化問題と呼ぶ．SVMも正則化項付き最適化問題の特殊ケースである．

正則化項を導入する目的
  • 汎化性能の向上
  • 重みベクトルのスパース化
  • 行列補完の低ランク性制約
  • 既知の補助情報の付加 等があげられる．

また，それぞれの目的に合わせた正則化手法が提案されている．アルゴリズムは，（近接）勾配法ベースの求解法が代表的である．その他，グラフマッチやブロック座標緩和等を使用する方法も存在する．

正則化項付き最適化に関係する主な章
  • 正則化項付き凸最適化問題の双対理論と正則化項のより詳しい解説(2章)
  • min-max系への変形とその求解法，さらに高速解法 (6章)
  • その他(7,9,11,17,18章)

1.3 本の構成

  • 省略