刷頁還是刷專題：ACM競賽做題之道
論文：<Automatically Learning Topics and Difficulty Levels of Problems in
Online Judge Systems>發表時間：2017
發表期刊：ACM Transactions on Information Systems (CCF A類期刊)
作者：WAYNE XIN ZHAO, WENHUI ZHANG,
YULAN HE，XING XIE, JI-RONG WEN
單位： Renmin University of China， Aston University，Microsoft Research
論文鏈接：有意者郵箱聯繫 frankwhzhang@126.com
前言：作為在線教育的一種形式，在線評測系統（Online Judge System,簡稱OJ）近年來廣泛應用於編程、數學、工作面試等多個領域。在線評測系統提供大量的、快速增長的題目並且自動檢測，是無指導的自學習平台。在傳統的課程設計中，主題與難度是和題目相關的兩個重要因素。題目的展現形式往往是按照頁面和題號簡單排列，由於題目是快速生成和載入的，所以往往並沒有題目的標註。
關鍵詞：主題學習，能力學習，在線評測系統
一、 寫作動機。
簡單的按照頁面呈現題目很難快速找到相關的資源。比如新手想要找一些適合自己難度的題目，需要花費很長時間，一個專註於做「動態規劃」問題的人也很難快速找到自己想做的題目。以上兩個問題分別涉及到了題目的難度和主題維度，由於在線評測系統的題目是快速生成和載入的，往往並沒有題目的主題和難度標註。因此這篇文章通過挖掘用戶的學習軌跡來自動進行主題學習和能力學習。
二、 論文框架。
通過分析用戶的學習軌跡，我們發現了兩種主要的學習模式。一種是簡單的順序思維模式（volume-oriented learning），按照頁面的默認順序進行題目學習;另一種是按照主題的思維（topic-oriented learning），從不同頁面中選擇同一主題連續學習.為了刻畫這兩種學習模式，我們採用了雙模式馬爾科夫主題模型，設計出兩種主題，頁面主題（volume topic）和技能主題（skill topic）分別表示兩種學習模式。一個用戶可以以一定的概率選擇某種模式，在這種模式下在一定的概率選擇某個主題，進而生成相應的題目，整體構成生成模型框架進行主題學習。
除了主題學習，我們採用了一種新穎的模型來刻畫問題的難度，通過數據分析，我們發現一個用戶在不同的興趣或者主題上的能力是有差異的。傳統的能力模型中，將能力或者難度用單個值表示，而我們的模型採用了主題敏感的競爭性能力模型，一個用戶的不同主題上設定了不同的能力值。我們假定一個問題也是一個特殊的虛擬用戶，一個用戶對一道題目的正確與否，就表示為在這道題目的主題背景下的兩者能力強弱表示，通過大量用戶提交的評測結果，構建出用戶與題目之間的競爭模型，最終生成每一個用戶或者題目在不同主題下的能力。題目的主題背景來源於第一部分對題目的主題學習。
我們的論文框架如下圖所示，通過主題和能力的兩部分學習，最終我們又提出了模型的三種應用場景和評估方式，分別是問題分類，能力檢測和問題推薦。
三、 問題定義
a) 用戶做題序列（UAS），由三元組<q, s, l> 組成，分別表示題號，時間戳和做題結果。一個用戶的軌跡行為按照時間排序，由若干個這樣的三元組構成。
b) 能力競爭三元組（ECT），<u, u』, q> 兩個用戶在題目q上的競爭結果，題目是一種特殊的用戶。
四、 實驗數據
如下圖所示，我們總共爬取了三個網站的數據，分別是POJ、Timus和HDU。、
五、 模型介紹
a) 第一部分採用了雙模式馬爾科夫主題生成模型，如下圖所示。
b) 第二部分基於 Bradley-Terry comparison model，考慮到一個用戶在不同主題下有著不同的能力，如下圖所示。
六、 實驗設置
a) 主題學習的應用及評估方法。
i. 評估方法
1. 標註數據中主題之間的相似度。
2. 生成的主題中的純度。
3. 新題目的分類準確度。
ii. Baseline
1. LDA， LDA text， HMM， HTMM
b) 能力學習的評估方法
i. 準確率（ACC）
ii. Baseline
1. Trueskill，Bradley-Terry，PageRank，Blade-chest，AC Rank
c) 用戶問題推薦的評估
i. 評估方法
1. 4:1 隨機切分訓練集與測試集
2. 推薦最後10個
ii. Baseline
1. UserKNN，PMF，BPR，NCF，TOP，MC，FPMC，HRM
七、 總結與貢獻
a) 首先提出了自動學習主題和難度用於在線評測系統的模型
b) 量化分析了用戶的學習行為，提出了兩種行為模式。
c) 量化分析了在不同主題上難度的差異，進而提出了一個新穎的能力比較模型
d) 基於多個數據源的實驗結果表明，在三個應用場景中表現出色。
推薦閱讀：