Representing and Learning Grammars in ASP with Domain-specific Scoring Functions

Abstract Learning generative policy models can be seen as analogous to the general problem of learning context-sensitive grammars. This paper provides theoretical contributions in the areas of context-sensitive grammars (CSGs) and related machine learning. Specifically, we introduce a new class of CSGs, called Answer Set Grammars (ASGs), which extend context-free grammars by allowing annotations on production rules, written in Answer Set Programming (ASP). We investigate the complexity of various classes of ASG with respect to deciding wether (i) a given string belongs to the language of an ASG and (ii) the language of an ASG is non-empty. We introduce an algorithm for learning the annotations of an ASG. To scale up the applicability of our learning algorithm we also present a notion of domain-specific scoring functions applicable to logic-based machine learning in general. We present an efficient mechanism for constructing a small subset of the search space that is guaranteed to contain at least one optimal solution with respect to a given scoring function. We show that our FastLAS algorithm, which uses this efficient mechanism, outperforms state-of-the-art logic-based machine learning systems in terms of running time, and is able to find the optimal solution of a task with respect to a given scoring function.
  • Mark Law (Imperial)
  • Alessandra Russo (Imperial)
  • Elisa Bertino (Purdue)
  • Seraphin Calo (IBM US)
  • Dinesh Verma (IBM US)
  • Jorge Lobo
  • Krysia Broda (Imperial)
  • Greg Cirincione (ARL)
Date Sep-2019
Venue Annual Fall Meeting of the DAIS ITA, 2019