Let the data be D = {($x_1$, $y_1$), ($x_2$, $y_2$), …, ($x_n$, $y_n$)} where $y_i$ is the label of the feature vector $x_i$. Let the hypothesis space be $H = {h | h: X \to Y}$. The Bayes classifier is defined as: $$h_B(x) = \begin{cases} 1 & \text{if } P(y=1 | x=x_i) > P(y=0 | x=x_i) \ 0 & \text{if } P(y=1 | x=x_i) \leq P(y=0 | x=x_i) \end{cases}$$ Notations $P(y)$ is also called the prior probability of class $y$ or class prior probability. $P(x|y)$ is also called the likelihood of $x$ given class $y$. $P(y|x)$ is also called the posterior probability of class $y$ given $x$. $P(x)$ is also called the evidence. Bayes classifier is the best classifier for 0-1 loss function To prove that the Bayes classifier is the best classifier for the 0-1 loss function, we need to show that it minimizes the expected risk (error) for any given input $x$. ...

It can be shown that average risk for square error loss can be decomposed into three components: $$ R_{\text{avg}}(h) = \mathbb{E}_{P_D} \mathbb{E}_{P_{x,y}} \left[ \left( h_D(x) - \hat{h}(x) \right)^2 \right] \quad \text{// variance (sensitivity to dataset)} $$ $$ + \mathbb{E}_{P_{x,y}} \left[ \left( \hat{h}(x) - h^*(x) \right)^2 \right] \quad \text{// bias (how different is avg classifier from optimum classifier)} $$ $$ + \mathbb{E}_{P_{x,y}} \left[ \left( h^*(x) - y \right)^2 \right] \quad \text{// irreducible noise (nothing can be done about this)} $$ where: ...

In bagging, we train each model independently on a random subset of the data. In boosting, we train each model sequentially on the same data, with each subsequent model focusing on correcting the errors of combined previous model by increasing weights of misclassified datapoints Unlike bagging, each model depends on the previous ones and its contribution to the final prediction is weighted differently. Mathematical Formulation of Boosting Let’s define the ensemble model $H_T(x)$ as: ...

Formulas: K L divergence: $D_{KL}(p; q) = \int p(x) \log \frac{p(x)}{q(x)} dx$ F-divergence: $D_{F}(p \parallel q) = \int q(x) f\left(\frac{p(x)}{q(x)}\right) dx$ $f: \mathbb{R}^+ \rightarrow \mathbb{R}$ is lower semi continous convex function such that $f(1) = 0$ If $f(x) = x \log x$, then $D_{F}(p \parallel q) = D_{KL}(p \parallel q)$ If $f(x) = x\log(x) - (x+1)\log(x+1)$, then $f^*=-\log(1-\exp^x)$, then $D_{F}(p \parallel q)$ = Jensen-Shannon divergence = $D_{JS}(p \parallel q) = \frac{1}{2}D_{KL}(p \parallel m) + \frac{1}{2}D_{KL}(q \parallel m)$, where $m = \frac{1}{2}(p + q)$ Jensen’s inequality: For a convex function $f$ and a random variable $X$: $f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)]$ Used to prove F-divergence is non-negative Used in VAEs as latent space models Convex functions: Let f: $\mathbb{R}^N \rightarrow \mathbb{R}$ be a convex function. Then f is convex if and only if $f(\lambda x + (1-\lambda) y) \leq \lambda f(x) + (1-\lambda)f(y)$ Convex conjugate: Let f: $\mathbb{R}^N \rightarrow \mathbb{R}$ be a convex function. The convex conjugate of f is the function $f^*(y) = \sup_x (y^Tx - f(x))$ $f^{**}(x)$ is also convex, i.e: $f^{**}(\lambda x + (1-\lambda) y) \leq \lambda f^{**}(x) + (1-\lambda)f^{**}(y)$ $f^{**}(y) = f(y)$ Wasserstein metric: The Wasserstein distance $W_p(P,Q)$ of order $p$ is defined as:$W_p(P,Q) = \left( \inf_{\gamma \in \Gamma(P,Q)} \mathbb{E}_{(x,y) \sim \gamma} [d(x,y)^p] \right)^{1/p}$ K - Lipschitz: K lipschitz is defined as: $|f(x) - f(y)| \leq K |x-y|$ FID: $FID = |\mu_r - \mu_g|^2 + \operatorname{Tr}(\Sigma_r + \Sigma_g - 2\sqrt{\Sigma_r \cdot \Sigma_g})$ GANs: $\theta^*_{GAN} = \underset{\theta}{\text{argmin}} \underset{\phi}{\sup} \left[\mathbb{E}_{x \sim p_{data}}[T_\phi(x)] - \mathbb{E}_{x \sim p_{generator}}[f^*(T_\phi(x))]\right]$ $\theta^*_{NaiveGAN} = \underset{\theta}{\text{argmin}} \underset{\phi}{\sup} \left[\mathbb{E}_{x \sim p_{data}}[\log(D_\phi(x))] + \mathbb{E}_{x \sim p_{generator}}[\log(1-D_\phi(x))]\right]$ $\theta^*_{WGAN} = \underset{\theta}{\argmin} \, \sup_{f \in \text{Lip}_1} [\mathbb{E}_{x \sim P_{data}}[f(x)] - \mathbb{E}_{x \sim P_{generator}}[f(x)]]$ $\theta^*_{CGAN} = \underset{\theta}{\text{argmin}} \underset{\phi}{\sup}[\mathbb{E}_{x \sim p_{data}(x|y)}[\log D(x|y)] + \mathbb{E}_{z \sim p_z(z)}[\log(1 - D(G(z|y)|y))]]$ $\mathcal{L}_{DA} = \mathbb{E}_{x^s \sim p_s(x)}[\log(D(\phi(x^s)))] + \mathbb{E}_{x^t \sim p_t(x)}[\log(1 - D(\phi(x^t)))]$ VAEs: **$ELBO_{VAE}$** = $F_{\theta}(q) = \mathbb{E}_{q(z|x)} \left[ \log p_{\theta}(x|z) \right] - D_{KL} \left( q(z|x) \mid p_{\theta}(z) \right) $ - **First term**: $ \nabla_{\phi} \mathbb{E}_{q(z|x)}[\log p_{\theta}(x|z)] \approx \frac{1}{N} \sum_{i=1}^N \nabla_{\phi} [\log p_{\theta}(x|g_{\phi}(\epsilon_i))]$ where $\epsilon \sim p(\epsilon)$ (typically a standard normal distribution) and $g_{\phi}(\epsilon)$ is our reparameterization function typically $z=g_{\phi}(\epsilon) = \mu_{\phi}(x) + \sigma_{\phi}(x) \odot \epsilon$ - **Second term**: $ D_{KL}(N(z; \mu_\phi(x), \Sigma_\phi(x)) \| N(0, I)) = \frac{1}{2} \sum_{j=1}^J \left( \mu_{\phi,j}^2(x) + \Sigma_{\phi,j}(x) - \log \Sigma_{\phi,j}(x) - 1 \right) $ - **Aggregated posterior mismatch**: $ q_{\phi}(z) = \int q_{\phi}(z|x) p(x) dx \neq \int p_{\theta}(z|x) p(x) dx = p_{\theta}(z) $ **$ELBO_{Regularized VAEs(Beta VAEs)}$** = $ F_{\theta}(q) = \mathbb{E}_{q_{\phi}(z|x)} \left[ \log p_{\theta}(x|z) \right] - \beta D_{KL} \left( q_{\phi}(z|x) \| p(z) \right) $ **$ELBO_{InfoVAE}$**: $ = \mathbb{E}_{q_\phi(z|x)}[\log p_\theta(x|z)] -\lambda D_{KL}(q_\phi(z) \| p(z)) + \alpha I_q(x;z) $ where $I_q(x;z) = \mathbb{E}{p_D(x)}[D{KL}(q_\phi(z|x) | q_\phi(z))]$ DDPMs: Forward diffusion process: $X_t = \sqrt{\alpha_t} X_{t-1} + \sqrt{1-\alpha_t} \epsilon, \quad \epsilon \sim \mathcal{N}(0,I)$ $ X_t = \sqrt{\bar{\alpha}_t}X_0 + \sqrt{1-\bar{\alpha}_t}\epsilon $ where $ \bar{\alpha}t = \prod{i=1}^t \alpha_i $ $ELBO_{DDPMs}$ = $\mathbb{E}{q(X{1:T}|X_0)}\left[\log p_\theta(X_0|X_1) + \log \frac{p(X_T)}{q(X_T|X_0)} + \sum_{t=2}^T \log \left(\frac{p_\theta(X_{t-1}|X_t)}{q(X_{t-1}|X_t,X_0)}\right)\right]$ ie reconstruction term + prior matching term + transition matching term Score matching: Langevin equation: $x_{t+1} = x_t + \alpha \cdot \nabla_\theta \log p_\theta(x_t) + \sqrt{2\alpha} \epsilon, \quad \epsilon \sim \mathcal{N}(0, I)$ Score function: $\nabla_x \log p(x) = s(x)$ Explicit score matching: $J_{ESM}(\theta) = \mathbb{E}_{p(x)} \left[ \frac{1}{2} | \hat{s}(x; \theta) - \nabla_x \log p(x) |^2 \right]$ Implicit score matching: $J_{ISM}(\theta) = \mathbb{E}_{p(x)} \left[ \frac{1}{2} | \hat{s}(x; \theta) |^2 + \text{tr}(\nabla_x \hat{s}(x; \theta)) \right] + C$ Theorem: $J_{ISM}(\theta) = J_{ESM}(\theta) + C$ Projected score matching: $J_{PSM}(\theta) = \frac{1}{2} \mathbb{E}v \mathbb{E}{p(x)} \left[ | v^\top \hat{s}_\theta(x) - v^\top s(x) |^2 \right]$ Sliced score matching: $J_{SSM}(\theta) = \mathbb{E}v \mathbb{E}{p(x)} \left[ \frac{1}{2}(v^\top \hat{s}\theta(x))^2 + v^\top (\nabla_x \hat{s}\theta(x)) v \right]$ Theorem: $J_{PSM}(\theta) = J_{SSM}(\theta) + C$ Deep score matching: $J_{DSM}(\theta) = \frac{1}{2} \mathbb{E}{p(x,x’)} \left[ | \hat{s}\theta(x) - \nabla_{x} \log p(x|x’) |^2 \right]$ Theorem: $J_{ESM}(\theta) = J_{DSM}(\theta) + C$ Conditional score matching: Classifier guided: $ s(x|y) = s(y|x) + s(x) $ Classifier free: $s_\theta(x|y){CFG} = (1+w)s\theta(x|y) - w s_\theta(x|\text{null})$ Stochastic differential equation: Standard Stochastic differential equation: $dx = f(x,t)dt + g(x,t)dB_t$ such that $dB_t = \sqrt{dt}\epsilon \quad \text{where} \quad \epsilon \sim N(0,1)$ Anderson’s result: The corresponding reverse SDE takes the form: $dx = \left(f(x,t) - g^2(t)\nabla_x(\log p_t(x))\right)dt + g(t)dB_t$ Big picture: Stochastic discrete forward process to continuous SDE Continuous SDE to continuous reverse SDE Continuous reverse SDE to discrete reverse process Self supervised learning: Noise contrastive estimation: $J(\theta) = \frac{1}{2} \mathbb{E} [\log \sigma(\log p_\theta(x) - \log p_N(x)) + \log(1-\sigma(\log p_\theta(y) - \log p_N(y)))]$ Info NCE: $\mathcal{L}{\text{InfoNCE}} = -\mathbb{E}\left[\log \frac{\exp(f\theta(x)^\top f_\theta(x^+))}{\exp(f_\theta(x)^\top f_\theta(x^+)) + \sum_{i=1}^{N-1} \exp(f_\theta(x)^\top f_\theta(x^-_i))}\right]$ Masked reconstruction: $\mathcal{L}(\theta) = \mathbb{E}{x \sim p\text{data}}\left[d(x, T_\theta(\text{mask}(x)))\right]$ JEPA: $\mathcal{L}(\theta,\phi,\psi) = \mathbb{E}{(x_c,x_t) \sim p\text{data}}\left[|z_t - \hat{z}_t|^2\right]$ Gradient: For a scalar-valued differentiable function $f(\mathbf{x})$ of vector $\mathbf{x} \in \mathbb{R}^n$, the gradient $\nabla_{\mathbf{x}} f(\mathbf{x})$ is: $$\nabla_{\mathbf{x}} f(\mathbf{x}) = \begin{bmatrix} \frac{\partial f}{\partial x_1} \ \frac{\partial f}{\partial x_2} \ \vdots \ \frac{\partial f}{\partial x_n} \end{bmatrix}$$ Jacobian: If $f(\mathbf{x})$ is a vector-valued function of vector $\mathbf{x}$ ie $f: \mathbb{R}^n \rightarrow \mathbb{R}^m$, then the Jacobian matrix contains the partial derivatives of each component of $f$ with respect to each component of $\mathbf{x}$: $$J = \begin{bmatrix} \frac{\partial f_1}{\partial x_1} & \frac{\partial f_1}{\partial x_2} & \cdots & \frac{\partial f_1}{\partial x_n} \ \frac{\partial f_2}{\partial x_1} & \frac{\partial f_2}{\partial x_2} & \cdots & \frac{\partial f_2}{\partial x_n} \ \vdots & \vdots & \ddots & \vdots \ \frac{\partial f_m}{\partial x_1} & \frac{\partial f_m}{\partial x_2} & \cdots & \frac{\partial f_m}{\partial x_n} \end{bmatrix}$$ Hessian: The Hessian matrix is the second derivative of scalar valued function $f$ with respect to each component of $\mathbf{x}$, and is a matrix of size $n \times n$. In simple words, hessian is just jacobian of gradient of $f$. It is defined as: $$H = \begin{bmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_n} \ \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \cdots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \ \vdots & \vdots & \ddots & \vdots \ \frac{\partial^2 f}{\partial x_n \partial x_1} & \frac{\partial^2 f}{\partial x_n \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_n^2} \end{bmatrix}$$ ...

A Conditional Generative Adversarial Network (cGAN) is a type of Generative Adversarial Network (GAN) where the generation process is conditioned on some additional information, such as class labels or data from other modalities. Architecture modification Generator Concatenate the conditional information Y with the noise input Z and feed it to the generator. Here Y can be: One hot encoded class label Text embedding etc Discriminator The discriminator in a cGAN is modified similarly to the generator. Concatenate the conditional information Y with the input image X and feed this combined input (X, Y) to the discriminator. ...

When we had unlabeled data, we estimated the score function: $$s(x) = \nabla_x \log p(x)$$ Now, we have labeled data ie $D = {(x_i, y_i)}_{i=1}^N$ we instead estimate the conditional score function: $$s(x|y) = \nabla_x \log p(x|y)$$ Where: $s(x)$ is the unconditional score function $s(x|y)$ is the conditional score function $p(x)$ is the data distribution $p(x|y)$ is the conditional data distribution given some condition $y$ This can be done in 2 ways: ...

Convex conjugate is also known as the Fenchel conjugate or the Legendre transform Definition Let $f: R^n → R$ be a convex function. The convex conjugate of $f$, denoted as $f^*$, is defined as: $$f^*(y) = \underset{x \in \text{dom} f}{\sup} (y^T x - f(x))$$ Where: $y \in R^n$ is the variable $\text{dom} f$ is the domain of $f$ $\sup$ denotes the supremum (least upper bound) Properties 1. Convexity: $f^{**}(x)$ is also convex Proof: Let $y_1, y_2 \in \mathbb{R}^n$ and $\lambda \in [0,1]$. We need to show that: ...

Motivation During inference, we often had to sequentially traverse through 1000 time steps because of the Markov property assumption, which can be computationally intensive. Is it possible to give up the Markov property assumption so that we can train the same way but sample faster - not have to traverse through 1000 time steps? Recall the DDPM Forward process: $$q(x_t | x_0) = \int q(x_{t:1} | x_0) dx_{1:(t-1)}$$ $$q(x_t | x_0) = \mathcal{N}(x_t; \sqrt{\alpha_t} x_0, (1 - \alpha_t) \mathbb{I})$$ $$\Rightarrow x_t = \sqrt{\alpha_t} x_0 + \sqrt{1 - \alpha_t} \epsilon, \quad \epsilon \sim \mathcal{N}(.)$$ Note that here $\alpha_t$ is $\bar{\alpha}$ that we studied in DDPM. ...

Step 1 of big picture (Stochastic forward process to continuous SDE) Now let’s see how DDPMs can be viewed as discretizations of SDEs. The forward process in DDPMs is given by: $$x_{i+1} = \sqrt{1-\beta_{i+1}}x_i + \sqrt{\beta_{i+1}}\epsilon_i \quad \text{where} \quad \epsilon_i \sim \mathcal{N}(0,I)$$ Let’s derive the corresponding continuous-time SDE: First, rewrite the discrete equation: $$x_{i+1} - x_i = (\sqrt{1-\beta_{i+1}} - 1)x_i + \sqrt{\beta_{i+1}}\epsilon_i$$ As the time step $\Delta t \to 0$, we can approximate: $$\sqrt{1-\beta_{i+1}} \approx 1 - \frac{\beta_{i+1}}{2}$$ This approximation comes from the Taylor series expansion of $\sqrt{1-x}$ around $x=0$: $$\sqrt{1-x} = 1 - \frac{1}{2}x - \frac{1}{8}x^2 - \frac{1}{16}x^3 + \cdots$$ We keep only the first two terms, assuming $\beta_{i+1}$ is small. Substituting this approximation and introducing $\Delta t$: $$x_{i+1} - x_i \approx -\frac{\beta_{i+1}}{2}x_i\Delta t + \sqrt{\beta_{i+1}}\epsilon_i\sqrt{\Delta t}$$ Here, $\Delta t$ is introduced to represent the time step between $i$ and $i+1$. In the continuous limit, as $\Delta t \to 0$: $x_{i+1} - x_i \to dx$ $\beta_{i+1} \to \beta(t)$ $\epsilon_i\sqrt{\Delta t} \to dB_t$ (where $B_t$ is Brownian motion) Therefore, the continuous-time SDE is: $$dx = -\frac{\beta(t)}{2}x dt + \sqrt{\beta(t)}dB_t$$ ...

How to descion tree works At each node, a question is asked about the data that splits the data into two or more non-overlapping subsets. $$ \text{Question: } x_j \leq \theta $$ then the data is split into two subsets, one where $x_j \leq \theta$ and one where $x_j > \theta$. The process is repeated till we reach leaf node, that classifies the datapoint to a region of the feature space. We can do regression and classification of the test datapoint based on the trainig datapoints that lie in the region. ...