svm理论与实验之18: libsvm自动参数选择
徐海蛟博士 Teaching.
libsvm可用grid.py(grid的意思是：网格)这个网格搜索python程序帮我们自动完成参数选择。这里，给童鞋们上课说说交叉验证与网格搜索。
1. 交叉验证
交叉验证是一种评估统计分析、机器学习算法对独立于训练数据的数据集的泛化能力，能够避免过拟合问题。交叉验证一般要尽量满足：
1）训练集的比例要足够多，一般大于一半(>50%)
2）训练集和测试集要均匀抽样
交叉验证主要分成以下3类：
（1）双交叉验证
也称2折交叉验证(2-CV)
将数据集分成两个相等大小的子集，进行两回合的分类器训练。在第一回合中，一个子集作为训练集，另一个作为测试集；在第二回合中，则将训练集与测试集对换后，再次训练分类器，而其中我们比较关心的是两次测试集的识别率。
在实际中2-CV并不常用，主要原因是训练集样本数太少(仅有50%)，通常不足以代表母体样本的分布，导致测试阶段识别率容易出现明显落差。此外，2-CV中子集的变异度大，往往无法达到"实验过程必须可以被复制"的要求。
（2）k折交叉验证(k-CV)
双交叉验证的延伸，做法是将数据集分成k个子集，每个子集均做一次测试集，其余的作为训练集。k-CV交叉验证重复k次，每次选择一个子集作为测试集，并将k次的平均交叉验证识别率作为结果。
优点：所有的样本都被作为了训练集和测试集，每个样本都被验证一次。10-folder通常被使用。
3)留一验证法(LOOCV)
假设数据集中有n个样本，那LOOCV也就是n-CV，意思是每个样本单独作为一次测试集，剩余n-1个样本则做为训练集。
优点：
1）每一回合中几乎所有的样本皆用于训练model，因此最接近母体样本的分布，估测所得的泛化错误比较可靠。因此在实验数据集样本较少时，可以考虑使用LOOCV。
2）实验过程中没有随机因素会影响实验数据，确保实验过程是可以被复制的。
缺点: 计算成本高，为需要建立的models数量与总样本数量相同，当总样本数量相当多时，LOOCV在实作上便有困难，除非每次训练model的速度很快，或是可以用平行化计算减少计算所需的时间。
libsvm提供了Java方法(svm.java)：
// 分层交叉验证, nr_fold折
public static void svm_cross_validation(svm_problem prob,
svm_parameter param, int nr_fold, double[] target)
方法参数含义如下：
prob：待解决的分类问题，就是样本数据。
param：svm训练参数。
nr_fold：k折交叉验证中的k，如果k=n的话就是留一法了。
target：预测值，如果是分类问题的话就是类别标签了。
在程序svm-train中可用-v n传参。如：-v 10 是10-folder交叉验证。
2. 参数选择。
以RBF核为例，在《A Practical Guide to Support Vector Classification》一文中作者提到在RBF核中有2个参数：惩罚因子C和γ参数g。对于一个给定的问题，我们事先不知道C和g取多少最优，因此我们要进行模型选择（参数搜索）。这样做的目标是找到好的(C, g)参数对，使得分类器能够精确地预测未知的数据，比如测试集。需要注意的是在在训练集上追求高精确度可能是没用的（意指泛化能力）。根据前一部分所说的，衡量泛化能力要用到交叉验证。
在文章中作者推荐使用“网格搜索”来寻找最优的C和g。所谓的网格搜索就是尝试各种可能的(C, g)对值，然后进行交叉验证，找出使交叉验证精确度最高的(C, g)对。“网格搜索”的方法很直观但是看起来有些原始。事实上有许多高级的算法，比如可以使用一些近似算法或启发式的搜索来降低复杂度。但是我们倾向于使用“网格搜索”这一简单的方法：
1）从心理上讲，不进行全面的参数搜索而是使用近似算法或启发式算法让人感觉不安全。
2）如果参数比较少，“网格搜索”的复杂度比高级算法高不了多少。
3）“网格搜索”并行性高，因为每个(C, g)对是相互独立的。
“网格搜索”就是n层循环，n是参数个数，仍然以RBF核为例，编程实现如下：
for(double c=c_begin;c<c_end;c+=c_step){
for(double g=g_begin;g<g_end;g+=g_step){
// 这里进行交叉验证，计算精确度...
}
}
通过上述两层循环找到最优的C和g就可以了。
libsvm可用grid.py(grid的意思是：网格)这个网格搜索python程序帮我们自动完成参数选择。这里，给童鞋们上课说说交叉验证与网格搜索。
1. 交叉验证
交叉验证是一种评估统计分析、机器学习算法对独立于训练数据的数据集的泛化能力，能够避免过拟合问题。交叉验证一般要尽量满足：
1）训练集的比例要足够多，一般大于一半(>50%)
2）训练集和测试集要均匀抽样
交叉验证主要分成以下3类：
（1）双交叉验证
也称2折交叉验证(2-CV)
将数据集分成两个相等大小的子集，进行两回合的分类器训练。在第一回合中，一个子集作为训练集，另一个作为测试集；在第二回合中，则将训练集与测试集对换后，再次训练分类器，而其中我们比较关心的是两次测试集的识别率。
在实际中2-CV并不常用，主要原因是训练集样本数太少(仅有50%)，通常不足以代表母体样本的分布，导致测试阶段识别率容易出现明显落差。此外，2-CV中子集的变异度大，往往无法达到"实验过程必须可以被复制"的要求。
（2）k折交叉验证(k-CV)
双交叉验证的延伸，做法是将数据集分成k个子集，每个子集均做一次测试集，其余的作为训练集。k-CV交叉验证重复k次，每次选择一个子集作为测试集，并将k次的平均交叉验证识别率作为结果。
优点：所有的样本都被作为了训练集和测试集，每个样本都被验证一次。10-folder通常被使用。
3)留一验证法(LOOCV)
假设数据集中有n个样本，那LOOCV也就是n-CV，意思是每个样本单独作为一次测试集，剩余n-1个样本则做为训练集。
优点：
1）每一回合中几乎所有的样本皆用于训练model，因此最接近母体样本的分布，估测所得的泛化错误比较可靠。因此在实验数据集样本较少时，可以考虑使用LOOCV。
2）实验过程中没有随机因素会影响实验数据，确保实验过程是可以被复制的。
缺点: 计算成本高，为需要建立的models数量与总样本数量相同，当总样本数量相当多时，LOOCV在实作上便有困难，除非每次训练model的速度很快，或是可以用平行化计算减少计算所需的时间。
libsvm提供了Java方法(svm.java)：
// 分层交叉验证, nr_fold折
public static void svm_cross_validation(svm_problem prob,
svm_parameter param, int nr_fold, double[] target)
方法参数含义如下：
prob：待解决的分类问题，就是样本数据。
param：svm训练参数。
nr_fold：k折交叉验证中的k，如果k=n的话就是留一法了。
target：预测值，如果是分类问题的话就是类别标签了。
在程序svm-train中可用-v n传参。如：-v 10 是10-folder交叉验证。
2. 参数选择。
以RBF核为例，在《A Practical Guide to Support Vector Classification》一文中作者提到在RBF核中有2个参数：惩罚因子C和γ参数g。对于一个给定的问题，我们事先不知道C和g取多少最优，因此我们要进行模型选择（参数搜索）。这样做的目标是找到好的(C, g)参数对，使得分类器能够精确地预测未知的数据，比如测试集。需要注意的是在在训练集上追求高精确度可能是没用的（意指泛化能力）。根据前一部分所说的，衡量泛化能力要用到交叉验证。
在文章中作者推荐使用“网格搜索”来寻找最优的C和g。所谓的网格搜索就是尝试各种可能的(C, g)对值，然后进行交叉验证，找出使交叉验证精确度最高的(C, g)对。“网格搜索”的方法很直观但是看起来有些原始。事实上有许多高级的算法，比如可以使用一些近似算法或启发式的搜索来降低复杂度。但是我们倾向于使用“网格搜索”这一简单的方法：
1）从心理上讲，不进行全面的参数搜索而是使用近似算法或启发式算法让人感觉不安全。
2）如果参数比较少，“网格搜索”的复杂度比高级算法高不了多少。
3）“网格搜索”并行性高，因为每个(C, g)对是相互独立的。
“网格搜索”就是n层循环，n是参数个数，仍然以RBF核为例，编程实现如下：
for(double c=c_begin;c<c_end;c+=c_step){
for(double g=g_begin;g<g_end;g+=g_step){
// 这里进行交叉验证，计算精确度...
}
}
通过上述两层循环找到最优的C和g就可以了。
