支持向量机(Support Vector Machine,SVM)算法复杂度详解

水深无声 2023-06-30 05:28 23阅读 0赞

关于支持向量机的算法复杂度，因为SVM在训练阶段的算法较为复杂，详细的算法复杂度较为难以推算且众说纷纭，与很多因素相关。但是可以根据相应的数据类型大致推算出SVM的算法复杂度。

**参考资料：**

Burges C J C . A Tutorial on Support Vector Machines for Pattern Recognition\[J\]. Data Mining and Knowledge Discovery, 1998, 2(2):121-167.

**文献地址：**

[https://www.researchgate.net/publication/226658534\_A\_Tutorial\_on\_Support\_Vector\_Machines\_for\_Pattern\_Recognition][https_www.researchgate.net_publication_226658534_A_Tutorial_on_Support_Vector_Machines_for_Pattern_Recognition]

**目录**

一、训练阶段的算法复杂度

1.1 算法复杂度

1.2 参考文献

二、测试阶段的算法复杂度

2.1 算法复杂度

2.2 参考文献与推导

三、测试阶段存储量分析

3.1 测试阶段线性SVM存储复杂度

--------------------

# 一、训练阶段的算法复杂度 #

## 1.1 算法复杂度 ##

训练算法为Bunch-Kaufman算法，算法复杂度为：

![20200115130850284.png][]

其中， ![20200115125645907.png][]为支持向量的个数， ![20200115125721658.png][]为输入向量的维度，![20200115125731817.png][] 为训练样本点的个数。上边界为Upper Bound。当条件介于以上条件之间时，运算复杂度介于以上运算复杂度之间。

## 1.2 参考文献 ##

详细参见A Tutorial on Support Vector Machines for Pattern Recognition\[J\] P28

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70][]

# 二、测试阶段的算法复杂度 #

## 2.1 算法复杂度 ##

SVM在测试阶段的算法复杂度为： ![20200115132953276.png][],M为SVM的kernel需要的运算次数，如果RBF核的话并且是点乘的话，M就是![20200115133007788.png][]

因此对于线性SVM分类器，算法复杂度为![20200115133043836.png][]

就是支持向量的个数乘以输入向量的维度。

## 2.2 参考文献与推导 ##

详细参见A Tutorial on Support Vector Machines for Pattern Recognition\[J\]  P29

原文：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70 1][]

相应的测试阶段的运算公式为：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70 2][]

# 三、测试阶段存储量分析 #

注：第三部分未经过详细考证，可能有误，欢迎留言交流与探讨。

## 3.1 测试阶段线性SVM存储复杂度 ##

假定分类数量为![20200115125645907.png][]，也是支持向量的个数，输入向量维度为![20200115125721658.png][]

相当于在维度为![20200115125721658.png][]的高维空间上，存储![20200115125645907.png][]个高维超平面，用于对每个![20200115125721658.png][]维度的样本点进行分类。

线性SVM需要存储的参数就是这![20200115125645907.png][]个高维超平面的参数，共![20200118180323576.png][]个数字需要存储。

相关内容：

[博客文章总目录-邢翔瑞的技术博客 ][-_]

[机器学习算法基础问题(一)PCA|SVM|贝叶斯|过拟合 ][PCA_SVM_]

[机器学习算法基础问题(二)类别不均|尺寸及感受野|Batch Norm|损失函数 ][Batch Norm_]

*  [linux操作系统基础知识 ][linux_]
 *  [谷歌论文Weight Agnostic Neural Networks（WANN）权重无关神经网络 ][Weight Agnostic Neural Networks_WANN_]
 *  [Unet论文详解U-Net:Convolutional Networks for Biomedical Image Segmentation ][Unet_U-Net_Convolutional Networks for Biomedical Image Segmentation]
 *  [Text to image基于GAN的文本生成图像GAN-INT-CLS解析 ][Text to image_GAN_GAN-INT-CLS_]
 *  [眼底血管分割MICCAI 2019论文详解Multi-task Neural Networks with Spatial Activation for Retinal Vessel... ][MICCAI 2019_Multi-task Neural Networks with Spatial Activation for Retinal Vessel...]

[概率相关实际问题汇总及解析 ][Link 1]

[比赛竞猜投注类问题概率模型 ][Link 2]

[王者荣耀中的数学原理及游戏策略(一)防御篇(护甲|魔抗|伤害运算机制) ][Link 3]

[https_www.researchgate.net_publication_226658534_A_Tutorial_on_Support_Vector_Machines_for_Pattern_Recognition]: https://www.researchgate.net/publication/226658534_A_Tutorial_on_Support_Vector_Machines_for_Pattern_Recognition
[20200115130850284.png]: https://img-blog.csdnimg.cn/20200115130850284.png
[20200115125645907.png]: https://img-blog.csdnimg.cn/20200115125645907.png
[20200115125721658.png]: https://img-blog.csdnimg.cn/20200115125721658.png
[20200115125731817.png]: https://img-blog.csdnimg.cn/20200115125731817.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200115130125605.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ==,size_16,color_FFFFFF,t_70
[20200115132953276.png]: https://img-blog.csdnimg.cn/20200115132953276.png
[20200115133007788.png]: https://img-blog.csdnimg.cn/20200115133007788.png
[20200115133043836.png]: https://img-blog.csdnimg.cn/20200115133043836.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200115133144152.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/202001151332215.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ==,size_16,color_FFFFFF,t_70
[20200118180323576.png]: https://img-blog.csdnimg.cn/20200118180323576.png
[-_]: https://blog.csdn.net/weixin_36474809/article/details/88884137
[PCA_SVM_]: https://blog.csdn.net/weixin_36474809/article/details/90753252
[Batch Norm_]: https://blog.csdn.net/weixin_36474809/article/details/98597337
[linux_]: https://blog.csdn.net/weixin_36474809/article/details/103528951
[Weight Agnostic Neural Networks_WANN_]: https://blog.csdn.net/weixin_36474809/article/details/103368471
[Unet_U-Net_Convolutional Networks for Biomedical Image Segmentation]: https://blog.csdn.net/weixin_36474809/article/details/87931260
[Text to image_GAN_GAN-INT-CLS_]: https://blog.csdn.net/weixin_36474809/article/details/102997864
[MICCAI 2019_Multi-task Neural Networks with Spatial Activation for Retinal Vessel...]: https://blog.csdn.net/weixin_36474809/article/details/102854635
[Link 1]: https://blog.csdn.net/weixin_36474809/article/details/101448598
[Link 2]: https://blog.csdn.net/weixin_36474809/article/details/102842063
[Link 3]: https://blog.csdn.net/weixin_36474809/article/details/102087639