Parte 1 - Introdução e Motivação
- Apresentação dos participantes.
- Apresentação do Data & Knowledge Engineering
Group.
- Usuários não devem se adaptar ao software, mas sim o software deve se
adaptar ao usuário.
- Livro do fita: Adaptive Methods for User-Centered Organization of Music
Collections.
- Sistemas MIR típicos: interface de dados, recuperação de informações,
interface de usuário.
- Desafios para MIR: multiculturalismo, pluralidade de facetas, usuários
com diferentes necessidades e percepções diferentes.
- Exemplos: três gravações de Missão Impossível.
- Exemplo de conjunto de dados: beatles e facetas.
- Definições de sistemas adaptativos:
- se comporta diferente em contextos diferentes com a mesma entrada.
- a adaptação está relacionada com o objetivo.
- Sistema adaptável -> sistema adaptativo.
- Lógica de adaptação.
- Modelo contextual.
- Espectro da especificidade da similaridade musical:
- Fingerprinting (exact matches).
- Remixes/sampling (nearest neighbour).
- Audio/music semantic gap.
- Cover songs (nearest neighbour).
- Artista (bag of features).
- Gênero (bag of features).
- Espectro incluindo as tarefas dos profissionais, consumidores e indústria.
- Definição de medida de similaridade em um conjunto X (Ciência da Computação):
- s: X x X -> R+
- s(x,x) = s(y,y)
- s(x,y) = s(y,x)
- s(x,x) >= s(x,y)
- s(x,y) \in [0,1]
- s(x,y) = 1 sse x = y.
- Definição de métrica:
- Propriedades:
- não negativa.
- identidade dos indiscerníveis.
- simetria.
- desigualdade triangular.
- Observações:
- sem (2) se torna uma pseudométrica.
- sem (3) se torna uma quasimétrica.
- sem (4) se torna uma semimétrica.
- Divergência de Kullback-Leibler não é simétrica e nã satisfaz a
desigualdade triangular (premétrica).
- Compatibilidade de distância e similaridade.
- Transformação entre similaridade e distância.
- Shepard: s(x,y) = exp(-d(x,y))
- Alternativa: s(x,y) = 1/(1+d(x,y))
- Opcionalmente: scaling.
- Medidas de distância/similaridade comuns.
- Podem ser divididas pelo tipo de dados: vetor (mikowski, mahalanobis,
coseno), sequência (hamming, levenshtein), conjunto (jaccard),
distribuição (KL, earth mover).
- Distâncias de Minkowski.
- compara 2 vetores n-dimensionais x e y.
- dmink(x,y) := (\sum_{i=1}(x_i - y_i)p)^{1/p}
- Distância de Mahalanobis.
- Compara 2 vetores n-dimensionais x e y.
- dmahalanobis(x,y) := ||x-y||_W = \sqrt((x-y)T W(x-y))
- Distância do coseno.
- Mede o ângulo entre dois vetores n_dimensionais x e y.
- sim{cos}(x,y) := cos(x,y) = \sum{i=1}^n x_i y_i / ||x||.||y||
- Comumente utilizada em recuperação de texto.
- Se os vetores estiverem normalizados, pode ser substituída por um
produto escalar.
- Distância de Hamming.
- compara 2 sequências de tamanho igual.
- pode ser usada para vetores (discretos).
- comparação de cada entrada e soma dos diferentes.
- Distância de Levenshtein.
- compara duas sequências de tamanho possivelmente diferente,
transformando uma na outra através de operações de edição.
- operações permitidas: inserir, apagar, substituir.
- as operações podem ter custos diferentes.
- pode-se encontrar o mínimo através de programação dinâmica.
- Distância de Jaccard.
- compara 2 conjuntos A e B.
- d_{jaccard}(A,B) := 1 - ( |A inter B| / |A uniao B| )
- pode ser usada para comparar sequências de símbolos representados por
ngramas.
- Representando preferências de similaridade/distância.
- Afirmações absolutas (quantitativas):
- binária (x e y são / não são similares).
- quantitativa (a similaridade/distância entre x e y é 0.5)
- qual é a escala?
- pode não haver limitante superior.
- Afirmações relativas (qualitativas):
- x e y são mais/menos similares que u e v.
- x é mais similar/distante de y do que de z.
- é mais fácil de expressar.
- mais estável.
- ainda pode ser inconsistente.
- Lidando com inconsistências.
- Definição de ordem parcial (irreflexibilidade, antisimetria,
transitividade).
- Pode ser representada em um grafo dirigido acíclico.
- Construa um multigrafo dirigido:
- vértices: pares de objetos
- arestas: distâncias relativas
- Remova ciclos de tamanho 2.
- Construa um DAG. Encontrar a sub-árvore máxima é NP-completo, então
temos que utilizar um algoritmo aleatorizado e guloso para obter uma
aproximação.
- inicie sem arestas.
- adicione arestas aleatoriamente.
- descarte arestas que introduzem ciclos.
- Remova arestas redundantes.
Parte 2 - Aprendendo Modelos Lineares
- Modelos adaptáveis de similaridade.
- Objetos são descritos por características.
- Definição de Distância de faceta (facet distance):
- conjunto de características + medida de distância (não negatividade e
simetria são necessárias, desigualdade triangular é opcional).
- suposição: objetividade (cálculo a partir dos dados, sem
subjetividade).
- distância = soma ponderada de distâncias de faceta.
- pesos não negativos.
- adaptação direta (manual) é possível.
- obs: em geral, as pessoas não querem que o sistema tome decisões que
elas não gostariam, então é importante conhecer o sistema e ter o
controle do que acontece.
- Distâncias de faceta -> medida de distância -> distância agregada.
- Distâncias de faceta podem ser utilizadas como restrições na formulação
de um problema de otimização.
- ... podem também ser utilizadas como exemplos de treinamento para um
classificador linear.
- Abordagens:
- Abordagem: gradient descent (minimiza diretamente mas pode fica preso no
mínimo local).
- Abordagem: programação quadrática.
- Abordagem: SVM linear.
- classificador com maior margem (largest margin classifier). Ele escala
bem com relação ao número de restrições (pode inclusive ser utilizado
em real-time).
- Comparação de desempenho entre os modelos.
- Aplicações.
- Dutch song database: muitos pesquisadores
percorrem a Holanda pedindo para pessoas cantarem músicas populares. O
interesse deles é extrair uma representação simbólica e descobrir como as
músicas evoluíram (muitas são transmitidas de forma oral).
- Ranking adaptativo, baseado nos pesos das facetas.
- É possível mudar a estratégia de seleção de pesos das facetas
dependendo do caso.
- Análise de desempenho.
- The Beatles Explorer (com vídeo!).
- Simulação da interação com o usuário.
- Aplicação: MusicGalaxy.
- Gera uma visualização de uma coleção musical para explicação.
- Redução de dimensionalidade para visualização.
- Problemas:
- similares podem não aparecer na mesma região.
- não similares podem aparecer na mesma região.
- Forma de resolver: foco temporário na região de interesse.
- Foco primário e focos secundários.
- Utilização de tags.
Parte 3 - Aprendendo Distâncias de Mahalanobis
- Partial order embedding
- Definições:
- Ordem parcial.
- Decomposição Espectral.
- Matriz semi-definida positiva.
- Uma MSDP define uma função de distância de Mahalanobis.
- Objetivo: encontrar uma representação dos dados num espaço euclidiano
que seja consistente com as restrições.
- Utilização de variáveis de folga para viabilizar a violação das
restrições.
- O truque do Kernel (expressar a computação da distância pelo produto
interno de uma matriz, combinando informação sobre os pontos e a função
de mapeamento).
- Embedando um kernel.
- Embedando múltiplos kernels.
- Combinação sem pesos.
- Resumo:
- colete os julgamentos de similaridade.
- construa um grafo e filtre as arestas redundantes e inconsistentes.
- compute os kernels.
- Transforme os kernels em um espaço euclidiano, que esteja de acordo
com a percepção humana.
- Metric Learning for Ranking
- Dada uma consulta, queremos os melhores resultados primeiro e os piores
por último.
- SVM estruturais.
Parte 4 - Comparações experimentais
- Magnatagatune (magnatune + tag a tune + echonest).