Unsupervised Evidence Integration

Philip M. Long
Vinay Varadan
Sarah Gilman
Mark Treshock
Rocco A. Servedio
Columbia University, 2960 Broadway, New York, NY 10027-6902 USA

Abstract
Many biological propositions can be supported by a variety of different types ofevidence. It is often useful to collect together large numbers of such propositions,
together with the evidence supporting them,into databases to be used in other analyses. Methods that automatically make preliminary choices about which propositions toinclude can be helpful, if they are accurateenough. This can involve weighing evidenceof varying strength.
We describe a method for learning a scoring
function to weigh evidence of different types.
The algorithm evaluates each source of evidence by the extent to which other sources
tend to support it. The details are guided
by a probabilistic formulation of the problem, building on previous theoretical work.
We evaluate our method by applying it topredict protein-protein interactions in yeast,
and using synthetic data.

1. Introduction
Motivation. An ongoing major international effort
has targeted the problem of identifying which pairs ofproteins interact [12, 8, 10, 3]. There are many fundamentally different indications of protein-protein interaction. These include indirect indications, such asa tendency to be synthesized under the same conditions, as well as various high-throughput experimental
techniques that directly test whether pairs of proteins“like” to bind. Jansen, et al [5] showed that it is possible to learn an accurate predictor of protein-protein

interactions in yeast using five attributes of a candidate protein pair, corresponding to a mix of direct andindirect evidence as described above.
Other bioinformatics problems take a similar form.
There are many candidate propositions, and a numberof fundamentally different sources of evidence that canbe evaluated for each. One example is pairing genes
in a newly sequenced genome with their counterpart
human genes.
While databases have been automatically constructedusing multiple sources of evidence (see [12]), it has notbeen obvious how best to automatically weigh the evidence of different types. A natural approach is to learn
the relationship between numerical scores formalizing
the strength of evidence arising from different sources,
and a binary class designation indicating whether thestatement is true or not. Jansen et al [5] learned to
predict protein-protein interactions in yeast this way.
However, it is often not possible to get sufficient training data consisting of examples of this relationship,1
as is the case at present regarding protein-protein interactions in higher organisms [11].
Even when a few “gold standard” designations areavailable, they may be biased in unpredictable ways,
and these biases could skew the results of algorithms
that tried to use them in a supervised analysis. For example, a curated database may tend to be enriched forconclusions that can be drawn on the basis of the mosteasily applied and popular technology. If so, most supervised algorithms would overvalue the attribute corresponding to this “popular” evidence source.
Thus, we are faced with the problem of learning arule for predicting class membership using training
data without class membership information. This can
1Appearing in Proceedings of the 22 nd International Conference on Machine Learning, Bonn, Germany, 2005. Copyright 2005 by the author(s)/owner(s).

plong@cs.columbia.edu
varadan@ee.columbia.edu
srg2104@columbia.edu
mat140@columbia.edu
rocco@cs.columbia.edu

For the case in which the class designation can be observed, sophisticated methods have also been developed(see [4, 2, 7]).

Unsupervised Evidence Integration

also be thought of as the problem faced by clustering algorithms; however, the applications driving thiswork present opportunities and challenges not foundin many clustering problems.
The first opportunity arises from the fact that thevalue of each of the variables can be interpreted as
the strength of evidence of a certain type supporting
the proposition. Consequently, we can assume a priori that the larger the value of a variable, the more
likely it is that the proposition holds. Furthermore, it
is often the case that a number of unrelated sourcesof evidence are available. The approximate independence of the prediction errors resulting from such measures can be exploited by a learning algorithm. (Thiswas exploited by the supervised algorithm for proteinprotein interaction prediction in yeast in the Jansen,
et al paper.) Finally, usually each of the sources of evidence is known to have some utility, so that deciding
which to use and which to discard (“feature selection”)
is unnecessary.
The term “clustering” arises from the fact that in mostclustering applications, members of each class tend to
be grouped together away from the other classes. For
some of the problems targeted in this work, however,the distributions of the values of the variables in thetwo classes overlap significantly. For example, as observed by Atschul [1], the distribution of BLAST scoresof orthologous pairs of genes is approximately uniform
from 0 up to a maximum, whereas the distribution of
BLAST scores for other pairs of genes is approximately
exponential.2
Because of these special characteristics, we prefer not
to think of the problems studied here as clustering
problems; if they are, they form an important typeof clustering problem that merits special attention. In
any case, we compare the method we propose withestablished approaches to clustering.
Our approach. In this paper, we describe a practical method of unsupervised evidence integration inspired by a theoretical analysis.
In the applications targeted in this work, scientists
have sources of evidence that look for fundamentallydifferent kinds of indications that a proposition might
hold, and thus it is reasonable to expect that these evidence sources are approximately independent given
the class designation. Conditional independence isused in our analysis in order to conclude that what
association there is between pairs of variables is dueto their common association with the class designa2Extreme value distributions [6] provide a more detailed
model.

tion, and therefore strong associations are evidence
that the variables are useful. If significant associations among variables are possible due to causes otherthan the common class designation, it would appear
impossible to perform class prediction in an unsupervised manner, which is our goal. We note that (as will
be seen in Section 2) our method includes measuresthat “shrink” estimates toward a default; this may beviewed in part as hedging against limited violations of
independence. Still, the view that the main source ofdependence among variables is their common association with the class designation is central to the designof our algorithm. While this assumption may not holdexactly true in real-world data sets, our experimental
results reported in Section 3 show that our method
does perform very well on natural biological data.
The details of our approach are based on a theoretical analysis that builds on earlier theoretical work by
Mitina and Vereshchagin [9]. In their analysis, in addition to assuming that the values of X1 , ..., Xn areconditionally independent given Y , they also assumed
that• the observed variables X1 , ..., Xn are {0, 1}valued,• each variable is equal to the hidden class designation Y more often than not,• for each i, Pr(Xi 6= Y |Y = y) does not depend ony.
This last property was identified by Mitina andVereshchagin as crucial for their analysis. If independent training examples are generated from a sourcewith these properties, they gave a polynomial-time algorithm that learns a rule for predicting the value ofY that approaches the accuracy of the optimal such
rule.
Some aspects of our application are not captured in
Mitina and Vereshchagin’s setting. For example, someof the variables in our applications are continuousvalued. Even if we were to treat each Xi as a binaryvalued variable by thresholding, it is difficult to do soin such a way that whether this binary-valued variable equals Y is (approximately) independent of thevalue of Y . For these and other reasons, we needed tobuild substantially on Mitina and Vereshchagin’s work
to address our applications.
Our algorithm, like Mitina and Vereshchagin’s, takes
advantage of the fact that a variable is valuable forprediction to the extent that it tends to agree withother variables. We call our new method peer ranking.3
3

Thanks to Vinsensius Vega for suggesting this term.

Unsupervised Evidence Integration

Evaluation. We compare peer ranking with threepossible alternatives. The first is an algorithm that(i) finds the line with the property that projecting theexamples onto that line maximizes the variance, and(ii) then sorts examples according to their positions
on that line. The second is an algorithm (describedin Section 3) based on k-means clustering. The thirduses EM, a standard incremental optimization technique, to search for the maximum likelihood probability model from a set of “naive bayes” models likethose implicitly used by our method. The applications
targeted in this work give rise to inputs with tens of
millions of examples, and possibly more. Thus, direct application of kernel-based or spectral clustering
methods appears infeasible.
Although the peer ranking method is intended to be
applied in an unsupervised setting, to evaluate how
well it works on natural data, it is necessary to apply
it in a situation where a gold standard is available. For
this, we use five sources of evidence of protein-protein
interaction from Jansen, et al’s paper [5]. We also
evaluated the peer algorithm on synthetic randomly
generated data. On both kinds of data, peer ranking also performs substantially better than the othermethods.

2. The peer ranking algorithm
In our problem, an algorithm is given a collection of
examples, each of which is a tuple (X1 , ..., Xn ), andoutputs a scoring function g that is used to rank theexamples. The goal is for examples for which a hidden
variable Y takes the value 1 to be high on the list.
As mentioned in the introduction, the peer ranking
approach is based on a view that the values X1 , ..., Xnof the variables, together with the hidden class designation Y , are generated collectively by a joint probability distribution. The peer algorithm behaves as if
X1 , .., Xn complement one another, in the sense thatthey are conditionally independent given Y . It also
behaves as if Pr(Y = 1|Xi > x) is nondecreasing in x
for all i.
2.1. Outline
The outline of the peer ranking algorithm is as follows:
1. It estimates conditional probabilities relevant to
the predictive ability of binary-valued discretizations of X1 , ..., Xn in a number of rounds: inround number `, ita. chooses a value β` and thresholds b`,1 , ..., b`,nso that for each i, Pr(Xi ≥ b`,i ) ∼ β` (howβ` is chosen, and how exactly b`,1 , ..., b`,n arechosen, are described in Section 2.3),
b. for each i, estimates Pr(Xi ≥ b`,i |Y = 1) andPr(Xi ≥ b`,i |Y = 0) (this is the key step in
the algorithm – how it does this is explainedin Section 2.2).
2. It constructs a scoring function g using the estimates as follows: given an example (X1 , ..., Xn )to be scored, ita. for each i, finds the largest member b of
Bi = {b1,i , b2,i , ...} for which Xi ≥ b (callit floorBi (Xi )), andb. sets g to be an estimate ofPr(Y = 1|X1 ≥ floorB1 (X1 )∧...∧Xn ≥ floorBn (Xn ))obtained from the previously constructedconditional probability estimates (how this isdone is described in Sections 2.7 and 2.8).
2.2. The basic estimates
In this subsection we concentrate on a particular iteration of step 1, i.e. a particular value of `. Since ` is
fixed, we drop it from all notation.
Define U1 , ..., Un by letting Ui be 1 if Xi ≥ bi , and0 otherwise. Each value Ui can be viewed as a (veryrough) prediction of Y , since by assumption the examples with large values of Xi are those examples
that the ith source of evidence views as most likely
to have Y = 1. The value of bi is chosen so that
Pr(Ui = 1) = Pr(Xi ≥ bi ) is approximately β (howthis is done is described in Section 2.3), but if, forexample, the distribution of Xi has an accumulation
point (that is, many examples have the same value for
Xi ), then this probability may not actually be very
close to β. Note that if we have a lot of training data,
the fraction of examples in our training set for which
Ui = 1 provides an accurate estimate of the true valueof Pr(Ui = 1).
We emphasize the difference between Xi and Ui : Xi isa (possibly continuous) value that is interpreted as thestrength of evidence of the ith type, and Ui is a binaryvalued prediction obtained by examining whether Xi
is large enough.
Suppose for a moment that we know Pr(Y = 1) (howto estimate it will be treated in Section 2.4). Since
Pr(Ui = 1|Y = 0) equals
Pr(Ui = 1) − Pr(Y = 1) Pr(Ui = 1|Y = 1),
1 − Pr(Y = 1)

(1)

if we have an estimate of Pr(Ui = 1|Y = 1), we canuse it to obtain an estimate of Pr(Ui = 1|Y = 0).

Unsupervised Evidence IntegrationIf, in addition, the number n of variables is at least
3, then in fact we can estimate Pr(Ui = 1|Y = 1) bylooking at the extent to which pairs of variables agree
that Y = 1. This is because for any three distinct
indices i, j, k we have
Pr(Ui =
1|Y = 1)s
1−Pr(Y = 1) (ai,j −ai aj )(ai,k −ai ak )= ai +
Pr(Y = 1)
aj,k −aj ak(2)
where ai denotes Pr(Ui = 1) and ai,j denotes Pr(Ui =1 & Uj = 1). The straightforward but tedious derivation of (2) is in Appendix A.
The most natural estimate of ai,j = Pr(Ui = 1 & Uj =1) is the fraction of training examples for which both
Ui = 1 and Uj = 1. Indeed this, and the corresponding estimate of ai,k , are plugged into the numerator in (2) to estimate Pr(Ui = 1|Y = 1) in
our algorithm. However, estimation of the probability aj,k = Pr(Uj = 1 & Uk = 1) in the denominatorrequires special treatment. Note that underestimatesof this quantity can have a radical effect on the resulting estimate of Pr(Ui = 1|Y = 1), as they canbring the denominator close to 0. Thus our algorithm
adjusts the estimate of aj,k upwards by the width of
a 95% confidence interval around the empirical estimate, to make it unlikely that aj,k is underestimated,
and to reduce the extent of such underestimation when
it occurs. Specifically, if qj,k is the fraction of training
examples for which Uj = 1 and Xk ≥ bk , then ourestimate âj,k is given byr
qj,k (1 − qj,k ),(3)âj,k = qj,k + 1.96mwhere m is the number of training examples. This adjustment also has the effect of bringing Pr(Ui = 1|Y =1) closer to Pr(Ui = 1), that is, moderating any optimism about utility of the ith variable.
Estimates of Pr(Ui = 1|Y = 1) can be constructedin this way using any other pair {j, k} of variables.
The role that a particular pair plays is determined inpart by the fractions qj and qk of training examples forwhich Uj = 1 and Uk = 1 respectively. The estimatesobtained from other pairs are combined as follows:• for all pairs {j, k} of other variables for whichqj,k > qj qk , qi,j > qi qj and qi,k > qi qk ,(4)

and estimate of Pr(Ui = 1|Y = 1) is constructedusing using variables j and k as outlined above,and• the median of the resulting estimates is used as
the final estimate.

This further enhances the robustness of the method
against departures from the conditional independence
assumption. In the unlikely but conceivable event thatno pair {j, k} satisfies (4), then Pr(Ui = 1|Y = 1) isestimated to be Pr(Ui = 1) (that is, Ui is estimated to
be useless for prediction).
2.3. Choosing values for β and b
In round `, the peer algorithm chooses thresholdsb`,1 , ..., b`,n so that, for each i, the fraction of examples for which Xi ≥ b`,i is as close as possible to β`
subject to the constraint that the fraction is at leastβ` . (Note that many examples might share the samevalue of Xi .)As described above, the event that Xi ≥ b`,i can beviewed as a rough prediction of the event that Y = 1;
in order for this prediction to be as accurate as possible we would like to have Pr[Xi ≥ b`,i ] ≈ P r[Y = 1].
Since, in many applications, Pr(Y = 1) is small, thevalues of β` are chosen according to a geometric progression, so that the region near 0 is populated more
densely. Specifically, the value of β is doubled eachtime, so that β` = β1 2`−1 .
We set β1 = 1/m because we cannot measure probabilities at a finer granularity from m examples.
2.4. Estimating Pr(Y = 1)
The ordering output by the algorithm should be expected to be insensitive to its estimated value of
Pr(Y = 1): the main effect of changing its value will be
to shift all estimates of conditional probabilities up or
down, leaving the order largely unchanged. The valueof Pr(Y = 1) is therefore estimated in a rough way,by examining the consequences of plugging different
estimates into (1) and (2).
If an estimate is too small, then plugging into (2) will
result in estimates of Pr(Xi ≥ bi |Y = 1) that are toolarge. In extreme cases, they can be greater than 1. On
the other hand, using estimates of Pr(Y = 1) that are
too large with (1) can result in estimates of Pr(Xi ≥bi |Y = 0) that are too small, and, in extreme cases, lessthan 0. The value of Pr(Y = 1) is chosen to maximize
the margin by which both of these illogical outcomesis avoided. This maximum margin might be viewed asa crude, but computationally feasible, approximation
to maximum likelihood.
2.5. Clipping
Intuitively, the training data can only provide information about probabilities at a granularity inversely
proportional to the number of training examples. Con-

Unsupervised Evidence Integration

ditional probability can be informed only at a coarser
granularity. Thus, we clip all probability estimates tofall between 1/m and 1−1/m (and any other estimates
are replaced with the closest value in that range).
2.6. Enforcing monotonicity
Recall that, in the intended applications, we expectthat Pr(Y = 1|Xi ≥ b) is nondecreasing in b. On
the other hand, our adjustment (3) results in a bias
toward conservatism. While, overall, this helps, one
unfortunate side effect is that our estimates of Pr(Y =1|Xi ≥ b) might not be monotone in b. An estimate ofPr(Y = 1|Xi ≥ b) for large b might be based on only a
few cases, and so the algorithm would conservatively
adjust this estimate downward. There might be b0 < b
for which, due to a larger number of cases for which
Xi ≥ b0 , the algorithm might be able to confidently
assert a large value of Pr(Y = 1|Xi ≥ b0 ). But in suchcases, the monotonicity implies that the algorithm canconclude that Pr(Y = 1|Xi ≥ b) is at least as big.
This reasoning is incorporated into the peer ranking
algorithm in a postprocessing step, in which pairs of
estimates that conflict with the monotonicity assumption are resolved in favor of the more confident estimate.
2.7. Preliminary scoring function
Recall from Section 2.1 that the scoring function is
obtained by evaluating an estimate ofPr(Y = 1|X1 ≥ floorB1 (X1 ) ∧ ... ∧ Xn ≥ floorBn (Xn ))where each Bi is made up of the thresholds b`,i for theuseful rounds `. Exploiting the conditional independence assumption in a standard way, we can see thatthe above conditional probability is monotone in
X
i

log

Pr(Xi ≥ bi |Y = 1).
Pr(Xi ≥ bi |Y = 0)

(5)

Since our ultimate goal is to order the examples basedon their values of X1 , ..., Xn , any two scoring functions
are equivalent if they order the examples in the sameway, and thus we can perform any monotone transformation on our scoring function. The derivation of (5)is standard (omitted due to space constraints).
Plugging our estimates of Pr(Xi ≥ bi |Y = 1) andPr(Xi ≥ bi |Y = 0) for various i into (5), we obtainour preliminary scoring function.
2.8. Final, smoothed, scoring function
A drawback of the scoring function f described in Section 2.7 is that, when used for sorting, it can result in

Figure 1. An example of the definition of the function gi
mapping the value of a variable Xi to its contribution tothe overall score: gi is a continous, piecewise linear approximation to the function fi .

many ties (cases where two propositions are assigned
the same score). Note that (5) expresses f as a sum
over functions that depend on individual variables; let
us denote by fi the function that depends on variable i.
Each of f1 , . . . , fn is monotone and piecewise constant.
The final scoring function g used by the peer ranking
algorithm is obtained by replacing each fi with a corresponding piecewise linear function gi and lettingX
g(X1 , ..., Xn ) =gi (Xi ).
iA representative example of how gi is generated fromfi is shown in Figure 1: The value of gi at a thresholdis the average of the values of fi on either side, and gi
interpolates linearly between.
2.9. Discussion – why not use bins?
An arguably more principled approach would be touse the members of each Bi to divide the real line into
bins, and then design the scoring function by evaluating the conditional probability that Y is 1 given thebin memberships of the values of the variables. However, the individual conditional probabilities that values fall in bins given that Y is 1 and 0 respectively are
estimated with too high a variance for this to work.
The probability that an example falls in a bin is thedifference between the probability that it falls to theright of the right endpoint, and the probability that if
falls to the right of the left endpoint. The estimate of
the bin probability is thus sensitive to fluctuations inboth these probability estimates. We have found thatthe approach we suggest works better, we suspect inlarge part because only one of these probabilities is
estimated.

Unsupervised Evidence Integration

We note since the peer algorithm chooses thresholds
geometrically, many of the examples for which Xi ≥b`,i also satisfy Xi ∈ [b`,i , b`−1,i ]. Thus, it is reasoni ≥bi |Y =1)
able to view Pr(X
Pr(Xi ≥bi |Y =0) as an approximation to thecorresponding ratio for the bin with left endpoint bi .

gle binary-valued hidden variable, and regards thediscretized observed variables as conditionally independent given the hidden variable. It uses EM
to attempt to find the maximum likelihood modelin this class.

Alternatively, note that, if a scientist is able to identify a null distribution that matches the conditional
distribution given that Y = 0, then Pr(Xi ≥ b|Y = 0)
is the p-value associated with the case where Xi = b.
So the peer method may be viewed as going beyond
combining p-values to also estimate the corresponding
conditional distributions given that Y = 1.

3. It defines the Y = 1 cluster to be the one forwhich most variables are more likely to take theirlargest value.

3. Experiments
We evaluated the peer ranking algorithm by applying
it to predict protein-protein interactions in yeast, andon artificial data. The results are summarized in Table 1.
3.1. Other algorithms
We compare the peer algorithm with three standard
methods that are feasible with large datasets like thosethat arise in the targeted applications.
The first algorithm (“k-means algorithm”)
1. performs k-means clustering with k = 2,
2. defines the Y = 1 cluster to be the one with the“larger” center (the center with the larger valueon the majority of the variables),3. ranks propositions by how much closer they areto the center of the Y = 1 cluster than the othercluster center.
The second algorithm (“EM algorithm”) proceeds asfollows:
1. It discretizes the data by dividing the values ofthe variables into bins roughly as in the peer algorithm: for each variable i, if the examples are
sorted in order of the values of variable j, then thejth bin boundary is placed after example number 100 · 2j . If the next example takes the samevalue, the boundary is placed after the last example with that value. (As in the peer algorithm,
more boundaries are placed near the top because
the minority class is small, and large values of thevariables are associated with membership in theminority class.)
2. It learns a Naive Bayes probability model for thediscretized data: i.e., the model includes a sin-

4. It ranks propositions by evaluating the conditional probability that Y = 1 given the discretizedvalues of their variables.
The third algorithm (“eigen algorithm”)
1. estimates the covariance matrix C of X1 , ..., Xn ,2. finds the eigenvector (w1 , ..., wn ) of C with thelargest eigenvalue, and3. ranks propositions by w1 X1 + ... + wn Xn .
Because the datasets targeted in this work are toolarge to fit in memory, the run-times of the algorithms
are dominated by the number of passes required overthe data. The eigen algorithm makes two passes overthe data, one to estimate the covariance matrix, andone to compute the scores. The peer algorithm needs
to sort the values of each attribute, then make anotherpass to collect statistics, followed by a pass to computescores. The k-means and EM algorithms need to makea pass over the data for each iteration, making themmuch slower than the eigen and peer algorithms. It
was infeasible for us to perform our experiments whileallowing these algorithms to run all the way to convergence: we limited the number of iterations of eachalgorithm to 20, still allowing the iterative algorithms
much more time than the peer and eigen algorithms.
3.2. Protein-protein data
To evaluate algorithms, we need data with goldstandard indications of the truth or falsehood of the
propositions they are predicting. It is worth emphasizing that the purpose of this analysis is to evaluate
the algorithms, and not to discover new biology.
We used data provided with a paper by Jansen, et al[5] on predicting protein-protein interactions in yeast.
Their analysis used the following sources of evidence
of interaction: (a) the outcome of yeast two-hybrid experiments, high-throughput experiments in which candidate pairs of proteins are brought close to one another, with molecular machinery attached that reports
whether they appear to have bound, (b) the outcome

Unsupervised Evidence Integrationof in-vivo pulldown experiments, in which scientists
attempt to catch protein pairs in the act, by grabbing
complexes (groups of interacting proteins), and characterizing them e.g. by breaking them into pieces andweighing the parts, (c) the tendency to be produced
or not coordinately across a variety of conditions, (d)similar functional annotations in public databases, and(e) whether both are essential or not.
We used the raw variables from the Jansen, et al
study exactly as we found them, with the following
exceptions: (a) We summed the indicator variables
corresponding to the results of two yeast two-hybrid
screens, obtaining a single {0, 1, 2}-valued yeast twohybrid variable, (b) we analogously summed the two
in-vivo pulldown variables, and (c) we took the reciprocals of the two functional annotation raw variables(to obtain values that increase with the likelihood ofinteraction, and are on a similar scale to the other variables) and added them to obtain a single functional annotation variable. Missing values were replaced with0.
We downloaded the gold-standard indications of interaction from the web site of the Jansen, et al paper: these were obtained from the curated MIPS data.
Jansen, et al, also determined a list of proteins regarded as not interacting by finding pairs that are annotated as localizing to different parts of the cell in
the GO database. Of the 24229603 protein pairs in
the dataset, 2713970 are given gold standard designations this way, 8250 annotated as interacting and therest not. (In the raw data from the Jansen, et al web
site, 124 protein pairs appeared both in the list of interacting proteins, and in the list of negative examples
arising from the localization evidence. These protein
pairs were regarded as interacting in our evaluation.
This appears the most logical choice, but due to theirsmall number, this choice must have an insignificant
effect on our evaluation anyway.)
We applied the peer algorithm, and the four algorithms
we compare with, to the set of 24229603 protein pairs
with data from that paper, and evaluated them bycomputing ROC scores (also known as the AUC, forArea Under the Curve) on the 2713970 gold-standard
examples. The results are tabulated in Table 1. Because the iterative algorithms use random starting configurations, their results are averaged over 5 runs.
For a given value a of the AUC, 1 − a can be viewed
as an error probability: it is the probability that arandomly chosen true proposition is ranked below arandomly chosen false proposition. On the proteinprotein data, the peer algorithm reduces this error
probability by more than a factor of two compared

Algorithm
Peer
Eigen
k-means
EM

Protein-Protein
0.947
0.862
0.862
0.848

Synthetic
0.977
0.899
0.724
0.911

Table 1. AUC scores on protein-protein and synthetic data.

with the other algorithms. With 8250 positive examples, this difference is highly statistically significant.
3.3. Synthetic data
We also tried out the algorithms on artificially generated data. An obvious advantage of such data is thatthe correct class of an item can be determined without question. In our data, X1 , ..., Xn are conditionallyindependent given Y . The probability distributions
governing the individual variables were inspired by thehigh-level description of BLAST scores described by
Altschul [1]: when Y = 1, Xi is distributed uniformly
on [0, 1], and when Y = 0, Xi is distributed according to an exponential distribution that has been truncated at 1 and normalized (so that Pr(Y = 1|X ≥ b)
is monotone in b). To generate variables with varying
strengths, the means of the exponential variables werechosen uniformly at random from [0,1/2]. The value
1/2 was chosen to generate variables with strong but
not overwhelming association with Y .
We generated 100 random sources with five variables
and Pr(Y = 1) = 0.01 this way. For each source, we
generated 100000 examples, tried all the algorithms,
and calculated the AUC for each algorithm. For eachalgorithm, we then averaged the AUC scores.
3.4. Code and data
On the website
http://www.cs.columbia.edu/~plong/peer
the following can be found: source code for all the algorithms, the protein-protein data used in our analysis,
scripts to generate the synthetic data, and a script toreproduce the results of this section.

Acknowledgments
We warmly thank Edison Liu, Yoav Freund, Vinsensius Vega, K. R. Krishna Murthy, Anshul Kundaje,
John Rice, Prasanna Kolatkar, Peter Bickel, Drew
Bagnell, Naoki Abe, David Haussler and Bin Yu forvaluable conversations.

Unsupervised Evidence Integration

References

A. Derivation of equation (2)[1] S. Altschul. Assessing the accuracy of databasesearch methods,and improving the performanceof psi-blast, 2002. Invited talk at ISMB.

Define[2] M. Deng, T. Chen, and F. Sun. An integrative analysis of protein function prediction. RECOMB, pages 95–103, 2003.
[3] C. Alfarano et al. The biomolecular interaction
network database and related tools. Nucleic Acids
Res., 33:D418–D424, 2005.
[4] Y. Freund, R. Iyer, R.E. Schapire, and Y. Singer.
An efficient boosting algorithm for combining
preferences. In Proc. 15th International Conference on Machine Learning, 1998.
[5] R. Jansen, H. Yu, D. Greenbaum, Y. Kluger, N. J.
Krogan, S. Chung, A. Emili, M. Snyder, J. F.
Greenblatt, and M. Gerstein. A bayesian networks approach for predicting protein-protein interactions from genomic data. Science, 302:449–
453, 2003.
[6] S. Karlin and S. F. Altschul. Method for assessing the statistical significance of molecular sequence features by using general scoring schemes.
Proceedings of the National Academy of Sciences,
87:2264–2268, 1990.
[7] G. R. G. Lanckriet, M. Deng, N. Cristianini, M. I.
Jordan, , and W. S. Noble. Kernel-based data fusion and its application to protein function prediction in yeast. PSB, 2003.
[8] E. M. Marcotte, M. Pellegrini, H. L. Ng, D. W.
Rice, T. O. Yeates, and D. Eisenberg. Detecting
protein function and protein-protein interactions
from genome sequences. Science, 285(5428):751–
3, 1999.
[9] O. Mitina and N. Vereshchagin. How to use several noisy channels with unknown error probabilities. Information and Computation, 184(2):229–
241, 2003.
[10] I. M. Nooren and J. M. Thornton. EMBO J.,
22(14):3486–92, 2003.
[11] C. Von Mering, R. Krause, B. Snel, M. Cornell,
S. G. Oliver, S. Fields, and P. Bork. Comparative assessment of large-scale data sets of proteinprotein interactions. Nature, 417:399–403, 2002.
[12] I. Xenarios, D. W. Rice, L. Salwinski, M. K.
Baron, E. M. Marcotte, and D. Eisenberg. DIP:
The database of interacting proteins. Nucleic
Acids Research, 28:289–91, 2000.

• θi = Pr(Ui = 1|Y = 1), and• p = Pr(Y = 1).
By breaking down into the cases in which Y = 1 andY = 0, we get
ai,j = Pr(Ui = Uj = 1|Y = 0) Pr(Y = 0)
+ Pr(Ui = Uj = 1|Y = 1) Pr(Y = 1).

(6)

Exploiting the conditional independence, we get
ai,j = Pr(Ui = 1|Y = 0) Pr(Uj = 1|Y = 0) Pr(Y = 0)
+ Pr(Ui = 1|Y = 1) Pr(Uj = 1|Y = 1) Pr(Y = 1).
(7)
Equation (1) can be rewritten using this section’s notation as follows:ai − pθi.
(8)
Pr(Ui = 1 | Y = 0) =1−pCombining (7) and (8) with the fact that Pr(Y = 0) =1 − Pr(Y = 1), and simplifying, we get
ai,j =(ai − pθi )(aj − pθj )+ θi θj p.
1−p

(9)

Similarly,
ai,k

=

aj,k

=

(ai − pθi )(ak − pθk )+ θ i θk p
1−p
(aj − pθj )(ak − pθk )+ θj θk p.
1−p

(10)
(11)

Solving (9) for θj , we getθj =aj (θi p − ai ) + ai,j (1 − p).
p(θi − ai )(12)

Replacing the occurrence of θj in (11) with the righthand-side of (12) and simplifying yields
aj,k =

ai,j ak − aj ak θi − ai,j θk + ai aj θk.
ai − θ i(13)

Solving (13) for θk and simplifying, we getθk =−ai aj,k + ai,j ak + aj,k θi − aj ak θiai,j − ai aj(14)

Replacing the θk in (10) with the right-hand-side of(14), and simplifying, yields
ai,k = a2i (aj,k p − aj ak ) + (aj,k − aj ak )pθi2
+ai (ai,j ak (1 − p)− 2(aj,k − aj ak )pθi ) /(ai,j − ai aj )(1 − p) .
(15)
Solving for θi and simplifying completes the proof.