Fatoração de matrizes

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

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

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

Observação: a fatoração de matrizes normalmente oferece uma representação mais compacta do que e aprenderemos a matriz completa. A matriz completa tem \(O(nm)\) entradas, enquanto a matrizes de embedding \(U, \ V\) têm \(O((n+m)d)\) entradas, onde a dimensão de embedding \(d\) geralmente é muito menor que \(m\) e \(n\). Como resultado, a fatoração de matrizes encontra uma estrutura latente em os 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 o vantagem é insignificante. No entanto, em sistemas de recomendação do mundo real, a fatoração de matrizes pode ser significativamente mais compacta do que o aprendizado a matriz completa.

Escolher a função objetiva

Uma função objetiva intuitiva é a distância ao quadrado. Para isso, minimizar 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.\]

Nesta função objetiva, você só soma sobre pares observados (i, j), ou seja, sobre valores diferentes de zero na matriz de feedback. No entanto, apenas somar sobre valores de um não é uma boa ideia. Uma matriz de todos os uma perda mínima e produzir um modelo que não faz recomendações eficazes e que generaliza mal.

Talvez seja possível tratar os valores não observados como zero e somar todo o entradas na matriz. Isso corresponde a minimizar Frobenius ao quadrado distância entre \(A\) e sua aproximação \(U V^T\):

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

É possível resolver esse problema quadrático Decomposição de valor singular (SVD, na sigla em inglês) da matriz. No entanto, O SVD também não é uma ótima solução porque, em aplicativos reais, matricial \(A\) pode ser muito esparsa. Por exemplo, pense em todos os vídeos em comparação com todos os vídeos que um usuário específico assistiu. A solução \(UV^T\) (que corresponde à aproximação do modelo) da matriz de entrada) provavelmente será próximo de zero, o que resulta desempenho de generalização.

Já a Fatoração de matriz ponderada decompõe o objetivo nas duas somas a seguir:

• Uma soma sobre as entradas observadas.
• Uma soma sobre 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. É muito importante ajustar esse hiperparâmetro.

Observação: em aplicações práticas, você também precisa ponderar os valores os pares com cuidado. Por exemplo, itens frequentes (por exemplo, extremamente vídeos populares do YouTube) ou consultas frequentes (por exemplo, usuários frequentes) podem dominar a função objetiva. Você pode corrigir esse efeito de treinamento de ponderação para considerar a frequência do item. Em outras palavras, substitua 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 das consultas i e item j.

Minimizar a função de objetivo

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

• Gradiente descendente estocástico (SGD) é um método genérico para minimizar funções de perda.

• O Menor quadrado alternado ponderado (WALS, na sigla em inglês) é especializado neste um objetivo específico.

O objetivo é quadrático em cada uma das duas matrizes U e V. No entanto, que o problema não é convexo conjuntamente. O WALS funciona com a inicialização os embeddings de forma aleatória e, em seguida, alternando entre:

• Corrigindo \(U\) e resolvendo para \(V\).
• Corrigindo \(V\) e resolvendo para \(U\).

Cada etapa pode ser resolvida exatamente (por meio da solução de um sistema linear) e pode ser distribuídos. Essa técnica certamente converge, porque cada etapa vai diminuir a perda.

SGD x WALS

O SGD e o WALS têm vantagens e desvantagens. Analise as informações abaixo para compará-los:

SGD

Muito flexível: pode usar outras perdas .

Pode ser carregado em paralelo.

Mais lenta: não converge tão rapidamente.

É mais difícil de lidar com entradas não observadas (é necessário usar amostragem negativa ou gravidade).

WALS

Depende apenas de quadrados de perda.

Pode ser carregado em paralelo.

Converge mais rápido que o SGD.

Mais fácil de lidar com entradas não observadas.