Collaborative Rating Allocation

1 Introduction

Collaborative prediction aims to predict users' preference based on their previous choices and connections with other users. It has wide applications in industry; for example, in an Amazon book recommendation system, if the system inputs are user ratings on previously read books, predictions of a user's preference of new and unread books are accomplished using patterns discovered from the partially observed rating matrix.

Most collaborative filtering works under the underlying assumption that if user A has the same interest in an item as user B , then A is more likely to have more similar opinions on other items with B than with an arbitrarily chosen user [Breese et al., 1998]. Memory-based methods refer to algorithms that explore similarities among users or items. Of these, neighborhood-based methods are most popular [Lee et al., 2012] and can be divided into two categories: user-based and item-based methods. User-based methods [Breese et al., 1998] identify similar users to the queried user, and the desired rating is then estimated by averaging the ratings of these similar users. Conversely, item-based methods [Sarwar et al., 2001] discover similar items to the queried item and evaluate the desired rating by the average of ratings of these similar items. Different similarity measurements are employed to compute the averaging weights including Pearson correlations [Herlocker et al., 1999], vector cosine [Sarwar et al., 2001], and mean-squared-difference [Papagelis et al., 2005]. Other researchers employ a model-based approach by constructing a parametric model and fit parameters to training data to make predictions of unseen data [Lee et al., 2012]. In addition to these traditional methods, a fairly large body of work describes collaborative prediction from the perspective of matrix factorization. A rating matrix is factorized into a product of two low rank matrices (user profiles and item profiles), which are used to estimate missing entries. Different factorization techniques can be applied such as nonnegative matrix factorization [Lee and Seung, 1999], probabilistic matrix factorization [Salakhutdinov and Mnih, 2011; Lawrence and Urtasun, 2009; Fang et al., 2014], maximum margin matrix factorization [Rennie and Srebro, 2005], and non-linear principal component analysis [Yu et al., 2009].

Existing collaborative prediction algorithms are effective and perform well in diverse applications including book, movie, and music recommendation systems. However, their success is mainly seen in isolated situations where items are rated independently by a user without consideration on their connections. In practice, a user may be required to allocate limited credits to a set of items. In other words, the limited credits owned by the user are split among all items. For example, in cumulative voting, a voter is given an explicit number of points (or votes) to distribute among candidates, while in family financing, a user distributes his (or her) limited money among different financial products based on his (or her) preference or confidence. We refer to this type of user as "energy limited". Thus, existing collaborative prediction algorithms are not applicable to collaborative rating allocation problem, which additionally involves constraints among ratings.

For an energy-limited user, N different items will occupy parts of the energy and together they will use up all the user's energy. The deep-seated truth in this scenario is that the elements in the N-dimensional vector of ratings are not independent. With the observation of the limited budget of a user's ratings, we are motivated to consider users' rating vectors lying on the simplex, i.e., the multinomial manifold [Sun et al., 2016].

In this paper, we investigate the method that emphasizes the connections among ratings of a user. We seat each user's rating vector on the simplex and develop a simplex constrained matrix completion algorithm-referred to as MC-S. In this way, the relations among ratings are intrinsically implied in the model. Rather than using the intuitive distance metric in Euclidean space, a non-linear pull-back metric from sphere is employed to investigate the geometric properties of the data on the simplex. The resulting objective function can be efficiently optimized using a Riemannian conjugate gradient method. Experimental results on real world datasets demonstrate the effectiveness of the proposed method on excavating data's geometric properties.

2 RelatedWork

We first provide a brief review of existing collaborative filtering algorithms, which can be divided into three main categories: memory-based methods, model-based methods, and a new class of matrix factorization methods.

Memory-based methods [Linden et al., 2003] predict new entries according to users who are similar to the queried user. These methods memorize the rating matrix and make recommendations by calculating an aggregate of some similar users ratings of the item [Lee et al., 2012]. Of these memory-based methods, neighborhood-based methods achieve good performance by identifying similar users to the queried user or by identifying similar items to the predicted item. The main similarity metrics include cosine similarity [Sarwar et al., 2001] and Pearson correlation [Herlocker et al., 1999]. However, they have some shortcomings; when there are only a few observed entries, the calculated similarity might be inaccurate, compromising algorithm effectiveness.

Model-based collaborative filtering algorithms [Breese et al., 1998] use the input rating data to learn or estimate a parametric model and then make predictions for unseen entries. Data mining and machine learning algorithms are applied to find the input rating pattern based on the data's statistical properties. Bayesian networks [Su and Khoshgoftaar, 2006] train a Bayesian classifier based on the given training ratings and make predictions on new items [Miyahara and Pazzani, 2002; Song and Zhu, 2016], while clusteringbased collaborative models [Chee et al., 2001; Wang et al., 2015] partition either the set of items or the set of users [OConnor and Herlocker, 1999] based on the rating data as the basis for future predictions. Markov decision processbased collaborative filtering systems [Shani et al., 2002; Su and Khoshgoftaar, 2009] provide better performance than those that do not deploy the system. In addition to the algorithms discussed above, some hybrid methods have been developed that combine the above collaborative filtering algorithms [Ghazanfar et al., 2012]. By combining the strengths of memory and model-based collaborative algorithms, they can result in increased computational complexity.

Recently, plentiful collaborative filtering algorithms are based on low-rank matrix factorizations and they are even further generalized to multi-label and multi-class learning problems [Xu et al., 2016]. In this case, the rating matrix is factorized into a product of two low-rank matrices, thus filling the missing entries. Apart from the basic non-negative matrix factorization [Lee and Seung, 1999], variations include manhattan matrix factorization [Liu and Tao, 2016], probabilistic matrix factorization [Salakhutdinov and Mnih, 2011], maximum margin matrix factorization [Srebro et al., 2004; Rennie and Srebro, 2005], and non-linear principal component analysis [Yu et al., 2009].

3 ProblemFormulation

Take m users and their ratings on n+1 items as a matrix Y ∈ R(n+1)×m, where the j-th column represents user j's ratings on n + 1 items and the i-th row corresponds to the ratings on item i from m users with i ≤ n + 1 and j ≤ m. Indices of observed entries constitute a set Ω. Valid ratings usually settle within a range [0, k]. In the rating allocation problem, the budget of a user's ratings on all items is fixed. Hence, the goal of collaborative rating allocation can be interpreted as filling an incomplete matrix Y with a matrix X whose columns X·j lie on the simplex. An n-simplex Pn is defined as

The simplex Pn is described as a subset of Rn+1 , but it is actually an n-dimensional manifold. In fact, any point on the simplex is a parameter vector x, which itself happens to be a probability vector.

The incomplete matrix Y(n+1)×m can be recovered through a matrix X(n+1)×m with a lower latent dimension

where dist(·, ·) is a distance measurement and PΩ is the sampling operator defined as:

Considering a maximal latent dimension of X ∈ R(n+1)×m as r, we can approximate X by a matrix product X = UV where U ∈ R(n+1)×r acts as the basis on the simplex and V ∈ Rr×m is the corresponding coefficient matrix. We give the constraints on U as

where 1n+1 is an (n+1)-dimensional column matrix of all 1s. Since each individual column of X(n+1)×m lies on the simplex Pn and X·j = UV·j , we get

which implies V T ·j 1r = 1, ∀j. Hence, problem (1) can be reformulated as

where distM(·, ·) refers to the distance on the simplex. Since an n-simplex Pn is a subset of Rn+1 , Euclidean metric is an intuitive choice. However, it has been shown to be inefficient [Le and Cuturi, 2015], since it cannot depict the geometric constraints. Therefore, we propose using a pull-back metric from the sphere to specify the distance on the simplex.

In information geometry, Fisher information metric is a particular Riemannian metric defined on the simplex. Given the diffeomorphism mapping H : Pn ↦ -→ S+n , we consider the pull-back metric from the positive orthant from the sphere S+n , where

The pull-back Fisher information metric (inner product) on the simplex Pn takes the form

which derives the geodesic distance on the simplex

Here 〈·, ·〉 is the Euclidean inner product (more details about simplex can be found in [Sun et al., 2016]).

Based on the aforementioned knowledge on the simplex, we can proceed to specialize Eq. (2) to the simplex Pn to achieve the following model:

By solving the above objective function, we expect to obtain user profiles U and item profiles V , which then produce X to approximate unseen entries in the partially observed Y . In contrast to existing matrix completion methods, the proposed model thoroughly investigates the geometric properties of the data, and thus it can lead to an optimal solution for the challenging collaborative rating allocation problem.

4 Optimization on the Manifold

Optimization of the objective Eq. (3) is split into two subproblems: (i) optimize U and V while X is fixed; and (ii)

optimize X while U and V are fixed. This method refers to the alternating direction method (see [Parikh and Boyd, 2014] for further details). Since X can be updated by X = UV + PΩ(Y - UV ), we only focus on the optimization of (i), which leads to the following subproblem

Eq. (4) is a non-convex function with regard to U and V , so we proceed to update U and V alternately. The objective function Eq. (4) can be decomposed over Ui· row-wise and V·j column-wise. Taking derivatives to Ui· and V·j, we get

where S = (Sj)1×m = (∑n+1 i=1 √Xij · √Ui·V·j)j=1,2,...,m. Since both X·j and UV·j are on Pn, Sj is guaranteed to be not bigger than 1.

We can optimize V·j column-by-column on the simplex Pr-1. As for Ui·, however, row-by-row optimization may violate the constraints among the rows; for example, Uij and Ukj with i ̸= k are not independent given U T ·j 1n+1 = 1. In this case, we cannot optimize Ui· and Uk· independently. To tackle this problem, we consider the product manifold of the multiple simplex manifold

We consider stacking the derivatives of ∂F ∂Ui· , obtain the derivative of U

and then perform manifold optimization on the product manifold.

This approach is convenient because: (i) optimizing on the product manifold Prn intrinsically implies the constraints among the rows of U; and (ii) optimizing the rows of U jointly can parallelize computation and improve numerical efficiency. Although we do not need to jointly optimize V·j , we process it similar to the optimization U to exploit numerical efficiency.

Optimization on a Riemannian manifold is comparable to that on a Euclidean space, that is: (i) finding a descent direction; and (ii) performing a line search to obtain a sufficient decrease and to ensure convergence. In the following section, we discuss the optimization of U in detail to illustrate our optimization method on the simplex. The optimization of V is similar, which is omitted here.

4.1 Conjugate Gradients with the Armijo Line Search Method

The conjugate gradient method is chosen to solve the model in Eq. (4) due to its well-recognized efficiency when applied to large-scale problems.

The conjugate gradient method incorporates gradients at the current point with descent directions from previous points to obtain a new direction. Let f (U) and g(V ) denote F (U, V ) with V and U fixed respectiveely, in Euclidean space, a conjugate gradient method generates a sequence Uk by the following recurrence:

where αk is the step size generated by a line search algorithm, and in Euclidean space ξUk is the descent direction generated by the following rule:

On a Riemannian manifold, the descent direction is computed on the tangent space. This space varies smoothly as one moves along the manifold. At a point U, the tangent space TUPrn is a vector space and is actually a subspace of its embedded Euclidean space,

Given a descent direction ξU ∈ TUPrn , the line-search is performed along a smooth curve on the manifold. The derivative of this curve at U equals the descent direction ξU. After one step movement on tangent space TU, we need to retract it back to the manifold. The retraction operation is defined as a mapping from the tangent space to the manifold. The updating step is concluded by Uk+1 = RUk (αkξUk ).

Unfortunately, the tangent space TUPrn is defined locally at point U, which means ξUk ∈ TUk Prn and ξUk+1 ∈ TUk+1 Prn are in different tangent spaces and might not coincide. This property makes the direct addition of tangent vector ξUk and ξUk+1 impossible. To adapt the conjugate gradient method to manifolds, vector transport needs to be defined to transport tangent vectors from one tangent space to another.

To specify this recurrence to the simplex, we need to define: (i) a projection of the matrix in ambient space into the tangent space; and (ii) a retracting mapping from tangent space to the manifold RUk (αkξUk+1 ).

(i) Projection: the linear operation that projects a matrix Z ∈ Rn×r into the tangent space TUPrn , is defined as

where ⊗ is the element-wise matrix multiplication operation. (ii) Retraction: the mapping that locates the next iteration

to the manifold along the tangent vector RU : TUPrn → Prn is

where ()* denotes the element-wise matrix inversion and exp(·) denotes the element-wise exponential operator.

Let gradf(U) denote the Riemannian gradient in tangent space TUPrn at U; it is calculated by projecting a normalized Euclidean gradient into the tangent space TUPrn ,

Algorithm 1 Alternating Direction Method for Eq. (3)

Input: Y : Incomplete matrix, Ω: sampling set, ϵ: stopping criteria, k: latent dimension, T: max iteration

Output: X: the optimal approximation of Y

• 1: Initialize U0, V0 and X0 = O(n+1)×m
• 2: for t = 1, 2, ..., T do
• 3: Xt = Ut-1Vt-1 +PΩ(Y -Ut-1Vt-1)
• 4: Update Ut :

4a: choose a proper step size τt from Eq.(14) Uinit = -τtgradf(Ut-1) 4b: use Uinit as an initial guess and call RSCG Ut = RSCG(Uinit)

• 5: Update Vt :

5a: choose a proper step size υt from Eq.(14) Vinit = -υtgradg(Vt-1)

• 5b: use Uinit as an initial guess and call RSCG Vt = RSCG(Vinit)
• 6: If 1-F(Ut, Vt)/F(Ut-1, Vt-1) < ϵ; break; end
• 7: end for

The vector transport from the previous tangent space to the current tangent space

is specified by the projection defined in Eq.(8).

Hence the conjugate gradient method can be specified to the simplex

with ξUk = -gradf (Uk) + βk-1TUk-1→Uk ξUk-1 .

4.2 Conjugate Gradients Update Parameter

Several options of βk can be used in the conjugate gradient algorithm. Here we choose the Polak-Ribiere(PR+) method to calculate the CG update parameter. Within the Riemannian optimization framework, βk takes the following form:

Note that the PR+ updating rule has the auto restart property when the descent direction is almost orthogonal to the gradient direction. Specifically, the algorithm will abandon the previous CG descent direction and initialize the CG algorithm according to the current gradient direction.

4.3 Armijo Step Size

The step size αk is chosen with the Armijo line search algorithm. Given the initialized step size α and t, σ ∈ (0, 1), the condition is given by:

where m is the number of backtrackings in finding the current Armijo point. Thus the step size is given by α = tmα.

The initialization of step size α is very important since it can greatly enhance the efficiency of the line search algorithm. In our method, we observe that an exact minization on the tangent space alone without retraction is a good initial guess. For U, the exact minimization takes the form

V takes a similar form so it is omitted here. The minimizer of Eq. (13) takes a closed-form solution:

As ξ is the search direction of U, it is always non-zero when the algorithm has not converged. Therefore, there are no worries about the denominator being zero.

We name our algorithm the "Riemannian Simplex Conjugate Gradient" (RSCG). The convergence of RSCG can be guaranteed by [Absil et al., 2009; Hager and Zhang, 2006] when β is chosen by the PR+ rule and α is chosen by the Armijo condition. The overall algorithm is summarized in Algorithm 1.

5 Experiments

In this section, we evaluate the proposed MC-S on three real-world datasets and compare it with PMF [Salakhutdinov and Mnih, 2007], NPCA [Yu et al., 2009], LGeomCG [Vandereycken, 2013] and LMaFit [Wen et al., 2012]. PMF is a probabilistic matrix factorization model for collaborative filtering that models users' preference by a conditional distribution on user and item matrices ; LMaFit performs baisc matrix factorization while employing non-linear successive over-relaxation algorithm for advancing the effectiveness; NPCA refers to a non-parametric probabilistic PCA model; and LGeomCG performs matrix completion on the manifold of fixed-rank matrices.

Following Marlin's setup [Marlin, 2004], we test our algorithm under "weak" and "strong" generalization. The weak generalization is a single step process that involves directly predicting missing data in the rating matrix. The strong generalization refers to a two-stage process where the models are trained on one set of users and tested on another disjoint set of users. Since LGeomCG cannot explicitly factorize a rating matrix into user profiles and item profiles, it is not applicable for strong generalization. The measurements for matrix recovery are root mean square error (RMSE) and normalized mean absolute error (NMAE):

where Y represents ground truth ratings and X shows estimated values.

5.1 Image Data

We consider two image datasets MIT Scene and UIUC Scene whose properties and parameters are displayed in Table 1. We extract SIFT descriptors on 16 × 16 patches in images and then convert them to bag-of-features (BoF). The number of visual words in the codebook, |V |, is set to be 600 and the implementation is based on vlfeat toolbox [Vedaldi and Fulkerson, 2010].

The BoF representation of each image is the histogram of visual words. Each dimension of a histogram represents the relative frequency of a visual word in the descriptors of an image and the sum of the histogram equals 1. It is an estimation of the probability distribution and is exactly on a (|V |-1)- simplex.

We first extract the BoF features of an image dataset. Define sampling fraction p = |Ω| (n+1)m as the ratio of observed entries to total entries. By setting p = 0.5, we randomly keep 50% of features for fitting collaborative filtering models. Then we split the dataset into training, validation and test sets. In "weak" generalization, we train the collaborative filtering algorithms on the training set and recover the full matrix. Then we train multi-class Support Vector Machine classifiers on the recovered training set by one-vs-all strategy. In "strong" generalization, we train the collaborative filtering algorithms on test set by using the basis matrix learned from training set and hence estimate missing entries in test set. At last we evaluate the performance of SVM classifier on the recovered test set.

Evaluation results

The number of basis points on the simplex r is set to be the number of classes. We random start the training of collaborative filtering algorithms for five times and report averaged RMSE and NMAE in Table 2. We find that MC-S outperforms baselines on two datasets under both "weak" and "strong" generalization. The BoF feature vectors lie exactly on the (|V |-1)-simplex. While comparative algorithms ignore this property, we subtly make use of data's geometric properties and constrain the optimization of each user's rating vector on the simplex, which leads to prominent performance of MC-S. The corresponding classification performance is illustrated in Fig. 2 with sampling fraction p = 0.5.

When sampling fraction p = 1, which means no feature is missing, the averaged classification accuracies of MIT Scene and UIUC Scene are 88.75% and 76.87% respectively. Based on the collaborative filtering results under different sampling fraction p, we repeat the training of SVM for five times, and report averaged accuracies in Fig. 2. With the growing of sampling fractions, all methods witness rising performance. Under different sampling fractions of feature matrix, our method MC-S achieves consistently better performance on UIUC Scene and shows promising efficacy especially when sample size is small. This indicates that our collaborative filtering method implements better approximation to the ground truth feature matrix.

5.2 Recommendation Data

We next explore the proposed MC-S's performance on MovieLens dataset in collaborative filtering [Harper and Konstan, 2015]. ML-1M contains 1,000,209 anonymous ratings of 3,952 movies by 6,040 MovieLens users. 5,000 users are selected for weak generalization and 1,040 users for strong generalization. The input ratings are integers between 1 and 5, and the budget of user j's ratings on items is fixed, i.e., E = ∑n+1 i=1 Yij. We can normalize the data through Y ′ ij = Yij/E, i = 1, 2, ..., n + 1. The pre-processed ratings of user i now lie on the simplex satisfying ∑n+1 i=1 Y ′ ij = 1. By assuming that sampling of Ω is random and unbiased, the budget of one user's ratings on n items is approximated by E ≈ (∑(i,j)∈Ω PΩ(Y ))(n + 1)/Ω. The test and validation sets are created by reserving one rating from each user respectively. This process is repeated three times. We compare the averaged NMAE on three random partitions of weak and strong generalization and report the results in Table 3. After the preprocessing, users' rating vectors lie on the simplex and our method MC-S can preserve this geometric property during the learning of user and item matrices, while baseline methods optimize in the free space and hence gain deficient performance.

Latent dimensionality and efficiency

To test the response of MC-S to increasing latent dimension, we report our testing NMAE under latent dimension from 10 to 1000. In Fig. 3, NMAE shows obvious decreasing trends with the increasing of latent dimension and stays stable between [10, 1000], which indicates that MC-S is steady and can achieve good performance in a large parameter range.

To verify the efficiency of MC-S, changes of NMAE with iterations under different latent dimensionalities in training process are reported in Fig. 3. We find that in weak generalization, MC-S reduces NMAE by every iteration and stays stable after 10 iterations while in strong generalization, MCS becomes steady after only three iterations. We owe this effiency to the representative model learned from weak generalization. The model's representativeness indicates MC-S's capability of learning the geometric properties of users' rating vectors on the simplex.

6 Conclusions

Here we consider collaborative filtering problem with energy limited users. The limited budget of a user's ratings is depicted by the simplex. By seating a user's rating vector on the simplex, we abandon the usual Euclidean metric and employ the pull-back metric from the sphere to specify the distance between points on the simplex, since it can depict geometric constraints of a user's rating vector. We extend conjugate gradient method onto the simplex to optimize our model. Experiments on real data demonstrate our model's effectiveness on learning user and item features.

Acknowledgments

This work is supported by Australian Research Council Projects FT-130101457, DP-140102164, LP-150100671.