notes_05_the_mysterious_phi_x.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    },
    "gpuClass": "standard"
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "#### Transformation $\\phi(x)$ as virtual sample"
      ],
      "metadata": {
        "id": "EKenkxIndQaI"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "When we are doing kernel method, we say that the transformation $\\phi(x)$ should satisfy\n",
        "\n",
        "$$\\boxed{\\phi(x)^T \\phi(x')=k(x, x')=e^{-\\frac{(x-x')^2}{2\\sigma_k^2}}}$$\n",
        "\n",
        "To get $\\phi(x)$, we assume that we have $m$ data points: $x_1, x_2, ..., x_m$\n",
        "\n",
        "We know how to compute the correlation between each pair, it gives us a matrix $X_k$ where the `ith row` and the `jth column` is\n",
        "\n",
        "$$e^{-\\frac{(x_i-x_j)^2}{2\\sigma_k^2}}$$\n",
        "\n",
        "Now, assume we write out all transformed $x_i$ ($i=1, 2,..., m$) as following\n",
        "\n",
        "$$F=\\begin{bmatrix} ---\\phi(x_1)^T--- \\\\ ---\\phi(x_2)^T--- \\\\ ... \\\\ ---\\phi(x_m)^T--- \\end{bmatrix}$$\n",
        "\n",
        "This matrix has $m$ rows and each row corresponds to a `(transposed) transformation` of $x$: $\\phi(x)^T$"
      ],
      "metadata": {
        "id": "4cmnNqvLz2qP"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "As a result, $F$ and its transpose $F^T$ must satisfy the condition of preservation of correlation:\n",
        "\n",
        "$$F F^T=\\begin{bmatrix} ---\\phi(x_1)^T--- \\\\ ---\\phi(x_2)^T--- \\\\ ... \\\\ ---\\phi(x_m)^T--- \\end{bmatrix}\\begin{bmatrix} | & | & ... & | \\\\ | & | & ... & | \\\\ \\phi(x_1)& \\phi(x_2) & ... & \\phi(x_m) \\\\ | & | & ... & | \\\\ | & | & ... & | \\end{bmatrix} = X_k$$\n",
        "\n",
        "We decompose $X_k$ as\n",
        "\n",
        "$$X_k = U\\Lambda U^T$$\n",
        "\n",
        "where the `ith column` in $U$ contains the `ith eigenvector` of $X_k$ and $\\Lambda$ contains corresponding `eigenvalues` of $X_k$ in its diagonal and 0 off-diagonal.\n",
        "\n",
        "As $\\Lambda$ is symmetric, we can write\n",
        "\n",
        "$$X_k = U\\Lambda^{\\frac{1}{2}} \\Lambda^{\\frac{1}{2}}U^T=U\\Lambda^{\\frac{1}{2}} (\\Lambda^{\\frac{1}{2}})^T U^T = U\\Lambda^{\\frac{1}{2}} (U\\Lambda^{\\frac{1}{2}} )^T$$"
      ],
      "metadata": {
        "id": "6xt3hwtWjKoM"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "As a result, we have\n",
        "\n",
        "$$F=\\begin{bmatrix} ---\\phi(x_1)^T--- \\\\ ---\\phi(x_2)^T--- \\\\ ... \\\\ ---\\phi(x_m)^T--- \\end{bmatrix} = U\\Lambda^{\\frac{1}{2}}=\\begin{bmatrix} | & | & ... & | \\\\ | & | & ... & | \\\\ \\mathbf{u}_1& \\mathbf{u}_2 & ... & \\mathbf{u}_m \\\\ | & | & ... & | \\\\ | & | & ... & | \\end{bmatrix}\\begin{bmatrix} \\lambda_1^{\\frac{1}{2}} & 0 & ... & 0 \\\\ 0 & \\lambda_2^{\\frac{1}{2}} & ... & 0 \\\\  &   & ... &   \\\\  0 & 0 & ... & \\lambda_m^{\\frac{1}{2}} \\end{bmatrix}$$\n",
        "\n",
        "where the ith `row` of $U\\Lambda^{\\frac{1}{2}}$ represents $\\phi(x_i)^T$, which is of length $m$\n",
        "\n",
        "Now, $y=ax$ becomes\n",
        "\n",
        "$$y=\\phi(x)^T  \\theta$$\n",
        "\n",
        "and\n",
        "\n",
        "$$\\begin{align*}\n",
        "\\phi(x)^T&=\\begin{bmatrix}\\phi_1(x) & \\phi_2(x) & ... & \\phi_m(x)\\end{bmatrix} \\\\\\theta^T&=\\begin{bmatrix}\\theta_1 & \\theta_2 & ... & \\theta_m \\end{bmatrix}\n",
        "\\end{align*}$$\n",
        "\n",
        "We can call $\\phi(x)^T=\\begin{bmatrix}\\phi_1(x) & \\phi_2(x) & ... & \\phi_m(x)\\end{bmatrix}$ the `virtual sample` of $x$ based on eigendecomposition\n",
        "\n",
        "`So far, this is how we obtain` $\\phi(x)$"
      ],
      "metadata": {
        "id": "wMHRt3p5j-xT"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### BUT, is the virtual sample via eigendecomposition truly the `underlying` $\\phi(x)$ induced by RBF kernel?"
      ],
      "metadata": {
        "id": "drpkEColdXHL"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "We recall the kernel expression (and let $\\sigma_k=1$ for simplicity)\n",
        "\n",
        "$$\n",
        "k(x, x') = \\exp\\left( -\\frac{1}{2} (x^2 + x'^2 - 2xx') \\right) = \\exp\\left( -\\frac{1}{2} x^2 \\right) \\exp\\left( -\\frac{1}{2} x'^2 \\right)\\exp(xx')\n",
        "$$\n",
        "\n",
        "Recall `Taylor approximation` of $e^x$ at $x=0$:\n",
        "\n",
        "$$\\begin{align*}\n",
        "e^x &= e^0 + \\frac{e^0}{1!} (x - 0) + \\frac{e^0}{2!} (x - 0)^2 + \\cdots + \\frac{e^0}{n!} (x - 0)^n + \\cdots \\\\\n",
        "&= 1 + x + \\frac{1}{2}x^2 + \\cdots + \\frac{1}{n!}x^n + \\cdots\n",
        "\\end{align*}\n",
        "$$\n",
        "\n",
        "We use this expansion to replace $\\exp(xx')$ so that the initial formulation becomes:\n",
        "\n",
        "$$\n",
        "k(x, x') =\\exp\\left( -\\frac{1}{2} x^2 \\right) \\exp\\left( -\\frac{1}{2} x'^2 \\right) (1 + xx' + \\frac{1}{2}x^2x'^2 + \\cdots + \\frac{1}{n!}x^nx'^n + \\cdots)\n",
        "$$\n",
        "\n",
        "If we let $s=\\exp\\left( -\\frac{1}{2} x^2 \\right)$ and group $s$ with $x$ from each term in Taylor expansion, and let $s'=\\exp\\left( -\\frac{1}{2} x'^2 \\right)$ and group $s'$ with $x'$ from each term in Taylor expansion, we see $k(x,x')$ is actually a dot product from two `infinite-dimensional` vectors\n",
        "\n",
        "$$\n",
        "k(x, x') = [ s, sx, s\\sqrt{\\frac{1}{2}}x^2, \\cdots, s\\sqrt{\\frac{1}{n!}}x^n, \\cdots ] \\cdot [ s', s'x', s'\\sqrt{\\frac{1}{2}}x'^2, \\cdots, s'\\sqrt{\\frac{1}{n!}}x'^n, \\cdots ]\n",
        "$$\n",
        "\n",
        "However, we are never able to compute infinite-dimensional vectors directly. As one of solutions, the virtual samples we obtained earlier are `approximations` to the true $\\phi(x)$'s"
      ],
      "metadata": {
        "id": "kRtysUSGlSZf"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Potential issue"
      ],
      "metadata": {
        "id": "SvXotEIedZoU"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "As the $\\phi(x)$'s we obtained are not true ones, therefore, the information based on which we obtain these $\\phi(x)$'s matters, and this leads to the need for results correction in our computation"
      ],
      "metadata": {
        "id": "S-MXXN4Nkr7d"
      }
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "HfkArMpAdZH9"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}