Die schlimmste Anzahl von Fragen, die zum Erlernen eines monotonen Prädikats über einem Poset erforderlich sind

15

Man betrachte einen endlichen Satz über Elementen und ein unbekanntes monotones Prädikat über (dh für jedes , , wenn und dann ). . Ich kann auswerten, indem ich einen Knoten bereitstelle und herausfinde, ob P ( x ) gilt oder nicht. Mein Ziel ist es, die Menge der Knoten x X so genau zu bestimmen, dass P ( x ) gilt, wobei nur wenige Bewertungen von P verwendet werden(X,)nPXxyXP(x)xyP(y)PxXP(x)xXP(x)Pwie möglich. (Ich kann meine Abfragen in Abhängigkeit von der Antwort auf alle vorherigen Abfragen auswählen. Ich muss nicht alle Abfragen im Voraus planen.)

S(X,)PPr(S,P)SPPSwr(S)=maxPr(S,P)Swr(S)=minSwr(S)

Meine Frage ist folgende: Als Eingabe das Poset , wie kann ich die schlechteste Laufzeit der optimalen Strategien bestimmen?(X,)

[Es ist klar, dass für ein leeres Poset Abfragen erforderlich sind (wir müssen nach jedem einzelnen Knoten fragen) und dass für eine Gesamtreihenfolge um Abfragen erforderlich sind (eine binäre Suche durchführen, um zu finden) Der Frontmann). Ein allgemeineres Ergebnis ist die folgende informationstheoretische Untergrenze: Die Anzahl der möglichen Auswahlen für das Prädikat ist die Anzahl der Antiketten von (da es eine Eins-zu-Eins-Zuordnung zwischen monotonen Prädikaten und gibt Antichains werden als die maximalen Elemente von ) interpretiert. Da also jede Abfrage ein Bit Information liefert, benötigen wir mindestensnlog2nPNX(X,)Plog2NXAbfragen, wobei die beiden vorherigen Fälle zusammengefasst werden. Ist dies eng gebunden, oder handelt es sich um einige Posets, deren Struktur derart ist, dass für das Lernen asymptotisch mehr Abfragen erforderlich sind als die Anzahl der Antichains?]

a3nm
quelle
2
Inwiefern unterscheidet sich das von Ihrer vorherigen Frage zu diesem Thema? cstheory.stackexchange.com/questions/14772/…
Suresh Venkat
1
Einverstanden ist es ähnlich, aber ich interessiere mich hier für allgemeine Posets, einschließlich Posets mit geringer Breite, die überhaupt nicht wie das gesamte Gitter aussehen. Außerdem kümmert es mich nicht mehr um die inkrementelle Komplexität oder irgendetwas Ähnliches, nur um die Anzahl der Abfragen, die in Abhängigkeit von der Wahl des Posets erforderlich sind. In dieser Einstellung ist die Interpretation der Booleschen Funktion nicht anwendbar und es sieht wirklich so aus, als ob die Antwort irgendwie von der "Struktur" des Posets abhängt (möglicherweise die Anzahl der Antichains, wie ich vorgeschlagen habe). Hoffentlich ist dies eine separate Frage, bitte schließen, wenn ich mich geirrt habe.
a3nm
1
Zu Ihrer Information: In der Komplexitätsliteratur werden Strategien, wie Sie sie definiert haben, in der Regel als "Entscheidungsbäume" bezeichnet. Sie haben einen Standardbegriff für Höhe (das Maß, an dem Sie interessiert sind) und Größe.
Joshua Grochow
Danke, Joshua! Ich bin mir dessen mehr oder weniger bewusst. Ich dachte nur, es sei einfacher, Vokabeln aus der Spieltheorie zu verwenden, aber ich bin mir bewusst, dass die Strategie als Baum betrachtet werden kann.
a3nm
1
(Kein Problem. Übrigens habe ich nicht nur darauf hingewiesen, dass es sich um einen Baum handelt. Die Art und Weise, wie Sie ihn beschrieben haben, ist in der Tat sehr einfach und klar in der Lage sein zu suchen, zusätzlich zu einem Begriff, der wahrscheinlich vielen Leuten, die diese Seite besuchen, sofort bekannt ist. Prost!)
Joshua Grochow

Antworten:

7

Dies ist keine vollständige Antwort, aber es ist zu lang, um einen Kommentar abzugeben.

Ich glaube, ich habe ein Beispiel gefunden, für das die Schranke nicht eng ist.log2NX

Betrachten Sie den folgenden Poset. Die Grundmenge ist und a i kleiner als b j für alle i , j { 1 , 2 } . Die anderen Paare sind unvergleichlich. (Das Hasse-Diagramm ist ein 4- Zyklus).X={a1,a2,b1,b2}aibji,j{1,2}4

Lassen Sie mich die monotonen Eigenschaften mit den Störungen des Posets identifizieren. Dieses Poset hat sieben Verstimmungen: , { b 1 } , { b 2 } , { b 1 , b 2 } , { a 1 , b 1 , b 2 } , { a 2 , b 1 , b 2 } , { a 1 , a 2 , b 1 ,{b1}{b2}{b1,b2}{a1,b1,b2}{a2,b1,b2} , und dieses Poset hat sieben Gegenketten, da die Gegenketten mit den Verstimmungen eins zu eins korrespondieren. Also ist 2 log 2 N X= log 2 7 = 3 für diesen Poset.{a1,a2,b1,b2}log2NX=log27=3

Nun zeige ich durch gegnerische Argumentation, dass jede Strategie mindestens vier Abfragen benötigt (also alle Elemente abfragen muss). Lassen Sie uns eine beliebige Strategie festlegen.

Wenn die Strategie zuerst abfragt , antwortet der Gegner " P ( eine 1 ) ist nicht gültig". Dann haben wir fünf Möglichkeiten: , { b 1 } , { b 2 } , { b 1 , b 2 } , { a 2 , b 1 , b 2 } . Um festzustellen, was der Fall ist, benötigen wir also mindestens least log 2 5 = 3a1P(a1){b1}{b2}{b1,b2}{a2,b1,b2}log25=3mehr Anfragen. Insgesamt benötigen wir vier Abfragen. Dasselbe Argument gilt, wenn die erste Abfrage .a2

Wenn die Strategie zuerst abfragt , antwortet der Gegner mit " P ( b 1 ) gilt". Dann haben wir fünf Möglichkeiten: { b 1 } , { b 1 , b 2 } , { a 1 , b 1 , b 2 } , { a 2 , b 1 , b 2 } , { a 1 , a 2 , bb1P(b1){b1}{b1,b2}{a1,b1,b2}{a2,b1,b2} . Aus diesem Grund benötigen wir nach wie vor mindestens drei weitere Abfragen. Insgesamt benötigen wir vier Abfragen. Das gleiche Argument gilt, wenn die erste Abfrage b 2 ist .{a1,a2,b1,b2}b2

Wenn wir parallele Kopien dieses Posets nehmen, dann hat es 7 k Antichains, und daher ist die vorgeschlagene Grenze log 2 7 k= 3 k . Da jedoch jede Kopie vier Abfragen benötigt, benötigen wir mindestens 4 k Abfragen.k7klog27k=3k4k

Wahrscheinlich gibt es einen größeren Poset mit größerer Lücke. Dieses Argument kann jedoch nur den Koeffizienten verbessern.

Hier scheint das Problem eine Situation zu sein, in der keine Abfrage den Suchraum gleichmäßig aufteilt. In einem solchen Fall kann der Gegner die größere Hälfte zum Bleiben zwingen.

Yoshio Okamoto
quelle
1
Ah, interessant. Verallgemeinert Ihr Beispiel ist es klar, dass wenn die Antwort answer i , ¬ P ( a i ) und i , P ( b i ) ist, wir es nicht sicher wissen, bis alle 2 n Knoten abgefragt sind. Es gibt jedoch 2 nX={a1,...,an,b1,...,bn}i,¬P(ai)i,P(bi)2nAntiketten ( 2 n -1nicht-leere Teilmengen von einer i ‚s, idem für b i ‘ s, und die leere Menge), so dass die Schranke um den Faktor 2. Dank für dieses Beispiel nicht dicht ist. Ich sehe jedoch nicht wirklich ein, wie / ob die Lücke mehr als ein multiplikativer Faktor sein könnte oder ob eine nicht triviale Obergrenze gefunden werden kann, geschweige denn ein Algorithmus für eine genaue Antwort. 2n+112n1aibi
Am
7

In ihrer Arbeit Jedes Poset hat ein zentrales Element , Linial und Saks zeigen (Satz 1), dass die Anzahl der Abfragen, die zur Lösung des idealen Identifikationsproblems in einem Poset erforderlich sind, höchstens K 0 log 2 i ( X ) beträgt , wobei K 0 = 1 / ( 2 - log 2 ( 1 + log 2 5 ) ) und I ( X ) ist die Anzahl der Ideale von X . Was sie ein "Ideal" nennen, ist eigentlich eine niedrigere MengeXK0log2i(X)K0=1/(2log2(1+log25))i(X)Xund es gibt eine offensichtliche Eins-zu-eins-Entsprechung zwischen monotonen Prädikaten und der unteren Menge der Punkte, an denen sie nicht festhalten, abgesehen von ihrem "Identifikationsproblem", dass sie durch Abfragen von Knoten identifiziert werden, genau wie in meiner Einstellung, also denke ich, dass dies der Fall ist Umgang mit dem Problem in ich interessiert bin und dass .i(X)=NX

Entsprechend ihrem Ergebnis ist die informationstheoretische Untergrenze bis zu einer relativ kleinen multiplikativen Konstante eng. Also im Grunde dies die Frage nach der Anzahl der Fragen erforderlich gelegt hat , als eine Funktion von und bis zu einer multiplikativen Konstante: Es ist zwischen log 2 N X und K 0 log 2 N X .NXlog2NXK0log2NX

Linial und Saks zitieren eine persönliche Mitteilung von Shearer, um zu sagen, dass es bekannte Ordnungen gibt, für die wir eine Untergrenze von für einige K 1 nachweisen können, die nur geringfügig kleiner als K 0 ist (dies ist im Sinne von Die Antwort von Yoshio Okamoto, der diesen Ansatz für einen kleineren Wert von K 1 ) ausprobierte .K1log2NXK1K0K1

Damit ist meine Frage nach der Berechnung der Anzahl der von benötigten Fragen nicht vollständig beantwortet. Da jedoch die Berechnung von N X von X # P-vollständig ist , habe ich das Gefühl, dass es wenig Hoffnung gibt. (Kommentare zu diesem Punkt sind willkommen.) Dennoch ist dieses Ergebnis von Linial und Saks aufschlussreich.XNXX

a3nm
quelle
5

Für den booleschen n-Würfel (oder äquivalent für den Satz ( 2 S , ) aller Teilmengen einer n-Elementmenge) wird die Antwort von Korobkov und Hänsel gegeben (ab 1963 bzw. 1966). Der Satz von Hansel [1] besagt, dass eine unbekannte monotone Boolesche Funktion (dh ein unbekanntes monotones Prädikat für diesen Poset) durch einen deterministischen Algorithmus gelernt werden kann, der höchstens ϕ ( n ) = ( n ) ergibt({0,1}n,)(2S,) Abfragen (das heißt,fragenφ(n)Fragen im schlimmsten Fall). Dieser Algorithmus entspricht der Untergrenze von Korobkovs Theorem [2], wonachϕ(n)-1-Abfragen nicht ausreichen. (Hansels Algorithmus ist also im ungünstigsten Fall optimal.) Ein Algorithmus in beiden Anweisungen wird als deterministischer Entscheidungsbaum verstanden.ϕ(n)=(nn/2)+(nn/2+1)ϕ(n)ϕ(n)1

Der Logarithmus der Anzahl der Antichains in ist asymptotisch gleich ( n({0,1}n,) , so gibt es eine konstante Faktorlücke zwischenlogNXund der optimalen Algorithmusleistungϕ(n)2 ( n(nn/2)2n/πn/2logNX für diesen Poset.ϕ(n)2(nn/2)

Leider war es mir nicht möglich, eine gute Behandlung von Hansels Algorithmus in englischer Sprache im Internet zu finden. Es basiert auf einem Lemma, das den n-Würfel in -Ketten mit speziellen Eigenschaften unterteilt. Eine Beschreibung findet sich in [3]. Für die untere Grenze kenne ich keinen Verweis auf eine Beschreibung in Englisch.ϕ(n)

Da ich mit diesen Ergebnissen vertraut bin, kann ich eine Beschreibung auf arXiv posten, falls die Behandlung in Kovalerchuks Artikel nicht ausreicht.

Wenn nicht viel falsch ist, hat es Versuche gegeben, Hansels Ansatz zu verallgemeinern, zumindest auf das Poset , wobei ( E k , ) eine Kette 0 < 1 < < k - 1 ist , obwohl ich kann nicht sofort einen Hinweis geben. Für den Booleschen Fall haben die Menschen auch andere Komplexitätsbegriffe als den Worst-Case für dieses Problem untersucht.(Ekn,)(Ek,)0<1<<k1

[1] G. Hansel, Sur le nombre des fonctions booléennes monotones de n variables. CR Acad. Sci. Paris, 262 (20), 1088-1090 (1966)

[2] VK Korobkov. Abschätzung der Anzahl der monotonen Funktionen der Algebra der Logik und der Komplexität des Algorithmus zum Auffinden des Resolventensatzes für eine beliebige monotone Funktion der Algebra der Logik. Sowjetische Mathematik. Doklady 4, 753-756 (1963) (Übersetzung aus dem Russischen)

[3] B. Kovalerchuk, E. Triantaphyllou, AS Deshpande, E. Vityaev. Interaktives Lernen von monotonen Booleschen Funktionen. Information Sciences 94 (1), 87-118 (1996) ( Link )

dd1
quelle
Vielen Dank für diese ausführliche Antwort! Für den Booleschen Würfel siehe < cstheory.stackexchange.com/q/14772 >. Ich kann Französisch lesen, konnte aber Hansels Artikel nicht finden (hätte auf Gallica verfügbar sein sollen, aber diese Ausgabe scheint zu fehlen). Ich fand relevante Informationen in Sokolov, NA (1982), "Über die optimale Bewertung monotoner Boolescher Funktionen". UdSSR Comput Math Math Phys, Band 22, Nr. 2, 207-220 (englische Übersetzung vorhanden). Ich bin an Verallgemeinerungen für andere DAGs interessiert, wenn Sie Referenzen finden können. Zögern Sie nicht, per E-Mail zu antworten (a3nm AT a3nm DOT net), wenn eine Längenbeschränkung ein Problem darstellt. Danke noch einmal! n
a3nm
Bitte schön! Leider weiß ich nicht, wie ich die Laufzeit des Algorithmus in Bezug auf die Ausgabegröße einschränken soll. Korobkovs Beweis der Untergrenze gibt beispielsweise keine Antwort auf diese Frage. Ich glaube jedoch, dass es einen Hinweis gibt, der leicht relevant ist. Ich werde versuchen, über das Wochenende etwas Zeit zu finden und auch nach Verallgemeinerungen zu suchen. Gleichzeitig bin ich mir nicht sicher, ob eine geschlossene englische Beschreibung des Booleschen Falls (dieser beiden Theoreme) es wert ist, geschrieben zu werden ...
dd1
@ a3nm vielleicht wurde der DAG-Fall in der Literatur nicht berücksichtigt? könnte es schwieriger sein als der boolesche n-Würfel, der nach Inklusion geordnet ist?
vzn
@vzn Ich denke, dass zumindest einige der hier gestellten Fragen offen sind. Selbst für eine Kette ist es nicht sofort klar, wie der Algorithmus von Hansel verallgemeinert werden soll.
dd1
@ a3nm es scheint alles ähnlich zu sein, untere Schranken / minimale monotone Schaltkreise (Größen) zu finden, aber es wurde bisher noch nicht klar verknüpft gesehen ...
vzn
0

[ HINWEIS: Das folgende Argument scheint nicht zu funktionieren, aber ich lasse es hier, damit andere nicht denselben Fehler machen / falls jemand es beheben kann. Das Problem ist, dass eine exponentielle Untergrenze für das Lernen / Identifizieren einer monotonen Funktion, wie unten gezeigt, einem inkrementell polynomiellen Algorithmus für das Problem nicht unbedingt widerspricht . Und das letztere ist äquivalent zur Überprüfung der gegenseitigen Dualität zweier monotoner Funktionen in Polyzeit.]

Ich glaube, Ihre Vermutung in ist im Allgemeinen falsch. Wenn es tatsächlich der Fall ist, dass log N X Abfragen benötigt werden, impliziert dies eine ziemlich starke Untergrenze für das Erlernen von monotonen Funktionen unter Verwendung von Mitgliedschaftsabfragen . Insbesondere läßt die poset X der Boolesche Würfel mit der üblichen Ordnung sein (wenn man so will, X ist die Potenz von { 1 , . . . , N } mit als Teilauftrag). Die Anzahl M der maximalen Antiketten in X erfüllt log M =logNXlogNXXX{1,...,n}MX [1]. Wenn Ihre Idee inlogNXkorrekt ist, gibt es ein monotonisches Prädikat inX, das im Wesentlichen ( n-1)erfordertlogM=(1+o(1))(n1n/2)logNXXAbfragen. Insbesondere impliziert dies eine Untergrenze von im Wesentlichen2nfür die Komplexität jedes Algorithmus, der dieses Problem löst.(n1n/2)2n2n

Wenn ich es jedoch richtig verstanden habe (von dem ich jetzt weiß, dass ich es nicht verstanden habe ), ist Ihr Problem gleichbedeutend damit, die gegenseitige Dualität von zwei monotonen Funktionen zu überprüfen, was in quasi-polynomialer Zeit geschehen kann (siehe das Intro dieses Artikels von Bioch und Ibaraki , die Fredman und Khachiyan zitieren , widersprechen allem, was nahe an einer Untergrenze liegt.2n

[1] Liviu Ilinca und Jeff Kahn. Zählung maximaler Antichains und unabhängiger Mengen . arXiv: 1202,4427

Joshua Grochow
quelle
Josh, ich sehe kein Problem mit dem Argument. Ich verstehe, dass es offen ist, ob eine monotone Funktion im Zeitpolynom in n und der Anzahl der minimalen Elemente gelernt werden kann . das Bioch-Ibaraki Papier ist etwa inkrementell Polynom - AlgorithmuslogNXn
Sasho Nikolov
Ah, okay. Das war mir nicht bewusst. (Wie gesagt, ich bin kein Experte auf diesem Gebiet - meine Antwort beruhte nur darauf, ein paar Dinge nachzuschlagen und zusammenzufügen.) Ich lasse es hier, damit andere Leute es sehen und es zumindest nicht schaffen gleicher Fehler / am besten in etwas Nützliches verwandeln.
Joshua Grochow