Predicting Diverse Subsets Using Structural SVMs
这篇论文主要讲述了如何使用Structural SVMs来进行推测拥有多样性的子集。
首先我们可能要问什么叫做多样性呢？作者给出了这样一个问题背景，当我们检索一个词" Jaguar"，其可能代表着多个意思，如，动物，车，等。此时，如果我们只将某个单一意思的检索结果返回给用户的话，那么这样的用户体验是十分不好的。因而，我们有必要在所有检索结果中，再次寻找一个子集，使其能够包含大量不同种类含义的检索结果。这也就是这篇论文所说的多样性。
在这篇论文中，作者指出多样性是由在labeled data上的subtopic 的覆盖情况来衡量。
接下来进入正文
首先给出学习问题的描述：
对于一个检索，假设我们被给出了一个候选文档的集合
。定义
，其中
包含了文档
所覆盖的subtopics。我们的目标就是从候选文档集合中挑选一个拥有K个元素的子集
，使其拥有最大的topic覆盖率。如果topic sets 
已知，使用greedy subset selection 算法能够选择y。现在我们假设有
形式的训练样本，在缺少的情况下来找到一个预测的函数。这在本质上就是一个学习问题。
接下来我们要看看如何进行建模的。
让
代表候选集合
的空间，
代表topic sets
的空间，并且
代表预测集合
的空间。根据标准的机器学习过程，我们可以将我们的问题构建成学习一个假设函数（hypothesis function）
，其当给定
时预测一个
。
定义loss function: 
，其用来衡量选择
的惩罚。在这里，作者将代价函数定义为distinct subtopics 在中却不在中的比例。
定义discriminant function
，来评价predicting y 能够拟合x的程度：
这个特征表征
必须在high quality 和 low quality之间产生有意义的差异。
我们可以用这个 discriminant function 来实现预测y：
看到这里也许有人要问，既然有了预测式子了，我们通过训练数据不是就可以学习得到参数w了吗？为什么还要定义一个代价函数
呢？建议看看另外一片文章Support Vector Machine Learning for Interdependent and Structured Output Spaces。
下面我们举一个小例子，来形象说明一下到底什么是document的subtopics的覆盖。
这张图描述了预测的基本问题。这个集合代表着一个检索的候选文档，每个文档覆盖的面积代表着被这个文档覆盖的信息量（就是所谓的subtopics）.如果
已知，我们就可以通过greedy method来找到这个solution。当
时，这个最优解是
。
对于测试样本，由于我们不知道，因而我们需要找到一种替代方式。我们基于weighted word coverage来构建
。从直觉上来说，覆盖越多的词应该导致会覆盖越多的subtopics。
为了更好的说明如何设计，作者举了一个简单的例子。
代表预测子集中document内包含的word的集合，
描述在所有候选文档中word 
的频率的特征向量。然后我们就可以将写为：
为了更好地表明一个document覆盖一个 word，作者又设计了复杂的
。
到目前为止我们应该已经知道如何建立discriminant function 
,以及如何建立loss function 。接下来我们便要引入如何学习参数了，也就是建立Structural SVMs（论文的第5部分）。
为了使公式汇总的变量更容易理解，我们在这里再次描述一下变量的含义：
训练集合：
（注意哦，在训练集合中T使已知的）
权重向量：
（需要学习的变量）
Structural SVM Optimization Problem
注：这就是标准的structural svm优化问题
对于训练集合的说明：我们知道
和其对应的
，但我们不知道对应于
的真实的
。我们如何得到呢？当然是通过最小化
来得到了，我们可以通过greedy selection来实现。
现在已经没有什么能够阻止我们来求解SVM了。如何求解见。。。
接下来，我们看看如何进行预测（已经知道权重向量 ）
其中
使用一个greedy algorithm，其迭代地选择拥有highest marginal gained 的document加入子集中。具体算法见下：
至此，整个模型的含义已经分析完毕。