edu(b)log

Graduating

I'm graduating December 11, 2006. So there will no longer be notes added to this site! But I will leave it here for those of you who still wish to use it as a tool to study.... It's been a great few years and I wish you all the best!

P.S. If the notes help you at all, click on an ad or something to help me keep this site running. Thanks!

The Last Class...!

Example 1

Mike went to Tampa on a truck.

Semantically, Mike is the agent. Syntactically, it is the subject. Semantically, "went" is a change of location (Change-Location). "to Tampa" is the destination (to-loc). "on a truck" is the instrument. Mike is actually the scene because he caused the change of location himself.

Example 2

Mike went from Orlando to Tampa on a truck in the morning.

"Mike" = agent & scene
"from Orlando" = from-loc
"to Tampa" = to-loc
"in the morning" = at-time

Example 3

Mike studied at the library.

"Mike" = agent
"at the library" = at-loc and at-time

Example 4

Mike ate an apple in the evening.

"an apple" = theme

Example 5

The door broke.

"The door" = theme

The agent will be the one performing the action (a human or animal), while the theme will be the thing that undergoes the action.

Example 6

The plane crashed.

"The plane" = theme

The plane destroyed several houses.

"The plane" = inanimate cause
"several houses" = theme

So we have a new term, inanimate cause, which is like a theme but for inanimate objects.

Example 7

Mike studies at the library around the corner.

A*

A* is a best-first algorithm that is also optimal, insofar as the heuristic used is a good one. A best-first is a heuristic algorithm that uses a heuristic function to expand the nodes. It's a greedy algorithm that jumps all over the tree. If we can establish that a heuristic is admissible then that best-first algorithm becomes an A* algorithm.

Lisp

There are two functions in your notes which are very useful. The most trivial one (delete-last) takes a list of atoms and deletes the last one. It uses head recursion.

> (delete-last '(a b c d))
(a b c)

The other one (more complex) will get any atoms in a given tree. It uses tail and head recursion. (get-at)

More exam stuff

You may be asked to prove something using the GPS axioms or using resolution.

…
(P ∧ ¬ R) ∨ ¬ R
(P ∨ ¬ R) ∧ (¬Q ∨ ¬R)

Go over transferring simple English statements into predicate calculus. (e.g. Every student answered the questions).

Parsing Sentences cont.

Last class, we decided that the ATM will not parse the sentence, "The teacher wanted to read a book." It is because there is no prepositional phrase that has a noun in it. So it will die on "to read."

The subject of "wanted" is "the teacher" and the subject of "to read" is "the teacher" also. But we would not say "the teacher wanted the teacher to read a book" because it is repetitive. There are many sentences in English that follow this pattern.

The teacher wanted the students to read a book.

The direct object of "wanted" is the entire phrase "the students to read a book." The direct object is what is wanted.

Additions to the ATM

What would you have to do to the ATM to handle a sentence of this nature? You would have to complicate the ATM! Dr. Gomez gave out the last handout with the updated ATM.

There are three new arcs on this new sheet, but we are only interested in 17 and 18 (13 will not be included on the final exam). Arcs 17 and 18 use z-slash notation. It means to give a recursive call to z (you will call the entire ATM recursively). There are no conditions on 17 (taken non-deterministically). There is, however, an initialization. You will initialize some registers when you do the recursive call. The action is taken when we come back to the point after we recurse.

Trace (The teacher wanted to read a book)

SUBJECT(the teacher)
MAIN-VERB(wanted)
3, 4, 5, and 8 all fail.
Recurse-17 {
	SUBJECT1(teacher)
	MAIN-VERB1(read)
	DO1(a book)
	JUMP
	SEND
}
DO(SUBJECT1, MAIN-VERB1, DO1)

Trace (The teacher wanted the students to read a book)

SUBJECT(the teacher)
MAIN-VERB(wanted)
DO(the students)
Recurse-18 {
	SUBJECT1(the students)
	MAIN-VERB1(read)
	DO1(a book)
}
IO(the students)
DO(SUBJECT1, MAIN-VERB1, DO1)

Note: This works only using 18 but not 17.

A relative clause is a clause that describes a noun. For example, "the person who went to the store" is a relative clause. Differentiating between "that" and "who" is complicated.

The computer's life is made easier when you have stricter rules, but many people make the mistake of using "that" instead of "who" when qualifying a human. Humans can use knowledge to decipher whether the "that" qualifies a person or a thing, but it's much harder for the computer to do that.

The horse raced past the barn fell is the same as The horse which was raced past the barn fell. The human parse breaks down around the dangling participle. This is an example of why you cannot build a deterministic parser for English; you need to be able to back out. The human parser is not parallel, i.e. "raced" can be used two ways but you cannot parse them both at the same time.

Relative clauses occur in every language (Chomsky referred to this as universal linguistics.

The teacher the students like left.

The direct object of "like" is "the teacher."

The teacher the students the children admire like left.

A computer will handle this sentence easily, but humans can't easily parse this sentence. According to the formalism the grammar is perfect. According to human users, the grammar is weird. The reason is because we can keep very few items in our "stack." Our stack "overflows" very easily. We see that when our stack has three items it overflows! This only happens when you have self-embedded sentences (recursion).

We can parse a sentence like "The cat that ate the mouse that ate the cheese that came from Spain left." It's because each embedded sentence has its Direct Object attached.

You can use commas to separate main clauses from subordinate clauses (While I was reading, I got sick), delimit a list (apples, oranges, and monkeys), and "opposition" (not sure if this is the word he meant) phrases like "Giraffes, African mammals, like green valleys."

Comparative phrases add complexity. There is a big difference between "My children eat more apples than yours" and "My children eat more apples than oranges." We are using semantic knowledge to eliminate a tremendous combinatorial expression. When you try to parse these using only syntax, you wind up with ambiguity — more than one syntactically correct parse."

More Sentence Parsing

For the homework: Use the "member" function we learned in class using equal instead of eq.

The ATM on page 217 cannot parse the sentence, "The deer ran."

Example 1

"The deer ate the apple."

a → b: Subject = The deer
b → c: Main-verb = ate
c → d: Direct object = the apple

Example 2

"The apple was eaten by the deer."

Trace:

a → b: (1) Subject = The apple
b → c: (2) Main-verb = was
c → d: (4) Voice = passive. Auxiliaries = was. Main-verb = eat. Direct Object = The apple. Subject = dummy
d → d: (7) Subject = the deer

There are two separate parses of this sentence. One implies that the apple was eaten in close proximity to the deer. The other (more likely) interpretation is that the deer ate the apple.

Example 3

"The teacher gave the children a book."

a → b: (1) Subject = the teacher
b → c: (2) Main-verb = gave
c → d: (5) DO = the children
d → ?

This ATM on page 217 does not parse this sentence. "The children" will be the indirect object and "the book" will be the direct object.

Now, using the ATM on 224:

a → b: (1) Subject = the teacher
b → c: (2) Main-verb = gave
c → d: (5) DO = the children
d → e: (6) IO = the children, DO = a book

The ATM on 224 does not, however, parse, "The teacher wanted to read the book."

Dissecting Sentences

In the final, he may give us a grammar and a sentence and ask us to do a derivation of the sentence in a tree.

Bring the grammar handout with you to the final exam.

• Name an English sentence that the grammar given in class does not generate. "Give me a book." (Any sentence that starts with a verb). You could add S → VP as a rule to make this sentence work. Another sentence would be, "Are you studying for the exam?" Also, "Which books do you like?" It also fails to handle compound sentences (e.g. Mary went to the store and bought an apple.) It won't handle any sentence that starts with a prepositional phrase.

What if we add VP → Verb NP NP? Then we can have sentences like, "Peter gave the children a book."

There's another way to parse besides building trees: sentence diagramming.

A recursive transition network is a nondeterministic finite state automata. But it happens that the nondeterministic finite state automata and the recursive transition network and the CFG generate the same number of sentences.

The Recursive Transition Netowrk diagram is the preffered way to analyze a sentence.

Example: The bird on the roof vanished.

Here, "vanished" is an intransitive verb.

An augmented transition network (ATM) is like a recursive transition network, but it has been augmented with actions. This method of parsing was popular until several years ago when people forgot about it. The idea is that we want to build a subject out of a direct object and indirect object.

"The man ate a pea."

SUBJ (The man)
MV (ate)
DO (a pea)

"The man vanished."

SUBJ (The man)
---- uh oh it won't parse this sentence.

"The apple was eaten by Mary."

Final Register:

  DO (The apple)
  AUX (was)
  MV (eaten)
  Prep (by)
  SUBJ (Mary)

The last step in the trace is abbreviated but the first two steps are accurate:

1. a → b: SUBJ (The apple)
2. b → c…
   S-4: Voice is passive. AUX (was). SUBJ (dummy NP).
3. c → d: MV (eaten), Prep (by), SUBJ (Mary).

Example: The lion was killed by the fire. "By the fire" could mean the lion was killed near the fire or that the fire actually killed the lion. So there will be two parses.