Probability and inductive logic

Logical methods for AI

Probability and inductive logic

Lecture 11

What you’ll be able to do

Next-token prediction

Each continuation has a probability.
The inference is probable, not certain.

Weighted truth-tables

Enable JavaScript to edit the probabilities and calculate with this table.

Probabilities

Examples:

Uniform, $14$ each: $Pr(SUN \lor \negRAIN) = 34$
Sun certain, $12$ on each sunny model: $Pr(SUN \lor \negRAIN) = 1$

Conditioning

$EVEN = D₂ \lor D₄ \lor D₆$ , $TWO = D₂$

Enable JavaScript to edit the probabilities and calculate with this table.

Conditional probability

Examples: $Pr(TWO | EVEN)$

Fair die: $13$
Six loaded to $12$ : $17$

Independence

Examples: $Pr(RAIN | SUN)$ and $Pr(RAIN)$

Uniform: $12 = 12$ , independent
Dependent: $13 < 38$ , sun lowers rain

Probability laws

Every weighted truth-table obeys them.
Finitely many variables: the converse holds.
Laws follow without a table, even in FOL.

Negation

$Pr(\negA) = 1 - Pr(A)$

Pr(A) + Pr(¬A) = Pr(A ∨ ¬A) – Additivity (axiom 3), read right to left: A and ¬A are logically incompatible.

Pr(A) + Pr(¬A) = 1 – Normalization (axiom 2): A ∨ ¬A is a tautology.

Pr(¬A) = 1 − Pr(A) – Subtract Pr(A) from both sides of line 2.

Disjunction

$Pr(A \lor B) = Pr(A) + Pr(B) - Pr(A \land B)$

Pr(B) = Pr(A ∧ B) + Pr(¬A ∧ B) – B is equivalent to (A ∧ B) ∨ (¬A ∧ B). Its two cases are incompatible, so apply axiom 3.

Pr(¬A ∧ B) = Pr(B) − Pr(A ∧ B) – Subtract Pr(A ∧ B) from both sides of line 1.

Pr(A ∨ B) = Pr(A) + Pr(¬A ∧ B) – A ∨ B is equivalent to A ∨ (¬A ∧ B). These two disjuncts are incompatible, so apply axiom 3.

Pr(A ∨ B) = Pr(A) + Pr(B) − Pr(A ∧ B) – Substitute the expression from line 2 into line 3.

Bayes’ rule

Turns $Pr(E | C)$ into $Pr(C | E)$ :

Prior (glossary, opens in a new tab) $Pr(C)$ : before the evidence
Likelihood (glossary, opens in a new tab) $Pr(E | C)$ : the evidence, if $C$
Posterior (glossary, opens in a new tab) $Pr(C | E)$ : after the evidence
Total probability (glossary, opens in a new tab) gives the denominator:

Pr(E) = Pr(E | C) \times Pr(C) + Pr(E | \negC) \times Pr(\negC)

Measures of support

Increase of firmness: $d(C, E) = Pr(C | E) - Pr(C)$
Log probability ratio: $r(C, E) = log(Pr(C | E) Pr(C))$
Log-likelihood ratio: $l(C, E) = log(Pr(E | C) Pr(E | \negC))$

Ratio above $1$ : $log > 0$ , support
Ratio $1$ : $log(1) = 0$ , irrelevance
Ratio below $1$ : $log < 0$ , counter-evidence

Comparing the measures

Enable JavaScript to edit the probabilities and calculate with this table.

Spam filters

Markers: $Unknown$ , $Urgent$ , $Exclamation$ , $Money$
Rule: $(Urgent \land Money) \to SPAM$
Jim’s birthday wishes: spam!

Naive Bayes classifiers

Score each class: $score(K) = Pr(K) \times \prod i = 1 n Pr(Lᵢ | K)$
Normalize: $Pr(SPAM | E) = score(SPAM) score(SPAM) + score(\negSPAM)$

A spam filter

Enable JavaScript to edit the probabilities and calculate with this table.

Logical inductive support

Confirmation by consequence

Example:

$TWO ⊨ EVEN$
$Pr(TWO | EVEN) = Pr(TWO) Pr(EVEN) \geq Pr(TWO)$
Fair die: from $16$ to $13$

Enumerative induction

Example: 100 marbles, each white with chance $12$

70 drawn, all white
Prior: $Pr(\forallx White(x)) = 2 -100$
Posterior: $Pr(\forallx White(x) | E) = 2 -30$
A huge increase, and still tiny.