Knowledge compilation

Knowledge compilation is a family of approaches for addressing the intractability of a number of artificial intelligence problems.

A propositional model is compiled in an off-line phase in order to support some queries in polytime. Many ways of compiling a propositional models exist.[1]

Different compiled representations have different properties. The three main properties are:

  • The compactness of the representation
  • The queries that are supported in polytime
  • The transformations of the representations that can be performed in polytime

Classes of representations

Some examples of diagram classes include OBDDs, FBDDs, and non-deterministic OBDDs, as well as MDD.

Some examples of formula classes include DNF and CNF.

Examples of circuit classes include NNF, DNNF, d-DNNF, and SDD.

gollark: I mean, in certain regions of exotic geometry there are definitionally holes in place, but they're irrelevant to the defenses.
gollark: You're clearly firing into a decoy.
gollark: Also impossible ones.
gollark: Also possible ones.
gollark: GTech™ sites are shielded in all extant and hypothetical realities.

References
  1. Adnan Darwiche, Pierre Marquis, "A Knowledge Compilation Map", Journal of Artificial Intelligence Research 17 (2002) 229-264


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.