Stanford_CS224N/01_Word_Vector.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "01_Word_Vector.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ISIzgYBbD0Ha",
        "colab_type": "text"
      },
      "source": [
        "# Reference\n",
        "\n",
        "- [Stanford CS224N: NLP with Deep Learning | Winter 2019 | Lecture 1 – Introduction and Word Vectors](https://www.youtube.com/watch?v=8rXD5-xhemo&list=PLoROMvodv4rOhcuXMZkNm7j3fVwBBY42z)\n",
        "- [Lecture notes](https://web.stanford.edu/class/archive/cs/cs224n/cs224n.1194/readings/cs224n-2019-notes01-wordvecs1.pdf)\n",
        "- [Lecture slides](http://web.stanford.edu/class/cs224n/slides/cs224n-2019-lecture01-wordvecs1.pdf)\n",
        "- [numpy.linalg.svd](https://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.svd.html)\n",
        "- [Lecture 47 — Singular Value Decomposition | Stanford University\n",
        "](https://www.youtube.com/watch?v=P5mlg91as1c)\n",
        "- [Lecture: The Singular Value Decomposition (SVD)](https://www.youtube.com/watch?v=EokL7E6o1AE)\n",
        "- [Singular Value Decomposition (the SVD)](https://www.youtube.com/watch?v=mBcLRGuAFUk)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Gzsgz21pDy_X",
        "colab_type": "text"
      },
      "source": [
        "# Very basic concept of NLP(?)\n",
        "\n",
        "Language is about compression (of information) -- I'd like to personally say that the communication is (by its nature) a form of (information) comparession.\n",
        "\n",
        "Historically, people have been considering \"word\" to convey \"meaning\". *Wordnet* could be considered as an example of \"localist\" approach, where each word is considered as each entry => limitation in order to represent the relationships between words ($N^2$ size table required in order to store (one type of) relationship between $N$ words). "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cRMi02yqsEqC",
        "colab_type": "text"
      },
      "source": [
        "# Distributional semantics\n",
        "\n",
        "Meaning of the word is determined by the context words (distributed representation). \n",
        "\n",
        "Such \"context\" could be represented with respect to the surrounding words of a word in question. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jYo0ND5yEo6l",
        "colab_type": "text"
      },
      "source": [
        "## Word as vector -- How should we represent?\n",
        "\n",
        "\"One-hot vector\" as the easiest approach. Of course, it not be an ideal approach in order to represent the relationships between words. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "u-PaA-jbIXNj",
        "colab_type": "text"
      },
      "source": [
        "### SVD (Singular Value Decomposition)\n",
        "\n",
        "Notes of the lecture starts with SVD as a (first) means to represent the relationships of the words in \"non-one-hot\" manner. \n",
        "\n",
        "SVD is composed as following: \n",
        "\n",
        "$\n",
        "A_{m\\times n} \\approx U_{m\\times r} \\Sigma_{r\\times r} (V_{n \\times r})^T\n",
        "$\n",
        "\n",
        ", where $r$ is size of the concept, usually a small number. Please note that it's an approximation (nearly equal) \n",
        "\n",
        "Following is a Python code snippet to demonstrate SVD (using NumPy function (for the time being..)."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "JPPW97XZh-Ut",
        "colab_type": "code",
        "outputId": "e1622939-5dea-4bdd-e8fe-9f4518094763",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 544
        }
      },
      "source": [
        "import numpy as np\n",
        "np.set_printoptions(suppress=True)\n",
        "\n",
        "# original value\n",
        "A = np.array=([\n",
        "               [1,1,1,3,0],\n",
        "               [3,3,3,0,0],\n",
        "               [4,4,4,0,0],\n",
        "               [5,5,5,0,0],\n",
        "               [0,2,0,4,4],\n",
        "               [0,0,0,5,5],\n",
        "               [0,1,0,2,2]\n",
        "])\n",
        "\n",
        "# compute SVD, give full_matrices=False for de-composition\n",
        "U,s,V = np.linalg.svd(A, full_matrices=False)\n",
        "print(\"U = \")\n",
        "print(U)\n",
        "print(\"\\nSigma = \")\n",
        "print(np.diag(s))\n",
        "print(\"\\nV = \")\n",
        "print(V)\n",
        "print('\\n-- Producing the original matrix.. --')\n",
        "print( np.dot(U, np.dot( np.diag(s), V ) ) )"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "U = \n",
            "[[-0.17300786  0.18701168  0.95659304  0.14150855 -0.        ]\n",
            " [-0.40633267 -0.10519243 -0.04696495 -0.0402816  -0.49339255]\n",
            " [-0.54177689 -0.14025658 -0.06261993 -0.0537088  -0.51037156]\n",
            " [-0.67722112 -0.17532072 -0.07827491 -0.067136    0.70433278]\n",
            " [-0.18109771  0.56497531 -0.23586712  0.62639701 -0.        ]\n",
            " [-0.10870109  0.71032073 -0.05598404 -0.69317698  0.        ]\n",
            " [-0.09054885  0.28248766 -0.11793356  0.31319851 -0.        ]]\n",
            "\n",
            "Sigma = \n",
            "[[12.53693231  0.          0.          0.          0.        ]\n",
            " [ 0.          9.68081588  0.          0.          0.        ]\n",
            " [ 0.          0.          2.0862302   0.          0.        ]\n",
            " [ 0.          0.          0.          1.32467943  0.        ]\n",
            " [ 0.          0.          0.          0.          0.        ]]\n",
            "\n",
            "V = \n",
            "[[-0.55398074 -0.59009358 -0.55398074 -0.1569776  -0.11557803]\n",
            " [-0.16178343 -0.01588268 -0.16178343  0.71662506  0.65867178]\n",
            " [ 0.08332921 -0.19931832  0.08332921  0.67611106 -0.69947018]\n",
            " [-0.39998463  0.78218253 -0.39998463  0.0684134  -0.25206086]\n",
            " [ 0.70710678 -0.         -0.70710678 -0.          0.        ]]\n",
            "\n",
            "-- Producing the original matrix.. --\n",
            "[[ 1.  1.  1.  3. -0.]\n",
            " [ 3.  3.  3. -0. -0.]\n",
            " [ 4.  4.  4.  0.  0.]\n",
            " [ 5.  5.  5.  0.  0.]\n",
            " [ 0.  2. -0.  4.  4.]\n",
            " [ 0. -0.  0.  5.  5.]\n",
            " [ 0.  1. -0.  2.  2.]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "e1jQjyPMWf1s",
        "colab_type": "text"
      },
      "source": [
        "For the original (given) matrix $A$, we can give a unitary matrixes $U$ and $V$: \n",
        "\n",
        "$\n",
        "\\begin{eqnarray}\n",
        "AV & = & U \\Sigma \\\\\n",
        "AVV^{-1} & = & U \\Sigma V^{-1}\\\\\n",
        "A & = & U \\Sigma V^{-1}\\\\\n",
        "  & = & U \\Sigma V^T.\\\\\n",
        "\\end{eqnarray}\n",
        "$\n",
        "\n",
        "As for $AV = U \\Sigma$, where $U$ is list of unit vector and $\\Sigma$ is diagonal vector with just values. In other words, $U$ (and $V$) dictates the direction of the vector and $\\sigma_j$ dictates its power (how much a vector should stretch). Both $U$ and $V$ are called \"unitary matrix\" where $U^TU = UU^T = E$. \n",
        "\n",
        "In order to understand how one could obtain $U$, $\\Sigma$, and $V$, we could go over the following:\n",
        "\n",
        "$\n",
        "\\begin{eqnarray}\n",
        "A^T A & = & (U\\Sigma V^T)^T(U\\Sigma V^T) \\tag{1}\\\\\n",
        "      & = & V\\Sigma^T U^T U\\Sigma V^T \\tag{2}\\\\\n",
        "      & = & V\\Sigma^2V^T \\tag{3}, \\\\\n",
        "A^T A V & = & V\\Sigma^2V^T V \\tag{4} \\\\\n",
        "        & = & V\\Sigma^2 \\tag{5}\n",
        "\\end{eqnarray}\n",
        "$\n",
        "\n",
        "If we consider $A^TA = Z$ and $\\Sigma^2=\\lambda$, and $V = X$, $(5)$ could be re-written as: \n",
        "\n",
        "$\n",
        "ZX = \\lambda X\n",
        "$\n",
        "\n",
        ", which is an eigenvalue / eigenvector problem. By solving the eigenvector problem, we should get\n",
        "\n",
        "$\n",
        "\\lambda_j = \\sigma^2_j\n",
        "$\n",
        "\n",
        "And $V$ can be computed by list of eigenvalues ($\\lambda_j$). \n",
        "\n",
        "$\n",
        "\\begin{eqnarray}\n",
        "AA^T & = & (U\\Sigma V^T)(U\\Sigma V^T)^T \\tag{6}\\\\\n",
        "     & = & U\\Sigma V^T V \\Sigma^T U^T \\tag{7}\\\\\n",
        "     & = & U \\Sigma^2 U^T, \\tag{8} \\\\\n",
        "AA^TU & = & U \\Sigma^2 U^T U \\tag{9} \\\\\n",
        "      & = & U \\Sigma^2. \\tag{10}\n",
        "\\end{eqnarray}\n",
        "$\n",
        "\n",
        "Again, this is yet another eigenvalue / eigenvector problem that we saw on $(5)$; with one difference between $A^TA$ in $(5)$ and $AA^T$ in $(10)$. \n",
        "\n",
        "So to sum up (perhaps somewhat confusing expression)..\n",
        "1. for $A^TA$, we'd need to first obtain the eigenvalues ($\\sigma_j$):\n",
        "$\n",
        "|A^TA-\\lambda E|=0\n",
        "$\n",
        "2. for each $\\sigma_j = \\sqrt{\\lambda_j}$ (singular value), sort the elements of $\\Sigma$ and create a diagonal matrix. This diagonal matrix is $\\Sigma$ in SVD formula. \n",
        "3. for each $\\lambda_j$ and (original) $A^TA$, compute eigenvectors: \n",
        "$\n",
        "(A^TA -\\lambda_j E) = 0\n",
        "$, \n",
        "and one should get a matrix $V$. \n",
        "3. do the same eigenvector-calculation over $AA^T$; one should get another matrix $U$. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OOkMtkc3kvyI",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}