Probabilistic Context-Free Grammar

AKA: PCFG, Stochastic Context-Free Grammar, SCFG.
Context:
- It can be a Lexicalized Probabilistic Context Free Grammar.
Example(s):
- …
Counter-Example(s):
- a Probabilistic Context-Sensitive Grammar.
See: Context Free Grammar, PCFG-based Parse Tree, CYK Algorithm, Hidden Markov Model, Regular Grammar, Formal Grammar.

References

(Wikipedia, 2016) ⇒ http://wikipedia.org/wiki/Stochastic_context-free_grammar Retrieved:2016-4-9.
- Grammar theory to model symbol strings originated from work in computational linguistics aiming to understand the structure of natural languages. Probabilistic context free grammars (PCFGs) have been applied in probabilistic modeling of RNA structures almost 40 years after they were introduced in computational linguistics.
  PCFGs extend context-free grammars similar to how hidden Markov models extend regular grammars. Each production is assigned a probability. The probability of a derivation (parse) is the product of the probabilities of the productions used in that derivation. These probabilities can be viewed as parameters of the model, and for large problems it is convenient to learn these parameters via machine learning. A probabilistic grammar's validity is constrained by context of its training dataset.
  PCFGs have application in areas as diverse as natural language processing to the study the structure of RNA molecules and design of programming languages. Designing efficient PCFGs has to weigh factors of scalability and generality. Issues such as grammar ambiguity must be resolved. The grammar design affects results accuracy. Grammar parsing algorithms have various time and memory requirements.

(Sakakibara, 2011) ⇒ Yasubumi Sakakibara. (2011). “Probabilistic Context-Free Grammars.” In: (Sammut & Webb, 2011) p.802

(Kakkonen, 2007) ⇒ Tuomo Kakkonen. (2007). “Framework and Resources for Natural Language Evaluation." Academic Dissertation. University of Joensuu.
- In probabilistic grammar formalisms a probability is associated with each rule. For example, probabilistic context-free grammars (PCFGs) can be characterized as CFPSGs that assign to each production the probability of its use. A PCFG (Booth & Thompson 1973) is a 4-tuple G = (N, Σ, P, S) like a CFPSG (Definition 3-9), except that each rule in P is associated with a probability in which [math]\displaystyle{ α }[/math] will be expanded to β.
- Definition 3-10. Productions in probabilistic context-free phrase structure grammar.
  - 1. P = {a ®b a Î N,b Î(ΣÈN)*}.
  - 2. There is a probability function p: P→[0,1] such that for each a ÎN,Σ p(a ®b a )= 1.

(Charniak, 1997) ⇒ Eugene Charniak. (1997). “Statistical Parsing with a Context-free Grammar and Word Statistics." AAAI / IAAI 2005, no . 598-603