The importance of interpretability of machine learning models has been increasing due to emerging enterprise predictive analytics. Piecewise linear models have been actively studied to achieve both accuracy and interpretability. They often produce competitive accuracy against state-of-the-art non-linear methods. In addition, their representations (i.e., rule-based segmentation plus sparse linear formula) are often preferred by domain experts. A disadvantage of such models, however, is high computational cost for simultaneous determinations of the number of “pieces” and cardinality of each linear predictor, which has restricted their applicability to middle-scale data sets. This paper discusses an empirical study on the derivation of a distributed factorized asymptotic Bayesian (FAB) inference of learning piece-wise sparse linear models on distributed memory architectures from the original FAB inference algorithm. The distributed FAB inference solves the simultaneous model selection issue without communicating O(N) data where N is the number of training samples and achieves linear scale-out against the number of CPU cores. Experimental results demonstrate that the distributed FAB inference achieves high prediction accuracy and performance scalability with both synthetic and public benchmark data.

For data-driven decision-making, one promising approach, called predictive optimization, is to solve maximization problems i n which the objective function to be maximized is estimated from data. Predictive optimization, however, suffers from the problem of a calculated optimal solution’s being evaluated too optimistically, i.e., the value of the objective function is overestimated. This paper investigates such optimistic bias and presents two methods for correcting it. The first, which is analogous to cross-validation, successfully corrects the optimistic bias but results in underestimation of the true value. Our second method employs resampling techniques to avoid both overestimation and underestimation. We show that the second method, referred to as the parameter perturbation method, achieves asymptotically unbiased estimation. Empirical results for both artificial and real-world datasets demonstrate that our proposed approach successfully corrects the optimistic bias.

Many systems, including space satellites, cannot be upgraded or repaired easily during their missions. Simulation-based design techniques are often used to check conditions that can induce critical malfunctions in them, to ensure sufficient credibility and reliability during operation. However, critical conditions with a very low probability of occurring (e.g., 10−8 per trial) rarely appear within a tractable number of simulations. We propose herein a multicanonical Markov Chain Monte Carlo (MCMC) technique extended for the efficient search of rare but critical conditions, to significantly enhance simulation efficiency. Furthermore, we demonstrate an application of our proposed technique to an efficient search of “stray light” in a space telescope satellite.

This paper proposes a distributed factorized asymptotic Bayesian (FAB) inference of learning piece-wise sparse linear models on distributed memory architectures. The distributed FAB inference solves the simultaneous model selection issue without communicating O(N) data where N is the number of training samples and achieves linear scale-out against the number of CPU cores. It unlocks the limitation of their applicability to middle-scale data sets due to high computational cost for simultaneous determinations of the number of “pieces” and cardinality of each linear predictor. Experimental results demonstrate that the distributed FAB inference achieves high prediction accuracy and performance scalability with benchmark data.

The cardinality constraint is an intrinsic way to restrict the solution structure in many domains, for example, sparse learning, feature selection, and compressed sensing. To solve a cardinality constrained problem, the key challenge is to solve the projection onto the cardinality constraint set, which is NP-hard in general when there exist multiple overlapped cardinality constraints. In this paper, we consider the scenario where the overlapped cardinality constraints satisfy a Three-view Cardinality Structure (TVCS), which reflects the natural restriction in many applications, such as identification of gene regulatory networks and task-worker assignment problem. We cast the projection into a linear programming, and show that for TVCS, the vertex solution of this linear programming is the solution for the original projection problem. We further prove that such solution can be found with the complexity proportional to the number of variables and constraints. We finally use synthetic experiments and two interesting applications in bioinformatics and crowdsourcing to validate the proposed TVCS model and method.

This paper proposes a novel direct policy search (DPS) method with model selection for partially observed Markov decision processes (POMDPs). DPSs have been standard for learning POMDPs due to their computational efficiency and natural ability to maximize total rewards. An important open challenge for the best use of DPS methods is model selection, i.e., determination of the proper dimensionality of hidden states and complexity of policy functions, to mitigate overfitting in highly-flexible model representations of POMDPs. This paper bridges Bayesian inference and reward maximization and derives marginalized weighted log-likelihood~(MWL) for POMDPs which takes both advantages of Bayesian model selection and DPS. Then we propose factorized asymptotic Bayesian policy search (FABPS) to explore the model and the policy which maximizes MWL by expanding recently-developed factorized asymptotic Bayesian inference. Experimental results show that FABPS outperforms state-of-the-art model selection methods for POMDPs, with respect both to model selection and to expected total rewards.

The goal of price optimization is to maximize total revenue by adjusting the prices of products, on the basis of predicted sales numbers that are functions of pricing strategies. Recent advances in demand modeling using machine learning raise a new challenge in price optimization, i.e., how to manage statistical errors in estimation. In this paper, we show that uncertainty in recently-proposed prescriptive price optimization frameworks can be represented by a matrix normal distribution. For this particular uncertainty, we propose novel robust quadratic programming algorithms for conservative lower-bound maximization. We offer an asymptotic probabilistic guarantee of conservativeness of our formulation. Our experiments on both artificial and actual price data show that our robust price optimization allows users to determine best risk-return trade-offs and to explore safe, profitable price strategies.

This paper addresses a novel data science problem, prescriptive price optimization, which derives the optimal price strategy to maximize future profit/revenue on the basis of massive predictive formulas produced by machine learning. The prescriptive price optimization first builds sales forecast formulas of multiple products, on the basis of historical data, which reveal complex relationships between sales and prices, such as price elasticity of demand and cannibalization. Then, it constructs a mathematical optimization problem on the basis of those predictive formulas. We present that the optimization problem can be formulated as an instance of binary quadratic programming (BQP). Although BQP problems are NP-hard in general and computationally intractable, we propose a fast approximation algorithm using a semi-definite programming (SDP) relaxation. Our experiments on simulation and real retail datasets show that our prescriptive price optimization simultaneously derives the optimal prices of tens/hundreds products with practical computational time, that potentially improve approximately 30% of gross profit of those products.

We propose a scalable algorithm for model selection in sigmoid belief networks (SBNs), based on the factorized asymptotic Bayesian (FAB) framework. We derive the corresponding generalized factorized information criterion (gFIC) for the SBN, which is proven to be statistically consistent with the marginal log-likelihood. To capture the dependencies within hidden variables in SBNs, a recognition network is employed to model the variational distribution. The resulting algorithm, which we call FABIA, can simultaneously execute both model selection and inference by maximizing the lower bound of gFIC. On both synthetic and real data, our experiments suggest that FABIA, when compared to state-of-the-art algorithms for learning SBNs, $(i)$ produces a more concise model, thus enabling faster testing; $(ii)$ improves predictive performance; $(iii)$ accelerates convergence; and $(iv)$ prevents overfitting.

Recent growing needs for real time data analytics have increased importance of streaming model selection. Real-world streaming observations are often obtained by dynamically-changing or heterogeneous data sources, and learning machines must identify the complexities of the data generation processes on the fly without prior knowledge. This paper proposes online FAB (OFAB) inference as a general framework for streaming model selection of latent variable models. The key idea in OFAB inference is degeneration, i.e. it intentionally considers a "redundant" latent space anddynamically derives a "non-redundant" latent sub-space using a FAB-unique shrinkage mechanism on demand. By integrating the idea of stochastic variational inference, OFAB automatically and dynamically selects the best dimensionality of latent variables in a streaming and Bayesian principled manner. Empirical results on two applications, density estimation and abnormal detection, show that online FAB (OFAB) outperformed the state-of-the-art online inference methods.

This paper considers the feature selection scenario where only a few features are accessible at any time point. For example, features are generated sequentially and visible one by one. Therefore, one has to make an online decision to identify key features after all features are only scanned once or twice. The optimization based approach is a powerful tool for the online feature selection.

This paper deals with price optimization, which is to find the best pricing strategy that maximizes revenue or profit, on the basis of demand forecasting models. Though recent advances in regression technologies have made it possible to reveal price-demand relationship of a number of multiple products, most existing price optimization methods, such as mixed integer programming formulation, cannot handle tens or hundreds of products because of their high computational costs. To cope with this problem, this paper proposes a novel approach based on network flow algorithms. We reveal a connection between supermodularity of the revenue and cross elasticity of demand. On the basis of this connection, we propose an efficient algorithm that employs network flow algorithms. The proposed algorithm can handle hundreds or thousands of products, and returns an exact optimal solution under an assumption regarding cross elasticity of demand. Even in case in which the assumption does not hold, the proposed algorithm can efficiently find approximate solutions as good as can other state-of-the-art methods, as empirical results show.

Factorized information criterion (FIC) is a recently developed approximation technique for the marginal log-likelihood, which provides an automatic model selection framework for a few latent variable models (LVMs) with tractable inference algorithms. This paper reconsiders FIC and fills theoretical gaps of previous FIC studies. First, we reveal the core idea of FIC that allows generalization for a broader class of LVMs, including continuous LVMs, in contrast to previous FICs, which are applicable only to binary LVMs. Second, we investigate the model selection mechanism of the generalized FIC. Our analysis provides a formal justification of FIC as a model selection criterion for LVMs and also a systematic procedure for pruning redundant latent variables that have been removed heuristically in previous studies. Third, we provide an interpretation of FIC as a variational free energy and uncover previously-unknown their relationship. A demonstrative study on Bayesian principal component analysis is provided and numerical experiments support our theoretical results.

With a growing need to understand large-scale networks, factorial relational models, such as binary matrix factorization models (BMFs), have become important in many applications. Although BMFs have a natural capability to uncover overlapping group structures behind network data, existing inference techniques have issues of either high computational cost or lack of model selection capability, and this limits their applicability. For scalable model selection of BMFs, this paper proposes stochastic factorized asymptotic Bayesian (sFAB) inference that combines concepts in two recently-developed techniques: stochastic variational inference (SVI) and FAB inference. sFAB is a highly-efficient algorithm, having both scalability and an inherent model selection capability in a single inference framework. Empirical results show the superiority of sFAB/BMF in both accuracy and scalability over state-of-the-art inference methods for overlapping relational models.

Model interpretability has been recognized to play a key role in practical data mining. Interpretable models provide significant insights on data and model behaviors and may convince end-users to employ certain models. In return for these advantages, however, there is generally a sacrifice in accuracy, i.e., flexibility of model representation (e.g., linear, rule-based, etc.) and model complexity needs to be restricted in order for users to be able to understand the results. This paper proposes oblique treed sparse additive models (OT-SpAMs). Our main focus is on developing a model which sacrifices a certain degree of interpretability for accuracy but achieves entirely sufficient accuracy with such fully non-linear models as kernel support vector machines (SVMs). OT-SpAMs are instances of region-specific predictive models. They divide feature spaces into regions with sparse oblique tree splitting and assign local sparse additive experts to individual regions. In order to maintain OT-SpAM interpretability, we have to keep the overall model structure simple, and this produces simultaneous model selection issues for sparse oblique region structures and sparse local experts. We address this problem by extending factorized asymptotic Bayesian inference. We demonstrate, on simulation, benchmark, and real world datasets that, in terms of accuracy, OT-SpAMs outperform state-of-the-art interpretable models and perform competitively with kernel SVMs, while still providing results that are highly understandable.

MOTIVATION: Recent studies have suggested that both the genome and the genome with epigenetic modifications, the so-called epigenome, play important roles in various biological functions, such as transcription and DNA replication, repair, and recombination. It is well known that specific combinations of histone modifications (e.g. methylations and acetylations) of nucleosomes induce chromatin states that correspond to specific functions of chromatin. Although the advent of next-generation sequencing (NGS) technologies enables measurement of epigenetic information for entire genomes at high-resolution, the variety of chromatin states has not been completely characterized. RESULTS: In this study, we propose a method to estimate the chromatin states indicated by genome-wide chromatin marks identified by NGS technologies. The proposed method automatically estimates the number of chromatin states and characterize each state on the basis of a hidden Markov model (HMM) in combination with a recently proposed model selection technique, factorized information criteria. The method is expected to provide an unbiased model because it relies on only two adjustable parameters and avoids heuristic procedures as much as possible. Computational experiments with simulated datasets show that our method automatically learns an appropriate model, even in cases where methods that rely on Bayesian information criteria fail to learn the model structures. In addition, we comprehensively compare our method to ChromHMM on three real datasets and show that our method estimates more chromatin states than ChromHMM for those datasets.

Piecewise linear models (PLMs) have been widely used in many enterprise machine learning problems, which assign linear experts to individual partitions on feature spaces and express whole models as patches of local experts. This paper addresses simultaneous model selection issues of PLMs; partition structure determination and feature selection of individual experts. Our contributions are mainly three-fold. First, we extend factorized asymptotic Bayesian (FAB) inference for hierarchical mixtures of experts (probabilistic PLMs). FAB inference offers penalty terms w.r.t. partition and expert complexities, and enable us to resolve the model selection issue. Second, we propose posterior optimization which significantly improves predictive accuracy. Roughly speaking, our new posterior optimization mitigates accuracy degradation due to a gap between marginal log-likelihood maximization and predictive accuracy. Third, we present an application of energy demand forecasting as well as benchmark comparisons. The experiments show our capability of acquiring compact and highly-accurate models.

We consider forward-backward greedy algorithms for solving sparse feature selection problems with general convex smooth functions. A state-of-the-art greedy method, the Forward-Backward greedy algorithm (FoBa-obj) requires to solve a large number of optimization problems, thus it is not scalable for large-size problems. The FoBa-gdt algorithm, which uses the gradient information for feature selection at each forward iteration, significantly improves the efficiency of FoBa-obj. In this paper, we systematically analyze the theoretical properties of both algorithms. Our main contributions are: 1) We derive better theoretical bounds than existing analyses regarding FoBa-obj for general smooth convex functions; 2) We show that FoBa-gdt achieves the same theoretical performance as FoBa-obj under the same condition: restricted strong convexity condition. Our new bounds are consistent with the bounds of a special case (least squares) and fills a previously existing theoretical gap for general convex smooth functions; 3) We show that the restricted strong convexity condition is satisfied if the number of independent samples is more than \bark\log d where \bark is the sparsity number and d is the dimension of the variable; 4) We apply FoBa-gdt (with the conditional random field objective) to the sensor selection problem for human indoor activity recognition and our results show that FoBa-gdt outperforms other methods based on forward greedy selection and L1-regularization.

Multidimensional data visualization is an important research topic that has been receiving increasing attention. Several techniques that use parallel coordinate plots have been proposed to represent all dimensions of data in a single display space. In addition, several other techniques that apply scatter plot matrices have been proposed to represent multidimensional data as a collection of low-dimensional data visualization spaces. Typically, when using the latter approach it is easier to understand relations among particular dimensions, but it is often difficult to observe relations between dimensions separated into different visualization spaces. This paper presents a framework for displaying an arrangement of low-dimensional data visualization spaces that are generated from high-dimensional datasets. Our proposed technique first divides the dimensions of the input datasets into groups of lower dimensions based on their correlations or other relationships. If the groups of lower dimensions can be visualized in independent rectangular spaces, our technique packs the set of low-dimensional data visualizations into a single display space. Because our technique places relevant low-dimensions closer together in the display space, it is easier to visually compare relevant sets of low-dimensional data visualizations. In this paper, we describe in detail how we implement our framework using parallel coordinate plots, and present several results demonstrating its effectiveness.

This paper extends factorized asymptotic Bayesian (FAB) inference for latent feature models~(LFMs). FAB inference has not been applicable to models, including LFMs, without a specific condition on the Hesqsian matrix of a complete log-likelihood, which is required to derive a factorized information criterion''~(FIC). Our asymptotic analysis of the Hessian matrix of LFMs shows that FIC of LFMs has the same form as those of mixture models. FAB/LFMs have several desirable properties (e.g., automatic hidden states selection and parameter identifiability) and empirically perform better than state-of-the-art Indian Buffet processes in terms of model selection, prediction, and computational efficiency."

This paper proposes an online mixture modeling methodology in which individual components can have different marginal distributions and dependency structures. Mixture models have been widely studied and applied to various application areas, including density estimation, fraud/failure detection, image segmentation, etc. Previous research has been almost exclusively focused on mixture models having components of a single type (e.g., a Gaussian mixture model.) However, recent growing needs for complicated data modeling necessitate the use of more flexible mixture models (e.g., a mixture of a lognormal distribution for medical costs and a Gaussian distribution for blood pressure, for medical analytics.) Our key ideas include: 1) separating marginal distributions and their dependencies using copulas and 2) online extension of a recently-developed "expectation minimization of description length," which enable us to efficiently learn types of both marginal distributions and copulas as well as their parameters. The proposed method provides not only good performance in applications, but also scalable, automatic model selection, which greatly reduces the intensive modeling costs in data mining processes. We show that the proposed method outperforms state-of-the-art methods in application to density estimation and to anomaly detection.

This paper addresses the issue of unsupervised network anomaly detection. In recent years, networks have played more and more critical roles. Since their outages cause serious economic losses, it is quite significant to monitor their changes over time and to detect anomalies as early as possible. In this paper, we specifically focus on the management of the whole network. In it, it is important to detect anomalies which make great impact on the whole network, and the other local anomalies should be ignored. Further, when we detect the former anomalies, it is required to localize nodes responsible for them. It is challenging to simultaneously perform the above two tasks taking into account the nonstationarity and strong correlations between nodes.

We address the issue of classification problems in the following situation: test data include data belonging to unlearned classes. To address this issue, most previous works have taken two-stage strategies where unclear data are detected using an anomaly detection algorithm in the first stage while the rest of data are classified into learned classes using a classification algorithm in the second stage. In this study, we propose anomaly detection support vector machine (ADSVM) which unifies classification and anomaly detection. ADSVM is unique in comparison with the previous work in that it addresses the two problems simultaneously. We also propose a multiclass extension of ADSVM that uses a pairwise voting strategy. We empirically present that ADSVM outperforms two-stage algorithms in application to an real automobile fault dataset, as well as to UCI benchmark datasets.

Although Subsequence Time Series (STS) clustering is one of the most popular pattern discovery techniques from time-series data, a mathematical methodology for analyzing STS clustering (or pattern discovery from time-series data) has attracted little attention. In the situation, it has had a surprising report [10] that cluster centers obtained using STS clustering closely resemble “sine waves” with little relation to input time-series data. With this report as a start, establishment of the methodology has been recognized as a significant issue. The contributions of this paper are mainly two folds. 1) We give, for the first time, a theoretical analysis of Subsequence Time Series (STS) clustering from a frequency-analysis viewpoint and identify a mathematical background on which STS clustering generates sine wave patterns. This also gives a novel theoretical analysis methodology for pattern discovery from time-series data, and 2) we propose a clustering algorithm using a phase alignment preprocessing to avoid sine-wave patterns and refer to it as Phase Alignment STS (PA-STS) clustering. PA-STS clustering is the first algorithm, which is based on theoretical analysis, to obtain meaningful clustering results. We present experimental results that show the reliability of the theoretical results and the effectiveness of PA-STS clustering in application to UCR datasets.

We address the issue of detecting fault events in multivariate time series. We suppose the following realistic situation: A) the features to which multivariate time series correspond are heterogeneous; B) relative to a large number of normal examples, only a small number of examples of fault events are available in advance; and C) many features irrelevant to fault events are included. In such a situation, we require real-time, high-accuracy processing. We propose an algorithm to resolve the issue. Key ideas in it include: 1) transforming the time-series for each feature into a sequence of anomaly scores, in order to map heterogeneous features to homogeneous features (an anomaly score indicates the degree of anomaly relative to an ordinal sequence) and then representing the pattern of a fault event in terms of anomaly score vectors; 2) selecting features specifying a fault event by means of iterative optimization using both normal and fault anomaly score vectors. We then monitor the degree of abnormal with regard to test anomaly score vectors by matching with the abnormal patterns. We demonstrate the effectiveness of our proposed algorithm through an application to an actual automobile fault diagnosis data set.

Development of advanced anomaly detection and failure diagnosis technologies for spacecraft is a quite significant issue in the space industry, because the space environment is harsh, distant and uncertain. While several modern approaches based on qualitative reasoning, expert systems, and probabilistic reasoning have been developed recently for this purpose, any of them has a common difficulty in obtaining accurate and complete a priori knowledge on the space systems from human experts. A reasonable alternative to this conventional anomaly detection method is to reuse a vast amount of telemetry data which is multi-dimensional time-series continuously produced from a number of system components in the spacecraft.This paper proposes a novel "knowledge-free" anomaly detection method for spacecraft based on Kernel Feature Space and directional distribution, which constructs a system behavior model from the past normal telemetry data from a set of telemetry data in normal operation and monitors the current system status by checking incoming data with the model.In this method, we regard anomaly phenomena as unexpected changes of causal associations in the spacecraft system, and hypothesize that the significant causal associations inside the system will appear in the form of principal component directions in a high-dimensional non-linear feature space which is constructed by a kernel function and a set of data.We have confirmed the effectiveness of the proposed anomaly detection method by applying it to the telemetry data obtained from a simulator of an orbital transfer vehicle designed to make a rendezvous maneuver with the International Space Station.