The Netflix $1M collaborative filtering competition has ended with an outcome that is doubly-interesting. First, there was a nice “photo-finish” with two separate groups passing the prize-winning mark and with the winner not yet announced. More interesting is the fact that both contenders at this point are rather large coalitions each composed of several groups who were previously separately competing. In fact, once the first such coalition passed the prize-wining mark, the second coalition formed, combined forces, and reached first place within the 30 days mandated by the rules.
Many have written about the significance of the fact that it is not one “magic bullet” that lets you win such a competition but rather the combination of many “small” ideas and much work. What I am intrigued by is how such a fruitful combination of separately written pieces of software happens. In the case of the first group, who have been working together for a while, one might take the point of view that it is just the usual miracle seen in any large software effort (open source or not) where a sound software architecture with well-defined interfaces lets many people contribute to a project. (Just like Linux or Google Search keep getting better by the combined efforts of many programmers.) However, in case of the second group, there seems to be something more interesting going on in the sense that the pieces were joined ex-post, seemingly with a very simple combination architecture. How can this be done? Can it be done for other challenges as well? (A competition to beat Google search?) Can competitions be designed with collaboration built in? (Maybe the second Netfilx competition?)
Let us look at an easy example for simple software collaboration: optimization given a set of constraints (such as Integer programming). Here the input consists of a set of constraints on n variables, as well as an optimization goal defined on these variables. The output should be an assignment of values to the variables that satisfies the constraints and with as high as possible a value for the optimization goal. The nice thing about such problems is that collaboration is essentially built in by the problem definition. Once clear input and output formats are defined, combining several optimizers is easy: just run all of them on the input instance, and output the best assignment returned by any of the component optimizers. If the total measure of success of an algorithm is the average (say) value of the returned assignment over some distribution of problem instances, then the collaborative optimizer is certainly at least as good as any single component used, and if the different components used have distinct “strengths” then the collaborative optimizer is actually better than any single one. This architecture naturally supports specialization: each optimizer focuses on some subset of instances and tries to do as good a job as possible on it, leaving other inputs for other optimization efforts.
Now back to Netflix-like machine learning challenges where the optimization goal is to produce a single predictor p that agrees as much as possible with the given target function t. The natural ML tendencies would be, I suppose, to combine different p‘s using some kind of weighted voting or averaging, as indeed the second team seems to have done according to the Wired blog post:
To combine competitors’ algorithms, The Ensemble didn’t have to cut and paste much code together. Instead, they simply ran hundreds of algorithms from their 30-plus members (updated) and combined their results into a single set, using a variation of weighted averaging that favored the more accurate algorithms.
Thus the collaboration architecture is not different from the problem statement with the addition of a module that chooses the best weights for averaging. When the aim is to minimize the sum-squares error, as was the case in the Netflix challenge, then the best coefficients for weighting the average can be efficiently obtained by linear regression which should be doable with these data set sizes (I think).
I can see many interesting theoretical and practical research issues in generalizing the scope of collaboration:
- How can we easily allow more sophisticated combinations? E.g. a component that specializes in figuring out “who to ask” among other algorithms? Or branch-n-bound algorithms that use partial results from other optimizers to control branching? In the Netflix case, one researcher found a way to take temporal dynamics into consideration — can this be effortlessly used as a subroutine in other components? What kind of meta-data will be useful here?
- Can we get Organic-like growth with sub-algorithms constantly being added that utilize and then improve the previous state of affairs? How do we best mimic natural-selection? How do we avoid evolutionary dead-ends?
- How do we incentivize partial algorithms? How do we determine the contribution of a single component relative to others? I can immediately think of two types of models here: one based on a cooperative games formalism where for each subset S of components we have the value v(S) that its combination can bring, and another taking a sequential approach where each contribution gets credited according to the marginal improvement that it brings relative to the previous combination. This is somewhat like an intellectual property model when the first one to come up with an idea gets the credit for it, but then others can build upon it — a model that presumably encourages rapid progress.
- What if we don’t have resources (say CPU time) to run all components, how do we choose which to use? Obviously we want to take their cost-performance trade off into account. Can we have components that specialize in such resource allocation?
and then the players somehow interact until they find an equilibrium of the game 
defined by their joint utilities. The analysis here abstracts away the different incentives of the players (the usual focus of attention in game theory) and is only concerned with the amount of information transfer required between the players. I.e., we treat this as a purely distributed computation question where the input 
is distributed between the players who all just want to jointly compute an equilibrium point. We assume perfect cooperation and prior coordination between the players, i.e. that all follow a predetermined protocol that was devised to compute the required output with minimum amount of communication. The advantage of this model is that it provides lower bounds for all sorts of processes and dynamics and that eventually should reach equilibria: if even under perfect cooperation much communication is required for reaching equilibrium, then certainly whatever individual strategy each player follows, convergence to equilibrium cannot happen quickly.
players, where each player 
holds part of the input which we assume is an 
-bit string, 
. The usual focus is on the two-player case, 
, in which case we simplify the notation to use 
and 
rather than 
and 
. The joint goal of these players is to compute the value of 
where 
is some predetermined function. As 
, the players will need to communicate with each other in order to do so (we will use “broadcasting” rather than player-to-player channels), and they will do so according to a predetermined protocol. Such a protocol specifies when each of them speaks and what he says, where the main point is that each player’s behavior must be a function of his own input as well as what was broadcast so far. We will assume that all communication is in bits (any finite alphabet can be represented in bits). The communication complexity of 
is the minimum amount of bits of communication that a protocol for 
and Bob holds 
. They need to determine whether there exists an index 
. If we view 
and 
, then we are asking whether 
.
lower bound also applies to randomized protocols, but the proof for the randomized case is harder, while the proof for the deterministic case is easy.
different input pairs of the form 
(these are the “maximal disjoint” inputs). We will show that for no two of these input pairs can the protocol produce the same communication transcript (i.e. the exact same sequence of bits is sent throughout the protocol). It follows that the protocol must have at least 
and 
have the same transcript? Had we been in a situation that 
then we would know that the transcripts must be different since the protocol must output a different answer in the two cases; however in our case all “maximal disjoint” input pairs give the same answer: “disjoint”. We use the structure of communication protocols — that each player’s actions can only depend on his own input (and on the communication so far) — to show that if 
has the same transcript too (and so does 
). Consider the players communicating on inputs 
cannot distinguish it from the case 
and 
there must be an index 
. If 
and 
then 
and 
in which case 
and 
then 
and 
in which case 
, where the 
‘s are the commonly known strategy sets, which we will assume have size 
each. Thus each player’s input consists of 
real numbers, which we will always assume are in some small integer range. Perhaps it is best to start with a non-trivial (just) upper bound. Let us consider the class of games that are (strictly) dominance solvable, i.e. those that 
times:
do
numbers for each player. Can some protocol like this be designed for all games that have a pure Nash equilibrium? The basic answer in no:
bits of communication.
.
. The idea is very simple: Alice will build a utility matrix 
by filling it with the values of its bit string 
from 
will turn out to be a Nash equilibrium since both players get the highest utility possible in this matrix. For this idea to formally work, we just need to make sure that no other cell is a Nash equilibrium. This can be done in one of several ways (and different ones are used in the C&S and H&M papers), the simplest of which is adding two more rows and columns as follows:
players that have utilities that are identically 0. Thus any strategy will be a best reply for these new players, and a pure Nash equilibrium is determined solely by Alice and Bob. The main change that the new players bring is that the utility functions of Alice and Bob are now 
-bit long vectors.
. (Exercise: show that the randomized communication complexity in this case is 
.) As 
lower bound for constant 
is 
, where the point is that it’s wasteful to copy the integer parts when you’re doing the common denominator.)
Turing's Invisible Hand 