Name Nationality Classification with Recurrent Neural Networks

1 Introduction

Personal names can be used to investigate how characters are arranged for naming. Among proper nouns, personal names tend to have many more conventional structures than other proper nouns such as company names or acronyms. These structures become clearer when the names are confined to a specific ethnicity. For instance, Russian names tend to have "-sky" or "-v" at the end (e.g., Melnitsky, Shagaev), and German names frequently include "-mann" or "-urg-" (e.g., Hermann, Burgher). However, these naming conventions become subtler and more difficult when a model predicts a specific nationality of a name.

To predict the nationality of a name, a model must consider several different factors of a country. First, the language of a country is one of the most important factors to consider. For example, "Chenglong Zhang" is an easily recognizable Chinese name. Second, geographical location can provide useful information for name to country prediction. Germany and Austria are geographically close to each other and categorized as Germanic countries. Therefore, personal names of Germans and Austrians are difficult to separate. Third, the history of a country sometimes plays a crucial role for the naming convention. In Mexico, the Aztec empire in the 16th century was controlled by Spain until 1821. Due to this historical fact, Mexican names tend to look like Spanish names. For example, "Jose Calderson" is a Spanish name and "Jose Corona" is a Mexican name. Other subtle factors can effect the naming conventions varying from country to country. "Von" and "Van" can be one example. The prefix "Von" is related to German origin (e.g., Anake Von Seck, Ida Von Nagel) while "Van" is commonly used in Dutch names (e.g., Wouter Van Pelt, Eake Van Nes). Due to its diversity and subtlety, naming conventions of all countries are quite difficult to distinguish. Table 1 shows how difficult it is to distinguish countries by personal names.

On the other hand, as Web services grow, personal names have become one of the most abundant sources of data on the Web [Ambekar et al., 2009; Chang et al., 2010; Treeratpituk and Giles, 2012; Huang et al., 2014; Bergsma et al., 2013]. Results of ethnicity classification have been often utilized as key features of other classification tasks [Wu et al., 2014; Humphreys et al., 2016]. If one can predict or suggest proper countries for personal names, services such as web browsers or mobile applications can benefit from knowing each user's nationalities. However, leveraging personal names for nationality prediction is quite challenging, due to their simple but diverse and subtle structures.

We propose a recurrent neural network based model which predicts nationalities of each name with considerably high accuracy. Without specifying any hand crafted features of naming conventions, our model's performance is comparable with that of previous feature based models. While previous models mainly focused on predicting the ethnicity of a name, we propose to predict the nationality of a person solely based on characters of a name. Character level embeddings dramatically improves the performance, proving its effectiveness in automatic feature extraction. We also evaluate our model on the ethnicity classification task to test the generalization of our model. To further show the effectiveness of our model, we provide a qualitative analysis on incorrect answers and character embeddings.

Contributions of this paper are three-fold.

• We propose a recurrent neural network based model, predicting the nationality of a personal name solely based on the characters without using external resources or hand crafted features.
• Using character embedding, our model automatically extracts character level features for the name nationality classification task.
• Compared to previous feature based models, our model achieves comparable or better performances on the name nationality classification and name ethnicity classification tasks.

In Section 2, we introduce related studies on personal name based classification tasks and recurrent neural networks. In Section 3, we briefly describe our task and describe our recurrent neural network based model. We provide the Olympic records dataset and the data processing rules in Section 4. In Section 5, we present our results on the nationality and ethnicity classification tasks. In Section 6, we qualitatively show how our model successfully predicts nationalities using automatic feature extraction. Conclusion and future work are presented in Section 7. Our source code and datasets for the experiments are publicly available on the Web. 1

2 RelatedWork

2.1 Personal Name Classification

Despite the simplicity of name data, there are a number of studies that utilize personal names for classification tasks.

Ethnicity classification is one of the main tasks that utilizes personal names. [Ambekar et al., 2009] classified 13 cultural groups using decision tree and the Hidden Markov Model on a news corpus. [Treeratpituk and Giles, 2012] classified personal names into 12 ethnic groups based on phonetic sequences information and the character sequences information. [Harris, 2015] extracts race and ethnicity different from classical classify-and-aggregate approaches. Classifyand-aggregate approaches focused on individual classification of names while [Harris, 2015] considered the proportions of each unique name.

There are some following studies that utilize the results of name ethnicity classification task. [Wu et al., 2014] used same model in [Treeratpituk and Giles, 2012] to analyze each ethnicity group's proportion in the computer science research community. [Humphreys et al., 2016] use the ethnicity classification method to find out the relationship between house marketing and ethnicity and prove the cultural superstitions of Chinese.

Name classification models can be also used for classifying users in social networks. [Chang et al., 2010] trains a classifier using a Bayesian approach with U.S. Census name data. The classifier found relationships between Facebook user names and ethnicities. [Pennacchiotti and Popescu, 2011] classifies Twitter users into nationalities or ethnicities using several machine learning approaches. They used various features such as name, profile, tweeting behavior, and linguistic content. Another approach of Twitter user classification is studied by [Bergsma et al., 2013]. Instead of utilizing user profiles, [Bergsma et al., 2013] used clusters of users' first names, last names, and locations to identify users. [Liu and Ruths, 2013] focuses on gender classification in Twitter using SVM-based classifier and first names. [Huang et al., 2014] utilized Twitter based ethnicity classification results and other information such as user profiles to predict a user's nationality.

1 https://github.com/63coldnoodle/ethnicity-tensorflow

[Treeratpituk and Giles, 2012] is one of the studies most similar to this paper. They utilized crawled Wikipedia data for name ethnicity classification task and used multinomial logistic regression for the task. Their model uses various features from basic n-grams to external features such as Double Metaphone or Soundex. Because [Treeratpituk and Giles, 2012] did not share their algorithm or the dataset, we reconstructed the feature based algorithm proposed in their paper and compared the model to our model on the name nationality classification task. As far as we know, this is the first work to classify nationalities based solely on personal names. Also, as [Treeratpituk and Giles, 2012]'s model was built for the ethnicity classification task, we adjusted our dataset for the ethnicity classification task for a fair comparison. We mapped each country to a probable ethnicity using specific rules on each country's race ratio.

2.2 Recurrent Neural Networks

Recurrent neural networks are known for their ability to predict sequential data such as natural language. [Mikolov et al., 2010] showed that recurrent neural networks is effective on language modeling. [Bahdanau et al., 2014] used recurrent neural networks for machine translation, achieving performances comparable with statistical machine translation models.

However, due to its recurrent structure, recurrent neural networks tend to suffer from long-term dependency [Bengio et al., 1994] and severe overfitting problems [Zaremba et al., 2014]. To learn long-term dependencies, [Hochreiter and Schmidhuber, 1997] suggested Long Short Term Memory which significantly reduced the long term dependency problem using memory cell and forget gate. Similar RNN cells such as Gated Recurrent Unit (GRU) [Cho et al., 2014] were introduced to improve efficiency of LSTM. Overfitting problems of RNNs were alleviated with applying dropout on non-recurrent connections of RNNs [Zaremba et al., 2014].

As a result, recurrent neural networks achieve state-of-theart performance on sequential data especially in natural language processing. Image captioning [Xu et al., 2015], question answering [Kadlec et al., 2016], and machine translation [Bahdanau et al., 2014] all benefited from recurrent neural networks. Also, in most of the previous studies, they utilize an ensemble version of neural networks to boost each model's performance. It is empirically well known that the neural network ensemble works well in many classification tasks [Zhou et al., 2002]. We propose to use recurrent neural networks for name nationality and ethnicity classification tasks. We build a single model that resembles the structures of ensemble neural networks.

2.3 Character Embedding

The concept of dense representation of words was first introduced by [Bengio et al., 2003]. They mapped each word to an embedding lookup table and used resulting dense vectors for language modeling. [Collobert et al., 2011] further improved the idea of word embedding and proved the versatility of word embedding in multiple NLP tasks. After the development of more efficient word embeddings [Mikolov et al., 2013; Pennington et al., 2014], word embedding became a basic component of neural network based natural language processing.

Also, character level embeddings gained popularity among researchers. [Kim et al., 2015] used character embedding to construct word level representations to deal with the "out of vocabulary" problem. [Chiu and Nichols, 2015] also used character embeddings with a convolutional neural network for named entity recognition. However, none of them utilized character embeddings for personal name classification.

3 Task &Model Description

3.1 Name Nationality (Ethnicity) Classification

The objective of the task is to predict the nationality or ethnicity of a personal name. Given a personal name X = [x0, x1, ..., xn-1] where xk indicates kth character of a personal name with maximum length n. Note that xk can be any ngram character such as a unigram or bigram. Name nationality classification task is then:

where yi is ith nationality (ethnicity) label and D(·) represents any kind of discriminative model with trainable parameter θ. g(·) is a function for character level feature extraction.

Note that the range of y differs between nationality and ethnicity with the former usually having more than 10 times the number of classes. For our dataset, we used 127 nationalities and 13 ethnicities, which makes the nationality prediction task much more difficult.

3.2 Model Description

To capture the structures of character sequences, we opt for a recurrent neural network with long short term memory [Hochreiter and Schmidhuber, 1997] as our basic model. For basic RNNs, the hidden state of the neural networks are updated as follows:

where hlt is a hidden state of RNN at time step t in lth layer. Note that h0t = xt for our task. Wxh, Whh, and bh are parameters to learn, and σ is a basic sigmoid function. The probabilities for each class yi is given as,

where Whz and bz are trainable parameters. However, due to the long term dependency problem, basic RNNs often fail to convey useful information in the hidden states. [Hochreiter and Schmidhuber, 1997] introduced Long Short Term Memory to alleviate the problem using memory cell and forget gate. LSTM is constructed as follows:

where W∗ and b∗ are trainable parameters. ⊙ indicates element-wise multiplication. Long term memory can be restored from clt where the information is written with input gate i and previous cell clt-1 , and updated with forget gate f. After retrieving the hidden state of LSTM, probabilities for each class are the same as Equations 3 and 4. While training the model, LSTM suffered severe overfitting on the training data. To mitigate the problem, we added a dropout to non recurrent part of the RNN as described in [Zaremba et al., 2014].

As inputs xt are represented as one hot encoding, it is difficult to capture the semantics of each character with respect to the naming convention. Thus, we applied character level embedding to the input xt to learn more dense representations. From one hot encoded xt, new input vector x′t is given as follows:

where P ∈ IRd×K is a projection matrix which turns 1 of K encoded vectors into corresponding dense vectors x′t ∈ IRd . We initialized character embeddings in two different ways, random uniform of [-0.1, 0.1] and Skip-gram [Mikolov et al., 2013]. When using Skip-gram, we constructed a training corpus consisting of characters of each name. When using Skipgram, projection matrix P is obtained by maximizing the following log probability:

where T is total number of characters of all names, c is the size of context window and Pt is the t-th column vector of P . We used window size of 5 (i.e., c=5) and pretrained the vectors for 10 iterations. Details of Skip-gram can be found in [Mikolov et al., 2013]. In the experiments, we have found that Skip-gram pretrained models achieve better and more robust performances than randomly initialized models. To learn various n-gram features, we constructed three different projection matrices for unigram, bigram, and trigram. Each of them were inputted to three different recurrent neural networks as shown in Figure 1. We concatenate hidden vectors of each RNN and predict the class label yi. We found that an additional hidden layer after the concatenation gave a slight improvement of performances. Finally, we define and optimize our cross entropy loss function L(θ) as follows:

We trained our model with back propagation through time [Werbos, 1990].

4 Dataset

We crawled Olympic records data from official Olympic website 2 . Total 17721 pairs of personal names and nationalities were collected and statistics of the dataset is in Table 2.

We processed the data into two different ways. First, we did not preprocessed the raw crawled data, preserving all the capital letters and special characters such as quotation marks or parenthesis (e.g., Anton (Toni) ROM). There exist 11 different non-alphabetic special characters in this dataset, which we call a raw dataset. In this raw dataset, there exists an extreme scarcity of personal names where some countries have only 1 personal name.

2 http://www.olympic.org

3 18 countries had only one names each.

For cleaned dataset, we preprocessed the raw dataset as follows: we removed all the redundant characters such as (") or (-), and lowercased the names. Names between quotation marks or parenthesis were also removed because they were usually used for nicknames. We substituted '-' with spacing. Motivated by [Treeratpituk and Giles, 2012], we added special tokens such as '$' and '+' around the first (middle) names and the last name (e.g. $anton$ +rom+). This resulted in the following five special characters: spacing ( ), apostrophe ('), dollar sign ($), plus sign (+) and a period (.), all of which we considered meaningful for naming convention. Also, scarce country labels that have less than 5 personal names were removed from the cleaned dataset.

For the fair comparisons between models, we made a country ethnicity mapping table for the ethnicity classification task. Since there exist various ethnicities in a country, the majority ethnicity (more than 50%) of a country was considered to be the ethnicity of that country. This gave us total 44 countries to complete ethnicity mappings. For cleaned data, we added additional ethnicity 'African' which was not in the previous ethnicity taxonomy. Though the dataset became smaller, the size of the data was large enough to prove the model's capability.

5 Evaluation

Evaluations are completed on 2 main tasks; Name nationality classification and Name ethnicity classification. Top 1 and top 5 accuracy were used as performance metric. Baseline models and our LSTM based model used for the evaluations are as follows:

• Multinomial Logistic Regression (LR): model suggested by [Treeratpituk and Giles, 2012]
• Random Forest (RF): Random forest model with same feature as LR
• Long Short TermMemory (LSTM): our proposed model

5.1 Model Parameters and Features

Finding the optimal hyper parameters is one of the most important tasks for optimizing neural networks. Using LSTM model, we performed parameter validation on 5 different hyper parameters as described in Table 4. Best performing parameter set on validation phase was used for the LSTM model.

We used Adam optimizer [Kingma and Ba, 2014] for the LSTMmodel and learning rate decay was set to 0.99 for every 100 iterations. Additionally, mini batch of size 1000 was used. Norms of gradients were clipped at 5. Implementations of RF is based on Sklearn library, and for LR and LSTM, we used Tensorflow 4 .

Features for the Logistic Regression and Random Forest were constructed in the same way as [Treeratpituk and Giles, 2012]; nonASCII, character n-gram, Double Metaphone (dmp) n-gram, and Soundex. For character and dmp ngrams, we used bigram, trigram, and four-gram as proposed in [Treeratpituk and Giles, 2012]. Resulting dimension of feature vector is over 66,000 in raw dataset. Note that for our LSTMmodel, we only utilized character level n-grams (unigram, bigram, and trigram), which are very basic features of personal names. Also, we leveraged unigram features, which were not considered in previous studies for name classification.

5.2 Name Nationality Classification

Results of name nationality classification is in Table 5. We can see that external features of LR and RF have reasonable performances. On both raw and cleaned datasets, LSTM model outperforms RF and LR models with significant margins. Considering the fact that feature based approaches utilized external features such as soundex and double metaphone features, the results are very promising. On cleaned dataset, the LR model's performance improves a lot but accuracy of the LSTM model is still better than LR. We argue that well tuned LSTM models without any external features can effectively predict nationalities of personal names.

To further investigate the effect of each components in our LSTM model, performances of ablated LSTM models on cleaned dataset are reported in Table 6. We constructed one-hot unigram (LSTM+uni), bigram (LSTM+bi), and trigram (LSTM+tri) based LSTM model. Embedded versions for each n-gram are marked with (embed). Despite the lack of other n-gram features, the performances of ablated models are considerably high compared to the Random Forest model. We can see that bigram and trigram embeddings have significantly boosted the performance. Unigram embeddings, which were not considered in feature based approaches, also shows its effectiveness when used alone.

4 http://www.tensorflow.org

5.3 Name Ethnicity Classification

Results of ethnicity classification is in Table 7. Using the ethnicity mapping table, most of the models accurately identify the ethnicity of each name. The performance of Logistic Regression is similar to that of [Treeratpituk and Giles, 2012] (85%), suggesting that the mapping was reasonable.

Among all the models, LSTM model performed similarly to the LR model. Though LR model's performances have slightly higher top 1 accuracies in cleaned dataset, LSTM showed better top 5 accuracies once again. It seems that the LSTM model captures broader concepts of naming conventions. In our detailed analysis, KOR and JAP ethnicities were the easiest to discriminate on both LR and LSTM models.

6 Qualitative Analysis

By inspecting incorrect predictions of our model, we present qualitative analysis of the models. In Table 8, we give lists of the top 5 predictors for incorrect predictions.

From the Table, we can see that the incorrect answers of LSTM are also reasonable. When predicting nationality of "$yoanka$ +gonzalez+", both LR and LSTM correctly predict "Cuba". Though RF model identified the correct answers in the top 5, the listed countries seemed rather unrelated (Japan, Germany). On the other hand, LSTMmodel suggests Spanish using countries such as Mexico or Urguay. "$oscar$ +brayson+" is a Cuban name which has Spanish naming custom, although it has quite globally common first name "Oscar". Our model captures the features of both "Oscar" and "Brayson", and suggests proper nationalities. When predicting the nationality of "$georg$ +tallberg+", RF and LR focused on German custom "-berg", but failed to suggest Finland. Based on the fact that "Georg" is a common northern European name, LSTM model successfully suggests Finland, as well.

To analyze how our LSTM based models automatically extracted features from characters, we plotted each character embedding into lower dimensional space using T-SNE

[Maaten and Hinton, 2008] in Figure 2 and 3. In unigram embeddings, we can clearly see that the model separates vowels, consonants, European characters, and special characters. For instance, the nearest neighbors of 'a' are 'e', 'i', 'o', 'u'. Special characters that mark the boundaries ('$' and '+') were also mapped closely. In bigram embeddings, we plotted vowel+vowel (VV, yellow), vowel+consonant (VC, red), consonant+vowel (CV, light pink), consonant+consonant (CC, pink), and others (XX, blue). Bigram embeddings are plotted more complex than unigram embeddings, but the characters tend to make clusters based on their combinations of vowels and consonants. The nearest neighbors of 'bo' are 'to', 'ko', and 'go' in bigram embeddings. As a result, we can see that n-gram embeddings have succeeded in automatically extracting character level features for name classification tasks.

7 Conclusion

Predicting nationality based solely on personal names has been poorly studied due to its difficulties finding subtle structures between naming conventions. We propose a recurrent neural network based model, which predicts nationality of each personal name with high accuracy. Utilizing Skip-gram based embeddings, we show that n-gram embeddings significantly improve the performance our models.

For future work, we can produce various n-gram embeddings utilizing only unigram embeddings. Also, hierarchical recurrent neural networks can be applied to extract higher and more complex representation of personal names.

Acknowledgement

This work was supported by the National Research Foundation of Korea (NRF) grant funded by the government of Korea (MSIP) (NRF-2014R1A2A1A10051238).