【CS231n】Linear classification

Stanford大の教材CS231nを使ってNNやCNNを学んでいる.
本記事では,Linear Classificationについて,下記項目を中心に扱う.

Linear Classification

  • k-Nearest Neighborは以下の欠点があった
    • 空間的な非効率性
      • 分類器は全てのtraining dataを記憶し,将来のtest dataとの比較のために保持しておく必要があった.
    • 計算コストがかかる
      • 全てのtraining dataと比較してはじめてtest dataを分類できた.

  • そこでscore functionloss functionを導入する
    • score function
      • raw dataを分類クラスごとにスコア付け
    • loss function
      • 予測したスコアとラベルの持つスコアの差を計算
  • これらを最適化問題(optimization problem)に帰着させる

Parameterized mapping from images to label scores

  • 画像から分類クラスへのスコア付けを考える
    • たとえば,前回のCIFAR-10で考えると,
      • training set {N = 50000}
      • d次元 {D = 32 * 32 * 3 = 3072}
      • 分類クラス数 {K = 10}
    • このときにはscore functionは{f: R^{D} \mapsto R^{K}}となる
Linear classifier
  • 一番シンプルなscore functionはlinear mapping(線形写像
    • {X_i}は画像で[D * 1]へ平らにベクトル化されたもの
    • {W}は[K * D]の行列(重み(weight)ともいう)
    • {b}は[K * 1]のベクトル(バイアス(bias vector)ともいう) $$ f(x_{i}, W, b) = Wx_{i} + b $$

  • 注意点
    • 目標は{W}{b}を設定すること
    • これらを設定したらtraining dataは捨ててよい.

Interpreting a linear classifier

  • このlinear classifierの特徴
    • ピクセルの各3色チャネルに対して,重み付けされた値が算出される.
      (言い換えると,位置に対して3色を好きか嫌いかで重み付けしたものが算出される)
      • "ship"クラスであれば,blueが大きく,redやgreenは小さく重み付けされている.

  • {W}の行ごとに分類器の特性を表していると考えることができる(下図)

f:id:yusuke_ujitoko:20170103142944p:plain (CS231nより引用)

  • 結果のベクトルを低次元としてみなして考察してみる
    • 本当は結果のベクトルは高次元だが,それを二次元だと想定してみる
    • {W}は分類ごとの特性を表している
    • もし{W}を変化させたら,分類の境界は回転する(下図)
    • バイアス{b}は分類の境界線を並進移動させる働きがある

f:id:yusuke_ujitoko:20170103143947p:plain (CS231nより引用)

  • 別の解釈としてtemplate matchingとしても見ることができる
    • {W}の各行と入力画像ベクトルの内積をとってスコア付けしている
    • なにが一番合致しているかをスコア化
    • Nearest Neighborを効率化したものでもある.

f:id:yusuke_ujitoko:20170103144508p:plain (CS231nより引用)

  • バイアス{b}を重み{W}として扱うテクニック
    • 下図のように,{W}{x_i}を拡張して{b}を隠蔽する

f:id:yusuke_ujitoko:20170103155934p:plain

  • 入力データの前処理
    • 正規化をするのが通例
    • 勾配降下法のため.

Loss function

  • 重み{W}を制御したい
    • training dataの真のラベルと分類予測が一致するように

  • loss functionの導入
    • cost functionobjectiveともいう
    • 「lossが高いとだめ」,「lossが低いとよい」という指標

Multiclass Support Vector Machine loss

  • 前提
    • {x_{i}}をi個目の画像ピクセル
    • {y_{i}}をi個目の画像の正しい分類クラスのインデックス
    • score functionを{s}とする.
    • i個目の画像の,j個目のクラスへのスコアは{s_{j}}で表す. $$ s_{j} = f(x_{i}, W)_{j} $$

  • i個目の画像のMulticlass SVM lossは以下の式で表す.
    • i個目の画像に対して,
    • 全クラス分の損失を合計する

$$ L_{i} = \sum_{j \neq y_{i}}{ \max (0, s_{j} - s_{y_{i}} + \Delta) } $$

    • ある画像に対して3つの分類クラスを考える
    • それぞれのクラスへのスコアは{s = ( 13, -7, 11 ) }
    • その画像に対しては1つ目のクラスが真({y_{i} = 0})
    • ハイパーパラメータ{\Delta = 10}(あとで説明あり)

$$ \begin{align} L_{i} &= \sum_{j \neq y_{i}}{ \max (0, s_{j} - s_{y_{i}} + \Delta) } \\ &= \max (0, -7 -13 +10 ) + \max (0, 11 -13 +10 ) \\ &= 0 + 8 \\ &= 8 \end{align} $$

  • 上式を眺めると,
    • ハイパーパラメータ{\Delta = 10}があるので,{s_{j} - s_{y_{i}}}が-10より大きくないと0となる.
    • このSVN loss functionは結局,{s_{j} - s_{y_{i}}}が-10以下となることを目指している.そうでない場合にはlossとなる.(下図がわかりやすい)

f:id:yusuke_ujitoko:20170103202303p:plain (CS231nより引用)

  • 0で閾値を持つ関数{\max(0, -)}hinge lossという
    • squared hinge loss SVM{\max(0, -)^2}もある.
      • こちらはマージンを超えたときのペナルティが大きい.

  • 正規化(Regularization)の必要性
    • このままだと重み{W}が一意に決まらない
      • datasetと重み{W}で,うまく分類できた({L_{i}=0})とする.
      • でも{W}{\lambda W}に入れ替えてもうまく分類できてしまう.

  • loss functionを拡張する
    • regularization penalty {R(W)}を導入する
    • 普通はL2 normを使う.

$$ R(W) = \sum_{k} \sum_{l} {W_{k,l}^2} $$

  • loss functionはdata loss {L_{i}}とregularization lossから構成する
    • {\lambda}はハイパーパラメータ {} $$ \begin{align} L &= \frac{1}{N} \sum_{i}{L_{i}} + \lambda R(W) \\ &= \frac{1}{N}\sum_{i}\sum_{j \neq y_{i}}{\max(0, f(x_{i}; W)_{j} - f(x_{i}; W)_{y_{i}} + \Delta)}+ \lambda \sum_{k}\sum_{l} {W_{k,l}^2} \end{align} $$

  • 大きい重みにペナルティを課す利点は汎用性が増すこと
    • 入力{ x = (1, 1, 1, 1) }
    • 2つの重みベクトル
      • { w_1 = (1, 0, 0, 0) }
      • { w_2 = (0.25, 0.25, 0.25, 0.25) }
    • この場合,{w_{1}^{T} x = w_{2}^{T} x = 1}となり内積は同じになる.
    • でも{w_1}のL2ペナルティは1.0で,{w_2}のL2ペナルティは0.25となる. よって,{w2}の方がペナルティが小さくて,分散しているので好ましい.
    • 分類器は最終的には,全ての入力次元に対して少しづつ影響を受ける方が,一部の入力次元に強力に影響を受けるよりも好ましい.
    • これが汎用性の促進と,過学習の抑制につながる.

Practical Considerations

  • ハイパーパラメータの{\Delta}をどう設定するか
  • {\Delta}{\lambda}は異なるハイパーパラメータに見えるが,実際には同じトレードオフを制御している

Softmax Classifier

  • SVMはよく使われる分類器の1つ
  • 別の人気の分類器は,Softmax classifier

  • Softmax classifier
    • SVMより直観的な結果を出力する
    • 確率的な解釈ができる

  • cross-entropy loss(交差エントロピー誤差)をhinge lossの代わりに使う {} $$ \begin{align} L_{i} &= - \log{ (\frac{\exp(f_{y_{i}})}{\sum_{j} \exp(f_{j})}) } \\ &= -f_{y_{i}} + \log \sum_{j} \exp(f_{j}) \end{align} $$

  • {f_{j} (z) = \frac{\exp(z_{j})}{\sum_{k} \exp(z_{k})}}softmax functionという

  • cross-entropyは真の広がり{p}と推定した広がり{q}で定義される
    • 真の確率と推定された確率のcross-entropyを最小化する {} $$ H(p, q) = - \sum_{x} p(x) \log q(x) $$

  • このcross-entropyの目的は,推定された確率をを真のラベルの重みに集めること

  • 確率的な解釈
    • 下記の式は確率としてみなせる
      • 画像{x_{i}}が真のラベル{y_{i}}に割り当てられ,{W}によってパラメータ化されたもの {} $$ P(y_{i} | x_{i}; W) = \frac{\exp(f_{y_{i}})}{\sum_{j} \exp(f_{j})} $$

  • 安定に計算させるための工夫
    • {\exp(f_{y_{i}})}などは大きい値になる
    • 大きい値の割り算は不安定なので,工夫が必要となる
      • 下記の{C}は自由に決められるので,通常{\log C = - \max f_{j}}とする {} $$ \frac{\exp(f_{y_{i}})}{\sum_{j} \exp(f_{j})} = \frac{C \exp(f_{y_{i}})}{C \sum_{j} \exp(f_{j})} = \frac{\exp(f_{y_{i}} + \log C)}{\sum_{j} \exp(f_{j} + \log C)} $$

SVM vs. Softmax

  • SVMはクラスのスコアとして,loss functionは,真のクラスのスコアがmargin分だけ高くなるよう促進する
  • Softmax classifierは各クラススコアのlog probabilityをとる.そして正規化して,真のクラスのスコアが高くなることを促進する

f:id:yusuke_ujitoko:20170104193805p:plain (CS231nより引用)

  • Softmaxではスコアの順序は意味があるが,大小はそこまで意味がない
    • [1,−2,0]→[exp(1),exp(−2),exp(0)]=[2.71,0.14,1]→[0.7,0.04,0.26]
    • [0.5,−1,0]→[exp(0.5),exp(−1),exp(0)]=[1.65,0.37,1]→[0.55,0.12,0.33]

  • 実用上の大きな差はないが下記の違いはある
    • SVMlocal objective
        • 最初のクラスが真でΔが1の場合,結果が [10, -2, 3]でも[10, -100, -100]でも[10, 9, 9]でもSVMとしては違いがない
    • Softmaxは最後まで満たされることはない(never fully happy with scores)

Summary

  • 画像ピクセルからクラススコアscore functionを定義
    • このセクションでは重み{W}バイアス{b}に依存する線形関数

  • kNN classifierと違って,このparametric approachの利点
    • 一度パラメータを学習すればtraining setを捨てられる
    • 新しいtest画像への予測は高速

  • bias trickの紹介
    • バイアスのベクトルを重み行列に組み込んだ

  • 2つのloss function(SVMSoftmax
    • そのときのパラメータのセットが真のラベルを導けるかを調べる
    • このパラメータの決め方は次のトピックとなる.

理解できなかった内容

The most appealing property is that penalizing large weights tends to improve generalization, because it means that no input dimension can have a very large influence on the scores all by itself.

さらに踏み込んだ学習をするなら

次の記事

yusuke-ujitoko.hatenablog.com

まとめ

yusuke-ujitoko.hatenablog.com