Войти
Грамматическая индукция (или грамматический вывод ) - это процесс в машинном обучении изучения формальной грамматики (обычно в виде набора переписанных rules или продукции или, альтернативно, как конечный автомат или aut omaton) из набора наблюдений, тем самым создавая модель, которая учитывает характеристики наблюдаемых объектов. В более общем смысле, грамматический вывод - это та ветвь машинного обучения, где пространство экземпляров состоит из дискретных комбинаторных объектов, таких как строки, деревья и графы.
Грамматический вывод часто был очень сфокусирован на проблеме обучения конечных автоматов различных типов (см. Статью Индукция регулярных языков для подробностей об этих подходах), поскольку были эффективными алгоритмами решения этой проблемы с 1980-х годов.
С начала века эти подходы были расширены на проблему вывода контекстно-свободных грамматик и более обширных формализмов, таких как множественные контекстно-свободные грамматики и параллельные множественные контекстные- бесплатные грамматики. Другими классами грамматик, для которых изучался грамматический вывод, являются комбинаторно-категориальные грамматики, стохастические контекстно-свободные грамматики, контекстные грамматики и языки шаблонов.
Самая простая форма обучения - это когда алгоритм обучения просто получает набор примеров, взятых из рассматриваемого языка: цель состоит в том, чтобы изучить язык на его примерах (и, редко, из контрпримеров, то есть примеров, не относящихся к языку). Однако были изучены и другие модели обучения. Одной из часто изучаемых альтернатив является случай, когда учащийся может задавать вопросы о членстве, как в модели обучения с точным запросом или в минимально адекватной модели учителя, представленной Англуином.
Существует большое разнообразие методов для грамматического вывода. Два классических источника: Fu (1977) и Fu (1982). Дуда, Харт и Сторк (2001) также посвятили этой проблеме краткий раздел и процитировали ряд ссылок. Предлагаемый ими основной метод проб и ошибок обсуждается ниже. О подходах к выводу подклассов обычных языков, в частности, см. Индукция регулярных языков. Более поздним учебником является de la Higuera (2010), который охватывает теорию грамматического вывода регулярных языков и конечных автоматов. Д'Улиция, Ферри и Грифони проводят обзор, в котором исследуются методы грамматического вывода для естественных языков.
Метод, предложенный в разделе 8.7 документа Duda, Hart Stork (2001), предлагает последовательно угадывать правила грамматики (продукции) и проверка их на положительные и отрицательные наблюдения. Набор правил расширяется, чтобы иметь возможность генерировать каждый положительный пример, но если данный набор правил также генерирует отрицательный пример, он должен быть отброшен. Этот конкретный подход может быть охарактеризован как «проверка гипотез» и имеет некоторое сходство с алгоритмом пространства версий Митчела. Текст Duda, Hart Stork (2001) предоставляет простой пример, который хорошо иллюстрирует процесс, но возможность такого неуправляемого подхода методом проб и ошибок для решения более серьезных проблем сомнительна.
Грамматическая индукция с использованием эволюционных алгоритмов - это процесс развития представления грамматики целевого языка посредством некоторого эволюционного процесса. Формальные грамматики могут быть легко представлены как древовидные структуры производственных правил, которые могут подвергаться эволюционным операторам. Алгоритмы этого типа происходят из парадигмы генетического программирования, впервые предложенной Джоном Козой. В других ранних работах над простыми формальными языками использовалось двоичное строковое представление генетических алгоритмов, но изначально иерархическая структура грамматик, сформулированная в языке EBNF, сделала деревья более гибким подходом.
Коза представил программы Lisp в виде деревьев. Он смог найти аналоги генетическим операторам в стандартном наборе древовидных операторов. Например, замена поддеревьев эквивалентна соответствующему процессу генетического кроссовера, при котором подстроки генетического кода трансплантируются в особь следующего поколения. Пригодность измеряется путем подсчета результатов функций кода Lisp. Подобные аналоги между древовидным представлением Lisp и представлением грамматик в виде деревьев сделали возможным применение методов генетического программирования для индукции грамматики.
В случае введения в грамматику трансплантация поддеревьев соответствует замене правил производства, которые позволяют анализировать фразы из некоторого языка. Оператор пригодности для грамматики основан на некоторой мере того, насколько хорошо он выполнял синтаксический анализ некоторой группы предложений из целевого языка. В древовидном представлении грамматики конечный символ производственного правила соответствует конечному узлу дерева. Его родительские узлы соответствуют нетерминальному символу (например, именная фраза или глагольная фраза ) в наборе правил. В конечном итоге корневой узел может соответствовать нетерминальному предложению.
Как и все жадные алгоритмы, жадные алгоритмы грамматического вывода принимают итеративным образом решения, которые кажутся лучшими на данном этапе. Принимаемые решения обычно касаются таких вещей, как создание новых правил, удаление существующих правил, выбор правила, которое будет применяться, или слияние некоторых существующих правил. Поскольку существует несколько способов определить «стадию» и «лучший», существует также несколько жадных алгоритмов вывода грамматики.
Эти алгоритмы создания контекстно-свободной грамматики принимают решение после каждого символа чтения:
Эти контекстно-свободные алгоритмы генерации грамматики сначала читают всю данную последовательность символов, а затем начинают принимать решения :
Более современный подход основан на распределенном обучении. Алгоритмы, использующие эти подходы, применялись для изучения контекстно-свободных грамматик и умеренно контекстно-зависимых языков и оказались правильными и эффективными для больших подклассов этих грамматик.
Angluin определяет шаблон как «строку постоянных символов из Σ и переменных символов из непересекающегося набора». Язык такого шаблона - это набор всех его непустых основных экземпляров, то есть всех строк, полученных в результате последовательной замены его переменных символов непустыми строками постоянных символов. Шаблон называется описательным для конечного входного набора строк, если его язык минимален (относительно включения набора) среди всех языков шаблонов, входящих в набор входных данных.
Angluin дает полиномиальный алгоритм для вычисления для заданного набора входных строк всех описательных шаблонов в одной переменной x. С этой целью она строит автомат, представляющий все возможные подходящие шаблоны; используя сложные аргументы о длине слова, которые полагаются на то, что x является единственной переменной, количество состояний может быть резко сокращено.
Erlebach et al. дают более эффективную версию алгоритма изучения паттернов Angluin, а также распараллеленную версию.
Arimura et al. показывают, что языковой класс, полученный из ограниченного объединения шаблонов, может быть изучен за полиномиальное время.
Теория шаблонов, сформулированная Ульфом Гренандером, является математическим формализм для описания познания мира в виде шаблонов. Он отличается от других подходов к искусственному интеллекту тем, что не начинается с предписания алгоритмов и механизмов для распознавания и классификации шаблонов; скорее, он предписывает словарный запас, чтобы сформулировать и преобразовать концепции шаблонов точным языком.
В дополнение к новому алгебраическому словарю, его статистический подход был новаторским с целью:
Широкий в своем математический охват, теория образов охватывает алгебру и статистику, а также локальные топологические и глобальные энтропийные свойства.
Принцип грамматической индукции применялся к другим аспектам обработки естественного языка, а также (среди многих других проблем) к семантике анализ, понимание естественного языка, перевод на основе примеров, анализ морфем и происхождение географических названий. Грамматическая индукция также использовалась для сжатия данных без потерь и статистического вывода с помощью минимальной длины сообщения (MML) и минимальной длины описания (MDL) принципы. Индукция грамматики также использовалась в некоторых вероятностных моделях овладения языком.
