Нижние границы для обучения в запросе членства и модели контрпримеров

11

Дана Англюин ( 1987 ; pdf ) определяет модель обучения с помощью запросов на членство и теоретических запросов (контрпримеры к предложенной функции). Она показывает, что регулярный язык, представленный минимальным DFA из состояний, может быть изучен за полиномиальное время (где предложенные функции - DFA) с запросами на членство и не более теоретическими запросами ( размер самого большого контрпримера, предоставленного репетитором). К сожалению, она не обсуждает нижние границы.NО(мN2)N-1м

Мы можем немного обобщить модель, предполагая магический наставник, который может проверить равенство между произвольными функциями и предоставить контрпримеры, если они различны. Тогда мы можем спросить, насколько сложно выучить классы больше, чем обычные языки. Я заинтересован в этом обобщении и оригинальном ограничении на обычные языки.

Существуют ли какие-либо известные нижние границы для количества запросов в модели членства и контрпримеров?

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

Если нижних границ нет: существуют ли известные барьеры для доказательства нижних границ запросов в этой модели?


Смежные вопросы

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

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

Ответы:

11

Да, некоторые нижние границы известны. Например, предполагая, что , вы не сможете даже правильно выучить трижды прочитанные формулы DNF за полиномиальное время. Существует целая статья, в которой описываются такие результаты по твердости с использованием так называемой «проблемы представления».NпсоNп

О(N)О(N2+Nжурналм)

Один простой способ получить нижние оценки - теория информации. Вы можете выяснить, сколько существует различных целей и сколько битов дает запрос и т. Д. Эти верхние границы близки, но их нет. Есть также вопросы, о которых нужно подумать относительно того, как «контрпримеры» попадают к ученику. Правильно подобранный контрпример может дать достаточно много информации.

Обновление к обсуждению выше : Angluin и Dohrn рассматривают вопрос обучения со случайными контрпримерами в недавней статье .

Лев Рейзин
источник
Спасибо за ответ! Вы не возражаете, если я дам ваш ответ на мой связанный вопрос по связанному вопросу (со ссылками сюда)? Или вы планируете создать учетную запись CS.SE? Я полностью согласен с пунктом 3, я дурачился с требованием, чтобы преподаватель дал минимальный контрпример, и обучение, кажется, стало намного легче.
Артем Казнатчеев
Нет проблем! И не стесняйтесь писать на связанный вопрос CS.SE.
Лев Рейзин
Я прочитал соответствующую часть диссертации Шапира (раздел 5.4.5) и подытожил улучшение , надеюсь, я понял суть правильно. Я посмотрю более внимательно на нижнюю статью, которую вы цитируете позже на этой неделе: D.
Артем Казнатчеев
Здорово. Я бы проголосовал, если бы у меня был аккаунт в CS.SE :)
Лев Рейзин