经典机器学习系列(十三)【结构化学习】（二）-阿里云开发者社区

经典机器学习系列(十三)【结构化学习】（二）

2023-08-05 66

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 经典机器学习系列(十三)【结构化学习】（二）

此时问题又转变成了：

上述问题就跟SVM一样，转换成了一个凸二次规划问题。

现在的问题就是约束(constraints)太多了，在这么多约束的情况下如何来做呢？

Cutting Plane Algorithm

虽然参数空间中有很多约束(constraints)，但是大部分的约束对我们找的结果是没有影响的。(Red line是我们需要的两个constraint，而例如绿色的constraint即使忽略，也不会对结果产生影响)。

如果我们能够找到只与结果有关的约束项(work set)，我们的求解就会比较容易。约束条件可以改为对于任意的 n nn 和 y ∈ A n 有：

现在的问题就是我们如何来找到这样一个working setA n \mathbb{A}^{n}An? 我们可以通过迭代的方法来做。

为每一个样本初始化一个空的working setA n \mathbb{A}^{n}An。
我们只需要考虑working set里面的y yy，求解上述约束最优化二次问次，能够求解出一个新的w ww。
依据w ww，重新找一个working set成员，这样working set就不一样了。（每次找没有满足约束最严重的那一个约束，将其添加到working set中，如何来找到最严重的这一项呢？不满足约束的条件可表示为：w ′ ⋅ ( ϕ ( x , y ^ ) − ϕ ( x , y ) ) < Δ ( y ^ , y ) − ε ′ w^{\prime} \cdot(\phi(x, \hat{y})-\phi(x, y))<\Delta(\hat{y}, y)-\varepsilon^{\prime}w′⋅(ϕ(x,y^)−ϕ(x,y))<Δ(y^,y)−ε′，因此当Δ ( y ^ , y ) − ε ′ − w ′ ⋅ ( ϕ ( x , y ^ ) − ϕ ( x , y ) ) \Delta(\hat{y}, y)-\varepsilon^{\prime}-w^{\prime} \cdot(\phi(x, \hat{y})-\phi(x, y))Δ(y^,y)−ε′−w′⋅(ϕ(x,y^)−ϕ(x,y))值最大的时候就是最难搞的那个约束，也就是求解哪个y yy对应的约束，找到y yy就找到了对应的约束。对于y yy来说，ε ′ \varepsilon^{\prime}ε′和w ′ ⋅ ϕ ( x , y ^ ) w^{\prime} \cdot \phi(x, \hat{y})w′⋅ϕ(x,y^)是不变项，因此我们需要求解的y yy为arg ⁡ max ⁡ y [ Δ ( y ^ , y ) + w ⋅ ϕ ( x , y ) ] \arg \max _{y}[\Delta(\hat{y}, y)+w \cdot \phi(x, y)]argmaxy[Δ(y^,y)+w⋅ϕ(x,y)] 。
再得到一个w ww，再重新找到一个新的working set，不断地循环。

上述算法用于分类问题也是一样，甚至用DNN去替代上述抽取特征的步骤也同样是可以的。

Sequence Labeling Problem

Sequence Labeling Problem说的是我们需要找一个函数f ff，它的输入是一个Sequence，输出也是一个Sequence。

Hidden Markov Model (HMM)

隐马尔可夫模型(Hidden Markov Model,HMM)大体上可以分为两步：1. 基于语法生成一个合法的词性序列(generate a POS sequence based on the grammar)；2. 在第一步生成的词性序列的基础上，基于字典生成一个句子序列(gengerate a sentence based on the POS sequence;based on a dictionary)。

语法可以假设成一个Markov Chain，那语法长什么样子呢？假设我们现在要产生一句话，那句首的第一个词汇有0.5的概率是一个冠词，0.4的概率是一个专有名词，0.1的概率是一个动词这样。第二个动词就在第一个词汇之上再产生下一个词的概率：

基于第一步，我们可以计算出一个词性序列的概率。

基于这个词性序列，我们可以计算出在第一步生成的合法词性序列的条件下生成对应句子的概率：

接下来我们就需要从训练数据中去获取这些概率值，最简单的方法就是直接统计。

假设我们现在要做一个词性标注的问题，就是给定句子序列x ，找词性序列y ，y 其实是隐变量，如何把y 找到呢？最有可能的y yy就是给定x ，能够使得P ( y ∣ x ) 最大的那个y ，就是最有可能的词性序列y 。

可以发现我们需要遍历所有的 y 才能求解上述问题。如果序列长度为 L ，词性序列为 ∣ S ∣ 的话，我们会有 ∣ S ∣ 种可能，如何来做呢？

Viterbi algorithm

Viterbi algorithm 算法求解上述问题算法复杂度仅有

HMM - Summary

HMM也是structured learning的一种方法，structured learning的方法需要解决三个问题，HMM是如何解决的呢？

HMM的方法也存在一些缺点：

计算转移概率和输出概率是分开计算的，认为其是相互独立的。然而序列标注问题不仅和单个词相关，而且和观察序列的长度，单词的上下文，等等相关。因此x xx和y yy会条件独立吗？
目标函数和预测目标函数不匹配问题，HMM学到的是状态和观察序列的联合分布P ( Y , X )，而预测问题中，我们需要的是条件概率P ( Y ∣ X ) 。