CSCE 420 Lecture 22

« previous | Tuesday, April 9, 2013 | next »

Probability

Uncertainty in AI

Limitations of First-Order Logic: handling exceptions to the rules

• Universal rules

Most birds fly:

• Default Logic: bird(x)/flies(x) → flies(x)
• Strength of rules in expert systems = "certainty factors" people gave up on certainty factors in favor of probability
  • headache(x) →^0.1 meningitis(x)
  • toothache(x) →^0.6 cavity(x)
• Conditional Probability
  • $Pr[{\text{cavity}}\mid {\text{toothache}}]$ = 0.6 (read "probability of having a cavity given a toothache")

Applications

• Diagnosis in engineering systems
• Decision-making in uncertain environments
• "rational" decision-making: take action that maximizes expected (weighted by probability) outcome/payoff

Definitions and Axioms

• $Pr[E]$ = Probability of an event $E$
• $0\leq Pr[E]\leq 1$, and $\sum _{e_{i}\in E}Pr[e_{i}]=1$
• $Pr[\neg E]=1-Pr[E]$
• $Pr[A\vee B]=Pr[A]+Pr[B]-Pr[A\wedge B]$
• $Pr[A\wedge B]=Pr[A,B]=Pr[B]\cdot Pr[A\mid B]=Pr[A]\cdot Pr[B\mid A]$ (joint probability; product rule)
  • $Pr[B]$ is prior probability, and
  • $Pr[A\mid B]$ is the conditional probability

Interpretations

• Frequentist: (Objectivist, Empiricist) probabilities are estimates of outcomes of repeated experiments
• Subjective: beliefs and don't have to be tied to repeatable events
• Stochastic: Lazy (don't want to quantify all relevant factors); ignorance

Example

3 Vars:

• catch, cavity, and toothache
• JPT enumerates all possibilities (2³ for 3 binary variables) and their probability
• Calculations
  1. Calculate Priors (e.g. $Pr[{\text{cavity}}]=0.108+0.012+0.072+0.008=0.2$): sum of all cells that satisfy probability independent of other variables
  2. Calculate Joints (e.g. $Pr[{\text{catch}},{\text{toothache}}]=0.108+0.016=0.124$)
  3. Calculate Conditionals (e.g. $Pr[{\text{cavity}}\mid ({\text{catch}}\wedge {\text{toothache}})]={\frac {Pr[{\text{cavity}},{\text{catch}},{\text{toothache}}]}{Pr[{\text{catch}},{\text{toothache}}]}}={\frac {0.108}{0.124}}=0.871$

Joint Probability Table

	Toothache		¬Toothache
	Catch	¬Catch	Catch	¬Catch
Cavity	0.108	0.012	0.072	0.008
¬Cavity	0.016	0.064	0.144	0.576

Marginalization

"summing out" unknown variables

Normalization

Conditional probabilities are proportional to joint probabilities

$Pr[A\mid B]+Pr[\neg A\mid B]=1$, so ${\frac {Pr[A,B]}{Pr[B]}}+{\frac {Pr[\neg A,B]}{Pr[B]}}={\frac {1}{Pr[B]}}\,\left(Pr[A,B]+Pr[\neg A,B]\right)=1$

Normalization constant $\alpha ={\frac {1}{Pr[B]}}$

In Practice

We can find

• $Pr[{\text{cavity}}]=0.2$
• $Pr[{\text{toothache}}\mid {\text{cavity}}]=0.6$
• $Pr[{\text{catch}}\mid {\text{cavity}}]=0.9$

We have conditional probabilities as causal relationships, but we want them as diagnostic relationships: $Pr[{\text{cavity}}\mid {\text{toothache}}]$

• We use Bayes' Rule for this: $Pr[{\text{cavity}}\mid {\text{toothache}}]={\frac {Pr[{\text{toothache}}\mid {\text{cavity}}]\cdot Pr[{\text{cavity}}]}{Pr[{\text{toothache}}]}}$

Bayes' Rule

$Pr[A\mid B]={\frac {Pr[B\mid A]\cdot Pr[A]}{Pr[B]}}$

Proof

From product rule, we have $Pr[A,B]=Pr[A\mid B]\cdot Pr[B]=Pr[B\mid A]\cdot Pr[A]$

Take the second part of this equality and divide by B:

$Pr[A\mid B]={\frac {Pr[B\mid A]\cdot Pr[A]}{Pr[B]}}$

Q.E.D.

Conditional Independence Assumption

$Pr[(A,B)\mid C]=Pr[A\mid C]\cdot Pr[B\mid C]$