Above is a diagram of my view of some complexity results. P is the set of problems that are solvable in polynomial time. P-Complete is the set of problems which all problems in P can be polynomial-time reduced to...

A Horn clause is restricted to have at most one positive literal. They are typically written as an implication statement which can be converted to a disjunctive clause: Horn clauses are an interesting restriction because they allow efficient resolution and...

Generally speaking in generative learning one is trying to optimize the parameters of a generative model to best explain the data that is observed. In discriminative learning there is no model assumed, but instead a function is optimized to best...

The negative binomial distribution captures the probability of having S-1 successes and F failures in F+S-1 trials and then a success on the (F+S)th trial[1] where the probability of success at any trial is P. Let this function be...

Jeff Bilmes makes an excellent point about distributions and talking about them correctly. In particular: An exponential distribution is a continous distribution. A geometric distribution is the discrete version. A gamma distribution is a continuous distribution. A negative binomial distribution...

There is a progression of sophistication in parameter estimation which goes as follows, from less sophisticated to more sophisticate: Maximum Likelihood: This is a point estimate of a parameter which defines an unobservable distribution. It is obtained by choosing the...

A conjugate prior is a distribution whose aposterior estimate has the same form as the prior. This is good because it allows arbitrary numbers of updates to be made to the distribution as more data becomes available....

From Decision-Theoretic Planning: Structural Assumptions and Computational Leverage: A classical STRIPS operator is described by a precondition and a set of effects. The former identifies the set of states in which the action can be executed, and the latter...

A directed graphical model can be converted to an undirected graphical model through a process called moralization. Graphically, moralization is accomplished by creating an undirected clique for every node in the directed graph and it's parents. A directed graph...

Belief propagation is an algorithm for efficiently calculating the probability of a variable in a graphical model given some evidence. This requires marginalizing out all the other variables in the graph. The naive approach to marginalization would lead to...

From Policy Recognition in the Abstract Hidden Markov Model: Rao-Blackwellisation is a general technique for improving the accuracy of sampling methods by analytically marginalizing some variables and only sampling the remainder. In its simplest form, consider the problem of...

It is known that exact inference in Bayesian Networks is NP-Hard with respect to the network size. Cooper, G.F. (1990). The computational complexity of probabilistic inference using Bayesian belief networks. Artificial Intelligence, 42, 393-405 Approximate Bayesian Network inference scales...