Индукция обычных языков - Induction of regular languages

В теория вычислительного обучения, индукция регулярных языков относится к задаче изучения формальное описание (например, грамматика) обычный язык из заданного набора примеров строк. Несмотря на то что Э. Марк Голд показал, что не каждый обычный язык можно выучить таким образом (см. определение языка в пределе ) подходы были исследованы для множества подклассов. Они обрисованы в общих чертах в этой статье. Для изучения более общих грамматик см. Введение в грамматику.

Пример

А обычный язык определяется как (конечный или бесконечный) набор струны что может быть описано одним из математических формализмов, называемых "конечный автомат ", "регулярная грамматика ", или же "регулярное выражение ", все из которых обладают одинаковой выразительной силой. Поскольку последний формализм приводит к кратчайшим обозначениям, он будет введен и использован здесь. Для набора Σ символов (он же алфавит) a регулярное выражение может быть любым из

  • ∅ (обозначает пустой набор строк),
  • ε (обозначает одноэлементный набор, содержащий только пустую строку),
  • а (куда а - любой характер из Σ; обозначает одноэлементный набор, содержащий только односимвольную строку а),
  • р+s (куда р и s являются, в свою очередь, более простыми регулярными выражениями; обозначающий объединение их множества)
  • р⋅s (обозначающий набор всех возможных конкатенаций строк из р 'песок s набор),
  • р+ (обозначая набор п-кратные повторы струн из р набор, для любого п≥1), или
  • р* (аналогично обозначая набор п-кратное повторение, но также включая пустую строку, рассматриваемую как 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, 10 и 100 (положительные примеры). Для каждой из отрицательных примерных строк 11, 1001, 101 и 0 верхний комплект автоматов, порождающих его. Единственные автоматы, которые генерируют все {1, 10, 100}, но ни один из {11, 1001, 101, 0}, - это тривиальный нижний автомат и тот, который соответствует регулярному выражению 1⋅0*.

Dupont et al. показали, что множество всех структурно полных конечных автоматов[примечание 1]создание заданного входного набора примеров строк формирует решетка, с тривиальным неполнообобщенным автоматом и тривиальным сверхобобщенным автоматом в качестве нижнего и верхнего элементов соответственно. Каждый член этой решетки может быть получен следующим образом: факторинг недостаточно обобщенный автомат подходящим отношение эквивалентности.

В приведенном выше примере набора строк {1, 10, 100} на картинке внизу показан неполнообобщенный автомат Аа, б, в, г в серый, состоящий из состояний а, б, c, и d. На множестве состояний {a, b, c, d} существует всего 15 отношений эквивалентности, образующих решетку. Картография[заметка 2] каждая эквивалентность E к соответствующему языку фактор-автоматов L (Аа, б, в, г / E) получает частично упорядоченный набор, показанный на рисунке. Язык каждого узла обозначается регулярным выражением. Язык может быть распознан с помощью частных автоматов по различные отношения эквивалентности, все из которых показаны под узлом. Стрелка между двумя узлами указывает, что язык нижнего узла является правильным подмножеством языка более высокого узла.

Если даны как положительные, так и отрицательные примеры строк, Dupont et al. построить решетку из положительных примеров, а затем исследовать разделительную границу между автоматами, которые генерируют какой-то отрицательный пример, и такими, которые нет. Наиболее интересны те автоматы, которые находятся непосредственно под границей.[1]На рисунке показаны границы раздела для отрицательных примеров строк 11 (зеленый), 1001 (синий), 101 (голубой) и 0 (красный).

Косте и Николас представляют собственный метод поиска в решетке, который они соотносят с методом Митчелла. пространство версий парадигма: чтобы найти границу разделения, они используют алгоритм раскраски графа по отношению неравенства состояний, индуцированному отрицательными примерами.[2]Позже они исследуют несколько отношений упорядочения на множестве всех возможных слияний состояний.[3]

Кудо и Шимбо используют представление с помощью автоматных факторизаций, чтобы дать уникальную основу для следующих подходов (схематично показано ниже ):

Показано, что каждый из этих подходов соответствует определенному виду отношений эквивалентности, используемых для факторизации.[5]

Подходы

k-реверсивные языки

Англуин считает так называемым "k-обратимые регулярные автоматы, то есть детерминированные автоматы, в которых каждое состояние может быть достигнуто не более чем из одного состояния, следуя цепочке переходов длины kФормально, если Σ, Q, а δ обозначают входной алфавит, набор состояний и функцию перехода автомата Асоответственно, то А называется k-обратимый, если: ∀а0,...,аk ∈ Σ ∀s1, s2 ∈ Q: δ*(s1,а0...аk) = δ*(s2,а0...аk) ⇒ s1 = s2, где δ* означает гомоморфное расширение δ до произвольных слов. Angluin дает кубический алгоритм для обучения наименьших k-обратимый язык из заданного набора входных слов; за k= 0 алгоритм имеет даже почти линейную сложность.[6][7]Требуемая уникальность состояния после k+1 заданный символ вынуждает объединять состояния автомата, таким образом приводя к собственному обобщению, отличному от тривиального недостаточно обобщенного автомата. Этот алгоритм использовался для изучения простых частей синтаксиса английского языка;[8]позже была предоставлена ​​инкрементная версия.[9]Другой подход, основанный на k-обратимым автоматом является метод кластеризации хвостов.[10]

Преемник автоматов

Из заданного набора входных строк Вернадат и Ришетен создают так называемый автомат-преемник, состоящий из одного состояния для каждого отдельного символа и перехода между состояниями каждых двух соседних символов.[11]Например, входной набор singleton { Aabbaabb } приводит к автомату, соответствующему регулярное выражение (а+⋅б+)*.

Расширением этого подхода является метод предшественника-преемника который немедленно обобщает каждое повторение символа на Клини + а затем включает для каждого символа набор его возможных предшественников в его состояние. Автомат-последователь может точно узнать класс местные языки.Поскольку каждый обычный язык является гомоморфным образом местного языка, грамматики из первого класса могут быть изучены подъем, при необходимости (в зависимости от предполагаемого применения) гомоморфизм В частности, такой гомоморфизм существует для класса языков, изучаемых методом предшественник-преемник.[12]Изучение местных языков можно свести к изучению k-обратимые языки.[13][14]

Производная Бжозовского (на красном фоне) словарной строки, установленной относительно "против"
Иллюстрация леммы о накачке для регулярных автоматов

Ранние подходы

Хомский и Миллер (1957)[15]использовал лемма о накачке: они угадывают часть v входной строки uvw и попытайтесь встроить соответствующий цикл в автомат, который нужно обучить; с помощью запросы о членстве они просят соответствующие k, какая из струн уф, uvvw, увввв, ..., УФkш также принадлежит к изучаемому языку, тем самым улучшая структуру своего автомата. В 1959 г. Соломонов обобщил этот подход на контекстно-свободные языки, которые также подчиняются лемма о накачке.[16]

Крышка автоматов

Кампеану и др. изучать конечный автомат как компактное представление большого конечного языка. F, они ищут так называемый крышка автомат А так что его язык L(А) охватывает F в следующем смысле: L(А) ∩ Σ≤л = F, куда л это длина самой длинной строки в F, и Σ≤л обозначает набор всех строк не длиннее, чем л. Если такой автомат покрытия существует, F однозначно определяется А и л.Например, F = { объявление, читать, перечитать } имеет л=6 и покрывающий автомат, соответствующий регулярному выражению (р⋅е)*⋅а⋅d.

Для двух струн Икс и у, Кампеану и др. определять Икс ~ у если xz∈F ⇔ yz∈F для всех струн z такой длины, что оба xz и yz не длиннее, чем л.[17] Исходя из этого соотношения, отсутствие транзитивность[заметка 3] вызывает значительные технические проблемы, они дают О (п4)[примечание 4] алгоритм построения из F прикрывающий автомат А с минимальным числом состояний. Более того, для объединения, пересечения и разности двух конечных языков они обеспечивают соответствующие операции над их автоматами покрытия.[18][19]Păun et al. улучшить временную сложность до О(п2).[20]

Остаточные автоматы

Для набора S струн и струны ты, то Производная Бжозовского ты−1S определяется как набор всех остальных строк, получаемых из строки в S отрезав его префикс ты (если возможно), формально: ты−1S = { v ∈ Σ*: УФ ∈ S }, ср. рисунок.[21]Денис и др. определить остаточный автомат быть недетерминированным конечным автоматом А где каждое государство q соответствует производной Бжозовского принятого языка L(А), формально: ∀q∈Q ∃ты∈Σ*: L(А,q) = ты−1L(А), куда L(А,q) обозначает язык, принятый из q как начальное состояние.

Они показывают, что каждый регулярный язык порождается однозначно определенным минимальным остаточным автоматом. Его состояния являются ∪-неразложимыми производными Бжозовского, и они могут быть экспоненциально меньше, чем минимальный детерминированный автомат. Более того, они показывают, что остаточные автоматы для обычных языков не могут быть изучены за полиномиальное время, даже при условии оптимальных входных выборок. Они дают алгоритм обучения для остаточных автоматов и докажите, что он изучает автомат характерный образец положительных и отрицательных входных строк.[22][23]

Изучение запросов

Обычные языки нельзя выучить за полиномиальное время, используя только запросы членства[24] или используя только запросы эквивалентности.[25]Однако Англуин показал, что обычные языки можно изучать за полиномиальное время, используя запросы членства и запросы эквивалентности, и предоставил алгоритм обучения под названием L *, который делает именно это.[26]Позднее алгоритм L * был обобщен для вывода NFA (недетерминированные конечные автоматы ), а не DFA (детерминированные конечные автоматы ) с помощью алгоритма, называемого NL *.[27]Этот результат был дополнительно обобщен, и алгоритм, который выводит AFA (переменные конечные автоматы ), названный AL *.[28] Следует отметить, что NFA могут быть экспоненциально более лаконичными, чем DFA, и что AFA могут быть экспоненциально более лаконичными, чем NFA, и вдвойне экспоненциально более лаконичными, чем DFA.[29]

Сокращенные регулярные выражения

Брилл определяет сокращенное регулярное выражение быть любым из

  • а (где a - любой символ в Σ; обозначает одноэлементный набор, содержащий только односимвольную строку a),
  • ¬а (обозначает любой другой одиночный символ в Σ, кроме а),
  • • (обозначает любой одиночный символ в Σ)
  • а*, (¬а)*, или же •* (обозначает произвольно много, возможно, ноль, повторений символов из набора а, ¬а, или • соответственно), или
  • р⋅s (где r и s, в свою очередь, представляют собой более простые сокращенные регулярные выражения, обозначающие набор всех возможных конкатенаций строк из р 'песок s установлен).

Учитывая входной набор строк, он шаг за шагом строит дерево где каждая ветвь помечена сокращенным регулярным выражением, принимающим префикс некоторых входных строк, и каждый узел помечен набором длин принятых префиксов. Он стремится изучить правила исправления орфографических ошибок английского языка,[примечание 5]а не теоретические соображения об обучаемости языковых классов. Следовательно, он использует эвристика чтобы сократить скопление деревьев, что приведет к значительному сокращению времени выполнения.[30]

Приложения

Примечания

  1. ^ т.е. конечные автоматы без лишних состояний и переходов по отношению к заданному входному набору строк
  2. ^ Это отображение не решеточный гомоморфизм, но только монотонное отображение.
  3. ^ Например, F = { ааб, баа, aabb } приводит к ааб ~ aabb (Только z= ε необходимо учитывать, чтобы проверить это) и aabb ~ баа (аналогично), но не ааб ~ баа (по делу z=б). По данным Câmpeanu et al. (2001, лемма 1, с. 5), однако Икс ~ у ∧ у ~ z → Икс ~ z держится для струн Икс, у, z с |Икс| ≤ |у| ≤ |z|.
  4. ^ куда п количество состояний DFA АF такой, что L(АF) = F
  5. ^ Например: заменить "прошлый" к "прошедший«в контексте» (¬т⋅о)*⋅СУЩЕСТВИТЕЛЬНОЕ В ЕДИНСТВЕННОМ ЧИСЛЕ⋅прошлый"

Рекомендации

  1. ^ П. Дюпон; Л. Микле; Э. Видаль (1994). «Что такое пространство поиска регулярного вывода?». У Р. К. Карраско; Дж. Онцина (ред.). Труды Второго международного коллоквиума по грамматическому выводу (ICGI): грамматический вывод и приложения. LNCS. 862. Springer. С. 25–37. CiteSeerX  10.1.1.54.5734.
  2. ^ Ф. Косте; Дж. Николас (1997). «Регулярный вывод как проблема раскраски графа». Proc. Семинар ICML по грамматическому выводу, автоматной индукции и овладению языком. С. 9–7. CiteSeerX  10.1.1.34.4048.
  3. ^ Ф. Косте; Дж. Николас (1998). «Как учет несовместимых слияний состояний может уменьшить дерево поиска индукции DFA». В Васант Хонавар; Гиора Слуцки (ред.). Грамматический вывод, 4-й Международный коллоквиум, ICGI. LNCS. 1433. Springer. С. 199–210. CiteSeerX  10.1.1.34.2050.
  4. ^ Доминик Люзо (август 1997 г.). «Универсальный подход к положительному выводу регулярной грамматики». Proc. 15-й Всемирный конгресс IMACS по научным вычислениям, моделированию и прикладной математике.
  5. ^ М. Кудо; М. Шимбо (1988). «Эффективные методы регулярного грамматического вывода с использованием частичных сходств и их логических отношений». Распознавание образов. 21 (4): 401–409. Дои:10.1016/0031-3203(88)90053-2.
  6. ^ Д. Англуин (1981). «Примечание о количестве запросов, необходимых для определения регулярных языков». Информация и контроль. 51: 76–87. Дои:10.1016 / с0019-9958 (81) 90090-5.
  7. ^ Д. Англуин (1982). «Вывод обратимых языков». J. ACM. 293 (3): 741–765. CiteSeerX  10.1.1.232.8749. Дои:10.1145/322326.322334.
  8. ^ Роберт С. Бервик; Сэмюэл Ф. Пилато (1987). «Изучение синтаксиса с помощью индукции автоматов». Машинное обучение. 2 (1): 9–38. Дои:10.1007 / bf00058753.
  9. ^ Раджеш Парекх; Кодрин Ничитиу; Васант Хонавар (январь 1997 г.). Полиномиальный инкрементальный алгоритм для регулярного вывода грамматики (Технический отчет). Исследовательская группа AI, Iowa State Univ. п. 14. ТР 97-03.
  10. ^ Л. Микле; К. Фор (1985). Reconnaissance des Formes Structurelle: Développement et Tendances (Технический отчет). INRIA.
  11. ^ Ф. Вернадат; М. Рикетен (1984). «Регулярный вывод для распознавания синтаксических образов: тематическое исследование». Proc. 7-я Международная конференция по распознаванию образов (ICPR). С. 1370–1372.
  12. ^ П. Гарсия; Э. Видаль; Ф. Казакуберта (1987). «Местные языки, метод преемника и шаг к общей методологии вывода регулярных грамматик». IEEE Transactions по анализу шаблонов и машинному анализу. 9.
  13. ^ Такаши Ёкомори (октябрь 1989 г.). «Эффективное изучение контекстно-свободных языков». В К.П. Янтке (ред.). Proc. Int. Мастерская AII. LNAI. 397. Springer. С. 104–123. Дои:10.1007/3-540-51734-0_54. ISBN  978-3-540-51734-4.
  14. ^ Сатоши Кобаяши; Такаши Ёкомори (1994). «Изучение конкатенации локально тестируемых языков на основе положительных данных». В Сэцуо Арикава; Клаус П. Янтке (ред.). Proc. 5-й ALT. LNAI. 872. Springer. С. 405–422. CiteSeerX  10.1.1.52.4678.
  15. ^ Н. Хомский; Г.А. Миллер (1957). Зачатие модели (Технический отчет). АСТИЯ. Документ AD110076.
  16. ^ Р. Соломонов (июнь 1959 г.). «Новый метод для открытия грамматики языков с фразовой структурой». Proc. Int. Конф. по обработке информации. Р.Ольденбург. С. 285–290.
  17. ^ Это соотношение обобщает соотношение рF от Теорема Майхилла-Нероде. Более подробно это исследовано в разделе 3: Синтия Дворк; Ларри Стокмейер (1990). «Временной разрыв в сложности для двухсторонних вероятностных конечных автоматов». SIAM Журнал по вычислениям. 19 (6): 1011–1023. Дои:10.1137/0219069.
  18. ^ а б Сезар Кампеану; Николае Сантеан; Шэн Ю (1998). «Минимальные автоматы-обложки для конечных языков». В Ж.-М. Шампарно; Д. Морель; Д. Зиади (ред.). Proc. Семинар по внедрению автоматов (WIA) (PDF). LNCS. 1660. Springer. С. 43–56. CiteSeerX  10.1.1.37.431. Дои:10.1007/3-540-48057-9_4. ISBN  978-3-540-66652-3.
  19. ^ Сезар Кампеану; Николае Сантеан; Шэн Ю (2001). «Минимальные автоматы-обложки для конечных языков». Теоретическая информатика. 267 (1–2): 3–16. Дои:10.1016 / s0304-3975 (00) 00292-9.
  20. ^ Андрей Паун; Николае Сантеан; Шэн Ю (сентябрь 2001 г.). "An O (n2) Алгоритм построения автоматов с минимальным покрытием для конечных языков ». In Sheng Yu; Andrei Păun (eds.). Proc. 5-й Int. Конф. по внедрению и применению автоматов (CIAA) (PDF). LNCS. 2088. Springer. С. 243–251. ISBN  978-3-540-42491-8.
  21. ^ Януш А. Бжозовский (1964). «Производные от регулярных выражений». J ACM. 11 (4): 481–494. Дои:10.1145/321239.321249.
  22. ^ Франсуа Дени; Орелиен Лемей; Ален Терлютте (2000). «Изучение обычных языков с помощью недетерминированных конечных автоматов». В Арлиндо Л. Оливейра (ред.). Грамматический вывод: алгоритмы и приложения, 5-й международный коллоквиум, ICGI. LNCS. 1891. Springer. С. 39–50. CiteSeerX  10.1.1.13.5559. ISBN  978-3-540-41011-9.
  23. ^ Франсуа Дени; Орелиен Лемей; Ален Терлютте (2001). «Изучение обычных языков с помощью RFSA» (PDF). Proc. ALT '01.
  24. ^ Англуин, Дана (1995). «Когда не помогут запросы о членстве? (Расширенная аннотация)». 23-й ежегодный симпозиум ACM по теории вычислений.
  25. ^ Англуин, Дана (1990). «Отрицательные результаты для запросов на эквивалентность». Машинное обучение. 5.
  26. ^ Англуин, Дана (1987). «Изучение регулярных наборов на основе запросов и контрпримеров». Информация и вычисления. 75.
  27. ^ Бенедикт, Хабермель, Керн, Лекер (2009). «Изучение NFA в стиле англуинов» (PDF). 21-я Международная совместная конференция по искусственному интеллекту.CS1 maint: несколько имен: список авторов (связь)
  28. ^ Англуин, Эйзенстат и Фисман (2015). «Изучение обычных языков с помощью чередующихся автоматов». 24-я международная совместная конференция по искусственному интеллекту.
  29. ^ Майер и Стокмейер (1995). «Сложность задач со словами - на этот раз с чередованием». Информация и вычисления. 115.
  30. ^ а б Эрик Брилл (2000). «Устранение неоднозначности на основе шаблонов для обработки естественного языка» (PDF). Proc. EMNLP / VLC.
  31. ^ Алвис Бразма; Инге Йонассен; Яак Вило; Эско Укконен (1998). «Открытие закономерностей в биопоследовательностях». В Васант Хонавар; Гиора Слуцки (ред.). Грамматический вывод, 4-й Международный коллоквиум, ICGI. LNCS. 1433. Springer. С. 257–270.
  32. ^ РС. Waterman, ed. (Январь 1989 г.). Математические методы определения последовательностей ДНК. CRC Press. ISBN  978-0849366642.
  33. ^ Фернандо Перейра; Ив Шабес (1992). «Переоценка изнутри-наружу для частично заключенных в скобки корпусов». Proc. 30-я Ann. Встреча доц. для комп. Лингвистика. С. 128–135.
  34. ^ Хелена Ахонен (ноябрь 1996 г.). Создание грамматик для структурированных документов с использованием методов грамматического вывода (PDF) (Кандидат наук.). Отчет. А-1996-4. Университет Хельсинки, факультет компьютерных наук.
  35. ^ Стивен Уоткинсон (1997). Индукция музыкального синтаксиса (Владелец). Кафедра искусственного интеллекта Univ. Эдинбург. Архивировано из оригинал 4 июня 2001 г.
  36. ^ Педро П. Крус-Алькасар; Энрике Видаль (1998). «Изучение обычных грамматик для моделирования музыкального стиля: сравнение различных схем кодирования» (PDF). В Васант Хонавар; Гиора Слуцки (ред.). Грамматический вывод, 4-й Международный коллоквиум, ICGI. LNCS. 1433. Springer. С. 211–222.
  37. ^ Александр С. Саиди; Суад Тайеб-бей (1998). «Грамматический вывод в распознавании документов». В Васант Хонавар; Гиора Слуцки (ред.). Грамматический вывод, 4-й Международный коллоквиум, ICGI. LNCS. 1433. Springer. С. 175–186. ISBN  978-3-540-64776-8.