Stolcke:
An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
An efficient probabilistic context-free. Parsing algorithm that computes prefix probabilities презентация
Содержание
- 1. An efficient probabilistic context-free. Parsing algorithm that computes prefix probabilities
- 2. Overview What is this paper all about?
- 3. Context-Free Parsing The ball is heavy.
- 4. Context-Free Parsing Parser Grammar
- 5. Context-Free Parsing Parser Grammar
- 6. Context-Free Parsing What if there are multiple
- 7. Probabilistic Parsing Use probabilities to find the
- 8. Prefix Probabilities How likely is a partial
- 9. Efficiency The Earley algorithm (upon which
- 10. Parsing Algorithms How do we construct
- 11. Earley Parsing Overview Start with a root
- 12. Earley Parsing Overview Earley parsing uses a
- 13. Earley Parsing Example S → NP VP NP → ART N VP → V ADJ
- 14. Earley Parsing Example S → NP VP NP → ART N VP → V ADJ
- 15. Earley Parsing Example S → NP VP NP → ART N VP → V ADJ
- 16. Earley Parsing Example S → NP VP NP → ART N VP → V ADJ
- 17. Earley Parsing Example S → NP VP NP → ART N VP → V ADJ
- 18. Earley Parsing Example S → NP VP NP → ART N VP → V ADJ
- 19. Earley Parsing Example S → NP VP NP → ART N VP → V ADJ
- 20. Earley Parsing Example S → NP VP NP → ART N VP → V ADJ
- 21. Earley Parsing Example S → NP VP NP → ART N VP → V ADJ
- 22. Probabilistic Parsing How do we parse
- 23. Probabilistic Parsing Terminology Earley state: each step
- 24. etc. Probabilistic Parsing Can represent the parse
- 25. Probabilistic Parsing Every Earley path corresponds to
- 26. Probabilistic Parse Example Grammar Lexicon
- 27. Probabilistic Parse Example
- 28. Probabilistic Parse Example
- 29. Probabilistic Parse Example
- 30. Probabilistic Parse Example
- 31. Probabilistic Parse Example
- 32. Probabilistic Parse Example
- 33. Probabilistic Parse Example
- 34. Probabilistic Parse Example
- 35. Probabilistic Parse Example
- 36. Probabilistic Parse Example
- 37. Probabilistic Parse Example
- 38. Prefix Probabilities Current algorithm reports parse
- 39. Prefix Probabilities Solution: add a separate
- 40. Prefix Probability Example
- 41. Prefix Probability Example
- 42. Prefix Probability Example
- 43. Prefix Probability Example
- 44. Prefix Probability Example
- 45. Prefix Probability Example
- 46. Prefix Probability Example
- 47. Prefix Probability Example
- 48. Prefix Probability Example
- 49. Summary Use Earley chart parser for efficient
Overview What is this paper all about? Key ideas from the title: Context-Free Parsing Probabilistic Computes Prefix Probabilities Efficient
Слайд 2Overview
What is this paper all about?
Key ideas from the title:
Context-Free Parsing
Probabilistic
Computes
Prefix Probabilities
Efficient
Efficient
Слайд 6Context-Free Parsing
What if there are multiple legal parses?
Example: “Yair looked over
the paper.”
How does the word “over” function?
How does the word “over” function?
Yair looked over the paper
S
NP
VP
V
NP
Yair looked over the paper
S
NP
VP
V
NP
PP
P
N
N
or
Слайд 7Probabilistic Parsing
Use probabilities to find the most likely parse
Store typical probabilities
for words and rules
In this case:
In this case:
P = 0.99
P = 0.01
Yair looked over the paper
S
NP
VP
V
NP
Yair looked over the paper
S
NP
VP
V
NP
PP
P
N
N
or
Слайд 8Prefix Probabilities
How likely is a partial parse?
Yair looked over …
Yair
looked over …
S
NP
VP
V
NP
S
NP
VP
V
NP
PP
P
N
N
or
Слайд 9Efficiency
The Earley algorithm (upon which Stolcke builds) is one of the
most efficient known parsing algorithms
Probabilities allow intelligent pruning of the developing parse tree(s)
Probabilities allow intelligent pruning of the developing parse tree(s)
Слайд 10Parsing Algorithms
How do we construct a parse tree?
Work from grammar to
sentence (top-down)
Work from sentence to grammar (bottom-up)
Work from both ends at once (Earley)
Predictably, Earley works best
Work from sentence to grammar (bottom-up)
Work from both ends at once (Earley)
Predictably, Earley works best
Слайд 11Earley Parsing Overview
Start with a root constituent, e.g. sentence
Until the sentence
is complete, repeatedly
Predict: expand constituents as specified in the grammar
Scan: match constituents with words in the input
Complete: propagate constituent completions up to their parents
Prediction is top-down, while scanning and completion are bottom-up
Predict: expand constituents as specified in the grammar
Scan: match constituents with words in the input
Complete: propagate constituent completions up to their parents
Prediction is top-down, while scanning and completion are bottom-up
Слайд 12Earley Parsing Overview
Earley parsing uses a chart rather than a tree
to develop the parse
Constituents are stored independently, indexed by word positions in the sentence
Why do this?
Eliminate recalculation when tree branches are abandoned and later rebuilt
Concisely represent multiple parses
Constituents are stored independently, indexed by word positions in the sentence
Why do this?
Eliminate recalculation when tree branches are abandoned and later rebuilt
Concisely represent multiple parses
Слайд 22Probabilistic Parsing
How do we parse probabilistically?
Assign probabilities to grammar rules and
words in lexicon
Grammar and lexicon “randomly” generate all possible sentences in the language
P(parse tree) = P(sentence generation)
Grammar and lexicon “randomly” generate all possible sentences in the language
P(parse tree) = P(sentence generation)
Слайд 23Probabilistic Parsing
Terminology
Earley state: each step of the processing that a constituent
undergoes. Examples:
Starting sentence
Half-finished sentence
Complete sentence
Half-finished noun phrase
etc.
Earley path: a sequence of linked states
Example: the complete parse just described
Starting sentence
Half-finished sentence
Complete sentence
Half-finished noun phrase
etc.
Earley path: a sequence of linked states
Example: the complete parse just described
Слайд 24etc.
Probabilistic Parsing
Can represent the parse as a Markov chain:
Markov assumption (state
probability is independent of path) applies, due to CFG
S ►
NP VP
Begin
S
Begin
NP ►
ART N Begin
NP ►
PN Begin
NP Half Done
NP Done
S Half Done
(path abandoned)
Predict S
Predict NP
Scan “the”
Scan “ball”
Complete NP
Слайд 25Probabilistic Parsing
Every Earley path corresponds to a parse tree
P(tree) = P(path)
Assign
a probability to each state transition
Prediction: probability of grammar rule
Scanning: probability of word in lexicon
Completion: accumulated (“inner”) probability of the finished constituent
P(path) = product of P(transition)s
Prediction: probability of grammar rule
Scanning: probability of word in lexicon
Completion: accumulated (“inner”) probability of the finished constituent
P(path) = product of P(transition)s
Слайд 38Prefix Probabilities
Current algorithm reports parse tree probability when the sentence is
completed
What if we don’t have a full sentence?
Probability is tracked by constituent (“inner”), rather than by path (“forward”)
What if we don’t have a full sentence?
Probability is tracked by constituent (“inner”), rather than by path (“forward”)
Слайд 39Prefix Probabilities
Solution: add a separate path probability
Same as before, but propagate
down on prediction step
This is the missing link to chain the path probabilities together
This is the missing link to chain the path probabilities together
Слайд 49Summary
Use Earley chart parser for efficient parsing, even with ambiguous or
complex sentences
Use probabilities to choose among multiple possible parse trees
Track constituent probability for complete sentences
Also track path probability for incomplete sentences
Use probabilities to choose among multiple possible parse trees
Track constituent probability for complete sentences
Also track path probability for incomplete sentences
