一．问题的提出 我们先回想一下之前经常处理的问题，我们常常是在给定这样一组模式的情况下: (x1,y1),...,(xn,yn)∈X×Y 寻找这样一个映射： f:X→Y 但是我们注意到，在各种回归和分类问题中，我们常常认为Y=R，也即是响应变量为标量，但是我们应该注意到，我们在学习过程中，往往还要面对另一类很重要的问题，需要我们通过模型得到结构化的y，例如，我们在进行自然语言处理的时候，我们在输入一个句子（x），我们可能希望得到一个解析树（y），显然，这是我们之前的模型所无法处理的，因此我们引入了结构化学习(Structured Learning)。 二．Ranking SVM 1. 问题说明 在介绍怎么解决这一类问题之前，让我先绕一点儿弯路，想一下另一个问题：我们在进行网络检索的时候，我们常常需要需要考虑一个问题，当我们获取到检索相关的文档之后，我们需要对文档做一定的顺序排列返回给用户，原因很简单，放在前面的文档显然更加占便宜，容易被用户关注到。 考虑直接将排序问题转化为以查询-文档为训练样本的分类或者回归问题： 但是我们注意到，这样的建模方法所进行的样本训练是跨查询进行的，而这些查询中由于对文档的重要性标注有不同的数量级差异，而这种差异会导致我们在训练时学习到不必要的特性，从而干扰模型的效果。 进一步，我们注意到我们在进行排序的时候，只需要考虑在同一个查询中的文档相对分值大小，因此不会跨查询进行： 因此我们考虑充分利用这种特性获得更好性能的模型。 2. 模型建立 给定训练数据: D={Dqi}Ni=1,Dqi={(dij,yij)}Mij=1 分别对应查询集合和查询的文档集合。 对于每一个查询-文档对都建立特征向量ϕ(q,d) 将其参数化，不妨设： f(q,d)=⟨w,ϕ(q,d)⟩ 对于文档di和文档dj，我们都可以一组序偶对： (ϕ(q,di)−ϕ(q,di),z),z={+1,di>dj−1,di 然后，我们注意到，我们已经建立了一个求解目标，对于任何的输入x，我们希望找到： y^=argmaxy∈YF(x,y;w) 因此，这个问题也被转化为一个二分类问题，我们得到如下样本点： ∀y∈Y∖yi,(ψ(xi,yi)−ψ(xi,y),+1) ∀y∈Y∖yi,(ψ(xi,y)−ψ(xi,yi),−1) 四．损失函数的建立 在解决模型的时候，我们毫无例外地，需要定义一个优化方向，我们按照机器学习的一般方法，首先定义损失函数： 对于一个给定的样本（xi,yi），我们可以借鉴上面的Ranking SVM思想，由于我们在进行模型推断的时候，我们并不需要跨xi进行，因此我们只需要比较得到相对大小即可，我们可以直观的获得一个损失函数： E=maxy∈Y− 可能会有人有疑问，这个并不是我们常见的经验损失函数，我将在后面对这个问题进行解释，并且证明它们的同质性。 先占个坑，我们直观意义上的损失函数为： Eempirical=1n∑nΔ(y~,y) 五．使用感知机进行求解 我们考察上面的损失函数，我们注意到，尽管上面的函数是一个阶梯函数，但是我们在取定y的时候，依然可以对其进行求导： ∂E∂w=ψ(xi,y~)−ψ(xi,yi) 使用梯度下降法，我们可以得到： wk+1=wk−η∇E=wk−η(ψ(xi,y~)−ψ(xi,yi)) 如果我们取学习率参数为1，那么我们就很轻易的获得： wk+1=wk−ψ(xi,y~)+ψ(xi,yi) 我们注意到，这恰好是感知机的迭代方式。 进一步，根据感知机收敛法则，这样的迭代式一定能够结束的，并且最大迭代次数： k≤Rσ 很庆幸，没有与|Y|扯上关系，那么这个问题的求解就是很简单的了。 六．Structured SVM 从上面的感知机模型，我们一个很自然的想法就是，我们可不可以使用SVM对问题的解的形式做进一步的优化： 与SVM相似，如果我们提出约束： ∀i∈{1,2,3,...,n},∀y∈Y∖yi −≥1 上面约束的意思也很明显，就是我们要求最佳的匹配要比其它的好出一个度。 此时我们的优化目标为： minw12∥w∥2 这与我们之前的SVM是完全一致的，但是值得一提的我们注意到Y空间的高维性会带来求解的困难。 进一步，如果我们引入松弛因子，我们有： minw,ξi12∥w∥2+Cn∑i=1nξi s.t. −≥1−ξi,∀i∈{1,2,3,...,n},∀y∈Y∖yi 七．re-scaling slacks or margin 1. slack re-scaling 我们解到这一步的时候，可能都觉得会松了一口气，但是其实我们还忽略了另一个问题，也就是我们之前一直忽略的经验损失函数，我们仅仅考虑了两个模式的匹配程度，但是从一个角度讲，如果这两个结果在结构上是相似的，我是是不是就应该倾向于接受它；反之呢，我们是不是该选择抛弃它？ 基于上面的做法，我们进一步引入惩罚因子——经验损失函数，直观的，我们可以将这个惩罚因子加在松弛因子上，那么其约束条件变为： −≥1−ξiΔ(yi,y),∀i∈{1,2,3,...,n},∀y∈Y∖yi 2. margin re-scaling 也许你也能看出来，将这个惩罚因子加在第一个因子上也是合情合理的，此时，约束变为： −≥Δ(yi,y)−ξi,∀i∈{1,2,3,...,n},∀y∈Y∖yi 这两个并不是很难理解，进一步可以引出来我们下面对于损失函数的解释。 八．why not 经验损失？ 我们知道，在一般的SVM中，我们求得的合页损失函数是0-1损失函数的一个上界，但是structured svm还要更复杂一点。 回到我们上面关于slack re-scaling的公式，结合松弛因子的约束： 整理得： ξi=maxy≠yi{0,maxΔ(yi,y)(1−())} 我们可以分为两种情况进行讨论： 1.= 从而我们有： ξi≥0=Δ(yi,y) 2.不相等，即我们没有找到严丝合缝的match： ξi=maxΔ(yi,y)(1−())≥Δ(yi,y) 从而我们得出结论：我们求出的损失函数是经验损失的一个上界（upper bound）。 对于margin re-scaling的证明不再赘述。 进一步，我们注意到对于结构化的输出，经验损失函数的定义是比较复杂的，此时我们很难对其进行求导等操作，因此我觉得这也算是一个权宜之计。 九．参数学习-cutting plane algorithm 我们注意到在上面的优化目标中，我们可能在求解上遇到一些困难。 考察约束个数，我们发现上述的约束个数为n*|Y|-n，如果我们考虑Y的维度十分高的时候，我们对于这个问题的求解是无能为力的。 但是我们同时进行一些直观的思考，我们很难去想象，我们最终搜索的可行域，是被所有的约束条件所限制的，直观上和实际上，大多数约束都属于redundancy，对于我们的求解，我们希望避开所有这样的约束（甚至于，某些有意义的约束在求解过程中也是可以忽略的）。 因此我们在实际求解中，我们会使用cutting plane algorithm，其思想是进行试错，每一次选择违背最厉害（violated mostly）的约束，将之加入到约束集中，直到不违反任何约束为止。 考虑到我们的学习过程可以和约束选择过程可以同时进行，因此我们不难想象这一个算法的收敛是比较快的。 其算法步骤如下： 或者： https://www.cnblogs.com/sugar-mouse-wbz/p/9884898.html