Индукция регулярных языков
В теории компьютерного обучения индукция регулярных языков относится к задаче изучения формального описания (например, грамматики) регулярного языка на основе заданного набора примеров строк. Хотя Э. Марк Голд показал, что не каждый обычный язык можно выучить таким способом (см. идентификацию языка в пределе ), подходы исследовались для множества подклассов. Их эскизы представлены в этой статье. Для изучения более общих грамматик см. « Введение в грамматику» .
Определения [ править ]
Регулярный язык определяется как (конечный или бесконечный) набор строк , который может быть описан одним из математических формализмов, называемых « конечный автомат », « регулярная грамматика » или « регулярное выражение », каждый из которых имеет одинаковую выразительную силу. . Поскольку последний формализм приводит к кратчайшим обозначениям, он будет введен и использован здесь. Учитывая набор символов Σ (он же алфавит), регулярное выражение может быть любым из
- ∅ (обозначающий пустой набор строк),
- ε (обозначает одноэлементный набор, содержащий только пустую строку),
- a (где a — любой символ из Σ; обозначает одноэлементный набор, содержащий только односимвольную строку a ),
- r + s (где r и s , в свою очередь, являются более простыми регулярными выражениями; обозначают объединение их множества)
- r ⋅ s (обозначает набор всех возможных конкатенаций строк из набора r и s ),
- р + (обозначая набор n -кратных повторений строк из n набора r для любого ≥ 1), или
- р * (аналогично обозначает набор n -кратных повторений, но также включает пустую строку, рассматриваемую как 0-кратное повторение).
Например, используя Σ = {0,1}, регулярное выражение (0+1+ε)⋅(0+1) обозначает набор всех двоичных чисел с одной или двумя цифрами (допускается ведущий ноль), а 1⋅( 0+1) * ⋅0 обозначает (бесконечное) множество всех четных двоичных чисел (без ведущих нулей).
Учитывая набор строк (также называемых «положительными примерами»), задача индукции регулярного языка состоит в том, чтобы найти регулярное выражение, обозначающее набор, содержащий их все. Например, учитывая {1, 10, 100}, «естественным» описанием может быть регулярное выражение 1⋅0. * , что соответствует неформальной характеристике « 1, за которым следует произвольное количество (возможно, даже ни одного) 0 ». Однако (0+1) * и 1+(1⋅0)+(1⋅0⋅0) — ещё одно регулярное выражение, обозначающее наибольший (при условии, что Σ = {0,1}) и наименьший набор, содержащий заданные строки, и называемое тривиальным сверхобобщением и недостаточным обобщением. , соответственно. Некоторые подходы работают в расширенной настройке, где также дается набор строк «отрицательного примера»; затем необходимо найти регулярное выражение, которое генерирует все положительные примеры, но не генерирует ни одного отрицательного.
Решетка автоматов [ править ]
 |
Дюпон и др. показали, что множество всех структурно полных конечных автоматов [примечание 1] генерация заданного входного набора строк-примеров образует решетку с тривиальным недообобщенным и тривиальным сверхобобщенным автоматом в качестве нижнего и верхнего элемента соответственно. Каждый член этой решетки может быть получен факторизацией недообобщенного автомата соответствующим отношением эквивалентности .
Для приведенного выше примера набора строк {1, 10, 100} на рисунке внизу показан недообобщенный автомат A a,b,c,d в серый , состоящий из состояний а , б , с и д . На наборе состояний {a,b,c,d} существует всего 15 отношений эквивалентности, образующих решетку. Картирование [заметка 2] каждая эквивалентность E соответствующему факторавтоматному языку L ( A a,b,c,d / E ) получает частично упорядоченный набор , показанный на рисунке. Язык каждого узла обозначается регулярным выражением. Язык может распознаваться факторавтоматами по различным отношениям эквивалентности, все из которых показаны под узлом. Стрелка между двумя узлами указывает, что язык нижнего узла является подмножеством языка верхнего узла.
Если приведены как положительные, так и отрицательные примеры строк, Dupont et al. постройте решетку из положительных примеров, а затем исследуйте границу разделения между автоматами, генерирующими какой-либо отрицательный пример, и такими, которые этого не делают. Наиболее интересны те автоматы, которые находятся сразу под границей. [1] На рисунке границы разделения показаны для отрицательных строк примера 11 ( зеленый ), 1001 ( синий) , 101 ( голубой ) и 0 ( красный ).
Митчелла Косте и Николас представляют собственный метод поиска внутри решетки, который они соотносят с парадигмой пространства версий . Чтобы найти границу разделения, они используют алгоритм раскраски графа отношения неравенства состояния, вызванного отрицательными примерами. [2] Позже они исследуют несколько отношений упорядочения на множестве всех возможных слияний состояний. [3]
Кудо и Шимбо используют представление посредством автоматной факторизации, чтобы создать уникальную основу для следующих подходов (наброски показаны ниже ):
- k -обратимые языки и последующий подход «хвостовой кластеризации»,
- Автоматы-преемники и метод предшественник-последователь, а также
- подходы, основанные на перекачке (интеграция рамок, оспариваемая Люзо, [4] однако).
Показано, что каждый из этих подходов соответствует определенному виду отношений эквивалентности, используемых для факторизации. [5]
Подходы [ править ]
k -реверсивные языки [ править ]
Англуин рассматривает так называемые « k -обратимые» регулярные автоматы, то есть детерминированные автоматы, в которых каждое состояние может быть достигнуто не более чем из одного состояния, следуя цепочке переходов длины k . Формально, если Σ, Q и δ обозначают входной алфавит, множество состояний и функцию перехода автомата A соответственно, то A называется k -обратимым, если: ∀ a 0 , ..., a k ∈ Σ ∀ s 1 , s 2 ∈ Q : δ * ( s 1 , а 0 ... а k ) знак равно δ * ( s 2 , а 0 ... а k ) ⇒ s 1 знак равно s 2 , где δ * означает гомоморфное расширение δ на произвольные слова. Англуин предлагает кубический алгоритм изучения наименьшего k -обратимого языка по заданному набору входных слов; при k = 0 алгоритм имеет даже почти линейную сложность. [6] [7] Требуемая уникальность состояния после k + 1 заданных символов приводит к объединению состояний автомата, что приводит к правильному обобщению, отличному от тривиального недостаточно обобщенного автомата. Этот алгоритм использовался для изучения простых частей английского синтаксиса; [8] позже была предоставлена дополнительная версия. [9] Другой подход, основанный на k -обратимых автоматах, — это метод хвостовой кластеризации . [10]
Автоматы-преемники [ править ]
Из заданного набора входных строк Вернада и Ришетен строят так называемый автомат-преемник , состоящий из одного состояния для каждого отдельного символа и перехода между состояниями каждых двух соседних символов. [11] Например, одноэлементный входной набор { aabbaabb } приводит к автомату, соответствующему регулярному выражению ( a + ⋅ b + ) * .
Расширением этого подхода является метод предшественника-преемника , который немедленно обобщает каждое повторение символа до числа Клини. + а затем включает для каждого символа набор его возможных предшественников в его состоянии. Автоматы-преемники смогут выучить именно тот класс локальных языков . Поскольку каждый регулярный язык является гомоморфным образом локального языка, грамматики первого класса можно выучить путем поднятия соответствующий (в зависимости от предполагаемого применения) гомоморфизм , если обеспечен . В частности, такой гомоморфизм существует для класса языков, изучаемых методом предшественника-преемника. [12] Изучаемость местных языков можно свести к изучению k -обратимых языков. [13] [14]
Ранние подходы
Хомский и Миллер (1957) [15] использовали лемму о накачке : угадывают часть v входной строки uvw и пытаются встроить соответствующий цикл в обучаемый автомат; используя запросы на членство , они для соответствующего k спрашивают , какая из строк uw , uvvw , uvvvw , ..., uv к w также принадлежит изучаемому языку, тем самым уточняя структуру их автомата. В 1959 году Соломонов обобщил этот подход на контекстно-свободные языки , которые также подчиняются лемме о накачке . [16]
Прикрытие автоматов [ править ]
Кампеану и др. изучить конечный автомат как компактное представление большого конечного языка. Учитывая такой язык F , они ищут так называемый автомат покрытия A такой, что его язык L ( A ) покрывает F в следующем смысле: L ( A ) ∩ Σ ≤ л = F , где l — длина самой длинной строки в F , а Σ ≤ л обозначает набор всех строк длиной не более l . Если такой автомат-накрытие существует, то F однозначно определяется A и l . Например, F = { ad , read , reread } имеет l = 6 и автомат покрытия, соответствующий регулярному выражению ( r ⋅ e ) * ⋅ a ⋅ d .
Для двух строк x и y Кампеану и др. определим x ~ y , если xz ∈ F ⇔ yz ∈ F для всех строк z такой длины, что xz и yz не длиннее l . [17] На основании этого соотношения, отсутствие транзитивности которого [заметка 3] вызывает значительные технические проблемы, они дают O ( n 4 ) [примечание 4] Алгоритм построения из F автомата покрытия A с минимальным числом состояний. Более того, для объединения, пересечения и разности двух конечных языков они обеспечивают соответствующие операции на их автоматах покрытия. [18] [19] Паун и др. улучшить временную сложность до O ( n 2 ). [20]
Остаточные автоматы [ править ]
Для набора S строк и строки u Бжозовского производная u −1 S определяется как набор всех остальных строк, которые можно получить из строки в S путем отрезания ее префикса u (если возможно), формально: u −1 S = { v ∈ Σ * : uv ∈ S } , ср. картина. [21] Денис и др. определим остаточный автомат как недетерминированный конечный автомат A, где каждое состояние q соответствует производной Бжозовского его принятого языка L ( A ), формально: ∀ q ∈ Q ∃ u ∈ Σ * : L ( А , q ) знак равно ты −1 L ( A ), где L ( A , q ) обозначает язык, принятый из q в качестве начального состояния.
Они показывают, что каждый регулярный язык порождается однозначно определенным минимальным автоматом-остатком. Его состояния являются ∪ -неразложимыми производными Бжозовского, и он может быть экспоненциально меньшим, чем минимальный детерминированный автомат. Более того, они показывают, что остаточные автоматы для обычных языков не могут быть изучены за полиномиальное время, даже при условии оптимального набора входных данных. Они предлагают алгоритм обучения остаточных автоматов и доказывают, что он обучает автомат по характерной выборке положительных и отрицательных входных строк. [22] [23]
Обучение запросам [ править ]
Обычные языки невозможно выучить за полиномиальное время. используя только запросы членства [24] или используя только запросы эквивалентности. [25] Однако Англуин показал, что обычные языки можно выучить за полиномиальное время. используя запросы членства и запросы эквивалентности, а также предоставил алгоритм обучения названный L*, который делает именно это. [26] Позднее алгоритм L* был обобщен для вывода NFA ( недетерминированных конечных автоматов ), а не DFA ( детерминированных конечных автоматов ), с помощью алгоритма, названного NL*. [27] алгоритм, который выводит AFA ( чередующиеся конечные автоматы ), названный AL*. Этот результат был далее обобщен, и был разработан [28] Отмечается, что NFA может быть экспоненциально более кратким, чем DFA, и что AFA может быть экспоненциально более кратким, чем NFA, и вдвойне экспоненциально более кратким, чем DFA. [29] Алгоритм L* и его обобщения имеют важное значение в области теории автоматов и формального изучения языков, поскольку они демонстрируют возможность эффективного изучения более выразительных моделей автоматов, таких как NFA и AFA, которые могут представлять языки более кратко и захватывать более сложные модели. шаблоны по сравнению с традиционными DFA.
Сокращенные регулярные выражения [ править ]
Брилл определяет сокращенное регулярное выражение как любое из
- a (где a — любой символ из Σ; обозначает одноэлементный набор, содержащий только односимвольную строку a ),
- ¬ a (обозначающий любой другой одиночный символ в Σ, кроме a ),
- • (обозначает любой одиночный символ в Σ)
- а * , (¬ a ) * , или • * (обозначая произвольное количество, возможно нулевое, повторений символов из набора a , ¬ a или • соответственно), или
- r ⋅ s (где r и s , в свою очередь, являются более простыми сокращенными регулярными выражениями; обозначают набор всех возможных конкатенаций строк из набора r и s ).
Учитывая входной набор строк, он шаг за шагом строит дерево , каждая ветвь которого помечена сокращенным регулярным выражением, принимающим префикс некоторых входных строк, а каждый узел помечен набором длин принятых префиксов. Его цель - выучить правила исправления английских орфографических ошибок. [примечание 5] а не на теоретические размышления об обучаемости языковых занятий. Следовательно, он использует эвристику для сокращения древовидной структуры, что приводит к значительному улучшению времени выполнения. [30]
Приложения [ править ]
- Нахождение общих закономерностей в структур ДНК и РНК описаниях [31] [32] ( Биоинформатика )
- Моделирование овладения человеком естественным языком [33]
- Изучение структурных описаний из структурированных примеров документов, в частности определений типов документов (DTD) из SGML. документов [34]
- Изучение структуры музыкальных произведений. [35] [36]
- Получение компактных представлений конечных языков [18]
- Классификация и поиск документов [37]
- Генерация контекстно-зависимых правил исправления английских грамматических ошибок [30]
Примечания [ править ]
- ^ т.е. конечные автоматы без лишних состояний и переходов по заданному входному набору строк
- ^ Это отображение не является решеточным гомоморфизмом , а лишь монотонным отображением .
- ^ Например, F = { aab , baa , aabb } приводит к aab ~ aabb ( только z для проверки этого нужно учитывать = ε) и aabb ~ baa (аналогично), но не aab ~ baa (ввиду случая z = б ). По данным Кампеану и др. (2001, лемма 1, стр.5), однако x ~ y ∧ y ~ z → x ~ z справедливо для строк x , y , z с | х | ≤ | й | ≤ | г |.
- ^ где n — количество состояний DFA A F таких, что L ( A F ) = F
- ^ Например: Замените « прошлое » на « прошло » в контексте «(¬ t ⋅ o ) * ⋅ SINGULAR_NOUN ⋅ прошлое "
Ссылки [ править ]
- ^ П. Дюпон; Л. Микле; Э. Видаль (1994). «Что такое пространство поиска обычного вывода?». В РЦ Карраско; Дж. Ончина (ред.). Труды Второго международного коллоквиума по грамматическому выводу (ICGI): грамматический вывод и приложения . ЛНКС. Том. 862. Спрингер. стр. 25–37. CiteSeerX 10.1.1.54.5734 .
- ^ Ф. Косте; Дж. Николас (1997). «Регулярный вывод как задача раскраски графа». Учеб. Семинар ICML по грамматическому выводу, автоматной индукции и овладению языком . стр. 9–7. CiteSeerX 10.1.1.34.4048 .
- ^ Ф. Косте; Дж. Николас (1998). «Как рассмотрение слияний несовместимых состояний может уменьшить дерево поиска по индукции DFA». В Васанте Хонаваре; Гиора Слуцки (ред.). Грамматический вывод, 4-й международный коллоквиум, ICGI . ЛНКС. Том. 1433. Спрингер. стр. 199–210. CiteSeerX 10.1.1.34.2050 .
- ^ Доминик Люзо (август 1997 г.). «Универсальный подход к положительному выводу регулярной грамматики» . Учеб. 15-й Всемирный конгресс IMACS по научным вычислениям, моделированию и прикладной математике . Архивировано из оригинала 13 января 2005 г. Проверено 26 ноября 2013 г.
- ^ М. Кудо; М. Шимбо (1988). «Эффективные методы регулярного грамматического вывода с использованием частичных сходств и их логических связей». Распознавание образов . 21 (4): 401–409. Бибкод : 1988PatRe..21..401K . дои : 10.1016/0031-3203(88)90053-2 .
- ^ Д. Англуин (1981). «Примечание о количестве запросов, необходимых для определения обычных языков». Информация и контроль . 51 : 76–87. дои : 10.1016/s0019-9958(81)90090-5 .
- ^ Д. Англуин (1982). «Вывод обратимых языков». Дж. АКМ . 293 (3): 741–765. CiteSeerX 10.1.1.232.8749 . дои : 10.1145/322326.322334 . S2CID 18300595 .
- ^ Роберт С. Бервик; Сэмюэл Ф. Пилато (1987). «Изучение синтаксиса методом автоматной индукции» . Машинное обучение . 2 (1): 9–38. дои : 10.1007/bf00058753 .
- ^ Раджеш Парех; Кодрин Никитиу; Васант Хонавар (январь 1997 г.). Полиномиальный алгоритм приращения времени для вывода регулярной грамматики (технический отчет). Исследовательская группа искусственного интеллекта, Университет штата Айова. п. 14. ТР 97-03.
- ^ Л. Микле; К. Фор (1985). Распознавание структурных образов: развитие и тенденции (Технический отчет). ИНРИА.
- ^ Ф. Вернада; М. Ришетен (1984). «Регулярный вывод для распознавания синтаксических образов: практический пример». Учеб. 7-я Международная конференция по распознаванию образов (ICPR) . стр. 1370–1372.
- ^ П. Гарсия; Э. Видаль; Ф. Касакуберта (1987). «Местные языки, метод преемника и шаг к общей методологии вывода регулярных грамматик». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 9 .
- ^ Такаси Ёкомори (октябрь 1989 г.). «Эффективное изучение контекстно-свободных языков». В КП Янтке [на немецком языке] (ред.). Учеб. Межд. Семинар АII . ЛНАИ. Том. 397. Спрингер. стр. 104–123. дои : 10.1007/3-540-51734-0_54 . ISBN 978-3-540-51734-4 .
- ^ Сатоши Кобаяши; Такаси Ёкомори (1994). «Изучение конкатенации локально проверяемых языков на основе положительных данных». В Сэцуо Арикава; Клаус П. Янтке (ред.). Учеб. 5-й АЛТ . ЛНАИ. Том. 872. Спрингер. стр. 405–422. CiteSeerX 10.1.1.52.4678 .
- ^ Н. Хомский; Г. А. Миллер (1957). Концепция шаблона (Технический отчет). АСТИЯ. Документ AD110076.
- ^ Р. Соломонов (июнь 1959 г.). «Новый метод открытия грамматик языков фразовой структуры». Учеб. Межд. Конф. по обработке информации . Р.Ольденбург. стр. 285–290.
- ^ Это соотношение обобщает отношение R F из теоремы Майхилла-Нерода . Более подробно это было исследовано в разделе 3: Синтия Дворк; Ларри Стокмейер (1990). «Разрыв во временной сложности для двусторонних вероятностных конечных автоматов» . SIAM Journal по вычислительной технике . 19 (6): 1011–1023. дои : 10.1137/0219069 .
- ^ Перейти обратно: а б Цезарь Кампеану; Николае Сантян; Шэн Юй (1998). «Минимальные автоматы-покрытия для конечных языков». В Ж.-М. Шампарно; Д. Морел; Д. Зиади (ред.). Учеб. Семинар по внедрению автоматов (WIA) (PDF) . ЛНКС . Том. 1660. Спрингер. стр. 43–56. CiteSeerX 10.1.1.37.431 . дои : 10.1007/3-540-48057-9_4 . ISBN 978-3-540-66652-3 .
- ^ Цезарь Кампеану; Николае Сантян; Шэн Юй (2001). «Минимальные автоматы-покрытия для конечных языков» . Теоретическая информатика . 267 (1–2): 3–16. CiteSeerX 10.1.1.550.3055 . дои : 10.1016/s0304-3975(00)00292-9 .
- ^ Андрей Паун; Николае Сантян; Шэн Юй (сентябрь 2001 г.). «О(н 2 ) Алгоритм построения автоматов с минимальным покрытием для конечных языков». В Шэн Ю; Андрей Паун (ред.). Материалы 5-й Международной конференции по реализации и применению автоматов (CIAA) (PDF) . LNCS. Том 2088. Springer . стр. 243–251 . 978-3-540-42491-8 .
- ^ Януш А. Бжозовский (1964). «Производные регулярных выражений» . Дж АСМ . 11 (4): 481–494. дои : 10.1145/321239.321249 . S2CID 14126942 .
- ^ Франсуа Дени; Орельен Лемей; Ален Терлютт (2000). «Изучение регулярных языков с использованием недетерминированных конечных автоматов». В Арлиндо Л. Оливейра (ред.). Грамматический вывод: алгоритмы и приложения, 5-й международный коллоквиум, ICGI . ЛНКС. Том. 1891. Спрингер. стр. 39–50. CiteSeerX 10.1.1.13.5559 . ISBN 978-3-540-41011-9 .
- ^ Франсуа Дени; Орельен Лемей; Ален Терлютт (2001). «Изучение обычных языков с использованием RFSA» (PDF) . Учеб. АЛЬТ '01 .
- ^ Англуин, Дана (1995). «Когда вопросы о членстве не помогут?». Материалы двадцать третьего ежегодного симпозиума ACM по теории вычислений - STOC '91 . стр. 444–454. дои : 10.1145/103418.103420 . ISBN 9780897913973 . S2CID 9960280 .
- ^ Англуин, Дана (1990). «Отрицательные результаты для запросов эквивалентности» . Машинное обучение . 5 (2): 121–150. дои : 10.1007/BF00116034 . S2CID 189902172 .
- ^ Англуин, Дана (1987). «Изучение регулярных наборов на основе запросов и контрпримеров» . Информация и вычисления . 75 (2): 87–106. дои : 10.1016/0890-5401(87)90052-6 .
- ^ Боллиг; Хабермель; Керн; Лейкер (2009). «Изучение NFA в англуинском стиле» (PDF) . 21-я Международная совместная конференция по искусственному интеллекту .
- ^ Англуин; Айзенштат; Фисман (2015). «Изучение обычных языков с помощью альтернативных автоматов» . 24-я Международная совместная конференция по искусственному интеллекту .
- ^ Майер, Арканзас; Стокмейер, Ларри Дж. (1995). «Сложность текстовых задач — на этот раз с чередованием» . Информация и вычисления . 115 .
- ^ Перейти обратно: а б Эрик Брилл (2000). «Устранение неоднозначности на основе шаблонов для обработки естественного языка» (PDF) . Учеб. ЭМНЛП/ВЛК .
- ^ Алвис Бразма; Инге Йонассен; Яак Вило; Эско Укконен (1998). «Обнаружение закономерностей в биопоследовательностях». В Васанте Хонаваре; Гиора Слуцки (ред.). Грамматический вывод, 4-й международный коллоквиум, ICGI . ЛНКС. Том. 1433. Спрингер. стр. 257–270.
- ^ М. С. Уотерман, изд. (январь 1989 г.). Математические методы исследования последовательностей ДНК . ЦРК Пресс. ISBN 978-0849366642 .
- ^ Фернандо Перейра; Ив Шабес (1992). «Внутри-внешняя переоценка для частично брекетированных корпораций» . Учеб. 30-я Энн. Заседание доц. для Комп. Лингвистика . стр. 128–135. дои : 10.3115/981967.981984 . S2CID 63967455 .
- ^ Хелена Ахонен (ноябрь 1996 г.). Создание грамматик для структурированных документов с использованием методов грамматического вывода (PDF) (доктор философии). Отчет. Том. А-1996-4. Хельсинкский университет, факультет компьютерных наук. S2CID 60722498 . Архивировано из оригинала (PDF) 12 февраля 2020 г.
- ^ Стивен Уоткинсон (1997). Индукция музыкального синтаксиса (Магистр). Кафедра искусственного интеллекта, унив. Эдинбург. Архивировано из оригинала 4 июня 2001 года.
- ^ Педро П. Крус-Алькасар; Энрике Видаль (1998). «Изучение регулярных грамматик для моделирования музыкального стиля: сравнение различных схем кодирования» (PDF) . В Васанте Хонаваре; Гиора Слуцки (ред.). Грамматический вывод, 4-й международный коллоквиум, ICGI . ЛНКС. Том. 1433. Спрингер. стр. 211–222. дои : 10.1007/BFb0054077 . ISBN 978-3-540-64776-8 . S2CID 15302415 . Архивировано из оригинала (PDF) 16 февраля 2018 г.
- ^ Александр С. Саид; Суад Тайеб-бей (1998). «Грамматический вывод в распознавании документов». Весной Хонавар; Гиора Слуцки (ред.). Грамматический вывод, 4-й международный коллоквиум, ICGI . ЛНКС. Том. 1433. Спрингер. стр. 100-1 175–186. ISBN 978-3-540-64776-8 .