System and methods for predicting probable relationships between items

Abstract

The present invention relates generally to identifying relationships between items. Certain embodiments of the present invention are configurable to identify the probability that a certain event will occur by identifying relationships between items. Certain embodiments of the present invention provide an improved supervised machine learning system.

Claims

1. A system for automatically predicting an interaction between information items comprising: a processor: a memory in communication with said processor via a communication infrastructure and storing instructions that, when executed by said processor, cause the processor to: access a collection including at least two or more information items; develop a training set from the at least two or more information items in the collection; analyze the training set using one or more machine learning models selected from the group consisting of a Naive Bayes, a Naive Bayes Multinomial, and a support vector machine, identify one or more interactions between pairs of information items, and extract two or more features of the one or more interactions, one of the two or more extracted features being a content feature, and the other of the two or more extracted features being selected from the group consisting of Adamic, numCommonNeighbor, Jaccard, and sum Neighbor; produce a classifier element based upon the analysis of the training set wherein the classifier element is selected from the group consisting of a Naive Bayes classifier that assumes features are generated independently from each other, a Naive Bayes Multinomial classifier that assumes a conditional probability of features follows multinomial distribution, and a support vector machine classifier defining decision boundaries of features; establish an evaluation set comprising new pairs of information items; apply the classifier element to the new pairs of information items in the evaluation set, thereby producing a probability value for each of the new pairs of information items; rank each classified pair of information items in a data set from a high probability value to a low probability value; predict a likelihood of interaction between the information items of each ranked pair; and deliver an output comprising the likelihood of interaction, wherein delivery of the output includes display of a graphical representation configured to convey relationships between information items.

2. The system of claim 1, wherein the graphical representation includes node symbols representing the at least two or more information items and link symbols representing relationships between the at least two or more information items.

3. The system of claim 2, wherein the graphical representation includes link symbols representing at least known relationships between the at least two or more information items.

4. The system of claim 2, wherein the graphical representation includes link symbols representing any predicted relationships between the at least two or more information items.

5. The system of claim 2, wherein the processor is further configured to assign a degree for each node symbol.

6. The system of claim 2, wherein the graphical representation is an interaction network.

7. The system of claim 2, wherein the graphical representation is a map.

8. The system of claim 1, wherein the content feature is an individual property of the information item.

9. The system of claim 1, wherein the training set is indexed to facilitate analysis of the training set.

10. The system of claim 1, wherein the evaluation set is indexed to facilitate analysis of the evaluation set.

11. The system of claim 1, wherein the probability value indicates a likelihood of interaction between the classified pair of information items.

12. The system of claim 1, wherein one of the at least two or more information items is a topic information item.

13. The system of claim 1, wherein one of the at least two or more information items is a protein information item.

14. The system of claim 1, wherein one of the at least two or more information items is a publication information item.

15. The system of claim 1, wherein one of the at least two or more information items is a type of pharmaceutical drug information item.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The foregoing will be apparent from the following more particular description of example embodiments, as illustrated in the accompanying drawings in which like reference characters refer to the same parts throughout the different views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating embodiments.

(2) The preferred embodiments of the invention will be described in conjunction with the appended drawings provided to illustrate and not to the limit the invention, where like designations denote like elements, and in which:

(3) FIG. 1 illustrates an embodiment of a system of the present invention;

(4) FIG. 2 illustrates a flowchart representing a method embodiment of the present invention;

(5) FIG. 3 illustrates an interaction network map according to the present invention;

(6) FIG. 4 illustrates a graph representing the frequency of degree of nodes in a dataset;

(7) FIG. 5A illustrates a graphical representation of a collection of performance results;

(8) FIG. 5B illustrates a graphical representation of a subcollection (Homo sapiens) of performance results;

(9) FIG. 5C illustrates a graphical representation of a subcollection (Saccharomyces cerevisiae) of performance results;

(10) FIG. 5D illustrates a graphical representation of a subcollection (Schizosaccharomyces pombe) of performance results;

(11) FIG. 6 illustrates a graphical representation of new interactions per year;

(12) FIG. 7 illustrates a computer system according to an embodiment of the present invention; and

(13) FIG. 8 illustrates a cloud computing system according to an embodiment of the present invention.

DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION

(14) A description of example embodiments follows.

(15) Certain embodiments of the present invention are configured to generate quality hypotheses regarding information items. More specifically, certain embodiments are configured to identify the two or more information items that have the highest likelihood of interaction.

(16) For purposes of this application, the present invention is discussed in reference to automatically generating quality hypotheses regarding relationships between biological information items—specifically, proteins—, but the discussion is merely exemplary. The present invention is applicable to automatically generating quality hypotheses regarding any one or more information items.

(17) Certain embodiments of the present invention include a system 100 including a storage component 102, training analysis component 104, and prediction creation component 106 as illustrated in FIG. 1.

(18) Certain embodiments of the present invention include a method 200, as illustrated in FIG. 2. For example, a scope of information items to be included in a collection may be defined 202. In such step, two or more information items may be mined from data source units (which may be stored internal or external to the system, for example, in a storage component 102). Examples of data source units include published articles, published abstracts, raw data, catalogued data, or other collections of information. Examples of storage components include main memory, secondary memory, databases, indexes, files, or other retention systems.

(19) Also, to define the scope of information items to be included, the user may apply some criteria (e.g., time range, quality, type of item, type of data source unit).

(20) Certain embodiments of the present invention may be configured to process large amounts of information (e.g., “big data”). For example, a collection of information may include over 33,000 pairs of information items (e.g., over 16,000 positive pairs and 17,000 negative pairs) in a certain time frame (e.g., before the year 2011). The collections may be sub-divided to form sub-collections. Each sub-collection may be directed to information associated with, for example, a certain time frame, certain species (e.g., Homo sapiens, Saccharomyces cerevisiae, and Schizosaccharomyces pombe), certain publications, or some other relevant criteria. In time-based sub-collections, longitudinal datasets may be formed.

(21) Once the scope of known information items in the collection is defined, a map 120 may be built to illustrate any known relationships between the one or more information items, as illustrated in FIG. 3. In one embodiment of the interaction network map, the information items may be represented by nodes 122 and connections 124. A node may be assigned a “degree”, which is the number of connections the node has to other nodes. Generally, low degree nodes have few interactions with other nodes, while high degree nodes—also termed “hubs”—have many interactions with other nodes.

(22) The degree of the nodes may follow the power law distribution. In certain embodiments, the node is calculated using log (frequency)=alpha−beta*log (degree). In one example in which over 48,000 nodes are identified and over 12,000 of them are known to have only one interaction, a mean degree may be 21, a median degree may be 4, minimum degree may be 1, maximum degree may be 10095, and a standard deviation may be 75. In such an embodiment, the alpha=0.36 and the beta=1.6 by linear regression. The adjusted r-squared is 0.9 and p-value<2.2e-16 for the linear regression. An example of a plot of the node degrees is shown in FIG. 4.

(23) Next, a training set may be developed from all or some of the information items in the collection 204. In certain embodiments, the training set may include topic information items and publication information items. In certain embodiments, the topic information items may be configured as protein information items, such as characteristics or aspects of proteins themselves (e.g., name, amino acid sequence, functional groups, charge, polarity, hydrophobic/hydrophilic, date of discovery of aspect, or other physical or non-physical characteristics of the proteins, etc.). The publication information items may include information regarding publicly available article, document, or presentation, such information possibly including author(s), past occurrences of co-authorship between authors, other proteins cited or tagged in the same article, other proteins cited or tagged in articles in which certain co-authorship recurs, publication date, abstract, article title, periodical title, volume, issue no., other publication method, research fund source, institution with which the publication or author is associated, or other.

(24) In an example, a training set may be constructed by using information before Year y to predict the new pairs in Year y. This approach may be applied from Year 1995 to Year 2012. For each year, 1000 positive and 1000 negative training instances from the data before y may be randomly selected from the collection to train the models.

(25) The training set may be input into a training analysis component 104, which is configured to assess whether there are interactions between certain information items and then to recognize and extract features of the interaction(s) 206 or perform other types of analysis on the training set.

(26) A “feature” is an individual measurable heuristic property of a phenomenon. Examples of features for publication information items may include Medical Subject Headings (“MeSH”) terms—term for tags used in MEDLINE database articles—or other “tags” associated with publications. For purposes of this application, the similarity of the MeSH terms in publication history of two proteins is called “SimMeSH”, which is described in more detail in Table 1.

(27) Another feature—termed “JaccardArticleCoOccurence” for purposes of this application—, assumes that if two proteins are cited in the same article, they are related. JaccardArticleCoOccurence is also described in more detail in Table 1.

(28) An additional feature—termed “SumPub” for purposes of this application—represents the research intensity between two proteins in certain embodiments and is also described in more detail in Table 1.

(29) Certain features may be recognized by using information related to an interaction network map. Such features are termed “network features”.

(30) One network feature may include the number of “neighbor nodes” shared by two nodes in a network (each node representing an information item), which may be termed “numCommonNeighbor” and is described in more detail in Table 1. Another network feature may include the total number of neighbors collectively held by two nodes, which may be termed “sumNeighbor”, and is described in more detail in Table 1. Possibly, connectivity of a node in the network is related to the likelihood that the information item represented by the node has additional relationships with other nodes/information items.

(31) Yet another network feature may include the sum of two nodes' clustering coefficient, which is termed “sumClusteringCoef”, and is described in more detail in Table 1. The clustering coefficient of vertex “v” in a graph is the proportion that v's neighbors connect among themselves. For example, assume “v” has 4 neighbors (meaning 6 possible connections among them), and there are actually 3 confirmed links (where each link represents a relationship between the information items of the respective nodes). In that example, the clustering coefficient is 0.5 ( 3/6).

(32) Additional network features may include a Jaccard coefficient feature and Adamic feature, which are topological based measures that describe the pairs' common neighbors and generally are effective on link prediction task. These features are also described in more detail in Table 1.

(33) TABLE-US-00001 TABLE 1 Category Feature Name Definition Source Text features simMeSH $\frac{.Math.M\left(x\right).Math.M\left(y\right).Math.}{.Math.M\left(x\right)M\left(y\right).Math.}.$   M(.) is the set of mesh terms of all the articles that mention the protein. MEDLINE sumPub |Pub(x)| + |Pub(y)|. Pub(.) is the set of MEDLINE publications that mention the protein. jaccardArticleCoOccur $\frac{.Math.\mathrm{Pub}\left(x\right)\mathrm{Pub}\left(y\right).Math.}{.Math.\mathrm{Pub}\left(x\right)\mathrm{Pub}\left(y\right).Math.}.$ MEDLINE Network features Adamic $\underset{Z\mathrm{ϵ\Gamma }\left(x\right).Math.\Gamma \left(y\right)}{.Math.}\frac{1}{.Math.\Gamma \left(z\right)).Math.}.$ BioGRID numCommonNeighbor |Γ(x) ∩ Γ(y)|. Γ(.) is the set of neighbors. BioGRID Jaccard $\frac{.Math.\Gamma \left(x\right).Math.\Gamma \left(y\right).Math.}{.Math.\Gamma \left(x\right)\Gamma \left(y\right).Math.}.$ BioGRID sumNeighbor |Γ(x)| + |Γ(y)|. BioGRID sumClusteringCoef clustering_coef(x) + clustering_coef(y) BioGRID

(34) To more quickly and easily analyze the training set, the records in a database of known information items (e.g., MEDLINE, BioGRID, other collection or sub-collection of information items) may be indexed. Indexing also may permit extracting features from that collection of information items. For example, search terms such as protein names and synonyms could be used to identify a group of information items relevant to a specific hypothesis.

(35) In another method step, the training analysis component 104 may produce a classifier element 208.

(36) An evaluation set may be established from all or some of the information items in the collection 210. Typically, at least some information items not present in the training set are included in the evaluation set. In certain embodiments, all of the information items in the evaluation set were not included in the training set.

(37) The evaluation set may be input into a prediction creation component, which may be configured to apply the classifier element to determine the likelihood of interaction between one or more information items in the evaluation set 212. In other words, new pairs of information items may be predicted by ranking the known pairs according to the probability produced by the classifier element. In link prediction task, there may be no absolute negative instance, as each pair that has no interaction so far may interact in the future. In certain embodiments, it may be assumed that the network is sparse and most of the pairs are not going to interact at all, where the model learns negative instances. Given a new pair, the model may be used to predict the probability of matching. If a pair has high rank in the dataset, it may be a possible interaction.

(38) In certain embodiments, the training analysis component and possibly the prediction creation component may be using one or more supervised machine learning models. Examples of supervised machine learning models include Naïve Bayes (NB), Naive Bayes Multinomial (NBM), support vector machine (SVM), and logistic regression. The classifiers resulting from these four models typically perform well and generally are also robust, fast, and easy to implement.

(39) When applying a Naïve Bayes model, the training analysis component may produce a Naive Bayes classifier, which is a simple probabilistic classifier based on applying Bayes's theorem with the strong (naive) independence assumption that the features are generated independently from each other given the instance label.

(40) A Naïve Bayes Multinomial model includes an assumption that the conditional probability of the feature given a class follows multinomial distribution.

(41) SVMs are based on the concept of maximum margin decision planes that define generalizable decision boundaries for classification and regression. An SVM constructs a hyperplane to maximize the margin between the data points and the hyperplane, often after mapping the data points to a higher dimensional space in which they are linearly separable or close.

(42) The training set also may be subjected to a 10-fold cross validation, the results of which are illustrated in Table 2 (for an example dataset).

(43) TABLE-US-00002 TABLE 2 Model ROC Precision Recall F1 Naïve Bayes 0.832 0.787 0.697 0.668 Naïve Bayes Multinomial 0.738 0.639 0.618 0.607 SVM 0.765 0.771 0.766 0.765 Logistic 0.856 0.781 0.772 0.769

(44) Logistic regression may achieve high performance, e.g., with 0.856 ROC and 0.769 F1 for one dataset. Naïve Bayes model may have the second best at 0.832 ROC and 0.668 F1. Naïve Bayes Multinomial and SVM may not be as useful as the previous two, with 0.738 and 0.765 ROC respectively, for certain embodiments.

(45) The features identified may be ranked using information in the training set analysis to examine each feature's contribution to the information gained, as illustrated in Table 3. Neighbor-based features, e.g., Adamic, numCommonNeighbor, Jaccard, and sumNeighbor may rank relatively high.

(46) TABLE-US-00003 TABLE 3 Rank Feature Information Gain 1 Adamic 0.306 2 numCommonNeighbor 0.291 3 Jaccard 0.287 4 sumNeighbor 0.176 5 sumPub 0.135 6 simMeSH 0.122 7 sumClusteringCoef 0.105 8 jaccardArticleCoOccur 0.0382

(47) In addition, models may be tested for their performance level relative to a random classifier. An example of such a test is illustrated in Table 4 To quantify quality prediction, an embodiment of the SML model may utilize an existing high quality data set, for example, a collection of protein-protein interactions (the BioGRID database) manually curated by biologists. As shown in Table 4, the SML model can predict thousands of predictions automatically with the best performing model of >90% F1 score or accuracy, a high precision or quality prediction.

(48) TABLE-US-00004 TABLE 4 Model ROC Precision Recall F1 Naïve Bayes 0.95 0.876 0.841 0.837 Naïve Bayes 0.917 0.804 0.783 0.78 Multinomial SVM 0.911 0.911 0.911 0.911 Logistic 0.946 0.911 0.911 0.911 Random Baseline — 0.503 0.509 0.506

(49) After a classifier is applied to an evaluation set, the output may include information related to likelihood of interaction between any two or more information items or just information item pairs. The likelihood of interaction may be termed “relationship value”. The relationship value for each pair of information items may be ranked according to size and/or converted into a results graphical representation for display via a display unit.

(50) Examples of graphical representations of results are illustrated in FIG. 5A-5D. Each results graphical representation illustrates performance of a model used to predict next year's discoveries regarding information item interactions. FIG. 5A is for a whole collection, while FIG. 5B-FIG. 5D are for sub-collections (Homo sapiens, Saccharomyces cerevisiae, and Schizosaccharomyces pombe, respectively).

(51) FIG. 6 illustrates the actual new interactions discovered between years 1995-2012.

(52) FIG. 7 illustrates an exemplary computer system 300 that may be used to implement the methods according to the invention. One or more computer systems 300 may carry out the methods presented herein as computer code.

(53) Computer system 300 includes an input/output display interface 302 connected to communication infrastructure 304—such as a bus—, which forwards data such as graphics, text, and information, from the communication infrastructure 304 or from a frame buffer (not shown) to other components of the computer system 300. The input/output display interface 302 may be, for example, a keyboard, touch screen, joystick, trackball, mouse, monitor, speaker, printer, Google Glass® unit, webcamera, any other computer peripheral device, or any combination thereof, capable of entering and/or viewing data.

(54) Computer system 300 includes one or more processors 306, which may be a special purpose or a general-purpose digital signal processor that processes certain information. Computer system 300 also includes a main memory 308, for example random access memory (“RAM”), read-only memory (“ROM”), mass storage device, or any combination thereof. Computer system 300 may also include a secondary memory 310 such as a hard disk unit 312, a removable storage unit 314, or any combination thereof. Computer system 300 may also include a communication interface 316, for example, a modem, a network interface (such as an Ethernet card or Ethernet cable), a communication port, a PCMCIA slot and card, wired or wireless systems (such as Wi-Fi, Bluetooth, Infrared), local area networks, wide area networks, intranets, etc.

(55) It is contemplated that the main memory 308, secondary memory 310, communication interface 316, or a combination thereof, function as a computer usable storage medium, otherwise referred to as a computer readable storage medium, to store and/or access computer software including computer instructions. Certain embodiments of a computer readable storage medium do not include any transitory signals or waves. For example, computer programs or other instructions may be loaded into the computer system 300 such as through a removable storage device, for example, a floppy disk, ZIP disks, magnetic tape, portable flash drive, optical disk such as a CD or DVD or Blu-ray, Micro-Electro-Mechanical Systems (“MEMS”), nanotechnological apparatus. Specifically, computer software including computer instructions may be transferred from the removable storage unit 314 or hard disc unit 312 to the secondary memory 310 or through the communication infrastructure 304 to the main memory 308 of the computer system 300.

(56) Communication interface 316 allows software, instructions and data to be transferred between the computer system 300 and external devices or external networks. Software, instructions, and/or data transferred by the communication interface 316 are typically in the form of signals that may be electronic, electromagnetic, optical or other signals capable of being sent and received by the communication interface 316. Signals may be sent and received using wire or cable, fiber optics, a phone line, a cellular phone link, a Radio Frequency (“RF”) link, wireless link, or other communication channels.

(57) Computer programs, when executed, enable the computer system 300, particularly the processor 306, to implement the methods of the invention according to computer software including instructions.

(58) The computer system 300 described herein may perform any one of, or any combination of, the steps of any of the methods presented herein. It is also contemplated that the methods according to the invention may be performed automatically, or may be invoked by some form of manual intervention.

(59) The computer system 300 of FIG. 7 is provided only for purposes of illustration, such that the invention is not limited to this specific embodiment. It is appreciated that a person skilled in the relevant art knows how to program and implement the invention using any computer system.

(60) The computer system 300 may be a handheld device and include any small-sized computer device including, for example, a personal digital assistant (“PDA”), smart hand-held computing device, cellular telephone, or a laptop or netbook computer, hand held console or MP3 player, tablet, or similar hand held computer device, such as an iPad®, iPad Touch®, or iPhone®.

(61) FIG. 8 illustrates an exemplary cloud computing system 400 that may be used to implement the methods according to the present invention. The cloud computing system 400 includes a plurality of interconnected computing environments. The cloud computing system 400 utilizes the resources from various networks as a collective virtual computer, where the services and applications can run independently from a particular computer or server configuration making hardware less important.

(62) Specifically, the cloud computing system 400 includes at least one client computer 402. The client computer 402 may be any device through the use of which a distributed computing environment may be accessed to perform the methods disclosed herein, for example, a traditional computer, portable computer, mobile phone, personal digital assistant, tablet to name a few. The client computer 402 includes memory such as random access memory (“RAM”), read-only memory (“ROM”), mass storage device, or any combination thereof. The memory functions as a computer usable storage medium, otherwise referred to as a computer readable storage medium, to store and/or access computer software and/or instructions.

(63) The client computer 402 also includes a communications interface, for example, a modem, a network interface (such as an Ethernet card), a communications port, a PCMCIA slot and card, wired or wireless systems, etc. The communications interface allows communication through transferred signals between the client computer 402 and external devices including networks such as the Internet 404 and cloud data center 406. Communication may be implemented using wireless or wired capability such as cable, fiber optics, a phone line, a cellular phone link, radio waves or other communication channels.

(64) The client computer 402 establishes communication with the Internet 404—specifically to one or more servers—to, in turn, establish communication with one or more cloud data centers 406. A cloud data center 406 includes one or more networks 410a, 410b, 410c managed through a cloud management system 408. Each network 410a, 410b, 410c includes resource servers 412a, 412b, 412c, respectively. Servers 412a, 412b, 412c permit access to a collection of computing resources and components that can be invoked to instantiate a virtual machine, process, or other resource for a limited or defined duration. For example, one group of resource servers can host and serve an operating system or components thereof to deliver and instantiate a virtual machine. Another group of resource servers can accept requests to host computing cycles or processor time, to supply a defined level of processing power for a virtual machine. A further group of resource servers can host and serve applications to load on an instantiation of a virtual machine, such as an email client, a browser application, a messaging application, or other applications or software.

(65) The cloud management system 408 can comprise a dedicated or centralized server and/or other software, hardware, and network tools to communicate with one or more networks 410a, 410b, 410c, such as the Internet or other public or private network, with all sets of resource servers 412a, 412b, 412c. The cloud management system 408 may be configured to query and identify the computing resources and components managed by the set of resource servers 412a, 412b, 412c needed and available for use in the cloud data center 406. Specifically, the cloud management system 408 may be configured to identify the hardware resources and components such as type and amount of processing power, type and amount of memory, type and amount of storage, type and amount of network bandwidth and the like, of the set of resource servers 412a, 412b, 412c needed and available for use in the cloud data center 406. Likewise, the cloud management system 408 can be configured to identify the software resources and components, such as type of Operating System (“OS”), application programs, and the like, of the set of resource servers 412a, 412b, 412c needed and available for use in the cloud data center 406.

(66) The present invention is also directed to computer products, otherwise referred to as computer program products, to provide software to the cloud computing system 400. Computer products store software on any computer useable medium, known now or in the future. Such software, when executed, may implement the methods according to certain embodiments of the invention. Examples of computer useable mediums include, but are not limited to, primary storage devices (e.g., any type of random access memory), secondary storage devices (e.g., hard drives, floppy disks, CD ROMS, ZIP disks, tapes, magnetic storage devices, optical storage devices, Micro-Electro-Mechanical Systems (“MEMS”), nanotechnological storage device, etc.), and communication mediums (e.g., wired and wireless communications networks, local area networks, wide area networks, intranets, etc.). It is to be appreciated that the embodiments described herein may be implemented using software, hardware, firmware, or combinations thereof.

(67) The cloud computing system 400 of FIG. 8 is provided only for purposes of illustration and does not limit the invention to this specific embodiment. It is appreciated that a person skilled in the relevant art knows how to program and implement the invention using any computer system or network architecture.

(68) While the disclosure is susceptible to various modifications and alternative forms, specific exemplary embodiments of the present invention have been shown by way of example in the drawings and have been described in detail. It should be understood, however, that there is no intent to limit the disclosure to the particular embodiments disclosed, but on the contrary, the intention is to cover all modifications, equivalents, and alternatives falling within the scope of the disclosure as defined by the appended claims.

(69) The teachings of all patents, published applications and references cited herein are incorporated by reference in their entirety.

(70) While example embodiments have been particularly shown and described, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the scope of the embodiments encompassed by the appended claims.