Knowledge compilation (KC) is a research area which aims to preprocess information to improve the time required to solve highly-demanding computational tasks (NP and Beyond NP problems). Pioneered more than two decades ago, KC is nowadays a very active field, being at the intersection of several areas of AI and computer science. This includes knowledge representation, tractable reasoning, algorithms, complexity theory and databases. As a result, KC is now providing a meeting point for several active research areas, while offering a great potential for new synergies and advancements.
The tutorial will discuss some key dimensions relating to KC. This includes (1) the choice of a tractable language to compile into, which depends on its degree of tractability (operations it supports in polytime) and its succinctness (space efficiency of its representations); (2) the design and evaluation of knowledge compilers and supporting preprocessors; and (3) the applications of KC within AI, including product configuration, probabilistic inference, machine learning and explanations.
- Basic definitions
- Time/space trade-off in problem solving: notion of compilability
- Notion of knowledge compilation map
- DNNF, d-DNNF
- OBDD, SDD
- Knowledge Compilers
- Key ingredients of compilers (caching, heuristics, component analysis, etc.)
- Top-down compilers (recording the trace of a search engine)
- Bottom-up compilers (the apply transformation and searching for variables orders and trees)
- Preprocessing Techniques
- Knowledge compilation vs. other preprocessing techniques
- Reducing CNF formulae
- Properties of preprocessing techniques
- P-preprocessings: occurrence elimination, vivification, gate detection and replacement
- NP-preprocessings: backbone detection, definability
- Product configuration
- Probabilistic inference
- Machine learning
KC is of interest to a broad segment of the AI community (and also to some researchers outside AI). Prerequisite knowledge will be limited to basics of propositional logic and complexity theory.
The “Recent Advances in Knowledge Compilation” tutorial will be held during the 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence (IJCAI-ECAI-18), in Stockholm, Sweden. Tutorials will be held on July 13-15, 2018, immediately prior to the technical conference. Tutorial attendance is complimentary for all IJCAI-ECAI-18 conference registrants.