$AD^3$(alternating directions dual decomposition)算法出自《Dual Decomposition with Many Overlapping Components》，是对dual decomposition算法的改进，通过增加额外的二次惩罚项来加速收敛，在理论和实践中都更快。这里记录一下将该算法应用于Graph Parsing的子任务解决方法。
A Second-Order Graph Parser
最先使用$AD^3$算法的是参加 SemEval 2014 Task 8 的《Priberam: A Turbo Semantic Parser with Second Order Features》。他们使用了包括基础的predicate, arc, labeled arc以及二阶的grandparent, siblings等子结构。除此之外，由于目的是要生成图结构，因此还首次使用了co-parent结构（也就是一个词和其多个父节点组成的结构）。
需要强调的一点是：$AD^3$算法只是用于解决一个结构预测问题的不同分解之间存在部分重叠情况下的优化问题。在parsing中，最终生成图还是生成树还是取决于$AD^3$算法中每个子问题使用的解码算法得到的是图还是树。
解决子问题
Predicate and Arc-Factored Parts
对于上图中最上面三种结构，这里用一个component统一解决，下面给出算法：
该算法外层循环分别对每个predicate找出其argument，内层循环对每个argument首先找出当前predicate-argument对间分数最高的label，然后判断unlabeled score和labeled score之和，如果大于0则将这条边加入该predicate的侯选边集合，同时把该和加到当前predicate的总分中。当一个predicate的所有argument都判断完之后，如果predicate总分大于0，则把这些侯选边加入输出的依存图中。
注意，解决这个子问题的算法本身产生的就是图结构。
《Deep Multitask Learning for Semantic Dependency Parsing》 中的baseline方法也采用了这三种结构，但是如果用上面给出的算法，应该不需要再使用$AD^3$算法，所以猜测他们应该是至少将这三种结构分成两个component解决的。由于在他们的论文中没有详细描述decoding算法，需要看一下代码。
Unique Roles
假设有些role对于一个predicate来说是唯一的，也就是说该predicate只能与其中一个argument之间有这个label：
$$ sumaz(p\rightarrow^r a \in y) \leq 1, \forall p, \forall r \in R{uniq} $$
其中$R_{uniq}$表示唯一的label集合，通过观测训练集获得。
该约束可以用$AD^3$算法中的Uniqueness factor解决，见 《Dual Decomposition with Many Overlapping Components》第6页。
Grandparents, Arbitrary Siblings and Co-parents
这些二阶子结构都包括一对弧，除此之外不包括其他的弧，因此使用Pairwise factor解决，见 《Dual Decomposition with Many Overlapping Components》第6页。
Predicate Automata
这里使用简单的head automaton model来解决consecutive siblings的问题。对每一个predicate独立地求解其所有的argument，从而一个predicate的score为：
$$ fi(y{|i})=\sum^{p+1}_{k=1}gL(i,l{k-1},lk)+\sum^{q+1}{k=1}gR(i,r{k-1},r_k) $$
其中$y_{|i}$是一个二值向量，表示句中每个词是不是词i的argument。$g_L$和 $g_R$ 分别是predicate左边和右边的argument bigram的评分函数。$l_n$和$r_n$ 分别代表prediacte左边和右边的arguments。
具体参考《Dual Decomposition for Parsing with Non-Projective Head Automata》第3页。
Argument Automata
可以用与前一节类似的方法解决co-parents的问题，只是把上面的argument和predicate位置换一下，这里不再赘述。
以上就是Priberam Graph Parser用到的所有子结构的解决方法。