Data fusion using consensus aggregation functions

• US 8,150,793 B2
• Filed: 07/07/2008
• Issued: 04/03/2012
• Est. Priority Date: 07/07/2008
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Ah-Pine, Julien
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): RIFKIN, BEN M
• Application Number:
  US12/168,436
• Publication Number:
  US 20100005050A1
• Time in Patent Office: 1,366 Days
• Field of Search: 706/50
• US Class Current: 706/50
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06N 5/043 Distributed expert systems; Blackboards

Abstract

A fusion system fuses M rankings generated by M judges by (i) computing values of an aggregation function for items of the M rankings, the aggregation function including a sum of pairwise conjunctions of ranking values of different judges for an input item, and (ii) constructing an aggregation ranking based on the aggregation function values. In an illustrative application, the judges are different Internet search engines and the rankings are sets of search engine results generated for a query input to the search engines, and a consensus search result corresponding to the query is defined by the aggregation ranking. In another illustrative application, the judges are different soft classifiers, and the rankings are probability vectors generated for an input object by the different soft classifiers, and the input object is classified based on a consensus probability vector defined by the aggregation ranking.

Claims

1. A fusion method for fusing M rankings generated by M judges where M is an integer greater than unity, the fusion method comprising:

computing values of an aggregation function for items in a union of items of the M rankings, the aggregation function including a sum of pairwise conjunctions of ranking values of different judges for an input item, wherein the aggregation function has an output quantitatively equal to A(i) where A(i) is given by;

2. The fusion method as set forth in claim 1, further comprising:

prior to the computing, truncating the M rankings to include only k highest ranked items of each truncated ranking where k is an integer greater than unity; and

normalizing the M truncated rankings.

3. The fusion method as set forth in claim 1, wherein the M judges are M different Internet search engines and the M rankings are M sets of search engine results generated for a query input to the M different Internet search engines, and the outputting of informational content embodying the aggregation ranking comprises:

displaying a consensus Internet search result defined by the aggregation ranking and corresponding to the query.

4. The fusion method as set forth in claim 1, wherein the M judges are M different soft classifiers for classifying an object respective to a set of k classes where k is an integer greater than unity, and the M rankings are M probability vectors each having k elements generated for an input object by the M different soft classifiers, and the outputting of informational content embodying the aggregation ranking comprises:

assigning a classification to the input object based on a consensus probability vector defined by the aggregation ranking; and

at least one of displaying and storing the classification.

5. The fusion method as set forth in claim 1, wherein the triangular norm T(S_j(i),S_j′

(i)) is a non-parametric triangular norm selected from a group consisting of;

min(S_j(i),S_j′

(i)),

(S_j(i)●

S_j′

(i)) where ●

denotes a product,

a Lukasiewicz norm T^L(S_j(i),S_j′

(i))=max(S_j(i)+S_j′

(i)−

1,

     0), and

a drastic product

6. The fusion method as set forth in claim 1, wherein the triangular norm T(S_j(i),S_j′

(i)) is a parametric triangular norm.

7. The fusion method as set forth in claim 6, further comprising:

estimating strengths of relationship for different pairs of ranking values obtained from the M rankings; and

adjusting a parameter of the parametric triangular norm for different pairwise conjunctions of ranking values based on the estimated strengths of relationship of the different pairs of ranking values.

8. A fusion apparatus comprising:

a digital processing device configured to perform a fusion method for fusing M rankings generated by M judges where M is an integer greater than unity, the fusion method including;

computing values of an aggregation function for items in a union of items of the M rankings, the aggregation function including a sum of pairwise conjunctions of ranking values of different judges for an input item, wherein the aggregation function has an output quantitatively equal to A(i) where A(i) is given by;

9. A storage medium storing instructions executable by a digital processing device to perform a fusion method for fusing M rankings generated by M judges where M is an integer greater than unity, the fusion method including (1) computing values of an aggregation function for items in a union of items of the M rankings, the aggregation function including a sum of pairwise conjunctions of ranking values of different judges for an input item, wherein the aggregation function has an output quantitatively equal to A(i) where A(i) is given by:

10. The storage medium as set forth in claim 9, wherein the triangular norm T(S_j(i),S_j′

(i)) is a non-parametric triangular norm selected from a group consisting of;

min(S_j(i),S_j′

(i)),

(S_j(i)●

S_j′

(i)) where ●

denotes a product,

a Lukasiewicz norm T^L(S_j(i),S_j′

(i))=max(S_j(i)+S_j′

(i)−

1,

     0), and

a drastic product

11. The storage medium as set forth in claim 9, wherein the triangular norm T(S_j(i),S_j′

(i)) is a parametric triangular norm.

12. The storage medium as set forth in claim 9, wherein the triangular norms are selected from a group consisting of:

13. The storage medium as set forth in claim 9, wherein the stored instructions are further executable to one of (1) acquire the M rankings as M sets of search engine results generated for a query input to M different Internet search engines and (2) acquire the M rankings as M probability vectors each having k elements corresponding to classes of a set of k classes generated for an input object by M different soft classifiers.

14. The storage medium as set forth in claim 9, wherein the M judges are M different Internet search engines and the M rankings are M sets of search engine results generated for a query input to the M different Internet search engines, and the outputting operation (3) comprises:

displaying a consensus Internet search result defined by the aggregation ranking and corresponding to the query.

15. The storage medium as set forth in claim 9, wherein the M judges are M different soft classifiers for classifying an object respective to a set of k classes where k is an integer greater than unity, and the M rankings are M probability vectors each having k elements generated for an input object by the M different soft classifiers, and the outputting operation (3) comprises:

assigning a classification to the input object based on a consensus probability vector defined by the aggregation ranking; and

at least one of displaying and storing the classification.