×

Distributed parametric and nonparametric regression with on-line performance bounds computation. (English) Zbl 1271.93151

Summary: In this paper we focus on collaborative multi-agent systems, where agents are distributed over a region of interest and collaborate to achieve a common estimation goal. In particular, we introduce two consensus-based distributed linear estimators. The first one is designed for a Bayesian scenario, where an unknown common finite-dimensional parameter vector has to be reconstructed, while the second one regards the nonparametric reconstruction of an unknown function sampled at different locations by the sensors. Both of the algorithms are characterized in terms of the trade-off between estimation performance, communication, computation and memory complexity. In the finite-dimensional setting, we derive mild sufficient conditions which ensure that a distributed estimator performs better than the local optimal ones in terms of estimation error variance. In the nonparametric setting, we introduce an on-line algorithm that allows the agents to simultaneously compute the function estimate with small computational, communication and data storage efforts, as well as to quantify its distance from the centralized estimate given by a Regularization Network, one of the most powerful regularized kernel methods. These results are obtained by deriving bounds on the estimation error that provide insights on how the uncertainty inherent in a sensor network, such as imperfect knowledge on the number of agents and the measurement models used by the sensors, can degrade the performance of the estimation process. Numerical experiments are included to support the theoretical findings.

MSC:

93E10 Estimation and detection in stochastic control theory
93A14 Decentralized systems
68T42 Agent technology and artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Akyildiz, I.; Su, W.; Sankarasubramaniam, Y.; Cayirci, E., A survey on sensor networks, IEEE Communications Magazine, 40, 8, 102-114 (2002)
[2] Anderson, B. D.O.; Moore, J. B., Optimal filtering (1979), Prentice-Hall · Zbl 0758.93070
[3] Aronszajn, N., Theory of reproducing kernels, Transactions of the American Mathematical Society, 68, 337-404 (1950) · Zbl 0037.20701
[4] Bertsekas, D.; Tsitsiklis, J., Parallel and distributed computation: numerical methods (1997), Athena Scientific: Athena Scientific Belmont, MA
[5] Blum, R.; Kassam, S.; Poor, H. V., Distributed detection with multiple sensors II: advanced topics, Proceedings of the IEEE, 85, January, 64-79 (1997)
[6] Boyd, S.; Ghosh, A.; Prabhakar, B.; Shah, D., Randomized gossip algorithms, IEEE Transactions on Information Theory/ACM Transactions on Networking, 52, 6, 2508-2530 (2006) · Zbl 1283.94005
[7] Choi, J.; Oh, S.; Horowitz, R., Distributed learning and cooperative control for multi-agent systems, Automatica, 45, 12, 2802-2814 (2009) · Zbl 1192.93011
[8] Cortés, J., Distributed kriged kalman filter for spatial estimation, IEEE Transactions on Automatic Control, 54, 12, 2816-2827 (2009) · Zbl 1367.93640
[9] Cortés, J., Distributed algorithms for reaching consensus on general functions, Automatica, 44, 3, 726-737 (2008) · Zbl 1283.93016
[10] Cucker, F.; Smale, S., On the mathematical foundations of learning, Bulletin of the American Mathematical Society, 39 (2001)
[11] Delouille, V., Neelamani, R., & Baraniuk, R. (2004). Robust distributed estimation in sensor networks using the embedded polygons algorithm. In Proceedings of the 3rd international symposium on information processing in sensor networks; Delouille, V., Neelamani, R., & Baraniuk, R. (2004). Robust distributed estimation in sensor networks using the embedded polygons algorithm. In Proceedings of the 3rd international symposium on information processing in sensor networks · Zbl 1373.94563
[12] Evgeniou, T.; Pontil, M.; Poggio, T., Regularization networks and support vector machines, Advances in Computational Mathematics, 13, 1, 1-50 (2000) · Zbl 0939.68098
[13] Fagnani, F.; Zampieri, S., Randomized consensus algorithms over large scale networks, IEEE Journal on Selected Areas in Communications, 26, 4, 634-649 (2008)
[14] Garin, F.; Schenato, L., A survey on distributed estimation and control applications using linear consensus algorithms, (Networked control systems. Networked control systems, Springer lecture notes in control and information sciences (2011), Springer), 75-107, (chapter) · Zbl 1216.93097
[15] Gilks, W. R.; Richardson, S.; Spiegelhalter, D. J., Markov chain Monte Carlo in practice (1996), Chapman and Hall: Chapman and Hall London · Zbl 0832.00018
[16] Girosi, F.; Jones, M.; Poggio, T., Regularization theory and neural networks architecture, Neural Computation, 7, 219-269 (1995)
[17] Guestrin, C., Bodik, P., Thibaux, R., Paskin, M., & Madden, S. (2004). Distributed regression: an efficient framework for modeling sensor network data. In Proceedings of the third international symposium on information processing in sensor networks (IPSN); Guestrin, C., Bodik, P., Thibaux, R., Paskin, M., & Madden, S. (2004). Distributed regression: an efficient framework for modeling sensor network data. In Proceedings of the third international symposium on information processing in sensor networks (IPSN)
[18] Hastie, T.; Tibshirani, R.; Friedman, J., The elements of statistical learning (2001), Springer: Springer New York
[19] Honeine, P., Essoloh, M., Richard, C., & Snoussi, H. (2008). Distributed regression in sensor networks with a reduced-order kernel model. In IEEE global telecommunications conference; Honeine, P., Essoloh, M., Richard, C., & Snoussi, H. (2008). Distributed regression in sensor networks with a reduced-order kernel model. In IEEE global telecommunications conference
[20] Ihler, A. (2005). Inference in sensor networks: graphical models and particle methods. Ph.D. dissertation; Ihler, A. (2005). Inference in sensor networks: graphical models and particle methods. Ph.D. dissertation
[21] Kay, S. M., Fundamentals of statistical signal processing: estimation theory (1993), Prentice-Hall, Inc.: Prentice-Hall, Inc. Upper Saddle River, NJ, USA · Zbl 0803.62002
[22] Li, L.; Chambers, J. A.; Lopes, C. G.; Sayed, A. H., Distributed estimation over an adaptive incremental network based on the affine projection algorithm, IEEE Transactions on Signal Processing, 58, 1, 151-164 (2010) · Zbl 1392.94300
[23] Mateos, G.; Bazerque, J. A.; Giannakis, G. B., Distributed sparse linear regression, IEEE Transactions on Signal Processing, 58, 10, 5262-5276 (2010) · Zbl 1391.62133
[24] Micchelli, C. A.; Pontil, M., Learning the kernel function via regularization, Journal of Machine Learning Research, 6, 1099-1125 (2005) · Zbl 1222.68265
[25] Micchelli, C.; Xu, Y.; Zhang, H., Universal Kernels, Journal of Machine Learning Research, 7, 2651-2667 (2006) · Zbl 1222.68266
[26] Nef, W., Linear algebra (1967), McGraw-Hill · Zbl 0178.03001
[27] Martínez, S., Distributed interpolation schemes for field estimation by mobile sensor networks, IEEE Transactions on Control Systems Technology, 18, 491-500 (2010)
[28] Nicolao, G. D.; Ferrari-Trecate, G., Consistent identification of NARX models via regularization networks, IEEE Transactions on Automatic Control, 44, 11, 2045-2049 (1999) · Zbl 1136.93454
[29] Olfati-Saber, R.; Murray, R. M., Consensus problems in networks of agents with switching topology and time-delays, IEEE Transactions on Automatic Control, 49, 9, 1520-1533 (2004) · Zbl 1365.93301
[30] Oliveira, R. I., Sums of random Hermitian matrices and an inequality by Rudelson, Electronic Communications in Probability, 15, 203-212 (2010) · Zbl 1228.60017
[31] Pérez-Cruz, F.; Kulkarni, S. R., Robust and low complexity distributed kernel least squares learning in sensor networks, IEEE Signal Processing Letters, 17, 4 (2010)
[32] Pillonetto, G.; Bell, B. M., Bayes and empirical Bayes semi-blind deconvolution using eigenfunctions of a prior covariance, Automatica, 43, 10, 1698-1712 (2007) · Zbl 1119.93064
[33] Poggio, T.; Girosi, F., Networks for approximation and learning, Proceedings of the IEEE, 78, 9 (1990) · Zbl 1226.92005
[34] Poor, H.V. (2009). Competition and collaboration in wireless sensor networks. In Sensor networksSignals and communication technology; Poor, H.V. (2009). Competition and collaboration in wireless sensor networks. In Sensor networksSignals and communication technology
[35] Predd, J. B.; Kulkarni, S. R.; Poor, H. V., Distributed learning in wireless sensor networks, IEEE Signal Processing Magazine, 23, 4, 56-69 (2006)
[36] Predd, J. B.; Kulkarni, S. R.; Poor, H. V., A collaborative training algorithm for distributed learning, IEEE Transactions on Information Theory, 55, 4 (2009) · Zbl 1368.68285
[37] Predd, J. B.; Kulkarni, S. R.; Poor, H. V., Regression in sensor networks: training distributively with alternating projections, Advanced Signal Processing Algorithms, Architectures, and Implementations XV, 5910, 1 (2005)
[38] Puccinelli, D.; Haenggi, M., Wireless sensor networks: applications and challenges of ubiquitous sensing, IEEE Circuits and Systems Magazine, 5, 3 (2005)
[39] Rasmussen, C. E.; Williams, C. K.I., Gaussian processes for machine learning (2006), The MIT Press · Zbl 1177.68165
[40] Schölkopf, B.; Smola, A., Learning with kernels: support vector machines, regularization, optimization, and beyond (2001), MIT Press: MIT Press Cambridge, MA, USA
[41] Schizas, I.D., & Giannakis, G.B. (2006). Consensus-based distributed estimation of random signals with wireless sensor networks. In 40th Asilomar conference on signals, systems and computers; Schizas, I.D., & Giannakis, G.B. (2006). Consensus-based distributed estimation of random signals with wireless sensor networks. In 40th Asilomar conference on signals, systems and computers
[42] Schizas, I. D.; Ribeiro, A.; Giannakis, G. B., Consensus in ad hoc WSNs with noisy links — part i: distributed estimation of deterministic signals, IEEE Transactions on Signal Processing, 56, 1, 350-364 (2008) · Zbl 1390.94395
[43] Smale, S.; Zhou, D.-X., Learning theory estimates via integral operators and their approximations, Constructive Approximation, 26, 153-172 (2007) · Zbl 1127.68088
[44] Smale, S.; Zhou, D.-X., Shannon sampling II: connections to learning theory, Applied and Computational Harmonic Analysis, 19, 285-302 (2005) · Zbl 1107.94008
[45] Tikhonov, A. N.; Arsenin, V. Y., Solution of ill-posed problems (1977), Wiston · Zbl 0354.65028
[46] Vapnik, V. N., The nature of statistical learning theory (1995), Springer: Springer New York · Zbl 0934.62009
[47] Varagnolo, D., Pillonetto, G., & Schenato, L. (2009). Distributed function and time delay estimation using nonparametric techniques. In IEEE conference on decision and control; Varagnolo, D., Pillonetto, G., & Schenato, L. (2009). Distributed function and time delay estimation using nonparametric techniques. In IEEE conference on decision and control
[48] Varagnolo, D., Pillonetto, G., & Schenato, L. (2010). Distributed consensus-based Bayesian estimation: sufficient conditions for performance characterization. In American control conference; Varagnolo, D., Pillonetto, G., & Schenato, L. (2010). Distributed consensus-based Bayesian estimation: sufficient conditions for performance characterization. In American control conference
[49] Varshney, P. K., Distributed detection and data fusion (1996), Springer-Verlag New York, Inc.: Springer-Verlag New York, Inc. Secaucus, NJ, USA
[50] Viswanathan, R.; Varshney, P. K., Distributed detection with multiple sensors I: fundamentals, Proceedings of the IEEE, 85, 54-63 (1997)
[51] Wahba, G., Spline models for observational data (1990), SIAM · Zbl 0813.62001
[52] Xiao, J.-J.; Ribeiro, A.; Luo, Z.-Q.; Giannakis, G., Distributed compression-estimation using wireless sensor networks, IEEE Signal Processing Magazine, 23, 4, 27-41 (2006)
[53] Xu, Y.; Choi, J.; Oh, S., Mobile sensor network navigation using gaussian processes with truncated observations, IEEE Transactions on Robotics, 27, 6, 1118-1131 (2011)
[54] Yamanishi, K., Distributed cooperative Bayesian learning strategies, (COLT’97: proceedings of the tenth annual conference on computational learning theory (1997), ACM: ACM New York, NY, USA), 250-262
[55] Yosida, K., Functional analysis, vol. 123 (1965), Springer-Verlag · Zbl 0126.11504
[56] Zheng, H., Kulkarni, S.R., & Poor, H.V. (2008). Dimensionally distributed learning models and algorithm. In 11th international conference on information fusion; Zheng, H., Kulkarni, S.R., & Poor, H.V. (2008). Dimensionally distributed learning models and algorithm. In 11th international conference on information fusion
[57] Zhu, H.; Williams, C. K.I.; Rohwer, R.; Morciniec, M., (Gaussian regression and optimal finite dimensional linear models. Gaussian regression and optimal finite dimensional linear models, Neural networks and machine learning (1998), Springer-Verlag)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.