06-algebra-lineal-matrices.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-0",
   "metadata": {},
   "source": [
    "# 06: Álgebra Lineal Computacional (Matrices)\n",
    "\n",
    "<table style=\"margin:0; max-width: 1000px;\">\n",
    "    <tbody>\n",
    "        <tr>\n",
    "            <td>\n",
    "                <a href=\"https://thatcsharpguy.com\">\n",
    "                    <img src=\"assets/general/Sharp@1x.png\" />\n",
    "                </a>\n",
    "            </td>\n",
    "            <td>\n",
    "                <a href=\"https://twitter.com/io_exception\">\n",
    "                    <img src=\"assets/general/Twitter@1x.png\" />\n",
    "                </a>\n",
    "            </td>\n",
    "            <td>\n",
    "                <a href=\"https://tcsg.dev/discord\">\n",
    "                    <img src=\"assets/general/Discord@1x.png\" />\n",
    "                </a>\n",
    "            </td>\n",
    "            <td>\n",
    "                <a href=\"https://github.com/thatcsharpguy/df\">\n",
    "                    <img src=\"assets/general/GitHub@1x.png\" />\n",
    "                </a>\n",
    "            </td>\n",
    "            <td>\n",
    "                <a href=\"https://youtube.com/thatcsharpguy\">\n",
    "                    <img src=\"assets/general/YouTube@1x.png\" />\n",
    "                </a>\n",
    "            </td>\n",
    "            <td>\n",
    "                <a href=\"https://youtu.be/Vdn-8j8yFSk\">\n",
    "                    <img src=\"assets/general/EnVivo@1x.png\" />\n",
    "                </a>\n",
    "            </td>\n",
    "            <td>\n",
    "                <a href=\"https://twitch.tv/thatcsharpguy\">\n",
    "                    <img src=\"assets/general/Twitch@1x.png\" />\n",
    "                </a>\n",
    "            </td>\n",
    "        </tr>\n",
    "    </tbody>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-1",
   "metadata": {},
   "source": [
    "## Paquetes  \n",
    "\n",
    " - `numpy`\n",
    " - `pandas`\n",
    " - `matplotlib`\n",
    " - `scikit-learn`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-2",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import random\n",
    "import matplotlib.pyplot as plt\n",
    "from df.display_algebra import draw_covariance_ellipse"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-3",
   "metadata": {},
   "source": [
    "## Descomposición matricial  \n",
    "\n",
    "¿Recuerdas los factores primos? recuerdas que un número puede ser obtenido a partir de sus factores primos, por ejemplo:  \n",
    "\n",
    "$$42 = 2 \\times 3 \\times 7$$  \n",
    "\n",
    "Este proceso se conoce como descomposición matemática. Como el título de esta sección lo indica, las matrices también se pueden descomponer de esta manera en objetos relativamente más simples.  \n",
    "\n",
    "Estas descomposiciones pueden ser usadas para diversos fines:  \n",
    "\n",
    " - Análisis de datos representados como matrices\n",
    " - Ejecución eficiente de operaciones matriciales\n",
    "\n",
    "En ejemplos más tangibles: podemos usar descomposiciones para [sistemas de recomendación](https://datajobs.com/data-science-repo/Recommender-Systems-[Netflix].pdf), [motores de búsqueda](https://www.maa.org/press/periodicals/loci/joma/the-linear-algebra-behind-search-engines-an-advanced-vector-space-model-lsi), [compresión de imágenes](http://timbaumann.info/svd-image-compression-demo/), [reconocimiento facial](http://openimaj.org/tutorial/eigenfaces.html), y [otras aplicaciones](https://heartbeat.fritz.ai/applications-of-matrix-decompositions-for-machine-learning-f1986d03571a)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-4",
   "metadata": {},
   "source": [
    "### Puntos fijos\n",
    "\n",
    "Supongamos que tenemos un punto $x$, tal que si le aplicamos una función $f$, el resultado es $x$. Es decir si:  \n",
    "\n",
    "$$f(x) = x$$   \n",
    "\n",
    "Podemos decir que $x$ es un punto fijo de $f$. Por ejemplo, supongamos que $f(x) = x^2$: \n",
    " - Cuando $x = 0$, $f(x) = 0$\n",
    " - Cuando $x = 1$, $f(1) = 1$\n",
    " \n",
    "Tanto $x = 0$ como $x = 1$ son considerados puntos fijos de $x^2$.\n",
    "\n",
    " > 🤔 existen dos tipos de puntos fijos: estables y no estables. Se dice que un punto fijo es estable si cualquier valor en su vecindad hace que la función se acerque al punto fijo, mientras que se dice que uno no es estable si cualquier valor en su vecindad hace que la función se aleje de este.  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-5",
   "metadata": {},
   "source": [
    "Podemos obtener los puntos fijos de una función de manera *ingenua* eligiendo un valor aleatorio $x$ y aplicando sucesivamente la regla $x_t=f(x_{t-1})$ hasta llegar a un punto estable, ese es tu punto fijo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_fixed_point(f, r, eps=1e-5):\n",
    "\n",
    "    fr = f(r)\n",
    "    history = [(r, fr)]\n",
    "    # ¿Ya dejamos de movernos?\n",
    "    while np.abs(fr - r) > eps and np.abs(fr) < np.inf:\n",
    "        r = fr\n",
    "        fr = f(r)\n",
    "        history.append((r, fr))\n",
    "\n",
    "    return fr, np.array(history)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def function(x):\n",
    "    return np.cos(x)\n",
    "\n",
    "\n",
    "r = np.random.uniform(-5, 5)  # random starting point\n",
    "fixed, history = find_fixed_point(function, r)\n",
    "\n",
    "print(f\"Punto fijo {fixed:0.5}\")\n",
    "print(f\"f({fixed:0.5}) = {function(fixed):0.5}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-8",
   "metadata": {},
   "source": [
    "## Eigen.. ¿qué?\n",
    "\n",
    "De cierto modo, cada matriz representan una función conocida como [aplicación lineal](https://es.wikipedia.org/wiki/Aplicaci%C3%B3n_lineal), dentro de las aplicaciones lineales existen las [transformaciones lineales] que transforman elementos entre espacios vectoriales.\n",
    "\n",
    "### Eigenvalores y eigenvectores  \n",
    "\n",
    "Si bien las transformaciones lineales tienen puntos fijos, existen valores análogos, y aún más interesantes para analizar de una matriz:  \n",
    "\n",
    " - **Eigenvectores**  \n",
    " - **Eigenvalores** \n",
    "\n",
    " > **eigen** = propio (o característico).\n",
    "\n",
    "#### Método de las potencias    \n",
    "\n",
    "Vamos a tomar una matriz cuadrada $A$ y aplicarla a un vector aleatorio $\\vec{x}$, al resultado volverle a aplicar $A$ y luego volverle a aplicar $A$... es decir, calculamos:\n",
    "\n",
    "$$AAA \\dots AA\\vec{x}$$\n",
    "$$A^n\\vec{x}$$\n",
    "\n",
    "En la práctica esto causaría que el resultado crezca hasta infinito o colapse a cero. Podemos normalizar el resultado hacer algo para contrarrestar este efecto:\n",
    "\n",
    "\n",
    "$$\\begin{equation}x_n = \\frac{Ax_{n-1}}{\\|Ax_{n-1}\\|_\\infty}\\end{equation}$$\n",
    "\n",
    "El resultado a cada paso será forzado a ser un vector unitario usando al norma mínima $L_\\infty$. Finalmente, a este método lo vamos a conocer como el **método de las potencias** o *power iteration method*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def power_iterate(A, x, n):\n",
    "    for i in range(n):\n",
    "        x = A @ x  # multiply\n",
    "        x = x / np.linalg.norm(x, np.inf)  # normalize\n",
    "\n",
    "    return x / np.linalg.norm(x, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-10",
   "metadata": {},
   "source": [
    "Comencemos con nuestra matriz $A$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-11",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = np.random.normal(0, 1, (2, 2))\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-12",
   "metadata": {},
   "source": [
    "Seguimos con un vector cualquiera:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-13",
   "metadata": {},
   "outputs": [],
   "source": [
    "cualquiera = np.random.normal(0, 3, (2,))\n",
    "print(cualquiera)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-14",
   "metadata": {},
   "outputs": [],
   "source": [
    "# El vector resultante -casi siempre- es el mismo\n",
    "eigenvector = power_iterate(A, cualquiera, n=500)\n",
    "print(eigenvector)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-15",
   "metadata": {},
   "source": [
    "Este vector es conocido como el **eigenvector principal**, y es una característica de la matriz.  \n",
    "\n",
    "La matriz $A$ toma nuestro vector y la única transformación que le hace es escalarlo (hacerlo más grande) sin rotaciones ni sesgos.\n",
    "\n",
    "Para calcular el factor de escalamiento podemos..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-16",
   "metadata": {},
   "outputs": [],
   "source": [
    "ratio = (A @ eigenvector) / eigenvector\n",
    "eigenvalue = ratio[0]  # Todos los elementos tienen el mismo valor.\n",
    "print(eigenvalue)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-17",
   "metadata": {},
   "source": [
    "El escalar que ves más arriba es conocido como el **eigenvalor principal**, llamémoslo $\\lambda$ por el momento, y satisface esta ecuación:\n",
    "\n",
    "$$A\\vec{x}_i = \\lambda_i\\vec{x}_i$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-18",
   "metadata": {},
   "outputs": [],
   "source": [
    "uno = A @ eigenvector\n",
    "dos = eigenvector * eigenvalue\n",
    "\n",
    "np.allclose(uno, dos)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-19",
   "metadata": {},
   "source": [
    "Cada vector $\\vec{x}_i$ que satisfaga la ecuación es un **eigenvector** y cada $\\lambda_i$ que cumpla esta ecuación es un **eigenvalue**. Estos elementos vienen en pares."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-20",
   "metadata": {},
   "source": [
    "### Otros eigenvalores  \n",
    "\n",
    "El método de las potencias nos ayuda a encontrar **un solo** vector, sin embargo pueden existir múltiples pares de **eigen cosas**, para encontrar los otros, podemos seguir este algoritmo:  \n",
    "\n",
    "#### Encontrar más valores..."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-21",
   "metadata": {},
   "source": [
    "Mientras tanto en NumPy..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-22",
   "metadata": {},
   "outputs": [],
   "source": [
    "evals, evecs = np.linalg.eig(A)\n",
    "print(evals[0])\n",
    "print(evecs[:, 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-23",
   "metadata": {},
   "source": [
    "## El espectro... *eigenspectro*. \n",
    "\n",
    "A la secuencia eigenvalores ordenados por su valor absoluto se le conoce como el eigenespectro de una matriz; esto nos puede ayudar a encontrar versiones simplificadas de nuestras matrices.\n",
    "\n",
    "Supongamos que tenemos un dataset de 18K jugadores de fútbol:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-24",
   "metadata": {},
   "outputs": [],
   "source": [
    "fifa19 = pd.read_csv(\"assets/06/fifa19.csv\")\n",
    "# https://fifauteam.com/fifa-19-attributes-guide/\n",
    "\n",
    "attributes = [\n",
    "    \"Acceleration\",\n",
    "    \"SprintSpeed\",  # Pace\n",
    "    \"Finishing\",\n",
    "    \"LongShots\",\n",
    "    \"Penalties\",\n",
    "    \"Positioning\",\n",
    "    \"ShotPower\",\n",
    "    \"Volleys\",  # Shooting\n",
    "    \"Crossing\",\n",
    "    \"Curve\",\n",
    "    \"FKAccuracy\",\n",
    "    \"LongPassing\",\n",
    "    \"ShortPassing\",\n",
    "    \"Vision\",  # Passing\n",
    "    \"Agility\",\n",
    "    \"Balance\",\n",
    "    \"BallControl\",\n",
    "    \"Composure\",\n",
    "    \"Dribbling\",\n",
    "    \"Reactions\",  # Dribbling\n",
    "    \"HeadingAccuracy\",\n",
    "    \"Interceptions\",\n",
    "    \"Marking\",\n",
    "    \"SlidingTackle\",\n",
    "    \"StandingTackle\",  # Defending\n",
    "    \"Aggression\",\n",
    "    \"Jumping\",\n",
    "    \"Stamina\",\n",
    "    \"Strength\",  # Physical\n",
    "    # 'GKDiving', 'GKHandling', 'GKKicking', 'GKPositioning', 'GKReflexes', # Goalkeeping\n",
    "]\n",
    "\n",
    "player_stats = fifa19[attributes].copy().fillna(axis=\"index\", method=\"backfill\")\n",
    "player_stats.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-25",
   "metadata": {},
   "source": [
    "Calculando la matriz de covarianza y vemos los eigenvectores y los valores correspondientes a cada uno de ellos:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-26",
   "metadata": {},
   "outputs": [],
   "source": [
    "players_cov = np.cov(player_stats.values, rowvar=False)\n",
    "eigs, eigv = np.linalg.eig(players_cov)\n",
    "\n",
    "order = np.argsort(eigs)\n",
    "eigs, eigv = eigs[order], eigv[order]\n",
    "\n",
    "fig = plt.figure()\n",
    "ax = fig.gca()\n",
    "ax.bar(np.arange(len(eigs)), list(reversed(eigs)))\n",
    "ax.set_xlabel(\"Eigenvalor\")\n",
    "ax.set_ylabel(\"Amplitud\")\n",
    "ax.set_title(\"Eigenspectrum of the FIFA 19 dataset\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-27",
   "metadata": {},
   "source": [
    "Los eigenvectores nos ayudan a identificar los ejes a lo largo de los que nuestro dataset varía:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-28",
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_vector(vector):\n",
    "    properties = []\n",
    "    for attribute, value in zip(attributes, vector):\n",
    "        properties.append(f\"{attribute:<20s} {value:+.03}\")\n",
    "    results = \"\\n\".join(properties)\n",
    "    print(results)\n",
    "\n",
    "\n",
    "print(\"Eigenvector 1\")\n",
    "print_vector(eigv[0])\n",
    "print()\n",
    "print(\"Eigenvector 2\")\n",
    "print_vector(eigv[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-29",
   "metadata": {},
   "source": [
    "Estos dos vectores son las direcciones con mayor varianza en nuestro dataset... difícil de ver e imaginar porque estamos hablando de un espacio de 29 dimensiones."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-30",
   "metadata": {},
   "source": [
    "## PCA   \n",
    "\n",
    "Lo que acabamos de hacer acá arriba se conoce como **análisis de componentes principales** o *principal component análisis* (*PCA*). \n",
    "\n",
    "Los componentes principales de un dataset son los eigenvectores de su matriz de covarianza. Usando este análisis de componentes principales podemos encontrar una proyección de bajas dimensiones para nuestros datos si proyectamos nuestro dataset en los vectores principales:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-31",
   "metadata": {},
   "outputs": [],
   "source": [
    "def pca(data, n_components):\n",
    "    cov = np.cov(data, rowvar=False)\n",
    "    eigs, eigv = np.linalg.eig(cov)\n",
    "\n",
    "    order = np.argsort(eigs)\n",
    "    eigs, eigv = eigs[order], eigv[order]\n",
    "    eig_order = np.argsort(np.abs(eigs))\n",
    "    components = []\n",
    "    for i in range(n_components):\n",
    "        components.append(data @ eigv[eig_order[-i - 1]])\n",
    "    return np.stack(components).T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-32",
   "metadata": {},
   "outputs": [],
   "source": [
    "components = pca(player_stats.values, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-33",
   "metadata": {},
   "outputs": [],
   "source": [
    "player_ids = [158023, 20801, 190871, 238789, 231747, 194765, 208722, 209331] + [\n",
    "    156519,\n",
    "    186302,\n",
    "    192041,\n",
    "    187478,\n",
    "    167524,\n",
    "    213445,\n",
    "    217167,\n",
    "    224103,\n",
    "    173434,\n",
    "    186551,\n",
    "    187208,\n",
    "    199569,\n",
    "    190485,\n",
    "    233260,\n",
    "    187705,\n",
    "    186979,\n",
    "    167532,\n",
    "    212377,\n",
    "    183743,\n",
    "    139229,\n",
    "    203283,\n",
    "    171377,\n",
    "    222645,\n",
    "    192015,\n",
    "    #    186513, 232316, 239545, 187722, 237498, 169415, 202786, 192046,\n",
    "    #    235368, 235123, 236434, 237978, 246188, 243157, 236842, 240177,\n",
    "    #    237657, 244349, 244611, 193164, 242823, 210426, 244743, 233535,\n",
    "    244615,\n",
    "    212475,\n",
    "    246294,\n",
    "    244831,\n",
    "    240107,\n",
    "    239548,\n",
    "    244637,\n",
    "]\n",
    "\n",
    "\n",
    "index = fifa19[fifa19[\"ID\"].isin(set(player_ids))].index\n",
    "comp = components[index]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-34",
   "metadata": {},
   "outputs": [],
   "source": [
    "len(comp), len(index), len(set(player_ids)), len(player_ids)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-35",
   "metadata": {},
   "outputs": [],
   "source": [
    "fifa19[fifa19[\"Name\"].str.contains(\"Mané\")]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-36",
   "metadata": {},
   "outputs": [],
   "source": [
    "fig = plt.figure(figsize=(10, 5), dpi=100)\n",
    "ax = fig.gca()\n",
    "\n",
    "ax.scatter(comp[:, 0], comp[:, 1])\n",
    "for i, player_id in enumerate(player_ids):\n",
    "    ax.text(\n",
    "        comp[i, 0],\n",
    "        comp[i, 1],\n",
    "        fifa19[fifa19[\"ID\"] == player_id][\"Name\"].values[0],\n",
    "        fontsize=6,\n",
    "    )\n",
    "\n",
    "ax.set_xlabel(\"Componente 1\")\n",
    "ax.set_ylabel(\"Componente 2\")\n",
    "ax.set_title(\"Componentes principales FIFA19\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-37",
   "metadata": {},
   "source": [
    "### Proyecciones de pocas dimensiones  \n",
    "\n",
    "Las proyecciones de pocas dimensiones son herramientas de vital importancia en la ciencia de datos exploratoria. PCA es una forma de lograr esta tarea, sin embargo, no es la única. Existe otro algoritmo llamado *t-SNE* que, al igual que PCA nos permite descomponer nuestra información para proyectar nuestro dataset:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-38",
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.manifold import TSNE\n",
    "\n",
    "t_reduce = TSNE()\n",
    "xy_2d = t_reduce.fit_transform(player_stats.values)[index]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-39",
   "metadata": {},
   "outputs": [],
   "source": [
    "fig = plt.figure(figsize=(10, 5), dpi=100)\n",
    "ax = fig.add_subplot(1, 1, 1)\n",
    "\n",
    "ax.scatter(xy_2d[:, 0], xy_2d[:, 1])\n",
    "for i, player_id in enumerate(player_ids):\n",
    "    ax.text(\n",
    "        xy_2d[i, 0],\n",
    "        xy_2d[i, 1],\n",
    "        fifa19[fifa19[\"ID\"] == player_id][\"Name\"].values[0],\n",
    "        fontsize=6,\n",
    "    )\n",
    "\n",
    "\n",
    "ax.set_xlabel(\"t-SNE componente 1\")\n",
    "ax.set_ylabel(\"t-SNE componente 2\")\n",
    "ax.set_title(\"t-SNE transformation of the whisky dataset\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-40",
   "metadata": {},
   "source": [
    "## Otras propiedades de las matrices  \n",
    "\n",
    "### Traza  \n",
    "\n",
    "La traza $\\text{tr}$ de una matriz cuadrada es la suma de los elementos en la diagonal:\n",
    "\n",
    "$$\\text{tr}(A) = a_{1,1} + a_{2,2} + \\dots + a_{n,n}$$  \n",
    "\n",
    "Esto es igual que la suma de los eigenvalores:  \n",
    "\n",
    "$$\\text{tr}(A) = \\sum_{i=1}^n \\lambda_i$$\n",
    "\n",
    "### Determinante  \n",
    "\n",
    "El determinante $\\text{det}$ de una matriz es igual a la multiplicación de los eigenvalores:  \n",
    "\n",
    "$$\\text{det}(A) = \\prod_{i=1}^n \\lambda_i$$  \n",
    "\n",
    "Cuando alguno de los eigenvalores de la matriz es $0$ el determinante es $0$, lo cual tiene implicaciones para la matriz.\n",
    "\n",
    " > ⚠️ Hay matrices con eigenvalores complejos, sin embargo... no las veremos aquí.\n",
    "\n",
    "\n",
    "## Inversion de matrices    \n",
    "\n",
    "Recordarás las operaciones básicas sobre las matrices:  \n",
    " \n",
    " - Multiplicación por un escalar: $cA$\n",
    " - Suma matricial: $A + B$\n",
    " - Multiplicación matricial: $AB$\n",
    " - Transposición: $A^T$  \n",
    " \n",
    "Ves la suma y la multiplicación y tal vez te preguntes... ¿hay división? \n",
    "\n",
    "La operación más parecida es la inversa de una matriz, que nos permite:  \n",
    "\n",
    " - $A^{-1}(A\\vec{x}) = \\vec{x}$ \n",
    " - $A^{-1}A = I$ \n",
    " - $(A^{-1})^{-1} = A$  \n",
    " \n",
    "Sin embargo esta operación, (la inversa) no está siempre definida para todas las matrices. En particular, la inversa no está definida para matrices **no cuadradas** y con **determinante = $0$**.  \n",
    "\n",
    "Una matriz es llamada **singular** si su determinante es 0 (y por tanto no invertible) y es llamada **no singular** si es posible invertirla.\n",
    "\n",
    "#### Algoritmo  \n",
    "\n",
    "Hay diversas maneras de calcular la inversa de una matriz, incluyendo un algoritmo recursivo; este algoritmo recursivo funciona, pero solo para matrices pequeñas. Más adelante hablaremos de una forma efectiva para invertir matrices.\n",
    " \n",
    "### ¿Qué problemas resuelve la inversión de matrices? \n",
    "\n",
    "#### Sistemas lineales  \n",
    "\n",
    "Imagina que tenemos la siguiente matriz:  \n",
    "\n",
    "$$A = \\begin{bmatrix}\n",
    "0.5 & 1.0 & 2.0\\\\\n",
    "1.0 & 0.5 & 0.0\\\\\n",
    "0.6 & 1.1 & -0.3\\\\\n",
    "\\end{bmatrix}$$   \n",
    "\n",
    "Esta matriz representa una aplicación lineal que opera sobre vectores tridimensionales $\\vec{x}$, y que produce vectores 3D $\\vec{y}$. Cada uno de las entradas de este vector es una suma ponderada de las entradas del vector $\\vec{x}$:\n",
    "\n",
    "$$y_1 = 0.5x_1 + 1.0x_2 +2.0x_3\\\\\n",
    "y_2 = 1.0x_1 +0.5x_2 +0.0x_3\\\\\n",
    "y_3 = 0.6x_1 + 1.1x_2 - 0.3x_3$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-41",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = np.array([[0.5, 1.0, 2.0], [1.0, 0.5, 0.0], [0.6, 1.1, -0.3]])\n",
    "x = np.array([1, -1, 1])\n",
    "\n",
    "print(A @ x)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-42",
   "metadata": {},
   "source": [
    "Viéndolo desde otra perspectiva, esta es la forma en la que sistemas de ecuaciones simultaneas pueden ser representadas de la siguiente forma:\n",
    "\n",
    "$$A\\vec{x} = \\vec{y}$$\n",
    "\n",
    "Esto es conocido como un sistema de ecuaciones lineares.  \n",
    "\n",
    "Partiendo de esto, y de que ahora sabemos que la inversa de una matriz existe, podríamos pensar que la solución es bastante trivial:\n",
    "\n",
    "$$\n",
    "A^{-1}A\\vec{x}=A^{-1}\\vec{y} \\\\\n",
    "I \\vec{x} = A^{-1} \\vec{y} \\\\\n",
    "\\vec{x} = A^{-1}\\vec{y}\n",
    "$$\n",
    "\n",
    " > Recuerda que la inversa de una matriz solamente está definida si la matriz es cuadrada  \n",
    " \n",
    "En la práctica, los sistemas lineales casi nunca son resueltos invirtiendo directamente la matriz; hay problemas de estabilidad numérica así como de complejidad algorítmica que lo hacen un procedimiento inviable.\n",
    "\n",
    "### Soluciones aproximadas  \n",
    "\n",
    "En lugar de tratar de invertir de una vez la matriz, resuelven el problema de forma iterativa, una de las formas es utilizando optimización, algo que veremos en el futuro.  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-43",
   "metadata": {},
   "source": [
    "## Descomposición en valores singulares   \n",
    "\n",
    "La eigendescomposición que vimos hace poco solamente funciona para matrices cuadradas, sin embargo no siempre nuestros problemas van a venir en esta forma; es aquí en donde entra otra forma de descomponer matrices:\n",
    "\n",
    "La *singular value decomposition* (SVD) es una forma general de descomponer cualquier matriz $A$. Es una de las grandes herramientas del álgebra lineal.  \n",
    "\n",
    "*SVD* descompone una matriz en tres partes:  \n",
    "\n",
    "$$A = U \\Sigma V$$  \n",
    "\n",
    "En donde:  \n",
    "\n",
    " - $A$ es la matriz inicial de  $m \\times n$, \n",
    " - $U$ es una matriz **ortonormal** de $m \\times m$, conocida como **vectores singulares izquierdos**,\n",
    " - $V$ es una matriz **ortonormal** de $n \\times n$, conocida como **vectores singulares derechos**,\n",
    " - $\\Sigma$ es una matriz diagonal de $m \\times n$, la diagonal son los **valores singulares**\n",
    " \n",
    " > Una matriz ortonormal $U$ es una matriz que cumple que $U^{-1} =U^T$ y que las columnas y filas tienen norma unitaria. \n",
    " \n",
    "La diagonal de $\\Sigma$ son los **valores singulares** que son parecidos a los *eigenvectores* sin embargo no son lo mismo. Por ejemplo, los valores singulares siempre son números positivos.  \n",
    "\n",
    "En *NumPy*..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-44",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = np.array([[3, 2, 3, 2], [2, 9, 4, 2], [4, 1, 9, 8]])\n",
    "\n",
    "\n",
    "u, sigma, v = np.linalg.svd(A)\n",
    "true_sigma = np.zeros_like(A, dtype=np.float64)\n",
    "np.fill_diagonal(true_sigma, sigma)\n",
    "A_reconstructed = u @ true_sigma @ v\n",
    "\n",
    "\n",
    "print(u)\n",
    "print()\n",
    "# print(sigma)\n",
    "print(true_sigma)\n",
    "print()\n",
    "print(v)\n",
    "\n",
    "print()\n",
    "print(A_reconstructed)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-45",
   "metadata": {},
   "source": [
    "### SVD 🤝 eigendescomposición  \n",
    "\n",
    "La *SVD* es:  \n",
    "\n",
    " - Obtener los eigenvectores de $A^T A$ para obtener $U$\n",
    " - Obtener los eigenvectores de $A A^T$ para obtener $V$  \n",
    " - Calcular la raíz cuadrada de los eigenvalores de $A^T A$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-46",
   "metadata": {},
   "source": [
    "### Aplicaciones de las descomposiciones  \n",
    "\n",
    "Una vez que tenemos la descomposición hay operaciones que se vuelven triviales:  \n",
    "\n",
    "$$A = U\\Sigma V$$\n",
    "$$A^{-1} = V^T \\Sigma^\\dagger U^T$$   \n",
    "\n",
    " - $\\Sigma^\\dagger$ es $\\text{diag}(1.0/\\Sigma_{ii})^T$  \n",
    " \n",
    "### Pseudo-inversa...\n",
    "\n",
    "$\\dots$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-47",
   "metadata": {},
   "source": [
    "## Los valores singulares \n",
    "\n",
    "Como te imaginarás, los valores singulares capturan algunos aspectos esenciales de una matriz. \n",
    "\n",
    " - Se dice que una matriz es de **rango completo** si su número de valores singulares distintos de cero es igual al número de elementos en la diagonal de la matriz; de otro modo se trata de una matriz de **rango deficiente**.    \n",
    " \n",
    " - El **número condicional** de una matriz es la relación entre su valor singular más grande y el más pequeño; este número nos dice qué tan sensible es la aplicación lineal a cambios, es decir en la operación $A\\vec{x} = \\vec{y}$ nos dice si $\\vec{y}$ cambia mucho o poco cuando realizamos pequeños cambios a $\\vec{x}$. Se relaciona con los conceptos de matrices **bien condicionadas** y **mal condicionadas**.  \n",
    " \n",
    "### Los valores singulares y la singularidad  \n",
    "\n",
    "Habíamos dicho que una matriz es singular si es *no invertible* y tiene $\\text{det}(A) = 0$, esta definición es binaria, los conceptos de rango y número condicional nos ayudan a convertir esta distinción en un gradiente, usando estos dos números podemos responder la pregunta \"¿Qué tan singular es la matriz?\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-48",
   "metadata": {},
   "source": [
    "## Aplicaciones de las descomposiciones  \n",
    "\n",
    "### Operaciones *avanzadas*. \n",
    "\n",
    "Ahora que podemos descomponer una matriz, podemos plantearnos el realizar operaciones como:   \n",
    "\n",
    " - Elevar una matriz a una potencia fraccionaria $A^{\\frac{1}{3}}$  \n",
    " - Invertir una matriz ${A^{-1}}$\n",
    " - Calcular el logaritmo de una matriz $\\ln{A}$  \n",
    " \n",
    "La forma de hacerlo es \"sencilla\": ignoramos $U$ y $V$ y se le aplica la operación en cuestión a todos los elementos de $\\Sigma$.\n",
    "\n",
    "### Esferización  (*sphering*)\n",
    "\n",
    "El **esferización** (mas comúnmente conocido como blanqueamiento) consiste en remover todas las correlaciones lineales dentro de un dataset, es una forma de normalizar un conjunto de datos que se realiza antes de realizar un análisis.  \n",
    "\n",
    "Dado una matriz $X$:  \n",
    "\n",
    "$$X^* =(X-\\mu)\\Sigma^{-\\frac{1}{2}}$$\n",
    "\n",
    "en donde $\\vec{\\mu}$ es el **vector promedio** y $\\Sigma$ es la  **matriz de covarianza**.  \n",
    "\n",
    "El resultado de aplicar esta operación **centra el dataset** y modifica el dataset para que la matriz de covarianza sea **unitaria**.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-49",
   "metadata": {},
   "outputs": [],
   "source": [
    "def apply_sphering(x):\n",
    "    center_x = x - np.mean(x, axis=0)\n",
    "    u, sigma, v = np.linalg.svd(np.cov(center_x, rowvar=False))\n",
    "\n",
    "    # La magia\n",
    "    sigma_inv_sqr = v.T @ np.diag(1.0 / np.sqrt(sigma)) @ u.T\n",
    "    shphere_x = center_x @ sigma_inv_sqr\n",
    "\n",
    "    return shphere_x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06-algebra-lineal-matrices-50",
   "metadata": {},
   "outputs": [],
   "source": [
    "X = np.random.normal(0, 1, (200, 2)) @ np.array([[0.1, 0.5], [-0.9, 1.0]]) + np.array(\n",
    "    [2, 3]\n",
    ")\n",
    "X_sphered = apply_sphering(X)\n",
    "\n",
    "fig = plt.figure(figsize=(10, 10))\n",
    "ax = fig.gca()\n",
    "\n",
    "ax.scatter(X[:, 0], X[:, 1], c=\"#99d8c9\", label=\"Original\")\n",
    "ax.scatter(X_sphered[:, 0], X_sphered[:, 1], c=\"#feb24c\", label=\"Esferada\")\n",
    "\n",
    "for dataset in [X, X_sphered]:\n",
    "    for std in [0.5, 1, 2]:\n",
    "        draw_covariance_ellipse(ax, dataset, std)\n",
    "\n",
    "for one, two in zip(X, X_sphered):\n",
    "    ax.plot([one[0], two[0]], [one[1], two[1]], alpha=0.2)\n",
    "\n",
    "# ax.set_xlim(-6, 6)\n",
    "# ax.set_ylim(-6, 6)\n",
    "\n",
    "ax.axhline(0)\n",
    "ax.axvline(0)\n",
    "ax.set_aspect(1.0)\n",
    "ax.legend()\n",
    "ax.set_title(\"Esferización de un dataset\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-51",
   "metadata": {},
   "source": [
    "### Aproximaciones de bajo rango\n",
    "\n",
    "¿Recuerdan las matrices dispersas de la sesión pasada?\n",
    "\n",
    "|                    | Feregrino | Alma      | Benito    | ... | Terry     | Destiny   |\n",
    "|--------------------|-----------|-----------|-----------|-----|-----------|-----------|\n",
    "| La Puerta Negra    | ${\\bf 1}$ | $0$       | $0$       |     | $0$       | $0$       |\n",
    "| Flux               | $0$       | ${\\bf 1}$ | $0$       |     | ${\\bf 1}$ | $0$       |\n",
    "| La mesa del rincón | ${\\bf 1}$ | $0$       | $0$       |     | $0$       | $0$       |\n",
    "| Andar conmigo      | ${\\bf 1}$ | ${\\bf 1}$ | $0$       |     | ${\\bf 1}$ | $0$       |\n",
    "| ...                |           |           |           | ... |           |           |\n",
    "| Dark Horse         | $0$       | ${\\bf 1}$ | ${\\bf 1}$ |     | $0$       | ${\\bf 1}$ |\n",
    "\n",
    "Datasets como este tipo son el pan de cada día de compañías como Spotify, Netflix y Amazon. Lo que siempre están tratando de hacer es encontrar nuevos objetos para recomendarles a sus usuarios.   \n",
    "\n",
    "Como vimos anteriormente, la gran mayoría de los usuarios han escuchado/visto/comprado una cantidad mínima de canciones/películas/productos.  \n",
    "\n",
    "Centrándonos en el ejemplo de las canciones, una forma simplista de verlos podríamos encapsular a los usuarios dentro de grupos como \"el fan de los tigres del norte\", \"el que solo escucha canciones de my chemical romance\", \"el fan de música de tienda de ropa\"... sin embargo la realidad no funciona así, un modelo más realista es uno que representa a los usuarios como una suma ponderada:  \n",
    "\n",
    "$$\\text{usuario} = 0.2 \\times \\text{tigres del norte} + 0.7 \\times \\text{mcr} + 0.1 \\times \\text{música de zara}$$  \n",
    "\n",
    "Esto nos permite usar solamente una parcialidad de la información de los usuarios para realizar recomendaciones; usamos la *SVD* para realizar esto. \n",
    "\n",
    "Podemos encontrar una aproximación de bajo rango truncando la *SVD* y manteniendo solamente una fracción, digamos $K$, de los valores singulares, y las primeras $K$ columnas y filas de $U$ y $V$ respectivamente.\n",
    "\n",
    "Esta es una forma de reducción dimensional."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-52",
   "metadata": {},
   "source": [
    "[Ver recursos al final]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06-algebra-lineal-matrices-53",
   "metadata": {},
   "source": [
    "---------\n",
    "## Recursos\n",
    "\n",
    "<table style=\"margin:0; max-width: 1000px;\">\n",
    "    <tbody>\n",
    "        <tr>\n",
    "            <td>\n",
    "                <a href=\"https://thatcsharpguy.com\">\n",
    "                    <img src=\"assets/general/Sharp@1x.png\" />\n",
    "                </a>\n",
    "            </td>\n",
    "            <td>\n",
    "                <a href=\"https://twitter.com/io_exception\">\n",
    "                    <img src=\"assets/general/Twitter@1x.png\" />\n",
    "                </a>\n",
    "            </td>\n",
    "            <td>\n",
    "                <a href=\"https://tcsg.dev/discord\">\n",
    "                    <img src=\"assets/general/Discord@1x.png\" />\n",
    "                </a>\n",
    "            </td>\n",
    "            <td>\n",
    "                <a href=\"https://github.com/thatcsharpguy/df\">\n",
    "                    <img src=\"assets/general/GitHub@1x.png\" />\n",
    "                </a>\n",
    "            </td>\n",
    "            <td>\n",
    "                <a href=\"https://youtube.com/thatcsharpguy\">\n",
    "                    <img src=\"assets/general/YouTube@1x.png\" />\n",
    "                </a>\n",
    "            </td>\n",
    "            <td>\n",
    "                <a href=\"https://youtu.be/Vdn-8j8yFSk\">\n",
    "                    <img src=\"assets/general/EnVivo@1x.png\" />\n",
    "                </a>\n",
    "            </td>\n",
    "            <td>\n",
    "                <a href=\"https://twitch.tv/thatcsharpguy\">\n",
    "                    <img src=\"assets/general/Twitch@1x.png\" />\n",
    "                </a>\n",
    "            </td>\n",
    "        </tr>\n",
    "    </tbody>\n",
    "</table>\n",
    "\n",
    "### Sitios web\n",
    "\n",
    " - **The Linear Algebra Behind Search Engines** - [https://www.maa.org/press/periodicals/loci/joma/the-linear-algebra-behind-search-engines-introduction](https://www.maa.org/press/periodicals/loci/joma/the-linear-algebra-behind-search-engines-introduction)\n",
    " \n",
    " - **Eigenfaces: Recovering Humans from Ghosts** - [https://towardsdatascience.com/eigenfaces-recovering-humans-from-ghosts-17606c328184](https://towardsdatascience.com/eigenfaces-recovering-humans-from-ghosts-17606c328184)  \n",
    " \n",
    " - **Eigenfaces for recognition** - [https://www.face-rec.org/algorithms/pca/jcn.pdf](https://www.face-rec.org/algorithms/pca/jcn.pdf)  \n",
    " \n",
    " - **Image Compression with Singular Value Decomposition** - [http://timbaumann.info/svd-image-compression-demo/](http://timbaumann.info/svd-image-compression-demo/)\n",
    " \n",
    " - **Eigenvectors and eigenvalues** - [http://setosa.io/ev/eigenvectors-and-eigenvalues/](http://setosa.io/ev/eigenvectors-and-eigenvalues/)\n",
    " \n",
    " -  **Power Iteration | ML Wiki** - [http://mlwiki.org/index.php/Power_Iteration](http://mlwiki.org/index.php/Power_Iteration)\n",
    " \n",
    " - **PCA Whitening** - [http://ufldl.stanford.edu/tutorial/unsupervised/PCAWhitening](http://ufldl.stanford.edu/tutorial/unsupervised/PCAWhitening)\n",
    " \n",
    " - **Matrix Factorization for Movie Recommendations in Python** - [https://beckernick.github.io/_posts/2016-11-10-matrix-factorization-recommender/](https://beckernick.github.io/_posts/2016-11-10-matrix-factorization-recommender/)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}