We demonstrate DBxAI, a system for explaining predictions of arbitrary machine learning models even if model owners opt not to, giving the right-to-explanation to model users as requested by GDPR. The enabling idea of DBxAI is to accumulate prediction histories at the client side during model serving, by collecting inference instances and predictions as a database. DBxAI then deduces explanations by using this database, without the need for any coordination from model owners. Using real-world traces, we demonstrate that, by retrieving different contexts from the database, DBxAI explanations are contextual, accurate, and orders of magnitude faster to compute than existing explainers that are developed for and operated by model owners.

While counterfactuals have been extensively studied as an intuitive explanation of model predictions, they still have limited adoption in practice due to two obstacles: (a) They rely on excessive access to the model for explanation that the model owner may not provide; and (b) counterfactuals carry information that adversarial users can exploit to launch model extraction attacks. To address the challenges, we propose CPC, a data-driven approach to counterfactual. CPC works at the client side and gives full control and right-to-explain to model users, even when model owners opt not to. Moreover, CPC warrants that adversarial users cannot exploit counterfactuals to extract models. We formulate properties and fundamental problems underlying CPC, study their complexity and develop effective algorithms. Using real-world datasets and user study, we verify that CPC does prevent adversaries from exploiting counterfactuals for model extraction attacks, and is orders of magnitude faster than existing explainers, while maintaining comparable and often higher quality.

Formal feature explanations strictly maintain perfect conformity but are intractable to compute, while heuristic methods are much faster but can lead to problematic explanations due to lack of conformity guarantees. We propose relative keys that have the best of both worlds. Relative keys associate feature explanations with a set of instances as context, and warrant perfect conformity over the context as formal explanations do, whilst being orders of magnitudes faster and working for complex blackbox models. Based on it, we develop CCE, a prototype that computes explanations with provably bounded conformity and succinctness, without accessing the models. We show that computing the most succinct relative keys is NP-complete and develop various algorithms for it under the batch and online models. Using 9 real-life datasets and 7 state-of-the-art explanation methods, we demonstrate that CCE explains cases where existing methods cannot, and provides more succinct explanations with perfect conformity for cases they can; moreover, it is 2 orders of magnitude faster.

This paper studies cache policies for transactional caches. Different from conventional caches that focus on latency, transactional caches are primarily used to augment database systems and improve their transaction throughput by offloading read load onto the cache. A read transaction commits on the cache only if it is a consistent cache hit, i.e., all of its reads see a consistent view of the database. We prove that conventional cache policies are not competitive for transactions. We then show that for the large class of batching-based transaction systems, one can break the theoretical performance barrier of conventional cache policies via transaction consistency aware cache policies, although it is NP-complete to find the optimal ones. As a proof, we develop a consistent cache policy that is theoretically competitive under common cache schemes. To further exploit batching, we propose to reorder transactions within batches while guaranteeing that each transaction sees data values with bounded staleness. Using benchmarks and real-life workloads, we experimentally verify that our policy improves the transaction throughput of Memcached atop HBase by 126.95% on average, up to 479.27% higher than existing cache policies adopted for transactions.

We propose monotonic consistent caching (MCC), a cache scheme for applications that demand consistency and monotonicity. MCC warrants that a transaction-like request always sees a consistent view of the backend database and observed writes over the cache will not be lost. We show that the complexity of MCC ranges from P time to N p -C omplete . We characterize MCC via a notion of obsolete items, based on which we abstract a principle for designing competitive MCC policies. By applying the principle, we develop an optimal MCC policy for the batch model, where requests in a batch are known in advance. For the online and semi-online models, we develop ML-augmented policies that benefit from blackbox ML models for classifying obsolete items, while being provably competitive even if the ML is arbitrarily bad. Using benchmark and real-life traces, we show that MCC policies reduce 39.09% of database reads for Redis atop HBase and improve their throughput by 77.15%.

Multi-label feature selection focuses on constructing a reduced feature space for discriminating multi-label instances. In consideration of the complex structures of label and feature spaces, a critical issue that explicitly determines selection performance is how to induce consistent information from both spaces to steer feature selection. Existing approaches tackle this issue in various spatial-aware views, without sufficient consideration of the negative effects of irrelevant features and imbalanced neighbors on inferring space structure. Inspired by the superiority of margin theory in assessing reliable space structure, we approach multi-label feature selection in the learning framework of preserving label-feature space consistency through probabilistic margin in this paper. In contrast to existing approaches, our model assesses the weighted margin based on the probabilistic nearest neighbors, and preserves consistent margin information in label and feature spaces. In this manner, label-feature space consistency is elegantly achieved, which conduces to effectively capturing discriminative features suitable for multi-label learning tasks and eliminating noisy features. Experimental results on multi-label data sets demonstrate the encouraging performance of the proposed model.

Semi-supervised learning and multi-label learning pose different challenges for feature selection, which is one of the core techniques for dimension reduction, and the exploration of reducing feature space for multi-label learning with incomplete label information is far from satisfactory. Existing feature selection approaches devote attention to either of two issues, namely, alleviating negative effects of imperfectly predicted labels and quantitatively evaluating label correlations, exclusively for semi-supervised or multi-label scenarios. A unified framework to extract label correlation information with incomplete prior knowledge and embed this information in feature selection however, is rarely touched. In this paper, we propose a space consistency-based feature selection model to address this issue. Specifically, correlation information in feature space is learned based on the probabilistic neighborhood similarities, and correlation information in label space is optimized by preserving feature-label space consistency. This mechanism contributes to appropriately extracting label information in semi-supervised multi-label learning scenario and effectively employing this information to select discriminative features. An extensive experimental evaluation on real-world data shows the superiority of the proposed approach under various evaluation metrics.

Selecting functional genes is essential for analyzing microarray data. Among many available feature (gene) selection approaches, the ones on the basis of the large margin nearest neighbor receive more attention due to their low computational costs and high accuracies in analyzing the high-dimensional data. Yet, there still exist some problems that hamper the existing approaches in sifting real target genes, including selecting erroneous nearest neighbors, high sensitivity to irrelevant genes, and inappropriate evaluation criteria. Previous pioneer works have partly addressed some of the problems, but none of them are capable of solving these problems simultaneously. In this paper, we propose a new local-nearest-neighbors-based feature weighting approach to alleviate the above problems. The proposed approach is based on the trick of locally minimizing the within-class distances and maximizing the between-class distances with the nearest neighbors rule. We further define a feature weight vector, and construct it by minimizing the cost function with a regularization term. The proposed approach can be applied naturally to the multi-class problems and does not require extra modification. Experimental results on the UCI and the open microarray data sets validate the effectiveness and efficiency of the new approach.

Unsupervised feature selection has raised considerable interests in the past decade, due to its remarkable performance in reducing dimensionality without any prior class information. Preserving reliable locality information and achieving excellent cluster separation are two critical issues for unsupervised feature selection. However, existing methods cannot tackle two issues simultaneously. To address the problems, we propose a novel unsupervised approach that integrates sparse feature selection and robust joint clustering analysis. The joint clustering analysis seamlessly unifies the spectral clustering and the orthogonal basis clustering. Specifically, a probabilistic neighborhood graph is utilized to preserve reliable locality information in the spectral clustering, and an orthogonal basis matrix is incorporated to achieve excellent cluster separation in the orthogonal basis clustering. A compact and effective iterative algorithm is designed to optimize the proposed selection framework. Extensive experiments on both synthetic data and real-world data validate the effectiveness of our approach under various evaluation indices.