Feature selection for ranking

1. A method to select features for ranking for information retrieval, implemented by a computing device, the method comprising:

selecting the features iteratively;

computing importance scores for the features, wherein the importance scores include ranking performances;

measuring similarity scores between two features based on the ranking performances, wherein the similarity scores are based on a correlation between ranking results of the two features; and

selecting the features that maximize a sum of the importance scores of individual features and that minimize a sum of the similarity scores between the selected features, wherein the features that are selected have a largest cumulative importance score and a least mutual similarity score;

wherein the features selected for ranking are modeled as an optimization problem, the optimization problem includes:

constructing an undirected graph and using a node to represent a feature;

representing a weight of the node and a weight of an edge between two nodes; and

constructing a set to contain the selected features.

2. The method of claim 1 , wherein computing the importance scores comprises at least one of a mean average precision (MAP), a normalized discounted cumulative gain (NDCG), or a loss function.

3. The method of claim 1 , wherein measuring the similarity scores comprises at least one of a Spearman's footrule F, a rank correlation R, or a Kendall tau coefficient.

4. The method of claim 1 , wherein the maximizing the sum of the importance scores of the individual features and the minimizing the sum of the similarity scores between the selected features include:

max

⁢

⁢

∑

i

⁢

ω

i

⁢

x

i

min

⁢

⁢

∑

i

⁢

⁢

∑

j

≠

i

⁢

⁢

e

i

,

j

⁢

x

i

⁢

x

j

s

.

t

.

⁢

x

i

∈

{

0

,

1

}

⁢

⁢

i

=

1

,

…

⁢

,

m

∑

i

⁢

⁢

x

i

=

t

wherein t is a number of selected features;

wherein x i =1 (or 0) denotes whether feature v i is selected or not;

wherein ω i is an importance score of feature ν i ;

wherein e i,t is an edge that denotes a similarity between the features ν i and ν j ;

wherein e i,t=τ(ν νν j ).;and

wherein e i,j=e j,i .

5. The method of claim 4 , wherein the maximizing the sum of the importance scores of the individual features and the minimizing the sum of the similarity scores between the selected features further comprises using a linear combination of:

max

⁢

⁢

∑

i

⁢

ω

i

⁢

x

i

-

c

⁢

∑

i

⁢

∑

j

≠

i

⁢

e

i

,

j

⁢

x

i

⁢

x

j

s

.

t

.

⁢

x

i

∈

{

0

,

1

}

⁢

⁢

i

=

1

,

…

⁢

,

m

∑

i

⁢

⁢

x

i

=

t

wherein c is a parameter to balance maximizing the the sum of the importance scores of individual features and minimizing the sum of the similarity scores between the selected features.

6. The method of claim 1 , further comprising solving the optimization problem by using a greedy algorithm.

7. The method of claim 6 , wherein the greedy algorithm further comprises:

selecting the node with a largest weight without loss of generality;

handicapping the other nodes according to the similarities;

adding the selected node to the set and removing the selected node from the graph together with edges connected to the selected node; and

outputting the set that contains the selected features.

8. The method of claim 7 , wherein the greedy algorithm comprises selecting the features iteratively.

9. The method of claim 7 , wherein the undirected graph is represented by G 0 ;

wherein the feature is represented by ν i , wherein the weight of the node ν i is represented by ω i , wherein the weight of the edge between a first node ν i and a second node ν j is represented by e i,j ;

wherein the set is represented by S;

wherein a node with a largest weight is ν k i ; and

further comprising identifying nodes that have similarities to the node with the largest weight ν k i ;

updating weights of the identified nodes by:

ω j ←ω j −e k t′ j *2c,j≠k i ;

adding the identified nodes with the largest weight ν k i to the set S;

removing the node with the largest weight ν k i from the undirected graph together with edges connected to the node by:

S i+1 =S i {ν k i }, G i+1 =G i \{ν k i }; and

outputting the set S t to solve the optimization problem.

10. A computer-readable storage medium comprising computer-readable instructions executable on a computing device, the computer-readable instructions comprising:

selecting features iteratively;

defining an importance score for the features, wherein the importance score includes a ranking result;

defining a similarity score between every two features based on the ranking result, wherein the similarity score is based on a correlation between ranking results of the two features;

selecting the features that maximize total importance scores of the features and minimize total similarity scores of a set of features, wherein the features that are selected have a largest cumulative importance score and a least mutual similarity score;

solving an optimization problem with the features that are selected for ranking; and

using a greedy algorithm to solve the optimization problem, the greedy algorithm includes:

constructing an undirected graph;

using a node to represent a feature;

representing a weight of the node and a weight of an edge between two nodes; and

constructing a set to contain the selected features.

11. The computer-readable storage medium of claim 10 , wherein defining the importance score comprises at least one of a mean average precision (MAP), a normalized discounted cumulative gain (NDCG), or a loss function.

12. The computer-readable storage medium of claim 10 , wherein defining the similarity score comprises at least one of a Spearman's footrule F, a rank correlation R, or a Kendall tau coefficient.

13. The computer-readable storage medium of claim 10 , wherein defining the similarity score includes using a Kendall tau coefficient;

wherein the Kendall tau coefficient is represented by τ, the τ value of a query q for features ν i and ν j is calculated as:

τ

q

⁡

(

v

i

,

v

j

)

=

#

⁢

{

(

d

s

,

d

t

)

∈

D

q

|

d

s

⁢

π

⁢

⁢

v

i

⁢

d

t

⁢

⁢

and

⁢

⁢

d

s

⁢

π

⁢

⁢

v

j

⁢

d

t

}

#

⁢

{

(

d

s

,

d

t

)

∈

D

q

}

;

wherein D q is a set of instance pairs (d s , d t ) in response to the query q;

wherein #{·} represents a number of an element in a set;

wherein d s <ν i d t means that instance d t is ranked before d s according to a feature ν i ;

wherein for a set of queries, τ q (ν i , ν j ) values of queries are averaged; and

wherein corresponding result τ(ν i ,ν j ) is used as a final similarity measure between the features ν i and ν j .

14. The computer-readable storage medium of claim 10 , wherein solving the optimization problem with the features selected for ranking comprises selecting the features with a largest cumulative importance score and a least mutual similarity score.

15. The computer-readable storage medium of claim 10 , wherein the greedy algorithm further comprises:

selecting the node with a largest weight without loss of generality;

handicapping the other nodes according to the similarities;

adding a selected node to the set and removing the selected node from the undirected graph together with edges connected to the selected node; and

outputting the set that contains the selected features.

16. A system for feature selection for ranking, comprising:

a processor;

a memory coupled to the processor, wherein the processor is configured for:

processing data to select features from an entire feature set;

assigning an importance score to the features, wherein the importance score includes ranking performance;

defining a similarity score between the features based on the ranking performance, wherein the similarity score is based on a correlation between ranking results of the two features;

using an algorithm to maximize cumulative importance score and minimize mutual similarity score of the features, the algorithm includes:

constructing an undirected graph and using a node to represent a feature;

representing a weight of the node and a weight of an edge between two nodes; and

constructing a set to contain the selected features; and

identifying the features that are selected for ranking, wherein the features that are selected have a largest cumulative importance score and a least mutual similarity score.

17. The system of claim 16 , wherein the identifying the features comprises selecting the features that maximize total importance scores of the selected features and minimize total similarity scores between the selected features, wherein the features selected for ranking models an optimization problem.

18. The system of claim 16 , wherein assigning the importance score comprises at least one of a mean average precision (MAP), a normalized discounted cumulative gain (NDCG), or a loss function.

19. The system of claim 16 , wherein the algorithm further comprises constructing an undirected graph with nodes corresponding to the features and a weight of an edge between the nodes, wherein the edge represents a similarity between the features.

20. The system of claim 16 , wherein the algorithm further comprises:

selecting a node with a largest weight without loss of generality;

handicapping the other nodes according to the similarities;

adding a selected node to the set and removing the selected node from the undirected graph together with edges connected to the selected node; and outputting the set that contains the selected features.