台湾大学林轩田老师的《机器学习基石》课程由浅入深、内容全面，基本涵盖了机器学习领域的很多方面，作为机器学习的入门资料非常适合。很久之前看过这门课，但是有些地方还是不太明白，二刷这门课，把重要的知识总结起来，算是做一个复习，加深理解，也方便之后查阅。这篇文章介绍了第三部分How Can Machine Learn？

How Can Machine Learn？

本章将介绍机器学习中比较常见的算法：Linear Regression、Logistic Regression

Linear Regression

线性回归的预测函数取值在整个实数空间，记做

$h(x)=w^TX$

根据上图，在一维或者多维空间里，线性回归的目标是找到一条直线（对应一维）、一个平面（对应二维）或者更高维的超平面，使样本集中的点更接近它，也就是残留误差Residuals最小化。一般最常用的错误测量方式是基于最小二乘法，其目标是计算误差的最小平方和对应的权重$w$。此外需要提一点，最小二乘法可以解决线性问题和非线性问题，线性最小二乘法的解是closed-form，即$X=(A^TA)^{-1}A^Ty$，而非线性最小二乘法没有closed-form，通常用迭代法求解。

样本数据误差$E_{in}$是权重$w$的函数，因为$X$和$y$都是已知的，我们的目标是找出合适的$w$，使得$E_{in}$能够最小。

首先，运用矩阵转换的思想，将$E_{in}$计算转换为矩阵的形式。

然后，对于此类线性回归问题，$E_{in}(w)$一般是个凸函数，凸函数的话，我们只要找到一阶导数等于0的位置，就找到了最优解。那么，我们将$E_{w}$对每个$w_{i},i=0,1,\cdots ,d$求偏导，偏导为零的$w_i$，即为最优化的权重值分布。

根据梯度的思想，对$E_w$进行矩阵化求偏导处理

令偏导为零，最终可以计算出权重向量$w$为

最终，我们推导得到了权重向量$w=(X^TX)^{-1}X^Ty$，这是上文提到的closed-form解。其中，$(X^TX)^{-1}X^T$又称为伪逆矩阵pseudo-inverse，记为$X^+$，维度是$N(d+1)$。

但是，我们注意到，伪逆矩阵中有逆矩阵的计算，逆矩阵$(X^TX)^{-1}$是否一定存在？一般情况下，只要满足样本数量N远大于样本特征维度d+1，就能保证矩阵的逆是存在的，称之为非奇异矩阵。但是如果是奇异矩阵，不可逆怎么办呢？其实，大部分的计算逆矩阵的软件程序，都可以处理这个问题，也会计算出一个逆矩阵。所以，一般伪逆矩阵是可解的。

Logistic Regression

一个心脏病预测的问题：根据患者的年龄、血压、体重等信息，来预测患者是否会有心脏病。很明显这是一个二分类问题，其输出y只有{-1,1}两种情况。

二元分类，一般情况下，理想的目标函数f(x)>0.5，则判断为正类1；若f(x)<0.5，则判断为负类-1。但是，如果我们想知道的不是患者有没有心脏病，而是到底患者有多大的几率是心脏病。这表示，我们更关心的是目标函数的值（分布在0,1之间），表示是正类的概率（正类表示是心脏病）。因此，我们需要找到一个特征加权和$s\in (-\infty ,+\infty)$，并将s的取值限定在[0,1]之间。一个方法是使用Sigmoid函数，记做$\theta (s)$，那么我们的目标就是找到一个hypothesis：$h(x)=\theta (w^Tx)$。

Sigmoid函数记为$\theta (s)=\frac{1}{1+e^{-s}}$，满足$\theta (-\infty) = 0, \theta (0)=\frac{1}{2}, \theta (+\infty)=1$，这个函数是平滑的、单调的S型函数，对于Logistic Regression问题，hypothesis的形式如下：

$h(x)=\frac{1}{1+e^{-w^Tx}}$

因此，我们的目标就是求出这个预测函数h(x)，使它接近目标函数f(x)。

且慢，我们将Logistic Regression与之前讲的Linear Classification、Linear Regression做个比较

Linear Classification的误差使用的是0/1 err；Linear Regression的误差使用的是squared err。那么Logistic Rregression的误差该如何定义呢？

先介绍一下“似然性”的概念，如果我们找到了hypothesis很接近目标函数$f(x)$，也就是说，在所有的Hypothesis集合中找到一个hypothesis与目标函数最接近，能产生同样的数据集D，包含y输出label，则称这个hypothesis是最大似然likelihood。

$h(x)=\theta (w^Tx)$满足一个性质：$1-h(x)=h(-x)$。那么，似然性为$likehood(h)=P(x_1)h(+x_1)*P(x_2)h(-x_2)*\cdots *P(x_N)h(-x_)n$。

因为$P(x_n)$对所有的h来说，都是一样的，所以我们可以忽略它。那么我们可以得到logistic h正比于所有的$h(y_nx)$乘积。我们的目标就是让乘积值最大化。我们将Logistic Regression的err function称之为交叉熵误差：

$err(W,X,Y)=ln(1+exp(-ywx))$

那么接下来的问题就是如何找到合适的向量w，让$E_{in}$最小

$min\quad E_{in}(W)=\frac{1}{N}\sum^N_{n=1}ln(1+exp(-y_nW^Tx_n))$

Logistic Regression的$E_{in}$是连续、可微、二次可微的凸曲线（开口向上），根据之前Linear Regression的思路，我们只要计算$E_{in}$的梯度为零时的w，即为最优解。我们把$E_{in}(w)$曲线看做是一个山谷的话，要求$E_{in}(w)$最小，即可比作下山的过程。整个下山过程由两个因素影响：一个是下山的单位方向w；另外一个是下山的步长$\eta$。

利用微分思想和线性近似，假设每次下山我们只前进一小步，即$\eta$很小，那么根据泰勒Taylor一阶展开，可以得到

$E_{in}(w_t+\eta v)\approx E_in(w_t)+\eta v^T\bigtriangledown E_in(w_t)$

迭代的目的是让$E_{in}$越来越小，即让$E_{in}(w_t+\eta v)<E_{in}(w_t)$。$\eta$是标量， 因为如果两个向量方向相反的话，那么他们的内积最小（为负），也即是说如果方向$v$与梯度反向的话，那么就能保证每次地跌 E_{in}(w_t_\eta v) < E_{in}(w_t)都成立。则，我们令下降方向为

$v=-\frac{\bigtriangledown E_{in}(w_t)}{||\bigtriangledown E_{in}(w_t)||}$

$v$是单位方向，$v$每次都是沿着梯度的反方向走，这种方法称为梯度下降（gradient descent）算法。那么每次迭代公式就可以写成

$w_{t+1}\gets w_t-\eta \frac{\bigtriangledown E_{in}(w_t)}{||\bigtriangledown E_{in}(w_t)||}$

下面讨论一下$\eta$的大小对迭代优化的影响，$\eta$如果太小的话，那么下降的速度就会很慢，$\eta$如果很大的话，那么之前利用Taylor展开的方法就不准了，造成下降不稳定，甚至会上升。因此，$\eta$应该选择合适的值，一种方法是在梯度较小的时候，选择小的$\eta$，梯度较大的时候，选择大的$\eta$。