Online Learning of K-CNF Boolean Functions
Abstract
This paper revisits the problem of learning a k-CNF Boolean function from examples, for fixed k, in the context of online learning under the logarithmic loss. We give a Bayesian interpretation to one of Valiant’s classic PAC learning algorithms, which we then build upon to derive three efficient, online, probabilistic, supervised learning algorithms for predicting the output of an unknown k-CNF Boolean function. We analyze the loss of our methods, and show that the cumulative log-loss can be upper bounded by a polynomial function of the size of each example.
Cite
Text
Veness et al. "Online Learning of K-CNF Boolean Functions." International Joint Conference on Artificial Intelligence, 2015.Markdown
[Veness et al. "Online Learning of K-CNF Boolean Functions." International Joint Conference on Artificial Intelligence, 2015.](https://mlanthology.org/ijcai/2015/veness2015ijcai-online/)BibTeX
@inproceedings{veness2015ijcai-online,
title = {{Online Learning of K-CNF Boolean Functions}},
author = {Veness, Joel and Hutter, Marcus and Orseau, Laurent and Bellemare, Marc G.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2015},
pages = {3865-3873},
url = {https://mlanthology.org/ijcai/2015/veness2015ijcai-online/}
}