Is Shortest Always Best? The Role of Brevity in Logic-to-Text Generation (2023)

Abstract: Some applications of artificial intelligence make it desirable that logical formulae be converted computationally to comprehensible natural language sentences. As there are many logical equivalents to a given formula, finding the most suitable equivalent to be used as input for such a “logic-to-text” generation system is a difficult challenge. In this paper, we focus on the role of brevity: Are the shortest formulae the most suitable? We focus on propositional logic (PL), framing formula minimization (i.e., the problem of finding the shortest equivalent of a given formula) as a Quantified Boolean Formulae (QBFs) satisfiability problem. We experiment with several generators and selection strategies to prune the resulting candidates. We conduct exhaustive automatic and human evaluations of the comprehensibility and fluency of the generated texts. The results suggest that while, in many cases, minimization has a positive impact on the quality of the sentences generated, formula minimization may ultimately not be the best strategy.

## introduction logical formulae (lfs) are essential for scholars in many scientific fields, such as artificial intelligence and linguistics (e.g., formal semantics). for instance, some explainable artificial intelligence (xai) methods (e.g., @xcite use lfs to provide interpretable and faithful explanations to black-box models. however, one of the drawbacks of these xai methods is that their output formulae might be complex, hindering their understandability. grasping the meaning of formulae is also hard for students of logic, especially when they are exposed to formalisms they are not yet accustomed to @xcite . natural language generation (nlg) methods can be employed to simplify and translate lfs into understandable text in natural languages (nls), effectively providing explanations for them. recently, nlg has made remarkable progress. in particular, in the context of data-to-text generation, good results have been achieved in different domains and datasets, such as sport (e.g., the rotowire dataset @xcite ), restaurant (e.g., the e2e challenge @xcite ), or webnlg @xcite . however, the texts produced in these contexts are often relatively poor in logical and rhetorical structure. moreover, neural language models still fail to encode the semantics of logical formulae @xcite and acquire analytical and deductive logical reasoning capabilities @xcite . in particular, they struggle with logical connectives, where they fail to differentiate between conjunction and disjunction @xcite . logic-to-text generation thus addresses an area of natural language processing where further progress is much needed. one way in which the task of generating nl from complex lfs could be facilitated is by simplifying the input. we are interested in understanding the factors that make a formula more or less suitable as an input for a generator. in our work, we focus on brevity. the concept of brevity has long been a topic of linguistic discussion, dating back to at least @xcite , where grice's submaxim of brevity states that shorter utterances should be favored over longer ones, avoiding unnecessary verbosity. brevity has loomed large in computational accounts of language use as well, especially in the modeling of the human production of referring expressions (see §6 for discussion), a research area known as referring expressions generation @xcite . brevity could also be useful in our situation, in which case a shorter formula, instead of a lengthier logical equivalent, once verbalized using an nlg algorithm, might lead to nl sentences that are more fluent and easier to understand. in this paper, we study the role of brevity in logicto-text generation, focusing on propositional logic (pl), a formalism for which logical equivalence is decidable. we formulate propositional logic formula minimization (i.e., finding the shortest logical equivalent of a given formula) as a quantified boolean formulae (qbfs) satisfiability problem and employ the algorithm introduced in @xcite that consistently identifies the shortest equivalents for a given formula. it is not a foregone conclusion that the shortest formula must always lead to the best verbalization in english. to see this, suppose the input to the generator is of the form ¬p ∨ ¬q. if the sheffer stroke, |, (i.e., the nand operator) is a permitted symbol, then the same information can be written more briefly as p|q, yet a "direct" verbalization of the former formula (e.g., not p or not q) could well be more comprehensible and fluent than a direct verbalization of the latter (e.g., it is not the case that p and q), because the sheffer stroke does not have a convenient shorthand in english. following this line of thought, several questions arise: when verbalizing an input logical formula into english, is it useful to start by finding the shortest formula that is equivalent to the input? is the resulting text comprehensible to humans? how do we choose among the pool of potential shortest equivalent candidates? the last question specifically opens up the issue of selecting the optimal translation, given that all potential shortest candidates are exactly of the same length. in our work, we experiment with several deterministic rule-based generators (thus controlling for faithfulness) and a number of selection strategies based on linguistic criteria, ranging from heuristics to neural metrics, to prune the resulting nl candidates. finally, we conduct comprehensive automatic and human evaluations to assess comprehensibility and fluency of the generated texts. quantified boolean formulae quantified boolean formulae (qbfs) are an extension of propositional logic, where universal and existential quantifications over boolean variables are allowed @xcite . any qbf ϕ can be rewritten in a canonical prenex conjunctive normal form (pcnf) without any loss in expressivity, as follows. let b be a finite set of boolean variables, and @xmath0, ∃}. a qbf ϕ over b in pcnf is given by ϕ := q 1 b 1 .q 2 b 2 . . . q n b n .ψ, where q @xmath1, b i ⊆ b, and ψ is a boolean formula over b in cnf. the part including only quantifiers and bound variables q 1 b 1 .q 2 b 2 . . . q n b n is called the prefix, and ψ is called the matrix. the qbf satisfiability problem @xcite involves determining the truth of a given qbf ϕ. for example, given the qbf ϕ := ∃x 1 , . . . , x n .∀y 1 , . . . , y m .∃z 1 , . . . , z t .ψ, ϕ is true iff, there exists a truth assignment to x 1 , . . . , x n , such that, for all truth assignments to y 1 , . . . , y m , there exists a truth assignment to z 1 , . . . , z t such that ψ is true. to solve this problem, several qbf solvers have been developed. foot_0 practical applications of qbfs include ai, logic, planning, and games @xcite @xcite . in our study, we utilize qbfs to encode and solve pl formula minimization. logic-to-text generation logic-to-text generation is the task of generating nl text, starting from a logical formalism (e.g., propositional logic, description logic, or first-order logic). although the bulk of recent work on nlg (see e.g., gatt and krahmer (2018) for a survey) has focused on other areas, generating text from logic nonetheless has a long tradition, with approaches ranging from rule-based methodologies @xcite @xcite @xcite @xcite @xcite @xcite to statistical @xcite @xcite and neural models @xcite @xcite @xcite . one of the complicating factors for this task is the problem of logical-form equivalence @xcite @xcite , which implies that every logical formula is equivalent to infinitely many other formulae, where the question of whether two formulae are logically equivalent is, in many formalisms (e.g., first-order logic), undecidable. in the present paper, we circumvent this problem by focusing on a decidable fragment of logic, as did, e.g., @xcite and @xcite before us in different ways. in a closely related work, calò et al. (2022) manipulate a given first-order formula to obtain logically equivalent simplified versions via logical equivalence laws, yet their algorithm is not guaranteed to return the shortest formula. ## algorithm to solve our pl minimization problem, we leverage the qbf-based algorithm presented in @xcite . we define formula length as the number of symbols (i.e., predicates and connectives, parentheses excluded) contained in a formula. in outline, given (i) a pl formula ψ and (ii) a functionally complete set c of pl connectives, the algorithm produces the set @xmath2, . . . , ψ ′ n } of all those pl formulae such that (a) ψ and ψ ′ i are logically equivalent, (b) ψ ′ i does not contain any connectives that are not members of c, and (c) there does not exist any strictly shorter sentence χ satisfying (a) and (b). the strength of the qbf-based algorithm is that it computes a scheme t n of all candidates ψ ′ i of length n, instead of checking each one of ψ ′ i for equivalence with ψ. tseitin transformation @xcite ) is used to encode the equivalence of t n and ψ as a qbf formula, which is checked for satisfiability (see section 2) by a qbf solver @xcite . the algorithm can find all ψ ′ @xmath3. by making several calls to the qbf solver, increasing n, we make sure that the first found solution is a minimal solution. the fact that the algorithm computes a unique scheme for all candidates of length n makes it very efficient, compared with other straightforward approaches. we refer the reader to @xcite for details on the implementation. ## experiments our experimentation strategy can be summarized as follows: (i) we simplify the input formulae using the algorithm described in §3, (ii) we realize all the outputs using different generators, and (iii) we prune the resulting candidate realizations using a number of selection strategies. we use three rule-based generators: (i) a base-line, (ii) the system presented in @xcite , and (iii) lola @xcite . baseline is a system that generates near-literal translations of the formulae. ranta performs some syntactic optimization (e.g., flattening, aggregation, etc.) to improve fluency. lola is an extension of ranta that performs heuristic logical optimization based on standard equivalence laws to the input formula before verbalizing it. the generators were evaluated for faithfulness (i.e., whether the generated text conveys all and only the information of the input formula) in @xcite and shown to guarantee faithful translations. we refer the reader to @xcite and @xcite for more details on the systems. for pruning, we experiment with the following five selection strategies: (i) length in number of words, (ii) pseudo-perplexity using bert @xcite , (iii) pseudo-slor using bert, (iv) perplexity (ppl) using gpt-2 @xcite , (v) slor using gpt-2. foot_1 slor (syntactic log-odds ratio; @xcite is a metric based on negative log-likelihood that penalizes highly probable unigrams. in detail, the score given by slor consists of the log probability of a sentence under a given language model, normalized by unigram log probability and sentence length. the intuition behind the normalizations is that a rare token should not bring down the sentence's score and shorter sentences should not be preferred over equally fluent longer ones. in our case, this should help us make fairer comparisons, as the length of the sentences generated by the re-alizers varies considerably, and logical variables and constants (e.g., x, y, etc., which a language model treats as unigrams), which appear regularly in our sentences, have a unigram probability much higher than the other tokens in the lexicon. we compute ppl and slor with bert, following the methodologies described in @xcite and lau et al. (2020) for masked language models. for the experiments, we consider the grade grinder corpus (ggc; @xcite , a parallel corpus where each nl sentence is paired with multiple logically equivalent formulae. we retrieve all pl formulae that are parsable by the generators we use. we first simplify the formulae using the algorithm described in §3 and obtain, for each formula, a set of logical equivalents, maximally reduced in terms of length. out of 1092 pl formulae, 680 got simplified; the others were already in their shortest form. at the logic level, all potential candidates are exactly of the same length. therefore, once nl sentences are generated, we prune the candidates by (i) scoring them using the five selection strategies 5 evaluation ## conclusion we have studied the role of brevity in logic-totext generation. we employed a state-of-the-art (in terms of speed) qbf-based algorithm @xcite that always finds the shortest equivalents to an input pl formula. we verbalized the outputs experimenting with several realizers and selection strategies to study whether the translations from shorter formulae are more comprehensible and fluent than those from their longer logically equivalent counterparts. the results of our evaluations suggest that manipulating the original input formula (using logical equivalence laws as in lola or via minimization) improves the sentences generated. our study taught us some other lessons as well. for example, the free text comments that our evaluators provided suggest that there is a need to (i) take measures to mitigate ambiguity in the generated sentences (see also in conclusion, is brevity valid as a principle that guides logic-to-text generation? a comparison with referring expressions generation (reg) might be helpful here. researchers in reg build computational models of the choices that human speakers make when referring. early reg algorithms @xcite always generated the shortest expression that singles out the intended referent. however, such brevity-oriented reg algorithms have been found both computationally infeasible @xcite and dissimilar to the approaches followed by human speakers. recent reg models all strike a compromise between brevity and a number of other factors (van deemter, 2016); they can be seen as approximating brevity to different degrees. it is conceivable, likewise, that future work on logic-totext generation ends up following a similar pattern. for example, although the results reported in this paper suggest that brevity has a role to play, future logic-to-text algorithms might achieve even better performance by deviating from brevity to some extent. perhaps brevity in logic-to-text generation should be weighed less heavily in some communicative situations, just as speakers are known to generate more elaborate referring expressions when referential situations are complex @xcite . we hope that future research, in which logical formulae and their natural language "translations" are embedded in well-understood practical tasks, for example in logic teaching or xai, may shed further light on these questions.