Regressão Linear

Um modelo de regressão linear é dado por:

• Uma variável aleatória de interesse, denominada resposta, cujo interesse do modelo é aproximá-la;
• Um conjunto de variáveis aleatórias, denominadas regressoras, cujo objetivo é explicar, ou predizer, os valores da resposta;
• Um termo aditivo de erro, usado para contabilizar a imprecisão do modelo e da dependencia entre os regressores e a resposta. Este termo também é conhecido por erro de expectativa ou erro de explicação.

O modelo de regressão é dado por:

$$ d = \sum_{j=1}^{M} w_jx_j + \epsilon $$

Tal que:

• $M$ é a ordem do modelo
• $x_j$ é uma observação das variáveis de entrada, de dimensão $M$
• $w_j = [w_1, w_2, \dots, w_M] $ é o vetor de peso
• $\epsilon$ é o erro esperado
• $d$ é o valor estimado

Em forma matricial, o modelo de regressão é expresso:

$$d = w^Tx+ \epsilon$$

Tal que:

• $w^Tx$ é o produto interno entre $w^T$ e $x$.

O problema de regressão linear pode ser enunciado por:

"Dado um conjunto de tuplas $(x,d)$, tal que $x$ tem dimensão $M$, estimar o vetor de pesos $w$ de forma a minimizar o erro esperado".

Existem vários métodos para estimar $w$. A seguir é apresentada a estimativa por mínimos quadrados regularizada.

Estimativa de $w$ regularizada por mínimos quadrados

Seja $E_0(w)$ uma função de custo definida pela soma dos errors de expectativa ao quadrados dos N experimentos no ambiente (N amostras de teste). Metematicamente,

$$E_0(w) = \sum_{i=1}^{N} E_i^2$$

Podemos reescrever o modelo de regressão linear $d = w^t+ \epsilon$ para o i-ésimo experimento

$$d_i = w^Tx_i + \epsilon_i \quad i = 1, 2, \dots, N$$

Colocando $E_i$ em evidência,

$$-E_i = w^Tx_i - d_i $$

$$ \Leftrightarrow E_i = d_i - w^Tx_i \quad i = 1, 2, \dots, N$$

Aplicando o erro $E_0(w)$,

$$ E_0(w) = \frac{1}{2} \sum_{i=1}^{N} \left ( d_i - w^Tx_i \right )^2 $$

Minimizar $E_0(w)$ em relação a $w$ nos dá $w$ por máxima verossimilhança:

$$W_{\text{ML}} = \underset{w}{\operatorname{argmax}} \frac{1}{2} \sum_{i=1}^{N} \left ( d_i - w^Tx_i \right )^2$$

Que sofre de instabilidade de multiplas soluções. Adicionando um termo e regularização, temos $W_{\text{MAP}}$, que nos dá $w$ por máxima verossimilhança a priori:

$$W_{\text{MAP}} = \underset{w}{\operatorname{argmax}} \frac{1}{2} \sum_{i=1}^{N} \left ( d_i - w^Tx_i \right )^2 + \frac{\lambda}{2} ||w||^2$$

tal que $\lambda$ é o parâmetro de regularização e $||w||$ representa a norma euclidiana.

Minimização de $W_{\text{ML}}$ e $W_{\text{MAP}}$ por gradiente descentente

O desafio de implementar o gradiente descendente para otimizar $W_{\text{ML}}$ ou $W_{\text{MAP}}$ está no cálculo do vetor gradiente destas funções em relação a $w$, um vetor. Seja $w = [w_1, w_2, \dots, w_M]$. O vetor gradiente $\nabla_w f(w)$ de uma função $f(w)$ é dado por:

$$\nabla_w f(w) = \left [ \frac{f(w)}{\partial w_1}, \frac{f(w)}{\partial w_2}, \dots, \frac{f(w)}{\partial w_M} \right ]$$

Os vetores gradientes para otimizar $W_{\text{ML}}$ e $W_{\text{MAP}}$ são dados a seguir.

Vetor gradiente para otimizar $W_{\text{ML}}$

Ao expandir a soma

$$\frac{1}{2} \sum_{i=1}^{N} \left ( d_i - w^Tx_i \right )^2$$

temos:

$$f(w) = \frac{1}{2} \sum_{i=1}^{N} \left ( d_i - w^Tx_i \right )^2 = (d_1^2 + 2d_1w^Tx_1 + (w^Tx_1)^2) + (d_2^2 + 2d_2w^Tx_2 + (w^Tx_2)^2) \\ + (d_3^2 + 2d_3w^Tx_3 + (w^Tx_3)^2) + \dots + (d_N^2 + 2d_Nw^Tx_N + (w^Tx_N)^2)$$

Desta forma, usando as regras das derivadas de constantes, das derivadas de polinômios e a regra da cadeia, $\frac{f(w)}{\partial w_1}$ é dada por:

$$\frac{f(w)}{\partial w_1} = (-2d_1 x_{11} + 2 w^Tx_1 x_{11}) + (-2d_2 x_{21} + 2 w^Tx_2 x_{21}) \\ + \dots + (-2d_N x_{N1} + 2 w^Tx_N x_{N1}) \\ = 2x_{11}(-d_1 + w^Tx_1 ) + 2x_{21}(-d_2 + w^Tx_2 ) + \dots + 2x_{N1}(-d_N + w^Tx_N ) \\ = 2 \sum_{i=1}^{N}x_{i1} \left (-d_i + w^Tx_i \right )$$

Na realidade, para uma $\frac{f(w)}{\partial w_k}$ qualquer,

$$\frac{f(w)}{\partial w_k} = 2 \sum_{i=1}^{N}x_{ik} \left (-d_i + w^Tx_i \right )$$

Desta forma, a equação acima pode ser usada para calcular o vetor gradiente $\nabla_w f(w)$ tal que $f(w) = \frac{1}{2} \sum_{i=1}^{N} \left ( d_i - w^Tx_i \right )^2$.

No código Python abaixo, a função e0 computa $f(w)$ e a função grad_e0 computa $\nabla_w f(w)$. A função rls_ml calcula o vetor $w$ por máxima verossimilhança minimizando $f(w)$ pelo método do gradiente descendente.

Vetor gradiente para otimizar $W_{\text{MAP}}$

No caso de encontrar $w$ por máxima verossimilhança a priori, a função a minimizar é $g(w) = \frac{1}{2} \sum_{i=1}^{N} \left ( d_i - w^Tx_i \right )^2 + \frac{\lambda}{2} ||w||^2$. Nota-se que a diferença está apenas no termo $\frac{\lambda}{2} ||w||^2$. Portanto, o vetor gradiente $\nabla_w g(w)$ difere do caso $W_{\text{ML}}$ por apenas um termo.

Seja $t(w) = \frac{\lambda}{2}||w||^2$. Assim, $\nabla_w t(w) = \left [ \frac{t(w)}{\partial w_1}, \frac{t(w)}{\partial w_2}, \dots, \frac{t(w)}{\partial w_M} \right ]$.

$$\frac{t(w)}{\partial w_1} = \frac{\frac{\lambda}{2} \left ( \sqrt{\left (w_1^2 + w_2^2 + \dots + w_N^2 \right )} \right )^2}{\partial w_1} = \frac{\frac{\lambda}{2} \left (w_1^2 + w_2^2 + \dots + w_N^2 \right )}{\partial w_1} = \frac{\lambda}{2} 2 w_1 = \lambda w_1$$

É facil notar que para uma parcial $\frac{t(w)}{\partial w_k}$ qualquer,

$$\frac{t(w)}{\partial w_1} = \lambda w_k$$

.

Portanto,

$$\frac{g(w)}{\partial w_k} = \frac{f(w)}{\partial w_k} + \frac{t(w)}{\partial w_k} \\ = \left( 2 \sum_{i=1}^{N}x_{ik} \left (-d_i + w^Tx_i \right ) \right )+ \lambda w_k$$

Desta forma, a equação acima pode ser usada para calcular o vetor gradiente $\nabla_w g(w)$ tal que $g(w) = \frac{1}{2} \sum_{i=1}^{N} \left ( d_i - w^Tx_i \right )^2 + \frac{\lambda}{2} ||w||^2$.

No código Python abaixo, a função e0_map computa $g(w)$ e a função grad_e0_map computa $\nabla_w g(w)$. A função rls_map calcula o vetor $w$ por máxima verossimilhança a priori minimizando $g(w)$ pelo método do gradiente descendente.

Exemplo de Classificação usando Regressão Linear

Abaixo está um exemplo de classificação usando regresso linear. O dataset utilizado é o IRIS, composto de 3 classes linearmente separáveis (cada uma com 50 exemplos) usando 4 características. Os rótulos das classes são 0, 1 e 2. Desta forma, espera-se que a saída da regressão linear para vetores de entrada com as características da classe 0 aproxime-se mais de 0 do que dos demais valores, e assim por diante.

O conjunto de dados foi dividido em dois subconjuntos: um conjunto de treino e um conjunto de teste. A proporção foi 33% pra treino e 67% para teste. O conjunto de teste foi usado para aproximar o vetor $w$ por máxima verossimilhança a priori. Usando $w$ aproximado, o conjunto de treino é usado para determinar o valor médio esperado de cada classe. O valor esperado de cada classe é armazenado em um vetor indexado por classe, denominado centroids no código. Nota-se que, no caso onde a otimização reduz o erro a zero, as médias deveriam corresponder exatamente ao valor dos rótulos.

A classificação de um exemplo $x_k$ do conjunto de teste é realizada da seguinte maneira: $d_k = w_{\text{MAP}} {}^Tx_k$, tal que $d_k$ é o valor estimado. Se $w$ estiver suficientemente otimizado, $d_k$ tende ao rótulo correspondente à classe de $x_k$. A decisão sobre qual classe $d_k$ corresponde é realizada na função decide.

A função decide calcula a distância mínima entre $d_k$ e os valores do vetor centroids. A posição que corresponde à distância mínima é a classe escolhida para $d_k$.