假设第二个问题被解决情况下先讨论第三个问题。即如何找到一个\(W^{T}\)满足$w \cdot \phi (x,\hat{y}) > w \cdot \phi (x,y) \(。我们先随机生成权重`w`，在通过式子\)w -> w+\phi (x{r},\hat{y}{r}) - \phi (x{r},\tilde{y}{r})\(来更新直至 `w`不再变化，此时我们便找到了所需的`w`。（其中\)\hat{y}{r}$是标签，$\tilde{y}{r}$是第二步找到的结果）
这个寻找w的算法就是perceptron感知器算法。perceptron learning感知器学习也是结构化学习的一个特例
在下一章会又更详细的讲解。
证明算法的可行性和收敛性(省略)
第二十五章 结构化学习 - 结构化支持向量机
之前提及的三个问题：模型选择，如何解决arg max，如何重建F(x,y)
问题二之所有跳过是因为对于不同的task，所使用的手段不一。如下：
Object Detection
Branch and Bound algorithm分支定界算法
Selective Search选择性搜寻
Sequence Labeling
Viterbi Algorithm维特比算法
The algorithms can depend on\(\phi(x,y)\)
Genetic Algorithm基因算法（遗传算法）
三个问题着重focus on第三个问题。
假设Separable case：存在一个w满足$w \cdot \phi (x,\hat{y}) > w \cdot \phi (x,y) $。
Structured Perceptron结构化感知机：这就是上一章描述的方法，先随机生成权重w，对于每个数据再通过式子\(w -> w+\phi (x^{r},\hat{y}^{r}) - \phi (x^{r},\tilde{y}^{r})\)来更新直至 w不再变化，此时我们便找到了所需的w。（其中\(\hat{y}^{r}\)是标签，\(\tilde{y}^{r}\)是第二步找到的最大结果）
该方法的最多需要更新\((R/ \zeta )^{2}\)次就能找到w的收敛值，$\zeta \(是`margin` 错误点与正确点向量差，\)R\(是\)\phi{x,y}\(与所有\)\phi(x,y\')$之间距离的最大值。（收敛次数与y空间规模无关）
收敛证明（省略）
加快训练速度：从分子角度来说可以Normalization；从分母角度来说可以Larger margin减少更新。
假设Non-Separable case：假设数据集没有办法很好的找到需要的w，但是不同的w之间也能体现出好坏。
因此可以定义一个Cost Function代价函数来评估w从来通过最小化代价函数找到最优w。代价函数也可以自己定义，该处定义的是对于每个数据的代价函数\(C^{n}\)而言，有\(C^{n}=max[w \cdot \phi(x^{n},y)] - w \cdot \phi(x^{n},y^{n})\)，总的损失函数：\(C=ΣC^{n}\)。
对该式进行随机梯度下降，梯度通过\(argmax[w \cdot \phi(x^{n},y)] =w \cdot \phi (x^{r},y\') - w \cdot \phi (x^{r},\tilde{y}^{r})\)（每个 w落到不同的y区域而定\(y\'\)是哪个）可知\(\bigtriangledown C^{n}=\phi (x^{r},y\') - \phi (x^{r},\tilde{y}^{r})\)，所以更新$w -> w-\eta \bigtriangledown C^{n} $。
假设\(\eta =1\)时，做的实际上就是结构化感知机；设置成其他的学习率，将会产生不同的模型
假设Considering Errors：误差也可以分为不同的等级，训练数据的时候也需要考虑进去。
我们可以定义Error Function误差函数来确定正确标记与错误标记之间的差异。误差函数也是自定义的，图像上常见的误差函数定义为：\(\Delta(\hat{y},y) = 1- \frac{A(\hat{y}) \bigcap A(y)} {A(\hat{y}) \bigcup A(y)}\)，\(A(y)\)表示边界框\(y\)的区域。
那么损失函数改为：\(C^{n}=max[w \cdot \phi(x^{n},y)+\Delta(\hat{y},y)] - w \cdot \phi(x^{n},y^{n})\)。同样对此进行求解梯度，也是通过argmax得到，\(\bigtriangledown C^{n}\)除了之前不同的是\(y\)取值不同（因为有误差函数的英雄）其他都是一样的。
最小化代价函数实际上是最小化训练集误差的上界，因为对于任何的数据集而言，误差函数可以是任何函数形式，所以我们通过证明\(\Delta(\hat{y},y) \leq C^{n}\)将最小化误差转换为最小化代价函数。
我们上述使用的代价函数是Margin rescaling间隔调整，也可以使用Slack variable rescaling松弛变量调整作为代价函数。
假设Regularization正则化：在之前的代价函数基础上加上正则式
\(C=ΣC^{n} -> C=\frac{1}{2}\begin{Vmatrix}w \end{Vmatrix}^{2}+\lambda ΣC^{n}\)
梯度和w的迭代公式也随之有变化
Structured SVM - intuition直觉解释：
把\(C\)替换成\(\varepsilon ^{n}\)（SVM中的松弛因子），将\(C^{n}\)变形得到：对所有\(y\)有：
\(\varepsilon ^{n} + w \cdot \phi(x^{n},\hat{y}^{n}) \geq w \cdot \phi(x^{n},y)+\Delta(\hat{y}^{n},y)\)
$ w \cdot \phi(x{n},\hat{y}{n}) - w \cdot \phi(x^{n},y) \geq \Delta(\hat{y}^{n},y) - \varepsilon ^{n}$
\(C=\frac{1}{2}\begin{Vmatrix}w \end{Vmatrix}^{2}+\lambda Σ\varepsilon ^{n}\)