ML@GT will host Vincent Y.F. Tan from the National University of Singapore (NUS) for a virtual seminar on Wednesday, Feb. 10.
Learning Tree Models in Noise: Exact Asymptotics and Robust Algorithms
We consider the classical problem of learning tree-structured graphical models but with the twist that the observations are corrupted in independent noise. For the case in which the noise is identically distributed, we derive the exact asymptotics via the use of probabilistic tools from the theory of strong large deviations. Our results strictly improve those of Bresler and Karzand (2020) and Nikolakakis et al. (2019) and demonstrate keen agreement with experimental results for sample sizes as small as that in the hundreds. When the noise is non-identically distributed, Katiyar et al. (2020) showed that although the exact tree structure cannot be recovered, one can recover a "partial" tree structure; that is, one that belongs to the equivalence class containing the true tree. We propose Symmetrized Geometric Averaging (SGA), a statistically robust algorithm for partial tree recovery. We provide error exponent analyses and extensive numerical results on a variety of trees to show that the sample complexity of SGA is significantly better than the algorithm of Katiyar et al. (2020). SGA can be readily extended to Gaussian models and is shown via numerical experiments to be similarly superior.
This is joint work with Anshoo Tandon, Aldric J. Y. Han and Shiyao Zhu.
Vincent Y. F. Tan received the B.A. and M.Eng. degrees in electrical and information sciences from Cambridge University and the Ph.D. degree in electrical engineering and computer science (EECS) from the Massachusetts Institute of Technology (MIT).
He is currently a Dean’s Chair Associate Professor with the Department of Electrical and Computer Engineering and the Department of Mathematics, National University of Singapore (NUS). His research interests include information theory, machine learning, and statistical signal processing.
He was also an IEEE Information Theory Society Distinguished Lecturer in 2018/9. He is currently serving as an Associate Editor for the IEEE Transactions on Signal Processing and an Associate Editor for Machine Learning for the IEEE Transactions on Information Theory. He is a member of the IEEE Information Theory Society Board of Governors.