多示例学习（Multiple Instance Learning）

在DPM中提到的latent SVM 实际上就是MILSVM的变种。

我们考虑这样一种训练数据，这个数据是有标记的，标记只有两个类别，正和负。但这一次标记的目标不是一个样本，而是一个数据包（bag)。某一个或者几个数据合在一起叫做一个bag，每个bag有自己的标记。当一个bag的标记为负时，这个bag里面所有样本的标记都是负的。当一个bag的标记为正时，这个bag里面至少有一个样本的标记为正。 我们的目标是学习得到一个分类器，使得对新输入的样本，可以给出它的正负标记。这样的一类问题就是多示例问题。

实际问题： 检测问题，标记训练图片样本的时候需要给出一个矩形框指明目标的位置，有可能标的不够准确，导致不同的样本之间对不齐，这时候可以将标记的矩形框做一些局部扰动得到一些新的矩形框，将它们一起看成一个bag，其中总有一个是最佳的正样本，也就是标记为正。而取一张没有目标的图片，作为负样本包：无论在里面怎么截取图片，都是负样本。

求解方法

关于多示例问题怎么求解，假如说所有的样本标记都已经知道了，那就是一个监督学习的问题了，用SVM，adaboost之类的都可以做。现在的困难是，有很多样本的标记我们不知道。对于负样本包来说就无所谓了，里面每个样本那都是负标记，这个是明确的。问题出在正样本包上面，每个正样本包里只能保证有一个是正样本，其他的是正是负就不知道了，关键是到底是哪个样本是正的呢？这个也是不清楚的。

解决这个问题的方法其实挺直接的：迭代优化（alternative optimization)。也就是说，我们先假设已经知道了所有样本的标记，那么就可以通过某种监督学习的方法得到一个分类模型，通过这个模型我们可以对每个训练样本进行预测，然后更新它们的标记，我们又可以拿这一次新得到的标记重新训练分类模型了。所以整个优化过程分为两部分：监督学习，标记更新。

这里还有一些地方需要注意：

第一点， 训练监督学习的模型的时候，只从正样本包里挑选被预测的“最像正确”(也就是分类得分最高)的那一个，正样本包里面其他的样本，不管预测出来是正的还是负的都不要了。这是因为，其实多示例的问题也可以描述为，正样本包里面“最正确”的一个样本标记是正的，跟其他样本无关。所以，这种选择策略恰恰是符合问题定义的。

第二点，如果负样本足够多的话，可以只挑选每个负样本包里面被预测“最像正确”的一个样本作为负样本进行训练，这样子的负样本也叫做hard sample或者most violated sample。实践上来说，它们对于模型快速收敛是最有效的。

关于非监督学习和监督学习

2.很多时候，不是每个训练样本都有标记，而是只有一部分被标记，而另一部分只有数据本身，标记缺失掉了。这时候需要将没有标记的数据和有标记的数据结合起来进行机器学习，这就是半监督学习。

3.又有的时候，甚至所有的样本都没有标记，这就是非监督学习。但是实际上，非监督学习没法进行目标明确的分类、拟合任务，只能做一些分析性的任务，比如说聚类，PCA，字典学习等等。

关于SVM的核函数理解

来看个核函数的例子。如下图所示的两类数据，分别分布为两个圆圈的形状，这样的数据本身就是线性不可分的，此时咱们该如何把这两类数据分开呢(下文将会有一个相应的三维空间图)？



事实上，上图所述的这个数据集，是用两个半径不同的圆圈加上了少量的噪音生成得到的，所以，一个理想的分界应该是一个“圆圈”而不是一条线（超平面）。如果用X1和X2来表示这个二维平面的两个坐标的话，我们知道一条二次曲线（圆圈是二次曲线的一种特殊情况）的方程可以写作这样的形式：



注意上面的形式，如果我们构造另外一个五维的空间，其中五个坐标的值分别为 X1,X1X2 ,X2 ,X1^2 ,X2^2 ，那么显然，上面的方程在新的坐标系下可以写作：





所以原来的方程



可以写成



而其中的可以通过求解如下 dual 问题而得到的：



这样一来问题就解决了吗？似乎是的：拿到非线性数据，就找一个映射 ，然后一股脑把原来的数据映射到新空间中，再做线性 SVM 即可。不过事实上没有这么简单！其实刚才的方法稍想一下就会发现有问题：在最初的例子里，我们对一个二维空间做映射，选择的新空间是原始空间的所有一阶和二阶的组合，得到了五个维度；如果原始空间是三维，那么我们会得到 19 维的新空间，这个数目是呈爆炸性增长的，这给 的计算带来了非常大的困难，而且如果遇到无穷维的情况，就根本无从计算了。所以就需要 Kernel 出马了。

五维空间映射的内积为