ESL学习笔记-Ch2

统计学习 ESL 笔记

---

Ch2 - Overview of Supervised Learning

---

本文是结合《ESL》与《Statistical Learning》课程两部分内容做的笔记。

Prediction & Regression

Use input to predict the output.

术语、分类

因变量（dependent variable, responses）一般有2种类型：

• Quantitive, 定量的一般预测是回归问题;

• Qualitative, 定性的一般是分类问题， 但是在定性的问题中，也有一种Ordered Category，比如Great, Good, Bad, Terrible这些有顺序的类型，可以编码用数值标量来表示。

例如哑变量（Dummy Variable），即一个向量，一个Instance只能有一个分量不为0，$x=[1,0,0,0]$表示Great，而$x=[0,0,0,1]^T$表示Terrible.

或者我们将Ordered Category量化，例如$Y\in[0,1]$，然后将$[0,0.5]$划分为一个区间，将$[0.5,1]$划分为一个区间。对于K个Category的也可以这么做。

其实就是随便搞，只要能有等价变换的关系，以及解释的通就行。

Example

Example, Sales Campaign

TV ads, radio ads, Newspaper ads influence Sales (or jointly together)，我们想知道哪些因素影响了Sales，或者他们联合一起影响的sales，可以建这样一个模型：

$$y \approx f(ads_{TV}, ads_{radio}, ads_{newspaper})$$

这样的模型中，我们可以不进看到单独因素对$y$ (Sales)的影响，也能看到他们的联合影响。

What is a good f(x)?

good f(X), predict well

we have a lot of data when x = 4, how to esitmate f(4)?
average value $f(4) = E(Y|X=4)$

$f(x) = E(Y|X=x)$ is called the Regression function

But in my view, $E(Y|X)$ is just a method, and we can import more to estimate it. 是的，但$E(Y|X)$是一个比较直观的想法(后文会有理论推导，证明是在平方误差下的最优估计)。如果我们能从数据中估计出$X=4$时的分布，那么就能做更多的事情了。

Define a loss function:
good predictor: minimize the loss function:$E[(Y-g(X))^2|X=x]$

真实模型就是有误差的：$Y=f(x) + \epsilon$, 也就是说会有一个irreducible error ，可见如下公式：

$$E[(Y-g(X))^2|X=x] = \underbrace{[f(x)-\hat{f}(x)]^2}_{reducible} + \underbrace{ Var(\epsilon) }_{irreducible}$$

这意味着，无论怎么预测，即使模型是非常准确的，方差也是不为0的，因此称作Irreducible Error，我们要尽可能的minimize loss function，就只能更好的估计$\hat{f}(x)$以靠近真实的$f(x)$

How to estimate f

in our dataset, 在x=4时，可能根本没有值，那怎么estimate

$$\hat f(x) = Ave(Y|X\in N(x))$$
用邻居的值来估计，也是一个不错的方法，但当维数增加时，这个方法并不是很好用了。

p is the variable number, N is the data
small p is good for NN method
future: Kernel, spline smoothing

why NN method can be losy when p is large
高维中，要capture同样比例的数据（足够的数据），太远了

Q1. 为什么要capture同样比例的数据，而不是capture同样个数，因为当dimension升高时，同样比例的数据会急剧升高，但是个数不会
A1: 个人认为，高维空间中，整个空间过大，如果能很好的覆盖整个空间，那么需要非常巨大的数据。那么从另一个角度看，如果你想估计这个值，那么就需要很多的周边的数据.

例如，最开始时我们只有2维，有20个数据，那么足够估计某个点的值了；但是假设我们的空间升到了100维，20个数据显然不能估计得了，因为20个数据根本连维数都没达到(有一些维度很可能一直都是0)，这样的估计显然很难。这是在100维空间都是独立的情况下的，如果100维空间是个图像，那么可能就很有相关关系，就可以采用一些降维的方法提取出一些主要的维度。

Parametric and Structured models

定好结构，然后再估计参数，比直接估计值强得多
结构反映了其关系特性，泛化能力就是在结构中蕴含的

linear model is the simplest parametric model

$$y=\beta_0 + \beta_1X + \cdots + \beta_pX_p = X^T\beta=(1,x_1,x_2,\cdots,x_p)(\beta_0,\beta_1,\cdots,\beta_p)^T$$

Obviously, Linear is not always right, but it's a good and interpritive model

线性模型的含义

1. 某个$X_n$的变化量，对于结果$y$的变化量是成正比的，这个在很多情况下并不成立，可能最开始影响的多，后面就影响的少了，例如购买数量和投放的广告数目，最开始投放广告多，购买数量正比上升，但是当投放的过多了，可能就饱和了，也可能人们由于厌倦而不会购买，从而导致了下降。

2. 我们从式子中发现，各个$X$是相互独立的，当某个分量的变化不会影响其他分量对$y$的贡献。
   但是，实际上并不是这样，一般来说很多分量之间是相互耦合的，一个分量取值发生了变化，另一个分量对结果的贡献就不同。举个例子，预测是否可能购买某件商品，我们的特征有：年龄和收入，当年龄处于中青年时，收入对是否购买其关键性作用，但是年龄处于儿童阶段时，其收入的影响(额，实际上也没啥收入，这里字不是很恰当)就对其微乎其微了。

线性模型可以看成是一个线性超平面，例如$X=(x_1,x_2)^T$，预测模型$Y=X^T\beta$，然后我们得到的是一个在三维空间中的平面，即任何一个方向上的变动对y的值的贡献都是线性的；而且，由于是线性边界，因此两个分量之间是不相互耦合的.

而非线性估计一种平滑的曲面，Ch7会讲如何调参数;

Parametered Structured Model & Nearest-Neighboor Model

Structured Model

参数化的有结构模型的好处是，我们知道了他的结构模型，只要将其系数（参数）求出来，就可以整个模型，而这一步很显然我们可以将其转化为优化问题，例如上文的

$$E[(Y-g(X))^2|X=x]$$

但是这个loss function其实考虑的全局的因素，也就是说，将所有数据点全部放在一起，然后考虑得到一个trade-off的解，但是在这个过程中如果有离群点之类的，就会大大的增加误差，从而使得求出来的解偏离真实的模型。这里将所有数据点全部考虑在一起，同等对待，所有的都归结到一个优化目标函数，最后求解，其实忽略了一些局部的信息.

K-Nearest-Neighboor Model

k-NN模型（Nearest-Neighboor Model）就是另一个视角的方法，其仅仅考虑了周边的局部信息，没有一个Model，没有参数化，仅仅是将空间离散掉，然后对于每一个进行求解，这样可以克服掉离群点的问题。

但是这里面也有一个需要调的参数：k，即取临近的k个的个数，如果过于少的话，例如k=1，会分的非常精细，一些其他类的点就会自己周围形成一个“小圈”，作为局部的小类，但实际上那个地方只是由于噪声作用过去了而已。在上文的$E[(Y-g(X))^2|X=x]$这个指标中，可以让其为0。

在K=1情况下，一些离群点在空间中分出来的其实就是传说中的Voronoi diagram[1]，即空间中的某个位置的取值是周边的最近的那个的取值，由各种点对之间的中垂线构成 ，如图所示，但是这样的话分的太细，会出现过拟合（我们也知道模型本身就是有噪声（误差）的，不可能为0），这样会把误差也分进去，所以不能以这个为指标进行k的评判选取。

可以想象当K减小时（从最大N降到1），也就是1/K增大时（最大为1，即K=1），按照我们之前的最小二乘的误差准则来评判我们的效果应该是越来越好的，即分的越来越细。但在训练集中误差不断减小，测试集中就不是这样了。即，为了修正过拟合和欠拟合的现象，选取恰当的k，应该在训练集-测试集两个集合上同时考虑。

Trade-offs

interpretability (linear or non-linear, high dimension)
Over-fit VS under-fit
parsimony VS black-box

Interpretability - Flexibility(自由度) plot (Interpretability↓, Flexibility↑)
1 Subset Selection Lasso
2 Least Squares
3 Generalized Additive Models Trees
4 Bagging, Boosting
5 SVM
6 ...

---

Statistical Decision Theory

---

Model Selection and Bias-Variance Tradeoff

A way of assessing model accuracy

how to select these models ?

当Flexibility上升，训练集误差下降，但测试集先下降再上升。

训练集下降很容易理解，测试集前面下降是由于模型逐渐精确(如何定义精确？是覆盖到了大多数的数据，而且还能泛化出来?——泛化指在训练集上好使，测试机上也好使)，后面上升是由于Overfitting。（感觉我需要一个基于训练集和测试集关系的理论去认识他们）

精确：自由度不够时，必然会有一些值不准确，就像拿线性去拟合二次型一样；当自由度上升时，就一定准确吗？如果原模型就是拿$x,x^2,x^3,\cdots$生成的，那么显然可以是自由度够了，就非常准确（准确的能训练出和原模型一模一样的参数？），但是如果原模型不是，那么这个最小值的Flexibility又是指什么？

要选一个测试集达到最小值的点作为我们的模型（但是测试集的选取也要有学问的吧）。

另外，即使模型非常完美，那么也会有一个irreducible error在那里，那个是$Var(\epsilon)$，所有拟合的模型的误差（测试集）都不会超越他，即不会无限下降。

Bias-Variance Trade-off

把Reducible-Error再分解一下，

$$E(y_0 - \hat f(x_0))^2=\underbrace{Var(\hat f(x_0)) + [Bias(\hat f(x_0))]^2 }_{Reducible-Error}+Var(\epsilon)$$

其中$Bias[\hat f(x_0)]=E[\hat f(x_0)] - f(x_0)$，而这里的E取期望是表示对不同的训练集所产生的不同的拟合函数，最后求得的值的再求平均，Bias表示不同训练集与真实模型的差。$Var(\hat f(x_0))$表示不同训练集训练出的模型的Variance。

$E(y_0 - \hat f(x_0))^2 = E(f(x_0) + \epsilon - \hat f(x_0))^2= Var(\hat f(x_0))+Var(\epsilon) + Bias???$

???

flexibility增加，他的Variance增加（Why？），而Bias减小，但Reducible-Error不一定绝对的上升或下降（应该是先下降再上升），这就是bias-variance trade-off。

---

Classification

Introduction

x的条件类别概率

$$p_k(x) = Pr(Y=k|X=x)$$
k是类别

Bayes Optiomal Classifier

$$C(x)=j if p_j(x) = \max \{p_1(x),p_2(x),\cdots,p_K(x)\}$$

同样，我们也在x某些值时没有data，那么我们可以选择附近的一部分进行估计。

KNN

NN is also Ok in Classification as well.
为什么Regression不行呢？

Measure the performance

$$Err_{Te} = Ave_{i\in Te}I[y_i\neq \hat{C}(x_i)]$$

Ave表示取平均

这么定义真的好么？

SVM, structed models for C(x)

Decision boundary

K=1时，其实就是V图，然后画出的边界
K=100时，太多了，所以大趋势？？？
K=10，well

Bayes error

KNN 是强大的Classfier， 1/3的问题都是可以的
HandWritten digits problem

Example

• Iris
• Handwriting digit recognition