🤖 machine learning

Estimation, Prediction, and Assortment Optimization for Markov Chain Choice Models with Panel Data

Cet article introduit un nouveau cadre pour les modèles de choix à chaîne de Markov avec des données de panel qui exploite des informations de préférence par ordre partiel pour développer des algorithmes EM supérieurs pour l'estimation des paramètres, tout en établissant la complexité computationnelle de la prédiction de choix personnalisée et de l'optimisation de l'assortiment.

Auteurs originaux : Yalcin Akcay, Gerardo Berbeglia, Young-San Lin

Publié 2026-07-14

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Yalcin Akcay, Gerardo Berbeglia, Young-San Lin

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous soyez un détective essayant de découvrir ce qu'un groupe de personnes aime réellement manger. Autrefois, les détectives examinaient une pile géante de reçus provenant d'un restaurant. Ils supposaient que chaque commande était une nouvelle intuition indépendante, comme si l'on lançait une pièce de monnaie. Si quelqu'un commandait des sushis, puis une pizza, puis un burger, le calcul ancien traitait ces trois choix comme trois événements distincts et sans lien.

Mais voici le rebondissement : les gens ne sont pas des pièces de monnaie. Si un client commande un maki au thon épicé, puis commande plus tard à nouveau un maki au thon épicé, c'est un indice ! Cela suggère qu'il aime vraiment le thon épicé. Ce document présente une nouvelle façon d'examiner ces « reçus » (que les auteurs appellent données de panel) en les traitant comme l'histoire connectée d'un client spécifique, plutôt que comme une pile de papier aléatoire.

Le nouvel outil du détective : la chaîne de Markov

Les auteurs proposent d'utiliser un outil mathématique spécifique appelé modèle de choix par Chaîne de Markov (CM). Voyez ce modèle comme une « carte de préférences ». Au lieu de simplement dire « J'aime les sushis », le modèle trace un parcours. Il demande : « Si je pense actuellement aux sushis, à quoi vais-je probablement penser ensuite ? Est-ce que je passe au sashimi, ou est-ce que j'abandonne pour commander un soda ? »

La grande découverte de ce document est que lorsque vous disposez de l'historique d'un client (ses données de panel), dessiner précisément cette « carte de voyage » devient beaucoup plus facile. Les auteurs ont réalisé des simulations (expériences informatiques) et ont testé leur méthode sur un ensemble de données réelles concernant les préférences en matière de sushis de 5 000 personnes. Ils ont découvert qu'en utilisant l'historique du client pour mettre à jour la carte, leurs nouveaux algorithmes (Cus et Hyb) étaient bien meilleurs pour deviner ce que les gens achèteraient ensuite par rapport aux anciennes méthodes.

Ce que les anciennes méthodes comprenaient mal

Le document s'oppose explicitement à l'idée selon laquelle on peut simplement ignorer la connexion entre les commandes passées d'un même client.

Le mythe de l'« indépendance » : Les auteurs montrent que si vous traitez chaque commande comme un événement totalement nouveau et aléatoire (la méthode traditionnelle), vous manquez la « commande partielle » des préférences. C'est comme essayer de deviner le film préféré d'une personne en regardant une liste aléatoire de films qu'elle a visionnés, sans réaliser qu'elle a regardé tous les suites dans l'ordre.
Le piège du MNL : Il existe un modèle plus simple et très populaire appelé Logit Multinomial (MNL). Le document prouve que pour ce modèle spécifique, regarder l'historique d'un client ne permet pas de mieux comprendre les préférences de la population générale que de simplement regarder la pile totale de reçus. Cependant, pour le modèle de chaîne de Markov qu'ils utilisent, l'historique fait une énorme différence. C'est comme dire : « Pour certains types d'énigmes, regarder les indices dans l'ordre aide ; pour d'autres, cela ne sert à rien. »

Le détective « hybride »

Les auteurs ont également créé un outil de détective hybride appelé Hyb. Dans le monde réel, l'historique d'un client est parfois désordonné. Peut-être qu'un client a commandé un burger, puis une salade, puis un burger à nouveau, d'une manière qui ne forme pas une ligne logique parfaite (un « cycle »).

L'algorithme Cus est strict : il ne fonctionne que si l'historique du client forme une ligne de préférence parfaite et logique.
L'algorithme Hyb est flexible : il prend les parties désordonnées et non linéaires de l'historique et les traite comme des points de données « indépendants », tout en conservant les parties propres et logiques comme une histoire connectée. Cela permet au modèle d'utiliser toutes les données sans être perturbé par les éléments désordonnés.

À quel point cela a-t-il fonctionné ?

Les auteurs n'ont pas seulement deviné ; ils ont mesuré.

La configuration : Ils ont créé 2 000 scénarios de test différents à l'aide de données synthétiques (faux clients) et ont également testé sur l'ensemble de données de sushis impliquant 5 000 individus.
Les résultats : Dans leurs simulations, les nouvelles méthodes (Cus et Hyb) ont systématiquement battu les anciennes méthodes.
- Lorsque les données étaient peu nombreuses (seulement 100 clients), les nouvelles méthodes étaient nettement meilleures pour prédire ce que les gens achèteraient.
- À mesure que le nombre de clients augmentait jusqu'à 2 000, les nouvelles méthodes continuaient de surpasser les anciennes, particulièrement pour prédire les choix de clients spécifiques.
- En termes d'argent (revenus), les nouvelles méthodes ont aidé les détaillants à prendre de meilleures décisions sur les articles à afficher. Par exemple, dans les tests de sushis, les nouveaux modèles ont atteint près de 100 % du revenu maximum possible dans de nombreux cas, alors que les anciens modèles restaient en retrait.

L'essentiel

Ce document suggère que si vous voulez comprendre comment les gens choisissent des choses, vous ne devez pas seulement regarder le « quoi » (le produit) ; vous devez regarder « l'histoire » (l'historique). En traitant les choix passés d'un client comme un voyage connecté plutôt que comme des événements aléatoires, vous pouvez construire une carte beaucoup plus précise de leurs préférences. Les auteurs ont découvert que cette approche fonctionne mieux en utilisant le modèle de la chaîne de Markov, transformant une pile de reçus désordonnée en un guide personnalisé et clair de ce que les clients voudront ensuite.

Résumé technique : Estimation, prédiction et optimisation de l'assortiment pour les modèles de choix à chaîne de Markov avec des données de panel

Énoncé du problème

La planification traditionnelle de l'assortiment repose sur des modèles de choix où les transactions historiques sont supposées être des tirages indépendants et identiquement distribués (i.i.d.) d'un modèle d'utilité aléatoire (RUM). Ce cadre utilise des probabilités de choix inconditionnelles, ignorant les corrélations entre les transactions effectuées par un même client. Cependant, la disponibilité des données de panel (historiques de transactions individuelles détaillés) remet en question cette hypothèse d'indépendance.

L'article traite de trois problèmes fondamentaux dans le contexte du modèle de choix par chaîne de Markov (MC) utilisant des données de panel :

Estimation des paramètres : Comment estimer les paramètres de la chaîne de Markov en incorporant les informations de transaction historiques spécifiques au client (préférences d'ordre partiel) plutôt qu'en traitant les transactions comme indépendantes.
Prédiction de choix conditionnel : Comment calculer la probabilité qu'un client choisisse un produit d'un ensemble d'offres, conditionnellement à son historique de transactions spécifique.
Optimisation de l'assortiment : Comment déterminer l'ensemble optimal de produits à proposer à un client spécifique (optimisation d'assortiment conditionnelle) afin de maximiser les revenus attendus, compte tenu de son historique.

Les auteurs examinent si l'exploitation de l'information de transaction individuelle améliore l'estimation au niveau de la population pour les modèles MC par rapport aux modèles Logit Multinomial (MNL) et aux méthodes d'estimation traditionnelles.

Méthodologie

Cadre théorique

Les auteurs formalisent le problème en utilisant l'information de préférence d'ordre partiel. L'historique de transaction d'un client $D_c$ est représenté par un graphe orienté acyclique (DAG) où les arcs indiquent les préférences par paires dérivées des choix observés.

Probabilité conditionnelle : La probabilité d'un choix $j$ dans l'ensemble $S$ , étant donné l'historique $D$ , est dérivée des extensions linéaires réduites (classements stricts cohérents avec le DAG observé).
MC vs MNL : L'article établit un écart théorique entre MC et MNL. Sous MNL, les données de panel n'ajoutent pas de puissance d'identification pour les paramètres si les probabilités de choix de la population sont connues. En revanche, pour MC, l'information au niveau du client améliore considérablement l'identifiabilité des paramètres, particulièrement lorsque l'ensemble des assortiments observés est limité.

Algorithmes : Expectation-Maximization (EM)

La principale contribution est le développement de nouveaux algorithmes EM pour estimer les paramètres MC ( $\lambda$ pour les états initiaux, $\rho$ pour les probabilités de transition) en utilisant des données de panel.

Algorithme Cus (Spécifique au client) :
- Hypothèse : L'ensemble de transactions de chaque client est cohérent avec au moins une liste de préférences stricte (pas de cycles).
- Mécanisme : L'algorithme traite la préférence stricte sous-jacente du client (représentée comme une extension linéaire réduite $\sigma$ ) et son état initial comme des variables latentes.
- Étape E : Calcule les valeurs attendues des variables latentes (indicateurs d'état initial et comptes de transition) conditionnellement au DAG observé et aux estimations actuelles des paramètres. Cela implique de calculer les probabilités de marches aléatoires cohérentes avec les extensions linéaires réduites.
- Étape M : Met à jour les paramètres $\lambda$ et $\rho$ en maximisant la log-vraisemblance attendue des données complètes, ce qui aboutit à des solutions sous forme fermée basées sur les comptes attendus.
Algorithme Hyb (Hybride) :
- Motivation : Les données réelles peuvent contenir des préférences cycliques ou des transactions incohérentes qui violent un DAG strict.
- Mécanisme : Hyb combine l'algorithme Cus (pour les transactions cohérentes avec un DAG) et l'algorithme EM traditionnel (pour les transactions indépendantes).
- Flexibilité : Il permet de traiter les transactions "violantes" (celles causant des cycles) comme des observations indépendantes dans la composante de vraisemblance traditionnelle, plutôt que de les écarter totalement. Cela capture l'information sur la distribution inconditionnelle de la population tout en exploitant la structure du DAG pour les historiques cohérents.

Complexité computationnelle

L'article présente des résultats de dureté pour la prédiction de choix conditionnel et l'optimisation d'assortiment. Bien que l'optimisation d'assortiment traditionnelle sous MC soit soluble en temps polynomial, les versions conditionnelles (CAO et TCAO) sont montrées comme étant informatiquement complexes. Cependant, les auteurs fournissent des expressions en forme fermée pour les probabilités de choix conditionnels sous MC, réduisant la charge de calcul par rapport aux RUM généraux.

Principales contributions

Initiation de l'étude des données de panel pour MC : À la connaissance des auteurs, il s'agit du premier cadre étudiant la modélisation de choix avec des données de panel spécifiquement sous le modèle de chaîne de Markov.
Nouveaux algorithmes EM : La proposition des algorithmes Cus et Hyb qui intègrent l'information de préférence basée sur l'ordre partiel des clients. Ces algorithmes surpassent l'algorithme EM traditionnel pour MC (S¸im¸sek et Topaloglu, 2018) et les références de base MNL basées sur l'ordre partiel (Jagabathula et Vulcano, 2018).
Écart d'identification théorique : Une démonstration que si les paramètres MNL peuvent être identifiés sans lier les transactions à des clients spécifiques (étant donné suffisamment de données d'assortiment), les paramètres MC bénéficient considérablement des données de panel, surtout dans les scénarios avec des observations d'assortiment limitées.
Paysage computationnel : Une clarification de la dureté et de la tractabilité computationnelle pour la prédiction de choix conditionnel et l'optimisation d'assortiment sous MC et MNL, complétant le cadre d'estimation.

Résultats expérimentaux

Les auteurs ont évalué leurs méthodes sur des jeux de données synthétiques et un jeu de données semi-synthétique dérivé des données de préférence de sushi (5 000 individus).

Métriques de performance : L'étude a utilisé la racine carrée de l'erreur quadratique moyenne (RMSE) pour la précision prédictive et les ratios de revenus pour la performance de décision.
Données synthétiques :
- Les modèles Cus-MC et Hyb-MC proposés ont systématiquement surpassé l'estimation MC traditionnelle, le MNL et les variantes de LC-MNL (Latent-Class MNL), particulièrement à mesure que le nombre de clients augmentait.
- L'amélioration était la plus marquée lorsque la distribution réelle était concentrée sur un petit nombre de listes de préférences (par exemple, Rank List avec 10 listes ou Mallows avec une forte concentration).
- L'incorporation des données de panel a généré des marges d'amélioration plus importantes pour l'estimation MC par rapport à l'estimation MNL, surtout avec de petites tailles de données.
Données Sushi :
- Les modèles basés sur MC ont généralement surpassé les modèles basés sur MNL en termes de ratios de revenus et de précision prédictive.
- Hyb-MC et Cus-MC ont atteint un revenu attendu proche de l'optimal dans la plupart des scénarios.
- Une exception a été notée dans le scénario de troncature "Top 5" où la performance du revenu conditionnel se dégradait avec l'augmentation de la taille des données, suggérant qu'une profondeur de transaction limitée (moins de choix supérieurs observés) peut restreindre la capacité à ajuster des structures MC complexes par les seules données de panel.

Signification et affirmations

L'article affirme que l'information au niveau du client est plus précieuse pour l'estimation de la chaîne de Markov que pour l'estimation MNL. En exploitant systématiquement les corrélations dans les historiques de transactions individuels, le cadre proposé améliore à la fois la précision prédictive et la performance de l'optimisation d'assortiment.

Les auteurs positionnent leur travail comme une étape fondamentale, en notant que :

Le cadre comble le fossé entre les modèles traditionnels de transactions indépendantes et la réalité des comportements clients corrélés.
L'algorithme Hyb offre une heuristique pratique pour les jeux de données réels présentant des préférences cycliques, permettant de conserver l'information qui serait autrement rejetée par les heuristiques strictes basées sur le DAG.
Les travaux futurs impliquent de tester ces algorithmes sur des données réelles avec des préférences cycliques et d'étendre le cadre à d'autres classes de modèles d'utilité aléatoire (RUM).

L'article maintient un ton modeste concernant ses affirmations, reconnaissant que bien que les résultats synthétiques soient solides, la validation par des données réelles (particulièrement concernant les préférences cycliques) reste une direction future nécessaire. Il ne revendique pas une supériorité universelle sur tous les modèles dans tous les contextes, mais souligne les conditions spécifiques (modèles MC, assortiments limités, disponibilité des données de panel) où les méthodes proposées offrent des avantages distincts.