The Complexity of Analytical Tasks: A Driving Force for Sensor Array Design
Authors: Knapp Adam , Johnson Kevin 
Published: May 2020

Introduction

Analytical tasks, the detection goals and scoping of quantitative measurements, are a foundational consideration for the design of chemical sensor arrays. Often sensor arrays are expected to support a variety of possible tasks which are only vaguely defined by both the end user and array designer. Nonetheless, the expedient choices made by or forced upon array designers and fabricators can significantly impact the analytical tasks that could be supported by an array. Analytical tasks may be defined as boundaries in an abstract space defining chemically and practically relevant quantities that are to be measured; chemical sensor and instrument responses may be defined in related spaces specific to their physics. Intelligently finding a mapping between these two abstract spaces defines our problem and informs the impact of analytical tasks upon sensor array design while avoiding the “black box” problems of popular machine learning approaches. This presentation details recent work at NRL that probes the meaning and impact of analytical tasks on chemical sensor array design through general, device agnostic figures of merit developed via techniques originating in statistical mechanics, information theory, information retrieval, and theoretical computer science.

Approaches

Multiple theoretical approaches are explored to determine and measure the impact of analytical task on chemical sensor array design. To begin, we use Ising model-like descriptions of binary sensor responses first described in a biological context by Murugan et. al. [1-3] and subsequently developed by us for chemical sensing with environmental interferents. Analytical tasks are then scoped as molecular and concentration identification against an unknown chemical background. On this framework, we explore the capabilities of a variety of approaches towards assessing the impact of analytical task on sensor array design.

The first set of approaches originate in information theory and we consider the mutual information and Kullback-Leibler divergences between different sensor array configurations considered over probability distributions defining the likelihood of that sensor array needing to perform different analytical tasks. Platform-agnostic figures of merit are derived and used to show the impact of analytical tasks on sensor array design.

Next, Van Riijsbergen and Melucci [4,5] have developed and elaborated upon an approach to representing and searching information in Hilbert spaces using operator theoretic methods reminiscent to those used in quantum mechanical calculations. By transferring our probabilistic sensor array models to a Hilbert space, we are able to perform similar searches against sensor arrays and by operator methods to ask logical questions of the sensor array using operators that encode analytical tasks and specific exigencies like comparisons to the effectiveness of the array for other analytical tasks.

Finally, Almagor et. al. [6-9] have recently developed a finite state machine approach for formally describing the complexity of sensing tasks within formal languages. We attempt to map our binary chemical sensor array model to this methodology and to describe the formal complexity of this toy model for chemical sensing. Analytical tasks are input as restrictions on available formal words in the finite state language.

Conclusions

Using a simple statistical mechanical model for a chemical sensor array with background interferents, we have been able to probe multiple approaches to quantifying the impact of analytical tasks on the design and relevance of a sensor array for a set of chemical detection problems. Importantly, these approaches avoid drawbacks associated with more empirical, machine learning-based approaches, enabling a more clear understanding of the chemical landscape and how chemical sensor array design interacts with it. Our investigation has explored ways to construct figures of merit for specific families of analytical tasks using methodologies as diverse as information theory, Hilbert space search methods, and complexity techniques for automata-defined sensing.

References

[1] M. H. Huntley, A. Murugan, M. P. Brenner, Information Capacity of Specific Interactions Proceedings of the National Academy of Sciences 113, 5841-5846 (2016); doi:10.1073/pnas.1520969113

[2] D. Zwicker, A. Murugan, M. P. Brenner, Receptor Arrays Optimized for Natural Odor Statistics Proceedings of the National Academy of Sciences 113, 5570-5575 (2016); doi:10.1073/pnas.1600357113

[3] A. Murugan, Z. Zeravcic, M. P. Brenner, S. Leibler, Multifarious Assembly Mixtures: Systems Allowing Retrieval of Diverse Stored Structures Proceedings of the National Academy of Sciences 112, 54-59 (2015); doi:10.1073/pnas.1413941112

[4] C. J. van Rijsbergen. The Geometry of Information Retrieval. Cambridge University Press. New York. (2004); doi: 10.1017/CBO9780511543333

[5] M. Melucci, Introduction to Information Retrieval and Quantum Mechanics. Springer-Verlag Berlin Heidelberg. New York. (2015); doi: 10.1007/978-3-662-48313-8

[6] S. Almagor, D. Kuperberg, O. Kupferman, Sensing as a Complexity Measure International Journal of Foundations of Computer Science, 30, 831-873 (2019); doi: 10.1142/S0129054119400203

[7] S. Almagor, D. Kuperberg, O. Kupferman, Sensing as a Complexity Measure International Conference on Descriptional Complexity of Formal Systems: DCFS 2017 Springer-Verlag Berlin Heidelberg. New York. (2017); doi: 10.1007/978-3-319-60252-3_1

[8] S. Almagor, D. Kuperberg, O. Kupferman Regular Sensing

[9] S. Almagor, D. Kuperberg, O. Kupferman The sensing cost of monitoring and synthesis FSTTCS. New York. (2015); doi: 10.4230/LIPIcs.FSTTCS.2015.380