Entry for the 2008 Humie award for Human Competitive Results
Title: Design of Distributed/Decentralized Detection Networks
(1) the complete title of one (or more) paper(s) published in the open
literature describing the work that the author claims describes a
human-competitive result
Paper title:
"Design of Distributed Detection Systems with Correlated Heterogeneous Sensors", Proceedings of 45th Allerton Conference on Communications, Control, and Computing, Allerton House, University of Illinois, September, 2007.
(2) the name, complete physical mailing address, e-mail address, and phone
number of EACH author of EACH paper,
Author 1:
-Name: Kalyan Veeramachaneni ,
-Address: Department of Electrical Engineering and Computer Science, Syracuse University, Syracuse, NY- 13244
-Email: kveerama@syr.edu
-Phone: (315) 443 3366
Author 2:
-Name: Lisa Osadciw
-Address: Department of Electrical Engineering and Computer Science, Syracuse University, Syracuse, NY, 13210, USA
-Email: laosadci@syr.edu
-Phone: 315 443 1319
(3) the name of the corresponding author (i.e., the author to whom notices
will be sent concerning the competition),
Kalyan Veeramachaneni & Lisa Osadciw
(4) the abstract of the paper(s),
Paper abstract:
The optimization of sensor decision thresholds and fusion rule for heterogeneous and correlated sensor suite is accomplished through a particle swarm optimization algorithm. Different correlation structures are assumed and the effect of correlation on the choice of final fusion rule and thresholds is analyzed. Optimal decision fusion for correlated sensors includes estimation of 2N joint probabilities for N sensors. Bahadur-Lazarfeld expansion is used to reduce the computational burden. Bahadur-lazarfeld expansion reduces the burden to evaluation of N-1 joint probabilities. Numerical integration is proposed to evaluate the joint probability. Examples using Gaussian distributions assumed under both the hypothesis are presented. The results achieved using a particle swarm optimization algorithm are compared to the traditional decision fusion strategies based on the fusion methodology developed by Moshe Kam et al.
(5) a list containing one or more of the eight letters (A, B, C, D, E, F, G,
or H) that correspond to the criteria (see above) that the author claims that
the work satisfies,
B, D, E and G
(6) a statement stating why the result satisfies the criteria that the
contestant claims (see the examples below as a guide to aid in constructing
this part of the submission),
Tenney and Sandell originally introduced decentralized detection in the 1980’s [1]. The main motivation for the research at that time was radar-based systems. The goal was to reduce the amount of data that needs to be transferred by the sensors before relaying it to the central processing node [1]. A framework was developed in which sensors divided their observation space (the real valued observation) into different regions and sent binary bits indicating which region the observation belonged to.
More recently, the decentralized detection has found applications in sensor networks and pattern recognition. Detection is often the primary goal of many sensor networks, and the subsequent functionalities of the network are based on the detection of the phenomena. For many applications, like biometrics and airport surveillance, detection is the only purpose of the sensor network. Other applications include detection of forest fires, detection of chemical, biological and nuclear agents, detecting faults on an aircraft engine and detecting cracks in pipelines and bridges.
A frequently used network topology is the parallel network topology. In a parallel network, each sensor applies threshold to its observations and gives decisions regarding the presence or absence of phenomena (i.e., the binary hypothesis). The decisions from multiple sensors are fused at the fusion processor producing a final decision. This type of network minimizes the communication bandwidth of a sensor network by transmitting a single bit, representing the decision, to the fusion center. Due to this thresholding of the information, accuracy is compromised for bandwidth. However, distributed detection system weighs each sensor’s decision based on the sensor’s performance characteristics. The sensor threshold and the fusion rule employed determine the weighting of a sensor’s observation. Hence, accuracy can be recovered if joint optimization of thresholds and fusion rule is accomplished.
The goal of the work is to achieve optimal thresholds for each sensors observation and the fusion rule such that the accuracy is maximized. Accuracy is defined using the estimates of probability of false alarms and probability of misses for a given design. Given the conditional density functions under each hypothesis for each sensor, these errors are estimated for a given set of thresholds and fusion rule. Both the errors are tied into a single cost function called the Bayesian risk. For equal costs for both the errors the Bayesian risk is known as probability of error. With the goal of minimizing this error, the optimal sensor thresholds and the optimal fusion rule is found using particle swarm optimization (PSO) algorithm.
The sensor thresholds are continuous valued and can have values ranging from -inf to inf. The fusion rule is a binary number determining the final decision for a given set of binary decisions. The fusion rule is 2^N bits long for 2 sensors. There are hence 2^2^N possible fusion rules. For example, there are 16 rules for 2 sensors, 256 for 3 sensors and approximately 1 million for 10 sensors.
Regaining accuracy is further complicated if the sensor observations are conditionally correlated and heterogeneous. In real world applications observations are correlated since the sensors are observing the same phenomena. For example, for face recognition sensors, the sensors observe the persons face and use different algorithms to come up with matching score. These scores (sensor observation) will be correlated.
The paper solves the problem for a correlated heterogeneous sensor suite. The PSO generated optimal thresholds and fusion rule achieved 71% higher accuracy when compared with the Moshe Kam optimal fusion rule method [4], for a correlation of rho= 0.1. Rho is varied from 0.1 to 0.9 (rho can vary from -1 to 1). The benefits were 54% for rho=0.3, 13% for 0.7 and 2.5% for 0.9 correlation. At 0.9 correlation, the information content among sensors is the same resulting in decline of performance. However, using our method we are still able to enhance the accuracy by 2.5%.
We present the following reasons for considering this evolutionary method as a best human competitive result.
(B) The result is equal to or better than a result that was accepted as a new
scientific result at the time when it was published in a peer-reviewed
scientific journal.
This entry deals with design of decision rules (thresholds) for sensors in a distributed detection network. A particle swarm optimization algorithm is used to achieve optimal thresholds for sensors and the optimal fusion rule. The results presented in the paper outperform the Moshe Kam optimal fusion rule used as a design method in this area. The result has been accepted at the 45th Allerton conference on control and communications. The conference focuses on improving the overall information quality of the multiple sensor data while minimizing the communication bandwidth. The result was well received and a journal article is underway.
(D) The result is publishable in its own right as a new scientific result -
independent of the fact that the result was mechanically created.
The design of sensor decision rules (thresholds) for correlated sensors has been published in Annual Allerton Conference on Communications and Control, 2007.
A second, much larger, paper is being submitted to one of the key sensor networks
Journal (ACM Transactions on Sensor Networks) showing that our evolutionary algorithm-based thresholding method produces better than current state of the art (whether human made or not) designs.
The work has been extended for correlated biometric classifiers and accepted for IEEE Computer Vision and Pattern Recognition Conference, 2008.
(E) The result is equal to or better than the most recent human-created
solution to a long-standing problem for which there has been a
succession of increasingly better human-created solutions.
Chair-Varshney in 1986 [3] designed optimal fusion rule for conditionally independent sensors, given that individual thresholds are fixed. This was a significant result, however, suboptimal. The thresholds of individual sensors were assumed to be fixed, determined using a likelihood ratio test at the sensor. This decoupled the problem into two separate problems, making the problem tractable, however, suboptimal. Moshe Kam et al. in 1992 [4] designed the optimal fusion rule for correlated sensor network given that the individual sensor thresholds were fixed. They followed the same methodology as Chair-Varshney in 1986.
Further, several suboptimal approaches were developed in 1990, 1991 [3] by employing certain conditions on the underlying problem structure. The conditions imposed on the problem were, homogeneity of sensors, strictly concave receiver-operating curve for individual sensors. The conditions employed made the problem mathematically tractable and necessary conditions were developed. A Gauss-Seidal iterative approach, isolating one variable at a time was employed to achieve a locally optimal solution.
We developed a PSO based approach to solve the problem for distributed detection network problem involving heterogeneous correlated sensors in our 2007 paper. Under these conditions, the human made design involved
a. Deriving individual threshold for each sensor using log likelihood ratio test
b. Applying Moshe Kam method to arrive at the optimal fusion rule
We compared this with the particle swarm based result presented in our paper. We achieved 54% more accuracy for 0.3 correlation and 34% more accuracy for 0.5 correlation.
(G) The result solves a problem of indisputable difficulty in its field.
The problem was originally formulated by Tenney et al. [1] for reduction of data size while fusing data from multiple radars. For the binary hypothesis problem, they concentrated on designing optimal likelihood ratio tests. They concluded that the solution to the local likelihood ratio tests become coupled in the case of distributed detection; solutions to these computations may be locally optimal but not globally optimal. They also presented that even in the most simplistic network, with conditionally identical detectors and symmetric cost functions, applying identical thresholds are not optimal.
Further, Tsitsiklis in [2] showed the non-optimality of identical decision rules for distributed detection systems with fusion. This has also led to the conclusion that computation of optimal local decision rules is intractable, especially when the number of local detectors becomes large. This is because the search over all non-identical decision rules is required. It has been shown in, by Tsitsiklis et al [2] that finding optimal decision rules for each individual sensor, as well as the corresponding optimal fusion rule is NP-complete. Subsequent to this conclusion by Tsitsiklis, the optimality became an elusive goal. Several methods have been proposed to solve this problem in literature. One can refer to the brief description of methods presented in the previous section and also in literature, given below [1 -6].
(7) a full citation of the paper (that is, author names; publication date;
name of journal, conference, technical report, thesis, book, or book chapter;
name of editors, if applicable, of the journal or edited book; publisher name;
publisher city; page numbers, if applicable);
1. R. Tenny, N. S. Sandell, "Detection with Distributed Sensors", IEEE Transactions on Aerospace and Electronis Systems, Vol. AES-17, No. 4, July 1981.
2. J. N. Tsitsiklis and M. Athans, " On Complexity of decentralized decision making and detection problems", IEEE Transactions on Automatic Control, vol. AC-30, pp.. 440-446, 1985.
3. Chair Z., P. K. Varshney, "Optimal Data Fusion in Multiple Sensor Detection Systems," IEEE Trans. on Aerospace and Elect. Systems, Vol. AES-22, No. 1, pp. 98-101, Jan. 1986.
4. Tang, Z. -B., K. R. Pattipati, and D. L. Kleinman, "An Algorithm for Determining the Decision Thresholds in a Distributed Detection Problem," IEEE Trans. on Systems, Man, and Cybernetics, Vol. SMC-21, pp. 231-237, Jan./Feb. 1991.
5. Kam., M., Q. Zhu., and W. S. Gray, "Optimal Data Fusion of Correlated Local Decisions in Multiple Sensor Detection Systems," IEEE Transactions on Aerospace and Elect. Syst., Vol. 28, pp. 916-920, July 1992.
6. Peter Willet, Peter F. Swaszek, Rick S. Blum, "The Good, Bad, and Ugly : Distributed Detection of Known Signal in Dependent Gaussian Noise," IEEE Transactions on Signal Processing, Vol. 48, No. 12, December 2000.
7. Kalyan Veeramachaneni, Lisa Osadciw, "Design of Distributed Detection Systems with Correlated Heterogeneous Sensors", 45th Annual Allerton Communications and Control Conference, September 26-28th, Allerton Park, Illinois, 2007.
8. Kalyan Veeramachaneni, Lisa Osadciw, Pramod Varshney, "Adaptive Multimodal Biometric Management Algorithm", IEEE Transactions on Systems, Man and Cybernetics, Vol. 35, 2005.
9. kalyan Veeramachaneni, Lisa Osadciw, Arun Ross, Nisha Srinivas, "Decision-Level Fusion Strategies for Correlated Biometric Classifiers", accepted IEEE Conference on Computer Vision and Pattern Recognition, Anchorage, Alaska, June 26-28, 2008.
(8) a statement either that "any prize money, if any, is to be divided equally
among the co-authors" OR a specific percentage breakdown as to how the prize
money, if any, is to be divided among the co-authors;
Any prize money, if any, is to be divided equally among the co-authors
(9) a statement stating why the judges should consider the entry as "best" in
comparison to other entries that may also be "human-competitive."
Design of sensor decision rules and design of fusion rule for a heterogeneous sensor network is a long-standing problem in the distributed detection and sensor network community. Researchers at first attempted to solve the problem by optimizing each individual sensor decision rule and then optimizing the fusion rule. Accuracy was compromised by individually optimizing sensor decision rules and the fusion rule. Further, researchers attempted to solve the problem by restricting the parameters of the conditional density functions. On these subset of problems necessary conditions were found and an iterative approach was employed to achieve a locally optimal solution. By restricting the parameters of the conditional density functions (i.e., making them conditionally independent and/or identical), only problems related to digital communications were solved, i.e., known signal in additive noise. Our method produces better results when compared to the human created solutions described above. Our method also solves problems that were not solved before, i.e. heterogeneous and correlated.
We think it should be considered best since this method solves significant sensor network problems currently needed by our society. Besides theoretical advancement, we have successfully employed our method to real world applications like biometrics [9] (a pdf file of the paper is attached)based verification systems, pipeline crack detection system (using ultrasound images from sensors) and have achieved higher performance using our method. Achieving higher accuracy in terms of probability of false alarms and probability of misses has significant impact on these applications. Higher false alarm rates come at a very high expense of unnecessary digs at remote locations costing thousands of dollars in case of the pipeline crack detection problem and at the same time higher miss rates can cause severe damages to the infrastructure. Similarly, higher false alarm rates are causing people to circumvent the biometrics system all together; eventually requiring security personnel to identify the humans and at the same time higher miss rates can cause havoc since an intruder is let into the system. With the omnipresence of pattern recognition and machine learning based systems around us, we believe our method will allow realization of some critical sensor networks and enhance the performance of some existing ones.