Machine Learning Concept（一）：Mean Average Precision（mAP）

Machine Learning Concept（一）：Mean Average Precision（mAP）

2018/05/08

前言：

R-CNN 系列已經看了一陣子，YOLO 系列是目前正在看的。要知道這些演算法有多好，你得先知道「好」的標準何在？

Summary：

物件偵測 [1] 的第一步應該是瞭解 mAP 的計算方式 [2]-[11]。本文從基本觀念 [2]-[6] 出發，另外找了相關討論 [7]-[9] 與原始碼 [10]，最後是補充資料 [11]。相關資料再配上本文的說明，讀者應可對物件偵測有初步的瞭解。

-----



Fig. 1. Object detection [1].

-----

Outline

一、Object Detection
二、IoU
三、Precision / Recall
四、Average Precision（11-point interpolated average precision）
五、Average Precision（PASCAL VOC 2010）
六、Mean Average Precision
七、mAP@[.5 .95]
八、公式（程式）

-----

一、Object Detection

Mean average precision（mAP）是 object detection 演算法的評估標準。

Object detection，一般翻譯為物件偵測或物體偵測。如圖1 所示，一張圖片，或一個影片的停格，先框出物件，再根據框框裡的物件加以分類，標示名稱，這就是 object detection。

傳統較有名的物件偵測演算法有 DPM、Selective Search 等，新一代的深度學習演算法則有 R-CNN 系列與 YOLO 系列 [1]。

-----
 
二、IoU

一般 object detection 演算法會先在一些資料集上進行訓練與測試，例如 PASCAL 等 [4]。資料集先由人工（或專家）將物件的框框與類別設定好。

演算法選出的框框，不會（不一定會）百分之百與人工設定的框框符合，將這兩個框框的交集除以聯集，是一個判斷標準，一般是設定為 0.5，高於這個值，則表示演算法「偵測」到一個物件，如圖2 所示 [2]。

至於偵測的「物件」是否「存在」，或者這個物件是否被標示為正確的類別，這在下方會繼續說明。

Fig. 2. Intersection over union [2].

-----

三、Precision / Recall

Precision / Recall 有一些不同的翻譯名稱，在此直接以英文跟圖片加以理解。

Precision / Recall，看圖3 則一目了然。

圓圈裡，是所有檢測到的物件（positives），淺綠色的部分是標示正確的（true positives），粉紅色的部分是標示錯誤的（false positives）。

左邊的矩形，是所有應該檢測出來的物件，半圓裡的部分是檢測出來的（true positives），半圓以外的部分，是沒有檢測出來的（false negatives）。

Precision，是演算法偵測到的物件總數裡，有幾成是正確的物件。
Recall 則是全部該偵測出來的物體，演算法檢測出幾成。

Fig. 3. Precision and Recall [3].

-----

四、Average Precision（11-point interpolated average precision）

圖4.1a 是一個測試結果，類別假定為汽車好了。

你偵測出「可能」有 20 輛汽車，其「可能性」從 0.91 遞減到 0.01。但是實際上，真正的汽車只有 4 號的 0.91、2 號的 0.76、9 號的 0.38 等六輛。




Fig. 4.1a. Top 20 [4].

以圖4.1b 為例，假定你「選」前五名好了，那你的正確率就是 2 / 5，也就是 0.4。




Fig. 4.1b. Top 5 [4].

「實際多類別分類任務中，我們通常不滿足只通過 top-5 來衡量一個模型的好壞，而是需要知道從 top-1到 top-N（N 是所有測試樣本個數，本文中為20）對應的 precision 和 recall。顯然隨著我們選定的樣本越來也多，recall 一定會越來越高，而 precision 整體上會呈下降趨勢。把 recall 當成橫坐標，precision 當成縱坐標，即可得到常用的 precision-recall 曲線。」[4]




Fig. 4.1c. Top 6 - 20 [4].

圖4.2 可以看到，Top 1 是 1 / 1，Top 2 是 2 / 2。
Top 3 到 Top 5 分別是 2 / 3、2 / 4、2 / 5。垂直遞減。
Top 6 與 Top 7 分別是 3 / 6、4 / 7。遞增。 
Top 8 到 Top 20 以此類推。


 

Fig. 4.2. Average Precision（11-point interpolated average precision）[4].

-----

五、Average Precision（PASCAL VOC 2010）

PASCAL 競賽在 2010 年開始，使用不同的計算方式。

圖4.3 跟 圖4.1 是同一份資料，但呈現、與計算的方式不同。主要是它沒有遞增的片段，全部是單調遞減。

執行上是以 Recall 為主，同樣 Recall 的取為一組，這組後面如果有更大的 Precision，就以後面為主。

以圖4.3為例。第三組的 Precision 是 3/6，但因為第四組的 4/7 更高，所以就採用第四組的 Precision 當成第三組的。因此得到圖4.4。

Fig. 4.3. Top 20 [4].

Fig. 4.4. Average Precision（PASCAL VOC 2010）[4].

-----

圖4.5 可以看出兩種方法的差別。AP 則是計算藍色部分所佔的比率。

Fig. 4.5. Precision monotonically decreasing [2].

-----

六、Mean Average Precision

瞭解了 AP 之後，mAP 其實就是把多個類別的 AP 再取平均。如圖5.1 所示。

Fig. 5.1 mAP [2].

圖5.2 則是 FP 跟 TP 個數的統計。這邊會有一個小問題，就是每個類別的物件要一樣多才公平嗎？

Fig. 5.2. Detected classes (36) [2].

-----

七、mAP@[.5 .95]

mAP@[.5:.95](someone denoted mAP@[.5,.95]) means average mAP over different IoU thresholds, from 0.5 to 0.95, step 0.05 (0.5, 0.55, 0.6, 0.65, 0.7, 0.75, 0.8, 0.85, 0.9, 0.95). [6]

IoU 取 0.5 可以計算 mAP，從 0.5 到 0.95 每 0.05 都來算一次 mAP 再平均，又是一種衡量的標準。

-----

八、公式（程式）

以上的觀念都瞭解之後，程式部分請自行參考 [7], [10]。

-----

Conclusion

瞭解 mAP 是 object detection 的第一步，至於如果同一物件被重複偵測，有好幾個類似的框框，那要如何處理？這也是很重要，後續會再討論！

-----

References

一、背景

[1] 關於影像辨識，所有你應該知道的深度學習模型 – Steven Shen – Medium
https://medium.com/@syshen/%E7%89%A9%E9%AB%94%E5%81%B5%E6%B8%AC-object-detection-740096ec4540

二、基本

[2] GitHub - Cartucho_mAP  mean Average Precision - This code will evaluate the performance of your neural net for object recognition
https://github.com/Cartucho/mAP 

[3] Precision and recall - Wikipedia
https://en.wikipedia.org/wiki/Precision_and_recall

[4] 多标签图像分类任务的评价方法-mAP_花心大罗博_新浪博客
http://blog.sina.com.cn/s/blog_9db078090102whzw.html

[5] The PASCAL Visual Object Classes Challenge 2010 (VOC2010)
http://host.robots.ox.ac.uk/pascal/VOC/voc2010/

[6] computer vision - What does the notation mAP@[.5 .95] mean  - Data Science Stack Exchange
https://datascience.stackexchange.com/questions/16797/what-does-the-notation-map-5-95-mean 
 
-----

三、討論

[7] mean average precision（MAP）在计算机视觉中是如何计算和应用的？ - 知乎
https://www.zhihu.com/question/41540197

[8] machine learning - mAP metric in object detection and computer vision - Stack Overflow
https://stackoverflow.com/questions/36274638/map-metric-in-object-detection-and-computer-vision

[9] machine learning - How to calculate mAP for detection task for the PASCAL VOC Challenge  - Data Science Stack Exchange
https://datascience.stackexchange.com/questions/25119/how-to-calculate-map-for-detection-task-for-the-pascal-voc-challenge

-----

四、code

[10] 深度学习  mAP (Mean Average Precision) - CSDN博客
https://blog.csdn.net/JNingWei/article/details/78955536

-----

五、其他

[11] What you wanted to know about Mean Average Precision - FastML
http://fastml.com/what-you-wanted-to-know-about-mean-average-precision/