Introduction, Neural Networks Construction
All modern machine learning algorithms are just nearest neighbors. It’s only that the neural networks are telling you the space in which to compute the distance.
Risk: expected loss
\[R(\theta) = \mathbb{E}\left[\mathcal{L}(\theta, X, Y)\right]\]Empirical Risk: average loss
\[\hat{R}(\theta) = \frac{1}{N}\sum_{i=1}^N\mathcal{L}(\theta, x_i, y_i)\]Empirical Risk too high: underfitting; too low: overfitting.
其实就是用 Bayesian 的视角来看待 Regularization。
就是我们现在是要最大化
\[p(\theta \mid \mathcal{D}) = \frac{p(\mathcal{D} \mid \theta)\cdot p(\theta)}{p(\mathcal{D})}\]这东西叫 MAP 也就是 Maximum A Posteriori。
取对数之后，我们就可以得到
\[\begin{aligned} \arg\max_{\theta}\log p(\theta \mid \mathcal{D}) &= \arg\max_{\theta}\left\{\log p(\mathcal{D} \mid \theta) + \log p(\theta) - \log p(\mathcal{D})\right\} \\ &= \arg\max_{\theta}\left\{\log p(\mathcal{D} \mid \theta) + \log p(\theta)\right\} \end{aligned}\]而 \(\log p(\mathcal{D} \mid \theta)\) 其实就是 loss 嘛。那 \(\log p(\theta)\) 其实就是 regularization。
就比如说我们现在假设 \(\theta\sim\mathcal{N}(0, \sigma^2I)\)，那么我们就可以得到
\[\log p(\theta) = -\frac{1}{2}\sum_{i=1}^n\left(\frac{\theta_i}{\sigma}\right)^2\log\left(\frac{1}{\sigma\sqrt{2\pi}}\right) = \lambda\Vert\theta\Vert^2\]其中 \(\lambda\) 是一个常数。
Linear Regression:
\[\hat{y}(x, w) = \sum_{j=0}^{M-1}w_j\phi_j(x) = w^{\top}\phi(x)\]其中 \(\phi\) 叫 bias functions。一般 \(\phi_0(x)=1\)。
然后其实我们认为真实值 \(y\) 是
\[y = \Phi w + \epsilon, \quad \epsilon_i \sim \mathcal{N}(0, \sigma^2)\]然后根据 loss function
\[\mathcal{L}(w) = \frac{1}{2}\left(y - \Phi w\right)^{\top}\left(y - \Phi w\right) + \frac{\lambda}{2}w^{\top}w\]容易得到
\[\hat{w} = (\Phi^{\top}\Phi + \lambda I)^{-1}\Phi^{\top}y\]这边简单复习一下上学期学的东西。假设没有 regularization，那么我们就有
\[\hat{w} = (\Phi^{\top}\Phi)^{-1}\Phi^{\top}y\]然后我们令
\[H = \Phi(\Phi^{\top}\Phi)^{-1}\Phi^{\top}\]那么 \(H\) 和 \(I - H\) 是 projection matrix，并且 \(Hy \perp (I - H)y\)：
\[\begin{cases} H\Phi = \Phi \\ H^2 = H \\ (I - H)^2 = I - H \\ H^{\top} = H \\ (I - H)^{\top} = I - H \end{cases}\]误差分析的话，其实就考虑的是在那个 \(\Phi\) 的平面上，加上一个正态分布的 \(\epsilon\) 嘛。\(\Phi\) 这个平面是 \(M\) 维的，那么与之正交的那个东西，也就是 \(I - H\) 肯定是 \(N - M\) 维的。现在我们要求的是 \(\epsilon\) 投影在这个平面上的长度，那很显然是 \(N - M\) 个 \(\mathcal{N}(0, \sigma^2)\) 相加，也就是
\[\frac{1}{\sigma^2}(y - \hat{y})^{\top}(y - \hat{y}) \sim \chi^2_{N-M}\]所以说
\[\mathbb{E}\left[(y - \hat{y})^{\top}(y - \hat{y})\right] = \sigma^2(N - M)\]也就是
\[s^2 = \frac{1}{N-M}\sum_{i=1}^N(y_i - \hat{y}_i)^2\Longrightarrow\mathbb{E}[s^2] = \sigma^2\]ANOVA Table (\(A = \frac{1}{n}11^{\top}\))：
| Source | DF | Sum of Squares | Mean Square | \(\mathcal{F}\)-value |
|---|---|---|---|---|
| Regression | \(M - 1\) | \(\mathrm{SSR}=\sum_{i=1}^N(\overline{y}_i - \hat{y}_i)^2 = y^{\top}(H - A)y\) | \(\mathrm{MSR}=\frac{\mathrm{SSR}}{M-1}\) | \(F=\frac{\mathrm{MSR}}{s^2}\) |
| Residual | \(N - M\) | \(\mathrm{SSE}=\sum_{i=1}^N(y_i - \hat{y}_i)^2 = y^{\top}(I - H)y\) | \(s^2=\frac{\mathrm{SSE}}{N-M}\) | |
| Total | \(N - 1\) | \(\mathcal{S}_{yy}=\sum_{i=1}^N(\hat{y}_i - \overline{y}_i)^2 = y^{\top}(I - A)y\) |
考虑到 \(\mathrm{SSR}\) 和 \(\mathrm{SSE}\) 都是 \(\chi^2\) distribution，他们除一除的 \(F\) 就是一个 \(\mathcal{F}\) distribution 嘛。
所以说
\[F = \frac{\mathrm{MSR}}{s^2}\sim \mathcal{F}_{M - 1, N - M}\] \[\mathbb{E}[\mathcal{L}] = \mathbb{E}\left[\frac{1}{2}\left(f(x) - y\right)^2\right]\]然后一个很好玩但是经常被人忽略的话题是，假设我们已经预测出了（当然也可能是别的 distribution）
\[y \sim \mathcal{N}(\mu, \sigma^2)\]我们为啥会去预测 \(\hat{y}\leftarrow \mu\) 捏？
这其实可以去证明，在 MSE 作为 loss 的情况下，是最优的。我们需要用到一些泛函的技巧。就是我们假设有一个关于 \(f\) 的泛函 \(F\)。我们定义 calculus of variations \(\frac{\delta F}{\delta f}\)：
\[F(y(x) + \epsilon \eta(x)) = F(y(x)) + \int \frac{\delta F}{\delta y(x)}\eta(x)\mathrm{d}x + \mathcal{O}(\epsilon^2)\]那么对于 MSE：
\[\begin{aligned} \mathbb{E}[\mathcal{L}\left(f(x) + \epsilon\eta(x), y\right)] &=&& \mathbb{E}\left[\frac{1}{2}\left(f(x) + \epsilon\eta(x)- y\right)^2\right]\\ &=&&\iint \frac{1}{2}(f(x) + \epsilon\eta(x) - y)^2 p(x, y)\mathrm{d}x\mathrm{d}y\\ &=&&\iint\frac{1}{2}(f(x) - y)^2 p(x, y)\mathrm{d}x\mathrm{d}y\\&&& + \iint (f(x)-y)\cdot\epsilon\eta(x)\cdot p(x, y)\mathrm{d}x\mathrm{d}y + \mathcal{O}(\epsilon^2)\\ &=&&\mathbb{E}[\mathcal{L}\left(f(x), y\right)] + \epsilon \int\eta(x)\left(\int(f(x) - y)p(x, y)\mathrm{d}y\right)\mathrm{d}x+\mathcal{O}(\epsilon^2) \end{aligned}\]也就是说：
\[\frac{\delta\mathbb{E}\left[\mathcal{L}\right]}{\delta f(x)}=\int(f(x) - y)p(x, y)\mathrm{d}y = f(x)p(x)-\int yp(x, y)\mathrm{d}y\]考虑到我们最优化 \(\mathbb{E}[\mathcal{L}]\)，所以说
\[\frac{\delta\mathbb{E}[\mathcal{L}]}{\delta f^*(x)}=f^*(x)p(x) - \int yp(x, y)\mathrm{d}y = 0\]也就是
\[f^*(x)=\frac{1}{p(x)}\int yp(x, y)\mathrm{d}y=\int yp(y\mid x)\mathrm{d}y=\mathbb{E}[y\mid x]\]所以说咱们预测 \(\mathbb{E}[y\mid x]\) 是最优的。
所以说其实不同 \(\mathcal{L}\)，取的值其实是不一样的。这个其实很好理解嘛，就比如你前面有根柱子，可以往左走也可以往右走，但也不至于直接往中间撞上去。
就肯定是把类别先 1-of-\(K\) coding 一下，\(t=i\Rightarrow y = e_i\)。
那么
\[\hat{y} = \hat{W}^{\top} \tilde{x}\]其中 \(\tilde{x} = \begin{bmatrix}1&x^\top\end{bmatrix}^\top\)。