This is where stochastic control theory meets signal processing and information theory. Here we consider a generalization of active sequential hypothesis testing (see below) and Hidden Markov Models (HMM). Much similar to an HMM problem, we assume a Markovian stochastic process whose state is available to us only through partial (noisy) observations. In classical HMM problems, given some knowledge of the conditional distribution of observations given the true state, we are often interested in filtering or smoothing our observations to arrive at estimate of the true state of the process. However, in an information acquisition problem, very much like our treatment of active hypothesis testing, we assume that the statistics of these observations can be controlled and tuned actively and dynamically by our decision maker and beyond filtering the state estimate is used to utilize certain resources. The applications are wide and include the very fundamental problem of
An important and closely related problem is the problem of noisy active learning. In this context, we have applied our work on extrinsic Jensen--Shannon divergence to this problem to obtain strong guarantees. In particular, we have addressed the following problems:
S. Yan, K. Chaudhuri and T. Javidi. Active Learning with Logged Data, International Conference on Machine Learning (ICML), 2018
S. Yan, K. Chaudhuri and T. Javidi. Active Learning from Imperfect Labelers. Neural Information Processing Systems (NIPS) 2016
S. Yan, K. Chaudhuri and T. Javidi. Active Learning from Noisy and Abstention Feedback, Allerton Conference on Communication, Control and Computing, 2015
M. Naghshvar, T. Javidi, and K. Chaudhuri. Bayesian Active Learning With Non-Persistent Noise. IEEE Transactions on Information Theory. Vol 61. Issue: 7. July 2015
M. Naghshvar, T. Javidi, and K. Chaudhuri. Noisy Bayesian active learning. in Proceedings of 50th Annual Allerton Conference on Commununication, Control and Computation, October 2012
There is a variety of applications where the decision maker needs to track a partially observable stochastic process. The examples include:
1. Enhanced Spectrum Access:
Javidi, T.; Krishnamachari, B.; Qing Zhao; Mingyan Liu; , "Optimality of Myopic Sensing in Multi-Channel Opportunistic Access. IEEE International Conference on Communications, 2008. ICC '08, 19-23 May 2008 [here]
Ahmad, S.; Mingyan Liu; Javidi, T.; Qing Zhao; Krishnamachari, B.; , "Optimality of Myopic Sensing in Multichannel Opportunistic Access," Information Theory, IEEE Transactions on , vol.55, no.9, pp.4040-4050, Sept. 2009 [here]
P. Mansourifard, T. Javidi, and B. Krishnamachari. Optimality of Myopic Policy for a Class of Monotone Affine Restless Multi-Armed Bandits. in Proceedings of IEEE Conference on Decision and Control (CDC), December, 2012.
2. Search and Tracking with Measurement-dependent Noise:
S. Chiu and T. Javidi. Sequential Measurement-Dependent Noisy Search. Proceedings of IEEE Information Theory Workshop (ITW), September 2016
A. Lalitha and T. Javidi. Reliability of Sequential Hypothesis Testing Can Be Achieved by an Almost-Fixed-Length Test. in Proceedings of the IEEE International Symposium on Information Theory (ISIT), July 2016.
M. Naghshvar and T. Javidi. Two-Dimensional Visual Search. in Proceedings of International Symposium Information Theory (ISIT), July 2013
M. Naghshvar and T. Javidi. Rate–Reliability Tradeoff in Two-Dimensional Visual Search. in Proceedings of Iran Workshop on Communication and Information Theory (IWCIT), May 2013 [Invited]
3. And even joint source-channel coding:
T. Javidi and A. Goldsmith. Dynamic Joint Source–Channel Coding with Feedback. in Proceedings of International Symposium Information Theory (ISIT), July 2013
As one expects this area of research is very much motivated by our work on active hypothesis testing.
This is where stochastic control theory meets information theory: Consider the classic “I-SPY: Can You See What I See” game in which a child is given a page and is asked to identify the location of an object against a crowded background. Given our eyes’ inherent non-uniform information gathering across the field of vision, i.e. reduced vision perception and precision away from the center of gaze onto the periphery, the following question arises: How do our brains best control the uncertain visual information collection process and refine our belief in this and similar environments? The problem of dynamical control of an information state hardly remains as a singular childhood preoccupation with the I-SPY game nor is limited to the vision application domain. Related problems arise in the context of sequential design of scientific experiments, sensor activation in health monitoring, and even communication over noisy channels with feedback. My work with my former graduate student Mohammad Naghshvar considers a broad spectrum of applications in cognition, communications, design of experiments, and sensor management. In all of these applications, a decision maker is responsible to control the system dynamically so as to enhance his information in a speedy manner about an underlying phenomena of interest while accounting for the cost of communication, sensing, or data collection. Furthermore, due to the sequential nature of the problem, the decision maker relies on his current information state to constantly (re-)evaluate the trade-off between the precision and the cost of various actions:
M. Naghshvar, T. Javidi, and K. Chaudhuri. Noisy Bayesian active learning. in Proceedings of 50th Annual Allerton Conference on Commununication, Control and Computation, October 2012
M. Naghshvar and T. Javidi. Extrinsic Jensen--Shannon divergence with application in active hypothesis testing. in Proceedings of IEEE International Symposium on Information Theory (ISIT), July 2012
M. Naghshvar and T. Javidi. Active Sequential Hypothesis Testing: Sequentiality and Adapativity Gains. in Proccedings of Conference on Information Sciences and Systems (CISS). Princeton, NJ. 2012 [here]
M. Naghshvar and T. Javidi. Performance Bounds for Active Sequential Hypothesis Testing. to appear in Proceedings of IEEE International Symposium on Information Theory (ISIT), August 2011 [here]
M. Naghshvar and T. Javidi. Information utility in active sequential hypothesis testing. In Proceedings of Forty-eighth Annual Allerton Conference on Communication, Control, and Computing, Monticello, Illinois, 2010 [here]
M. Naghshvar and T. Javidi. Active M-ary Sequential Hypothesis Testing. in Proceedings of IEEE International Symposium on Information Theory (ISIT), 2010 [here]
For more detailed treatment, you can check out our more detailed manuscripts on arxiv:
M. Naghshvar and T. Javidi, Active Sequential Hypothesis Testing. Annals of Statistics. Vol. 41, No. 6, December 2013
(see the version on arxiv: [here] )
M. Naghshvar and T. Javidi, Sequentiality and Adaptivity Gains in Active Hypothesis Testing. To appear in IEEE Journal of Selected Topics in Signal Processing, Vol. 7, No. 5, October 2013.
(see the version on arxiv: [here] )
Interestingly, we have shown that the problem of channel coding over a memoryless noisy channel (point to point as well as multiple access) with feedback is nothing but a special case of the active sequential hypothesis problem analyzed in certain asymptotic regimes:
Mohammad Naghshvar, Tara Javidi, and Michele Wigger. Extrinsic Jensen–Shannon Divergence:
Applications to Variable-Length Coding. [Arxiv]
M. Naghshvar and T. Javidi. Optimal reliability over a DMC with feedback via deterministic sequential coding. in Proceedings of IEEE International Symposium of Information Theory and Applications (ISITA), October 2012 [here]
M. Naghshvar, M. Wigger, and T. Javidi, Optimal reliability over a class of binary-input channels with feedback. in Proceedings of IEEE Information Theory Workshop (ITW), September 2012 [here]
E. Ardestanizadeh, M. A. Wigger, Y.H. Kim, and T. Javidi. Linear-Feedback Sum-Capacity for Gaussian Multiple Access Channels. IEEE Transactions on Information Theory, Issue 1, volume 58. January 2012 [here]
E. Ardestanizadeh, M. A. Wigger, Y.H. Kim, and T. Javidi. Linear sum capacity for Gaussian multiple access channel with feedback, Proceedings of IEEE International Symposium on Information Theory (ISIT), 2010
M. Naghshvar and T. Javidi. Variable-length coding with noiseless feedback and finite messages. in Proceedings of Asilomar Conference on Signals, Systems, and Computers, November 2010 [here]
Ardetsanizadeh, E.; Javidi, T.; Young-Han Kim; Wigger, M.A.; , "On the sum capacity of the Gaussian multiple access channel with feedback," 47th Annual Allerton Conference on Communication, Control, and Computing, 2009 [here]