共轭梯度法在SVM原问题参数优化中的应用

1. 共轭性

关于共轭先了解一下其基本性质, 共轭性的定义为: 设\(A \in {R^{n \times n}}\)是对称正定矩阵. 称\({{\bf{p}}_1},{{\bf{p}}_2}\)是 -共轭的, 是指 \({\bf{p}}_1^TA{{\bf{p}}_2}{\rm{ = }}0,\begin{array}{*{20}{c}}
{}
\end{array}{\bf{p}}_1^TA{{\bf{p}}_1} > 0,\begin{array}{*{20}{c}}
{}
\end{array}{\bf{p}}_2^TA{{\bf{p}}_2} > 0\)

那么它的性质有:

1). 设有\({{\bf{p}}_1},{{\bf{p}}_2},…,{{\bf{p}}_m}(m < n)\)是彼此共轭的\(n\)维向量, 即

\[{\bf{p}}_i^TA{{\bf{p}}_j}\left\{ {\begin{array}{*{20}{c}}
{ = 0,\begin{array}{*{20}{c}}
{}
\end{array}i \ne j,}\\
{ > 0,\begin{array}{*{20}{c}}
{}
\end{array}i = j,}
\end{array}\begin{array}{*{20}{c}}
{}&{i,j = 0,1,...,m}
\end{array}} \right.\]

则\({{\bf{p}}_1},{{\bf{p}}_2},…,{{\bf{p}}_m}\)一定是线性无关的.

2). 设向量\({{\bf{g}}_1},{{\bf{g}}_2},…,{{\bf{g}}_m}\)是线性无关的向量组, 则可通过它们的线性组合得到一组向量\({{\bf{p}}_1},{{\bf{p}}_2},…,{{\bf{p}}_m}\), 而\({{\bf{p}}_1},{{\bf{p}}_2},…,{{\bf{p}}_m}\)是两两共轭的.

具体的证明, 和很多其他的性质这里我们都做略过.

2. 共轭梯度下降法

之前已经介绍过牛顿法, 它从梯度的变化趋势来改进搜索方向, 使它能更更好趋向最优方向. 但在牛顿法中计算\({{\bf{D}}^{{\rm{ – }}1}}\)工作量很大, 而且要求\({\bf{D}}\)非奇异. 能否使算法不要计算\({{\bf{D}}^{{\rm{ – }}1}}\)而又能改善梯度法的收敛性能呢? 共轭梯度法就是基于这种考虑的算法.

共轭梯度法最初由Hesteness和Stiefel于1952年为求解线性方程组而提出的. 后来, 人们把这种方法用于求解无约束最优化问题, 使之成为一种重要的最优化方法.

Fletcher-Reeves共轭梯度法, 简称FR法.

共轭梯度法的基本思想是把共轭性与最速下降方法相结合, 利用已知点处的梯度构造一组共轭方向, 并沿这组方向进行搜素, 求出目标函数的极小点. 根据共轭方向基本性质,这种方法具有二次终止性. 它也是一种改进搜索方向的方法, 把前一点的梯度乘以适当的系数 , 加到该点的梯度上, 得到新的搜索方向. 因此, 可以说共轭梯度法是过去的梯度和现在某点的梯度的信息综合利用. 用其线性组合来构造更好的搜索方向. 新的搜索方向\({{\bf{s}}^{(1)}},{{\bf{s}}^{(2)}},…,{{\bf{s}}^{(n)}} \in {E^n}\)是满足共轭性质的, 即对于某个\(n \times n\)正定阵\({\bf{C}}\)满足
\[{{\bf{s}}^{{{(i)}^T}}}{\bf{C}}{{\bf{s}}^{(j)}}\left\{ {\begin{array}{*{20}{c}}
{ = 0,\begin{array}{*{20}{c}}
{}
\end{array}i \ne j,}\\
{ > 0,\begin{array}{*{20}{c}}
{}
\end{array}i = j,}
\end{array}\begin{array}{*{20}{c}}
{}&{i,j = 0,1,...,m}
\end{array}} \right.\]

正定阵\({\bf{C}}\)可以是\(J({\bf{a}})\)的二次偏导数矩阵\({\bf{D}}\). 在特殊情况下\({\bf{C}}{\rm{ = }}{\bf{I}}\), 则\({{\bf{s}}^{{{(i)}^T}}}{{\bf{s}}^{(j)}}{\rm{ = }}0\)表示两个搜索方向是正交的.

与牛顿法类似, 迭代公式为: \({{\bf{a}}_{k + 1}} = {{\bf{a}}_k} + \rho _k^ * {{\bf{\hat s}}_k}\), 其中搜索方向 是一组共轭向量, 且

\[\left\{ {\begin{array}{*{20}{c}}
{{{\bf{s}}_k}{\rm{ = - }}\nabla J({{\bf{a}}_k}) + {v_{k - 1}}{{\bf{s}}_{k - 1}}}\\
{{v_{k - 1}} = \frac{{\nabla {J^T}({{\bf{a}}_k})\nabla J({{\bf{a}}_k})}}{{\nabla {J^T}({{\bf{a}}_{k - 1}})\nabla J({{\bf{a}}_{k - 1}})}} = \frac{{{{\left\| {\nabla J({{\bf{a}}_k})} \right\|}^2}}}{{{{\left\| {\nabla J({{\bf{a}}_{k - 1}})} \right\|}^2}}}}
\end{array}} \right.\]

OK, 这就有了搜索方向和迭代公式. 还差搜索方向的系数, 即最佳步长\(\rho _{}^ * \). 仍可采用和之前牛顿法一样的方法, 一维线性搜索得到. 而有些情况不需要求最佳步长, 只要人工选定一个较优值即可.

如果准则函数是\(n\)维二次函数, 则利用这种算法, 只要迭代\(n\)次就能得到最优解. 但实际计算\({{\bf{s}}_k}\)时, 由于舍入误差的影响, 常需要进行\(n\)次以上的计算.

3. matlab代码实现

由于共轭梯度法很简单, 这里不再对svm进行公式推导而是直接给出共轭梯度的调用函数, 需要和之前牛顿法中的完整代码结合才能够运行.

function  [w, obj] = primal_svm_linear_cg(Y,lambda,opt)
% -----------------------------------------------------
% Train a linear SVM using nonlinear conjugate gradient
% -----------------------------------------------------
  global X;
  [n,d] = size(X);%n为样本个数,d为样本维数
  w = zeros(d+1,1); % The last component of w is b.
  iter = 0;
  out = ones(n,1); % Vector containing 1-Y.*(X*w)
  go = [X'*Y; sum(Y)];  % -gradient at w=0
  s = go; % The first search direction is given by the gradient
  while 1
    iter = iter + 1;
    if iter > opt.cg_it * min(n,d)
      warning(sprintf(['Maximum number of CG iterations reached. ' ...
                       'Try larger lambda']));
      break;
    end;
    % Do an exact line search
    [t,out] = line_search_linear(w,s,out,Y,lambda);
    w = w + t*s;
    % Compute the new gradient
    [obj, gn] = obj_fun_linear(w,Y,lambda,out); gn=-gn;
    fprintf('Iter = %d, Obj = %f, Norm of grad = %.3f     \n',iter,obj,norm(gn));
    % Stop when the relative decrease in the objective function is small
    if t*s'*go < opt.prec*obj, break; end;
    % Flecher-Reeves update. Change 0 in 1 for Polack-Ribiere
    be = (gn'*gn - 0*gn'*go) / (go'*go);
    s = be*s+gn;
    go = gn;
  end;  

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>