1. A system, comprising: one or more computers; and a computer-readable storage device storing instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising: storing data identifying for each of a plurality of queries, a plurality of training images for the query, wherein each of the training images is classified as being in a positive group of images for the query or a negative group of images for the query according to a respective query-specific preference measure for the image; selecting one of the queries as a selected query; iteratively evaluating a scoring model with the selected query, the evaluation iteration comprising: selecting a first image from either the positive group of images or the negative group of images for the selected query, and applying a scoring model to the first image and the selected query to determine a score for the first image; selecting a plurality of candidate images from the other group of images for the selected query; applying the scoring model to each of the candidate images and the selected query to determine a respective score for each candidate image and the selected query, and then selecting a second image from the candidate images, the second image having a highest score; and determining that the scores for the first image and the second image for the selected query fail to satisfy a criterion, wherein the criterion requires that a result of the score of the image selected from the positive group of images for the selected query minus the score of the image selected from the negative group of images for the selected query exceeds a threshold, and in response updating the scoring model, storing the updated scoring model, and selecting another one of the queries as a selected query for another evaluation iteration.