Predicting Nearly as Well as the Best Pruning of a Planar Decision Graph
Abstract
We design efficient on-line algorithms that predict nearly as well as the best pruning of a planar decision graph. We assume that the graph has no cycles. As in the previous work on decision trees, we implicitly maintain one weight for each of the prunings (exponentially many). The method works for a large class of algorithms that update its weights multiplicatively. It can also be used to design algorithms that predict nearly as well as the best convex combination of prunings.
Cite
Text
Takimoto and Warmuth. "Predicting Nearly as Well as the Best Pruning of a Planar Decision Graph." International Conference on Algorithmic Learning Theory, 1999. doi:10.1007/3-540-46769-6_28Markdown
[Takimoto and Warmuth. "Predicting Nearly as Well as the Best Pruning of a Planar Decision Graph." International Conference on Algorithmic Learning Theory, 1999.](https://mlanthology.org/alt/1999/takimoto1999alt-predicting/) doi:10.1007/3-540-46769-6_28BibTeX
@inproceedings{takimoto1999alt-predicting,
title = {{Predicting Nearly as Well as the Best Pruning of a Planar Decision Graph}},
author = {Takimoto, Eiji and Warmuth, Manfred K.},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1999},
pages = {335-346},
doi = {10.1007/3-540-46769-6_28},
url = {https://mlanthology.org/alt/1999/takimoto1999alt-predicting/}
}