notebooks/4-linear-separability.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linear Separability"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " To check for linear separability of a Boolean function, write your own computer program to train a simple perceptron with four input terminals, and one output $O^{(\\mu)}={\\text{tanh}}[\\frac{1}{2}(-\\theta+\\sum_{i=1}^4 w_i x_i^{(\\mu)})] \\quad$ where $w_i$ are the weights, $\\theta$ is the threshold, and $x_i^{(\\mu)}$ is the i-th component of the $\\mu$-th input pattern. Train the perceptron by implementing stochastic gradient descent (sequential training) on the energy function $H = \\frac{1}{2}\\sum_\\mu \\left (t^{(\\mu)} - O^{(\\mu)} \\right )^2$. Set the learning rate $\\eta$ to 0.02. Initialise the weights to random numbers uniformly distributed in the range [-0.2,0.2]. Initialise the threshold to a random number uniformly distributed in the range [−1,1].\n",
    "\n",
    "For each function perform a maximum of $10^5$ updates. If you find that the network classifies all inputs of a function correctly, i.e. if $\\text{sgn}(O^{(\\mu)})=t^{(\\mu)}$ for $\\mu=1,2,\\ldots,16$, the function is linearly separable and the learning should be stopped. If correct classification is not achieved within the learning time, this may mean that the function is either not linearly separable, or that your algorithm is stuck in a local mimimum. In such cases, you need to repeat the learning at least 10 times using the same procedure. Conclude that the function is not linearly separable if you do not achieve correct classification for any of the repetitions.\n",
    "\n",
    "Based on the results from your stochastic gradient-descent algorithm, answer which of the functions given below are linearly separable by ticking the corresponding box(es). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import numpy.random as rnd\n",
    "import csv\n",
    "\n",
    "def calculate_output(threshold, weight_matrix, x, my):\n",
    "    inner_sum = 0\n",
    "    for i in range(len(x[0])):\n",
    "        inner_sum+= weight_matrix[i]*x[my][i]\n",
    "    return np.tanh(0.5*(inner_sum-threshold))\n",
    "\n",
    "def calculate_energy_function(t,O):\n",
    "    inner_sum = 0\n",
    "    for my in len(t):\n",
    "        inner_sum+= np.power(t[my] - O[my],2)\n",
    "    return 0.5*inner_sum\n",
    "\n",
    "\n",
    "def calculate_gradient(t, weight_matrix, x, threshold, learning_rate = 0.02, my_list = range(16)):\n",
    "\n",
    "    #Let's do it without matrix multiplication first and later think of a solution where we dont have 3 for loops\n",
    "    dw = np.zeros(w_ij.shape)\n",
    "    for i in range(len(w_ij)):\n",
    "        inner_sum = 0\n",
    "        for my in my_list:\n",
    "            O_my = calculate_output(threshold, weight_matrix,x, my)\n",
    "            #Here the  order of x[my][i] is important!\n",
    "            inner_sum += (t[my] - O_my)*x[my][i]\n",
    "        dw[i] = learning_rate*inner_sum\n",
    "    return dw    \n",
    "\n",
    "def esign(i):\n",
    "    if i == 0:\n",
    "        return 1\n",
    "    return np.sign(i)\n",
    "#Targe vectors\n",
    "A =  [-1, -1, 1, 1, -1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1] \n",
    "B = [1, 1, 1, 1, 1, -1, -1, -1, 1, -1, 1, -1, -1, -1, -1, -1] \n",
    "C = [-1, -1, -1, -1, -1, -1, -1, -1, 1, -1, -1, -1, -1, -1, 1, 1] \n",
    "D = [1, 1, 1, 1, -1, -1, -1, -1, -1, 1, -1, -1, 1, -1, -1, -1] \n",
    "E = [-1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, -1] \n",
    "F = [-1, -1, -1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1] \n",
    "G = [1, 1, -1, 1, -1, -1, 1, -1, 1, -1, 1, 1, -1, 1, 1, -1]\n",
    "#x vector\n",
    "with open(\"../data/input_data_numeric.csv\",\"r\") as f:\n",
    "    x = list(csv.reader(f, delimiter=\",\"))\n",
    "    for idx, el in enumerate(x):\n",
    "        x[idx] = list(map(int,el))\n",
    "    x = np.array(x)[:,1:]\n",
    "#Initialize variables with random inputs\n",
    "\n",
    "for t in (A, B,C,D,E,F):\n",
    "    for j in range(10):\n",
    "        w_ij = (rnd.rand(4,)*0.4)-np.ones(4,)*0.2\n",
    "        threshold = rnd.random_sample()*2 -1\n",
    "        learning_rate = 0.02\n",
    "        for i in range(100000):\n",
    "            dw = calculate_gradient(t,w_ij,x, threshold)\n",
    "            w_ij += dw\n",
    "            #We need to test!\n",
    "            finished = True\n",
    "            for el in range(16):\n",
    "                finished = finished and (t[el] == esign(calculate_output(threshold, w_ij, x, el)))\n",
    "            if finished:\n",
    "                break\n",
    "        if finished:\n",
    "            break\n",
    "    print(finished)"
   ]
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}