Beam search hierárquico em taxonomia profunda

Uma taxonomia de patentes tem seções, classes, subclasses, grupos e subgrupos. Para chegar à folha certa você toma cinco ou seis decisões em sequência. Se a primeira estiver errada, nenhuma decisão posterior salva o resultado: você está no galho errado da árvore e a única coisa que resta é escolher bem dentro do erro.

O cookbook oficial de classificação hierárquica mostra exatamente esse fracasso com um documento sobre poleiros para aves. A busca gananciosa — escolher o filho mais provável e descartar o resto — terminou em “assunto não previsto nesta seção”. Mantendo três caminhos vivos, o mesmo documento chegou ao subgrupo correto de poleiros para aves domésticas.

Este padrão é leitura nossa. A página oficial de padrões nomeia quatro, e este não está lá. Nós o descrevemos como padrão porque a forma se repete em qualquer taxonomia profunda, mas o vocabulário é nosso.

A mecânica

Cada nó da hierarquia vira uma pergunta Choice cujas opções são os filhos daquele nó. A distribuição de probabilidades da resposta é, literalmente, o peso das arestas que saem dele.

• Greedy: escolhe o filho de maior probabilidade e joga fora as alternativas. Uma decisão ruim no começo não tem volta.
• Beam: mantém K caminhos plausíveis e classifica todas as frentes em paralelo. Evidência mais profunda pode consertar uma decisão ambígua no topo. Ganha a folha do caminho com a maior média geométrica.

A pontuação é o detalhe que faz o padrão funcionar:

path_score = product(edge_probabilities) ** (1 / decisions)
separation = top_path_score / second_path_score

A média geométrica normalizada pelo comprimento permite comparar caminhos de profundidades diferentes sem punir o mais fundo. A separação não entra na poda: ela serve para você saber se a decisão foi disputada. Para hierarquias com mais de dez camadas, o cookbook recomenda exp(mean(log(probs))) em vez do produto elevado, para evitar erro de precisão.

O que o padrão compra além da acurácia

O cookbook lista dois ganhos que não são sobre o acerto, e são os que mais importam para arquitetura.

Observabilidade. Como cada nó é uma pergunta, você sabe em qual nó as classificações erram mais e quantas vezes cada nó e cada aresta foram percorridos. Isso transforma “o classificador está ruim” em “o nó 12 separa mal”, que é um problema com endereço.

Testabilidade. Dá para testar unitariamente um nó e medir o impacto de uma mudança na hierarquia. Quando alguém acrescenta uma subcategoria, você consegue dizer o que aquilo fez com a classificação — em vez de descobrir em produção.

Há um terceiro ganho, implícito: a decisão fica explicável. O caminho percorrido é a justificativa, com a probabilidade de cada aresta ao longo dele.

O que ele obriga a arquitetura a ter

Uma hierarquia versionada. O cookbook usa fontes fixadas por versão: CPC 2026.05 para patentes, Shopify 2026-02 para produtos de varejo, MeSH 2026 para assuntos biomédicos e a própria árvore de arquivos do repositório de cookbooks da TypeSafe. Sem a versão, comparar resultados entre duas execuções não significa nada.

Descrições de nó escritas para separar irmãos. A opção não precisa explicar a categoria ao mundo; precisa distinguir aquele filho dos outros filhos do mesmo pai. É a mesma disciplina de critérios que separam.

Cuidado com grafo em vez de árvore. O MeSH é um grafo acíclico dirigido: um descritor pode aparecer sob vários pais. O cookbook expande os caminhos oficiais de número de árvore para tratá-lo como árvore. Se a sua taxonomia tem o mesmo formato, essa escolha precisa ser explícita.

Um K decidido com dados. K é o parâmetro do padrão. O cookbook usa 3 nos exemplos; o seu valor depende de onde as ambiguidades aparecem na sua árvore.

Quando não usar

Quando a taxonomia é rasa. Com dois níveis, o beam quase não tem o que recuperar. Uma pergunta por nível já resolve, e talvez uma pergunta só resolva.

Quando os filhos de um nó não são mutuamente exclusivos. Choice é uma escolha relativa entre opções. Se um documento pertence legitimamente a dois ramos, a resposta certa não é um caminho — é um Noul por ramo, como discutido em qual primitiva usar.

Quando o pai não contém informação suficiente para o desvio. Se a decisão do primeiro nível só é possível depois de ler o nível três, a hierarquia está organizada por outra lógica que não a da decisão, e o beam gasta perguntas sem ganhar acurácia.

Quando a folha errada custa o mesmo que a certa. Se a ação a jusante é igual para o galho inteiro, classifique até o nível que muda a ação e pare ali.

Quando a confiança do caminho não é usada. Sem um destino para o caso de separação perto de 1, o padrão devolve uma folha ambígua com cara de decisão. A faixa disputada merece o tratamento de roteamento por confiança ou fila de curadoria, como em revisão humana.

Por onde continuar

Quando a hierarquia existe mas você quer apenas subir um nível em caso de dúvida, a receita de classificar com confiança mostra esse desenho mais simples. Para entender por que as probabilidades das arestas podem ser lidas assim, veja confiança. O índice está em padrões.