Let the data be $(x_i, y_i)$ for $i = 1, 2, …, n$ where $x_i \in \mathbb{R}^d$ and $y_i \in \mathbb{R}$. then we can model $y_i$ as: $$Y = \beta_0 + \beta_1X + \varepsilon$$ Where: $Y \in \mathbb{R}$ is the dependent variable $X \in \mathbb{R}^d$ is the independent variable (or feature vector in higher dimensions) $\beta_0$ is the y-intercept (bias term) $\beta_1$ is the slope (or coefficient vector in higher dimensions) $\varepsilon$ is the error term Ideal regressor For mean squared error loss, the ideal regressor is defined as: ...

Bayes Classifier Expectation Maximization (EM) Algorithm Linear Regression Parzen Window Estimate Linear Discriminant Analysis (LDA) Bias variance tradeoff Support Vector Machine (SVM) - Linearly Separable Data Support Vector Machine (SVM) - Non-linearly Separable Data SVM with Kernel Neural Networks Decision Trees Boosting XGBoost Adaboost K-means Clustering Miscellaneous Machine Learning Terms

Epoch One complete pass of the entire training dataset for training the model. Batch Size Risk is defined as $$L = \frac{1}{N} \sum_{i=1}^N l(y_i, \hat{y}_i)$$ Where $l(y_i, \hat{y}_i)$ is a general loss function that measures the discrepancy between the true value $y_i$ and the predicted value $\hat{y}_i$ for each sample. Instead of calculating the risk over the entire dataset, however calculating the risk over complete dataset is computationally expensive. Hence we calculate the risk over a small subset of the dataset, called a batch to perform back propogation. ...

Multi-Armed Bandit Problem The Multi-Armed Bandit problem is a fundamental concept in reinforcement learning, where an agent must repeatedly select from multiple options, known as “arms” (akin to slot machines), to maximize its cumulative reward. This scenario is simplified by the fact that the environment is state-less, meaning the outcome of an action is solely dependent on the action itself, without any influence from a changing state. Key characteristics of the Multi-Armed Bandit problem include: ...

A Naive GAN (Generative Adversarial Network) refers to the basic or “vanilla” version of GANs, introduced by Ian Goodfellow in 2014. Derivation Recall the genereral expression for the GANs that we got by minimizing F-divergence: $$\theta^* = \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]$$ where: $\theta$: Parameters of the generator network $\phi$: Parameters of the discriminator (critic) network $\theta^*$: Optimal parameters for the generator $\text{argmin}_\theta$: Argument that minimizes the expression with respect to $\theta$ $\sup_\phi$: Supremum (least upper bound) with respect to $\phi$ $T_\phi(x)$: The discriminator function, parameterized by $\phi$ $f^*$: The convex conjugate of the function $f$ used in the F-divergence $p_{data}$: The true data distribution $p_{generator}$: The distribution of the generated data Write $T_\phi(x)$ as composite function $T_\phi(x) = \sigma(V_\phi(x))$, where $\sigma$ is the sigmoid function Substitute this in the expression for GANs: ...

A neural network is a computational model inspired by the structure and function of biological neural networks. Mathematically, it can be defined as a series of function compositions: $$ f(x) = f_L(f_{L-1}(…f_2(f_1(x)))) $$ where $L$ is the number of layers in the network, and each function $f_i$ represents a layer operation. For a single layer, the operation can be expressed as: $$ f_i(x) = \sigma(W_i x + b_i) $$ where: ...

Idea The core idea behind Noise Contrastive Estimation (NCE) is: Given samples from a distribution, if you know how to distinguish them from noise samples, then you implicitly know the underlying distribution. If you know how to tell what is noise from what is real data, you must have learned something about the true data distribution. This provides an alternative way to learn probability distributions by transforming the density estimation problem into a binary classification problem between real and noise samples. ...

Parzen window estimate is also known as the kernel density estimate Basic idea Recall that we had derived the following equation for non-parametric density estimation: $$p(x) = \frac{k}{nV}$$ where: $k$ is the number of data points in region $R$ $n$ is the total number of data points in the dataset $D$ $V$ is the volume of the region $R$ In Parzen window estimate, we fix the volume $V$ and count $k$ by using a window function. ...

In value iteration, we were focused on finding the optimal value function $J^*$. In policy iteration, we start with a random policy and then improve it iteratively. Algorithm Description Policy iteration alternates between two main steps: Policy Evaluation: Given a policy $\mu_k$, compute its cost-to-go vector $J^{\mu_k}$ by solving the system of linear equations: $$ J^{\mu_k}(i) = \sum_{j=1}^n p_{ij}(\mu_k(i))(g(i,\mu_k(i),j) + J^{\mu_k}(j)) \quad i=1,\ldots,n $$ where $J^{\mu_k}(1), J^{\mu_k}(2), \ldots, J^{\mu_k}(n)$ are the unknowns to be solved for. This is equivalent to solving the fixed point equation: $$ J^{\mu_k} = T_{\mu_k}J^{\mu_k} $$ Policy Improvement: Given the cost-to-go vector $J^{\mu_k}$, find an improved policy $\mu_{k+1}$ by: $$ \mu_{k+1}(i) = \arg\min_{u \in \mathcal{A}(i)} \sum_{j=1}^n p_{ij}(u)(g(i,u,j) + J^{\mu_k}(j)) \quad \forall i=1,\ldots,n $$ This is equivalent to: $$ T_{\mu_{k+1}}J^{\mu_k} = TJ^{\mu_k} $$ ...

Proposition: Optimality Conditions in Policy Iteration Let’s examine a fundamental proposition that establishes optimality conditions for policy iteration in infinite horizon discounted cost problems. This proposition provides crucial insights into why policy iteration converges to optimal policies. Statement of the Proposition Consider a stationary policy $\bar{\mu}$ that satisfies the Bellman optimality condition: $$ \underbrace{T_{\bar{\mu}}J^{\bar{\mu}} = TJ^{\bar{\mu}}}_{\substack{\text{Policy } \bar{\mu} \text{ achieves the minimum} \\ \text{in the Bellman equation for all states}}} $$ This can be expressed more explicitly for all states $i = 1,2,\ldots,n$ as: ...