learning DLsite trend function by rankNet
簡介：
此篇文章記錄我使用 rankNet 來學習日本大型的二次元類型產品數位發行平台 DLsite 中的熱門排名公式。這篇文章會包含問題定義、演算法簡介、資料集處理、結果、總結。完整程式碼可以在我的 github 上找到。
learning to rank：
在 DLsite 中，存在產品熱門排名頁面，假設該網站並沒有用一些未公開的數據來當作排序依據，我們就可以猜測網站中存在某種用於排序的公式。
例如圖中第三名的作品在銷量、收藏、評價上明顯不高於第四名，但其發售時間是較第四名新的，所以其排序依據大概是某種融合時間與熱門指標的公式。
學習排序的機器學習演算法可以根據學習目標大致分成三類：
- point wise：每個物品都存在一個用於排序的依據分數，直接讓演算法學習該分數，把問題轉換為一般的 regression 問題。
- pair wise：跟程式中自定義排序規則時一樣，演算法只需要回答每兩兩物品之間的排序關係，間接學習該分數。
- list wise：演算法需要回答一串物品之間的排序關係，一樣屬於間接學習分數。
point wise 的優勢在於將排序問題轉換成 regression 後，許多 regression 演算法都能不修改就直接用來解問題。缺點在於不容易公平地對每個物品標上`絕對`分數，資料標籤的取得與定義都不容易。相較之下 pair wise 與 list wise 是比較貼近原目標的學習方式。
rankNet：
來源：Burges, Chris, et al. "Learning to rank using gradient descent." Proceedings of the 22nd international conference on Machine learning. 2005.
這次使用的 rankNet 是 2005 的發表的 pair wise learning to rank 演算法。
rankNet 的概念就是由一個孿生網路分別計算兩個物品的分數後，相減後計算 sigmoid。將其輸出視為物品 1 應該排序在物品 2 之前的機率。
paper 內則寫的更學術、嚴謹一些，公式 (2) 就是該機率，公式 (1) 則是相對應的 loss function，binary cross entropy。
|
device = None
def getDevice():
global device
if device is None:
device = 'cuda' if torch.cuda.is_available() else 'cpu'
return device
class RankNet(nn.Module):
def __init__(self):
super().__init__()
self.linear1 = nn.Linear(12, 16)
self.tanh = nn.Tanh()
self.linear2 = nn.Linear(16, 16)
self.linear3 = nn.Linear(16, 1)
def forward(self, x):
out = self.linear1(x)
out = self.tanh(out)
out = self.linear2(out)
out = self.tanh(out)
out = self.linear3(out)
return out
def train(dataloader, model, lossFunction, optimizer, l1Weight = 0):
model.train()
for batch, (X, y) in enumerate(dataloader):
X, y = X.to(getDevice()), y.to(getDevice())
optimizer.zero_grad()
X1 = X[:, 0]
X2 = X[:, 1]
score1 = model(X1)
score2 = model(X2)
out = score1 - score2
loss = lossFunction(out, y)
|
孿生網路在架構圖示上通常都會顯示兩個架構一樣、參數共用的網路，在程式上其實就是寫一個網路就可以了，training 時讓兩個輸入分別通過網路後再做後續的相減即可。
dataset：
implicit feedback
不少 paper 的主題是有關如何從用戶的點擊紀錄來產生 pair wise 的 training data，例如：當用戶點擊第二順位物品時，代表該 context 下有`第二順位物品 > 第一順位物品`這樣的一個 pair。
不需要用戶主動告知我們喜好、也不須人為介入，僅從一般閱讀行為的 server log 即可輕易取得的 implicit 足跡就能產生訓練資料，就是 pair wise 的最大優勢。
relative relevance
相對相關性指的 dataset 有時會處在不同的 context 下，這時候兩 context 之間就無法作比較。
例如上圖，艾爾登法環與薔葳的夜宴是兩款不一樣類型的遊戲、熱度上也有天壤之別，所以我們不容易將兩者的評論作比較。
這點如果是使用 pair wise、list wise 時只需要在處理資料時分開產生 pair、list 即可。但在 point wise 則必須要找出某種分數讓兩者可以被公平比較，這也是前面提到 point wise 分數不好設定的一個範例。
preprocessing
資料的取得相當簡單，不需要特別準備爬蟲。
|
let itemRankedATag = document.getElementsByClassName('work_thumb_inner');
let itemIds = [];
var itemIdPattern = new RegExp('\.([A-Z]+[0-9]+)\.html');
for (let i = 0; i < itemRankedATag.length; i++) {
let hrefUrl = itemRankedATag[i].getAttribute("href");
let match = itemIdPattern.exec(hrefUrl)
itemIds.push(match[1]);
}
console.log(JSON.stringify(itemIds));
|
進入 DLsite 熱門頁面後，最多一次可以顯示 100 筆資料，用簡易的 JS 語法就能一次取出 100 筆商品排名。
商品特徵屬性則可以觀察 DLsite 頁面的 ajax，網站本身就有提供取得特徵屬性的 api 可以利用。
|
// item rank
[itemId01, itemId02, itemId03]
// item feature
{
itemId01: [1, 42, 1000,… 1718643747],
itemId02: [2, 215, 950,… 1718642458],
itemId03: [3, 195, 660,… 1718645528]
}
// pairs
[
[[1, 42, 1000,… 1718643747], [2, 215, 950,… 1718642458]],
[[1, 42, 1000,… 1718643747], [3, 195, 660,… 1718645528]],
[[2, 215, 950,… 1718642458], [3, 195, 660,… 1718645528]]
]
|
依照 pair wise 的需求，需要將，item rank 與 item feature 組合成 pairs 的資料形式。
|
// item rank
[itemId01, itemId02, itemId03]
// pairs
[
[itemId01, itemId02],
[itemId01, itemId03],
[itemId02, itemId03]
]
// item to index
{
itemId01: 0,
itemId02: 1,
itemId03: 2
}
// item feature
[
[1, 42, 1000,… 1718643747],
[2, 215, 950,… 1718642458],
[3, 195, 660,… 1718645528]
]
|
但因為這樣最終的 pairs 會是 item feature 的排列組合、充滿很佔記憶體的冗於資料，所以改成 pairs 只儲存 item id，真的要訓練時再從 item feature 中取出相對應的資料。
|
class PostivePairsDataset(Dataset):
def __init__(self, rankItem, item2Index, itemFeature):
self.item2Index = item2Index
self.itemFeature = numpy.array(itemFeature)
self.postivePairs = order2postivePairs(rankItem)
def __len__(self):
return len(self.postivePairs)
def __getitem__(self, idx):
postivePair = torch.tensor(numpy.stack((
self.itemFeature[self.item2Index[self.postivePairs[idx][0]]],
self.itemFeature[self.item2Index[self.postivePairs[idx][1]]]
)), dtype=torch.float32)
postiveLabel = torch.tensor([1], dtype=torch.float32)
return postivePair, postiveLabel
def order2postivePairs(order):
pairs = [list(pair) for pair in combinations(order, 2)]
return pairs
|
最後這裡有另外一個值得一提的是 rankNet 只需要正樣本就可以學習了，原因在於其孿生網路的結構，如果網路會因資料樣本正負偏差而只輸出 1 或 0，那代表網路需要在忽略輸入的同時，在第一個物品輸入時輸出大、第二個物品輸入時輸出小，但後者條件是網路無法感知的，網路不會知道現在輸入的順序與次數更不可能在同樣權重下輸出大又輸出小。最終 rankNet 本身的優秀結構讓它只能學習輸入值並給予相對應的輸出，不會受到資料正負樣本偏差影響。
training & result：
將排序列表以九比一的比例分割成 training、testing data。
最終結果如圖所示，可以從右圖看出雖然有些許偏差，但 rankNet 能大致學到排序的規則。以數據來看則有 test accuracy 78%、NDCG 0.94 的成績。
NDCG 是排序與推薦常用的指標，顧名思義，Cumulative Gain 代表他會累加分數，Discounted 則是越前方的物品會獲得越多的加權 (往後遞減)、Normalized 正歸化代表其範圍在 0 ~ 1。要注意的是 NDCG 的累加代表怎麼排序都能拿到分數，差別只在於加權較少，導致其不太容易出現 0.5 以下的分數，通常要 0.7 以上才算是不錯的成績。
distribution shift：
covariate shift
如果今天是一般的實作的話就到剛剛那部分就結束了，不過我還想探討另一個問題。
當我們在聲音類 ASMR 作品 training rankNet，並在遊戲類作品做 testing。
結果比預想的還要糟糕，accuracy 降低不少，只剩下 56%。這個問題發生的原因在於雖然 training data 與 testing data 在排序的分數上有相似的規則，但其特徵之間相差過大，出現太多模型在訓練期間沒有見過的輸入。
更數據一點說明，當我們針對 12 個特徵做統計檢定可以發現，當我們在同一個聲音類 ASMR 作品中做 training、testing 時，training data 與 testing data 在大部分的特徵維度上都沒有顯著差異 (α = 0.01)。
而當我們在聲音類 ASMR 作品以及遊戲類作品兩項數據做 training、testing 時，training data 與 testing data 在大部分的特徵維度上都有顯著差異 (α = 0.01)。
此現象被稱為 distribution shift，在 Dive into deep learning 一書中有完整的介紹。
|
Sometimes models appear to perform marvelously as measured by test set accuracy but fail catastrophically in deployment when the distribution of data suddenly shifts Statisticians call this covariate shift because the problem arises due to a shift in the distribution of the covariates (features). |
來源：Zhang, Aston, et al. "Dive into deep learning." arXiv preprint arXiv:2106.11342 (2021).
而這種因輸入特徵分布不一所導致的問題又被特別稱為 covariate shift。這次的 covariate shift 是我自己替換 testing data 到其他作品類型所產生的，但實際上 covariate shift 在 learning to rank 遇到的機率不低，如果我們的輸入特徵有包含熱度 (下載量、PV、點擊數等)，那會非常容易受到外部影響而產生爆炸性的變動。
此圖是 Google Trends 上的進擊的巨人查詢熱度。假設我們設計的是販售動漫周邊商品的購物網站，那很顯然當進擊的巨人在最火的完結篇階段時，用戶的使用量會上升造成 covariate shift，讓 ranking 不穩定，進而導致讓網站在最能賺錢的時候錯失良機。
L1、L2 regularization
降低 covariate shift 的其中一個方法是避免模型 overfitting，當模型更 generalization 時遇到 shift 的衝擊就更小。在這邊使用 L1、L2 regularization 來避免 overfitting，L1、L2 可以利用 Lagrange 乘數法嚴謹的證明其效用，但我通常使用較不嚴謹、簡易的方式來說明它。
來源：Zhang, Aston, et al. "Dive into deep learning." arXiv preprint arXiv:2106.11342 (2021).
可以將 regularization 視為在原本的 loss function 之上再添加一個懲戒 function，這樣模型就必須在兩個條件的拉扯下做權重優化，而 λ 就是控制懲戒強度的參數。
來源：Prince, Simon JD. Understanding deep learning. MIT press, 2023.
可以看到如果想要降低 L2 regularization 的懲戒 function 就必須讓模型內的權重盡可能的小，這部分的想法是來自於當權重小，模型就無法擬合出太複雜的曲線，來達到 generalization 的目標。
加上 regularization 後，可以看出不只 overfitting 的問題緩解外，test accuracy 也提升至 58%。
|
==========================
originalCurrentRateRecords
originalMean: 0.56
originalStd: 0.01
==========================
modifiedCurrentRateRecords (l1l2)
modifiedMean: 0.58
modifiedStd: 0.00
==========================
hypothesisTesting
Ttest_indResult(statistic=-6.314052380768227, pvalue=2.1129290951895752e-07)
KruskalResult(statistic=26.708447531443582, pvalue=2.3658493954024695e-07)
==========================
|
數據上也能進行統計檢定加入 regularization 前後是有顯著差異的。
normalization testing data
這時候我突發奇想，我遇到的 shift 問題應該是類似圖中左側，不同作品類型的熱度導致模型看見沒看過的數字。那如果我向右側一樣，testing data 使用自己獨立的 normalization 呢？這個依據是來自於我認為 pair wise ranking 應該只需要兩兩相對大小就能計算，不需要絕對的數值。同時這也能保證模型不可能再看見未曾見過的數字。
|
==========================
originalCurrentRateRecords
originalMean: 0.56
originalStd: 0.02
==========================
modifiedCurrentRateRecords (shareScaler = False)
modifiedMean: 0.56
modifiedStd: 0.02
==========================
hypothesisTesting
Ttest_indResult(statistic=1.1578581965511585, pvalue=0.254147756569922)
KruskalResult(statistic=2.6346406455244944, pvalue=0.10455571570292992)
==========================
|
很顯然事情沒這麼順利，這麼做之後的結果與原本共用 normalization 時沒有顯著差異。但研究有趣的地方就在於其未知相關性，當你把幾個效能不佳的東西湊在一起時，有時候反而有奇效，當然也有反過來的時候。
|
==========================
originalCurrentRateRecords
originalMean: 0.56
originalStd: 0.02
==========================
modifiedCurrentRateRecords (l1l2、shareScaler = False)
modifiedMean: 0.61
modifiedStd: 0.01
==========================
hypothesisTesting
Ttest_indResult(statistic=-11.262083804733697, pvalue=1.1346763672447975e-13)
KruskalResult(statistic=28.839030684057438, pvalue=7.865007317601521e-08)
==========================
|
當我同時使用 L1、L2 regularization + normalization testing data 兩個技巧後，regularization 依舊發揮其緩解 overfitting 的能力外，test accuracy 又進一步的提升至 58%。
最後則秀出四種排序的前九名，分別是，左上正確答案、右上原始模型、左下加了 L1L2 regularization、右下加了 L1L2 regularization 與 normalization testing data，紅色點點代表有出現在正確答案上的前九名。
conclusion：
結論上我會認為 rankNet 雖古老但優點依舊很多，而且使用上容易、對超參數也沒有太敏感，如果沒有要求極高的正確率，只是要大致學出 generalization 的排序公式，那它是不錯的選擇。
而 covariate shift 部分是所有 learning to rank 都需要注意的問題，再往下還有幾種方法可以處理。
使用更複雜的解法
後續我查詢了一下有許多研究目標本身就是在緩解 covariate shift，例如 online learning 讓 shift 盡量不存在、根據 testing data 的分布 adaptive 模型的參數或輸入等方法。
使用不依賴訓練資料的方法
covariate shift 發生的原因在於模型已經學到了太多 training data 的資料分布，以這個方向來看，若是使用不依賴 training data 的模型就能緩解這個狀況。
例如：
簡單到沒有本錢學過頭的 linear regression。
不依賴 training data 的黑箱優化，Evolutionary Computation。
hybrid method
最後則是可以 hybrid 的使用這些方法，我們可以利用簡易的統計檢定來判定現在資料是否 shift 了。若沒有就使用原始較高正確率的模型，若有就使用較 generalization 的模型或是開始 online learning 調整模型。
參考資料：
以上就是這次的分享，感謝看到這邊的你，最後附上參考資料以及完整程式碼
[1] 完整程式碼
https://github.com/avengerandy/rankNet
[1] DLsite 官方網站
https://www.dlsite.com/index.html
[2] Google Trends
[3] Burges, Chris, et al. "Learning to rank using gradient descent." Proceedings of the 22nd international conference on Machine learning. 2005.
[4] Radlinski, Filip, and Thorsten Joachims. "Query chains: learning to rank from implicit feedback." Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining. 2005.
[5] Joachims, Thorsten. "Optimizing search engines using clickthrough data." Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. 2002.
[6] Zhang, Aston, et al. "Dive into deep learning." arXiv preprint arXiv:2106.11342 (2021).
[7] Prince, Simon JD. Understanding deep learning. MIT press, 2023.
留言列表
