Шексіз тілдерді тану моделі

Кіріспе

Тілдерді лимитте анықтау – негізінен компьютерлер арқылы формалды тілдерді индуктивті қорытудың формалды моделі (машиналық оқыту және реттелі тілдерді қорытуды қараңыз). Оны Э. Марк Голд техникалық есептемесінде және сол аттас мақаласында енгізді. Бұл модельде мұғалім оқушыға белгілі бір формалды тілдің ұсынысын (яғни, жолдар тізбегін) ұсынады. Оқу процесі шексіз деп есептеледі. Оқушы ұсыныстың әрбір элементін оқыған сайын, ол тілдің өрнегін (мысалы, формалды грамматика) беруі керек. Голд оқушының тілдер класын лимитте анықтай алатынын анықтайды, егер кластағы кез келген тілдің кез келген ұсынысы берілгенде, оқушы тек шектеулі санда қате өрнектер шығарады, содан кейін дұрыс өрнекке тоқталады. Дегенмен, оқушы өзінің дұрыстығын жариялауға міндетті емес; және мұғалім кез келген өрнекке қарсы мысал кез келген уақытта ұсынуы мүмкін. Голд ұсыныстың екі түрін анықтады: Мәтін (оң ақпарат): тілді құрайтын барлық жолдардың тізбегі. Толық ұсыныс (оң және теріс ақпарат): барлық мүмкін жолдардың тізімі, олардың әрқайсысы жол тілге жата ма, жатпай ма, дегенді көрсететін белгімен.

Мысалдар

+ 4. Сұраныс бойынша толық презентация Мұғалім Оқушының болжау сұранысы 0. abab 1. abab baba 2. a*(ba)*b* aa 3. (ab)*(ba)*(ab)*(ba)* bababa 4. (ab+ba)* babb 5. (ab+ba)* baaa
+ 3. Оқытушы-оқушыға 1. abab 2. a*(ba)*b* 3. (ab)*(ba)*(ab)*(ba)* 4. (ab+ba)* 5. (ab+ba)* 6. (ab+ba)* 7. (ab+ba)*
+ 2. Одақ болжау Ұстаз Оқушы 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. Мәтінді ұсыну Ұстаз Оқушы 1. 2. + 3. (b+ε)(ab)* 4. (b+ε)(ab)*+ 5. (ab)*(ba)*(ab)*(ba)* 6. (ab+ba)* 7. (ab+ba)*

Таблицадағы нақты мысалдарды қарастыру пайдалы. Текстті ұсынудан {a,b} алфавитіне L тұрақты тілін үйрену үшін ойдан шығарылған сессия: Әр қадамда мұғалім L-ге жататын тізбек береді, ал оқушы L үшін болжамды жауап береді, ол тұрақты өрнек ретінде кодталады. 3-қадамда оқушының болжамы осыған дейін көрген тізбектермен сәйкес келмейді; 4-қадамда мұғалім бір тізбені бірнеше рет береді. 6-қадамнан кейін оқушы тұрақты өрнекті (ab+ba)* қолданады. Егер бұл мұғалім ойдағы L тілінің сипаттамасы болса, онда оқушы сол тілді үйренді деп айтылады. Егер оқушының рөліне арналған компьютерлік бағдарлама болса, ол әр тұрақты тілді сәтті үйрене алатын болса, онда тілдердің бұл класы шекте анықталатын болады. Голд зерттеудің нәтижесі бұның дұрыс емес екенін көрсетті. Белгілі бір оқу алгоритмі әрқашан L-ді осы уақытқа дейін көрінген барлық тізбектердің бірігуі деп болжайды: Егер L - шекті тіл болса, оқушы оны дұрыс болжайды, бірақ қашан екенін айта алмайды. 3-6 қадамда болжау өзгермесе де, оқушы дұрыс екеніне сенімді бола алмайды. Голд шекті тілдер класының шекте анықталатынын көрсетті, алайда бұл класс шекті де, белгіленген уақытта да анықталмайды. Толық презентациядан үйрену: Әр қадамда мұғалім бір жолды береді және оның L-ге жататынын немесе жатпайтынын айтады. Сұрау бойынша толық баяндаудан үйрену: Оқушы сұраныс тізбегін береді, мұғалім оның L-ге жататынын немесе жатпайтынын айтады; Оқушы содан кейін L-ге болжау береді, содан кейін келесі сұраныс тізбегі. Бұл мысалда оқушы әр қадамда мұғалімнің 3-ші мысалда берген тізбегін сұрап алады. Жалпы, Голд әрбір тіл класы сұраныс презентация параметрінде анықталатын, сонымен қатар, баяндау презентация параметрінде де анықталатындығын көрсетті, өйткені оқушы, сөз тізбегін сұратудың орнына, оны мұғалім бергенше күтуі керек.

It is instructive to look at concrete examples (in the tables) of learning sessions the definition of identification in the limit speaks about. A fictitious session to learn a regular language L over the alphabet {a,b} from text presentation:In each step, the teacher gives a string belonging to L, and the learner answers a guess for L, encoded as a regular expression. In step 3, the learner's guess is not consistent with the strings seen so far; in step 4, the teacher gives a string repeatedly. After step 6, the learner sticks to the regular expression (ab+ba)*. If this happens to be a description of the language L the teacher has in mind, it is said that the learner has learned that language. If a computer program for the learner's role would exist that was able to successfully learn each regular language, that class of languages would be identifiable in the limit. Gold has shown that this is not the case. A particular learning algorithm always guessing L to be just the union of all strings seen so far:If L is a finite language, the learner will eventually guess it correctly, however, without being able to tell when. Although the guess didn't change during step 3 to 6, the learner couldn't be sure to be correct. Gold has shown that the class of finite languages is identifiable in the limit, however, this class is neither finitely nor fixed time identifiable. Learning from complete presentation by telling:In each step, the teacher gives a string and tells whether it belongs to L or not Each possible string is eventually classified in this way by the teacher. Learning from complete presentation by request:The learner gives a query string, the teacher tells whether it belongs to L or not ; the learner then gives a guess for L, followed by the next query string. In this example, the learner happens to query in each step just the same string as given by the teacher in example 3. In general, Gold has shown that each language class identifiable in the request presentation setting is also identifiable in the telling presentation setting, since the learner, instead of querying a string, just needs to wait until it is eventually given by the teacher.

Оқу қабілетін сипаттау

Дана Англюин 1980 жылғы мақаласында мәтін арқылы үйренудің сипаттамасын берді (оң пікір). Егер оқушы тиімді болуы керек болса, онда рекурсивті тілдердің индекстелген класы, егер кластағы әрбір тіл үшін оқиғаларды біркелкі тізімдейтін тиімді процедура болса, шекте үйреніледі (1-шарт). Егер идеалды оқушыға (яғни, кез келген функцияға) рұқсат берілсе, онда индекстелген тілдер класы, егер кластағы әрбір тілде оқиға болса, шекте үйреніледі (2-шарт).

Оқу қабілеті үшін жеткілікті жағдайлар

Англюиннің мақаласындағы 1-шарт бойынша, егер рекурсивті тілдер класының шекті қалыңдығы болса, онда оны лимит бойынша үйренуге болады. Шекті қалыңдығы бар класс, әрине, МЭҚ және МҚҚ шарттарын қанағаттандырады; яғни, шекті қалыңдық М шекті қалыңдығын білдіреді.

Шекті икемділік

Тілдер класы шекті серпімділікке ие деп есептеледі, егер кластағы әрбір шексіз тізбек және тілдердің әрбір шексіз тізбегі үшін, мұндай n саны болса, онда бұл керісінше дұрыс емес. Шекті серпімділік және консервативті үйренуге болатындық, ой өзгерту шегінің болуын білдіреді. Шекті серпімділік және M шекті қалыңдығы, ой өзгерту шегінің болуын білдіреді. Дегенмен, M шекті қалыңдығы ғана ой өзгерту шегінің болуын білдірмейді; сондай-ақ, ой өзгерту шегінің болуы M шекті қалыңдығын білдірмейді. Ой өзгерту шегінің болуы үйренуге қабілеттілікті білдіреді; керісінше, бұл дұрыс емес. Егер біз есептелмейтін оқушыларды қарастырсақ, онда шекті серпімділік ой өзгерту шегінің болуын білдіреді; керісінше, бұл дұрыс емес. Егер тілдер класы үшін жинақталу реті болмаса, онда класта шексіз қиылыс қасиетіне ие тіл (класта міндетті түрде болмауы мүмкін) бар, бұл өз кезегінде кластың шексіз серпімділігін білдіреді.