VC-Dimension von Polynomen über tropische Halbierungen?

14

BPPPpoly ( min , + )(max,+)(Mindest,+)

Sei ein Semiring. Ein Nullmuster einer Folge von Polynomen in ist eine Teilmenge für die existiert. und , so dass für alle , iff . Das heißt, die Graphen genau jener Polynome mit müssen den Punkt treffen . ("Nullmuster", weil die Bedingung durch .)Rm R [ x 1 , , x n ] S { 1 , , m } x R n y R i = 1 , , m f i ( x ) = y i S f i i S ( x ,(f1,,fm)mR[x1,,xn]S{1,,m}xRnyRi=1,,mfi(x)=yiSfiiS f(x,y)Rn+1f i ( x ) - y = 0 Z ( m )fi(x)=yfi(x)y=0Z(m) = die maximal mögliche Anzahl von Nullmustern einer Folge von Polynomen mit höchstens Grad . Daher ist . Die Vapnik-Chervonenkis-Dimension von Polynomen vom Grad ist VC (n, d): = \ max \ {m \ Doppelpunkt Z (m) = 2 ^ m \} . d 0 Z ( m ) 2 mmd0Z(m)2mV C ( n , d ) : = max { m : Z ( m ) = 2 m }dVC(n,d):=max{m:Z(m)=2m}

Anmerkung: Normalerweise wird die VC-Dimension für eine Familie F von Mengen als die größte Kardinalität |S|ein Satz S , so dass {FS:FF}=2S . Um in diesen Rahmen zu passen, können wir mit jedem Paar (x,y)Rn+1 die Menge Fx,y aller Polynome von f Grad d für die f(x)=y hält. Dann ist die VC-Dimension der Familie F aller solcher Mengen Fx,y genau VC(n,d) .

Eine triviale Obergrenze für m=VC(n,d) ist mnlog|R|(wir brauchen mindestens 2m verschiedene Vektoren xRn , um alle 2m möglichen Muster zu haben), aber es ist in unendlichen Halbierungen nutzlos. Um gute Obergrenzen für die VC-Dimension zu haben, benötigen wir gute Obergrenzen für Z(m) . Über Felder sind solche Grenzen bekannt.

Satz 1: Über jedem Feld R haben wir Z(m)(md+nn) .
Ähnliche Obergrenzen wurden früher von Milnor , Heintz und Warren bewiesen ; Ihre Beweise verwenden schwere Techniken aus der realen algebraischen Geometrie. Im Gegensatz dazu ist ein halbseitiger Beweis von Satz 1 von Ronyai, Babai und Ganapathy (den wir unten geben) eine einfache Anwendung der linearen Algebra.

Wenn wir nach kleinen suchen , die erfüllen , erhalten wir, dass über jedem beliebigen Feld gilt . Im Hinblick auf vs. / ist hier wichtig, dass die Dimension nur im Grad logarithmisch ist . Dies ist wichtig, da polynomgroße Schaltkreise Polynome exponentiellen Grades berechnen können, und weil ein Ergebnis von Haussler beim PAC-Lernen (Korollar 2 auf Seite 114 dieses Papiers ) Folgendes ergibt (wobei angenommen wird, dass deterministische Schaltkreise Mehrheitsstimmen verwenden dürfen) ihre Werte auszugeben). (mVC(n,d)=O(nlogd)BPPPPolyd(md+nn)<2mVC(n,d)=O(nlogd)BPPPpolyd

Satz 2: gilt für Schaltungen über jedes semiring , wobei nur in und polynomisch ist . R V C ( n , d ) n log dBPPP/polyRVC(n,d)nlogd
Sehen Sie hier, wie das Ergebnis von Haussler Satz 2 impliziert.

Insbesondere gilt nach Satz 1 für jedes Feld. (Interessant ist hier nur der Fall von unendlichen Feldern: Für endliche funktionieren viel einfachere Argumente: Chernoff gebunden erledigt dann die Arbeit.) Aber was ist mit (unendlichen) Halbbildern, die keine Felder oder gar keine Ringe sind? Motiviert durch dynamisches Programmieren interessieren mich hauptsächlich tropische und Semirings, aber auch andere (unendliche) Nicht-Feld-Semirings sind interessant. Beachten Sie, dass über das Semiring ein Polynom mit undBPPP/poly(max,+)(min,+)(max,+)f(x)=aAcai=1nxiaiANcaR wird zum Maximierungsproblem ; der Grad der (wie üblich) die maximal Gesamt .f(x)=maxaA {ca+a1x1+a2x2++anxn}fa1++anaA

Frage: Liegt die VC-Dimension von Grad Polynomen über tropischem Semirings-Polynom in ? dnlogd

Ich gebe zu, es kann eine ziemlich schwierige Frage sein, eine schnelle Antwort zu erwarten: Tropische Algebra ist eher "verrückt". Aber vielleicht hat jemand eine Vorstellung davon, warum (wenn überhaupt) tropische Polynome mehr Nullmuster erzeugen können als echte Polynome? Oder warum "sollten" sie nicht? Oder einige verwandte Referenzen.

Oder kann der Beweis von Babai, Ronyai und Ganapathy (unten) irgendwie "verdreht" werden, um über tropische Semirings zu arbeiten? Oder über irgendwelche anderen unendlichen Halbbilder (die keine Felder sind)?

Beweis von Satz 1: Es sei angenommen, dass eine Folge verschiedene hat und dass Zeugen dieser Nullmuster sind. Sei ein , das vom ten Vektor , und betrachte die Polynome . Wir behaupten, dass diese Polynome über unser Feld linear unabhängig sind. Dieser Anspruch ist der Beweis des Theorems da jeder Grad höchstens hat und die Dimension des Raums der Polynome vom Grad höchstens ist(f1,,fm)pv1,,vpRnSi={k:fk(vi)0}ivigi:=kSifkgiD:=mdD(n+DD). Um die Behauptung zu beweisen, genügt es zu beachten, dass genau dann ist, wenn . Nehmen wir umgekehrt an, dass eine nichttriviale lineare Beziehung existiert. Sei ein Index, so dassist unter den mit minimal . Ersatz in der Beziehung. Während , haben wir für alle , einen Widerspruch. gi(vj)0SiSjλ1gi(x)++λpgp(x)=0j|Sj|Siλi0vjλjgj(vj)0λigi(vj)=0ij

Stasys
quelle

Antworten:

9

Ich habe erkannt, dass die Antwort auf meine Frage lautet: Ja, die VC-Dimension von Grad d Polynomen auf n Variablen über jedes tropische Semiring beträgt höchstens konstante Zeiten n2log(n+d) . Dies kann mit dem obigen Satz 1 gezeigt werden. Einzelheiten finden Sie hier . So BPP P / Poly gilt auch für tropische Schaltungen und damit auch für die „reine“ dynamische Programmieralgorithmen.


NB (hinzugefügt am 25.06.2019) In der Zwischenzeit habe ich das Problem in diesem Artikel vollständig gelöst . In einer solchen Allgemeinheit, von der ich am Anfang noch nicht einmal geträumt habe. Tropenfall ist hier nur ein ganz ganz besonderer Fall. Und noch seltsamer: durch nur eine entsprechende Kombination bereits bekannter (in jeder Hinsicht tiefer gehender) Ergebnisse anderer Autoren.

Was bleibt in dieser Richtung (BPP vs. P / Poly) noch zu tun? Neben der Verringerung der Größe der resultierenden deterministischen Schaltungen (eine interessante Frage an sich).

Stasys
quelle