Изменить: Поскольку я не получил никаких ответов / комментариев в течение недели, я хотел бы добавить, что я рад услышать что-нибудь о проблеме. Я не работаю в этом районе, поэтому, даже если это простое наблюдение, я могу не знать его. Даже комментарий типа «Я работаю в этом районе, но я не видел подобной характеристики» был бы полезен!
Фон:
Существует несколько хорошо изученных моделей обучения в теории обучения (например, обучение по программе PAC, онлайн-обучение, точное обучение с запросами на членство / эквивалентность).
Например, в обучении PAC примерная сложность концептуального класса имеет хорошую комбинаторную характеристику с точки зрения измерения VC класса. Поэтому, если мы хотим выучить класс с постоянной точностью и уверенностью, это можно сделать с помощью примеров , где - это измерение VC. (Обратите внимание, что мы говорим о сложности образца, а не о сложности времени.) Существует также более точная характеристика с точки зрения точности и достоверности. Точно так же модель онлайн-обучения, связанная с ошибками, имеет хорошую комбинаторную характеристику.д
Вопрос:
Я хочу знать, известен ли подобный результат для модели точного обучения с запросами на членство. Модель определяется следующим образом: у нас есть доступ к черному ящику, который на входе дает вам . Мы знаем , что происходит от некоторой концепции класса . Мы хотим определить с минимально возможным количеством запросов.
Существует ли комбинаторный параметр концептуального класса который характеризует количество запросов, необходимых для изучения концепта в модели точного обучения с запросами на членство?
Что я знаю:
Наилучшая подобная характеристика, которую я нашел, содержится в этой работе Серведио и Гортлера , использующей параметр, который они приписывают Bshouty, Cleve, Gavaldà, Kannan и Tamon . Они определяют комбинаторный параметр, называемый , где - это концептуальный класс, который имеет следующие свойства. (Пусть будет оптимальным количеством запросов, необходимых для изучения в этой модели.)
Эта характеристика почти жесткая. Однако между верхней и нижней границами может быть квадратичный зазор. Например, если , то нижняя граница равна , но верхняя граница равна . (Я также думаю, что этот разрыв достижим, т. Е. Существует концептуальный класс, для которого нижние границы равны , но верхняя граница равна .)Ω ( k ) O ( k 2 ) Ω ( k ) O ( k 2 )
источник
Ответы:
Чтобы понять суть примера анонимного лося, рассмотрим концептуальный класс, который состоит из функций, которые выводят 1 только в одну точку в {0,1} ^ n. Класс имеет размер 2 ^ n, и в худшем случае требуется 2 ^ n запросов. Взгляните на наихудший вариант Teaching Dimension (Goldman & Schapire), который дает нечто похожее на то, что вы ищете.
источник
Я не знаю такой характеристики. Тем не менее, стоит отметить, что практически для любого концептуального класса необходимо запрашивать все точки. Чтобы увидеть это, рассмотрим концептуальный класс, который состоит из всех n-мерных логических векторов с весом Хэмминга 1. Этот концептуальный класс, очевидно, требует изучения n запросов, что равно его мощности. Вероятно, вы можете обобщить это наблюдение, чтобы получить, что почти любой концептуальный класс также требует выполнения всех запросов.
Я подозреваю, что с учетом концептуального класса C в качестве входных данных трудно определить сложность точного изучения концептуального класса с помощью запросов членства или даже приблизить его, скажем, до константы. Это дало бы некоторое указание на то, что «хорошей» комбинаторной характеристики не существует. Если вы хотите доказать такой результат NP-твердости, но попробуйте и не можете написать здесь, и я посмотрю, смогу ли я это выяснить (у меня есть некоторые идеи).
источник
Хотя другие указали на ответ. Я подумал, что могу сделать это самодостаточным и показать, почему педагогическое измерение - это ответ.
Рассмотрим понятие класса над входной пространства . Набор элементов называется учение набор для концепции , если является единственной концепцией в в соответствии с .ХС Икс f f CS⊆ X е е С S
Пусть будет множеством всех обучающих наборов для и определим TD - обучающее измерение . т.е. мощность наименьшего обучающего набора TS в . Аналогично, рассмотрим ТД макс TD , чтобы быть учение измерение .f ( f , C ) = m i n { | S | | S ∈ Т ( е ) } е м я н ( е ) Т ( е ) ( С ) = F ∈ C ( F , С ) СT(ф) е (ф,C) = m i n { | S | | S∈ T(ф) } е м я н(ф) T(ф) ( C) = е∈ C ( ф, C) С
Минимальное количество запросов, необходимое для идентификации - это TD . Это происходит, когда стратегия запроса использует последовательность TS . Что касается любого меньшего количества запросов, у нас есть по крайней мере две концепции, согласующиеся с ним. И TD является минимумом для любого .( f , C ) m i n ( f ) ( C ) fе ( ф, C) м я н( ф) ( C) е
источник