# Error measure

$$
\min_{\color{blue}{\mathbf{w}}} E_{in}(\color{blue}{\mathbf{w}})=\frac{1}{N}\left \| \mathbf{\color{red}{X}\color{blue}{w}-\color{purple}{y}} \right \|^{2}
$$

# Gradient

$$
\nabla E_{in}(\color{blue}{\mathbf{w}})=\frac{2}{N}\left(\color{red}{\mathbf{X}^{T}\mathbf{X}}\color{blue}{\mathbf{w}}-\color{red}{\mathbf{X}^{T}}\color{purple}{\mathbf{y}}\right)
$$

# Closed-form Solution

$$
\color{blue}{\mathbf{w}_{LIN}}=\left(\color{red}{\mathbf{X}^{T}\mathbf{X}}\right)^{-1}\color{red}{\mathbf{X}^{T}}\color{purple}{\mathbf{y}}=\color{red}{\mathbf{X}^{\dagger}}\color{purple}{\mathbf{y}}
$$

$\color{red}{\mathbf{X}^{\dagger}}$ 這個東西叫做 $Pseudo-inverse$，因為其所包含的 $\left(\color{red}{\mathbf{X}^{T}\mathbf{X}}\right)^{-1}$ 有可能不存在反矩陣。

- 但是通常來說會存在，因為 $N \gg d+1$
- 如果真的不存在反矩陣，那麼就用已經被開發好的近似解 optimal solution

# 真的有學會嗎

經過神奇的線性代數圖解，可以證明：

$$
\overline{E_{in}}=\underset{\mathcal{D}\sim P^{N}}{\varepsilon}\left\{E_{in}\left(\mathbf{w}_{LIN}\ w.r.t.\ \mathcal{D}\right)\right\}=\text{noise level}\times\left(1-\frac{d+1}{N}\right)
$$

Noise level 在平均的情況下，就是 $\sigma^{2}$。
$\overline{E_{out}}$ 可以用更複雜的方式得出類似的形式：

$$
\overline{E_{in}}=\sigma^{2}\left(1-\frac{d+1}{N}\right)\\
\overline{E_{out}}=\sigma^{2}\left(1+\frac{d+1}{N}\right)
$$

也就是說 expected generalization error 是：

$$
|\overline{E_{in}}-\overline{E_{out}}|=\sigma^{2}\frac{2(d+1)}{N}
$$

因此跟 VC 很類似的，我們可以確信，當 N 夠大，則兩者會非常接近。

# 上下界

square error 實際上是 0/1 error 的上界，只要以 $s=\mathbf{w}^{T}\mathbf{x}$ 為 x 軸， y 值為 y 軸作圖就可以觀察到這件事。

回顧之前的：

$$
\text{classification } E_{out} \le \text{classification }\ E_{in} + \sqrt{\cdots}\\
\le \text{regression }\ E_{in} + \sqrt{\cdots}\\
$$

也就是說我們找到了一個更鬆的上界。

代表其實可以用 regression 來去學 classification 的內容，用 regression 學到的 $\mathbf{w}$ 直接取 sign 來預測 classification；或者以 regression 學到的 $\mathbf{w}$ 作為 PLA/Pocket 的初始 $\mathbf{w}$。