Large alphabet probability estimnation
Narayana Santhanam, Alon Orlitsky · 2007
We develop on priorresults onprobability estimation obtained inIll. We specialize theresults to uniformdistributions inordertoobtain sampling rules forsupport size estimation. We consider textclassification, andshowthattheestimators developed forprobability estimation canimprove current state ofthearttechniques. Theavailability ofunprecedented communication, computation, andstorage resources hasmadepossible complex systems suchastheInternet aswellashelped scientific advances liketheHumanGenomeProject. Parallely, tobetter utilize these advances andtofacilitate them, several newproblems havecometooccupy re- searchers' efforts. Routing, speech recognition, anddata mining arejustafewofmanysuchapplications that spring tomind. However, alotofworksofarinstatistics isasymptotic innature. Itassumes that weoperate inaregime where thedata size ismuchlarger than thealphabet size. Forthe large alphabet problems mentioned above, this isoften notthecase. We aretherefore forced torework topics whereconventional approaches nolonger apply.