牛頓法於因子分解機之應用

Abstract

矩陣分解在推薦系統上是一個普及的應用，它可以根據已看過的資料去預測使用者對商品的評分。矩陣分解是因子分解機的一種特例，後者的優勢在於能有效地處理稀疏的資料。一般而言，牛頓法可以有效地解大規模的迴歸問題，然而，因為因子分解機的目標函數是非凸函數，牛頓法無法應用於因子分解機。在這篇論文中，我們考慮了一種因子分解機的變形，其在解子問題時目標函數會變成凸函數。相較於交替地解子問題，我們直接將高斯牛頓法應用於此種變形的因子分解機。同時我們在矩陣分解的實作上，也利用其特性而達到降低空間複雜度。我們的實驗顯示應用於此種因子分解機的高斯牛頓法很有潛力。

Matrix factorization (MF) is a popular technique for collaborative filtering. With observed ratings given by $m$th user to $n$th item, MF aims to find a model such that we can use it to predict the unobserved rating of a user on an item. MF is a special case of Factorization Machines (FM) which can model all interactions between variables using factorized parameters so that FM are able to estimate interactions even in problems with huge sparsity (like recommender systems). For the training of large-scale regression problem, Newton methods have been shown to be an effective approach, but it is difficult to apply such methods to FM because of the non-convexity. We consider a modification of FM that is multi-block convex and usually solved by alternating minimization algorithms. In this work, we apply Gauss-Newton method to the modification of FM instead of alternately switching between solving sub-problems. Furthermore, we introduce an effective implementation for MF to reduce the memory consumption. Through experiments in this work, we compare the Gauss Newton method with the alternating Newton method and show the effectiveness of our algorithm.