Weighted context-free grammar

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 2 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.
  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.
  3. ↑ Johnson, Mark (2005). "log linear or Gibbs models" (PDF).
  4. ↑ Chi, Zhiyi (March 1999). "Statistical properties of probabilistic context-free grammars" (PDF). Computational Linguistics. 25 (1): 131–160.


This article is issued from Wikipedia - version of the 2/11/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.