Posts

In unsupervised learning, we don’t have labeled data. We want to find structure in the data. Hence the data is of the form $X = {x_1, …, x_N}$ where $x_i \in \mathbb{R}^d$.

Understanding VAE as a Regularized Autoencoder Recall that the Variational Autoencoder (VAE) objective is given by: $$ F_{\theta}(q) = \mathbb{E}_{q_{\phi}(z|x)} \left[ \log p_{\theta}(x|z) \right] - D_{KL} \left( q_{\phi}(z|x) \| p(z) \right) $$ We can rewrite this as: $$ F_{\theta}(q) = \mathbb{E}_{q_{\phi}(z|x)} \left[ \|x - \hat{x}\|^2 \right] - D_{KL} \left( q_{\phi}(z|x) \| p(z) \right) $$ Where: The first term is the reconstruction error The second term acts as a regularizer This formulation shows that the VAE objective can be interpreted as a regularized autoencoder, where the regularization term encourages the latent distribution to be close to the prior $p(z)$. ...

Value iteration is a numerical method for solving Stochastic Shortest Path (SSP) problems that relies on the dynamic programming operator $T_\mu$. Let’s examine how this operator works and its key properties: The Dynamic Programming Operator $T_\mu$ For a given policy $\mu$, the dynamic programming operator $T_\mu$ transforms one value function into another. Mathematically, for any state $x$, we have: $$ \underbrace{(T_\mu J)(x)}_{\substack{\text{New value function} \\ \text{at state } x}} = \underbrace{E_{x_{k+1}}}_{\substack{\text{Expected value over} \\ \text{next states}}} \left[ \underbrace{g(x,\mu(x),x_{k+1})}_{\substack{\text{Stage cost under} \\ \text{policy } \mu}} + \underbrace{J(x_{k+1})}_{\substack{\text{Cost-to-go from} \\ \text{next state}}} \biggm\vert x_k=x \right] $$ where: ...

Problem setting Given a set of data points $D = ({x_i})_{i=1}^N$ Where $x_i \in \mathbb{R}^d$ are iid samples from some unknown distribution $p_{\text{data}}$. We want to model $p_{\text{data}}$ as $p_{\theta}$ using a neural network. We model $p_{\theta}$ as a latent variable model Modelling Log likelihood is given by: $$ \ell(\theta) = \log p_{\theta}(x) $$ We assume that each data point $x_i$ is associated with a latent variable $z_i$. Hence, we will introduce the latent variable $z$ and marginalize over it: ...

Vector Quantized Variational Autoencoders (VQ-VAEs) were introduced to address several limitations of regular VAEs: The “posterior collapse” problem where the latent code is ignored The continuous latent space can make it difficult to model discrete structures The aggregated posterior mismatch between $q_\phi(z)$ and the prior $p(z)$ VQ-VAEs solve these issues by using discrete latent variables through vector quantization. The architecture consists of: An encoder network $E_{\phi}$ that maps input $x \in \mathbb{R}^N$ to continuous latent vectors $z_e = E_{\phi}(x) \in \mathbb{R}^{D}$ ...

Perfect Discriminator theorem The Perfect Discriminator theorem states that if two distributions $p_x$ and $q_x$ have support on two disjoint subsets $M$ and $P$ respectively, there always exists a discriminator $D^*: x \rightarrow [0,1]$ that has accuracy 1: $$\forall x \in M \cup P, D^*(x) = \begin{cases} 1 & \text{if } x \in M \ 0 & \text{if } x \in P \end{cases}$$ This discriminator achieves perfect classification, as it correctly identifies the origin of every sample with 100% accuracy. ...

Definition We can use Wasserstein metric in place of F-divergence to define a distance between two distributions $P$ and $Q$ both defined over the same space $X$. 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}$$ where: $\Gamma(P,Q)$ is the set of all possible joint distributions of $(x,y)$ where $x,y \in X$ with marginals $x \sim P$ and $y \sim Q$ (also called couplings) $\gamma(x,y)$ is a particular joint distribution chosen out of all possible joint distributions in $\Gamma(P,Q)$ that minimizes $\mathbb{E}_{(x,y) \sim \gamma} [d(x,y)^p]$ $d(x,y)$ is the metric (distance) between points $x$ and $y$ in the space $X$ $p \geq 1$ is the order of the Wasserstein distance. Common choices are $p=1$ (first-order Wasserstein distance) and $p=2$ (second-order Wasserstein distance). Properties of Wasserstein metric When $p=1$, the Wasserstein distance is equivalent to the Earth Mover’s Distance (EMD), because it can be interpreted as the minimum amount of work required to transform one distribution into another. When $p=2$, the Wasserstein distance is equivalent to the squared Euclidean distance. The Wasserstein distance is always finite, unlike the F-divergence, which can be infinite. The Wasserstein distance is a true metric, meaning it satisfies the triangle inequality. When KL divergence is $0$ then Wasserstein distance is $0$, but not vice versa. Proof for 5th property - KL divergence is 0 then Wasserstein distance is 0 To prove that when the KL divergence is 0, the Wasserstein distance is also 0, we start with the definitions of both metrics. ...

In XGBoost, the weak learners are decision trees. The algorithm builds these trees sequentially, with each new tree aiming to correct the errors of the combined previous trees. Recall that $r_i = -\frac{\partial R(H_{T-1}(x_i))}{\partial H_{T-1}(x_i)}$ are the pseudo-residuals. XGBoost formulates the optimization problem for finding the next weak learner as: $$ h_T = \arg\min_{h \in H} \sum_{i=1}^n (r_i \cdot h(x_i) + \frac{1}{2} h(x_i)^2) $$ We can rewrite this by defining $\hat{y}_i = -r_i$: ...