Advances in Knowledge Discovery and Data Mining

Table of Contents

1. Frontmatter

2. Classification and Supervised Learning

   1. Frontmatter

   2. Multitask Learning for Sparse Failure Prediction

      Simon Luo, Victor W. Chu, Zhidong Li, Yang Wang, Jianlong Zhou, Fang Chen, Raymond K. Wong

      Abstract

      Sparsity is a problem which occurs inherently in many real-world datasets. Sparsity induces an imbalance in data, which has an adverse effect on machine learning and hence reducing the predictability. Previously, strong assumptions were made by domain experts on the model parameters by using their experience to overcome sparsity, albeit assumptions are subjective. Differently, we propose a multi-task learning solution which is able to automatically learn model parameters from a common latent structure of the data from related domains. Despite related, datasets commonly have overlapped but dissimilar feature spaces and therefore cannot simply be combined into a single dataset. Our proposed model, namely hierarchical Dirichlet process mixture of hierarchical beta process (HDP-HBP), learns tasks with a common model parameter for the failure prediction model using hierarchical Dirichlet process. Our model uses recorded failure history to make failure predictions on a water supply network. Multi-task learning is used to gain additional information from the failure records of water supply networks managed by other utility companies to improve prediction in one network. We achieve superior accuracy for sparse predictions compared to previous state-of-the-art models and have demonstrated the capability to be used in risk management to proactively repair critical infrastructure.

   3. Cost Sensitive Learning in the Presence of Symmetric Label Noise

      Sandhya Tripathi, Nandyala Hemachandra

      Abstract

      In binary classification framework, we are interested in making cost sensitive label predictions in the presence of uniform/symmetric label noise. We first observe that 0–1 Bayes classifiers are not (uniform) noise robust in cost sensitive setting. To circumvent this impossibility result, we present two schemes; unlike the existing methods, our schemes do not require noise rate. The first one uses \(\alpha \)-weighted \(\gamma \)-uneven margin squared loss function, \(l_{\alpha , usq}\), which can handle cost sensitivity arising due to domain requirement (using user given \(\alpha \)) or class imbalance (by tuning \(\gamma \)) or both. However, we observe that \(l_{\alpha , usq}\) Bayes classifiers are also not cost sensitive and noise robust. We show that regularized ERM of this loss function over the class of linear classifiers yields a cost sensitive uniform noise robust classifier as a solution of a system of linear equations. We also provide a performance bound for this classifier. The second scheme that we propose is a re-sampling based scheme that exploits the special structure of the uniform noise models and uses in-class probability estimates. Our computational experiments on some UCI datasets with class imbalance show that classifiers of our two schemes are on par with the existing methods and in fact better in some cases w.r.t. Accuracy and Arithmetic Mean, without using/tuning noise rate. We also consider other cost sensitive performance measures viz., F measure and Weighted Cost for evaluation.

   4. Semantic Explanations in Ensemble Learning

      Md. Zahidul Islam, Jixue Liu, Lin Liu, Jiuyong Li, Wei Kang

      Abstract

      A combination method is an integral part of an ensemble classifier. Existing combination methods determine the combined prediction of a new instance by relying on the predictions made by the majority of base classifiers. This can result in incorrect combined predictions when the majority predict the incorrect class. It has been noted that in group decision-making, the decision by the majority, if lacking consistency in the reasons for the decision provided by its members, could be less reliable than the minority’s decision with higher consistency in the reasons of its members. Based on this observation, in this paper, we propose a new combination method, EBCM, which considers the consistency of the features, i.e. explanations of individual predictions for generating ensemble classifiers. EBCM firstly identifies the features accountable for each base classifier’s prediction, and then uses the features to measure the consistency among the predictions. Finally, EBCM combines the predictions based on both the majority and the consistency of features. We evaluated the performance of EBCM with 16 real-world datasets and observed substantial improvement over existing techniques.

   5. Latent Gaussian-Multinomial Generative Model for Annotated Data

      Shuoran Jiang, Yarui Chen, Zhifei Qin, Jucheng Yang, Tingting Zhao, Chuanlei Zhang

      Abstract

      Traditional generative models annotate images by multiple instances independently segmented, but these models have been becoming prohibitively expensive and time-consuming along with the growth of Internet data. Focusing on the annotated data, we propose a latent Gaussian-Multinomial generative model (LGMG), which generates the image-annotations using a multimodal probabilistic models. Specifically, we use a continuous latent variable with prior of Normal distribution as the latent representation summarizing the high-level semantics of images, and a discrete latent variable with prior of Multinomial distribution as the topics indicator for annotation. We compute the variational posteriors from a mapping structure among latent representation, topics indicator and image-annotation. The stochastic gradient variational Bayes estimator on variational objective is realized by combining the reparameterization trick and Monte Carlo estimator. Finally, we demonstrate the performance of LGMG on LabelMe in terms of held-out likelihood, automatic image annotation with the state-of-the-art models.

   6. Investigating Neighborhood Generation Methods for Explanations of Obscure Image Classifiers

      Riccardo Guidotti, Anna Monreale, Leonardo Cariaggi

      Abstract

      Given the wide use of machine learning approaches based on opaque prediction models, understanding the reasons behind decisions of black box decision systems is nowadays a crucial topic. We address the problem of providing meaningful explanations in the widely-applied image classification tasks. In particular, we explore the impact of changing the neighborhood generation function for a local interpretable model-agnostic explanator by proposing four different variants. All the proposed methods are based on a grid-based segmentation of the images, but each of them proposes a different strategy for generating the neighborhood of the image for which an explanation is required. A deep experimentation shows both improvements and weakness of each proposed approach.

   7. On Calibration of Nested Dichotomies

      Tim Leathart, Eibe Frank, Bernhard Pfahringer, Geoffrey Holmes

      Abstract

      Nested dichotomies (NDs) are used as a method of transforming a multiclass classification problem into a series of binary problems. A tree structure is induced that recursively splits the set of classes into subsets, and a binary classification model learns to discriminate between the two subsets of classes at each node. In this paper, we demonstrate that these NDs typically exhibit poor probability calibration, even when the binary base models are well-calibrated. We also show that this problem is exacerbated when the binary models are poorly calibrated. We discuss the effectiveness of different calibration strategies and show that accuracy and log-loss can be significantly improved by calibrating both the internal base models and the full ND structure, especially when the number of classes is high.

   8. Ensembles of Nested Dichotomies with Multiple Subset Evaluation

      Tim Leathart, Eibe Frank, Bernhard Pfahringer, Geoffrey Holmes

      Abstract

      A system of nested dichotomies (NDs) is a method of decomposing a multiclass problem into a collection of binary problems. Such a system recursively applies binary splits to divide the set of classes into two subsets, and trains a binary classifier for each split. Many methods have been proposed to perform this split, each with various advantages and disadvantages. In this paper, we present a simple, general method for improving the predictive performance of NDs produced by any subset selection techniques that employ randomness to construct the subsets. We provide a theoretical expectation for performance improvements, as well as empirical results showing that our method improves the root mean squared error of NDs, regardless of whether they are employed as an individual model or in an ensemble setting.