20140120-CoCoSci Problem Set 2 walkthrough

20140120-CoCoSci Problem Set 2.ipynb

{
 "metadata": {
  "name": "20140120-CoCoSci Problem Set 2"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "The first thing to do is to use a set of 3 features to build examples. An individual example will be a feature paired with a Boolean label, e.g. $\\{(f_0,0), (f_1,0), (f_2,0)\\}$, which we can abbreviate as $000$. This allows the use of binary strings to represent concepts. The following matrix is what the set of examples should look like with each row corresponding to an individual example and each column corresponding to a feature.\n\n$$\n\\begin{equation*}\nX = \n  \\begin{bmatrix}\n    0  & 0  & 0 \\\\\n    0  & 0  & 1 \\\\\n    0  & 1  & 0 \\\\\n    \\vdots & \\vdots & \\vdots \\\\\n    1 & 1 & 0 \\\\\n    1 & 1 & 1\n  \\end{bmatrix}\n\\end{equation*}\n$$"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "def index2bool(index,width):\n    b_string = binary_repr(index,width)\n    b_dict = {\"0\":False, \"1\":True}\n    return array( [ b_dict[i] for i in b_string.format(index) ] )\n\ndef bool2index(b_array):\n    b_dict = {False: \"0\", True:\"1\"}\n    b_string = ''.join([ b_dict[i] for i in b_array ])\n    return int(b_string, 2)",
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 112
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "num_features = 3\nexamples = [ index2bool(i,num_features) for i in range(2**num_features) ]\nexamples = array(examples)\nexamples",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 113,
       "text": "array([[False, False, False],\n       [False, False,  True],\n       [False,  True, False],\n       [False,  True,  True],\n       [ True, False, False],\n       [ True, False,  True],\n       [ True,  True, False],\n       [ True,  True,  True]], dtype=bool)"
      }
     ],
     "prompt_number": 113
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "To build the set of single-feature concepts, `sf_concepts`, we start with the un-negated features. Each column of the example matrix, `examples[:,i]`, corresponds to a concept that is true when an unnegated feature is true and false when that feature is false. \n\nI'll convert each concept to an index so that we can quickly compare two concepts. I'll also use python's `set` datatype to ensure that only one of each index is in each concept class."
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "sf_concepts = { bool2index(examples[:,i]) for i in range(num_features) }\nsf_concepts",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 114,
       "text": "{15, 51, 85}"
      }
     ],
     "prompt_number": 114
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "The next step is to operate on concepts to form our concept classes. I've written these functions to operate on indices rather than a concept vector. I'll use negation, `index_not()`, to build a set of single-feature concepts; and `index_and()` to build the set of conjunctions; and or `index_or()` to build the set of disjunctions."
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "def index_not(index,num_features=3):\n    out = bitwise_not(uint8(index))\n    if out < 2**2**num_features:\n        return out\n    else:\n        return index\n\ndef index_and(index1,index2,num_features):\n    out = bitwise_and(index1,index2)\n    if out < 2**2**num_features:\n            return out\n    else:\n            return index1\n\ndef index_or(index1,index2,num_features):\n    out = bitwise_or(index1,index2)\n    if out < 2**2**num_features:\n        return out\n    else:\n        return index1",
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 87
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "In the next cells, I'll repeatedly use these operations to form new concepts. For single-feature cocnepts, we only need to use negation once. But for conjunction and disjunction, I'll make use of `while` loops to ensure that I keep using the operation until no new concepts are added."
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "old = sf_concepts.copy()\nfor c in old:\n    sf_concepts.add(index_not(c,num_features=num_features))\nsf_concepts",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 88,
       "text": "{15, 51, 85, 170, 204, 240}"
      }
     ],
     "prompt_number": 88
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "c_concepts = sf_concepts.copy()\nold = c_concepts.copy()\ngo_flag = True\nwhile go_flag:\n    for c1 in old:\n        for c2 in old:\n            c_concepts.add(index_and(c1,c2,num_features=num_features))\n    go_flag = len(old) < len(c_concepts)\n    old = c_concepts.copy()\nc_concepts",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 89,
       "text": "{0,\n 1,\n 2,\n 3,\n 4,\n 5,\n 8,\n 10,\n 12,\n 15,\n 16,\n 17,\n 32,\n 34,\n 48,\n 51,\n 64,\n 68,\n 80,\n 85,\n 128,\n 136,\n 160,\n 170,\n 192,\n 204,\n 240}"
      }
     ],
     "prompt_number": 89
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "d_concepts = sf_concepts.copy()\nold = d_concepts.copy()\ngo_flag = True\nwhile go_flag:\n    for c1 in old:\n        for c2 in old:\n            d_concepts.add(index_or(c1,c2,num_features=num_features))\n    go_flag = len(old) < len(d_concepts)\n    old = d_concepts.copy()\nd_concepts",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 92,
       "text": "{15,\n 51,\n 63,\n 85,\n 95,\n 119,\n 127,\n 170,\n 175,\n 187,\n 191,\n 204,\n 207,\n 221,\n 223,\n 238,\n 239,\n 240,\n 243,\n 245,\n 247,\n 250,\n 251,\n 252,\n 253,\n 254,\n 255}"
      }
     ],
     "prompt_number": 92
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "Finally, to simulate teaching, I'll make a function that inputs a teaching set in the form of a string with `1`s and `0`s for the taught examples and `*`s for omitted examples. For example, a teacher that teaches every other example for the concept 85 (`11110000`) would use the teaching set `1*1*0*0*`. The `consistent()` function takes this teaching set and finds all concepts that are consistent with it. A teacher teaches a target concept when that is the only concepts consistent with the teaching sample."
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "def consistent(ts,concept_class,num_features=3):\n    cons = set()\n    for i in concept_class:\n        candidate = binary_repr(i,width=2**num_features)\n        comparison = [ '1' if (ts[j] == '*')|(candidate[j] == ts[j]) else '0' for j in range(len(ts))]\n        comparison = ''.join(comparison)\n        if comparison == '1'*len(ts):\n            cons.add(i)\n    return cons",
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 107
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "Below, you can see that using the teaching set `1111****` to teach concept 240 works in the class of single feature concepts but not in the other two."
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "consistent('1111****',d_concepts)",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 108,
       "text": "{240, 243, 245, 247, 250, 251, 252, 253, 254, 255}"
      }
     ],
     "prompt_number": 108
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "consistent('1111****',c_concepts)",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 109,
       "text": "{240, 243, 245, 250, 252, 255}"
      }
     ],
     "prompt_number": 109
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "consistent('1111****',sf_concepts)",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 110,
       "text": "{240}"
      }
     ],
     "prompt_number": 110
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "",
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}