stringtranslate.com

Индукция регулярных языков

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

Определения

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

Например, при использовании Σ = {0,1} регулярное выражение (0+1+ε)⋅(0+1) обозначает множество всех двоичных чисел с одной или двумя цифрами (допускается начальный ноль), тогда как 1⋅(0+1) * ⋅0 обозначает (бесконечное) множество всех четных двоичных чисел (без начальных нулей).

При наличии набора строк (также называемых «положительными примерами») задача индукции регулярного языка состоит в том, чтобы придумать регулярное выражение, которое обозначает набор, содержащий все из них. Например, при наличии {1, 10, 100} «естественным» описанием может быть регулярное выражение 1⋅0 * , соответствующее неформальной характеристике « 1, за которой следует произвольное количество (возможно, даже ни одного) нулей ». Однако (0+1) * и 1+(1⋅0)+(1⋅0⋅0) — это еще одно регулярное выражение, обозначающее наибольший (предполагая, что Σ = {0,1}) и наименьший набор, содержащий заданные строки, и называемые тривиальным переобобщением и недообобщением соответственно. Некоторые подходы работают в расширенной обстановке, где также задан набор строк «отрицательных примеров»; затем необходимо найти регулярное выражение, которое генерирует все положительные, но ни одного отрицательного примера.

Решетка автоматов

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

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

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

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

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

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

Подходы

к-обратимые языки

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

Автоматы-преемники

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

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

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

Иллюстрация леммы о накачке для регулярных автоматов

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

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

Câmpeanu et al. изучают конечный автомат как компактное представление большого конечного языка. Учитывая такой язык F , они ищут так называемый покрывающий автомат A такой, что его язык L ( A ) покрывает F в следующем смысле: L ( A ) ∩ Σ ≤  l = F , где l — длина самой длинной строки в F , а Σ ≤  l обозначает множество всех строк не длиннее 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]

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

Производная Бжозовского (на красном фоне) набора словарных строк относительно " con "

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

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

Запрос обучения

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

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

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

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

Приложения

Примечания

  1. ^ т.е. конечные автоматы без лишних состояний и переходов, относительно заданного входного набора строк
  2. ^ Это отображение не является решеточным гомоморфизмом , а лишь монотонным отображением .
  3. ^ Например, F = { aab , baa , aabb } приводит к aab ~ aabb ( для проверки этого нужно рассмотреть только z = ε) и aabb ~ baa (аналогично), но не к aab ~ baa (из-за случая z = b ). Согласно Кампеану и др. (2001, Лемма 1, стр. 5), однако x ~ y ∧ y ~ z → x ~ z выполняется для строк x , y , z с | x | ≤ | y | ≤ | z |.
  4. ^ где n — число состояний DFA A F, таких что L ( A F ) = F
  5. ^ Например: замените " past " на " passed " в контексте "(¬ t ⋅ o ) * ⋅ SINGULAR_NOUN ⋅ past "

Ссылки

  1. ^ P. Dupont; L. Miclet; E. Vidal (1994). «Что такое пространство поиска регулярного вывода?». В RC Carrasco; J. Oncina (ред.). Труды Второго международного коллоквиума по грамматическому выводу (ICGI): грамматический вывод и приложения . LNCS. Том 862. Springer. стр. 25–37. CiteSeerX  10.1.1.54.5734 .
  2. ^ Ф. Кост; Дж. Николас (1997). «Регулярный вывод как проблема раскраски графа». Труды семинара ICML по грамматическому выводу, индукции автоматов и освоению языка . стр. 9–7. CiteSeerX 10.1.1.34.4048 . 
  3. ^ F. Coste; J. Nicolas (1998). «Как рассмотрение несовместимых слияний состояний может сократить дерево поиска индукции DFA». В Васант Хонавар; Гиора Слуцки (ред.). Грамматический вывод, 4-й международный коллоквиум, ICGI . LNCS. Том 1433. Springer. стр. 199–210. CiteSeerX 10.1.1.34.2050 . 
  4. ↑ Доминик Люзо (август 1997 г.). «Универсальный подход к выводу положительной регулярной грамматики». Труды 15-го Всемирного конгресса IMACS по научным вычислениям, моделированию и прикладной математике . Архивировано из оригинала 2005-01-13 . Получено 2013-11-26 .
  5. ^ М. Кудо; М. Шимбо (1988). «Эффективные регулярные грамматические методы вывода с использованием частичных сходств и их логических отношений». Распознавание образов . 21 (4): 401–409. Bibcode : 1988PatRe..21..401K. doi : 10.1016/0031-3203(88)90053-2.
  6. ^ Д. Энглуин (1981). «Заметка о количестве запросов, необходимых для идентификации регулярных языков». Информация и управление . 51 : 76–87. doi :10.1016/s0019-9958(81)90090-5.
  7. ^ Д. Энглуин (1982). «Вывод обратимых языков». J. ACM . 293 (3): 741–765. CiteSeerX 10.1.1.232.8749 . doi :10.1145/322326.322334. S2CID  18300595. 
  8. ^ Роберт К. Бервик; Сэмюэл Ф. Пилато (1987). «Изучение синтаксиса с помощью индукции автоматов». Машинное обучение . 2 (1): 9–38. doi : 10.1007/bf00058753 .
  9. ^ Раджеш Парекх; Кодрин Ничитиу; Васант Хонавар (январь 1997 г.). Полиномиальный алгоритм инкремента для вывода регулярной грамматики (технический отчет). Исследовательская группа ИИ, Университет штата Айова. стр. 14. TR 97-03.
  10. ^ Л. Миклет; К. Фор (1985). Reconnaissance des Formes Structurelle: Développement et Tendances (Технический отчет). ИНРИА.
  11. ^ Ф. Вернадат; М. Ришетин (1984). «Регулярный вывод для распознавания синтаксических образов: исследование случая». Труды 7-й Международной конференции по распознаванию образов (ICPR) . стр. 1370–1372.
  12. ^ П. Гарсия; Э. Видал; Ф. Касакуберта (1987). «Локальные языки, метод преемника и шаг к общей методологии вывода регулярных грамматик». Труды IEEE по анализу шаблонов и машинному интеллекту . 9 .
  13. ^ Такаси Ёкомори (октябрь 1989 г.). «Эффективное изучение контекстно-свободных языков». В KP Jantke [на немецком языке] (ред.). Proc. Int. Workshop AII . LNAI. Vol. 397. Springer. pp. 104–123. doi :10.1007/3-540-51734-0_54. ISBN 978-3-540-51734-4.
  14. ^ Сатоши Кобаяси; Такаши Ёкомори (1994). «Изучение конкатенаций локально проверяемых языков на основе положительных данных». В Сэцуо Арикава; Клаус П. Янтке (ред.). Proc. 5th ALT . LNAI. Vol. 872. Springer. pp. 405–422. CiteSeerX 10.1.1.52.4678 . 
  15. ^ Н. Хомский; GA Miller (1957). Pattern Conception (Технический отчет). ASTIA. Документ AD110076.
  16. ^ Р. Соломонофф (июнь 1959 г.). «Новый метод обнаружения грамматик языков фразовой структуры». Труды Междунар. конференции по обработке информации . Р.Олденбург. С. 285–290.
  17. ^ Это отношение обобщает отношение R F из теоремы Майхилла-Нерода . Оно было исследовано более подробно в разделе 3: Синтия Дворк; Ларри Стокмейер (1990). "A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata". SIAM Journal on Computing . 19 (6): 1011–1023. doi :10.1137/0219069.
  18. ^ ab Cezar Câmpeanu; Nicolae Sântean; Sheng Yu (1998). "Minimal Cover-Automata for Finite Languages". В J.-M. Champarnaud; D. Maurel; D. Ziadi (ред.). Proc. Workshop on Implementing Automata (WIA) (PDF) . LNCS . Vol. 1660. Springer. pp. 43–56. CiteSeerX 10.1.1.37.431 . doi :10.1007/3-540-48057-9_4. ISBN  978-3-540-66652-3.
  19. ^ Цезарь Кампеану; Николае Сантян; Шэн Юй (2001). «Минимальные автоматы-покрытия для конечных языков». Теоретическая информатика . 267 (1–2): 3–16. CiteSeerX 10.1.1.550.3055 . дои : 10.1016/s0304-3975(00)00292-9 . 
  20. ^ Андрей Паун; Николае Сантин; Шэн Юй (сентябрь 2001 г.). "О(n 2 ) алгоритм построения минимальных покрывающих автоматов для конечных языков". В Шэн Юй; Андрей Паун (ред.). Труды 5-й Международной конференции по реализации и применению автоматов (CIAA) (PDF) . LNCS. Том 2088. Springer. стр. 243–251. ISBN 978-3-540-42491-8.
  21. ^ Януш А. Бжозовский (1964). «Производные регулярных выражений». Дж АСМ . 11 (4): 481–494. дои : 10.1145/321239.321249 . S2CID  14126942.
  22. ^ Франсуа Дени; Орельен Лемей; Ален Терлютт (2000). «Изучение регулярных языков с использованием недетерминированных конечных автоматов». В Arlindo L. Oliveira (ред.). Грамматический вывод: алгоритмы и приложения, 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. ^ Angluin, Dana (1995). «Когда запросы о членстве не помогут?». Труды двадцать третьего ежегодного симпозиума ACM по теории вычислений — STOC '91 . С. 444–454. doi : 10.1145/103418.103420 . ISBN 9780897913973. S2CID  9960280.
  25. ^ Angluin, Dana (1990). «Отрицательные результаты для запросов эквивалентности». Машинное обучение . 5 (2): 121–150. doi : 10.1007/BF00116034 . S2CID  189902172.
  26. ^ Angluin, Dana (1987). «Изучение регулярных множеств с помощью запросов и контрпримеров». Информация и вычисления . 75 (2): 87–106. doi : 10.1016/0890-5401(87)90052-6 .
  27. ^ Боллиг; Хабермель; Керн; Лойкер (2009). «Обучение НКА в стиле Англуина» (PDF) . 21-я Международная совместная конференция по искусственному интеллекту .
  28. ^ Angluin; Eisenstat; Fisman (2015). «Изучение регулярных языков с помощью альтернативных автоматов». 24-я Международная совместная конференция по искусственному интеллекту .
  29. ^ Майер, AR; Стокмейер, Ларри Дж. (1995). «Сложность текстовых задач — на этот раз с чередованием». Информация и вычисления . 115 (2): 293–311. doi : 10.1006/inco.1994.1098 .
  30. ^ ab Eric Brill (2000). "Pattern–Based Disambiguation for Natural Language Processing" (PDF) . Proc. EMNLP/VLC . Архивировано из оригинала (PDF) 2018-02-16 . Получено 2018-02-16 .
  31. ^ Алвис Бразма; Инге Йонассен; Яак Вило; Эско Укконен (1998). «Обнаружение закономерностей в биопоследовательностях». В Васанте Хонаваре; Гиора Слуцки (ред.). Грамматический вывод, 4-й международный коллоквиум, ICGI . ЛНКС. Том. 1433. Спрингер. стр. 257–270.
  32. ^ MS Waterman, ред. (январь 1989). Математические методы для ДНК-последовательностей . CRC Press. ISBN 978-0849366642.
  33. ^ Фернандо Перейра; Ив Шабес (1992). «Внутренне-внешняя переоценка для частично заключенных в скобки корпусов». Труды 30-го ежегодного заседания Ассоциации комп. лингвистики . С. 128–135. doi :10.3115/981967.981984. S2CID  63967455.
  34. ^ Хелена Ахонен (ноябрь 1996 г.). Генерация грамматик для структурированных документов с использованием методов грамматического вывода (PDF) (доктор философии). Отчет. Том A-1996-4. Университет Хельсинки, кафедра компьютерных наук. S2CID  60722498. Архивировано из оригинала (PDF) 2020-02-12.
  35. ^ Стивен Уоткинсон (1997). Индукция музыкального синтаксиса (магистр). Кафедра искусственного интеллекта, Эдинбургский университет. Архивировано из оригинала 4 июня 2001 г.
  36. ^ Педро П. Крус-Алькасар; Энрике Видал (1998). «Изучение регулярных грамматик для моделирования музыкального стиля: сравнение различных схем кодирования» (PDF) . В Васант Хонавар; Гиора Слуцки (ред.). Грамматический вывод, 4-й Международный коллоквиум, ICGI . LNCS. Том 1433. Springer. стр. 211–222. doi :10.1007/BFb0054077. ISBN 978-3-540-64776-8. S2CID  15302415. Архивировано из оригинала (PDF) 2018-02-16.
  37. ^ Александр С. Саиди; Суад Тайеб-бей (1998). «Грамматический вывод в распознавании документов». В Васант Хонавар; Гиора Слуцки (ред.). Грамматический вывод, 4-й Международный коллоквиум, ICGI . LNCS. Т. 1433. Springer. С. 175–186. ISBN 978-3-540-64776-8.