更高效的支持向量机算法实现及其在手写数字识别中的应用——00绪论

大数据机器学习课程第二次实验项目

作者

叶璨铭 (2024214500) ycm24@mails.tsinghua.edu.cn

发布于

2024年11月11日星期一

清华深研院-横

1 绪论

2 代码与文档格式说明

本文档使用Jupyter Notebook编写，所以同时包括了实验文档和实验代码。

本次实验项目采用了 Quarto + nbdev 的系统来发布Jupyter Notebook, 因而我们的实验文档导出为pdf和html格式可以进行阅读，而我们的代码也导出为python模块形式，可以作为代码库被其他项目使用。

我们这样做的好处是，避免单独管理一堆 .py 文件，防止代码冗余和同步混乱，py文件和pdf文件都是从.ipynb文件导出的，可以保证实验文档和代码的一致性。

!!! important

可以通过以下命令安装我们实验的代码：

```shell
pip install git+https://github.com/Open-Book-Studio/THU-Coursework-Machine-Learning-for-Big-Data.git
```
我们的代码导出为了python模块形式，通过以下命令导入：
```python
from thu_big_data_ml.svm import *
```

https://github.com/Open-Book-Studio/THU-Coursework-Machine-Learning-for-Big-Data.git 是我们本次大数据机器学习课程实验的代码仓库地址，

而这次作业中，我开发的另一个用于图像分类科研的开源项目有名的分类框架 (NamableClassify)也相应地进行了代码更新，把我们这次作业实现的SVM算法加入到了其中。接下来我们也会用到这个项目中的一些代码（比如分类评测指标）来完成本次作业。我还构建了我们课题组的基础依赖库ScholarlyInfrastructure，对标fastcore库，对AI科研经常会用到的一些基础性地、和Python语言的表达力有关的代码进行了整理，比如PyTorch模型检查、清晰的日志、实验参数管理、异常处理、argmax自动函数优化等。这里我们用到了实验参数管理功能，把SVM的超参数表达为随机变量，随即使用元参数优化算法进行搜索。

pip install git+https://github.com/2catycm/NamableClassify.git
pip install git+https://github.com/THU-CVML/ScholarlyInfrastructure.git
from namable_classify import *
from scholarly_infrastructure import *

以上代码库开源在github，欢迎各位同学、老师们提出宝贵意见，或者加入我们的开发一起完善，构建更加优质的科研工具。

!!! important

本文档具有一定的交互性，建议使用浏览器打开html文件，这样比pdf文件阅读体验更佳。

由于这次项目作业内容太多，为了便于管理，我们将项目文档和代码分为了不同几个部分。

3 实验目的与项目要求

老师给我们的要求是

  1. ⼿动实现一个 SVM 分类器，熟悉 SVM 的原理与优化求解 SVM 分类器的算法的过程。

  2. MNIST 数据集分类，报告你在测试集上的准确率，与已有SVM库进行对比。

  3. 对 SVM 分类器训练的超参数(包括收敛终止条件，学习率等)进行调优

  4. 构建使用 kernel 方法的 SVM 分类器

  5. 对比不同 SVM 方法

作为Top1大学的学生，我们不仅需要完成以上内容，还需要进行一些深入的思考和探索。

  1. 现有最流行的SVM分类的实现是sklearn以及其背后的libsvm，由于C++编写，确实在CPU上运行很快。但是，如果我们需要在GPU上运行，是否可以考虑用CUDA等方法来加速呢？我们决定尝试一下实现速度更快的SVM分类器。
  2. sklearn自带的调参GridSearchCV和RandomizedSearchCV都具有一定的局限性。参考谷歌调参手册，我们使用科学的实验设计来对SVM分类算法的元参数进行搜索，从而实现更高的分类精度，并且获得一些insight，便于我们后续科研中使用SVM。
  3. 实现自己的kernel方法。实现之后，不仅像2那样参考谷歌调参手册和假设检验来比较数值上的性能，还使用可视化工具来对不同核函数的效果进行比较。
  4. 除了李航《统计学习方法》的介绍逻辑，也补充阅读周志华的《机器学习》西瓜书，加深对SVM的理解。进一步阅读深度学习时代的SVM前沿论文，探索一些更加新的SVM策略，为后续科研提供参考。

事不宜迟，我们开始动手吧！

4 实验数据

MNIST 数据库是由 Yann et. al. 提供的⼿写数字数据库⽂件, 官网地址为 http://yann.lecun.com/exdb/mnist/。 主要包含了 60000 张的训练图像和 10000 张的测试图像

类似于上一次Project（KD树实现KNN），我们使用 sklearn CI（持续集成）测试用例的load_digits数据集，而不只是使用原始的MNIST数据集，来加快实验的效率。并且在划分数据集时，train_test_split应当使用stratify参数，以确保每一类样本的比例相同。

from scholarly_infrastructure.logging.nucleus import logger, print
from sklearn.datasets import load_digits, fetch_openml
# dataset_dict_uci_digits = load_digits(as_frame=True)
dataset_dict_uci_digits = load_digits(as_frame=False)
dataset_dict_full_mnist = fetch_openml("mnist_784", as_frame=True)
dataset_dict_uci_digits.keys(), dataset_dict_full_mnist.keys()








(
    dict_keys(['data', 'target', 'frame', 'feature_names', 'target_names', 'images', 'DESCR']),
    dict_keys(['data', 'target', 'frame', 'categories', 'feature_names', 'target_names', 'DESCR', 'details', 'url'])
)










dataset_dict_uci_digits.target_names












array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])










source




4.1 sklearn_to_X_y_categories




 sklearn_to_X_y_categories (dataset_dict)







Exported source

import pandas as pd
import numpy as np









Exported source

def sklearn_to_X_y_categories(dataset_dict):
    X = dataset_dict['data']
    y = dataset_dict['target']
    if isinstance(X, pd.DataFrame):
        X:np.array = X.values
    if isinstance(y, pd.Series):
        y:np.array = y.values
    # if y.dtype.name == 'category':
    #     categories = y.dtype.categories
    # else:
    X = X.astype(np.float32)
    y = y.astype(np.int64)
    categories = np.unique(y)
    # print(str((X.shape, X.dtype, y.shape, y.dtype, categories)))
    print(X.shape, X.dtype, y.shape, y.dtype, categories)
    return X, y, categories








X, y, categories = sklearn_to_X_y_categories(dataset_dict_uci_digits)
X_full, y_full, categories_full = sklearn_to_X_y_categories(dataset_dict_full_mnist)




Sat 2024-11-16 22:11:02.268075







INFO     ((1797, 64), dtype('float32'), (1797,), dtype('int64'), array([0, 1, 2, 3, 4, 5, 6, 7, 8,    nucleus.py:55
         9]))                                                                                                      







Sat 2024-11-16 22:11:02.537849







INFO     ((70000, 784), dtype('float32'), (70000,), dtype('int64'), array([0, 1, 2, 3, 4, 5, 6, 7, 8, nucleus.py:55
         9]))                                                                                                      







划分数据集为训练集和测试集。 注意这里与官方的mnist划分有所不同，但是是合理而且科学的，因为正确使用了stratify参数。




source






4.2 make_train_val_test




 make_train_val_test (X, y, val_size=0.1, test_size=0.2, random_state=42,
                      normalize=True)







Exported source

from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler









Exported source

def make_train_val_test(X, y, val_size=0.1, test_size=0.2, random_state=42, normalize=True):
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42, 
                                                        stratify=y)
    # print(len(X_train), len(X_test))
    if normalize:
        scaler = StandardScaler()
        X_train = scaler.fit_transform(X_train)
        X_test = scaler.transform(X_test)
    # 进一步划分出验证集，用于调参、early stopping等。
    X_train, X_val, y_train, y_val = train_test_split(X_train, y_train, test_size=0.1, random_state=42, 
                                                    stratify=y_train)
    print(len(X_train), len(X_val), len(X_test))
    return X_train, X_val, X_test, y_train, y_val, y_test








X_train, X_val, X_test, y_train, y_val, y_test = make_train_val_test(X, y)
X_train_full, X_val_full, X_test_full, y_train_full, y_val_full, y_test_full = make_train_val_test(X_full, y_full)




Sat 2024-11-16 22:11:02.748631







INFO     (1293, 144, 360)                                                                             nucleus.py:55







Sat 2024-11-16 22:11:07.325810







INFO     (50400, 5600, 14000)                                                                         nucleus.py:55







获得 PyTorch 格式 的Dataset， 进一步得到 PyTorch Lightning 的 DataModule




source






4.3 get_torch_dataset




 get_torch_dataset (X, y)







Exported source

import torch
import lightning as L









Exported source

def get_torch_dataset(X, y):
    X_tensor = torch.tensor(X, dtype=torch.float32)
    y_tensor = torch.tensor(y, dtype=torch.long)
    dataset = torch.utils.data.TensorDataset(X_tensor, y_tensor)
    return dataset








train_set = get_torch_dataset(X_train, y_train)
val_set = get_torch_dataset(X_val, y_val)
test_set = get_torch_dataset(X_test, y_test)
train_set_full = get_torch_dataset(X_train_full, y_train_full)
val_set_full = get_torch_dataset(X_val_full, y_val_full)
test_set_full = get_torch_dataset(X_test_full, y_test_full)






import lightning as L






data_module = L.LightningDataModule.from_datasets(
    train_dataset=train_set, 
    val_dataset=val_set, 
    test_dataset=test_set, 
    predict_dataset=test_set, 
    batch_size=128,  
    num_workers=4
)
data_module_full = L.LightningDataModule.from_datasets(
    train_dataset=train_set_full, 
    val_dataset=val_set_full, 
    test_dataset=test_set_full, 
    predict_dataset=test_set_full, 
    batch_size=128,  
    num_workers=4
)






source






4.4 process_sklearn_dataset_dict




 process_sklearn_dataset_dict (dataset_dict:dict,
                               return_type:Literal['numpy','torch','lightn
                               ing','pandas','all'])







Exported source

from typing import Literal









Exported source

ReturnType = Literal['numpy', 'torch', 'lightning', 'pandas', 'all']

def process_sklearn_dataset_dict(dataset_dict:dict, return_type:ReturnType):
    X, y, categories = sklearn_to_X_y_categories(dataset_dict)
    X_train, X_val, X_test, y_train, y_val, y_test = make_train_val_test(X, y)
    train_set = get_torch_dataset(X_train, y_train)
    val_set = get_torch_dataset(X_val, y_val)
    test_set = get_torch_dataset(X_test, y_test)
    data_module = L.LightningDataModule.from_datasets(
        train_dataset=train_set, 
            val_dataset=val_set, 
            test_dataset=test_set, 
            predict_dataset=test_set, 
            batch_size=128,  
            num_workers=4
        )
    if return_type == 'numpy':
        return X_train, X_val, X_test, y_train, y_val, y_test
    elif return_type == 'torch':
        return train_set, val_set, test_set
    elif return_type == 'lightning':
        return data_module  
    elif return_type == 'pandas':
        raise NotImplementedError("Pandas not implemented yet") # 这里可以用 dataset_dict 的 frame, 但是 train test split 还有预处理。
    elif return_type == 'all':
        return X_train, X_val, X_test, y_train, y_val, y_test, train_set, val_set, test_set, data_module, categories
    else:
        raise ValueError(f"Invalid return_type: {return_type}")












5 理论回顾




5.1 SVM有哪些优化形式？我们选择哪种来实现代码？


参考论文1和论文2，以及sklearn代码库中的分法，支持向量机（SVM）的优化方法最主要地分为两大流派：


    

  1. 使用hinge loss（或者周志华西瓜书SVM章节提到的其他surrogate loss）对线性支持向量机软间隔原始问题进行随机梯度下降SGD（或者西瓜书提到坐标下降也可以）。
    2. 

  2. 使用SMO算法（或者通用的凸二次规划算法）来求解Kernel SVM的对偶问题（也可以求解Linear Kernel）。
    3. 



这是两个不同形式的问题：


    

  1. 参数保存上，（我个人认为）后者是非参数化方法，需要保存训练集中的支持向量，可能会有很多个，而前者训练成功后就是w和b，可以认为是参数化方法。
    2. 

  2. 前者与现代的深度学习方法非常兼容，可以端到端地优化，作为深度学习方法的一个特殊loss。而后者虽然也有很多文章将CNN预训练的feature加上SVC去做分类器，但是本身的优化问题是不一样的优化问题。前者的优化难度和神经网络类似（不是简单，是很难），后者却对数据量非常敏感，数据量大的时候会很慢（不少论文提到对大数据集使用SVM仍然是研究热点，西瓜书指出其时间复杂度理论上不可能低于O(m^2)）。
    3. 

  3. 后者支持核方法，而前者有论文和博客指出，SGD不可能优化Kernel Method的SVM。
    4. 

  4. 对于前者，论文3说使用GD来优化的情况下，对线性可分数据集而言，hard margin SVM和Logistic Regression是等价的。
    5. 







5.2 SVM如何实现多分类？


李航书上介绍的SVM是用于二分类问题的，然而本次项目我们需要做MNIST手写数字分类，这需要多分类，因而我们必须了解SVM如何实现多分类。


周志华西瓜书告诉我们认为普通的二分类分类器，可以通过ovr或者ovo策略来实现多分类。那么SVM本身有没有更加独特的技巧去实现多分类呢？


我们参考这个课件。


目前，构造SVM多类分类器的方法主要有两类：


    

  1. 直接法（也就是我说的独特的方法）：直接在目标函数上进行修改，将多个分类面的参数求解合并到一个最优化问题中，通过求解该最优化问题“一次性”实现多类分类。
    2. 

  2. 间接法（所有二分类器都可以这么操作得到多分类器）：主要是通过组合多个二分类器来实现多分类器的构造，常见的方法有one-against-one（OvO）和one-against-all（OvR）两种。具体来说，

      

    • 一对多法（One-Versus-Rest, OvR）：训练时依次把某个类别的样本归为一类，其他剩余的样本归为另一类，这样k个类别的样本就构造出了k个SVM。分类时将未知样本分类为具有最大分类函数值的那类。
      • 

    • 一对一法（One-Versus-One, OvO）：将n个类别两两配对，产生n(n-1)/2个二分类任务，获得n(n-1)/2个分类器，新样本交给这些分类器，得到n(n-1)/2个结果，最终结果投票产生。
      • 

    3. 







5.3 SVM如何实现概率输出？


尽管李航书第一章把SVM是归类为非概率模型，实际上SVM经过一定的操作，是可以得到概率输出的。经典机器学习sklearn库的学习器有一个重要的API，predict_proba()，而sklearn中的SVC同样支持该API的调用。


那么SVM概率输出有哪些方法呢？是否要用到点和分离超平面的几何间隔呢？经过资料查询，我发现SVM的概率输出几种方法：


    

  1. Sigmoid函数转换：可以将实轴上的数值投射到[0,1]上，即将一个输出实值抓化为一个概率值。比如一个分类器的分界线为0，大于0标为+1，小于0标为-1；如果使用sigmoid函数套一下输出值，我们就可以说，输出为0时标为+1的概率为0.5；输出为2时标为+1的概率为0.8等。
    2. 

  2. Platt Scaling：这是libsvm中使用的一种方法，核心思想是把分类的结果作为新的训练集，用logistics回归再训练一个关系，得到具体的概率值。
    3. 

  3. CalibratedClassifierCV：在scikit-learn中，可以使用专门的函数CalibratedClassifierCV对训练好的分类器模型进行校准，校准过程用到了cross-validation。
    4. 



在使用predict_proba()函数时，返回的是一个n行k列的数组，第i行第j列上的数值是模型预测第i个预测样本为某个标签的概率，并且每一行的概率和为1。






5.4 相关工作


类似于我们这次Project的，实现SVM的代码仓库有哪些？


教育学习目的的库：


    

  • https://github.com/Kaslanarian/libsvm-sc-reading?tab=readme-ov-file

      

    • 这篇文章写得非常用心，阅读libsvm源码解读地非常详细。
      • 

    • 

  • https://github.com/lzx1019056432/Be-Friendly-To-New-People/tree/master/SVM%E6%94%AF%E6%8C%81%E5%90%91%E9%87%8F%E6%9C%BA

      

    • 作者历时一个月，终于实现了SMO版本的SVM。但是我们做这个Project只有一周，我们要站在巨人的肩膀上实现地更好。
      • 

    • 

  • https://github.com/Learner0x5a/SVM-SMO

      

    • 作者推导良久，终于搞懂了SVM以及SMO的公式，实现了符合sklearn接口的SVM。
      • 

    • 

  • https://github.com/shicaiwei123/svm-smo?tab=readme-ov-file

      

    • 作者使用numpy实现了 SMO，并且使用ovo策略实现了多分类。
      • 

    • 

  • https://github.com/kazuto1011/svm-pytorch

      

    • 作者使用早期版本的PyTorch实现了SVM。
      • 

    • 

  • https://bytepawn.com/svm-with-pytorch.html

      

    • 这篇文章实现了二分类情况下，更早期PyTorch版本下实现的SVM。并且开源到github jupyter notebook。
      • 

    • 



实际部署在工业界的Python库：


    

  • sklearn 本质上调用了 libsvm

      

    • 注意sklearn很长一段时间不会利用GPU优化SVM！ https://stackoverflow.com/questions/35292741/what-svm-python-modules-use-gpu
      • 

    • 

  • https://pypi.org/project/svmlight/
    • 



非Python语言的库


    

  • C++ libsvm https://github.com/cjlin1/libsvm

      

    • GPU升级版，基于CUDA/C++实现 https://mklab.iti.gr/results/gpu-accelerated-libsvm/
      • 

    • 

  • Rust https://athemathmo.github.io/rusty-machine/doc/rusty_machine/learning/svm/index.html
    • 

  • Rust https://docs.rs/linfa-svm/latest/linfa_svm/
    • 



可以看出这次Project的难度不小，我们需要对SVM的原理有深刻的理解，而且需要有较强的工程能力，才能手动实验一个SVM。








6 实验内容




6.1 分类的评价指标


开尔文爵士曾说，如果你连measure都做不到，谈不上improve。所以我们先measure。





Exported source

from namable_classify.metrics import compute_classification_metrics








compute_classification_metrics?




Signature:
compute_classification_metrics(
    y_true: numpy.ndarray,
    y_pred_logits: numpy.ndarray = None,
    logits_to_prob: bool = False,
    y_pred: numpy.ndarray = None,
    labels: list[int | str] | None = None,
    supress_warnings: bool = True,
    y_pred_metrics_only: bool = False,
)
Docstring: <no docstring>
File:      ~/repos/novelties/cv/cls/NamableClassify/namable_classify/metrics.py
Type:      function






这里涵盖了 from sklearn.metrics import roc_auc_score, top_k_accuracy_score, matthews_corrcoef, f1_score, precision_score, recall_score, log_loss, balanced_accuracy_score, cohen_kappa_score, hinge_loss, accuracy_score 当结果有意义的时候，这些指标都会被计算，用于评价模型的精度。






6.2 调库实现SVM


为了给我们后面的实验一个参照，我们调用现有代码库的SVM，关注其精度与速度的情况。 当然如果我们Project在此收尾，只能酌情被扣除分数。 在本节之后，我们将使用 PyTorch 和 numpy 这样的基础科学计算库，来在GPU和CPU上实现SVM及其优化。


!!! important


本次Project首先展示了几个常用的SVM库的精度与速度，并且对其进行调参；随后本次Project基于基础科学计算库手写实现了SVM及其优化，和前面的库的精度与速度进行了对比。


接下来的内容请见文件 01sv_use_lib






6.3 实现 Hinge Loss+SGD 版本的 Soft Margin Linear SVM


我们现在来实现与from sklearn.linear_model import SGDClassifier等价的 SVM，但是我们基于PyTorch实现，在GPU上面运行，期望能在大型数据集上比sklearn的实现快。


这部分内容请见文件 02svm_handy_crafted_linear






6.4 对手动实现的SVM进行调参


这部分内容请见文件 02svm_handy_crafted_linear






6.5 附加题: 对比不同 kernel 方法下的 SVM 分类器 （对完整SVM进行调参）


这一题本质上是让我们以 kernel 的选择（也包括选择线性Kernel）作为目标元参数，其他参数作为冗余或固定元参数，进行调参实验，发现不同 kernel 方法下的 SVM 分类器的分类效果数值上的区别及其显著性，并且从可视化分析上也作出进一步解释。


这部分内容请见 03svm_kernel_hpo






6.6 附加题: 构建使用 kernel 方法的 SVM 分类器 （手动实现SMO）


这也就是让我们手动实现 SMO 优化算法以及Kernel Method。


这部分内容请见 04svm_handy_crafted_kernel