Идентификация в пределе: формальная модель индуктивного вывода языков.

Введение

Идентификация языка в пределе — это формальная модель индуктивного вывода формальных языков, в основном с помощью компьютеров (см. машинное обучение и индукция регулярных языков). Она была представлена Э. Марком Голдом в техническом отчете и статье в журнале с тем же названием. В этой модели учитель предоставляет учащемуся некоторую презентацию (то есть последовательность строк) некоторого формального языка. Обучение рассматривается как бесконечный процесс. Каждый раз, когда учащийся читает элемент презентации, он должен предлагать гипотезу (например, формальную грамматику) для языка. Голд определяет, что учащийся может идентифицировать в пределе класс языков, если для любой презентации любого языка из этого класса учащийся будет выдавать лишь конечное число неверных гипотез, а затем остановится на правильной. Однако учащийся не обязан подтверждать правильность своей гипотезы, и учитель может привести контрпример к любой гипотезе спустя произвольно долгое время. Голд определил два типа презентаций: текст (позитивная информация): перечисление всех строк, составляющих язык; полная презентация (позитивная и негативная информация): перечисление всех возможных строк, каждая из которых снабжена меткой, указывающей, принадлежит ли строка языку или нет.

Примеры

+ 4. Полное представление по запросу Учитель Ученик Угадывание Запрос 0. abab 1. abab 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)*

Полезно рассмотреть конкретные примеры (в таблицах) обучающих сессий, о которых говорит определение идентификации в пределе. Фиктивная сессия для изучения регулярного языка L над алфавитом {a,b} из текстового представления: На каждом шаге учитель предоставляет строку, принадлежащую 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 в работе Англуина показало, что если класс рекурсивных языков имеет конечную толщину, то он обучаем в пределе. Класс с конечной толщиной, безусловно, удовлетворяет условию MEF и условию MFF; иными словами, конечная толщина подразумевает конечность толщины M.

Определенная эластичность

Класс языков называется обладающим конечной эластичностью, если для каждой бесконечной последовательности строк и каждой бесконечной последовательности языков в этом классе существует конечное число n, такое что влечет за собой несовместимость, и обратное неверно. Конечная эластичность и консервативное обучение подразумевают существование границы изменения мнения. Конечная эластичность и M-конечная толщина подразумевают существование границы изменения мнения. Однако, одна лишь M-конечная толщина не подразумевает существование границы изменения мнения, равно как и существование границы изменения мнения не подразумевает M-конечную толщину. Существование границы изменения мнения подразумевает обучаемость, но обратное неверно. Если мы допускаем невычислимых обучающихся, то конечная эластичность подразумевает существование границы изменения мнения, и обратное неверно. Если для класса языков отсутствует порядок накопления, то существует язык (не обязательно принадлежащий классу), обладающий бесконечным кросс-свойством внутри класса, что, в свою очередь, подразумевает бесконечную эластичность класса.