Planet Zorgnine

don't break the only way to do something

2011-11-15T10:57:00.001-08:00

It is impossible to stay up-to-date with all of the blogs and news sites I read. For infrequently-updated sites with a high percentage of good stuff, RSS solves the problem. For frequently-updated sites with a lower percentage, it does not. I don't want to sift through hundreds or thousands of articles manually each day.

Up until a few weeks ago, I knew of exactly one solution to this problem: "sort by magic" in Google Reader, which sorted the RSS entries in my feed by, well, magic. Unfortunately, Google's much-maligned Reader update has killed the magic. The "sort by magic" option is still there, but they should probably change its name to "sort by angry illiterate moose". I used to see a nice mixture of posts from all of my followed sites, where posts from infrequently-updated sites usually showed up near the top, along with only the "best" posts from frequently-updated sites. (I don't know what "best" means, but it seemed to do just fine.) Now, I just see hundreds of posts from TechCrunch. This is not magic.

So, now I have zero solutions to this problem. I can no longer follow blogs like Marginal Revolution with several posts per day. TechCrunch is out of the question.

Any suggestions?

does playlist order matter?

2011-10-30T22:45:00.000-07:00

Does playlist order matter? Many people seem to think so (see High Fidelity), but I remain unconvinced. I was inspired to resolve this issue in my mind after seeing a poster at ISMIR 2011 evaluating several algorithms for automatic playlist generation. It turns out that there's a free dataset containing around 30,000 actual user-created playlists, covering over 200,000 songs.

What does it mean for playlist order to matter? There are a few simple things we could look for:

Some pairs of songs should occur frequently in one order, but not the other.
Some pairs of songs should occur close together (in either order) more frequently than predicted by chance alone.

There's a problem with looking at pairs of songs, though: the above dataset contains over 47 billion possible song transitions and only 30,000 playlists, containing around 20 songs on average. Possibly worse, only 9627 of the 545,867 pairs of consecutive songs (1.8%) appear more than once.
To address this lack-of-common-pairs issue, we can think about modeling a playlist as a list of artists rather than a list of songs, as this should increase the amount of repetition. Now, instead of counting the number of times Even Flow by Pearl Jam comes after Rusty Cage by Soundgarden, we count the number of times any Pearl Jam song comes after any Soundgarden song. This ameliorates the problem somewhat, as there are 128,778 consecutive artist pairs (23.6%) that occur at least twice in the data set.

Now, let's address #1: are there pairs of artists for which one is more likely to come first? Here's a simple way to test this:

For each pair of artists, compute the probability that they appear in one order (say, Pearl Jam then Soundgarden) when they appear consecutively. Then find the pairs of artists for which this probability is highest. (It's necessary to use something akin to Bayesian Rating here, to avoid pairs of artists that appear a few times in one direction and zero in the other.)
Randomly shuffle each playlist and recompute the probabilities, again looking at the highest-probability pairs. Do this several times. The highest probabilities you see will give you a good sense of what can happen based on chance alone, since there is obviously no meaningful order to the randomly shuffled playlists.
Are there any pairs of artists with ordering probability higher than anything you saw when using the randomly shuffled playlists? If so, we can say this pair of artists is likely to appear in one order over the other with some degree of significance.

It turns out that running this experiment yields no pair of artists that are significantly likely to appear in one order over the other. There's still a possibility of some asymmetry, however — maybe Pearl Jam is likely to appear two songs before Soundgarden, or three, etc. To address this, we can re-run the above test, but without the requirement that the songs are adjacent. That is, we can compute the probability that Pearl Jam occurs earlier than Soundgarden in a playlist where both appear. When we do this, we find that there's still no pair of artists with a preferred ordering.

Let's look at #2, then: are there pairs of artists that appear next to each other more than chance would predict? We can adapt our above experiment for this case: just compute the probability that two artists appear consecutively (in either order) when they both show up in the same playlist, and do the same for the randomly shuffled playlists. It turns out that now there are a few pairs of artists that tend to appear consecutively with some significance (keep in mind these playlists are from the early 2000s):

Ben Folds Five and Barenaked Ladies
Radiohead and Björk
Blink 182 and Weezer
Radiohead and Pink Floyd

So, I guess I will have to acknowledge that playlist ordering is something, and not nothing.

reverse lottery

2011-01-24T20:11:00.000-08:00

Of course you know about the lottery, where you can pay some small amount of money for a low probability of winning a large amount of money. And lots of businesses have promotions along the same lines: e.g., if you buy our slightly-overpriced french fries, you might win a yacht.

However, I have never seen the reverse: we're giving out free french fries, except there's a small chance you'll have to pay us $1000. Now, a potential customer might not have $1000, so let's lower the values here to get a simpler and fairer comparison between two potential offerings:

French fries cost $1.25, but one out of every five customers gets his for free.
French fries are free, but one out of every five customers has to pay a $5.00 fine.

There must be a reason why businesses never offer the second type of deal. Is it just logistical? Or is it that people would hate this, and a 1 in 5 chance of losing $5 is worse than just giving away $1.25. It seems that this sort of deal would not be too difficult to arrange, so I have to imagine that businesses don't offer it because people don't like it.

This brings me to my main point: a lot of law enforcement works like this "reverse lottery", and I think we're underestimating just how much people hate this. Our goal should be punishments that exactly offset the value of the crime, and a 100% chance of getting caught. This makes enforcement prohibitively costly, but serves as an ideal. (The other extreme, where you get away with criminal behavior almost all of the time, but if you get caught you and your family are tortured for 20 years then killed, sounds awful to anyone.) Certainty itself has value, and this needs to be traded off against the cost of enforcement.

Disclaimer: I don't know anything about crime statistics, and I would hope there are experts who do know what happens as you vary the level of punishment and probability of getting caught. I'm betting that, while keeping level of punishment times probability of getting caught constant, good things happen as punishment goes down and probability of getting caught goes up, and the only reason not to move further in this direction is cost of patrol.

This blog post arose from a discussion with Alex Jaffe.

(Another way to look at things is that in my ideal scenario, there is no crime — you simply pay for the damage you do.)

resolutions: 2011 edition

2010-12-26T13:14:00.000-08:00

The last time I made resolutions, it was the end of 2008. I've since gone 2 for 4 on those resolutions, and one of them took me an extra year. Here's what I resolve to do in the coming year (in no particular order):

Take piano lessons and do at least one public performance (Rewind shows don't count).
Participate in at least one submission wrestling tournament.
Re-learn and improve the 540 kick (see this video).
Take a dance class.
Finish (version 1 of) the awesome chord-listening iPhone app I'm working on.

I think I can go 5 for 5 this time. These are all extremely doable, like your mom. Notice that I did not officially resolve to post more often to this blog, or learn to snowboard, or learn to ride a bike, or learn Portuguese, or learn Chinese, or read more books, or play more video games, even though these are all things I want to do. You have to make cuts somewhere.

I also didn't include any work-related resolutions, because they are top-secret. And because we already have a similar process, except they actually hold you to it.

generalized bullshit

2010-06-17T18:41:00.000-07:00

I haven't read Harry Frankfurt's 1986 philosophical treatise On Bullshit. But here's a summary I like from its Wikipedia page:

In the essay, Frankfurt defines a theory of bullshit, defining the concept and analyzing its applications. In particular, Frankfurt distinguishes bullshitting from lying: while the liar deliberately makes false claims, the bullshitter is simply uninterested in the truth. Bullshitters aim primarily to impress and persuade their audiences. While liars need to know the truth to better conceal it, bullshitters, interested solely in advancing their own agendas, have no use for the truth. Thus, Frankfurt claims, "...bullshit is a greater enemy of the truth than lies are."

This does seem to be the defining characteristic of bullshitting - the lack of regard for truth. And it does seem to be more dangerous than lying, for the same reason that a machine learning classifier with 50% accuracy is far less useful than one with 10% accuracy.

However, bullshit can describe many things beyond statements with a truth value. For example, we talk about bullshit jobs. What exactly is a bullshit job? Is a bullshit job just one that requires you to generate bullshit statements? I think there's more to it than that. There's a whole book on bullshit jobs, and it provides us with some useful examples: cheese artisan (sculptor of supermarket cheese), feng shui consultant, economist, aromatherapist, life coach, and so on, though some unfortunately stray from bullshit territory into mere unpleasantness (roadkill collector) or overt detriment to society (patent troll).

What do these jobs have in common with Harry Frankfurt's definition, the lack of regard for truth? Certainly some may require explicit truth-disregarding, but I think a more fundamental similarity is the idea of a broken link to what really matters. For bullshit statements, the link between a statement and its truth value has been severed. Again, this is different from false statements, in which the link is present but set to "reverse". And bullshit jobs, then, are jobs which provide no direct benefit to society, and for which the indirect benefit requires a link which has been severed or never really existed at all.

What "really matters"? I'd say something that makes a person happy, though you can use whatever rule you want, as long as it isn't "nothing". Or, I suppose, if you say nothing matters, then you should conclude that everything is bullshit, which might be a defensible position. And keep in mind that there's lots of non-bullshit that is pretty far removed from mattering, like designing uniforms for train conductors, but that remain non-bullshit as long as the intermediate links hold up. In many cases it may be difficult to test all of these intermediate links, and in fact the increasing specialization in modern society may be the cause of the proliferation of bullshit. I'd guess that hunter-gatherer societies are able to get away with considerably less bullshit, because the links to usefulness of any activity are easily testable by anyone.

Looking it at this way, a large fraction of what we do all day is bullshit. From personal experience, most of what happens in academia is bullshit. 99% of research papers, including (especially?) the ones by me, are bullshit, even if every single statement in them is intentionally true. The business world, notorious for its bullshit, actually seems a little bit better. From what I can tell, tech startups seem to have relatively low levels of bullshit. At least, the good ones do - some have made my life noticeably better. And things like baking and selling bread are about as far from bullshit as you can get.

my first iPhone app

2010-02-16T22:40:00.000-08:00

Last week, my first iPhone app was finally accepted by Apple and is now available in the App Store. At first, I was a bit surprised at the number of hoops I had to jump through just to make my app available: lots of certificates, code signing, Developer Program joining, bundle identifying, not to mention Apple's notorious review process. Now that I look at the sheer number of throwaway apps available, though, I think there should be some more hoops, or at least different ones. For example, does iLike really need to produce an app for every single music artist in existence?

My app has now been up for a week or so, and another surprise has been the geographic distribution of downloads. Most of my downloads are from outside the US, even though I made no special effort at internationalization. I'm not even sure how people are finding it, as so far I've only told my friends about it and it's certainly not at the top of the App Store charts.

Oh yeah, I suppose I should describe the app itself. It grew out of a simple demo I created for our music seminar here at UW. Our theme that quarter was the theremin, which allows for continuous control over pitch but is extremely difficult to play. The problem with continuous control over pitch is that usually (in Western music), you just want to play the 12 standard notes, and mostly just the 7 notes from one key. My app lets you trade off between these two extremes. You play by touching the screen, with pitch on the x-axis and hardness of quantization on the y-axis. Touch near the top of the screen, and the pitch is quantized to the nearest note from a particular scale. Touch near the bottom, and the pitch is unaltered. Touch near the middle, and the pitch is "soft-quantized", or nudged gently toward the nearest scale note.

Anyway, my app is pretty fun. You should download it. And if you tell me how to make it better, I might actually do it, especially if you have suggestions for making it a "real" instrument, that someone might use in a performance.

Interestingly, there is another instrument that allows for both continuous and discrete control over pitch: the ondes Martenot. Good luck porting that to the iPhone.

LeechBlockList

2009-12-05T13:05:00.000-08:00

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

2009-11-16T23:30:00.000-08:00

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

2009-11-01T15:51:00.000-08:00

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

2009-08-28T22:50:00.000-07:00

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

2009-08-19T10:42:00.000-07:00

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

2009-08-01T16:04:00.000-07:00

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

2009-06-01T22:01:00.001-07:00

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

2009-05-10T00:04:00.001-07:00

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

2009-04-26T19:36:00.001-07:00

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

2009-03-16T11:00:00.000-07:00

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

2009-01-16T00:50:00.000-08:00

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.

automatic rebalancing through automatic exchange

2008-12-30T22:23:00.000-08:00

When investing, you often want to maintain your asset allocation, which can depart from your initial allocation as specific assets increase or decrease in value. One option is to periodically check your allocation and manually transfer funds between assets (rebalance) if necessary. An added convenience is automatic rebalancing, where your investment company rebalances for you at some frequency.

However, Vanguard, one of the most popular investment companies, does not seem to support automatic rebalancing of an arbitrary asset allocation. Here's a trick you can use to achieve the same effect through automatic exchange:

Suppose you have three assets A, B, and C that you'd like to hold in the percentages a, b, and c respectively, where a + b + c = 100. All you need to do is set up 6 automatic exchanges, where A gives b percent of its value to B and c percent of its value to C, B gives a percent to A and c percent to C, and C gives a percent to A and b percent to B. In general, each asset receives a fixed percentage of each other asset, equal to the percentage of the receiving asset in the desired allocation.

The above technique rebalances exactly, but it has some problems. First, you definitely do not want to do this if there are taxes or fees associated with the transactions, since the transactions will be pretty large. (Performing the exchanges within a Roth IRA at Vanguard should still be okay.) Second, it can be a pain to set up an automatic exchange for each pair of assets you own.

Let's address both problems, though really, if you're faced with taxes or fees, you probably just want to do your rebalancing manually. However, you can decrease both the number and the size of the transactions by doing something I might call "soft rebalancing". The trick is that instead of exchanging between every pair of assets, we create a cycle of exchanges. In the above example, we could have A give to B, B give to C, and C give to A. (I'll get to the exchange amounts in a bit.) In general, if you have n assets, you only have to set up n exchanges. With soft rebalancing, you lose the ability to rebalance exactly, as we'll see.

So what are the exchange amounts? There's a slight complication, in that we can now change the rate at which rebalancing occurs, so the exchange amounts can be scaled. In the above example, A would give B proportional to 1/a, B would give C proportional to 1/b, and C would give A proportional to 1/c. In general, each asset gives up value proportional to the inverse of its percentage in the desired allocation. Again, these amounts should be scaled based on how fast you want the rebalancing to happen. At the maximum allowable rate, one of the assets will be giving up all of its value at each rebalance.

There are some problems with the cycle of exchanges scheme. Most importantly, it may take many rebalancing steps to transfer between an asset with excess value and an asset with insufficient value if the asset with insufficient value is far "downstream" from the asset with excess value. There are other schemes that address this issue, like setting up one "hub" asset and having all exchanges take place between the hub and one of the other assets (in both directions), though this scheme requires setting up about twice as many automatic exchanges.

An important point is that these exchanges must be in terms of the percent of the holdings of an asset. If the only supported exchanges are in fixed dollar amounts, automatic rebalancing is impossible. Also, I'm not sure how practical any of this is, since I have to assume that at some point Vanguard and other investment companies will offer automatic rebalancing. In the meantime though, you can use my trick if you're desperate.

resolutions

2008-12-30T09:54:00.000-08:00

I have never made New Year's resolutions before, but this time I actually have some idea of the things I want to accomplish in the coming year:

Graduate.
Create an interactive labeling demo, where users can annotate static objects in images and they get attached to the "real world". I'm working some of the techniques behind this right now, and I have a crappy demo built on top of LabelMe, but I would like to have a more scalable and usable one.
Work out the details of my convex formulation of visibility constraints in multiview stereo and write a paper on this.
Start training MMA, probably here.

lyrics quiz

2008-12-13T01:40:00.000-08:00

Here's a lyrics quiz with a twist: all of the lyrics consist of syllables like "na" and "la" instead of actual words. Spacing and commas generally indicate time between syllables. The "X" indicates other words that are part of the phrase, but would give away the identity of the song. Name as many songs as you can in the comments. None of them are at all obscure, and I've included the decade in which each song was released.

1) 1980s
na na na na na
na na na na na, na na na na na, na
na na na na na, na na na na na na na, na
X

2) 1980s
na na nana na na
nana na na nanana na na

3) 1990s
nana nana nana nana na na
nana nana nana nana na na

4) 1960s
na, na na nanana na
nanana na, X

5) 1960s
na nana na nana na nana na

6) 1970s
fa fa fa fa, fa fa fa fa fa, fa

7) 1960s
na na na, na
na na na, na
X

8) 1980s
la la la lala la
la la la lala la la

9) 1970s
doo, doo doo, doo doo, doo, doo doo
doo, doo doo, doo doo, doo, doo doo

10) 2000s
la la la, la la lala la
la la la, la la lala la

ECCV 2008

2008-12-06T19:47:00.000-08:00

ECCV 2008 happened over a month ago, but it's not too late for me to post a summary of some of my favorite papers from the conference, as well as my own paper. Let's start with my paper:

Scene Segmentation Using the Wisdom of Crowds
Ian Simon and Steven M. Seitz
There are many cues one could use when segmenting images, such as color, edges, recognizing objects, etc. Here we ignore all of these cues and segment 3D scenes based on the distribution of photos taken at the scenes (downloaded from Flickr). The basic idea is that people do not take photos simply by pointing the camera randomly, but take pictures "of" interesting objects. We effectively treat each photo as a vote that all of the scene points appearing in this photo belong to the same object. Of course, this is not precisely true for most photographs, but by combining information from multiple photographers, we can get accurate 3D segmentations.

Here are some other papers I liked:

Learning to Localize Objects with Structured Output Regression
Matthew B. Blaschko and Christoph H. Lampert
Object localization is usually done by training a classifier on positive and negative image regions, then running this classifier in sliding-window fashion on a new image. This paper proposes training directly for the localization task using a structured SVM.

Integration of Multiview Stereo and Silhouettes via Convex Functionals on Convex Domains
Kalin Kolev and Daniel Cremers
Several previous papers have tried to combine photoconsistency and silhouettes. The key insight here is a way to express silhouette constraints over a voxel grid in a way that yields a simple convex relaxation. There's no proof of a meaningful performance guarantee relative to the optimal solution of the discrete problem, but it's still cleaner than any of the other papers I've seen that address silhouettes in multiview stereo.

Image Segmentation by Branch-and-Mincut
Victor Lempitsky, Andrew Blake, and Carsten Rother
Suppose you're trying to segment a particular object with unknown pose in an image. For fixed pose, the problem can be solved with a graph cut. This paper describes a branch-and-bound search through a tree of hierarchically-clustered poses for the optimal pose and segmentation. The important observation is that a lower bound on the quality of the optimal solution in a particular subtree can be computed with a single graph cut.

What is a Good Image Segment? A Unified Approach to Segment Extraction
Shai Bagon, Oren Boiman, and Michal Irani
This paper proposes a simple criterion for segmentation: a segment should be easily composable using its own pieces, but difficult to compose from pieces outside the segment. The algorithm implied by this criterion sacrificies speediness for elegance, but I think there is value in figuring out the right thing to optimize, even if actually optimizing it proves impractical. Of course, it's not clear that composability is the right thing, and it would be interesting to compare against human segmentations.

Taleb's notebook

2008-11-07T16:51:00.000-08:00

Nassim Nicholas Taleb, author of The Black Swan and Fooled by Randomness, keeps a notebook on his site, in somewhat unfriendly HTML. Using a cool tool called Feed43 (after having failed with several other tools), I was able to extract an RSS feed for Taleb's notes. The feed is here:

http://feed43.com/7032722802218873.xml

Taleb is brilliant and very entertaining, but why oh why can't he use a standard blogging platform?

RIP 8aweek

2008-10-05T19:37:00.000-07:00

The only barrier between me and hours wasted browsing the likes of Digg, etc. has now been torn down. What self-control? The creators of 8aweek left a message on their home page (now completely gone) stating:

With the public launch of our new application Socialbrowse Zack and I no longer have the resources to support 8aweek.

Socialbrowse looks like a decent Web 2.0 app. It lives in your browser as a Firefox plugin and lets you leave comments on any web page, which are viewable to other users that have the plugin installed. Also, I am never, ever using it. I don't need social browsing, I need you to prevent me from doing too much social browsing.

I guess it's hard to make money blocking users from accessing ad-supported websites. So, 8aweek founders, I have an idea for you. 8aweek, when it existed (sniff), used to give me a fixed amount of time I was allowed to spend each day looking at crap, after which it would block me from accessing said crap. Put 8aweek back up (please?), but this time, get my credit card information, and charge me for each additional minute I spend looking at crap, warning me first of course.

I guarantee you this will make money, so you don't have to bother with all that boring Socialbrowse stuff.

whom to notify when you change your mailing address

2008-09-03T18:15:00.000-07:00

I recently moved to a new apartment, which involved notifying many, many organizations of my change of address. I'd be happiest if some website handled this for me, and updated my address everywhere, but in the meantime I created a list of organizations to notify in the hope that it will be useful to someone, perhaps the future me:

the USPS
your school/job
any banks at which you have an account
any investment management companies, like Vanguard
Amazon, eBay, PayPal, and any other sites that need your address
your cell phone provider
your cable and/or Internet provider
any insurance providers (car, health, etc.)
any credit card companies with whom you have an account
voter registration
vehicle and driver registration

Is there anything I missed? Also, does a list like this already exist anywhere? I couldn't find one...

"real-world" object recognition

2008-07-14T08:38:00.000-07:00

A paper from earlier this year (actual paper here) argues that Caltech 101 and similar benchmarks used to test object recognition systems fail to capture what is truly difficult about visual object recognition, and good performance can be achieved by local models with no explicit higher-level processing. This, the authors claim, is not because these models are actually effective, but because the datasets used contain very little "real-world" variation. For instance, in Caltech 101 the objects are centered, similarly oriented, mostly unoccluded and free from clutter, and are correlated with the image backgrounds.

Instead, the authors argue, we should use synthetic data sets where the amount of variation is controlled. They test their simple model on such a data set where object size, position, and orientation vary and find that as the variation increases, performance quickly degrades to no better than chance.

I think the paper raises an important point, in that we should take care that our datasets are capturing the essence of the problem to be solved. A few comments:

The problem of object recognition has multiple essences, and Caltech 101 captures some of them. Our "texture recognition as object recognition" models work pretty well because they do capture some of the appearance variation across different object instances, illumination, and very small changes in viewpoint.
It's not clear that a dataset in which objects have large amounts of variation in viewing angle better captures object recognition in the "real world". In particular, cars and airplanes, the two objects used in the synthetic dataset, are rarely viewed from some angles.
I would like to see how humans perform on the synthetic data set with lots of variation.

Incidentally, here's another argument from the paper about the standard recognition datasets:

The majority of images are also ‘‘composed’’ photographs, in that a human decided how the shot should be framed, and thus the placement of objects within the image is not random and the set may not properly reflect the variation found in the real world.

My ECCV 2008 paper uses this observation as a cue for segmenting 3D scenes into objects of interest using photographs from Flickr.

transformations between point sets with no correspondence

2008-07-05T18:46:00.000-07:00

Another problem that arises frequently in computer vision applications is finding a transformation that maps one set of points to another, where we have no information about point correspondences.

For instance, suppose I have a corner detector, and I want to align the set of detected corners to a floor plan, perhaps for an application like this one.

In addition, as will nearly always be the case, many of my detected corners are spurious. What I want to do is find a transformation that maps as many detected corners as possible to corners on the floor plan.

Unfortunately, even an extremely simplified version of this problem is thought to be hard, where hard means there is no solution better than quadratic. This implies that to find the exact solution, we will have to look at each pair of a detected corner and a floor plan corner.

Here's the simplified version: given two sets of numbers A and B, find the constant offset c that we can add to all elements of A to maximize the number of elements that A and B have in common. In other words, considering points in 1D, what is the translation that maximizes the number of correspondences?

It turns out that this problem is hard even if we are merely trying to detect whether or not there are two correspondences that agree on a translation. This is shown through a reduction to the 3SUM problem in this paper.

symmetric affine transformations

2008-06-30T17:34:00.000-07:00

A common task in computer vision problems is fitting an affine transformation to a set of point correspondences. The transformation is uniquely determined by 3 correspondences for 2D points or 4 correspondences for 3D points, and can be obtained by solving a linear system of equations.

Often, however, we have more correspondences. The usual solution is then to minimize the sum of squared distances between each point in one set and its transformed corresponding point in the other set. The problem with this approach is that you get different answers if the point sets trade roles. So, if we have point sets P and Q, the affine transformation A_PQ that transforms P to Q will in general not be the inverse of the affine transformation A_QP that transforms Q to P.

(Note that sometimes, this makes sense. If one of your point sets is a ground-truth "model" and the other is an "observation", it is reasonable to minimize the squared distances between observation points and transformed model points.)

Is there an alternative? There is, and it's based on a technique called total least squares. I'll write more about this later, but for now, here's some Matlab code that solves the problem for sets of 2D points:

function [a_pq,a_qp] = symmetric_affine(p,q)
% p and q are both 2-by-n matrices
% a_pq and a_qp will be 2-by-3 matrices

n = size(p,2);
x = [p; q];
c = mean(x,2);
x = x - c*ones(1,n);
[v d] = eigs(x*x',2,0);
a = [v; -c'*v]';

a_pq = [-a(:,[3 4])\a(:,[1 2 5])];
a_qp = [-a(:,[1 2])\a(:,[3 4 5])];

movie poster quiz

2008-06-25T12:04:00.000-07:00

What do I hate about the following two movie posters?

It might be difficult to fix in the first one, but it would be really easy to fix in the second one.

subscription math

2008-06-11T10:17:00.000-07:00

Ramit Sethi suggests cancelling all your subscriptions and paying for items à la carte to save money. Without considering whether or not this is a good idea in reality, my first thought was, "can we turn this into a cool math problem?".

Using movies as an example, let's assume that you will rent x_i dollars of movies during month i. Before the month, you can choose to either pay x_i (whatever it turns out to be), or pay a c dollar subscription fee to Netflix. Though this is obviously not true in reality, just for simplicity let's assume that whether or not you've subscribed doesn't affect how many movies you will watch that month. So I won't watch more movies just because I subscribed to Netflix.

Now, there is some optimal strategy that, before each month, psychically knows how many movies you're going to watch, and if their total cost is above c, subscribes for the month, otherwise pays à la carte. Of course, you can't use this strategy, because you aren't psychic.

Two questions, nonexistent readers. First, is there any other strategy that we can make any claims about? For instance, is there a strategy that will never pay more than twice what the optimal strategy pays in the long run? I'm pretty certain there is not, since an evil god could make you watch nothing every time you subscribe and $1,000,000 worth of movies every time you don't.

Second, can we add any additional elements to make the problem more interesting, where some strategy is competitive with the optimal one? What if you have to pay a fee every time you switch from subscription to nonsubscription or vice versa? What if the x_i come from a normal distribution?

excellent analogy by Marc Davis

2008-06-04T23:05:00.000-07:00

Marc Davis of Yahoo Research gave an excellent talk at UW today on mobile phones and social media. During the talk, he gave the following analogy (paraphrased):

You are at a bar.
You get drunk.
You get even more drunk.
Someone hits you in the back of the head and you go unconscious.
While you're out cold, they take you to the airport and fly you to another country.
They drive you to an unknown location and leave you lying in the street.
You wake up and open your eyes.

That's what it's like to be a computer vision system.

The lesson, of course, is that context from our lifestream is incredibly useful for solving problems that are not easily tackled by vision alone.

using Intrade for news

2008-06-04T09:47:00.000-07:00

I find it is enlightening to fact-check the reported news against reality, and I find that Intrade is a good surrogate for reality.

So here's my Intrade observation of the moment: although Clinton has not yet dropped out of the Democratic race, right now Obama has the same probability of being the Democratic nominee as McCain has of being the Republican one (95%).

productivity wars

2008-04-27T20:33:00.000-07:00

As someone who wastes a lot of time reading lists of ways to be more productive, I notice two pieces of advice that show up frequently (paraphrased):

If someone else asks you to do something for them, say no.
Ask other people to do things for you.

Sometimes both even show up in one list. I guess a good way to increase your productivity is by decreasing the productivity of others.

practice

2008-04-26T15:49:00.000-07:00

If you're reading this, I'm surprised. The main purpose of this blog is to get me some writing practice. I haven't told anyone about the blog and as far as I know, no one reads it. This is partially why I was willing to use such a silly title.

All that said, for anyone who somehow stumbles upon this blog, if you want to leave me a comment telling me I suck, I will be thrilled, especially if you also tell me how to suck less.

microscience

2008-04-25T17:49:00.000-07:00

The word "microscience" may already mean something else, but this post is about an idea that should steal the term away.

One difference between scientists and non-scientists is that scientists tend to have more experience and skill at testing hypotheses and conducting experiments in a particular area of expertise. However, non-scientists (and scientists in other areas) also benefit from the results of these experiments. In addition, individual non-scientists may have specific questions they'd like answered for which scientists have not yet conducted any experiments.

The problem, if you want to call it that, is that scientists tend to study things that make sense for them career-wise. Often this means making a little bit of progress on an important existing problem, other times spending some effort carving out a new area, either way it is something that will further their careers as scientists. I hope I'm not sounding too cynical here, Robin Hanson seems to agree. This isn't unreasonable, as scientists are motivated by long-term incentives such as tenure and multi-year grants. For the overall progress of science, this is probably a good thing, but it potentially leaves smaller questions unanswered, even if knowing the answers to these questions would be valuable to some individuals. Questions that have little potential of leading to other interesting scientific questions are likely ignored. (This itself is a hypothesis I would like tested.)

I would like to see something I'm calling "microscience", where individuals post hypotheses and freelance scientists bid on testing the hypotheses through experiment. The experiments might be things that can be completed in anywhere from a few days to a few months, but fall outside the realm of current NSF funding practices.

And no, I have no idea if this kind of thing would really work for science.

In-N-Out

2008-03-31T13:12:00.000-07:00

So I finally, after 29 years of existence, got a chance to eat at the much-hyped In-N-Out Burger chain, and I have to say, I was pretty disappointed. People in California talk about this place as if Jesus himself returned to Earth and started a burger chain. This view seems to be corroborated by the quotes on some of the utensils. It just didn't do it for me, though. I got the same kind of greasy burger you can get at any fast food joint, and In-N-Out has an extremely limited set of ingredients (no bacon, no mushrooms, and no cheese except American).

My guess is that some of the hype originates from the existence of secret menu items, which lets select patrons feel as though they belong to an exclusive club of people who know the code name for each subset of the 5 ingredients In-N-Out carries. It's the same phenomenon as knowing the correct grammar for constructing Starbucks drink names. (I'm pretty sure it's a regular grammar.) Anyway, I'd be much more likely to go back to In-N-Out if someone tells me the secret word for "not drowning in grease".

keeping myself organized

2008-03-08T21:32:00.001-08:00

I'm supposed to be working on my ECCV paper right now, but I decided to procrastinate by streamlining my eLife. It's pretty surprising how many cool Web 2.0 tools there are for keeping yourself organized. With each new tool I discovered, I would usually think "great, now if only I could also x", and almost every time, with a little bit of searching, I managed to find another tool that accomplishes exactly x.

Here are some things that absolutely everyone should do:

Use an RSS reader. Hopefully you already do this. You should not be checking and re-checking dozens of sites for updates. I use Google Reader, but there are plenty of others. There are some slightly less obvious uses of RSS too. For instance, if you find yourself repeatedly searching Craigslist for something, you can subscribe to the search as an RSS feed instead.
Do not subscribe directly to RSS feeds that have hundreds of items each week (Digg, TechCrunch, etc.). This, as they say, is like drinking from a firehose. If you are checking these sites for articles on a particular topic, use FeedRinse to filter the RSS feeds using keywords. Otherwise, use AideRSS to filter out the less important items from each feed. AideRSS appears to use a ranking algorithm similar to Google's PageRank to measure quality.
Use some kind of calendar application. I recommend an online one like Google Calendar, as I use different computers in different locations. With Google Calendar, you can add events by entering text like "meet with Xander at 3 PM on Tuesday" into a field, and this event will be added to your calendar, even if you don't know anyone named Xander. Even nicer is that several sites, like TripIt, communicate directly with your Google Calendar, so you can keep all of your scheduled events in one place without even entering many of them manually.
Collect data on yourself. You need to know how you are spending your time and money. RescueTime is pretty good for the former, and Mint is good for the latter. Both of these require virtually zero data entry on your part. Actually, here's a tool I would like but was unable to find: something that punishes you for wasting time or money, or rewards you for being good. The website stickK is sort of close to this, but requires too much manual effort.

And because no such tool exists, I am writing this blog entry instead of my ECCV paper. Oh well, at least I'm producing something instead of consuming, even if it is of little value.

MySong

2008-03-03T17:15:00.000-08:00

MySong, a project I worked on last summer with Dan Morris and Sumit Basu of Microsoft Research, seems to be hitting the blogs:

http://www.boingboing.net/2008/03/03/microsoft-researchs.html

I'm a bit surprised at the negativity of some of the commenters. Remember: this isn't supposed to be the ultimate solution to music composition. The chord progression model is pretty simple and the synthesis (at least without Band-in-a-Box) is just a Let It Be pattern. What MySong does do, however, is let people who have no idea how music "works" play with basic composition. I know a fair amount of music theory and still had tons of fun singing into MySong and messing with the chords that came out. In fact, I spent more time doing that than actually working on the code (but don't tell anyone that).

medoids

2008-02-28T10:40:00.000-08:00

Suppose I have a set of points. The mean of this set of points is the point (not necessarily in the set) which minimizes the sum of its squared distances to all the points in the set. A related concept is the medoid, which is like the mean but is restricted to being one of the points in the set.

Interesting fact: the sum of squared distances from the medoid to all points in the set cannot be more than twice the sum of squared distances from the mean to all points in the set.

This imples that for the k-medoids problem, if you have an algorithm that achieves some constant times the optimal solution cost, this same algorithm also achieves a constant factor approximation for the k-means problem.

Again, this is probably trivial if you're a theory person, but I think it's fun.

double triangle inequality

2008-02-26T22:34:00.000-08:00

The triangle inequality is one of the properties of a distance metric d. It states that, for any x, y, and z:

d(x,y) + d(y,z) ≥ d(x,z)

A somewhat lesser-known (but easy to derive) extension of this is the double triangle inequality for squared distances:

2(d²(x,y) + d²(y,z)) ≥ d²(x,z)

I have never seen the double triangle inequality used for anything. However, I would think it would be useful, given the prevalence of squared distances in objective functions. The k-means objective, for instance, is to minimize a sum of squared distances. For problems in which the objective function involves non-squared distances, the ordinary triangle inequality is often used to prove bounds on an algorithm's performance. I'm not sure why I haven't seen similar things with the double triangle inequality and squared distances.

Also, I should point out that I'm not really a theory person, so my not having seen something provides very little evidence for the nonexistence of said thing.