A Survey of the Usages of Deep Learning in Natural Language Processing <s> Parsing <s> Constructing a grammar which can parse sentences selected from a natural language corpus is a difficult task. One of the most serious problems is the unmanageably large number of ambiguities. Pure syntactic analysis based only on syntactic knowledge will sometimes result in hundreds of ambiguous parses. <s> BIB001 </s> A Survey of the Usages of Deep Learning in Natural Language Processing <s> Parsing <s> In automatic speech recognition, language models can be represented by Probabilistic Context Free Grammars (PCFGs). In this lecture we review some known algorithms which handle PCFGs; in particular an algorithm for the computation of the total probability that a PCFG generates a given sentence (Inside), an algorithm for finding the most probable parse tree (Viterbi), and an algorithm for the estimation of the probabilities of the rewriting rules of a PCFG given a corpus (Inside-Outside). Moreover, we introduce the Left-to-Right Inside algorithm, which computes the probability that successive applications of the grammar rewriting rules (beginning with the sentence start symbol s) produce a word string whose initial substring is a given one. <s> BIB002 </s> A Survey of the Usages of Deep Learning in Natural Language Processing <s> Parsing <s> Abstract : As a result of this grant, the researchers have now published oil CDROM a corpus of over 4 million words of running text annotated with part-of- speech (POS) tags, with over 3 million words of that material assigned skeletal grammatical structure. This material now includes a fully hand-parsed version of the classic Brown corpus. About one half of the papers at the ACL Workshop on Using Large Text Corpora this past summer were based on the materials generated by this grant. <s> BIB003 </s> A Survey of the Usages of Deep Learning in Natural Language Processing <s> Parsing <s> The assignment of probabilities to the productions of a context-free grammar may generate an improper distribution: the probability of all finite parse trees is less than one. The condition for proper assignment is rather subtle. Production probabilities can be estimated from parsed or unparsed sentences, and the question arises as to whether or not an estimated system is automatically proper. We show here that estimated production probabilities always yield proper distributions. <s> BIB004 </s> A Survey of the Usages of Deep Learning in Natural Language Processing <s> Parsing <s> Deterministic dependency parsing is a robust and efficient approach to syntactic parsing of unrestricted natural language text. In this paper, we analyze its potential for incremental processing and conclude that strict incrementality is not achievable within this framework. However, we also show that it is possible to minimize the number of structures that require non-incremental processing by choosing an optimal parsing algorithm. This claim is substantiated with experimental evidence showing that the algorithm achieves incremental parsing for 68.9% of the input when tested on a random sample of Swedish text. When restricted to sentences that are accepted by the parser, the degree of incrementality increases to 87.9%. <s> BIB005 </s> A Survey of the Usages of Deep Learning in Natural Language Processing <s> Parsing <s> This paper describes the development of QuestionBank, a corpus of 4000 parse-annotated questions for (i) use in training parsers employed in QA, and (ii) evaluation of question parsing. We present a series of experiments to investigate the effectiveness of QuestionBank as both an exclusive and supplementary training resource for a state-of-the-art parser in parsing both question and non-question test sets. We introduce a new method for recovering empty nodes and their antecedents (capturing long distance dependencies) from parser output in CFG trees using LFG f-structure reentrancies. Our main findings are (i) using QuestionBank training data improves parser performance to 89.75% labelled bracketing f-score, an increase of almost 11% over the baseline; (ii) back-testing experiments on non-question data (Penn-II WSJ Section 23) shows that the retrained parser does not suffer a performance drop on non-question material; (iii) ablation experiments show that the size of training material provided by QuestionBank is sufficient to achieve optimal results; (iv) our method for recovering empty nodes captures long distance dependencies in questions from the ATIS corpus with high precision (96.82%) and low recall (39.38%). In summary, QuestionBank provides a useful new resource in parser-based QA research. <s> BIB006 </s> A Survey of the Usages of Deep Learning in Natural Language Processing <s> Parsing <s> The Conference on Computational Natural Language Learning is accompanied every year by a shared task whose purpose is to promote natural language processing applications and evaluate them in a standard setting. In 2008 the shared task was dedicated to the joint parsing of syntactic and semantic dependencies. This shared task not only unifies the shared tasks of the previous four years under a unique dependency-based formalism, but also extends them significantly: this year's syntactic dependencies include more information such as named-entity boundaries; the semantic dependencies model roles of both verbal and nominal predicates. In this paper, we define the shared task and describe how the data sets were created. Furthermore, we report and analyze the results and describe the approaches of the participating systems. <s> BIB007 </s> A Survey of the Usages of Deep Learning in Natural Language Processing <s> Parsing <s> This paper examines the Stanford typed dependencies representation, which was designed to provide a straightforward description of grammatical relations for any user who could benefit from automatic text understanding. For such purposes, we argue that dependency schemes must follow a simple design and provide semantically contentful information, as well as offer an automatic procedure to extract the relations. We consider the underlying design principles of the Stanford scheme from this perspective, and compare it to the GR and PARC representations. Finally, we address the question of the suitability of the Stanford scheme for parser evaluation. <s> BIB008 </s> A Survey of the Usages of Deep Learning in Natural Language Processing <s> Parsing <s> For the 11th straight year, the Conference on Computational Natural Language Learning has been accompanied by a shared task whose purpose is to promote natural language processing applications and evaluate them in a standard setting. In 2009, the shared task was dedicated to the joint parsing of syntactic and semantic dependencies in multiple languages. This shared task combines the shared tasks of the previous five years under a unique dependency-based formalism similar to the 2008 task. In this paper, we define the shared task, describe how the data sets were created and show their quantitative properties, report the results and summarize the approaches of the participating systems. <s> BIB009 </s> A Survey of the Usages of Deep Learning in Natural Language Processing <s> Parsing <s> We describe a shared task on parsing web text from the Google Web Treebank. Participants were to build a single parsing system that is robust to domain changes and can handle noisy text that is commonly encountered on the web. There was a constituency and a dependency parsing track and 11 sites submitted a total of 20 systems. System combination approaches achieved the best results, however, falling short of newswire accuracies by a large margin. The best accuracies were in the 80-84% range for F1 and LAS; even part-ofspeech accuracies were just above 90%. <s> BIB010 </s> A Survey of the Usages of Deep Learning in Natural Language Processing <s> Parsing <s> In this work, we present a general compositional vector framework for transitionbased dependency parsing. The ability to use transition-based algorithms allows for the application of vector composition to a large set of languages where only dependency treebanks are available, as well as handling linguistic phenomena such as non-projectivities which pose problems for previously proposed methods. We introduce the concept of a Transition Directed Acyclic Graph that allows us to apply Recursive Neural Networks for parsing with existing transition-based algorithms. Our framework captures semantic relatedness between phrases similarly to a constituency-based counterpart from the literature, for example predicting that “a financial crisis”, “a cash crunch” and “a bear market” are semantically similar. Currently, a parser based on our framework is capable of achieving 86.25% in Unlabelled Attachment Score for a well-established dependency dataset using only word representations as input, falling less than 2% points short of a previously proposed comparable feature-based model. <s> BIB011 </s> A Survey of the Usages of Deep Learning in Natural Language Processing <s> Parsing <s> We propose the first implementation of an infinite-order generative dependency model. The model is based on a new recursive neural network architecture, the Inside-Outside Recursive Neural Network. This architecture allows information to flow not only bottom-up, as in traditional recursive neural networks, but also topdown. This is achieved by computing content as well as context representations for any constituent, and letting these representations interact. Experimental results on the English section of the Universal Dependency Treebank show that the infinite-order model achieves a perplexity seven times lower than the traditional third-order model using counting, and tends to choose more accurate parses in k-best lists. In addition, reranking with this model achieves state-of-the-art unlabelled attachment scores and unlabelled exact match scores. <s> BIB012 </s> A Survey of the Usages of Deep Learning in Natural Language Processing <s> Parsing <s> Syntactic parsing is a fundamental problem in computational linguistics and Natural Language Processing. Traditional approaches to parsing are highly complex and problem specific. Recently, Sutskever et al. (2014) presented a domain-independent method for learning to map input sequences to output sequences that achieved strong results on a large scale machine translation problem. In this work, we show that precisely the same sequence-to-sequence method achieves results that are close to state-of-the-art on syntactic constituency parsing, whilst making almost no assumptions about the structure of the problem. To achieve these results we need to mitigate the lack of domain knowledge in the model by providing it with a large amount of automatically parsed data. <s> BIB013 </s> A Survey of the Usages of Deep Learning in Natural Language Processing <s> Parsing <s> Almost all current dependency parsers classify based on millions of sparse indicator features. Not only do these features generalize poorly, but the cost of feature computation restricts parsing speed significantly. In this work, we propose a novel way of learning a neural network classifier for use in a greedy, transition-based dependency parser. Because this classifier learns and uses just a small number of dense features, it can work very fast, while achieving an about 2% improvement in unlabeled and labeled attachment scores on both English and Chinese datasets. Concretely, our parser is able to parse more than 1000 sentences per second at 92.2% unlabeled attachment score on the English Penn Treebank. <s> BIB014 </s> A Survey of the Usages of Deep Learning in Natural Language Processing <s> Parsing <s> Because of their superior ability to preserve sequence information over time, Long Short-Term Memory (LSTM) networks, a type of recurrent neural network with a more complex computational unit, have obtained strong results on a variety of sequence modeling tasks. The only underlying LSTM structure that has been explored so far is a linear chain. However, natural language exhibits syntactic properties that would naturally combine words to phrases. We introduce the Tree-LSTM, a generalization of LSTMs to tree-structured network topologies. Tree-LSTMs outperform all existing systems and strong LSTM baselines on two tasks: predicting the semantic relatedness of two sentences (SemEval 2014, Task 1) and sentiment classification (Stanford Sentiment Treebank). <s> BIB015 </s> A Survey of the Usages of Deep Learning in Natural Language Processing <s> Parsing <s> We introduce a globally normalized transition-based neural network model that achieves state-of-the-art part-of-speech tagging, dependency parsing and sentence compression results. Our model is a simple feed-forward neural network that operates on a task-specific transition system, yet achieves comparable or better accuracies than recurrent models. We discuss the importance of global as opposed to local normalization: a key insight is that the label bias problem implies that globally normalized models can be strictly more expressive than locally normalized models. <s> BIB016 </s> A Survey of the Usages of Deep Learning in Natural Language Processing <s> Parsing <s> Recently, neural network approaches for parsing have largely automated the combination of individual features, but still rely on (often a larger number of) atomic features created from human linguistic intuition, and potentially omitting important global context. To further reduce feature engineering to the bare minimum, we use bi-directional LSTM sentence representations to model a parser state with only three sentence positions, which automatically identifies important aspects of the entire sentence. This model achieves state-of-the-art results among greedy dependency parsers for English. We also introduce a novel transition system for constituency parsing which does not require binarization, and together with the above architecture, achieves state-of-the-art results among greedy parsers for both English and Chinese. <s> BIB017 </s> A Survey of the Usages of Deep Learning in Natural Language Processing <s> Parsing <s> Recent work has proposed several generative neural models for constituency parsing that achieve state-of-the-art results. Since direct search in these generative models is difficult, they have primarily been used to rescore candidate outputs from base parsers in which decoding is more straightforward. We first present an algorithm for direct search in these generative models. We then demonstrate that the rescoring results are at least partly due to implicit model combination rather than reranking effects. Finally, we show that explicit model combination can improve performance even further, resulting in new state-of-the-art numbers on the PTB of 94.25 F1 when training only on gold data and 94.66 F1 when using external data. <s> BIB018
Parsing examines how different words and phrases relate to each other within a sentence. There are at least two distinct forms of parsing: constituency parsing and dependency parsing  . In constituency parsing, phrasal constituents are extracted from a sentence in a hierarchical fashion. Phrases are identified, which in turn form larger phrases, eventually culminating in complete sentences. Dependency parsing on the other hand looks solely at the relationships between pairs of individual words. Most recent uses of deep learning in natural language parsing have been in the area of dependency parsing, within which there exists another major divide in types of solutions. Graph-based parsing constructs a number of parse trees that are then searched to find the correct one. Most graph-based approaches are generative models, in which a formal grammar, based on the natural language, is used to construct the trees  . Without such an approach, an immense number of trees would be produced, many of them being totally illogical. More popular in recent years than graph-based approaches have been transition-based approaches. In these approaches, only one parse tree is usually constructed. While a number of modifications have been proposed, the standard method of transition-based dependency parsing is to create a buffer containing all of the words in the sentence and stack containing only the ROOT label. Words are then pushed onto the stack, where connections, known as arcs, are made between the top two items. These arcs can either be right-arcs or left-arcs, depending on whether the top word (which is further right in the sentence) is dependent on the bottom word (which is further left), or the bottom word is dependent on the top. Once dependencies have been determined, words are popped off the stack. The process continues until the buffer is empty and only the ROOT label remains on the stack. Three major approaches are used to regulate the conditions in which each of the previously described actions takes place. In the arc-standard approach  BIB005 , all dependents are connected to a word before the word is connected to its parent. In the arc-eager approach  BIB005 , words are connected to their parents as soon as possible, regardless of whether or not their children are all connected to them. Finally, in the Swap-Lazy approach ], the arc-standard approach is modified to allow swapping of positions on the stack. This makes the graphing of non-projective edges possible. 3.3.1 Early Neural Parsing. Compared to many areas of NLP, parsing has only recently been introduced to the power of deep learning. One early application of deep learning to natural language processing, that of Scoher et al. [2013a; , included the use of RNNs with probabilistic context-free grammars (PCFGs) BIB004 BIB001 BIB002 , allowing for semantically different phrases to be parsed differently, even if their part-of-speech tags were identical. As far as the authors are aware, the first neural model to achieve state-of-the-art performance in parsing was that of BIB012 . Such performance was achieved on the Penn Treebank for both labeled attachment score (LAS) and unlabeled attachment score (UAS) by using an Inside-Out Recursive Neural Network, which used two vector representations (an inner and an outer) to allow both top-down and bottom-up flows of data. BIB013 created an LSTM with an attention mechanism in a syntactic constituency parser, which they tested on data from domains different from those of the test data (the English Web Treebank BIB010 and the Question Treebank BIB006 ] as opposed to the Wall Street Journal portion of the Penn Treebank BIB003 , showing that neural models can generalize between domains. Embeddings were first used in dependency parsing by BIB011 , laying the path for most recent attempts at natural language parsing. This approach used an RNN to create a directed acyclic graph. While this model did produce results within 2% of the state of the art (on the Wall Street Journal portion of the CoNLL 2008 Shared Task dataset BIB007 ), by the time it reached the end of a sentence, it seemed to have difficulty remembering phrases from early in the sentence. 3.3.2 Transition-Based Dependency Parsing. The basis for most major recent research in parsing is the work of BIB014 , who pushed the state of the art in both UAS and LAS on both English and Chinese datasets, scoring 92.2% UAS on the English Penn Treebank. They accomplished this by using a simple feedforward neural network as the decision maker in a transition-based parser. By doing so they were able to subvert the problem of sparsity persistent in the statistical models that were being heavily used. While they achieved state-of-the-art results, they noted the simplicity of their model as well as a number of areas in which it could be improved upon. The first of such areas was that of the search mechanism employed by the model. Chen and Manning used a simple greedy search, which was replaced by with a beam search. By doing this, they achieved a significant improvement, nearing the performance of the new state of the art. In addition to using beam search, improved upon Chen and Manning's work by using a deeper neural network with residual connections and a perceptron layer placed after the softmax layer. Furthermore, they were able to train on significantly more examples than typical by utilizing tri-training , a process in which potential data samples are fed to two other parsers, and those on which both of the parsers agree upon are used for training the primary parser. This approach became the state of the art with respective UAS and LAS scores of 94.26% and 92.41% on the Penn Treebank. further extended this work by testing several similar models on the Wall Street Journal dataset, the Web English Treebank dataset, and the Question Treebank data, as well as datasets from CoNLL 2009 BIB009 ] for a number of languages. State-of-the-art performance was achieved in both UAS and LAS on the three English datasets as well as for most of the languages tested from CoNLL 2009. Another model was produced using an LSTM instead of a feedforward network . Unlike previous models, this model was given knowledge of the entire buffer and the entire stack and had knowledge of the entire history of transition decisions. This allowed for better predictions, generating state-of-the-art UAS and LAS scores of 93.1% and 90.9%, respectively on the Stanford Dependency Treebank BIB008 , as well as state-of-the-art results on the CTB5 Chinese dataset  . Lastly, BIB016 used a feedforward network with global normalization on a number of tasks including part-of-speech tagging, sentence compression, and dependency parsing. State-of-the-art results were obtained on all tasks, including reaching a UAS score of 94.61% on the Wall Street Journal dataset. Notably, their model required significantly less computation than comparable models to achieve these results. At the time of writing of this survey, the state of the art is defined by another such transition-based dependency parser . Much like the work of Stenentorp [2013] , this model uses an alternative algorithm to produce directed acyclic graphs, rather than simple trees. In addition to the typical stack and buffer used in transition-based parsing, the algorithm employs a deque. This allows for the representation of multi-parented words, which although rare in English, are common in many natural languages. Furthermore, it allows for multiple children of the ROOT label. In addition to producing said graphs, this work is novel in its use of two new LSTM-based techniques: Bi-LSTM Subtraction and Incremental Tree-LSTM. Bi-LSTM Subtraction builds off of previous work BIB017  ] to represent the buffer as a subtraction of the vectors from the head and tail of the LSTM, in addition to using an additional LSTM to represent the deque. Incremental Tree-LSTM is an extension of Tree-LSTM BIB015 , modified for directed acyclic graphs instead of trees, by connecting children to parents incrementally, rather than connecting all children to a parent simultaneously. Both techniques were found to improve performance, and the model exercising both achieved the best published scores for fourteen of the sixteen evaluation metrics used on SemEval-2015 Task 18 (English)  and SemEval-2016 Task 9 (Chinese)  . 3.3.3 Generative Dependency and Constituent Parsing. While transition-based dependency parsing still remains successful, currently defining the state of the art, improvements have recently been attained by applying deep learning to constituency parsing and generative models. proposed a model that used recurrent neural network grammars for parsing and language modeling. Whereas most approaches take a bottom-up approach to parsing, this took a top-down approach, taking as input the full sentence in addition to the current parse tree. This allowed the sentence to be viewed as a whole, rather than simply allowing local phrases within it to be considered. While not attaining state-of-the-art results in all of parsing, this model achieved the best results in English generative parsing as well as in single sentence language modeling. It also attained results close to the best in Chinese generative parsing. The first model to achieve state-of-the-art results using a deep learning approach to generative parsing was that of Choe and Charniak [2016] . Parsing was treated as a language modeling problem, and an LSTM was used to assign probabilities to the parse trees. Using this approach, UAS and LAS scores of 95.9% and 94.1%, respectively, were achieved on the Penn Treebank. BIB018 considered both of these models and tested them to determine whether the power of these models came from the reranking process or simply from the combined power of two models. They found that while using one parser for producing candidate trees and another for ranking them was superior to a single parser approach, combining two parsers explicitly was preferable still. They used two parsers to both select the candidates and rerank them, achieving state-of-the-art results. They extended this model to use three parsers, achieving even better results, with an F1 score on the Penn Treebank of 93.4%. Finally, an ensemble of eight such models (using two parsers) was constructed and achieved the best results (94.25% F1 on Penn Treebank) prior to the model proposed by .