Metoda pomiaru „podobieństwa” między gramatykami FSA?

10

Pracuję z algorytmem dopasowywania wzorców, który generuje acykliczny automat stanów skończonych, który akceptuje dany ciąg tekstowy i wszystkie jego podciągi. Algorytm FSA jest uruchamiany na symbolicznej reprezentacji strumienia muzycznego (np. Dane MIDI). Strumień muzyczny został wstępnie przetworzony, aby podzielić każdą piosenkę na nieoznaczone „segmenty”. FSA jest generowany dla każdego z segmentów w każdym Song: jeśli mają piosenki, dzielone na segmentów będę mieć oddzielne FSA.nyn⋅y

Chciałbym porównać FSA każdego segmentu z innymi FSA w moim korpusie. Ostatecznym celem byłoby tworzenie klastrów w przestrzeni podobieństwa i tworzenie „klas” segmentów zgodnie z tym, jak podobne są ich wskaźniki konstrukcyjne. Dlatego szczególnie interesujące są gramatyki, które definiuje każdy FSA (odpowiadające z grubsza niektórym komponentom treści muzycznych w segmencie). Czy istnieją techniki, które mogą być przydatne do porównania czegoś takiego? Przychodzi mi na myśl rozbieżność KL (np. Używając jej porównać rozkład między łańcuchami związanymi z danym FSA), chociaż mogą istnieć lepsze / bardziej wydajne techniki?

Przepraszamy również, jeśli to pytanie jest (1) trywialnie łatwe lub (2) wskazuje na jakieś głębsze nieporozumienie lub (3) odpowiedział w innym miejscu. Jestem niezły, ludzie!

formal-languages reference-request finite-automata trzepnięcie
źródło
3
Musisz powiedzieć nam, co rozumiesz przez „podobny”. Musisz wybrać metrykę; nie ma jednej właściwej miary, która byłaby odpowiednia do wszystkich celów. Bez dodatkowych informacji nie możemy powiedzieć, jakich danych użyć. Sugeruję edycję pytania, aby wyjaśnić, dlaczego chcesz zmierzyć podobieństwo, co zrobisz z wynikami pomiaru podobieństwa i jakie badania przeprowadziłeś. Możesz zacząć od spojrzenia na miary podobieństw między bazowymi łańcuchami, zamiast mierzenia podobieństw FSA pochodzących z tych łańcuchów. Przypomina się edycja odległości.
DW
Istnieje wiele wskaźników ciągów ; to, co działa dla ciebie, zależy. (Uwaga: niektóre z ciągów „metryk” wymienionych w tym artykule nie są tak naprawdę metrykami w sensie matematycznym.)
Raphael
Wskaźniki ciągów są dobre, ale nie do końca to, o co mi chodzi. Zamiast porównywać ze sobą określone ciągi, chciałbym porównać system reguł (gramatyki formalne / FSA), które mogły wytworzyć te ciągi. Rozumiem, że istnieje nieskończenie wiele gramatyk, które mogą wytwarzać dowolny określony ciąg, więc ograniczam swoje wyszukiwanie do gramatyki (FSA) zbudowanej przy użyciu określonego zestawu reguł. Wyobrażam sobie, że mogą zdarzyć się przypadki, w których dwa pojedyncze łańcuchy są formalnie podobne zgodnie z daną metryką ciągów, ale gramatyka wymagana do ich wytworzenia jest zupełnie inna
przełóż
Z opisu problemu każdy FSA akceptuje jeden ciąg znaków i wszystkie jego podciągi. Zasadniczo ten FSA charakteryzuje się najdłuższym ciągiem, który akceptuje. Z tego wywodzi się cała jego struktura. Dlatego porównywanie FSA nie ma większego sensu, niż bezpośrednie porównywanie ciągów, z których są zbudowane. Być może technika budowy FSA podkreśla pewne cechy, które uważasz za ważne. Następnie musimy wiedzieć, jak mogą wyglądać, aby zrozumieć, co jest ważne. Wraca do: co jest podobne, jakie dane. W tej chwili to pytanie nie ma sensu.
babou

Odpowiedzi:

1

możesz mieć więcej szczęścia z innej strony i patrząc na badania podobieństwa utworów muzycznych, są badacze, którzy to badają, i chociaż twoje podejście może działać, istnieją inne podejścia. istnieją duże bazy danych, które analizują wiele elementów / kryteriów, takich jak teksty piosenek, gatunek itp., np . projekt genomu muzyki .

czasami, gdy istnieje wiele różnych algorytmów, ankieta może pomóc. oto dwie ankiety dotyczące dopasowywania wykresów.

vzn
źródło
0

Ponieważ FSA są grafami ukierunkowanymi, pytanie można uogólnić jako „algorytm pomiaru podobieństwa między grafami ukierunkowanymi”. Wyszukiwanie w Google „algorytmu podobieństwa wykresu” daje strony i strony z wynikami, może jeden z nich byłby odpowiedni do twoich celów?

Kiedyś różnica między FSA a ogólnymi digrafami to etykiety krawędzi lub symbole przejściowe w FSA, więc trzeba by zmodyfikować te algorytmy, aby to uwzględnić.

Mike Ounsworth
źródło
Metoda taka jak ominie niektóre kluczowe właściwości. Na przykład prawdopodobnie chcesz, aby różne reprezentacje tego samego języka miały pełne podobieństwo, ale porównanie wykresów może zgłosić dwa automaty dla tego samego języka, co niepodobne.
jmite