| 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.
|