Aula 10: Sistemas de Recomendação: Fatoração de Matrizes (SVD e NMF)
Aprendizado Não Supervisionado
1 Revisão e Introdução
1.1 Que filme recomendar para esta pessoa?
Você abre um serviço de streaming e ele sugere um filme. Para fazer isso, o sistema sabe muito pouco sobre você: quais filmes você já avaliou e que nota deu a cada um. E sabe o mesmo sobre milhares de outras pessoas.
Podemos guardar tudo isso numa tabela \(R\in\mathbb{R}^{M\times N}\). Cada linha \(u\) é um usuário, cada coluna \(i\) é um filme, e \(r_{ui}\) é a nota que \(u\) deu a \(i\). A figura mostra um pedaço dessa tabela no MovieLens, a base que vocês usarão no trabalho final. O cinza é o que importa: são os filmes que aquela pessoa nunca avaliou.
Recomendar é tentar adivinhar o que está escrito nas células cinza. Se soubermos estimar a nota que você daria a um filme que ainda não viu, basta sugerir os filmes com as maiores estimativas.
O MovieLens completo tem 990.425 notas, de 0,5 a 5, dadas por 44.088 usuários a 15.603 filmes. Só 0,14% da tabela está preenchida, e o usuário mediano avaliou 8 filmes. Para que as contas caibam na aula, vamos ficar com os 2.000 usuários mais ativos e os 1.000 filmes mais avaliados. Nesse recorte, 14,1% da tabela está preenchida, cerca de cem vezes mais que na base completa. É um cenário bem favorável, e vale lembrar disso ao ler os resultados.
1.2 O que já vimos que pode ajudar
Essa tabela lembra duas coisas que já estudamos.
Na Aula 6, a PCA resumia uma tabela com poucos fatores: encontrava o subespaço que minimiza o erro de reconstrução, e a PPCA dava a versão probabilística, \(\mathbf{x}=\mathbf{W}\mathbf{z}+\boldsymbol\mu+\boldsymbol\epsilon\). Aqui também parece razoável que poucos fatores expliquem muita coisa, já que as pessoas não têm gostos totalmente independentes para cada filme. A diferença é que, na Aula 6, todos os atributos eram conhecidos.
Na Aula 9, trabalhamos com tabelas discretas e quase vazias. As regras de associação olhavam poucas variáveis por vez, e as redes Bayesianas nos ensinaram a desconfiar do que aparece nos dados. Uma ideia de lá vai voltar no fim da aula: condicionar num efeito comum, o colisor, cria dependência entre as causas. Toda nota que vemos existe porque alguém escolheu ver o filme e avaliá-lo.
1.3 Ideia central
Recomendação é parecida com a PCA da Aula 6, só que boa parte da tabela está escondida. Continuamos supondo que poucos fatores explicam os dados, agora os gostos das pessoas. O que precisa mudar é o objetivo, que passa a olhar apenas para as células conhecidas. No fim, teremos um espaço em que usuários e filmes convivem, e vamos querer saber o que esse espaço diz.
1.4 Roteiro
Vamos do mais simples ao mais completo, tentando responder a cinco perguntas:
- Baselines: até onde vão a média e a SVD com os buracos preenchidos?
- Modelo: como colocar pessoas e filmes no mesmo espaço e separar o gosto da generosidade de quem dá a nota?
- Treino: como ajustar esse modelo com SGD e com ALS?
- NMF: o que muda quando proibimos números negativos?
- Leitura e suposições: como interpretar o espaço aprendido, e o que estamos supondo sobre os dados?
2 Baselines
2.1 Primeiro, o mais simples
Antes de qualquer modelo elaborado, vale perguntar o que dá para fazer com quase nada. Para comparar as tentativas, separamos 80% das notas para treino, 10% para escolher hiperparâmetros e 10% para teste, e medimos a raiz do erro quadrático médio (RMSE) nas notas de teste. É um erro na mesma escala das estrelas.
Tentativa 1: dar a mesma nota para tudo. Prevemos sempre a média das notas de treino, \(\mu\). O erro de teste é 0,979, ou seja, erramos por volta de uma estrela. Qualquer método mais sofisticado precisa pelo menos superar esse número.
Tentativa 2: considerar quem dá a nota e qual é o filme. Há pessoas generosas e pessoas exigentes, e há filmes de que quase todo mundo gosta. Podemos somar à média um ajuste por usuário, \(b_u\), e um ajuste por filme, \(b_i\):
\[\hat r_{ui}=\mu+b_u+b_i.\]
Esses são os vieses, ou preditores de baseline. Com eles, o erro cai para 0,769. Como veremos, nenhum outro passo da aula reduz tanto o erro. No trabalho final, é esse o modelo que vocês precisam vencer primeiro.
2.2 Temos uma ferramenta da Aula 6: a SVD
Se a ideia é resumir uma tabela com poucos fatores, por que não usar o que já sabemos? Toda matriz real admite a decomposição em valores singulares,
\[R=U\Sigma V^T=\sum_{k=1}^r\sigma_k\mathbf{u}_k\mathbf{v}_k^T,\]
e cortar essa soma nos \(K\) maiores termos dá a melhor aproximação possível:
2.3 O que é cada pedaço de \(PQ^T\)?
Escrevemos essa aproximação como \(\hat R=PQ^T\), com \(P=U_K\Sigma_K^{1/2}\) e \(Q=V_K\Sigma_K^{1/2}\). Vale olhar o formato das matrizes, porque ele explica quase tudo.
Como \(\hat R\) tem uma linha por usuário e uma coluna por filme, e o produto herda as linhas do fator da esquerda e as colunas do fator da direita, \(P\) precisa ter uma linha por usuário e \(Q^T\), uma coluna por filme. A linha \(u\) de \(P\) é o vetor \(\mathbf{p}_u\). A coluna \(i\) de \(Q^T\), que é a linha \(i\) de \(Q\), é o vetor \(\mathbf{q}_i\).
E o \(K\)? É o tamanho que sobra no meio do produto: o número de colunas de \(P\), igual ao número de linhas de \(Q^T\). Somos nós que o escolhemos. Cada uma dessas \(K\) posições é um fator, e usuários e filmes têm um número para cada fator.
Pela regra do produto de matrizes, a célula \((u,i)\) só depende da linha \(u\) da esquerda e da coluna \(i\) da direita:
\[\hat r_{ui}=\sum_{k=1}^K P_{uk}\,(Q^T)_{ki}=\mathbf{p}_u^T\mathbf{q}_i.\]
Na figura, com números ilustrativos e \(K=3\), a conta é \(1{,}5\cdot2{,}0+0{,}5\cdot1{,}0+1{,}0\cdot0{,}5=4{,}0\). Fica claro também por que isso é um resumo: no nosso recorte, a tabela tem 2.000.000 células, e com \(K=\) 20 bastam \((M+N)K=\) 60.000 números para gerar todas elas.
2.4 A SVD é a PCA da Aula 6
A ligação com a Aula 6 é direta. Para uma matriz \(X\in\mathbb{R}^{n\times d}\) centrada, com \(X=U\Sigma V^T\), a covariância amostral é \(\frac1n X^TX=\frac1n V\Sigma U^TU\Sigma V^T=V\frac{\Sigma^2}{n}V^T\), usando \(U^TU=I\). Portanto, as colunas de \(V\) são as direções principais, com autovalores \(\sigma_k^2/n\). Aqui \(P\) faz o papel das coordenadas \(\mathbf{z}_n\), e \(Q\), o da matriz de carregamento \(\mathbf{W}\), a menos de como dividimos \(\Sigma\) entre os dois.
Também herdamos a invariância da PPCA: para qualquer \(G\) invertível, \((PG,\ QG^{-T})\) produz o mesmo \(PQ^T\). Os dados determinam o subespaço, mas os eixos ficam em aberto. Isso vai importar quando tentarmos dar nome aos eixos.
2.5 Tapando os buracos
O teorema supõe que conhecemos todas as entradas, e nós não conhecemos. A saída mais natural é preencher os buracos e seguir em frente. Mas preencher com quê?
Tentativa 3: preencher com zero. É o que acontece por padrão quando guardamos a tabela numa matriz esparsa. O erro de teste vai a 2,422, 2,5 vezes pior que prever a média. A nota real média nas células de teste é 3,41, e o modelo prevê em média 1,25.
O motivo fica claro quando escrevemos o que a SVD está minimizando:
\[\|R_0-PQ^T\|_F^2=\underbrace{\sum_{(u,i)\in\Omega}\left(r_{ui}-\mathbf{p}_u^T\mathbf{q}_i\right)^2}_{\text{notas reais}}+\underbrace{\sum_{(u,i)\notin\Omega}\left(0-\mathbf{p}_u^T\mathbf{q}_i\right)^2}_{\text{zeros inventados}},\]
em que \(\Omega\) é o conjunto das células com nota. A segunda soma tem cerca de 8 vezes mais termos que a primeira. O teorema continua valendo, mas o problema que ele resolve é reconstruir uma tabela em que quem não viu um filme lhe deu nota zero, pior que a pior nota da escala.
Tentativa 4: preencher com a média. Melhora bastante: 0,868. Já supera a média pura, mas ainda perde para os vieses, e a matriz, antes esparsa, fica densa, com custo de \(\mathcal{O}(MNK)\) por passagem.
Tentativa 5: preencher os buracos com a previsão dos vieses. Em vez de fatorar as notas, fatoramos o resíduo \(r_{ui}-\mu-b_u-b_i\). Nele, um buraco vale zero, o que significa “nada além do esperado”, uma hipótese bem mais razoável que “nota zero”. Na hora de prever, somamos os vieses de volta: \(\hat r_{ui}=\mu+b_u+b_i+\hat Y_{ui}\), em que \(\hat Y\) é a SVD truncada dos resíduos. O erro cai para 0,747, o melhor até aqui. Ainda assim, o método continua gastando esforço para reconstruir células que ninguém avaliou.
2.6 As cinco tentativas lado a lado
A figura reúne as cinco tentativas. Note que uma SVD ingênua erra mais que uma constante, e que os vieses, com uma fórmula de três termos, superam a SVD com a média.
2.7 O que ainda falta
Os vieses têm um defeito que o RMSE não mostra. Para um usuário fixo, a ordem dos filmes em \(\mu+b_u+b_i\) depende só de \(b_i\). O \(b_u\) desloca todas as previsões da pessoa pelo mesmo valor, sem alterar a ordem. Portanto, todo mundo recebe a mesma lista, retirados os filmes já vistos. No nosso recorte, ela começa com Planet Earth II, Blue Planet II, It’s Such a Beautiful Day, Parasite, The Jinx: The Life and Deaths of Robert Durst.
Esse modelo sabe que um filme é bem avaliado e que você dá notas altas, mas não sabe se você gosta de animação. Recomendar, de fato, é captar esse tipo de coisa. É o que falta: alguma estrutura no que sobra depois de tirar os vieses.
3 Intuição: Gostos Ocultos
3.1 Por que alguém gosta de um filme?
Raramente é pelo título ou pelo ano de lançamento. Um filme tem perseguições, é uma comédia leve, tem um roteiro complicado de ficção científica. E cada pessoa se importa mais com umas coisas que com outras.
Imagine que cada filme \(i\) tem um vetor \(\mathbf{q}_i\in\mathbb{R}^K\), em que a primeira coordenada mede quanto ele tem de ação, a segunda quanto tem de romance, e assim por diante. Cada usuário \(u\) tem um vetor \(\mathbf{p}_u\in\mathbb{R}^K\) que diz quanto ele aprecia cada uma dessas coisas. Uma forma simples de combinar os dois é o produto interno:
\[\mathbf{p}_u^T\mathbf{q}_i=\sum_{k=1}^K p_{uk}q_{ik}.\]
Se o filme tem muita ação e a pessoa adora ação, esse termo sobe a previsão. Se a pessoa detesta (\(p_{u1}<0\)), ele a derruba. É a estrutura que faltava: somando esse termo aos vieses, duas pessoas podem receber listas diferentes.
\[\hat r_{ui}=\mu+b_u+b_i+\mathbf{p}_u^T\mathbf{q}_i.\]
3.2 Ninguém nos deu esses vetores
Falamos em “quanto o filme tem de ação” para facilitar, mas o MovieLens não informa nada disso. Um usuário é só um índice \(u\), um filme é só outro índice \(i\), e o dado é a tripla “\(u\) deu a nota \(r_{ui}\) a \(i\)”.
Aí está uma diferença em relação à PCA. Lá, partimos de um vetor de atributos conhecido, \(\mathbf{x}_n\), e calculamos o código \(\mathbf{z}_n\). Aqui, o candidato natural a vetor de atributos seria a linha de \(R\), com as notas da pessoa para cada filme. Só que 86% desses valores não existem, mesmo no recorte favorável.
A fatoração faz o caminho inverso. \(\mathbf{p}_u\) e \(\mathbf{q}_i\) são parâmetros aprendidos, duas tabelas consultadas pelo índice, com todas as \(K\) coordenadas preenchidas. Daí saem três consequências:
- Não precisamos de atributos, basta o histórico de interações.
- Os eixos não vêm com nome. “Ação” é uma leitura que fazemos depois, quando faz sentido.
- Quem não tem histórico não tem vetor. Esse é o problema do cold start.
Aqui aparece nossa primeira suposição: a de que a tabela completa tem posto baixo, ou seja, poucos fatores bastam para explicar os gostos. Sem isso, as células conhecidas não diriam nada sobre as desconhecidas.
3.3 Como é esse espaço na prática?
Como os filmes viram pontos, podemos desenhá-los. A figura usa a Tentativa 5, a SVD do resíduo, e mostra os dois primeiros fatores. Ninguém informou gêneros, e mesmo assim os extremos fazem algum sentido: um eixo parece separar grandes franquias de filmes mais autorais, e o outro destaca os filmes recentes de super-heróis. Essa leitura é nossa, feita depois de olhar os nomes. Repare também na nuvem perto da origem. Voltaremos a ela no Bloco 5.
4 Bloco 1: Aprender Só com o que Foi Observado
4.1 Parar de inventar notas
As tentativas 3 a 5 têm o mesmo problema: todas ajustam valores que nós mesmos inventamos. A saída é simples de dizer. Se uma célula está vazia, ela não entra na conta.
Essa virada ficou conhecida durante o Netflix Prize (2006–2009), com o trabalho de Simon Funk (2006), e foi sistematizada por Koren, Bell & Volinsky (2009). Com \(\Omega\) o conjunto das células observadas, minimizamos
\[\mathcal{L}(P,Q)=\frac12\sum_{(u,i)\in\Omega}\left(r_{ui}-\mathbf{p}_u^T\mathbf{q}_i\right)^2+\frac\lambda2\sum_{u=1}^M\|\mathbf{p}_u\|^2+\frac\lambda2\sum_{i=1}^N\|\mathbf{q}_i\|^2.\]
Os termos com \(\lambda>0\) são necessários porque um usuário com poucas notas tem poucos dados para determinar \(K\) coordenadas. Sem esse freio, o modelo decora as notas que viu.
Com isso, perdemos a fórmula fechada: o teorema de Eckart-Young-Mirsky não se aplica a esse problema, e precisaremos de um algoritmo iterativo, assunto do Bloco 2.
4.2 Colocando os vieses de volta
Já vimos que os vieses explicam muita coisa, então faz sentido mantê-los e deixar os fatores cuidarem só do que sobra. O modelo completo é
\[\hat r_{ui}=\mu+b_u+b_i+\mathbf{p}_u^T\mathbf{q}_i,\]
em que \(\mu\) é a média global das notas observadas, \(b_u\) e \(b_i\) são os desvios do usuário e do filme, e \(\mathbf{p}_u^T\mathbf{q}_i\) é a interação. A perda fica
\[\mathcal{L}(P,Q,\mathbf{b}_u,\mathbf{b}_i)=\frac12\sum_{(u,i)\in\Omega}\left(r_{ui}-\hat r_{ui}\right)^2+\frac\lambda2\left(\sum_u b_u^2+\sum_i b_i^2+\sum_u\|\mathbf{p}_u\|^2+\sum_i\|\mathbf{q}_i\|^2\right).\]
4.3 O que estamos supondo
Escrever essa perda já nos compromete com três suposições, além do posto baixo:
- Interação aditiva e bilinear: os efeitos se somam, e o gosto entra por um produto interno. Não há lugar para contexto nem para a ordem em que os filmes foram vistos.
- Ruído Gaussiano com variância constante: é o que justifica a perda quadrática, embora as notas sejam discretas e limitadas.
- A falta não informa o valor: somar só em \(\Omega\) trata as células vazias como se o motivo de estarem vazias não dissesse nada sobre a nota. Já dá para desconfiar dessa, e voltaremos a ela no Bloco 5.
4.4 Pausa 1: Baseline e Dados Faltantes
DicaCom \(\mu = 3{,}5\), \(b_u = -0{,}6\) (Carlos, crítico) e \(b_i = +0{,}8\) (Interestelar), qual é a nota de baseline? E a nota final, se \(\mathbf{p}_u^T \mathbf{q}_i = +0{,}5\)?
Some os efeitos sistemáticos antes de considerar qualquer afinidade latente. O que cada termo diz sobre Carlos e sobre o filme?
DicaO Colapso da SVD e os Vieses
Julgue V ou F — a questão só conta se acertar os 4 itens:
- □ O Teorema de Eckart-Young-Mirsky garante que a SVD truncada fornece a melhor aproximação de posto \(K\) mesmo quando a matriz possui \(90\%\) de entradas não observadas preenchidas com NaN.
- □ Preencher as células vazias de uma matriz de recomendação com zero é equivalente a assumir que a ausência de avaliação representa insatisfação máxima do usuário com o item.
- □ O preditor de baseline \(\mu + b_u + b_i\) consegue capturar o fato de que um usuário generoso tende a dar notas altas mesmo para filmes medianos.
- □ A regularização \(L_2\) nos fatores latentes (\(\lambda \|\mathbf{p}_u\|^2\)) tem como objetivo principal forçar as coordenadas dos fatores a serem estritamente não-negativas.
5 Bloco 2: Como Treinar: SGD e ALS
5.1 Duas variáveis que se multiplicam
Temos uma perda, mas ela não é convexa, por causa do produto \(\mathbf{p}_u^T\mathbf{q}_i\). Um caso mínimo mostra isso. Com um usuário, um filme, \(K=1\) e sem regularização, a perda \((1-pq)^2\) vale 0 em \((1,1)\) e em \((-1,-1)\), mas vale 1 no ponto médio \((0,0)\).
Por outro lado, se fixarmos \(Q\), o que resta é quadrático em \(P\) e, com \(\lambda>0\), estritamente convexo. O mesmo vale trocando os papéis. Problemas assim são chamados de biconvexos, e cada um dos dois algoritmos clássicos explora essa estrutura de um jeito.
5.2 SGD: uma nota de cada vez (Funk-SVD)
O SGD percorre as notas observadas uma a uma e corrige o modelo um pouco a cada nota. Para cada \((u,i)\in\Omega\), calculamos o erro
\[e_{ui}=r_{ui}-\left(\mu+b_u+b_i+\mathbf{p}_u^T\mathbf{q}_i\right).\]
A perda dessa nota é \(\mathcal{L}_{ui}=\frac12 e_{ui}^2+\frac\lambda2\left(b_u^2+b_i^2+\|\mathbf{p}_u\|^2+\|\mathbf{q}_i\|^2\right)\), e seus gradientes são
\[\frac{\partial\mathcal{L}_{ui}}{\partial b_u}=-e_{ui}+\lambda b_u,\quad\frac{\partial\mathcal{L}_{ui}}{\partial b_i}=-e_{ui}+\lambda b_i,\quad\nabla_{\mathbf{p}_u}\mathcal{L}_{ui}=-e_{ui}\mathbf{q}_i+\lambda\mathbf{p}_u,\quad\nabla_{\mathbf{q}_i}\mathcal{L}_{ui}=-e_{ui}\mathbf{p}_u+\lambda\mathbf{q}_i.\]
Andando no sentido oposto, com passo \(\gamma\):
\[b_u\leftarrow b_u+\gamma(e_{ui}-\lambda b_u),\qquad b_i\leftarrow b_i+\gamma(e_{ui}-\lambda b_i),\] \[\mathbf{p}_u\leftarrow\mathbf{p}_u+\gamma(e_{ui}\mathbf{q}_i-\lambda\mathbf{p}_u),\qquad\mathbf{q}_i\leftarrow\mathbf{q}_i+\gamma(e_{ui}\mathbf{p}_u-\lambda\mathbf{q}_i).\]
Dá para ler a regra em voz alta: se a nota veio acima do previsto (\(e_{ui}>0\)), aproximamos o gosto do usuário do perfil do filme. Cada atualização custa \(\mathcal{O}(K)\), e uma passada completa custa \(\mathcal{O}(|\Omega|K)\). O custo depende só das notas conhecidas.
Um cuidado ao ajustar o \(\lambda\): aqui a penalidade é aplicada a cada nota, enquanto na perda global ela aparece uma vez por usuário e por filme. Por isso, o \(\lambda\) do SGD e o do ALS têm escalas diferentes e não dá para compará-los diretamente.
5.3 ALS: um fator de cada vez
Se fixar \(Q\) torna o problema convexo, por que não resolvê-lo exatamente? O ALS (Alternating Least Squares) alterna: congela \(Q\) e resolve para todos os \(\mathbf{p}_u\); congela \(P\) e resolve para todos os \(\mathbf{q}_i\); e repete.
Seja \(\mathcal{I}_u\) o conjunto de filmes avaliados por \(u\), e \(\tilde r_{ui}=r_{ui}-\mu-b_u-b_i\) o resíduo, com os vieses fixos neste passo.
Passo 1, os termos que dependem de \(\mathbf{p}_u\): \(\ \mathcal{L}_u=\frac12\sum_{i\in\mathcal{I}_u}\left(\tilde r_{ui}-\mathbf{q}_i^T\mathbf{p}_u\right)^2+\frac\lambda2\|\mathbf{p}_u\|^2\).
Passo 2, gradiente: \(\ \nabla_{\mathbf{p}_u}\mathcal{L}_u=-\sum_{i\in\mathcal{I}_u}\mathbf{q}_i\left(\tilde r_{ui}-\mathbf{q}_i^T\mathbf{p}_u\right)+\lambda\mathbf{p}_u\).
Passo 3, igualando a zero: \(\ \left(\sum_{i\in\mathcal{I}_u}\mathbf{q}_i\mathbf{q}_i^T+\lambda I_K\right)\mathbf{p}_u=\sum_{i\in\mathcal{I}_u}\tilde r_{ui}\mathbf{q}_i\).
Passo 4, a matriz é definida positiva (\(\lambda>0\)), logo invertível:
\[\mathbf{p}_u=\left(\sum_{i\in\mathcal{I}_u}\mathbf{q}_i\mathbf{q}_i^T+\lambda I_K\right)^{-1}\sum_{i\in\mathcal{I}_u}\left(r_{ui}-\mu-b_u-b_i\right)\mathbf{q}_i.\]
Olhando a fórmula: cada usuário é uma regressão Ridge, cujos atributos são os perfis dos filmes que ele viu. Do mesmo modo, para cada filme \(i\), com \(\mathcal{U}_i\) o conjunto de quem o avaliou,
\[\mathbf{q}_i=\left(\sum_{u\in\mathcal{U}_i}\mathbf{p}_u\mathbf{p}_u^T+\lambda I_K\right)^{-1}\sum_{u\in\mathcal{U}_i}\left(r_{ui}-\mu-b_u-b_i\right)\mathbf{p}_u.\]
Como o problema de um usuário não depende dos outros, dá para resolver todos em paralelo. É por isso que o ALS é a implementação usada em ferramentas distribuídas como o MLlib do Spark. Um filme sem nenhuma avaliação fica com \(\mathbf{q}_i=\mathbf{0}\), o que é o cold start escrito em forma de equação.
5.4 E na prática, quanto melhorou?
Agora podemos voltar à comparação das baselines, usando \(K=\) 20 e hiperparâmetros escolhidos na validação (\(\lambda=\) 20 no ALS e \(\lambda=0{,}05\) no SGD). A Funk-SVD chega a 0,728 e o ALS, a 0,733. Os dois superam tudo o que tínhamos antes, inclusive a SVD no resíduo (0,747).
Mas compare os tamanhos dos ganhos. Da média global aos vieses, o erro caiu de 0,979 para 0,769. Dos vieses aos fatores, foi de 0,769 para 0,728. O ganho dos fatores é real, porém bem menor. Lembre, no entanto, que é ele que permite listas diferentes para pessoas diferentes.
O painel da direita compara os algoritmos por passagem. O ALS estabiliza em poucas iterações, cada uma mais cara. O SGD precisa de mais épocas, e seu erro de validação ainda estava caindo quando paramos, na época 20. Uma diferença de 0,005 entre os dois não nos permite declarar um vencedor.
5.5 E se não houvesse \(\lambda\)?
Parar de inventar notas resolve um problema e abre outro. Com \(K=50\), temos 150.000 parâmetros para 225.605 notas de treino. Quase sem regularização (\(\lambda=0{,}01\)), o erro de treino cai para 0,284 e o de teste sobe para 1,661, pior que a média global. Com \(\lambda=\) 20, escolhido na validação, ficam em 0,647 e 0,732. No outro extremo, \(\lambda\to\infty\) leva os fatores a zero, e voltamos aos vieses.
Há também uma razão algébrica. No nosso recorte, o usuário menos ativo tem 55 notas de treino. Na base completa, o usuário mediano tem 8, menos notas que fatores em muitas configurações. Nesse caso, \(\sum_{i\in\mathcal{I}_u}\mathbf{q}_i\mathbf{q}_i^T\) não é invertível, e só \(\lambda>0\) deixa o problema bem definido.
5.6 Pausa 2: Otimização e Atualização
DicaCom \(\gamma = 0{,}05\), \(\lambda = 0{,}02\), \(\mathbf{p}_u = [0{,}8;\ 0{,}2]^T\), \(\mathbf{q}_i = [1{,}0;\ 0{,}5]^T\), \(r_{ui} = 5{,}0\) e baseline \(3{,}5\), quanto valem \(\hat{r}_{ui}\), \(e_{ui}\) e o novo \(\mathbf{p}_u\)?
Depois do cálculo, observe qual coordenada de \(\mathbf{p}_u\) cresce mais, e por quê.
DicaDinâmica de Otimização
Julgue V ou F — a questão só conta se acertar os 4 itens:
- □ A função de custo da fatoração de matrizes regularizada \(\mathcal{L}(P, Q)\) é globalmente convexa em relação a todas as variáveis simultaneamente.
- □ O algoritmo ALS resolve sistemas lineares exatos de forma alternada, garantindo que o valor da função de perda decresça (ou permaneça constante) a cada iteração.
- □ No algoritmo SGD de Funk, se a predição para um item for exatamente igual à nota real observada (\(e_{ui} = 0\)), os fatores latentes \(\mathbf{p}_u\) e \(\mathbf{q}_i\) não sofrem alteração alguma.
- □ Em sistemas de recomendação em larga escala, o ALS é preferido sobre o SGD quando o treinamento precisa ser distribuído em dezenas de máquinas via computação em memória (ex.: Spark).
6 Bloco 3: E se Proibirmos Números Negativos? (NMF)
6.1 O incômodo com os sinais
Volte ao mapa de filmes. Os eixos têm valores positivos e negativos, e isso dificulta a leitura. O que quer dizer um filme ter \(-0{,}3\) de um fator? Acontece o mesmo em dados bem mais visuais. Na PCA de imagens de rostos (as eigenfaces de Turk & Pentland, 1991), os componentes acrescentam luz em algumas regiões e tiram em outras. Nenhum deles sozinho parece um olho ou um nariz, porque a reconstrução depende de cancelamentos entre eles.
Pense em construir um rosto de duas maneiras:
- Massinha de modelar (PCA/SVD): começamos com um rosto médio, colocamos massa em um lugar e tiramos de outro até acertar. Cada passo isolado não representa nada de reconhecível.
- Blocos de Lego (NMF): só podemos empilhar peças. Se não dá para tirar, as peças precisam ser, elas mesmas, partes úteis: um bloco para os olhos, outro para o nariz, outro para a boca.
Muitos dados já são não negativos por natureza: pixels, contagens de palavras em documentos, espectrogramas, número de reproduções de uma música. Então é natural perguntar o que acontece quando impomos isso aos fatores.
6.2 A definição
A fatoração não negativa (NMF), popularizada por Lee & Seung (1999), aproxima uma matriz \(V\in\mathbb{R}_{\ge0}^{M\times N}\) por
\[V\approx WH,\qquad W\in\mathbb{R}_{\ge0}^{M\times K},\quad H\in\mathbb{R}_{\ge0}^{K\times N}.\]
Olhando coluna a coluna, cada dado é uma soma de peças, com pesos que não podem ser negativos:
\[\mathbf{v}_j\approx\sum_{k=1}^K H_{kj}\mathbf{w}_k.\]
Lee & Seung relatam, em imagens de rostos, componentes parecidos com olhos, sobrancelhas, narizes e bocas e, em textos, tópicos com vocabulários coerentes. Mas por que a restrição levaria a isso? Uma observação simples ajuda:
Sem subtração, um fator não pode “desfazer” o excesso de outro. Quando a matriz tem muitos zeros de verdade, reproduzi-los obriga cada fator a atuar só em parte das linhas e das colunas. Isso explica uma tendência, mas não garante que ela sempre apareça, como veremos nos dados.
6.3 Onde dá para ver: MNIST
Antes de voltar aos filmes, vejamos um caso em que os fatores podem ser literalmente enxergados: 5 mil dígitos do MNIST, com \(K=16\). Cada pixel é não negativo, e o fundo é zero de verdade.
As bases da NMF (em laranja) lembram traços e arcos, embora algumas ainda pareçam dígitos inteiros, como o 1 e o 7. As da PCA (em azul e vermelho) misturam regiões positivas e negativas. Em números, 81% dos pixels das bases da NMF são praticamente nulos, e 42% das cargas da PCA são negativas.
A restrição também limita o ajuste, e dá para dizer quanto. Como \(WH\) tem posto no máximo \(K\), Eckart-Young-Mirsky impede a NMF de superar a SVD em erro de reconstrução. O erro relativo é 0,541 na NMF e 0,491 na SVD sem centralização.
6.4 E nos filmes? Quem assiste ao quê
O MNIST mostrou partes bem visíveis, e gostaríamos de ver algo parecido nos filmes. Para isso, vale fazer outra pergunta. Até aqui, perguntamos quanto alguém gostaria de um filme. Podemos perguntar também o que as pessoas costumam assistir, ou seja, quais são os padrões de consumo, tenham elas gostado ou não.
Para responder a isso, basta guardar se houve interação:
\[v_{ui}=\begin{cases}1 & \text{se } u \text{ avaliou } i,\\ 0 & \text{caso contrário.}\end{cases}\]
Esse tipo de dado é chamado de feedback implícito (Hu, Koren & Volinsky, 2008), e muitos sistemas reais só têm isso, como cliques ou reproduções. Três coisas mudam em relação ao que fizemos até agora:
- A nota sai de cena. Dar 1 ou 5 estrelas vira o mesmo \(v_{ui}=1\). Passamos a falar de consumo, e não de gosto, e o RMSE das notas não se aplica. No Bloco 5 veremos uma métrica adequada, o Hit@10.
- Os fatores ficam mais fáceis de interpretar. Filmes assistidos pelas mesmas pessoas tendem a cair no mesmo fator, e o peso de um filme não precisa expressar ao mesmo tempo quem o viu e quanto gostou.
- Há novas suposições. Tratamos “avaliou” como aproximação de “assistiu”, e um zero significa só “não interagiu”. Pode ser que a pessoa não goste do filme, mas também pode ser que nunca tenha ouvido falar dele.
6.5 O que cada fator reúne
Cada linha da tabela é um fator da NMF com \(K=\) 12, e estão todos ali, do mais ao menos concentrado. O método não recebeu nenhum gênero. A coluna de gênero foi calculada depois, olhando os 20 filmes mais fortes de cada fator: mostramos o gênero mais comum entre eles e a fração dos 20 que o têm.
| Fator | Filmes mais fortes | Gênero mais comum | Dos 20 mais fortes, têm esse gênero |
|---|---|---|---|
| 1 | Neighbors, 22 Jump Street, Horrible Bosses 2 | Comédia | 100% |
| 2 | Jason Bourne, Mission: Impossible - Rogue Nation, Furious 7 | Ação | 95% |
| 3 | Sully, Hidden Figures, Lion | Drama | 95% |
| 4 | Thor: Ragnarok, Avengers: Infinity War - Part I, Guardians of the Galaxy 2 | Ação | 95% |
| 5 | Frances Ha, Blue Jasmine, Inside Llewyn Davis | Drama | 85% |
| 6 | Don’t Breathe, The Conjuring 2, It Follows | Terror | 80% |
| 7 | Captain Marvel, Avengers: Infinity War - Part II, Ant-Man and the Wasp | Ação | 80% |
| 8 | Finding Dory, Moana, Frozen | Animação | 80% |
| 9 | The Favourite, Lady Bird, Roma | Drama | 75% |
| 10 | Olympus Has Fallen, Transcendence, Non-Stop | Ação | 70% |
| 11 | Whiplash, Nightcrawler, Gone Girl | Drama | 65% |
| 12 | Coherence, Predestination, Upgrade | Suspense | 65% |
Repare que 4 fatores têm ação como gênero mais comum, e 4 têm drama. Se os fatores fossem simplesmente gêneros, bastaria um de cada. Eles parecem separar públicos: os filmes da Marvel ficam em fatores diferentes de Jason Bourne, e os dramas de grande bilheteria, em fatores diferentes dos mais autorais. Essa leitura é nossa, e os gêneros são só uma forma externa de conferi-la.
6.6 E se usássemos as notas?
Podemos aplicar a mesma NMF às notas, medindo o erro só em \(\Omega\), como na Funk-SVD, com a regularização escolhida na validação (NMF com máscara). É um problema legítimo, mas os fatores recebem outra tarefa: reproduzir o valor da nota.
Veja o que isso exige. A menor nota possível é 0,5 e a média é 3,42. Em toda célula observada, a soma \(\sum_k W_{uk}H_{ki}\) precisa chegar a esse nível, então um par observado nunca pode ter todos os fatores desligados. Além disso, como esse modelo não tem vieses, o nível geral das notas também precisa sair dos fatores. Na matriz binária é diferente: toda célula com zero, que são 86% delas, pede justamente que os fatores se desliguem, como os fundos do MNIST.
Para comparar os dois casos usando todos os fatores, olhamos três medidas:
- Fatores ativos por célula: quantos fatores respondem por pelo menos 5% da previsão, em média nas células observadas. Quanto menor, mais cada previsão se apoia em poucas peças.
- Concentração de gênero: o gênero mais comum nos 20 filmes mais fortes de cada fator, como na tabela anterior, em média sobre os fatores. Uma seleção aleatória de filmes serve de referência, e ela fica longe de zero porque alguns gêneros são muito frequentes por si só.
- Cargas praticamente nulas: a fração das entradas de \(H\) abaixo de 0,1% do maior valor da matriz. Quanto maior, mais filmes cada fator ignora.
| Dado fatorado | Menor valor a reproduzir | Fatores ativos por célula | Concentração de gênero | Cargas praticamente nulas |
|---|---|---|---|---|
| Binário (feedback implícito) | 0 | 3,0 de 12 | 82% | 58,1% |
| Notas com máscara | 0,5 | 7,6 de 12 | 63% | 0,2% |
| Referência: filmes aleatórios | — | — | 44% | — |
Com as notas, cada previsão usa mais fatores, e quase nenhuma carga é nula: os fatores se sobrepõem bem mais. Os gêneros ainda aparecem, com concentração acima da referência aleatória, mas abaixo da do dado binário. Ligar isso ao piso das notas e à Proposição é uma leitura nossa, apoiada nessas medidas. O ponto prático é que a positividade sozinha não produz fatores que ignoram parte do catálogo: para isso, ajudam os zeros que a matriz traz para o ajuste.
7 Bloco 4: Como Treinar a NMF
7.1 Qual erro minimizar?
Até agora medimos o erro ao quadrado, que é a escolha natural quando supomos ruído Gaussiano:
\[\mathcal{L}_{\text{Fro}}(W,H)=\frac12\|V-WH\|_F^2=\frac12\sum_{i,j}\left(v_{ij}-(WH)_{ij}\right)^2 \qquad \text{s.t.} \quad W,H \geq 0.\]
Mas muitos dados da NMF são contagens, como palavras em documentos ou reproduções de músicas. Para esses casos, costuma-se usar a divergência de Kullback-Leibler generalizada:
\[\mathcal{D}_{KL}(V\parallel WH)=\sum_{i,j}\left(v_{ij}\ln\frac{v_{ij}}{(WH)_{ij}}-v_{ij}+(WH)_{ij}\right).\]
Minimizá-la equivale a maximizar a log-verossimilhança de um modelo em que cada \(v_{ij}\) segue uma Poisson independente com média \((WH)_{ij}\) (ESL §14.6, eq. 14.73). Ou seja, escolher a perda é escolher uma suposição sobre como os dados foram gerados.
7.2 Como manter tudo positivo?
Com um gradiente comum, \(W\leftarrow W-\gamma\nabla_W\mathcal{L}\), um passo grande leva entradas para valores negativos. Poderíamos cortá-las em zero, mas Lee & Seung (2001) propuseram outra saída: escolher o passo de modo que o gradiente vire uma multiplicação. Usando \(\odot\) e \(\oslash\) para produto e divisão entrada a entrada:
Passo 1, gradiente em relação a \(H\): \(\ \nabla_H\mathcal{L}=W^TWH-W^TV\).
Passo 2, descida com passo por coordenada: \(\ H\leftarrow H-\boldsymbol\eta\odot\left(W^TWH-W^TV\right)\).
Passo 3, escolhendo \(\boldsymbol\eta=H\oslash\left(W^TWH\right)\): \(\ H\leftarrow H-H\oslash\left(W^TWH\right)\odot\left(W^TWH-W^TV\right)\).
Passo 4, simplificando: o termo \(H\) se cancela e sobra a regra multiplicativa. A de \(W\) sai por simetria:
\[H_{kj}\leftarrow H_{kj}\frac{(W^TV)_{kj}}{(W^TWH)_{kj}},\qquad W_{ik}\leftarrow W_{ik}\frac{(VH^T)_{ik}}{(WHH^T)_{ik}}.\]
Para a KL, as regras são:
\[H_{kj}\leftarrow H_{kj}\frac{\sum_i W_{ik}\,v_{ij}/(WH)_{ij}}{\sum_i W_{ik}},\qquad W_{ik}\leftarrow W_{ik}\frac{\sum_j H_{kj}\,v_{ij}/(WH)_{ij}}{\sum_j H_{kj}}.\]
Repare no que aconteceu. Cada entrada é multiplicada por uma razão de números não negativos, então não há como ficar negativa, e nenhuma projeção é necessária. Quando a reconstrução acerta, \(WH=V\), a razão vale 1 e nada muda. Lee & Seung também provam que a perda nunca aumenta sob essas regras. Um detalhe prático: uma entrada que chega a zero fica em zero para sempre, e por isso começamos com valores positivos.
7.3 A resposta não é única
Lembra da invariância por \(G\) na SVD? Ela também existe aqui, de forma mais restrita. Dada uma fatoração \(V=WH\) e uma matriz invertível \(A\),
\[V=(WA)(A^{-1}H)=\tilde W\tilde H,\]
e essa é outra NMF válida sempre que \(WA\ge0\) e \(A^{-1}H\ge0\). Se \(A\) só permuta e reescala os fatores, nada de importante muda. Mas se houver folga entre o cone gerado pelos dados e as fronteiras do ortante, existe uma infinidade de soluções realmente diferentes (Donoho & Stodden, 2004; ESL §14.6, p. 554).
Na prática, a solução pode depender da inicialização. Penalidades de esparsidade (\(L_1\)) sobre \(W\) ou \(H\) podem reduzir a ambiguidade, sem garantir unicidade em geral. Também não vale reaproveitar uma solução ao mudar \(K\): ao contrário da SVD, as soluções não são aninhadas.
Isso não nos diz quanto o problema pesa num caso concreto, então vale medir. No MovieLens implícito, duas inicializações aleatórias dão fatores pareados com cosseno médio de 0,99 (mínimo de 0,97). Aqui a ambiguidade foi pequena, mas isso é um resultado destes dados. No trabalho final, repitam o teste nos seus.
8 Bloco 5: O que Fazer com o Espaço Aprendido
8.1 Treinamos. E agora, como ler isso?
No trabalho final, vocês vão terminar o treino com duas tabelas de números e a vontade de dizer o que elas significam. Quatro cuidados ajudam:
- Desconfie de um eixo sozinho. Pela invariância por \(G\), o modelo determina as previsões \(\mathbf{p}_u^T\mathbf{q}_i\), e os eixos ficam em aberto. Olhar os extremos de um eixo sugere uma hipótese, que precisa ser conferida com algo que o modelo não viu, como os gêneros.
- A direção indica semelhança. O cosseno entre \(\mathbf{q}_i\) e \(\mathbf{q}_j\) mede se dois filmes são avaliados de modo parecido pelo mesmo público. A regularização \(L_2\) tende a equilibrar as escalas de \(P\) e \(Q\), sobrando principalmente a ambiguidade de rotação, à qual o cosseno é invariante (inferência nossa). Na tabela, Moana e Thor têm vizinhos coerentes. La La Land tem cossenos menores e vizinhos mais variados, porque a semelhança é de padrão de avaliação, e esse padrão nem sempre coincide com o gênero.
- A norma indica quanta informação há. Lembra da nuvem no centro do mapa? São, em boa parte, filmes com poucas notas, encolhidos pela regularização. A correlação de Spearman entre \(\|\mathbf{q}_i\|\) e o número de avaliações é 0,87. Norma grande não significa filme bom. A aprovação geral está em \(b_i\).
- Um usuário é um ponto, e dá para colocar um novo no mapa. Basta uma etapa do ALS, sem retreinar nada: \(\mathbf{p}=\left(\sum_i\mathbf{q}_i\mathbf{q}_i^T+\lambda I\right)^{-1}\sum_i(r_i-\mu-b_i)\mathbf{q}_i\), tomando \(b_u=0\).
Vamos testar esse último ponto com um usuário fictício que dá nota 5 a filmes populares de animação, separando duas perguntas: quais filmes mais sobem por causa da parte latente, \(\mathbf{q}_i^T\mathbf{p}\), e quais ficam no topo da lista final.
- Com 3 notas, a direção já parece certa: 100% dos que mais sobem são de animação. Mas o efeito é pequeno (\(\|\mathbf{p}\|=\) 0,23, subida máxima de 0,31, enquanto \(b_i\) tem desvio-padrão de 0,39), e 5 dos 5 primeiros coincidem com o ranking só por vieses. Esse é o cold start em números: com pouco histórico, \(\lambda\) segura o usuário perto da origem.
- Com 30 notas, \(\|\mathbf{p}\|\) sobe para 0,72, e o resultado surpreende. O que mais sobe já não é animação, e sim filmes de grande público de outros gêneros, e 4 de 5 ainda coincidem com os vieses. O fator aprendeu quem assiste ao quê junto. Quem vê muita animação popular também vê esses filmes, e isso é diferente de aprender um gênero.
Se todo mundo no seu trabalho estiver recebendo listas parecidas, a causa pode ser a escala de \(b_i\), mesmo com estrutura latente presente. Vale inspecionar a parte latente em separado.
| Filme | Vizinhos em \(\mathbf{q}_i\) (cosseno) |
|---|---|
| Moana | Coco (0,84), Finding Dory (0,79), Kung Fu Panda 3 (0,74), Inside Out (0,71) |
| Thor: Ragnarok | Avengers: Infinity War - Part I (0,87), Untitled Spider-Man Reboot (0,85), Avengers: Infinity War - Part II (0,77), Ant-Man and the Wasp (0,74) |
| La La Land | Cake (0,61), Louis C.K. 2017 (0,60), Before the Flood (0,58), White Bird in a Blizzard (0,52) |
| Notas | \(\|\mathbf{p}\|\) | Mais sobem com a parte latente (\(\mathbf{q}_i^T\mathbf{p}\)) | 5 primeiras recomendações | Iguais aos vieses |
|---|---|---|---|---|
| 3 | 0,23 | Frozen (+0,31), Moana (+0,27), Finding Dory (+0,23), Incredibles 2 (+0,20), Coco (+0,17) | Planet Earth II, Blue Planet II, It’s Such a Beautiful Day, The Jinx: The Life and Deaths of Robert Durst, Parasite | 5 de 5 |
| 30 | 0,72 | Fantastic Beasts and Where to Find Them (+0,38), Hidden Figures (+0,38), The Theory of Everything (+0,36), Hacksaw Ridge (+0,34), Wonder (+0,33) | Planet Earth II, Blue Planet II, It’s Such a Beautiful Day, Parasite, Grand Budapest Hotel, The | 4 de 5 |
8.2 Tudo o que supusemos até aqui
Ao longo da aula fomos acumulando suposições. Vale reuni-las, com um jeito de examinar cada uma no MovieLens.
Antes, uma observação sobre \(\lambda\). Se \(r_{ui}\) é Gaussiana em torno de \(\hat r_{ui}\) com variância \(\sigma^2\), e os fatores têm priori \(\mathcal{N}(\mathbf{0},\sigma_p^2 I)\), o log da posterior é \(-\frac{1}{2\sigma^2}\sum_{\Omega}e_{ui}^2-\frac{1}{2\sigma_p^2}\left(\sum_u\|\mathbf{p}_u\|^2+\sum_i\|\mathbf{q}_i\|^2\right)+\text{const}\). Multiplicando por \(-\sigma^2\), chegamos à perda da aula, com \(\lambda=\sigma^2/\sigma_p^2\) (PMF; Salakhutdinov & Mnih). Então a regularização também é uma suposição: a razão entre o ruído das notas e a variância que admitimos para os gostos. Ao contrário da PPCA, que integra \(\mathbf{z}\), aqui os dois fatores recebem só uma estimativa pontual.
| Suposição | Onde aparece | Quando pode falhar | Como examinar |
|---|---|---|---|
| Posto baixo | \(K\ll\min(M,N)\) | Gostos de nicho somem | Curva de validação por \(K\) |
| Interação bilinear e aditiva | \(\mu+b_u+b_i+\mathbf{p}_u^T\mathbf{q}_i\) | Contexto, ordem, sequência de consumo | Erro por grupo de usuários e filmes |
| Ruído Gaussiano homogêneo | Perda quadrática | Notas discretas e limitadas | Resíduo por nível de nota |
| A falta não informa o valor | Soma só em \(\Omega\) | Pessoas veem o que esperam gostar | Ver a seguir |
| Preferências estáveis | Um \(\mathbf{p}_u\) por usuário | Gostos e catálogo mudam | Partição temporal; Aula 11 |
| Zero = não interagiu (NMF implícita) | \(v_{ui}=0\) | Ausência não é desinteresse | Comparar com notas explícitas |
8.3 Por que aquela célula está vazia?
Esta é a suposição mais difícil de examinar. Pense em como você escolhe filmes: em geral, assiste ao que espera gostar. Quando isso acontece, a falta depende do valor que está faltando, o que é chamado de MNAR (missing not at random; Marlin et al., 2007).
A Aula 9 ajuda a enxergar a estrutura. Gosto e popularidade influenciam o evento “avaliou”, que é um colisor, e todo o nosso dado está condicionado a “avaliou = 1”. O grafo é uma ilustração nossa, e não um modelo estimado.
No MovieLens, filmes mais avaliados têm nota média maior (Spearman de 0,29). Isso é compatível com a seleção, mas filmes bons também atraem público, e sem as notas das células vazias os dados não têm como separar as duas explicações. Por isso usamos uma simulação em que todas as notas são conhecidas (800 usuários, 400 itens, posto 5, cerca de 15% observados). Quando a falta depende da nota, o erro nas notas retidas subestima o erro nas células nunca vistas, que são justamente as que queremos preencher. E coletar mais dados do mesmo jeito não corrige isso.
Portanto, os RMSE desta aula, e os do seu trabalho final, medem o desempenho nas células observadas.
| Simulação: mecanismo de falta | Média real | Média observada | RMSE nas notas retidas | RMSE nas nunca observadas |
|---|---|---|---|---|
| Sorteio uniforme | 3,00 | 3,00 | 0,33 | 0,33 |
| Depende da nota | 3,00 | 3,58 | 0,40 | 0,55 |
8.4 RMSE baixo não garante boa lista
Até aqui medimos o erro da nota, mas o que a pessoa vê é uma lista. Uma métrica de lista é o Hit@10: recomendamos a cada usuário os 10 filmes com maior pontuação, entre os que ele ainda não avaliou no treino nem na validação, e contamos a fração de usuários com pelo menos um filme de teste com nota 4 ou mais nessa lista. Na figura, os modelos estão na ordem do RMSE, com hiperparâmetros escolhidos para o RMSE e \(K=\) 20.
A ordem quase se inverte. A SVD com zeros, o pior RMSE da aula, dá a melhor lista. A Funk-SVD, o melhor RMSE, fica bem abaixo de simplesmente recomendar o que é popular. E veja a NMF nas notas: com RMSE quase igual ao da Funk-SVD (0,731 contra 0,728), seu Hit@10 é 50%, contra 22%. Esse número também é sensível à regularização: variando \(\lambda\), vai de 20% a 60%.
Uma explicação provável é que prever a nota e ordenar o catálogo são tarefas diferentes. Quem treina só em \(\Omega\) nunca aprende quais filmes a pessoa chegaria a ver, e um filme bem avaliado por poucos pode ir ao topo. Os zeros ensinam justamente isso, como vimos com o dado binário: a NMF binária, que nem usa notas, também vai bem. Resultado parecido aparece em Cremonesi, Koren & Turrin (2010).
Isso não faz da SVD com zeros o melhor recomendador. O teste só contém filmes que as pessoas escolheram avaliar, a mesma seleção da seção anterior, e isso favorece quem aprende quem assiste ao quê. As duas métricas respondem a perguntas diferentes, então o trabalho final deve reportar as duas, vencer primeiro os vieses e a popularidade, e repetir com outras sementes e outros \(K\).
9 Fechamento e Ponte para a Aula 11
9.1 Retomando as 5 perguntas
- Baselines: a média já dá uma referência, e os vieses trazem o maior ganho da aula, mas dão a mesma lista para todos. Preencher os buracos para usar a SVD resolve o problema errado: com zeros, ficamos 2,5 vezes pior que a média.
- Modelo: somamos aos vieses um produto interno entre o vetor do usuário e o do filme, \(\mu+b_u+b_i+\mathbf{p}_u^T\mathbf{q}_i\), e ajustamos só nas células observadas, com regularização \(L_2\).
- Treino: a perda é biconvexa. O SGD corrige uma nota por vez, a \(\mathcal{O}(|\Omega|K)\) por passada. O ALS resolve uma regressão Ridge por usuário e por filme, fácil de paralelizar. No MovieLens, os dois ficaram praticamente juntos.
- NMF: sem negativos não há cancelamento. Com zeros reais, como no MNIST e no feedback implícito, os fatores tendem a virar partes. Com notas e máscara, os fatores se sobrepõem bem mais, e o erro de reconstrução nunca fica abaixo do da SVD.
- Leitura e suposições: desconfie de um eixo sozinho, leia a direção como semelhança de avaliação e a norma como quantidade de informação. Os modelos supõem posto baixo, interação bilinear, ruído Gaussiano, falta ignorável e gostos estáveis, e os RMSE valem para as células observadas.
9.1.1 Os métodos lado a lado
| SVD clássica | Funk-SVD | NMF | |
|---|---|---|---|
| Entrada | Matriz completa | Matriz com células faltantes | \(V\ge0\), densa ou esparsa |
| O que restringe os fatores | Ortogonalidade (\(U^TU=I\)) | Regularização \(L_2\) | Não negatividade |
| Como ler as bases | Eixos de variância máxima | Afinidades, a conferir | Partes ou tópicos, quando há zeros reais |
| Há cancelamento? | Sim | Sim | Não |
| Como treinar | Decomposição espectral, Lanczos | SGD, ALS | Regras multiplicativas, HALS |
| Solução | Única a menos de sinal (com \(\sigma_k\) distintos) | Problema não convexo, mínimos locais | Em geral não única |
9.1.2 O que fica em aberto
- Cold start: sem histórico, a fatoração não tem o que dizer. Na prática, é combinada com atributos de usuários e filmes.
- Avaliação offline: a seleção afeta toda métrica histórica, e os dados de um sistema em produção dependem das recomendações que ele próprio fez.
- Matrix completion: em que condições as notas observadas determinam a matriz? Há resultados teóricos (Candès & Recht, 2009), com hipóteses sobre posto e amostragem que os dados reais raramente garantem.
9.1.3 Ponte para a Aula 11
Tudo aqui supôs que os gostos ficam parados. Na prática, surgem novos públicos, a moda muda, e os dados de hoje deixam de se parecer com os dados do treino. Como perceber isso, de forma estatisticamente justificada, sem esperar por novos rótulos?
Na Aula 11, veremos testes de duas amostras em alta dimensão e a Maximum Mean Discrepancy (MMD), usada para detectar data drift e domain shift.