PROFILPELAJAR.COM

Индукция грамматики (или грамматический вывод^[1]) — процедура машинного обучения, которая восстанавливает формальную грамматику языка на основе набора наблюдений (примеров) с известной принадлежностью этому языку. В результате процедуры строится модель наблюдаемых объектов в виде набора правил вывода или порождающих правил^[англ.], конечного автомата или автомата другого вида. В более общем смысле, грамматический вывод — это одно из направлений машинного обучения, в котором пространство примеров состоит из дискретных комбинаторных объектов, таких как строки, деревья, графы.

Классы грамматик

Грамматический вывод часто фокусируется на задаче обучения конечных автоматов различного типа (см. статью Индукция регулярных языков^[англ.] о деталях этих подходов), поскольку существуют эффективные алгоритмы решения этой задачи с 1980-х годов.

С начала 2000-х эти подходы были распространены на задачу вывода контекстно-свободных грамматик и более богатых формализмов, таких как множественных контекстно-свободных грамматик и параллельных множественных контекстно-свободных грамматик. Другие классы грамматик, для которых изучался грамматический вывод изучался и для других классов грамматик — контекстуальных грамматик и языков образцов (англ. pattern language).

Модели обучения

Простейший вид обучения — это когда алгоритм обучения получает лишь набор примеров, а иногда и контрпримеров, слов рассматриваемого языка. Существуют и другие модели обучения. Одной из часто изучаемых альтернатив является случай, когда обучающийся может спрашивать о принадлежности слова языку как, например, в модели точного обучения или минимальной адекватной модели учителя (англ. minimally adequate teacher model), которую ввела Англуин^[2].

Методологии

Разработано большое разнообразие методов для грамматического вывода. Два классических источника — статьи Фу 1977 года^[3] и 1982 года^[4]. Дуда, Харт и Сторк^[5] также посвятили небольшой раздел этой проблеме и цитируют много источников. Базовый метод проб и ошибок, который они представили, обсуждается ниже. Для подходов по выводу подклассов регулярных языков, в частности, см. Индукция регулярных языков^[англ.]. Более свежей книгой является книга де ла Хигеры (2010)^[1], в которой освещается теория грамматического вывода регулярных языков и конечных автоматов. Д’Улизия, Ферри и Грифони^[6] дали обзор исследований по методам грамматического вывода для естественных языков.

Грамматический вывод методом проб и ошибок

Метод, предложенный в разделе 8.7 статьи Дауда, Харта и Сторка^[5], предлагает последовательное угадывание грамматических правил и проверки их на положительных и отрицательных наблюдениях. Набор правил расширяется так, чтобы можно было сгенерировать каждый положительный пример, но если данный набор правил генерирует отрицательный пример, он должен быть отброшен. Этот конкретный подход можно охарактеризовать, как «проверка гипотезы», представляет собой некоторое подобие алгоритма Митчела версионного пространства^[англ.]. Текст статьи Дауда, Харта и Сторка^[5] даёт простой пример, который хорошо иллюстрирует процесс, но выполнимость такого неуправляемого подхода проб и ошибок для более крупных задач сомнительна.

Грамматический вывод с помощью генетических алгоритмов

Грамматический вывод с помощью эволюционных алгоритмов является процессом эволюции представления грамматики целевого языка посредством некоторого эволюционного процесса. Формальные грамматики могут легко быть представлены как деревья правил вывода, к которым могут быть применены эволюционные операторы. Алгоритмы этого вида берут начало от генетического программирования, начало которому положил Джон Коза. Другие ранние работы по простым формальным языкам использовали бинарное строковое представление генетических алгоритмов, но внутренняя иерархическая структура грамматик, лежащая в основе языка расширенной формы Бэкуса — Наура, делает деревья более гибким подходом.

Коза представил программы языка Lisp как деревья. Он сумел найти аналогии среди генетических операторов стандартным операторам на деревьях. Например, обмен поддеревьев эквивалентен соответствующему процессу генетического кроссинговера, где подстроки генетического кода преобразуются в индивидуальность следующего поколения. Годность измеряется путём оценки выходного кода функции^[англ.] Lisp. Похожие аналогии между древесными структурами представлений языка Lisp и представлениями грамматик в виде деревьев, делают технику применения генетического программирования возможной для индукции грамматики.

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

Грамматический вывод с помощью жадных алгоритмов

Подобно всем жадным алгоритмам, жадные алгоритмы грамматического вывода принимают в итеративной манере решение, которое кажется лучшим на данном этапе. Под решением обычно понимают создание нового правила, удаление существующего правила, выбор применяемого правила, слияние существующих правил. Поскольку понятия «этап» и «лучший» можно определить по-разному, создано несколько алгоритмов жадного грамматического вывода.

Следующие алгоритмы порождения контекстно-свободных грамматик принимают решение после каждого прочитанного символа:

Алгоритм Лемпеля — Зива — Велча создаёт контекстно-свободную грамматику детерминировано, так что необходимо запоминать лишь стартовое правило генерируемой грамматики.
Sequitur^[англ.] и его модификации.

Следующие алгоритмы генерации контекстно-свободных грамматик сначала читают всю последовательность символов, а затем начинают принимать решения:

Кодирование пар байтов^[англ.] и его оптимизированные варианты.

Дистрибутивное обучение

Более свежие подходы основываются на дистрибутивном обучении^[англ.]. Алгоритмы, использующие эти подходы, были применены к обучению контекстно-свободным грамматикам и слегка контекстно-зависимым языкам^[англ.], и была доказана их корректность и эффективность для больших подклассов этих грамматик^[7]^[8]

Обучение языкам образцов^[англ.]

Англуин определила образец как «строку постоянных символов из алфавита Σ и переменных символов из непересекающегося множества». Язык таких образцов является набором всех непустых основных примеров, то есть всех строк, получающихся соответствующей заменой переменных символов непустыми строками постоянных символов^{[note 1]}. Образец называется описательным для конечного набора строк, если его язык минимален (учитывая включение множеств) среди всех языков образцов, включая входное множество.

Англуин дала полиномиальный алгоритм для вычисления из заданного входного множества строк всех описательных образцов от одной переменной x^{[note 2]}. С этой целью она строит автомат, представляющий все возможные относящиеся к делу образцы. Используя изощрённые аргументы о длинах слов, которые зависят только от единственной переменной x, число состояний может быть значительно сокращено^[9].

Эрлебах с сотрудниками дал более эффективную версию алгоритма Англуин обучения образцам, а также параллельную версию алгоритма^[10].

Аримура и др. показали, что класс языков, полученный из ограниченного объединения образцов, может быть обучен за полиномиальное время^[11].

Теория образцов

Теория образцов^[англ.] (англ. pattern theory), сформулированная Ульфом Гренандером^[12], является математическим формализмом для описания знаний о мире в виде образцов. Отличием предложенного подхода к искусственному интеллекту от других состоит в том, что он начинается не с определения алгоритмов и машин для распознавания и классификации образов. Скорее, метод предписывает словарь для формулирования и переписывания образцов на точном языке.

Вдобавок к новому алгебраическому языку, новый статистический подход был введён с целью:

Распознавания скрытых переменных набора данных, используя данные реального мира, а не искусственных воздействий.
Определения априорного распределения скрытых переменных и модели для наблюдаемых переменных, которые образуют вершины графа, подобного графу Гиббса.
Изучения случайности и вариативности этих графов.
Создания базовых классы стохастических моделей, применяемых путём перечисления деформаций^{[неизвестный термин]} образцов.
Осуществления синтеза (сэмплирования) с помощью моделей, а не только изучение сигналов

Приложения

Принципы индукции грамматики были применены у другим аспектам обработки естественного языка, и (среди многих других задач) к восприятию естественного языка^[англ.]^[13], машинному переводу на основе примеров ^[14], анализе морфем и вывода происхождения названий мест. Индукция грамматики использовалась также для сжатия без потерь^[15] и статистического вывода через принципы сообщений минимальной длины и описаний минимальной длины. Индукция грамматики использовалась также в некоторых вероятностных моделях освоения языка^[англ.]^[16].

См. также

Примечания

↑ Язык образов с по меньшей мере двумя вхождениями той же самой переменной не является регулярным вследствие леммы о накачке.
↑ x может встретиться несколько раз, но не должно быть какой-либо другой переменной y

↑ ¹ ² de la Higuera, 2010.
↑ Angluin, 1987, с. 87–106.
↑ Fu, 1977.
↑ Fu, 1982.
↑ ¹ ² ³ Duda, Hart, Stork, 2001.
↑ D’Ulizia, Ferri, Grifoni, 2011, с. 1–27.
↑ Clark, Eyraud, 2007.
↑ Yoshinaka, 2011, с. 1821—183.
↑ Angluin, 1980, с. 46–62.
↑ Erlebach, Rossmanith, Stadtherr, Steger, Zeugmann, 1997, с. 260–276.
↑ Arimura, Shinohara, Otsuki, 1994, с. 649–660.
↑ Grenander, Miller, 2007.
↑ Miller, Bobrow, Schwartz, 1994.
↑ Brown, 2001.
↑ Cherniavsky, Ladner, 2004.
↑ Chater, Manning, 2006, с. 335—344.

Литература

Colin de la Higuera. Grammatical Inference: Learning Automata and Grammars. — Cambridge: Cambridge University Press, 2010.
Ulf Grenander, Michael I. Miller. Pattern theory: from representation to inference. — Oxford university press, 2007. — ISBN 0–19–850570–1.
Alexander Clark, Rémi Eyraud. Polynomial Identification in the Limit of Substitutable Context-free Languages // Journal of Machine Learning Research. — 2007.
Ryo Yoshinaka. Efficient learning of multiple context-free languages with multidimensional substitutability from positive data // Theoretical Computer Science. — 2011. — Т. 412, вып. 19. — С. 1821—1831.
Scott Miller, Robert J. Bobrow, Richard M. Schwartz. Hidden understanding models of natural language // Proceedings of the 32nd annual meeting on Association for Computational Linguistics.. — Association for Computational Linguistics, 1994.
Ralf D. Brown. Transfer-rule induction for example-based translation // Proceedings of the MT Summit VIII Workshop on Example-Based Machine Translation. — 2001.
Neva Cherniavsky, Richard Ladner. Grammar-based compression of DNA sequences // DIMACS Working Group on The Burrows-Wheeler Transform. — 2004.
Nick Chater, Christopher D. Manning. Probabilistic models of language processing and acquisition // Trends in cognitive sciences. — 2006.
Dana Angluin. Learning Regular Sets from Queries and Counter-Examples // Information and Control. — 1987. — Т. 75. — С. 87–106. — doi:10.1016/0890-5401(87)90052-6. Архивировано 2 декабря 2013 года.
D’Ulizia A., Ferri F., Grifoni P. A Survey of Grammatical Inference Methods for Natural Language Learning // Artificial Intelligence Review. — 2011. — Т. 36, № 1.
Dana Angluin. Finding Patterns Common to a Set of Strings // Journal of Computer and System Sciences. — 1980. — Т. 21. — doi:10.1016/0022-0000(80)90041-0.
Erlebach T., Rossmanith P., Stadtherr H., Steger A., Zeugmann T. Learning One-Variable Pattern Languages Very Efficiently on Average, in Parallel, and by Asking Queries // Proc. 8th International Workshop on Algorithmic Learning Theory — ALT'97 / M. Li, A. Maruoka. — Springer, 1997. — Т. 1316. — (LNAI).
Hiroki Arimura, Takeshi Shinohara, Setsuko Otsuki. Finding Minimal Generalizations for Unions of Pattern Languages and Its Application to Inductive Inference from Positive Data // Proc. STACS 11. — Springer, 1994. — Т. 775. — (LNCS).
Richard O. Duda, Peter E. Hart, David G. Stork. Pattern Classification. — 2. — New York: John Wiley & Sons, 2001.
King Sun Fu. Syntactic Pattern Recognition and Applications. — Englewood Cliffs, NJ: Prentice-Hall, 1982.
King Sun Fu. Syntactic Pattern Recognition, Applications. — Berlin: Springer-Verlag, 1977.
James Jay Horning. A Study of Grammatical Inference. — Stanford: Stanford University Computer Science Department, 1969. — (Ph.D. Thesis).
E. Mark Gold. Language Identification in the Limit. — Information and Control, 1967. — Т. 10. — С. 447–474. Архивировано 28 августа 2016 года.

[9] Язык образов с по меньшей мере двумя вхождениями той же самой переменной не является регулярным вследствие леммы о накачке.

[10] x может встретиться несколько раз, но не должно быть какой-либо другой переменной y

[_ea471dc2298a22ff-1] ¹ ² de la Higuera, 2010.

[_865b1e20f1e82cd9-2] Angluin, 1987, с. 87–106.

[_ab3920d90a6c0ecc-3] Fu, 1977.

[_f9ac67ac8ba2d510-4] Fu, 1982.

[_95bd5f59ab8cb150-5] ¹ ² ³ Duda, Hart, Stork, 2001.

[_2fc8a617ff82cf2d-6] D’Ulizia, Ferri, Grifoni, 2011, с. 1–27.

[_051686d5c22024f9-7] Clark, Eyraud, 2007.

[_a6b290ee6f6b2018-8] Yoshinaka, 2011, с. 1821—183.

[_16ffceef5412468c-11] Angluin, 1980, с. 46–62.

[_bd131ffe6385d2c7-12] Erlebach, Rossmanith, Stadtherr, Steger, Zeugmann, 1997, с. 260–276.

[_9ae33fa3fff695d1-13] Arimura, Shinohara, Otsuki, 1994, с. 649–660.

[_61ce11cf7b3355e7-14] Grenander, Miller, 2007.

[_b3ead8d232d3c0f6-15] Miller, Bobrow, Schwartz, 1994.

[_8b1fda58e4584ed8-16] Brown, 2001.

[_9d48dea180a170a0-17] Cherniavsky, Ladner, 2004.

[_91ae60ac8ad91af8-18] Chater, Manning, 2006, с. 335—344.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[note 1]

[note 2]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]