Оценка VC-измерения

12

Что известно о следующей проблеме?

Для набора функций : f : { 0 , 1 } n{ 0 , 1 } найдите наибольшую подгруппу S C с учетом ограничения VC-Dimension ( S ) k для некоторого целого числа k .Cf:{0,1}n{0,1}SC(S)kk

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

Аарон Рот
источник
Кажется, что функции не играют роли в максимизации | S |
Суреш Венкат
Выбор функций определяет VC-размерность S. Задача состоит в том, чтобы найти как можно больший класс функций с учетом ограничения VC-размерности.
Аарон Рот
Понимаю. Таким образом, в переводе «геометрия земли», вы получаете набор диапазонов (f действует как характеристическая функция), и вы хотите самую большую коллекцию ограниченного измерения VC.
Суреш Венкат
Другая проблема в ответе на вопрос: как представлен C? Мы знаем, что максимально возможный размер равен по лемме Сауэра, и для записи хотя бы одной функции в требуется битов. O ( 2 n k ) C nSO(2nk)Cn
Суреш Венкат
1
Правильно. Я заинтересован в результатах в любом представительском режиме. Вы можете представить, что представлен какматрица, в этом случае время выполнениябыло бы `` эффективным '' (хотя не время , что требуется для исчерпывающей проверки, были ли разбиты все коллекции из точек). Если какие-либо алгоритмические результаты возможны только с помощью черного доступа к функциям в , это было бы еще лучше. 2 n × | C | 2 n × | C | 2 n × k k CC2n×|C|2n×|C|2n×kkC
Аарон Рот

Ответы:

7

Редактирование : исходная задача -Жесткого аппроксимировать , когда к = 1 , где п обозначает число наборов.n1ϵk=1n

Двойной гиперграф получаются путем обмена вершин с ребрами, и сохранением числа случаев. Проще понять проблему, когда мы заметим, что гиперграф имеет VC-размерность 1, если его двойник является кросс-свободным (для всех в A хотя бы один из P Q , P Q , Q P , ( P Q ) c пусто).P,QAPQ,PQ,QP,(PQ)c

В силу двойственности исходная задача (для ) эквивалентна тому, что с учетом гиперграфа ( V , S ) найти максимальный размер U V с ( U , { S U S S } ) кросс-свободным.k=1(V,S)UV(U,{SUSS})

S

Оригинальный ответ

k=1SSn1ϵΘ(n)

AP,QAPQ,PQ,QP,(PQ)c

G=(V,E)H=(X,S)X=VE{0}0vGTvS

{v}{ee is an edge incident to v}.

{Tv}vUUG

Но для первоначальной (первичной) проблемы, кажется, нужно еще немного подумать ... выглядит интересно!

daveagp
источник
4

Некоторая соответствующая связанная с этим работа: Оценка самого измерения VC (не говоря уже о нахождении большого подколлекции с ограниченным измерением VC) в вашем представлении является завершением LOGNP (LOGNP - это NP, ограниченная записью n битов недетерминизма). Есть также немного связанной работы по оценке и аппроксимации VC-измерения, когда представление пространства диапазонов является более компактным (см. Также ссылки внутри)

Суреш Венкат
источник