写在前面

【三年面试五年模拟】栏目专注于分享CV算法与机器学习相关的经典&&必备&&高价值的面试知识点，并向着更实战，更真实，更从容的方向不断优化迭代。也欢迎大家提出宝贵的意见或优化ideas，一起交流学习💪

大家好，我是Rocky。

本文是“三年面试五年模拟”之独孤九剑秘籍的第七式，之前我们将独孤九剑秘籍前六式进行汇总梳理成汇总篇，并制作成pdf版本，大家可在公众号后台 【精华干货】菜单或者回复关键词“三年面试五年模拟” 进行取用。由于本系列都是Rocky在工作之余进行整理总结，难免有疏漏与错误之处，欢迎大家对可优化的部分进行指正，我将在后续的优化迭代版本中及时更正。

在【人人都是算法工程师】算法工程师的“三年面试五年模拟”之独孤九剑秘籍（先行版）中我们阐述了这个program的愿景与规划。本系列接下来的每一篇文章都将以独孤九剑秘籍框架的逻辑展开，考虑到易读性与文章篇幅，一篇文章中只选取每个分支技能树中的2-3个经典&&高价值知识点和面试问题，并配以相应的参考答案（精简版），供大家参考。

希望独孤九剑秘籍的每一式都能让江湖中的英雄豪杰获益。

So，enjoy（与本文的BGM一起食用更佳哦）：

干货篇

----【目录先行】----

深度学习基础：

1. 反向传播算法（BP）的概念及简单推导

2. 分组卷积的相关知识

经典模型&&热门模型：

1. 目标检测中AP，AP50，AP75，mAP等指标的含义

2. YOLOv2中的anchor如何生成？

机器学习基础：

1. K-means算法逻辑？

2. K近邻算法逻辑？

数据结构&&算法：

1. 算法的时间复杂度和空间复杂度

2. 深度优先搜索(DFS)与广度优先搜索(BFS)的相关知识

Python/C/C++知识：

1. Python中如何进行异常处理？

2. Python中remove，del以及pop之间的区别？

3. C/C++中宏定义的相关知识

4. C/C++中typedef关键字的相关知识

模型部署：

1. ONNX的相关知识

2. TensorRT的相关知识

图像处理基础：

1. OpenCV读取图像的格式？

2. 中值滤波与均值滤波的相关概念

计算机基础：

1. 深度学习中常用的文件格式汇总

2. TCP和UDP的区别？

开放性问题：

1. 对一个零基础的CV算法学习者，有什么入门建议？

2. 对CV算法技术的发展前景的看法？

----【深度学习基础】----

【一】反向传播算法（BP）的概念及简单推导

反向传播（Backpropagation，BP）算法是一种与最优化方法（如梯度下降法）结合使用的，用来训练人工神经网络的常见算法。BP算法对网络中所有权重计算损失函数的梯度，并将梯度反馈给最优化方法，用来更新权值以最小化损失函数。该算法会先按前向传播方式计算（并缓存）每个节点的输出值，然后再按反向传播遍历图的方式计算损失函数值相对于每个参数的偏导数。

接下来我们以全连接层，使用sigmoid激活函数，Softmax+MSE作为损失函数的神经网络为例，推导BP算法逻辑。由于篇幅限制，这里只进行简单推导，后续Rocky将专门写一篇PB算法完整推导流程，大家敬请期待。

首先，我们看看sigmoid激活函数的表达式及其导数：

$$sigmoid表达式：\sigma (x)=\frac{1}{1+e^{-x}}$$
$$sigmoid导数：\frac{d}{dx}\sigma (x)=\sigma (x)-\sigma (x{)}^2=\sigma (1-\sigma )$$

可以看到sigmoid激活函数的导数最终可以表达为输出值的简单运算。

我们再看MSE损失函数的表达式及其导数：

$$MSE损失函数的表达式：L=\frac{1}{2}\sum _{k=1}^K(y_k-o_k{)}^2$$

其中$y_k$代表ground truth（gt）值，$o_k$代表网络输出值。

$$MSE损失函数的偏导：\frac{\partial L}{\partial o_i}=(o_i-y_i)$$

由于偏导数中单且仅当$k=i$时才会起作用，故进行了简化。

接下来我们看看全连接层输出的梯度：

$$MSE损失函数的表达式：L=\frac{1}{2}\sum _{i=1}^K(o_i^1-t_i{)}^2$$

$$MSE损失函数的偏导：\frac{\partial L}{\partial w_{jk}}=(o_k-t_k)o_k(1-o_k)x_j$$

我们用${\delta }_k=(o_k-t_k)o_k(1-o_k)$，则能再次简化：

$$MSE损失函数的偏导：\frac{dL}{d{w}_{jk}}={\delta }_k{x}_j$$

最后，我们看看那PB算法中每一层的偏导数：

输出层：
$$\frac{\partial L}{\partial w_{jk}}={\delta }_k^K{o}_j$$
$${\delta }_k^K=(o_k-t_k)o_k(1-o_k)$$

倒数第二层：
$$\frac{\partial L}{\partial w_{ij}}={\delta }_j^J{o}_i$$
$${\delta }_j^J=o_j(1-o_j)\sum _k{\delta }_k^K{w}_{jk}$$

倒数第三层：
$$\frac{\partial L}{\partial w_{ni}}={\delta }_i^I{o}_n$$
$${\delta }_i^I=o_i(1-o_i)\sum _j{\delta }_j^J{w}_{ij}$$

像这样依次往回推导，再通过梯度下降算法迭代优化网络参数，即可走完PB算法逻辑。

【二】分组卷积的相关知识

分组卷积（Group Convolution）最早出现在AlexNet网络中，分组卷积被用来切分网络，使其能在多个GPU上并行运行。

普通卷积进行运算的时候，如果输入feature map尺寸是$C\times H\times W$，卷积核有N个，那么输出的feature map与卷积核的数量相同也是N个，每个卷积核的尺寸为$C\times K\times K$，N个卷积核的总参数量为$N\times C\times K\times K$。

分组卷积的主要对输入的feature map进行分组，然后每组分别进行卷积。如果输入feature map尺寸是$C\times H\times W$，输出feature map的数量为$N$个，如果我们设定要分成G个group，则每组的输入feature map数量为$\frac{C}{G}$，则每组的输出feature map数量为$\frac{N}{G}$，每个卷积核的尺寸为$\frac{C}{G}\times K\times K$，卷积核的总数仍为N个，每组的卷积核数量为$\frac{N}{G}$，卷积核只与其同组的输入map进行卷积，卷积核的总参数量为$N\times \frac{C}{G}\times K\times K$，易得总的参数量减少为原来的$\frac{1}{G}$。

分组卷积的作用:

1. 分组卷积可以减少参数量。
2. 分组卷积可以看成是稀疏操作，有时可以在较少参数量的情况下获得更好的效果（相当于正则化操作）。
3. 当分组数量等于输入feature map通道数量，输出feature map数量也等于输入feature map数量时，分组卷积就成了Depthwise卷积，可以使参数量进一步缩减。

----【经典模型&&热门模型】----

【一】目标检测中AP，AP50，AP75，mAP等指标的含义

AP：PR曲线下的面积。

AP50: 固定IoU为50%时的AP值。

AP75:固定IoU为75%时的AP值。

AP@[0.5:0.95]:把IoU的值从50%到95%每隔5%进行了一次划分，并对这10组AP值取平均。

mAP：对所有的类别进行AP的计算，然后取均值。

mAP@[.5:.95]（即mAP@[.5,.95]）：表示在不同IoU阈值（从0.5到0.95，步长0.05）（0.5、0.55、0.6、0.65、0.7、0.75、0.8、0.85、0.9、0.95）上的平均mAP。

【二】YOLOv2中的anchor如何生成？

YOLOv2中引入K-means算法进行anchor的生成，可以自动找到更好的anchor宽高的值用于模型训练的初始化。

但如果使用经典K-means中的欧氏距离作为度量，意味着较大的Anchor会比较小的Anchor产生更大的误差，聚类结果可能会偏离。

由于目标检测中主要关心anchor与ground true box（gt box）的IOU，不关心两者的大小。因此，使用IOU作为度量更加合适，即提高IOU值。因此YOLOv2采用IOU值为评判标准：

$$d(gtbox,anchor)=1-IOU(gtbox,anchor)$$

具体anchor生成步骤与经典K-means大致相同，在下一个章节中会详细介绍。主要的不同是使用的度量是$d(gtbox,anchor)$，并将anchor作为簇的中心。

----【机器学习基础】----

【一】K-means算法逻辑？

K-means算法是一个实用的无监督聚类算法，其聚类逻辑依托欧式距离，当两个目标的距离越近，相似度越大。对于给定的样本集，按照样本之间的距离大小，将样本集划分为$K$个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。

K-means的主要算法步骤：

1. 选择初始化的$k$个样本作为初始聚类中心 D = { D 1 , D 2 , D 3 , . . . , D k } D = \{ D_{1}, D_{2}, D_{3}, ..., D_{k} \} D={D1​,D2​,D3​,...,Dk​}。
2. 针对数据集中每个样本$x_i$，计算它到$k$个聚类中心的距离并将其分到距离最小的聚类中心所对应的类中.
3. 针对每个类别$D_j$，重新计算它的聚类中心$D_j=\frac{1}{|c_j|}{\sum }_{x\in c_j}x$。（即属于该类的所有样本的质心）；
4. 重复上面2和3两步的操作，直到达到设定的中止条件（迭代次数、最小误差变化等）。

K-Means的主要优点：

1. 原理简单，实现容易，收敛速度快。
2. 聚类效果较优。
3. 算法的可解释度比较强。
4. 主要需要调参的参数仅仅是簇数k。

K-Means的主要缺点：

1. K值需要人为设定，不好把握。
2. 对初始的簇中心敏感，不同选取方式会得到不同结果。
3. 对于不是凸的数据集比较难收敛。
4. 如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳。
5. 迭代结果只是局部最优。
6. 对噪音和异常点比较的敏感。

【二】K近邻算法逻辑？

K近邻（K-NN）算法计算不同数据特征值之间的距离进行分类。存在一个样本数据集合，也称作训练数据集，并且数据集中每个数据都存在标签，即我们知道每一个数据与所属分类的映射关系。接着输入没有标签的新数据后，在训练数据集中找到与该新数据最邻近的K个数据，然后提取这K个数据中占多数的标签作为新数据的标签（少数服从多数逻辑）。

K近邻算法的主要步骤：

1. 计算新数据与各个训练数据之间的距离。
2. 按照距离的递增关系进行排序。
3. 选取距离最小的K个点。
4. 确定前K个点所在类别的出现频率。
5. 返回前K个点中出现频率最高的类别作为新数据的预测分类。

K近邻算法的结果很大程度取决于K的选择。其距离计算一般使用欧氏距离或曼哈顿距离等经典距离度量。

K近邻算法的主要优点：

1. 理论成熟，思想简单，既可以用来做分类又可以做回归。
2. 可以用于非线性分类。
3. 对数据没有假设，准确度高，对异常点不敏感。
4. 比较适用于数据量比较大的场景，而那些数据量比较小的场景采用K近邻算法算法比较容易产生误分类情况。

K近邻算法的主要缺点：

1. 计算复杂性高；空间复杂性高。
2. 样本不平衡的时候，对稀有类别的预测准确率低。
3. 是慵懒散学习方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢。
4. 可解释性不强。

----【数据结构&&算法】----

【一】算法的时间复杂度和空间复杂度

通常我们主要从空间复杂度和时间复杂度两个方面来衡量不同算法的性能区别。

时间复杂度：表述执行当前算法所消耗的时间。

空间复杂度：表述执行当前算法需要占用多少内存空间。

在工业界中，常常是算法的时间和空间不可兼得，我们需要根据实际场景来进行平衡。

我们可以用大O符号表示法来对算法进行时间复杂度和空间复杂度的估算：

时间复杂度：

常数阶$O(1)$，无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是$O(1)$，如：

i = 2
j = 6
i += 6
j += 2
WeThinkIn = i + j
1
2
3
4
5

线性阶$O(n)$，例如代码中有for循环等循环逻辑使得部分代码重复执行$n$遍，那么它消耗的时间是随着$n$的变化而变化的：

WeThinkIn = 1
for i in range(n):
   WeThinkIn += i
1
2
3

对数阶$O(logN)$，🌰如下所示：

i = 1
while i < n:
    i *= 2
1
2
3

像这样while循环里每次都乘$2$，$i$距离$n$就会越来越近，最后大于等于$n$了。此时我们可以算$2^x=n$从而推出$x=\log (N)$。

线性对数阶$O(nlog(N))$就是将时间复杂度为$O(logn)$的代码循环$n$遍的话，那么它的时间复杂度就是$O(nlogN)$。

for m in range(n):
    i = 1
    while i < n:
        i *= 2
1
2
3
4

平方阶$O(n^2)$可以理解成包含两个循环的代码：

for i in range(n):
   for j in range(n):
       x = 1
       y = 1
1
2
3
4

空间复杂度

常数复杂度$O(1)$，如果算法执行所需要的临时空间不随着某个变量$n$的大小而变化，即此算法空间复杂度为一个常量，可表示为$O(1)$。

i = 2
j = 6
i += 6
j += 2
WeThinkIn = i + j
1
2
3
4
5

线性阶复杂度$O(n)$，如果在代码中开了额外空间如数组、队列、栈等，就会消耗内存空间。

【二】深度优先搜索(DFS)与广度优先搜索(BFS)的相关知识

DFS（深度优先搜索）

深度优先搜索的主要步骤：

1. 递归下去。
2. 回溯上来。

深度优先则是以深度为准则，先一条路走到底，即为递归下去。如果没有递归时没有达到目标又无路可走了，那么则退回到上一步的状态，走其他路。即为回溯上来。

DFS的重要点在于状态回溯。

BFS（广度优先搜索）

比起深度优先搜索的一条路走到黑，广度优先搜索在面临一个路口时，把所有的岔路口都记下来，然后选择其中一个进入，然后将它的分路情况记录下来，然后再返回来进入另外一个岔路，并重复这样的操作。

BFS的重点在于状态的选取和标记。

DFS和BFS的总结

DFS用递归的形式，用到了栈结构，先进后出。BDS选取状态用队列的形式，先进先出。

DFS的复杂度与BFS的复杂度基本一致，不同之处在于遍历的方式与看待问题的出发点不同，DFS适合目标明确的任务，而BFS适合大范围的搜索。

从算法思想上来说都是穷举所有的情况。

----【Python/C/C++知识】----

【一】Python中如何进行异常处理？

一般情况下，在Python无法正常处理程序时就会发生一个异常。异常在Python中是一个对象，表示一个错误。当Python脚本发生异常时我们需要捕获处理它，否则程序会终止执行。

捕捉异常可以使用try，except和finally语句。

try和except语句用来检测try语句块中的错误，从而让except语句捕获异常信息并处理。

try:
    6688 / 0
except:
    '''异常的父类，可以捕获所有的异常'''
    print "0不能被除"
else:
    '''保护不抛出异常的代码'''
    print "没有异常"
finally:
    print "最后总是要执行我"
1
2
3
4
5
6
7
8
9
10

【二】Python中remove，del以及pop之间的区别？

remove，del以及pop都可以用于删除列表、字符串等里面的元素，但是具体用法并不相同。

1. remove是剔除第一个匹配的值。
2. del是通过索引来删除当中的元素。
3. pop是通过索引来删除当中的元素，并且返回该元素；若括号内不添加索引值，则默认删除最后一个元素。

>>> a = [0, 1, 2, 1, 3] 
>>> a.remove(1) 
>>> a 
[0, 2, 1, 3] 

>>> a = [0, 1, 2, 1, 3] 
>>> del a[1] 
[0, 2, 1, 3] 

>>> a = [0, 1, 2, 1, 3] 
>>> a.pop(1) 
1 
>>> a 
[0, 2, 1, 3] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

【三】C/C++中宏定义的相关知识

宏定义可以把一个名称指定成任何一个文本。在完成宏定义后，无论宏名称出现在源代码的何处，预处理器都会将其替换成指定的文本。

//define 宏名 文本
#define WeThinkIn 666688889999

//define 宏名(参数) 文本
#define R(a,b) (a/b)
//注：带参数的宏替换最好在表达式整体上加括号，避免结果受其他运算影响。
1
2
3
4
5
6

宏定义的优点：

1. 方便程序修改，如果一个常量在程序中大量使用，我们可以使用宏定义为其设置一个标识符。当我们想修改这个常量时，直接修改宏定义处即可，不必在程序中海量寻找所有相关位置。
2. 提高程序的运行效率，使用带参数的宏定义可以完成函数的功能，但同时又比函数节省系统开销，提升程序运行效率。（无需调用函数这个流程）

宏定义和函数的区别：

1. 宏在预处理阶段完成替换，之后替换的文本参与编译，相当于是恒等代换过程，运行时不存在函数调用，执行起来更快；而函数调用在运行时需要跳转到具体调用函数。
2. 宏定义没有返回值；函数调用具有返回值。
3. 宏定义参数没有类型，不进行类型检查；函数参数具有类型，需要检查类型。
4. 宏定义不是说明或者语句，结尾不用加分号。
5. 宏定义必须写在函数之外，其作用域为宏定义命令起到源程序结束。如要终止其作用域可使用# undef命令；而函数作用域在函数调用处。

【四】C/C++中typedef关键字的相关知识

我们可以使用typedef关键字来定义自己习惯的数据类型名称，来替代系统默认的基本类型名称以及其他类型等名称。

在工业界中，我们一般在如下两个场景中会见到typedef的身影。

// 1.为基本数据类型定义新的类型名
typedef unsigned int WeThinkIn_int;
typedef char* WeThinkIn_point;
  
// 2.为自定义数据类型（结构体、共用体和枚举类型）定义简洁的类型名称
typedef struct target_Object
{
    int x;
    int y;
} WeThinkIn_Object;
1
2
3
4
5
6
7
8
9
10

typedef与宏定义的区别：

1. 宏主要用于定义常量及书写复杂的内容；typedef主要用于定义类型别名。
2. 宏替换发生在预处理阶段，属于文本恒等替换；typedef是编译中发挥作用。
3. 宏定义参数没有类型，不进行类型检查；typedef参数具有类型，需要检查类型。
4. 宏不是语句，不用在最后加分号；typedef是语句，要加分号标识结束。
5. 注意对指针的操作，typedef char * p_char和#define p_char char *区别巨大。

----【模型部署】----

【一】ONNX的相关知识

ONNX是一种神经网络模型的框架，其最经典的作用是作为不同框架之间的中间件，成为模型表达的一个通用架构，来增加不同框架之间的交互性。

ONNX的优势：

1. ONNX的模型格式有极佳的细粒度。
2. ONNX是模型表达的一个通用架构，主流框架都可以兼容。
3. ONNX可以实现不同框架之间的互相转化。

【二】TensorRT的相关知识

TensorRT是一个高性能的深度学习前向Inference的优化器和运行的引擎。

TensorRT的核心：将现有的模型编译成一个engine，类似于C++的编译过程。在编译engine过程中，会为每一层的计算操作找寻最优的算子方法，将模型结构和参数以及相应kernel计算方法都编译成一个二进制engine，因此在部署之后大大加快了推理速度。

我们需要给TensorRT填充模型结构和参数，也就是解析我们自己的模型结构和参数文件，获取数据放到其中。官方给了三种主流框架模型格式的解析器（parser），分别是：ONNX，Caffe以及TensorFlow。

TensorRT的优势：

1. 把一些网络层进行了合并。具体🌰如下图所示。
2. 取消一些不必要的操作。比如不用专门做concat的操作等。
3. TensorRT会针对不同的硬件都相应的优化，得到优化后的engine。
4. TensorRT支持INT8和FP16的计算，通过在减少计算量和保持精度之间达到一个理想的trade-off。

----【图像处理基础】----

【一】OpenCV读取图像的格式？

通常其他图像读取函数读取图片的时候是按RGB格式读取，但在OpenCV在读取图片时，是按BGR读取的。

【二】中值滤波与均值滤波的相关概念

均值滤波也称为线性滤波，其采用的主要方法为邻域平均法。线性滤波的基本原理是用均值代替原图像中的各个像素值，即对待处理的当前像素点$(x,y)$，选择一个模板，该模板由其近邻的若干像素组成，求模板中所有像素的均值，再把该均值赋予当前像素点$(x,y)$，作为处理后图像在该点上的灰度值$g(x,y)$，即$g(x,y)=\frac{1}{m}\Sigma f(x,y)$， $m$为该模板中包含当前像素在内的像素总个数。这样的方法可以平滑图像，速度快，算法简单。但是无法去掉噪声，但能微弱的减弱它。

中值滤波是一种非线性平滑技术，它将每一像素点的灰度值设置为该点某邻域窗口内的所有像素点灰度值的中值。具体实现过程如下：

1. 通过从图像中的某个采样窗口取出奇数个数据进行排序。
2. 用排序后的中值作为当前像素点的灰度值。
3. 在图像处理中，中值滤波常用来保护边缘信息，是经典的平滑噪声的方法，该方法法对消除椒盐噪音非常有效，在光学测量条纹图象的相位分析处理方法中有特殊作用，但在条纹中心分析方法中作用不大。

----【计算机基础】----

【一】深度学习中常用的文件格式汇总

1. csv：可用于方便的存储数据与标签。
2. txt：最常见的文件格式，可用于存储数据路径与数据label。
3. Json：是一种轻量级的数据交换格式，常用于保存数据label。
4. Yaml：是一种数据序列化语言，通常用于编写配置文件，比如将网络模型配置参数与训练参数解耦至Yaml文件中，方便训练与优化。
5. Cfg：Darknet中经典的保存网络模型结构的文件格式。
6. Protobuf：是一个高效的结构化数据存储格式，可以存储神经网络的权重信息，在caffe中经常出现它的身影。

【二】TCP和UDP的区别？

1. TCP面向连接，UDP是无连接的；
2. TCP提供可靠的服务，也就是说，通过TCP连接传送的数据，无差错，不丢失，不重复，且按序到达；UDP尽最大努力交付，即不保证可靠交付；
3. TCP的逻辑通信信道是全双工的可靠信道；UDP则是不可靠信道；
4. 每一条TCP连接只能是点到点的；UDP支持一对一，一对多，多对一和多对多的交互通信；
5. TCP面向字节流（可能出现黏包问题），本质上是TCP把数据看成一连串无结构的字节流；UDP是面向报文的（不会出现黏包问题）；
6. UDP没有拥塞控制，因此网络出现拥塞不会使源主机的发送速率降低（对实时应用很有用，如IP电话，实时视频会议等）；
7. TCP首部开销20字节；UDP的首部开销小，只需8个字节。

----【开放性问题】----

这些问题基于我的思考提出，希望除了能给大家带来面试的思考，也能给大家带来面试以外的思考。这些问题没有标准答案，我相信每个人心中都有自己灵光一现的创造，你的呢？

【一】对一个零基础的CV算法学习者，有什么入门建议？

这是一个非常好的问题，既可以反映出面试者自身的CV学习入场逻辑，也能反映出面试者对于自己的学习过程是否有总结与提炼。

【二】对CV算法技术的发展前景的看法？

我觉得这个问题可以从我经常提到的业务侧，竞赛侧，研究侧三个维度去思考和表达。在不同维度下，CV算法技术的发展前景会更加真实的体现，我们也能更从容地去表述我们的观点。

精致的结尾

最后，感谢大家读完这篇文章，希望能给大家带来帮助～后续Rocky会持续撰写“三年面试五年模拟”之独孤九剑的系列文章，大家敬请期待！

Rocky也一直在运营技术交流群（WeThinkIn-技术交流群），这个群的初心主要聚焦于技术话题的讨论与学习，包括但不限于CV算法，算法，开发，IT技术等。群里有很多人工智能行业的大牛，欢迎大家入群一起学习交流～（请添加小助手微信USTB-Rocky，拉你进群～）