logging in or signing up NLP Freedom Download Post to : URL : Related Presentations : Let's Connect Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Copy embed code: Embed: Flash iPad Dynamic Copy Does not support media & animations Automatically changes to Flash or non-Flash embed WordPress Embed Customize Embed URL: Copy Thumbnail: Copy The presentation is successfully added In Your Favorites. Views: 5487 Category: Entertainment License: All Rights Reserved Like it (3) Dislike it (0) Added: November 07, 2007 This Presentation is Public Favorites: 3 Presentation Description No description available. Comments Posting comment... By: prisonbreak1051 (36 month(s) ago) please may i down loadthis because we have a research about AI-NLP Saving..... Post Reply Close Saving..... Edit Comment Close By: nksharma (44 month(s) ago) Pl send me this presentation on firstname.lastname@example.org Saving..... Post Reply Close Saving..... Edit Comment Close By: meenakshi.pariyani (51 month(s) ago) i want to download this ppt for my college presentation................i would highly appreciate if could be given permission to download this.........pls its a humble request......... regards Meenakshi email@example.com Saving..... Post Reply Close Saving..... Edit Comment Close Premium member Presentation Transcript 15-381 Artificial Intelligence: 15-381 Artificial Intelligence Natural Language Processing Jaime Carbonell 13-February-2003 OUTLINE Overview of NLP Tasks Parsing: Augmented Transition Networks Parsing: Case Frame Instantiation Intro to Machine TranslationNLP in a Nutshell: NLP in a Nutshell Objectives: To study the nature of language (Linguistics) As a window into cognition (Psychology) As a human-interface technology (HCI) As a technology for text translation (MT) As a technology for information management (IR)Component Technologies: Component Technologies Text NLP Parsing: text internal representation such as parse trees, frames, FOL,… Generation: representation text Inference: representation fuller representation Filter: huge volumes text relevant-only text Summarize: clustering, extraction, presentation Speech NLP Speech recognition: acoustics text Speech synthesis: text acoustics Language modeling: text p(text | context) …and all the text-NLP componentsOutline of an NLP System: Outline of an NLP System Natural language processing involves translation of input into an unambiguous internal representation before any further inferences can be made or any response given. In applied natural language processing: Little additional inference is necessary after initial translation Canned text templates can often provide adequate natural language output So translation into internal representation is central problem Natural Language input parsing generation Internal representation Natural Language output inferencingTranslation into Internal Representation: Translation into Internal Representation Examples of representations: DB query language (for DB access) Parse trees with word sense terminal nodes (for machine translation) Case frame instantiations (for a variety of applications) Conceptual dependency (for story understanding) Natural language utterance "who is the captain of the Kennedy?" Internal representation ((NAM EQ JOHN#F. KENNEDY (? COMMANDER))Ambiguity Makes NLP Hard: Ambiguity Makes NLP Hard Syntactic I saw the Grand Canyon flying to New York. Time flies like an arrow. Word Sense The man went to the bank to get some cash. and jumped in. Case He ran the mile in four minutes. the Olympics. Referential I took the cake from the table and washed it. ate it. Indirect Speech Acts Can you open the window? I need some air.Parsing in NLP: Parsing in NLP Parsing Technologies Parsing by template matching (e.g. ELIZA) Parsing by direct grammar application (e.g. LR, CF) Parsing with Augmented Transition Networks (ATNs) Parsing with Case Frames (e.g. DYPAR) Unification-Based parsing methods (e.g. GLR/LFG) Robust parsing methods (e.g. GLR*) Parsing Complexity Unambiguous Context-Free O(n2) (e.g. LR) General CF O(n3) (e.g. Early, GLR, CYK) Context-Sensitive O(2n) NLP is "mostly" Context Free Semantic constraints reduce average case complexity In practice: O(n2) < O(NLP) < O(n3) Classical Period : Classical Period LINGUISTIC INPUT PRE-PROCESSOR CLEANED-UP INPUT SYNTACTIC ANALYZER PARSE TREE SEMANTIC INTERPRETER PREPOSITIONAL REPRESENTATION "REAL" PROCESSING INFERENCE/RESPONSE … Baroque Period: Baroque Period LINGUISTIC INPUT PRE-PROCESSOR CLEANED-UP INPUT SYNTACTIC ANALYZER PARSE TREE SEMANTIC INTERPRETER PREPOSITIONAL REPRESENTATION "REAL" PROCESSING INFERENCE/RESPONSE … Renaissance: Renaissance LINGUISTIC INPUT PRE-PROCESSOR CLEANED-UP INPUT SYNTACTIC ANALYZER PARSE TREE SEMANTIC INTERPRETER PREPOSITIONAL REPRESENTATION "REAL" PROCESSING INFERENCE/RESPONSE … Context-Free Grammars: Context-Free Grammars Example: S NP VP NP DET N | DET ADJ N VP V NP DET the | a | am ADJ big | green N rabbit | rabbit | carrot V nibbled | nibbles | nibble Advantages: Simple to define Efficient parsing algorithms Disadvantages: Can't enforce agreements in a concise way Can't capture relationships between similar utterances (e.g. passive and active) No semantic checks (as in all syntactic approaches)Example ATN: Example ATN 1 T (SETR V *) (SETR TYPE “QUESTION”) 2 T (SETR SUBJ *) (SETR TYPE “DECLARATIVE”) 3 (agrees * V) (SETR SUBJ*) 4 (agrees SUBJ *) (SETR V *) 5 (AND (GETF PPRT) (= V “BE”)) (SETR OBJ SUBJ) (SETR V*) (SETR AGFLAG T) (SETR SUBJ “SOMEONE”) 6 (TRANSV) (SETR OBJ *) 7 AGFLAG (SETR AGFLAG FALSE) 8 T (SETR SUBJ *) AUX NP NP V NP V NP 1 8 7 6 5 4 3 2 byLifer Semantic Grammars: Lifer Semantic Grammars Example domain—access to DB of US Navy ships S <present> the <attribute> of <ship> <present> what is | [can you] tell me <attribute> length | beam | class <ship> the <shipname> <shipname> kennedy | enterprise <ship> <classname> class ship <classname> kitty hawk | lafayette Example inputs recognized by above grammar: what is the length of the Kennedy can you tell me the class of the Enterprise what is the length of Kitty Hawk class ships Not all categories are "true" syntactic categories Words are recognized by their context rather than category (e.g. class) Recognition is strongly directed Strong direction useful for spelling correctionSemantic Grammars Summary: Semantic Grammars Summary Advantages: Efficient recognition of limited domain input Absence of overall grammar allows pattern-matching possibilities for idioms, etc. No separate interpretation phase Strength of top-down constraints allow powerful ellipsis mechanisms What is the length of the Kennedy? The Kittyhawk? Disadvantages: Different grammar required for each new domain Lack of overall syntax can lead to "spotty" grammar coverage (e.g. fronting possessive in "<attribute> of <ship>") doesn't imply fronting in "<rank> of <officer>") Difficult to develop grammars Suffers from same fragility as ATNsCase Frames: Case Frames Case frames were introduced by Fillmore (a linguist) to account for essential equivalence of sentences like: “John broke the window with a hammer” “The window was broken by John with a hammer” “Using a hammer, John broke the window” [head: BREAK agent: JOHN object: WINDOW instrument: HAMMER ] Case Frames: Case Frames Fillmore postulated finite set of cases applicable to all actions: [head: <the action> agent: <the active causal agent agent instigating the action> object: <the object upon which the action is done> instrument: <an instrument used to assist in the action> recipient: <the receiver of an action-often the I-OBJ> directive:<the target of an (usually physical) action> locative: <the location where the action takes place> benefactive: <the entity for whom the action is taken> source: <where the object acted upon comes from> temporal <when the action takes place> co-agent: <a secondary or assistant active agent>] Case Frame Examples: Case Frame Examples “John broke the window with a hammer on Elm Street for Billy on Tuesday” “John broke the window with Sally” “Sally threw the ball at Billy” “Billy gave Sally the baseball bat” “Billy took the bat from his house to the playground”Uninstantiated Case Frame: Uninstantiated Case Frame [CASE-F: [HEADER [NAME: “move”] [PATTERN: <move>]] [OBJECT: [VALUE: _______ ] [POSITION: DO] [SEM-FILLER: <file> | <directory>]] [DESTINATION: [VALUE: _________ ] [MARKER: <dest> ] [SEM-FILLER: <directory> | <O-port> ]] [SOURCE: [VALUE: _________ ] [MARKER: <source> ] [SEM-FILLER: <directory> | <I-port> ]]]Case-Frame Grammar Fragments: Case-Frame Grammar Fragments HEADER PATTERN determines which case frame to instantiate <move> “move” | “transfer” | … <delete> “delete” | “erase” | “flush” | … LEXICAL MARKERS are prepositions++ that assign NPs to cases <dest> “to” | “into” | “onto” | … <source> “from” | “in” | “that’s in” | … POSITIONAL INDICATORS also assign NPs to cases DO means “direct object position” (unmarked NP right of V) SUBJ means “subject position” (unmarked NP left of V)Case Frame Instantiation Process: Case Frame Instantiation Process Select which case-frame(s) match input string Match header-patterns against input Set up constraint-satisfaction problem SEM-FILLER, POSITION, MARKER constraints At-most one value per case constraint Any required case must be filled constraint At-most one case per input-substring constraint Solve constraint-satisfaction problem Use least-commitment, or satisfiability algorithmInstantiated Case Frame: Instantiated Case Frame S1: “Please transfer foo.c from the diskette to my notes directory” [CASE-F: [HEADER [NAME: “move”] [VALUE: S1]] [OBJECT: [VALUE: “foo.c” ]] [DESTINATION: [VALUE: “notes directory” ]] [SOURCE: [VALUE: “diskette” ]]]Conceptual Dependency: Conceptual Dependency Canonical representation of NL developed by Schank Computational motivation—organization of inferences [ATRANS [ATRANS rel: POSSESSION rel: POSSESSION actor: JOHN actor: MARY object: BALL object: BALL source: JOHN source: JOHN recipient: MARY] recipient: MARY] "John gave Mary a ball" "Mary took the ball from John" [ATRANS [ATRANS rel: OWNERSHIP CAUSE rel: OWNERSHIP actor: JOHN actor: MARY object: APPLE object: 25 CENTS source: JOHN CAUSE source: MARY recipient: MARY recipient: JOHN "John sold an apple to Mary for 25 Cents."Conceptual Dependency: Conceptual Dependency Other conceptual dependency primitive actions include: PTRANS--Physical transfer of location MTRANS--Mental transfer of information MBUILD--Create a new idea/conclusion from other info INGEST--Bring any substance into the body PROPEL--Apply a force to an object States and causal relations are also part of the representation: ENABLE (State enables an action) RESULT (An action results in a state change) INITIATE (State or action initiates mental state) REASON (Mental state is the internal reason for an action) [PROPEL [STATECHANGE actor: JOHN CAUSE state: PHYSICALINTEGRITY object: HAMMER object: WINDOW direction: WINDOW] endpoint: -10] "John broke the window with a hammer"Robust Parsing: Robust Parsing Spontaneously generated input will contain errors and items outside an interface's grammar Spelling errors tarnsfer Jim Smith from Econoics 237 too Mathematics 156 Novel words transfer Smith out of Economics 237 to Basketwork 100 Spurious phrases please enroll Smith if that's possible in I think Economics 237 Ellipsis or other fragmentary utterances also Physics 314 Unusual word order In Economics 237 Jim Smith enroll Missing words enroll Smith Economics 237What Makes MT Hard?: What Makes MT Hard? Word Sense “Comer” [Spanish] eat, capture, overlook “Banco” [Spanish] bank, bench Specificity “Reach” (up) “atteindre” [French] “Reach” (down) “baisser” [French] 14 words for “snow” in Inupiac Lexical holes “Shadenfreuder” [German] happiness in the misery of others, no such English word Syntactic Ambiguity (as discussed earlier)Bar Hillel's Argument: Bar Hillel's Argument Text must be (minimally) understood before translation can proceed effectively. Computer understanding of text is too difficult. Therefore, Machine Translation is infeasible. - Bar Hillel (1960) Premise 1 is accurate Premise 2 was accurate in 1960 Some forms of text comprehension are becoming possible with present AI technology, but we have a long way to go. Hence, Bar Hillel's conclusion is losing its validity, but only gradually. What Makes MT Hard?: What Makes MT Hard? Word Sense “Comer” [Spanish] eat, capture, overlook “Banco” [Spanish] bank, bench Specificity “Reach” (up) “atteindre” [French] “Reach” (down) “baisser” [French] 14 words for “snow” in Inupiac Lexical holes “Shadenfreuder” [German] happiness in the misery of others, no such English word Syntactic Ambiguity (as discussed earlier)Types of Machine Translation: Types of Machine Translation Interlingua Syntactic Parsing Semantic Analysis Sentence Planning Text Generation Source (Arabic) Target (English) Transfer Rules Direct: SMT, EBMTTransfer Grammars: N(N-1): Transfer Grammars: N(N-1) L1 L1 L2 L2 L3 L3 L4 L4Interlingua Paradigm for MT (2N): Interlingua Paradigm for MT (2N) L 1 L 1 L2 L2 L3 L3 L4 L4 Semantic Representation aka “interlingua” For N = 72, T/G 5112 grammars, Interlingua 144Beyond Parsing, Generation and MT: Beyond Parsing, Generation and MT Anaphora and Ellipsis Resolution "Mary got a nice present from Cindy. It was her birthday." "John likes oranges and Mary apples." Dialog Processing "Speech Acts" (literal intended message) Social Role context s peech act selection "General" context sometimes needed Example 10-year old: "I want a juicy Hamburger!" Mother: "Not today, perhaps tomorrow…" General: "I want a juicy Hamburger." Aide: "Yes, sir!!" Prisoner 1: "I want a juicy Hamburger." Prisoner 2: "Wouldn't that be nice for once."Social Role Determines Interpretation: Social Role Determines Interpretation 10-year old: “I want a juicy Hamburger!” Mother: “Not today, perhaps tomorrow…” General: “I want a juicy Hamburger!” Aide: “Yes, sir!!” Prisoner 1: “I want a juicy Hamburger!” Prisoner 2: “Wouldn't that be nice for once!”Merit Cigarette Advertisement: Merit Cigarette Advertisement Merit Smashes Taste Barrier. -National Smoker Study ________________________________________ Majority of smokers confirm 'Enriched Flavor' cigarette matches taste of leading high tar brands. Why do we intepret barrier-smashing as good? [Metaphors, Metonomy, … other hard stuff] You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.