A fim de dar uma introdução adequada ao kernel gaussiano, o post desta semana vai começar um pouco mais abstrato do que o normal. Este nível de abstração não é estritamente necessário para entender como os grãos gaussianos funcionam, mas a perspectiva abstrata pode ser extremamente útil como fonte de intuição quando se tenta entender as distribuições de probabilidade em geral. Então é o seguinte: vou tentar construir a abstração lentamente, mas se você se perder ou não aguentar mais, você pode pular para o cabeçalho que diz “A parte prática” em negrito – É aí que eu vou mudar para uma descrição mais concreta do algoritmo do kernel gaussiano. Além disso, se você ainda estiver tendo problemas, não se preocupe muito – A maioria dos posts posteriores neste blog não vai exigir que você entenda os kernels gaussianos, então você pode simplesmente esperar pelo post da próxima semana (ou pular para ele se você estiver lendo isto mais tarde).

Recorde que um kernel é uma forma de colocar um espaço de dados em um espaço vetorial dimensional mais alto de modo que as interseções do espaço de dados com hiperplanos no espaço dimensional mais alto determinem limites de decisão mais complicados e curvos no espaço de dados. O exemplo principal que olhamos foi o kernel que envia um espaço de dados bidimensional para um espaço de dados de cinco dimensões enviando cada ponto com coordenadas para o ponto de dados de cinco dimensões com coordenadas . Se quiséssemos nos dar ainda mais flexibilidade, poderíamos escolher um kernel dimensional ainda maior, por exemplo enviando o ponto para o ponto num espaço de nove dimensões.

Esta semana, vamos além dos espaços vectoriais dimensionais superiores para espaços vectoriais infinitamente dimensionais. Você pode ver como o kernel de nove dimensões acima é uma extensão do kernel de cinco dimensões – nós essencialmente só nos debruçamos sobre mais quatro dimensões no final. Se continuarmos a abordar mais dimensões desta forma, vamos obter núcleos dimensionais cada vez mais elevados. Se continuarmos a fazer isto “para sempre”, acabaremos por ter infinitas dimensões. Note que só podemos fazer isso em abstrato. Os computadores só podem lidar com coisas finitas, por isso não podem armazenar e processar computações em espaços vectoriais dimensionais infinitos. Mas nós vamos fingir por um minuto que podemos, só para ver o que acontece. Depois vamos traduzir as coisas de volta para o mundo finito.

Neste hipotético espaço vectorial infinito dimensional, podemos adicionar vectores da mesma forma que fazemos com os vectores normais, bastando para isso adicionar as coordenadas correspondentes. No entanto, neste caso, temos de adicionar coordenadas infinitas. Da mesma forma, podemos multiplicar por escalares, multiplicando cada uma das (infinitamente muitas) coordenadas por um dado número. Vamos definir o kernel polinomial infinito enviando cada ponto ao vector infinito . Em particular, todo monômio nas variáveis e , como ou aparecerá em uma das entradas deste kernel, possivelmente muito abaixo da seqüência.

Para voltar ao mundo computacional, nós podemos recuperar nosso kernel quinqu-dimensional original apenas esquecendo todas, exceto as cinco primeiras entradas. Na verdade, o espaço quinqu-dimensional original está contido neste espaço dimensional infinito. (O kernel quinqu-dimensional original é o que obtemos ao projectarmos o kernel polinomial infinito neste espaço quinqu-dimensional.)

Agora respire fundo, porque vamos dar mais um passo em frente. Considere, por um momento, o que é um vector. Se você já tomou uma classe de álgebra linear matemática, você pode se lembrar que os vetores são oficialmente definidos em termos de suas propriedades de adição e multiplicação. Mas vou ignorar isso temporariamente (com desculpas a qualquer matemático que esteja lendo isso.) No mundo da computação, normalmente pensamos em um vetor como sendo uma lista de números. Se você leu até aqui, você pode estar disposto a deixar essa lista ser infinita. Mas quero que pensem num vector como sendo uma colecção de números em que cada número é atribuído a uma coisa em particular. Por exemplo, cada número do nosso tipo normal de vector é atribuído a uma das coordenadas/características. Num dos nossos vectores infinitos, cada número é atribuído a um ponto da nossa lista infinitamente longa.

Mas que tal isto: O que aconteceria se definíssemos um vector atribuindo um número a cada ponto do nosso espaço de dados (dimensional finito)? Tal vetor não escolhe um único ponto no espaço de dados; ao contrário, uma vez que você escolhe esse vetor, se você apontar para qualquer ponto no espaço de dados, o vetor lhe diz um número. Bem, na verdade, nós já temos um nome para isso: Algo que atribui um número a cada ponto no espaço de dados é uma função. Na verdade, nós temos olhado muito para funções neste blog, na forma de funções de densidade que definem distribuições de probabilidade. Mas o ponto é, podemos pensar nessas funções de densidade como vetores em um espaço vetorial infinito.

Como uma função pode ser um vetor? Bem, nós podemos adicionar duas funções simplesmente adicionando os seus valores em cada ponto. Este foi o primeiro esquema que discutimos para combinar distribuições no post da semana passada sobre modelos de mistura. As funções de densidade para dois vetores (blobs gaussianos) e o resultado de adicioná-los são mostrados na Figura abaixo. Podemos multiplicar uma função por um número de forma semelhante, o que resultaria em tornar a densidade total mais clara ou mais escura. Na verdade, estas são duas operações com as quais você provavelmente já teve muita prática na classe de álgebra e cálculo. Então ainda não estamos fazendo nada de novo, estamos apenas pensando nas coisas de uma maneira diferente.

O próximo passo é definir um kernel do nosso espaço de dados original para este espaço dimensional infinito, e aqui temos muitas escolhas. Uma das escolhas mais comuns é a função blob gaussiana que já vimos algumas vezes em posts anteriores. Para este kernel, vamos escolher um tamanho padrão para os blobs gaussianos, ou seja, um valor fixo para o desvio . Então enviaremos cada ponto de dados para a função Gaussiana centrada nesse ponto. Lembre-se que estamos pensando em cada uma dessas funções como um vetor, então esse kernel faz o que todos os kernels fazem: Ele coloca cada ponto do nosso espaço de dados original em um espaço vetorial dimensional maior (de fato, infinito).

Agora, aqui está o problema: Para trazer as coisas de volta ao mundo computacional, precisamos escolher um espaço vetorial dimensional finito sentado nesse espaço vetorial dimensional infinito e “projetar” o espaço dimensional infinito no subespaço dimensional finito. Escolheremos um espaço finito dimensional escolhendo um número (finito) de pontos no espaço de dados, tomando então o espaço vectorial abrangido pelos blobs gaussianos centrados nesses pontos. Este é o equivalente ao ritmo dos vectores definido pelas primeiras cinco coordenadas do núcleo polinomial infinito, como acima descrito. A escolha destes pontos é importante, mas voltaremos a isso mais tarde. Por enquanto, a questão é como projetar?

Para vetores dimensionais finitos, a maneira mais comum de definir uma projeção é usando o produto ponto: Este é o número que obtemos multiplicando as coordenadas correspondentes de dois vectores, depois adicionando-os a todos juntos. Assim, por exemplo, o produto ponto dos vetores tridimensionais e é .

Poderíamos fazer algo semelhante com as funções, multiplicando os valores que elas assumem em pontos correspondentes no conjunto de dados. (Em outras palavras, multiplicamos as duas funções juntas.) Mas não podemos então adicionar todos esses números juntos porque são infinitamente muitos deles. Em vez disso, vamos tomar uma integral! (Repare que estou a passar por cima de uma tonelada de detalhes aqui, e peço novamente desculpa a qualquer matemático que esteja a ler isto). O bom aqui é que se multiplicarmos duas funções gaussianas e nos integrarmos, o número é igual a uma função gaussiana da distância entre os pontos centrais. (Embora a nova função gaussiana terá um valor de desvio diferente.)

Em outras palavras, o kernel gaussiano transforma o produto ponto no espaço dimensional infinito na função gaussiana da distância entre os pontos no espaço de dados: Se dois pontos no espaço de dados estiverem próximos, então o ângulo entre os vetores que os representam no espaço do kernel será pequeno. Se os pontos estiverem muito afastados então os vectores correspondentes estarão próximos da “perpendicular”.

A parte prática

Então, vamos rever o que temos até agora: Para definir um kernel gaussiano -dimensional, primeiro escolhemos pontos no espaço de dados. Podemos então calcular as coordenadas do kernel de qualquer ponto no espaço de dados calculando sua distância para cada um desses pontos de dados escolhidos e tomando a função Gaussiana das distâncias.

Para entender melhor como esse kernel funciona, vamos descobrir como é a intersecção de um hiperplano com o espaço de dados. (Isto é o que é feito com os kernels a maior parte do tempo, de qualquer forma.) Lembre-se que um plano é definido por uma equação da forma onde são as coordenadas do ponto (no espaço do kernel dimensional superior) e são parâmetros que definem o hiperplano. Se estamos a utilizar um kernel gaussiano então, graças à nossa versão do produto ponto, os valores medem as distâncias para os nossos pontos escolhidos. O limite de decisão é assim o conjunto de pontos para os quais a função Gaussiana das distâncias a estes pontos satisfazem esta equação.

Isso ainda é bastante difícil de desempacotar, então vamos olhar para um exemplo onde cada um dos valores é ou 1 ou -1. Então perto de cada ponto de dados com etiqueta , o valor será muito próximo de 1, enquanto os outros valores serão pequenos, então a soma será positiva. Da mesma forma, perto de um ponto com , a soma será negativa. Assim, se então o limite de decisão separará os pontos positivos dos pontos negativos. Na verdade, ele irá esculpir uma região que lembra as bolas gaussianas que definem o núcleo. Um exemplo é indicado à esquerda na Figura abaixo, onde as cores indicam se os coeficientes são positivos ou negativos. Como você pode ver, o resultado parece algo como uma versão suave do algoritmo vizinho mais próximo.

Se ajustarmos os parâmetros , isto tem o efeito de mudar os tamanhos das bolas gaussianas em torno dos pontos, e assim move o limite de decisão para ou para longe deles, como à direita da Figura. Se um coeficiente muda de positivo para negativo, o limite de decisão se moverá de um lado de um ponto para o outro. Se tivermos um conjunto de dados rotulado (que pode ou não coincidir com os pontos que definem o kernel gaussiano) então o treinamento de um algoritmo de classificação linear (como SVM ou regressão logística) no espaço do kernel corresponde a mover este limite de decisão, dentro das restrições definidas acima, para maximizar quantos dos pontos de decisão estão no lado correto.

Então, isto nos dá mais flexibilidade para escolher o limite de decisão (ou, pelo menos, um tipo diferente de flexibilidade) mas o resultado final será muito dependente dos vectores que escolhemos. Se escolhermos demasiados (como se deixarmos os pontos que definem o kernel serem os mesmos que os pontos de dados) então correremos o risco de sobreajustamento, semelhante a como o algoritmo vizinho mais próximo tende a levar ao sobreajustamento. O que realmente queremos é um pequeno número de pontos que estejam distribuídos uniformemente pelo conjunto, idealmente de forma que cada um dos pontos esteja próximo à maioria dos pontos da mesma classe.

Finding such a collection of points is a very different problem from what we’ve been focusing on the posts so far on this blog, and falls under the category of unsupervised learning/descriptive analytics. (No contexto dos kernels, também pode ser pensado como seleção/engenharia de recursos). Nos próximos posts, vamos trocar de roupa e começar a explorar idéias nesse sentido.