Hulu机器学习问题与解答系列 | 十八：SVM – 核函数与松弛变量

嗨，又见面了~ 你可以进入公众号，点击菜单栏的“机器学习”回顾本系列的全部内容，并留言与作者交流。

今天的内容是

【SVM – 核函数与松弛变量】

场景描述

当我们在SVM中处理线性不可分的数据时，核函数可以对数据进行映射，从而使得原问题在某种度量下具有更为可分的相似度，而通过引入松弛变量，我们可以放弃一些离群点的精确分类来使分类平面不受太大的影响。将这两种技术与SVM结合起来，正是SVM分类器简洁而强大的原因之一。

问题描述

1. 一个使用高斯核

   
   

   训练的SVM（Support Vector Machine）中，试证明若给定训练集中不存在两个点在同一位置，则存在一组参数{α₁, ... α_m, b}以及参数γ使得该SVM的训练误差为0。

2. 若我们使用问题1中得到的参数γ训练一个不加入松弛变量的SVM，是否能保证得到的SVM，仍有训练误差为0的结果，试说明你的观点。

3. 若我们使用SMO（Sequential Minimal Optimization）算法来训练一个带有松弛变量的SVM，并且惩罚因子C为任意事先不知道的常数，我们是否仍能得到训练误差为0的结果，试说明你的观点。

先验知识：SVM训练过程、核函数、SMO算法

解答与分析

1.

根据SVM的原理，我们可以将SVM的预测公式可写为下式：

其中{(x⁽¹⁾, y⁽¹⁾), …, (x^(m), y^(m))}为训练样本，而{α₁, …, α_m, b}以及高斯核参数γ则为训练样本的参数，根据题意我们可以得到对于任意的i≠j 我们有‖x⁽ⁱ⁾﹣x^(j)‖≥ε，我们可以直接对任意i，取α_i＝1，b＝0，则有

将任意x^(j)代入则有

注意到y⁽ⁱ⁾∈{1, ﹣1}

由题意知‖x⁽ⁱ⁾﹣x^(j)‖≥ε，取γ＝ε/㏒^1/2m

故有

可知对于任意x^(j)，预测结果与样本的距离不超过1，则训练误差为0。

2.

我们能得到训练误差为0的分类器，我们仅需要证明解存在即可。考虑SVM推导中的限制y⁽ⁱ⁾(w^Tx⁽ⁱ⁾﹢b)≥1，与上一问相同，我们取b＝0，那么则有y⁽ⁱ⁾·f(x^(j))＞0，由上问，我们有

所以一个可行解在将所有α_i取到足够大时（这里改变α_i的取值并不会影响上一问的结论），我们可得到y⁽ⁱ⁾(w^Tx⁽ⁱ⁾﹢b)≥1，则得到一个可行解，那么最优解的训练误差仍为0。

3.

我们的分类器并不一定能得到0训练误差，因为我们的优化目标改变了，并不再是训练误差最小，考虑我们优化的结果实际上包含两项

可知当我们的参数C选取较小的值时，我们就可以得出后一正则项将占据优化的较大比重，那么一个带有训练误差，但是参数较小的点将成为更优的结果，例如当C取0时，w也可取0即可达到优化目标，但是显然这样我们的训练误差不一定能达到0。

下一题预告

【主题模型】

场景描述

基于Bag-Of-Words（或N-gram）的文本表示模型有一个明显的缺陷，就是无法识别出不同的词（或词组）具有相同主题的情况。我们需要一种技术能够将具有相同主题的词（或词组）映射到同一维度上去，于是产生了主题模型(Topic Model)。主题模型是一种特殊的概率图模型。想象一下我们如何判定两个不同的词具有相同的主题呢？这两个词可能有更高的概率出现在同一主题的文档中；换句话说，给定某一主题，这两个词的产生概率都是比较高的，而另一些不太相关的词产生的概率则是较低的。假设有K个主题，我们可以把任意文章表示成一个K维的主题向量，其中向量的每一维代表一个主题，权重代表这篇文章属于该主题的概率。主题模型所解决的事情，就是从语料库中发现有代表性的主题（得到每个主题上面词的分布），并且计算出每篇文章对应着哪些主题。这样具有相似主题的文章拥有相似的主题向量表示，从而能够更好地表示文章的语义，提高文本分类、信息检索等应用的效果。

问题描述

1. 常见的主题模型有哪些？试介绍其原理。

2. 如何确定LDA模型中的主题个数？

欢迎留言提问或探讨

关注“Hulu”微信公众号

点击菜单栏“机器学习”获得更多系列文章