2021年7月初，深圳TPlink图像算法工程师面试题分享

问题1：介绍下K近邻、kmeans聚类算法

K近邻算法也称为knn算法。
knn算法的核心思想是未标记样本的类别，由距离其最近的k个邻居投票来决定。
具体的，假设我们有一个已标记好的数据集。此时有一个未标记的数据样本，我们的任务是预测出这个数据样本所属的类别。knn的原理是，计算待标记样本和数据集中每个样本的距离，取距离最近的k个样本。待标记的样本所属类别就由这k个距离最近的样本投票产生。

假设X_test为待标记的样本，X_train为已标记的数据集，算法原理如下：
遍历X_train中的所有样本，计算每个样本与X_test的距离，并把距离保存在Distance数组中。
对Distance数组进行排序，取距离最近的k个点，记为X_knn。
在X_knn中统计每个类别的个数，即class0在X_knn中有几个样本，class1在X_knn中有几个样本等。
待标记样本的类别，就是在X_knn中样本个数最多的那个类别。

算法优缺点
优点：准确性高，对异常值和噪声有较高的容忍度。
缺点：计算量较大，对内存的需求也较大。

算法参数
其算法参数是k，参数选择需要根据数据来决定。
k值越大，模型的偏差越大，对噪声数据越不敏感，当k值很大时，可能造成欠拟合；
k值越小，模型的方差就会越大，当k值太小，就会造成过拟合。

kmeans聚类算法
K-means算法的基本思想是：以空间中k个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。
假设要把样本集分为k个类别，算法描述如下：
（1）适当选择k个类的初始中心，最初一般为随机选取；
（2）在每次迭代中，对任意一个样本，分别求其到k个中心的欧式距离，将该样本归到距离最短的中心所在的类；
（3）利用均值方法更新该k个类的中心的值；
（4）对于所有的k个聚类中心，重复（2）（3），类的中心值的移动距离满足一定条件时，则迭代结束，完成分类。
Kmeans聚类算法原理简单，效果也依赖于k值和类中初始点的选择。

问题2：介绍下随机森林和SVM算法
随机森林是一种基于bagging的分类算法，它通过自助法（bootstrap）重采样技术，从原始训练样本集N中有放回地重复随机抽取n个样本生成新的训练样本集合训练决策树，然后按以上步骤生成m棵决策树组成随机森林，新数据的分类结果按分类树投票多少形成的分数而定。

随机森林大致过程如下：
1）从样本集中有放回随机采样选出n个样本；
2）从所有特征中随机选择k个特征，对选出的样本利用这些特征建立决策树（一般是CART，也可是别的或混合）；
3）重复以上两步m次，即生成m棵决策树，形成随机森林；
4）对于新数据，经过每棵树决策，最后投票确认分到哪一类。

2.随机森林特点：
随机森林有很多优点：
1） 每棵树都选择部分样本及部分特征，一定程度避免过拟合；
2） 每棵树随机选择样本并随机选择特征，使得具有很好的抗噪能力，性能稳定；
3） 能处理很高维度的数据，并且不用做特征选择；
4） 适合并行计算；
5） 实现比较简单；
缺点：
1） 参数较复杂；
2） 模型训练和预测都比较慢。

SVM算法：
是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机。

SVM可分为三种：
线性可分SVM
当训练数据线性可分时，通过最大化硬间隔（hard margin）可以学习得到一个线性分类器，即硬间隔SVM。
线性SVM
当训练数据不能线性可分但是近似线性可分时，通过最大化软间隔（soft margin）也可以学习到一个线性分类器，即软间隔SVM。
非线性SVM
当训练数据线性不可分时，通过使用核技巧（kernel trick）和最大化软间隔，可以学习到一个非线性SVM。

SVM的的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。SVM的的学习算法就是求解凸二次规划的最优化算法。

问题3：Batch-norm作用和参数
batch norm的作用


1.batch norm对于输入数据做了零均值化和方差归一化过程，方便了下一层网络的训练过程，从而加速了网络的学习。不同batch的数据，由于加入了batch norm，中间层的表现会更加稳定，输出值不会偏移太多。各层之间受之前层的影响降低，各层之间比较独立，有助于加速网络的学习。梯度爆炸和梯度消失现象也得到了一些缓解（我自己加上去的）。

2. batch norm利用的是mini-batch上的均值和方差来做的缩放，但是不同的mini-batch上面的数据是有波动的，相当于给整个模型引入了一些噪音，从而相当于有了一些正则化的效果，从而提升表现。

测试时的batch norm在训练过程中，y，b参数和w相似，直接利用梯度值乘以学习率，更新值就好了。需要注意的是，batch norm中的z的均值和方差都是通过每一个mini-batch上的训练数据得到的。在测试过程中，不能通过单独样本的数据计算均值和方差，我们可以通过让训练过程中的每一个mini-batch的均值和方差数据，计算指数加权平均，从而得到完整样本的均值和方差的一个估计。在测试过程中，使用该值作为均值和方差，从而完成计算。

问题4：L1/L2的区别和作用

L1/L2的区别
L1是模型各个参数的绝对值之和。
L2是模型各个参数的平方和的开方值。
L1会趋向于产生少量的特征，而其他的特征都是0。
因为最优的参数值很大概率出现在坐标轴上，这样就会导致某一维的权重为0 ，产生稀疏权重矩阵
L2会选择更多的特征，这些特征都会接近于0。
最优的参数值很小概率出现在坐标轴上，因此每一维的参数都不会是0。当最小化||w||时，就会使每一项趋近于0。
L1的作用是为了矩阵稀疏化。假设的是模型的参数取值满足拉普拉斯分布。
L2的作用是为了使模型更平滑，得到更好的泛化能力。假设的是参数是满足高斯分布。


问题5：模型的加速与压缩

深度学习模型压缩与加速是指利用神经网络参数和结构的冗余性精简模型，在不影响任务完成度的情况下，得到参数量更少、结构更精简的模型。被压缩后的模型对计算资源和内存的需求更小，相比原始模型能满足更广泛的应用需求。（事实上，压缩和加速是有区别的，压缩侧重于减少网络参数量，加速侧重于降低计算复杂度、提升并行能力等，压缩未必一定能加速）

主流的压缩与加速技术有4种：结构优化、剪枝（Pruning）、量化（Quantization）、知识蒸馏（Knowledge Distillation）。

问题6：两个链表存在交叉结点，怎么判断交叉点
该题为leetcode160——相交链表
方法一：暴力解法
对于A中的每一个结点，我们都遍历一次链表B查找是否存在重复结点，第一个查找到的即第一个公共结点。
时间复杂度：O(n^2)
空间复杂度：O(1)
无法通过，会超时。

方法二：
对暴力解法的一个优化方案是：先将其中一个链表存到哈希表中，此时再遍历另外一个链表查找重复结点只需 O(n) 时间。
代码如下：
时间复杂度：O(n)
空间复杂度：O(n)

方法三：走过彼此的路
利用两链表长度和相等的性质来使得两个遍历指针同步。
具体做法是：让两指针同时开始遍历，遍历到结尾的时候，跳到对方的头指针，如果有公共结点，则，会同时到达相遇的地方。
代码如下：
时间复杂度：O(n)
空间复杂度：O(1)