Lecture 11. Logic and probability

Slides

∀I

Logical methods for AI

Lecture 11

Logic and probability

This work is licensed under CC BY 4.0

https://forms.gle/JiXXM9eysAZaJMja9

Logic and probability

Concepts

So far: deductive logic
Deductive validity: premisses necessitate conclusion
Now: inductive logic
Inductive validity: premisses make conclusion (more) likely

Models of probability

Background

Probability of $E$: how likely is $E$
Interpretations of probability

Objectivists: objective chance
Subjectivists: subjective degree of belief

Probabilities

A function $Pr:\mathcal{L}\to\mathbb{R}$, s.t.:

$Pr(A)\geq 0$
$Pr(A)=1$, if $\vDash A$
$Pr(A\lor B)=Pr(A)+Pr(B)$, whenever $\vDash\neg(A\land B)$

Laws

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

$\vDash \neg(A\land \neg A)$
$Pr(A\lor\neg A)=Pr(A)+Pr(\neg A)$
$\vDash A\lor\neg A$
$Pr(A\lor\neg A)=1$
$1=Pr(A)+Pr(\neg A)$

Fair die

$$Pr(\mathsf{RESULT}_i)=\frac{1}{6}\text{, for }i=1,\dots,6$$ $$Pr(\mathsf{RESULT}_i\land \mathsf{RESULT}_j)=0\text{, for all }i\neqj$$

Calculation

$$Pr(\mathsf{R}_2\lor \mathsf{R}_4)=\frac{1}{3}$$

Inclusion-exclusion $$Pr(A\lor B)=Pr(A)+Pr(B)-Pr(A\land B)$$
Calculation: $$Pr(\mathsf{R}_2\lor \mathsf{R}_4)=Pr(\mathsf{R}_2)+Pr(\mathsf{R}_4)-Pr(\mathsf{R}_2\land \mathsf{R}_4)$$ $$=\frac{1}{6}+\frac{1}{6}-0$$
Probabilities are not recursive.

Probability truth-tables

Example

$$\langle prop\rangle::=\mathsf{RAIN}\mid\mathsf{SUN}$$

$\nu_1(\mathsf{RAIN})=1$ and $\nu_1(\mathsf{SUN})=1$
$\nu_2(\mathsf{RAIN})=1$ and $\nu_2(\mathsf{SUN})=0$
$\nu_3(\mathsf{RAIN})=0$ and $\nu_3(\mathsf{SUN})=1$
$\nu_4(\mathsf{RAIN})=0$ and $\nu_4(\mathsf{SUN})=0$

Weights

$\nu_1(\mathsf{RAIN})=1$ and $\nu_1(\mathsf{SUN})=1$: $m(\nu_1)=0.5$
$\nu_2(\mathsf{RAIN})=1$ and $\nu_2(\mathsf{SUN})=0$: $m(\nu_2)=0.3$
$\nu_3(\mathsf{RAIN})=0$ and $\nu_3(\mathsf{SUN})=1$: $m(\nu_3)=0.2$
$\nu_4(\mathsf{RAIN})=0$ and $\nu_4(\mathsf{SUN})=0$: $m(\nu_4)=0$

$$Pr(\mathsf{RAIN})=\sum_{\nu(\mathsf{RAIN})=1}m(\nu)=$$ $$m(\nu_1)+m(\nu_2)=0.5+0.3=0.8$$

Tables

Example

$$Pr(\mathsf{RAIN}\lor\neg\mathsf{SUN})=m(\nu_1)+m(\nu_2)+m(\nu_4)=0.5+0.3+0=0.8$$

Dice

Conditional probabilities

Formula

$$Pr(A\mid B)=\frac{Pr(A\land B)}{Pr(B)}$$

$$Pr(\mathsf{RAIN}\land\mathsf{SUN})=0.5\qquad Pr(\mathsf{SUN})=0.5+0.2=0.7$$ $$\mathsf{Pr}(\mathsf{RAIN}\mid\mathsf{SUN})=\frac{0.5}{0.7}\approx 0.71$$

$$Pr(\mathsf{R}_2\lor\mathsf{R}_4\lor\mathsf{R}_6)=\frac{1}{6}+\frac{1}{6}+\frac{1}{6}=\frac{1}{2}\quad Pr(\mathsf{R}_2\land (\mathsf{R}_2\lor\mathsf{R}_4\lor\mathsf{R}_6))=\frac{1}{6}$$ $$Pr(\mathsf{R}_2\mid \mathsf{R}_2\lor\mathsf{R}_4\lor\mathsf{R}_6 )=\frac{\frac{1}{6}}{\frac{1}{2}}=\frac{1}{3}$$

Conjunction

$$Pr(A\land B)=Pr(A\mid B)P(B)$$

Still not recursive!

Independence

$$A,B\text{ are independent}\Leftrightarrow Pr(A\mid B)=Pr(A)$$

For $A,B$ independent: $Pr(A\land B)=Pr(A)\times Pr(B)$

$$Pr(\mathsf{SUN}\mid\mathsf{RAIN})=\frac{Pr(\mathsf{SUN}\land\mathsf{RAIN})}{Pr(\mathsf{RAIN})}$$ $$=\frac{0.5}{0.5+0.3=0.8}=0.625=0.5+0.125=Pr(\mathsf{SUN})$$

Inductive validity

Background

Related to statistical inference.
Not as standardized, much variety.
Bayesian inference.

Increase of firmness

$$ P_1,P_2,\dots\mid\approx_{Pr} C \Leftrightarrow Pr(C|P_1\land P_2\land \dots)\geq Pr(C)$$

Strong inference

$$ P_1,P_2,\dots\mid\overset{!}{\approx} C \Leftrightarrow Pr(C|P_1\land P_2\land\dots)\gg Pr(C),$$

Alt: Threshold view

$$ P_1,P_2,\dots\mid\overset{!}{\approx} C \Leftrightarrow Pr(C|P_1\land P_2\land \dots)\geq \epsilon>0.5.$$

Explosion?

Undefined if $Pr(B)=0$
What to do?
Options:

Explosion $\Rightarrow$ $Pr(A\mid B)=1$
Caution $\Rightarrow$ $Pr(A\mid B)=0$

Inductive Laws 1

If $P_1,P_2,\dots\vDash C$, then $P_1,P_2,\dots\mid\approx C$.

Inductive Laws 2

$C\vDash P_1\land P_2\land \dots\Rightarrow P_1\land P_2\land \dots\mid\approx C$
DN-model
Important!!

Inductive (in)validities

Enumerative induction

All observed swans are white. So all swans are white.
$P(a_1),P(a_2),\dots\mid\overset{!}{\approx}\forall xP(x)$
Theorem!

Linda

Linda is 31 years old, single, outspoken, and very bright. She majored in philosophy. As a student, she was deeply concerned with issues of discrimination and social justice, and also participated in anti-nuclear demonstrations. Which is more probable?

Linda is a bank teller.

Linda is a bank teller and is active in the feminist movement.

$$\mathsf{BANK}\land\mathsf{FEMINIST}\vDash\mathsf{BANK}$$ $$\Rightarrow$$ $$Pr(\mathsf{BANK}\land\mathsf{FEMINIST})\leq Pr(\mathsf{BANK})$$