読者です 読者をやめる 読者になる 読者になる

(OCW)機械学習の授業のめもその3

機械学習 OCW

情報源及び出典、参照元

※上記のページおよびpdf、上記以外の参考文献や関連ページを注釈の形でページ末尾に改めて記載します。

関連する文献

黄色いのがいいです。

前回のめも


(OCW)機械学習の授業のめもその2 - 雑なメモ


第六回授業メモ


Event models for text classication*1*2


ナイーブベイズを用いたテキスト分類 - 人工知能に関する断創録

上記すばらしい記事を参考にしたほうがわかりやすいのでこの項目については省略します。

Nonlinear classifiers(非線形分類器)


Linear versus nonlinear classifiers

これまでに出てきた非線形分類器
  • ロジスティック回帰

{
 h_{\theta} (x) = \frac{1}{1 + e^{-{\theta}^T x}}
}

ここからあたらしい非線形分類器、ニューラルネットワーク*3を紹介する。パーセプトロンと呼ばれるものは線形分離できない問題は解けない。


ニューラルネットワーク*4


村上・泉田研究室 ニューラルネットワーク

が参考になるかもしれない。

  • 微分可能な連続関数を出力するパラメータを決定づけるのに利用する
    • 微分可能だからこそ次の「誤差伝播」が可能でそれによって「線形分離できない」問題もとけるようになる
  • 誤差逆伝播法(バックプロパゲーション*5など、データの進行方向は一方向ではない
  • 二乗誤差をコスト関数とする


f:id:misos:20150219030413p:plain

 講義中のニューラルネットの概念図の記号に則って、

  • 入力されるデータの特徴は{x_0,\dots,x_3}
  • 各ユニット(図の○)はそれぞれ別のパラメータ{\theta_i}を持つ
  • 関数{g}シグモイド関数(あえて言えば、連続で微分可能な関数)とする
  • 第k層のユニットは第(k-1)層のユニットの出力{a_i^{(k-1)} \ (i = 1,\dots , m)}を要素にもつベクトル{\vec{a^{(k-1)}}}を入力として{g(\vec{a^{(k-1)}}^T \theta_{(p)}^{(k)})}を出力とする


machine learning - What does the hidden layer in a neural network compute? - Cross Validated


Support Vector Machines(サポートベクターマシン*6 *7 )*8

  • はじめに{\theta^T x}を計算
    • {\theta^T x >0 }の時、そしてその時に限り{1}と予測
    • {\theta^T x \leq 0 }の時、そしてその時に限り{0}と予測
      • {\theta^T x >0 }かつその値が大きいほど予測{1}は”確からしい”
      • {\theta^T x \leq 0 }かつその値が小さいほど予測{0}は”確からしい”

 マージンとは(直感的には)予測の確からしさの指標で、その値が大きいほどそのデータのクラス分類の予測は「確からしい」と言える。


f:id:misos:20150219034249p:plain

もう一つの直感的な理解として上の図を見る。横切る直線(ただし直線に見えるのは二次元だからというだけで一般的な表現ではない)separating hyperplane*9:分割超平面とよばれるものでそこを境にクラスが分類される。マージンはこの超平面からの離れ具合と見て取れる。そしてサポートベクターマシンをモデル化するために以下の表記を導入する。


f:id:misos:20150219033212p:plain
*10

上記板書に従って以下では
{
 y \in \{-1,+1\}  ~クラスを示すフラグ \\
 g(z) =\left\{
    \begin{array}{l}
      1  ifandonlyif  z > 0\\
      -1 otherwise
    \end{array}
  \right.  ~ステップ関数 \\
 h_{w,b}(x) = g( w^T x + b )  ~この講義でのSVMの仮説はこの式で記述する
}
と書くことにする。{b}はパラメータ{\theta}とは分離した定数。

次に直感的だった「マージン」について定式化する必要がある。

Functional and geometric margins(関数マージンと幾何マージン)


machine learning - SVM - what is a functional margin? - Stack Overflow
より抜粋

"A geometric margin is simply the euclidean distance between a certain x (data point) to the hyperlane. "

I don't think that is a proper definition for the geometric margin, and I believe that is what is confusing you. The geometric margin is just a scaled version of the functional margin.

(そして偶然にもこの質問の解答で講義のNg氏の講義資料が登場していた..)

  • 関数マージン(functional margin)

 {(w,b)}の関数マージン

{

\hat{\gamma^{(i)}} = y^{(i)} (w^T x + b)

}

と定義する。この式は{y^{(i)} }の値がデータ{x^{(i)}}の正しい分類先であることに注意すると {\hat{\gamma^{(i)}} } は「データの予測値を決める{(w^T x + b)}の符号とデータ{x^{(i)}}の正しい分類先{y^{(i)} }の積」なのだからこの関数マージンが負の値になるのはデータの予測値の符号が正しい分類先の符号と異なる場合だけであることが分かる。よって関数マージン正の大きい値であるほどその予測は確からしく、逆に負の値ならその予測は間違っていると判断できる。

 正規化項{ || w ||_2 }はなぜ必要か。なぜならサポートベクターマシンの「マージン」は制限がなければいくらでも大きくできてしまうから。例えばもとの関数の結果を100倍するだけでもマージンは広がってしまうようにできる。だけどそれでは正確な分類ができるとは言えない。

 こうしてすべてのデータについての関数マージンを求めたとして

{

 \hat{\gamma} = \min_{i} \hat{\gamma^{(i)}} =\min_{i}  y^{(i)} (\frac{w}{|| w ||_2}^T x + \frac{b}{|| w ||_2})

}

と書くことにする。

  • 幾何マージン(geometric margin)


f:id:misos:20150219035748p:plain*11

 上の図でいう各データ点と分割超平面(図の黒直線)との間の距離こそが幾何マージン。そしてこの距離をどのようにはかるかが問題、そこで分割超平面に重なって存在する任意の点{x'}では{ w^T x + b = 0}であることを利用する。図をもとに考えるとこのときデータ点Aのもつ幾何マージンは「直線ABの長さ」でありつまり

{
 (データ点Aの位置ベクトル) - (ABの長さ)(分割超平面に直交する単位ベクトル) = (点Bの位置ベクトル)  
}

でありもちろん

{
 w^T (点Bの位置ベクトル) + b = 0
}

が成り立つ。これを記号で書き直すと

{
  w^T (x^{(i)} - \gamma^{(i)} \frac{w}{||w||}  ) + b = 0
}

でありこの式から求めたい幾何マージン{\gamma^{(i)} }を求められる。すなわち

{
 \gamma^{(i)}  = y^{(i)} \{ (\frac{w}{||w||})^T x^{(i)} + \frac{b}{||w||} \}
}

と求められた..!しかし注意すべきは{||w|| = 1 }の場合、関数マージンと幾何マージンの式は違いがないこと、そして幾何マージンは重みづけ{w}を定数倍しても変化しないこと。

最適マージン分類器(optimal margin classifier)

 それじゃあ「よいSVM(サポートベクターマシン)」って何?という話になる、つまり「よい」と判断する指標が必要。ここで言葉の意味を定義。

  • サポートベクトル
    • クラスを分割する超平面に対して最も小さい(幾何)マージンを持つ点

サポートベクターマシンは途中までやって次回(以下)の講義にまたぎます。

(OCW)機械学習の授業のめもその4 - 雑なメモ

参考文献と関連ページ

  • 上記のページおよびpdf以外の参考文献や関連ページ

*1:McCallum, A. and Nigam K. "A Comparison of Event Models for Naive Bayes Text Classification". In AAAI/ICML-98 Workshop on Learning for Text Categorization, pp. 41-48. Technical Report WS-98-05. AAAI Press. 1998,pdf

*2:cs229-notes2.pdf page12以降

*3:ニューラルネットワーク

*4:http://www-ailab.elcom.nitech.ac.jp/lecture/neuro/menu.html

*5:http://ipr20.cs.ehime-u.ac.jp/column/neural/chapter6.html

*6:サポートベクターマシン - Wikipedia

*7:関連資料;http://see.stanford.edu/materials/aimlcs229/cs229-notes3.pdf

*8:映像43:43~

*9:Supporting hyperplane - Wikipedia, the free encyclopedia

*10:引用元;https://www.youtube.com/watch?v=qyyJKd-zXRE#t=4063

*11:引用元:cs229-notes3.pdf