nips nips2010 nips2010-126 nips2010-126-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Danny Bickson, Carlos Guestrin
Abstract: Heavy-tailed distributions naturally occur in many real life problems. Unfortunately, it is typically not possible to compute inference in closed-form in graphical models which involve such heavy-tailed distributions. In this work, we propose a novel simple linear graphical model for independent latent random variables, called linear characteristic model (LCM), defined in the characteristic function domain. Using stable distributions, a heavy-tailed family of distributions which is a generalization of Cauchy, L´ vy and Gaussian distrie butions, we show for the first time, how to compute both exact and approximate inference in such a linear multivariate graphical model. LCMs are not limited to stable distributions, in fact LCMs are always defined for any random variables (discrete, continuous or a mixture of both). We provide a realistic problem from the field of computer networks to demonstrate the applicability of our construction. Other potential application is iterative decoding of linear channels with non-Gaussian noise. 1
[1] PlanetLab Network Homepage http://www.planet-lab.org/.
[2] D. P. Bertsekas and J. N. Tsitsiklis. Parallel and Distributed Calculation. Numerical Methods. Prentice Hall, 1989.
[3] D. Bickson. Linear characteristic graphical models Matlab toolbox. Carnegie Mellon university. Available on http://www.cs.cmu.edu/∼bickson/stable/.
[4] D. Bickson. Gaussian Belief Propagation: Theory and Application. PhD thesis, The Hebrew University of Jerusalem, 2008.
[5] D. Bickson, D. Baron, A. T. Ihler, H. Avissar, and D. Dolev. Fault identification via non-parametric belief propagation. IEEE Tran. on Signal Processing, to appear, 2010.
[6] D. Bickson, O. Shental, P. H. Siegel, J. K. Wolf, and D. Dolev. Gaussian belief propagation based multiuser detection. In IEEE Int. Symp. on Inform. Theory (ISIT), Toronto, Canada, July 2008.
[7] M. Briers, A. Doucet, and S. S. Singh. Sequential auxiliary particle belief propagation. In International Conference on Information Fusion, pages 705–711, 2005. 8
[8] A. Chen, J. Cao, and T. Bu. Network tomography: Identifiability and fourier domain estimation. In INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE, pages 1875– 1883, May 2007.
[9] R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, 1990.
[10] M. Huang, A. Bavier, and L. Peterson. Planetflow: maintaining accountability for network services. SIGOPS Oper. Syst. Rev., (1):89–94, 2006.
[11] A. T. Ihler, E. Sudderth, W. Freeman, and A. Willsky. Efficient multiscale sampling from products of Gaussian mixtures. In Neural Information Processing Systems (NIPS), Dec. 2003.
[12] J. Johnson, D. Malioutov, and A. Willsky. Walk-Sum Interpretation and Analysis of Gaussian Belief Propagation. In Advances in Neural Information Processing Systems 18, pages 579–586, 2006.
[13] A. Lakhina, M. Crovella, and C. Diot. Diagnosing network-wide traffic anomalies. In SIGCOMM ’04: Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, number 4, pages 219–230, New York, NY, USA, October 2004.
[14] A. Lakhina, M. Crovella, and C. Diot. Mining anomalies using traffic feature distributions. In SIGCOMM ’05: Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, pages 217–228, New York, NY, USA, 2005. ACM.
[15] A. Lakhina, K. Papagiannaki, M. Crovella, C. Diot, E. D. Kolaczyk, and N. Taft. Structural analysis of network traffic flows. In SIGMETRICS ’04/Performance ’04: Proceedings of the joint international conference on Measurement and modeling of computer systems, number 1, pages 61–72, New York, NY, USA, June 2004.
[16] X. Li, F. Bian, M. Crovella, C. Diot, R. Govindan, G. Iannaccone, and A. Lakhina. Detection and identification of network anomalies using sketch subspaces. In IMC ’06: Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, pages 147–152, New York, NY, USA, 2006. ACM.
[17] H. Liu, J. Lafferty, and L. Wasserman. The nonparanormal: Semiparametric estimation of high dimensional undirected graphs. In Journal of Machine Learning Research, to appear., 2009.
[18] Y. Mao and F. R. Kschischang. On factor graphs and the Fourier transform. In IEEE Trans. Inform. Theory, volume 51, pages 1635–1649, August 2005.
[19] Y. Mao, F. R. Kschischang, and B. J. Frey. Convolutional factor graphs as probabilistic models. In UAI ’04: Proceedings of the 20th conference on Uncertainty in artificial intelligence, pages 374–381, Arlington, Virginia, United States, 2004. AUAI Press.
[20] R. J. Marks II. Handbook of Fourier Analysis and Its Applications. Oxford University Press, 2009.
[21] T. P. Minka. Expectation propagation for approximate Bayesian inference. In UAI ’01: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, pages 362–369, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc.
[22] R. B. Nelsen. An Introduction to Copulas. Springer Serias in Statistics, second edition, 2006.
[23] H. X. Nguyen and P. Thiran. Network loss inference with second order statistics of end-to-end flows. In IMC ’07: Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, pages 227–240, New York, NY, USA, 2007. ACM.
[24] J. P. Nolan. Bibliography on stable distributions, processes and related topics. Technical report, 2010.
[25] J. P. Nolan. Stable Distributions - Models for Heavy Tailed Data. Birkh¨ user, Boston, 2010. In progress, a Chapter 1 online at http://academic2.american.edu/∼jpnolan.
[26] J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Francisco, 1988.
[27] H. Shen, S. Jegelka, and A. Gretton. Fast kernel-based independent component analysis. Signal Processing, IEEE Transactions on, 57(9):3498–3511, May 2009.
[28] T. T. Soong. Fundamentals of Probability and Statistics for Engineers. Wiley, 2004.
[29] E. Sudderth, A. T. Ihler, W. Freeman, and A. Willsky. Nonparametric belief propagation. In Conference on Computer Vision and Pattern Recognition (CVPR), June 2003.
[30] V. V. Uchaikin and V. M. Zolotarev. Chance and stability. In Stable Distributions and their Applications. Utrecht, VSP, 1999.
[31] M. Veillette. Stable distribution Matlab package. Boston university. http://math.bu.edu/people/mveillet/. Available on
[32] A. Yener, R. Yates, and S. Ulukus. CDMA multiuser detection: A nonlinear programming approach. IEEE Tran. On Communications, 50(6):1016–1024, 2002. 9