Mining geographic knowledge using a location aware topic model

• US 7,853,596 B2
• Filed: 06/21/2007
• Issued: 12/14/2010
• Est. Priority Date: 06/21/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Chong, Wang, Jinggang, Ma, Wei-Ying, Xie, Xing
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Shanmugasundaram; Kannan
• Application Number:
  US11/766,716
• Publication Number:
  US 20080319974A1
• Time in Patent Office: 1,272 Days
• Field of Search: 707/5
• US Class Current: 707/741
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

Mining geographic knowledge using a location aware topic model is provided. A location system estimates topics and locations associated with documents based on a location aware topic (“LAT”) model. The location system generates the model from a collection of documents that are labeled with their associated locations. The location system generates collection level parameters based on an LDA-style model. To generate the collection level parameters, the location system estimates probabilities of latent topics, locations, and words of the collection. After the model is generated, the location system uses the collection level parameters to estimate probabilities of topics and locations being associated with target documents.

Claims

1. A method in a computing device for identifying a location associated with a first document, the method comprising:

providing a collection of documents of words, each document labeled with an associated location, the collection not including the first document;

generating by the computing device collection level parameters for a latent Dirichlet allocation style model for the collection of documents that is based on latent topics and the location of each document, the collection level parameters indicating a probability that a document in the collection relates to each latent topic, a probability that each word of the collection relates to each latent topic, and a probability that each location of the collection relates to each latent topic, wherein a variational expectation maximization algorithm is used to estimate the collection level parameters that are a maximization of a lower bound on the collection level parameters represented by a summation for each document in the collection of the log of the conditional probability of the document and its location given the collection level parameters;

for each location, estimating, using the collection level parameters, a probability that the location is associated with the first document based on an aggregation of, for each topic, the conditional probability of the location given the topic and the conditional probability of the topic given the document, the conditional probabilities being derived from the collection of documents in which each document is labeled with an associated location; and

selecting the location with the highest probability as the location associated with the first document.

2. The method of claim 1 wherein the estimating of the probability that a location is associated with the first document includes estimating a posterior probability that the first document relates to each topic and that each word of the first document relates to each topic given the first document and the location.

3. The method of claim 2 wherein a variational probabilistic distribution is used to approximate the posterior probability.

4. The method of claim 1 including wherein the first document represents search terms of a query and wherein the probability for each location is estimated and the locations with the highest probability are indicated as locations that may be associated with the query.

5. The method of claim 4 including estimating the probability of each topic and the topics with the highest probability are indicated as topics that may be associated with the query.

6. The method of claim 5 wherein a topic is represented by the words with the highest probabilities to be associated with the topic.

7. A computer-readable storage medium that is not a signal encoded with instructions for controlling a computing device to estimate topics and locations associated with target documents, by a method comprising:

providing a collection of documents of words, each word of a document associated with a location;

generating collection level parameters for a latent Dirichlet allocation style model for the collection of documents based on latent topics and the location of each document, the collection level parameters relating to probabilities of latent topics, locations, and words of the collection, the collection level parameters indicating a probability that a document in the collection relates to each latent topic, a probability that each word of the collection relates to each latent topic, and a probability that each location of the collection relates to each latent topic, wherein a variational expectation maximization algorithm is used to estimate the collection level parameters that are a maximization of a lower bound on the collection level parameters represented by a summation for each document in the collection of the log of the conditional probability of the document and its location given the collection level parameters; and

estimating using the collection level parameters probabilities of topics and locations being associated with each of the target documents; and

for each target document, selecting the location with the highest estimated probability as the location associated with that target document.

8. The computer-readable storage medium of claim 7 wherein the estimating of the probability that a location is associated with a target document includes estimating a posterior probability that a document relates to each topic and that each word of the document relates to each topic given the target document and the location.

9. The computer-readable storage medium of claim 8 wherein a variational probabilistic distribution is used to approximate the posterior probability.

10. The computer-readable storage medium of claim 7 wherein the words of a target document are a query and the locations with the highest estimated probabilities relate to the query.

11. The computer-readable storage medium of claim 7 wherein a target location is provided as a query and wherein the probability of each location being related to that target location is provided by a summation for each topic of the conditional probability of the location given the topic and the conditional probability of the topic given the target location.

12. The computer-readable storage medium of claim 7 wherein a target location and words of a target document are provided as a query and wherein the probability of each location being related to the query is provided by a summation for each topic of the probability of the location given the topic and the probability of the topic given the target location and the target document.

13. A computing device for determining topics and locations associated with a target document, comprising:

a document store having a collection of documents of words, each word of a document associated with a location;

a memory storing computer-implemented instructions of

a component that generates collection level parameters for a latent Dirichlet allocation model for the collection of documents based on latent topics and the location of each document, the collection level parameters relating to probabilities of latent topics, locations, and words of the collection including a probability that each location of the collection relates to each latent topic, the collection level parameters indicating a probability that a document in the collection relates to each latent topic, a probability that each word of the collection relates to each latent topic, and a probability that each location of the collection relates to each latent topic, wherein a variational expectation maximization algorithm is used to estimate the collection level parameters that are a maximization of a lower bound on the collection level parameters represented by a summation for each document in the collection of the log of the conditional probability of the document and its location given the collection level parameters; and

a component that estimates using the collection level parameters probabilities of topics and locations being associated with the target document; and

a component that selects the location with the highest estimated probability for a target document as the location associated with that target document; and

a processor for executing the computer-implemented instructions stored in memory.

14. The computing device of claim 13 wherein each word of a document in the document store is associated with the same document.