Posts

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)]$ ...

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. ...

$X_T$ to $X_0$ For $\sigma = 0$, the DDIM process becomes deterministic: $$x_{t-1} = \sqrt{\alpha_{t-1}}\left(\frac{x_t - \sqrt{1-\alpha_t}\epsilon_\theta^{(t)}(x_t)}{\sqrt{\alpha_t}}\right) + \sqrt{1-\alpha_{t-1}}\epsilon_\theta^{(t)}(x_t)$$ where: $\epsilon_\theta^{(t)}(x_t)$ is the predicted noise from our trained model $\alpha_t$ is the cumulative product of $(1-\beta_t)$ This deterministic nature means that: For a given $x_T$, we can find a unique $x_0$ by following the forward process Given this $x_T$, we can recover the exact same $x_0$ through the reverse process This property makes DDIM particularly useful for: ...

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. ...

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. ...