Pire nombre de questions nécessaires pour apprendre un prédicat monotone sur un poset

15

Considérons un poset fini sur éléments, et un prédicat monotone inconnu sur (c'est-à-dire pour tout , , si et alors ) . Je peux évaluer en fournissant un nœud et en déterminant si est vrai ou non. Mon objectif est de déterminer exactement l'ensemble des nœuds tel que valide, en utilisant aussi peu d'évaluations de(X,)nPXxyXP(x)xyP(y)PxXP(x)xXP(x)Pque possible. (Je peux choisir mes requêtes en fonction de la réponse à toutes les requêtes précédentes, je ne suis pas obligé de planifier toutes les requêtes à l'avance.)

Une stratégie sur est une fonction qui me dit, en fonction des requêtes que j'ai exécutées jusqu'ici et de leurs réponses, quel noeud interroger, et qui s'assure que sur tout prédicat , en suivant la stratégie , J'atteindrai un état dans lequel je connais la valeur de sur tous les nœuds. Le temps d'exécution de sur un prédicat est le nombre de requêtes nécessaires pour connaître la valeur de sur tous les nœuds. Le pire temps de fonctionnement de est . Une stratégie optimale S ' est telle que wr (S') = \ min_S wr (S) .S(X,)PPr(S,P)SPPSwr(S)=maxPr(S,P)Swr(S)=minSwr(S)

Ma question est la suivante: étant donné en entrée le poset (X,) , comment puis-je déterminer le pire temps d'exécution des stratégies optimales?

[Il est clair que pour un poset vide, n requêtes seront nécessaires (nous devons nous interroger sur chaque nœud), et que pour un ordre total autour de log2n requêtes seront nécessaires (faire une recherche binaire pour trouver la frontière). Un résultat plus général est la borne inférieure de la théorie de l'information suivante: le nombre de choix possibles pour le prédicat P est le nombre NX d'antichaînes de (X,) (car il existe une correspondance biunivoque entre les prédicats monotones et antichaines interprétées comme les éléments maximaux de P ), donc, puisque chaque requête nous donne un bit d'information, nous aurons besoin d'au moins log2NXrequêtes, en subsumant les deux cas précédents. Est-ce lié étroitement ou s'agit-il de posets dont la structure est telle que l'apprentissage peut nécessiter asymptotiquement plus de requêtes que le nombre d'antichaînes?]

a3nm
la source
2
En quoi est-ce différent de votre question précédente sur ce sujet? cstheory.stackexchange.com/questions/14772/…
Suresh Venkat
1
D'accord, c'est similaire, mais je m'intéresse aux posets généraux ici, y compris les posets de petite largeur qui ne ressemblent pas du tout au réseau complet. En outre, je ne me soucie plus de la complexité incrémentale ou de quoi que ce soit du genre, juste au nombre de requêtes requises en fonction du choix du poset. Dans ce contexte, l'interprétation de la fonction booléenne n'est pas applicable et il semble vraiment que la réponse dépende en quelque sorte de la "structure" du poset (peut-être le nombre d'antichaînes, comme je l'ai suggéré). J'espère que cela mérite une question distincte, veuillez fermer si je me trompais.
a3nm
1
Pour info, dans la littérature sur la complexité, les stratégies telles que vous les avez définies sont généralement appelées «arbres de décision» et elles ont une notion standard de hauteur (la mesure qui vous intéresse) et de taille.
Joshua Grochow
Merci, Joshua! J'en suis plus ou moins conscient, je pensais juste qu'il était plus simple d'utiliser le vocabulaire de la théorie des jeux, mais oui, je suis conscient que la stratégie peut être vue comme un arbre.
a3nm
1
(Pas de problème. Soit dit en passant, je ne faisais pas simplement remarquer qu'il peut être vu comme un arbre. La façon dont vous l'avez décrit est en effet très simple et claire, mais je vous fournissais un mot-clé / terme d'art que vous pourriez utiliser être capable de rechercher, en plus d'un terme qui est probablement immédiatement familier à de nombreuses personnes qui fréquentent ce site. À la vôtre!)
Joshua Grochow

Réponses:

7

Ce n'est pas une réponse complète, mais c'est trop long pour être un commentaire.

Je pense avoir trouvé un exemple pour lequel la borne n'est pas serrée.log2NX

Considérez le poset suivant. L'ensemble de base est , et a i est plus petit que b j pour tout i , j { 1 , 2 } . Les autres paires sont incomparables. (Le diagramme de Hasse est un cycle de 4 ).X={a1,a2,b1,b2}aibji,j{1,2}4

Permettez-moi d'identifier les propriétés monotones avec les bouleversements du poset. Ce poset a sept bouleversements: , { 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} , et ce poset a sept antichaines puisque les antichaines sont en correspondance biunivoque avec les bouleversements. Donc,log 2 N X= log 2 7 = 3 pour ce poset.{a1,a2,b1,b2}log2NX=log27=3

Maintenant, par l'argument de l'adversaire, je montrerai que toute stratégie nécessite au moins quatre requêtes (donc doit interroger tous les éléments). Corrigeons une stratégie arbitraire.

Si la stratégie demande d'abord , l'adversaire répond " P ( a 1 ) ne tient pas". Il nous reste alors cinq possibilités: , { b 1 } , { b 2 } , { b 1 , b 2 } , { a 2 , b 1 , b 2 } . Ainsi, pour déterminer quel est le cas, il nous faut au moins log 2 5 = 3a1P(a1){b1}{b2}{b1,b2}{a2,b1,b2}log25=3plus de requêtes. Au total, nous avons besoin de quatre requêtes. Le même argument s'applique si la première requête est .a2

Si la stratégie interroge d'abord , l'adversaire répond " P ( b 1 ) tient". Il nous reste alors cinq possibilités: { 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} . Par conséquent, nous avons besoin d'au moins trois requêtes supplémentaires comme auparavant. Au total, nous avons besoin de quatre requêtes. Le même argument s'applique lorsque la première requête est b 2 .{a1,a2,b1,b2}b2

Si nous prenons copies parallèles de ce poset, alors il a 7 k antichaines, et donc la borne proposée est log 2 7 k= 3 k . Mais, comme chacune des copies nécessite quatre requêtes, nous avons besoin d'au moins 4 k requêtes.k7klog27k=3k4k

Probablement, il y a un plus grand poset avec un plus grand écart. Mais cet argument ne peut qu'améliorer le coefficient.

Ici, le problème semble être une situation où aucune requête ne partitionne l'espace de recherche de manière égale. Dans un tel cas, l'adversaire peut forcer la plus grande moitié à rester.

Yoshio Okamoto
la source
1
Ah, intéressant. En généralisant votre exemple , il est clair que si la réponse est i , ¬ P ( a i ) et i , P ( b i ) alors nous ne le saurons pas avec certitude jusqu'à ce que les 2 n nœuds soient interrogés. Cependant, il y a 2 nX={a1,...,an,b1,...,bn}i,¬P(ai)i,P(bi)2nantichains ( 2 n -1sous-ensembles non vides de a i , idem pour b i et l'ensemble vide), donc la limite n'est pas serrée d'un facteur 2. Merci pour cet exemple. Cependant, je ne vois pas vraiment comment / si l'écart pourrait être plus qu'un facteur multiplicatif, ou si une limite supérieure non triviale peut être trouvée, sans parler d'un algorithme pour une réponse exacte. 2n+112n1aibi
a3nm
7

Dans leur article Every Poset Has a Central Element , Linial et Saks montrent (Théorème 1) que le nombre de requêtes nécessaires pour résoudre le problème d'identification idéal dans un poset est au plus K 0 log 2 i ( X ) , où K 0 = 1 / ( 2 - log 2 ( 1 + log 2 5 ) ) et i ( X ) est le nombre d'idéaux de X . Ce qu'ils appellent un "idéal" est en fait un ensemble inférieurXK0log2i(X)K0=1/(2log2(1+log25))i(X)Xet il y a une correspondance évidente entre les prédicats monotones et l'ensemble inférieur des points sur lesquels ils ne tiennent pas, outre leur "problème d'identification" est d'identifier en interrogeant les nœuds comme dans mon contexte, donc je pense qu'ils sont traiter le problème que je suis intéressé et que .i(X)=NX

Ainsi, selon leur résultat, la borne inférieure théorique de l'information est serrée jusqu'à une constante multiplicative relativement petite. Donc , ce règle essentiellement la question du nombre de questions posées, en fonction de et jusqu'à une constante multiplicatif: il est entre log 2 N X et K 0 log 2 N X .NXlog2NXK0log2NX

Linial et Saks citent une communication personnelle de Shearer pour dire qu'il existe des ordres connus pour lesquels nous pouvons prouver une borne inférieure de pour certains K 1 qui est juste légèrement inférieure à K 0 (c'est dans l'esprit de Réponse de Yoshio Okamoto qui a essayé cette approche pour une valeur plus petite de K 1 ).K1log2NXK1K0K1

Cela ne répond pas entièrement à ma question de calculer le nombre de questions requises de , cependant, puisque le calcul de N X à partir de X est # P-complet , j'ai le sentiment qu'il y a peu d'espoir. (Les commentaires sur ce point sont les bienvenus.) Pourtant, ce résultat de Linial et Saks est instructif.XNXX

a3nm
la source
5

Pour le n-cube booléen (ou, de manière équivalente, pour le poset ( 2 S , ) de tous les sous-ensembles d'un ensemble de n éléments), la réponse est donnée par les théorèmes de Korobkov et Hansel (respectivement de 1963 et 1966). Le théorème de Hansel [1] déclare qu'une fonction booléenne monotone inconnue (c'est-à-dire un prédicat monotone inconnu sur ce poset) peut être apprise par un algorithme déterministe faisant au plus ϕ ( n ) = ( n({0,1}n,)(2S,) requêtes (qui est, demander& phiv(n)questions dans le pirecas). Cet algorithme correspond à la borne inférieure du théorème de Korobkov [2], qui dit que lesrequêtesϕ(n)-1ne suffisent pas. (L'algorithme de Hansel est donc optimal dans le pire des cas.) Un algorithme dans les deux déclarations est considéré comme un arbre de décision déterministe.ϕ(n)=(nn/2)+(nn/2+1)ϕ(n)ϕ(n)1

Le logarithme du nombre d'antichaînes dans est asymptotiquement égal à ( n({0,1}n,) , il existe donc un écart de facteur constant entrelogNXet les performances optimales de l'algorithmeϕ(n)2 ( n(nn/2)2n/πn/2logNX pour ce poset.ϕ(n)2(nn/2)

Malheureusement, je n'ai pas pu trouver un bon traitement de l'algorithme de Hansel en anglais disponible sur le web. Il est basé sur un lemme qui partitionne le n-cube en chaînes avec des propriétés spéciales. Une description peut être trouvée dans [3]. Pour la borne inférieure, je ne connais aucune référence à une description en anglais.ϕ(n)

Étant donné que je connais ces résultats, je peux publier une description sur arXiv, si le traitement dans l'article de Kovalerchuk ne suffit pas.

Si je ne me trompe pas beaucoup, il y a eu des tentatives pour généraliser l'approche de Hansel, au moins au poset , où ( E k , ) est une chaîne 0 < 1 < < k - 1 , bien que je ne peut donner aucune référence immédiatement. Pour le cas booléen, les gens ont également étudié des notions de complexité autres que le pire des cas pour ce problème.(Ekn,)(Ek,)0<1<<k1

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

[2] VK Korobkov. Estimation du nombre de fonctions monotones de l'algèbre de la logique et de la complexité de l'algorithme de recherche de l'ensemble résolu pour une fonction monotone arbitraire de l'algèbre de la logique. Mathématiques soviétiques. Doklady 4, 753-756 (1963) (traduction du russe)

[3] B. Kovalerchuk, E. Triantaphyllou, AS Deshpande, E. Vityaev. Apprentissage interactif des fonctions booléennes monotones. Sciences de l'information 94 (1), 87-118 (1996) ( lien )

dd1
la source
Merci beaucoup pour cette réponse détaillée! Pour le cube booléen, voir < cstheory.stackexchange.com/q/14772 >. Je peux lire le français mais je n'ai pas trouvé l'article de Hansel (aurait dû être disponible sur Gallica mais ce problème semble manquer), j'ai trouvé des informations pertinentes dans Sokolov, NA (1982), "On the Optimal Evaluation of Monotonic Boolean Functions", USSR Comput Math Math Phys, Vol 22, No 2, 207-220 (une traduction en anglais existe). Je suis intéressé par les généralisations à d'autres DAG si vous pouvez trouver des références. N'hésitez pas à répondre par email (a3nm AT a3nm DOT net) si la limite de longueur est un problème. Merci encore! n
a3nm
Je vous en prie! Malheureusement, je ne sais pas comment limiter le temps d'exécution de l'algorithme en termes de taille de sortie. La preuve de Korobkov de la borne inférieure, par exemple, ne répond pas à cette question. Cependant, je pense qu'il peut y avoir une référence qui est légèrement pertinente. J'essaierai de trouver du temps au cours du week-end et de rechercher également des généralisations. En même temps, je ne sais pas si une description fermée en anglais du cas booléen (ces deux théorèmes) mérite d'être écrite ...
dd1
@ a3nm le cas DAG n'a peut-être pas été pris en compte dans la littérature? pourrait-il être plus difficile que le n-cube booléen ordonné par inclusion?
vzn
@vzn Je suppose qu'au moins certaines des questions ici ne manqueront pas d'être ouvertes. Même pour une chaîne, il n'est pas immédiatement clair comment généraliser l'algorithme de Hansel.
dd1
@ a3nm, tout semble similaire à la recherche de bornes inférieures / circuits monotones minimaux (tailles), mais je ne l'ai pas vu clairement lié jusqu'à présent ...
vzn
0

[ REMARQUE: L'argument suivant ne semble pas fonctionner, mais je le laisse ici pour que les autres ne commettent pas la même erreur / au cas où quelqu'un pourrait le réparer. Le problème est qu'une limite inférieure exponentielle sur l'apprentissage / l'identification d'une fonction monotone, comme ci-dessous, ne contredit pas nécessairement un algorithme polynomial incrémentiel pour le problème. Et c'est ce dernier qui équivaut à vérifier la dualité mutuelle de deux fonctions monotones en temps poly.]

Je crois que votre conjecture sur le est fausse en général. S'il est vrai que des requêtes log N X sont nécessaires, cela implique une borne inférieure assez forte pour l' apprentissage des fonctions monotones à l'aide de requêtes d'appartenance . En particulier, que le poset X soit le cube Boolean à la commande habituelle (si vous voulez, X est le powerset de { 1 , . . . , N } avec comme ordre partiel). Le nombre M d'antichaînes maximales dans X satisfait log M =logNXlogNXXX{1,...,n}MX [1]. Si votre idée sur lejournalNXest correcte, alors il existe un prédicat monotone surXqui nécessite essentiellement ( n-1logM=(1+o(1))(n1n/2)logNXXrequêtes. En particulier, cela implique une borne inférieure essentiellement de2npour la complexité de tout algorithme résolvant ce problème.(n1n/2)2n2n

However, if I've understood correctly [which I now know I hadn't], your problem is equivalent to checking the mutual duality of two monotone functions, which can be done in quasi-polynomial time (see the intro of this paper by Bioch and Ibaraki, which cites Fredman and Khachiyan), contradicting anything close to a 2n lower bound.

[1] Liviu Ilinca and Jeff Kahn. Counting maximal antichains and independent sets. arXiv:1202.4427

Joshua Grochow
la source
Josh, I don't see a problem with the logNX argument. my understanding is that it is open whether a monotone function can be learned in time polynomial in n and the number of minimal elements. the Bioch-Ibaraki paper is about incrementally polynomial algorithm
Sasho Nikolov
Ah, okay. I wasn't aware of that. (Like I said, I'm not an expert in this area - my answer was just based on looking up a few things and putting them together.) I'll leave it here so other people can see it and at least not make the same mistake / at best turn it into something useful.
Joshua Grochow