automatic rebalancing through automatic exchange

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

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:

1. Graduate.
2. 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.
3. Work out the details of my convex formulation of visibility constraints in multiview stereo and write a paper on this.
4. Start training MMA, probably here.
   

lyrics quiz

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

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

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

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

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

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:

1. 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.
   
2. 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.
   
3. 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

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

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

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

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

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

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

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):

1. If someone else asks you to do something for them, say no.
2. 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

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

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

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

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:

1. 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.
   
2. 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.
   
3. 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.
   
4. 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

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

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

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.