Является ли нахождение минимального регулярного выражения NP-полной проблемой?

43

Я думаю о следующей проблеме: я хочу найти регулярное выражение, которое соответствует определенному набору строк (например, действительные адреса электронной почты) и не соответствует другим (недействительные адреса электронной почты).

Предположим, что под регулярным выражением мы подразумеваем некоторый четко определенный конечный автомат, я не знаком с точной терминологией, но давайте договоримся о некотором классе разрешенных выражений.

Вместо того, чтобы вручную создавать выражение, я хочу дать ему набор положительных и отрицательных примеров.

Затем должно появиться выражение, которое соответствует «+», отклоняет «-» и является минимальным в некотором четко определенном смысле (число состояний в автоматах?).

Мои вопросы:

  • Рассматривалась ли эта проблема, как ее можно определить более конкретным образом и можно ли решить ее эффективно? Можем ли мы решить это за полиномиальное время? Это NP завершено, мы можем приблизить это как-нибудь? Для каких классов выражений это будет работать? Буду признателен за любой указатель на учебники, статьи или тому подобное, которые обсуждают эту тему.
  • Это как-то связано со сложностью Колмогорова?
  • Это как-то связано с обучением? Если регулярное выражение согласуется с моими примерами, поскольку оно минимально, можем ли мы что-то сказать о его обобщающей силе на еще невиданных примерах? Какой критерий минимальности был бы более подходящим для этого? Какой из них будет более эффективным? Это как-то связано с машинным обучением? Снова любые указатели были бы полезны ...

Извините за грязный вопрос ... Направьте меня в правильном направлении, чтобы понять это. Благодарность !

Ласло Козьма
источник
2
Следующая страница очень важна для изучения вопроса: people.dsv.su.se/~henke/ML/MERLIN.html
Tsuyoshi Ito
1
… а может и нет. В любом случае, похоже, что есть много работ по изучению DFA.
Цуёси Ито
2
Этот вопрос недавно обсуждался в блоге сообщества .
Аарон Стерлинг

Ответы:

39

Да, это NP-Hard. Питт и Вармут показали, что нахождение наименьшего DFA, соответствующего данному образцу, не может быть аппроксимировано с точностью до для любой постоянной , если только .OPTkkP=NP

Что касается вопроса об обучении: Кернс и Валиант доказали, что вы можете кодировать RSA в DFA. Таким образом, даже если помеченные примеры исходят из равномерного распределения, возможность обобщения на будущие примеры (даже исходя из равномерного распределения) сломает RSA. Следовательно, мы думаем, что в худшем случае маркировка примеров не поможет в изучении DFA (в модели PAC). Это один из классических результатов криптографической стойкости для обучения.

Обе эти проблемы переплетаются из-за того, что мы называем теоремой Оккама о бритве . В основном это говорит о том, что если у нас есть процедура для нахождения наименьшей гипотезы из данного класса, которая согласуется с выборкой, помеченной гипотезой из того же класса, то мы можем PAC изучить этот класс. Таким образом, учитывая результат твердости RSA, мы ожидаем, что поиск наименьшего непротиворечивого DFA будет трудным в целом!

Чтобы добавить положительный результат обучения, Angluin показал, что вы можете изучать DFA, если вы создаете свои собственные примеры, но для этого требуется дополнительная способность спрашивать «верна ли моя текущая гипотеза?» Это было также основополагающим документом в обучении.

Чтобы ответить на ваш другой вопрос, все это действительно связано со сложностью Колмогорова, поскольку проблема обучения становится проще, когда каноническое представление целевого DFA имеет низкую сложность.

Лев Рейзин
источник
3
Вы победили меня с более недавним, более сильным результатом! Вы должны опубликовать лучший ответ позже !! 1 !!
Цуёси Ито
ой, извини! Я потратил достаточно времени на изучение DFA, и мне пришлось прыгнуть на это :)
Лев Рейзин
1
На всякий случай я пошутил в своем предыдущем комментарии. Конечно, я рад видеть лучший ответ!
Цуёси Ито
1
другими словами, ключевое различие между этой проблемой и регулярной минимизацией DFA заключается в наличии отрицательных примеров, да?
Суреш Венкат
1
я не понимаю без отрицательных примеров, у самого маленького непротиворечивого dfa есть только 1 состояние - состояние принятия, которое указывает на себя ...
Лев Рейзин
13

Я отвечаю на вопросы, связанные с обучением.

Эта проблема, кажется, в литературе называется «обучение DFA».

Голд [Gol78] показал, что он NP-полон, чтобы при заданном k ∈ℕ и двух конечных наборах P и N строк решить, существует ли детерминированный конечный автомат (DFA) с не более чем k состояниями, который принимает каждую строку в Р и ни одна из строк в N . В статье [PH01], похоже, обсуждаются проблемы, связанные с этой мотивацией (может быть, их будет гораздо больше; это возникло, когда я попытался найти соответствующие статьи в Google).

Ссылки

[Gol78] E Марк Золото. Сложность идентификации автоматов по заданным данным. Информация и управление , 37 (3): 302-320, июнь 1978. http://dx.doi.org/10.1016/S0019-9958(78)90562-4

[PH01] Раджеш Парех и Васант Гонавар. Изучение ДФА на простых примерах. Машинное обучение , 44 (1–2): 9–35, июль 2001 г. http://www.springerlink.com/content/kr2501h2442l8mk1/ http://www.cs.iastate.edu/~honavar/Papers/parekh- dfa.pdf

Цуёси Ито
источник
1
Спасибо за ответ, я смотрю ссылки. Могу ли я проголосовать за один из лучших ответов на этом сайте? :) Опять же, я смущен тем, что пропустил целое подполе "Обучение DFA", хотя я много лет изучал машинное обучение.
Ласло Козма
@steve: Вы можете принять только один ответ, но вы можете проголосовать столько раз, сколько захотите.
Юкка Суомела
2
Обратите внимание, что [Gold78] также заявляет, что DFA может быть изучен за полиномиальное время (в рамках обучаемости идентификации в пределе). См. Также недавнюю книгу по грамматическому выводу ( pagesperso.lina.univ-nantes.fr/~cdlh/book_webpage.html ) для обзора.
mgalle
@mgalle: Спасибо за дополнительную информацию.
Цуёси Ито
8

На протяжении всего этого обсуждения предполагалось, что нахождение минимального регулярного выражения равносильно нахождению минимального FSM, распознающего язык, но это две разные вещи. Если я правильно помню, DFA можно минимизировать за полиномиальное время, тогда как поиск минимального регулярного выражения, представляющего данный регулярный язык, сложен для PSPACE. Последнее является одним из тех результатов, которые принадлежат фольклору Теории автоматов, но чье доказательство не может быть найдено нигде. Я думаю, что это указано как упражнение в книге Пападимитру.


источник
1
Это верно, что длина регулярного выражения и количество состояний в DFA являются различными целевыми функциями. Я ответил о минимизации DFA, потому что он обладает более приятным свойством (например, существует уникальный DFA с минимальным количеством состояний), и после постановки вопроса у меня сложилось впечатление, что точная целевая функция была гибкой.
Цуёси Ито
Случайный комментарий: учитывая тот факт, что регулярное выражение размера f (n) может быть смоделировано NFA размером O (f (n)), минимизация регулярных выражений больше похожа на минимизацию NFA, что, очевидно, сложнее.
Сянь-Чи Чанг 之 之
часть этого адресована в комментариях к ответу @ keith
Лев Рейзин
2

Смотрите также этот пост переполнения стека. Похоже, что книга, которую вы ищете, - « Введение в теорию вычислений » Майкла Сипсера.

Вы задаете пару разных вопросов, поэтому берете их по одному:

Is finding a minimal Finite State Machine for a language L NP-complete?

Нет, это не так. В статье «Переполнение стека» обсуждается наивный алгоритм n ^ 2 для уменьшения FSM до минимального размера. (Работая в обратном направлении от состояний остановки, объедините состояния, которые являются «идентичными» в точном смысле.)

По-видимому (я не перешел по ссылке), для этого существует алгоритм n log n.

I have a training set of strings, how do I find the minimal FSM 
that separates the good examples from the bad?

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

Is this a good way to build a classifier?

Я бы так не сказал. Минимизация FSM не меняет его дискриминационную силу - вот в чем дело. Минимальный FSM принимает точно набор строк как любой эквивалентный неминимальный FSM.

Как правило, регулярные выражения не подходят для классификации новых данных. Для любого конечного обучающего набора вы получите RE / FSM, который соответствует только положительным примерам в этом наборе, без возможности обобщения на новые данные. Я никогда не видел подход, который пытается найти бесконечный регулярный язык, который соответствует некоторому корпусу обучения.

Для машинного обучения вам нужно что-то вроде наивного байесовского классификатора, дерева решений, нейронной сети или чего-то более экзотического. Искусственный интеллект Рассела и Норвига : современный подход - это то же самое место, где можно найти обзор методов машинного обучения (и многое, многое другое).

Сообщество
источник
2
Я не согласен с этим ответом. Если вы просто берете все положительные примеры и создаете FSM, который принимает только эти примеры и ничего больше, ваш FSM может быть огромным. С другой стороны, самый маленький FSM, который принимает все положительные примеры и не имеет отрицательных примеров, может быть намного меньше.
Юкка Суомела
3
Я думаю, что оригинальный вопрос прояснил это: «выражение, которое соответствует +, отвергает - и минимально в некотором четком смысле».
Юкка Суомела
5
@ Различие между вашим ответом и моим довольно тонкое. когда вы строите свой dfa, создавая новые состояния для каждой строки в образце, вы берете себя на другой язык, чем тот, который представлен минимальным dfa, разделяющим положительные и отрицательные примеры. поэтому алгоритм генерации dfa и его минимизации, к сожалению, этого не делает!
Лев Рейзин
1
Я не уверен, что понимаю это различие. Если у нас есть набор положительных и отрицательных примеров, у нас есть семейство языков, которые удовлетворяют этим ограничениям. для каждого есть (набор) минимальный dfas. Пока я возвращаю DFA минимального размера, какое это имеет значение, какой из этих языков я выберу.
Суреш Венкат
1
Для обучения вы хотите выбрать самый маленький DFA, потому что он обладает наилучшей способностью к обобщению. Процедура @ kieth не выберет минимальный DFA для всех этих языков, только самый маленький для языка, который привержен использованию его процедуры.
Лев Рейзин