Two approaches to Robust Stochastic Parsing

NLP applications in all domains require more than a formal grammar to process the input in a practical way, because natural language contains phenomena that a formal grammar is usually not able to describe. Such phenomena are typically disfluencies and extra-grammaticality. Some robust technique is needed to deal with them. An important issue in the development of robust parsing techniques is the choice of flexibility. What precise phenomena outside the systems grammar shall the parser be able to handle? Another question is how to select the correct analysis among the great number of solutions, which are produced as a consequence of the flexibility. This report presents experiments done with two different techniques. One is based on the combination of partial parses, the other on controlled relaxation of grammar rules. In both techniques the selection of the ?best? analysis is done with a statistically based ranking procedure. The grammars and test sentences are extracted from two treebanks, ATIS and Susanne. Experimental results show that the first technique has the advantage of full coverage, while the other has a better accuracy. The best performance is achieved by parsing in three passes, first with the initial grammar, then with the rule-relaxation approach and finally, if still no analysis was found, with combination of partial analyses.

Modèles syntaxiques probabilistes non-génératifs

Antoine Rozenknop

This work deals with models used, or usable in the domain of Automatic Natural Language Processing, when one seeks a syntactic interpretation of a statement. This interpretation can be used as additional information for subsequent treatments, that can aim for instance at producing a semantic representation of the statement. It can also be used as a filter to select utterances belonging to a specific language, among several hypotheses, as done in Automatic Speech Recognition. As the syntactic interpretation of a statement is generally ambiguous with natural languages, the probabilisation of the space of syntactic trees can help in the analysis task : when several analyses are competing, one can then extract the most probable interpretation, or classify interpretations according to their probabilities. We are interested here in the probabilistic versions of Context-Free Grammars (PCFGs) and Substitution Tree Grammar (PTSGs). Syntactic treebanks, which as much as possible account for the language we wish to model, serve as the basis for defining the probabilistic parameters of such grammars. First, we exhibit in this thesis some drawbacks of the usual learning paradigms, due to the use of arbitrary heuristics (STSG DOP model), or to the use of learning criteria that consider these grammars as generative ones (creation of sentences from the grammar) rather than dedicated to analysis (creation of analyses from the sentence). In a second time, we propose new methods for training grammars, based on the traditional Maximum Entropy and Maximum Likelihood criteria. These criteria are instanciated so that they correspond to a syntactic analysis task rather than a language generation task. Specific training algorithms are necessary for their implementation, but traditional algorithms can cope with those models for the task of syntactic analysis. Lastly, we invest the problem of time complexity of syntactic analysis, which is a real issue for the effective use of PTSGs. We describe classes of PTSGs that allow the analysis of a sentence in polynomial complexity. We finally describe a method that enable the extraction of such a PTSG from the set of subtrees of a treebank. The PTSG produced by this method allows us to test our non-generative learning criterium on "realistic" data, and to give a statistical comparison between this criterium and the usual heuristic criterium in term of analysis performance.

EPFL2003

Harmonic Syntax in Time: Rhythm Improves Grammatical Models of Harmony

Daniel Harasim, Martin Alois Rohrmeier

Music is hierarchically structured, both in how it is perceived by listeners and how it is composed. Such structure can be elegantly captured using probabilistic grammatical models similar to those used to study natural language. They address the complexity of the structure using abstract categories in a recursive formalism. Most existing grammatical models of musical structure focus on one single dimension of music–such as melody, harmony, or rhythm. While these grammar models often work well on short musical excerpts, accurate analysis of longer pieces requires taking into account the constraints from multiple domains of structure. The present paper proposes abstract product grammars–a formalism which integrates multiple dimensions of musical structure into a single grammatical model–along with efficient parsing and inference algorithms for this formalism. We use this model to study the combination of hierarchically-structured harmonic syntax and hierarchically-structured rhythmic information. The latter is modeled by a novel grammar of rhythm that is capable of expressing temporal regularities in musical phrases. It integrates grouping structure and meter. The combined model of harmony and rhythm outperforms both single-dimension models in computational experiments. All models are trained and evaluated on a treebank of hand-annotated Jazz standards.

ISMIR2019

Modèles syntaxiques probabilistes non-génératifs

Antoine Rozenknop

EPFL2003