Supervised Hypothesis Discovery Using Syllogistic Patterns in the Biomedical Literature

1 Introduction

The amount of scientific knowledge is rapidly growing beyond the pace one could digest. For example, Medline, 1 the most comprehensive bibliographic database in life science, currently contains over 19 million references to journal articles and 2,000-4,000 completed references are added each day. Given the substantial volume of the publications, it is virtually impossible for individuals to deal with the information without the aid of intelligent information technologies, such as information extraction [Bj¨orne et al., 2010] and text data mining (TDM) [Ananiadou et al., 2006; Kostoff et al., 2009].

TDM aims to discover heretofore unknown knowledge through an automatic analysis on textual data. A pioneering work in TDM, also known as literature-based discovery or hypothesis discovery, was conducted by Swanson in the 1980's. He argued that there were two premises logically connected but the connection had been unnoticed due to overwhelming publications and/or over-specialization. To demonstrate the validity of the idea, he manually analyzed a number of articles and identified logical connections implying a hypothesis that fish oil was effective for clinical treatment of Raynaud's disease [Swanson, 1986]. The hypothesis was later supported by experimental evidence [Digiacomo and adn Dhiraj M. Shah, 1989].

1 http://www.ncbi.nlm.nih.gov/entrez

This study is motivated by the series of Swanson's work [Swanson, 1987; 1988; 1990; Swanson et al., 2006] and attempts to advance the research in hypothesis discovery. Specifically, we aim to address two problems that the existing work has generally suffered from. One is the unknown nature of a generated hypothesis. Most approaches only identify two potentially associated concepts, leaving the meaning of the association unknown, which requires experts to interpret the hypothesis. This vagueness has significantly limited the utility of hypothesis discovery. To cope with the problem, we derive hypothesis generation rules from numerous known facts or relations extracted from the scientific literature. Each rule explicitly states the meaning of an association as a predicate and is able to produce an interpretable hypothesis in the form of "N1 V N2", where N and V denote a concept (noun phrase) and a predicate (verb phrase), respectively.

The second problem is the large number of generated hypotheses. Typically, most of the hypotheses are spurious and only a small fragment is worth further investigation. Because the latter is far outnumbered by the former and thus is difficult to find, it is crucial to prioritize or rank the hypotheses according to their plausibility. To this end, we first identify true associations among the automatically generated hypotheses and learn their characteristics by adopting a semi-supervised regression model. To build an effective model, we explore several types of features, including the reliability of the hypothesis generation rules, the semantic similarities between concepts, and specificity of concepts. Through a series of experiments on the Medline bibliographic database, we demonstrate the validity of the proposed framework for generation and prioritization of interpretable hypotheses.

2 RelatedWork

Swanson has argued the potential use of a literature to discover new knowledge that has implicitly existed but been overlooked for years. His discovery framework is based on a syllogism. That is, two premises, "A causes B" and "B causes C," suggest a potential association, "A causes C," where A and C do not have a known, explicit relationship. Such an association can be seen as a hypothesis testable for verification to produce new knowledge, such as the aforementioned association between Raynaud's disease and fish oil. For this particular example, Swanson manually inspected two groups of articles, one concerning Raynaud's disease and the other concerning fish oil, and identified premises that "Raynaud's disease is characterized by high platelet affregability, high blood viscosity, and vasoconstriction" and that "dietary fish oil reduces blood lipids, platelet affregability, blood viscosity, and vascular reactivity," which together suggest a potential benefit of fish oil for Raynaud's patients. Based on the groundwork, Swanson himself and other researchers developed computer programs to aid hypothesis discovery. The following summarizes some of the representative studies.

Weeber et al. [2001] implemented a system, called DADsystem, taking advantage of a natural language processing tool. The key feature of their system is the incorporation of the Unified Medical Language System (UMLS) Metathesaurus 2 for knowledge representation and pruning. While the previous work focused on words or phrases appearing in Medline records for reasoning, DAD-system maps them to a set of concepts defined in the UMLS Metathesaurus using MetaMap [Aronson, 2001]. An advantage of using MetaMap is that it can automatically collapse different wordforms (e.g., inflections) and synonyms to a single Metathesaurus concept. In addition, using semantic types (e.g., "Body location or region") under which each concept is categorized, irrelevant concepts can be excluded from further exploration if particular semantic types of interest are given. This filtering step can drastically reduce the number of potential associations, enabling more focused knowledge discovery. Pratt and Yetisgen-Yildiz [2003]'s system, LitLinker, is similar to Weeber's, also using the UMLS Metathesaurus but adopted a technique from association rule mining [Agrawal et al., 1996] to find two associated concepts.

Srinivasan [2004] developed another system, called Manjal, for hypothesis discovery. A primary difference of Manjal from the others is that it solely relies on MeSH 3 terms assigned to Medline records, disregarding all textual information. MeSH is a controlled vocabulary consisting of sets of terms (MeSH terms) used to manually indexing articles in life science. Manjal conducts a Medline search for a given concept and extracts MeSH terms from the retrieved articles. Then, according to predefined mapping, each of the extracted MeSH terms is associated with its corresponding UMLS semantic types. Similar to DAD-system, the subsequent processes can be restricted only to the concepts under particular semantic types of interest, so as to narrow down the potential pathways. In addition, Manjal uses the semantic types for grouping resultant concepts in order to help users browse the system output.

More recently, Liu et al. [2011] proposed an approach to hypothesis discovery based on hypergraphs. In the approach, concepts and their direct associations (co-occurrences) are represented by nodes and edges, respectively, and the strength of direct/indirect associations between two concepts were defined using their commute time (taken for a random walk to make a round trip between two nodes) or inner product. They evaluated the approach on synthetic small data, along with shopping basket and clinical note data, and showed that Swanson's hypothesis regarding fish oil can be replicated.

2 http://www.nlm.nih.gov/research/umls/

3 http://www.nlm.nih.gov/mesh/

Despite the prolonged efforts, however, the research in hypothesis discovery is still at an early stage of development, leaving much room to improve. Most of the previous works only suggest two concepts indirectly associated without indicating their nature of the association. Also, their evaluation was typically limited only to a small number of known hypotheses reported in Swanson's work. In contrast, this study proposes a novel approach to generating and ranking hypotheses with explicit meaning and quantitatively evaluates them against a number of known associations automatically extracted fromMedline.

3 Proposed Framework

The proposed framework is roughly divided into two parts. One is hypothesis generation and the other is learning true hypotheses. The former first derives hypothesis generation rules based on known facts or relations represented in predicate argument structure extracted from a corpus of texts and then generates potential hypotheses by applying the acquired rules to known relations. The latter uses true hypotheses as positive examples for learning a regression model and applies it to the generated hypotheses for prioritization according to their plausibility. Figure 1 illustrates the overview of the framework. The following sections describe each component depicted in the figure by roughly following the flow of the processes/data.

3.1 Deriving Hypothesis Generation Rules

Much previous work generates hypotheses simply based on co-occurrences of two terms or concepts. Although such approaches may produce valid hypotheses, they also produce even more spurious ones, making it more difficult to spot truly important hypotheses. This study takes into account the meaning of the relation between two concepts instead of their simple co-occurrence and only produces more reasonable hypotheses in consideration of the existing knowledge. In this study, each known relation extracted from the existing knowledge is expressed as a predicate-argument structure "N1 V N2", where V is a predicate and N1 and N2 are subjective and objective arguments, respectively. Based on the same arguments, these relations are merged to identify a chain of relations described shortly to derive a hypothesis generation rule.

Knowledge Extraction

To extract known relations from the literature, this study relies on publicly available NLP tools, specifically, a shallow syntactic parser and a named entity (NE) recognizer. Based on the former's output, predicate-argument structure is identified. For example, from a sentence "the guideline is being reexamined currently by the NCRP committee", a relation 〈the guideline, is being reexamined currently by, the NCRP committee〉 is extracted. In addition, the following preprocessing is applied in this order to normalize the representation.

• Transform all the terms to their base forms.
• Remove all articles.
• Replace negative adverbs (e.g., barely) with "not"
• Remove all adverbs (except for "not").
• Remove the relation itself if auxiliary verb is uncertain ("may" or "might").
• Remove auxiliary verb.
• Remove present/past/future tense.
• Transform passive voice to active.

For the above example, the extracted relation is finally normalized to 〈NCRP committee, reexamine, guideline〉.

An NE recognizer identifies biomedical entities, including proteins and RNA. We retain only relations containing at least one such entity, which would help to generate biomedically meaningful hypotheses. Hereafter, the set of extracted relations is refereed to as the knowledge base, denoted as K.

Rule Induction and Hypothesis Generation

From the knowledge base K, a hypothesis generation rule r is derived as a sequence of three predicates V1, V2, V3. The basic idea is to identify a syllogistic pattern composed of three relations corresponding to two premises and one conclusion in Swanson's syllogism (see Section 2) by merging the same arguments. For example, suppose that two relations were extracted from the literature: "N1 inhibits N2" and "N2 directs N3". The objective and subjective arguments of the former and latter, respectively, are the same (i.e., N2) and thus form a chain of two relations by merging them: "N1-inhibit-N2direct-N3". Here, the previous work in hypothesis discovery may suggest that N1 and N3 have some implicit association without being able to specify the meaning of the association. In contrast, we take a further step to search for another relation involving N1 and N3, such as "N1 impairs N3" in the knowledge base K. 4 This time, the subjective and objective arguments are the same as those of the first two relations, respectively. Further merging the arguments produces a triangular chain of relations as shown in Figure 2.

These known relations collectively suggest that a general rule r below may hold:

Rule r: If "x inhibits y" and "y directs z", then "x impairs z",

where x, y, and z can be any noun phrases. Note that the rule only indicates a possible association that may be invalid. However, because the possible association follows a more reasonable logic than mere co-occurrence-based approaches, fewer spurious hypotheses would be expected than the previous work.

These rules, denoted as R = {r1, r2, · · ·}, can be easily identified by first finding two predicate-argument structures that share the same argument as the object and subject (i.e., N2), and then finding another predicate-argument structure having the other two arguments (N1 and N3) as its subject and object. Here, it should be mentioned that rule r also keeps the information on N1, N2, and N3 for reasons described in Section 3.2. Once such rules R are exhaustively identified in the knowledge base K, they can be applied back to K to generate hypotheses, denoted as H = {h1, h2, · · ·} where h is a generated hypothesis. Let us stress that, in the hypothesis, the exact meaning of the association between two concepts is explicitly stated as a predicate (i.e., "impair" in the above example).

3.2 Learning True Hypotheses

The number of hypotheses |H| to be generated from the rules R will be much smaller than co-occurrence-based approaches adopted by the previous work. Still, there will be many hypotheses that hinder manual investigation. Therefore, it is crucial to prioritize or rank the generated hypotheses by considering their plausibility. To this end, we attempt to learn the characteristics of the "true" hypotheses using a supervised learning framework and predict a plausibility or confidence of each generated hypothesis h. Specifically, we take the following three steps: identification of true hypotheses, feature extraction, and PU learning, each described below.

4 In fact, three relations, "actinomycin D inhibits mRNA", "mRNA directs protein synthesis", and "actinomycin D impairs protein synthesis", were extracted from Medline.

Identification of True Hypotheses

For applying supervised learning, there need to be labeled examples, i.e., true and false hypotheses in this case. Such labeled examples are often manually created in many classification/regression tasks, such as spam filtering. However, it is not realistic to manually judge the validity of the generated hypotheses since it may require domain expertise, extensive reading, and even laboratory experiments. Instead, we take advantage of the biomedical literature more recent than those used for rule induction and hypothesis generation. In other words, if a generated hypothesis is found in the recent literature, the hypothesis can be seen as a validated, true hypothesis.

Specifically, we first split the knowledge base K into three subsets: K1,K2,K3 with Ki being the ith oldest set of knowledge. Then, K1 is used for inducing the rules, denoted as R1, and then for generating hypotheses, denoted as H1. Among H1, true hypotheses are identified using more recent knowledge K2. Note that the remaining, newest knowledge K3 will be held for evaluation as described later.

A potential problem of this approach is that the hypotheses not found in K2 cannot be simply regarded as false hypotheses. This is because it is possible that they are actually true hypotheses but not yet appear in the literature. In other words, definite negative examples are difficult to identify. To cope with this issue, we see the non-true, inconclusive hypotheses as "noisy" data containing both true and false hypotheses and adopt a learning approach using positive and unlabeled examples, so called PU learning. Specifically, this study adopts an existing approach proposed by Lee and Liu [Lee and Liu, 2003], which considers PU learning as a problem of learning with noise by labeling all unlabeled examples as negative and learns a linear regression model.

Feature Extraction

To apply a supervised learning method, each hypothesis (instance) needs to be represented by a set of features that possibly reflect the characteristics of true/false hypotheses. There are two types of information that can be used to predict the plausibility of hypothesis h generated by a rule r. One is associated with r itself and the other is associated with r and h. In the following, the former is called rule-dependent features, and the latter rule/hypothesis-dependent features. Note that a rule is represented by a sequence of verbs (V1, V2, V3) but retain the noun phrases (N1, N2, N3) in the syllogistic pattern from which it is derived so as to obtain some of the features.

For the rule-dependent, this work uses the features summarized below.

• The number of syllogistic patterns that resulted in the same rule (V1, V2, V3). If multiple patterns lead to the same rule, it is thought to be more reliable.
• Specificity of verbs. More specific verbs may lead to more specific, useful hypotheses. Following the intuition, two features below are extracted for each verb, V1, V2, and V3, involved in a rule r (see Figure 2).
• Document frequency (DF) in Medline. The inverse of DF is often used as an indicator of the specificity
• of a word in information retrieval [Sparck Jones, 1972].
• The number of synonyms. We assume that broader terms have more synonyms, and vice versa. The number is based on an English lexical database, WordNet [Fellbaum, 1998]
• Specificity of nouns. The assumption is similar to the above. For each noun, N1, N2, and N3, involved in a rule r, two features are extracted. When the same r is derived frommultiple syllogistic patterns, the generated hypothesis is replicated for each pattern to encode different feature values.
• DF in Medline.
• The number of synonyms.

For the rule/hypothesis-dependent features, the following set is utilized.

• The number of rules that produced the same hypothesis h.
• Specificity of nouns involved in the premises "N4 V1 N5" and "N5 V2 N6" that produced h (See the righthand side of Figure 3). For each noun (N4, N5, N6), its DF in Medline is used as specificity.
• Applicability of rule r to generate hypothesis h. We assume that h is more plausible if r which generated h is more appropriate to the context (two premises) to be applied. We define this applicability of r as "analogical resemblance" between the syllogistic pattern from which r was derived and the one associated with h. The details are described in the next paragraphs.

Analogical Resemblance

Figure 3 illustrates the idea of analogical resemblance, where the left triangle is the syllogistic pattern from which a rule is derived and the right triangle is the two premises "N4 V1 N5" and "N5 V2 N6" from which a possible hypothesis "N4 V3 N6" is inferred. A dashed line connects two concepts that play the same role in the syllogistic rule represented by a sequence of predicates V1, V2, and V3. If the connected concepts are semantically more similar to each other, the rule is likely to be more applicable to the right triangle with concepts N4, N5, and N6.

There is much work in estimating the semantic similarity of two concepts, such as corpus-based and lexicon-based approaches [Mihalcea et al., 2006]. This study adopts a corpusbased approach for its wide coverage, specifically, Normalized Google Distance (NGD) [Cilibrasi and Vitanyi, 2007]. NGD is an approximation of Normalized Information Distance (NID) and replaces the Kolmogorov complexity in the formulation with the number of Google hits as defined in

where f (x) is the number of hits by Google search with query x and N is the number of web pages indexed by Google. NGD(x, y) ranges from 0 to ∞ and NGD(x, y)=0 means that they are identical.

Instead of Google, however, we use Medline, which would better reflect the domain knowledge and also ensures that f(x) for any concept x will exist (non-zero) since the concepts in the propositions are all extracted from Medline in this study. Although the formulation is exactly the same, we call the distance used with Medline Normalized Medline Distance (NMD) to avoid unnecessary confusion. It should be mentioned that Lu and Wilbur [2009] also used Medline for computing NGD. We compute an NMD value for each of the three pairs of concepts in Figure 3, i.e., NGD(N1,N4), NGD(N2,N5), NGD(N3,N6), to represent the applicability of rule r to hypothesis h.

4 Evaluation

4.1 Experimental Procedure and Settings

To demonstrate the validity of our proposed framework, we performed evaluative experiments. As the existing knowledge, we used a subset of Medline, specifically, the 2004 Genomics track data set [Hersh et al., 2004]. The data set is a subset of Medline from 1994 to 2003 and is composed of 4,591,008 records. From the data set, known relations were extracted in a predicate-argument structure from the titles and abstracts of the Medline records using the Genia tagger [Tsuruoka and Tsujii, 2005]. After applying the normalizing processes described in Section 3.1, 17,904,002 relations were acquired and formed knowledge base K. Then, K was split into three subsets K1, K2, K3 of around the same size. The oldest knowledge, K1, was used for rule derivation and hypothesis generation. The number of rules was 12,180 and the number of generated hypotheses was 346,424 including duplicates.

The generated hypotheses were then compared with the knowledge base K2 and subsequently K3. If a hypothesis was found in K2, it was considered as a positive example and was added to the training data. If it was not found in K2 but found in K3, it was added to the test data as a positive example. The hypotheses not found in K2 nor K3 were unlabeled and were added to either the training or test data at random. This process ensures that training and test data do not have the same instances.

The training data were used for PU learning and the test data were used for evaluating the performance of our proposed framework for hypothesis generation and ranking. The training data contain 226 positive and 169,060 unlabeled examples, and the test data contain 88 positive and 169,059 unlabeled examples. The unlabeled examples in the test data are regarded as negatives in evaluation, although they may not be truly negatives as they may be verified in future. We will come back to this issue in the next section when discussing the evaluation criteria.

In applying the PU learning approach by Lee and Liu [2003], some parameters need to be set. Following their report, the number of iterations (epochs) was set to 500. Similarly, the decay rate and learning rate were experimentally set to 0.05 and 0.00001, respectively, by consulting their report. Although we have tested a few different values on the test set and the results were not very different, better results may be obtained by systematically optimizing the parameters.

4.2 Results and Discussion

Performance of Hypothesis Generation and Ranking

The generated hypotheses in the test data were ranked by the output of the regression model learned from the training data. The performance of the ranking was evaluated by a receiver operating characteristic (ROC) curve and the area under it (AUC). An ROC curve is plotted with x and y axes being false positive and true positive rates, respectively, and is often used for evaluating the performance of classifiers. There are other commonly used evaluation criteria, including accuracy and F-measure. However, accuracy is not suitable for this experiment as the number of positive and negative examples is heavily unbalanced. F-measure is not suitable either because negative examples in the test data may not be actually negatives. An ROC curve is more appropriate in this setting. It basically indicates the degree to which the distributions of positives and negatives are separated, and even if some negatives are actually positives, the influence on the resulting ROC curve is limited if the number of such not-yet-known positives is much smaller than that of negatives. Figure 4 shows the resulting ROC curve, where the AUC was computed as 0.860.

As shown by the result, the curve is above the dotted diagonal line, and consequently, AUC is much greater than 0.5 corresponding to random guess, which confirms the overall effectiveness of our proposed framework to hypothesis generation and ranking.

We then looked at which features contributed to the performance based on the regression coefficients (weights) for the features as summarized in Table 1, where features are sorted in descending order of the absolute weight values within the rule-dependent and rule/hypothesis-dependent groups.

Let us first examine the rule-dependent features. Among them, DF of V3 was found to have the greatest predictive power with the highest weight of 246.33, followed by DF of N2 and DF of V1 and other DF values. The higher effect of V3's makes sense as it appears as the predicate of the generated hypotheses. Interestingly, DFs for verbs and for nouns were found to have positive and negative weights, respectively. This means that more commonly used general verbs and less commonly used specific nouns tend to form more reliable rules leading to true hypotheses. A possible explanation is that verbs are closed vocabulary and those used to express biological mechanism are often in a regular pattern (e.g., x activates y), whereas nouns in true hypotheses are often specific biomedical entities with lower DFs. Other features including the number of synonyms were found to have little information to predict the true hypotheses.

For the rule/hypothesis-dependent features, DFs of N4 and N6 show the higher weights, indicating their positive correlation to true hypotheses. Also, NGD values associated with them were found useful. The negative values of the NGD's weights mean that semantically similar phrases (i.e., smaller distance) lead to true hypotheses, supporting our assumption for analogical resemblance between two syllogistic patterns.

Performance vs. Training Data Size

The training data collected for the evaluation is relatively small, containing only 226 positive examples. Therefore, it is important to investigate the effect of the training data size in learning a regression model to see if more training data would help to increase the performance. For this purpose, we randomly sampled n% of the training data and used them for learning a regression model. For each n, the same process was repeated for 10 times to compute an average AUC for the particular n. Figure 5 shows the transition of the average AUC with different values of n, where the error bars indicate ±1 standard deviation.

The result shows that more training data gradually improve the performance but the difference is subtle. From this experiment, we conclude that more training data would not lead to performance boost with the current model and features. We plan to explore alternative PU learning models [Elkan and Noto, 2008; Xiao et al., 2011, for example] and richer features.

5 Conclusion

This paper focused on a triangular chain of relations, called syllogistic patterns, and proposed a novel approach to hypothesis discovery. The key intuition is that a generalized rule can be induced from such patterns and can then be applied back to the existing knowledge to generate hypotheses. To validate the idea, we implemented the proposed framework and exhaustively identified such hypothesis generation rules in a subset of Medline database and generated hypotheses based on the acquired rules. Among them, true hypotheses were automatically identified based on more recent literature so as to construct training/test data for PU learning. We examined various features associated with specificity, analogical resemblance, and others to represent generated hypotheses. Our evaluation demonstrated that the proposed framework was effective in discovering true hypotheses and that some of those features were characteristic to true hypotheses.

Although the results were promising, the present work has some limitations. The literature used for our experiment was limited in the amount and coverage. Thus, the identified true hypotheses may be actually old knowledge that simply did not appear in our data. Also, basic biomedical knowledge may not appear in Medline and thus not in our knowledge base, either. We plan to address these issues and also explore other PU learning models and features in future work.

Acknowledgments

This work is supported by the Kayamori Foundation grant #K23-XVI-363 and JSPS Kakenhi grant #25330363.