In structured prediction, the goal is to jointly predict many output variables that together encode a structured object -- a path in a graph, an entity-relation triple, or an ordering of objects. Such a large output space makes learning hard and requires vast amounts of labeled data. Different approaches leverage alternate sources of supervision. One approach -- entropy regularization -- posits that decision boundaries should lie in low-probability regions. It extracts supervision from unlabeled examples, but remains agnostic to the structure of the output space. Conversely, neuro-symbolic approaches exploit the knowledge that not every prediction corresponds to a valid structure in the output space. Yet, they does not further restrict the learned output distribution. This paper introduces a framework that unifies both approaches. We propose a loss, neuro-symbolic entropy regularization, that encourages the model to confidently predict a valid object. It is obtained by restricting entropy regularization to the distribution over only valid structures. This loss is efficiently computed when the output constraint is expressed as a tractable logic circuit. Moreover, it seamlessly integrates with other neuro-symbolic losses that eliminate invalid predictions. We demonstrate the efficacy of our approach on a series of semi-supervised and fully-supervised structured-prediction experiments, where we find that it leads to models whose predictions are more accurate and more likely to be valid.

@inproceedings{AhmedUAI22,
  title    = {Neuro-Symbolic Entropy Regularization},
  author   = {Ahmed, Kareem and Wang, Eric and Chang, Kai-Wei and Van den Broeck, Guy},
  month    = 8,
  year     = {2022},
  booktitle= {Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence (UAI)},
  annotation = "(Oral full presentation, acceptance rate 36/712 = 5\%)",
  url      = "http://starai.cs.ucla.edu/papers/AhmedUAI22.pdf",
  code 		= "https://github.com/UCLA-StarAI/NeSyEntropy",
  keywords = {conference,selective}
}