# US 2010/0250190 A1 · Tag ranking

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0250190 A1
- Document ID: US20100250190A1
- Status: Published application
- Kind: A1
- Application number: 12/415,722
- Filed: 2009-03-31
- Published: 2010-09-30
- Earliest claimed: 2009-03-31
- Assignees: Microsoft Corporation
- Inventors: HongJiang Zhang; Dong Liu; Meng Wang; Linjun Yang; Xian-Sheng Hua
- Web page: https://patentgrep.com/patent/US20100250190A1

## CPC

- G06F 16/48: Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Technologies for generating a boosted tag ranking for a media instance, the boosted tag ranking based on probabilistic relevance estimation and tag correlation refining. Such boosted tag rankings may be used for search result ranking, tag recommendation, and group recommendation.

## Claims

### Claim 1

A system for generating a boosted tag ranking for a media instance, the system comprising:
a probabilistic relevance estimator operable to estimate a relevance score for each input tag of the target media instance, wherein each relevance score is associated with a corresponding input tag, wherein the relevance scores are ordered by relevance thus forming a relevance tag ranking; and
a tag correlation refiner operable to refine the relevance tag ranking based on tag similarity measurements derived from media instances that share a common tag with the media instance wherein the tag similarity measurements are based on tag exemplar similarity and tag concurrence similarity, wherein the media instances are comprised by at least one media repository.

### Claim 2 (depends on 1)

The system of claim 1 wherein the tag exemplar similarity between tags ti and tj is defined as:
ϕ
e

(
t
i
,
t
j
)
=
exp
(
-
1
N
*
N

∑
x
∈
Γ
t
i
,
y
∈
Γ
t
j


x
-
y

2
σ
2
)
where Γt represents a collection of N nearest media instances of the media instances, and where σ is a radius parameter.

### Claim 3 (depends on 2)

The system of claim 2 wherein the radius parameter σ is the median value of all pair-wise Euclidian distances between the media instances.

### Claim 4 (depends on 2)

The system of claim 2 wherein the tag concurrence similarity between tags ti and tj is computed in part by estimating the distance between the tags ti and tj:
d

(
t
i
,
t
j
)
=
max

(
log


f

(
t
i
)
,
log


f

(
t
j
)
)
-
log


f

(
t
i
,
t
j
)
log


G
-
min

(
log


f

(
t
i
)
,
log


f

(
t
j
)
)
)
where f(ti) and f(tj) are total numbers of media instances tagged with tag ti and tag tj respectively in a media repository, and f(ti,tj) is a total number of media instances tagged with both tag ti and tag tj in the media repository.

### Claim 5 (depends on 4)

The system of claim 4 wherein the concurrence similarity between tags ti and tj is defined as:
φc(t1,tj)=exp(−d(t1,tj)).

### Claim 6 (depends on 5)

The system of claim 5 wherein the tag exemplar similarity and tag concurrence similarity between two tags ti and tj are combined as similarity value sij.

### Claim 7 (depends on 6)

The system of claim 6 wherein the similarity value sij is defined as:
sij=s(ti,tj)=λ·φe(ti,tj)+(1−λ)·φc(ti,tj)
where λ belongs to [0, 1].

### Claim 8 (depends on 7)

The system of claim 7 wherein the tag correlation refiner constructs a tag graph wherein an edge between two nodes of the tag graph, wherein the two nodes represent the two tags ti and tj, is weighted based on the similarity value sij.

### Claim 9 (depends on 8)

The system of claim 8 wherein a random walk over the tag graph is performed, the random walk operable to promote tags of the relevance tag ranking that have many near neighbors and demote isolated tags of the relevance tag ranking.

### Claim 10 (depends on 1)

The system of claim 1 wherein the media instance is a digital image.

### Claim 11 (depends on 1)

The system of claim 1 wherein the media instance is a digital video.

### Claim 12 (depends on 1)

The system of claim 1 wherein the each input tag is taken from surrounding text of a document including the media instance.

### Claim 13 (depends on 1)

The system of claim 1 wherein a search result ranking is generated for each media instance returned in a search.

### Claim 14 (depends on 1)

The system of claim 1 wherein a group recommendation is generated for the media instance based in part on keywords associated with various groups.

### Claim 15 (depends on 1)

The system of claim 1 wherein a tag recommendation is generated for the media instance and wherein the each input tag is derived from neighbors of the media instance.

### Claim 16

A method for generating a boosted tag ranking for a media instance, the method comprising:
estimating, by a probabilistic relevance estimator of a computer, a relevance score for each input tag of the target media instance, wherein each relevance score is associated with a corresponding input tag, wherein the relevance scores are ordered by relevance thus forming a relevance tag ranking; and
refining, by a tag correlation refiner of the computer, the relevance tag ranking based on tag similarity measurements derived from media instances that share a common tag with the media instance wherein the tag similarity measurements are based on tag exemplar similarity and tag concurrence similarity, wherein the media instances are comprised by at least one media repository.

### Claim 17 (depends on 16)

The method of claim 16 wherein a search result ranking is generated for each media instance returned in a search.

### Claim 18 (depends on 16)

The method of claim 16 wherein a group recommendation is generated for the media instance based in part on keywords associated with various groups.

### Claim 19 (depends on 16)

The method of claim 16 wherein a tag recommendation is generated for the media instance and wherein the each input tag is derived from neighbors of the media instance.

### Claim 20

One or more computer-readable media embodying computer-executable instructions that, when executed by a processor of a computer, cause the computer to perform a method for generating a boosted tag ranking for a media instance, the method comprising:
estimating, by a probabilistic relevance estimator of the computer, a relevance score for each input tag of the target media instance, wherein each relevance score is associated with a corresponding input tag, wherein the relevance scores are ordered by relevance thus forming a relevance tag ranking; and
refining, by a tag correlation refiner of the computer, the relevance tag ranking based on tag similarity measurements derived from media instances that share a common tag with the media instance wherein the tag similarity measurements are based on tag exemplar similarity and tag concurrence similarity, wherein the media instances are comprised by at least one media repository.
