We apply linear algebra (polynomial) techniques to various VC-Dimension based inequalities. We expore connections between the sample compression and this technique for so called maximum classes and prove that maximum classes are connected subgraphs of a Boolean cube. We provide a fast (linear in the cardinality of the class for the fixed VC- dimension) interpolational algorithm for maximum classes. A new method to bound a pseudo-dimension for a class of cell-wise constant functions is proposed.
展开▼
