Online Learning of k-CNF Boolean Functions
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Special Track on Machine Learning. Pages 3865-3872.
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.
@inproceedings{ijcai2015p543,
title = {Online Learning of k-CNF Boolean Functions},
author = {Veness, Joel and Hutter, Marcus and Orseau, Laurent and Bellemare, Marc G.},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-15}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Qiang Yang and Michael Wooldridge},
pages = {3865--3872},
year = {2015},
month = {7},
note = {Special Track on Machine Learning},
url = {https://ijcai.org/proceedings/2015/543},
}
TY - CPAPER TI - Online Learning of k-CNF Boolean Functions AU - Veness, Joel AU - Hutter, Marcus AU - Orseau, Laurent AU - Bellemare, Marc G. T2 - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 PB - International Joint Conferences on Artificial Intelligence PY - 2015 SP - 3865 EP - 3872 UR - https://ijcai.org/proceedings/2015/543 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
