PRML復活の呪文 part1 (1.1)

# このページでは

- あの黄色い本（パターン認識と機械学習）の自分なりの解説を書きます
- 数か月後、数年後にPRMLを読んでもスッと頭に入るように  
  **＝勉強した直後の自分に復活できるように**
- あまり大事でないと感じた節は飛ばしたりします
- 演習問題も時々解きます


# 想定レベル＝私のレベル

- 高校レベルの数学はとりあえず出来る  
  置換積分とかも（公式みながらすれば）解ける
- 線形代数について、固有値や行列式などを勉強した記憶はある  
  （固有値などのイメージを掴めるような解説を入れたい）

# 数学表記ルール（Mathematical Notation）

- ベクトルは太字ローマン体$\boldsymbol{\rm{x}}$で表記。列ベクトル
- 1次元ベクトル$\boldsymbol{\rm{x_i}}= \\{x_{i1}\\}$を複数個観測したとする。
  すなわち、$\boldsymbol{\rm{x_1}}= \\{x_{11}\\}, \cdots, \boldsymbol{\rm{x_N}}= \\{x_{N1}\\}$を観測したときは
**x**$=(\boldsymbol{\rm{x_1}}, \cdots, \boldsymbol{\rm{x_N}})^T$と表記する  
※$\boldsymbol{\rm{x}}$と**x**でフォントが異なっていることに注意
- $\boldsymbol{\rm{x}}$は次元数＝特徴次元数、**x**の次元数＝1次元ベクトル$\boldsymbol{\rm{x}}$の観測数であることに注意

# TL;DR

- ある関数を$M$次の多項式で推定したい問題を考える。
$M$を大きくしすぎると訓練データに過剰にフィッティングしてしまい、本当に推定したい関数とかけ離れた関数となってしまう。
これを過学習 (over-fitting) という。
- 過学習を抑えるために、正則化 (regularization) というテクニックがある。

# 導入部

- 手書き数字画像データセットの例で説明
- 訓練データと異なるデータ（＝テストデータ）を正しく判定できることが大切　　
※手書き数字の筆跡などには無数のパターンがあり得るので、訓練データと全く同じパターンしか正しく判定出来ないとなると嬉しくない
- 訓練データと異なるデータを正しく判定できる能力を汎化性能 (generalization) という
- データ間のパターンのばらつきを抑えるため、前処理 (preprocessing) と呼ばれる処理で
手書き数字の大きさを揃える等の処理をする。こうすることで、文字の場所やスケールといったパターンのばらつきが抑えられ、学習する問題が簡単化される。この処理は特徴抽出 (feature extraction) とも呼ばれる
- [筆者補足]  
前処理は非常によく使われる。画像データでは明るさ（輝度値）のばらつきを抑えるために、輝度値の最大値を1に揃える（正規化という）演算やカラー画像をグレー画像に変換する演算もよく使われる
- 教師あり学習 (supervised learning)、分類 (classification)、回帰 (regression)、教師なし学習 (unsupervised learning)、強化学習 (reinforcement learning)の用語説明。これらの解説は他に譲ります

# 1.1 多項式曲線フィッティング

##最小二乗法によるフィッティング

- $x$と$y$は$y=\sin (2 \pi x)$という関係式が成り立っている前提。この節での例題ではtarget vector $t$は$y$に少しノイズが乗ったもの  
※現実的にはどんな関係式が成り立っているかは未知な点に注意。既知だったらわざわざ推定する必要がない
- （1次元ベクトル$x$, $t$を複数個まとめてベクトルとした）**X**と**t**から$t=\sin (2 \pi x)$という関係式を推定したい。推定できれば未知のデータ
$\boldsymbol{\mathrm{\hat{x}}}$に対する値$\hat{t}$が推定できる
- **t**にはノイズが乗っているので**x**から**t**を推定する際には不確かさ (uncertainty) が残る。uncertaintyを扱う道具に確率理論がある（詳しくは後で出てくる）
- ここでは$t$=($M$次の$x$の多項式)で表されると仮定し、
$$
y(x, \boldsymbol{w} ) = w_0 + w_1 x + w_2 x^2 + \cdots + w_M x^M = 
\sum_{j=0}^M w_j x^j  \tag{1.1}
$$
とする。やりたいことは学習によって$\boldsymbol{w}$をいい感じの値に設定し、
$t=\sin (2 \pi x)$という関係式に近いものを推定する（多項式曲線にフィッティングする）こと
- $\boldsymbol{w}$をいい感じの値に設定する方法は、target vector $t$と(1.1)の
多項式による推測結果$y(x, \boldsymbol{w} )$の差（誤差）を誤差関数 (Error function) として定義し、訓練データでの誤差関数が最少になる$\boldsymbol{w}$を数学テクニックで探す  
※誤差関数が最少＝誤差が最少＝推定がうまくいっている
- 誤差関数は問題の設計者（我々）が自由に決めていい[^1]が、ここでは一般的に使われる以下の二乗誤差を使う
$$
E( \boldsymbol{w} ) = \frac{1}{2} \\{  y(x, \boldsymbol{w} ) - t_n \\}^2 \tag{1.2}
$$
※$\frac{1}{2}$がついている理由は微分したときに$\\{\cdots\\}^2$の2と打ち消しあって便利だから

[^1]: 極端な話、例えば四乗誤差でもよいが数学的に便利なので二乗誤差がよく使われる

- 誤差関数は二次関数なので、誤差が最少になる$\boldsymbol{w}$は
($\boldsymbol{w}$で微分した式) = 0
を解けば求まる（⇒演習1.1）。こうして求まった$\boldsymbol{w}$は$\boldsymbol{w^{\*}}$[^2]と表し、その時の多項式は$y(x, \boldsymbol{w^{\*}} )$と表す。

[^2]: テキストでは\*ではなく★だが、書き方が分からないので\*にする

## 過学習とは

- さて、$x$の多項式の次数$M$はどう決めるのか？これはモデル選択 (model selection) と呼ばれる重要な問題。次数が低すぎる（例えば1次関数＝直線）とどう頑張っても$\sin (2 \pi x)$を表現できない。かといって次数が高すぎると図1.4のように、訓練データには完璧にフィッティングしているが真の関数である$\sin (2 \pi x)$とかけ離れた関数になってしまう。訓練データに過剰にフィッティングしてしまい、本当に推定したい関数とかけ離れた関数となってしまう振舞いを過学習 (over-fitting)という。原因は訓練データに加えられているrandom noiseに過剰にフィッティングし、$\boldsymbol{w}$の係数がすごく大きい or 小さい値になっているため
- $M$の一つの決め方は、訓練データと同じ条件で生成された別のデータ（＝テストデータ）との誤差を評価し、誤差が小さくなる$M$にする方法
- 学習データの数が増えると過学習は抑えられる⇔学習データの数が増えると、より複雑（柔軟）な関数（＝次数$M$が高い）にフィッティングできるようになる。では、次数$M$は学習データの数を見て決めればいいか？というと答えはNoで、本当は推定したい関数の複雑さに合わせて次数$M$を決めるべき
- $\boldsymbol{w}$を最小二乗法によって推定したが、最小二乗法は最尤推定 (maximum likelihood)と呼ばれる推定法になる。そして、過学習は最尤推定によって起こる特性
- ベイズ推定という方法を使えば過学習は回避できる。詳しくは今後でてきます

## 正則化とは

- 最尤推定で過学習を抑えるためのテクニックとして、(1.2)式に罰則項を足して、
$\boldsymbol{w}$の係数がすごく大きい or 小さい値にならないようにする
正則化 (regularization) がある

```math
\tilde{E}(\boldsymbol{w}) = \frac{1}{2} \sum_{n=1}^N 
\Bigl\{ y(x_n, \boldsymbol{w}) - t_n \Bigr\}^2 + 
\frac{\lambda}{2} || \boldsymbol{w}^2 ||, \tag{1.4}\\

|| \boldsymbol{w}^2 || = w_0^2 + w_1^2 + \cdots + w_M^2
```
（正則化つき誤差関数の最小化⇒演習1.2）

- [筆者補足]  
正則化も簡単ながら効果が大きいのでよく使われる。scikit-learnでフィッティングを行う
際にも、罰則項のあり/なし、ありの場合は式(1.4)のように二乗にするか、絶対値にするかを選べる
- $\boldsymbol{w}$の係数の絶対値が大きくなるにつれ $ \frac{\lambda}{2} || \boldsymbol{w}^2 || $が大きくなり、誤差関数$ \tilde{E}(\boldsymbol{w}) $が
大きくなってしまう（＝罰則項）。そのため、係数の絶対を小さくしつつ、推測結果$y(x, \boldsymbol{w} )$と$t_n$の差（誤差）を小さくしようとする。
罰則項をどれぐらい影響させるかを決めるパラメータが$\lambda$であり、これは人間が決める必要があるパラメータ[^3]
- $\lambda$が小さすぎると過学習を抑えられない。逆に大きすぎると$\boldsymbol{w}$の係数がほぼ0となってしまい、
(1.1)式を見ると分かるようにほぼ$y=0$となってしまうのでフィッティング精度が悪くなる。
- 適した$\lambda$を決める単純な方法としては、訓練データを訓練セットと検証セット (validation set)に分けて、
$\lambda$の値をいろいろと変えたときの検証セットに対するフィッティング精度を見る方法がある。

[^3]: なお、$\lambda$のように学習によって自動的に獲得されるパラメータでなく、人間が決める必要があるパラメータのことをハイパーパラメータとよぶ

# 演習問題
## Exercise1.1

$w$についての2次式なので、($w$について微分）=0を解けば誤差関数が最少になる$w$が求まる。
(1.1)式を(1.2)式に代入

```math
E(\boldsymbol{w}) = \frac{1}{2} \sum_{n=1}^N 
\Bigl\{ \sum_{j=0}^M (w_j x_n^j - t_n ) \Bigr\}^2 \tag{e1}
```
し、それを$w_i$について微分する。
(e1)式の$\sum_{j=0}^M w_j x_n^j$ の部分で、
$w$の添え字が$i$のときのみ$w_i$での微分がゼロにならず、$x_n^i$が残ることに注意すると

```math
\begin{align}
\frac{dE}{dw_i} &= \frac{1}{2} \sum_n \Bigl[ 
2 \Bigl\{ \sum_j w_j x_n^j - t_n \Bigr\} x_n^i \Bigr] \\
  &= \sum_n \sum_j \Bigl( w_j x_n^j - t_n \Bigr) x_n^i \\
  &= \sum_n \sum_j \Bigl( w_j x_n^{i+j} - x_n^i t_n \Bigr) \\ 
  &= \sum_n \sum_j w_j x_n^{i+j} - \sum_n x_n^i t_n = 0
\end{align}
```

整理すると

```math
\sum_n \sum_j w_j x_n^{i+j} = \sum_n x_n^i t_n \tag{e2}
```
となるので、右辺は解けた。
(e2)式の左辺について、添え字に注目して書き換えると

```math
\sum_n \sum_j w_j x_n^{i+j} = \sum_j w_j \sum_n n^{i+j}
```
となるので左辺も解けた。

## Exercise1.2

解き方はExercise1.1と同じで($w$について微分）=0を解く。

```math
\begin{align}
\frac{dE}{dw_i} &= \frac{1}{2} \sum_n \Bigl[ 
2 \Bigl\{ \sum_j w_j x_n^j - t_n \Bigr\} x_n^i \Bigr] + \frac{\lambda}{2} 2 w_i \\
  &= \sum_n \sum_j w_j x_n^{i+j} - \sum_n x_n^i t_n + \lambda w_i = 0
\end{align}
```

整理すると

```math
\sum_n \sum_j w_j x_n^{i+j} + \lambda w_i = \sum_n x_n^i t_n \tag{e1.3}
```
となり、右辺はEx1.1と同じ形になった。  
テキストの(1.122)式をにらみながら(e1.3)式をにらむと
$$
\sum_n x_n^{i+j} + \lambda w_i
$$
を$\tilde{A_{ij}}$として表したい。$\lambda w_i$は$\sum$の添え字$n$とは関係なく、
(1.122)式の$\sum$の添え字$j$が$i$のときのみ有効になる。
そこで、$i=j$とのきのみ1となる変数を$I_{ij}$とすると

```math
\tilde{A}_{ij} = \sum_n x_n^{i+j} + I_{ij} \lambda
```
と書ける。  
以上により、Ex1.1と同様の記法で解を表せた。