支持向量机(SVM)之Mercer定理与损失函数----5

任何时代，大部分人的研究所得都不过是基于前人的研究成果，前人所做的是开创性工作，而这往往是最艰难最有价值的，他们被称为真正的先驱。牛顿也曾说过，他不过是站在巨人的肩上。你，我，更是如此。

本次文章的大纲：

1----线性学习器之感知机

2----非线性学习器之Mercer定理

3----常用损失函数分析

1----线性学习器

1-1----感知机

这个感知机算法是1956 年提出的，年代久远，依然影响着当今，当然，可以肯定的是，此算法亦非最优，后续会有更详尽阐述。不过，有一点，你必须清楚，这个算法是为了干嘛的：不断的训练试错以期寻找一个合适的超平面（是的，就这么简单）。

下面，举个例子。如下图所示，凭我们的直觉可以看出，图中的红线是最优超平面，蓝线则是根据感知机算法在不断的训练中，最终，若蓝线能通过不断的训练移动到红线位置上，则代表训练成功。

既然需要通过不断的训练以让蓝线最终成为最优分类超平面，那么，到底需要训练多少次呢？Novikoff 定理告诉我们当间隔是正的时候感知机算法会在有限次数的迭代中收敛，也就是说Novikoff 定理证明了感知机算法的收敛性，即能得到一个界，不至于无穷循环下去。

感知机

定理 Novikoff 定理

如果分类超平面存在，仅需在序列S 上迭代几次，在界为(2R/r)^2的错误次数下就可以找到分类超平面，算法停止。这里R = max1≤i≤l ∥xi∥，r 为扩充间隔。

同时有一点得注意：感知机算法虽然可以通过简单迭代对线性可分数据生成正确分类的超平面，但不是最优效果，那怎样才能得到最优效果呢，就是上文中第一部分所讲的寻找最大分类间隔超平面。

感知机分类的伪代码形式

2---非线性学习器

2-1----Mercer定理

定理 Mercer 定理

如果函数 是Rn × Rn → R 上的映射。那么如果 是一个有效核函数（也称为Mercer 核函数），那么当且仅当对于训练样例{x1; x2; ..... ; xn}，其相应的核函数矩阵是对称半正定的。

要理解这个Mercer 定理，先要了解什么是半正定矩阵，要了解什么是半正定矩阵，先得知道什么是正定矩阵.请查阅相关资料。

3----常用损失函数

有这么一句话“支持向量机（SVM）是90 年代中期发展起来的基于统计学习理论的一种机器学习方法，通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。”但初次看到的读者可能并不了解什么是结构化风险，什么又是经验风险。要了解这两个所谓的“风险”，还得又从监督学习说起。

监督学习实际上就是一个经验风险或者结构风险函数的最优化问题。风险函数度量平均意义下模型预测的好坏，模型每一次预测的好坏用损失函数来度量。它从假设空间F 中选择模型f 作为决策函数，对于给定的输入X，由f(X) 给出相应的输出Y ，这个输出的预测值f(X) 与真实值Y 可能一致也可能不一致，用一个损失函数来度量预测错误的程度。损失函数记为L(Y, f(X))。

常用的损失函数有以下几种（以下基本引用自《统计学习方法》）：

给定一个训练数据集

模型f(X) 关于训练数据集的平均损失成为经验风险，如下：

关于如何选择模型，监督学习有两种策略：经验风险最小化和结构风险最小化。

经验风险最小化策略认为，经验风险最小的模型就是最优的模型，则按照经验风险最小化求最优模型就是求解如下最优化问题：

当样本容量很小时，经验风险最小化的策略容易产生过拟合的现象。结构风险最小化可以防止过拟合。结构风险是在经验风险的基础上加上表示模型复杂度的正则化项或罚项，结构风险定义如下：

其中J(f) 为模型的复杂度，模型f 越复杂，J(f) 值就越大，模型越简单，J(f) 就越小，也就是说J(f) 是对复杂模型的惩罚。 ≥ 0 是系数，用以权衡经验风险和模型复杂度。结构风险最小化的策略认为结构风险最小的模型是最优的模型，所以求最优的模型就是求解下面的优化问题：

这样，监督学习问题就变成了经验风险或结构风险函数的最优化问题。

如此，SVM 有第二种理解，即最优化+ 损失最小：可从损失函数和优化算法角度看SVM、Boosting、LR 等算法，可能会有不同收获。 欢迎转载