Skip to content
Voltar aos resultados

Aprendizagem Ativa K-Vizinhos Mais Próximos

Proposto por
Settles, B. (active learning framework); Fix & Hodges (KNN base)
Ano
1951–2010
Tipo
Active learning with KNN base learner
Família
Machine learning

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

A aprendizagem ativa com K-vizinhos mais próximos combina a previsão baseada em instâncias do KNN com uma estratégia de consulta iterativa que seleciona os exemplos não rotulados mais informativos para anotação.

O modelo solicita rótulos apenas para instâncias onde as margens de votação da vizinhança são mais estreitas, alcançando precisão competitiva com muito menos exemplos rotulados do que o KNN totalmente supervisionado em dados tabulares.

A intuição por trás do método

O KNN classifica um ponto observando seus k vizinhos rotulados mais próximos e realizando uma votação majoritária. Quando esses vizinhos estão quase igualmente divididos entre as classes, o modelo está genuinamente incerto — e essa incerteza aponta qual exemplo não rotulado valeria mais a pena rotular. A aprendizagem ativa explora esse sinal: a cada iteração, o algoritmo encontra o ponto não rotulado cuja vizinhança está mais igualmente dividida, pede a um oráculo para rotulá-lo, adiciona-o ao pool rotulado e repete. O resultado é que o esforço de rotulagem se concentra perto das fronteiras de decisão, onde novos rótulos ensinam mais.

História

O classificador K-vizinhos mais próximos tem origem em Fix e Hodges (1951) e foi formalizado por Cover e Hart (1967). A aprendizagem ativa como um arcabouço principiado foi sistematicamente pesquisada por Burr Settles (2010), que documentou a amostragem de incerteza baseada em pool, consulta por comitê e estratégias ponderadas por densidade. O KNN tem sido um aprendiz base em benchmarks de aprendizagem ativa baseados em pool desde pelo menos o trabalho fundamental de Cohn, Atlas e Ladner (1994), valorizado por seu sinal de incerteza transparente e custo zero de retreinamento por iteração.

Quando usar

Use aprendizagem ativa com KNN quando os dados rotulados são escassos ou caros de obter, as instâncias não rotuladas são abundantes, o espaço de características tem dimensionalidade moderada e a fronteira de decisão é esperada ser localmente suave. É especialmente prático em projetos de classificação em estágio inicial onde a rotulagem deve ser racionada. Evite-o quando o conjunto de dados é de dimensionalidade muito alta (as métricas de distância do KNN degradam em altas dimensões, a maldição da dimensionalidade), quando o pool rotulado já é grande (o KNN passivo é suficiente), quando a previsão de baixa latência é necessária em escala (a previsão do KNN é O(n) no conjunto rotulado), ou quando o orçamento de rótulos é tão pequeno que as estimativas de vizinhança não são confiáveis.

Limitações e considerações

  • O custo de previsão escala linearmente com o tamanho do conjunto rotulado, tornando a inferência lenta à medida que o pool cresce através das iterações.
  • A incerteza baseada em distância degrada drasticamente em espaços de alta dimensionalidade devido à maldição da dimensionalidade.
  • O teto de precisão do KNN é inferior ao dos métodos de ensemble; a estratégia ativa não pode compensar a capacidade limitada do aprendiz base.
  • Sensível à escolha de k e da métrica de distância; padrões ruins levam a estimativas de incerteza não confiáveis.
  • Todos os pontos rotulados são armazenados na memória; grandes orçamentos resultam em alto consumo de memória.

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Não paramétrico e livre de suposições: não são necessárias suposições distribucionais sobre os dados.
  • A estimativa de incerteza é natural e interpretável — reflete diretamente a divisão de votos entre os vizinhos mais próximos.
  • A aprendizagem preguiçosa significa que não há custo de retreinamento por iteração; o conjunto rotulado expandido é o modelo atualizado.
  • Eficaz em concentrar rótulos perto das fronteiras de decisão, produzindo boa resolução de fronteira com poucas anotações.
  • Funciona bem em dados tabulares de dimensionalidade moderada com características contínuas e binárias.

Aplicações

  • Anotação de prontuários médicos ou imagens onde o tempo de rotulagem de especialistas é limitado e as fronteiras de decisão são localmente suaves.
  • Classificação de texto ou documentos com pequenos corpora rotulados e abundantes documentos não rotulados usando distâncias baseadas em embeddings.
  • Tarefas de detecção de falhas em sensores e industriais onde apenas uma fração dos eventos pode ser verificada manualmente.
  • Pesquisas ecológicas onde a confirmação em campo dos rótulos de espécies é cara e localmente agrupada.
  • Classificadores protótipos em estágio inicial antes de mudar para um modelo de maior capacidade, uma vez que rótulos suficientes são coletados.

Como funciona

Como funciona

1

Um pequeno conjunto inicial de instâncias rotuladas é montado para iniciar o processo, juntamente com um pool maior de instâncias não rotuladas. A seleção aleatória estratificada é recomendada para garantir que pelo menos um exemplo por classe esteja presente, dando ao KNN uma vizinhança inicial significativa antes que o ciclo ativo comece.

2

Um classificador KNN é ajustado no conjunto rotulado atual usando um k e uma métrica de distância escolhidos (comumente Euclidiana ou cosseno). Como o KNN é preguiçoso e armazena todos os pontos de treinamento, o ajuste é instantâneo, mas o custo de previsão escala linearmente com o tamanho do conjunto rotulado — uma consideração relevante à medida que o pool cresce através das iterações.

3

Cada instância não rotulada é pontuada por um critério de informatividade. A amostragem de margem calcula a diferença entre as proporções de votos das duas classes principais entre os k vizinhos; a amostragem de entropia calcula H(y-hat | x) sobre todas as proporções de classe. A instância com a menor margem ou maior entropia é consultada: x* = argmax H(y-hat | x).

Fórmula
x^* = \arg\max_{x \in U} H(\hat{y} \mid x)
4

A instância consultada é enviada a um oráculo — um anotador humano ou mecanismo de rotulagem automatizado — para seu rótulo verdadeiro. O rótulo é adicionado ao conjunto de treinamento e a instância é removida do pool não rotulado. A confiabilidade do anotador deve ser monitorada, pois rótulos ruidosos degradam drasticamente o desempenho do KNN perto das fronteiras.

5

Como o KNN é um aprendiz preguiçoso, nenhum retreinamento explícito é necessário; o conjunto rotulado expandido constitui imediatamente o novo modelo. O ciclo de consulta-pontuação-rotulagem se repete até que o orçamento de rotulagem seja esgotado, um limite de precisão de validação seja atingido ou um número máximo de iterações seja alcançado. O desempenho final é relatado em um conjunto de teste independente e retido.

Erros comuns

  • Não normalizar as características antes de calcular as distâncias, fazendo com que características de alta magnitude dominem a vizinhança.
  • Usar o conjunto de teste para guiar ou avaliar a seleção de consultas, o que constitui vazamento de dados.
  • Definir k muito pequeno (k=1) perto da fronteira de decisão, produzindo pontuações de incerteza altamente variáveis que não refletem a verdadeira ambiguidade.
  • Ignorar o desequilíbrio de classes no conjunto semente, o que polariza as consultas iniciais em direção às fronteiras da classe majoritária.
  • Tratar a precisão da aprendizagem ativa como equivalente a uma linha de base totalmente supervisionada sem relatar a contagem de rótulos utilizada.

Perguntas frequentes

Por que usar KNN em vez de um modelo mais poderoso como base de aprendizagem ativa?

A incerteza de divisão de votos do KNN é barata de calcular e não requer retreinamento — adicionar um novo ponto rotulado atualiza imediatamente o modelo. Isso o torna atraente quando o custo computacional por iteração é importante. Para máxima precisão em um orçamento de rótulos fixo, aprendizes base de ensemble, como random forest ou gradient boosting, geralmente superam o KNN.

Como escolho k para aprendizagem ativa?

Um intervalo inicial comum é k = 5 a 15. Valores menores de k produzem estimativas de incerteza mais ruidosas; valores maiores de k suavizam a fronteira, mas podem perder ambiguidades finas. Faça validação cruzada de k no conjunto semente rotulado inicial e ajuste à medida que o pool rotulado cresce.

A escala de características importa?

Sim, criticamente. A distância do KNN é dominada por características de alta magnitude se as características não forem normalizadas. Sempre aplique a escala min-max ou a padronização z-score antes de calcular distâncias e pontuações de incerteza.

Quantos exemplos rotulados iniciais são necessários?

No mínimo, uma ou duas instâncias rotuladas por classe são necessárias para que o KNN possa formar vizinhanças para todas as classes. Na prática, 5 a 20 instâncias rotuladas fornecem estimativas de incerteza iniciais mais estáveis; menos arriscam vizinhanças degeneradas que produzem consultas iniciais não informativas.

Quando devo parar o ciclo ativo?

Defina um orçamento de rotulagem com antecedência, ou monitore a precisão de validação e pare quando a melhoria por novo rótulo cair abaixo de um limite significativo. Nunca use o conjunto de teste como um sinal de parada, pois isso vaza informações para o processo de consulta.

Métodos relacionados

Fontes

  1. Settles, B. (2010). Active Learning Literature Survey. Computer Sciences Technical Report 1648, University of Wisconsin-Madison.

    Abrir referência da publicação
    Copiado.
  2. Zhu, X., Lafferty, J., & Ghahramani, Z. (2003). Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions. Proceedings of the ICML 2003 Workshop on the Continuum from Labeled to Unlabeled Data, 58–65.

    Abrir referência da publicação
    Copiado.