Bjørn Arild Mæland's Blog

The Rule of 78

2009-09-03T00:00:00+02:00

In 1986, McClelland and Rumelhart published their seminal paper on the learning of past tenses of English verbs. It played a large part in the renewal of academic interest in neuron-like computing and machine learning. I'm taking a class on modelling for computational linguistics this term and we've been using JavaNNS to play around with some neural networks. McClelland and Rumelhart provides a scaled-down example of their experiment, so we used that as a practice exercise. They call their example the rule of 78. It can be described as a basic rewriting rule, e.g. (2 4 7) -> (2 4 8), (1 6 8) -> (1 6 7), etc. The point is that the rules are regular in the sense that it is only the last digit that gets changed in the output (7 turns into 8 and vice versa). This is just like regular verbs – the base form remains intact and there is a systematic change to the suffix. However, they also introduce an exception to the rule: (1 4 7) -> (1 4 7). This can be seen as an irregular verb, e.g. hit -> hit.

In order to get this data set into JavaNNS, we need to encode it somehow, into sequences of binary numbers. McClelland and Rumelhart use a simple feed-forward network with 8 inputs and 8 outputs, so we'll basically do the same thing. They don't mention how they encoded the patterns into binary sequences, but its quite easy to figure out how it can be done. I'll spoil it in the table below:


Pattern	1	2	4	7	8
(1 4 7)	1	0	1	1	0
(2 4 7)	0	1	1	1	0
(2 4 8)	0	1	1	0	1

Et cetera. I wrote a small Ruby script for creating pattern files with these data for JavaNNS, which is available here. It's very raw but it should be understandable. It produces .pat files which can be opened directly in JavaNNS and then used for training the network. I won't go into the details of McClelland and Rumelhart's training scheme, however I'd highly recommend reading the article for the rest of the story. We more or less replicated their results, using Backpropagation as the learning function in JavaNNS.

Frequencies of word frequencies

2009-08-25T00:00:00+02:00

During Christopher D. Manning's CS224N lectures on Natural Language Processing, he intially presents some interesting tables of the frequencies of word frequencies you can expect to see in a regular corpus. The corpus he uses as an example is Tom Sawyer, freely available from Project Gutenberg. The topic is data sparseness and N-gram language models (lecture 2). These sorts of things are really simple to plot out with NLTK; here I am just going to quickly go through the steps required to get a nice plot of the data.

First, we need to get a list of all the words in our corpus:

## Assuming that nltk is available, and that the text is in the current
## directory, named 'twain-tomsawyer.txt'
import nltk
reader = nltk.corpus.reader.PlaintextCorpusReader('.', 'twain-tomsawyer.txt')
words = reader.words('twain-tomsawyer.txt') # List of all the words in the text

Note that the NLTK corpus reader class does a lot of work behind the scenes, including tokenization. To create a word frequency distribution of the words we just collected, we can use the FreqDist class:

fdist = nltk.FreqDist([w.lower() for w in words])

The values of this frequency distribution now consists of an integer for each word in the corpus, telling us how often they occured (i.e. the word frequencies). We'd like to group these frequencies under 13 different labels (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11-51, 51-100, >100):

def group(i):
    if i < 11: return str(i)
    elif i in range(11, 51): return("11-50")
    elif i in range(51, 101): return("51-100")
    else: return(">100")

Now we can create another frequency distribution of the previously obtained values:

fdist_freq = nltk.FreqDist([group(freq) for freq in fdist.values()])

Here we basically count how often each of the 13 different "groups" occur, resulting in the frequencies we were after. To plot out the data graphically we can now use fdist_freq.plot(), or as a plain text table with fdist_freq.tabulate().

In summary, I hope this small article shows how easy it is to do corpus experiments with NLTK. The best part is that the toolkit provides an uniform corpus API for dealing with different kinds of corpora (tagged, annotated, coded, etc). The NLTK data collection also includes a lot of corpora to play around with right out of the box.

The complete code is available here.

Using Metal with live-validations

2009-08-04T13:51:00+02:00

The popular live-validations plugin for Rails works by providing a controller that is polled asynchronously by Ajax-requests. I decided that re-implementing this controller as a piece of Metal (a way to write super fast pieces of optimized logic that routes around Action Controller in Rails 2.3+) would be a nice learning-opportunity. I started out by watching Gregg Pollack's screencast on Rack, Metal, and Rails Middleware – highly recommendable if you want to learn more about any of the mentioned technologies. After watching I was able to whip up some code:

# Allow the metal piece to run in isolation
require(File.dirname(__FILE__) + "/../../config/environment") unless defined?(Rails)

# Drop-in replacement for the LiveValidations controller that ships with
# live-validations.
class ValidationPoller

  def self.call(env)
    if env["PATH_INFO"] =~ /^\/live_validations\/uniqueness/
      params = HashWithIndifferentAccess.new(Rack::Request.new(env).params)
      responder = LiveValidations.current_adapter.validation_responses[:uniqueness]

      [200, {"Content-Type" => "text/html"}, [responder.respond(params).to_s]]
    else
      [404, {"Content-Type" => "text/html"}, ["Not Found"]]
    end
  end

end

As described in the comments, this really is a drop-in solution (just store the file in the app/metal folder). The controller that ships with live-validations will never be reached (or any other part of Rails – this all happens before the Rails routing process is triggered). We use this in production for crantastic (my GSoC 2009 project) without any problems. If you have a really big site this will probably give you a small improvement in performance – I haven't done any benchmarking though.

Validating your markup with RSpec and markup_validity

2009-06-13T17:32:00+02:00

markup_validity was announced earlier today by Aaron Patterson on the comp.lang.ruby mailing list (read the full announcement here). Perfect timing, as this was something I have wanted to add to my test suites for some time now. Here are my installation notes:

sudo gem install markup_validity
echo 'config.gem "markup_validity"' >> $RAILS_ROOT/config/environments/test.rb
# Thats it!

I then added a basic spec for one of my controllers:

describe PackagesController do

  integrate_views

  it "should have an XHTML Strict compilant show page" do
    get :show, :id => 1
    response.body.should be_xhtml_strict
  end

end

However, I ran into an internal error when running the spec:

"Internal error: xmlSchemaVDocWalk, there is at least one entity reference in the node-tree currently being validated. Processing of entities with this XML Schema processor is not supported (yet). Please substitute entities before validation.."

My pages make use of HTML entities, and seemingly those aren't supported for validation yet. Thus, I added the following method to my core_extensions.rb file:

class String
  def strip_entities
    self.gsub(/&#?[A-Za-z0-9]+;/, '')
  end
end

And changed the XHTML strict assertion in my spec to read like this: response.body.strip_entities.should be_xhtml_strict. If you end up using strip_entities a lot, I guess it could make sense to monkey patch.

All in all, this seems to be a nice gem for making sure your generated XHTML is valid.

UPDATE: This has been fixed by Aaron in HEAD, so the substitution tricky won't be necessary anymore after the new version is released.

Demonstrating how Heroku handles your database

2009-05-11T13:15:00+02:00

Heroku is an amazing platform for hosting Rack-compilant web applications. Although some people complain about steep pricing, I'm sure that many will feel that the productivity gain is worth it. I'll provide more detail about Heroku and how I/we use it later. This post will simply show how database configuration is done when you work with Heroku. I think this might be a bit vague in the documentation, some people get confused over it. Lets utilize the console:

zero:~/Projects/crantastic $ heroku console
Ruby console for crantastic.heroku.com
>> puts File.read(Rails.configuration.database_configuration_file)
---
production:
  encoding: unicode
  adapter: postgresql
  username: something_random
  port: 5432
  host: somewhere.at.heroku
  database: something_random
  password: something_random

=> nil
>>

Heroku in practice replaces your apps database.yml when you push your site to their servers. Your data will be stored in one of their fancy PostgreSQL servers no matter what you use locally - this means that you don't have to think about database.yml at all (except for development purpses, naturally). Taps makes sure that everything's db agnostic. If you want to push your latest development db to Heroku, simply run heroku db:push. Awesome!

Oystercatcher Spotting 2.0

2009-05-09T11:59:00+02:00

Since 2005, the University of Bergen has made a webcam of roof-breeding oystercatchers (tjeld, in Norwegian) available for everyone to enjoy. And for some reason, the site is quite popular among students and others during the breeding period in May. To make this activity a bit more practical, at least for me, I decided to turn to why's Shoes, the nicest/smallest GUI library known to man. Thus I created a small GUI app that fetches the latest images from the webcam and display them at 240x180 instead of the original 800x600. Together with "always on top", this turned out to work quite well. What can possibly be better than watching birds while working?

If you want to attempt to install this thingy, install Shoes from http://shoooes.net/, then download http://chrononaut.net/tjeld-app.shy. Run Shoes, click "Open an App" and select the .shy file you just downloaded. It has been reported to be rather dodgy in Windows (d'oh), it works fine in Linux and OS X though. The source is made available here. It weights in at about 20 lines of code (discarding the comments etc). Not bad for a fully functional webcam frontend.

Using Compass with Jekyll

2009-05-08T00:00:00+02:00

Compass is a great stylesheet framework that has received a lot of well-deserved attention recently. It got an additional boost in popularity after being highlighted as featured project in GitHub Rebase #20. In this small post I'll describe how you could use it together with Jekyll. It's not exactly rocket science, but following these steps might save you some time.

sudo gem install chriseppstein-compass
cd your/jekyll/root
compass -f blueprint --sass-dir _sass .

This will create a _sass directory for sass sources, a config.rb file for compass and a grid.png image file. As you might know, prefixing the sass directory with an underscore causes Jekyll to skip over it when it compiles the site. I'm accepting stylesheets as the default directory for compiled css files, however. The next step is optional but recommended. Open _config.yml and add (or modify) an exclude section:

exclude:
  - config.rb

This is a new feature in Jekyll 0.5.1 which can be used to exclude arbitrary files from being copied during compilation (note that GitHub Pages still use Jekyll 0.5.0). Now you're all set for using Sass with the CSS framework of your choice for styling your site! Just run compass --watch together with jekyll --server --auto while developing. If you're interested, the entire source code for this blog (using Compass, of course) is available on GitHub.

If you don't already use Compass and would like to learn more, there's an hour long walk through available on Vimeo.

ZSH Tip of the Day: #2

2009-04-07T00:00:00+02:00

How many times have you forgotten to use sudo when executing commands? Countless, I'm sure. One trick is to simply write sudo !!, since !! is replaced with the full contents of the previously entered command. Sure beats re-entering the entire thing. But we can do better - three key strokes should be enough. Here's how I do it:

# Prefix the previous line with "sudo " then execute it
rerun-with-sudo () {
  LBUFFER="sudo !!"
  zle accept-line
}
zle -N rerun-with-sudo

bindkey '\C-x\C-x' rerun-with-sudo

I think this small function showcases how nice zle is. LBUFFER is basically a variable which contains the contents of the prompt. Since this function assigns to LBUFFER, it overwrites anything already there (if anything) with sudo !!. zle accept-line is equivalent to hitting enter. Finally I bind the function to ^x^x - which now can be used to quickly rerun commands with sudo.

Experimenting with automatons in Ruby (part 2)

2009-03-21T00:00:00+01:00

Better late than never, I finally published the code I produced for my small automaton library at http://github.com/Chrononaut/rton/tree/master. It was created as part of a introductionary course in computational linguistics. I'm quite pleased with how the DSL turned out. Consider the following example, a pushdown automaton for the aⁿ bⁿ language:

@anbn = Automaton.setup(:pda) do
  initial_state :q0 do
    transition ['a', EMPTY], [:q0, 'A']
    transition ['b', 'A'],   [:q1, EMPTY]
  end

  state :q1 do
    transition ['b', 'A'],   [:q1, EMPTY]
  end

  final_states :q0, :q1
end

From the initial state, if an 'a' is read, 'A' is pushed onto the stack. This is called the automatons 'pushing state'. Once a 'b' is read, it transists to state q1, where it starts popping off the 'A' characters from the stack. Basically, if the end of the input string is reached and the stack is empty at that point, the string is accepted. Therefore this automaton accepts input strings like a b, a a b b, etc.

Unfortunately, I doubt that I will actually turn this into something generally usable, mainly because I now spend more time on languages like Python and Clojure for NLP tasks. However, I can recommend JFLAP for a more visual automaton experience.

ZSH Tip of the Day: #1

2009-03-12T00:00:00+01:00

As you can see in my zsh repository on GitHub, I spend a lot of time playing around with my zsh configuration. I'm going to present some of my favourite tricks here on this blog. Today I'll show a very useful function that handles extraction of files. It serves two purposes: it both abstracts away the specific extraction command and deletes the archive file (if successfully extracted). I call it ed:

# Extract & Delete
ed() {
  case ${1##*.} in
    tar)
      tar -xvf $1
      ;;
    tgz|gz)
      tar -zxvf $1
      ;;
    tbz|tbz2|bz2)
      tar -jxvf $1
      ;;
    zip)
      unzip $1
      ;;
    rar)
      unrar x $1
      ;;
  esac || return 1
  rm $1
}

This allows you to do stuff like ed latest.tar.gz, and it would have the same effect as tar -zxvf latest.tar.gz; rm latest.tar.gz. As you can see, it determines which extraction command to use based on the file extension. I find that I almost always want to delete archive files after I have extracted them, hence the deletion. Hope you'll find it useful as well!

NOTE: In order to make Jekyll handle the # in the title of this post, I had to create a small patch.

Introducing Happyblogger

2009-03-11T00:00:00+01:00

I finally ditched my old Blogger account and hacked together a neat blogging solution I would like to call happyblogger. Its basically just some glue that lets me write posts in Emacs' fabolous org-mode and via some processing lets mojombo's slick Jekyll package take care of the rest. I'm very pleased with the result, at least for the time being. :) This is of course mostly for personal use, but I've wrapped it up into a package that should be easy to install/use for others as well.

I actually thought that I had to modify Jekyll quite heavily to get it to work with orgmode instead of the default Textile/Markdown, but luckily it was enough to just postprocess the HTML that orgmode produces and feed it right into Jekyll. The processing is done with Hpricot. I did create some patches for Jekyll though while I was looking through its codebase (now accepted into the mainline). Happyblogger depends on these patches - this means that you currently have to install Jekyll from git in order to use it.

The code, along with some documentation, is available at happyblogger's GitHub repository.

If you actually decide to give it a shot it would be interesting to hear your comments, but since I haven't added a commenting solution yet you'd have to ship me an email. :)

Working with strings in Prolog

2008-11-30T00:00:00+01:00

Strings in Prolog can be quite confusing if you come from another language. In this short article I will illustrate how they work, mainly by showing different examples and by creating a term that checks if a string is contained within another string.

First off, strings in Prolog are written in single quotes. Terms written in double quotes are immediately converted to a list of character codes. Therefore, strings can be handed directly to write. Strings are also atoms.

?- 'bergen' = L.
L = bergen.

?- "bergen" = L.
L = [98, 101, 114, 103, 101, 110].

?- atom('bergen').
true.

?- is_list("bergen").
true.

?- write('sdf').
sdf
true.

?- write("sdf").
[115, 100, 102]
true.

?- writef("%s", ["sdf"]).
sdf
true.

Since strings in Prolog are atoms, they naturally cannot be manipulated. So for certain tasks they need to be converted to char lists. This can be done with name. So to print the first character of a string you'll have to convert it to a char list first.

?- name('bergen', CharList), nth0(0, CharList, FirstChar), put(FirstChar).
b
CharList = [98, 101, 114, 103, 101, 110],
FirstChar = 98.

We now know enough to create our term, contains/2. For illustration, we will make it work for both strings and char lists, by converting to a char list when needed. It will succeed if A is contained within B. We'll need a utility term for this as well. Note that I am using SWI-Prolog, so I am utilizing built in terms that might not be available elsewhere. of this article, but they should be decipherable if you have written recursive terms in Prolog. The full program as well as an example that generates all possible substrings contained within A follows below.

sublist(S, L) :-
  append(_, L2, L),
  append(S, _, L2).

contains(A, B) :-
  atom(A),
  atom(B),
  name(A, AA),
  name(B, BB),
  contains(AA, BB).

contains(A, B) :-
  atom(A),
  name(A, AA),
  contains(AA, B).

%% The empty list is removed mainly for nicer output in the following example.
contains(A, B) :-
  sublist(B, A),
  B \= [].

?- forall( contains('bergen', X) , writef("%s\n", [X]) ).
b
be
ber
berg
berge
bergen
e
er
erg
erge
ergen
r
rg
rge
rgen
g
ge
gen
e
en
n
true.

Experimenting with automatons in Ruby (part 1)

2008-10-26T00:00:00+02:00

A finite automaton is an abstract computing device, which more often than not is used to recognize formal languages. One can look at an automaton as a tape reader which consists of a initial state, a set of final states and a set of transitions between states. The automaton accepts its input if it has reached the end of the input tape and is in a final state.

For the purpose of language processing we will implement different kinds of automatons in Ruby, starting with the simplest one we can conceive. We'll start out with a deterministic finite-state automaton (DFSA). Such an automaton is called deterministic, since it in any given state only has one possible transition for a given input symbol.

First we need an example language to work with, so I've created the "Ruby-language". It can be described with the following regular expression: @/Ru+by/@ (yes, DFSA's correspond to the languages that can be described by (pure) regular expressions). I admit this is a quite boring language, but we have to start somewhere, right? The alphabet for this language is the set {R,u,b,y}.

To create an automaton for this language we need four states (visualize this as a directed graph):

q0: 'R' -> q1
q1: 'u' -> q2
q2: 'u' -> q2, 'b' -> q3
q3: 'y' -> q4

The initial state is q0 and the set of final states is {q4}. As you can see there is a cycle at q2 to allow for an (theoretically) infinite amount of 'u' characters. Also note that there is no ambiguity of which state is the next one at any given point for any given input. Hence, the automaton is deterministic.

On to the implementation considerations. One of the most important design decisions is how we should represent the state transitions. For a DFSA almost anything would work, but we want to choose something flexible. Let's try with a nested hash:

{
 :q0 => {"R" => :q1},
 :q1 => {"u" => :q2},
 :q2 => {"u" => :q2, "b" => :q3},
 :q3 => {"y" => :q4}
}

I think this will work quite well. If we look up a given state in the hash, we will get another hash of all the possible transitions. Matching this up with a input tape should be quite easy. I've sketched up a spec for how this should work in practice:

describe "the Ruby-language" do
  before(:each) do
    @r = DFSA.new({
                    :q0 => {"R" => :q1},
                    :q1 => {"u" => :q2},
                    :q2 => {"u" => :q2, "b" => :q3},
                    :q3 => {"y" => :q4}
                  }, :q0, [:q4])
  end

  it "should recognize valid sentences" do
    @r.should recognize %w(R u b y)
    @r.should recognize %w(R u u u u b y)
  end

  it "should reject invalid sentences" do
    @r.should_not recognize %w(r u b y)
    @r.should_not recognize %w(R u b)
  end
end

Note that we give the input to the automaton as a list (I've picked the %w() syntax since it feels kinda Lispy). This is called tokenization, and for now we'll do it by hand. The second argument to the DFSA constructor is the symbol for the initial state, and the third one is the set of final states. We won't worry about the actual implementation yet, as we want to let this sink in for a bit.

The next article in this series will be to create a DSL for setting up the automaton, then I'll write up on non-deterministic automatons and pushdown automatons. I'll also show more actual code (I'll create a GitHub repos for the automaton library). Possibly I'll get to transducers as well. If you have any suggestions, please leave a comment or ship me an e-mail.

Use your .gitignore as the ignore pattern for echoe

2008-08-09T00:00:00+02:00

Use your .gitignore as the ignore pattern for echoe

Echoe is a library for quickly creating gems in Ruby. I I've hacked up a quick patch for it so you can use your .gitignore file as the manifest ignore pattern. I found it boring to re-list the ignore stuff since it in 99% of the cases (at least for me) already is present in .gitignore.

I'm sure that the patch doesn't work perfectly though. I know there is differences between the globbing syntax in gitignore and in Ruby's File#fnmatch - the latter is stricter. But it still works perfectly for the (small) projects I've tried it on.

Usage goes down like this:

Echoe.new(PROJECT) do |p|
  # ...
  p.ignore_pattern = FileList[".gitignore"]
  # ...
end

Grab it from my fork on GitHub.

UPDATE: This feature is now included in echoe 3.0.2!

The lack of Database Abstraction in PHP

2008-07-21T00:00:00+02:00

Unfortunately, almost none of the most popular PHP software supports other databases than MySQL (with MediaWiki being a notable exception - it supports Postgres). When you're used to programming in Ruby, multi-db compatibility is something you just take for granted after a while because of the excellent ActiveRecord and DataMapper projects. In PHP however, this is a real deal breaker. I don't know if its a cultural problem or a library problem. I did look at Propel some time ago, but honestly the Java-esque XML configuration and over-complex API turned me off real quick. If someone could come up with something better, maybe even WordPress will support SQLite and PostgreSQL one day…

Arch Linux: First impressions

2008-06-02T00:00:00+02:00

So, I finally got fed up with Ubuntu. I really wanted to use FreeBSD again - but unfortunately the hardware in this box is not compatible. Arch Linux looked like a decent alternative so I downloaded the 2007.08-2 image and started installing. Misfortune struck again as I had to spend a couple of hours trying to get wireless working, but everything worked well as soon as I switched to the 2008.04-RC image. I wonder why they don't link to the RC image on the "Get Arch" page.

After some configuration I ended up with a really slick system - It's amazing how much faster stuff runs on OpenBox! Also, the BSD inspired rc.conf and init system made my day. The only real problem I encountered was when I tried to install an older version of a library. Pacman (Arch's package manager) doesn't support this. I consider this to be a flaw in the package manager (which all over feels immature compared to apt or BSD ports), and I predict the devs will realize this sooner or later - even though they currently consider it to be a "feature".

I find it amusing how things tend to move in cycles. When I started out with Linux ~8 years ago Slackware was the coolest thing around. Then we somehow ended up with Ubuntu. And now the "KISS"-distros are turning into the hippest kids on the block again. If you're fed up with the bloat, give Arch a try. :)

Public domain?

2007-12-06T00:00:00+01:00

I'm currently reading "Fundamentals of database systems" by Elmasri & Navathe as part of the curriculum in a database course at my University. The book overall isn't all that bad, but their take on open source databases is really horrid. Quote:

"Personal computers and database system-like software products such as Excel, Visual FoxPro, Access (Microsoft), or SQL Anywhere (Sybase), and public domain products such as MySQL and PostgreSQL are being heavily utilized by users who previously belonged to the category of casual and occasional database users."

Wow. Public domain? I think they should at least invest two minutes to read up about open source software and open source licences, before they wrote about it. Excel and PostgreSQL in the same sentence? That's pretty fucked up if you ask me. And they have this highly patronizing tone which goes something like "commercial dbms > *, lol!". Someone should ship the authors a copy of PostgreSQL, I'm sure they would've been amazed if they tried it.

Leopard: First impressions

2007-10-27T00:00:00+02:00

Alright, so Leopard has arrived! On Friday I wiped the harddrive of my MacBook and eagerly installed my new OS. In this post I will present some of my thoughts about it, based a couple of days usage.

The good:

It's very convenient that so much quality software ships with the OS. Built-in svn is nice even tho I prefer Git, since a lot of projects use it. I really wanted the Ruby support to be good. But it turned out that I pretty quickly had to change it with a custom install via MacPorts. The built in Ruby simply refused to install the ruby-postgres gem. I gave the exact same params to extconf.rb with the custom Ruby in place, and it just worked. I had to install PostgreSQL 8.2 from source by the way, since the port for it is broken at the moment. Its still very nice that the OS ships with a up to date Ruby tho.
Spaces are cool, even tho I don't like everything about their behavior. I really want to disable the animated gliding that occurs when you change between spaces.
The new finder feels much better to use.
Safari have gotten a bunch of updates as well, I especially like the new search function.
Its faster than Tiger.

The bad:

Transparency which you cant turn off. God, I hate transparent windows.
The new terminal isn't as good as expected. I switched back to iTerm pretty quickly.
The new dock is way too heavy on the eye candy for my taste.

The ugly:

A lot of port breakage, but thats to be expected I guess. And most of them get fixed really quick.