libDAI
|
Namespace for libDAI. More...
Classes | |
class | BBP |
Implements BBP (Back-Belief-Propagation) [EaG09]. More... | |
class | BBPCostFunction |
Predefined cost functions that can be used with BBP. More... | |
class | BipartiteGraph |
Represents the neighborhood structure of nodes in an undirected, bipartite graph. More... | |
class | BP |
Approximate inference algorithm "(Loopy) Belief Propagation". More... | |
class | BP_dual |
Calculates both types of BP messages and their normalizers from an InfAlg. More... | |
class | CBP |
Class for CBP (Conditioned Belief Propagation) [EaG09]. More... | |
class | ClusterGraph |
A ClusterGraph is a hypergraph with variables as nodes, and "clusters" (sets of variables) as hyperedges. More... | |
class | CobwebGraph |
A CobwebGraph is a special type of region graph used by the GLC algorithm. More... | |
class | CondProbEstimation |
Estimates the parameters of a conditional probability table, using pseudocounts. More... | |
class | DAG |
Represents the neighborhood structure of nodes in a directed cyclic graph. More... | |
class | DAIAlg |
Combines the abstract base class InfAlg with a graphical model (e.g., a FactorGraph or RegionGraph). More... | |
class | DEdge |
Represents a directed edge. More... | |
class | EMAlg |
EMAlg performs Expectation Maximization to learn factor parameters. More... | |
class | Evidence |
Stores a data set consisting of multiple samples, where each sample is the observed joint state of some variables. More... | |
class | ExactInf |
Exact inference algorithm using brute force enumeration (mainly useful for testing purposes) More... | |
class | Exception |
Error handling in libDAI is done by throwing an instance of the Exception class. More... | |
class | FactorGraph |
Represents a factor graph. More... | |
class | FBP |
Approximate inference algorithm "Fractional Belief Propagation" [WiH03]. More... | |
struct | fo_abs |
Function object that takes the absolute value. More... | |
struct | fo_absdiff |
Function object that returns the absolute difference of x and y. More... | |
struct | fo_divides0 |
Function object similar to std::divides(), but different in that dividing by zero results in zero. More... | |
struct | fo_exp |
Function object that takes the exponent. More... | |
struct | fo_Hellinger |
Function object useful for calculating the Hellinger distance. More... | |
struct | fo_id |
Function object that returns the value itself. More... | |
struct | fo_inv |
Function object that takes the inverse. More... | |
struct | fo_inv0 |
Function object that takes the inverse, except that 1/0 is defined to be 0. More... | |
struct | fo_KL |
Function object useful for calculating the KL distance. More... | |
struct | fo_log |
Function object that takes the logarithm. More... | |
struct | fo_log0 |
Function object that takes the logarithm, except that log(0) is defined to be 0. More... | |
struct | fo_max |
Function object that returns the maximum of two values. More... | |
struct | fo_min |
Function object that returns the minimum of two values. More... | |
struct | fo_plog0p |
Function object that returns p*log0(p) More... | |
struct | fo_pow |
Function object that returns x to the power y. More... | |
class | FRegion |
An FRegion is a factor with a counting number. More... | |
class | GraphAL |
Represents the neighborhood structure of nodes in an undirected graph. More... | |
class | GraphEL |
Represents an undirected graph, implemented as a std::set of undirected edges. More... | |
class | greedyVariableElimination |
Helper object for dai::ClusterGraph::VarElim() More... | |
class | HAK |
Approximate inference algorithm: implementation of single-loop ("Generalized Belief Propagation") and double-loop algorithms by Heskes, Albers and Kappen [HAK03]. More... | |
class | hash_map |
hash_map is an alias for std::tr1::unordered_map . More... | |
class | IndexFor |
Tool for looping over the states of several variables. More... | |
class | InfAlg |
InfAlg is an abstract base class, defining the common interface of all inference algorithms in libDAI. More... | |
class | JTree |
Exact inference algorithm using junction tree. More... | |
class | LC |
Approximate inference algorithm "Loop Corrected Belief Propagation" [MoK07]. More... | |
class | MaximizationStep |
A MaximizationStep groups together several parameter estimation tasks (SharedParameters objects) into a single unit. More... | |
class | MF |
Approximate inference algorithm "Mean Field". More... | |
class | MR |
Approximate inference algorithm by Montanari and Rizzo [MoR05]. More... | |
class | multifor |
multifor makes it easy to perform a dynamic number of nested for loops. More... | |
struct | Neighbor |
Describes the neighbor relationship of two nodes in a graph. More... | |
class | ParameterEstimation |
Base class for parameter estimation methods. More... | |
class | Permute |
Tool for calculating permutations of linear indices of multi-dimensional arrays. More... | |
class | PropertySet |
Represents a set of properties, mapping keys (of type PropertyKey) to values (of type PropertyValue) More... | |
class | Region |
A Region is a set of variables with a counting number. More... | |
class | RegionGraph |
A RegionGraph combines a bipartite graph consisting of outer regions (type FRegion) and inner regions (type Region) with a FactorGraph. More... | |
class | RootedTree |
Represents a rooted tree, implemented as a vector of directed edges. More... | |
class | sequentialVariableElimination |
Helper object for dai::ClusterGraph::VarElim() More... | |
class | SharedParameters |
Represents a single factor or set of factors whose parameters should be estimated. More... | |
class | SmallSet |
Represents a set; the implementation is optimized for a small number of elements. More... | |
class | State |
Makes it easy to iterate over all possible joint states of variables within a VarSet. More... | |
class | TFactor |
Represents a (probability) factor. More... | |
class | TProb |
Represents a vector with entries of type T. More... | |
class | TreeEP |
Approximate inference algorithm "Tree Expectation Propagation" [MiQ04]. More... | |
class | TRWBP |
Approximate inference algorithm "Tree-Reweighted Belief Propagation" [WJW03]. More... | |
class | UEdge |
Represents an undirected edge. More... | |
class | Var |
Represents a discrete random variable. More... | |
class | VarSet |
Represents a set of variables. More... | |
class | WeightedGraph |
Represents an undirected weighted graph, with weights of type T, implemented as a std::map mapping undirected edges to weights. More... | |
Typedefs | |
typedef boost::mt19937 | _rnd_gen_type |
Type of global random number generator. More... | |
typedef DAIAlg< FactorGraph > | DAIAlgFG |
Base class for inference algorithms that operate on a FactorGraph. More... | |
typedef DAIAlg< RegionGraph > | DAIAlgRG |
Base class for inference algorithms that operate on a RegionGraph. More... | |
typedef DAIAlg< CobwebGraph > | DAIAlgCG |
Base class for GLC that operates on CobwebGraph. More... | |
typedef TFactor< Real > | Factor |
Represents a factor with values of type dai::Real. More... | |
typedef std::vector< Neighbor > | Neighbors |
Describes the set of neighbors of some node in a graph. More... | |
typedef std::pair< size_t, size_t > | Edge |
Represents an edge in a graph: an Edge(i,j) corresponds to the edge between node i and node j. More... | |
typedef TProb< Real > | Prob |
Represents a vector with entries of type dai::Real. More... | |
typedef std::string | PropertyKey |
Type of the key of a Property. More... | |
typedef boost::any | PropertyValue |
Type of the value of a Property. More... | |
typedef std::pair< PropertyKey, PropertyValue > | Property |
A Property is a pair of a key and a corresponding value. More... | |
typedef double | Real |
Real number (alias for double , which could be changed to long double if necessary) More... | |
typedef mpz_class | BigInt |
Arbitrary precision integer number. More... | |
Enumerations | |
enum | ProbNormType { NORMPROB, NORMLINF } |
Enumerates different ways of normalizing a probability measure. More... | |
enum | ProbDistType { DISTL1, DISTLINF, DISTTV, DISTKL, DISTHEL } |
Enumerates different distance measures between probability measures. More... | |
Functions | |
std::map< std::string, InfAlg * > & | builtinInfAlgs () |
Returns a map that contains for each built-in inference algorithm its name and a pointer to an object of that type. More... | |
std::set< std::string > | builtinInfAlgNames () |
Returns a set of names of all available inference algorithms. More... | |
InfAlg * | newInfAlg (const std::string &name, const FactorGraph &fg, const PropertySet &opts) |
Constructs a new inference algorithm. More... | |
InfAlg * | newInfAlgFromString (const std::string &nameOpts, const FactorGraph &fg) |
Constructs a new inference algorithm. More... | |
InfAlg * | newInfAlgFromString (const std::string &nameOpts, const FactorGraph &fg, const std::map< std::string, std::string > &aliases) |
Constructs a new inference algorithm. More... | |
std::pair< std::string, PropertySet > | parseNameProperties (const std::string &s) |
Extracts the name and property set from a string s in the format "name[key1=val1,key2=val2,...]" or "name". More... | |
std::pair< std::string, PropertySet > | parseNameProperties (const std::string &s, const std::map< std::string, std::string > &aliases) |
Extracts the name and property set from a string s in the format "name[key1=val1,key2=val2,...]" or "name", performing alias substitution. More... | |
std::map< std::string, std::string > | readAliasesFile (const std::string &filename) |
Reads aliases from file named filename. More... | |
size_t | getFactorEntryForState (const FactorGraph &fg, size_t I, const vector< size_t > &state) |
Returns the entry of the I'th factor corresponding to a global state. More... | |
Real | numericBBPTest (const InfAlg &bp, const std::vector< size_t > *state, const PropertySet &bbp_props, const BBPCostFunction &cfn, Real h) |
vector< size_t > | complement (vector< size_t > &xis, size_t n_states) |
Given a sorted vector of states xis and total state count n_states, return a vector of states not in xis. More... | |
Real | unSoftMax (Real a, Real b) |
Computes . More... | |
Real | logSumExp (Real a, Real b) |
Computes log of sum of exponents, i.e., . More... | |
Real | dist (const vector< Factor > &b1, const vector< Factor > &b2, size_t nv) |
Compute sum of pairwise L-infinity distances of the first nv factors in each vector. More... | |
static vector< Factor > | mixBeliefs (Real p, const vector< Factor > &b, const vector< Factor > &c) |
Calculates a vector of mixtures p * b + (1-p) * c. More... | |
std::pair< size_t, size_t > | BBPFindClampVar (const InfAlg &in_bp, bool clampingVar, const PropertySet &bbp_props, const BBPCostFunction &cfn, Real *maxVarOut) |
size_t | eliminationCost_MinNeighbors (const ClusterGraph &cl, size_t i) |
Calculates cost of eliminating the i 'th variable from cluster graph cl according to the "MinNeighbors" criterion. More... | |
size_t | eliminationCost_MinWeight (const ClusterGraph &cl, size_t i) |
Calculates cost of eliminating the i 'th variable from cluster graph cl according to the "MinWeight" criterion. More... | |
size_t | eliminationCost_MinFill (const ClusterGraph &cl, size_t i) |
Calculates cost of eliminating the i 'th variable from cluster graph cl according to the "MinFill" criterion. More... | |
size_t | eliminationCost_WeightedMinFill (const ClusterGraph &cl, size_t i) |
Calculates cost of eliminating the i 'th variable from cluster graph cl according to the "WeightedMinFill" criterion. More... | |
FactorGraph | createFG (const GraphAL &G, FactorType ft, size_t states, const PropertySet &props) |
Creates a factor graph from a pairwise interactions graph. More... | |
FactorGraph | createHOIFG (size_t N, size_t M, size_t k, Real beta) |
Return a random factor graph with higher-order interactions. More... | |
BipartiteGraph | createRandomBipartiteGraph (size_t N1, size_t N2, size_t d1, size_t d2) |
Creates a regular random bipartite graph. More... | |
int | powmod (int x, int n, int p) |
Returns x**n % p, assuming p is prime. More... | |
size_t | order (int x, int p) |
Returns order of x in GF(p) with p prime. More... | |
bool | isPrime (size_t n) |
Returns whether n is a prime number. More... | |
BipartiteGraph | createSmallLDPCGraph () |
Constructs a regular LDPC graph with N=6, j=2, K=4, k=3. More... | |
BipartiteGraph | createGroupStructuredLDPCGraph (size_t p, size_t j, size_t k) |
Creates group-structured LDPC code. More... | |
void | createParityCheck (Real *result, size_t n, Real eps) |
DAI_ENUM (LDPCType, SMALL, GROUP, RANDOM) | |
Possible LDPC structures. More... | |
Factor | calcMarginal (const InfAlg &obj, const VarSet &vs, bool reInit) |
Calculates the marginal probability distribution for vs using inference algorithm obj. More... | |
vector< Factor > | calcPairBeliefs (const InfAlg &obj, const VarSet &vs, bool reInit, bool accurate=false) |
Calculates beliefs for all pairs of variables in vs using inference algorithm obj. More... | |
std::vector< size_t > | findMaximum (const InfAlg &obj) |
Calculates the joint state of all variables that has maximum probability, according to the inference algorithm obj. More... | |
Factor | createFactorIsing (const Var &x, Real h) |
Returns a binary unnormalized single-variable factor where . More... | |
Factor | createFactorIsing (const Var &x1, const Var &x2, Real J) |
Returns a binary unnormalized pairwise factor where . More... | |
Factor | createFactorExpGauss (const VarSet &vs, Real beta) |
Returns a random factor on the variables vs with strength beta. More... | |
Factor | createFactorPotts (const Var &x1, const Var &x2, Real J) |
Returns a pairwise Potts factor . More... | |
Factor | createFactorDelta (const Var &v, size_t state) |
Returns a Kronecker delta point mass. More... | |
Factor | createFactorDelta (const VarSet &vs, size_t state) |
Returns a Kronecker delta point mass. More... | |
std::ostream & | operator<< (std::ostream &os, const FactorGraph &fg) |
Writes a FactorGraph to an output stream. More... | |
std::istream & | operator>> (std::istream &is, FactorGraph &fg) |
Reads a FactorGraph from an input stream. More... | |
GraphAL | createGraphFull (size_t N) |
Creates a fully-connected graph with N nodes. More... | |
GraphAL | createGraphGrid (size_t N1, size_t N2, bool periodic) |
Creates a two-dimensional rectangular grid of N1 by N2 nodes, which can be periodic. More... | |
GraphAL | createGraphGrid3D (size_t N1, size_t N2, size_t N3, bool periodic) |
Creates a three-dimensional rectangular grid of N1 by N2 by N3 nodes, which can be periodic. More... | |
GraphAL | createGraphLoop (size_t N) |
Creates a graph consisting of a single loop of N nodes. More... | |
GraphAL | createGraphTree (size_t N) |
Creates a random tree-structured graph of N nodes. More... | |
GraphAL | createGraphRegular (size_t N, size_t d) |
Creates a random regular graph of N nodes with uniform connectivity d. More... | |
template<class T > | |
TFactor< T > & | makePositive (TFactor< T > &f, T epsilon) |
Sets factor entries that lie between 0 and epsilon to epsilon. More... | |
template<class T > | |
TFactor< T > & | makeZero (TFactor< T > &f, T epsilon) |
Sets factor entries that are smaller (in absolute value) than epsilon to 0. More... | |
void | ReadUaiAieFactorGraphFile (const char *filename, size_t verbose, std::vector< Var > &vars, std::vector< Factor > &factors, std::vector< Permute > &permutations) |
Reads factor graph (as a pair of a variable vector and factor vector) from a file in the UAI approximate inference challenge format. More... | |
std::vector< std::map< size_t, size_t > > | ReadUaiAieEvidenceFile (const char *filename, size_t verbose) |
Reads evidence (a mapping from observed variable labels to the observed values) from a file in the UAI approximate inference challenge format. More... | |
std::pair< size_t, BigInt > | boundTreewidth (const FactorGraph &fg, greedyVariableElimination::eliminationCostFunction fn, size_t maxStates) |
std::ostream & | operator<< (std::ostream &os, const Property &p) |
Writes a Property object (key-value pair) to an output stream. More... | |
std::ostream & | operator<< (std::ostream &os, const PropertySet &ps) |
Writes a PropertySet object to an output stream. More... | |
std::istream & | operator>> (std::istream &is, PropertySet &ps) |
Reads a PropertySet object from an input stream, storing values as strings. More... | |
ostream & | operator<< (ostream &os, const RegionGraph &rg) |
Send RegionGraph to output stream. More... | |
bool | isnan (Real x) |
Returns true if argument is NAN (Not A Number) More... | |
double | toc () |
Returns wall clock time in seconds. More... | |
_rnd_gen_type | _rnd_gen (42U) |
Global random number generator. More... | |
boost::uniform_real< Real > | _uni_dist (0, 1) |
Uniform distribution with values between 0 and 1 (0 inclusive, 1 exclusive). More... | |
boost::variate_generator< _rnd_gen_type &, boost::uniform_real< Real > > | _uni_rnd (_rnd_gen, _uni_dist) |
Global uniform random random number. More... | |
boost::variate_generator< _rnd_gen_type &, boost::normal_distribution< Real > > | _normal_rnd (_rnd_gen, _normal_dist) |
Global random number generator with standard normal distribution. More... | |
void | rnd_seed (size_t seed) |
Sets the random seed. More... | |
Real | rnd_uniform () |
Returns a real number, distributed uniformly on [0,1) More... | |
Real | rnd_stdnormal () |
Returns a real number from a standard-normal distribution. More... | |
int | rnd_int (int min, int max) |
Returns a random integer in interval [min, max]. More... | |
std::vector< std::string > | tokenizeString (const std::string &s, bool singleDelim, const std::string &delim="\t\n") |
Split a string into tokens delimited by one of the characters in delim. More... | |
size_t | calcLinearState (const VarSet &vs, const std::map< Var, size_t > &state) |
Calculates the linear index in the Cartesian product of the variables in vs that corresponds to a particular joint assignment of the variables, specified by state. More... | |
std::map< Var, size_t > | calcState (const VarSet &vs, size_t linearState) |
Calculates the joint assignment of the variables in vs corresponding to the linear index linearState. More... | |
mxArray * | Factors2mx (const std::vector< Factor > &Ps) |
Convert vector<Factor> structure to a cell vector of CPTAB-like structs. More... | |
vector< Factor > | mx2Factors (const mxArray *psi, long verbose) |
Convert cell vector of CPTAB-like structs to vector<Factor> More... | |
Factor | mx2Factor (const mxArray *psi) |
Convert CPTAB-like struct to Factor. More... | |
DAI_ENUM (BBPCostFunctionBase, CFN_GIBBS_B, CFN_GIBBS_B2, CFN_GIBBS_EXP, CFN_GIBBS_B_FACTOR, CFN_GIBBS_B2_FACTOR, CFN_GIBBS_EXP_FACTOR, CFN_VAR_ENT, CFN_FACTOR_ENT, CFN_BETHE_ENT) | |
Enumeration of several cost functions that can be used with BBP. More... | |
DAI_ENUM (FactorType, ISINGGAUSS, ISINGUNIFORM, EXPGAUSS, POTTS) | |
Possible factor types. More... | |
size_t | BigInt_size_t (const BigInt &N) |
Safe down-cast of big integer to size_t. More... | |
Real | log (Real x) |
Returns logarithm of x. More... | |
Real | log0 (Real x) |
Returns logarithm of x, or 0 if x == 0. More... | |
Real | exp (Real x) |
Returns exponent of x. More... | |
Real | pow (Real x, Real y) |
Returns x to the power y. More... | |
template<class T > | |
T | abs (const T &t) |
Returns absolute value of t. More... | |
int | rnd (int n) |
Returns a random integer in the half-open interval [0, n) More... | |
template<class T > | |
std::string | toString (const T &x) |
Converts a variable of type T to a std::string by using a boost::lexical_cast . More... | |
template<class T > | |
T | fromString (const std::string &x) |
Converts a variable of type std::string to T by using a boost::lexical_cast . More... | |
template<class T > | |
std::ostream & | operator<< (std::ostream &os, const std::vector< T > &x) |
Writes a std::vector<> to a std::ostream . More... | |
template<class T > | |
std::ostream & | operator<< (std::ostream &os, const std::set< T > &x) |
Writes a std::set<> to a std::ostream . More... | |
template<class T1 , class T2 > | |
std::ostream & | operator<< (std::ostream &os, const std::map< T1, T2 > &x) |
Writes a std::map<> to a std::ostream . More... | |
template<class T1 , class T2 > | |
std::ostream & | operator<< (std::ostream &os, const std::pair< T1, T2 > &x) |
Writes a std::pair<> to a std::ostream . More... | |
template<class T > | |
std::vector< T > | concat (const std::vector< T > &u, const std::vector< T > &v) |
Concatenates two vectors. More... | |
template<typename T > | |
RootedTree | MinSpanningTree (const WeightedGraph< T > &G, bool usePrim) |
Constructs a minimum spanning tree from the (non-negatively) weighted graph G. More... | |
template<typename T > | |
RootedTree | MaxSpanningTree (const WeightedGraph< T > &G, bool usePrim) |
Constructs a minimum spanning tree from the (non-negatively) weighted graph G. More... | |
Variables | |
static _builtinInfAlgs | allBuiltinInfAlgs |
const char * | FULL_TYPE = "FULL" |
Predefined names of various factor graph types. More... | |
const char * | DREG_TYPE = "DREG" |
const char * | LOOP_TYPE = "LOOP" |
const char * | TREE_TYPE = "TREE" |
const char * | GRID_TYPE = "GRID" |
const char * | GRID3D_TYPE = "GRID3D" |
const char * | HOI_TYPE = "HOI" |
const char * | LDPC_TYPE = "LDPC" |
boost::normal_distribution< Real > | _normal_dist |
Normal distribution with mean 0 and standard deviation 1. More... | |
Namespace for libDAI.
typedef boost::mt19937 dai::_rnd_gen_type |
Type of global random number generator.
typedef DAIAlg<FactorGraph> dai::DAIAlgFG |
Base class for inference algorithms that operate on a FactorGraph.
typedef DAIAlg<RegionGraph> dai::DAIAlgRG |
Base class for inference algorithms that operate on a RegionGraph.
typedef DAIAlg<CobwebGraph> dai::DAIAlgCG |
Base class for GLC that operates on CobwebGraph.
typedef TFactor<Real> dai::Factor |
Represents a factor with values of type dai::Real.
typedef std::vector<Neighbor> dai::Neighbors |
Describes the set of neighbors of some node in a graph.
typedef std::pair<size_t,size_t> dai::Edge |
Represents an edge in a graph: an Edge(i,j) corresponds to the edge between node i and node j.
typedef std::string dai::PropertyKey |
Type of the key of a Property.
typedef boost::any dai::PropertyValue |
Type of the value of a Property.
typedef std::pair<PropertyKey, PropertyValue> dai::Property |
A Property is a pair of a key and a corresponding value.
typedef double dai::Real |
Real number (alias for double
, which could be changed to long double
if necessary)
typedef mpz_class dai::BigInt |
Arbitrary precision integer number.
enum dai::ProbNormType |
Enumerates different ways of normalizing a probability measure.
enum dai::ProbDistType |
Enumerates different distance measures between probability measures.
std::map< std::string, InfAlg * > & dai::builtinInfAlgs | ( | ) |
Returns a map that contains for each built-in inference algorithm its name and a pointer to an object of that type.
This functionality is obsolete and will be removed in future versions of libDAI
std::set< std::string > dai::builtinInfAlgNames | ( | ) |
Returns a set of names of all available inference algorithms.
InfAlg * dai::newInfAlg | ( | const std::string & | name, |
const FactorGraph & | fg, | ||
const PropertySet & | opts | ||
) |
Constructs a new inference algorithm.
name | The name of the inference algorithm. |
fg | The FactorGraph that the algorithm should be applied to. |
opts | A PropertySet specifying the options for the algorithm. |
UNKNOWN_DAI_ALGORITHM | if the requested name is not known/compiled in. |
InfAlg * dai::newInfAlgFromString | ( | const std::string & | nameOpts, |
const FactorGraph & | fg | ||
) |
Constructs a new inference algorithm.
nameOpts | The name and options of the inference algorithm (should be in the format "name[key1=val1,key2=val2,...,keyn=valn]"). |
fg | The FactorGraph that the algorithm should be applied to. |
UNKNOWN_DAI_ALGORITHM | if the requested name is not known/compiled in. |
InfAlg * dai::newInfAlgFromString | ( | const std::string & | nameOpts, |
const FactorGraph & | fg, | ||
const std::map< std::string, std::string > & | aliases | ||
) |
Constructs a new inference algorithm.
nameOpts | The name and options of the inference algorithm (should be in the format "name[key1=val1,key2=val2,...,keyn=valn]"). |
fg | The FactorGraph that the algorithm should be applied to. |
aliases | Maps names to strings in the format "name[key1=val1,key2=val2,...,keyn=valn]"; if not empty, alias substitution will be performed when parsing nameOpts by invoking parseNameProperties(const std::string &,const std::map<std::string,std::string> &) |
std::pair< std::string, PropertySet > dai::parseNameProperties | ( | const std::string & | s | ) |
Extracts the name and property set from a string s in the format "name[key1=val1,key2=val2,...]" or "name".
std::pair< std::string, PropertySet > dai::parseNameProperties | ( | const std::string & | s, |
const std::map< std::string, std::string > & | aliases | ||
) |
Extracts the name and property set from a string s in the format "name[key1=val1,key2=val2,...]" or "name", performing alias substitution.
Alias substitution is performed as follows: as long as name appears as a key in aliases, it is substituted by its value. Properties in s override those of the alias (in case of recursion, the "outer" properties override those of the "inner" aliases).
std::map< std::string, std::string > dai::readAliasesFile | ( | const std::string & | filename | ) |
Reads aliases from file named filename.
filename | Name of the alias file |
size_t dai::getFactorEntryForState | ( | const FactorGraph & | fg, |
size_t | I, | ||
const vector< size_t > & | state | ||
) |
Returns the entry of the I'th factor corresponding to a global state.
vector<size_t> dai::complement | ( | vector< size_t > & | xis, |
size_t | n_states | ||
) |
Given a sorted vector of states xis and total state count n_states, return a vector of states not in xis.
Compute sum of pairwise L-infinity distances of the first nv factors in each vector.
|
static |
Calculates a vector of mixtures p * b + (1-p) * c.
size_t dai::eliminationCost_MinNeighbors | ( | const ClusterGraph & | cl, |
size_t | i | ||
) |
Calculates cost of eliminating the i 'th variable from cluster graph cl according to the "MinNeighbors" criterion.
The cost is measured as "number of neigboring nodes in the current adjacency graph", where the adjacency graph has the variables as its nodes and connects nodes i1 and i2 iff i1 and i2 occur together in some common cluster.
size_t dai::eliminationCost_MinWeight | ( | const ClusterGraph & | cl, |
size_t | i | ||
) |
Calculates cost of eliminating the i 'th variable from cluster graph cl according to the "MinWeight" criterion.
The cost is measured as "product of weights of neighboring nodes in the current adjacency graph", where the adjacency graph has the variables as its nodes and connects nodes i1 and i2 iff i1 and i2 occur together in some common cluster. The weight of a node is the number of states of the corresponding variable.
size_t dai::eliminationCost_MinFill | ( | const ClusterGraph & | cl, |
size_t | i | ||
) |
Calculates cost of eliminating the i 'th variable from cluster graph cl according to the "MinFill" criterion.
The cost is measured as "number of added edges in the adjacency graph", where the adjacency graph has the variables as its nodes and connects nodes i1 and i2 iff i1 and i2 occur together in some common cluster.
size_t dai::eliminationCost_WeightedMinFill | ( | const ClusterGraph & | cl, |
size_t | i | ||
) |
Calculates cost of eliminating the i 'th variable from cluster graph cl according to the "WeightedMinFill" criterion.
The cost is measured as "total weight of added edges in the adjacency graph", where the adjacency graph has the variables as its nodes and connects nodes i1 and i2 iff i1 and i2 occur together in some common cluster. The weight of an edge is the product of the number of states of the variables corresponding with its nodes.
FactorGraph dai::createFG | ( | const GraphAL & | G, |
FactorType | ft, | ||
size_t | states, | ||
const PropertySet & | props | ||
) |
Creates a factor graph from a pairwise interactions graph.
G | Graph describing interactions between variables |
ft | Type of factors to use for interactions |
states | Number of states of the variables |
props | Additional properties for generating the interactions |
FactorGraph dai::createHOIFG | ( | size_t | N, |
size_t | M, | ||
size_t | k, | ||
Real | beta | ||
) |
Return a random factor graph with higher-order interactions.
N | number of variables |
M | number of factors |
k | number of variables that each factor depends on |
beta | standard-deviation of Gaussian log-factor entries |
BipartiteGraph dai::createRandomBipartiteGraph | ( | size_t | N1, |
size_t | N2, | ||
size_t | d1, | ||
size_t | d2 | ||
) |
Creates a regular random bipartite graph.
N1 | = number of nodes of type 1 |
d1 | = size of neighborhoods of nodes of type 1 |
N2 | = number of nodes of type 2 |
d2 | = size of neighborhoods of nodes of type 2 |
int dai::powmod | ( | int | x, |
int | n, | ||
int | p | ||
) |
Returns x**n % p, assuming p is prime.
size_t dai::order | ( | int | x, |
int | p | ||
) |
Returns order of x in GF(p) with p prime.
bool dai::isPrime | ( | size_t | n | ) |
Returns whether n is a prime number.
BipartiteGraph dai::createSmallLDPCGraph | ( | ) |
Constructs a regular LDPC graph with N=6, j=2, K=4, k=3.
BipartiteGraph dai::createGroupStructuredLDPCGraph | ( | size_t | p, |
size_t | j, | ||
size_t | k | ||
) |
Creates group-structured LDPC code.
Use construction described in "A Class of Group-Structured LDPC Codes" by R. M. Tanner, D. Sridhara and T. Fuja Proceedings of ICSTA, 2001
Example parameters: (p,j,k) = (31,3,5) (p,j,k) = (37,3,4) (p,j,k) = (7,2,4) (p,j,k) = (29,2,4)
j and k must be divisors of p-1
dai::DAI_ENUM | ( | LDPCType | , |
SMALL | , | ||
GROUP | , | ||
RANDOM | |||
) |
Possible LDPC structures.
Calculates the marginal probability distribution for vs using inference algorithm obj.
calcMarginal() works by clamping all variables in vs and calculating the partition sum for each clamped state. Therefore, it can be used in combination with any inference algorithm that can calculate/approximate partition sums.
obj | instance of inference algorithm to be used |
vs | variables for which the marginal should be calculated |
reInit | should be set to true if at least one of the possible clamped states would be invalid (leading to a factor graph with zero partition sum). |
std::vector< Factor > dai::calcPairBeliefs | ( | const InfAlg & | obj, |
const VarSet & | vs, | ||
bool | reInit, | ||
bool | accurate = false |
||
) |
Calculates beliefs for all pairs of variables in vs using inference algorithm obj.
calcPairBeliefs() works by
false
;true
.Therefore, it can be used in combination with any inference algorithm that can calculate/approximate partition sums (and single variable beliefs, if accurate == true
).
obj | instance of inference algorithm to be used |
vs | variables for which the pair beliefs should be calculated |
reInit | should be set to true if at least one of the possible clamped states would be invalid (leading to a factor graph with zero partition sum). |
accurate | if true , uses a slower but more accurate approximation algorithm |
std::vector< size_t > dai::findMaximum | ( | const InfAlg & | obj | ) |
Calculates the joint state of all variables that has maximum probability, according to the inference algorithm obj.
Returns a binary unnormalized single-variable factor where .
x | Variable (should be binary) |
h | Field strength |
Returns a binary unnormalized pairwise factor where .
x1 | First variable (should be binary) |
x2 | Second variable (should be binary) |
J | Coupling strength |
Returns a random factor on the variables vs with strength beta.
Each entry are set by drawing a normally distributed random with mean 0 and standard-deviation beta, and taking its exponent.
vs | Variables |
beta | Factor strength (inverse temperature) |
Returns a pairwise Potts factor .
x1 | First variable |
x2 | Second variable (should have the same number of states as x1) |
J | Factor strength |
Returns a Kronecker delta point mass.
v | Variable |
state | The state of v that should get value 1 |
Returns a Kronecker delta point mass.
vs | Set of variables |
state | The state of vs that should get value 1 |
std::ostream& dai::operator<< | ( | std::ostream & | os, |
const FactorGraph & | fg | ||
) |
Writes a FactorGraph to an output stream.
Writes a factor graph to an output stream.
std::istream& dai::operator>> | ( | std::istream & | is, |
FactorGraph & | fg | ||
) |
Reads a FactorGraph from an input stream.
Reads a factor graph from an input stream.
INVALID_FACTORGRAPH_FILE | if the input stream is not valid |
GraphAL dai::createGraphFull | ( | size_t | N | ) |
Creates a fully-connected graph with N nodes.
GraphAL dai::createGraphGrid | ( | size_t | N1, |
size_t | N2, | ||
bool | periodic | ||
) |
Creates a two-dimensional rectangular grid of N1 by N2 nodes, which can be periodic.
GraphAL dai::createGraphGrid3D | ( | size_t | N1, |
size_t | N2, | ||
size_t | N3, | ||
bool | periodic | ||
) |
Creates a three-dimensional rectangular grid of N1 by N2 by N3 nodes, which can be periodic.
GraphAL dai::createGraphLoop | ( | size_t | N | ) |
Creates a graph consisting of a single loop of N nodes.
GraphAL dai::createGraphTree | ( | size_t | N | ) |
Creates a random tree-structured graph of N nodes.
GraphAL dai::createGraphRegular | ( | size_t | N, |
size_t | d | ||
) |
Creates a random regular graph of N nodes with uniform connectivity d.
Algorithm 1 in [StW99]. Draws a random graph of size N and uniform degree d from an almost uniform probability distribution over these graphs (which becomes uniform in the limit that d is small and N goes to infinity).
Sets factor entries that lie between 0 and epsilon to epsilon.
Sets factor entries that are smaller (in absolute value) than epsilon to 0.
void dai::ReadUaiAieFactorGraphFile | ( | const char * | filename, |
size_t | verbose, | ||
std::vector< Var > & | vars, | ||
std::vector< Factor > & | factors, | ||
std::vector< Permute > & | permutations | ||
) |
Reads factor graph (as a pair of a variable vector and factor vector) from a file in the UAI approximate inference challenge format.
[in] | filename | The filename (usually ends with ".uai") |
[in] | verbose | The amount of output sent to cout |
[out] | vars | Array of variables read from the file |
[out] | factors | Array of factors read from the file |
[out] | permutations | Array of permutations, which permute between libDAI canonical ordering and ordering specified by the file |
std::vector< std::map< size_t, size_t > > dai::ReadUaiAieEvidenceFile | ( | const char * | filename, |
size_t | verbose | ||
) |
Reads evidence (a mapping from observed variable labels to the observed values) from a file in the UAI approximate inference challenge format.
[in] | filename | The filename (usually ends with ".uai.evid") |
[in] | verbose | The amount of output sent to cout |
std::ostream & dai::operator<< | ( | std::ostream & | os, |
const Property & | p | ||
) |
Writes a Property object (key-value pair) to an output stream.
std::ostream& dai::operator<< | ( | std::ostream & | os, |
const PropertySet & | ps | ||
) |
Writes a PropertySet object to an output stream.
It uses the format "[key1=val1,key2=val2,...,keyn=valn]"
.
UNKNOWN_PROPERTY_TYPE | if the type of a property value is not supported. |
std::istream& dai::operator>> | ( | std::istream & | is, |
PropertySet & | ps | ||
) |
Reads a PropertySet object from an input stream, storing values as strings.
Reads a PropertySet object from an input stream.
It expects a string in the format "[key1=val1,key2=val2,...,keyn=valn]"
. Values are stored as strings.
MALFORMED_PROPERTY | if the string is not in the expected format |
ostream& dai::operator<< | ( | std::ostream & | os, |
const RegionGraph & | rg | ||
) |
Send RegionGraph to output stream.
Writes a region graph to an output stream.
bool dai::isnan | ( | Real | x | ) |
Returns true if argument is NAN (Not A Number)
double dai::toc | ( | ) |
Returns wall clock time in seconds.
_rnd_gen_type dai::_rnd_gen | ( | 42U | ) |
Global random number generator.
boost::uniform_real<Real> dai::_uni_dist | ( | 0 | , |
1 | |||
) |
Uniform distribution with values between 0 and 1 (0 inclusive, 1 exclusive).
boost::variate_generator<_rnd_gen_type&, boost::uniform_real<Real> > dai::_uni_rnd | ( | _rnd_gen | , |
_uni_dist | |||
) |
Global uniform random random number.
boost::variate_generator<_rnd_gen_type&, boost::normal_distribution<Real> > dai::_normal_rnd | ( | _rnd_gen | , |
_normal_dist | |||
) |
Global random number generator with standard normal distribution.
void dai::rnd_seed | ( | size_t | seed | ) |
Sets the random seed.
Real dai::rnd_uniform | ( | ) |
Returns a real number, distributed uniformly on [0,1)
Real dai::rnd_stdnormal | ( | ) |
Returns a real number from a standard-normal distribution.
int dai::rnd_int | ( | int | min, |
int | max | ||
) |
Returns a random integer in interval [min, max].
std::vector< std::string > dai::tokenizeString | ( | const std::string & | s, |
bool | singleDelim, | ||
const std::string & | delim = "\t\n" |
||
) |
Split a string into tokens delimited by one of the characters in delim.
s | the string to be split into tokens |
singleDelim | if true , any single delimiter forms a boundary between two tokens; if false , a maximal group of consecutive delimiters forms a boundary between two tokens |
delim | delimiter characters |
Calculates the linear index in the Cartesian product of the variables in vs that corresponds to a particular joint assignment of the variables, specified by state.
vs | Set of variables for which the linear state should be calculated; |
state | Specifies the states of some variables. |
The linear index is calculated as follows. The variables in vs are ordered according to their label (in ascending order); say vs corresponds with the set with , where variable has label l. Denote by the number of possible values ("states") of variable . The argument state corresponds with a mapping s that assigns to each variable a state , where if is not specified in state. The linear index corresponding with state is now calculated by:
Calculates the joint assignment of the variables in vs corresponding to the linear index linearState.
vs | Set of variables to which linearState refers |
linearState | should be smaller than vs.nrStates(). |
The variables in vs are ordered according to their label (in ascending order); say vs corresponds with the set with , where variable has label l. Denote by the number of possible values ("states") of variable with label l. The mapping returned by this function is defined as:
where denotes the value of linearState.
mxArray * dai::Factors2mx | ( | const vector< Factor > & | Ps | ) |
Convert vector<Factor> structure to a cell vector of CPTAB-like structs.
std::vector< Factor > dai::mx2Factors | ( | const mxArray * | psi, |
long | verbose | ||
) |
Convert cell vector of CPTAB-like structs to vector<Factor>
Factor dai::mx2Factor | ( | const mxArray * | psi | ) |
Convert CPTAB-like struct to Factor.
dai::DAI_ENUM | ( | BBPCostFunctionBase | , |
CFN_GIBBS_B | , | ||
CFN_GIBBS_B2 | , | ||
CFN_GIBBS_EXP | , | ||
CFN_GIBBS_B_FACTOR | , | ||
CFN_GIBBS_B2_FACTOR | , | ||
CFN_GIBBS_EXP_FACTOR | , | ||
CFN_VAR_ENT | , | ||
CFN_FACTOR_ENT | , | ||
CFN_BETHE_ENT | |||
) |
Enumeration of several cost functions that can be used with BBP.
dai::DAI_ENUM | ( | FactorType | , |
ISINGGAUSS | , | ||
ISINGUNIFORM | , | ||
EXPGAUSS | , | ||
POTTS | |||
) |
Possible factor types.
|
inline |
Safe down-cast of big integer to size_t.
Returns logarithm of x.
Returns exponent of x.
Returns x to the power y.
We use the convention that division by zero yields zero; for powers, this means that if x == 0.0 and y < 0.0, we return 0.0 instead of generating an error.
|
inline |
Returns absolute value of t.
|
inline |
Returns a random integer in the half-open interval [0, n)
std::string dai::toString | ( | const T & | x | ) |
Converts a variable of type T to a std::string
by using a boost::lexical_cast
.
T dai::fromString | ( | const std::string & | x | ) |
Converts a variable of type std::string to T by using a boost::lexical_cast
.
std::ostream& dai::operator<< | ( | std::ostream & | os, |
const std::vector< T > & | x | ||
) |
Writes a std::vector<>
to a std::ostream
.
std::ostream& dai::operator<< | ( | std::ostream & | os, |
const std::set< T > & | x | ||
) |
Writes a std::set<>
to a std::ostream
.
std::ostream& dai::operator<< | ( | std::ostream & | os, |
const std::map< T1, T2 > & | x | ||
) |
Writes a std::map<>
to a std::ostream
.
std::ostream& dai::operator<< | ( | std::ostream & | os, |
const std::pair< T1, T2 > & | x | ||
) |
Writes a std::pair<>
to a std::ostream
.
std::vector<T> dai::concat | ( | const std::vector< T > & | u, |
const std::vector< T > & | v | ||
) |
Concatenates two vectors.
RootedTree dai::MinSpanningTree | ( | const WeightedGraph< T > & | G, |
bool | usePrim | ||
) |
Constructs a minimum spanning tree from the (non-negatively) weighted graph G.
G | Weighted graph that should have non-negative weights. |
usePrim | If true, use Prim's algorithm (complexity O(E log(V))), otherwise, use Kruskal's algorithm (complexity O(E log(E))). |
RootedTree dai::MaxSpanningTree | ( | const WeightedGraph< T > & | G, |
bool | usePrim | ||
) |
Constructs a minimum spanning tree from the (non-negatively) weighted graph G.
G | Weighted graph that should have non-negative weights. |
usePrim | If true, use Prim's algorithm (complexity O(E log(V))), otherwise, use Kruskal's algorithm (complexity O(E log(E))). |
const char* dai::FULL_TYPE = "FULL" |
Predefined names of various factor graph types.
boost::normal_distribution<Real> dai::_normal_dist |
Normal distribution with mean 0 and standard deviation 1.