16
$\begingroup$

Consider $(X, \leq)$ a finite poset over $n$ items, and $P$ an unknown monotonic predicate over $X$ (i.e., for any $x$, $y \in X$, if $P(x)$ and $x \leq y$ then $P(y)$). I can evaluate $P$ by providing one node $x \in X$ and finding out if $P(x)$ holds or not. My goal is to determine exactly the set of nodes $x \in X$ such that $P(x)$ holds, using as few evaluations of $P$ as possible. (I can choose my queries depending on the answer of all previous queries, I am not required to plan all queries in advance.)

A strategy $S$ over $(X, \leq)$ is a function which tells me, as a function of the queries that I ran so far and their answers, which node to query, and which ensures that on any predicate $P$, by following the strategy, I will reach a state in which I know the value of $P$ on all nodes. The running time $r(S, P)$ of $S$ on a predicate $P$ is the number of queries required to know the value of $P$ on all nodes. The worst running time of $S$ is $wr(S) = \max_P r(S, P)$. An optimal strategy $S'$ is such that $wr(S') = \min_S wr(S)$.

My question is the following: given as input the poset $(X, \leq)$, how can I determine the worst running time of the optimal strategies?

[It is clear that for an empty poset $n$ queries will be needed (we need to ask about each single node), and that for a total order around $\lceil \log_2 n \rceil$ queries will be needed (doing a binary search to find the frontier). A more general result is the following information-theoretic lower bound: the number of possible choices for the predicate $P$ is the number $N_X$ of antichains of $(X, \leq)$ (because there is a one-to-one mapping between monotonic predicates and antichains interpreted as the maximal elements of $P$), so, since each query gives us one bit of information, we will need at least $\lceil \log_2 N_X \rceil$ queries, subsuming the two previous cases. Is this bound tight, or are them some posets whose structure is such that learning can require asymptotically more queries than the number of antichains?]

$\endgroup$
5
  • 2
    $\begingroup$ How is this different from your previous question on this topic ? cstheory.stackexchange.com/questions/14772/… $\endgroup$ Jan 28, 2013 at 17:34
  • 1
    $\begingroup$ Agreed, it is similar, but I'm interested about general posets here, including posets of small width that do not look at all like the complete lattice. Besides, I do not care anymore about the incremental complexity or anything of the kind, just at the number of queries required as a function of the choice of the poset. In this setting the boolean function interpretation is not applicable and it really looks like the answer depends somehow on the "structure" of the poset (maybe the number of antichains, as I suggested). Hopefully this warrants a separate question, please close if I was wrong. $\endgroup$
    – a3nm
    Jan 28, 2013 at 17:45
  • 1
    $\begingroup$ FYI, in the complexity literature, strategies as you've defined them are typically called "decision trees," and they have a standard notion of height (the measure you're interested in) and size. $\endgroup$ Jan 28, 2013 at 20:18
  • $\begingroup$ Thanks, Joshua! I'm more or less aware of this, I just thought it was simpler to use vocabulary from game theory, but yes, I'm aware that the strategy can be seen as a tree. $\endgroup$
    – a3nm
    Jan 28, 2013 at 20:22
  • 2
    $\begingroup$ (No problem. By the way, I wasn't just pointing out that it can be seen as a tree. The way you described it is indeed very straightforward and clear, but I was providing you a keyword/term of art that you might be able to search for, in addition to a term that is probably immediately familiar to many people who frequent this site. Cheers!) $\endgroup$ Jan 28, 2013 at 20:34

4 Answers 4

7
$\begingroup$

This is not a complete answer, but it's too long to be a comment.

I think I found an example for which the bound $\lceil \log_2 N_X \rceil$ is not tight.

Consider the following poset. The ground set is $X=\{a_1, a_2, b_1, b_2\}$, and $a_i$ is smaller than $b_j$ for all $i,j\in\{1,2\}$. The other pairs are incomparable. (The Hasse diagram is a $4$-cycle).

Let me identify the monotone properties with the upsets of the poset. This poset has seven upsets: $\emptyset$, $\{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,b_2\}$, and this poset has seven antichains since the antichains are in one-to-one correspondence with the upsets. So, $\lceil \log_2 N_X \rceil=\lceil \log_2 7 \rceil = 3$ for this poset.

Now, by adversary argument I'll show that any strategy needs at least four queries (so needs to query all elements). Let's fix an arbitrary strategy.

If the strategy first queries $a_1$, then the adversary answers "$P(a_1)$ doesn't hold." Then, we are left with five possibilities: $\emptyset$, $\{b_1\}$, $\{b_2\}$, $\{b_1,b_2\}$, $\{a_2,b_1,b_2\}$. Thus, to determine which is the case, we need at least $\lceil \log_2 5\rceil = 3$ more queries. In total, we need four queries. The same argument applies if the first query is $a_2$.

If the strategy first queries $b_1$, then the adversary answers "$P(b_1)$ holds." Then, we are left with five possibilities: $\{b_1\}$, $\{b_1,b_2\}$, $\{a_1,b_1,b_2\}$, $\{a_2,b_1,b_2\}$, $\{a_1,a_2,b_1,b_2\}$. Therefore, we need at least three more queries as before. In total, we need four queries. The same argument applies when the first query is $b_2$.

If we take $k$ parallel copies of this poset, then it has $7^k$ antichains, and thus the proposed bound is $\lceil \log_2 7^k \rceil = 3k$. But, since each of the copies needs four queries, we need at least $4k$ queries.

Probably, there is a larger poset with larger gap. But this argument can only improve the coefficient.

Here, the problem looks to be a situation where no query partitions the search space evenly. In such a case, the adversary can force the larger half to remain.

$\endgroup$
1
  • 1
    $\begingroup$ Ah, interesting. Generalizing your example to $X = \{a_1, ..., a_n, b_1, ..., b_n\}$, it's clear that if the answer is $\forall i, \neg P(a_i)$ and $\forall i, P(b_i)$ then we won't know it for sure until all $2n$ nodes are queried. However, there are $2^{n+1} - 1$ antichains ($2^n-1$ non-empty subsets of $a_i$'s, idem for $b_i$'s, and the empty set), so the bound is not tight by a factor of 2. Thanks for this example. However, I don't really see how/if the gap could be more than a multiplicative factor, or if a non-trivial upper bound can be found, let alone an algorithm for an exact answer. $\endgroup$
    – a3nm
    Jan 29, 2013 at 13:24
7
$\begingroup$

In their paper Every Poset Has a Central Element, Linial and Saks show (Theorem 1) that the number of queries required to solve the ideal identification problem in a poset $X$ is at most $K_0 \log_2 i(X)$, where $K_0 = 1/(2 - \log_2(1 + \log_2 5))$ and $i(X)$ is the number of ideals of $X$. What they call an "ideal" is actually a lower set and there is an obvious one to one correspondance between monotonic predicates and the lower set of the points at which they don't hold, besides their "identification problem" is to identify by querying nodes just like in my setting, so I think they are dealing with the problem I'm interested in and that $i(X) = N_X$.

So, according to their result, the information-theoretic lower bound is tight up to a relatively small multiplicative constant. So this basically settles the question of the number of questions required, as a function of $N_X$ and up to a multiplicative constant: it is between $\log_2 N_X$ and $K_0 \log_2 N_X$.

Linial and Saks quote a personal communication by Shearer to say that there are known orders for which we can prove a lower bound of $K_1 \log_2 N_X$ for some $K_1$ which is just slightly less than $K_0$ (this is in the spirit of Yoshio Okamoto's answer who tried this approach for a smaller value of $K_1$).

This does not fully answer my question of computing the number of questions required from $X$, however, since computing $N_X$ from $X$ is #P-complete, I have a feeling that there is little hope. (Comments about this point are welcome.) Still, this result by Linial and Saks is enlightening.

$\endgroup$
5
$\begingroup$

For the Boolean n-cube $(\{0, 1\}^n, \leq)$ (or, equivalently, for the poset $(2^S, \subseteq)$ of all subsets of an n-element set), the answer is given by Korobkov and Hansel's theorems (from 1963 and 1966, respectively). Hansel's theorem [1] states that an unknown monotone Boolean function (i.e., an unknown monotone predicate on this poset) can be learned by a deterministic algorithm making at most $\phi(n) = \binom{n}{\lfloor n/2 \rfloor} + \binom{n}{\lfloor n/2 \rfloor + 1}$ queries (that is, asking $\phi(n)$ questions in the worst case). This algorithm matches the lower bound of Korobkov's theorem [2], which says that $\phi(n) - 1$ queries do not suffice. (So Hansel's algorithm is optimal in the worst-case setting.) An algorithm in both statements is understood as a deterministic decision tree.

The logarithm of the number of antichains in $(\{0, 1\}^n, \le)$ is asymptotically equal to $\binom{n}{\lfloor n/2 \rfloor} \sim 2^n / \sqrt{\pi n / 2}$, so there is a constant-factor gap between $\log N_X$ and the optimal algorithm performance $\phi(n) \sim 2 \binom{n}{\lfloor n/2 \rfloor}$ for this poset.

Unfortunately, I have not been able to find a good treatment of Hansel's algorithm in English available on the web. It is based on a lemma that partitions the n-cube into $\phi(n)$ chains with special properties. Some description can be found in [3]. For the lower bound, I don't know any reference to a description in English.

Since I am familiar with these results, I can post a description on arXiv, if the treatment in Kovalerchuk's paper does not suffice.

If am not much mistaken, there have been attempts to generalize Hansel's approach, at least to the poset $(E_k^n, \le)$, where $(E_k, \le)$ is a chain $0 < 1 < \ldots < k - 1$, although I cannot give any reference straight away. For the Boolean case, people have also investigated notions of complexity other than worst-case for this problem.

[1] G. Hansel, Sur le nombre des fonctions booléennes monotones de n variables. C. R. 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)

$\endgroup$
7
  • $\begingroup$ 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! $\endgroup$
    – a3nm
    Feb 7, 2013 at 12:24
  • $\begingroup$ 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... $\endgroup$
    – dd1
    Feb 7, 2013 at 13:16
  • $\begingroup$ @a3nm maybe the DAG case hasnt been considered in the literature? could it be harder than the boolean n-cube ordered by inclusion? $\endgroup$
    – vzn
    Feb 7, 2013 at 16:15
  • $\begingroup$ @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. $\endgroup$
    – dd1
    Feb 7, 2013 at 16:25
  • $\begingroup$ @a3nm it all seems to be similar to finding lower bounds/minimal monotone circuits (sizes) but havent seen it clearly linked so far... $\endgroup$
    – vzn
    Feb 7, 2013 at 16:52
0
$\begingroup$

[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 $\log N_X$ is false in general. If it is indeed the case that $\log N_X$ 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 $\subseteq$ as its partial order). The number $M$ of maximal antichains in $X$ satisfies $\log M = (1 + o(1))\binom{n-1}{\lfloor n/2 \rfloor}$ [1]. If your idea on $\log N_X$ is correct, then there is some monotone predicate on $X$ that requires essentially $\binom{n-1}{n/2} \approx 2^n$ queries. In particular, this implies a lower bound of essentially $2^n$ 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 $2^n$ lower bound.

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

$\endgroup$
2
  • $\begingroup$ Josh, I don't see a problem with the $\log N_X$ 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 $\endgroup$ Jan 28, 2013 at 23:46
  • $\begingroup$ 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. $\endgroup$ Jan 29, 2013 at 1:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.