DeepIndeed's Blog!

• Detection算法Overview

  2019-07-14

  blog

  detection  CV算法
  • 物体检测算法概述
    • R-CNN的前世
  • 基于region proposals的方法（Two-Stage方法）
    • RCNN
      • 主要工作流程
      • RCNN的缺点
      • 优化思路
    • SPP net
      • SPP-NET的主要思想
      • 相对于R-CNN，SPP-net的优势
    • Fast RCNN
      • 算法框架图
      • 优点&贡献
      • 小结
    • Faster RCNN
      • Faster RCNN算法框架
      • 参考链接
    • FPN(feature pyramid networks for object detection)
      • 图像金字塔
      • 论文概述：
      • 小结
    • Mask-RCNN
    • Mask Scoring R-CNN
  • One-stage方法
    • SSD原理与实现
    • CornerNet 人体姿态检测
    • RPN中的Anchor
    • 目标检测算法研究问题小结
  • 目标检测特殊层
    • ROIpooling
      • 缺点：由于两次量化带来的误差；
      • 案例说明
    • ROI Align
    • NMS算法优化的必要性
      • NMS算法的功能
      • 从R-CNN到SPPNet
        • Faster RCNN
      • SSD
      • 注意
      • 参考文献
    • one-stage和two-stage的anchor-base detection
      • 为什么one-stage网络速度要快很多？
      • 为什么one-stage网络的准确性要比two-stage网络要低？
      • 那么什么情况下背景anchor不会拉低这个准确率呢？
      • 解决one-stage网络背景anchor过多导致的不均衡问题方案
      • 四步交替训练Faster RCNN
    • Faster-RCNN和YOLO的anchor有什么区别

  物体检测算法概述

  深度学习让物体检测从实验室走到生活。基于深度学习的物体检测算法分类两大类。一类是像RCNN类似的两stage方法，将ROI的选择和对ROI的分类score过程。 另外一类是类似YOLO将ROI的选择和最终打分实现端到端一步完成。前者是先由算法生成一系列作为样本的候选框，再通过卷积神经网络进行样本分类；后者则不用产生候选框，直接将目标边框定位的问题转化为回归问题处理。正是由于两种方法的差异，在性能上也有不同，前者在检测准确率和定位精度上占优，后者在算法速度上占优。

  

  各种检测算法之间的性能对比，准确率，速度，以及一些可能加速的tips

  R-CNN的前世

  • HOG
  • DPM
  • Selective Search
  • 深度学习应用到物体检测以前

  基于region proposals的方法（Two-Stage方法）

  • RCNN => Fast RCNN => Faster RCNN => FPN

  RCNN

  在早期深度学习技术发展进程中，主要都是围绕分类问题展开研究，这是因为神经网络特有的结构输出将概率统计和分类问题结合，提供一种直观易行的思路。国内外研究人员虽然也在致力于将其他如目标检测领域和深度学习结合，但都没有取得成效，这种情况直到R-CNN算法出现才得以解决。

  • 论文链接：https://arxiv.org/pdf/1311.2524.pdf
  • 作者：Ross Girshick Jeff Donahue Trevor Darrell Jitendra Malik 之前的视觉任务大多数考虑使用SIFT和HOG特征，而近年来CNN和ImageNet的出现使得图像分类问题取得重大突破，那么这方面的成功能否迁移到PASCAL VOC的目标检测任务上呢？基于这个问题，论文提出了R-CNN。 R-CNN (Region-based CNN features) 性能：RCNN在VOC2007上的mAP是58%左右。

  主要工作流程

  R-CNN要完成目标定位，其流程主要分为四步：

  • 输入图像
  • 利用选择性搜索(Selective Search)这样的区域生成算法提取Region Proposal 提案区域(2000个左右)
  • 将每个Region Proposal分别resize(因为训练好的CNN输入是固定的)后(也即下图中的warped region，文章中是归一化为227×227)作为CNN网络的输入。
  • CNN网络提取到经过resize的region proposal的特征送入每一类的SVM分类器，判断是否属于该类

  RCNN的缺点

  • 对于提取的每个Region Proposal，多数都是互相重叠，重叠部分会被多次重复提取feature)，都要分别进行CNN前向传播一次(相当于进行了2000吃提特征和SVM分类的过程)，计算量较大。
  • CNN的模型确定的情况下只能接受固定大小的输入(也即wraped region的大小固定)

  优化思路

  既然所有的Region Proposal都在输入图像中，与其提取后分别作为CNN的输入，为什么不考虑将带有Region Proposal的原图像直接作为CNN的输入呢？原图像在经过CNN的卷积层得到feature map，原图像中的Region Proposal经过特征映射(也即CNN的卷积下采样等操作)也与feature map中的一块儿区域相对应。

  SPP net

  • 论文链接：]https://arxiv.org/abs/1406.4729
  • 作者：Kaiming He, Xiangyu Zhang, Shaoqing Ren, Jian Sun 简述：SPP net中Region Proposal仍然是在原始输入图像中选取的，不过是通过CNN映射到了feature map中的一片区域。

  SPP-NET的主要思想

  

  • 对卷积层的feature map上的Region Proposal映射区域分别划分成1×1，2×2，4×4的窗口(window)，
  • 在每个窗口内做max pooling，这样对于一个卷积核产生的feature map，就可以由SPP得到一个(1×1+2×2+4×4)维的特征向量。
  • 论文中采用的网络结构最后一层卷积层共有256个卷积核，所以最后会得到一个固定维度的特征向量(1×1+2×2+4×4)×256维)，并用此特征向量作为全连接层的输入后做分类。

  相对于R-CNN，SPP-net的优势

  • 使用原始图像作为CNN网络的输入来计算feature map(R-CNN中是每个Region Proposal都要经历一次CNN计算)，大大减少了计算量。
  • RCNN要resize，易于失真，而SPP-net不需要，原因是，SPP net中Region Proposal仍然是通过选择性搜索等算法在输入图像中生成的，通过映射的方式得到feature map中对应的区域，并对Region Proposal在feature map中对应区域做空间金字塔池化。通过空间金字塔池化操作，对于任意尺寸的候选区域，经过SPP后都会得到固定长度的特征向量。

  Fast RCNN

  • Fast R-CNN
  • 作者：Ross Girshick 性能：在VOC2007上的mAP也提高到了68%

  算法框架图

  

  优点&贡献

  • Fast R-CNN引入了RoI 池化层(相当于是一层SPP)，对于图像中的Region Poposal(也即RoI)，通过映射关系(图中的RoI projection)可以得到feature map中Region Proposal对应的区域。
  • RoI Pooling层的操作是将feature map上的RoI区域划分为7×7的窗口，在每个窗口内进行max pooling，然后得到(7×7)×256的输出，最后连接到全连接层得到固定长度的RoI特征向量。
  • 前面得到的RoI特征向量再通过全连接层作为Softmax和Regressor的输入,训练过程可以更新所有的网络层
  • 训练过程是端到端的(Sigle-stage),并使用了一个多任务的损失函数(也即将边框回归直接加入到CNN网络中后,Fast R-CNN网络的损失函数包含了Softmax的损失和Regressor的损失)

  小结

  在前面三种目标检测框架中(R-CNN，SPP net，Fast R-CNN)，Region Proposal都是通过区域生成的算法(选择性搜索等)在原始输入图像中产生的，不过在SPP net及Fast R-CNN中都是输入图像中的Region Proposal通过映射关系映射到CNN中feature map上再操作的。Fast R-CNN中RoI池化的对象是输入图像中产生的proposal在feature map上的映射区域

  Faster RCNN

  • 论文链接：https://arxiv.org/pdf/1506.01497.pdf
  • 作者：Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun

  Faster RCNN算法框架

  我们先整体的介绍下上图中各层主要的功能

  • 卷积网络提取特征图：

  作为一种CNN网络目标检测方法，Faster RCNN首先使用一组基础的conv+relu+pooling层提取input image的feature maps,该feature maps会用于后续的RPN层和全连接层。

  • RPN(Region Proposal Networks,区域提议网络):

  RPN网络主要用于生成region proposals，

  • 首先生成一堆Anchor box，对其进行裁剪过滤后通过softmax判断anchors属于前景(foreground)或者后景(background)，即是物体or不是物体，所以这是一个二分类；
  • 另一分支bounding box regression修正anchor box，形成较精确的proposal（注：这里的较精确是相对于后面全连接层的再一次box regression而言）

  Feature Map进入RPN后，先经过一次$33$的卷积，同样，特征图大小依然是$6040$,数量512，这样做的目的应该是进一步集中特征信息，接着看到两个全卷积,即kernel_size=1*1,p=0,stride=1;

  • cls layer 逐像素对其9个Anchor box进行二分类
  • reg layer 逐像素得到其9个Anchor box四个坐标信息

  特征图大小为6040，所以会一共生成6040*9=21600个Anchor box

  

  • Roi Pooling：

  该层利用RPN生成的proposals和VGG16最后一层得到的feature map，得到固定大小的proposal feature map,进入到后面可利用全连接操作来进行目标识别和定位

  • Classifier：

  会将ROI Pooling层形成固定大小的feature map进行全连接操作，利用Softmax进行具体类别的分类，同时，利用SmoothL1Loss完成bounding box regression回归操作获得物体的精确位置。

  

  参考链接

  • [1]. https://www.cnblogs.com/wangyong/p/8513563.html
  • [2]. https://www.jianshu.com/p/00a6a6efd83d
  • [3]. https://www.cnblogs.com/liaohuiqiang/p/9740382.html
  • [4]. https://blog.csdn.net/u011436429/article/details/80414615
  • [5]. https://blog.csdn.net/xiaoye5606/article/details/71191429

  

  向RGB大神,He Kaiming致敬！

  FPN(feature pyramid networks for object detection)

  • 论文链接：https://arxiv.org/abs/1612.03144
  • poster链接： https://vision.cornell.edu/se3/wp-content/uploads/2017/07/fpn-poster.pdf
  • caffe实现: https://github.com/unsky/FPN
  • 作者：Tsung-Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, Serge Belongie

  图像金字塔

  图像金字塔,在很多的经典算法里面都有它的身影，比如SIFT、HOG等算法。 我们常用的是高斯金字塔，所谓的高斯金字塔是通过高斯平滑和亚采样获得 一些下采样图像，也就是说第K层高斯金字塔通过平滑、亚采样操作就可以 获得K+1层高斯图像，高斯金字塔包含了一系列低通滤波器，其截止频率从 上一层到下一层是以因子2逐渐增加，所以高斯金字塔可以跨越很大的频率范围。 总之，我们输入一张图片，我们可以获得多张不同尺度的图像，我们将这些 不同尺度的图像的4个顶点连接起来，就可以构造出一个类似真实金字塔的一 个图像金字塔。通过这个操作，我们可以为2维图像增加一个尺度维度（或者说是深度）， 这样我们可以从中获得更多的有用信息。整个过程类似于人眼看一个目标由远及近的 过程（近大远小原理）。

  

  论文概述：

  作者提出的多尺度的object detection算法：FPN（feature pyramid networks）。原来多数的object detection算法都是只采用顶层特征做预测，但我们知道低层的特征语义信息比较少，但是目标位置准确；高层的特征语义信息比较丰富，但是目标位置比较粗略。另外虽然也有些算法采用多尺度特征融合的方式，但是一般是采用融合后的特征做预测，而本文不一样的地方在于预测是在不同特征层独立进行的。

  

  前面已经提到了高斯金字塔，由于它可以在一定程度上面提高算法的性能， 因此很多经典的算法中都包含它。但是这些都是在传统的算法中使用，当然也可以将 这种方法直应用在深度神经网络上面，但是由于它需要大量的运算和大量的内存。 但是我们的特征金字塔可以在速度和准确率之间进行权衡，可以通过它获得更加鲁棒 的语义信息，这是其中的一个原因。

  

  如上图所示，我们可以看到我们的图像中存在不同尺寸的目标，而不同的目标具有不同的特征， 利用浅层的特征就可以将简单的目标的区分开来； 利用深层的特征可以将复杂的目标区分开来；这样我们就需要这样的一个特征金字塔来完成这件事。 图中我们在第1层（请看绿色标注）输出较大目标的实例分割结果， 在第2层输出次大目标的实例检测结果，在第3层输出较小目标的实例分割结果。 检测也是一样，我们会在第1层输出简单的目标，第2层输出较复杂的目标，第3层输出复杂的目标。

  小结

  作者提出的FPN（Feature Pyramid Network）算法同时利用低层特征高分辨率和高层特征的高语义信息，通过融合这些不同层的特征达到预测的效果。并且预测是在每个融合后的特征层上单独进行的，这和常规的特征融合方式不同。

  Mask-RCNN

  • 论文地址：https://arxiv.org/abs/1703.06870
  • 作者：Kaiming He，Georgia Gkioxari，Piotr Dollar，Ross Girshick
  • FAIR Detectron：https://github.com/facebookresearch/Detectron
  • tensorflow: https://github.com/matterport/Mask_RCNN

  Mask Scoring R-CNN

  • 论文地址：https://arxiv.org/abs/1903.00241
  • github: https://github.com/zjhuang22/maskscoring_rcnn

  

  One-stage方法

  以R-CNN算法为代表的two stage的方法由于RPN结构的存在，虽然检测精度越来越高，但是其速度却遇到瓶颈，比较难于满足部分场景实时性的需求。 因此出现一种基于回归方法的one stage的目标检测算法，不同于two stage的方法的分步训练共享检测结果，one stage的方法能实现完整单次 训练共享特征，且在保证一定准确率的前提下，速度得到极大提升。

  SSD原理与实现

  https://blog.csdn.net/u010712012/article/details/86555814 https://github.com/amdegroot/ssd.pytorch http://www.cs.unc.edu/~wliu/papers/ssd_eccv2016_slide.pdf

  CornerNet 人体姿态检测

  • paper出处：https://arxiv.org/abs/1808.01244
  • https://zhuanlan.zhihu.com/p/46505759

  RPN中的Anchor

  Anchor是RPN网络的核心。需要确定每个滑窗中心对应感受野内存在目标与否。由于目标大小和长宽比例不一，需要多个尺度的窗。Anchor即给出一个基准窗大小，按照倍数和长宽比例得到不同大小的窗。有了Anchor之后，才能通过Select Search的方法\Slide Windows方法进行选取ROI的。

  首先我们需要知道anchor的本质是什么，本质是SPP(spatial pyramid pooling)思想的逆向。而SPP本身是做什么的呢，就是将不同尺寸的输入resize成为相同尺寸的输出。所以SPP的逆向就是，将相同尺寸的输出，倒推得到不同尺寸的输入。

  接下来是anchor的窗口尺寸，这个不难理解，三个面积尺寸（128^2，256^2，512^2），然后在每个面积尺寸下，取三种不同的长宽比例（1:1,1:2,2:1）.这样一来，我们得到了一共9种面积尺寸各异的anchor。示意图如下： 至于这个anchor到底是怎么用的，这个是理解整个问题的关键。

  • Faster RCNN
  • SSD
  • YOLO
  • Guided Anchor: https://arxiv.org/abs/1901.03278

  目标检测算法研究问题小结

  目标检测领域的深度学习算法，需要进行目标定位和物体识别，算法相对来说还是很复杂的。当前各种新算法也是层不出穷，但模型之间有很强的延续性，大部分模型算法都是借鉴了前人的思想，站在巨人的肩膀上。我们需要知道经典模型的特点，这些tricks是为了解决什么问题，以及为什么解决了这些问题。这样才能举一反三，万变不离其宗。综合下来，目标检测领域主要的难点如下:

  • 检测速度：实时性要求高，故网络结构不能太复杂，参数不能太多，卷积层次也不能太多。
  • 位置准确率：(x y w h)参数必须准确，也就是检测框大小尺寸要匹配，且重合度IOU要高。SSD和faster RCNN通过多个bounding box来优化这个问题
  • 漏检率：必须尽量检测出所有目标物体，特别是靠的近的物体和尺寸小的物体。SSD和faster RCNN通过多个bounding box来优化这个问题
  • 物体宽高比例不常见：SSD通过不同尺寸feature map，yoloV2通过不同尺寸输入图片，来优化这个问题。
  • 靠的近的物体准确率低
  • 小尺寸物体准确率低：SSD取消全连接层，yoloV2增加pass through layer，采用高分辨率输入图片，来优化这个问题

  目标检测特殊层

  ROIpooling

  ROIs Pooling顾名思义，是Pooling层的一种，而且是针对RoIs的Pooling，他的特点是输入特征图尺寸不固定，但是输出特征图尺寸固定；

  ROI是Region of Interest的简写，指的是在“特征图上的框”;

  • 在Fast RCNN中， RoI是指Selective Search完成后得到的“候选框”在特征图上的映射，如下图中的红色框所示；
  • 在Faster RCNN中，候选框是经过RPN产生的，然后再把各个“候选框”映射到特征图上，得到RoIs。

  

  参考faster rcnn中的ROI Pool层，功能是将不同size的ROI区域映射到固定大小的feature map上。

  缺点：由于两次量化带来的误差；

  • 将候选框边界量化为整数点坐标值。
  • 将量化后的边界区域平均分割成$k\times k$个单元(bin),对每一个单元的边界进行量化。

  案例说明

  下面我们用直观的例子具体分析一下上述区域不匹配问题。如 图1 所示，这是一个Faster-RCNN检测框架。输入一张$800\times 800$的图片，图片上有一个$665\times 665$的包围框(框着一只狗)。图片经过主干网络提取特征后，特征图缩放步长（stride）为32。因此，图像和包围框的边长都是输入时的1/32。800正好可以被32整除变为25。但665除以32以后得到20.78，带有小数，于是ROI Pooling 直接将它量化成20。接下来需要把框内的特征池化$7\times7$的大小，因此将上述包围框平均分割成$7\times7$个矩形区域。显然，每个矩形区域的边长为2.86，又含有小数。于是ROI Pooling 再次把它量化到2。经过这两次量化，候选区域已经出现了较明显的偏差（如图中绿色部分所示）。更重要的是，该层特征图上0.1个像素的偏差，缩放到原图就是3.2个像素。那么0.8的偏差，在原图上就是接近30个像素点的差别，这一差别不容小觑。

  caffe中实现roi_pooling_layer.cpp

  template <typename Dtype>
  void ROIPoolingLayer<Dtype>::Forward_cpu(const vector<Blob<Dtype>*>& bottom,
        const vector<Blob<Dtype>*>& top) {
    //输入有两部分组成，data和rois
    const Dtype* bottom_data = bottom[0]->cpu_data();
    const Dtype* bottom_rois = bottom[1]->cpu_data();
    // ROIs的个数
    int num_rois = bottom[1]->num();
    int batch_size = bottom[0]->num();
    int top_count = top[0]->count();
    Dtype* top_data = top[0]->mutable_cpu_data();
    caffe_set(top_count, Dtype(-FLT_MAX), top_data);
    int* argmax_data = max_idx_.mutable_cpu_data();
    caffe_set(top_count, -1, argmax_data);
  
    // For each ROI R = [batch_index x1 y1 x2 y2]: max pool over R
    for (int n = 0; n < num_rois; ++n) {
      int roi_batch_ind = bottom_rois[0];
      // 把原图的坐标映射到feature map上面
      int roi_start_w = round(bottom_rois[1] * spatial_scale_);
      int roi_start_h = round(bottom_rois[2] * spatial_scale_);
      int roi_end_w = round(bottom_rois[3] * spatial_scale_);
      int roi_end_h = round(bottom_rois[4] * spatial_scale_);
      // 计算每个roi在feature map上面的大小
      int roi_height = max(roi_end_h - roi_start_h + 1, 1);
      int roi_width = max(roi_end_w - roi_start_w + 1, 1);
      //pooling之后的feature map的一个值对应于pooling之前的feature map上的大小
      //注：由于roi的大小不一致，所以每次都需要计算一次
      const Dtype bin_size_h = static_cast<Dtype>(roi_height)
                               / static_cast<Dtype>(pooled_height_);
      const Dtype bin_size_w = static_cast<Dtype>(roi_width)
                               / static_cast<Dtype>(pooled_width_);
      //找到对应的roi的feature map，如果input data的batch size为1
      //那么roi_batch_ind=0
      const Dtype* batch_data = bottom_data + bottom[0]->offset(roi_batch_ind);
      //pooling的过程是针对每一个channel的，所以需要循环遍历
      for (int c = 0; c < channels_; ++c) {
        //计算output的每一个值，所以需要遍历一遍output，然后求出所有值
        for (int ph = 0; ph < pooled_height_; ++ph) {
          for (int pw = 0; pw < pooled_width_; ++pw) {
            // Compute pooling region for this output unit:
            //  start (included) = floor(ph * roi_height / pooled_height_)
            //  end (excluded) = ceil((ph + 1) * roi_height / pooled_height_)
            // 计算output上的一点对应于input上面区域的大小[hstart, wstart, hend, wend]
            int hstart = static_cast<int>(floor(static_cast<Dtype>(ph)
                                                * bin_size_h));
            int hend = static_cast<int>(ceil(static_cast<Dtype>(ph + 1)
                                             * bin_size_h));
            int wstart = static_cast<int>(floor(static_cast<Dtype>(pw)
                                                * bin_size_w));
            int wend = static_cast<int>(ceil(static_cast<Dtype>(pw + 1)
                                             * bin_size_w));
            //将映射后的区域平动到对应的位置[hstart, wstart, hend, wend]
            hstart = min(max(hstart + roi_start_h, 0), height_);
            hend = min(max(hend + roi_start_h, 0), height_);
            wstart = min(max(wstart + roi_start_w, 0), width_);
            wend = min(max(wend + roi_start_w, 0), width_);
            //如果映射后的矩形框不符合
            bool is_empty = (hend <= hstart) || (wend <= wstart);
            //pool_index指的是此时计算的output的值对应于output的位置
            const int pool_index = ph * pooled_width_ + pw;
            //如果矩形不符合，此处output的值设为0，此处的对应于输入区域的最大值为-1
            if (is_empty) {
              top_data[pool_index] = 0;
              argmax_data[pool_index] = -1;
            }
            //遍历output的值对应于input的区域块
            for (int h = hstart; h < hend; ++h) {
              for (int w = wstart; w < wend; ++w) {
               // 对应于input上的位置
                const int index = h * width_ + w;
                //计算区域块的最大值，保存在output对应的位置上
                //同时记录最大值的索引
                if (batch_data[index] > top_data[pool_index]) {
                  top_data[pool_index] = batch_data[index];
                  argmax_data[pool_index] = index;
                }
              }
            }
          }
        }
        // Increment all data pointers by one channel
        batch_data += bottom[0]->offset(0, 1);
        top_data += top[0]->offset(0, 1);
        argmax_data += max_idx_.offset(0, 1);
      }
      // Increment ROI data pointer
      bottom_rois += bottom[1]->offset(1);
    }
  }
  

  ROI Align

  

  为了解决ROI Pooling的上述缺点，作者提出了ROI Align这一改进的方法。ROI Align的思路很简单：取消量化操作，使用双线性内插的方法获得坐标为浮点数的像素点上的图像数值,从而将整个特征聚集过程转化为一个连续的操作。值得注意的是，在具体的算法操作上，ROI Align并不是简单地补充出候选区域边界上的坐标点，然后将这些坐标点进行池化，而是重新设计了一套比较优雅的流程，如下图所示：

  • 遍历每一个候选区域，保持浮点数边界不做量化。
  • 将候选区域分割成$k\times k$个单元，每个单元的边界也不做量化。
  • 在每个单元中计算固定四个坐标位置，用双线性内插的方法计算出这四个位置的值，然后进行最大池化操作。

  这里对上述步骤的第三点作一些说明：这个固定位置是指在每一个矩形单元（bin）中按照固定规则确定的位置。比如，如果采样点数是1，那么就是这个单元的中心点。如果采样点数是4，那么就是把这个单元平均分割成四个小方块以后它们分别的中心点。显然这些采样点的坐标通常是浮点数，所以需要使用插值的方法得到它的像素值。在相关实验中，作者发现将采样点设为4会获得最佳性能，甚至直接设为1在性能上也相差无几。 事实上，ROIAlign在遍历取样点的数量上没有ROIPooling那么多，但却可以获得更好的性能，这主要归功于解决了misalignment的问题。值得一提的是，我在实验时发现，ROIAlign在VOC2007数据集上的提升效果并不如在COCO上明显。经过分析，造成这种区别的原因是COCO上小目标的数量更多，而小目标受misalignment问题的影响更大（比如，同样是0.5个像素点的偏差，对于较大的目标而言显得微不足道，但是对于小目标，误差的影响就要高很多）。ROIAlign层要将feature map固定为2*2大小，那些蓝色的点即为采样点，然后每个bin中有4个采样点，则这四个采样点经过MAX得到ROI output；

  通过双线性插值避免了量化操作，保存了原始ROI的空间分布，有效避免了误差的产生；小目标效果比较好

  NMS算法优化的必要性

  NMS算法的功能

  非极大值抑制（NMS）非极大值抑制顾名思义就是抑制不是极大值的元素，搜索局部的极大值。例如在对象检测中，滑动窗口经提取特征，经分类器分类识别后，每个窗口都会得到一个分类及分数。但是滑动窗口会导致很多窗口与其他窗口存在包含或者大部分交叉的情况。这时就需要用到NMS来选取那些邻域里分数最高（是某类对象的概率最大），并且抑制那些分数低的窗口。印象最为深刻的就是Overfeat算法中的狗熊抓鱼图了。

  从R-CNN到SPPNet

  $RCNN$主要作用就是用于物体检测，就是首先通过$selective search$选择$2000$个候选区域，这些区域中有我们需要的所对应的物体的bounding-box，然后对于每一个region proposal都wrap到固定的大小的scale, $227\times227$(AlexNet Input),对于每一个处理之后的图片，把他都放到CNN上去进行特征提取，得到每个region proposal的feature map,这些特征用固定长度的特征集合feature vector来表示。 最后对于每一个类别，我们都会得到很多的feature vector，然后把这些特征向量直接放到SVM现行分类器去判断，当前region所对应的实物是background还是所对应的物体类别，每个region都会给出所对应的score，因为有些时候并不是说这些region中所包含的实物就一点都不存在，有些包含的多有些包含的少，包含的多少还需要合适的bounding box，所以我们才会对于每一region给出包含实物类别多少的分数，选出前几个对大数值，然后再用非极大值抑制canny来进行边缘检测，最后就会得到所对应的bounding box.

  同样，SPPNet作者观察得，对selective search(ss)提供的2000多个候选区域都逐一进行卷积处理，势必会耗费大量的时间， 所以SPPNet中先对一整张图进行卷积得到特征图，然后再将ss算法提供的2000多个候选区域的位置记录下来，通过比例映射到整张图的feature map上提取出候选区域的特征图B,然后将B送入到金字塔池化层中，进行权重计算. 然后经过尝试，这种方法是可行的，于是在RCNN基础上，进行了这两个优化得到了这个新的网络SPPNet.

  Faster RCNN

  NMS算法，非极大值抑制算法，引入NMS算法的目的在于：根据事先提供的score向量，以及regions(由不同的bounding boxes，矩形窗口左上和右下点的坐标构成) 的坐标信息，从中筛选出置信度较高的bounding boxes。

  

  Faster RCNN中输入s=600时，采用了三个尺度的anchor进行推荐，分别时128,256和512，其中推荐的框的个数为$1106786$，需要将这$1100k$的推荐框合并为$2k$个。这个过程其实正是$RPN$神经网络模型。

  SSD

  https://blog.csdn.net/wfei101/article/details/78176322 SSD算法中是分为default box(下图中(b)中为default box示意图)和prior box(实际推荐的框)

  

  

  注意

  在图像处理领域，几点经验：

  1. 输入的图像越大，结果越准确，但是计算量也更多
  2. 推荐的框越多，定位准确的概率更高，但是计算量也是会增多
  3. 推荐的框往往远大于最终的定位的个数

  那么NMS存在什么问题呢，其中最主要的问题有这么几个：

  • 物体重叠：如下面第一张图，会有一个最高分数的框，如果使用nms的话就会把其他置信度稍低，但是表示另一个物体的预测框删掉（由于和最高置信度的框overlap过大）
  • 某些情况下，所有的bbox都预测不准，对于下面第二张图我们看到，不是所有的框都那么精准，有时甚至会出现某个物体周围的所有框都标出来了，但是都不准的情况
  • 传统的NMS方法是基于分类分数的，只有最高分数的预测框能留下来，但是大多数情况下IoU和分类分数不是强相关，很多分类标签置信度高的框都位置都不是很准

  参考文献

  1. NMS的解释
  2. 附录中ROI的解释
  3. SSD算法
  4. One-Stage Detector, With Focal Loss and RetinaNet Using ResNet+FPN, Surpass the Accuracy of Two-Stage Detectors, Faster R-CNN
  5. 非极大值抑制算法的两个改进算法 & 传统NMS的问题
  6. 非极大值抑制算法（NMS）与源码分析

  one-stage和two-stage的anchor-base detection

  它们的主要区别

  • one-stage网络速度要快很多
  • one-stage网络的准确性要比two-stage网络要低

  为什么one-stage网络速度要快很多？

  首先来看第一点这个好理解，one-stage网络生成的anchor框只是一个逻辑结构，或者只是一个数据块，只需要对这个数据块进行分类和回归就可以，不会像two-stage网络那样，生成的 anchor框会映射到feature map的区域（rcnn除外），然后将该区域重新输入到全连接层进行分类和回归，每个anchor映射的区域都要进行这样的分类和回归，所以它非常耗时

  为什么one-stage网络的准确性要比two-stage网络要低？

  我们来看RCNN，它是首先在原图上生成若干个候选区域，这个候选区域表示可能会是目标的候选区域，注意，这样的候选区域肯定不会特别多，假如我一张图像是$100\times100$的，它可能会生成2000个候选框，然后再把这些候选框送到分类和回归网络中进行分类和回归，Fast R-CNN其实差不多，只不过它不是最开始将原图的这些候选区域送到网络中，而是在最后一个feature map将这个候选区域提出来，进行分类和回归，它可能最终进行分类和回归的候选区域也只有2000多个并不多。再来看Faster R-CNN，虽然Faster R-CNN它最终一个feature map它是每个像素点产生9个anchor，那么$100\times100$假如到最终的feature map变成了$26\times26$了，那么生成的anchor就是$26\times 26 \times 9 = 6084$个，虽然看似很多，但是其实它在RPN网络结束后，它会不断的筛选留下2000多个，然后再从2000多个中筛选留下300多个，然后再将这300多个候选区域送到最终的分类和回归网络中进行训练，所以不管是R-CNN还是Fast-RCNN还是Faster-RCNN，它们最终进行训练的anchor其实并不多，几百到几千，不会存在特别严重的正负样本不均衡问题. 但是我们再来看yolo系列网络，就拿yolo3来说吧，它有三种尺度，$13\times 13$，$26\times 26$，$52\times 52$，每种尺度的每个像素点生成三种anchor，那么它最终生成的anchor数目就是 $(13\times 13+26\times 26+52\times52)\times 3 = 10647$个anchor，而真正负责预测的可能每种尺度的就那么几个，假如一张图片有3个目标，那么每种尺度有三个anchor负责预测，那么10647个anchor中总共也只有9个anchor负责预测，也就是正样本，其余的10638个anchor都是背景anchor，这存在一个严重的正负样本失衡问题，虽然位置损失，类别损失，这10638个anchor不需要参与，但是目标置信度损失，背景anchor参与了，因为

  $$总的损失 = 位置损失 + 目标置信度损失 + 类别损失$$

  所以背景anchor对总的损失有了很大的贡献，但是我们其实不希望这样的，我们更希望的是非背景的anchor对总的损失贡献大一些，这样不利于正常负责预测anchor的学习，而two-stage网络就不存在这样的问题，two-stage网络最终参与训练的或者计算损失的也只有2000个或者300个，它不会有多大的样本不均衡问题，不管是正样本还是负样本对损失的贡献几乎都差不多，所以网络会更有利于负责预测anchor的学习，所以它最终的准确性肯定要高些

  总结

  one-stage网络最终学习的anchor有很多，但是只有少数anchor对最终网络的学习是有利的，而大部分anchor对最终网络的学习都是不利的，这部分的anchor很大程度上影响了整个网络的学习，拉低了整体的准确率；而two-stage网络最终学习的anchor虽然不多，但是背景anchor也就是对网络学习不利的anchor也不会特别多，它虽然也能影响整体的准确率，但是肯定没有one-stage影响得那么严重，所以它的准确率比one-stage肯定要高。

  那么什么情况下背景anchor不会拉低这个准确率呢？

  设置阀值，与真实GrundTruth IOU阀值设得小一点，只要大于这个阀值，就认为你是非背景anchor（注意这部分anchor只负责计算目标置信度损失，而位置、类别损失仍然还是那几个负责预测的anchor来负责）或者假如一个图片上有非常多的位置都是目标，这样很多anchor都不是背景anchor；总之保证背景anchor和非背景anchor比例差不多，那样可能就不会拉低这个准确率，但是只要它们比例相差比较大，那么就会拉低这个准确率，只是不同的比例，拉低的程度不同而已

  解决one-stage网络背景anchor过多导致的不均衡问题方案

  • 采用focal loss，将目标置信度这部分的损失换成focal loss
  • 增大非背景anchor的数量

  某个像素点生成的三个anchor，与真实GrundTruth重合最大那个负责预测，它负责计算位置损失、目标置信度损失、类别损失，这些不管，它还有另外两个anchor，虽然另外两个anchor不是与真实GrundTruth重合最大，但是只要重合大于某个阀值比如大于0.7，我就认为它是非背景anchor，但注意它只计算目标置信度损失，位置和类别损失不参与计算，而小于0.3的我直接不让它参与目标置信度损失的计算，实现也就是将它的权重置0，这个思想就类似two-stage网络那个筛选机制，从2000多个anchor中筛选300个参与训练或者计算目标置信度损失，相当于我把小于0.3的anchor我都筛选掉了，让它不参与损失计算

  • 设置权重 在目标置信度损失计算时，将背景anchor的权重设置得很小，非背景anchor的权重设置得很大。

  四步交替训练Faster RCNN

  训练RPN网络

  Faster RCNN有两种训练方式，一种是四步交替训练法，一种是end-to-end训练法。主文件位于/tools/train_fast_rcnn_alt_opt.py。

  第一步，训练RPN，该网络用ImageNet预训练的模型初始化，并端到端微调，用于生成region proposal;

  第二步，由imageNet model初始化，利用第一步的RPN生成的region proposals作为输入数据，训练Fast R-CNN一个单独的检测网络，这时候两个网络还没有共享卷积层;

  第三步，用第二步的fast-rcnn model初始化RPN再次进行训练，但固定共享的卷积层，并且只微调RPN独有的层，现在两个网络共享卷积层了;

  第四步，由第三步的RPN model初始化fast-RCNN网络，输入数据为第三步生成的proposals。保持共享的卷积层固定，微调Fast R-CNN的fc层。这样，两个网络共享相同的卷积层，构成一个统一的网络。

  Faster-RCNN和YOLO的anchor有什么区别

  

  可以看到yolov3是直接对你的训练样本进行k-means聚类，由训练样本得来的先验框（anchor），也就是对样本聚类的结果。Kmeans因为初始点敏感，所以每次运行得到的anchor值不一样，但是对应的avg iou稳定。用于训练的话就需要统计多组anchor，针对固定的测试集比较了。

  • https://blog.csdn.net/xiqi4145/article/details/86516511

  • https://blog.csdn.net/cgt19910923/article/details/82154401

  Read All

  ---

• 纪念工作一周年

  2019-07-07

  opinion

  随笔

  七律·人民解放军占领南京
  作者：毛泽东
  钟山风雨起苍黄，百万雄师过大江。
  虎踞龙盘今胜昔，天翻地覆慨而慷。
  宜将剩勇追穷寇，不可沽名学霸王。
  天若有情天亦老，人间正道是沧桑。
  

  纪念工作一周年

  七月，是北京炎热的开始。前几天都飙升到38摄氏度。两年前这个时候，校招季的到来，然我提前忙碌起来。现在想想，我已经工作一年了。 我们组在这一年里的故事，可以写成一部小说。故事情节可能不如战争年代的故事激荡人心，不及爱情故事扣人心弦，但是一年的努力与成长让我想写点什么。

  万丈高楼平地起，AI建设在基础。基础架构部在深入贯彻落实“正，信，恒，勇，合”的道路上，本着”数据是AI算法之基础，测试是算法优势之保障，落地是算法研发之目的。”的原则，加强系统建设与算法落实，解决AI算法应用的基本问题，构建稳固的AI大楼基础。基础架构部在过去的一年内，在平台建设，算法落地等基础架构建设方面取得卓越的成果。正所谓：“基础不牢，地动山摇。” 打牢基层基础，既是构建工程院的重要内容，也是有序推进AI发展的重要保障，意义十分重大。

  这是加入半年后的年会，为我们部门编写晚会视频开篇。回想我们组的工作内容，的确就是这么回事儿，基础而重要，没有我们的工作，产品组实现起来得非常困难。

  “绿叶吮吸雨露，沐浴阳光的时候，可曾想过根茎在岩石和土壤中的努力付出；花朵以美丽的姿态绽放，接受虫鸟的光顾和人类的褒奖之时可曾想起过根茎的努力付出与绿叶的衬托；秋天的果实以饱满丰硕的体态迎接丰收的时候，可能想起过根茎的努力，叶子与花朵的牺牲。” 而基础架构部的工作内容就像根茎，我只能说很重要，但如果你想被人直接赞美，那是不可能的。

  一年来，结识了不同年龄段的朋友，他们口中的故事是我们日常午餐的甜点。夏天，在空调室内呆久了，就尤其喜欢直射的烈日，晒在身上一下子把身上的霜层烤干。散步到或春天通风，或夏天阴凉，冬日阳光温和的地方，停下来侃侃天地，拉拉家常，有点像户外度假的日子。但一旦到点儿，都立刻马上回到自己的工作岗位上。 我突然想起一句歌词：“打起鼓来，敲起锣来哎，推着小车来送货…” 这虽说的小货郎的工作，但是我们工作内容也像小货郎卖的货品一样丰富多彩，要啥有啥，工作状态也是欢快轻松的。

  最后，我们组缺人，缺人。我们组hc丰富：

  校招-算法开发工程师

  工作职责：
  
  1、机器视觉系统中图像处理、分析及识别算法的设计、实现及性能调优； 
  2、参与图像视觉处理技术的研究与设计； 
  3、参与图像视觉SDK的设计与实现。
  
  任职资格：
  
  1、较强的C/C++语言设计、开发及调试能力； 
  2、熟悉 X86、ARM 的多线程和SIMD代码优化技术； 
  3、有计算机视觉、模式识别、图像处理方面开发经验优先； 
  4、具有GPU cuda编程/openMP/openMPI等并行加速开发经验者优先； 
  5、良好的沟通能力和团队协作能力。
  

  社招-SDK开发工程师

  工作职责：
  
  1. 底层框架通用性封装及优化；保障底层框架SDK的稳定性及高效，跨平台并针对平台进行优化
  2. 算法应用成果转化；深度学习相关算法成果转化，包括基于深度学习底层SDK实现的检测、分类、跟踪等方向的算法
  3. 负责工程性算法策略创建及优化；基于算法SDK，面向行业业务的工程性算法策略的设计及实现;针对不同应用场景，优化工程性算法策略
  4、上层业务支持；针对确定的产品业务，与算法及产品一起快速迭代，保障业务顺利推进
  
  任职资格：
  
  1. 计算机或电子相关专业硕士或以上，两年以上相关工作经验
  2. 精通C/C++开发，编程功底扎实，掌握常用数据结构和算法，熟悉面向对象编程，熟悉常见的架构及设计模式
  3. 有嵌入式SDK开发以及优化等相关经验的优先
  4、有计算机视觉（检测、跟踪、识别）方向、图像处理应用经验优先
  5、有良好的代码开发风格和软件工程思维，熟悉 Git, CMake 等工具
  

  社招-后端高级开发工程师

  工作职责：
  
  1、负责系统后端服务的需求分析、详细设计以及开发工作。
  2、负责系统模块的开发、测试、集成。
  3、不断优化、提升服务的性能。
  
  
  任职资格：
  
  1、本科及以上学历，计算机或地理信息相关专业，3年及以上后端开发经验。
  2、扎实的计算机基础，熟悉常见的数据结构、设计模式及算法
  3、精通至少一门后端语言（nodejs、java、go、python），并能熟练进行服务开发。
  4、熟悉PostgreSQL、Redis等数据库；熟悉Kafka、RabbitMQ等消息中间件；
  5、了解TCP/HTTP/WebSocket等网络通信协议
  6、良好的代码习惯，强大的编码能力，善于学习，勇于解决难题，具备团队精神。
  

  社招-产品技术经理

  工作职责：
  
  1. 负责视觉人工智能算法SDK和平台产品的需求分析、产品规划设计和目标管理
  2. 管理产品生命周期，协调资源，推动跨部门协同，管理依赖和风险，保证高效率、高质量地完成产品开发交付
  3. 负责产品运营推广，跟踪用户反馈，分析系统数据，持续优化产品
  4. 推动研发团队做出合理的技术决策，梳理和改善研发流程和规范
  
  任职资格：
  
  1. 本科或以上学历，计算机或相关专业毕业，3年以上软件、互联网或AI行业产品相关经验
  2. 具有扎实的技术基础和技术背景，熟悉软件或互联网产品开发的开发技术栈，有计算机视觉、机器学习或分布式系统开发相关背景者优先
  3. 熟悉软件或互联网产品开发技术栈，熟悉软件工程和敏捷开发方法
  4. 优秀的学习和沟通能力，逻辑性强，自驱力强，项目推动力强，有团队管理经验者优先
  

  更多岗位可以查询：http://hr.sensetime.com

  Read All

  ---

• Megvii:计算机视觉之物体检测与深度神经网络模型设计专场

  2019-05-11

  blog

  计算机视觉
  • 概述
  • Deform ConvNet(DCN) v.s. ConvNet
  • Review Object Detection from anchor base to anchor-free
  • 当前scene text detection中的一些问题和研究进展
    • 暂时定的路线是：
    • 需要思考的内容：
  • 相关文献及blog

  概述

  今天主要围绕计算机视觉领域的一些任务中，如何提高score的方面进行了各种方面的讨论。研究领域包括：基本的场景的物体检测，开放领域的物体检测，不规则文本检测。涉及的相关技术有

  • 在backbone设计中总结的一些tips；
  • 如何在物体检测领域，通过分析对比各种方法，提出自己的解决方案；
  • 物体检测领域中多尺度问题的重要性；
  • anchor是什么东西，anchor free和anchor base之间的 vs
  • attention在计算机视觉中的应用SENet

  Deform ConvNet(DCN)¹ v.s. ConvNet

  这个专题主要是为了改善遮挡和分割算法而做的相关研究。在普通的卷积中，加入旋转，scale等特性，使得能够对一个非正方凸区域进行卷积。这就可以使得卷积提取特征不仅仅局限在的一个方正的空间区域，可以根据物体的形状等等学习到相关的角度变化等权重，从而实现对非规则空间区域的特征提取。这无疑将物体分割任务直接统一为物体检测任务，还是比较nice的构想。虽然有好处，但由于多个计算过程中引入了非规则的问题，导致计算速度方面可能受到一定的影响。

  

  Review Object Detection from anchor base to anchor-free

  这个主要通过介绍anchor-base和anchor-free的发展路线，讨论两种方法的之间的优劣之处。认为现在anchor-base的research空间已经有限，所以开始考虑向anchor-free开始进展。anchor-base需要设置较多的超参数，落地的过程中存在较大的调参困难。而anchor-free相对来说，比较少。

  

  当前scene text detection中的一些问题和研究进展

  这个话题我还比较感兴趣的。因为我后面要做一些自然场景文本检测的一个项目，所以最近在突击这方面的论文。而这个论坛中关于自然场景文本检测的分享让我受益颇丰。我才发现原来要找的相关文献很多都是白翔老师这个组的工作。

  白翔，华中科技大学电信学院教授，先后于华中大获得学士、硕士、博士学位。他的主要研究领域为计算机视觉与模式识别、深度学习应用技术。尤其在形状的匹配与检索、相似性度量与融合、场景OCR取得了一系列重要研究成果，入选2014、2015、2016年Elsevier中国高被引学者。他的研究工作曾获微软学者，首届国家自然科学基金优秀青年基金的资助。他已在相关领域一流国际期刊或会议如PAMI、IJCV、CVPR、ICCV、ECCV、NIPS、ICML、AAAI、IJCAI上发表论文40余篇。任国际期刊Pattern Recognition, Pattern Recognition Letters, Neurocomputing, Frontier of Computer Science编委，VALSE指导委员，曾任VALSE在线委员会(VOOC)主席, VALSE 2016大会主席, 是VALSE在线活动（VALSE Webinar）主要发起人之一。

  现在还是没有入门，师傅已经带我走马观花了，剩下的就是我自己细细品读各个方法的奥秘了。

  暂时定的路线是：

  1. SWT，MSER两个经典方法和衍生方法
  2. 引入CNN之后如何演变到CNN+LSTM的方法
  3. 分割技术如何提升不规则排布文本检测的²³⁴

  需要思考的内容：

  1. 常用数据集，和应用场景的实际数据之间的差别
  2. 各个方法之间的改进策略的出发点是什么，有什么收获？
  3. 水平文本检测性能、速度比较推荐的算法是什么，简单应用场景呢？
  4. 常规检测算法的与文本检测算法之间能不能直接迁移应用，有什么gap，克服这个gap需要做什么工作
  5. 分割算法应用到文本检测中有什么结果，为什么会对非规则文本检测有好处

  相关文献及blog

  1. https://arxiv.org/abs/1703.06211 “Deformable Convolutional Networks” ↩

  2. https://arxiv.org/abs/1811.00751 “Show, Attend and Read: A Simple and Strong Baseline for Irregular Text Recognition” ↩

  3. https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/81437413 “Mask TextSpotter: An End-to-End Trainable Neural Network for Spotting Text with Arbitrary Shapes” ↩

  4. https://blog.csdn.net/francislucien2017/article/details/88583219 “不规则文字识别方法之 SAR: Show, Attend and Read” ↩

  Read All

  ---

• 关于开发中常见的编译器技巧

  2019-04-11

  blog

  C++  开发
  • 引言
  • 编译常见问题
    • 包含静态库中所有符号的option
    • 其他可能问题
    • Solution
    • 编译运行查找头文件和库的顺序
    • 运行时动态库的搜索路径
    • 动态库中的static变量
  • windows编译
    • windows下路径长度不能太长
    • MSVC中预定义宏
  • GNU 编译器
    • gcc/g++的--as-needed
    • -rdynamic
    • _GLIBCXX_USE_CXX11_ABI
    • -Wl,–allow-shlib-undefined
    • TARGET_LINK_LIBRARY & LINK_LIBRARY
  • GCC不同版本中一些东西
    • GCC4.9.4
      • Inter-procedural optimization improvements:
      • Feedback directed optimization improvements:
    • GCC 5.4
      • libstd++上的优化
    • GCC dump preprocessor defines
    • TODO

  引言

  编译器是我们开发人员与机器指令之间的翻译,现在编译器越来越优化,而且基于一些开源的编译器项目(gcc,clang)等,相继出现不同platform下的编译器。 此外，各种芯片、开发板层出不穷，各个商业公司都针对自己出产的开发板定制特定的编译链条。例如华为hisi系列的himix100中提供的编译链中，包括编译器，链接器，打包器之外，还提供了nm，gdb，gcov，gprof等等开发工具。 这篇文章将主要将开发工作中与编译器（这篇文章中不作特殊说明，指的是gnu gcc编译器）相关的一些options和配置参数进行总结,方便在后面的项目遇到相似的问题进行查阅与借鉴。

  编译常见问题

  包含静态库中所有符号的option

  $$A -> B -> C$$

  编译shared target B库的时候，gcc编译器默认是用什么区什么的原则，也就是说，依赖了库A中哪个.o文件中的东西，就会把相应的.o文件 打包到最终的库中。但是，有的时候在这个库中我们并没有引用全部的符号，但是当其他库C依赖我们这个B库的时候，如果引用了B中未引用的A中的符号，这个时候会出现”undefined reference”的编译错误。-Wl,--whole-archive可以实现将所有库中的符号打包进去。

  编译器编译动态库或者运行程序的时候，会对依赖的静态库中进行基于.o的选择，但是有的时候我们希望我们编译的动态库能够包含所有的函数实现给用户使用。gcc中的链接控制选项-Wl,--whole-archive xxxxx_lib -Wl,--no-whole-archive就可以实现类似功能。

  target_link_libraries(xxxx_export 
              PRIVATE "-Wl,--whole-archive" $<TARGET_FILE:xxxxx_lib>
                      "-Wl,--no-whole-archive -Wl,--exclude-libs,ALL")
  

  其他可能问题

  --exclude-libs does not work for static libraries affected by the --whole-archive option.

  • --exclude-libs creates a list of static library paths and does library lookups in this list.
  • --whole-archive splits the static libraries that follow it into separate objects. As a result, lld no longer sees static libraries among linked files and does no --exclude-libs lookups.

  Solution

  The proposed solution is to make --exclude-libs consider object files too. When lld finds an object file it checks whether this file originates from an archive and, if so, looks the archive up in the --exclude-libs list.

  Reference: https://reviews.llvm.org/D39353

  编译运行查找头文件和库的顺序

  gcc 在编译时如何去寻找所需要的头文件:

  • 所以header file的搜寻会从-I开始
  • 然后找gcc的环境变量 C_INCLUDE_PATH，CPLUS_INCLUDE_PATH，OBJC_INCLUDE_PATH
  • 再找内定目录
    • /usr/include
    • /usr/local/include

  gcc的一系列自带目录 CPLUS_INCLUDE_PATH=/usr/lib/gcc/x86_64-linux-gnu/4.9.4/include:/usr/include/c++/4.9.4

  库文件

  编译的时候：

  • gcc会去找-L
  • 再找gcc的环境变量LIBRARY_PATH
  • 再找内定目录
    • /lib和/lib64
    • /usr/lib 和/usr/lib64
    • /usr/local/lib和/usr/local/lib64

  这是当初compile gcc时写在程序内的

  运行时动态库的搜索路径

  动态库的搜索路径搜索的先后顺序是：

  1. 编译目标代码时指定的动态库搜索路径；
  2. 环境变量LD_LIBRARY_PATH指定的动态库搜索路径；
  3. 配置文件/etc/ld.so.conf中指定的动态库搜索路径；
  4. 默认的动态库搜索路径/lib；
  5. 默认的动态库搜索路径/usr/lib。

  动态库中的static变量

  In all cases, static global variables (or functions) are never visible from outside a module (dll/so or executable). The C++ standard requires that these have internal linkage, meaning that they are not visible outside the translation unit (which becomes an object file) in which they are defined.

  windows编译

  在windows常用的编译器是VS里面的cl编译器。我们要实现上述 cmake使用cmake -DCMAKE_WINDOWS_EXPORT_ALL_SYMBOLS=TRUE -DBUILD_SHARED_LIBS=TRUE

  Enable this boolean property to automatically create a module definition (.def) file with all global symbols found in the input .obj files for a SHARED library on Windows. The module definition file will be passed to the linker causing all symbols to be exported from the .dll. For global data symbols, __declspec(dllimport) must still be used when compiling against the code in the .dll. All other function symbols will be automatically exported and imported by callers. This simplifies porting projects to Windows by reducing the need for explicit dllexport markup, even in C++ classes.
  
  This property is initialized by the value of the CMAKE_WINDOWS_EXPORT_ALL_SYMBOLS variable if it is set when a target is created.
  

  Reference: WINDOWS_EXPORT_ALL_SYMBOLS

  windows下路径长度不能太长

  error MSB3491: Could n ot write lines to file https://stackoverflow.com/questions/31765909/node-socket-io-client-windows-path-too-long-to-install

  MSVC中预定义宏¹

  • _M_IX86 Defined as the integer literal value 600 for compilations that target x86 processors. This macro isn’t defined for x64 or ARM compilation targets.

  • _M_IX86_FP Defined as an integer literal value that indicates the /arch compiler option that was set, or the default. This macro is always defined when the compilation target is an x86 processor. Otherwise, undefined. When defined, the value is:
    • 0 if the /arch:IA32 compiler option was set.
    • 1 if the /arch:SSE compiler option was set.
    • 2 if the /arch:SSE2, /arch:AVX, /arch:AVX2, or /arch:AVX512 compiler option was set. This value is the default if an /arch compiler option wasn’t specified. When /arch:AVX is specified, the macro __AVX__ is also defined. When /arch:AVX2 is specified, both __AVX__ and __AVX2__ are also defined. When /arch:AVX512 is specified, __AVX__, __AVX2__, __AVX512BW__, __AVX512CD__, __AVX512DQ__, __AVX512F__ and __AVX512VL__ are also defined.

    For more information, see /arch (x86).

  • _M_X64 Defined as the integer literal value 100 for compilations that target x64 processors. Otherwise, undefined.

  • _MSC_VER Defined as an integer literal that encodes the major and minor number elements of the compiler’s version number. The major number is the first element of the period-delimited version number and the minor number is the second element. For example, if the version number of the Microsoft C/C++ compiler is 17.00.51106.1, the _MSC_VER macro evaluates to 1700. Enter cl /? at the command line to view the compiler’s version number. This macro is always defined.

    Visual Studio version	_MSC_VER
    Visual Studio 6.0	1200
    Visual Studio .NET 2002 (7.0)	1300
    Visual Studio .NET 2003 (7.1)	1310
    Visual Studio 2005 (8.0)	1400
    Visual Studio 2008 (9.0)	1500
    Visual Studio 2010 (10.0)	1600
    Visual Studio 2012 (11.0)	1700
    Visual Studio 2013 (12.0)	1800
    Visual Studio 2015 (14.0)	1900
    Visual Studio 2017 RTW (15.0)	1910
    Visual Studio 2017 version 15.3	1911
    Visual Studio 2017 version 15.5	1912
    Visual Studio 2017 version 15.6	1913
    Visual Studio 2017 version 15.7	1914
    Visual Studio 2017 version 15.8	1915
    Visual Studio 2017 version 15.9	1916
    Visual Studio 2019 RTW (16.0)	1920
    Visual Studio 2019 version 16.1	1921
    Visual Studio 2019 version 16.2	1922
    Visual Studio 2019 version 16.3	1923

  • _MSVC_LANG Defined as an integer literal that specifies the C++ language standard targeted by the compiler. It’s set only in code compiled as C++. The macro is the integer literal value 201402L by default, or when the /std:c++14 compiler option is specified. The macro is set to 201703L if the /std:c++17 compiler option is specified. It’s set to a higher, unspecified value when the /std:c++latest option is specified. Otherwise, the macro is undefined. The _MSVC_LANG macro and /std (Specify Language Standard Version) compiler options are available beginning in Visual Studio 2015 Update 3.

  • _MT Defined as 1 when /MD or /MDd (Multithreaded DLL) or /MT or /MTd (Multithreaded) is specified. Otherwise, undefined.

  • _WIN32 Defined as 1 when the compilation target is 32-bit ARM, 64-bit ARM, x86, or x64. Otherwise, undefined.

  • _WIN64 Defined as 1 when the compilation target is 64-bit ARM or x64. Otherwise, undefined.

  GNU 编译器

  gcc/g++的--as-needed

  gcc/g++提供了-Wl,--as-needed和 -Wl,--no-as-needed两个选项，这两个选项一个是开启特性，一个是取消该特性。

  在生成可执行文件的时候，通过 -lxxx 选项指定需要链接的库文件。以动态库为例，如果我们指定了一个需要链接的库，则连接器会在可执行文件的文件头中会记录下该库的信息。而后，在可执行文件运行的时候，动态加载器会读取文件头信息，并加载所有的链接库。在这个过程中，如果用户指定链接了一个毫不相关的库，则这个库在最终的可执行程序运行时也会被加载，如果类似这样的不相关库很多，会明显拖慢程序启动过程。

  这时，通过指定-Wl,--as-needed选项，链接过程中，链接器会检查所有的依赖库，没有实际被引用的库，不再写入可执行文件头。最终生成的可执行文件头中包含的都是必要的链接库信息。-Wl,--no-as-needed选项不会做这样的检查，会把用户指定的链接库完全写入可执行文件中。

  Reference: GCC/G++选项 -Wl,–as-needed

  -rdynamic

  Pass the flag `-export-dynamic` to the ELF linker, on targets that support
  it. This instructs the linker to add all symbols, not only used ones, to the dynamic symbol table. This option is needed for some uses of `dlopen` or to allow obtaining backtraces from within a program.
  

  关键的不同是：-Wl,--export-dynamic -pthread -Wl:指示后面的选项是给链接器的 -pthread: 链接程序的时包含libpthread.so --export-dynamic：就是这个选项让主程序内定义的全局函数对库函数可见。

  Reference: gcc链接选项–export-dynamic的一次问题记录

  _GLIBCXX_USE_CXX11_ABI

  在GCC 5.1版本中，libstdc++引入了一个新的ABI，其中包括std::string和std::list的新实现。为了符合2011年c++标准，这些更改是必要的，该标准禁止复制即写字符串，并要求列表跟踪字符串的大小。 为了保持与libstdc++链接的现有代码的向后兼容性，库的soname没有更改，并且仍然支持与新实现并行的旧实现。这是通过在内联命名空间中定义新的实现来实现的，因此它们具有不同的用于链接目的的名称，例如，std::list的新版本实际上定义为std:: _cxx11::list。因为新实现的符号有不同的名称，所以两个版本的定义可以出现在同一个库中。 _GLIBCXX_USE_CXX11_ABI宏控制库头中的声明是使用旧ABI还是新ABI。因此，可以为正在编译的每个源文件分别决定使用哪个ABI。使用GCC的默认配置选项，宏的默认值为1，这将导致新的ABI处于活动状态，因此要使用旧的ABI，必须在包含任何库头之前显式地将宏定义为0。(注意，一些GNU/Linux发行版对GCC 5的配置不同，因此宏的默认值是0，用户必须将它定义为1才能启用新的ABI)。

  IF(CMAKE_CXX_COMPILER_VERSION VERSION_LESS "5.1")
  	ADD_DEFINITIONS(-D_GLIBCXX_USE_CXX11_ABI=0)
  ENDIF()
  

  -Wl,–allow-shlib-undefined

  在交叉编译程序过程中，往往会有这样的情况，依赖的target系统上的动态库（例如android上的OpenCL.so）又依赖其他的许多动态库，这个时候，我们希望链接target系统上的这个动态库的时候，我们可以不要去找OpenCL相关的依赖符号。

  SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wl,--allow-shlib-undefined")

  Linking errors with “-Wl,–no-undefined -Wl,–no-allow-shlib-undefined”

  第二个参数的默认值是--allow-shlib-undefined。如果您选择该选项，代码可能会生成。 第二个参数处理构建时检查，启用它意味着检查您所链接的库是否在构建时连接了其依赖项。

  第一个参数确保您没有忘记声明对运行时库的依赖项(也可能是运行时库对另一个运行时库的依赖项)。 例如，如果您调用的函数的实现位于示例运行时库“libfunc”中。然后这个库会调用另一个运行时库中的函数libext。然后通过声明对libfunc的“func”和“ext”的依赖关系。因此，将在内部生成一个对libext的依赖引用。 如果您省略--no undefined并忘记添加依赖项声明，那么构建仍然会成功，因为您相信运行时链接器将在运行时解析依赖项。 由于构建成功了，您可能会相信一切都会好起来，而不知道构建已经将责任推迟到运行时链接器。 但大多数情况下，运行时链接器的设计目的不是搜索未解析的引用，而是希望找到运行时库中声明的此类依赖项。如果没有这样的引用，您将得到一个运行时错误。 运行时错误通常比解决编译时错误要昂贵得多。

  TARGET_LINK_LIBRARY & LINK_LIBRARY

  target_link_libraries 会将需要链接的库作为属性挂在目标库上， 后面用户用到这个库的时候可以通过get_target_property(interface_link_libs ${} TARGET_LINK_LIBRARIES)进行获取相应的值。

  GCC不同版本中一些东西

  GCC4.9.4

  The -Wdate-time option has been added for the C, C++ and Fortran compilers, which warns when the __DATE__, __TIME__ or __TIMESTAMP__ macros are used. Those macros might prevent bit-wise-identical reproducible compilations.

  With the new #pragma GCC ivdep, the user can assert that there are no loop-carried dependencies which would prevent concurrent execution of consecutive iterations using SIMD (single instruction multiple data) instructions.

  Inter-procedural optimization improvements:

  • New type inheritance analysis module improving devirtualization. Devirtualization now takes into account anonymous name-spaces and the C++11 final keyword.
  • New speculative devirtualization pass (controlled by -fdevirtualize-speculatively.
  • Calls that were speculatively made direct are turned back to indirect where direct call is not cheaper.
  • Local aliases are introduced for symbols that are known to be semantically equivalent across shared libraries improving dynamic linking times.

  Feedback directed optimization improvements:

  • Profiling of programs using C++ inline functions is now more reliable.
  • New time profiling determines typical order in which functions are executed.
  • A new function reordering pass (controlled by -freorder-functions) significantly reduces startup time of large applications. Until binutils support is completed, it is effective only with link-time optimization.
  • Feedback driven indirect call removal and devirtualization now handle cross-module calls when link-time optimization is enabled.

  https://gcc.gnu.org/gcc-4.9/porting_to.html

  GCC 5.4

  • The default mode for C is now -std=gnu11 instead of -std=gnu89.
  • The C++ runtime library (libstdc++) uses a new ABI by default (see below).

  • The non-standard C++0x type traits has_trivial_default_constructor, has_trivial_copy_constructor and has_trivial_copy_assign have been deprecated and will be removed in a future version. The standard C++11 traits is_trivially_default_constructible, is_trivially_copy_constructible and is_trivially_copy_assignable should be used instead.

  • 添加-fipa-icf的配置项目

    An Identical Code Folding (ICF) pass (controlled via -fipa-icf) has been added. Compared to the identical code folding performed by the Gold linker this pass does not require function sections. It also performs merging before inlining, so inter-procedural optimizations are aware of the code re-use. On the other hand not all unifications performed by a linker are doable by GCC which must honor aliasing information.

  • The devirtualization pass was significantly improved by adding better support for speculative devirtualization and dynamic type detection.

  • 虚表进行了优化以减少动态链接时间 Virtual tables are now optimized. Local aliases are used to reduce dynamic linking time of C++ virtual tables on ELF targets and data alignment has been reduced to limit data segment bloat.

  • 添加针对不允许插入导出符号的shared库，添加了控制项目以提高代码质量

    A new -fno-semantic-interposition option can be used to improve code quality of shared libraries where interposition of exported symbols is not allowed.

  • 内联可以控制

    With profile feedback the function inliner can now bypass –param inline-insns-auto and –param inline-insns-single limits for hot calls.

  • 常量的过程间传播现在也传播指针参数的对齐。

    The interprocedural propagation of constants now also propagates alignments of pointer parameters. This for example means that the vectorizer often does not need to generate loop prologues and epilogues to make up for potential misalignments.

  • 内存使用上一些优化

    Memory usage and link times were improved. Tree merging was sped up, memory usage of GIMPLE declarations and types was reduced, and, support for on-demand streaming of variable constructors was added.

  libstd++上的优化

  • Dual ABI
  • A new implementation of std::string is enabled by default, using the small string optimization(SSO) instead of copy-on-write(COW) reference counting.
  • A new implementation of std::list is enabled by default, with an O(1) size() function;

  GCC dump preprocessor defines

  • 最常用的输出编译器预定义的宏

  gcc -dM -E - < /dev/null

  g++ -dM -E -x c++ - < /dev/null

  • How do I dump preprocessor macros coming from a particular header file?

  echo "#include <sys/socket.h>" | gcc -E -dM -

  • 添加某些options之后的

  gcc -dM -E -msse4 - < /dev/null | grep SSE[34]

  #define SSE3 1 \ #define SSE4_1 1 \ #define SSE4_2 1 \ #define SSSE3 1

  TODO

  • 常用的交叉编译的选项
  • -O3和-O2之间的差别
  • 不同平台之间之间的差别
  • 如何给不同版本的gcc打补丁

  在文章[Algorithm-Optimization]²中介绍了一些有利于优化性能的函数，感兴趣可以结合不同平台的优化指令一起学习使用。

  1. https://docs.microsoft.com/en-us/cpp/preprocessor/predefined-macros?view=vs-2017 “Predefined macros” ↩

  2. http://deepindeed.cn/2017/03/17/Algorithm-Optimization/ ↩

  Read All

  ---

• 混合精度训练

  2019-04-07

  blog

  Algorithm
  • 引言
  • Alibaba PAI: Auto-Mixed Precision Training Techniques
    • 为什么采用AMP（Auto mixed-precision）
      • Mixed-precision的优势
      • No free-lunch
    • 如何AMP：Design Philosophy
    • 结果
  • 题外思考
  • 参考文献

  引言

  CUDA在推出7.5的时候提出了 可以计算16位浮点数据的新特性。定义了两种新的数据类型half和half2. NVIDIA GPUs implement the IEEE 754 floating point standard (2008), which defines half-precision numbers as follows (see Figure 1).

  • Sign: 1 bit
  • Exponent width: 5 bits
  • Significand precision: 11 bits (10 explicitly stored) The range of half-precision numbers is approximately $5.96 \times 10^{-8} \ldots 6.55 \times 10^4$. half2 structures store two half values in the space of a single 32-bit word, as the bottom of Figure 1 shows.

  

  CUDA-9中已经开始支持混合精度训练¹，TensorRT作为NVIDIA的inference引擎，同样支持混合精度的神经网络inference计算. 之前在网上看到半精度memory copy与计算，发现copy的代价会减少一半，而计算的提升并不是很理想。后来看到了《why cublasHgemm is slower more than cublasSgemm when I use?》这个帖子，终于发现其中的一点规律。

  问题的提出者问，为什么在GTX1070上运行cublasHgemm（半精度计算） 比 cublasSgemm（单精度计算）计算的慢呢？NVIDIA官方的回答说，当前Pascal架构的GPU只有的P100的FP16计算快于FP32。并且给出了编程手册的吞吐量的表²。

  Alibaba PAI: Auto-Mixed Precision Training Techniques

  随着NVIDIA release的APEX³，利用Volta架构和混合精度在Pytorch上进行拓展，实现了训练的精度混合。腾讯⁴和百度⁵分别发表关于混合精度训练的文章.PAI-TAO是alibaba内部一个关于混合精度训练的一个研究项目。 在整个AI模型的生命周期中的位置如下：

  

  从中可以看出，自动混合精度主要是在训练过程中，为了加快计算节点之间的数据交换和层之间的数据交换与计算，采用FP16来替换FP32，这样在计算结果精度几乎不损失的情况下，带了数据交换和计算速度方面的性能提升，从而加快模型训练速度。

  而这项任务的成功，与CUDA9中支持TensorCore的特性是息息相关的。下面对TensorCode进行简单介绍。

  

  TensorCore是NVIDIA在Volta architecture下引入的，专门针对计算4x4矩阵的计算模块。 以前NVIDIA的GPU中只有FP32和FP64计算单元，在TensorCore中，特别针对FP16做了相应的补充， 来补充在半精度浮点方面的不足。TensorCore相比较直接进行FP32的计算，速度有了很大的提升。

  为什么采用AMP（Auto mixed-precision）

  Mixed-precision的优势

  • 充分发挥Volta架构引入的TensorCore计算性能 (15->120TFLOPs, 8X)
  • 减少了访存带宽

  No free-lunch

  • 用户模型改写的人力负担
  • 精度调优问题
  • 充分利用TensorCore的技术tricks
    • 数据尺寸对齐问题
    • Layout问题
  • TensorCore将计算密集部分比例降低以后的进一步优化空间挖掘

  如何AMP：Design Philosophy

  • 精度问题
    • 模型以FP32进行保存
    • 不同算子的区别处理
      • 计算密集型算子（MatMul/Conv） 输入为FP16，FP32累加中间结果，输出为FP32，计算基于TensorCore
      • 访存密集型算法（Add/Reduce/…) 输入输出均为FP16，计算为FP16/FP32, 不使用TensorCore，访存量减少
    • Loss scaling策略解决gradient underflow问题
    • 表达精度问题： FP32->FP16
      • 尾数位减少: precision gap in sum (Solution: 模型以FP32进行保存)
      • 指数位减少: gradient underflow

  

  • 速度及易用性问题
    • 通过图优化pass自动完成混合精度所需的图转换工作

  结果

  • No laborious FP32/FP16 casting work anymore
  • Already supporting diversified internal workloads: NLP/CNN/Bert/Graph Embedding
  • 1.3~3x time-to-accuracy speed-up 与PAI-TAO Compiler联合使用可以达到1+1>2的加速收益

  题外思考

  现在我们的训练应该是没有引入混合精度训练的，而且inference框架中没有混合精度的苗头。 我们的inference应该可以先支持起混合精度的，然后后面慢慢地在训练框架中添加相关功能。 然后重构节点之间的数据交换代码，加大对混合精度训练的时候并行度，进一步降低训练模型的成本。 尤其是弱计算能力的芯片上，通过添加混合计算功能，能够在加速的同时，追求更高的精度。 现在很多AI推理芯片如华为himix200中，支持int8和int16的计算，而且同一个模型可以混合int8和int16的精度类型。

  参考文献

  1. https://docs.nvidia.com/deeplearning/sdk/pdf/Training-Mixed-Precision-User-Guide.pdf “Training-Mixed-Precision-User-Guide” ↩

  2. https://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html#arithmetic-instructions “throughputs of the arithmetic instructions” ↩

  3. https://cloud.tencent.com/developer/news/254121 “混合精度训练之APEX” ↩

  4. http://m.elecfans.com/article/721085.html “一种具有混合精度的高度可扩展的深度学习训练系统” ↩

  5. https://arxiv.org/pdf/1710.03740.pdf “百度和NVIDIA联合出品：MIXED PRECISION TRAINING” ↩

  Read All

  ---

• 约束优化方法：拉格朗日乘子法与KKT条件

  2019-03-23

  blog

  Algorithm
  • 引言
  • 不同类型的约束下的优化问题
    • 无约束优化
    • 等式约束优化
    • 不等式约束
    • KKT条件
  • 拉格朗日对偶问题
  • 参考链接

  引言

  最速下降法、拟牛顿法等都是求解准则函数（即无约束优化问题）的算法，这就需要有一个前提：怎样得到无约束准则函数？而拉格朗日乘子，将有限制条件的优化问题转化为无限制的优化问题，可见拉格朗日乘子搭建了一个桥梁：将有限制的准则函数，转化为无限制准则函数，进而借助最速下降法、拟牛顿法等求参算法进行求解，在这里汇总一下拉格朗日乘子法是有必要的，全文包括：

  • 含有等式约束的拉格朗日乘子法；
  • 拉格朗日对偶方法；

  不同类型的约束下的优化问题

  无约束优化

  如果不带任何约束的优化问题，对于变量$x \in \mathbb{R}^N$,无约束的优化问题 $\min_xf(x)$ 这个问题直接找到使目标函数的导数为0的点即可，$\nabla_xf(x) = 0$,如果没有解析解的话，可以使用 梯度下降法或者牛顿法等迭代手段来使$x$沿负梯度方向逐步逼近极小值点。

  等式约束优化

  当目标函数加上约束条件之后：

  $$\begin{aligned} &\min_{x } \ f(x) \\ &s.t. \ \ \ g_i(x) = 0 , i = 1,2,...,m \\ \end{aligned}$$

  约束条件会将解的范围限定在一个可行域，此时不一定能找到使得 $\nabla_xf(x)$为 0 的点，只需找到在可行域内使得$f(x)$最小的值即可， 常用的方法即为拉格朗日乘子法，该方法首先引入Lagrange Multiplier $\alpha \in \mathbb{R}^m$，构建 Lagrangian 如下：

  $$L(x,\alpha) = f(x) + \sum_{i=1}^m \alpha_i g_i(x)$$

  求解方法，首先对Lagrangian关于$\alpha$和$x$求导数，令导数为0：

  $$\left \{ \begin{aligned} \nabla_x L(x,\alpha)= 0 \\ \nabla_{ \alpha } L(x,\alpha)= 0 \end{aligned} \right.$$

  求得$x, \alpha$的值以后，将$x$带入$f(x)$即为在约束条件$h_i(x)$下的可行解。

  看一个示例，对于二维情况下的目标函数是$f(x,y)$， 在平面中画出$f(x,y)$的等高线，如下图的虚线所示，并只给出一个约束等式$g(x,y)=c$， 如下图的红线所示， 目标函数$f(x,y)$与约束函数$g(x,y)$只有三种情况，相交、相切或者没有交集， 没交集肯定不是解,只有相交或者相切可能是解， 但相交得到的一定不是最优值，因为相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部， 使得新的等高线与目标函数的交点的值更大或者更小，这就意味着只有等高线与目标函数的曲线相切的时候， 才可能得到可行解.

  

  因此给出结论：拉格朗日乘子法取得极值的必要条件是目标函数与约束函数相切，这时两者的法向量是平行的，即 $\nabla _xf(x) – \alpha \nabla_x g(x) = 0$

  不等式约束

  当约束加上不等式之后，情况变得更加复杂，首先来看一个简单的情况，给定如下不等式约束问题

  $$\begin{aligned} &\min_x \ f(x) \\ & \ s.t. \ \ g(x) \le 0 \end{aligned}$$

  对应的 Lagrangian 与图形分别如下所示,这时的可行解必须落在约束区域$g(x)$之内，下图给出了目标函数的等高线与约束

  $$L(x, \lambda) = f(x) + \lambda g(x)$$

  由图可见可行解$x$只能在$g(x)\le 0$的区域里取得：

  • 当可行解$x$落在$g(x)<0$的区域内，此时直接极小化$f(x)$即可；
  • 当可行解$x$落在$g(x)=0$即边界上，此时等价于等式约束优化问题。

  当约束区域包含目标函数原有的的可行解时，此时加上约束可行解仍落在约束区域内部，对应$g(x)<0$的情况，这时约束条件不起作用； 当约束区域不包含目标函数原有的可行解时，此时加上约束后可行解落在边界$g(x)=0$上。 下图分别描述了两种情况，右图表示加上约束可行解会落在约束区域的边界上。

  

  以上两种情况就是说，要么可行解落在约束边界上即得$g(x)=0$, 要么可行解落在约束区域内部，此时约束不起作用，令$\lambda=0$消去约束即可， 所以无论哪种情况都会得到： $\lambda g(x)=0$

  还有一个问题是$\lambda$的取值，在等式约束优化中，约束函数与目标函数的梯度 只要满足平行即可，而在不等式约束中则不然，若$\lambda \ne 0$， 这便说明可行解$x$是落在约束区域的边界上的，这时可行解应尽量靠近无约束时的解， 所以在约束边界上，目标函数的负梯度方向应该远离约束区域朝向无约束时的解， 此时正好可得约束函数的梯度方向与目标函数的负梯度方向应相同：

  $$-\nabla_x f(x) = \lambda \nabla_xg(x)$$

  上式需要满足的要求是拉格朗日乘子$\lambda>0$ ，这个问题可以举一个形象的例子，假设你去爬山，目标是山顶，但有一个障碍挡住了通向山顶的路，所以只能沿着障碍爬到尽可能靠近山顶的位置，然后望着山顶叹叹气，这里山顶便是目标函数的可行解，障碍便是约束函数的边界，此时的梯度方向一定是指向山顶的，与障碍的梯度同向，下图描述了这种情况:

  左图中这个$-\nabla_x f(x)$局部最小值指向可行区域（$g(x) \le 0$），也就是还有使得更小的点存在。 而右图中的$-\nabla_x f(x)$局部最小值是远离可行区域的。

  KKT条件

  任何不等式约束条件的函数凸优化问题，都可以转化为约束方程小于0且语义不变的形式，以便于使用KKT条件.
  

  可见对于不等式约束，只要满足一定的条件，依然可以使用拉格朗日乘子法解决，这里的条件便是KKT条件。接下来给出形式化的KKT条件 首先给出形式化的不等式约束优化问题：

  $$\begin{aligned} &\min_x \ f(x) \\ &s.t. \ \ \ h_i(x) = 0 , \ i = 1,2,...,m \ \\ & \ \ \ \ \ \ \ \ \ \ g_j(x) \le 0, \ j = 1,2,...,n \end{aligned}$$

  列出 Lagrangian 得到无约束优化问题：

  $$L(x,\alpha,\beta) =f(x) + \sum_{i=1}^m \alpha_i h_i(x) + \sum_{j=1}^n\beta_ig_i(x)$$

  经过之前的分析，便得知加上不等式约束后可行解$x$需要满足的就是以下的 KKT 条件：

  $$\begin{aligned} \nabla_x L(x,\alpha,\beta) &= 0 \qquad\qquad\qquad\qquad(1)\\ \beta_jg_j(x) &= 0 , \ j=1,2,...,n \qquad(2) \\ h_i(x) &= 0 , \ i=1,2,...,m \qquad(3) \\ g_j(x) &\le 0 , \ j=1,2,...,n \qquad(4) \\ \beta_j &\ge 0 , \ j=1,2,...,n \qquad(5) \\ \end{aligned}$$

  满足 KKT 条件后极小化 Lagrangian 即可得到在不等式约束条件下的可行解。 KKT 条件看起来很多，其实很好理解:

  (1). 拉格朗日取得可行解的必要条件；

  (2). 这就是以上分析的一个比较有意思的约束，称作松弛互补条件；

  (3)-(4). 初始的约束条件；

  (5). 不等式约束的 Lagrange Multiplier 需满足的条件。

  主要的KKT条件便是 (3) 和 (5) ，只要满足这俩个条件便可直接用拉格朗日乘子法， SVM 中的支持向量便是来自于此。

  拉格朗日对偶问题

  https://www.cnblogs.com/ooon/p/5723725.html#4200596 未完，待续

  参考链接

  • 一个经典问题：最短路径问题
  • 曲面上一点求法向量
  • 拉格朗日乘子法与KKT条件
  • lagrange算子
  • KKT
  • http://www.csc.kth.se/utbildning/kth/kurser/DD3364/Lectures/KKT.pdf
  • http://www.csc.kth.se/utbildning/kth/kurser/DD3364/Lectures/Duality.pdf
  • 如何理解拉格朗日算子
  • 从SVM算法理解拉格朗日对偶问题
  Read All

  ---