libhmm: A Modern C++20 Library for Hidden Markov Models with Correct MLE Emission M-Steps

Resumo Técnico: libhmm – Uma Biblioteca Moderna C++20 para Modelos Ocultos de Markov

Declaração do Problema
O artigo identifica duas lacunas principais no cenário atual de software para Modelos Ocultos de Markov (HMM):

1. Falta de Infraestrutura C++ Embarcável: As ferramentas dominantes de HMM (por exemplo, moveHMM, fHMM, hmmlearn) dependem de tempos de execução R ou Python, tornando-as inadequadas para incorporação em sistemas de produção C++ sem sobrecarga significativa. As bibliotecas existentes em C/C++ (por exemplo, GHMM, HMMLib) estão ou abandonadas, carecem de idiomatismos modernos de C++ ou são restritas a emissões discretas.
2. Etapas M de Emissão Incorretas: Muitos pacotes existentes utilizam aproximações do Método dos Momentos (MOM) para a etapa M da distribuição de emissão no algoritmo de Baum-Welch quando Estimadores de Máxima Verossimilhança (MLE) de forma fechada não estão disponíveis. Os autores argumentam que isso é uma conveniência computacional que compromete a correção estatística, particularmente para distribuições como Gama, Beta, Weibull, Binomial Negativa e t de Student, onde o MOM pode convergir para pontos fixos diferentes do MLE exato.

Metodologia
O artigo descreve o libhmm, uma biblioteca C++20 sem dependências projetada para estimação de parâmetros, decodificação de sequências e seleção de modelos.

• Algoritmos de Inferência: A biblioteca implementa os algoritmos completos forward-backward e Viterbi no espaço de logaritmos. Diferentemente de algoritmos escalados que exigem constantes de normalização explícitas (que podem causar underflow), o libhmm utiliza a operação numericamente estável log-sum-exp em todo o processo, garantindo estabilidade incondicional para sequências de comprimento arbitrário.
• Distribuições de Emissão: A biblioteca suporta dezesseis distribuições de emissão contínuas e discretas.
  • MLE de Forma Fechada: Implementado para Gaussiana, Log-normal, Exponencial, Poisson, Rayleigh, Uniforme, Discreta e Von Mises (direção média).
  • MLE Newton-Raphson: Implementado para Gama, Beta, Weibull, Binomial Negativa e Von Mises (parâmetro de concentração). Estes utilizam estimativas MOM como sementes e tipicamente convergem em 2–4 iterações.
  • Algoritmo ECME: Para a distribuição t de Student de localização-escala, a biblioteca implementa o algoritmo Expectation/Conditional Maximization Either (ECME) (Liu e Rubin, 1994). Isso aborda a conhecida falha da estimação de curtose MOM em convergir para o verdadeiro MLE para caudas próximas à Gaussiana.
• Arquitetura:
  • Zero Dependências: A biblioteca compila apenas com a biblioteca padrão C++20, evitando dependências externas como Eigen ou GSL.
  • Polimorfismo vs. Templates: O design utiliza polimorfismo em tempo de execução (métodos virtuais) para distribuições de emissão para permitir a mistura de tipos de distribuição dentro de um único modelo e simplificar a serialização/ligações Python, aceitando uma pequena sobrecarga de chamada virtual.
  • Aceleração SIMD: O despacho em tempo de compilação fornece suporte a AVX-512, AVX2, SSE2 e ARM NEON para o laço interno forward-backward, com fallbacks escalares.
  • Design em Camadas: O código é organizado em oito camadas com fluxo de dependência estritamente unidirecional para garantir manutenibilidade e grafos de dependência auditáveis.

Contribuições Principais

1. Etapas M de MLE Corretas: A derivação e implementação de estimadores de máxima verossimilhança corretos para dezesseis distribuições, substituindo especificamente aproximações MOM por métodos Newton-Raphson e ECME.
2. Estabilidade no Espaço de Logaritmos: Uma implementação completa da decodificação forward-backward e Viterbi no espaço de logaritmos para prevenir underflow numérico sem a complexidade de contabilidade do redimensionamento.
3. Implementação Moderna C++20: Uma biblioteca embarcável, sem dependências, que suporta sistemas de construção modernos (CMake) e idiomatismos, preenchendo o vazio deixado por bibliotecas legadas C/C++ abandonadas.
4. Ligações Python: Um pacote companheiro, pylibhmm, que envolve a API C++ via nanobind para fornecer capacidades de etapa M corretas aos usuários Python.

Resultados e Benchmarks
O artigo compara o libhmm com pacotes de referência R estabelecidos e outras bibliotecas C/C++ em cinco benchmarks de dados reais e dados sintéticos:

• Vazão (Sintético): Em modelos discretos, o libhmm é mais lento que o HMMLib (aproximadamente 2,8×) e o GHMM (aproximadamente 4,9×) na vazão bruta forward-backward. Os autores atribuem isso ao uso do libhmm de espaço de logaritmos (vs. escalado) e polimorfismo em tempo de execução. No entanto, os autores observam que essa lacuna diminui significativamente para distribuições contínuas, onde a avaliação de emissão domina o cálculo.
• Precisão Estatística (Dados Reais):
  • Regimes Financeiros DAX: Em um HMM t de Student de 3 estados para retornos do DAX, a implementação ECME alcançou uma verossimilhança logarítmica de 17.487,2, superando a referência fHMM (17.485,7) e a implementação anterior baseada em MOM (17.334,9) em 152 nats. Isso confirma que o ECME encontra uma solução superior em comparação ao MOM.
  • Movimento de Alces: Parâmetros ajustados a rastreamentos GPS corresponderam aos valores de referência do moveHMM com diferença <2%.
  • Direção do Vento: Um HMM Von Mises lidou corretamente com limites de dados circulares (0°/360°), enquanto uma aproximação Normal (usada por HiddenMarkov) resultou em 100% de classificação errônea para observações próximas ao limite.
• Desempenho (Dados Reais): O libhmm demonstrou acelerações significativas sobre pacotes R devido à execução compilada em C++ e à falta de sobrecarga de interpretador (por exemplo, 23× mais rápido em dados de movimento de alces, 5–12× mais rápido em regimes DAX).

Significado e Alegações
O artigo posiciona o libhmm como uma ferramenta distinta no ecossistema HMM: é a única biblioteca C++ que combina amplo suporte a distribuições (16 tipos), implementações de etapa M estatisticamente corretas (ECME/Newton-Raphson) e convenções de construção modernas e sem dependências.

Os autores reconhecem explicitamente compensações arquiteturais: a biblioteca sacrifica a vazão bruta em modelos discretos (onde GHMM/HMMLib se destacam) para ganhar usabilidade da API, amplitude de distribuições e correção numérica. O significado principal reside em fornecer uma alternativa "correta" e "embarcável" para pesquisadores e engenheiros integrando HMMs em pipelines de produção C++, particularmente para distribuições de emissão contínuas onde aproximações MOM padrão são estatisticamente subótimas. A biblioteca é lançada sob a licença MIT com ligações Python disponíveis via pylibhmm.