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
- $P r [cavity ∣ 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

$P r [E]$ = Probability of an event $E$
$0 \leq P r [E] \leq 1$ , and $\sum_{e_{i} \in E} P r [e_{i}] = 1$
$P r [\neg E] = 1 - P r [E]$
$P r [A \lor B] = P r [A] + P r [B] - P r [A \land B]$
Pr[A∧B]=Pr[A,B]=Pr[B]⋅Pr[A∣B]=Pr[A]⋅Pr[B∣A] (joint probability; product rule) ^[1]
- $P r [B]$ is prior probability, and
- $P r [A ∣ 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. $P r [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. $P r [catch, toothache] = 0.108 + 0.016 = 0.124$ )
3. Calculate Conditionals (e.g. $P r [cavity ∣ (catch \land toothache)] = \frac{P r [cavity, catch, toothache]}{P r [catch, 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; $P r [A ∣ B] + P r [\neg A ∣ B] = 1$ , so $\frac{P r [A, B]}{P r [B]} + \frac{P r [\neg A, B]}{P r [B]} = \frac{1}{P r [B]} (P r [A, B] + P r [\neg A, B]) = 1$; Normalization constant $α = \frac{1}{P r [B]}$

In Practice

We can find

$P r [cavity] = 0.2$
$P r [toothache ∣ cavity] = 0.6$
$P r [catch ∣ cavity] = 0.9$

We have conditional probabilities as causal relationships, but we want them as diagnostic relationships: $P r [cavity ∣ toothache]$

We use Bayes' Rule for this: $P r [cavity ∣ toothache] = \frac{P r [toothache ∣ cavity] \cdot P r [cavity]}{P r [toothache]}$

Bayes' Rule

P r [A ∣ B] = \frac{P r [B ∣ A] \cdot P r [A]}{P r [B]}

Proof

From product rule, we have $P r [A, B] = P r [A ∣ B] \cdot P r [B] = P r [B ∣ A] \cdot P r [A]$

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

$P r [A ∣ B] = \frac{P r [B ∣ A] \cdot P r [A]}{P r [B]}$

Q.E.D.

Conditional Independence Assumption

P r [(A, B) ∣ C] = P r [A ∣ C] \cdot P r [B ∣ C]

Footnotes

↑ $P r [A \land B] \neq P r [A] \cdot P r [B]$ (Depends on correlation)

[1] $P r [A \land B] \neq P r [A] \cdot P r [B]$ (Depends on correlation)

[1]

CSCE 420 Lecture 22

Contents

Probability

Definitions and Axioms

Interpretations

Example

In Practice

Bayes' Rule

Proof

Conditional Independence Assumption

Footnotes

Navigation menu

CSCE 420 Lecture 22

Probability

Definitions and Axioms

Interpretations

Example

In Practice

Bayes' Rule

Proof

Conditional Independence Assumption

Footnotes

Navigation menu

Search