21

Será que alguém me pode explicar o algoritmo Support Vector Regression? (usei este do scikit)

Já dei uma olhadela por alguns sites mas ainda não estou percebendo bem.

0

1 Resposta 1

34
+50

Processo de Decisão: Seleção de Características e Classificação

Imagine o seguinte exemplo (tirado do clássico livro Pattern Classification). Você precisa desenvolver um sistema para separar (classificar) automaticamente dois tipos de peixes, o Salmão (Salmon) e o Badejo/Robalo (Sea Bass). A questão é, como fazer isso? Se você considerar medir o comprimento do peixe (de alguma forma que não vem ao caso aqui), ao fazer uma análise sobre o tamanho de várias amostras de peixes (que você mesmo coletou) pode chegar ao seguinte resultado (a fonte das imagens também é o livro referenciado acima):

inserir a descrição da imagem aqui

Esse gráfico é um histograma que mostra o número de amostras (no eixo y, ou count) que contém um determinado comprimento (no eixo x, ou length). Pode-se observar que nessas amostras (e isso é importante! mais sobre o assunto depois) o Salmão tem sempre um comprimento maior do que o Badejo até aproximadamente 11 polegadas, e que o Badejo tem - em geral - comprimento maior do que o Salmão acima disso.

Dada essa observação, você poderia facilmente fazer um singelo IF num programa pra decidir se um peixe observado é um Salmão usando o valor que melhor separa as duas "classes". Nesse gráfico, o valor é 11 polegadas, e a linha pontilhada é chamada de "fronteira de decisão" (decision boundary). Seu programa funcionaria assim: se o comprimento medido for menor do que 11 polegadas, é um Salmão. Senão (se o comprimento medido for maior do que 11), é um Badejo.

Esse programa classificador pode funcionar bem em muitos casos, mas você deve observar no gráfico que há bastante chances de erro. Valores exatamente em 11 polegadas são difíceis de serem diferenciados e mesmo tendo mais ocorrências de Badejos com comprimento 17, por exemplo, ainda assim há bastante exemplos de Salmões com esse tamanho. Além disso, acima de 22 polegadas o Salmão passa a ter um tamanho maior. Poder-se-ia utilizar mais IFs com outras fronteiras de decisão, mas ainda assim nessas áreas seria muito fácil ocorrer erros de classificação. Talvez existam outras variáveis melhores.

De fato, se você for capaz de medir a luminosidade (lightness) da cor da pele dos peixes, observará o seguinte:

inserir a descrição da imagem aqui

Ou seja, com essa variável ou "característica" (em inglês chamada de feature) é bem mais fácil diferenciar os Salmões dos Badejos (com um só IF!). Ainda assim, tem alguma confusão na região do valor de luminosidade próximo a 5,8 (não lembro a unidade usada no exemplo), que é justamente a melhor fronteira de decisão para essa característica.

Mas, e se usarmos as duas características, será que é mais fácil decidir? Veja esse outro gráfico em que ambas as características são apresentadas nos dois eixos, e cada amostra (isto é, cada peixe) é apresentado como um ponto nesse espaço bidimensional:

inserir a descrição da imagem aqui

A linha separadora é também chamada de fronteira de decisão. Ela separa razoavelmente bem os peixes das amostras utilizadas para gerar o classificador (por isso são chamados de "dados de treinamento"), mas dá pra perceber que há ainda alguns erros, que podem se dever a falhas de medição das características ou a indivíduos foram do padrão (outliners) que talvez possam ser ignorados. Poderia-se tentar gerar um classificador EXATO (figura A abaixo), mas ele provavelmente estaria muito ajustado aos dados de exemplo (que podem ser pouco representativos ou conter erros de amostragem) e erraria por excesso (algo chamado sobreajuste ou overfitting). O ideal é gerar um modelo que aproxime o mundo real a partir dos dados de treinamento, e não meramente o replique. Talvez nesse exemplo seja mais interessente, ao invés de um separador linear (uma linha ou um plano), utilizar um separador polinomial (como uma curva próxima a uma equação do terceiro grau, por exemplo, como na figura B abaixo).

inserir a descrição da imagem aqui

Deve estar claro que por se ter utilizado duas características o resultado é uma dispersão das amostras em um plano bidimensional (eixos x e y, um para cada característica). Assim, a fronteira de decisão ainda é uma linha (nos exemplos anteriores, usando cada característica individualmente, era um ponto na verdade - o valor do IF). Deve também ser fácil perceber que ao adicionar mais uma característica qualquer, esse gráfico se tornaria um espaço tridimensional, e a fronteira de decisão passaria a ser um plano separando as duas classes. Com mais características, a dimensão do problema continuaria aumentando, e por isso essa fronteira de decisão passa a ser chamada genericamente de hiperplano.

O uso (ou a necessidade do uso) de muitas características nem sempre é bom, porque eleva as dimensões do problema e dificulta encontrar a fronteira de decisão, gerando a chamada maldição da dimensionalidade. Por isso, o processo de analisar e selecionar as melhores características (feature selection) é importantíssimo.

Classificação e Regressão

Esses exemplos tratam de aprender uma fronteira de decisão a partir de dados de treinamento (as amostras do problema) para classificar futuras amostras desconhecidas entre duas classes distintas (vamos chamar de A e B). Mas há outros tipos de problemas em que não se deseja classificar os novos dados, e sim calcular um valor de saída a partir das características de entrada. O processo é mais ou menos o mesmo, mas a fronteira de decisão é usada como a função aproximada que gera os resultados. A regressão linear é um exemplo clássico desse tipo de problema, em que a partir de um conjunto de dados se "aprende" uma equação que pode então ser utilizada para calcular o resultado a partir de uma nova sequência de parâmetros. Esse assunto é retomado mais pra frente.

A Máquina de Vetores de Suporte

Uma Máquina de Vetores de Suporte (ou Support Vector Machines = SVM) é um algoritmo construído para encontrar a melhor fronteira de decisão (as vezes chamada de superfície de decisão) que separa duas únicas classes (A e B) a partir das amostras de treinamento. Ele faz isso por um processo de otimização contínua em que busca encontrar o hiperplano que mais bem separa as duas classes. Esse hiperplano é aquele cuja distância (no gráfico abaixo chamada de maximum margin b) dos exemplos das classes é a maior possível (de modo a ficar o mais bem separado possível!). Note que nem todos os exemplos das classes A e B são necessários para se calcular essa distância e obter esse hiperplano (apenas aqueles mais próximos da área de confusão), e são justamente esses pontos (ou vetores, em termos geométricos utilizados na fundamentação matemática do algorítmo) que importam. Eles são chamados de "vetores de suporte" porque caracterizam o hiperplano separador, e é dai justamente que vem o nome do algoritmo.

Nota: A distância (com sinal, uma vez que um valor positivo está de um lado do hiperplano e um valor negativo está do outro lado) de uma amostra ao hiperplano separador é chamada de score é pode ser entendida como uma indicação do quão pertinente a amostra é a classe classificada (isto é, quanto mais longe do plano está uma amostra, mais fortemente pode-se acreditar que ela percente à classe daquele "lado").

inserir a descrição da imagem aqui

Não vou entrar em detalhes na implementação desse processo de otimização porque ele requer muito mais informações (e essa resposta já está fugindo do ideal do SOPT mesmo sem isso! hahaha), e também porque você não precisa saber de tais detalhes pra utilizar as bibliotecas como a do Scikit-Learn (Python) e o libSVM (C++). O que você precisa saber é que os Kernels usados pelo SVM servem apenas para permitir flexibilizar a fronteira de decisão, permitindo outras opções além de um separador linear. Também que para a classificação entre mais do que duas classes, o algoritmo simplesmente utiliza um conjunto de classificadores binários, treinados para cada combinação de pares (1, n-1): as amostras da classe A são consideradas normalmente e as demais amostras (de todas as outras classes) são consideradas como amostras de uma classe B - esse classificador individual apenas indica se uma amostra é ou não da classe A - com um desses para cada classe, pode-se separá-las pela melhor resposta dentre os classificadores para cada amostra.

O Scikit-learn, por exemplo, tem alguns kernels que permitem hiperplanos não-lineares muito úteis (a imagem de exemplo é do próprio site do Scikit-learn, ilustrando a separação de três classes de orquídeas do banco de dados clássico Iris Dataset):

inserir a descrição da imagem aqui

SVM e Regressão

As SVM são idealizadas para servirem como classificadores. Porém, podem ser utilizadas para regressão ao se fazer um passo adicional de treinamento em que os valores da regressão são estimados a partir das probabilidades de pertinência às classes obtidas com testes adicionais (e assim o treinamento demora bem mais). Esse procedimento se chama Platt Scaling e foi proposto por John C. Platt no artigo Probabilistic Outputs for Support Vector Machines and Comparisons to Regularized Likelihood Methods. O Scikit-learn, por exemplo, diferencia os métodos em classes separados: o SVC é o classificador (normal) e o SVR é o regressor, usando o Platt Scaling.

O princípio básico do Platt Scaling é o seguinte:

  1. O SVM é treinado normalmente a partir dos dados de entrada, gerando um classificador capaz de prever a classe ao indicar um valor de score com sinal para uma nova amostra de teste (scores negativos indicam classe A, e positivos indicam classe B, por exemplo).

  2. Usando validação cruzada K-Fold, são realizados diversos testes para prever o resultado com as diferentes amostras. Dependendo da qualidade do classificador, ele vai acertar algumas vezes e errar outras, e tais resultados são contabilizados. Como se fazem vários testes com partições dos próprios dados de treinamento (o tal do K-Fold), o algoritmo naturalmente demora mais pra executar.

  3. Com a proporção de acertos nos testes, um modelo probabilístico (geralmente usando a função logística) é construído (ou "aprendido") ajustando-se os parâmetros da função logística, para que o resultado do classificador deixe de ser uma indicação binária y = sinal(f(x)) (isto é, y = sinal do valor de score da classe A ou B, dada a observação de x - sendo x o vetor de características) e passe a ser uma probabilidade P(y=1|x) ou P(y=-1|x) (isto é, a probabilidade condicional da amostra ser da classe A, ou B, dada a observação de x).

Essa probabilidade é um valor real (infinitesimal) e não meramente um sinal. Representa realmente uma probabilidade de a predição estar certa dados testes realizados com o classificador, e não uma distância exclusiva de uma só amostra. Assim, esse novo programa é o equivalente de uma regressão e pode ser utilizado para prever um resultado ao invés de meramente indicar uma classificação binária.

P.S.: Alguém poderia perguntar: por que fazer uma regressão logística com vários testes ao invés de utilizar diretamente o valor do score (e não somente seu sinal) como valor de regressão? A resposta é que isso se deve para evitar o sobreajuste. O score é uma medida muito individual de uma amostra (sua particular distância ao hiperplano), e a probabilidade baseada em diversos testes diminui os efeitos de amostras ruins (devido a erros de medição, por exemplo).

5
  • A parte das SVM eu já percebia :) No entanto, obrigado pela explicação. Será que poderia desenvolver mais a parte da regressão? Como é que o algoritmo funciona?
    – Ins
    Commented 12/11/2014 às 10:19
  • 4
    +1. Magnífica resposta, uma das melhores que já vi aqui. =)
    – OnoSendai
    Commented 12/11/2014 às 16:54
  • @Ins Tentei adicionar um pouco mais de informação sobre o Plot Scalling, sem tornar o texto muito mais longo. Espero que ajude. Commented 12/11/2014 às 19:34
  • 2
    Sempre aprendo com as suas respostas, mesmo quando o assunto passa longe da minha zona de conforto (como nesta). Só não entendi se sea bass é badejo ou robalo :)
    – bfavaretto
    Commented 20/05/2015 às 2:45
  • 1
    @bfavaretto Que legal que curtiu a resposta (aliás, obrigado pela edição). Também nunca sei qual peixe é qual. :) Commented 20/05/2015 às 3:15

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .