VC bounds on the cardinality of nearly orthogonal function classes

详细信息	查看全文 | 推荐本文 |

• 作者：Lee-Ad Gottlieb^a ; ^{lee-ad.gottlieb@weizmann.ac.il} ; Aryeh Kontorovich^b ; ^{karyeh@cs.bgu.ac.il} ; Elchanan Mossel^a ; ^c ; ^{mossel@stat.berkeley.edu}
• 关键词：VC dimension ; Packing number ; Orthogonal
• 刊名：Discrete Mathematics
• 出版年：2012
• 期刊代码：47_0012365x
• 类别：cp
• 出版时间：28 May, 2012
• 卷：312
• 期：10
• 页码：1766-1775
• 文件大小：386 K

摘要

We bound the number of nearly orthogonal vectors with fixed VC-dimension over . Our bounds are of interest in machine learning and empirical process theory and improve previous bounds by Haussler. The bounds are based on a simple projection argument and they generalize to other product spaces. Along the way we derive tight bounds on the sum of binomial coefficients in terms of the entropy function.