Mutual Information Gaining Algorithm and Its Relation to PAC-Learning Algorithm
Abstract
In this paper, the mutual information between a target concept and a hypothesis is used to measure the goodness of the hypothesis rather than the accuracy, and a notion of mutual information gaining (MI-gaining) algorithms is introduced. In particular, strong and weak MI-gaining algorithms are defined depending on the amount of information acquired, and their relation to strong and weak PAC-learning algorithms are investigated. It is shown that although a strong MI-gaining algorithm is equivalent to a strong PAC-learning algorithm, a weak MI-gaining algorithm does not necessarily imply a weak PAC-learning algorithm, and vice versa. Moreover, a general boosting scheme for weak MI-gaining algorithms is given. That is, any weak MI-gaining algorithm can be used to build a strong one. Since a strong MI-gaining algorithm is also a strong PAC-learning algorithm, the result can be viewed to give a sufficient condition for a class of algorithms to be boosted into strong learning algorithms.
Cite
Text
Takimoto et al. "Mutual Information Gaining Algorithm and Its Relation to PAC-Learning Algorithm." International Conference on Algorithmic Learning Theory, 1994. doi:10.1007/3-540-58520-6_89Markdown
[Takimoto et al. "Mutual Information Gaining Algorithm and Its Relation to PAC-Learning Algorithm." International Conference on Algorithmic Learning Theory, 1994.](https://mlanthology.org/alt/1994/takimoto1994alt-mutual/) doi:10.1007/3-540-58520-6_89BibTeX
@inproceedings{takimoto1994alt-mutual,
title = {{Mutual Information Gaining Algorithm and Its Relation to PAC-Learning Algorithm}},
author = {Takimoto, Eiji and Tajika, Ichiro and Maruoka, Akira},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1994},
pages = {547-559},
doi = {10.1007/3-540-58520-6_89},
url = {https://mlanthology.org/alt/1994/takimoto1994alt-mutual/}
}