Inside-Outside and Forward-Backward Algorithms Are Just Backprop (tutorial paper)
Inside-Outside and Forward-Backward Algorithms Are Just Backprop (tutorial paper)
复制标题
DOI：
10.18653/v1/w16-5901
复制
发表时间：
2016-11
影响因子：
3.8
通讯作者：
Jason Eisner
中科院分区：
文献类型：
--
作者：
Jason Eisner
概率或加权语法意味着给定输入句子的可能解析的后验概率分布。人们经常需要通过计算各种语法规则、成分、转换或状态的预期计数（在未知解析中）来从这种分布中提取信息。这需要一个算法，如内部-外部或前向-后向，这是适合于语法形式主义。方便的是，每个这样的al-tax m可以通过自动区分一个“内部”算法来获得，该算法只计算证据（句子）的对数概率。这种机械程序产生正确和有效的代码。至于反向传播的任何其他实例，可以手动或通过软件进行。这篇教学论文仔细地阐述了这些算法的结构，并将其与传统和非传统的观点联系起来。
A probabilistic or weighted grammar implies a posterior probability distribution over possible parses of a given input sentence. One often needs to extract information from this distribution, by computing the expected counts (in the unknown parse) of various grammar rules, constituents, transitions, or states. This requires an algorithm such as inside-outside or forward-backward that is tailored to the grammar formalism. Conveniently, each such al-gorithm can be obtained by automatically differentiating an “inside” algorithm that merely computes the log-probability of the evidence (the sentence). This mechanical procedure produces correct and efficient code. As for any other instance of back-propagation, it can be carried out manually or by software. This pedagogical paper carefully spells out the construction and relates it to traditional and non-traditional views of these algorithms.