Bayesian inference for partial orders from random linear extensions: power relations from 12th Century Royal Acta

Résumé technique : Inférence bayésienne pour les ordres partiels à partir d'extensions linéaires aléatoires

Énoncé du problème
L'article aborde le défi statistique consistant à inférer une hiérarchie sociale évolutive à partir de données d'ordre de classement où la structure sous-jacente n'est pas nécessairement un ordre complet (total). Les auteurs analysent 371 listes de témoins issues des Acta royaux anglais et normands du XIIe siècle (documents juridiques), enregistrant l'ordre dans lequel 67 évêques étaient listés. Les historiens émettent l'hypothèse que cet ordre reflète une hiérarchie sociale basée sur le statut, l'ancienneté et l'influence politique. Cependant, les données sont bruyantes, incomplètes (des sous-ensembles d'évêques apparaissent dans chaque liste), et la hiérarchie sous-jacente peut contenir des paires d'acteurs incomparables (un ordre partiel), plutôt qu'un classement linéaire unique. Les modèles existants pour les données de classement, tels que Mallows et Plackett-Luce, supposent généralement un ordre total ou des probabilités indépendantes du contexte, ce qui peut être inapproprié pour ce contexte historique où la transitivité est attendue mais où l'ordre est partiel.

Méthodologie
Les auteurs proposent un modèle de Markov caché (HMM) bayésien où l'état latent est un ordre partiel (poset) évolutif et les données observées sont des extensions linéaires aléatoires de ce poset.

1. Paramétrisation de la variable latente :

   • Le poset au temps $t$, noté $h(t)$, est généré à partir d'une matrice de statut latente $Z(t)$ de dimension $K$.
   • Pour chaque évêque $j$, un vecteur d'autorité latent $U^{(t)}_j$ évolue dans le temps selon une autorégression vectorielle (VAR) d'ordre 1.
   • Un effet de covariable $\beta_{s_{t,j}}$ basé sur l'ancienneté est ajouté au vecteur d'autorité pour former le vecteur de statut : $Z^{(t)}_j = U^{(t)}_j + \mathbf{1}_K \beta_{s_{t,j}}$.
   • Le poset $h(t)$ est défini par l'intersection de $K$ ordres totaux dérivés des colonnes de $Z(t)$. L'évêque $i$ précède $j$ dans le poset si et seulement si $Z^{(t)}_{i,k} > Z^{(t)}_{j,k}$ pour tout $k=1,\dots,K$.
   • La dimension $K$ est choisie comme $\lfloor D/2 \rfloor$ (où $D$ est le nombre maximum d'évêques actifs), garantissant que le modèle peut représenter n'importe quel poset possible (propriété de représentation universelle).

2. Modèle d'observation (saut de file) :

   • Les listes observées sont modélisées comme des extensions linéaires « bruyantes » du vrai poset.
   • Les auteurs introduisent un mécanisme de « saut de file » : avec une probabilité $p$, le prochain acteur dans la liste est choisi uniformément au hasard (en ignorant les contraintes du poset) ; sinon, l'acteur est choisi selon une extension linéaire aléatoire du sous-ordre restant.
   • Cela permet d'incorporer du « bruit » où l'ordre observé contredit la hiérarchie sous-jacente, tout en maintenant la contrainte selon laquelle les extensions linéaires valides sont plus probables.
   • Le modèle gère les listes incomplètes (sous-ensembles d'évêques) en conditionnant sur le sous-ordre induit par les acteurs présents.

3. Priors et cohérence :

   • Le prior sur le processus de poset est construit pour être cohérent marginalement, ce qui signifie que la distribution d'un sous-ordre (induit par un sous-ensemble d'acteurs) est cohérente avec la distribution de l'ordre complet. Cela est obtenu en utilisant un prior spécifique sur les vecteurs latents $U$ et le paramètre de corrélation $\rho$.
   • Un hyperparamètre $\rho$ contrôle la « profondeur » du poset (la longueur de la plus longue chaîne). Le prior est conçu pour être non informatif concernant la profondeur, évitant la concentration sur les posets de profondeur 3 observée avec des priors uniformes sur tous les posets.
   • Les effets d'ancienneté $\beta$ sont contraints d'être ordonnés ($\beta_1 > \beta_2 > \dots$) pour refléter les attentes historiques selon lesquelles l'ancienneté est corrélée au statut, bien que des modèles non contraints soient également testés.

4. Inférence :

   • L'inférence postérieure est réalisée par des chaînes de Markov Monte Carlo (MCMC) avec des mises à jour de Metropolis-Hastings.
   • La vraisemblance implique le dénombrement des extensions linéaires, un problème #P-complet. Les auteurs utilisent des algorithmes de dénombrement récursifs (spécifiquement le package lecount) qui sont réalisables pour le petit nombre d'acteurs ($m \le 22$) dans cet ensemble de données, mais limitent l'évolutivité à des problèmes plus vastes.

Contributions clés

• Nouvelle classe de modèles : L'article introduit un cadre général pour modéliser des données de classement en série temporelle où la structure sous-jacente est un ordre partiel, généralisant les modèles existants tels que Mallows et Plackett-Luce.
• Cohérence marginale : Les auteurs dérivent et prouvent que leur prior de variable latente pour les posets est cohérent marginalement, une propriété souvent violée dans les priors ad hoc pour les ordres partiels.
• Représentation universelle : Ils démontrent qu'avec une dimension latente $K \ge \lfloor D/2 \rfloor$, le modèle peut représenter n'importe quelle série temporelle de posets possible, garantissant l'absence de biais structurel contre les hiérarchies complexes.
• Application historique : Il s'agit de la première analyse statistique des listes de témoins des Acta royaux du XIIe siècle modélisant explicitement la hiérarchie sociale comme un ordre partiel, séparant les effets de l'ancienneté de l'autorité personnelle.

Résultats

• Adéquation du modèle : Le modèle basé sur les posets surpasse les alternatives plus simples (ordres Vertex-Series-Parallel, ordres à seaux) et un modèle de mélange de séries temporelles Plackett-Luce en termes d'adéquation (mesurée par la validation croisée Leave-One-Out et les facteurs de Bayes).
• Ancienneté vs Autorité : L'analyse confirme une forte dépendance du statut à l'ancienneté, l'effet de l'ancienneté diminuant à mesure que le numéro de rang augmente. Cependant, le modèle isole avec succès l'« autorité » (écarts par rapport à l'ancienneté).
• Insights historiques :
  • Évêques normands : Le modèle détecte un déclin du statut des évêques normands (par exemple, d'Avranches, de Bayeux, d'Évreux) par rapport aux évêques anglais à partir du début du XIIe siècle, une tendance jamais quantifiée auparavant.
  • Influence politique : Le statut d'évêques spécifiques, tels que Henri de Blois (frère du roi Étienne) et Nigel d'Ely, fluctue d'une manière corrélée à la faveur ou à la disgrâce politique, indépendamment de leur ancienneté.
  • Structure hiérarchique : Les posets de consensus reconstruits sont relativement peu profonds, consistant généralement en quelques groupes d'évêques de rang moyen avec un petit nombre d'acteurs au-dessus ou en dessous, plutôt qu'une hiérarchie profonde et rigide.

Signification et revendications
L'article affirme que sa contribution principale est le développement d'une méthode statistiquement rigoureuse pour inférer des ordres partiels évolutifs à partir de données de classement bruyantes et incomplètes. En appliquant cela aux Acta historiques, les auteurs fournissent des preuves quantitatives du fonctionnement des hiérarchies sociales au XIIe siècle, distinguant spécifiquement l'ancienneté structurelle de l'autorité politique fluide.

Les auteurs sont modestes concernant l'évolutivité computationnelle de leur méthode, reconnaissant que la nature #P-complète du dénombrement des extensions linéaires limite le modèle aux ensembles de données avec un petit nombre d'acteurs (environ 20). Ils suggèrent que pour des ensembles de données plus vastes, des classes restreintes de posets (comme les ordres VSP ou les ordres à seaux) pourraient être des compromis nécessaires. Ils notent également que, bien que leur modèle s'adapte bien aux données, le modèle de « bruit » suppose que les erreurs se produisent dans une seule direction (saut de file), et que des travaux futurs pourraient explorer des modèles de bruit bidirectionnels.

En fin de compte, l'article soutient que supposer un ordre total (comme dans les modèles de classement standard) est injustifié pour ce type de données sociales et que les modèles d'ordre partiel offrent une représentation plus précise et interprétable des structures sociales historiques.