How to represent large irregular graphsIn some problems, you have a large set of interacting entities, where the interactions are irregular. This interaction graph can be represented efficiently in Infer.NET by making use of the ability to index arrays by observed variables.
For illustration, let's consider the problem of inferring the skill levels of players given a set of game outcomes. Suppose there are 4 players (numbered 0,1,2,3) and the game outcomes are:
The outcomes define a graph of interactions amongst the player performances. That is, we know that in game 0, player 2 performed better than player 0. To get the skill of each player, we assume that his performance was Gaussian-distributed around his skill. The constraints on the performances then gives information about the skills. (This is the model used by Microsoft TrueSkill.) We will consider two different ways of writing this model in Infer.NET. The first uses a separate Variable object for each player. The second uses a VariableArray of players, and runs much faster.
Big, slow model: A variable for each player
An explicit encoding of the game outcomes into an Infer.NET model would be as follows. The game outcomes are represented by two arrays, giving the index of the player that won or lost:
We create a C# array holding a Variable object for each player's skill:
Now each game outcome can be written as a constraint between the winning and losing performance, like so:
When run, this code prints out:
As expected, player 3 is inferred to have the highest skill.
We call this approach 'unrolling the graph', similar to unrolling a loop in C#. In this approach, the structure of the game graph is baked into the model definition, allowing a specialized inference schedule to be computed. However, if there are many players or games, a large amount of code will be generated, making Infer.NET run slowly. (See the Learning a Gaussian tutorial for a simple example of this.) Furthermore, unrolling prevents the game graph from changing at runtime.
Small, fast model: Indexing a VariableArray
Indexing a VariableArray provides both a more efficient model definition and the ability to change the game graph at runtime. The idea is to represent the player variables with VariableArrays:
The game outcomes are copied into two VariableArrays, giving the index of the player that won or lost:
Note these variables can be set and changed at any time, even after the model
For each game, we want to make a constraint that the winner had a better performance than the loser. This is accomplished with similar code as before, but excluding the C# loop (the constraint is automatically applied across all games):
Finally, we infer the entire array of player skills:
The result is:
At this point, you can change the observed values of the winner and loser arrays and get new results quickly.