Emerging Computational Linguistics

I received this text in an email.  It pretty much says it all.

i cdnuolt blveiee taht I cluod aulaclty uesdnatnrd waht I was rdanieg. The phaonmneal pweor of the hmuan mnid, aoccdrnig to a rscheearch at Cmabrigde Uinervtisy, it dseno’t mtaetr in waht oerdr the ltteres in a wrod are, the olny iproamtnt tihng is taht the frsit and lsat ltteer be in the rghit pclae. The rset can be a taotl mses and you can sitll raed it whotuit a pboerlm. Tihs is bcuseae the huamn mnid deos not raed ervey lteter by istlef, but the wrod as a wlohe. Azanmig huh? yaeh and I awlyas tghuhot slpeling was ipmorantt!

Yoav Seginer wrote his dissertation on the Incremental Parser.  The paper is pretty easy to read – accessible.  The introduction is an especially well written introduction to unsupervised grammar induction.

I was surprised to read what he had to say about substitutability.   Substitutability is the capacity to replace phrases with other phrases that are of the same type.  For example ‘the dog’ in ‘the dog ran to town’ can be replaced with ‘it’.   So in some sense, the phrase ‘the dog’ and ‘it’ can be substituted for each other.  This is one of the cornerstones of linguistic theory and is used as a basis of many parsing techniques.  The PCFG parser uses probabilities for a phrase type that can be traded out in a given context.

However, Seginer makes the claim that substitutability is not required for his incremental parser.

Substitutability, the essential idea of the Harris method, which has been seen as a starting point for the induction process for so long, turns out to be unnecessary in unsupervised parsing.

 …unlabeled parsing which only requires the parser to identify the constituents (or dependency links) but does not require them to be labeled, is purely syntagmatic (by definition).   A parser induction algorithm can therefore focus on learning to detect syntactic units while ignoring substitutability. (p20)

Another fresh idea (to me) from Seginer’s paper is the skewness of language structure.

The syntactic structure of natural language is skewed. This simply means that when the syntactic structure of an utterance is represented by a tree, each node in the tree has at least one short branch. The shorter the shortest branch is, the greater the skewness.  (p22)

Essentially how the incremental parser takes advantage of skewness is to expect skewness in the parse result.  This reduces the search size and thereby make the parsing process more efficient.

…context free grammars, allow (a-priori) any tree structure and, therefore, a learning algorithm for such representations must discover by itself the skewness property of syntactic trees. However, if this property is indeed universal, there is no need to burden the learning algorithm with its discovery and it is possible to code skewness directly into the parser.  (p23)

He claims that ‘coding the skewness’ into the syntactic representation and the parser, i.e., expecting branches to be of mixed depths, does not retract from the accuracy of the parse result.

Here is a link to Yoav’s dissertation.  Dissertation

Since graduating in 2007, it looks like Yoav Seginer is working at a  small company in Amsterdam, Mondria Technologies Ltd (according to LinkedIn.com).  The company website doesn’t say anything yet.  I wonder if they are working on a project that uses the incremental parser.

This paper by Yoav Seginer is very exciting.  It covers a method of learning a language grammar that resonates with my mental model of how a young child learns language.  These are some aspects of the Seginer algorithm.

Incremental Learning.  The system adds information to the grammar with each new sentence.  In other approaches (CCM by Manning and Klein, UDOP by Bod), the entire corpus is processed as a block to collect the parameters of the grammar and the entire corpus is repeatedly processed until the learning converges on final result.  In Seginer’s approach, the corpus is processed one sentence at a time.  After each sentence, the grammar weights are updated.  That sentence is not revisited for further training.

Simpler Math.  The approach by Seginer uses much simpler math for computing the parameters of the resulting grammar.   There are a few ratios, some accumulation of values into other, and some comparison of weights to choose which one to apply for a given step.  There are no long chains of probabilities to compute the best parse.  I don’t have any principled reason why this makes more sense for a model of how the brain works – it just fits my gut feeling better.

Not Restricted to Binary Trees.  The CMM approach and others approaches that are referenced in Seginer’s paper all give binary parse trees as the result.  But natural languages aren’t limited to binary trees.  Although it is possible to represent any non-binary tree as a binary tree, forcing a binary representation onto natural language is not adding to the value of the result.  Seginer’s process gives parse trees that include constructions of more than two nodes.

Exocentric Constructions.   A phrase like ‘the boy’ has links going both directions between the two words.  Either word can be considered the head of the phrase – which in some way matches the disagreement between linguists about which word is actually the head of the phrase.

Link depths.  His algorithm result include a depth value on dependency links.  This value can be used to distinguish between internal and external arguments to a phrase.

Incremental Parsing.  For each word read into the sentence, links can only be added to or from the new word.

             I know the boy (sleeps)

When the algorithm encounters the word sleeps it can only add a link to or from this word.  No links that were generated at earlier steps can be affected.   This reduces the search space and contributes to the overall speed of the parser.  Another advantage is that the links in ‘I know the boy’ are an exact subset of the links in ‘I know the boy sleeps’.  There is no decision necessary about dropping links that were previously discovered.

No Clustering.  Seginer’s approach groups words with class labels that in some respect are part of speech classes.  However, the approach does not require clustering of words into specific classes.  It finds similarities between the and a but it does not require that all determiners are grouped together in a well defined class.  This makes the approach better able to deal with noise in the training data.

Homophony.  When a word has more than one meaning, it can confuse any machine algorithm.  Seginer’s algorithm deals with homophony by comparing labels between target pairs of words.  In the example that follows, words in brackets are possible labels for the target words.  When an underscore appears in the label, it means look at  the label of the preceding or following word.

             This[the] year[_the]    (this is a determiner)

            This[is_] was [is]          (this is a pronoun).

In the example given above, in one case this is a determiner.  One of its labels is [the] because this and the occur in similar places.  In the second line a label for this is [is_] which means that this is frequently followed by is.  The algorithm finds pairs of labels such as [the] and [_the] or [is_] and [is] to decide where to put links.

I think Seginer’s approach has some real merit.  It is a greedy algorithm – it learns as it goes and does not need to revisit previous sentences.  It uses simple math.  It has results that seem to match psycholinguistic models.   It would be great to see this approach extended to take advantage of other linguistic phenomena such as morphology.

 A link to the paper can be found here.  Paper

 A link to a video presentation on the approach can be found here.    Video

Today I was pondering the issue of head directionality of languages – does the head of a phrase come before or after the remaining portion of the phrase.  This parameter has been largely disregarded because most languages are inconsistent its use.

However, it occurred to me that infants could rely on the heavy weighting of head directionality when they are first learning a language.  By choosing the direction that is predominant and ignoring the incoming utterances of the opposite direction, it would simplify the initial learning phase.

Perhaps someone has already proposed this little insight into child language acquisition.

As I was pondering this, it also occurred to me that the single most important characteristic of a language is that it can be learned by an infant.  If the majority of infants in a culture can’t learn the language of their parents, then that language will not persist.  It will die out.

Perhaps someone else has already proposed this little insight as well.

Here are two links to videos on Unsupervised Learning of natural language syntax.

Chris Manning gave this talk at MLCS 2007.  It is a fairly detailed discussion of the work that Chris did with Dan Klein on learning syntax structure.  Dan used the material for his dissertation.

Chris Manning Video

Dan Klein gave this talk at UAI 2008.  It is more high level, and describes how Dan and his students have applied their work to a few other areas of unsupervised learning.

Dan Klein Video

Both these videos are worth watching.

I have been reading The Stuff of Thought by Steven Pinker which is a survey of different ways language gives clues to how the mind works.  (See my related entry dated September 28, 2007)  In the fourth chapter, he gives a very enlightening portrayal of how language describes objects in space. 

“Languages tend to have terms for contact, vertical alignment, attachment, containment, and proximity, as if there were a cognitive alphabet of spatial relationships more basic than the prepositions of a given language.”  (p. 178)

“A light bulb is considered to be in a socket when its base is inserted, since that allows it to be illuminated, but a person is not in a car if only his arm extends in through a window, since that doesn’t allow the car to move him or even shelter him.” (p. 187)  The meaning of the preposition in depends on the objects that are being described.

“If Sally has one big stone and Jenny three much smaller stones, who has more?  The question by itself is unanswerable: it depends on whether you mean “more stone”, or “more stones.”  (p. 173)   The meaning of more depends on whether it is referring to the number of objects (stones) or the mass/volume/weight of the object (stone).

“The part of the mind that interfaces with language treats objects schematically.  … Every morsel of matter has a length, a width, and a thickness, but when we speak of these morsels we pretend that some of the dimensions aren’t there. … A road, a river, or a ribbon is conceptualized as an unbounded line (its length which serves as its single primary dimension) fattened out by a bounded line (its width which serves as a secondary dimension), resulting in a surface.”  (pp. 179, 180)

 ”Since words and syllables aren’t free, languages economize when they can. … Imagine you are in a rainstorm, ten feet away from an overhanging ledge.  Move one foot toward it, you still get wet.  Move over another foot; you still get wet.  Keep moving, and at some point you no longer get wet.  Continue to move another foot in the same direction, you don’t get any dryer.  So nature has set up a discontinuity between the segment of the path where gradual changes of position leave you equally wet and the segment where gradual changes leave you equally dry.  And it is exactly at that discontinuity that one would begin to describe your position using under rather than near.”  (P 186)

“Spatial terms quantize space at the cusps where causal events play out differently on each side.  As your palm gradually [wraps] around a marble, the curvature at which you stop saying the marble is on the hand and start saying it’s in is more or less the shape that would prevent it from rolling off when you jiggle it.”  (P 186)

Dr. Pinker’s premise in this book is that language reflects our thoughts.  By disecting our language, we get a glimpse of how the thought engine behind the language works.  We use count nouns and mass nouns in language because our minds see countable items such as chairs or dogs and our minds also see non-countable mass objects such as water or furniture.  We use a preposition like along to describe proximity to a one-dimensional line and we use inside to describe containment in a two or three dimensional object. 

All languages take slightly different approaches to describing space, but there are similarities that can possibly be used to infer an underlying brain structure that helps define our language.  “Most of the world’s languages divide the space around the speaker into just two regions, though about a quarter of them (including Spanish) make a three-way distinction among ‘near me’, ‘far from me’, and ‘in between,’ and a very few go to four, adding ‘very far from me’.” (p. 178)  He is referring to the English terms here (near me) and there (far from me).

“Not all languages carve [spatial relationships] up in the same way.  Presumably this is because each language trades off expressiveness, precision, word length, and vocabulary size in a different way.  But the quantization of spatial relations is universal, and causally important relations like contact, attachment, alignment, verticality and proximity make their appearance in all the spatial vocabularies of the world.”  (p. 187)

The book is an excellent example of Dr. Pinker’s writing – it is entertaining while at the same time being specific and to the point.  He digs into the issues and comes at them from all aspects – cognitive psychology, neuro-science, pathology, and child language acquisition.  He is an academic, and at the same time he presents his material in a way that is concise and engaging.

I am taking Ling566, Introduction to Syntax for Computational Linguistics, at the University of Washington as part of a Master’s program in Computational Linguistics.  The course is taught by Dr. Emily Bender who is also the director of the program.

This week Emily was introducing how feature structures are used to create a grammar description for English.  A big part of the grammar is the syntax portion, how words are formed into phrases and phrases are joined into sentences.  Feature structures are a way of adding detail to a grammar so that things like agreement can be accounted for.

As part of her lecture she said, “There is no magic in syntax.”

What she means by this is that when specifying the grammar using feature structures, all of the details have to be specified.  If something is left out of the definition, then the grammar will not work correctly.

A statement that is similar to this that I am fond of repeating is “It does exactly what you tell it to.”  What is meant by this is that the computer is a machine that executes the instructions given to it – it executes them faithfully.  When a program runs correctly and performs the desired actions without any negative side effects, this is because the program was written that way.  And just the same, when a program crashes and you lose your data, this is because the instuctions in the program have been arranged in a way that makes it crash.

At any rate, I am thoroughly enjoying taking classes at UW.  It is a thrill to be spending all of my time focused on CL.

This year I have been enjoying a Gary Larson daily calendar.  It goes without saying that Gary has a unique insight into reality in our lives.  Many of his cartoons use issues that are illuminated by a linguistic view point.

For example, in this frame, the dog has written a threat letter to the cats, but the dog only uses one word.

Our dog certainly has a wider vocabulary than one kind of bark, but for each situation such as a barking at a stranger, he only uses one ‘word’.  However, he does vary his barks.  Some barks are louder and there is variation in pitch.  His series of barks could be interpretted as having prosody (variation in pitch and emphasis).  Of course, we as humans can’t tell if there is any information that can be interpretted from the variation, or if it just means that he is not capable of generating a series of barks that are identical.

Here is another frame relating to dogs.  Dogs certainly understand many human words – their name, ‘out’, ‘walk’, ’sit’, ‘go lay down’, etc.  But dogs don’t make a relationship between words when uttered in a series.  My interpretation is that they hear one or two words in a context and use that as the entire meaning of the situation.  Our dog is very tuned into ‘walk’.

This frame is about meeting aliens and trying to communicate through translation of language.  The assumption is that if we do ever meet an alien, that the same technique for language translation we use between human languages will also work with aliens.  This will certainly be the place to start, but what if the alien brain language structures are different than ours?  In other words, Chomksy has helped us see that all human languages are based on similar structures, but if we do meet aliens, we won’t necessarily be able to rely on the existence of that similarity.

This frame shows how a misinterpretation of a foreign word can be used as a joke.  Of course, Webster’s gives us the definition for Kemosabe as “faithful friend”.

This frame shows a common play on words.  Take a phrase or frequent saying and replace one or more of the words.  Also in this case, he is using a homophone (same sound different spelling) for ‘ate’ versus ‘8′.

This frame makes fun of our basic drives for attracting mates.  The truth is that many of our instincts come from our more simple ancestors.  The only real difference between us and lower animals is that we are self-aware and are able to modify our behavior in much more complex ways.

My appologies to the copyright holder of these images.

I have been working with feature structures as a means of specifying correct parses of sentences.  There are several resources that I have used in this work:

• Syntactic Theory (Sag, Wasow, Bender, 2003), covers the linguistic theory behind feature structures for parsing sentences.  This text is very intense, so it makes sense to understand natural language syntax before starting this book.
• Implementing Typed Feature Structures (Copestake, 2002) covers a tool (LKB) that is available to download and try.  Here is a link to the LKB page.  http://wiki.delph-in.net/moin/LkbTop

I spent quite a bit of time reading Syntactic Theory and then downloaded LKB and to play with it.  At this point my understanding of what was going on accellerated considerably.  My recommendation is to get LKB as soon as possible, instead of waiting to read most of Syntactic Theory before starting with LKB.  This will give you a chance to try things to see how they fit together which will help you grasp the text better.

Ann Copestake’s book is a very good description of how to use LKB.  Initially I tried learning LKB without the book.  Part of the book is available in PDF form, but I did better after I bought the book.

Imagine a picture puzzle that is inside-out.  The edges of the puzzle start in a small square with an empty space in the middle.  The smooth edges face in to the center.  As pieces are added to the puzzle, the area gets larger, but there is no finish to it.  Each row that is added around the outside has larger total area than the previous row.

This is how I see computational lingusitics.  We are learning some of the basics of language and how computers can interact with humans using it.  But we are still at the middle of the picture.

There is lots of research occuring in areas that are developing the pieces:

• Voice recognition and generation.
• Word semantics – finding relationships between words.
• Document extraction and summarization.
• Question Answering.
• Information retrieval.
• Analysis of syntax, discourse.

Much of this research is providing some amount of useful result.  There are real world applications that are being created based on these results that are helping users get their job done.

But we have not yet arrived at the part of the puzzle solving process where large sections fall together and a whirlwind of activity suddenly explodes out of the pieces.  We have not yet achieved the level of mastery where suddenly ‘aha’ occurs and we see how syntax, semantics and a theory of meaning form the basis for a system that learns meaning from the words it encounters without being supervised.

Eventually we will get computers to the point of the Enterprise mainframe.

• We will be able to interact with the computer by voice with ambiguity of context, sentence structure, and word sense. 
• The computer will acknowledge our individuality and adjust its responses to match.
• The computer will have access to a large body of knowledge to use for responses to questions.
• Answers to questions will be generated in context from the deep structure of the underlying knowledge.  Answers will be generated in the language of the questioner even though the knowledge may have been extracted from a source in a different language.
• When you ask a question, the computer will answer with a single result.  You won’t need to sift through 198,235 pages to find what you are looking for.

We are not there yet.   

In the mean time, the small advances being made toward that vision with today’s real world applications are the places where we are learning.   Each researcher that attempts to solve the puzzle in a different way adds to our total understanding.  It is the incremental steps that eventually get us to the larger results.