Voila!

http://arxiv.org/abs/1201.6251

and

In the dark ages of programming, functions acted on data. To slice your bread, you passed a bread data structure to a slice function:

slice(bread);

Then came object oriented programming. Instead of having an external function slice our bread, we would ask the bread to slice itself by calling the slice method on a bread object:

bread.slice();

Obviously a vast improvement.
Now object oriented programming has become more refined. First we create a bread-slicing object and then we simply pass bread objects to the slice method on the bread-slicer:

BreadSlicer slicer = new BreadSlicer();
slicer.slice(bread);

via John Cook

update

There is an argument against the final improvement. Travis Griggs advices not to make objects with -er, which probably will act the same way functions act (applying a function over an argument). You can read about it here

Here is the naive implementation in python :

def fib( n ) :
	if n <= 1 :
		return 1
	return fib(n-1) + fib(n-2)

Calculating fibonacci sequence from 1 to 35 takes about 8 seconds (8.056s). So, let's how we can improve this by using decorators.

The Memento decorator will allow us to save time by not calling a function which we've already called.

Here is an implementation of Memento decorator:

class Memento :
	__mem__ = {}
	def __init__(self, f) :
		self.f = f

	def __call__(self, arg) :
		if arg not in self.__mem__ :
			self.__mem__[arg] = self.f(arg)
		return self.__mem__[arg]

Let's see what it does. The __init__ function is pretty obvious. It assigns the function f to an object variable. The __call__ function is triggered every time the decorated function is called. By using a dictionary we check and return the result of a function call with the same argument (if we've already computed that). The cost of querying the dictionary is almost .

By just applying this decorator to our function

@Memento
def fib( n ) :
	if n <= 1 :
		return 1
	return fib(n-1) + fib(n-2)

we manage to compute the first 1000 fibonacci numbers in less than a second.

Here is a gist of this example https://gist.github.com/1988734 .

There are several solutions to this but the following is considered one of the best. Also it’s dead simple. The algorithm is also known as “Tortoise and Hare Algorithm”

def toirtoise_and_hare(l) :
	tortoise = l.head
	hare = l.head
	steps = 0
	while True:
		if hare == None :
			return (steps, 'No loop found')
		hare = hare.next
		if hare == None :
			return (steps, 'No loop found')
		hare = hare.next
		tortoise = tortoise.next
		if hare == tortoise:
			#print hare, tortoise
			return (steps, 'Loop found')
		steps += 1

Below you can find a simple implementation of linked list in python

class Node :
	def __init__(self, data) :
		self.next = None
		self.data = data

	def __str__(self) :
		return str(self.data)

class LinkedList :
	def __init__(self) :
		self.head = None

	def add_node(self, data):
		if self.head == None :
			self.head = Node(data)
		else :
			tmp = Node(data)
			tmp.next = self.head
			self.head = tmp

	def add_loop(self, f, t) :
		node = self.head
		i = 0
		node_f = None
		node_t = None
		while node != None :
			i += 1
			if i == f :
				node_f = node
			if i == t :
				node_t = node
			node = node.next
		node_f.next = node_t

	def print_list(self):
		node = self.head
		while node != None :
			print node.data
			node = node.next

… and test …

l = LinkedList()
for i in xrange(1000) :
	l.add_node(i)

l.add_loop(800, 200)

print toirtoise_and_hare(l)

As mentioned the complexity of the algorithm is .

Here is the complete gist.

Review of “Collaborative Filtering For Implicit Feedback Datasets”

Collaborative Filtering is a method for providing recommendations based on preferences fetched from users about items (products, shows, tracks, etc. ). Recommender systems utilise such techniques for personalised suggestions using past history of users. For example, Amazon use a type of Collaborative Filtering, called item-based collaborative filtering. According this method, relationships between pair of items are being extracted and combined with user’s data (purchase history) so as to infer recommendations.

As we saw in the previous example, users provide feedback to Amazon about items by rating and buying. This (explicit) feedback is characterised by the fact that the users explicitly define what they like (by buying it or rating positively) and what they don’t (by giving low ratings). However, there are cases that this kind of feedback is not available. For example, when a user is listening to a track or an album, without rating it, it is difficult to know if he liked it or not. This kind of feedback is known as implicit feedback and its main characteristic is that it describes users’ behaviours. As the authors argue, there are several implications that arise from the lack of explicit feedback.

What is of interest is what the user didn’t like. This information is difficult to be extracted for the reason that a user (listener) doesn’t provide negative feedback (such as low ratings) of tracks that he didn’t like. What is more, it is dangerous to assume that he didn’t like the songs the he hasn’t listened to since there is a positive probability that he hadn’t even been aware of them. Also, implicit feedback might contain a lot of nois . For example, it is very common for a family’s members to share a computer thus by tracking listening behaviours from this specific computer might not match to a specific member of the family.

In this paper, the authors describe a latent factor model method based on matrix factorisation which deals with this problem. Providing recommendations to users using implicit feedback data.

The method

For users and items, users histories are stored in matrix such as :

For example, might represent the times a user listened to track multiplied each time by the percentage of the track listened.

What is of great importance is that in contrast to explicit feedback where indicates likeness or dislikeness, in implicit feedback it indicates confidence. For example, a low value of doesn’t reveal dislikeness of item by user but low confidence about the preference of user for this item .

For the needs of the method the binarization (preferences) of is computed as follows:

What is more values are mapped to confidence values . For this the authors chose to use the following linear relation:

The main method tries to factorize in two factors (user factors) and (item factors) such that . Please note that is a parameter of the system which represents the number of hidden factors and the authors experimented with values from to . For the estimation of the factors the authors used Tikhonov regularisation to minimise the cost function :

The greatest characteristic of this optimisation problem is that 1) it incorporates confidence levels thus it takes into consideration how sufficient is the behaviour observation and 2) it can be solved by an algorithm called Alternative-Least-Squares with Weighted--Regularization (ALS-WR) whose sub steps can be parallelized. According this method, by fixing and alternately the cost function is minimised using simple quadratic minimisation methods. The following algorithm is used to compute the factors :

Algorithm

is a diagonal matrix where . Also contains all values of . Please note that matrix is very sparse and only are non-zero.
Complexity of step 2 is and for step 3 , where . As we already mentioned, steps 2 and 3 are parallelizable and frameworks such as map reduce (Hadoop) can be used ( in fact, a variation of this model for explicit feedback has been implemented on Mahout 0.5 ). This is of great importance since it makes it suitable for huge number of users and items. So as to recommend items for user , a list of the items which maximise is returned.

An important and desired feature of recommendation algorithms is explanations. The current method gives explanations of recommendations by using a clever trick which transform the preferences prediction to linear function of past behaviours, weighted by item-to-item similarity. This item-to-item similarity is specified by the user and denoted by .

For the evaluation of the method they used the average number of predicted positions of items weighted by the observations ( denoted ). Lower values of means more desired predictions but not more accurate predictions. Thus, this is not to be confused with accuracy.

US Social Security Administration office http://www.ssa.gov/ created a service where you can request the number of births of a babies per name per gender since 1880. However, their pages are not easily accessible. After searching a while I found this page http://www.infochimps.com/datasets/popular-baby-names-by-year-top-1000-us-social-security-administr where is given a method of how to scrape SAS name list with a bash script.

!#/bin/sh
url=http://www.ssa.gov/cgi-bin/popularnames.cgi
mkdir -p names
for ((yr=1879 ; $yr <= 2010 ; yr++)) ; do
	echo $yr
	curl -d "year=$yr&top=1000&number=n" $url > names/$yr.html
done

Alternatively you can just download the data from infochimp’s website.

However this is raw information and thus not very helpful. What we need is to have them in a data structure which will enable us to query the gender per name (ideally a distribution).

I used BeautifulSoup to parse the page and extract records.

import glob
from BeautifulSoup import BeautifulSoup

files = glob.glob('names/*.html')

for f in files :
	html_data = open( f ,'r').read()

	soup = BeautifulSoup(html_data)
	year = soup.find(id="yob")['value']
	tables = soup.findAll('table')
	trs = tables[2].findAll('tr')
	for tr in trs[1:-1]:
		tds = tr.findAll('td')
		print "%s,%s,%s,%s" % (
                       tds[1].contents[0],
                       tds[0].contents[0].replace(',',''),
                       'male',
                       year)
		print "%s,%s,%s,%s" % (
                       tds[3].contents[0],
                       tds[2].contents[0].replace(',',''),
                       'female',
                       year)

I stored the output to names.csv .

Then, to transform this information to a probability distribution per name I used the following code.

import json 

def prob( m, f ) :
    s = m + f
    return {'male':m/(1.0*s), 'female':f/(1.0*s)}

def load_data( file ) :
    names = {}
    f = open( file, 'r' )
    for l in f :
        d = l.rstrip().split(',')

        name = d[0]
        counter = d[1]
        gender = d[2]
        year = d[3]

        if name not in names :
            names[name] = { 'male':0, 'female':0 }

        if gender == 'male' :
            names[name]['male'] += int(counter)
        else :
            names[name]['female'] += int(counter)

    return names

db = load_data('names.csv')

names = {}
for d in db:
    p = prob( db[d]['male'], db[d]['female'])
    if p['male'] > p['female'] :
        gender = 'male'
    elif p['female'] > p['male'] :
        gender = 'female'
    else:
        gender = 'both'

    names[d] = gender

print json.dumps( names )

I saved this to names.json.

Finally, to query the gender of a name you just compare the probabilities

f = open('names.json','r')
names = json.loads( f.read() );
print names
def check_name( name ):
	if name in names :
                if names[name]['male']>names[name]['female']:
                         return 'male';
                elif names[name]['male']>names[name]['female']:
                         return 'female';
                else :
                         return 'unknown';
	else :
		return 'unknown'

The probability approach gives the flexibility to compute also a confidence of the gender for a given name [TODO].

Then, the software part was to programm the robot to perform a taks, known as global localization. In simple words, imagine that you are given a map but you have no idea about the position of the robot in the map. Then, by using a ultrasound sensor you have to find the position and the using this information to drive the robot to a target. As you see, an error in the estimation can be disastrous.

The method we used for the localization part is know as Monte Carlo Localization. This method (uniformly) samples a number of hypotheses (particles) and then by comparing the measurements with the hypothetical measurements we re-sample hypotheses by weightening them so as the more consistent a measurement is, the more probabilities are that a hypothesis will be re-chosen.

After a serveral iterations of the MCL, an estimation of the position is found. Then, using this estimation, with the hope that it is also the correct position, we guide the robot to the target. So, how do we chose how to get from a position to another ? A simple and safe solution to that was to compute the Delauney triangulation of the map and then compute the dual graph of it, . Then we find the closest node of the dual graph to the robot and to the target. So, we have a starting position, a node (A) of that is close to the starting point, a node (B) of that is close to the target and a path from A to B on . Voila, this is the path that we have to follow so as to be as safe as possible that we won’t hit on a wall.

Well, here it is on action.

That was fun

Sol Robeson: Have you met Archimedes? The one with the black spots, you see? You remember Archimedes of Syracuse, eh? The king asks Archimedes to determine if a present he’s received is actually solid gold. Unsolved problem at the time. It tortures the great Greek mathematician for weeks – insomnia haunts him and he twists and turns in his bed for nights on end. Finally, his equally exhausted wife – she’s forced to share a bed with this genius – convinces him to take a bath to relax. While he’s entering the tub, Archimedes notices the bath water rise. Displacement, a way to determine volume, and that’s a way to determine density – weight over volume. And thus, Archimedes solves the problem. He screams “Eureka” and he is so overwhelmed he runs dripping naked through the streets to the king’s palace to report his discovery

Sol Robeson: Now, what is the moral of the story?

Maximillian Cohen: That a breakthrough will come.

Sol Robeson: Wrong! The point of the story is the wife. You listen to your wife, she will give you perspective, meaning. You need a break, you have to take a bath or you will get nowhere.

From Aronovsky’s Pi. I’ve forgotten how much I enjoyed that movie.

As the title suggests, my project is to research and develop a system which will make use of machine learning and music information retrieval so as to understand and then generate music automatically, simulating an improvising musician. In short, a system which will improvise in a jam session.

There are several ideas to begin with. The first milestone is to construct a system which will use simple midi input and fixed tempo, like the system suggested in [1]. However, the goal is to be able to use real instruments and beat to be extracted by rhythm instruments (take a look at [2] and [3] for real-time feature extraction).

Here is a list of the tools and languages i am planning to use:

• ChucK and weakinator.
• Pure Data and/or Max/MSP for interaction, programming, generation (using it with max for live).
• WEKA for machine learning.
• Ableton for audio synthesis (generative part)

Feel free to leave a comment, to make a suggestion or just tell me what you think.

References

1. Kitahara, Tetsuro, Naoyuki Totani, R. Tokuami, and H. Katayose. 2010. €œBayesianBand: Jam Session System Based on Mutual Prediction by User and System.€ Entertainment Computing €“ICEC 2009

2. Stark, A.M., and M.D. Plumbley. 2009. “Real-time chord recognition for live performance.”in Proceedings of International Computer Music Conference.

3. Stark, Adam M, Matthew E P Davies, and Mark D Plumbley. 2009. “REAL-TIME BEAT-SYNCHRONOUS ANALYSIS OF MUSICAL AUDIO Centre for Digital Music Queen Mary University of London London , United Kingdom.” Analysis 1-6.

In this example we are going to use the following images.

test image

It’s easy to observe the followings. First of all, a fixed size (monospace) font has been used. This makes extracting all the letters and using them as masks to check each digit, one by one, very easy. Also, the alphabet is simple lowercase hexadecimal letters. Thus, we had to extract only 16 letters.

The first part was to to extract all the letters. To achieve that, first of all we sampled several images so as to be sure that the images we have contains all the 16 letters. Then, using a simple image editor we cropped all the letters, one by one. We had to be careful so all the letters be aligned properly. Here is the final mask.

mask

As you can notice there is some noise which we have to remove. After playing with several techniques we finally ended to the following. We turned the image to greyscale. Then we used a threshold to remove some of the noise. Here is the example after the filtering (cropping also applied).

after filtering

So, now we have the image almost cleared and some letters to play with.

Procedure

Move each letter across the image and take the difference of the pixels for each position and sum them. Thus for each position we have a score of how much the letter (mask) fits the letter behind it. Then, store for each letter the position where the maximum score found. Then sort by score, take the top five results (our captcha is five letters) and finally sort by position. The result is the CAPTCHA text.

More formally

Let

be the distance of the image , with the letter in position

Then

Thus, we need 5 letters with maximum  ordered by .

def p(img, letter):
		A = img.load()
		B = letter.load()
		mx = 1000000
		max_x = 0
		x = 0
		for x in xrange(img.size[0]-letter.size[0]):
			sum = 0
			for i in xrange(letter.size[0]):
			    for j in xrange(letter.size[1]):
					sum = sum + abs(A[x+i, j][0] - B[i, j][0])
			if sum < mx :
				mx = sum
				max_x = x
		return (mx, max_x)

Here is the code which implements this method. You can browse and download everything from https://github.com/ptigas/simple-CAPTCHA-solver

from PIL import Image

def ocr(im, threshold = 200, aplhabet = "0123456789abcdef"):
	img = Image.open(im)
	img = img.convert("RGB")
	box = (8, 8, 58, 18)
	img = img.crop(box)
	pixdata = img.load()

	letters = Image.open('letters.bmp')
	ledata = letters.load()

	# Clean the background noise, if color != black, then set to white.
	for y in xrange(img.size[1]):
	    for x in xrange(img.size[0]):
			if not(pixdata[x, y][0] > threshold \
			and pixdata[x, y][1] > threshold \
			and pixdata[x, y][2] > threshold):
				pixdata[x, y] = (0, 0, 0, 255)
			else:
				pixdata[x, y] = (255, 255, 255, 255)

	counter = 0;
	old_x = -1;

	letterlist = []

	for x in xrange(letters.size[0]):
		black = True
		for y in xrange(letters.size[1]):
			if ledata[x, y][0] <> 0 :
				black = False
				break
		if black :
			if True :
				box = (old_x+1, 0, x, 10)
				letter = letters.crop(box)
				t = p(img, letter);
				print counter, x, t
				letterlist.append((t[0],aplhabet[counter], t[1]))
			old_x = x
			counter = counter + 1

	box = (old_x+1, 0, 140, 10)
	letter = letters.crop(box)
	t = p(img, letter)
	letterlist.append((t[0],aplhabet[counter], t[1]))

	t = sorted(letterlist)
	t = t[0:5] # 5-letter captcha

	final = sorted(t, key=lambda x: x[2])
	answer = ""
	for l in final:
		answer = answer + l[1]
	return answer

print ocr('test.jpg')

[update]

Today I found this. Very nice tutorial for CAPTCHA solving using python and vector space searching.