1 Probabilistic Context-Free Grammars.pptx

This presentation describes about probabilistic context free grammars

1. UNIT III Lavanya B CSE(AI & ML)

2. probabilistic context free grammars A Probabilistic Context-Free Grammar (PCFG) extends Context-Free Grammar (CFG) by assigning probabilities to each production rule, allowing it to model the likelihood of different sentence structures. This probabilistic element is crucial for handling ambiguity in natural language processing, as it enables the selection of the most probable parse tree for a given sentence.  Tuesday, August 12, 2025 © BVRIT 2

3. 1. Context-Free Grammar (CFG): Tuesday, August 12, 2025 © BVRIT 3 A CFG defines the grammatical rules of a language using symbols (terminals and non-terminals) and production rules that specify how non-terminals can be expanded into other symbols.  For example, a rule like "S -> NP VP" (Sentence -> Noun Phrase Verb Phrase) is a CFG rule. 

4. 2. Probabilistic Extension:  Tuesday, August 12, 2025 © BVRIT 4 A PCFG adds probabilities to each CFG rule, indicating how likely that rule is to be used in generating a sentence.  For instance, a rule "S -> NP VP" might have a probability of 0.7, while another rule like "S -> NP VP PP" might have a probability of 0.3, 

5. 3. PCFG in NLP:  Tuesday, August 12, 2025 BVRIT 5 PCFGs are used in NLP for tasks like parsing, where the goal is to determine the grammatical structure of a sentence.  Because natural language is often ambiguous (a sentence can have multiple possible grammatical structures), CFGs alone are not sufficient.  PCFGs overcome this by assigning probabilities to different parse trees, allowing the most likely parse to be selected. 

6. Tuesday, August 12, 2025 © BVRIT 6 A CFG is defined by 4 components : N → Non-terminal symbols (e.g., S , NP , VP , etc.) Σ → Terminal symbols (actual words, e.g., book , flights ) P → Production rules (e.g., S → NP VP ) S → Start symbol (often S for sentence) A PCFG adds a 5th component : D → A function that assigns a probability to each rule in P . Formally: G=(N,Σ,P,S,D) G = (N, Σ, P, S, D)

7. Example rule in PCFG format: S → NP VP [0.80] S → Aux NP VP [0.15] S → VP [0.05] Tuesday, August 12, 2025 © BVRIT 7

8. 2. Why add probabilities? Normal CFGs allow multiple possible parse trees for sentence. PCFGs let us rank parses by likelihood . This is useful for: Disambiguation (choosing the most likely meaning) Language modeling (estimating sentence probabilities) Speech recognition, spelling correction, etc. Tuesday, August 12, 2025 © BVRIT 8

9. 3. How to get rule probabilities? Definition: Rule probability = probability of choosing a specific expansion given a particular non-terminal. Tuesday, August 12, 2025 © BVRIT 9

10. Tuesday, August 12, 2025 © BVRIT 10 Example: If in a treebank we see: NP → Pronoun happens 40 times NP → Noun happens 60 times Total NP expansions = 100

11. 2. Probability of a parse tree This is about the probability of an entire derivation (tree) for a sentence. Definition: Multiply the probabilities of all rules used in that tree . Tuesday, August 12, 2025 © BVRIT 11

12. Example: Tuesday, August 12, 2025 © BVRIT 12 I f your parse uses: S → NP VP [0.8] NP → Pronoun [0.4] VP → Verb NP [0.5] Pronoun → you [0.6] Verb → see [0.3] NP → Noun [0.6] Noun → dog [0.5] Then:

13. 5. Choosing the best parse Tuesday, August 12, 2025 © BVRIT 13

14. 6. Probability of a sentence Tuesday, August 12, 2025 © BVRIT 14

15. Probabilistic CYK Parsing of PCFGs Probabilistic CYK (Cocke-Younger- Kasami ) parsing of Probabilistic Context-Free Grammars (PCFGs) in Natural Language Processing (NLP) is a dynamic programming algorithm used to find the most probable parse tree for a given sentence. Tuesday, August 12, 2025 © BVRIT 15

16. Probabilistic Context-Free Grammars (PCFGs): These are an extension of traditional Context-Free Grammars (CFGs) where each production rule is assigned a probability. This allows the grammar to model the likelihood of different syntactic structures. CYK Algorithm: The classic CYK algorithm is a dynamic programming algorithm for parsing CFGs in Chomsky Normal Form (CNF). It builds a table representing possible constituents spanning contiguous segments of the input sentence. Tuesday, August 12, 2025 © BVRIT 16

17. Probabilistic CYK Extension: The probabilistic CYK algorithm extends the classic CYK by incorporating probabilities into the table entries. Instead of simply storing whether a constituent can span a segment, it stores the maximum probability of a parse tree for that segment, along with back-pointers to reconstruct the tree. How it Works: Grammar in CNF: The PCFG must be converted to Chomsky Normal Form, where all production rules are either of the form A -> BC (two non-terminals) or A -> a (a terminal). Tuesday, August 12, 2025 © BVRIT 17

18. Goal of Probabilistic CYK Tuesday, August 12, 2025 © BVRIT 18 That is: Given a sentence S and a PCFG, Find the single parse tree with the highest probability. CYK is bottom-up and uses dynamic programming to do this efficiently.

19. Requirements CYK works only if the grammar is in Chomsky Normal Form (CNF) : Every rule is either: Tuesday, August 12, 2025 © BVRIT 19 No ε-productions (no empty string rules). Why? → CNF structure makes it easy to split the problem into two smaller subproblems (binary splitting).

20. Data Structure We use a 3D array : Tuesday, August 12, 2025 © BVRIT 20

21. Base Case (length 1 spans) Tuesday, August 12, 2025 © BVRIT 21

22. Recursive Case (length > 1 spans) Tuesday, August 12, 2025 © BVRIT 22

23. Output Tuesday, August 12, 2025 © BVRIT 23

24. Example S → NP VP [0.9] NP → Det N [0.5] VP → V NP [0.6] Det → the [0.8] N → cat [0.7] V → chased [0.9] Tuesday, August 12, 2025 © BVRIT 24

25. Tuesday, August 12, 2025 © NIT Warangal 25 Thank You