DEIM Forum 2017 G8-2

Learning Query Paraphrasing from A Monolingual Corpus
Meng ZHAO† , Hiroaki OHSHIMA† , and Katsumi TANAKA†† Department of Social Informatics, Graduate School of Informatics, Kyoto University
Yoshida Honmachi, Kyoto, 606–8501 Japan
E-mail: †{zhao,ohshima,tanaka}@dl.kuis.kyoto-u.ac.jp
Abstract We propose a method to obtain diﬀerent expressions that convey the same meaning with that of a given
phrase or sentence query. The notion is based on the distributional hypothesis that words that occur in the samecontexts tend to have similar meanings. We assume that a phrase or sentence can be divided into a template partand an entity part. Therefore, surrounding entities generate the context of a template and vice versa, surrounding (in precise, suitable) templates generate the context of an entity. In this paper, we present an extension to
the continuous bag-of-words (CBOW) model that eﬃciently learns the embedding for each template. As a result,semantically similar templates are detected in such a way that their semantic representations are similar to eachother.
Key words query paraphrasing, CBOW model, semantic representation

1. Introduction

to close to the expressions used in the systems, and consequently improving search performance. We introduce anParaphrases are linguistic expressions that restate theunsupervised learning approach which is based on the word

same meaning using diﬀerent variations. In the most ex-embedding technique, to capture paraphrases on a monolin-

treme case, they may not be even similar in wording. It

gual corpus.

has been shown that paraphrases are useful in many appli-

Word embedding, where words or phrases from the vo-

cations. For example, paraphrases can help detect fragments

cabulary are mapped to dense vectors of real numbers, hasof text that convey the same meaning across documents andattracted a lot of research interest, since it is first introduced

this can improve the precision of multi-document summariza-

by Bengio et al. [7] in 2003. It has been exceptionally success-tion [6] [16]. In the field of machine translation, [10] [14] [15]ful in many natural language processing tasks such as named

show that augmenting the training data with paraphrases

entity extraction [21] [25] [24], dependency parsing [3], ma-generated by pivoting through other languages can alleviatechine translation [34] [18] and learning representations of

the vocabulary coverage problem. In information extraction,

paragraphs and documents [13].

[33] [11] [9] present approaches incorporating paraphrases

With the help of word embedding, words whose meaning is

to extract semantic relations among entities. In informa-

similar are mapped to a similar position in the vector space.

tion retrieval, paraphrases have been used for query expan-

For example, word “strong” is similar to “powerful”, word

sion [26] [1] [32]. A large proportion of previous work extract“Paris” is similar to “Berlin” [20]. Moreover, the learned dis-and generate paraphrases based on parallel corpora [5] [2] ortributed vectors can capture many linguistic regularities andcomparable corpora [4] [27] [30]. However, there are limi-

patterns. For example, vector operations vector(“Paris”) -tations in using those corpora. For example, the quality ofvector(“France”) + vector(“Germany”) results in a vector

obtained paraphrases strongly depends on the quality of thethat is very close to vector(“Berlin”), and vector(“brother”)

corpus, a high-quality corpus can cost a great deal of man-- vector(“grandson”) + vector(“granddaughter”) is close topower and time to construct. Moreover, it may be hard tovector(“sister”) [17] [20].

cover all possible genres. For example, [30] uses a corpus

However, the meaning of a phrase cannot be obtained byconsisted of newswire articles written by six diﬀerent news

simply combining the meanings of words in the phrase. For

agencies.

example, the meaning of “Volga River” cannot be obtained

A bottleneck for information retrieval systems is the iden-

by combining the meanings “Volga” and “River”. Mikolov

tification of diﬀerent expressions with the same meaning be-

el al. realized the problem and hence proposed a data-driven

tween a user s query and existing descriptions in the systems.

approach where phrases are formed based on the unigram

In this paper, we aim at paraphrasing user-given queries

and bigram counts to find phrases and then phrases are re-garded as individual tokens for the later training [19].

"#$%&'()*+,!

We assume that a phrase or sentence can be divided intoa template part and an entity part. Take a sentence “Bayer
W

!!!!

xi−2

!!!!

said it would buy Monsanto” for example. The template

W

-%./'
01+,)2+/34#5)&+#)&+!

6%&$%&'()*+,!

part corresponds to “said it would buy”, while the entity
part corresponds to a tuple (Bayer, Monsanto). Alternative
expressions for either the template part or the entity partxi−1

can be found, and hence a variety of combinations could be
generated. Here, we concentrate on learning alternative ex-

W'

!!!!

!!!!

pressions for templates, where the length for both of themxi

are variable. For example, vector(“has announced its acqui!!!!

W

!!!!

xi+1

sition of”) is close to vector(“said it would buy”). We findWthat still, it is diﬃcult to capture the meanings of variablelength pieces of texts by the above approach [19]. Therefore,
we present a method based on the continuous bag-of-words
xi+2(CBOW) model [17] which predicts multiple words rather
than a single word based on the context. The learned vectors of words in a template are summed, averaged or con-Figure 1 Architecture of the CBOW model with window size

catenated to represent the meaning of the template.

c = 2. xi is a one-hot vector with dimensionality V and

The remainder of the paper is organized as follows. In

consists of 0s in all cells with the exception of a single

Section 2., we briefly review the CBOW model. In Section

1 in the cell corresponding to the i-th word, denoted by

3., we describe the details of our extension to the CBOWti . Here, V is the size of vocabulary. Context of wordmodel. In Section 4., we show experimental results, as wellti consists of words ti − 2 , ti − 1 , ti+1 and ti+2 .

as some interesting observations. We dedicate Section 5. tothe discussion of the previous work on paraphrase detection
and acquisition, adopting machine learning approaches. Finally, in Section 6., we conclude the paper and draw somewhere c is the window size of the context.
Basically, p(ti |ti−c , ..., ti+c ) is defined by using the softmax
function

future directions.

2. Background: Continuous Bag-of-words
Model
The CBOW model [17] learns distributed vector representation for words by predicting a word given the surroundingp(ti |ti−c , ..., ti+c ) = ∑exp(v̂t⊤i · vcti )⊤t∈T exp(v̂t · vcti )(2)where vt and v̂t are the input and output vector representations of t, and vcti denotes the sum, average or concatenationof context words.

words as the context. The model architecture is shown in

Because the cost of computing the log probabilities of all

Figure 1. xi is a one-hot vector with dimensionality V andwords is very expensive, hierarchical softmax [22], an ap-

consists of 0s in all cells with the exception of a single 1 inproximation inspired by binary trees, is employed for fast

the cell corresponding to the i-th word, denoted by ti . Here,training. Mikolov et al. used a binary Huﬀman tree for

V is the size of vocabulary. W is the input to hidden weight

speedup in a series of their research [19] [18] [13].

′matrix, W the hidden to output weight matrix.
In the CBOW model, v(t) ∈ RN is the vector representa-

3. An Extension to the CBOW Modeltion of the word t ∈ T , where T is the word vocabulary and

To extend the CBOW model to learn embeddings of tem-

N is the number of hidden units, thus the dimensionality ofplates, we use the surrounding words to predict multiple

the word embeddings. v(ti ) is easily obtained by left mul-

words rather than a single word. The model architecture

tiply xi by the input to hidden weight matrix W . Given a

is shown in Figure 2 where for simplicity, two words are pre-training set including the sequence of words t1 , t2 , t3 , ..., tV ,dicted given the context. tif and til indicate the former andthe word embeddings are learned by maximizing the average

latter words, respectively, considering the relative positionlog probability

in a training sequence. We denote M the maximum distance1 ∑p(ti |ti−c , ..., ti+c )V i=cbetween tif and til . If the distance between them is larger

V −c

(1)

than M , we discard the probability that they co-occur. Figure 3 shows an example of context words in the model, where“Google” denotes tif and “DoubleClick” denotes til .

"#$%&'()*+,!

Given a training set including the sequence of words t1 , t2 ,t3 , ..., tV , the word embeddings are learned by maximizing
W

W

!!!!

xi f −2∑!!!!

1
V (V − 1)!!!!

the average log probability

W

-%./'
01+,)2+/34#5)&+#)&+!

6%&$%&'()*+,!

p(tif , til |tif −c , ..., til +c ) (3)ti ,ti ∈T −C,ti =t
| i
f

l

f

l

where tif and til are not identical, C is the set of context

xi f −1words and c is the window size of the context. We use tO torepresent {tif , til }, tI to represent {tif −c , ..., til +c } for simple notation hereinafter. As a result, p(tif , til |tif −c , ..., til +c )is equal to p(tO |tI ).

xi f +1!!!!

where vt and v̂t are the input and output vector representaW

!!!!

W

!!!!

xil −1!!!!

tions of t, respectively.

W

xi f

!!!!

(4)

!!!!

exp(v̂t⊤O · vtI )⊤t∈T ×T exp(v̂t · vtI )p(tO |tI ) = ∑!!!!

We define p(tO |tI ) using the softmax function

xil

W'

We define the distributed vector representation of a template as the average of template word vectors weighted by
the input to hidden weight matrix W :1
L∑

W · xixil +1(5)

ti ∈template

where L denotes the number of words contained in a template. Therefore, the vector representation of “plan to ac-

xil +2quire” is the average of vectors of the words “plan”, “to”
and “acquire”.

4. Experiments
We plan to train the model on the full English Wikipedia
（注 1）

text

.

To evaluate whether templates with the same, or similar

Figure 2 Architecture of the extended CBOW model with window size c = 2. Context of words tif and til consists ofthree parts: words before tif with window size c, i.e.,tif − 2 , tif − 1 , words between tif and til , words after
til with window size c, i.e., til +1 and til +2 .

meaning could be mapped to a similar position in the vector
space, we plan to select some relations by referring to somecan contain paraphrases. Thus, they proposed an automatic

previous works [8] [9] [12] about acquiring paraphrases or de-paraphrase acquisition approach based on the assumption

tecting paraphrases in a corpus, and questions from TREC-8

that named entities are preserved across paraphrases.

Question-Answering Track.

Paşca and Dienes proposed a diﬀerent method [23]. Theyuse inherently noisy, unreliable Web documents rather than

5. Related Work

clean, formatted documents. They assumed that if two sen-Paraphrase acquisition is a task of acquiring paraphrases oftence fragments have common word sequences at both ex-

a given text fragment. Some approaches have been proposed

tremities, then the variable word sequences in the middle

for acquiring paraphrases at word, or phrasal level. How-

are potential paraphrases of each other. Socher et al. pro-

ever, these techniques are designed to be only suitable for

posed an unsupervised feature learning algorithm based on

specific types of resources. Shinyama et al. [28] and Wubben

recursive autoencoders(RAE) in [29] for paraphrase detec-

et al. [31] acquired paraphrases from news articles. For ex-tion. Their RAEs are based on a novel unfolding objective

ample, Shinyama et al. [28] argued that news articles by dif-and learn feature vectors for phrases in syntactic trees. These

ferent news agents reporting the same event of the same dayfeatures are used to measure the word- and phrase-wise similarity between two sentences.

（注 1）：It can be downloaded from http://en.wikipedia.org/wiki/

Wikipedia_database.

!"#$%&'(")*'+,-!

…'%#."#*'/$0*12("#3'"#4%'$"(5./6'/$(7'!""#$%&8%93:4''"()$%*$+,-';%1'<=7>'8".."%#'"#'-??@7'!
ti
ti
f

l

$"(4/#+*'8*4&**#'2;'/#$'2.!

!"#$%&'(")*'+,-!

Figure 3 An example of context words for tif and til with window size c = 2.

6. Conclusion
We proposed a method which is an extension to the CBOW
model, to obtain diﬀerent expressions that convey the same
meaning with that of a given phrase or sentence query. We
assume that a phrase or sentence can be divided into a template part and an entity part. Especially, we focused on thetemplate part. After the training, templates with the same,or similar meaning are mapped to a similar position in thevector space.

Acknowledgment
This work was supported by JSPS KAKENHI Grant Numbers JP24680008, JP15H01718, JP16H02906.

References[1] Anick, P.G., Tipirneni, S.: The paraphrase search assistant:
Terminological feedback for iterative information seeking.
In: Proceedings of the 22Nd Annual International ACM
SIGIR Conference on Research and Development in Information Retrieval. pp. 153–159 (1999)[2] Bannard, C., Callison-Burch, C.: Paraphrasing with bilingual parallel corpora. In: Proceedings of the 43rd Annual
Meeting on Association for Computational Linguistics. pp.
597–604 (2005)[3] Bansal, M., Gimpel, K., Livescu, K.: Tailoring continuous
word representations for dependency parsing. In: ACL (2).
pp. 809–815 (2014)[4] Barzilay, R., Elhadad, N.: Sentence alignment for monolingual comparable corpora. In: Proceedings of the 2003
Conference on Empirical Methods in Natural Language Processing. pp. 25–32 (2003)[5] Barzilay, R., McKeown, K.R.: Extracting paraphrases froma parallel corpus. In: Proceedings of the 39th Annual Meeting on Association for Computational Linguistics. pp. 50–57(2001)[6] Barzilay, R., McKeown, K.R., Elhadad, M.: Information
fusion in the context of multi-document summarization. In:
Proceedings of the 37th Annual Meeting of the Association
for Computational Linguistics on Computational Linguistics. pp. 550–557 (1999)[7] Bengio, Y., Ducharme, R., Vincent, P., Jauvin, C.: A neuralprobabilistic language model. journal of machine learning
research 3, 1137–1155 (2003)[8] Bhagat, R., Ravichandran, D.: Large scale acquisition ofparaphrases for learning surface patterns. In: Proceedingsof ACL2008: HLT. pp. 674–682 (2008)[9] Bollegala, D.T., Matsuo, Y., Ishizuka, M.: Relational duality: Unsupervised extraction of semantic relations between
entities on the web. In: Proceedings of WWW. pp. 151–160(2010)[10] Callison-Burch, C., Koehn, P., Osborne, M.: Improved statistical machine translation using paraphrases. In: Proceedings of the Main Conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics. pp. 17–24 (2006)[11] Etzioni, O., Banko, M., Soderland, S., Weld, D.S.: Open information extraction from the web. Commun. ACM 51(12),68–74 (Dec 2008)[12] Idan, I.S., Tanev, H., Dagan, I.: Scaling web-based acquisition of entailment relations. In: Proceedings of EMNLP.
pp. 41–48 (2004)[13] Le, Q.V., Mikolov, T.: Distributed representations of sentences and documents. In: ICML. vol. 14, pp. 1188–1196(2014)[14] Madnani, N., Ayan, N.F., Resnik, P., Dorr, B.J.: Using paraphrases for parameter tuning in statistical machinetranslation. In: Proceedings of the ACL Workshop on Statistical Machine Translation (2007)[15] Marton, Y., Callison-Burch, C., Resnik, P.: Improved
statistical machine translation using monolingually-derived
paraphrases. In: Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing. pp. 381–
390 (2009)[16] McKeown, K.R., Barzilay, R., Evans, D., Hatzivassiloglou,
V., Klavans, J.L., Nenkova, A., Sable, C., Schiﬀman, B.,
Sigelman, S., Summarization, M.: Tracking and summarizing news on a daily basis with columbia’s newsblaster.
In: Proceedings of the second international conference on
Human Language Technology Research. pp. 280–285 (2002)[17] Mikolov, T., Chen, K., Corrado, G., Dean, J.: Eﬃcientestimation of word representations in vector space. arXiv
preprint arXiv:1301.3781 (2013)[18] Mikolov, T., Le, Q.V., Sutskever, I.: Exploiting similarities among languages for machine translation. CoRR
abs/1309.4168 (2013)[19] Mikolov, T., Sutskever, I., Chen, K., Corrado, G.S., Dean,
J.: Distributed representations of words and phrases andtheir compositionality. In: Advances in Neural Information
Processing Systems. pp. 3111–3119 (2013)[20] Mikolov, T., Yih, W.t., Zweig, G.: Linguistic regularities incontinuous space word representations. In: HLT-NAACL.
vol. 13, pp. 746–751 (2013)[21] Miller, S., Guinness, J., Zamanian, A.: Name tagging withword clusters and discriminative training. In: North American Chapter of the Association for Computational Linguistics: Hu- man Language Technologies (NAACL-HLT).
vol. 4, pp. 337–342 (2004)[22] Morin, F., Bengio, Y.: Hierarchical probabilistic neural network language model. In: Proceedings of the International
Workshop on Artificial Intelligence and Statistics. pp. 246–
252 (2005)[23] Paşca, M., Dienes, P.: Aligning needles in a haystack: Paraphrase acquisition across the web. In: Proceedings of IJC-NLP. pp. 119–130 (2005)[24] Passos, A., Kumar, V., McCallum, A.: Lexicon infusedphrase embeddings for named entity resolution. arXiv
preprint arXiv:1404.5367 (2014)[25] Ratinov, L., Roth, D.: Design challenges and misconceptions in named entity recognition. In: Proceedings of theThirteenth Conference on Computational Natural Language
Learning. pp. 147–155 (2009)[26] Salton, G., McGill, M.J.: Introduction to Modern Information Retrieval. McGraw-Hill, Inc. (1986)[27] Shinyama, Y., Sekine, S.: Paraphrase acquisition for information extraction. In: Proceedings of the Second International Workshop on Paraphrasing. vol. 16, pp. 65–71 (2003)[28] Shinyama, Y., Sekine, S., Sudo, K.: Automatic paraphrase
acquisition from news articles. In: Proceedings of HLT. pp.
313–318 (2002)[29] Socher, R., Huang, E.H., Pennington, J., Ng, A.Y., Manning, C.D.: Dynamic pooling and unfolding recursive autoencoders for paraphrase detection. In: NIPS. vol. 24, pp.
801–809 (2011)[30] Wang, R., Callison-Burch, C.: Paraphrase fragment extraction from monolingual comparable corpora. In: Proceedings of the 4th Workshop on Building and Using Comparable Corpora: Comparable Corpora and the Web. pp. 52–60(2011)[31] Wubben, S., van den Bosch, A., Krahmer, E., Marsi,
E.: Clustering and matching headlines for automatic paraphrase acquisition. In: Proceedings of ENLG. pp. 122–125(2009)[32] Yamamoto, Y., Tanaka, K.: Towards web search by sentence queries: Asking the web for query substitutions.
In: Proceedings of the 16th International Conference on
Database Systems for Advanced Application (DASFAA
2011). pp. 83–92 (2011)[33] Yates, A., Cafarella, M., Banko, M., Etzioni, O., Broadhead, M., Soderland, S.: Textrunner: Open information
extraction on the web. In: Proceedings of Human Language
Technologies: The Annual Conference of the North American Chapter of the Association for Computational Linguistics: Demonstrations. pp. 25–26 (2007)[34] Zou, W.Y., Socher, R., Cer, D.M., Manning, C.D.: Bilingual word embeddings for phrase-based machine translation. In: Empirical Methods in Natural Language Processing (EMNLP). pp. 1393–1398 (2013)