Strange paths

Don’t read this blog, go and read Strange Paths instead. Beautiful animations and discussion on aspects of “Physics, computation, philosophy”.

Advertisements

Non-negative matrix factorization and music

Amongst the work I did during the EASy MSc at Sussex was this 2005 paper on non-negative matrix factorization (NMF) applied to sound analysis.

I’d become fascinated with the information theoretic ideas about perception and redundancy originated by people like Horace Barlow, and particularly their application to sound by researchers like Paris Smaragdis. I’d originally been interested in ICA but Smaragdis and others were starting to apply NMF to sound around that time.

The basic idea of the paper is: the brain is able to analyze distinct sounds from the jumbled mixture that hits our eardrums because audio signals generally have structure, musical audio particularly so. If you take a time-frequency transform like a spectrogram of a piece of piano music, you find that it has approximately:

  • A sparse representation: each note has a characteristic frequency profile. The complete spectrogram is made by scaling and adding all the notes playing simultaneously. In the bases of all these profiles, the sparse representation consists of the activation levels of each notes.
  • Scaling invariants: scaling a vibrating system physically up or down is equivalent to translation in log-frequency.

NMF is a way of obtaining a low-rank approximation of a matrix as a product of two others, subject to the constraint that all the elements have to be positive of zero. Amazingly, this simple assumption is enough to discover all kinds of useful structure, including the separation into spectral bases like that in a spectrogram.

Left to its own devices, straight NMF on the piano spectrogram piece would likely approximate the spectral profiles of each note, but in no particular order. The additional step in this paper is to further require there to be only one profile, log-frequency translated – and this is indeed enough to get you recognizable notes.

There is an enormous and booming literature on sparsity in signal processing in areas like compressed sensing – Nuit Blanche blog is a good place to find out more.

Evolutionary and Adaptive Systems

Synchronicity… a sudden convergence of interesting links have got me all nostalgic.

It all sent me back to the fascinating year I spent in 2004/05 doing the Evolutionary and Adaptive Systems MSc at the University of Sussex.

This wonderful inter-disciplinary course brings together researchers in computer science, biology, creative systems and even a little philosophy. Pretty much everything was fair game for study, from robot ants spreading glow in the dark pheromone trails; neural networks made of actual buckets of water; to evolved passive-dynamic walking legs with fourteen knees.

I mean to go back through the work I did at Sussex and see what’s interesting enough to post here, starting with my dissertation on NMF.

Wild things

I made this absolutely ages ago but it’s my favourite musical creation. Storytelling, animal noises and wild rumpus – Wild Things MP3.

Debugging Flex with Emacs 22/23

I’m working a lot with the Flex 3.3 SDK at the moment, using Emacs and the Adobe fdb debugger run from M-x gdb. Since upgrading from Emacs 21 to 22, the debugger seemed to stop being able to trace through the source files correctly. You could set breakpoints in files from Emacs with C-x b, and the source paths were all known to fdb so the correct code would appear list in the debugger console. But the connection back to display the source file in another buffer with the current line arrow wouldn’t show.

After some digging it turns out that to produce output specially marked up with ^Z characters for Emacs to read, both gdb and fdb need to be invoked with the fullname option. But while gdb accepts -f, -fullname or --fullname for this, fdb doesn’t accept the double-dash --fullname style – and the Emacs 21 to 22 upgrade changes the argument from the single to the double dash form.

If you know that the fix is easy, you just need to invoke fdb with the -f or -fullname argument. You can find the acceptable forms in the fdb source code here.

Update: for the change to Emacs 23, you need to use M-x gud-gdb instead of M-x gdb.
So: M-x gud-gdb, enter fdb -f and everything works as it should.

Or put this in .emacs, and use M-x fdb:

(defun fdb ()
"Run fdb debugger"
(interactive)
(gud-gdb "$PATH_TO_FDB/fdb -f") )

Ambient computing Arduino display

This Christmas I finally found time to finish the Arduino based “ambient computing” project I started last year.

Box

The idea is that there are lots of tiny pieces of information on the web that are useful enough to deserve a dedicated, unobtrusive display like a clock or calendar. Getting rid of the need to check a PC or phone screen for these is a matter of:

  • Having a low-power display that can be left on in the background
  • Defining the right, relevant bits of information and writing scripts to scrape from the web, boil them down to the right format and send them to the display

As an example of the kinds of super-relevant bits of data I mean, we live right underneath the train station. In the morning before leaving for work, I’d like to know:
* Are the trains from the local station to London on time?
* What’s the worst the weather is likely to do today, maybe I’ll cycle…
* Have I got any appointments that might affect my journey plans?

This information is all available on the web from National Rail live departure boards, weather forecast RSS feeds, and my online calendar at 30 boxes. But it’s only useful if it’s pushed to me, while I’m having breakfast – I can’t be stopping to fiddle about with a browser or I’ll never get out the door!

Construction

The actual display is very simple, just an ArduinoBT microcontroller with Bluetooth hooked to a 20×4 blue LCD screen (an HD44780).

Lovely wires
Ideally the display would have enough computing power to retrieve them from the net itself via Wi-Fi. However my current version doesn’t so it depends on a net-connected server with a Bluetooth card. I already have a quiet, low carbon footprint server from Tranquil PC to do this job.

It’s housed in an attractive cardboard box 🙂

Code

The Arduino embedded code is written in C. It keeps a set of buffers for different messages, and displays them in rotation. It also listens for Bluetooth connections, in case there are new messages to show. The messages are prefixed with a code saying which buffer to store them in, so I can avoid overwriting important but rarely updated information with high-frequency fluff like Facebook messages. The LCD backlight is controlled via a transistor which the Arduino’s “analog” PWM output can fade in and out. I use this to get an unobtrusive “pulsing” effect to show when new updates have been received.

I used a 20×4 modification of the Arduino 4-bit LCD library to drive the display whilst keeping some I/O pins spare to extend it later.

When I started the project a year ago, I wrote the server code in Perl, with LWP and HTML::TableExtract to fetch and parse the data. I’m now doing a new more portable version in Python with the LightBlue Bluetooth library. The Python version should also run on my Nokia N82 phone as an alternative to needing a server machine.

It has a few feed connections implemented at the moment:

  • Departure boards – the estimated time of the next four departures from our local station to central London, neatly formatted for the four lines
  • Weather forecast for today and tomorrow from the BBC – again from an RSS feed, you get a one-word forecast like “cloudy” with the max and min temperatures.
  • Calendar entries from 30boxes
  • Facebook status messages taken from the RSS feed. It’s quite nice to have your friends’ messages as background chatter.

Let me know in the comments if you’d like to see any of the code or the wiring details.

Issues

Communication range and power are critical in embedded projects like this. I currently have it running from 2 rechargeable AA batteries for portability which lasts a few hours, but as it’s meant to sit on a table or shelf like a wall clock I will switch it back to use a DC adaptor.

The Bluetooth range is also an issue, if it can’t receive updates from the server it’s not a lot of use! Fortunately it works where it needs to in our flat though it needs some careful placement. The Arduino board is class I so should have a 100m unobstructed range, though my PC’s USB dongle might not be.

I might also experiment with adding an another input device, like a button or slider of some kind, so if you happen to want something in particular like the weather forecast, you can rotate straight to it without waiting for it to page there.

I keep thinking of other content to add, like Twitter messages or the next contents of our organic veg box – but one interesting thing is that the busier and flashier the box is, the less it’s doing it’s job! For information rich, rapidly changing feeds, it makes much more sense to use the web or a mobile browser. The niche of this device is to keep a very small amount of slowly changing info present in the background, so the stuff you need to know is “just there” like the time on a wall clock. Cram too much in and you end up staring at it waiting for the page to change like old fashioned Ceefax displays.

For now, I’m quite pleased with it, and will live with it for a bit to see how it settles in before I add anything else. If you have any ideas of things to add or ways to improve it, ping me in the comments.

Bayesian decision theory explained simply

Ghahramani and Wolpert present a clear and simple account of Bayesian decision theory in perception.