Search and Probabilistic Reasoning

Bayesian network conditional independence

A Bayesian network is a directed acyclic graph whose nodes are random variables, and its joint distribution factorizes as P(X_1,\dots,X_n)=\prod_{i}P(X_i \mid \mathrm{Pa}(X_i)), where \mathrm{Pa}(X_i) is the set of parents of X_i. Each factor is a conditional probability table (CPT), so the probability of a full assignment is found by multiplying one CPT entry per variable. For example, if P(A=1)=0.3 and P(B=1 \mid A=1)=0.8, then P(A=1,B=1)=0.3 \times 0.8=0.24.

Conditional independence is read from the graph structure rather than from the numbers. Every variable is independent of its non-descendants given its parents, and other independence statements follow from d-separation. Three basic three-node patterns are the building blocks.

• Chain A \to B \to C and fork A \leftarrow B \rightarrow C: observing the middle node blocks the path, so A \perp C \mid B.
• Collider (v-structure) A \to B \leftarrow C: A and C are marginally independent, but observing B or a descendant of B makes them dependent. This is called explaining away.

When two parents feed a common child, conditioning on that child generally creates dependence between the parents, even if they were independent before. Check this by reading the factorization: if P(A,B,C)=P(A)P(B \mid A)P(C \mid B), then C depends on A only through B, so A \perp C \mid B.

Inference asks for a query probability such as P(\text{query}\mid\text{evidence}). Variable elimination is an exact method: it multiplies the relevant factors and sums out hidden variables one at a time, so the answer has no sampling error, although its cost can grow exponentially with the network's treewidth. Sampling methods are approximate. Rejection sampling draws samples from the network, discards those that disagree with the evidence, and estimates the query from the rest. Gibbs sampling is a Markov chain Monte Carlo method that resamples one non-evidence variable at a time, and it approximates the posterior only in the limit of many iterations.

Alpha-beta pruning

Alpha-beta pruning is a modification of minimax search that returns exactly the same root value while skipping branches that cannot change the decision. Two bounds are passed down the search. \alpha is the best (highest) value that MAX can already guarantee along the current path, and \beta is the best (lowest) value that MIN can already guarantee along that path. They start at \alpha=-\infty and \beta=+\infty. A MAX node raises \alpha to the largest value found among its children, and a MIN node lowers \beta to the smallest.

• Alpha (α): the highest lower bound for MAX on the path; it never decreases.
• Beta (β): the lowest upper bound for MIN on the path; it never increases.

Pruning occurs when \alpha \ge \beta at a node, so the remaining children need not be examined. For example, suppose MAX already has \alpha=5 from an earlier branch. A MIN node whose first leaf is 3 sets \beta=3. Since \alpha \ge \beta, the rest of that MIN node's children are pruned, because MIN can return at most 3, which MAX would never prefer to 5. Pruning can happen at any depth of the tree, and its effectiveness depends on move ordering.

Applying the condition to a specific tree means tracking the bound carried from one subtree to the next. A MIN node whose left leaf is x, under a MAX ancestor that already has \alpha = 2 from a sibling subtree, prunes its right child exactly when x \le 2. When the bound comes from a MIN subtree whose value is the minimum of its leaves, the cutoff requires \min(\cdots)\ge\beta, which holds only if every leaf in that subtree is at least \beta. This turns the cutoff into an inequality on the unknown leaf value.

Alpha-beta preserves the minimax rule. A MIN node takes the minimum of its children's values, a MAX node takes the maximum, and a leaf returns its utility. For example, a MAX root with three moves whose MIN replies have leaf sets \{3,5\}, \{4,2\}, and \{7,1\} backs up the values 3, 2, and 1, so MAX chooses the first move. When a question asks for the best strategy as an integer, it refers to the label of the move with the largest backed-up value.

First-order logic quantifier translation

In first-order logic, a universal quantifier \forall x is normally paired with an implication, and an existential quantifier \exists x with a conjunction. For example, 'every dog is an animal' is \forall x\,(Dog(x)\Rightarrow Animal(x)), while 'some dog is brown' is \exists x\,(Dog(x)\wedge Brown(x)). Pairing \forall with a conjunction says that every object is both a dog and an animal, which is a much stronger and different claim.

A sentence with an exception is translated as two conditions, one for each group. 'Every student in the lab is off campus, and every student not in the lab is on campus' becomes \forall s\,(Lab(s)\Rightarrow\neg Campus(s)) \wedge \forall s\,(\neg Lab(s)\Rightarrow Campus(s)). A binary predicate such as Classmate is symmetric only if \forall x\,\forall y\,(R(x,y)\Rightarrow R(y,x)) is stated, and the meaning of the predicate name is what suggests this.

An implication is equivalent to its contrapositive: A\Rightarrow B \equiv \neg B\Rightarrow \neg A, and \neg A\Rightarrow B \equiv \neg B\Rightarrow A. So a sentence and its contrapositive can both be correct translations, and candidate formulas should be compared by their logical content rather than their surface form.