Learning Geographical Hierarchy Features for Social Image Location Prediction

1 Introduction

With the rising popularity of GPS-equipped mobile terminals, the amount of geo-tagged social images is increasing rapidly. Image location is an important type of information that could support many applications. First, it allows users in searching and organizing images more effectively. Second, by analyzing the correlation between geolocation and image content, we can discover the geographical knowledge about the popularity of image content patterns. For example, images about NYC might cover entirely different events compared to those about Beijing, and the choices of tags and visual features are different for the two cities. In addition, there are also largescale and ever-growing images that are not tagged with GPS records. Hence, it is becoming increasingly important for an effective image location prediction algorithm, i.e., predicting where an image is taken [Serdyukov et al., 2009].

⇤The majority of this work was done while the author was affiliated with Computer Science and Engineering at Arizona State University

Some approaches have been proposed for image location prediction [Hays and Efros, 2008; Hauff and Houben, 2012]. These approaches can be roughly categorized into three classes. In the first category, user-generated text tags are used as a basis for location predication [Kling et al., 2014; Laere et al., 2011; Serdyukov et al., 2009; Yin et al., 2011]. Those approaches use a pure language model to identify the relation between text content and location. Since there are many noisy tags and different locations have their own characteristics of vision pattern, combining visual content could contribute to the performance of the proposed methods. Moreover, there are a large percentage of images that are not associated with any tags, and they cannot be geolocated with these text-based approaches. The second class is vision-based methods which estimate the location of query image based on the locations of visually similar images [Hays and Efros, 2008; Li et al., 2013; Li et al., 2009]. Due to the variety of visual content and the "semantic gap" [Smeulders et al.,2000; Zhang et al., 2012], exploiting visual content is challenging. The third class of approaches combines different types of image contents, i.e., text tags and visual content, for landmark prediction [Crandall et al., 2009]. However, the linear combination strategy of these approaches cannot be directly applied to social image since the text space and visual space have inherently different structures.

Meanwhile, the distribution of image content across geographical locations presents unique characteristics. First, some patterns of image content are popular in a large-scale region, while the sub-regions also have their location specific characteristics. It has been reported that these preferences correlate hierarchically [Wu and David, 2002]. For example, it is likely that images taken in Philadelphia and Camden are more similar than those in Chicago. Second, social images are far from uniformly distributed over the globe. The widely used single-level assumption by existing approaches is affected by the problem of unbalanced sampling on geographical regions. For example, there might be many geotagged images about the famous location Los Angeles but less geo-tagged images for the adjacent location Riverside. Given a query image from Riverside, it may be located to other densely photographed locations by the single-level method due to the little training images for Riverside. However, when using the hierarchal structure, it may first locate the query image to the super region that covers both Los Angeles and Riverside, which increases the chance to estimate a more accurate location. This is because that images within the same super-region may share some features and can help to represent the location Riverside better other than the little training samples of region Riverside itself. Therefore, these characteristics motivate us to arrange image content and location preferences in a hierarchical structure and learn geographical hierarchy features which capture the hierarchical correlation for location prediction.

To learn the hierarchical features, it is quite challenging due to the following reasons. First, social images contain different modalities of content, i.e., text tags and visual content. These contents are presented in different feature space. It needs a joint representation that correlates both modalities and is thus ideal surrogate for learning the hierarchical features. Second, to capture the hierarchical structure, the highlevel features should be able to express the distinctive perceptual structure of a specific region. That is, a hierarchy of super regions for sharing abstract knowledge among adjacent regions should be learned. Third, the hierarchical structure is implicit and not pre-defined.

To tackle the challenges, we propose to take advantage of the hierarchical correlation between image content patterns and locations for image location prediction. In particular, we investigate: (1) how to learn a joint representation which correlates visual content and text content; (2) how to automatically learn a hierarchical structure as well as hierarchical features that capture the hierarchical correlation between image content patterns and locations. Our solutions to these questions result in a new architecture for image location prediction. In particular, we propose a geographically hierarchical bi-modal deep belief network model (GH-BDBN) that integrates multi-modal deep models with a non-parametric hierarchical prior model. The bi-modal deep model (BDBN) is used to correlate visual content and text content through the top hidden level, and a geographically hierarchical prior over the top-level features of BDBN is proposed to model the hierarchical correlation between image content patterns and locations. The main contributions are outlined as:

• ÷ We propose a unified model to effectively integrate visual content and text content through their correlation for image location prediction.
• ÷ We propose a compound model GH-BDBN that integrates a deep learning model with a non-parametric hierarchical model, which learns the hierarchical features as well as the hierarchical structure.
• ÷ We empirically evaluate the proposed model on a realworld Flickr dataset and elaborate the effects of each type of content information for location prediction.

2 Problem Statement

In this section, we first introduce the notations used in the paper and then formally define the problem we study.

Notation: In this paper, the hierarchical structure is represented by a tree. We denote by C l i a node assignment of i-th input in the lth level of the tree, where the superscript denotes the level of the variable indicated by the subscript, and other notations are defined similarly. l(i) denotes the level of node i and ⇡(i) denotes its parent. Each geo-tagged image x = ¶xp ↪ xt ↪ lx♦x2I consists of three atoms: xp 2 RD is the visual feature vector for the visual content; xt 2 RM is the text feature vector for the text content; lx is a real-valued 2-D vector containing the latitude and longitude where the image is taken; and I denotes the training dataset.

With the given notations, we formally define the problem of location prediction for social image as follows:

Given a set of geo-tagged social images I in which each image contains text features, visual features, and geo-coordinate, we aim to automatically estimate the geocoordinate le for query image e based on GH-BDBN.

3 Geographically Hierarchical bi-modal DBN

Usually, social images are uploaded with text descriptions such as tags and comments. Both of the visual content and text content relate to the location where the image was taken. Moreover, these types of content are correlated with location in a hierarchical structure. That is, adjacent locations always share some common features, such as language habit and natural scenery, while each location also has its own specific features. To model these information for image location prediction, we propose a geographically hierarchical bi-modal deep belief network model (GH-BDBN) to learn the geographically hierarchical features by incorporating the visual content, text content and geographical information of social images. A graphical representation of GH-BDBN is shown in Figure 1. The bi-modal deep model is used to correlated visual content xp and text content xt through the top hidden level h(v) which is in turn used as the low-level features of the geographically hierarchical model. Then, we place a geographically hierarchical prior over the h(v) , which obtains both a layered hierarchy of increasingly abstract features and a tree-structured hierarchy of geographical regions.

3.1 Joint Representation of Social Image

To combine different types of image content for location prediction, some methods have been proposed using a linear combination strategy [Crandall et al., 2009]. This method cannot be directly applied to the problem that these contents are represented in heterogeneous feature. Therefore, we learn a joint representation that is expected to be a higher-level abstraction representation for both modalities and is thus a ideal surrogate for location prediction.

In particular, we use the bi-modal DBN (BDBN) [Srivastava and Salakhutdinov, 2012] to learn latent features from the raw features of visual content and text content. The deep learning model has been validated as an effective tool for feature learning and can deal with noisy data [Erhan et al., 2014; Chen et al., 2013]. As shown in the bottom of Figure 1, each data modality is modeled with a separate DBN which uses a Gaussian RBM to model the distribution over the input values. The two models are combined by learning a joint level h(u) on top of them. The conditional distribution of h(u) based on the two low levels is:

where δ(x) = 1◁(1 + exp(-x)). The parameters of BDBN can be learned approximately by greedy lay-wise training and using contrastive divergence algorithm [Hinton et al., 2006].

To enable BDBN to express more information and introduce more structured hierarchical priors, we add another level h(v) on the top. The activities of this level units are modeled by a conditional multinomial distribution. Specifically, h(v) consists of M softmax units each of which is 1-of-K encoding and contains a set of K weights. The kth discrete value of the hidden unit is represented by a vector containing 1 at the kth location and zeros elsewhere. The conditional probability of a softmax unit of h(v) is estimated by:

In Eq. (2), all M separate softmax units share the same set of weights, connecting them to binary hidden units at the lower level. This means that M separate copies of softmax units can be viewed as a single multinomial units that are sampled M times from the conditional distribution of Eq. (2) [Srivastava et al., 2013]. It is the same as the bag-of-words representation. The conditional distribution of h(u) k based on softmax units is estimated as following:

where ˆh(v) j = PMm=1 h(v↪m) j denotes the count for the j th discrete value of a hidden unit.

3.2 Geographically Hierarchical Prior

Usually, image content patterns and locations are hierarchically correlated, and locations are not uniformly photographed. Therefore, the single-level models [Kling et al., 2014; Li et al., 2013; Crandall et al., 2009] are not directly adaptable to this problem. It is reasonable to arrange image content patterns and location preferences in a tree structure, and thus the sparsely photographed regions can share the prior knowledge learned from the super region. Also, the joint representation is variety for different images and thus is unsuitable to model the more abstract knowledge of the larger scale regions. Therefore, we employ a geographically hierarchical prior over h(v) which is used as the low-level features that provide a useful initial representation for all image content patterns. Then, the high-level features are learned to express the distinctive perceptual structure of a specific region, which is in terms of region-specific correlations over low-level features.

Specifically, we propose a geographically hierarchical topic model of prior over the activities of h(v) . The multinomial unit h(v) is referred as document, and the M samples of h(v) represent M "words" of the document. Locations are automatically clustered into hierarchical regions, and each region has its own distribution over topics that are modeled as mulinomial distribution over words [Blei et al., 2003] and are referred as our learned higher level features. A joint generative process is used to model the generation of image location and "words" as follows: for each image, a region is first chose, and then, its "words" and geographical location are generated from their corresponding distributions in this region.

Generation of Tree Structure

For simplicity, we present our hierarchical model with a three-level tree as shown in Figure 2. Each node denotes a region, and the parent region is a sum of the children regions.

Hierarchical regions: We use a hierarchical multivariate Gaussian model to capture the hierarchical structure of geographical locations. Each region r has a region-dependent multivariate normal distribution of location. To accomplish conjugacy of the joint prior distribution of the mean and the covariance to the likelihood, the distribution of the mean has to depend on the covariance. The prior distribution of the mean θr is Gaussian conditioned on ⌃r: θr ⇠ N(⇠r↪ ⇢-1 0 ⌃r). The prior distribution of ⌃r is inverseWishart: ⌃r ⇠ IW(v0↪Hr). The joint distribution of θr and ⌃r is the Normal/inverse-Wishart distribution:

where ⇢0, and v0 are hyperparameters, ⇠r and Hr are levelspecific parameters: ⇠r = θ⇡(r), Hr = ↵⌃⇡(r)(0 < ↵ < 1). Latent topic φ: The number of topics φ is assumed to

be finite (it can be alleviated that the number is infinite).

Each topic is a multinomial distribution on word vocabulary, and is drawn from a Dirichlet distribution over words: φi ⇠ Dir(⌘).

Region-specific distribution of topics ✓: The distribution over latent topics of each node is also modeled hierarchically. It is reasonable that geographical proximity is a good prior for similarity in region-specific distribution of topics. The Hierarchical Dirichlet Process (HDP) [Teh et al. 2006] is used to model this hierarchical distribution. First, we draw the global-level ✓(0) for the global region R(0) : ✓(0) ⇠ Dir(β). At the lower level node r, ✓r is drawn using the parent ✓⇡(r) as a prior: ✓r ⇠ Dir("✓⇡(r)). In this way, the sparsely sampled regions can share the prior knowledge of the larger-scale region. Similarly, the topic distribution ✓d i of each document i is drawn using ✓⇡(i) of the node which generates the document as a prior.

Prior of the tree structure

Since the tree structure is not pre-defined, we need to automatically infer the distribution over the possible hierarchical structures. We place a nested Chinese restaurant prior (nCRP) [Blei et al., 2010] over the path of node selection in the tree. The main building block of the nCRP is the Chinese restaurant process (CRP). To select a node, we define a CRP process over the children of a parent node i:

where nj is the number of previous observations selecting child node j, λ is the concentration parameter, and C l(i)+1 n = j denotes that the nth observation selects child node j. nCRP extends CRP to a nested sequence of partition, one for each level of the tree. This model allows for a nonparametric prior learns an arbitrary tree taxonomy.

3.3 Parameter Inference

We use Markov Chain Monte Carlo to infer parameters at all levels. When the tree structure C is unknown, the inference process alternates between fixing C while sampling the space of model parameters, and vice verse.

Sampling HDP parameters: Given the node assignments C and the states of h(v) , we use the posterior representation sampler to sample [Teh and Jordan, 2010]. That is, the HDP sampler maintains θ and ⌃ of each level, topic distribution of each level and document, i.e., ✓(0) , ✓(0) , ✓(1) , ✓(2) , ✓d , and topic indicator variables t of words. The sampler alternates between: 1) sampling topic indicator tni for each word using Gibbs updating in the Chinese restaurant franchise (CRF) representation of HDP; 2) updating ✓, θ and ⌃ at all levels conditioned on t and C with the usual posterior of a DP (Dirichlet Process). We use the MAP estimating method to update θ and ⌃ for each node r:

where lr denotes the average value of geographical coordinates in node r, and d is the dimensionality of geographical record. The posteriors over leaf node are independent, and the inference can be speeded up by sampling in parallel.

Sampling node assignments C: Given the current instantiation of ✓, θ, ⌃, for each input n we have:

where T is the number of topics. Combining the above likelihood terms with the CRP prior Eq. (5), the posterior over the node assignment is estimated as follows:

where C-n denotes variables C for all observations other than n. When computing the probability of placing ✓dn and ln under a new node, its parameters are sampled from the prior.

Sampling hidden unit h(v) : Given the states of h(v) n , conditional samples from P(h(pl) n ↪ h(tl) n ↪ ▷▷▷↪ h(u) n ♣h(v) n ↪ vn) can be obtained by running a Gibbs sampler that alternates between sampling the states of units in one level independently given the unit in the adjacent level. Conditioned on topic assignments tni and h(u) n , the states of h(v) n for each input n are sampled using Gibbs condition:

where the first term is estimated by the product of logistic functions of Eq. (3) as following:

The second term of Eq.(12) is estimated by the multinomial, i.e., Multi(φtni ). Since it has a conjugate prior of Dirichlet, the parameter φ can be integrated out.

Fine-tuning bi-modal DBN: Given the states of the top level h(v) , the bi-modal DBN parameters in the low levels are fine-tuned in the same way as in contrastive divergence algorithm. Fine-tuning low-level BDBN features can improve the model by encoding the geographical information in the learning of joint representation, and thus the learned representation is more effective to reflect the geographical information.

4 Location Prediction

Based on the results of posterior inference, it is straightforward to predict the node assignment of a query image e. That is, we first infer the posterior over h(v) e on the bi-modal DBN, and then we run the Gibbs sampler to get approximate samples from posterior over the node assignments. For calculation efficiency, we approximate the document-specific topic distribution by the leaf node-specific distribution ✓(2) Ce . Then the posterior probability of a node assignment is:

where the topic assignments of words can be integrated out. By combining the nCRP prior, this likelihood can be used to approximately infer the posterior over node assignment. Then, we select top-m images that are most similar to the query image from the images located in the assigned node. The similarity between two images is estimated based on the JSD (Jensen-Shannon-Divergence) between their probability distributions over latent topics. Finally, the location of the query image e is estimated as following:

where Nm(e) denotes the m most similar images.

5 Experiments

In this section, we conduct experiments to assess the effectiveness of GH-BDBN. Through the experiments, we aim to answer:

1. What are the effects of content type and hierarchy prior on image location prediction?
2. How effective is the proposed model compared with other methods of image location prediction?

We begin by introducing the experiment settings and then analyze the experimental results.

5.1 Experiment Settings

We use the dataset MediaEval2012 [Rae and Kelm, 2012] which is a community-driven benchmark and is run by the MediaEval organizing committee to evaluate our model. Since MediaEval2012 doesn't includes the raw images and some images were removed after the dataset was collected, we download 1,020,130 raw images with their tag lists using the links in the metadata from Flickr. We concatenated 1024D HOG features, 144-D color correlogram in HSV color space, and 128-D wavelet texture to set a 1296-D representation for image's visual content. Each dimension was meancentered. As the raw tags are sparse and noisy, we include a new presentation for text content. First, we remove the stop words and words that appear in more than 10% of the images. Word2Vec [Mikolov et al., 2013] is used to represent each tag with a 500-D vector, which is trained on Wikipedia articles of about 100 million words. Then, all the image tag lists are clustered into 2000 groups based on the geographical information using GMM algorithm, and a 2000-D geographical dictionary is obtained. Finally, each tag is represented by a 2000-D sparse codes learned from the geographical dictionary, and the tag list of each image is represented by a 2000-D feature by max pooling all the words in the list. For BDBN, there are three levels for the vision-specific DBN, and the numbers of units are 1296, 1000, and 800 respectively. Since text is closer to the learned latent feature level, we use two levels to model the text-specific DBN with the numbers of units being 2000 and 1000 respectively. For hu and hv , we set the numbers of units to be 1500 and 1000 respectively. We split the dataset and use 80% for training and 20% for testing.

There is a parameter involved in the experiments, i.e., m which denotes the number of most similar images in Eq.(15). The effect of the parameter on location prediction will be further discussed in Section 5.2. For quantitative evaluation, we use average distance error (ADE) as the evaluation metric: ADE = PNi=1 (ˆ li↪ li)◁N, where dis(ˆ li↪ li) is the Euclidean distance between the estimated location and the true location.

We compare our approach with three groups of four approaches that are effective for location prediction based on different types of image content. The first group of approach is the text-based LMSS (language model and similarity search) [Laere et al., 2011]. It uses the text model to first locate the region and then precisely determine the location in this region based on text similarity measuring. The second group of approaches are vision-based IM2GPS [Hays and Efros, 2008] and GVR [Li et al., 2013]. They estimate the location of query image based on the locations of visual neighbors. The third group of approach is Mapping [Crandall et al., 2009] which combines both visual feature and text content to classify the query image into a region. We revise it to estimate a more precise location based on the locations of neighbor images similar to Eq.(15).

5.2 Effects of Content Type and Hierarchy Prior

In this subsection, we study the importance of image content type and hierarchy prior, which accordingly answers the first question asked in the beginning of Section 5.

First, we evaluate the performance of our model on predicting location by using different types of image content, i.e., only visual content, only tags, and both of visual content and tags, respectively. Figure 3 shows the performance of predicting location using different types of content, with various values of m shown in the X axis and ADE of using different types of image content shown in the Y axis. From the results in Figure 3, we draw several observations. First, the performance is not always proportionate to the number of similar images used in location estimation, and the optimal choice of m is 4. When m is too small, the influence of the falsely selected images increases. When m is too great, the chance of selecting more noisy images increases. Second, location prediction using both of visual content and tags has the best performance, and the text content is more effective in location prediction than visual content. This is because that, usually, text description is more effective in conveying the semantic content of social image than visual features. Since there are many noisy tags and visual content is of large variety in each geographical location, combining both text content and visual content has a better performance than using text content only.

Then, we test whether the hierarchical prior is effective for location prediction. The prediction without hierarchical prior has following steps. First, we cluster the training images based on their geo-coordinates using GMM, and each cluster is labeled as a region. Then, we use the semi-supervised classification model [Liu et al., 2011] to train a classifier on the bi-modal DBN. To predict the location, the query image is classified to a region, and then a precise location is estimated similar to Eq.(15). To evaluate the performance on unbalanced sampling regions, we split the geo-coordinates into grid cells whose sizes are 50km*50km, and density degree is used to define the number of images in a cell. Figure 4 illustrates the performances of GH-BDBN and the deep model without hierarchical prior respectively, with different degrees of image density shown in the X axis. The dashed line denotes the performance of the model without hierarchical prior, and the solid line denotes the performance of GH-BDBN. It can be seen that GH-BDBN performs better at relatively low densities. This is because the low density region can share prior knowledge of the geographical neighbor regions in our model, which decreases the effect of unbalanced sampling. Without the hierarchical prior, the query image located in the low density region will has a great chance to be wrongly classified to other density regions that are far away from the target region. It can also be seen that GH-BDBN outperforms the deep model without hierarchical prior across the board, which demonstrates that exploiting the hierarchical correlation help improve the performance of image location prediction.

5.3 Performance Comparison

To answer the second question asked in the beginning of Section 5. We compare GH-BDBN with the baseline approaches. Figure 5 shows the experimental result with the percentage of training dataset varied from 20% to 100%, by fixing m=4. The results show that all the performances are affected by the volume of training data. This is because when the training dataset is too small, the distributions of images in many locations are very sparse, especially in the locations that are less frequently photographed. The performance of our model is less sensitive to the volume of training data because we can enrich the knowledge of the sparsely photographed region by exploiting the knowledge of the large-scale region with geographically hierarchical prior model. Moreover, our deep learning model is more effective to learn latent feature from few examples. It also shows that our approach outperforms other ones consistently. IM2GPS and GVR predict location mainly based on the similarity between visual feature directly. However, the visually similar images might be semantically far away from each other. The text-based approach LMSS performs better than the vision-based approaches. It uses a pure text model to discover the link between image tags and locations, which ignores the vision patterns of each location. Therefore the performance is also affected. Mapping is better than other three baselines since it exploits both visual feature and textual feature. However, the linear combination strategy is not directly adaptable to the features that belong to different representation spaces. Our approach learns the joint representation to correlate different types of image content, and the geographical hierarchy features are also learned to more effectively capture the hierarchical correlation between image content patterns and location preferences.

6 Conclusion and FutureWork

In this paper, we proposed a compositional learning architecture GH-BDBN that integrates multi-modal deep learning models with non-parametric hierarchical prior models. Experimental results on real-world dataset demonstrate the effectiveness of GH-BDBN. The novelty of this work is to tackle the analysis and application in geo-tagged multi-modal data with latent feature automatically learned from a multimodal deep architecture with nonparametric geography hierarchy prior. This complements the current research which focuses on single-level model for raw data directly and neglects the inherent and hierarchical relation between multimodal data and geolocations.

There are many potential future extensions of this work. It would be interesting to investigate image owner's other social information, like the micro-blogs published in the travel and the interesting points that the owner often visit, for image location prediction.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China (No. 61202239, No. 60973105, and No. 61170189), the Fundamental Research Funds for the Central Universities (No. YWF-14-JSJXY-16), and the Fund of the State Key Laboratory of Software Development Environment (No. SKLSDE-2015ZX-11).