Methode zur Messung der Ähnlichkeit zwischen FSA-Grammatiken?

10

Ich arbeite mit einem Pattern-Matching-Algorithmus, der einen azyklischen Finite-State-Automaten generiert, der eine bestimmte Textzeichenfolge und alle ihre Teilzeichenfolgen akzeptiert. Der FSA-Algorithmus wird auf einer symbolischen Darstellung eines Musikstroms (z. B. MIDI-Daten) ausgeführt. Der Musikstrom wurde vorverarbeitet, um jedes Lied in unbeschriftete "Segmente" zu unterteilen. Für jedes Segment in jedem Song wird eine FSA generiert: Wenn ich Songs habe, die jeweils in y Segmente unterteilt sind, habe ich n ⋅ y separate FSAs.nyn⋅y

Ich möchte die FSA jedes Segments mit den anderen FSAs in meinem Korpus vergleichen. Das ultimative Ziel wäre es, Clustering innerhalb eines Ähnlichkeitsraums durchzuführen und "Klassen" von Segmenten zu erstellen, je nachdem, wie ähnlich ihre Konstruktionsmetriken sind. Von besonderem Interesse sind daher die Grammatiken, die jede FSA definiert (die ungefähr bestimmten Komponenten des Musikinhalts in dem Segment entsprechen). Gibt es Techniken, mit denen man so etwas vergleichen kann? KL-Divergenz kommt in den Sinn (z. B. Vergleichen Sie die Verteilung über Zeichenfolgen, die mit einer bestimmten FSA verbunden sind), obwohl es möglicherweise bessere / effizientere Techniken gibt?

Wir entschuldigen uns auch, wenn diese Frage entweder (1) trivial einfach ist oder (2) auf ein tieferes Missverständnis hinweist oder (3) an anderer Stelle beantwortet wird. Ich bin ein echter Noppen, Leute!

formal-languages reference-request finite-automata Flip
quelle
3
Sie müssen uns sagen, was Sie mit "ähnlich" meinen. Sie müssen die Metrik auswählen; Es gibt keine richtige Metrik, die für alle Zwecke geeignet ist. Ohne weitere Informationen können wir Ihnen nicht sagen, welche Metrik Sie verwenden sollen. Ich schlage vor, die Frage zu bearbeiten, um zu erklären, warum Sie die Ähnlichkeit messen möchten, was Sie mit den Ergebnissen der Ähnlichkeitsmetrik tun und welche Untersuchungen Sie durchgeführt haben. Sie könnten zunächst Ähnlichkeitsmaße zwischen den zugrunde liegenden Zeichenfolgen betrachten, anstatt die Ähnlichkeiten der aus diesen Zeichenfolgen abgeleiteten FSAs zu messen. Distanz bearbeiten fällt mir ein.
DW
Es gibt viele Zeichenfolgenmetriken . Was für Sie funktioniert, hängt davon ab. (Hinweis: Einige der in diesem Artikel aufgeführten Zeichenfolgen "Metriken" sind keine Metriken im mathematischen Sinne.)
Raphael
String-Metriken sind gut, aber nicht ganz das, wonach ich suche. Anstatt bestimmte Zeichenfolgen miteinander zu vergleichen, möchte ich das Regelsystem (die formalen Grammatiken / FSAs) vergleichen, die diese Zeichenfolgen hätten erzeugen können. Ich erkenne, dass es unendlich viele Grammatiken gibt, die eine bestimmte Zeichenfolge erzeugen können. Daher beschränke ich meine Suche auf eine Grammatik (FSA), die nach einem bestimmten Regelwerk erstellt wurde. Ich stelle mir vor, dass es Fälle geben könnte, in denen zwei einzelne Zeichenfolgen gemäß einer bestimmten Zeichenfolgenmetrik formal ähnlich sind, aber die Grammatik, die für ihre Erstellung erforderlich ist, sehr unterschiedlich ist
Flip
Aus der Erklärung des Problems geht hervor, dass jede FSA eine Zeichenfolge und alle ihre Teilzeichenfolgen akzeptiert. Grundsätzlich zeichnet sich diese FSA durch die längste akzeptierte Zeichenfolge aus. Daraus leitet sich seine gesamte Struktur ab. Daher macht es wenig Sinn, die FSA zu vergleichen, anstatt die Zeichenfolgen, aus denen sie aufgebaut sind, direkt zu vergleichen. Es kann sein, dass Ihre FSA-Konstruktionstechnik einige Merkmale hervorhebt, die Sie für wichtig halten. Dann müssen wir wissen, wie sie aussehen können, um zu verstehen, worauf es ankommt. Es kommt zurück auf: Was ist ähnlich, welche Metrik. So wie es ist, macht diese Frage keinen Sinn.
Babou

Antworten:

1

Vielleicht haben Sie aus einem anderen Blickwinkel mehr Glück und untersuchen die Ähnlichkeit von Musikstücken. Es gibt Forscher, die dies untersuchen, und während Ihr Ansatz funktionieren kann, gibt es andere Ansätze. gibt es große Datenbanken , den Blick auf vielen Elemente / Kriterien wie Texte, Genre etc. zB Musik Genomprojekt .

Manchmal, wenn es eine Vielzahl von Algorithmen gibt, kann eine Umfrage helfen. Hier sind zwei Umfragen zum Graph Matching.

vzn
quelle
0

Da es sich bei FSAs um gerichtete Graphen handelt, kann Ihre Frage als "Algorithmus zur Messung der Ähnlichkeit zwischen gerichteten Graphen" verallgemeinert werden. Eine Google-Suche nach "Graph-Ähnlichkeitsalgorithmus" liefert Seiten und Seiten mit Treffern. Vielleicht wäre eine davon für Ihre Zwecke geeignet?

Sobald der Unterschied zwischen FSAs und allgemeinen Digraphen die Kantenbeschriftungen oder Übergangssymbole in FSAs sind, müssten Sie diese Algorithmen ändern, um dies zu berücksichtigen.

Mike Ounsworth
quelle
Bei einer solchen Methode fehlen einige Schlüsseleigenschaften. Beispielsweise möchten Sie wahrscheinlich, dass verschiedene Darstellungen derselben Sprache vollständig ähnlich sind. Wenn Sie jedoch die Diagramme vergleichen, werden möglicherweise zwei Automaten für dieselbe Sprache als unterschiedlich angezeigt.
Jmite