Graph Structured Prediction Energy Networks

Colin Graber, Alexander Schwing

2 Background

因为公式1除了loss，还加入了model score，因此这个也称为loss-augmented inference。下面具体讨论model score $$F(x,y;w)$$。

Unstructured Models

简答的说，就是假设label prediction的时候，所有的label是相互没有联系。

$$F(x,y;w) = \sum_{k=1}^K f_k(x, y_k; w)$$

Classical Sturctured Models

从可能的subsets来考虑。假设K个instance所有可能的关系是$$R$$，然后考虑所以可能的关系子集$$r \in R$$。因此有

$$F(x,y;w) = \sum_{r \in R} f_r(x,y_r; w)$$

这个方法可以显示得计算F。而variable subset relations，也就是结构，通常是通过factor graphs，或者更一般化的，Hasse diagrams，来可视化。

这个方法的代价是，这个NP-hard的问题会带来更复杂的inference。有一些approximation的方法。这里主要还是随着largest region $$r$$ 的大小会resize。因此，通常这类模型只考虑unary或者pairwise region，也就是一个或者两个变量。

Inference，或者score的最大化，相当于integer linear program

$$\max{p \in \mathcal{M}} \sum{r \in R} \sum_{y_r \in \mathcal{Y}_r} p_r(y_r) f_r(x,y_r;w)$$

其中的$$p_r$$代表了marginal probability vector for region $$r$$，而$$\mathcal{M}$$代表了set of $$p_r$$，他们的marginal distributions are globally consistent，通常被叫做marginal polytope。而在这个term上加入了entropy term就从maximum a-posterior (MAP) 转换为了marginal inference。这使得prediction更加的uniform。

从计算的角度，会很精彩将marginal polytope $$\mathcal{M}$$ relax 到 local polytope $$\mathcal{M}L$$，是所有和 marginalize consistently for the factors present in the graph 一致的probability vector的集合。既然最终的margianls再也不是globally consistent，也就是没办法再保证从同一个single joint distribution产生，我们给每一个region就算的prediction，用$$b_r(y_r)$$，而不是 $$p_r(y_r)$$，并将前者称为beliefs。而且因为entropy term是用fractional entropies来估算的，也就是他只依赖于factors in the graph，在这种情况下它的形式就是 $$H_R(b) = \sum{r \in R} \sum_{y_r \in \mathcal{Y}_r} -b_r(y_r) \log b_r(y_r)$$

Structured Prediction Energy Networks

是为了表示larger sets of outputs，且同时避免了大量的computational cost。SPEN score function如下

$$F(x, p_1, ..., p_K; w) = T(\bar f(x;w), p_1, ..., p_K; w)$$

其中 $$\bar f (x;w)$$是学习到的feature representation，而每一个 $$p_k$$ 是one-hot，T把这两个项拿出来并计算一个score。而inference就是通过以下

$$\max_{p_k \in \Delta_k \forall k} T(\bar f(x;w), p_1, ..., p_K; w)$$

其中$$p_k$$被限制在一个$$|\mathcal{Y}_k|$$-维度的probability simplex $$\Delta_k$$中。这个方法可以用constrained optimization方法解决。但对于non-concave T，这个inference也只是提供了一个估算方案。

NLStruct

****

3 Graph Structured Prediction Energy Nets

****

****

****