Incorporações no aprendizado de máquina: simplificando dados complexos

Trabalhar com dados não numéricos pode ser difícil, mesmo para cientistas de dados experientes. Um modelo típico de aprendizado de máquina espera que seus recursos sejam números, não palavras, e-mails, páginas de sites, listas, gráficos ou distribuições de probabilidade. Para serem úteis, os dados precisam ser transformados em um espaço vetorial primeiro. Mas como?

Uma abordagem popular seria tratar um recurso não numérico como categórico . Isso pode funcionar bem se o número de categorias for pequeno (por exemplo, se os dados indicarem uma profissão ou um país). No entanto, se tentarmos aplicar esse método a e-mails, provavelmente obteremos tantas categorias quanto amostras. Não há dois e-mails exatamente iguais, portanto, essa abordagem seria inútil.

Outra abordagem seria definir uma distância entre as amostras de dados , uma função que nos diz o quão perto duas amostras estão. Ou poderíamos definir uma medida de similaridade , que nos daria a mesma informação, exceto que a distância entre duas amostras próximas é pequena enquanto a similaridade é grande. Calcular a distância (semelhança) entre todas as amostras de dados nos daria uma matriz de distância (ou similaridade). Estes são dados numéricos que poderíamos usar.

No entanto, esses dados teriam tantas dimensões quanto amostras, o que geralmente não é ótimo se quisermos usá-lo como um recurso (consulte a maldição da dimensionalidade) ou para visualizá-lo (enquanto um gráfico pode lidar com até 6D, eu ainda para ver um gráfico 100D). Poderíamos reduzir o número de dimensões para uma quantidade razoável?

A resposta é sim! É para isso que temos incorporações .

O que é uma incorporação e por que usá-la?

Uma incorporação é uma representação de baixa dimensão de dados de alta dimensão. Normalmente, uma incorporação não captura todas as informações contidas nos dados originais. Uma boa incorporação, no entanto, capturará o suficiente para resolver o problema em questão.

Existem muitos embeddings adaptados para uma estrutura de dados específica. Por exemplo, você pode ter ouvido falar de word2vec para dados de texto ou descritores de Fourier para dados de imagem de forma. Em vez disso, discutiremos como aplicar embeddings a quaisquer dados em que possamos definir uma distância ou uma medida de similaridade. Enquanto pudermos calcular uma matriz de distância, a natureza dos dados é completamente irrelevante. Funcionará da mesma forma, sejam e-mails, listas, árvores ou páginas da web.

Neste artigo, apresentaremos diferentes tipos de incorporação e discutiremos como algumas incorporações populares funcionam e como podemos usar incorporações para resolver problemas do mundo real envolvendo dados complexos. Também passaremos pelos prós e contras desse método, bem como algumas alternativas. Sim, alguns problemas podem ser resolvidos melhor por outros meios, mas, infelizmente, não existe uma bala de prata no aprendizado de máquina.

Vamos começar.

Como funcionam as incorporações

Todas as incorporações tentam reduzir a dimensionalidade dos dados enquanto preservam informações “essenciais” nos dados, mas cada incorporação faz isso à sua maneira. Aqui, veremos alguns embeddings populares que podem ser aplicados a uma matriz de distância ou similaridade.

Nós nem tentaremos cobrir todas as incorporações por aí. Há pelo menos uma dúzia de incorporações bem conhecidas que podem fazer isso e muitas outras menos conhecidas e suas variações. Cada um deles tem sua própria abordagem, vantagens e desvantagens.

Se você quiser ver quais outras incorporações estão por aí, você pode começar aqui:

• Guia do usuário do Scikit-learn
• Os Elementos da Aprendizagem Estatística (Segunda Edição), Capítulo 14

Matriz de distância

Vamos tocar brevemente em matrizes de distância. Encontrar uma distância apropriada para os dados requer uma boa compreensão do problema, algum conhecimento de matemática e, às vezes, pura sorte . Na abordagem descrita neste artigo, esse pode ser o fator mais importante que contribui para o sucesso ou fracasso geral do seu projeto.

Você também deve manter alguns detalhes técnicos em mente. Muitos algoritmos de incorporação assumem que uma matriz de distância (ou dissimilaridade ) $\textbf{D}$ tem zeros em sua diagonal e é simétrica. Se não for simétrico, podemos usar $(\textbf{D} + \textbf{D}^T) / 2$. Algoritmos usando o truque do kernel também assumirão que uma distância é uma métrica, o que significa que a desigualdade triangular é válida:

\[\forall a, b, c \;\; d(a,c) \leq d(a,b) + d(b,c)\]

Além disso, se um algoritmo requer uma matriz de similaridade, podemos aplicar qualquer função de diminuição monótona para transformar uma matriz de distância em uma matriz de similaridade: por exemplo, $\exp -x$.

Análise de Componentes Principais (PCA)

A Análise de Componentes Principais, ou PCA, é provavelmente a incorporação mais usada até hoje. A ideia é simples: encontre uma transformação linear de características que maximize a variância capturada ou (equivalentemente) minimize o erro de reconstrução quadrática .

Especificamente, seja uma matriz de amostra $\textbf{X} \in \mathbb{R}^{n \times p}$ tenha $n$ características e $p$ dimensões. Para simplificar, vamos supor que a média da amostra de dados seja zero. Podemos reduzir o número de dimensões de $p$ para $q$ multiplicando $\textbf{X}$ por uma matriz ortonormal $\textbf{V}_q \in \mathbb{R}^{p \times q}$ :

\[\hat{\textbf{X}} = \textbf{X} \textbf{V}_q\]

Então, $\hat{\textbf{X}} \in \mathbb{R}^{n \times q}$ será o novo conjunto de recursos. Para mapear os novos recursos de volta ao espaço original (esta operação é chamada de reconstrução ), basta multiplicar novamente por $\textbf{V}_q^T$.

Agora, devemos encontrar a matriz $\textbf{V}_q$ que minimiza o erro de reconstrução:

\[\min_{\textbf{V}_q} ||\textbf{X}\textbf{V}_q\textbf{V}_q^T - \textbf{X}||^2\]

As colunas da matriz $\textbf{V}_q$ são chamadas de direções dos componentes principais, e as colunas de $\hat{\textbf{X}}$ são chamadas de componentes principais. Numericamente, podemos encontrar $\textbf{V}_q$ aplicando a decomposição SVD a $\textbf{X}$, embora existam outras maneiras igualmente válidas de fazer isso.

O PCA pode ser aplicado diretamente a recursos numéricos. Ou, se nossos recursos não forem numéricos, podemos aplicá-los a uma matriz de distância ou similaridade.

Se você usa Python, o PCA é implementado no scikit-learn.

A vantagem deste método é que é rápido de calcular e bastante robusto a ruídos nos dados.

A desvantagem seria que ele só pode capturar estruturas lineares, portanto, as informações não lineares contidas nos dados originais provavelmente serão perdidas.

Kernel PCA

Kernel PCA é uma versão não linear do PCA. A ideia é usar o kernel trick , do qual você provavelmente já ouviu falar se estiver familiarizado com o Support Vector Machines SVM.

Especificamente, existem algumas maneiras diferentes de calcular o PCA. Uma delas é calcular a autodecomposição da versão duplamente centrada da matriz grama $\textbf{X} \textbf{X}^T \in \mathbb{R}^{n \times n}$. Agora, se calcularmos uma matriz kernel $\textbf{K} \in \mathbb{R}^{n \times n}$ para nossos dados, o Kernel PCA irá tratá-la como uma matriz grama para encontrar os componentes principais.

Sejam $x_i$, $i \in {1,..,n}$ as amostras de recursos. A matriz do kernel é definida por uma função do kernel $K(x_i,x_j)=\langle \phi(x_i),\phi(x_j) \rangle$.

Uma escolha popular é um kernel radial:

\[K(x_i,x_j)=\exp -\gamma \cdot d(x_i,x_j)\]

onde $d$ é uma função de distância.

O Kernel PCA exigiu que especifiquemos uma distância. Por exemplo, para recursos numéricos, poderíamos usar a distância euclidiana: $d(x_i,x_j)=\vert\vert x_i-x_j \vert \vert ^2$.

Para recursos não numéricos, talvez precisemos ser criativos. Uma coisa a lembrar é que esse algoritmo assume que nossa distância é uma métrica.

Se você usa Python, o Kernel PCA é implementado no scikit-learn.

A vantagem do método Kernel PCA é que ele pode capturar estruturas de dados não lineares.

A desvantagem é que ele é sensível ao ruído nos dados e que a escolha das funções de distância e kernel afetará muito os resultados.

Dimensionamento Multidimensional (MDS)

O dimensionamento multidimensional (MDS) tenta preservar as distâncias entre as amostras globalmente. A ideia é bastante intuitiva e funciona bem com matrizes de distância.

Especificamente, dadas amostras de recursos $x_i$, $i \in {1,..,n}$ e uma função de distância $d$, calculamos novas amostras de recursos $z_i \in \mathbb{R}^{q}$, $i \in {1,..,n}$ minimizando uma função de estresse :

\[\min_{z_1,..,z_n} \sum_{1 \leq i < j \leq n} (d(x_i, x_j) - ||z_i - z_j||)^2\]

Se você usa Python, o MDS é implementado no scikit-learn. No entanto, o scikit-learn não suporta a transformação de pontos fora da amostra, o que pode ser inconveniente se quisermos usar uma incorporação em conjunto com um modelo de regressão ou classificação. Em princípio, no entanto, é possível.

A vantagem do MDS é que sua ideia está perfeitamente de acordo com nossa estrutura e que não é muito afetada por ruídos nos dados.

A desvantagem é que sua implementação no scikit-learn é bastante lenta e não suporta transformação fora da amostra.

Caso de uso: rastreamento de remessa

Alguns assentamentos em uma pequena ilha tropical desenvolveram serviços de remessa de encomendas para atender à indústria de turismo local. Um comerciante em um desses assentamentos decidiu tomar medidas para ganhar vantagem sobre a concorrência, então ele montou um sistema de vigilância por satélite rastreando todas as remessas de pacotes na ilha. Uma vez que os dados foram coletados, o comerciante chamou um cientista de dados (somos nós!) para ajudá-lo a responder a seguinte pergunta: podemos prever o destino de um pacote que está a caminho?

O conjunto de dados contém informações sobre 200 remessas rastreadas. Para cada remessa rastreada, há uma lista de coordenadas (x,y) de todos os locais onde o pacote foi localizado, o que normalmente é algo entre 20 e 50 observações. O gráfico abaixo mostra como esses dados se parecem.

Esses dados parecem problemas – dois tipos diferentes de problemas, na verdade.

O primeiro problema é que os dados com os quais estamos lidando são de alta dimensão. Por exemplo, se cada pacote fosse localizado em 50 locais, nossos dados teriam 100 dimensões – parece muito, em comparação com as 200 amostras à sua disposição.

O segundo problema: diferentes rotas de embarque na verdade têm um número diferente de observações, então não podemos simplesmente empilhar as listas com coordenadas para representar os dados em uma forma tabular (e mesmo se tivessem, isso ainda não faria sentido).

O comerciante está batendo impacientemente na mesa com os dedos, e o cientista de dados está se esforçando para não mostrar nenhum sinal de pânico.

É aqui que as matrizes de distância e os embeddings serão úteis. Só precisamos encontrar uma maneira de comparar duas rotas de envio. A distância de Frechet parece ser uma escolha razoável. Com uma distância, podemos calcular uma matriz de distância.

Observação: esta etapa pode demorar um pouco. Precisamos calcular distâncias $O(n^2)$ com cada distância tendo iterações $O(k^2)$, onde $n$ é o número de amostras e $k$ é o número de observações em uma amostra. Escrever uma função de distância de forma eficiente é fundamental. Por exemplo, em Python, você pode usar numba para acelerar esse cálculo muitas vezes.

Visualizando Embeddings

Agora, podemos usar uma incorporação para reduzir o número de dimensões de 200 para apenas algumas. Podemos ver claramente que existem apenas algumas rotas comerciais, então podemos esperar encontrar uma boa representação dos dados mesmo em duas ou três dimensões. Usaremos embeddings que discutimos anteriormente: PCA, Kernel PCA e MDS.

Nos gráficos abaixo, você pode ver os dados da rota rotulada (dados para demonstração) e sua representação por uma incorporação em 2D e 3D (da esquerda para a direita). Os dados rotulados marcam quatro postos comerciais conectados por seis rotas comerciais. Duas das seis rotas comerciais são bidirecionais, o que totaliza oito grupos de embarque (6+2). Como você pode ver, temos uma separação bastante clara de todos os oito grupos de remessas com embeddings 3D.

Este é um bom começo.

Incorporações em um pipeline de modelo

Agora, estamos prontos para treinar uma incorporação. Embora o MDS tenha apresentado os melhores resultados, é bastante lento; além disso, a implementação do scikit-learn não suporta transformação fora da amostra. Não é um problema para pesquisa, mas pode ser para produção, então usaremos Kernel PCA. Para Kernel PCA, não devemos esquecer de aplicar previamente um kernel radial à matriz de distância.

Como você seleciona o número de dimensões de saída? A análise mostrou que mesmo o 3D funciona bem. Apenas para garantir e não deixar de fora nenhuma informação importante, vamos definir a saída de incorporação para 10D. Para obter o melhor desempenho, o número de dimensões de saída pode ser definido como um hiperparâmetro de modelo e ajustado por validação cruzada.

Assim, teremos 10 recursos numéricos que podemos usar como entrada para praticamente qualquer modelo de classificação. Que tal um modelo linear e um não linear: digamos, regressão logística e aumento de gradiente? Para comparação, vamos também usar esses dois modelos com uma matriz de distância total como entrada. Além disso, vamos testar o SVM também (o SVM foi projetado para trabalhar diretamente com uma matriz de distância, portanto, nenhuma incorporação seria necessária).

A precisão do modelo no conjunto de teste é mostrada abaixo (10 conjuntos de dados de treinamento e teste foram gerados para que pudéssemos estimar a variância do modelo):

• O aumento de gradiente emparelhado com uma incorporação (KernelPCA + GB) obtém o primeiro lugar. Ele superou o aumento de gradiente sem incorporação (GB). Aqui, o Kernel PCA provou ser útil.
• A regressão logística deu certo. O interessante é que a regressão logística sem incorporação (LR) se saiu melhor do que com uma incorporação (KernelPCA+LR). Isso não é totalmente inesperado. Modelos lineares não são muito flexíveis, mas são relativamente difíceis de superajustar. Aqui, a perda de informação causada por uma incorporação parece superar o benefício de uma dimensionalidade de entrada menor.
• Por último, mas não menos importante, o SVM também teve um bom desempenho, embora a variação desse modelo seja bastante significativa.

Precisão do modelo

O código Python para este caso de uso está disponível no GitHub.

Conclusão

Explicamos o que são embeddings e demonstramos como eles podem ser usados ​​em conjunto com matrizes de distância para resolver problemas do mundo real. Hora do veredicto:

Os embeddings são algo que um cientista de dados deve usar? Vamos dar uma olhada em ambos os lados da história.

Prós e contras do uso de embeddings

Prós:

• Essa abordagem nos permite trabalhar com estruturas de dados incomuns ou complexas, desde que você possa definir uma distância que, com um certo grau de conhecimento, imaginação e sorte, normalmente pode.
  
• A saída são dados numéricos de baixa dimensão, que você pode facilmente analisar, agrupar ou usar como recursos de modelo para praticamente qualquer modelo de aprendizado de máquina existente.

Contras:

• Usando essa abordagem, necessariamente perderemos algumas informações:

  • Durante a primeira etapa, quando substituímos os dados originais pela matriz de similaridade
  • Durante a segunda etapa, quando reduzimos a dimensionalidade usando uma incorporação
• Dependendo dos dados e da função de distância, o cálculo de uma matriz de distância pode ser demorado. Isso pode ser mitigado por uma função de distância escrita eficientemente.
• Alguns embeddings são muito sensíveis ao ruído nos dados. Isso pode ser mitigado pela limpeza de dados adicional.
• Alguns embeddings são sensíveis à escolha de seus hiperparâmetros. Isso pode ser mitigado por uma análise cuidadosa ou ajuste de hiperparâmetro.

Alternativas: Por que não usar…?

• Por que não usar apenas uma incorporação diretamente nos dados, em vez de uma matriz de distância?
  Se você conhece uma incorporação que pode codificar seus dados de forma eficiente e direta, use-a. O problema é que nem sempre existe.
  
• Por que não usar apenas a clusterização em uma matriz de distância?
  Se seu único objetivo é segmentar seu conjunto de dados, não há problema em fazê-lo. Alguns métodos de clusterização também aproveitam os embeddings (por exemplo, Spectral Clustering). Se você quiser saber mais, aqui está um tutorial sobre clusterização.
  
• Por que não usar apenas uma matriz de distância como recursos?
  O tamanho de uma matriz de distância é $(n_{amostras}, n_{amostras})$. Nem todos os modelos podem lidar com isso de forma eficiente - alguns podem se ajustar demais, alguns podem demorar para se ajustar, alguns podem não se ajustar completamente. Modelos com baixa variância seriam uma boa escolha aqui, como modelos lineares e/ou regularizados.
  
• Por que não usar SVM com uma matriz de distância?
  O SVM é um ótimo modelo, que teve um bom desempenho em nosso caso de uso. No entanto, existem algumas ressalvas. Primeiro, se quisermos adicionar outros recursos (podem ser apenas números numéricos simples), não poderemos fazê-lo diretamente. Teríamos que incorporá-los em nossa matriz de similaridade e potencialmente perder algumas informações valiosas. Em segundo lugar, por melhor que seja o SVM, outro modelo pode funcionar melhor para o seu problema específico.
  
• Por que não usar o aprendizado profundo?
  É verdade que, para qualquer problema, você pode encontrar uma rede neural adequada se pesquisar o suficiente. Tenha em mente, porém, que o processo de encontrar, treinar, validar e implantar essa rede neural não será necessariamente simples. Então, como sempre, use seu bom senso.

Em uma frase

Embeddings em conjunto com matrizes de distância são uma ferramenta incrivelmente útil se você trabalhar com dados não numéricos complexos, especialmente quando não puder transformar seus dados em um espaço vetorial diretamente e preferir ter uma entrada de baixa dimensão para seu modelo.