The Geometry of Generalized Binary Search

I Introduction

This paper studies learning problems of the following form. Consider a finite, but potentially very large, collection of binary-valued functions ${\cal H}$ defined on a domain ${\cal X}$. In this paper, ${\cal H}$ will be called the hypothesis space and ${\cal X}$ will be called the query space. Each $h\in{\cal H}$ is a mapping from ${\cal X}$ to $\{-1,1\}$. Throughout the paper we will let $N$ denote the cardinality of ${\cal H}$. Assume that the functions in ${\cal H}$ are unique and that one function, $h^{*}\in{\cal H}$, produces the correct binary labeling. It is assumed that $h^{*}$ is fixed but unknown, and the goal is to determine $h^{*}$ through as few queries from ${\cal X}$ as possible. For each query $x\in{\cal X}$, the value $h^{*}(x)$, possibly corrupted with independently distributed binary noise, is observed. The goal is to strategically select queries in a sequential fashion in order to identify $h^{*}$ as quickly as possible.

If the responses to queries are noiseless, then the problem is related to the construction of a binary decision tree. A sequence of queries defines a path from the root of the tree (corresponding to ${\cal H}$) to a leaf (corresponding to a single element of ${\cal H}$). There are several ways in which one might define the notion of an optimal tree; e.g., the tree with the minimum average or worst case depth. In general the determination of the optimal tree (in either sense above) is a combinatorial problem and was shown by Hyafil and Rivest to be NP-complete . Therefore, this paper investigates the performance of a greedy procedure called generalized binary search (GBS), depicted below in Fig. 1. At each step GBS selects a query that results in the most even split of the hypotheses under consideration into two subsets responding $+1$ and $-1$, respectively, to the query. The correct response to the query eliminates one of these two subsets from further consideration. We denote the number of hypotheses remaining at step $n$ by $|{\cal H}_{n}|$. The main results of the paper characterize the worst-case number of queries required by GBS in order to identify the correct hypothesis $h^{*}$. More formally, we define the notion of query complexity as follows.

The minimum number of queries required by GBS (or another algorithm) to identify any hypothesis in ${\cal H}$ is called the query complexity of the algorithm. The query complexity is said to be near-optimal if it is within a constant factor of $\log N$, since at least $\log N$ queries are required to specify one of $N$ hypotheses.

The following notation will be used throughout the paper. The hypothesis space ${\cal H}$ is a finite collection of binary-valued functions defined on a domain ${\cal X}$, which is called the query space. Each $h\in{\cal H}$ is a mapping from ${\cal X}$ to $\{-1,1\}$. For any subset ${\cal H}^{\prime}\subset H$, $|{\cal H}^{\prime}|$ denotes the number of hypotheses in ${\cal H}^{\prime}$. The number of hypotheses in ${\cal H}$ is denoted by $N:=|{\cal H}|$.

II A Geometrical View of Generalized Binary Search

While it may not be possible to naturally order the hypotheses within ${\cal X}$, there does exist a similar local geometry that can be exploited in the search process. Observe that the query space ${\cal X}$ can be partitioned into equivalence subsets such that every $h\in{\cal H}$ is constant for all queries in each such subset. Let ${\cal A}({\cal X},{\cal H})$ denote the smallest such partition Each $h$ splits ${\cal X}$ into two disjoint sets. Let $C_{h}:=\{x\in{\cal X}:h(x)=+1\}$ and let $\bar{C}_{n}$ denote its complement. ${\cal A}$ is the collection of all non-empty intersections of the form $\bigcap_{h\in H}\widetilde{C}_{h}$, where $\widetilde{C}_{h}\in\{C_{h},\bar{C}_{h}\}$, and it is the smallest partition that refines the sets $\{C_{h}\}_{h\in{\cal H}}$. ${\cal A}$ is known as the join of the sets $\{C_{h}\}_{h\in{\cal H}}$.. Note that ${\cal X}=\bigcup_{A\in{\cal A}}A$. For every $A\in{\cal A}$ and $h\in{\cal H}$, the value of $h(x)$ is constant (either $+1$ or $-1$) for all $x\in A$; denote this value by $h(A)$. Observe that the query selection step in GBS is equivalent to an optimization over the partition cells in ${\cal A}$. That is, it suffices to select a partition cell for the query according to $A_{n}=\arg\min_{A\in{\cal A}}|\sum_{h\in{\cal H}_{n}}h(A)|$.

II-B Distance in 𝒳{\cal X}

The partition ${\cal A}$ provides a geometrical link between ${\cal X}$ and ${\cal H}$. The hypotheses induce a distance function on ${\cal A}$, and hence ${\cal X}$. For every pair $A,A^{\prime}\in{\cal A}$ the Hamming distance between the response vectors $\{h_{1}(A),\dots,h_{N}(A)\}$ and $\{h_{1}(A^{\prime}),\dots,h_{N}(A^{\prime})\}$ provides a natural distance metric in ${\cal X}$.

Two sets $A,A^{\prime}\in{\cal A}$ are said to be $k$-neighbors if $k$ or fewer hypotheses (along with their complements, if they belong to ${\cal H}$) output different values on $A$ and $A^{\prime}$.

For example, suppose that ${\cal H}$ is symmetric, so that $h\in{\cal H}$ implies $-h\in{\cal H}$. Then two sets $A$ and $A^{\prime}$ are $k$-neighbors if the Hamming distance between their respective response vectors is less than or equal to $2k$. If ${\cal H}$ is non-symmetric ($h\in{\cal H}$ implies that $-h$ is not in ${\cal H}$), then $A$ and $A^{\prime}$ are $k$-neighbors if the Hamming distance between their respective response vectors is less than or equal to $k$.

The pair $({\cal X},{\cal H})$ is said to be $k$-neighborly if the $k$-neighborhood graph of ${\cal A}$ is connected (i.e., for every pair of sets in ${\cal A}$ there exists a sequence of $k$-neighbor sets that begins at one of the pair and ends with the other).

If $({\cal X},{\cal H})$ is $k$-neighborly, then the distance between $A$ and $A^{\prime}$ is bounded by $k$ times the minimum path length between $A$ and $A^{\prime}$. Moreover, the neighborly condition implies that there is an incremental way to move from one query to the another, moving a distance of at most $k$ at each step. This local geometry guarantees that near-bisecting queries almost always exist, as shown in the following lemma.

Assume that $({\cal X},{\cal H})$ is $k$-neighborly and define the coherence parameter

where the minimization is over all probability mass functions on ${\cal A}$. For every ${\cal H}^{\prime}\subset{\cal H}$ and any constant $c$ satisfying $c^{*}\leq c<1$ there exists an $A\in{\cal A}$ that approximately bisects ${\cal H}^{\prime}$

or the set ${\cal H}^{\prime}$ is a small

where $|{\cal H}^{\prime}|$ denotes the cardinality of ${\cal H}^{\prime}$.

Proof: According to the definition of $c^{*}$ it follows that there exists a probability distribution $P$ such that

This implies that there exists an $A\in{\cal A}$ such that

or there exists a pair $A$ and $A^{\prime}$ such that

In the former case, it follows that a query from $A$ will reduce the size of ${\cal H}^{\prime}$ by a factor of at least $(1+c)/2$ (i.e., every query $x\in{\cal A}$ approximately bisects the subset ${\cal H}^{\prime}$). In latter case, an approximately bisecting query does not exist, but the $k$-neighborly condition implies that $|{\cal H}^{\prime}|$ must be small. To see this note that the $k$-neighborly condition guarantees that there exists a sequence of $k$-neighbor sets beginning at $A$ and ending at $A^{\prime}$. By assumption in this case, $\left|\sum_{h\in{\cal H}^{\prime}}h(\cdot)\right|>c|{\cal H}^{\prime}|$ on every set and the sign of $\sum_{h\in{\cal H}^{\prime}}h(\cdot)$ must change at some point in the sequence. It follows that there exist $k$-neighbor sets $A$ and $A^{\prime}$ such that $\sum_{h\in{\cal H}^{\prime}}h(A)\ >\ c|{\cal H}^{\prime}|$ and $\sum_{h\in{\cal H}^{\prime}}h(A^{\prime})\ <\ -c|{\cal H}^{\prime}|$. Two inequalities follow from this observation. First, $\sum_{h\in{\cal H}^{\prime}}h(A)-\sum_{h\in{\cal H}^{\prime}}h(A^{\prime})>2c|{\cal H}^{\prime}|$. Second, $|\sum_{h\in{\cal H}^{\prime}}h(A)-\sum_{h\in{\cal H}^{\prime}}h(A^{\prime})|\leq 2k$. Note that if $h$ and its complement $h^{\prime}$ belong to ${\cal H}^{\prime}$, then their contributions to the quantity $|\sum_{h\in{\cal H}^{\prime}}h(A)-\sum_{h\in{\cal H}^{\prime}}h(A^{\prime})|$ cancel each other. Combining these inequalities yields $|{\cal H}^{\prime}|<k/c$. $\blacksquare$

To illustrate Lemma 1, consider the special situation in which we are given two points $x_{1},x_{2}\in{\cal X}$ known to satisfy $h^{*}(x_{1})=+1$ and $h^{*}(x_{2})=-1$. This allows us to restrict our attention to only those hypotheses that agree with $h^{*}$ at these points. Let ${\cal H}$ denote this collection of hypotheses. A depiction of this situation is shown in Fig. 2, where the solid curves represent the classification boundaries of the hypotheses, and each cell in the partition shown corresponds to a subset of ${\cal X}$ (i.e., an element of ${\cal A}$). As long as each subset is non-empty, then the $1$-neighborhood graph is connected in this example. The minimization in (1) is achieved by the distribution $P=\frac{1}{2}\delta_{x_{1}}+\frac{1}{2}\delta_{x_{2}}$ (equal point-masses on $x_{1}$ and $x_{2}$) and $c^{*}({\cal X},{\cal H})=0$. Lemma 1 implies that there exists a query (equivalently a partition cell $A$) where half of the hypotheses take the value $+1$ and the other half $-1$. The shaded cell in Fig. 2 has this bisection property. The figure also shows a dashed path between $x_{1}$ and $x_{2}$ that passes through the bisecting cell.

II-C Coherence and Query Complexity

The coherence parameter $c^{*}$ quantifies the informativeness of queries. The coherence parameter is optimized over the choice of $P$, rather than sampled at random according to a specific distribution on ${\cal X}$, because the queries may be selected as needed from ${\cal X}$. The minimizer in (1) exists because the minimization can be computed over the space of finite-dimensional probability mass functions over the elements of ${\cal A}$. For $c^{*}$ to be close to $0$, there must exist a distribution $P$ on ${\cal A}$ so that the moment of every $h\in{\cal H}$ is close to zero (i.e., for each $h\in{\cal H}$ the probabilities of the responses $+1$ and $-1$ are both close to $1/2$). This implies that there is a way to randomly sample queries so that the expected response of every hypothesis is close to zero. In this sense, the queries are incoherent with the hypotheses. In Lemma 1, $c^{*}$ bounds the proportion of the split of any subset ${\cal H}^{\prime}$ generated by the best query (i.e., the degree to which the best query bisects any subset ${\cal H}^{\prime}$). The coherence parameter $c^{*}$ leads to a bound on the number of queries required by GBS.

If $({\cal X},{\cal H})$ is $k$-neighborly, then GBS terminates with the correct hypothesis after at most $\lceil\log N/\log(\lambda^{-1})\rceil$ queries, where $\lambda=\max\{\frac{1+c^{*}}{2},\frac{k+1}{k+2}\}$.

Proof: Consider the $n$th step of the GBS algorithm. Lemma 1 shows that for any $c\in[c^{*},1)$ either there exists an approximately bisecting query and $|{\cal H}_{n}|\leq\frac{1+c}{2}|{\cal H}_{n-1}|$ or $|{\cal H}_{n-1}|<k/c$. The uniqueness of the hypotheses with respect to ${\cal X}$ implies that there exists a query that eliminates at least one hypothesis. Therefore, $|H_{n}|\leq|{\cal H}_{n-1}|-1=|{\cal H}_{n-1}|(1-|{\cal H}_{n-1}|^{-1})<|{\cal H}_{n-1}|(1-c/k)$. It follows that each GBS query reduces the number of viable hypotheses by a factor of at least

Therefore, $|{\cal H}_{n}|\leq N\lambda^{n}$ and GBS is guaranteed to terminate when $n$ satisfies $N\lambda^{n}\leq 1$. Taking the logarithm of this inequality produces the query complexity bound. $\blacksquare$

Theorem 1 demonstrates that if $({\cal X},{\cal H})$ is neighborly, then the query complexity of GBS is near-optimal; i.e., within a constant factor of $\log_{2}N$. The constant depends on coherence parameter $c^{*}$ and $k$, and clearly it is desirable that both are as small as possible. Note that GBS does not require knowledge of $c^{*}$ or $k$. We also remark that the constant in the bound is not necessarily the best that one can obtain. The proof involves selecting $c$ to balance splitting factor $\frac{1+c}{2}$ and the “tail” behavior $1-c/k$, and this may not give the best bound. The coherence parameter $c^{*}$ can be computed or bounded for many pairs $({\cal X},{\cal H})$ that are commonly encountered in applications, as covered later in Section V.

III Noisy Generalized Binary Search

We begin by describing a simple noise-tolerant version of GBS. The noise-tolerant algorithm is based on the simple idea of repeating each query of the GBS several times, in order to overcome the uncertainty introduced by the noise. Similar approaches are proposed in the work Kääriäinen . Karp and Kleinberg analyze of this strategy for noise-tolerant classic binary search. This is essentially like using a simple repetition code to communicate over a noisy channel. This procedure is termed noise-tolerant GBS (NGBS) and is summarized in Fig. 3.

Let $n_{0}$ denote the number of queries made by GBS to determine $h^{*}$ in the noiseless setting. Then in the noisy setting, with probability at least $\max\{0\,,\,1-n_{0}\,e^{-R|\frac{1}{2}-\alpha|^{2}}\}$ the noise-tolerant GBS algorithm in Fig. 3 terminates in exactly $R\,n_{0}$ queries and outputs $h^{*}$.

Based on the bound above, $R$ must satisfy $R\geq\frac{\log(n_{o}/\delta)}{|1/2-\alpha|^{2}}$ to guarantee that the labels determined for all $n_{0}$ queries are correct with probability $1-\delta$. The query complexity of NGBS can thus be bounded by $\frac{n_{0}\log(n_{0}/\delta)}{|1/2-\alpha|^{2}}.$ Recall that $N=|{\cal H}|$, the cardinality of ${\cal H}$. If $n_{0}=\log N$, then bound on the query complexity of NGBS is proportional to $\log N\,\log\frac{\log N}{\delta}$, a logarithmic factor worse than the query complexity in the noiseless setting. Moreover, if an upper bound on $n_{0}$ is not known in advance, then one must assume the worst-case value, $n_{0}=N$, in order to set $R$. That is, in order to guarantee that the correct hypothesis is determined with probability at least $1-\delta$, the required number of repetitions of each query is $R=\lceil\frac{\log(N/\delta)}{|1/2-\alpha|^{2}}\rceil.$ In this situation, the bound on the query complexity of NGBS is proportional to $\log N\,\log\frac{N}{\delta}$, compared to $\log N$ in the noiseless setting. It is conjectured that the extra logarithmic factor cannot be removed from the query complexity (i.e., it is unavoidable using repetitive queries). As we show next, these problems can be eliminated by a more sophisticated approach to noisy GBS.

III-B Soft-Decision Procedure

A more effective approach to noisy GBS is based on the following soft-decision procedure. A similar procedure has been shown to be near-optimal for the noisy (classic) binary search problem by Burnashev and Zigangirov and later independently by Karp and Kleinberg . The crucial distinction here is that GBS calls for a more general approach to query selection and a fundamentally different convergence analysis. Let $p_{0}$ be a known probability measure over ${\cal H}$. That is, $p_{0}:{\cal H}\rightarrow$ and $\sum_{h\in{\cal H}}p_{0}(h)=1$. The measure $p_{0}$ can be viewed as an initial weighting over the hypothesis class. For example, taking $p_{0}$ to be the uniform distribution over ${\cal H}$ expresses the fact that all hypothesis are equally reasonable prior to making queries. We will assume that $p_{0}$ is uniform for the remainder of the paper, but the extension to other initial distributions is trivial. Note, however, that we still assume that $h^{*}\in{\cal H}$ is fixed but unknown. After each query and response $(x_{n},y_{n}),$ $n=0,1,\dots,$ the distribution is updated according to

where $z_{n}(h)=h(x_{n})y_{n},\ h\in{\cal H}$, $\beta$ is any constant satisfying $0<\beta<1/2$, and $p_{n+1}(h)$ is normalized to satisfy $\sum_{h\in{\cal H}}p_{n+1}(h)=1$ . The update can be viewed as an application of Bayes rule and its effect is simple; the probability masses of hypotheses that agree with the label $y_{n}$ are boosted relative to those that disagree. The parameter $\beta$ controls the size of the boost. The hypothesis with the largest weight is selected at each step:

If the maximizer is not unique, one of the maximizers is selected at random. Note that, unlike the hard-decisions made by the GBS algorithm in Fig. 1, this procedure does not eliminate hypotheses that disagree with the observed labels, rather the weight assigned to each hypothesis is an indication of how successful its predictions have been. Thus, the procedure is termed Soft-Decision GBS (SGBS) and is summarized in Fig. 4.

At this point, the method of analyzing SGBS departs from that of Burnashev and Zigangirov which focused only on the classic binary search problem. The lack of an ordered structure calls for a different attack on the problem, which is summarized in the following results and detailed in the Appendix.

First observe that for every positive integer $n$

The modified SGBS algorithm is outlined in Fig. 5. It is easily verified that Lemma 2 and Theorem 3 also hold for the modified SGBS algorithm. This follows since the modified query selection step is identical to that of the original SGBS algorithm, unless there exist two neighboring sets with strongly bipolar weighted responses. In the latter case, a query is randomly selected from one of these two sets with equal probability.

For every $A\in{\cal A}$ and any probability measure $p$ on ${\cal H}$ the weighted prediction on $A$ is defined to be $W(p,A):=\sum_{h\in H}p(h)h(A)$, where $h(A)$ is the constant value of $h$ for every $x\in A$. The following lemma, which is the soft-decision analog of Lemma 1, plays a crucial role in the analysis of the modified SGBS algorithm.

If $({\cal X},{\cal H})$ is $k$-neighborly, then for every probability measure $p$ on ${\cal H}$ there either exists a set $A\in{\cal A}$ such that $|W(p,A)|\leq c^{*}$ or a pair of $k$-neighbor sets $A,A^{\prime}\in{\cal A}$ such that $W(p,A)>c^{*}$ and $W(p,A^{\prime})<-c^{*}$.

Suppose that $\min_{A\in{\cal A}}|W(p,A)|>c^{*}$. Then there must exist $A,A^{\prime}\in{\cal A}$ such that $W(p,A)>c^{*}$ and $W(p,A^{\prime})<-c^{*}$, otherwise $c^{*}$ cannot be the incoherence parameter of ${\cal H}$, defined in (1). To see this suppose, for instance, that $W(p,A)>c^{*}$ for all $A\in{\cal A}$. Then for every distribution $P$ on ${\cal X}$ we have $\sum_{A\in{\cal A}}\sum_{h\in{\cal H}}p(h)h(A)P(A)>c^{*}$. This contradicts the definition of $c^{*}$ since $\sum_{A\in{\cal A}}\sum_{h\in{\cal H}}p(h)h(A)P(A)\leq\sum_{h\in{\cal H}}p(h)|\sum_{A\in{\cal A}}h(A)\,P(A)|\leq\max_{h\in{\cal H}}|\sum_{A\in{\cal A}}h(A)\,P(A)|$. The neighborly condition guarantees that there exists a sequence of $k$-neighbor sets beginning at $A$ and ending at $A^{\prime}$. Since $|W(p,A)|>c^{*}$ on every set and the sign of $W(p,\cdot)$ must change at some point in the sequence, it follows that there exist $k$-neighbor sets satisfying the claim. ∎

with exponential constant $\lambda=\min\left\{\frac{1-c^{*}}{2},\frac{1}{4}\right\}\left(1-\frac{\beta(1-\alpha)}{1-\beta}-\frac{\alpha(1-\beta)}{\beta}\right)$, where $c^{*}$ is defined in (1).

Let ${\cal H}$ be a finite collection of hypotheses of form (4) and assume that the responses to each query are noisy, with noise bound $\alpha<1/2$. Then the hypotheses selected by modified SGBS with $\beta>\alpha$ satisfy

with $\lambda=\frac{1}{4}\left(1-\frac{\beta(1-\alpha)}{1-\beta}-\frac{\alpha(1-\beta)}{\beta}\right)$. Moreover, $\widehat{h}_{n}$ can be computed in time polynomial in $|H|$.

IV Agnostic GBS

So far we have assumed that the correct hypothesis $h^{*}$ is in ${\cal H}$. In this section we drop this assumption and consider agnostic algorithms guaranteed to find the best hypothesis in ${\cal H}$ even if the correct hypothesis $h^{*}$ is not in ${\cal H}$ and/or the assumptions of Theorem 1 or 4 do not hold. The best hypothesis in ${\cal H}$ can be defined as the one that minimizes the error with respect to a probability measure on ${\cal X}$, denoted by $P_{\cal X}$, which can be arbitrary. This notion of “best” commonly arises in machine problems where it is customary to measure the error or risk with respect to a distribution on ${\cal X}$. A common approach to hypothesis selection is empirical risk minimization (ERM), which uses queries randomly drawn according to $P_{\cal X}$ and then selects the hypothesis in ${\cal H}$ that minimizes the number of errors made on these queries. Given a budget of $n$ queries, consider the following agnostic procedure. Divide the query budget into three equal portions. Use GBS (or NGBS or modified SGBS) with one portion, ERM (queries randomly distributed according $P_{\cal X}$) with another, and then allocate the third portion to queries from the subset of ${\cal X}$ where the hypothesis selected by GBS (or NGBS or modified SGBS) and the hypothesis selected by ERM disagree, with these queries randomly distributed according to the restriction of $P_{\cal X}$ to this subset. Finally, select the hypothesis that makes the fewest mistakes on the third portion as the final choice. The sample complexity of this agnostic procedure is within a constant factor of that of the better of the two competing algorithms. For example, if the conditions of Theorems 1 or 4 hold, then the sample complexity of the agnostic algorithm is proportional to $\log N$. In general, the sample complexity of the agnostic procedure is within a constant factor of that of ERM alone. We formalize this as follows.

Let $P_{\cal X}$ denote a measure on ${\cal X}$ and suppose we have a query budget of $n$. Let $h_{1}$ denote the hypothesis selected by modified SGBS using $n/3$ of the queries and let $h_{2}$ denote the hypothesis selected by ERM from $n/3$ queries drawn independently from $P_{\cal X}$. Draw the remaining $n/3$ queries independently from $P_{\Delta}$, the restriction of $P_{\cal X}$ to the set $\Delta$ on which $h_{1}$ and $h_{2}$ disagree, and let $\widehat{R}_{\Delta}(h_{1})$ and $\widehat{R}_{\Delta}(h_{2})$ denote the average number of errors made by $h_{1}$ and $h_{2}$ on these queries. Select $\widehat{h}=\arg\min\{\widehat{R}_{\Delta}(h_{1}),\widehat{R}_{\Delta}(h_{2})\}$. Then, in general,

where $R(h)$, $h\in{\cal H}$, denotes the probability of error of $h$ with respect to $P_{\cal X}$. Furthermore, if the assumptions of Theorem 4 hold and $h^{*}\in{\cal H}$, then

where $C>0$ is a constant depending on $\lambda$ and $\alpha$. The exponential convergence of the expected risk is much faster than the usual parametric rate for ERM.

If the conditions of Theorem 4 are not met, then modified SGBS (alone) may perform poorly since it might select inappropriate queries and could even terminate with an incorrect hypothesis. However, the expected error of the agnostic selection $\widehat{h}$ is within $\sqrt{3/n}$ of the expected error of ERM, with no assumptions on the underlying distributions. Note that the expected error of ERM is proportional to $n^{-1/2}$ in the worst-case situation. Therefore, the agnostic procedure is near-optimal in general. The agnostic procedure offers this safeguard on performance. The same approach could be used to derive agnostic procedures from any active learning scheme (i.e., learning from adaptively selected queries), including GBS or NGBS. We also note that the important element in the agnostic procedure is the selection of queries; the proposed selection of $\widehat{h}$ based on those queries is convenient for proving the bounds, but not necessarily optimal.

V Applications of GBS

In this section we examine a variety of common situations in which the neighborliness condition can be verified. We will confine the discussion to GBS in the noise-free situation, and analogous results hold in the presence of noise. For a given pair $({\cal X},{\cal H})$, the effectiveness of GBS hinges on determining (or bounding) $c^{*}$ and establishing that $({\cal X},{\cal H})$ are neighborly. Recall the definition of the bound $c^{*}$ from (1) and that $N=|{\cal H}|$, the cardinality of ${\cal H}$. A trivial bound for $c^{*}$ is

which is achieved by allocating $N^{-1}$ mass to each hypothesis and evenly distributing $\frac{1}{2N}$ mass to set(s) $A$ where $h(A)=+1$ and $\frac{1}{2N}$ on set(s) $A$ where $h(A)=-1$. Non-trivial coherence bounds are those for which there exists a $P$ and $0\leq c<1$ that does not depend on $N$ such that

The coherence parameter $c^{*}$ is analytically determined or bounded in several illustrative applications below. We also note that it may be known a priori that $c^{*}$ is bounded far way from $1$. Suppose that for a certain $P$ on ${\cal X}$ (or ${\cal A}$) the absolute value of the first-moment of the correct hypothesis (w.r.t. $P$) is known to be upper bounded by a constant $c<1$. Then all hypotheses that violate the bound can be eliminated from consideration. Thus the constant $c$ is an upper bound on $c^{*}$. Situations like this can arise, for example, in binary classification problems with side/prior knowledge that the marginal probabilities of the two classes are somewhat balanced. Then the moment of the correct hypothesis, with respect to the marginal probability distribution on ${\cal X}$, is bounded far away from $1$ and $-1$.

First we show that GBS reduces to classic binary search. Let ${\cal H}=\{h_{1},\dots,h_{N}\}$ be the collection of binary-valued functions on ${\cal X}=$ of the following form, $h_{i}(x):=\mbox{sign}\left(x-\frac{i}{N+1}\right)$ for $i=1,\dots,N$ (and $\mbox{sign}(0):=+1$). Assume that $h^{*}\in{\cal H}$.

First consider the neighborly condition. Recall that ${\cal A}$ is the smallest partition of ${\cal X}$ into equivalence sets induced by ${\cal H}$. In this case, each $A$ is an interval of the form $A_{i}=[\frac{i-1}{N+1},\frac{i}{N+1})$, $i=1,\dots,N$. Observe that only a single hypothesis, $h_{i}$, has different responses to queries from $A_{i}$ and $A_{i+1}$ and so they are $1$-neighbors, for $i=1,\dots,N-1$. Moreover, the $1$-neighborhood graph is connected in this case, and so $({\cal X},{\cal H})$ is $1$-neighborly.

Next consider coherence parameter $c^{*}$. Take $P$ to be two point masses at $x=0$ and $x=1$ of probability $1/2$ each. Then $\left|\sum_{A\in{\cal A}}h(A)\,P(A)\right|\ =\ 0$ for every $h\in{\cal H}$, since $h(0)=-1$ and $h(1)=+1$. Thus, $c^{*}=0$. Since $c^{*}=0$ and $k=1$, we have $\alpha=2/3$ and the query complexity of GBS is proportional to $\log N$ according to Theorem 1. The reduction factor of $2/3$, instead of $1/2$, arises because we allow the situation in which the number of hypotheses may be odd (e.g., given three hypotheses), the best query may eliminate just one). If $N$ is even, then the query complexity is $\log_{2}(N)$, which is information-theoretically optimal.

However, consider the special case in which the intervals are disjoint. Then it is not hard to see that the best allocation of mass is to place $1/N$ mass in each subinterval, resulting in $c^{*}=1-2N^{-1}$. And so, Theorem 1 only guarantees that GBS is will terminate in at most $N$ steps (the number of steps required by exhaustive linear search). In fact, it is easy to see that no procedure can do better than linear search in this case and the query complexity of any method is proportional to $N$. However, note that if queries of a different form were allowed, then much better performance is possible. For example, if queries in the form of dyadic subinterval tests were allowed (e.g., tests that indicate whether or not the correct hypothesis is $+1$-valued anywhere within a dyadic subinterval of choice), then the correct hypothesis can be identified through $\lceil\log_{2}N\rceil$ queries (essentially a binary encoding of the correct hypothesis). This underscores the importance of the geometrical relationship between ${\cal X}$ and ${\cal H}$ embodied in the neighborly condition and the incoherence parameter $c^{*}$. Optimizing the query space to the structure of ${\cal H}$ is related to the notion of arbitrary queries examined in the work of Kulkarni et al , and somewhat to the theory of compressed sensing developed by Candes et al and Donoho .

V-B Multidimensional Problems

Finally, we also mention hypotheses associated with axis-aligned rectangles in $^{d}$, the multidimensional version of the interval hypotheses considered above. An axis-aligned rectangle is defined by its boundary coordinates in each dimension, $\{a_{j},b_{j}\}_{j=1}^{d}$, $0\leq a_{j}<b_{j}\leq 1$. The hypothesis associated with such a rectangle takes the value $+1$ on the set $\{x\in^{d}:\ a_{j}\leq x_{j}\leq b_{j},\ j=1,\dots,d\}$ and $-1$ otherwise. The complementary hypothesis may also be included. Consider a finite collection ${\cal H}$ of hypotheses of this form. If the rectangles associated with each $h\in{\cal H}$ have volume at least $\nu$, then by taking $P$ to be the uniform measure on $^{d}$ it follows that the coherence parameter $c^{*}\leq 1-2\nu$ for this problem. The cells of partition ${\cal A}$ of $$associated with a collection of such hypotheses are rectangles themselves. If the boundaries of the rectangles associated with the hypotheses are distinct, then the$1$-neighborhood graph of${\cal A}$is connected. Theorem 1 implies that the number of queries needed by GBS to determine the correct rectangle is proportional to$\log N/\log((1-\nu)^{-1})$.

V-C Discrete Query Spaces

Also note that a finite query space naturally limits the number of hypotheses that need be considered. Consider an uncountable collection of hypotheses. The number of unique labeling assignments generated by these hypotheses can be bounded in terms of the VC dimension of the class; see the book by Vapnik for more information on VC theory . As a result, it suffices to consider a finite subset of the hypotheses consisting of just one representative of each unique labeling assignment. Furthermore, the computational complexity of GBS is proportional to $N\,|{\cal X}|$ in this case.

VI Related Work

Generalized binary search can be viewed as a generalization of classic binary search, Shannon-Fano coding as noted by Goodman and Smyth , and channel coding with noiseless feedback as studied by Horstein . Problems of this nature arise in many applications, including channel coding (e.g., the work of Horstein and Zigangirov ), experimental design (e.g., as studied by Rényi ), disease diagnosis (e.g., see the work of Loveland ), fault-tolerant computing (e.g., the work of Feige et al ), the scheduling problem considered by Kosaraju et al , computer vision problems investigated by Geman and Jedynak and Arkin et al ), image processing problems studied by Korostelev and Kim , and active learning research; for example the investigations by Freund et al , Dasgupta , Balcan et al , and Castro and Nowak .

Past work has provided a partial characterization of this problem. If the responses to queries are noiseless, then selecting the sequence of queries from ${\cal X}$ is equivalent to determining a binary decision tree, where a sequence of queries defines a path from the root of the tree (corresponding to ${\cal H}$) to a leaf (corresponding to a single element of ${\cal H}$). In general the determination of the optimal (worst- or average-case) tree is NP-complete as shown by Hyafil and Rivest . However, there exists a greedy procedure that yields query sequences that are within a factor of $\log N$ of the optimal search tree depth; this result has been discovered independently by several researchers including Loveland , Garey and Graham , Arkin et al , and Dasgupta . The greedy procedure is referred to here as Generalized Binary Search (GBS) or the splitting algorithm, and it reduces to classic binary search, as discussed in Section V-A.

The number of queries an algorithm requires to determine $h^{*}$ is called the query complexity of the algorithm. Since the hypotheses are assumed to be distinct, it is clear that the query complexity of GBS is at most $N$ (because it is always possible to find query that eliminates at least one hypothesis at each step). In fact, there are simple examples (see Section V-A) demonstrating that this is the best one can hope to do in general. However, it is also true that in many cases the performance of GBS can be much better, requiring as few as $\log_{2}(N)$ queries. In classic binary search, for example, half of the hypotheses are eliminated at each step (e.g., refer to the textbook by Cormen et al ). Rényi first considered a form of binary search with noise and explored its connections with information theory . In particular, the problem of sequential transmission over a binary symmetric channel with noiseless feedback, as formulated by Horstein and studied by Burnashev and Zigangirov and more recently by Pelc et al , is equivalent to a noisy binary search problem.

There is a large literature on learning from queries; see the review articles by Angluin . This paper focuses exclusively on membership queries (i.e., an $x\in{\cal X}$ is the query and the response is $h^{*}(x)$), although other types of queries (equivalence, subset, superset, disjointness, and exhaustiveness) are possible as discussed by Angluin . Arbitrary queries have also been investigated, in which the query is a subset of ${\cal H}$ and the output is $+1$ if $h^{*}$ belongs to the subset and $-1$ otherwise. A finite collection of hypotheses ${\cal H}$ can be successively halved using arbitrary queries, and so it is possible to determine $h^{*}$ with $\log_{2}N$ arbitrary queries, the information-theoretically optimal query complexity discussed by Kulkarni et al . Membership queries are the most natural in function learning problems, and because this paper deals only with this type we will simply refer to them as queries throughout the rest of the paper. The number of queries required to determine a binary-valued function in a finite collection of hypotheses can be bounded (above and below) in terms of a combinatorial parameter of $({\cal X},{\cal H})$ due to Hegedüs (see the work of Hellerstein et al for related work). Due to its combinatorial nature, computing such bounds are generally NP-hard. In contrast, the geometric relationship between ${\cal X}$ and ${\cal H}$ developed in this paper leads to an upper bound on the query complexity that can be determined analytically or computed in polynomial time in many cases of interest.

The term GBS is used in this paper to emphasize connections and similarities with classic binary search, which is a special case the general problem considered here. Classic binary search is equivalent to learning a one-dimensional binary-valued threshold function by selecting point evaluations of the function according to a bisection procedure. Consider the threshold function $h_{t}(x):=\mbox{sign}(x-t)$ on the interval ${\cal X}:=$ for some threshold value $t\in(0,1)$. Throughout the paper we adopt the convention that $\mbox{sign}(0)=+1$. Suppose that $t$ belongs to the discrete set $\{\frac{1}{N+1},\dots,\frac{N}{N+1}\}$ and let ${\cal H}$ denote the collection of threshold functions $h_{1},\dots,h_{N}$. The value of $t$ can then determined from a constant times $\log N$ queries using a bisection procedure analogous to the game of twenty questions. In fact, this is precisely what GBS performs in this case (i.e., GBS reduces to classic binary search in this setting). If $N=2^{m}$ for some integer $m$, then each point evaluation provides one bit in the $m$-bit binary expansion of $t$. Thus, classic binary search is information-theoretically optimal; see the book by Traub, Wasilkowski and Wozniakowski for a nice treatment of classic bisection and binary search. The main results of this paper generalize the salient aspects of classic binary search to a much broader class of problems. In many (if not most) applications it is unrealistic to assume that the responses to queries are without error. A form of binary search with noise appears to have been first posed by Rényi . The noisy binary search problem arises in sequential transmission over a binary symmetric channel with noiseless feedback studied by Horstein and Zigangirov . The survey paper by Pelc et al discusses the connections between search and coding problems. In channel coding with feedback, each threshold corresponds to a unique binary codeword (the binary expansion of $t$). Thus, channel coding with noiseless feedback is equivalent to the problem of learning a one-dimensional threshold function in binary noise, as noted by Burnashev and Zigangirov . The near-optimal solutions to the noisy binary search problem first appear in these two contexts. Discrete versions of Horstein’s probabilistic bisection procedure were shown to be information-theoretically optimal (optimal decay of the error probability) in the works of Zigangirov and Burnashev . More recently, the same procedure was independently proposed and analyzed in the context of noise-tolerant versions of the classic binary search problem by Karp and Kleinberg , which was motivated by applications ranging from investment planning to admission control in queueing networks. Closely related approaches are considered in the work of Feige et al . The noisy binary search problem has found important applications in the minimax theory of sequential, adaptive sampling procedures proposed by Korostelov and Kim for image recovery and binary classification problems studied by Castro and Nowak . We also mention the works of Rivest et al , Spencer and Aslam and Dhagat , and Dhagat et al , which consider adversarial situations in which the total number of erroneous oracle responses is fixed in advance.

One straightforward approach to noisy GBS is to follow the GBS algorithm, but to repeat the query at each step multiple times in order to decide whether the response is more probably $+1$ or $-1$. This simple approach has been studied in the context of noisy versions of classic binary search and shown to perform significantly worse than other approaches in the work of Karp and Kleinberg ; perhaps not surprising since this is essentially a simple repetition code approach to communicating over a noisy channel. A near-optimal noise-tolerant version of GBS was developed in this paper. The algorithm can be viewed as a non-trivial generalization of Horstein’s probabilistic bisection procedure. Horstein’s method relies on the special structure of classic binary search, namely that the hypotheses and queries can be naturally ordered together in the unit interval. Horstein’s method is a sequential Bayesian procedure. It begins with uniform distribution over the set of hypotheses. At each step, it queries at the point that bisects the probability mass of the current distribution over hypotheses, and then updates the distribution according to Bayes rule. Horstein’s procedure isn’t directly applicable to situations in which the hypotheses and queries cannot be ordered togetherl, but the geometric condition developed in this paper provides similar structure that is exploited here to devise a generalized probabilistic bisection procedure. The key elements of the procedure and the analysis of its convergence are fundamentally different from those in the classic binary search work of Burnashev and Zigangirov and Karp and Kleinberg .

VII Conclusions and Possible Extensions

This paper investigated a generalization of classic binary search, called GBS, that extends it to arbitrary query and hypothesis spaces. While the GBS algorithm is well-known, past work has only partially characterized its capabilities. This paper developed new conditions under which GBS (and a noise-tolerant variant) achieve the information-theoretically optimal query complexity. The new conditions are based on a novel geometric relation between the query and hypothesis spaces, which is verifiable analytically and/or computationally in many cases of practical interest. The main results are applied to learning multidimensional threshold functions, a problem arising routinely in image processing and machine learning.

Let us briefly consider some possible extensions and open problems. First recall that in noisy situations it is assumed that the binary noise probability has a known upper bound $\alpha<1/2$. It is possible to accommodate situations in which the bound is unknown a priori. This can be accomplished using an NGBS algorithm in which the number of repetitions of each query, $R$, is determined adaptively to adjust to the unknown noise level. This procedure was developed by the author in , and is based on a straightforward, iterated application of Chernoff’s bound. Similar strategies have been suggested as a general approach for devising noise-tolerant learning algorithms . Using an adaptive procedure for adjusting the number of repetitions of each query yields an NGBS algorithm with query complexity bound proportional to $\log N\log\frac{\log N}{\delta}$, the same order as that of the NGBS algorithm discussed above which assumed a known bound $\alpha$. Whether or not the additional logarithmic factor can be removed if the noise bound $\alpha$ is unknown is an open question. Adversarial noise models in which total number of errors is fixed in advance, like those considered by Rivest et al and Spencer , are also of interest in classic binary search problems. Repeating each query multiple times and taking the majority vote of the responses, as in the NGBS algorithm, is a standard approach to adversarial noise. Thus, NGBS provides an algorithm for generalized binary search with adversarial noise.

VIII Appendix

First we derive the precise form of $p_{1},p_{2},\dots$ is derived as follows. Let $\delta_{i}=(1+\sum_{h}p_{i}(h)\,z_{i}(h))/2$, the weighted proportion of hypotheses that agree with $y_{i}$. The factor that normalizes the updated distribution in (2) is related to $\delta_{i}$ as follows. Note that \sum_{h}p_{i}(h)\,\beta^{(1-z_{i}(h))/2}(1-\beta)^{(1+z_{i}(h))/2}=\sum_{h:z_{i}(h)=-1}p_{i}(h)\beta+\sum_{h:z_{i}(h)=1}p_{i}(h)(1-\beta)=\mbox{(1-\delta_{i})\beta+\delta_{i}(1-\beta)}. Thus,

Denote the reciprocal of the update factor for $p_{i+1}(h^{*})$ by

where $z_{i}(h^{*})=h^{*}(x_{i})y_{i}$, and observe that $p_{i+1}(h^{*})=p_{i}(h^{*})/\gamma_{i}$. Thus,

For every $A\in{\cal A}$ and every $h\in{\cal H}$ let $h(A)$ denote the value of $h$ on the set $A$. Define $\delta_{A}^{+}=(1+\sum_{h}p_{i}(h)h(A))/2$, the proportion of hypotheses that take the value $+1$ on $A$. Let $A_{i}$ denote that set that $x_{i}$ is selected from, and consider the four possible situations:

Define $\gamma_{i}^{+}(A_{i}):=\delta_{A_{i}}^{+}+(1-\delta_{A_{i}}^{+})\left[\frac{\beta(1-q_{i})}{1-\beta}+\frac{q_{i}(1-\beta)}{\beta}\right]$. Similarly, if $h^{*}(A_{i})=-1$, then

By assumption $q_{i}\leq\alpha<1/2$, and since $\alpha\leq\beta<1/2$ the factor $\frac{\beta(1-q_{i})}{1-\beta}+\frac{q_{i}(1-\beta)}{\beta}\leq\frac{\beta(1-\alpha)}{1-\beta}+\frac{\alpha(1-\beta)}{\beta}\leq 1$ (strictly less than $1$ if $\beta>\alpha$). Define

VIII-B Proof of Theorem 4

The proof amounts to obtaining upper bounds for $\gamma_{i}^{+}(A_{i})$ and $\gamma_{i}^{-}(A_{i})$, defined above in (7) and (8). Consider two distinct situations. Define $b_{i}:=\min_{A\in{\cal A}}|W(p_{i},A)|$. First suppose that there do not exist neighboring sets $A$ and $A^{\prime}$ with $W(p_{i},A)>b_{i}$ and $W(p_{i},A^{\prime})<-b_{i}$. Then by Lemma 1, this implies that $b_{i}\leq c^{*}$, and according the query selection step of the modified SGBS algorithm, $A_{i}=\arg\min_{A}\left|W(p_{i},A)\right|$. Note that because $|W(p_{i},A_{i})|\leq c^{*}$, $(1-c^{*})/2\ \leq\ \delta_{A_{i}}^{+}\ \leq(1+c^{*})/2$. Hence, both $\gamma_{i}^{+}(A_{i})$ and $\gamma_{i}^{-}(A_{i})$ are bounded above by $1-\varepsilon_{0}(1-c^{*})/2$.

Now suppose that there exist neighboring sets $A$ and $A^{\prime}$ with $W(p_{i},A)>b_{i}$ and $W(p_{i},A^{\prime})<-b_{i}$. Recall that in this case $A_{i}$ is randomly chosen to be $A$ or $A^{\prime}$ with equal probability. Note that $\delta_{A}^{+}>(1+b_{i})/2$ and $\delta_{A^{\prime}}^{+}<(1-b_{i})/2$. If $h^{*}(A)=h^{*}(A^{\prime})=+1$, then applying (7) results in

since $0\leq\delta_{A}^{+}-\delta_{A^{\prime}}^{+}\leq 1$. The final possibility is that $h^{*}(A)=+1$ and $h^{*}(A^{\prime})=-1$. Apply (7) on $A$ and (8) on $A^{\prime}$ to obtain

Next, use the fact that because $A$ and $A^{\prime}$ are neighbors, $\delta_{A}^{+}-\delta_{A^{\prime}}^{+}=p_{i}(h^{*})-p_{i}(-h^{*})$; if $-h^{*}$ does not belong to ${\cal H}$, then $p_{i}(-h^{*})=0$. Hence,

VIII-C Proof of Theorem 5

where the last inequality follows from the fact that $|R(h_{1})-R(h_{2})|\leq|R_{\Delta}(h_{1})-R_{\Delta}(h_{2})|$.

The function $2u\,e^{-\zeta u^{2}}$ attains its maximum at $u=\sqrt{\frac{2}{e\zeta}}<\sqrt{1/\zeta}$, and therefore

Now taking the expectation with respect to $h_{1}$ and $h_{2}$ (i.e., with respect to the queries used for the selection of $h_{1}$ and $h_{2}$)

References