State-of-the-art rule mining algorithms rely on summarizing the training set into efficient data structures which allow to quickly answer arbitrary conjunctive queries about the data. The key limitation of such techniques is their memory consumption. Pre-post code trees (PPC-trees) which are the basis of several efficient association and classification rule mining algorithms, are only constructed as an intermediate representation and subsequently converted into a much more efficient N-lists structure. In this paper, we introduce partial pre-post code trees (P3C-trees), which are based on the idea that partial trees are iteratively constructed, and immediately converted into N-lists. This tight integration of these phases allows to avoid the memory bottleneck of a full PPC-tree construction, and thus enables these algorithms to tackle the memory scalability problem posed by large-scale datasets. Our experiments with big datasets confirm that the memory used by P3C-tree is orders of magnitude smaller than the memory consumed by PPC-tree, and the generated N-lists are also more effective than alternative structures such as Tidset or Diffset. Moreover, the N-list construction can also be considerably sped up with the P3C-tree structure.

Abstract A scoring system is a simple decision model that checks a set of features, adds a certain number of points to a total score for each feature that is satisfied, and finally makes a decision by comparing the total score to a threshold. Scoring systems have a long history of active use in safety-critical domains such as healthcare and justice, where they provide guidance for making objective and accurate decisions. Given their genuine interpretability, the idea of learning scoring systems from data is obviously appealing from the perspective of explainable AI. In this paper, we propose a practically motivated extension of scoring systems called probabilistic scoring lists (PSL), as well as a method for learning PSLs from data. Instead of making a deterministic decision, a PSL represents uncertainty in the form of probability distributions, or, more generally, probability intervals. Moreover, in the spirit of decision lists, a PSL evaluates features one by one and stops as soon as a decision can be made with enough confidence. To evaluate our approach, we conduct case studies in the medical domain and on standard benchmark data.

A defining feature of collectable card games is the deck building process prior to actual gameplay, in which players form their decks according to some restrictions. Learning to build decks is difficult for players and models alike due to the large card variety and highly complex semantics, as well as requiring meaningful card and deck representations when aiming to utilise AI. In addition, regular releases of new card sets lead to unforeseeable fluctuations in the available card pool, thus affecting possible deck configurations and requiring continuous updates. Previous Game AI approaches to building decks have often been limited to fixed sets of possible cards, which greatly limits their utility in practice. In this work, we explore possible card representations that generalise to unseen cards, thus greatly extending the real-world utility of AI-based deck building for the game “Magic: The Gathering”. We study such representations based on numerical, nominal, and text-based features of cards, card images, and meta information about card usage from third-party services. Our results show that while the particular choice of generalised input representation has little effect on learning to predict human card selections among known cards, the performance on new, unseen cards can be greatly improved. Our generalised model is able to predict $55 \%$ of human choices on completely unseen cards, thus showing a deep understanding of card quality and strategy.

Abstract The growing number of applications of machine learning and data mining in many domains—from agriculture to business, education, industrial manufacturing, and medicine—gave rise to new requirements for how to inspect and control the learned models. The research domain of explainable artificial intelligence (XAI) has been newly established with a strong focus on methods being applied post-hoc on black-box models. As an alternative, the use of interpretable machine learning methods has been considered—where the learned models are white-box ones. Black-box models can be characterized as representing implicit knowledge—typically resulting from statistical and neural approaches of machine learning, while white-box models are explicit representations of knowledge—typically resulting from rule-learning approaches. In this introduction to the special issue on ‘Explainable and Interpretable Machine Learning and Data Mining’ we propose to bring together both perspectives, pointing out commonalities and discussing possibilities to integrate them.

In this paper, we formalize the problem of learning coherent collections of decision models, which we call decision catalogues, and illustrate it for the case where models are scoring systems. This problem is motivated by the recent rise of algorithmic decision-making and the idea to improve human decision-making through machine learning, in conjunction with the observation that decision models should be situated in terms of their complexity and resource requirements: Instead of constructing a single decision model and using this model in all cases, different models might be appropriate depending on the decision context. Decision catalogues are supposed to support a seamless transition from very simple, resource-efficient to more sophisticated but also more demanding models. We present a general algorithmic framework for inducing such catalogues from training data, which tackles the learning task as a problem of searching the space of candidate catalogues systematically and, to this end, makes use of heuristic search methods. We also present a concrete instantiation of this framework as well as empirical studies for performance evaluation, which, in a nutshell, show that greedy search is an efficient and hard-to-beat strategy for the construction of catalogues of scoring systems.

In imperfect information games, the game state is generally not fully observable to players. Therefore, good gameplay requires policies that deal with the different information that is hidden from each player. To combat this, effective algorithms often reason about information sets; the sets of all possible game states that are consistent with a player's observations. While there is no way to distinguish between the states within an information set, this property does not imply that all states are equally likely to occur in play. We extend previous research on assigning weights to the states in an information set in order to facilitate better gameplay in the imperfect information game of Reconnaissance Blind Chess. For this, we train two different neural networks which estimate the likelihood of each state in an information set from historical game data. Experimentally, we find that a Siamese neural network is able to achieve higher accuracy and is more efficient than a classical convolutional neural network for the given domain. Finally, we evaluate an RBC-playing agent that is based on the generated weightings and compare different parameter settings that influence how strongly it should rely on them. The resulting best player is ranked 5thon the public leaderboard.

Research in Game Artificial Intelligence distinguishes between fully observable, perfect-information games and imperfect-information games, which hide part of the game’s full information. In games with imperfect information, all possible game states that are consistent with a player’s currently available information about the progress of the game are called the information set for that player. This information set can be used for multiple purposes such as determining the expected outcome of a certain move by evaluating it on all possible states in the information set. While in theory there is no way to distinguish states within an information set, players can use experience and other context information to estimate which states are the most likely. In this paper, we estimate a probability distribution over an information set from historic data such that we can assign a weight to each individual state. We achieve this by training a Siamese neural network with triplets of comparisons between different states in the information set given the context of the previously obtained information. A first evaluation in the game of Reconnaissance Blind Chess shows that we can learn to identify the one true game state in a large information set with high probability. In addition, when used within a naively constructed RBC agent, this approach shows promising gameplay performance. At the time of writing, a simple agent based on the Siamese neural network is ranked #6 of all agents on the public RBC leaderboard.

Abstract Classifier chains are an effective technique for modeling label dependencies in multi-label classification. However, the method requires a fixed, static order of the labels. While in theory, any order is sufficient, in practice, this order has a substantial impact on the quality of the final prediction. Dynamic classifier chains denote the idea that for each instance to classify, the order in which the labels are predicted is dynamically chosen. The complexity of a naïve implementation of such an approach is prohibitive, because it would require to train a sequence of classifiers for every possible permutation of the labels. To tackle this problem efficiently, we propose a new approach based on random decision trees which can dynamically select the label ordering for each prediction. We show empirically that a dynamic selection of the next label improves over the use of a static ordering under an otherwise unchanged random decision tree model. In addition, we also demonstrate an alternative approach based on extreme gradient boosted trees, which allows for a more target-oriented training of dynamic classifier chains. Our results show that this variant outperforms random decision trees and other tree-based multi-label classification methods. More importantly, the dynamic selection strategy allows to considerably speed up training and prediction.

Abstract Conventional rule learning algorithms aim at finding a set of simple rules, where each rule covers as many examples as possible. In this paper, we argue that the rules found in this way may not be the optimal explanations for each of the examples they cover. Instead, we propose an efficient algorithm that aims at finding the best rule covering each training example in a greedy optimization consisting of one specialization and one generalization loop. These locally optimal rules are collected and then filtered for a final rule set, which is much larger than the sets learned by conventional rule learning algorithms. A new example is classified by selecting the best among the rules that cover this example. In our experiments on small to very large datasets, the approach’s average classification accuracy is higher than that of state-of-the-art rule learning algorithms. Moreover, the algorithm is highly efficient and can inherently be processed in parallel without affecting the learned rule set and so the classification accuracy. We thus believe that it closes an important gap for large-scale classification rule induction.

In this work, we adapt a training approach inspired by the original AlphaGo system to play the imperfect information game of Reconnaissance Blind Chess. Using only the observations instead of a full description of the game state, we first train a supervised agent on publicly available game records. Next, we increase the performance of the agent through self-play with the on-policy reinforcement learning algorithm Proximal Policy optimization. We do not use any search to avoid problems caused by the partial observability of game states and only use the policy network to generate moves when playing. With this approach, we achieve an ELO of 1330 on the RBC leaderboard, which places our agent at position 27 at the time of this writing. We see that self-play significantly improves performance and that the agent plays acceptably well without search and without making assumptions about the true game state.

Abstract The idea to exploit label dependencies for better prediction is at the core of methods for multi-label classification (MLC), and performance improvements are normally explained in this way. Surprisingly, however, there is no established methodology that allows to analyze the dependence-awareness of MLC algorithms. With that goal in mind, we introduce a class of loss functions that are able to capture the important aspect of label dependence. To this end, we leverage the mathematical framework of non-additive measures and integrals. Roughly speaking, a non-additive measure allows for modeling the importance of correct predictions of label subsets (instead of single labels), and thereby their impact on the overall evaluation, in a flexible way. The well-known Hamming and subset 0/1 losses are rather extreme special cases of this function class, which give full importance to single label sets or the entire label set, respectively. We present concrete instantiations of this class, which appear to be especially appealing from a modeling perspective. The assessment of multi-label classifiers in terms of these losses is illustrated in an empirical study, clearly showing their aptness at capturing label dependencies. Finally, while not being the main goal of this study, we also show some preliminary results on the minimization of this parametrized family of losses.

Drafting, i.e., the iterative, adversarial selection of a subset of items from a larger candidate set, is a key element of many games and related problems. It encompasses team formation in sports or e-sports, as well as deck selection in formats of many modern card games. The key difficulty of drafting is that it is typically not sufficient to simply evaluate each item in a vacuum and to select the best items. The evaluation of an item depends on the context of the set of items that were already selected earlier, as the value of a set is not just the sum of the values of its members - it must include a notion of how well items go together. In this paper, we study drafting in the context of the card game Magic: The Gathering. We propose the use of the Contextual Preference Ranking framework, which learns to compare two possible extensions of a given deck of cards. We demonstrate that the resulting neural network is better able to better inform decisions in this game than previous attempts.

State-of-the-art game playing programs do not provide an explanation for their move choice beyond a numerical score for the best and alternative moves. However, human players want to understand the reasons why a certain move is considered to be the best. Saliency maps are a useful general technique for this purpose, because they allow visualizing relevant aspects of a given input to the produced output. While such saliency maps are commonly used in the field of image classification, their adaptation to chess engines like Stockfish or Leela has not yet seen much work. This paper takes one such approach, Specific and Relevant Feature Attribution (SARFA), which has previously been proposed for a variety of game settings, and analyzes it specifically for the game of chess. In particular, we investigate differences with respect to its use with different chess engines, to different types of positions (tactical vs. positional as well as middle-game vs. endgame), and point out some of the approach's down-sides. Ultimately, we also suggest and evaluate a few improvements of the basic algorithm that are able to address some of the found shortcomings.

While the interpretability of machine learning models is often equated with their mere syntactic comprehensibility, we think that interpretability goes beyond that, and that human interpretability should also be investigated from the point of view of cognitive science. The goal of this paper is to discuss to what extent cognitive biases may affect human understanding of interpretable machine learning models, in particular of logical rules discovered from data. Twenty cognitive biases are covered, as are possible debiasing techniques that can be adopted by designers of machine learning algorithms and software. Our review transfers results obtained in cognitive psychology to the domain of machine learning, aiming to bridge the current gap between these two areas. It needs to be followed by empirical studies specifically focused on the machine learning domain.

Many machine learning problems require to learn to permute a set of objects. Notable applications include ranking or sorting. One of the difficulties of learning in such a combinatorial space is the definition of meaningful and differentiable distances and loss functions. Lehmer codes are an elegant way for mapping permutations into a vector space where the Euclidean distance between two codes corresponds to the Kendall tau distance between the corresponding rankings. This transformation, therefore, allows the use of a surrogate loss converting the original permutation learning problem into a surrogate prediction problem which is easier to optimize. To that end, learning to predict Lehmer codes allows a transformation of the inference problem from permutations matrices to row-stochastic matrices, thereby removing the constraints of row and columns to sum to one. This permits a straight-forward optimization of the permutation prediction problem. We demonstrate the effectiveness of this approach for object ranking problems by providing empirical results and comparing it to competitive baselines on different tasks.

Abstract It is conventional wisdom in machine learning and data mining that logical models such as rule sets are more interpretable than other models, and that among such rule-based models, simpler models are more interpretable than more complex ones. In this position paper, we question this latter assumption by focusing on one particular aspect of interpretability, namely the plausibility of models. Roughly speaking, we equate the plausibility of a model with the likeliness that a user accepts it as an explanation for a prediction. In particular, we argue that—all other things being equal—longer explanations may be more convincing than shorter ones, and that the predominant bias for shorter models, which is typically necessary for learning powerful discriminative models, may not be suitable when it comes to user acceptance of the learned models. To that end, we first recapitulate evidence for and against this postulate, and then report the results of an evaluation in a crowdsourcing study based on about 3000 judgments. The results do not reveal a strong preference for simple rules, whereas we can observe a weak preference for longer rules in some domains. We then relate these results to well-known cognitive biases such as the conjunction fallacy, the representative heuristic, or the recognition heuristic, and investigate their relation to rule length and plausibility.

In this paper, we present a simple and cheap ordinal bucketing algorithm that approximately generates q-quantiles from an incremental data stream. The bucketing is done dynamically in the sense that the amount of buckets q increases with the number of seen samples. We show how this can be used in Ordinal Monte Carlo Tree Search (OMCTS) to yield better bounds on time and space complexity, especially in the presence of noisy rewards. Besides complexity analysis and quality tests of quantiles, we evaluate our method using OMCTS in the General Video Game Framework (GVGAI). Our results demonstrate its dominance over vanilla Monte Carlo Tree Search in the presence of noise, where OMCTS without bucketing has a very bad time and space complexity.

Answer selection aims at identifying the correct answer for a given question from a set of potentially correct answers.Contrary to previous works, which typically focus on the semantic similarity between a question and its answer, our hypothesis is that question-answer pairs are often in analogical relation to each other.Using analogical inference as our use case, we propose a framework and a neural network architecture for learning dedicated sentence embeddings that preserve analogical properties in the semantic space.We evaluate the proposed method on benchmark datasets for answer selection and demonstrate that our sentence embeddings indeed capture analogical properties better than conventional embeddings, and that analogy-based question answering outperforms a comparable similaritybased technique.

A key problem in multi-label classification is to utilize dependencies among the labels. Chaining classifiers are a simple technique for addressing this problem but current algorithms all assume a fixed, static label ordering. In this work, we propose a multi-label classification approach which allows to choose a dynamic, context-dependent label ordering. Our proposed approach consists of two sub-components: a simple EM-like algorithm which bootstraps the learned model, and a more elaborate approach based on reinforcement learning. Our experiments on three public multi-label classification benchmarks show that our proposed dynamic label ordering approach based on reinforcement learning outperforms recurrent neural networks with fixed label ordering across both bipartition and ranking measures on all the three datasets. As a result, we obtain a powerful sequence prediction-based algorithm for multi-label classification, which is able to efficiently and explicitly exploit label dependencies.

In times of abundant streams of data, the only constant we can rely on is change itself. Given an existing classification model, it might be impractical or impossible to retrain when concept drift impairs the performance. In this paper, we propose an ensemble learning approach that fixes errors of a given model via patches: smaller, local models that are applied when the base model is likely to fail. These patches are added to the ensemble when the base learner shows decreased performance for one or multiple classes, which we discover by applying explicit drift detection. Each patch covers the drift of a subset of the classes. Via the drift detection method, the misclassification behavior of the base learner can be matched to an existing patch. This reduces the total amount of patches to the number of seen concept drifts, which is an advantage in the long run. Patches can be added to the ensemble and refined incrementally. The ensemble decision is conducted by a sequential classifier, which allows a high number of ensemble members that can be added incrementally. Experimental results show that ensemble patching performs well w.r.t. accuracy and adaptation speed.

In this work we present neural network patching, an approach for adapting deep neural network models to nonstationary environments. Instead of creating or updating a network to accommodate concept drift, neural network patching leverages the inner layers of a previously trained network as well as its output to learn a patch that enhances the classification. It learns (i) a predictor that estimates whether the original network will misclassify an instance, and (ii) a patching network that fixes the misclassification. Neural network patching is based on the idea that the original network can still classify a majority of instances well, and that the inner feature representations encoded in the deep network aid the classifier to cope with unseen or changed inputs. We evaluated this technique on several datasets, comparing it to similar methods. Our finding is that neural network patching is adapting quickly to concept shifts, while also maintaining long-term learning capabilities similar to more complex methods that update the whole network.

Recently, the problem of driver classification has received considerable attention in the literature. Most approaches formulate this problem as a classification task, in which the drivers are the classes. The number of classes is thus fixed in the training and test set. By this formulation, a model that is trained to classify two drivers D1and D2can not be used to classify other drivers (e.g, D3and D4). In this paper, we formulate the problem of driver identification as a comparison problem, in which a model should learn to extract individual characteristics of drivers and use them as a basis for the comparison. To tackle this problem, we propose an approach using a Siamese network architecture in combination with Long Short-Term Memory (LSTM) for mapping maneuver execution into a lower-dimensional space. The network is trained in such a way that it maps maneuver executions of the same driver into similar vectors in the embedding space and maneuver executions from different drivers to dissimilar vectors in this space. Our approach shows various advantages over the classification-based setting, most notably that it can be used to identify drivers that are not in the training set. Furthermore, the distance between embedding vectors of different drivers can be used as a scalar for measuring the similarity of their driving styles. In addition, since the network only uses a single maneuver pair at a time for producing the prediction, we show that the identification performance theoretically and empirically increases along with the number of seen maneuvers. Finally, the embedding vector can be used as feature to represent the driver or to personalize the assistance systems.

In this work we present classifier patching, an approach for adapting an existing black-box classification model to new data. Instead of creating a new model, patching infers regions in the instance space where the existing model is error-prone by training a classifier on the previously misclassified data. It then learns a specific model to determine the error regions, which allows to patch the old model’s predictions for them. Patching relies on a strong, albeit unchangeable, existing base classifier, and the idea that the true labels of seen instances will be available in batches at some point in time after the original classification. We experimentally evaluate our approach, and show that it meets the original design goals. Moreover, we compare our approach to existing methods from the domain of ensemble stream classification in both concept drift and transfer learning situations. Patching adapts quickly and achieves high classification accuracy, outperforming state-of-the-art competitors in either adaptation speed or accuracy in many scenarios.

In predictive maintenance, one may face a scenario where a series of anomalous events is indicative of an impending fault. While each of them by itself would not be sufficient for setting off an alarm, their collective occurrence is. However, supervised training of recognizers for these anomalous events is difficult. The number of occurrences of such faults is generally low, and the derived labels are unreliable because they apply to the entire sequence-a so-called mission-and not the individual events. In this paper, we propose an approach for tackling such problems via unsupervised training of autoencoders on data of normal events. Individual anomalies are recognized via the reconstruction error. Missions are then classified via a threshold-based approach on the ensemble of anomaly ratios. Our method handles artificially generated data well and is robust against noisy data. Its main advantage is a low level of supervision, since all the parameters can be extracted experimentally with little knowledge about the ground truth in the data.

Markus Zopf, Eneldo Loza Mencía, Johannes Fürnkranz. Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers). 2018.

In this paper, we introduce a universal game playing agent that is able to successfully play a wide variety of video games. It combines the strengths of Monte Carlo tree search with conventional heuristic search into a single hybrid search agent, which is able to select the appropriate strategy based on its observations about the game dynamics. In particular, the agent learns a knowledge base which provides the agent with information such as an approximate transition function, the type of agents and objects that participate in the game and the possible effects of interacting with them, heuristics for focusing and pruning the search, and more. This hybrid strategy proved to be successful in the 2015 General Video Game Competition, in which our agent emerged as the clear winner.

Multi-label classification is the task of predicting a set of labels for a given input instance. Classifier chains are a state-of-the-art method for tackling such problems, which essentially converts this problem into a sequential prediction problem, where the labels are first ordered in an arbitrary fashion, and the task is to predict a sequence of binary values for these labels. In this paper, we replace classifier chains with recurrent neural networks, a sequence-to-sequence prediction algorithm which has recently been successfully applied to sequential prediction tasks in many domains. The key advantage of this approach is that it allows to focus on the prediction of the positive labels only, a much smaller set than the full set of possible labels. Moreover, parameter sharing across all classifiers allows to better exploit information of previous decisions. As both, classifier chains and recurrent neural networks depend on a fixed ordering of the labels, which is typically not part of a multi-label problem specification, we also compare different ways of ordering the label set, and give some recommendations on suitable ordering strategies.

Reinforcement learning (RL) techniques optimize the accumulated long-term reward of a suitably chosen reward function. However, designing such a reward function often requires a lot of task- specific prior knowledge. The designer needs to consider different objectives that do not only influence the learned behavior but also the learning progress. To alleviate these issues, preference-based reinforcement learning algorithms (PbRL) have been proposed that can directly learn from an expert's preferences instead of a hand-designed numeric reward. PbRL has gained traction in recent years due to its ability to resolve the reward shaping problem, its ability to learn from non numeric rewards and the possibility to reduce the dependence on expert knowledge. We provide a unified framework for PbRL that describes the task formally and points out the different design principles that affect the evaluation task for the human as well as the computational complexity. The design principles include the type of feedback that is assumed, the representation that is learned to capture the preferences, the optimization problem that has to be solved as well as how the exploration/exploitation problem is tackled. Furthermore, we point out shortcomings of current algorithms, propose open research questions and briefly survey practical tasks that have been solved using PbRL.

Conventional multi-label classification algorithms treat the target labels of the classification task as mere symbols that are void of an inherent semantics. However, in many cases textual descriptions of these labels are available or can be easily constructed from public document sources such as Wikipedia. In this paper, we investigate an approach for embedding documents and labels into a joint space while sharing word representations between documents and labels. For finding such embeddings, we rely on the text of documents as well as descriptions for the labels. The use of such label descriptions not only lets us expect an increased performance on conventional multi-label text classification tasks, but can also be used to make predictions for labels that have not been seen during the training phase. The potential of our method is demonstrated on the multi-label classification task of assigning keywords from the Medical Subject Headings (MeSH) to publications in biomedical research, both in a conventional and in a zero-shot learning setting.

Specifying a numeric reward function for reinforcement learning typically requires a lot of hand-tuning from a human expert. In contrast, preference-based reinforcement learning (PBRL) utilizes only pairwise comparisons between trajectories as a feedback signal, which are often more intuitive to specify. Currently available approaches to PBRL for control problems with continuous state/action spaces require a known or estimated model, which is often not available and hard to learn. In this paper, we integrate preference-based estimation of the reward function into a model-free reinforcement learning (RL) algorithm, resulting in a model-free PBRL algorithm. Our new algorithm is based on Relative Entropy Policy Search (REPS), enabling us to utilize stochastic policies and to directly control the greediness of the policy update. REPS decreases exploration of the policy slowly by limiting the relative entropy of the policy update, which ensures that the algorithm is provided with a versatile set of trajectories, and consequently with informative preferences. The preference-based estimation is computed using a sample-based Bayesian method, which can also estimate the uncertainty of the utility. Additionally, we also compare to a linear solvable approximation, based on inverse RL. We show that both approaches perform favourably to the current state-of-the-art. The overall result is an algorithm that can learn non-parametric continuous action policies from a small number of preferences.

Traditional machine translation systems often require heavy feature engineering and the combination of multiple techniques for solving different subproblems. In recent years, several end-to-end learning architectures based on recurrent neural networks have been proposed. Unlike traditional systems, Neural Machine Translation (NMT) systems learn the parameters of the model and require only minimal preprocessing. Memory and time constraints allow to take only a fixed number of words into account, which leads to the out-of-vocabulary (OOV) problem. In this work, we analyze why the OOV problem arises and why it is considered a serious problem in German. We study the effectiveness of compound word splitters for alleviating the OOV problem, resulting in a 2.5+ BLEU points improvement over a baseline on the WMT’14 German-to-English translation task. For English-to-German translation, we use target-side compound splitting through a special syntax during training that allows the model to merge compound words and gain 0.2 BLEU points.

Unexpected events such as accidents, natural disasters and terrorist attacks represent an information situation where it is crucial to give users access to important and non-redundant information as early as possible. Incremental update summarization (IUS) aims at summarizing events which develop over time. In this paper, we propose a combination of sequential clustering and contextual importance measures to identify important sentences in a stream of documents in a timely manner. Sequential clustering is used to cluster similar sentences. The created clusters are scored by a contextual importance measure which identifies important information as well as redundant information. Experiments on the TREC Temporal Summarization 2015 shared task dataset show that our system achieves superior results compared to the best participating systems.

Most automatic text summarization systems proposed to date rely on centrality and structural features as indicators for information importance.In this paper, we argue that these features cannot reliably detect important information in heterogeneous document collections.Instead, we propose CPSum, a summarizer that learns the importance of information objects from a background source.Our hypothesis is tested on a multi-document corpus where we remove centrality and structural features.CPSum proves to be able to perform well in this challenging scenario whereas reference systems fail.

You hold in your hands the first issue of Data Mining and Knowledge Discovery in 10 years that does not bear the name of Geoffrey Webb as its editor-in-chief on the cover.It is a great honor but a much greater challenge for me to try to fill his shoes.And those are really big shoes to fill.As the editor-in-chief of this journal, Geoff has brought an enormous commitment and dedication to his role.His primary concern has always been the authors of the submitted papers, who should receive fast feedback of the highest quality, and, in case of acceptance, support for making the best out of their work.Most importantly, they should always be treated with the highest respect.As an editorial board member and action editor for this journal, I knew exactly that no review and no decision letter that I write will be unread by Geoff, and more than once he got back to me and pointed out shortcomings and improvements in my work for the journal.It is a daunting task to continue at this level, but I will do my best to live up to it.Thanks to his efforts, the journal is now in a healthy state.When Geoff took over in 2005, the journal published six issues in two volumes with a total of 22 papers on a bit more than 600 pages.In 2014, the journal has returned to publishing a single volume per year, but this volume consisted of four regular issues and a double special issue with a total of 48 papers on more than 1,600 pages.From 2005 onwards, the impact factor of the journal had continuously risen to its highest level of 2.95 in 2009.Since then, it has taken some ups and downs but essentially maintained its high level, which is the highest for journals that focus specifically on data mining.I am glad that Geoff will continue to serve on the Advisory Board of the journal.Where will the journal be heading in the next 10 years?One of the big challenges is open access publishing.

Most of the research in the area of evaluation function learning is focused on self-play. However in many domains, like Chess, expert feedback is amply available in the form of annotated games. This feedback usually comes in the form of qualitative information because human annotators find it hard to determine precise utility values for game states. The goal of this work is to investigate inasmuch it is possible to leverage this qualitative feedback for learning an evaluation function for the game. To this end, we show how the game annotations can be translated into preference statements over moves and game states, which in turn can be used for learning a utility function that respects these preference constraints. We evaluate the resulting function by creating multiple heuristics based upon different sized subsets of the training data and compare them in a tournament scenario. The results showed that learning from game annotations is possible, but, on the other hand, our learned functions did not quite reach the performance of the original, manually tuned function of the Chess program. The reason for this failure seems to lie in the fact that human annotators only annotate “interesting” positions, so that it is hard to learn basic information, such as material advantage from game annotations alone.

The task in multilabel classification is to predict for a given set of labels whether each individual label should be attached to an instance or not. Graded multilabel classification generalizes this setting by allowing to specify for each label a degree of membership on an ordinal scale. This setting can be frequently found in practice, for example when movies or books are assessed on a one-to-five star rating in multiple categories. In this paper, we propose to reformulate the problem in terms of preferences between the labels and their scales, which can then be tackled by learning from pair wise comparisons. We present three different approaches which make use of this decomposition and show on three datasets that we are able to outperform baseline approaches. In particular, we show that our solution, which is able to model pair wise preferences across multiple scales, outperforms a straight-forward approach which considers the problem as a set of independent ordinal regression tasks.

Reinforcement learning algorithms are usually hard to use for non expert users. It is required to consider several aspects like the definition of state-, action- and reward-space as well as the algorithms hyperparameters. Preference based approaches try to address these problems by omitting the requirement for exact rewards, replacing them with preferences over solutions. Some algorithms have been proposed within this framework, but they are usually requiring parameterized policies which is again a hinderance for their application. Monte Carlo based approaches do not have this restriction and are also model free. Hence, we present a new preference-based reinforcement learning algorithm, utilizing Monte Carlo estimates. The main idea is to estimate the relative Q-value of two actions for the same state within a every-visit framework. This means, preferences are used to estimate the Q-value of state-action pairs within a trajectory, based on the feedback concerning the complete trajectory. The algorithm is evaluated on three common benchmark problems, namely mountain car, inverted pendulum and acrobot, showing its advantage over a closely related algorithm which is also using estimates for intermediate states, but based on a probability theorem. In comparison to SARSA(λ), EPMC converges somewhat slower, but computes policies that are almost as good or better.

In this paper, we propose a novel approach for learning regression rules by transforming the regression problem into a classification problem. Unlike previous approaches to regression by classification, in our approach the discretization of the class variable is tightly integrated into the rule learning algorithm. The key idea is to dynamically define a region around the target value predicted by the rule, and considering all examples within that region as positive and all examples outside that region as negative. In this way, conventional rule learning heuristics may be used for inducing regression rules. Our results show that our heuristic algorithm outperforms approaches that use a static discretization of the target variable, and performs en par with other comparable rule-based approaches, albeit without reaching the performance of statistical approaches.

Overthelastdecade,localpatterndiscoveryhasbecomearapidlygrowingfield(Moriketal.2005),andarangeoftechniquesisavailableforproducingextensivecollectionsofpatterns.Becauseoftheexhaustivenatureofmostsuchtechniques,thepatterncol-lections provide a fairly complete picture of the information content of the database.However,suchso-calledlocalpatternsrepresentfragmentedknowledge,anditisoftennot clear how the pieces of the puzzle can be combined into a global model, which isoften the desirable result of a data mining process. Thus, the question of how to turnlarge collections of patterns into global models deserves attention.This special issue of the Data Mining and Knowledge Discovery Journal featuresa number of papers that represent the state of the art in building global models fromlocal patterns. In our view, a common ground of all the local pattern mining tech-niquesisthattheycanbeconsidered tobefeatureconstructiontechniques thatfollowdifferent objectives (or constraints). We will see that the redundancy of these patternsandtheselectionofsuitablesubsetsofpatternsareaddressedinseparatesteps,sothateach resulting feature is highly informative in the context of the global data miningproblem.In earlier work (Knobbe et al. 2008), a framework was proposed that provides ageneral outline of the activities involved. The framework, called From Local Patterns

Most commonly used inductive rule learning algorithms employ a hill-climbing search, whereas local pattern discovery algorithms employ exhaustive search. In this paper, we evaluate the spectrum of different search strategies to see whether separate-and-conquer rule learning algorithms are able to gain performance in terms of predictive accuracy or theory size by using more powerful search strategies like beam search or exhaustive search. Unlike previous results that demonstrated that rule learning algorithms suffer from over-searching, our work pays particular attention to the interaction between the search heuristic and the search strategy. Our results show that exhaustive search has primarily the effect of finding longer, but nevertheless more general rules than hill-climbing search. Thus, in cases where hillclimbing finds too specific rules, exhaustive search may help, while in others it may lead to over-generalization. 1

Multiclass multilabel perceptrons (MMP) have been proposed as an efficient incremental training algorithm for addressing a multilabel prediction task with a team of perceptrons. The key idea is to train one binary classifier per label, as is typically done for addressing multilabel problems, but to make the training signal dependent on the performance of the whole ensemble. In this paper, we propose an alternative technique that is based on a pairwise approach, i.e., we incrementally train a perceptron for each pair of classes. Our evaluation on four multilabel datasets shows that the multilabel pairwise perceptron (MLPP) algorithm yields substantial improvements over MMP in terms of ranking quality and overfitting resistance, while maintaining its efficiency. Despite the quadratic increase in the number of perceptrons that have to be trained, the increase in computational complexity is bounded by the average number of labels per training example.

The goal of this paper is to investigate to what extent a rule learning heuristic can be learned from experience. To that end, we let a rule learner learn a large number of rules and record their performance on the test set. Subsequently, we train regression algorithms on predicting the test set performance of a rule from its training set characteristics. We investigate several variations of this basic scenario, including the question whether it is better to predict the performance of the candidate rule itself or of the resulting final rule. Our experiments on a number of independent evaluation sets show that the learned heuristics outperform standard rule learning heuristics. We also analyze their behavior in coverage space.

We consider the problem of learning ranking functions in a supervised manner. A ranking function is a mapping from instances to rankings over a finite number of labels and can thus be seen as an extension of a classification function. Our learning method, referred to as ranking by pairwise comparison (RPC), is a two-step procedure. First, a valued preference structure is induced from given preference data, using a natural extension of so-called pairwise classification. A ranking is then derived from that preference structure by means of a simple scoring function. It is shown that, under some idealized assumptions, a prediction thus obtained is a risk minimizer if the distance resp. similarity between rankings is measured by the Spearman rank correlation. We conclude the paper by outlining a potential application of the method in (qualitative) fuzzy classification and identifying some extensions necessary in this context.

This paper presents an empirical study on the possibility of discovering interesting event sequences and sequential rules in a large database of international political events. A data mining algorithm first presented by Mannila and Toivonen (1996), has been implemented and extended, which is able to search for generalized episodes in such event databases. Experiments conducted with this algorithm on the Kansas Event Data System (KEDS) database, an event data set covering interactions between countries in the Persian Gulf region, are described. Some qualitative and quantitative results are reported, and experiences with strategies for reducing the problem complexity and focusing on the search on interesting subsets of events are described.

In this paper we re-investigate windowing for rule learning algorithms. We show that, contrary to previous results for decision tree learning, windowing can in fact achieve significant run-time gains in noise-free domains and explain the different behavior of rule learning algorithms by the fact that they learn each rule independently. The main contribution of this paper is integrative windowing, a new type of algorithm that further exploits this property by integrating good rules into the final theory right after they have been discovered. Thus it avoids re-learning these rules in subsequent iterations of the windowing process. Experimental evidence in a variety of noise-free domains shows that integrative windowing can in fact achieve substantial run-time gains. Furthermore, we discuss the problem of noise in windowing and present an algorithm that is able to achieve run-time gains in a set of experiments in a simple domain with artificial noise.