DEIM Forum 2017 G8-3

Cluster-biased Transformation of Texts across Heterogeneous Domains
Yating ZHANG† , Adam JATOWT† , and Katsumi TANAKA†† Graduate School of Informatics, Kyoto University
Yoshida-Honmachi, Sakyo-ku, Kyoto, 606-8501 Japan
E-mail: †{zhang,adam,tanaka}@dl.kuis.kyoto-u.ac.jp
Abstract In the recent years we have witnessed a rapid increase of diverse text content generated on the Web
or digitized in archives. It is then more difficult for users to perform search and comparison within large volumesof text data, due to the terminology gap between the domain of user’s knowledge and the search domain. For
example, users often struggle when searching in unfamiliar domains if they do not know correct keywords (e.g.,
searching for information related to a specific time or a foreign country) or when comparing documents generated
by different sources. In this paper, we approach the problem of terminology gap by providing a general framework
to bridge different domains and, by this, to facilitate search and comparison as if they would be carried in user’s
familiar domains. We first propose a cluster-biased transformation technique which allows mapping words acrossdifferent domains and we then adapt this method to enable mapping entire documents (e.g., set of words, relationalgraphs) across domains. The proposed methods are unsupervised and can be applied to any scenario. We test theperformance of our approaches on documents from geographically as well as temporally different domains.
Key words text transformation, cluster-biased, heterogeneous domains

1. INTRODUCTION

cess). Once the transformation is established, different retrieval requests/applications can be accessed/applied to. For

In the recent years we have witnessed a rapid increase of

instance, in the research problem of searching by analogicaltext content generated on the Web or digitized in archives.

objects as we mentioned before, users can search by “iPod

The current keyword-based search engine thus has limited

in 1980s” (replacing the correct keyword “Walkman”) or

performance in supporting users to perform search and com-

“Japanese NASA” (instead of the keyword “JAXA”), when

parison within large volumes of text data, due to the termi-

the keyword “Walkman” or “JAXA” is unknown to them.

nology gap between user’s knowledge domain and the search

The comparison between long texts (e.g., sentences or doc-

domain. For example, when searching in unfamiliar domains,uments) can be also conducted by applying across-domainsuch as searching within past collections or collections of doc-

similarity measures introduced in this paper.

uments related to different countries, users have often diffi-

Transformation mechanism for text does not only help toculty to recall correct keywords to search with. The vocab-

solve the cold-start problem in search across domains by for-ulary mismatch resulting from heterogeneous document col-mulating queries in the form of analogy, but it also enables

lections also hinders the comparison of documents publishedthe text comparison (e.g., word, sentence, document com-in different periods due to the terminology change acrossparison) in different collections. However, transformation oftime or in diverse locations where cultures/objects/entities

text in heterogeneous domains is not trivial. The main chal-

are quite different. The search and comparison of texts acrosslenge lies in the vocabulary gap across collections due to theheterogeneous domains is the research focus of this paper.

time change, culture differences etc, suggesting that the di-

To bridge the gap between a user’s familiar domain andrect context comparison will not work. To solve this issue, we

the unfamiliar search domain for enabling easy text search

apply distributed word embedding technique [6], [7] in orderand comparison, we propose a cluster-biased transformation

to first set the vocabularies of each domain into their own

mechanism which automatically transforms the text from one

semantic spaces separately. Then, we construct similarity

domain to the other as well as establishing the across-domain

measure of words across domains by mapping the vocabular-

similarity measures, thus allowing users to search by analog-

ies across vector spaces.

ical objects or compare different documents. In this paper,

To design the mapping function as mentioned above, we

we focus on the process of constructing the connections offirst propose to utilize automatically derived training seeds

text across different collections (or text transformation pro-to construct one transformation matrix for aligning two vec-

tor spaces by assuming that all the vocabularies in one space

Across-Domain Similar Object is defined as an object wt

follow the same rule (mapping function) in transformation.

(e.g., JAXA) which is contextually similar to the queried ob-

In this paper we also introduce an advanced approach named

ject wb (e.g., NASA) (in the scenarios of searching acrosscluster-biased term transformation to relax the above as-

locations (Japan vs. USA)). Note that the context between

sumption by training multiple transformation matrices bi-

wt and wb is not required to be literally same. The literalased on specific semantic clusters across vector spaces. This

form could be different as long as their meanings are similar.

advanced approach aims at providing more precise mapping

Across-Domain Similar Document is defined as a docu-

across different vocabulary sets by considering the specificityttment dt = {(w1t , f1t ), (w2t , f2t ), ..., (wm, fm)} (where fit is theof transforming different sets of semantics.

frequency of term wi in dt ) which is semantically similar to

To utilize the trained mapping functions (or transformation matrices) for further across-domain search or documentcomparisons, we introduce several retrieval models and similarity metrics based on the above mentioned transformation
mechanisms.

bbqueried document db = {(w1b , f1b ), (w2b , f2b ), ..., (wm
, fm
)}.

3. GLOBAL
TION

TERM

TRANSFORMA-Our goal is to compare terms related to disjoint geograph-

To sum up, our contributions in this work are as follows:

ical areas and to find matching term pairs (e.g., NASA and（ 1 ） We propose an efficient and effective framework to

JAXA). For this, we propose constructing a mapping function

transform text across heterogeneous domains, which pro-

between the base space and the target space. This process

vides fundamental technique to conduct similarity compar-

is query independent and can be done offline. While es-

ison across vector spaces. For more precise mapping, wetablishing the mapping function would necessarily requirethen introduce an advanced cluster-biased text transforma-a supervised method, we assume in this work an unsuper-tion mechanism to train specific mapping function for each

vised approach. This is because it is infeasible to provide

semantic cluster.

sufficient number of training pairs of terms (such as the ex-（ 2 ） To test the performance of the proposed transfor-amples listed above) for any possible combination of two dif-mation techniques, we provide several retrieval models forferent countries or other geographic regions. We then resort

across-domain search scenario and text comparison.

to automatically finding training pairs. One way to gener-（ 3 ） We evaluate the proposed approaches on the un-ate such term pairs could be based on the equality of term

structured text in both temporal collections and spatial

literal forms. However, we cannot always assume a direct

datasets, which prove the effectiveness of our approach.

semantic correspondence between the same term in two dif-

The reminder of this paper is structured as follows. We for-ferent spaces. Even if the same term appears in two different

mally describe the research problem in the next section. We

spaces, there is no assurance that it indeed denotes iden-

then discuss the general term transformation technique fortical concept. For example, sushi in Japan is regarded asaligning two vector spaces in Section 3. Section 4 explains

the typical or local food, however in another country, such

our advanced approach of cluster-biased term transforma-as USA, though sushi also exists, the position/role behindtion. Next, we describe the experimental setup and give theit is rather different (e.g., sushi is regarded as foreign andevaluation results in Sections 5 and 6, respectively. The next

relatively luxury food in USA). This phenomena can be in-section contains the discussion. We conclude the paper andterpreted as the meaning shift across spaces. On the other

outline the future work in the last section.

hand, sometimes literally different terms in different spatial
areas may represent the same or very similar concept, such

2. PROBLEM STATEMENT

as haiku in Japan and poetry in USA.

In this section, we formally define the problem of the termtransformation across heterogeneous domains.

3. 1 Word Embedding
For capturing word semantics we use word embedding

We set two spaces: a base domain (user’s knowledge do-techniques. Distributed representation of words by usingb} (wib ∈ Vocabulary of S b ) frommain) S b = {w1b , w2b , ..., wm

neural networks was originally proposed in [9]. Mikolov etwhich the query (or document) is selected, and a target do-al. [6], [7] improved such representation by introducing Skip-

main (user’s search domain) S t = {w1t , w2t , ..., wnt } (wit ∈gram model based on a simplified neural network architec-t

Vocabulary of S ) where the answer is to be retrieved from.

ture for constructing vector representations of words from

Term Transformation is a mapping function M (∗) to alignunstructured text. Skip-gram model has several advantages:bt

the vocabularies of two vector spaces (S and S where each(1) it captures precise semantic word relationships; (2) it canof the vector space contains the vector representation ofeasily scale to millions of words.

words).

3. 2 Transformation based on Anchor Mapping
Our goal is to compare words in the base space and3. 3 Retrieval Model for Global Term Transformation

words in the target space in order to find their counter-

After obtaining the transformation matrix M, we can thenparts. Since, as mentioned before, it is impossible to di-compute the similarity of a query, q, in the base space withrectly compare words in two different semantic vector spaces

any term v in the target space by multiplying the query’s vec-(the features/dimensions in both spaces have no direct cor-

tor representation with the transformation matrix M, andrespondence due to separate training processes), we train athen by calculating the cosine similarity between such trans-

transformation matrix to build the connection between dif-formed vector and the vector v.

ferent vector spaces. To better imagine the transformation

Ssim (q, v) = cos(Mq, v)(2)

idea, the semantic spaces could be compared to buildings.
If we regard two semantic spaces as two buildings, then, inorder to map the components from one building to the ones

4. CLUSTER-BIASED TERM TRANSFORMATION

in the other one, we need first to know how the main frames

In Sec. 3, we explained the way to construct a single trans-of the two buildings correspond to each other. Afterwards,

formation matrix for aligning two vector spaces by assuming

the rest of the components can be mapped automaticallythat all the vocabularies in one space follow the same map-by considering their relative positions to the main frames ofping function, which is obviously a simplified approach. To

their building. So, in our case, having established the cor-relax the above assumption, we propose an advanced ap-

respondence between the anchor terms in the two semantic

proach, called cluster-biased term transformation, to train

spaces, we can automatically map any terms relative to these

multiple transformation matrices biased on specific seman-anchors. In this work, we propose to use Shared Frequenttic clusters across vector spaces. The motivation behind thisConcepts (SFC) as anchors to build the transformation. To

approach lies in the notion that a single transformation ma-

construct the transformation, however, manually preparingtrix is too coarse and general to serve well for any possi-

large enough sets of anchor terms that would cover various

ble queries. We believe that the combination of ”local” ap-

topics/domains as well as exist in any possible combinations

proaches designed for semantic subspaces should work bet-of the base and target spaces requires much effort and re-ter. In the new approach we consider that the characteristics

sources. We rely here on an approximation procedure forof the word embedding spaces are such that in each vector

automatically extracting SFC as anchor pairs. Specifically,

space, the semantically similar words are located close to

we select terms that (a) are general in their meaning and (b)each other. We then propose a clustering based approach inhave high frequency (e.g., mountain, river, lake, president)

which each semantic cluster should be subject to its own spe-in both the base and the target spaces. The intuition behindcific transformation mechanism. In the following sections,this idea is that general terms that are also frequent in both

we first introduce the way to construct semantic clusters ofspaces are more likely to have stable meaning and be alsoeach space by hierarchical clustering and then establish theco-occurring with many other terms.

mapping function across clusters in two domains.

Suppose there are u pairs of anchor terms {(xb1 ,4. 1 Hierarchical Clustering in Vector Spacext1 ),. . . ,(xbu , xtu )} where xbi is an anchor in one space (e.g.,

Hierarchical Agglomerative Clustering (HAC), one of theJapan) and xti is its counterpart, that is, the same anchor

methods of cluster analysis, has been successfully used forin the other space (e.g., USA). The transformation matrix

building a hierarchy of clusters in a “bottom up” cluster-

M is found by minimizing the differences between Mxb
i anding manner. In this paper, we utilize single-linkage criterion

xti (see Eq. 1). This is realized by minimizing the sum of(implemented by SLINK [11] algorithm（ 注 1） ) to determine theEuclidean 2-norms between the transformed query vectors

distance between clusters when doing the merging, that is theand their counterparts. Eq. 1 is used for solving the regu-

minimum distance between elements of each cluster wherelarized least squares problem (γ = .02) with regularization

the distance of words are measured by the inverse of cosine

component used for preventing overfitting:uX2t
M = argmin
Mxb+ γ kMk22
i − xisimilarity between their word embeddings. HAC process is

M

i=1

2

(1)

u denotes here the size of anchor term set which contains,in our implementation, the top 5% frequent concepts (overdone separately for each vector space. After the HAC iscompleted, we can obtain a hierarchical clusters. Then eachword in a vector space belongs to a hierarchical path of clusters from the leaf cluster (the word itself) to the root cluster

10,000 terms) in the intersection of vocabularies of the two
corpora.

（ 注 1）： Considering the lower complexity of the SLINK algorithm:

O(n2 ) in time complexity and O(n) in space complexity

which contains all the words.

transformation matrix biased on cluster Ck=4 .

4. 2 Term Transformation biased on Semantic

Note that when k = 0 (root cluster), the seed weights willbe all equal, which is as the same as the approach of global

Clusters
As discussed in the beginning of Sec. 4, we aim at train-term transformation introduce in Sec. 3. Therefore, global

ing transformation matrices for different semantic clusters.

term transformation (Eq. 1) can be regarded as a special

Different from training of global term transformation whichcase of cluster-biased term transformation (Eq. 3).

give equal weights to all the seeds (see Eq. 1), in clusterbiased approach, our idea is that for each semantic cluster,
we bias on the seeds which highly related to this cluster by

4. 3 Retrieval Model for Cluster-biased Term
Transformation
As discussed above, for each semantic cluster, we train

manipulating the weights (λ) on the seeds when training thea transformation matrix in the way described in Eq.

transformation matrix (see Eq. 3).

However each word has multiple memberships over differ-

Mk = argmin
Mk

u
X

3.

ent clusters from the word itself to the root cluster and
λi,k

2

t
Mk x bi − xi2

i=1+ γ kMk k22(3)each transformation process will obtain a list of candidate
results. Therefore, in this section we propose to combine

The weight λi,k of seed xi biasing on cluster Ckb is computed

the results from different transformations by aggregating theby Eq. 4.

transformed vector of the query (see Eq. 5).
λi,k = e−(L b −L b )
C
C
k

(4)

j

K

Ssim (q, v) =where LC b (or LC b ) denotes the length (or hops) of the shortk

(5)

k=1

j

est path from cluster Ckb (or Cjb ) to the root of the hierarchy

1 X
cos(Mk q, v)
K

5. EXPERIMENTAL SETTINGS

tree; Cjb represents the cluster (1) which is on the shortest
path from Ckb to the root, (2) which contains the word xi
and meanwhile (3) it is the nearest cluster to Ckb .
Toy Example. We show a toy example for better explaining how to calculate the weights of the seeds for a specificcluster. In our toy example, the hierarchy tree of the words
in base space is shown in Fig. 1 and we specifically compute the seed weights for semantic cluster Ck=4 . Suppose
the seeds for training transformation matrix are {x1 , x2 , x3 },then Table 1 computes the weights of these seeds step by

5. 1 Datasets
Across-time search. For the experiments we use the New
York Times Annotated Corpus [10]. This dataset contains
over 1.8 million newspaper articles published between 1987
and 2007. We first divide it into five parts according to article
publication time: [1987-1991], [1992-1996], [1997-2001] and[2002-2007]. Each time period contains then around half million articles. We next train the model of distributed vector
representation separately for each time period. The vocabulary size of the entire corpus is 360k, while the vocabulary

step following Eq. 4.

size of each time period is around 300k.
5. 2 Test sets
As far as we know there is no standard test bench for
temporal correspondence finding. We then have to manually create test sets containing queries in the base domain
and their correct counterparts in the target domain. In thisprocess we used external resources including the Wikipedia,
Figure 1 Toy example of hierarchy tree with seeds denoted as xi

Web search engines and several historical textbooks. The
test terms cover three types of entities: persons, locations
and objects.

Table 1 Toy example of weights calculation for Ck=4 (Note that

In total, we have 225 pairs of query term and its counter-

we remove the mark b representing the base domain forpart for the task of mapping [2002-2007] with [1987, 1991]

simplicity.)
seed

path

and 100 test pairs for the task of mapping [2002-2007] withCj

LCk=4 − LCj

λi,k=4x1{C4 ,C1 ,C0 } C4

2-2=0

1

x2

{C5 ,C1 ,C0 } C1

2-1=1

e−1

x3

{C7 ,C2 ,C0 } C0

2-0=2

e−2

[1992, 1996].
5. 3 Tested Methods
5. 3. 1 Baselines
We prepare five baselines as follows:

After computing the seed weights, they can be normalized over all the seeds and input to Eq. 3 to obtain a term

(1) Word embedding model without transformation(NT): NT uses distributional representation for capturing

Table 2 [2002,2007]→[1992,1996]
MRR
P@1 @5 @10 @20 @50(Impr.%)(%)
HT 0.213 (+16.9) 8.7

Table 3 [2002,2007]→[1987,1991]
MRR
P@1 @5@10 @20@50(%) (%) (%) (%)
32.6 42.4 58.7 77.2

(Impr.%)(%)
HT 0.216* (+21.0) 11.1(%) (%) (%) (%)
32.4 43.6 63.1 78.7

GT

0.182

7.6

27.2 33.7 50.0 63.0

GT

0.179

10.2

23.6

35.1

49.3

69.8

NT

0.119 (-34.6)

3.8

17.0 23.8 30.1 41.7

NT

0.129 (-27.8)

4.5

17.9

21.4

28.4

35.8

word semantics same as the proposed methods do. Instead

adaptation task.

Blitzer et al. [1] proposed a Structuralof training the document collections from two periods sep-

Correspondence Learning (SCL) to identify correspondences

arately, it however trains a joint vector space by mixing all

among features from different domains by modeling their cor-the documents. We can then evaluate the necessity of therelations with pivot features. The method was proved to per-transformation by testing this method in comparison to theform well in a discriminative framework, such as in the task

proposed methods.

of PoS-tagging. Similarly, Kato et al. [4], [5] proposed to uti-

(2) Global Transformation (GT) maps the terms in one

lize Relative Aggregation Point (RAP) such as average price,

vector space to the other by training a global transformation

maximum/minimum cost, restaurant categories etc. in dif-matrix as described in Sec. 3. We set GT as control base-ferent domains as features to detect a corresponding restau-line to verify the effectiveness of our proposed transformation

rant in another city. Both of these approaches were done in atechnique based on dual hierarchical structures as describeddiscriminative learning manner where a conditional probabil-in Sec. 4.

ity of the instances in a domain was estimated and classified

5. 3. 2 Proposed Methods

into a certain class. However, these approaches only work

HT conducts term transformation at each cluster on thefor the data where the instances are already classified or thepath of query to the root following the base hierarchical tree

distributions of the instances over categories are known in a(see Sec. 4.

domain. For many datasets, such as news archives, online

6. EXPERIMENTAL RESULTS
As shown in Tab. 2 and 3, the method HT statisticallysignificantly (p < .1) outperforms the best baseline GTreviews, encyclopedias where the entities are unstructuredor the entities are not represented by any fixed attributes,
one needs to leverage other information to solve the domain
adaptation problem. Unlike these researches, we propose a

6. 0. 1 Necessity of Transformation

general framework by only leveraging the semantics of terms

The next observation is that method NT achieves rela-and their relative positions in each semantic space to perform

NT essentially assumes a statictransformation. Our methods can be applied to any orthog-

world in which every term is supposed to retain its semantics

onal raw-text datasets while the query can be any term (e.g.,

across the different domains (or should have the same “posi-

city, person, object, culture).

tively low performance.

tion” in a single joint vector space created on the merged set

Analogical relation detection [2], [12], [13] is to some extent

of documents from the different time periods). Yet, many

related to our work. Structure Mapping Engine (SME) [2]terms change their meaning and usage in different times.

was the original implementation of Structure Mapping The-

Thus, their relative “positions” w.r.t. to other terms shouldory (SMT) [3] that explains how humans reason with analogy.

change, too. Without the transformation, the information

Later, Turney proposed Latent Relational Mapping Engine

on the relative changes of term positions in the vector spaces(LRME) [13] that extracts lexical patterns in which words

is lost.

co-occur to measure relational similarity. These approaches

6. 0. 2 Improvement by Leveraging Hierarchical Cluster
Information

are always based on a single dataset. This means that in sucha case contextual information specific to particular country

In Sec. 4, we have proposed a cluster-biased transforma-

is lost as also shown in our experiments. Moreover nonetion techqnieu for boosting the search performance. As seenof the previous works specifically focused on spatial analogy

in Tab. 2 and 3, we can observe an increase of performancetask. Finally, different types of models have been proposedby incorporating the information about hierarchical cluster-for the task of proportional analogy [13]. However, their ob-

ing information when performing transformation. HT has

jective was to extract an object that can fit into equation

on average 19% better performance than GTa : b :: c : d when one of the four constituents is missing.

7. RELATED WORK

8. CONCLUSION

Several researchers [1], [4], [5], [8] have approached domain

Nowadays, users often search for information related todistant and unknown places. To decrease the problem stemming from the vocabulary gap we propose query suggestion
mechanism based on automatic transformation of concepts
from one time area to another. The problem is not trivial
due to diverse contexts of semantically similar terms withindifferent time periods as demonstrated by poor performanceof approaches relying on a joint dataset. We introduce several unsupervised methods for mapping terms from different
time periods. An important characteristics of our approachis that it works on raw text collections without the need for
utilizing knowledge bases or any supervision.
References[1] J. Blitzer, R. McDonald, and F. Pereira. Domain adaptation with structural correspondence learning. In Proc. of
EMNLP, pages 120–128, 2006.
[2] B. Falkenhainer, K. D. Forbus, and D. Gentner. The
structure-mapping engine: Algorithm and examples. Artificial intelligence, 41(1):1–63, 1989.
[3] D. Gentner. Structure-mapping: A theoretical framework
for analogy*. Cognitive science, 7(2):155–170, 1983.
[4] M. P. Kato, H. Ohshima, S. Oyama, and K. Tanaka. Search
as if you were in your home town: Geographic search byregional context and dynamic feature-space selection. In
Proc. of CIKM, pages 1541–1544, 2010.
[5] M. P. Kato, H. Ohshima, and K. Tanaka. Content-based retrieval for heterogeneous domains: Domain adaptation byrelative aggregation points. In Proc. of SIGIR, pages 811–
820, 2012.
[6] T. Mikolov, K. Chen, G. Corrado, and J. Dean. Efficientestimation of word representations in vector space. In Proc.
of ICLR Workshop, 2013.
[7] T. Mikolov, I. Sutskever, K. Chen, G. Corrado, and J. Dean.
Distributed representation of phrases and their compositionality. In Proc. of NIPS, pages 3111–3119, 2013.
[8] S. Pan and Q. Yang. A survey on transfer learning. IEEE
TKDE, 22(10):1345–1359, 2010.
[9] D. E. Rumelhart, G. E. Hinton, and R. J. Williams. Learning internal representations by error propagation. Technicalreport, California Univ, San Diego La Jolla Inst. For Cognitive Science, 1985.
[10] E. Sandhaus.
The new york times annotated corpus
overview. The New York Times Company, Research & Develop., pages 1–22, 2008.
[11] R. Sibson. Slink: an optimally efficient algorithm for the
single-link cluster method. The computer journal, 16(1):30–
34, 1973.
[12] P. D. Turney. Expressing implicit semantic relations without supervision. CoRR, 2006.
[13] P. D. Turney. The latent relation mapping engine: Algorithm and experiments. Journal of Artificial Intelligence
Research, pages 615–655, 2008.