# Greedy SLIM: A SLIM-Based Approach For Preference Elicitation

Claudius Proissl
University of Stuttgart
Germany
&Amel Vatic
University of Stuttgart
Germany
&Helmut Waldschmidt
University of Stuttgart
Germany

###### Abstract

Preference elicitation is an active learning approach to tackle the cold-start
problem of recommender systems. Roughly speaking, new users are asked to rate
some carefully selected items in order to compute appropriate recommendations
for them.

To the best of our knowledge, we are the first to propose a method for
preference elicitation that is based on SLIM Ning and Karypis (2011), a state-
of-the-art technique for top-N recommendation.

Our approach mainly consists of a new training technique for SLIM, which we
call Greedy SLIM. This technique iteratively selects items for the training in
order to minimize the SLIM loss greedily.

We conduct offline experiments as well as a user study to assess the
performance of this new method. The results are remarkable, especially with
respect to the user study. We conclude that Greedy SLIM seems to be more
suitable for preference elicitation than widely used methods based on latent
factor models.

_Keywords_ preference elicitation $\cdot$ SLIM $\cdot$ cold-start problem

##  1 Introduction

Providing accurate top-N recommendations is an important task for many online
services. Among the most successful approaches to this problem are those in
the field of collaborative filtering, which process user-item interactions in
order to compute recommendations. The accuracy of these approaches is known to
suffers for users with only a few item interactions, which is always the case
if new users enter the system.

This issue is known as the user cold-start problem Lam et al. (2008) and it
can be addressed in many different ways Elahi et al. (2019). Perhaps the most
popular approach is to augment the input parameters with other sources of
information by, for instance, combining collaborative filtering with content-
based filtering Soboroff and Nicholas (1999); Vartak et al. (2017); Lika et
al. (2014) or by incorporating cross-domain knowledge about the new users
Fernández-Tobías et al. (2016); Cantador and Cremonesi (2014).

A different way to tackle the cold-start problem is to ask the new users to
rate some carefully selected items during an onboarding process. We call this
the questionnaire approach, also known as preference elicitation Parapar and
Radlinski (2021); Sepliarskaia et al. (2018); Elahi et al. (2019). This method
aims to create a first basis of ratings for each user with which the
recommender system can produce meaningful results.

In this work we address the questionnaire approach without claiming that it is
the preferred way. Our humble advice to practitioners is to use any
information about the users that is available. There are, however, many
conceivable scenarios where this information is simply insufficient to work
with and then the questionnaire approach may be the best option. Another
strong point of this way is that it inherits all the benefits of collaborative
filtering: it can be widely applied, no domain-specific knowledge is
necessary, and the users can stay anonymous.

The general question we address in this work is, given a top-N recommender of
your choice, which items should new users be asked to rate in order to
maximize the accuracy of the subsequently computed recommendations? This is a
classic problem in the field of active learning and similar questions have
been raised in many other publications before Christakopoulou et al. (2016);
Golbandi et al. (2011); Sepliarskaia et al. (2018); Rokach and Kisilevich
(2012); Fonarev et al. (2016); Wang et al. (2017). Clearly, the answer may
depend on the chosen recommender system. In this aspect, the existing
literature is surprisingly confident that latent factor models (LFM, also
known as matrix factorization; see, for instance, Koren et al. (2022)) are the
correct choice.

In this work we propose a different approach and use SLIM Ning and Karypis
(2011) as recommender system. SLIM is a well-established method for top-N
recommendation in the field of collaborative filtering. Ever since its
publication in 2011, SLIM has attracted a lot of attention in the scientific
community and has been inspiration for similar approaches Kabbur et al.
(2013); Zheng et al. (2014); Steck (2019, 2019); Steck et al. (2020).

Still, one may wonder why we select a method that is more than ten years old.
First, to us, SLIM is more a concept than a concrete method, just as the LFM
is and there are modern and very efficient incarnations of it Steck (2019);
Steck et al. (2020). Second, there are available implementations of SLIM
everywhere. It is therefore safe to bet that SLIM will stay important for the
next couple of years.

The concrete question we address in this work is how SLIM can be used to
construct efficient questionnaires. The answer we propose in this work is that
the typical way to train SLIM is not suitable to tackle the cold-start problem
(Section 4). We therefore discuss in Section 5 a new preprocessing routine
that trains SLIM iteratively item by item, each turn greedily selecting the
item that minimizes the loss. We call this approach Greedy SLIM. Our training,
thus, already orders the items by importance and our questionnaire simply
consists of the $k$ most important items (where $k$ can be chosen
arbitrarily).

In Section 6 we compare our approach with a popular existing preference
elicitation method and in Section 7 we present our results from a small user
study we conducted.

##  2 Related Work

We are not the first to adapt the training phase of SLIM to a specific problem
setting. For instance, in Steck et al. (2020) a training method based on the
Alternating Direction Method of Multipliers Boyd et al. (2011) is proposed.
This approach decouples the run time of the training phase from the number of
users, which is especially important if the number of users is much larger
than the number of items.

Improving the run time of the training phase is also the main objective of the
approach in Steck (2019), which slightly changes the definition of SLIM in
order to apply more efficient training methods.

In principle, we think that the ideas presented in this work can be combined
with any autoencoder-based top-N recommender. We chose SLIM as we think that
it is the most established approach.

Preference elicitation is a very active research direction and in our humble
opinion it is hard to tell which methods are state-of-the-art. Most existing
approaches are based on LFMs. Some examples are Christakopoulou et al. (2016);
Sepliarskaia et al. (2018); Rokach and Kisilevich (2012); Fonarev et al.
(2016); Wang et al. (2017). For instance, in Christakopoulou et al. (2016) a
probabilistic method is proposed that tries to find the optimal trade-off
between exploration and exploitation when selecting the next question. This
strategy is motivated by the multi-armed bandit problem. The general idea is
to assign weights to all existing users denoting the probability that the new
user rates items similarly. The parameters for the new user are then obtained
by taking the weighted sum of the existing users’ parameters. We call this
approach in the following $Q_{\text{Bandit}}$ for bandit questionnaire.

The authors of Golbandi et al. (2011) present a similar method based on
decision trees. Their algorithm chooses the questions greedily by taking the
question that minimizes the expected root mean squared error (RMSE) of the new
user’s predicted ratings after receiving the answer to the selected question.
The shortcoming of this approach is that the RMSE is not a good measure for
the performance of top-N recommender systems as it was shown in Cremonesi et
al. (2010). It is, however, one of the few existing techniques that is not
based on the LFM.

Another interesting LFM-based approach is described in Sepliarskaia et al.
(2018). Very roughly speaking, it selects questions based on a kind of binary
search in order to narrow down the region in the latent factor space where the
feature vector of the new user may live. We found that this approach was very
appealing from a theoretical point of view.

Despite these and other interesting techniques we found it hard to find
appropriate baselines for our approach. First of all, while there is a lot of
literature about the cold-start problem in general, the questionnaire approach
is less popular. Furthermore, the reproducibility issue within the recommender
systems community is also an issue when it comes to questionnaires. We had to
implement all the baselines we wanted to consider on our own. For Golbandi et
al. (2011) and Sepliarskaia et al. (2018) we, unfortunately, obtained poor
results. We therefore decided to not include them in our official experiments
as there is always the possibility of a misinterpretation or an implementation
error.

We chose $Q_{\text{Bandit}}$ as the main baseline for our experiments in
Section 6 and 7. We found that this method is popular and a good
representative of many other LFM-based approaches. Furthermore, the method is
intuitive and, hence, we are confident that our implementation is correct.

##  3 Preliminaries

In the remainder of this work we assume that we are given a set of $m$ users
$\mathcal{U}:=\\{u_{1},\,u_{2},\dots,\,u_{m}\\}$ and a set of $n$ items
$\mathcal{I}:=\\{i_{1},\,i_{2},\dots,\,i_{n}\\}$. Furthermore, we have a user-
item interaction matrix $X$ of size $m\times n$. The definition of a user-item
interaction differs from application to application. In our case user $u$
interacts with item $i$ by setting the rating $r_{ui}\in[1,\,5]$. Therefore,
the values $x_{ui}$ of $X$ are either $0$ if user $u$ has not rated item $i$
yet or $x_{ui}=r_{ui}$.

Our vectors are column vectors and written with bold lowercase letters. For
any matrix $A$ we write $\textbf{a}_{j}$ for the $j$-th column of $A$ and
$\textbf{a}^{T}_{j}$ for its $j$-th row. We write $A^{T}$ for the transposed
matrix of $A$. Furthermore, we write $\lVert\cdot\rVert_{1}$ for the
$L_{1}$-norm and $\lVert\cdot\rVert_{F}$ for the Frobenius norm. For any set
$S$ we write $|S|$ to denote its size.

###  3.1 Questionnaire

We define a questionnaire to be a function $Q:~{}\mathbb{R}^{m\times
n}\times\mathcal{U}\rightarrow\mathcal{I}$ that takes as input the user-item
interaction matrix $X$ and a user $u$. The output of this function is an item
$i$ that the user $u$ should rate. The questionnaire is therefore allowed to
reveal some unknown ratings of the input user $u$.

We always consider questionnaires in combination with a recommender system
$R:~{}\mathbb{R}^{m\times n}\times\mathcal{U}\times
N\in\mathbb{N}\rightarrow\mathcal{I}^{N}$. We interpret recommender systems as
a function $R$ that takes as input the user-item interaction matrix $X$, a
user $u$ and a number $N$ and returns $N$ sorted items as recommendations for
user $u$. For a given recommender system, our goal is to find the right
questionnaire in order to maximize the accuracy of the recommender system for
the input user $u$. In this work we try to find a good questionnaire for SLIM.

An important application of questionnaires is when the input user $u$ is new
to the system, which means the row $\textbf{x}^{T}_{u}$ of $X$ is a zero-
vector. This is also the scenario we consider in this work. In such a case, it
makes sense to distinguish between two types of questionnaires, static and
dynamic questionnaires. Static questionnaires ask the same questions to all
new users whereas the output of dynamic questionnaires depends on the already
given answers of the user.

While dynamic questionnaires are more flexible with respect to the asked
questions, the computation of the questions often needs to be conducted
online. This means that the questions must be computed fast. Static
questionnaires can be computed in a preprocessing phase such that much more
complex calculations are affordable. Our approach describes a static
questionnaire but we believe that our ideas can be easily extended to the
dynamic setting.

In this work we assume that a question always consists of a single item that
the user should rate. Clearly, there are other types of questions that are at
least as plausible. For instance, a question could also consist of two items
and the users should tell which one they prefer. In Christakopoulou et al.
(2016) a way is described to extend $Q_{\text{Bandit}}$ to this question type.
There are concerns that so called absolute questions, questions about one
item, are too difficult to answer accurately. We do see that point as well but
prefer to keep this dimension of complexity out for the sake of readability
and compactness.

###  3.2 SLIM

In SLIM Ning and Karypis (2011) we are looking for a non-negative matrix $W$
of size $n\times n$ such that $XW\approx X$. As such, the problem could be
trivially solved by choosing $W$ to be the identity matrix. We therefore
additionally require the diagonal of $W$ to be zero. A suitable matrix $W$
reveals interaction similarities among items. For instance, if items $i_{1}$
and $i_{2}$ had identical user interactions, we could set
$w_{i_{1}i_{2}}=w_{i_{2}i_{1}}=1$. The non-negativity constraint ensures that
$W$ only reflects positive interaction correlations. In Steck et al. (2020) it
is shown that for some datasets it is beneficial to drop this constraint. We
call $W$ the SLIM matrix.

The SLIM loss function $l_{SLIM}:~{}\mathbb{R}^{n\times
n}\rightarrow\mathbb{R}$ is defined as

$\displaystyle l_{SLIM}\left(W\right):=\lVert
X-XW\rVert_{F}^{2}+\lambda_{F}\lVert W\rVert_{F}^{2}+\lambda_{1}\lVert
W\rVert_{1},$ (1)

where $\lambda_{F}$ and $\lambda_{1}$ are fixed parameters. The complete
optimization problem is given below.

$\displaystyle\min_{W}$ $\displaystyle l_{SLIM}\left(W\right)$ (2) subject to
$\displaystyle W\geq 0$ $\displaystyle\text{diag}\left(W\right)=0$

In Ning and Karypis (2011) the authors propose coordinate descent Friedman et
al. (2010) in order to compute $W$. Another approach based on the Alternating
Direction Method of Multipliers is presented in Steck et al. (2020). In this
work we propose a greedy strategy to compute $W$, which we present in Section
5.

In the following we discuss how we can compute top-N recommendations for any
user $u\in\mathcal{U}$ using the SLIM matrix $W$. We define the predicted
relevance $\tilde{r}_{ui}$ of item $i\in\mathcal{I}$ for user $u$ as

$\displaystyle\tilde{r}_{ui}:=\textbf{x}_{u}^{T}\textbf{w}_{i},$

where $\textbf{x}_{u}^{T}$ is the row of matrix $X$ that corresponds to the
item interactions of user $u$ and $\textbf{w}_{i}$ is the $i$-th column of
matrix $W$. We sort the items $i\in\mathcal{I}$ with $x_{ui}=0$ by their
predicted relevance in descending order and show user $u$ the list of the
first $N$ items ($x_{ui}=0$ because we restrict our recommendations to unknown
user-item interactions).

###  3.3 Evaluation Method

####  3.3.1 Evaluation Metrics

We mainly use the Normalized Discounted Cumulative Gain (NDCG) in order to
compare different top-N recommendations. The NDCG is designed to measure the
relevance of search results, which fits very well to our setting. We set the
gain $g_{ui}$ of user $u$ for item $i$ to be $2^{x_{ui}}-1$ in order to
emphasize that a high rating is much more important than a medium rating.

Let $\mathcal{I}_{R}\subseteq\mathcal{I}$ be the item subset from which the
recommender system is allowed to draw the recommendations. This may not be the
complete item set $\mathcal{I}$ as we sometimes exclude items (discussed in
Section 3.3.2). The cumulative gain $CG:~{}\mathbb{R}^{m\times
n}\times\mathcal{U}\times 2^{\mathcal{I}_{R}}$ takes the interaction matrix
$X$, a user $u$ and an item subset $I\subseteq\mathcal{I}_{R}$ as input and is
defined as

$\displaystyle CG\left(X,\,u,\,I\right):=\sum_{i\in I}2^{x_{ui}}-1.$

The discounted cumulative gain $DCG$ turns the subset $I$ into a sorted list
and weights the gain depending on the position of the item. This is motivated
by the goal to put the best search results on top of the list.

$\displaystyle DCG\left(X,\,u,\,I\right):=\sum_{1\leq
j\leq|I|}\frac{2^{x_{uI[j]}}-1}{\log_{2}\left(j+1\right)}.$

The NDCG is the DCG normalized by the maximum DCG among all subsets
$I\subseteq\mathcal{I}_{R}$ (for a fixed user $u$). This ensures that the NDCG
is a number between 0 and 1. We write NDCG@$N$ to emphasize that $|I|$ is $N$.

Other metrics we consider are Precision@$N$ and Recall@$N$. Let $I_{u}$ be the
set of items rated by user $u$ and let $I_{R}$ be the recommendation for this
user. Precision is then defined as

$\displaystyle\frac{|I_{R}\cap I_{u}|}{|I_{R}|},$

while Recall is defined as

$\displaystyle\frac{|I_{R}\cap I_{u}|}{|I_{u}|}.$

####  3.3.2 Offline Experiments

Our offline experiments of this work have the following structure. We first
randomly split the users $\mathcal{U}$ into disjoint training and test sets
$\mathcal{U}_{\text{train}}$ and $\mathcal{U}_{\text{test}}$ with
$|\mathcal{U}_{\text{test}}|=0.1\cdot|\mathcal{U}|$. The corresponding
interaction matrices $X_{\text{train}}$ and $X_{\text{test}}$ only contain the
interactions of the respective users.

For each pair $(Q,\,R)$ of questionnaires and recommender systems we want to
consider we conduct the following experiment for each test user
$u\in\mathcal{U}_{\text{test}}$. We add a zero row for the user $u$ to the
interaction matrix $X_{\text{train}}$ and call the thereby obtained matrix
$X^{\prime}$. We then iteratively call the questionnaire
$Q\left(X^{\prime},\,u\right)$, which returns an item $i$, and copy the user-
item interaction $r_{ui}$ from $X_{\text{test}}$ to $X^{\prime}$. When we call
$Q\left(X^{\prime},\,u\right)$ the next time, the row of user $u$ may
therefore look different. After doing this (arbitrary) $k$ times, we call our
recommender system $R\left(X^{\prime},\,u,\,N\right)$ to evaluate the accuracy
of the top-N recommendation after $k$ questions.

Let $I_{Q}$ be the set of items asked by the questionnaire and let $I_{R}$ be
the set of recommended items. We always require $I_{Q}\cap I_{R}=\emptyset$ to
avoid trivial recommendations.

We found that this procedure simulates the onboarding process of a new user
$u$ well and is less biased than other approaches where the user behavior is
simulated by some trained model. The following shortcomings remain, however.
First, the information contained in $X_{\text{test}}$ may be incomplete
because the users do not rate all the items they know. Second, a real new user
most likely knows less items than the users contained in $X_{\text{test}}$. We
found that these points might have a severe impact on the results, which is
why we additionally conducted an online user study that is discussed in
Section 7.

It is common practice to evaluate how well top-N recommender systems perform
if they are restricted to lesser known items. Following Cremonesi et al.
(2010), we refer to the set of most popular items that represent 33% of the
ratings as short-head items. The remaining items are called long-tail items.
Accurately recommending short-head items is relatively simple, as we
demonstrate in Section 4, and often rather pointless as most users, even new
users, are likely to be aware of these items. It is much more challenging to
find accurate recommender systems for long-tail items, which is why we conduct
separate experiments for these. In this setting the questionnaires are still
allowed to contain short-head items, of course, but the top-N recommendation
is restricted to long-tail items.

Note that in our experiments we do not apply any kind of item sampling to
avoid the problems reported in Krichene and Rendle (2022).

####  3.3.3 Reproducibility

Our source code can be found here111Source code:
https://osf.io/myh2q/?view_only=a9a747dee8704203ae594ae0a8cc88f8.

###  3.4 Bandit Questionnaire

As $Q_{\text{Bandit}}$ Christakopoulou et al. (2016) is our main baseline
algorithm in Section 6 and 7, we would like to discuss it in more detail. The
approach assumes that a trained LFM is available without specifying how
exactly this model is obtained. An LFM mainly consists of feature vectors, for
the users as well as for the items (see, for instance, Koren et al. (2022) for
an overview). If we believe that an LFM approximates the rating behavior of
the users well, our goal should be to find out the feature vectors of new
users in order to predict their ratings.

The idea of $Q_{\text{Bandit}}$ is to approximate the feature vector of the
new user by a weighted sum of the feature vectors of the existing users. We
can then use this approximation to compute the recommendation for the user in
a straightforward manner.

The approach takes a probabilistic point of view and interprets the weighted
sum of the feature vectors as the expected feature vector of the new user.
This can be done in a mathematically strict manner with the assumption that
all users rate according to the LFM plus some random noise that is normally
distributed with mean zero. Each existing user is then weighted by the
probability that he or she rates as the new user (times a normalization
factor).

It remains to specify a strategy, which questions are asked to the new user.
The authors of Christakopoulou et al. (2016) propose several plausible ways,
in the nature similar to the baseline approaches we discuss in Section 4. We
only consider the method that works best according to Christakopoulou et al.
(2016), which they call Thompson Sampling Chapelle and Li (2011). In this
context222At least, that’s our interpretation as in Christakopoulou et al.
(2016) it is not clearly specified., Thompson Sampling means that for each
question we draw an existing user from the probability distribution specified
by the mentioned weights. Initially, this is the uniform distribution. We then
pick the item as question that receives the best rating of the drawn user
according to the LFM.

Note that the way questions are selected would also be a reasonable way to
construct recommendations. From an information theoretical point of view this
makes sense (to some extend) because the new user most likely only knows a
fraction of the items. We should therefore try to find items the user knows to
increase the information gain per question.

##  4 A First Approach

In this section we would like to demonstrate the difficulty of finding good
questionnaires for SLIM. We discuss some straightforward strategies and show
their (poor) performance in experiments with our Movielens dataset (ML-25, see
Table 1).

We train SLIM as described in Section 3.3 using the implementation of Ning et
al. (2019), version 2.0, with the default parameters $\lambda_{1}=1$ and
$\lambda_{F}=1$.333Unfortunately, we did not have the computational capacity
for a proper parameter optimization as the training phase of SLIM is
computationally expensive.

A basic but important approach for a questionnaire is to simply pick the most
popular items Rashid et al. (2008). Our first questionnaire $Q_{\text{Pop}}$
therefore selects among all items $\mathcal{I}\setminus I_{u}$ the item with
most ratings, where $I_{u}$ is the set of items the input user $u$ has already
rated. We also consider the questionnaire $Q_{\text{Var}}$ that selects items
based on a trade-off between high entropy and high popularity Golbandi et al.
(2011). Note that $Q_{\text{Pop}}$ and $Q_{\text{Var}}$ are not at all adapted
to SLIM.

We therefore present a more sophisticated approach we call
$Q_{\text{Greedy}}$. Let $W$ be the SLIM matrix we obtained from our training
with $X_{\text{train}}$ and let $I$ be any subset of the items $\mathcal{I}$.
We define $W_{I}$ to be equal to $W$ for every row $i\in I$ and to be filled
with zeros otherwise. We can think of $I$ to be our questionnaire that reveals
columns of the interaction matrix, which is equivalent to revealing rows of
$W$.

We start with $I:=\\{\\}$ and in each step we add the item $i$ to $I$ such
that $l_{SLIM}\left(W_{I}\right)$ is minimized. The motivation behind this
approach is that we want to maximize the information gain of every question,
which we achieve greedily by minimizing the SLIM loss.

Note that $Q_{\text{Greedy}}$ has a similar flavor as the approach we present
in Section 5 but is conceptually very different. Here we take a trained matrix
$W$ and greedily order the items while the approach in Section 5 greedily
computes the matrix $W$.

To get a better feeling how well the mentioned approaches perform, we add a
very simple, static recommender system $R_{\text{Gain}}$ that recommends the
same set of items to all users in $\mathcal{U}_{\text{test}}$. It sorts the
items by their sum of gain (see Section 3.3) for the users in
$\mathcal{U}_{\text{train}}$ in descending order and returns the first $N$
items as recommendation. We’ve tried several other static recommender systems
and found that this one performs best with respect to NDCG. This approach
achieves an average NDCG@10 of $0.314$ for all items and of $0.064$ for long-
tail items, which confirms the well-known observation that recommending long-
tail items is much more challenging. Clearly, any sophisticated approach must
outperform this baseline to be of relevance.

Figure 1: Performance of different SLIM questionnaires and $R_{\text{Gain}}$
for ML-25. Left: all items, right: long-tail items. While for long-tail items
the NDCG increases with the number of questions, this is not the case for all
items.

Figure 1 shows the results of our experiments. Considering all items (left) we
can observe that, surprisingly, the recommendation accuracy decreases with the
number of questions. The questionnaires mainly consist of popular items that
would have been good candidates for the recommendation. As we restrict the
recommendation list to items not included in the questionnaire, asking
questions about popular items may have a negative effect on the recommendation
performance if the recommender system is unable to generalize the gained
information. Another interesting observation is that only $Q_{\text{Greedy}}$
is able to achieve better results than $R_{\text{Gain}}$.

Looking at long-tail items (Figure 1, right) we can observe that the NDCG
first drops below the static approach $R_{\text{Gain}}$, which is used as
fallback strategy for all other approaches. However, after the first five
questions the performance of the SLIM questionnaires improves with each
question as expected. Again, $Q_{\text{Greedy}}$ seems to be the best approach
by beating $R_{\text{Gain}}$ after $10$ questions.

In summary, even though we are partly able to obtain better results than
$R_{\text{Gain}}$, we do not think that the presented approaches are
practical. The reason is that it takes 15 to 20 questions until we obtain a
clear performance benefit, which we consider to be too slow in practice.

##  5 Greedy SLIM

Motivated by the mediocre performance of SLIM-based questionnaires (see
Section 4) we present a new approach for the training phase of SLIM that is
much more suitable for the questionnaire setting. Our method constructs the
SLIM matrix $W$ row by row, each time selecting the item $i\in\mathcal{I}$
that minimizes the SLIM loss. We therefore propose a greedy algorithm for the
SLIM training, which is why we call it Greedy SLIM, or GSLIM. Our approach
tries to maximize the information gain with every additional row of $W$, which
is exactly what a questionnaire tries to achieve. After the training phase our
questionnaire $Q_{\text{GSLIM}}$ orders the items used as questions in the
same way the rows were added to $W$. After receiving the answers we can use
matrix $W$ to compute the recommendations as explained in Section 3.2.

We initialize $W$ as an $n\times n$ zero-matrix. Our algorithm iteratively
fills the rows of $W$. Recall that each row of $W$ corresponds to an item
$i\in\mathcal{I}$. Let $I_{W}\subseteq\mathcal{I}$ be the set of empty rows in
$W$, which is initially the entire set $\mathcal{I}$. Furthermore, let
$\hat{X}:=X-XW$ with entries $\hat{x}_{ui}$.

We now define the loss functions
$l_{ij}\left(w\right):~{}\mathbb{R}\rightarrow\mathbb{R}$, where $i$ and $j$
are any two items in $\mathcal{I}$, as follows.

$\displaystyle
l_{ij}\left(w\right):=\lambda_{1}w+\lambda_{F}w^{2}+\sum_{u\in\mathcal{U}_{\text{train}}}\left(\hat{x}_{uj}-x_{ui}w\right)^{2}$

Note that function $l_{ij}$ is very similar to the SLIM loss except that it is
restricted to a single element in $W$. Lemma 3 describes how these loss
functions and the SLIM loss correlate.

######  Lemma 1.

Given a SLIM matrix $W$ with empty rows $I_{W}\subseteq\mathcal{I}$, let
$W^{\prime}$ be another SLIM matrix that is equal to $W$ except for one row
${\textbf{w}^{\prime}}_{i}^{T}$ with $i\in I_{W}$. We then have

$\displaystyle
l_{SLIM}\left(W^{\prime}\right)=l_{SLIM}\left(W\right)+\sum_{j\in\mathcal{I}\setminus\\{i\\}}\left(l_{ij}\left(w^{\prime}_{ij}\right)-l_{ij}\left(0\right)\right).$
(3)

###### Proof.

First, note that from $i\in I_{W}$ it follows by definition that
$\textbf{w}_{i}^{T}$ is filled with zeros. Let $\hat{X}:=X-XW$ and
$\hat{X}^{\prime}:=X-XW^{\prime}$. Note that
$\hat{X}^{\prime}=\hat{X}-\textbf{x}_{i}{\textbf{w}^{\prime}}_{i}^{T}$. We,
thus, have

$\displaystyle l_{SLIM}\left(W^{\prime}\right)$
$\displaystyle=\lambda_{1}\lVert
W+{\textbf{w}^{\prime}}_{i}^{T}\rVert_{1}+\lambda_{F}\lVert
W+{\textbf{w}^{\prime}}_{i}^{T}\rVert_{F}^{2}+\lVert\hat{X}-\textbf{x}_{i}{\textbf{w}^{\prime}}_{i}^{T}\lVert_{F}^{2}$
$\displaystyle=\lambda_{1}\lVert W\rVert_{1}+\lambda_{F}\lVert
W\rVert_{F}^{2}+\lVert\hat{X}\lVert_{F}^{2}+\lambda_{1}\lVert{\textbf{w}^{\prime}}_{i}^{T}\rVert_{1}+\lambda_{F}\lVert{\textbf{w}^{\prime}}_{i}^{T}\lVert_{F}^{2}$
$\displaystyle+\sum_{j\in\mathcal{I}\setminus\\{i\\}}\sum_{u\in\mathcal{U}_{train}}\left(\hat{x}_{uj}-x_{ui}w^{\prime}_{ij}\right)^{2}-\hat{x}_{uj}^{2}$
$\displaystyle=l_{SLIM}\left(W\right)+\sum_{j\in\mathcal{I}\setminus\\{i\\}}\left(l_{ij}\left(w^{\prime}_{ij}\right)-l_{ij}\left(0\right)\right).$

∎

Our goal is to find the matrix $W^{\prime}$ that minimizes
$l_{SLIM}\left(W^{\prime}\right)$. For a fixed item $i\in I_{W}$ it follows
from Equation 3 that minimizing $l_{SLIM}\left(W^{\prime}\right)$ is equal to
minimizing the sum
$\sum_{j\in\mathcal{I}\setminus\\{i\\}}l_{ij}\left(w^{\prime}_{ij}\right)$.
The summands $l_{ij}\left(w^{\prime}_{ij}\right)$ are (for a fixed $i$)
independent from each other and, thus, can be minimized separately.
Furthermore, the function $l_{ij}\left(w\right)$ is a quadratic function in
$w$ and we can therefore find its minimum by setting its derivative
$l^{\prime}_{ij}\left(w\right)$ to zero.

$\displaystyle l^{\prime}_{ij}\left(w\right)$
$\displaystyle=\lambda_{1}+2\lambda_{F}w+\sum_{u\in\mathcal{U}_{\text{train}}}\left(-2\hat{x}_{uj}x_{ui}+2x_{ui}^{2}w\right)$
(4)
$\displaystyle=2\left(\lambda_{F}+\sum_{u\in\mathcal{U}_{\text{train}}}x_{ui}^{2}\right)w+\lambda_{1}-2\sum_{u\in\mathcal{U}_{\text{train}}}\hat{x}_{uj}x_{ui}$
$\displaystyle\stackrel{{\scriptstyle!}}{{=}}0$

Equation 4 is solved by

$w^{*}=\frac{-\frac{\lambda_{1}}{2}+\sum_{u\in\mathcal{U}_{\text{train}}}\hat{x}_{uj}x_{ui}}{\lambda_{F}+\sum_{u\in\mathcal{U}_{\text{train}}}x_{ui}^{2}}.$
(5)

We set
$w^{*}_{ij}:=\max\\{\frac{-\frac{\lambda_{1}}{2}+\sum_{u\in\mathcal{U}_{\text{train}}}\hat{x}_{uj}x_{ui}}{\lambda_{F}+\sum_{u\in\mathcal{U}_{\text{train}}}x_{ui}^{2}},0\\}$
in order to satisfy the non-negativity constraint.

In each round of our algorithm we solve the problem

$\displaystyle i^{*}=\arg\min_{i\in
I_{W}}\sum_{j\in\mathcal{I}\setminus\\{i\\}}\left(l_{ij}\left(w^{*}_{ij}\right)-l_{ij}\left(0\right)\right),$

remove $i^{*}$ from $I_{W}$ and fill the $i^{*}$-th row of $W$ with the values
$w^{*}_{i^{*}j}$. Note that this step also changes $\hat{X}$ and the loss
functions $l_{ij}$. We repeat until $I_{W}$ is the empty set.

##  6 Offline Experiments

###  6.1 Datasets

We consider two well-known datasets in our experiments Movielens-25M (ML-25)
Harper and Konstan (2015) and the Netflix Bennett et al. (2007) dataset (see
Table 1 for details). We do not filter these sets to ensure that we do not
accidentally introduce any biases.

Table 1: Datasets Name | Users | Items | Ratings
---|---|---|---
ML-25444Publicly available dataset described in Harper and Konstan (2015). Download link: https://grouplens.org/datasets/movielens/25m/ | $162,541$ | $59,047$ | $25,000,095$
Netflix555Publicly available dataset described in Bennett et al. (2007). | $480,189$ | $17,770$ | $100,480,507$

We split the datasets into training and test sets as described in Section 3.3.

###  6.2 Baselines

Our main baseline is $Q_{\text{Bandit}}$, see Section 3.4 for a description.
$Q_{\text{Bandit}}$ requires a trained LFM as input and in Christakopoulou et
al. (2016) it is not specified how the LFM is trained. We decided to use the
approach called PureSVD Cremonesi et al. (2010) for the following reasons.
First, PureSVD outperforms other training methods regarding top-N
recommendations Cremonesi et al. (2010). Second, the approach is conceptually
simple and there are reliable implementations available. Thus, we keep the
risk low that we run into the problems discussed in Rendle et al. (2019). We
used the implementation called redsvd Okanohara (2011).

Apart from $Q_{\text{Bandit}}$ we compare our method with the baselines
$R_{\text{Gain}}$ and $Q_{\text{Greedy}}$ as described in Section 4.

###  6.3 Training Phase

For Netflix it took 9 minutes per row to compute the SLIM matrix, for ML-25 it
took even 19 minutes. It is therefore often not feasible to compute the
complete SLIM matrix with this approach. Fortunately, for our purpose it
suffices to compute the number of rows that equals the size of the
questionnaire, which is 20 in our experiments.

As our questionnaire is static, we can compute the SLIM matrix in a
preprocessing step and do not have to worry too much about the run time. This
is also the reason why optimizing the computational cost of the training phase
is not the focus of this work. We are confident that there are many ways to
improve the run´ times and leave this task as future work.

The main reason for the high computational effort is that we are unable to
hold the matrix $\hat{X}$ in memory. We therefore compute it in each iteration
from scratch. Furthermore, we consider each item as possible candidate for the
next row, even items with very few ratings. This is the reason why the
training for ML-25 takes much longer than for Netflix. Excluding lesser known
items would greatly improve the run times. Lastly, the parallelization of our
implementation is on a simple level, leaving much room for improvement.

Our baseline $Q_{\text{Bandit}}$ clearly outperforms $Q_{\text{GSLIM}}$ in
this step. The training phase of PureSVD took $96$ seconds for Netflix and
$25$ seconds for ML-25.

###  6.4 Parameter Optimization

Before conducting the actual experiments, we needed to set the parameters for
$Q_{\text{GSLIM}}$ and $Q_{\text{Bandit}}$ meaningfully. The parameters of
$Q_{\text{GSLIM}}$ are the regularization variables $\lambda_{1}$ and
$\lambda_{F}$, while for $Q_{\text{Bandit}}$ we need to specify the number of
features $\lambda_{\text{LFM}}$.

Regarding $Q_{\text{GSLIM}}$, we tried all combinations of powers of two
between $2^{0}$ and $2^{19}$ for $\lambda_{1}$ and $\lambda_{F}$. For
$Q_{\text{Bandit}}$, we considered all multiples of $100$ between $200$ and
$800$ for $\lambda_{\text{LFM}}$. Note that one test run of
$Q_{\text{Bandit}}$ took between $20-100$ times longer than one test run of
$Q_{\text{GSLIM}}$ (due to its expensive evaluation phase), such that we
roughly invested the same computational effort in both approaches.

We conducted our parameter optimization by splitting $X_{\text{train}}$ into a
new test and training set following a similar procedure as explained in
Section 3.3. Most importantly, we did not consider $X_{\text{test}}$ in this
phase. Our results are shown in Table 2. Interestingly, our parameters for
$Q_{\text{GSLIM}}$ are much larger than those reported in Ning and Karypis
(2011) for SLIM.

Questionnaire | ML-25 | Netflix
---|---|---
$Q_{\text{Bandit}}$ | $\lambda_{\text{LFM}}=700$ | $\lambda_{\text{LFM}}=800$
$Q_{\text{GSLIM}}$ |  $\lambda_{1}=2^{12}$, $\lambda_{F}=2^{16}$ |  $\lambda_{1}=2^{15}$, $\lambda_{F}=2^{10}$
Table 2: This table shows the results of the parameter optimization for both
considered datasets.

###  6.5 Top-N Recommendation

We conducted our experiments as explained in Section 3.3. Figure 2 shows the
average results with respect to the NDCG@10. The NDCG of $Q_{\text{Bandit}}$
converges or even decreases after ten questions. We think that the main reason
for the decreasing NDCG is that the questionnaires are not allowed to
recommend items that they contain as questions. Therefore, using popular items
as questions may have a negative impact on the recommendation performance if
the questionnaire is unable to generalize the gained information.
$Q_{\text{GSLIM}}$ does not suffer from this restriction. On the contrary,
even after 20 questions there is no sign of convergence or overfitting.

Figure 2: Comparison of our approach $Q_{\text{GSLIM}}$ with the baselines
$Q_{\text{Bandit}}$, $R_{\text{Gain}}$ and $Q_{\text{Greedy}}$. Top: ML-25,
bottom: Netflix, left: all items, right: long-tail items.

Looking at the numbers, shown in Table 3, two tendencies can be observed.
First, $Q_{\text{Bandit}}$ seems to perform slightly better than
$Q_{\text{GSLIM}}$ if the questionnaire consists of very few questions. This
is especially the case with the Netflix dataset, where $Q_{\text{Bandit}}$
clearly outperforms $Q_{\text{GSLIM}}$ during the first ten questions. Second,
$Q_{\text{GSLIM}}$ is able to profit from every additional question, which
leads to favorable results if the questionnaire consists of ten or more
questions.

|  | ML-25 |  | Netflix |
---|---|---|---|---|---
#Q |  | $Q_{\text{GSLIM}}$ | $Q_{\text{Bandit}}$ | $Q_{\text{GSLIM}}$ | $Q_{\text{Bandit}}$
| NDCG@5 | $0.3480$ | 0.3591 | $0.2931$ | 0.3173
| NDCG@10 | 0.3390 | $0.3382$ | $0.2859$ | 0.3030
5 | Precision@5 | $0.3959$ | 0.4040 | $0.3375$ | 0.3639
| Precision@10 | 0.3686 | $0.3590$ | $0.3256$ | 0.3384
| Recall@5 | 0.0815 | $0.0805$ | $0.0367$ | 0.0481
| Recall@10 | 0.1250 | $0.1220$ | $0.0648$ | 0.0783
| NDCG@5 | 0.3720 | $0.3651$ | $0.3148$ | 0.3425
| NDCG@10 | 0.3594 | $0.3456$ | $0.3042$ | 0.3251
10 | Precision@5 | 0.4195 | $0.4088$ | $0.3663$ | 0.3907
| Precision@10 | 0.3868 | $0.3642$ | $0.3456$ | 0.3599
| Recall@5 | 0.0880 | $0.0857$ | $0.0473$ | 0.0547
| Recall@10 | 0.1375 | $0.1314$ | $0.0777$ | 0.0874
| NDCG@5 | 0.3857 | $0.3388$ | 0.3586 | $0.3381$
| NDCG@10 | 0.3709 | $0.3221$ | 0.3398 | $0.3206$
15 | Precision@5 | 0.4347 | $0.3785$ | 0.4050 | $0.3855$
| Precision@10 | 0.3987 | $0.3358$ | 0.3756 | $0.3539$
| Recall@5 | 0.0927 | $0.0797$ | $0.0527$ | 0.0547
| Recall@10 | 0.1437 | $0.1229$ | $0.0843$ | 0.0873
| NDCG@5 | 0.3895 | $0.3053$ | 0.3686 | $0.3205$
| NDCG@10 | 0.3752 | $0.2916$ | 0.3493 | $0.3045$
20 | Precision@5 | 0.4399 | $0.3376$ | 0.4149 | $0.3667$
| Precision@10 | 0.4034 | $0.3004$ | 0.3847 | $0.3360$
| Recall@5 | 0.0961 | $0.0698$ | 0.0548 | $0.0519$
| Recall@10 | 0.1474 | $0.1107$ | 0.0872 | $0.0830$

|  | ML-25 |  | Netflix |
---|---|---|---|---|---
#Q |  | $Q_{\text{GSLIM}}$ | $Q_{\text{Bandit}}$ | $Q_{\text{GSLIM}}$ | $Q_{\text{Bandit}}$
| NDCG@5 | $0.1152$ | 0.1162 | $0.1359$ | 0.1579
| NDCG@10 | $0.1163$ | 0.1183 | $0.1301$ | 0.1504
5 | Precision@5 | 0.1215 | $0.1177$ | $0.1572$ | 0.1754
| Precision@10 | 0.1103 | $0.1066$ | $0.1462$ | 0.1599
| Recall@5 | $0.0291$ | 0.0338 | $0.0152$ | 0.0254
| Recall@10 | $0.0481$ | 0.0558 | $0.0267$ | 0.0421
| NDCG@5 | 0.1539 | $0.1461$ | $0.1703$ | 0.1821
| NDCG@10 | 0.1543 | $0.1465$ | $0.1638$ | 0.1720
10 | Precision@5 | 0.1570 | $0.1473$ | $0.1931$ | 0.2008
| Precision@10 | 0.1422 | $0.1312$ | $0.1788$ | 0.1805
| Recall@5 | $0.0424$ | 0.0428 | $0.0255$ | 0.0316
| Recall@10 | 0.0690 | $0.0684$ | $0.0409$ | 0.0508
| NDCG@5 | 0.1682 | $0.1491$ | 0.2195 | $0.1848$
| NDCG@10 | 0.1674 | $0.1488$ | 0.2016 | $0.1739$
15 | Precision@5 | 0.1736 | $0.1479$ | 0.2369 | $0.2029$
| Precision@10 | 0.1555 | $0.1320$ | 0.2089 | $0.1809$
| Recall@5 | 0.0466 | $0.0437$ | $0.0323$ | 0.0327
| Recall@10 | 0.0756 | $0.0691$ | $0.0491$ | 0.0519
| NDCG@5 | 0.1788 | $0.1469$ | 0.2444 | $0.1804$
| NDCG@10 | 0.1779 | $0.1466$ | 0.2234 | $0.1700$
20 | Precision@5 | 0.1806 | $0.1459$ | 0.2620 | $0.1988$
| Precision@10 | 0.1613 | $0.1299$ | 0.2293 | $0.1767$
| Recall@5 | 0.0499 | $0.0425$ | 0.0374 | $0.0321$
| Recall@10 | 0.0796 | $0.0680$ | 0.0555 | $0.0509$

Table 3: From left to right: Number of questions, metric, results for ML-25,
results for Netflix. Top: recommendations for all items, bottom:
recommendations for long-tail items.

In summary, while our approach $Q_{\text{GSLIM}}$ shows a strong learning
curve with respect to the number of questions, it seems to depend on the
application which approach to choose. If the questionnaire should be very
short, $Q_{\text{Bandit}}$ is probably the preferred method. Otherwise,
$Q_{\text{GSLIM}}$ performs better.

##  7 User Study

Figure 3: This figure shows the layout of a question. It contained the title,
a poster and an abstract of the movie. The layout of a recommendation looked
similar.

As discussed in Section 3.3, we found it necessary to conduct a user study to
confirm the results of our offline experiments. Our study consisted of two
parts. In the first part, the questionnaire part, the participants were asked
to rate ten movies. They could give any rating from one (very bad) to five
(very good) or say that they don’t know the movie, which we refer to as zero-
rating.

In the second part, ten recommendations were shown and the users were asked
whether they know the movie and whether they like (or think they like) the
movie. There was one negative option (bad), two positive options (good, very
good) and one neutral option (don’t know).

Given our limited resources, we decided to compare only $Q_{\text{GSLIM}}$,
$Q_{\text{Bandit}}$ and $R_{\text{Gain}}$. To do so, the participants were
split randomly into two groups. The first group received the questions from
$Q_{\text{GSLIM}}$ and the second group from $Q_{\text{Bandit}}$. Every
participant received the top-5 recommendation from $R_{\text{Gain}}$ (which is
a static recommendation) as well as the top-5 recommendation from the
recommender systems that corresponds to their questionnaire. Note that the
participants did neither know in which group they were, nor which algorithm
computed their questions or recommendations.

Our algorithms were trained using a subset of ML-25. We decided to exclude
items with very few ratings and items produced before 1995 to make sure that
our algorithms (especially $Q_{\text{Bandit}}$) are fast enough for a good
user experience. We also excluded items for which we did not find the
information we wanted to show the users (see Figure 2).

Furthermore, we tried to ensure that the task of recommendation would not be
too simple. First, we removed all but one representative of popular movie
series. Second, all recommendations were limited to long-tail items, as
explained in Section 3.3. The questionnaires could ask to rate short-head
items, though.

The remaining dataset consisted of $162,541$ users, $8,070$ items and
$13,705,543$ ratings.

Our user study had 103 participants, many of them were somehow linked to the
authors. Thus, we don’t claim that the study is representative.

###  7.1 Questionnaire Phase

Interestingly, $Q_{\text{GSLIM}}$ and $Q_{\text{Bandit}}$ pursue very
different strategies for the item selection. While $Q_{\text{Bandit}}$ selects
items that might be good recommendations, this is not so much the case for
$Q_{\text{GSLIM}}$.

Questionnaire | Known Items | Average Rating
---|---|---
$Q_{\text{Bandit}}$ |  $48.7$% | $3.99$
$Q_{\text{GSLIM}}$ |  $34.4$% | $3.67$
Table 4: This table shows some statistics about the questionnaire phase. For
instance, among all items selected by $Q_{\text{Bandit}}$ $48.7$% received a
rating other than zero. Among these items the average rating was $3.99$.

Table 4 shows the statistics. Only $34.4$% of the items selected by
$Q_{\text{GSLIM}}$ received a rating other than zero whereas almost half of
the items selected by $Q_{\text{Bandit}}$ where known to the participants.
Among the known items, the items selected by $Q_{\text{Bandit}}$ also received
the better ratings.

###  7.2 Recommendation Phase

Table 5 shows the results of the recommendation phase, which are surprisingly
clear. $Q_{\text{GSLIM}}$ performs remarkably well in all aspects while
$Q_{\text{Bandit}}$ is not significantly better than the static recommender
$R_{\text{Gain}}$.

| $R_{\text{Gain}}$ | $Q_{\text{Bandit}}$ | $Q_{\text{GSLIM}}$
---|---|---|---
Positive Feedback (PF) |  $52.0$% |  $52.6$% |  $77.2$%
Very Positive Feedback |  $15.7$% |  $13.9$% |  $36.1$%
Unknown Items |  $54.5$% |  $51.3$% |  $25.6$%
PF Among Unknown Items |  $30.0$% |  $28.0$% |  $43.8$%
Table 5: We measured for each recommender system the positive feedback, also
known as hit rate, the very positive feedback, the percentage of unknown items
among the recommendations and among these items the positive feedback. For
instance, $52.0$% of the recommendations generated by $R_{\text{Gain}}$
received a positive feedback by the participants, $15.7$% received a very
positive feedback and $54.5$% of the recommended items were unknown to the
participants.

The recommendations of $Q_{\text{GSLIM}}$ received a positive feedback of
$77.2$%, much more than the other two approaches. Also, if we only consider
the recommendations of items unknown to the participants, the positive
feedback of $43.8$% for $Q_{\text{GSLIM}}$ is outstanding. Thus, even though
the user study was small and perhaps not fully representative, there is at
least a strong indication that $Q_{\text{GSLIM}}$ shows very favorable results
in practice.

Regarding serendipity, one could argue that $Q_{\text{GSLIM}}$ shows worse
results than the other two approaches as only $25.6$% of the recommendations
concerned unknown items. Also, regarding the product of unknown items and
positive feedback among unknown items, which could be considered as the true
relevant recommendations, $Q_{\text{GSLIM}}$ does not perform very well.

From a practical point of view, this might indeed be a weak spot of
$Q_{\text{GSLIM}}$ that should be improved. However, it is important to note
that our design of $Q_{\text{GSLIM}}$ does not consider serendipity at all.
The only objective of $Q_{\text{GSLIM}}$ (as well as of $Q_{\text{Bandit}}$)
is to compute recommendations that receive positive feedback. Thus, we would
blame $Q_{\text{GSLIM}}$ for doing a great job.

Furthermore, even from a practical point of view, we do not think that the
product of unknown recommendations and positive feedback among unknown items
is what we want to maximize. We believe that, from a user’s perspective, it is
much easier to identify known items than irrelevant unknown items. Thus, the
rate of positive feedback among unknown items is probably the most important
measure while the rate of unknown items should not be too low.

##  8 Conclusions

In this work we discussed the idea of eliciting user preferences with SLIM, a
popular approach for top-N recommendation. We first showed in Section 4 that
the common way to train SLIM is unsuitable for this task. This motivated the
presentation of a new training algorithm for SLIM called Greedy SLIM that
computes the SLIM matrix greedily row by row.

We showed in offline experiments that with Greedy SLIM it is possible to
construct a questionnaire $Q_{\text{GSLIM}}$ that improves the recommendation
performance for new users considerably and that it achieves better results
than a popular approach based on latent factors, especially if the
questionnaire contains more than ten questions.

Furthermore, we conducted a user study and were able to confirm the findings
of the offline experiments also in practice. In fact, the results of
$Q_{\text{GSLIM}}$ in the user study are even more remarkable. We, hence, dare
to conclude that SLIM-based questionnaires are an excellent alternative to the
existing LFM-based approaches.

Even though we’ve tried our best to conduct a meaningful user study, we have
to notice that the results might not be representative. We would therefore
like to repeat this experiment on larger scale and would be grateful for
support, if anyone is interested.

A small drawback of Greedy SLIM is its expensive training phase. It took hours
to merely compute 20 rows of the SLIM matrix. Improving these times is a
promising open problem.

Furthermore, there are many possible extensions to $Q_{\text{GSLIM}}$. For
instance, a dynamic version of $Q_{\text{GSLIM}}$ would be interesting that
does not ask the same questions to each user. Moreover, it would be worthwhile
investigating if the presented ideas can be applied to other types of
questions such as pairwise questions.

Another interesting aspect which we did not cover is whether our greedy
approach can be applied to other problem settings as well. It is possible that
this training method leads to better results than the standard training
approach of SLIM with coordinate descent. The big obstacle, however, is the
preprocessing time of Greedy SLIM, which is even worse than with standard
SLIM.

## Acknowledgments

This research was funded by the German Federal Ministry of Education and
Research (BMBF) through grants 01IS17051 Software Campus 2.0.

## References

  * Ning and Karypis [2011] Xia Ning and George Karypis.  Slim: Sparse linear methods for top-n recommender systems.  In _2011 IEEE 11th international conference on data mining_ , pages 497–506. IEEE, 2011.
  * Lam et al. [2008] Xuan Nhat Lam, Thuc Vu, Trong Duc Le, and Anh Duc Duong.  Addressing cold-start problem in recommendation systems.  In _Proceedings of the 2nd international conference on Ubiquitous information management and communication_ , pages 208–211, 2008.
  * Elahi et al. [2019] Mehdi Elahi, M Braunhofer, T Gurbanov, and Francesco Ricci.  User preference elicitation, rating sparsity and cold start.  In _Collaborative Recommendations: Algorithms, Practical Challenges and Applications_ , page 42. World Scientific, New Jersey, 2019.  ISBN 978-981-3275-34-8.
  * Soboroff and Nicholas [1999] Ian Soboroff and Charles Nicholas.  Combining content and collaboration in text filtering.  In _Proceedings of the IJCAI_ , volume 99, pages 86–91. sn, 1999\.
  * Vartak et al. [2017] Manasi Vartak, Arvind Thiagarajan, Conrado Miranda, Jeshua Bratman, and Hugo Larochelle.  A meta-learning perspective on cold-start recommendations for items.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.  URL https://proceedings.neurips.cc/paper_files/paper/2017/file/51e6d6e679953c6311757004d8cbbba9-Paper.pdf.
  * Lika et al. [2014] Blerina Lika, Kostas Kolomvatsos, and Stathes Hadjiefthymiades.  Facing the cold start problem in recommender systems.  _Expert Systems with Applications_ , 41(4, Part 2):2065–2073, 2014.  ISSN 0957-4174.  doi:https://doi.org/10.1016/j.eswa.2013.09.005.  URL https://www.sciencedirect.com/science/article/pii/S0957417413007240.
  * Fernández-Tobías et al. [2016] Ignacio Fernández-Tobías, Matthias Braunhofer, Mehdi Elahi, Francesco Ricci, and Iván Cantador.  Alleviating the new user problem in collaborative filtering by exploiting personality information.  _User Modeling and User-Adapted Interaction_ , 26:221–255, 2016.
  * Cantador and Cremonesi [2014] Iván Cantador and Paolo Cremonesi.  Tutorial on cross-domain recommender systems.  In _Proceedings of the 8th ACM Conference on Recommender Systems_ , RecSys ’14, page 401–402, New York, NY, USA, 2014. Association for Computing Machinery.  ISBN 9781450326681.  doi:10.1145/2645710.2645777.  URL https://doi.org/10.1145/2645710.2645777.
  * Parapar and Radlinski [2021] Javier Parapar and Filip Radlinski.  Diverse user preference elicitation with multi-armed bandits.  In _Proceedings of the 14th ACM International Conference on Web Search and Data Mining_ , pages 130–138, 2021.
  * Sepliarskaia et al. [2018] Anna Sepliarskaia, Julia Kiseleva, Filip Radlinski, and Maarten de Rijke.  Preference elicitation as an optimization problem.  In _Proceedings of the 12th ACM Conference on Recommender Systems_ , RecSys ’18, page 172–180, New York, NY, USA, 2018. Association for Computing Machinery.  ISBN 9781450359016.  doi:10.1145/3240323.3240352.  URL https://doi.org/10.1145/3240323.3240352.
  * Christakopoulou et al. [2016] Konstantina Christakopoulou, Filip Radlinski, and Katja Hofmann.  Towards conversational recommender systems.  In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’16, page 815–824, New York, NY, USA, 2016. Association for Computing Machinery.  ISBN 9781450342322.  doi:10.1145/2939672.2939746.  URL https://doi.org/10.1145/2939672.2939746.
  * Golbandi et al. [2011] Nadav Golbandi, Yehuda Koren, and Ronny Lempel.  Adaptive bootstrapping of recommender systems using decision trees.  In _Proceedings of the Fourth ACM International Conference on Web Search and Data Mining_ , WSDM ’11, page 595–604, New York, NY, USA, 2011\. Association for Computing Machinery.  ISBN 9781450304931.  doi:10.1145/1935826.1935910.  URL https://doi.org/10.1145/1935826.1935910.
  * Rokach and Kisilevich [2012] Lior Rokach and Slava Kisilevich.  Initial profile generation in recommender systems using pairwise comparison.  _IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews)_ , 42(6):1854–1859, 2012.
  * Fonarev et al. [2016] Alexander Fonarev, Alexander Mikhalev, Pavel Serdyukov, Gleb Gusev, and Ivan Oseledets.  Efficient rectangular maximal-volume algorithm for rating elicitation in collaborative filtering.  In _2016 IEEE 16th International Conference on Data Mining (ICDM)_ , pages 141–150. IEEE, 2016.
  * Wang et al. [2017] Huazheng Wang, Qingyun Wu, and Hongning Wang.  Factorization bandits for interactive recommendation.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 31(1), Feb. 2017.  doi:10.1609/aaai.v31i1.10936.  URL https://ojs.aaai.org/index.php/AAAI/article/view/10936.
  * Koren et al. [2022] Yehuda Koren, Steffen Rendle, and Robert Bell.  _Advances in Collaborative Filtering_ , pages 91–142.  Springer US, New York, NY, 2022.  ISBN 978-1-0716-2197-4.  doi:10.1007/978-1-0716-2197-4_3.  URL https://doi.org/10.1007/978-1-0716-2197-4_3.
  * Kabbur et al. [2013] Santosh Kabbur, Xia Ning, and George Karypis.  Fism: factored item similarity models for top-n recommender systems.  In _Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 659–667, 2013.
  * Zheng et al. [2014] Yong Zheng, Bamshad Mobasher, and Robin Burke.  Cslim: Contextual slim recommendation algorithms.  In _Proceedings of the 8th ACM Conference on Recommender Systems_ , RecSys ’14, page 301–304, New York, NY, USA, 2014. Association for Computing Machinery.  ISBN 9781450326681.  doi:10.1145/2645710.2645756.  URL https://doi.org/10.1145/2645710.2645756.
  * Steck [2019] Harald Steck.  Embarrassingly shallow autoencoders for sparse data.  In _The World Wide Web Conference_ , pages 3251–3257, 2019.
  * Steck et al. [2020] Harald Steck, Maria Dimakopoulou, Nickolai Riabov, and Tony Jebara.  Admm slim: Sparse recommendations for many users.  In _Proceedings of the 13th international conference on web search and data mining_ , pages 555–563, 2020.
  * Boyd et al. [2011] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al.  Distributed optimization and statistical learning via the alternating direction method of multipliers.  _Foundations and Trends® in Machine learning_ , 3(1):1–122, 2011.
  * Cremonesi et al. [2010] Paolo Cremonesi, Yehuda Koren, and Roberto Turrin.  Performance of recommender algorithms on top-n recommendation tasks.  In _Proceedings of the Fourth ACM Conference on Recommender Systems_ , RecSys ’10, page 39–46, New York, NY, USA, 2010. Association for Computing Machinery.  ISBN 9781605589060.  doi:10.1145/1864708.1864721.  URL https://doi.org/10.1145/1864708.1864721.
  * Friedman et al. [2010] Jerome Friedman, Trevor Hastie, and Rob Tibshirani.  Regularization paths for generalized linear models via coordinate descent.  _Journal of statistical software_ , 33(1):1, 2010\.
  * Krichene and Rendle [2022] Walid Krichene and Steffen Rendle.  On sampled metrics for item recommendation.  _Communications of the ACM_ , 65(7):75–83, 2022\.
  * Chapelle and Li [2011] Olivier Chapelle and Lihong Li.  An empirical evaluation of thompson sampling.  In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 24. Curran Associates, Inc., 2011.  URL https://proceedings.neurips.cc/paper_files/paper/2011/file/e53a0a2978c28872a4505bdb51db06dc-Paper.pdf.
  * Ning et al. [2019] Xia Ning, Athanasios N. Nikolakopoulos, Zeren Shui, Mohit Sharma, and George Karypis.  SLIM Library for Recommender Systems, 2019.  URL https://github.com/KarypisLab/SLIM.
  * Rashid et al. [2008] Al Mamunur Rashid, George Karypis, and John Riedl.  Learning preferences of new users in recommender systems: an information theoretic approach.  _Acm Sigkdd Explorations Newsletter_ , 10(2):90–100, 2008.
  * Harper and Konstan [2015] F. Maxwell Harper and Joseph A. Konstan.  The movielens datasets: History and context.  _ACM Trans. Interact. Intell. Syst._ , 5(4), dec 2015.  ISSN 2160-6455.  doi:10.1145/2827872.  URL https://doi.org/10.1145/2827872.
  * Bennett et al. [2007] James Bennett, Stan Lanning, et al.  The netflix prize.  In _Proceedings of KDD cup and workshop_ , volume 2007, page 35. New York, 2007.
  * Rendle et al. [2019] Steffen Rendle, Li Zhang, and Yehuda Koren.  On the difficulty of evaluating baselines: A study on recommender systems.  _CoRR_ , abs/1905.01395, 2019.  URL http://arxiv.org/abs/1905.01395.
  * Okanohara [2011] Daisuke Okanohara.  redsvd, 2011.  URL https://code.google.com/archive/p/redsvd/.