機械学習概観 ~その③ 数値計算論編~
さて，機械学習概観，いよいよ最終回． 前回までの2回はそれぞれ学習フレームワーク論，そしてモデリング論に関して議論してきた． しかし問題設定とモデルを好き勝手に決めても，そこに莫大な計算コストがかかったしまっては良いアルゴリズムとは言えない． 故に問題設定とモデリングは数値計算の下支えがあってこそだとも言える． 今回はそのような数値計算部分について紹介していきたいと考えている． ここで，「学習フレームワーク論？モデリング論？」となっている方は以下の2記事を読んでいただきたい．
数値計算論
数値計算でのゴールは「いかに精度をなるべく落とさずに，少ない計算量を達成するか」だと言える． 以下ではそのような枠組みや，先人たちが計算量を落とすためにしてきた工夫などについて見ていく．
行列計算
まず数値計算において最も基本的な部分の一つである行列計算について説明する．
逆行列計算
逆行列の計算は最小二乗回帰などでも使用される行列計算の手法の一つである． しかし逆行列の計算は行列サイズ$n$に対して$\mathrm{O}(n^3)$の計算量がかかり，非常に大変である． この逆行列の計算をいかに回避or工夫するかが非常に大切になってくる．
この計算の工夫に関して2つほど論文を紹介する． まず1つ目は非定常状態下での密度比推定に関する論文*1である． この論文中のモデル選択の部分で，一つ抜き交差確認法(LOOCV)を用いているのだが，愚直にこれを実行しようとすると，データ数$n$に対して，
ので，モデル選択を含めた計算量として$\mathrm{O}(n^4)$かかってしまい，非常に遅い． そこで，こちらの論文では以下のSherman-Woodbury-Morrisonの公式を用いて計算量を削減している:
$$ \begin{aligned} (A + \bm{b} \bm{c}^\top )^{-1} = A^{-1} - \frac{A^{-1} \bm{b} \bm{c}^\top A^{-1}}{1 + \bm{c}^\top A^{-1} \bm{b}}. \end{aligned} $$
これを利用すると，逆行列の計算を1回のみ行うことでLOOCVの計算を行うことが可能になる． つまり，モデル選択を含めた計算量は$\mathrm{O}(n^3)$で済むということになる．
2つ目はカーネル法の計算量を抑えた論文*2だ． 例えば最小二乗回帰などではカーネル行列の逆行列などが必要になるが，この行列のサイズはデータ点の数に比例する． つまり，カーネル法は大規模なデータだと半端ない計算時間がかかってしまう． こちらの論文は，この問題をNyström methodと呼ばれる手法で解消しようとした． ざっくり言ってしまえば，全てのデータ点を使ってカーネル行列を再現するのではなく，ごく少量のデータのみを使ってカーネル行列を精度よく近似しよう，というアイデアである． 詳細は論文を本体を読んでいただきたい．
ヘッセ行列の計算
ヘッセ行列は特にモデル自体のバリアンス解析や，モデルの解釈性などを見る際に良く使用されるものである:
$$ \begin{aligned} H(f)(\bm{x}) = \nabla^2_\bm{x} f(\bm{x}). \end{aligned} $$
このヘッセ行列の計算も非常に大変で，特にディープモデルなど，パラメータ数が尋常じゃなく多いモデルなどを使用すると，とてつもない計算コストが発生してしまう．
しかし現実問題，ヘッセ行列単体が必要なケースはほぼなく，ヘッセ行列とベクトルの積を計算したい場合がほとんどである:
$$ \begin{aligned} H\bm{v} = \nabla_\bm{x} \Bigl[ (\nabla_\bm{x} f(\bm{x}))^\top \bm{v} \Bigr]. \end{aligned} $$
この場合，クリロフ法と呼ばれる手法を用いてヘッセ行列とベクトルの積を効率良く計算することが可能になる．
ICML2017のベストペーパー*3を紹介する． この論文では，影響関数と呼ばれる量を計算するのだが，その計算にはヘッセ行列の逆行列が必要になる(いかにもやばそう...)． 愚直に計算しようとすると，データ数$n$，パラメータ数$d$に対し，ヘッセ行列の逆行列は$\mathrm{O}(nd^2 + d^3)$の計算量が必要になり，さらにこれを全てのデータ点ごとに計算するので，合計$\mathrm{O}(n^2 d^2 + nd^3)$の計算量が必要になる． この論文のすごいところは，この大変な計算をなんと合計$\mathrm{O}(nd)$の計算量まで落とした点にある． 詳細は書かないが，その工夫として共役勾配法などを用いているらしい．
固有値計算
固有値計算も機械学習でよく使用されるもので，例えば主成分分析(PCA)でも使用される． その計算コストは行列サイズ$n$に対して$\mathrm{O}(n^3)$であり，逆行列の計算同様大変重い． なので，これもいかに回避or工夫するかが非常に大切になってくる．
ベイズ推定における計算
ベイズ推定は機械学習で良く使用される手法の一つである(残念ながら筆者は頻度論者なので，ベイズに対する理解は浅い．もし間違いなどがあれば容赦なくご指摘ください...)． 個人的な意見として，「ベイズは正直常に計算と格闘しているな...」と思っている(ベイズの方々ごめんなさい)．
例えばベイズ推定ではしばしば以下の予測分布を計算する必要がある:
$$ \begin{aligned} p(x | \mathcal{D}) = \int p(x | \theta) p(\theta | \mathcal{D}) \mathrm{d} \theta. \end{aligned} $$
ここで，$\mathcal{D} = \lbrace x_1, \ldots, x_n \rbrace$である． この積分，書くのは簡単だが，計算は地獄のように難しい． 正直，ベイズの方々はこの積分の計算をするために並々ならぬ努力をしている． 以下では，その計算方法について紹介する．
モンテカルロ法 (Monte-Carlo Method)
モンテカルロ法では，積分するのを諦め，その代わりにサンプリングを行うことで積分の近似を求める:
$$ \begin{aligned} p(x | \mathcal{D}) = \int p(x | \theta) & p(\theta | \mathcal{D}) \mathrm{d} \theta \simeq \frac{1}{T} \sum_{t=1}^T p(x | \theta_t), \\ & \theta_t \sim p(\theta | \mathcal{D}). \end{aligned} $$
つまり，十分大きな$T$(サンプリング数)をとれば，積分の良い近似が得られるということである． その$\theta_t$をどのようにして得るのかがこの手法のミソだと言える． 実際この手法を用いると，比較的高い精度で積分を計算できる(らしい)． 代表的なサンプリング手法としては:
- マルコフ連鎖モンテカルロ法(MCMC)
- ギブズサンプリング法(Gibbs Sampling) (これはMCMCのうちに入っている？)
- 粒子フィルタ
などがある．
変分近似 (Variational Inference)
上記のモンテカルロ法は確かに複雑な積分の計算を克服できる． しかも比較的高い精度で． しかし，それでもかなりの計算時間がかかるらしい． そこで精度を少し落としても良いので，なんとかして計算時間を落とせないか． それがこの変分近似である．
以下では事後分布$p(\theta | \mathcal{D})$を求めることを念頭に考える． 変分近似では，以下のように別の関数$q$を用いて事後分布を近似する:
$$ \begin{aligned} q(\theta) \simeq p(\theta | \mathcal{D}). \end{aligned} $$
この2つの分布をなるべく同じのものにしたいので，分布間の距離，例えばKLダイバージェンスを取り，その最小値を求める，というのが変分近似の考え方になる:
$$ \begin{aligned} \min_q \mathcal{D}_{\mathrm{KL}} \Bigl( q(\theta) \Big| \Big| p(\theta | \mathcal{D}) \Bigr) = \min_q \int q(\theta) \log \frac{q(\theta)}{p(\theta | \mathcal{D})} \mathrm{d} \theta. \end{aligned} $$
実際，変分近似を使うと，モンテカルロ法よりも早く積分を計算できる(らしい)． しかし，精度はあまり保証されない(らしい)． 直感的には，モンテカルロ法では，「本当の分布からサンプリング」しているので，精度が高く，変分近似は，別の関数を使って近似しているので，その近似がずれた場合は精度が低くなる． この精度と計算時間に関するトレードオフは実に面白い．
最適化計算
さて，数値計算の部分で最も大切なのがこの最適化計算だろう． 最適化計算に関しては「離散か連続か」「凸か非凸か」で分けることができる．
離散vs連続
- 連続最適化: 制約領域が$\mathbb{R}^n$の部分集合の最適化問題(機械学習の最適化問題のうち，体感ベースで90%は連続最適化)
- 離散最適化: 制約領域が$\mathbb{Z}^n$の部分集合の最適化問題(機械学習の最適化問題のうち，体感ベースで10%は離散最適化)
凸vs非凸
- 凸計画: 最小化すべき目的関数が凸関数であり，さらに実行可能領域が凸集合であるような最適化問題
- 非凸計画: 上記以外の最適化問題．すなわち，目的関数が非凸 or 実行可能領域が非凸集合であるような最適化問題
| 凸計画 | 非凸計画 | |
|---|---|---|
| 連続最適化 | 比較的簡単 | 難しい(ディープモデルなど) |
| 離散最適化 | 難しい(劣モジュラ関数最適化など) | 超難しい(NP困難な問題多数) |
最適化問題に関するカテゴリーに関するまとめの表は以上のようになる．
まず連続最適化と離散最適化についてだが，一般的に連続最適化に比べて離散最適化の方が難しい． またほとんどの機械学習の問題は連続最適化問題によって定式化される． しかし，これは離散最適化が全く使われないというわけではない． 実際は能動学習や，グラフ系の話で離散最適化のフレームワークが使われたりする． また，分類問題の序盤に出てくる01-リスクの最小化は実は組み合わせ最適化になっているので，これまた離散最適化だったりする．
次に凸計画と非凸計画について． 凸計画の嬉しいポイントは「局所的最適解$=$大域的最適解」である点で，勾配降下法などを用いて局所的最適解に辿り着けさえすれば，そこが自分たちが望む解になっている． かたや非凸計画の場合は「局所的最適解$\neq$大域的最適解」なので，局所最適解に陥り，本当に欲しい大域的最適解に辿り着けない． そういう意味で，凸計画に定式化してしまえば嬉しいことは多いように思える．
ただし，案外そのような単純な話ではない． 例えば分類手法の一つであるSVMは二次凸錐計画問題と呼ばれる最適化問題によって定式化され，これは凸計画である． しかし計算量は$\mathrm{O}(n^2 d)$であると言われており，ビッグデータを積極的に扱う最近の傾向にはそぐわない． かたや非凸計画であることの多いディープラーニングでよく使われるSGDと呼ばれる最適化手法は，データ数にほぼ依存しない計算量で比較的実用的な局所解を探してくれる． よって，アルゴリズムを設計する段階で「どのような最適化問題に落とし込むか」「何を重視するのか(大域最適解を見つけたいのかor計算時間を早くしたいのかなど)」をしっかり考えなければならない．
まとめ
今回は数値計算論全般に関する論点を概説した． ベイズ推定の話をここ数値計算のところに含めるべきかかなり悩んだが，「こういう区分の仕方もあるよ」というつもりで今回の話に含めた． この数値計算はいわば機械学習の根幹をなしており，機械学習研究者ならば避けて通れない部分と言えるだろう．
さて，以上3回を通して主に機械学習のバックボーンである3要素「学習フレームワーク論」「モデリング論」「数値計算論」について見てきた． 機械学習研究者やデータサイエンティストの方々はこの3要素のうち，自分たちがどこの部分をやっているのか把握すると良いのかもしれない． また初心者の方々はこの3要素をまず見てから勉強すると，今勉強していることやこれから勉強することのイメージが湧くかもしれない．
この3回の記事が機械学習に携わる全員の指南書になることを心の底から切に願う．
niltatsu
*1:Takafumi Kanamori, Shohei Hido, and Masashi Sugiyama. "Efficient direct density ratio estimation for non-stationarity adaptation and outlier detection." Advances in neural information processing systems. 2009.
*2:Christopher KI Williams, and Matthias Seeger. "Using the Nyström method to speed up kernel machines." Advances in neural information processing systems. 2001.
*3:Pan Wei Koh and Percy Liang. "Understanding black-box predictions via influence functions." In Proceedings of the International Conference on Machine Learning. 2017.
