Parity Queries for Binary Classification

Abstract

Consider a query-based data acquisition problem that aims to recover the values of k binary variables from parity (XOR) measurements of chosen subsets of the variables. Assume the response model where only a randomly selected subset of the measurements is received. We propose a method for designing a sequence of queries so that the variables can be identified with high probability using as few (n) measurements as possible. We define the query difficulty d as the average size of the query subsets and the sample complexity n as the minimum number of measurements required to attain a given recovery accuracy. We obtain fundamental trade-offs between recovery accuracy, query difficulty, and sample complexity. In particular, the necessary and sufficient sample complexity required for recovering all k variables with high probability is n = c_0 , (k k)/d\ and the sample complexity for recovering a fixed proportion (1-)k of the variables for =o(1) is n = c_1 , (k (1/))/d\, where c_0, c_1>0.

Tasks

Reproductions