C o S a T a: A Constraint Satisfaction Solver and Interpreted Language for Semi-Structured Tables of Sentences (2020)

Abstract: This work presents CoSaTa, an intuitive constraint satisfaction solver and interpreted language for knowledge bases of semi-structured tables expressed as text. The stand-alone CoSaTa solver allows easily expressing complex compositional “inference patterns” for how knowledge from different tables tends to connect to support inference and explanation construction in question answering and other downstream tasks, while including advanced declarative features and the ability to operate over multiple representations of text (words, lemmas, or part-of-speech tags). CoSaTa also includes a hybrid imperative/declarative interpreted language for expressing simple models through minimally-specified simulations grounded in constraint patterns, helping bridge the gap between question answering, question explanation, and model simulation. The solver and interpreter are released as open source. Screencast Demo: https://youtu.be/t93Acsz7LyE

## introduction performing inference for complex question answering typically requires combining multiple facts from a knowledge base to arrive at a correct answer, where this set of facts can then be used to generate detailed human-readable explanations for the reasoning behind those answers. combining multiple facts to perform natural language inference is extremely challenging, with contemporary methods generally unable to reliably combine more than two facts together. this is a significant limitation, as even elementary science questions require an average of six @xcite atomic facts to answer and explain @xcite ) -particularly when those explanations include detailed world knowledge. for example, 1 demo: https://youtu.be/t93acsz7lye a middle-ground exists between these two extremes, where semi-structured knowledge bases of text (such as tables) are used to support multi-hop inference (e.g. @xcite . this approach offers many practical benefits, such as ease of knowledge base creation (over logical decomposition methods), and providing structure to help infer when combining facts is appropriate (versus free text methods). in spite of these benefits, it is often still challenging to implement inference models that compose (or "hop" between) facts expressed in tables of language data in practice, and practitioners tend to resort to using complex models (such as integer linear programming (e.g. tableilp; @xcite ) that significantly increase development time and limit interpretability, maintainability, and reuse. this work presents an easy-to-use scripting language paired with an open source solver and interpreter designed to make compositional inference over semi-structured knowledge bases of tables easy, particularly when those tables express knowledge as lightly structured sentences. the contributions of this work are: the cosata language allows easily expressing large multi-hop "inference patterns" that describe how facts typically connect across tables in a knowledge base to express a larger compositional solution. the optimized multithreaded solver supports advanced features for dealing with text, including enumerative variable span detection, and robustness to surface form variations with patterns that can match words, lemmas, or parts-of-speech. ## language description the cosata language includes declarative features for performing constraint satisfaction over tables, and imperative features for expressing and executing models. the fundamental unit is the pattern, analagous to a class in object oriented programming, which (at a minimum) contains a declarative constraint pattern of table rows. the declarative features are sufficient for easily expressing variablized compositional patterns over collections of table rows, and the output of the stand-alone constraint satisfaction solver (e.g. solutions in json format) can serve as input to further processing. the language also supports a suite of imperative features for expressing and executing models. in this paradigm, each pattern is considered a process that, if executed, imparts some change upon a small model of the world (such as an object warming from heat transfer) by executing a pattern code block. agents, physical objects, and environments in the model are represented as objects, here sets of property-value pairs. a control script imports a library of patterns, initializes objects, and executes a small subset of patterns in a particular order to create a simulation. a state space keeps a log of each object, it's properties, the patterns executed, and their resulting changes, to form a detailed and human-readable record of a simulation performed to arrive at a particular inference. ## example solutions here the feasibility of generating constraint patterns (for downstream processing) or executable patterns (for modeling) is empirically demonstrated in the context of generating detailed multi-hop explanations to standardized elementary and middle school science exam questions drawn from the ai2 aristo reasoning challenge @xcite . ## conclusion cosata is an open-source constraint satisfaction solver for easily expressing and evaluating multifact compositional patterns in semi-structured tables of text, paired with an interpreted language that allows expressing micro-models. the tool, source, examples, and documentation are available at http://www.github.com/clulab/cosata/ .