homework2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Homework 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "pycharm": {
     "is_executing": false
    }
   },
   "outputs": [],
   "source": [
    "############################\n",
    "# spamFilter.py implements a spam filter based on Paul\n",
    "# Graham's statistical algorithm.\n",
    "# \n",
    "# Exercise 1 for Homework 2 for CS344 at Calvin University\n",
    "# @author isa3\n",
    "# @version March 9, 2020\n",
    "############################\n",
    "\n",
    "'''\n",
    "calculate_word_probabilities returns a dictionary of strings\n",
    "mapped to their float likelihood of being in a spam email\n",
    "\n",
    "@params spamCorpus, nonSpamCorpus\n",
    "    lists of lists of strings, representing example spam\n",
    "    and non-spam messages respectively\n",
    "@return a dictionary of strings mapped to floats\n",
    "'''\n",
    "def calculate_word_probabilities(spamCorpus, nonSpamCorpus):\n",
    "    # spam hash table, tokens to # of occurrences\n",
    "    spamDict = {}\n",
    "    # nonspam hash table, tokens to # of occurrences\n",
    "    nonSpamDict = {}\n",
    "    # hash table mapping token to probability of spam\n",
    "    probabilityDict = {}\n",
    "\n",
    "    # tally occurrences of tokens in spam corpus\n",
    "    for message in spamCorpus:\n",
    "        for token in message:\n",
    "            token = token.lower()\n",
    "            if token in spamDict.keys():\n",
    "                spamDict[token] += 1\n",
    "            else:\n",
    "                spamDict[token] = 1;\n",
    "            # add each token as a key to the probability dict\n",
    "            if token not in probabilityDict.keys():\n",
    "                probabilityDict[token] = 0\n",
    "\n",
    "    # tally occurrences of tokens in nonspam corpus\n",
    "    for message in nonSpamCorpus:\n",
    "        for token in message:\n",
    "            token = token.lower()\n",
    "            if token in nonSpamDict.keys():\n",
    "                nonSpamDict[token] += 1\n",
    "            else:\n",
    "                nonSpamDict[token] = 1;\n",
    "            # add any nonspam tokens that haven't been added already\n",
    "            if token not in probabilityDict.keys():\n",
    "                probabilityDict[token] = 0\n",
    "\n",
    "    # calculate probabilities\n",
    "    for key in probabilityDict.keys():\n",
    "        if key in nonSpamDict.keys():\n",
    "            g = 2 * nonSpamDict[key]\n",
    "        else:\n",
    "            g = 0\n",
    "        if key in spamDict.keys():\n",
    "            b = spamDict[key]\n",
    "        else:\n",
    "            b = 0\n",
    "\n",
    "        if g + b > 1:\n",
    "            probabilityDict[key] = max(0.01, min(0.99, min(1.0, b/len(spamCorpus)) / (min(1.0, g/len(nonSpamCorpus)) + min(1.0, b/len(spamCorpus)))))\n",
    "        else:\n",
    "            probabilityDict[key] = 0\n",
    "\n",
    "    return probabilityDict\n",
    "\n",
    "'''\n",
    "calculate_message_spam_probability returns a float\n",
    "representing the probability of the message parameter being\n",
    "spam based on the probabilities parameter\n",
    "\n",
    "@params message A list of strings representing a message\n",
    "@params probabilities A dictionary of strings mapped to their\n",
    "    respective probabilities of being in a spam message\n",
    "\n",
    "@return a float representing the probability of message being spam\n",
    "'''\n",
    "def calculate_message_spam_probability(message, probabilities):\n",
    "    # initial product of probabilities\n",
    "    prod = 1.0\n",
    "    # initial product of inverse probabilities\n",
    "    inverse_prod = 1.0\n",
    "    # calculate final product and inverse product values\n",
    "    for token in message:\n",
    "        token = token.lower()\n",
    "        if token in probabilities.keys():\n",
    "            prod *= probabilities[token]\n",
    "            inverse_prod *= 1.0 - probabilities[token]\n",
    "            \n",
    "    return prod / (prod + inverse_prod)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a Bayesian approach to spam because it begins with a prior probability for a message to be spam (1.0) and then modifies that probability based on the likelihood calculated through data. This results in a posterior probability of the message being spam."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "pycharm": {
     "is_executing": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "i :  0.5\n",
      "am :  0.99\n",
      "spam :  0.99\n",
      "do :  0.3333333333333333\n",
      "not :  0\n",
      "like :  0.3333333333333333\n",
      "that :  0\n",
      "spamiam :  0\n",
      "green :  0.01\n",
      "eggs :  0.01\n",
      "and :  0.01\n",
      "ham :  0.01\n",
      "Probability of 'i do hate spam i am' being spam:\n",
      "0.9997959808221973\n",
      "Probability of 'spam ham confused i do like i' being spam:\n",
      "0.1999999999999998\n"
     ]
    }
   ],
   "source": [
    "spam_corpus = [[\"I\", \"am\", \"spam\", \"spam\", \"I\", \"am\"], [\"I\", \"do\", \"not\", \"like\", \"that\", \"spamiam\"]]\n",
    "ham_corpus = [[\"do\", \"i\", \"like\", \"green\", \"eggs\", \"and\", \"ham\"], [\"i\", \"do\"]]\n",
    "spam_filter_probabilities = calculate_word_probabilities(spam_corpus, ham_corpus)\n",
    "\n",
    "for key in spam_filter_probabilities.keys():\n",
    "    print(key, \": \", spam_filter_probabilities[key])\n",
    "\n",
    "test_message = [\"i\", \"do\", \"hate\", \"spam\", \"i\", \"am\"]\n",
    "\n",
    "print(\"Probability of 'i do hate spam i am' being spam:\")\n",
    "print(calculate_message_spam_probability(test_message, spam_filter_probabilities))\n",
    "\n",
    "test_message2 = [\"spam\", \"ham\", \"confused\", \"i\", \"do\", \"like\", \"i\"]\n",
    "\n",
    "print(\"Probability of 'spam ham confused i do like i' being spam:\")\n",
    "print(calculate_message_spam_probability(test_message2, spam_filter_probabilities))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.2\n",
    "\n",
    "a."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "pycharm": {
     "is_executing": false
    }
   },
   "outputs": [],
   "source": [
    "'''\n",
    "This module implements the Bayesian network for Figure 14.12\n",
    "in the textbook.\n",
    "\n",
    "Written for part 2 of homework 2 for CS344 at Calvin University.\n",
    "\n",
    "@author: isa3\n",
    "@version March 8, 2020\n",
    "'''\n",
    "\n",
    "import sys\n",
    "sys.path.append('/home/isa3/cs344-code/tools/aima')\n",
    "\n",
    "from probability import BayesNet, enumeration_ask\n",
    "\n",
    "# Utility variables\n",
    "T, F = True, False\n",
    "\n",
    "wet = BayesNet([\n",
    "    ('Cloudy', '', 0.5),\n",
    "    ('Sprinkler', 'Cloudy', {T: 0.10, F: 0.50}),\n",
    "    ('Rain', 'Cloudy', {T: 0.80, F: 0.20}),\n",
    "    ('WetGrass', 'Sprinkler Rain', {(T, T): 0.99, (T, F): 0.9, (F, T): 0.9, (F, F): 0.0})\n",
    "    ])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "b."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are no independent values in the full joint probability distribution for this domain."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Showing that WetGrass is not absolutely independent of the other variables.\n",
      "P(WetGrass):\t\t\t\t False: 0.353, True: 0.647\n",
      "P(WetGrass | Cloudy, Rain, Sprinkler):\t False: 0.01, True: 0.99\n",
      "Showing that Rain is not absolutely independent of the other variables.\n",
      "P(Rain):\t\t\t\t False: 0.5, True: 0.5\n",
      "P(Rain | Cloudy, Sprinkler, WetGrass):\t False: 0.185, True: 0.815\n",
      "Showing that Sprinkler is not absolutely independent of the other variables.\n",
      "P(Sprinkler):\t\t\t\t False: 0.7, True: 0.3\n",
      "P(Sprinkler | Cloudy, Rain, WetGrass):\t False: 0.891, True: 0.109\n",
      "Showing that Cloudy is not absolutely independent of the other variables.\n",
      "P(Cloudy):\t\t\t\t False: 0.5, True: 0.5\n",
      "P(Cloudy | WetGrass, Rain, Sprinkler):\t False: 0.556, True: 0.444\n"
     ]
    }
   ],
   "source": [
    "print(\"Showing that WetGrass is not absolutely independent of the other variables.\")\n",
    "print(\"P(WetGrass):\\t\\t\\t\\t\", enumeration_ask('WetGrass', dict(), wet).show_approx())\n",
    "print(\"P(WetGrass | Cloudy, Rain, Sprinkler):\\t\", enumeration_ask('WetGrass', dict(Cloudy=T, Rain=T, Sprinkler=T), wet).show_approx())\n",
    "\n",
    "print(\"Showing that Rain is not absolutely independent of the other variables.\")\n",
    "print(\"P(Rain):\\t\\t\\t\\t\", enumeration_ask('Rain', dict(), wet).show_approx())\n",
    "print(\"P(Rain | Cloudy, Sprinkler, WetGrass):\\t\", enumeration_ask('Rain', dict(Cloudy=T, Sprinkler=T, WetGrass=T), wet).show_approx())\n",
    "\n",
    "print(\"Showing that Sprinkler is not absolutely independent of the other variables.\")\n",
    "print(\"P(Sprinkler):\\t\\t\\t\\t\",enumeration_ask('Sprinkler', dict(), wet).show_approx())\n",
    "print(\"P(Sprinkler | Cloudy, Rain, WetGrass):\\t\", enumeration_ask('Sprinkler', dict(Cloudy=T, Rain=T, WetGrass=T), wet).show_approx())\n",
    "\n",
    "print(\"Showing that Cloudy is not absolutely independent of the other variables.\")\n",
    "print(\"P(Cloudy):\\t\\t\\t\\t\", enumeration_ask('Cloudy', dict(), wet).show_approx())\n",
    "print(\"P(Cloudy | WetGrass, Rain, Sprinkler):\\t\", enumeration_ask('Cloudy', dict(WetGrass=T, Rain=T, Sprinkler=T), wet).show_approx())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "c."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Showing that given Rain and Sprinkler, WetGrass is independent of Cloudy.\n",
      "False: 0.01, True: 0.99\n",
      "False: 0.01, True: 0.99\n",
      "Showing that given Cloudy, Rain is independent of Sprinkler.\n",
      "False: 0.2, True: 0.8\n",
      "False: 0.2, True: 0.8\n",
      "Showing that given Cloudy, Sprinkler is independent of Rain.\n",
      "False: 0.9, True: 0.1\n",
      "False: 0.9, True: 0.1\n",
      "Showing that given Rain and Sprinkler, Cloudy is independent of WetGrass.\n",
      "False: 0.556, True: 0.444\n",
      "False: 0.556, True: 0.444\n"
     ]
    }
   ],
   "source": [
    "print(\"Showing that given Rain and Sprinkler, WetGrass is independent of Cloudy.\")\n",
    "print(enumeration_ask('WetGrass', dict(Rain=T, Sprinkler=T), wet).show_approx())\n",
    "print(enumeration_ask('WetGrass', dict(Cloudy=T, Rain=T, Sprinkler=T), wet).show_approx())\n",
    "\n",
    "#    Given Cloudy, Rain is independent of Sprinkler.\n",
    "\n",
    "print(\"Showing that given Cloudy, Rain is independent of Sprinkler.\")\n",
    "print(enumeration_ask('Rain', dict(Cloudy=T), wet).show_approx())\n",
    "print(enumeration_ask('Rain', dict(Cloudy=T, Sprinkler=T), wet).show_approx())\n",
    "\n",
    "#    Given Cloudy, Sprinkler is independent of Rain.\n",
    "\n",
    "print(\"Showing that given Cloudy, Sprinkler is independent of Rain.\")\n",
    "print(enumeration_ask('Sprinkler', dict(Cloudy=T), wet).show_approx())\n",
    "print(enumeration_ask('Sprinkler', dict(Cloudy=T, Rain=T), wet).show_approx())\n",
    "\n",
    "# Given Rain and Sprinkler, Cloudy is independent of WetGrass.\n",
    "print(\"Showing that given Rain and Sprinkler, Cloudy is independent of WetGrass.\")\n",
    "print(enumeration_ask('Cloudy', dict(Rain=T, Sprinkler=T), wet).show_approx())\n",
    "print(enumeration_ask('Cloudy', dict(WetGrass=T, Rain=T, Sprinkler=T), wet).show_approx())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "d."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "i. P(Cloudy)\n",
      "False: 0.5, True: 0.5\n"
     ]
    }
   ],
   "source": [
    "print(\"i. P(Cloudy)\")\n",
    "print(enumeration_ask('Cloudy', dict(), wet).show_approx())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "P(Cloudy) = < 0.5, 0.5 >"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ii. P(Sprinkler | Cloudy)\n",
      "False: 0.9, True: 0.1\n"
     ]
    }
   ],
   "source": [
    "print(\"ii. P(Sprinkler | Cloudy)\")\n",
    "print(enumeration_ask('Sprinkler', dict(Cloudy=T), wet).show_approx())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "P(Sprinkler | Cloudy) = < 0.10, 0.90 >"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iii. P(Cloudy | Sprinkler ^ !Rain)\n",
      "False: 0.952, True: 0.0476\n"
     ]
    }
   ],
   "source": [
    "print(\"iii. P(Cloudy | Sprinkler ^ !Rain)\")\n",
    "print(enumeration_ask('Cloudy', dict(Sprinkler=T, Rain=F), wet).show_approx())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "P(Cloudy | Sprinkler ^ !Rain) = alpha P(Cloudy, Sprinkler, !Rain)\n",
    "\n",
    "                          = alpha P(Cloudy) * P(Sprinkler | Cloudy) * P(!Rain | Cloudy)\n",
    "                          \n",
    "                          = alpha < P(Cloudy) * P(Sprinkler | Cloudy) * P(!Rain | Cloudy)\n",
    "                          \n",
    "                                  P(!Cloudy) * P(Sprinkler | !Cloudy) * P(!Rain | !Cloudy) >\n",
    "                                  \n",
    "                          = alpha < 0.5 * 0.1 * 0.2, 0.5 * 0.5 * 0.8 >\n",
    "                          \n",
    "                          = alpha < .01, .20 >\n",
    "                          \n",
    "                          = < .048, .952 >"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iv. P(WetGrass | Cloudy ^ Sprinkler ^ Raining)\n",
      "False: 0.01, True: 0.99\n"
     ]
    }
   ],
   "source": [
    "print(\"iv. P(WetGrass | Cloudy ^ Sprinkler ^ Raining)\")\n",
    "print(enumeration_ask('WetGrass', dict(Cloudy=T, Sprinkler=T, Rain=T), wet).show_approx())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "P(WetGrass | Cloudy ^ Sprinkler ^ Raining) = P(WetGrass | Sprinkler ^ Raining) \n",
    "\n",
    "                                            = < 0.99, 0.01 >"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "v. P(Cloudy | !WetGrass)\n",
      "False: 0.639, True: 0.361\n"
     ]
    }
   ],
   "source": [
    "print(\"v. P(Cloudy | !WetGrass)\")\n",
    "print(enumeration_ask('Cloudy', dict(WetGrass=F), wet).show_approx())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "P(Cloudy | !Wetgrass) = \n",
    "\n",
    "    P(Cloudy) * \n",
    "\n",
    "    ( [ P(Rain | Cloudy) * P(!Wet  | Rain) * P(Sprinkler | Cloudy) * P(!Wet | Sprinkler) ] +\n",
    "\n",
    "      [ P(!Rain | Cloudy) * P(!Wet  | !Rain) * P(Sprinkler | Cloudy) * P(!Wet | Sprinkler) ] +\n",
    "  \n",
    "      [ P(Rain | Cloudy) * P(!Wet  | Rain) * P(!Sprinkler | Cloudy) * P(!Wet | !Sprinkler) ] +\n",
    "  \n",
    "      [ P(!Rain | Cloudy) * P(!Wet  | !Rain) * P(!Sprinkler | Cloudy) * P(!Wet | !Sprinkler) ]\n",
    "                                                                                  )\n",
    "      \n",
    "      \n",
    "= alpha < P(Cloudy) * \n",
    "\n",
    "    ( [ P(Rain | Cloudy) * P(Sprinkler | Cloudy) * P(!Wet | Rain ^ Sprinkler) ] +\n",
    "\n",
    "      [ P(!Rain | Cloudy) * P(Sprinkler | Cloudy) * P(!Wet | !Rain ^ Sprinkler) ] +\n",
    "  \n",
    "      [ P(Rain | Cloudy) * P(!Sprinkler | Cloudy) * P(!Wet | Rain ^ !Sprinkler) ] +\n",
    "  \n",
    "      [ P(!Rain | Cloudy) * P(!Sprinkler | Cloudy) * P(!Wet | !Rain ^ !Sprinkler) ] ) ,\n",
    "  \n",
    "    P(!Cloudy) * \n",
    "\n",
    "    ( [ P(Rain | !Cloudy) * P(Sprinkler | !Cloudy) * P(!Wet | Rain ^ Sprinkler) ] +\n",
    "\n",
    "      [ P(!Rain | !Cloudy) * P(Sprinkler | !Cloudy) * P(!Wet | !Rain ^ Sprinkler) ] +\n",
    "  \n",
    "      [ P(Rain | !Cloudy) * P(!Sprinkler | !Cloudy) * P(!Wet | Rain ^ !Sprinkler) ] +\n",
    "  \n",
    "      [ P(!Rain | !Cloudy) * P(!Sprinkler | !Cloudy) * P(!Wet | !Rain ^ !Sprinkler) ] ) >\n",
    "  \n",
    "\n",
    "\n",
    "= alpha < 0.5 *\n",
    "\n",
    "    ( [ .8 * .1 * .01 ] +\n",
    "\n",
    "      [ .2 * .1 * .1 ] +\n",
    "  \n",
    "      [ .8 * .9 * .1 ] +\n",
    "  \n",
    "      [ .2 * .9 * 1.0 ] ) ,\n",
    "  \n",
    "      0.5 *\n",
    "  \n",
    "    ( [ .2 * .5 * .01 ] +\n",
    "\n",
    "      [ .8 * .5 * .1 ] +\n",
    "  \n",
    "      [ .2 * .5 * .1] +\n",
    "  \n",
    "      [ .8 * .5 * 1.0] ) >\n",
    "  \n",
    "\n",
    "= alpha < .1274, 0.2255 >\n",
    "\n",
    "    alpha = 1 / 0.3529\n",
    "    \n",
    "= <  0.361 , 0.639 >"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7"
  },
  "pycharm": {
   "stem_cell": {
    "cell_type": "raw",
    "metadata": {
     "collapsed": false
    },
    "source": []
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}