Scratching the surface of German NLP, from ParZu down

Back in June, looking for parsers for the German language, I ran across ParZu, which is from the University of Zurich. Test sentences thrown against its online demo were translated handily, and all in all it's a convincing parser, so I'm going to be working with it for a while to get a handle on things. It is written in Prolog.

For the past three days, I've gone down the rabbit hole of NLP tools for German, starting from ParZu. There is (of course) a vast amount of previous work, and it's really difficult to get a comprehensive grasp, but this post should at least link to some of it, with initial thoughts, and I can go from there later. I had considered writing an article, but honestly none of this is sufficiently coherent for an article. There's kind of a threshold of effort I expect from articles on the Vivtek site, and that's not there. Yet.

OK. So ParZu can work with any tool that delivers text in a tab-delimited format (token-tab-tag) using the STTS tagset (Stuttgart-Tübingen TagSet, if you were wondering). My Lex::DE can already be converted to generate some of these, so my best bet at the moment would simply be to continue work on Lex::DE and feed it directly into ParZu.  Even better, of course, would be to do this online by talking directly to Prolog, probably ideally through HTTP to avoid 32/64-bit process boundaries. More on this notion later. The cheap way to do this is just to kick out tagged text and go on.

The output from ParZu uses the CoNLL format, which seems pretty straightforward.

Which is all very nice and self-contained, but how do the Zurchers do their tagging? I'm glad you asked! The main tagger is clevertagger, which works on the output of Zmorge. Zmorge is the Zurich variant of SMOR, which is the Stuttgart morphological analyzer, although active development seems to have moved to Munich.

clevertagger has a statistical component that uses CRF (Conditional Random Field) training to judge, based on the Zmorge lemmatization output, which POS is most likely for the word based on your corpus. You can use either Wapiti or CRF++. The point of doing this is to eliminate POS amibiguity (or to quantize it? but no, I think it's a disambiguation step), which is what I hope to use Marpa to do directly - instead of providing unambiguous parts of speech, with Marpa I'll be able to provide alternatives for a given word, and disambiguate after parsing. Well, that's the idea, anyway - but that's going to take some effort.

(Note, by the way, that since ParZu is coded in Prolog, I can probably cannibalize it relatively smoothly to convert to a Marpa grammar, so none of this effort will be lost even if I do switch to Marpa later.)

Anyway, the CRF thing leaves me relatively unexcited. It would be nice to take an aside and figure out just what the heck it's doing, but that's pretty low priority.

Zmorge is based (somehow) on a crawl of the Wiktionary lexicon for German, and uses a variant of SMOR, SMORlemma, for the meat of the processing. I'm unclear on exactly how this step is done, but I do know that SMOR has a lexicon that is read into the FST on a more-or-less one-to-one basis, so I presume that Zmorge is putting the Wiktionary data into that lexicon, and then using updated rules for the rest of the morphological analysis. It would take a little exegesis to confirm that supposition. Maybe later.

SMOR and SMORlemma are both written in an FST-specific language SFST, which is just one example of a general FST language. It's roughly a tool for writing very, very extensive regular expressions (well, that's nearly tautological, in a sense). There are other FST-specific languages originating in different lineages, including OpenFST (developed by Google Research and NYU), AFST (an SFST fork developed in Helsinki - notice that a lot of the original FST work in NLP was done in Helsinki), and the umbrella library that sort of combines all of the above and some other stuff as well, HFST (Helsinki Finite State Technology). Overall, there's been a lot of work in finite-state transducers for the processing of natural language.

There are some tasty-looking links proceeding from the OpenFST project, by the way.

From my point of view, what I'd like to do might consist of a couple of different threads. First, it would be nice to look at each of these toolsets and produce Perl modules to work with them. Maybe. That, or possibly some kind of exegetical approach that could approximate some kind of general semantics of FSTs and allow implementation of the ideas in any appropriate library or something. I'm not even sure.

But second, it would be ideal to take some of the morphological information already contained in the various open-source morphologies here (note: OMor at Helsinki, which aims to do something along these lines, and of course our old friend Freeling) and build that knowledge into Lex::DE where it can do me some good. How that would specifically work is still up in the air, but to get good parses from ParZu (and later from Marpa), it's clear that solid morphological analysis is going to be crucial.

Third, I still want to look at compilation of FSTs and friends into fast C select structures as a speed optimization. I'm not sure what work has already been done here, but the various FST tools above all seem to compile to some binary structure that calls into complex code. I'm not sure how necessary that is - until I examine those libraries, anyway. Also, I'd really like to get something out of lemmatization that isn't a string. Those structures bug the hell out of me, because I still need to parse them again next time I do something. I want something in memory that I can use directly. (Although truth be told I have no idea whether that's premature optimization or not - until I try it out.)

Fourth, there are other POS systems as well. One that naturally caught my eye is hunpos.

So that's the state of the German parsing effort as of today. Lots of things to try, not much actually tried yet.

Update 2014-09-30: A closer look at the underlying technology of ParZu, the Pro3gres parser originally written for English, as described in a technical report by the author, has me somewhat dismayed. I'm simply not convinced that a probabilistic approach is ideal - sure, I might be wrong about this, but first I want to try the Marpa route. Yesterday I sat down to try parsing something with ParZu, and found myself writing an initial Marpa parser for German, working from my own tokenizer (which, granted, has absolutely horrible lemmatization and POS assignment). I think I'm going to continue down that path for now.

That said, SFST is a fascinating system and the German morphologies written in it are really going to come in handy - so I might end up using that before even considering the parser level.

Marpa stuff

As I get further into Marpa, I'm starting to see there's a whole little world of cool stuff out there based on it. Here are a couple of bookmarks for later.

• A fantastic article on using Marpa to convert Excel spreadsheet formulas into Perl using AST transformations.
• Kegler's "Ruby slippers" parsing technique: essentially ways to trick a simple grammar into functioning within a larger whole by using invisible tokens and wishing the language were easier to parse. Marpa is ... well, it's beyond cool and into virgin territory.
• Another Kegler post on mixing declarative and procedural parsing that should come in handy here and there.
• Here's a gist showing a Marpa parser for CSS that uses a tokenizer external to Marpa - the key technique is in the loop starting on line 187, where we pass each individual token to the recognizer. Only after the token stream is complete do we read the value from the recognizer. (So for a series of sentences, do we have to create a new recognizer for each sentence? I think we actually do. That will be something for experimentation later.)

Marpa

So I decided to sit down finally and write the line parser for the new Decl, and since it was parsing, I decided not to unearth my old HOP-inspired parsing code but rather take the plunge and try Marpa, to avoid getting bogged down in parser issues.

I am in love.

It basically looks like Marpa can do anything related to parsing. It can even handle ambiguous parses! One of the test cases is literally "time flies like an arrow"!

But what doesn't yet exist (there's a partial beginning) is a tutorial set, a "Gentle Guide to Marpa". I think I'll write one.

Attempto controlled English

A controlled/minimal grammar for pseudo-English that can be used for expressing specifications and so forth. Neat project, and parsable without leaving the Slow Zone.

Express regexes with verbal expressions

Neat JS library for expression of simple regex use cases in non-incomprehensible form. This is an interesting start, but I don't see any way to extend it to more complicated use cases (identified match outputs, replacements, alternates with any nested structure, and so on).

Although for a lot of things, honestly, regexes should be replaced by explicit grammars with named components and a match specification.

Anyway, this is a nice start and deserves contemplation.

Function grapher play-by-play

Neat blog post series about writing a function grapher, including the parser.

Parsing C

So I'm taking another stab at writing a quasi-literate-programming tool, which, as I am writing things in C with it, requires a credible C parser to find declarations of stuff.

And while Perl has lots of C parsing tools of varying quantity, including a sample with Parse::Eyapp (which is quite fascinating in its own right), none of them are easily adapted - with the exception of the Inline tools.  Inline::C::ParseRegExp, for example, which does exactly what I want it to - find declarations of stuff.

Python, though, has pycparser.  (And of course, Perl has Inline::Python...)

And then, as always, there is Marpa.  I still have a big fat to-do on my list that says "Learn Marpa".  There's a new set of tutorials on Kegler's blog.  I need to work through those.

Update: I realized I was wrong.  I don't actually need a parser - just a tokenizer for C.  This is because all I need to do is cross-reference all identifiers, and the job is done.

Marpa tutorial

Ooh, Kegler wrote another Marpa example tutorial of a DSL.

Think what this will do when wrapped in Decl!  Maybe I should write the parser tutorial chapter early on, then double back to write more sensible things before it.

Shakespeare, the programming language

So there's a cute little language called Shakespeare that I've run across before. It's a little silly, of course (well, that's the point!) but it came up on HNN, as does everything eventually, and one of the posts there suggests a "sort of obfuscator" that would, you know, write Shakespeare for you.

Which I think is a pretty dandy idea, in conjunction with a Shakespeare interpreter. It might use a Markov chain to generate the fluff, select characters at random, and so on and so forth - and everything should compile/interpret correctly.

Underlying the Shakespeare, of course, is a kind of bytecode language. That would be the interpreted language, and that would have a more normal expression as well that could be Shakespearified.

This could showcase parsers in Decl, and might not be a bad way to start doing some fun NLP-type stuff, too. Think about it!

Another parser toolkit

This one in Javascript: Language.js.

COLM: COmputer Language Manipulator

COLM is a language for parsing and tree transformation (like TXL before it). Bears watching.

(I'm pretty sure my concept of mapping is equivalent to a tree transformation with notes kept to permit reversibility.)

MediaWiki parsing

... is apparently a hard nut to crack. I find this a little surprising. Here's an interesting article about a rigorous parsing approach (Dropbox backup) and the HNN thread.

Here's an example parse.

File structure specification

Here is the specification for the IFO format used on DVDs. Decl's "file" tag should also be able to parse binary files in some way. This is a typical file format, so I'm tossing it out as an example.

Update: General directory structure is important, too. An example of How DVDs Work is at doom9.net.

Pratt parsers

An implementation of a Pratt parser in Java. I'm too tired to understand anything but Bahnhof.

TXL: Tree Transformation Language

I essentially think of Decl macros or maps or whatever as falling into two categories: first is the text expression of a template, but the other works on tree structures.

Googling on "tree transformation" is a useful exercise, and five minutes perusal finds me two good links: TXL (the tree transformation language) is precisely what I want to be able to do (with a rule-based approach), and then there's an interesting paper ("A Language for Bidirectional Tree Transformations") by the Unison guys at UPenn about reversible lenses that act between tree structures, which is of course my map concept. (I should probably read everything they're doing.)

So those need to be read carefully. I'm sure there's more.

Parsing works!

OK, so my parsing unit test passes 139 individual tests having to do with all aspects of tokenization, parsing, and building of nodes and nodal structure. I'm independent of Parse::RecDescent and Parse::Indented now, and I'm entirely using Class::Declarative::Parser objects to parse everything.

I still have a little work to adapt the existing classes to their new non-XML::xmlapi existence, but that seems to be going well. So in a couple of days, I guess I'll be starting templates, with a much more satisfactory parse-and-build regime going into the exercise.

Progress!

Down the parsing rabbit hole

So I wanted to do parsers, you know, because I'd like to be able to parse SQL statements and stuff? So I got sucked into Chapter 8 of Higher Order Perl, of course, and once I really started getting into it and realizing how much better life would be if I did some stuff different in the basic parser, well, two weeks had passed.

Still not done.

I do have a lot of parser tools done, though.

But my basic approach to parsing nodal structure was naive. First, the idea that a tag will always mean the same throughout the application is naive - a page in a PDF will have to mean something different from a page in a Web site, and yet I still want to use the tag "page" for both meanings.

But secondly, I realized that I couldn't rely on runtime objects to determine parsing structures, and that rankled.

So I'm going to do things differently now, and in a much more flexible manner. I'm removing the dependency on Parse::RecursiveDescent, and I'm making Class::Declarative::Node a primary class instead of using XML::xmlapi (snif).

Each top-level tag will be parsed minimally into a line and a body, and the first word in the line will determine its semantics, as now. But those semantics will already be able to determine the parsing of all lines indented under that tag! In other words, if it wants to use a different parser, it can. If templates should be expressed, they will be. I'm halfway leaning towards everything always being a template, actually.

This scheme, though, allows me to vary the semantics of inner tags, so if I want to use a radically different syntax to express parser rules, for instance, I can, without a lot of twisting or tweaking.

More on this when it firms up. But there will be recursive-descent parser support built right into Class::Declarative from the get-go. If the strength of Lisp is that it has no syntax, let the strength of Declarative be that it has all syntaxes.

Wx::DefinedUI

For quite some time (like, years) I've toyed with the possibility of defining GUIs under wxWidgets (in Perl, Wx, or in Python, wxPython) by using a sort of pseudocode decorated with actual code to execute the meat of the program. This year, the Muse has accepted my application, and I've started on Wx::DefinedUI in Perl.

To do this, I first managed to get past the hump that's always stopped me in the past: syntax. Bear with me, this is important.

See, whenever I start brainstorming about a new way to reorganize programming, I first scratch out a bunch of data structures in pseudocode, then I realize it's hard to implement that stuff. Then I run aground. For I while I thought XML would help, but no, XML is also too hard to type. This is what killed MagnifiCat, it's what killed the semantic programming of last year (earlier posts on this blog), and it's what killed the Web programming framework I started over the holidays.

But early this year, I got back to Wx. And I looked at the structure of one of the demo programs, and it looks like this:

use Wx::DefinedUI qw(-filter);

dialog (resize) "Wx::BoxSizer"
size (box, v):
  size (box, h) [1, GROW]:
     button (id=OK) [0, ALL, 10] "Close window"
     button [0, 0] "Button 2"
     button [0, TOP BOTTOM, 5] "Button 3"
  space [10, 10, 0, GROW]
  size (box, h) [1, GROW]:
     button [1, ALL, 5] "Button 1"
     space [1, 30, 1, 0, 0]
     button [1, GROW ALL, 5] "Button 2"
     size (static, v) [2, GROW] "Wx::StaticBoxSizer":
        button [1, GROW ALL, 5] "Button 3"
        button [1, GROW ALL, 5] "Button 4"

That's it. Granted, that code doesn't do anything, it just demonstrates the use of box sizers, but there are two points I want to make about it.

First, it provides a detailed, extremely readable, and yet still parseable, overview of the application. If we provided IDs for all those buttons and wrote code to be called on click, we'd have a real application, and one that we could understand with no further ado.

Second - and this is important - as of yesterday, it works. I decided to go ahead and tackle the parsing problem. I looked up Parse::RecDescent and found it good - but then I went ahead and polished up my old XML::xmlapi as a structure manipulation module I can work quickly with, and wrote Parse::RecDescent::Simple to allow parsing of each of those lines. That stuff's already on CPAN, because it's working and stable to the point I need right now.

For parsing of the indentation, I've written part of Parse::Indented. It's not on CPAN yet, because I still want to add a feature allowing embedding of Perl code into my tree. Maybe tomorrow.

The crucial point here is this: I have a parsing framework that lets me use pseudocode to define things, things that will then run. Next step: use that very parsing framework to get back to the Web application framework and semantic programming. It should be easy!

Here's another point, by the bye: publishing early and often keeps the momentum going. I've published five modules to CPAN in the last week. It's heady stuff.