pa-prepare | In Web3 | Truth

数据结构与算法

快排

算法描述

先从序列中取出一个数作为基准数
分区过程, 将比这个数大的数全部放到它的右边, 小于或等于它的数全部放到它的左边
再对左右区间重复第二步, 直到各区间只有一个数

算法时间复杂度分析

$$T(n) = 2T(\frac{n}{2}) + f(n)$$
假设m次递归后结束，则
$$T(n) = 2^{m}T(1)+mn$$
$$n = 2^{m}T(1)$$
由于T(1)是常量，所以
$$n = 2^{m}, m = log(n)$$
得到
$$T(n) = nT(1) + nlog(n)$$

因为n>2时，nlog(n) > n，所以快排最优情况下的时间复杂度是
$$O(nlogn)$$

def quick_sort(array, l, r):
    if l < r:
        q = partition(array, l, r)
        quick_sort(array, l, q-1)
        quick_sort(array, q+1, r)

# partition algorithm
def partition(array, l, r):
    x = array[r]
    i = l - 1
    for j in range(l, r):
        if array[j] <= x:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i+1], array[r] = array[r], array[i+1]
    return i + 1

二分查找

原数组必须是有序的

def binary_search(array, num):
    left = 0
    right = len(array) - 1
    while left <= right:
        mid = (left + right) // 2
        if num < array[mid]:
            right = mid - 1
        elif num > array[mid]:
            left = mid + 1
        else:
            return mid
    return -1

最大堆和最小堆，一般求无序数组中最大(小)的K个数

计算机视觉图形学基础

图像本身就是一个函数

low-level feature
- 图片锐化，拉普拉斯
- 边缘检测，sobel
- 图片模糊，中值滤波/高斯滤波
- 图像二值化，灰度图
- 图像resize，插值（临近插值，双线性插值）

机器学习

Logistic regression
SVM
- 首先它是一个二类分类器，核心思想是在特征空间中寻找间隔最大化的分离超平面的线性分类器。
  - 当训练样本线性可分时，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机；
  - 当训练数据近似线性可分时，引入松弛变量，通过软间隔最大化，学习一个线性分类器，即线性支持向量机；
  - 当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。
- SVM 核函数之间的区别
  - 一般选择线性核和高斯核，也就是线性核与 RBF 核。线性核：主要用于线性可分的情形，参数少，速度快，对于一般数据，分类效果已经很理想了。 RBF 核：主要用于线性不可分的情形，参数多，分类结果非常依赖于参数。有很多人是通过训练数据的交叉验证来寻找合适的参数，不过这个过程比较耗时。如果 Feature 的数量很大，跟样本数量差不多，这时候选用线性核的 SVM。如果 Feature 的数量比较小，样本数量一般，不算大也不算小，选用高斯核的 SVM。
PCA
Kmeans
- K-means的基本算法流程：
  1. 初始化$k$个聚类中心$c1,c2,…,ck$
  2. 对于每个样本$x_i$和每个聚类中心$c_j$，计算样本与聚类中心之间的距离$d_{ij}$
  3. 对于每个样本$x_i$，基于其最小的$d_{ij}$把其分配到第$j$个类$C_j$
  4. 对于每个类$C_j$，计算其所有样本的均值作为新的聚类中心，重复步骤2和步骤3直至样本点所属的类不再变化或达到最大迭代次数
L1和L2 regulation
- 从参数W更新，即求梯度的角度来看，
- L1是在原来式子上加多了一个$-\eta\frac{\lambda sgn(W)}{n}$
- 上式可知，当w大于0时，更新的参数w变小；当w小于0时，更新的参数w变大；所以，L1正则化容易使参数变为0，即特征稀疏化。
- L2是在原来式子上加多了一个$-\eta\frac{\lambda}{n}W$
- 上式可知，当w趋向于0时，参数减小的非常缓慢，因此L2正则化使参数减小到很小的范围，但不为0。
- L1使权重稀疏，L2使权重平滑，一句话总结就是：L1会趋向于产生少量的特征，而其他的特征都是0，而L2会选择更多的特征，这些特征都会接近于0

深度学习

基础网络
1. VGG
  - 1*1
  - 多个小卷积代替一个大的卷积
  - 网络更深
2. Inception
  - 网络更宽
  - 让网络自己选择合适的卷积核
3. ResNet
  - 解决网络加深时难以训练的问题
  - skip connection，计算残差
  - 总结：
  - Inception V1——构建了1x1、3x3、5x5的 conv 和3x3的 pooling 的分支网络，同时使用 MLPConv 和全局平均池化，扩宽卷积层网络宽度，增加了网络对尺度的适应性；
  - Inception V2——提出了 Batch Normalization，代替 Dropout 和 LRN，其正则化的效果让大型卷积网络的训练速度加快很多倍，同时收敛后的分类准确率也可以得到大幅提高，同时学习 VGG 使用两个3´3的卷积核代替5´5的卷积核，在降低参数量同时提高网络学习能力；
  - Inception V3——引入了 Factorization，将一个较大的二维卷积拆成两个较小的一维卷积，比如将3´3卷积拆成1´3卷积和3´1卷积，一方面节约了大量参数，加速运算并减轻了过拟合，同时增加了一层非线性扩展模型表达能力，除了在 Inception Module 中使用分支，还在分支中使用了分支（Network In Network In Network）；
  - Inception V4——研究了 Inception Module 结合 Residual Connection，结合 ResNet 可以极大地加速训练，同时极大提升性能，在构建 Inception-ResNet 网络同时，还设计了一个更深更优化的 Inception v4 模型，能达到相媲美的性能。
  - 原文链接
4. 1×1卷积的作用
  - 增加非线性, 实现跨通道的交互和信息整合
  - 进行卷积核通道数的降维和升维
目标检测
1. RCNN-series
2. Yolo-series
3. SSD
4. 目标检测的一些发展趋势
5. 在目标检测算法中，two stage的算法比one stage在检测小物体上更有效，此说法同意吗，为什么？
  - 基本上同意这个说法。
  - 要说明这个问题主要从感受野的角度去看，one stage的方法，对于SSD，其采取多个特征图进行分类，但由于依赖网络中比较深的层（特征图），感受野很大，因而小物体检测不准确。同样，对于Yolo，由于在方法设计中就把原图分块，即设定了最后用于判断的特征图尺寸，其感受野也很大，因而对小物体判断也不准确。
  - 相对于one stage方法要求同时分离前景和背景以及做出分类，two stage的方法由于proposal的存在可以先用简单的结构分出前景和背景（此时感受野小，特征图分辨率高），再通过深层网络做进一步分类和精修，提高准确率。
  - one stage的方法也有针对这个问题进行过优化，SSD增加相对不那么深的特征图层作判断，以减小感受野增加分辨率，但层数不深的特征图的判别能力有限，无法大幅增加准确率；Yolo v3增加了FPN，用多尺度特征来判断，增加了对小物体判别能力；RetinaNet也是one stage方法，用了FPN判别，此处对小物体检测更有效，另外其设计了focal loss的训练方式，此方式可认为把two stage中proposal达到的正负样本平衡以修改损失函数的方式达到类似效果，提高了训练效率和整体的准确率。
6. MAP，mean average precision
  - Precision & Recall
    1. 预测为Positive当中真正是Positivede比例
      $$Precision = \frac{TP}{TP+FP}=\frac{TP}{all-detections}$$
    2. 实际为Postivie当中被预测为Positive的比例
      $$Recall = \frac{TP}{TP+FN}=\frac{TP}{all-ground-truths}$$
  - mAP的步骤
    1. 对于某个类别$C$，在某一张图片上，首先计算$C$在一张图片上的$Precision$:
    - $$Precision = 在一张图片上类别C识别正确的个数（也就是IoU>0.5）/ 一张图片上类别C的总个数}$$
    1. 依然对于某个类别$C$，可能在多张图片上有该类别，下面计算类别C的AP指数：
    - $$AP = 每张图片上的Precision求和 / 含有类别C的图片数目$$
    1. 对于整个数据集，存在多个类别$C1、C2、C3$：
    - $$mAP = 上一步计算的所有类别的AP和 / 总的类别数目$$
    - 相当于所有类别的AP的平均值