This study focuses on detecting dependency changes in multivariate time series. This is a practically important issue because, for example, changes in the relationships between several stocks may lead to early warning of critical economic events. The corresponding change detection methods should be feasible for addressing high-dimensional cases online. We use the Gaussian graphical model (GGM) to represent the conditional dependencies in multivariate and reduce our issue to change detection in GGM and consider the cases with the size of the graphical model significantly larger than the sample size as high-dimensional. Although there are several studies on GGM change detection, adequately controlling the sparsity of the model to handle high-dimensional data remains a significant challenge. To address this problem, we introduce new change statistics based on the luckiness normalized maximum likelihood (LNML) code length and minimum description length (MDL) adapted for sparse modeling. We demonstrate how to efficiently calculate the LNML-based change statistics and provide a theoretical guarantee in terms of Type I and Type II error probabilities. We expand the methodology to include cases in which missing values exist. We compare the effectiveness of our methodology with that of conventional methods through experiments using synthetic and real-world datasets.

This study addresses the issue of graph generation with generative models. In particular, we are concerned with graph community augmentation problem, which refers to the problem of generating unseen or unfamiliar graphs with a new community out of the probability distribution estimated with a given graph dataset. The graph community augmentation means that the generated graphs have a new community. There is a chance of discovering an unseen but important structure of graphs with a new community, for example, in a social network such as a purchaser network. Graph community augmentation may also be helpful for generalization of data mining models in a case where it is difficult to collect real graph data enough. In fact, there are many ways to generate a new community in an existing graph. It is desirable to discover a new graph with a new community beyond the given graph while we keep the structure of the original graphs to some extent for the generated graphs to be realistic. To this end, we propose an algorithm called the graph community augmentation (GCA). The key ideas of GCA are (i) to fit Gaussian mixture model (GMM) to data points in the latent space into which the nodes in the original graph are embedded, and (ii) to add data points in the new cluster in the latent space for generating a new community based on the minimum description length (MDL) principle. We empirically demonstrate the effectiveness of GCA for generating graphs with a new community structure on synthetic and real datasets.

Abstract Graph data augmentation (GDA), which manipulates graph structure and/or attributes, has been demonstrated as an effective method for improving the generalization of graph neural networks on semi-supervised node classification. As a data augmentation technique, label preservation is critical, that is, node labels should not change after data manipulation. However, most existing methods overlook the label preservation requirements. Determining the label-preserving nature of a GDA method is highly challenging, owing to the non-Euclidean nature of the graph structure. In this study, for the first time, we formulate a label-preserving problem (LPP) in the context of GDA. The LPP is formulated as an optimization problem in which, given a fixed augmentation budget, the objective is to find an augmented graph with minimal difference in data distribution compared to the original graph. To solve the LPP problem, we propose GMMDA, a generative data augmentation (DA) method based on Gaussian mixture modeling (GMM) of a graph in a latent space. We designed a novel learning objective that jointly learns a low-dimensional graph representation and estimates the GMM. The learning is followed by sampling from the GMM, and the samples are converted back to the graph as additional nodes. To uphold label preservation, we designed a minimum description length (MDL)-based method to select a set of samples that produces the minimum shift in the data distribution captured by the GMM. Through experiments, we demonstrate that GMMDA can improve the performance of graph convolutional network on Cora , Citeseer and Pubmed by as much as $$7.75\%$$ 7.75 % , $$8.75\%$$ 8.75 % and $$5.87\%$$ 5.87 % , respectively, significantly outperforming the state-of-the-art methods.

This study addresses the issue of balancing graph summarization and graph change detection. Graph summarization compresses large-scale graphs into a smaller scale. However, the question remains: To what extent should the original graph be compressed? This problem is solved from the perspective of graph change detection, aiming to detect statistically significant changes using a stream of summary graphs. If the compression rate is extremely high, important changes can be ignored, whereas if the compression rate is extremely low, false alarms may increase with more memory. This implies that there is a trade-off between compression rate in graph summarization and accuracy in change detection. We propose a novel quantitative methodology to balance this trade-off to simultaneously realize reliable graph summarization and change detection. We introduce a probabilistic structure of hierarchical latent variable model into a graph, thereby designing a parameterized summary graph on the basis of the minimum description length principle. The parameter specifying the summary graph is then optimized so that the accuracy of change detection is guaranteed to suppress Type I error probability (probability of raising false alarms) to be less than a given confidence level. First, we provide a theoretical framework for connecting graph summarization with change detection. Then, we empirically demonstrate its effectiveness on synthetic and real datasets.

Graph data augmentation (GDA), which manipulates graph structure and/or attributes, has been demonstrated as an effective method for improving the generalization of graph neural networks on semi-supervised node classification. As a data augmentation technique, label-preservation is critical, that is, node labels should not change after data manipulation. However, most existing methods overlook the label-preservation requirements. Determining the label-preserving nature of a GDA method is highly challenging, owing to the non-Euclidean nature of the graph structure. In this study, for the first time, we formulate a label-preserving problem (LPP) in the context of GDA. The LPP is formulated as an optimization problem in which, given a fixed augmentation budget, the objective is to find an augmented graph with minimal difference in data distribution compared to the original graph. To solve the LPP problem, we propose GMMDA, a generative data augmentation (DA) method based on Gaussian mixture modeling (GMM) of a graph in a latent space. The proposed GMMDA has three phases. First, a novel objective is designed to jointly learn a low-dimensional graph representation and estimate the GMM. The learning is followed by sampling from the GMM, and then the samples are converted back to the graph as additional nodes. To uphold label preservation, we designed a minimum description length (MDL)-based method to select a set of samples that produces the minimum shift in the data distribution. Through experiments, we demonstrate that GMMDA can improve the performance of graph convolutional network on CORA, CITESEER and PUBMED by as much as 7.75% 8.75% and 5.87%, respectively, significantly outperforming the state-of-the-art methods.

Graph embedding methods are effective techniques for representing nodes and their relations in a continuous space. Several studies try to embed graphs in constant curvature manifolds such as Euclidean, hyperbolic, and spherical space. It is critical how to select the best space for the graph embedding, as well as its dimensionality. In this study, we focus on the aforementioned constant curvature manifolds and aim at the dimensionality and curvature selection from the viewpoint of statistical model selection for latent variable models. Thereafter, we introduce universal latent variables models using wrapped normal distributions, which are the extension of Gaussian distribution for Riemannian manifolds. We then propose a novel methodology using decomposed normalized maximum likelihood code-length, which is based on the minimum description length principle. We empirically demonstrated the effectiveness of our method using both artificial and real-world datasets.

Abstract Graph embedding methods are effective techniques for representing nodes and their relations in a continuous space. Specifically, the hyperbolic space is more effective than the Euclidean space for embedding graphs with tree-like structures. Thus, it is critical how to select the best dimensionality for the hyperbolic space in which a graph is embedded. This is because we cannot distinguish nodes well with dimensionality that is considerably low, whereas the embedded relations are affected by irregularities in data with excessively high dimensionality. We consider this problem from the viewpoint of statistical model selection for latent variable models. Thereafter, we propose a novel methodology for dimensionality selection based on the minimum description length principle. We aim to introduce a latent variable modeling of hyperbolic embeddings and apply the decomposed normalized maximum likelihood code-length to latent variable model selection. We empirically demonstrated the effectiveness of our method using both synthetic and real-world datasets.

The detection of network changes over time is based on identifying deviations of the network structure. The challenge mainly lies in designing a good summary or descriptor of the network structure for facilitating the measure of deviations. In particular, a network may have a huge number of nodes and edges. Moreover, there can exist complicated dependences among edges, e.g., the existence of some edges may be because of others. Therefore, it is non-trivial to measure the contribution of each node and each edge to the deviation of the entire network structure. Existing descriptors are designed to have factors less than the number of nodes and edges. They also model edge dependences, but can only achieve partial modeling. In this paper, we propose a novel type of descriptor. We first obtain node coordinates or positions in a latent space where nodes connected by edges have close positions by network embedding. Node positions are low-dimensional. More importantly, node positions can fully model edge dependences. We then design the descriptor based on random walk on the node positions. We conducted extensive experiments on synthetic datasets and three real-world datasets to demonstrate the effectiveness of our proposed change detection framework with the descriptor.

Detecting structural changes in time-series data is crucial in many applications. However, the changes in the data may appear as global structural changes that cannot be detected by conventional methods. In recent years, Topological Data Analysis (TDA) has been used to detect such global structural changes. In TDA, information on connected components or holes of data is encoded into a two-dimensional plot called a persistence diagram (PD), which can be used to detect global changes in time-series. However, only a few studies on TDA conducted change detection assuming probabilistic structure on PDs. In this paper, we introduce probability structures into PD, with which we conduct change detection on the basis of the minimum description length principle. We propose the following two methods: (1) A parametric method: We employ the Gaussian mixture model for PD modeling and then detect global changes by tracking the changes in the optimal number of mixture components. (2) A non-parametric method: We employ kernel densities for PD modeling and then detect changes by tracking changes in their global complexity. These methods not only improve the detection accuracy of global structural changes but also provide the explainability of global changes. We showcase the effectiveness of the proposed methods using synthetic data and real-world financial time-series data.

Graph embedding methods are effective techniques for representing nodes and their relations in a continuous space. Specifically, hyperbolic space is more effective for embedding graphs with tree-like structures than Euclidean one. Then it is critical how to select the best dimensionality of the hyperbolic space where a graph is embedded. This is because we cannot distinguish nodes well with too low a dimensionality, whereas the embedded relations are affected by irregularities of data with too high a dimensionality. We consider this problem from the view of statistical model selection for latent variable models. We then propose a novel methodology for dimensionality selection on the basis of the minimum description length principle. The key idea is to make the latent variable model of hyperbolic embeddings and to employ the decomposed normalized maximum likelihood code-length as an evaluation criterion. We empirically demonstrate the effectiveness of our method through synthetic and real datasets.

This study is concerned with an algorithm to detect structural change with KC in nonparametric distributions. We propose an index of the quantification of structural information for nonparametric distributions with the aim of detecting their changes in time series data. In a parametric model such as a Gaussian mixture model, the number of clusters can represent the structural information. However, the notion of structural information for modeling data nonparametrically does not exist. Herein we introduce the novel notion of kernel complexity (KC) as structural information in a nonparametric setting. The key idea of KC is to combine the information bias by the Gini index with the quantity of information measured by the normalized maximum likelihood (NML) code length. We empirically show the similarities between KC and the number of clusters in a parametric model under certain conditions. Using synthetic and real datasets, we empirically demonstrate that our framework enables us to detect the structural changes underlying the data. We use the synthetic datasets to demonstrate the usefulness of our method with some characteristic data distribution. We then use real datasets to evaluate the validity of the detected results both quantitatively and qualitatively.

Glaucoma, which can cause irreversible damage to the sight of human eyes, is conventionally diagnosed by visual field (VF) sensitivity. However, it is labor-intensive and time-consuming to measure VF. Recently, optical coherence tomography (OCT) has been adopted to measure retinal layers thickness (RT) for assisting the diagnosis because glaucoma makes structural changes to RT and it is much less costly to obtain RT. In particular, RT can assist in mainly two manners. One is to estimate a VF from an RT such that clinical doctors only need to obtain an RT of a patient and then convert it to a VF for the diagnosis. The other is to predict future VFs by utilizing both past VFs and RTs, i.e., the prediction of progression of VF over time. The two computational tasks are performed as two data mining tasks because currently there is no knowledge about the exact form of the computations involved. In this paper, we study a novel problem which is the integration of the two data mining tasks. The motivation is that both the two data mining tasks deal with transforming information from the RT domain to the VF domain such that the knowledge discovered in one task can be useful for another. The integration is non-trivial because the two tasks do not share the way of transformation. To address this issue, we design a progression-agnostic and mode-independent (PAMI) module which facilitates cross-task knowledge utilization. We empirically demonstrate that our proposed method outperforms the state-of-the-art method for the estimation by 6.33% in terms of mean of the root mean square error on a real dataset, and outperforms the state-of-the-art method for the progression prediction by 3.49% for the best case.

Abstract Multi-label learning deals with data examples which are associated with multiple class labels simultaneously. Despite the success of existing approaches to multi-label learning, there is still a problem neglected by researchers, i.e., not only are some of the values of observed labels missing, but also some of the labels are completely unobserved for the training data. We refer to the problem asmulti-label learning with missing and completely unobserved labels, and argue that it is necessary to discover these completely unobserved labels in order to mine useful knowledge and make a deeper understanding of what is behind the data. In this paper, we propose a new approach named MCUL to solve multi-label learning with Missing and Completely Unobserved Labels. We try to discover the unobserved labels of a multi-label data set with a clustering based regularization term and describe the semantic meanings of them based on the label-specific features learned by MCUL, and overcome the problem of missing labels by exploiting label correlations. The proposed method MCUL can predict both the observed and newly discovered labels simultaneously for unseen data examples. Experimental results validated over ten benchmark datasets demonstrate that the proposed method can outperform other state-of-the-art approaches on observed labels and obtain an acceptable performance on the new discovered labels as well.

Heterogeneous information network (HIN) embedding is to encode network structure into node representations with the heterogeneous semantics of different node and edge types considered. However, since each HIN may have a unique nature, e.g., a unique set of node and edge types, a model designed for one type of networks may not be applicable to or effective on another type. In this article, we thus attempt to propose a framework for HINs with arbitrary number of node and edge types. The proposed framework constructs a novel mixture-split representation of an HIN, and hence is named as MixSp. The mixture sub-representation and the split sub-representation serve as two different views of the network. Compared with existing models which only learn from the original view, MixSp thus may exploit more comprehensive information. Node representations in each view are learned by embedding the respective network structure. Moreover, the node representations are further refined through cross-view co-regularization. The framework is instantiated in three models which differ from each other in the co-regularization. Extensive experiments on three real-world datasets show MixSp outperforms several recent models in both node classification and link prediction tasks even though MixSp is not designed for a particular type of HINs.

This paper addresses the issue of detecting hierarchical changes in latent variable models (HCDL) from data streams. There are three different levels of changes for latent variable models: 1) the first level is the change in data distribution for fixed latent variables, 2) the second one is that in the distribution over latent variables, and 3) the third one is that in the number of latent variables. It is important to detect these changes because we can analyze the causes of changes by identifying which level a change comes from (change interpretability). This paper proposes an information-theoretic framework for detecting changes of the three levels in a hierarchical way. The key idea to realize it is to employ the MDL (minimum description length) change statistics for measuring the degree of change, in combination with DNML (decomposed normalized maximum likelihood) code-length calculation. We give a theoretical basis for making reliable alarms for changes. Focusing on stochastic block models, we employ synthetic and benchmark datasets to empirically demonstrate the effectiveness of our framework in terms of change interpretability as well as change detection.

Abstract We consider the class of linear predictors over all logical conjunctions of binary attributes, which we refer to as the class of combinatorial binary models (CBMs) in this paper. CBMs are of high knowledge interpretability but naïve learning of them from labeled data requires exponentially high computational cost with respect to the length of the conjunctions. On the other hand, in the case of large-scale datasets, long conjunctions are effective for learning predictors. To overcome this computational difficulty, we propose an algorithm,GRAfting for Binary datasets (GRAB), which efficiently learns CBMs within the $$L_1$$ L1 -regularized loss minimization framework. The key idea of GRAB is to adopt weighted frequent itemset mining for the most time-consuming step in the grafting algorithm, which is designed to solve large-scale $$L_1$$ L1 -RERM problems by an iterative approach. Furthermore, we experimentally showed that linear predictors of CBMs are effective in terms of prediction accuracy and knowledge discovery.

This study is concerned with the issue of detecting changes in Gaussian mixture models (GMM) from stream data. A change in a GMM implies a change in the number of clusters as well as a change in the cluster assignments. Unlike all the existing work that addresses this issue, we aim at detecting the early warning signals of changes as well as the changes themselves. To this end, we propose a novel notion of the sequential MDL change statistics (SMCS). SMCS is a real-valued index measuring the degree of change in a GMM from an information-theoretic viewpoint. This index can also be calculated sequentially every time a dataset is generated. Therefore, by tracking the changes of SMCS in real-time, we can possibly detect the early warning signals of changes in a GMM as well as its changes. We derive error probabilities for model change detection with SMCS to show that they converge to zero exponentially as sample size increases, and we derive a suitable parameter using this theorem. Furthermore, we empirically demonstrate cases where early warning signals of the changes can be successfully tracked by SMCS.

When considering a data set it is often unknown how complex it is, and hence it is difficult to assess how rich a model for the data should be. Often these choices are swept under the carpet, ignored, left to the domain expert, but in practice this is highly unsatisfactory; domain experts do not know how to set k, what prior to choose, or how many degrees of freedom is optimal any more than we do. The Minimum Description Length (MDL) principle can answer the model selection problem from an intuitively appealing and clear viewpoint of information theory and data compression. In a nutshell, it asserts that the best model is the one that best compresses both the data and that model. It does not only imply the best strategy for model selection, but also gives a unifying viewpoint of designing optimal data mining algorithms for a wide range of issues, and has been very successfully applied to a wide range of data mining tasks, ranging from pattern mining, clustering, classification, text mining, graph mining, anomaly detection, up to causal inference. In this tutorial we do not only give an introduction to the basics of model selection, show important properties of MDL-based modelling, successful examples as well as pitfalls for how to apply MDL to solve data mining problems, but also introduce advanced topics on important new concepts in modern MDL (e.g, normalized maximum likelihood (NML), sequential NML, decomposed NML, and MDL change statistics) and emerging applications in dynamic settings.

Prediction of glaucomatous visual field loss has significant clinical benefits because it can help with early detection of glaucoma as well as decision-making for treatments. Glaucomatous visual loss is conventionally captured through visual field sensitivity (VF ) measurement, which is costly and time-consuming. Thus, existing approaches mainly predict future VF utilizing limited VF data collected in the past. Recently, optical coherence tomography (OCT) has been adopted to measure retinal layers thickness (RT ) for considerably more low-cost treatment assistance. There then arises an important question in the context of ophthalmology: are RT measurements beneficial for VF prediction? In this paper, we propose a novel method to demonstrate the benefits provided by RT measurements. The challenge is management of the two heterogeneities of VF data and RT data as RT data are collected according to different clinical schedules and lie in a different space to VF data. To tackle these heterogeneities, we propose latent progression patterns (LPPs), a novel type of representations for glaucoma progression. Along with LPPs, we propose a method to transform VF series to an LPP based on matrix factorization and a method to transform RT series to an LPP based on deep neural networks. Partial VF and RT information is integrated in LPPs to provide accurate prediction. The proposed framework is named deeply-regularized latent-space linear regression (\em DLLR). We empirically demonstrate that our proposed method outperforms the state-of-the-art technique by 12% for the best case in terms of the mean of the root mean square error on a real dataset.

This paper proposes a new method for detecting the uncertainty of a latent structure. We consider the case where the latent structure of dataset changes gradually over time, with the goal of selecting the optimal model at any given time. In selecting the optimal model, we use the minimum description length (MDL) principle, specifically the normalized maximum likelihood (NML), which is the optimal code length in the sense of Shtarkov's minimax regret. To detect the uncertainty of a latent structure, the main idea proposed here is that the uncertainty of the model selection will increase at the initial stage when the model change occurs. Here, we propose a new indicator called "structural entropy (SE)", which defines model selection uncertainty based on the MDL principle. We use several models for model selection, including the clustering structures of the Gaussian mixture model and Poisson mixture model, and a time-dependent structure model such as the autoregression model. We show the behavior of the proposed indicator (SE) using an artificial dataset and a real marketing dataset.

Conventionally, glaucoma is diagnosed on the basis of visual field sensitivity (VF). However, the VF test is time-consuming, costly, and noisy. Using retinal thickness (RT) for glaucoma diagnosis is currently desirable. Thus, we propose a new methodology for estimating VF from RT in glaucomatous eyes. The key ideas are to use our new methods of pattern-based regularization (PBR) and pattern-based visualization (PBV) with convolutional neural networks (CNNs). PBR effectively conducts supervised learning of RT-VF relations in combination with unsupervised learning from non-paired VF data. We can thereby avoid overfitting of a CNN to small sized data. PBV visualizes functional correspondence between RT and VF with its nonlinearity preserved. We empirically demonstrate with real datasets that a CNN with PBR achieves the highest estimation accuracy to date and that a CNN with PBV is effective for knowledge discovery in an ophthalmological context.

This study addresses the problem of detecting change points in streaming data. Herein, we focus on detecting changes with low complexity and high accuracy to manage large-volume, high-velocity data. To this end, we propose a novel method of detecting changes via data compression, by introducing minimum description length (MDL) change statistics to an adaptive windowing regime. The time complexity of the resulting algorithm, Sequential Compression with Adaptive Windowing (SCAW), is optimal except for a logarithmic factor, and is theoretically justified through exponential upper bounds on error probabilities. Moreover, SCAW can be used to detect arbitrary types of changes by choosing an appropriate compressor. We also introduce the notion of asymptotic reliability as a criterion of change point detection algorithms, and determine SCAW's parameter using this criterion. Finally, we demonstrate the effectiveness of the proposed method in experiments using synthetic and real-world data from markets and industrial machinery.

Traffic accidents are caused by many different factors, such as the status of drivers, climate, and road conditions. Among them, we focus on risk factors derived from road facilities and connectivity relations. We collected statistics regarding these factors for risky and safe roads in Tokyo and employed supervised learning to train linear classifiers with two models: a L2-logistic regression model, and a combinatorial Boolean model. We found different aspects of traffic risk and concluded that combinatorial Boolean models are more effective to discover useful knowledge pertaining to risk.

Discovering hidden common factors from multiple different but related datasets is an important task in data mining. Probabilistic canonical correlation analysis (PCCA) is successfully used for this task, where private factors, which represent independent factors that have influence on a dataset, are modeled as well as common factors. We propose a method for estimating the latent dimensionality of PCCA, which represents the numbers of common and private factors. The dimensionality estimation is indispensable for both generalization ability and interpretability. The proposed method applies the minimum description length criterion using normalized maximum likelihood coding to PCCA in a theoretically justified manner, where PCCA is transformed to a regular model by latent variable completion. We demonstrate that the proposed method surpasses conventional methods in terms of dimensionality estimation performance.

Dense measurements of visual-field, which is necessary to detect glaucoma, is known as very costly and labor intensive. Recently, measurement of retinal-thickness can be less costly than measurement of visual-field. Thus, it is sincerely desired that the retinal-thickness could be transformed into visual-sensitivity data somehow. In this paper, we propose two novel methods to estimate the sensitivity of the visual-field with SITA-Standard mode 10-2 resolution using retinal-thickness data measured with optical coherence tomography (OCT). The first method called Affine-Structured Non-negative Matrix Factorization (ASNMF) which is able to cope with both the estimation of visual-field and the discovery of deep glaucoma knowledge. While, the second is based on Convolutional Neural Networks (CNNs) which demonstrates very high estimation performance. These methods are kinds of multi-view learning methods because they utilize visual-field and retinal thickness data simultaneously. We experimentally tested the performance of our methods from several perspectives. We found that ASNMF worked better for relatively small data size while CNNs did for relatively large data size. In addition, some clinical knowledge are discovered via ASNMF. To the best of our knowledge, this is the first paper to address the dense estimation of the visual-field based on the retinal-thickness data.

We propose a new model selection criterion based on the minimum description length principle in a name of the decomposed normalized maximum likelihood criterion. Our criterion can be applied to a large class of hierarchical latent variable models, such as the Naive Bayes models, stochastic block models and latent Dirichlet allocations, for which many conventional information criteria cannot be straightforwardly applied due to irregularity of latent variable models. Our method also has an advantage that it can be exactly evaluated without asymptotic approximation with small time complexity. Our experiments using synthetic and real data demonstrated validity of our method in terms of computational efficiency and model selection accuracy, while our criterion especially dominated the other criteria when sample size is small and when data are noisy.

Discovering a true sparse model capable of generating data is a challenging yet important problem for understanding the nature of the source of the data. A major part of the challenge arises from the fact that the number of possible sparse models grows exponentially as the dimensionality of the models increases. In this study, we consider a method for estimating the true model over an exponentially large number of sparse models based on the minimum description length principle. We show that a novel criterion derived by continuous relaxation of the stochastic complexity induces selection of the true model by solving the l1-regularization problem for which the hyperparameters are appropriately chosen. Moreover, we provide an efficient optimization algorithm for finding the appropriate hyperparameters and select the sparse model accordingly. The experimental results we obtained for the problem of sparse graphical modeling indicate that the proposed method estimates the true model effectively in comparison to existing methods for choosing hyperparameters to solve the l1-regularization problem.

In this paper we propose a novel methodology of sequential change detection using the minimum description length (MDL)-change statistics. We first introduce the MDL-change statistics as the difference between the code-lengths with change and that without change. We give a theoretical justification for its use in the scenario of hypothesis testing. In it we evaluate the error probabilities for the MDL-change detection to relate them to the information-theoretic complexities of the probabilistic models and their discrepancy measure. We then convert the MDL-change statistics into the sequential change detection algorithm. It is designed to detect gradual changes as well as abrupt changes from big stream data. We empirically demonstrate the effectiveness of the proposed method by showing that it performs better than existing algorithms for synthetic data. We also show its validity through real problems such as SQL injection detection and failure symptom detection.

We are concerned with the issue of discovering behavioral patterns on the web. When a large amount of web access logs are given, we are interested in how they are categorized and how they are related to activities in real life. In order to conduct that analysis, we develop a novel algorithm for sparse non-negative matrix factorization (SNMF), which can discover patterns of web behaviors. Although there exist a number of variants of SNMFs, our algorithm is novel in that it updates parameters in a multiplicative way with performance guaranteed, thereby works more robustly than existing ones, even when the rank of factorized matrices is large. We demonstrate the effectiveness of our algorithm using artificial data sets. We then apply our algorithm into a large scale web log data obtained from 70,000 monitors to discover meaningful relations among web behavioral patterns and real life activities. We employ the information-theoretic measure to demonstrate that our algorithm is able to extract more significant relations among web behavior patterns and real life activities than competitive methods.

A large amount of traffic-related data, including traffic statistics, accident statistics, road information, and drivers' and pedestrians' comments, is being collected through sensors and social media networks. We focus on the issue of extracting traffic risk factors from such heterogeneous data and ranking locations according to the extracted factors. In general, it is difficult to define traffic risk. We may adopt a clustering approach to identify groups of risky locations, where the risk factor is extracted by comparing the groups. Furthermore, we may utilize prior knowledge about partially ordered relations such that a specific location should be more risky than others. In this paper, we propose a novel method for traffic risk mining by unifying the clustering approach with prior knowledge with respect to order relations. Specifically, we propose the partially ordered non-negative matrix factorization (PONMF) algorithm, which is capable of clustering locations under partially ordered relations among them. The key idea is to employ the multiplicative update rule as well as the gradient descent rule for parameter estimation. Through experiments conducted using synthetic and real data sets, we show that PONMF can identify clusters that include high-risk roads and extract their risk factors.

In this paper, we propose a novel change detection method for temporal networks. In usual change detection algorithms, change scores are generated from an observed time series. When this change score reaches a threshold, an alert is raised to declare the change. Our method aggregates these change scores and alerts based on network centralities. Many types of changes in a network can be discovered from changes to the network structure. Thus, nodes and links should be monitored in order to recognize changes. However, it is difficult to focus on the appropriate nodes and links when there is little information regarding the dataset. Network centrality such as PageRank measures the importance of nodes in a network based on certain criteria. Therefore, it is natural to apply network centralities in order to improve the accuracy of change detection methods. Our analysis reveals how and when network centrality works well in terms of change detection. Based on this understanding, we propose an aggregating algorithm that emphasizes the appropriate network centralities. Our evaluation of the proposed aggregation algorithm showed highly accurate predictions for an artificial dataset and two real datasets. Our method contributes to extending the field of change detection in temporal networks by utilizing network centralities.

Convolutive non-negative matrix factorization (CNMF) is a promising method for extracting features from sequential multivariate data. Conventional algorithms for CNMF require that the structure, or the number of bases for expressing the data, be specified in advance. We are concerned with the issue of how we can select the best structure of CNMF from given data. We first introduce a framework of probabilistic modeling of CNMF and reduce this issue to statistical model selection. The problem is here that conventional model selection criteria such as AIC, BIC, MDL cannot straightforwardly be applied since the probabilistic model for CNMF is irregular in the sense that parameters are not uniquely identifiable. We overcome this problem to propose a novel criterion for best structure selection for CNMF. The key idea is to apply the technique of latent variable completion in combination with normalized maximum likelihood coding criterion under the minimum description length principle. We empirically demonstrate the effectiveness of our method using artificial and real data sets.

Non-negative matrix factorization (NMF) is one of the most important technologies in data mining. This is the task of factorizing a matrix into the product of two non-negative low rank matrices. In most of works on NMF, the rank is predetermined in ad hoc. This paper addresses the issue of how we can select the best rank from given data. The problem is that the conventional statistical model selection criteria such as AIC, MDL etc. cannot straightforwardly be applied to this issue because the regularity conditions for the criteria are not fulfilled. We overcome this problem to propose a novel methodology for rank selection. The key ideas are to 1) use the technique of latent variable completion to make the model regular and 2) then to apply the normalized maximum likelihood coding to rank selection for the regular model. We further propose a novel method for rank change detection when rank changes over time. We demonstrate the effectiveness of our methods for rank selection and rank change detection through synthetic data and real data sets.

This paper addresses the issue of detecting changes in stochastic processes. In conventional studies on change detection, it has been explored how to detect discrete changes for which the statistical models of data suddenly change. We are rather concerned with how to detect continuous changes which occurs incrementally over some successive periods. This paper gives a novel methodology for detecting continuous changes. We first define the information-theoretic measure of continuous change and prove that it is invariant with respect to the parametrization of statistical model. We then propose an efficient algorithm to detect continuous changes according to the proposed measure. We demonstrate the effectiveness of our method through the experiments using synthetic data and the applications to security and economic event detection.

Lately, a large amount of traffic-related data, such as traffic statistics, accident statistics, road information, and drivers' and pedestrians' comments, has been collected through sensors and social media networks. In this paper, we propose a novel framework for mining traffic risk from such heterogeneous data. Traffic risk refers to the possibility of traffic accidents occurring. We specifically focus on two issues: 1) predicting the number of accidents for any road and intersection and 2) clustering roads to identify the risk factors that are common to risky road clusters. We followed a unifying approach to these issues by using feature-based non-negative matrix factorization (FNMF). More specifically, we developed a new multiplicative updating FNMF algorithm capable of processing large traffic data. Using real traffic data from Tokyo, we demonstrate that our proposed algorithm is able to predict traffic risk at any location more accurately and efficiently than existing methods. A number of clusters containing high-risk roads were identified and their risk factors were characterized. Through this study we have opened a new research area of traffic risk mining.

In this paper, we propose a method to cluster the spacial patterns of the visual field in glaucoma patients to analyze the progression patterns of glaucoma. The degree of progression in the visual field of glaucoma patients can be divided into several regions by straight line boundaries, we call this specific structure Direct Product Structure in this paper. Since we can observe the direct product structure in the visual fields, we propose a bottom-up hierarchical clustering method to embed this structure into the clustering structure. In our method, according to the minimum description length (MDL) principle, we select the best cluster division so that the total code length required for encoding the data as well as the clustering structure is minimum. We can thereby select the clusters that are robust to the noise in the position of the direct product structure for clustering. We demonstrate the effectiveness of our method using an artificial dataset and a real glaucoma dataset. Our proposed method performed better than existing methods for both datasets. For the real glaucoma dataset in particular, our method discovered the characteristic progressive patterns of glaucoma as specific features of clusters. These patterns agree with clinical knowledge. Furthermore, we show that our clusters can be applied to improve the accuracy of predicting glaucoma progression. Thus, our clusters contain rich information of glaucoma, and hence can contribute to further development in glaucoma research.

In social networking services (SNSs), persistent topics are extremely rare and valuable. In this paper, we propose an algorithm for the detection of persistent topics in SNSs based on Topic Graph. A topic graph is a subgraph of the ordinary social network graph that consists of the users who shared a certain topic up to some time point. Based on the assumption that the time-evolutions of the topic graphs associated with a persistent and non-persistent topics are different, we propose to detect persistent topics by performing anomaly detection on the feature values extracted from the time-evolution of the topic graph. For anomaly detection, we use principal component analysis to capture the subspace spanned by normal (non-persistent) topics. We demonstrate our technique on a real data set we gathered from Twitter and show that it performs significantly better than a base-line method based on power law curve fitting and the linear influence model.

We consider the prediction of glaucomatous visual field loss based on patient datasets. It is critically important to predict how rapidly the disease is progressing in an individual patient. However, the number of measurements for each patient is so small that a reliable predictor cannot be constructed from the data of a single patient alone. In this paper, we propose a novel multi-task learning approach to this issue. Patient data consist of three features: patient ID, 74-dimensional visual loss values, and inspection time. We reduce the prediction problem into one of matrix completion for these features. Specifically, by assuming heterogeneity in the three features, we introduce similarity measures that reflect the unique statistical nature of the respective features to solve a specific type of matrix decomposition problem. For example, we employ Gaussian kernels as a similarity measure for visual field loss and a linear regression-type relation for the time feature. We empirically demonstrate that our proposed method works significantly better than the existing methods.

We address the issue of data fusion. Suppose that we are given two datasets, where some variables are different each other and others are the same. The goal of data fusion is to complement the missing unique variables in each dataset using the common variables. Data fusion facilitates inference over multiple independent and different datasets, which is an important data mining issues that affect many applications, such as recommendation, image reconstruction, or market analysis. In this paper, we propose a novel approach to data fusion using restricted Boltzmann machines (RBMs). In applying to data fusion, RBMs are able to model hidden patterns lying behind the two datasets with bipartite graph structure between hidden variables and observable ones. There is a bottleneck in the application of RBMs to data fusion: It is computationally expensive to learn RBMs from data with missing values. Therefore, we propose a new efficient algorithm for learning RBMs from missing data. This algorithm maximizes the lower bound on the observation likelihood, which can efficiently be computed. With benchmark datasets, we empirically demonstrate that our RBM-based data fusion method significantly outperforms existing methods in terms of complement accuracy. These results demonstrate an advantage of data fusion based on latent-variable modeling.

Detection of emerging topics is now receiving renewed interest motivated by the rapid growth of social networks. Conventional-term-frequency-based approaches may not be appropriate in this context, because the information exchanged in social-network posts include not only text but also images, URLs, and videos. We focus on emergence of topics signaled by social aspects of theses networks. Specifically, we focus on mentions of users--links between users that are generated dynamically (intentionally or unintentionally) through replies, mentions, and retweets. We propose a probability model of the mentioning behavior of a social network user, and propose to detect the emergence of a new topic from the anomalies measured through the model. Aggregating anomaly scores from hundreds of users, we show that we can detect emerging topics only based on the reply/mention relationships in social-network posts. We demonstrate our technique in several real data sets we gathered from Twitter. The experiments show that the proposed mention-anomaly-based approaches can detect new topics at least as early as text-anomaly-based approaches, and in some cases much earlier when the topic is poorly identified by the textual contents in posts.

Whereas the main interest in most existing data mining approaches has been sequence data on a single type of object, namely attribute data, real-world databases store information about multiple relationships between various classes of objects. The modeling of these general relational data (GRD) plays an important role in eliciting knowledge across multiple relations. It is not reasonable to directly apply existing modeling methods to GRD, because GRD have statistical properties that distinguish them from attribute data. In this paper, we address the issue of statistical model selection in GRD modeling. From the viewpoint of the minimum description length principle, we propose a new model selection criterion by considering the statistical properties of GRD. We employ the normalized maximum likelihood code-length as a model selection criterion, and provide an asymptotic expansion theorem for its application to GRD modeling. To demonstrate its use in a critical application, we apply our proposed criterion to the issue of model selection in relational data clustering. An experiment using artificial datasets demonstrates the effectiveness of our technique compared to other criteria, and we also present a brand analysis using real beer-purchase data.

We propose database-aware regression methods for extrapolation from few measurements in the context of quantitative prognosis. The idea is to leverage a database of patients with similar conditions to increase the effective number of samples when we train a predictive model. Applying the proposed method to a database of glaucoma patients, we were able to predict the disease condition at a future time point significantly more accurately than the conventional patient-wise linear regression approach. In fact, our prediction was 50% more accurate than the conventional approach when three or less measurements were available and with only two measurements at least as accurate as the conventional approach with six measurements. Moreover, the proposed method can provide spatially localized prediction and also the (localized) speed of progression, which are valuable for doctors in making decisions.

We are concerned with the issue of detecting changes of graph partitioning structures from a graph sequence. We call this issue GPCD(graph partitioning change detection). The graph partitioning structures may represent network communities. Hence GPCD is important in that it leads to discovery of important events which cause changes of network communities. We introduce a new algorithm for GPCD, denoted as TREE. The key ideas are: 1) we employ probabilistic trees to represent probabilistic models of graph partitioning structures. 2) We then reduce GPCD into the issue of detecting changes of trees on the basis of the minimum description length (MDL) principle. 3) By taking the cost of changes into consideration, we realize significantly less false alarm rates for change detection than the baseline method called Graph Scope. We empirically demonstrate that TREE is able to detect changes more accurately than Graph Scope.

We are concerned with the issue of tracking changes of variable dependencies from multivariate time series. Conventionally, this issue has been addressed in the batch scenario where the whole data set is given at once, and the change detection must be done in a retrospective way. This paper addresses this issue in a sequential scenario where multivariate data are sequentially input and the detection must be done in a sequential fashion. We propose a new method for sequential tracking of variable dependencies. In it we employ a Bayesian network as a representation of variable dependencies. The key ideas of our method are, 1) we extend the theory of dynamic model selection (DMS), which has been developed in the batch-learning scenario, into the sequential setting, and apply it to our issue, 2) we conduct the change detection sequentially using dynamic programming per a window where we employ the Hoeffding's bound to automatically determine the window size. We empirically demonstrate that our proposed method is able to perform change detection more efficiently than a conventional batch method. Further, we give a new framework of an application of variable dependency change detection, which we call Ad Impact Relation analysis (AIR). In it, we detect the time point when a commercial message advertisement has given an impact on the market and effectively visulaize the impact through network changes. We employ real data sets to demonstrate the validity of AIR.

We are concerned with the issue of detecting changes of clustering structures from multivariate time series. From the viewpoint of the minimum description length(MDL) principle, we propose an algorithm that tracks changes of clustering structures so that the sum of the code-length for data and that for clustering changes is minimum. Here we employ a Gaussian mixture model(GMM) as representation of clustering, and compute the code-length for data sequences using the normalized maximum likelihood (NML) coding. The proposed algorithm enables us to deal with clustering dynamics including merging, splitting, emergence, disappearance of clusters from a unifying view of the MDL principle. We empirically demonstrate using artificial data sets that our proposed method is able to detect cluster changes significantly more accurately than an existing statistical-test based method and AIC/BIC-based methods. We further use real customers' transaction data sets to demonstrate the validity of our algorithm in market analysis. We show that it is able to detect changes of customer groups, which correspond to changes of real market environments.

Detection of emerging topics are now receiving renewed interest motivated by the rapid growth of social networks. Conventional term-frequency-based approaches may not be appropriate in this context, because the information exchanged are not only texts but also images, URLs, and videos. We focus on the social aspects of theses networks. That is, the links between users that are generated dynamically intentionally or unintentionally through replies, mentions, and retweets. We propose a probability model of the mentioning behaviour of a social network user, and propose to detect the emergence of a new topic from the anomaly measured through the model. We combine the proposed mention anomaly score with a recently proposed change-point detection technique based on the Sequentially Discounting Normalized Maximum Likelihood (SDNML), or with Kleinberg's burst model. Aggregating anomaly scores from hundreds of users, we show that we can detect emerging topics only based on the reply/mention relationships in social network posts. We demonstrate our technique in a number of real data sets we gathered from Twitter. The experiments show that the proposed mention-anomaly-based approaches can detect new topics at least as early as the conventional term-frequency-based approach, and sometimes much earlier when the keyword is ill-defined.

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.

In this paper, we propose a new approach to anomaly detection by looking at the latent variable space to make the first step toward latent anomaly detection.Most conventional approaches to anomaly detection are concerned with tracking data which are largely deviated from the ordinary pattern.In this paper, we are instead concerned with the issue of how to track changes happening in the latent variable space consisting of the meta information existing behind observed data.For example, in the case of masquerade detection, the conventional task was to detect anomalous command lines related to masqueraders' malicious behaviors.Meanwhile we rather attempt to track changes of behavior patterns such as writing mails, making software, etc. which are information of more abstract level than command lines.The key ideas of the methods are: 1) constructing the model variation vector, which is introduced relative to the latent variable space, and 2) the latent anomaly detection is reduced to the issue of change-point detection for the time series that the model variation vector forms.We demonstrate through the experimental results using artificial data set and UNIX command data set that our method has significantly enhanced the accuracy of existing anomaly detection methods.

We are concerned with the issue of detecting outliers and change points from time series. In the area of data mining, there have been increased interest in these issues since outlier detection is related to fraud detection, rare event discovery, etc., while change-point detection is related to event/trend change detection, activity monitoring, etc. Although, in most previous work, outlier detection and change point detection have not been related explicitly, this paper presents a unifying framework for dealing with both of them. In this framework, a probabilistic model of time series is incrementally learned using an online discounting learning algorithm, which can track a drifting data source adaptively by forgetting out-of-date statistics gradually. A score for any given data is calculated in terms of its deviation from the learned model, with a higher score indicating a high possibility of being an outlier. By taking an average of the scores over a window of a fixed length and sliding the window, we may obtain a new time series consisting of moving-averaged scores. Change point detection is then reduced to the issue of detecting outliers in that time series. We compare the performance of our framework with those of conventional methods to demonstrate its validity through simulation and experimental applications to incidents detection in network security.

Syslog monitoring technologies have recently received vast attentions in the areas of network management and network monitoring. They are used to address a wide range of important issues including network failure symptom detection and event correlation discovery. Syslogs are intrinsically dynamic in the sense that they form a time series and that their behavior may change over time. This paper proposes a new methodology of dynamic syslog mining in order to detect failure symptoms with higher confidence and to discover sequential alarm patterns among computer devices. The key ideas of dynamic syslog mining are 1) to represent syslog behavior using a mixture of Hidden Markov Models, 2) to adaptively learn the model using an on-line discounting learning algorithm in combination with dynamic selection of the optimal number of mixture components, and 3) to give anomaly scores using universal test statistics with a dynamically optimized threshold. Using real syslog data we demonstrate the validity of our methodology in the scenarios of failure symptom detection, emerging pattern identification, and correlation discovery.

In a wide range of business areas dealing with text data streams, including CRM, knowledge management, and Web monitoring services, it is an important issue to discover topic trends and analyze their dynamics in real-time. Specifically we consider the following three tasks in topic trend analysis: 1)Topic Structure Identification; identifying what kinds of main topics exist and how important they are, 2)Topic Emergence Detection; detecting the emergence of a new topic and recognizing how it grows, 3)Topic Characterization; identifying the characteristics for each of main topics. For real topic analysis systems, we may require that these three tasks be performed in an on-line fashion rather than in a retrospective way, and be dealt with in a single framework. This paper proposes a new topic analysis framework which satisfies this requirement from a unifying viewpoint that a topic structure is modeled using a finite mixture model and that any change of a topic trend is tracked by learning the finite mixture model dynamically. In this framework we propose the usage of a time-stamp based discounting learning algorithm in order to realize real-time topic structure identification. This enables tracking the topic structure adaptively by forgetting out-of-date statistics. Further we apply the theory of dynamic model selection to detecting changes of main components in the finite mixture model in order to realize topic emergence detection. We demonstrate the effectiveness of our framework using real data collected at a help desk to show that we are able to track dynamics of topic trends in a timely fashion.

We consider the situation where a number of agents are distributed and each of them collects a data sequence generated according to an unknown probability distribution. Here each of the distributions is specified by common parameters and individual parameters e.g., a normal distribution with an identical mean and a different variance. Here we introduce a notion of an information consortium, which is a framework where the agents cannot show raw data to one another, but they like to enjoy significant information gain for estimating the respective distributions. Such an information consortium has recently received much interest in a broad range of areas including financial risk management, ubiquitous network mining, etc. In this paper we are concerned with the following three issues: 1) how to design a collaborative strategy for agents to estimate the respective distributions in the information consortium, 2) characterizing when each agent has a benefit in terms of information gain for estimating its distribution or information loss for predicting future data, and 3) charracterizing how much benefit each agent obtains. In this paper we yield a statistical formulation of information consortia and solve all of the above three problems for a general form of probability distributions. Specifically we propose a basic strategy for cooperative estimation and derive a necessary and sufficient condition for each agent to have a significant benefit.

Knowing the reputations of your own and/or competitors' products is important for marketing and customer relationship management. It is, however, very costly to collect and analyze survey data manually. This paper presents a new framework for mining product reputations on the Internet. It automatically collects people's opinions about target products from Web pages, and it uses text mining techniques to obtain the reputations of those products. On the basis of human-test samples, we generate in advance syntactic and linguistic rules to determine whether any given statement is an opinion or not, as well as whether such any opinion is positive or negative in nature. We first collect statements regarding target products using a general search engine, and then, using the rules, extract opinions

We are concerned with the issues of outlier detection and change point detection from a data stream. In the area of data mining, there have been increased interest in these issues since the former is related to fraud detection, rare event discovery, etc., while the latter is related to event/trend by change detection, activity monitoring, etc. Specifically, it is important to consider the situation where the data source is non-stationary, since the nature of data source may change over time in real applications. Although in most previous work outlier detection and change point detection have not been related explicitly, this paper presents a unifying framework for dealing with both of them on the basis of the theory of on-line learning of non-stationary time series. In this framework a probabilistic model of the data source is incrementally learned using an on-line discounting learning algorithm, which can track the changing data source adaptively by forgetting the effect of past data gradually. Then the score for any given data is calculated to measure its deviation from the learned model, with a higher score indicating a high possibility of being an outlier. Further change points in a data stream are detected by applying this scoring method into a time series of moving averaged losses for prediction using the learned model. Specifically we develop an efficient algorithms for on-line discounting learning of auto-regression models from time series data, and demonstrate the validity of our framework through simulation and experimental applications to stock market data analysis.

Surveys are an important part of marketing and customer relationship management, and open answers (i.e., answers to open questions) in particular may contain valuable information and provide an important basis for making business decisions. We have developed a text mining system that provides a new way for analyzing open answers in questionnaire data. The product is able to perform the following two functions: (A) accurate extraction of characteristics for individual analysis targets, (B) accurate extraction of the relationships among characteristics of analysis targets. In this paper, we describe the working of our text mining system. It employs two statistical learning techniques: rule analysis and Correspondence Analysis for performing the two functions. Our text mining system has already been put into use by a number of large corporations in Japan in the performance of text mining on various types of survey data, including open answers about brand images, open answers about company images, complaints about products, comments written on home pages, business reports, and help desk records. In this it has been found to be useful in forming a basis for effective business decisions.

This paper is concerned with the problem of detecting outliers from unlabeled data. In prior work we have developed SmartSifter, which is an on-line outlier detection algorithm based on unsupervised learning from data. On the basis of SmartSifter this paper yields a new framework for outlier filtering using both supervised and unsupervised learning techniques iteratively in order to make the detection process more effective and more understandable. The outline of the framework is as follows: In the first round, for an initial dataset, we run SmartSifter to give each data a score, with a high score indicating a high possibility of being an outlier. Next, giving positive labels to a number of higher scored data and negative labels to a number of lower scored data, we create labeled examples. Then we construct an outlier filtering rule by supervised learning from them. Here the rule is generated based on the principle of minimizing extended stochastic complexity. In the second round, for a new dataset, we filter the data using the constructed rule, then among the filtered data, we run SmartSifter again to evaluate the data in order to update the filtering rule. Applying of our framework to the network intrusion detection, we demonstrate that 1) it can significantly improve the accuracy of SmartSifter, and 2) outlier filtering rules can help the user to discover a general pattern of an outlier group.

Outlier detection is a fundamental issue in data mining, speci cally in fraud detection, network intrusion detection, network monitoring, etc. SmartSifter, which we abbreviate as SS, is an outlier detection engine adrressing this problem from the viewpoint of statistical learning theory. This paper provides a theoretical basis for SS and empirically demonstrates its effectiveness. SS detects outliers in an online process through the on-line unsupervised learning of a probabilistic model (using a finite mixture model) of the information source. Each time a datum is input SS employs an on-line discounting learning algorithm to learn the probabilistic model. A score is given to the datum based on the learned model, with a high score indicating a high possibility of being a statistical outlier. The novel features of SS are: 1) it is adaptive to non-stationary sources of data; 2) a score has a clear statistical/information-theoretic meaning; 3) it is computationally inexpensive; and 4) it can handle both categorical and continuous variables. An experimental application to network intrusion detection shows that SS was able to identify data with high scores that corresponded to attacks, with low computational costs. Further experimental application has identified a number of meaningful rare cases in actual health insurance pathology data from Australia's Health Insurance Commission.

We propose a new method of text classification using stochastic decision lists. A stochastic decision list is an ordered sequence of IF-THEN rules, and our method can be viewed as a rule-based method for text classification having advantages of readability and refinability of acquired knowledge. Our method is unique in that decision lists are automatically constructed on the basis of the principle of minimizing Extended Stochastic Complexity (ESC), and with it we are able to construct decision lists that have fewer errors in classification. The accuracy of classification achieved with our method appears better than or comparable to those of existing rule-based methods.