Out of thousands of names to choose from, picking the right one for your child is a daunting task. In this work, our objective is to help parents making an informed decision while choosing a name for their baby. We follow a recommender system approach and combine, in an ensemble, the individual rankings produced by simple collaborative filtering algorithms in order to produce a personalized list of names that meets the individual parents' taste. Our experiments were conducted using real-world data collected from the query logs of nameling (nameling.net), an online portal for searching and exploring names, which corresponds to the dataset released in the context of the ECML PKDD Discover Challenge 2013. Our approach is intuitive, easy to implement, and features fast training and prediction steps.
There are many considerations when parents are deciding on a name for their child. Many parents choose to name their babies after a grandparent, other relative, or a close friend. Some others pick names from the actors or actresses of their favorite soap opera. Cultural and societal rules, the meaning of the name, family’s traditions, or religious beliefs also play an important role in many countries at the time of choosing a given name for a baby.
This is indeed a daunting task for the parents and their decision will mark the child for the rest of his or her life. The given name should be unique, making the bearer stand out from the crowd, but at the same time it should also avoid embarrassment of being the source for nicknames, humiliating initials, or annoying email addresses1.
From thousands of names to choose from, how do parents pick the right one for their baby? In this paper, we present an approach to help parents dealing with this information overload problem. In particular, we take a recommender systems approach and show how an ensemble of simple collaborative filtering algorithms can help users to find given names that match their needs from a big pool of names.
We conduct this study in the context of the ECML PKDD’13 Discovery Challenge. This paper documents the approach of team “cadejo” on the o ine phase of the challenge.
The main contribution of this paper is an intuitive approach for the task of given name prediction that is easy to implement, and that features fast training and prediction steps. Our study shows that, in this particular task, our ensemble of simple collaborative filtering building blocks performs significantly better than state-of-the-art latent factor models. 1.1
We consider the dataset as sparse matrix X = [xui], where we use through this paper the letter u for users and i for names, which corresponds to the items in a recommender system setting. We use bold letters for matrices and vectors, and non bold for scalars. The set of users and names2 are denoted by U and I, respectively. Predictions for useritem pairs are denoted as xˆui. The set of names that the user has interacted with is written as I(u). The set of users, who interacted with name i is U(i).
We use the notation Cu(i) to represent the set of names co-occurring with name i within I(u), that is, Cu(i) := f j j i; j 2 I(u) ^ i , jg.
We denote the bag of co-occurring names for a given item i, as follows: C(i) := [ f((i; j); m(i; j)) j i 2 I(u) ^ j 2 Cu(i)g ;
u2U where m(i; j) : I I ! N 1 is a function from the set name pairs (i; j) 2 I I to the set N 1 of positive natural numbers. For each pair of names (i; j), m(i; j) represents the number of occurrences of such pair in the bag, i.e., its multiplicity. The aggregated bag C over all items corresponds to C := Si2I C(i).
We use S u to represent the user u’s sequence of interactions ordered according to the corresponding timestamp , e.g., if user u searches first for name i1, after that for i4 and finally for name i2, then his sequence S u is represented as:
Su = i1 ! i4 ! i2:
For example, consider three users u1, u2 and u3, and their corresponding sequences S of search actions in temporal order:
Su1 = i1 ! i4 ! i2 ! i3 Su2 = i4 ! i5 ! i1 ! i4 ! i3
Su3 = i3 ! i5 ! i6 ! i7 ! i4 2 In this paper, we use the terms “names” and “items” interchangeably.
The bag of co-occurrences for item i4, C(i4), sorted in decreasing order of multiplicity, is given by:
C(i4) = f((i4; i3); 3); ((i4; i1); 2); ((i4; i5); 2); ((i4; i2); 1); ((i4; i6); 1); ((i4; i7); 1)g : 1.2
The dataset provided for the o ine challenge is based on the query logs of nameling (nameling.net), an online portal for searching and exploring names. The collection comprises the time period from March 6th, 2012 to February 12th, 2013. In total the dataset contains 515,848 interactions (i.e., activities) from 60; 922 di erent users and 50; 277 unique names. Figure 1a shows the frequency of names per user. We can observe that it corresponds to a characteristic graph of a long-tail distribution, where few names tend to concentrate a large number of users. The frequency of users per given name is shown in Figure 1b.
There are 5 di erent types of interactions within the dataset, which are described as follows: 1. ENTER SEARCH: the user explicitly writes a name in the search field of nameling’s website in order to search for it. 2. LINK SEARCH: the user clicks on a name of showed names at nameling’s website, following a link to a search result page. 3. NAME DETAILS: the user requests more detailed information of a name. 4. LINK CATEGORY SEARCH: Wherever available, a name is categorized according to the corresponding Wikipedia article. Users may click on such a category link to obtain all names in the corresponding category. 5. ADD FAVORITE: the user saves the name in his list of favorite names.
In addition to these datasets there is a list of valid or known names provided by the organizers of the challenge, which contains 36,436 given names.
104 cy103 n e u freq102 s e anm101 100 104 y103 c n e requ102 f r e su101 100 100 101 102 103 104 105 100 101 102 103 104 105 users (a) Frequency of names per given user.
names (b) Frequency of users per given name. The task for the o ine challenge is to recommend a personalized ranked list of names for each user in the test set, based on the users’ (partial) search history in nameling.
The recommender system’s quality is evaluated with respect to the set of names that users have entered directly into nameling’s search field. The rationale to restrict the evaluation to ENTER SEARCH activities is that all other user activities are biased towards the lists of names which were displayed to nameling users.
The test set is built by taking from the training data the chronologically last two names, which had directly been entered into nameling’s search field (i.e., using the ENTER SEARCH activity) and which are also contained in the list of known names as detailed in the challenge description3.
The assessment metric for the recommendations is Mean Average Precision at a
cut-o of 1000 (MAP@1000) [
In our study we could not find a clear mechanism on how to exploit activities of type LINK CATEGORY SEARCH, and therefore we drop such interactions from the dataset. We also concentrate only on names which appear as part of at least one interaction and that were also present in the known names list. In total our experiments consider a total number of 260,236 user-name pair interactions, from jUj = 60; 922 di erent users and jIj = 17; 467 unique names. The mean of names per user is 4:35, the median is 3 names per user, with a minimum 1 and a maximum of 1670 names per user.
To evaluate our results we built a cross-validation dataset using the script provided by the organizers of the challenge. The script gives us a validation with 13,008 users and two target names. From these 13,008 users, 2,264 are not within the 4,140 users in the test set, which are the ones we are required to give recommendations. In order to have a more representative cross-validation dataset, for each of these 2,264 users we also selected, from the remaining transactions in the training set, the last 2 names the user interacted with. Note that in this case we ignored the additional constraints imposed by the script, e.g., the type of activity. 2
Although top-N recommender systems have been studied in depth, the particular task
of recommending given names is rather new. For example recent work by Mitzla
et al. studies the relatedness of given names based on data from the social web [
This work shows the importance of co-occurrence networks for the recommendation task. Our approach also exploits name co-occurrences in the Name-to-Name algorithm introduced in Section 3.
The NameRank algorithm introduced in [
Collaborative Filtering (CF) algorithms are best known for their use on e-commerce Web sites, Online Social Networks, or Web 2.0 video sharing platforms, where they use input about a user’s interests to generate a (ranked) list of recommended items. In this section, we describe the collaborative filtering models which are used by our approach as well as the assembling strategy to compute the final prediction. 3.1
This approach for name recommendation is based on the classic item-based
collaborative filtering algorithm introduced by Amazon.com [
To determine the most similar match for a given name, the algorithm constructs a bag of co-occurring names across all user interactions in the collection. The rationale behind this algorithm is that there are many names that do not co-occur in any of the user’s name transactions (I(u)), and thus the approach is e cient in terms of processing time in memory, since there is no need to compute similarities over all possible pairs of names in the collection.
To compute the final recommendation list, the algorithm finds names similar to each of the ones in the user’s set of names I(u), aggregates those co-occurring names, and then recommends the most popular or correlated names. This computation is very quick, depending only on the number of names the user has interacted with.
The Name-to-Name algorithm is summarized in Algorithm 14. 3.2
Neighborhood-based recommendation is a classic approach for Collaborative Filtering that still ranks among the most popular methods for this problem. These approaches are quite simple to describe and implement featuring important advantages such as the ability to explain a recommendation and to capture “local” relations in the data, which 4 In Section 4, we explain the models used in our ensemble and provide more details about
Algorithm 1’s functions getRandomName() and getRandomCoName() in this context.
Target user u 2 U. Recommendations will be computed for this user; I(u) I: set of names that the user has interacted with; C : bag of co-occurring names; N 2 N: size of the recommendation list; max iterations: maximum number of iterations.
Output: Recs(u): ranked list of recommendations for user u.
are useful in making serendipitous recommendations. In particular, we used the Top-N
variants of the User-Based and Item-Based algorithms [
Since the value estimates of our models, xˆ, can be in di erent scales, we do not combine their values directly, but rather we use their rank estimates. Formally, the ensemble of the rank estimates of l models is given by: xˆuraink := X
l l
1 rank(xˆuli) ; (1) where l is a weight associated to the predictors of model l, rank(xˆuli) is the rank position within the lth ranked list corresponding to the estimate value xˆuli. That is, the combined estimate xˆrank corresponds to the weighted reciprocal rank of the individual models.
ui 4
In this section, we detail the collaborative filtering models, report their parameters, and individual recommendation performance in terms of MAP@1000. We also present the performance boost achieved by our ensemble.
The ensemble of our solution consists of 9 collaborative models that we describe as follows. [m0 – N2N-Freq] is a Name-to-Name CF model that is created using the names cooccurring with the names of a given test user, according to Algorithm 1. This model considers the “ENTER SEARCH”, “LINK SEARCH” and “NAME DETAILS” activites to build the bag of co-occurrences. We randomly select a name i for given test user u via the getRandomName( ) procedure specified in Algorithm 1, where the chance for a name to be chosen is proportional to how often user u has interacted with it, which adds a positive bias towards those names that are more searched by the user. Furthermore, we also bias the selection of the co-occurring name j (getRandomCoName( ) procedure in Algorithm 1) towards the multiplicity of the pair (i; j).
Example. To illustrate this approach, consider the following example. Our dataset consists of five users, u1 : : : u5, and our task is to predict a recommendation list of names for user u1. The sequence of interactions for user u1 is denoted as S u1 (cf. Section 1.1) is given by
Su1 = i4 ! i1 ! i4: and for the other four users, their corresponding sequences are:
Su2 = i1 Su3 = i4 ! i5 ! i4 ! i1 ! i3 ! i4
! i3 Su4 = i3 ! i6 ! i7
! i4 Su5 = i1 ! i5 ! i2 then, the bags of co-occurrences for the names in Su1, i.e., i4 and i1, sorted in decreasing order of multiplicity, are given by:
C(i4) = f((i4; i1); 3); ((i4; i3); 3); ((i4; i5); 1); ((i4; i6); 1); ((i4; i7); 1)g:
C(i1) = f((i1; i4); 3); ((i1; i3); 2); ((i1; i5); 2); ((i1; i2); 1)g: Using the N2N-Freq shown in Algorithm 1, we first chose one name from user u1’s names (i.e., from I(u1)), and the name’s corresponding bag of co-occurrences. Let us assume that i4 2 I(u1) and its respective bag C(i4) are chosen. The first item to be included in the list of recommendations is i3 (i1 would not be chosen because i1 2 I(u1)).
In the next iteration, consider that C(i4) is selected again, given that it has a higher probability to be picked due to the frequency of item i4 in the sequence S u1. In this case, i5 would be the item chosen to be included in the list of recommendations. In the third iteration, the list selected is C(i1), then the first item to be selected is i2. Note that there are no more items from C(i1) that can be included in the list. Then, R(u1) is filled up using items from C(i4).
Finally, the list of recommendations for u1 corresponds to:
R(u1) = [i3; i5; i2; i6; i7] : [m1 – N2N-Freq-ES] follows the same approach as model m0, but the bag of cooccurring names used to compute the predictions considers only the “ENTER SEARCH” activity to build the bag of co-occurrences. [m2 – N2N-Time] is also a Name-to-Name CF model similar to m0, but with the difference that the names I(u) are not selected biased towards frequency of user interactions, but towards recency. That is, the names included in the recommendation list are those that co-occur with the last searches of the test user. The goal of this model is to capture the latest user preferences as input to compute the recommendations.
Example. Using this algorithm, with Su1, Su2, Su3, Su4 Su5, C(i4) and C(i1) from the example given for m0. Using this algorithm, biased towards recency, all selectable items from C(i4) have a higher probability of being chosen. The firsts items would correspond to i3, i5 and i6. From C(i1) the selectable items are i7 and i2. A possible recommendation list corresponds to:
R(u1) = [i3; i5; i6; i7; i2] :
[m3 – N2N-Time-ES] follows the same temporal strategy as m2, but the bag of
cooccurring names only considers the “ENTER SEARCH” activity.
[m4 – N2N-Time-NoTop5] this model is the same one as m2, but only the top-5 most
popular names are excluded from the bag of co-occurrences. The rationale behind
this model is to get a more specific list of names, avoiding the names that are too
popular.
[m5 – N2N-Time-NoTop10] This model is similar to model m2, with the exception
that the top-10 most popular names in the collection have not been considered to
build the bag of co-occurrences.
[m6 – UB-T] is a user-based collaborative filtering algorithm [
N2N-Freq-ES N2N-Time N2N-Time-ES N2N-Time-NoTop5 N2N-Time-NoTop10 UB-T UB-LL PR
Final ensemble
baseline Most Popular Names
[m7 – UB-LL] is a user-based model that uses likelihood as similarity metric. As in
the previous model, we also used a neighborhood of size 100 in this case.
[m8 – PR] This model corresponds to PageRank [
All models, except m6 and m7, were implemented in the Python programming language, using the numeric libraries of NumPy and SciPy6. For the user-based models (m6 and m7), we used the Java implementation provided by Apache Mahout7.
Table 1 summarizes the individual performance of these models. We also report the performance of a non-personalized model that always recommends the most popular 1000 names.
We compute the final ensemble by first combining di erent flavors of the same approach, and then combining the resulting ranked lists as explained in Section 3.3. Figure 2 illustrates the assembling process.
All weights (the ’s in Equation 2) were determined experimentally based on the performance achieved by the (sub-)ensambles in our cross validation set. 6 http://www.scipy.org/ . 7 http://mahout.apache.org/ .
We found that the best way to combine the N2N-Freq* (m0 and m1) and N2NTime* (m2 and m3) algorithms was by giving them equal weights, this is not surprising given their very similar performance. On the other hand, the performance of the User Based algorithms di ers more substantially. In this case, we found that the best way to combine them was by giving a higher weight to UB-LL ( UB LL = 0:8) and a weight of
UB T = 0:2 to UB-T, for a UB combination (m6 + m7) that achieved a MAP@1000 of 0.028880.
We combine the unpersonalized ranked list output by the PageRank (m8) with the UB ensemble to fill up user’s lists with less than 1000 items, using an asymmetric weighting scheme, favoring the UB combination.
The final ensemble combines the N2N family combinations with the ranked list from the filled UB models. We found that the best combination was obtained by giving the N2N and UB*+PR a weights of 0.8 and 0.2, respectively. The MAP@1000 for the final ensemble reaches a value of 0.036766. Please refer to Table 1 to compare the ensemble’s performance to the one of the individual models.
m2 m4 m5 m6 m7
N2N-Freq* m0
0.5 0.034134 0.036133 m1 0.5 0.3 0.036766 m3 0.25
N2N-Time* Figure 2. Final ensemble. The weights for the partial model ensembles are indicated next to the corresponding arrow. The symbol ‘+’ indicates the assembling of the models. The
The low values of MAP@1000 obtained by our approach on this dataset give an idea of how di cult the problem of recommending given names is.
Given the evaluation design of hiding the last two names the user interacted with, models that capture the latest user preferences, e.g., from the session information, tend to work well for us.
Neighborhood-based algorithms perform worse than item-to-item co-occurrences. Within the item-based and user-based variants, we observed that results from itembased collaborative filtering were inferior to the ones achieved by the user-based models, and therefore we did not consider them in the ensemble.
One of CF’s most successful techniques are low dimensional linear factor models,
that assume user preferences can be modeled by only a small number of latent factors.
One of such methods is matrix factorization, which has been e ectively used for the
rating and item prediction task [
We conducted extensive experiments using state-of-the-art CF algorithms based
on matrix factorization. In particular, we evaluated the performance of BPR [
We also learned a name-to-name similarity matrix from the co-occurring names
adjacency via optimizing a ranking criteria, as suggested in [
Furthermore, we also tried to optimize directly for MAP following a Learning to
Rank framework suggested in [
Given this performance, we did not include any latent factor model in our ensemble. Why the results achieved using latent factor models, for this particular task of name prediction, are inferior to the ones obtained with simple methods? In our future research, we plan to explore this question more in detail. 6
In this paper, we presented an ensemble of several algorithm for personalized ranked recommendation of given names. We found that the co-occurring name information was a key component for the Name-to-Name algorithms used in our ensemble. Our method is intuitive and simple to implement, and does not su er from the scalability issues as previous methods introduced for this task.
As a future work, we plan to further explore this interesting challenge in order to help parents deciding what is the best name for their baby. We would like to thank Asmelash Teka and Rakshit Gautam for their valuable feedback. This work is funded, in part, by the L3S IAI research grant for the FizzStream! Project. Bernat Coma-Puig is sponsored by the EuRopean Community Action Scheme for the Mobility of University Students (ERASMUS).