<!-- wp:html -->
<div class="post-header">
<div class="published"><span class="publishdate">Thursday, May 12, 2016</span></div>
</div>
<!-- /wp:html -->

<!-- wp:html -->
<div class="post-body">
<div class="post-content post-original"><span class="byline-author">Posted by Slav Petrov, Senior Staff Research Scientist</span><p></p>
<p>At Google, we spend a lot of time thinking about how <a href="http://googleresearch.blogspot.com/2013/12/free-language-lessons-for-computers.html">computer systems</a> can <a href="http://googleresearch.blogspot.com/2015/06/a-multilingual-corpus-of-automatically.html">read</a> and understand human<a href="http://googleresearch.blogspot.com/2014/08/teaching-machines-to-read-between-lines.html"> language</a> to<a href="http://googleresearch.blogspot.com/2014/04/a-billion-words-because-todays-language.html"> process it</a> in <a href="http://googleresearch.blogspot.com/2015/11/computer-respond-to-this-email.html">intelligent ways</a>. Today, we are excited to share the fruits of our research with the broader community by releasing <a href="https://github.com/tensorflow/models/tree/master/syntaxnet">SyntaxNet</a>, an open-source neural network framework implemented in <a href="https://www.tensorflow.org/">TensorFlow</a> that provides a foundation for <a href="https://en.wikipedia.org/wiki/Natural_language_understanding">Natural Language Understanding</a> (NLU) systems. Our version includes all the code needed to train new SyntaxNet models on your data, as well as <i>Parsey McParseface</i>, an English parser that we have trained for you and that you can use to analyze English text.</p>
<p>Parsey McParseface is built on powerful machine learning algorithms that learn to analyze the linguistic structure of language, and that can explain the functional role of each word in a given sentence. Because Parsey McParseface is the <a href="http://arxiv.org/abs/1603.06042">most accurate such model in the world</a>, we hope that it will be useful to developers and researchers interested in automatic extraction of information, translation, and other core applications of NLU.</p>
<p><b>How does SyntaxNet work?</b></p>
<p>SyntaxNet is a framework for what’s known in academic circles as a <a href="https://en.wikipedia.org/wiki/Parsing"><i>syntactic parser</i></a>, which is a key first component in many NLU systems. Given a sentence as input, it tags each word with a part-of-speech (POS) tag that describes the word's syntactic function, and it determines the syntactic relationships between words in the sentence, represented in the dependency parse tree. These syntactic relationships are directly related to the underlying meaning of the phrase in question. To take a very simple example, consider the following dependency tree for <i>Alice saw Bob</i>:</p>
<div class="separator"></div>
<figure><a href="https://3.bp.blogspot.com/-M-7PIST2hq8/VzTFhESMeuI/AAAAAAAAA_s/k4wOQe0UlnwmoVnZtuU6CNHw6xLQRN7egCLcB/s1600/asawb.png"><img class="aligncenter" src="https://3.bp.blogspot.com/-M-7PIST2hq8/VzTFhESMeuI/AAAAAAAAA_s/k4wOQe0UlnwmoVnZtuU6CNHw6xLQRN7egCLcB/s320/asawb.png" width="320" height="262" border="0"></a></figure><div class="separator"></div>
<p>This structure encodes that <i>Alice</i> and <i>Bob</i> are nouns and <i>saw</i> is a verb. The main verb <i>saw</i> is the root of the sentence and <i>Alice</i> is the subject (nsubj) of <i>saw</i>, while <i>Bob</i> is its direct object (dobj). As expected, Parsey McParseface analyzes this sentence correctly, but also understands the following more complex example:</p>
<div class="separator"></div>
<figure><a href="https://4.bp.blogspot.com/-1Ntx47T1WvU/VzTF2HgbqrI/AAAAAAAAA_w/UWofRQPhqU0ITD5HPQmEVCrwsEroCN8PQCLcB/s1600/long.png"><img src="https://4.bp.blogspot.com/-1Ntx47T1WvU/VzTF2HgbqrI/AAAAAAAAA_w/UWofRQPhqU0ITD5HPQmEVCrwsEroCN8PQCLcB/s640/long.png" width="640" height="202" border="0"></a></figure><div class="separator"></div>
<p>This structure again encodes the fact that <i>Alice</i> and <i>Bob</i> are the subject and object respectively of the <i>saw</i>, also, that <i>Alice</i> is modified by a relative clause with the verb <i>reading</i>, that <i>saw</i> is amended by the temporal modifier <i>yesterday</i>, and so on. The grammatical relationships encoded in dependency structures allow us to 20-year-old recover the answers to various questions, for example, <i>who did Alice see?</i> <i>who saw Bob?</i> <i>what had Alice been reading about?</i> Or <i>when did Alice see Bob?</i>.</p>
<p><b>Why is Parsing So Hard For Computers to Get Right?</b></p>
<p>One of the main problems that make parsing so challenging is that human languages show remarkable levels of ambiguity. It is not uncommon for moderate length sentences - say 20 or 30 words in length - to have hundreds, thousands, or even tens of thousands of possible syntactic structures. A natural language parser must somehow search through all of these alternatives, and find the most plausible structure given the context. As a very simple example, the sentence <i>Alice drove down the street in her car</i> has at least two possible dependency parses:</p>
<figure><a href="https://2.bp.blogspot.com/-cXYL6RGkV_g/VzTDzbh6yEI/AAAAAAAAA_Q/1c-76sGQ124oE9njB2E6QzU6KcxDCn0KgCLcB/s1600/drovedown.png"><img src="https://2.bp.blogspot.com/-cXYL6RGkV_g/VzTDzbh6yEI/AAAAAAAAA_Q/1c-76sGQ124oE9njB2E6QzU6KcxDCn0KgCLcB/s640/drovedown.png" width="640" height="136" border="0"></a></figure><div class="separator"></div>
<p>The first corresponds to the (correct) interpretation where Alice is driving in her car; the second corresponds to the (impossible, but possible) interpretation where the street is located in her car. The ambiguity arises because the preposition <i>in</i> can either modify <i>drove</i> or <i>street</i>; this example is an instance of what is called <i>prepositional phrase attachment ambiguity</i>.</p>
<p>Humans do a remarkable job of dealing with uncertainty, almost to the point where the problem is unnoticeable; the challenge is for computers to do the same. Multiple uncertainties such as these in longer sentences conspire to give a combinatorial explosion in the number of possible structures for a sentence. Usually, the vast majority of these structures are wildly implausible, but are nevertheless possible and must be somehow discarded by a parser.</p>
<p>SyntaxNet applies neural networks to the ambiguity problem. An input sentence is processed from left to right, with dependencies between words being incrementally added as each word in the phrase is considered. At each point in processing, many decisions may be possible—due to ambiguity—and a neural network gives scores for competing decisions based on their plausibility. For this reason, it is critical to use <i><a href="https://en.wikipedia.org/wiki/Beam_search">beam search</a></i> in the model. Instead of simply taking the first-best decision at each point, multiple partial hypotheses are kept at each step, with hypotheses only being discarded when there are several other higher-ranked hypotheses under consideration. An example of a left-to-right sequence of decisions that produces a simple parse is shown below for the sentence <i>I booked a ticket to Google</i>.</p>
<figure><a href="https://2.bp.blogspot.com/-fqtmVS97tOs/VzTEAI9BQ8I/AAAAAAAAA_U/xPj0Av64sGseS0rF4Z1BbhmS77J-HuEvwCLcB/s1600/image04.gif"><img src="https://2.bp.blogspot.com/-fqtmVS97tOs/VzTEAI9BQ8I/AAAAAAAAA_U/xPj0Av64sGseS0rF4Z1BbhmS77J-HuEvwCLcB/s640/image04.gif" width="640" height="336" border="0"></a></figure><div class="separator"></div>
<p>Furthermore, as described in our <a href="http://arxiv.org/abs/1603.06042">paper</a>, it is critical to tightly <i>integrate learning and search</i> to achieve the highest prediction accuracy. Parsey McParseface and other <a href="https://github.com/tensorflow/models/tree/master/syntaxnet">SyntaxNet</a> models are some of the most complex networks that we have trained with the <a href="https://www.tensorflow.org/">TensorFlow</a> framework at Google. Given some data from the Google supported <a href="http://universaldependencies.org/">Universal Dependencies</a> project, you can train a parsing model on your specific machine.</p>
<p><b>So How Accurate is Parsey McParseface?</b></p>
<p>On a standard benchmark consisting of randomly drawn English newswire sentences (the 20 year old <a href="https://www.cis.upenn.edu/~treebank/">Penn Treebank</a>), Parsey McParseface recovers individual dependencies between words with over 94% accuracy, beating our previous state-of-the-art results, which were already <a href="http://arxiv.org/abs/1603.06042">better than any previous approach</a>. While there are no explicit studies in the literature about human performance, we know from our in-house annotation projects that linguists trained for this task agree in 96-97% of the cases. This suggests that we are approaching human performance—but only on well-formed text. Sentences drawn from the web are a lot harder to analyze, as we learned from the <a href="http://googleresearch.blogspot.com/2011/03/building-resources-to-syntactically.html">Google WebTreebank</a> (released in 2011). Parsey McParseface achieves just over 90% of parse accuracy on this dataset.</p>
<p>While the accuracy is not perfect, it’s certainly high enough to be useful in many applications. The major source of errors at this point are examples such as the prepositional phrase attachment ambiguity described above, which require real world knowledge (e.g. that a street is not likely to be located in a car) and deep contextual reasoning. Machine learning (and in particular, neural networks) have made significant progress in resolving these ambiguities. But our work is still cut out for us: we would like to develop methods that can learn world knowledge and enable same understanding of natural language across <i>all</i> languages and contexts.</p>
<p>To get started, see the <a href="https://github.com/tensorflow/models/tree/master/syntaxnet">SyntaxNet</a> code and download the Parsey McParseface parser model. Happy parsing from the main developers, Chris Alberti, David Weiss, Daniel Andor, Michael Collins &amp; Slav Petrov.</p></div>
</div>
<!-- /wp:html -->