读者背景知识：线性回归、逻辑回归、SVM、最大熵模型、拉格朗日乘子法

说在前面的废话：

前面已经讲清楚了最大似然估计(MLE)与EM演算法的关系，按照计划，是要讨论EM演算法求解优化问题的思想的

不过细想，优化目标求解问题其实就那么几种，而EM演算法只不过是其中某种大类求解策略下的一种具体实现而已，一个是道，一个是术，道的高度是大于术的，讲清楚了道，则一通百通，术便不再是问题 所以，这一节，我就给大家理一理那些优化目标求解问题中的几大求解策略

1. 两种优化目标：有约束与无约束

首先，大家要知道，优化目标按照是否有额外的约束条件可以分为以下两种情况：

  • 无约束的最优化问题

这种情况是最常见的，也是比较容易求解的优化问题

比如：

（1）线性回归的损失函数最小化目标（又称为最小二乘法）：

min_w frac 12 sum_{i=1}^m(h(x_i)-y_i)^2

如果再在原始最小二乘法损失函数的基础上加上正则化项，又变成了新的优化目标：

min_w frac 12 sum_{i=1}^m(h(x_i)-y_i)^2+lambdasum_{j=1}^n|w_i|quad LASSO

min_w frac 12 sum_{i=1}^m(h(x_i)-y_i)^2+lambdasum_{j=1}^n|w_i|_2^2quad ext{岭回归}

其中， lambda 是正则化项的系数，用于权衡模型结构风险与经验风险的比重，可以看到LASS回归于岭回归的差别仅仅在于使用的正则化项而已，LASS使用的是L1正则化，岭回归使用的是L2正则化

（2）逻辑回归的最大对数似然估计：

egin{aligned} &max_w logprod_{i=1}^m P(y_i mid x_i) \ &= logprod_{i=1}^m P(y_i=1 mid x_i)^{y_i}P(y_i=0 mid x_i)^{1-y_i} \ &= sum_{i=1}^m y_ilog P(y_i=1 mid x_i)+(1-y_i)log(1-P(y_i=1 mid x_i)) end{aligned}

其中，

h(x)=P(y=1mid x)=frac{1}{1+e^{wx}}\ P(y=0mid x)=1-P(y=1mid x)=frac{e^{wx}}{1+e^{wx}}

则，优化目标可以写成：

max_w sum_{i=1}^m y_ilog h(x_i)+(1-y_i)log(1-h(x_i))

  • 有约束的最优化问题

这一类优化问题除了有目标函数项，还有其他约束项

比如：

（1）支持向量机的最大化几何间隔 (max margin)

它的优化目标为最大化几何间隔，即

max_w r=frac {hat r}{||W||}

其中， r 是样本集合在样本空间的几何间隔（几何间隔：样本点到分界面的垂直距离）， hat r 是函数间隔，几何间隔与函数间隔满足 r=hat r/||W|| ， W 是分界超平面的系数向量，SVM的目标就是要让上图中的r最大化

但是，这个优化目标还要满足额外的约束条件：

r^{(i)}ge r

其中， r^{(i)} 表示每个样本各自的几何间隔，很显然几何的几何间隔肯定要大于等于每个样本各自的几何间隔

另外，根据几何间隔的定义，可以把上面的约束条件写成：

y_ifrac{W^Tx_i}{||W||}ge frac{hat r}{||W||}quad Rightarrow y_i(W^Tx_i)ge hat r

则，完整的优化目标可以写成：

max_W frac{hat r}{||W||} \ s.t. quad y_i(W^Tx_i)ge hat r quad i=1,2,...,m

为了简化优化目标，我们限定 hat r=1 ，则完整的优化目标可以写成：

max_W frac{1}{||W||} \ s.t. quad y_i(W^Tx_i)ge 1 quad i=1,2,...,m

而我们习惯将优化目标写成最小化形式，所以，可以进一步改写成：

min_W frac 12 ||W|| \ s.t. quad 1-y_i(W^Tx_i)le 0 quad i=1,2,...,m

（2）最大熵模型的极大化模型的熵

对于给定的训练集 T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)} 以及特征函数 f_i(x,y),, i=1,2,...,n ，最大熵模型的学习等价于约束最优化问题：

max_{Pin C} H(P)=-sum_{x,y} hat P(x)P(ymid x)log P(y mid x) \ s.t. quad E_P(f_i)=E_{hat P}(f_i), , i=1,2,...,n \ sum_y P(y mid x)=1

其中， C 是满足约束条件的模型空间， hat P(x) 是训练样本的边际分布 P(x) 的经验分布， E_{hat P}(f) 是经验分布 hat P(X,Y) 的期望值， E_P(f) 是模型 P(y mid x) 与经验分布 hat P(X,Y) 的期望值，即

E_{hat P}(f)=sum_{x,y} hat P(x,y)f(x,y)

E_P(f)=sum_{x,y} hat P(x)P(y mid x)f(x,y)

对于上面谈到的两类优化目标，第一类无约束优化目标，它可以之间使用我们常用的最优化问题的求解方法（具体内容在后面展开）进行解决，而第二类，即有约束优化目标，则不能进行直接求解，需要先将它转化为无约束优化目标，然后再用求解无约束优化目标的方法进行求解

那么，如何将有约束优化目标转化为无约束优化目标呢？

需要使用拉格朗日乘子法

对于以下一般形式的带约束的优化问题（即有等式约束，又有不等式约束）

min_w f(w) \ s.t. quad g_i(w) le 0, , i=1,2,...,k \ h_i(w)=0, , i=1,2,...,l 引入拉格朗日乘子 alpha_1,alpha_2,...,alpha_k,eta_1,eta_2,...,eta_l ，定义拉格朗日函数 L(w,alpha,eta) ： L(w,alpha,eta)=f(w)+sum_{i=1}^k alpha_i g_i(w) + sum_{i=1}^l eta_i h_i(w) 则，在引入拉格朗日乘子法后，原先有约束优化问题就转化成了下面的无约束优化问题：

min_w max_{alpha>0,eta} L(w,alpha,eta)

至于为什么 f(w) 会等于 max_{alpha>0,eta} L(w,alpha,eta) ，由于文章篇幅有限，这里就不展开证明了

2. 两种求解策略

读者知识背景：线性代数

下面来讨论一下怎么求解优化问题

其实，任它优化问题千变万化，求解起来无非就是两种策略：

（1）标准方程法 (Normal equation method)

（2）迭代法 (iteration)
  • 标准方程法

它的基本思想其实非常简单，即假设目标函数是一个凸函数，那么它在定义域上的最优解一般来说，是在其极值点取到，那么我们就可以对目标函数求偏导数，且令各个偏导数的值为0，从而找出极值点，也就获得了最优解

比如，对于线性回归问题，其优化目标（不进行正则化）为：

min_w frac 12 sum_{i=1}^m(h(x_i)-y_i)^2

即

min_w frac 12 sum_{i=1}^m(W^Tx_i-y_i)^2

记

f(W)=frac 12 sum_{i=1}^m(W^Tx_i-y_i)^2

为了方便后面的推导，用向量化形式来表示：

f(W)=frac 12 [XW-Y]^T[XW-Y]

其中，

W=(w_0,w_1,...,w_n)^T

X= egin{bmatrix} -x_1- \ -x_2- \ ... \ -x_m- end{bmatrix}

Y=(y_1,y_2,...,y_m)^T

则对模型参数的每一项求偏导数，得到

egin{aligned} Delta_W f(W) &= frac 12 Delta_W [XW-Y]^T[XW-Y] \ &= frac 12 Delta_W (W^TX^TXW - W^TX^TY - Y^TXW+Y^TY) \ &= frac 12 Delta_W tr(W^TX^TXW - W^TX^TY - Y^TXW+Y^TY) \ &= frac 12 Delta_W tr(WW^TX^TX - Y^TWX - Y^TXW) end{aligned}

而

Delta_W tr(WW^TX^TX)=X^TXWI + X^TXWI \ Delta_W tr(Y^TXW)=X^TY

因此

Delta_W f(W)=frac 12 [X^TXW + X^TXW - X^TY- X^TY]=X^TXW-X^TY

所以，

X^TXW=X^TY Rightarrow W=(X^TX)^{-1}Y

上面的推导过程，涉及到比较深的线性代数的知识，尤其是关于矩阵的迹相关的知识，看不懂没有关系，上面讲这么多只是想说明，可以通过对目标函数求导并让导数为0来得到解

  • 迭代法

像我们最熟悉的梯度下降法以及牛顿法或拟牛顿法都属于迭代求解的方法，包括我们下一节要进一步讨论的EM演算法也属于迭代法

它们的基本思想为：

与标准方程法一步到位获得最优解的策略不同，迭代法先找一个随机解做为起始的当前解，然后对当前解进行迭代更新，保证每一次迭代后得到的新解朝著最优化的方向前进，即

若最优化目标为：

min_W f(W) 则找到一种解的更新方法，实现 W o W+delta ，保证 f(W_{i+1})le f(W_i) 不断迭代，直到目标函数不再朝著优化目标改变为止，即解已经收敛了，此时的解W即为最优解不过迭代法不能保证收敛到的解是全局最优，它很可能落到局部最优位置

区别具体的迭代法的，是它们各自所采用的参数更新的方法

比如梯度下降法的参数更新的方法为：

W o W - alpha Delta f(W)

参考资料：

(1) 周志华《机器学习》

(2) 李航《统计学习方法》

(3) 吴军《数学之美》

(4) 兰艳艳《SVM演算法》，国科大《模式识别与机器学习》课程

(5) 吴恩达《斯坦福大学·机器学习》公开课

(6) 机械工业出版社《机器学习实战：基于Scikit-Learn和TensorFlow》


推荐阅读：
相关文章