Timezone: »

 
Poster
Near-Optimal Smoothing of Structured Conditional Probability Matrices
Moein Falahatgar · Mesrob Ohannessian · Alon Orlitsky

Mon Dec 05 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #172
in Monday Posters »

Utilizing the structure of a probabilistic model can significantly increase its learning speed. Motivated by several recent applications, in particular bigram models in language processing, we consider learning low-rank conditional probability matrices under expected KL-risk. This choice makes smoothing, that is the careful handling of low-probability elements, paramount. We derive an iterative algorithm that extends classical non-negative matrix factorization to naturally incorporate additive smoothing and prove that it converges to the stationary points of a penalized empirical risk. We then derive sample-complexity bounds for the global minimizer of the penalized risk and show that it is within a small factor of the optimal sample complexity. This framework generalizes to more sophisticated smoothing techniques, including absolute-discounting.

Keywords: (Other) Statistics · Learning Theory · Matrix Factorization · (Other) Machine Learning Topics · Structured Prediction · (Application) Natural Language and Text Processing
[ PDF] 

Author Information

Moein Falahatgar (UCSD)
Mesrob Ohannessian (University of Illinois at Chicago)
Alon Orlitsky (University of California, San Diego)

More from the Same Authors