Parsing English with 500 lines of Python (2013)

http://honnibal.wordpress.com/2013/12/18/a-simple-fast-algorithm-for-natural-language-dependency-parsing/

by adamnemecek • 12 years ago

285 61 12 years ago

honnibal.wordpress.com

frik• 12 years ago

Really interesting.

Does it work on Windows too / does it rely on Unix-only constructs?

adamnemecek• 12 years ago

It should work fine.

voltagex_• 12 years ago

How does this relate/compare to NLTK?

http://www.nltk.org/

andrewguenther• 12 years ago

NLTK is a toolkit which includes a bunch of different tokenizers, parsers, taggers, stemmers, lemmatizers, and corpora. The Stanford parser which he references in this post is a parser which can be integrated to work with NLTK, but it seems the methods which he discusses are more accurate and much faster than anything included in NLTK.

Also, the work he describes requires that the text already be tokenize and POS-tagged which will add some time, but not too much (and are also functions which can be performed by NLTK).

piokuc• 12 years ago

It's also worth noting that the Stanford parser is a Java software, so using it from within NLTK involves calling Java from Python.

syllogism15• 12 years ago

The truth is nltk is basically crap for real work, but there's so little NLP software that's put proper effort into documentation that nltk still gets a lot of use.

You can work your way down the vast number of nltk modules, and you'll find almost none of them are useful for real work, and those that are, ship a host of alternatives that are all much worse than the current state-of-the-art.

nltk makes most sense as a teaching tool, but even then it's mostly out of date. The chapter on "Parsing" in the nltk book doesn't even really deal with statistical parsing. The dependency parsing work referenced in this post is almost all 1-3 years old, so obviously it isn't covered either.

As an integration layer, nltk is so much more trouble than it's worth. You can use it to compute some of your scoring metrics, or read in a corpus, but...why bother?

I'm slowly putting together an alternative, where you get exactly one tokeniser, exactly one tagger, etc. All these algorithms have the same i/o, so we shouldn't ask a user to choose one. We should just provide the best one.

My previous post, on POS tagging, shows that ntlk's POS tagger is incredibly slow, and not very accurate: https://honnibal.wordpress.com/2013/09/11/a-good-part-of-spe... . nltk scores 94% in 3m56s, my 200 line implementation scores 96.8% in 12s.

I used to use nltk for tokenisation and sentence-boundary detection, but this library seems better for that: https://code.google.com/p/splitta/

orf• 12 years ago

If that overhead comes from Python then have you tried running either of the implementations on PyPy?

jliechti1• 12 years ago

Since NLTK does enjoy some popularity, would it make sense to try to get some of your code into the project? I'm sure a lot of people could benefit from using/learning about more current algorithms.

shabadoop• 12 years ago

I was thinking about working through the NLTK book once I'm finished with Bishop's Pattern Recognition, would you be able to recommend an alternative?

ma2rten• 12 years ago

Thanks that was enlightening.

sitkack4• 12 years ago

As an aside, OpenCV seems to have the same problem. Widely used and at least a std deviation away from OK.

cf• 12 years ago

Are there any feasible production-ready NLP solutions? My default approach has been to browse the codebases of different computational linguistics labs, but something more central would be very handy. As it stands I just say something to the tune, "please don't use nltk, use opennlp, cleannlp, redshift, etc".

danso• 12 years ago

It's worth checking out the OP's previous post on this: A good POS tagger in about 200 lines of Python: http://honnibal.wordpress.com/2013/09/11/a-good-part-of-spee...

The OP says his PyGreedyAP gets 96.8% accuracy in 12s (vs NLTK's 94% at 236s)

xiaq• 12 years ago

On a related note, parsing Chinese could be much harder since the first step, identifying word boundaries [1], is already hard enough...

1. https://en.wikipedia.org/wiki/Text_segmentation

habeanf7• 12 years ago

State of the art research indicates that joint processing (segmentation, tagging and syntactic analysis) achieves better results than a pipeline model. For an example, see Hatori et al: http://aclweb.org/anthology//P/P12/P12-1110.pdf

Also, OPs model only runs unlabeled dependency parsing. Most applications require labeled dependency parsing, which is much harder. State of the art results for English are currently ~93% established by Joakim Nivre and Yue Zhang in http://www.sutd.edu.sg/cmsresource/faculty/yuezhang/acl11j.p... and based on the zpar parser framework (see http://www.cl.cam.ac.uk/~sc609/pubs/cl11_early.pdf ).

zpar ( http://sourceforge.net/projects/zpar/ ) is the fastest dependency parser I am aware of, and it achieves lower parsing rates.

In all papers, note how many more feature templates are specified. More recent work contains yet another order of magnitude more feature templates. I'm betting python (w/ or w/o Cython) won't last very long as competition.

All that being said, the most significant problem in this part of NLP is that the best corpus files required for training modern accurate models are very expensive to license for both research and commercial purposes (tens if not hundreds of thousands of $s).

syllogism15• 12 years ago

The Cython parser is basically an implementation of zpar, and achieves slightly faster run-times, and slightly better accuracy (I've added some extra features, and made some nips and tucks).

Note that the Stanford label set has 40 labels, so there are about 80 classes to evaluate. The Penn2Malt scheme has 20 labels, so you need to be careful which dependency scheme is being referenced when run-time figures are reported.

The way the run-time cost works is, if you extract f features per transition, for c classes, with a beam of size k and n words, you make O(cfkn) feature-lookups, which is the main cost.

For the parser.py implementation, most of the speed is coming from greedy search (k=1), and low number of classes (c=3, instead of c=80). Number of feature templates, f, is similar between this parser and zpar. We could add some more templates for label features, and do labelled parsing, and gain about 1% accuracy here, at the cost of being about 40x slower. The only reason I didn't was that it complicates the implementation and presentation slightly. The implementation was all about the blog post.

The Cython parser does everything with C data structures, which are manually memory managed. I don't think I'm paying any language overhead compared to a C++ implementation. So you're absolutely right that as more feature templates stack on, and you use more dependency labels, speed goes down. But, the Cython parser has no problem relative to zpar in this respect.

syllogism15• 12 years ago

Segmentation is a big issue for Chinese, but actually incremental parsers have been doing promising things here, because you can do the segmentation jointly with the parsing.

I'd start with Yue Zhang's papers for work on this: http://www.sutd.edu.sg/yuezhang.aspx

waterside81• 12 years ago

We've been working on this problem for a while - and have a pretty solid solution.

Check us out https://www.repustate.com

We also do this for Arabic, which is equally challenging.

natch3• 12 years ago

Repustate will tell extract the opinions contained within your text...

What does that mean, "tell extract"? Not familiar with this terminology.

bjoernbu2• 12 years ago

I couldn't find any publication on the RedShift system that is part of the author's current work. Any pointers?

cash2m• 12 years ago

Found this one: https://github.com/syllog1sm/redshift

syllogism15• 12 years ago

If you're looking for the academic papers, my Google Scholar page is here: http://scholar.google.com.au/citations?user=FXwlnmAAAAAJ&hl=... . The 2013 paper with Yoav Goldberg and Mark Johnson, and the 2014 paper with Mark Johnson are the two main things I've published with the system. I have another paper almost ready for publication, too.

bjoernbu2• 12 years ago

Yes, that was what i was looking for, thanks. I was interested in details on the evaluation and why the Stanford parser is still widely accepted as state-of-art, especially by non-NLP researchers that want to try some NLP features to work with. By the way, what is a typical use-case for unlabled parses?

uuid_to_string4• 12 years ago

How many LOC in the libraries used to be able to write the implementation in 500 lines of Python?

Why not include some experiments with Lua and lpeg?

It would probably be faster than Java or Python.

And arguably Lua is easier to learn.

Maybe the work required (one-time cost) would be rewarded with significant gains.

sanxiyn• 12 years ago

As you can easily check yourself, it uses no external library whatsoever besides Python standard library. So the answer to the first question is zero.

uuid_to_string4• 12 years ago

The standard libraries count as an external library.

Why wouldn't they?

natch3• 12 years ago

As a Python newbie, just curious:

Python3 came out in 2008. Right now the year is 2014. Assuming this is pretty new code, what reason could there possibly be for not using Python3 for this?

dopamean• 12 years ago

I'm not a python user myself but from what I understand some people are rather partial to particular versions of python. I think 2.7 is very popular. I think there also may have been some backward compatibility issues in python 3 that some people were unhappy with. Perhaps someone with more knowledge on the matter can chime in.

sqrt17• 12 years ago

You're free to try and see if the code also works in Python3.

Python3 used to come without a lot of the "batteries" that make Python a useful language for science-y stuff (numpy, matplotlib, Cython),and the 'improvements' that Python3 brings are not big enough that people would switch over.

Contrast this to C++11, which brings real improvements to pain points that existed before (i.e., areas of the STL that ought to have been standardized but were not).

Contrast this to Java 6 (Generics) and Java 8 (Lambdas) which solve actual perceived pain points that many people who program in Java are feeling.

The biggest pain point in Python2-the-language isn't any missing language feature -- most people are happy with those since at least 2.6. Instead, it's speed, and people are indeed transitioning part of their programs from Python2 to Cython. Python3 doesn't do anything for speed.

natch3• 12 years ago

No need to try, even a beginner can see that it won't.

syllogism15• 12 years ago

I should really have written the code to be Python 2/3 compatible.

I've not really worked with Python 3 yet, and I've regretted not basing a recent project, http://cloze.it , on it. I was getting unicode problems that Python 3 addresses pretty well.

sitkack4• 12 years ago

That question is best asked and answered in other forums. OT.

nymph• 12 years ago

...for some value of "parsing"

Parsing English with 500 lines of Python (2013)

Related Stories