Pairwise Comparisons without Stochastic Transitivity: Model, Theory and Applications

Dit artikel introduceert een nieuw statistisch model voor paarwijze vergelijkingen dat de beperkende aanname van stochastische transitiviteit elimineert door gebruik te maken van een laag-dimensionale schuine-symmetrische matrix, waardoor het superieure voorspellende prestaties biedt in complexe scenario's waar traditionele modellen zoals Bradley-Terry falen.

De kern

Hier is een uitleg van het onderzoek in eenvoudig Nederlands, met behulp van alledaagse vergelijkingen.

De Kern van het Onderzoek: Waarom "Rock, Paper, Scissors" de Regel is, niet de Uitzondering

Stel je voor dat je een groot toernooi organiseert, bijvoorbeeld voor schaken, tennis of een computerspel. De meeste statistische modellen die we vandaag de dag gebruiken, gaan uit van één simpele regel: er is altijd een duidelijk winnaar en een duidelijke volgorde.

Als speler A beter is dan speler B, en speler B is beter dan speler C, dan moet speler A ook beter zijn dan speler C. Dit noemen wetenschappers "transitiviteit". Het is als een ladder: als je op de derde trede staat, ben je hoger dan de tweede, en dus ook hoger dan de eerste.

Maar in het echte leven werkt het vaak niet zo.

Denk aan het spel Steen, Papier, Schaar:

• Steen wint van Schaar.
• Schaar wint van Papier.
• Maar Papier wint van Steen.

Er is geen enkele ladder waarop je iedereen kunt rangschikken. Dit noemen we niet-transitiviteit. In de echte wereld, vooral bij complexe spellen of sporten waar strategieën en verschillende vaardigheden een rol spelen, gebeurt dit constant. Een speler kan heel goed zijn in aanval, maar slecht in verdediging. Tegen de ene tegenstander wint hij makkelijk, maar tegen een andere verliest hij, ook al is die tweede "in het algemeen" minder sterk.

Het Probleem met de Oude Methodes

De auteurs van dit paper (Lee en Chen) merken op dat de oude, populaire modellen (zoals het Bradley-Terry model) proberen om die ladder te forceren, zelfs als die er niet is. Ze zeggen: "We moeten een ranglijst maken, ook al klopt die niet helemaal."

Het gevolg? De voorspellingen worden onnauwkeurig. Het is alsof je probeert om een ronde aardappel in een vierkant gat te duwen. Het past niet, en je krijgt een slecht resultaat. Vooral bij moderne e-sporten (zoals StarCraft II) of complexe teamsporten, waar strategieën als "Steen, Papier, Schaar" werken, faalt deze oude methode.

De Oplossing: Een Nieuw, Flexibeler Model

De auteurs hebben een nieuw statistisch model bedacht dat geen ladder vereist. In plaats van te vragen "Wie is nummer 1, nummer 2, nummer 3?", kijken ze naar de relaties tussen de spelers.

Ze gebruiken een wiskundig trucje (een "schuinsymmetrische matrix") om alle mogelijke uitkomsten van wedstrijden in één groot plaatje te vangen.

• De Analogie: Stel je voor dat je in plaats van een ladder, een web of een net maakt. In dit net zie je niet alleen wie beter is, maar ook waarom en tegen wie.
• De "Laag" (Low-Rank): Ze nemen aan dat dit complexe web eigenlijk niet zo willekeurig is. Het heeft een onderliggende structuur, net als een schilderij dat op afstand chaotisch lijkt, maar van dichtbij uit een paar hoofdkleuren bestaat. Ze noemen dit een "ongeveer laag-rang" structuur. Dit maakt het model slim genoeg om de complexe patronen te zien, maar niet zo complex dat het de computer laat crashen.

Wat hebben ze bewezen?

1. Het werkt sneller en beter: Ze hebben bewezen dat hun nieuwe methode, zelfs als er weinig data is (bijvoorbeeld als spelers elkaar maar zelden hebben ontmoet), de beste mogelijke voorspellingen doet.
2. Het is flexibel: Als de wereld wel een ladder heeft (zoals bij tennis, waar de sterkste spelers vaak winnen), werkt hun model net zo goed als de oude methodes. Maar als de wereld een "Steen-Papier-Schaar" situatie heeft (zoals bij e-sporten), wint hun model het met kop en schouders.
3. Rekenkracht: Ze hebben een slim algoritme bedacht om dit model snel te berekenen, zelfs voor duizenden spelers.

De Praktijk: StarCraft II en Tennis

Om hun theorie te testen, hebben ze twee echte datasets gebruikt:

• StarCraft II (E-sport): Hier is de chaos groot. Spelers kiezen verschillende eenheden met sterke en zwakke punten. Het resultaat? Een enorme "Steen-Papier-Schaar" situatie. Het oude model kon hier niets van voorspellen. Het nieuwe model zag de patronen en voorspelde de winnaars veel accurater.
• Tennis: Hier is de ladder vaak wel redelijk geldig (de beste spelers winnen vaak). Het nieuwe model deed het hier bijna net zo goed als het oude model, maar zonder de risico's van een verkeerde aanneming.

Conclusie in Eén Zin

De auteurs hebben een nieuwe manier bedacht om wedstrijden te analyseren die erkent dat de wereld niet altijd uit een simpele ranglijst bestaat, maar vaak uit een complex web van sterke en zwakke punten, waardoor we veel betere voorspellingen kunnen doen voor sporten en spellen waar strategieën elkaar opheffen.

Kortom: Ze hebben de "ladder" weggegooid en een "net" opgezet, zodat ze de echte, chaotische wereld van competitie beter kunnen begrijpen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Pairwise Comparisons without Stochastic Transitivity: Model, Theory and Applications" in het Nederlands.

Titel: Paarsgewijze Vergelijkingen zonder Stochastische Transitiviteit: Model, Theorie en Toepassingen

Auteurs: Sze Ming Lee en Yunxiao Chen (London School of Economics and Political Science)

---

1. Het Probleem

Paarsgewijze vergelijkingen (waarbij twee entiteiten, zoals spelers of items, met elkaar worden vergeleken) zijn een fundamenteel onderwerp in statistiek en machine learning. Traditionele modellen, zoals het Bradley-Terry (BT)-model en het Thurstone-model, maken een sterke aanname: stochastische transitiviteit.

• Stochastische Transitiviteit: Dit impliceert dat er een onderliggende, globale rangschikking bestaat. Als speler A beter is dan B, en B beter dan C, dan moet A ook beter zijn dan C.
• De Beperking: In veel real-world scenario's, vooral bij wedstrijden met meerdere vaardigheden of strategieën (zoals e-sports of complexe sporten), is deze aanname onrealistisch. Hier kan intransitiviteit optreden (bijvoorbeeld: "Steen-Schaar-Doek": A verslaat B, B verslaat C, maar C verslaat A).
• Huidige Oplossingen: Bestaande modellen die intransitiviteit toestaan (zoals die van Chen & Joachims, 2016, of Spearing et al., 2023) hebben ernstige tekortkomingen: ze zijn vaak niet-convex, computatie-intensief (Bayesiaanse MCMC), gebaseerd op exacte lage-rang structuren, of missen strikte theoretische garanties voor convergentie en foutgrenzen.

2. Methodologie

De auteurs stellen een nieuw, algemeen statistisch kader voor dat stochastische intransitiviteit expliciet toelaat zonder de transitiviteitsaanname.

• Modelstructuur:

  • De kans dat speler $i$ speler $j$ verslaat, wordt gemodelleerd via een logistische linkfunctie: $\pi_{ij} = g(m_{ij}) = (1 + e^{-m_{ij}})^{-1}$.
  • De parametermatrix $M = (m_{ij})$ is schuif-symmetrisch (skew-symmetric), d.w.z. $M = -M^\top$. Dit garandeert dat $\pi_{ij} = 1 - \pi_{ji}$.
  • In tegenstelling tot het BT-model (waarbij $m_{ij} = u_i - u_j$, wat een rang-2 structuur oplevert), wordt hier aangenomen dat $M$ een ongeveer lage-rang (approximately low-rank) structuur heeft. Dit betekent dat de complexiteit van de vergelijkingen kan worden beschreven door een beperkt aantal dominante factoren, maar niet noodzakelijk een exact lage rang.

• Schatting (Estimator):

  • De auteurs definiëren een maximum-likelihood schatter onder een nucleaire norm-beperking (nuclear norm constraint).
  • Het optimalisatieprobleem is:
    $$\hat{M} = \arg \max_{M} L(M) \quad \text{onder de voorwaarde} \quad \|M\|_* \leq C_n n, \quad M = -M^\top$$
    waarbij $\|M\|_*$ de nucleaire norm is (de som van de singuliere waarden), wat dient als een convex relaxatie van de rang van de matrix.
  • Dit maakt het probleem convex, wat zorgt voor een efficiënte en gegarandeerde oplossing.

• Algoritme:

  • Er wordt een spectraal geprojecteerd gradiënt-algoritme (spectral projected gradient algorithm) gebruikt om het probleem op te lossen.
  • De projectie op de nucleaire norm-bol wordt uitgevoerd via singuliere waarde soft-thresholding (Singular Value Soft-Thresholding), waarbij de schuif-symmetrische structuur van de matrix behouden blijft.

3. Belangrijkste Bijdragen

1. Nieuw Modelkader: Het eerste kader dat stochastische intransitiviteit behandelt met een ongeveer lage-rang structuur, in plaats van een exacte lage-rang structuur. Dit biedt meer flexibiliteit en robuustheid tegen modelmisspecificatie.
2. Theoretische Optimaliteit: De auteurs bewijzen dat hun schatter minimax-rate optimaliteit bereikt. De convergentiesnelheid past zich automatisch aan de dichtheid van de data (sparsiteit) aan.
3. Strikte Theoretische Analyse: In tegenstelling tot eerdere werken, worden er rigoureuze foutgrenzen en convergentieresultaten bewezen, zelfs in settings met schaarse data (waar niet alle paren met elkaar zijn vergeleken).
4. Efficiënte Berekening: Door het gebruik van convex optimalisatie en spectrale methoden, is het model schaalbaar naar hoge dimensies (veel spelers/items), wat een groot voordeel is ten opzichte van Bayesiaanse MCMC-methoden.

4. Resultaten

• Theoretische Bevindingen:

  • Theorema 1: De gemiddelde kwadratische fout (Frobenius-norm) tussen de geschatte en ware waarschijnlijkheidsmatrix convergeert met een snelheid die afhankelijk is van het aantal spelers ($n$), de steekproefdichtheid ($p_n$) en de complexiteit van het model ($C_n$).
  • Theorema 2: Er wordt een ondergrens bewezen die aantoont dat de convergentiesnelheid van de voorgestelde estimator niet verder kan worden verbeterd (optimaliteit).

• Simulaties:

  • De methode presteert aanzienlijk beter dan het Bradley-Terry-model in scenario's met intransitiviteit en hoge complexiteit (hoge rang $k$).
  • Zelfs bij toenemende data-omvang blijft de BT-methode stagneren, terwijl de voorgestelde methode blijft verbeteren.
  • De methode is robuust in schrale data-omstandigheden.

• Real-World Data Analyse:

  • StarCraft II (E-sport): In dit dataset (1.958 spelers) wordt 70% van de tripletten geconcludeerd als intransitief. De voorgestelde methode levert een significant hogere log-likelihood en nauwkeurigheid op dan het BT-model. Dit bevestigt dat strikte rangschikkingen in e-sports ongeschikt zijn.
  • Tennis (ATP): In professioneel tennis is intransitiviteit minder aanwezig. Hier presteert het BT-model marginaal beter (door de kleinere parameterruimte), maar de voorgestelde methode blijft zeer competitief. Dit toont de robustheid van het nieuwe model: het faalt niet als transitiviteit wel geldt, maar wint sterk als deze niet geldt.

5. Betekenis en Impact

• Paradigmaverschuiving: Dit werk breekt met de traditionele aanname van een globale rangschikking in paarsgewijze vergelijkingen. Het erkent dat in veel complexe systemen (sport, e-sport, aanbevelingssystemen) "winnaars" afhankelijk zijn van specifieke matchups en strategieën.
• Praktische Toepasbaarheid: De methode is direct toepasbaar op grote datasets (zoals toernooien en crowdsourcing) en biedt betere voorspellingen voor uitkomsten waar strategieën een rol spelen.
• Toekomstperspectief: Het kader kan worden uitgebreid naar covariaten (bijv. thuisvoordeel), tijdreeksen (vormveranderingen) en rater-heterogeniteit (in crowdsourcing).

Kortom, dit artikel biedt een wiskundig onderbouwde, computatie-efficiënte en theoretisch optimale oplossing voor het modelleren van complexe, niet-transitieve competitieve relaties, waarbij het de beperkingen van klassieke modellen zoals Bradley-Terry overwint.