[数据结构与算法]机器学习入门之线性回归与逻辑回归

前言

本文为吴恩达机器学习课程的笔记系列第一篇，主要关于线性回归与逻辑回归的详细推导，以及介绍两者之间的区别。

线性回归 LinearRegression

单元线性回归

属于回归问题，我们先来看代价函数的定义。

代价函数 cost function

线性平方代价函数：

$$h_{\theta }(x)={\theta }_0+{\theta }_{1}x$$

建模误差平方和：

$$J({\theta }_0,{\theta }_1)=\frac{1}{2m}\sum _{i=1}^m(h_{\theta }(x^{(i)})?y^{(i)}{)}^2$$

几个概念：

• 误差平方和(Sum of the Squared Errors,即SSE)：用来表明函数拟合的好坏

• 均方误差(MSE)：，指参数估计值与参数真值之差的平方的期望值。

梯度下降 gradient descent

基于经典的下山问题，即当你在山上的某一点时，因如何在山上选择最佳的下山方向，以及每一步因走多大。梯度下降目的是用来求代价函数最小值。

算法思想：

• 初始选择一个参数组合，计算代价函数
• 接着寻找得使得代价函数值下降最多的参数组合，并同样计算代价函数
• 持续上述过程，直至目标值为局部最小值

批量梯度下降(batch gradient descent)

公式(假设两个参数)：${\theta }_j={\theta }_j?\alpha \frac{?}{?{\theta }_j}J({\theta }_0,{\theta }_j)$

• $\alpha$ 为学习率(learing rate)，它决定了我们沿着能让代价函数下降程度最大的方向向下迈出的步子有多大，在批量梯度下降中，我们每一次都同时让所有的参数减去学习速率乘以代价函数的导数。
• 对于多个$\theta$ ，必须同步更新值，学习率也是会更新的，因为越接近极值点，我们的学习率也就是下山的步长应该越小，这样的结果才越准确。实际上就是要偏导数为0，使之收敛于局部最优解。

如何选择 $\alpha$ 值？

• 基于上式，我们可以看到若 $\alpha$ 太小，每一次的步伐非常小，一点一点移动接近最低点，这样一次迭代花费时间会很久。
• 若 $\alpha$ 太大，那么移动步伐过大，可能会越过最低点，下一次迭代移动又再越一次，一次次越过最低点，这样就会导致无法收敛。
• 一般实际应用中，选择一组区间如 $[0.01,0.1,1,10]$ 这样去多次尝试，再根据结果进一步更选择合适的区间。

在梯度下降法中，当我们接近局部最低点时，梯度下降法会自动采取更小的幅度，这是因为当我们接近局部最低点时，很显然在局部最低时导数等于零，所以当我们接近局部最低时，导数值会自动变得越来越小，所以梯度下降将自动采取较小的幅度，也就是 $\alpha$ 没必要在此时另外减小了。

梯度下降的线性回归

梯度下降算法：

R e p e a t ?? u n t i l ?? c o n v e r g e n c e { θ j = θ j ? α ? ? θ 0 J ( θ 0 , θ 1 ) f o r ?? j = 0 ?? a n d ?? 1 } \begin{aligned} &Repeat\;until\;convergence\{ \\ & \quad\theta_j=\theta_j-\alpha\dfrac{\partial}{\partial\theta_0}J(\theta_0,\theta_1) \\ & \quad for\;j=0\;and\;1\\ &\} \end{aligned} ?Repeatuntilconvergence{θj?=θj??α?θ0???J(θ0?,θ1?)forj=0and1}?

对代价函数求导：

$$\frac{?}{?{\theta }_j}J({\theta }_0,{\theta }_1)=\frac{?}{?{\theta }_j}\frac{1}{2m}\sum _{i=1}^m(h_{\theta }(x^{(i)})?y^{(i)}{)}^2$$

$$j=0,\frac{?}{?{\theta }_0}J({\theta }_0,{\theta }_1)=\frac{1}{m}\sum _{i=1}^m(h_{\theta }(x^{(i)})?y^{(i)}),{\theta }_0={\theta }_0?\alpha \frac{1}{m}\sum _{i=1}^m(h_{\theta }(x^{(i)})?y^{(i)})$$

$$j=1,\frac{?}{?{\theta }_1}J({\theta }_0,{\theta }_1)=\frac{1}{m}\sum _{i=1}^m(h_{\theta }(x^{(i)})?y^{(i)})?x^{(i)},{\theta }_1={\theta }_1?\alpha \frac{1}{m}\sum _{i=1}^m(h_{\theta }(x^{(i)})?y^{(i)})?x^{(i)}$$

我们也可以利用**“最小二乘法”**来对模型求解。在线性回归中，最小二乘法就是试图找到一条直线，是所有样本到直线上的欧式距离之和最小，也就是模型中的$J({\theta }_0,{\theta }_1)$ 最小。

解法：分别对 ${\theta }_0,{\theta }_1$ 求导并令所求式子为0，从而解出${\theta }_0,{\theta }_1$ 最优解。

多元线性回归

其实就是 单特征=>多维特征，用向量表示

假设特征数量为 $n$ ，特征矩阵如下：

$$\begin{gathered} X=\begin{array}{c} \\ \\ x^{(1)}:\\ x^{(2)}:\\ x^{(3)}:\\ ...\end{array}\begin{array}{cccc} \\ \text{特征}1& \text{特征}2& \text{特征}3& \text{特征}4\\ 1& 0.2& 41& 6\\ 2& 0.6& 35& 4\\ 5& 0.5& 60& 8\\ ...& ...& ...& ...\end{array}=?\begin{array}{c}{x}^{(1{)}^T}\\ x^{(2{)}^T}\\ x^{(3{)}^T}\\ ...\\ x^{(n{)}^T}\end{array}? \end{gathered}$$

$x^{(i)}$代表第 $i$ 个特征实例，也就是特征矩阵的第 $i$ 行，是一个向量，如 $$\begin{gathered} x^{(2)}=\left[\begin{array}{c}2 \\ 0.6 \\ 35 \\ 4\end{array}\right] \end{gathered}$$

多变量的 $h$ 表示为：

$$h_{\theta }(x)={\theta }_0+{\theta }_{1}x+{\theta }_2{x}_2+...+{\theta }_n{x}_n$$

可以看出，参数为一个 $n+1$ 维的向量，特征矩阵的维度为 $m?(n+1)$，为了计算方便，我们引入 $x_0=1$,即公式变为：

$$h_{\theta }(x)={\theta }_0{x}_0+{\theta }_1{x}_1+{\theta }_2{x}_2+...+{\theta }_n{x}_n$$

令 $$\begin{gathered} \theta =\left[\begin{array}{c}{\theta }_0 \\ {\theta }_1 \\ ... \\ {\theta }_n\end{array}\right] \end{gathered}$$

故进一步简化：$h_{\theta }(x)={\theta }^{T}x$

梯度下降

在单元线性回归的梯度下降基础上拓展，

$$\frac{?}{?{\theta }_j}J({\theta }_j)=\frac{?}{?{\theta }_j}\frac{1}{2m}\sum _{i=1}^m(h_{\theta }(x^{(i)})?y^{(i)}{)}^2$$

特征缩放：放缩每个特征，大约至 $[?1,1]$

均值归一化(Mean normalization)：就是标准化

• $x_i=\frac{x_i?{\mu }_i}{max?min}$
• $i>1,\text{因为}{x}_0=1$

正规方程

假设训练集结果为向量 $y$ ，引入$x_0$ 后，特征矩阵也可写为：

$$\begin{gathered} X=\begin{array}{cccc} \\ \text{特征}1& \text{特征}2& \text{特征}3& \text{特征}4\\ 1& 0.2& 41& 6\\ 2& 0.6& 35& 4\\ 5& 0.5& 60& 8\\ ...& ...& ...& ...\end{array}=\begin{array}{cc} \\ & \\ 1& x^{(1{)}^T}\\ 1& x^{(2{)}^T}\\ 1& x^{(3{)}^T}\\ 1& ...\end{array} \end{gathered}$$

将上述的代价函数写作矩阵形式：

$$J(\theta )=\frac{1}{2m}(X\theta ?y{)}^T(X\theta ?y)$$

实际上就是求解使得 $J(\theta )$ 最小的 参数 $\theta$ 值，即如下表示：

$$\theta =argmin(X\theta ?y{)}^T(X\theta ?y)$$

令 $E_{\theta }=(X\theta ?y{)}^T(X\theta ?y)$ ，对 $\theta$ 求导可解得：

$$\theta =(X^{T}X{)}^{?1}{X}^{T}y$$

梯度下降与正规方程的比较

逻辑回归 Logistic Regression

属于分类问题。对于分类问题，数据一般是离散的，应用线性回归的方法处理分类问题并不是一个很好的方法，所以下面介绍一种处理分类问题的经典算法——逻辑回归。

逻辑回归的本质是：假设数据服从这个分布，然后使用极大似然估计做参数的估计，使得输出的变量范围始终在0和1之间。下面以二分类问题为例介绍该算法。

逻辑回归的分布函数采用的是 $Sigmoid$ 函数： $g(z)=\frac{1}{1+e^{?z}}$ ，该函数图像如下：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Cb4IBXex-1628157342810)(/imgs/Sigmoid函数图像.jpg)]

可以看出该函数将输入数值转换至概率值，所以我们借此可构造逻辑回归模型的假设函数是：

$$h_{\theta }(x)=g({\theta }^{T}x)=\frac{1}{1+e^{?{\theta }^{T}x}}$$

其中： $x$ 代表特征向量，$\theta$ 为我们要求取的参数。

$$P(y=1|x;\theta )=h_{\theta }(x)$$

即表示给定 $x$ 和 $\theta$ 的条件下，预测 $y=1$ 的概率

可以得到决策函数：

$$y(i)=1,\text{if?}P(y=1|x)>0.5$$

$0.5$ 就是我们选择的阈值，当然可以根据实际情况选择其它数值，比如对正例的预测性高一点，就可以大于0.5

决策边界

这个概念的介绍引用吴恩达教授的课程ppt

线性决策边界

非线性边界

代价函数

定义逻辑回归的代价函数为：

$$J(\theta )=\frac{1}{m}\sum _{i=1}^{m}Cost(h_{\theta }(x^{(i)})?y^{(i)})$$

其中:

$$Cost(h_{\theta }(x),y)=\{\begin{array}{ll}?log(h_{\theta }(x))& y=1\text{时}\\ ?log(1?h_{\theta }(x))& y=0\text{时}\end{array}$$

$Cost(h_{\theta }(x),y)$ 函数的特点是：

• 当实际的 $y=1$ 时， $h_{\theta }(x)=1$ 时代价为 0，当 $h_{\theta }(x)$ 不为 $1$ 时，代价随着 $h_{\theta }(x)$ 变小而变大；
• 当实际的 $y=0$ 时， $h_{\theta }(x)=0$ 时代价为 0，当 $h_{\theta }(x)$ 不为 $0$ 时，代价随着 $h_{\theta }(x)$ 变大而变大；

图像如下：
可进一步化简：

$$J(\theta )=?\frac{1}{m}\sum _{i=1}^m[y^{(i)}log(h_{\theta }(x))+(1?y^{(i)})log(1?h_{\theta }(x))]$$

使用梯度下降

对代价函数 $J(\theta )$ 求导，可得

$$\frac{?}{?\theta }J(\theta )=\frac{1}{m}\sum _{i=1}^m(h_{\theta }(x^{(i)})?y^{(i)})x^{(i)}$$

同样对 ${\theta }_j={\theta }_j?\alpha \frac{1}{m}\sum _{i=1}^m(h_{\theta }(x^{(i)})?y^{(i)})$ 不停更新每个参数值，直至求出使函数值最小化，也就是导数值趋于$0$的 $\theta$ 即可。

多分类问题

通常采用 One-vs-All，亦称 One-vs-the Rest 方法来实现多分类，其将多分类问题转化为了多次二分类问题。其实就是轮流把某一特征视为正样本，其余统统视为负样本，然后同二分类一样进行模型训练。若样本特征数为 $n$ ，总共会获得 $n?1$ 个决策边界。

例：给定输入 $x$，分别计算 $h_{\theta }^{(i)}(x),i=1,2,...,n$ ，然后进行比较，若$h_{\theta }^{(k)}(x)$ 最接近$1$ ，则预测 $x$ 属于 $k$ 类。

过拟合与欠拟合

什么是过拟合？

欠拟合(underfitting)：拟合程度不高，数据距离拟合曲线较远

过拟合(overfitting)：过度拟合，貌似拟合几乎每一个数据，但是丢失了信息规律。在机器学习中，经常出现训练集拟合程度过高，过于精确，这样的模型并无实际预测意义。

正则化

上述提到了存在的过拟合问题，那么解决过拟合的方法一般有：

• 减少特征数。这样显然会破坏特征的完整性。
• 保留特征，但是弱化一些高阶项的系数 ${\theta }_i$ 。我们把这种弱化称之为对参数 ${\theta }_i$ 的惩罚。

所谓正则化，就是弱化高阶特征的过程。

线性回归中的正则化

在线性回归的基础上，我们引入参数 $\lambda$ 来实现正则化惩罚。将代价函数改为：

$$\begin{gathered} J(\theta )=\frac{1}{2m}\sum _{i=1}^m[(h_{\theta }(x^{(i)})?y^{(i)}{)}^2+\lambda \sum _{i=1}^n{\theta }_j^2] \\ =\frac{1}{2m}[(X\theta ?y{)}^T(X\theta ?y)+\lambda \sum _{j=1}^n{\theta }_j^2] \end{gathered}$$

$\lambda$ 越大，正则化惩罚力度越大，就越能避免过拟合。当然也不能太大，不然参数的趋于0，最后的图像可能是一条直线。

同时，梯度下降中也发生相应变化：

R e p e a t ?? u n t i l ?? c o n v e r g e n c e { θ 0 = θ 0 ? α 1 m ∑ i = 1 m [ ( h θ ( x ( i ) ) ? y ( i ) ) x 0 ( i ) ] θ j = θ j ? α 1 m ∑ i = 1 m [ ( h θ ( x ( i ) ) ? y ( i ) ) x ( i ) + λ m θ j ] f o r ? j = 1 , 2 , . . , n } \begin{aligned}&Repeat\;until\;convergence\{ \\ & \quad \theta_0=\theta_0-\alpha\frac{1}{m}\sum\limits_{i=1}^m [(h_{\theta}(x^{(i)})-y^{(i)})x_0^{(i)}] \\ & \quad \theta_j=\theta_j-\alpha\frac{1}{m}\sum\limits_{i=1}^m [(h_{\theta}(x^{(i)})-y^{(i)})x^{(i)} + \frac{\lambda}{m}\theta_j]\\ & \quad for \ j=1,2,..,n\\ &\}\end{aligned} ?Repeatuntilconvergence{θ0?=θ0??αm1?i=1∑m?[(hθ?(x(i))?y(i))x0(i)?]θj?=θj??αm1?i=1∑m?[(hθ?(x(i))?y(i))x(i)+mλ?θj?]for?j=1,2,..,n}?

可进一步简化为：

$${\theta }_j={\theta }_j(1?\alpha \frac{\lambda }{m})?\alpha \frac{1}{m}\sum _{i=1}^m[h_{\theta }(x^{(i)})?y^{(i)}]x_j^{(i)}$$

可以看出，正则化线性回归的梯度下降算法的变化在于，每次都在原有算法更新规则的基础上令 $\theta$ 值减少了一个额外的值，也就是梯度下降中每次更新 $\theta$ 的同时也会减小 $\theta$ 值。

若用正规方程，则同样可以求解，方法如下：

$$\theta =(X^{T}X+\lambda ?\begin{array}{cccc}0& ...& ...& 0\\ 0& 1& ...& 0\\ ...& ...& ...& ...\\ 0& 0& ...& 1\end{array}?{)}^{?1}{X}^{T}y$$

逻辑回归中的正则化

同样对于逻辑回归，我们也给代价函数增加一个正则化的表达式，得到代价函数：

$$J(\theta )=\frac{1}{m}\sum _{i=1}^m[?y^{(i)}log(h_{\theta }(x))?(1?y^{(i)})log(1?h_{\theta }(x))]+\frac{\lambda }{2m}\sum _{j=1}^n{\theta }_j^2$$

同样得出梯度下降算法为：

R e p e a t ?? u n t i l ?? c o n v e r g e n c e { θ 0 = θ 0 ? α 1 m ∑ i = 1 m [ ( h θ ( x ( i ) ) ? y ( i ) ) x 0 ( i ) ] θ j = θ j ? α 1 m ∑ i = 1 m [ ( h θ ( x ( i ) ) ? y ( i ) ) x ( i ) + λ m θ j ] f o r ? j = 1 , 2 , . . , n } \begin{aligned}&Repeat\;until\;convergence\{ \\ & \quad \theta_0=\theta_0-\alpha\frac{1}{m}\sum\limits_{i=1}^m [(h_{\theta}(x^{(i)})-y^{(i)})x_0^{(i)}] \\ & \quad \theta_j=\theta_j-\alpha\frac{1}{m}\sum\limits_{i=1}^m [(h_{\theta}(x^{(i)})-y^{(i)})x^{(i)} + \frac{\lambda}{m}\theta_j]\\ & \quad for \ j=1,2,..,n\\ &\}\end{aligned} ?Repeatuntilconvergence{θ0?=θ0??αm1?i=1∑m?[(hθ?(x(i))?y(i))x0(i)?]θj?=θj??αm1?i=1∑m?[(hθ?(x(i))?y(i))x(i)+mλ?θj?]for?j=1,2,..,n}?

注意，${\theta }_0$ 是不参与其中的任何一个正则化的。

小结

线性回归与逻辑回归的区别

线性回归与逻辑回归都是一种广义线性模型(generalized linear model)。线性回归假设因变量 y 服从高斯分布，而逻辑回归假设因变量 y 服从伯努利分布。 线性回归是回归任务，逻辑回归是分类任务。

逻辑回归与线性回归虽然代价函数求导后看起来形式一样，但是二者的假设函数 $h_{\theta }(x)$ 是不同的。

• 线性回归：$h_{\theta }(x)={\theta }^{T}x$
• 逻辑回归：$h_{\theta }(x)=g({\theta }^{T}x)$ ，其中$g(z)$为 $Sigmoid$ 函数

附上课后作业的代码实现（github）：

• ex1-Linear Regression
• ex2-Logistic Regression