Identyfikacja języka w limicie

Identyfikacja języka w granicy jest formalnym modelem indukcyjnego wnioskowania o językach formalnych , głównie przez komputery (patrz uczenie maszynowe i indukcja języków regularnych ). Został wprowadzony przez E. Marka Golda w raporcie technicznym i artykule w czasopiśmie o tym samym tytule.

W tym modelu nauczyciel zapewnia uczniowi prezentację ( tj . sekwencję ciągów znaków ) jakiegoś formalnego języka. Uczenie się jest postrzegane jako nieskończony proces. Za każdym razem, gdy uczeń czyta element prezentacji, powinien on przedstawiać reprezentację ( np. gramatykę formalną ) języka.

Gold definiuje, że uczeń może zidentyfikować w limicie klasę języków, jeśli przy jakiejkolwiek prezentacji dowolnego języka w klasie, uczeń stworzy tylko skończoną liczbę błędnych reprezentacji, a następnie będzie trzymał się prawidłowej reprezentacji. Jednak uczący się nie musi być w stanie ogłosić swojej poprawności; a nauczyciel może podać kontrprzykład dla dowolnego przedstawienia arbitralnie długo po tym.

Gold zdefiniował dwa rodzaje prezentacji:

• Tekst (informacja pozytywna): wyliczenie wszystkich łańcuchów, z których składa się język.
• Pełna prezentacja (informacje pozytywne i negatywne): wyliczenie wszystkich możliwych ciągów, każdy z etykietą wskazującą, czy ciąg należy do języka, czy nie.

Łatwość uczenia się

Model ten jest wczesną próbą formalnego uchwycenia pojęcia zdolności uczenia się . Artykuł w czasopiśmie Golda przedstawia dla kontrastu silniejsze modele

• Skończona identyfikacja (gdzie uczeń musi ogłosić poprawność po skończonej liczbie kroków) oraz
• Identyfikacja w ustalonym czasie (gdzie poprawność musi zostać osiągnięta po określonej z góry liczbie kroków).

Słabszym formalnym modelem zdolności uczenia się jest model prawdopodobnie poprawnego uczenia się (PAC) , wprowadzony przez Lesliego Valianta w 1984 roku.

Przykłady

4. Kompletna prezentacja na żądanie

	Nauczyciel	ucznia
		Zgadywać	Zapytanie
0.			Abab
1.	Tak	Abab	baba
2.	Tak	za * ( ba ) * b *	aa
3.	NIE	( ab ) * ( ba ) * ( ab ) * ( ba ) *	bababa
4.	Tak	( ab + ba ) *	babb
5.	NIE	( ab + ba ) *	baaa
	...	...

3. Uzupełnij prezentację opowiadając

	Nauczyciel	Uczeń
1.	Abab	Abab
2.	baba	za * ( ba ) * b *
3.	aa	( ab ) * ( ba ) * ( ab ) * ( ba ) *
4.	bababa	( ab + ba ) *
5.	babb	( ab + ba ) *
6.	baaa	( ab + ba ) *
7.	ε	( ab + ba ) *
	...	...

2. Zgadywanie unii
 

	Nauczyciel	Uczeń
1.	Abab	Abab
2.	ba	abab + ba
3.	baba	abab + ba + baba
4.	ba	abab + ba + baba
5.	baba	abab + ba + baba
6.	Abab	abab + ba + baba
7.	ε	abab + ba + baba + ε
	...	...

1. Prezentacja tekstu
 

	Nauczyciel	Uczeń
1.	Abab	Abab
2.	baba	abab + baba
3.	baabab	( b + ε)( ab ) *
4.	baabab	( b + ε)( ab ) * + baabab
5.	Abbaabba	( ab ) * ( ba ) * ( ab ) * ( ba ) *
6.	baabbaab	( ab + ba ) *
7.	bababa	( ab + ba ) *
	...	...

Pouczające jest przyjrzenie się konkretnym przykładom (w tabelach) sesji uczenia się, o których mówi definicja identyfikacji w granicy.

1. 
   Fikcyjna sesja nauki języka regularnego L nad alfabetem { a , b } z prezentacji tekstowej : W każdym kroku nauczyciel podaje ciąg należący do L , a uczeń odpowiada na odgadnięcie L , zakodowane jako wyrażenie regularne . W kroku 3 zgadywanie ucznia nie jest zgodne z łańcuchami widzianymi do tej pory; w kroku 4 nauczyciel wielokrotnie podaje ciąg znaków. Po kroku 6
   , uczeń trzyma się wyrażenia regularnego ( ab + ba ) ^* . Jeśli tak się składa, że ​​jest to opis języka L , który nauczyciel ma na myśli, mówi się, że uczeń nauczył się tego języka. Gdyby istniał program komputerowy do roli ucznia, który byłby w stanie z powodzeniem nauczyć się każdego zwykłego języka, ta klasa języków byłaby możliwa do zidentyfikowania w limicie . Złoto pokazało, że tak nie jest.
2. 
   
   Konkretny algorytm uczący się zawsze zgadujący, że L jest po prostu sumą wszystkich łańcuchów widzianych do tej pory : jeśli L jest skończonym językiem, uczeń w końcu odgadnie go poprawnie, jednak nie będzie w stanie powiedzieć kiedy. Chociaż przypuszczenie nie zmieniło się w krokach od 3 do 6 , uczeń nie mógł mieć pewności, że jest poprawny. Gold wykazał, że klasę języków skończonych można zidentyfikować w granicach, jednak klasy tej nie można zidentyfikować ani w sposób skończony, ani w ustalonym czasie.
3. 
   Uczenie się z pełnej prezentacji poprzez opowiadanie : W każdym kroku nauczyciel podaje ciąg znaków i mówi, czy należy on do litery L ( zielony ), czy nie ( czerwony, przekreślony ). Każdy możliwy ciąg jest ostatecznie klasyfikowany w ten sposób przez nauczyciela.
4. 
   Uczenie się z pełnej prezentacji na żądanie : Uczeń podaje ciąg zapytania, nauczyciel mówi, czy należy on do L ( tak ), czy nie ( nie ); uczeń następnie podaje zgadywanie dla L , po którym następuje następny ciąg zapytania. W tym przykładzie uczeń wysyła zapytanie w każdym kroku o ten sam ciąg znaków, który podał nauczyciel w przykładzie 3.
   Ogólnie rzecz biorąc, Gold wykazał, że każdą klasę językową identyfikowalną w ustawieniu prośba-prezentacja można również zidentyfikować w ustawieniu mówienie-prezentacja, ponieważ uczeń, zamiast pytać o ciąg, musi po prostu poczekać, aż nauczyciel w końcu go poda.

Twierdzenie Golda

Bardziej formalnie,

• język $zbiorem$ niepustym, a jego elementy nazywane są zdaniami .
• rodzina językowa to zbiór języków.
• środowisko $L}$ nauki języka dla języka to strumień zdań z $, tak że$$każde$ zdanie w $displaystyle$ się co najmniej raz
• uczący się języka to funkcja $która$ wysyła listę zdań do języka.
  • Jest to interpretowane jako stwierdzenie, że po obejrzeniu zdań ${\ Displaystyle a_ {1}, a_ {2} ..., a_ {n}}$ w tej kolejności , uczący się języka zgaduje ${\ Displaystyle f (a_ {1}, ..., a_ {n})}$ tworzy zdania, powinno .
  • ${\ displaystyle a_ {1}, ..., a_ {n}$ że uczeń nie jest zobowiązany do poprawności — równie dobrze mógłby odgadnąć język, który nie zawiera nawet .
• $uczący$ języka uczy się języka w środowisku $Displaystyle E = ($${1}, a_ {2} ,$ , jeśli uczeń zawsze zgaduje $wystarczającej$ liczby przykładów ze środowiska.
• $języka$$L$ się języka uczy się , jeśli uczy się w dowolnym środowisku dla $displaystyle$${$$}$
• rodzina językowa jest możliwa do nauczenia , jeśli istnieje osoba ucząca się języka, która może nauczyć się wszystkich języków w rodzinie.

Uwagi:

• W kontekście twierdzenia Golda zdania muszą być tylko rozróżnialne. Nie muszą to być nic szczególnego, na przykład skończone ciągi znaków (jak zwykle w językoznawstwie formalnym).
• Łatwość uczenia się nie jest pojęciem dla poszczególnych języków. Każdy indywidualny język $być$$zgaduje$ przez trywialnego ucznia, który zawsze .
• Uczenie się nie jest pojęciem dla poszczególnych uczniów. Rodzina językowa jest możliwa do nauczenia się, jeśli istnieje jakiś uczeń, który może się jej nauczyć. Nie ma znaczenia, jak dobrze uczeń radzi sobie z nauką języków poza rodziną.

  Twierdzenie Golda (1967) $($${2}, ..., L_ {\ infty}}$ I.8 z (Gold, 1967)) - Jeśli rodzina języków zawiera takie, że

$${\ Displaystyle L_ {1} \ subsetneq L_ {2} \ subsetneq \ cdots}$$

i ${\ Displaystyle L _ {\ infty} = \ kubek _ {n = 1} ^ {\ infty} L_ {n}}, to nie$ jest do nauczenia.

Dowód

Załóżmy, $jest$ uczniem, który może się uczyć ${\ Displaystyle L_ {1}, L_ {2}, ...}$${\ Displaystyle L_ {\$ to pokazujemy, że nie może się nauczyć , konstruując środowisko dla $}$ to „sztuczki” ${\ displaystyle f}$ .

Najpierw skonstruuj środowiska ${\ Displaystyle E_ {1}, E_ {2}, ...}$ dla języków ${\ Displaystyle L_ {1}, L_ {2},...}$ .

Następnie skonstruuj środowisko indukcyjnie $E$ następujący sposób: ${\ displaystyle$

• Prezentuj z $displaystyle$${1}}$ \ $wyjdzie$ dopóki nie
• $naprzemienną$$_$ na $resztą$ z i _ Ponieważ ${\ Displaystyle L_ {1} \ subset L_ {2}}$ , to połączone środowisko jest nadal środowiskiem dla ${\ Displaystyle L_ {2}}$ , więc $wyjść$ musi ${\ Displaystyle L_ {2}}$ .
• $}$ reszty i całości $3$ .
• I tak dalej.

${\ Displaystyle E_ {1}, E_ {2},...}$ powstałe środowisko całość $.$ , więc zawiera ${\ Displaystyle \ kubek _ {n} E_ {n} = \ kubek _ {n} L_ {n} = L_ {\ infty}}$ , więc jest to środowisko dla ${\ Displaystyle L_ {\ infty}}$ . Ponieważ uczeń zawsze przełącza się na $\ displaystyle L_ {\ infty$ skończony $,$ nigdy nie zbiega się do ${$ }

Twierdzenie Golda można łatwo obejść, jeśli dozwolone są negatywne przykłady . ${\ Displaystyle \ {L_ {1}, L_ {2}, ..., L _ {\ infty} \}}$ rodzina się nauczyć uczeń, który zawsze zgaduje ${\ Displaystyle L_ {\ infty} },$ dopóki nie otrzyma pierwszego negatywnego przykładu ${\ Displaystyle \ neg a_ {n}}$ , gdzie ${\ Displaystyle a_ {n} \ w L_ {n + 1} \ setminus L_ {n}}$ , w którym to momencie zawsze zgaduje ${\ Displaystyle L_ {n}}$ .

Charakterystyka uczenia się

Dana Angluin przedstawił charakterystykę możliwości uczenia się z tekstu (informacje pozytywne) w artykule z 1980 roku. Jeśli od ucznia wymaga się, aby był efektywny , to indeksowana klasa języków rekurencyjnych jest możliwa do nauczenia się w limicie, jeśli istnieje skuteczna procedura, która jednolicie wylicza wskaźniki ostrzegawcze dla każdego języka w klasie (Warunek 1). Nietrudno zauważyć, że jeśli dopuszczony jest idealny uczeń (tj. dowolna funkcja), to zindeksowana klasa języków jest możliwa do nauczenia się w granicach, jeśli każdy język w klasie ma wskaźnik ostrzegawczy (Warunek 2).

Zajęcia językowe do nauki w limicie

Linie podziału między identyfikowalnymi i nieidentyfikowalnymi klasami językowymi

Model uczenia się	Klasa języków
Anomalna prezentacja tekstu
	Rekurencyjnie wyliczalna
	Rekurencyjna
Kompletna prezentacja
	Prymitywna rekurencyjna
	Kontekstowa
	Bezkontekstowa
	Regularna
	Superfinite
Normalna prezentacja tekstu
	Skończona
	Singleton

Tabela pokazuje, które klasy językowe są możliwe do zidentyfikowania w ramach danego modelu uczenia się. Po prawej stronie każda klasa językowa jest nadklasą wszystkich niższych klas. Każdy model uczenia się (tj. typ prezentacji) może identyfikować w limicie wszystkie klasy poniżej niego. W szczególności klasa języków skończonych jest możliwa do zidentyfikowania w granicach poprzez prezentację tekstu (por. Przykład 2 powyżej ), podczas gdy klasa języków regularnych nie.

Języki wzorców , wprowadzone przez Danę Angluin w innym artykule z 1980 roku, można również rozpoznać po normalnej prezentacji tekstu; są one pominięte w tabeli, ponieważ znajdują się powyżej klasy pojedynczej i poniżej prymitywnej klasy języka rekurencyjnego, ale nieporównywalne z klasami pomiędzy nimi.

Wystarczające warunki do uczenia się

Warunek 1 w artykule Angluina nie zawsze jest łatwy do zweryfikowania. Dlatego ludzie wymyślają różne warunki wystarczające do uczenia się klasy językowej. Zobacz także Indukcja języków regularnych dla możliwych do nauczenia podklas języków regularnych.

Skończona grubość

Klasa języków ma skończoną grubość , jeśli każdy niepusty zbiór ciągów znaków jest zawarty w co najwyżej skończenie wielu językach tej klasy. To jest dokładnie Warunek 3 w artykule Angluina. Angluin wykazał, że jeśli klasa języków rekurencyjnych ma skończoną grubość, to można się jej nauczyć w granicach.

Klasa o skończonej grubości z pewnością spełnia warunek MEF i warunek MFF ; innymi słowy, skończona grubość implikuje M-skończoną grubość .

Skończona elastyczność

Mówimy, że klasa języków ma skończoną elastyczność, jeśli dla każdego nieskończonego ciągu napisów ${\ Displaystyle s_ {0}, s_ {1},...}$ i każda nieskończona sekwencja języków w klasie ${\ Displaystyle L_ {1}, L_ {2}, ...}$ istnieje skończona liczba n taka, że ​​implikuje ${\ Displaystyle s_ {n} \ not \ in L_ {n}}$${\ Displaystyle L_ {n}}$ jest niezgodne z $..., s_ {n-1} \}}$ .

Pokazano, że klasa rekurencyjnie przeliczalnych języków jest możliwa do nauczenia się w granicy, jeśli ma skończoną elastyczność.

Zobowiązanie do zmiany zdania

Ograniczenie liczby zmian hipotez, które występują przed zbieżnością.

Inne koncepcje

Nieskończona własność krzyżowa

Język L ma nieskończoną właściwość krzyżową w klasie języków , jeśli istnieje nieskończona sekwencja różnych języków ${\ displaystyle {\ displaystyle {\}$$} L ja {\ displaystyle {$$\}} mathcal {L}}}$ i sekwencja skończonego podzbioru taka, że: ${\ displaystyle T_ {i}}$

• ${\ Displaystyle T_ {1} \ podzbiór T_ {2} \ podzbiór ...}$ ,
• ${\ Displaystyle T_ {i} \ w L_ {i}}$ ,
• ${\ Displaystyle T_ {i + 1} \ nie \ w L_ {i}}$ i
• ${\ Displaystyle \ lim _ {n = \ infty} T_ {i} = L}$ .

Zauważ, że L niekoniecznie należy do klasy języków.

Nietrudno zauważyć, że jeśli istnieje język o nieskończonej właściwości krzyżowej w obrębie klasy języków, to ta klasa języków ma nieskończoną elastyczność.

Relacje między pojęciami

• Skończona grubość implikuje skończoną elastyczność; odwrotność nie jest prawdziwa.
• Skończona elastyczność i konserwatywnie możliwa do nauczenia implikuje istnienie granicy zmiany umysłu. [1]
• Skończona elastyczność i M-skończona grubość implikują istnienie granicy zmiany umysłu. Jednak M-skończona grubość nie implikuje istnienia ograniczenia związanego ze zmianą umysłu; ani istnienie ograniczonej zmiany umysłu nie implikuje M-skończonej grubości . [2]
• Istnienie ograniczenia związanego ze zmianą umysłu oznacza zdolność do uczenia się; odwrotność nie jest prawdziwa.
• Jeśli weźmiemy pod uwagę uczących się, których nie można obliczyć, to skończona elastyczność implikuje istnienie ograniczenia związanego ze zmianą umysłu; odwrotność nie jest prawdziwa.
• Jeśli nie ma porządku akumulacji dla klasy języków, to istnieje język (niekoniecznie w klasie), który ma nieskończoną własność krzyżową w obrębie klasy, co z kolei implikuje nieskończoną elastyczność klasy.

Otwarte pytania

• Jeśli policzalna klasa języków rekurencyjnych ma zmianę zdania związaną z uczniami nieobliczalnymi, czy ta klasa ma również zmianę zdania związaną z uczniami obliczalnymi, czy też klasa jest niemożliwa do nauczenia się przez ucznia obliczeniowego?