03-PreceptronBinEnt.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Perceptrón con entradas y salidas binarias y pesos enteros (perceptrón unario bipolar)\n",
    "===\n",
    "\n",
    "**Juan David Velásquez Henao**  \n",
    "jdvelasq@unal.edu.co   \n",
    "Universidad Nacional de Colombia, Sede Medellín  \n",
    "Facultad de Minas  \n",
    "Medellín, Colombia\n",
    "\n",
    "---\n",
    "\n",
    "Haga click [aquí](https://github.com/jdvelasq/deep-neural-nets/tree/master/) para acceder al repositorio online.\n",
    "\n",
    "Haga click [aquí](http://nbviewer.jupyter.org/github/jdvelasq/deep-neural-nets/tree/master/) para explorar el repositorio usando `nbviewer`. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Definición del problema"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A continuación se presentan dos circuitos lógicos que implementan un codificador y un decodificador respectivamente. Se desean obtener dos compuertas lógicas que reproduzcan el comportamiento de dichos circuitos. Los valores de las conexiones de las compuertas deben ser números enteros.\n",
    "\n",
    "![alt](images/PerceptronBinEnt-01.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "**Ejercicio.--** Cuál es la salida del codificador para: \n",
    "\n",
    "* (1,0,0,0) = ( _ , _ )\n",
    "* (0,1,0,0) = ( _ , _ )\n",
    "* (0,0,1,0) = ( _ , _ )  \n",
    "* (1,0,0,0) = ( _ , _ )\n",
    "\n",
    "**Ejercicio.--** Cuál es la salida del decodificador para:  \n",
    "* (0,0) = ( _ , _ , _ , _ ) \n",
    "* (0,1) = ( _ , _ , _ , _ )\n",
    "* (1,0) = ( _ , _ , _ , _ ) \n",
    "* (1,1) = ( _ , _ , _ , _ )\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Metodología de Solución"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Este problema puede ser resuelto usando un perceptrón con entradas y salidas binarias y conexiones entre neuronas que pueden tomar valores enteros. Las conexiones son equivalentes a circuitos eléctricos con resistencias. El siguiente diagrama representa un perceptrón (izquierda) y su notación como una compuerta lógica (derecha).\n",
    "\n",
    "![alt](images/PerceptronBinEnt-02.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Matemáticamente este modelo puede representarse como:\n",
    "\n",
    "$$x_i \\in \\{0, 1\\},  \\qquad w_j \\in Z,  \\qquad v = w_0 + \\sum_{i=1}^n w_i x_i, \\qquad \n",
    "y = \\text{step}(v) = S(v) = \n",
    "\\begin{cases}      \n",
    "      1, & \\text{Si $v \\ge 0$}\\\\\n",
    "      0, & \\text{Si $v \\lt 0$}\\\\\n",
    "\\end{cases}$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Estimación usando restricciones\n",
    "\n",
    "La estimación de los parámetros puede realizarse, planteando y resolviendo las siguientes restricciones (puede existir más de una solución):\n",
    "\n",
    "\n",
    "* $a \\ge 0 \\quad \\land \\quad  b \\ge 0 \\quad \\to \\quad a + b \\ge 0$\n",
    "\n",
    "\n",
    "* $a \\le 0 \\quad \\land \\quad  b \\le 0 \\quad \\to \\quad a + b \\le 0$\n",
    "\n",
    "\n",
    "* $a \\gt 0 \\quad \\land \\quad  a + b \\le 0 \\quad \\to \\quad b \\lt 0$\n",
    "\n",
    "\n",
    "* $a \\le 0 \\quad \\land \\quad  a + b \\gt 0 \\quad \\to \\quad b \\gt 0$\n",
    "\n",
    "\n",
    "* $a+b \\gt 0 \\quad \\land \\quad  a + c \\le 0 \\quad \\to \\quad b \\gt c$\n",
    "\n",
    "\n",
    "* $\\sum a_i \\gt 0 \\quad \\land \\quad  \\lambda \\gt 0 \\quad \\to \\quad \\sum \\lambda a_i \\gt 0$\n",
    "\n",
    "\n",
    "* $\\sum a_i \\lt 0 \\quad \\land \\quad  \\lambda \\gt 0 \\quad \\to \\quad \\sum \\lambda a_i \\lt 0$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "**Ejercicio.--** Estime los parámetros para una compuerta de umbral que calcule la siguiente función:\n",
    "\n",
    "![alt](images/PerceptronBinEnt-03.png)\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Separabilidad lineal\n",
    "\n",
    "Uno de los conceptos más importantes es el de separabilidad lineal. La función conmutable $f(x_1, ..., x_n)$ es linealmente separable si existe una función de umbral tal que:\n",
    "\n",
    "$$y = f(x_1, ..., x_n) = \\text{step} \\left( w_0 + \\sum_{i=1}^n w_i x_i \\right) = \\text{step}(\\mathbf{\\text{w}}^T \\mathbf{\\text{x}})$$\n",
    "\n",
    "![alt](images/PerceptronBinEnt-04.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Red de perceptrones de dos capas\n",
    "\n",
    "Se obtiene al agrupar los perceptrones por capas, y luego conectarlas (las capas).\n",
    "\n",
    "![alt](images/PerceptronBinEnt-05.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A continuación se describe una metodología de especificación de perceptrones unarios bipolares (entradas y salidas binarias {0,1} y pesos enteros) a partir de la especificación de la función binaria que deben describir."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Definición 1.--** $\\mathbf{P}=\\{0,1\\}^n$ es el universo de cadenas binarias de longitud $n$. Un elemento de $\\mathbf{p} \\in \\mathbf{P}$ es representado como $p_1 p_2 ... p_n$.  $\\mathbf{p}, \\mathbf{q}, \\mathbf{r} \\in \\{0,1\\}^n$.\n",
    "\n",
    "Para $n=3$,  $\\mathbf{P}=\\{000,001,010,011,100,101,110,111\\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Definición 2.--** El orden de $\\mathbf{p}$, $|\\mathbf{p}|$, es la cantidad de 1s que tiene la cadena. Por ejemplo, $|000|=0$ y $|101|=2$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Definición 3.--** El substractum se define como  $S_\\mathbf{p}=\\{\\mathbf{q} \\, | \\, \\mathbf{q} \\cap  \\mathbf{p}=\\mathbf{q}\\}$. Es decir, es el conjunto de todas las cadenas posibles que se obtienen al reemplazar en la cadena $\\mathbf{p}$ los 1s por 0s. Por ejemplo:  \n",
    "\n",
    "$S_{000}=\\{000\\}$,\n",
    "\n",
    "$S_{001}=\\{000,001\\}$, \n",
    "\n",
    "$S_{010}=\\{000,010\\}$,\n",
    "\n",
    "$S_{011}=\\{000, 001, 010, 011\\}$,\n",
    "\n",
    "$S_{100}=\\{000,100\\}$,\n",
    "\n",
    "$S_{101}=\\{000,001,100,101\\}$,\n",
    "\n",
    "$S_{110}=\\{000,010,100,   110\\}$,\n",
    "\n",
    "$S_{111}=\\{000,001, 010,011,100,101,   110,111\\}$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Definición 4.--** $F(.)$ es una función lógica booleana, definida como $F:\\{0,1\\}^n \\to \\{0,1\\}$ donde la notación $F_\\mathbf{p}$ representa $F(\\mathbf{p})=F_\\mathbf{p}$. Cualquier función lógica booleana $F$ puede ser representada por un perceptrón binario de dos capas cuya función matemática es:\n",
    "\n",
    "$$F=\\text{step}\\left(\\sum_{\\mathbf{q} \\in \\mathbf{P}} w_\\mathbf{q} * M_\\mathbf{q} \\right)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Definición 5.--** Cálculo de $w_\\mathbf{q}$. Los valores de $w_\\mathbf{q}$ se pueden calcular como:\n",
    "\n",
    "$$w_\\mathbf{q} = \\sum_{\\mathbf{p} \\in S_\\mathbf{q}} (-1)^{|\\mathbf{p}|} (-1)^{|\\mathbf{q}|}F_\\mathbf{p}$$\n",
    "\n",
    "\n",
    "**Ejemplo**: Los pesos $w_\\mathbf{q}$ para la función $F$ definida como $F_{000}=F_{001}=F_{010}=0$ y $F_{011}=F_{100}=F_{101}=F_{110}=F_{111}=1$, son:\n",
    "\n",
    "$w_{000}=F_{000}=0$ \n",
    "\n",
    "$w_{001}= -F_{000}+F_{001}=0$ \n",
    "\n",
    "$w_{010}=-F_{000}+F_{010}=0$ \n",
    "\n",
    "$w_{011}=F_{000}-F_{010}-F_{001}+F_{011}=1$ \n",
    "\n",
    "$w_{100}=-F_{000}+F_{100}=1$ \n",
    "\n",
    "$w_{101}=F_{000}-F_{001}-F_{100}+F_{101}=0$ \n",
    "\n",
    "$w_{110}=F_{000}-F_{100}-F_{010}+F_{110}=0$ \n",
    "\n",
    "$w_{111}= -F_{000}+F_{001}+F_{010}-F_{011}+F_{100}-F_{101}-F_{110}+F_{111}=-1$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Definición 6.--** Cálculo de $M_\\mathbf{q}$. La función máscara se define como:\n",
    "\n",
    "$$M_\\mathbf{q}(\\mathbf{p}) = \n",
    "\\begin{cases}      \n",
    "      1, & \\mathbf{q} \\cap \\mathbf{p} = \\mathbf{q}\\\\\n",
    "      0, & \\text{otro caso}\\\\\n",
    "\\end{cases}$$\n",
    "\n",
    "$M_\\mathbf{q}$ puede ser escrita como un producto de funciones de pixel: \n",
    "\n",
    "$$M_\\mathbf{q}=\\tilde{x} _{q_1} * \\tilde{x} _{q_2} * ... * \\tilde{x}_{q_n}$$\n",
    "\n",
    "con $\\mathbf{q} = q_1 \\, q_2 \\, ... \\, q_n$, y\n",
    "\n",
    "$$\\tilde{x}_{q_i} = \n",
    "\\begin{cases}      \n",
    "      x_i, & \\text{Si $q_i = 1$}\\\\\n",
    "      1,   & \\text{Si $q_i = 0$}\\\\\n",
    "\\end{cases}$$\n",
    "\n",
    "de tal forma que: $M_{000}= 1*1*1=1$,   $M_{001}=1*1*x_3=x_3$,  $M_{011}=1*x_2*x_3$ y así sucesivamene. \n",
    "\n",
    "Nótese que $M_\\textbf{q}=x_i * x_j * ...* x_k$, es una operación lógica AND la cual puede ser representada por una función de umbral, es decir, \n",
    "$M_\\mathbf{q}=\\text{step} (x_i+x_j+...+x_k-T)$, donde $T$ es la cantidad de variables en $x_i$, $x_j$, ..., $x_k$.\n",
    "\n",
    "Para el ejemplo planteado:\n",
    "\n",
    "$M_{000}=1$,\n",
    "\n",
    "$M_{001}=\\text{step}(x_3-1) $,\n",
    "\n",
    "$M_{010}=\\text{step}(x_2-1)$,\n",
    "\n",
    "$M_{011}=\\text{step}(x_2+x_3-2)$,\n",
    "\n",
    "$M_{100}=\\text{step}(x_1-1)$,\n",
    "\n",
    "$M_{101}=\\text{step}(x_1+x_3-2)$,\n",
    "\n",
    "$M_{110}=\\text{step}(x_1+x_2-2)$,\n",
    "\n",
    "$M_{111}=\\text{step}(x_1+x_2+x_3-3)$.\n",
    "\n",
    "\n",
    "Finalmente, para el ejemplo desarrollado se obtiene:\n",
    "\n",
    "$$F(x_1,x_2,x_3)=\\text{step}( \\text{step} (x_2+x_3-1)+\\text{step} (x_1 )-\\text{step}(x_1+x_2+x_3-2))$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "**Ejercicio.--** Resuelva el caso del codificador propuesto al inicio de este tutorial.\n",
    "\n",
    "**Ejercicio.--** Resuelva el caso del decodificador propuesto al inicio de este tutorial.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Ejercicio.--** Complete el siguiente código que implementa una red de neuronas unarias bipolares usando `numpy`. \n",
    "\n",
    "*Ayuda:* Los vectores $w_\\mathbf{q}$ y $M_\\mathbf{q}$ se pueden representar como diccionarios."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[H\u001b[2J**********************************************************************\n",
      "File \"__main__\", line 25, in __main__.BipolarNeuron.predict\n",
      "Failed example:\n",
      "    m.predict(x)\n",
      "Expected:\n",
      "    [0, 0, 0, 1, 1, 1, 1, 1]\n",
      "Got nothing\n",
      "**********************************************************************\n",
      "1 items had failures:\n",
      "   1 of   5 in __main__.BipolarNeuron.predict\n",
      "***Test Failed*** 1 failures.\n"
     ]
    }
   ],
   "source": [
    "%clear\n",
    "class BipolarNeuron:\n",
    "    def __init__(self, n):\n",
    "        \"\"\"\n",
    "        n es el numero de entradas a la red \n",
    "        \"\"\"\n",
    "        pass\n",
    "    \n",
    "    def fit(self, x, y):\n",
    "        \"\"\"\n",
    "        x son las entradas, y es la salida esperada\n",
    "        \"\"\"\n",
    "        pass\n",
    "        \n",
    "    def predict(self, x):\n",
    "        \"\"\"\n",
    "        Pronostica la salida para una lista de entradas.\n",
    "        \n",
    "        >>> x = [[0, 0, 0],   [0, 0, 1],  [0, 1, 0],  [0, 1, 1],\n",
    "        ...      [1, 0, 0],   [1, 0, 1],  [1, 1, 0],  [1, 1, 1]]\n",
    "        >>> y = [0, 0, 0, 1, \n",
    "        ...      1, 1, 1, 1]\n",
    "        >>> m = BipolarNeuron(3)\n",
    "        >>> m.fit(x, y)\n",
    "        >>> m.predict(x)\n",
    "        [0, 0, 0, 1, 1, 1, 1, 1]\n",
    "       \n",
    "        \"\"\"\n",
    "        pass\n",
    "    \n",
    "if __name__ == \"__main__\":\n",
    "    import doctest\n",
    "    doctest.testmod()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Perceptrón con entradas y salidas binarias y pesos enteros (perceptrón unario bipolar)\n",
    "===\n",
    "\n",
    "**Juan David Velásquez Henao**  \n",
    "jdvelasq@unal.edu.co   \n",
    "Universidad Nacional de Colombia, Sede Medellín  \n",
    "Facultad de Minas  \n",
    "Medellín, Colombia\n",
    "\n",
    "---\n",
    "\n",
    "Haga click [aquí](https://github.com/jdvelasq/deep-neural-nets/tree/master/) para acceder al repositorio online.\n",
    "\n",
    "Haga click [aquí](http://nbviewer.jupyter.org/github/jdvelasq/deep-neural-nets/tree/master/) para explorar el repositorio usando `nbviewer`. "
   ]
  }
 ],
 "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}