Structured learning is appropriate when predicting structured outputs such as
trees, graphs, or sequences. Most prior work requires the training set to
consist of complete trees, graphs or sequences. Specifying such detailed ground
truth can be tedious or infeasible for large outputs. Our main contribution is
a large margin formulation that makes structured learning from only partially
annotated data possible. The resulting optimization problem is non-convex, yet
can be efficiently solve by concave-convex procedure (CCCP) with novel speedup
strategies. We apply our method to a challenging tracking-by-assignment problem
of a variable number of divisible objects. On this benchmark, using only 25% of
a full annotation we achieve a performance comparable to a model learned with a
full annotation. Finally, we offer a unifying perspective of previous work
using the hinge, ramp, or max loss for structured learning, followed by an
empirical comparison on their practical performance.

本研究提出一种处理结构化输出的大规模公式，该公式基于部分注释数据进行学习，并通过 concave-convex procedure (CCCP) 进行高效求解以达到解决实际应用的目的。我们将该方法应用于可变数量可分对象的具有挑战性的跟踪问题中，并在仅使用完全注释的 25％的情况下实现与完全注释模型相媲美的性能。最后，我们通过实证比较来统一之前使用的 hinge、ramp 或 max loss 用于结构化学习的透视图。