Inference In Alchemy

All inference algorithms in Alchemy are implemented as subclasses of the abstract class Inference (see dir src/infer/). Currently, the class hierarchy (see diagram below) contains two large classes of inference algorithms: SAT-solvers and MCMC algorithms. These two classes hold the parameters which are common among all flavors of SAT-solvers and MCMC algorithms, respectively. SAT and MCMC are also implemented as abstract classes as they should only serve as superclasses for various implementations.

All inference algorithms are based on a VariableState (see dir /src/logic/) which encodes the state of the propositional variables and clauses. There are two different methods to build the state: lazily and eagerly. An eager state builds a Markov random field based on the queries, the MLN and the domain of constants. Inference is then run on the clauses and variables in the MRF. A lazy state makes the assumption of all variables being false in the beginning and activates variables and clauses as needed by the inference algorithm. In sparse domains, this can lead to large savings in memory usage. The laziness or eagerness of a state is encapsulated in the class

VariableState and is set with the constructor.

In addition, all inference algorithms can be instantiated with a seed for the random number generator, if needed. If the algorithm contains no randomness, this is ignored. The ability to set the seed is useful when debugging and comparing different parameter settings of an algorithm.

Implementing a New Inference Algorithm

Any new inference algorithm in Alchemy must fit into the existing class hierarchy (i.e. it must be a subclass of Inference). Therefore, it must implement the methods init() and infer(), although it could be that no initialization is required (see, for example, UnitPropagation). The constructor of the new class should call the constructor of Inference so that the state and seed are initialized.

Every inference algorithm is called in the same manner in infer/infer.cpp. A VariableState is initialized and the pointer inference is set to the inference algorithm as specified on the command line. If a new inference algorithm is added, this should be extended (along with the command line options) to accomodate the new algorithm, i.e.:

inference = new NewAlgorithm(state, seed, params);

where params is a struct to hold the parameters specific to the new algorithm. Finally, init() and infer() are called which perform the inference and the probabilities (or best state) of the ground atoms are output to file by calling printProbabilities(). Of course, the header file of the new algorithm must be included in infer.cpp. The laziness or eagerness of the inference algorithm should be encapsulated in VariableState.

Inference: The Class Hierarchy