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

参考资料&＃xff1a;

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

文献地址&＃xff1a;

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算法&＃xff0c;算法复杂度为&＃xff1a;

其中&＃xff0c; 为支持向量的个数&＃xff0c; 为输入向量的维度&＃xff0c; 为训练样本点的个数。上边界为Upper Bound。当条件介于以上条件之间时&＃xff0c;运算复杂度介于以上运算复杂度之间。

1.2 参考文献

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

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

2.1 算法复杂度

SVM在测试阶段的算法复杂度为&＃xff1a; ,M为SVM的kernel需要的运算次数&＃xff0c;如果RBF核的话并且是点乘的话&＃xff0c;M就是

因此对于线性SVM分类器&＃xff0c;算法复杂度为

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

2.2 参考文献与推导

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

原文&＃xff1a;

相应的测试阶段的运算公式为&＃xff1a;

三、测试阶段存储量分析

注&＃xff1a;第三部分未经过详细考证&＃xff0c;可能有误&＃xff0c;欢迎留言交流与探讨。

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

假定分类数量为&＃xff0c;也是支持向量的个数&＃xff0c;输入向量维度为

相当于在维度为的高维空间上&＃xff0c;存储个高维超平面&＃xff0c;用于对每个维度的样本点进行分类。

线性SVM需要存储的参数就是这个高维超平面的参数&＃xff0c;共个数字需要存储。

相关内容&＃xff1a;

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

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

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

• linux操作系统基础知识
• 谷歌论文Weight Agnostic Neural Networks&＃xff08;WANN&＃xff09;权重无关神经网络
• Unet论文详解U-Net:Convolutional Networks for Biomedical Image Segmentation
• Text to image基于GAN的文本生成图像GAN-INT-CLS解析
• 眼底血管分割MICCAI 2019论文详解Multi-task Neural Networks with Spatial Activation for Retinal Vessel...

概率相关实际问题汇总及解析

比赛竞猜投注类问题概率模型

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