经典机器学习算法（一）：回归算法

学习笔记，大佬勿喷

1. 回归算法

1.1 概述

1.1.1 符号约定

$训练集： (x^{(i)},y^{(i)})，有监督的学习 \\ x^{(i)}为第i个训练样本， x^{(i)}= \begin{bmatrix} 1\\x^{(i)}_{1}\\x^{(i)}_{2}\\...\\x^{(i)}_{n_x} \end{bmatrix}, x^{(i)}_{j}表示第i个样本中的第j个属性\\ y^{(i)}为第i个样本的标签 \\ X = [x^{(1)}, x^{(2)} ...,x^{(m)}] \\ Y = [y^{(1)},y^{(2)},⋯,y^{(m)}]\\ \\ 参数： \Theta=(b,W)=(b,w_1,w_2...,w_{n_x})=(\theta_0,\theta_1...,\theta_{n_x})$训练集：(x(i),y(i))，有监督的学习x(i)为第i个训练样本，x(i)=⎣⎢⎢⎢⎢⎢⎡​1x1(i)​x2(i)​...xnx​(i)​​⎦⎥⎥⎥⎥⎥⎤​,xj(i)​表示第i个样本中的第j个属性y(i)为第i个样本的标签X=[x(1),x(2)...,x(m)]Y=[y(1),y(2),⋯,y(m)]参数：Θ=(b,W)=(b,w1​,w2​...,wnx​​)=(θ0​,θ1​...,θnx​​)

1.1.2 回归与神经网络的区别

• 线性回归：适用于线性可分的样本的回归拟合
• 逻辑回归：多用于二分类，适用于线性模型
• 神经网络：由各个神经元组成，逻辑回归就可以作为神经网络的一个神经元，相比于线性回归，其在每个神经元中增加了非线性的**函数，故神经网络是一个对于处理复杂的非线性模型很优秀的算法。

1.2 线性回归

1.2.1 预测函数

线性回归是根据样本x各个维度的xi的线性叠加（线性叠加的权重系数Θi就是模型的参数）来得到预测值的y，然后最小化所有的样本预测值Y与真实值y’的误差来求得模型参数。我们看到这里的模型的值y是样本x各个维度的xi的线性叠加，是线性的。
$预测函数：h(\Theta)=\Theta x\ = \theta_1x_1+\theta_2x_2+...+\theta_nx_n$预测函数：h(Θ)=Θx =θ1​x1​+θ2​x2​+...+θn​xn​

1.2.2 代价函数

优化问题： 找到一组参数 $\Theta$Θ 使预测值$h(x^{(i)})$h(x(i))与样本标签$y^{(i)}$y(i)拟合
$y^{(i)} = h(\Theta)^{(i)}+\epsilon^{(i)} \\ 误差\epsilon^{(i)}是独立并服从均值为0,方差为\sigma^2的正态分布 \\ 可得误差表达式为：\epsilon^{(i)} = y^{(i)} - h(\Theta)$y(i)=h(Θ)(i)+ϵ(i)误差ϵ(i)是独立并服从均值为0,方差为σ2的正态分布可得误差表达式为：ϵ(i)=y(i)−h(Θ)

我们的目的是使误差接近于0，由于 ε 概率分布的特点可知：
$当\epsilon \rightarrow0时，p(\epsilon) \rightarrow max \\ p(\epsilon^{(i)}) = p(y^{(i)}|x^{(i)}; \Theta) =\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(y^{(i)}-h(\Theta))^2}{2\sigma^2}}$当ϵ→0时，p(ϵ)→maxp(ϵ(i))=p(y(i)∣x(i);Θ)=2π​σ1​e−2σ2(y(i)−h(Θ))2​

由最大似然估计，将每个样本带入可得似然函数L(Θ)，最优化问题就变成了求解 $argmin(L(\Theta))$argmin(L(Θ))的问题
$L(\Theta) = \prod^{m}_{i=1}p(y^{(i)}|x^{(i)}; \Theta) \\ = \prod^{m}_{i=1}\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(y^{(i)}-h(\Theta))^2}{2\sigma^2}} \\ ln(L(\Theta)) = ln(\prod^{m}_{i=1}\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(y^{(i)}-h(\Theta))^2}{2\sigma^2}})\\ = m\ ln(\frac{1}{\sqrt{2\pi}\sigma}) -\frac{1}{2\sigma^2}\sum^{m}_{i=1}((y^{(i)}-h(\Theta))^2)$L(Θ)=i=1∏m​p(y(i)∣x(i);Θ)=i=1∏m​2π​σ1​e−2σ2(y(i)−h(Θ))2​ln(L(Θ))=ln(i=1∏m​2π​σ1​e−2σ2(y(i)−h(Θ))2​)=m ln(2π​σ1​)−2σ21​i=1∑m​((y(i)−h(Θ))2)

由于上式的左部为一个常数，右部才是影响释然函数大小的因素。可以定义损失函数：
$Loss(\Theta) = \frac{1}{2}(h(\Theta)-y^{(i)})^2$Loss(Θ)=21​(h(Θ)−y(i))2

优化问题就变成了 $argmin(J(\Theta))$argmin(J(Θ)) 的问题：
$J(\Theta) = \frac{1}{2m} \sum^{m}_{i=1} ((h(\Theta) - y^{(i)})^2) = \frac{1}{2m}(\Theta X-Y)^T(\Theta X-Y) \\ 其中\frac{1}{m}是为了防止样本的数量对代价函数的影响$J(Θ)=2m1​i=1∑m​((h(Θ)−y(i))2)=2m1​(ΘX−Y)T(ΘX−Y)其中m1​是为了防止样本的数量对代价函数的影响

1.3 逻辑回归

1.3.1 预测函数

logistic回归用于二分类问题（$y^{(i)}=0,1$y(i)=0,1），相比于线性回归而言，求解回归模型时多了一步Sigmoid函数非线性映射，这种自变量$\Theta$Θ 与因变量$h(x^{(i)})$h(x(i))的变化形式就叫做logistic变化。回归模型得到的预测值 $h(x^{(i)})$h(x(i)) 不是预测样本 $x^{(i)}$x(i) 对应的 $y^{(i)}$y(i) 值，而是 $y^{(i)}=0$y(i)=0 或 $y^{(i)}=1$y(i)=1 的概率，通常我们将 $y^{(i)}=1$y(i)=1 时的概率公式作为二分类问题的预测值：
$z^{(i)}=\Theta x^{(i)},\ Sigmoid(z)=\frac{1}{1+e^{-z}} \\ h(x^{(i)}) = P(y^{(i)}=1|x^{(i)}) =Sigmoid(z^{(i)})=\frac{1}{1+e^{-\Theta x^{(i)}}}\\$z(i)=Θx(i), Sigmoid(z)=1+e−z1​h(x(i))=P(y(i)=1∣x(i))=Sigmoid(z(i))=1+e−Θx(i)1​

为什么自变量与因变量要选用logistic关系呢，其原因如下：

1. 我们需要 $h(x^{(i)})$h(x(i)) 代表的是概率，即 $h(x^{(i)})$h(x(i)) ∈（0,1）；
2. 我们需要 $x^{(i)}$x(i) 各维度叠加和在0附近变化幅度比较大，并且是非线性的变化。而在很大或很小的时候，几乎不变化，这是基于概率的一种认识与需要。感性的一个例子，想想你学习努力的程度与从60分提高到80分和80提高到100分并不是线性的。
3. 这个关系的公式要在之后形成的cost function是凸函数。

1.3.2 代价函数

优化问题： 找到一组参数 $\Theta$Θ 使预测值$h(x^{(i)})$h(x(i))与样本标签$y^{(i)}$y(i)拟合

由于Logistics回归的 $h(x^{(i)})$h(x(i)) 表示样本标签预测值等于1的概率，$1-h(x^{(i)})$1−h(x(i)) 表示标签预测值等于0的概率。所以可根据实际样本的标签值$y^{(i)}$y(i) 直接使用极大释然估计求解最优化问题，无需使用误差优化。
$似然函数：L(\Theta)=\prod_{i=1}^{m}[h(x^{(i)})]^{y^{(i)}}[1-h(x^{(i)})]^{1-y^{(i)}} \\ \ln(J'(\Theta)) =\sum_{i=1}^{m}\left[y^{(i)}\ln h(x^{(i)})+(1-y^{(i)})\log(1-h(x^{(i)}))\right] \\$似然函数：L(Θ)=i=1∏m​[h(x(i))]y(i)[1−h(x(i))]1−y(i)ln(J′(Θ))=i=1∑m​[y(i)lnh(x(i))+(1−y(i))log(1−h(x(i)))]

可以定义损失函数为：
$Loss(p^{(i)}, y^{(i)})=-\left[y^{(i)}\ln h(x^{(i)})+(1-y^{(i)})\log(1-h(x^{(i)}))\right]$Loss(p(i),y(i))=−[y(i)lnh(x(i))+(1−y(i))log(1−h(x(i)))]

对似然函数做一定的处理，使其代价函数$J(\Theta)$J(Θ)成为凹函数，最小值点为最优解
$J(\Theta)=-\frac{1}{m}\ln(J'(\Theta)) \\ =-\dfrac{1}{m}\sum_{i=1}^{m}\left[y^{(i)}\ln h(x^{(i)})+(1-y^{(i)})\log(1-h(x^{(i)}))\right]$J(Θ)=−m1​ln(J′(Θ))=−m1​i=1∑m​[y(i)lnh(x(i))+(1−y(i))log(1−h(x(i)))]

1.4 梯度下降法

1.4.1 原理解释

梯度下降法属于一种最优化算法，目的是求解最目标代价函数$J(\Theta)$J(Θ) 的最小值（在机器学习中代价函数一般为凹函数，故使用下降法）。

梯度下降法思想的三要素：出发点、下降方向、下降步长。

此公式的意义是：J是关于待求向量Θ的一个代价函数，我们当前所处的位置为$Θ^0$Θ0点，要从这个点走到J的最小值点，也就是谷底。首先我们先确定前进的方向，也就是梯度的反向，然后走一段距离的步长，也就是α，走完这个段步长，就到达了Θ1这个点！

• α是什么含义？

  α在梯度下降算法中被称作为学习率或者步长，意味着我们可以通过α来控制每一步走的距离，所以α的选择在梯度下降法中往往是很重要的！α不能太大也不能太小，太小的话，可能导致迟迟走不到最低点，太大的话，会导致错过最低点！

  

• 为什么要梯度要乘以一个负号？
  梯度前加一个负号，就意味着朝着梯度相反的方向前进！我们在前文提到，梯度的方向实际就是函数在此点上升最快的方向！而我们需要朝着下降最快的方向走，自然就是负的梯度的方向，所以此处需要加上负号

1.4.2 为何要使用梯度下降

既然知道了代价函数$J( \Theta), \Theta 为待求参数$J(Θ),Θ为待求参数 ，为何不直接令其导数为0求最小值？

1. 可以求出代价函数每个变量的偏导数在每个点的值, 但是直接解方程解不出来。
   $\begin{cases} \frac{\partial J(\Theta)}{\partial\theta_0}=0 \\ \frac{\partial J(\Theta)}{\partial\theta_1}=0 \\ ...\\ \frac{\partial J(\Theta)}{\partial\theta_{n_x}}=0 \end{cases}$⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​∂θ0​∂J(Θ)​=0∂θ1​∂J(Θ)​=0...∂θnx​​∂J(Θ)​=0​

2. 计算机更加适合用循环迭代的方法来求极值。

1.4.3 回归问题梯度下降的运用

为线性回归、逻辑回归定义训练集的代价函数（Cost function）具有如下目标：

• Cost function是待求系数 $\Theta$Θ 的函数；
• 我们的目标就是迭代计算出最佳的$\Theta$Θ的值，最小化Cost function，让其尽可能地接近于0。

由于Cos Function为凹函数，故使用梯度下降法求其最小值

线性回归：

代价函数的梯度：
$\nabla J(\Theta)=&lt;\frac{\partial J}{\partial \theta_0}, \frac{\partial J}{\partial \theta_1}...,\frac{\partial J}{\partial \theta_{n_x}}&gt; =\frac{1}{m}(\Theta X -Y)X^T ，（1 \times n_x\ 行向量） \\ 其中：\frac{\partial J}{\partial \theta_j} =\frac{1}{m}\sum^{m}_{i=1} [L_\Theta(x^{(i)})\times x_{j}^{(i)}] = \frac{1}{m}(\Theta X -Y)^T \times \begin{bmatrix} x_j^{(1)}\\ x_j^{(2)}\\ ...\\ x_j^{(m)} \end{bmatrix} , （标量） \\ i代表样本号，j代表每个样本内部的分量，x^{(i)}\in R^{n_x+1}, x_{j}^{(i)}=R,\ x_0=1$∇J(Θ)=<∂θ0​∂J​,∂θ1​∂J​...,∂θnx​​∂J​>=m1​(ΘX−Y)XT，（1×nx​ 行向量）其中：∂θj​∂J​=m1​i=1∑m​[LΘ​(x(i))×xj(i)​]=m1​(ΘX−Y)T×⎣⎢⎢⎢⎡​xj(1)​xj(2)​...xj(m)​​⎦⎥⎥⎥⎤​,（标量）i代表样本号，j代表每个样本内部的分量，x(i)∈Rnx​+1,xj(i)​=R, x0​=1
代价函数和梯度转化为矩阵向量相乘的形式:
$J(\Theta)=\frac{1}{2m}(\Theta X-Y)(\Theta X-Y)^T \\ \nabla J(\Theta)=\frac{1}{m}X^T(\Theta X-Y) \\$J(Θ)=2m1​(ΘX−Y)(ΘX−Y)T∇J(Θ)=m1​XT(ΘX−Y)
可得每轮迭代待求解参数的修正表达式：
$\Theta=\Theta-\alpha\dfrac{\partial J(\Theta)}{\partial W}= \begin{bmatrix} \theta_1−αd\theta_1 \\ \theta_2−αd\theta_2 \\ ... \\ \theta_{n_x}−αd\theta_{n_x} \end{bmatrix}$Θ=Θ−α∂W∂J(Θ)​=⎣⎢⎢⎡​θ1​−αdθ1​θ2​−αdθ2​...θnx​​−αdθnx​​​⎦⎥⎥⎤​

逻辑回归：

使用联式求导法得：
$da = \dfrac{\partial L}{\partial a} =-\dfrac{y}{a}+\dfrac{1-y}{1-a} \\ dz = \dfrac{\partial L}{\partial z} =\dfrac{\partial L}{\partial a}\cdot\dfrac{\partial a}{\partial z} =(-\dfrac{y}{a}+\dfrac{1-y}{1-a})\cdot a(1-a) =a-y \\ d\theta_{j} = \dfrac{\partial L}{\partial \theta_{j}} =\dfrac{\partial L}{\partial z}\cdot\dfrac{\partial z}{\partial \theta_{j}} =x_{j}^{(i)}\cdot dz =\dfrac{1}{m}\sum_{i=1}^{m}x_{j}^{(i)}(a^{(i)}-y^{(i)})$da=∂a∂L​=−ay​+1−a1−y​dz=∂z∂L​=∂a∂L​⋅∂z∂a​=(−ay​+1−a1−y​)⋅a(1−a)=a−ydθj​=∂θj​∂L​=∂z∂L​⋅∂θj​∂z​=xj(i)​⋅dz=m1​i=1∑m​xj(i)​(a(i)−y(i))
可得每轮迭代待求解参数的修正表达式：
$\Theta=\Theta-\alpha\dfrac{\partial J(\Theta)}{\partial W}= \begin{bmatrix} \theta_1−αd\theta_1 \\ \theta_2−αd\theta_2 \\ ... \\ \theta_{n_x}−αd\theta_{n_x} \end{bmatrix}$Θ=Θ−α∂W∂J(Θ)​=⎣⎢⎢⎡​θ1​−αdθ1​θ2​−αdθ2​...θnx​​−αdθnx​​​⎦⎥⎥⎤​

---

参考文献：

https://mooc.study.163.com/smartSpec/detail/1001319001.htm
https://www.jianshu.com/p/c7e642877b0e