PARSER COMPARISON

[Anne Sing]

Before going into a detailed discussion of the points made in Daniel Sleators
last message, I would like to point out that the one point he has not
made is that his parser cannot conform to the majority of all three areas
of our challenge except through assertion.  Taking a look at his web site you
will find a parser that will provide a complex tree that can only be read by
those
who have studied his Link theory of grammar.  There is a minor bit of
labelling of
parts of speech, but there is no indication, he can accurately label
subjects verbs,
objects and complements of any sort.  There is also no indication that he
can return
multiple strings of ambiguous sentences ("John saw a man in the park" or
"the Chinese
Insructor.")

Most importantly, there is absolutely no indication that he can do anything
with the
trees that he provides; e.g. can he change actives to passives, statements to
questions or answer questions?  The answer is probably no but we simply do
not know.  A parser that merely produces a set of obscure trees is of value to
no one.

This is precisely the reason that Derek and I have issued this challenge.
If a parser
is parsing it should be able to meet the minimum requirements of our
challenge in a
way that ANYONE can see, not just those who are the insiders of a particular
theory
or those with a strong background in syntax.

Parsing that merely results in a labelled bracketing or a tree structure is
nothing
more than an intellectual exercise.

DO SOMETHING WITH IT THAT ALL CAN JUDGE OR KEEP IT OUT OF THE RUNNING
UNTIL YOU CAN is the motto we bring to this challenge.

Particularly, put something on the web that indicates that you can do something
of value such as ask and answer questions or correct grammar.  These functions
absolutely require that you can accurately handle all the items listed in
our challenge
or you can't do them at all.

Certainly, in the private sector, individuals who have to make decisions
concerning
parsers are not going to be linguists.  Also, you cannot ask them to get a
degree
in linguistics before they are qualified to make such decisions.  If that is
a requirement
companies are simply not going to participate.

HERE IS A MORE DETAILED RESPONSE TO DANIEL SLEATOR'S MESSAGE
At 11:34 AM 1/1/97 -1000, Daniel Sleator wrote:

He begins with a review of our challenge.

>Philip Bralich suggests that those of us working in the area pf parsing
>should make our systems available via the web.  Davy Temperley and I are
>in full agreement with this.  That's why a demonstration of our link
>grammar system has been up on the web for over a year.  Go to
>"www.cs.cmu.edu/~sleator" and click on "link grammar" to get to the
>parser page.
>
>Philip has also proposed a set of criteria by which parsing systems can
>be judged:
>
>> In addition to using a dictionary that is at least 25,000 words in
>> size and working in real time and handling sentences up to 12 or 14
>> words in length (the size required for most commercial applications),
>> we suggest that parsers should also meet the following standards
>> before engaging this challenge:
>>
>> At a minimum, from the point of view of the STRUCTURAL ANALYSIS OF
>> STRINGS, the parser should:, 1) identify parts of speech, 2) identify
>> parts of sentence, 3) identify internal clauses, 4) identify sentence
>> type (without using punctuation), and 5) identify tense and voice in
>> main and internal clauses.
>>
>> At a minimum from the point of view of EVALUATION OF STRINGS, the
>> parser should: 1) recognize acceptable strings, 2) reject unacceptable
>> strings, 3) give the number of correct parses identified, 4) identify
>> what sort of items succeeded (e.g. sentences, noun phrases, adjective
>> phrases, etc), 5) give the number of unacceptable parses that were
>> tried, and 6) give the exact time of the parse in seconds.
>>
>> At a minimum, from the point of view of MANIPULATION OF STRINGS, the
>> parser should: 1) change questions to statements and statements to
>> questions, 2) change actives to passives in statements and questions
>> and change passives to actives in statements and questions, and 3)
>> change tense in statements and questions.
>
>Whether or not anybody else agrees that these are the right desiderata,
>it's useful that he's put them forward.  We can use them to evaluate
>our own work, and Bralich's work as well.  We have done this, and
>it seems to us that our system is superior to Bralich's.


This is only an assertion until the functions are written that show this in a
manner an outisder can judge.  If you can do it at all then you know that
each function can be written in one day.

They should take the part of speech and part of sentence info and all the
other info and arrange it in a way that is easy to read for all:

For example:

The man who mary likes is reading a book

"The" is an article
"man" is a noun


"The man who mary likes is" is the subject of "is reading"
"who" is the direct object of the verb "likes"

This is a statement
It is simple present active

And so on

Expecting the user to learn your theory before he can see these things is just
asking too much.

>The version of link grammar that we have put up on the web already does
>very well in a number of these criteria.

But not many.  And not in a way that others can see or judge.

> Regarding STRUCTURAL ANALYSIS,
>the parser outputs a representation of a sentence which contains much of
>the information discussed by Bralich. Parts of speech are shown
>explicitly; things like constituent structure are virtually explicit
>(for example, a subject phrase is anything that is on the left end of an
>"S" link). Tense and aspect are not explicit in the output, but they
>could quite easily be recovered.

Then lets see it.  Which is really all we are asking in this challenge.

Regarding EVAULATION OF STRINGS, our
>system is far superior to the Ergo parser. Our system does an excellent
>job of distinguishing acceptable from unacceptable sentences.

It is very difficult to see this.  Certainly, many of the bad sentences we
typed in looked like they parsed.  More suspiciously, I typed in a number
of ambiguous sentences and it returned only parse each.

>Furthermore, it is often able to obtain useful structural information
>from non-grammatical sentences, by making use of "null-links".

I have no idea what this means as do many readers I suspect.

>Below we
>discuss some basic problems with the Ergo parser regarding its
>evaluation and analysis of sentences.  We have not implemented a
>MANIPULATION OF STRINGS component. We have worked out a sentence
>constructing mechanism that we believe would be able to handle this as
>well.  Of course we'll have to do the work to make this convincing.  We
>may be inspired to add this feature as a result of these discussions.

This again is not at all clear.  Make a function where we can see this.
Until you
show your ability to manipulate strings this is just an assertion.  Also
your ability
to recognize a question/statement/command as well as tense and voice
is not shown.  Further whether a sentence is simple compound or complex
is not mentioned.

>Bralich's aim is to build a parser that will be useful for interactive
>games and other applications. It is therefore restricted to short
>sentences, and has a fairly small vocabulary.

Our vocabulary of over 50,000 words is double his stated vocabulary of 25,000.
Further, the smaller the dictionary the less problems there will be with
ambiguity.  We take the risk with the higher vocabulary and have no serious
problems.
We also handle large sentences like anyone else; however, on sentences
with more than 14 or 15 words we cannot yet meet the standards of our challenge
which is much more comprehensive than what is required by Mr. Sleator.  We
will be able to do this in two or three months for now we limit ourselves to
sentence
lengths that are amenable to easier applications. We can now do as much as
Mr. Sleator with large sentences but that does not satisfy the challenge.  When
we can do all of our challenge they will also be on our web site.  (This
could be
as early as two months from now).

As it stands if the link parser were asked to do interactive games it is
unclear whether
he could do much at all as we do not know that he can make a question from a
statement
let alone answer one.  Further until he clearly indicates his parsers
ability to find subjects
and objects and so on there is no way we can expect his parser to properly
analyze
questions or return appropriate responses.

However, even with these
>constraints, there are a number of very basic constructions that his
>parser cannot handle. Here are some examples. All of the sentences below
>are simply rejected by his parser.



>       I went out              The parser does not allow two-word verbs
>       He came in              like "set up", "go out", "put in", which are
>       He sent it off          extremely common.
>       I set it up

He did find some verbs with some problems, but in general we handle these.

>       He did it quickly       The parser seems to have extremely limited
>                               use of adverbs. (It does accept some
>                               constructions of this type, like "He ran
>                               quickly", so perhaps this is a bug.)

We have not yet allowed such adverbs to attach sentence finally. It is a
small task,
but we have not yet done it.  I will see if the programmer has time for this
tomorrow.

One extremely important plus for our parser is that it is easy to trouble
shoot.  All of the
problems mentioned here will be fixed before the month is out.  Many much
sooner.

>       John and Fred are here  The parser does not know that conjoined
>                               singular noun phrases take plural verbs.

This should also be fixed by tomorrow.

I am sorry that some of what is happening here may seem like our beta
testing.  That is,
comments such as these help us find and correct problems.  Again we are not
promising
that we can do everything, merely that ours is the best and that it can be
judged in an
open forum.

>       The dog jumped and the  The parser does not seem to
>       cat ran                 accept ANY sentences in which clauses
>                               are joined with conjunctions.

We only recently began adding coordinate structures.  Complex phrases will
be done soon, but the
coordination of verb phrases (john read a book wrote a paper and took a
test) is about six weeks
away.

>       He said he was coming   The parser accepts "He said THAT he was
>                               coming"; but it does not allow deletion of
>                               "THAT", which is extremely common with some
>                               verbs

We will add this.  I was unaware that our subcategorization frame for "say"
did not allow that.

>       I made him angry        There are a number of kinds of verb
>       I saw him leave         verb complements which the parser does
>       I suggested he go       not handle: direct object + adjective
>                               ("I made him angry"), direct object +
>                               infinitive ("I saw him leave"),
>                               subjunctive ("I suggested [that] he go").

Again we will add these and easily 90% of the errors that we encounter
during this public
announcement in very short time.

>       His attempt to do it    The parser cannot handle nouns that take
>       was a failure           infinitives.



>       I went to the store     The parser cannot handle the extremely
>       to get some milk        common use of infinitive phrases meaning
>                               "In order to".

I will add it.
>
>There are also cases where the parser assigns the wrong interpretation
>to sentences. One of the biggest problems here is in the treatment of
>verbs. Verbs in English take many different kinds of complements: direct
>objects, infinitives, clauses, indirect questions, adjectives, object +
>clause, and so on. The Ergo Parser seems to treat all of these
>complements as direct objects, and makes no distinctions between which
>verbs take which kind. This means, in the first place, that it will
>accept all kinds of strange sentences like "I chased that he came",
>blithely labeling the embedded clause as an object of "chased". More
>seriously, this often causes it to assign the wrong interpretation to
>sentences. For example,

This is not true.  Try it.

>       I left when he came

>The verb "left" can be either transitive or intransitive. Here, it is
>clearly being used intransitively, with "when he came" acting as a
>subordinate clause. But the Ergo Parser treats "when he came" as a
>direct object.

Yes, again something we will add.  As you will note, though we parse
complex and compound sentences, we do not label parts of speech
in those sentences.  We will soon.

Of course, you should note that we have no idea whether or not the
link parser can label parts of the sentence at all.

>The program does not seem to analyze relative clauses at all. In
>the sentence
>
        The dog I saw was black


How can you say we do not analyze relative clauses when we get them
exactly correct.  You can say

        the dog I saw
        the dog that I saw
        the dog which I saw

and recieve a correct and complete analysis.


>the parser states that "I" is the subject of "saw", and that "The dog I
>saw" is the subject of "was",

which is exactly correct.
>but does not state that "dog" is the
>object of "saw". The program also accepts


We could but we decided not to because we thought it would be confusing for
the user.  In a sentence like "the dog which I saw" or "the dog which I saw" we
would label "THAT"  or "WHICH" as the object of "saw" which is more accurate.
We could also label "dog" as the object which has some sense to it as well,
but we decided against it.

You might try the more difficult "the man who mary likes is reading a book" or
an example of your own.  I know in the past we have had trouble with the sub-
categorization frame for "saw" and I am not sure if we have fixed it or not.
 "The dog I died was black"

>(analyzing it in the same way), further indicating that it simply has no
>understanding of relative clauses.

>In the sentence "How big is it", the program analyzes "how big" as the
>subject of the sentence.

Yes, "How" questions are still on the programmers desk.  They will be there in
about a week.

>We were able to identify all these problems with the Ergo parser without
>knowing anything about how it works -- the formalism used is
>proprietary.  A plethora of new problems would probably emerge if we
>knew how it worked.  And all of these problems will probably be
>exacerbated with longer sentences.

On the contrary, the fact that the link parser just gives an obscure tree
rather than a user-friendly output, it is impossible to know  if his
parser does much of anything at all.

>All of these problems with the Ergo Parser - constructions that it does
>not accept, and things that it mis-analyzes - are things that our system
>handles well. Indeed, the _original_ 1991 version of our parser could
>handle all these things. In our version 2.0, released in 1995, we
>incorporate many constructions which are less common. We should point
>out that even the latest version of our parser is far from perfect. It
>finds complete, correct parses for about 80% of Wall Street Journal
>sentences.

This is merely assertion.  You simply must prerpare the functions that
will show this to the user and put that on the web.  Especially, you
need to show that your parser can handle the manipulation of strings
rather than just a bracketing.  A bracketing is meaningless unless
you can use it to do something with the langauge you are analyzing.
No one really cares about statistical analyses of words or sentences
what people need and want are applications that will allow them to use
real language in real time with computer applications.  There is nothing
at your site that indicates your ability to do this.

>The reader can try both systems for himself or herself, and come to
>his/her own conclusions.  (The Ergo parser is at www.ergo-ling.com, ours
>is at www.cs.cmu.edu/~sleator.)

Yes, please.

>      Daniel Sleator <sleator at cs.cmu.edu>
>      Davy Temperley <dt3 at columbia.edu>


In sum, the purpose of our challenge is to allow the academic community and
private sector an opportunity to see and judge for themselves what is
possible in the area of the analysis of grammar.  We proposed a set of
minimum standards that are necessary to show that  a parser is what we
call "commercially viable."  Until the link parser demonstrates its ability to
meet these challenges in a way that anyone can see, we simply do not
know that it is "commercially viable."

Further, we did not claim that our parser was perfect. Just the best.  And that
we are willing to put it to the test.  An imporant aspect of our parser is that
it is easy to trouble shoot.  Early next week we will go through all the
sentences
that were input during this challenge and then address the problems.  This will
take a few days to a couple of weeks depending on the problem.  Please try these
parsers and then try them again in a couple of weeks.  I am sure you will agree
that we have redifined what parsing is and can be.

I also suspect that the link parser will not be able to meet the challenge any
more in two weeks than it is now; that is, with a user friendly web site
rather than assertion and obfuscation.

Phil Bralich

Philip A. Bralich, Ph.D.
Presidend and CEO
Ergo Linguistic Technologies
2800 Woodlawn Drive, Suite 175
Honolulu, HI 96822
Tel:(808)539-3920
Fax:(808)539-3924

Sincerely,

Anne Sing
ERGO LINGUISTIC TECHNOLOGIES
Manoa Innovation Center
2800 Woodlawn Drive, Suite 175
Honolulu, Hawaii  96822
TEL: (808) 539-3920
FAX: (808) 539-3924