机器学习中大部分问题考虑的输入都是一个向量，输出是另外一个向量。而现实生活中的问题往往比这复杂地多，输出可能是一个sequence，list，tree或者bounding box。如何处理这种结构化的数据呢？而这种结构化的数据在现实生活中又比比皆是。想语音辨识(Speech recognition，输入一个声音信号，输出一段文本)，翻译(Translation，输入一段文本，输出一段文本)，目标检测(Object Detection，输入一张图片，输出bounding box)，摘要生成(Summarization，输入一长串文本，输出摘要)，检索(Retrieval，输入是一个关键字，输出是一个list)。
Unified Framework
听起来比较难做，其实是有一个通用的框架的。我们知道机器学习算法通常分为两步：训练和测试。这个通用的框架也分为两步：
上述过程其实就是G A N GANGAN的思想，不过是用Deep Learning来做这样一件事情。
- 举个例子：假设我们现在要做目标检测，输入是一张图片，输出是一个
bounding box。
在训练的时候，给定图片和bounding box，(也就是输入是图片和bounding box) 如果比较匹配的话分数就会很高，如果不匹配的话，分数就会很低。
在测试的时候，给定一张从来没有见过的例子，穷举所有可能的bounding box，看看哪一个bounding box能够拿到最高分，能拿到最高分的bounding box就是我们最终的输出。
Statistics
上述的说法如果在统计学中描述就与贝叶斯推论联系起来了。同样分为两步：
这种概率的方法需要穷举所有的 y yy，这一步有时候会变得很难。单这种方式更容易理解，可解释性也比较强。与这个算法比较类似的有能量模型(Energy Model)，图模型(Graph Model)也是说的一样的东西。
- Energy-based Model：https://cs.nyu.edu/home/index.html
求解
现在我们大概知道了算法的大体思想，接下来我们需要看看如何求解这个模型。如果我们要解这个通用的框架，我们需要计算三件事：
- Evaluation：F ( x , y ) 长什么样子？比如目标检测中输入是图像和
bounding box，这两样东西组合起来应该长什么样子？ - Inference：在推理过程中需要计算：y ~ = arg max y ∈ Y F ( x , y ) ，如何解
argmax这个问题？如果是做目标检测求上述结果，我们需要穷举所有可能的bounding box。 - Training：在训练过程中如何找到能够使得样本集中的样本满足正确标签的F ( x , y ) 能够大过其它的情况？真的能够训练出来吗？
这三个问题也就是HMM (Hidden Markov Model)需要解决的三个问题。
那这种structured learning与DNN有什么区别；以手写数字为例，我们输入一张image，得到输出向量N ( x ) ，标签是一个十维的向量 y ，把 y 与 N ( x ) 算交叉熵(cross entropy) 得到 C E ( N ( x ) , y ) 。将其取负号就是 F ( x , y ) = − C E ( N ( x ) , y )。在测试的时候，就是穷举是个可能的标签(十个one-hot向量)，看哪一个标签能够使得 F ( x , y ) 最大。所以DNN是Structed learning的一个特殊例子。这里只有十个label，我们是可以穷举的。
说回来我们如何解决上述三个问题呢？
- 对于如何表示F ( x , y ) 这个问题，可以采用多个
characteristic线性加权组成。即先将( x , y ) (x,y)(x,y)用characteristic表示为 ϕ ( x , y )，在将多个这样的characteristic线性加权：F ( x , y ) = w 1 ϕ 1 ( x , y ) + w 2 ϕ 2 ( x , y ) + ⋯ ，参数w i 为待学习参数。那ϕ ( x , y )在做一件什么事情呢？以目标检测为例，可以想象成在bounding box中看看某些特征出现了多少次这样。那这样的特征又如何来找呢？可以用CNN的方法来找，也就是CNN抽取bounding box里面的图像特征。因为F ( x , y ) 是线性的，所以一般期望ϕ ( x , y )抽特征的能力比较强。 - 测试部分(推理部分)：对于找一个 y 能够满足y ~ = arg max y ∈ Y w 1 ϕ 1 ( x , y ) + w 2 ϕ 2 ( x , y ) + ⋯ ，这一部分我们先假设能够求解(之后再说)。
可以看出算法的思想就是先基于当前的 w 找其最大的 y ~ 如果 y ~ 与真实标签不符，则更新 w 重新找，直到 w 不再更新。
Proof of Termination
假设我们已经解决了前两步，也就是知道如何抽ϕ ( x , y ) ，知道如何解argmax的问题，考虑第三个问题，求解参数w 。
那上述求解w ww的过程真的会收敛吗？因为里面有穷举所有的label这一步，看起来会比较难处理，并且收敛性好像难以直观理解。
由上述推导可知 w 的更新公式为：
先回顾一下δ的定义：
因此我们如果把抽特征的ϕ ( ) 都乘以2会不会使得δ 变大两倍呢？其实不会，R 也会变大两倍，因此不会变快。
不可分情况
w k更新前与更新后可能并不会使得其在数据集上做到：正确的数据标签对应的
要大于任何错误的情况
，单更新后如果能够做到更多数量的样本满足上述要求呢？是不是说明了算法的效果变好了，单依旧不是完美的情况。单也是我们希望看到的，由此定义一个损失函数(Cost Function)，它用来评估w 有多不好。
损失函数可定义为：当前的样本最高的得分与正确标签的得分的差距：
对于所有的样本
有这里取max也与上面第二问取argmax对应，如果取前三名的平均减去正确标签也可以，但是计算第二名第三名的得分就更困难了。
那现在问题就变成了如何找一个 w 来最小化costC 。能不能用(Stochastic) Gradient Descent的方法来做呢？损失函数C 中含有max这一项，如何来求其梯度呢？
对于下述损失函数：
最难处理的就是max这一项，我们采用分段函数的思想，w 取值某块区域的时候取max得到y ′，w 取值另一块区域的时候取max得到y ′ 这样我们就可以对每一个由w 分割开的region进行微分：
到此我们就可以找到线性不可分情况的求解点。
Considering Errors
我们应该如何定义准确值和错误值之间的差距呢？ 常用的做法有以下几种方法：
Error Function：定义正确值和错误值之间的差距。
Regularization
Structured SVM
回归一下原问题：期望寻找到一个参数 w ，它能够最小化 C ：
C n 可以用 ε n代替，称之为松弛变量(Slack variable)。(本来是w ww的值确定下来C n也会定下来，这里我们不考虑这一点，把ε n 也作为一个待优化参数)。
