Hot answers tagged

13

Short answer There is a favoured structure for storing ambiguous parse trees. It is usually called a shared forest, and it is simply a grammar that generates only the sentence parsed with exactly the same parse trees as the grammar of the language (up to a renaming homomorphisme for the non-terminal symbols). This applies to Context-Free grammars, but also ...


11

Kübler, Sandra, Ryan McDonald, and Joakim Nivre. "Dependency parsing." Synthesis Lectures on Human Language Technologies 1.1 (2009): 1-127. Chapter 6: Evaluation > Section 6.1: Evaluation metrics The standard methodology for evaluating dependency parsers, as well as other kinds of parsers, is to apply them to a test set taken from a treebank and ...


11

Parsing speed obviously depends on a lot of factors, but in this case I would say that algorithmic complexity is the most important. The transition-based dependency parsers (all except MSTParser and RelEx) use greedy decoding and achieve linear complexity (or quadratic in the case of the Covington algorithm). This should be compared to the constituency-based ...


8

Michael Collins gives a nice explanation in his MOOC on NLP, summarized in this slide: In short: with the usual CKY algorithm in PCFG parsing, which is based on dynamic programming and yields a constituency-based tree, you have a time complexity of O(n^3 * G^3) as the dynamic programming algorithm is also looking for which non-terminal to choose (hence G^3)...


7

I asked Michael Covington, whose name is on one of the faster parsers, and he replies: I don't know the inner workings of any of these parsers (not even the one with my name on it, which was implemented by Joakim Nivre). Choice of programming language may have a lot to do with it. Another factor is that with dependency parsing, the search space can be ...


7

This phenomenon is called zero copula. It especially common for third person present tense. I recommend that you read on how this is handled in syntax parsers for Russian or Hindi. It was also an issue for Irish, Hungarian, Japanese, Turkish, Arabic and many other languages.


6

All headed constituency-based structures (i.e. endocentric structures) can be easily translated to the corresponding dependency-based structures. One need merely collapse all the projections (minimal, intermediate, and maximal) of a word down to one node. A non-headed constituency-based structure (i.e. it has exocentric structures), however, cannot be ...


6

As you correctly note, ambiguity is rampant in natural language and whatever data structure is used for parsing in ambiguous grammars must somehow represent a large number of possible derivations. Despite this, it's not feasible to represent every possible derivation as an explicit parse tree, because the number of possible bracketings of a string is its ...


6

This is almost certainly done with LaTeX, or one of its friends, and the tikz-qtree package. It is an improvement of the qtree package with nicer node placement. If you are not familiar with LaTeX, and want to learn more, this Wikibook might help (link is to the page about linguistics, but the book is in general about LaTeX). Both tikz-qtree and qtree have a ...


5

There are several factors at play: The implementation language: C/C++ is faster than Java is faster than Python The algorithm: Most of the constituent parsers, as well as MSTParser, use a dynamic programming approach with O(N^3) time consumption. The ones with "Nivre" in the name use a stepwise deterministic approach with O(N) time consumption. The "...


5

Earley parser is one example of chart parser, also called dynamic programming parser. There are many other kinds such as the CYK parser, the GLR and GLL parser, and more. The whole point of chart parsing is to build a unique chart that will mimic all possible parsing computations, since there may be exponentially many (or even infinitely many in ...


4

(I guess the answer goes here, not the comments; oops.) According to this reference (http://bulba.sdsu.edu/jeanette/thesis/PennTags.html), SBAR is "SBAR - Clause introduced by a (possibly empty) subordinating conjunction." In this case, that conjunction is 'after'. There are two S because 'she ate the cake' is an S, embedded within the larger S via the ...


4

A nice study: Kummerfeld, Jonathan K., et al. "Parser showdown at the wall street corral: An empirical investigation of error types in parser output." Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning. Association for Computational Linguistics, 2012. Abstract: ...


4

I think you are talking about joint POS tagging and parsing. If you do not limit yourself to the neural network framework. The following paper can help: graph-based parser: Joint models for Chinese POS tagging and dependency parsing: http://ir.hit.edu.cn/~car/papers/emnlp11.pdf transition-based parser: Incremental Joint POS Tagging and Dependency Parsing ...


4

The top parsers like spaCy, Stanford and Google unfortunately only return one parse, although in many cases another parse is nearly equally probable. However, the always helpful Matt from spaCy explained to me in https://github.com/explosion/spaCy/issues/238 how to get the underlying options and even the probabilities: import numpy as np import plac ...


4

Parsing is mostly an important building block used for improving the performance of downstream tasks, not as an application per se. So, for example, if we are training NER, it helps to hint to the model what the parser guesses the noun phrases are. Similar for dialogue systems, translation and so on. See also: POS language model. In the old days (before ...


3

I suppose you mean a rule-based parser since nobody would think of developing his own statistical parser (there are so many good open-source libraries). Building a parser is quite complicated. The best way is to have a context-free grammar (CF parsing is trivial) and build up the dependency structures via constraint rules. This is how LFG works, whose f-...


3

Science must be reproducible, and closely connected to experimental data. This has consequences on scientific practice, and in particular on the how experimental resources and copora should be dealt with, which can be translated in what I would consider rules of scientific ethics (which are not confined to linguistics): A corpus of data should be precisely ...


3

Since the one has an article, it seems fair to treat it like a (pro)noun, so it functions as a noun subject complement. For whom you are looking is as a whole a relative clause modifying the one, so I would make it one branch from the "predicate nominative" down, so the two branches would be the one and for whom you are looking. Then I would probably ...


3

After going through a number of examples, I think I got meaning of *NONE* in parse tree output. Let's take an example, suppose we have to parse following sentence: Ricky is a boy and likes fruits. In above sentence two sentences are joined with coordinating conjunction and. Sentence 1: Ricky is a boy. Sentence 2: likes fruits. In first sentence subject ...


3

I've just seen your question, I don't know whether it's still relevant, but here you have a paper that describes how to projectivise a dependency tree. http://www.aclweb.org/anthology/P05-1013


3

Thanks for your question. This example reflects a larger problem in grammaticizing language. Roughly speaking there are two approaches: Generative and descriptive. A parser is generative, presupposing that there are elementary and globally correct grammar rules whom all sentences in a language ideally abide by. Exceptions are accepted but are treated as “...


3

These are more or less like the word-sense disambiguation, anaphora resolution or co-reference resolution examples in the Winograd Schema Challenge and generally in natural language understanding. How far ahead do we look when parsing and understanding text? As you essentially show in your examples where the necessary information is not in the sentence, ...


3

Here is a script I quickly assembled from pieces of code I had lying around: https://trinket.io/python3/a33a025467?toggleCode=true&showInstructions=true Beware that this script parses your tree very naively; it just processes the input symbol by symbol and does some formatting when it encounters opening or closing brackets; it will not warn you if you ...


2

Yes, there are measures. Whether they are consistent or useful is subjective. A probabilistic parser like https://demos.explosion.ai/displacy or https://cloud.google.com/natural-language/ returns one parse. But under the hood, it had a few candidates and just chose the most probable one. If the even the first candidate had a low probability then we could ...


2

Of the two interpretations suggested in the question, I prefer the first. That is, upon my first reading of the example and the context in which it appears, I immediately concluded that the it is a standard anaphoric pronoun, referring back to the community. Only after reading the context and the alternative interpretation carefully was I able to get that ...


2

Projectivity is a concept that applies to both dependency grammars (DGs) and constituency grammars (CGs). The extent to which it is applicable to both approaches to syntax is discussed and illustrated with numerous trees here: https://en.wikipedia.org/wiki/Discontinuity_%28linguistics%29 The term itself, i.e. projectivity, was introduced in the 1960s in ...


2

If there are crossing lines in the syntactic tree, then one or more discontinuous dependencies is present. A projectivity violation is a discontinuous dependency. There are a lot of terms used to denote such dependencies, many of which are listed at the start of that Wikipedia article (discontinuous dependency, long distance dependency, displaced constituent,...


2

I'm actually a grad student on the team at Stanford that's been developing Stanford Dependencies (on which Universal Dependencies is based), so I think I can clarify things for you. You're assuming that SD and UD are theories, which they are not. They're frameworks for annotating strings of words, and they never claim to be predictive in any way. The goal ...


2

There are multiple competing procedures. Linguistics is still quite far from proving true even fractions of the grammar of any specific natural language. Even the most basic phenomena are interpreted differently in various paradigms. For the most obvious example: one important fraction within theoretical syntax, and at least historically the most important ...


Only top voted, non community-wiki answers of a minimum length are eligible