Método para medir a 'similaridade' entre gramáticas da FSA?

10

Estou trabalhando com um algoritmo de correspondência de padrões que gera um autômato de estado finito acíclico que aceita uma sequência de texto especificada e todas as suas substrings. O algoritmo FSA está sendo executado em uma representação simbólica de um fluxo de música (por exemplo, dados MIDI). O fluxo de música foi pré-processado para dividir cada música em 'segmentos' não identificados. Um FSA é gerado para cada segmento de cada música: se eu tiver músicas, cada uma dividida em segmentos , terei FSAs separados.nyn⋅y

Eu gostaria de comparar o FSA de cada segmento com os outros FSAs do meu corpus. O objetivo final seria agrupar-se em um espaço de similaridade e criar 'classes' de segmentos de acordo com a semelhança entre as métricas de construção. Assim, são de particular interesse as gramáticas que cada FSA define (correspondendo aproximadamente a certos componentes do conteúdo musical no segmento). Existem técnicas que podem ser boas para comparar algo assim? A divergência de KL vem à mente (por exemplo, usando-a para comparar a distribuição sobre cadeias associadas a uma determinada FSA), embora possa haver técnicas melhores / mais eficientes?

Além disso, peça desculpas se essa pergunta for (1) trivialmente fácil ou (2) indicativa de algum mal-entendido mais profundo ou (3) respondida em outro lugar. Eu sou um verdadeiro idiota, pessoal!

formal-languages reference-request finite-automata giro
fonte
3
Você precisará nos dizer o que quer dizer com "semelhante". Você precisa selecionar a métrica; não existe uma métrica certa para todos os fins. Sem mais informações, não podemos dizer qual métrica usar. Sugiro editar a pergunta para explicar por que você deseja medir a similaridade, o que fará com os resultados da métrica de similaridade e que pesquisa você fez. Você pode começar analisando medidas de semelhanças entre as cadeias subjacentes, em vez de medir as semelhanças dos FSAs derivados dessas cadeias. Editar distância vem à mente.
DW
Existem muitas métricas de string ; o que funciona para você depende. (Nota: algumas das "métricas" da seqüência listadas nesse artigo não são na verdade métricas no sentido matemático.)
Raphael
As métricas de string são boas, mas não exatamente o que estou procurando. Em vez de comparar seqüências específicas entre si, eu gostaria de comparar o sistema de regras (as gramáticas formais / FSAs) que poderiam ter produzido essas seqüências. Reconheço que existem infinitas gramáticas que podem produzir qualquer sequência específica, por isso estou restringindo minha pesquisa a uma gramática (FSA) construída usando um conjunto específico de regras. Eu imagino que pode haver casos em que duas cordas individuais estão de acordo formalmente semelhante a uma determinada cadeia métrica, mas as gramáticas necessário para produzi-los são bastante diferentes
aleta
A partir da declaração do problema, cada FSA está aceitando uma string e todas as suas substrings. Fundamentalmente, esse FSA é caracterizado pela cadeia mais longa que aceita. Toda a sua estrutura deriva disso. Portanto, há pouco sentido em comparar a FSA em vez de comparar diretamente as strings das quais elas são construídas. Pode ser que sua técnica de construção da FSA enfatize alguns recursos que você considera importantes. Então, precisamos saber como eles podem ser para entender o que importa. Volta para: o que é semelhante, o que métrica. Como é, essa questão não faz sentido.
babou

Respostas:

1

você pode ter mais sorte de outro ângulo e investigar a similaridade de uma peça musical, existem pesquisadores estudando isso e, embora sua abordagem possa funcionar, há outras abordagens. existem grandes bancos de dados que analisam muitos elementos / critérios, como letras, gênero etc., por exemplo, projeto de genoma da música .

às vezes, quando há uma grande variedade de algoritmos, uma pesquisa pode ajudar. Aqui estão duas pesquisas sobre correspondência de gráficos.

vzn
fonte
0

Como os FSAs são gráficos direcionados, sua pergunta pode ser generalizada como "algoritmo para medir a similaridade entre gráficos direcionados". Uma pesquisa no Google por "algoritmo de similaridade de gráficos" fornece páginas e páginas de hits. Talvez um deles seja adequado para seus propósitos?

Uma vez que a diferença entre os FSAs e os dígrafos gerais são os rótulos das bordas ou símbolos de transição nos FSAs, você precisará modificar esses algoritmos para levar isso em consideração.

Mike Ounsworth
fonte
Um método como esse perderá algumas propriedades importantes. Por exemplo, você provavelmente deseja que diferentes representações do mesmo idioma tenham completa semelhança, mas a comparação dos gráficos pode reportar dois autômatos para o mesmo idioma como diferentes.
jmite