September 3, 2009

16:1

WSPC - Proceedings Trim Size: 9.75in x 6.5in

10-Aso1

PREDICTING PROTEIN-PROTEIN RELATIONSHIPSFROM LITERATURE USING LATENT TOPICSTATSUYA ASO1
dango-r@cs25.scitec.kobe-u.ac.jp

KOJI EGUCHI1
eguchi@port.kobe-u.ac.jp

1 Department of Computer Science and Systems Engineering, Kobe University, 1-1

Rokkoudai, Nada-ku, Kobe, 657-8501, Japan
This paper investigates applying statistical topic models to extract and predict relationships between biological entities, especially protein mentions. A statistical topic model,
Latent Dirichlet Allocation (LDA) is promising; however, it has not been investigated forsuch a task. In this paper, we apply the state-of-the-art Collapsed Variational BayesianInference and Gibbs Sampling inference to estimating the LDA model. We also apply
probabilistic Latent Semantic Analysis (pLSA) as a baseline for comparison, and compare them from the viewpoints of log-likelihood, classification accuracy and retrieval
effectiveness. We demonstrate through experiments that the Collapsed Variational LDA
gives better results than the others, especially in terms of classification accuracy andretrieval effectiveness in the task of the protein-protein relationship prediction.
Keywords: Biomedical text mining; probabilistic topic models.

1. Introduction
There have been increasing demands for organizing knowledge accumulated in documents and then generating potential hypotheses in biomedical fields. This paper
focuses on the task to predict relationships between biological entities. Research
trends on the biomedical relationship extraction can be categorized into: (1) methods using manually or automatically generated templates, (2) methods based onnatural language processing, and (3) statistical co-occurrence-based methods [1, 2].
This paper focuses on the third approaches targeting a specific type of biomedical
entities, proteins. While the natural language processing-based approaches usually
extract entity relationships within a document, statistical methods are based on cooccurrence of biomedical entities or their related statements in a set of documents
to extract relationships between the entities. Statistical topic models are promising
for this objective.
Statistical topic models (e.g., [3, 4]) are based on the idea that documents are
mixtures of topics, where a topic is a probability distribution over words, in orderto capture semantics or to achieve dimensionality reduction. “Probabilistic Latent
Semantic Analysis” (pLSA) [5], proposed by Hoffman, can model underlying topics
for given documents; however, it cannot model the topics for unseen documentsthat were not used for parameter estimation. Blei et al. [3] proposed one of theSeptember 3, 2009

2

16:1

WSPC - Proceedings Trim Size: 9.75in x 6.5in

10-AsoT. Aso & K. Eguchi

Fig. 1.

The graphical model of LDA.

topic models called “Latent Dirichlet Allocation” (LDA) in an extension of pLSA,
introducing a Dirichlet prior on a multinomial distribution over topics for each document. This makes the model applicable to unseen documents. The LDA model has
been accepted in various fields; however, it has not been investigated for predicting biological entity relationships, to our knowledge. In this paper, we investigate
applying the LDA model to extract and predict protein-protein relationships frombiomedical literature. In the statistical topic modeling, a set of topics are usuallyassumed to be unobserved in a document collection, and so we need to infer such
unknown distributions from the documents. To estimate the LDA model, “Collapsed Gibbs Sampling inference”a method can be used [4]. “Collapsed Variational
Bayesian inference” (CVB) [6] is alternative approach to estimate the LDA model.
The focus of this paper is to investigate how to apply the LDA model to thetask of protein-protein relationship prediction from biomedical literature, and toevaluate, in an extrinsic manner, the effectiveness over different model estimation
methods.
2. LDA and Estimation Algorithms
2.1. Generative Process of LDA
Figure 1 shows the graphical model of LDA. We formally describe generative processof LDA [3], as follows,(1) For all j documents sample θj ∼ Dir(α)(2) For all k topic sample φk ∼ Dir(β)(3) For each of the Nj words xi in document dj(a) Sample a topic zi ∼ M ult(θj )(b) Sample a word xi ∼ M ult(φzi )a It is sometimes simply called “Gibbs Sampling inference” [4].

September 3, 2009

16:1

WSPC - Proceedings Trim Size: 9.75in x 6.5in

10-AsoPredicting PP Relationships Using Latent Topics

3

where Nj is the total number of words in document j. θ and φ indicate a perdocument topic distribution and a per-topic word distribution, respectively; and α
and β indicate hyperparameters that specify Dirichlet priors corresponding to θ andφ, respectively.
Joint distribution of all the random variables and parameters in the LDA model
are given by the following equation:p(x, z, θ, φ|α, β) =K
DY
Γ(Kα) Y

Γ(α)K
j=1

α−1+njk·

θjk

k=1

×

W
K
Y
Γ(W β) Y
k=1

Γ(β)W w=1·kw
φβ−1+nkw(1)where njkw is the number of word w assigned to topic k in document j, and ‘·’Pmeans a corresponding index is marginalized. In other words, n·kw = j njkw andPnjk· = w njkw . D, K and W indicate the number of documents, the number of
topics, and the size of the entire vocabulary, respectively.
Given the observed words x = {xij }, the task of Bayesian inference is to computethe posterior distribution over the latent topic variable z = {zij }, the per-document
topic distribution θ = {θj } and per-topic word distribution φ = {φk }.
2.2. Collapsed Gibbs Sampling Inference“Collapsed” Gibbs Sampling inference [4] uses the marginalized distribution over x
and z, as follows:p(z, x|α, β) =YY Γ(α + njk· ) YY Γ(β + n·kw )Γ(Kα)Γ(W β)×
Γ(Kα + nj·· )Γ(α)Γ(W β + n·k· ) w
Γ(β)

j

k

k

(2)
Given the current state of all except one topic assignment to a word xij , the conditional probability of zij is given by:¬ijp(zij = k|z¬ij¬ij −1(α + n¬ijjk· )(β + n·kxij )(W β + n·k· ), x, α, β) = PK¬ij
¬ij
¬ij −1
k0 =1 (α + njk0 · )(β + n·k0 xij )(W β + n·k0 · )(3)where n¬ij corresponds to variables or counts excluding xij and zij . The conditional probability specified by Eq. (3) can be used to carry out the Collapsed Gibbs
Sampling inference.
2.3. Collapsed Variational Bayesian Inference
Very recently, Collapsed Variational Bayesian inference (CVB) was proposed andapplied to estimate the LDA model [6]. According to [6], this section briefly describes the CVB method. The CVB method is an algorithm that improves theestimation accuracy in an extension of Variational Bayesian inference (VB) [3]. The
CVB method models the dependence of the parameters on the latent variables, instead of assuming independence. The only assumption made in the CVB method

September 3, 2009

4

16:1

WSPC - Proceedings Trim Size: 9.75in x 6.5in

10-AsoT. Aso & K. Eguchi

is that the latent variables z are mutually independent, thus the posterior can beapproximated as:Yq(z, θ, φ) = q(θ, φ|z)q(zij |γij )(4)
ijwhere q(zij |γij ) is multinomial distribution with parameter γij . The variational freeenergy can be simplified to:F (q(z)) = min F (q(z)q(θ, φ|z)) = Eq(z) [− log p(x, z|α, β)] − H(q(z))
q(θ,φ|z)(5)

Minimizing Eq. (5) with respect to the variational parameters γijk , we get:exp(Eq(z¬ij ) [p(x, z¬ij , zij = k|α, β)])γijk = q(zij = k) = PK
(6)
¬ij , z = k 0 |α, β)])ij
k0 =1 exp(Eq(z¬ij ) [p(x, zPn−1
Using Eq. (2), expanding log Γ(η+n)
l=0 log(η + l) for positive real values η andΓ(η) =
positive integers n, we get:γijk = P¬ij¬ij
exp(Eq(z¬ij ) [log(α + n¬ijjk· ) + log(β + n·kxij ) − log(W β + n·k· )])

¬ij
¬ij
¬ij
k0 exp(Eq(z¬ij ) [log(α + njk0 · ) + log(β + n·k0 xij ) − log(W β + n·k0 · )])(7)

3. Protein-Protein Relationship Prediction based on LDA
The LDA model can represent semantics or concepts that appear in a document.
Therefore, it can be applied to compute likelihood that an entity is related to anotherentity. Using the LDA model, similarity between a pair of entities can be computedby the following equation.
Sim1(ei , ej ) = p(ei |ej )/2 + p(ej |ei )/2.
where p(ei |ej ) is obtained using latent topic k by:Xp(ei |ej ) =p(ei |k)p(k|ej ).

(8)

(9)

k

In [7, 8], Eq. (8) was used to compute similarity between social entities that appear
in newspaper articles; however, we believe that this similarity computation has
some problems. One of the problems is that the similarity largely depends on asmall number of frequently appearing entities. For instance, even when the value ofp(ei |ej ) is very large and p(ej |ei ) is almost zero, the final similarity given by Eq. (8)is still large because this similarity is computed by averaging these two conditional
probabilities.
To address such problems, we define a new method to compute similarity between a pair of entities, as follows:
Sim2(ei , ej ) = p(ei |ej ) × p(ej |ei ).

(10)This equation indicates joint probability of P (ei |ej ) and P (ej |ei ) assuming thatthese are independent of each other.

September 3, 2009

16:1

WSPC - Proceedings Trim Size: 9.75in x 6.5in

10-AsoPredicting PP Relationships Using Latent Topics

5

4. Data and Entity Representation
In this section, we briefly explain GENIA collection and TREC collection that weused for our experiments. Table 1 shows a summary of these datasets.
4.1. GENIA Collection
GENIA collectionb is a subset of MEDLINE formatted in XML, and entities suchas proteins are manually tagged. We removed standard 418 stop words used in“InQuery system” [9], and words and entities that were observed in less than 10
documents (abstracts).
4.2. TREC Collection and GENIA Tagger
Another data collection is TREC collection that was used in TREC Genomic Trackfrom 2004 to 2005, formatted in XML. We extracted titles and abstracts of documents from the collection. First, we used a subset of documents (abstracts) inwhich values in “PubData” and “DataComplete” fields are 2002 for training, andanother subset of documents in which values of these fields are 2003 for testing in
Section 5.2. Second, we removed standard 418 stop-words from the training and test
data, and removed words and entities that were observed less than 10 documentsfrom the training data. In TREC collection, entities are not tagged and thus weidentified biomedical entities using GENIA taggerc .
Table 1.

DW
E
Wf reqEf reqDatasets extracted from GENIA and TREC collection.

Data item nameGENIA

TREC(2002)

TREC(2003)

The number of documents (abstracts)
The number of vocabulary words
The number of vocabulary entities
The total frequency of words
The total frequency of entities

2000
1959
229
107532
9733

33000
16879
1897
3501405
48457

31000
18371058430
3863255
171056

5. Experiments
5.1. Log-Likelihood
We describe the way to compute the log-likelihood of each estimated model. The
larger per-word test-set log-likelihood of estimated model is, the higher the performance of the model is. In this experiment, we computed the log-likelihood of twomodels. One model was estimated by Collapsed Gibbs Sampling inference, and theother was estimated by Collapsed Variational Bayesian Inference (CVB). In theb http://www-tsujii.is.s.u-tokyo.ac.jp/GENIA/home/wiki.cgi
c http://www-tsujii.is.s.u-tokyo.ac.jp/GENIA/tagger/September 3, 2009

6

16:1

WSPC - Proceedings Trim Size: 9.75in x 6.5in

10-AsoT. Aso & K. Eguchi

experiments, we used GENIA collection and 2002’s dataset extracted from TREC
collection. We randomly divided each dataset into 90% and 10%, and we used theformer as training data, and the latter as test data. When we compute the loglikelihood, we set the number of topic of LDA as K = 10. For the hyperparametersof Dirichlet priors, we set α = 0.1 and β = 0.1 [6] for GENIA collection, andα = 50/K and β = 0.1 [8] for the dataset from TREC collection.
For Collapsed Gibbs Sampling inference (GS), given S samples from the posterior, the log-likelihood is given by:p(xtest ) =S
YX 1 Xijkθs φs test
|S| s=1 jk kxij

(11)

β + ns·kw.
W β + ns·k·(12)s
where θjk
and φskw are computed by:s=θjk

α + nsjk·
Kα + nsj··

φskw =For the CVB method, the log-likelihood is computed by:YX
p(xtest ) =θ̄jk φ̄kxtest
ij
ij

(13)

k

where θ̄jk and φ̄kw are computed by:θ̄jk =

α + Eq [njk· ]Kα + Eq [nj·· ]φ̄kw =

β + Eq [n·kw ].
W β + Eq [n·k· ](14)The horizontal axis in Figure 2 (a) and (b) correspond to the number of iterations, the vertical axis corresponds to per-word log-likelihood. The log-likelihoodin Figure 2 (a) was obtained by running each of the two inference algorithms 50
times with different random initializations (S = 50) and averaging the resulting
test-set log-likelihood. Moreover, Figure 3 indicates histograms of per-word testset log-likelihood across 50 random initializations, obtained by the two inference
algorithms using GENIA collection. Comparing with the log-likelihood using Collapsed Gibbs Sampling (GS), that using the CVB method was found larger from10 to 20 iterations; however, it is smaller when more iterations are performed. This
indicates the Gibbs sampling method works better than the CVB method when asufficient number of iterations are carried out, from a viewpoint of log-likelihood (orperplexity) of the estimated models. This result is similar to that was tested using
non-biomedical collections [6]. However, in the following section, we demonstratethat our task-based extrinsic evaluation is not the case.
5.2. Entity-Link Prediction
For evaluation of protein-protein relationship prediction task, we predicted proteinprotein pairs using the LDA model estimated by Collapsed Gibbs Sampling andthat by the CVB method, and the pLSA model, with a couple of different similarity
computations that were described in Section 3. In this experiment, we used EM
algorithm to estimate pLSA.

September 3, 2009

16:1

WSPC - Proceedings Trim Size: 9.75in x 6.5in

10-AsoPredicting PP Relationships Using Latent Topics

7

-6.6
CVB
CGS

CVB
CGS

-7.4

-6.7

log-likelihood

-6.9

-7.8

-8

-7

-8.2

(a) Using GENIA collection.
-7.120(b) Using TREC collection.
-8.4

Fig. 2.

80
100
0
20
40
80
Per-word
test-setlog-likelihood
over a coupleof60collections.

40
60
the number of iterations

100

the number of iterations

10
CVB
CGS
8

6

4

2

-6.70

-6.71

-6.72

-6.73

-6.74

-6.75

-6.76

-6.77

-6.78

-6.79

-6.80

-6.81

-6.82

-6.83

-6.84

-6.85

-6.86

-6.87

-6.88

-6.89

-6.90

0
Histogramsof per-word test-set log-likelihood over GENIA collection.
-6.91

Fig. 3.

-6.92

0

-6.93

log-likelihood

-7.6
-6.8

log-likelihood

5.2.1. Experimental Settings
We used the datasets extracted from TREC collection: 2002’s dataset for training
and 2003’s dataset for testing, as described in Table 1. We generated two types ofentity-entity datasets. One is “true pair” dataset, in which each pair did not cooccur within any document in the training data, but co-occurred within at least one
document in the test data. We removed the entity pairs, one of which entities did
not appear in any document in the training data. The other is “false pair” dataset,in which each pair never co-occurred within any document both in the training
data and the test data. The number of true pairs is equal to that of false pair, as
M = 15494.
In the experiments, we set five different numbers of topics for the LDA modeland the pLSA model: K = 10, 50, 100 and 300. For the hyperparameters of Dirichletprior distributions, we set α = 50/K and β = 0.1 in both algorithms of LDA model
estimation.
5.2.2. Task-based Evaluation
We computed similarity of M true pairs and M false pairs, and ranked 2M total
pairs in descending order of the similarity. We then assumed the top M entity-entity

September 3, 2009

8

16:1

WSPC - Proceedings Trim Size: 9.75in x 6.5in

10-AsoT. Aso & K. Eguchi
Table 2.

K=10
K=50
K=100
K=300

Classification Accuracy.

Table 3.

CGS-LDA

CVB-LDA

pLSA

0.63180.53590.56690.5504

0.63100.6434
0.63830.63170.60750.58290.56480.5293

K=10
K=50
K=100
K=300

Average Precision.

CGS-LDA

CVB-LDA

pLSA

0.67450.65740.64430.62620.66510.68950.69050.68900.63470.59770.56060.5308

Table 4. Comparison of two different similarity computations (in the case of CVB-LDA).

K=10
K=50
K=100
K=300

ClassificationAccuracy

AveragePrecision

Sim1

Sim2

Sim1

Sim2

0.63100.6434
0.63830.63170.6351∗0.66510.68950.69050.68900.6719∗0.6947∗0.6940∗0.68920.6467∗0.6398∗0.6305∗

Note: “*” indicates that the result of Sim2 was 0.05
level significant via Wilcoxon signed rank test, compared to the result of Sim1 with the same topic number.

pairs to be positive, and the other M pairs to be negative. We computed classification accuracy that is given by the proportion of true-positive and false-negative
pairs, changing the parameter K setting, and compared the classification accuracy.
In the experiments, we used two methods to compute the similarity between entity
pairs: one is the existing method presented in Eq. (8) and the other is our method
presented in Eq. (10), and compared the results of these methods.
Table 2 shows the classification accuracy results with each parameter. In thistable, we found that the classification accuracy of the CVB-based LDA worked bestwhen K = 50. The LDA based on CVB worked better than that based on the
Collapsed Gibbs Sampling (CGS) and than pLSA, with 0.05 level significance via
Wilcoxon signed rank test in case of using the optimal topic number in each model.
We further evaluated using average precision [10], which is widely used to evaluate information retrieval. Average precision was computed by averaging precision ateach rank of true-positive entity pairs. In this paper, we sometimes refer to average
precision as “ranking effectiveness” in contrast to classification accuracy. Table 3
shows the evaluated results of average precision with each parameter. Ranking effectiveness of LDA based on CVB worked best when we set K = 100. The resultsof LDA based on CVB were better than the results of Collapsed Gibbs Sampling
inference and than the results of pLSA, both with statistical significance in the samemanner as in the last paragraph.
Table 4 shows that our proposed similarity computation worked better than theprevious one in case of LDA based on CVB, at a statistically significant level of
0.05 in almost every test.

September 3, 2009

16:1

WSPC - Proceedings Trim Size: 9.75in x 6.5in

10-AsoPredicting PP Relationships Using Latent Topics

Fig. 4.

9

An example entity-entity network

5.2.3. Protein-Protein Relationship Network
In the previous section, we investigated how well knowledge contained in the test
data in the year of 2003 can be predicted using the LDA model that was estimatedover the training data in the year of 2002. Figure 4 shows an example of the predicted
protein-protein network using the LDA model with the best condition that wasdetermined by the results in Section 5.2.2. This network consists of top-ranked 50
entity-entity pairs in order of similarity. In the network, vertices represent proteinnames. As for the length of edge, the tighter the relationship between a pair ofvertices connected to an edge is, the shorter the edge will be.
6. Conclusions
In this paper, we presented how to generate hypotheses, especially on proteinprotein relationships, from the biomedical literature using the LDA model, andcompared the LDA model estimated via different inference approaches and thepLSA model. For the LDA model, we investigated a couple of model estimation
methods: one is Collapsed Variational Bayesian method and the other is Collapsed
Gibbs Sampling method. We found that both LDA models worked better than pLSA
in terms of classification accuracy and ranking effectiveness.
We further found that the LDA based on Collapsed Variational Bayesian method
worked better than that based on Collapsed Gibbs Sampling method in terms of theevaluation measures mentioned above. We also proposed a new method to compute
similarity between entities using the LDA model, and indicated that the proposed
method worked better than the previous method. Since our approaches do not
require specific knowledge on target entities, other various types of entities can also
be targeted.
The above-mentioned findings with a couple of inference approaches for the LDA
model were opposite to what was found in terms of test-set log-likelihood, and thus itSeptember 3, 2009

10

16:1

WSPC - Proceedings Trim Size: 9.75in x 6.5in

10-AsoT. Aso & K. Eguchi

suggests that intrinsic evaluation, such as using test-set log-likelihood or perplexity,
does not always indicate the same findings as task-based extrinsic evaluation. Oneof the future tasks is to investigate why this happens, theoretically. Another task is
to combine the Collapsed Variational Bayesian LDA model with non-cooccurrencebased approaches, such as based on natural language processing. Examining how
the topic-based method is actually useful to protein-protein interaction predictionis also left to future work.
Acknowledgements
This work was partially supported by the Grant-in-Aid for Scientific Research (B)(#20300038) from the Ministry of Education, Culture, Sports, Science and Technology of Japan.
References[1] A. M. Cohen and W. R. Hersh. A survey of current work in biomedical text mining.
Briefings in Bioinformatics, 6(1):57–71, 2005.
[2] Deyu Zhou, and Yulan He, Extracting Interactions between Proteins from the Literature. Journal of Biomedical Informatics, No.41, pp. 393–407 (2008).
[3] D. M. Blei, A. Y. Ng, and M. I. Jordan. Latent Dirichlet allocation. Journal of Machine
Learning Research, 3:993–1022, 2003.
[4] T. L. Griffiths and M. Steyvers. Finding scientific topics. Proc. National Academy of
Sciences of the United States of America, 101:5228–5235, 2004.
[5] T.Hofmann, Probabilistic latent semantic indexing. Proceeding of the 22nd International Conference on Research and Development in Information Retrieval, Berkeley,
California, USA, pp. 50–57 (1999).
[6] Y. W. Teh, D. Newman, and M. Welling. A collapsed variational Bayesian inference
algorithm for latent Dirichlet allocation. Advances in Neural Information Processing
Systems, 19:1353–1360, 2007.
[7] D. Newman, C. Chemudugunta, P. Smyth, and M. Steyvers. Statistical entity-topic
models. In Proc. of ACM SIGKDD 2006, pages 680–686, 2006.
[8] M.Steyvers and T.Griffiths, Handbook of Latent Semantic Analysis. chapter 21:Probabilistic Topic Models, Lawrence Erbaum Associates, Mahwah, New Jersey, London(2007).
[9] James P. Callan, W. Bruce Croft and Stephen M. Harding, The INQUERY Retrieval
System. Proceedings of the 3rd International Conference on Database and Expert Systems Applications, Valencia, Spain, pp. 78–83 (1992).
[10] Ricardo Baeza-Yates, and Berthier Ribeiro-Neto, Modern Information Retrieval.
Addison-Wesley (1999).
[11] S. Deerwester, S. T. Dumais, G. W. Furnas, T. K. Landauer, R. Harshman, Indexing
by Latent Semantic Analysis. Journal of the Society for Information Science, 41(6),pp. 391–407 (1990).
[12] Ramin Homayouni, Kevin Heinrich, Lai Wei, and Michael W. Berry, Gene clusteringby Latent Semantic Indexing of MEDLINE Abstracts. Bioinformatics, Vol.21, No.1,
pp. 104–115 (2005).
[13] Hyunsoo Kim, Haesun Park, and Barry L Drake, Extracting Unrecognized Gene
Relationships from the Biomedical Literature via Matrix Factorizations. BMC Bioinformatics, Vol.8 (Suppl 9), No.S6 (2007).