Natural Language Understanding :1 Natural Language Understanding What is understanding ? Inference about speaker’s goals and assumptions and context of interaction NLU program requires Large amount of knowledge Reason effectively with knowledge


Natural Language Understanding(Contd..) :2 Natural Language Understanding(Contd..) Why NLU is AI ? Intelligent behaviour Perception Communication through sight, hearing, touch smell, taste and generating words. Ability to communicate effectively is an intelligent behaviour


Natural Language Understanding(Contd..) :3 Natural Language Understanding(Contd..) NLU is used in Question answering Database queries Automatic translation system Story understanding


NLU problem is Complex :4 NLU problem is Complex “Shall I compare thee to a summer’s day thou art more lovely and more temperateRough winds do share the darling buds of may, and summer’s lease what all too short a date’ Shakespeare


NLU problem is Complex(Contd..) :5 NLU problem is Complex(Contd..) Dictionary meaning of words is not sufficient inference requires - Metaphor -Application of name or description to an object for which it is not directly applicable Eg. A camel is a ship of desert Variety is a spice of life. - Analogies – Eg “As clear as crystal” - Background knowledge


Levels of Analysis for Natural language understanding (NLU) :6 Levels of Analysis for Natural language understanding (NLU) Prosody(system of versification) : - Deals with the rhythm of language - Importance in poetry or religious chants. Phonology(Science of sound in speech language : - Phoneme is the smallest unit of sound - Relates sounds to words we recognize - Importance in speech recognition and generation Morphology : - Knowledge relating to word constructions from basic units. - Morpheme is the smallest unit of meaning - Construction of friendly from friend.


Levels of Analysis for NLU (Contd..) :7 Levels of Analysis for NLU (Contd..) Syntactic : - Knowledge related to forming grammatically correct sentences. Semantic : - Knowledge concerned with meaning of words and phrases and sentences. Pragmatic : - Relates to use of sentences in different contexts. Ex : “Do you know what time it is ?“ “ Yes” is an inappropriate answer.


Levels of Analysis for NLU (Contd..) :8 Levels of Analysis for NLU (Contd..) World Knowledge : - Knowledge of the physical world - role of goals and intentions in communication. - Background knowledge - essential to understand full meaning of a text.


Levels of Analysis for NLU (Contd..) :9 Levels of Analysis for NLU (Contd..) Natural Language Understanding Text or written language Speech understanding Understanding - More complex - Often corrupted by noise


Stages of NLU :10 Stages of NLU INPUT : MOTHER PATTED CHILD PARSING PARSE TREE : SENTENCE NOUN PHARSE VERB PHRASE NOUN VERB NOUN PHARSE MOTHER NOUN PATTED CHILD SEMANTIC INTERPRETATION Next


Stages of NLU(Contd..) :11 Stages of NLU(Contd..) SEMANTIC INTERPRETATION INTERNAL REPRESENTATION PERSON : MOTHER PERSON : CHILD AGENT PAT OBJECT INSTRUMENT HAND CONTEST/ WORLD KNOWLEDGE INTERPRETATION Next


Stages of NLU (Contd..) :12 Stages of NLU (Contd..) CONTEXT/WORLD KNOWLEDGE INTERPRETATION EXPANDED REPRESENTATION : EXPERIENCER LOVE OBJECT PERSON : MOTHER PERSON : CHILD AGENT PAT OBJECT To INSTRUMENT HAND Question answerer data base query LOCATION HOME LOCATION handler, translator etc.


Stages of NLU :13 Stages of NLU Parsing : - Verifies syntactic correctness - Creates parse tree - Employs knowledge of language syntax, morphology Semantic Interpretation : - Represents meaning of text - Frames, or other logic-based representations are used - Performing semantic consistency checks. World Knowledge Interpretation : - Produces expanded representation - uses necessary world knowledge for complete understanding.


Parsing Techniques :14 Parsing Techniques Grammars and Languages V = { A,B,..,Z, a,b,..z } String is constructed from concatenating elements of V L = { S/ S is a string } A language is a set of strings of finite length Well formed sentences are constructed using set of rules called grammar L(G) – Denotes the Language Generated by grammar


Parsing Techniques (Contd..) :15 Parsing Techniques (Contd..) G = (Vn, Vt, s, P) Vn - Set of non terminal symbols Vt - Set of terminal symbols s - Starting symbol P – Finite set of production rules or rewrite rules V = Vt U Vn U e, e – the empty string Vt ? Vn = ?


Parsing Techniques(Contd..) :16 Parsing Techniques(Contd..) Vt – the terminals are symbols which cannot be decomposed further - Adjectives, nouns, verbs etc. Vn - the non terminals that can be decomposed further - noun phrase, verb phrase A general production rule P has the form x y z ? x w z x,y, and z belongs to V i.e., y should be rewritten as w in the context of x to z ; x and z can be even empty


Example of a Simple grammar :17 Example of a Simple grammar QN = { S, NP, N, VP, V, ART } QT = { boy, ate, tpffey, frog, flew, the, a } Rewrite rules P : S ? NP VP NP ? ART N VP ? V NP N ? boy ? frog ? toffey ? for alternative choices V ? ate ? Flew ART ? the ? a


Example of a Simple grammar (Contd..) :18 Example of a Simple grammar (Contd..) S initial symbol (for sentence) NP noun phrase, VP verb phase N noun, V verb, ART article Example sentences from above grammar G - The boy ate a toffey - The frog flew a boy - A boy ate the frog To generate a sentence, Start with S Apply rules from P sequentially till no non-terminal appears


Example of a Simple Grammar (Contd..) :19 Example of a Simple Grammar (Contd..) The boy ate a toffey S ? NP VP ? ART N VP ? the N VP ? the boy VP ? the boy V NP ? the boy ate NP ? the boy ate ART N ? the boy ate a N ? the boy ate a toffey


Example of a Simple grammar (Contd..) :20 Example of a Simple grammar (Contd..) A grammar generates grammatically correct sentences. No guarantee for meaningful sentences Natural language can not be formally characterized by simple grammar (As above) Constrained / formal programming languages have been classified by grammar


Chomsky Hierarchy of Grammars :21 Chomsky Hierarchy of Grammars Type 0 grammar Most general xyz ? xwz y can not be e High power machine to recognize sentences is required


Context-Sensitive Grammar :22 Context-Sensitive Grammar Type - 1 grammar Also called context-sensitive grammar Restrictions Length of string on R.H.S. in a rule >= length of string on L.H.S. in rewrite rule x y z ? x w z, y must be a non-terminal w ? e


Context Sensitive Grammar(Contd..) :23 Context Sensitive Grammar(Contd..) Typical grammar rules S ? aS S ? aAB Capitals - non-terminals AB ? BA Small letters - terminals aA ? ab aA ? aa


Context-Free Grammar :24 Context-Free Grammar Type 2 grammar Also called context-free grammar Typical form A ? xyz A – single non terminal Production Rules S ? aS S ? a Sb S ? aB S ? a AB A ? a B ? a


Regular grammar :25 Regular grammar Type 3 grammar Most restrictive Also called finite state or regular grammar Production Rules A ? aB A ? a


Types of Grammars (Contd..) :26 Types of Grammars (Contd..) Regular and context-free languages are most widely studied and understood. Context-free languages are basis for formal programming languages. Type 0 and type 1 are not established More extensive grammar includes Prepositional Phrases PP Adjectives ADJ Determiners DET Adverbs ADV Auxiliary verbs AUX


Additional rewrite rules :27 Additional rewrite rules PP ? PREP NP (in the house) VP ? V ADV (work hard) VP ? V PP (locked in the house) VP ? V NP PP (locked the dog in the house) VP ? AUX V NP (must do the job) DET ? ART ADJ (Determiners-either,next, DET ? ART other, both etc.) NP ? DET N The mean boy locked the dog in the house The cute girl worked to make some extra money


Basic Parsing Techniques :28 Basic Parsing Techniques Parsing - Determining the syntactical structure of a sentence. Inverse of sentence generation process. Parser : Uses lexicon to determine the meaning of a word. Input Parser Output represen- string tation structure Lexicon Parsing an input to create an output


The Lexicon :29 The Lexicon Lexicon : A dictionary of words containing syntactic, semantic and pragmatic information. The entries of a lexicon may not be the same.


The Lexicon (Contd..) :30 The Lexicon (Contd..) Example Lexicon : Word Type Features ------------------------------------------------------------------------------- a Determiner { 3 s } 3 s means third person singular be Verb Trans : Intransitive boy Noun { 3 s } can Noun { 1s, 2s, 3s, 1p, 2p, 3p } Verb Trans : Intransitive orange Adjective { 3 s } Noun


Top-Down Versus Bottom-Up Parsing :31 Top-Down Versus Bottom-Up Parsing A Top-down parser begins with a sentence Terminal symbols are replaced by input sentence words. Example “ “ Kathy jumped the horse “ S ? NP VP ? Noun VP ? Kathy VP ? Kathy V VP ? Kathy jumped NP ? Kathy jumped article N ? Kathy jumped the N ? Kathy jumped the horse


Top-Down VersusBottom-Up Parsing (Contd..) :32 Top-Down VersusBottom-Up Parsing (Contd..) A Bottom-up parser is data driven because it begins with the actual words in sentence Kathy jumped the horse ? name jumped the horse ? name V the horse ? name V art horse ? name V art N ? NP V art N ? NP V NP ? NP VP ? S


Transition Networks :33 Transition Networks Used to represent natural language structures Consists of a number of nodes and labeled arcs. Nodes represent different states in a sentence Arcs represent rules or test conditions to make the transition from state to state


Transition Networks (Contd..) :34 Transition Networks (Contd..) Determiner noun verb N1 N2 N3 N4 “ The Child Runs “ Adjective Adjective Determiner N1 Pronoun N2 Noun N3 Proper Noun Jump


Transition Networks (Contd..) :35 Transition Networks (Contd..) To move from N1 to N2 it is necessary to find an adjective, a pronoun, a determiner, a proper noun or none of these by jumping directly to N2. Examples Big white fluffy clouds Our bright children A large beautiful white flower Large green leaves


Augmented Transition Networks :36 Augmented Transition Networks Uses Recursive Transition Networks (RTN) RTN – are more powerful than simple networks An RTN is a transition network which permits arc labels to refer to other networks and they in turn may refer back to the referring network.


Recursive Transition Network :37 Recursive Transition Network Example : The big tree shades the old house by the stream (the big tree) (shades) (the old house) NP V NP PP S : S1 S2 S5 S6 POP Aux NP V POP S3 S4 (a) Top Level RTN


Augmented Transition Networks (Contd..) :38 Augmented Transition Networks (Contd..) The big tree DET ADJ PP NP : N1 N2 N N4 POP NPR N3 POP (b) Noun Phrase sub-network


Augmented Transition Networks (Contd..) :39 Augmented Transition Networks (Contd..) PREP NP PP P1 P2 P3 POP by the stream (c) Prepositional Phrase Network Note : POP is used to signal the successful completion of the sub network.


Augmented Transition Networks (Contd..) :40 Augmented Transition Networks (Contd..) Include more semantic information into structure RTN with additional features is ATN. Additional sentence features include Number S/P Mood Declarative or Interrogative Tense Present, Past Additional tests performed for semantic features. Temporary storage registers are used in ATN. A set of registers for NP network A set of registrar for PP network Register contents are cleared when failure occurs After successful parsing, contents of registers are combined for final sentence structure


Augmented Transition Networks (Contd..) :41 Augmented Transition Networks (Contd..) Word Definition Word Definition a Part-of-speech: article Part-of-speech: verb Root: a Root: like Number: Singular Like Number: Plural men Part-of-speech: noun Likes Part-of-speech: verb Root: man Root: like Number: Plural Number: Singular Dog Part-of-speech: noun Root : dog Number: Singular Dictionary of Entries for a Simple ATN