Editing Probabilistic context-free grammar (section)

==Weighted context-free grammar==
A '''weighted context-free grammar''' ('''WCFG''') is a more general category of [[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<ref name=PCFG_WCFG_same>{{Cite journal|doi=10.1162/coli.2007.33.4.477|title=Weighted and Probabilistic Context-Free Grammars Are Equally Expressive|year=2007|last1=Smith|first1=Noah A.|last2=Johnson|first2=Mark|journal=Computational Linguistics|volume=33|issue=4|pages=477|s2cid=1405777|url=http://www.cs.cmu.edu/%7Enasmith/papers/smith%2Bjohnson.cl07.pdf}}</ref> (or sum<ref name=sumWeightedCFG>{{Cite book|doi=10.1007/978-3-540-68155-7_31|title=Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems|series=Lecture Notes in Computer Science|year=2008|last1=Katsirelos|first1=George|last2=Narodytska|first2=Nina|last3=Walsh|first3=Toby|chapter=The Weighted CFG Constraint |isbn=978-3-540-68154-0|volume=5015|pages=323–327|chapter-url=https://books.google.com/books?id=zKlk6bA3u3oC&pg=PA323|citeseerx=10.1.1.150.1187|s2cid=9375313}}</ref> ) 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 PCFGs, where the weights are ([[logarithm]]s of <ref name=logLinear>{{Cite web|url=http://web.science.mq.edu.au/~mjohnson/papers/ESSLLI05-wcfgs.pdf#page=10 |title=log linear or Gibbs models|first=Mark |last=Johnson|year=2005}}</ref><ref>{{cite journal|title=Statistical properties of probabilistic context-free grammars|first=Zhiyi|last=Chi|journal=Computational Linguistics|volume=25|issue=1|date=March 1999|pages=131–160|url=http://acl.ldc.upenn.edu/J/J99/J99-1004.pdf|url-status=dead|archive-url=https://web.archive.org/web/20100821232432/http://acl.ldc.upenn.edu/J/J99/J99-1004.pdf|archive-date=2010-08-21}}
</ref>) [[probability|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 distribution]]s.<ref name=PCFG_WCFG_same/>