Example

The probability of rolling a 6 on a die given that an even number has rolled.

$P(6|\mathrm{even}) = \frac{P(\mathrm{even},\ 6)}{P(\mathrm{even})} = \frac13$

Symmetry: $$P(y|x)P(x) = P(x, y) = P(x|y)P(y)$$

\[ p(y|x)p(x) = p(x, y) = p(x|y)p(y) \Rightarrow \]

\[ \Rightarrow p(y|x) = \frac{p(x|y)p(y)}{p(x)} \]

\[ p(x) = \int p(x, y)dy = \int p(x|y)p(y)dy = E_y p(x|y)\]

Sum Rule:

\[p(x_1, \dots , x_k) = \int p(x_1, \dots , x_k, \dots , x_n)d{x_{k+1}} \dots d{x_n}\]

Product Rule:

\[ p(x_1, x_2, x_3, \dots , x_{n−1}, x_n) = p(x_1|x_2, x_3, \dots, x_{n−1}, x_n) \cdot \\ \cdot p(x_2|x_3, \dots, x_{n−1}, x_n) \cdot \ldots \cdot p(x_{n}) \]

\[ \begin{cases} p(y|x) = \frac{p(x|y)p(y)}{p(x)} \\ p(x) = \int p(x|y)p(y)dy \end{cases} \Rightarrow \] \[ p(y|x) = \frac{p(x|y)p(y)}{\int p(x|y)p(y)dy} \] \[ \mathrm{Posterior} = \frac{\mathrm{Likelihood}\cdot \mathrm{Prior}}{\mathrm{Evidence}} \]

Given:

• $x$ — student is (not) happy
• $y$ — exam is (not) passed
• $P(\text{exam is passed}) = 1/3$
• $P(\text{student is happy}|\text{exam is passed}) = 1$
• $P(\text{student is happy}|\text{exam is NOT passed}) = 1/6$

Find:

$P(y=1|x=1) = P(\mathrm{exam\ is\ passed}|\mathrm{student\ is\ happy})\ —\ ?$

\[ P(\text{exam is passed}|\text{student is happy}) = \\[0.1cm] = \frac{P(\text{student is happy}|\text{exam is passed})P(\text{exam is passed})}{P(\text{student is happy})} = \\[0.2cm] = \frac{P(\text{student is happy}|\text{exam is passed})P(\text{exam is passed})}{P(\cdot,\ \text{exam is passed}) + P(\cdot,\ \text{exam is NOT passed})} = \\[0.2cm] = \frac{P(\text{student is happy}|\text{exam is passed})P(\text{exam is passed})}{ P(\cdot|\cdot)P(\text{exam is passed}) + P(\cdot|\cdot)P(\text{exam is NOT passed}) } = \\[0.1cm] =\frac{\frac{1}{3}}{\frac{1}{3} + \frac{1}{6}\cdot\frac{2}{3}} = \frac{3}{4} \]

$$X = \{x_1, x_2, \dots, x_n\}, x_i \sim p(x|\theta)$$ $$\theta_{\text{MaxL}} = \arg\max\limits_\theta p(X|θ) {\color{orange}=} \arg\max\limits_\theta \prod\limits_{i=1}^n p(x_i|\theta) \\ = \arg\max\limits_\theta \sum\limits_{i=1}^n \log p(x_i|\theta)$$

• MaxL estimate is consistent: $$\theta_{\text{MaxL}} \overset{p}{\to} \theta_{\text{ground truth}}$$
• Asymptotically efficient: there is no consistent estimate that improves mean-square error as $n \to \infty$
• Asymptotically normal: $$\sqrt{n} \left(\theta_{\text{MaxL}} - \theta_{\text{ground truth}}\right) \overset{d}{\to} N(0, \text{FI}^{-1})$$

$\text{FI} = -\lim\limits_{n \to \infty} \frac1n \mathbb{E}(\text{Hessian})$ — asymptotic Fisher information matrix

Relationship to Randomness	Cannot predict	Can predict given enough information

• Regularization
• Compositeness. For example, the popularity of topics on social networks — first, we calculated based on the news feed, then refined using video data
• On-the-fly data processing — iteratively update the posterior distribution
• We can calculate various statistics
• We can estimate the confidence in the values of model parameters

$$p(\theta|X) = \frac{p(X|\theta)p(\theta)}{\underbrace{\int p(X|\theta)p(\theta)d\theta}_{\text{multidimensional integral}}}$$

Calculation Methods

• Analytical calculation
• Markov chain Monte Carlo (MCMC)
• Variational inference (not covered in the first part of the course)

Let $p(x|\theta) = A(\theta)$ and $p(\theta) = B(\alpha)$

The prior distribution of parameters $p(\theta)$ is called conjugate to $p(x|\theta)$ (conjugate priors), if the posterior distribution belongs to the same family as the prior $p(\theta|x) = B(\alpha^\prime)$

Knowing the formula for the family to which our posterior distribution should belong, it is easy to calculate its normalizing factor (the integral in the denominator)

Posterior distribution of the expected value of a normal distribution

Normal distribution:

$N(x|\mu, \sigma) = \frac{1}{\sigma \sqrt{2\pi}} \exp\left(-\frac{(x-\mu)^2}{2\sigma^2} \right)$

Posterior probability of getting heads when flipping a biased coin

Frequentist approach

$q$ — the probability of heads equals the fraction of heads in $n$ flips

Likelihood

Binomial distribution: $p(x|q) = C_n^x q^x (1-q)^{n-x}$

Conjugate prior

Beta distribution: $p(q| \alpha, \beta) = \frac{q^{\alpha-1} (1-q)^{\beta-1}}{B(\alpha, \beta)}$

The numerator of the posterior distribution:

$$q^{\alpha-1+x} (1-q)^{\beta-1+(n-x)} = q^{\alpha^\prime-1} (1-q)^{\beta^\prime-1},$$

where $\alpha^\prime = \alpha + x, \beta^\prime = \beta + n - x$, so essentially, we also know the denominator, it equals $B(\alpha^\prime, \beta^\prime)$.

Posterior distribution

$$p(q|x) = \frac{q^{\alpha-1+x} (1-q)^{\beta-1+(n-x)}}{B(\alpha + x, \beta + n - x)}$$

Motivation

• We'd like to be able to calculate mathematical expectations and other quantities according to the posterior distribution, known up to a constant
• For example, we'd like to know the response of an ensemble consisting of an infinite number of algorithms :)
• We can sum up (integrate) the expected responses of the classifier, according to the probability of the model parameters

A broad class of computational algorithms based on the repeated execution of random experiments and the subsequent calculation of quantities of interest.

$$\int f(x)dx \approx \frac{1}{n} \sum\limits_{i=1}^n f(x_i)$$

• Invented by Stanislaw Ulam in 1949 when he was playing solitaire while ill and wondered what is the probability of being able to play out all the cards? He didn't solve it combinatorically, but simply by the share of successful games
• The method was named after the Monte Carlo casino in Monaco for the sake of secrecy since it was used in the Manhattan Project for the development of nuclear weapons in the USA

• $x_1^1 \sim p(x_1 | x_2 = x_2^0, x_3 = x_3^0)$
• $x_2^1 \sim p(x_2 | x_1 = x_1^1, x_3 = x_3^0)$
• $x_3^1 \sim p(x_3 | x_1 = x_1^1, x_2 = x_2^1)$
• $x_1^2 \sim p(x_1 | x_2 = x_2^1, x_3 = x_3^1)$ etc.

After a few iterations "the chain has warmed up", we can estimate expectations based on these samples.