LeechBlockList

LeechBlock is a Firefox extension that blocks time-wasting websites that you manually specify.  One of the nicest features for those of us who use multiple computers is the ability to load the block list from a URL.  I put together a simple web interface for maintaining such block lists:

http://leechblocklist.appspot.com/

It's useful even if you just want to maintain your own list, but possibly more useful in that it maintains a list of sites that are commonly thought to be time-wasting.  Or, it will, if a few more people start using it.

so much to say

How is it that everyone has so much to say they have trouble deciding what not to say?  I'm thinking of this quote, attributed to Blaise Pascal:

I made this letter longer than usual because I lack the time to make it shorter.

This gets brought up in the context of presentations, papers, conversations, code, art, anything that requires some amount of creativity.  The hard part, as it goes, is condensing the huge number of things you'd like to say into a smaller coherent form, often to satisfy some external constraint on time or space.  If left to my own devices, a person of this mindset must think, I would emit an endless stream of wisdom, but alas, others are unwilling or unable to process my brilliance in its entirety.  All of my effort must therefore go toward eliminating all but the very best of what I have to offer.  And these are gems I'm discarding.

Never once in my life have I had this experience.  Coming up with enough to say has always been a struggle for me.  While other people are cutting stuff out left and right, I'm trying to come up with just enough to avoid outright embarrassment.  Am I just not creative?  Not prolific?  Or is my threshold for what is worth saying much higher?  I wouldn't say it's that high, since I'm blogging about this right now.

Incidentally, So Much to Say is possibly the only Dave Matthews Band song I like.

PageRank for images

I was just watching a talk by Peter Norvig in which he mentions some research done at Google (paper here) on applying PageRank to image search. The idea is that instead of connections based on hyperlinks, connections between images are based on visual similarity between the two images, as computed via SIFT or some other descriptor. Then, the VisualRank of an image is some estimate of its centrality in the underlying collection of images.

I don't think this is the right way to think about image search, for a few reasons. First, and most simply, a hyperlink between two web pages has different meaning from a pair of similar images. The PageRank algorithm for web pages has an intuitive explanation: imagining a simplified web surfer randomly following web links, what is the stationary distribution over pages visited by this surfer? (Of course, it's slightly more complicated than that.) VisualRank has no such intuitive model -- instead of following web links, a surfer would have to randomly jump from one image to another similar image. This doesn't seem related to actual image browsing, and is nearly impossible on the current web as links between visually similar images aren't manifested in any way.

One could argue that it's not clear that the PageRank browsing model is the right way to think about web search either, and I would imagine much research has been done on alternative models. In essence, what is captured by both PageRank and VisualRank is a measure of centrality. I want to argue that while centrality may be a reasonable criterion for ranking web search results, it is less reasonable for ranking image search results.

In PageRank, hyperlinks are directed. I can link to CNN (and just did) without them linking back to me. This is not true of image similarities in VisualRank, which are undirected. What are the implications of this? Well, if I link to CNN and they don't link back, it is entirely possible and likely that our PageRanks will be very different. However, if two images are visually similar, they are likely to have similar VisualRanks. (This is caused not only by the symmetry of visual similarity, but also its near-transitivity -- if image A is similar to B and B is similar to C, then it is likely that A is also similar to C. One can imagine a contrived image collection in which this is not the case, but in a quick test it seemed to hold about 75% of the time. Visual similarity is much more like an equivalence relation than hyperlinking is.)

This is all fine if you want to find the single best image. But, if you want to find the best k images, you're going to get a bunch of near-duplicates of the highest ranked image, or at least a set that exhibits high redundancy. As an example, I computed the VisualRank of every image in a collection of a few thousand images of the city of Dubrovnik. Here are the images with the top 5 VisualRanks:


In contrast, and to illustrate that this isn't the only photo people take in Dubrovnik, here are the top 5 images selected by a simple summarization algorithm that also aims, indirectly, to avoid redundancy (disclaimer: algorithm is mine):


I do think centrality is a useful measurement on image collections. Alone, however, it is not a good way to order image search results unless you want homogeneity. This is less of a problem in web search in that there's nothing inherently wrong with the top set of results linking to one another. Sure, they may suffer from homogeneity of opinion to some degree, but the content of each result is different. With connections based on visual similarity, linkage among the top ranked images means some of them are providing no new information at all.

Paul Graham's essays

It annoys me when blog-like content does not have an RSS feed. Sometimes it even annoys me enough that I go and do something about it. So without further ado (not that there was that much ado to begin with), here's a full-text RSS feed of Y Combinator founder Paul Graham's essays:

http://pipes.yahoo.com/pipes/pipe.run?_id=e7e734678a95c1b71652ef7c4f4cfe9c&_render=rss

It only contains the most recent 10 entries, to keep loading time reasonable. I tried to include more, but Google Reader kept choking on Yahoo's Pipe when I tried to import the feed.

the kind of person

I was flipping through one of Michael Pollan's books at the airport bookstore last weekend. It may have been In Defense of Food, but I can't remember. Anyway, I came across this puzzling piece of advice:

Be the kind of person who takes supplements.

That is, you don't really have to take the supplements, as long as you are the kind of person who might. Pollan explains that studies have shown people who take multivitamins are generally healthier, but in controlled studies, multivitamins haven't been shown to actually make anyone healthier. This is reasonable, as it could be that supplement-takers are more health-conscious to begin with, and taking the supplements simply indicates their health-conscious status.

The puzzling part is this: how can someone follow Pollan's advice, other than by taking supplements?

This is related to a few philosophical paradoxes. Here's Kavka's toxin puzzle (from Wikipedia):

An eccentric billionaire places before you a vial of toxin that, if you drink it, will make you painfully ill for a day, but will not threaten your life or have any lasting effects. The billionaire will pay you one million dollars tomorrow morning if, at midnight tonight, you intend to drink the toxin tomorrow afternoon. He emphasizes that you need not drink the toxin to receive the money; in fact, the money will already be in your bank account hours before the time for drinking it arrives, if you succeed. All you have to do is. . . intend at midnight tonight to drink the stuff tomorrow afternoon. You are perfectly free to change your mind after receiving the money and not drink the toxin.

The question being, is it possible to intend to drink the toxin tonight if you know you won't actually have to tomorrow?

starting tomorrow

It's sad that it took me this long to come to this realization, but starting tomorrow does not work, at all, for anything.

The interesting part is that starting now does not work either. The entire mindset associated with making an abrupt transition from a bad state to a good state is the problem. Typically, the good state is unsustainable and you eventually end up back in the bad state again, where you tell yourself that at time t you will make another abrupt transition to the good state, which is unsustainable, so you end up in the bad state again, and so on.

The only solution that I've found is to try to be in a state that is not so bad that you have to make empty promises to yourself to transition out of it, and not so good that you can't keep it up.

Another reason not to make an abrupt transition from the bad state to the good state at some future time t is that this encourages you to get in all the damage you can before time t. And since you keep reverting back to the bad state, you can end up doing a lot of damage this way.

wordless melodies

This is the second post in my Things I Like in Music series.

Have you noticed that lots of songs have vocal parts with "la la la..." or "na na na..." instead of lyrics? And have you noticed that these parts are almost always extremely catchy? The best example is probably Hey Jude, but there are many such songs: Land of 1000 Dances, Centerfold, Can't Get You out of My Head, and many more. I posted a quiz a while back about guessing these songs given only the rhythm of the "na na na..." part, if you're interested in more examples.

If you agree that these parts are usually catchy, and you do, you may wonder why this is the case. My guess is that removing lyrics doesn't actually make the melody catchier, but that sometimes a melody is so catchy that the songwriter feels no need to embellish it with lyrics.

A related phenomenon that I also like is when a song has an instrumental solo that is just the vocal melody. Some examples are Come as You Are (or Smells Like Teen Spirit for that matter), Buddy Holly, and Paint It Black, in which the vocal melody is both played on guitar and hummed (not simultaneously). You could also count the whistling in Walk Like an Egyptian.

Or you could make an entire song out of weird vocal noises, like this one.

in between major and minor

This is the first post of many I plan to make about Things I Like in Music.

If you've played around with Songsmith (and if you haven't, you should), you'll notice that instead of a switch between major and minor, we provide a "happy" slider that lets you explore a continuum between strictly major and strictly minor chord progressions. Is this really how music works, you might ask? Can a song be somewhere in between major and minor? Now, certainly a song can be major and minor in different sections, like the chorus and verse (Happy Together is a good example of this). Minor-verse-major-chorus (and its much rarer opposite) is also a Thing I Like in Music, but right now I'm interested in songs that sound both major and minor within a single section.

It turns out that many great songs do this, and wavering between major and minor is part of what makes them great. Here are a few examples (Roman numeral chord names assume the major key):

One Headlight
Listen to the verse, and notice how the first half of each line sounds just a little bit less gloomy than the second half, which helps give the song its poignant feel. The chord progression during the verse is VI -> I -> III -> vi, two chords generally associated with the major key followed by a minor cadence.

Just What I Needed
The same thing happens in the verses here. The first half of each line sounds happier than the second. Even the lyrics seem to follow suit. "I don't mind you coming here." Moderately happy! "And wasting all my time." Umm, not quite so happy. The chord progression in the verse is I -> V -> vi -> III, the two chords most indicative of a major key followed by the two chords most indicative of a minor key.

Say It Ain't So
The previous two songs (or at least their verses, which we were focusing on) probably sounded closer to minor than major. This song, to me, sounds closer to major. The chord progression is vi -> III -> VI -> I, this time ending each phrase with a major sound. Perhaps ends of phrases have a stronger influence on the overall feel.

Yesterday
Both sections of this song live in the mysterious land between major and minor, and it's generally considered one of the best songs ever (citation needed). Coincidence?

silly headline

Robbery suspect attacks clerk with machete

Whether or not the guy is the attempted robber is uncertain, but he's definitely the guy who attacked the clerk with a machete during the attempted robbery. Of course the article itself is not this confused, only the headline.

Sudoku and nothing

Dan has given me an excellent way to look at research or other ideas, adapted from a David Letterman bit: is this something, or is it just nothing?

Here's one that seems to be nothing: a computer scientist has come up with an algorithm for Sudoku. And (surprise!) the algorithm is exactly how everyone already solves Sudoku puzzles. Nor is this strategy very interesting algorithmically, as it ends up being a regular old constraint satisfaction search.

Songsmith is blowing up

Microsoft Research Songsmith, which grew out of the MySong project I worked on last year, has gone viral, largely because of the (intentional) over-the-top silliness of the promo video. The fact that so many people are experiencing the results of our research is blowing my mind a little bit, especially with the wide variety of responses we're seeing. There's been some praise, some good-natured poking fun, and a fair amount of irrational hatred. Many people seem to appreciate the research while mocking the promo video, which I guess is okay, though the vast majority of them would never have heard about the research if not for the exceptionally silly video.

The most pathetic response I've seen is here. Yes, Michael Arrington, world's most famous tech blogger, decided to call a researcher at MSR gay. If you're going to call us gay, at least do it like this (warning: extremely offensive). And there are many other ways to diss Songsmith that I'm totally cool with.