System and method for the calibration of a scoring function

• US 8,280,891 B1
• Filed: 06/17/2011
• Issued: 10/02/2012
• Est. Priority Date: 06/17/2011
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Urbach, Shlomo, Netzer, Yuval
• Primary Examiner(s): Wong, Leslie
• Application Number:
  US13/163,014
• Time in Patent Office: 473 Days
• Field of Search: 707748-750, 707/758, 707/999.006, 707/999.01, 707/999.107, 706/12, 706/20
• US Class Current: 707/748
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06V 2201/10 Recognition assisted with metadata

Abstract

A system and method for calibrating a scoring function. The scoring function S(input, classification) provides a score based on the amount of evidence a particular input has in connection with a particular classification. For example, a street level image may be OCR'"'"'ed so as to indicate the names of establishments contained within the image, and the scoring function indicates how much evidence exists within the image for a particular establishment. Some establishments (i.e. classifications) may produce higher scores based on the nature of the establishment rather than the nature of the image (i.e. input) causing any ranking of establishments done on the basis of the scoring function to be biased. Accordingly, the scoring function is calibrated by determining the probability distribution of scores for an establishment over a false set of images that do not display the establishment. The scoring function is calibrated so as to adjust the score to overcome such bias.

Claims

1. A method of calibrating a scoring function, the method comprising:

accessing a scoring function, wherein the scoring function provides a score indicating a degree to which an input relates to a classification;

receiving a first classification;

accessing a set of background inputs that have no more than an incidental relation to the first classification;

applying the scoring function to each of the background inputs in connection with the first classification so as to create a first distribution of background scores;

receiving a first input that is not included in the set of background inputs;

altering the scoring function in accordance with the first distribution of background scores to create a first calibrated scoring function; and

determining a first calibrated score for the first input in connection with the first classification using the first calibrated scoring function.

2. The method of claim 1, wherein the first input and the set of background inputs are images, the classification is an establishment, and the score from the scoring function relates to the amount of evidence that exists as to whether the establishment appears within a particular image.

3. The method of claim 1, wherein the first input, the set of background inputs, and classification are websites, and the score from the scoring function relates to the number of users that visited both a first input website and one or more classification websites.

4. The method of claim 1, wherein the first input and the set of background inputs include text, the classification is a phrase, and the score from the scoring function relates to number of times the phrase appears within a particular input.

5. The method of claim 4, wherein the first input and the set of background inputs are selected from the group consisting of:

documents, websites, or books.

6. The method of claim 1, wherein determining the calibrated score includes creating a cumulative distribution function (CDF), the CDF indicating, for a subset of potential scores, the probability of the distribution of background scores being higher than each of the potential scores.

7. The method of claim 6, wherein determining the calibrated score includes:

smoothing the CDF to create a smoothed CDF (SCDF); and

calculating −

log₂(SCDF).

8. The method of claim 7, wherein the CDF for any potential score is represented as CDF_i=CDF_i+1+H_i/n, where n is the number of potential scores, H_i represents the number of background inputs receiving a score i, and CDF_N=H_N/n.

9. The method of claim 7, wherein determining the calibrated score includes:

calculating M_i=min(K*M_i^all, U, −

log₂(SCDF_i)), where M_i^all represents a default model for all background scores relating to a set of classifications, K represents an optional limiting factor, and U represents an upper limit on calibrated scores.

10. The method of claim 1 further comprising:

accessing a second classification, wherein the scoring function provides a second score indicating a degree to which an input relates to the second classification;

applying the scoring function to each of the background inputs in connection with the second classification to create a second distribution of background scores;

altering the scoring function in accordance with the second distribution of background scores to create a second calibrated scoring function;

determining a second calibrated score for the first input in connection with the second classification using the second calibrated scoring function; and

comparing the first calibrated score and the second calibrated score.

11. The method of claim 10, wherein the second calibrated score is for a second input in connection with the second classification.

12. The method of claim 10, further comprising transmitting data over a network based on the comparison of the first calibrated score and the second calibrated score.

13. The method of claim 1, further comprising:

accessing a set of default classifications;

applying the scoring function to each combination of background inputs and default classifications, to create a default background distribution; and

altering the first calibrated scoring function in accordance with the default background distribution.

14. The method of claim 13 further comprising:

comparing the default background distribution to the first distribution of background scores;

wherein the altering of the first calibrated scoring function occurs only if the first distribution of background scores indicates a higher score than the default background distribution.

15. A device for calibrating a scoring function:

a memory for storing classifications, inputs, and scoring functions, wherein at least a subset of the inputs are background inputs; and

a processor coupled to the memory, the processor configured to execute the instructions to;

access a first classification and a scoring function, wherein the scoring function provides a score indicating a degree to which an input relates to the first classification;

access background inputs that have no more than incidental relation to the first classification;

apply the scoring function to each of the background inputs in connection with the first classification so as to create a first distribution of background scores;

access a first input that is not included in the set of background inputs; and

determine a first calibrated score for the first input in connection with the first classification, the first calibrated score being determined by altering the scoring function in accordance with the distribution of background scores.

16. The device of claim 15, wherein the first input and the set of background inputs are images, the first classification is an establishment, and the first score from the scoring function relates to whether the establishment appears within a particular image.

17. The device of claim 15, wherein the first input, the set of background inputs, and first classification are websites, and the first score from the scoring function relates to the number of users that visited both a first input website and one or more classification websites.

18. The device of claim 15, wherein the first input and the set of background inputs include text, the classification is a phrase, and the first score from the scoring function relates to number of times the phrase appears within a particular input.

19. The device of claim 15 wherein the instructions further cause the processor to:

receive a second classification, wherein the scoring function provides a second score indicating a degree to which an input relates to the classification;

apply the scoring function to each of the background inputs in connection with the second classification so as to create a second distribution of background scores;

determine a second calibrated score for the first input in connection with the second classification, the second calibrated score being determined using the second distribution of background scores to alter the second score of the scoring function; and

compare the first calibrated score and second calibrated score.

20. The device of claim 15 wherein the processor is further configured to:

transmit data relating to the classification having a higher calibrated score.