大厂面试机器学习算法（1）SVM常考问题_svm 大厂面试-程序员宅基地
技术标签： 支持向量机 算法 面试 机器学习 数据分析与机器学习 svm
网易有道数据挖掘面试题：介绍svm的原理
字节跳动机器学习算法面试题：手推svm过程
今天整理一下面试常考问题。
文章目录
1. SVM算法原理
SVM的基本原理是求解能够正确划分训练数据集并且几何间隔最大的超平面。
如图1， w x + b = 1 wx+b=1 wx+b=1和 w x + b = − 1 wx+b=-1 wx+b=−1 即为所求超平面。
2. SVM与感知机(Perceptron)/逻辑回归（LR）的区别
- 与感知机：
感知机所求超平面为 w x + b = 0 wx+b=0 wx+b=0，对于线性可分数据集有无穷多个。而SVM所求间隔最大的超平面结果唯一。 - 与LR：
svm只考虑支持向量点，LR考虑所有样本；
svm是非参数模型，LR是参数模型；
svm的目标函数是hinge损失函数，LR采用logistics损失函数
svm自带结构风险最小化（ 1 / ∣ ∣ w ∣ ∣ 2 1/||w||^2 1/∣∣w∣∣2)，LR是经验风险最小化
svm产生区间，LR产生概率
3. 什么是支持向量
对线性可分的情形，构造硬间隔，位于间隔边界上的样本点称为支持向量；
对线性不可分的情形，构造软间隔，位于间隔边界上及间隔边界之内的样本点的实例称为支持向量。
4. 手推SVM最优化公式
目标：最大化异类支持向量的间隔。
① 点 ( x i , y i ) (x_i,y_i) (xi,yi)到直线 w x + b = 0 wx+b=0 wx+b=0的距离 d = y i ( w x i + b ∣ ∣ w ∣ ∣ ) d=y_i(\frac{wx_i+b}{||w||}) d=yi(∣∣w∣∣wxi+b)
② 支持向量：位于间隔边界线上的点，即 m i n ( x i , y i ) y i ( w x i + b ∣ ∣ w ∣ ∣ ) \underset{(x_i,y_i)}{min}y_i(\frac{wx_i+b}{||w||}) (xi,yi)minyi(∣∣w∣∣wxi+b)
③ 最大化异类支持向量间隔，即 m a x w , b m i n ( x i , y i ) y i ( w x i + b ∣ ∣ w ∣ ∣ ) \underset{w,b}{max} \underset{(x_i,y_i)}{min}y_i(\frac{wx_i+b}{||w||}) w,bmax(xi,yi)minyi(∣∣w∣∣wxi+b)
④ 根据几何直线的可缩放性质（x+y=0<=>2x+2y=0），对 ∀ w , b \forall w,b ∀w,b，可通过缩放使得 m i n ( x i , y i ) y i ( w x i + b ) \underset{(x_i,y_i)}{min}y_i(wx_i+b) (xi,yi)minyi(wxi+b)=1，即 y i ( w x i + b ) ≥ 1 y_i(wx_i+b)≥1 yi(wxi+b)≥1
因此目标函数等价于 m a x w , b 1 ∣ ∣ w ∣ ∣ \underset{w,b}{max}\frac{1}{||w||} w,bmax∣∣w∣∣1
又等价于：
m i n w , b 1 2 ∣ ∣ w ∣ ∣ 2 \underset{w,b}{min}\frac{1}{2}||w||^2 w,bmin21∣∣w∣∣2
s.t. y i ( w x i + b ) ≥ 1 y_i(wx_i+b)≥1 yi(wxi+b)≥1
即支持向量机的最优化公式。
5. SVM使用对偶计算的目的是什么？如何推导出来的？
目的有两个：
- 方便核函数的引入；
- 原问题的求解复杂度与特征的维数相关，而转成对偶问题后只与变量个数有关。而SVM的变量个数为支持向量的个数，相较于特征位数较少。
通过拉格朗日算子法使带约束的优化目标转为不带约束的优化函数，
即由： m i n w , b 1 2 ∣ ∣ w ∣ ∣ 2 \underset{w,b}{min}\frac{1}{2}||w||^2 w,bmin21∣∣w∣∣2
s.t. y i ( w x i + b ) ≥ 1 y_i(wx_i+b)≥1 yi(wxi+b)≥1
写出拉格朗日函数 L ( w , b , α ) = 1 2 ∣ ∣ w ∣ ∣ 2 + ∑ i = 1 m α i ( 1 − y i ( w x i + b ) ) L(w,b,\alpha)=\frac{1}{2}||w||^2+\sum_{i=1}^m\alpha_i(1-y_i(wx_i+b)) L(w,b,α)=21∣∣w∣∣2+∑i=1mαi(1−yi(wxi+b)),
令w和b的偏导数等于零，得：
w = ∑ i = 1 m α i y i x i w=\sum_{i=1}^m\alpha_iy_ix_i w=∑i=1mαiyixi
0 = ∑ i = 1 m α i y i 0=\sum_{i=1}^m\alpha_iy_i 0=∑i=1mαiyi
带入原来的式子，即转成对偶问题： m a x α ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j ϕ ( x i ) T ϕ ( x j ) \underset{\alpha}{max}\sum_{i=1}^m \alpha_i-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m}\alpha_i\alpha_jy_iy_j\phi(x_i)^T\phi(x_j) αmax∑i=1mαi−21∑i=1m∑j=1mαiαjyiyjϕ(xi)Tϕ(xj)
s.t. ∑ i = 1 m α i y i = 0 , α i ≥ 0 , i = 1 , 2 , . . . m . \sum_{i=1}^m\alpha_iy_i=0,\alpha_i≥0,i=1,2,...m. ∑i=1mαiyi=0,αi≥0,i=1,2,...m.
6. SVM中什么时候用线性核什么时候用高斯核?
对[n,m]数据集（即n个样本，m个特征）：
线性核函数：
① 当数据的特征提取的较好,所包含的信息量足够大,很多问题是线性可分的，一般用线性核函数，直接实现可分；
② 若样本n和特征m很大时，且特征m>>n时，需要用线性核函数，因为此时考虑高斯核函数的映射后空间维数更高，更复杂，也容易过拟合，此时使用高斯核函数的弊大于利，选择使用线性核会更好；
③ 若样本n很大，但特征m较小，同样难以避免计算复杂的问题，因此会更多考虑线性核。
高斯核函数：
① 当训练数据不可分时，需要使用核技巧，将训练数据映射到另一个高维空间，使再高维空间中，数据可线性划分；
② 若样本n一般大小，特征m较小，此时进行高斯核函数映射后，不仅能够实现将原训练数据在高维空间中实现线性划分，而且计算方面不会有很大的消耗，因此利大于弊，适合用高斯核函数。
核函数是什么？
ϕ ( x ) \phi(x) ϕ(x)为x的高维映射；
K ( x , y ) = < ϕ ( x ) , ϕ ( y ) > K(x,y)=<\phi(x),\phi(y)> K(x,y)=<ϕ(x),ϕ(y)>为核函数（"< , >"符号表示内积）；
例：设 x = ( 1 , 2 , 3 , 4 ) , y = ( 5 , 6 , 7 , 8 ) x=(1,2,3,4),y=(5,6,7,8) x=(1,2,3,4),y=(5,6,7,8)，
将 x = ( x 1 , x 2 , x 3 , x 4 ) x=(x_1,x_2,x_3,x_4) x=(x1,x2,x3,x4)映射为 ϕ ( x ) = [ x 1 2 x 1 x 2 x 1 x 3 x 1 x 4 x 2 x 1 x 2 2 x 2 x 3 x 2 x 4 x 3 x 1 x 3 x 2 x 3 2 x 3 x 4 x 4 x 1 x 4 x 2 x 4 x 3 x 4 2 ] \phi(x)= \begin{bmatrix}x_1^2&x_1x_2&x_1x_3&x_1x_4\\ x_2x_1&x_2^2&x_2x_3 & x_2x_4\\ x_3x_1&x_3x_2&x_3^2&x_3x_4\\ x_4x_1&x_4x_2&x_4x_3&x_4^2 \end{bmatrix} ϕ(x)=⎣⎢⎢⎡x12x2x1x3x1x4x1x1x2x22x3x2x4x2x1x3x2x3x32x4x3x1x4x2x4x3x4x42⎦⎥⎥⎤；
K ( x , y ) = < ϕ ( x ) , ϕ ( y ) > = < x , y > 2 K(x,y)=<\phi(x),\phi(y)>=<x,y>^2 K(x,y)=<ϕ(x),ϕ(y)>=<x,y>2
则 < ϕ ( x ) , ϕ ( y ) > = < ( 1 , 2 , 3 , 4 , 2 , 4 , 6 , 8 , 3 , 6 , 9 , 12 , 4 , 8 , 12 , 16 ) , ( 25 , 30 , 35 , 40 , 30 , 36 , 42 , 48 , 35 , 42 , 49 , 56 , 40 , 48 , 56 , 64 ) > = 25 + 60 + 105 + 160 + 60 + 144 + 252 + 384 + 105 + 252 + 441 + 672 + 160 + 384 + 672 + 1024 = 4900 \begin{aligned} <\phi(x),\phi(y)>&= <( 1, 2, 3, 4, 2, 4, 6, 8, 3, 6, 9, 12, 4, 8, 12, 16) , (25, 30, 35, 40, 30, 36, 42, 48, 35, 42, 49, 56, 40, 48, 56, 64)>\\[2ex] &=25+60+105+160+60+144+252+384+105+252+441+672+160+384+672+1024\\[2ex] &= 4900 \end{aligned} <ϕ(x),ϕ(y)>=<(1,2,3,4,2,4,6,8,3,6,9,12,4,8,12,16),(25,30,35,40,30,36,42,48,35,42,49,56,40,48,56,64)>=25+60+105+160+60+144+252+384+105+252+441+672+160+384+672+1024=4900
而 K ( x , y ) = ( 5 + 12 + 21 + 32 ) 2 K(x,y)=(5+12+21+32)^2 K(x,y)=(5+12+21+32)2=4900
由此可见，核函数是对两个高维映射函数的内积运算的简便运算。
为什么SVM需要核函数？
将4. 最优化公式转化为5. 对偶形式后需要进行求解，对偶问题推导为：
m a x α ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j ϕ ( x i ) T ϕ ( x j ) \underset{\alpha}{max}\sum_{i=1}^m \alpha_i-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m}\alpha_i\alpha_jy_iy_j\phi(x_i)^T\phi(x_j) αmax∑i=1mαi−21∑i=1m∑j=1mαiαjyiyjϕ(xi)Tϕ(xj) （ x i x_i xi和 x j x_j xj为任意两个样本点）
s.t. ∑ i = 1 m α i y i = 0 , α i ≥ 0 , i = 1 , 2 , . . . m . \sum_{i=1}^m\alpha_iy_i=0,\alpha_i≥0,i=1,2,...m. ∑i=1mαiyi=0,αi≥0,i=1,2,...m.
此处我们便可以通过核函数来计算上式中的 ϕ ( x i ) T ϕ ( x j ) \phi(x_i)^T\phi(x_j) ϕ(xi)Tϕ(xj)。
实际上，将低维样本点（在上例中为4维）映射为高维样本（16维）的函数是 ϕ ( x ) \phi(x) ϕ(x)，
而K(x,y)是为简化计算 ϕ ( x i ) T ϕ ( x j ) \phi(x_i)^T\phi(x_j) ϕ(xi)Tϕ(xj)引入的核函数。
在很多计算中，我们不需要计算复杂的 ϕ ( x ) \phi(x) ϕ(x)，只需要计算简单的K(x,y)即可得到结果。
7. SVM的硬间隔、软间隔表达式
硬间隔： m i n w , b 1 2 ∣ ∣ w ∣ ∣ 2 \underset{w,b}{min}\frac{1}{2}||w||^2 w,bmin21∣∣w∣∣2
s.t. y i ( w x i + b ) ≥ 1 y_i(wx_i+b)≥1 yi(wxi+b)≥1
软间隔： m i n w , b 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 m ξ i \underset{w,b}{min}\frac{1}{2}||w||^2+C\sum_{i=1}^m\xi_i w,bmin21∣∣w∣∣2+C∑i=1mξi
s.t. y i ( w x i + b ) ≥ 1 − ξ i , y_i(wx_i+b)≥1-\xi_i, yi(wxi+b)≥1−ξi,
ξ i ≥ 0 , i = 1 , 2 , . . . , m . \xi_i≥0,i=1,2,...,m. ξi≥0,i=1,2,...,m.
不同点在于有无引入松弛变量。
其中，hinge损失的松弛变量为 m a x ( 0 , y i ( w x i + b ) ) max(0,y_i(wx_i+b)) max(0,yi(wxi+b))
损失函数变为 m i n w , b 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 m m a x ( 0 , y i ( w x i + b ) ) \underset{w,b}{min}\frac{1}{2}||w||^2+C\sum_{i=1}^mmax(0,y_i(wx_i+b)) w,bmin21∣∣w∣∣2+C∑i=1mmax(0,yi(wxi+b))
智能推荐
艾美捷Epigentek DNA样品的超声能量处理方案-程序员宅基地
文章浏览阅读15次。空化气泡的大小和相应的空化能量可以通过调整完全标度的振幅水平来操纵和数字控制。通过强调超声技术中的更高通量处理和防止样品污染，Epigentek EpiSonic超声仪可以轻松集成到现有的实验室工作流程中，并且特别适合与表观遗传学和下一代应用的兼容性。Epigentek的EpiSonic已成为一种有效的剪切设备，用于在染色质免疫沉淀技术中制备染色质样品，以及用于下一代测序平台的DNA文库制备。该装置的经济性及其多重样品的能力使其成为每个实验室拥有的经济高效的工具，而不仅仅是核心设施。
11、合宙Air模块Luat开发：通过http协议获取天气信息_合宙获取天气-程序员宅基地
文章浏览阅读4.2k次，点赞3次，收藏14次。目录点击这里查看所有博文 本系列博客，理论上适用于合宙的Air202、Air268、Air720x、Air720S以及最近发布的Air720U（我还没拿到样机，应该也能支持）。 先不管支不支持，如果你用的是合宙的模块，那都不妨一试，也许会有意外收获。 我使用的是Air720SL模块，如果在其他模块上不能用，那就是底层core固件暂时还没有支持，这里的代码是没有问题的。例程仅供参考！..._合宙获取天气
EasyMesh和802.11s对比-程序员宅基地
文章浏览阅读7.7k次，点赞2次，收藏41次。1 关于meshMesh的意思是网状物，以前读书的时候，在自动化领域有传感器自组网，zigbee、蓝牙等无线方式实现各个网络节点消息通信，通过各种算法，保证整个网络中所有节点信息能经过多跳最终传递到目的地，用于数据采集。十多年过去了，在无线路由器领域又把这个mesh概念翻炒了一下，各大品牌都推出了mesh路由器，大多数是3个为一组，实现在面积较大的住宅里，增强wifi覆盖范围，智能在多热点之间切换，提升上网体验。因为节点基本上在3个以内，所以mesh的算法不必太复杂，组网形式比较简单。各厂家都自定义了组_802.11s
线程的几种状态_线程状态-程序员宅基地
文章浏览阅读5.2k次，点赞8次，收藏21次。线程的几种状态_线程状态
stack的常见用法详解_stack函数用法-程序员宅基地
文章浏览阅读4.2w次，点赞124次，收藏688次。stack翻译为栈，是STL中实现的一个后进先出的容器。要使用 stack，应先添加头文件include<stack>，并在头文件下面加上“ using namespacestd;"1. stack的定义其定义的写法和其他STL容器相同, typename可以任意基本数据类型或容器：stack<typename> name;2. stack容器内元素的访问..._stack函数用法
2018.11.16javascript课上随笔（DOM）-程序员宅基地
文章浏览阅读71次。<li> <a href = "“#”>-</a></li><li>子节点：文本节点（回车），元素节点，文本节点。不同节点树： 节点（各种类型节点）childNodes:返回子节点的所有子节点的集合，包含任何类型、元素节点（元素类型节点）：child。node.getAttribute(at...
随便推点
layui.extend的一点知识 第三方模块base 路径_layui extend-程序员宅基地
文章浏览阅读3.4k次。//config的设置是全局的layui.config({ base: '/res/js/' //假设这是你存放拓展模块的根目录}).extend({ //设定模块别名 mymod: 'mymod' //如果 mymod.js 是在根目录，也可以不用设定别名 ,mod1: 'admin/mod1' //相对于上述 base 目录的子目录}); //你也可以忽略 base 设定的根目录，直接在 extend 指定路径（主要：该功能为 layui 2.2.0 新增）layui.exten_layui extend
5G云计算：5G网络的分层思想_5g分层结构-程序员宅基地
文章浏览阅读3.2k次，点赞6次，收藏13次。分层思想分层思想分层思想-1分层思想-2分层思想-2OSI七层参考模型物理层和数据链路层物理层数据链路层网络层传输层会话层表示层应用层OSI七层模型的分层结构TCP/IP协议族的组成数据封装过程数据解封装过程PDU设备与层的对应关系各层通信分层思想分层思想-1在现实生活种，我们在喝牛奶时，未必了解他的生产过程，我们所接触的或许只是从超时购买牛奶。分层思想-2平时我们在网络时也未必知道数据的传输过程我们的所考虑的就是可以传就可以，不用管他时怎么传输的分层思想-2将复杂的流程分解为几个功能_5g分层结构
基于二值化图像转GCode的单向扫描实现-程序员宅基地
文章浏览阅读191次。在激光雕刻中，单向扫描（Unidirectional Scanning）是一种雕刻技术，其中激光头只在一个方向上移动，而不是来回移动。这种移动方式主要应用于通过激光逐行扫描图像表面的过程。具体而言，单向扫描的过程通常包括以下步骤：横向移动（X轴）： 激光头沿X轴方向移动到图像的一侧。纵向移动（Y轴）： 激光头沿Y轴方向开始逐行移动，刻蚀图像表面。这一过程是单向的，即在每一行上激光头只在一个方向上移动。返回横向移动： 一旦一行完成，激光头返回到图像的一侧，准备进行下一行的刻蚀。
算法随笔：强连通分量-程序员宅基地
文章浏览阅读577次。强连通：在有向图G中，如果两个点u和v是互相可达的，即从u出发可以到达v，从v出发也可以到达u，则成u和v是强连通的。强连通分量：如果一个有向图G不是强连通图，那么可以把它分成躲个子图，其中每个子图的内部是强连通的，而且这些子图已经扩展到最大，不能与子图外的任一点强连通，成这样的一个“极大连通”子图是G的一个强连通分量（SCC）。强连通分量的一些性质：（1）一个点必须有出度和入度，才会与其他点强连通。（2）把一个SCC从图中挖掉，不影响其他点的强连通性。_强连通分量
Django(2)|templates模板+静态资源目录static_django templates-程序员宅基地
文章浏览阅读3.9k次，点赞5次，收藏18次。在做web开发，要给用户提供一个页面，页面包括静态页面+数据，两者结合起来就是完整的可视化的页面，django的模板系统支持这种功能，首先需要写一个静态页面,然后通过python的模板语法将数据渲染上去。1.创建一个templates目录2.配置。_django templates
linux下的GPU测试软件,Ubuntu等Linux系统显卡性能测试软件 Unigine 3D-程序员宅基地
文章浏览阅读1.7k次。Ubuntu等Linux系统显卡性能测试软件 Unigine 3DUbuntu Intel显卡驱动安装，请参考：ATI和NVIDIA显卡请在软件和更新中的附加驱动中安装。 这里推荐： 运行后，F9就可评分，已测试显卡有K2000 2GB 900+分，GT330m 1GB 340+ 分，GT620 1GB 340+ 分，四代i5核显340+ 分，还有写博客的小盒子100+ 分。relaybot@re...