Modelos de Vetores de Suporte

Uma Introdução ao Aprendizado Estatístico de Máquina

SUMÁRIO

🗒️ Resumo

🗒️ 1. Introdução

🗒️ 2. Fundamentação teórica

🗒️ 3. Primeiros passos Hands-on

🗒️ 4. Aplicações com SVM

• 📋 4.1 Linguagem R

• 📋 4.2 Linguagem Python

🗒️ 5. Outros tipos de Modelos de Vetores de Suporte

🗒️ 6. Exercícios

🗒️ Apêndice

APÊNDICE

Conceitos básicos de Vetores

Um segmento de reta com comprimento e direção, i.e., orientado é chamado de vetor. Se o vetor tem comprimento \(1\) é chamado de vetor unitário. Dadas as coordenadas do vetor \(\bar{p} = (p_1, \cdots, p_n)\) em \(\mathbb{R}^n\), podemos calcular seu tamanho ou norma, representado por \(|\bar{p}|\) como:

\[|\bar{p}| = \sqrt{p_1^2 + \cdots + p_n^2}.\]

Sejam \(\bar{a} = (a_1, \cdots, a_n)\), \(\bar{b} = (b_1, \cdots, b_n)\) dois vetores em \(\mathbb{R}^n\), então \(\bar{a}\) e \(\bar{b}\) serão iguais se, e somente se os componentes correspondentes de cada vetor são iguais. Formalmente, temos:

\[\bar{a} = \bar{b}, \textrm{ se } a_1 = b_1, \cdots, a_n = b_n.\]

Sejam \(\bar{a} = (a_1, \cdots, a_n)\), \(\bar{b} = (b_1, \cdots, b_n)\) e \(\bar{c} = (c_1, \cdots, c_n)\) três vetores em \(\mathbb{R}^n\), então definimos a adição de vetores como:

\[\bar{c} = \bar{a} + \bar{b}\] tal que, \(c_1 = a_1 + b_1\), \(\cdots\), \(c_n = a_n + b_n\).

O vetor \(\bar{0} = (0, \cdots, 0)\) é chamada de vetor nulo, possuindo \(n\) elementos, tem tamanho \(0\) e pode ser considerado o ponto de origem de um sistema de coordenadas \(n\)-dimensional. Por fim, temos o vetor oposto \((-\bar{a})\), que é o vetor \(\bar{a}\) com todos os componentes negativos, i.e.,

\[-\bar{a} = -(a_1, \cdots, a_n) = (-a_1, \cdots, -a_n).\]

Nas duas tabelas a seguir são apresentados alguns axiomas de soma de vetores e de multiplicação de vetores por um escalar. Um conjunto \(V\) de vetores em \(\mathbb{R}^n\) é chamado de espaço vetorial real se os axiomas de adição de vetores e multiplicação de vetores por um escalar apresentados nas Tabelas 1 e 2 são satisfeitos.

Comutatividade	\(\bar{a} + \bar{b} = \bar{b} + \bar{a}\)
Associatividade	\((\bar{a} + \bar{b}) + \bar{c} = \bar{a} + (\bar{b} + \bar{c})\)
Identidade	\(\bar{a} + \bar{0} = \bar{a}\)
Reciprocidade	\(\bar{a} + (-\bar{a}) = \bar{0}\)

Tabela 1. Axiomas de adição de vetores.

Distributiva I	\(q(\bar{a} + \bar{b}) = q\bar{a} + q\bar{b}\)
Distributiva II	\((p + q)\bar{a} = p\bar{a} + q\bar{a}\)
Associativa	\((pq)\bar{a} = p(q\bar{a})\)
Identidade	\(1\bar{a} = \bar{a}\)

Tabela 2. Axiomas de multiplicação de um vetor por um escalar. Aqui \(p,q \in \mathbb{R}\)

Dado dois vetores \(\bar{a} = (a_1, \cdots, a_n)\) e \(\bar{b} = (b_1, \cdots, b_n)\) em um espaço vetorial real \(n\)-dimensional \(\mathbb{R}^n\), defini-se o produto escalar \(\bar{a} \cdot \bar{b}\) como:

\[\bar{a} \cdot \bar{b} = a_1b_1 + \cdots + a_nb_n = |\bar{a}||\bar{b}|cos(\gamma)\]

onde \(|\bar{a}|\) e \(|\bar{b}|\) são as normas dos vetores \(\bar{a}\) e \(\bar{b}\), respectivamente, e \(\gamma\) é o ângulo entre os dois vetores. Dois vetores \(\bar{a}\) e \(\bar{b}\) com \(|\bar{a}| > 0\) e \(|\bar{b}| > 0\) são ditos ortogonais se formam um ângulo de \(90^{\circ}\) entre si. Pela definição acima, temos que se \(\bar{a}\) e \(\bar{b}\) são ortogonais \(\bar{a} \cdot \bar{b} = 0\).

Na Tabela abaixo são expostas algumas identidades algébricas para o produto de vetores por um escalar.

Linearidade	\((p\bar{a} + q\bar{b}) \cdot \bar{c} = p\bar{a} \cdot \bar{c} + q\bar{b} \cdot \bar{c}\)
Simetria	\(\bar{a} \cdot \bar{b} = \bar{b} \cdot \bar{a}\)
Não negatividade	\(\bar{a} \cdot \bar{a} \geq 0\)
Não degeneração	\(\bar{a} \cdot \bar{a} = 0, \textrm{ se } \bar{a} = 0\)

Tabela 3. Identidades algébricas do produto escalar.

Além das identidades apresentadas acima, temos as seguintes identidades que se mostram bastante úteis. Começando pela relação entre a norma de um vetor e o produto escalar. \[|\bar{a}| = \sqrt{\bar{a} \cdot \bar{a}}. \] Na sequência temos uma derivação para o \(cos(\gamma)\) onde: \[cos(\gamma) = \frac{\bar{a} \cdot \bar{b}}{|\bar{a}||\bar{b}|}. \]

Seja \(\bar{a}\) e \(\bar{b}\) vetores em \(\mathbb{R}^n\) que formam um ângulo \(\gamma\) entre eles, dizemos que \(P_{\bar{a}}\) é a projeção de \(\bar{a}\) na direção de \(\bar{b}\), de forma que: \[p_{\bar{a}} = |\bar{a}|cos(\gamma) = \frac{|\bar{a}|(\bar{a} \cdot \bar{b})}{|\bar{a}||\bar{b}|} = \frac{\bar{a} \cdot \bar{b}}{|\bar{b}|}.\] Na Figura 1, temos a representação geométrica da projeção do vetor \(\bar{a}\) na direção de \(\bar{b}\).

Figura 1. Representação geométrica da projeção do vetor \(\bar{a}\) na direção de \(\bar{b}\).

Retas, Planos e Hiperplanos

A forma mais simples de separar dois grupos de observações no plano é traçando uma reta, um plano ou hiperplano (a depender da dimensão dos dados) o qual pode ser representado por uma função linear. No caso do plano (\(\mathbb{R}^2\)), podemos definir dita função por uma equação da forma \[f(x) = y = -mx\]

em que \(x, y, m \in \mathbb{R}\), esta função é interpretada como um conjunto de pontos \((x, y) \in \mathbb{R}^2\), tais que \[mx + y = 0.\] Se definimos \(w_1 = m\) e \(w_2 = 1\), podemos escrever:

\[f(x) = w_1x + w_2y = 0\] que pode ser visto como o produto escalar entre os vetores \(\bar{w} = (w_1, w_2)\) e \(\bar{x} = (x, y)\): \[f(x) = w_1x + w_2y = \bar{w} \cdot \bar{x} = 0.\]

Como o produto escalar entre os dois vetores é zero, implica que \(\bar{w}\) e \(\bar{x}\) são ortogonais, sendo \(\bar{x}\) interpretado como o vetor de posição para qualquer ponto \((x, y)\) pertencente a reta \(mx + y = 0\), e o \(\bar{w}\) chamado de vetor normal. Como esta reta passa pela origem, o vetor de posição \(\bar{x}\) é paralelo a reta para qualquer ponto pertencente a ela. Uma vez que \(\bar{w}\) é ortogonal a \(\bar{x}\) e o qual é paralelo a reta, então \(\bar{w}\) é ortogonal a reta.

Observando um caso mais geral, ao inserir uma variável de viés ( - Intercepto) \(b \in \mathbb{R}\), a reta será escrita como: \[f(x) = y = -mx + b.\] De modo análogo para o caso em que a reta passa pela origem, pode ser mostrado que: \[ \bar{w} \cdot \bar{x} = b \]

com \(\bar{w} = (m, 1)\) e \(\bar{x} = (x, y)\). Observe que o vetor normal \(\bar{w}\) e o vetor de posição \(\bar{x}\) não são mais ortogonais, dado que a reta não passa mais pela origem, porém, \(\bar{w}\) segue ortogonal a reta. Note que através do produto escalar entre vetores \(\bar{w} \cdot \bar{x} = b\) podemos especificar a equação de uma reta qualquer no plano.

De forma analoga, podemos estender estes conceitos para um espaço tridimensional. Sejam \(\bar{w} = (w_1, w_2, w_3)\) e \(\bar{x} = (x, y, z)\), então: \[ \bar{w} \cdot \bar{x} = b \]

descreve um plano com \(\bar{w}\) vetor normal ao plano e \(\bar{x}\) o vetor de posição dos pontos no plano. Da mesma forma, se considerarmos \(\bar{w} = (w_1, \cdots, w_n)\) e \(\bar{x} = (x_1, \cdots, x_n)\), a equação \(\bar{w} \cdot \bar{x} = b\) define um hiperplano no espaço 3-dimensional.

Hiperplano separador

Superfície linear de decisão a partir da origem

Consideremos um conjunto de dados de treinamento bidimensional contido no espaço \(\mathbb{R}^2\) e linearmente separável por uma reta passando pela origem. Essa linha será denotada por \(g(\textbf{x})\) e pode ser escrita como: \[ g(\textbf{x})= \textbf{w} \cdot \textbf{x} = 0 \] em que \(\textbf{w}\),\(\textbf{x} \in \mathbb{R}^2\).

Como \(g\) separa o conjunto de treinamento perfeitamente ela será chamada de superfície de decisão. Seja \(\textbf{a} \in \mathbb{R}^2\) tal que \(a \in \mathcal{S}\) sendo \(\mathcal{S}\subset\ \mathbb{R}^2.\) O ponto podera ser classificado a partir de sua localização no plano, i.e., se estiver acima ou abaixo da superfície de decisão. Para determinar a decisão do posicionamento de \(\textbf{a}\) definimos \[ g(\textbf{a})= \textbf{w} \cdot \textbf{a} = \mid \textbf{w} \mid \mid \textbf{a} \mid \cos \gamma = k \] em que \(\gamma\) é o ângulo entre o vetor normal da superfície de decisão \(\textbf{w}\) e o vetor de posição \(\textbf{a}.\) Note que

• O valor de \(k\) será positivo se \(\textbf{a}\) está acima da superfície com \(\gamma \leq 90^{\circ}\).

• O valor de \(k\) será negativo se \(\textbf{a}\) está abaixo da superfície com \(\gamma > 90^{\circ}\).

A Figura 2 apresenta de forma esquemática a superfície de decisão para duas classes de pontos (+) acima da superficie de decisão e (-) abaixo da superficie de decisão em função do vetor \(\textbf{w}\)

Figura 2. Divisão do plano para duas classes através da superficie de decisão que passa pela origem.

Entretanto uma forma mais razoável é considerar uma função de decisão dicotómica, da forma

\[ f(\textbf{x}) = \begin{cases} +1, & \quad \text{ se } g(\textbf{x}) \geq 0 \\ -1, & \quad \text{ se } g(\textbf{x}) < 0 \end{cases} \]

Superfície linear de decisão com um intercepto

Suponhamos novamente que conjunto de dados de interesse é bidimensional e linearmente separável por uma reta que passa pelo eixo das coordenadas \(y\) no valor \(b\). Então a linha \(g\) pode ser escrita como:

\[ g(\textbf{x})= b. \] Através de uma adição de vetores, podemos o vetor \(\textbf{z}\) de modo que \(\textbf{a}=\textbf{c}+\textbf{z}\), e portanto \(\textbf{z}=\textbf{a}-\textbf{c}\), como ilustrado na Figura 3, em que, a esquerda há a divisão da superfície de decisão com intercepto fora da origem, para duas classes e na figura da direita há a classificação do vetor \(\textbf{a},\) sendo também \(\textbf{w}=\bar{w}\).

Figura 3. Divisão do plano para duas classes fora da origem. Fonte: Adaptado de Hamel (2011)

Determinando, então, uma solução para o problema de classificação. Uma vez que o vetor normal \(\textbf{w}\) surge da reta \(g\) no ponto o qual tem a direção apontada pelo vetor \(\textbf{c}\) temos que \(\textbf{w}\) é perpendicular a reta \(g\). Neste caso, o vetor \(\textbf{z}\) será o vetor posição do ponto \(\textbf{a}\) com respeito ao ponto \(\textbf{c}.\) Finalmente o ponto \(\textbf{c}\) pode ser visto como a solução para superfícies lineares de decisão a partir da origem, uma vez que o ponto \(\textbf{a}\) e o ponto \(\textbf{c}\) partem da origem e os vetores \(\textbf{w}\) e \(\textbf{z}\) estão deslocados a partir do ponto que aponta a direção do vetor \(\textbf{c}.\) Nesta situao, o produto escalar é dado por:

\[ \textbf{w} \cdot \textbf{z}= \mid \textbf{w} \mid \mid \textbf{z} \mid \cos \gamma = k \]

De forma análoga ao caso anteriormente discutido, o ponto \(\textbf{a}\) será classificado em função de sua posição, i.e., ele se encontrar acima ou abaixo da superfície de decisão \(g.\) Desta forma o valor de \(k\) novamente será usado como limiar discriminatório, ou seja,

• o valor de \(k\) será positivo se o ponto \(\textbf{a}\) estiver acima da superfície de decisão se \(\gamma \leq 90^{\circ}\) .

• o valor de \(k\) será negativo se o ponto \(\textbf{a}\) estiver abaixo da superfície de decisão com \(\gamma > 90^{\circ}\).

Novamente, \(\boldsymbol{\gamma}\) representa o ângulo entre o vetor normal \(\textbf{w}\) e o vetor \(\textbf{z}\).

A função de decisão pode ser definida agora como: \[\begin{eqnarray*} \textbf{w} \cdot \textbf{z} = \textbf{w} \cdot (\textbf{a} - \textbf{c}) \\ \textbf{w} \cdot \textbf{z} = ( \textbf{w} \cdot \textbf{a} ) - ( \textbf{w} \cdot \textbf{c} )\\ \textbf{w} \cdot \textbf{z} = ( \textbf{w} \cdot \textbf{a} ) - b\\ \textbf{w} \cdot \textbf{z} = g(\textbf{a} ) - b \end{eqnarray*}\]

Logo, para encontrar o produto escalar do ponto \(\textbf{a},\) basta transferir a superfície de decisão \(g\) em \(\textbf{a}\) e então subtrairmos o intercepto \(b.\)

Novamente, a forma mais simples da função de decisão pode ser definida por:

\[ f(\textbf{x}) = \begin{cases} +1 & \quad \text{ se } g(\textbf{x}) - b \geq 0, \\ -1 & \quad \text{ se } g(\textbf{x}) - b < 0 \end{cases} \] para todo \(\textbf{x} \in \mathbb{R}^{2}\) .

Até agora foram desenvolvidas funções e superfícies de decisão para \(\mathbb{R}^{2},\) porém tais conceitos podem ser estendidos para dimensões superiores.

Para uma superfície de decisão \(\textbf{w} \cdot \textbf{x} = b\) no espaço euclidiano \(p\)-dimensional (\(\mathbb{R}^{p}\)), a função de decisão é dada por: \[ \widehat{f}(\textbf{x}) = sgn (\textbf{w} \cdot \textbf{x} - b) \] qm que \(\textbf{w},\textbf{x} \in \mathbb{R}^{p}\), \(b \in \mathbb{R}^{2}\) e \(sgn\) é a função sinal tal que

\[ sgn(k) = \begin{cases} +1, & \quad \text{ se } k \geq 0, \\ -1, & \quad \text{ se } k < 0 \end{cases} \] para todo \(k \in \mathbb{R}\).

Referências

Hamel, Lutz H. 2011. Knowledge discovery with support vector machines. John Wiley & Sons.