|
There's an old theorem by Cover on the number of linear dichotomies of a set of m points in "general position" in d-dimensional space. Does anyone know if there's been any variants of that which, say, require bounded norm of coefficients of the hyperplanes or require a minimum margin on the hyperplanes? Or, failing there being theorems, are there practical algorithms for estimating the number of bounded norm or minimum margin separated dichotomies for a particular data set one has at hand?
showing 5 of 6
show all
|
Just curious, do you have a reference for that theorem?
Here's the original reference:
Cover, T. M. (1965). "Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition," IEEE Trans. Elec. Comp., EC-14, 326-334.
It's discussed in various textbooks on machine learning, including
Massoud, M. H. Fundamentals of Artificial Neural Networks (MIT Press, 1995)
The relevant section is:
http://neuron.eng.wayne.edu/tarek/MITbook/chap1/1_3.html
Are you talking about VC dimension?
Yes and no. What I'm wondering (to jump ahead) is whether having a particular data set at hand can give you tighter bounds than VC dimension would.
@Dave Lewis : In that case, you should be looking at data dependent bounds such as Radamacher complexity.
@spinxl39 - Thanks, indeed Radamacher complexity is the kind of thing I was looking for. If you want to turn your comment into an answer, I'll accept it as the answer.