Indukcja gramatyczna - Grammar induction

Część serii na
Uczenie maszynowe
i eksploracja danych
Wielowarstwowa sieć neuronowa-Vector-Blank.svg
Problemy
Uczenie nadzorowane
( klasyfikacja  • regresja )
Grupowanie
Redukcja wymiarowości
Prognoza strukturalna
Wykrywanie anomalii
Sztuczna sieć neuronowa
Nauka wzmacniania
Teoria
Miejsca uczenia maszynowego
Powiązane artykuły

Gramatyka indukcyjna (lub gramatyczne wnioskowanie ) jest procesem, w maszynie uczenie uczenia się formalnego gramatyki (zazwyczaj jako zbiór zasad ponownego zapisu lub produkcji lub alternatywnie jako skończonej maszyny stanów lub automatu pewnego rodzaju) ze zbioru obserwacji, a tym samym zbudowanie modelu uwzględniającego cechy obserwowanych obiektów. Mówiąc bardziej ogólnie, wnioskowanie gramatyczne to ta gałąź uczenia maszynowego, w której przestrzeń instancji składa się z dyskretnych obiektów kombinatorycznych, takich jak ciągi, drzewa i wykresy.

Zajęcia gramatyczne

Wnioskowanie gramatyczne było często bardzo skoncentrowane na problemie uczenia maszyn skończonych różnych typów ( szczegóły na temat tych podejść można znaleźć w artykule Indukcja języków regularnych ), ponieważ od lat 80. XX wieku istnieją wydajne algorytmy rozwiązywania tego problemu.

Od początku stulecia podejścia te rozszerzono o problem wnioskowania o gramatykach bezkontekstowych i bogatszych formalizmach, takich jak wielokrotne gramatyki bezkontekstowe i równoległe wielokrotne gramatyki bezkontekstowe. Inne klasy gramatyk, dla których badano wnioskowanie gramatyczne, to kombinatoryczne gramatyki kategorialne , stochastyczne gramatyki bezkontekstowe , gramatyki kontekstowe i języki wzorców.

Modele uczenia się

Najprostsza forma uczenia się polega na tym, że algorytm uczenia otrzymuje jedynie zestaw przykładów zaczerpniętych z danego języka: celem jest nauka języka na jego przykładach (i rzadko na kontrprzykładach, czyli przykładach, które nie należą do języka). Jednak zbadano inne modele uczenia się. Jedną z często badanych alternatyw jest przypadek, w którym uczeń może zadawać pytania dotyczące członkostwa, jak w dokładnym modelu uczenia się za pomocą zapytań lub minimalnie adekwatnym modelu nauczyciela wprowadzonym przez Angluin.

Metodologie

Istnieje wiele różnych metod wnioskowania gramatycznego. Dwa z klasycznych źródeł to Fu (1977) i Fu (1982) . Duda, Hart i Stork (2001) również poświęcają temu zagadnieniu krótką część i przytaczają szereg odniesień. Poniżej omówiono podstawową metodę prób i błędów, którą prezentują. Podejścia do wywnioskowania podklas języków regularnych w szczególności, zobacz Indukcja języków regularnych . Nowszym podręcznikiem jest de la Higuera (2010), który obejmuje teorię wnioskowania gramatycznego języków regularnych i automatów skończonych. D'Ulizia, Ferri i Grifoni przeprowadzają ankietę badającą metody wnioskowania gramatycznego dla języków naturalnych.

Wnioskowanie gramatyczne metodą prób i błędów

Metoda zaproponowana w rozdziale 8.7 pracy Duda, Hart i Stork (2001) sugeruje sukcesywne odgadywanie reguł gramatycznych (produkcja) i testowanie ich z pozytywnymi i negatywnymi obserwacjami. Zestaw reguł jest rozszerzany, aby móc wygenerować każdy pozytywny przykład, ale jeśli dany zestaw reguł generuje również negatywny przykład, należy go odrzucić. To szczególne podejście można scharakteryzować jako „testowanie hipotez” i wykazuje pewne podobieństwo do algorytmu przestrzeni wersji Mitchela . Tekst Duda, Hart i Stork (2001) dostarcza prostego przykładu, który ładnie ilustruje ten proces, ale wykonalność takiego niekierowanego podejścia opartego na próbach i błędach w przypadku bardziej istotnych problemów jest wątpliwa.

Wnioskowanie gramatyczne za pomocą algorytmów genetycznych

Indukcja gramatyczna przy użyciu algorytmów ewolucyjnych to proces ewolucji reprezentacji gramatyki języka docelowego poprzez pewien proces ewolucyjny. Gramatyki formalne można łatwo przedstawić jako struktury drzewiaste reguł produkcji, które można poddać operatorom ewolucyjnym. Algorytmy tego rodzaju wywodzą się z paradygmatu programowania genetycznego, którego pionierem był John Koza . Inne wczesne prace nad prostymi językami formalnymi wykorzystywały binarną reprezentację algorytmów genetycznych, ale z natury hierarchiczna struktura gramatyk sformułowanych w języku EBNF sprawiła, że ​​drzewa stały się bardziej elastycznym podejściem.

Koza reprezentowała programy Lisp jako drzewa. Był w stanie znaleźć analogi do operatorów genetycznych w standardowym zestawie operatorów drzew. Na przykład zamiana poddrzew jest odpowiednikiem odpowiedniego procesu krzyżowania genetycznego, w którym podciągi kodu genetycznego są przeszczepiane osobnikowi następnego pokolenia. Sprawność jest mierzona poprzez ocenę wyników funkcji kodu Lisp. Podobne analogie między reprezentacją seplenienia o strukturze drzewa a reprezentacją gramatyk jako drzew umożliwiły zastosowanie technik programowania genetycznego do indukcji gramatyki.

W przypadku indukcji gramatycznej przeszczepienie poddrzew odpowiada zamianie reguł produkcji, które umożliwiają parsowanie fraz z jakiegoś języka. Operator sprawności gramatyki opiera się na pewnej mierze tego, jak dobrze poradziła sobie z analizowaniem pewnej grupy zdań z języka docelowego. W drzewiastej reprezentacji gramatyki końcowy symbol reguły produkcji odpowiada węzłowi liściowemu drzewa. Jego węzły rodzicielskie odpowiadają symbolowi niekońcowemu (np. frazie rzeczownikowej lub czasownikowej ) w zestawie reguł. Ostatecznie węzeł główny może odpowiadać zdaniu nieterminalnemu.

Wnioskowanie gramatyczne przez algorytmy zachłanne

Podobnie jak wszystkie zachłanne algorytmy , zachłanne algorytmy wnioskowania gramatycznego podejmują w sposób iteracyjny decyzje, które na tym etapie wydają się najlepsze. Podejmowane decyzje zwykle dotyczą takich rzeczy, jak tworzenie nowych reguł, usuwanie istniejących reguł, wybór reguły do ​​zastosowania lub łączenie niektórych istniejących reguł. Ponieważ istnieje kilka sposobów na zdefiniowanie „etapu” i „najlepszego”, istnieje również kilka zachłannych algorytmów wnioskowania gramatycznego.

Te bezkontekstowe algorytmy generowania gramatyki podejmują decyzję po każdym odczytanym symbolu:

  • Algorytm Lempel-Ziv-Welch tworzy gramatykę bezkontekstową w sposób deterministyczny, tak że konieczne jest przechowywanie tylko reguły początkowej wygenerowanej gramatyki.
  • Sequitur i jego modyfikacje.

Te bezkontekstowe algorytmy generujące gramatykę najpierw odczytują całą podaną sekwencję symboli, a następnie zaczynają podejmować decyzje:

Nauczanie dystrybucyjne

Nowsze podejście opiera się na uczeniu dystrybucyjnym. Algorytmy wykorzystujące te podejścia zostały zastosowane do nauki gramatyk bezkontekstowych i umiarkowanie kontekstowych języków i okazały się poprawne i wydajne w przypadku dużych podklas tych gramatyk.

Nauka języków wzorcowych

Angluin definiuje wzorzec jako „łańcuch symboli stałych z Σ i symboli zmiennych z zestawu rozłącznego”. Język takiego wzorca jest zbiorem wszystkich jego niepustych instancji podstawowych, tj. wszystkich ciągów znaków wynikających z konsekwentnego zastępowania jego symboli zmiennych przez niepuste ciągi symboli stałych. Wzorzec jest nazywany opisowym dla skończonego wejściowego zbioru łańcuchów, jeśli jego język jest minimalny (w odniesieniu do włączenia zbioru) wśród wszystkich języków wzorców obejmujących zbiór wejściowy.

Angluin daje algorytm wielomianowy do obliczenia, dla danego zestawu ciągów wejściowych, wszystkich wzorców opisowych w jednej zmiennej x . W tym celu buduje automat reprezentujący wszelkie możliwe wzorce; używając wyrafinowanych argumentów dotyczących długości słów, które opierają się na x jako jedynej zmiennej, liczba stanów może zostać drastycznie zmniejszona.

Erlebach i in. dać bardziej wydajną wersję algorytmu uczenia się wzorców Angluin, a także wersję zrównoległą.

Arimura i in. pokazują, że klasę języka uzyskaną z ograniczonych związków wzorców można nauczyć się w czasie wielomianowym.

Teoria wzorców

Teoria wzorców , sformułowana przez Ulfa Grenandera , to matematyczny formalizm opisujący wiedzę o świecie jako wzorce. Różni się od innych podejść do sztucznej inteligencji tym, że nie zaczyna się od przepisywania algorytmów i maszyn do rozpoznawania i klasyfikowania wzorców; raczej zaleca słownictwo do artykułowania i przekształcania pojęć wzorcowych w precyzyjnym języku.

Oprócz nowego słownictwa algebraicznego, nowatorskie podejście statystyczne miało na celu:

  • Zidentyfikuj ukryte zmienne zestawu danych, używając danych ze świata rzeczywistego, a nie sztucznych bodźców, co było wówczas powszechne.
  • Sformułuj wcześniejsze rozkłady dla ukrytych zmiennych i modele dla obserwowanych zmiennych, które tworzą wierzchołki grafu podobnego do Gibbsa.
  • Zbadaj losowość i zmienność tych wykresów.
  • Utwórz podstawowe klasy stosowanych modeli stochastycznych, wymieniając deformacje wzorców.
  • Syntezuj (próbkę) z modeli, a nie tylko analizuj za ich pomocą sygnały.

Szeroka pod względem matematycznym teoria wzorów obejmuje algebrę i statystykę, a także lokalne właściwości topologiczne i globalne entropiczne.

Aplikacje

Zasada indukcji gramatycznej została zastosowana do innych aspektów przetwarzania języka naturalnego i została zastosowana (między wieloma innymi problemami) do parsowania semantycznego , rozumienia języka naturalnego , tłumaczenia opartego na przykładach , analizy morfemów i wyprowadzania nazw miejsc. Indukcję gramatyczną zastosowano również do kompresji opartej na gramatyce i wnioskowania statystycznego za pomocą zasad minimalnej długości wiadomości (MML) i minimalnej długości opisu (MDL). Indukcję gramatyczną stosowano również w niektórych probabilistycznych modelach akwizycji języka .

Zobacz też

Uwagi

Bibliografia

Źródła