index.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction to Programming in Python\n",
    "\n",
    "In this short introduction, I'll introduce you to the basics of programming, using the Python programming language.  By the end of it, you should hopefully be able to write your own HMM POS-tagger."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### First Steps\n",
    "\n",
    "You can think of a program as a series of instructions for the computer, which it will follow one after the other.  When the computer runs the program, it will create objects and manipulate them, according to our instructions.  For example, we could tell it to create some objects representing numbers, add them together, then show us (`print`) the result.  If you click on the block of code below to select it, then click on the \"run\" button in the toolbar above (or press ctrl+enter), you should see the output appear underneath."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "kim = 4\n",
    "jamie = 3\n",
    "chris = kim + jamie\n",
    "print(chris)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now try editing the above code to do a different calculation, and then run it again.  As well as adding (`+`), we can also subtract (`-`), multiply (`*`), and divide (`/`).  Note that `kim`, `jamie`, and `chris` are just names we've assigned to the objects, and you can change the names to whatever you want.\n",
    "\n",
    "These named objects are called **variables**.  We can also calculate things without explicitly naming the objects, as shown below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print(3 + 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you work through this notebook, I would encourage you to play with the examples until you feel comfortable with what the code is doing.\n",
    "\n",
    "If a line of code can't be interpreted, Python will throw an error.  Run the following code, which has a mistake - it will tell you which line caused the error, and give you an error message."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "hamster = 2 = 3\n",
    "print(hamster)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now edit the above code so that it does not throw an error, then run it again.\n",
    "\n",
    "Don't be worried if you introduce errors as you play with the code in this notebook - finding errors and fixing them is called **debugging**, and is an important part of programming."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, if we write a hash symbol, Python will ignore everything after it in that line.  This is called a **comment**, and is useful to document what the code is doing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "kim = 4  # Define a variable\n",
    "jamie = 3  # Define another variable\n",
    "chris = kim + jamie  # Add these objects together, and save the result as a new variable\n",
    "print(chris)  # Print the new variable\n",
    "\n",
    "chris = 10  # If we re-define a variable, it replaces the old value\n",
    "print(chris)\n",
    "chris = chris + 1  # We can also assign a new value to a variable based on its current value\n",
    "print(chris)\n",
    "chris += 1  # This is shorthand for the line 'chris = chris + 1'\n",
    "print(chris)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Types of Object\n",
    "\n",
    "There are many types of object in Python, apart from numbers.  Another type is a **string**, to represent text.  A string must start and finish with quotes (either single or double quotes, as long as the same kind is used)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "text = \"hello\"\n",
    "more_text = ' world!'\n",
    "combined = text + more_text  # '+' will concatenate strings\n",
    "print(combined)\n",
    "\n",
    "repeated = text * 5  # '*' will repeat strings\n",
    "print(repeated)\n",
    "\n",
    "string_23 = '23'  # This is a string\n",
    "integer_23 = 23  # This is an integer\n",
    "\n",
    "# What do you think will be printed if you uncomment the lines below?\n",
    "#print(string_23 * 3)\n",
    "#print(integer_23 * 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can refer to specific characters in a string, and refer to substrings, using square brackets:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "long_string = \"they fish in rivers in December\"\n",
    "letter = long_string[0]  # We start counting from zero.  This does: letter = \"t\"\n",
    "print(letter)\n",
    "another_letter = long_string[15]\n",
    "print(another_letter)\n",
    "\n",
    "end = long_string[-1]  # If you give a negative number, it counts backwards from the end\n",
    "print(end)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "long_string = \"they fish in rivers in December\"\n",
    "substring = long_string[0:3]  # We can get a substring by specifying start and end points, separated by a colon\n",
    "print(substring)  # This prints the first three characters\n",
    "\n",
    "long_substring = long_string[5:]  # If you don't specify a number, it uses the very start or very end\n",
    "print(long_substring)  # This prints everything except the first five characters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Other important types of object are **lists**, **tuples**, and **dictionaries**.  Lists and tuples are made up of several objects in a particular order.  Dictionaries map from one set of objects (the **keys**) to another (the **values**), and have no inherent order.  Lists are written with square brackets `[]`, tuples with round brackets `()`, and dictionaries with curly brackets `{}`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "my_list = [1, 5, 12, 'dog']\n",
    "my_tuple = ('cat', 17, 18)\n",
    "my_dict = {'banana': 'yellow', 'apple': 'green', 'orange': 'orange'}\n",
    "\n",
    "print(my_tuple[0])  # You can refer to elements of a tuple or list, in the same way as for a string\n",
    "print(my_dict['apple'])  # You can also look something up in a dictionary in this way\n",
    "\n",
    "# Lists and dictionaries can also be changed:\n",
    "my_list[1] = 100\n",
    "my_dict['apple'] = 'red'\n",
    "print(my_list)\n",
    "print(my_dict)\n",
    "\n",
    "# Note you can't change strings or tuples like this (what happens if you try?)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# This dict maps from bigrams (tuples of strings) to integers\n",
    "tuple_dict = {('the', 'fish'): 351, ('dog', 'barked'): 233, ('cat', 'barked'): 1}\n",
    "\n",
    "# If a key is a tuple, the round brackets of the tuple are optional:\n",
    "print(tuple_dict[('the', 'fish')])\n",
    "print(tuple_dict['the', 'fish'])\n",
    "\n",
    "# Note that you can't use lists and dicts as keys of a dict (because lists and dicts can be changed)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Functions and Methods\n",
    "\n",
    "So far, we've written programs where each line is executed exactly once.  However, it is often useful to run the same code in different places, and we can do that using a **function**.  We've seen one function so far, namely the `print` function.  We can also define our own, using the keyword `def`.  The function will take some number of arguments (possibly zero), run some code, and `return` a result.  The code inside the function is indented (here, indented with 4 spaces)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def add_one(x):  # This defines a function 'add_one' which takes one argument 'x'\n",
    "    y = x + 1  # We create a new object which is one larger\n",
    "    return y  # We return the result\n",
    "\n",
    "new_value = add_one(10)  # We're calling the add_one function, with x=10\n",
    "print(new_value)  # We're calling the print function\n",
    "print(add_one(add_one(0)))  # We can also pass the result of one function as the input to another function\n",
    "\n",
    "def repeat_substring(string, number):  # This function takes two arguments\n",
    "    substring = string[0:3]  # We take the first three letters in the string\n",
    "    return substring * number  # We return this substring, repeated some number of times\n",
    "\n",
    "print(repeat_substring('cathode', 3))\n",
    "\n",
    "# If the print function is given multiple arguments, it prints them all, separated by a space\n",
    "print('and finally,', repeat_substring('doggerel', add_one(1)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Try writing your own function for \"Pig Latin\" - it should take a string, remove the first letter, put the first letter on the end, then add \"ay\".  For example,\n",
    "\n",
    "\"pig\" -> \"igpay\" (\"ig\" + \"p\" + \"ay\")\n",
    "\n",
    "\"latin\" -> \"atinlay\" (\"atin\" + \"l\" + \"ay\")\n",
    "\n",
    "\"eat\" -> \"ateay\" (\"at\" + \"e\" + \"ay\")\n",
    "\n",
    "(This is a slight simplification of the children's game.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some types of object have built-in functions, called **methods**.  We can call a method by writing `.` after an object's name, followed by the name of the method.  Different types of object have different methods available.  Here is one method of strings, called `split`, which splits it up into a list of smaller strings:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "tagged_string = \"they_PNP\"\n",
    "token_tag = tagged_string.split('_')  # split whenever we see '_'\n",
    "print(token_tag)\n",
    "token, tag = tagged_string.split('_')  # we can also assign each element to a separate variable\n",
    "print(token, tag)\n",
    "\n",
    "long_string = \"they fish in rivers in December\"\n",
    "tokens = long_string.split()  # if we don't specify what to split on, the function splits on whitespace\n",
    "print(tokens)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Loops\n",
    "\n",
    "Another way that we can execute lines multiple times is with a **loop**.  If we have an object that has multiple elements (like a list, tuple, or dict), then we can loop through them, and execute some code for each element.  We write a loop using the keywords `for` and `in`, and define a new variable that stands for the current element.  As with a function, the code inside the loop is indented."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for x in [1, 2, 3, 'pineapple']:\n",
    "    print(x, 5*x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "my_dict = {'banana': 'yellow', 'apple': 'green', 'orange': 'orange'}\n",
    "\n",
    "for x in my_dict:  # This iterates through the keys of the dict\n",
    "    print('this', x, 'is', my_dict[x])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "tuple_dict = {('the', 'fish'): 351, ('dog', 'barked'): 233, ('cat', 'barked'): 1}\n",
    "\n",
    "for thing in tuple_dict:  # Each x is a tuple\n",
    "    print(thing[0])\n",
    "\n",
    "for p, q in tuple_dict:  # We can break the tuple into two parts\n",
    "    print(p, q, tuple_dict[p,q])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Variables defined inside a loop will be available in the next iteration.  For example, let's iterate through a list of tokens and print both the current token and the previous token:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "tokens = \"they fish in rivers in December\".split()\n",
    "\n",
    "previous = \"nothing yet...\"\n",
    "for current in tokens:\n",
    "    print('processing new token!')\n",
    "    print('current token is', current)\n",
    "    print('previous token was', previous)\n",
    "    previous = current  # Assign a new value to 'previous', in preparation for the next iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What happens if we get rid of the line `previous = \"nothing yet...\"`?\n",
    "\n",
    "Try writing a function that will take a list of numbers as input, and return the product of all the numbers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Logic\n",
    "\n",
    "Sometimes we may want to do different things depending on the value of an object.  For example, suppose we have a list of strings, and want to print everything that starts with the letter 'h'.  To do this, we write `if`, followed by a condition that can be `True` or `False`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "my_list = 'the hungry hamster has a question to ask'.split()\n",
    "\n",
    "for w in my_list:\n",
    "    if w[0] == 'h':  # A *double* equals sign checks for equality\n",
    "        print(w)  # As with loops and function, we indent the code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Optionally, we can say what to do if the condition is not true, using the keyword `else`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for w in 'the hungry hamster has a question to ask'.split():\n",
    "    if w[0] == 'h':\n",
    "        print(w, 'begins with h')\n",
    "    else:\n",
    "        print(w, 'does not begin with h')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here are a few examples of conditions that we can use:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print('1 == 1', 1 == 1)  # Equality\n",
    "print('1 > 2', 1 > 2)  # More than\n",
    "print('1 < 2', 1 < 2)  # Less than\n",
    "print('1 in [1, 2, 3]', 1 in [1, 2, 3])  # Being in a list\n",
    "print('5 in [1, 2, 3]', 5 in [1, 2, 3])\n",
    "print('\"h\" in \"hamster\"', \"h\" in \"hamster\")  # Being in a string\n",
    "print('\"cat\" in {\"cat\": 5, \"the\" : 8}', \"cat\" in {\"cat\": 5, \"the\" : 8})  # Being a key in a dictionary\n",
    "print('\"dog\" in {\"cat\": 5, \"the\" : 8}', \"dog\" in {\"cat\": 5, \"the\" : 8})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Putting it all together\n",
    "\n",
    "For example, let's go through a toy corpus and count how many times each token appears."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "corpus = 'Once upon a time there was a dragon . The dragon liked to fly . The end .'\n",
    "tokens = corpus.split()\n",
    "frequency = {}  # An empty dictionary, which will map from words to their counts\n",
    "\n",
    "for w in tokens:\n",
    "    if w in frequency:  # If we've seen the word before\n",
    "        frequency[w] += 1  # Add 1 to the count\n",
    "    else:\n",
    "        frequency[w] = 1  # Start the count from 1\n",
    "\n",
    "# Let's print all the words that appear more than once\n",
    "\n",
    "for w in frequency:\n",
    "    if frequency[w] > 1:\n",
    "        print(w)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the above code, we are effectively saying that when a word is not in the `frequency` dictionary, the default value is 0.  Because this is a common thing to do, there is a special type of dict called a `defaultdict`, which can be given a default value.  The code below effectively does the same thing as the code above.\n",
    "\n",
    "Because a `defaultdict` is not a core part of Python, we have to **import** it to make it available.  There are many packages which extend Python in various ways, including a number of packages specifically for Natural Language Processing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from collections import defaultdict  # Make defaultdict available\n",
    "\n",
    "corpus = 'Once upon a time there was a dragon . The dragon liked to fly . The end .'\n",
    "tokens = corpus.split()\n",
    "frequency = defaultdict(int)  # The default value will be an int (integer), which defaults to 0\n",
    "\n",
    "for w in tokens:\n",
    "    frequency[w] += 1  # Add 1 to the count\n",
    "\n",
    "# Let's print all the words that appear more than once\n",
    "\n",
    "for w in frequency:\n",
    "    if frequency[w] > 1:\n",
    "        print(w)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Writing an HMM POS-tagger\n",
    "\n",
    "You should now know enough programming to write your own HMM part-of-speech tagger!  Use everything we've covered above to split up the corpus into the bits you need, count the frequencies of the things you need, calculate the relevant probabilities, and finally write a function that will take a tagged string as input, and return the probability of that sequence in the model.\n",
    "\n",
    "The comments below should guide you through writing a tagger.  You can uncomment lines and complete them, as you need to - lines with '...' are incomplete!  If you're halfway through writing the tagger and you're not sure if you're not sure if you've done something right, you can `print` things to check that they're what you expect."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "corpus = \"They_PNP used_VVD to_TO0 can_VVI fish_NN2 in_PRP those_DT0 towns_NN2 ._PUN These_DT0 days_NN2 now_AV0 in_PRP these_DT0 areas_NN2 few_DT0 people_NN2 can_VM0 fish_VVB ._PUN\"\n",
    "\n",
    "### We need to find the frequency of each tag, each tag-tag bigram, and each tag-token combination\n",
    "### First, we need to define the right type of object that will record these frequencies\n",
    "### If you want to use a type that hasn't been imported, make sure to import it first\n",
    "\n",
    "#tag_count = ...\n",
    "#tag_tag_count = ...\n",
    "#tag_token_count = ...\n",
    "\n",
    "### Next, we need to calculate these counts by looping over the corpus\n",
    "\n",
    "#token_tag_list = corpus...\n",
    "#previous_tag = ...\n",
    "#for token_tag in token_tag_list:\n",
    "#    token, tag = ...\n",
    "#    tag_count[...] ...\n",
    "#    tag_tag_count[...] ...\n",
    "#    tag_token_count[...] ...\n",
    "#    previous_tag ...\n",
    "\n",
    "### Finally, we need to use these counts to calculate the probabilities\n",
    "### First define the right type of object\n",
    "\n",
    "#tag_tag_prob = ...\n",
    "#tag_token_prob = ...\n",
    "\n",
    "### And then do the calculation\n",
    "\n",
    "#for ... in ...:\n",
    "#    tag_tag_prob[...] = ...\n",
    "\n",
    "#for ... in ...:\n",
    "#    tag_token_prob[...] = ...\n",
    "\n",
    "### We have now calculated all the probabilities we need for a Hidden Markov Model!\n",
    "### Let's define a function that will take a tagged sequence, and calculate the probability of generating it\n",
    "### The 'text' variable will be something like \"They_PNP fished_VVD\"\n",
    "\n",
    "#def prob(text):\n",
    "#    token_tag_list = ...\n",
    "#    result = ...\n",
    "#    previous_tag = ...\n",
    "#    for token_tag in token_tag_list:\n",
    "#        token, tag = ...\n",
    "#        result *= ...\n",
    "#        result *= ...\n",
    "#        previous_tag = ...\n",
    "#    return result\n",
    "\n",
    "### Now, for the last step! Here are the two sequences we wanted to compare:\n",
    "\n",
    "#option1 = 'These_DT0 areas_NN2 can_VM0 fish_VVB'\n",
    "#option2 = 'These_DT0 areas_NN2 can_VVB fish_NN2'\n",
    "\n",
    "#prob1 = prob(option1)\n",
    "#prob2 = prob(option2)\n",
    "\n",
    "#print(prob1)\n",
    "#print(prob2)\n",
    "#print(prob2 > prob1)\n",
    "\n",
    "### If you change the corpus at the beginning, see how the results change"
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}