Linear classification: Support Vector Machine, Softmax 線形分離による分類アルゴリズムの解説．
Parameterized mapping from images to label scores
学習や評価に使うデータがD次元のベクトル空間で，ラベルは1からKまでの整数とする．
$f: \mathbb{R} ^D \mapsto \mathbb{R} ^K $ のような関数をscore function という.
Linear classifier
$$ f(x_i, W, b) = Wx_i + b$$
$x_i$ はD次元縦ベクトルで，$W$はK行D列ベクトル，$b$はk次元縦ベクトルである．$W$をweights, $b$をbiasesといい，$W$, $b$が最適になるようにするのが学習．学習が終わればtrain dataは予測には必要ないし，予測の計算は行列算だけなのでkNNより非常に高速．
$W$の第i行$W_{i:}$は第iクラスのclassifierである．つまりexample $x$ があるとき， $W_{i:} x $はxがどれほど第iクラスに属するらしいかを与える．
Interpretation of linear classifiers as template matching
$W_{i:}$ を第iクラスのtemplate(or prototype)と考えることもできる．各クラスのtemplateたちとexampleがどれほど似ているかを比較して，最良のものを選び出す．
Bias trick
$$ f(x_i, W, b) = Wx_i + b$$ について，CIFAR-10では$W$は10行3072列の行列で，$x$ は3072次元のベクトル, $b$は10次元のベクトルだが，$W$の第3073列に$b$を挿入して，$x$の11次元目を1とすれば，$$f(x_i, W) = Wx_i$$ と簡潔に書ける．これをbias trick という．
Image data ppreprocessing
CIFAR-10のデータは0から255の値を取る整数の3072次元のベクトルだが，ベクトルごとに標準化を行って，平均0, 標準偏差1に揃える．
Loss function(cost function, objective)
score function によって計算した予測と正しい答えの食い違いを計量する関数で，これができるだけ小さな値になるようにscore functionの係数を変えていく．
Multiclass Support Vector Machine loss
loss functionの一つ．exapmle $x_i$に対して$s = f(x_i, W)$とするとき，$x_i$におけるloss $L_i$を $$L_i = \sum_{j \neq y_i} max(0, s_j - s_{y_i} + \Delta ) (\Delta;マージン は定数)$$ で定義する．0に閾値をもつ$max(0, -)$の形の関数をhinge loss という．
Regularization
重みの行列の各要素は絶対値が小さくなるように最適化する．そのためにloss functionにregularization項 $$ R(W) = \sum_k \sum_l W^2 _{k,l} == ||W||_{F}^2 $$ を挿入する．理由は
- $W$のある要素$W_{ij}$がほかと比べて大きいというのは，画像データの第j要素が画像のクラス分類に大きな影響があるということで，実際にそういうことは無さそうなので無くしたい(過学習の抑制)
- $W$をできるだけ一意に決めたい( $W$が$x_i$の分類に成功するとき，$\lambda W$ ($\lambda > 1 $)も分類に成功する．) (2.の理由はNielsenには無かった気がする) regularization項を加えて，loss functionは $$ L = \frac{1}{n}\sum_i L_i + \lambda R(W)$$ となる．($\lambda$はregularization定数)
Practical Considerations
setting data
$\Delta$と$\lambda$は一見別々に設定するハイパーパラメーターだが，$\Delta$は判別成否によるlossを計量するをどれほど重視するかというハイパーパラメーターで，$\lambda$はどれほどregularzationを重視するかというハイパーパラメーターだから，どちらか一方を1.0と定めてもう一方を調整する．ふつう$\Delta =1.0$とする．
Softmax classifier
SVM分類器のほか，よく使われる分類器にSoftmax がある． $f(x_i;W)= Wx_i$にって各クラスのスコアを計算したあと，Softmax関数によって確率にする． $f(x_i;W)= Wx_i = f$とすると， $$softmax(f) = [\frac{e^{f_1}}{\sum_k {e^{f_k}}}, ... , \frac{e^{f_K}}{\sum_k {e^{f_k}}}]^T$$ またこれによるloss $$L_i = -log(\frac{e^{f_{y_i}}}{\sum_k e^{f_k}}) = -f_{y_i} + log \sum_k e^{f_k} $$ をcross-entropy loss という．
謎
Nielsenの定義と食い違う．今度調べる．
$C_i = $
$-\sum_k [y_k ln a_j ^L + (1 - y_k) ln (1 - a_j ^L)]$ 式(63)のデータセットによる和を無視した変形
$= - ln a_i - \sum_{k \neq y_i} ln (1 - a_k)$
$= -ln \frac{e^{f_{y_i}}}{\sum_k e^{f_k}} - \sum_{k \neq y_i} ln ( 1 - \frac{e^{f_{y_k}}}{\sum_k e^{f_k}})$ (softmaxを使った場合)
$\neq L_i$
Information theory view (わからん)
真の確率分布$p$と推定された確率分布$q$があるとき,p, qの間のcross-entropy$H(p, q)$は
$$ H(p, q) = -\sum_x p(x)logq(x) = H(p) + D_{KL} (p||q)$$
で定義される．
推定された確率分布$q$とは$q=\frac{e^{f_{y_i}}}{\sum_k e^{f_k}}$ のことで，pは正しい分類すなわち$p = [o, ..., 1, ..., 0]$(y_i番目が1).
また$H(p)=0$から，$H(p, q) ==D_{KL} (p||q)$
Probablistic interpretation
$$ P(y_i| x_i;W) = \frac{e^{f_{y_i}}}{\sum_k e^{f_k}}$$ は$W$という重み行列があり，example $x_i$が与えられた時，そのラベルが$y_i$(正解)である事後確率と考えることができる．それを最大にするような$W$を計算することは最尤推定(Maximum Likelihood Estimation, MLE)であって，またregularization項$R(W)$はガウス事前分布を仮定した時の$W$のMaximum a posteriori(MAP)と考えることができる．
Practical issues: Numeric stability
$\frac{e^{f_{y_i}}}{\sum_k e^{f_k}}$ の分母分子は非常に大きな数になりがちで，数値計算上の問題が生じうるので，何かしら定数をexponentialの中に足して計算できるようにする．一般的には$C = -log(max_j f_j)$を足す．
import numpy as np
f = np.array([123, 456, 789])
p = np.exp(f)/np.sum(np.exp(f))
print(p)
f -= np.max(f)
p = np.exp(f)/np.sum(np.exp(f))
print(p)
SVM vs. Softmax
Softmax classifier provides “probabilities” for each class.
fの出力が$[1, -2, 0]^T$のとき，softmaxの結果は$[0.7, 0.04, 0.26]^T$
Wの全ての要素が半分になると，fの出力は
$[0.5, -1, 0]^T$で，softmaxの出力は$[0.55, 0.12, 0.33]$
よって確率はdiffuse(拡散)する．究極的には，$W$の要素の値たちが小さくなるに連れて，softmaxの結果は一様分布に近づいていく．よって，softmaxの結果はどのクラスに分類されるかの確率の形をしているが，実際には順序だけを考えるべき．
In practice, SVM and Softmax are usually comparable.
正解ラベルが1のexampleで，$Wx_i = [10, -2, 3]^T$であり，$\Delta = 1.0$であるとき，lossは0.$[10, -100, -100]^T,これは [10, 9, 9]^T$でも同様．一方softmaxは$[10, 9, 9]^T$で大きなlossを出す．このようにSVMのlossは近視眼出来なところがある．これは利点にもなりうる．例えば自動車分類器の行が，自動車とトラックの分離に殆どの要素を割いている時，すでに良好に分離が可能になったカエルのexampleに影響されるべきではない．例えば$[自動車, トラック, カエル]^T = [1, 2, 12]^T$のスコアがでているとき，softmaxでは多少のlossが発生して$W$が書き換えられてしまうが,SVMでは書き換えられない.(この解釈でいいのか？)
