The posterior matching scheme, for feedback encoding of a message point lying on the unit interval over memoryless channels, maximizes mutual information for an arbitrary number of channel uses. However, it in general does not always achieve any positive rate; so far, elaborate analyses have been required to show that it achieves any positive rate below capacity. More recent efforts have introduced a random "dither" shared by the encoder and decoder to the problem formulation, to simplify analyses and guarantee that the randomized scheme achieves any rate below capacity. Motivated by applications (e.g. human-computer interfaces) where (a) common randomness shared by the encoder and decoder may not be feasible and (b) the message point lies in a higher dimensional space, we focus here on the original formulation without common randomness, and use optimal transport theory to generalize the scheme for a message point in a higher dimensional space. By defining a stricter, almost sure, notion of message decoding, we use classical probabilistic techniques (e.g. change of measure and martingale convergence) to establish succinct necessary and sufficient conditions on when the message point can be recovered from infinite observations: Birkhoff ergodicity of a random process sequentially generated by the encoder. We also show a surprising "all or nothing" result: the same ergodicity condition is necessary and sufficient to achieve any rate below capacity. We provide applications of this message point framework in human-computer interfaces and multi-antenna communications.
Applications and variations of this formulation are manyfold. The Horstein scheme, combined with arithmetic coding of a sequence of symbols in an ordered symbolic alphabet to represent any sequence with enumerative source encoding @cite_56 as a message point on the @math line, has been used for brain-computer interfaces to specify a sentence or a smooth path @cite_18 , to navigate mobile robots @cite_14 , and to remotely teleoperate an unmanned aircraft @cite_8 . Many active learning problems borrow principles from posterior matching, but with different formulations or performance criteria; generalized 20 questions for target search @cite_26 @cite_24 and generalized binary search for function search @cite_49 @cite_37 serve as examples. Naghsvar and Tavidi considered variable-length encoding with feedback and utilized principles from stochastic control and posterior matching to demonstrate non-asymptotic upper bounds on expected code length and deterministic one-phase coding schemes that achieve capacity and attain optimal error exponents @cite_9 . More general variable-length formulations of active hypothesis testing, where the statistics of the measurement may depend on the query or are controllable, have been developed in @cite_10 @cite_4 @cite_23 @cite_51 . Feedback coding channels with memory using principles from posterior matching have been explored in @cite_3 @cite_50 @cite_59 @cite_7 .
@cite_18 @cite_14 @cite_26 @cite_37 @cite_4 @cite_8 @cite_7 @cite_9 @cite_3 @cite_56 @cite_24 @cite_49 @cite_23 @cite_51 @cite_50 @cite_59 @cite_10
2168790074 2062626064 1965313644 2963912378 2010661952 2963656208 1992720861 2163608699 2034323860 2725485065 2106447856 2540076116 2744584070 2081237665 2509220592 1990503235
This paper presents an interface for navigating a mobile robot that moves at a fixed speed in a planar workspace, with noisy binary inputs that are obtained asynchronously at low bit-rates from a human user through an electroencephalograph (EEG). The approach is to construct an ordered symbolic language for smooth planar curves and to use these curves as desired paths for a mobile robot. The underlying problem is then to design a communication protocol by which the user can, with vanishing error probability, specify a string in this language using a sequence of inputs. Such a protocol, provided by tools from information theory, relies on a human user's ability to compare smooth curves, just like they can compare strings of text. We demonstrate our interface by performing experiments in which twenty subjects fly a simulated aircraft at a fixed speed and altitude with input only from EEG. Experimental results show that the majority of subjects are able to specify desired paths despite a wide range of errors made in decoding EEG signals. We consider the problem of 20 questions with noise for multiple players under the minimum entropy criterion in the setting of stochastic search, with application to target localization. Each player yields a noisy response to a binary query governed by a certain error probability. First, we propose a sequential policy for constructing questions that queries each player in sequence and refines the posterior of the target location. Second, we consider a joint policy that asks all players questions in parallel at each time instant and 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. Third, we prove an equivalence between the two schemes showing that, despite the fact that the sequential scheme has access to a more refined filtration, the joint scheme performs just as well on average. Fourth, we establish convergence rates of the mean-square error and derive error exponents. Finally, we obtain an extension to the case of unknown error probabilities. This framework provides a mathematical model for incorporating a human in the loop for active machine learning systems. This paper investigates the problem of determining a binary-valued function through a sequence of strategically selected queries. The focus is an algorithm called Generalized Binary Search (GBS). GBS is a well-known greedy algorithm for determining a binary-valued function through a sequence of strategically selected queries. At each step, a query is selected that most evenly splits the hypotheses under consideration into two disjoint subsets, a natural generalization of the idea underlying classic binary search. This paper develops novel incoherence and geometric conditions under which GBS achieves the information-theoretically optimal query complexity; i.e., given a collection of N hypotheses, GBS terminates with the correct function after no more than a constant times logN queries. Furthermore, a noise-tolerant version of GBS is developed that also achieves the optimal query complexity. These results are applied to learning halfspaces, a problem arising routinely in image processing and machine learning. Consider a target moving at a constant velocity on a unit-circumference circle, starting at an arbitrary location. To acquire the target, any region of the circle can be probed to obtain a noisy measurement of the target’s presence, where the noise level increases with the size of the probed region. We are interested in the expected time required to find the target to within some given resolution and error probability. For a known velocity and a given reliability, we provide an asymptotical characterization of the optimal tradeoff between time and resolution. Considering an asymptotically diminishing error probability, we derive the maximal targeting rate, and show that in contrast to the well-studied case of constant measurement noise, measurement dependent noise incurs a multiplicative gap in the maximal targeting rate between adaptive and non-adaptive search strategies. Moreover, for all rates below this maximal rate, our adaptive strategy attains the optimal rate-reliability tradeoff. We further show that accounting for a target moving at an unknown fixed velocity, the optimal non-adaptive search strategy incurs a factor of at least two in the maximal targeting rate. This article presents a new approach to designing brain–computer interfaces (BCIs) that explicitly accounts for both the uncertainty of neural signals and the important role of sensory feedback. This approach views a BCI as the means by which users communicate intent to an external device and models intent as a string in an ordered symbolic language. This abstraction allows the problem of designing a BCI to be reformulated as the problem of designing a reliable communication protocol using tools from feedback information theory. Here, this protocol is given by a posterior matching scheme. This scheme is not only provably optimal but also easily understood and implemented by a human user. Experimental validation is provided by an interface for text entry and an interface for tracing smooth planar curves, where input is taken in each case from an electroencephalograph during left- and right-hand motor imagery. The reliability function of memoryless channels with noiseless feedback and variable-length coding has been found to be a linear function of the average rate in the classic work of Burnashev. In this work we consider unifilar channels with noiseless feedback and study specific transmission schemes, the performance of which provides lower bounds for the channel reliability function. In unifilar channels the channel state evolves in a deterministic fashion based on the previous state, input, and output, and is known to the transmitter but is unknown to the receiver. We consider a two-stage transmission scheme. In the first stage, both transmitter and receiver summarize their common information in an M-dimensional vector with elements in the state space of the unifilar channel and an M-dimensional probability mass function, with M being the number of messages. The second stage, which is entered when one of the messages is sufficiently reliable, is resolving a binary hypothesis testing problem. The analysis assumes the presence of some common randomness shared by the transmitter and receiver, and is based on the study of the log-likelihood ratio of the transmitted message posterior belief, and in particular on the study of its multistep drift. Simulation results confirm that the bounds are tight compared to the upper bounds derived in a companion paper. This paper considers the problem of variable-length coding over a discrete memoryless channel with noiseless feedback. This paper provides a stochastic control view of the problem whose solution is analyzed via a newly proposed symmetrized divergence, termed extrinsic Jensen–Shannon (EJS) divergence. It is shown that strictly positive lower bounds on EJS divergence provide nonasymptotic upper bounds on the expected code length. This paper presents strictly positive lower bounds on EJS divergence, and hence nonasymptotic upper bounds on the expected code length, for the following two coding schemes: 1) variable-length posterior matching and 2) MaxEJS coding scheme that is based on a greedy maximization of the EJS divergence. As an asymptotic corollary of the main results, this paper also provides a rate–reliability test. Variable-length coding schemes that satisfy the condition(s) of the test for parameters @math and @math are guaranteed to achieve a rate @math and an error exponent @math . The results are specialized for posterior matching and MaxEJS to obtain deterministic one-phase coding schemes achieving capacity and optimal error exponent. For the special case of symmetric binary-input channels, simpler deterministic schemes of optimal performance are proposed and analyzed. For a memoryless channel, although feedback cannot increase capacity, it can reduce the complexity and or improve the error performance of a communication system. Recently, Shayevitz and Feder proposed the posterior matching scheme (PMS) which is a simple recursive transmission scheme that achieves the capacity of memoryless channels with feedback. Furthermore, Coleman provided a Lyapunov function approach to prove capacity achievability of the PMS. In this paper, we investigate a capacity-achieving PMS for the case of finite-state channels (FSCs). We first derive a single-letter expression for the capacity of the FSC with delayed output and state feedback by formulating the problem in a stochastic control framework. The resulting capacity expression can be evaluated using dynamic programming. We then propose a simple recursive PMS-like transmission scheme. To prove capacity achievability of the proposed PMS, we identify an appropriate Markov chain induced by the PMS. Let S be a given subset of binary n-sequences. We provide an explicit scheme for calculating the index of any sequence in S according to its position in the lexicographic ordering of S . A simple inverse algorithm is also given. Particularly nice formulas arise when S is the set of all n -sequences of weight k and also when S is the set of all sequences having a given empirical Markov property. Schalkwijk and Lynch have investigated the former case. The envisioned use of this indexing scheme is to transmit or store the index rather than the sequence, thus resulting in a data compression of ( ) n . Abstract This paper considers the problem of adaptively searching for an unknown target using multiple agents connected through a time-varying network topology. Agents are equipped with sensors capable of fast information processing, and we propose a decentralized collaborative algorithm for controlling their search given noisy observations. Specifically, we propose decentralized extensions of the adaptive query-based search strategy that combines elements from the 20 questions approach and social learning. Under standard assumptions on the time-varying network dynamics, we prove convergence to correct consensus on the value of the parameter as the number of iterations go to infinity. The convergence analysis takes a novel approach using martingale-based techniques combined with spectral graph theory. Our results establish that stability and consistency can be maintained even with one-way updating and randomized pairwise averaging, thus providing a scalable low complexity method with performance guarantees. We illustrate the effectiveness of our algorithm for random network topologies. This paper analyzes the potential advantages and theoretical challenges of "active learning" algorithms. Active learning involves sequential sampling procedures that use information gleaned from previous samples in order to focus the sampling and accelerate the learning process relative to "passive learning" algorithms, which are based on nonadaptive (usually random) samples. There are a number of empirical and theoretical results suggesting that in certain situations active learning can be significantly more effective than passive learning. However, the fact that active learning algorithms are feedback systems makes their theoretical analysis very challenging. This paper aims to shed light on achievable limits in active learning. Using minimax analysis techniques, we study the achievable rates of classification error convergence for broad classes of distributions characterized by decision boundary regularity and noise conditions. The results clearly indicate the conditions under which one can expect significant gains through active learning. Furthermore, we show that the learning rates derived are tight for "boundary fragment" classes in d-dimensional feature spaces when the feature marginal density is bounded from above and below. Consider a target search problem on a unit interval where at any given time an agent can choose a region to probe into for the presence of the target in that region. The measurement noise is assumed to be increasing with the size of the search region the agent chooses. In this paper, a single-phase sequential and adaptive search algorithm is proposed and shown to achieve the best possible targeting rate and error exponent among all adaptive search algorithms. The proposed algorithm simply adopts a low complexity sorting operation on the posterior of the target and then pick up locations with larger posterior until the probability that the search region contains the target is closest to half. This paper considers the problem of searching for the unknown location of a target among a finite number of possible locations by probing multiple locations simultaneously. Outcome of each search measurement is corrupted by Gaussian noise whose intensity is proportional to the number of locations probed. We characterize a non-asymptotic lower bound on adaptivity gain; i.e. reduction in the expected number of measurements under an adaptive search strategies over the non-adaptive search strategies. Then we investigate the adaptivity gain in two complementary asymptotic regimes: one where the total search area is kept fixed but the location width is shrinking or the search resolution is increasing, and the other where each location width is fixed but the total search area is growing. Interestingly, adaptivity gain grows in distinctly different manner in these two regimes. In particular, adaptivity gains are significant in the later regime when the total search space grows; implying adaptivity is far more critical when either total search area or the noise intensity is large. The capacity of unifilar finite-state channels with feedback has been recently derived in the form of a single-letter expression and it has been evaluated analytically for a number of channels of interest, such as the trapdoor channel and the Ising channel with feedback. In this paper, we investigate transmission schemes for this class of channels. These schemes are inspired by the posterior matching scheme (PMS) introduced for memoryless channels with feedback. The transmission scheme is proven to achieve zero rate and is conjectured to achieve channel capacity. Shayevitz and Feder proposed a capacity-achieving sequential transmission scheme for memoryless channels called posterior matching (PM). The proof of capacity achievability of PM is involved and requires invertibility of the PM kernel (also referred to as one-step invertibility). Recent work by the same authors provided a simpler proof but still requires PM kernel invertibility. Consider a decision maker who is responsible to dynamically collect observations so as to enhance his information about an underlying phenomena of interest in a speedy manner while accounting for the penalty of wrong declaration. Due to the sequential nature of the problem, the decision maker relies on his current information state to adaptively select the most informative'' sensing action among the available ones. In this paper, using results in dynamic programming, lower bounds for the optimal total cost are established. The lower bounds characterize the fundamental limits on the maximum achievable information acquisition rate and the optimal reliability. Moreover, upper bounds are obtained via an analysis of two heuristic policies for dynamic selection of actions. It is shown that the first proposed heuristic achieves asymptotic optimality, where the notion of asymptotic optimality, due to Chernoff, implies that the relative difference between the total cost achieved by the proposed policy and the optimal total cost approaches zero as the penalty of wrong declaration (hence the number of collected samples) increases. The second heuristic is shown to achieve asymptotic optimality only in a limited setting such as the problem of a noisy dynamic search. However, by considering the dependency on the number of hypotheses, under a technical condition, this second heuristic is shown to achieve a nonzero information acquisition rate, establishing a lower bound for the maximum achievable rate and error exponent. In the case of a noisy dynamic search with size-independent noise, the obtained nonzero rate and error exponent are shown to be maximum.