Hybrid Semantics for Goal-Directed Natural Language Generation (2022)

Abstract: We consider the problem of generating natural language given a communicative goal and a world description. We ask the question: is it possible to combine complementary meaning representations to scale a goal-directed NLG system without losing expressiveness? In particular, we consider using two meaning representations, one based on logical semantics and the other based on distributional semantics. We build upon an existing goal-directed generation system, S-STRUCT, which models sentence generation as planning in a Markov decision process. We develop a hybrid approach, which uses distributional semantics to quickly and imprecisely add the main elements of the sentence and then uses first-order logic based semantics to more slowly add the precise details. We find that our hybrid method allows S-STRUCT’s generation to scale significantly better in early phases of generation and that the hybrid can often generate sentences with the same quality as S-STRUCT in substantially less time. However, we also observe and give insight into cases where the imprecision in distributional semantics leads to generation that is not as good as using pure logical semantics.

## introduction we consider the problem of goal-directed natural language generation (nlg) @xcite . here, the agent intends to communicate some information about its world to another entity. it has semantic representations for its world, its goal, and a grammar to realize the language. given this input, the goal is to generate (realize) a syntactically correct representation of the semantic goal without omissions or additions (see figure 1 ). this task is different from open ended text generation that fills in text after a prompt or the problem of filling in a blank given some context. many previous systems for goal-directed nlg use first-order logic (fol) extended with the λcalculus to represent semantics @xcite . this semantic representation allows for very precise generation. however, the process is usually slow, primarily because each step of the generation process needs to check that the semantics of the partially realized text is compatible with the eventual goal. this step typically involves checking all possible compatible bindings, which is combinatorial. using distributional semantic representations @xcite @xcite ) may allow us to sidestep this combinatorial process through checks via sim-ple algebraic operations. however, these semantics may lack precision and introduce errors in generation with respect to the goal. in this paper we ask whether it is possible to combine these two different semantic representations in a single generation system that takes advantage of their strengths while mitigating their weaknesses. in particular our insight is that, early in the generating process, we may not need to be very precise. we can use distributional semantics to quickly add in the main elements of a sentence and then use logical semantics to fill in the details more slowly and precisely. our goal is to balance these elements to get a more scalable generation system while not sacrificing much, if any, expressiveness. a rich literature exists for generation systems. overgeneration and ranking systems derive possible sentences from word lattices @xcite @xcite . these word lattices are directed acyclic graphs whose edges correspond to single words. to generate a valid sentence, the system can traverse a path in the lattice. then, they rank the candidate sentences using a language model. an alternative approach is to view generation as an ai planning problem. the planner can apply grammar "actions" to take planning steps until it finds a state that fulfils some communicative goal. one such system is spud (sentence planner using descriptions) which answers questions using a knowledge base @xcite . the crisp system builds on spud by applying an off-the-shelf planner instead of using a greedy search @xcite . this allows for the application of search heuristics and other advances in classical planning. a further improvement is pcrisp which allows probabilistic actions by translating probabilities into costs @xcite . other work uses neural networks with an encoder and/or decoder architectures. for instance, a transformer will already have the semantics of individual words as static word vectors @xcite @xcite @xcite . the overall meaning is calculated using attention and feedforward layers. these approaches create a complex representation of the language model in the encoder and employ a variety of sampling strategies in the decoder. while they can be much faster than logicbased systems, it can be difficult to guarantee that the generated string will be consistent with some world or goal. recent work has started to explore hybrid approaches in this space. one approach adds logical constraints and plans to transformers and lstms. dualenc models are provided "content plan" traversals through rdf graphs as input @xcite . while these plans provide the model with the information that is supposed to be included in the generated text, there is no guarantee the model will include all of it or that the information is truly consistent with the original rdf graph. rather than providing a plan before generation, neurologic decoding constrains generated transformer output based on logical constraints during the decoding step @xcite . by leveraging predicate logic, this allows the output to be more precisely constrained to include any necessary true facts and leave out any extra, potentially incorrect, information. this precision is added at a cost asymptotically equivalent to a conventional beam search. however, the logical constraints in this work are syntactic rather than semantic, and ensure that, for example, certain words are not used by the decoded string. in contrast to such approaches, in our work, we modify s-struct @xcite , a planning based system for goal-directed nlg, to use both distributional as well as logical semantics. s-struct is described in detail in the next section. this system models generation as planning in a markov decision process (mdp). we show experimentally that our approach scales better than pure logical semantics in many cases. we also identify and discuss tradeoffs that arise from the use of distributional semantics, that in some cases lead to worse generation quality. ## s-struct scalable sentence tree realization using uct (upper confidence bounds applied to trees), or s-struct, is a planning based nlg system that generates single sentences, using a world of facts, a communicative goal, and a grammar. the world and goal are both specified semantically in fol. the world describes all entities and relations known to the generator while the goal specifies information to communicate. the grammar consists of a semantically annotated probabilistic lexicalized tree adjoining grammar (pltag) derived from the xtag project @xcite . uct search get action explore action initialization get action apply action update best sent/reward continue? return best sent action from open/tree policy continue? return best action actions from default policy apply actions calc reward propagate reward no yes yes no figure 2: s-struct algorithm. uct is used to find the best action (pltag tree substitution/adjoin) at each step until the goal is satisfied (reward is maximized). before s-struct begins the generation process, it finds an expanded communicative goal. the expanded goal includes any extra information necessary to make the goal entities unambigiuous from the other entities in the world. then, s-struct prunes the grammar of lexicalized trees that, given the goal, will never be used. the resulting pruned grammar will be able to express relations between goal entities and will contain trees that satisfy semantic constraints that may not be explicitly mentioned in the goal (e.g., a complementizer "that" tree). it will also be able to express at least one referring-expression for each unique entity (e.g., if we need to generate a "cat" entity, we may need to clarify whether it is black or brown). we observe that once trees are pruned, any associated entities and relations in the world can be pruned as well. this world pruning reduces the space of possible bindings, which we have empirically verified results in a significant speed increase without impacting accuracy. we call this version of s-struct with world pruning s-struct v2. once this pruning is completed, to generate a sentence, s-struct uses the uct @xcite procedure (see figure 2 ) to plan in an mdp. states in the mdp are semantically an-notated partial trees reflecting the partial sentence constructed so far. actions adjoin or substitute a single pltag tree. at each step, s-struct ranks actions to add a new fragment to the current partial tree. if there are unexplored actions, it chooses such an action to explore. otherwise, it chooses actions based on the uct ranking, which balances explore/exploit criteria. to estimate the downstream quality of the action, s-struct looks ahead by a number of exploratory actions that are uniformly sampled. for each action, s-struct finds the reward of each state reached, propagating the rewards up the search tree. these rewards identify the best action at a state. the reward is largely determined by how well the partial sentence matches the semantics of the goal. to do this, s-struct considers bindings between entities in the partial sentences and the goal. here, a valid binding between entities is one in which the stated semantic information does not disagree (e.g., we have a cat in the partial sentence that is white and a cat in the goal that is white and long-haired). in the reward, s-struct only receives credit when a goal entity has a valid biding to a partial-sentence entity. the reward also considers the number of entities missing a determiner, the number of partialsentence entities with no goal bindings, the number of world bindings, and the length of the sentence. the first two characteristics penalize missing information. the number of world bindings reflects potential ambiguity in the sentence. finally, the last criterion reflects the fact that given two sentences, both of which express the goal semantics precisely, we prefer the shorter sentence. the action search procedure returns the action with the best reward. s-struct applies this action and updates the partial sentence. if a terminal state is reached in which adding more actions will not improve the reward or the generation process runs out of time, then this sentence is returned. if not, the action search repeats. in subsequent searches, we may be able to reuse parts of the search tree of exploratory actions as some will still be relevant in the new state. to improve search efficiency, the search in s-struct is carried out in two phases. first, only substitution actions are considered until all substitution nodes in the pltag tree are filled. then, adjoin actions (and some substitutions if required by the added adjoins) are considered to complete the generation. this reduces the branching factor of the search considerably, speeding up the process. ## hs-struct: s-struct with hybrid semantics in this section, we describe how we modify s-struct to use distributional semantics. we first describe how we compose distributional semantics and how the distributional reward is computed. then, we describe additional modifications required by using imprecise semantics in the search, including a step to correct word ordering errors and using a beam search instead of a greedy search in uct. ## conclusion we have presented hs-struct, which uses both distributional and logical semantics for goaldirected language generation. by taking a hybrid approach hs-struct's generation scales significantly better in early phases. however, in some cases, the quality of the final generation can be lower than a pure logical approach. hs-struct is available through github upon request.