A type or type class is basically an empirical distribution for a sequence of n independent events. For instance, suppose we flip coin n=2 times. We have 3 type classes, all heads, all tails, one head/one tail. Size of the type class is the number of sequences in that class. Here, two of our classes have size 1 and "one head/one tail" has size 2.

Since the number of types grows polynomially with n, while number of observation sequences grows exponentially, some type classes end up getting an exponential number of sequences. Since constants of exponential growth are different for different types, probability mass ends up getting concentrated in a small number of types and several important properties follow from this concentration behavior.

In particular, Thomas/Cover use method of types to formalize and prove the following statements in Chapter 12 of "Information Theory and Statistics" (1991).

- Probability of hypothesis E under distribution P is determined by the probability of closest member of E to P (Sanov's theorem)
- To test whether data x was generated by p or q, it's sufficient to only look at the ratio of probabilities of x under p and under q (Neyman-Pearson lemma)
- When data is generated by p or q and you are trying to tell which one it is from data, probability of making a mistake for an optimal classifier is bounded by exp(-n max(KL(p,q),KL(q,p)). A tighter bound is to use KL(x,p)=KL(x,q) where x is the "halfway point" between distributions (Chernoff's theorem)

Rodriguez says it outperforms BIC and AIC by orders of magnitude

- Thomas, Cover "Information Theory and Statistics"
- Csiszar, Shields Notes on Information Theory and Statistics

## 5 comments:

Excellent machine learning blog,thanks for sharing...

Seo Internship in Bangalore

Smo Internship in Bangalore

Digital Marketing Internship Program in Bangalore

I have read your blog its very attractive and impressive. I like it your blog.

rebranding your business

Faisalabad is one of the biggest cities in Pakistan and the hub of the textile industry. It is widely acknowledged as the Manchester of Pakistan due to its large industrial role. The quality of the fabrics produced in this city has no parallel. In fact, the fabric is something of a specialty of Faisalabad. Many people from all over the country flock to this city for a spot of cloth shopping. We aim to provide you all of the best of Faisalabad at our store.

Roaster Review

I really liked your blog article.Really thank you! Really Cool.

Machine Learning Online Training In Hyderabad

Post a Comment