机器学习讲义

### 机器学习讲义：支持向量机与LIBSVM #### 一、概述 本讲义由台湾大学计算机科学系林智仁教授撰写，主要讲述了支持向量机（SVM）的基本概念及其在实际应用中的训练方法。文档中不仅介绍了SVM的基本原理，还深入探讨了线性和非线性SVM的训练过程、参数选择以及多分类问题等关键内容。此外，还提到了如何使用LIBSVM工具包来进行实际操作。 #### 二、基础知识 ##### 2.1 为什么选择SVM和支持向量机方法？ 支持向量机在很多情况下能够与现有的分类方法相竞争，并且相对易于使用。而核技术的应用使得支持向量机能够在回归分析、密度估计、主成分分析等多个领域得到扩展和发展。 ##### 2.2 支持向量分类 - **训练数据**：表示为`x_i`，其中`i = 1,...,l`。 - **特征向量**：例如患者的信息可以表示为`[身高, 体重, ...]`。 - **类别标识**：设有一个指示向量`y`，其中`y_i`定义如下： - 如果`x_i`属于第一类，则`y_i = 1` - 如果`x_i`属于第二类，则`y_i = -1` 目标是找到一个超平面`w^T x + b = 0`，该超平面能够将两类数据完全分开。 - **决策函数**：`f(x) = sgn(w^T x + b)`，其中`x`为测试数据。 - **超平面的选择**：存在多种可能的`w`和`b`组合，但是我们需要寻找最佳的组合。 ##### 2.3 最大间隔 为了最大化分类器的边界，我们需要找到距离超平面最近的数据点，并且这些数据点到超平面的距离应该尽可能地大。这可以通过以下公式计算： - 距离`2 / ||w||`，即`2 / sqrt(w^T w)`。 - 构建一个二次规划问题来求解最优`w`和`b`： - `min_{w, b} 1/2 w^T w` - `s.t. y_i (w^T x_i + b) >= 1, i = 1,...,l` #### 三、非线性可分性 ##### 3.1 数据可能并非线性可分 有时数据可能无法通过简单的超平面进行分割。例如： - **允许训练错误**：允许一定程度的误差，即某些数据点可能位于错误的一侧。 - **映射到更高维的空间**：将原始数据映射到更高维度或无限维度的特征空间，以便在新的空间中实现线性可分。 ##### 3.2 标准SVM 标准的支持向量机模型允许一定的训练误差，并通过引入松弛变量`ξ_i`来处理非线性可分的情况。模型的目标函数如下： - `min_{w, b, ξ} 1/2 w^T w + C ∑_{i=1}^{l} ξ_i` - `s.t. y_i (w^T φ(x_i) + b) >= 1 - ξ_i, ξ_i >= 0, i = 1,...,l` 其中`φ(x)`表示一个映射函数，它可以将低维数据映射到高维空间。 ##### 示例 假设`x ∈ R^3`，我们可以将其映射到`φ(x) ∈ R^10`的空间，例如`φ(x) = (1, √(2x_1), √(2x_2), ...)` #### 四、LIBSVM LIBSVM是一个开源的支持向量机软件包，广泛应用于学术界和工业界。它提供了一套完整的工具来解决分类和回归问题。LIBSVM的特点包括： - **高效性**：对于中小型数据集，LIBSVM表现出极高的效率。 - **易用性**：用户可以通过简单的命令行接口调用LIBSVM的各种功能。 - **灵活性**：支持多种核函数，如线性核、多项式核、径向基核等。 #### 五、总结 支持向量机作为一种强大的机器学习算法，在许多领域都有着广泛的应用。通过本讲义的学习，我们不仅了解了SVM的基本原理，还掌握了如何使用LIBSVM工具包来实现具体的任务。未来的研究方向包括进一步优化SVM算法、探索更多种类的核函数以及提高其在大规模数据集上的性能表现。