This paper presents island models, methods, implementation and experiments connecting stochastic optimization methods and recommendation task (collaborative one). Our models and methods are based on matrix factorization. Parallel run of methods optimizes the RMSE metric from an island model point-of-view. This paper comments on architecture and some implementation decisions. We dealt with two research hypotheses. First, whether island models bring always improvement. We will show that almost always yes. Second, whether evolutionary algorithm does or does not always find the best solution. This will be confirmed only on smaller data. Experiments were provided on Movie Lens 100k and 1M data.
This paper studies recommender systems, especially learning user/customer preferences. Main idea of this paper is to connect this study to evolutionary island models. Here, island models are a computational tool for matrix factorization.
Instances of one stochastic optimization method run in parallel on island models, searching the same state space. Such a method traverses the state space of solutions. The actual state they visit is influenced by (mutually independent) stochasticity. Hence, different instances can visit different parts of the state space. Island model parallelization is based on cooperation of methods during the computation.
This resembles ensemble and/or hybrid learning, where different optimization methods are: • run in parallel • allowed to run in different state spaces The solution (usually one of them) is chosen at the end by an additional aggregation/decision method.
Using evolutionary computing for recommendation is
surveyed in the paper of Horvath [
In this paper, parameters of our methods were chosen after experiments on sample data. We will try to improve RMSE using parallelization. We will provide results on both ML100k and ML1M data.
Main contribution of this paper is: • Multiple island model brings statistically significant improvement of recommendation in comparison to single instance optimization. • Our implementation is able to handle individuals (matrix factors). Size of our individuals is several orders bigger than usual in evolutionary computation.
This paper is organized as follows: Chapter 2 "Related work" concerns recommender systems and matrix factorization; evolutionary algorithms and island model. Chapter 3 "Methods, models and parameters" sketches our view of stochastic optimization methods; parameters and settings of island model used in tests. Next section "Data" describes realization of experiments and design of tests and computing resources. Finally section 4 "Results" gives both numeric and graphic presentation of our results and discusses confirmation of our hypotheses. After conclusions paper ends with Future work. 2
This section gives basic notation for recommender systems, evolutionary computation used and overviews some relevant literature. 2.1
It was the Netflix price (announced in October 2006) which excited public and changed the landscape of recommender systems area research.
The BellKor squad included Chris Volinsky and his
AT&T colleagues Robert Bell and Yehuda Koren, along
with four other engineers from the United States, Austria,
Canada and Israel (BellKor’s Pragmatic Chaos) on June
26, 2009, finally crossed the 10% finish line. Main
ingredient of winning solution has been matrix factorization
(MF), see e.g. [
We focus on latent model based recommendation which is a part of collaborative filtering technique (Co), of evolutionary algorithms in combination with the computation of latent factors.
Motivated by this, in our paper individuals are
represented by concatenation of U| and I| (like a worm d-thick
and |U | + |I | long)
...
i11 . . . i1|I |
... . . . ...
id1 . . . xd|I |
asked for in Netflix Price competition. Co was introduced
by [
Let us denote U set of user ids and I the set of item ids.
Input data can be viewed as partial function r : U × I −→
P, here P is the preference scale (e.g. one to five stars
or real numbers). Alternative representation is in the form
of algebraic matrix R ∈ P|U |×|I | with dimensions
representing users and items respectively. Rating of user i ∈ U
of an item j ∈ I is content of corresponding cell of matrix
ri j ∈ P. Usually this matrix is very sparse, so in practice
input data are represented in a form of a database table R
with schema R(uid = user id, iid = item id, rating).
Although implementation uses database table formal model
of [
R ≈ U × I| = Rˆ where U ∈ P|U |×d , I ∈ P|I |×d are user and item latent factors matrices and × is a matrix product. d is much smaller than |U | and |I |. Approximation of R by Rˆ is measured by ei2j = (ri j − rˆij)2 =
d ri j − ∑ uiki jk k=1 ! here rˆij will serve as approximation of value ri j.
Our main optimization method is SGD - stochastic
gradient descent method. For other approaches and
dimensions of research in recommender systems we reffer to [
Evolutionary algorithms became popular after 1970,
thanks to John Holland [
The contribution of evolutionary algorithms in the area
of recommender systems was reviewed by Horvath de
Carvalho in [
Most of nature-inspired algorithms reviewed in [
Computing latent factor models by using of
evolutionary algorithms has emerged as a possible approach [
v uu ∑|iU=1| ∑|jI=1| ei2j t |U | ∗ |I | (3) Island models are one of approaches how parallelize optimization algorithms. Their characterization is that there is no central master and populations are distributed. Island model consists of parallel algorithms enriched by sending and accepting migrants. Migrants are individuals from other islands population. The hope is that this propagation of genetic material can speed up convergence and escape from local optima trap.
Parameters of island model are frequency of
sendingreceiving migrants and the way how the migrant is chosen
from local population (remember that parameters of
methods are fixed and are chosen after experiments on a sample
data). Optimal choice of these parameters depends on the
type of optimization method and is subject of study. These
aspects of island models are studied in [
Specific type of island models, heterogeneous, were
used in the application of multi-criteria optimization by
Martin Pilát and Roman Neruda [
The first who come up with heterogeneous island
models (HeIM), the way we understand them, was Martin Pilat
([
In this paper this tool is used with homogeneous islands to find optimal user and item latent factor.
Then different optimization techniques are used to converge with factor to optimal one. For illustration we give formulas for stochastic gradient descent. Recall ei2j, then next generation values of user and item factors equal to u´ik = uik + α
∂ ∂ uik 2 ei j ik´j = ik j + α ∂ ∂ ik j 2 ei j (4)
Note, that in our implementation we do not consider
normalization factor, this is left for future. Nevertheless,
some normalization effect is obtained by migration and
synergy of islands. α is not fixed, just bounded from
above. More on our system is in [
Island models where originally developed for parallelization of evolutionary algorithms. In this paper we will use also other stochastic optimization methods. 3.1
Evolutionary algorithms try to balance trade off between
exploration and exploitation. This property should help
evolutionary algorithm to escape from local extremes and
simultaneously converge to optimal solution. For this
ability they pay a higher time complexity because of parallel
development of bigger population. Because of this fact,
on some types of problems, the winners are other
stochastic optimization methods. An example is TSP solution by
hill climbing with 2-opt ([
All these methods use the stochastic gradient descent.
A general link to description of stochastic optimization
methods is [
Our implementation of stochastic optimization methods was changed in two ways. First, we had to create operators to enable them to work with latent factor based individuals. Second, methods were modified for parallel run in island models with migration. They were enriched with ability to cooperate. They receive individuals and enrich their local population. Please notice, that only evolution and differential evolution have bigger population. Remaining methods have only one individual population. In this case enrichment means replacement. They provide their solution from local population to neighboring islands. Methods manipulate incoming individuals in concordance with basic algorithm idea. E.g. the tabu search method inserts a newcomer to the tabu set.
Individual equals solution. Solution is represented by pair of latent factors of users and items (Figure 1). Multiplying of these latent factor we get a matrix which represents our estimation of ratings. Length of first vector is the number of users and the length of second vector equals number of items. Size of the individual depends on size of input problem. Width of latent vector is an optional parameter. 3.2
Now we describe island model - the environment in which
the above methods will be parallelized. It is the
environment which ensures dissemination of genetic material.
The main tool for this is the migration. This migration
does not mean only exchange of best solutions. We would
like to spread across the system (between islands) genetic
material which has the potential to contribute to further
improvement of population quality and to speed-up the
convergence. Migration is inspired by processes in nature
([
Key parameter of island models , as nature shows ([
Matrix factorization needs migration of much bigger
individuals than e.g. continuous optimization, where
individual is a point in an n-dimensional space. In this paper
we had to change architecture of model used in [
We used data from the movie recommendation domain in the experiments. The effectiveness of parallelization has been verified on datasets ml-100k1 and ml-1m2. Datasets are formed by movie evaluation (1-5 stars), for trials we use the trinity (user, movie, rating).
The training set consists of four-fifths from the dataset, the rest is the test set. Counting derivatives for SGD lever
HillClimbing RandomSearch Evolution
SGD random rating from each line generation of latent vectors uniform crossover + SGD
numberOfNeighbors=10 popSize=10, mutationRate=0.9, crossRate=0.1, parentSelector=CompareTwoRandomSelectors
TabuSearch Sim.Annealing SGD according to the I-th rating SGD random rating from each line SGD random rating from each line
differential crossover tabuModelSize=50 temperature=10000, coolingRate=0.002 popSize=50, F=0.25 ages the training set. The test set is used to evaluate individuals. 3.4
Our main idea is to increase stochasticity of searching the state space (which is enormous for movie data). First level of stochasticity is enabled by stochastic optimization method. Second level is enabled by several independent islands. The third level is attained by migration. Our system enables all of these. Moreover, all of these run in parallel with mutually assisting methods (not competitive).
In order to be able to obtain the best solution from such a computation resource, the computation must be continuously monitored (Figure 2). Solutions represent individuals that are unpredictably moving across the island model. We can never know when and where the best solution will appear (sometimes the best solution does not appear at the end, see Figure 3).
Our implementation uses agent middle-ware Jade3 for achievement of higher adaptivity of methods (in our three levels of stochasticity).
Here we were facing main decision. Whether to prefer higher adaptivity (based e.g. on Jade) or better use of effectiveness of specific hardware (based e.g. on C). From pure experimental curiosity we went along the agent based middle-ware framework direction.
The central brain of the multi-agent based system is a manager of migration which directs the computation and measures genetic material during evolution.
Island 1 Method (agent)
I.
Island 2 Method (agent)
II.
Manager (planner)
Monitor (statistic) Island 3 Method (agent)
III.
The use of this system is the implementation of methods as an agent, who can develop methods as adaptive computing resources. The infrastructure of the system is made up of two central points, by Agent-manager that manages computation and by Agent-monitor, that monitors genetic material in the system.
Software allows multiple ways of monitoring. The monitor statistically processes the quality of the individuals. Another way of observing what happens in the system is to produce the pedigrees of an individual. The basic idea is to enrich every individual of the pedigree that contains information on the involvement of concrete islands in its creation.
For our experiments, were used statistics that are computed from each monitored individuals in one iteration of planner. We will present the results as a measure of the system, which is monitoring follow-planner-iterations.
Our evolutionary methods (Table 1) use uniform crossover. In phase of mutation they apply stochastic gradient descent on a randomly chosen rating.
Differential evolution combines 3 latent vectors (individuals which are models/solutions) LV1 which is a concatenation of U1| and I1|, similarly LV2 and LV3. Result of the differential operator is latent vector
LVnew = LV1 + F ∗ (LV2 − LV3) here F is 0.25. Comparison of single methods - MFML1m
Single-BruteForce Single-Evolution Single-Hil Climbing Single-SimulatedAnnealing Single-TabuSearch 3.5
Two pairs of tests were created, comparing single methods and island models, differing in the size of the input Movieland dataset. The width of the latent vector was set to 10 (best after initial experiments on smaller samples). The tests run on all initial parameter settings (Table 3) 9 times. As far as our computations are nondeterministic this makes difference (see Figures 4 and 5). These are computationally demanding calculations.
Number of runs Computing nodes Latent factor width Datasets value 9 AMD Opteron 6376, 64GB memory 10 ml-100k, ml-1m Our experiments validated two hypotheses. First is that evolution does not necessary give best solution and second that island models improve results. We will present results for two datasets separately. We will show the best solution of 9 runs and average of all runs (for distribution see Figures 4 and 5).
On the smaller data set the winner is always Evolution and Islands give always better solution.
On the bigger dataset the single island winner is simulated annealing (in both minimum and average). In Islands the winner is hill climbing (in both minimum and average). On bigger data we can not always observe advantage brought by parallelization by islands and migration. This can be observed especially by simulated annealing. One possible explanation is that hill climbing does not risk that much going in wrong direction as simulated annealing is doing (sometimes). Bigger data bring bigger state space and hence risk is necessary, but 50 iterations of the planner is probably not enough. In future research we will run island models with more iterations. 5
We proved that island models are a good computing tool for recommender systems. Our experiments have shown following. Island models brought clear improvement on smaller data set. On bigger data, it is also true except of simulated annealing. Moreover on bigger data evolution does not find best solution.
Our implementation is publicly available on Github4
and hence enables repeatability of our experiments (see
[
1.7 1.6 In our future work we plan to extend this to heterogeneous island models. We also plan to develop new planners which will be specifically designed for recommendation domain. We would like to consider also islands with statistical learning methods. Challenge is extension to content based recommendation.
Single-SimulatedAnnealing
Island-SimulatedAnnealing
Acknowledgements. This work was supported by a Ph.D grant SVV2018-260451 under supervision of Peter Vojtas.