mirror of https://github.com/2martens/uni.git
155 lines
6.4 KiB
Plaintext
155 lines
6.4 KiB
Plaintext
Methods for understanding natural language
|
|
=========================================
|
|
|
|
title slide: present title and lead to motivation (Why is it interesting?)
|
|
-----------
|
|
|
|
Motivation
|
|
----------
|
|
|
|
- explain Mass Effect 1 screenshot (short and concise without story details)
|
|
-1- it's a dialogue with predefined options
|
|
- click
|
|
-1- what about a game where I can freely decide what I say?
|
|
-1- speech recognition would be necessary
|
|
- but there are also other kinds of dialogue in computer games
|
|
-2- Shroud of the Avatar uses a dialogue box (similar to chat box) to enter your sentences
|
|
-2- the NPCs react appropriately
|
|
-2- behind the hood they just use keyword searching
|
|
- click
|
|
- if this is developed further, you come pretty quickly to the methods used to understand natural language
|
|
- but there is an imminent problem: Ambiguity (click)
|
|
- Disambiguation is used to address ambiguity
|
|
|
|
Outline
|
|
-------
|
|
|
|
- start with some basic definitions
|
|
- then Syntactic Parsing which is the key aspect of this presentation
|
|
- Semantic Analysis is next but only the key points are presented
|
|
- Conclusion (refers to critical discussion in paper)
|
|
|
|
Definitions
|
|
-----------
|
|
|
|
syntax: describes sentence structure (for example subject-predicate-object order) and kind (declarative, question, order)
|
|
|
|
grammar: specifies valid sentences
|
|
|
|
semantics: meaning of the written words
|
|
|
|
pragmatics: meaning of words in a given context/actual meaning
|
|
|
|
- explain ambiguity on semantic level with the word "order"
|
|
- as you can see this ambiguity can easily be resolved if the context is given
|
|
- but without the context, the word "order" has different possible meanings
|
|
- which one to choose?
|
|
- that's a question that belongs to the semantic analysis
|
|
|
|
Syntactic Parsing (Lexicon)
|
|
---------------------------
|
|
|
|
- first we come to syntactic parsing
|
|
- a lexicon is very important there
|
|
- it defines the set of allowed words divided into categories
|
|
- open and closed categories
|
|
-1- open: new words are added constantly, complete list not feasible
|
|
-1- closed: change over course of centuries, complete list possible
|
|
|
|
- each word is attached a probability
|
|
- all probabilities in one category sum up to 1
|
|
|
|
Syntactic Parsing (Grammar)
|
|
---------------------------
|
|
|
|
- the grammar is somewhat the brother of the lexicon
|
|
- defines how the allowed words can be brought into a sentence structure
|
|
- contains multiple rules
|
|
- base for all kinds of parsing as every algorithm must be able to determine if the input is valid
|
|
|
|
- in our case the grammar is a "Probabilistic context free grammar"
|
|
-1- it has probabilities for each rule
|
|
-1- the probabilities of all rules starting with the same non-terminal sum up to 1
|
|
|
|
- click
|
|
|
|
- this is example from paper
|
|
- it's a very simplistic grammar that does only allow the simplest forms of sentences
|
|
- Article, Noun, Verb, Adjective stand for a word from these categories in lexicon
|
|
- as you can see the probabilities of the VP and Adjs rules sum up to 1 each
|
|
- these probabilities are used to calculate the total probability of a parse tree in the (click) Cocke-Younger-Kasami or short CYK algorithm
|
|
|
|
Syntactic Parsing (CYK)
|
|
-----------------------
|
|
|
|
- it is named after the inventors John Cocke, Daniel H. Younger and Tadeo Kasami
|
|
- Cocke was awarded the ACM Turing Award and National Medal of Science of the United States
|
|
- Kasami was the first to publish the ideas of the CYK algorithm
|
|
|
|
- it's a dynamic programming parsing algorithm
|
|
-1- in short: it utilizes the results from earlier iterations
|
|
- it's got the drawback that it only works with grammars in CNF
|
|
-2- in theory no problem as every CFG can be converted to CNF without loss in expressiveness
|
|
-2- in practice it poses non-trivial problems as the resulting trees do not fit to original grammar
|
|
-2- solution to this is a modification of the CYK algorithm to handle unit productions (A->C->B) directly (Jurafsky Chapter 13 Section 4 Page 475)
|
|
|
|
- probabilities are used for disambiguation (if two things are possible, the one with higher probability does make probably more sense and comes closer to the intended meaning)
|
|
- probabilities are gained from a treebank (like Penn Treebank)
|
|
|
|
- CYK is the best algorithm for general CFGs
|
|
|
|
- click
|
|
|
|
- here's an example for the table used by CYK to determine parse trees (excerpt from table in paper)
|
|
- begins with length 1 and looks at every word (here it's the sentence "The tree is very high")
|
|
- next it looks at length 2, 3, 4 and finally 5
|
|
|
|
- in the end there should be at least one entry in the table with S in column X, 1 in start and 5 in length.
|
|
- If there is no such entry and the algorithm was performed correctly, the input is not valid.
|
|
- if there is more than one such entry, there are multiple parse trees and therefore we have ambiguity
|
|
- the probability is then used to decide which one is used to determine the parse tree (for example with the help of backpointers)
|
|
|
|
- this parse tree is then given to (click) the Semantic Analysis
|
|
|
|
Semantic Analysis
|
|
-----------------
|
|
|
|
- there are multiple approaches for Semantic Analysis, the syntax-driven is presented
|
|
- it requires a syntax representation as input
|
|
-1- can be parse trees
|
|
-1- but also dependency structures or other things
|
|
|
|
- the analysis utilizes First-Order Logic
|
|
-2- connectives: and, or, implies
|
|
-2- quantifiers: for all, exists
|
|
-2- predicates, functions, variables
|
|
|
|
- and lambda notation (example can be seen in paper)
|
|
|
|
- the grammar is augmented with semantic attachments (click)
|
|
- these are now combined starting with S and going down
|
|
- in the example of the paper, the final meaning representation is this (showing on representation on slide)
|
|
- one can also see here the elements of the logic (at least partially)
|
|
- the whole process (step-by-step) can be seen in the paper
|
|
|
|
- the meaning representation can then be computationally used to react to the input
|
|
|
|
- click
|
|
|
|
Conclusion
|
|
----------
|
|
|
|
- even though there are means to minimize ambiguity like probabilities, it is by far not possible to use the full grammar of a natural language (with no hint of the context, there are meany parses that make syntactically sense but not necessarily context-wise)
|
|
- there is simply to much ambiguity and the known methods of disambiguation don't solve the problem completely
|
|
- a restriction of the context and allowed words is therefore necessary to be able to parse and/or compute the meaning
|
|
|
|
- if we manage to find a way to tell the computer the context without hardcoding it by limiting the input, the problem could be solved altogether
|
|
- cognitive inspired methods could be the key here
|
|
|
|
- click
|
|
|
|
End
|
|
---
|
|
|
|
Thank you for your attention
|