similarity

Workshop: Learning similarity measures for music.

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:
    1. não negativa.
    2. identidade dos indiscerníveis.
    3. simetria.
    4. 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.
    1. Construa um multigrafo dirigido:
    2. vértices: pares de objetos
    3. arestas: distâncias relativas
    4. Remova ciclos de tamanho 2.
    5. 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.
    6. inicie sem arestas.
    7. adicione arestas aleatoriamente.
    8. descarte arestas que introduzem ciclos.
    9. 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:
    1. colete os julgamentos de similaridade.
    2. construa um grafo e filtre as arestas redundantes e inconsistentes.
    3. compute os kernels.
    4. 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).