Classificação Temporal Conexionista (CTC)

Visão geral: por que o CTC existe

Em muitos problemas de sequência a sequência (sequence-to-sequence), temos entradas muito mais longas do que saídas, e não conhecemos o alinhamento entre elas.

Um exemplo canônico é o reconhecimento automático de fala (automatic speech recognition, ASR):

Entrada: uma sequência de quadros de características acústicas (acoustic feature frames) (por exemplo, quadros de 10 ms), comprimento (T) (frequentemente centenas ou milhares).
Saída: uma sequência de tokens (tokens) (caracteres, subpalavras (subwords) ou fragmentos de palavra (wordpieces)), comprimento (U) (frequentemente dezenas).
Informação ausente: quais quadros correspondem a qual token de saída.

A Classificação Temporal Conexionista (Connectionist Temporal Classification, CTC) é um objetivo de treinamento (e a estrutura de decodificação associada) que permite treinar um modelo de sequência acústica sem rótulos em nível de quadro (frame-level labels), somando sobre todos os alinhamentos monotônicos válidos entre quadros de entrada e tokens de saída.

O CTC é amplamente usado em sistemas modernos de ASR (frequentemente com codificadores Transformer ou Conformer), assim como em reconhecimento de escrita e reconhecimento óptico de caracteres (optical character recognition, OCR).

Quando o CTC é uma boa opção

O CTC assume que o alinhamento entre passos de tempo de entrada e tokens de saída é:

Monotônico (da esquerda para a direita): os tokens de saída ocorrem na mesma ordem conforme o tempo avança.
Muitos-para-um: múltiplos quadros podem corresponder a um único token.
Com quadros “sem rótulo”: muitos quadros podem não corresponder a nada (silêncio, transições).

Isso combina bem com fala: a evidência fonética para um caractere/subpalavra tende a aparecer ao longo de um intervalo de quadros, intercalada com quadros que não emitem nada.

Se você precisa de reordenação não monotônica (por exemplo, tradução automática), o CTC geralmente não é apropriado; modelos sequência a sequência baseados em atenção (attention-based) são mais comuns (veja Sequence-to-Sequence Learning).

O símbolo em branco e “caminhos”

O CTC introduz um símbolo em branco (blank symbol) (frequentemente escrito como (\varnothing) ou “_”) que significa “não emitir nada neste passo de tempo”.

Defina:

Vocabulário de rótulos (labels) (tokens): (\mathcal{V})
Vocabulário estendido: (\mathcal{V}' = \mathcal{V} \cup {\varnothing})
Comprimento da entrada: (T)
Sequência-alvo de rótulos: (\mathbf{y} = (y_1, \dots, y_U)), onde (y_u \in \mathcal{V})

Um modelo CTC (tipicamente um codificador neural (neural encoder)) produz uma distribuição sobre (\mathcal{V}') em cada passo de tempo: [ \mathbf{p}_t(k) = P(\pi_t = k \mid \mathbf{x}) \quad \text{para } t=1..T, ; k \in \mathcal{V}' ] onde (\pi_t) é o símbolo emitido no passo de tempo (t). A sequência de comprimento (T) (\boldsymbol{\pi} = (\pi_1,\dots,\pi_T)) é chamada de caminho (path).

O colapso do CTC (mapeando caminhos para sequências de rótulos)

O CTC define um mapeamento determinístico muitos-para-um (B(\cdot)) de caminhos para sequências de rótulos:

Mesclar símbolos repetidos que são adjacentes (por exemplo, a a a → a)
Remover brancos (por exemplo, _ a _ → a)

Exemplo:

Caminho: _ h h _ e _ l l _ o _
Mesclar repetições: _ h _ e _ l _ o _
Remover brancos: h e l o → "helo"

Sutileza importante: para representar letras duplicadas como "ll" em "hello", o CTC precisa de um branco (ou outro símbolo) entre elas:

Caminho para obter "hello": h e l _ l o (após o colapso)

Pequeno exemplo prático (por que os brancos importam)

Suponha que o alvo seja "aa".

O caminho a a colapsa para "a" (repetições mescladas)
Para obter "aa" você precisa de algo como a _ a ou a b a (onde b é outro símbolo)

Por isso o CTC modela explicitamente passos de tempo de “não emissão”.

A probabilidade e a perda do CTC

O CTC define a probabilidade de uma sequência-alvo (\mathbf{y}) como a soma das probabilidades de todos os caminhos que colapsam para (\mathbf{y}): [ P(\mathbf{y} \mid \mathbf{x}) = \sum_{\boldsymbol{\pi} \in B^{-1}(\mathbf{y})} P(\boldsymbol{\pi} \mid \mathbf{x}) ]

O CTC faz uma suposição simplificadora chave: dado o input (\mathbf{x}), os passos de tempo são condicionalmente independentes (conditionally independent): [ P(\boldsymbol{\pi} \mid \mathbf{x}) = \prod_{t=1}^{T} P(\pi_t \mid \mathbf{x}) ] Então: [ P(\boldsymbol{\pi} \mid \mathbf{x}) = \prod_{t=1}^{T} \mathbf{p}_t(\pi_t) ]

A perda do CTC (CTC loss) é o log-verossimilhança negativa: [ \mathcal{L}_{\text{CTC}} = -\log P(\mathbf{y} \mid \mathbf{x}) ]

Por que programação dinâmica é necessária

O conjunto (B^{-1}(\mathbf{y})) pode ser enorme (exponencial em (T)). O CTC usa um programa dinâmico para frente–para trás (forward–backward dynamic program) (similar em espírito aos modelos ocultos de Markov (hidden Markov models, HMMs)) para calcular (P(\mathbf{y}\mid\mathbf{x})) de forma eficiente.

Cálculo para frente–para trás (programação dinâmica)

A programação dinâmica do CTC é mais fácil de expressar criando uma sequência-alvo “expandida”, com brancos inseridos:

Dada (\mathbf{y} = (y_1,\dots,y_U)), defina: [ \mathbf{\tilde{y}} = (\varnothing, y_1, \varnothing, y_2, \dots, \varnothing, y_U, \varnothing) ] Ela tem comprimento (S = 2U + 1).

Então calculamos as probabilidades de estar na posição (s) em (\mathbf{\tilde{y}}) no tempo (t), respeitando as regras de transição do CTC.

Transições válidas

Da posição (s) no tempo (t-1), você pode ir para o tempo (t) por:

permanecer em (s) (repetir o mesmo símbolo),
avançar para (s+1),
às vezes avançar para (s+2) (pulando um branco), se o rótulo de destino não for igual ao rótulo atual (para evitar ambiguidade de mesclagem).

Esta é a estrutura padrão de transições do CTC.

Variáveis para frente (\(\alpha\))

Seja (\alpha(t,s)) a probabilidade total de todos os caminhos até o tempo (t) que terminam na posição (s) na sequência expandida.

Uma recorrência comum (no espaço de probabilidades) é: [ \alpha(t,s) = \mathbf{p}_t(\tilde{y}_s)\Big(\alpha(t-1,s) + \alpha(t-1,s-1) + \mathbb{1}[\text{skip allowed}]\alpha(t-1,s-2)\Big) ]

Onde “skip allowed” é verdadeiro quando:

(s \ge 3),
(\tilde{y}_s \neq \varnothing),
(\tilde{y}s \neq \tilde{y}{s-2})

A inicialização lida com o fato de que em (t=1) você só pode estar em (s=1) (branco) ou (s=2) (primeiro rótulo), dependendo das convenções.

Por fim, a probabilidade total tipicamente é: [ P(\mathbf{y}\mid\mathbf{x}) = \alpha(T, S) + \alpha(T, S-1) ] (o último branco ou o último rótulo).

Variáveis para trás (\(\beta\))

De forma análoga, (\beta(t,s)) é a probabilidade de completar a sequência do estado ((t,s)) até o fim. Na prática, muitas implementações calculam apenas o avanço em espaço logarítmico (log-space) para a perda e usam diferenciação automática, mas a derivação clássica do CTC usa ambos.

Estabilidade numérica: use espaço logarítmico

Como você multiplica muitas probabilidades, implementações computam em espaço logarítmico usando logsumexp:

Substituir somas por logsumexp
Substituir produtos por adições

Isso é crucial para enunciados longos (long utterances).

Intuição: o que a programação dinâmica está somando

O CTC está efetivamente treinando o modelo para que exista algum alinhamento monotônico em que:

quadros com evidência para o token (y_u) atribuam alta probabilidade a (y_u),
outros quadros possam atribuir probabilidade a brancos (ou a outros tokens) sem serem penalizados de forma severa.

Isso frequentemente produz posteriores “pontiagudos” (spiky posteriors): o modelo emite alta probabilidade para um token apenas em poucos quadros, cercados por quadros com muita massa no branco. Esse comportamento é normal em sistemas CTC.

Decodificação com CTC

O treinamento fornece distribuições por quadro (\mathbf{p}_t(\cdot)). A decodificação transforma isso em uma sequência de saída.

Decodificação gulosa (melhor caminho)

A abordagem mais simples:

Em cada passo de tempo, escolha o símbolo mais provável: [ \hat{\pi}t = \arg\max{k\in\mathcal{V}'} \mathbf{p}_t(k) ]
Colapsar: (\hat{\mathbf{y}} = B(\hat{\boldsymbol{\pi}}))

Isso é rápido e frequentemente surpreendentemente forte, mas não garante encontrar a sequência de rótulos globalmente mais provável porque: [ \arg\max_{\mathbf{y}} \sum_{\pi \in B^{-1}(\mathbf{y})} P(\pi|\mathbf{x}) \neq B\left(\arg\max_{\pi} P(\pi|\mathbf{x})\right) ]

Decodificação por busca em feixe

A busca em feixe (beam search) explora múltiplas hipóteses. Para CTC, uma variante padrão é a busca em feixe por prefixos (prefix beam search), que acompanha probabilidades de prefixos enquanto trata brancos corretamente.

Ideia-chave: para cada prefixo (\ell), rastrear duas pontuações:

(p_b(\ell)): probabilidade de caminhos que terminam em branco
(p_{nb}(\ell)): probabilidade de caminhos que terminam em não branco

Isso evita contagem dupla ao repetir caracteres.

Um esboço (em espaço logarítmico em sistemas reais) é:

beam = { "" : (p_b=1.0, p_nb=0.0) }

for t in 1..T:
  new_beam = empty
  for prefix, (p_b, p_nb) in beam:
    for c in V' (including blank):
      p = p_t(c)

      if c == blank:
        new_beam[prefix].p_b += (p_b + p_nb) * p
      else:
        new_prefix = prefix + c
        if prefix ends with c:
          # extending with same char has special handling
          new_beam[new_prefix].p_nb += p_b * p
          new_beam[prefix].p_nb += p_nb * p  # repeat without extending
        else:
          new_beam[new_prefix].p_nb += (p_b + p_nb) * p

  beam = topK(new_beam)
return best prefix in beam

Na prática, você também:

faz poda agressiva (largura do feixe 10–1000 dependendo da configuração),
mantém pontuações em espaço logarítmico,
aplica normalização por comprimento ou outras heurísticas.

Adicionando um modelo de linguagem (LM)

A independência quadro a quadro do CTC significa que ele não modela dependências ricas entre tokens de saída (além do que o codificador implicitamente codifica a partir da acústica). A decodificação frequentemente melhora drasticamente ao incorporar um modelo de linguagem (language model, LM) externo, tipicamente via fusão rasa (shallow fusion):

[ \text{score}(\mathbf{y}) = \log P_{\text{CTC}}(\mathbf{y}\mid\mathbf{x})

\lambda \log P_{\text{LM}}(\mathbf{y})
\gamma \cdot \text{bonus}(\mathbf{y}) ]

(\lambda): peso do LM
(\gamma): bônus opcional de inserção de palavras / bônus de comprimento (ajuda a controlar deleções)

LMs podem ser:

LMs de n-gramas (frequentemente compilados em decodificadores com transdutores de estados finitos ponderados (weighted finite-state transducers, WFST) em pipelines clássicos),
LMs neurais (por exemplo, Transformer LM) usados durante a busca em feixe.

Veja também: Beam Search, Language Models.

Escolhas práticas de decodificação em ASR

Configurações comuns no mundo real:

CTC guloso: mais simples, baixa latência, baseline.
CTC + busca em feixe por prefixos: forte sem componentes extras.
CTC + feixe + LM (fusão rasa): frequentemente a melhor taxa de erro de palavras (word error rate, WER).
CTC + reranqueamento com atenção/LM: gerar N-best com CTC, reranquear com outro modelo.

O CTC é frequentemente usado como:

um critério independente para codificadores não streaming ou streaming, ou
uma perda auxiliar (auxiliary loss) junto de um decodificador por atenção (“multitarefa CTC/atenção”), o que estabiliza o treinamento e incentiva alinhamentos monotônicos.

Considerações práticas e dicas de implementação

Escolha das unidades de saída

O CTC funciona com várias tokenizações (tokenizations):

caracteres (simples, robusto; sequências mais longas),
subpalavras (codificação por pares de bytes (byte-pair encoding, BPE)/fragmentos de palavra; comum em ASR moderno),
fonemas (às vezes usados, frequentemente com um léxico e WFST).

Subpalavras frequentemente oferecem um bom compromisso entre comprimento de sequência e flexibilidade de modelagem.

Subamostragem de entrada

Codificadores de fala comumente reduzem a resolução temporal (por exemplo, subamostragem 4× ou 8×). O CTC funciona bem com subamostragem, mas tenha em mente:

Se você subamostrar de forma agressiva demais, o modelo pode não ter passos de tempo (T) suficientes para alinhar com (U) tokens.
Uma condição necessária tipicamente é (T \ge U) (mais precisamente, (T) precisa ser grande o suficiente para acomodar brancos e repetições).

“Picos de CTC” e calibração

Posteriores do CTC frequentemente são bem concentrados. Isso pode causar:

picos de tokens com excesso de confiança,
muita massa de branco em outros lugares.

Isso é normal, mas se você depende de calibração de posterior (posterior calibration) (por exemplo, estimativa de confiança (confidence estimation)), pode precisar de técnicas adicionais de calibração.

Alinhamento forçado com CTC

Após treinado, o CTC pode produzir alinhamentos aproximados ao encontrar o caminho mais provável restrito a uma transcrição (um “alinhamento forçado (forced alignment)”), usando uma programação dinâmica no estilo Viterbi sobre a treliça (trellis) do CTC. Isso é útil para:

atribuir timestamps a palavras/subpalavras,
segmentar áudio,
limpeza de dados.

Usando implementações de bibliotecas

A maioria dos usuários depende de implementações otimizadas de CTC:

PyTorch: torch.nn.CTCLoss
TensorFlow: tf.nn.ctc_loss
NVIDIA/outros: kernels otimizados (muitos frameworks fazem wrapper disso)

Armadilhas comuns:

Garanta as expectativas corretas sobre logits vs log-probabilities (algumas APIs recebem saídas de log-softmax).
Preste atenção ao mascaramento de comprimentos de entrada e comprimentos de alvo para batching.
Use log-softmax + perda estável para evitar NaNs.

Aplicações além de fala

O CTC é aplicável sempre que as saídas sejam uma rotulagem monotônica de uma sequência de entrada mais longa:

Reconhecimento de escrita (traços da caneta → texto)
OCR (colunas/patches de imagem → texto)
Detecção de fonemas/palavras-chave (keyword spotting) (quadros de áudio → sequência de palavra-chave)
Legendagem de áudio (audio captioning) em formas restritas (quando a monotonicidade vale)

O requisito-chave é que o alinhamento correto exista e seja monotônico.

Limitações e extensões comuns

Independência condicional (uma grande limitação)

O CTC assume que as saídas por passo de tempo são independentes dado (\mathbf{x}). Isso significa:

O modelo não representa explicitamente (P(y_u \mid y_{<u}, \mathbf{x})).
Dependências token a token (ortografia, gramática) precisam vir de:
- o codificador implicitamente, e/ou
- um LM externo durante a decodificação.

Este é um dos motivos pelos quais CTC + LM é tão comum.

Apenas monotonicidade

O CTC não consegue lidar com reordenação entre entrada e saída. Para tradução ou tarefas com reordenação, modelos baseados em atenção são preferidos.

Restrições de repetição de rótulos

A regra de “mesclar repetições” do CTC complica representar tokens idênticos consecutivos (precisa de brancos). Isso geralmente é aceitável, mas afeta o comportamento de decodificação e alinhamento.

Extensões e variantes

Melhorias comuns incluem:

Pontuação de prefixo CTC (CTC prefix scoring): usar probabilidades do CTC para pontuar prefixos dentro de outros decodificadores (por exemplo, busca em feixe baseada em atenção).
Perda auxiliar de CTC em modelos codificador–decodificador: ajuda o treinamento a convergir e melhora a monotonicidade do alinhamento.
Decodificação com WFST: combinar emissões do CTC com grafo de léxico + LM para decodificação em nível de palavra (clássico, mas ainda usado).

Relação com RNN-T (Transdutor RNN)

O CTC é intimamente relacionado ao Transdutor RNN (RNN Transducer, RNN-T), sobre o qual você pode ler em RNN Transducer (RNN-T).

O que eles compartilham

Tanto CTC quanto RNN-T:

lidam com alinhamentos desconhecidos somando sobre alinhamentos com programação dinâmica,
usam um símbolo em branco para representar passos de “sem saída”,
dão suporte a casos de uso streaming quando o codificador é causal (com decodificação apropriada).

A diferença principal: modelar dependências de saída

CTC:

Produz distribuições por quadro (P(\pi_t \mid \mathbf{x})).
Não condiciona explicitamente em tokens emitidos anteriormente.
Frequentemente depende de um LM externo no momento da decodificação.

RNN-T:

Modela (P(\text{próximo token} \mid \mathbf{x}, \text{tokens anteriores})) explicitamente usando:
- um codificador sobre a acústica,
- uma rede de previsão (prediction network) sobre tokens de saída anteriores (como um LM interno),
- uma rede conjunta (joint network) combinando as duas.
Usa uma programação dinâmica 2D sobre tempo (t) e passo de saída (u), o que é um pouco mais complexo do que a treliça 1D do CTC.

Implicações práticas

O RNN-T frequentemente tem melhor desempenho em ASR streaming porque internaliza o histórico de tokens.
O CTC pode ser mais simples e rápido, especialmente com decodificação gulosa.
Muitos sistemas de produção escolhem entre:
- CTC + LM externo (simples, forte),
- RNN-T (integrado, amigável a streaming),
- ou híbridos (por exemplo, RNN-T com fusão de LM externo).

Resumo

A Classificação Temporal Conexionista (CTC) é uma abordagem fundamental para treinar modelos de sequência quando alinhamentos são desconhecidos, mas monotônicos. Ela funciona ao:

adicionar um símbolo em branco,
definir uma função de colapso (collapse function) que mapeia caminhos em nível de quadro para sequências de rótulos,
calcular (P(\mathbf{y}\mid\mathbf{x})) somando sobre todos os caminhos válidos usando programação dinâmica para frente–para trás,
decodificar via gulosa ou busca em feixe, frequentemente melhorada com um modelo de linguagem externo.

O CTC continua amplamente utilizado em sistemas modernos de ASR — tanto como critério independente quanto como perda auxiliar — e forma uma ponte conceitual importante para modelos transdutores como o RNN Transducer (RNN-T).