CSC 594 Topics in AI Natural Language Processing

CSC 594 Topics in AI Natural Language Processing

CSC 594 Topics in AI Natural Language Processing Spring 2018 8. Formal Grammar of English (Some slides adapted from Jurafsky & Martin) 1 Syntax By grammar, or syntax, we have in mind the kind of implicit knowledge of your native language that you had mastered by the time you were 3 years old without explicit instruction

Not the kind of stuff you were later taught in grammar school Speech and Language Processing - Jurafsky and Martin 2 Syntax Why should you care? Grammars (and parsing) are key components in many applications

Grammar checkers Dialogue management Question answering Information extraction Machine translation Speech and Language Processing - Jurafsky and Martin 3

Syntax Key notions that well cover Constituency Grammatical relations and Dependency Heads Key formalism Context-free grammars Resources Treebanks

Speech and Language Processing - Jurafsky and Martin 4 Constituency The basic idea here is that groups of words within utterances can be shown to act as single units. And in a given language, these units form coherent classes that can be be shown to behave in similar ways With respect to their internal structure And with respect to other units in the language Speech and Language Processing - Jurafsky and Martin

5 Constituency For example, it makes sense to the say that the following are all noun phrases in English... Why? One piece of evidence is that they can all precede verbs. This is external evidence Speech and Language Processing - Jurafsky and Martin

6 Grammars and Constituency Of course, theres nothing easy or obvious about how we come up with right set of constituents and the rules that govern how they combine... Thats why there are so many different theories of grammar and competing analyses of the same data. The approach to grammar, and the analyses, adopted here are very generic (and dont correspond to any modern linguistic theory of grammar).

Speech and Language Processing - Jurafsky and Martin 7 Context-Free Grammars Context-free grammars (CFGs) Also known as Phrase structure grammars Backus-Naur form Consist of Rules Terminals

Non-terminals Speech and Language Processing - Jurafsky and Martin 8 Formal Definition of CFG More formally, a CFG consists of Speech and Language Processing - Jurafsky and Martin 9

Example Grammar Rules Speech and Language Processing - Jurafsky and Martin 10 Example Lexicon 11 Generativity As with FSAs and FSTs, you can view these rules as either analysis or synthesis machines

Generate strings in the language Reject strings not in the language Impose structures (trees) on strings in the language Speech and Language Processing - Jurafsky and Martin 12 Derivations Syntax Tree A derivation is a sequence of rules applied to a string that accounts for

that string Covers all the elements in the string Covers only the elements in the string Speech and Language Processing - Jurafsky and Martin 13 Bracketed Notation

Sometimes it is convenient to represent a parse tree in a compact format. 14 Phrase Structure of English Sentences Noun phrases Agreement Verb phrases Subcategorization

Speech and Language Processing - Jurafsky and Martin 15 Sentence Types Declaratives: A plane left. S NP VP Imperatives: Leave! S

VP Yes-No Questions: Did the plane leave? S Aux NP VP WH Questions: When did the plane leave? S WH-NP Aux NP VP Speech and Language Processing - Jurafsky and Martin

16 Noun Phrases Lets consider the following rule in more detail... NP Det Nominal Most of the complexity of English noun phrases is hidden in this rule. Consider the derivation for the following example All the morning flights from Denver to Tampa leaving before 10 Speech and Language Processing - Jurafsky and Martin

17 Noun Phrases Speech and Language Processing - Jurafsky and Martin 18 NP Structure Head Noun Clearly this NP is really about flights. Thats the central critical noun in this NP. Lets call that the head.

We can dissect this kind of NP into the stuff that can come before the head, and the stuff that can come after it. Speech and Language Processing - Jurafsky and Martin 19 Determiners Noun phrases can start with determiners... Determiners can be Simple lexical items: the, this, a, an, etc. A car

Or simple possessives Johns car Or complex recursive versions of that Johns sisters husbands sons car Speech and Language Processing - Jurafsky and Martin 20 Nominals Contains the head and any pre- and postmodifiers of the head. Pre Quantifiers, cardinals, ordinals... Three cars

Adjectives and Aps large cars Ordering constraints Three large cars ?large three cars Speech and Language Processing - Jurafsky and Martin 21 Postmodifiers Three kinds Prepositional phrases

From Seattle Non-finite clauses Arriving before noon Relative clauses That serve breakfast Same general (recursive) rule to handle these Nominal Nominal PP Nominal Nominal GerundVP Nominal Nominal RelClause Speech and Language Processing - Jurafsky and Martin

22 Agreement By agreement, we have in mind constraints that hold among various constituents that take part in a rule or set of rules For example, in English, determiners and the head nouns in NPs have to agree in their number. This flight Those flights

*This flights *Those flight Speech and Language Processing - Jurafsky and Martin 23 Problem Our earlier NP rules are clearly deficient since they dont capture this constraint NP Det Nominal Accepts, and assigns correct structures, to grammatical examples (this flight)

But its also happy with incorrect examples (*these flight) Such a rule is said to over-generate. Speech and Language Processing - Jurafsky and Martin 24 Verb Phrases English VPs consist of a head verb along with 0 or more following constituents which well call arguments.

Speech and Language Processing - Jurafsky and Martin 25 Subcategorization But, even though there are many valid VP rules in English, not all verbs are allowed to participate in all those VP rules. We can subcategorize the verbs in a language according to the sets of VP rules that they participate in. This is a modern take on the traditional notion of transitive/intransitive.

Modern grammars may have 100s or such classes. Speech and Language Processing - Jurafsky and Martin 26 Subcategorization Sneeze: John sneezed Find: Please find [a flight to NY]NP Give: Give [me]NP[a cheaper fare]NP Help: Can you help [me]NP[with a flight]PP Prefer: I prefer [to leave earlier]TO-VP Told: I was told [United has a flight]S

Speech and Language Processing - Jurafsky and Martin 27 Subcategorization *John sneezed the book *I prefer United has a flight *Give with a flight As with agreement phenomena, we need a way to formally express the constraints.

Speech and Language Processing - Jurafsky and Martin 28 Possible CFG Solution Possible solution for agreement. Can use the same trick for all the verb/VP classes.

SgS -> SgNP SgVP PlS -> PlNp PlVP SgNP -> SgDet SgNom PlNP -> PlDet PlNom PlVP -> PlV NP SgVP ->SgV Np

Speech and Language Processing - Jurafsky and Martin 29 CFG Solution for Agreement It works and stays within the power of CFGs But its ugly And it doesnt scale all that well because of the interaction among the various constraints explodes the number of rules in our grammar. Speech and Language Processing - Jurafsky and Martin

30 Long-Distance Dependencies Long-distance dependencies arise from many English constructions including wh-questions, relative clauses, and topicalization. What these constructions have in common is a constituent that appears somewhere distant from its usual, or expected, location. e.g. the flight that United diverted The direct object the flight has been moved to the beginning of the clause, while the subject United remains in its normal position.

What is needed is a way to incorporate the subject argument, while dealing with the fact that the flight is not in its expected location. 31 The Point CFGs appear to be just about what we need to account for a lot of basic syntactic structure in English. But there are problems That can be dealt with adequately, although not elegantly, by staying within the CFG framework. There are simpler, more elegant, solutions that

take us out of the CFG framework (beyond its formal power) LFG, HPSG, Construction grammar, XTAG, etc. Chapter 15 explores the unification approach in more detail Speech and Language Processing - Jurafsky and Martin 32 Treebanks Treebanks are corpora in which each sentence has been paired with a parse tree (presumably the right one).

These are generally created By first parsing the collection with an automatic parser And then having human annotators correct each parse as necessary. This generally requires detailed annotation guidelines that provide a POS tagset, a grammar and instructions for how to deal with particular grammatical constructions. Speech and Language Processing - Jurafsky and Martin 33

Penn Treebank Penn TreeBank is a widely used treebank. Most well known is the Wall Street Journal section of the Penn TreeBank. 1 M words from the 1987-1989 Wall Street Journal. Speech and Language Processing - Jurafsky and Martin 34

Treebank Grammars Treebanks implicitly define a grammar for the language covered in the treebank. Simply take the local rules that make up the subtrees in all the trees in the collection and you have a grammar. Not complete, but if you have decent size corpus, youll have a grammar with decent coverage. Speech and Language Processing - Jurafsky and Martin 35

Treebank Grammars Such grammars tend to be very flat due to the fact that they tend to avoid recursion. To ease the annotators burden For example, the Penn Treebank has 4500 different rules for VPs. Among them... Speech and Language Processing - Jurafsky and Martin 36

Heads in Trees Finding heads in treebank trees is a task that arises frequently in many applications. Particularly important in statistical parsing We can visualize this task by annotating the nodes of a parse tree with the heads of each corresponding node. Speech and Language Processing - Jurafsky and Martin 37

Lexically Decorated Tree Speech and Language Processing - Jurafsky and Martin 38 Head Finding The standard way to do head finding is to use a simple set of tree traversal rules specific to each non-terminal in the grammar. Speech and Language Processing - Jurafsky and Martin

39 Noun Phrases Speech and Language Processing - Jurafsky and Martin 40 Treebank Uses Treebanks (and head finding) are particularly critical to the development of statistical parsers Chapter 14

Also valuable to Corpus Linguistics Investigating the empirical details of various constructions in a given language Speech and Language Processing - Jurafsky and Martin 41 Dependency Grammars In CFG-style phrase-structure grammars the main focus is on constituents. But it turns out you can get a lot done with just binary relations among the words in an

utterance. In a dependency grammar framework, a parse is a tree where the nodes stand for the words in an utterance The links between the words represent dependency relations between pairs of words. Relations may be typed (labeled), or not. Speech and Language Processing - Jurafsky and Martin 42 Dependency Relations

Speech and Language Processing - Jurafsky and Martin 43 Dependency Parse They hid the letter on the shelf Speech and Language Processing - Jurafsky and Martin 44 Dependency Parsing

The dependency approach has a number of advantages over full phrase-structure parsing. Deals well with free word order languages where the constituent structure is quite fluid Parsing is much faster than CFG-bases parsers Dependency structure often captures the syntactic relations needed by later applications CFG-based approaches often extract this same information from trees anyway. Speech and Language Processing - Jurafsky and Martin 45

Dependency Parsing There are two modern approaches to dependency parsing Optimization-based approaches that search a space of trees for the tree that best matches some criteria Shift-reduce approaches that greedily take actions based on the current word and state. Speech and Language Processing - Jurafsky and Martin 46

Summary Context-free grammars can be used to model various facts about the syntax of a language. When paired with parsers, such grammars consititute a critical component in many applications. Constituency is a key phenomena easily captured with CFG rules. But agreement and subcategorization do pose significant problems Treebanks pair sentences in corpus with their corresponding trees.

Speech and Language Processing - Jurafsky and Martin 47

Recently Viewed Presentations

  • JEOPARDY! Click Once to Begin Greek City States

    JEOPARDY! Click Once to Begin Greek City States

    JEOPARDY! Click Once to Begin Greek City States Template by Bill Arcuri, WCSD
  • Powerful Ways to Engage Students Using Google Classroom

    Powerful Ways to Engage Students Using Google Classroom

    One stop shop for main course materials. Create Announcements, Assignments, and Questions ... Primary Teacher. Secondary Teacher. Add materials such as: links, Drive files, YouTube videos and attachments ... Post to more than one class! Add topics to organize your...
  • Multimedia for Book Publishers: Transmedia Storytelling ...

    Multimedia for Book Publishers: Transmedia Storytelling ...

    Growing up in Findlay, Ohio, on lazy summer afternoons, I would read aloud to my grandmother who was blind. She would read to me too, her fingers flying over the Braille. From the deep cushions on her porch, we were...
  • The Writing Process - Dakota State University

    The Writing Process - Dakota State University

    The Writing Process Steps in the Writing Process Steps are: Prewriting Drafting Revising Editing Publication Prewriting Topic Audience Content Prewriting Help students organize their thoughts. Drafting "Getting It Down" Rough Draft SLOPPY COPY Draft Copy Put the students on the...
  • Geography of Canada SS6G5 & SS6G6 Physical Features,

    Geography of Canada SS6G5 & SS6G6 Physical Features,

    Major source of overseas and US/Canada shipping & trade. Closed from November to April (frozen) Seaway has made cities in Eastern Canada home to many successful manufacturing companies . ... Inside of the suitcase, draw FIVE things that you are...
  • Atoms & the Periodic Table - Powers Physical Science

    Atoms & the Periodic Table - Powers Physical Science

    Atoms & the Periodic Table. Test Review. 2011. ... Bohr. Chadwick discovered this particle in the nucleus that was hard to detect because it had the same mass as a proton and was electrically neutral ... Sodium has 11 electrons....
  • deepblue.lib.umich.edu

    deepblue.lib.umich.edu

    The telegraph - 1840s Electronic signal standard still used in network interface cards * CC: BY NC SA 2010 - Don M. Blumenthal More to the Point Hollerith machines - 1886 Punch cards Used for census Still best systems into...
  • Stress: Its Meaning, Impact, and Sources

    Stress: Its Meaning, Impact, and Sources

    Components of the definition of stress Lazarus: Cognitive Appraisal Factors Affecting Appraisals Biopsychosocial Aspects of Stress General Adaptation Syndrome Psychosocial Aspects of Stress Sources of Stress Measuring Stress Good Stress - Bad Stress PowerPoint Presentation