Regressão Linear
Mínimos Quadrados
Digamos que estamos anotando o tamanho de uma planta a 3 dias em uma tabela e queremos ter uma estimativa de qual será o tamanho no dia 5:
| Dia | Tamanho |
|---|---|
| 1 | 1,72 |
| 2 | 2,73 |
| 3 | 2,98 |
Com a ideia que viemos construindo, podemos tratar dia e tamanho como duas dimensões e cada linha como um vetor, assim podemos visualizar em um gráfico:
Por alguma experiência com crescimento de plantas e pelo gráfico até então podemos dizer que o crescimento é aproximadamente linear, isso é, respeita uma função do tipo:
Onde \(t\) é a variável representando o tamanho, \(d\) é a variável representando o dia e \(\{a,b\}\) são os coeficientes. No gráfico essa equação representa uma reta que, idealmente, conteria todos esses vetores, porém no mundo real não contém.
A reta só conteria esses vetores se eles fossem colineares, poderíamos testar se os vetores são colineares se essa equação vale para os 3 vetores, ou seja, existe solução para esse sistema linear:
Dica
Nossas variáveis são temporariamente \(a\) e \(b\) antes de termos a função pronta, devemos achar os coeficientes com os valores aproximados de \(t\) e \(d\) que temos até agora.
Esse sistema não tem solução, note que a cada vetor que adicionamos, fica mais improvável desse sistema ter solução, porém se tivéssemos apenas 2 vetores teríamos uma reta.
Relembre
Porém, esse sistema ainda tem informações relevantes para o valor adequado de \(\{a,b\}\), vamos definir alguns \(\{a,b\}\) que resolvem um sistema linear similar a este (permitindo um \(t\) diferente).
Ao plotar as retas definidas por \(\{a,b\}\) percebemos que quanto mais o sistema linear parece o original, mais a reta aproxima da reta ideal.
Então queremos saber qual é o \(\{a,b\}\) que resolve o sistema linear mais próximo do original. Será que podemos pensar em "próximo" como próximo espacialmente?
Vamos apelar para a visualização da álgebra linear para ter outra interpretação desse problema:
Se pegarmos as 3 tentativas de \(\{a,b\}\) que fizemos anteriormente, aplicarmos na matriz e visualizarmos os vetores saídas, então veremos a similaridade com a conclusão anterior: quanto mais similar o sistema de equação mais o vetor saída está próximo do resultado ideal \(\mathbf{b}\).
Os 3 vetores saída das tentativas de \(\{a,b\}\) definem o Espaço Coluna, como \(\mathbf{b}\) não tem solução então não está no Espaço Coluna.
Como achamos o vetor saída mais próximo do resultado ideal?
Qual a menor distância entre um plano (Espaço Coluna) e um ponto \(\mathbf{b}\)?
Esse vetor saída será o vetor \(\mathbf{b}\) projetado no Espaço Coluna, logo conseguimos achar o vetor entrada pela Equação Normal.
Relembre
Com os valores de \(a,b\) podemos montar a função que relaciona tamanho e dia, assim podemos estimar o tamanho no dia 5:
Pseudoinversa
Podemos tentar generalizar a ideia da solução dos mínimos quadrados: queremos uma "solução" para todo sistema \(A\mathbf{x} = \mathbf{b}\):
- caso o sistema tenha uma solução, porém não conseguimos inverter \(A\)
- caso o sistema não tenha solução
- caso o sistema tenha infinitas soluções, porém não conseguimos inverter \(A\)
Note que já resolvemos os 2 primeiros casos, o exemplo dos Mínimos Quadrados era o segundo, porém se \(\mathbf{b}\) estivesse no Espaço Coluna então a projeção não mudaria nada e teríamos uma fórmula para calcular \(\mathbf{x}\).
Note que em um sistema comum podemos chegar a Equação Normal e isolar \(\mathbf{x}\):
No 3° caso podemos usar a ideia de que um vetor saída do Espaço Coluna tem apenas um vetor entrada no Espaço Linha, assim podemos assumir que \(\mathbf{x}\) está no Espaço Linha:
O problema é que quando projetamos no Espaço Coluna assumimos que as colunas eram uma Base para o Espaço Coluna, quando projetamos no Espaço Linha assumimos que as linhas eram uma Base para o Espaço Linha, ou seja, assumimos que as colunas ou linhas eram Linearmente Independentes, porém nada garante isso como no exemplo dos mínimos quadrados.
Será que existe uma forma de chegar nesses mesmos resultados sem necessitar de colunas/linhas Linearmente Independentes?
Será que existe uma forma unificada de "inverter" sem necessitar de avaliar cada caso?
Vamos quebrar a matriz A em pedaços e achar um valor que anula cada pedaço e isola o \(\mathbf{x}\), uma decomposição que vale para toda matriz é a Decomposição por Valor Singular:
Relembre
Podemos usar a forma truncada ou não do SVD, porém cada forma terá um impeditivo em isolar o \(\mathbf{x}\) em uma operação como:
- Truncada: \(VV^T\) são Ortonormais então não resultam na identidade
- Não truncada: a matriz \(\Sigma\) geralmente não é quadrada e nem sempre conseguimos achar uma "inversa pela esquerda"
Exemplo
No caso não truncado:
Caso \(\sigma \ne 0\), podemos achar a "inversa pela esquerda" independente de \(\Sigma\) ser quadrada:
Porém se \(\sigma = 0\), então ao invés de \(\frac{1}{\sigma}\) usamos 0, assim não chegaremos a identidade, chegaremos em algo parecido:
A notação para essa "inversa pela esquerda" ou aproximação dela será \(\Sigma^+\).
De qualquer forma, note que não faz sentido isolar \(\mathbf{x}\), já que \(\mathbf{x}\) pode ser infinitos vetores, então queremos "artificialmente" restringir \(\mathbf{x}\) a uma única solução, então vamos assumir:
Onde estamos usando a forma truncada, por isso o uso de \(\Sigma^{-1}\) e não \(\Sigma^+\).
Se testarmos essa equação acima no sistema dos Mínimos Quadrados:
Quase que magicamente chegamos no mesmo resultado, se continuarmos testando veremos que ela resolve os 3 casos de sistema sem depender do Posto. Vamos tentar entender esse resultado usando a forma truncada do SVD:
Relembre
Os vetores Singulares formam Bases para os Subespaços, \(A^TA\) para o Espaço Linha e o Espaço Nulo e \(AA^T\) para o Espaço Coluna e o Espaço Nulo Esquerdo.
Porém note que cortamos as bases para o Espaço Nulo e Espaço Nulo Esquerdo no SVD truncado, então:
1) \(\mathbf{y} = U^T\mathbf{b}\) será uma projeção na Base do Espaço Coluna, então o \(\mathbf{y}\) também pertencerá ao Espaço Coluna
2) \(\mathbf{z} = \Sigma^{-1} \mathbf{y}\) apenas escala o vetor, então o \(\mathbf{z}\) continuará no Espaço Coluna
3) \(\mathbf{x} = V\mathbf{z}\) faremos uma combinação linear das bases do Espaço Linha, então necessariamente \(\mathbf{x}\) pertencerá ao Espaço Linha
Note que é como se retirássemos os problemas que o Espaço Nulo e o Espaço Nulo Esquerdo causam em alguns sistemas.
A etapa 1 garante solução (exata ou por aproximação) para o sistema e a etapa 3 garante que a solução é única (\(\mathbf{x}\) pertence ao Espaço Linha), assim unificamos essas operações no que chamamos de Pseudoinversa, a notação usada é \(A^+\).
Resolução das Equações Normais
A condição para a Equação Normal ser válida: \(A\) tem colunas Linearmente Independentes. Caso contrário, use a Pseudoinversa.
Como \(A^TA\) é uma matriz Simétrica Definida Positiva, temos a oportunidade de usar a descomposição de Cholesky para resolver o sistema, porém se \(A\) for mal-condicionada, então a multiplicação \(A^TA\) será muito mais mal-condicionada.
Outra forma de resolver é pela decomposição QR, note que conseguimos cortar algumas multiplicações de matrizes densas, então nosso condicionamento será baixo:
A resolução A=LU terá o mesmo problema de condicionamento da Cholesky, porém com um número de operações maior, então não temos motivo para escolher essa forma.