Main

Biography

Teaching

Publications

Lav R. Varshney - Research

Research Interests

• information and coding theory
• data analytics
• statistical signal processing
• systems theory
• neuroscience and neuroengineering
• history and social studies of engineering

Optimality Principles for Neural Systems

A key limitation of systems involving humans and machines is the neural information processing limitations of the humans themselves. My work in neuroscience has studied a variety of informational tasks, and adopting the optimization approach to biology, has put forth principles that provide theoretical explanations for experimentally observed phenomena. We put forth the principle that the synaptic microarchitecture of the mammalian brain optimizes memory capacity per unit volume. This hypothesis together with information-theoretic optimization led to predictions that explain why synapses are small and noisy on average, why synaptic strength distributions in the brain have a wide tail, why synaptic connectivity is sparse, and why synaptic strength may be discrete-valued: L. R. Varshney, P. J. Sjöström, and D. B. Chklovskii, "Optimal Information Storage in Noisy Synapses under Resource Constraints," Neuron, November 2006. After performing new experimental electron micrography that establishes the canonical connectome of the nematode C. elegans, as well as network-theoretic and circuit-theoretic characterization in: L. R. Varshney, B. L. Chen, E. Paniagua, D. H. Hall, and D. B. Chklovskii, "Structural Properties of the Caenorhabditis elegans Neuronal Network," PLoS Computational Biology, February 2011. we put forth the principle that neuronal network structure and noise provide the basic limits for behavioral speed. This hypothesis together with information-theoretic optimization led to explanations for the microsecond speed of C. elegans behavior: L. R. Varshney and D. Shah, "Informational Limits of Neural Circuits," in Proceedings of the Forty-Ninth Annual Allerton Conference on Communication, Control, and Computing, September 2011. It remains to test this information flow hypothesis in larger organisms. Perception of stimuli in the natural environment is critical for humans. We put forth the principle that human information processing is both matched to natural stimuli and optimized for perceptual fidelity under information flow constraints. This hypothesis together with information-theoretic optimization led to an explanation for the centuries old Weber-Fechner Law of logarithmic psychophysical scaling and its deviations: J. Z. Sun, G. I. Wang, V. K. Goyal, and L. R. Varshney, "A Framework for Bayesian Optimality of Psychophysical Laws," Journal of Mathematical Psychology, to appear. In studying neural information processing, we have also developed state-of-the-art data acquisition techniques for neuroengineering and neuroscience, which can increase signal and system measurement efficiencies significantly. Using finite rate of innovation sampling, we can very efficiently record neural spike trains for applications in neuroscience and neural prosthetics: L. Srinivasan, L. R. Varshney, and J. Kusuma, "Acquisition of Action Potentials with Ultra-Low Sampling Rates," in Proceedings of the 32nd Annual International Conference of the IEEE Engineering in Medicine and Biology Society, September 2010. Using compressive sensing acquisition and message-passing data processing, we can very efficiently determine retinal ganglion cell receptive fields and reconstruct connectomes: A. K. Fletcher, S. Rangan, L. R. Varshney, and A. Bhargava, "Neural Reconstruction with Approximate Message Passing (NeuRAMP)," in Proceedings of the Twenty-Fifth Annual Conference on Neural Information Processing Systems, December 2011. Message-passing is also how the brain itself is thought to operate, and so understanding the limits of noisy message-passing, as in: L. R. Varshney "Performance of LDPC Codes Under Faulty Iterative Decoding," IEEE Transactions on Information Theory, July 2011. will provide a mathematical basis for garnering further insights into the limits of neural circuits. Indeed, this work has already provided fundamental insight into the limits of processing unreliable information with unreliable circuits and design principles for systems with low-power, nanoscale technological circuits. There is also biomimetic value in studying neuronal systems: L. R. Varshney "The Wiring Economy Principle for Designing Inference Networks," IEEE Journal on Selected Areas in Communications, to appear.

Drawing and Prioritizing Human Attention

Beyond neurobiological limitations, however, another key limitation of humans is their attention and participation. We have found involuntary attention can be driven by novelty and surprise, whereas voluntary attention can be driven by a mix of extrinsic and intrinsic motivations. Often, data analytics technologies can help people figure out what it is that matters and prioritize their attention. We have built a computational creativity system that automatically produces novel and high-quality artifacts in a specific domain, briefly described in D. Bhattacharjya, L. R. Varshney, F. Pinel, and Y.-M. Chee, "Computational Creativity: A Two-attribute Search Technique," presented at INFORMS Annual Meeting, October 2012. but primarily unpublished as yet. Remarkably, we have found that optimizing novelty through a formal information-theoretic surprise metric is effective in drawing human attention. When trying to communicate in the information overload regime, this notion of surprise can be balanced against information transmission rate. When considering voluntary attention for knowledge work, we have found a mix of intrinsic, extrinsic, and social factors are the key for getting participation in crowd systems such as IBM's internal Liquid platform: L. R. Varshney, "Participation in Crowd Systems," in Proceedings of the Fiftieth Annual Allerton Conference on Communication, Control, and Computing, October 2012. E. H. Bokelberg and L. R. Varshney, "Liquid: Harnessing the Passion of the Crowd within the Enterprise," submitted. The challenge of doing interesting work is often a greater motivator than financial reward. In an attention economy, people often stop listening to data/information transmitted over a noisy channel after a certain amount of time. To model this setting, we introduced an information-theoretic problem where a unique informational quantity, information volume under fixed reliability, arises. An exact characterization of the optimal value of this quantity stems from a dynamic programming procedure: L. R. Varshney, S. K. Mitter, and V. K. Goyal, "An Information-Theoretic Characterization of Channels That Die," IEEE Transactions on Information Theory, September 2012. In my recent technical work at IBM, I have been developing data analytics tools that help people figure out what it is that matters and prioritize their actions. Application areas include information retrieval, human resource management, and child welfare protection. By building a predictor for the severity of a reported child abuse case, and further using queuing-theoretic ideas when classification is noisy, we can prioritize cases to be investigated: R. Williams, W. M. Gifford, and L. R. Varshney, "Using Statistical Algorithms to Predict Abuse against Children and Prioritize Cases," presented at 18th National Conference on Child Abuse and Neglect, April 2012. A particularly interesting use of data analytics to prioritize human attention is as part of abandoned property prevention policy within cities, such as Syracuse, New York. The goal is to go from a reactive approach to a proactive one, by drawing attention to those parcels and neighborhoods that are on the tipping point of vacancy, rather than those that are in the worst shape: D. Botti, J. Jamison, L. Plant, J. Shyr, and L. Varshney, IBM’s Smarter Cities Challenge Syracuse Report, IBM Corporation, November 2011. Moving beyond the practical matter of developing good data analytics tools for particular applications, I am currently studying the fundamental limits of data analytics in larger systems involving humans and machines, using complexity results from machine learning and the theory of order statistics: L. R. Varshney, "Fundamental Limits of Data Analytics for Sequential Selection," to appear in Proceedings of the 2013 Information Theory and its Applications Workshop, February 2013.

Information Representation for a Purpose

A traditional approach to representing data and information is to keep as much as possible without specific regard for how it will be used. But thinking about the purpose of the data can significantly reduce the information burden for people and more efficiently use their cognitive energies and limited attention. Typically when data records are from transactions, scientific experiments, or sensor logs, the order does not matter and databases can be thought of as nonsequential signals. We showed that information capacity requirements for nonsequential sources scale only logarithmically with the number of records in several source coding regimes (low-rate/high-rate quantization, rate-distortion theory, lossy/lossless universal source coding), rather than linearly as for sequential sources: L. R. Varshney and V. K. Goyal, "Toward a Source Coding Theory for Sets," in Proceedings of the IEEE Data Compression Conference, March 2006. L. R. Varshney and V. K. Goyal, "On Universal Coding of Unordered Data," in Proceedings of the 2007 Information Theory and its Applications Workshop, February 2007. By understanding the nature and context of information, rather than blindly using traditional techniques, the fundamental scaling change from O(n) to O(log n) bits transforms the conversation of what is possible. Carrying forward the idea of data compression for a given purpose, we considered settings where the function of data to be computed from the compressed representation is fixed, but compression must be carried out in a distributed manner. Similar to the fundamental scaling change in the nonsequential setting, there can be an exponential rate improvement even in this distributed setting: V. Misra, V. K. Goyal, and L. R. Varshney, "Distributed Scalar Quantization for Computing: High-Resolution Analysis and Extensions," IEEE Transactions on Information Theory, August 2011. One major function of information is to enable knowledge work through interaction among different parties; knowledge work includes handling information and creativity. How might data for work be represented in systems for global service delivery? We have developed a framework called Work as a Service that encapsulates the minimal sufficient data needed to do knowledge work and to coordinate complex work engagements: D. V. Oppenheim, L. R. Varshney, and Y.-M. Chee, "Work as a Service," in Handbook on Web Services, A. Bouguettaya, Q. Z. Sheng, and F. Daniel (eds.), Springer, 2012, to appear. Several extensions of this framework for a variety of settings have been developed and the framework also forms the basis of a newly-deployed system for global service delivery used by more than 15000 practitioners around the world within IBM. When information is represented for both local purposes and for social exchange, an intriguing balance between focal and shared vocabularies must be struck: A. Mani, L. R. Varshney, and A. Pentland, "Focal Vocabularies vs. Shared Vocabularies in Social Networks: Balancing Individual Concerns and Social Exchange," presented at Interdisciplinary Workshop on Information and Decision in Social Networks, November 2012. Sometimes the cause of information overload is not new data but rather data from the past; it then makes sense to lift the weight of history and write over past data. When updating memory devices with new versions of information, old versions can be overwritten. Compressed representations where only a small number of symbols need be changed during updates improve memory performance, energy consumption, and endurance. We determined information-theoretic limits in two settings: random access editing for local storage and fixed segment replacement for distributed storage: L. R. Varshney, J. Kusuma, and V. K. Goyal, "Malleable Coding with Edit-Distance Cost," in Proceedings of the 2009 IEEE International Symposium on Information Theory, July 2009. J. Kusuma, L. R. Varshney, and V. K. Goyal, "Malleable Coding with Fixed Segment Reuse," in Proceedings of the 2011 IEEE International Symposium on Information Theory, August 2011. Providing the right information in the right representation to the right person at the right time will be key to success in the emerging data-abundant environment.

Collective Intelligence

When people come together to make decisions or to perform knowledge work, this is termed collective intelligence. Often collectives are able to perform better than individuals, but sometimes not. I have been interested in understanding how to optimize the structure of teams and platforms to yield improved information processing performance. Human decision makers have limited memory and therefore must think categorically. We studied how an individual would optimally operate under this form of bounded rationality: quantizing classes of decision problems into categories: K. R. Varshney and L. R. Varshney, "Quantization of Prior Probabilities for Hypothesis Testing," IEEE Transactions on Signal Processing, October 2008. This memory-limited decision-making framework led to an understanding of the troubling social phenomenon of racial discrimination in decision-making. Our analysis shows that models of limited memory combined with social cognition constraints yield discrimination as an optimal outcome and also suggests a reexamination of legal evidentiary standards: L. R. Varshney and K. R. Varshney, "Decision Making with Quantized Priors Leads to Discrimination," submitted. Categorical decision-making could explain racial discrimination, but approaching things from the other side we have shown that assembling a diverse team of decision-makers to vote to make a common decision can partially mitigate this effect: J. B. Rhim, L. R. Varshney, and V. K. Goyal, "Quantization of Prior Probabilities for Collaborative Distributed Hypothesis Testing." IEEE Transactions on Signal Processing, September 2012. J. B. Rhim, L. R. Varshney, and V. K. Goyal, "Distributed Decision Making by Categorically-Thinking Agents," in Decision Making with Imperfect Decision Makers, T. V. Guy, M. Karny, and D. H. Wolpert (eds.), Springer, 2012, to appear. Diversity is defined as having different categorizations, as might arise from different experience or training, and optimal quantizers are found. Even when there are disagreements on desired goals among groups of categorically-thinking decision-makers, a game-theoretic formulation of the group decision-making problem shows that diversity can help, though a bit less: J. B. Rhim, L. R. Varshney, and V. K. Goyal, "Conflict in Distributed Hypothesis Testing with Quantized Prior Probabilities," in Proceedings of the IEEE Data Compression Conference, March 2011. Collaborating with others that have different viewpoints leads to better decisions. Collaborative groups of specialized people can not only make better decisions, but also do better and more efficient information processing and knowledge work. Global service delivery not only introduces important data representation problems, but also the question of how to coordinate the doing of work by tens of thousands of specialized workers distributed around the world. Encapsulation of work into service requests facilitates this greatly: D. V. Oppenheim, L. R. Varshney, and Y.-M. Chee, "Work as a Service," in Handbook on Web Services, A. Bouguettaya, Q. Z. Sheng, and F. Daniel (eds.), Springer, 2012, to appear. We have developed and deployed within IBM a novel coordination algorithm based on a Markov decision process formulation for this knowledge work structure, which is able to handle stochastic perturbations that surely arise: L. R. Varshney and D. V. Oppenheim, "Coordinating Global Service Delivery in the Presence of Uncertainty," in Proceedings of the 12th International Research Symposium on Service Excellence in Management, June 2011. Another way to coordinate specialized workers is by allowing self-selection through crowdsourcing. Since managers may have limited time and attention to understand the abilities of individuals in a large global pool, it is often difficult for them to determine who is best for a given job. Crowdsourcing contests for macrotasks are able to not only find the best person for the job but also incentivize the best person to perform at his/her best: G. V. Ranade and L. R. Varshney, "To Crowdsource or not to Crowdsource?," in Proceedings of the 4th Human Computation Workshop, July 2012. We have also shown that crowd-workers typically put in more effort than is rational under complete information, but that this is explained by imperfect information: L. R. Varshney, J. B. Rhim, K. R. Varshney, and V. K. Goyal, "Categorical Decision Making by People, Committees, and Crowds," in Proceedings of the 2011 Information Theory and its Applications Workshop, February 2011. suggesting an information provision technique for indirectly controlling the crowd. By thinking of crowd workers as atomic particles, with varying degrees of motivation under the incentive structure present, we have considered a thermodynamic interpretation of empirical power-law participation rates in crowd systems such as IBM's Liquid and tied it to a micro-level generative model. With this thermodynamic view, we can start to understand the fundamental limits of crowd systems for doing knowledge work: L. R. Varshney, "Participation in Crowd Systems," in Proceedings of the Fiftieth Annual Allerton Conference on Communication, Control, and Computing, October 2012. Crowdsourcing microtasks using platforms such as Amazon Mechanical Turk introduce interesting questions of reliability and privacy: L. R. Varshney, "Privacy and Reliability in Crowdsourcing Service Delivery," in Proceedings of the 2012 SRII Global Conference, July 2012. Related questions of privacy also arise in the complicated environment of cross-enterprise collaboration, where several organizations may come together to do work at one point in time but may later be competitors: L. R. Varshney and D. V. Oppenheim, "On Cross-Enterprise Collaboration," in Proceedings of the 9th International Conference on Business Process Management, August 2011. We have only begun to scratch the surface of information, control, and signal processing problems in crowdsourcing, knowledge markets, and global collaboration.

Interaction between Humans and Machines

As we move forward and build large systems that involve humans and machines, especially in sophisticated sociotechnical systems such as cities and firms, it is important to understand what makes us tick and how we use tools to overcome our limitations in memory and information processing. Designing, building, and operating large-scale informational systems for people within firms for global service delivery and crowdsourcing, as well as for addressing property vacancy problems that impact the quality of life of all citizens in a city: S. Appel, D. Botti, J. Jamison, L. Plant, J. Y. Shyr, and L. R. Varshney, "Predictive Analytics can Facilitate Proactive Property Vacancy Policies for Cities," submitted. has provided insight into how people interact with machines, and indeed when they find value in engaging machines rather than seeing them as obstacles to productivity. I have found that given finite human memory, the explosion of scientific literature, and the near-constant availability of the internet, a Google effect has begun. Rather than remembering everything in the scientific literature internally, researchers are using the internet-enabled scientific literature as transactive memory and only remembering where information is to be found: L. R. Varshney, "The Google Effect in Doctoral Theses," Scientometrics, September 2012. This also holds for software developers with regard to asset reuse. The development of difficult mathematical arguments has similarly been enhanced by internet-enabled collaboration. In studying the Polymath Project, I found evidence of much more complicated argument structure than say the geometry proofs of Archimedes. Computer-mediated conversations, however, can take a variety of forms. L. R. Varshney, "Toward a Comparative Cognitive History: Archimedes and D. H. J. Polymath," in Proceedings of Collective Intelligence 2012, March 2012. L. R. Varshney, "“Directed Acyclic Motifs for Conversation Analytics," presented at Interdisciplinary Workshop on Information and Decision in Social Networks, November 2012. The use of technologies to enable cognition is not new. In studying the history of information theory, I found that block diagrams are important tools for harnessing visual perception for mathematical reasoning, as well as for defining closed deductive systems in the first place: L. R. Varshney, "Block Diagrams in Information Theory: Drawing Things Closed," in preparation. L. R. Varshney, "Engineering Theory and Mathematics in the Early Development of Information Theory," in Proceedings of the 2004 IEEE Conference on the History of Electronics, June 2004. With these and related phenomenological findings in hand, we can work to improve individual and collective intelligence in modern environments.

Last Updated October 2012, XHTML 1.0