いまさら聞けない! コンピュータの数学：3. 機械学習のための数学

全文

(1)小特集. いまさら聞けない！コンピュータの数学基応専般. 03. 機械学習のための数学. 杉山将（東京大学）鈴木大慈（東京工業大学）. 統計的パターン認識の枠組みパターン認識の目的は，パターン x. d. p ( y x) =. p (x y) p ( y) p (x). をそれ. p ( x y) p ( y). （1）. {1,...,c} に割り当てることであ. を用いれば，p(y|x) の y に関する最大化を p(x|y)p(y). は d 次元の実ベクトルを表し，c. の最大化に変換できる．ここで，は比例関係を表. はクラス数を表す．たとえば，16 × 16 画素の画像. す．p(x|y)p (y) を訓練標本から推定することによって. に書かれた手書き数字を認識する問題では，次元. パターン認識を行う方式を，生成的アプローチ. 数は d=16 × 16=256 であり，クラス数は数字の 0. と呼ぶ．「生成的」という名称は，データの生成. ～ 9 に対応して c = 10 である．. 確率 p ( x|y ) p ( y ) =p ( x, y ) を推定することに由来し. 統計的パターン認識では，パターン x が従う確. ている．. が属するクラス y る．ここで，. d. 3)，4). 率 p (x)，クラス y が従う確率 p(y)，それらの同時確率 p(x,y)，パターン x がクラス y に属する条件付き確率 p(y|x)，クラス y に属するパターン x の条件付 ☆1. き確率 p(x|y) を考える. ．p(y|x) はパターン x を見. た後でのクラス y の出現確率，p(y) はパターン x を. 生成的アプローチ生成的アプローチでは，p(x|y) と p(y) を訓練標本. D = {( xi , yi )}. n. i 1. から推定する．p(y) は，クラス y に. 見る前のクラス y の出現確率を表すことから，これ. 属する訓練パターン数 ny を用いて単純に p(y)=ny /n. らをそれぞれクラス y の事後確率，事前確率と呼ぶ．. と近似することが多い．一方，p(x|y) の推定にはさま. 事後確率 p(y|x) が最大となるクラス y にパターン x. ざまな方法が用いられる．. ^. を分類すれば，認識誤差が最小になるため，これが理論的に最適なパターン認識法である．. ㍤最尤推定法. しかし実際には事後確率 p (y|x) が未知であるた. 最尤推定法では，パラメータ i y を持つパラメト. め，同時確率 p(x,y) に独立に従う n 個の訓練標本. リックモデル q(x|iy) を考え，クラス y に属する訓. D = {( xi , yi )} を用いてパターン認識器を構成する n. i 1. ことにする．p(y|x) を訓練標本から直接推定する方式を識別的アプローチ. 1)，2). と呼ぶ．「識別的」とい. う名称は，パターン x をクラス y に識別するため. 練パターン X y = {xi }i:y =y が生成される確率の対数 i. である対数尤度. (. log p Xy. y. ) = ∑ log q (x ) i. i : yi = y. に必要な事後確率 p(y|x) そのものを直接推定するこ. を最大にするようにパラメータ i y を決定する．す. とに由来している．一方，ベイズの定理. なわち，p(x|y) の推定量 p (x|y) は. ☆1. ^. ( ),. p ( x y) = q x. 正確には，p (x) は確率密度関数，p (y) は確率質量関数であるが，表記を簡単にするため，本稿ではこれらを単に「確率」と呼ぶことにする．. y. y. (. = argmax log p Xy. 情報処理 Vol.56 No.5 May 2015. y. ). y. で与えられる．「最尤推定法」という名称は，与えられた訓練パターン Xy = {xi }i:y =y のもとで，最も尤 i. 442. y.

(2) 機械学習のための数学. もらしいパラメータ値を求めることに由来している．. を用いて事後確率 p(iy|Xy) を計算する．「ベイズ推. たとえば，パラメトリックモデル q(x|iy) として，. 定法」という名称は，ベイズの定理を用いて事後確. 期待値ベクトル n y と分散共分散行列 ℜ y をパラメ. 率を計算することに由来している．. ータとするガウスモデル. 事後確率 p(iy|Xy) の形状はモデル q(x|iy) と事前確. (. qG x μy ,. y. ) = (2 ). 1 (x 2. exp. 率 p(iy) に依存し，組合せによっては事後確率の計. 1 2. d 2. 算が困難になることがある．もし，モデル q(x|iy) と. y. <. μy ). 1 y. (x. μy ). （2）. を用いることにしよう．ここで，|・| は行列式を表す．対数尤度. (. log qG xi μy ,. i:yi =y. ^. y. ) の微分をゼロ. ^. とおけば，最尤推定量 ny, ℜy は，. μy =. 共役な事前確率 p(iy) を用いれば，事後確率 p(iy|Xy) は事前確率と同じ種類の確率分布になり，計算が容易になる．たとえば，式（2）で示した期待値ベクトル n y と分散共分散行列 ℜ y をパラメータとするガウスモデルに対しては，正規・逆ウィシャート分布. 1 x ny i:yi =y i. (. )(. 1 x y= ny i:yi =y i. μy. μy xi. p (μy ,. ). <. exp. と解析的に求められる．. y. +d+2 2. ). y. <. (μ 2. m). y. 1 tr (S 2. exp 1 y. (μ. 1 y. ). m). y. 全クラス y=1,...,c の分散共分散行列 ℜy が等しい. が共役な事前確率である．ここで，m は d 次元ベ. と仮定すると，その共通の分散共分散行列 ℜ の最. クトル，. ^. 尤推定量 ℜ は. =. 1 n. は正のスカラー，. は正の整数，S は正. 定値対称行列であり，これらは正規・逆ウィシャー. c y=1 i:yi =y. (x. )(. ). <. μy =. μy xi. i. c y=1. ny n. ト分布のパラメータである．事後確率では，これら y. のパラメータは. で与えられる．このとき，クラス y の対数事後確率. 1. log p ( y x) = x<. 1 < μy 2. μy. 1. μy + log. ny n. +C. m + ny μy. m. log p(y|x) は. + ny S + ny. S. y. +. + ny ,. , ny. (μ +n. + ny ,. )(. m μy. y. y. m. ). <. と近似できる．ここで，C は y に依存しない定数. となる．. である．したがって，クラス間の分離境界は x の. パラメータの事後確率 p(iy|Xy) を求めた後は，モ. 一次形式となる．これをフィッシャーの判別分析. デル q(x|iy) の事後確率に関する期待値. と呼ぶ．. p ( x y) =. (. q x. y. )p (. y. ). Xy d. y. （3）. ㍤ベイズ推定法. を p(x|y) の推定結果とする．これをベイズ予測分. 最尤推定法ではモデルのパラメータの値 iy を訓. 布と呼ぶ．最尤推定では，モデル q(x|iy) に最尤. 練標本 Xy から推定した．一方，ベイズ推定法では. 推定量 iy を代入することにより確率分布の推定量. パラメータ iy を確率変数とみなして，パラメータ. q (x|iy) を求めた．したがって，たとえば式（2）で. の値そのものではなくその事後確率 p (iy|Xy) を求. 示したガウスモデルを用いれば，推定量 q (x|iy) も. める．具体的には，パラメータ i y の事前確率 p (iy). ガウス分布である．一方，ベイズ予測分布はモデル. を考え，ベイズの定理. q (x|iy) を平均化するため，たとえガウスモデルを. p. 03. (. y. Xy. ). (. p Xy. y. ) p( ) y. ^. ^. ^. 用いたとしても式（3）は一般にガウス分布にはならない．このように，パラメトリックモデルを用い. 情報処理 Vol.56 No.5 May 2015. 443.

(3) 小特集. いまさら聞けない！コンピュータの数学. るにもかかわらず，モデルで表すことのできない確. て決定する．. 率分布も表現できるのが，ベイズ予測分布の特徴で. 1. クラス y に属する訓練パターン Xy = {xi }i:y =y. ある．しかし，式（3）の積分も一般に計算が困難なため，変分法やサンプリングと呼ばれる技法による近似がよく用いられる．また最大事後確率推定法では，対数事後確率 log p (iy|Xy) を最大にするパラメータ値 ~. iy を用いて，. 2 . X (t ) 以外の訓練パターンを用いて，バンド幅 h y (t ). ( ). のカーネル密度推定量 p h x y を求め， X y(t ) での平均対数尤度を求める． 1 (t ) L(th ) = (t ) log p h x(t ) y X y x( t ) X ( t ). (. ). y. ( ),. p (x y) = q x. y. y. = argmax log p y. (. y. Xy. ). ~. と p(x|y) を推定する．iy は， y. i. を X y(1) ,..., X y(T) に等分割する．. (. = argmax log p Xy. y. ) + log p ( ). 3. これを t=1,...,T に対して実行し，平均対数尤度 1 T (t ) L を求める．の平均 Lh = T t=1 h 4. これをさまざまなバンド幅 h に対して実行し， Lh を最大にするものを選択する．. y. y. とも書けることから，最大事後確率推定法では事前. ㍤最近傍密度推定法. 確率による罰則項 log p (iy) を対数尤度に加えた量. 最近傍密度推定法は，クラス y に属する訓練パタ. を最大化していることが分かる．そのため，最大事. ーン Xy= {xi }i:y =y の中で注目点 x から k 番目に. 後確率推定法は罰則付き最尤推定法と呼ばれること. 近い点 x. (k). i. (k) への距離 ry(k)=<x -x< を用いて，. もある．実際，ベイズ予測分布と異なり，最大事後確率推定法はモデルの中でのみ確率分布を推定する. p (x y) =. ため，ベイズ推定よりは最尤推定に性質が近いと言. d 2. k. d 2. ny. える．. 1. ry (k ). d. によって p(x|y) を推定するノンパラメトリック法で. ㍤カーネル密度推定法. ある．ここで，. 最尤推定法やベイズ推定法では，p (x|y) の推定に. ( )=. パラメトリックモデル q(x|iy) を用いた．一方ノン. u. 1. e. x. du. パラメトリック法では，パラメトリックモデルを用. はガンマ関数であり，階乗. いずに p(x|y) を直接推定する．. なっている．. 代表的なノンパラメトリック法であるカーネル密. k=1 の最近傍密度推定法を式（1）に適用すれば，. 度推定法では，. 事後確率 p(y|x) の近似の y に関する最大化は，ry（1）. p ( x y) =. 1 K( x, xi ) ny i:yi =y. ネルと呼ばれる 2 変数関数であり，ガウスカーネル 2 K( x, x ) = (2 h ). d 2. exp. x x. ! の実数への一般化に. の y に関する最小化に帰着される：. ) はカーによって p(x|y) を推定する．ここで，K(x, x′. 2. 2h 2. がよく用いられる．h >0 はバンド幅と呼ばれ，ガ. 444. 0. d +1 2. argmax p (x y) p ( y) = argmax y. y. = argmax ry (1) y. d. ny. d 2. ny. ry (1). d. n. = argmin ry (1) y. すなわち，全クラスの訓練パターン X = {xi }i=1 n. の中で注目点 x に最も近いパターンが属するクラ. ウスカーネルの滑らかさを調整するパラメータであ. ス y を，x が属するクラスと予測する．これを最近. る．バンド幅は，たとえば以下の交差確認法によっ. 傍識別器と呼ぶ．これを一般化して，注目点 x の. 情報処理 Vol.56 No.5 May 2015.

(4) 機械学習のための数学. 03. 近傍 k 個のパターンが属するクラスの多数決を取る方式を，k 最近傍識別器と呼ぶ．近傍数 k の値は，. f ( x) =. たとえば上述した交差確認法によって決定できる．. n j. （4）. K( x, xj ). j=1. を用いて，ロジスティックモデルを. 識別的アプローチ. qL( y = +1 x) =. 識別的アプローチでは，クラス y の事後確率 p(y|x). exp ( f ( x)). exp ( f ( x)) + exp ( f (x)). qL( y = 1 x) = 1 qL ( y = +1 x). を直接推定する．. と表現することにする．そうすると，ロジスティッ. ㍤ロジスティック回帰. クモデルの最尤推定は. ロジスティック回帰では，事後確率 p(y|x) をカー. n. min. ネルロジスティックモデル. qL ( y x,. exp. )=. c y =1. (. exp. i=1 n. (. ( y) j. j=1 n. j =1. ). ). K( x, xj ). によってモデル化する．そして，最尤推定法やベイズ推定法によって，パラメータ. { }. c,n ( y) j y=1, j=1. ). （5）. と表現できる．f(x i)y i >0 のとき x i は f によって正. K( x, xj ) (y ) j. (. log 1 + exp ( f ( xi ) yi ). を訓練標. しく分類されるため，f(x i)y i が大きければ大きいほど訓練標本 (x i, yi) を余裕を持って正しく分類できることになる．そのため，f(xi)yi は訓練標本 (xi, yi) に対するマージン（余裕）と呼ばれる．式（5）で. 本から学習する．. は，マージン f(xi)yi が大きくなるようにパラメータ. ロジスティック回帰の最尤推定量は，たとえば勾. i が学習される．. 配法によって求められる．すなわち，パラメータ i を適当な初期値に設定し，対数尤度の勾配を上昇す. ㍤最小二乗法. るようにパラメータ値を更新する：. 上記のマージン最大化の考え方に基づけ. ( y) j. +. n i=1. exp. (. c y =1. n j =1. exp. (. (. ( y) j. ば，ロジスティック回帰をさまざまな学習法. I ( y = yi ) K(xi, x j ). ). K (xi, x j ) K (xi, x j ). n j =1. (y ) j. K ( xi , xj. )). に拡張できる．たとえば，ロジスティック損. (. ( y) j. for y = 1,...,c, j = 1,...,n. (. ). 失 log 1 + exp ( f ( xi ) yi ) の代わりに二乗損失. (1. f (xi ) yi ) を用いれば，マージンを 1 に近づけ 2. るようにパラメータ i が学習される： n. min. ここで，I (y=yi) は y=yi のとき 1，y ≠ yi のとき 0 を出力する指示関数であり，f>0 は勾配上昇のステップ幅を表す．この勾配上昇をパラメータ値が収束するまで繰り返すことにより，最尤推定量が求められる．なお，上記の勾配の計算において，n 個の訓練標本すべてを用いずにランダムに選んだ部分集. ( 1 f(x ) y ). 2. i. i=1. i. （6）. ここで，yi=!1 より. (1. f (xi ) yi ). 2. 1 =y yi 2 i. 2. f (xi ) = ( yi. f ( xi )). 2. が成り立つことから，式 (6) は訓練出力標本 { yi }i=1 n. 合（ミニバッチ）で近似することにより，収束速度. とモデルの出力 { f ( xi )}. を改善できることがある．. るようにパラメータ i を学習する最小二乗法と等. ここで，2 クラスの分類問題を考え y=!1 とおき，. 価であることが分かる．最小二乗法は適当な条件の. パラメータ i=(i1,...,in) を持つカーネルモデル. もとで，生成的アプローチで紹介したフィッシャー. <. n. i=1. の二乗誤差和が最小にな. の判別分析と本質的に一致する．. 情報処理 Vol.56 No.5 May 2015. 445.

(5) 小特集. いまさら聞けない！コンピュータの数学. 最小二乗法ではモデルの出力 { f ( xi )}i=1 を訓練 n. が雑音. 4. 0/1損失ロジスティック. を含むときは過適合する傾向がある．そこで，式. 3. 二乗ヒンジ. (6) にℓ2 正則化項 <i<2 を加えたℓ2 正則化最小二. 2. 乗法. 1. 出力標本 { yi }i=1 に適合させるため， { yi } n. n. i=1. n. min i=1. (1. f ( xi ) yi ) + 2. 2. 0. －2. －1. 0 m. 1. 2. 図 -1 損失関数. がよく用いられる．ただし，m$0 は正則化の強さ (t ). を調整する正則化パラメータであり，X y の平均対. りの分類可能性をしらみつぶしに調べるよりも良い. 法によって決定できる．ℓ2 正則化最小二乗法の解. したがって，しらみつぶし探索が可能なほど訓練. (t ) y. 数尤度の代わりに X の誤分類率を用いた交差確認 ^. i は，解析的に. アルゴリズムが今のところ知られていない．標本数 n が小さいとき以外は，0/1 損失を最小にす. = ( K 2 + I ) K ( y1 ,..., yn ). るパラメータ値を求めることが事実上できない．そ. と求められる．ただし，K は (i, j) 要素が K (xi, xj). の代理損失を近似として用いる．しかし，二乗損失. のカーネル行列であり，I は単位行列を表す．「正. を 0/1 損失の近似としてみたとき，m>1 で損失が. 則化」という名称は，K が特異行列の場合でも，. 増加するのが不自然である（図 -1）．. <. 1. こで実用上は，ロジスティック損失や二乗損失など. 2. mI を加えて正則行列にすることに由来している． ℓ2 正則化項 1. j=1. =. n j=1. 2 j. の代わりにℓ1 正則化項 ^. n. =. 2. j. を式（6）に加えると，解 i がスパース，. すなわち，多くの要素がゼロになることが知られて. ㍤サポートベクトルマシン損失最小化の観点から，二乗損失の代わりによく用いられるのがヒンジ損失である．ヒンジ損失：max (0, 12m). いる．. 図 -1 に示したように，「ヒンジ損失」という名称. ㍤0/1 損失. は，ちょうつがい（ヒンジ）を 135 度開いた形状を. 式（5）と式（6）をマージン m の関数と見たも. していることに由来している．. のを損失関数と呼ぶ（図 -1）：. < ヒンジ損失に一般化したℓ2 正則化項 i Ki を加. ロジスティック損失：log (1+exp (2m)). えた規準を最小にするパターン認識法. 二乗損失：(12m). 2. n. パターン認識において，最も自然な損失関数は 0/1. i=1. max (0,1. f ( xi ) yi ) +. <. K. （7）. は，サポートベクトルマシンと呼ばれている．歴史. ：損失であろう（図 -1）. 0/1 損失：I (m#0). 的には，サポートベクトルマシンはソフトマージン. 0/1 損失は，マージンが正のときは 0 を取り，それ. 最大化やカーネルトリックと呼ばれる技法を組み合. 以外のときは 1 を取る．マージンが正のときにその. わせて導出されたが，上述したように最小二乗法の. 標本は正しく分類されることから，0/1 損失は誤分. 自然な拡張としても導出できる．. 類標本数を表す．. 技術的な詳細は省略するが，最適化問題（7）のラ. 0/1 損失は原点で微分不可能で，それ以外の点で. グランジュ双対問題を考えると，双対変数 ai=yiii. は傾きを持たない関数であり，この最小化は NP 困. に関する最適化問題. 難であることが知られている．つまり 0/1 損失の最小化は，n 個の訓練標本の正負のクラスへの 2 通 n. 446. min. 情報処理 Vol.56 No.5 May 2015.

(6) 機械学習のための数学. n. max 0. . 1. i. 1 i=1. 1 n 2 i, j=1. i. 一方，最先端の機械学習手法は最適化理論やアル. y y j K (xi , x j ). ゴリズム論などとも深くかかわっているため，初学. j i. 者が習得するのは必ずしも容易でない．そして，こ. が得られる．ただし，0 と 1 はそれぞれ 0 と 1 だけ. れらのアルゴリズムを用いて実際にデータ解析を行. からなるベクトルを表し，ベクトルに対する不等号. うためには，MapReduce や Hadoop などの分散処. は要素ごとの大小を表す．これは，二次計画と呼ば. 理技術，GPU プログラミング，さらには，データ. れる最適化問題であり，標準的な最適化ソフトウェ. ベースシステムや計算機システムそのものに関する. アで解を求められる．また，この双対問題の解はス. 知識が必要となることもあり，敷居が低いとは言え. パースになることが知られている．. ない．また，機械学習技術の応用分野は基礎科学か. 式（4）で示したカーネルモデルの定義より，n 次. ら産業まで非常に多様なため，これらを俯瞰的な視. 元の双対変数 a の各要素は各訓練標本に対応してい. 点から学ぶことも困難である．このような状況を踏. る．「サポートベクトル」という名称は，ii=aiyi と. まえて，発展著しい機械学習技術の数学的な基礎理. いう関係より，非零の双対変数 ai に対応する訓練入. 論，実用的なアルゴリズム，そして，それらの活用. 力標本ベクトル xi だけが学習結果を支えて（サポー. 法を，入門的な内容から先端的な研究成果まで分か. トして）いることに由来している．. りやすく解説した教科書も登場しつつある．. また，サポートベクトルマシンは各クラスの事後. 本稿が，読者の機械学習への興味を掻き立てると. 確率の差の符号. ともに，ビッグデータ時代を渡り歩いていくための. (. sign p ( y = +1 x). 03. 6）. ). p ( y = 1 x). （8）. 一助となることを願う．. 一方ロジスティック回帰では，パターン x の認. 参考文献 1）杉山将，井手剛，神嶌敏弘，栗田多喜夫，前田英作編：統計的学習の基礎，共立出版 (2014). 2）杉山将：イラストで学ぶ機械学習，講談社 (2013). 3）元田浩，栗田多喜夫，樋口知之，松本裕治，村田昇編：パターン認識と機械学習（上・下），丸善出版 (2007 ～ 2008). 4）杉山将：統計的機械学習，オーム社 (2009). 5）金森敬文，竹之内高志，村田昇：パターン認識 , 共立出版 (2009). 6）杉山将編：機械学習プロフェッショナルシリーズ（全 29 巻），講談社 (2015)，http://urx2.nu/gc1Q. 識に対する信頼度が事後確率 p(y|x) として得られる. (2015 年 1 月 8 日受付）. を推定しているとも解釈できる．式（8）こそがまさにパターン x をクラス y=!1 に分類するために直接的に必要な量であり，それを直接推定していることがサポートベクトルマシンのロジスティック回帰に対する優位性だと考えられる．. ため，認識が難しいパターンを棄却するといった使い方が可能である．杉山将（正会員）■ [email protected]. 機械学習の知識をさらに深めるには. 2001 年に東京工業大学より博士（工学）の学位を取得．現在，東京大学教授．機械学習とデータマイニングのアルゴリズムの開発，および，その応用研究に従事．. 現在主流の機械学習技術は確率と統計を基盤とし. 鈴木大慈 ■ [email protected]. ており，MATLAB や R などを用いれば容易に基. 2009 年に東京大学より博士（情報理工学）の学位を取得．現在，東京工業大学准教授．専門は統計学と機械学習，特に統計的学習理論および最適化手法の研究に従事．. . 礎的なデータ解析が行える. 2)，4)，5). ．. 情報処理 Vol.56 No.5 May 2015. 447.

(7)