Density Estimation for Geolocation via Convolutional Mixture Density Network

Introduction

Geographic information related to Twitter enriches the availability of data resources. Such information is indispensable for various practical applications such as early earthquake detection Sakaki et al. (2010), infectious disease dispersion assessment Broniatowski et al. (2013), and regional user behavior assessment during an election period Caldarelli et al. (2014). However the application performance depends strongly on the number of geo-tagged tweets, which account for fewer than 0.5 % of all tweets Cheng et al. (2010).

To extend the possibilities of the geographic information, a great deal of effort has been devoted to specifying the geolocation automatically Han et al. (2014). These studies are classified roughly into two aspects, the User level Cheng et al. (2010); Han et al. (2014); Jurgens et al. (2015); Rahimi et al. (2015) and the Message level Dredze et al. (2016); Liu and Huang (2016); Priedhorsky et al. (2014) prediction. The former predicts the residential area. The latter one predicts the place that the user mentioned. This study targeted the latter problem, with message level prediction, involving the following three levels of difficulty.

First, most tweets lack information to identify the true geolocation. In general, many tweets do not include geolocation identifiable words. Therefore, it is difficult even for humans to identify a geolocation (Figure 1(b)).

Next, some location names involve ambiguity because a word refers to multiple locations. For example, places called “Portland” exist in several locations worldwide. Similarly, this ambiguity also arises within a single country, as shown in Figure 2. Although additional context words are necessary to identify the exact location, many tweets do not include such clue words for identifying the location. As for such tweet, the real-valued point estimation is expected to be degraded by regression towards the mean Stigler (1997).

Finally, if a user states the word that represents the exact location, the user is not necessarily there. In case the user describes several places in the tweet, contextual comprehension of the tweet is needed to identify the true location (Figure 1(c)).

In contrast to most studies, this study was conducted to resolve these issues based on the density estimation approach. A salient benefit of density estimation is to enable comprehension of the uncertainty related to the tweet user location because it propagates from the estimated distribution and handles tweets distributed to multiple points properly. Figure 1 shows each estimated density as a heatmap. The estimated distribution is concentrated near the true location (Figure 1(a)) and vice versa (Figure 1(b)) if the tweet includes plenty of clues. Furthermore, the density-based approach can accommodate the representation of multiple output data, whereas the regression-based approach cannot (Figure 1(c)).

The density-based approach provides additional benefits for practical application. The estimated density appends the estimation reliability for each tweet as the likelihood value. For reliable estimation, the estimated density provides the high likelihood (Figure 1(a) and 1(c)) and vice versa (Figure 1(b)).

To realize this modeling, we propose a Convolutional Mixture Density Network (CMDN), a method for estimating the geolocation density estimation from text data. Actually, CMDN extracts valuable features using a convolutional neural network architecture and converts these features to mixture density parameters. Our experimentally obtained results reveal that not merely the high prediction performance, but also the reliability measure works properly for filtering out uncertain estimations.

Related work

Social media geolocation has been undertaken on various platforms such as Facebook Backstrom et al. (2010), Flickr Serdyukov et al. (2009), and Wikipedia Lieberman and Lin (2009). Especially, Twitter geolocation is the predominant field among all of them because of its availability Han et al. (2014).

Twitter geolocation methods are not confined to text information. Diverse information can facilitate geolocation performance such as meta information (time Dredze et al. (2016) and estimated age and gender Pavalanathan and Eisenstein (2015)), social network structures Jurgens et al. (2015); Rahimi et al. (2015), and user movement Liu and Huang (2016). Many studies, however, have attempted user level geolocation, not the message level. Although the user level geolocation is certainly effective for some applications, message level geolocation supports fine-grained analyses.

However, Priedhorsky et al. (2014) has attempted density estimation for message level geolocation by estimating a word-independent Gaussian Mixture Model and then combining them to derive each tweet density. Although the paper proposed many weight estimation methods, many of them depend strongly on locally distributed words. Our proposed method, CMDN, enables estimate of the geolocation density from the text sequence in the End-to-End manner and considers the marginal context of the tweet via CNN.

Convolutional Neural Network for Regression (Unimodal output)

We start by introducing the convolutional neural network Fukushima (1980); LeCun et al. (1998) (CNN) for a regression problem, which directly estimates the real-valued output as our baseline method. Our regression formulation is almost identical to that of CNN for document classification based on Kim (2014). We merely remove the softmax layer and replace the loss function.

In that equation, $\oplus$ represents vector concatenation.

where $m$ stands for the number of feature maps, and $\phi$ represents the activation function. As described herein, we employ ReLU Nair and Hinton (2010) as the activation function.

For each filter’s output, we apply 1-max pooling to extract the most probable window feature $\hat{c}_{j}$. Then we compose the abstracted feature vectors $\mathbf{h}$ by concatenating each pooled feature $\hat{c}_{j}$ as shown below.

Finally, we estimate the real value output $\mathbf{y}$ using the abstracted feature vector $\mathbf{h}$ as

Convolutional Mixture Density Network (Multimodal output)

In the previous section, we introduced the CNN method for regression problem. This regression formulation is good for addressing well-defined problems. Both the input and output have one-to-one correspondence. Our tweet corpus is fundamentally unfulfilled with this assumption. Therefore, a more flexible model must be used to represent the richer information.

In this section, we propose a novel architecture for text to density estimation, Convolutional Mixture Density Network (CMDN), which is the extension of Mixture Density Network by Bishop (1994). In contrast to the regression approach that directly represents the output values $\hat{\mathbf{y}}$, CMDN can accommodate more complex information as the probability distribution. The CMDN estimates the parameters of Gaussian mixture model $\pi_{k},\bm{\mu}_{k},\bm{\Sigma}_{k}$, where $k$ is the $k$-th mixture component using the same abstracted features $\mathbf{h}$ in the CNN regression (Sec 3).

Presuming that density consists of $K$ components of multivariate normal distribution $\mathcal{N}(\mathbf{y}|\bm{\mu}_{k},\bm{\Sigma}_{k})$, then the number of each $q$-dimensional normal distribution parameters are $p=\frac{q(q+3)}{2}$ ($q$ parameters for each mean $\bm{\mu}_{k}$ and diagonal values of the covariance matrix $\bm{\Sigma}_{k}$ and $\frac{q(q-1)}{2}$ parameters for correlation parameters $\rho$) between dimension outputs.

For $q=2$, each component of the parameters is represented as

To estimate these parameters, we first project the hidden layer $\mathbf{h}$ into the required number of parameters space $\bm{\theta}$ as

Although the parameter $\bm{\theta}$ has a sufficient number of parameters to represent the $K$ mixture model, these parameters are not optimal for insertion to the parameters of the multivariate normal distribution $\mathcal{N}(\mathbf{y}|\bm{\mu}_{k},\bm{\Sigma}_{k})$, and its mixture weight $\pi_{k}$.

The mixture weights $\pi_{k}$ must be positive values and must sum to 1. The variance parameters $\sigma$ must be a positive real value. The correlation parameter $\rho_{k}$ must be $(-1,1)$. For this purpose, we transform real-valued outputs $\bm{\theta}$ into the optimal range for each parameter of mixture density.

2 Parameter conversion

For simplicity, we first decompose $\bm{\theta}$ to each mixture parameter $\bm{\theta}_{k}$ as

To restrict each parameter range, we convert each vanilla parameter $\bm{\theta}_{k}$ as

The original MDN paper Bishop (1994) and its well known application of MDN for handwriting generation Graves (2013) used an exponential function for transforming variance parameter $\sigma$ and a hyperbolic tangent function for the correlation parameter $\rho$. However, we use softplus Glorot et al. (2011) for variance and softsign Glorot and Bengio (2010) for correlation.

Replacing the activation function in the output layer prevents these gradient problems. Actually, these gradient values are often exploded or nonexistent. Our proposed transformation is effective to achieve rapid convergence and stable learning.

3 Loss function for parameter estimation

To optimize the mixture density model, we use negative log likelihood as the training loss:

Experiments

In this section, we formalize our problem setting and clarify our proposed model effectiveness.

This study explores CMDN performance from two perspectives.

Our first experiment is to predict the geographic coordinates by which each user stated using the only single tweet content. We evaluate the mean and median value of distances measured using Vincenty’s formula Vincenty (1975) between the estimated and true geographic coordinates for the overall dataset.

The second experiment is used to filter out the unreliable estimation quantitatively using the likelihood-based threshold. Each estimated density assigns the likelihood value for every point of the location. We designate the likelihood values as reliability indicators for the respective estimated locations. Then, we remove the estimation from the lowest likelihood value and calculate both the mean and median values. This indicator is filtered correctly out the unreliable estimations if the statistics decrease monotonically.

In contrast to the regression approach, it is necessary to specify the estimation point from the estimated density of each tweet. In accordance with Bishop (1994), we employ the mode value of estimated density as the estimated location $\hat{\mathbf{y}}$. The mode value of the probability distribution can be found by numerical optimization, but it requires overly high costs for scalable estimation. For a simple and scalable approximation for seeking the mode value of the estimated density, we restrict the search space to each mean value of the mixture components as shown below:

2 Dataset

Our tweet corpus consists of 24,633,478 Japanese tweets posted from July 14, 2011 to July 31, 2012. Our corpus statistics are presented in Table 1. We split our corpus randomly into training for 20M tweets, development for 2M, and test for 2M.

3 Comparative models

We compare our proposed model effectiveness by controlling experiment procedures, which replace the model components one-by-one. We also provide simple baseline performance. The following model configurations are presented in Table 2.

Mean: Mean value of the training data locations.

Median: Median value of the training data locations.

MDN: Mode value of Mixture Density Network Bishop (1994)

CMDN: Mode value of Convolutional Mixture Density Network (Proposed)

4 Results

The experimental geolocation performance results are presented in Table 3.

Overall results show that our proposed model CMDN provides the lowest median error distance: CNN-l1 is the lowest mean error distance. Also, CMDN gives similar mean error distances to those of CNN-l1. Both CMDN and CNN-l1 outperform all others in comparative models.

In addition to the results obtained for the feature extraction part, the CNN-based model consistently achieved better prediction performance than the vanilla MLP-based model measured by both the mean and median.

4.2 Likelihood based threshold

We show how the likelihood-based threshold affects both mean and median statistics in Figure 3. The likelihood-based threshold consistently decreases both statistics in proportion to the likelihood lower bound increases. Especially, these statistics dramatically decrease when the likelihood is between $10^{1}$ and $10^{2}$. Several likelihood bounds results are presented in Figure 4. Although the model mistakenly estimates many incorrect predictions for the overall dataset (blue), the likelihood base threshold correctly prunes the outlier estimations.

Discussion

Our proposed model provides high accuracy for our experimental data. Moreover, likelihood-based thresholds reveal a consistent indicator of estimation certainty. In this section, we further explore the properties of the CMDN from the viewpoint of difference of the loss function.

An important shortcoming of aggressive prediction is that the estimation deteriorates when the estimation fails. The mean value tends to be affected strongly by the outlier estimation. Therefore, CMDN’s mean value becomes higher than that of CNN-l1’s.

Future work

This study assessed the performance of our proposed model, CMDN, using text data alone. Although text-only estimation is readily applicable to existing resources, we still have room for improvement of the prediction performance. The winner of the Twitter Geolocation Prediction Shared Task, Miura et al. (2016), proposed that the unified architecture handle several meta-data such as the user location, user description, and time zone for predicting geolocations. The CMDN can integrate this information in the same manner.

Furthermore, Liu and Huang (2016) reports that the user home location strongly affects location prediction for a single tweet. For example, a routine tweet is fundamentally unpredictable using text contents alone, but if the user home location is known, this information is a valuable indication for evaluating the tweet. As future work, we plan to develop a unified architecture that incorporates user movement information using a recurrent neural network.

In contrast, our objective function might be no longer useful for world scale geolocation because ours approximates the spherical coordinates into the real coordinate space. This approximation error tends to become larger for the larger scale geolocation inference. We will explore our method’s geolocation performance using the world scale geolocation dataset such as W-NUT data Han et al. (2016).

Conclusion

This study clarified the capabilities of the density estimation approach to Twitter geolocation. Our proposed model, CMDN, performed not only with high accuracy for our experimental data; it also extracted reliable geolocated tweets using likelihood-based thresholds. Results show that CMDN merely requires the tweet message contents to identify its geolocation, while obviating preparation of meta-information. Consequently, CMDN can contribute to extension of the fields in which geographic information application can be used.

References