Generating Recommendation Evidence Using Translation Model

1 Introduction

Over the past few years, major commercial web search engines have enriched and improved users' experiences of information retrieval by presenting recommended entities related to their search queries besides the regular search results. Figure 1 shows an example of Baidu (www.baidu.com) web search engine's recommendation results of the query "Obama". On the panel, a ranked list of celebrities related to "Obama" is presented, providing users a quick access to entities closely attached to their interests and enhance their information discovery experiences.

Related entity recommendations can increase users' engagements by evoking their interests to these entities and thereby extending their search sessions [Aggarwal et al., 2015]. However, if users have no background knowledge on a recommended entity, they may possibly be confused, and leave without exploring these entities. In order to help users to quickly understand whether, and why, the entities can meet their interests, it is important to provide evidences on the recommended entities. As depicted in Figure 1, the phrase under each entity, which we refer to as the "recommendation evidence" ( "evidence" for short later in this paper), is presented, providing users a quick overview of the representative features of each entity. 1 Using the third recommended entity "Oh Han Ma" as an example, its evidence is "Obama's Korean name". Without this evidence, users may get confused and think it is an unrelated recommendation, because this entity is unfamiliar. Therefore, presenting evidence for recommendation can help in building and promoting trust between the users and the recommendation system [Voskarides et al., 2015]. In this paper, we will focus on generating evidences from sentences. Selecting appropriate evidences for each recommended entity related to a search query will be left for future work.

⇤Corresponding author.

Although there is some previous work on entity recommendation systems, e.g., [Blanco et al., 2013; Yu et al., 2014; Bi et al., 2015], the problem of providing evidence for recommendation has not been well addressed. To the best of our knowledge, little research has been published on automatically generating evidences for recommended entities. Although extracting evidences from structured data is a feasible way, the coverage is insufficient. Take "Obama" as an example, the disambiguation texts of entities inWikipedia, e.g., Obama 2 , providing useful and key information to help disambiguate different mentions of an entity, can be used as evidences for recommendation. For example, from the following disambiguation texts of Obama (EXAMPLE 1 and 2), we could extract "the highest point in Antigua and Barbuda" as an evidence of the entity "Mount Obama" and "the 44th and current President of the United States" for "Barack Obama". But the method does not work for the entity "Oh Han Ma" since no such information is available in Wikipedia.

1 We translate both Chinese entities and evidences into English to make it more understandable.

2 https://en.wikipedia.org/wiki/Obama (disambiguation)

EXAMPLE 1. Barack Obama (born 1961) is the 44th and current President of the United States

EXAMPLE 2. Mount Obama, the highest point in Antigua and Barbuda

We also investigated the largest Chinese online encyclopedia Baidu Baike 3 , to examine the coverage of disambiguation texts in Chinese. Results show that only 3.4% of entities in Wikipedia and 5.9% of entities in Baike have such disambiguation information, which shows that directly extracting evidences from such online resources is not sufficient. In order to provide users with consistent user experiences, it is important to generate evidences for all recommended entities.

In this paper, we propose to use statistical machine translation (SMT) techniques to generate evidences for the entities recommended in web search. We train a translation model on a query-title aligned corpus, derived from clickthrough data of Baidu web search engine. Two additional feature functions are introduced in the translation model to produce attractive evidences.

The major contributions of this paper are summarized as follows:

1. We study the novel issue of evidence generation (EG) for entity recommendation.
2. We propose an SMT based approach to generate evidence candidates for entities, and introduce two additional feature functions in the model to produce attractive evidences. The experimental results show that our approach is very promising.
3. Large-scale monolingual parallel data is essential for training EG models. We propose an efficient method to mine aligned sentence-evidence pairs from the clickthrough data of a search engine.

2 Problem Statement

In this paper, we generate recommendation evidences for an entity from sentences that contain the entity. In order to provide users a quick overview of the representative features of a given entity, we define entity evidence as follows: (1) the evidence must correctly describe the entity; (2) the evidence must be concise so as to be presented in a limited space 4 ; (3) the evidence should be informative and attractive so as to attract users to browse and click the recommended entity.

From the definition, we can see that the EG task requires to shorten a sentence by deleting some less important words and/or replacing some phrases with other more concise and attractive phrases, and organize the generated evidences in an accurate, fluent, and catchy manner. An example is depicted in Figure 2.

3 http://baike.baidu.com/

4 In this paper, we constrain that the evidence should be no longer than 10 Chinese characters.

Given a sentence s, our task is to generate a ranked list of evidences E = ¶e1↪ e2↪ · · · ↪ ek♦ for s.

Figure 3 shows an overview of our method. The EG method contains two components, i.e., sentence preprocessing and evidence generation. Sentence preprocessing mainly includes Chinese word segmentation [Peng et al., 2004], POS tagging [Gimenez and Marquez, 2004] and dependency parsing [McDonald et al., 2006] for the input sentences, as POS tags and dependency information are necessary for the following stages. Evidence generation (described in Section 3.2) is designed to generate evidences for the input sentences with a statistical machine translation model. The evidence generation model needs three data sources. Firstly, sentenceevidence parallel corpus (S-E Pairs) is used to train the "translation" model and language model (described in Section 3.1 and 3.2). Furthermore, headlines of news articles (Headlines) and manually-labeled evidences are used to train an attraction model (described in Section 3.2 and 3.3) to increase the attraction of generated evidences.

3 Evidence GenerationModel

Despite the similarity between evidence generation (EG) and machine translation (MT), the statistical model used in SMT cannot be directly applied in EG, since there are some clear differences between them: (1) the bilingual parallel data for SMT are easy to collect. In contrast, the large monolingual parallel data for EG are difficult to acquire; (2) SMT has a unique purpose, i.e., producing high-quality translations for the inputs. In comparison, EG aims at generating attractive and concise descriptions as evidences; (3) In SMT, there is not any limitation for the length of translations, whereas in EG, the length of evidence is strictly limited due to the layout limitation.

3.1 Sentence-evidence Parallel Data

To train the EG model, we need large-scale monolingual parallel data of sentence-evidence aligned pairs. Take the entity "Ilham Anas" in Figure 1 as an example, Table 1 shows several evidences (E) of this entity and their aligned sentences (S) from which the evidences are generated.

S: Ilham Anas is Indonesia's Obama look alike E: the Obama's Indonesian look-alike

S: Ilham Anas shares a striking resemblance with US President Barack Obama E: a striking resemblance to Obama

Table 2: Performance of evidence classifier.

From the examples shown in Table 1, we can see that the evidences and sentences may use different language styles and vocabularies, so the generation model is required to bridge the gap between them. We view the title-query pairs derived from the clickthrough data of a search engine as sentence-evidence pairs, and use this data to construct the training corpus for evidence generation model, the reasons are as follows:

1. The queries and evidences have similar language styles and vocabularies, because the perplexity result of the language model trained on 12 million random queries tested on 200,000 sample evidences is 578, which indicates high language similarity between them according to the metric described in [Gao et al., 2010].
2. A query is parallel to the titles of documents clicked on for that query [Gao et al., 2010], thus the query-title aligned corpus is a good source of monolingual parallel data.

The task of evidence identification from query logs can be viewed as a binary classification problem of distinguishing evidence from non-evidence. To construct the data for training the classifier, we collected the disambiguation texts of entities from Baidu Baike as seed evidences, and got 488,001 evidences in this way. To enrich the evidence data, we used pattern based method [Muslea, 1999] to extract more evidences from the main texts in Baidu Baike using the pattern "<entity> is <evidence>". Altogether, we collected 1,040,897 evidences as positive instances. We then extracted equivalently random queries as negative instances with the same length range as the positive instances. To construct the test set for the classifier, we randomly sampled 10% of the data from positive and negative instances separately, and the 90% of data were left for training.

Maximum Entropy is selected as the classification model because it is an effective technique for text classification [Nigam et al., 1999]. The features used for training the evidence classifier are unigrams (U), bigrams (B), POS tagging (P) and dependency parsing (D). Table 2 shows the performance of the evidence classifier.

To extract candidate sentence-evidence pairs, we used the evidence classifier to identify evidences from queries on a sixmonths clickthrough data of Baidu web search engine. To enrich the data, each title was segmented into multiple sub-titles using punctuations, and formed multiple title-query pairs. Finally, similar to [Quirk et al., 2004], the pairs were filtered if they met any of the following rules:

• ÷ Title and query have no word overlapping;
• ÷ Title and query are identical;
• ÷ The length 5 of a query is greater than 10 or less than 6;
• ÷ Title-query pairs with significantly different lengths (the shorter is less than two-thirds the length of the longer).

A total of 55,149,076 title-query aligned pairs were obtained, which we used as sentence-evidence parallel corpus to train our evidence generation model. Mean edit distance [Levenshtein, 1966] over Chinese characters was 5.7; mean lengths of sentence and evidence were 10.7 and 7.9, respectively.

3.2 Evidence GenerationModel

Our EGmodel contains four sub-models: a translation model, a language model, a length model, and an attraction model, which control the adequacy, fluency, length, and attraction of the evidences, respectively. 6

TranslationModel (M1)

Evidence generation is a decoding process. Similar to [Zhao et al., 2009], the input sentence s is first segmented into a sequence of units ¯ sl1 , which are then "translated" to a sequence of units ¯ el1 . Let (¯ si↪ ¯ ei) be a pair of translation units, their translation likelihood is computed using a score function φtm(¯ si↪ ¯ ei). Thus the translation score between s and e is decomposed into:

where λtm is the weight for the translation model. Actually, it is defined similarly to the translation model in SMT [Koehn et al., 2003].

Language Model (M2)

We use a tri-gram language model in this work. The language model based score for the evidence e is computed as:

where J is the number of words of e, ej is the j-th word of e, and λlm is the weight for the language model.

LengthModel (M3)

We use a length-penalty function to generate short evidences whenever possible. To meet the requirement that the evidence should be less than 10 Chinese characters, the length score for the evidence e is computed as:

where N is the number of Chinese characters of e.

5 Throughout this paper the length of sentences, evidences, and queries is assumed to be the number of Chinese characters in them.

6 The EG model applies monotone decoding, which does not contain a reordering sub-model that is often used in SMT.

AttractionModel (M4)

The attraction model prefers evidences that can better achieve the requirements of entity recommendation described in Section 2. After analyzing a set of manually labeled entity evidences, we found that the attraction of e depends on three aspects: the vocabulary used, the language style, and sentence structure. We use two sub-models to capture these aspects. The first one is a special language model trained on headlines of news articles (M4-1 for short), which tries to generate catchy and interesting evidences with similar vocabularies and styles to headlines. The motivation is that news editors usually try their best to use the attractive expressions to write the headlines. The second one is a sentence structure model trained on human annotated evidences (M4-2), which tries to generate evidences with popular syntax styles that users might prefer. Hence the attraction model is decomposed into:

where phl(e) is the headline language model and pss(e) is the sentence structure model. phl(e) is similar to plm(e), but trained on headlines. pss(e) is computed as:

where Tx is the dependency tree of sentence x, ti is the human annotated evidences, and K(·↪ ·) is the dependency tree kernels described in [Culotta and Sorensen, 2004], which measures the structure similarity between sentences. We combine the four sub-models based on a log-linear framework and get the EG model:

3.3 Resources for Training AttractionModel

To train the attraction model, we need data of headlines and human annotated evidences. We firstly extracted all headlines from three major Chinese news Websites 7 , then we ranked the headlines by the click count in the query logs, and finally top ranked 10 million headlines were remained. To guide the EG model to generate evidences with similar structures to human composed evidences, we need a set of human annotated evidences of high-quality. We used crowdsourcing method [Hsueh et al., 2009] to collect this set. We asked annotators to compose evidences for each sentence, then asked 5 different annotators to vote each evidence with two options: acceptable or not, finally an evidence voted by more than 4 annotators out of 5 as acceptable were kept. A total of 104,775 excellent evidences were obtained.

3.4 Parameter Estimation

To estimate parameters λtm↪ λlm↪ λlf ↪ λhl, and λss, we adopt the approach of minimum error rate training (MERT) that is popular in SMT [Och, 2003]. In SMT, the optimization objective function in MERT is usually BLEU [Papineni et al., 2002], which requires human references. To provide human annotated evidences as references for each sentence, we asked 5 annotators to compose evidences for each sentence separately. Finally, we invited other 3 judges to vote each evidence, and evidences with at least two agreements were kept. A total of 7,822 sentences with human annotated evidences were obtained, and only the first evidence of a sentence was used as the reference. We estimate parameters for each model separately. The parameters that result in the highest BLEU score on the development set were finally selected.

7 (1) http://news.qq.com/, (2) http://news.sina.com.cn/, and (3) http://news.sohu.com/

4 Experimental Setup

We use the method proposed in [Che et al., 2015] as baseline, which used a CRF model to compress sentences by dropping certain less important words. For the EG method proposed in this paper, we have trained three models. The first EG model combines M1, M2, and M3, which is used for evaluating the performance of default features (named as EG-D). The second EG model combines M1, M2, M3, and M4-1, which is used to examine if headlines could help increase the performance (named as EG-H). The third considers all sub-models M1, M2, M3, and M4 (named as EG-F).

4.1 Experimental Data

Our method is not restricted in domain or language, since the translation models and features employed here are language independent. Thus sentences in different languages or containing entities of different categories can be used for testing. In this paper, all EG models are trained on a Chinese corpus. Furthermore, to evaluate if our method can generate evidences for sentences of different lengths and categories, in our experiments, we manually select 1,000 Chinese sentences as a test set to carry out the evaluation according to the following rules: (1) the sentence contains descriptive information about an entity in a randomly selected entity set, and (2) the length of a sentence is in the range 5 to 20. The average length of the sentences is 11.8. Finally, to check if our method can generate evidences for different types of entities, we classify the entities described by the collected sentences. After classification, 104 categories in total are obtained. Table 3 shows the percentage of the classification results, in which, the top 6 categories are listed, and all the other categories are combined into "Others".

4.2 EvaluationMetrics

The evaluation metrics for EG are similar to the human evaluation for MT [Callison-Burch et al., 2007]. The generated evidences are manually evaluated based on three criteria, i.e., adequacy, fluency, and attraction, each of which has three scales from 1 to 3. Here is a brief description of the different scales for the criteria:

• Adequacy 1: The meaning is obviously changed.
• 2: The meaning is generally preserved.

Fluency

• 3: The meaning is completely preserved.
• 1: The evidence e is incomprehensible.
• 2: e is comprehensible.
• 3: e is a flawless phrase.
• Attraction 1: The attraction is obviously decreased.
• 2: The attraction is generally retained.

• 3: The attraction is increased.

To make the attraction understood consistently by raters in practice, we define attraction in detail by using three aspects: the evidence should be more concise, informative, and/or interesting than the sentence.

BLEU is widely used for automatic evaluation in MT. It measures the similarity between a translation and human references. To further assess the quality of the generated evidences, we compute BLEU scores of each method, and 3 human references for each test sentence are provided.

5 Results and Analysis

We use the baseline and the three EG models to generate evidences. Results show that the percentages of test sentences that can be generated ("coverage" for short later in this paper) are 99.9%, 88.8%, 87.3%, and 87.3% for baseline, EGD, EG-H, and EG-F, respectively. The coverage of baseline is much higher, because it is easy to delete words to match the required length without considering other constraints of evidence. The reason why the last two coverages are lower than the second one is that, after adding the sub-models into the EG-D, several extremely long sentences cannot find properly short phrase replacements or do phrase deletion so that the method fails to generate evidences within maximum length allowed. It indicates that generating evidences for extremely long sentences is more difficult than the shorter ones. In our experiments, the first evidence generated by each model is used for evaluation.

5.1 Evaluation

We ask two raters to label the evidences generated by baseline and the three models based on the criteria defined in Section 4.2. The labeling results averaged between two raters are shown in Table 5. We can see that for adequacy, fluency, and attraction, the EG-F model gets the highest scores. The percentages of label "3" are 50.9%, 69.9% for adequacy and fluency, which is promising for our EG task. But the percentage of label "3" for attraction is 17.6%, the main reason is that it is difficult to increase much attraction due to the strict length limitation of EG task. This motivates us to further improve the attraction model in the future work.

We compute the kappa statistic between the raters. Kappa is defined as K = P(A)-P(E) 1-P(E) [Carletta, 1996], where P(A)

Table 4: The generated evidences of some sentences. \ indicates that the evidence has grammatical errors.

is the proportion of times that the labels agree, and P(E) is the proportion of times that they may agree by chance. We define P(E)=1/3, as the labeling is based on three point scales. The results show that the kappa statistics for adequacy, fluency, and attraction are 0.6598, 0.6833, and 0.6763, respectively, which indicates a substantial agreement (K: 0.61-0.8) according to [Landis and Koch, 1977].

Table 4 shows an example of the generated evidences. Evidences E of baseline, EG-D, EG-H, and EG-F are listed with their source sentences S.

5.2 Comparison

We tune the parameters for the three EG models using the development data as described in Section 3.4 and evaluate them with the test data as described in Section 4.1.

As can be seen from the test results in Table 5, the EGH and EG-F models significantly outperform baseline and EG-D in both human and automated evaluation. Although the coverage of EG-F (87.3%) is lower compared to baseline (99.9%), the usability of EG-F is much higher than that of baseline: (1) the BLEU score is improved by 15.01 (from 53.63 to 68.64), and (2) the overall improvements of labels "2" and "3" are higher for adequacy, fluency, and attraction. Compared with baseline, the EG-F achieves a better balance between coverage and usability. The baseline is not readily applicable to the application of entity recommendation due to its low usability. The overall percentages of labels "2" and "3" of EG-D, baseline, EG-H, and EG-F, in all three evaluation metrics, are largely consistent with movements in BLEU scores, which verifies that BLEU tracks human evaluation well.

As shown in Table 5, the EG-H model outperforms the EGD model with noticeable improvements, as the percentages of labels "2" and "3" are much higher for all three evaluation metrics. This shows that the model M4-1 can contribute to generating evidences of higher quality. Table 5 also shows that the EG-F model improves the performance compared with EG-H model. This verifies the effectiveness of bringing model M4-2 with human annotated data set. It also indicates that more human annotated evidences can be adopted to better guide the EG model to generate evidences similar to human composed evidences.

We further compare the phrase replacements and deletions performed by each model. Experimental results show that the average number of phrase replacements/deletions in sentences are 0/2.2, 0.8/1.9, 0.5/1.7, and 0.5/1.6 for baseline, EG-D, EG-H, and EG-F, and the average lengths of evidences generated by these models are 7.9, 7.2, 7.7, and 7.8, respectively. The baseline conducts more deletions than the other three models, but makes no replacement. As we can see from Table 5, the adequacy, fluency, and attraction of baseline and EG-D are lower than that of EG-H and EG-F models, which demonstrates that some key phrase replacements or deletions are inadequately or incorrectly performed in baseline and EGD. This motivates us that more efficient models for replacing and deleting can be explored in future to get better results.

Table 6 shows the evaluation results of each category involved in our experiments. Except C2 (terminology) and C3 (organization), the performance of all the other categories match up with or outperform the overall performance of EG-F (shown in Table 5). This verifies that EG-F can generate domain independent evidences which achieve our applications. The percentages of label "1" of C2 and C3 for all three evaluation metrics are higher than that of the overall performance of EG-F. The main reason is that the average lengths of sentences of C2 and C3 are 12.1 and 13.3, which are larger than the overall average length 11.8. Another reason is the "mistranslation" of the infrequent numbers that occur more frequently in C2 and C3 (account for 24.2% of bad cases), e.g., the "ranked 27th" is wrongly "translated" to "ranked 1st". It is thus more necessary to bring a new model to "translate" numbers in correct ways to improve the EG performance.

6 RelatedWork

In this section, we review the related work. A research topic closely related to our work is the task of mining evidences for entities. [Li et al., 2013] proposed a method to mine evidences for named entity disambiguation task. The evidences consist of multiple words related to an entity. Our work is different in that we aim at generating comprehensible and human-readable sentences as evidences. Our work is also related to the task of sentence compression. [Turner and Charniak, 2005; Galley and McKeown, 2007; Nomoto, 2007; Che et al., 2015] proposed methods to compress an original sentence by deleting words or constituents. However, these extractive methods are restricted to word deletion, and therefore are not readily applicable to the more complex EG task. [Cohn and Lapata, 2013] proposed an abstractive method to compress an original sentence by reordering, substituting, inserting, and removing its words. This method cannot be directly transplanted to the EG task due to the specificity of the entity evidence, since the EG task requires to generate evidences within specified length limits by using attractive expressions and vocabularies from a sentence, rather than simply compress a sentence.

Our work is also closely related to the studies in sentential paraphrase generation using monolingual machine translation. Although the studies share the same idea in translating a source sentence into a target sentence that are in the same language by using monolingual parallel corpus, there are some differences from our work. [Wubben et al., 2012] built a monolingual machine translation system to convert complex sentences into their simpler variants. While our work aims at generating concise, informative, and interesting evidences from sentences rather than just simplifying sentences. [Quirk et al., 2004; Zhao et al., 2009] viewed paraphrase generation as monolingual machine translation, which aims to generate a paraphrase for a source sentence in a certain application. The three major distinctions between evidence generation and these studies are: (1) we consider language styles and vocabularies in evidences; (2) we add a length model to ensure the generating of evidences within maximum length allowed; (3) we introduce two attraction measures and features in the EG model, to produce more attractive evidences from sentences.

7 Conclusion and FutureWork

In this paper, we study the problem of generating evidences for the recommended entities in web search. We propose a translation model to generate evidences from sentences. The experiments show that our method can generate domain independent evidences with high usability.

As future work, we plan to dynamically select appropriate evidences for each recommended entity related to the search query. We are interested in generating evidence using multiple sentences, rather than relying on a single sentence.

Acknowledgments

This research is supported by the National Basic Research Program of China (973 program No. 2014CB340505). We would like to thank the anonymous reviewers for their insightful comments.