Грамматическая индукция

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

Уроки грамматики [ править ]

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

С начала века эти подходы были распространены на проблему вывода контекстно-свободных грамматик и более богатых формализмов, таких как множественные контекстно-свободные грамматики и параллельные множественные контекстно-свободные грамматики.Другими классами грамматик, для которых изучался грамматический вывод, являются комбинаторные категориальные грамматики , ^[2] стохастические контекстно-свободные грамматики , ^[3] контекстуальные грамматики и языки шаблонов.

Модели обучения [ править ]

Самая простая форма обучения заключается в том, что алгоритм обучения просто получает набор примеров, взятых из рассматриваемого языка: цель состоит в том, чтобы изучить язык на его примерах (и, редко, на контрпримерах, то есть примерах, которые не принадлежит языку).Однако были изучены и другие модели обучения. Одной из часто изучаемых альтернатив является случай, когда учащийся может задавать вопросы членства, как в модели обучения с точными запросами или минимально адекватной модели учителя, представленной Angluin. ^[4]

Методологии [ править ]

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

Индукция вероятностных грамматик [ править ]

Существует несколько методов индукции вероятностных контекстно-свободных грамматик . ^[6]^[7]^{[ нужны дальнейшие объяснения ]}

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

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

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

Грамматическая индукция с использованием эволюционных алгоритмов — это процесс развития представления грамматики целевого языка посредством некоторого эволюционного процесса. Формальные грамматики можно легко представить в виде древовидных структур продукционных правил, которые можно подчинять эволюционным операторам. Алгоритмы такого рода берут начало в парадигме генетического программирования, впервые предложенной Джоном Коза . ^{[ нужна ссылка ]} В других ранних работах над простыми формальными языками использовалось бинарное строковое представление генетических алгоритмов, но иерархическая структура грамматик, заложенная в языке EBNF , сделала деревья более гибким подходом.

Коза представлял программы на Лиспе в виде деревьев. Ему удалось найти аналоги генетическим операторам в стандартном наборе операторов дерева. Например, замена поддеревьев эквивалентна соответствующему процессу генетического скрещивания, при котором подстроки генетического кода трансплантируются индивидууму следующего поколения. Пригодность измеряется путем оценки результатов функций кода Lisp. Подобные аналоги между древовидным представлением Lisp и представлением грамматик в виде деревьев сделали возможным применение методов генетического программирования для индукции грамматики.

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

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

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

Эти алгоритмы генерации контекстно-свободной грамматики принимают решение после каждого прочитанного символа:

Алгоритм Лемпеля-Зива-Уэлча создает контекстно-свободную грамматику детерминированным способом, так что необходимо хранить только начальное правило сгенерированной грамматики.
Секвитур и его модификации.

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

Кодирование пар байтов и его оптимизация.

обучение Распределительное

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

Изучение языков шаблонов [ править ]

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

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

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

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

Теория закономерностей [ править ]

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

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

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

Теория паттернов, широкая по своему математическому охвату, охватывает алгебру и статистику, а также локальные топологические и глобальные энтропийные свойства.

Приложения [ править ]

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

Алгоритмы сжатия [ править ]

Прямолинейная грамматика (с начальным символом ß) второго предложения Декларации независимости США . Каждый синий символ обозначает нетерминальный символ ; они были получены в результате gzip -сжатия предложения.

Коды на основе грамматики или сжатие на основе грамматики — это алгоритмы сжатия, основанные на идее создания контекстно-свободной грамматики (CFG) для сжимаемой строки. Примеры включают универсальные сжатия данных без потерь . алгоритмы ^[18] Сжатие последовательности данных $x=x_{1}\cdots x_{n}$ , код, основанный на грамматике, преобразует $x$ в контекстно-свободную грамматику $G$ .Задача нахождения наименьшей грамматики для входной последовательности ( самая маленькая грамматическая задача ), как известно, NP-трудна, ^[19] очень много алгоритмов грамматического преобразования предложено с теоретической и практической точек зрения.

Как правило, полученная грамматика

G

дополнительно сжимается статистическими кодировщиками, такими как арифметическое кодирование .

См. также [ править ]

Примечания [ править ]

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

Ссылки [ править ]

↑ Перейти обратно: Перейти обратно: ^а ^б де ла Игера, Колин (2010). Грамматический вывод: автоматы обучения и грамматики (PDF) . Кембридж: Издательство Кембриджского университета. Архивировано из оригинала (PDF) 14 февраля 2019 г. Проверено 16 августа 2017 г.
↑ Перейти обратно: Перейти обратно: ^а ^б Квятковски, Том и др. « Лексическое обобщение в индукции грамматики CCG для семантического анализа ». Материалы конференции по эмпирическим методам обработки естественного языка. Ассоциация компьютерной лингвистики , 2011.
^ Кларк, Александр. « Неконтролируемая индукция стохастических контекстно-свободных грамматик с использованием распределительной кластеризации ». Материалы семинара 2001 г. по компьютерному изучению естественного языка, том 7. Ассоциация компьютерной лингвистики, 2001.
^ Дана Англуин (1987). «Изучение регулярных наборов на основе запросов и контрпримеров» (PDF) . Информация и контроль . 75 (2): 87–106. CiteSeerX 10.1.1.187.9414 . дои : 10.1016/0890-5401(87)90052-6 . S2CID 11873053 . Архивировано из оригинала (PDF) 2 декабря 2013 г.
^ Д'Улиция, А., Ферри, Ф., Грифони, П. (2011) « Обзор методов грамматического вывода для изучения естественного языка». ^{[ мертвая ссылка ]}», «Обзор искусственного интеллекта» , том 36, № 1, стр. 1–27.
^ Талтон, Джерри и др. «Изучение шаблонов проектирования с помощью индукции байесовской грамматики». Материалы 25-го ежегодного симпозиума ACM по программному обеспечению и технологиям пользовательского интерфейса. 2012.
^ Ким, Юн, Крис Дайер и Александр М. Раш. «Сложные вероятностные бесконтекстные грамматики для индукции грамматики». Препринт arXiv arXiv:1906.10225 (2019).
^ Кларк и Эйро (2007) Журнал исследований машинного обучения ; Ре Ёсинака (2011) Теоретическая информатика
^ Дана Англуин (1980). «Нахождение закономерностей, общих для набора строк» . Журнал компьютерных и системных наук . 21 : 46–62. дои : 10.1016/0022-0000(80)90041-0 .
^ Т. Эрлебах; П. Россманит; Х. Стадтерр; А. Стегер ; Т. Зейгманн (1997). «Очень эффективное изучение языков с одной переменной в среднем, параллельно и с помощью запросов» . У М. Ли; А. Маруока (ред.). Учеб. 8-й международный семинар по теории алгоритмического обучения — ALT'97 . ЛНАИ. Том. 1316. Спрингер. стр. 260–276.
^ Хироки Аримура; Такеши Синохара; Сэцуко Оцуки (1994). «Поиск минимальных обобщений для объединений языков шаблонов и его применение к индуктивному выводу на основе положительных данных» (PDF) . Учеб. СТАКС 11 . ЛНКС. Том. 775. Спрингер. стр. 649–660. ^{[ мертвая ссылка ]}
^ Гренандер, Ульф и Майкл И. Миллер. Теория паттернов: от представления к выводу . ^{[ мертвая ссылка ]} Том. 1. Оксфорд: Издательство Оксфордского университета, 2007.
^ Миллер, Скотт и др. « Скрытые модели понимания естественного языка ». Материалы 32-го ежегодного собрания Ассоциации компьютерной лингвистики. Ассоциация компьютерной лингвистики, 1994.
^ Браун, Ральф Д. « Индукция по правилам переноса для перевода на основе примеров ». Материалы восьмого семинара MT Summit по машинному переводу на основе примеров. 2001.
^ Чейтер, Ник и Кристофер Д. Мэннинг. « Вероятностные модели обработки и усвоения языка ». Тенденции в когнитивных науках 10.7 (2006): 335-344.
^ Чернявский, Нева и Ричард Ладнер. « Сжатие последовательностей ДНК на основе грамматики ». Рабочая группа DIMACS по преобразованию Берроуза – Уиллера 21 (2004).
^ Сенин, Павел и др. «Обнаружение аномалий временных рядов с помощью сжатия на основе грамматики». Эдбт. 2015.
^ Киффер, Дж. К.; Ян, Э.-Х. (2000), «Коды на основе грамматики: новый класс универсальных исходных кодов без потерь», IEEE Trans. Инф. Теория , 46 (3): 737–754, doi : 10.1109/18.841160.
^ Чарикар, М.; Леман, Э.; Лю, Д.; Паниграхи, Р.; Прабхаракан, М.; Сахай, А.; Шелат, А. (2005), «Маленькая грамматическая проблема», IEEE Trans. Инф. Theory , 51 (7): 2554–2576, doi : 10.1109/tit.2005.850116 , S2CID 6900082.

Источники [ править ]

Дуда, Ричард О.; Харт, Питер Э.; Сторк, Дэвид Г. (2001), Классификация образцов (2-е изд.), Нью-Йорк : John Wiley & Sons.
Фу, Кинг Сан (1982), Распознавание синтаксических образов и их применение , Энглвуд Клиффс, Нью-Джерси : Прентис-Холл
Фу, Король Сунь (1977), Распознавание синтаксических образов, Приложения , Берлин : Springer-Verlag
Хорнинг, Джеймс Джей (1969), Исследование грамматического вывода (под ред. Кандидатской диссертации), Стэнфорд : Факультет компьютерных наук Стэнфордского университета, ПроКвест 302483145
Голд, Э. Марк (1967), Языковая идентификация в пределе , том. 10, Информация и контроль , стр. 447–474, заархивировано из оригинала 28 августа 2016 г. , получено 4 сентября 2016 г.
Голд, Э. Марк (1967), Предельная языковая идентификация (PDF) , том. 10, Информация и контроль , стр. 447–474.

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

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

[Grammatical_Inference-1] Перейти обратно: Перейти обратно: ^а ^б де ла Игера, Колин (2010). Грамматический вывод: автоматы обучения и грамматики (PDF) . Кембридж: Издательство Кембриджского университета. Архивировано из оригинала (PDF) 14 февраля 2019 г. Проверено 16 августа 2017 г.

[Kwiatkowski-2] Перейти обратно: Перейти обратно: ^а ^б Квятковски, Том и др. « Лексическое обобщение в индукции грамматики CCG для семантического анализа ». Материалы конференции по эмпирическим методам обработки естественного языка. Ассоциация компьютерной лингвистики , 2011.

[3] Кларк, Александр. « Неконтролируемая индукция стохастических контекстно-свободных грамматик с использованием распределительной кластеризации ». Материалы семинара 2001 г. по компьютерному изучению естественного языка, том 7. Ассоциация компьютерной лингвистики, 2001.

[4] Дана Англуин (1987). «Изучение регулярных наборов на основе запросов и контрпримеров» (PDF) . Информация и контроль . 75 (2): 87–106. CiteSeerX 10.1.1.187.9414 . дои : 10.1016/0890-5401(87)90052-6 . S2CID 11873053 . Архивировано из оригинала (PDF) 2 декабря 2013 г.

[5] Д'Улиция, А., Ферри, Ф., Грифони, П. (2011) « Обзор методов грамматического вывода для изучения естественного языка». ^{[ мертвая ссылка ]}», «Обзор искусственного интеллекта» , том 36, № 1, стр. 1–27.

[6] Талтон, Джерри и др. «Изучение шаблонов проектирования с помощью индукции байесовской грамматики». Материалы 25-го ежегодного симпозиума ACM по программному обеспечению и технологиям пользовательского интерфейса. 2012.

[7] Ким, Юн, Крис Дайер и Александр М. Раш. «Сложные вероятностные бесконтекстные грамматики для индукции грамматики». Препринт arXiv arXiv:1906.10225 (2019).

[8] Кларк и Эйро (2007) Журнал исследований машинного обучения ; Ре Ёсинака (2011) Теоретическая информатика

[11] Дана Англуин (1980). «Нахождение закономерностей, общих для набора строк» . Журнал компьютерных и системных наук . 21 : 46–62. дои : 10.1016/0022-0000(80)90041-0 .

[12] Т. Эрлебах; П. Россманит; Х. Стадтерр; А. Стегер ; Т. Зейгманн (1997). «Очень эффективное изучение языков с одной переменной в среднем, параллельно и с помощью запросов» . У М. Ли; А. Маруока (ред.). Учеб. 8-й международный семинар по теории алгоритмического обучения — ALT'97 . ЛНАИ. Том. 1316. Спрингер. стр. 260–276.

[13] Хироки Аримура; Такеши Синохара; Сэцуко Оцуки (1994). «Поиск минимальных обобщений для объединений языков шаблонов и его применение к индуктивному выводу на основе положительных данных» (PDF) . Учеб. СТАКС 11 . ЛНКС. Том. 775. Спрингер. стр. 649–660. ^{[ мертвая ссылка ]}

[14] Гренандер, Ульф и Майкл И. Миллер. Теория паттернов: от представления к выводу . ^{[ мертвая ссылка ]} Том. 1. Оксфорд: Издательство Оксфордского университета, 2007.

[15] Миллер, Скотт и др. « Скрытые модели понимания естественного языка ». Материалы 32-го ежегодного собрания Ассоциации компьютерной лингвистики. Ассоциация компьютерной лингвистики, 1994.

[16] Браун, Ральф Д. « Индукция по правилам переноса для перевода на основе примеров ». Материалы восьмого семинара MT Summit по машинному переводу на основе примеров. 2001.

[17] Чейтер, Ник и Кристофер Д. Мэннинг. « Вероятностные модели обработки и усвоения языка ». Тенденции в когнитивных науках 10.7 (2006): 335-344.

[18] Чернявский, Нева и Ричард Ладнер. « Сжатие последовательностей ДНК на основе грамматики ». Рабочая группа DIMACS по преобразованию Берроуза – Уиллера 21 (2004).

[19] Сенин, Павел и др. «Обнаружение аномалий временных рядов с помощью сжатия на основе грамматики». Эдбт. 2015.

[20] Киффер, Дж. К.; Ян, Э.-Х. (2000), «Коды на основе грамматики: новый класс универсальных исходных кодов без потерь», IEEE Trans. Инф. Теория , 46 (3): 737–754, doi : 10.1109/18.841160.

[21] Чарикар, М.; Леман, Э.; Лю, Д.; Паниграхи, Р.; Прабхаракан, М.; Сахай, А.; Шелат, А. (2005), «Маленькая грамматическая проблема», IEEE Trans. Инф. Theory , 51 (7): 2554–2576, doi : 10.1109/tit.2005.850116 , S2CID 6900082.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[примечание 1]

[примечание 2]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]