  Structured output prediction problems (e.g., sequential tagging, hierarchical
multi-class classification) often involve constraints over the output label
space. These constraints interact with the learned models to filter infeasible
solutions and facilitate in building an accountable system. However, although
constraints are useful, they are often based on hand-crafted rules. This raises
a question -- \emph{can we mine constraints and rules from data based on a
learning algorithm?}
  In this paper, we present a general framework for mining constraints from
data. In particular, we consider the inference in structured output prediction
as an integer linear programming (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. Our algorithm can also integrate with a neural network model
to learn the hierarchical label structure of a multi-label classification task.
Besides, we provide a theoretical analysis about the tightness of the polytopes
and the reliability of the mined constraints.
