Compiling Combinatorial Prediction Games
Authors: Frederic Koriche
ICML 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our Results. Viewing feasible solutions as paths in a DAG is only one of many abstractions that have been proposed in the literature of circuit complexity for representing combinatorial spaces. In the related field of knowledge compilation (Darwiche & Marquis, 2002), various classes of Boolean circuits have been identified, each associated with a set of inference tasks which can be performed in polynomial time. These theoretical results naturally motivate the following question: can we compile a set of constraints representing a combinatorial space S into a compact and Boolean circuit for which both solution sampling and linear optimization are tractable? By viewing the compilation process as a pre-processing step , we may get for free efficient implementations of sampling and optimization oracles, provided that the size of the resulting circuit is not too large. The present study aims at solving combinatorial prediction games, by compiling decision sets into deterministic Decomposable Negation Normal Form (d DNNF) circuits (Darwiche, 2001). This class comes with generic compilers which take as input a SAT formula representing a decision set S, and return a d DNNF circuit C that encodes S (Darwiche, 2002; Lagniez & Marquis, 2017). Although the size of C may grow exponentially in the treewidth of the input formula, it is usually much smaller in practice; existing compilers are able to compress combinatorial spaces defined over thousands of variables and constraints. With these compilation tools in hand, our contributions are threefold: (i) we show that for d DNNF circuits, the sampling oracle in EH and the linear optimization oracle in FPL, run in linear time using a simple variant of the weight-pushing technique; (ii) for the SGD and CH strategies, we develop a Bregman projection-decomposition method that uses O(d2 ln(d T)) calls to the linear optimization oracle; (iii) we experimentally show on online configuration and planning tasks that EH and FPL are fast, but our variants of SGD and CH are more efficient to minimize the empirical regret. |
| Researcher Affiliation | Academia | 1CRIL, CNRS UMR 8188, Universit e d Artois, France. |
| Pseudocode | Yes | Algorithm 1 OSMD... Algorithm 2 PCG |
| Open Source Code | Yes | www.github.com/frederic-koriche/ccpg.git |
| Open Datasets | Yes | In order to evaluate the performance of the different online combinatorial optimization strategies examined in Section 3, we have considered 16 instances of the SAT Library,2 described in Table 3. Namely, the first six rows of the table are (car) configuration tasks, while the remaining rows are planning problems. ... 2www.cs.ubc.ca/ hoos/SATLIB/ |
| Dataset Splits | No | The paper describes an online learning setting with an adversarial environment and sequential feedback, rather than traditional train/validation/test dataset splits. There is no explicit mention of data splitting for training, validation, or testing. |
| Hardware Specification | Yes | The combinatorial prediction strategies were implemented in C++ and tested on a six-core Intel i7-5930K with 32 Gi B RAM. |
| Software Dependencies | No | The paper mentions 'implemented in C++' and uses the 'D4 compiler' but does not provide specific version numbers for any software components, libraries, or compilers. |
| Experiment Setup | Yes | For the FPL and EH algorithms, we used the step-size η reported in (Audibert et al., 2011) and (Hutter & Poland, 2005), respectively. Concerning the SGD+PCG and δ-CH+PCG algorithms, we used for η and γ the values determined by our theoretical analysis; the step-sizes {ηt} of PCG were computed from binary search as advocated by Garber & Meshi (2016) in their experiments, and the value of δ was fixed to 1/ln d in order to keep a quadratic runtime complexity for δ-CH+PCG. Finally, the horizon T was set to 103, and a timeout of one day was fixed for learning. |