Online Learning of k-CNF Boolean Functions
Authors: Joel Veness, Marcus Hutter, Laurent Orseau, Marc Bellemare
IJCAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Collaboration | 1Google Deep Mind, 2Australian National University {veness,lorseau,bellemare}@google.com, marcus.hutter@anu.edu.au |
| Pseudocode | Yes | Algorithm 1 ζd(x1:n; a1:n); Algorithm 2 πd(x1:n; a1:n); Algorithm 3 ωd(x1:n; a1:n) |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code or a link to a code repository. |
| Open Datasets | No | The paper is theoretical and discusses learning from 'examples' without specifying any public datasets or providing access information for any data used. |
| Dataset Splits | No | The paper is theoretical and does not describe any specific training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not mention any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and analysis. It does not describe any specific experimental setup details such as hyperparameters or training configurations. |