Active Learning and Best-Response Dynamics
We examine an important setting for engineered systems in which low-power distributed sensors are each making highly noisy measurements of some unknown target function. A center wants to accurately learn this function by querying a small number of sensors, which ordinarily would be impossible due to the high noise rate. The question we address is whether local communication among sensors, together with natural best-response dynamics in an appropriately-defined game, can denoise the system without destroying the true signal and allow the center to succeed from only a small number of active queries. By using techniques from game theory and empirical processes, we prove positive (and negative) results on the denoising power of several natural dynamics. We then show experimentally that when combined with recent agnostic active learning algorithms, this process can achieve low error from very few queries, performing substantially better than active or passive learning without these denoising dynamics as well as passive learning with denoising.
SUMMARY:This paper combines dynamics from game theory and active learning techniques to solve a problem where a center tries to determine a decision boundary from noisy sensors.  Under the assumption that the noise is independent, the authors prove that simple simultaneous or asynchronous game dynamics successfully denoise the system with high probability, given enough sensors.  To illustrate the effectiveness of the denoising together with active learning (which is known to perform poorly in the presence of large amounts of noise), the authors give experiments in the plane which show superior results compared with learning without denoising and passive learning with denoising.CRITIQUE:The results are interesting, the approach is novel, and the exposition is clear.  My only concern is the significance.  I believe the authors make a good case in general that denoising a collection of sensors, using simple distributed local computations, can be effective enough in some situations to allow active learning to be applied, thereby enabling an efficient sensor query load.  However, the bounds given in the analysis leave a lot of room to question the applicability of this approach in practice.  Is it really reasonable to have N = 10000 for r = 0.1, as in the experiments?  Some rough sense of reasonable settings of these parameters is badly needed to evaluate the utility of this approach.  For example, if r = 0.8, then surely one would want a more sophisticated denoising algorithm, since the theoretical guarantees break down, and moreover nodes have unreasonable communication loads.  Similarly, if r=0.001, then the communication graph is likely to be disconnected, unless N is even larger.  What settings of r, N, eta, etc are reasonable?  Likewise, is a uniform distribution reasonable?As another high level point, I was surprised not to see more discussion of the 2r band around the separator within which all bets are off -- are we assuming r is so small that this is negligible?  For large r, it seems that a slightly more sophisticated distance-weighted approach would be much better here.  This (or some similar procedure) is stated in a footnote to perform similarly to the simple majority; intuitively, the two should behave roughly the same away from the boundary, but the distance weighting should perform significantly better near the boundary, even for smaller r.  A more fine-grained comparison near the boundary would be nice here.SPECIFIC COMMENTS:pg 1. This paper would be much more accessible if terms such as active learning and agnostic active learning were defined in simple terms after their first use (e.g. "active learning, a branch of machine learning where...")pg 2. "sensors within distance r are connected by an edge" -- as mentioned above, the relationship between r and d (dim) and N is not discussed much in the text; aside from what values one should expect in practice, it might be good to mention some results from theoretical computer science / graph theory about the connectedness of the communication graph.pg 3. it would help to give an overview of section 3 at the top, since it was not stated priorpg 7. "Pockets of noise appear to be more difficult to denoise." -- the algorithm was not designed for this case, so this is not surprising.  One might expect pockets to be less severe in higher dimensions.pg 8. "A synchronous round" -- perhaps change to "One synchronous round" to avoid confusion with "asynchronous"