DATA FUSION USING CONSENSUS AGGREGATION FUNCTIONS

• US 20100005050A1
• Filed: 07/07/2008
• Published: 01/07/2010
• Est. Priority Date: 07/07/2008
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Ah-Pine, Julien
• Granted Patent: US 8,150,793 B2
• Time in Patent Office: Days
• US Class Current: 706/52
• 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;

constructing an aggregation ranking of items in the union of items of the M rankings based on the computed values of the aggregation function; and

outputting informational content embodying the aggregation ranking.

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 pairwise conjunctions are pairwise triangular norms.

4. The fusion method as set forth in claim 1, wherein the aggregation function has an output quantitatively equal to A(i) where A(i) is given by:

5. The fusion method as set forth in claim 1, wherein the sum of pairwise conjunctions of ranking values of different judges for an input item included in the aggregation function has an output quantitatively equal to an output of the sum:

6. The fusion method as set forth in claim 5, 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<sub>j′

(i)),</sub>

(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

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

(i)) is a parametric triangular norm.

8. The fusion method as set forth in claim 7, 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.

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

estimating strengths of relationship for different pairs of ranking values for items in the union of items of the M rankings; and

adjusting the pairwise conjunctions of ranking values of the sum of pairwise conjunctions of ranking values included in the aggregation function based on the estimated strengths of relationship for the different pairs of ranking values.

10. 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.

11. 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.

12. A storage medium storing instructions executable to fuse M rankings generated by M judges where M is an integer greater than unity 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 of items of the M rankings based on the computed values of the aggregation function.

13. The storage medium as set forth in claim 12, wherein the stored instructions are further executable to truncate the M rankings to include only k highest ranked items of each truncated ranking where k is an integer greater than unity and to normalize the M truncated rankings, the computing (i) and constructing (ii) operating on the M truncated rankings.

14. The storage medium as set forth in claim 12, wherein the pairwise conjunctions are pairwise triangular norms.

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

16. The storage medium as set forth in claim 12, wherein the computing of values of the aggregation function for items of the M rankings further includes (i)(a) estimating strengths of relationship for different pairs of ranking values for items of the M rankings and (i)(b) adjusting the pairwise conjunctions of ranking values of the sum of pairwise conjunctions based on the estimated strengths of relationship for the different pairs of ranking values.

17. The storage medium as set forth in claim 12, wherein the stored instructions are further executable to acquire the M rankings as M sets of search engine results generated for a query input to M different Internet search engines.

18. The storage medium as set forth in claim 12, wherein the stored instructions are further executable to 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.

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

a digital processing device configured to (i) compute 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) construct an aggregation ranking of items of the M rankings based on the computed values of the aggregation function.

20. The fusion apparatus as set forth in claim 19, further comprising:

a user interface device integrated with or separate from the digital processing device, the user interface device configured to display informational content embodying the aggregation ranking.