Extending Causal Metamodeling to a non-Markovian Queue

Resumo Técnico: Estendendo a Metamodelação Causal para uma Fila Não-Markoviana

Definição do Problema
A metamodelação de simulação de eventos discretos aproxima comportamentos complexos de simulação para permitir a previsão rápida e a otimização, uma capacidade crítica para aplicações de "gêmeo digital". Redes Bayesianas Dinâmicas Modulares (MDBNs) foram previamente introduzidas como uma classe de metamodelos causais capazes de responder a um rico conjunto de consultas probabilísticas e causais (PCQs) a partir de um único modelo treinado. No entanto, implementações anteriores de MDBNs foram restritas a sistemas Markovianos (ex: filas M/M/1), onde o estado futuro depende apenas do estado atual. Sistemas do mundo real frequentemente empregam distribuições de tempo de chegada ou de serviço gerais (ex: Gamma, Weibull, Beta) que violam a propriedade de Markov. Nesses cenários não-Markovianos, o sistema carrega memória (ex: o tempo restante até a próxima conclusão de serviço depende de quanto tempo o serviço atual está em progresso), tornando a estrutura padrão de duas fatias de tempo da MDBN insuficiente para uma modelagem precisa.

Metodologia
Este artigo inicia a extensão das MDBNs para filas não-Markovianas, focando especificamente na fila G/M/1 (chegadas gerais, serviço exponencial). A abordagem proposta aborda a perda da propriedade de Markov através de três mecanismos técnicos primários:

1. Aproximação por Tipo de Fase (Phase-Type Approximation): Para recuperar a estrutura Markoviana necessária pelas MDBNs, a distribuição de chegada geral (não-Markoviana) é aproximada usando distribuições de tipo de fase. Especificamente, os autores empregam Distribuições de Erlang Generalizadas (GEDs), que modelam o tempo de chegada como uma sequência de estágios exponenciais. Isso permite que o sistema seja representado como uma cadeia de Markov de tempo contínuo (CTMC) ao aumentar o espaço de estados com uma variável de fase $S$ que rastreia o estágio atual do processo de chegada.

   • Para distribuições Gamma, é utilizada uma construção GED de forma fechada que combina os dois primeiros momentos.
   • Para distribuições Weibull e Beta, uma abordagem de correspondência de momentos é empregada, resolvendo equações não lineares ou otimização para minimizar a divergência de Jensen-Shannon.

2. Estrutura MDBN Aumentada: A MDBN é modificada para incluir a variável de fase $S$ ao lado do comprimento da fila $L$. As dinâmicas de transição são definidas de tal forma que $S(j+1)$ depende de $S(j)$ e dos parâmetros da distribuição, enquanto $L(j+1)$ depende de $L(j)$, $S(j)$ e da taxa de serviço $\mu$. Isso restaura a estrutura de dependência de duas fatias de tempo necessária para a inferência de MDBN.

3. Aprendizado Eficiente e Seleção de Parâmetros:

   • Intervalo de Amostragem Ótimo: Ao contrário de trabalhos anteriores que ajustavam empiricamente o intervalo de amostragem $\delta$, este artigo deriva $\delta_{optimal}$ analiticamente usando a teoria da discretização de CTMC. O intervalo é escolhido para garantir que a matriz de transição de tempo discreto resultante seja válida e limitada, minimizando o elemento diagonal máximo da matriz geradora infinitesimal $Q$ através do espaço de parâmetros.
   • Extrapolação de Parâmetros: Para abordar o desafio de escalabilidade na estimativa de Distribuições de Probabilidade Condicional (CPDs) para espaços de estados de alta dimensão, os autores introduzem a "extrapolação de parâmetros". Observando que a distribuição das transições de comprimento de fila para $L(j) = \ell$ é aproximadamente uma versão deslocada da distribuição para $L(j) = \ell-1$, o método agrupa dados para $\ell > 1$. Uma única distribuição é aprendida e então deslocada para popular as entradas de CPD para comprimentos de fila mais altos, reduzindo significativamente o número de parâmetros a serem estimados e melhorando a eficiência dos dados.

Principais Contribuições
O artigo apresenta três contribuições inovadoras para o campo da metamodelação de simulação:

1. Extensão Estrutural: Descreve modificações estruturais para MDBNs que acomodam o aumento da complexidade de estado das filas não-Markovianas, mantendo a inferência tratável.
2. Eficiência de Aprendizado: Apresenta métodos para melhorar o aprendizado de CPD, incluindo aproximações de tipo de fase eficazes, a técnica inovadora de "extrapolação de parâmetros" e uma abordagem teoricamente fundamentada para selecionar o intervalo de amostragem ideal.
3. Validação Empírica: Fornece a primeira aplicação de técnicas de modelos gráficos causais para a metamodelação de simulação não-Markoviana, demonstrando que as MDBNs podem produzir respostas precisas para PCQs para filas G/M/1.

Resultados Experimentais
Os autores avaliaram a MDBN estendida em uma fila G/M/1 com distribuições de chegada Gamma, Weibull e Beta. A avaliação envolveu 500 PCQs, incluindo consultas de condição, intervenção de parâmetro e intervenção de comprimento de fila. O ground truth foi estabelecido via 50.000 replicações de Monte Carlo por consulta.

• Precisão: A MDBN produziu respostas precisas em todas as distribuições. A fila Weibull/M/1 apresentou o melhor desempenho (média da Distância de Jensen-Shannon [JSD] = 0,166), enquanto a fila Beta/M/1 foi mais desafiadora (média JSD = 0,236) devido à complexidade de aproximar seu suporte limitado. Estatísticas descritivas (comprimento médio da fila e intervalo interquartil) acompanharam de perto os valores do ground truth, com Erros Absolutos Médios (MAE) geralmente abaixo de 1,3.
• Eficiência: O resultado mais significativo é a aceleração da inferência. Os tempos de inferência da MDBN foram aproximadamente quatro ordens de magnitude mais rápidos do que a simulação direta de Monte Carlo (ex: ~0,05 segundos vs. ~600–1600 segundos por consulta). Mesmo com a paralelização da simulação, a MDBN permaneceu pelo menos uma ordem de magnitude mais rápida.

Significância e Alegações
O artigo afirma fornecer a primeira técnica de metamodelação causal para sistemas não-Markovianos. Ao estender com sucesso as MDBNs para o cenário G/M/1, os autores demonstram que o método de fases pode preencher a lacuna entre os requisitos teóricos dos modelos gráficos causais e as realidades práticas da simulação não-Markoviana. O trabalho estabelece que é possível equilibrar a precisão da metamodelação com a tratabilidade em contextos não-Markovianos, oferecendo uma ferramenta para análise rápida de "e se" (what-if) e otimização em sistemas onde a simulação tradicional é lenta demais para a tomada de decisão iterativa. As técnicas descritas são observadas como aplicáveis à classe mais ampla de filas G/G/1, sugerindo um caminho para modelar sistemas não-Markovianos ainda mais complexos no futuro.