1 引用
Haoran Niu and Iman Keivanloo and Ying Zou. Learning to rank code examples for code search engines. Empirical Software Engineering, 2017, 22(1):259-291.
2 摘要
開發者通常會從已有的解決方案中學習使用源代碼示例來實現一些自己不熟悉的編程任務。為了更好地支持開發者查找已有解決方案，代碼搜索引擎旨在查找和排序與用戶查詢相關的代碼示例。本質上，代碼搜索引擎提供了一種排名模式，該模式整合了一組排序特徵來計算查詢和候選代碼示例之間的相關性。接著，排名模式將相關聯的代碼示例放置在結果列表的頂部。然而，很難主觀確定排名模式的配置。。在本文中，我們提出了一種代碼示例搜索方法，該方法應用了機器學習技術來自動地訓練排名方案。我們使用訓練後的排名方案在運行時對新查詢的候選代碼示例進行排名。我們使用從 586 個開源 Android 項目中爬取的超過 360,000 個代碼段的語料庫來評估該方法的排名性能。性能評估研究表明，學習排名方法可以有效地對代碼示例進行排名，並且在歸一化累計折損增益（NDCG）和預期倒數排名（ERR）度量方面，它們分別比現有的排名方案高出約 35.65％和 48.42％。
3 技術介紹
排名模式指定如何在運行時組合一組排序功能以產生最終的排序結果集。然而，我們很難主觀地確定現有排名方案的配置（即參與排名方法的特徵或其特徵的權重）。在本文中，我們使用了排序學習技術來自動調整排名模式的配置。排序學習是一種機器學習方法，主要應用於信息檢索系統的排名方案。開發人員可以使用排序學習技術來自動構建性能比最佳配置更好的排名模式，而無需為配置問題而苦惱。
3.1 總體流程
如圖 1 所示，我們的代碼搜索方法的整個過程包括四個主要階段：1）抓取 Android 項目；2）提取特徵；3）學習排名模式；4）為新查詢排名候選代碼示例。其中前三個步驟可以通過離線的方式完成，第四個步驟發生在運行時，我們方法的輸入是一個查詢語句（類+方法名）以及代碼片段語料庫。對於指定的查詢，系統會從語料庫中檢索包含查詢中指定的類或方法名稱的所有代碼段，計算查詢和代碼段之間的餘弦相似度。我們選擇與查詢最相似的代碼段作為候選代碼段。最後使用經過訓練的排名方案對候選人進行排名。
圖 1. 用於構建排名模式的代碼片段推薦流程圖
3.2 提取特徵
在本節中，我們描述了用於訓練排名模式的方法中使用的代碼示例特徵。總體而言，我們採用瞭如表 2 所示的 12 種特徵。我們將功能分為四類：文本相似性，受歡迎程度，代碼指標和上下文相似度。此外，我們可以將特徵分為兩組：依賴於查詢的特徵和不依賴於查詢的特徵。
表 2. 選用代碼示例的特徵
A. 文本相似度
我們首先使用 TF-IDF 將查詢語句和候選代碼示例轉化為空間向量的形式，之後通過如下公式計算兩個空間向量的餘弦相似度來表示文本相似度。
B. 受歡迎程度
有關代碼搜索和推薦的最新研究中使用受歡迎程度來識別具有更高接受率的候選答案。受歡迎程度表示代碼片段與在源代碼語料庫中經常觀察到的常見實現方式的接近程度。基本原理是，與語料庫中的通用模式越接近，開發人員接受推薦代碼段的機會就越大。受歡迎程度可以使用頻率或概率兩個維度進行評估。
使用頻率來衡量受歡迎程度：首先提取候選代碼片段中的方法調用的有序序列，並使用頻繁項集挖掘技術，分析語料庫來識別語料庫中的通用使用模式，之後我們通過計算每個候選代碼片段的和通用模式之間的餘弦相似度，最後將最相似的一種使用方式視為該代碼示例的通用實現方式。
C. 代碼度量
代碼度量標準組包含四組用於代碼搜索和代碼質量預測的代碼度量標準。代碼度量是一組與查詢無關的功能。表 2 總結了我們的方法中使用的代碼度量指標：
- 代碼行和標識符數量：代碼行和每行標識符的平均數量可以用來預測代碼的可讀性。
- 調用序列長度：代碼片段的調用序列中方法調用數量。
- 註釋與代碼的比例：代碼片段中註釋的佔比。
- 扇入，扇出和頁面排名：用於衡量代碼片段的複雜性, 扇入定義為調用特定代碼段的代碼片段數。扇出描述了被特定代碼段調用的數量。頁面排名通過計算指向特定代碼示例的調用量來確定代碼片段的重要性。
D. 上下文相似度
上下文相似性是指查詢上下文與候選代碼段之間的相似性。我們使用代碼示例的方法簽名和查詢片段的方法簽名分別表示代碼示例和查詢的上下文。通過識別其駝峰命名法方式將方法簽名拆分成令牌集合。之後使用 Jaccard 方法計算上下文的相似度。
3.3 訓練排名模式
在我們的方法中，我們使用一種學習排序算法來訓練排名模式，該算法由 Freund 等人提出，稱為 RankBoost。RankBoost 是一種高效算法，對我們的訓練數據的訓練過程只需幾分鐘。
排序學習算法的輸入是訓練數據，其中包含與一組查詢相關的候選代碼示例。每個代碼示例均以（q，r，Vc）形式表示為一條記錄，其中 q 表示查詢 ID； r 表示查詢 q 與候選代碼示例 c 之間的相關性，由專家進行標記；Vc 是包含代碼示例 c 的不同特徵值的向量。算法 1 顯示了生成最終排名 H 的 RankBoost 算法的詳細學習過程。
4 案例研究
為了評估我們的代碼示例搜索方法的性能，我們進行了一個案例研究。本案例研究的目標有兩個：（1）評估我們提出的方法的有效性；（2）比較研究特徵對我們方法性能的影響。
4.1 創建訓練和測試數據集
我們的訓練和測試數據集是一組查詢和候選代碼示例，首先從語料庫中隨機選擇一個代碼片段，作為預期答案。然後，通過從期望答案的代碼片段中隨機選擇一個方法調用，並提取該方法調用中的類和方法，轉化為針對期望答案的查詢。
要為我們的方法創建訓練數據集以學習如何對代碼示例進行排名，我們需要提供查詢及其候選代碼示例之間的相關性。 查詢和候選答案之間的相關性由代表相關等級的標籤描述。 我們使用廣泛接受的多等級絕對相關性判斷方法進行標記。具體來說，我們使用四個相關性級別，即優，良，中，差。我們要求評估者為每對查詢分配相關性標籤和候選人的答案。評估人員需要通過將候選答案與查詢的預期答案進行比較來判斷每個查詢與候選答案之間的相關性。
4.2 方法性能評估
我們通過確定由我們的方法產生的排名結果列表的優劣來評估排序模式的性能。由於結果列表中使用了多等級的相關性來度量，需要我們使用分級的相關性指標來評估結果列表。並且開發人員始終對前 k 個答案感興趣，因此我們使用擴展的評估方法 k-DCG 和 k-ERR 來強調對前 k 個答案進行排名的重要性。
4.3 基線對比
我們將已有排名方法中使用的排名模式概括為五種，包括隨機排名，相似性排名，加權總和排名，優先級排名和重排名。我們列出了五個現有的排名模式，如下所示：
- 隨機排名：對結果集中的候選答案進行隨機排名。在機器學習研究中，衡量相對於隨機猜測的優化情況是一種常見的做法。
- 相似性排名：基於候選代碼示例與相應查詢的文本相似性對它們進行排名。
- 加權總和排名：對代碼示例不同特徵的加權求和來計算查詢和候選代碼示例之間的相關性值。
- 優先級排名：基於主要特性對代碼示例進行排名，如果兩個代碼示例的主要特性相同，則使用次要特性對兩個代碼示例進行排名。
- 重排名：將使用次要特徵對由主要特徵確定的前 k 個候選答案進行重新排名。
最後，我們還將我們的方法與商業代碼推薦系統 Codota 進行了比較。更具體地說，Codota 是唯一能夠對 Android 代碼示例進行排名的公開代碼示例搜索引擎。 Codota 中使用的排名算法可識別常見、可信和清晰的代碼段。
5 實驗結論
RQ1: 對於代碼示例搜索，學習排名方法是否優於現已有的排名方法？
如下圖 2 所示，我們使用 10-NDCG 和 10-ERR 對比我們的排學學習方法和其他基線方法。最終結果如下圖所示，我們的排名學習方法可以勝過其他幾種基線方法，在 10-NDCG 和 10-ERR 指標上分別平均提高了 35.65％和 48.42％
圖 2. 使用 10-NDCG 進行評估，我們的方法與現有排名方案之間的績效評估研究結果
RQ2：代碼示例的研究功能對我們的方法是否同樣重要？
我們的實驗方法是將特徵中的一個的權重設置為隨機值來構建一個新的排名模式，當特徵值隨機化後，就可以和原排名進行比較，來判定該特徵的重要程度。結果如下表所示，文本相似性，頻率和上下文相似性是在代碼示例搜索和推薦中影響最大的三個特徵。
RQ3：我們使用的排序學習技術是否優於 Codota？
通過用戶研究實驗，我們選取 5 位評估員分別對我們的方法以及 Codata 的方法在推薦有效代碼數量上面進行比較，最終結果如下圖 3 所示，我們的學習排名方法比 Codota 的性能高出 44％。
圖 3.我們的學習排名方法和 Codota 的首選候選代碼示例數量方面的比較結果
4 本文主要貢獻
在本文中，我們做出了以下貢獻：1）提出一種代碼示例搜索方法，該方法應用機器學習從訓練數據中自動學習排名模式；2）使用包含 50 個查詢條件以及 2500 個用於 Android 應用程序開發的代碼示例的訓練和測試數據集來評估我們的方法。評估結果表明，與現有的排名模式和在線搜索引擎相比，我們的方法可以有效地對候選代碼示例進行排名併為開發人員推薦相關的代碼示例。
致謝
感謝國家重點研發計劃課題：基於協同編程現場的智能實時質量提升方法與技術（2018YFB1003901）和國家自然科學基金項目：基於可理解信息融合的人機協同移動應用測試研究（61802171）支持！
本文由南京大學軟件學院 2018 級碩士生門鐸翻譯轉述。
閱讀更多 慕測科技 的文章
