Search

Causal classification concerns the estimation of the net effect of a treatment on an outcome of interest at the instance level, i.e., of the individual treatment effect (ITE). For binary treatment and outcome variables, causal classification models produce ITE estimates that essentially allow one to rank instances from a large positive effect to a large negative effect. Often, as in uplift modeling (UM), one is merely interested in this ranking, rather than in the ITE estimates themselves. In this regard, we investigate the potential of learning to rank (L2R) techniques to learn a ranking of the instances directly. We propose a unified formalization of different binary causal classification performance measures from the UM literature and explore how these can be integrated into the L2R framework. Additionally, we introduce a new metric for UM with L2R called the promoted cumulative gain (PCG). We employ the L2R technique LambdaMART to optimize the ranking according to PCG and show improved results over the use of standard L2R metrics and equal to improved results when compared with state-of-the-art UM. Finally, we show how L2R techniques can be used to specifically optimize for the top-k fraction of the ranking in a UM context, however, these results do not generalize to the test set. ispartof: IEEE Transactions on Knowledge and Data Engineering vol:34 issue:10 pages:4888-4904 status: published

Probability of default estimation via machine learning on historical data is widely studied in credit risk modeling, where risk is estimated by the probability of an entire company or person to default on a loan. In this work, we investigated the use of machine learning for a finer-grained risk estimation task, namely spot factoring. Here, the goal is to estimate the likelihood that a single invoice will be paid in an acceptable timeframe. In this case, risk is more related to when the invoice was paid (if ever), compared to the contractual payment date, that is, the overdueness of an invoice. In order to express overdueness in a spot factoring context, we construct three new variables to predict. One such target variable directly shows the overdueness in terms of days overdue. A second, graded, target variable that we use stems from the way decision makers categorize invoices in risk groups that reflect increasingly later payment periods and more thorough collection efforts. We obtain a third and binary target variable by merging the two best and merging the three worst risk groups. This amounts to splitting the invoices between those that are paid within the first 25 days after their due day and those that are not. We investigate the suitability of three prediction tasks when using the new target variables: classical binary classification, regression of the days overdue and learning-to-rank methods that learn to optimize the risk-related ranking of all instances rather than predicting a value. We describe different ways of modeling these tasks and evaluate them on real-life spot factoring data, with measures specific to each of the learning tasks. As the goal is to evaluate the tasks, rather than the learning methods, we compare them for three different families of learning methods: linear models, support vector machines and gradient-boosted trees. To better answer the question of the suitability of the different tasks for spot factoring, we also perform a profit-driven evaluation. In the experiments, regression methods achieve consistently high scores across the evaluation measures and for all method families. The profit-based evaluation identified the regressor with XGBoost as an outspokenly good performer. We recommend evaluating from a profit-based perspective in a spot factoring context, as it is easily interpretable, consolidates the business objective and addresses the different possible costs associated with different invoice outcomes.

Uplift modeling is an instrument used to estimate the change in outcome due to a treatment at the individual entity level. Uplift models assist decision-makers in optimally allocating scarce resources. This allows the selection of the subset of entities for which the effect of a treatment will be largest and, as such, the maximization of the overall returns. The literature on uplift modeling mostly focuses on queries concerning the effect of a single treatment and rarely considers situations where more than one treatment alternative is utilized. This article surveys the current literature on multitreatment uplift modeling and proposes two novel techniques: the naive uplift approach and the multitreatment modified outcome approach. Moreover, a benchmarking experiment is performed to contrast the performances of different multitreatment uplift modeling techniques across eight data sets from various domains. We verify and, if needed, correct the imbalance among the pretreatment characteristics of the treatment groups by means of optimal propensity score matching, which ensures a correct interpretation of the estimated uplift. Conventional and recently proposed evaluation metrics are adapted to the multitreatment scenario to assess performance. None of the evaluated techniques consistently outperforms other techniques. Hence, it is concluded that performance largely depends on the context and problem characteristics. The newly proposed techniques are found to offer similar performances compared to state-of-the-art approaches.

In the majority of executive domains, a notion of normality is involved in most strategic decisions. However, few data-driven tools that support strategic decision-making are available. We introduce and extend the use of autoencoders to provide strategically relevant granular feedback. A first experiment indicates that experts are inconsistent in their decision making, highlighting the need for strategic decision support. Furthermore, using two large industry-provided human resources datasets, the proposed solution is evaluated in terms of ranking accuracy, synergy with human experts, and dimension-level feedback. This three-point scheme is validated using (a) synthetic data, (b) the perspective of data quality, (c) blind expert validation, and (d) transparent expert evaluation. Our study confirms several principal weaknesses of human decision-making and stresses the importance of synergy between a model and humans. Moreover, unsupervised learning and in particular the autoencoder are shown to be valuable tools for strategic decision-making. ispartof: Decision Support Systems vol:150 status: published

Many decision-making processes involve solving a combinatorial optimization problem with uncertain input that can be estimated from historic data. Recently, problems in this class have been successfully addressed via end-to-end learning approaches, which rely on solving one optimization problem for each training instance at every epoch. In this context, we provide two distinct contributions. First, we use a Noise Contrastive approach to motivate a family of surrogate loss functions, based on viewing non-optimal solutions as negative examples. Second, we address a major bottleneck of all predict-and-optimize approaches, i.e. the need to frequently recompute optimal solutions at training time. This is done via a solver-agnostic solution caching scheme, and by replacing optimization calls with a lookup in the solution cache. The method is formally based on an inner approximation of the feasible space and, combined with a cache lookup strategy, provides a controllable trade-off between training time and accuracy of the loss approximation. We empirically show that even a very slow growth rate is enough to match the quality of state-of-the-art methods, at a fraction of the computational cost., Accepted at IJCAI2021

There is an increased interest in solving complex constrained problems where part of the input is not given as facts, but received as raw sensor data such as images or speech. We will use ‘visual sudoku’ as a prototype problem, where the given cell digits are handwritten and provided as an image thereof. In this case, one first has to train and use a classifier to label the images, so that the labels can be used for solving the problem. In this paper, we explore the hybridisation of classifying the images with the reasoning of a constraint solver. We show that pure constraint reasoning on predictions does not give satisfactory results. Instead, we explore the possibilities of a tighter integration, by exposing the probabilistic estimates of the classifier to the constraint solver. This allows joint inference on these probabilistic estimates, where we use the solver to find the maximum likelihood solution. We explore the trade-off between the power of the classifier and the power of the constraint reasoning, as well as further integration through the additional use of structural knowledge. Furthermore, we investigate the effect of calibration of the probabilistic estimates on the reasoning. Our results show that such hybrid approaches vastly outperform a separate approach, which encourages a further integration of prediction (probabilities) and constraint solving.

The interest for data mining techniques has increased tremendously during the past decades, and numerous classification techniques have been applied in a wide range of business applications. Hence, the need for adequate performance measures has become more important than ever. In this paper, a cost-benefit analysis framework is formalized in order to define performance measures which are aligned with the main objectives of the end users, i.e., profit maximization. A new performance measure is defined, the expected maximum profit criterion. This general framework is then applied to the customer churn problem with its particular cost-benefit structure. The advantage of this approach is that it assists companies with selecting the classifier which maximizes the profit. Moreover, it aids with the practical implementation in the sense that it provides guidance about the fraction of the customer base to be included in the retention campaign.

Much of the power of CP comes from the ability to create complex hybrid search algorithms specific to an application. Unfortu- nately there is no widely accepted standard for specifying search, and each solver typically requires detailed knowledge in order to build com- plex searches. This makes the barrier to entry for exploring different search methods quite high. Furthermore, search is a core part of the solver and usually highly optimised. Any imposition on the solver writer to change this part of their system is significant. In this paper we investigate how powerful we can make a uniform lan- guage for meta-search without placing any burden on the solver writer. The key to this is to only interact with the solver when a solution is found. We present MiniSearch, a meta-search language that can directly use any FlatZinc solver. Optionally, it can interact with solvers through an efficient C++ API. We illustrate the expressiveness of the language and performance using different solvers on a number of examples. ispartof: pages:376-392 ispartof: Proceedings of the 21st International Conference on Principles and Practice of Constraint Programming (CP 2015) vol:9255 pages:376-392 ispartof: Principles and Practice of Constraint Programming location:Cork, Ireland date:31 Aug - 4 Sep 2015 status: published

We present MiningZinc, a novel system for con- straint-based pattern mining. It provides a declarative approach to data mining, where a user specifies a problem in terms of constraints and the system employs advanced techniques to efficiently find solutions. Declarative programming and modeling are common in artificial intelligence and in database systems, but not so much in data mining; by building on ideas from these communities, MiningZinc advances the state-of-the-art of declarative data mining significantly. Key components of the MiningZinc system are (1) a high-level and natural language for formalizing constraint-based itemset mining problems in models, and (2) an infrastructure for executing these models, which supports both specialised mining algorithms as well as generic constraint solving systems. A use case demonstrates the generality of the language, as well as its flexibility towards adding and modifying constraints and data, as well as the use of different solution methods. ispartof: pages:1081-1084 ispartof: 13th IEEE International Conference on Data Mining Workshops pages:1081-1084 ispartof: Demo track at the IEEE International Conference on Data Mining location:Dallas, Texas, USA date:7 Dec - 10 Dec 2013 status: published

We introduce the problem of k-pattern set mining, concerned with finding a set of k related patterns under constraints. This contrasts to regular pattern mining, where one searches for many individual patterns. The k-pattern set mining problem is a very general problem that can be instantiated to a wide variety of well-known mining tasks including concept-learning, rule-learning, redescription mining, conceptual clustering and tiling. To this end, we formulate a large number of constraints for use in k-pattern set mining, both at the local level, that is, on individual patterns, and on the global level, that is, on the overall pattern set. Building general solvers for the pattern set mining problem remains a challenge. Here, we investigate to what extent constraint programming (CP) can be used as a general solution strategy. We present a mapping of pattern set constraints to constraints currently available in CP. This allows us to investigate a large number of settings within a unified framework and to gain insight in the possibilities and limitations of these solvers. This is important as it allows us to create guidelines in how to model new problems successfully and how to model existing problems more efficiently. It also opens up the way for other solver technologies. ispartof: IEEE Transactions on Knowledge and Data Engineering vol:25 issue:2 pages:402-418 status: published

Finding small sets of interesting patterns is an important challenge in pattern mining. In this paper, we argue that several well-known approaches that address this challenge are based on performing pairwise comparisons between patterns. Examples include finding closed patterns, free patterns, relevant subgroups and skyline patterns. Although progress has been made on each of these individual problems, a generic approach for solving these problems (and more) is still lacking. This paper tackles this challenge. It proposes a novel, generic approach for handling pattern mining problems that involve pairwise compar- isons between patterns. Our key contributions are the following. First, we propose a novel algebra for programming pattern mining problems. This algebra extends relational algebras in a novel way towards pattern mining. It allows for the generic combination of constraints on individual patterns with dominance relations between patterns. Second, we introduce a modified generic constraint satisfaction system to evaluate these algebraic expressions. Experiments show that this generic approach can indeed effectively identify patterns expressed in the algebra. ispartof: pages:557-566 ispartof: 13th IEEE International Conference on Data Mining pages:557-566 ispartof: IEEE International Conference on Data Mining location:Dallas, Texas, USA date:7 Dec - 10 Dec 2013 status: published

Most traditional biclustering algorithms identify biclusters with no or little overlap. In this paper, we introduce the problem of identifying staircases of biclusters. Such staircases may be indicative for causal relationships between columns and can not easily be identified by existing biclustering algorithms. Our formalization relies on a scoring function based on the Minimum Description Length principle. Furthermore, we propose a first algorithm for identifying staircase biclusters, based on a combination of local search and constraint programming. Experiments show that the approach is promising. ispartof: pages:139-146 ispartof: 12th IEEE International Conference on Data Mining Workshops pages:139-146 ispartof: International workshop on Co-Clustering and Applications (CoClus'12) in conjunction with IEEE ICDM 2012 location:Brussels date:10 Dec - 10 Dec 2012 status: published

Recently, constraint programming has been proposed as a declarative framework for constraint-based pattern mining. In constraint programming, a problem is modelled in terms of constraints and search is done by a general solver. Similar to most pattern mining algorithms, these solvers typically employ exhaustive depth-first search, where constraints are used to prune the search space and make the search viable. In this paper we investigate the use of a similar declarative approach to the problem of pattern set mining. In pattern set mining one is searching for a small and useful set of patterns. In contrast to pattern mining, however, exhaustive search is not common in pattern set mining; the search space is often far too large to make such an approach practical. In this paper, we investigate an approach which aims to make general pattern set mining feasible by using a recently developed general solver that supports exhaustive as well as heuristic search. The key idea in this solver is that next to a declarative specification of the constraints also a high-level declarative description of the search is given. By separating the model and the search from the solver, the approach offers the advantage of reusing constraints and search strategies declaratively, while also allowing fast heuristic search. ispartof: pages:1104-1111 ispartof: Proceedings of the 11th IEEE International Conference on Data Mining Workshops pages:1104-1111 ispartof: Workshop on Declarative Pattern Mining in conjunction with the 11th IEEE International Conference on Data Mining location:Vancouver, Canada date:11 Dec - 14 Dec 2011 status: published

The pattern mining community has shifted its attention from local pattern mining to pattern set mining. The task of pattern set mining is concerned with finding a set of patterns that satisfies a set of constraints and often also scores best w.r.t. an optimisation criteria. Furthermore, while in local pattern mining the constraints are imposed at the level of individual patterns, in pattern set mining they are also concerned with the overall set of patterns. A wide variety of different pattern set mining techniques is available in literature. The key contribution of this paper is that it studies, compares and evaluates such search strategies for pattern set mining. The investigation employs concept-learning as a benchmark for pattern set mining and employs a constraint programming framework in which key components of pattern set mining are formulated and implemented. The study leads to novel insights into the strong and weak points of different pattern set mining strategies. Book subtitle: 15TH PACIFIC-ASIA CONFERENCE, PAKDD 2011 ispartof: pages:382-394 ispartof: Advances in Knowledge Discovery and Data Mining, 15th Pacific-Asia Conference, PAKDD 2011 vol:6635 issue:PART 2 pages:382-394 ispartof: Pacific-Asia Conference on Knowledge Discovery and Data Mining location:Shenzhen, China date:24 May - 27 May 2011 status: published

We propose a new framework for constraint-based pattern mining in multi-relational databases. Distinguishing features of the framework are that (1) it allows finding patterns not only under anti-monotonic constraints, but also under monotonic constraints and closedness constraints, among others, expressed over complex aggregates over multiple relations; (2) it builds on a declarative graphical representation of constraints that links closely to data models of multi-relational databases and constraint networks in constraint programming; (3) it maps multi-relational pattern mining tasks into constraint programs. Our framework builds on a unifying perspective of multi-relational pattern mining, relational database technology and constraint networks in constraint programming. We demonstrate our framework on IMDB and Finance multi-relational databases. ispartof: pages:1120-1127 ispartof: Proceedings of the 11th IEEE International Conference on Data Mining Workshops pages:1120-1127 ispartof: Workshop on Declarative Pattern Mining in conjunction with the 11th IEEE International Conference on Data Mining location:Vancouver, Canada date:11 Dec - 14 Dec 2011 status: published

Over the years many pattern mining tasks and algorithms have been proposed. Traditionally, the focus of these studies was on the efficiency of the computation and the scalability towards very large databases. Little research has however been done on a general framework that encompasses several of these problems. In earlier work we showed how constraint programming (CP) can offer such a general framework; unfortunately, however, we also found that out-of-the-box CP solvers lack the efficiency and scalability achieved by specialized itemset mining systems, which could discourage their use. Here we study the question whether a framework can be built that inherits the generality of CP systems and the efficiency of specialized algorithms. We propose a CP-based framework for pattern mining that avoids the redundant representations and propagations found in existing CP systems. We show experimentally that an implementation of this framework performs comparable to specialized itemset mining systems; furthermore, under certain conditions it lists itemsets with polynomial delay, which demonstrates that it also is a promising approach for analyzing pattern mining tasks from more theoretical perspectives. This is illustrated on a graph mining problem. acceptance rate = 19.0% ispartof: pages:467-482 ispartof: Lecture Notes in Computer Science vol:6322 issue:PART 2 pages:467-482 ispartof: European Conference on Machine Learning and Knowledge Discovery in Databases location:Barcelona date:20 Sep - 24 Sep 2010 status: published

We propose a method for finding CRMs in a set of co-regulated genes. Each CRM consists of a set of binding sites of transcription factors. We wish to find CRMs involving the same transcription factors in multiple sequences. Finding such a combination of transcription factors is inherently a combinatorial problem. We solve this problem by combining the principles of itemset mining and constraint programming. The constraints involve the putative binding sites of transcription factors, the number of sequences in which they co-occur and the proximity of the binding sites. Genomic background sequences are used to assess the significance of the modules. We experimentally validate our approach and compare it with state-of-the-art techniques. acceptance rate = 17.2% ispartof: pages:363-368 ispartof: Proc. of IEEE International Conference on Bioinformatics & Biomedicine pages:363-368 ispartof: IEEE International Conference on Bioinformatics & Biomedicine location:Hong Kong date:18 Dec - 21 Dec 2010 status: published

Correlated or discriminative pattern mining is concerned with finding the highest scoring patterns w.r.t. a correlation measure (such as information gain). By reinterpreting correlation measures in ROC space and formulating correlated itemset mining as a constraint programming problem, we obtain new theoretical insights with practical benefits. More specifically, we contribute 1) an improved bound for correlated itemset miners, 2) a novel iterative pruning algorithm to exploit the bound, and 3) an adaptation of this algorithm to mine all itemsets on the convex hull in ROC space. The algorithm does not depend on a minimal frequency threshold and is shown to outperform several alternative approaches by orders of magnitude, both in runtime and in memory requirements. ispartof: pages:647-656 ispartof: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining pages:647-656 ispartof: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining location:Paris, France date:28 Jun - 1 Jul 2009 status: published