Natural and Context-free Languages (CFLs)/Ambiguity contest

profileRony
AppendixLNaturalLanguageProcessingFile.ppt
Home>Computer Science homework help>Natural and Context-free Languages (CFLs)/Ambiguity contest

Natural Language Processing

Appendix L

Morphological Analysis

  • loudly: composed of two morphemes:
  • loud + ly (adverb).
  • likes: two analyses:
  • like (noun) + s (plural).
  • like (verb) + s (third person singular).
  • leaves: three or more analyses:
  • leaf (noun) + s (plural).
  • leave (noun, as in military leave) + s (plural).
  • leave (verb) + s (third person singular).
  • disparagingly: three morphemes:
  • disparag- (verb) + ing (progressive) + ly (adverb).
  • skies: sometimes the stem is changed:
  • sky (noun) + e + s (plural).

Morphological Analysis

  • toys: change depends on the preceding letter:
  • toy (noun) + s (plural).
  • went: root is nowhere to be found:
  • go (verb) + ed (past).
  • fish: two noun analyses (plus a verb one):
  • fish (noun), no affixes, so the unmarked form, singular, is meant.
  • fish (noun) + (plural).
  • fish (verb).
  • women:
  • woman (noun) + (plural).
  • unfriendly: affixes can be added to both front and end:
  • un (negative) + friend + ly (adverb).

A Tiny Morphological Transducer

Some Transformations It Can Do

  • leaf#  leaf +N +SG
  • leave#  leave +N +SG
  • leave#  leave +V
  • leaves#  leaf +N +PL
  • leaves#  leave +N +PL
  • leaves#  leave +V +3SG
  • lean#  lean +ADJ
  • lean#  lean +V

Part of Speech Tagging

Store ice in the cooler.

store N, V
ice N, V
cooler N, Adj

Information a POS Tagger Needs

  • Given a word, what tags can be applied and how likely is each of them? For example, while the word store can be either a noun or a verb, it is more likely to be a noun than it is to be a verb.

  • Given a particular sentential context, what tag is most likely to come next? For example, a verb rarely comes after the word the.

Two Approaches to POS Tagging

  • Create a set of rules that describe the facts. Match the rules against input sentences to build a tag sequence.

  • Build a hidden Markov model (HMM). Use the Viterbi algorithm to find the path that is most likely to have produced the observed sequence of words.

Using HMMs

  • Let K contain one state for each part of speech tag.
  • Let O be the set of possible words.
  • Let  describe the probabilities, for each tag, of a sentence starting with that tag.
  • Let A describe the transition probabilities, i.e., the probability, given some tag t1, that the next tag will be t2.
  • Let B describe the output probabilities, i.e., the probability, given some tag t, that the word that corresponds to that tag is word w.

Build an HMM M = (K, O, , A, B) as follows:

The Grammar of English

  • Is English regular?

  • Can English be described with a Markov model?

  • Is English context-free?

Is English Regular?

Is English finite?

In the event that the Purchaser defaults in the payment of any installment of purchase price, taxes, insurance, interest, or the annual charge described elsewhere herein, or shall default in the performance of any other obligations set forth in this Contract, the Seller may: at his option: (a) Declare immediately due and payable the entire unpaid balance of purchase price, with accrued interest, taxes, and annual charge, and demand full payment thereof, and enforce conveyance of the land by termination of the contract or according to the terms hereof, in which case the Purchaser shall also be liable to the Seller for reasonable attorney's fees for services rendered by any attorney on behalf of the Seller, or (b) sell said land and premises or any part thereof at public auction, in such manner, at such time and place, upon such terms and conditions, and upon such public notice as the Seller may deem best for the interest of all concerned, consisting of advertisement in a newspaper of general circulation in the county or city in which the security property is located at least once a week for Three (3) successive weeks or for such period as applicable law may require and, in case of default of any purchaser, to re-sell with such postponement of sale or resale and upon such public notice thereof as the Seller may determine, and upon compliance by the Purchaser with the terms of sale, and upon judicial approval as may be required by law, convey said land and premises in fee simple to and at the cost of the Purchaser, who shall not be liable to see to the application of the purchase money; and from the proceeds of the sale: First to pay all proper costs and charges, including but not limited to court costs, advertising expenses, auctioneer's allowance, the expenses, if any required to correct any irregularity in the title, premium for Seller's bond, auditor's fee, attorney's fee, and all other expenses of sale occurred in and about the protection and execution of this contract, and all moneys advanced for taxes, assessments, insurance, and with interest thereon as provided herein, and all taxes due upon said land and premises at time of sale, and to retain as compensation a commission of five percent (5%) on the amount of said sale or sales; SECOND, to pay the whole amount then remaining unpaid of the principal of said contract, and interest thereon to date of payment, whether the same shall be due or not, it being understood and agreed that upon such sale before maturity of the contract the balance thereof shall be immediately due and payable; THIRD, to pay liens of record against the security property according to their priority of lien and to the extent that funds remaining in the hands of the Seller are available; and LAST, to pay the remainder of said proceeds, if any, to the vendor, his heirs, personal representatives, successors or assigns upon the delivery and surrender to the vendee of possession of the land and premises, less costs and excess of obtaining possession.

Is English Regular?

● The rat ran.

● The rat that the cat saw ran.

● The rat that the cat that the dog chased

saw ran.

Let:

A = {cat, rat, dog, bird, bug, pony}

V = {ran, saw, chased, flew, sang, frolicked}.

Let L = English  {The A (that the A)* V* V}.

L = {The A (that the A)n Vn V, n  0}.

Let w = The cat (that the rat)k sawk ran.

A Different Argument

S  if S then S

S  either S or S

S  the man who said S is arriving today

Example sentence:

If either the man who said if it rains then we can’t go is arriving today or the man who said if it’s sunny then we must go is arriving today then we must go.

A Different Argument, Continued

If English were regular, then we could apply the following substitutions and the resulting language would also be regular:

  • Replace if, either and the man who said by (.
  • Replace then, or and is arriving today by ).
  • Replace each sentence that contains no embedded

sentences by c.

If either the man who said if it rains then we can’t go is arriving today or the man who said if it’s sunny then we must go is arriving today then we must go.

Becomes:

((((c) c ))((c) c )) c.

Describing English as Regular Isn’t Very Useful

  • the necessary weak generative capacity, which we define to be the ability to generate all and only the strings in L, and

  • the necessary strong generative capacity, which we define to be the ability not only to generate all and only the strings in L but also to generate, for each of them, at least one meaningful parse tree.

Contrast a context-free grammar with a regular one with respect to:

A (Tiny) CF Grammar of English

S  NP VP

NP  the Nominal | a Nominal | Nominal |

ProperNoun | NP PP

Nominal  N | Adjs N

N  cat | dogs | bear | girl | chocolate | rifle

ProperNoun  Chris | Fluffy

Adjs  Adj Adjs | Adj

Adj  young | older | smart

VP  V | V NP | VP PP

V  like | likes | thinks | shots | smells

PP  Prep NP

Prep  with

S


NP VP

Nominal V NP


Adjs N Nominal


Adj N


the smart cat smells chocolate

Creates This Parse Tree

A Parse Tree Generated by a Regular Grammar

This tree has no meaningful semantics.

Is English Regular?

  • If English is finite, then:

Regular grammars have the weak generative capacity to describe it.

Regular grammars to not have the strong generative capacity to describe it.

  • If English is not finite, then:

Regular grammars have neither the weak nor the strong generative capacity to describe it.

A Letter-Level Markov Model of English

● (k = 1): a a idjume Thicha lanbede f nghecom isonys rar t r ores aty

Ela ancuny, ithi, witheis        weche

● (k = 2): Ther to for an th she con simach a so a impty dough par we

forate for len postrit cal nowillopecide allexis inteme

numbectionsityFSM            Cons onste on codere elexpre ther  

● (k = 3): Ouput that the collowing with to that we’ll in which of that is

returesult is alway ther is id, the cal on the Prove be and N.

● (k = 4): Notice out at least to steps if new Turing derived for

explored.  What this to check solved each equal string it matrix (i, k,

y must be put part can may generated grammar in D.

● (k = 5): So states, and Marting rules of strings.  We may have been

regions to see, a list.  If ? ? unrestricted grammars exist a devices

are constructive-state i back to computation

● (k = 6): We’ll have letter substituted languages that L(G) since we

drop the address to the rule1 were counterexample, that is that we

are true when we switched in how we

● (k = 7): If it does a context-free language 3.  If the model of which

corresponding b’s.  M must have chosen strings as a tree such

characters of some p.

K = 1 means use one letter of context.

A Word-Level Markov Model of English

● (k = 1): there exists at the idea was presented for some finite state 3

together. So U begins in this approach, it is labeled with wj as some

model to position-list, solve-15 can reduce every derivation becomes M1

and the number of A building efficient algorithms.

● (k = 2): The language to be if the various grammar formalisms in which

they were deposited make no moves are possible. The competition can

come from somewhere. Fortunately, there are edges from level nodes to

level nodes. Now suppose that we do with a successful value.

● (k = 4): Again, let st be the working string at any point in its computation it

will have executed only a finite number of squares can be nonblank. And,

even if M never halts, at any point in its computation it will have executed

only a finite number of choices at each derivation step and since each

path that is generated must eventually end, the Turing machine M that

computes it.

● (k = 5): Is there any computational solution to the problem? • If there is,

can it be implemented using some fixed amount of memory? • If there is

no such element, then choose will: • Halt and return False if all the

actions halt and return False. • Fail to halt if there is no mechanism for

determining that no elements of S that satisfy P exist. This may happen

either because v and y are both nonempty and they both occur in region n

Markov Model for Spam Generation

An example:

There was something gipsy-like and agreeable in the dinner, after confident in the character and behaviour of the girl who never was then, of not having been to sleep at all, and by the uncommon Well, I dont know, replied Steerforth, coolly. You may as well This was formerly the castle of the redoubted giant Despair, That affair of the first bond for four thousand five hundred grammar; so that, for a brother and sister, we made a most uneven pair.

Is English Context-Free?

  • Weak generative capacity

  • Strong generative capacity

  • Good engineering

Is English Formally Context-Free?

If either the man who said it would rain is arriving today or the man who said it wouldn’t rain is not arriving today then we must go.

Cross Serial Dependencies

*Chris and the girls runs and swims respectively.

If English is context-free, then so is:

English 

{Chris (and (Chris  the girls))*

runs (and (run  runs))*

respectively}

Each sentence is of the form:

ssverb respectively

What language of a’s and b’s is this similar to?

Swiss German

But English doesn’t really work this way:

● ? Jan and Pat runs and swims, respectively.

● Jan and Pat run and swim, respectively.

But Swiss German does:

Generating Good Parse Trees

One problem is handling gaps:

What did Will say he ate for lunch?

Good Engineering

Chris likes the cat.

* The dogs likes the cat.

The problem arises from the first rule in the grammar:

S  NP VP

We could replace it by:

S  SNP SVP /* single NP and single VP.

S  PNP PVP /* plural NP and plural VP.

But then we’d need two copies of all NP and VP rules.

Good Engineering

The girl likes herself.

* The girl likes himself.

We could again split the grammar:

S  MNP MVP /* masculine.

S  FNP FVP /* feminine.

But now we have four kinds of NP’s and four kinds of VP’s.

Good Engineering

And there is more:

This cat likes chocolate.

* These cat likes chocolate.

The cat likes chocolate.

* The cat sleeps chocolate.

* The bear like chocolate.

The culprit is the rule S  NP VP. Replace NP and VP by:

[ CATEGORY NP [ CATEGORY VP

PERSON THIRD PERSON THIRD

NUMBER SINGULAR] NUMBER SINGULAR]

Replace atomic terminal symbols like bear, with:

[ CATEGORY N

LEX bear

PERSON THIRD

NUMBER SINGULAR]

A Unification Grammar for Subject/Verb Agreement

Replace S  NP VP with:

[ CATEGORY S] 

[ CATEGORY NP [ CATEGORY VP

NUMBER x1 NUMBER x1

PERSON x2 ] PERSON x2 ]

So an NP and a VP can be combined to form an S iff they have

matching values for their NUMBER and PERSON features.

A Unification Grammar for Subject/Verb Agreement

Ambiguity

Ambiguity

Ambiguity

Ambiguity

Other Reasons English Syntax is Hard

* Furiously sleep ideas green colorless.

Colorless green ideas sleep furiously.

Chris cooked.

The potatoes cooked.

Chris and the girls cooked.

* Chris and the potatoes cooked.

? The window needs cleaned.

Speech Understanding

An HMM for hit and hot