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
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pr[E]} = Probability of an event $E$
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \le Pr[E] \le 1} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{e_i \in E} Pr[e_i] = 1}
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pr[\neg E] = 1 - Pr[E]}
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pr[A \vee B] = Pr[A] + Pr[B] - Pr[A \wedge B]}
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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)
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pr[B]} is prior probability, and
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pr[\text{catch},\text{toothache}] = 0.108 + 0.016 = 0.124} )
  3. Calculate Conditionals (e.g. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pr[A \mid B] + Pr[\neg A \mid B] = 1} , so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha = \frac{1}{Pr[B]}}

In Practice

We can find

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pr[\text{cavity}] = 0.2}
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pr[\text{toothache} \mid \text{cavity}] = 0.6}
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pr[\text{catch} \mid \text{cavity}] = 0.9}

We have conditional probabilities as causal relationships, but we want them as diagnostic relationships: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pr[\text{cavity} \mid \text{toothache}]}

• We use Bayes' Rule for this: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pr[\text{cavity} \mid \text{toothache}] = \frac{Pr[\text{toothache} \mid \text{cavity}] \cdot Pr[\text{cavity}]}{Pr[\text{toothache}]}}

Bayes' Rule

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pr[A \mid B] = \frac{Pr[B \mid A] \cdot Pr[A]}{Pr[B]}}

Proof

From product rule, we have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pr[A \mid B] = \frac{Pr[B \mid A] \cdot Pr[A]}{Pr[B]}}

Q.E.D.

Conditional Independence Assumption

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pr[(A,B) \mid C] = Pr[A \mid C] \cdot Pr[B \mid C]}