Losses e Otimização

Artigo por Miguel Cyrineu Vale

Tópicos Abordados

• Introdução e ideias básicas
• Losses: o que é, detalhamento na MSE e MAE
• Otimização da regressão linear multivariada com o OLS
• Detalhamento dos padrões na literatura

Introdução

Em muitos dos artigos sobre modelos matemáticos do NOIC, falamos sobre os parâmetros de melhor ajuste dos modelos – mas nem sempre falamos de onde eles vêm.

Por exemplo, no artigo sobre Regressão Logística, primeiro apresentamos os dados, e depois a curva do modelo ajustada, juntamente com os parâmetros; como se tivessemos descoberto-os com mágica.
E, até um certo ponto, isso é meio o que acontece! Para encontrar os parâmetros dessas funções, utilizamos uma biblioteca do python, que faz isso para gente. No entanto, saber o que realmente acontece por trás desses algoritmos nos ajuda a entender como o modelo funciona, e melhora nossa intuição na hora de fazer escolhas para criar modelos melhores.

Aqui, vamos entender como funciona esse processo de encontrar os melhores pesos de um modelo.

Para acharmos os pesos de “melhor ajuste”, temos que antes definir o que é um ajuste bom. Um ajuste bom, de certa forma, é algo subjetivo – existem diversas maneiras de calcular o quão bom está um modelo, cada uma com suas vantagens e desvantagens, mas a forma mais comum de quantificar isso são as losses (ou funções de perda).

As losses

Uma função de loss é uma função que quantifica o erro (loss) de uma predição.
A única “regra” que define uma loss é que, quanto maior ela é, maior deve ser o erro do modelo naquele determinado ponto. Ou seja, ela pode ser o que nós quisermos, desde que satisfaça isso. No entanto, na prática, existem algumas outras características que são essenciais para seu funcionamento.

As duas losses mais comuns, utilizadas em modelos de regressão (que prevêem um valor contínuo, como o preço de um imóvel), são a MAE (Mean Absolute Error) e a MSE (Mean Squared Error). Como o próprio nome diz, elas são calculadas a partir da média do erro absoluto e da média do erro ao quadrado. Aqui estão as definições dessas losses para apenas um ponto:

$AE = \left| y-\hat{y} \right|$

$SE = (y-\hat{y})^{2}$

Isso é para apenas um ponto. Para um modelo inteiro, tiramos a média das losses de todos os pontos, obtendo, de fato, a MAE e MSE:

$\mathcal{L}_{MAE}(y, \hat{y}) = \frac{1}{n} \displaystyle \sum_{i=1}^{n} \left| y_i-\hat{y}_i \right|$

$\mathcal{L}_{MSE}(y, \hat{y}) = \frac{1}{n} \displaystyle \sum_{i=1}^{n} (y_i-\hat{y}_i)^{2}$

_{Importante! A loss geralmente é representada por $L$, $J$ ou $\mathcal{L}$.}

A MAE

A MAE é a loss mais simples de todas – é apenas a diferença entre o valor predito e o valor real. O módulo é utilizado nela para que os erros negativos não cancelem os positivos na hora de fazer a média. Ela é boa pela sua simplicidade e interpretabilidade, já que nos diz exatamente o quanto que o modelo erra, em geral. No entanto, ela tem uma desvantagem: penaliza erros maiores com o mesmo “peso” que erros menores. Isto é, um erro de 1000 vai ser penalizado na mesma proporção que um erro de 10, por mais que ele deveria ser muito mais importante, já que é muito mais absurdo.

A MSE

A MSE também é bastante simples, mas traz uma vantagem e uma desvantagem. A vantagem é que, diferentemente da MAE, ela penaliza mais erros maiores do que erros menores, o que, na maioria dos casos, é desejável ao treinar modelos (existem, no entanto, algumas exceções, como em conjuntos de dados com muitos outliers). Contudo, ela não é tão interpretável quanto a MAE, já que distorce os valores dos erros de acordo com os seus tamanhos.

Uma alternativa a ela é a RMSE, que é a raiz quadrada da MSE. Ela retém a característica de penalizar mais erros maiores, mas é mais interpretável que a MSE crua.

A Otimização

Agora que já temos nossas losses definidas, temos como saber se nosso modelo está bom, e, acima disso, temos como saber para onde nosso modelo “deve ir” para melhorar.

Como uma loss pequena indica um modelo bom, nosso papel é encontrar os parâmetros que minimizem essa loss, já que aí estará o melhor modelo. Para fazer isso, é necessario ter uma função que nos da a loss do modelo, dados os parâmetros. Podemos fazer isso pegando a saída do modelo ($\hat{y}$) e passando pela loss (vamos usar MSE aqui):

$\mathcal{L}(y) = \frac{1}{n} \displaystyle \sum_{i=1}^{n} (y_i-\hat{y}_i)^{2}$, onde ${\hat{y}}$ é a saída do nosso modelo.

Para simplificar, vamos dizer que nosso modelo é uma regressão linear: $M(x) = \hat{y} = A^\top X + b$, onde $X$ é um vetor com todos os nossos features ($x_1, x_2, \dots, x_n$), e $A$ é um vetor com todos os pesos ($a_1, a_2, \dots, a_n$). Colocando-o na loss

$\mathcal{L}(\hat{y}) = \frac{1}{n} \displaystyle \sum_{i=1}^{n} (b + A_i^\top X_i -y_i)^{2}$

Como $X$ é um vetor com valores conhecidos (todos os pontos de dados), essa função depende apenas dos valores de $A$ e $b$. Assim, vamos reescrevê-la usando-os como parâmetros:

$\mathcal{L}(A, b) = \frac{1}{n} \displaystyle \sum_{i=1}^{n} (b + A_i^\top X_i-y_i)^{2}$

_{Importante! Essa expressão pode ser um pouco confusa, pois ela está em função de $A$ e $b$ (coeficientes), e não de $X$. Na função de um modelo, fornecemos $X$ (os dados) e ela nos fornece a predição, mas aqui, fornecemos os coeficientes e ela nos fornece a média da Loss.}

Beleza! Agora temos uma função que nos dá a loss dado os valores de A e o valor de b. Se acharmos o valor mínimo dessa função, teremos os melhores pesos para o nosso modelo, de acordo com nossa loss. Para achar o valor mínimo de qualquer função linear, podemos simplesmente derivá-la, e achar o valor onde a derivada é 0. Como temos mais de um parâmetro, vamos calcular as derivais parciais para cada parâmetro, igualar tudo a 0, e resolver o sistema. Mas primeiro, vamos passar nossa função para a forma matricial. Assim, retiramos a somatória, que vai facilitar o cálculo das derivadas:

Primeiro, definimos $X$ como uma matriz com todos os $X_i$: $X \in \mathbb{R}^{n \times d}$ onde a linha $i$ é $X_i^\top$. Definimos também $A \in \mathbb{R}^{d}$ como todos os coeficientes lineares $b$ como um escalar e $\mathbf{1} \in \mathbb{R}^{n}$ como um vetor de uns (um viés para cada ponto de dado).

$\mathcal{L}(A, b) = \lVert Y - XA - b\mathbf{1} \rVert_2^{2}$

_{Dissecando essa função, temos:
O vetor de coeficientes lineares ($d$ deles, um pra cada $x$); o vetor de $X$ ($dn$ deles, $d$ pra cada ponto de dado, tendo no total $n$ pontos de dados); o escalar $b$ multiplicado pelo vetor de uns (resultando num vetor com $n$ deles, um pra cada $X_i$); e o vetor $Y$ ($n$ $y$s, que são os dados “reais”). Nós multiplicamos os $X$ pelos $A$, somamos o $b$, e tiramos a diferença do valor real. Depois, fazemos uma normalização euclideana (o $||$) e elevamos-a ao quadrado, que eleva cada elemento ao quadrado, soma tudo e tira a média. Resumindo: rodamos a função para todos os pontos, e tiramos a média das losses.}

Vamos chamar $Y - XA - b\mathbf{1}$ de $r$ (chamado de residual), e derivar parcialmente w.r.t. A e b:

$\mathcal{L} = \lVert r \rVert_2^{2} = r^\top r = \displaystyle \sum_{i}r_i^{2}$

$\displaystyle \frac{\partial r^\top r}{\partial A} = \displaystyle \sum_i \frac{\partial r_i^2}{\partial A}\displaystyle$

Para cada $r_i$:

$\displaystyle \frac{\partial r_i^2}{\partial A} = 2r_i\frac{\partial r_i}{\partial A}$

Somando tudo:

$\displaystyle\frac{\partial r^\top r}{\partial A} = \displaystyle 2 \sum_i r_i \frac{\partial r_i}{\partial A}$

Em forma vetorial:

$\displaystyle \frac{\partial \mathcal{L}}{\partial A} = 2 \left( \frac{\partial r}{\partial A} \right)^\top r$

Como $-AX$ é o único termo de $r$ que varia w.r.t. A, derivamos ele e zeramos todos os outros:

\begin{equation}
\boxed{\displaystyle \frac{\partial \mathcal L}{\partial A} = 2X^\top r}
\label{eq:LA}
\end{equation}

Agora, vamos calcular a parcial do viés:

$\displaystyle \frac{\partial \mathcal{L}}{\partial b} = 2(\frac{\partial r}{\partial b})^\top r = -2 \mathbf{1}^\top r$

\begin{equation}
\boxed{\frac{\partial \mathcal{L}}{\partial b} = -2 \mathbf{1}^\top r}
\label{eq:Lb}
\end{equation}

Beleza, temos as derivadas parciais da nossa função de perda w.r.t. os pesos e w.r.t. o viés. Como eles indicam o quanto a loss varia em função dessas variáveis, e queremos achar o ponto mínimo dessa função (já que alí teremos a menor loss, ou seja, o melhor modelo), precisamos zerar essas derivadas. O ponto ponto onde a derivada é zero indica que estamos em um “vérticie” do gráfico, ou seja, em um ponto onde o gráfico apenas aumenta ou apenas diminui para qualquer direção.

Lembrando que, como estamos tratando de uma regressão linear, o vérticie da função é obrigatóriamente o mínimo global (ponto onde a loss é a menor na superfície inteira), já que o gráfico dela é convexo (pense numa parábola com a>0).

Eu sei que isso pode parecer meio confuso, então vamos visualizar um gráfico de loss arbitrário, e depois suas parciais, pra realmente entender o que estamos fazendo aqui.

_{Importante: Aqui, usei apenas uma variável (apenas um X), portanto, temos apenas duas dimensões: um peso/coeficiente linear para X e um viés. No entanto, se tivessemos, por exemplo, 5 variáveis, teríamos um gráfico 6-dimensional.}

Nesse gráfico, podemos ver uma coisa importante: o vérticie do gráfico, em vermelho, onde a derivada é 0, corresponde ao mínimo global da loss. Isso ocorre pois todos os gráficos de loss de regressão linear são convexos (como uma tigela). Voltando à nossa matemática, isso significa que se igualarmos as duas derivadas a 0, e resolver o sistema de n + 1 variáveis (n pesos e um viés), acharemos esse ponto do vérticie do gráfico, onde estão os melhores parâmetros para o nosso modelo.

Então vamos fazer exatamente isso para chegar na nossa fórmula para achar tais parâmetros:

_{Aviso: daqui pra frente, a matemática fica bem pesada. Se você já entendeu o conceito, pode pular para a fórmula final, e para a sessão “Modelo Matemático Convencional” abaixo. Não se preocupe tanto em entender cada detalhe aqui.}

Para os coeficientes lineares: (A)

$\displaystyle \frac{\partial \mathcal L}{\partial A} = 2X^\top r = 0$

$\displaystyle 2X^\top (Y - XA - b\mathbf{1}) = 0$

E para o viés: (b)

$\displaystyle \frac{\partial \mathcal{L}}{\partial b} = -2 \mathbf{1}^\top r = 0$

$\displaystyle -2 \mathbf{1}^\top (Y - XA - b\mathbf{1}) = 0$

Simplificando o $2$, distribuíndo o $X^\top$ e passando o $Y$ par ao outro lado, ficamos com:

\begin{cases}
\displaystyle X^\top XA + X^\top b\mathbf{1} = X^\top Y \\
\displaystyle \mathbf{1}^\top XA + \mathbf{1}^\top b\mathbf{1} = \mathbf{1}^\top Y
\end{cases}

Para facilitar a solução, vamos assumir:

$S := X^\top X,\qquad c := X^\top\mathbf{1},\qquad r := X^\top Y,\qquad s := \mathbf{1}^\top Y,\qquad n := \mathbf{1}^\top\mathbf{1}.$

Supondo $S$ invertível, podemos resolver a primeira:

$S A + b\,c = r \quad \Rightarrow \quad A = S^{-1}(r - b\,c)$

Substituindo $A$ na segunda:

$c^\top S^{-1}(r - b c) + n\,b = s$
$c^\top S^{-1} r - c^\top S^{-1} c\,b + n\,b = s$

Isolando $b$:

$b\big(n - c^\top S^{-1} c\big) = s - c^\top S^{-1} r$

Finalmente, o viés $b$ é:

$b = \dfrac{s - c^\top S^{-1} r}{n - c^\top S^{-1} c}$

e o vetor de coeficientes $A$ é:

$A = S^{-1}\big(r - c\,b\big)$

Substituindo $S, c, s, n$ e $r$ por suas definições, obtemos as fórmulas finais para os coeficientes lineares $A$ e o viés $b$:

$\boxed{b=\frac{\mathbf{1}^\top Y-\mathbf{1}^\top X\,(X^\top X)^{-1} X^\top Y}{\mathbf{1}^\top\mathbf{1}-\mathbf{1}^\top X\,(X^\top X)^{-1} X^\top \mathbf{1}}}$

$\boxed{A=(X^\top X)^{-1}\left[X^\top Y-X^\top \mathbf{1}\, b\right]}$

Modelo matemático convencional

Esse problema, chamado de OLS (Ordinary Least Squares; Mínimos Quadrados Ordinários) otimiza o problema de regressão linear multivariada. A solução que derivamos aqui é correta e o resolve: se você usar as fórmulas apresentadas, vai chegar nos melhores pesos. No entanto, na literatura, é comum serem feitos alguns passos que modificam um pouco a cara do problema, que eu omiti para deixar a explicação mais simplificada e enxuta.

Como agora nós já estamos mais familiares com o problema, vou apresentar esse modelo mais “convencional”.

Primeiramente, ao invés de usarmos $A$ para os coeficientes lineares e $b$ para o viés, usamos simplesmente $\hat{\beta}$, definido por:

$\hat{\beta} = \begin{pmatrix}b \\ A\end{pmatrix}$

E, como agora nós temos apenas um vetor com todos os parâmetros, também precisamos de apenas um vetor com todos os inputs. Antes, tinhamos um $X = {x_1, x_2, \dots, x_n}$, e um vetor $\mathbf{1}$ de uns, que multiplicávamos pelo escalar $b$. Agora, está tudo em $X$:

$X_{completo} = \begin{pmatrix}1 & X \end{pmatrix}$

Assim, nossa predição fica:

$\hat{y} = \hat{\beta} X_{completo}$

E, como agora temos apenas um vetor de parâmetros (e não um vetor e um escalar), temos apenas uma fórmula que resolve o OLS:

$\boxed{\hat{\beta} = (X^\top X)^{-1}X^\top Y}$

E se eu quiser usar outra loss?

Se você quiser usar outra loss, o procedimento é exatamente o mesmo: calculamos o residual com essa nova loss, derivamos-o parcialmente em relação a $\hat{\beta}$, e zeramos a derivada. Simples assim.