No notes for first lecture part of lecture video.

Probability Basics

Sample space

The sample space, $S/\Omega$, of the experiment is the set of all possible outcomes $$ S/\Omega = \{ s_1, s_2, ..., s_n \} $$

Link to original

Probability space

$\omega \in \Omega$ is a sample point (atomic event)

A probability space is a sample space with an assignment $P(\omega )$ for every $\omega \in \Omega$ such that:

$$\begin{array}{rl}0\le P(\omega )& \le 1\\ \sum _{\omega }P(w)& =1\end{array}$$Link to original

Event

An event is a subset of the [[Sample space|sample space]], or otherwise a set of possible outcomes.

$$P(A)=\sum _{\{\omega \in A\}}P(\omega )$$ Link to original

Random Variable

A random variable on $S$ is a measurement of a random outcome $s\in S$.

The probability that a random variable $X$ takes the value $k\in \mathbb{R}$ is given by:

$$\text{Prob}(X=k)=\text{Prob}(\{s\in S:X(s)=k\})$$

It follows similarly that:

$$\begin{array}{c}\text{Prob}(X\le k)=\text{Prob}(\{s\in S:X(s)\le k\})\\ \text{Prob}(X\ge k)=\text{Prob}(\{s\in S:X(s)\ge k\})\end{array}$$Link to original

Propositions

Proposition

A proposition is a **declarative sentence** of which we can meaningfully ask whether it is true $(T)$ or false $(F)$.

Sample syntax:

• Propositional / boolean random variables: $\text{Cavity = true}\mapsto \text{cavity}$ $\text{Cavity = false}\mapsto \neg \text{cavity}$
• Discrete random variables (finite or infinite) Given $\text{Weather}$ is one of $\{sunny,rain,cloudy,snow\}$ "$\text{Weather}=rain$" is a proposition
• Continuous random variables (bounded or unbounded) $\text{Temp}=21.6$; $\text{Temp}<22.0$; $\text{Temp}\ge 5.0\text{ AND }\text{Temp}\le 23.0$

Link to original

Conditional probability

The conditional probability of event $a$ given another event $b$ occurs is $$ P(a\vert b) = \frac{p(a \land b)}{p(b)} \text{ if } p(b) > 0$$

Link to original

Probability distribution

A probability distribution in the sample space $S$ is a function $p$ assigning a number $p(s_i)$ to each possible outcome $s_i$ in $S$ (the probability of $s_i$), such that:

• values are exhaustive (cover everything)
• values are mutually exclusive (no overlap)
• $0\le p(s_i)\le 1$, for all $i=1\text{ to }n$
• $p(s_1)+p(s_2)+...+p(s_n)=1$ All probability values add up to $1$.

$$P(\text{Weather})=\left(\begin{array}{c}0.72\\ 0.1\\ 0.08\\ 0.1\end{array}\right)=⟨0.72,0.1,0.08,0.1⟩$$

This means, for example: $P(\text{Weather}=sunny)=0.72$.

Link to original

Joint Probabilities

Joint probability distribution

Joint probability distribution for a set of random variables gives the probability of every atomic event on those random variables (every sample point).

$P(\text{Cavity},\text{Weather})$ is a $2\times 4$ matrix of values

$$\left(\begin{array}{cccc}0.144& 0.02& 0.016& 0.02\\ 0.576& 0.08& 0.064& 0.08\end{array}\right)$$

Which is interpreted as:

	$W=sunny$	$W=rain$	$W=cloudy$	$W=snow$
$C=true$	$0.144$	$0.02$	$0.016$	$0.02$
$C=false$	$0.576$	$0.08$	$0.064$	$0.08$

Link to original

Conditional Probability

Conditional probability

The conditional probability of event $a$ given another event $b$ occurs is $$ P(a\vert b) = \frac{p(a \land b)}{p(b)} \text{ if } p(b) > 0$$

Link to original

Joint probability distribution using conditional probability

We can use the product rule to formulate conditional probability in the form:

$$P(a\wedge b)=P(a|b)P(b)=P(b|a)P(a)$$

A general version holds for joint distributions:

$$P(\text{Weather},\text{Cavity})=P(\text{Weather}|\text{Cavity})\cdot P(\text{Cavity})$$

(we interpret this as $4\cdot 2=8$ set of equations, not using matrix math)

Link to original

Chain Rule

Chain Rule (probabilities)

Chain rule is successive application of the product rule:

$$\begin{array}{rl}P(a,b,c)& =P(a,b)P(c|a,b)\\ & =P(a)P(b|a)P(c|a,b)\end{array}$$

In general:

$$\begin{array}{rl}P(X_1,\dots ,X_n)& =P(X_1,\dots ,X_{n-1})P(X_n|X_1,\dots ,X_{n-1})\\ & =P(x_1,\dots ,X_{n-2})P(X_{n-1}|X_1,\dots ,X_{n-2})P(x_n|X_1,\dots ,X_{n-1})\\ & =\dots \\ & =\prod _{i=1}^{n}P(X_i|X_1,\dots ,X_{i-1})\end{array}$$Link to original

How to compute posterior joint distribution? (inference by enumeration)

Let $X$ be all of the variables. We want to find the posterior joint distribution of the query variables $Y$ given specific values $e$ for the evidence variables $E$. Let the hidden variables be $H=X-Y-E$.

Then, the required summation of joint entries is done by summing out hidden variables:

The terms in the summation are joint entries because $Y$, $E$, and $H$ together exhaust the set of random variables.

Normalisation

Normalisation (probabilities)

We can use $\alpha =1/P(\text{toothache})$ (calculation not necessary) to normalise the following:

$$\begin{array}{rl}P(\text{Cavity}|\text{toothache})& =\alpha P(\text{Cavity},\text{toothache})\\ & =\alpha [P(\text{Cavity},\text{toothache},\text{catch}),P(\text{Cavity},\text{toothache},\neg \text{catch})]\\ & =\alpha \left[\begin{array}{c}\left(\begin{array}{c}0.108\\ 0.016\end{array}\right)+\left(\begin{array}{c}0.012\\ 0.064\end{array}\right)\end{array}\right]\\ & =\left(\begin{array}{c}0.12\\ 0.08\end{array}\right)\\ & =\left(\begin{array}{c}0.6\\ 0.4\end{array}\right)\end{array}$$

The source of these numbers is from the follow joint distribution table:

	$toothache$		$\neg toothache$
	$catch$	$\neg catch$	$catch$	$\neg catch$
$cavity$	$0.108$	$0.012$	$0.072$	$0.008$
$\neg cavity$	$0.016$	$0.064$	$0.144$	$0.576$

Link to original

Independence and Conditional Independence

Preamble

We saw with joint distribution tables that we can calculate any probability, but this has multiple problems such as:

• Worst-case time complexity is $O(d^n)$ where $d$ is the largest arity
• Space complexity $O(d^n)$ to store the joint distribution
• We must find numbers for $O(d^n)$ entries

To get efficient probabilistic computations, we need:

1. (Conditional) independence
2. Bayes rule

Independence

Two events $E$ and $F$ are said to be independent if the occurrence of one of the events gives no information about the probability of the other event. $$ \boxed{p(E | F) = p(E)} \text{ or } \boxed{p(F | E) = p(F)} $$

Using conditional probability, we can obtain that $E$ and $F$ are independent events whenever $p(E\cap F)=$ $p(E) \cdot p(F)$.

Link to original

Decomposing variables

If we have the variables Cavity, Toothache, Catch, Weather:

• We may store them naively, requiring $2\cdot 2\cdot 2\cdot 4=32\text{ entries}$
• We may decompose them into two independent groups of Cavity, Toothache, Catch and Weather, now we can reduce the $31$ values to $10$.

For $n$ independent biased coins, $2^n\to n$.

Conditional Independence

We say $A$ is conditionally independent of $B$ given $C$:

$$P(A|B,C)=P(A|C)$$

We write this as $A\perp \perp B|C$.

Link to original

Bayes’ Rule

Bayes' Rule

Bayes’ Rule provides the probability hypothesis h is true given that some event e has occurred.

$$P(h|e)=\frac{P(e|h)P(h)}{P(e)}$$Link to original

Bayes' Theorem

Bayes’ Theorem states that $$ p(F | E) = \frac{p(E|F)p(F)}{p(E|F)p(F) + p(E|\bar F)p(\bar F)} $$

Short form: $P(A|B)=\frac{P(B|A)\cdot P(A)}{P(B)}$

Link to original

When do we use Bayes’ Theorem?

• $E$ and $F$ are events from the same sample space $S$.
• We can easily compute $p(E|F)$ but we want $p(F|E)$.
• Often easier to access causal probabilities: $$P(\text{Cause}|\text{Effect})=\frac{P(\text{Effect}|\text{Cause})P(\text{Cause})}{P(\text{Effect})}$$ Visualised as:

  graph LR
  	Cause-->Effect