Perceptron

The perceptron algorithm attempts to find a line of separation between two classes of data--hence it is a classification algorithm. 
Below is the python code for the perceptron algorithm. We first generate a dataset with two dimensional input and one-dimensional output. The input is normally distributed along both axes. The output, y, is either +1 or -1. The training set is a list of tuples of the form ([x1, x2], y) where the first element of the tuple is a list (actually a numpy array in the code, but for simplicity, I write it as a list), and the second element is the output. 
Then we feed the training set to the learning algorithm. The perceptron function initializes the weight vector, w, randomly. It then iterates over the training set data. At each iteration, we multiply w by x, resulting in the dot product over the two vectors. If this dot product is positive, then the point x is on the correct side of the dividing line. If the dot product is negative, then the point x is on the wrong side of the dividing line, and therefore the classifier is wrong. To correct this wrong, we nudge the line slightly.  

#! /usr/bin/env python

import math
import numpy as np
from numpy.random import normal
from pylab import plot, cla, show, norm, rand, xlabel, ylabel, title, legend, get_cmap, savefig, xlim, ylim
from random import shuffle, random
import matplotlib.pyplot as plt

def generateDataNormal(n):
 data = []
 mu, sigma = 0.15, 0.15 # mean and standard deviation
 x1 = np.random.normal(mu, sigma, n)
 y1 = np.random.normal(mu, sigma, n)
 data.extend([(np.array([x1[i], y1[i]]), 1) for i in range(n)])
 mu, sigma = -0.15, 0.15 # mean and standard deviation
 x2 = np.random.normal(mu, sigma, n)
 y2 = np.random.normal(mu, sigma, n)
 data.extend([(np.array([x2[i], y2[i]]), -1) for i in range(n)])
 return data

def test_error(w, test_data):
 correct = 0
 for x_i, y_i in test_data:
  y_i_prime = np.dot(w, x_i)
  if y_i * y_i_prime >= 0:
   correct += 1
 e = (len(test_data)-float(correct))/len(test_data)
 return e

def perceptron_weights(training_data, lrate=0.2):
 w = []
 xlen = len(training_data[0][0])
 for i in xrange(xlen):
  w.append(random())
 w = np.array(w)
 for x_i, y_i in training_data:
  y_i_prime = np.dot(w, x_i)
  if y_i * y_i_prime <= 0.0:
   w = w + lrate*y_i*x_i
   yield w.copy()

def perceptron_weight(training_data, lrate=0.2):
 w = []
 xlen = len(training_data[0][0])
 for i in xrange(xlen):
  w.append(random())
 w = np.array(w)
 for x_i, y_i in training_data:
  y_i_prime = np.dot(w, x_i)
  if y_i * y_i_prime <= 0.0:
   w = w + lrate*y_i*x_i
 return w

def plot_data(training_data, ws, lrate):
 for x in training_data:
  if x[-1] == 1:
   plot(x[0][0], x[0][1], 'ob')
  else:
   plot(x[0][0], x[0][1], 'or')
 colors = np.linspace(0.1, 1, len(ws))
 mymap = get_cmap("Greys")
 mycolors = mymap(colors)
 i = 0
 for w in ws:
  n = norm(w)
  ww = w/n
  ww1 = [ww[1], -ww[0]]
  ww2 = [-ww[1], ww[0]]
  plot([ww1[0], ww2[0]],[ww1[1], ww2[1]],color=mycolors[i])
  i += 1
 xlim(-1, 1)
 ylim(-1, 1)
 savefig('perceptron_'+str(lrate)+'.png')
 cla()
 #show()

if __name__ == '__main__':
 training_data = generateDataNormal(100)
 shuffle(training_data)
 for lrate in [0.1, 0.2, 0.4, 0.8]:
  weights = [w for w in perceptron_weights(training_data, lrate)]
  plot_data(training_data, weights, lrate)

Below are three plots of how w changes on each iteration (where it is wrong and w must be changed) for different learning rates, represented by the Greek letter lambda. A note about the color mapping for the lines (which are actually the lines orthogonal to w): there is a line for each time w is updated, and the first line is the lightest, and the last line is the darkest. As you can see, small learning rates like 0.1 result in small changes in w and larger learning rates like 1.0 result in larger change. Caution should be taken when choosing lambda to somewhat guarantee convergence and avoid thrashing or cycling of w. 
The blue circles are one class and the red circles are the other. 

Counting Words using MapReduce

This class counts words in a document.

#! /usr/bin/env python

import re
from mrjob.job import MRJob

class WordCount(MRJob):
 def mapper(self, key, value):
  for word in value.split():
   yield word.lower(), 1
 def reducer(self, key, value):
  yield key, sum(value)

if __name__ == '__main__':
 WordCount.run()

Assuming you have Jane Austin's Sense and Sensibility in a .txt file like I do, call it like so: 

Each output line contains two tab-delimited elements: the word, and the count of that word. 

Oh, dear, that's a lot of 'dear's. As you can see, the mapper function simply defines words as anything between two spaces, or space characters. Additional work can clean that up a bit. The following fix uses regular expressions--regex. The special character '\w' means 'a word character', which means a-z or A-Z or 0-9. The '+' means 'one or more'. Putting these together, '\w+' means one or more word characters, which comprises a word. The 'ws' variable contains all matching words in the 'word' string. So for example, if 'word' is "dear--sure!", then 'ws' is all occurrences of one or more word characters, which for this example is "dear" and "sure."

def mapper(self, key, value):
  for word in value.split():
   ws = re.findall(r'\w+', word)
   for w in ws:
    yield w.lower(), 1

The occurrences of the word 'dear' and its kin have been stripped of the non-word characters, giving better knowledge of the words themselves, but loosing some of the peripheral info contained in the punctuation; that is, 'dear' does not equal 'dear!'

Coin Changing

This code finds all ways of making change for a given amount using the specified denominations. For example, if we had use of an infinite supply of pennies, nickels, dimes, and quarters, then the best way to make change for 33 cents is 1 quarter, 1 nickel, and 3 pennies.

def change(n, coins_available, coins_so_far):
 if sum(coins_so_far) == n:
  yield coins_so_far
 elif sum(coins_so_far) > n:
  pass
 elif coins_available == []:
  pass
 else:
  for c in change(n, coins_available[:], coins_so_far+[coins_available[0]]):
   yield c
  for c in change(n, coins_available[1:], coins_so_far):
   yield c

if __name__ == '__main__':
 n = 33
 coins = [1, 5, 10, 25]

 solutions = [s for s in change(n, coins, [])]
 for s in solutions:
  print s

 print 'optimal solution:', min(solutions, key=len)

Below is the output, showing all ways of making change for 33 cents using only coins worth 1, 5, 10, and 25 cents.

Counting Letter Frequencies with MapReduce

This code shows how to use the mrjob library in python to count the occurrence of letters in a document.

#! /usr/bin/env python

from mrjob.job import MRJob

class LetterCount(MRJob):
 def mapper(self, key, value):
  for word in value.split():
   for letter in list(word):
    yield letter.lower(), 1
 def reducer(self, key, value):
  yield key, sum(value)

if __name__ == '__main__':
 LetterCount.run()

The input and output files can be passed in like so:

We pass dict.txt--just a text file with about 118,000 words, one per line--as the input and we specify lettercounts.txt as the output. The '<' and '>' symbols are called 'redirect' operators for stdin and stdout, respectively. Below is some sample output. Observe that 'e' is the most frequent letter, a fact that makes code breaking slightly easier. 

merging k sorted lists

Function to merge $k$ sorted lists. This algorithm uses a queue data structure. The keys into the queue are the first element (the head) of each sorted list, and the values are the remaining elements of the list (the tail). Using a (min) queue guarantees that the list with the smallest first element will always be used first. The first for loop runs in $O(k*log(k))$ time, since the heads of $k$ lists must be heapified; the while loop runs in $O(k*n*log(k))$ time, where there are $k$ lists, and assuming all $k$ lists have $n$ elements.

import heapq

def merge_k_sorted_lists(lists):
 h = []
 for l in lists:
  head = l[0]
  l.pop(0)
  rest = l
  h.append((head, rest))
 heapq.heapify(h)
 r = []
 while h != []:
  head, rest = heapq.heappop(h)
  r.append(head)
  if rest != []:
   head = rest.pop(0)
   heapq.heappush(h, (head, rest))
 return r

lists = [range(5), range(-5,1), range(5,9)]
print lists
listsmerged = merge_k_sorted_lists(lists)
print listsmerged

merging two sorted lists

Function to merge two sorted lists in linear time. This function is half of the mergesort algorithm.

#! /usr/bin/env python

def merge_sorted_lists(list1, list2):
 r = []
 i, j = 0, 0
 while i < len(list1) and j < len(list2):
  if list1[i] < list2[j]:
   r.append(list1[i])
   i += 1
  else:
   r.append(list2[j])
   j += 1
 if i == len(list1):
  r.extend(list2[j:])
 elif j == len(list2):
  r.extend(list1[i:])
 else:
  print 'something\'s wrong'
 return r

print merge_sorted_lists([1,3,5], [2,4,6])

Sample output:

converting between decimal and hexadecimal

Two functions for converting between decimal and hexadecimal.

def decimal_to_hexadecimal(decimal_num):
 if decimal_num == 0:
  return '0'
 hexvals = map(str, range(10)) + ['A', 'B', 'C', 'D', 'E', 'F']
 h = ''
 while decimal_num > 0:
  mod = decimal_num % 16
  h = hexvals[mod] + h
  decimal_num /= 16
 return h

def hexadecimal_to_decimal(hex_num):
 hexvals = map(str, range(10)) + ['A', 'B', 'C', 'D', 'E', 'F']
 i, d = len(hex_num)-1, 0
 while i >= 0:
  #print i
  d = d + hexvals.index(hex_num[i]) * 16**(len(hex_num)-1-i)
  i -= 1
 return d

def test_hex():
 originals = range(20)
 hexes = [decimal_to_hexadecimal(d) for d in originals]
 decimals = [hexadecimal_to_decimal(b) for b in hexes]
 assert originals == decimals
 print 'originals:', originals
 print 'hexes:', hexes
 print 'decimals:', decimals

if __name__ == '__main__':
 test_hex()

Below is some sample output.