http://antkillerfarm.github.io/

H <script type="math/tex" id="MathJax-Element-2502">\mathcal{H}</script>为无限集的情况

某些预测函数的参数是实数，它实际上包含了无穷多个数。针对这样的情况，我们可以参照IEEE浮点数的规则，进行离散采样。

IEEE浮点数由64bit的二进制数构成，因此d个实数参数组成的 H <script type="math/tex" id="MathJax-Element-2503">\mathcal{H}</script>，可组成 k=264d <script type="math/tex" id="MathJax-Element-2504">k=2^{64d}</script>个不同的预测函数，因此：

<script type="math/tex; mode=display" id="MathJax-Element-2483">m\ge O\left(\frac{1}{\gamma^2}\log\frac{2^{64d}}{\delta}\right)=O\left(\frac{d}{\gamma^2}\log\frac{1}{\delta}\right)=O_{\gamma,\delta}(d)</script>

这里的下标 γ,δ <script type="math/tex" id="MathJax-Element-2484">\gamma,\delta</script>表示一些依赖于它们的常量。从上式可以看出需要的训练样本的数量和预测模型的参数个数成线性关系。

以上就是和ERM相关的算法的理论知识，至于其他非ERM算法理论仍在研究之中。

下面是 H <script type="math/tex" id="MathJax-Element-2485">\mathcal{H}</script>参数化的问题。一个线性分类器可以写为：

<script type="math/tex; mode=display" id="MathJax-Element-2472">h_\theta(x)=1\{\theta_0+\theta_1x_1+\dots+\theta_nx_n\ge 0\}</script>

这种形式有 n+1 <script type="math/tex" id="MathJax-Element-2473">n+1</script>个参数。

但它也可以写为：

<script type="math/tex; mode=display" id="MathJax-Element-2555">h_{u,v}(x)=1\{(u_0^2-v_0^2)+(u_0^2-v_0^2)x_1+\dots+(u_n^2-v_n^2)x_n\ge 0\}</script>

这种形式有 2n+2 <script type="math/tex" id="MathJax-Element-2556">2n+2</script>个参数。

显然这两种形式在数学上是等价的，但参数的个数却不同。为此我们引入Vapnik-Chervonenkis维度（简称VC维度），用以刻画参数的个数。

如上图所示，3个样本点有以上几种分布方式。毫无疑问，它们都能被 hθ(x)=1{θ0+θ1x1+θ2x2≥0} <script type="math/tex" id="MathJax-Element-2557">h_\theta(x)=1\{\theta_0+\theta_1x_1+\theta_2x_2\ge 0\}</script>所分割，且它们的训练误差为0。但如果是4个点的话，就不能无训练误差的分割了。我们将这种最大分割的个数称作VC维度，这里 VC(H)=3 <script type="math/tex" id="MathJax-Element-2558">VC(\mathcal{H})=3</script>。

需要注意的是，VC维度表征的是模型的最大切割能力，而不是针对所有的情况都成立。比如下图所示的三个点，就不可以被 hθ(x)=1{θ0+θ1x1+θ2x2≥0} <script type="math/tex" id="MathJax-Element-2559">h_\theta(x)=1\{\theta_0+\theta_1x_1+\theta_2x_2\ge 0\}</script>所分割，但这并不影响 hθ(x) <script type="math/tex" id="MathJax-Element-2560">h_\theta(x)</script>的VC维度值。

如果模型能切割任意大小的样本集，则 VC(H)=∞ <script type="math/tex" id="MathJax-Element-2561">VC(\mathcal{H})=\infty</script>。

我们将VC维度值替换 H <script type="math/tex" id="MathJax-Element-2562">\mathcal{H}</script>为有限集时的 ∣H∣ <script type="math/tex" id="MathJax-Element-2563">\lvert\mathcal{H}\rvert</script>，可得以下相关结论：

令 VC(H)=d <script type="math/tex" id="MathJax-Element-2564">VC(\mathcal{H})=d</script>，则：

<script type="math/tex; mode=display" id="MathJax-Element-19">\lvert\varepsilon(h)-\hat\varepsilon(h)\rvert\le O\left(\sqrt{\frac{d}{m}\log\frac{m}{d}+\frac{1}{m}\log\frac{1}{\delta}}\right)</script>

<script type="math/tex; mode=display" id="MathJax-Element-20">\varepsilon(\hat h)\le \varepsilon(h^*)+O\left(\sqrt{\frac{d}{m}\log\frac{m}{d}+\frac{1}{m}\log\frac{1}{\delta}}\right)</script>

<script type="math/tex; mode=display" id="MathJax-Element-2294">m=O_{\gamma,\delta}(d)</script>

以上公式的其他条件，与 H <script type="math/tex" id="MathJax-Element-2295">\mathcal{H}</script>为有限集时相同，这里不再赘述。

规则化和模型选择

对于多项回归模型

<script type="math/tex; mode=display" id="MathJax-Element-2289">h_\theta(x)=g(\theta_0+\theta_1x_1+\dots+\theta_kx_k)</script>来说，如何选择合适的k值呢？

或者，我们是选择局部权重回归（locally weighted regression），还是SVM呢？

我们定义算法模型的集合为 M={M1,…,Md} <script type="math/tex" id="MathJax-Element-2290">\mathcal{M}=\{M_1,\dots,M_d\}</script>。其中的 Mi <script type="math/tex" id="MathJax-Element-2291">M_i</script>为不同的算法模型，比如SVM、神经网络等等。

交叉验证

回想之前讨论的过拟合和ERM算法，如果我们针对多项回归模型使用ERM算法，几乎必然会选择高方差的高维多项回归模型，因为它的训练误差最小。但这显然不是个好选择。

因此，我们改进算法如下：

1.从全部的训练数据S中随机选择70%的样例作为训练集 Strain <script type="math/tex" id="MathJax-Element-2250">S_{train}</script>，剩余的30%作为测试集 SCV <script type="math/tex" id="MathJax-Element-2251">S_{CV}</script>。
2.在 Strain <script type="math/tex" id="MathJax-Element-2252">S_{train}</script>上训练每一个 Mi <script type="math/tex" id="MathJax-Element-2253">M_i</script>，得到预测函数 hi <script type="math/tex" id="MathJax-Element-2254">h_i</script>。
3.在 SCV <script type="math/tex" id="MathJax-Element-2255">S_{CV}</script>上测试每一个 hi <script type="math/tex" id="MathJax-Element-2256">h_i</script>，得到相应的经验误差 ε^SCV(hi) <script type="math/tex" id="MathJax-Element-2257">\hat\varepsilon_{S_{CV}}(h_i)</script>。
4.选择具有最小 ε^SCV(hi) <script type="math/tex" id="MathJax-Element-2258">\hat\varepsilon_{S_{CV}}(h_i)</script>的 hi <script type="math/tex" id="MathJax-Element-2259">h_i</script>，作为最佳模型。

这种方法被称为hold-out交叉验证（cross validation），或者称为简单（simple）交叉验证。

由于 Strain <script type="math/tex" id="MathJax-Element-2260">S_{train}</script>和 SCV <script type="math/tex" id="MathJax-Element-2261">S_{CV}</script>是随机选取的，因此我们可以认为这里的经验误差 ε^SCV(hi) <script type="math/tex" id="MathJax-Element-2262">\hat\varepsilon_{S_{CV}}(h_i)</script>是 hi <script type="math/tex" id="MathJax-Element-2263">h_i</script>的泛化误差的一个很好的估计值。测试集一般占所有样本数的1/4~1/3，这里的30%是一个典型值。

还可以对模型作改进，当选出最佳的模型 Mi <script type="math/tex" id="MathJax-Element-2264">M_i</script>后，再在全部数据S上做一次训练，显然训练数据越多，模型参数越准确。

简单交叉验证方法的缺点在于得到的最佳模型是在70%的训练数据上选出来的，不代表在全部训练数据上是最佳的。还有当训练数据本来就很少时，再分出测试集后，训练数据就太少了。

我们对简单交叉验证方法再做一次改进，如下：

1.将全部训练集S分成k个不相交的子集，假设S中的训练样例个数为m，那么每一个子集有m/k个训练样例，相应的子集称作 {S1,…,Sk} <script type="math/tex" id="MathJax-Element-2265">\{S_1,\dots,S_k\}</script>。
2.每次从模型集合 M <script type="math/tex" id="MathJax-Element-2266">\mathcal{M}</script>中拿出来一个 Mi <script type="math/tex" id="MathJax-Element-2267">M_i</script>，然后在S中选择出k-1个子集 S1∪⋯∪Sj−1∪Sj+1∪⋯∪Sk <script type="math/tex" id="MathJax-Element-2268">S_1\cup\dots\cup S_{j-1}\cup S_{j+1}\cup\dots\cup S_k</script>，在这个集合上训练 Mi <script type="math/tex" id="MathJax-Element-2269">M_i</script>得到预测函数 hij <script type="math/tex" id="MathJax-Element-2270">h_{ij}</script>。在 Sj <script type="math/tex" id="MathJax-Element-2271">S_j</script>上测试 hij <script type="math/tex" id="MathJax-Element-2272">h_{ij}</script>，得到相应的经验误差 ε^Sj(hij) <script type="math/tex" id="MathJax-Element-2273">\hat\varepsilon_{S_j}(h_{ij})</script>。
3.使用 1k∑kj=1ε^Sj(hij) <script type="math/tex" id="MathJax-Element-2274">\frac{1}{k}\sum_{j=1}^k\hat\varepsilon_{S_j}(h_{ij})</script>作为 Mi <script type="math/tex" id="MathJax-Element-2275">M_i</script>泛化误差的估计值。
4.选出泛化误差估计值最小的 Mi <script type="math/tex" id="MathJax-Element-2276">M_i</script>，在S上重新训练，得到最终的预测函数 hi <script type="math/tex" id="MathJax-Element-2277">h_i</script>。

这个方法被称为k-折叠（k-fold）交叉验证。一般来说k取值为10，这样训练数据稀疏时，基本上也能进行训练，缺点是训练和测试次数过多。

更极端的，如果 k=m <script type="math/tex" id="MathJax-Element-2278">k=m</script>，则该方法又被称为leave-one-out交叉验证。

特征选择

特征选择（Feature Selection）严格来说也是模型选择中的一种。

假设我们想对维度为n的样本点进行回归，如果，n远远大于训练样例数m，且你认为其中只有很少的特征起关键作用的话，就可以对整个特征集进行特征选择，以减少特征的数量。

对于n个特征的 M <script type="math/tex" id="MathJax-Element-672">\mathcal{M}</script>来说，根据特征是否包含在最终结果中，可以写出 2n <script type="math/tex" id="MathJax-Element-673">2^n</script>个不同的 Mi <script type="math/tex" id="MathJax-Element-674">M_i</script>。直接使用上面的交叉验证方法，计算量过大。这时可以采用如下启发式算法：

1.初始化特征集 F=∅ <script type="math/tex" id="MathJax-Element-675">\mathcal{F}=\emptyset</script>。
2.Repeat {
(a)for 特征i=1 to n, {
如果 i∉F <script type="math/tex" id="MathJax-Element-676">i\notin\mathcal{F}</script>，则 Fi=F∪{i} <script type="math/tex" id="MathJax-Element-677">\mathcal{F}_i=\mathcal{F}\cup\{i\}</script>。
在 Fi <script type="math/tex" id="MathJax-Element-678">\mathcal{F}_i</script>上使用交叉验证方法评估它的泛化误差。
}
(b)将第(a)步中最优的 Fi <script type="math/tex" id="MathJax-Element-679">\mathcal{F}_i</script>设为新的 F <script type="math/tex" id="MathJax-Element-680">\mathcal{F}</script>。
}
3.选择并输出搜索过程中得到的最优子集。

这个算法被称为前向搜索（forward search）。其外部循环的终止条件为 ∣F∣ <script type="math/tex" id="MathJax-Element-681">\lvert\mathcal{F}\rvert</script>达到n或者事先设定的门限值。

前向搜索属于wrapper model特征选择方法的一种。 Wrapper这里指不断地使用不同的特征子集来测试学习的算法。

除了前向搜索之外，还有后向搜索（backward search）算法。它和前者的区别在于，它的初始集合为全集，然后每次删除一个特征，并评价，直到 ∣F∣ <script type="math/tex" id="MathJax-Element-682">\lvert\mathcal{F}\rvert</script>达到阈值或者为空，然后选择最佳的 F <script type="math/tex" id="MathJax-Element-683">\mathcal{F}</script>即可。

可以看出无论前向搜索，还是后向搜索，其算法复杂度都是 O(n2) <script type="math/tex" id="MathJax-Element-684">O(n^2)</script>。

KL散度

KL散度（Kullback–Leibler divergence）是两个随机分布间距离的度量。其定义如下：

<script type="math/tex; mode=display" id="MathJax-Element-349">D_{KL}(P\|Q)=\sum_iP(i)\log\frac{P(i)}{Q(i)}</script>

其中，P和Q是离散概率分布， P(i) <script type="math/tex" id="MathJax-Element-350">P(i)</script>和 Q(i) <script type="math/tex" id="MathJax-Element-351">Q(i)</script>是相应分布的概率密度函数。如果P和Q是连续随机变量的话，将上式中的累加符号换成积分符号即可。

但KL散度并不是真正的度量（metric）。它既不满足三角不等式(两边之和 ≥ <script type="math/tex" id="MathJax-Element-352">\ge</script>第三边)，也不满足对称性（即 DKL(P∥Q)≠DKL(Q∥P) <script type="math/tex" id="MathJax-Element-353">D_{KL}(P\|Q)\neq D_{KL}(Q\|P)</script>）。

注：Solomon Kullback，1907～1994，美国数学家和密码学家。乔治·华盛顿大学博士。NSA首任首席科学家。二战期间，参与破解德国的Enigma机器。

Richard Leibler，1914～2003，美国数学家和密码学家。伊利诺伊大学博士。NSA高级主管，入选NSA名人堂。

过滤特征选择方法

过滤特征选择（Filter feature selection）方法，是另一种启发式的特征选择算法，计算量比较小。它的思路是计算特征 xi <script type="math/tex" id="MathJax-Element-312">x_i</script>和类别标签y之间的相关度的评分 S(i) <script type="math/tex" id="MathJax-Element-313">S(i)</script>。

可以使用 xi <script type="math/tex" id="MathJax-Element-314">x_i</script>和y之间的互信息量（mutual information），作为评分依据。

<script type="math/tex; mode=display" id="MathJax-Element-292">MI(x_i,y)=\sum_{x_i\in X_i}\sum_{y\in Y}p(x_i,y)\log\frac{p(x_i,y)}{p(x_i)p(y)}</script>

其中， p(xi,y) <script type="math/tex" id="MathJax-Element-293">p(x_i,y)</script>是 xi <script type="math/tex" id="MathJax-Element-294">x_i</script>和y的联合概率密度， p(xi) <script type="math/tex" id="MathJax-Element-295">p(x_i)</script>和 p(y) <script type="math/tex" id="MathJax-Element-296">p(y)</script>是相应的边缘概率密度。

和KL散度类似，如果x和y是连续随机变量的话，将上式中的累加符号换成积分符号即可。

MI也可以用KL散度来表示：

<script type="math/tex; mode=display" id="MathJax-Element-248">MI(x_i,y)=KL(p(x_i,y)\|p(x_i)p(y))</script>

过滤特征选择方法的算法复杂度为 O(n) <script type="math/tex" id="MathJax-Element-249">O(n)</script>。

最后一个问题，选择多少个特征合适呢？按照 S(i) <script type="math/tex" id="MathJax-Element-250">S(i)</script>从高到低的顺序，依次选择1到n个特征进行交叉验证，直到效果达到预期为止。

贝叶斯统计和规则化

前面提到最大似然（maximum likelihood）估计方法的公式如下：

<script type="math/tex; mode=display" id="MathJax-Element-230">\theta_{ML}=\arg\max_\theta\prod_{i=1}^mp(y^{(i)}\vert x^{(i)};\theta)</script>

从频率统计（frequentist statistic）学派的观点来看，这里的 θ <script type="math/tex" id="MathJax-Element-231">\theta</script>是一个未知的常数，我们的任务就是求出这个常数。然而从贝叶斯学派的观点来看， θ <script type="math/tex" id="MathJax-Element-232">\theta</script>是一个未知的随机变量。

也就是说似然函数，对于前者来说，是这样的： ∏mi=1p(y(i)|x(i);θ) <script type="math/tex" id="MathJax-Element-233">\prod_{i=1}^mp(y^{(i)}\vert x^{(i)};\theta)</script>；但对于后者来说，却是这样的： ∏mi=1p(y(i)|x(i),θ) <script type="math/tex" id="MathJax-Element-234">\prod_{i=1}^mp(y^{(i)}\vert x^{(i)},\theta)</script>

我们首先假定 θ <script type="math/tex" id="MathJax-Element-235">\theta</script> 的分布为 <script type="math/tex" id="MathJax-Element-236">的分布为</script> p(θ) <script type="math/tex" id="MathJax-Element-237">p(\theta)</script>，这种假定由于没有事实根据，通常被称作先验分布（prior distribution）。

我们针对训练集 S={(x(i),y(i))}mi=1 <script type="math/tex" id="MathJax-Element-238">S=\{(x^{(i)},y^{(i)})\}_{i=1}^m</script>，训练得到预测函数。并按照如下公式计算后验分布（posterior distribution）：

<script type="math/tex; mode=display" id="MathJax-Element-92">p(\theta\vert S)=\frac{p(S\vert\theta)p(\theta)}{p(S)}\tag{1}</script>

由全概率公式可得：

<script type="math/tex; mode=display" id="MathJax-Element-129">p(S)=p(S\vert\theta_1)p(\theta_1)+\dots+p(S\vert\theta_n)p(\theta_n)</script>

上式的 θi <script type="math/tex" id="MathJax-Element-130">\theta_i</script>表示 θ <script type="math/tex" id="MathJax-Element-131">\theta</script>的各个取值区间，然而由于 θ <script type="math/tex" id="MathJax-Element-132">\theta</script>是连续随机变量，根据微积分原理可得：

<script type="math/tex; mode=display" id="MathJax-Element-133">p(S)=\int_\theta p(S\vert\theta)p(\theta)\mathrm{d}\theta\tag{2}</script>

将公式2代入公式1可得：

<script type="math/tex; mode=display" id="MathJax-Element-98">p(\theta\vert S)=\frac{p(S\vert\theta)p(\theta)}{\int_\theta p(S\vert\theta)p(\theta)\mathrm{d}\theta}=\frac{\left(\prod_{i=1}^mp(y^{(i)}\vert x^{(i)},\theta)\right)p(\theta)}{\int_\theta\left(\prod_{i=1}^mp(y^{(i)}\vert x^{(i)},\theta)\right)p(\theta)\mathrm{d}\theta}</script>

当我们针对新的样本x进行预测时，和上面的推导类似，可得：

<script type="math/tex; mode=display" id="MathJax-Element-99">p(y\vert x,S)=\int_\theta p(y\vert x,\theta,S)p(\theta\vert S)\mathrm{d}\theta</script>

因为预测样本集和训练样本集的分布是独立的，因此上式又可写为：

<script type="math/tex; mode=display" id="MathJax-Element-100">p(y\vert x,S)=\int_\theta p(y\vert x,\theta)p(\theta\vert S)\mathrm{d}\theta</script>

这个公式又被称作后验预测分布（Posterior predictive distribution）。