We propose to use two lectures (out of the given triplet of three lectures) in order to define a direction of prediction, which includes the set of predicted lectures accompanied by the corresponding frequencies. The relevance of the whole predicted set is calculated according to the remaining third lecture. Further improvements were achieved with homogeneous ensembles, based on the random sampling known, also, as bagging. The experimental results were obtained online during the VideoLectures.Net ECML/PKDD 2011 Discovery Challenge (Track N2).
The core problem (and the main subject of this study) lies around the second issue: how to give the right direction to a generation of learners, who live on the Internet, in the wide space of the available research/educational resources.
Recommender systems attempt to profile user preferences over items, and model the relation between users and items. The task of recommender systems is to recommend items that fit a users tastes, in order to help the user in selecting/purchasing items from an overwhelming set of choices [2]. Such systems have great importance in applications such as e-commerce, subscription based services, information filtering, etc. Recommender systems providing personalized suggestions greatly increase the likelihood of a customer making a purchase compared to unpersonalized ones. Personalized recommendations are especially important in markets where the variety of choices is large, the taste of the customer is important, and last but not least the price of the items is modest. Typical areas of such services are mostly related to art (esp. books, lectures, movies, music), fashion, food and restaurants, gaming and humor.
The most of the methods presented and discussed in [2] were motivated by the famous Netflix Cup. Those methods, where matrix factorization is the most common, cannot be applied in our case directly, because the structure of the data is different. In our case we are dealing not with a specific users, but with abstract users who had seen in the past a triplet as a set of three given lectures, where an exact sequence of lectures is not given. We shall consider in Section 4 one suitable modification (as a prospective direction) of the gradient-based matrix factorization (GMF) [6] as an example of stochastic gradient descent algorithm.
Traditional data mining techniques such as association rules were tried with good results at the early stages of the development of recommender systems [3]. Frequent item sets, discovered as part of association rule mining, represent the least restrictive type of navigational patterns, since they focus on the presence of items rather than the order in which they occur within user session [4]. Frequency-based methods are the primary tool in the following below Sections 3.1 - 3.6. Note, also, that Markov decision processes provide a more advanced model for recommender systems (in the case if the sequence of the states is given). According to the Markov Chain Model, we are dealing with a finite space of possible states, and, using a maximum-likelihood estimate (applied to the historical data) as a transition function, we can formulate a prediction [5].
Bagging predictors is a method for generating multiple versions of a predictor and using these to get an aggregated predictor. The aggregation averages over the versions when predicting a numerical outcome and does a plurality vote when predicting a class [7]. In Section 3.6 we consider method of random resampling: it is supposed that using the hundreds of predictors (base learners) based on the subset of the whole training set we shall reduce the random factors. According to the principles of homogeneous ensembling, the final predictor represents an average of base predictors. As a reference, we mention random forests as a well-known example of successful homogeneous ensemble. However, the construction of random forests is based on another method, which is linked to the features but not to the samples. 0.1 0.2 0.3 0.4 0.6 0.7 0.8 0.9 5 10 15 20 30 35 40
45 0.5 (a) 25 (b) (c) 1 50
The training database includes two sets named 1) pairs P and 2) triplets T with two parts left and right, where the left part contains input triplets and the corresponding numbers of views, the right part contains output lectures and the corresponding numbers of views. 2.1
Let us denote by IP set of indexes corresponding to the pairs data. Any element of IP represents a set (without order) of two lectures I = {a, b}, where I ∈ IP . We shall understand under PI = Pab number of times lectures a and b were viewed/seen together. 2.2
Let us denote by IT set of indexes corresponding to the triplets data. The element with index I ∈ T has two values (one for the left, and one for the right parts): τI = {a, b, c} is a triplet or a set of three lectures a, b and c. Under TI we shall understand the number of times those three lectures were seen together. Further, LI is a set of single lectures, which were seen after τI . Under TI (ℓ), ℓ ∈ LI , we shall understand the number of times lecture ℓ was seen after the triplet τI . 2.3
where all the values in Figure 1(b) were truncated to 50, Figure 1(c) illustrates histogram of the values PI bigger than 50, which were truncated to 500.
The task of the Challenge was to make predictions according to the test dataset V , which has the same structure as T (left part). In more details, the task was to make a recommendation of the ten the most appropriate lectures after viewing the given triplet. Remark 1. As a particular and very important feature of this Challenge, we note the absence of the same triplets in both training T (left part) and test V sets. At the same time, we can report a very significant proportion of the same sets of two lectures (couples) in both training and test sets.
In total, we found nc = 34756 couples, with number of record (which were extracted from the right part of T ) per couple ranging from 1 to mc = 4020. Note that any triplet may be considered as a set of three couples. There are NV = 60274 triplets in the test set V , and 1) we did not find any related couples in the training set only in 116 cases, 2) we found one couple in 829 cases , 3) we found two couples in 4705 cases, and 4) we found all three couples in an absolute majority of 54624 cases.
Remark 2. Any lecture is identified by the index, where the biggest index is nL = 13251. However, not all nL lectures were used. We had assumed that the predicted lectures should be found in the right part of T , where we identified only ns = 5209 different lectures. Some preliminary definitions We shall explain how the system works in the terms of the ns secondary indexes, because the transformation to the original nL indexes is a trivial one. Our database was organised as follows. Squared matrix A with sizes ns × ns contains nc different addresses of the matrix B with sizes nc × mc.
Firstly, we shall find three couples αij , j = 1, . . . , 3, for any triplet τi, i = 1, . . . , NV , in the test dataset V . Then, for any couple αij we shall find (according to the matrix A) the corresponding address β(αij ) (in the matrix B) and the number of records n(αij ), where 1 ≤ β ≤ nc, 1 ≤ n ≤ mc.
Under the element of matrix B we shall understand predicted/recommended lecture
ℓ and the corresponding frequency
{ℓ, rτ (ℓ)},
(
Remark 3. The main advantage of the above method is its speed: the algorithm will go through the whole test set V and will output required solution for the Track N2 within 5 min.
An update process Now, we shall describe the most critical step of the computational process. Any particular triplet τ from the test dataset is to be considered in an identical manner, so we omit index i in order to simplify notations.
Suppose that initially all the ratings are set to zero s(ℓ) = 0, ℓ = 1, . . . , ns, where s(ℓ) is the rating of the corresponding lecture ℓ which will be used for the final ranking as an output of this model.
This is the most important update formula
s(Bβk(
After computation of the vector s according to (
Remark 4. In the case if the number of positive values in the vector s is smaller compared to the required 10, we shall generate remaining indexes at random assuming that the indexes are different compared to 1) the indexes of the input triplet τi plus 2) those indexes which were selected already.
The method, as described above produced the score on the Leaderboard 0.49568, where the detailed definition (with numerical examples) of the Competition score is available from the web-site of the PKDD 2011 Contest. 3.2
Essentially, predictions with singles (single lectures) work similarly as predictions with couples. However, there are some differences, which could be treated as simplifications. We had found that the maximum number of the records corresponding to the single lecture is ms = 77798. Accordingly, the matrix Bb (as a replacement to the matrix B in the previous Section 3.1) has sizes ns × ms.
The model works in the following way: by definition, any triplet represents a set of three lectures ℓj, j = 1, . . . , 3. We shall find the number of records 1 ≤ n(ℓ) ≤ ms, where 1 ≤ ℓ ≤ ns.
An update process Again, initial ratings of lectures are set to zero: s(ℓ) = 0, ℓ = 1, . . . , ns.
This is the main update formula
s(Bbℓjk(
After computation of the vector s according to (
The method, as described above produced the score on the Leaderboard 0.33278. 3.3
Definition 1. We shall call that the lectures a and b are P-linked if Pab ≥ 1. According
to the symmetric matrix P, we define set H(a) of all P-linked lectures to the lecture a.
An update process As before, initial ratings of lectures are set to zero: s(ℓ) = 0, ℓ =
1, . . . , ns. Then, we shall apply an update formula
s(d)+ = P (ℓj , d), d ∈ H(ℓj), j = 1, . . . , 3,
(
After computation of the vector s according to (
The method, as described above produced the score on the Leaderboard 0.12677. Remark 5. The solution, as described in this section, was recommended by the Organisers on the forum as “simple pairs solution”.
Note, also, that during our numerous experiments we made a very interesting observation/discovery.
Remark 6. Statistics defined in (
According to the above three sections, predictions with the couples produced best results. We decided to go further and to take into account remaining third lectures φ and ψ in both training and test sets.
Motivation: in the case if remaining (“extra”) lectures φ and ψ are closer (have bigger number of the joint views according to the pairs data), the predicted direction, corresponding to the related couple, must be given bigger weight.
As it was discussed in Remark 1, lectures φ and ψ are different by definition. In other words, the corresponding (“similar”) triplets in the training and test datasets may be represented as
αj ∪ φj , αj ∪ ψj , where φj 6= ψj , j = 1, . . . , 3.
An update process As before, initial ratings of lectures are set to zero: s(ℓ) = 0, ℓ =
1, . . . , ns. Then, we can re-write (
After computation of the vector s according to (
The method with weighted couples, as described above, produced very significant improvement on the Leaderboard 0.58145. 3.5
This section may be regarded as an extension of Section 3.2. In some sense, prediction with weighted singles is similar to the prediction with weighted couples, Section 3.4. However, there are some differences. In the case of singles, we are defining direction of the prediction according to the single lectures. Accordingly, we have two other (“extra”) lectures, which should be compared properly with two lectures in the corresponding triplet of the training data.
An update process Updates were conducted according to
s(Bbℓjk(
= 0.0005(P (φ1j, ψ1j )P (φ2j , ψ2j ) + P (φ1j , ψ2j )P (φ2j , ψ1j )) + 0.01.
The motivation behind the above formula is a very simple: we must ensure that any “extra” lecture from the test triplet is close to at least one “extra” lecture from the train triplet.
After computation of the vector s according to (
The method, as described in this section, produced the score 0.4529 on the Leaderboard. 3.6
In this section computation of the single ranking vector s was based on 75% of randomly
selected samples. In an absolute majority of all 60274 test instances, the number of
positive components of the vector s defined in (
Let us denote vector of secondary ratings as z, which is set to zero at the beginning of the whole resampling process. We conducted 200 random samplings (global iterations). After any global iteration, only 100 top lectures (components of the vector z) received increments ranging from 1 to 100 votes (bigger for better performance). The method which we used within any global iteration (base learner) is described in Section 3.4.
After completion of all 200 global iterations, we sorted vector z in a decreasing order, and the arguments (indexes of the lectures) corresponding to the ten biggest z (from the top to the bottom) were submitted as a solution.
The final model with resampling, as described above, produced the following score on the Leaderboard 0.58727. This solution was used as a final.
The distances in the above Table 1 were computer using simplified version of the PKDD 2011 Contest evaluation method. Any solution represents an integer matrix of NV × 10, T = 10NV integer indexes in total. By comparing two matrices, we shall find the number of common indexes (intersection) in any row. The total number of all intersections will give us a numerator R, and the required distance represents a ratio
D =
R T
.
A Linux multiprocessor workstation with speed 3.2GHz and 16GB RAM was used for the most of the computations, which were conducted according to the specially developed codes in C. The computation of the final solution, as described in Section 3.6, was conducted overnight and took about 12 hours. 4
The main idea behind an approach of this section is to factorize the transition matrix X of a Markov chain (or matrix of frequencies) [9].
By definition, X is a squared symmetrical matrix with size ns, and any element of X reflects similarity between the corresponding lectures (the bigger value indicates the higher level of similarity).
Further, we shall consider factorization of the matrix X
′
X ∼ GG ,
(
We shall compute matrix X according to an update formula, which is very similar to
(
In this section, boldface capital letters denote matrices or vector-columns, while normal letters denote elements of matrices. Also, it will be convenient for us to use notation xab = x(a, b).
We now describe the procedure for undertaking the matrix factorization (
n−1 n L(A) = X X
e2ab, a=1 b=a+1 where eab = xab − Pk
f=1 gaf gfb.
The above target function (11) includes in total kn regulation parameters and may be unstable if we minimise it without taking into account the mutual dependence between elements of the factor matrix G.
As a solution to the problem, we can go consequently through all the differences eab, minimising them as a function of the particular parameters which are involved in the definition of eab. Compared to usual gradient-based optimisation, in our optimisation model we are dealing with two sets of parameters, and we should mix uniformly updates of these parameters, because these parameters are dependent.
Algorithm 1: Gradient-based matrix factorization. 1. Input: X - similarity matrix. 2. Select M - number of global iterations; k ≥ 1 - number of factors; λ > 0 - learning rate. 3. Initial similarity matrix G is generated randomly. 4. Global cycle: repeat M times the following steps 5 - 15: 5. external-cycle: for a = 1 to ns − 1 repeat steps 6 - 15: 6. internal-cycle: for b = a + 1 to ns repeat steps 7 - 15:
Remark 7. The content within this section represents rather a direction for a prospective work. We are thinking that transformation by the logit function of the values of the matrix X will work better with Algorithm 1.
As an outcome, Algorithm 1 produces the matrix G of latent factors. Accordingly, we can characterize any lecture by the corresponding vector-row of k numerical values, and can compute a proximity measure with the given three lecture (triplet) from the test set V . The smaller value of the distance indicates higher preference. 5
We fully agree with [10] that the superiority of new algorithms should always be demonstrated on an independent validation data. In this sense, an importance of the data mining contests is unquestionable. The rapid popularity growth of the data mining challenges demonstrates with confidence that it is the best known way to evaluate different models and systems.
In general terms, we are satisfied with our results. However, due to the lack of available time, we did not find an efficient way how to construct heterogeneous ensembles. For example, the outcomes of the methods of weighted singles and couples are very different. Nevertheless, both results are competitive, and it is very important to find out how to exploit the differences in order to produce more advanced solution.
Also, we did not explore in details gradient-based matrix factorization, which is presented in Section 4. We can expect that this method may lead (after proper adjustment and modification) to the solution, which will be different and competitive at the same time.
This work was supported by a grant from the Australian Research Council. Also, we are grateful to the Organisers of the PKDD 2011 data mining Contest for this stimulating opportunity. Many thanks to the reviewers for very helpful comments and advices, including some very important references.