The whole Artificial Intelligence formula sheet, to print

Uniform tree with branching factor $b$, goal at depth $d$, the last iteration generating every node to depth $d$, root counted in every iteration. Nodes at depth $i$ are generated $d+1-i$ times.

From the sum above with $k=d-i$: $N_{\text{IDS}}=b^d{\sum }_{k=0}^d(k+1)b^{-k}<b^d(1-1/b{)}^{-2}$. For $b=2$ the factor is 4; for $b=10$ it is about 1.23.

A* always expands the frontier node with the smallest $f$. Greedy best-first search uses $f(n)=h(n)$ alone; uniform-cost search is A* with $h\equiv 0$.

Never overestimates the true remaining cost. Enough for A* to be optimal in tree search, and in graph search when cheaper paths re-open expanded nodes.

A triangle inequality on estimates. Every consistent heuristic is admissible; the converse is false. Along any path $f$ never decreases when $h$ is consistent.

Two-player zero-sum game, perfect information, finite tree. The value is computed bottom-up.

$m$ is the maximum depth of the game tree. Minimax is complete on a finite tree and optimal against an optimal opponent.

Updates: at a MAX node $\alpha \leftarrow \max (\alpha ,v)$; at a MIN node $\beta \leftarrow \min (\beta ,v)$, where $v$ is the best child value so far. Pruning when $\alpha =\beta$ is safe because it cannot change the root value. Some sources prune only when $\alpha >\beta$; that can change the number of pruned leaves but never the root value. These notes use $\alpha \ge \beta$.

With perfect ordering alpha-beta can look about twice as deep as minimax in the same time; with random ordering the cost is roughly $b^{3m/4}$. The root value is the same for every ordering; only the number of pruned leaves changes.

Uniform game tree with branching factor $b$, all leaves at depth $m$, distinct leaf values, children ordered best-first for the player to move. Example: $b=3$, $m=2$ gives $3+3-1=5$ leaves (all three under the first MIN child, then one under each other child).

The usual first step (after rewriting $\leftrightarrow$) when converting to CNF or DNF.

True exactly when p and q have the same truth value.

The converse $q\to p$ and the inverse $\neg p\to \neg q$ are NOT equivalent to $p\to q$ (they are equivalent to each other).

Double negation: $\neg \neg p\equiv p$.

$\neg (p\leftrightarrow q)$ is the exclusive or $p\oplus q$: true exactly when $p$ and $q$ differ. The negation of an implication is a conjunction, never another implication.

Each of $\wedge$ and $\vee$ distributes over the other; used to reach CNF and DNF.

Moves a conjunction in the premise into a chain of implications.

Check any of these by rewriting both sides with $p\to q\equiv \neg p\vee q$. Note the second line: a conjunctive premise splits into an OR, not an AND.

$\phi \models \psi$ means every assignment making $\phi$ true also makes $\psi$ true. With several premises: ${\phi }_1,\dots ,{\phi }_k\models \psi$ exactly when $({\phi }_1\wedge \cdots \wedge {\phi }_k)\to \psi$ is a tautology.

The basis of proof by contradiction and of resolution refutation.

A minterm is true exactly on its row; a maxterm is false exactly on its row. In the maxterm, a variable that is T in the row appears negated and one that is F appears plain (for the row $p=\mathrm{T},q=\mathrm{F}$ the maxterm is $\neg p\vee q$). A formula with no T rows has an empty DNF (a contradiction); one with no F rows has an empty CNF (a tautology).

Applies to two clauses holding a complementary pair of literals. The resolvent is entailed by its two parents (soundness). Resolution refutation is also complete for propositional logic: if a clause set is unsatisfiable, the empty clause can be derived from it.

Negation flips the quantifier and moves inside; apply De Morgan's laws to what remains.

When both P and Q contain x free, only these two distribute as equivalences.

Valid when $x$ does not occur free in $Q$ and the domain is non-empty.

Valid when $x$ does not occur free in $Q$ and the domain is non-empty. A quantifier moved out of the conclusion stays the same; one moved out of the premise FLIPS ($\forall$ becomes $\exists$ and vice versa), because the premise sits under a hidden negation: $P(x)\to Q\equiv \neg P(x)\vee Q$.

The converse of each is NOT valid.

The first needs the non-empty domain. None of the converses is valid: for example, with domain $\{1,2\}$, $P(1)$ true, $P(2)$ false and $Q(1)$ false, $\forall xP\to \forall xQ$ is true but $\forall x(P\to Q)$ is false.

Like quantifiers commute: $\forall x\forall y\equiv \forall y\forall x$ and $\exists x\exists y\equiv \exists y\exists x$.

Clauses must share no variable names (standardise apart); the empty clause again signals unsatisfiability of the clause set. Resolution together with factoring (unifying two literals inside one clause) is refutation-complete for first-order logic: an unsatisfiable clause set always yields the empty clause. If the set is satisfiable the search may never stop, since first-order entailment is only semi-decidable.

Each conditional is defined only when the event it conditions on has positive probability ($P(B)>0$ for $P(A\mid B)$).

Sum over every value of each variable being removed.

Requires $P(B)>0$. Turns a likelihood $P(B\mid A)$ into a posterior $P(A\mid B)$; the denominator comes from marginalisation.

Requires $P(e)>0$. Compute the unnormalised values $P(x,e)$ for each $x$, then divide by their sum. $\alpha$ is just $1/P(e)$.

Holds for any distribution and any variable ordering (wherever the conditionals are defined); it is the starting point for the Bayesian-network factorisation.

Must hold for every pair of values of $A$ and $B$; the last form is for values with $P(B)>0$.

Must hold for every value of $A$, $B$ and $C$ with $P(C)>0$ (and $P(B,C)>0$ for the last form).

For any choice of CPTs this product is a valid joint distribution, and a joint factorises this way exactly when it satisfies the local Markov property for the DAG. Any joint entry is the product of one CPT entry per node.

For all-binary variables this is ${\sum }_i{2}^{|\mathrm{Pa}(X_i)|}$, compared with $2^n-1$ for the full joint.

Parents, children and the children's other parents (co-parents). Given its Markov blanket, $X$ is conditionally independent of every other variable in the network.

Sum the network's joint over all hidden-variable assignments with evidence fixed, then normalise ($P(e)>0$). Cost is exponential in the number of hidden variables.

Multiply only the factors that mention $X$, then sum $X$ out; factors not mentioning $X$ are left untouched and can be pulled outside the sum.

Each sample is drawn from the full joint, ignoring evidence; $N(\cdot )$ counts matching samples out of $N$.

Generate prior samples, discard any that disagree with the evidence, and use the counts among the kept ones (undefined if $N(e)=0$). The fraction kept is about $P(e)$, so rare evidence wastes almost all samples.

Evidence variables are fixed, not sampled; each sample is weighted by the probability of the evidence given its parents' values in that same sample (a parent may itself be an evidence variable, fixed at its observed value). Non-evidence variables are sampled as usual, so no sample is rejected. The method is consistent because the probability of drawing the non-evidence values $z$ times the weight equals $P(z,e)$.

All other variables are held at their current values; $\alpha$ normalises over the values $x_i$. Only the CPTs of $X_i$ and of its children are needed, because $X_i$ is independent of everything else given its Markov blanket.