机器学习CR-EP03：欠拟合与过拟合【存疑】

By arthur503 -- 01 Nov 2013

貌似这节课和上两节课都是连着上的（难道每次课3小时的节奏？），Andrew先是写了个课程思路的outline，如下：

Linear Regression	→	Locally Weighted Regression（Andrew之前一个mentor最喜欢的算法）

Probabilistic interpretation

Logistic Regression 	→	Digression Perceptron

Newton Method（最后没讲到）

之后，又总结了下上节课的数学符号（估计之前是大课间，回来再总结下）：

(x^{(i)}, y^{(i)})：第i个训练样本
h_{θ}(x^{(i)}) 	 = ∑_{j=0}^{n}θ_{j}x_{j}^{(i)} = θ^{T}x 	假设函数对第i个训练样本的输出（每个训练样本有n个feature）
J(θ) = 1/2 * ∑_{i=1}^{m}(h_{θ}(x^{(i)} - y^{(i)}))^{2}
θ = (x^{T}x)^{-1}x^{T}y

线性回归

之后，继续以房价模型为例，如果有m个数据点，那么以x1=size建模，即为线性模型；以x1=size, x2=size^2建模，则为二阶模型；m个数据点，则最高可建m+1阶模型（模型曲线通过每一个数据点）。则可以看出，m+1阶模型的时候，属于过拟合状态，而一阶线性模型时，属于欠拟合状态；而二阶模型的效果比较好。

这里有两个问题：

1. 如何判断模型的好坏？为了防止过拟合的，《统计学习方法》里面有讲过，使用正则化和交叉验证。至于如何判断模型好坏，我们可以通过下一个问题来解答。 2. 如何选取合适的特征？这个之后会将特征选择算法，因此此处先【存疑】。

Parameter Learning Algorithm和Non-Parameter Learning Algorithm

对于线性回归这样的算法模型，都需要有固定个数的参数，因此可以称为Parameter Learning Algorithm；如果算法中的参数随着数据集数量m的变化而变化，则称为Non-Parameter Learning Algorithm（非参学习方法）。注意：非参学习方法并非没有参数，相反，一般其参数为m，而且在学习完毕之后还需要维持数据集（实际上每次预测都需要遍历一遍数据集）。非参学习方法的一个例子就是：Locally Weighted Regression(局部加权回归)，以前的名字也叫Loess。

以局部加权回归为例，它实际上是每次都是在所需预测的点周围，与预测点越近的点的权值越高（趋近于1），越远则权值越低（趋近于0），因此，在单点的结果类似于是该点的切线，合并起来的最终结果是类似于将所有的点串联起来的曲线（如：举例中所使用的钟形曲线），这样，在每次对新的点进行预测的时候，由于没有曲线的函数表示，因此还是需要在该点周围进行一遍加权计算，得到该点附近的近似切线的曲线，从而进行预测。

LWR中的权重函数w^{(i)}是可以自己选择的，Andrew在课堂中选择的类似高斯分布函数，但他强调说着和并高斯分布函数没有关系，只是看起来像而已。

非参学习方法的好处在于无需太担心参数选择的问题。不过，非参学习方法并没有解决过拟合的问题。而且，对于大数据集，每次运算均需要遍历一遍，效率比较低（即便优化之后，只计算区间的数据，也比不上线性回归那样得到假设函数后就是O(1)的复杂度了）。不过即便如此，Andrew说，这个算法在飞机飞行中使用到了，可见在计算能力OK的情况下，还是个很好的算法。

线性回归的概率解释

此处只是非加权的线性回归的概率解释，不包含局部加权回归。那么，在线性回归中，为什么选用最小二乘法，而不是，比如说，面积的绝对值、四次方等来计算呢？

Andrew给出一组假设（这组假设只是一种可能性，并不保证所有状态下都成立，但是，在其他状态下不成立的时候，也可以有其他的假设来满足其状态），即：各个特征的条件是独立同分布的，这样，根据中心极限定理，引入一个误差函数e，可以认为e是符合高斯分布的。之后，利用概率的知识推导得到：为了选择合适的θ使得似然函数最大化，相当于最小化函数l(θ)（=LogL(θ)=LogP(y|x;θ)），推得到的l(θ)与之前的J(θ)的表达式相同。这就是J(θ)的概率解释。

分类算法之Logic Regression（逻辑回归）

下面要学的是第一个分类算法：Logic Regression（逻辑回归）。

如果某个分类问题的点为一些0和一些1的分布，那么，若用线性回归，得到一条斜直线，并不能很好的表现模型的特征。这时，我们引入逻辑回归算法。

逻辑回归是选择：

h_{θ}(x)=g(θ^{T}x) = frac{1}{1+exp(-θ^{T}x)}
其中，g(z) = frac{1}{1+exp(-z)}

g(z)叫做sigmoid function，也叫做logic function（类似于以前学的阶跃函数，在0附近跳跃，从趋于0变为趋于1）。

注：为什么使用logic function？一是因为这是一类更广泛的线性模型；二是，【存疑：以后再讲。。。】。

这样，Andrew通过概率推导，重新得到l(θ)，再次使用梯度下降法（不过这次由于是”+”号，所以其实是梯度上升法），可以退出θ的更新式。

可以看到，Logic Regression中θ的更新式与Linear Regression中的表达式很相似，不过二者确实不同，因为h_{θ}(x)函数并不相同。不过，Andrew说着并不是巧合，以后会更多讨论通用的学习模型。

Digression Perceptron（感知机算法）

在Logic Regression中，h_{θ}(x)是Logic function，取值范围在[0~1]的区间上。在感知机算法中，对此作了改变，即：使g(z)为离散的{0,1}函数：

g(z) = z≥0 ? 1 : 0

这里我用了Java语言的表达方法。

感知机中，其他的函数的推导类似，因此最后得到的θ的更新式也是相似的。不过，虽然这次θ的更新式与上面讲到的Linear Regression和Logic Regression相似，但是，Andrew说其实是不同的学习规则。【存疑：不同在哪里？】对于感知机的这种离散的二分类，很难赋予概率意义，不过在实际计算中比较简单，之后也会再次用到。