We propose—somewhat tongue-in-cheek, yet with serious implications—a new test for artificial intelligence: the ability to watch a 90-minute episode of the long-running German crime drama Tatort, and to explain every relevant detail. This involves reconstructing the evolving social network of characters, identifying their beliefs, desires, and intentions, and, crucially, determining who committed the crime. We argue that this task integrates narrative understanding, common-sense reasoning, social cognition, and theory of mind—and thus provides a uniquely challenging benchmark for AI.

Abstract Ensemble methods for stream mining necessitate managing multiple models and updating them as data distributions evolve. Considering the calls for more sustainability, established methods are however not sufficiently considerate of ensemble members’ computational expenses and instead overly focus on predictive capabilities. To address these challenges and enable green online learning, we propose heterogeneous online ensembles (HEROS). For every training step, HEROS chooses a subset of models from a pool of models initialized with diverse hyperparameter choices under resource constraints to train. We introduce a Markov decision process to theoretically capture the trade-offs between predictive performance and sustainability constraints. Based on this framework, we present different policies for choosing which models to train on incoming data. Most notably, we propose the novel $$\zeta $$ -policy, which focuses on training near-optimal models at reduced costs. Using a stochastic model, we theoretically prove that our $$\zeta $$ -policy achieves near optimal performance while using fewer resources compared to the best performing policy. In our experiments across 11 benchmark datasets, we find empiric evidence that our $$\zeta $$ -policy is a strong contribution to the state-of-the-art, demonstrating highly accurate performance, in some cases even outperforming competitors, and simultaneously being much more resource-friendly.

Abstract Automating scientific discovery has been one of the motivating tasks in the development of AI methods. The task of Equation Discovery (also called Symbolic Regression) is to learn a free-form symbolic equation from experimental data. Equation Discovery benchmarks, however, assume the experimental data as given. Recent successes in protein folding and material optimization, powered by advancements, amongst others, in reinforcement learning and deep learning, have renewed the broader community’s interest in applications of AI in science. Nonetheless, these successful applications do not necessarily lead to an improved understanding of the underlying phenomena, just as super-human chess engines do not necessarily lead to improved understanding of chess theory and practice. In this paper, we propose Science-Gym: a new testbed for basic physics understanding. To the best of our knowledge, Science-Gym is the first scientific discovery benchmark that requires agents to autonomously perform data collection, experimental design, and discover the underlying equations of phenomena. Science-Gym is a Python software library with Gym-compatible bindings. It offers seven scientific simulations, which reproduce basic physics and epidemiology principles: the law of the lever, projectile motion, the inclined plane, Lagrangian points in space, brachistochrones, the SIRV model, and the friction force of a droplet. In these environments, agents may be evaluated not only on their ability in e.g. balancing objects on the two beams of a lever, but more importantly on finding equations that describe the overall behavior of the dynamical system at hand.

Abstract The paper surveys automated scientific discovery, from equation discovery and symbolic regression to autonomous discovery systems and agents. It discusses the individual approaches from a "big picture" perspective and in context, but also discusses open issues and recent topics like the various roles of deep neural networks in this area, aiding in the discovery of human-interpretable knowledge. Further, we will present closed-loop scientific discovery systems, starting with the pioneering work on the Adam system up to current efforts in fields from material science to astronomy. Finally, we will elaborate on autonomy from a machine learning perspective, but also in analogy to the autonomy levels in autonomous driving. The maximal level, level five, is defined to require no human intervention at all in the production of scientific knowledge. Achieving this is one step towards solving the Nobel Turing Grand Challenge to develop AI Scientists: AI systems capable of making Nobel-quality scientific discoveries highly autonomously at a level comparable, and possibly superior, to the best human scientists by 2050.

Abstract Maintaining learning models in dynamic environments requires transparency for trust and compliance, particularly under regulatory frameworks like the Artificial Intelligence (AI) Act by the European Union. Data stream models must balance adaptability with interpretability, and to keep AI models effective in evolving contexts, maintaining transparency is essential. To address this, we introduce Soft Hoeffding Trees (SoHoT) as transparent, differentiable decision trees for data streams. SoHoTs use a novel routing function, leveraging the Hoeffding inequality for tree expansion, while gradient descent updates tree weights to adapt to drifting data distributions. Transparency is further enhanced with decision-rule-based feature importance and a sparse activation function, enabling selective subtree consideration for final predictions. We also provide a visualization of the model’s decision-making process for user interpretability. Evaluated on 20 data streams, SoHoT outperforms Hoeffding trees and competes with Hoeffding adaptive trees and soft trees under AUROC. We also demonstrate how to balance transparency and performance, by looking at the trade-off and measuring prediction performance per complexity, which showcases SoHoT’s benefits compared to existing data stream algorithms.

Abstract We reevaluate the pairwise learning to rank approach based on neural nets, called RankNet, and present a theoretical analysis of its architecture. We show mathematically that the model can, under certain conditions, learn reflexive, antisymmetric, and transitive relations, enabling simplified training and improved performance. Experimental results on the LETOR MSLR-WEB10K, MQ2007 and MQ2008 datasets show that the model outperforms numerous state-of-the-art methods (including a listwise approach), while being inherently simpler in structure and using a pairwise approach only.

Abstract Multi-relational databases are the basis of most consolidated data collections in science and industry today. Most learning and mining algorithms, however, require data to be represented in a propositional form. While there is a variety of specialized machine learning algorithms that can operate directly on multi-relational data sets, propositionalization algorithms transform multi-relational databases into propositional data sets, thereby allowing the application of traditional machine learning and data mining algorithms without their modification. One prominent propositionalization algorithm is RELAGGS by Krogel and Wrobel, which transforms the data by nested aggregations. We propose a new neural network based algorithm in the spirit of RELAGGS that employs trainable composite aggregate functions instead of the static aggregate functions used in the original approach. In this way, we can jointly train the propositionalization with the prediction model, or, alternatively, use the learned aggegrations as embeddings in other algorithms. We demonstrate the increased predictive performance by comparing N-RELAGGS with RELAGGS and multiple other state-of-the-art algorithms.

Peer learning is a novel high-level reinforcement learning framework for agents learning in groups. While standard reinforcement learning trains an individual agent in trial-and-error fashion, all on its own, peer learning addresses a related setting in which a group of agents, i.e., peers, learns to master a task simultaneously together from scratch. Peers are allowed to communicate only about their own states and actions recommended by others: "What would you do in my situation?". Our motivation is to study the learning behavior of these agents. We formalize the teacher selection process in the action advice setting as a multi-armed bandit problem and therefore highlight the need for exploration. Eventually, we analyze the learning behavior of the peers and observe their ability to rank the agents' performance within the study group and understand which agents give reliable advice. Further, we compare peer learning with single agent learning and a state-of-the-art action advice baseline. We show that peer learning is able to outperform single-agent learning and the baseline in several challenging discrete and continuous OpenAI Gym domains. Doing so, we also show that within such a framework complex policies from action recommendations beyond discrete action spaces can evolve.

Representation learning algorithms offer the opportunity to learn invariant representations of the input data with regard to nuisance factors. Many authors have leveraged such strategies to learn fair representations, i.e., vectors where information about sensitive attributes is removed. These methods are attractive as they may be interpreted as minimizing the mutual information between a neural layer's activations and a sensitive attribute. However, the theoretical grounding of such methods relies either on the computation of infinitely accurate adversaries or on minimizing a variational upper bound of a mutual information estimate. In this paper, we propose a methodology for direct computation of the mutual information between neurons in a layer and a sensitive attribute. We employ stochastically-activated binary neural networks, which lets us treat neurons as random variables. Our method is therefore able to minimize an upper bound on the mutual information between the neural representations and a sensitive attribute. We show that this method compares favorably with the state of the art in fair representation learning and that the learned representations display a higher level of invariance compared to full-precision neural networks.

Airport traffic surveillance requires reliable safety systems to prevent accidents in safety-critical areas. This paper examines airport aprons, where existing holding point protection systems have shown that they are sometimes not able to prevent accidents. One possible solution to this problem is the use of innovative sensor technology such as magnetometers. These sensors can be used to measure the distortion of the earth’s magnetic field by metallic objects. The main objective is to identify the geometrical pattern of a passing object by fusing coherent events, and classify it into a category based on its size. We propose a hypotheses-based multi-task framework for the classification of aircraft by making use of the estimated motion behaviour of a passing object. The framework includes statistical components, domain knowledge, and artificial intelligence solutions to infer the geometrical pattern and motion vector of an object from a predefined set of possible hypotheses. In future work, we aim to optimize the framework using synthetic and real-world data to increase its robustness and generalization ability to other airports.

In aviation there are many safety-critical domains where reliable safety systems are essential to prevent any kind of hazard. This paper focuses on airport aprons, where currently used holding point protection systems have shown to be not faultless, sometimes leading to avoidable accidents. One way to avoid such accidents is by means of innovative sensor technology, in our case, magnetometers, i.e. sensors measuring the distortion of the earth’s magnetic field by metallic objects. The main goal is to use the magnetometry data to detect passing aircraft and to capture their geometrical pattern as well as to estimate their motion vector. Therefore, we present a spatio-temporal cluster fusion and an event fusion algorithm. The cluster fusion can be applied as a post-processing step to any spatio-temporal clustering method and is able to more accurately represent aircraft patterns by integrating expert knowledge into the fusion process. In this context, we present a spatio-temporal cluster tree representation for a fast and accurate estimation of the motion vector. Finally, the data-driven event fusion is able to separate detected aircraft crossings into separate events by employing domain-knowledge. In future work, we aim to come up with a framework making use of the cluster results and estimated motion vector to classify and infer the position of an aircraft, before this is deployed as a real-time application.

BACKGROUND: Recent years have seen a surge of novel neural network architectures for the integration of multi-omics data for prediction. Most of the architectures include either encoders alone or encoders and decoders, i.e., autoencoders of various sorts, to transform multi-omics data into latent representations. One important parameter is the depth of integration: the point at which the latent representations are computed or merged, which can be either early, intermediate, or late. The literature on integration methods is growing steadily, however, close to nothing is known about the relative performance of these methods under fair experimental conditions and under consideration of different use cases. RESULTS: We developed a comparison framework that trains and optimizes multi-omics integration methods under equal conditions. We incorporated early integration, PCA and four recently published deep learning methods: MOLI, Super.FELT, OmiEmbed, and MOMA. Further, we devised a novel method, Omics Stacking, that combines the advantages of intermediate and late integration. Experiments were conducted on a public drug response data set with multiple omics data (somatic point mutations, somatic copy number profiles and gene expression profiles) that was obtained from cell lines, patient-derived xenografts, and patient samples. Our experiments confirmed that early integration has the lowest predictive performance. Overall, architectures that integrate triplet loss achieved the best results. Statistical differences can, overall, rarely be observed, however, in terms of the average ranks of methods, Super.FELT is consistently performing best in a cross-validation setting and Omics Stacking best in an external test set setting. CONCLUSIONS: We recommend researchers to follow fair comparison protocols, as suggested in the paper. When faced with a new data set, Super.FELT is a good option in the cross-validation setting as well as Omics Stacking in the external test set setting. Statistical significances are hardly observable, despite trends in the algorithms' rankings. Future work on refined methods for transfer learning tailored for this domain may improve the situation for external test sets. The source code of all experiments is available under https://github.com/kramerlab/Multi-Omics_analysis.

Ranking algorithms based on Neural Networks have been a topic of recent research. Ranking is employed in everyday applications like product recommendations, search results, or even in finding good candidates for hiring. However, Neural Networks are mostly opaque tools, and it is hard to evaluate why a specific candidate, for instance, was not considered. Therefore, for neural-based ranking methods to be trustworthy, it is crucial to guarantee that the outcome is fair and that the decisions are not discriminating people according to sensitive attributes such as gender, sexual orientation, or ethnicity.In this work we present a family of fair pairwise learning to rank approaches based on Neural Networks, which are able to produce balanced outcomes for underprivileged groups and, at the same time, build fair representations of data, i.e. new vectors having no correlation with regard to a sensitive attribute. We compare our approaches to recent work dealing with fair ranking and evaluate them using both relevance and fairness metrics. Our results show that the introduced fair pairwise ranking methods compare favorably to other methods when considering the fairness/relevance trade-off.

Learning higher-level representations from data has been on the agenda of AI research for several decades. In the paper, I will give a survey of various approaches to learning symbolic higher-level representations: feature construction and constructive induction, predicate invention, propositionalization, pattern mining, and mining time series patterns. Finally, I will give an outlook on how approaches to learning higher-level representations, symbolic and neural, can benefit from each other to solve current issues in machine learning.

Multi-label classification deals with the task of predicting multiple class labels for a given sample. Several performance metrics are designed in the literature to measure the quality of any multi-label classification technique. In general existing multi-label classification approaches focus on optimizing only a single performance measure. The current work builds on the hypothesis that a weighted ensemble of multiple multi-label classifiers will lead to obtain improved results. The appropriate weight combinations for combining the outputs of multiple classifiers can be selected after simultaneously optimizing different multi-label classification metrics like micro F1, hamming loss, 0/1 loss, accuracy, etc. The problem is posed as a multi-objective optimization problem where a set of 13 conflicting objective functions are simultaneously optimized using the search capability of a multi-objective genetic algorithm based technique, namely NSGA-II. The weights of votes for a classifier for different class labels vary over a range quantifying the degrees of confidence of a classifier for different class labels. Several base classifiers are utilized for solving the problem of multi-objective multi-label classification. The effectiveness of the proposed multi-objective based multi-label classifier ensemble approach is shown for 10 data sets of varying complexities, and comparisons are reported for several existing techniques. Obtained experimental results clearly illustrate the efficacy of the proposed technique.

Recent work on variational autoencoders (VAEs) has enabled the development of generative topic models using neural networks. Topic models based on latent Dirichlet allocation (LDA) successfully use the Dirichlet distribution as a prior for the topic and word distributions to enforce sparseness. However, there is a trade-off between sparsity and smoothness in Dirichlet distributions. Sparsity is important for a low reconstruction error during training of the autoencoder, whereas smoothness enables generalization and leads to a better log-likelihood of the test data. Both of these properties are encoded in the Dirichlet parameter vector. By rewriting this parameter vector into a product of a sparse binary vector and a smoothness vector, we decouple the two properties, leading to a model that features both a competitive topic coherence and a high log-likelihood. Efficient training is enabled using rejection sampling variational inference for the reparameterization of the Dirichlet distribution. Our experiments show that our method is competitive with other recent VAE topic models.

Due to their disclosure required by law, business management reports have become publicly available for a large number of companies, and these reports offer the opportunity to assess the financial health or distress of a company, both quantitatively from the balance sheets and qualitatively from the text. In this paper, we analyze the potential of deep sentiment mining from the textual parts of business management reports and aim to detect signals for financial distress. We (1) created the largest corpus of business reports analyzed qualitatively to date, (2) defined a non-trivial target variable based on the so-called Altman Z-score, (3) developed a filtering of sentences based on class-correlated pattern mining to reduce the complexity of these long and complex texts, and (4) employed one of the best-performing machine learning methods for this type of task, Dependency Sensitive Convolutional Neural Networks (DSCNNs). Experimental results show that strong prediction performance can be achieved by a suitable bundle of methods, with an F1-score of more than 0.86 and a Kappa score of more than 65%. To better understand the parts of management reports that indicate financial distress, the prediction engine is complemented by a visualization tool that highlights critical text passages.

Density estimation of streaming data is a relevant task in numerous domains. In this paper, a novel non-parametric density estimator called FRONT (forest of normalized trees) is introduced. It uses a structure of multiple normalized trees, segments the feature space of the data stream through a periodically updated linear transformation and is able to adapt to ever evolving data streams. FRONT provides accurate density estimation and performs favorably compared to existing online density estimators in terms of the average log score on multiple standard data sets. Its low complexity, linear runtime as well as constant memory usage, makes FRONT by design suitable for large data streams. Finally, the paper provides a variation of FRONT called N-FRONT suitable for statistically independent data streams and correction methods for badly initialized trees to further improve performance.

Boolean Matrix Factorization (BMF) is a commonly used technique in the field of unsupervised data analytics. The goal is to decompose a ground truth matrix C into a product of two matrices A and B being either an exact or approximate rank k factorization of C. Both exact and approximate factorization are time-consuming tasks due to their combinatorial complexity. In this paper, we introduce a massively parallel implementation of BMF - namely cuBool - in order to significantly speed up factorization of huge Boolean matrices. Our approach is based on alternately adjusting rows and columns of A and B using thousands of lightweight CUDA threads. The massively parallel manipulation of entries enables full usage of all available cores on modern CUDA-enabled GPUs. Additionally, modelling up to 32 consecutive entries of the Boolean matrices A, Band C as 32-bit integer results in fewer data accesses and faster computation of inner products. This bit-parallel approach allows for a significant decrease of memory requirements in contrast to gradient-based continuous updates of entries on dense representations. cuBool is compared to other state-of-the-art matrix factorization algorithms. Experiments on a number of real-world data sets show highly competitive results at only a fraction of computation time. cuBool proves to be a good compromise between low run time and a high-quality factorization for the decomposition of large-scale Boolean matrices. It can freely be accessed under https://github.com/funatiq/cubool.

For explicit representation of commonality and variability of a product line, a feature model is mostly used. An open question is how a feature model can be inductively learned in an automated way from a limited number of given product specifications in terms of features.

We present a new multiview clustering approach based on multiobjective optimization. In contrast to existing clustering algorithms based on multiobjective optimization, it is generally applicable to data represented by two or more views and does not require specifying the number of clusters a priori . The approach builds upon the search capability of a multiobjective simulated annealing based technique, AMOSA, as the underlying optimization technique. In the first version of the proposed approach, an internal cluster validity index is used to assess the quality of different partitionings obtained using different views. A new way of checking the compatibility of these different partitionings is also proposed and this is used as another objective function. A new encoding strategy and some new mutation operators are introduced. Finally, a new way of computing a consensus partitioning from multiple individual partitions obtained on multiple views is proposed. As a baseline and for comparison, two multiobjective based ensemble clustering techniques are proposed to combine the outputs of different simple clustering approaches. The efficacy of the proposed clustering methods is shown for partitioning several real-world datasets having multiple views. To show the practical usefulness of the method, we present results on web-search result clustering, where the task is to find a suitable partitioning of web snippets.

Clustering very large datasets while preserving cluster quality remains a challenging data-mining task to date. In this paper, we propose an effective scalable clustering algorithm for large datasets that builds upon the concept of synchronization. Inherited from the powerful concept of synchronization, the proposed algorithm, CIPA (Clustering by Iterative Partitioning and Point Attractor Representations), is capable of handling very large datasets by iteratively partitioning them into thousands of subsets and clustering each subset separately. Using dynamic clustering by synchronization, each subset is then represented by a set of point attractors and outliers. Finally, CIPA identifies the cluster structure of the original dataset by clustering the newly generated dataset consisting of points attractors and outliers from all subsets. We demonstrate that our new scalable clustering approach has several attractive benefits: (a) CIPA faithfully captures the cluster structure of the original data by performing clustering on each separate data iteratively instead of using any sampling or statistical summarization technique. (b) It allows clustering very large datasets efficiently with high cluster quality. (c) CIPA is parallelizable and also suitable for distributed data. Extensive experiments demonstrate the effectiveness and efficiency of our approach.

Discovering changes in the data distribution of streams and discovering recurrent data distributions are challenging problems in data mining and machine learning. Both have received a lot of attention in the context of classification. With the ever increasing growth of data, however, there is a high demand of compact and universal representations of data streams that enable the user to analyze current as well as historic data without having access to the raw data. To make a first step towards this direction, we propose a condensed representation that captures the various - possibly recurrent - data distributions of the stream by extending the notion of possible worlds. The representation enables queries concerning the whole stream and can, hence, serve as a tool for supporting decision-making processes or serve as a basis for implementing data mining and machine learning algorithms on top of it. We evaluate this condensed representation on synthetic and real-world data.

While the physiological response of humans to emotional events or stimuli is well-investigated for many modalities (like EEG, skin resistance, ...), surprisingly little is known about the exhalation of so-called Volatile Organic Compounds (VOCs) at quite low concentrations in response to such stimuli. VOCs are molecules of relatively small mass that quickly evaporate or sublimate and can be detected in the air that surrounds us. The paper introduces a new field of application for data mining, where trace gas responses of people reacting on-line to films shown in cinemas (or movie theaters) are related to the semantic content of the films themselves. To do so, we measured the VOCs from a movie theater over a whole month in intervals of thirty seconds, and annotated the screened films by a controlled vocabulary compiled from multiple sources. To gain a better understanding of the data and to reveal unknown relationships, we have built prediction models for so-called forward prediction (the prediction of future VOCs from the past), backward prediction (the prediction of past scene labels from future VOCs), which is some form of abductive reasoning, and Granger causality. Experimental results show that some VOCs and some labels can be predicted with relatively low error, and that hint for causality with low p-values can be detected in the data. The data set is publicly available at: https://github.com/jorro/smelloffear.

Data mining and machine learning algorithms usually operate directly on the data. However, if the data is not available at once or consists of billions of instances, these algorithms easily become infeasible with respect to memory and run-time concerns. As a solution to this problem, we propose a framework, called MiDEO (Mining Density Estimates inferred Online), in which algorithms are designed to operate on a condensed representation of the data. In particular, we propose to use density estimates, which are able to represent billions of instances in a compact form and can be updated when new instances arrive. As an example for an algorithm that operates on density estimates, we consider the task of mining association rules, which we consider as a form of simple statements about the data. The algorithm, called POEt (Pattern mining on Online density esTimates), is evaluated on synthetic and real-world data and is compared to state-of-the-art algorithms.

Subgroup discovery is the task of identifying subgroups that show the most unusual statistical (distributional) characteristics with respect to a given target variable, at the intersection of predictive and descriptive induction. Redundancy and lack of rule interpretability constitute the major challenges in subgroup discovery today. We address these two issues by constrained latent Dirichlet allocation (LDA) to identify co-occurring feature values (descriptions) for subgroup rule search, obtaining a less redundant and more diverse rule set. Latent Dirichlet Allocation, as a topic modeling approach, is able to identify diverse topics, from which the rules can be derived. The resulting rules are less redundant and can also be interpreted by the corresponding topic. Experimental results on six benchmark datasets show that the presented approach provides rule sets with better rule redundancy and diversity compared to those of four existing algorithms. One unique and interesting advantage of the proposed method is that it can categorize rules by topics as well as the assignment of a probability to each feature value of a discovered rule, which can be used in the interpretation of the results.

Data stream mining has gained growing attentions due to its wide emerging applications such as target marketing, email filtering and network intrusion detection. In this paper, we propose a prototype-based classification model for evolving data streams, called SyncStream, which dynamically models time-changing concepts and makes predictions in a local fashion. Instead of learning a single model on a sliding window or ensemble learning, SyncStream captures evolving concepts by dynamically maintaining a set of prototypes in a new data structure called the P-tree. The prototypes are obtained by error-driven representativeness learning and synchronization-inspired constrained clustering. To identify abrupt concept drift in data streams, PCA and statistics based heuristic approaches are employed. SyncStream has several attractive benefits: (a) It is capable of dynamically modeling evolving concepts from even a small set of prototypes and is robust against noisy examples. (b) Owing to synchronization-based constrained clustering and the P-Tree, it supports an efficient and effective data representation and maintenance. (c) Gradual and abrupt concept drift can be effectively detected. Empirical results shows that our method achieves good predictive performance compared to state-of-the-art algorithms and that it requires much less time than another instance-based stream mining algorithm.

Incremental linear model trees with approximate lookahead are fast, but produce overly large trees. This is due to non-optimal splitting decisions boosted by a possibly unlimited number of examples obtained from a data source. To keep the processing speed high and the tree complexity low, appropriate incremental pruning techniques are needed. In this paper, we introduce a pruning technique for the class of incremental linear model trees with approximate lookahead on stationary data sources. Experimental results show that the advantage of approximate lookahead in terms of processing speed can be further improved by producing much smaller and consequently more explanatory, less memory consuming trees on high-dimensional data. This is done at the expense of only a small increase in prediction error. Additionally, the pruning algorithm can be tuned to either produce less accurate model trees at a much higher processing speed or, alternatively, more accurate trees at the expense of higher processing times.

We address the problem of estimating a discrete joint density online, that is, the algorithm is only provided the current example and its current estimate. The proposed online estimator of discrete densities, EDDO (Estimation of Discrete Densities Online), uses classifier chains to model dependencies among features. Each classifier in the chain estimates the probability of one particular feature. Because a single chain may not provide a reliable estimate, we also consider ensembles of classifier chains and ensembles of weighted classifier chains. For all density estimators, we provide consistency proofs and propose algorithms to perform certain inference tasks. The empirical evaluation of the estimators is conducted in several experiments and on data sets of up to several million instances: We compare them to density estimates computed from Bayesian structure learners, evaluate them under the influence of noise, measure their ability to deal with concept drift, and measure the run-time performance. Our experiments demonstrate that, even though designed to work online, EDDO delivers estimators of competitive accuracy compared to batch Bayesian structure learners and batch variants of EDDO.

Quantitative structure–activity relationships are regression models relating chemical structure to biological activity. Such models allow to make predictions for toxicologically relevant endpoints, which constitute the target outcomes of experiments. The task is often tackled by instance-based methods, which are all based on the notion of chemical (dis-)similarity. Our starting point is the observation by Raymond and Willett that the two families of chemical distance measures, fingerprint-based and maximum common subgraph-based measures, provide orthogonal information about chemical similarity. This paper presents a novel method for finding suitable combinations of them, called adapted transfer, which adapts a distance measure learned on another, related dataset to a given dataset. Adapted transfer thus combines distance learning and transfer learning in a novel manner. In our experiments, we visualize the performance of the methods by learning curves and present a quantitative comparison for 10 and 100% of the maximum training set size to show that transfer exploiting source datasets is effective with small training datasets. Additionally, we present an approach to select the source task in a data-driven manner. The relevant experiments include an example that shows that the selection of a meaningful source task is a critical factor for transfer learning.

The growing number of time-labeled datasets in science and industry increases the need for algorithms that automatically induce process models. Existing methods are capable of identifying process models that typically only work on single attribute events. We propose a new model type to address the problem of mining multi-attribute events, meaning that each event is described by a vector of attributes. The model is based on timed automata, includes expressive descriptions of states and can be used for making predictions. A probabilistic real time automaton is created, where each state is annotated by a profile of events. To identify the states of the automaton, similar events are combined by a clustering approach. The method was implemented and tested on a synthetic, a medical and a biological dataset. Its prediction accuracy was evaluated on a medical dataset and compared to a combined logistic regression, which is considered a standard in this application domain. Moreover, the method was experimentally compared to Multi-Output HMMs and Petri nets learned by standard process mining algorithms. The experimental comparison suggests that the automaton-based approach performs favorably in several dimensions. Most importantly, we show that meaningful medical and biological process knowledge can be extracted from such automata.

Probabilistic real time automata (PRTAs) are a representation of dynamic processes arising in the sciences and industry. Currently, the induction of automata is divided into two steps: the creation of the prefix tree acceptor (PTA) and the merge procedure based on clustering of the states. These two steps can be very time intensive when a PRTA is to be induced for massive or even unbounded data sets. The latter one can be efficiently processed, as there exist scalable online clustering algorithms. However, the creation of the PTA still can be very time consuming. To overcome this problem, we propose a genuine online PRTA induction approach that incorporates new instances by first collapsing them and then using a maximum frequent pattern based clustering. The approach is tested against a predefined synthetic automaton and real-world data sets, for which the approach is scalable and stable. Moreover, we present a broad evaluation on a real world disease group data set that shows the applicability of such a model to the analysis of medical processes.

In recent years, graph kernels have received considerable interest within the machine learning and data mining community. Here, we introduce a novel approach enabling kernel methods to utilize additional information hidden in the structural neighborhood of the graphs under consideration. Our novel structural cluster kernel (SCK) incorporates similarities induced by a structural clustering algorithm to improve state-of-the-art graph kernels. The approach taken is based on the idea that graph similarity can not only be described by the similarity between the graphs themselves, but also by the similarity they possess with respect to their structural neighborhood. We applied our novel kernel in a supervised and a semi-supervised setting to regression and classification problems on a number of real-world datasets of molecular graphs.

The paper presents a scalable method for learning probabilistic real-time automata (PRTAs), a new type of model that captures the dynamics of multi-dimensional event logs. In multi-dimensional event logs, events are described by several features instead of only one symbol. Moreover, it is not clear up front which events occur in an event log. The learning method to find a PRTA that models such an event log is based on the state merging of a prefix tree acceptor, which is guided by a clustering to determine the states of the automaton. To make the overall approach scalable, an online clustering method based on maximum frequent patterns (MFPs) is used. The approach is evaluated on a synthetic, a biological and a medical data set. The results show that the induction of automata using MFP-based clustering gives easy to understand and stable automata, but most importantly, makes it scalable to large data sets.

UNLABELLED: Pyrosequencing technologies are frequently used for sequencing the 16S ribosomal RNA marker gene for profiling microbial communities. Clustering of the produced reads is an important but time-consuming task. We present Dynamic Seed-based Clustering (DySC), a new tool based on the greedy clustering approach that uses a dynamic seeding strategy. Evaluations based on the normalized mutual information (NMI) criterion show that DySC produces higher quality clusters than UCLUST and CD-HIT at a comparable runtime. AVAILABILITY AND IMPLEMENTATION: DySC, implemented in C, is available at http://code.google.com/p/dysc/ under GNU GPL license.

In many clustering applications the incorporation of background knowledge in the form of constraints is desirable. In this paper, we introduce a new constraint type and the corresponding clustering problem: attribute constrained clustering. The goal is to induce clusters of binary instances that satisfy constraints on the attribute level. These constraints specify whether instances may or may not be grouped to a cluster, depending on specific attribute values. We show how the well-established instance-level constraints, must-link and cannot-link, can be adapted to the attribute level. A variant of the k-Medoids algorithm taking into account attribute level constraints is evaluated on synthetic and real-world data. Experimental results show that such constraints may provide better clustering results at lower specification costs if constraints can be expressed on the attribute level.

MOTIVATION: The slow growth of expert-curated databases compared to experimental databases makes it necessary to build upon highly accurate automated processing pipelines to make the most of the data until curation becomes available. We address this problem in the context of protein structures and their classification into structural and functional classes, more specifically, the structural classification of proteins (SCOP). Structural alignment methods like Vorolign already provide good classification results, but effectively work in a 1-Nearest Neighbor mode. Model-based (in contrast to instance-based) approaches so far have been shown to be of limited values due to small classes arising in such classification schemes. RESULTS: In this article, we describe how kernels defined in terms of Vorolign scores can be used in SVM learning, and explore variants of combined instance-based and model-based learning, up to exclusively model-based learning. Our results suggest that kernels based on Vorolign scores are effective and that model-based learning can yield highly competitive classification results for the prediction of SCOP families. AVAILABILITY: The code is made available at: http://wwwkramer.in.tum.de/research/applications/vorolign-kernel.

Many methods for quantitative structure-activity relationships (QSARs) deliver point estimates only, without quantifying the uncertainty inherent in the prediction. One way to quantify the uncertainy of a QSAR prediction is to predict the conditional density of the activity given the structure instead of a point estimate. If a conditional density estimate is available, it is easy to derive prediction intervals of activities. In this paper, we experimentally evaluate and compare three methods for conditional density estimation for their suitability in QSAR modeling. In contrast to traditional methods for conditional density estimation, they are based on generic machine learning schemes, more specifically, class probability estimators. Our experiments show that a kernel estimator based on class probability estimates from a random forest classifier is highly competitive with Gaussian process regression, while taking only a fraction of the time for training. Therefore, generic machine-learning based methods for conditional density estimation may be a good and fast option for quantifying uncertainty in QSAR modeling.

Contact: [email protected] Supplementary information: Supplementary data are available at Bioinformatics online. Data mining is a cornerstone of modern bioinformatics. Techniques such as feature selection or data-driven model (classifier) building are used broadly in many fields including gene expression data analysis (Wood et al., 2007), proteomics (Barla et al., 2008), secondary and tertiary protein structure prediction (Heringa, 2000; Kryshtafovych et al., 2007), prediction of experimental behavior of proteins or other molecules (Liao et al., 2006; Smialowski et al., 2007) and medical science (Patel and Goyal, 2007). It is widely accepted that any model building requires stringent evaluation of its performance and generalization capabilities using well-established methods such as k-fold cross-validation, leave-one-out cross-validation, bootstrap and others (Frank et al., 2004). The growing complexity of the data and the urge to improve available methods have led to the development of procedures combining feature selection and model building. Feature selection is often used to limit the amount and dimensionality of the data or to select features that correlate well with the target class. Feature selection methods can be subdivided into those that are unsupervised, i.e. unaware of class attributes [e.g. removal of a feature with the same constant values throughout the whole dataset, PCA (principal component analysis), MF (matrix factorization)] and those that are supervised, i.e. driven by class information. The latter group includes filter methods using, e.g. information gain as well as the Wrapper approach (Witten and Frank, 2005). Special consideration is required when supervised feature selection is used to construct input data for model building (classification). In order to correctly evaluate classifiers built on such projected data, the entire procedure including feature selection and model training has to be evaluated against independent data. In other words, the test set must not be used for supervised feature selection (or more generally, supervised preprocessing). Otherwise, estimates of the classifiers’ performance will be over optimistic (Ambroise and McLachlan, 2002; Efron, 2005; Kohavi and John, 1997; Molinaro et al., 2005; Reunane, 2004). Any model building method integrated with feature selection must be externally evaluated. Evaluation must include both: supervised feature selection and classification and should not be limited to classification only (Fig. 1). The correct [(A) followed (C)] and the incorrect [(B) followed by (C)] procedure for combining supervised feature selection and learning a classifier. In the figure, processes and products are depicted by ellipses and rectangles, respectively. Training and test sets consist of features X and a target attribute Y (to be predicted). X′ is a subset of features reduced by supervised feature selection, f() is a classifier and Ŷ contains the prediction of Y values by this function. (A and B) show the workflows for the correct and incorrect application of supervised feature selection, and (C) holds the evaluation workflow (more description in the text). The correct procedure is depicted in Figure 1 and consists of the workflow from Figure 1A for training and Figure 1C for testing (evaluation). In a preprocessing step, supervised feature selection reduces the set of features X to a subset X′ (Y is the target attribute). Subsequently, the reduced training set is used to infer a classifier f(). During testing (Fig. 1C), the trained classifier f() is evaluated using an independent test set with the feature space reduced to X′ according to the feature selection derived in the previous step (Fig. 1A). The classifier predicts Ŷ for each instance. Various performance measures can then be calculated by comparing the predictions Ŷ with the true values for Y. In contrast with this procedure, the most common mistake (according to our observation) of machine learning applications in the life sciences is illustrated in Figure 1B: both training and test sets are used for supervised feature selection. After that, a classifier f() is learned from the reduced training set as before. During testing, this classifier is applied to the test set as described above (Fig. 1C). However, as evident from the illustration, information from the test set has already been used for the inference of the classifier, by choosing an appropriate subset of features for the learning algorithm (Fig. 1B). Therefore, class information from the test set has leaked to the training phase. This analysis remains true for classification and regression and regardless whether training and test sets are created as part of a k-fold cross-validation or any other method. Recently, it has repeatedly come to our attention while reading or reviewing manuscripts submitted to Bioinformatics and other journals that often no proper external evaluations of the whole method consisting of supervised feature selection and subsequent classification is provided. In this brief note we would like to demonstrate the consequences of this type of a mistake for classification performance estimation using data where attribute values are generated randomly as well as data with random class assignments. We also estimate the consequences of such erroneous overoptimism as a function of the dataset size. For simplicity, we focus only on classification and leave out regression methods. Three types of datasets were used in this study. All have 21 attributes: 20 frequencies of amino acids and one class attribute assigning each instance to one of two classes. Datasets of the first type (randomly generated attributes) contain real random attribute values resembling natural frequency distributions of 20 amino acids. To generate randomly perturbated frequencies of the 20 amino acids, we used Gaussian random numbers with peak maximums at their natural occurrence frequencies (as provided at http://prowl.rockefeller.edu/aainfo/struct.htm) and standard deviation (SD) equal to 0.25 of this value. All negative values were set to 0 and the sum of 20 frequencies for a given instance was not allowed to be greater than 100. Datasets of the second type (randomize class data) consist of instances picked randomly from a dataset of 1000 proteins of which a half showed good solubility upon heterologous expression in Escherichia coli, while the other half was notoriously insoluble. Classes of these instances—soluble or non-soluble—were assigned randomly. Third type of datasets (real data) was same as second except that real class labels were preserved. Quantum Random Bit Generator Service (QRBG; Stevanovic et al., 2008) was used as a source of seeds for random numbers. We maintained even class distribution at all times. For selecting the best features, the following methods were used: Wrapper (Kohavi and John, 1997), Relief Attribute Evaluation with Ranker (Witten and Frank, 2005) and PCA (Pearson, 1901). The Wrapper method takes into account class information by evaluating feature sets based on the performance of the classifier. Hence, the resulting feature set is tailored to a given classification method. In our comparison, the Wrapper method is the most ‘aggressive’ feature selection method. It was setup to use Naive Bayes for classification and Best First for attribute space search (Witten and Frank, 2005). The Relief method is also supervised, but does not optimize feature sets directly for classifier performance. Thus, it takes into account class information in a ‘less aggressive’ manner than the Wrapper method. The threshold of Ranker coupled to the Relief Attribute Evaluation method was set to zero. PCA (Jolliffe, 2002) is an unsupervised feature selection method and hence does not take into account class information at all. PCA dimensionality reduction was accomplished by the following steps: data normalization, calculation of orthonormal vectors [PC (principal components)], sorting PC according to decreasing variance. We save PC accounting cumulatively for 95% of the data variance (Jolliffe, 2002). Naive Bayes and nearest neighbor IB1 (Aha and Kibler, 1991) algorithms were used for classification, because they are among the simplest and most fundamental classification methods. Classifiers were trained and evaluated using 10-fold cross-validation. MCC (Matthew's correlation coefficient) and AUROC (area under receiver operating curve) were calculated to measure classifier performance. For each dataset size, feature selection and classification algorithm the whole procedure starting from data construction was repeated 30 times. Overfitting (overoptimism) was measured as the difference in classification performance (denoted by ΔAUROC in the following) on data after and before feature selection, averaged over 30 trials. Information density is defined as the number of instances per number of attributes. For datasets resulting from feature selection, we calculate the information density ratio (ID ratio, the factor by which the number of features is reduced) to measure loss of information. We generated a range of datasets containing between 10 and 1000 instances. For both types of randomize datasets, half of the data were tagged with the ‘no’ class and the rest with ‘yes’ to simulate a two class problem with an even class distribution. We found that using supervised feature selection with dataset containing both training and test sets leads to a significant overoptimistic assessment of classifier performance. This holds true for datasets with randomly generated attribute values, randomized class data (Fig. 2) and real data (Supplementary Fig. 1, Supplementary Table 1). The extent of overfitting depends on the dataset size. The strongest overfitting (AUROC increase ∼0.5) was observed for the smallest real datasets with random class labels using the Wrapper method. Classification on randomly generated attribute data exhibits a slightly smaller increase (∼0.4) (data with real class labels also reached 0.4). These values are extremely high considering that the AUROC ranges from 0.5 for random guessing to 1.0 for the best theoretically possible model. Improper use of feature selection also distorts classifier performance when larger datasets are used. Even for datasets with 1000 instances we observed slight albeit statistically significant increase in AUROC values (0.04) (whiskers in Fig. 2 mark 95% confidence intervals). As seen in Figure 2, the use of both the Wrapper and the Relief feature selection algorithms results in falsified measures of classifier performance. Application of PCA which is not supervised did not lead to substantial overfitting on any tested dataset. Relation between the number of instances and the extent of overfitting caused by feature selection as measured by AUROC growth. (A) Randomly generated attribute values, (B) randomly tagged real data. Three different feature selection algorithms were used: Wrapper (hashed bars), Relief Attribute Evaluation (white bars), PCA (black bars). Whiskers mark 95% confidence intervals. Feature selection reduces the amount of information by lowering the number of attributes and thus leads to an increase of the ratio between the number of instances and the number of attributes. We assessed the extent of information loss by calculating the ID ratio between datasets before and after feature selection as described above. A higher ID ratio means that a higher percentage of features was removed. For example, ID ratio = 2, means that after feature selection the number of attributes is reduced by two. For each of the feature selection method, we found that the more features got removed, the stronger were the effects of overfitting (Fig. 3). Interestingly, there are also differences between attribute selection algorithms. Wrapper seems to be less prone to overfitting compared with the Relief method. By almost the same magnitude of overfitting (increase in AUROC 0.25), it reduces the information content more effectively (4.5 times) compared with Relief (2.5 times). Wrappers reduce the number of features stronger than Relief method possibly because it comprehensively evaluates also combinations of features, selecting features based on not only their own relevancy but also redundancy (Kohavi and John, 1997). Moreover, Wrapper efficiency in feature selection depends on internally employed classifier and search algorithms. Data with randomly generated attribute values showed higher resistance against classification bias permitting a greater decrease in the feature number compared with real data with randomized class tags and real data. PCA did not cause overfitting while still being able to slightly reduce the number of attributes of all data types. Similar results were obtained when MCC was used instead of AUROC and also when the whole analysis was repeated using the IB1 nearest neighbor classification method (Supplementary Table 1, Data not shown). Relation between information loss and overfitting measured by ΔAUROC growth. (A) Randomly generated attribute values, (B) randomly tagged real data. Three feature selection methods were examined: Wrapper (black circles), Relief Attribute Evaluation (open squares) and PCA (gray triangles). Lines were fitted by linear regression: solid lines to Wrapper and dashed to Relief Attribute Evaluation data points. ID ratio is the information density ratio. In summary, we show that supervised feature selection coupled with or integral to model building (classification) requires external evaluation. Failure in setting up evaluation with external data (Fig. 1B) leads to overoptimism in the assessment of classifier performance. It is reasonable to expect that overfitting will be at least in the same order of magnitude as what is observed on randomly generated data for most of the real life classification tasks, where amino acid composition is used as input. Real data may be more prone to overfitting because they are likely to contain more patterns than randomly generated data. Even if patterns are orthogonal to the problem under consideration overfitting can still occur. For this reason, whenever model building (classification) is integrated with supervised attribute selection, it is crucial to evaluate classifiers with the data not used for attribute selection (Fig. 1 A and C). Conflict of Interest: none declared.

MOTIVATION: Current methods for the prediction of biodegradation products and pathways of organic environmental pollutants either do not take into account domain knowledge or do not provide probability estimates. In this article, we propose a hybrid knowledge- and machine learning-based approach to overcome these limitations in the context of the University of Minnesota Pathway Prediction System (UM-PPS). The proposed solution performs relative reasoning in a machine learning framework, and obtains one probability estimate for each biotransformation rule of the system. As the application of a rule then depends on a threshold for the probability estimate, the trade-off between recall (sensitivity) and precision (selectivity) can be addressed and leveraged in practice. RESULTS: Results from leave-one-out cross-validation show that a recall and precision of approximately 0.8 can be achieved for a subset of 13 transformation rules. Therefore, it is possible to optimize precision without compromising recall. We are currently integrating the results into an experimental version of the UM-PPS server. AVAILABILITY: The program is freely available on the web at http://wwwkramer.in.tum.de/research/applications/biodegradation/data. CONTACT: [email protected].

Automatic classification of proteins using machine learning is an important problem that has received significant attention in the literature. One feature of this problem is that expert-defined hierarchies of protein classes exist and can potentially be exploited to improve classification performance. In this article, we investigate empirically whether this is the case for two such hierarchies. We compare multiclass classification techniques that exploit the information in those class hierarchies and those that do not, using logistic regression, decision trees, bagged decision trees, and support vector machines as the underlying base learners. In particular, we compare hierarchical and flat variants of ensembles of nested dichotomies. The latter have been shown to deliver strong classification performance in multiclass settings. We present experimental results for synthetic, fold recognition, enzyme classification, and remote homology detection data. Our results show that exploiting the class hierarchy improves performance on the synthetic data but not in the case of the protein classification problems. Based on this, we recommend that strong flat multiclass methods be used as a baseline to establish the benefit of exploiting class hierarchies in this area.

We present a new approach to large-scale graph mining based on so-called backbone refinement classes. The method efficiently mines tree-shaped subgraph descriptors under minimum frequency and significance constraints, using classes of fragments to reduce feature set size and running times. The classes are defined in terms of fragments sharing a common backbone. The method is able to optimize structural inter-feature entropy as opposed to occurrences, which is characteristic for open or closed fragment mining. In the experiments, the proposed method reduces feature set sizes by >90 % and >30 % compared to complete tree mining and open tree mining, respectively. Evaluation using crossvalidation runs shows that their classification accuracy is similar to the complete set of trees but significantly better than that of open trees. Compared to open or closed fragment mining, a large part of the search space can be pruned due to an improved statistical constraint (dynamic upper bound adjustment), which is also confirmed in the experiments in lower running times compared to ordinary (static) upper bound pruning. Further analysis using large-scale datasets yields insight into important properties of the proposed descriptors, such as the dataset coverage and the class size represented by each descriptor. A final cross-validation run confirms that the novel descriptors render large training sets feasible which previously might have been intractable.

BACKGROUND: The breadth of biological databases and their information content continues to increase exponentially. Unfortunately, our ability to query such sources is still often suboptimal. Here, we introduce and apply community voting, database-driven text classification, and visual aids as a means to incorporate distributed expert knowledge, to automatically classify database entries and to efficiently retrieve them. RESULTS: Using a previously developed peptide database as an example, we compared several machine learning algorithms in their ability to classify abstracts of published literature results into categories relevant to peptide research, such as related or not related to cancer, angiogenesis, molecular imaging, etc. Ensembles of bagged decision trees met the requirements of our application best. No other algorithm consistently performed better in comparative testing. Moreover, we show that the algorithm produces meaningful class probability estimates, which can be used to visualize the confidence of automatic classification during the retrieval process. To allow viewing long lists of search results enriched by automatic classifications, we added a dynamic heat map to the web interface. We take advantage of community knowledge by enabling users to cast votes in Web 2.0 style in order to correct automated classification errors, which triggers reclassification of all entries. We used a novel framework in which the database "drives" the entire vote aggregation and reclassification process to increase speed while conserving computational resources and keeping the method scalable. In our experiments, we simulate community voting by adding various levels of noise to nearly perfectly labelled instances, and show that, under such conditions, classification can be improved significantly. CONCLUSION: Using PepBank as a model database, we show how to build a classification-aided retrieval system that gathers training data from the community, is completely controlled by the database, scales well with concurrent change events, and can be adapted to add text classification capability to other biomedical databases.The system can be accessed at http://pepbank.mgh.harvard.edu.

In the demonstration, we will present the concepts and an implementation of an inductive database -- as proposed by Imielinski and Mannila -- in the relational model. The goal is to support all steps of the knowledge discovery process, from pre-processing via data mining to post-processing, on the basis of queries to a database system. The query language SIQL (structured inductive query language), an SQL extension, offers query primitives for feature selection, discretization, pattern mining, clustering, instance-based learning and rule induction. A prototype system processing such queries was implemented as part of the SINDBAD (structured inductive database development) project. Key concepts of this system, among others, are the closure of operators and distances between objects. To support the analysis of multi-relational data, we incorporated multi-relational distance measures based on set distances and recursive descent. The inclusion of rule-based classification models made it necessary to extend the data model and the software architecture significantly. The prototype is applied to three different applications: gene expression analysis, gene regulation prediction and structure-activity relationships (SARs) of small molecules.

One of the goals of medical research in the area of dementia is to correlate images of the brain with other variables, for instance, demographic information or outcomes of clinical tests. The usual approach is to select a subset of patients based on such variables and analyze the images associated with those patients. In this paper, we apply data mining techniques to take the opposite approach: We start with the images and explain the differences and commonalities in terms of the other variables. In the first step, we cluster PET scans of patients to form groups sharing similar features in brain metabolism. To the best of our knowledge, it is the first time ever that clustering is applied to whole PET scans. In the second step, we explain the clusters by relating them to non-image variables. To do so, we employ RSD, an algorithm for relational subgroup discovery, with the cluster membership of patients as target variable. Our results enable interesting interpretations of differences in brain metabolism in terms of demographic and clinical variables. The approach was implemented and tested on an exceptionally large pre-existing data collection of patients with different types of dementia. It comprises 10 GB of image data from 454 PET scans, and 42 variables from psychological and demographical data organized in 11 relations of a relational database. We believe that explaining medical images in terms of other variables (patient records, demographic information, etc.) is a challenging new and rewarding area for data mining research.

MOTIVATION: The University of Minnesota Pathway Prediction System (UM-PPS) is a rule-based expert system to predict plausible biodegradation pathways for organic compounds. However, iterative application of these rules to generate biodegradation pathways leads to combinatorial explosion. We use data from known biotransformation pathways to rationally determine biotransformation priorities (relative reasoning rules) to limit this explosion. RESULTS: A total of 112 relative reasoning rules were identified and implemented. In one prediction step, i.e. as per one generation predicted, the use of relative reasoning decreases the predicted biotransformations by over 25% for 50 compounds used to generate the rules and by about 15% for an external validation set of 47 xenobiotics, including pesticides, biocides and pharmaceuticals. The percentage of correctly predicted, experimentally known products remains at 75% when relative reasoning is used. The set of relative reasoning rules identified, therefore, effectively reduces the number of predicted transformation products without compromising the quality of the predictions. AVAILABILITY: The UM-PPS server is freely available on the web to all users at the time of submission of this manuscript and will be available following publication at http://umbbd.msi.umn.edu/predict/. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

We show how chemical background knowledge can he used to improve the prediction performance in structure-activitity relationships (SARs) for non-congeneric compounds. The goal of the study is to build a model of growth-inhibition for the NCI DTP human tumor cell line screening data. The SAR model is based on frequent molecular fragments generated from the structure data. Background knowledge in the form of standard anti-cancer agents (ACAs) grouped by known mechanisms of action is available and used twice: First, the standard agents are treated separately in the fragment generation process. Second, we represent each molecule in terms of the similarities with structures known to be associated with certain mechanisms of action. In experiments, we show that using chemical background knowledge in this way reduces the mean absolute error (MAE) by about 5% compared to initial experiments, and by 9% compared to a previous publication. We conjecture that specific instances and groups of instances are a commonly occurring type of background knowledge that is particularly easy to use and effective in practice

We present a new, statistical approach to rule learning. Doing so, we address two of the problems inherent in traditional rule learning: The computational hardness of finding rule sets with low training error and the need for capacity control to avoid over-fitting. The chosen representation involves weights attached to rules. Instead of optimizing the error rate directly, we optimize for rule sets that have large margin and low variance. This can be formulated as a convex optimization problem allowing for efficient computation. Given the representation and the optimization procedure, we effectively yield weighted clauses in a CNF-like representation. To avoid overfitting, we propose a model selection strategy that utilizes a novel concentration inequality. Empirical tests show that the system is competitive with existing rule learning algorithms and that its flexible learning bias can be adjusted to improve predictive accuracy considerably.

MOTIVATION: A new representation for protein secondary structure prediction based on frequent amino acid patterns is described and evaluated. We discuss in detail how to identify frequent patterns in a protein sequence database using a level-wise search technique, how to define a set of features from those patterns and how to use those features in the prediction of the secondary structure of a protein sequence using support vector machines (SVMs). RESULTS: Three different sets of features based on frequent patterns are evaluated in a blind testing setup using 150 targets from the EVA contest and compared to predictions of PSI-PRED, PHD and PROFsec. Despite being trained on only 940 proteins, a simple SVM classifier based on this new representation yields results comparable to PSI-PRED and PROFsec. Finally, we show that the method contributes significant information to consensus predictions. AVAILABILITY: The method is available from the authors upon request.

We present a method to mine strings that are frequent in one database and infrequent in another. The method uses suffix- and lcp-arrays that can be computed extremely fast and space efficiently, and further exhibit a good locality behavior. Experiments with several biologically relevant data sets show that our approach outperforms existing methods in terms of time and space.

We tackle the problem of finding association rules for quantitative data. Whereas most of the previous approaches operate on hyper rectangles, we propose a representation based on half-spaces. Consequently, the left-hand side and right-hand side of an association rule does not contain a conjunction of items or intervals, but a weighted sum of variables tested against a threshold. Since the downward closure property does not hold for such rules, we propose an optimization setting for finding locally optimal rules. A simple gradient descent algorithm optimizes a parameterized score function, where iterations optimizing the first separating hyperplane alternate with iterations optimizing the second. Experiments with two real-world data sets show that the approach finds non-random patterns and scales up well. We therefore propose quantitative association rules based on half-spaces as an interesting new class of patterns with a high potential for applications.

Nested dichotomies are a standard statistical technique for tackling certain polytomous classification problems with logistic regression. They can be represented as binary trees that recursively split a multi-class clas-sification task into a system of dichotomies and provide a statistically sound way of applying two-class learning algorithms to multi-class prob-lems (assuming these algorithms generate class probability estimates). However, there are usually many candidate trees for a given problem and in the standard approach the choice of a particular tree is based on do-main knowledge that may not be available in practice. An alternative is to treat every system of nested dichotomies as equally likely and to form an ensemble classifier based on this assumption. We show that this approach produces more accurate classifications than applying C4.5 and logistic regression directly to multi-class problems. Our results also show that ensembles of nested dichotomies produce more accurate classifiers than pairwise classification if both techniques are used with C4.5, and compa-rable results for logistic regression. Compared to error-correcting output codes, they are preferable if logistic regression is used, and comparable in the case of C4.5. An additional benefit is that they generate class proba-bility estimates. Consequently they appear to be a good general-purpose method for applying binary classifiers to multi-class problems. 1

While there is a lot of empirical evidence showing that traditional rule learning approaches work well in practice, it is nearly impossible to derive analytical results about their predictive accuracy. In this paper, we investigate rule-learning from a theoretical perspective. We show that the application of McAllester's PAC-Bayesian bound to rule learning yields a practical learning algorithm, which is based on ensembles of weighted rule sets. Experiments with the resulting learning algorithm show not only that it is competitive with state-of-the-art rule learners, but also that its error rate can often be bounded tightly. In fact, the bound turns out to be tighter than one of the "best" bounds for a practical learning scheme known so far (the Set Covering Machine). Finally, we prove that the bound can be further improved by allowing the learner to abstain from uncertain predictions.

Software systems and in particular also knowledge-based systems (KBS) become increasingly large and complex. In response to this challenge, software engineering has a long tradition of advocating modularity. This has also heavily influenced object-oriented development. For measuring certain important aspects of modularity, coupling and cohesion metrics have been developed. Metrics have also attracted considerable attention for object-oriented development. For KBS development, however, no such metrics are available yet. This article presents the core of the first metrics suite for KBS development, its coupling and cohesion metrics. These metrics measure modularity in terms of the relations induced between slots of frames through their common references in rules. We show the soundness of these metrics according to theory and report on their usefulness in practice. As a consequence, we propose using our metrics in order to improve KBS development, and developing other important metrics and assessing their theoretical soundness along these lines.

Abstract Motivation: The Predictive Toxicology Challenge (PTC) was initiated to stimulate the development of advanced techniques for predictive toxicology models. The goal of this challenge was to compare different approaches for the prediction of rodent carcinogenicity, based on the experimental results of the US National Toxicology Program (NTP). Results: 111 sets of predictions for 185 compounds have been evaluated on quantitative and qualitative scales to select the most predictive models and those with the highest toxicological relevance. The accuracy of the submitted predictions was between 25 and 79 %. An evaluation of the most accurate models by toxicological experts showed, that it is still hard for domain experts to interpret the submitted models and to put them into relation with toxicological knowledge. Availability: PTC details and data can be found at: http://www.predictive-toxicology.org/ptc/ Contact: [email protected] * To whom correspondence should be addressed. † Present address: Institute for Computer Science, Technical University Munich, D-85748, Garching, Germany.

MOTIVATION: The development of in silico models to predict chemical carcinogenesis from molecular structure would help greatly to prevent environmentally caused cancers. The Predictive Toxicology Challenge (PTC) competition was organized to test the state-of-the-art in applying machine learning to form such predictive models. RESULTS: Fourteen machine learning groups generated 111 models. The use of Receiver Operating Characteristic (ROC) space allowed the models to be uniformly compared regardless of the error cost function. We developed a statistical method to test if a model performs significantly better than random in ROC space. Using this test as criteria five models performed better than random guessing at a significance level p of 0.05 (not corrected for multiple testing). Statistically the best predictor was the Viniti model for female mice, with p value below 0.002. The toxicologically most interesting models were Leuven2 for male mice, and Kwansei for female rats. These models performed well in the statistical analysis and they are in the middle of ROC space, i.e. distant from extreme cost assumptions. These predictive models were also independently judged by domain experts to be among the three most interesting, and are believed to include a small but significant amount of empirically learned toxicological knowledge. AVAILABILITY: PTC details and data can be found at: http://www.predictive-toxicology.org/ptc/.

We present the application of Feature Mining techniques to the Developmental Therapeutics Program's AIDS antiviral screen database. The database consists of 43576 compounds, which were measured for their capability to protect human cells from HIV-1 infection. According to these measurements, the compounds were classified as either active, moderately active or inactive. The distribution of classes is extremely skewed: Only 1.3 % of the molecules is known to be active, and 2.7 % is known to be moderately active. Given this database, we were interested in molecular substructures (i.e., features) that are frequent in the active molecules, and infrequent in the inactives. In data mining terms, we focused on features with a minimum support in active compounds and a maximum support in inactive compounds. We analyzed the database using the levelwise version space algorithm that forms the basis of the inductive query and database system MOLFEA (Molecular Feature Miner). Within this framework, it is possible to declaratively specify the features of interest, such as the frequency of features on (possibly different) datasets as well as on the generality and syntax of them. Assuming that the detected substructures are causally related to biochemical mechanisms, it should be possible to facilitate the development of new pharmaceuticals with improved activities.

Abstract Summary: We initiated the Predictive Toxicology Challenge (PTC) to stimulate the development of advanced SAR techniques for predictive toxicology models. The goal of this challenge is to predict the rodent carcinogenicity of new compounds based on the experimental results of the US National Toxicology Program (NTP). Submissions will be evaluated on quantitative and qualitative scales to select the most predictive models and those with the highest toxicological relevance. Availability: http://www.informatik.uni-freiburg.de/~ml/ptc/ Contact: [email protected] * To whom correspondence should be addressed.