研究背景：
统计学习理论的核心概念就是用VC维来描述学习机器的复杂度，并以VC维为出发点推导出了表示学习机器推广能力的界的概念。统计学习理论在不需要利用样本数趋于无穷大的渐进性条件的情况下致力于寻找在小样本情况下学习问题的最优解，这使得在小样本情况下统计学习理论同样具有良好的推广价值。
VC维：
指示函数集的VC维是指用来刻画指示函数集容量的系数h。如果指示函数集的生长函数以参数h的对数函数为界，则该指示函数的VC维等于h且是有限的；以线性函数为生长函数的指示函数集的VC维是无穷大。
VC维反映了学习机器复杂程度和函数集的学习能力。目前只知道一些特殊函数集的VC维，比如在n维实数空间中线性函数的VC维是n+1。关于计算任意函数集VC维的通用理论还没成型。比较复杂的学习机器的VC维就更不容易确定，因为VC维除了与函数集有关外，还受到学习算法的影响。如何计算给定的函数集的VC维是当前统计学习理论中一个有待解决的问题。
VC维越大，学习机器越复杂。VC维的大小，与学习算法无关，与输入变量X的分布无关，与我们求解的目标函数g无关，只与模型和假设空间有关。实践中有这样一个规律：假设空间的VC维与假设参数w的自由变量数且大约相等。即：
VC(H)=free parameters
换种说法，VC维度量了二元分类器的容量。定义该分类器能够分类的训练样本的最大数目。假设存在m个不同x点的训练集，分类器可以任意标记该m个不同的x点，VC维被定义为m的最大可能值。
多项式核函数（polynomial function）的VC维是：〖(n〗^2+3n+2)/2。
Problems:
第一问：k(x ?,y ? )=〖(x ?*y ?)〗^n
将公式转换为：
k〖(x_1 y_1+x_2 y_2+?+x_d y_d)〗^n=γ(x ?)γ(y ?)
利用多项式展开公式
〖(x_1 y_1+x_2 y_2+?+x_d y_d)〗^n=∑?〖n!/(n_1 !n_2 !…n_d !) 〖(x_1,y_1)〗^(n_1 ) 〖(x_2,y_2)〗^(n_2 )…〖(x_d,y_d)〗^(n_d ) 〗
求得γ函数为：
参考资料：
原文：https://www.cnblogs.com/xlwang1995/p/13285624.html