RIID知識追蹤(一)基於NN方法的SAKT模型(含論文及代碼實現)

RIID！Answer Correctness Prediction比賽是kaggle上近期比較火的比賽，比賽的任務是根據學生的學習行為，預測其下一次的答題情況，這是一個知識追蹤（Knowledge Tracing）任務。

前言

目前，知識追蹤算法主要分類兩大類：（1）基於Markov模型的BKT，（2）基於深度學習的DKT類模型。

相對於BKT，基於深度學習的DKT類算法，因為算法實現更簡單，同時因為深度學習模型能夠更好的捕捉到用戶學習行為中更深層次的一些特徵，所以效果更好。下圖可以很直觀的看出來，DKT算法明顯優於BKT算法。

2015年，Deep Knowledge Tracing這篇論文首次將知識追蹤任務轉換為Seq-to-Seq的任務，並用RNN實現，取得的跨越式的進展。但是，由於DKT用的是RNN，局限性還比較大。

2019年，A Self-Attentive model for Knowledge Tracing這篇論文用Self-Attention模型取代了RNN，取得了更好的性能。同時，後期基於Transformer類的一些論文，可以說都是在SAKT的基礎上進行改進的，因此本篇文章主要是根據論文用pytorch實現模型。

1 數據準備

Knowledge Tracing任務有一些開源的數據集：Synthetic、Assistments、Junyi和Ednet等。下圖是Ednet論文中對比數據集的數據情況。

Kaggle上的RIID比賽是EdNet同一個機構發布的，所以數據內容上差不多。

數據準備很簡單，就不講太多，直接看代碼就可以了。

我們需要將數據進行預處理，每個學生的學習記錄利用group by合併為序列。

# group by
group = train_df[['user_id', 'content_id', 'answered_correctly']].groupby('user_id').apply(lambda r: (
            r['content_id'].values,
            r['answered_correctly'].values))
經過Group by操作後，每個學生都有與之對應的學習記錄。然後需要將問題和答案進行padding補全，並將{q、qa}編碼為模型的輸入。其中：q為問題{content_id}，qa為學生在本問題上的回答情況{0,1}
Dataset代碼如下，關鍵的幾步是：
（1）初始化，每個用戶對應一組訓練數據，用戶集就是整個數據集的大小。
（2）q、qa進行左側padding，對齊到最長序列，不足補全，超出選取最近的100次學習行為
（3）q、qa進行編碼，如果qa==0，則x=q，如果qa==1，則x=q + n_skill。（目的是對q、qa進行one-hot編碼）
class SAKTDataset(Dataset):
    def __init__(self, group, n_skill, max_seq=100):
        super(SAKTDataset, self).__init__()
        self.max_seq = max_seq
        self.n_skill = n_skill
        self.samples = group
     
        self.user_ids = [x for x in group.index]

    def __len__(self):
        return len(self.user_ids)

    def __getitem__(self, index):
        user_id = self.user_ids[index]
        q_, qa_ = self.samples[user_id]
        seq_len = len(q_)

        q = np.zeros(self.max_seq, dtype=int)
        qa = np.zeros(self.max_seq, dtype=int)
        if seq_len >= self.max_seq:
            q[:] = q_[-self.max_seq:]
            qa[:] = qa_[-self.max_seq:]
        else:
            q[-seq_len:] = q_
            qa[-seq_len:] = qa_
        
        target_id = q[1:]
        label = qa[1:]

        x = np.zeros(self.max_seq-1, dtype=int)
        x = q[:-1].copy()
        x += (qa[:-1] == 1) * self.n_skill

        return x, target_id, label
2 模型定義
SAKT模型結構很簡單，模型輸入學生的學習記錄 ，模型輸出下一次測試 的結果。
模型的輸入是用戶的0～k-1次的學習行為：
（1）x：{i1, i_k-1}，經過編碼後的學習表現
（2）question：{e1, e_k}
輸出是用戶第K次的表現：
（1）r_k：{0，1}
模型如下圖，主要由：Embedding layer、Self-attention layer、Feed Forward layers、Prediction layer組成。
2.1 Embedding layer
Embedding層將輸入的題目信息和答題信息編碼為Embedding矩陣。
SAKT有倆個矩陣，M和E。M是Interaction embedding，並加入Position encoding，E是exercise矩陣。
# 定義
self.embedding = nn.Embedding(2*n_skill+1, embed_dim)
self.pos_embedding = nn.Embedding(max_seq-1, embed_dim)

self.e_embedding = nn.Embedding(n_skill+1, embed_dim)

# 計算
x = self.embedding(x)
pos_id = torch.arange(x.size(1)).unsqueeze(0).to(device)
pos_x = self.pos_embedding(pos_id)
x = x + pos_x

e = self.e_embedding(question_ids)
2.2 Self-attention layer
Self-attention layer採用scaled dotproduct attention mechanism。
Self-attention的query、key和value分別為：
# 定義
self.multi_att = nn.MultiheadAttention(embed_dim=embed_dim, num_heads=8, dropout=0.2)

# 計算
att_output, att_weight = self.multi_att(e, x, x, attn_mask=att_mask)
2.3 Feed Forward layer
用一個簡單的前向傳播網絡將self-attention的輸出進行前向傳播。
# 定義
class FFN(nn.Module):
    def __init__(self, state_size=200):
        super(FFN, self).__init__()
        self.state_size = state_size

        self.lr1 = nn.Linear(state_size, state_size)
        self.relu = nn.ReLU()
        self.lr2 = nn.Linear(state_size, state_size)
        self.dropout = nn.Dropout(0.2)
    
    def forward(self, x):
        x = self.lr1(x)
        x = self.relu(x)
        x = self.lr2(x)
        return self.dropout(x)
 
self.ffn = FFN(embed_dim)

# 計算
x = self.ffn(att_output)
2.4 Prediction layer
self-attention的輸出經過前向傳播後得到矩陣F，預測層是一個全連接層，最後經過sigmod激活函數，輸出每個question的概率。
x = self.pred(x)
pred = torch.Sigmoid(x)
3 模型訓練
模型的目標是預測用戶答題的對錯情況，利用cross entropy loss計算（y_true, y_pred）。
優化器選擇Adam，learning_rate設置為0.001。
optimizer = torch.optim.Adam(model.parameters(), lr=1e-3)
criterion = nn.BCELoss()
4 模型驗證
因為是Kaggle上舉辦的比賽，我們直接將結果提交到kaggle平臺，在平臺的測試集上查看模型的auc。
kernel已經開源：https://www.kaggle.com/wangsg/a-self-attentive-model-for-knowledge-tracing
總結
RIID的這個比賽是近期非常值得關注的一個比賽，目前在kaggle上公開的方案主要是採用的ML方法，我們復現了SAKT算法，並開放了提交的完整代碼，開放的Baseline模型AUC為0.751，是目前開源KT類模型中效果最好的。
可以根據我開放的baseline做進一步的工作，復現SAINT+等基於Transformer的模型，單模型的AUC可以輕鬆達到0.77+。後期我也會視情況考慮公開性能更好的KT模型。
參考
https://github.com/wsg011/kt
A self-attentive model for knowledge tracing
https://www.kaggle.com/wangsg/a-self-attentive-model-for-knowledge-tracing
既然看到最後了，那感謝點讚分享，謝謝你的鼓勵！
歡迎關注微信公眾號：kaggle數據分析。