Retrieve Synonymous keywords for Frequent Queries in Sponsored Search in a Data Augmentation Way

Our translation model follows the common sequence to sequence learning encoder-decoder framework (Sutskever et al., 2014). And we implemented it with the Transformer (Vaswani et al., 2017), considering its state-of-the-art performance in learning long-range dependencies and capturing the semantic structure of the sentences.

To increase the translation model’s retrieval efficiency, a prefix tree for the keyword repository is built ahead of time, and all the beam search decoding is constrained on this prefix tree (Lian et al., 2019). At each step of the beam search, the prefix tree will directly give the valid suffix tokens following the current hypothesis path, then a greedy top-N selection is performed within the legal tokens. This technique makes sure all the generated sequences are valid keywords.

Paraphrases extracted from web data usually include some trivial patterns: reordering of words, insertion of function words and punctuation. A simple implementation of the translation model might generate too many trivial paraphrases, as is shown in Table 1. Common stop words removing method is too coarse to meet our need for synonym keeping, especially in Chinese. We carefully designed a synonym preserving data reduction method called Bag-of-Core-Words (abbreviated as BCW) transformation to reduce each sentence into a compact form without losing semantic information.

For each tokenized sentence, the BCW transformation consists of two sequential steps:

1. (1)

   Core-Words Transformation. Here we consider some part of speech (abbreviated as POS) tags (like interjections, modal particles, etc.) as redundant, which means removing it generally does not change the query’s intention. Table 2 lists the typical redundant POS tags. Tokens with these tags would be removed. It is worth noting that some of the POS removing rules might not be universally applicable to other languages. For example, modal particles and interjections are quite common in Mandarin Chinese, however, these words are unusual in English. And the remaining tokens are considered as core words. For brevity, we refer to this step as CW in the following sections.

   POS tag	Typical terms
   Interjection	哼(humph), 嗯 (em), 嘿 (hey), 嘘 (shh)
   Auxiliary word	等等 (and so on), 一般 (generally)
   Punctuation	comma, colon, question mark
   Modal particle	啊 (ah), 哇 (wow), 呦 (yo), 耶 (yeah)

2. (2)

   Bag-of-Words Transformation. In most cases word order does not affect the meaning of a sentence. In fact, we sample 600 commercial queries from the ad weblog and find that in 94% of cases, the original query and its Bag-of-Words form have the same meaning. Based on this consideration, we sort the remaining core tokens in the sentence literally to remove the order’s effect in the model training process. To make it more accurate, additional rules have been made to exempt the special cases. For example, Flights from New York to Beijing and Flights from Beijing to New York have the same Bag-of-words form, but their meanings are different. The same is true for Does hypertension cause hyperlipidemia and Does hyperlipidemia cause hypertension. So when sentences have two location tokens or two disease entity tokens or other token pairs with causality, temporal relation, etc., the order of the paired tokens remains unchanged.

The BCW transformation is simple, fast and very effective. Applying it to our Chinese training data effectively reduces the dataset size by nearly 20% with a synonym precision of 98%. Based on the BCW transformation, we devised a data-augmentation-like method to retrieve synonymous keywords, as is illustrated in Algorithm 1.

In business applications like sponsored search’s matching product, high precision is essential. The BERT-based classifier we use to further filter out bad cases has a similar structure with the classifier used in the sentence pair classification task illustrated in (Devlin et al., 2018). So we skip the exhaustive background description of the architecture and the training progress of the underlying model.

For the translation model, the word embeddings are randomly initialized. The vocabulary contains 100,000 most frequent tokens in the training data $\mathcal{D}_{train}^{PG}$. The word embedding dimension and the number of hidden units are both set to 512. For multi-layer and multi-head architecture of the Transformer, 4 encoder and decoder layers and 8 multi-attention heads are used. And during the training, all layers are regularized with a dropout rate of 0.2. And the model’s cross-entropy loss is minimized with an initial learning rate of $5\times 10^{-5}$ by Adam (Kingma and Ba, 2015) with a batch size of 128.

The paraphrase discriminant model is implemented with BERT (Devlin et al., 2018), which takes a query-keyword pair separated by a special token as input and predicts a synonymy label. The model contains 12 layers, 12 self-attention heads, and the hidden dimension size is 768. We initialize it with ERNIE (Sun et al., 2019), which learns Chinese lexical, syntactic and semantic information from a number of pretrained tasks, and fine-tuned it on $\mathcal{D}_{train}^{PI}$. The fine-tuned loss is minimized with an initial learning rate of $1\times 10^{-6}$ by Adam (Kingma and Ba, 2015) with a batch size of 64. We evaluate our model after each epoch and stop training when the validation loss on $\mathcal{D}_{dev}^{PI}$ does not decrease after 3 epochs.

All of the experiments are run on a machine equipped with a 12-core Intel(R) Xeon(R) E5-2620 v3 clocked at 2.40GHz, a RAM of 256G and 8 Tesla K40m GPUs.

For the translation model, we compared the retrieval performances of 3 different strategies. For all of the strategies, decoding is conducted in a Trie-constrained mode. For the sake of convenience, these strategies are abbreviated as follows:

• •

  BASE-M: This is our base strategy, where the translation model is trained on the original training data $\mathcal{D}_{train}^{PG}$. And the prefix tree is built on $\mathcal{K}$.

• •

  CW-M: In this strategy, the model is trained on the CW-transformed data. And the prefix tree is built on CW-trans–formed $\mathcal{K}$. The final result is made by joining the generated hypotheses with $\mathcal{K}$ based on the CW transformation.

• •

  BCW-M: In this strategy, the model is trained on the BCW-transformed data. And the prefix tree is built on BCW-trans–formed $\mathcal{K}$. The final result is made by joining the generated hypotheses with $\mathcal{K}$ based on the BCW transformation.

Each of the trained models is utilized to decode towards those queries in $\mathcal{D}_{test}^{PG}$ to get a result data set $\mathcal{D}_{1}^{PG}$. Under the data augmentation framework, we expect the translation model could make a large data increment $\Delta$ while keeping a high precision. There are three major concerns: the size of $\Delta$, the precision of $\Delta$, and the decoding time for generating $\Delta$. The following indicators are considered for evaluation:

• •

  Diff ratio is defined as $\frac{|\mathcal{D}_{1}^{PG}-\mathcal{D}_{test}^{PG}|}{|\mathcal{D}_{test}^{PG}|}$, which is an indicator of the generalization ability.

• •

  BLEU-n is an indirect indicator of the generation quality. Since most sentences in our scenario are short texts, we only consider BLEU-2.

• •

  Dist-n measures the number of distinct N-grams within the set of generated data, which indicates the diversity among the generated paraphrases. Following previous studies (Park et al., 2019), we use Dist-1,2.

• •

  Precision indicates the proportion of synonymous pairs in generated data. Concretely, for each strategy, 400 query-keyword pairs are sampled from the generated results $\mathcal{D}^{PG}_{1}$ for binary human evaluation. We denote this dataset as $\mathcal{D}^{PG}_{1h}$ for later reference.

Rows 1, 3 and 4 in Table 4 show the retrieval performances for these three different strategies with a beam size of 30. We can see that: BASE-M could already make a certain amount of Diff ratio, which proves the feasibility of the data-augmentation-like framework. CW-M and BCW-M further enlarge the Diff ratio to 2.4 times and 4.2 times, compared with the base method. Meanwhile, the precision of CW-M and BCW-M are almost the same as that of BASE-M. The Dist indicator shows that the results’ diversity has been improved by CW-M and BCW-M.

For further analysis, we evaluate the decoding results of BASE-M with a beam size of 120. As is shown in Table 4, although the diff ratio increases up to 4 times, which is nearly equal to BCW-M with a beam size of 30, the precision and diversity drop significantly. What’s more, BASE-M has to spend more than 10 times of time to make it.

To conclude, BCW-M greatly enlarges the Diff ratio while maintaining a high level precision. It is fast and almost little extra time is consumed.

Our baseline model is a GBDT (Gradient Boosting Decision Tree) model (Ke et al., 2017) trained on a collection of human designed text similarity features. The features are listed as follows:

1. (1)

   Token level matching degree: max matching length, the proportion of matching and missing tokens, BM25, BLEU1 and BLEU2.

2. (2)

   Named entity similarity: whether the named entities in query and keyword are matched.

3. (3)

   Simple Approximate Bigram Kernel (Özateş et al., 2016) based on dependency parsing tree.

4. (4)

   Document class similarity: whether query and keyword belong to the same document class.

5. (5)

   Semantic similarity: DSSM (Huang et al., 2013) trained with query-keyword click-noclick pairs shown in the weblog, and Word2vec based cosine similarity (Mikolov et al., 2013).

6. (6)

   Translation likelihood: the BASE-M translation score which is calculated by $P(\emph{keyword}~{}|~{}\rm{query})$.

GBDT is also trained on $\mathcal{D}^{PI}_{train}$, and validated on $\mathcal{D}^{PI}_{dev}$. And the model hyperparameters are optimized by grid search. For evaluation, we use two metrics: the area under an ROC curve (AUC) and recall under 95% precision. Table 5 shows the models’ performances on $\mathcal{D}_{test}^{PI}$. To our surprise, BERT greatly exceeds GBDT’s performance. For the AUC indicator, BERT outperforms GBDT by 11.4 percentage points. Under the precision of 95%, BERT’s recall exceeds GBDT by 45 percentage points.

We also considered the models’ performances on $\mathcal{D}^{PG}_{1}$ generated by BCW-M, since our motivation is to remove bad cases in the translations. Here we use the previously human evaluated dataset $\mathcal{D}^{PG}_{1h}$ for testing. As is shown in Table 6, BERT achieves a recall of 91.3% under the precision of 95%, which also far exceeds the GBDT’s performance. (The difference of recall ratios in Table 6 and Table 5 comes from the difference of data distribution between $\mathcal{D}^{PG}_{1h}$ and $\mathcal{D}_{test}^{PI}$. In $\mathcal{D}^{PG}_{1h}$, positive examples account for 82.5% , while in $\mathcal{D}_{test}^{PI}$, positive examples account for 42.8%.)

BERT’s dramatic improvement might come from the following points: a) BERT has a super large parameter space in contrast to the simple semantic similarity features like Word2vec and DSSM. The huge capacity and abundant pretraining make BERT being able to learn a lot of external semantic similarity knowledge, which is especially useful to alleviate the vocabulary mismatch in paraphrase identification. b) The paraphrase relationship between two sentences is usually judged by the alignment of their tokens. To some extent, the multi-head attention mechanism in the Transformer might make soft alignments in multiple semantic spaces.

Our work has a close relationship with paraphrase generation and paraphrase identification. Most of the existing large scale paraphrasing datasets (MSCOCO, SNLI, etc.) are in English and high-quality Chinese dataset is extremely scarce in this domain. The most related dataset is a 24K sized dataset LCQMC (Liu et al., 2018). However, it focuses on general intent matching rather than paraphrasing. To promote the Chinese paraphrasing research, we decide to publish a large scale high-quality dataset containing 500K commercial synonymous short text pairs along with this paper. This dataset is produced in the following steps: A translation model trained with the BASE-M strategy is used to make unconstrained decoding for real-world frequent queries, where the prefix tree constraint is discarded. Then our discriminant model is used to filter out bad cases. Finally, some heuristic rules are devised to filter out trivial translations. Manual sampling evaluation shows that this dataset has a precision of 95%.

A real online A/B test experiment is deployed on Baidu’s commercial advertising system, where two fractions of search flow are sent to the experimental group and the control group independently. $\mathcal{D}_{old}$ is used as the Key-Value table in the control group and $\mathcal{D}_{old}+\Delta$ in the experimental group. We use 10,000,000 frequent queries, and the translation model is trained with BCW-M strategy.

For each group, $\#\{\rm{searches}\}$ is used to denote the total number of queries it received, $\#\{\rm{clicks}\}$ to denote the corresponding number of clicks, and $\rm{revenue}$ to denote the search company revenue. The following metrics are calculated independently for each group to evaluate the performance of our method.

$\bullet$ SHOW denotes the total number of ads shown to users.

$\bullet$ $\rm{CTR}=\frac{\#\{\rm{clicks}\}}{\#\{\rm{searches}\}}$, which denotes the average clicks received by the search engine.

$\bullet$ $\rm{ACP}=\frac{\sum\rm{price}}{\#\{\rm{clicks}\}}=\frac{\rm{revenue}}{\#\{\rm{clicks}\}}$, which denotes the average click price paid by the advertisers.

$\bullet$ $\rm{CPM}=\frac{\rm{revenue}}{\#\{\rm{searches}\}}\times 1000=\mathrm{CTR}\times\mathrm{ACP}\times 1000$, which denotes the average revenue received by the search engine for 1000 searches.

$\bullet$ Quality refers to the query-keyword synonym relationship. For each side of this A/B experiment, 600 query-keyword cases under the exact match type (excluding literally identical ones) are sampled from the system’s ad weblog and are sent for binary human evaluation. And the quality score is calculated as the proportion of the synonymous pairs.

Table 9 shows the relative improvements in these indicators. We can see that the incremental dataset $\Delta$ increases the CPM by 1.64%, which is a significant improvement for our revenue. We give our intuitive explanation from the demand-supply perspective. The sponsored search system aims to match query flows to the advertisers’ demands. Detecting more synonym relationships between queries and keywords helps to get more ads into the downstream auction phase. The ACP’s 0.62% growth shows the competition in the ad queue has been intensified. Finally, the number of shown ads increased by 0.8%, and the clicks increased by 1.02%. The growth in clicks and prices combined to bring about the final CPM growth. In the meanwhile, the human evaluation demonstrates that the ads’ relevance quality has not been deteriorated.