Interpretable Decision Sets (IDS) is an approach to building transparent and interpretable supervised machine learning models. Unfortunately, IDS does not scale to most commonly encountered big data sets. In this paper, we propose Rapid And Precise Interpretable Decision Sets (RAPID), a faster alternative to IDS. We use the existing formulation of decision set learning and propose a time-efficient learning framework. RAPID has two major improvements over IDS. First, it uses a linear-time randomized Unconstrained Submodular Maximization algorithm to optimize the objective function. Second, we design special data structures, based on Frequent-Pattern (FP) trees to achieve better computational efficiency. In this work, we first perform a time complexity analysis of IDS and RAPID, and show the significant advantages of the proposed method. Next we run our algorithm, along with baselines, on three public datasets. We show comparable accuracy for RAPID, with 10, 000x improvement in running time over IDS. Additionally, due to the significant improvements in running time of RAPID, we can run more extensive hyperparameter search algorithms, leading to comparable accuracy with competitive baseline models.

In this work, we propose the notion of a Parse Condition—a logical condition that is satisfiable if and only if a given string w can be successfully parsed using a grammar G. Further, we propose an algorithm for building an SMT encoding of such parse conditions for LL(1) grammars and demonstrate its utility by building two applications over it: automated repair of syntax errors in Tiger programs and automated parser synthesis to automatically synthesize LL(1) parsers from examples. We implement our ideas into a tool, Cyclops, that is able to successfully repair 80% of our benchmarks (675 buggy Tiger programs), clocking an average of 30 seconds per repair and synthesize parsers for interesting languages from examples. Like verification conditions (encoding a program in logic) have found widespread applications in program analysis, we believe that Parse Conditions can serve as a foundation for interesting applications in syntax analysis.