Обучение с запросами, формулы Хорна и формальные понятия

В традиционной постановке задачи обучения с учителем мы располагаем набором данных, разбитым учителем на несколько классов, и стремимся реконструировать принцип, лежащий в основе этого разбиения. Что, если данных нет, но есть сам учитель, готовый отвечать на наши вопросы? Какие вопросы и в какой последовательности нужно задавать, чтобы как можно быстрее обучиться интересующему нас понятию?
Мы рассмотрим базовые принципы обучения с запросами и разберем некоторые простые алгоритмы, работающие в такой модели. Подробнее остановимся на задаче обучения формуле Хорна, для которой существует полиномиальный алгоритм обучения с запросами. Эта задача тесно связана с задачей вычисления базиса импликативных зависимостей, выполняющихся в данных, которая изучается, в частности, в анализе формальных понятий. Можно ли превратить полиномиальный алгоритм обучения с запросами в полиномиальный алгоритм обучения по данным, эффективно имитируя учителя? Ответ пока неизвестен.