DI Law of Large Numbers e Central limit theorem ne parliamo in Central Limit Theorem and Law of Large Numbers. Usually these methods are useful when you need to calculate following something similar to Bayes rule, but don’t know how to calculate the denominator, often infeasible integral. We estimate this value without explicitly calculating that.

Interested in $\mathbb{P}(x) = \frac{1}{z} \mathbb{P}^{*}(x) = \frac{1}{Z} e^{-E(x)}$ Can evaluate E(x) at any x.

  • Problem 1 Make samples x(r) ~ 2 P
  • Problem 2 Estimate expectations $\Phi = \sum_{x}\phi(x)\mathbb{P}(x)$) What we’re not trying to do:
  • We’re not trying to find the most probable state.
  • We’re not trying to visit all typical states.

Law of large numbers

Data una sequenza di variabili aleatorie, $X_{1}, X_{2}, \dots, X_{n}\dots$, tali che siano i.i.d tali per cui $E(X_{1}) = E(X_{2}) = \dots = E(X_{n}) =\dots = \mu$ tale che sia finito. Consideriamo

$$ S_{n} = \sum^n_{i=1} x_{i} ,:, \bar{x}_{n} = \frac{S_{n}}{n} $$

Allora questo teorema afferma che:

$$ \bar{x}_{n} \to \mu $$

Ossia il limite converge sul valore atteso di tutte le variabili aleatorie.

Inoltre se abbiamo che la varianza di tutte le variabili aleatorie, abbiamo che

$$ var(\hat{x}_{n}) = \frac{\sigma^{2}}{n} \to 0 $$

Strong Law of large Numbers

$$ \mathbb{P}(\lim_{ n \to \infty } \bar{x}_{n} =\mu) = 1 $$

Ci permette di prendere la sample average per quei valori di mezzo. E posso fare la stima della nostra funzione di interesse $h$ tenendo conto:

$$ \bar{h}_{n} = \sum_{i=1}^{n} \frac{h(x_{i})}{n} $$

E questo converge $O(\sqrt{ n })$ per la legge dopo.

Central limit theorem

Data una sequenza di variabili aleatorie, $X_{1}, X_{2}, \dots, X_{n}\dots$, tali che siano i.i.d tali per cui $E(X_{1}) = E(X_{2}) = \dots = E(X_{n}) =\dots = \mu$ tale che sia finito, e con varianza tutti uguali $= \sigma^{2}$ finito.

Abbiamo come risultato che

$$ \sqrt{ n } (\hat{x}_{n} - \mu) \to N(0, \sigma^{2}) $$

La prima parte è una variabile aleatoria e converge a quel valore. (questo permette di utilizzare la gaussiana quando $n$ è grande abbastanza).

Monte carlo integration

Abbiamo che:

$$ \int_{X} h(x) \cdot f(x) dx = E_{f}[h(x)] = \mu $$

Questo è tutto il significato dell’integrazione di monte carlo (molte variabili aleatorie per stimare il valore di qualcosa). E questo vale sempre, anche se $f$ non è una funzione di densità, basta che sia positiva (basta riscalare).

Il motivo per cui funziona è per LLN, perché abbiamo che convergerà su $\mu$ in lungo termine, basta considerare molte variabili aleatorie consecutive.

Cose interessanti:

  1. Posso stimare il valore atteso grazie a LLN
  2. Posso stimare la varianza grazie ad essa
  3. Posso stimare variabili condizionali.

Importance sampling

  1. Deve soddisfare la cosa del supporto (contiene supporto sia di h che di f)
  2. Deve avere varianza finita per i pesi che sono trovati. (ci sono metodi per stimare poi il $g$).
    1. la frazione $\frac{f}{g}$ deve essere limitata e la varianza di $h$ rispetto alla densità $f$ deve essere finita.

Bound on samples

TODO: this should be interesting and important and should use Hoeffding’s inequality.

Markov Chain Monte Carlo

L’idea principale di Markov Chain Monte carlo è di costruire una catena di Markov tale che si possa utilizzare per generare dalla distribuzione difficilmente trattabile. Uno dei metodi principali per fare ciò è utilizzare tecniche si sampling.

Metropolis Hastings

Con distribuzioni Gaussiane

Il caso continuo con distribuzione Gaussiane potrebbe essere di particolare interesse perché semplifica l’analisi del calcolo del coefficiente $\alpha$: dato che le Gaussians sono simmetriche, abbiamo che il valore di

$$ \frac{r(x' \mid x)}{r(x \mid x')} = \frac{\mathcal{N}(x'; x, \tau I)}{\mathcal{N}(x; x', \tau I)} = 1 $$

Quindi il coefficiente $\alpha$ si può scrivere anche solo come le distribuzioni $\frac{q(x)}{q(x')}$ che se si assume una distribuzione di Gibbs, si può intendere come un $\exp(f(x) - f(x'))$, che è di facile interpretazione.

Metropolis adjusted Langevin Algorithm

This is just metropolist hasting with Gaussians, but we fix the mean with a gradient descent step. This is interpretable as using information from the gradient. Now the mean is $x - \tau \nabla f(x)$ instead of just $x$. The proposal function is still a Gaussian. This allows us to accept always, which motivates why it is more efficient compared to the Metropolis Hasting algorithm. Now the proposal distribution is the following

$$ r(x'\mid x) = \mathcal{N}(x'; x - \tau \nabla f(x), 2\tau I)) $$

§ It is possible to show that for log-concave distributions (e.g., Bayesian log. Regression), MALA efficiently converges to the stationary distribution (mixing time is polynomial in the dimension)

Somehow, one can prove that if $\tau \to 0$ then the Metropolis Hastings tends to always accept the proposal, which is why it is more efficient. The version of Metropolis Hastings that always accepts is called Unadjusted Langevin Algorithm.

If we model the energy function as:

$$ p(\theta \mid x_{1:n}, y_{1:n}) = \frac{1}{Z} \exp(\log p(\theta) + \sum_{i=1}^{n} \log p(y_{i} \mid x_{i}, \theta)) $$

Similarly to a Log Linear Models in language processing, then the update function is the following:

$$ \theta_{t+1} = \theta_{t} + \tau \nabla_{\theta} \log p(\theta) + \tau \sum_{i=1}^{n} \nabla_{\theta} \log p(y_{i} \mid x_{i}, \theta) + \varepsilon $$

Where $\varepsilon \sim \mathcal{N}(0, 2\tau I)$

The drawback of this method is that computing the energy for the whole dataset is expensive for large datasets. This is why sometimes we use a stochastic version of this algorithm. Which drives to the stochastic gradient Langevin dynamics.

Stochastic Gradient Langevin Dynamics

The double value for the Noise signal is justifiable if you study diffusion processes. So if you want to know how the $2$ factor comes into play when analyzing the process take a look at those courses. One can also estimate the update of the gradient of the likelihood by having $m$ samples and then using that values for the update: So the algorithm for the update becomes:

  1. Sample $m$ points and then update $\theta$ as follows: $$ \theta_{t+1} = \theta_{t} + \tau \nabla_{\theta} \log p(\theta) + \tau\frac{n}{m} \sum_{i=1}^{m} \nabla_{\theta} \log p(y_{i} \mid x_{i}, \theta) + \varepsilon $$

Langevin Monte Carlo

TODO: this is just an Outlook, and it is left out.

Gibbs Sampling

These are probably not very important for the exam.

The Idea

Gibbs sampling is a special case of Metropolis Hasting, in this case the proposal distribution $r$ is as follows:

$$ r_{i}(x' \mid x) = \begin{cases} p(x_{i}' \mid x'_{-i}) & \text{if } x' \text{ differs from } x \text{ only in } i \\ 0 & \text{else} \\ \end{cases} $$

We just focus on a single coordinate difference. Similar to the coordinate descent in some manner.

Landscape of sampling methods

we can broadly categorize optimization methods based on the use of

  • Momentum
  • Stochasticity
  • Sampling Then we would have this cube. Monte Carlo Methods-20241104133523681