What in the hell is the AP and mAP?

Detection都做了两个月了，对AP（average precision）和mAP（mean average precision）的理解还是似懂非懂。

其实这个东西，适用面很广，在text retrieval, classification等问题中都有应用，或者说，只要是广义的分类问题都可以用AP来做metric。

具体操作就是，将某一个类的detect到的目标，按照score降序排列，从recall为0开始（也就是第一个目标开始），依次往后加入目标，这样recall肯定是一个递增的趋势（但不一定是严格递增），而precision的话，过程中有增有减，但是总的趋势还是降低的，这样就可以画出这个类的PR曲线了，比如：

recall = 当前score之前的TP/所有的TP
precision = TP/(TP+FN)

严格的AP就是这个PR曲线下的面积，mAP就是所有类AP的算术平均。

但是一般都是用逼近的方法去估计这个面积，比如
approximated precision的方法：每个recall point都approximate，计算每个矩形面积求和（下图红色虚线）
Interpolated Precision的方法：从每个recall point往后看，用最大的precision作为插值来，计算每个矩形面积求和（下图蓝色虚线）

从PASCAL VOC 2007开始，就是用的类似Interpolated Precision的方法，不过稍有不同的是，VOC使用的是在固定的11个recall（[.0,.1,.2,.3,.4,.5,.6,.7,.8,.9,1.]）的地方取precision然后来近似AP，所以又叫11-point interpolated average precision。

而从PASCAL VOC 2010开始，又摈弃了11-point interpolated average precision的计算方法，取而代之的是用所有的(recall, precision)数据点（只要是recall有改变的地方）来计算AP。具体而言就是，取所有recall改变的数据点及其后的最大的precision作为当前recall的precion（这样就能得到一条单调递减的(recall, precision)曲线）来计算矩形面积，然后累加所有小矩形，即得AP。
（下图来自VOC2012的devkit文档）

用上述方法分别算出各个类的AP，然后取平均，就得到mAP了。AP的计算可以直接统计该类别下的TP，FP和postitive number的总数，然后就可以一次性算出AP了。得到了各类的AP，mAP就是各类别AP的算术平均！mAP的好处是可以防止AP bias到某一个数量较多的类别上去。

================================================================

这里截取一些SSD源码中，对应计算AP的代码片段：

caffe.proto

  // ap_version: different ways of computing Average Precision.
  //    Check https://sanchom.wordpress.com/tag/average-precision/ for details.
  //    11point: the 11-point interpolated average precision. Used in VOC2007.
  //    MaxIntegral: maximally interpolated AP. Used in VOC2012/ILSVRC.
  //    Integral: the natural integral of the precision-recall curve.
  optional string ap_version = 42 [default = "Integral"];

bbox_util.cpp

void ComputeAP(const vector<pair<float, int> >& tp, const int num_pos,
               const vector<pair<float, int> >& fp, const string ap_version,
               vector<float>* prec, vector<float>* rec, float* ap) {
  const float eps = 1e-6;
  CHECK_EQ(tp.size(), fp.size()) << "tp must have same size as fp.";
  const int num = tp.size();
  // Make sure that tp and fp have complement value.
  for (int i = 0; i < num; ++i) {
    CHECK_LE(fabs(tp[i].first - fp[i].first), eps);
    CHECK_EQ(tp[i].second, 1 - fp[i].second);
  }
  prec->clear();
  rec->clear();
  *ap = 0;
  if (tp.size() == 0 || num_pos == 0) {
    return;
  }

  // Compute cumsum of tp.
  vector<int> tp_cumsum;
  CumSum(tp, &tp_cumsum);
  CHECK_EQ(tp_cumsum.size(), num);

  // Compute cumsum of fp.
  vector<int> fp_cumsum;
  CumSum(fp, &fp_cumsum);
  CHECK_EQ(fp_cumsum.size(), num);

  // Compute precision.
  for (int i = 0; i < num; ++i) {
    prec->push_back(static_cast<float>(tp_cumsum[i]) /
                    (tp_cumsum[i] + fp_cumsum[i]));
  }

  // Compute recall.
  for (int i = 0; i < num; ++i) {
    CHECK_LE(tp_cumsum[i], num_pos);
    rec->push_back(static_cast<float>(tp_cumsum[i]) / num_pos);
  }

  if (ap_version == "11point") {
    // VOC2007 style for computing AP.
    vector<float> max_precs(11, 0.);
    int start_idx = num - 1;
    for (int j = 10; j >= 0; --j) {
      for (int i = start_idx; i >= 0 ; --i) {
        if ((*rec)[i] < j / 10.) {
          start_idx = i;
          if (j > 0) {
            max_precs[j-1] = max_precs[j];
          }
          break;
        } else {
          if (max_precs[j] < (*prec)[i]) {
            max_precs[j] = (*prec)[i];
          }
        }
      }
    }
    for (int j = 10; j >= 0; --j) {
      *ap += max_precs[j] / 11;
    }
  } else if (ap_version == "MaxIntegral") {
    // VOC2012 or ILSVRC style for computing AP.
    float cur_rec = rec->back();
    float cur_prec = prec->back();
    for (int i = num - 2; i >= 0; --i) {
      cur_prec = std::max<float>((*prec)[i], cur_prec);
      if (fabs(cur_rec - (*rec)[i]) > eps) {
        *ap += cur_prec * fabs(cur_rec - (*rec)[i]);
      }
      cur_rec = (*rec)[i];
    }
    *ap += cur_rec * cur_prec;
  } else if (ap_version == "Integral") {
    // Natural integral.
    float prev_rec = 0.;
    for (int i = 0; i < num; ++i) {
      if (fabs((*rec)[i] - prev_rec) > eps) {
        *ap += (*prec)[i] * fabs((*rec)[i] - prev_rec);
      }
      prev_rec = (*rec)[i];
    }
  } else {
    LOG(FATAL) << "Unknown ap_version: " << ap_version;
  }
}

================================================================

从上面可以看出，AP的计算方法还是有几种不同方法的，所以在比较算法的时候，一定要确保使用的是相同的AP计算方法，否则对比就不严格。比如说使用的是VOC2007那样的interpolated AP，那么就可能会存在高估算法性能的可能。

本文参考了：https://sanchom.wordpress.com/tag/average-precision/ （刚发现连SSD源码中的caffe.proto文件都引用了这个网址。。）以及SSD源码