Weighted context-free grammar

From Infogalactic: the planetary knowledge core
Jump to: navigation, search

A weighted context-free grammar (WCFG) is a context-free grammar where each production has a numeric weight associated with it. The weight of a specific parse tree in a WCFG is the product[1] (or sum[2] ) of all rule weights in the tree. Each rule weight is included as often as the rule is used in the tree. A special case of WCFGs are probabilistic context-free grammars (PCFGs), where the weights are (logarithms of [3][4]) probabilities.

An extended version of the CYK algorithm can be used to find the "lightest" (least-weight) derivation of a string given some WCFG.

When the tree weight is the product of the rule weights, WCFGs and PCFGs can express the same set of probability distributions.[1]

References

  1. 1.0 1.1 Smith, Noah A.; Johnson, Mark (2007). "Weighted and Probabilistic Context-Free Grammars Are Equally Expressive". Computational Linguistics. 33 (4): 477. doi:10.1162/coli.2007.33.4.477.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
  2. Katsirelos, George; Narodytska, Nina; Walsh, Toby (2008). "The Weighted Cfg Constraint". Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Lecture Notes in Computer Science. 5015. p. 323. doi:10.1007/978-3-540-68155-7_31. ISBN 978-3-540-68154-0.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
  3. Johnson, Mark (2005). "log linear or Gibbs models" (PDF).<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
  4. Chi, Zhiyi (March 1999). "Statistical properties of probabilistic context-free grammars" (PDF). Computational Linguistics. 25 (1): 131–160.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>