Combinatorics in ML: Counting Points with co-ordinates from among a set.

manpreet Best Answer 3 years ago

I'm trying to re-prove a theorem in the book Understanding Machine Learning: From Theory to Algorithms by Shalev-Schwartz et. al to aid my understanding of the material. The proof in the book derives a crude bound, and I'd like to derive a tighter one by counting the relevant quantities.

General Version of Problem:

Given a finite domain XX of size MM, I'd like to consider points in the nn-fold product of X; these points have n-coordinates, each an element of X. There are a total of MnMn such points.

Now, I'd like to partition these points into nn sets. The first set, S1S1, will contain all points that contain exactly 1 unique element of XX among its co-ordinates. The second set, S2S2, will contain all points that contain exactly two unique elements, and so on.

I would like to determine |Si||Si| for 1≤i≤n1≤i≤n.

|S1|=M|S1|=M, since, there are exactly MM points with one unique member of XX among their co-ordinates. Similarly, |