Dimension VC des polynômes sur semirings tropicaux?

14

Comme dans cette question, je suis intéressé par le problème vs / pour les circuits tropicaux et (\ min, +) . Cette question se réduit à montrer les limites supérieures de la dimension VC des polynômes sur les semirings tropicaux (voir le théorème 2 ci-dessous). BPPPpoly (max,+)(min,+)

Soit R un semiring. Un modèle nul d'une séquence (f1,,fm) de m polynômes dans R[x1,,xn] est un sous-ensemble S{1,,m} pour lequel il existe xRn et yR tel que pour tout i=1,,m , fi(x)=y ssi iS . Autrement dit, les graphiques de ces polynômes fi avec iS doivent atteindre le point (x,y)Rn+1 . ("Zero-pattern" car la condition fi(x)=y peut être remplacée par fi(x)y=0 ) SoitZ(m) = le nombre maximum possible de motifs zéro d'une séquence de m polynômes de degré au plus d . Par conséquent, 0Z(m)2m . La dimension Vapnik-Chervonenkis des polynômes de degré d est VC(n,d):=max{m:Z(m)=2m} .

Remarque: Habituellement, la dimension VC est définie pour une famille F d'ensembles comme la plus grande cardinalité |S|d'un ensemble S tel que {FS:FF}=2S . Pour tenir dans ce cadre, on peut associer à chaque paire (x,y)Rn+1 l'ensemble Fx,y de tous les polynômes de f degré d pour lesquels f(x)=y tient. Alors la dimension VC de la famille F de tous ces ensembles Fx,y est exactement VC(n,d) .

Une borne supérieure triviale sur m=VC(n,d) est mnlog|R|(nous avons besoin d'au moins 2m vecteurs distincts xRn pour avoir tous les 2m motifs possibles), mais cela est inutile dans les demi-tours infinis. Pour avoir de bonnes limites supérieures sur la dimension VC, nous avons besoin de bonnes limites supérieures sur Z(m) . Au-dessus des champs , de telles limites sont connues.

Théorème 1: Sur tout champ R , nous avons Z(m)(md+nn) .
Des limites supérieures similaires ont été précédemment démontrées par Milnor , Heintz et Warren ; leurs preuves utilisent des techniques lourdes issues de la géométrie algébrique réelle. En revanche, une preuve d'une demi-page du Théorème 1 de Ronyai, Babai et Ganapathy (que nous donnons ci-dessous) est une simple application d'algèbre linéaire.

En recherchant de petits satisfaisant , nous obtenons que maintient sur n'importe quel champ . Au vu de vs / , il est important ici que la dimension soit uniquement logarithmique au degré . Ceci est important parce que les circuits de taille polynomiale peuvent calculer des polynômes de degré exponentiel, et parce qu'un résultat de Haussler dans l'apprentissage PAC (Corollaire 2 à la page 114 de ce document ) donne ce qui suit (où nous supposons que les circuits déterministes sont autorisés à utiliser le vote majoritaire pour afficher leurs valeurs). m(md+nn)<2mVC(n,d)=O(nlogd)BPPPpolyd

Théorème 2: BPPP/poly est valable pour les circuits sur n'importe quel R semi-conducteur R, où VC(n,d) n'est que polynôme dans n et logd .
Voir ici comment le résultat de Haussler implique le théorème 2.

En particulier, selon le théorème 1, tient sur n'importe quel champ. (Intéressant n'est ici que le cas des champs infinis : pour les champs finis, les arguments beaucoup plus simples fonctionnent: Chernoff lié alors fait le travail.) Mais qu'en est-il des demi-tours (infinis) qui ne sont pas des champs, ou même pas des anneaux? Motivé par la programmation dynamique, je m'intéresse principalement aux demi-tours tropicaux et , mais d'autres demi-tours "non-champ" (infinis) sont également intéressants. Notez que, sur le semi-cercle , un polynôme avec etBPPP/poly(max,+)(min,+)(max,+)f(x)=aAcai=1nxiaiANcaR , se transforme en problème de maximisation ; le degré de est (comme d' habitude) le maximum de sur l' ensemble .f(x)=maxaA {ca+a1x1+a2x2++anxn}fa1++anaA

Question: La dimension VC des polynômes degré sur les semirings tropicaux est-elle polynomiale dans ? dnlogd

J'avoue, cela peut être une question assez difficile à attendre une réponse rapide: l'algèbre tropicale est plutôt "folle". Mais peut-être que quelqu'un a des idées sur pourquoi (le cas échéant) les polynômes tropicaux pourraient produire plus de schémas nuls que les polynômes réels? Ou pourquoi ils "ne devraient pas"? Ou quelques références connexes.

Ou, peut-être, la preuve de Babai, Ronyai et Ganapathy (ci-dessous) peut être en quelque sorte "tordue" pour fonctionner sur des semirings tropicaux? Ou sur tout autre demi-cercle infini (qui ne sont pas des champs)?

Preuve du théorème 1: Supposons qu'une séquence a motifs différents et laissez être témoins de ces motifs zéro. Soit un zéro mis par le -ème vecteur , et considérons les polynômes . Nous affirmons que ces polynômes sont linéairement indépendants sur notre champ. Cette affirmation complète la preuve du théorème puisque chaque a un degré au plus , et la dimension de l'espace des polynômes de degré au plus est(f1,,fm)pv1,,vpRnSi={k:fk(vi)0}ivigi:=kSifkgiD:=mdD(n+DD). Pour prouver cette affirmation, il suffit de noter que si et seulement si . Supposons au contraire qu'il existe une relation linéaire non triviale . Soit un indice tel queest minime parmi les avec . Remplacez dans la relation. Alors que , nous avons pour tout , une contradiction. gi(vj)0SiSjλ1gi(x)++λpgp(x)=0j|Sj|Siλi0vjλjgj(vj)0λigi(vj)=0ij

Stasys
la source

Réponses:

9

J'ai réalisé que la réponse à ma question est - oui: la dimension VC des polynômes degré sur variables sur n'importe quel semi-tropical est au maximum une constante . Cela peut être montré en utilisant le théorème 1 ci-dessus. Voir ici pour plus de détails. Ainsi, BPP P / poly est également valable pour les circuits tropicaux et, par conséquent, également pour les algorithmes de programmation dynamique "purs". dnn2log(n+d)


NB (ajouté le 25.06.2019) En attendant, j'ai résolu le problème complètement dans cet article . Dans une telle généralité, dont je n'avais même pas rêvé au début. Le cas tropical n'est ici qu'un cas très, très spécial. Et encore plus curieusement: par juste une combinaison appropriée de résultats déjà connus (profonds à tous égards) d'autres auteurs.

Que reste-t-il d'autre à faire dans cette direction (BPP vs. P / poly)? Outre la diminution de la taille des circuits déterministes résultants (une question intéressante en soi).

Stasys
la source