METHODS AND SYSTEMS OF VENUE INFERENCE FOR SOCIAL MESSAGES

• US 20160275401A1
• Filed: 03/20/2015
• Published: 09/22/2016
• Est. Priority Date: 03/20/2015
• Status: Active Grant

• Current Assignee: Fujifilm Business Innovation Corp. (Fujifilm Holdings Corporation)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Inventors: CAO, BOKAI, JOSHI, DHJRAJ, CHEN, FRANCINE
• Granted Patent: US 10,395,179 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: H04L 51/52 for supporting social networking services

Abstract

A method for inferring venues from social messages includes: accessing a collection of venues and training a classifier that predicts whether a social message is linked to a venue in the collection of venues; receiving a new social message; for each venue in the collection of venues: identifying for the new social message corresponding meta-paths to the particular venue; encoding the corresponding meta-paths as a feature vector for the trained classifier; computing by the trained classifier a score for each venue in the collection of venues indicating whether the new social message is linked to the venue; and based on the scores, identifying at least one candidate venue as a predicted venue for the new social message and associating the predicted venue with the new social message. In some implementations, the new social message is not geotagged.

Claims

1. A method for inferring venues from social messages, comprising:

at a computer system with one or more processors and memory storing instructions for execution by the processor;

accessing a collection of venues and training a classifier that predicts whether or not a social message is linked to a venue in the collection of venues;

receiving a new social message;

for each venue in the collection of venues;

identifying for the new social message corresponding meta-paths to the particular venue;

encoding the corresponding meta-paths as a feature vector for the trained classifier, wherein each element of the feature vector includes a measure based on a respective type of social message connected to the particular venue;

computing by the trained classifier a score for each venue in the collection of venues indicating whether the new social message is linked or not linked to the venue; and

based on the scores, identifying at least one candidate venue as a predicted venue for the new social message and associating the predicted venue with the new social message.

2. The method of claim 1, wherein training a classifier that predicts whether or not a social message is linked to a venue in the collection of venues includes:

accessing a set of training social messages;

obtaining a plurality of social message and venue pairs, wherein each social message and venue pair in the plurality of social message and venue pairs has a training social message from the set of training social messages and a venue from the collection of venues;

for a pair in the plurality of social message and venue pairs;

encoding the respective training social message in the pair as a label, wherein the label indicates whether the training message is linked or not linked to the venue;

identifying for the respective training social message corresponding training meta-paths to the respective venue in the pair;

encoding the corresponding training meta-paths to a corresponding training feature vector, wherein each element of the corresponding training feature vector includes a measure based on a respective type of the respective training social message connected to the respective venue in the pair; and

giving the encoded labels and training feature vectors to the classifier for training.

3. The method of claim 1, wherein identifying for the new social message corresponding meta-paths to the particular venue includes:

obtaining a social graph as a social network schema based on types of entities and relationships extracted from a collection of messages and the collection of venues, wherein each type of entities is represented as a type of node in the social network schema and the relationships between the entities are represented as different types of links; and

based on the social graph, content of the new social message and/or a user writing the new social message and/or social friends of the user, identifying for the new social message corresponding meta-paths connecting the new social message to the particular venue, wherein each of the corresponding meta-paths represents a type of path within the social network, containing a certain sequence of link types.

4. The method of claim 1, wherein the meta-paths include one or more of:

EGOPATH that directly relates a user'"'"'s social messages to venues, FRIENDPATH that relates a user'"'"'s social messages to venues through their friends, INTERESTPATH that expands the relationship between social messages and venues through venue categories, and TEXTPATH that models the content in social messages about venues.

5. The method of claim 1, wherein the measure includes a frequency of a respective type of social messages connected to the particular venue, and encoding the corresponding meta-paths as a feature vector for the trained classifier includes:

obtaining path counts for each of the corresponding meta-paths representing the frequency of the respective type of social messages connected to the particular venue; and

setting the path counts as the measure in each element of the feature vector.

6. The method of claim 5, further comprising:

combining the path counts for different meta-paths to create an overall feature matrix.

7. The method of claim 1, wherein the measure is an egogeo score for a tweet t_i being posted by user u_i at venue v_p that measures a closest distance between geotagged social messages of a user who posted a non-geotagged message and the respective venue.

8. The method of claim 1, wherein the measure is an egogeo score calculated by EGOGEO(t_i,v_p)=−

log(min<sub>tjε

Ti-ti</sub>∥

t_j−

v_p∥

₁+ε

), T_i denotes the set of geotagged social messages posted by d(.,.) denotes the distance between a geotagged social message and a venue, and c is added to avoid underflow with default value 10<sup>−

9</sup>.

9. The method of claim 1, wherein the measure is a friendgeo score that measures a closest distance between geotagged social messages of friends of a user who posted the new social message and the respective venue.

10. The method of claim 1, wherein the measure is a friendgeo score calculated by FRIENDGEO(t_i,v_p)=−

log(min<sub>tjε

Tk,ukε

Ni</sub>,∥

t_j−

v_p∥

₁+ε

).

11. The method of claim 1, wherein the classifier is a support vector machine (SVM) with a linear kernel and default parameters, and probability estimates are enabled as the classifier output.

12. The method of claim 1, wherein based on the scores, identifying at least one candidate venue as a predicted venue includes:

identifying at least one candidate venue with a highest score represented as a probability as the predicted venue.

13. The method of claim 1, wherein the collection of venues is selected based on at least one of a predefined region, a type of venue, a venue name, a preference by a user, a history of venue inference, or a distance from a geo-coordinate associated with a social message.

14. The method of claim 1, wherein the new social message is not geotagged.

15. A first device, comprising:

memory;

one or more processors; and

one or more programs stored in the memory and configured for execution by the one or more processors, the one or more programs including instructions for;

accessing a collection of venues and training a classifier that predicts whether or not a social message is linked to a venue in the collection of venues;

receiving a new social message;

for each venue in the collection of venues;

identifying for the new social message corresponding meta-paths to the particular venue;

encoding the corresponding meta-paths as a feature vector for the trained classifier, wherein each element of the feature vector includes a measure based on a respective type of social message connected to the particular venue;

computing by the trained classifier a score for each venue in the collection of venues indicating whether the new social message is linked or not linked to the venue; and

based on the scores, identifying at least one candidate venue as a predicted venue for the new social message and associating the predicted venue with the new social message.

16. The device of claim 15, wherein training a classifier that predicts whether or not a social message is linked to a venue in the collection of venues includes:

accessing a set of training social messages;

obtaining a plurality of social message and venue pairs, wherein each social message and venue pair in the plurality of social message and venue pairs has a training social message from the set of training social messages and a venue from the collection of venues;

for a pair in the plurality of social message and venue pairs;

encoding the respective training social message in the pair as a label, wherein the label indicates whether the training message is linked or not linked to the venue;

identifying for the respective training social message corresponding training meta-paths to the respective venue in the pair;

encoding the corresponding training meta-paths to a corresponding training feature vector, wherein each element of the corresponding training feature vector includes a measure based on a respective type of the respective training social message connected to the respective venue in the pair; and

giving the encoded labels and training feature vectors to the classifier for training.

17. The device of claim 15, wherein identifying for the new social message corresponding meta-paths to the particular venue includes:

obtaining a social graph as a social network schema based on types of entities and relationships extracted from a collection of messages and the collection of venues, wherein each type of entities is represented as a type of node in the social network schema and the relationships between the entities are represented as different types of links; and

based on the social graph, content of the new social message and/or a user writing the new social message and/or social friends of the user, identifying for the new social message corresponding meta-paths connecting the new social message to the particular venue, wherein each of the corresponding meta-paths represents a type of path within the social network, containing a certain sequence of link types.

18. The device of claim 15, wherein the meta-paths include one or more of:

EGOPATH that directly relates a user'"'"'s social messages to venues, FRIENDPATH that relates a user'"'"'s social messages to venues through their friends, INTERESTPATH that expands the relationship between social messages and venues through venue categories, and TEXTPATH that models the content in social messages about venues.

19. The device of claim 15, wherein the new social message is not geotagged.

20. A non-transitory computer readable storage medium storing one or more programs to be executed by a computer system with memory and one or more processors, the one or more programs comprising:

instructions for accessing a collection of venues and training a classifier that predicts whether or not a social message is linked to a venue in the collection of venues;

instructions for receiving a new social message that is not geotagged;

for each venue in the collection of venues;

instructions for identifying for the new social message corresponding meta-paths to the particular venue;

instructions for encoding the corresponding meta-paths as a feature vector for the trained classifier, wherein each element of the feature vector includes a measure based on a respective type of social message connected to the particular venue;

instructions for computing by the trained classifier a score for each venue in the collection of venues indicating whether the new social message is linked or not linked to the venue; and

based on the scores, instructions for identifying at least one candidate venue as a predicted venue for the new social message and associating the predicted venue with the new social message.