We argue that the dominant approach to explainable AI for explaining image classification, annotating images with heatmaps, provides little value for users unfamiliar with deep learning. We argue that explainable AI for images should produce output like experts produce when communicating with one another, with apprentices, and with novices. We provide an expanded set of goals of explainable AI systems and propose a Turing Test for explainable AI.

In this study, we propose a post-hoc explainability framework for deep learning models applied to quasi-periodic biomedical time-series classification. As a case study, we focus on the problem of atrial fibrillation (AF) detection from electrocardiography signals, which has strong clinical relevance. Starting from a state-of-the-art pretrained model, we tackle the problem from two different perspectives: global and local explanation. With global explanation, we analyze the model behavior by looking at entire classes of data, showing which regions of the input repetitive patterns have the most influence for a specific outcome of the model. Our explanation results align with the expectations of clinical experts, showing that features crucial for AF detection contribute heavily to the final decision. These features include R-R interval regularity, absence of the P-wave or presence of electrical activity in the isoelectric period. On the other hand, with local explanation, we analyze specific input signals and model outcomes. We present a comprehensive analysis of the network facing different conditions, whether the model has correctly classified the input signal or not. This enables a deeper understanding of the network's behavior, showing the most informative regions that trigger the classification decision and highlighting possible causes of misbehavior.

Noise and missing data are intrinsic characteristics of real-world data, leading to uncertainty that negatively affects the quality of knowledge extracted from the data. The burden imposed by missing data is often severe in sensors that collect data from the physical world, where large gaps of missing data may occur when the system is temporarily off or disconnected. How can we reconstruct missing data for these periods? We introduce an accurate and efficient algorithm for missing data reconstruction (imputation), that is specifically designed to recover off-period segments of missing data. This algorithm, Ghost, searches the sequential dataset to find data segments that have a prior and posterior segment that matches those of the missing data. If there is a similar segment that also satisfies the constraint - such as location or time of day - then it is substituted for the missing data. A baseline approach results in quadratic computational complexity, therefore we introduce a caching approach that reduces the search space and improves the computational complexity to linear in the common case. Experimental evaluations on five real-world datasets show that our algorithm significantly outperforms four state-of-the-art algorithms with an average of 18 percent higher F-score.

This work introduces a set of scalable algorithms to identify patterns of human daily behaviors. These patterns are extracted from multivariate temporal data that have been collected from smartphones. We have exploited sensors that are available on these devices, and have identified frequent behavioral patterns with a temporal granularity, which has been inspired by the way individuals segment time into events. These patterns are helpful to both end-users and third parties who provide services based on this information. We have demonstrated our approach on two real-world datasets and showed that our pattern identification algorithms are scalable. This scalability makes analysis on resource constrained and small devices such as smartwatches feasible. Traditional data analysis systems are usually operated in a remote system outside the device. This is largely due to the lack of scalability originating from software and hardware restrictions of mobile/wearable devices. By analyzing the data on the device, the user has the control over the data, i.e., privacy, and the network costs will also be removed.

This paper describes a new technique and analysis for using on-line learning algorithms to solve active learning problems. Our algorithm is called Active Vote, and it works by actively selecting instances that force several perturbed copies of an on-line algorithm to make mistakes. The main intuition for our result is based on the fact that the number of mistakes made by the optimal on-line algorithm is a lower bound on the number of labels needed for active learning. We provide performance bounds for Active Vote in both a batch and on-line model of active learning. These performance bounds depend on the algorithm having a set of unlabeled instances in which the various perturbed on-line algorithms disagree. The motivating application for Active Vote is an Internet advertisement rating program. We conduct experiments using data collected for this advertisement problem along with experiments using standard datasets. We show Active Vote can achieve an order of magnitude decrease in the number of labeled instances over various passive learning algorithms such as Support Vector Machines.

The increasing availability of large-scale location traces creates unprecedent opportunities to change the paradigm for knowledge discovery in transportation systems. A particularly promising area is to extract energy-efficient transportation patterns (green knowledge), which can be used as guidance for reducing inefficiencies in energy consumption of transportation sectors. However, extracting green knowledge from location traces is not a trivial task. Conventional data analysis tools are usually not customized for handling the massive quantity, complex, dynamic, and distributed nature of location traces. To that end, in this paper, we provide a focused study of extracting energy-efficient transportation patterns from location traces. Specifically, we have the initial focus on a sequence of mobile recommendations. As a case study, we develop a mobile recommender system which has the ability in recommending a sequence of pick-up points for taxi drivers or a sequence of potential parking positions. The goal of this mobile recommendation system is to maximize the probability of business success. Along this line, we provide a Potential Travel Distance (PTD) function for evaluating each candidate sequence. This PTD function possesses a monotone property which can be used to effectively prune the search space. Based on this PTD function, we develop two algorithms, LCP and SkyRoute, for finding the recommended routes. Finally, experimental results show that the proposed system can provide effective mobile sequential recommendation and the knowledge extracted from location traces can be used for coaching drivers and leading to the efficient use of energy.

In this paper, we discuss a prototype application deployed at the U.S. National Science Foundation for assisting program directors in identifying reviewers for proposals. The application helps program directors sort proposals into panels and find reviewers for proposals. To accomplish these tasks, it extracts information from the full text of proposals both to learn about the topics of proposals and the expertise of reviewers. We discuss a variety of alternatives that were explored, the solution that was implemented, and the experience in using the solution within the workflow of NSF.

Summary form only given. People have access to vast stores of information on the World Wide Web ranging from online publications to electronic commerce. All this information, however, used to be accessible only while users are tethered to a computer at home or in an office. Wireless data and voice access to this vast store allows unprecedented access to information from any location at any time. The presentation of this information must be tailored to the constraints of mobile devices. Although browsing and searching are the acceptable methods of locating information on the wired Web, those operations soon become cumbersome and inefficient in the wireless setting and impossible in voice interfaces. Small screens, slower connections, high latency, limited input capabilities, and the serial nature of voice interfaces present new challenges. This work focuses on personalization techniques that are essential for the usability of handheld wireless devices.

1 Introduction Time series are a ubiquitous form of data occurring in virtually every scientific discipline and business application. There has been much recent work on adapting data mining algorithms to time series databases. For example, Das et al. attempt to show how association rules can be learned from time series [7]. Debregeas and Hebrail [8] demonstrate a technique for scaling up time series clustering algorithms to massive datasets. Keogh and Pazzani introduced a new, scalable time series classification algorithm [16]. Almost all algorithms that operate on time series data need to compute the similarity between them. Euclidean distance, or some extension or modification thereof, is typically used. However as we will demonstrate in Section 2.1, Euclidean distance can be an extremely brittle distance measure.

Similarity search in large time series databases has attracted much research interest recently. It is a difficult problem because of the typically high dimensionality of the data. The most promising solutions involve performing dimensionality reduction on the data, then indexing the reduced data with a multidimensional index structure. Many dimensionality reduction techniques have been proposed, including Singular Value Decomposition (SVD), the Discrete Fourier transform (DFT), and the Discrete Wavelet Transform (DWT). In this article, we introduce a new dimensionality reduction technique, which we call Adaptive Piecewise Constant Approximation (APCA). While previous techniques (e.g., SVD, DFT and DWT) choose a common representation for all the items in the database that minimizes the global reconstruction error, APCA approximates each time series by a set of constant value segments of varying lengths such that their individual reconstruction errors are minimal. We show how APCA can be indexed using a multidimensional index structure. We propose two distance measures in the indexed space that exploit the high fidelity of APCA for fast searching: a lower bounding Euclidean distance approximation, and a non-lower-bounding, but very tight, Euclidean distance approximation, and show how they can support fast exact searching and even faster approximate searching on the same index structure. We theoretically and empirically compare APCA to all the other techniques and demonstrate its superiority.

In recent years, there has been an explosion of interest in mining time-series databases. As with most computer science problems, representation of the data is the key to efficient and effective solutions. One of the most commonly used representations is piecewise linear approximation. This representation has been used by various researchers to support clustering, classification, indexing and association rule mining of time-series data. A variety of algorithms have been proposed to obtain this representation, with several algorithms having been independently rediscovered several times. In this paper, we undertake the first extensive review and empirical comparison of all proposed techniques. We show that all these algorithms have fatal flaws from a data-mining perspective. We introduce a novel algorithm that we empirically show to be superior to all others in the literature.

The problem of similarity search (query-by-content) has attracted much research interest. It is a difficult problem because of the inherently high dimensionality of the data. The most promising solutions involve performing dimensionality reduction on the data, then indexing the reduced data with a multidimensional index structure. Many dimensionality reduction techniques have been proposed, including Singular Value Decomposition (SVD), the Discrete Fourier Transform (DFT), the Discrete Wavelet Transform (DWT) and Piecewise Polynomial Approximation. In this work, we introduce a novel framework for using ensembles of two or more representations for more efficient indexing. The basic idea is that instead of committing to a single representation for an entire dataset, different representations are chosen for indexing different parts of the database. The representations are chosen based upon a local view of the database. For example, sections of the data that can achieve a high fidelity representation with wavelets are indexed as wavelets, but highly spectral sections of the data are indexed using the Fourier transform. At query time, it is necessary to search several small heterogeneous indices, rather than one large homogeneous index. As we will theoretically and empirically demonstrate this results in much faster query response times.

1 Introduction Time series are a ubiquitous form of data occurring in virtually every scientific discipline. A common task with time series data is comparing one sequence with another. In some domains a very simple distance measure, such as Euclidean distance will suffice. However, it is often the case that two sequences have the approximately the same overall component shapes, but these shapes do not line up in X-axis. Figure 1 shows this with a simple example. In order to find the similarity between such sequences, or as a preprocessing step before averaging them, we must “warp” the time axis of one (or both) sequences to achieve a better alignment. Dynamic time warping (DTW), is a technique for efficiently achieving this warping. In addition to data mining (Keogh & Pazzani 2000, Yi et. al. 1998, Berndt & Clifford 1994), DTW has been used in gesture recognition (Gavrila & Davis 1995), robotics (Schmill et. al 1999), speech processing (Rabiner & Juang 1993), manufacturing (Gollmer & Posten 1995) and medicine (Caiani et. al 1998).

Similarity search in large time series databases has attracted much research interest recently. It is a difficult problem because of the typically high dimensionality of the data.. The most promising solutions involve performing dimensionality reduction on the data, then indexing the reduced data with a multidimensional index structure. Many dimensionality reduction techniques have been proposed, including Singular Value Decomposition (SVD), the Discrete Fourier transform (DFT), and the Discrete Wavelet Transform (DWT). In this work we introduce a new dimensionality reduction technique which we call Adaptive Piecewise Constant Approximation (APCA). While previous techniques (e.g., SVD, DFT and DWT) choose a common representation for all the items in the database that minimizes the global reconstruction error, APCA approximates each time series by a set of constant value segments of varying lengths such that their individual reconstruction errors are minimal. We show how APCA can be indexed using a multidimensional index structure. We propose two distance measures in the indexed space that exploit the high fidelity of APCA for fast searching: a lower bounding Euclidean distance approximation, and a non-lower bounding, but very tight Euclidean distance approximation and show how they can support fast exact searching, and even faster approximate searching on the same index structure. We theoretically and empirically compare APCA to all the other techniques and demonstrate its superiority.

Mobile internet technologies, such as WAP, are important for pervasive, anytime, anywhere computing. Although much progress has been made in terms of technological innovation, many of mobile internet systems are difficult to use, lack flexibility and robustness. They give a poor user experience. Evaluation and theoretical analysis of usability combined with innovative design can achieve significant improvements in user performance and satisfaction. Using such multidisciplinary methods explains the negative reactions to WAP, and --- more constructively --- suggest ways of developing more effective and efficient devices and services. Key words: Mobile internet, HCI, Usability, WAP. 1.

We describe a user interface for wireless information devices, specifically designed to facilitate learning about users' individual interests in daily news stories. User feedback is collected unobtrusively to form the basis for a content-based machine learning algorithm. As a result, the described system can adapt to users' individual interests, reduce the amount of information that needs to be transmitted, and help users access relevant information with minimal effort.

Electronic mail offers the promise of rapid communication of essential information. However, electronic mail is also used to send unwanted messages. A variety of approaches can learn a profile of a user's interests for filtering mail. Here, we report on a usability study that investigates what types of profiles people would be willing to use to filter mail.

There has been much recent interest in adapting data mining algorithms to time series databases.Most of these algorithms need to compare time series.Typically some variation of Euclidean distance is used.However, as we demonstrate in this paper, Euclidean distance can be an extremely brittle distance measure.Dynamic time warping (DTW) has been suggested as a technique to allow more robust distance calculations, however it is computationally expensive.In this paper we introduce a modification of DTW which operates on a higher level abstraction of the data, in particular, a Piecewise Aggregate Approximation (PAA).Our approach allows us to outperform DTW by one to two orders of magnitude, with no loss of accuracy.

Article Detecting change in categorical data: mining contrast sets Share on Authors: Stephen D. Bay Department of Information and Computer Science, University of California, Irvine, Irvine, CA Department of Information and Computer Science, University of California, Irvine, Irvine, CAView Profile , Michael J. Pazzani Department of Information and Computer Science, University of California, Irvine, Irvine, CA Department of Information and Computer Science, University of California, Irvine, Irvine, CAView Profile Authors Info & Claims KDD '99: Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data miningAugust 1999 Pages 302–306https://doi.org/10.1145/312129.312263Online:01 August 1999Publication History 106citation1,021DownloadsMetricsTotal Citations106Total Downloads1,021Last 12 Months37Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

There has been much recent interest in retrieval of time series data.Earlier work has used a fixed similarity metric (e.g., Euclidean distance) to determine the similarity between a userspecified query and items in the database.Here, we describe a novel approach to retrieval of time series data by using relevance feedback from the user to adjust the similarity metric.This is important because the Euclidean distance metric does not capture many notions of similarity between time series.In particular, Euclidean distance is sensitive to various "distortions" such as offset translation, amplitude scaling, etc. Depending on the domain and the user, one may wish a query to be sensitive or insensitive to these distortions to varying degrees.This paper addresses this problem by introducing a profile that encodes the user's subjective notion of similarity in a domain.These profiles can be learned continuously from interaction with the user.We further show how the user profile may be embedded in a system that uses relevance feedback to modify the query in a manner analogous to the familiar text retrieval algorithms.

Addresses the problem of similarity searching in large time-series databases. We introduce a novel indexing algorithm that allows faster retrieval. The index is formed by creating bins that contain time series subsequences of approximately the same shape. For each bin, we can quickly calculate a lower bound on the distance between a given query and the most similar element of the bin. This bound allows us to search the bins in best-first order, and to prune some bins from the search space without having to examine the contents. Additional speedup is obtained by optimizing the data within the bins such that we can avoid having to compare the query to every item in the bin. We call our approach STB (Shape To Bit-vector) indexing, and experimentally validate it on space telemetry, medical and synthetic data, demonstrating approximately an order-of-magnitude speedup.

We describe a software agent that learns to find information on the World Wide Web (WWW), deciding what new pages might interest a user. The agent maintains a separate hotlist (for links that were interesting) and coldlist (for links that were not interesting) for each topic. By analyzing the information immediately accessible from each link, the agent learns the types of information the user is interested in. This can be used to inform the user when a new interesting page becomes available or to order the user's exploration of unseen existing links so that the more promising ones are investigated first. We compare four different learning algorithms on this task. We describe an experiment in which a simple Bayesian classifier acquires a user profile that agrees with a user's judgment over 90% of the time.

In sparse data environments, greater classification accuracy can be achieved by learning several concept descriptions of the data and combining their classifications. Stochastic searching can be used to generate many concept descriptions (rule sets) for each class in the data. We use a tractable approximation to the optimal Bayesian method for combining classifications from such descriptions. The primary result of this paper is that multiple concept descriptions are particularly helpful in "flat" hypothesis spaces in which there are many equally good ways to grow a rule, each having similar gain. Another result is experimental evidence that learning multiple rule sets yields more accurate classifications than learning multiple rules for some domains.>

We investigate methods for tuning numeric parameters in Nynex MAX, a telephone trouble screening expert system. Steepest descent, hillclimbing, and simulated annealing parameter adjustment strategies are applied to the problems of maximizing classification accuracy and minimizing misclassification cost. For both of those optimization problems we evaluate each algorithm's ability to tune initial parameters for several situations.>

We report on a series of experiments in which all decision trees consistent with the training data are constructed. These experiments were run to gain an understanding of the properties of the set of consistent decision trees and the factors that affect the accuracy of individual trees. In particular, we investigated the relationship between the size of a decision tree consistent with some training data and the accuracy of the tree on test data. The experiments were performed on a massively parallel Maspar computer. The results of the experiments on several artificial and two real world problems indicate that, for many of the problems investigated, smaller consistent decision trees are on average less accurate than the average accuracy of slightly larger trees.

An application of failure-driven learning to the construction of the knowledge base of a diagnostic expert system is discussed. Diagnosis heuristics (i.e., efficient rules which encode empirical associations between atypical device behavior and device failures) are learned from information implicit in device models. This approach is desirable since less effort is required to obtain information about device functionality and connectivity to define device models than to encode and debug diagnosis heuristics from a domain expert. Results are given of applying this technique in an expert system for the diagnosis of failures in the attitude control system of the DSCS-III satellite. The system is fully implemented in a combination of Lisp and PROLOG on a Symbolics 3600. The results indicate that realistic applications can be built using this approach. The performance of the diagnostic expert system after learning is equivalent to and, in some cases, better than the performance of the expert system with rules supplied by a domain expert.

By integrating syntactic and semantic processing, our parser (LAZY) is able to deterministically parse sentences which syntactically appear to be garden path sentences although native speakers do not need conscious reanalysis to understand them. LAZY comprises an extension to conceptual analysis which yields an explicit representation of syntactic information and a flexible interaction between semantic and syntactic knowledge.

An understander reading or listening to someone speak has to repeatedly solve the problem of word-meaning ambiguity, the selection of the intended meaning of a word from the set of its possible meanings. For example, the problem of pronominal reference can be considered as a choosing of the intended referent from the collection of entities which have already been mentioned or which can be inferred. Human understanders apply rules of syntax, surface semantics, general world knowledge, and various types of contextual knowledge to resolve word-sense or pronominal ambiguity as they process language. We describe a mechanism, called a cooperative word-meaning selector, which allows the computer to use various knowledge sources as it ``understands'' text. The word-meaning selector is part of a conceptual analyzer which forms the natural-language interface for a pair of multiprocess language processing systems. The first, called DSAM (distributable script applier mechanism), reads and summarizes newspaper articles making heavy reference to situational scripts. The second, ACE (academic counseling experiment), is a conversational program which automates certain parts of the academic counseling task. In each of these systems, a variety of knowledge sources, each managed by a distinct ``expert'' process, is brought to bear to enable the word-meaning selector to form the most plausible reading of a sentence containing ambiguous words.