Review of Probability Theory
Overview
Probability is an important aspect of machine learning, and forms a useful basis for concepts. It is the study of uncertainty
Elements of Probability
Defining probability on a set requires the following:
Sample Space : $\Omega$
- The set of all possible outcomes of a random experiment
- Each outcome $\omega \in \Omega$ is the complete description of the state at the end of the experiment
Event Space (Set of events) : $\mathcal{F}$
- A set whose elements $A \in \mathcal{F}$ (events) are subsets of $\Omega$
- Eg: $A$ is the set of possible outcomes for an experiment
Probability Measure : $P : \mathcal F \rightarrow \mathbb R$ which satisfies the Axioms of Probability
- $P(A) \geq 0$ for all $A \in \mathcal F$
- $P(\Omega) = 1$
- If $A_1, A_2, \dots$ are disjoint events
$P(\cup_i A_i) = \sum_i P(A_i)$
Conditional Probability
For an event $B$ with non-zero probability
The conditional probability of $A$ given $B$ is $$ P(A|B) \triangleq \frac{P (A \cap B)}{P(B)} $$
Independence
If and only if
- $P(A \cap B) = P(A) P(B)$
- $P(A|B) = P(A)$
Random Variables
A function $X : \Omega \rightarrow \mathbb R$ that maps a sample space to a real-valued outcome
Cumulative Distribution Functions (CDF)
Function $F_X : \mathbb R \rightarrow [0,1]$ that calculates the probability of an event $$ F_X(x) \triangleq P(X \leq x) $$ Properties
- $0 \leq F_X(x) \leq 1$
- $\underset{x \rightarrow -\infty}{\lim} F_X(x) = 0$
- $\underset{x \rightarrow \infty}{\lim} F_X(x) = 1$
- $x \leq y \implies F_X(x) \leq F_Y(y)$
Probability Mass Function (PMF)
Function $p_X : \Omega \rightarrow \mathbb R$ that directly specifies the probability of each value for a discrete RV $$ p_X(x) \triangleq P(X=x) $$ Properties
- $0 \leq p_X(x) \leq 1$
- $\underset{x\in Val(X)}{\sum} p_X(x) = 1$
- $\underset{x\in A}{\sum} p_X(x) = P(X\in A)$
Probability Density Functions (PDF)
Derivative of the CDF $$ f_X(x) \triangleq \frac{dF_X(x)}{dx} $$ If the CDF is differentiable everywhere
Properties
- $f_X(x) \geq 0$
- $\int_{-\infty}^{\infty} f_X(x) = 1$
- $\int_{x\in A} f_X(x) dx = P(X \in A)$
Expectation
The “weighted average” of the values that a distribution can take
Discrete RV $$ E[g(X)] \triangleq \sum_{x\in Val(A)} g(x) p_X(x) $$ Continuous RV $$ E[g(X)] \triangleq \int_{-\infty}^{\infty} g(x) f_X(x)\ dx $$ Properties
- $E[a] = a$ for any constant $a$
- $E[a f(X)] = aE[f(X)]$ for any constant $a$
- (Linearity of Expectation)
$E[f(X) + g(X)] = E[f(X)] + E[g(X)]$ - For discrete RV
$E[1{ X=k }] = P(X = k)$
Variance
Measure of how concentrated a distribution is around it’s mean $$ Var[X] \triangleq E[(X - E(X))^2] $$ or equivalently $$ Var[x] = E[X^2] - E[X]^2 $$ Properties
- $Var[a] = 0$ for any constant $a$
- $Var[a f(X)] = a^2 Var[f(X)]$ for any constant $a$
Common Random Variables
Discrete
Bernoulli
Event happens with probability $p$ $$ p(x) = \left\{ \begin{aligned} &p && \text{if } p = 1 \cr &1-p && \text{if } p = 0 \end{aligned} \right. $$ Binomial
Number of outcomes in $n$ independent events $$ p(x) = \begin{pmatrix} n \cr x \end{pmatrix} p^x (1-p^{n-x}) $$ Geometric
Number of independent events until outcome is true $$ p(x) = p (1-p)^{x-1} $$ Poisson
Probability distribution over nonnegative integers $$ p(x) = e^{-\lambda} \frac{\lambda^x}{x!} $$
Continuous
Uniform
Equal probability density to every value between $a$ and $b$ $$ f(x) = \left\{ \begin{aligned} &\frac{1}{b-a} && \text{if } a\leq x \leq b \cr &0 && \text{otherwise} \end{aligned} \right. $$
Exponential
Decaying probability density over nonnegative reals $$ f(x) = \left\{ \begin{aligned} &\lambda e^{-\lambda x} && \text{if } x\geq 0 \cr &0 && \text{otherwise} \end{aligned} \right. $$ Normal
Gaussian distribution $$ f(x) = \frac{1}{\sqrt{2\pi}\sigma} \exp \left( -\frac{1}{2\sigma^2}(x-\mu)^2 \right) $$
Joint and Marginal Distributions
CDF
Of $X$ and $Y$ $$ F_{XY}(x,y) = P(X \leq x, Y \leq y) $$ The joint CDF is related to the marginal CDF $F_X(x) / F_Y(y)$ via $$ \begin{aligned} F_X(x) &= \lim_{y \rightarrow \infty} F_{XY}(x,y) dy \cr F_Y(y) &= \lim_{x \rightarrow \infty} F_{XY}(x,y) dx \end{aligned} $$ Properties
- $0 \leq F_{XY}(x,y) \leq 1$
- $\lim_{x,y \rightarrow \infty} F_{XY}(x,y) = 1$
- $\lim_{x,y \rightarrow -\infty} F_{XY}(x,y) = 0$
- $F_X(x) = \lim_{y \rightarrow \infty} F_{XY}(x,y)$
PMF
$$ p_{XY}(x,y) = P(X=x, Y=y) $$
And is related to the marginal PMF via $$ \begin{aligned} p_X(x) &= \sum_y p_XY(x,y) \cr p_Y(y) &= \sum_x p_XY(x,y) \end{aligned} $$
$$ f_{XY}(x,y) = \frac {\partial^2 F_{XY}(x,y)} {\partial x \partial y} $$
Where $$ \begin{aligned} \iint_{x\in A} f_XY(x,y)\ dx\ dy = P((X,Y) \in A) \cr \end{aligned} $$ And $$ \begin{aligned} f_X(x) = \int_{-\infty}^{\infty} f_{XY}(x,y) dy \cr f_Y(y) = \int_{-\infty}^{\infty} f_{XY}(x,y) dx \end{aligned} $$
Conditional Distribution
What is the probability distribution over $Y$ given that we know $X = x$?
Discrete $$ p_{Y|X} (y|x) = \frac{p_{XY}(x,y)}{p_X(x)} $$ Continuous $$ f_{Y|X} (y|x) = \frac{f_{XY}(x,y)}{f_X(x)} $$
Bayes’s Rule
Used to derive conditional probability of one variable given another $$ P(A|B)\ P(B) = P(B|A)\ P(A) $$ And therefore $$ P(A|B) = \frac{ P(B|A)\ P(A) }{ P(B) } $$
Independence
Two RVs $X$ and $Y$ are independent if $$ P(X,Y) = P(X)\ P(Y) $$ for all values of $x$ and $y$
Expectation and Covariance
Let $X$ and $Y$ be RVs and $g : \mathbb{R}^2 \rightarrow \mathbb R$
Expectation
Discrete $$ E{g(X,Y)} \triangleq \sum_{x \in Val(X)} \sum_{y \in Val(Y)} g(x,y) p_{XY}(x,y) $$ Continuous $$ E[g(X,Y)] = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} g(x,y) f_{XY}(x,y)\ dx\ dy $$
Convariance
$$ \begin{aligned} Cov[X,Y] &\triangleq E[(X-E[X])(Y-E(Y))] \cr &= E[XY] - E[X] E[Y] \end{aligned} $$
Uncorrelated : $Cov[X,Y] = 0$
Properties
- (Linearity of Expectation)
- $Var[X+Y] = Var[ X ] + Var[Y] + 2 Cov[X,Y]$
- If $X$ and $Y$ independent
$\implies E[f(X)g(Y)] = E[f(X)]\ E[g(Y)]$
Multiple RV
The notation for two RVs can be generalised to $n$ RVs
Properties
Chain Rule
$$ f(x_1, x_2, \dots, x_n) = f(x_1) f(x_2 | x_1) \prod_{i=3}^{n} f(x_i | x_1, \dots, x_{i-1}) $$
Independence
Events $A_1, \dots, A_k$ are mutually independent if $$ P(\underset{i \in S}{\cap} A_i) = \prod_{i\in S} P(A_i) $$ Random variables $X_1, \dots, X_n$ are independent if $$ f(x_1, \dots, x_n) = f(x_1) f(x_2) \dots f(x_n) $$
Random Vectors
A vector of random variables is a random vector
It is a mapping from $\Omega \rightarrow \mathbb R^n$
It is an alternative notation for multiple RVs $$ X = \begin{bmatrix} X_1 \cr \vdots \cr X_n \end{bmatrix} $$
Expectation
$$ E[g(X)] = \begin{bmatrix} E[g_1(X)] \cr \vdots \cr E[g_m(X)] \end{bmatrix} $$
Covariance
$$ \Sigma = \begin{bmatrix} E[X_1^2] & \dots & E[X_1 X_n] \cr \vdots & \ddots & \vdots \cr E[X_n X_1] & \dots & E[X_n^2] \end{bmatrix} $$
or $$ \begin{aligned} \Sigma &= E[XX^T] - E[X]\ E[X]^T \cr &= E[(X-E[X])(X-E[X])^T] \end{aligned} $$
Properties
- Positive semidefinite : $\Sigma \succeq 0$
- Symmetric : $\Sigma = \Sigma^T$
Multivariate Gaussian Distribution
Particularly important example
Has a
Mean : $\mu \in \mathbb R^n$
Covariance : $\Sigma \in \mathbb S_{++}^n$ (symmetric positive definite matrices) $$ f_{X_1, \dots, X_n} (x_1, \dots, x_n; \mu, \Sigma) = \frac{1}{(2\pi)^{\pi/2} |\Sigma|^{1/2} } \exp \left( -\frac{1}{2} (x-\mu)^T \Sigma^{-1} (x-\mu) \right) $$ Written as $X \sim \mathcal N(\mu, \Sigma)$
Usefulness
Comes up extremely often due to the Central Limit Theorem (CLT) - A large number of independent RVs will tend toward a Gaussian distribution.
Useful because it has simple closed-form solutions.