RATE: Overcoming Noise and Sparsity of Textual Features in Real-Time Location Estimation

Micro-blogging services such as Twitter, Tumblr and Weibo are regarded as indispensable platforms for information sharing and social networking. In recent years, estimating the location information of social media users has become a popular topic with some important applications. For example, the ability to select a group of users in the specific spatial range can enable analysis on real-time disaster information, localized friendship recommendation or investigations on the geographic variation in habits.

For Twitter users, while tweet text is the most commonly used feature in location inference, most of the prior works suffer from the following two problems of textual features.

In this paper, we propose RATE to overcome noise and sparsity of textual features in ReAl-Time location Estimation.

To tackle the noise problem, we incorporate other information available from the retrieved tweet. Figure 1 shows an example of a tweet with 8 metadata extracted through the Twitter streaming API (Zubiaga et al., 2017). Note that the exact latitude and longitude can be extracted only if users open their GPS service. But few users choose to do so for the concern of privacy. The absence of GPS signals forces us to rely on other information.¹¹1In this paper, we adopt the same scenario as (Zubiaga et al., 2017). We want to solve the location estimation problem for real-time Twitter streams. In this scenario, it becomes infeasible to retrieve follower-followee relationships or to make plenty of queries to an access-limited database. Therefore, we cannot rely on social connections or some third-party information although it is easy to put them in the model from the technical perspective.

In Figure 1, user’s residence, name and description are free-text fields completed during the registration. We can combine tweet text and some free-text fields into a single “document”. We name it as textual features. Besides, we also have several categorical features including time zone, UTC offset, tweet language and user language.

To tackle the sparsity problem, we use Latent Dirichlet Allocation (Blei et al., 2002) as a building block to deal with textual features so that “one-hot” encoding vectors will no longer be directly used as input.

Our generative model assumes that each location has different distributions over topics, words and categorical features. Therefore, we can infer the location through the observable features. Our model can be applied in either region classification or latitude and longitude regression, and experimental results show that RATE outperforms several benchmark methods in both tasks. As a byproduct, it can also be used to discover the real-time hot topics and find lexical variation of different regions.

Among various approaches used in location inference, finding location indication words is the most common one. For example, Cheng et al. (Cheng et al., 2010) propose a local word filtering method. Eisenstein et al. (Eisenstein et al., 2010) incorporate Correlated Topic Models (CTM) (Blei and Lafferty, 2006) to describe the relationships among different local topics. Chen et al. (Chen et al., 2013) further add user’s interests into their topic model.

Another widely used technique relies on social network relationships, so as to infer a user’s location from that of its followers and followees (Sadilek et al., 2012; Jurgens, 2013; Dong et al., 2014). But in our context, a classifier needs to deal with the additional challenge of having to rely only on the information in a single tweet.

Our method is inspired by Zubiaga et al.’s work (Zubiaga et al., 2017). They use tweet metadata to train a Maximum Entropy classifier (i.e., logistic regression). However, they adopt “one-hot” representation and ignore the sparsity of textual features.

We use a Bayesian graphical model RATE to characterize the relationship between tweets, topics and regions. Using plate notation, Figure 2 illustrates the structure of our model.

There are $L$ latent areas. Each area $i$ has $T$ topics $\phi_{i,j}$ (represented by multinomial distributions over the words), $F$ categorical features $f_{u,i}$ (represented by multinomial distributions over the categories) and a region distribution $\tilde{f}_{i}$. As normal practice, we suppose that all multinomial distributions have a Dirichlet prior. We also assume that the latitude and longitude are extracted from a two-dimensional Gaussian distribution governed by the area’s geographical center $\mu_{i}$ and variance $\sigma_{i}^{2}$. Given the area indicator $p$, we use the distributions of $p$ to generate words, categorical features, the region indicator and coordinates of the tweet.

RATE has three major components: the textual feature component, the categorical feature component and the prediction component, which have been marked in Figure 2.

The textual feature component has a similar structure with Latent Dirichlet Allocation (LDA) (Blei et al., 2002). The only difference is that in LDA, the word is selected by a per-token hidden variable $z$, while in RATE, the word is selected jointly by a topic index $z$ and a per-tweet area index $p$.

In the categorical feature component, features such as user language, tweet language and time zone are generated by the multinomial distribution $f_{u,i}$.

The prediction component includes the region indicator $c_{i}$ and the coordinates $y_{i}$ of the tweet. In the training set, they are the features which help us cluster the tweets and infer the latent parameters. And in the testing set, they are no longer observable and are the variables we want to predict.

We conclude our generative story as follows:

As common sense, different regions may have different popular topics. Even for the same topic, there exists a geographic lexical variation (Eisenstein et al., 2010). Different regions may also have distinct distributions of user’s features. For example, French will be the dominating element of the user language distribution in France, while it will not cover a considerable proportion in Germany. Therefore, the observable text and user features of the tweet are strong spatial indicators.

In the M step, we estimate $\mu$ and $\sigma^{2}$ by maximizing the likelihood function, which is defined as the average over all samples drawn from the E step:

By solving the equations $\frac{\partial Q}{\partial\mu_{p}}=0$ and $\frac{\partial Q}{\partial\sigma_{p}}=0$, we acquire an MLE estimation for the center and variance of each region:

and $\sigma_{p}^{2}$ is the positive root of the following biquadratic equation

For a tweet in the test set, we can either make a point estimation on the latitude and longitude or make a region classification.

For latitude and longitude regression, we have

For the classification, we have

In Europe, we select all the tweets from UK/France to form another 2 datasets. After the filtering, we have 77,852 and 36,451 tweets in UK and France respectively.

In all of the 3 datasets, we use 60% of tweets for training, 20% for tuning the parameters, and the remaining 20% for final testing. For the tweet text, we remove URLs and the words that occur less than 10 times in the whole corpus. But we retain mentions (“$@$username”), hashtags (“$\#$topic”) and stop words. After the preprocessing, we have a vocabulary of approximately 30K words.

For each tweet, we combine tweet text and the user’s profile location into a single “document”. It is our textual feature. Besides, we use user language, time zone and tweet language as categorical features.

For the coordinates regression task, we use mean distance error (MDE) as our metric. It is the average error distance (on the sphere) between predicted location and actual location.

(1) Naive Bayes (NB) is a basic classification method using only categorical features.

(2) SVM trains a linear Support Vector Machine with both categorical features and textual features.

(3) LR-Text (Zubiaga et al., 2017) trains a Logistic Regression classifier using only textual features with “one-hot” representation.

(4) LR-Full (Zubiaga et al., 2017) is similar to LR-Text, but it incorporates both categorical features and textual features. According to the original paper, this combination performs the best.

(5) RATE is the method proposed in this paper.²²2The code as well as the dataset is available at
https://github.com/yuzhimanhua/Location-Inference/.

(6) GeoTM is a simplification of RATE, using only textual features. It is also similar with the method in (Eisenstein et al., 2010). The only difference is that Eisenstein et al. use CTM, while we use LDA.

Table 1 shows the location prediction results of the methods mentioned above. As expected, RATE significantly outperforms all the benchmark methods, both in region classification and coordinates regression.

Methods only using textual features, such as GeoTM and LR-Text, perform not so well in country-level classification because categorical features do help a lot in dealing with the noise problem in coarse-grained tasks. However, textual features show their power in fine-grained tasks. We can see that GeoTM performs the second best in UK and France. where categorical features may have less contribution in location estimation. Therefore, if we want to balance the performances of our algorithm in both coarse-grained tasks and fine-grained ones, it will be effective to incorporate both textual features and categorical features into our model. Moreover, we should note that RATE adopts a better way than SVM and LR-Full in dealing with the sparsity of textual features.

Figure 3 shows the MDE of RATE in Europe with different numbers of regions ($L$) and topics ($T$). We can observe that for each fixed $L$, the model always performs the best in the case $T=1$. Therefore we no longer need to sample $\theta$ and $z$, and the structure of $\beta$, $\phi$, $w$, $p$, $\psi$ and $\gamma$ will be identical to the DMM model (Yin and Wang, 2014), which has proved to be effective in dealing with short text like tweets (Yin and Wang, 2014).

The “best” $L$ is 30 in Europe, which approximately equals to the number of countries.

In this paper, we propose a Bayesian graphical model to overcome the noise and sparsity problems in real-time location estimation on Twitter. The key ideas of our model are that: (1) we use the combination of text information and user profile information to tackle the noise problem. (2) we use topic modeling characterizing the geographic lexical variation to tackle the sparsity problem. Quantitative analysis justifies our model on several Twitter datasets by showing that our approach outperforms several benchmark methods. Qualitative analysis shows that our model is also useful in extracting location-relevant topics.