VC размерность полиномов над тропическими полукольцами?

14

Как и в этом вопросе, я заинтересован в BPP по сравнению с P / poly задачи для тропических (max,+) и (min,+) цепей. Этот вопрос сводится к показу верхних оценок размерности многочленов VC над тропическими полукольцами (см. Теорему 2 ниже).

Пусть R полукольцо. Нулевой шаблон из последовательности (f1,,fm) из m многочленов R[x1,,xn] является подмножество S{1,,m} , для которых существует xRn и yR такой, что для всех , е I ( х ) = у тогдатолько тогда я S . То есть, графики именнотех многочленов F I с I S должен попасть в точку ( х , у ) R п + 1 . («Нулевой шаблон», поскольку условие f i ( x ) = y можно заменить на f i ( x ) - y = 0. ) Пустьi=1,,mfi(x)=yiSfiiS(x,y)Rn+1fi(x)=yfi(x)y=0 = максимально возможное число шаблонов нулей последовательности из m многочленов степени не более d . Следовательно, 0 Z ( m ) 2 m . Измерение Вапника-Червоненкисиз степени д многочленов В С ( п , д ) : = макс { м : Z ( м ) = 2 м } . Z(m)md0Z(m)2mdVC(n,d):=max{m:Z(m)=2m}

Примечание: Обычно размерность VC определяется для семейства множеств как наибольшая мощность | S | множества S таким образом, что { F S : F F } = 2 S . Для того, чтобы вписаться в эту раму, можно связать с каждой парой ( х , у ) R п + 1 множество Р х , у всех многочленов ф степени D , для которых F (F|S|S{FS:FF}=2S(x,y)Rn+1Fx,yfd имеет место. Тогда размерность VC семейства F всех таких множеств F x , y точно равна V C ( n , d ) . f(x)=yFFx,yVC(n,d)

Тривиальная верхняя оценка равна m n log | R | (нам нужно по крайней мере 2 m различных векторов x R n, чтобы иметь все 2 m возможных шаблонов), но это бесполезно в бесконечных полукольцах. Чтобы иметь хорошие верхние оценки на размерность VC, нам нужны хорошие верхние оценки на Z ( m ) . Над полями такие границы известны.m=VC(n,d)mnlog|R|2mxRn2mZ(m)

Теорема 1: по любому полю имеем Z ( m ) ( m d + nR . Z(m)(md+nn)
Подобные верхние границы были ранее доказаны Милнором , Хайнцем и Уорреном ; их доказательства используют тяжелые методы из реальной алгебраической геометрии. Напротив, доказательство теоремы 1 на полстраницы Роняй, Бабая и Ганапати (которое мы приводим ниже) представляет собой простое применение линейной алгебры.

Глядя на небольшой «S , удовлетворяющие ( м d + пm, получаем, что VC(n,d)=O(nlogd)выполняется для любогополя. С учетомБПП(md+nn)<2mVC(n,d)=O(nlogd)BPP против / р ø л у , здесь важно , что размерность только логарифмическая в степени д . Это важно, потому что схемы полиномиального размера могут вычислять полиномы экспоненциальной степени, а также потому, что это результат Haussler в обучении PAC (следствие 2 на стр. 114Ppolydэта статья ) дает следующее (где мы предполагаем, что детерминированным схемам разрешено использовать большинство голосов для вывода их значений).

Теорема 2: выполняется для цепей над любым полукольцом R , где V C ( n , d ) является полиномиальным только от n и log d . BPPP/polyRVC(n,d)nlogd
Смотрите здесь о том, как из результата Хаусслера вытекает теорема 2.

В частности, по теореме 1 имеет место над любым полем. (Здесь интересен только случай бесконечных полей: для конечных работают гораздо более простые аргументы: тогда работает черновский предел.) Но как насчет (бесконечных) полуколец, которые не являются полями или даже не кольцами? Воодушевленные динамическим программированием, я в основном интересуюсь тропическими ( max , + ) и ( min , + ) полукольцами, но интересны и другие «неполевые» (бесконечные) полукольца. Обратите внимание, что за ( максBPPP/poly(max,+)(min,+) полукольцо, полином f ( x ) = a A c a n i = 1 x a i i с A N и c aR , превращается в задачу максимизации f ( x ) = max a A { c a + a 1 x 1 + a 2 x 2(max,+)f(x)=aAcai=1nxiaiANcaR ; степень F (как принято) максимум в 1 + + в п над всем в A .f(x)=maxaA {ca+a1x1+a2x2++anxn}fa1++anaA

Вопрос: Является ли размерность ВК полиномов степени над полиномом тропических полуколец от n log d ? dnlogd

Я допускаю, что это может быть довольно сложный вопрос, чтобы ожидать быстрого ответа: тропическая алгебра довольно "сумасшедшая". Но, возможно, у кого-то есть идеи о том, почему (если таковые имеются) тропические полиномы могут давать больше нулевых шаблонов, чем реальных полиномов? Или почему они "не должны"? Или некоторые связанные ссылки.

Или, может быть, доказательство Бабая, Роняи и Ганапати (см. Ниже) можно каким-то образом «исказить» для работы над тропическими полукольцами? Или над любыми другими бесконечными полукольцами (которые не являются полями)?

Доказательство теоремы 1. Предположим, что последовательность имеет p различных нулевых шаблонов, и пусть v 1 , , v pR n являются свидетелями этих нулевых шаблонов. Пусть S i = { k : f k ( v i ) 0 } - нулевой шаблон, засвидетельствованный i-м вектором v i , и рассмотрим полиномы g(f1,,fm)pv1,,vpRnSi={k:fk(vi)0}ivigi:=kSifk . Мы утверждаем, что эти многочлены линейно независимы от нашего поля. Это утверждение завершает доказательство теоремы, поскольку каждый имеет степень не более D : = m d , а размерность пространства многочленов степени не более D равна ( n + D).giD:=mdD . Чтобы доказать утверждение, достаточно отметить, чтоgi(vj)0тогда и только тогда, когдаSiSj. Предположим, что существует нетривиальное линейное отношение λ1gi(x)++λpgp(x)=0. Пустьjбудет индексом таким, что| Sj| является минимальным средиSяс(n+DD)gi(vj)0SiSjλ1gi(x)++λpgp(x)=0j|Sj|Siλi0. Substitute vj in the relation. While λjgj(vj)0, we have λigi(vj)=0 for all ij, a contradiction.

Stasys
источник

Ответы:

9

I've realized that the answer to my question is - yes: the VC dimension of degree d polynomials on n variables over any tropical semiring is at most a constant times n2log(n+d). This can be shown using Theorem 1 above. See here for details. So, BPP P / poly также подходит для тропических цепей и, следовательно, также для «чистых» алгоритмов динамического программирования.


NB (добавлено 25.06.2019) В то же время, я решил проблему полностью в этой статье. In such a generality, which I haven't even dreamed at the beginning. Tropical case is here just a very, very special case. And even more curiously: by just an appropriate combination of already know (deep in any respect) results of other authors.

Что еще нужно сделать в этом (BPP против P / poly) направлении? Помимо уменьшения размера получающихся детерминированных схем (интересный вопрос сам по себе).

Стасис
источник