Posted on 16 Aug 2022, this text provides information on Learning Aids/Tools related to General Tech. Please note that while accuracy is prioritized, the data presented might not be entirely correct or up-to-date. This information is offered for general knowledge and informational purposes only, and should not be considered as a substitute for professional advice.
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, |
No matter what stage you're at in your education or career, TuteeHUB will help you reach the next level that
you're aiming for. Simply,Choose a subject/topic and get started in self-paced practice
sessions to improve your knowledge and scores.
manpreet
Best Answer
2 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, |
0
views
0
shares
Facebook
Twitter
Linked In
WhatsApp