Data Science Asked on December 24, 2021
I have a question regarding exercise 14.17 in An Introduction to Information Retrieval by Manning et al.
The problem is:
“Assuming two classes, show that the percentage of non-separable
assignments of the vertices of a hypercube decreases with
dimensionality M for M > 1. For example, for M = 1 the proportion of
non-separable assignments is 0, for M = 2, it is 2/16. Solve the
exercise either analytically or by simulation.”
The total number of assignments of vertices of an N-dimensional hypercube is: $2^{(2^N)}$
And as I found in here the number of separable assignments is O($2^{(N^2)}$).
So the percentage of non-separable assignments is increasing with N (which is the opposite of what is said in the exercise).
What am I missing here?
You appear to be correct. I believe this is a simple proof of the opposite fact:
Let $s(n)$ denote the number of separable sets in the $n$-cube. Let $Q_0, Q_1$ denote the subcubes of one smaller dimension, with say last coordinates equal to 0, 1 respectively. The key fact is that any separable set of the whole cube intersects with each of $Q_0, Q_1$ in separable sets. (The separating hyperplane intersects the codimension-1 spaces to form separating hyperplanes.) So $$s(n)leq [s(n-1)]^2.$$
Now the proportion $r(n)$ satisfies $$r(n)= frac{s(n)}{2^{2^n}}leq frac{[s(n-1)]^2}{(2^{2^{n-1}})^2}= [r(n-1)]^2< r(n-1),$$ where the last inequality holds because $r(n-1)<1$ for $n>2$.
Answered by Ben Reiniger on December 24, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP