We describe in this paper our contribution to the ECML PKDD Discovery Challenge 2013 (O ine Track). This years task was to predict the next given names a user of a name search engine interacts with. We model the user preferences with a sequential factor model that we optimize with respect to the Bayesian Personalized Ranking (BPR) Optimization Criterion. Therefore we complement the sequential factor model with pre x smoothing in order to explicitly model syntactical similarity.
We describe in this paper our contribution to the ECML PKDD Discovery
Challenge 2013 (O ine Track). This years task task was to recommend given names
to user of the name search engine "Nameling"[
We use a factorized personalized Markov Chain (FPMC) [
(1) returns the estimated preference of a user U at time T for a name N . To obtain the user speci c ranking for every user u 2 U , each name is scored { i.e. y^(u; t; n1), y^(u; t; n2), etc. is computed { and the names are sorted by their score. We further de ne D U T N as the training set of available names which have been observed in the logs.
In order to extract training samples from the user activities, we rst de ned four indicator functions. These are then used to encode the training samples as sparse real valued features that can be used in a factorization machine. Finally, we give a formal de nition of our pre x smoothing approach. 3.1
Our model assumes that the name preference of a user u at time t can be explained by: 1. The ID of the user: u. 2. The ID of the name: n. 3. The last name selected by the user: l : U T ! N . 4. The history of all names selected by the user up to time t:
h : U T ! P(N ).
Besides these four indicators, the model should also take into account all
interactions between indicators. E.g. the interaction between name n and last name
l(u; t) would model the e ect for choosing name n if the name l(u; t) has been
selected before. In total, the rst three indicators correspond to a personalized
Markov chain [
The number of pairwise interactions between variables is high and cannot be
estimated reliably with standard parametrization. Thus, we use a factorized
parametrization [
The ideas described so far can be realized with a factorization machine [
For example, for a case (u; t; n) let the values of the four indicators be: 1. user ID: 0, 2. name to rank: Anna, 3. last name selected by user: Jana, 4. history of all names selected by the user up to time t: fPetra, Annabelle, Mariag. This can be encoded as a real valued feature vector of the form x(u; t; n) = (1; : : : ; 0; 0; 1; 0; : : :; 0; : : : ; 1; 0; : : :; 0; 0:33; : : : ; 0:33; : : : ; 0:33; : : : 0): | {z } | {z } | {z } | {z } jUj jNj jNj jNj
The factorization machine (FM) model [
p p p X wj xj + X X j=1 Here, w0 2 R; w 2 Rp; V 2 Rp k are the model parameters, k 2 N is the size/ dimensionality of the latent space. Thus, the model has one feature vector vi for each variable xi.
Empirically inspecting the generated recommendations with this model shows (see Table 2) that the semantic meaning of names is found: e.g. if a user searches mainly for female names, female names are recommended; if the user selects typically short names, short ones are recommended, etc. The reason for the success is that the model automatically nds latent features vn 2 Rk for each name n which describe its characteristics. Such characteristics could be gender, name length, etc. In general, the proposed model can express any kind of pairwise relation between names1. However, under small data sizes, the model might have problems to nd relations between infrequent names. To make an example, the model can express and will automatically learn that Anna and Anne are syntactically similar or that Farid and Behrouz are semantically similar (both Persian masculine names) if the data logs are large enough. However, the size of the observed logs is limited and the model cannot learn all these relations reliably { especially not for infrequent names.
To overcome the problem, we inject some syntactical relations manually into the model. We create indicators stating that two names (name n and last name l(u; t)) share a pre x of length m { we consider pre x lengths of m 2 f1; 2; 3; 4; 5; 6g. We add these indicators about syntactical similarity to the FM model mentioned above: y^(u; t; n) := y^FM(x(u; t; n))
X + m2f1;2;3;4;5;6g
zm (pre x(n; m) = pre x(l(u; t); m)); (4) where is the indicator function { i.e. (b) = 1 if b is true { and pre x(s; m) returns the pre x of string s of length m.
The nal model is slightly more complex and considers also syntactical similarity with the next-to-last name:
+ y^(u; t; n) := y^FM(x(u; t; n))
X X 1 Note that semantic or syntactical similarities are also just pairwise relations.
zm;t0 (pre x(n; m) = pre x(l(u; t0); m)): (5)
Please note that the idea of pre x smoothing { i.e. the indicator (pre x(n; m) = pre x(l(u; t); m)) { can be used directly in the FM by enlarging the feature vector x. Using this representation, the parameters zm;t are part of the w parameters of the original FM. Extending the pre x smoothing to longer pre xes as well as taking into account names earlier then t 1 could further improve the model. 4
We have a lot of positive samples if we assume that the user likes names he interacts with but we know little about other names. Encoding all names the user didn't interact with as negative samples can introduce wrong user preferences since we can not distinguish between a name the user knowingly ignored and a name the user has never seen. We avoid this problem by using a pairwise loss function. 4.1
The model parameters of the FM are learned by discriminating between
previously selected and unselected names. This optimization criterion has been
proposed for item recommendation as BPR (Bayesian Personalized Ranking ) [
X
X (u;t;n)2D n22(Nnfng) ln (y^(u; t; n) y^(u; t; n2)) jj jj 2 (6) where y^ is the FM (using the predictor variables encoded in the real valued vector x) and is a vector containing the model parameters V; w; w0. 4.2
The standard BPR algorithm [
Even though FM parameters and pre x smoothing could be learned jointly with BPR, for simplicity2 we learned only the FM parameters with BPR and selected the pre x smoothing parameters (only 12 parameters) manually. 2 The reason for separating both parts were only of practical matter because we reused an existing implementation. 4.3
The BPR algorithm is a point estimator and returns one ranking. We consider uncertainty in the ranking by running the learning algorithm three times, each time with a di erent sampling hyperparameter. While training each model, we select3 in total 20 iterations for which we predict the ranking each { i.e. we have 20 (slightly) di erent scores y^(u; t; n) for each triple (u; t; n). The nal scoring function is an unweighted average of the 20 scoring functions. 5
In this section, we rst present our scores from the o cial leaderboard and then discuss the latent features learned by our model on randomly selected samples. 5.1
We separate the training data into a new validation and training set using the splitting script provided. This gives us a training set with 60.922 user and a test set with 13.008 user. We use the rst 3.000 user from the new test set to calibrate our models. 5.2
3 The selected iterations were chosen close to the best iterations on the holdout set, i.e. slightly before and after the best iteration. In this section, we demonstrate on samples that our model is able to represent name similarities and user preferences through its latent variables. We illustrate this on name characteristics such as gender or length because the e ects of those items are easy to recognize. More subtle e ects might also be captured by our model but an casual inspection on a small sample might not su ce to identify them.
We select a subset of users from the challenge test set that have at least 30 and at most 50 activities (This is done to avoid users without history and to save space by avoiding user with a very large history). From this set, we randomly select 18 users and list them in table 2. The rst line h(u; t) for each user lists all names in his user history. Duplicates and names that are not used in the competition (not listed in namelist.txt) have been removed. The second line lists the top 14 recommendations generated by our FM model4. 4 The number of listed recommendations and the number of randomly selected users are adjusted to the available space. 5.4 Even though the predictive strength is best jugged by the leaderboard score, we want to give an impression of the kind of relationships that our model has learned from the training data. Please note that the rankings presented here are without pre x smoothing. This means that the model had no information on how long or which characters a certain name contains since names are only represented by unique identi ers.
Our model learns to distinguish between female and male names and recognizes if a user prefers male or female names. For users that have very strong preferences, such as user 6631, 9617, 29470, 3017, 28995, the recommendations that are accordingly balanced (see Table 2 and Figure 1). For users with very few user activities this becomes less reliable as can be seen on users; 16175 and 14192.
The model also learned if a name is long (user 3017, 38852, 16175) or very short (user 9617, 29470). It also recognizes if a user prefers infrequent names User 28995 for example has kjell and enno in his history and gets names like levi and nn recommended. Double consonant names are surprisingly frequent in the recommendations for user 31937, while names with similar pre xes have similar ranks for user 16175 (martin, markus, maximilian ) or user 20508 (julia, julius ) and also lotte and charlotte are ranked next to each other for user 31937. A more detailed analysis of the learned ranking could reveal more information on how people judge the similarities of given names. 6
In this paper, we have shown that a Factorization Machine [
The data used in this competition were strongly dominated by German speaking users (according to the user location obtained from the ip addresses) but our approach is supposed to work equally well with data that contain names from different alphabets or a user base that contains strong regional preferences without any modi cation.
We like to point out the close relation of given name recommendation to tasks such as movie recommendation where factor models have been very successful. The latent variables in this competition represent here syntactic and semantic similarity instead of movie related characteristics like genres or common actor. We have further shown that for infrequent names and small data sets the injection of regularizing information such as syntactical similarity does improve the prediction quality. We however expect that the bene t of information injection diminishes with the size of available data.
We gratefully acknowledge funding by Baden-Wurttemberg Stiftung.