[ML] 機器學習基石：第九講 Linear Regression

ML：基礎學習
課程：機器學習基石
簡介：第九講 Linear Regression

$$\begin{gathered} \mathbf{x}=(x_0,x_1,x_2,\cdots ,x_d) \\ y\approx \sum _{i=0}^d{w}_i{x}_i \\ h(\mathbf{x})={\mathbf{w}}^{\mathbf{Tx}} \end{gathered}$$

Error Measure

$$E_{in}(h\mathbf{w})=\frac{1}{N}\sum _{n=1}^N(\underset{{\mathbf{w}}_{\mathbf{n}}^{\mathbf{Tx}}}{\underbrace{h({\mathbf{x}}_{\mathbf{n}})}}-y_n{)}^2$$

$$E_{out}(\mathbf{w})=\underset{(\mathbf{x},y)\sim P}{\epsilon }({\mathbf{w}}^{\mathbf{Tx}}-y{)}^2$$

$$\begin{array}{rl}{E}_{in}(\mathbf{w})& =\frac{1}{N}\sum _{n=1}^N({\mathbf{w}}_{\mathbf{n}}^{\mathbf{Tx}}-y_n{)}^2\\ & =\frac{1}{N}\sum _{n=1}^N({\mathbf{x}}_{\mathbf{n}}^{\mathbf{Tw}}-y_n{)}^2\\ & =\frac{1}{N}{\Vert \begin{array}{c}{\mathbf{x}}_{\mathbf{1}}^{\mathbf{Tw}}-y_1\\ {\mathbf{x}}_{\mathbf{2}}^{\mathbf{Tw}}-y_2\\ ⋮\\ {\mathbf{x}}_{\mathbf{N}}^{\mathbf{Tw}}-y_N\end{array}\Vert }^2\\ & =\frac{1}{N}{\Vert \left[\begin{array}{c}{\mathbf{x}}_{\mathbf{1}}^{\mathbf{T}}\\ {\mathbf{x}}_{\mathbf{2}}^{\mathbf{T}}\\ ⋮\\ {\mathbf{x}}_{\mathbf{N}}^{\mathbf{T}}\end{array}\right]\mathbf{w}-\left[\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_N\end{array}\right]\Vert }^2\\ & =\frac{1}{N}{\Vert \underset{\mathrm{N}\times (\mathrm{d}+1)}{\underbrace{\mathbf{X}}}\underset{(\mathrm{d}+1)\times 1}{\underbrace{\mathbf{w}}}\mathbf{-}\underset{\mathrm{N}\times 1}{\underbrace{\mathbf{y}}}\Vert }^2\end{array}$$

求最小值 $E_{in}$

$$\text{Double exponent: use braces to clarify}$$ $$\begin{array}{rl}\frac{2}{N}({\mathbf{X}}^{\mathbf{TXw}}\mathbf{-}{\mathbf{X}}^{\mathbf{Ty}})& =0\\ {\mathbf{X}}^{\mathbf{TXw}}={\mathbf{X}}^{\mathbf{Ty}}\end{array}$$

${\mathbf{X}}^{\mathbf{TX}}$ invertible	${\mathbf{X}}^{\mathbf{TX}}$ singular
$({\mathbf{X}}^{\mathbf{TX}}{)}^{-1}{\mathbf{X}}^{\mathbf{Ty}}$	${\mathbf{X}}^{\mathbf{+}}\mathbf{y}$

程式建議直接使用別人寫好的 pseudo-inverse

$$\frac{\partial {\mathbf{w}}^{\mathbf{TAw}}}{\partial \mathbf{w}}=2\mathbf{A}\mathbf{w}$$

使用微分乘法法則
$$\begin{array}{rl}f\left(\mathbf{w}\right)& ={\mathbf{w}}^T\mathbf{A}\mathbf{w}=\sum _{i=1}^n\sum _{j=1}^n{a}_{ij}{w}_i{w}_j\\ \frac{\partial f}{\partial \mathbf{w}}& =(\frac{\partial f}{\partial w_1},\frac{\partial f}{\partial w_2},\frac{\partial f}{\partial w_3},\cdots ,\frac{\partial f}{\partial w_n}{)}^T\\ & =(2\sum _{k=1}^n{a}_{1k}{w}_k,2\sum _{k=1}^n{a}_{2k}{w}_k,\cdots ,2\sum _{k=1}^n{a}_{nk}{w}_k{)}^T\\ & =2\mathbf{A}(w_1,w_2,\cdots ,w_n{)}^T\\ & =2\mathbf{A}\mathbf{w}\end{array}$$

Linear Regression Algorithm

1. 從 $D$ 建構出 $\mathbf{X}$ 跟 $\mathbf{y}$
2. 算出 pseudo-inverse ${\mathbf{X}}^{\mathbf{+}}$
3.  ${\mathbf{w}}_{\mathbf{opt}}={\mathbf{X}}^{\mathbf{+}}\mathbf{y}$

good $E_{out}$？

因有限的 $d_{vc}$ 如同 perceptrons，相當於二分法
$E_{in}\mathrm{的}\mathrm{平}\mathrm{均}$

$$\overline{E_{in}}=\underset{D\sim P^N}{\epsilon }\{E_{in}({\mathbf{w}}_{\mathbf{opt}\mathbf{w}\mathbf{.}\mathbf{r}\mathbf{.}\mathbf{t}\mathbf{D}})\}=noiselevel\cdot (1-\frac{d+1}{N})$$

$$\begin{array}{rl}{E}_{in}({\mathbf{w}}_{\mathbf{opt}})& =\frac{1}{N}{\Vert \mathbf{y}-\underset{prediction}{\underbrace{\hat{\mathbf{y}}}}\Vert }^2\\ & =\frac{1}{N}{\Vert \mathbf{y}\mathbf{-}\mathbf{X}\underset{{\mathbf{w}}_{\mathbf{opt}}}{\underbrace{{\mathbf{X}}^{\mathbf{+}}\mathbf{y}}}\Vert }^2\\ & =\frac{1}{N}{\Vert (\mathbf{(}\mathbf{I}\mathbf{-}{\mathbf{XX}}^{\mathbf{+}}\mathbf{)}\mathbf{y})\Vert }^2\\ & =\frac{1}{N}{\Vert (\mathbf{(}\mathbf{I}\mathbf{-}\mathbf{H}\mathbf{)}\mathbf{y})\Vert }^2\\ call{\mathbf{XX}}^{\mathbf{+}}& hatmatrix\mathbf{H}\end{array}$$

$\mathbf{H}$ 即是投影轉換矩陣，故
$y=f(\mathbf{x})+noise$， $f(\mathbf{x})$ 為理想的目標函數
$$\text{Double exponent: use braces to clarify}$$ $$\begin{array}{rl}trace(\mathbf{H})& =trace({\mathbf{XX}}^{\mathbf{+}})\\ & =trace({\mathbf{XX}}^{\mathbf{+}})\\ & =trace(\mathbf{X}\mathbf{(}{\mathbf{X}}^{\mathbf{TX}}{\mathbf{)}}^{\mathbf{-}\mathbf{1}}{\mathbf{X}}^{\mathbf{T}})\\ & =trace(\mathbf{(}{\mathbf{X}}^{\mathbf{TX}}{\mathbf{)}}^{\mathbf{-}\mathbf{1}}{\mathbf{X}}^{\mathbf{TX}})\\ & =trace({\mathbf{I}}_{\mathbf{(}\mathbf{d}\mathbf{+}\mathbf{1}\mathbf{)}\mathbf{x}\mathbf{(}\mathbf{d}\mathbf{+}\mathbf{1}\mathbf{)}})\\ & =d+1\end{array}$$

$$\overline{E_{out}}=noiselevel\cdot (1+\frac{d+1}{N})$$ 因訓練後，會往 $\mathbf{X}$ domain 靠近，故
$E_{in}$ 會被修正 d+1 維的錯誤
$E_{out}$ 則再糟也只是再加上 d+1 維的錯誤
$E_{out}-E_{in}=\frac{2(d+1)}{N}$

${\sigma }^2$ noise level

H 的特性

Linear Classification & Linear Regression 比較

Linear Classification	Linear Regression
NP-hard 的解 $$\begin{array}{rl}y& =-1,+1\\ h(\mathbf{x})& =sign({\mathbf{w}}^{\mathbf{Tx}})\\ err(\hat{y},y)& =[\hat{y}\ne y]\end{array}$$	簡單易解 $$\begin{array}{rl}y& =\mathbb{R}\\ h(\mathbf{x})& ={\mathbf{w}}^{\mathbf{Tx}}\\ err(\hat{y},y)& =(\hat{y}\ne y{)}^2\end{array}$$

error 比較

$$\begin{array}{rl}{E}_{out}(\mathbf{w})& \stackrel{VC}{\le }classification{E}_{in}(\mathbf{w})+\sqrt{\cdots }\\ & \le regression{E}_{in}(\mathbf{w})+\sqrt{\cdots }\end{array}$$

regression 相較於 classfication 較為鬆散，也因此易解
故可用在

• 基本的分類器，大多數表現不差
• PLA/pocket 的初始值，加快 PLA/pocket 的速度