ML-RECAP.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# COVARIANCE MATRIX (always squared and symmetric)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The covariance matrix is a mathematical matrix that summarizes the joint variability of two or more random variables. It provides a measure of how much two variables vary together, and is often used in statistical analysis and machine learning. The elements of the covariance matrix represent the covariances between pairs of variables, and the diagonal elements represent the variances of each variable. A positive covariance indicates that the variables tend to vary in the same direction, while a negative covariance indicates that the variables tend to vary in opposite directions."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These formulas are faster\n",
    "\n",
    "`(if each column is a sample)`:\n",
    "\n",
    "$$ \\Sigma = \\frac{1}{n}(X-\\mu)({X}-\\mu)^\\top $$\n",
    "\n",
    "`(if each row is a sample)`:\n",
    "\n",
    "$$ \\Sigma = \\frac{1}{n}(X-\\mu)^\\top({X}-\\mu) $$\n",
    "\n",
    "where:\n",
    "\n",
    "- $X$ is a matrix of samples (each row is a sample)\n",
    "- $\\mu$ is the mean of $X$\n",
    "- $n$ is the number of samples"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "but, alternatively, we could also do:\n",
    "\n",
    "$$ var(x) = \\frac {1}{n} \\cdot \\sum_{i=1}^n({x_i} - \\mu_x)^2 $$\n",
    "\n",
    "$$ var(y) = \\frac {1}{n} \\cdot \\sum_{i=1}^n({y_i} - \\mu_y)^2 $$\n",
    "\n",
    "$$ cov(x, y) = cov(y, x) = \\frac {1}{n} \\cdot \\sum_{i=1}^n({x_i} - \\mu_x)({y_i} - \\mu_y) $$"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Example:\n",
    "\n",
    "Consider the following \"design\" matrix $X$, in which **`each column`** is a sample:\n",
    "\n",
    "$$\n",
    "X = \\begin{matrix}\n",
    "\\begin{pmatrix}\n",
    "1 & -5 & 10 & 2 & -3 \\\\\n",
    "2 & 10 & -5 & -1 & 4\n",
    "\\end{pmatrix}\n",
    "\\end{matrix}\n",
    "$$\n",
    "\n",
    "This matrix is a D $\\times$ N matrix, where D is the number of dimensions and N is the number of samples (in this case, D = 2 and N = 5).\n",
    "\n",
    "The covariance matrix must be a D $\\times$ D matrix, so, in this case will be a 2 $\\times$ 2."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# PROJECTION OF A VECTOR ONTO A SUBSPACE \n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The below formula is correct to compute the projection of a vector $\\vec{x}$ onto a subspace $u$ generated by a unit vector $\\vec{u}$."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ \\mathbb{P}_{u}{x} = ({x}^T{u})\\vec{u} $$\n",
    "\n",
    "where:\n",
    "\n",
    "- $ ({x}^T{u}) $ indicates the length, and\n",
    "- $ \\vec{u} $ indicates the direction."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Saying that we can either maximize the length from the origin of the projected point onto the subspace or minimize the reconstruction error is the same thing.\n",
    "\n",
    "But why \"maximize\" ? Because we want to keep the variance high, in order to don't loose information.\n",
    "\n",
    "We will use the concept of \"maximize the length from the origin of the project point onto the subspace\", and in order to achieve this:\n",
    "\n",
    "$$ \\arg\\max_{\\mathbf{u}} \\frac{1}{N}\\sum_i^N \\left\\|   \\mathbb{P}_{\\mathbf{u}}\\mathbf{x}_i \\right\\|_2^2 $$\n",
    "\n",
    "- The **size** of the projection is measured with the $\\ell_2^2$ norm:\n",
    "\n",
    "$$ || \\mathbb{P}_{\\mathbf{u}}\\mathbf{x}||_2^2 = ||X||\\cdot|cos\\theta|$$\n",
    "\n",
    "since $ ||u||_2 = 1 $ and $ \\theta $ is the angle between $X$ and $u$."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CENTERING A CLOUD OF POINTS (in order to get rid of offsets)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Centering a cloud of points in machine learning is a good practice because it can help to improve the accuracy and convergence of certain algorithms, particularly those that involve optimization or distance calculations.\n",
    "\n",
    "To center a cloud of points, we need to subtract the empirical mean from each point.\n",
    "\n",
    "NOTE: the empirical mean that we compute by considering the design matrix $X$"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In Python, would be something like: \n",
    "\n",
    "```python\n",
    "X-X.mean(axis=0)\n",
    "```\n",
    "\n",
    "where \"axis=0\" is the x-axis."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# ROTATION MATRIX (orthogonal matrix) ~ LINEAR TRANSFORMATION"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To obtain the rotation matrix $R$:\n",
    "\n",
    "Given the covariance matrix $\\sum$, we do eigendecomposition:\n",
    "\n",
    "1. Compute the eigenvectors & eigenvalues of $\\sum$;\n",
    "2. Arrange the eigenvectors in descending order into a matrix $V$. The order is given by the associated eigenvalues.\n",
    "3. Do the transpose of $V$ in order to obtain the inverse of $V$.\n",
    "\n",
    "$V^T$ = $V^{-1}$\n",
    "\n",
    "4. The rotation matrix $R$ can be obtained as $R = V^{-1} \\cdot V^\\top$"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall that, the rotation matrix $R$ is orthogonal, so $R^\\top = R^{-1}$ and also that $R^\\top \\cdot R = I$."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall that, after a rotation, the covariance matrix is diagonal, which means the covariance matrix is decorrelated."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# SPHERING"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The concept of sphering is used in machine learning to transform data into a new coordinate system where the features are uncorrelated and have equal variances. This transformation is achieved by applying a linear transformation to the original data, followed by scaling each feature by its standard deviation.\n",
    "\n",
    "The resulting transformed data is often referred to as \"sphered\" data, because the covariance matrix of the data is a diagonal matrix with all diagonal elements equal to one. In other words, the data has been transformed into a sphere in the new coordinate system.\n",
    "\n",
    "The motivation behind sphering is that many machine learning algorithms, such as principal component analysis (PCA) and linear discriminant analysis (LDA), perform better on data that is uncorrelated and has equal variances. Sphering is also useful for removing the effect of different scales and units between the features, which can distort the geometry of the data and affect the performance of certain algorithms.\n",
    "\n",
    "Overall, sphering is a useful pre-processing step in machine learning that can help to improve the performance of certain algorithms by transforming the data into a more suitable coordinate system."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sphering means that the data is centered, rotated and then scaled on the x-axis by the quare root of the eigenvalues. More formally, this is the formula:\n",
    "\n",
    "$$ X_{sphr} = \\Sigma^{-1/2} \\cdot U^\\top \\cdot (X - \\mu)^\\top $$\n",
    "\n",
    "where:\n",
    "\n",
    "- $ \\Sigma $ is the covariance matrix (diagonal matrix of eigenvalues);\n",
    "- $ U $ is the matrix of eigenvectors (principal components). Recall that the eigenvectors are the directions of the principal components and that can be obtained by doing the eigendecomposition of the centered covariance matrix;\n",
    "- $ \\bar{X} $ is the centered data matrix. We obtain it by subtracting the empirical mean from each point.\n",
    "\n",
    "Recall that, after a rotation, the covariance matrix is diagonal (identity), which means the covariance matrix is decorrelated."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TRANSFORMING A UNIT CIRCLE INTO AN ELLIPSOID"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In machine learning, circles can be stretched to become ellipsoids when the data is not linearly separable in the original feature space, but becomes linearly separable in a higher-dimensional feature space.\n",
    "\n",
    "This phenomenon is known as the \"kernel trick\", and it is commonly used in support vector machines (SVMs) and other kernel-based machine learning algorithms. The basic idea is to transform the original data into a higher-dimensional feature space using a non-linear function called a \"kernel function\", and then find a linear boundary that separates the transformed data.\n",
    "\n",
    "In the transformed feature space, a circle in the original feature space may become stretched or distorted into an ellipsoid, because the kernel function may map the original data points to new locations that are not equidistant from the origin.\n",
    "\n",
    "However, the important thing is that the linear boundary in the transformed feature space can still separate the transformed data points, even if they are not equidistant from the origin. This means that the original data is now separable by a non-linear boundary, which can be more powerful than a linear boundary in certain cases.\n",
    "\n",
    "Overall, stretching circles into ellipsoids is a common occurrence in machine learning when using the kernel trick to transform the data into a higher-dimensional feature space, and it can be a powerful technique for achieving non-linear separation of the data."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall that the area of the unit circle (radius 1) is $\\pi$, instead of $\\pi r^2$.\n",
    "\n",
    "Let $ X = \\begin{matrix} \\begin{pmatrix} 2 & 1 \\\\ 1 & 2 \\end{pmatrix} \\end{matrix} $ and DET($X$) = 3.\n",
    "\n",
    "If we transform the vector subspace in which the unit circle is contained (stretching in this way also the unit circle), the area of the ellipsoid will be DET($X$) $\\cdot \\pi$.\n",
    "\n",
    "This concept works fine in an N-dimensional space too if the given matrix, in this case $X$, is a square matrix.\n",
    "\n",
    "If the Determinant equals zero, the matrix is singular (not invertible) and the transformation is not possible, hence the unit circle gets squished into a line."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# STRETCHING CIRCLES INTO ELLIPSOIDS VS. SPHERING IN ML"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "While stretching circles into ellipsoids through the kernel trick and sphering are both techniques used in machine learning to transform data, they serve different purposes and operate in different ways.\n",
    "\n",
    "Sphering is a technique used to transform data into a new coordinate system where the features are uncorrelated and have equal variances. This transformation is achieved by applying a linear transformation to the original data, followed by scaling each feature by its standard deviation. The resulting transformed data is often referred to as \"sphered\" data, because the covariance matrix of the data is a diagonal matrix with all diagonal elements equal to one.\n",
    "\n",
    "The kernel trick, on the other hand, is a technique used to transform data into a higher-dimensional feature space using a non-linear function called a \"kernel function\". This transformation allows for non-linear separation of data that may be difficult or impossible to separate in the original feature space.\n",
    "\n",
    "While sphering and the kernel trick both involve transformations of the data, they serve different purposes and operate in different ways. Sphering is primarily used to reduce correlations between features and remove the effect of different scales and units between features, while the kernel trick is primarily used to transform data into a higher-dimensional space where it may be more easily separable."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3DMM (3D Morphable Model)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A 3D Morphable Model is a statistical model of 3D shapes and textures that can be used to represent and manipulate variations in facial features. It is typically constructed from a set of 3D scans or photographs of faces with varying identities, expressions, and poses.\n",
    "\n",
    "The model consists of two parts: a shape model and a texture model. The shape model captures the variations in the geometry of the face, while the texture model captures the variations in the color and texture of the face.\n",
    "\n",
    "Once the model is constructed, it can be used to perform a variety of tasks, such as 3D face reconstruction, face recognition, face tracking, and facial expression analysis. By manipulating the parameters of the model, it is possible to generate realistic 3D facial images that can be used for a variety of applications in computer vision and graphics."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To do this kind of stuff, we need to find the Principal Components of the data (usually given as a covariance matrix $X$).\n",
    "\n",
    "The Principal Components are the directions of the maximum variance of the data and correspond to the eigenvectors of the centered covariance matrix.\n",
    "\n",
    "Recall that the Principal Components are order by the eigenvalues in descending order.\n",
    "\n",
    "The eigenvector associated to the highest eigenvalue is the direction of the maximum variance of the data (PC1) and, if modified by a scalar, it will change the variance of the data in a significant way.\n",
    "\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ S' = \\hat{S} + \\alpha \\cdot U_i $$\n",
    "\n",
    "where:\n",
    "\n",
    "- $ \\hat{S} $ is the average shape;\n",
    "- $ \\alpha_i $ is the shape coefficient;\n",
    "- $ U_i $ is the shape basis (the eigenvector associated to the largest eigenvalue)."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CLUSTERING (unsupervised learning)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Clustering is a technique used in machine learning to group similar data points together based on their features or characteristics. Clustering is used in machine learning for a variety of reasons:\n",
    "\n",
    "1. Data exploration and understanding: Clustering can be used to explore and gain a better understanding of the underlying structure of a dataset. By grouping similar data points together, we can identify patterns and trends in the data that may not be immediately apparent.\n",
    "\n",
    "2. Data pre-processing: Clustering can be used as a pre-processing step to group similar data points together before applying other machine learning techniques. This can help to reduce noise and dimensionality in the data, and make it easier to model.\n",
    "\n",
    "3. Anomaly detection: Clustering can be used to detect outliers or anomalies in the data. Data points that do not belong to any of the clusters may be considered as potential outliers.\n",
    "\n",
    "4. Customer segmentation: Clustering can be used in marketing to group customers based on their behavior or preferences. This can help to tailor marketing strategies to specific groups of customers.\n",
    "\n",
    "5. Image segmentation: Clustering can be used to segment images into regions that are similar in color or texture. This can be useful in computer vision applications such as object recognition and tracking."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Image segmentation: Clustering can be used to segment images into regions that are similar in color or texture. This can be useful in computer vision applications such as object recognition and tracking."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### K-MEANS ALGORITHM STEPS"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. **Initialization:** `RANDOM` sample the $K$ centroids $\\{ {\\mu}_1, \\ldots, {\\mu}_k\\}$. A trick is using available points (just choose a few of them).\n",
    "\n",
    "- This random initialization can be far from the optimal solution.\n",
    "\n",
    "2. **Assignment:** assign each point to the closest centroid. \n",
    "\n",
    "- `VARIANCE MINIMIZER OBJECTIVE FUNCTION` $\\longrightarrow$ min $ \\mu, x =  \\sum_{i}^{N} || {x}_i -{\\mu}_k ||_2^2 $.\n",
    "\n",
    "- At the end of this step we should have a pair of aligned set $\\{ {x}_1, \\ldots, {x_n}\\}$ and $\\{ {y}_1, \\ldots, {y_n}\\}$.\n",
    "\n",
    "3. **Update:** \n",
    "\n",
    "- Now, it is the **inverse** of before. Now we consider the \"centroids\".\n",
    "- For every centroid $k=[1,\\ldots,K]$ **we center it**. How ? We compute the mean of all the points that are assigned to that centroid.\n",
    "\n",
    "- At the end of this step we should have a pair of aligned set $\\{ {x}_1, \\ldots, {x_n}\\}$ and $\\{ {y}_1, \\ldots, {y_n}\\}$ and **updated centroids** $\\{ {\\mu}_1, \\ldots, {\\mu}_k\\}$."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# INVERSE TRANSFORM SAMPLING"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Inverse transform sampling is a probabilistic method used in machine learning to generate random samples from a given probability distribution. The method relies on the cumulative distribution function (CDF) of the distribution to generate the samples.\n",
    "\n",
    "To use inverse transform sampling, we need to first compute the CDF of the probability distribution we want to sample from. The CDF gives the probability that a random variable takes a value less than or equal to a given value. We can use this information to generate random samples from the distribution.\n",
    "\n",
    "The steps to use inverse transform sampling are as follows:\n",
    "\n",
    "1. Choose a probability distribution that you want to sample from. This could be any probability distribution, such as a normal distribution, uniform distribution, or any other distribution.\n",
    "\n",
    "2. Compute the cumulative distribution function (CDF) of the chosen probability distribution. The CDF gives the probability that a random variable takes a value less than or equal to a given value. It is defined as the integral of the probability density function (PDF) from negative infinity to the given value. The CDF is a monotonically increasing function that ranges from 0 to 1.\n",
    "\n",
    "3. Generate a uniform random variable U between 0 and 1. This can be done using any method for generating random numbers in the range [0, 1], such as using a pseudorandom number generator.\n",
    "\n",
    "4. Use the inverse of the CDF to compute the corresponding value of the random variable X that corresponds to the probability U. This step is the core of inverse transform sampling. To do this, we take the inverse of the CDF, which gives us a function that maps probabilities to corresponding values of X. We then apply this inverse function to U to get a value of X that corresponds to the probability U.\n",
    "\n",
    "5. Repeat steps 3 and 4 as many times as necessary to generate the desired number of random samples. Each time step 4 is performed, we generate a new value of X that corresponds to a different probability U. By repeating this process many times, we can generate a large number of random samples from the desired probability distribution."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### K-MEANS ++ ALGORITHM STEPS"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "K-Means++ is an improvement over the original K-Means algorithm that helps to choose better initial centroids for the clusters. In the standard K-Means algorithm, the initial centroids are chosen randomly from the data points. However, this can lead to poor results if the initial centroids are chosen poorly.\n",
    "\n",
    "K-Means++ addresses this problem by using a more sophisticated initialization procedure. The algorithm chooses the first centroid randomly from the data points, and then chooses subsequent centroids based on the distance to the previously chosen centroids. Specifically, the next centroid is chosen with a probability proportional to the distance squared from each data point to the nearest centroid that has already been chosen.\n",
    "\n",
    "By using this initialization procedure, K-Means++ is able to choose centroids that are more spread out and representative of the data, which leads to better clustering results compared to the standard K-Means algorithm."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Choose the first centroid randomly from the data points.\n",
    "\n",
    "- For each data point, compute the distance to the nearest centroid that has already been chosen.\n",
    "\n",
    "- Choose the next centroid from the data points, with a probability proportional to the squared distance to the nearest centroid.\n",
    "\n",
    "- Repeat steps 2 and 3 until K centroids have been chosen.\n",
    "\n",
    "By selecting the initial centroids in this way, K-Means++ ensures that the initial centroids are well spread out and that they are likely to represent different clusters. This helps to avoid the problem of K-Means getting stuck in local optima or converging to suboptimal clusterings.\n",
    "\n",
    "After the initialization step, K-Means++ proceeds in the same way as K-Means. It iteratively assigns each data point to the nearest centroid, and then updates the centroids based on the mean of the assigned data points. The algorithm repeats until convergence or a maximum number of iterations is reached."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Choose ${\\mu}_1$ arbitrarily between data points.\n",
    "2. For $k=[2,\\ldots,K]$:\n",
    "    - **Inverse Transform Sampling** w.r.t. to distances between centroids\n",
    "    - $Pr[{\\mu}_k={x}_m] \\propto \\min_{k<k^{\\prime}} \\left| \\left| {x}_m - {\\mu}_k^{\\prime}\\right|\\right|_2^2 \\qquad$\n",
    "3. Repeat Lloyd’s method until convergence :\n",
    "    - **Assignment step:** $\\forall i\\in[1,N] \\quad y_i =  \\arg\\min_k || {x}_i -{\\mu}_k ||_2^2 $\n",
    "    - **Update step:** $\\forall k\\in[1,K] \\quad  {\\mu}_k \\leftarrow \\frac{\\sum_i \\delta\\{y_i=k\\}{x}_i}{\\sum_i \\delta\\{y_i=k\\}}$"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# GMM (Gaussian Mixture Model)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### MODES"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The modes are given by the eigenvalues of the covariance matrix. The number of modes is given by the number of non-zero eigenvalues.\n",
    "\n",
    "`The n. of modes can be easily deduced from the text of the problem`.\n",
    "\n",
    "Example: if the problem says that the data is generated by a mixture of 2 Gaussians, then the number of modes is 2.\n",
    "\n",
    "Usually, the modes are the cardinality of Z --> $|Z|$ or the cardinality of the responsability vector --> $|\\gamma|$.\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### PROBABILITY DENSITY FUNCTION"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The probability density function is a function that describes the relative likelihood for a given random variable to take on a given value. It is a function of the random variable and is often denoted by $f(x)$ or $p(x)$.\n",
    "\n",
    "It is a linear combination of Gaussian distributions, which is called a Gaussian mixture model. The Gaussian mixture model is a probabilistic model that assumes all the data points are generated from a mixture of a finite number of Gaussian distributions with unknown parameters.\n",
    "\n",
    "The linear combination between coefficients and mixing coefficients indicates also a categorical distribution $\\pi$. If the modes are $K$, then the categorical distribution is a $K$-dimensional vector and we have that $\\sum_{k=1}^K \\pi_{\\hat{k}} = 1$, with $\\pi_{\\hat{k}} \\geq 0$.\n",
    "\n",
    "Each Gaussian distribution is characterized by a mean $\\mu_k$ and a covariance matrix $\\Sigma_k$. \n",
    "\n",
    "The probability density function is given by:\n",
    "\n",
    "$$ p(x) = \\sum_{\\hat{k}=1}^K \\pi_{\\hat{k}} \\cdot \\mathcal{N}(x | \\mu_{\\hat{k}}, \\Sigma_{\\hat{k}}) $$\n",
    "\n",
    "where:\n",
    "\n",
    "- $\\mathcal{N}(x|\\mu_{\\hat{k}}, \\Sigma_{\\hat{k}})$ is the probability density function of a Gaussian distribution with mean $\\mu_{\\hat{k}}$ and covariance matrix $\\Sigma_{\\hat{k}}$.\n",
    "\n",
    "A Mixture of Gaussians (MoG) is a way of representing a more complex data distribution by combining several simpler ones, specifically, Gaussian distributions. You can think of it as creating a multi-hill landscape (our complex data distribution), by stacking several small mounds (the simpler Gaussian distributions) on top of each other.\n",
    "\n",
    "Each of these simpler Gaussian distributions (mounds) has:\n",
    "\n",
    "A \"center\" known as the mean (where the top of the mound is).\n",
    "A \"spread\" known as the covariance (how wide or narrow the mound is).\n",
    "Then, each Gaussian distribution is given a certain \"weight\". This means we decide how much each Gaussian distribution contributes to the overall landscape.\n",
    "\n",
    "The sum of all these weighted Gaussian distributions gives us the final complex distribution that we call a Mixture of Gaussians.\n",
    "\n",
    "It's a useful technique when the data we're dealing with doesn't neatly follow a simple distribution, but rather a combination of several. It's used in many areas such as machine learning and image processing.\n",
    "\n",
    "1. The \"weight\" of each Gaussian component in the mixture refers to the proportion or contribution of that component to the overall model. Each Gaussian has a certain \"weight\" that represents how much that specific Gaussian distribution contributes to the total mixture model. These weights must add up to 1, as they essentially represent the probability of a data point belonging to a certain Gaussian in the mixture.\n",
    "\n",
    "2. The \"density\" in the context of Gaussian distributions typically refers to the probability density function (PDF) of a particular Gaussian distribution. The PDF for a Gaussian (or normal) distribution is the familiar \"bell curve\" shape, and it gives you the probability of a random variable taking on a specific value."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## EM (Expectation-Maximization) ALGORITHM IN THE CONTEXT OF GMM (Gaussian Mixture Model)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### EXPECTATION STEP (RESPONSABILITIES)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The responsibility index is a key concept in the context of Gaussian Mixture Models (GMMs). In a GMM, we assume that the data is generated from a mixture of Gaussian distributions. The responsibility index is a measure of how responsible each Gaussian component is for generating each data point.\n",
    "\n",
    "The responsibility index can be used in various ways in GMMs. One common use is in the Expectation-Maximization (EM) algorithm for fitting GMMs to data. In the E-step of the EM algorithm, the responsibility index is computed for each data point and each Gaussian component. In the M-step, the parameters of the Gaussian components (i.e., mean, covariance matrix, and mixture weights) are updated based on the computed responsibility indices.\n",
    "\n",
    "Another use of the responsibility index is in model selection for GMMs. By comparing the values of the responsibility indices across different numbers of Gaussian components, one can determine the optimal number of components to use in the GMM. Specifically, one can use metrics such as the Bayesian Information Criterion (BIC) or the Akaike Information Criterion (AIC) to evaluate the fit of GMMs with different numbers of components and choose the model with the best balance of goodness-of-fit and complexity."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The responsability vector $\\gamma_k $ indicates the probability that a point $x$ may have been generated by the $k$-th Gaussian distribution."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ \\gamma = p(z == \\hat{k} | x) = \\frac{\\mathcal{N} \\cdot (x | \\mu_{\\hat{k}}, \\sigma_{\\hat{k}})\\cdot \\pi_{\\hat{k}}}{\\sum_{\\hat{k}\\in |\\gamma|} \\cdot \\mathcal{N}(x | \\mu_{\\hat{k}}, \\sigma_{\\hat{k}})\\cdot \\pi_{\\hat{k}}} $$\n",
    "\n",
    "where:\n",
    "\n",
    "- $N(x; \\mu_{\\hat{k}}, \\sigma_{\\hat{k}})$ is the probability density function of the $k$-th Gaussian distribution;\n",
    "- $\\pi_{\\hat{k}}$ is the prior probability of the $k$-th Gaussian distribution.\n",
    "\n",
    "$\\pi_{\\hat{k}}$ are also called mixing coefficients.\n",
    "\n",
    "$\\gamma$[0] = 0.8 means that there's 80% probability that the point $x$ was generated by the first Gaussian distribution."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "EXAMPLE:\n",
    "\n",
    "Given x' as a new point, we want to compute the probability that it was generated by the first Gaussian distribution.\n",
    "\n",
    "We can use the Bayes' theorem as follows:\n",
    "\n",
    "$$ p(z_0 | x') = \\frac{p(x' | z_0) \\cdot p(z_0)}{\\sum_{k\\in |\\gamma|}{p(x'|z_{\\hat{k}})\\cdot (z_{\\hat{k}})}} $$\n",
    "\n",
    "where:"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### MAXIMIZATION STEP $\\longrightarrow$ AKA: ESTIMATE THE PROBABILITY DENSITY FUNCTION OF THE GMM AT THAT STEP OF THE ALGORITHM $\\longrightarrow$ AKA: ESTIMATE THE PARAMETERS OF THE GMM ($\\pi_{\\hat{k}}$, $\\mu_{\\hat{k}}$, $\\sigma_{\\hat{k}}$)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall that a GMM is a mixture of $k$ Gaussian distributions.\n",
    "\n",
    "In the context of Gaussian Mixture Models (GMMs), the maximization step is part of the Expectation-Maximization (EM) algorithm used for estimating the parameters of the GMM. The EM algorithm is an iterative method for finding maximum likelihood or maximum a posteriori (MAP) estimates of parameters in statistical models when the model depends on unobserved latent variables.\n",
    "\n",
    "The EM algorithm consists of two main steps: the Expectation (E) step and the Maximization (M) step. In the context of GMMs, the E step computes the posterior probabilities of the latent variables given the current estimates of the parameters. The M step, on the other hand, updates the estimates of the parameters to maximize the expected complete-data log-likelihood based on the posterior probabilities computed in the E step. This process is iteratively repeated until convergence.\n",
    "\n",
    "For a GMM with K components, the model parameters include the mixing coefficients ($\\pi$), the means ($\\mu$), and the covariance matrices ($\\sigma$) for each component. In the maximization step, the goal is to update these parameters according to the following formulas:\n",
    "\n",
    "$$ \\pi_{\\hat{k}} = \\frac{N_{\\hat{k}}}{N} $$\n",
    "\n",
    "$$ \\mu_{\\hat{k}} = \\frac{\\sum_{i=1}^N \\gamma_{i\\hat{k}} x_i}{N_{\\hat{k}}} $$\n",
    "\n",
    "$$ \\sigma_{\\hat{k}}^2 = \\frac{\\sum_{i=1}^N \\gamma_{i\\hat{k}} (x_i - \\mu_{\\hat{k}})(x_i - \\mu_{\\hat{k}})^2}{N_{\\hat{k}}} $$\n",
    "\n",
    "where:\n",
    "\n",
    "- $N$ is the total number of data points;\n",
    "- $N_{\\hat{k}}$ is the number of data points assigned to the $k$-th component;\n",
    "- $\\gamma_{i{\\hat{k}}}$ is the posterior probability of the $i$-th data point belonging to the $\\hat{k}$-th component.\n",
    "\n",
    "After updating the parameters in the M step, you return to the E step to recompute the posterior probabilities based on the updated parameters. This process is repeated until the change in the log-likelihood or the parameters falls below a predefined threshold, indicating convergence.\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### POSSIBLE PROBLEMS DURING THE EXECUTION OF THE EM ALGORITHM"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. The algorithm may not converge to the global maximum of the likelihood function. This is because the likelihood function is not concave. This means that there are multiple local maxima. The EM algorithm may converge to a local maximum instead of the global maximum;\n",
    "\n",
    "2. `The algorithm may converge to a singular solution. This is because the likelihood function is not differentiable (not convex) at the singular points. In this case the log-likelihood function goes to infinity at the singular points and the algorithm may not converge at all`;\n",
    "\n",
    "3. The algorithm may converge to a solution that is not a maximum. This is because the likelihood function is not convex. The EM algorithm may converge to a point that is not a maximum instead of a maximum.\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### SAMPLING FROM THE GENERATIVE MODEL BEHIND THE GMM"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The generative model behind the GMM is a mixture of $\\hat{k}$ Gaussian distributions. The generative model can be used to generate new data points from the GMM. This is done by sampling from the mixture of Gaussian distributions. The sampling process is as follows:\n",
    "\n",
    "1. Sample the index of the Gaussian from which to sample the data point. This is done by sampling from a categorical distribution with probabilities equal to the mixing coefficients $\\pi_{\\hat{k}}$. We can do this by sampling from a uniform distribution and then using the cumulative distribution function (CDF) of the categorical distribution to determine the index of the Gaussian from which to sample the data point (in other words, we can use the inverse CDF of the categorical distribution to determine the index of the Gaussian from which to sample the data point).\n",
    "- $\\hat{k} \\sim \\mathcal{Categorical}(\\pi_1, \\pi_2, \\dots, \\pi_{\\hat{k}})$\n",
    "\n",
    "2. Sample the data point from the Gaussian distribution with the sampled index. \n",
    "- $x \\sim \\mathcal{N}(x|\\mu_{\\hat{k}}, \\sigma_{\\hat{k}})$"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# `SUPERVISED LEARNING`"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## CLASSIFICATION & REGRESSION"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### K-NEAREST NEIGHBORS (KNN)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "K-nearest neighbor (K-NN) is a non-parametric machine learning algorithm that can be used for both classification and regression tasks. The K-NN algorithm is based on the idea that similar data points tend to have similar labels or values. Therefore, when a new data point is given, K-NN algorithm identifies the K-nearest neighbors of the new data point and assigns the label or value of the majority of those neighbors as the predicted label or value for the new data point.\n",
    "\n",
    "The K in K-NN represents the number of nearest neighbors that are considered for making the prediction. The value of K can be chosen by the user, and a larger K results in a smoother decision boundary but may lead to poorer performance on complex datasets.\n",
    "\n",
    "To apply the K-NN algorithm, the first step is to define a distance metric to measure the similarity between the data points. The most commonly used distance metric is the Euclidean distance. Once the distance metric is defined, the algorithm finds the K-nearest neighbors of the new data point based on the distance metric. The predicted label or value of the new data point is then determined by the majority of the labels or values of the K-nearest neighbors.\n",
    "\n",
    "K-NN can also be used for regression problems, where the predicted value is the mean of the values of the K-nearest neighbors.\n",
    "\n",
    "One of the advantages of K-NN is that it is a simple algorithm to understand and implement, and it does not require training on the data. However, its performance can be affected by the choice of distance metric, the value of K, and the curse of dimensionality, where the algorithm becomes less effective as the number of dimensions in the feature space increases."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a training set of $n$ data points $ { (x_1, y_1), (x_2, y_2), ..., (x_n, y_n) } $ where $x_i$ is the $i$-th data point and $y_i$ is its associated label or value, and a new data point $x_q$:"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Define a distance metric $d(x, x')$ that measures the distance between two data points $x$ and $x'$. The most commonly used distance metric is the Euclidean distance, which is given by:\n",
    "\n",
    "$$ d(x, x') = \\sqrt{ \\sum_{i=1}^{d} (x_i - x'_i)^2 } $$\n",
    "\n",
    "where $x_i$ and $x'_i$ are the $i$-th feature of $x$ and $x'$, respectively.\n",
    "\n",
    "2. Calculate the distance between $x_q$ and all the training data points:\n",
    "\n",
    "$$ dist(x_q, x_i) = d(x_q, x_i) $$\n",
    "\n",
    "3. Identify the $K$-nearest neighbors of $x_q$ based on the calculated distances:\n",
    "\n",
    "$$ N_q = \\{ x_i | \\mathrm{dist}(x_q, x_i) \\leq \\mathrm{kth_{smallest}}( \\mathrm{dist}(x_q, x_1), \\mathrm{dist}(x_q, x_2), \\dots, \\mathrm{dist}(x_q, x_n) ) \\} $$\n",
    "\n",
    "where $kth_{smallest}()$ returns the $K$-th smallest element in a list of distances.\n",
    "\n",
    "4. Assign the label or value of the majority of the $K$-nearest neighbors as the predicted label or value for $x_q$:\n",
    "\n",
    "$$ y_q = \\arg\\max_{y_i} \\sum_{x_i \\in N_q} [y_i = y] $$\n",
    "\n",
    "where $\\arg\\max_{y_i}$ returns the label or value that occurs the most in the set of $K$-nearest neighbors $N_q$. If there is a tie, the label or value that occurs first in the set of $K$-nearest neighbors $N_q$ is returned.\n",
    "\n",
    "For regression tasks, the predicted value $y_q$ is the mean of the values of the $K$-nearest neighbors:\n",
    "\n",
    "$$ y_q = \\frac{1}{K} \\sum_{x_i \\in N_q} y_i $$"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### DECISION TREES"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Decision trees are a type of supervised learning algorithm used for classification and regression tasks. The basic idea behind decision trees is to split the dataset into smaller and smaller subsets while making decisions about which feature to use for splitting at each level of the tree, until a stopping criterion is reached. Each split creates a node in the tree, which represents a decision based on a particular feature and its corresponding threshold value.\n",
    "\n",
    "Here are the steps for building a decision tree:\n",
    "\n",
    "1. Choose the best feature to split the data based on some measure of impurity, such as the Gini impurity or entropy;\n",
    "\n",
    "2. Split the data into subsets based on the selected feature and its threshold value;\n",
    "\n",
    "3. Recursively apply steps 1 and 2 to each subset until a stopping criterion is reached. This could be a maximum depth of the tree, a minimum number of samples per leaf node, or some other rule;\n",
    "\n",
    "4. Assign a label or value to each leaf node of the tree based on the majority class or the mean value of the samples in that node.\n",
    "\n",
    "Once the decision tree is built, we can use it to make predictions for new data points by following the path from the root node to a leaf node based on the values of the features."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let $\\mathcal{D}$ be the training dataset with $n$ samples and $d$ features. Let $\\mathcal{Y}$ be the set of possible class labels for classification tasks, or a continuous range of values for regression tasks.\n",
    "\n",
    "1. At each node of the decision tree, select the feature $x_j$ and the threshold value $t$ that maximally reduces the impurity of the dataset, based on some impurity measure $H(\\cdot)$:\n",
    "\n",
    "$$ (j,t) = \\arg\\min_{j \\in \\{1,\\dots,d\\}, t} H(\\mathcal{D}; j,t) $$\n",
    "\n",
    "2. Split the dataset $\\mathcal{D}$ into two subsets $\\mathcal{D}\\mathrm{left}$ and $\\mathcal{D}\\mathrm{right}$ based on the selected feature and threshold:\n",
    "\n",
    "$$ \\begin{aligned} \\mathcal{D}_\\mathrm{left} &= \\{ (\\mathbf{x},y) \\in \\mathcal{D} : x_j \\leq t \\} \\\\ \\mathcal{D}_\\mathrm{right} &= \\{ (\\mathbf{x},y) \\in \\mathcal{D} : x_j > t \\} \\end{aligned} $$\n",
    "\n",
    "3. Recursively apply steps 2 and 3 to each subset until a stopping criterion is reached. This could be a maximum depth of the tree, a minimum number of samples per leaf node, or some other rule.\n",
    "\n",
    "4. Assign a label or value to each leaf node of the tree based on the majority class or the mean value of the samples in that node:\n",
    "\n",
    "$$ y_\\mathrm{leaf} = \\begin{cases} \\mathrm{mode}(\\{ y_i : (\\mathbf{x}_i,y_i) \\in \\mathcal{D}_\\mathrm{leaf} \\}) & \\text{for classification} \\\\ \\mathrm{mean}(\\{ y_i : (\\mathbf{x}_i,y_i) \\in \\mathcal{D}_\\mathrm{leaf} \\}) & \\text{for regression} \\end{cases} $$\n",
    "\n",
    "The impurity measure $H(\\cdot)$ used for step 2 could be the Gini impurity for classification tasks, which is defined as:\n",
    "\n",
    "$$ H_\\mathrm{Gini}(\\mathcal{D}; j,t) = \\frac{|\\mathcal{D}_\\mathrm{left}|}{|\\mathcal{D}|} \\cdot \\mathrm{Gini}(\\mathcal{D}_\\mathrm{left}) + \\frac{|\\mathcal{D}_\\mathrm{right}|}{|\\mathcal{D}|} \\cdot \\mathrm{Gini}(\\mathcal{D}_\\mathrm{right}) $$\n",
    "\n",
    "where $\\mathrm{Gini}(\\mathcal{D})$ is the Gini impurity of the dataset $\\mathcal{D}$, defined as:\n",
    "\n",
    "$$ \\mathrm{Gini}(\\mathcal{D}) = \\sum_{y \\in \\mathcal{Y}} p(y) (1 - p(y)) $$\n",
    "\n",
    "with $p(y)$ being the fraction of samples in $\\mathcal{D}$ that belong to class $y$.\n",
    "\n",
    "The Gini impurity is a measure of the probability of misclassifying a randomly chosen sample from the dataset $\\mathcal{D}$.\n",
    "\n",
    "For regression tasks, the impurity measure $H(\\cdot)$ could be the mean squared error (MSE), defined as:\n",
    "\n",
    "$$ H_\\mathrm{MSE}(\\mathcal{D}; j,t) = \\frac{1}{|\\mathcal{D}|} \\left( \\sum_{(\\mathbf{x},y) \\in \\mathcal{D}_\\mathrm{left}} (y - y_\\mathrm{left})^2 + \\sum_{(\\mathbf{x},y) \\in \\mathcal{D}_\\mathrm{right}} (y - y_\\mathrm{right})^2 \\right) $$\n",
    "\n",
    "where $y_\\mathrm{left}$ and $y_\\mathrm{right}$ are the mean values of the samples in $\\mathcal{D}_\\mathrm{left}$ and $\\mathcal{D}_\\mathrm{right}$, respectively.\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}