🤖 machine learning

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

Este artigo introduz um novo framework para modelos de escolha de cadeia de Markov com dados em painel que aproveita informações de preferência de ordenação parcial para desenvolver algoritmos EM superiores para estimativa de parâmetros, ao mesmo tempo em que estabelece a complexidade computacional da previsão de escolha personalizada e da otimização de sortimento.

Autores originais: Yalcin Akcay, Gerardo Berbeglia, Young-San Lin

Publicado 2026-07-14

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Yalcin Akcay, Gerardo Berbeglia, Young-San Lin

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você é um detetive tentando descobrir o que um grupo de pessoas realmente gosta de comer. Antigamente, os detetives olhavam para uma pilha gigante de recibos de um restaurante. Eles assumiam que cada pedido era um palpite novo e independente, como jogar uma moeda para o alto. Se alguém pedia sushi, depois pizza, depois um hambúrguer, a matemática antiga tratava essas três escolhas como três eventos separados e desconexos.

Mas aqui está a reviravolta: as pessoas não são moedas. Se um cliente pede um rolo de atum apimentado, e depois pede um rolo de atum apimentado novamente, isso é uma pista! Isso sugere que eles realmente gostam de atum apimentado. Este artigo apresenta uma nova maneira de olhar para esses "recibos" (que os autores chamam de dados de painel) ao tratá-los como uma história conectada para cada cliente específico, em vez de uma pilha de papel aleatória.

A Nova Ferramenta do Detetive: A Cadeia de Markov

Os autores propõem o uso de uma ferramenta matemática específica chamada modelo de escolha de Cadeia de Markov (MC). Pense neste modelo como um "mapa de preferências". Em vez de apenas dizer "eu gosto de sushi", o modelo mapeia uma jornada. Ele pergunta: "Se eu estou pensando em sushi agora, qual é a probabilidade de eu pensar em sashimi a seguir? Eu pulo para o sashimi ou desisto e peço um refrigerante?"

A grande descoberta deste artigo é que, quando você tem o histórico de um cliente (seus dados de painel), desenhar esse "mapa de jornada" torna-se muito mais fácil e preciso. Os autores realizaram simulações (experimentos computacionais) e testaram seu método em um conjunto de dados do mundo real sobre as preferências de sushi de 5.000 pessoas. Eles descobriram que, ao usar o histórico do cliente para atualizar o mapa, seus novos algoritmos (Cus e Hyb) foram muito melhores em adivinhar o que as pessoas comprariam a seguir em comparação com os métodos antigos.

O Que os Métodos Antigos Erraram

O artigo argumenta explicitamente contra a ideia de que você pode simplesmente ignorar a conexão entre os pedidos passados de um único cliente.

O Mito da "Independência": Os autores mostram que, se você tratar cada pedido como um evento totalmente novo e aleatório (a maneira tradicional), você perde a "ordenação parcial" das preferências. É como tentar adivinhar o filme favorito de uma pessoa olhando para uma lista aleatória de filmes que ela assistiu, sem perceber que ela assistiu a todas as sequências em ordem.
A Armadilha do MNL: Existe um modelo muito popular e mais simples chamado Logit Multinomial (MNL). O artigo prova que, para este modelo específico, olhar para o histórico de um cliente não ajuda a entender melhor as preferências da população geral do que apenas olhar para a pilha total de recibos. No entanto, para o modelo de Cadeia de Markov que eles estão usando, o histórico faz uma enorme diferença. É como dizer: "Para alguns tipos de enigmas, olhar para as pistas em ordem ajuda; para outros, não ajuda."

O Detetive "Híbrido"

Os autores também criaram uma ferramenta de detetive "híbrida" chamada Hyb. No mundo real, às vezes o histórico de um cliente é bagunçado. Talvez ele tenha pedido um hambúrguer, depois uma salada, depois um hambúrguer novamente, de uma forma que não forma uma linha lógica perfeita (um "ciclo").

O algoritmo Cus é rigoroso: ele só funciona se o histórico do cliente formar uma linha de preferência perfeita e lógica.
O algoritmo Hyb é flexível: ele pega as partes bagunçadas e não lineares do histórico e as trata como pontos de dados "independentes", enquanto mantém as partes limpas e lógicas como uma história conectada. Isso permite que o modelo use todos os dados sem se confundir com as partes bagunçadas.

O Quão Bem Funcionou?

Os autores não apenas adivinharam; eles mediram.

A Configuração: Eles criaram 2.000 diferentes cenários de teste usando dados sintéticos (clientes fictícios) e também testaram no conjunto de dados de sushi envolvendo 5.000 indivíduos.
Os Resultados: Em suas simulações, os novos métodos (Cus e Hyb) superaram consistentemente os métodos antigos.
- Quando os dados eram pequenos (apenas 100 clientes), os novos métodos eram significativamente melhores em prever o que as pessoas comprariam.
- À medida que o número de clientes crescia para 2.000, os novos métodos continuavam a superar os antigos, especialmente na previsão de escolhas específicas dos clientes.
- Em termos de dinheiro (receita), os novos métodos ajudaram os varejistas a tomar melhores decisões sobre quais itens exibir. Por exemplo, nos testes de sushi, os novos modelos alcançaram quase 100% da receita máxima possível em muitos casos, enquanto os modelos mais antigos ficaram para trás.

A Conclusão

Este artigo sugere que, se você quiser entender como as pessoas escolhem coisas, não deve olhar apenas para o "quê" (o produto); você deve olhar para a "história" (o histórico). Ao tratar as escolhas passadas de um cliente como uma jornada conectada, em vez de eventos aleatórios, você pode construir um mapa muito mais nítido de suas preferências. Os autores descobriram que essa abordagem funciona melhor ao usar o modelo de Cadeia de Markov, transformando uma pilha bagunçada de recibos em um guia claro e personalizado para o que os clientes desejarão a seguir.

Resumo Técnico: Estimativa, Predição e Otimização de Sortimento para Modelos de Escolha de Cadeia de Markov com Dados de Painel

Definição do Problema

O planejamento de sortimento tradicional baseia-se em modelos de escolha onde as transações históricas são assumidas como amostras independentes e identicamente distribuídas (i.i.d.) de um modelo de utilidade aleatória (RUM). Este framework utiliza probabilidades de escolha incondicionais, ignorando as correlações entre as transações feitas pelo mesmo cliente. No entanto, a disponibilidade de dados de painel (históricos detalhados de transações individuais) desafia essa suposição de independência.

O artigo aborda três problemas centrais no contexto do modelo de escolha de Cadeia de Markov (MC) utilizando dados de painel:

Estimativa de Parâmetros: Como estimar os parâmetros da MC incorporando informações de transações históricas específicas do cliente (preferências de ordenação parcial) em vez de tratar as transações como independentes.
Predição de Escolha Condicional: Como computar a probabilidade de um cliente escolher um produto de um conjunto de oferta, condicionado ao seu histórico de transações específico.
Otimização de Sortimento: Como determinar o conjunto ideal de produtos a serem oferecidos a um cliente específico (otimização de sortimento condicional) para maximizar a receita esperada, dada a sua história.

Os autores investigam se a exploração da informação de transação individual melhora a estimativa de nível populacional para modelos MC em comparação com modelos Multinomial Logit (MNL) e métodos de estimativa tradicionais.

Metodologia

Estrutura Teórica

Os autores formalizam o problema utilizando informação de preferência de ordenação parcial. O histórico de transações de um cliente $D_c$ é representado como um Grafo Acíclico Dirigido (DAG) onde os arcos indicam preferências pareadas derivadas das escolhas observadas.

Probabilidade Condicional: A probabilidade de uma escolha $j$ do conjunto $S$ , dado o histórico $D$ , é derivada de extensões lineares reduzidas (rankings estritos consistentes com o DAG observado).
MC vs. MNL: O artigo estabelece uma lacuna teórica entre MC e MNL. Sob o MNL, os dados de painel não adicionam poder de identificação para os parâmetros se as probabilidades de escolha populacionais forem conhecidas. Em contraste, para MC, a informação ao nível do cliente melhora significamente a identificabilidade dos parâmetros, particularmente quando o conjunto de assortamentos observados é limitado.

Algoritmos: Expectation-Maximization (EM)

A principal contribuição é o desenvolvimento de novos algoritmos EM para estimar os parâmetros da MC ( $\lambda$ para estados iniciais, $\rho$ para probabilidades de transição) usando dados de painel.

Algoritmo Cus (Customer-specific/Específico do Cliente):
- Suposição: O conjunto de transações de cada cliente é consistente com pelo menos uma lista de preferência estrita (sem ciclos).
- Mecanismo: O algoritmo trata a preferência estrita subjacente do cliente (representada como uma extensão linear reduzida $\sigma$ ) e seu estado inicial como variáveis latentes.
- E-Step: Computa os valores esperados das variáveis latentes (indicadores de estado inicial e contagens de transição) condicionados ao DAG observado e às estimativas atuais dos parâmetros. Isso envolve calcular probabilidades de caminhadas aleatórias consistentes com as extensões lineares reduzidas.
- M-Step: Atualiza os parâmetros $\lambda$ e $\rho$ maximizando a log-verossimilhança esperada dos dados completos, resultando em soluções de forma fechada baseadas nas contagens esperadas.
Algoritmo Hyb (Híbrido):
- Motivação: Dados do mundo real podem conter preferências cíclicas ou transações inconsistentes que violam um DAG estrito.
- Mecanismo: O Hyb combina o algoritmo Cus (para transações consistentes com um DAG) e o algoritmo EM tradicional (para transações independentes).
- Flexibilidade: Ele permite que transações "violadoras" (aquelas que causam ciclos) sejam tratadas como observações independentes no componente de verossimilhança tradicional, em vez de serem descartadas inteiramente. Isso captura informações sobre a distribuição populacional incondicional enquanto ainda aproveita a estrutura do DAG para históricos consistentes.

Complexidade Computacional

O artigo apresenta resultados de dureza para predição de escolha condicional e otimização de sortimento. Embora a otimização de sortimento tradicional sob MC seja solucionável em tempo polinomial, as versões condicionais (CAO e TCAO) mostram-se computacionalmente desafiadoras. No entanto, os autores fornecem expressões de forma fechada para probabilidades de escolha condicional sob MC, reduzindo a carga computacional em comparação com RUMs gerais.

Principais Contribuições

Iniciação do Estudo de Painel para MC: Tanto quanto os autores sabem, este é o primeiro framework para estudar modelagem de escolha com dados de painel especificamente sob o modelo de Cadeia de Markov.
Novos Algoritmos EM: A proposta dos algoritmos Cus e Hyb que incorporam informações de preferência de ordenação parcial do cliente. Esses algoritmos superam o algoritmo EM tradicional para MC (S¸im¸sek e Topaloglu, 2018) e os benchmarks de MNL baseados em ordenação parcial (Jagabathula e Vulcano, 2018).
Lacuna de Identificação Teórica: Uma demonstração de que, enquanto os parâmetros MNL podem ser identificados sem vincular transações a clientes específicos (dado um conjunto de assortamentos suficiente), os parâmetros de MC beneficiam-se significativamente de dados de painel, especialmente em cenários com observações de assortamento limitadas.
Panorama Computacional: Um esclarecimento da dureza computacional e da tratabilidade para predição de escolha condicional e otimização de sortimento sob MC e MNL, complementando o framework de estimativa.

Resultados Experimentais

Os autores avaliaram seus métodos em datasets sintéticos e um dataset semi-sintético derivado dos dados de preferência de sushi (5.000 indivíduos).

Métricas de Desempenho: O estudo utilizou Soft Root Mean Square Error (RMSE) para precisão preditiva e Razões de Receita (Revenue Ratios) para desempenho de tomada de decisão.
Dados Sintéticos:
- Os modelos propostos Cus-MC e Hyb-MC superaram consistentemente a estimativa de MC tradicional, MNL e variantes de Latent-Class MNL (LC-MNL), particularmente à medida que o número de clientes aumentava.
- A melhoria foi mais pronunciada quando a distribuição da verdade fundamental estava concentrada em um número menor de listas de preferência (ex: Rank List com 10 listas ou Mallows com alta concentração).
- A incorporação de dados de painel gerou margens de melhoria maiores para a estimativa de MC em comparação com a estimativa de MNL, especialmente com tamanhos de dados menores.
Dados de Sushi:
- Modelos baseados em MC geralmente superaram modelos baseados em MNL em termos de razões de receita e precisão preditiva.
- Hyb-MC e Cus-MC alcançaram receita esperada próxima da ótima na maioria dos cenários.
- Uma exceção foi observada no cenário de truncamento "Top 5", onde o desempenho da receita condicional degradou com tamanhos de dados maiores, sugerindo que a profundidade limitada de transação (menos escolhas principais observadas) pode restringir a capacidade de ajustar estruturas complexas de MC apenas com dados de painel.

Significância e Alegações

O artigo afirma que a informação ao nível do cliente é mais valiosa para a estimativa de Cadeia de Markov do que para a de MNL. Ao sistematizar a exploração das correlações nos históricos de transações individuais, o framework proposto melhora tanto a precisão preditiva quanto o desempenho da otimização de sortimento.

Os autores posicionam seu trabalho como um passo fundamental, observando que:

O framework preenche a lacuna entre os modelos tradicionais de transações independentes e a realidade do comportamento correlacionado dos clientes.
O algoritmo Hyb oferece uma heurística prática para datasets do mundo real onde as preferências podem ser cíclicas, permitindo a retenção de informações que seriam descartadas por heurísticas estritas de DAG.
Trabalhos futuros envolvem testar esses algoritmos em dados do mundo real com preferências cíclicas e estender o framework para outras classes de Modelos de Utilidade Aleatória (RUM).

O artigo mantém um tom modesto em relação às suas alegações, reconhecendo que, embora os resultados sintéticos sejam fortes, a validação no mundo real (particularmente em relação a preferências cíclicas) permanece uma direção futura necessária. Não se propõe uma superioridade universal sobre todos os modelos em todos os contextos, mas destaca condições específicas (modelos MC, assortamentos limitados, disponibilidade de dados de painel) onde os métodos propostos oferecem vantagens distintas.