Support for estimation of point mass parameters using rprop

[jamesdsmith99]

After reading the trueskill 2 paper, I was wondering if there is any support for this in the library. It is not clear what data structure I would need to accumilate the messages passed to the parameter.

I see there is a Class PointMass<T> to which I could assign an initial value for this parameter. I also see there is a bunch of classes relating to RProp. Is there any examples on how to tie this together to form a training loop for a simple model?

[tminka]

There is no example in the documentation, but you can refer to issue #226

[jamesdsmith99]

Thanks @tminka. The referenced issue makes it clear how to create and infer point estimates. Did you have any recommendations for how infer this parameter given the temporal dependencies between games. TrueSkill is traditionally an online method that takes a prior on a player's skill to be the inferred skill from the previous game, but when trying to learn the parameters for TrueSkill v2, it seems like the parameter must be inferred using 1 call to the inference engine.

So to clarify, for learning the parameters from previous data one must create a large factor graph for all games where the skill variables are connected to their corresponding prior factors in the next game similar to TrueSkill TT. Then once this parameter is inferred, its value can be assigned in the online model.

Doing this doesnt seem right because the value of the parameter will be estimated given the information being passed backwards from the future, whereas with online learning there is no information passed backward from the future. Is my understanding wrong or is this just a known limitation of inferring the parameter this way?

Though this doesnt seem right, it seems more correct than trying to infer this parameter by performing inference in a loop.

[tminka]

Your understanding is correct, but I don't see why you think it is a limitation. If the parameter is assumed to be unchanging over time, then I don't see any problem with using a batch of data to estimate it.

[jamesdsmith99]

But the online model and the 'TSTT style' model are different in terms of how information is propogated. So it's almost like the parameter we take to use in the online model was obtained from optimization of a parameter of a different model, which seems strange.

Though i suppose the difference between these two models must be negligable and the parameter produced is still good for the online model.

[tminka]

The online and batch models are not different models. They are different ways of performing inference in the same model.

[jamesdsmith99]

Yeah to say they are different models is imprecise, but in the batch model results of future games can influence the inferred skills of players in previous games. In the online model this flow backwards cant happen. Surley this would effect the value assigned to the parameter, if only a very little amount?

[tminka]

When you say it "would affect the value assigned to the parameter", you are implicitly saying that the models are different. Once you understand that the models are the same, the true parameter value must be the same.

[jamesdsmith99]

Ah, that makes sense. If we were to estimate this parameter using an online methos we would get a less accurate estimation of this true parameter. So performing this inference of the parameter in the differenat way is, actually, kind of like an opposite of a limitation.

Do you have any rough idea on how performance in terms of memory and compilation time should scale for this. I have a dataset of ~6k FFA games with 8-12 players in each.

I implemented this over the weekend, when running on 500 games compilation took nearly an hour on an AMD ryzen 5,then when trying to run on 750 games, I ran out of memory (>32gb). This seems like an excessive amount of resource usage, as the paper sates that this model was trained on ~23 million games.

My implementation might be rather naieve (creating many instances of the online model passing the parameter variable into the constructor). But I am unsure how to make this more efficient. I originally thought that repeat blocks would work but they seem to be for single variables rther than subgraphs. Is there any structure in infer.NET that could allow for each game subgraph to be repeated in an efficient way?

My naieve implementation was originally made by following the mbml book:

class TrueSkillGame
    {
        public Variable<int> PlayersInGame { get; }
        public VariableArray<Gaussian> SkillPriors { get; }
        public VariableArray<double> Skills { get; }
        public VariableArray<double> Performances { get; }
        public VariableArray<double> Scores { get; }

        public VariableArray<double> Biases { get; }
        public TrueSkillGame(
            string gameId,
            Variable<double> biasCoefficient,
            double dynamicsVariance,
            double performanceVariance,
            double drawMargin)
        {
            PlayersInGame = Variable.New<int>().Named($"PlayersInGame-{gameId}").Attrib(new DoNotInfer());

            Range player = new(PlayersInGame);

            SkillPriors = Variable.Array<Gaussian>(player).Named($"SkillPriors-{gameId}").Attrib(new DoNotInfer());
            Skills = Variable.Array<double>(player).Named($"Skills-{gameId}").Attrib(new DoNotInfer());
            Skills[player] = Variable.GaussianFromMeanAndVariance(Variable<double>.Random(SkillPriors[player]), dynamicsVariance);

            Performances = Variable.Array<double>(player).Named($"performances-{gameId}").Attrib(new DoNotInfer());

            Scores = Variable.Array<double>(player).Named($"Scores-{gameId}").Attrib(new DoNotInfer());

            Biases = Variable.Array<double>(player).Named($"Biases-{gameId}").Attrib(new DoNotInfer());
            Biases[player] = Variable.GaussianFromMeanAndVariance(0, 1).ForEach(player);

            using (var p = Variable.ForEach(player))
            {
                Performances[player] = Variable.GaussianFromMeanAndVariance(Skills[player] + biasCoefficient * Biases[player], performanceVariance);

                using (Variable.If(p.Index > 0))
                {
                    var diff = (Performances[p.Index - 1] - Performances[p.Index]).Named($"diff-{gameId}");

                    using (Variable.If(Scores[p.Index - 1] == Scores[p.Index]))
                    {
                        Variable.ConstrainBetween(diff, -drawMargin, drawMargin);
                    }

                    using (Variable.IfNot(Scores[p.Index - 1] == Scores[p.Index]))
                    {
                        Variable.ConstrainTrue(diff > drawMargin);
                    }
                }
            }
        }

        public void ObserveData(int numPlayers, Gaussian[] skillPriors, double[] scores, double[] biases)
        {
            PlayersInGame.ObservedValue = numPlayers;
            SkillPriors.ObservedValue = skillPriors;
            Scores.ObservedValue = scores;
            Biases.ObservedValue = biases;
        }
    }

class TrueSkillBatch
    {
        private DefaultDict<string, Gaussian> PlayerSkills;
        public Variable<double> BiasCoefficient { get; }
        ...
        public TrueSkillBatch(Dataset games)
        {
            BiasCoefficient = Variable.GaussianFromMeanAndVariance(0, 1).Named("Bias Coefficient");
            BiasCoefficient.AddAttribute(new PointEstimate());

            PlayerSkills = new(() => Gaussian.FromMeanAndVariance(0, INITIAL_SIGMA)); // class that behaves like python's defaultdict

            ...

            foreach (var game in games)
                CreateTrueSkillGame(game)
        }

        private TrueSkillGame CreateGame(GameInfo game)
        {
            ...

            TrueSkillGame game = new(gameId, BiasCoefficient, INITIAL_SIGMA / 100, 4.1666666666, 0.1);
            game.ObserveData(scores.Count, skillPriors, scores.ToArray(), biases.ToArray());
            return game;
        }
    }

[tminka]

See How to represent large irregular graphs and Chess Analysis.

[jamesdsmith99]

Ah so do the same thing that was done for the number of players, for the number of games. At first glance i believe i will need a jagged array for this implementation. I will implement this and check the performance. Thanks for the pointers 👍.

[jamesdsmith99]

So I used jagged array to represent the player's skills etc. Then had 2 other jagged arrays of ints that map to the index of a players last skill variable. I used an observed index of -1 as a value to indicate the base case where a player has not participated in a game before.

class TrueSkillV2Batch
    {
        public Variable<int> NGames { get; }
        public VariableArray<int> PlayersInGames { get; }
        public VariableArray<VariableArray<int>, int[][]> PrevGameIndices { get; }
        public VariableArray<VariableArray<int>, int[][]> PrevGamePlayerIndices { get; }
        public VariableArray<VariableArray<double>, double[][]> Skills { get; }
        public VariableArray<VariableArray<double>, double[][]> Performances { get; }
        public VariableArray<VariableArray<double>, double[][]> Scores { get; }

        public VariableArray<VariableArray<double>, double[][]> Biases { get; }
        public Variable<double> BiasCoefficient { get; }
        private readonly double InitialSigma;

        public TrueSkillV2Batch(double dynamicsVariance, double performanceVariance, double drawMargin, double initialSigma)
        {
            InitialSigma = initialSigma;
            NGames = Variable.New<int>();
            Range game = new(NGames);
            PlayersInGames = Variable.Array<int>(game);

            Range gamePlayer = new(PlayersInGames[game]);

            PrevGameIndices = Variable.Array(Variable.Array<int>(gamePlayer), game).Named("Previous Game Indices").Attrib(new DoNotInfer());
            PrevGamePlayerIndices = Variable.Array(Variable.Array<int>(gamePlayer), game).Named("Previous Game Player Indices").Attrib(new DoNotInfer());
            Skills = Variable.Array(Variable.Array<double>(gamePlayer), game).Named("Skills").Attrib(new DoNotInfer());

            Performances = Variable.Array(Variable.Array<double>(gamePlayer), game).Named("Performances").Attrib(new DoNotInfer());
            Scores = Variable.Array(Variable.Array<double>(gamePlayer), game).Named("Scores").Attrib(new DoNotInfer());

            Biases = Variable.Array(Variable.Array<double>(gamePlayer), game).Named("Biases").Attrib(new DoNotInfer());
            Biases[game][gamePlayer] = Variable.GaussianFromMeanAndVariance(0, 1).ForEach(game, gamePlayer);

            BiasCoefficient = Variable.GaussianFromMeanAndVariance(0, 1).Named("Bias Coefficient").Attrib(new PointEstimate());

            using (Variable.ForEach(game))
            {
                using (var p = Variable.ForEach(gamePlayer))
                {
                    var playersFirstGame = PrevGameIndices[game][gamePlayer] < 0;
                    using (Variable.If(playersFirstGame))
                    {
                        Skills[game][gamePlayer] = Variable.GaussianFromMeanAndVariance(0, InitialSigma);
                    }

                    using (Variable.IfNot(playersFirstGame))
                    {
                        var prevGame = Variable.Min(PrevGameIndices[game][gamePlayer], 0);
                        var prevGamePlayerIndex = Variable.Min(PrevGamePlayerIndices[game][gamePlayer], 0);
                        Skills[game][gamePlayer] = Variable.GaussianFromMeanAndVariance(
                            Skills[prevGame][prevGamePlayerIndex],
                            dynamicsVariance
                        ); 
                    }

                    Performances[game][gamePlayer] = Variable.GaussianFromMeanAndVariance(Skills[game][gamePlayer] + BiasCoefficient * Biases[game][gamePlayer], performanceVariance);

                    using (Variable.If(p.Index > 0))
                    {
                        var diff = (Performances[game][p.Index - 1] - Performances[game][p.Index]).Named("diff");

                        using (Variable.If(Scores[game][p.Index - 1] == Scores[game][p.Index]))
                        {
                            Variable.ConstrainBetween(diff, -drawMargin, drawMargin);
                        }

                        using (Variable.IfNot(Scores[game][p.Index - 1] == Scores[game][p.Index]))
                        {
                            Variable.ConstrainTrue(diff > drawMargin);
                        }
                    }
                }
            }
        }

Originally, the -1 values were throwing an IndexOutOfRangeException (during inference not compilation) so to fix this i just set the index to 0 in the block that represents the recurrance. var prevGame = Variable.Min(PrevGameIndices[game][gamePlayer], 0); Though this solution seems rather hacky.

I'm not sure why the IndexOutOfRangeException is thrown because when one of the indices are -1 the base case block should be active and not the recurrance block (i have verified that when PrevGamePlayerIndices is never < 0 when PrevGameIndices is > -1). In the first code example of this page in one of the if blocks an index evaluates to -1 but no such exception is thrown. The only thing that is different in this case is that the array is 2D so i am not sure if there is some extra precaution I am not taking.

In terms of performance, this hacky implementation compiles very quickly, but inference on 1k games takes 14Gb of RAM. Is this inline with expectations of infer.NET or can performance still be somehow improved?

[jamesdsmith99]

@tminka is there something I am missing here? I am able to run parameter estimation for 1.6k games before running into memory issues on my 32gb machine.

I have spent the last week trying to find ways to get rid of that Min factor to try and make the specification of the model more efficient but im having no luck.

Is this level of memory scaling what you would expect for this libary? It seems to me like this should scale better but I am unsure.

[tminka]

The large memory usage is due to the Min factor. The Min factor doesn't make sense to me because it should always return 0. After removing the Min factor, you can avoid the exception by using zero instead of -1 and letting another variable determine playersFirstGame.

[jamesdsmith99]

@tminka I find it ironic how my attempt to make this model take less memory by using -1 instead of creating another 2D array of booleans caused the memory usage of this model to blow up 😂.

[tminka]

In #376 the model compiler will now give an "excess memory usage" warning for the code above, with the offending expression.