Cracs.fc.up.pt

Discovering Latent Structure in Clinical Databases Statistical relational learning (SRL) allows algorithms to simultaneously reason about complex structure and uncertainty with a given domain. One common chal-lenge when analyzing these domains is the presence of latent structure within the data. We present a novel algorithm that is automatically able to group together different objects in a domain in order to uncover latent structure, including a hi- erarchy or even heterarchy. We empirically evaluate our algorithm on two large real-world tasks where the goal is predict whether a patient will have an adverse reaction to a medication. We found that the proposed approach produced a more accurate model than the baseline approach. Furthermore, we found interesting latent structure that was deemed to be relevant and interesting by a medical col- Statistical relational learning (SRL) [2, 6] focuses on developing learning and reasoning formalisms that combine the benefits of relational representations, such as relational databases or first-orderlogic, with those of probabilistic, graphical models. SRL is especially applicable for domains when (1) it is important to explicitly model uncertainty, for example the probabilities of predictions our model makes and (2) the data resides in a relational database, where information from each table is needed to learn an accurate model. One particularly challenging aspect of analyzing real-world relational data is the presence of latent structure. Accurately detecting and modeling this type of structure requires combining ideas from latent variable discovery in graphical models (e.g., [4, 16]) and predicate invention in inductive logic programming (e.g., [10, 15]). Despite the fact that many domains have latent structure, very few learning algorithms [8, 9, 14] are able to effectively cope with its presense in rich relational domains.
Is this last sentence OK? Or are we overselling? To motivate the need to discover latent structure, consider the task of analyzing electronic medi- cal records (EMRs). An EMR is a relational database that stores a patient’s clinical history (e.g.,disease diagnoses, prescriptions, lab test results, etc.). Recently, there has been much interest in applying machine learning to medical data []. When treating a patient, a doctor must decide among many different medications that could be prescribed. These medications share varying degrees of similarity in terms of (i) how they interact with the human body to counteract disease, (ii) how they interact with other drugs, and (iii) how they interact with genetic and other variations from one human body to another. In terms of medication, all that a patient’s clinical history contains is which drugs were prescribed for the patient (e.g., name, dosage, duration). Consequently, it can be difficult to detect interesting and meaningful patterns present in the data. For example, there may be a substantial number of people who take a class of medicines, such as statins for cholesterol, and also have certain outcome (e.g., disease diagnosis, adverse drug reaction, etc.). The data only records which specific medicine each patient has been prescribed, and the number of people whotake each individual medicine and have the outcome may be too small to meet an interestingness threshold (e.g., support threshold in association rule mining). What is missing is the ability to auto- matically detect related medicines and group them together. Requiring a domain expert to hand-craft all relevant features or relations necessary for a problem is a difficult and often infeasible task. For example, should drugs be grouped by which disease they treat, which mechanism they use, or by potential side-effects or interactions with other drugs? Ideally, the learning algorithm should be able to automatically discover and incorporate relevant features and relations.
In this paper we propose a novel approach for automatically discovering latent structure in relational domains. Our approach represents latent structure by, possibly hierarchically, grouping together sets of objects in a domain. The proposed approach dynamically introduces latent structure in a data- driven fashion. It automatically groups together objects and/or already-existing groups by evaluating whether the proposed grouping results in a more accurate learned model. Furthermore, each object can appear in multiple different groupings as an object may appear in multiple contexts (e.g., drug could be in different gr oupings related to its mechanism, indications, contraindications, etc.). A central challenge in the domains we consider is that they contain a large number of objects (e.g., diseases, drugs). Consequently, searching for latent relationships among all objects at once is pro-hibitively expensive. We introduce several search strategies that help automatically identify a small but promising subset of objects that could belong to the same latent group.
In this paper, we motivate and evaluate our proposed approach on the specific task of predicting adverse drug reactions (ADRs) from EMR data. This application is timely for a number of reasons.
First, EMRs are now becoming widespread, making large amounts of this data available for research for the first time. Second, adverse drug reactions are a major risk to health, quality-of-life andthe economy. ADRs are the fourth-leading cause of death in the United States. The pain reliever VioxxTMalone was earning US$2.5 billion per year before it was found to double the risk of heart attack and was pulled from the market, while the related drug CelebrexTMalso raised this risk and remains on the market. Third, accurate predictive models for ADRs are actionable—if found to be accurate in a prospective trial, such a model could easily be incorporated into EMR-based medical practices to avoid giving a drug to those at highest risk of an ADR. Using three real-world ADR tasks, we demonstrate that the proposed approach produces a more accurate model than the baseline approach. Furthermore, our algorithm uncovers latent structure that a doctor, who has expertise in our tasks of interest, deems to be interesting and relevant.
The proposed approach builds on the SRL algorithm VISTA [1], which combines automated feature construction and model learning into a single, dynamic process. Next, we briefly introduce (i) how the algorithm’s overall control structure operates, (ii) how the model is learned and (iii) how the VISTA uses first-order definite clauses, which can capture relational information, to define (binary) features. These features then become nodes in a Bayesian network. VISTA only selects those features which improve the underlying statistical model. In order to select features, VISTA performs the following iterative procedure until some stop criterion has been met. The feature induction module proposes a set of candidate feature to include in the model. VISTA evaluates each feature, f , in turn by learning a new model (i.e., the structure of the Bayesian network) that incorporates f . In order to evaluate each candidate feature f , VISTA needs to estimate the generalization ability of the model with and without the new feature. VISTA does this by calculating the area under the precision-recall curve (in principle, any metric is posible) on a tuning set. VISTA selects the featurethat results in the largest improvement in the score of the model and incorporates it into the model.
If no feature improves the score, the process terminates.
VISTA offers several advantages for analyzing clinical data. First, the first-order rules are equivalent to SQL queries and hence can incorporate information from different tables in the database within a single rule. Second, by incorporating each rule into a Bayesian network, VISTA can capture theinherent uncertainty in the data. Third, the learned rules are comprehensible to domain experts.
Bayesian networks [11] are probabilistic graphical models that encode a joint probability distri- bution over a set of random variables. Given a set of random variables X = {X1, . . . , Xn}, a G, Θ is defined as follows. G is a directed, acyclic graph that con- tains a node for each variable Xi ∈ X. For each variable (node) in the graph, the Bayesian network has a conditional probability distribution (CPD), θXi|P arents(Xi), giving the probabil- ity distribution over the values that variable can take for each possible setting of its parents, and }. A Bayesian network B encodes the following probability distribution: VISTA needs to learn the structure of a Bayesian network. That is, given a data set, it must learn both the network structure G (i.e., the arcs between different variables) and the CPDs, θXi|P arents(Xi), for each node in the network. In particular, VISTA uses tree augmented na¨ıve Bayes (TAN) [5], which is a well-known Bayesian network classifier, as its model. In a TAN model, there is a directed arc from the class variable to each non-class attribute (i.e., variable) in the domain. Furthermore, each non-class attribute may have at most one other parent, which allows the model to capture a limited set of dependencies between attributes. The algorithm for learning a TAN model has two nice theoretical properties [5]. First, it finds the TAN model that maximizes the log likelihood of the network structure given the data. Second, it finds this model in polynomial time.
VISTA makes use of formulas in first-order logic to define features. Technically, it uses the non- recursive Datalog subset of first-order logic, which with a closed-world assumption is equivalent to relational algebra/calculus. The alphabet for Datalog consists of three types of symbols: constants, variables, and predicates. Constants, which start (by common convention) with an upper case let- ter, denote specific objects in the domain. An example is the drug name Propranolol. Variables symbols, denoted by lower case letters, range over objects in the domain. An example is the vari- able disease. Predicate symbols P/n, where n refers to the arity of the predicate and n ≥ 0, represent relations among objects. An example of a predicate is Diagnosis/3, which is used in the example of an atomic formula below. A term is a constant or variable. If P/n is a predicate with arity n and t1, . . . , tn are terms, then P (t1, . . . , tn) is an atomic formula. An example of anatomic formula is Diagnosis(Patient123, 12 − 12 − 2010, Tuberculosis), where all three ar- guments are constants. This says that patient Patient123 had a diagnosis of Tuberculosis on December12, 2010. A literal is an atomic formula or its negation. A clause is a disjunction over a finite set of literals. A definite clause is a clause that contains exactly one positive literal; it can be written as a conjunction of atomic formulas that imply another atomic formula (the positive literal), VISTA uses definite clauses to define features for the statistical model. Typically, we write a definite clause in the implication form as follows: Drug(pid, date1, Ketoconazole) ∧ WithinMonth(date1, date2) ⇒ ADR(pid, date2) All variables in a definite clause are assumed to be universally-quantified. Each definite clausebecomes a binary feature in the underlying statistical model. The feature receives a value of one for a specific patient if data about that patient can be use to satisfy (i.e., prove) the clause and the receives a value of zero otherwise. Feature definitions are constructured in the standard, top-down (i.e., general-to-specific) manner. We briefly describe the approach here, but refer the reader to [need a cite] for more details. Each induced rule begins by just containing the target attribute (in the above example this is ADR(pid, date2)) on the right-hand side of the implication. This means that the feature matches all examples. The induction algorithm then follows an iterative procedure.
It generates a set of candidate refinements by conjoining predicates to left-hand of the rule. The search can proceed in a breadth-first, best-first, or greedy (no backtracking) manner, but we employ a breadth-first search in this paper. This has the effect of making the feature more specific (i.e., it matches fewer examples). The algorithm picks the best refinement. The algorithm stops when norefinement improves the score of the rule.
At a high-level, the key innovation of our approach occurs when constructing feature definitions.
Here, the algorithm has the ability to invent (hierarchical) clusters that pertain to a subset of the constants in the domain. Intuitively, constants that appear in the same grouping share some latent relationship. Discovering and exploiting the latent structure in the feature definitions provides sev- eral benefits. First, it allows for more compact feature definitions. Second, by aggregating across groups of objects, it helps identify important features that may not otherwise be deemed relevant by the learning algorithm. To illustrate the intuition behind our approach, we will use a running example about ADRs to the medication WarfarinTM, which is a blood thinner commonly prescribedto patients at risk of having a stroke. However, Warfarin is known to increase the risk of internal bleeding for some patients. Consider the following feature definition: Drug(pid, date1, Terconazole) ∧ Weight(pid, date1, w) ∧ w < 120 ⇒ ADR(pid) This rule applies only to those patients who satisfy all the conditions on the left hand side of rule.
Conditioning on whether a patient has been prescribed Terconazole, limits the applicability of this rule. Terconazole is an enzyme inducer, which is a type of medication known to elevate a patient’s sensitivity to Warfarin. However, many other drugs in the enzyme inducer class (e.g., Rifampicin and Ketoconazolegive) are frequently prescribed instead of Terconazole, which makes this feature overly specific. A potentially stronger feature would replace Terconazole with an invented conceptsuch as enzyme inducer or Warfarin elevator.
Yet, these concepts are not explicitly encoded in clinical data. By grouping together related objects, Need a Name captures latent structure and is able to learn more general features. For example, we could generalize the previous rule as follows: Cluster1(did) ∧ Drug(pid, date1, did) ∧ Weight(pid, date1, w) ∧ w < 120 ⇒ ADR(pid) The definition for Cluster1 represents latent structure among a group of medicines.
The four key elements of Need a Name, introduced in the next subsections, are: (i) how to represent latent structure, (ii) how to learn the latent structure, (iii) how to evaluate the model and (iv) how the The goal of our approach is to capture hierarchical latent structure about specific constants (i.e., objects) in the domains. First, we want to capture that specific constants are interchangeable in some cases. For example, Terconazole, Rifampicin and Ketoconazole are all enzyme inducers, and a doctor could reasonable prescribe any of them. We can accomplish this by introducing a new concept, which we generically call Cluster1, as follows: These statements simply assign these drugs to Cluster1. There is no limit on the number of objects that can be assigned to each invented cluster.
Secondly, we want to able to make use of previously discovered concepts to represent more high- level, hierarchical structure. We can do this in the following manner: Just as before, the first two statements assign specific drugs to Cluster2. The key step is the third statement, where all the constants that have been assigned to Cluster1 are assigned Cluster2 as well. Once a proposed grouping has been used in a feature that has been included in the model, it is available for future reuse during the learning procedure. Reusing previously discovered concepts allows the algorithm to automatically explore tradeoffs between fine-grained grouping (e.g., enzyme inducers) and more high-level groupings (e.g., Warfarin elevators) that may be present in the data.
Furthermore, it allows the algorithm to build progressively more complex concepts over time.
The key step in the algorithm is discovering the latent structure. Given a feature definition such as Rule 2, latent structure is learned in the following way. First, Needs a Name rewrites the feature definition by replacing the reference to the specific constant with a variable and conjoining an in- vented latent structure predicate to the end of the rule. For example, Rule 2 would be transformed into Rule 3, where Rule 3 has the variable did instead of the constant Terconazole and it containsthe invented predicate Second, Needs a Name learns a definition for the invented latent predicate (e.g., Cluster1). It begins by assigning the replaced constant to this cluster, which in the running example corresponds to this statement: Medicine(Terconazole) ⇒ Cluster1(x). Next, it tries to extend the definition of the cluster by identifying a set of candidate constants that could be added to the cluster. It adds each constant to the cluster in turn. The benefit of the modified cluster is measure by seeing ifthe model, which includes the feature that makes use of the extended cluster definition, improves.
Needs a Name greedily selects the single constant that results in the largest improvement in the model’s score. This procedure iterates until no addition improves the model’s performance or the set of candidate constants is empty. The end result is a cluster definition as illustrated by either in What should we call this 4 or What should we call this 5.
The central challenge in trying to discover latent structure is the large number of concepts we couldinvent. For example, in the predicting adverse reaction domain, the data contains information about thousands of drugs and diseases. Consequently, performing a complete search, where the utility of adding each constant to the cluster is evaluated separately, is prohibitively expensive. We propose two different techniques to identify promising candidates to include in a grouping.
Restrict constants to those from “near miss” examples.
To illustrate this idea, consider the fol- Weight(pid, date1, w) ∧ w < 120 ⇒ ADR(pid) Drug(pid, date1, Terconazole) ∧ Weight(pid, date1, w) ∧ w < 120 ⇒ ADR(pid) The second rule, by adding the condition Drug(pid, date1, Terconazole), applies to fewer pa- tients. Some patients may match Rule 6, but not the more specific Rule 7 because they took a similar, but not identical medication. Looking at the medications prescribed to these patients po- tentially can inform the search as to which medications can be prescribed in place of Terconazole.
Therefore, we restrict the search to only considering grouping together constants that appear in examples that are covered by a rules’ immediate predecessor (i.e., Rule 6) but the rule itself (i.e.,Rule 7).
Restrict constants to those correlated with initial constant. In this approach, we perform a pre- computation to identify constants that are mutually replaceable. Intuitively, the idea is to discover when one constant can be used in lieu of another (e.g., one drug is prescribed in place of anotherdrug). This can be done by employing a variant of “guilt by association,” which says that objects are similar if they appear in similar contexts. Given a ground atom, Rel(A constant C1 shares a context with another constant C2 (with C1 = C2) if replacing C1 with C2 results in ground atom that appears in the data.
Needs a Name performs a preprocessing step over the training data and computes the Pearson correlation among all pairs of constants Ci and Cj: where k ranges over all constants of the same type (such that i = k and j = k), Ni,k is the number of times that Ci shares a context with Ck in the data, and ¯ Ni is the average context size for Ci.
In principle, we can use any evaluation metric for evaluating the quality of the model. In our work we use the area under the precision-recall curve (AUC-PR). Our tasks contain many more negativeexamples than positive examples, and this measure ignores the potentially large number of true negative examples. We evaluate a model by looking at its AUC-PR on both its training set (used to learn the model structure and parameters) and an independent tune set. Since we have relatively few positive examples, both the train and tune set scores helps make the algorithm more robust to overfitting. Furthermore, it is likely that many features will improve the model. Therefore, we require the candidate to improve both the AUC-PR of the train set and the AUC-PR of the tune set by a certain percentage based threshold. Again, using the threshold helps control overfitting by preventing relative weak features (i.e., those that only improve the model score slightly) from being Needs a Name essentially follows the same high-level control structure as the VISTA algorithm described in Subsection 2.1. The key difference is that it defines more candidate features as it constructs and evaluates features that contain invented, latent predicates. However, it is prohibitively expensive to consider adding latent structure to each candidate feature. Therefore, Needs a Name restricts itself to adding latent concepts to only features that meet the following two conditions: Condition 1: The rule under consideration improves the score of the model. This provides initial evidence that the rule is useful, but the algorithm may be able to improve its quality by modeling latent structure. Discarding rules that initially exhibit no improvement dramatically improves the Condition 2: The most recent condition added to the rule must refer to a constant. Furthermore, the user must have identified this type of constant as a candidate for having latent structure. This helps reduce the search space as not all types of constants will exhibit latent structure.
For each candidate feature that meets these two criteria, Needs a Name attempts to discover latent structure. It invokes the procedure outlined in Subsection 3.2 and adds the feature it constructs (which contains an invented latent predicate) to the set of candidate features.
Given the extended set of candidate features, Needs a Name selects the feature that most improves the score of the model. After adding a candidate feature to the model, all other features must be re-evaluated. The modified model, which changes the score for each candidate features, means thatNeeds a Name must check each feature to determine which ones satisfy both of aforementioned conditions and should be augmented with a latent predicate. The modified model, if it incorporated a feature with a latent predicate, also presents expanded opportunities for latent structure discov- ery. Newly invented latent predicates can extend or reuse the previously introduced latent predicate We will evaluate our proposedThis organization has been using electronic medical records since 1985 and has electronic data back to the early 1960’s.
As a case study, we focus on the task of predicting which patients that take a selective Cox-2 inhibitor (e.g., VioxxTM) will have a myocardial infarction (MI) (i.e., a heart attack) while on the drug [?]. Tocreate a set of negative examples, we took patients that were prescribed a selective Cox-2 inhibitor and did not have an MI. Furthermore, we matched the negative examples to have the same age and gender distribution as the positive examples to control for those risk factors. We tested our methods on two additional data sets, which we will refer to here as the ACEI data set and the warfarin data set. To create the ACEI data set we selected all patients in PMRP with at least one prescription of an angiotensin-converting enzyme inhibitor (ACEI) drug in their electronic health record (7624 patients). Within this population we define cases to be those patients who have a diagnosis of angioedema at any point after their first ACEI prescription (102 patients). To create the warfarin data set we selected all patients in PMRP who have at least one prescription of warfarin in their electronic health record (3227 patients), and defined cases to be those patients with a bleeding event (any diagnosis of 219 distinct diagnoses representing bleeding events) at any point after their firstwarfarin prescription (1786 patients). For both the ACEI and warfarin data sets we then right- censored the data for each patient one week before that patient’s first ACEI or warfarin prescription, respectively. In this way we ensure that we are building predictive models only from data generated before the prescription of the drug under consideration.
We empirical compare two approaches.
1. We hold all things be between both algori Present and discuss several learned groupings.
Our approach is closely related to the pioneering work of Dietterich and Michalski [3] on relational learning, in which they performed an operation now known as internal disjunction. This operation replaced constant with a disjunction of several possible constants. A key distinction of our approach is that once an internal disjunction has been created as a category, it can be re-used in other rules.
Furthermore, our approach can create more interesting latent structure, specifically one or more hierarchies, because our disjunctions can include existing categories in addition to constants.
SRL lies at the intersection of relational learning and graphical model learning. The present paper is closely related to predicate invention in relational learning, especially in inductive logic program- ming, and latent variable discovery for graphical models. Inductive logic programming has a rich history of work on predicate invention (e.g., [10, 13, 15]). The present work advances beyond these approaches by explicitly modeling the uncertainty as well as structure within the data. These ap- proaches only invent new predicates when nothing else works, whereas our approach is much more liberal about detecting latent structure. More closely related with this area is the approach of Popes-cul and Ungar [12]. Their algorithm uses an initial pre-processing step that learns clusterings and then treats cluster membership as an invented feature during learning. In contrast, in the present approach the learning task guides the construction of clusterings; it also allows reuse of clusters as part of new clusters, therefeby uncovering hierarchical structure.
Introducing latent variables into a Bayesian network often results in a simpler structure, yet it is difficult to automatically discover these latent variables from data. One line of work adds latentvariables to capture correlations among other variables in the Bayes net [7]. This works particularly well with structural constraints that have strong conditional independence assumptions [16]. A more advanced approach is that of Elidan et al. [4] identifies “near cliques” in the Bayes net, where introducing a latent variable would greatly reduce the number of arcs in this sub-structure. Our work goes beyond these approaches by operating in a relational setting. Consequently our new clusters are incorporated into the Bayes net only within the context of specific rules, or definite clauses. Such rules can capture a limited context around the cluster in which it is relevant.
Our work is not the first to combine ideas from latent variable discovery and predicate invention.
Also related to this work is that of Kemp et al. [8] who propose using an infinite relational model to cluster entities in a domain. The cluster that an entity is assigned to should be predictive of the relationships it satisfies. A weakness to this approach is that each entity can belong to only one cluster. Xu et al. [14] simultaneously came up with a similar idea. Kok and Domingos [9] propose an algorithm that learns multiple relational clusters (MRC). The MRC algorithm clusters both relations and entities, and it allows relations and entity can belong to more than one cluster. However, MRC is a transductive approach, rather than inductive approach. These approaches have been evaluated on domains that contain information on only between 100 and 200 objects. We have evaluated our approach on problems that are between one and two orders of magnitude larger. It is unlikely thatthese approaches would scale to problems of this size.
[1] Jesse Davis, Irene Ong, Jan Struyf, Elizabeth Burnside, David Page, and V´ıtor Santos Costa.
Change of representation for statistical relational learning. In Proceedings of the 20th Interna- tional Joint Conference on Artificial Intelligence, pages 2719–2726, 2007.
[2] Luc De Raedt, Paolo Frasconi, Kristian Kersting, and Stephen Muggleton, editors. Probabilis- tic inductive logic programming: theory and applications. Springer-Verlag, Berlin, Heidelberg, [3] T. G. Dietterich and R. S. Michalski. A comparative review of selected methods for learn- ing from examples. In Machine Learning: An Artificial Intelligence Approach, pages 41–81.
[4] G. Elidan, N. Lotner, N. Friedman, and D. Koller. Discovering hidden variables: A structure- based approach. In Advances in Neural Information Processing Systems 13, pages 479–485, [5] N. Friedman, D. Geiger, and M. Goldszmidt. Bayesian networks classifiers. Machine Learning, [6] L. Getoor and B. Taskar, editors. An Introduction to Statistical Relational Learning. MIT [7] A. Jakulin. Machine Learning Based on Attribute Interactions. PhD thesis, University of [8] C. Kemp, J. Tenenbaum, T. Griffiths, T. Yamada, and N. Ueda. Learning systems of concepts with an infinite relational model. In Proceedings of the 21st National Conference on Artificial [9] Stanley Kok and Pedro Domingos. Statistical predicate invention. In Proceedings of the 24th International Conference on Machine Learning, pages 433–440, 2007.
[10] Stephen Muggleton and Wray Buntine. Machine invention of first-order predicates by inverting resolution. In Proceedings of the 5th International Conference on Machine Learning, pages [11] Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference.
Morgan Kaufmann, San Mateo, California, 1988.
[12] A. Popescul and L. Ungar. Cluster-based concept invention for statistical relational learning.
In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 665–670, 2004.
[13] Ashwin Srinivasan, Stephen Muggleton, and Michael Bain. Distinguishing exeptions from noise in non-monotonic learning. In Proceedings of the 2nd Inductive Logic Programming [14] Z. Xu, V. Tresp, K. Yu, and H-P. Kriegel. Infinite hidden relational models. In Proceedings of the 22nd Conference on Uncertainty in Artificial Intelligence, 2006.
[15] J. Zelle, R. Mooney, and J. Konvisser. Combining top-down and bottom-up techniques in inductive logic programming. In Proceedings of the 11th International Conference on Machine [16] N. L. Zhang, T. D. Nielsen, and F. V. Jensen. Latent variable discovery in classification models.
Artificial Intelligence in Medicine, 30(3):283299, 2004.

Source: http://cracs.fc.up.pt/sites/default/files/C2011_vsc_snowbird.pdf