Hello!
I'm looking for a German grammar for an chart parser in LISP. I intend
to use it to parse this kind of algebra word problems the kids have to
solve at school. It would be nice, if anyone could help me with this.
Thanks in advance!
... Tobias
Tobias Grimm wrote:
> I'm looking for a German grammar for an chart parser in LISP. I intend
> to use it to parse this kind of algebra word problems the kids have to
> solve at school. It would be nice, if anyone could help me with this.
I can't help with your actual request, but I can suggest that
if you haven't already read Norvig's "Paradigms of Artificial
Intelligence Programming" you'd probably find it very interesting.
(It discusses (1) chart parsers, (2) Lisp, and (3) solving
algebra word problems, although it doesn't combine #1 and #3.
Norvig also doesn't use the term "chart parsers" except in an
aside noting that a simple bottom-up parser, plus memoisation,
is essentially the same thing.)
--
Gareth McCaughan ················@pobox.com
sig under construction
On 29 Oct 1999 00:22:58 +0100, Gareth McCaughan
<················@pobox.com> wrote:
>I can't help with your actual request, but I can suggest that
>if you haven't already read Norvig's "Paradigms of Artificial
>Intelligence Programming"
I read this book. The discussion about the algebra word problems in
there is based on the program STUDENT, that was developed in the 60's
by D. Bobrow. The program uses a patternmatching to transform a text
in algebraic equations. The problem is, that I have to parse a much
more complex text. My Idea was, that I first solve any references in
the text and then replace words, that have the same meaning.
With the so transformed text, it should be possible to use it with the
STUDENT program.
The problem is, that German is a terrible language and I can't find a
simple grammar.
Here's an example (translated to English... sorry for any mistakes) of
the word problems:
Anne will fly the first time in her life with the plane. She flys with
her mother and her father in an airplane. It has 34 times 2 seats on
the left and right side. In the middle there are 29 times six seats.
How much passengers can fly with the aircraft?
Maybe you have any idea?
bye, Tobias
Tobias Grimm wrote:
[I said:]
>> I can't help with your actual request, but I can suggest that
>> if you haven't already read Norvig's "Paradigms of Artificial
>> Intelligence Programming"
>
> I read this book.
OK; then you didn't need my recommendation. Fine. :-)
> The discussion about the algebra word problems in
> there is based on the program STUDENT, that was developed in the 60's
> by D. Bobrow. The program uses a patternmatching to transform a text
> in algebraic equations. The problem is, that I have to parse a much
> more complex text. My Idea was, that I first solve any references in
> the text and then replace words, that have the same meaning.
> With the so transformed text, it should be possible to use it with the
> STUDENT program.
> The problem is, that German is a terrible language and I can't find a
> simple grammar.
>
> Here's an example (translated to English... sorry for any mistakes) of
> the word problems:
>
> Anne will fly the first time in her life with the plane. She flys with
> her mother and her father in an airplane. It has 34 times 2 seats on
> the left and right side. In the middle there are 29 times six seats.
> How much passengers can fly with the aircraft?
>
> Maybe you have any idea?
I don't think you have a hope of solving problems like this
without something much deeper than mere parsing. To solve this
you need to understand that an aeroplane has passenger seats
on both sides and in the middle, and nowhere else; and that
you get one passenger per seat. In other words, you need some
non-trivial real-world knowledge and some way of using it.
You also need to decide whether "34 times 2 seats on the left
and the right side" means "on each side" or "between the two
sides", which either requires some more knowledge of the way
seats are laid out in an aeroplane, or needs some pretty
sophisticated heuristic ideas about the way words get used
in practice.
That's real AI; you need a lot more than a parser.
Perhaps what you said about "solve any references in the
text" means that you propose to tell it that "passengers"
and "seats" are synonyms (which, of course, they aren't).
I think the problem is still much too hard, and I think
the difficulties of parsing German are the least of your
worries.
--
Gareth McCaughan ················@pobox.com
sig under construction
On 30 Oct 1999 01:03:37 +0000, Gareth McCaughan
<················@pobox.com> wrote:
>> I read this book.
>OK; then you didn't need my recommendation. Fine. :-)
But the book is quit good! :-)
>I don't think you have a hope of solving problems like this
>without something much deeper than mere parsing.
I know. But I have to find at least a solution that will work with a
few different word problems. It's more some kind of theoretical task.
It's a work I have to do for my study.
> To solve this
>you need to understand that an aeroplane has passenger seats
>on both sides and in the middle, and nowhere else;
The problem is to extract this information from a natural language
text. There are so much varieties and uncertainties that require a
huge background knowledge.
>you get one passenger per seat. In other words, you need some
>non-trivial real-world knowledge and some way of using it.
You're right, that's the real problem.
>That's real AI; you need a lot more than a parser.
Maybe I should forget the parser and try to find a solution with an
more or less intelligent pattern matching.
But that would mean, that the varieaty of the word problems will be
very much restricted.
>I think the problem is still much too hard, and I think
>the difficulties of parsing German are the least of your
>worries.
Tell that to my professor! :-)
bye, Tobias
On Sat, 30 Oct 1999 11:42:51 +0100, Tobias Grimm <············@gmx.de>
wrote:
> On 30 Oct 1999 01:03:37 +0000, Gareth McCaughan
> <················@pobox.com> wrote:
[...]
> >I think the problem is still much too hard, and I think
> >the difficulties of parsing German are the least of your
> >worries.
>
> Tell that to my professor! :-)
You may try to compare the cost of paying a programmer to write a good
German parsing application, and the cost of letting the user attend an
English course that makes him able to interact with an English user
interface :)
Paolo
--
EncyCMUCLopedia * Extensive collection of CMU Common Lisp documentation
http://cvs2.cons.org:8000/cmucl/doc/EncyCMUCLopedia/
On Sun, 31 Oct 1999 12:57:46 GMT, ·······@mclink.it (Paolo Amoroso)
wrote:
>> >the difficulties of parsing German are the least of your
>> >worries.
>You may try to compare the cost of paying a programmer to write a good
>German parsing application, and the cost of letting the user attend an
>English course that makes him able to interact with an English user
>interface :)
Interesting idea... But I don't think, my professor will like it as
much as I do :-)
bye, Tobias
Paolo Amoroso wrote:
> You may try to compare the cost of paying a programmer to write a good
> German parsing application, and the cost of letting the user attend an
> English course that makes him able to interact with an English user
> interface :)
Not entirely fair, since you only have to pay the programmer
to do it *once*, whereas there's likely to be more than one
user. :-)
--
Gareth McCaughan ················@pobox.com
sig under construction
Tobias Grimm wrote:
>>> I read this book.
>> OK; then you didn't need my recommendation. Fine. :-)
>
> But the book is quit good! :-)
It's more than just "quite good"!
>> I don't think you have a hope of solving problems like this
>> without something much deeper than mere parsing.
>
> I know. But I have to find at least a solution that will work with a
> few different word problems. It's more some kind of theoretical task.
> It's a work I have to do for my study.
What level of study? Undergraduate, or PhD, or what? (Presumably
not research, or it would be *your* choice whether to do this...)
>> you get one passenger per seat. In other words, you need some
>> non-trivial real-world knowledge and some way of using it.
>
> You're right, that's the real problem.
It's also a central problem in AI (unless someone solved it
while I wasn't looking...). If you're really being expected
to solve it, I can only conclude that whoever asked you to
do so has a *very* hige opinion of your abilities.
Anyway, good luck...
--
Gareth McCaughan ················@pobox.com
sig under construction
Gareth McCaughan <················@pobox.com> writes:
> It's also a central problem in AI (unless someone solved it
> while I wasn't looking...). If you're really being expected
> to solve it, I can only conclude that whoever asked you to
> do so has a *very* hige opinion of your abilities.
Or, more likely, the one expecting him to do it has no understanding
of the subject matter. Sadly, this seems to be happening much too
frequently in german german universities nowadays. When you get
lecturers in computer graphics, who don't understand the difference
between pixels and dots in the dot-mask of monitors, who believe that
chips like nVidia's TNT obviate SGI and who seemingly get most of
their material either from other lecturers or from consumer
publications like c't, you do start to wonder...
Regs, Pierre.
--
Pierre Mai <····@acm.org> PGP and GPG keys at your nearest Keyserver
"One smaller motivation which, in part, stems from altruism is Microsoft-
bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]
On 31 Oct 1999 15:28:20 +0000, Gareth McCaughan
<················@pobox.com> wrote:
>> But the book is quit good! :-)
>It's more than just "quite good"!
Sure... unfortunately, I didn't had the time to read the whole book.
>What level of study? Undergraduate, or PhD, or what?
Undergraduate!
>(Presumably not research, or it would be *your* choice whether to do this...)
I think research in natural language processing isn't really my thing
:-) I'm more interested in Data Mining, Agents and so on.
>It's also a central problem in AI (unless someone solved it
>while I wasn't looking...). If you're really being expected
>to solve it, I can only conclude that whoever asked you to
>do so has a *very* hige opinion of your abilities.
I don't think, that I will find a real solution. But I hope, that I
will develop at least a solution that can solve a hand full of
different algebra word problems. At least I will not give up so fast
:-)
>Anyway, good luck...
Thanks!
bye, Tobias
With apologies to Fermatt:
Gareth McCaughan <················@pobox.com> writes:
>
> It's also a central problem in AI (unless someone solved it
> while I wasn't looking...).
I discovered a very interesting and general solution to this problem,
but there isn't enough room on the margins of my screen to write the
entire program.
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
After making a joke like that, i would not be doing anything risky for a
couple of days at least!!!
coby
Thomas A. Russ <···@sevak.isi.edu> wrote in message
····················@sevak.isi.edu...
>
> With apologies to Fermatt:
>
> Gareth McCaughan <················@pobox.com> writes:
> >
> > It's also a central problem in AI (unless someone solved it
> > while I wasn't looking...).
>
> I discovered a very interesting and general solution to this problem,
> but there isn't enough room on the margins of my screen to write the
> entire program.
>
> --
> Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
Tobias Grimm <············@gmx.de> writes:
>
> Anne will fly the first time in her life with the plane. She flys with
> her mother and her father in an airplane. It has 34 times 2 seats on
> the left and right side. In the middle there are 29 times six seats.
> How much passengers can fly with the aircraft?
Of course, once you even have this parsed, you will still have a common
sense inference problem to solve. The information about quantities
describes "seats", whereas the question asks about the number of
"passengers". Somewhere you will need to know that the number of seats
in an aircraft determines the number of passengers that can be
accomodated.
> Maybe you have any idea?
>
> bye, Tobias
Good luck, this sounds like a challenging problem to be working on.
Regardless of the outcome, I think you will learn a lot about AI working
on this.
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
I just wonder: In the problems there are some words that reoccur: "How many"
for example. So the words are naturally divided into three classes: Those
"recurrent word", then the words that carry no sense (der die das etc.) and
finally the substantives that carry the meaning. So the system would try to
classify the words in the text and if there are unknow substantives (and at
the beginning they all will be) then it asks you. And then the inference is
entered. What I would be interested in, is this: If you work so through a
schoolbook, maybe you can solve a significant number of problems by this
type of "educated guessing" in another schoolbook?
It is well known that pupils often do the same (I think this principle is
called "coherence".) When for example children were given the problem
"Somebody has 120 sheep and 6 dogs. How old is he?". The children said this
was a difficult problem (they also had other problems to solve) as they
tried to add first and when it did not work they subtracted but that did not
work either! So finally they "found out" that they had to divide the 6 into
the 120. And then everything made sense and the person was 20 years old.
This is called numerical coherence.
Janos Blazi
Thomas A. Russ <···@sevak.isi.edu> schrieb in im Newsbeitrag:
···············@sevak.isi.edu...
> Tobias Grimm <············@gmx.de> writes:
> >
> > Anne will fly the first time in her life with the plane. She flys with
> > her mother and her father in an airplane. It has 34 times 2 seats on
> > the left and right side. In the middle there are 29 times six seats.
> > How much passengers can fly with the aircraft?
>
> Of course, once you even have this parsed, you will still have a common
> sense inference problem to solve. The information about quantities
> describes "seats", whereas the question asks about the number of
> "passengers". Somewhere you will need to know that the number of seats
> in an aircraft determines the number of passengers that can be
> accomodated.
>
> > Maybe you have any idea?
> >
> > bye, Tobias
>
> Good luck, this sounds like a challenging problem to be working on.
> Regardless of the outcome, I think you will learn a lot about AI working
> on this.
>
> --
> Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
On Wed, 3 Nov 1999 02:05:06 +0100, "Janos Blazi" <······@netsurf.de>
wrote:
>I just wonder: In the problems there are some words that reoccur: "How many"
>for example. So the words are naturally divided into three classes: Those
>"recurrent word", then the words that carry no sense (der die das etc.) and
>finally the substantives that carry the meaning.
The problem ist, that the substantives alone don't carry a meanig. But
what you describe is close to the STUDENT program by Daniel Bobrow. It
tries a patternmatching and replacing with some reoccuring patterns to
transform the text into equations. That works quit fine, but is very
restricted and doesn't "understand" the text in any way.
>It is well known that pupils often do the same (I think this principle is
>called "coherence".) When for example children were given the problem
>"Somebody has 120 sheep and 6 dogs. How old is he?". The children said this
>was a difficult problem (they also had other problems to solve) as they
>tried to add first and when it did not work they subtracted but that did not
>work either! So finally they "found out" that they had to divide the 6 into
>the 120. And then everything made sense and the person was 20 years old.
>This is called numerical coherence.
So you mean to solve the problem by trying all possibilities until you
get an answer that makes sense?
It should be no problem in creating some rules to define, that the
possibily, that a person is 20 is greater than the possibility, that a
person is 114. But for some more complex problems, this won't work.
bye, Tobias
> So you mean to solve the problem by trying all possibilities until you
> get an answer that makes sense?
> It should be no problem in creating some rules to define, that the
> possibily, that a person is 20 is greater than the possibility, that a
> person is 114. But for some more complex problems, this won't work.
>
Though what I said is true, this is of course a horror scenario! Of course
this does not work!
Janos Blazi
> So you mean to solve the problem by trying all possibilities until you
> get an answer that makes sense?
> It should be no problem in creating some rules to define, that the
> possibily, that a person is 20 is greater than the possibility, that a
> person is 114. But for some more complex problems, this won't work.
>
Though what I said is true, this is of course a horror scenario! Of course
this does not work!
Janos Blazi
On 02 Nov 1999 07:56:53 -0800, ···@sevak.isi.edu (Thomas A. Russ)
wrote:
>sense inference problem to solve. The information about quantities
>describes "seats", whereas the question asks about the number of
>"passengers". Somewhere you will need to know that the number of seats
>in an aircraft determines the number of passengers that can be
>accomodated.
It would be enough to define some background knwoledge like
"number_of_seats = number_of_passengers". Of course this would not be
very correct, but a more complex representation of background
knwoledge would be much more complicated.
>Good luck, this sounds like a challenging problem to be working on.
It is indeed :-) But I'm afraid, that I won't get the result, I would
like to get.
>Regardless of the outcome, I think you will learn a lot about AI working
>on this.
I already did.
bye, Tobias
Tobias Grimm <············@gmx.de> writes:
>
> On 02 Nov 1999 07:56:53 -0800, ···@sevak.isi.edu (Thomas A. Russ)
> wrote:
>
> >sense inference problem to solve. The information about quantities
> >describes "seats", whereas the question asks about the number of
> >"passengers". Somewhere you will need to know that the number of seats
> >in an aircraft determines the number of passengers that can be
> >accomodated.
>
> It would be enough to define some background knwoledge like
> "number_of_seats = number_of_passengers". Of course this would not be
> very correct, but a more complex representation of background
> knwoledge would be much more complicated.
But there are enough exceptions on the same rule !
2 children <2- 6 yrs-of-age == 2 passengers == 1 seat
1 wounded passengers on stretcher >= 3 seats
plus 1 seat for mandatory company == 2 passengers and >=4 seats.
then #-of-seats !== #of--passengers AND #-of-passensers !==
3-of-payed-seats;
But the plane still would be fully booked ;-)
BTW :
Personnel !== seats and !==passengers !== payload (human)
But will account to the total of human-entities on-board.
cor
--
/* If GNU/LINUX has no solution, you have the wrong problem */
/* Q: $:which Linux ······@amsat.org A: $:ANY linux */
/* I prefer Slackware */
/* http://utopia.knoware.nl/users/ccgestjr/linux.html */