机器学习公式推导

  本篇笔记主要记录及推导Andrew NG的Machine Learning课程中出现的公式。

  我们假设对于任意的分类、聚类、回归等问题在自然界中总是存在一个精确的模型与之相对应,接下来我们要做的就是根据获取的样本来反推并确定这个模型。由于我们毕竟无法遍历这个问题所有的情况,所以我们只能根据获取的样本去尽可能接近的确定这个模型。

  公式化上面这段描述,问题对应的模型就藏在假设空间(Hypothesis) hθ(x)中,我们需要通过观测样本,确定其中的θ值。在确定θ值的过程中,定义一个损失函数(Cost Function) J(θ),如果我们获取的样本在某一个参数θ时使损失值达到最小,即表示当前θ值确定的模型可以使预测值很接近观察值。那么这个模型就是我们需要寻找的。

  对于监督学习,我们要做的就是确定目标函数,损失函数,然后通过样本训练,得到损失值最小的那一组参数值,用该参数值代入目标函数,即可得到对应问题的模型。

一、线性回归模型

1、单一变量的线性回归模型

  目标函数

hθ(x)=θ0+θ1x

  损失函数
J(θ0,θ1)=12mi=1m(hθ(x(i))y(i))2

  公式说明:
  hθ(x(i)):i
  y(i):i

  接下来的目标就是找到一组参数值,使得损失函数值最小,即

minimizeθ0,θ1J(θ0,θ1)

  求损失函数最小值时,使用梯度下降(Gradient descent)的方法。在微积分中我们学过梯度,梯度方向是函数值下降最快的方向,所以在梯度下降方法中,我们分别求θ0θ1的偏导数,然后用该导数值更新参数值。

(7)repeat until convergence{θj:=θjαθjJ(θ0,θ1)(for j = 1 and j = 0)}

  说明,上面公式中的:=表示赋值的意思,如果直接写a = 1可能会被误理解为判断a是否等于1

  求损失函数J(θ0,θ1)θ0θ1的偏导数,

θ0J(θ0,θ1)=1mi=1m(hθ(x(i))y(i))θ1J(θ0,θ1)=1mi=1m(hθ(x(i))y(i))x(i)

使用偏导数公式对上式展开。

(8)repeat until convergence{θ0:=θ0α1mi=1m(hθ(x(i))y(i))θ1:=θ1α1mi=1m(hθ(x(i))y(i))x(i)}
 

2、多变量线性回归模型

  上一节的模型中只有一个指标x,理解了线性回归模型及其寻找最优化参数的过程。接下来将该思路应用到多变量模型中。

(1)目标函数

hθ(x)=θ0x0+θ1x1+θ2x2++θnxn

  上式中的x1,x2,,xn都是给定样本中的指标,其中x0=1是人为增加的。
  如果将目标函数使用向量表示,
hθ(x)=θTx

(2)损失函数

J(θ)=12mi=1m(hθ(x(i))y(i))2

(3)梯度下降

(9)repeat until convergence{θj:=θjαθjJ(θ)(for j = 0 ,, n)}

  分别对θ0,θ1,θ2求偏导数并进行展开,如下所示

θ0:=θ0α1mi=1m(hθ(x(i))y(i))θ1:=θ1α1mi=1m(hθ(x(i))y(i))x1(i)θ2:=θ2α1mi=1m(hθ(x(i))y(i))x2(i)

(4)公式法

  如果我们将目标函数向量化,TXTθ=y,需要求解其中的θ

Xθ=yXTXθ=XTyθ=(XTX)1XTy

  这里需要说明一下,θ,y,X分别代表的含义。在本文中,向量都是小写字母表示,并且都是列向量,即n1维。矩阵的维度mn表示有mn列。那么上式中,我们假设m=4n=5其中包括x0,给出一组示例数据

x0x1x2x3x4y12104514546011416324023211534323031518522136178

  对应的X为,每个x(i)表示一行数据的话:

X=[12104514511416324011534323018522136]=[(x(1))T(x(2))T(x(3))T(x(4))T]

  对应的y为:

y=[460232315178]

  对应的θ为:

θ=[θ0θ1θ2θ3]

二、逻辑回归模型

1、逻辑回归模型

  上面的线性回归模型输出结果为连续值,如果我们面对的是一个分类模型,比如判断是否为垃圾邮件,或者其他的分类问题时,就不能直接使用线性回归模型了。

  逻辑回归模型是在线性回归模型上的一个演变,它通过一个逻辑函数可以将线性回归模型的输出结果转变为0或1的离散输出。

(1)逻辑函数

  即Logistic Function,也称为Sigmoid Function,如下所示,

g(z)=11+ez

  对应的函数图形为:

机器学习公式推导

  从图中可以看到,横轴是连续取值,但是纵轴上的取值范围被限制在0和1之间,Sigmoid函数可以将连续值转变为0或1的离散值。

  如果将上面的逻辑函数g(z)应用在线性回归模型的输出函数hθ(x)上,就可以得到本节所讲的逻辑回归模型。

(2)目标函数

hθ(x)=11+eθTx

  当y=1时,hθ(x)的值,可以理解为是对当前样本x,在参数θ的情况下被预测为1的概率。即

P(y=1|x,θ)=hθ(x)=11+eθTx

(3)损失函数

  在前面的线性回归模型中,损失函数如下

J(θ)=12mi=1m(hθ(x(i))y(i))2=1mi=1m12(hθ(x(i))y(i))2

  上式第二行中将12向后移动到求和项中,如果将求和项中整体定义为

Cost(hθ(x),y)=12(hθ(x(i))y(i))2

  那么线性回归的损失函数可以写成

J(θ)=1mi=1mCost(hθ(x),y)Cost(hθ(x),y)=12(hθ(x(i))y(i))2

  线性回归使用的是平方损失,如果我们直接将平方损失函数应用到逻辑回归模型中,最终得到的J(θ)可能如下图所示,

机器学习公式推导

  逻辑回归模型中使用的是对数损失,定义如下

Cost(hθ(x),y)={log(hθ(x))y=1log(1hθ(x))y=0

  可以画出对数损失函数图形来看,当y=1 并且 hθ(x)=1时,Cost=0,当y=1 并且 hθ(x)0时,Costy=0时情况类似。

  最后,将逻辑回归的对数损失函数进行融合,

Cost(hθ(x),y)=ylog(hθ(x))(1y)log(1hθ(x))

  将Cost(hθ(x),y)代入J(Θ)可以得到逻辑回归完整的损失函数如下

J(θ)=1mi=1m[y(i)log(hθ(x(i)))+(1y(i))log(1hθ(x(i)))]

  逻辑回归中使用对数损失函数来求解参数,与采用极大似然估计求参数是一致的。

  以下为对数损失函数和极大似然估计的分析过程:

  假设样本服从伯努利分布(0-1分布),则有

P(hθ(x)=y)={1pn=0pn=1

  似然函数如下:
L(θ)=i=1mP(y=1|xi,θ)yiP(y=0|xi,θ)1yi

  对数似然函数为:
lnL(θ)=i=1m[yiln(P(y=1|xi,θ)+(1yi)lnP(y=0|xi,θ)]=i=1m[yiln(P(y=1|xi,θ)+(1yi)ln(1P(y=0|xi,θ))]

  根据对数损失函数的定义
Cost(y,p(y|x)=ylnp(y|x)(1y)ln(1p(y|x))

  那么对于全体样本,损失函数如下:
Cost(y,p(y|x)=i=1m[yilnp(yi|xi)(1yi)ln(1p(yi|xi))]

  可以看到,对数损失函数与上面的极大似然函数本质上是等价的。所以,逻辑回归直接采用对数损失函数,与采用极大似然估计是一致的。

(4)梯度下降

  接下来使用梯度下降方法求解逻辑回归的最佳参数,求解损失函数

J(θ)=1mi=1m[y(i)log(hθ(x(i)))+(1y(i))log(1hθ(x(i)))]

  的最优解过程如下,
(10)repeat until convergence{θj:=θjαθJ(θ):=θjα1mi=1m(hθ(x(i))y(i))xj(i)}

  以下为求θjJ(θ)的过程,

以下为了简便,将hθ(x)记作h,那么h=11+eθTxθ求偏导数如下,

θh=xeθTx(1+eθTx)2=xeθTx1+eθTx11+eθTx=x(111+eθTx)11+eθTx=x(1h)h

Cost(hθ(x),y)=ylog(hθ(x))(1y)log(1hθ(x))
简记为
Cost(h,y)=ylog(h)(1y)log(1h)

那么
θCost(h,y)=y1hθh(1y)11h(θh)=y1hθh+(1y)11hθh=y(1h)h(1h)θh+h(1y)h(1h)θh=y+yh+hyhh(1h)θh=hyh(1h)θh=hyh(1h)xh(1h)=x(hy)

将上式代入J(θ)=1mi=1mCost(hθ(x),y),可得到
θJ(θ)=1mi=1mθCost(hθ(x),y)=1mi=1m(hθ(x(i))y(i))x(i)

那么对于梯度下降,
θj:=θjαθJ(θ):=θjα1mi=1m(hθ(x(i))y(i))xj(i)

因为α是一个常量,并且1m对于一个给定的样本也是一个常量,所以可以将αm直接写成α

三、正则化

1、过拟合

  正则化的目的是防止过拟合,当指标较多,并且训练样本较少时得到的模型可能会出现过拟合。过拟合从函数图像上的理解就是,训练得到的模型完全拟合给定样本,可能出现对于训练样本,损失值为0,而对于未在训练样本中出现过的样本,误差会很大。下图示例了过拟合,

机器学习公式推导

2、线性回归模型正则化

  图中蓝色线条为线性回归模型的过拟合情况,增加了θ3x3θ4x4两项后,曲线完全拟合给定样本。而红色曲线是训练的比较好的情况。在这里,我们如果想将θ3x3θ4x4从模型中剔除,可以将损失函数进行一定改造,如下所示,

minθ12mi=1m(hθ(x(i))y(i))2+1000θ32+1000θ42

  上面这个损失函数中,由于给了θ3θ4两个很大的系数,所以最终得到θ3θ4接近于0才能使损失函数值尽可能小。

  正则化基本上就是这个过程,会为除θ0之外每个参数值增加一个类似的系数。增加了正则化后的线性回归模型损失函数如下,

J(θ)=12m[i=1m(hθ(x(i))y(i))2+λj=1nθj2]

3、欠拟合

  假如我们给λ设置一个很大的参数,可能会出现过拟合的情况,因为这时候需要得到最小损失值,可能会将所有θ全部训练为0。可能最终得到的目标函数是hθ(x)=θ0,欠拟合的函数图形如下所示,

机器学习公式推导

4、线性回归模型梯度下降

  对正则化之后的损失函数进行梯度下降求解参数值的过程如下所示,

(11)repeat until convergence{θ0:=θ0α1mi=1m(hθ(x(i))y(i))x0(i)θj:=θj(1αλm)α1mi=1m(hθ(x(i))y(i))xj(i)}

  这里更新θj时乘以了一个系数1αλm,由于α,λ,m都是正数,所以该系数是一个大于零的分数,最终和之前不同的是在更新θ值时会逐渐缩小θ值。

5、逻辑回归模型正则化

  逻辑回归模型的正则化也是在损失函数最后增加正则项,如下所示,

J(θ)=1mi=1m[y(i)log(hθ(x(i)))+(1y(i))log(1hθ(x(i)))]+λj=1nθj2

6、逻辑回归模型梯度下降

(12)repeat until convergence{θ0:=θ0α1mi=1m(hθ(x(i))y(i))x0(i)θj:=θj(1αλm)α1mi=1m(hθ(x(i))y(i))xj(i)}

7、L1正则

8、L2正则

四、神经网络

1、神经网络结构

  神经网络模型是模拟生物神经元,神经网络中每个节点可以理解成一个变量比如xi,不同层之间的连接线可以理解成参数比如θj。神经网络结构如下所示,

机器学习公式推导

  上图中,第一层中的x1,x2,x3即前面回归模型中见到的样本各指标值,第一层也被称为输入层,最后一层的输出就是我们前面介绍到的hθ(x)的输出值,最后一层也被称为输出层。并且在实现神经网络模型时会为除输出层之外的每一层增加一个x0或$a_0^{(2)}这么一个偏置项。

  定义几个概念:

  • ai(j),表示第j层的第i个节点
  • Θ(j),表示从第j层到第j+1层的参数矩阵,图中Θ(1)是一个34的矩阵,3表示下一层(即第2层)有3个节点,4表示本层(即第1层)有4个节点(包含x0项)

      生物上的神经元之间传递的电信号,一般是高低电平,而非一个连续的值。所以在我们的神经网络中一般会应用一个**函数g(x),以后未作特殊说明,g(x)一般取Sigmoid函数。上图中神经网络结构对应的表达式如下

a1(2)=g(Θ10(1)x0+Θ11(1)x1+Θ12(1)x2+Θ13(1)x3)a2(2)=g(Θ20(1)x0+Θ21(1)x1+Θ22(1)x2+Θ23(1)x3)a3(2)=g(Θ30(1)x0+Θ31(1)x1+Θ32(1)x2+Θ33(1)x3)hΘ(x)=a1(3)=g(Θ10(2)a0(2)+Θ11(2)a1(2)+Θ12(2)a2(2)+Θ13(2)a3(2))

  需要注意的是神经网络并不是如上面示例中只有一个中间层,而是可以更多,并且每一层的**函数g(x)也可以不相同。

2、神经网络实现的逻辑功能

  这里用简单的神经网络结构示例如何实现XOR,XNOR,OR,AND,OR等逻辑操作。

(1)AND

  网络结构如下所示

机器学习公式推导

  表达式为

hΘ(x)=g(30+20x1+20x2)

(2)OR

  网络结构如下所示

机器学习公式推导

  表达式为

hΘ(x)=g(10+20x1+20x2)

(3)NOT

  网络结构如下所示

机器学习公式推导

  表达式为

hΘ(x)=g(1020x1)

(4)XNOR

  网络结构如下所示,要想实现XNOR功能,简单的模型就不能实现了。下面同时使用了AND,OR,NOT进行组合,并且构建多层网络模型才得以实现。

机器学习公式推导

3、损失函数

  神经网络的损失函数如下:

J(\Theta) = -\frac 1m \sum_{i=1}^m\sum_{k=1}^K[y_k^{(i)}log(h_\Theta(x^{(i)})_k) + (1-y_k^{(i)})log(1-(h_\Theta(x^{(i)})_k)] + \frac \lambda {2m}\sum_{l=1}^{L-1}\sum_{i=1}^{s_l}\sum_{j=1}^{s_l+1}(\Theta_{ji}^{(l)})^2\tag{1}\label{1}

  上式中,L表示神经网络的总层数,sl表示第l层中神经元的个数(不包括偏置单元)。hΘ(x)RK,hΘ(x))i=ith output,其中K表示第K个节点,那么yk(i)表示对于样本i的第k个输出值。当分析的问题为二分类问题时,k=1,当分析的问题为多分类问题时,k为对应的分类数。

4、BP算法(Backpropagation Algorithm)

  我们需要根据上一节中列举的损失函数求出全部的θ值,得到minΘJ(Θ),接下来用梯度下降求解的话,需要计算Θij(l)J(Θ)

  对于一个包含两个隐含层的神经网络结构,给定一组样本(x,y),可以依次得到每一层相关数据:

\begin{split}&a^{(1)}=x \\&z^{(2)}=\Theta^{(1)}a^{(1)} \\&a^{(2)}=g(z^{(2)}) \ (add a_0^{(2)})\\&z^{(3)}=\Theta^{(2)}a^{(2)}\\&a^{(3)}=g(z^{(3)})\ (add a_0^{(3)})\\&z^{(4)}=\Theta^{(3)}a^{(3)}\\&a^{(4)}=h_\Theta(x)=g(z^{(4)})\end{split}\tag{2}\label{2}

  根据公式(1),对于二分类的单个样本,损失函数如下

J(\Theta) = - [ylog(h_\Theta(x)) + (1-y)log(1-(h_\Theta(x))] + \lambda\sum_{l=1}^{L-1}\sum_{i=1}^{s_l}\sum_{j=1}^{s_l+1}(\Theta_{ji}^{(l)})^2 \tag{3}\label{3}

  以下为该公式的推导过程

计算Θ(3)的梯度,结合公式(2)

\frac {\partial J(\Theta)}{\partial \Theta^{(3)}}=\frac {\partial J(\Theta)}{\partial a^{(4)}}*\frac {\partial a^{(4)}}{\partial z^{(4)}} * \frac {\partial z^{(4)}}{\partial \Theta^{(3)}} \tag{4}\label{4}

如果将式(4)中等号右边前两项定义为δ(4),则有
\delta^{(4)}=\frac {\partial}{\partial z^{(4)}}J(\Theta)=\frac {\partial J(\Theta)}{\partial a^{(4)}}*\frac {\partial a^{(4)}}{\partial z^{(4)}}\tag{5}\label{5}

结合(3)(5)并且a(4)=hΘ(x)=g(z(4))得到如下推导过程:
g(z(4))=11+ez(4)g(z(4))=ez(4)(1+ez(4))2=g(z(4))(1g(z(4)))

\begin{split}\delta^{(4)}&=\frac {\partial}{\partial z^{(4)}}J(\Theta)\\&=\frac {\partial J(\Theta)}{\partial a^{(4)}}*\frac {\partial a^{(4)}}{\partial z^{(4)}}\\&=-[y\frac 1{h_\Theta(x)}*h_\Theta'(x)+(1-y)\frac 1{1-h_\Theta(x)}*(-(h_\Theta'(x))]\\&=-[y\frac 1{g(z^{(4)})}*g'(z^{(4)})+(1-y)\frac 1{1-g(z^{(4)})}*(-g'(z^{(4)}))]\\&=-[y(1-g(z^{(4)})) + (y-1)g(z^{(4)})]\\&=g(z^{(4)})-y\\&=a^{(4)}-y\end{split}\tag{6}\label{6}

接下来求J(Θ)Θ(2)J(Θ)Θ(1),由式(2)可得,
\frac {\partial J(\Theta)}{\partial \Theta^{(2)}}=\frac {\partial J(\Theta)}{\partial a^{(4)} }\frac {\partial a^{(4)}}{\partial z^{(4)}}\frac {\partial z^{(4)}}{\partial a^{(3)}}\frac {\partial a^{(3)}}{\partial z^{(3)}}\frac {\partial z^{(3)}}{\partial \Theta^{(2)}}\tag{7}\label{7}

δ(3)=z(3)J(Θ)=J(Θ)a(4)a(4)z(4)z(4)a(3)a(3)z(3),结合(5)则有
\delta^{(3)} = \frac{\partial }{\partial z^{(3)}}J(\Theta)=\delta^{(4)}*\frac {\partial z^{(4)}}{\partial a^{(3)}}\frac {\partial a^{(3)}}{\partial z^{(3)}}=\delta^{(4)}*\Theta^{(3)}*g'(z^{(3)})\tag{8}\label{8}

\frac {\partial J(\Theta)}{\partial \Theta^{(1)}}=\frac {\partial J(\Theta)}{\partial a^{(4)} }\frac {\partial a^{(4)}}{\partial z^{(4)}}\frac {\partial z^{(4)}}{\partial a^{(3)}}\frac {\partial a^{(3)}}{\partial z^{(3)}}\frac {\partial z^{(3)}}{\partial a^{(2)}}\frac {\partial a^{(2)}}{\partial z^{(2)}}\frac {\partial z^{(2)}}{\partial \Theta^{(1)}}\tag{9}\label{9}

δ(2)=z(2)J(Θ)=J(Θ)a(4)a(4)z(4)z(4)a(3)a(3)z(3)z(3)a(2)a(2)z(2)
结合(8)
\delta^{(2)}=\frac{\partial }{\partial z^{(2)}}J(\Theta)=\delta^{(3)}*\frac {\partial z^{(3)}}{\partial a^{(2)}}\frac {\partial a^{(2)}}{\partial z^{(2)}}=\delta^{(3)}*\Theta^{(2)}*g'(z^{(2)})\tag{10}\label{10}

结合式(5)(8)(10)可以提炼出一个式子,
\delta^{(l)}=\frac{\partial }{\partial z^{(l)}}J(\Theta)\tag{11}\label{11}

正是有了式(11)的存在,当反向BP算法反向计算时,会根据保存的上一步的计算结果,进行一些简单计算得到下一层。这样在神经网络很复杂的时候,可以避免大量重复计算。
(4)中最后一项z(4)Θ(3)=a(3),所以
\frac {\partial J(\Theta)}{\partial \Theta^{(3)}}=\delta^{(4)}*a^{(3)}=(a^{(4)}-y)a^{(3)}\tag{12}\label{12}

(7)中最后一项z(3)Θ(2)=a(2),所以
\frac {\partial J(\Theta)}{\partial \Theta^{(2)}}=\delta^{(3)} * a^{(2)}=\delta^{(4)}*\Theta^{(3)}*g'(z^{(3)})*a^{(2)}\tag{13}\label{13}

(9)中最后一项z(2)Θ(1)=a(1),所以
(14)J(Θ)Θ(1)=δ(2)a(1)=δ(3)Θ(2)g(z(2))a(1)

  最后对于上面的四层神经网络模型,结合公式推导过程,可以得到PPT中如下公式,δj(l)可以理解为第l层第j个节点的误差。

δj(4)=aj(4)yjδj(3)=(Θ(3))Tδ(4).g(z(3))δj(2)=(Θ(2))Tδ(3).g(z(2))