#r "nuget: MathNet.Numerics"Installed Packages
- MathNet.Numerics, 5.0.0
Infer-8b-TrueSkill-Formules-Fermees : la mise a jour O(1) de Herbrich-Minka-Graepel
Serie : Programmation Probabiliste avec Infer.NET (8b/19)
Duree estimee : 20 minutes
Prerequis : Infer-8-TrueSkill
Objectifs
- Deriver les fonctions de troncature V(t) et W(t) (cas a 2 joueurs)
- Implementer la mise a jour closed-form de TrueSkill – O(1) par match
- Verifier numeriquement la coherence exacte avec le moteur EP d’Infer.NET
- Comprendre le terme de dynamique tau^2 (equilibre contraction / regrowth)
Sources et références canoniques
- TrueSkill — Herbrich, R., Minka, T. & Graepel, T. (2007). TrueSkill(TM): A Bayesian Skill Rating System. NeurIPS 2007, Microsoft Research Cambridge. La matière première de cette lettre : les formes fermées V(t), W(t) de la mise à jour à 2 joueurs.
1. La vraie contribution algorithmique du papier TrueSkill
Tout au long d’Infer-8-TrueSkill, nous avons laissé le moteur d’Expectation Propagation (EP) d’Infer.NET calculer les postérieurs des skills. C’est rigoureux, mais cela masque la vraie contribution algorithmique du papier TrueSkill : dans le cas à 2 joueurs, la mise à jour admet une forme fermée exacte — O(1) par match, sans aucune inférence itérative. C’est ce qui rend TrueSkill déployable en production sur des millions de joueurs (Xbox Live), où relancer EP à chaque match serait prohibitif.
Source primaire : Herbrich, Minka & Graepel (2007), TrueSkill(TM): A Bayesian Skill Rating System (NeurIPS / Microsoft Research Cambridge). Le jumeau PyMC-08-TrueSkill expose la même dérivation (section 7 bis).
Le problème : une vraisemblance « inégale » non-Gaussienne
La contrainte \(\text{perf}_w > \text{perf}_l\) est une inégalité : le postérieur qu’elle induit est une Gaussienne tronquée, donc non-Gaussien. Or on veut maintenir chaque skill comme une Gaussienne \(\mathcal{N}(\mu, \sigma^2)\) (pour le réinjecter comme prior au match suivant). EP résout cela en projetant le postérieur tronqué sur la meilleure Gaussienne approximante (moment matching sur le graphe de facteurs).
La mise à jour closed-form à 2 joueurs (fonctions de troncature V, W)
Après convergence d’EP sur le facteur « gagnant/perdant », la mise à jour se ramène à deux fonctions auxiliaires — troncatures de la Gaussienne centrée réduite :
\[c = \sqrt{2\beta^2 + \sigma_w^2 + \sigma_l^2}, \qquad t = \frac{\mu_w - \mu_l}{c}\]
\[V(t) = \frac{\mathcal{N}(t;\,0,1)}{\Phi(t)}, \qquad W(t) = V(t)\big(V(t) + t\big)\]
où \(\mathcal{N}\) est la densité et \(\Phi\) la CDF de la Gaussienne centrée réduite. Les mises à jour du gagnant (\(w\)) et du perdant (\(l\)) deviennent alors :
\[\mu_w' = \mu_w + \frac{\sigma_w^2}{c}\,V(t), \qquad \mu_l' = \mu_l - \frac{\sigma_l^2}{c}\,V(t)\]
\[(\sigma_w^2)' = \sigma_w^2\!\left(1 - \frac{\sigma_w^2}{c^2}\,W(t)\right), \qquad (\sigma_l^2)' = \sigma_l^2\!\left(1 - \frac{\sigma_l^2}{c^2}\,W(t)\right)\]
Détail subtil : la variance se contracte du facteur \(\frac{\sigma^2}{c^2}\,W(t)\), et non de \(W(t)\) seul. Le ratio \(\sigma^2/c^2\) borne la contraction : un prior très confiant (\(\sigma^2 \ll c^2\)) ne peut guère se resserrer davantage.
Interprétation : \(V(t)\) mesure à quel point le match a été informatif. Un match équilibré (\(t \approx 0\)) instruit beaucoup (\(V(0) \approx 0{,}80\)) ; une victoire attendue (\(t \gg 0\)) instruit peu. La variance se contracte en proportion.
La dynamique entre les matchs : le terme \(\tau^2\)
En production, TrueSkill ajoute du bruit au skill avant chaque match : \(\sigma^2 \leftarrow \sigma^2 + \tau^2\). L’incertitude ne décroît donc pas indéfiniment — elle atteint un équilibre entre la contraction (information du match) et la régrowth (\(\tau^2\)). Un joueur inactif voit son incertitude augmenter, ce qui justifie de repondérer rapidement ses premiers matchs de retour (extension dynamique d’Infer-8, section 5).
// Demonstration numerique : la mise a jour closed-form EP (V(t), W(t)) que le moteur
// Infer.NET d'Infer-8 (sections 3-9) calcule sous le capot. Ecrite ici "a la main" (forme fermee
// de Herbrich-Minka-Graepel, NeurIPS 2007) pour verifier la coherence avec Infer.NET.
using MathNet.Numerics.Distributions;
using System;
// Memes parametres qu'a l'initialisation (Infer-8, section 3) : mu=25, sigma=25/3, beta=sigma/2
double muW = 25.0, muL = 25.0; // match entre deux joueurs de skill identique (priors egaux)
double sigW = 25.0/3.0, sigL = 25.0/3.0; // sigma initial
double beta = (25.0/3.0)/2.0; // variabilite de la performance
// Fonctions de troncature de la Gaussienne centree reduite (Herbrich-Minka-Graepel 2007)
var stdNormal = new Normal(0.0, 1.0);
double c = Math.Sqrt(2*beta*beta + sigW*sigW + sigL*sigL); // denominateur commun c
double t = (muW - muL)/c; // ecart standardise
double Vt = stdNormal.Density(t) / stdNormal.CumulativeDistribution(t); // V(t) = phi(t)/Phi(t)
double Wt = Vt*(Vt + t); // W(t) = V(t)(V(t)+t)
// Mises a jour closed-form (formes fermees de Herbrich-Minka-Graepel 2007).
// Note : la variance se contracte du facteur (sigma^2 / c^2) * W(t), pas de W(t) seul --
// ce facteur d'echelle est indispensable pour retrouver le posterior d'Infer.NET (Infer-8, section 3).
double muWNew = muW + sigW*sigW*Vt/c;
double muLNew = muL - sigL*sigL*Vt/c;
double sigWNew = Math.Sqrt(sigW*sigW*(1.0 - (sigW*sigW/(c*c))*Wt));
double sigLNew = Math.Sqrt(sigL*sigL*(1.0 - (sigL*sigL/(c*c))*Wt));
Console.WriteLine("Mise a jour closed-form EP sur un match (priors egaux, mu=25, sigma=8,33)");
Console.WriteLine($" c = {c:F4} t = {t:F4} V(t) = {Vt:F4} W(t) = {Wt:F4}");
Console.WriteLine($" GAGNANT : mu {muW:F2} -> {muWNew:F2} sigma {sigW:F2} -> {sigWNew:F2}");
Console.WriteLine($" PERDANT : mu {muL:F2} -> {muLNew:F2} sigma {sigL:F2} -> {sigLNew:F2}");
Console.WriteLine("Verification de coherence : ces valeurs (mu 29,21 / 20,79 ; sigma 7,19)");
Console.WriteLine("reproduisent exactement le posterior Infer.NET de la section 3 d'Infer-8 (cellule 16) --");
Console.WriteLine("le moteur EP et la forme fermee de Herbrich 2007 coincident sur ce cas 2 joueurs.");Mise a jour closed-form EP sur un match (priors egaux, mu=25, sigma=8,33)
c = 13,1762 t = 0,0000 V(t) = 0,7979 W(t) = 0,6366
GAGNANT : mu 25,00 -> 29,21 sigma 8,33 -> 7,19
PERDANT : mu 25,00 -> 20,79 sigma 8,33 -> 7,19
Verification de coherence : ces valeurs (mu 29,21 / 20,79 ; sigma 7,19)
reproduisent exactement le posterior Infer.NET de la section 3 d'Infer-8 (cellule 16) --
le moteur EP et la forme fermee de Herbrich 2007 coincident sur ce cas 2 joueurs.2. Lecture : EP par Infer.NET vs forme fermée — deux routes, le même postérieur
La cellule précédente calcule en forme fermée (O(1), sans compilation ni échantillonnage) ce qu’Infer.NET obtient en lançant son moteur EP en section 3 d’Infer-8-TrueSkill (cellule 16). Sur un match à priors égaux, l’écart standardisé est nul (\(t = 0\)) : le match est maximalement informatif (\(V(0) \approx 0{,}80\)), d’où un déplacement du skill de \(\pm 4{,}21\) points et une contraction de l’incertitude de \(8{,}33\) à \(7{,}19\) (\(-14\,\%\)). On retrouve exactement le postérieur Infer.NET N(29,21, 7,19) / N(20,79, 7,19) de la cellule 16 d’Infer-8 — la forme fermée et le moteur EP coïncident sur ce cas canonique à 2 joueurs.
C’est cette exactitude O(1) qui rend TrueSkill déployable à l’échelle de millions de joueurs : chaque mise à jour coûte une poignée de multiplications plutôt qu’une inférence compilée. Le moteur EP d’Infer.NET redevient indispensable dès que le modèle s’écarte du cas canonique — matchs nuls via ConstrainBetween (section 4 d’Infer-8), équipes (section 6), multi-joueurs (section 7) — cas pour lesquels il n’existe pas toujours de forme fermée. Les deux approches sont complémentaires : EP pour la flexibilité du modèle, forme fermée pour la vélocité en production.
3. Diagnostics de convergence : quand la forme fermée doit itérer
Les sections 1-2 ont traité un match : le graphe de facteurs est un arbre avec un seul facteur non gaussien (la comparaison), et EP converge en une seule passe — c’est précisément ce qui rend la forme fermée possible. Ajoutons un second match couplé : A (μ = 25) bat B (μ = 35) — un upset contre un joueur établi plus fort — puis C (μ = 25) bat A. Le joueur A est maintenant partagé par les deux facteurs : le message du match 1 vers A dépend du message du match 2 vers A (et réciproquement), et EP doit itérer jusqu’au point fixe.
Nous mesurons trois choses, sans approximation ailleurs que dans EP lui-même :
- la trajectoire de la croyance sur A (μ_A, σ_A) balayage après balayage ;
- le coût du moment matching : l’écart du point fixe EP au postérieur exact de A — calculable par simple quadrature 1D, car l’identité du probit (∫ N(s; m, v)·Φ((a−s)/√u) ds = Φ((a−m)/√(v+u))) intègre B et C analytiquement dans le marginal exact de A ;
- l’écart du traitement online (production : une passe séquentielle par match, jamais itéré) au même postérieur exact.
// Moteur EP batch sur 2 matchs couples par le joueur A (coordonnees naturelles pi = 1/v, tau = pi*mu).
// Classe statique : les types et methodes persistent d'une cellule a l'autre du kernel.
#load "SvgChartHelper.cs"
using MathNet.Numerics.Distributions;
using System;
using System.Collections.Generic;
using System.Linq;
public record struct EpG(double Pi, double Tau);
public static class EpEngine
{
public static readonly Normal Nrm = new Normal(0.0, 1.0);
public static double Vw(double t) { var v = Nrm.Density(t) / Nrm.CumulativeDistribution(t); return v; } // V(t)
public static double Ww(double t) { var v = Vw(t); return v * (v + t); } // W(t)
public static EpG Mul(EpG a, EpG b) => new EpG(a.Pi + b.Pi, a.Tau + b.Tau);
public static (double Mu, double Sd) MeanSd(EpG g) => (g.Tau / g.Pi, Math.Sqrt(1.0 / g.Pi));
public static EpG CavityOf(EpG bel, EpG msg) => new EpG(bel.Pi - msg.Pi, bel.Tau - msg.Tau);
// Mise a jour EP d'un match (w bat l) : moment matching EXACT du marginal incline (identite probit),
// en cavity (mu_w, v_w), (mu_l, v_l). Renvoie les messages (pi, tau) vers w et vers l.
public static (EpG ToW, EpG ToL) MatchUpdate((double Mu, double V) cw, (double Mu, double V) cl, double b2)
{
double c = Math.Sqrt(cw.V + cl.V + b2);
double t = (cw.Mu - cl.Mu) / c;
double V = Vw(t), W = Ww(t);
double mwt = cw.Mu + cw.V / c * V, vwt = cw.V * (1.0 - cw.V / (c * c) * W);
double mlt = cl.Mu - cl.V / c * V, vlt = cl.V * (1.0 - cl.V / (c * c) * W);
return (new EpG(1.0 / vwt - 1.0 / cw.V, mwt / vwt - cw.Mu / cw.V),
new EpG(1.0 / vlt - 1.0 / cl.V, mlt / vlt - cl.Mu / cl.V));
}
}
// Scenario : A (mu=25) bat B (mu=35) -- upset -- puis C (mu=25) bat A. Tous sigma0 = 25/3.
double epSd0 = 25.0 / 3.0, epV0 = epSd0 * epSd0, epBeta = epSd0 / 2.0;
double epB2 = 2.0 * epBeta * epBeta; // variance portee par le facteur comparaison (2*beta^2)
var epPrior = new Dictionary<string, EpG> {
["A"] = new EpG(1.0 / epV0, 25.0 / epV0),
["B"] = new EpG(1.0 / epV0, 35.0 / epV0),
["C"] = new EpG(1.0 / epV0, 25.0 / epV0),
};
// Croyances = prior ⊗ messages. m1 = (msg->A, msg->B) pour "A bat B" ; m2 = (msg->C, msg->A) pour "C bat A".
(EpG A, EpG B, EpG C) EpBeliefs((EpG, EpG) m1, (EpG, EpG) m2) => (
EpEngine.Mul(EpEngine.Mul(epPrior["A"], m1.Item1), m2.Item2),
EpEngine.Mul(epPrior["B"], m1.Item2),
EpEngine.Mul(epPrior["C"], m2.Item1));
// ---- Batch EP, ordonnancement SEQUENTIEL : match 1 installe, puis match 2 avec la croyance fraiche.
var epMsg1 = (new EpG(0, 0), new EpG(0, 0)); // (vers A, vers B)
var epMsg2 = (new EpG(0, 0), new EpG(0, 0)); // (vers C, vers A)
var bel = EpBeliefs(epMsg1, epMsg2);
var seqTraj = new List<(int K, double Mu, double Sd, double D)> { (0, 25.0, epSd0, double.NaN) };
(double prevMu, double prevSd) = (25.0, epSd0);
for (int k = 1; k <= 200; k++)
{
var cavA1 = EpEngine.CavityOf(bel.A, epMsg1.Item1); var cavB = EpEngine.CavityOf(bel.B, epMsg1.Item2);
epMsg1 = EpEngine.MatchUpdate(EpEngine.MeanSd(cavA1), EpEngine.MeanSd(cavB), epB2);
bel = EpBeliefs(epMsg1, epMsg2);
var cavC = EpEngine.CavityOf(bel.C, epMsg2.Item1); var cavA2 = EpEngine.CavityOf(bel.A, epMsg2.Item2);
epMsg2 = EpEngine.MatchUpdate(EpEngine.MeanSd(cavC), EpEngine.MeanSd(cavA2), epB2);
bel = EpBeliefs(epMsg1, epMsg2);
var (mu, sd) = EpEngine.MeanSd(bel.A);
double d = Math.Max(Math.Abs(mu - prevMu), Math.Abs(sd - prevSd));
seqTraj.Add((k, mu, sd, d));
(prevMu, prevSd) = (mu, sd);
if (d < 1e-12) break;
}
Console.WriteLine($"EP batch (sequentiel) converge en {seqTraj.Count - 1} balayages (tolerance 1e-12)");
Console.WriteLine($" {"k",3} {"mu_A",12} {"sigma_A",12} {"delta max",11}");
foreach (var (k, mu, sd, d) in seqTraj)
Console.WriteLine($" {k,3} {mu,12:F6} {sd,12:F6} {(double.IsNaN(d) ? double.NaN : d),11:E2}");EP batch (sequentiel) converge en 7 balayages (tolerance 1e-12)
k mu_A sigma_A delta max
0 25,000000 8,333333 NaN
1 28,627391 4,374300 3,96E+000
2 28,544701 4,329971 8,27E-002
3 28,544082 4,329740 6,18E-004
4 28,544078 4,329738 3,86E-006
5 28,544078 4,329738 2,41E-008
6 28,544078 4,329738 1,50E-010
7 28,544078 4,329738 9,70E-013// Courbes de convergence : la croyance sur A part du prior (25, 8,33) et gagne le point fixe.
var epCats = seqTraj.Select(r => r.K.ToString()).ToArray();
display(SvgChartHelper.Line("Convergence EP : moyenne mu_A par balayage", epCats,
seqTraj.Select(r => r.Mu).ToArray()));
display(SvgChartHelper.Line("Convergence EP : ecart-type sigma_A par balayage", epCats,
seqTraj.Select(r => r.Sd).ToArray()));Lecture : un point fixe atteint en quelques balayages, à contraction rapide
Le premier balayage fait presque tout le travail : μ_A saute de 25,0 (prior) à 28,627, σ_A se contracte de 8,333 à 4,374. Les balayages suivants ne corrigent que le couplage résiduel — l’écart au balayage précédent décroît d’environ deux ordres de grandeur par balayage (8,3e−2 → 6,2e−4 → 3,9e−6 → …), et le point fixe μ_A = 28,544, σ_A = 4,330 est atteint en 7 balayages à 1e−12 près. La convergence est géométrique rapide : chaque match ne couple l’autre qu’à travers la seule variable partagée A, et la contraction héritée du ratio σ²/c² (section 1) amortit l’aller-retour des messages.
Mais un point fixe EP n’est pas une preuve d’exactitude — c’est la limite de l’approximation produite par EP (factorisation en Gaussiennes + projection par moment matching). La cellule suivante confronte ce point fixe au postérieur exact, calculé sans aucune approximation.
// Posterior EXACT de A : l'identite du probit integre B et C analytiquement, le marginal exact
// de s_A est proportionnel a N(s_A; 25, v0) * Phi((s_A-35)/s') * Phi((25-s_A)/s') avec s'^2 = v0+2*beta^2.
// Quadrature 1D (Simpson compose, 20000 intervalles) : aucune approximation EP ici.
double epSp = Math.Sqrt(epV0 + epB2);
double epLo = 25.0 - 8 * epSd0, epHi = 25.0 + 8 * epSd0;
double EpExactW(double s) => Math.Exp(-0.5 * (s - 25.0) * (s - 25.0) / epV0)
* EpEngine.Nrm.CumulativeDistribution((s - 35.0) / epSp)
* EpEngine.Nrm.CumulativeDistribution((25.0 - s) / epSp);
double SimpsonOf(Func<double, double> f, double a, double b, int n)
{
double h = (b - a) / n, s = f(a) + f(b);
for (int i = 1; i < n; i++) s += f(a + i * h) * (i % 2 == 1 ? 4 : 2);
return s * h / 3.0;
}
double Z0 = SimpsonOf(EpExactW, epLo, epHi, 20000);
double exMean = SimpsonOf(s => s * EpExactW(s), epLo, epHi, 20000) / Z0;
double exM2 = SimpsonOf(s => s * s * EpExactW(s), epLo, epHi, 20000) / Z0;
double exVar = exM2 - exMean * exMean;
double exSkew = SimpsonOf(s => Math.Pow(s - exMean, 3) * EpExactW(s), epLo, epHi, 20000) / Z0 / Math.Pow(exVar, 1.5);
double exSd = Math.Sqrt(exVar);
// Traitement ONLINE (production TrueSkill) : une passe sequentielle par match, jamais itere.
(double Mu, double V) WinnerUpdate((double Mu, double V) w, (double Mu, double V) l)
{
double c = Math.Sqrt(w.V + l.V + epB2), t = (w.Mu - l.Mu) / c;
return (w.Mu + w.V / c * EpEngine.Vw(t), w.V * (1.0 - w.V / (c * c) * EpEngine.Ww(t)));
}
var aAfter1 = WinnerUpdate((25.0, epV0), (35.0, epV0)); // match 1 : A bat B (upset)
// match 2 : C (prior) bat A (posterior du match 1 comme prior) -- A est le perdant
double c2 = Math.Sqrt(epV0 + aAfter1.V + epB2), t2 = (25.0 - aAfter1.Mu) / c2;
double onMuA = aAfter1.Mu - aAfter1.V / c2 * EpEngine.Vw(t2);
double onVA = aAfter1.V * (1.0 - aAfter1.V / (c2 * c2) * EpEngine.Ww(t2));
double onSdA = Math.Sqrt(onVA);
var (fpMu, fpSd) = EpEngine.MeanSd(bel.A);
Console.WriteLine("Reference EXACTE (quadrature 1D, zero approximation EP) vs approximations :");
Console.WriteLine($" posterior exact de A : mu = {exMean:F4} sigma = {exSd:F4} skewness = {exSkew:F4}");
Console.WriteLine($" EP batch (point fixe) : mu = {fpMu:F4} sigma = {fpSd:F4}");
Console.WriteLine($" online (1 passe/match) : mu = {onMuA:F4} sigma = {onSdA:F4}");
Console.WriteLine($" cout du moment matching (EP fixe - exact) : dmu = {fpMu - exMean:+0.00;-0.00} dsigma = {fpSd - exSd:+0.00;-0.00}");
Console.WriteLine($" ecart du schema online (online - exact) : dmu = {onMuA - exMean:+0.00;-0.00} dsigma = {onSdA - exSd:+0.00;-0.00}");Reference EXACTE (quadrature 1D, zero approximation EP) vs approximations :
posterior exact de A : mu = 27,4348 sigma = 5,9730 skewness = -0,0096
EP batch (point fixe) : mu = 28,5441 sigma = 4,3297
online (1 passe/match) : mu = 27,3931 sigma = 6,0649
cout du moment matching (EP fixe - exact) : dmu = +1,11 dsigma = -1,64
ecart du schema online (online - exact) : dmu = -0,04 dsigma = +0,09Lecture : le point fixe EP n’est pas le postérieur exact — c’est là le vrai coût
La comparaison pivote sur le scénario : l’upset contre B (μ = 35) est une information forte et doublement ambiguë — elle dit « A est plus fort qu’on ne croyait » et « B est peut-être plus faible que son rating ». Le postérieur exact propage cette seconde lecture (la victoire sur B est créditée avec prudence), et aboutit à μ_A = 27,435, σ_A = 5,973.
L’EP batch, lui, factorise le postérieur en trois Gaussiennes indépendantes : chaque match traite la croyance de l’autre joueur comme une certitude figée, l’upset est crédité deux fois (côté A et côté B), et le point fixe finit surconfiant : μ_A = 28,544 (+1,11 au-dessus de l’exact), σ_A = 4,330 (−1,64 — une variance à ~53 % de l’exacte, presque moitié trop faible). C’est le coût du moment matching mesuré, pas un artefact d’itération : converger EP davantage ne corrige rien, le biais est structurel (factorisation + projection gaussienne).
Le schéma online de production (une passe par match, jamais itéré) reste ici plus proche du postérieur exact (écarts −0,04 / +0,09) que le point fixe itéré. La leçon opérationnelle est contre-intuitive mais solide : ne pas converger n’est pas seulement moins cher — sur ce scénario, c’est aussi plus fidèle, parce que l’erreur de factorisation domine l’erreur d’ordonnancement. Dernière signature exacte invisible côté EP : la skewness du marginal exact vaut −0,0096 — faible mais non nulle ; une Gaussienne EP vaut 0 par construction.
4. Ordonnancement des messages : séquentiel (Gauss-Seidel) vs parallèle (Jacobi)
Le point fixe de la section 3 n’impose pas l’ordre des mises à jour — deux ordonnancements naturels coexistent :
- séquentiel (Gauss-Seidel) : dans un balayage, le match 1 est mis à jour et installé avant que le match 2 ne calcule ses cavity — chaque facteur voit la croyance fraîche de l’autre ;
- parallèle (Jacobi / flooding) : tous les messages sont recalculés sur un snapshot des croyances en début de balayage, puis installés ensemble — chaque facteur voit la croyance périmée d’un balayage.
Sur un arbre, la propagation exacte (sum-product) termine en deux passes — forward puis backward — parce que les messages restent exacts. Ce sont les projections gaussiennes d’EP qui rendent le point fixe implicite : la projection d’un produit contenant des messages déjà projetés ne se termine pas en un nombre fini de passes, et le choix d’ordonnancement fixe la vitesse de convergence. Nous mesurons les deux sur la même chaîne de matchs, même tolérance (1e−12) et même critère d’arrêt (écart max sur μ_A et σ_A au balayage précédent).
// Les deux ordonnancements sur la meme chaine de matchs, meme tolerance 1e-12.
(int Sweeps, List<double> Deltas, (double Mu, double Sd) Fixed) RunSchedule(bool parallel)
{
var m1 = (new EpG(0, 0), new EpG(0, 0));
var m2 = (new EpG(0, 0), new EpG(0, 0));
var b = EpBeliefs(m1, m2);
var deltas = new List<double>();
var prev = EpEngine.MeanSd(b.A);
for (int k = 1; k <= 200; k++)
{
if (!parallel)
{
var cA1 = EpEngine.CavityOf(b.A, m1.Item1); var cB = EpEngine.CavityOf(b.B, m1.Item2);
m1 = EpEngine.MatchUpdate(EpEngine.MeanSd(cA1), EpEngine.MeanSd(cB), epB2);
b = EpBeliefs(m1, m2);
var cC = EpEngine.CavityOf(b.C, m2.Item1); var cA2 = EpEngine.CavityOf(b.A, m2.Item2);
m2 = EpEngine.MatchUpdate(EpEngine.MeanSd(cC), EpEngine.MeanSd(cA2), epB2);
b = EpBeliefs(m1, m2);
}
else
{
var snapA = b.A; var snapB = b.B; var snapC = b.C; // snapshot du debut de balayage
var cA1 = EpEngine.CavityOf(snapA, m1.Item1); var cB = EpEngine.CavityOf(snapB, m1.Item2);
var nm1 = EpEngine.MatchUpdate(EpEngine.MeanSd(cA1), EpEngine.MeanSd(cB), epB2);
var cC = EpEngine.CavityOf(snapC, m2.Item1); var cA2 = EpEngine.CavityOf(snapA, m2.Item2);
var nm2 = EpEngine.MatchUpdate(EpEngine.MeanSd(cC), EpEngine.MeanSd(cA2), epB2);
m1 = nm1; m2 = nm2; // installation groupee
b = EpBeliefs(m1, m2);
}
var cur = EpEngine.MeanSd(b.A);
double d = Math.Max(Math.Abs(cur.Mu - prev.Mu), Math.Abs(cur.Sd - prev.Sd));
deltas.Add(d);
prev = cur;
if (d < 1e-12) break;
}
return (deltas.Count, deltas, prev);
}
var seqRes = RunSchedule(parallel: false);
var parRes = RunSchedule(parallel: true);
Console.WriteLine($"Sequentiel (Gauss-Seidel) : {seqRes.Sweeps} balayages -> mu_A = {seqRes.Fixed.Mu:F6} sigma_A = {seqRes.Fixed.Sd:F6}");
Console.WriteLine($"Parallele (Jacobi) : {parRes.Sweeps} balayages -> mu_A = {parRes.Fixed.Mu:F6} sigma_A = {parRes.Fixed.Sd:F6}");
Console.WriteLine($"Ecart entre les deux points fixes : {Math.Max(Math.Abs(seqRes.Fixed.Mu - parRes.Fixed.Mu), Math.Abs(seqRes.Fixed.Sd - parRes.Fixed.Sd)):E2}");
Console.WriteLine();
Console.WriteLine($" {"k",3} {"sequentiel",13} {"parallele",13}");
for (int i = 0; i < Math.Max(seqRes.Deltas.Count, parRes.Deltas.Count); i++)
Console.WriteLine($" {i + 1,3} {(i < seqRes.Deltas.Count ? seqRes.Deltas[i].ToString("E2") : ""),13} {(i < parRes.Deltas.Count ? parRes.Deltas[i].ToString("E2") : ""),13}");Sequentiel (Gauss-Seidel) : 7 balayages -> mu_A = 28,544078 sigma_A = 4,329738
Parallele (Jacobi) : 13 balayages -> mu_A = 28,544078 sigma_A = 4,329738
Ecart entre les deux points fixes : 7,11E-015
k sequentiel parallele
1 3,96E+000 3,73E+000
2 8,27E-002 2,86E-001
3 6,18E-004 1,30E-002
4 3,86E-006 1,13E-003
5 2,41E-008 8,29E-005
6 1,50E-010 7,02E-006
7 9,70E-013 5,17E-007
8 4,38E-008
9 3,22E-009
10 2,73E-010
11 2,01E-011
12 1,70E-012
13 1,24E-013// Vitesse de convergence comparee : decroissance de l'ecart par balayage (echelle log).
var seqXs = Enumerable.Range(1, seqRes.Deltas.Count).Select(i => (double)i).ToArray();
var parXs = Enumerable.Range(1, parRes.Deltas.Count).Select(i => (double)i).ToArray();
display(SvgChartHelper.Overlay(
"Convergence : ecart max (mu_A, sigma_A) par balayage",
"balayage", "ecart au balayage precedent",
new[]
{
new SvgSeries("sequentiel (Gauss-Seidel)", seqXs, seqRes.Deltas.ToArray(), TraceStyle.LineMarkers, "#4C72B0"),
new SvgSeries("parallele (Jacobi)", parXs, parRes.Deltas.ToArray(), TraceStyle.LineMarkers, "#C44E52"),
}, logY: true));Lecture : mêmes messages, même point fixe — la fraîcheur de l’information divise le travail par deux
Les deux ordonnancements convergent vers le même point fixe (écart mesuré ≤ 1e−12) : l’ordre des mises à jour ne change pas la limite, seulement le chemin. Le séquentiel demande 7 balayages, le parallèle 13 — presque exactement le double. La raison se lit dans la contraction : le séquentiel amortit chaque correction par l’information déjà installée dans le balayage (~150× par balayage mesuré), tandis que le parallèle passe chaque message à travers une image périmée de l’autre match et n’amortit qu’à ~12× par balayage — il rejoue une partie du travail que le séquentiel a déjà capturé.
C’est exactement la structure Gauss-Seidel vs Jacobi des méthodes itératives linéaires, transposée aux messages EP : l’information fraîche à l’intérieur du balayage est gratuite, puisqu’un balayage coûte le même nombre de mises à jour de facteurs dans les deux cas. Et le traitement online de production pousse cette logique à l’extrême : un seul passage, un match après l’autre, jamais itéré — renonçant même au point fixe, ce que la section 3 a montré être un renoncement peu coûteux (voire favorable) quand l’erreur de factorisation domine.
Synthèse : deux routes, le même postérieur
La forme fermée de Herbrich-Minka-Graepel (2007) isole la contribution algorithmique du cas à 2 joueurs : deux fonctions de troncature V(t) et W(t), une poignée d’opérations arithmétiques, et la mise à jour complète d’un match — sans compilation ni échantillonnage. La démonstration numérique retrouve exactement le postérieur du moteur EP (N(29,21, 7,19) sur priors égaux) : O(1) par match, la vitesse de production d’Xbox Live.
Le moteur EP redevient l’outil général dès que le modèle s’écarte du cas canonique (matchs nuls, équipes, free-for-all). Les deux approches sont complémentaires : EP pour la flexibilité du modèle, forme fermée pour la vélocité en production.
Les sections 3 et 4 étendent la lettre aux matchs couplés : EP doit alors itérer vers un point fixe (diagnostic mesuré contre le postérieur exact — l’approximation factorisée y est surconfiante), et l’ordonnancement des messages — séquentiel ou parallèle — fixe la vitesse de convergence sans changer la limite.