Комбинаторная характеристика точного обучения с запросами на членство

15

Изменить: Поскольку я не получил никаких ответов / комментариев в течение недели, я хотел бы добавить, что я рад услышать что-нибудь о проблеме. Я не работаю в этом районе, поэтому, даже если это простое наблюдение, я могу не знать его. Даже комментарий типа «Я работаю в этом районе, но я не видел подобной характеристики» был бы полезен!

Фон:

Существует несколько хорошо изученных моделей обучения в теории обучения (например, обучение по программе PAC, онлайн-обучение, точное обучение с запросами на членство / эквивалентность).

Например, в обучении PAC примерная сложность концептуального класса имеет хорошую комбинаторную характеристику с точки зрения измерения VC класса. Поэтому, если мы хотим выучить класс с постоянной точностью и уверенностью, это можно сделать с помощью примеров , где - это измерение VC. (Обратите внимание, что мы говорим о сложности образца, а не о сложности времени.) Существует также более точная характеристика с точки зрения точности и достоверности. Точно так же модель онлайн-обучения, связанная с ошибками, имеет хорошую комбинаторную характеристику.дΘ(d)d

Вопрос:

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

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

Что я знаю:

Наилучшая подобная характеристика, которую я нашел, содержится в этой работе Серведио и Гортлера , использующей параметр, который они приписывают Bshouty, Cleve, Gavaldà, Kannan и Tamon . Они определяют комбинаторный параметр, называемый γС , где С - это концептуальный класс, который имеет следующие свойства. (Пусть QС будет оптимальным количеством запросов, необходимых для изучения С в этой модели.)

QСзнак равноΩ(1/γС)QСзнак равноΩ(журнал|С|)QСзнак равноО(журнал|С|/γС)

Эта характеристика почти жесткая. Однако между верхней и нижней границами может быть квадратичный зазор. Например, если , то нижняя граница равна , но верхняя граница равна . (Я также думаю, что этот разрыв достижим, т. Е. Существует концептуальный класс, для которого нижние границы равны , но верхняя граница равна .)Ω ( k ) O ( k 2 ) Ω ( k ) O ( k 2 )1/γСзнак равножурнал|С|знак равноКΩ(К)О(К2)Ω(К)О(К2)

Робин Котари
источник
1
«Измерение стога сена» характеризует сложность запроса оптимизации функции: cis.upenn.edu/~mkearns/papers/haystack.pdf. Это отличается от того, что вы хотите, но вам может понравиться связанная работа, в которой обсуждается, что известно о характеристике сложность запроса точного обучения.
Аарон Рот

Ответы:

6

Чтобы понять суть примера анонимного лося, рассмотрим концептуальный класс, который состоит из функций, которые выводят 1 только в одну точку в {0,1} ^ n. Класс имеет размер 2 ^ n, и в худшем случае требуется 2 ^ n запросов. Взгляните на наихудший вариант Teaching Dimension (Goldman & Schapire), который дает нечто похожее на то, что вы ищете.

анонимный гусь
источник
1
Благодарность! Поиск Обучающего Измерения привел меня к Расширенному Обучающему Измерению, которое аналогично комбинаторному параметру, который я упомянул в вопросе, а затем привело меня ко многим другим интересным работам по этой теме.
Робин Котари
4

Я не знаю такой характеристики. Тем не менее, стоит отметить, что практически для любого концептуального класса необходимо запрашивать все точки. Чтобы увидеть это, рассмотрим концептуальный класс, который состоит из всех n-мерных логических векторов с весом Хэмминга 1. Этот концептуальный класс, очевидно, требует изучения n запросов, что равно его мощности. Вероятно, вы можете обобщить это наблюдение, чтобы получить, что почти любой концептуальный класс также требует выполнения всех запросов.

Я подозреваю, что с учетом концептуального класса C в качестве входных данных трудно определить сложность точного изучения концептуального класса с помощью запросов членства или даже приблизить его, скажем, до константы. Это дало бы некоторое указание на то, что «хорошей» комбинаторной характеристики не существует. Если вы хотите доказать такой результат NP-твердости, но попробуйте и не можете написать здесь, и я посмотрю, смогу ли я это выяснить (у меня есть некоторые идеи).

анонимный лось
источник
1
Спасибо за ответ. Даже если верно, что почти все концептуальные классы (при некотором разумном распределении по классам) трудно выучить, некоторые классы легко выучить, и было бы интересно иметь комбинаторный параметр, который характеризует это. Я не против, если параметр трудно вычислить. Даже известно, что измерение VC не является эффективно вычисляемым.
Робин Котари
1

Хотя другие указали на ответ. Я подумал, что могу сделать это самодостаточным и показать, почему педагогическое измерение - это ответ.

Рассмотрим понятие класса над входной пространства . Набор элементов называется учение набор для концепции , если является единственной концепцией в в соответствии с .ХСИксf f CSИксееСS

Пусть будет множеством всех обучающих наборов для и определим TD - обучающее измерение . т.е. мощность наименьшего обучающего набора TS в . Аналогично, рассмотрим ТД макс TD , чтобы быть учение измерение .f ( f , C ) = m i n { | S | | S Т ( е ) } е м я н ( е ) Т ( е ) ( С ) = F C ( F , С ) СT(е)е(е,С)знак равномяN{ |S| | ST(е)}емяN(е)T(е)(С)знак равноеС(е,С)С

Минимальное количество запросов, необходимое для идентификации - это TD . Это происходит, когда стратегия запроса использует последовательность TS . Что касается любого меньшего количества запросов, у нас есть по крайней мере две концепции, согласующиеся с ним. И TD является минимумом для любого .( f , C ) m i n ( f ) ( C ) fе(е,С)мяN(е)(С)е

seteropere
источник
еее
@RobinKothari TD нижняя граница минимального количества запросов в любом MQ-алгоритме. На практике не может быть алгоритма, который слепо достигает этой границы без обмана или хитростей кода. В статье Angluin «Queries Revisited» она обсуждала параметр MQ, представляющий количество запросов, необходимых для лучшего MQ-алгоритма в худшем случае. Я не помню его детали, но, конечно, TD <= MQ.
Четверг
1
Что меня интересовало (когда я задавал этот вопрос), так это параметр, характеризующий точное обучение с помощью запросов на членство. Это должна быть верхняя и нижняя граница. Я привел пример параметра, который достигает этого (с точностью до log | C | фактора) в вопросе. У меня был вопрос, известно ли что-то лучшее.
Робин Котари