LOCAL METRIC LEARNING FOR TAG RECOMMENDATION IN SOCIAL NETWORKS

• US 20120219191A1
• Filed: 02/28/2011
• Published: 08/30/2012
• Est. Priority Date: 02/28/2011
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Chidlovskii, Boris, Benzarti, Mohamed Aymen, Vijayakumar, Nishant
• Granted Patent: US 9,600,826 B2
• Time in Patent Office: Days
• US Class Current: 382/106
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data
• CPC Class Codes: G06Q 50/01 Social networking
• CPC Class Codes: G06V 20/30 in albums, collections or shared content, e.g. social network photos or video

Abstract

A tag recommendation for an item to be tagged is generated by: selecting a set of candidate neighboring items in an electronic social network based on context of items in the electronic social network respective to an owner of the item to be tagged; selecting a set of nearest neighboring items from the set of candidate neighboring items based on distances of the candidate neighboring items from the item to be tagged as measured by an item comparison metric; and selecting at least one tag recommendation based on tags of the items of the set of nearest neighboring items. The item comparison metric may comprise a Mahalanobis distance metric trained on the set of candidate neighboring items to correlate the trained Mahalanobis distance between pairs of items of the set of candidate neighboring items with an overlap metric indicative of overlap of the tag sets of the two items.

Claims

1. A storage medium storing instructions executable by a processing device to perform a method comprising:

generating at least one tag recommendation for an item to be tagged by;

selecting a set of candidate neighboring items in an electronic social network based on context of items in the electronic social network respective to an owner of the item to be tagged,

selecting a set of nearest neighboring items from the set of candidate neighboring items based on distances of the candidate neighboring items from the item to be tagged as measured by an item comparison metric, and

selecting the at least one tag recommendation based on tags of the items of the set of nearest neighboring items.

2. The storage medium as set forth in claim 1, wherein the selecting of the set of candidate neighboring items is further based on features of the items.

3. The storage medium as set forth in claim 1, wherein the selecting of the set of candidate neighboring items is limited to one of:

items owned by the owner of the item to be tagged,

items owned by the owner of the item to be tagged and items owned by users of the electronic social network who are contacts of the owner of the item to be tagged, and

items owned by the owner of the item to be tagged and items owned by users of the electronic social network having between one and N degrees of separation inclusive from the owner of the item to be tagged where N is an integer greater than or equal to two.

4. The storage medium as set forth in claim 1, wherein the selecting of the set of candidate neighboring items is limited to items owned by the owner of the item to be tagged and items owned by L users of the electronic social network who are the L closest contacts of the owner of the item to be tagged as measured by a user comparison metric.

5. The storage medium as set forth in claim 1, wherein the selecting of the set of nearest neighboring items comprises:

selecting K nearest neighboring items from the set of candidate neighboring items based on distances of the candidate neighboring items from the item to be tagged as measured by the item comparison metric, where K is an integer greater than one.

6. The storage medium as set forth in claim 5, wherein the item comparison metric comprises a Mahalanobis distance metric operating on feature vector representations of items.

7. The storage medium as set forth in claim 1, wherein the item comparison metric comprises a Mahalanobis distance metric operating on feature vector representations of items.

8. The storage medium as set forth in claim 7, wherein the generating further comprises training the Mahalanobis distance metric on the set of candidate neighboring items.

9. The storage medium as set forth in claim 7, wherein the generating further comprises training the Mahalanobis distance metric on the set of candidate neighboring items to minimize an objective function comprising a sum of Mahalanobis distances between feature vectors representing candidate neighboring items with at least one overlapping tag.

10. The storage medium as set forth in claim 7, wherein the generating further comprises training the Mahalanobis distance metric on the set of candidate neighboring items to optimize a correlation between the trained Mahalanobis distance between two items and a metric indicative of tag set overlap between the two items.

11. The storage medium as set forth in claim 1, wherein the item to be tagged comprises an image to be tagged and the selecting of the set of candidate neighboring items comprises selecting a set of candidate neighboring images.

12. A method comprising:

generating at least one tag recommendation for an item to be tagged by;

training a Mahalanobis distance metric on a set of candidate neighboring items in an electronic social network;

selecting a set of nearest neighboring items from the set of candidate neighboring items based on distances of the candidate neighboring items from the item to be tagged as measured by the trained Mahalanobis distance metric, and

selecting the at least one tag recommendation based on tags of the items of the set of nearest neighboring items;

wherein the generating is performed by a digital processing device.

13. The method as set forth in claim 12, wherein the training comprises:

training the Mahalanobis distance metric on the set of candidate neighboring items to minimize an objective function comprising a sum of Mahalanobis distances between candidate neighboring items with at least one overlapping tag.

14. The method as set forth in claim 13, wherein the training optimizes the semi-definite program comprising:

min_AΣ

<sub>(Xi;

Xj)S</sub>d_A(X_i;

X_j)+Σ

<sub>Xi;

XjXk)S</sub>ξ

_ijk s.t. d_A(X_i;

X_k)−

d_A(X_i;

X_j)≧

tov_ij−

ξ

_ijk for all triples (X_i;

X_j;

X_k)S A≧

0, ξ

_ijk≧

0.

where S denotes the set of candidate neighboring items, X_i and X_j are feature vectors representing respective items i and j of the set of candidate neighboring items having at least one common tag, and X_k is a feature vector representing an item k of the set of candidate neighboring items having no tag in common with item i and having no tag in common with item j, and d_A is a Mahalanobis distance metric given by;

d_A(X_i, X_j)=(X_i−

X_j)^TA(Xⁱ−

X_j)

where A is a parameter matrix whose values are optimized by the training.

15. The method as set forth in claim 12, wherein the training comprises:

training a Mahalanobis distance metric on the set of candidate neighboring items to optimize a correlation between (i) the trained Mahalanobis distance between pairs of items of the set of candidate neighboring items and (ii) an overlap metric indicative of overlap of the tag sets of the two items.

16. The method as set forth in claim 15, wherein the training optimizes the semi-definite program comprising:

min_AΣ

<sub>(Xi;

Xj)S</sub>d_A(X_i;

X_j)+Σ

<sub>(Xi;

Xj,Xk)S</sub>ξ

_ijk s.t. d_A(X_i;

X_k)−

d_A(X_i;

X_j)≧

tov_ij−

ξ

_ijk for all triples (X_i;

X_j;

X_k)S A≧

0, ξ

_ijk0.

where S denotes the set of candidate neighboring items, X_i and X_j are feature vectors representing respective items i and j of the set of candidate neighboring items having at least one common tag, and X_k is a feature vector representing an item k of the set of candidate neighboring items having no tag in common with item i and having no tag in common with item j, and d_A is a Mahalanobis distance metric given by;

d_A(X_i, X_j)=(X_i−

X_j)^TA(X_i−

X_j)

where A is a parameter matrix whose values are optimized by the training.

17. The method as set forth in claim 15, wherein the overlap metric comprises a tag set overlap fraction.

18. The method as set forth in claim 15, wherein the overlap metric between the two items i and j of the set of candidate neighboring items is proportional to:

|T_i∩

T_j|/(|T_i|+|T_j|)

where T_i denotes the set of tags associated with the item i and T_i denotes the set of tags associated with the item j.

19. The method as set forth in claim 12, wherein the generating further comprises:

selecting the set of candidate neighboring items from one of;

a set of items limited to items owned by an owner of the item to be tagged,

a set of items limited to items owned by the owner of the item to be tagged and items owned by users of the electronic social network who are contacts of the owner of the item to be tagged, and

a set of items limited to items owned by the owner of the item to be tagged and items owned by users of the electronic social network having between one and N degrees of separation inclusive from the owner of the item to be tagged where N is an integer greater than or equal to two.

20. The method as set forth in claim 12, wherein the selecting of the set of nearest neighboring items comprises:

selecting K nearest neighboring items from the set of candidate neighboring items based on distances of the candidate neighboring items from the item to be tagged as measured by the trained Mahalanobis distance metric, where K is an integer greater than one.

21. The method as set forth in claim 12, further comprising:

displaying the at least one tag recommendation for the item to be tagged.

22. An apparatus comprising:

a digital processing device configured to perform a method including;

training a Mahalanobis distance metric operating on feature vector representations of items on a set of training items, the training optimizing a correlation between (i) the trained Mahalanobis distance between pairs of training items (i, j) selected from the set of training items and (ii) an overlap metric indicative of overlap of sets of tags associated with the respective training items i and j.

23. The apparatus as set forth in claim 22, wherein the training optimizes the semi-definite program comprising:

min_AΣ

<sub>(Xi;

Xj)S</sub>d_A(X_i;

X_j)+Σ

<sub>(Xi;

Xj,Xk)S</sub>ξ

_ijk s.t. d_A(X_i;

X_k)−

d_A(X_i;

X_j)≧

tov_ij−

ξ

_ijk for all triples (X_i;

X_j;

X_k)S A≧

0, ξ

_ijk0.

where S denotes the set of training items, X_i and X_j are feature vectors representing respective training items i and j having at least one common tag, and X_k is a feature vector representing a training item k having no tag in common with training item i and having no tag in common with training item j, and d_A is a Mahalanobis distance metric given by;

d_A(X_i, X_j)=(X_j−

X_j)^TA(X_i−

X_j)

where A is a parameter matrix whose values are optimized by the training.

24. The apparatus as set forth in claim 22, wherein the overlap metric comprises a tag set overlap fraction.

25. The apparatus as set forth in claim 22, wherein the overlap metric is proportional to:

|T_i∩

T_j|/(|T_i|+|T_j|)

where T_i denotes the set of tags associated with the training item i and T_j denotes the set of tags associated with the training item j.

26. The apparatus as set forth in claim 22, wherein the digital processing device is further configured to select K nearest neighboring items from the set of training items based on distances of the training items from a reference item as measured by the trained Mahalanobis distance metric, where K is an integer greater than one.