结构预测瀑布（Structured prediction cascades）
也是很久没有看跟deep不相关的论文了，而且本身对图模型也不是特别的熟悉（虽然上过课，但是也是基本上忘的差不多。）
读这篇Structured prediction cascades是因为我的qualifying exam。我们这qualifying exam是给你assign一篇非你领域内的论文，然后给你一个月时间，然后做个关于这个paper的presentation。理论上他可以问任何跟这篇论文相关的问题，可以问的很偏，但是这主要看老师，有些老师就喜欢狂问问题，问蒙你，有些就比较和善。
我的committee member都很和善，当时我拿到名单我就觉得妥了。。。。然而。。。。。我是conditional pass。。。。。很尴尬，但是基本上算过了。
接下来是这篇论文，论文地址http://homes.cs.washington.edu/~taskar/pubs/aistats10cascades.pdf事实上这是一篇10年的paper，那个时候deep learning还没有这么牛逼，所以这篇文章跟dl半毛钱关系都没有。
首先在这篇文章中，主要研究的是structured prediction。structured prediction是什么呢？可以它认为是监督学习的一种。如果预测的输出是一个离散变量，我们一般称之为分类，如果是一个实数，我们一般叫他回归。而如果输出是一个structured object，则这时候叫structured prediction。
什么东西是structured data？structured object一般可以被分解成几个部分，并且部分之间包含信息。比如说一句句子，中间词与词总有主谓宾定状补的关系吧。image，text，甚至蛋白质folds都可以认为是结构数据。
有很多我们熟悉的问题都可以看作是structured prediction，比如说nlp中的pos tagging，parsing，translation，再比如vision中的segmentation，pose estimation。
这篇文章主要考虑的就是模型在做预测的时候approximation vs. computation. Approximation其实就是说模型能拟合的程度（在regression里面就是，你用一次来拟合二次就approximation就很差，三次来拟合二次approximation就很好）。approximation vs. computation就是，简单的模型approximation不够，但是速度快；而复杂的模型虽然approximation好，表达能力更强，但是速度太慢。这篇文章就是来解决这个问题的。
解决的方法就是用cascades（一串模型），用coarse to fine的方式来解决这个问题。这里先介绍一下cascade在face detector里面的用法。（这也是这篇文章的灵感来源）
这里是一个face detection的cascade例子。每一层的模型做的事情是确定哪些一定不是face，然后把他们滤掉。一开始可以先用简单的模型，快速滤掉明显错误的，然后再用复杂的模型在更小的搜索空间里搜索。由于搜索空间小了，所以原本跑的慢的模型也不会太慢了。
放在structure prediction中其实也是一样，我们想找到的是最好的一个输出，而每一层的模型就是将肯定是错的输出滤掉。
模型
notation：input space , output space
, X和Y的联合分布D(X, Y)，训练数据S和loss function
一般来说，监督学习可以认为是，学习一个，使得期望loss
最小。
在结构预测下，就是有结构的，这篇论文里，他们假设Y是定长的离散向量：
马尔可夫模型
TL;DR，他们定义了一个score function ，这个公式来自于markov模型，c为markov网络中的cliques。
这篇paper他们用了概率图模型来定义（其实他们最后并没有用到概率解释），那么这时候
就可以了。之所以使用图模型，1是这样可以对变量之间的关系进行建模，2是因为这样就可以使得argmax操作（inference）变成tractable的。（如果在Y空间中爆搜，就是指数级别的复杂度）
根据图模型然后就可以将因子化，变成定义在clique上的因子的乘积
是一个y的subset，是包含在clique c中的元素。
再进一步，我们这里用log-linear的模型，这样的话，就可以继续写成
为了之后notation方便，我们定义，
，这样的话
所以这时候。再之后我们就不用考虑概率解释了，就把
当作是一个分数，给（x,y）对的一个分数。
在这篇文章中，他们在每一层使用的都是linear-chain markov模型；随着层数的增高，他们从第一层的0阶到最后3阶4阶。
此图为一阶markov模型的示意图。
在一阶markov中，clique分别为，且
瀑布
在cascade的每一层中，都是上面介绍的这种linear分数模型，不同的是，每一层拥有不同的参数和结构，越后面的层越复杂。和普通的结构预测不一样，cascade模型只有在最后一层才做预测，前面所有的层都是做filtering。
Inference（推断）
怎么样用cascade做推断呢，其实很简单，就是通过一层一层的layer，每一层都滤掉一些错误解。滤掉错误解的方式，是滤掉错误的的clique assignment。比如说这一层是first order markov model，那我滤掉的就是 y1y2, y2y3 ... y_{l-1}yl的取值。怎么样的取值会被滤掉呢，我们可以计算每个clique 取值的max marginal（之后再定义，这里可以认为是clique assignment的分数），如果max marginal大于一个阈值（一会再定义），则它就被滤掉了。
max-marginal的定义为，也就是说，所有拥有y_c clique取值的y能获得的最大分数。
然后阈值的定义如下，
其中，
，
。这个阈值其实就是最高可能分数和平均max marginal分数的一个convex组合。其中alpha是在dev set上调的，可以认为是一个超参数。
这样的定义，1，与所有分数都是在同一scale的，不会因为不同x不同scale而会产生问题。第二，这个阈值关于w是凸的，所以之后训练时能是一个凸优化。
训练
cascade的训练时一层一层分开训练的。每一层我们先选定一些的取值，然后训练的到w。
loss function为：
其中，
这个loss function和在svm中非常像，简单的说就是希望ground truth的分数要比threshold要高一个margin（这里是1）。他们用subgreadient descent来训练这个模型。
实验
简单的说，就是他们能不怎么损失精度的得到更快的速度。
结尾
并不是特别exciting的paper，但是作为qualifying exam让我复习一遍图模型还是可以的。虽然这篇文章本身的idea很好，但是其实follow up的工作并不多，可能实际使用中没有特别的优势吧。
但是图模型在deep中还是有挺多应用的。用来做segmentation的post processing，或者将crf变成rnn啊，或者将本文中linear model替换成一个deepnet啊。可移步概率图模型与深度学习能够如何结合？ - 知乎
ps：很明显写到后面不是很想写了。。。。。。。但是如果想具体了解一些细节的话，这里有我写的英文的summary。http://ttic.uchicago.edu/~rluo/files/qualifying_exam_summary.pdf
如果再想多了解一些，这里是原paper，http://homes.cs.washington.edu/~taskar/pubs/aistats10cascades.pdf
如果再再想多了解一些的话，这里是原paper的journal版本，虽然没发出去，https://arxiv.org/pdf/1208.3279.pdf