Domain-Constrained Advertising Keyword Generation
Hao Zhou Minlie Huang Yishun Mao Changlei Zhu Peng Shu Xiaoyan Zhu






  ^1Institute for Artificial Intelligence, 
State Key Lab of Intelligent Technology and Systems
  Beijing National Research Center for Information Science and Technology
  Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
  ^2Sogou Inc., Beijing, China

tuxchow@gmail.com;aihuang@tsinghua.edu.cn;ps-adwr@sogou-inc.com;
zhuchanglei@sogou-inc.com;shupeng203672@sogou-inc.com	;zxy-dcs@tsinghua.edu.cn


Corresponding author: Minlie Huang, aihuang@tsinghua.edu.cn.




Advertising (ad for short) keyword suggestion is important for sponsored search to improve online advertising and increase search revenue. There are two common challenges in this task. First, the keyword bidding problem: hot ad keywords are very expensive for most of the advertisers because more advertisers are bidding on more popular keywords, while unpopular keywords are difficult to discover. As a result, most ads have few chances to be presented to the users. Second, the inefficient ad impression issue: a large proportion of search queries, which are unpopular yet relevant to many ad keywords, have no ads presented on their search result pages. Existing retrieval-based or matching-based methods either deteriorate the bidding competition or are unable to suggest novel keywords to cover more queries, which leads to inefficient ad impressions. 

To address the above issues, this work investigates to use generative neural networks for keyword generation in sponsored search. Given a purchased keyword (a word sequence) as input, our model can generate a set of keywords that are not only relevant to the input but also satisfy the domain constraint which enforces that the domain category of a generated keyword is as expected. 
Furthermore, a reinforcement learning algorithm is proposed to adaptively utilize domain-specific information in keyword generation. Offline evaluation shows that the proposed model can generate keywords that are diverse, novel, relevant to the source keyword, and accordant with the domain constraint. Online evaluation shows that generative models can improve coverage (COV), click-through rate (CTR), and revenue per mille (RPM) substantially in sponsored search.






<ccs2012>
<concept>
<concept_id>10002951.10003260.10003272.10003273</concept_id>
<concept_desc>Information systems Sponsored search advertising</concept_desc>
<concept_significance>500</concept_significance>
</concept>
<concept>
<concept_id>10002951.10003317.10003325.10003328</concept_id>
<concept_desc>Information systems Query log analysis</concept_desc>
<concept_significance>300</concept_significance>
</concept>
<concept>
<concept_id>10002951.10003317.10003325.10003329</concept_id>
<concept_desc>Information systems Query suggestion</concept_desc>
<concept_significance>100</concept_significance>
</concept>
</ccs2012>


[500]Information systems Sponsored search advertising
[300]Information systems Query log analysis
[100]Information systems Query suggestion





Domain-Constrained Advertising Keyword Generation
    Hao Zhou^1, Minlie Huang^1,*, Yishun Mao^2, Changlei Zhu^2, Peng Shu^2, Xiaoyan Zhu^1
    December 30, 2023
=========================================================================================





§ INTRODUCTION






Advertising (ad for short) keyword suggestion is an important task for sponsored search which is one of the major types of online advertising and the major source of revenue for search companies. In sponsored search, a search engine first retrieves a set of advertisements whose keywords match a user issued query. It then ranks these advertising candidates according to an auction process by considering both the ad quality and the bid price of each ad <cit.>. Finally, the chosen advertisement is presented in a search result page. 
Therefore, ad keywords are vital for ads to gain access to the auction process and have the chance to be displayed on a search result page. 

However, there are two common challenges that should be addressed in sponsored search. 
The first one is the keyword bidding problem: due to the Matthew effect <cit.>, the hot ad keywords become too expensive for most of the advertisers, because too many advertisers bid on such keywords. As a result, many advertisers cannot survive in the auction process to get their desired ad impressions. As reported in  <cit.>, 55.3% advertisers have no ad impression, and 92.3% advertisers have no ad click at all, which is mainly caused by low bid price or improper keywords that they bid. The second issue is inefficient ad impressions: a substantial proportion of search queries, which are unpopular yet relevant to many ad keywords, have less competitive ads (46.6% search queries)
even no ads (41.0% search queries) on their search result pages as reported in <cit.>. 
Because of the two reasons, the expectation of advertisers is not satisfied and the revenue of search engines is also not optimized.

To address these problems, several prior studies have been conducted in keyword generation or suggestion <cit.>. Most of these studies adopt matching methods based on the word co-occurrence between ad keywords <cit.> and queries <cit.>. However, these methods tend to suggest popular keywords to advertisers, which will deteriorate the bidding competition. In addition, these approaches cannot suggest novel ad keywords which do not appear in the corpus.

Recently, deep learning technologies have been applied in many natural language tasks, such as machine translation <cit.>, ad keyword suggestion <cit.>, and query rewriting <cit.>. However, it's not trivial to adapt these neural networks to the ad keyword generation task, due to two major challenges. First, the generated ad keywords should be diversified and relevant to the original keywords to cover more user queries, which is not supported by existing neural models applied in keyword and query generation tasks. Second, the generated ad keywords should satisfy many constraints in sponsored search. For instance, to provide relevant yet unexplored ads for users, it is necessary to satisfy the domain constraint which means that the generated keywords should belong to the domain of the source keyword or several appropriate domains. For instance, a keyword in the health care domain should only match the keywords from the same domain to ensure the ad quality, while a keyword from the information domain could match those from various domains, such as entertainment and shopping, to cover diverse user queries.


In this paper, we investigate to use generative neural networks in the task of ad keyword generation. Given the purchased keyword as input, our generative model can suggest a set of keywords based on the semantics of the input keyword, as shown in Figure <ref>. The generated keywords are diverse and even completely novel (the blue keywords) from those in the dataset. This generative approach can address the aforementioned problems in two ways.
First, our model is able to generate diverse, novel keywords, instead of merely suggesting the existing popular keywords in the dataset, which can recommend keywords for advertisers to alleviate the keyword bidding problem and retrieve ads by keyword reformulation for sponsored search engines to address the inefficient ad impression issue.
Second, to improve the quality of the generated keywords, we incorporate the domain constraint in our model, which is a key factor considered in sponsored search to display ads. Through capturing the domain constraint, our model learns both semantic information and domain-specific information of ad keywords during training, and is consequently able to predict the proper domain category and generate the ad keyword based on the predicted category. 
In addition, our model uses reinforcement learning to strengthen the domain constraint in the generation process, which further improve the domain correlation and the keyword quality.

To summarize, this paper makes the following contributions:



  * This work investigates to use generative neural networks for keyword generation in sponsored search, which addresses the issues of keyword bidding and inefficient ad impressions.


  * We present a novel model that incorporates the domain constraint in ad keyword generation. The model is able to predict a suitable domain category and generate an ad keyword correspondingly. A reinforcement learning algorithm is devised to adaptively utilize domain-specific information in keyword generation, which further improves the domain consistency and the keyword quality.


  * We perform offline and online evaluation with the proposed model, and extensive results demonstrate that our model can generate diverse, novel, relevant, and domain-consistent keywords, and also improves the performance of sponsored search.






§ RELATED WORK





 §.§ Keyword Generation

A variety of methods has been proposed for generating and suggesting the keywords for advertisements, as ad keywords play a critical role in sponsored search.   <cit.> collected text-snippets from search engine given the keyword as input, and constructed them as a graph model to generate relevant keywords based on the similarity score.  <cit.> further improved the graph model, which computes the similarity score based on the retrieved documents.  <cit.> applied concept hierarchy to keyword generation, which suggests new keywords according to the concept information rather than the co-occurrence of the keywords itself.  <cit.> made use of the query-click graph to compute the keyword similarity for recommendation based on a random walk with absorbing states.  <cit.> introduced a generative approach, a monolingual statistical translation model, to generate bid phrases given the landing page, which performs significantly better than extraction-based methods. Recently due to the advances of deep learning, various neural network models have been applied to ad keyword suggestion.  <cit.> proposed several neural language models to learn low-dimensional, distributed representations of search queries based on context and content of the ad queries within a search session.  <cit.> applied an attention network which is stacked on top of a recurrent neural network (RNN) and learns to assign attention scores to words within a sequence (either a query or an ad).




 §.§ Query Generation


Another related research topic is query generation, which is widely studied and applied in organic search. It improves user experience by either expanding (reformulating) a user's query to improve retrieval performance, or providing suggestions through guessing the user intention, according to the user's behaviour pattern (query suggestion). Some previous studies adopt query logs to generate queries by handcrafted features such as click-through data <cit.>, session based co-occurrence <cit.> or query similarity <cit.>. Recently, artificial neural networks have been applied in query processing. A hierarchical recurrent encoder-decoder model <cit.> is introduced to query suggestion.  <cit.> proposed a learning to rewrite framework consisting of a candidate generating phase and a candidate ranking phase for query rewriting.  <cit.> use an RNN encoder-decoder to translate a natural language query into a keyword query. An attention based hierarchical neural query suggestion model that combines a session-level neural network and a user-level neural network to model the short- and long-term search history of a user is proposed by  <cit.>



 §.§ Generative Neural Network

Recently, generative neural networks have been applied in many natural language tasks, such as machine translation <cit.>, dialogue generation <cit.>, and query rewriting <cit.>.  <cit.> apply an end-to-end approach, a sequence to sequence (Seq2Seq) model, on machine translation tasks.  <cit.> further introduce the Seq2Seq model to dialogue generation tasks with novel attention mechanisms. Although the Seq2Seq model is capable of generating a sequence with a certain meaning, it isn't suitable for diversified sequence generation as argued in <cit.>. Therefore, latent variable based models are proposed to address the diversity and uncertainty problem.  <cit.> introduce latent variables to a hierarchical encoder-decoder neural network to explicitly model generative processes that possess multiple levels of variability.  <cit.> propose several conditional variational autoencoders to use emojis to control the emotion of the generated text.  <cit.> use latent variables to learn a distribution over potential conversational intents based on conditional variational autoencoders, that is able to generate diverse responses using only greedy decoders.




§ MODEL




 §.§ Background: Encoder-Attention-Decoder Framework


We first introduce a general encoder-attention-decoder framework based on sequence-to-sequence (Seq2Seq) learning <cit.>, which is a widely used generative neural network. The encoder and decoder of the Seq2Seq model <cit.> are implemented with GRU <cit.>.

The encoder represents an input sequence X = x_1x_2⋯ x_n with hidden representations H = h_1h_2⋯h_n[Throughout the paper, a bold character (e.g., h) denotes the vector representation of a variable (h).]
, which is briefly defined as below:

    h_t = 𝐆𝐑𝐔(h_t-1,e(x_t)),

where e(x_t) is the embedding of the word x_t, and GRU is gated recurrent unit <cit.>.

The decoder takes as input a context vector c_t and the embedding of a previously decoded word e(y_t-1), and updates its state s_t using another GRU:

    s_t = 𝐆𝐑𝐔(s_t-1,[c_t-1;e(y_t-1)]) ,

where [c_t-1;e(y_t-1)] is the concatenation of the two vectors, serving as input to the GRU network. 
The context vector c_t is designed to attend to the key information of the input sequence during decoding, which is a weighted sum of the encoder's hidden states as c_t-1=∑_k=1^n α_k^t-1h_k, and α_k^t-1 measures the relevance between state s_t-1 and hidden state h_k. Refer to  <cit.> for more details. 

Once the state vector s_t is obtained, the decoder generates a token by sampling from the generation distribution o_t computed from the decoder's state s_t  as follows: 

    y_t ∼o_t     =     P(y_t | y_1, y_2,⋯, y_t-1, c_t) ,
        =     softmax(𝐖_𝐨s_t) .









 §.§ Task Definition and Overview





Our problem is formulated as follows: Given a purchased ad keyword X = (x_1,x_2,⋯, x_n) (a word sequence)[Throughout the paper, a keyword refers to a word sequence, but not a single word.] 
and the corresponding domain category d_x obtained from a domain classifier, the goal is to predict a suitable target domain category d_y and generate a target keyword Y = (y_1,y_2,⋯, y_m) (a word sequence) that is coherent with the domain category d_y. Essentially, the model estimates the probability:
P(Y, d_y|X,d_x)=P(d_y|X,d_x)∏_t=1^mP(y_t|y_<t,d_y,X,d_x).
The domain categories are adopted from the sponsored search engine, which consists of k domain categories, such as beauty care, shopping, and entertainment.

Building upon the encoder-attention-decoder framework, we propose the Domain-Constrained Keyword Generator (DCKG) to generate diversified keywords with domain constraints using three mechanisms.
First, DCKG incorporates a latent variable sampled from a multivariate Gaussian distribution to generate diversified keywords. 
Second, a domain constraint network is proposed to facilitate generating domain-consistent keywords, which imposes more probability bias to domain-specific words.
Third, DCKG further optimizes the decoder to adjust the word generation distribution with reinforcement learning.
 

An overview of DCKG is presented in Figure <ref>, which illustrates the dataflow of DCKG in supervised learning, reinforcement learning, and inference processes. In supervised learning, the source keyword X = (x_1,x_2,⋯, x_n) and the target keyword Y = (y_1,y_2,⋯, y_m) are fed to the encoder to generate the hidden representations h^n_x and h^m_y, meanwhile, they are fed to the domain classifier to obtain their domain categories d_x and d_y respectively. The domain categories are further converted to the domain embeddings e(d_x) and e(d_y) to encode the domain-specific information in DCKG. Then, the latent variable z is sampled from a multivariate Gaussian distribution, which is determined by a recognition network that takes the hidden representations and the domain embeddings as input. Given the latent variable z, the hidden representation of source keyword h^n_x, and the domain embedding e(d_x), DCKG predicts the target keyword category d'_y and generate the domain-specific word score D(y_t |e(d'_y)). Finally, the decoder takes as input the context vector c_t generated by attention mechanism, the latent variable z, and the domain-conditioned word score D(y_t |e(d'_y)) to generate the target keyword Y.

During the inference process, DCKG has the input of only the source keyword X = (x_1,x_2,⋯, x_n) to generate a target keyword, conditioned on the latent variable sampled from a prior network which is approximated by the recognition network during supervised training. 

During the reinforcement learning process, DCKG first infers a set of keyword samples. Then, these samples are fed to the reward estimator to get their rewards, considering both domain-specific and semantic information. Finally, these rewards are applied to train our model using reinforcement learning to further improve the quality of generated keywords. 



 §.§ Supervised Learning





We will concentrate on introducing the latent variable network, the domain constraint network, and the decoder network, as shown in Figure <ref>.
The domain classifier is adopted from the sponsored search engine with parameters fixed during training. It generates a one-hot domain category distribution d_x for a keyword. A category is converted to a domain category embedding as follows:

    e(d_x) = 𝐕_𝐝d_x,

where 𝐕_𝐝 is a random initialized domain category embedding matrix which will be learned automatically.




  §.§.§ Latent Variable Network


Building upon the encoder-attention-decoder framework, our model introduces a latent variable to project ad keywords to a latent space. By this means, the model can generate diversified keywords conditioned on different latent variable sampled from the latent space. Specifically, we adopt the conditional variational autoencoder (CVAE)  <cit.> as the latent variable network, which is successfully applied in language generation tasks <cit.>. 

DCKG assumes the latent variable z follows a multivariate Gaussian distribution, z∼𝒩(μ, σ^2𝐈). The latent variable network consists of a prior network and a recognition network to model the semantic and domain-specific information of ad keyword in the latent space. 

In the training process, the recognition network takes as input the semantic representations h_x^n, h_y^m and the domain embeddings e(d_x), e(d_y) of the source keyword X and the target keyword Y, to approximate the true posterior distribution, as q_ϕ(z|h_x^n, e(d_x), h_y^m, e(d_y)) ∼𝒩(μ, σ^2𝐈). 

In the inference process, the prior network takes only the semantic representation h_x^n and the domain embedding e(d_x) of the source keyword X as input, to sample latent variables from the prior distribution, p_θ(z|h_x^n, e(d_x)) ∼𝒩(μ', σ'^2𝐈). The prior/posterior distribution can be parameterized by neural networks such as a multilayer perceptron (MLP) as follows:

    [ μ , σ^2 ]     =    𝐌𝐋𝐏(h_x^n, e(d_x), h_y^m, e(d_y)) , 
    [μ', σ'^2]     =    𝐌𝐋𝐏(h_x^n, e(d_x)) ,


To alleviate the inconsistency between the prior distribution and the posterior distribution, we add the KL divergence term to the loss function as follows:

    ℒ_1 = KL(q_ϕ(z|h_x^n, e(d_x), h_y^m, e(d_y))   p_θ(z|h_x^n, e(d_x)))





  §.§.§ Domain Constraint Network


The domain constraint network is designed to model the domain-specific information of ad keyword. The output of the network is further incorporated into the process of keyword generation to improve the quality of generated keywords in sponsored search. It plays two roles in our model: first, predicting an appropriate domain category given a latent variable; second, endowing the generated keyword with the target domain features.

Essentially, it predicts a domain category distribution conditioned on the latent variable sampled from a multivariate Gaussian distribution. Once the domain category distribution is determined, we can sample a target domain category by an argmax operation. However, argmax operation is non-differentiable and the training signal cannot be backpropagated. Inspired by the Gumbel-Max trick <cit.>, we adopt Gumbel-Softmax <cit.> as a differentiable substitute to generate a sample from the domain category distribution, which is defined as follows: 

    ϵ   ∼   𝐔(0, 1),
    g    =     -  log(-  log(ϵ)),
    o_d     =    𝐔_𝐝 𝐌𝐋𝐏(h_x^n, e(d_x), z),
    
        P_real(d'_y |h_x^n, e(d_x), z)     =     softmax(o_d),
    
        P_sample(d'_y |h_x^n, e(d_x), z)     =     softmax((o_d + g) / τ)

where ϵ is a sample from the uniform distribution 𝐔(0, 1), g is a sample from the Gumbel distribution 𝐆𝐮𝐦𝐛𝐞𝐥(0, 1), o_d is the logits computed by a MLP and a projection matrix 𝐔_𝐝∈ℝ^k × n; P_real(d'_y |h_x^n, e(d_x), z) is the real distribution of the predicted domain category used in the inference process, P_sample(d'_y |h_x^n, e(d_x), z) is the sample distribution used in the training process, and τ is a temperature used to adjust the shape of the sample distribution, which is annealed during training.

In supervised learning, we use the ground-truth domain category d_y of a keyword as the supervision signal in the loss function, such that the domain constraint network can predict the target domain category as expected, which is defined as follows:

    ℒ_2 = - 𝐄_q_ϕ(z|h_x^n, e(d_x), h_y^m, e(d_y) [log P_real(d'_y |h_x^n, e(d_x), z)]


Another task of the domain constraint network is to compute the domain-specific score of a generated word from the domain category distribution. The domain-specific score is added to the word generation distribution in the decoder to endow a generated keyword with desirable domain-specific features.
When the target domain category distribution is obtained, the target domain embedding can be computed as follows:

    e(d'_y) = 𝐕_𝐝P(d'_y |h_x^n, e(d_x), z),

where 𝐕_𝐝 is the domain category embedding matrix as introduced in Eq. <ref>. Subsequently, taking the target domain embedding as input, the domain word score is generated as follows:

    D(y_t |e(d'_y)) = 𝐖_𝐝 𝐌𝐋𝐏(e(d'_y)),

where D(y_t |e(d'_y)) is the domain-specific score of a generated word, which models the domain-specific features of a target keyword, 𝐖_𝐝 is the domain word embedding matrix.




  §.§.§ Decoder Network

The decoder of DCKG incorporates the latent variable and the domain word score to generate an ad keyword. Taking as input the latent variable z and the context vector c_t, the language model score of a generated word, which captures the semantic information in a keyword, is generated as follows: 

    s_t     =    𝐆𝐑𝐔(s_t-1,[c_t-1;z;e(y_t-1)]),
    
        S(y_t | y_<t, c_t, z)     =    𝐖_𝐬s_t,

where S(y_t | y_<t, c_t, z) is the language model score and 𝐖_𝐬 is the semantic word embedding matrix.

Finally, the decoder combines the language model score and the domain-specific score with a factor β and then normalizes the result to the word generation distribution, which is defined as follows:

    P(y_t | y_<t, c_t, z, e(d'_y)) =  softmax(S(y_t | y_<t, c_t, z) + β D(y_t | e(d'_y))),

where β is a domain constraint factor that controls the influence of the domain-specific information in the final word generation distribution, and is fixed to 1.0 during supervised training.
The generation loss of the decoder is given as below:

    ℒ_3 = - 𝐄_q_ϕ(z|h_x^n, e(d_x), h_y^m, e(d_y) [∑_t=1^mlog P(y_t | y_<t, c_t, z, e(d'_y))].




  §.§.§ Loss Function

The final loss to be minimized in supervised learning is the combination of the KL divergence term ℒ_1, the domain prediction loss ℒ_2, and the generation loss ℒ_3:

    ℒ =  max(δ, ℒ_1) + ℒ_2 + ℒ_3,

where the max operation and the factor δ are used to balance the KL divergence term and other loss function for better optimization, which is known as the free bits method in <cit.>.




 §.§ Reinforcement Learning



One major disadvantage of DCKG described above is the domain constraint factor β is fixed for all the keywords in any domain. However, the optimal factor should be determined by the semantic and domain-specific information of a keyword dynamically. A lower β value leads to keywords containing less domain-specific features, while a higher value results in keywords that are less fluent or relevant but contain more domain-specific features, as shown in Section <ref>. Therefore, we propose a reinforcement learning algorithm that is able to learn different β values for different keywords.



  §.§.§ Policy Network

To explore suitable β values for different keywords, we first define a value space ℬ which contains feasible β values. The main idea is to choose the best β value by a policy network to achieve the maximum reward with respect to the evaluation metrics, which can be implemented in three steps:
first, generate a set of keywords with different β values sampled from ℬ, given the same source keyword and latent variable; second, obtain the reward of each keyword using the reward estimator; third, update the policy network to choose the β value that leads to a maximum reward.
The policy network π_ψ(β|X, z), parameterized by ψ, is formally given below:

    o_b     =     [h_x^n; e(d_x); z; e(d'_y)], 
    π_ψ(β|X, z)     =     softmax(𝐖_𝐛 𝐌𝐋𝐏(o_b)),

where 𝐖_𝐛∈ℝ^b × n is a matrix projecting the input vector o_b to the action space ℬ. 

We use the REINFORCE algorithm <cit.>, a policy gradient method, to optimize the parameters by maximizing the expected reward of a generated keyword as follows:

    𝒥(ψ) = 𝔼_β∼π_ψ(β|X, z)[R(X, z, β)],

where R(X, z, β) is the normalized reward of a generated keyword. 
It is noteworthy that the policy network cannot be optimized through supervised learning, as the ground-truth β value is not observable. 




  §.§.§ Reward Estimator

The reward estimator is designed to provide a reward balancing the domain-specific information and the semantic information for a generated keyword. To estimate the reward, given the source keyword X, the latent variable z, and the target domain category d'_y as the same input, we first sample a set of β values {β_1,β_2,⋯,β_k}, and infer a set of keyword samples {Y_1,Y_2,⋯,Y_k} based on different β samples using the proposed model. Then, we use the domain classifier to predict the domain category d_y_i of each keyword Y_i. The agreement γ between d'_y and d_y_i is treated as an evaluation metric of the domain-specific information, which is defined as follows:

    γ_i = 
         
        1,     d'_y = d_y_i
    
        0,    d'_y≠ d_y_i

Subsequently, we use the generation probabilities computed by a language model and DCKG as an evaluation metric of the semantic information. Finally, the min-max normalization is applied to re-scale the rewards {r_1,r_2,⋯,r_k} for each β_i and Y_i. This process is defined as follows:

    r_i     =    γ_i (λ P_LM(Y_i) + (1-λ) P_DCKG(Y_i)),
    
        R_i(X, z, β_i)     =    r_i -  min({r_i})/ max({r_i}) -  min({r_i}),
 
where r_i is the reward for each β_i and Y_i, γ_i is the domain category agreement, P_LM and P_DCKG are the generation probabilities modeled by a language model and our DCKG respectively, λ∈ (0, 1) is a weight to balance these two generation probabilities. 

And the gradient is approximated using the likelihood ratio trick <cit.> as:

    ∇𝒥(ψ) = R(X, z, β) ∇ logπ_ψ(β|X, z),


This RL component encourages the model to choose for each keyword an optimal factor β that will lead to both higher domain category agreement and generation quality. Through reinforcement learning, we can further improve the quality of keywords generated by DCKG, resulting in more relevant, fluent, and domain-specific keywords.




§ EXPERIMENTS




 §.§ Dataset




We sampled about 40 million query logs from Sogou.com, and each sample consists of a <ad keyword, user query> pair. When the search engine retrieves ads based on their owners' purchased keywords, the ad keyword must be relevant to the user query.
Therefore, we treat user queries as target keywords to train our model. In other words, the input to our model is a purchased ad keyword (X), and the expected output is a user query (Y). 
We randomly sampled 10,000 pairs for validation and test. The statistics are presented in Table <ref>. 





 §.§ Implementation Details


Our model was implemented with Tensorflow <cit.>. The encoder and decoder do not share parameters and each has 4-layer GRU networks with 1024 hidden neurons in each layer. The word embedding size is set to 1,024. The vocabulary size is limited to 40,000. The MLP is implemented as a one-layer linear transformation with a tanh activation function. The parameters of the MLP and the embedding matrix share the same hidden size n = 1,024. All the parameters and embeddings are randomly initialized and tuned during end-to-end training. 

We adopted top k = 25 frequent domain categories produced by the domain classifier, which is a key component used in the sponsored search engine. The domain classifier is a support vector machine <cit.> trained on a large human-labeled corpus.
The accuracy of the 25-class classification is 92.65%. 
The temperature τ is set to  3.0 at the beginning, and is annealed to 0.1 during supervised learning. The factor δ is set to 5.0. The value space ℬ consists of b = 21 values in the range [0, 5] with an interval of 0.25. The generation probability factor λ is set to 0.9.

Our model is trained in two stages: supervised learning is first used to model the semantic information and the domain-specific information of keywords; reinforcement learning is then used to adaptively utilize domain-specific information in the generation process. 
We used the Adam optimizer with a mini-batch size of 100. The learning rate is 0.0001 for supervised learning and 0.00001 for reinforcement learning. The models were run at most 10 epochs for supervised learning and 2 epochs for reinforcement learning. The training process of each model took about a week on a Tesla V100 GPU machine. 








 §.§ Baselines


As aforementioned, this paper is the first work to address the domain constraint factor in ad keyword generation. We did not find closely-related baselines in the literature. 

Although retrieval-based approaches proposed in previous studies are able to recommend relevant keywords from the dataset, these methods cannot generate novel keywords and thus deteriorate the bidding competition problem. Furthermore, as the dataset consists of <ad keyword, user query> pairs, retrieval-based methods can only suggest keywords which are already covered by the search engine. Consequently, the coverage and revenue of the search engine cannot be improved more than those methods which can generate novel keywords. Due to these reasons, we didn't consider retrieval-based methods as our baselines.

Nevertheless, we chose two suitable generative models as our baselines: 


  * A modified Seq2Seq model <cit.>. First, the target domain category is predicted by the domain constraint network and is embedded into a category vector. Then, the vector serves as input to each decoding position.



  * A modified CVAE model <cit.> considering the domain constraint information, which is implemented similarly to DCKG but without reinforcement learning.





 §.§ Automatic Evaluation




We evaluated the quality of keywords generated by different models using several automatic metrics. 
To evaluate the performance in metrics except for perplexity[We generated the ground-truth target keyword using greedy search for calculating the perplexity.], we generated 10 keywords for each purchased ad keyword using different models (for DCKG and CVAE, keywords were generated conditioned on 10 sampled latent variables using greedy search; for Seq2Seq, keywords were inferred using beam search with beam size = 10).
Due to the uncertainty caused by the latent variable in our model and the CVAE baseline, we repeatedly tested all the models for 10 times. The averaged performance, the standard deviation, and the significance test results were reported for these models [For the deterministic Seq2Seq model, we tested 10 models which achieve the top 10 performance in the validation set. These models differ in different training steps.]. 
The bold number indicates the best performing model, which outperforms all other models significantly (2-tailed t-test, p-value < 0.01). 




  §.§.§ Metrics



  * Perplexity: We adopted perplexity to evaluate the generation quality with respect to grammar and fluency. The perplexity here is computed by the generation distribution in the models themselves. 

  * Perplexity_LM: We trained a language model on our dataset, and used this language model to calculate the perplexity of keywords generated by different models.

  * Accuracy: To evaluate whether the model can generate domain-constrained keywords, we adopted the domain accuracy as the agreement between the expected domain category (as predicted by the model, see Eq. <ref>) and the domain category of a generated keyword predicted by the domain classifier. 

  * Distinct-n: We calculated the proportion of distinct n-grams to all the n-grams in generated keywords to evaluate the diversity.

  * Novelty_ALL/AD-n: To evaluate the novelty of the generated keywords, we counted the distinct n-grams that don't appear in all the corpus (ALL) or not in the purchased ad keyword set (AD). Novelty_ALL-n means the percentage of totally novel n-grams that have not been observed in the corpus. 




  §.§.§ Results


The results are shown in Table <ref> and Table <ref>, from which we made the following observations:

First, DCKG obtains the best performance in domain accuracy, distinct, and novelty. The improvement in domain accuracy shows that our model can enhance the domain consistency of the generated keywords, thanks to the reward we applied in reinforcement learning.
DCKG can generate more diverse and novel keywords than baselines, which can be attributed to the latent variable network we adopted and the domain constraint we considered. Our model has better perplexity and perplexity_LM than Seq2Seq but slightly worse than CVAE, because DCKG is tuned to satisfy the domain constraint more by reinforcement learning than fit to the language generation probability. Nevertheless, the disadvantage in perplexity and perplexity_LM harms the grammaticality of the generated keywords but less influences the overall performance, as shown in the following experiments. 

Second, the novelty scores indicate that our model can generate more novel n-grams than the baselines. The generative models can generate novel keywords which have not been purchased yet so that the bidding competition problem can be alleviated as aforementioned. For retrieval-based methods, the Novelty_ALL scores, which count n-grams that are never observed in the corpus, will be zero since they can only suggest existing keywords from the corpus.







  §.§.§ Effect of β


In order to investigate the influence of the domain constraint factor β in DCKG, we tested the performance of DCKG with different fixed β∈ℬ. The results are shown in Figure <ref>. As we can see, the domain accuracy of DCKG improves continuously with the increase of β (the green curve), indicating that β is critical to satisfying the domain constraint in keyword generation because larger β applies more domain-specific information in keyword generation. 
DCKG achieves the best performance in perplexity and perplexity_LM with β = 1 since this value is the default β value during supervised learning. However, when β becomes larger, DCKG performs worse in the perplexity metrics.
It is thus important to balance the domain constraint and the language generation quality. Therefore, we apply reinforcement learning to find an optimal β for different instances dynamically. 

It is noteworthy that DCKG with the dynamically determined β outperforms DCKG with the manually adjusted β. For example, although the performance of DCKG in perplexity and perplexity_LM is approximately equal to DCKG with the fixed β = 1.5, the domain accuracy of DCKG outperforms DCKG with the fixed β = 1.5 (84.61 vs. 82.49). Moreover, the novelty score and the diversity score of DCKG are also better than DCKG with the fixed β = 1.5, for instance, the Distinct-4 of DCKG is better than DCKG with any fixed β∈ℬ (91.26 vs. 91.20), indicating that the domain constraint can further improve the quality of generated keywords.





 §.§ Manual Evaluation




In manual evaluation, we tested whether the generated keywords are relevant to the source keyword and consistent with the expected domains, such that they are suitable to be suggested to advertisers. 
We manually evaluated the relevance and the grammaticality of keywords generated by different models. We randomly sampled 100 purchased ad keywords from the test set, and generated 10 keywords for each purchased ad keyword using different models as in automatic evaluation.
Five experienced annotators were recruited to judge the relevance (Relevant/Irrelevant) of 3000 pairs of generated and purchased keywords. The grammaticality of a generated keyword is also considered during annotation, as bad grammaticality leads to the ambiguity in the meaning and thus results in irrelevance rating. We used majority voting to obtain the final label of annotation. 
Moreover, as domain accuracy is critical to measuring how well the models satisfy domain constraint, we also reported the automatic measure in these tables. 
The bold number indicates the best performing model, which outperforms all other models significantly (2-tailed sign test, p-value < 0.05). 




  §.§.§ Metrics



  * Precision (P): Precision is defined as the ratio of the number of relevant
keywords generated to the number of total keywords generated. 


  * Recall (R): Recall is the proportion of relevant
keywords generated by a model to all the relevant keywords pooled from all models' results. Similar to <cit.>, the relevant keywords from all the models are pooled together and are treated as the entire relevant set. This metric is useful to compare the ability to cover the potential relevant keywords.


  * Accuracy (A): Similar to the preceding section, this metric is the agreement between the expected domain category, predicted by the model, and the domain category of a generated keyword, predicted by the domain classifier (SVM). 


  * F-measures: We adopted four F-measures to quantify the overall performance including F(PR), F(PA), F(RA), and F(PRA). Each F-measure is defined as the harmonic mean of all factors, where P/R/A indicate precision/recall/accuracy respectively.













  §.§.§ Annotation Statistics

We calculated the statistics to measure inter-rater agreement.  
For relevance rating, the percentage of the pairs that all 5 judges gave the same label is 85.1%, the percentage of the pairs that 4 judges gave the same label (4/5 agreement) amounts to 8.8%, and the percentage for 3/5 agreement is 6.1%.
We further computed the free-marginal kappa <cit.> to measure inter-rater consistency. The free-marginal kappa is 0.856, indicating adequate inter-rater agreement.






  §.§.§ Results

The results are shown in Table <ref>. As it can be seen, DCKG obtains the best performance in all the metrics, indicating that our model can generate relevant and grammatical keywords. The best precision shows that more relevant keywords are generated by DCKG. Our model also achieves the best recall, indicating that DCKG is able to cover more potential user queries than other models.
In addition, DCKG outperforms other models in domain accuracy, indicating that incorporating the domain constraint appropriately can enhance the quality of generated keywords.
Moreover, DCKG ranks highest for all the four F-measures, showing that our model is superior considering all these factors.





 §.§ Online Evaluation


In online evaluation, we examined whether the sponsored search engine can retrieve and present more relevant ads using the keywords generated by our model. We applied the generative models in the keyword reformulation method to facilitate the ad retrieval process of sponsored search (see Figure <ref>). Specifically, we collected 5 million purchased ad keywords, and then used each model to generate 10 keywords for each purchased keyword. We used these generated keywords as the reformulated keywords to retrieve original ads. 
The original keyword reformulation method, based on handcrafted rules and templates, is one of the retrieval methods in the ad retrieval process of the sponsored search engine, which retrieves about 2% unique ads. We added the keywords generated by our models to the keyword reformulation method of the sponsored search engine, which is called the enhanced keyword reformulation method.
To make a fair comparison, the enhanced keyword reformulation methods of all models run ten days in our A/B online test system on Sogou.com, where 10% user queries are selected into the test system. We compared the performance of the enhanced keyword reformulation method with the original keyword reformulation method, and reported the relative gain in percentage for all the metrics as the final result. The bold number indicates the best performing model, which outperforms all other models significantly (2-tailed t-test, p-value < 0.05). 



  §.§.§ Metrics



  * Coverage (COV): Coverage is defined as the percentage of web pages that contain at least one ad.

  * Click-through rate (CTR): Click-through rate is the ratio of page views that lead to a click to the total number of page views.

  * Revenue per mille (RPM): Revenue per mille is the revenue of the search engine per one thousand page views. 




  §.§.§ Results

The results are shown in Table <ref>. As it can be seen, DCKG obtains the best performance in all the metrics. Results show that keywords generated by DCKG can cover more user queries than those by other models. The click-through rate scores indicate that the new ads which are matched with ad keywords from DCKG lead to more user clicks, because the generated keywords (user queries) are of higher quality and more relevant. The revenue is improved because the click-through rate increases, which verifies that our model can contribute more ad impressions in sponsored search.

Although the Seq2Seq model can also retrieve more ads, the improvements in all metrics are the lowest in the three models, as the diversity and the quality of the generated keywords are lower than ours. CVAE outperforms Seq2Seq because CVAE is able to model diversity with latent variables. However, as CVAE incorporate the domain constraint in a fixed way, it cannot balance the semantic information and the domain-specific information in the generation process. DCKG further improves the diversity and the quality of generated keywords by tuning the β factor dynamically with reinforcement learning. The results of online evaluation agree with those of automatic evaluation, indicating that DCKG can generate the most diverse, novel and domain consistent keywords among the three models. 





 §.§ Case Study


UTF8gbsn







Several sample keywords generated by different models are shown in Table <ref>. We can see that keywords generated by Seq2Seq have lower diversity than other models since it tends to generate keywords with the same prefix in similar meanings using beam search <cit.>, such as the 3rd and 4th keywords generated by Seq2Seq. 
Moreover, it can only predict one target domain category since it is a deterministic model, which cannot handle the task of generating different keywords from multi-domain categories. 

In comparison, CVAE and DCKG are able to predict multiple domain categories as well as generate diverse keywords according to these domain categories. However, in CVAE, the domain constraint is not addressed properly in some cases, as it takes a fixed way to combine the domain-specific information with the semantic information. For example, although the 6th generated keyword, “what meat will lead to fat if I eat during weight loss”, is relevant to the source keyword, it is inconsistent with its domain category “information” since the domain-specific information is less considered than the semantic information in this case. By contrast, DCKG is able to choose a proper domain constraint factor to balance the domain-specific information and the semantic information for each instance. Hence, the generated keywords are both relevant to the source keyword and consistent with their domain categories.

In order to validate the influence of the domain constraint factor β in the generated keywords, we presented several sample keywords generated by DCKG with different β values in Table <ref>. Take the 6th keyword in Table <ref> as an example. Given the source keywords “weight loss weight loss” and its domain category “beauty care”, our model predicts a target domain category “information”, and then generates keywords with different β values while other parameters are fixed. 

As shown in Table <ref>, when β equals to 0.00, the target keyword belongs to the source domain category “beauty care” but violates the target domain category “information” since the keyword is generated regardless of the domain-specific information. 
With the increase of β, the domain accuracy improves since more domain-specific information is involved in the model, but the relevance decreases in some instances because the model faces with the compatibility of controlling semantic and domain-specific information. For example, the keywords generated when β=2.00/3.00, are both consistent to the target domain category and relevant to the source keyword. However, when β increases to 4.00/5.00, the generated keywords are not relevant to the source keyword anymore, as a high β value will harm the quality of generated keywords severely. 





§ CONCLUSION

In this paper, we investigate the use of generative neural networks for ad keyword generation. We propose a Domain-Constrained Keyword Generator (DCKG) to generate diversified and domain-consistent keywords. 
A latent variable network is designed to model the diversity and a domain constraint network to satisfy the domain constraint in supervised learning. 
To further leverage the domain-specific information in keyword generation, we propose a reinforcement learning algorithm to adaptively utilize domain-specific information in keyword generation. Offline evaluation shows that the proposed model can generate keywords that are diverse, novel, relevant to the source keyword, and accordant with the domain constraint. Online evaluation shows that generative models can improve coverage (COV), click-through rate (CTR), and revenue per mille (RPM) substantially in sponsored search.



§ ACKNOWLEDGMENTS

This work was jointly supported by the National Science Foundation of China  (Grant No.61876096/61332007), and
the National Key R&D Program of China (Grant No. 2018YFC0830200).

ACM-Reference-Format


