k-vizinhos mais próximos: uma análise

O algoritmo k-vizinhos mais próximos (do inglês, k-Nearest Neighbors – kNN) funciona da seguinte forma: dada uma instância de teste xq, o algoritmo encontra os k vizinhos mais próximos de xq no conjunto de treinamento. Em seguida, a classe de xq é dada pela classe que ocorrer com maior frequência entre os k vizinhos.

Na figura acima, são mostrados os cinco vizinhos mais próximos da instância de teste xq. Dessas cinco instâncias, 4 são da classe “+” (vermelha) e 1 da classe “0” (azul). Ao aplicar o kNN, com k=5, a instância xq é classificada como sendo da classe vermelha, pois essa classe possui mais representantes na vizinhança de xq.

Esse algoritmo possui dois parâmetros: o número de vizinhos (k) e a medida de dissimilaridade (ou de similaridade) usada para encontrar os vizinhos mais próximos. A distância Euclidiana é a medida mais amplamente usada para determinar os vizinhos, embora existam diversas opções. Em relação ao parâmetro k (número de vizinhos), várias alternativas para determinar o valor mais adequado por tarefa podem ser empregadas. Uma delas é avaliar o algoritmo kNN no conjunto de validação, adotando diferentes valores para k. O valor de k que alcançar a melhor precisão será escolhido para classificar todas as instâncias de teste.

Uma primeira diferença em relação a outras máquinas de aprendizagem, tais como árvore de decisão e multi-layer perceptron, é que, no kNN, a etapa de treinamento é caracterizada apenas pelo armazenamento das instâncias. A rigor, não há treinamento. Logo, a função que será usada para a tomada de decisão é definida em operação, analisando um subconjunto dos dados de treinamento, i.e., os k vizinhos mais próximos. Por esse motivo, pode-se dizer que o kNN é uma máquina de aprendizagem local.


Embora seja simples, vale destacar que o kNN constrói regiões de decisão não-lineares no espaço de características. Para ilustrar, a figura a seguir mostra como o espaço de características bidimensional é dividido quando emprega-se o kNN, com k=1. As linhas verdes delimitam a área de cobertura de cada uma das instâncias de treinamento (pontos pretos: x1, x2 e x3). Assim, qualquer instância de teste que se posicionar na região amarela será classificada como sendo da mesma classe da instância x1, pois essa será a instância mais próxima. Da mesma forma, instâncias localizadas na região laranja serão classificada pela classe de x2 e, na região azul, pela classe de x3.

Importante destacar que as regiões de cobertura mostradas na figura foram obtidas usando apenas um vizinho mais próximo (1NN). Ou seja, essas regiões podem ficam mais complexas ao adotar valores maiores de k. Além disso, uma caraterísticas interessante do kNN é que as regiões de coberturas podem ser facilmente modificadas ao inserir, remover ou reposicionar as instâncias.


Mas, o kNN possui algumas desvantagens:

Armazenamento: todas as instâncias de treinamento são armazenadas para posterior consulta, quando da chegada de uma instância de teste. Se o conjunto de treinamento possuir muitas instâncias, a quantidade de memória requerida para armazená-lo pode ser um problema. Uma alternativa, para aliviar essa questão, é usar algoritmos de redução de instâncias que têm o intuito de reduzir o número de instâncias no conjunto de treinamento.

Esforço computacional: a função que classificará uma instância de teste, só é definida em operação, usando os vizinhos mais próximos. Logo, o kNN requer um esforço de processamento, em tempo de execução, para vasculhar todo o conjunto de treinamento em busca dos vizinhos para cada instância de teste. Algoritmos de redução de instâncias também podem auxiliar para mitigar essa desvantagem do kNN.

Alta dimensionalidade: ao calcular a dissimilaridade (por exemplo: usando a distância Euclidiana) entre vetores que são representados por muitas variáveis, esse cálculo pode ser impreciso devido à alta dimensionalidade dos vetores. Uma maneira de atenuar essa questão é remover variáveis redundantes ou pouco relevantes, para fins de classificação, usando algoritmos de seleção ou de extração de características.


A figura a seguir mostra dois exemplos que ilustram uma instância de teste e seus cinco vizinhos mais próximos. Nesses dois exemplos, percebe-se que a instância de teste xq está bastante próxima das instâncias da classe “0” (azul). Mas, o kNN (k=5) classificará as duas instâncias de teste como pertencentes à classe “+” (vermelha), pois essa classe possui mais instâncias do que a classe azul na vizinhança de xq.

Nesses exemplos, a proximidade de xq em relação aos seus vizinhos não é levada em consideração. Apenas a quantidade de instâncias na vizinhança é usada para decidir a classe de xq. Mas, é possível encontrar variações do kNN que visam abrandar essa e outras propriedades previamente discutidas.

Processamento de linguagem natural: representando palavras

Os avanços científicos e tecnológicos em processamento de linguagem natural têm o objetivo de intermediar a comunicação entre computadores e humanos usando seu principal meio de transmissão de informação, de conhecimento e de sentimento: a linguagem natural. A comunicação entre humanos é uma relação social bastante complexa que envolve o uso de diversos recursos, tais como: gestos e símbolos. Mas, dentre todos os meios, a palavra merece uma atenção especial, por sua abrangência e alcance.

A confluência entre palavras e sistemas de aprendizagem de máquina mostra um caminho para a produção de aplicações que agregam valor a diversas tarefas: tradução, detecção de fake news, deteção de hate speech, categorização de documentos, análise de sentimentos e de emoções, entre outras. Um pilar fundamental para o sucesso da automatização de tais aplicações reside na representação dessas palavras de uma forma que facilite a tarefa das máquinas de aprendizagem. Essa tal representação deve preservar o significado das palavras.

WordNet é um dicionário de sinônimos de palavras em inglês. Além dos sinônimos, o WordNet armazena, para cada palavra, um conjunto de relações do tipo “é um”. Por exemplo: para a palavra morcego, as relações “é um” animal, “é um” mamífero, entre outras, podem ser recuperadas. Assim, o WordNet é uma alternativa para representar palavras, porém, possui algumas limitações. Uma delas refere-se a incompletude, ou seja, faltam sinônimos de várias palavras, especialmente, de palavras mais novas. Ao se analisar textos, algumas palavras aparecem regularmente próximas entre si, enquanto outras, raramente, aparecem juntas. Para exemplificar: as palavras “tubarão” e “baleia” ocorrem juntas com mais frequência do que as palavras “tubarão” e “deserto”. Logo, uma informação importante diz respeito à similaridade entre palavras, e isso, o WordNet também não oferece.  

One-hot encoding

Até 2012, boa parte das aplicações representavam palavras usando uma codificação ortogonal. Para ilustrar, um corpus composto por seis palavras: tubarão, baleia, deserto, golfinho, mamífero e peixe, seria representado pelos vetores binários:

one-hot-enconding

Essa forma de representar, também conhecida como one-hot encoding, traz consigo algumas questões. Em geral, um corpus (conjunto de textos) possui mais do que seis palavras. Dado que o tamanho do vetor, que representa cada palavra, é igual ao número de palavras no corpus, esse vetor terá, facilmente, o tamanho de algumas centenas de milhares de posições. Logo, são vetores grandes e esparsos (cada vetor possui apenas um valor “1” e vários “0”s). 

Outro fator negativo ao empregar o one-hot encoding está relacionado à similaridade entre as palavras. Nessa representação, a distância entre quaisquer duas palavras é a mesma, pois cada palavra é um vetor perpendicular a todos os outros, logo, o produto interno entre dois vetores é igual a zero. Desta forma, a distância entre as palavras “baleia” e “golfinho” e as palavras “baleia” e “deserto” é a mesma. Nenhuma relação entre as palavras é estabelecida, e isso fere o objetivo de adicionar semântica ao processo, pois sabemos que as palavras “baleia” e “golfinho” aparecem mais frequentemente juntas do que as palavras “baleia” e “deserto”.

Word vectors

Tendo em vista que a relação entre as palavras é importante, pois é uma forma de adicionar semântica ao processo, alternativas foram desenvolvidas para incluir essa informação de contexto no vetor que representada cada palavra. Desde 2013, uma forma de mapear palavras em vetores com valores reais, estabeleceu-se como o estado da arte da área: word vectors (word embedding).

Ao contrário do one-hot enconding, no qual um vetor perpendicular às demais palavras é atribuído a cada palavra, os word vectors são aprendidos usando uma rede neural artificial. Esse processo de aprendizagem dos vetores leva em consideração o fato de que palavras que ocorrem em contextos similares possuem semânticas, também, similares. Dito de outra forma, se a palavra “peixe” aparece próxima da palavra “tubarão” mais frequentemente do que a palavra “mamífero”, é esperado que as palavras “peixe” e “tubarão” sejam mais “parecidas”, semanticamente, do que as palavras “peixe” e “mamífero”. Assim, deseja-se construir vetores que representem as palavras de forma que a distância entre “peixe” e “tubarão” seja menor do que a distância entre “peixe” e “mamífero”.

A figura a seguir mostra exemplos de word vectors nos quais é possível observar que as distâncias entre as palavras não é a mesma e que algumas relações semânticas, semelhantes às descritas no parágrafo anterior, são preservadas. Nota: cada uma das palavras dessa figura era formada originalmente por um vetor de cem valores e, para fins de visualização, a dimensionalidade foi reduzido para duas usando a análise dos componentes principais. Logo, muita informação foi perdida nesse processo de redução para uma representação 2D.

pca-word2vec

Mas, como embutir tal semântica nos vetores que representam as palavras, sabendo que tais vetores são compostos por números reais? Para ilustrar a intuição dessa construção dos vetores, veja o exemplo a seguir que mostra a frase “Focas, orcas, golfinhos e baleias são mamíferos que vivem nos mares”. Nesse exemplo, o elemento “central” é dado pela palavra “baleia” e os elementos de “contexto” estão destacados em verde.  Esse processo é chamado de janelamento e, para essa ilustração, foi usado uma janela de tamanho cinco. De maneira iterativa, essa janela percorre a frase, colocando outras palavras como o elemento “central”.

word2vec-frase2

Os valores que compõem o vetor da palavra “central” são atualizados de maneira que consigam predizer quais palavras formam o “contexto”. Na figura, wt representa a palavra central “baleia” e P(wt+2|wt) é a probabilidade de predizer a palavra  “mamífero” (wt+2) dada a palavra “baleia” (wt). Desta forma, ao apresentar várias e várias janelas à máquina de aprendizagem, o modelo consegue aprender o contexto de palavras estimando a probabilidade de uma palavra no “contexto” ser predita pela palavra “central”. E, ao fim, esse processo “magicamente” embute o significado das palavras nos valores dos vetores.  Para mais detalhes sobre o funcionamento do modelo, veja o artigo que propõe o Word2vec. Esse é o modelo seminal que usa uma rede neural para representar as palavras seguindo a intuição descrita acima.

Como representar uma tarefa de aprendizagem de máquina: handcrafted features vs feature learning

Quando tomamos uma decisão, usamos uma grande quantidade de variáveis e de hierarquias de variáveis. Muitas vezes, nem nos apercebermos da importância dessas variáveis, pois, a complexidade de algumas decisões está além do nosso entendimento. Para ilustrar: você poderia me explicar, em detalhes, como reconhece seu amigo? Quais características, seus sistemas (visual, auditivo, …) analisam, a fim de identificá-lo com precisão?

Ok, vamos para um exemplo mais palpável. Suponha que desejamos comprar um carro. De pronto, nos vem a mente, uma série de variáveis que devemos avaliar: preço, cor, consumo de combustível, procedência, entre outras. Essas características nos ajudam a decidir, se iremos ou não comprar o carro.

De maneira similar, o conjunto de características, que apresentamos à máquina de aprendizagem, é de imperativa importância para que ela consiga tomar a melhor decisão. A escolha dessas características é uma tarefa não trivial, principalmente, quando não temos um especialista para nos ajudar no problema que desejamos resolver (e.g., comprar um carro usado sem a ajuda de um mecânico).

Em aprendizagem de máquina, essas características (features, em inglês), também chamadas de variáveis ou atributos, são fundamentais para o sucesso do processo de aprendizagem. Mas, geralmente, não sabemos quais são as características mais relevantes, consequentemente, decidimos por usar um grande número de características.  Assim, corre-se o risco de que algumas delas sejam irrelevantes ou mesmo prejudiciais para o treinamento da máquina de aprendizagem. Com o objetivo de reduzir essa quantidade de características e por conseguinte, aliviar a maldição da dimensionalidade, a alternativa mais comum é usar algoritmos de seleção de características. Esses algoritmos têm o papel de buscar o melhor subconjunto de características, a fim de realizar com sucesso, a tarefa que temos em mãos.

Mas, para selecionar características, precisamos, em primeiro lugar, ter as características. Essas características podem ser obtidas de duas formas: manual (handcrafted features) ou podem ser aprendidas (feature learning).

hand-crafted-vs-feature-learningNa primeira forma, handcrafted features, um conjunto de características é recomendado por um especialista, com a ajuda de um cientista de dados, e esse processo é chamado de feature engineering. Tal processo é mostrado no caminho superior da figura acima, no qual, o trabalho do especialista é definir as características (e/ou algoritmos extratores de características), que serão usadas para representar uma árvore. Após essa definição, um modelo é treinado, com o intuito de rotular como “árvore”, toda imagem de árvore que for dada como entrada ao sistema. Vale salientar, que se poucos especialistas estiverem disponíveis no mercado, o custo de seus serviços será alto. Todavia, mesmo se os especialistas estiverem disponíveis, a tarefa é inerentemente difícil. Não é incomum que especialistas discordem (links: 1, 2, 3, 4).

Dado que <manual> feature engineering é uma tarefa cara e difícil, como evitá-la? Uma alternativa é construir máquinas capazes de realizar essa tarefa automaticamente. Ou seja, ao invés da busca ser feita por humanos, podemos delegar a tarefa de encontrar as melhores características para um algoritmo. Esse procedimento é chamado de feature learning (mostrado como sendo o caminho inferior da imagem acima). A boa notícia é que algumas máquinas já fazem esse trabalho. Arquiteturas de aprendizado profundo (deep learning – DL) estão sendo usadas para esse fim, especialmente, para tarefas que envolvam imagens, voz e texto.

Não é à toa, que DL tem se destacado nas manchetes dos noticiários ultimamente. Ela tem obtido resultados bem superiores às handcrafted features em várias aplicações, e esse sucesso deve-se ao fato de que as características são aprendidas a partir dos dados do problema. Em outras palavras, essas características são automaticamente extraídas dos dados originais, por algoritmos que buscam minimizar o erro global do sistema. Logo, o conjunto de características gerado é dependente do problema, ou seja, são personalizadas para cada conjunto de dados de treinamento.

Ganha-se em precisão, perde-se em interpretabilidade. Essa é uma desvantagem de DL. As características aprendidas não possuem explicação conhecida no mundo real. Nesse sentido, o processo realizado pela DL, ao aprender as características, é, de certa forma, semelhante ao processo que trilhamos, por exemplo, ao reconhecer uma pessoa. Sabemos que funciona… mas não conseguimos explicar em detalhes como realizamos essa tarefa.

Outro fator limitante está relacionado à abrangência. Sabemos como aprender automaticamente características interessantes, quando os dados de entrada são imagens, voz e texto. O desafio agora é expandir esse aprendizado automático para outras aplicações, que ainda requerem a manufatura de características.