Local metric learning for tag recommendation in social networks using indexing

• US 9,600,826 B2
• Filed: 02/28/2011
• Issued: 03/21/2017
• Est. Priority Date: 02/28/2011
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Benzarti, Mohamed Aymen, Chidlovskii, Boris, Vijayakumar, Nishant
• Primary Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US13/036,209
• Publication Number:
  US 20120219191A1
• Time in Patent Office: 2,213 Days
• Field of Search: 707/748, 706/12, 706/45
• US Class Current: 1/1
• 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 non-transitory storage medium storing instructions executable by a processing device to perform a tag recommendation method operating in conjunction with an electronic social network including user accounts and tagged items, the user accounts including user-user contacts information and each tagged item being indexed in the electronic social network by an item owner of the tagged item wherein the item owner is a user of the electronic social network, the tag recommendation method comprising:

for an item to be tagged that is indexed in the electronic social network by an item owner of the item to be tagged, generating at least one tag recommendation for the item to be tagged by;

(1) selecting a set of candidate neighboring items in the electronic social network wherein the selecting of the set of candidate neighboring items is limited to one of;

selecting items from the set of items whose item owner is the item owner of the item to be tagged,

selecting items from a set of items consisting of a combination of the set of items whose item owner is the item owner of the item to be tagged and the set of items whose item owners are users of the electronic social network who are contacts in the electronic social network of the item owner of the item to be tagged, and

selecting items from a set of items consisting of a combination of the set of items whose item owner is the item owner of the item to be tagged and the set of items whose item owners are users of the electronic social network having between one and N degrees of separation inclusive from the item owner of the item to be tagged in the user-user contacts information of the electronic social network where N is an integer greater than or equal to two,

(2) selecting a set of nearest neighboring items from the set of candidate neighboring items that are nearest to the item to be tagged as measured by an item comparison metric, and

(3) selecting the at least one tag recommendation from tags of the items of the set of nearest neighboring items; and

displaying, on a display, the at least one tag recommendation for the item to be tagged.

2. The non-transitory 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 that are nearest to the item to be tagged as measured by the item comparison metric, where K is an integer greater than one.

3. The non-transitory storage medium as set forth in claim 2, wherein the item comparison metric comprises a Mahalanobis distance metric operating on feature vector representations of items.

4. The non-transitory 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.

5. The non-transitory storage medium as set forth in claim 4, wherein the generating further comprises training the Mahalanobis distance metric on the set of candidate neighboring items wherein the training comprises optimizing a parameter matrix of the Mahalanobis distance.

6. The non-transitory storage medium as set forth in claim 4, 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 the outputs of the Mahalanobis distance metric operating on feature vector representations of candidate neighboring items with at least one overlapping tag.

7. The non-transitory storage medium as set forth in claim 4, 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.

8. The non-transitory 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.

9. A tag recommendation method operating in conjunction with an electronic social network including user accounts and tagged items, the user accounts including user-user contacts information and each tagged item being indexed in the electronic social network by an item owner of the tagged item wherein the item owner is a user of the electronic social network, the tag recommendation method comprising:

for an item to be tagged that is indexed in the electronic social network by an item owner of the item to be tagged, generating at least one tag recommendation for the item to be tagged by;

training a Mahalanobis distance metric on a set of candidate neighboring items in the electronic social network wherein the training comprises optimizing a parameter matrix of the Mahalanobis distance to minimize an objective function comprising a sum of distances computed using the Mahalanobis distance metric between candidate neighboring items that share at least one tag by optimizing 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, ξ

_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_i−

X_j)

 

where A is the parameter matrix of the Mahalanobis distance whose values are optimized by the training;

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

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

wherein the generating is performed by a digital processing device; and

displaying, on a display, the at least one tag recommendation for the item to be tagged.

13. The tag recommendation method as set forth in claim 9, wherein the generating further comprises:

selecting the set of candidate neighboring items from one of;

the set of items whose item owner is the item owner of the item to be tagged,

a set of items consisting of a combination of the set of items whose item owner is the item owner of the item to be tagged and the set of items whose item owners are users of the electronic social network who are contacts in the electronic social network of the item owner of the item to be tagged, and

a set of items consisting of a combination of the set of items whose item owner is the item owner of the item to be tagged and the set of items whose item owners are users of the electronic social network having between one and N degrees of separation inclusive from the item owner of the item to be tagged in the user-user contacts information of the electronic social network where N is an integer greater than or equal to two.

14. The tag recommendation method as set forth in claim 9, wherein the selecting of the set of nearest neighboring items comprises:

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

10. A tag recommendation method operating in conjunction with an electronic social network including user accounts and tagged items, the user accounts including user-user contacts information and each tagged item being indexed in the electronic social network by an item owner of the tagged item wherein the item owner is a user of the electronic social network, the tag recommendation method comprising:

for an item to be tagged that is indexed in the electronic social network by an item owner of the item to be tagged, generating at least one tag recommendation for the item to be tagged by;

training a Mahalanobis distance metric on a set of candidate neighboring items in the electronic social network to optimize a correlation between (i) the trained Mahalanobis distance between pairs of items i and j of the set of candidate neighboring items and (ii) an overlap metric measuring set overlap of the tag sets of the two items i and j wherein the overlap metric is proportional to |T_i∩

T_j| where T_i denotes the tag set associated with the item i and T_j denotes the tag set associated with the item j,

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

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

wherein the generating is performed by a digital processing device; and

displaying, on a display, the at least one tag recommendation for the item to be tagged.

11. The tag recommendation method as set forth in claim 10, 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, ξ

_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_i−

X_j)

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

12. The tag recommendation method as set forth in claim 10, 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|).