Индукция грамматики (или грамматический вывод[1]) — это процесс в машинном обучении для обучения формальной грамматике (обычно в виде набора правил вывода или порождающих правил[en] или, альтернативно, как конечный автомат или автомат другого вида) из набора наблюдений, то есть построение модели, которая описывает наблюдаемые объекты. Более обще, грамматический вывод — это такая ветвь машинного обучения, в которой пространство примеров состоит из дискретных комбинаторных объектов, таких как строки, деревья и графы.
Грамматический вывод часто фокусируется на задаче обучения конечных автоматов различного типа (см. статью Индукция регулярных языков[en] о деталях этих подходов), поскольку существуют эффективные алгоритмы решения этой задачи с 1980-х годов.
С начала столетия эти подходы были распространены на задачу вывода контекстно-свободных грамматик и более богатые формализмы, такие как множественные контекстно-свободные грамматики и параллельные множественные контекстно-свободные грамматики. Другие классы грамматик, для которых изучался грамматический вывод,— это контекстуальные грамматики и языки образов.
Простейший вид обучения — это когда алгоритм обучения получает лишь набор примеров, получаемый из рассматриваемого языка — целью является изучение языка по его примерам (и, более редко, из контрпримеров, то есть примеров, не принадлежащих языку). Однако изучались и другие модели обучения. Одной из часто изучаемых альтернатив является случай, когда обучающийся может выдать запрос принадлежности как в модели точного обучения или минимальная адекватная модель учителя, которую ввела Англуин[2].
Есть большое разнообразие методов для грамматического вывода. Два классических источника — статьи Фу 1977 года[3] и 1982 года[4]. Дуда, Харт и Сторк[5] также посвятили небольшой раздел этой проблеме и цитируют много источников. Базовый метод проб и ошибок, который они представили, обсуждается ниже. Для подходов по выводу подклассов регулярных языков, в частности, см. Индукция регулярных языков[en]. Более свежей книгой является книга де ла Хигеры (2010)[1], в которой освещается теория грамматического вывода регулярных языков и конечных автоматов. Д'Улизия, Ферри и Грифони[6] дали обзор исследований по методам грамматического вывода для естественных языков.
Метод, предложенный в секции 8.7 статьи Дауда, Харта и Сторка[5], предлагает последовательное угадывание грамматических правил и проверки их на положительных и отрицательных наблюдениях. Набор правил расширяется так, чтобы можно было сгенерировать каждый положительный пример, но если данный набор правил генерирует отрицательный пример, он должен быть отброшен. Этот конкретный подход можно охарактеризовать, как «проверка гипотезы», представляет собой некоторое подобие алгоритма Митчела версионного пространства[en]. Текст статьи Дауда, Харта и Сторка[5] даёт простой пример, который хорошо иллюстрирует процесс, но выполнимость такого неуправляемого подхода проб и ошибок для более крупных задач сомнительна.
Грамматический вывод с помощью эволюционных алгоритмов является процессом эволюции представления грамматики целевого языка посредством некоторого эволюционного процесса. Формальные грамматики могут легко быть представлены как деревья правил вывода, к которым могут быть применены эволюционные операторы. Алгоритмы этого вида берут начало от генетического программирования, начало которому положил Джон Коза. Другие ранние работы по простым формальным языкам использовали бинарное строковое представление генетических алгоритмов, но внутренняя иерархическая структура грамматик, лежащая в основе языка расширенной формы Бэкуса — Наура, делает деревья более гибким подходом.
Коза представил программы языка Lisp как деревья. Он сумел найти аналогии среди генетических операторов стандартным операторам на деревьях. Например, обмен поддеревьев эквивалентен соответствующему процессу генетического кроссинговера, где подстроки генетического кода преобразуются в индивидуальность следующего поколения. Годность измеряется путём оценки выходного кода функции[en] Lisp. Похожие аналогии между древесными структурами представлений языка lisp и представлениями грамматик в виде деревьев, делают технику применения генетического программирования возможной для индукции грамматики.
В случае индукции грамматики, перенесение поддеревьев соответствует обмену правил вывода, что даёт возможность разбора фраз некоторого языка. Оператор годности для грамматики основывается на некоторой мере, как хорошо она разбирает некоторую группу предложений из целевого языка. В представлении грамматики в виде дерева терминальный символ производящего правила соответствует листу дерева. Его родительский узел соответствует нетерминальному символу (например, именной группе или глагольной группе) в наборе правил. В конце концов, корневой узел может соответствовать последовательности нетерминальных.
Подобно всем жадный алгоритмам, жадные алгоритмы грамматического вывода принимают в итеративной манере решение, которое кажется лучшим на данном этапе. Решения обычно имеют дело с такими вещами, как создание нового правила, удаление существующего правила, выбор применяемого правила, или слияния некоторых существующих правил. Поскольку понятия «этап» и «лучший» можно определить по-разному, есть несколько алгоритмов жадного грамматического вывода.
Следующие алгоритмы генерации контекстно-свободных грамматик принимают решение после каждого прочитанного символа:
Следующие алгоритмы генерации контекстно-свободных грамматик сначала читают всю последовательность символов, а затем начинают принимать решения:
Более свежие подходы основываются на дистрибутивном обучении. Алгоритмы, использующие эти подходы, были применены к обучению контекстно-свободным грамматикам и слегка контекстно-зависимым языкам[en] и была доказана их корректность и эффективность для больших подклассов этих грамматик[7][8]
Англуин определила образ как «строку постоянных символов из алфавита Σ и переменных символов из непересекающегося множества». Язык таких образов является набором всех непустых основных примеров, то есть всех строк, получающихся from consistent замены переменных символов непустыми строками постоянных символов [note 1]. Образ называется описательным для конечного набора строк, если его язык минимален (учитывая включение множеств) среди всех языков образов, включая входное множество.
Англуин дала полиномиальный алгоритм для вычисления, для заданного входного множества строк, всех описательных образов от одной переменной x[note 2]. С этой целью она строит автомат, представляющий все возможные относящиеся к делу образы. Используя изощрённые аргументы о длинах слов, которые зависят только от единственной переменной x, число состояний может быть значительно сокращено[9].
Эрлебах с сотрудниками дал более эффективную версию алгоритма Англуин обучения образам, а также версия с возможностью распараллеливания[10].
Аримура и др. Показали, что класс языков, полученный из ограниченного объединения образов, может быть обучен за полиномиальное время[11].
Теория образов[en], сформулированная Ульфом Гренандером[12], является математическим формализмом для описания знаний о мире как образов. Это отличается от другого подхода к искусственному интеллекту в том, что он не начинается прописывания алгоритмов и машины для распознавания и классификации образов. Скорее, алгоритм предписывает словарь связки и изменения образа в точном языке.
Вдобавок к новому алгебраическому языку, новый статистический подход был введён с целью:
Принципы индукции грамматики были применены у другим аспектам обработки естественного языка, и (среди многих других задач) к восприятию естественного языка[en][13], машинному переводу на основе примеров [14], анализе морфем и вывода происхождения названий мест. Индукция грамматики использовалась также для сжатия без потерь[15] and статистического вывода через принципы сообщений минимальной длины и описаний минимальной длины. Индукция грамматики использовалась также в некоторых вероятностных моделях освоения языка[en][16].
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .