@inproceedings{8e1a79d1407c4124beb3d63e7d097794,
title = "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.",
author = "Joel Veness and Marcus Hutter and Laurent Orseau and Marc Bellemare",
year = "2015",
language = "English",
series = "IJCAI International Joint Conference on Artificial Intelligence",
publisher = "International Joint Conferences on Artificial Intelligence",
pages = "3865--3873",
editor = "Michael Wooldridge and Qiang Yang",
booktitle = "IJCAI 2015 - Proceedings of the 24th International Joint Conference on Artificial Intelligence",
note = "24th International Joint Conference on Artificial Intelligence, IJCAI 2015 ; Conference date: 25-07-2015 Through 31-07-2015",
}