Pior número de perguntas necessárias para aprender um predicado monotônico sobre um poset

15

Considere (X,) um poset finita sobre itens, e um predicado monótona desconhecido através (isto é, para qualquer , , se e , em seguida, ). Eu posso avaliar fornecendo um nó e descobrindo senPXxyXP(x)xyP(y)PxXP(x) é válido ou não. Meu objetivo é determinar exatamente o conjunto de nós modo que válido, usando o mínimo de avaliações dexXP(x)Pque possível. (Posso escolher minhas consultas, dependendo da resposta de todas as consultas anteriores, não sou obrigado a planejar todas as consultas com antecedência.)

Uma estratégia over é uma função que me diz, em função das consultas que eu executei até agora e suas respostas, qual nó a ser consultado e que garante isso em qualquer predicado , seguindo a estratégia , Atingirei um estado em que conheço o valor de em todos os nós. O tempo de execução de em um predicado é o número de consultas necessárias para conhecer o valor de em todos os nós. O pior tempo de execução de é . Uma estratégia ideal S ' é tal que wr (S') = \ min_S wr (S) .( X , ) P P r ( S , P ) S P P S w r ( S ) = max P r ( S , P ) S w r ( S ) = min S w r ( S )S(X,)PPr(S,P)SPPSwr(S)=maxPr(S,P)Swr(S)=minSwr(S)

Minha pergunta é a seguinte: dado como entrada o poset (X,) , como posso determinar o pior tempo de execução das estratégias ideais?

[Está claro que, para um poset vazio , serão necessárias n consultas (precisamos perguntar sobre cada nó) e que, para um pedido total em torno de log2n , serão necessárias consultas n \ rceil (fazendo uma pesquisa binária para encontrar a fronteira). Um resultado mais geral é o seguinte limite inferior teórico da informação: o número de opções possíveis para o predicado P é o número NX de antichains de (X,) (porque existe um mapeamento individual entre predicados monotônicos e antichains interpretados como os elementos máximos de P ), portanto, como cada consulta nos fornece um pouco de informação, precisaremos de pelo menos log2NX , subsumindo os dois casos anteriores. Isso está limitado ou são alguns posets cuja estrutura é tal que o aprendizado pode exigir consultas assintoticamente mais do que o número de antichains?]

a3nm
fonte
2
Como isso é diferente da sua pergunta anterior sobre esse tópico? cstheory.stackexchange.com/questions/14772/...
Suresh Venkat
1
Concordo, é semelhante, mas estou interessado em posets gerais aqui, incluindo posets de largura pequena que não parecem nada com a estrutura completa. Além disso, não me importo mais com a complexidade incremental ou algo do tipo, apenas com o número de consultas necessárias em função da escolha do poset. Nesse cenário, a interpretação da função booleana não é aplicável e realmente parece que a resposta depende de alguma forma da "estrutura" do poset (talvez o número de antichains, como sugeri). Espero que isso justifique uma pergunta separada. Por favor, feche se eu estava errado.
a3nm
1
Para sua informação, na literatura de complexidade, as estratégias definidas por você são geralmente denominadas "árvores de decisão" e possuem uma noção padrão de altura (a medida em que você está interessado) e tamanho.
Joshua Grochow
Obrigado Joshua! Estou mais ou menos consciente disso, apenas pensei que era mais simples usar o vocabulário da teoria dos jogos, mas sim, estou ciente de que a estratégia pode ser vista como uma árvore.
a3nm
1
(Sem problemas. A propósito, eu não estava apenas apontando que ela pode ser vista como uma árvore. A maneira como você a descreveu é realmente muito direta e clara, mas estava fornecendo uma palavra-chave / termo de arte que você pode ser capaz de procurar, além de um termo que é provavelmente imediatamente familiar para muitas pessoas que frequentam este site Exclamações).!
Joshua Grochow

Respostas:

7

Esta não é uma resposta completa, mas é muito tempo para ser um comentário.

Acho que encontrei um exemplo para o qual o limite não é rígido.log2NX

Considere o seguinte poset. O conjunto de bases é e a i é menor que b j para todos os i , j { 1 , 2 } . Os outros pares são incomparáveis. (O diagrama de Hasse é um 4X={a1,a2,b1,b2}aibji,j{1,2}4 ciclo de ).

Deixe-me identificar as propriedades monótonas com os transtornos do poset. Este poset tem sete viradas: , { 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}para este poset. , e este poset possui sete antichains, uma vez que os antichains estão em correspondência individual com as perturbações. Assim,log 2 N X= log 2 7 = 3{a1,a2,b1,b2}log2NX=log27=3

Agora, pelo argumento do adversário, mostrarei que qualquer estratégia precisa de pelo menos quatro consultas (portanto, é necessário consultar todos os elementos). Vamos consertar uma estratégia arbitrária.

Se a estratégia primeiro consultar , o adversário responderá " P ( a 1 ) não é válido". Então, ficamos com cinco possibilidades: , { b 1 } , { b 2 } , { b 1 , b 2 } , { a 2 , b 1 , b 2 } . Assim, para determinar qual é o caso, precisamos de pelo menos log 2 5 = 3a1P(a1){b1}{b2}{b1,b2}{a2,b1,b2}log25=3mais consultas. No total, precisamos de quatro consultas. O mesmo argumento aplica-se a primeira consulta é .a2

Se a estratégia primeiro consultar , o adversário responderá " P ( b 1 ) é válido". Então, temos cinco possibilidades: { 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} . Portanto, precisamos de pelo menos mais três consultas como antes. No total, precisamos de quatro consultas. O mesmo argumento se aplica quando a primeira consulta é b 2 .{a1,a2,b1,b2}b2

Se tomarmos cópias paralelas deste poset, então ele tem 7 k antichains, e, assim, o proposto é ligado log 2 7 k= 3 k . Mas, como cada uma das cópias precisa de quatro consultas, precisamos de pelo menos 4 k consultas.k7klog27k=3k4k

Provavelmente, existe um poset maior com maior intervalo. Mas esse argumento só pode melhorar o coeficiente.

Aqui, o problema parece ser uma situação em que nenhuma consulta particiona o espaço de pesquisa uniformemente. Nesse caso, o adversário pode forçar a metade maior a permanecer.

Yoshio Okamoto
fonte
1
Ah, interessante. Generalizando o seu exemplo para , é claro que, se a resposta é i , ¬ P ( um i ) e i , P ( b i ) então não saberemos com certeza até que todos os 2 n nodos são consultados. No entanto, existem 2 nX={a1,...,an,b1,...,bn}i,¬P(ai)i,P(bi)2nantichains ( 2 n -1subconjuntos não vazios de uma i 's, idem para b i ' s, e o conjunto vazio), de modo que o limite não é apertado por um fator de 2. Graças para este exemplo. No entanto, eu realmente não vejo como / se a diferença pode ser mais do que um fator multiplicativo, ou se um limite superior não trivial pode ser encontrado, muito menos um algoritmo para uma resposta exata. 2n+112n1aibi
a3nm
7

Em seu artigo Todos os Posets possuem um elemento central , Linial e Saks mostram (Teorema 1) que o número de consultas necessárias para resolver o problema de identificação ideal em um poset é no máximo K 0 log 2 i ( X ) , onde K 0 = 1 / ( 2 - log 2 ( 1 + log 2 5 ) ) e I ( X ) é o número de ideais de X . O que eles chamam de "ideal" é na verdade um conjunto inferiorXK0log2i(X)K0=1/(2log2(1+log25))i(X)Xe existe uma correspondência óbvia de um para um entre predicados monotônicos e o conjunto mais baixo dos pontos nos quais eles não se sustentam, além de seu "problema de identificação" ser identificar consultando os nós exatamente como no meu ambiente, então acho que eles são lidando com o problema no qual estou interessado e que i(X)=NX .

Portanto, de acordo com o resultado, o limite inferior da teoria da informação é restrito a uma constante multiplicativa relativamente pequena. Portanto, isso basicamente resolve a questão do número de perguntas necessárias, em função de e até uma constante multiplicativa: está entre log 2 N X e K 0 log 2 N XNXlog2NXK0log2NX .

Linial e Saks citam uma comunicação pessoal de Shearer para dizer que existem ordens conhecidas para as quais podemos provar um limite inferior de para alguns K 1 que é um pouco menor que K 0 (isso é no espírito de A resposta de Yoshio Okamoto que tentou essa abordagem por um valor menor de K 1K1log2NXK1K0K1 ).

Isso não responde totalmente à minha pergunta de calcular o número de perguntas exigidas do , no entanto, como o cálculo do N X a partir do X é # P-completo , sinto que há pouca esperança. (Comentários sobre este ponto são bem-vindos.) Ainda assim, este resultado de Linial e Saks é esclarecedor.XNXX

a3nm
fonte
5

Para o cubo n booleano (ou, equivalentemente, para o poset ( 2 S , ) de todos os subconjuntos de um conjunto de n elementos), a resposta é dada pelos teoremas de Korobkov e Hansel (de 1963 e 1966, respectivamente). O teorema de Hansel [1] afirma que uma função booleana monótona desconhecida (isto é, um predicado monótono desconhecido neste poset) pode ser aprendida por um algoritmo determinístico que obtém no máximo ϕ ( n ) = ( n({0,1}n,)(2S,) consultas (ou seja,ϕ(n)perguntas no pior caso). Este algoritmo corresponde ao limite inferior do teorema de Korobkov [2], que diz que asconsultasϕ(n)-1não são suficientes. (Portanto, o algoritmo de Hansel é ideal na pior das hipóteses.) Um algoritmo em ambas as instruções é entendido como uma árvore de decisão determinística.ϕ(n)=(nn/2)+(nn/2+1)ϕ(n)ϕ(n)1

O logaritmo do número de antichains em é assintoticamente igual a ( n({0,1}n,) , portanto existe uma diferença de fator constante entre ologNXe o desempenho ótimo do algoritmoϕ(n)2 ( n(nn/2)2n/πn/2logNX para este poset.ϕ(n)2(nn/2)

Infelizmente, não consegui encontrar um bom tratamento do algoritmo de Hansel em inglês disponível na web. É baseado em um lema que particiona o cubo n em ϕ(n) cadeias com propriedades especiais. Alguma descrição pode ser encontrada em [3]. Para o limite inferior, não conheço nenhuma referência a uma descrição em inglês.

Como estou familiarizado com esses resultados, posso postar uma descrição no arXiv, se o tratamento no artigo de Kovalerchuk não for suficiente.

Se não estou muito enganado, houve tentativas de generalizar a abordagem de Hansel, pelo menos para o poset , onde ( E k , ) é uma cadeia 0 < 1 < < k - 1 , embora eu não pode dar nenhuma referência imediatamente. Para o caso booleano, as pessoas também investigaram outras noções de complexidade que não o pior caso para esse problema.(Ekn,)(Ek,)0<1<<k1

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

[2] V. K. Korobkov. Estimation of the number of monotonic functions of the algebra of logic and of the complexity of the algorithm for finding the resolvent set for an arbitrary monotonic function of the algebra of logic. Soviet Math. Doklady 4, 753-756 (1963) (translation from Russian)

[3] B. Kovalerchuk, E. Triantaphyllou, A. S. Deshpande, E. Vityaev. Interactive learning of monotone Boolean functions. Information Sciences 94(1), 87-118 (1996) (link)

dd1
fonte
Thanks a lot for this detailed answer! For the Boolean n-cube, cf <cstheory.stackexchange.com/q/14772>. I can read French but couldn't find Hansel's paper (should have been available on Gallica but this issue seems to be missing), I found relevant info in Sokolov, N.A. (1982), "On the Optimal Evaluation of Monotonic Boolean Functions", USSR Comput Math Math Phys, Vol 22, No 2, 207-220 (English translation exists). I'm interested about generalizations to other DAGs if you can find refs. Don't hesitate to reply by email (a3nm AT a3nm DOT net) if length limit is a problem. Thanks again!
a3nm
You are welcome! Unfortunately, I do not know how to bound the algorithm running time in terms of output size. Korobkov's proof of the lower bound, for instance, does not give an answer to that question. However, I feel there may be a reference that is slightly relevant. I'll try to find some time time over the weekend and look for generalizations as well. At the same time, I'm not sure whether a closed English description of the Boolean case (these two theorems) is worth writing...
dd1
@a3nm maybe the DAG case hasnt been considered in the literature? could it be harder than the boolean n-cube ordered by inclusion?
vzn
@vzn I guess that at least some of the questions here are bound to be open. Even for a chain, it is not immediately clear how to generalize Hansel's algorithm.
dd1
@a3nm it all seems to be similar to finding lower bounds/minimal monotone circuits (sizes) but havent seen it clearly linked so far...
vzn
0

[NOTE: The following argument doesn't seem to work, but I'm leaving it here so others don't make the same mistake / in case someone can fix it. The issue is that an exponential lower bound on learning/identifying a monotone function, as below, does not necessarily contradict an incrementally polynomial algorithm for the problem. And it is the latter which is equivalent to checking the mutual duality of two monotone functions in poly time.]

I believe your conjecture on logNX is false in general. If it is indeed the case that logNX queries are needed, that implies quite a strong lower bound on learning monotone functions using membership queries. In particular, let the poset X be the Boolean cube with the usual ordering (if you like, X is the powerset of {1,...,n} with as its partial order). The number M of maximal antichains in X satisfies logM=(1+o(1))(n1n/2) [1]. If your idea on logNX is correct, then there is some monotone predicate on X that requires essentially (n1n/2)2n queries. In particular, this implies a lower bound of essentially 2n for the complexity of any algorithm solving this problem.

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
fonte
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