As I wrote earlier, we've been working on language technology for Paraguay. There are a few of us on some related projects, with the goal of building both useful translation software for Spanish-Guarani and a nice website where folks can do collaborative translations, eventually with computer-assisted translation included! We're building these tools with reusability in mind too -- they should be applicable to other under-resourced language pairs in the near future.
The first tool is coming along: we've been building out Guampa, the collaborative translation website; we should be ready for the first beta users really soon. We would love some help on this system: if you're into software development and/or want to help build resources for the Guarani language, let's chat!
Coming next, watch for the Tereré translation system and the accompanying Chipa word-sense disambiguation module, completing our "Paraguayan afternoon snack" metaphor for translation tools...
In related news, the Mozilla Paraguay folks have been really busy, gearing up to translate Firefox into Guarani, in collaboration with FP-UNA. The Guarani Ñe'ẽ discussion group has been buzzing about this; from my vantage point in the frozen northern anglohablante climes, it looks like everybody is pumped about this. Pretty exciting times.
Showing posts with label machine translation. Show all posts
Showing posts with label machine translation. Show all posts
Saturday, November 30, 2013
Monday, September 30, 2013
Thesis proposal!
Last week, I had my thesis proposal.
I proposed, basically, that for doing machine translation into lower-resourced languages we're going to want better cross-lingual word sense disambiguation to help our MT systems make better word choices. And I outlined some methods that we might use to get that goal. I'm going to develop these approaches in the context of a few different kinds of MT systems, particularly focusing on translating from Spanish to Guarani.
So I guess now all I have to do for the rest of the PhD is this project.
If you're curious, I'm writing my dissertation in public, on github: http://github.com/alexrudnick/dissertation
Let's do this.
If you're curious, I'm writing my dissertation in public, on github: http://github.com/alexrudnick/dissertation
Let's do this.
Sunday, June 23, 2013
NAACL 2013 review
Just recently, I was in Atlanta for NAACL. So much fun! The hallway track is always the best -- I saw a bunch of friends from the NLP world, and especially a lot of Googlers, and met a bunch of new people! Also I managed to be present for Ray Mooney and David Forsyth and some other professors disagreeing animatedly about internal representations of meaning and to what extent you need to take the intentional stance with respect to other people.
Lots of really interesting papers this time around. There is of course Hal Daumé's expert opinion about the interesting papers at the main conference -- I saw a lot of those same talks, having mostly been hanging out at the machine translation and syntax/parsing tracks. On a personal note, it's exciting to see people I know and have worked with getting mentions on Hal's blog! (so, congratulations Greg Durrett and John DeNero and Juri Ganitkevitch!)
Additionally, here's what I thought was cool:
Lots of really interesting papers this time around. There is of course Hal Daumé's expert opinion about the interesting papers at the main conference -- I saw a lot of those same talks, having mostly been hanging out at the machine translation and syntax/parsing tracks. On a personal note, it's exciting to see people I know and have worked with getting mentions on Hal's blog! (so, congratulations Greg Durrett and John DeNero and Juri Ganitkevitch!)
Additionally, here's what I thought was cool:
- Training Parsers on Incompatible Treebanks by Richard Johansson. You want to build a parser for your language. And you've got a treebank. No! You've got two treebanks. Even better, right? But what if those two treebanks use entirely different annotation schemes? ...
- In the invited talk on Wednesday, Kathy McKeown talked about, among other things, the idea that as NLP people we can provide evidence for or against ideas in comparative literature or literary theory, in collaboration with literature folks -- "well, the theory is that narrative works like this -- let's check!"
- At *Sem, but also in the main conference, people are talking about using richer, more structured semantic models in our applications again. The really major change in the field in the early 1990s was to not do this -- but now we've got bigger computers and more data, and as a community we know a lot more about stats! Kevin Knight and his group are launching their Abstract Meaning Representation project ("It's like a treebank, but for semantics.") -- maybe it'll work this time!
- Also at *Sem, Yoav Goldberg talked about the unreasonably enormous Syntactic Ngrams dataset -- it's basically chunks of parse trees from the English part of the Google Books corpus, indexed by time. That's going to be super useful.
- I popped in to some of the Computational Linguistics for Literature talks -- Mark Riedl's invited talk about programmatically generating stories for games (slides) was especially good!
- SemEval! There were fourteen different tasks -- lots of different aspects of understanding text! And people are using all these wildly different techniques to do it. An introductory talk about a task and then a single presentation about a system for performing that task is not always enough to really understand the problem, though...
- I think my presentation went pretty well! People I've been citing for a while were at my talk, and people seemed engaged and asked good questions! (slides, paper)
Alright! So now, full of encouragement and ideas -- back to work.
Sunday, March 31, 2013
language technology for Paraguay
Earlier this month, we went to Paraguay. Why'd we do that?
Paraguay is the only country in the Americas where people are bilingual with a European language and the indigenous language. Paraguayans, the majority of them anyway, really do speak Guarani, or depending on context, a mixture of Spanish and Guarani called Jopará.
While we were there, we talked with Guarani-language teachers at the institutes where they're training translators and linguists. They let us sit in on some of the classes and talk with the students. We're working on building them a computer-assisted translation webapp that will help us collect lots of bilingual text! This is going to be huge.
It hit me, after the first visit to the schools, how much we were making use of our foreign-white-scientist privilege. We didn't have anything to do with the OLPC project -- aside from a desire to collaborate -- but here we were, wandering into schools without so much as a release form, talking to the kids. I'm trying to imagine Paraguayan scientists coming to the US to observe technology use among los niños estadounidenses.
Paraguay is the only country in the Americas where people are bilingual with a European language and the indigenous language. Paraguayans, the majority of them anyway, really do speak Guarani, or depending on context, a mixture of Spanish and Guarani called Jopará.
While we were there, we talked with Guarani-language teachers at the institutes where they're training translators and linguists. They let us sit in on some of the classes and talk with the students. We're working on building them a computer-assisted translation webapp that will help us collect lots of bilingual text! This is going to be huge.
While we were in the area, we also talked with the local One Laptop Per Child folks; there's an OLPC installation in the little town of Caacupé, which is near Asunción. The OLPC folks said that we should probably go visit local grade schools. Which we did!
It hit me, after the first visit to the schools, how much we were making use of our foreign-white-scientist privilege. We didn't have anything to do with the OLPC project -- aside from a desire to collaborate -- but here we were, wandering into schools without so much as a release form, talking to the kids. I'm trying to imagine Paraguayan scientists coming to the US to observe technology use among los niños estadounidenses.
The really interesting thing here: the kids in Caacupé weren't so surprised to see foreign scientist-looking guys coming to talk with them. They were really friendly, and eager to show off what they could do with the laptops! I get the impression this happens fairly frequently.
So there's a lot of stuff that needs to get built, to make computer use in Guarani more pleasant.
- At a very basic level, it's hard for people to type the diacritics that you need for Guarani, if your keyboard layout is set to Spanish. The diacritics for Guarani actually aren't that weird; they've got tildes on some vowels, but you see that in Portuguese too.
- There's no good spellchecker. Guarani morphology is pretty complicated, so this is not an easy thing to build. But we know a guy who's working on it...
- Text-to-speech. They kids in the schools have text-to-speech for Spanish, and they love it! There's a program on the OLPC where you can send messages to a friend's computer, and the receiving computer will speak your message. It's hilarious. But it doesn't work for Guarani. And as you get further out into the country, the kids are more likely to be monolingual Guarani speakers...
- The computer-assisted translation website: we're working on it. I'll write more about this soon...
Thursday, March 29, 2012
quals writeup: Tree Transducers, Machine Translation, and Cross-Language Divergences
I hope it's not too pretentious to put things I'm writing for my phd qualifiers on arXiv. I think arXiv is really exciting, by the way. Leak your preprints there! Also pretty exciting: tree transducers for machine translation.
Abstract:
Software! http://github.com/alexrudnick/kurt
Tree transducers are formal automata that transform trees into other trees. Many varieties of tree transducers have been explored in the automata theory literature, and more recently, in the machine translation literature. In this paper I review T and xT transducers, situate them among related formalisms, and show how they can be used to implement rules for machine translation systems that cover all of the cross-language structural divergences described in Bonnie Dorr's influential article on the topic. I also present an implementation of xT transduction, suitable and convenient for experimenting with translation rules.Paper! http://arxiv.org/abs/1203.6136
Software! http://github.com/alexrudnick/kurt
Saturday, December 31, 2011
reading: Readings in Machine Translation
Post before the end of the year!
I'm really enjoying Readings in Machine Translation -- it's got all of these great MT papers from past decades, going from the Warren Weaver memo from 1949 to the Brown et al. paper where they make stat-mt fashionable again in the early 90s. Apparently, a lot of the papers in the volume were somewhat hard to find online in 2003.
Really interesting: so far, the early papers have had some very detailed descriptions of the low-level particulars. "Well, we're going to need this many memory drums...", "oh, and the words will be stored in memory in alphabetical order" (which seems very archaic), and a fixation on picking the right word in the target language, in sort of a word-sense disambiguation sense (which is slightly fashionable again!).
So for people into MT who want a sense of history, these are papers that it seems like one should read -- I mean, Sergei Nirenburg and friends picked them out, so they've got to be good, right?
If you haven't read the 1949 Warren Weaver memo, though -- even if you're not an NLP person -- do yourself a favor and go ahead and read it!
I'm really enjoying Readings in Machine Translation -- it's got all of these great MT papers from past decades, going from the Warren Weaver memo from 1949 to the Brown et al. paper where they make stat-mt fashionable again in the early 90s. Apparently, a lot of the papers in the volume were somewhat hard to find online in 2003.
Really interesting: so far, the early papers have had some very detailed descriptions of the low-level particulars. "Well, we're going to need this many memory drums...", "oh, and the words will be stored in memory in alphabetical order" (which seems very archaic), and a fixation on picking the right word in the target language, in sort of a word-sense disambiguation sense (which is slightly fashionable again!).
So for people into MT who want a sense of history, these are papers that it seems like one should read -- I mean, Sergei Nirenburg and friends picked them out, so they've got to be good, right?
If you haven't read the 1949 Warren Weaver memo, though -- even if you're not an NLP person -- do yourself a favor and go ahead and read it!
Sunday, July 31, 2011
cross-lingual word sense disambiguation
Have I mentioned what I've been working on recently? Maybe I haven't.
In general, I'm working on cross-lingual word- and phrase-sense disambiguation. WSD/PSD is the problem of deciding, for a given word or phrase, which meaning was intended, for some pre-defined sets of meanings. You might get the possible senses out of a dictionary, where they're nicely enumerated, or perhaps from WordNet. The stock example is "bank" -- is it the side of a river, or is it a building where they do financial services? Or, is it the abstract financial institution?
There's a brilliant bit from the prescient Warren Weaver, from 1955 (via):
The "cross-lingual" kind of WSD means that we care about exactly the distinctions that cause you to pick a different word in a given target language, typically because the CLWSD system is meant to be integrated into an MT system; that's becoming fashionable (Carpuat and Wu, 2007). So in this setting, say if you're translating "bank" from English into Spanish, your system doesn't have to decide if it's the building or the institution that owns it -- it's still "banco". Now a riverbank is an "orilla".
In the general case, your system might end up learning how to make distinctions that you as a human didn't know you had to make -- for example, I'm given to understand that Japanese doesn't have just one word for "brother", but "older brother" and "younger brother", which are different enough concepts that they get totally separate words.
Making these choices is typically treated as a classification problem: you get some features for a bunch of instances of usage of a source word, and do supervised learning to get a classifier with (hopefully) good accuracy on the problem of predicting whether this is a "banco" usage or an "orilla" usage. The features are typically things like "which words are in the surrounding context?", or perhaps something fancier based on a parse of the sentence or knowledge about the document as a whole -- whatever you think will be predictive of what the target-language word should be. Hopefully your learning algorithm has some good way of filtering out irrelevant features.
And then, once that's all put together, hopefully you have some extra signal to feed into your translation system, and it makes better word choices, and everybody's happy.
And that's cross-lingual word/phrase-sense disambiguation!
In general, I'm working on cross-lingual word- and phrase-sense disambiguation. WSD/PSD is the problem of deciding, for a given word or phrase, which meaning was intended, for some pre-defined sets of meanings. You might get the possible senses out of a dictionary, where they're nicely enumerated, or perhaps from WordNet. The stock example is "bank" -- is it the side of a river, or is it a building where they do financial services? Or, is it the abstract financial institution?
There's a brilliant bit from the prescient Warren Weaver, from 1955 (via):
If one examines the words in a book, one at a time as through an opaque mask with a hole in it one word wide, then it is obviously impossible to determine, one at a time, the meaning of the words . . . . But if one lengthens the slit in the opaque mask, until one can see not only the central word in question but also say N words on either side, then if N is large enough one can unambiguously decide the meaning of the central word . . . . The practical question is: "What minimum value of N will, at least in a tolerable fraction of cases, lead to the correct choice of meaning for the central word?
The "cross-lingual" kind of WSD means that we care about exactly the distinctions that cause you to pick a different word in a given target language, typically because the CLWSD system is meant to be integrated into an MT system; that's becoming fashionable (Carpuat and Wu, 2007). So in this setting, say if you're translating "bank" from English into Spanish, your system doesn't have to decide if it's the building or the institution that owns it -- it's still "banco". Now a riverbank is an "orilla".
In the general case, your system might end up learning how to make distinctions that you as a human didn't know you had to make -- for example, I'm given to understand that Japanese doesn't have just one word for "brother", but "older brother" and "younger brother", which are different enough concepts that they get totally separate words.
Making these choices is typically treated as a classification problem: you get some features for a bunch of instances of usage of a source word, and do supervised learning to get a classifier with (hopefully) good accuracy on the problem of predicting whether this is a "banco" usage or an "orilla" usage. The features are typically things like "which words are in the surrounding context?", or perhaps something fancier based on a parse of the sentence or knowledge about the document as a whole -- whatever you think will be predictive of what the target-language word should be. Hopefully your learning algorithm has some good way of filtering out irrelevant features.
And then, once that's all put together, hopefully you have some extra signal to feed into your translation system, and it makes better word choices, and everybody's happy.
And that's cross-lingual word/phrase-sense disambiguation!
Thursday, March 31, 2011
CMU's Avenue Project
Before there was HLTDI, there was Carnegie Mellon's Avenue Project, which seems to have had basically the same goal as us -- produce good machine translation systems for under-resourced languages, especially those spoken by under-resourced indigenous people.
Avenue itself doesn't seem to have been under-resourced, though -- they sent people to South America (Chile, Peru, Bolivia...) to collect training data, and seemed to have a lot of contacts with local educators and language experts. They got quite a few papers out of this line of research, and apparently wrote a lot of good software. They had a much deeper pool of money (and arguably talent) than we do.
And now... the website is dormant, the PhD students involved seem to have graduated, the data and software are not publicly available, and the researchers seem to have moved on to other things. (one of the resulting doctors is the illimitable Kathrin Probst, who hipped me to Avenue when we were both at Google Atlanta, although I didn't really grasp how serious it was at the time -- darn her for being so humble!)
They were pretty gracious in giving us the Quechua data that they collected (and said we could redistribute it), and I've been reading a bunch of their papers, but I'm left some sadness about the whole enterprise -- they surely already went through a lot of the problems that HLTDI is going to have to address. Why can't we just check out and fork their code?
... maybe I should ask for their software too. Science is supposed to be easily replicable, isn't it?
Avenue itself doesn't seem to have been under-resourced, though -- they sent people to South America (Chile, Peru, Bolivia...) to collect training data, and seemed to have a lot of contacts with local educators and language experts. They got quite a few papers out of this line of research, and apparently wrote a lot of good software. They had a much deeper pool of money (and arguably talent) than we do.
And now... the website is dormant, the PhD students involved seem to have graduated, the data and software are not publicly available, and the researchers seem to have moved on to other things. (one of the resulting doctors is the illimitable Kathrin Probst, who hipped me to Avenue when we were both at Google Atlanta, although I didn't really grasp how serious it was at the time -- darn her for being so humble!)
They were pretty gracious in giving us the Quechua data that they collected (and said we could redistribute it), and I've been reading a bunch of their papers, but I'm left some sadness about the whole enterprise -- they surely already went through a lot of the problems that HLTDI is going to have to address. Why can't we just check out and fork their code?
... maybe I should ask for their software too. Science is supposed to be easily replicable, isn't it?
Saturday, October 23, 2010
workshop on FOSS machine translation!
Second International Workshop on Free/Open-Source Rule-Based Machine Translation. And it's in Barcelona! What could possibly be better?
I should probably go to this.
I should probably go to this.
extended abstract for a workshop, MTMRL
On Wednesday, I submitted a mini-writeup of my project this semester to the Machine Translation and Morphologically-rich Languages workshop. My code definitely isn't in a useful state yet, but they say that works-in-progress are OK.
I'll let you know if my project gets accepted. The workshop is in Israel, which would be a really interesting place to visit!
Here's what I wrote:
Abstract
Just in case you're not familiar with the idea of valency for verbs: wikipedia!
I'll let you know if my project gets accepted. The workshop is in Israel, which would be a really interesting place to visit!
Here's what I wrote:
Abstract
Here we describe a work-in-progress approach for learning valencies of verbs in a morphologically rich language using only a morphological analyzer and an unannotated corpus. We will compare the results from applying this approach to an unannotated Arabic corpus with those achieved by processing the same text in treebank form. The approach will then be applied to an unannotated corpus from Quechua, a morphologically rich but resource-scarce language.See the rest here; it's short! (or as a pdf)
Just in case you're not familiar with the idea of valency for verbs: wikipedia!
Monday, April 26, 2010
what I'm working on: XDG and weighted constraint solving
Abstract: It turns out that coordination (the use of conjunctions) is really hard for most grammatical theories. We're working on ways to handle it with graceful failure by selectively relaxing constraints in our constraint-based parser -- ideally we can come up with an approach for handling unfamiliar grammatical structures just by tweaking the weights on our constraints.
Slides from Tuesday's talk:
So in the previous post...
In the previous post, I discussed dependency grammar, XDG, and introduced why coordination is hard for DG. The plan for our current work is to allow some of the constraints described by the grammar to be broken, such that we can get reasonable parses from input sentences that we know are valid.
This fairly simple case of English coordination is hard to describe with our formalism, and as we expand our system to handle new languages, we're certainly not going to have complete grammars. It would also be nice if we could handle sentences with actual mistakes, but that'll have to be future work. In general, we'd like to be able to tweak our system to (badly) support sentences that our grammar doesn't explicitly handle just by finding out which constraints to relax. There may be other cases where we need to make changes to the grammar, but we'd like to avoid that as much as possible.
Engineering issues and weighted constraint solving
Getting to the point where we can relax constraints and "fail gracefully" took some programming work. XDG so far has only used hard constraints, which means that if one of the rules for the grammar can't be satisfied, then the parser just gives up and you don't get a parse. The original XDG implementation is done in Mozart/Oz, which has constraint programming built right into the language; Mike's version uses python-constraint.
So what I did, is I hooked our parser up to a "weighted" constraint solver, toulbar2. It's actively under development by friendly researchers at INRA, from Toulouse and Barcelona.
Weighted constraint solving is pretty simple. We define a problem, which contains a bunch of constraints, and each constraint pertains to some variables. A solution to the problem is a total assignment to all of the variables, and each solution has some penalty associated with it, due to violating constraints. There's a cost to violating each constraint. To solve a problem, you just have to say what the variables and constraints and costs are, and what the maximum cost you're willing to accept is.
toulbar2 is really fast. It's written in C++ and has some clever solving algorithms. Once it gets rolling, it can parse a sentence with a bunch of lexical ambiguity and an embedded clause, "the old man that argues eats", in about three seconds. For comparison, python-constraint takes 70 to 90.
The only problem with this is that to run toulbar2, we first have to translate the problem into the standard WCSP format, which takes several steps:
To get around the worst part of this problem, I came up with a dumb hack that I rather like: skip constraints where there are more than 15 variables, and let toulbar2 over-generate solutions. After the toulbar2 solver returns, then just prune down the solutions that went over-cost.
Parsing a simple sentence with coordination
Getting a parse that I like for "Dolores and Jake eat yogurt", where there are subject links from eat to both "Dolores" and "Jake", and "and" is unconnected, only required a few tweaks, done by hand:
Next steps: Optimization problem
Once we write down these features, we can treat tweaking the costs as an optimization problem, where our parameters are the costs for violating each kind of constraint, and maximum cost. We'll consider the grammar and the test sentences as fixed.
We want to know: how can we set the parameters so that we can parse the good sentences, but not the bad ones? And can we get parses that we like? There are many different incomplete parses that we could assign to a sentence -- which one of them should we reward?
To get started on this problem, we just need to know which constraints need to be relaxed so that the desired parse is in there somewhere, and after that, we can (hopefully) optimize the parameters with something like simulated annealing or genetic algorithms.
What I don't have an idea about yet is how to know what kinds of sentences will require tweaks to the grammar, or worse, to the parser code, in order to get sensible parses. For example, to get this coordination example to work, I had to make both of these kinds of changes, even if they were small -- the grammar had no idea about conjunctions, even conjunctions with no arcs attached to them, and the parser threw an exception if a word had no arcs attached.
From an engineering perspective, there's a lot left to do to speed up the parser. This will probably involve finding a tighter way to integrate toulbar2 with our XDG system, and I'm imagining some clever ways to avoid having to list out all the possible assignments after the first time, so the optimization process won't take forever.
Questions and suggestions gratefully accepted :) Thanks for reading!
Slides from Tuesday's talk:
Mike's slides: background for the project
My slides: recent progress with weighted constraint solving
So in the previous post...
In the previous post, I discussed dependency grammar, XDG, and introduced why coordination is hard for DG. The plan for our current work is to allow some of the constraints described by the grammar to be broken, such that we can get reasonable parses from input sentences that we know are valid.
This fairly simple case of English coordination is hard to describe with our formalism, and as we expand our system to handle new languages, we're certainly not going to have complete grammars. It would also be nice if we could handle sentences with actual mistakes, but that'll have to be future work. In general, we'd like to be able to tweak our system to (badly) support sentences that our grammar doesn't explicitly handle just by finding out which constraints to relax. There may be other cases where we need to make changes to the grammar, but we'd like to avoid that as much as possible.
Engineering issues and weighted constraint solving
Getting to the point where we can relax constraints and "fail gracefully" took some programming work. XDG so far has only used hard constraints, which means that if one of the rules for the grammar can't be satisfied, then the parser just gives up and you don't get a parse. The original XDG implementation is done in Mozart/Oz, which has constraint programming built right into the language; Mike's version uses python-constraint.
So what I did, is I hooked our parser up to a "weighted" constraint solver, toulbar2. It's actively under development by friendly researchers at INRA, from Toulouse and Barcelona.
Weighted constraint solving is pretty simple. We define a problem, which contains a bunch of constraints, and each constraint pertains to some variables. A solution to the problem is a total assignment to all of the variables, and each solution has some penalty associated with it, due to violating constraints. There's a cost to violating each constraint. To solve a problem, you just have to say what the variables and constraints and costs are, and what the maximum cost you're willing to accept is.
toulbar2 is really fast. It's written in C++ and has some clever solving algorithms. Once it gets rolling, it can parse a sentence with a bunch of lexical ambiguity and an embedded clause, "the old man that argues eats", in about three seconds. For comparison, python-constraint takes 70 to 90.
The only problem with this is that to run toulbar2, we first have to translate the problem into the standard WCSP format, which takes several steps:
- list each constraint and the variables involved (OK, easy)
- write down the "default cost" for each constraint (OK, easy -- it's 0.)
- store a mapping for all of our variables and their domains, since toulbar2's format wants everything to be an integer (OK.)
- write down every single non-default assignment to the relevant variables (OH NOES COMBINATORIAL EXPLOSION.)
To get around the worst part of this problem, I came up with a dumb hack that I rather like: skip constraints where there are more than 15 variables, and let toulbar2 over-generate solutions. After the toulbar2 solver returns, then just prune down the solutions that went over-cost.
Parsing a simple sentence with coordination
Getting a parse that I like for "Dolores and Jake eat yogurt", where there are subject links from eat to both "Dolores" and "Jake", and "and" is unconnected, only required a few tweaks, done by hand:
- Allow motherless nodes (code change, not good)
- add CONJ as a part of speech (grammar change)
- Allow breaking these three principles: valency (to allow for more than one subject), tree (every node has exactly 1 mother), and agree (eg, agreement between subjects and verbs)
Next steps: Optimization problem
Once we write down these features, we can treat tweaking the costs as an optimization problem, where our parameters are the costs for violating each kind of constraint, and maximum cost. We'll consider the grammar and the test sentences as fixed.
We want to know: how can we set the parameters so that we can parse the good sentences, but not the bad ones? And can we get parses that we like? There are many different incomplete parses that we could assign to a sentence -- which one of them should we reward?
To get started on this problem, we just need to know which constraints need to be relaxed so that the desired parse is in there somewhere, and after that, we can (hopefully) optimize the parameters with something like simulated annealing or genetic algorithms.
What I don't have an idea about yet is how to know what kinds of sentences will require tweaks to the grammar, or worse, to the parser code, in order to get sensible parses. For example, to get this coordination example to work, I had to make both of these kinds of changes, even if they were small -- the grammar had no idea about conjunctions, even conjunctions with no arcs attached to them, and the parser threw an exception if a word had no arcs attached.
From an engineering perspective, there's a lot left to do to speed up the parser. This will probably involve finding a tighter way to integrate toulbar2 with our XDG system, and I'm imagining some clever ways to avoid having to list out all the possible assignments after the first time, so the optimization process won't take forever.
Questions and suggestions gratefully accepted :) Thanks for reading!
Sunday, April 25, 2010
what I'm working on: Dependency Grammar and XDG
Abstract: It turns out that coordination (the use of conjunctions) is really hard for most grammatical theories. We're working on ways to handle it with graceful failure by selectively relaxing constraints in our constraint-based parser -- ideally we can come up with an approach for handling unfamiliar grammatical structures just by tweaking the weights on our constraints.
This post and the next one (forthcoming!) are basically a talk that Mike and I gave on Tuesday.
If you like slides, here are the slides:
Mike's slides: background for the project
My slides: recent progress with weighted constraint solving
About Dependency Grammar and XDG
For our translation system, we're using a dependency grammar formalism called XDG, the Extensible Dependency Grammar. In dependency grammar, instead of representing your analysis of a sentence as a tree of nested phrases, you're interested in the individual relationships between words (eg, "this noun is the subject of this verb"), so the analysis of a sentence ends up being a directed graph with labeled arcs, instead of a tree of phrases, like you might have with phrase-structure grammars. There are nice diagrams of this in Mike's slides. XDG was developed by Ralph Debusmann in his doctoral work -- his implementation of it is done in Mozart/Oz, and we're working on a new one in Python.
There are several competing DGs, of course. But XDG has a few nice properties that set it apart from other approaches, and one of them is that it's constraint-based. The task of producing a parse is expressed as a constrained search; there are rules in the grammar associated with each word (or class of words) that say things like "I'm a verb, and I need a subject, and it must come before me". So when we start to try to analyze a sentence, we list all of the possible links between words, find all of the constraints that apply, and then set a general-purpose constraint solver on the problem.
Another other neat thing about XDG is that it's multi-layered -- an analysis is actually a multigraph. So some of the links in the analysis represent syntax (or even different aspects of syntax, as we're doing for English), and some of them can represent your semantic model. And there are constraints that describe the relationships between different layers. In the next few months, we want to replace "semantic model" with "syntax of the target language for the translation"!
So XDG has these functions called "principles", and when these are run, they add to the list of constraints on the analysis. Some of them include the principle that the analysis should be a tree, or a planar graph (called "projectivity" in Linguistics World), and that we get other desiderata like verbs agreeing with their nouns. ("she jumps" is OK, but not "they jumps")
This works out pretty well, actually. In his dissertation, Debusmann comes up with fairly broad-coverage grammars for English and German, both of which have some involved syntax. What his grammars don't cover, though, is coordination -- he doesn't have support for conjunctions at all. It turns out that conjunctions are really hard for most grammar formalisms.
It's especially bad for dependency grammar because it seems like an inherently phrasal thing. What's the subject of this sentence?
Jake and Dolores eat yogurt.
You really want to say that it's "Jake and Dolores", but DG can't do that! Each link in the parse goes from one word to one other word. And there's a constraint that says that each verb has only one subject. What to do?
Worse, the sort of sentence that syntacticians seem to love: "Dolores makes and Max delivers yogurt" -- the two verbs here seem to share a direct object. But our "tree principle" says that each word in the graph should only have one head.
Well, let's break the constraints!
... that's the next post, in preparation!
Tuesday, April 20, 2010
what I'm working on: L3 overview
I haven't been writing much about what I'm working on. So let me tell you! If you prefer code to text about code: here's our project.
I'm working with the HLTDI group at IU, with Prof. Mike Gasser. Our goal is to do machine translation for medium-sized languages (say, those with a few million speakers) that don't have a lot of money behind them, and thus, not a lot of training data available. There are projects at other universities to do similar things, so we're definitely not alone. A lot of people would like to have good MT for "minority languages".
You might be familiar with statistical machine translation, which is all the rage right now, and with good reason! It works impressively well in cases where you have enough training data to sensibly cover the space of sentences that you'd like to translate. This is what Google is doing.
It's not what we're doing, for three reasons: (1) for the languages that we'd like to handle, Quechua and Amharic, there's some training data available, but not nearly enough to get a good SMT system going. (2) Both of these languages happen to have really complex morphology, so the probability of seeing a given word is extremely low, since so many different words are possible, and (3) we're not doing translation at all, yet. (but we will.)
Since we won't have enough training text to infer what we need from examples, we're going to have to make claims about what the grammars of our target languages are, and build parsers based on that. We'll see how much of the task we can off-load to machine learning over time, but we're prepared to do some grammar engineering if we need to. It turns out, thankfully, that when a language has complex morphology, it tends to have simpler syntax! You have to put the information somewhere.
So what we do have, is a bunch of morphological analyzers that Mike made, and we're working on the parser, which is going to grow to be the whole MT system once we work out how to make our grammar formalism generate the output language while it's parsing the input language, what you might call "synchronous grammar".
More about the parser and what I've been working on there, in the next post!
Subscribe to:
Posts (Atom)