Various structured output prediction problems (e.g., sequential tagging)
involve constraints over the output space. By identifying these constraints, we
can filter out infeasible solutions and build an accountable model.
To this end, we present a general integer linear programming (ILP) framework
for mining constraints from data. We model the inference of structured output
prediction as an ILP problem. Then, given the coefficients of the objective
function and the corresponding solution, we mine the underlying constraints by
estimating the outer and inner polytopes of the feasible set. We verify the
proposed constraint mining algorithm in various synthetic and real-world
applications and demonstrate that the proposed approach successfully identifies
the feasible set at scale.
In particular, we show that our approach can learn to solve 9x9 Sudoku
puzzles and minimal spanning tree problems from examples without providing the
underlying rules. We also demonstrate results on hierarchical multi-label
classification and conduct a theoretical analysis on how close the mined
constraints are from the ground truth.