机器学习10--学习理论的基础知识

本章：模型选择（交叉选择的方法）-->特征选择。

模型选择

• 设可选的模型集合为： ,那么 SVM、 logistic 回归、神经网络等模型都包含在 M 中。
• 训练集使用 S 来表示
• 任务：从 M 中选择最好的模型

方法一：简单交叉验证（数据集大）

> - 测试集的比例一般占全部数据的 1/4-1/3。30%是典型值。 > - 由于测试集是和训练集中是两个世界的，因此我们可以认为这里的经验错误接近于泛化错误。 > - 得到的最好模型，在全部数据上重新训练的到所需模型。

方法二：k-折叠交叉验证（数据集小）

> - 简而言之，这个方法就是将简单交叉验证的测试集改为 1/k，每个模型训练 k 次，测试 k 次，错误率为 k 次的平均。 - 一般讲k 取值为 10 - 数据集非常小的时候：极端情况下，k 可以取值为 m，意味着每次留一个样例做测试，这个称为 leave-one-out cross validation。

特征选择

• 其实，很多特征对于结果是无用的，想剔除 n 中的无用特征。n 个特征就有\(2^n\)种去除情况（每个特征去或者保留）。属于NP难问题。
• 本节主要将该问题简化：NP难\(2^n\)-->\(n^2\)-->\(n\)

第一种：启发式搜索方法：前向搜索和后向搜索\(O(n^2)\)

\(时间 复杂度为O(n + (n − 1) +(n − 2) + ⋯ + 1) = O(n^2)\)。 #### 前向搜索 #### 后向搜索 先将 F 设置为{1,2,..,n}，然后每次删除一个特征，并评价，直到达到阈值或者为空，然后选择最佳的 F。 ### 第二种：过滤特征选择（Filter feature selection）\(O(n)\) 过滤特征选择方法的想法是针对每一个特征 ，i 从 1 到 n，计算相对于类别标签y的信息量S(i)，得到 n 个结果，然后将 n 个S(i)按照从大到小排名，输出前 k 个特征。显然，这样复杂度大大降低，为 O(n)。 > 1、 $x_i \(是 0/1 离散值的时候 ：** 互信息（Mutual information）公式： 2、**\)x_i $是多个离散值 注：