Relatório 2 – Biochaves
Luiz Miranda Cavalcante Neto
Previously, on Relatório (Recapitulando): No relatório anterior, descrevi o que pretendia fazer e como pretendia fazer. Lá estão os links para os códigos implementados até agora e uma introdução de como modelei os artistas. A leitura é boa, vale a pena dar uma olhada lá para mais informações.
Relembrando nossos (ou só meus mesmo) problemas e dando um jeito neles
Como já foi dito, dois dos três passos para o sucesso foram dados no decorrer deste trabalho. Foram eles:
1 – Extrair os acordes de muitos artistas presentes no cifraclub;
2 – Modelar cada artista com uma cadeia de Markov (o porquê disso foi descrito no relatório anterior, mas tenho minhas dúvidas que esse caminho seja o ideal);
O terceiro passo, descrito como: “Com o modelo de cada artista, vou analisar seus parâmetros de modo a conseguir agrupar os músicos em grupos (clusterizar)” tem um problema inerente a como o modelo de cada artista foi gerado.
Veja só, cada artista é representado como uma tabela de transição entre uma sequência de N acordes e o acorde que vem após essa sequência. Esse N é dado pela ordem da cadeia de Markov. O tipo de representação pode ser visto na literatura como “N-gram representation” (ver [1] e [2]).
A pergunta é: Como raios eu vou clusterizar matrizes enormes?
A resposta é: Reduzindo as dimensões delas. Mas como?
Reduzindo dimensões
O ser humano tem uma limitação enorme: ser apenas tridimensional. Uma imagem digital, no entanto, tem centenas de dimensões. Eita! Como assim centenas de dimensões? Uma imagem não tem apenas altura e largura? É até menos do que nosso mundo 3D! (Isso em negrito, é você, leitor, querendo me bater já. Calma que eu explico). É isso mesmo, você não está errado. Maaaaas…. Ao olhar para uma imagem digital como uma matriz de pixels (que é o que ela realmente é) percebemos que se quisermos agrupar várias imagens parecidas e representar cada uma delas em um gráfico, não conseguimos fazer isso diretamente, temos que encontrar uma forma de reduzir suas dimensões.
Como fazer isso? De várias formas. Um exemplo para imagens é extrair certas características dessa imagem (como: cor média, brilho e formas geométricas) e usar essas características como novas dimensões que irão representar essas imagens. Na verdade, extrair características que podem representar um sinal multidimensional é a essência das técnicas de redução de dimensão. Considere uma rede neural treinada para dizer se em uma imagem há uma pessoa ou um cachorro. Para fazer isso, a rede converte uma imagem de algumas centenas de pixels (multidimensional) em apenas duas possíveis posições: cachorro ou pessoa. Esse valor final pode ser representado com uma simples dimensão.
(Disclaimer: Redes neurais diferentes trabalham diferente, nem todo sistema é implementado igual, esse exemplo ilustrativo saiu da minha cabeça para mostrar como a redução de dimensões é útil, ao persistirem os sintomas um médico deverá ser consultado)
Vamos ver agora outras formas de reduzir dimensões, essas mais formais e matemáticas.
Single Value Decomposition (SVD)
Considere que temos uma matriz de dados em que cada linha representa uma amostra e cada coluna representa uma característica dessa amostra. Uma matriz exemplo pode ser vista na Figura 1.
Figura 1. Meu gatinho Romeo. Cada linha da imagem representa uma amostra dela e cada coluna representa a escala de cinza na característica da imagem.
A teoria do SVD ([3] é só uma porta de entrada para o assunto) diz que toda matriz pode ser decomposta em três outras matrizes U, S e VT da seguinte forma:
A = U*S*VT
sendo:
A, uma matriz MxN que será decomposta;
U, uma matriz MxM sendo que cada coluna dela corresponde a um vetor característico de A;
S, uma matriz “diagonal” MxN com os pesos de cada vetor característico na ordem decrescente;
VT, uma matriz NxN sendo cada linha um vetor característico de A
Se isso lembra a você de autovalores e autovetores não é coincidência. Este teorema é parte geral da teoria de autovalores e autovetores. Tanto é que U são os autovetores de AT*A, e VT são os autovetores de A*AT. Tem mais coisa para aprender sobre redução de dimensão e álgebra linear, mas fica para outros relatórios.
Mas como esse teorema vai reduzir as dimensões de Romeo? Como foi dito, a matriz S representa a “força” de cada vetor característico. Se tentarmos representar Romeo apenas com os vetores com maior força talvez possamos ainda ver o gatinho. Vamos testar, as Figuras 2a, 2b, 2c e 2d ilustram o teste realizado. Primeiro tentamos representar o gato apenas com o vetor mais forte, não ficou tão bom. Depois, com os 5 mais fortes, já da para ver os contornos da imagem original. Com os 15 mais fortes já é possível ver um gato. E por último, com os 25 vetores mais fortes vemos o gatinho bonitinho.
Figura 2. Reconstrução da imagem do gato usando: a) apenas o vetor mais forte; b) os 5 vetores mais fortes; c) os 15 vetores mais fortes; d) os 25 vetores mais fortes
O que quero dizer com os vetores mais fortes? U e V estão ordenados da mesma forma que S. Então se quisermos usar apenas o vetor mais forte, iremos reconstruir o gato usando U*S*VT só que usando apenas a primeira coluna de U, o primeiro elemento de S e a primeira linha de V. Já se quiséssemos os 5 mais fortes usariamos as 5 primeiras colunas de U, os 5 primeiros elementos de S e as 5 primeiras linhas de V, e por aí vai.
Como isso se aplica a meu trabalho? A princípio eu apenas estudei métodos de reduzir dimensões. Além do SVD existe também o PCA, que é bastante parecido. A idéia é aplicar esses métodos nas matrizes de transição dos artistas e usar as matrizes decompostas e os vetores mais fortes para representar os artistas em um gráfico.
PS: Estudei bastante o word2vec também, não cheguei a implementar o danado, mas do jeito que os artistas estão modelados ele não é diretamente aplicável aos modelos. Tem uma aula de Stanford com o professor Richard Socher muito boa que explica detalhadamente o word2vec, vale a pena assistir ela, segue o link aqui : https://www.youtube.com/watch?v=ERibwqs9p38&t=1374s
Referências
[1] https://en.wikipedia.org/wiki/N-gram ;
[2] Cavnar, William B., and John M. Trenkle. “N-gram-based text categorization.” Ann arbor mi 48113.2 (1994): 161-175. (disponível aqui: https://goo.gl/9BRKP4 );
[3] https://en.wikipedia.org/wiki/Singular-value_decomposition
Possui graduação em Engenharia Elétrica com habilitação em Eletrônica pela Universidade Federal de Sergipe (2014) e mestrado em Engenharia Elétrica pela Universidade Federal de Sergipe (2017). Foi professor voluntário da Universidade Federal de Sergipe no período de 2015/1 lecionando a disciplina de Circuitos Digitais. É Professor substituto de Ensino Básico, Técnico, Tecnológico e Superior do Instituto Federal de Sergipe no Campus Lagarto (IFS-Lagarto). Tem experiência na área de Engenharia Elétrica, com ênfase em Robótica e Reconhecimento de Padrões.
-
Luiz Miranda Cavalcante Netohttps://www.biochaves.website/author/luiz-miranda/
-
Luiz Miranda Cavalcante Netohttps://www.biochaves.website/author/luiz-miranda/
-
Luiz Miranda Cavalcante Netohttps://www.biochaves.website/author/luiz-miranda/
-
Luiz Miranda Cavalcante Netohttps://www.biochaves.website/author/luiz-miranda/
Português do Brasil 
English (UK)