Soft-MSM: Differentiable Context-Aware Elastic Alignment for Time Series

1. Declaração do Problema

A aprendizagem de máquina para séries temporais (TSML) depende fortemente de medidas de distância para lidar com desalinhamentos temporais entre sequências. Distâncias elásticas, como a Warping Dinâmica do Tempo (DTW) e Move-Split-Merge (MSM), abordam isso encontrando caminhos de alinhamento ótimos que esticam ou comprimem os eixos temporais.

• A Limitação das Distâncias Elásticas: Embora eficazes para tarefas como agrupamento e classificação, as distâncias elásticas tradicionais são não diferenciáveis. Isso impede seu uso direto como funções de perda em otimização baseada em gradiente (por exemplo, redes neurais, média iterativa).
• A Limitação das Soluções Existentes: O Soft-DTW foi introduzido para tornar a DTW diferenciável, substituindo o mínimo rígido em sua recursão por um operador de soft-mínimo suave. No entanto, o Soft-DTW não pode ser estendido diretamente para outras distâncias elásticas como a MSM. A MSM é frequentemente superior à DTW em desempenho porque utiliza custos de transição conscientes do contexto (penalidades de divisão/fusão) que dependem da ordenação local de três valores. A natureza por partes da função de custo da MSM cria regiões não suaves que as abordagens padrão de soft-mínimo não conseguem diferenciar facilmente.

2. Metodologia: Soft-MSM

Os autores propõem o Soft-MSM, um relaxamento suave e diferenciável da distância Move-Split-Merge. O desafio central foi tornar o custo de transição da MSM diferenciável, preservando sua estrutura consciente do contexto.

Principais Inovações Técnicas:

1. Surrogado Portão Suave para Custos de Transição:

   • A função de custo original da MSM aplica uma penalidade fixa $c$ se um ponto $x$ estiver entre os vizinhos $y$ e $z$, e uma penalidade adicional caso contrário. Esta é uma função por partes com fronteiras não diferenciáveis.
   • Solução: Os autores introduzem uma função de portão entre-suave $g(x, y, z)$ usando uma aproximação semelhante ao tangente hiperbólico:
     $$g(x, y, z) = \frac{1}{2} \left( 1 - \frac{u}{\sqrt{u^2 + \epsilon}} \right), \quad \text{onde } u = (x-y)(x-z)$$
   • Este portão transita suavemente entre 1 (quando $x$ está entre $y$ e $z$) e 0 (caso contrário), permitindo que os gradientes fluam através da fronteira de decisão.
   • O custo de transição é redefinido como:
     $$\text{trans}_\gamma(x, y, z; c) = c + (1 - g(x, y, z)) \cdot \text{softmin}_\gamma((x-y)^2, (x-z)^2)$$
   • Eles também substituem a diferença absoluta na distância local por uma diferença quadrada para garantir diferenciabilidade em $x=y$.

2. Recursões Direta e Inversa:

   • Passo Direto: Calcula a matriz de custo acumulada $C$ usando um operador de soft-mínimo ($\text{softmin}_\gamma$) em vez do mínimo rígido, integrando os novos custos de transição suaves.
   • Passo Inverso: Deriva a matriz de alinhamento suave $A$ e o Jacobiano (gradiente) em relação à série temporal de entrada. O gradiente é decomposto em contribuições das arestas diagonais (correspondência), verticais (divisão) e horizontais (fusão), ponderadas pelas probabilidades de alinhamento.

3. Propriedades Teóricas:

   • Diferenciabilidade: Provado ser continuamente diferenciável para $\gamma > 0$ e $\epsilon > 0$.
   • Comportamento Limitante: À medida que $\gamma \to 0$ e $\epsilon \to 0$, o Soft-MSM converge pontualmente para a recursão MSM padrão (com desvios quadrados).
   • Metricidade: O Soft-MSM não é uma métrica (viola a identidade dos indiscerníveis e pode ser negativo). Para abordar isso, os autores propõem uma formulação corrigida por divergência (análoga à divergência Soft-DTW) para garantir não-negatividade e distância zero para auto-comparação.
   • Complexidade: Mantém a mesma complexidade de tempo e espaço $O(m^2)$ que a MSM padrão.

3. Principais Contribuições

• Primeira MSM Diferenciável: A primeira formulação de uma versão diferenciável da distância Move-Split-Merge, permitindo seu uso em aprendizagem baseada em gradiente.
• Novo Portão Suave: Uma derivação matemática de uma função de portão suave que lida com as penalidades de divisão/fusão dependentes do contexto da MSM sem perder os benefícios estruturais da distância original.
• Gradientes de Forma Fechada: Derivação da transformação do Jacobiano permitindo a otimização direta de sequências de séries temporais usando Soft-MSM.
• Implementação: O método é implementado no toolkit de código aberto aeon, apoiando a reprodutibilidade.

4. Resultados Experimentais

Os autores avaliaram o Soft-MSM em 112 conjuntos de dados de séries temporais UCR em três cenários principais:

A. Média de Séries Temporais (Baricentro)

• Objetivo: Encontrar uma série temporal representativa (baricentro) que minimize a soma das distâncias para um conjunto de séries de entrada.
• Comparação: Baricentro Soft-MSM (Soft-MBA) vs. Baricentro MSM padrão (MBA) e Baricentro MBA de Subgradiente Estocástico (SSG-MBA).
• Resultado: O Soft-MBA alcançou perda Fréchet MSM menor do que tanto o MBA quanto o SSG-MBA em 97,2% a 100% dos conjuntos de dados (dependendo do parâmetro de suavização $\gamma$). Superou significativamente as contrapartes rígidas, demonstrando que o relaxamento diferenciável leva a uma melhor convergência e menor perda.

B. Agrupamento de Séries Temporais

• Objetivo: Usar k-means com centróides elásticos.
• Comparação: Soft-MBA vs. Baricentro Soft-DTW (Soft-DBA), k-Shape e k-means Euclidiano.
• Resultado:
  • O Soft-MBA superou significativamente o Soft-DBA tanto em Precisão de Agrupamento quanto no Índice Rand Ajustado (ARI).
  • O Soft-MBA foi competitivo com o k-Shape (uma linha de base forte), apesar de usar uma medida de similaridade fundamentalmente diferente.
  • O Soft-MBA mostrou maior robustez ao parâmetro de suavização $\gamma$ em comparação com o Soft-DBA.

C. Classificação por Vizinho do Centróide

• Objetivo: Classificar séries temporais com base na distância para protótipos de classe (baricentros).
• Resultado: Classificadores usando protótipos Soft-MBA alcançaram precisão e precisão balanceada significativamente maiores do que aqueles usando protótipos Soft-DBA.
• Análise Qualitativa: No conjunto de dados CRICKETX, o Soft-MBA produziu protótipos de classe mais suaves e interpretáveis (capturando claramente o sinal de "seis corridas") em comparação com os protótipos ruidosos gerados por outros métodos.

5. Significado e Impacto

• Ponte entre Lacunas: O Soft-MSM conecta com sucesso a lacuna entre distâncias elásticas de alto desempenho (como MSM) e frameworks modernos de aprendizagem profunda baseados em gradiente.
• Superioridade sobre Soft-DTW: Os resultados sugerem que, para muitas tarefas de séries temporais, a MSM é uma medida de distância superior à DTW, e torná-la diferenciável produz resultados melhores do que simplesmente usar Soft-DTW.
• Aplicabilidade Ampla: O método abre caminho para o uso de perdas baseadas em MSM em:
  • Previsão de séries temporais profunda.
  • Modelos generativos para aumento de dados.
  • Alinhamento e segmentação fracamente supervisionados.
  • Aprendizagem de representação (por exemplo, Series2Vec).
• Viés Indutivo: Fornece um novo viés indutivo baseado em operações de "mover, dividir e fundir", que é particularmente útil para dados de séries temporais constantes por partes ou orientados a eventos.

Em conclusão, o Soft-MSM é um avanço significativo na aprendizagem de máquina para séries temporais, oferecendo uma distância elástica diferenciável e consciente do contexto que supera as abordagens existentes baseadas em Soft-DTW em tarefas de média, agrupamento e classificação.