A Collaborative 20 Questions Model for Target Search with Human-Machine Interaction

Abstract

We consider the problem of 20 questions with noise for collaborative players under the minimum entropy criterion in the setting of stochastic search, with application to target localization. First, assuming conditionally independent collaborators, we characterize the structure of the optimal policy for constructing the sequence of questions. This generalizes the single player probabilistic bisection method for stochastic search problems. Second, we prove a separation theorem showing that optimal joint queries achieve the same performance as a greedy sequential scheme. Third, we establish convergence rates of the mean-squared error (MSE). Fourth, we derive upper bounds on the MSE of the sequential scheme. This framework provides a mathematical model for incorporating a human in the loop for active machine learning systems.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 2013
Accession Number
ADA581713

Entities

People

  • Alfred O. Hero III
  • Brian M. Sadler
  • Theodoros Tsiligkaridis

Organizations

  • University of Michigan

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Automated Target Recognition
  • Channel Capacity
  • Classification
  • Computer Programming
  • Computer Science
  • Convergence
  • Data Science
  • Electrical Engineering
  • Estimators
  • Human-Machine Interaction
  • Iterations
  • Probability
  • Random Variables
  • Signal Processing
  • Target Recognition

Readers

  • Agent-Based Social Robotics and Mobile-Assisted Learning in Virtual Environments.
  • Graph Algorithms and Convex Optimization.
  • Statistical inference.

Technology Areas

  • AI & ML
  • AI & ML - Machine Learning Algorithms