A Generalization of Forward-Backward Algorithm
Abstract
Structured prediction has become very important in recent years. A simple but notable class of structured prediction is one for sequences, so-called sequential labeling. For sequential labeling, it is often required to take a summation over all the possible output sequences, when estimating the parameters of a probabilistic model for instance. We cannot make the direct calculation of such a summation from its definition in practice. Although the ordinary forward-backward algorithm provides an efficient way to do it, it is applicable to limited types of summations. In this paper, we propose a generalization of the forward-backward algorithm, by which we can calculate much broader types of summations than the existing forward-backward algorithms. We show that this generalization subsumes some existing calculations required in past studies, and we also discuss further possibilities of this generalization.
Cite
Text
Azuma and Matsumoto. "A Generalization of Forward-Backward Algorithm." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2009. doi:10.1007/978-3-642-04180-8_24Markdown
[Azuma and Matsumoto. "A Generalization of Forward-Backward Algorithm." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2009.](https://mlanthology.org/ecmlpkdd/2009/azuma2009ecmlpkdd-generalization/) doi:10.1007/978-3-642-04180-8_24BibTeX
@inproceedings{azuma2009ecmlpkdd-generalization,
title = {{A Generalization of Forward-Backward Algorithm}},
author = {Azuma, Ai and Matsumoto, Yuji},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2009},
pages = {99-114},
doi = {10.1007/978-3-642-04180-8_24},
url = {https://mlanthology.org/ecmlpkdd/2009/azuma2009ecmlpkdd-generalization/}
}