Есть ли улучшения в алгоритме Даны Англюин для изучения регулярных наборов

33

В своей основополагающей работе 1987 года Дана Англуин представляет алгоритм полиномиального времени для изучения DFA из запросов членства и теоретических запросов (контрпримеры к предлагаемому DFA).

Она показывает, что если вы пытаетесь выучить минимальный DFA с состояниями, а ваш самый большой контрпример имеет длину , то вам нужно выполнить членских запросов и не более теоретических запросов.m O ( m n 2 ) n - 1NмО(мN2)N-1

Были ли значительные улучшения в количестве запросов, необходимых для изучения регулярного набора?


Ссылки и связанные вопросы

Артем Казнатчеев
источник
Надеюсь, @DominikFreydenberger заглянет в какой-то момент в будущем. Он узнает.
Рафаэль
2
Я подозреваю, что @LevReyzin тоже знал бы ответ ... и именно поэтому я изначально задумывался над тем, чтобы спросить о cstheory, но я думаю, что должен помочь в развитии этого нового сайта.
Артем Казнатчеев
Не ответ на вопрос, но все еще может быть полезным: [ citeulike.org/user/erelsegal-halevi/article/9275508 Универсальное ядро ​​для изучения регулярных языков]
Эрел Сигал-Халеви,
спасибо за ссылку @Erel, но я не понимаю, как это связано. Универсальное ядро ​​Конторовича не является эффективно вычисляемым, и модель обучения не имеет контрпримеров.
Артем Казнатчеев

Ответы:

15

В своем ответе на cstheory.SE Лев Рейзин направил меня к тезису Роберта Шапира, который улучшает привязку к запросам на членство в разделе 5.4.5. Количество контрпримеров запросов остается неизменным. Алгоритм, который использует Schapire, отличается от того, что он делает после контрпримерного запроса.О(N2+Nжурналм)


Эскиз улучшения

На самом высоком уровне, Шапире заставляет из алгоритма Англуина иметь дополнительное условие, что для закрытых и каждого если то . Это гарантирует, что , а также делает консистенцию свойство алгоритма Angluin тривиальным удовлетворить. Чтобы обеспечить это, он должен по-разному обрабатывать результаты контрпримеров.( С , Е , Т ) с 1 , s 2S s 1с 2 г о ш ( с 1 ) г о ш ( с 2 ) | S | n(S,Е,T)(S,Е,T)s1,s2Ss1s2ровес(s1)ровес(s2)|S|N

Учитывая контрпример , Angluin просто добавил и все префиксы к . Schapire делает что - то более тонкое путем вместо добавления одного элемента в . Этот новый сделает не закрытым в смысле Англуина, а обновление, чтобы получить замыкание, введет по крайней мере одну новую строку в , сохраняя при этом все строки различными. Условие на :z S e E e ( S , E , T ) S eZZSеЕе(S,Е,T)Sе

s,s'S,aΣулицаровес(s)знак равноровес(s'a)а такжео(δ(Q0,sе))о(δ(Q0,s'aе))

Где - выходная функция, - начальное состояние и правило обновления истинного «неизвестного» DFA. Другими словами, должен служить свидетелем, чтобы отличить будущее от .q 0 δ e s s aоQ0δеss'a

Чтобы выяснить это из мы выполняем двоичный поиск, чтобы выяснить подстроку такую ​​что итакое, что поведение нашей предполагаемой машины отличается в зависимости от одного входного символа. Более подробно, мы позволим быть строкой, соответствующей состоянию, достигнутому в нашей предполагаемой машине, после . Мы используем бинарный поиск (отсюда ), чтобы найти , для которого . Другими словами,z r i z = p i r i 0 | р я | = я < | z | s i p i log m k o ( δ ( q 0 , s k r k ) ) o ( δ ( q 0 , s k + 1 r k + 1 ) r kеZряZзнак равнопяря0|пя|знак равноя<|Z|sяпяжурналмКо(δ(Q0,sКрК))о(δ(Q0,sК+1рК+1) еЕрК+1различает два государства наши машины высказал предположение находит эквивалентные и , таким образом , удовлетворяет условию на , поэтому мы добавим его в .еЕ

Артем Казнатчеев
источник
5

Я не знаю, актуален ли мой ответ. Недавно была описана реализация нового алгоритма под названием Observation Pack или, при некоторых обстоятельствах, дерева дискриминации Фалька Ховара. Этот алгоритм похож на L *, но использует Rivest-Shapire или другой метод (см. Steffen и Isberner) для разложения контрпримеров; и он использует структуру данных, дерево различения (двоичное дерево) для эффективного «просеивания», а именно вставки A-перехода (где A - каждый символ алфавита) нового состояния, найденного до тех пор, пока не будет закрытости , Этот алгоритм существует в двух версиях: OneGlobally и OneLocally в зависимости от того, добавлен ли суффикс, основанный в разложении, к каждому компоненту или нет (соотношение за алгоритмом состоит в том, что все префиксы в компоненте эквивалентны короткому префиксу и представляют одно и то же состояние в целевом объекте в соответствии с найденными суффиксами в это время. Позже с новым контрпримером будет найден новый суффикс, который различает как минимум 2 префикса одного и того же компонента. Это вызывает разделение этого компонента на два компонента). С OneLocally гораздо меньше запросов на членство, но количество запросов на эквивалентность может резко возрасти с большим целевым DFA. Скорее OneGlobally имеет количество запросов на членство всегда ниже, чем L * (но больше, чем OneLocally) и такое же количество запросов эквивалентностей, что и L * Позже с новым контрпримером будет найден новый суффикс, который различает как минимум 2 префикса одного и того же компонента. Это вызывает разделение этого компонента на два компонента). С OneLocally гораздо меньше запросов на членство, но количество запросов на эквивалентность может резко возрасти с большим целевым DFA. Скорее OneGlobally имеет количество запросов на членство всегда ниже, чем L * (но больше, чем OneLocally) и такое же количество запросов эквивалентностей, что и L * Позже с новым контрпримером будет найден новый суффикс, который различает как минимум 2 префикса одного и того же компонента. Это вызывает разделение этого компонента на два компонента). С OneLocally гораздо меньше запросов на членство, но количество запросов на эквивалентность может резко возрасти с большим целевым DFA. Скорее OneGlobally имеет количество запросов на членство всегда ниже, чем L * (но больше, чем OneLocally) и такое же количество запросов эквивалентностей, что и L *

Я знаю, что существует и другой алгоритм: алгоритм TTT, который лучше, чем Observation Pack, но я не очень хорошо его знаю. Алгоритм TTT должен быть современным

Umbert
источник
Спасибо за этот ответ! У вас есть справочный документ по алгоритму Ховара и ТТТ?
Артем Казнатчеев
Это для ссылки пакета наблюдений Ховар, а для ссылки алгоритма TTT - TTT Реализацию можно найти в LearLib (пакет наблюдений называется там Дискриминационным деревом)
Umbert