Constrained Binary Identification Problem.

Amin Karbasi, Morteza ZadimoghaddamSTACS 2013 · OpenReview

TL;DR

This paper tackles the "20 Questions" game with real-world constraints. It introduces novel polynomial-time approximation algorithms for efficiently identifying an object within a set, even when queries are restricted by graph structures, general costs, or submodular functions. The work provides theoretical guarantees for these algorithms, showing they can find the target with near-optimal efficiency.

What Problem Does This Paper Address?

Imagine you're trying to find a specific item in a large collection, and you can only ask yes/no questions. This is the essence of the "20 Questions" game, which is closely related to information theory and data compression. In an ideal world, where any question is allowed, Huffman coding provides an optimal strategy. However, real-world scenarios often impose limitations:

  • Network Tomography: In sensor networks, communication might be restricted to neighbors, or only certain groups of nodes can be queried together.
  • Interactive Content Search: When humans are involved (e.g., in image recognition), queries might be limited by complexity or cognitive load, leading to cost-based restrictions.

These constraints make finding the optimal strategy NP-hard. This paper aims to bridge this gap by developing efficient approximation algorithms that work under these realistic limitations.

Methods

The authors propose novel polynomial-time approximation algorithms for three types of constraints:

  • Graph Constraints: If the objects are arranged in a graph, and a query is only admissible if the queried subset forms a connected subgraph, they provide a constant-factor approximation algorithm. This algorithm leverages a divide-and-conquer strategy, similar to binary search, adapted for graph connectivity.
  • Cost Function Constraints: When queries have a cost that depends on their size (e.g., larger queries are more expensive), they develop an algorithm that achieves an approximation ratio of O(log(log n)). This involves clustering objects by probability and using a dynamic programming approach.
  • Submodular Constraints: This is a generalization of cost functions where the marginal cost of adding an element to a set decreases as the set grows. For these constraints, they present an algorithm with an O(log n) approximation ratio. This approach involves a bicriteria approximation to find a suitable initial query set and then a recursive strategy.

A common theme across these algorithms is a greedy approach: at each step, they select a query that aims to split the remaining possibilities as evenly as possible while respecting the given constraints.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging Theory and Practice: The paper demonstrates how theoretical concepts from information theory (like entropy) can be extended to practical problems with real-world constraints, moving beyond idealized scenarios.
  • Generalizing Constraints: By formalizing constraints as graph structures, cost functions, and submodular functions, the authors provide a unified framework for tackling a variety of identification problems.
  • Greedy Strategies are Powerful: The proposed algorithms often rely on greedy choices, which, despite their simplicity, yield provable approximation guarantees for complex NP-hard problems.
  • The Power of Approximation: For problems that are computationally intractable to solve optimally, approximation algorithms offer a practical path to finding near-optimal solutions with guaranteed performance bounds.

Key Results

The paper presents approximation algorithms with the following performance guarantees:

  • Graph Constraints: Constant-factor approximation.
  • Cost Function Constraints: O(log(log n)) gap from the optimal cost.
  • Submodular Constraints: O(log n) gap from the optimal cost.

These results are achieved in polynomial time and are proven theoretically.

Limitations and Future Work

The authors acknowledge that while they believe the problems studied are NP-hard, they have not provided rigorous proofs for this. This is identified as an interesting future research direction. Additionally, the paper focuses on deterministic policies for identifying the target. Exploring randomized policies or further refining the approximation ratios for specific constraint types could be avenues for future work.

Summary updated

Abstract

We consider the problem of building a binary decision tree, to locate an object within a set by way of the least number of membership queries. This problem is equivalent to the "20 questions game" of information theory and is closely related to lossless source compression. If any query is admissible, Huffman coding is optimal with close to H[P] questions on average, the entropy of the prior distribution P over objects. However, in many realistic scenarios, there are constraints on which queries can be asked, and solving the problem optimally is NP-hard. We provide novel polynomial time approximation algorithms where constraints are defined in terms of "graph", general "cost", and "submodular" functions. In particular, we show that under graph constraints, there exists a constant approximation algorithm for locating the target in the set. We then extend our approach for scenarios where the constraints are defined in terms of general cost functions that depend only on the size of the query and provide an approximation algorithm that can find the target within O(log(log n)) gap from the cost of the optimum algorithm. Submodular functions come as a natural generalization of cost functions with decreasing marginals. Under submodular set constraints, we devise an approximation algorithm that can find the target within O(log n) gap from the cost of the optimum algorithm. The proposed algorithms are greedy in a sense that at each step they select a query that most evenly splits the set without violating the underlying constraints. These results can be applied to network tomography, active learning and interactive content search.
BibTeX
@inproceedings{karbasi2013constrained,
  author = {Amin Karbasi and Morteza Zadimoghaddam},
  title = {{Constrained Binary Identification Problem.}},
  booktitle = {STACS},
  year = {2013},
  url = {https://openreview.net/forum?id=pylITuS1dwRW},
}
Figure