What is the best sequence to tighten the lug nuts on a wheel with N nuts?

November 10, 2010

Nuts are numbered [0,N) as you travel around the circle, and we’d like to output the list of nut indexes to tighten, in order. For N=4, we’d tighten [0,2,1,4], although there are many equivalent solutions due to the inherent symmetry. For N=5, we have [0,2,4,1,3].

This problem actually came up when I was trying to pick a deterministic “maximally distant sequence” of colors for a visualization that I was doing. There are answers good enough (or better) for my visualization problem, but I feel like the question is an interesting one. One thing that probably needs doing is defining the objective function (i.e., “maximally distant”) in a more formal way.

This post is intended to shame my future self into looking at it again, one day!

Speech Recognition Performance at NIST

November 5, 2010

The folks at NIST have plotted speech recognition competition performance over time on various datasets.  If you squint at the log-scale y-axis, it looks like we’re not making steady progress on the really complicated (i.e., real-life) datasets as one might hope.  On the other hand, this graph lists only NIST evaluations, which seem to have focused primarily on one particularly challenging type of speech for the past few years: meeting speech.

How to compile SRILM on Ubuntu

November 3, 2010

EDIT: This is my original post, but the comments have newer and better instructions.

I always encounter problems when compiling SRILM on Ubuntu.  Assuming the basic SRILM dependencies are installed on your system (see the Prerequisites), this works for SRILM 1.5.11 on Ubuntu 9.04 (Jaunty) and 10.04 (Lucid):

  1. Install tcsh if not already installed
  2. Install all the TCL developer libraries: tcl8.4-dev, tcl-dev, tcl-lib, tclx8.4, tclx8.4-dev.  This step may not be necessary, let me know what works for you.
  3. Uncomment the “SRILM =” line in the top level Makefile and replace the existing path with the absolute path of the SRILM top-level directory on your system (where the Makefile resides)
  4. Start the tcsh shell
  5. Type “make NO_TCL=X MACHINE_TYPE=i686-gcc4 World > & make.log.txt” to begin the build and capture stderr and stdout in a file
  6. If you can run “./bin/i686-gcc4/ngram-count -help“, the build was probably a success

Please add simplifications to this recipe or extensions to other versions of Ubuntu in the comments.

Personal Satellite Assistant

March 17, 2010

One of the coolest robot projects I’ve seen: the Personal Satellite Assistant (PSA).  It’s a red plastic sphere about the size of a bowling ball that is planned to fly around the space station on jets of air, acting as a speech-driven measurement and reference device.  They say it was inspired by Star Wars, and I couldn’t help but think of Luke’s training remote and the intelligent Exocomp robots from Star Trek.

The NASA website isn’t that great, but there is a 5 minute educational video and another 4 minute educational video that describe the PSA.

Mute annoying Pandora.com commercials

March 15, 2010

I love Pandora and I think they do a great job of monetizing their service.  The $1 surcharge on heavy use is pretty minimal and their audio ads are short and fairly infrequent.  However, I keep getting one audio ad that I absolutely hate but cannot ignore.  It pulls my attention away from what I’m doing and I am compelled to either take my headphones off or mute the sound to avoid accumulating aggravation.

The duct-tape solution for my Ubuntu box is a script that simply mutes the sound for 30 seconds.  I link to the script with an icon on Gnome’s toolbar and also map it to “CTRL-M” to allow for quick activation.  The script is below; the only thing you might need to do is change the soundcard index (the “0” in “-c 0 …”) on your system.


#!/bin/sh
amixer -c 0 sset Master,0 mute
sleep 30
amixer -c 0 sset Master,0 unmute

Speech Recognition with CMU Sphinx and SRILM language models

October 19, 2009

Speech recognition that does not take advantage of domain specific language models produces silly results.  The recognition menagerie below was generated with Sphinx 4.  I used the HUB4 acoustic model and an SRILM language model generated from the human annotator transcripts.

  • No LM: thusly islam brown ivan and apelike of yellow
  • LM: a seated small brown ottoman and teapot of yellow
  • True: i see a small brown ottoman and a pot of yellow

Read the rest of this entry »

Solving equations with exponential and polynomial functions of x: the Product Log Function

October 18, 2009

I was trying to solve an equation of the form cx^p=q^x for x, but couldn’t figure out how to do the algebra needed to isolate x.  The actual problem was to find when an algorithm with O(n^2) runtime performance would have a shorter runtime than an algorithm that is O(2^n).

Text-based searches weren’t turning up anything, so I tried to see how Wolfram Alpha would solve it.  Turns out there is a neat tool called the Product Log function, aka the Lambert W function, that can be used to find a closed-form solution to this equation.  The Wikipedia article explains the solution method, but you basically need to reorganize the original equation into the form y = x e^x using algebraic and logarithmic operations and then x=W(y).  Note that the solution may not be unique; W(y) is a multivalued function.

Of course, for my original problem where I was actually trying to find the closest integer less than or equal to x, and given that q^x grows rather quickly, it is sufficient to use a spreadsheet to calculate the two sides of the original equation for all small values of x.

Yahoo! Pipes – Helping Me Travel on the Cheap

October 13, 2009

Yahoo Pipes is something I came across when trying to find a RSS aggregator/keyword spotter/emailer.  It is a really neat web-based graphical scripting tool for manipulating web-accessible data.  It’s got a  regex component to manipulate datasources!

It didn’t take me long to construct a pipe that pulls multiple airline ticket RSS feeds from the STA website containing “Chicago” or “Detroit” and then sorts the aggregated feeds by ascending price.  The result is output to an RSS feed, whose updates can be sent to an email address by Yahoo Alerts.

Yahoo has been aggressively climbing back into the ranks of “cool” for the past few years.  I’ve been impressed with the amount they contribute to the web and open source community and how they seem to be more proactive than Google about sharing their research.  Thanks again, Yahoo!

Minor Greasemonkey Tweak to MSU Course Scheduler

October 10, 2009

Every time I use the MSU Course Scheduler, I may or may not remember to click the “View all results on one page” checkbox.  It’s a small pet peeve, but Greasemonkey comes to the rescue.  This simple Greasemonkey script will set the checkbox whenever the page is loaded.

Using Xournal to Annotate PDFs

September 13, 2009

Just came across an open source tool that allows easy annotation of PDF files: Xournal. One can add text, sketches, and highlighting and then export the result to a PDF.