Vago Mundo

尘世闲游，听凭风引

    libSVM源码解读（3）

    数据存储相关

    引言 SVM问题中，空间开销最大的两种数据，一个是训练数据，另一个则是核函数矩阵。由于两者都属于Tabular（表格）数据，因此我们没有必要将两者的实现分离。libSVM中用一个虚基类QMatrix表示数据矩阵，而其派生类Kernel则用来存储核函数，再往上是对应问题的特殊核函数存储。我们这里对它们进行讲解。 QMatrix类 我们直接看QMatrix类的源码： class QMat...

    Posted by Welt Xing on July 14, 2021

    libSVM源码解读（2）

    编程技巧

    引言 libSVM中有很多程序设计手法值得我们去学习，会为我们后面的程序设计工作带来帮助，在此进行收集和总结。 模板 libSVM使用了模板（template）去编写基础的函数，先是求极大极小的函数： #ifndef min template <class T> static inline T min(T x, T y) { return (x < y) ?...

    Posted by Welt Xing on July 14, 2021

    libSVM源码解读（1）

    svm.h

    引言 libSVM总体由头文件svm.h和源文件svm.cpp构成，我们在这里对libSVM的总体结构和svm.h数据结构进行剖析。 libSVM结构 如图是libSVM求解问题的逻辑结构：训练一个复杂的SVM模型，也就是svm_train，实际上以训练一个支持向量机为基础的（svm_train），我们提到过libSVM中可以求解5种SVM模型。所以svm_train会选择一个S...

    Posted by Welt Xing on July 13, 2021

    梯度重构

    在SVM中的应用

    引言 Joachims在《Making Large Scale SVM Learning Practical》中提出了三个解决SVM训练时间长问题的解决思路： 采用更有效的方法去选择工作集（Working set selection）; 采用收缩法（Shrinking）去减小数据规模； 采用计算上的技巧来提升效率，比如缓存（Caching）和梯度的增量式更新（Increme...

    Posted by Welt Xing on July 13, 2021

    SVM的Shrink技巧

    Making large-scale SVM learning practical

    引言 在解决支持向量机问题时，我们通常去解决其对偶问题，更具体地说，是去解一个长度为样本个数的$\alpha$向量。但在大样本学习过程中，这显然会导致数据存储和运算量过大的问题。幸运的是，SVM的解存在稀疏性，也就是最终模型仅与支持向量有关。在Joachims的《Making large-scale SVM learning practical》中，他提出的Shrinking方法能够有效缩...

    Posted by Welt Xing on July 12, 2021

    SVM的分布估计

    分类概率估计和回归噪声估计

    引言 SVM可以在不提供先验概率的情况下对标签数据（和分类任务中的目标值）进行分布估计，我们这里简单介绍这些问题的思路以及libSVM中相应的算法。 k分类问题的概率估计 给定共$k$类数据，对于任意数据$\pmb x$，我们的目标是估计出 \[p_i=\Pr(y=i\vert\pmb x),i=1,\cdots,k\] 我们用“一对一”的方法，先估计成对概率： \[r_{ij}...

    Posted by Welt Xing on July 12, 2021

    libSVM的Caching

    提高SVM训练速度的技巧

    引言 我们在《SVM的Shrink技巧》中提到，为了提高SVM的训练速度，从算法上我们可以收缩矩阵维数。我们也可以通过计算机系统中的缓存机制（Caching），从数据存取的角度来减少训练时间。从现在最流行的SVM工具包libSVM的C++源码中，我们可以见识到这种机制的巧妙设计。 核函数缓存 libSVM中所采用的缓存机制是为了对核函数矩阵，也是消耗空间最大的数据结构进行存储： \[...

    Posted by Welt Xing on July 12, 2021

    支持向量机

    种类汇总

    引言 我们会在这里介绍总共五种支持向量机，分别用于分类、回归和分布估计任务。 C-SVC C-SVC，也就是$C$-Support Vector Machine, 是最简单的二分类支持向量机 其实是解决下面的优化问题： \[\begin{aligned} \min_{\pmb w,b,\pmb\xi}\quad&\dfrac12\Vert\pmb w\Vert^2+C\...

    Posted by Welt Xing on July 11, 2021

    LIBSVM中的SMO算法

    更新与剪辑

    引言 我们之前已经通过简单的数学方法求出在选定变量$i$和$j$后对应的$\alpha$分量的更新公式： \[\alpha_i^{k+1}=\alpha_i^k+\dfrac{y_i}{\eta}(E_j-E_i)\\ \alpha_j^{k+1}=\alpha_j^k+\dfrac{y_j}{\eta}(E_i-E_j)\] 这种写法是抽象的，难以通过程序实现；而我们已经知道了LIB...

    Posted by Welt Xing on July 11, 2021

    SMO算法

    变量选择问题

    引言 我们前面提过，SMO算法中的变量选择会影响目标函数的收敛速度，我们固然可以像下面这样选择变量： for i in range(1, m): # m为变量数量 for j in range(i+1, m): solve subProblem(i, j) 但我们有更好的启发式的变量选择(working set selection)方法。 标准的变量选择法 ...

    Posted by Welt Xing on July 10, 2021

    FEATURED TAGS
    C/C++ Java Python 机器学习 SVM 集成学习 优化算法 神经网络 文献解读 数学 深度学习 卷积神经网络 自动微分 异常检测 数字信号处理 LIBLINEAR 在线学习 图神经网络
    ABOUT ME

    甄心动惧，敏以敬慎

    ✉️ xingcy@smail.nju.edu.cn