11.1 数理最適化の基礎知識

ロジスティック回帰をはじめ, 多くの機械学習アルゴリズムの学習は, 最大化/最小化問題を解くことであると説明しました. では, 実際にどうやって計算すればよいのでしょうか. これは手計算では難しいので, 昔から多くの数理最適化のアルゴリズムが考案されてきました. ニュートン=ラフソン (Newton-Raphson) 法あるいは単にニュートン法は古典的な非線形最適化アルゴリズム47で, ロジスティック回帰をはじめ様々なところで使われています. その一番の特徴は収束の速さにありますが, 一方で制約も多く, 適用できる目的関数の種類が, 滑らかなものに限られています (ニュートン=カントロヴィチの定理).

もう1つ, 機械学習によく使われる最適化アルゴリズムとして, 確率的勾配降下法 (SGD) が挙げられます. 両者は使われる場面がかなり異なってきます. 取り組む問題はどれを使うのが適切なのか考えながら取り組んでください.

一口に「数理最適化」といっても, 最小化/最大化問題の対象となる関数の種類によって効率的な方法が様々に発見されています. 例えば様々な最適化問題に対しての解説と Python を主としたオープンソースのライブラリを使用したサンプルコードを掲載した『Python言語による実務で使える100+の最適化問題』 (https://scmopt.github.io/opt100/) という教材が一般公開されています. しかしながら, この資料は主に組み合わせ最適化やロジスティクス (物流のほうの意味) に関する最適化問題を扱っているため, 本インターンのタスクにすぐに応用できるものではないかもしれません.

ここでは, この2つのアルゴリズムのアイディアと特徴を簡単に紹介しますが, 丸め誤差・桁落ち, あるいは行列演算のアルゴリズム, あるいはアルゴリズムの計算効率や精度の評価といった数値計算全般のより基礎的な知識については, 広範になりすぎるため解説していません. これらの話題を取り扱っている教科書は, 私も多くを把握しているわけではありませんが, 例えば数値計算の精度に関しては 大石 et al. (2018), という本があります (洋書ならばもっと多くあると思います).

11.1.1 ニュートン法

ニュートン法は \(g(x) = 0\) のような方程式を解くためのアルゴリズムです. しかし, 目的関数 \(f(\theta)\) が微分できて, かつ凹関数である場合, 方程式 \(f^\prime(\theta) = 0\) の解から最小値を得ることができます. つまり, ここにニュートン法を適用することで最適化をしています. ロジスティック回帰は損失関数の導関数の導出が簡単であるため, ニュートン法を適用することができます.

多くのライブラリでは正確にはニュートン法ではなく, ニュートン法を改良した準ニュートン法 (quasi-Newton —) が実装されていることが多いです. 準ニュートン法はニュートン法と違い二階導関数 (ヘッセ行列) を直接導出する必要がないため, ヘッセ行列の性質に依存しにくいという特徴があります. 準ニュートン法と呼ばれるアルゴリズムにも様々なバリエーションがありますがロジスティック回帰では L-BFGS 法が用いられることが多いです.

少々言い方が悪いですが, ニュートン法は「都合の良い」状況を想定して, その想定下でのみ優れた性能を発揮するアルゴリズムです. 一方で, データには様々なものがあり, 条件の悪いものは思ったよりうまく計算できないことがありえます. 機械学習における典型例を2つ挙げましょう.1つは, 特徴量ごとのスケールが違いすぎると, ニュートン法に限らず多くのアルゴリズムでは最適解への収束がしづらくなることが知られています. よって特徴量の前処理として標準化または正規化が重要になります.

もう1つは, 理論的にも完全にうまく計算できなくなる例である L1 正則化です. 正則化を一切しないロジスティック回帰の場合, 損失関数は理論上ニュートン法で扱える形になるため有効ですが, L1 正則化項を含む場合はニュートン法で計算できなくなります. scikit-learn の実装では, 正則化に応じて適切な最適化アルゴリズム (この場合は SAGA) が自動で選択されますが, ニュートン法と比べて計算に時間がかかるなどアルゴリズムごとの特性を覚えておきましょう.

11.1.2 SAGA

ニュートン法で計算できない機械学習のモデルの典型例はL1正則化です. scikit-learn で L1 正則化の最適化計算に採用されている SAGA は, Defazio, Bach, and Lacoste-Julien (2014) によれば次のような手順です.

\(F(\boldsymbol{\theta}) = (1/n)\sum_{i=1}^n f_i(\boldsymbol{\theta}) + h(\boldsymbol{\theta})\) を最小化するパラメータ \(\boldsymbol{\theta} = \begin{bmatrix}\theta_{1} & \cdots & \theta_{d}\end{bmatrix}\) を見つけたい時, 初期値 \(\boldsymbol{\theta}^{(0)}\) を与え, 以下を \(k=1, 2, 3\) と反復して繰り返します.

  1. ランダムに \(1,\cdots,n\) からランダムに1つ選び, \(j\) します
  2. \(f_j^\prime(\boldsymbol{\theta}^{(k)})\) を計算し値を保存します (以下, これを \(\psi^{(k+1)}_j\) と表します)
  3. \(\boldsymbol{\theta}^{(k)}\) を以下の式に基づいて \(\boldsymbol{\theta}^{(k+1)}\) に更新します

\[\begin{align} w^{(k+1)} &= \theta^{(k)} - \gamma \left[\psi^{(k+1)}_j - \psi^{(k)}_j + \frac{1}{n}\sum_{i=1}^n \psi^{(k)}_i \right]\\ \boldsymbol{\theta}^{(k+1)} &= \arg \min_\theta \left[h(\theta)+\frac{1}{2\gamma}\left\Vert \theta^{(k+1)}-\boldsymbol{w}^{(k+1)} \right\Vert^2\right] \end{align}\]

ここでいう \(f(x)\) は機械学習の損失関数で, \(h(x)\) は正則化項に対応します. つまり, \(h(x)\) が L1正則化項のように微分できない関数でも適用できるということです. しかし微分できない関数を含む最適化はニュートン法と比べ収束がおそく, 微分できる関数より難しい問題になることが多いです.

L1正則化の最適化に関しては, 川野, 松井, and 廣瀬 (2018), 富岡 (2015) などでも言及がなされています.

参考文献一覧

Defazio, Aaron, Francis Bach, and Simon Lacoste-Julien. 2014. “SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives.” Arxiv.
大石進一, 荻田武史, 柏木雅英, 劉雪峰, 尾崎克久, 山中脩也, 高安亮紀, et al. 2018. 精度保証付き数値計算の基礎. 東京: コロナ社.
富岡亮太. 2015. スパース性に基づく機械学習. 機械学習プロフェッショナルシリーズ. 東京: 講談社.
川野秀一, 松井秀俊, and 廣瀬慧, eds. 2018. スパース推定による統計モデリング. 6. 共立出版.

  1. ニュートン法は正確には非線型方程式の解を求めるアルゴリズムですが, 後述のように一定の条件下で最適解を得ることに使うことができます.↩︎