nips nips2007 nips2007-87 nips2007-87-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Emre Kiciman, David Maltz, John C. Platt
Abstract: Web servers on the Internet need to maintain high reliability, but the cause of intermittent failures of web transactions is non-obvious. We use approximate Bayesian inference to diagnose problems with web services. This diagnosis problem is far larger than any previously attempted: it requires inference of 104 possible faults from 105 observations. Further, such inference must be performed in less than a second. Inference can be done at this speed by combining a mean-field variational approximation and the use of stochastic gradient descent to optimize a variational cost function. We use this fast inference to diagnose a time series of anomalous HTTP requests taken from a real web service. The inference is fast enough to analyze network logs with billions of entries in a matter of hours. 1
[1] M. Chen, A. X. Zheng, J. Lloyd, M. I. Jordan, and E. Brewer. Failure diagnosis using decision trees. In Proc. Int’l. Conf. Autonomic Computing, pages 36–43, 2004.
[2] D. Heckerman. A tractable inference algorithm for diagnosing multiple diseases. In Proc. UAI, pages 163–172, 1989.
[3] T. Jaakkola and M. Jordan. Variational probabilistic inference and the QMR-DT database. Journal of Artificial Intelligence Research, 10:291–322, 1999.
[4] M. I. Jordan, Z. Ghahramani, T. S. Jaakkola, and L. K. Saul. An introduction to variational methods for graphical models. Machine Learning, 37:183–233, 1999.
[5] H. J. Kushner and G. G. Yin. Stochastic Approximation and Recursive Algorithms and Applications. Springer-Verlag, 2003.
[6] T. P. Minka. Expectation propagation for approximate bayesian inference. In Proc. UAI, pages 362–369, 2001.
[7] Q. Morris. Recognition networks for approximate inference in BN20 networks. In Proc. UAI, pages 370–37, 2001.
[8] K. P. Murphy, Y. Weiss, and M. I. Jordan. Loopy belief propagation for approximate inference: An empirical study. In Proc. UAI, pages 467–475, 1999.
[9] A. Y. Ng and M. Jordan. Approximate inference algorithms for two-layer bayesian networks. In Proc. NIPS, pages 533–539, 1999.
[10] J. Nocedal and S. J. Wright. Numerical Optimization. Springer, 2nd edition, 2006.
[11] J. Pearl. Probabilistic Reasoning In Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 1988.
[12] I. Rish, M. Brodie, and S. Ma. Accuracy vs. efficiency tradeoffs in probabilistic diagnosis. In Proc. AAAI, pages 560–566, 2001.
[13] M. A. Shwe and G. F. Cooper. An empirical analysis of likelihood-weighting simulation on a large, multiply-connected medical belief network. Computers and Biomedical Research, 24(5):453–475, 1991.
[14] M. A. Shwe, B. Middleton, D. E. Heckerman, M. Henrion, E. J. Horvitz, H. P. Lehmann, and G. F. Cooper. Probabilistic diagnosis using a reformulation of the INTERNIST1/QMR knowledge base. Methods of Information in Medicine, 30(4):241–255, 1991.
[15] J. J. Shynk and S. Roy. The LMS algorithm with momentum updating. In Proc. Intl. Symp. Circuits and Systems, pages 2651–2654, 1988.
[16] M. Steinder and A. Sethi. End-to-end service failure diagnosis using belief networks. In Proc. Network Operations and Management Symposium, pages 375–390, 2002. 8