Dataset is not linearly separable Unlike the case when the dataset is linearly separable, we cannot find a hyperplane that separates the two classes of data points with zero training error. Soft margin To handle this case, we introduce a slack variable $\xi_i$ for each data point $x_i$ to allow some points to be on the wrong side of the margin or even in the wrong class. Optimization problem The optimization problem becomes: ...

Prerequisites - Kernel trick Kernel function $k(x, y) = \phi(x)^T \phi(y)$ where $\phi(x)$ is a feature mapping that maps the data points to a higher dimensional space without actually computing the feature mapping, i.e., $\phi(x)$. In other words, we can compute the kernel function $k(x, y)$ without actually computing the feature mapping $\phi(x)$. Examples of kernel functions: Polynomial kernel: $k(x_1, x_2) = \phi(x_1)^T \phi(x_2) = (1 + x_1^T x_2)^p$ Sigmoid kernel: $k_s(x_1, x_2) = \frac{1}{1 + \exp(a x_1^T x_2)}$ RBF/Gaussian kernel: $k(x_1, x_2) = \exp\left(-\frac{| x_1 - x_2 |^2}{\sigma^2}\right)$ Motivation If the dataset $D = {(x_i, y_i)}_{i=1}^n$ where $x_i \in \mathbb{R}^d$ and $y_i \in {-1, 1}$ is not linearly separable in the original $d$-dimensional space, we can use a feature mapping $\phi(x)$ to map the data points to a higher dimensional space where they become linearly separable and then use the SVM optimization problem to find the optimal hyperplane. ...

Temporal Difference (TD) learning, introduced by Rich Sutton in 1984, is a fundamental reinforcement learning method that combines ideas from Monte Carlo methods and dynamic programming. Recap of Monte Carlo Methods Recall that Monte Carlo methods estimate the value function by: $$ V_\pi(s) = E[G_n | S_0 = s] $$ where: $G_n = r_{n+1} + r_{n+2} + … + r_N$ is the return (sum of rewards until terminal state) $N$ is the terminal instant of the episode Monte Carlo methods work with sample average data collected over complete trajectories, requiring episodes to terminate before learning can occur. ...

Temporal Difference (TD) learning is a fundamental reinforcement learning technique that combines ideas from Monte Carlo methods and dynamic programming. It allows agents to learn from experience without requiring a model of the environment, making it particularly valuable for real-world applications. Understanding Policy Evaluation Mathematical Foundation Policy evaluation refers to the process of determining the value function $J_π$ for a given policy $π$. The value function represents the expected cumulative reward when following policy $π$ from a given state. ...

Definitions Expected Single-Stage Cost The expected single-stage cost under policy $\mu$ in state $x$, denoted as $\bar{g}(x,\mu(x))$, is: $$ \underbrace{\bar{g}(x,\mu(x))}_{\substack{\text{Expected} \\ \text{single-stage cost}}} = \sum_{j=0}^n \underbrace{p_{xj}(\mu(x))}_{\substack{\text{Transition} \\ \text{probability}}} \underbrace{g(x,\mu(x),j)}_{\substack{\text{Stage cost for} \\ \text{this transition}}} $$ where: $p_{xj}(\mu(x))$ is the probability of transitioning from state $x$ to state $j$ under action $\mu(x)$ $g(x,\mu(x),j)$ is the stage cost for this transition The sum is over all possible next states $j$ This represents the immediate expected cost when taking the action prescribed by policy $\mu$ in state $x$. ...

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

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