夏天的时候本来打算上手Scala。看了几节cousera上的函数式编程语言课后，觉 得很多地方都没讲透，节奏也很慢。Scala那么多语法糖看不见本质的感觉。所以 弃了。重拾SICP，打算秒掉所有的习题。几年前刷到第3章就没坚持下去。有人说 精彩的部分在第4和第5章。做习题的过程中，顺便弄明白了Y-combinator这么神 奇的东西，参考。lambda演算 寥寥几句就把程序语言就构造出来了，非常巧妙。

ESL的笔记和正文提及的习题。这章主要介绍了linear regression。

Linear Regression Models and Least Squares

$$f(X) = \beta_0 + \sum_{j=1}^pX_j\beta_j$$

$X$可以是quantitative；可以是quantitative的各种变换后的值，取对数，开方。取对数很常见；可以是基展开的；可以是 qualitative变量的coding；可以是多个变量的函数。

最常用的是以least square最小二乘作为优化函数。中文名最小二乘对我来说真是好陌生啊。我觉得在学术文章里是中英夹杂是 用来提高效率的。

$$\text{RSS}(\beta) = \sum_{i=1}^N(y_i - \beta_0 - \sum_{j=1}^px_{ij}\beta_j)$$

least square隐含假设是i.i.d. 把$\mathbf{X}$表示用全1的列向量扩展的观察数据矩阵，对上面的式子求导得到看到过无数遍的 closed form，面试的时候被问过。

$$\hat{\beta} = (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y}$$

对$\hat{\mathbf{y}}$的估计就是用下面的矩阵$\mathbf{H}$

$$\mathbf{H} = \mathbf{X}(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y}$$

直接乘以$\mathbf{y}$得到。所以这个矩阵$\mathbf{H}$也就hat，这个也叫投影矩阵。自己乘自己还是自己。 落园的笔记的还提到了一个消灭矩阵$\mathbf{I}-\mathbf{H}$，反正就是 为了计算误差方便的矩阵。

笔锋一转，几何乱入。把RSS用矩阵形式表达并且对$\mathbf{X}$按列分块。least square做的其实也是在由 $\mathbf{X}$的列向量张成的线性空间里找到一个$\mathbf{y}$的近似，使得残差最小。最优值也就是在残差向量垂直于 张成的线性空间的时候，也就是$\mathbf{y}$作投影的时候得到。

毕竟是频率学派，对$\hat{\beta}$的分析和假设检验出场。因为

$$\hat{\beta} = (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y} = (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T(\mathbf{X}\beta + \boldsymbol{\epsilon})$$

所以$\text{E}(\hat{\beta}) = \beta$。这里要注意的是$\boldsymbol{\epsilon}$是一个由$N$个不同的$\epsilon$组成的向量，每个$\epsilon$服从i.i.d分布。这里一直误以为是对每个元素求方差，其实ESL里面不区分方差Variance和协方差Covariance。这里Variance就是 Covariance。怪不得之前算方差的时候这么别扭，T.T。而且ESL里面不细分点乘和矩阵乘，要自行辨认哪个是标量哪个是点乘。 陈希孺的书中有几个有用的公式，用ESL的符号表示就是，其中$\mathbf{A}$是常数矩阵

$$\text{Var}\left[ \mathbf{A}X \right] = \mathbf{A} \text{Var} [ X ] \mathbf{A}^T$$

按照这个公式和$\text{Var}[\boldsymbol{\epsilon}] = \sigma^2 \mathbf{I}$，最终得到

$$\text{Var} [ \hat{\beta} ] = \text{E}\left[ (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T \sigma^2 \mathbf{I} \mathbf{X} (\mathbf{X}^T\mathbf{X})^{-1} \right] = (\mathbf{X}^T\mathbf{X})^{-1}\sigma^2$$

所以$\hat{\beta}$服从正态分布。

$$\hat{\beta} \sim N(\beta, (\mathbf{X}^T\mathbf{X})^{-1}\sigma^2)$$

以下结论和证明都可以在陈希孺的近代回归分析中找到。因为$\sigma^2$是未知的，要通过

$$\hat{\sigma}^2 = \frac{1}{N-p-1}\sum_{i=1}^N(y_i - \hat{y}_i)^2$$

来对$\sigma^2$无偏估计。这个证明匆匆看了下，关键是用到$\mathbf{X}^T\mathbf{X}$的秩最多$p+1$。另外

$$(N-p-1)\hat{\sigma}^2 \sim \sigma^2\chi_{N-P-1}^2$$

这个证明关键是把RSS表示成二次型$\text{RSS} = \mathbf{y}(\mathbf{I} - \mathbf{X}(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T)\mathbf{y}$，和多个正态分布相加的形式。还有

$$z_j = \frac{\hat{\beta}_j}{\hat{\sigma}^2\sqrt{v_j}} \sim t_{N-p-1}$$

这个本身就是$t$分布的定义，具体的概率密度函数pdf是后来推导出来的，巨复杂。第1和第2个证明还好。当样本数量 足够大的时候$z_j$近似服从正态分布了。有了这个分布之后，我们就可以做假设检验看某个随机变量是否显著。也可以用 F分布对一个随机变量的集合做假设检验。这里还是就记一个结论吧。线性回归在统计里水应该还是蛮深的，可以讲一本书。和陈希孺的 近代线性回归和Seber的线性回归分析书比较，ESL算讲得少了，但还算比较深刻。MLAPP第7章只有几个公式，没有多少篇幅 具体讨论。比如没有QR分解和施密特正交化的关系。

高斯-马尔科夫定理 GM Theorem

证明见后文。least square是所有无偏估计中方差最小的。但是learning的最终问题是泛化误差或者叫做预测误差。任何一本 Machine Learning书中都会说到泛化误差可以分为噪声的方差 + bias^2 + variance。所以有的估计稍微提高一点bias但是 可以大幅降低variance，得到更好的泛化误差。最近的ICML有对MCMC的改进也是这个思路。

Multiple Regression from Simple Univariate Regression

这又是一个新的观点从中引出了QR分解和后面的特征选择。这个idea是，如果$\mathbf{X}$的每一列都是互相正交的话，那么 least square linear regression做起来非常简单，就是$<\mathbf{x}_j, \mathbf{y}>/<\mathbf{x}_j, \mathbf{x}_j>$。 所以只要对$\mathbf{X}$的列向量正交化就好了。单变量回归对于有截距intercept怎么办呢？从中推导出的公式相当于 $\beta_0$等于$\bar{\mathbf{x}}$，再把$\mathbf{x}$在前面的残差向量$\mathbf{z}$做regression。

那么一般形式就是在用全1向量扩展的$\mathbf{X}$上做schmidt正交化过程。正交化的结果就是一个正交矩阵和一个上三角矩阵。

$$\mathbf{X} = \mathbf{Z}\boldsymbol{\Gamma} = \mathbf{Q}\mathbf{R}$$

在标准化一下就是QR分解。用标准正交矩阵性质带入公式，得到

$$\mathbf{R}\hat{\beta} = \mathbf{Q}^T\mathbf{y}$$

这个线性方程组很容易算，back substitution。

Subset Selection

这里所有的特征选择是两步走的，先把一个feature选进来，拟合一下看一下好不好，不好下一个。Best-Subset Selection，Forward， Backward-stepwise，Forward-Stagewise。

Shrinkage Methods

Ridge regression就是加了一种bias。

$$\min \left\{ \sum_{i=1}^N (y_i - \beta_0 - \sum_{j=1}^p x_{ij} \beta_j)^2 + \lambda \sum_{j=1}^p \beta_j^2 \right\}$$

这种优化在Convex Optimization一书中叫做Scalarization。最优点叫做Pareto optimal。注意这里没有$\beta_0$的惩罚项。因为我们 可以把$\mathbf{Y}$都加上或处以某个相同的数，那么回归得到的系数除$\beta_0$以外应该不变才对。如果加上了$\beta_0$的惩罚 之后，其他系数就没有这种不变性了。

书中提到直接优化目标函数可以分为两步走。第一步把$\mathbf{X}$去中心化，$\beta_0=\bar{y}$。第二部用没有intercept的 ridge regression。这也是练习3.5，证明见后文。

解析解也是看了无数遍的

$$\hat{\beta} = (\mathbf{X}^T\mathbf{X} + \lambda \mathbf{I})^{-1}\mathbf{X}^T\mathbf{y}$$

还有可以联系贝叶斯后验概率。SVD分解又提供了另外一个角度。

$$\mathbf{X}\hat{\beta} = \mathbf{U}\mathbf{U}^T\mathbf{y}$$

变成了

$$\mathbf{X}\hat{\beta} = \sum_{j=1}^p \mathbf{u}_j\frac{d_j^2}{d_j^2 + \lambda}\mathbf{u}_j^T\mathbf{y}$$

ridge regression就是把$\mathbf{u}$缩放了一下。这种缩放有什么好处呢？联系PCA。

如果$d_j$比较小的话，

练习

习题3.3

$\hat{\beta}$的期望就是$\beta$。书中的 期望对$\beta$还乘了个向量$a$。之前都是自己死推无比繁琐。有了上面的方差 公式就方便多了，落园博客上的证明就冗长了。之于为什么要乘以一个向量，我 估计是因为最终比较的方差的大小。如果不乘的话，比较的是两个协方差矩阵， 怎么比么。写博客的一个好处是以前推导中疏忽的地方会纠正过来。这个是书中 习题。这里$\mathbf{c}$和$\mathbf{y}$粗体的原因是因为有$N$个元素。 因为$\text{E}[\mathbf{c}^T\mathbf{y}] = a^T\beta$，则把$\mathbf{y}$代换掉， 得到$a = \mathbf{X}^T\mathbf{c}$。

$$\text{Var}[\mathbf{c}^T\mathbf{y}] = \sigma^2 \mathbf{c}^T \mathbf{c} \label{first}$$

以及

$$\text{Var}[a^T\hat{\beta}] = \sigma^2 \mathbf{c}^T \mathbf{X} (\mathbf{X}^T\mathbf{X})^{-1} \mathbf{X}^T\mathbf{c} \label{second}$$

所以只要证明第一个式子的二次型中的矩阵$\mathbf{I}$减去第二个式子的是半正定的就好了。用SVD分解$\mathbf{X}$。

$\mathbf{X} (\mathbf{X}^T\mathbf{X})^{-1} \mathbf{X}^T = \mathbf{U}\Gamma\mathbf{U}^T$。

其中$\mathbf{U}$是$N \times N$的矩阵。那么$\mathbf{I} - \mathbf{U}\Gamma\mathbf{U}^T$必然是半正定的，因为 用$\Gamma$只有左上角的那个小块矩阵是单位矩阵。

习题3.5

网上有些习题是把书中公式3.41的$x_{ij}$变成$x_{ij} - \bar{x}_j + \bar{x}_j$，然后比较

$$\arg \min \left\{\sum_{i=1}^N [ y_i - \beta_0^c - \sum_{j=1}^p(x_{ij} - \bar{x}_j)\beta_j^c ]^2 + \lambda \sum_{j=1}^p {\beta_j^c}^2\right\}$$

得到$\hat{\beta}^c_0 = \hat{\beta}_0 - \sum^{p}_{j=1} \bar{x}_j\hat{\beta}_j$。

我觉得这里很有问题。因为一般用这种比较方法的时候都是两个公式是恒等式。而这里是求最小值。如果在从上面得到第二个式子做最小值的时候，必须考虑 $\hat{\beta}_0^c$ 和其他$\hat{\beta}_j^c$之间的约束$\hat{\beta}_0^c = \hat{\beta}_0 - \sum_{j=1}^p\bar{x}_j\hat{\beta}_j$。所以这里导出的第二个优化函数多了一个约束。如果得到了$\hat{\beta}^c$之后还要验证转换得到的 $\hat{\beta}$是否是使得原优化最小。

我的做法是两个优化公式直接求$\beta$和$\beta^c$然后比较是否相等，虽然麻烦了点。引入一个叫做centering matrix

$$\mathbf{C} = \mathbf{I} - \frac{1}{n}\mathbf{1}\mathbf{1}^T$$

左乘这个矩阵相当于做中心化。$\mathbf{C}$是对称的。性质有$\mathbf{1}^T\mathbf{C} = \mathbf{0}^T$， $\mathbf{C}^T\mathbf{C} = \mathbf{C}$。做1遍以上去中心化就相当于只做了1遍。

令$\beta = [\beta_0, \tilde{\beta}]$，其中$\tilde{\beta}$是$\beta$从1到p的向量。 去中心化后的优化函数写成矩阵的形式是

$$\min \|\mathbf{y} - [\mathbf{1}, \mathbf{C}\mathbf{X}]\beta^c \|_2^2 + \| \tilde{\beta}^c \|_2^2$$

导数等于0。用分块矩阵写出来是

$$\begin{bmatrix} \mathbf{1}^T\mathbf{y} \\ \mathbf{X}^T\mathbf{C}^T\mathbf{y} \end{bmatrix} = \begin{bmatrix} n & \mathbf{1}^T\mathbf{C}\mathbf{X} \\ \mathbf{X}^T\mathbf{C}^T\mathbf{1} & \mathbf{X}^T\mathbf{C}^T\mathbf{C}\mathbf{X} + \mathbf{I} \end{bmatrix} \begin{bmatrix} \beta^c_0 \\ \tilde{\beta}^c \end{bmatrix}$$

把$\tilde{\beta}^c$提出来之后得到

$$\mathbf{X}^T\mathbf{C}^T\mathbf{y} = (\mathbf{X}^T\mathbf{C}\mathbf{X} +\mathbf{I})\tilde{\beta}^c$$

另外一方面，原始的优化函数写成矩阵形式并求导等于0之后

$$\begin{bmatrix} \mathbf{1}^T\mathbf{y} \\ \mathbf{X}^T\mathbf{y} \end{bmatrix} = \begin{bmatrix} n & \mathbf{1}^T\mathbf{X} \\ \mathbf{X}^T\mathbf{1} & \mathbf{X^T}\mathbf{X} \end{bmatrix} \begin{bmatrix} \beta_0 \\ \tilde{\beta} \end{bmatrix}$$

解个2元一次方程组。把下面

$$\beta_0 = \frac{1}{n}\left[\mathbf{1}^T\mathbf{y} - \mathbf{1}^T\mathbf{X}\tilde{\beta}\right]$$

代入

$$\mathbf{X}^T\mathbf{1}\beta_0 + (\mathbf{X}^T\mathbf{X} + \mathbf{I})\tilde{\beta} = \mathbf{X}^T\mathbf{y}$$

整理并用$\mathbf{C}$的定义，$\tilde{\beta}$就得到了同$\tilde{\beta}^c$一样的样子了。

所以这道题无非说的是，最小二乘线性回归其实可以理解成，先做了去中心化，得到$\beta_0$，把他从$\mathbf{y}$里减掉， 剩下的是在做无截距的最小二乘。这样公式3.43中的$\beta$可以写的没联系中的那么别扭了。MLAPP第226页也有但是没提这一点 可能读到的时候会觉得奇怪吧。

习题3.8

有了练习3.5，3.8非常相似，简单得证。 故事说的是

简介

Bottou在Stochastic Gradient Descent和对Neural Network中的优化很有建树。 他早先是Lecun的同事，现在在Microsoft做研究。最近读了他的报告Stochastic Gradient Descent Tricks。这个报告其实是一本Neutral Networks Tricks of the Trade一本书的一章。这本书有电子版。Amazon上的一则评论说因为有不同的 人写的，所以有些对立观点。

SGD在大数据和NN优化Toolbox上乃是“装机必备”，比如PyLearn2, Caffe, Torch， CXXNet。传说NN优化太多trick，只有在Lecun周围方圆百里的人才懂得如何调参。

引用

Léon Bottou: Stochastic Gradient Tricks, Neural Networks, Tricks of the Trade, Reloaded, 430–445, Edited by Grégoire Montavon, Genevieve B. Orr and Klaus-Robert Müller, Lecture Notes in Computer Science (LNCS 7700), Springer, 2012.

公式

SGD 迭代公式非常简单。一般的Gradeint Descent的迭代式是，详见Convex Optimization等书。 $w_{t+1} = w_t - \gamma \nabla f(w_t)$ 因为Machine Learning的问题基本都是在训练集上求loss function的最小值。于是这里的梯度就是 N个训练样本上的梯度。

$$w_{t+1} = w_t - \gamma \sum_{i=1}^N \nabla f(x_i, w_t)$$

GD迭代一次使用全部训练集的梯度，SGD只使用一个训练样本的梯度而已。 $w_{t+1} = w_t - \gamma \nabla f(x_i, w_t)$

文中列举了Linear regression，Perceptron，K-Means，SVM，Lasso等SGD迭代公式。

文中的一个误差公式有点意思。说的是误差是由1. Approximation Error近似 误差，Estimation Error估计误差和Optimization Error优化误差组成。这和 统计学习理论LFD一书中不大一样。这里取的期望应该是所有数据空间的。统计 学习理论的用样本误差加上一个以VC维和样本数量的函数作为推广误差界的。 推广误差界应该对应的是第一项近似误差。

为什么SGD而不是以前经典的GD被大量运用于现在的优化问题，我的理解是一方 面因为现在数据量太大放不进内存。另外一个理解以前的算法都以达到 预定accuracy的迭代次数为标准。比如GD是线性收敛，即以等比级数收敛，大概需要$\log(1/\rho)$的迭代次数。 但是把每次迭代的遍历数据的个数也考虑进去的话情况就不一样了。文中说明了SGD要比GD都要快的原因。

这里有个地方我不是很明白。$\mathcal{E} = \mathcal{E}_{\text{app}} + \mathcal{E}_{\text{est}} + \mathcal{E}_{\text{opt}}$ 收敛的速度是这个三项里面最慢的一项决定的。可是第一项一旦hypothesis确定了，怎么还能在优化的时候减少呢？可能要看看是 另外NIPS的文章。

在一些convex假设下$\mathcal{E}_{\text{est}}$大概以$(\log (n) / n)^{\alpha} $收敛。如果$n$趋向于无穷大我们有无限多的数据那么这个误差确 实趋向于0。又因为我上面没看懂的原因，这三个误差收敛速度一样。因为 $\rho$差不多等于上面这个收敛速度。于是得到了$n$与$\epsilon$的关系。但是 这个是$n$是关于$\epsilon$的超越函数所以要用脚注2的公式近似一下。

$$\epsilon^{\frac{1}{\alpha}} \sim \frac{\log n}{n}$$

得到$\log n \sim \frac{1}{\alpha}\log \frac{1}{\epsilon}$再代入到原来的公式中得到

$$n \sim \epsilon^{-1/\alpha}\log(1/\epsilon)$$

意思是说达到$\epsilon$这样 的误差需要多少样本，代入到表格2中的第3行就得到了GD需要 $\frac{1}{\mathcal{E}^{1/\alpha}} \log^2 \frac{1}{\mathcal{E}}$这样的时 间。而SGD因为每次迭代都只要一个数据，所以还是$\frac{1}{\mathcal{E}}$。

Tricks

• Randomly shuffle
• User preconditioning techniques 需要看书1.4.3和1.5.3
• Monitor both the training cost and the validation error
• check the gradients using finite differences

• Experiment with the learning rates using a small sample of the training set

• Linear Models with $L_2$ regularization

$$w_{t+1} = (1-\gamma_t\lambda) w_t - \gamma_ty_tx_t\ell^\prime(y_tw_tx_t)$$

如果$x_t$很sparse的话，那么很多$w_t$的元素都只是在乘以一个数缩放而已，偶尔要相加第二项的数。如果大多数元素都需要做 每次迭代都要做差不多的缩放的话，不如把这些缩放都连乘，存在一个$s_{t+1}$这个变量里。这样就假设$w_t = s_tW_t$，带入上面的公式， 得到了$g_t, s_{t+1}, W_{t+1}$三个公式，尽管多了一个除法。

下面一个trick

$$\gamma_t = \gamma_0(1+\gamma_0\lambda t)^{-1}$$

这里的$\lambda$用的是regularization项前面的$\lambda$系数。

• ASGD把前面的迭代得到$w_t$都累加起来。这种累加可以写成迭代的形式，再考虑到$x$是sparse的情况。考虑到$w_t = s_tW_t$，而 $\bar{w}_t$要把自己的缩放给放在一个变量里，对$W_t$的缩放放在另外的变量里，恰好这两个变量的缩放 有一个公共的部分$\beta_t$所以就变成$(A_t + \alpha_t W_t ) / \beta_t$了，具体还要看看Wei Xu的paper。

ESL的笔记和正文提及的习题。这章主要介绍了supervised learning的基本概念和以后各章的摘要。

术语

在一个learning过程中涉及到的概念有inputs和outputs。inputs又叫做 predictors，independent variables，features。outputs又叫做responses， dependent variables。

根据变量是quantitative还是qualitative来区分learning是regression还是 classification。还有第3种变量ordered categorical，例如small，medium， large之类的。quantitative变量当然用实数表示。qualitative变量可以用 one-hot coding表示。

ESL比较好的一点是对用到的数学符号有准确的定义，而不像一些machine learning的paper，实数和随机变量符号不分。有时候会让人看不懂。输入随机变 量用大写斜体$X$表示。如果$X$是向量，其中第j个元素用$X_j$表示。 qualitative变量$G$。第i个$X$的观测值不论是$X$是标量还是向量，都用 小写的$x_i$表示。N个观测值的一个集合用大写粗体的$\mathbf{X}$。向量 一般不粗体。有时候为了表示第$j$随机变量的N个观测值，也就是矩阵$X$的一 列的时候才会粗体$\mathbf{x}_j$。矩阵的一行也就是第$i$个随机变量观测值 $x_i^T$。

LS和kNN

最简单的learning方法是least model和kNN。传说很多方法都是从这两个货改过来的。

$$\hat{Y} = X^T\hat{\beta}$$

估计$Y$值。 $\hat{Y}$可以是变量也可以是向量。用

$$\text{RSS}(\beta) = (\mathbf{y} - \mathbf{X}\beta)^T(\mathbf{y} - \mathbf{X}\beta)$$

作为loss function去求$\hat{\beta}$。

$$\hat{\beta} = (\mathbf{X}^T\mathbf{X})^{-1}X^T\mathbf{y}$$

linear model用在classification问题上，就以$0.5$为界。

kNN的用

$$\hat{Y}(x) = \frac{1}{k}\sum_{x_i \in N_k(x)} y_i$$

来估计$Y$值。看上去KNN只有一个参数$k$其实不然。因为kNN估计的是一个 neighborhood的里数据的mean，有多少个neighborhood就有多少个参数 $\frac{N}{k}$。kNN的有效参数个数一般都大于linear model的参数个数$p$。这 也印证了后面的bias-variance分解的结论：linear model是high bias，low variance；kNN是low bias，high variance。

Statistical Decision Theory

Statistical Learning Theory给出了一个学习框架。linear model和kNN可以自 然的从中推出。Learning from Data一书对这部分内容有非常通俗易懂的解释。 用统计学习理论回答了几个问题。什么是学习（learning）。机器能学习么？如 何学习？如何学得好。涉及了VC维，如何用Traing误差估计泛化误差，Cross Validation是如何影响估计的和trade-off。Foundations of Machine Learning 一书主要也是讲这个更加理论话一点。LFD研究最简单的二分类问题，loss function也是最理想的分类损失函数。重要结论有

$$\mathbb{P}[| \text{E}_{\text{in}}(g) - \text{E}_{\text{out}}(g)| > \epsilon] \le 4 m_{\mathcal{H}}(2N)e^{-\frac{1}{8}\epsilon^2N}$$

简单点

$$E_{\text{out}} \le E_{\text{in}} + \Omega$$

意思是说in-sample和 out-sample的误差也就是泛化误差不会超过一个由VC维，数据量$N$和误差 $\epsilon$决定的界。看上去很美，其实大部分理论界都尼玛太松了，实际用 来估计误差大误。所以LFD最后介绍了Cross Validation并重新估计了泛化误差。 里面有对Validation的数据量的trade-off。ESL和LFD都有Bias-Variance分解内 容大同小异。Machine Learning From A Probabilistic Perspective也不错。公 式细节都很详细，就是钻研MLAPP容易陷入细枝末节，insights没有ESL那么多。 外功MLAPP，内功LFD和ESL。

ESL定义EPE。奇怪为啥ESL不把EPE的全称写出来，多年以前看的时候一直很纠结。 EPE叫expected prediction error。EPE需要一个loss function，$L(Y,f(X))$。 EPE可以用各种loss function，squared error loss，logistic loss，hinge loss。Tong Zhang有一篇paper对各种loss近似分类误差的分析。

如果用squared error loss，

$$\text{EPE}(f) = \text{E}(Y-f(X))^2 = \int \left[y-f(x)\right]^2 \text{Pr}(dx, dy)$$

用条件概率公式

$$\text{EPE}(f) = \text{E}_X\text{E}_{Y|X}\left(\left|Y-f(X)\right|^2|X\right)$$

得

$$f(x) = \text{E}(Y|X=x)$$

kNN的近似

$$\hat{f}(x) = \text{Ave}(y_i | x_i \in N_k(x))$$

对这个做了两个近似，一是用平均取代期望，二是用领域取代了X，来近似Y和X的条件概率。 当$N$和$k$趋向于无穷大，$k/N$趋向于$0$。kNN的$\hat{f}$就逼近了用期望的$f(x)$。

linear regression也做了近似。一是用全局的线性函数近似$f(X)$，EPE得到

$$\beta = \left[ \text{E}\left(XX^T\right)\right]^{-1}\text{E}\left(XY\right)$$

linear regression的近似

$$\beta = \left[ \left(\mathbf{X}^T\mathbf{X}\right)\right]^{-1}\mathbf{X}^T\mathbf{y}$$

看到不同了没有？一个是随机变量一个是数据观测值。一个是求期望一个是求平均。可能很难看出哪里求了平均。 如果$X$只是一个随机变量的话，那么EPE是$\text{E}(X^2)$，linear regression是$N \times 1$大小的 观测值向量$x^Tx$。所以这里的转置符号稍微有点区别。

这里为啥squared loss会联系到kNN和linear regression？后面会讲因为隐式假定了数据的的高斯分布。 如果用绝对值的loss，kNN得到中值median。

分类问题稍微有点区别。EPE要对每一个$G$的取值要逐个考虑。

$$\text{EPE} = \text{E}\left[ L(G, \hat{G}(X))\right]$$

用条件概率公式

$$\text{EPE} = \text{E}_X\sum_{k=1}^K L \left[ L(\mathcal{G}_k, \hat{G}(X))\right]\text{Pr}\left(\mathcal{G}_k|X\right)$$

用0-1 loss function得到 $\hat{G}(x) = \arg \min_{g\in\mathcal{G}}\left[ 1- \text{Pr}\left( g|X=x\right)\right]$ 这个选最大概率的类来作为估计的分类器叫Bayes classifier。Bayes classifier的误差叫做Bayes rate。

kNN用majority vote近似Bayes rate。Pattern Classification一书中有证明。 kNN的误差最多是Bayes rate误差的两倍。忘记咋证的了。dummy-variable的 linear regression也可以Bayes classifier。

维数灾难

如果一个单位球是高维的，那么球的“质量”绝大多数分布在球最外层的壳上。这个时候要是在想取原点的最近邻的话就 差不多要跑到球表面上去了。

Bias和Variance在不同的情况下对总的error贡献是不同的。以kNN为例。在对称函数的$f$中搞kNN，随着维数的增加， bias增加，因为近邻会越来越趋向于1或者-1，函数值都趋近于0。但是因为对称的，variance不怎么增加， 基本上都是0左右。而另外一个用指数函数做的kNN，bias不怎么增加。因为最近邻随着维数的增加趋向于两端， 但是函数值是一大一小基本抵消。variance增加不少，因为有时候最近邻函数值很大（趋向于1），有时候很小（趋向于-1）。

以linear model为例子。

$$\begin{align} \text{EPE}(x_0) &= \text{Var}(y_0|x_0) + \text{Var}_{\mathcal{T}}(\hat{y}_0) + \text{Bias}^2(\hat{y}_0) \\ &= \sigma^2 + E_{\mathcal{T}}x_0^T\left(X^TX \right)^{-1}x_0\sigma^2 + 0^2 \end{align}$$

这个公式在其他书中都有。trick无非是加一项减一项 $\text{E}_{\mathcal{T}}\hat{y}_0$。当$N$趋向于无穷大，$\text{E}(X) = 0$ 的时候，用trace trick就$\text{trace}(x^TAx) = \text{trace}(Axx^T)$得到简化公式$\sigma^2(p/N)+\sigma^2$。

Statistical Models

additive model假设那些$Y$偏离$f(X)$的部分都可以用独立同分布的$\epsilon$表示。这也是quantitative变量的 EPE中使用squared errors的原因。但是在qualitative变量中一般就不大可行。因为$Pr(G|X)$是条件概率。

learning问题也可以看做是函数近似。通常是在一个以 $\theta$为参数的函数family里面找出一个能最好的近似数据。 least squares其实是最大似然估计maximum likelihood estimation下用高斯假设的特例。

$$L(\theta) = \sum_{i=1}^N \log \text{Pr}_\theta(y_i)$$

其中 $Pr (Y|X,\theta) = N(f_{\theta} (X), \sigma^2)$。

如果把最大似然估计用在qualitative变量做分类上，

$$L(\theta) = \sum_{i=1}^N \log p_{g_i,\theta}(x_i)$$

就得到了cross-entropy。如果对每一类的数据假设高斯分布的话，就是logistic regression了。所以logistic regression 也可以从Linear discriminant analysis推导出来。LDA假设数据是同Covariance的高斯分布， 用generative的方法，先写出高斯分布$P(X|Y)$，再用贝叶斯公式写出 $P(Y|X)$ ，MLAPP Page 102，假设同$\Sigma$。 其实就相当于直接假设$P(Y|X)$是sigmoid函数。

Structured Regression Models

单单用RSS作为选择函数$f$的标准是不够的，因为所有使得在已知数据点上的误差为0的函数都使得RSS为0。所以要在一个比较小 函数集合内找RSS。这类方法叫做complexity restriction。大多数方法是在input的邻域上有一些简单的结构，smooth啦，liear啦， 多项式啦。成功的算法大多如此。对于高维问题，也有巧妙的metric的定义。

Restrictions

对RSS增加一项smooth惩罚项$\int[f^{\prime\prime}(x)]$。projection pursuit regression也是在寻找参数的时候避免使得函数不smooth。

Kernel方法对一个邻域里的数据点赋予权重。这里对用kernel的RSS有了一个统一的解释。

$$\text{RSS}(f_\theta, x_0) = \sum_{i=1}^N K_\lambda(x_0, x_i)(y_i, f_\theta(x_i))^2$$

这里不像上面的RSS，这里的RSS还有个参数 $x_0$，所以基本的kernel methods像kNN一样特别得“local”。书中给出了两个特例。

Basis functions是用了一个基函数的集合。Neural Networks属于这一类。

Model Selection和Bias-Variance trade-off

kNN regression的bias-variance分解。kNN regression的函数

$$\hat{f}_k(x_0) = \frac{1}{k}\sum_{l=1}^k(f(x_l) + \epsilon_l)$$

Bias非常直接。算Variance的时候要注意每一个$ x_l $都有不同的 $ \epsilon_l $。

$$\text{Var}_{\mathcal{T}}\left( \hat{f}_k(x_0)\right) = \text{E}\left[ (\frac{1}{k}\sum_{l=1}^k \epsilon_l )^2\right]$$

接下去因为$\epsilon_l$是独立同分布的。所以只有每个$\epsilon_l$的方差留了下来。最终得到书中的结果。 Bias和Variance之间的trade-off说的是model complexity的增加Bias减少了，Variance增加了。

练习

习题2.3

求从原点到最近邻的距离的中位数的公式。

$$d(p, N) = \left( 1 - \frac{1}{2}^{1/N}\right)^{1/p}$$

因为数据点是均匀分布在$p$维单位球里。若原点的最近邻到原点的距离 $X$也是一个随机变量。那么其他所有的点都要落在$X$之外。 所以

$$P(X = x) = (1 - x^p)^N$$

根据median的定义$P(X\le m) \ge 0.5$, $P(X \ge m) \ge 0.5$。令上式右边等于0.5，解出 $x$就得到书中的公式了。

其他笔记

• demonstrate的笔记
• 落园的笔记