Concentration Bounds for Unigram Language Models
Natural language processing (NLP) has developed rapidly over the las t decades. It has a wide range of applications, including speech recognition, optical character recogn iti n, text categorization and many more. The theoretical analysis has also advanced significantly, thoug h many fundamental questions remain unanswered. One clear challenge, both practical and th eoretical, concerns deriving stochastic models for natural languages. Consider a simple language model, where the distribution of each word in the tex t is assumed to be independent. Even for such a simplistic model, fundamental questions rela ting s mple size to the learning accuracy are already challenging. This is mainly due to the fact that the sample size is almost always insufficient, regardless of how large it is. To demonstrate this phenomena, consider the following example. We would like to estimate the distribution of first names in the university. For that, we are given the na mes list of a graduate seminar: Alice, Bob, Charlie, Dan, Eve, Frank, two Georges, and two He nries. How can we use this sample to estimate the distribution of students’ first names? An empirical frequen cy estimator would