Finding Missing Categories in Incomplete Utterances (2017)

Abstract: Finding Missing Categories in Incomplete Utterances This paper introduces an efficient algorithm (O(n4 )) for finding a missing category in an incomplete utterance by using unification technique as when learning categorial grammars, and dynamic programming as in Cocke–Younger–Kasami algorithm. Using syntax/semantic interface of categorial grammar, this work can be used for deriving possible semantic readings of an incomplete utterance. The paper illustrates the problem with running examples.

## introduction this paper is a part of the author's ph.d. proposal regarding possible semantic readings of a given utterance with ranking. an utterance may yield several readings either from ambiguities (lexical, syntactical and semantical) or from syntactic incompleteness. the incomplete utterances can be linguistically considered as a type of non-canonical utterances @xcite and they can be caused by different reasons such as missing categories, extra categories, swap categories, misused categories, or any possible combination of mentioned reasons. the focus in this paper is on incomplete utterances with one missing category. to make our research problem clear we should emphasize that by the missing category one can generally suppose two things : a missed word in an incomplete sentence or an unknown word in a sentence with no proper category assignment. in this paper we especially deal with the problem of a missing category for a missing word in an incomplete sentence. moreover, we assume that the position of the word in the sentence is unknown. so obviously, our task is to find the possible position(s) of a missing word and its proper category assignment. syntactic analysis of incomplete utterances has been the subject of study in rule-based, data-driven and statistical approaches in computational linguistics @xcite . the scope of automatic error detection/fixation and robust parsing is so wide and different mechanisms are introduced by researchers such as 1 : over-generating and ranking parse trees @xcite , imposing ranking constraints on grammatical rule @xcite , introducing "mal-rules" @xcite , relaxing constraints in feature unification @xcite , modeling grammar as model-theoretic constraints @xcite @xcite , and finally, sub-tree parse fitting for non-parsable utterances. @xcite . all the mentioned approaches have their own advantages, and address the same issue that we have defined. however, the formalisms that are introduced in them is not the same as what is used in this paper. basic categorial grammars or ab grammars, is a formalism which is used in this research. it is a family of the categorial grammars. this choice is based on the requirement to bridge the incomplete utterances with semantical readings (author's ph.d. proposal). there are a number of reasons to explain why categorial grammars are suitable for our specific research topic : firstly, categorial grammars have a very nice correspondence with semantics and they are very suitable for syntacticsemantic interface modeling ; they can represent semantic ambiguities such as quantifier scope and negation @xcite , chapter 3) which does not exist in shallow approaches ; secondly, they enjoy learn-ability property from positive sentences which converge after learning a fixed number of sentences by using unification techniques @xcite ; thirdly, by applying a left-to-right incremental procedure and proof net construction for categorial grammar we can correctly predict a wide variety of human performance phenomena such as garden-pathing, preference for lower attachment, left-to-right quantifier scope preference @xcite ; finally, there is a wide-coverage syntactic and semantic parsing for french language, named grail, that allows researchers to design and experiment with multimodal categorial grammars which includes ab grammars as well. @xcite . grail is a modern, flexible and robust parser/automated theorem prover that has around 900 different category types for french language and works efficiently with the newspaper articles. categorial grammar is extracted semi-automatically from the paris 7 tree-bank and its semantic lexicon maps combinations of words, part-of-speech tags and formulas to discourse representation structures @xcite ). 2 our strategy for resolving incomplete utterances is based on using ab grammars as the basis of our syntactic formalism on the one hand, and adopting the notion of unification that exists in rg algorithm (learning rigid ab grammars) @xcite plus some dynamic programming technique on the other hand. this approach, to the best of our knowledge, is a new research technique that can efficiently deal with incomplete utterances with missing categories while benefiting from the good properties in categorial grammars. as we will see, the time complexity for the algorithm that we use to find one missing category with n number of words is o(n 4 ). this research can be extended to more missing categories, and other kind of incomplete utterances as we will discuss in the conclusion section. since this paper is self-contained, we have introduced some basic notions and definitions in section (2) which is essential for understanding ab grammars and notion of categorial unification. moreover, 1. see @xcite , chapter 1) for detailed descriptions. 2. as for the behaviour of the grail parser on the sentences containing an unknown word we should say that the widecoverage version of the grail parser uses a probabilistic model to propose one or more of the contextually most likely options. it is worth mentioning that our proposal can be used for finding missed words ; although it can be adopted for finding categories for unknown words as well. there are a number of running examples and illustrations on other sections to make notions more clearer. section (3) discusses unification technique of rg algorithm, and how this mechanism can be adopted for finding the missing category with some examples and the possible combinations of the structural tree. section (4) illustrate informally how unification technique and the notion of dynamic programming can be tackled with using bottom-up parsing in a modified version of well-known dynamic cyk algorithm. section (5) concludes our approach and explains possible direction in future studies. we have also included an appendix that contains the pseudo-code of our algorithm provided with discussions on the complexity of the algorithm. ## reminder of ab grammars and unification here, ab grammars, and some essential notions are discussed very quickly. as highlighted, this formalism is very suitable for our purpose since it enjoys learn-ability from positive examples and it converges after learning from a fixed number of sentence structures. @xcite @xcite definition 1 : categories taking lambek's notation @xcite , categories in ab grammars can be written as follows @xcite , chapter 1) : a function lex is a lexicon which maps words to finite set of categories. an expression, that is a sequence of words or terminals w 1 , • • • , w n is of category u whenever there exists for each it is worth mentioning that variable categories are also used such as it is basically a tree-structured proof representation with variable categories instead of having fixed categories. the only exception is fixed category s in the root of the tree which is naturally expected. arguments will have unique variable while the functors would get the argument category as its sub-formula in the right or left side. all the possible structural trees of a sequence with 3 words are represented in figure 1 . for convenient, when we use the term structural tree we mean the structural tree with variable categories. it can be easily noticed that the number of possible trees for a sequence of string with n length would be catalan(n -1) * 2 n-1 in which catalan(n -1) is the number of possible binary trees and 2 n-1 is the number of possible operations for \ and / over each binary sub-trees. 3 in the case of a sentence with 3 unspecific words, the number of all possible structural trees is 8 (= catalan(3 -1) * 2 2 ) as it can be observed in the figure 1 ## unification technique of rg algorithm the unification technique which is used here is introduced for the first time in learning rigid ab grammars algorithm @xcite and it has been re-studied and extended by some researchers as well @xcite @xcite . we are using almost the same technique, but with a new purpose which is dealing with incomplete utterances with one missing category that to our knowledge is a new field to experience. since we have explained the essential notions, we just focus on some examples to highlight the mechanism of unification in this section. let us consider the following lexicon which is adopted for our illustration purpose, and it is assumed that the lexicon is already learned from the positive sentences in corpus 5 . now, we consider the following examples where a category is missing. one missing determiner in example (3) and one missing preposition in example (4) : example 2 : lexicon le , la : np/n dans : (s\s)/np poisson , mer : n nage : np\s vite : (np\s)\(np\s) example 3 : * poisson nage vite. example 4 : * le poisson nage vite la mer. let us start with example (3). as it is illustrated in figure 2 we have illustrated only three cases. (just note that without knowing the categories of words there would be 160 (= catalan(3) * 2 3 * (3 + 1)) possible functor-argument tree structures that can be associated to example 3). we can unify the gained variable categories associated to the words in our structural trees with the one we have in our lexicon (figure 2 ). s (a) ## ab grammars, unification and dynamic programming as we saw in the previous section, for (unknown) n sequence of words the possible structural trees are (= catalan(n -1) * 2 n-1 ) and also the number of positions for a missing category is n + 1. 6 the final number of different combinations of a n sequence of words with one missing category @xmath0. actually, we do not need to explore all the possible structural trees since we know that some of our categories are fixed. in this section, we illustrate how the problem in example (4) can be tackled with dynamic bottom-up parsing. the idea behind our solution is to try all the (n+1) positions for the missing category and avoiding searching all the possible structural trees by early pattern matching and unification technique of rg algorithm using a modified version of cyk dynamic programming technique 7 . with this strategy we can save each step results for making decision as we go further. as we will see, this leads us to an efficient computational complexity of o(n 4 ) with n number of words. the the the notice that we have included question mark(= ?) in the cells of x 2 and x 3 to signify that we have not performed the pattern matching yet. our algorithm benefits from early pattern matching of variable categories with the lexicon or any external reference that provides categories 10 . note that all the possible substitutions for x 1 , namely ((np\s)\(np\s))\x 2 and x 3 /(np/n) fail in pattern matching phase ; since, there is no fixed type category (and even none subcategory) in our lexicon that can be matched with them. early matching is an efficient technique since it prevents unnecessary computation. as depicted in step (3) in again, we will follow the same procedure that we practiced for step 3 in although, x 6 /np matches with some categories in our lexicon so we will keep it as we go to the next step. we will continue the same procedure until we will reach to step 7 which is the last one. in in this section, we informally analyzed how our modification to cyk algorithm can be useful in finding a missing category using early pattern matching and unification in learning rg algorithm. the relevant algorithm and its computational complexity are discussed in the appendix. ## conclusion and possible extensions we explained how we can find one missing category in an incomplete utterance. the method is basically designed for aren project (argumentation et numérique) in which the average number of words in a sentence is twenty and the number of categorial types are around two hundred, so our proposal efficiently works on this specific domain. there are four possible extensions for our future study and research. the first extension is moving to non-rigid categories, namely fixed number of several categories assigned to each single word-instead of rigid ones. since our approach benefits from chart parsing, this is, in principle, tractable. however, it will increase our computational complexity as it is expected. we can reduce our search space when we have lexical ambiguities (several categories for each word of the input sentence) by adopting super-tagging technique @xcite . the one which is very suitable for our purpose is moot's super-tagger @xcite which is implemented in the wide-coverage version of the grail parser. the second extension is to focus on several numbers of missing categories, instead of just one. of course, we need to limit the number of missing categories, since, comprehension of sentences with so many missing categories is so hard even for human users of language, nevertheless, it will be useful if we stay limited to fixed number of categories. one, primitive suggestion would be trying all the possible combinations of k missing words. this solution would have some drawbacks since we need to know the accurate number of missing categories, and more important, we should consider the increasing number of categories. it is difficult to rule out these categories by early pattern matching. one of the approaches would be using jenson's approach @xcite to build possible structural sub-trees of an incomplete utterance to find a limited number of suggestion for the position of missing categories. further study is required for more clarification. the third extension is to tackle other classes of incomplete utterances such as extra categories, misused categories, swap categories or any possible combinations. the main problem with this approach is the need of having a computational mechanism to know what is the exact problem of a sentence before solving it. for instance, if we know that in a given utterance, we have the fixed numbers of missing words, extra words, and swap categories, then we can tackle the problem more efficiently with a different module that we might build. the author has designed an algorithm that transforms a context free grammar into constraint handling rules (implemented in prolog) for a fragment of natural language with relative clauses. nevertheless, still, we need to have more research and study to analyses the efficiency and suitability of this kind of approaches comparing to the approaches that do not consider such distinctions. the fourth extension is working on other families of categorial grammars such as lambek's calculus @xcite or some restricted version of partial proof trees @xcite for categorial grammar. the main problem -that the author is still dealing with-is that partial proof trees need to be restricted in order to work with lambek's calculus. moreover, designing a computationally decidable system with efficient complexity for incomplete utterances is still an on-going research. generally speaking, this line of research can possibly be helpful in the domain of incoherence discourses. for instance, writing-assistant systems with questionnaires, for some specific targeted users such as patients suffering from specific mental disorders. as discussed in the introduction, categorial grammar is chosen for its excellent correspondence with semantic. we drew the attention of readers to a special case, namely missing quantifier in the incomplete utterances. once the missing quantifier is found out, we can make a complete sentence, and deduce different semantic readings of the utterance. since each semantic proof corresponds to a cut-free proof net, we can make different complexity profiles having different proof nets gained from different readings. the low complexity profile will have the preferred reading among other readings @xcite . this is the main role of categorial grammars in modeling preferences of semantic readings that naturally makes our syntax-semantic interface work.