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

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

Пусть $R$ полукольцо. Нулевой шаблон из последовательности $(f_1,\ldots,f_m)$ из $m$ многочленов $R[x_1,\ldots,x_n]$ является подмножество $S\subseteq \{1,\ldots,m\}$ , для которых существует $x\in R^n$ и $y\in R$ такой, что для всех , тогдатолько тогда . То есть, графики именнотех многочленов с должен попасть в точку . («Нулевой шаблон», поскольку условие можно заменить на ) Пусть $i=1,\ldots,m$ $f_i(x)= y$ $i\in S$ $f_i$ $i\in S$ $(x,y)\in R^{n+1}$ $f_i(x)=y$ $f_i(x)-y=0$ = максимально возможное число шаблонов нулей последовательности из многочленов степени не более . Следовательно, . Измерение Вапника-Червоненкисиз степени многочленов . $Z(m)$ $m$ $d$ $0\leq Z(m)\leq 2^m$ $d$ $VC(n,d) := \max\{m\colon Z(m)=2^m\}$

Примечание: Обычно размерность VC определяется для семейства множеств как наибольшая мощность множества таким образом, что . Для того, чтобы вписаться в эту раму, можно связать с каждой парой множество всех многочленов степени , для которых ${\cal F}$ $|S|$ $S$ $\{F\cap S\colon F\in{\cal F}\}=2^S$ $(x,y)\in R^{n+1}$ $F_{x,y}$ $f$ $\leq d$ имеет место. Тогда размерность VC семейства всех таких множеств точно равна . $f(x)=y$ ${\cal F}$ $F_{x,y}$ $VC(n,d)$

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

Теорема 1: по любому полю имеем $R$ . $Z(m)\leq \binom{md+n}{n}$

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

Глядя на небольшой «S , удовлетворяющие $m$ , получаем, что выполняется для любогополя. С учетом $\binom{md+n}{n} < 2^m$ $VC(n,d)=O(n\log d)$ $\mathbf{BPP}$ против / , здесь важно , что размерность только логарифмическая в степени . Это важно, потому что схемы полиномиального размера могут вычислять полиномы экспоненциальной степени, а также потому, что это результат Haussler в обучении PAC (следствие 2 на стр. 114 $\mathbf{P}$ $\mathrm{poly}$ $d$ эта статья ) дает следующее (где мы предполагаем, что детерминированным схемам разрешено использовать большинство голосов для вывода их значений).

Теорема 2: выполняется для цепей над любым полукольцом , где является полиномиальным только от и . $\mathbf{BPP}\subseteq \mathbf{P}/\mathrm{poly}$ $R$ $VC(n,d)$ $n$ $\log d$

Смотрите здесь о том, как из результата Хаусслера вытекает теорема 2.

В частности, по теореме 1 имеет место над любым полем. (Здесь интересен только случай бесконечных полей: для конечных работают гораздо более простые аргументы: тогда работает черновский предел.) Но как насчет (бесконечных) полуколец, которые не являются полями или даже не кольцами? Воодушевленные динамическим программированием, я в основном интересуюсь тропическими и полукольцами, но интересны и другие «неполевые» (бесконечные) полукольца. Обратите внимание, что за $\mathbf{BPP}\subseteq \mathbf{P}/\mathrm{poly}$ $(\max,+)$ $(\min,+)$ полукольцо, полином с и , превращается в задачу максимизации $(\max,+)$ $f(x)=\sum_{a\in A} c_a\prod_{i=1}^n x_i^{a_i}$ $A\subseteq\mathbb{N}$ $c_a\in \mathbb{R}$ ; степень (как принято) максимум над всем . $f(x)=\max_{a\in A}\ \{c_a+a_1x_1+a_2x_2+\cdots+a_nx_n\}$ $f$ $a_1+\cdots+a_n$ $a\in A$

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

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

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

Доказательство теоремы 1. Предположим, что последовательность имеет различных нулевых шаблонов, и пусть являются свидетелями этих нулевых шаблонов. Пусть - нулевой шаблон, засвидетельствованный вектором , и рассмотрим полиномы $(f_1,\ldots,f_m)$ $p$ $v_1,\ldots,v_p\in R^n$ $S_i=\{k\colon f_k(v_i)\neq 0\}$ $i$ $v_i$ $g_i:=\prod_{k\in S_i}f_k$ . Мы утверждаем, что эти многочлены линейно независимы от нашего поля. Это утверждение завершает доказательство теоремы, поскольку каждый имеет степень не более , а размерность пространства многочленов степени не более равна $g_i$ $D:=md$ $D$ . Чтобы доказать утверждение, достаточно отметить, чтотогда и только тогда, когда. Предположим, что существует нетривиальное линейное отношение . Пустьбудет индексом таким, чтоявляется минимальным средис $\binom{n+D}{D}$ $g_i(v_j)\neq 0$ $S_i\subseteq S_j$ $\lambda_1 g_i(x)+\cdots+\lambda_p g_p(x)=0$ $j$ $|S_j|$ $S_i$ $\lambda_i\neq 0$ . Substitute $v_j$ in the relation. While $\lambda_jg_j(v_j)\neq 0$ , we have $\lambda_ig_i(v_j)=0$ for all $i\neq j$ , a contradiction. $\Box$

co.combinatorics circuit-complexity algebraic-complexity arithmetic-circuits vc-dimension Stasys
источник

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

Ответы: