MINING GEOGRAPHIC KNOWLEDGE USING A LOCATION AWARE TOPIC MODEL

• US 20080319974A1
• Filed: 06/21/2007
• Published: 12/25/2008
• Est. Priority Date: 06/21/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Xie, Xing, Wang, Chong, Wang, Jinggang
• Granted Patent: US 7,853,596 B2
• Time in Patent Office: Days
• US Class Current: 707/5
• 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 document, the method comprising:

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

generating collection level parameters for a latent Dirichlet allocation style model for the collection of documents that 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; and

estimating, using the collection level parameters, a probability that a location is associated with the 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.

2. The method of claim 1 wherein the probability for each location is estimated and the location with the highest probability is selected as the location associated with the document.

3. The method of claim 1 wherein the collection level parameters are estimated using a variational expectation maximization algorithm.

4. The method of claim 3 wherein the variational expectation maximization algorithm estimates 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.

5. The method of claim 1 wherein the estimating of the probability that a location is associated with a 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 document and the location.

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

7. The method of claim 1 including wherein the 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.

8. The method of claim 7 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.

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

10. A computer-readable medium 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; and

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

11. The computer-readable medium of claim 10 wherein the collection level parameters indicate 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.

12. The computer-readable medium of claim 11 wherein a variational expectation maximization algorithm is used to select 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.

13. The computer-readable medium of claim 10 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.

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

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

16. The computer-readable medium of claim 10 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.

17. The computer-readable medium of claim 10 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.

18. 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 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; and

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

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

20. The computing device of claim 19 wherein the collection level parameters indicate 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.