本文作者來(lái)自丹麥和意大利，曾設(shè)計(jì)ann-benchmarks獲得ANN領(lǐng)域廣泛關(guān)注。

編者的思考

1. 只選了數(shù)據(jù)集中的點(diǎn)當(dāng)做query，可能會(huì)有bias。
2. LID, expansion, RC和圖索引算法的設(shè)計(jì)邏輯并不匹配，包括最終的評(píng)估效果也一般，文章沒有提供強(qiáng)有力的結(jié)論。
3. 平均recall，和平均query time，都隱藏了很多實(shí)際性能分布，不適宜作為benchmark的度量。

Abstract

• 本文提出的LID, RC, query expansion三個(gè)度量，可以為現(xiàn)實(shí)數(shù)據(jù)集選擇各種難度的query。
• 調(diào)查了目前常用的多個(gè)數(shù)據(jù)集，發(fā)現(xiàn)并不是很多樣，在一個(gè)數(shù)據(jù)集上的結(jié)果往往能代表在其他數(shù)據(jù)集上的結(jié)果。

1 Introduction

• 很多數(shù)據(jù)集不是真正高維的，即可以通過(guò)一些手段把數(shù)據(jù)集映射到低維，使得數(shù)據(jù)間的距離不會(huì)有太多失真。

  • 本征維數(shù)(ID)就是允許有這樣性質(zhì)的最低維度。
  • JL轉(zhuǎn)換，PCA，都可以用作低維嵌入的實(shí)際手段。

• 本文重點(diǎn)關(guān)注維度的局部度量方式，即局部本征維數(shù)LID, query expansion，和Relative Contrast (RC)，以及它們?nèi)绾斡绊懥瞬樵冃阅堋?/p>

  • LID: 給定一個(gè)點(diǎn)q, 和一個(gè)距離r，LID描述了區(qū)分距離q, r和(1+)r的點(diǎn)的難度。
  • expansion：描述了knn和2knn到q距離的比值。
  • RC：1NN和距離數(shù)據(jù)集中其它所有點(diǎn)的均值的比值。

• 實(shí)驗(yàn)包括兩組：

  1. 固定一個(gè)數(shù)據(jù)集，根據(jù)三個(gè)度量將Query分成easy, middle, hard三組，觀察實(shí)際查詢性能的區(qū)別。【LID表現(xiàn)不錯(cuò)】
  2. 觀察不同的度量值分布，在不同數(shù)據(jù)集上如何影響運(yùn)行時(shí)間分布?！救魏我粋€(gè)度量對(duì)實(shí)際性能分布的預(yù)測(cè)都不準(zhǔn)】
  • 其中，第一組實(shí)驗(yàn)用了qps-recall curve來(lái)表征，但作者認(rèn)為平均recall會(huì)隱藏很多insights。
    • 比如說(shuō)，對(duì)于圖索引來(lái)說(shuō)，查詢精度的方差特別大，而對(duì)于其他類型的索引方差就會(huì)小很多。
  • 最后，作者想要選出一組代表性數(shù)據(jù)集來(lái)benchmark各類索引。然而現(xiàn)實(shí)benchmark中的數(shù)據(jù)集多樣性很差：各索引排名基本一致，但各索引在不同數(shù)據(jù)集上性能表現(xiàn)不同。

4 Datasets

• 下圖是在三個(gè)度量上的各數(shù)據(jù)集直方圖（以數(shù)據(jù)集中點(diǎn)當(dāng)做query），k=100。均為偏態(tài)、長(zhǎng)尾分布，Expansion是log軸。

• 從后面的結(jié)果來(lái)看，各個(gè)度量的中位數(shù)將數(shù)據(jù)集難度排名，和實(shí)際性能排名基本一致，但有兩個(gè)例外：LID和Expansion預(yù)測(cè)錯(cuò)了SIFT和Glove的順序，RC弄錯(cuò)了MNIST。所以都不太能預(yù)測(cè)的準(zhǔn)。

  
  
  image.png

• 三個(gè)度量的相互關(guān)系：相關(guān)性并不強(qiáng)

  
  
  image.png

• 根據(jù)LID，各選了10000個(gè)Easy, middle, hard的點(diǎn)當(dāng)做query

• 從定性上來(lái)看，LID能選出更難的Query來(lái)

  
  
  image.png

• 固定算法為Annoy，一個(gè)隨機(jī)映射樹索引，比較三種度量對(duì)query的選擇性

  
  
  image.png

• 固定Recall為0.9，查看不同難度query set的性能下降比例

• LID下降的最多

  
  
  image.png

• 再次固定算法為Annoy索引，LID為度量，點(diǎn)狀虛線是middle的，實(shí)線是diverse的，middle要比diverse更難。作者解釋實(shí)際上這些索引達(dá)到高Recall是通過(guò)讓Diverse中的簡(jiǎn)單query精度打滿，而非提升難Query的精度。

• 另外，F(xiàn)ashion-MNIST雖然在分類難度上遠(yuǎn)大于MNIST，但是ann的難度上卻差不多。

  
  
  image.png

5.4 Diversity of Results

• 用LID選出來(lái)的middle query set做benchmark。
  【為什么不用diverse呢？】

• NDC和QPS排名差距很大，這點(diǎn)很奇怪。

  
  
  image.png

5.5 Reporting the Distribution of Performance

• 各種索引在glove-2m數(shù)據(jù)集上的性能，但不僅僅是Recall-time curve，對(duì)于每一個(gè)點(diǎn)，都畫了關(guān)于橫軸的分布（上圖是各點(diǎn)recall的分布，下圖是各點(diǎn)的QPS的分布）

• 下面這組圖中，IVF和Annoy峰度很高，說(shuō)明對(duì)所有query的NDC差不多，方差很小，其余三個(gè)則展現(xiàn)出雙峰形態(tài)。

  
  
  image.png

• 固定ANNOY和glove-2m數(shù)據(jù)集，（也許固定了ndc？），畫出recall和measure的格子圖，都一般。

  
  
  image.png