Science Powering Product: Large-scale Query-to-Ad Matching in Sponsored Search
By Mihajlo Grbovic, Vladan Radosavljevic, Nemanja Djuric, Andy Feng, Erik Ordentlich, and Lee Yang
Sponsored search represents a major source of revenue for search engines on the Web. This popular advertising model brings a unique possibility for advertisers to target users’ immediate intent communicated through a search query. Usually this is done by displaying ads alongside organic search results for queries deemed relevant to an advertiser’s products or services. In a typical ad-booking scenario, the advertiser provides the search engine with their ad title and description, along with a list of bid terms (i.e., queries against which they want their ads to run). However, due to a large number of unique queries it is challenging for advertisers to identify all relevant bid terms. For this reason, search engines often provide a service of advanced matching, which automatically finds additional relevant queries for advertisers to bid on.
In a new research paper entitled “Scalable Semantic Matching of Queries to Ads in Sponsored Search Advertising,” published in the proceedings of the upcoming 39th International ACM SIGIR Conference, we present a novel advanced matching approach based on the idea of semantic embeddings that was recently launched at full scale on Yahoo’s Sponsored Search platform.
Traditionally, matches between queries and ads are found based on the level of textual similarity between the query text and the ad title text. In our approach, instead of forming the so-called bag-of-words vector representations of queries and ads, we propose learning vector representations using a large dataset of search sessions, such that ads and relevant queries would be close in the vector space. This makes it easy for a computer to match queries to ads based on similarities between the learned vectors.
Large-scale Training Algorithm
To train the query and ad vectors we used the largest in-house Yahoo Search dataset thus far, comprising over 9 billion search sessions. As illustrated in Figure 1 (left), a search session is defined as an uninterrupted sequence of user actions comprising queries (marked in blue), ad clicks (marked in orange), and search link clicks (marked in green).
Once a search session dataset is created, we then learn a vector representation for each unique query, ad id, and search link click id by leveraging surrounding context. Specifically, queries, ads, and links from the same session are used as positive signals, and ads that are skipped in favor of a click on a lower-positioned ad are seen as negative signals. When updating the vectors we also found it useful to utilize dwell-time, i.e. time spent on the landing page post click, such that we can distinguish between good clicks and unsatisfactory or accidental clicks. The graphical representation of our just-described search2vec model is illustrated in Figure 1 (right).
To realize the full potential of the proposed approach, we found it necessary to train vectors for several hundred million queries, ads, and links. Existing implementations for training embeddings were found to fall short for our vocabulary size target, as they require that all of the vectors fit in the memory of a single machine. To address this issue, we developed a novel distributed embedding training algorithm (Figure 2) based on the parameter server paradigm.
Our key innovations and findings were that the column-wise partitioning of vectors among parameter server (PS) shards and server-side computation of vector-dot products greatly reduces network bandwidth requirements relative to the conventional parameter server approach.
We implemented our search2vec system in Java and Scala on a Hadoop YARN-scheduled cluster, leveraging Slider and Spark. The system allowed us to train embeddings for more than 126 million unique queries, 43 million unique ads, and 132 million unique links, which is a 5x increase compared to a single machine implementation.
Finding the Best Queries for an Ad
After learning the query and ad vectors, finding the best queries for a specific ad becomes a matter of calculating a cosine similarity between the ad vector and all query vectors, and identifying queries with the highest cosine similarity value. As demonstrated in Figure 3, this allows us to find relevant queries for any ad without ever looking into an ad title and description.
To further illustrate the quality of our query vectors, in the demonstration video below we show how resulting query vectors can be manipulated to find similar queries to an input query. This process is known as query rewriting.
Experiments and Product Impact The launch of our new matching algorithm was a yearlong effort by a team of research scientists and engineers. In order to make sure the algorithm would function correctly, we conducted a series of offline and online tests.First, we asked humans to eyeball some matches between the queries and ads, and at the same time, used search2vec to calculate the cosine similarity between their corresponding vectors. We wanted the matching algorithm to ideally agree with human judgments; low similarity was assigned to matches that humans judged as bad, and high similarity matches to the ones judged by humans as good. Moreover, given a query we wanted our model to rank the ads with good grades higher than the ads with bad grades, which we evaluated using an NDCG measure.
The results summarized in Figure 4 (left), show that with the exception of several outliers, the search2vec algorithm does a great job in distinguishing between different classes of human judgments. In addition, as Figure 4 (right) shows, compared to several baseline algorithms, search2vec does a better job in ranking ads. Second, before launching our new matching algorithm at full scale, we performed online performance experiments in form of A/B tests. The first test was conducted one year ago and it involved testing a dictionary of query-ad matches produced by a single machine search2vec model that could scale up to 60 million vectors. When compared to the production model that did not contain this additional dictionary, we observed a 7% increase in revenue per search. This lead to the successful deployment of our first search2vec model. In the months ahead we worked on scaling up the size of our vocabulary by implementing parameter server-based distributed training. It allowed us to train more than 300 million vectors. Our second A/B test showed that our distributed search2vec model could achieve an additional 9.4% increase in revenue per search compared to the production model that already had the single machine dictionary. The results from both A/B tests (Table 1) also showed that as we increased query coverage and auction depth, we did not hurt user experience since click-through-rates (CTR) remained flat and even slightly positive.
Following successful A/B tests, our distributed training model was launched in production. Today, search2vec is being re-trained on a regular basis and accounts for more than 30% of all broad match impressions and revenue on Yahoo Search. Contributing Query Embeddings to the Research Community
As part of this research, we took 8M query vectors trained using our search2vec system, and made them available to researchers via our Yahoo Webscope data-sharing program. The vectors may serve as a testbed for query rewriting tasks, or word and sentence similarity tasks, which are common problems in NLP research. We would like for researchers to be able to produce query rewrites based on these vectors and test them against other state-of-the-art techniques. In addition, we provide an editorially-judged set of 4016 query rewrites, on which we compared our search2vec performance against the word2vec model, the results of which are summarized below.