使用重疊馬可夫空間計算物件序列模型

Abstract

馬可夫空間(Logistic Markov Embedding)已被驗證為能夠有效學習物件序列模型的演算法。 藉由此演算法，使用者可以從大量的歷史物件序列中，產生類似的新物件序列，藉以達成序列推薦的應用。 但是，由於計算馬可夫空間使用的演算法具有很高的時間複雜度，此演算法幾乎無法應用到實際擁有大量資料的系統之中。 為了增加其實用性與可擴張的規模，已有少數研究成果試著對此演算法進行加速，將原本的物件集合切割成許多小型的集合，並對每個小集合計算獨立的馬可夫空間。 在此論文中，我們提出了一種新的集合分群方式，允許分群後的小型集合彼此在必要的部份重疊。 我們驗證了新的分群方式相對於上述目前最好的加速演算法可以達到更高的準確度，並且可以在相同或是更短的運算時間內完成。

Logistic Markov Embedding (LME) has become a popular branch on the research of sequential item recommendation, such as music playlist generation. But, since LME is an algorithm with very high time complexity, it has a poor scalability and is not able to carry a huge dataset with many items. Hence, several approaches are trying to decrease the time complexity of LME, while keeping the prediction accuracy. In this paper, we present a new speed-up approach for LME, which convert the original item set into several smaller and overlapped clusters, then train a LME for each cluster. We show that this new clustering algorithm is able to get a better performance in a shorter training time compared to the current best speed-up approach.