Fatoração de matrizes

A fatoração de matriz é um modelo de embedding simples. Considerando a matriz de feedback A \(\in R^{m \times n}\), em que \(m\) é o número de usuários (ou consultas) e \(n\) é o número de itens, o modelo aprende:

• Uma matriz de incorporação de usuários \(U \in \mathbb R^{m \times d}\), em que a linha i é a incorporação para o usuário i.
• Uma matriz de incorporação de itens \(V \in \mathbb R^{n \times d}\), em que a linha j é a incorporação do item j.

Os embeddings são aprendidos de modo que o produto \(U V^T\) seja uma boa aproximação da matriz de feedback A. Observe que a \((i, j)\) entrada de \(U . V^T\) é simplesmente o produto de ponto \(\langle U_i, V_j\rangle\) dos embeddings de usuário \(i\) e item \(j\), que você quer aproximar perto de \(A_{i, j}\).

Observação: a fatoração de matriz normalmente oferece uma representação mais compacta do que o aprendizado da matriz completa. A matriz completa tem \(O(nm)\) entradas, enquanto as matrizes de embedding \(U, \ V\) têm \(O((n+m)d)\) entradas, em que a dimensão de incorporação \(d\) costuma ser muito menor que \(m\)e \(n\). Como resultado, a fatoração de matriz encontra a estrutura latente nos dados, supondo que as observações estejam próximas de um subespaço de baixa dimensão. No exemplo anterior, os valores de n, m e d são tão baixos que a vantagem é insignificante. Em sistemas de recomendação reais, no entanto, a fatoração de matriz pode ser significativamente mais compacta do que o aprendizado da matriz completa.

Como escolher a função do objetivo

Uma função de objetivo intuitiva é a distância ao quadrado. Para fazer isso, minimize a soma dos erros quadráticos em todos os pares de entradas observadas:

\[\min_{U \in \mathbb R^{m \times d},\ V \in \mathbb R^{n \times d}} \sum_{(i, j) \in \text{obs}} (A_{ij} - \langle U_{i}, V_{j} \rangle)^2.\]

Nessa função de objetivo, você apenas soma os pares observados (i, j), ou seja, os valores diferentes de zero na matriz de feedback. No entanto, apenas a soma de valores de um não é uma boa ideia. Uma matriz de todos eles terá uma perda mínima e produzirá um modelo que não pode fazer recomendações eficazes e que generalize mal.

Talvez você possa tratar os valores não observados como zero e somar todas as entradas na matriz. Isso corresponde a minimizar a distância quadrada de Frobenius entre \(A\) e a aproximação dela \(U V^T\):

\[\min_{U \in \mathbb R^{m \times d},\ V \in \mathbb R^{n \times d}} \|A - U V^T\|_F^2.\]

Esse problema quadrático pode ser resolvido por meio de Singular Value Decomposition (SVD) da matriz. No entanto, o SVG não é uma ótima solução, porque, em aplicativos reais, a matriz \(A\) pode ser muito esparsa. Por exemplo, pense em todos os vídeos no YouTube em comparação com todos os vídeos que um usuário específico visualizou. A solução \(UV^T\) (que corresponde à aproximação do modelo da matriz de entrada) provavelmente será zero, levando a um baixo desempenho de generalização.

Por outro lado, a fatoração de matriz ponderada decompõe o objetivo nas duas somas a seguir:

• Uma soma das entradas observadas.
• Uma soma das entradas não observadas (tratadas como zeros).

\[\min_{U \in \mathbb R^{m \times d},\ V \in \mathbb R^{n \times d}} \sum_{(i, j) \in \text{obs}} (A_{ij} - \langle U_{i}, V_{j} \rangle)^2 + w_0 \sum_{(i, j) \not \in \text{obs}} (\langle U_i, V_j\rangle)^2.\]

Aqui, \(w_0\) é um hiperparâmetro que pondera os dois termos para que o objetivo não seja dominado por um ou outro. O ajuste desse hiperparâmetro é muito importante.

Observação: em aplicativos práticos, você também precisa ponderar os pares observados com cuidado. Por exemplo, itens frequentes (por exemplo, vídeos extremamente populares do YouTube) ou consultas frequentes (por exemplo, usuários pesados) podem dominar a função de objetivo. É possível corrigir esse efeito ponderando exemplos de treinamento para considerar a frequência do item. Em outras palavras, é possível substituir a função de objetivo por:

\[\sum_{(i, j) \in \text{obs}} w_{i, j} (A_{i, j} - \langle U_i, V_j \rangle)^2 + w_0 \sum_{i, j \not \in \text{obs}} \langle U_i, V_j \rangle^2\]

em que \(w_{i, j}\) é uma função da frequência da consulta i e do item j.

Como minimizar a função do objetivo

Algoritmos comuns para minimizar a função de objetivo incluem:

• O gradiente descendente estocástico (SGD, na sigla em inglês) é um método genérico para minimizar as funções de perda.

• O formato de menos quadrados alternados (WALS, na sigla em inglês) é especializado nesse objetivo específico.

O objetivo é quadrático em cada uma das duas matrizes U e V. Observe, entretanto, que o problema não é convexo em conjunto. O WALS funciona inicializando aleatoriamente os embeddings e alternando entre:

• Correções \(U\) e soluções de \(V\).
• Correções \(V\) e soluções de \(U\).

Cada estágio pode ser resolvido exatamente (por meio da solução de um sistema linear) e pode ser distribuído. Essa técnica garante a convergência, porque cada etapa tem a garantia de diminuir a perda.

SGD x WALS

SGD e WALS têm vantagens e desvantagens. Leia as informações abaixo para ver uma comparação:

SGD

Muito flexível: pode usar outras funções de perda.

Pode ser carregada em paralelo.

Mais lento: não converge com tanta rapidez.

Mais difícil para lidar com as entradas não observadas (precisa usar amostragem negativa ou gravidade).

AGUARDAR

Confie apenas nos quadrados de perda.

Pode ser carregada em paralelo.

Converge mais rápido do que SGD.

Maior facilidade para processar entradas não observadas.