スパース性に基づく機械学習のわからないとこのメモ

機械学習 助けて

タイトル通りL1ノルムとか正則化あたりを理解しようと思ったので「スパース性に基づく機械学習」という本を読んでる
わからないというより日本語が理解できないところがいくつかあったのでメモとして残して、理解できた部分はここでまとめることにする。
わからないとこは箇条書きする

未解決のとこでわかる人いれば助けてほしい・・・・・・・

第1章

スパース性というのは「まばら」を意味する単語
この本だとn次元のベクトル{ \displaystyle \vec{x} }が非ゼロの成分がごく一部しかなくて、それ以外の成分が０なものとかを指す
{ \displaystyle \vec{x} = (1,1,1,0,0,...,0)^{T} }
こんな感じ

スパース性の考えが機械学習にどう役立つか？というのを「ひよこのオスとメスの分類」で考える
ひよこのオスとメスを仕分けするバイトがあるとして、どう仕分けするか。クチバシとか足とか全身をくまなく調べて仕分けする方法を取った時、全身を見るのでかなり時間がかからないだろうか。
実際に仕事としてやっている人たちはどうやら肛門や羽といった一部分のみを調べて仕分けしているそう。
これは全身、「すべての特徴」を見るのではなく「ある一部分の特徴」にのみに注目するだけで仕分けができるということを意味している。スパース性の考えとしては一部分(非ゼロ)ということになる。

また「すべての特徴」がひよこのオスとメスの分類に関係あるとしたら沢山のひよこの「すべての特徴」をくまなく調べないといけないが、「ある一部分の特徴」のみが関係あるとしたら、少数のひよこからその関係を調べるだけで済む。

こんな感じでスパース性は「計算量」の節約の他に「統計に必要なサンプル数」といった統計的な問題を良い方向に持っていってくれることができる。

ここで「ある一部分の特徴」のみが関係しているはずと仮定を立てたとして、「ある一部分の特徴」がどこなのかはわかっていない状況なのでその特徴は自分たちで探さないといけないというのも重要

  • ページ2の「スパース性の拡張のもう一つの例として行列の低ランク性が~」の部分 --- 解決

    d行T列の行列を推定する問題で行列のランクが{ \displaystyle r}であるということは、T個の学習課題に共通する{ \displaystyle r}個の要因が存在することを意味する

省略したけど大体ここら辺が理解できなかった

まず特異値というのは、これは行列Aを相似変換して対角行列の形にしたとき、その対角成分が非ゼロな値のものを特異値と呼ぶっぽい
そして相似変換された元の行列Aのランクはこの特異値の数と一致する性質があるとのこと。

$$ A = \begin{pmatrix} a_1 & a_2 & a_3 \\ a_4 & a_5 & a_6 \\ a_7 & a_8 & a_9 \end{pmatrix} $$

行列Aが(3,3)行列だったとして、第３列目が第１列目の3倍、つまり{ \displaystyle a_7 = 3a_1, a_8 = 3a_2, a_9 = 3a_3 }といった関係だったとしたら、3次元のうち一つの次元は残りの次元で表現できるということを意味する。
基底でいえば線型独立ではないって言えるということかな
スパース性でいえば、3次元の「すべての特徴」を見る必要はなくなったといえる

ここミスってる気がするから修正する

第2章

  • ページ4の「例示することが容易でも、ルールとして言い表すことが難しい事柄が多数存在する」 --- 疑問

MNISTみたいな手書き数字の分類で言えば、例示で「手書き数字の０と９の区別」を説明するのは簡単だけど、ルールで説明するには「基準としての手書き数字０と９」を定義しなければ説明できないが、基準を定義するにはほぼ無限にあるサンプルが必要であり困難ということであってる?

  • ページ5,6の相対エントロピーやロジスティック損失の導出 --- 未解決

イルカの方の深層学習で導出したような気がするのでそっちを復習してまとめるはず

この本では予測や分類を「入力ベクトル{ \displaystyle \boldsymbol{x} }が与えられたもとで、どの程度よくラベル{ \displaystyle y }を予測(分類)できるか」という観点で評価する。データから学習して、分類などを行いたいデータの背後にある未知の確率分布{ \displaystyle P(\boldsymbol{x},y) }に関する期待値を求める

でもこの期待値は未知の確率分布{ \displaystyle P(\boldsymbol{x},y) }に関する期待値だから直接評価はできないため、訓練データから{ \displaystyle P(\boldsymbol{x},y) }をある程度近似するということ。

統計学の授業で「日本人の20歳の平均身長」を求めたいとき全ての20歳の日本人のデータを集めるのはほぼ無理というか難しいから、例えばいくつかの大学に協力してもらったりして有限の人数、いくつかの20歳の日本人のデータを集めて「日本人の20歳の平均身長」を近似するという話に似ている気がする

そのため訓練データから期待誤差を近似したもの、最小化をすることを経験誤差と経験誤差最小化と呼ぶ
深層学習でよく定義する訓練誤差とかはこっちを指してるんだな

深層学習の本で入力と重み{ \displaystyle \boldsymbol{w} }とバイアス{ \displaystyle b}を用いた { \displaystyle f(\boldsymbol{x}) = \boldsymbol{x}^{T} \boldsymbol{w} + b }といった曲線の式をよく見る。この曲線に従ってラベル{ \displaystyle y}を予測したりヌンヌン...
誤差を最小にするというのは訓練データでいえば{ \displaystyle f(\boldsymbol{x}) = \boldsymbol{x}^{T} \boldsymbol{w} + b }という曲線による予測が訓練データがもつ答え{ \displaystyle y}と大体一致して欲しいということ

f:id:Owatank:20171228125452j:plain

曲線の形をグニャグニャ変えていけばいつかは大体一致する曲線になっていくはず。{ \displaystyle \boldsymbol{w} }と{ \displaystyle b}の値を変えていくと形は変わるので、最小化するとは最適な{ \displaystyle \hat{ \boldsymbol{w}} }と{ \displaystyle \hat{b} }を見つけること。

f:id:Owatank:20171228132907p:plain

最小化を達成するための{ \displaystyle (\hat{ \boldsymbol{w}},\hat{b}) }を推定量と呼び、ハットをつけて区別するらしい

ある行列
{ \displaystyle \boldsymbol{X} = ( \boldsymbol{x_1}, ... , \boldsymbol{x_n} ) }
のランクが{ \displaystyle d+1}以上であれば、一意に解{ \displaystyle (\hat{ \boldsymbol{w}},\hat{b}) }が定まる

ここが「？」となった。伝えたいことはランクが{ \displaystyle d+1}以上ということは解決したいことがらは{ \displaystyle d+1}次元で表現できるということ。3次元なら2次元で表現することは難しいから論外(というか自己符号化器の話になる？)として、{ \displaystyle d+1}以上なら次元が多くても、求めたい{ \displaystyle (\hat{ \boldsymbol{w}},\hat{b}) }は定まるということかな。

訓練誤差が小さい値になったからといって近似したい期待誤差が小さいとは限らないことがある。こういう状況は取ってきた一部、訓練データにかなり適合してしまっているとかが考えられる。適合しすぎて期待誤差が大きくなってしまう現象を過剰適合、オーバーフィッティングと呼ぶ。過適合ってやつだ
訓練誤差が小さくなって、期待誤差もそこそこ小さくなることを汎化するという。よく汎化性能って単語見ますね

過適合を防ぎ、汎化性能を上げるにはモデルを制約し、誤差への当てはまりを抑えることが大事になってくる。モデルを制約する方法としては

  1. 多項式などの独立な基底関数の和として関数{ \displaystyle f }を表現し、その基底関数の数を小さく抑える
  2. 関数{ \displaystyle f }の何らかのノルムを抑える

む、難しい単語で書かれてる・・・・。今までの知識を振り絞って考えると１つ目は要するに「次元数を抑えろ」ということだと思う。基底関数でエッッと混乱したけど、曲線を表す多項式は行列で表すとき、極端な話単位ベクトルで構成される基底で分解して表現できるはず。基底関数の数を小さく抑えるというのはこの基底の要素である基底ベクトルの本数を減らすということ。基底ベクトルの本数が減るんだから次元数も当然減る。

近似したい曲線が３次式のする。この曲線を3次式以上で表現しようと考えると、できないことはないが近似したい曲線と形は離れていくかもしれない。それは汎化性能が落ちてしまうことになる。

２つ目は次元数を固定したときの係数(推定量){ \displaystyle \boldsymbol{w} }のとり方の制限かな。実数範囲から係数の値を選べるとしてある次数の係数はめっちゃ大きくとって別の係数は小さくとって・・・とバラ付きすぎるのは問題。実数のある値より大きい値は取らないみたいな制約を決めて{ \displaystyle \hat{ \boldsymbol{w}} }を選ぶ方法をとるということ。

  • ページ12~14の平均期待二乗誤差 --- 未解決

ここ完全に頭追いつかなかった。
まず推定量{ \displaystyle \boldsymbol{w} }の期待二乗誤差の訓練データに関する期待値を
{ \displaystyle \bar{L}(\boldsymbol{w}) = E_T E_{\boldsymbol{x},y} (y-\hat{\boldsymbol{w}}^{T}\boldsymbol{\phi}(x))^{2})}と定義する

また次数pのとき { \displaystyle \boldsymbol{\phi} = (1,x^{1}, ... , x^{p})^{T} , \boldsymbol{w} = (w_0,w_1, ... ,w_p)^{T} }

このとき平均期待二乗誤差は
f:id:Owatank:20180101161043p:plain

(二乗が抜けていたので赤で修正)この導出が全然わからん・・・。第一行目でおそらく二乗の中身を \[ (( \hat{\boldsymbol{w}}^{T} + \bar{\boldsymbol{w}}^{T} - \bar{\boldsymbol{w}}^{T} + {\boldsymbol{w}^{\ast}}^{T} - {\boldsymbol{w}^{\ast}}^{T} )\boldsymbol{\phi}(x) - y )^{2} \]
こんな感じにして変換しているとは思うけど第二行目の変換で悩んでしまった。

※追記( 12/29 )

{ \displaystyle E_{T_r} }は推定量{ \displaystyle \hat{\boldsymbol{w}} }を見つけるために使った訓練データ(標本)からの期待値

{ \displaystyle \bar{\boldsymbol{w}} }は推定量{ \displaystyle \hat{\boldsymbol{w}} }の訓練データに関する期待値らしく{ \displaystyle \bar{\boldsymbol{w}} = E_{T_r}\hat{\boldsymbol{w}} }と定義している


最適性条件というのは
\[ E [ \boldsymbol{\phi}(x)(\boldsymbol{w}^{\ast} \boldsymbol{\phi}(x) - y) ] = 0 \]

{ \displaystyle \boldsymbol{w}^{\ast} }は全てに当てはまる理想のパラメータだから、{ \displaystyle (\boldsymbol{w}^{\ast} \boldsymbol{\phi}(x) - y) }のところが０にならないといけないということなはず

平均二乗誤差に存在する{ \displaystyle {\sum}_x }は計量行列と呼び以下のように定義される

\[ {\sum}_x = E [ \boldsymbol{\phi}(x) \boldsymbol{\phi}^{T}(x)] \]

この計量に基づく距離を

\[ || \boldsymbol{w} - \boldsymbol{w}^{\prime}||_{\sum{x}} = \sqrt{ (\boldsymbol{w} - \boldsymbol{w}^{\prime})^{T} {\sum{x}} (\boldsymbol{w} - \boldsymbol{w}^{\prime})} \]

と定義しているそうだ

ちなみに最後の行の第一項は期待値{ \displaystyle \bar{\boldsymbol{w}} }のまわりでの推定量{ \displaystyle \hat{\boldsymbol{w}} }の揺らぎを定量化する項、ばらけ具合ということで分散になって、第二項は期待二乗誤差{ \displaystyle L(\boldsymbol{w}) }を最小化するパラメータ{ \displaystyle \boldsymbol{w}^{\ast} }と推定量の期待値{ \displaystyle \bar{\boldsymbol{w}} }の距離の２乗でありバイアス(近似誤差)を定量化する項になる
近似して求めたいのは期待二乗誤差を最小化する理想のパラメータ{ \displaystyle \boldsymbol{w}^{\ast} }であり{ \displaystyle \bar{\boldsymbol{w}}=\boldsymbol{w}^{\ast} }になれば推定量{ \displaystyle \hat{\boldsymbol{w}} }は不偏推定量(訓練データ(標本)から求めた期待値が母集団の期待値と一致)になるのはわかる。

最適性条件などを使って平均期待二乗誤差を導出しているらしい。まとめておく

  • ページ18の制約付き最小化問題と罰則項付き最小化問題の等価性 --- 未解決


    ヤバイ

    文がわからなかっただけなので後回しかも

※追記(1/1)
ラグランジュの未定乗数法のことという神の声を頂いた

第3章

{ \displaystyle \boldsymbol{y}= \boldsymbol{x}^{T} \boldsymbol{w}}を満たすようなパラメータ(ベクトル){ \displaystyle \boldsymbol{w} }を決めるとき、ベクトルの非ゼロ要素は少ない方がいい。

例として電車を考える。目的地まで電車で移動したいとき、同じ料金、同じ時間で到着するなら乗り換え({ \displaystyle \boldsymbol{w} }の非ゼロ要素として見る)は少ない方が嬉しくないだろうか。自分は乗り換えが苦手なので少ない方が助かる。

なので推定量{ \displaystyle \hat{\boldsymbol{w}} }を見つけるときの条件として新たに非ゼロ要素は k個 以下という制約を加えてあげればより良い{ \displaystyle \hat{\boldsymbol{w}} }を見つけることができると書いてあった。すごい。

しかし残念ながらこのような制約を加えた最適化問題の計算は現実的に困難であるそうだ。ええ・・・。
理由としては{ \displaystyle \boldsymbol{y}= \boldsymbol{x}^{T} \boldsymbol{w}}を満たすような{ \displaystyle \boldsymbol{w} }の組をしらみ潰しというかブルートフォース？とも言えるのだろうか、調べなくてはいけないから。次元数が増えれば増えるほど調べないといけない組の数は多くなってしまう。

困ってしまった。そこでL1ノルム正則化と呼ばれる手法が役に立つ。
ベクトル{ \displaystyle \boldsymbol{w} }のL1ノルムはベクトルの要素ごとの絶対値の線形和として

{ \displaystyle {\| \boldsymbol{w} \|} (l_1) = \sum_{j=0}^d | w_i |}

で表される。
ベクトル{ \displaystyle \boldsymbol{w} }の非ゼロ要素の数が多いほど、L1ノルムの値も大きくなる。非ゼロの数が１、２、と増えていくのとは別でL1ノルムの値は要素の値によって比例して大きくなることに注意。

このL1ノルムと呼ばれるものを使って非ゼロ要素が少なくて、求めたい要件を満たすような{ \displaystyle \boldsymbol{w} }を見つける。最適化問題としては

{ \displaystyle minimize(\boldsymbol{w}) \,\, \,\, \hat{L}(\boldsymbol{w}) \,\, ( \,\, {\| \boldsymbol{w} \|} (l_1) \leq C \,\,) }

あるいは

{ \displaystyle minimize(\boldsymbol{w}) \,\, \,\, \hat{L}(\boldsymbol{w}) \,\, + \lambda \| \boldsymbol{w} \| (l_1) }

と表される。また条件として{ \displaystyle C > 0 , \lambda > 0}

L1ノルムは{ \displaystyle y = x^{2} }みたいな形をしているから任意の d次元ベクトル{ \displaystyle \boldsymbol{w} }のL1ノルムは凸関数になる

f:id:Owatank:20180102143841p:plain

なので最適化問題

{ \displaystyle minimize(\boldsymbol{w}) \,\, \,\, \hat{L}(\boldsymbol{w}) \,\, + \lambda \| \boldsymbol{w} \| (l_1) }

{ \displaystyle \hat{L}(\boldsymbol{w}) }が凸関数なら、凸最適化問題になると書いてあった。凸関数同士を合わせたものが凸関数になるという証明がなかったけど自明なのかな？

1次元ベクトル{ \displaystyle \boldsymbol{w} }のL1ノルムは

n = 100
x = np.linspace(-1, 1, n)

f = np.abs(x)
plt.plot(x,f,"r-")
plt.show()

f:id:Owatank:20180102153358p:plain

こんな感じの直線で引けるけど、本に書いてあるL1ノルムの図形はひし形みたいなグラフになっている。ﾅﾝﾃﾞﾀﾞﾖヾ(｀Д´)ﾉ
よく読んだらひし形はL1ノルムの等高線を表していると書いてあった。
等高線は小学校のときに地形の等高線しか引いた記憶しかないけど、ここでは d次元ベクトル{ \displaystyle \boldsymbol{w} }のL1ノルムの値を高さとしたグラフが等高線となる。書いてみる

等高線を書くには方眼、meshgridが必要なので用意する

n = 30
x = np.linspace(-1, 1, n)
y = np.linspace(-1, 1, n)

xx,yy = np.meshgrid(x, y)

変数xxとyyが方眼、グリッド線になってくれる。

次に描写したいL1ノルムの方程式を用意する。2次元のグラフとして表示したいので2次元ベクトル{ \displaystyle \boldsymbol{w} = (w1,w2)^{T} }として
{ \displaystyle f(w1,w2) = |w1| + |w2| }のようなL1ノルムの値を高さとして持つ { \displaystyle f(w1,w2) }を作る。
ここでは x軸をw1、y軸をw2として作ることにする。

meshgridで作ったxxとyyは変数を見る限りこんな感じになってるはず
f:id:Owatank:20180102161104p:plain f:id:Owatank:20180102161001p:plain f:id:Owatank:20180102160844p:plain

上の水色と緑の線は5本だけど、プログラムとしてはn = 30とn本で指定される
{ \displaystyle f(w1,w2) }はこの [-1,1]区間の全ての点、組の結果を計算して作る

f = np.abs(xx)+np.abs(yy)

plt.contour(xx,yy,f)
plt.xlim(-1,1)
plt.ylim(-1,1)
plt.gca()
plt.show()

f:id:Owatank:20180102164853p:plain

ひし形になってくれた。 n の値を変えるとよりひし形っぽくなるのも確認できた。
等高線っぽさを見たいので別のメソッドで出力してみると

from mpl_toolkits.mplot3d import Axes3D
fig = plt.figure(figsize=(10,6))
ax = Axes3D(fig)
ax.contourf3D(xx,yy,f)

f:id:Owatank:20180102165031p:plain

いい感じに等高線っぽくなった

このことからL2ノルムでよく見る楕円の形はあるベクトルの要素からできるL2ノルムの等高線、楕円を図示していたということかな。