Thoughts on Machine Learning, Representation Theory, and RoShamBo – Part I

I’ve recently been doing some reading on machine learning with a mind towards applying some of my prior knowledge of representation theory.  The initial realization that representation theory might have some interesting applications in machine learning came from discussions with Chris Olah at the Toronto HackLab a couple months ago; you can get interesting new insights by exploring new spaces!  Over winter break I’ve been reading Bishop’s ‘Pattern Recognition and Machine Learning‘ (slowly), alongside faster reads like ‘Building Machine Learning Systems with Python.‘  As I’ve read, I’ve realized that there is plenty of room for introducing group theory into machine learning in interesting ways.  (Note: This is the first of a few posts on this topic.)

There’s a strong tradition of statisticians using group theory, perhaps most famously Persi Diaconis, who used representation theory of the symmetric group to find the mixing time for card shuffling.  His notes ‘Group Representations in Probability and Statistics‘ are an excellent place to pick up the background material with a strong eye towards applications.  Over the next few posts I’ll make a case for the use of representation theory in machine learning, emphasizing automatic factor selection and Bayesian methods.

First, an extremely brief overview of what machine learning is about, and an introduction to using a Bayesian approach to play RoShamBo, or rock paper scissors.  In the second post, I’ll motivate the viewpoint of representation by exploring the Fourier transform and how to use it to beat repetitive opponents.  Finally, in the third post I’ll look at how we can use representations to select factors for our Bayesian algorithm by examining likelihood functions as functions on a group.

RPS25 is a generalized form of Rock Paper Scissors.  I'll leave generalizations of this post to the RPS25 case as an exercise to the reader...
RPS25 is a generalized form of Rock Paper Scissors. I’ll leave generalizations of this post to the RPS25 case as an exercise to the reader…

Continue reading

Know Your Sensor

Recently I’ve been playing with building a regression model for the brightness of images produced with the Raspberry Pi’s camera board. Essentially, I want to quickly figure out – hopefully from a single image – what shutter speed and ISO to choose to get an image of a given brightness.

This is a pretty standard regression problem: We some data, extract some information from it, and use that information to make a prediction. To get a better handle on the algorithms involved, I wrote my own code to perform the regression, using NumPy for fast linear algebra operations. You always learn something from re-inventing the wheel, after all.

Data from images of my back yard.  Each point is one image.  The y-axis is the brightness of the image, the x-axis is the ISO the image was taken at, and the color indicates the shutter speed the image was taken with.
Data from images of my back yard. Each point is one image. The y-axis is the brightness of the image, the x-axis is the ISO the image was taken at, and the color indicates the shutter speed the image was taken with.  The shutter speeds and ISO’s chosen were evenly spaced (except for a few rogue images).  We can see there’s a kind of ‘sweet area’ for SS/ISO, with some upper threshold where things get too bright/dark very quickly.  We also see that the increase in brightness as ISO increases is non-linear.

Continue reading

Pi-Lapse 3: Toronto Skyline

A still from a test-reel of timelapse taken at Owen Sound, in North-ish Ontario last week.
A still from a test-reel of timelapse taken at Owen Sound, in North-ish Ontario last week.

I’ve done quite a bit to improve my Raspberry Pi-based timelapser.  I have a pretty good system together now, thanks in part to recent firmware updates to the Pi which allow me to directly control the shutter speed and ISO of the camera sensor instead of relying on auto-exposure settings.  The auto-exposure is pretty unreliable from one shot to the next: the camera makes a different decision each time it snaps a picture, which leads to quite a lot of flicker.  Previously, I was dealing with this flicker by manipulating the images in post-production, but I’ve now written some code to get the camera to try to maintain a constant image brightness across a long shoot.

The code now consists of a ‘timelapser’ class, which keeps track of its current shutterspeed and ISO (SS/ISO henceforth), and the brightness of the last few images taken.  It then adjusts SS/ISO to try to get the image brightness to 100.  By keeping track of the last few images, it is a bit less susceptible to being upset by one strange image (like, say, if I put my hand over the lens for one shot, producing a black image), or more standard movement within the frame.  On the other hand, it takes a while longer to settle down to the ‘right’ SS/ISO.  So it’s currently set up with an initialization step, where it finds a good SS/ISO pretty quickly, and then transitions to actually taking pictures.  The result is very little flicker as the timelapse goes on, and a pretty constant level of image brightness when light levels gradually change: like when we watch dawn or dusk.  (If you’re interested in playing around with the code, I’ve set up a github repository here.)

As an example, this is a video that we shot over about three days on my friends Ketan and Ananya’s balcony.  They have a great view over Toronto, from the CN Tower to Honest Ed’s.

Continue reading

Pi-Lapse 2: Wychwood Barns Farmer’s Market

Aerial raspberry pi installation. The boxy-head is the pi(s), attached to a tripod held up by a jib arm.  A ten-port powered usb hub is duct taped to the tripod, providing lots of data storage and internet to the Pi's.
Aerial raspberry pi installation. The boxy-head is the pi(s), attached to a tripod held up by a jib arm. A ten-port powered usb hub is duct taped to the tripod, providing lots of data storage and internet to the Pi’s.

Almost immediately after my first foray with the Raspberry Pi timelapse I was contacted by Cookie Roscoe, who coordinates a weekly farmer’s market for The Stop.  The Stop is a community food center here in Toronto, providing lots of programming and emergency food access for lower-income people.  My partner, Elizabeth, worked with them for about three years, so I was super happy to try doing a time-lapse of their market.

Here’s the results!  Lots of technical stuff about what went into the video after the break!

Continue reading

Pi-Lapse Test Footage

A camera made of legos!  I've built two of these; the photo was taken with the _other_ raspberyy pi camera.
A camera made of legos! I’ve built two of these; this photo was taken with the other raspberry pi camera, during a three-week time-lapse shot.

My recent DIY electronics project has been putting together a Raspberry Pi-based camera.  The Pi foundation sells a camera board which plugs into the Pi; it’s sold as ‘a bit better than the average camera in a mobile phone.’ But the Pi’s default Raspbian Linux installation comes with a couple programs for controlling the camera, and lets you take still pictures and videos easily.

In the interest of using the camera for something you can’t usually do with a store-bought digital camera, I wrote a short python script which takes a photo assigns it a file name based on the date and time taken.  It then does some sampling of the picture, and only keeps pictures which aren’t ‘too dark.’  And then cron runs the photo script once every five minutes.  In other words, the Pi is set up for long-form time-lapse photography.  The resulting pictures are then easy to compile into a movie.

Continue reading

Two Weeks in Paris

A quick game of Go with Yan X Zhang at the Sage-Days in Orsay.  I lost badly!
A quick game of Go with Yan X Zhang at the Sage-Days in Orsay. I lost badly!

Back for a day in Nairobi after visiting Paris for FPSAC 2013 and Sage-Days 49.  On the whole, it was a really productive visit; I met a number of my primary goals.  On the mathematics front, Kenya has been extremely isolating: One of the big goals for the conference, then, was to connect to some new things to work on and figure out what’s been happening in the algebraic combinatorics world in the last year.  It was exciting to actually work on math with people: when I arrived in Maseno, it turned out that no new graduate students had come into pure maths in some time, which meant there was no real outlet for doing math with other people.  So it’s been kind of a lonely year: I did a lot of work on education, and did some interesting community building around computer science with LakeHub, but often felt like my big area of expertise really wasn’t terribly helpful in Kenya.  The institutions weren’t really ready to make use of what I was bringing, since there wasn’t time or space for people to do research.  I obviously found lots of great stuff to work on anyway, but it felt a bit funny that I was so unable to engage people on the maths.

Continue reading

Tips on Running a Headless Raspberry Pi

A Raspberry Pi with a head.  Well, not the usual meaning of 'head,' I guess.  (Giraffe and Carcassonne box included for scale.)
A Raspberry Pi with a head. Well, not the usual meaning of ‘head,’ I guess. (Giraffe and Carcassonne box included for scale.)

I was recently helping out a friend with a headless Raspberry Pi setup, and thought it would be helpful to consolidate a few useful bits here. From here, you can set up all kinds of cool projects using the GPIO pins, set up a headless web server, or anything else you can think of. For my part, when I hurt my ankle a few months ago, I hooked the Pi into a hard-to-get-to stereo system and logged in remotely from the other side of the room to play music… I also used a headless setup to run the really long compile for the Sage computer algebra system a few months ago.

Continue reading

Hashes with Salt

Passwords being cracked by some really simple python code I wrote.  Who knew 'Tigger' was such a common root word for passwords?
Passwords being cracked by some really simple python code I wrote. Who knew ‘Tigger’ was such a common root word for passwords?

(These are notes adapted from a presentation I gave at the LakeHub workshop this week.  They owe a lot of debt to this article, which inspired the talk.  If you already know that you should just use bcrypt or something similar, and why, you can just skip to the ‘conclusions’ section.)

So let’s suppose you’ve just made a hot new website from which you’ll make a million dollars a year.  You get to the point of creating a database for all of your users who will be logging in and doing things like buying airplanes, so you put together a database table.  Maybe it looks something like this:

Name Email Password
Bill Gates bill@microsoft.com passw0rd

A few weeks after launch, you have two million users, and someone breaks into your server and steals the database. Of course, they don’t tell you that they did this; they’re much happier to keep the database, pull out a name and password, log in as someone else, and use your site to steal lots of money and undermine the basic building blocks of democracy and common decency.  After sending apologies to the userbase, you decide that your database structure was flawed.

Continue reading

LakeHub

Lakehub Workshop #0 flyer
LakeHub Workshop #0 flyer

Over the last few weeks I’ve been helping out a group of technologists in Kisumu who are interested in starting a new tech-hub.  There are a number of such hubs in Nairobi; the most famous is the iHub, which provides a space for developers to work and connect with businesses that need their skills.  Kisumu is actually a pretty sizable place, and when one considers the universities in the area – like Maseno and Masinde Muliro – it’s a bit surprising that there isn’t more happening on the technological front.

Thus comes the LakeHub concept.

The plan is to create spaces to encourage the technological sector in Western Kenya by helping local techies build up relevant skills, encouraging local businesses to make better use of technology, and connect those same businesses with the tech people for envisioning and implementing new business ideas.  It’s been a really great opportunity to put my community organizing skills to good use in the local context; the on-the-ground work has felt eerily similar to work on building (and saving!) cooperative housing spaces back in Davis, California.

As an educator, I’m hopeful that such a space will help change university students’ expectations as to what they are learning in their degree programs, and to provide better opportunities and outcomes for those that passionately engage in the sciences.

Continue reading

Towards a Sage Problem Server

Layout of resources for a hypothetical Sage problem server.
Layout of resources for a hypothetical Sage problem server.Django

Problem Statement.

I’ve finally been making some progress towards building a Sage-based ‘problem server,’ as we were talking about way back in January.  It’s clear that the tools developed have a wide scope of use.  Before building something that gives open questions and reacts in really interesting ways to input, a stepping-stone is to build something that serves up individual math problems and asks for an answer.  In some sense, such things are already done by Webwork and Moodle with varying degrees of success, but building a nice implementation would allow some new directions.

Now, I should stress that I think WeBWorK is pretty awesome, and has some really transformative potential.  I’ve been encouraging its use in Kenya, and it’s been extremely interesting seeing it used in service courses in Strathmore University and now Maseno.  These are places with ever-increasing class sizes, and a well-designed online homework tool promises to greatly improve student comprehension of the course material.  The big database of existing problems in WeBWorK is also really helpful; there are over 26,000 problems in the Open Problem Library.  There are three issues with WeBWorK that a new implementation could/should address:

  1. Modularity: WeBWorK is a pretty monolithic piece of software.  It includes three essential components: a problem server, a problem database, and a learner management system (LMS).  Basically, these should be busted out into three genuinely separate components.  Breaking out the problem server allows easy integration into Moodle or another well-thought-out LMS, or else integration directly into things like online textbooks.
  2. Modernization: The WeBWorK codebase was mainly developed some time ago, and new versions are slow to come out.  (The last stable release is from December, 2010, over two years ago.)  The interface is also decidedly…  Clunky.  There’s a natural question of how one could improve the system using modern AJAX-type tools.  Better interactivity will lead to a much better user experience.  Things like one-button signup with Google or Facebook accounts is one thing I can think of off the top of my head that would greatly improve the user experience.
  3. Ease of Writing Problems:  Currently, WeBWorK problems are written in a highly idiomatic version of Perl.  I was interested in writing problems a couple years ago and got the feeling that it was, in the end, a bit of a black art.  The documentation is a bit scant, and most mathematical objects have their own idiomatic libraries.  Switching to a python/sage framework would mean that writing problems should become much easier: Sage already recognizes all of these mathematical structures.  And if the problem definitions are in python, we’re really using the same syntax as our Sage work.  This should make it much, much simpler to pick up a bit of Sage and then start writing problems.

Continue reading