Learning Structured Distributions: Power-Law and Low-Rank

Utilizing the structure of a probabilistic model can significantlyincrease its compression efficiency and learning speed. We considerthese potential improvements under two naturally-omnipresentstructures.Power-Law: English words and many other natural phenomena arewell-known to follow a power-law distribution. Yet this ubiquitousstructure has never been shown to help compress or predict thesephenomena. It is known that the class of unrestricted distributionsover alphabet of size k and blocks of length n can never becompressed with diminishing per-symbol redundancy, when k>n. Weshow that under power-law structure, in expectation we can compresswith diminishing per-symbol redundancy for k growing as large assub-exponential in n.For learning a power-law distribution, we rigorously explain theefficacy of the absolute-discount estimator using less pessimisticnotions. We show that (1) it is adaptive to an effectivedimension and (2) it is stronglyrelated to the Good--Turing estimator and inherits itscompetitive properties.Low-Rank: We study learning low-rank conditional probabilitymatrices under expected KL-risk. This choice accentuates smoothing,the careful handling of low-probability elements. We define a lossfunction, determine sample-complexity bound for its global minimizer,and show that this bound is optimal up to logarithmic terms. Wepropose an iterative algorithm that extends classical non-negativematrix factorization to naturally incorporate additive smoothing andprove that it converges to the stationary points of our loss function.Power-Law and Low-Rank: We consider learning distributions inthe presence of both low-rank and power-law structures. We studyKneser-Ney smoothing, a successful estimator for the N-gram languagemodels through the lens of competitive distribution estimation. Wefirst establish some competitive properties for the contextualprobability estimation problem. This leads to Partial Low Rank,a powerful generalization of Kneser-Ney that we conjecture to haveeven stronger competitive properties. Empirically, it significantlyimproves the performance on language modeling, even matching thefeed-forward neural models, and gives similar gains on the task ofpredicting attack types for the Global Terrorism Database