1. A computer-implemented method comprising: receiving a plurality of candidate translations for a phrase, wherein the phrase is in a first language and each candidate translation is a translation of the phrase into a different language from the first language; obtaining a first group of visual media search results, wherein the first group of visual media search results are responsive to a first visual media search query with text corresponding to the phrase; obtaining a respective second group of visual media search results for each of the candidate translations, wherein the second group of visual media search results are responsive to a second visual media search query with text corresponding to the candidate translation; generating a respective quality of results statistic for each of the candidate translations, wherein the quality of results statistic for each of the candidate translations is a value that represents a quality of search results that are responsive to the second visual media search query with text corresponding to the candidate translation; calculating, by one or more computers, a respective similarity score for each of the candidate translations, wherein the similarity score is an estimate of visual similarity between the first group of visual media search results and the second group of visual media search results for the candidate translation; selecting one or more of the candidate translations based on, for each candidate translation, the similarity score for the candidate translation and the quality of results statistic for the candidate translation; and associating each of the one or more selected candidate translations with the phrase as a valid translation for the phrase.