Определение языка в лимите - Language identification in the limit

Определение языка в лимите формальная модель для индуктивный вывод из формальные языки, в основном с помощью компьютеров (см. машинное обучение и индукция регулярных языков ). Он был представлен Э. Марк Голд в техническом отчете^[1] и журнальная статья^[2] с таким же названием.

В этой модели учитель предоставляет ученик немного презентация (т.е. последовательность струны ) некоторого формального языка. Обучение рассматривается как бесконечный процесс. Каждый раз, когда учащийся читает элемент презентации, он должен представление (например, формальная грамматика ) для языка.

Золото определяет, что учащийся может идентифицировать в пределе класс языков, если при любом представлении любого языка в классе учащийся произведет только конечное число неправильных представлений, а затем будет придерживаться правильного представления. Однако учащийся не должен уметь объявлять о его правильности; и учитель может сколь угодно долго спустя представить контрпример любому представлению.

Голд определил два типа презентаций:

Текст (положительная информация): перечисление всех строк, из которых состоит язык.
Полное представление (положительная и отрицательная информация): перечисление всех возможных строк, каждая с меткой, указывающей, принадлежит ли строка к языку или нет.

Обучаемость

Эта модель представляет собой раннюю попытку формально уловить понятие обучаемость.Золотая бумага^[3] вводит для контраста более сильные модели

Конечная идентификация (где учащийся должен объявить о правильности после конечного числа шагов), и
Идентификация с фиксированным временем (где правильность должна быть достигнута после определенного априори количества шагов).

Более слабой формальной моделью обучаемости является Наверное, примерно правильное обучение (PAC) модель, представленная Лесли Валиант в 1984 г.

Примеры

4. Полная презентация
по запросу
	Учитель	Ученика
		Угадай	Запрос
0.			Abab
1.	да	Abab	баба
2.	да	а^(ба)^б^*	аа
3.	нет	(ab)^(ба)^(ab)^(ба)^	бабаба
4.	да	(ab+ба)^*	бабб
5.	нет	(ab+ба)^*	бааа
	...	...

3. Полная презентация
рассказывая
	Учитель	Ученик
1.	Abab	Abab
2.	баба	а^(ба)^б^*
3.	аа	(ab)^(ба)^(ab)^(ба)^
4.	бабаба	(ab+ба)^*
5.	~~бабб~~	(ab+ба)^*
6.	~~бааа~~	(ab+ба)^*
7.	ε	(ab+ба)^*
	...	...

2. Отгадывание союза
	Учитель	Ученик
1.	Abab	Abab
2.	ба	Abab+ба
3.	баба	Abab+ба+баба
4.	ба	Abab+ба+баба
5.	баба	Abab+ба+баба
6.	Abab	Abab+ба+баба
7.	ε	Abab+ба+баба+ ε
	...	...

1. Текстовое представление
	Учитель	Ученик
1.	Abab	Abab
2.	баба	Abab+баба
3.	баабаб	(б+ ε) (ab)^*
4.	баабаб	(б+ ε) (ab)^+баабаб*
5.	Abbaabba	(ab)^(ба)^(ab)^(ба)^
6.	бааббааб	(ab+ба)^*
7.	бабаба	(ab+ба)^*
	...	...

Поучительно посмотреть на конкретные примеры (в таблицах) учебных занятий, о которых говорит определение идентификации в пределе.

Вымышленный сеанс для изучения обычный язык L над алфавит {а,б} из текстовое представление. На каждом шаге учитель дает строку, принадлежащую L, и ученик отвечает на предположение для L, закодированный как регулярное выражение.^{[примечание 1]} В ногу 3, предположение учащегося не согласуется со строками, которые мы видели до сих пор; в ногу 4, учитель дает строку повторно. После шага 6, учащийся придерживается регулярного выражения (ab+ба)^*. Если это описание языка L учитель имеет в виду, говорят, что ученик выучил этот язык. Если бы существовала компьютерная программа для роли учащегося, которая могла бы успешно изучать каждый обычный язык, этот класс языков был бы идентифицируемый в пределе. Голд показал, что это не так.^[4]
Определенный алгоритм обучения всегда угадывать L быть справедливым объединение всех струн, замеченных до сих пор. Если L является конечным языком, учащийся в конечном итоге угадывает его правильно, но не знает, когда. Хотя догадка не изменилась во время шага 3 к 6, учащийся не мог быть уверен, что он прав. Голд показал, что класс конечных языков идентифицируем в пределе^[5] однако этот класс нельзя идентифицировать ни по конечному результату, ни по фиксированному времени.
Учиться у закончить презентацию, рассказав. На каждом шаге учитель дает строку и сообщает, принадлежит ли она L (зеленый) или нет (~~красный, зачеркнутый~~). Каждая возможная строка в конечном итоге классифицируется учителем таким образом.
Учиться у полная презентация по запросу. Ученик дает строку запроса, учитель сообщает, принадлежит ли она L (да) или нет (нет); затем ученик дает предположение для L, за которым следует следующая строка запроса. В этом примере учащийся на каждом этапе запрашивает ту же строку, что и учитель в примере 3. В целом, Голд показал, что каждый языковой класс, идентифицируемый в настройке запроса-презентации, также идентифицируется в говорящей презентации. параметр,^[6] так как учащийся, вместо того, чтобы запрашивать строку, просто должен подождать, пока она в конечном итоге не будет дана учителем.

Характеристика обучаемости

Дана Англуин дал характеристики обучаемости по тексту (положительная информация) в статье 1980 года.^[7]Если ученик должен быть эффективный, то индексированный класс рекурсивные языки обучается в пределе, если существует эффективная процедура, которая равномерно перечисляет рассказывать сказки для каждого языка в классе (Условие 1).^[8] Нетрудно увидеть, что если разрешен идеальный ученик (то есть произвольная функция), то индексированный класс языков можно изучить в пределе, если каждый язык в классе имеет контрольный сигнал (Условие 2).^[9]

Языковые классы доступны для изучения в пределе

Разделительные линии между идентифицируемыми и неидентифицируемыми языковыми классами^[10]
Модель обучаемости	Класс языков
Аномальное представление текста^{[заметка 2]}
	Рекурсивно перечислимый
	Рекурсивный
Полная презентация
	Примитивно рекурсивный^{[заметка 3]}
	Контекстно-зависимый
	Без контекста
	Обычный
	Сверхконечный^{[примечание 4]}
Обычное текстовое представление^{[примечание 5]}
	Конечный
	Синглтон^{[примечание 6]}

В таблице показано, какие языковые классы идентифицируются в рамках той или иной модели обучения. Справа каждый языковой класс является суперклассом всех низших классов. Каждая модель обучения (т. Е. Тип презентации) может идентифицировать в пределе все классы ниже нее. В частности, класс конечных языков в пределе идентифицируется текстовым представлением (см. Пример 2 над ), а класс обычных языков - нет.

Языки шаблонов, представленный Даной Англуин в другой статье 1980 г.,^[11] также можно определить по обычному текстовому представлению; они опущены в таблице, так как они находятся выше одноэлементного и ниже примитивного рекурсивного языкового класса, но несопоставимы с классами между ними.^{[примечание 7]}^{[требуется разъяснение ]}

Достаточные условия для обучаемости

Условие 1 в статье Англюина^[8] не всегда легко проверить. Поэтому люди придумывают различные достаточные условия для усвоения языкового класса. Смотрите также Индукция обычных языков для обучаемых подклассов обычных языков.

Конечная толщина

Класс языков имеет конечная толщина если каждый непустой набор строк содержится не более чем в конечном числе языков класса. Это в точности Условие 3 в статье Англюина.^[12] Англуин показал, что если класс рекурсивные языки имеет конечную толщину, то его можно обучить в пределе.^[13]

Класс конечной толщины заведомо удовлетворяет MEF-состояние и MFF-состояние; другими словами, конечная толщина подразумевает M-конечная толщина.^[14]

Конечная эластичность

Говорят, что класс языков имеет конечная эластичность если для каждой бесконечной последовательности строк ${ displaystyle s_ {0}, s_ {1}, ...}$ и каждая бесконечная последовательность языков в классе ${ displaystyle L_ {1}, L_ {2}, ...}$ , существует конечное число n такое, что ${ displaystyle s_ {n} not in L_ {n}}$ подразумевает ${ displaystyle L_ {n}}$ несовместимо с ${ displaystyle {s_ {1}, ..., s_ {n-1} }}$ .^[15]

Показано, что класс рекурсивно перечислимый языки можно изучать в пределе, если они имеют конечную эластичность.

Граница изменения разума

Ограничение количества изменений гипотез, которые происходят до сходимости.

Другие концепции

Бесконечное перекрестное свойство

Язык L имеет бесконечное перекрестное свойство в классе языков ${ Displaystyle { mathcal {L}}}$ если есть бесконечная последовательность ${ displaystyle L_ {i}}$ различных языков в ${ Displaystyle { mathcal {L}}}$ и последовательность конечного подмножества ${ displaystyle T_ {i}}$ такой, что:

${ displaystyle T_ {1} subset T_ {2} subset ...}$ ,
${ displaystyle T_ {i} in L_ {i}}$ ,
${ Displaystyle T_ {я + 1} not in L_ {я}}$ , и
${ Displaystyle lim _ {п = infty} T_ {я} = L}$ .

Обратите внимание, что L не обязательно является членом класса языка.

Нетрудно увидеть, что если в классе языков существует язык с бесконечным перекрестным свойством, то этот класс языков имеет бесконечную эластичность.

Отношения между концепциями

Конечная толщина подразумевает конечную эластичность;^[14]^[16] обратное неверно.
Конечная эластичность и консервативно изучаемый подразумевает наличие ограниченного изменения ума. [1]
Конечная эластичность и M-конечная толщина подразумевает наличие ограниченного изменения ума. Однако, M-конечная толщина само по себе не подразумевает существования ограниченного изменения ума; и существование изменения ума не подразумевает M-конечная толщина. [2]
Существование границы изменения ума предполагает обучаемость; обратное неверно.
Если мы допускаем невычислимых учеников, то конечная эластичность подразумевает существование границы изменения мышления; обратное неверно.
Если нет порядок накопления для класса языков существует язык (не обязательно в классе), обладающий бесконечным перекрестным свойством внутри класса, что, в свою очередь, подразумевает бесконечную эластичность класса.

Открытые вопросы

Если у счетного класса рекурсивных языков есть предел изменения мышления для невычислимых учащихся, имеет ли класс также ограничение изменения разума для вычислимых учащихся, или этот класс не выучит вычислимый учащийся?

Заметки

^ "А+B"содержит все строки, которые находятся в А или в B; "AB"содержит все конкатенации строки в А со шнурком в B; "А^*"содержит все повторения (ноль или более раз) строк в А; «ε» обозначает пустую строку; «а» и «б» обозначают сами себя. Например, выражение "(ab+ба)^*"на шаге 7 обозначает бесконечное множество {ε, ab, ba, abab, abba, baab, baba, ababab, ababba, ...}.
^ т.е. текстовое представление, где строка, данная учителем, является примитивная рекурсивная функция текущего номера шага, и учащийся кодирует предположение о языке как программа, которая перечисляет язык
^ т.е. класс языков, которые разрешимый от примитивно рекурсивный функции
^ т.е. содержащий все конечные языки и хотя бы один бесконечный
^ то есть текстовое представление, за исключением настройки аномального представления текста
^ т.е. класс языков, состоящий из одной строки (они упоминаются здесь только как общая нижняя граница для конечных языков и языков шаблонов)
^ несравнимый с классом обычного и контекстно-свободного языка: Теорема 3.10, стр.53