dados (pontos nos espaço) tem dimensão m e passam a ser pontos num espaço de menos dimensões (k) m > k que capturam tudo/quase tudo do dado original
assume que dados “reais” sobre coisas “reais” estão organizados em sub-espaços (lineares ou não lineares).
Dados: uma matrix V de m colunas (atributos ou dimensões) e n linhas (número de dados)
V_{nm} \approx W_{nk} H_{km}
k é o numero novo (menor) de dimensões
W_{nk} é o “novos dados” - mesmo número de dados (n) e menos dimensões k.
H_{km} é o mecanismo de converter as dimensões velhas m para o numero novo.
cada coluna de H é um ponto no espaço original (de dimensão m) As k colunas de H pode ser pensado como k padrões ou pontos do espaço original que capturam a “essência” dos dados.
W H são os dados reconstruidos, depois de mapeados para as dimensões reduzidas e remapeados no espaço original.
as diferenças estão no \approx
mais formalmente
descubra W e H de forma que mimimize erro( V - W H) para
varias definições de erro
varias restrições no W (mas não necessariamente no H)
Também chamado de low rank (k) approximation
A solucão normalmente não é única (a nao ser que haja algumas restriçoes no W (ou no H)
Se W e H é uma solucão então \alpha W e 1/\alpha H também é.
em um caso há uma solução analitica (PCA)
alternating gradient descent (ou variações)
Em alguns casos, há uma solução analítica para o passo 2) e 5)
problema não é convexo e portanto os algoritmos vao encontrar minimos locais.
uma boa inicializacão é importante
https://en.wikipedia.org/wiki/Principal_component_analysis
visto na disciplina de algebra linear e também na de aprendizado supervisionado (como redução de dimensionalidade).
nao há restriçoes no W e H
V - W H é uma matriz do formato de V, onde dada entrada é o erro da matriz original para a reconstruida. Se a aproximação é boa, os numeros terão valores absolutos pequenos,
O erro é a norma de Frobenius de uma matrix que é a soma dos quadrados dos valores da matrix.
minimize \quad \sum_{ij} (V - WH)^2_{ij}
minimize \quad ||V - WH||_{fro}
ha 2 algoritmos principais
autovetores/autovalores da matriz de covariancia dos dados V
SVD da matriz dos dados https://en.wikipedia.org/wiki/Singular_value_decomposition
Em ambos casos:
X = U \Lambda V
U e V tem propriedades diferentes no caso de autovetores/autovalores (e pode nao existir) e de singular value decomposition
\Lambda é uma matriz diagonal (mas nao necessariamente quadrada no caso do SVD) dos autovalores/singular values, ordenadas decrescentemente
tunca as k primeiras colunas (os k maiores autovalores/SV ) \Lambda_k
W H = U \Lambda_k V
normalmente: W = U \Lambda e H = V
sparse PCA - tenta levar algumas das dimensões para 0 - projeta nas outras dimensões
independent PCA (?)
Factor analysis (= PCA?)
https://en.wikipedia.org/wiki/Non-negative_matrix_factorization
restrição: W \ge 0
normalmente H e V \ge 0 também.
a ideia é que os padrões de H sao aditivos -cada dado é uma combinação positiva dos padrões de H.
Por exemplos tópicos em texto
textos são sobre assuntos (tópicos): animais, finanças, esportes, etc
textos contem graus (positivos) de diferentes tópicos, e normalmente grau 0 da maiorias dos outros tópicos.
Nao existe grau negativo de um texto em relação a um tópico: mesmo um texto 100% contra vaquejada e touradas e rodeios é sobre animais e esportes! Um texto de diz que unicornios nao existem é sobre animais!
Por exemplo separação de fontes:
microfone capta todas as conversas numa sala.
diferente momentos há maior ou menor (ou 0) intensidade de cada conversa
nenhuma sinal captado tem um grau negativo de uma conversa em particular
NMF é um dos problemas onde há formas analíticas para os passos 2 e 5 (multiplicative update rule https://en.wikipedia.org/wiki/Non-negative_matrix_factorization)
cada texto é sobre poucos tópicos.
para cada linha de W, maioria das entradas deve ser 0
a maioria das entradas de W sao 0 (nao sao equivalentes)
Regularização L1
da disciplina de otimização, minimizar também a soma dos modulos de um vetor normalmente força que alguns/vários das entradas do vetor acaba sendo 0.
em oposição a regularização L2 (soma dos quadrados), que tende a baixar todos os valores sem necessariamente leva-los para 0
minimize \quad \sum_{ij} (V - WH)^2_{ij} + \alpha \sum_{ij} | W_ij|
minimize \quad ||V - WH||_{fro} + \alpha ||W||_{1}
python: https://scikit-learn.org/stable/modules/generated/sklearn.decomposition.NMF.html
R: http://renozao.github.io/NMF/master/index.html
dicionary learning: https://scikit-learn.org/stable/modules/generated/sklearn.decomposition.DictionaryLearning.html
cada linha de W deve somar 1
pode ser interpretado como uma probabilidade.
acho que é so normalizar as linhas de W apos cada computação de W_{i+1} (projected gradient descent)
sem restrição no H - pontos do espaço original
uma noção de clusterização probabilistica (tipo GMM)
pontos de H são os centroides
cada dado tem uma probabilidade de ligação para cada centroid (linhas do W)
eu acho que isso é equivalente a um GMM esférico com mesma matriz de covariância
uma formulação probabilistica de tópicos em texto
cada texto (linha de V) tem uma distribuição de probabilidades (linhas de W somam 1) para os tópicos.
a formulação original do LDA é baseada em modelos probabilisticos mas é possível que exista uma formulação baseada em fatoração de matrizes
ha outras medidas de erro para dados que se parecem com probabilidades (em vez da norma de Frobenius): KL divergence
R: https://cran.r-project.org/web/packages/topicmodels/index.html
Se cada linha de W é um 1 e os outros valores sao 0
clusterizaçao tradicional - cada dado é atribuido a apenas 1 cluster
H são os centros dos clusteres
W H voce esta substituindo cada dado pelo centro do seu cluster
(provavelmente) equivalente a k-means.
clusterizaçao multipla
cada dado pode pertencer a múltiplos clusteres
matriz V tem valores faltantes NA ou NaN
minimize \quad erro_{falt} (\tilde{V} - WH) onde erro_{falt} é o erro quadratico apenas nas entradas nao faltantes de V
\tilde{V} é uma imputação simples (NA -> 0 por exemplo)
ou
minimize \quad ||P \circ (\tilde{V} - WH)||_{fro}
P é uma matriz de pesos (neste caso 0/1) 0 para dados faltantes
\circ multiplicação de matrizes elementos por elementos.
nao estamos interessados em W ou H em separado, apenas na reconstrução W H que tem rank baixo e valores apropriados para os dados faltantes.
No caso de matrix completion normalmente há uma troca entre restricoes e objetivos de minimização.
X = WH
restrição: V_{ij} = X_{ij} para os dados nao faltantes
minimização: minimize rank(X)
troca a minimização de rank(x) -> nuclear norm(X) = ||X||_{*} = soma dos valores do SVD
dados faltantes numa coleta de dados “tradicional”
regiões corrompidas em imagens/som/video
sistemas de recomendação usuário x produto. As entradas que o usuário nao avaliou sao NA.
as entradas completadas com valor alto são as recomendações
collaborative filtering
assume-se que há ruido nas avaliaçoes e portanto nao mais queremos a restriçao V_{ij} = X_{ij}
queremos reduzir o erro de V_{ij} - X_{ij}
precisamos de novo usar o weighted NMF