Abstract Causal discovery from observational data alone in the presence of unobserved common causes is crucial yet challenging. We categorize the causal relationship between two random variables $$X$$ and $$Y$$ into the following four categories: two direct-case cases ( $$X \rightarrow Y$$ or $$X \leftarrow Y$$ ), a case in which $$X$$ and $$Y$$ are independent, and a case in which $$X$$ and $$Y$$ are confounded by unobserved common causes $$C$$ , and aim to decide among them from observational data alone. We call this the Reichenbach problem, since this categorization is valid if the Reichenbach’s common cause principle is assumed to be true. Although many methods have been proposed to address causal structure learning in the presence of $$C$$ , they typically impose assumptions on the nature of $$C$$ that require knowledge of how unobserved confounders behave, and it is difficult to guarantee in many practical cases compared to assumptions about observed variables. In our previous study (Kobayashi et al. in: 2022 IEEE international conference on big data (Big Data). IEEE, pp 45–54, 2022), we proposed a causal discovery method without such assumptions regarding the nature of unmeasured confounders, named $${\mathbf{\mathsf{CLOUD}}}$$ , for discrete data. Building on the Reichenbach’s common cause principle, if neither the two direct-cause models nor the independence model can explain the data well, we can infer the involvement of unobserved common causes in generating $$X$$ and $$Y$$ . To realize this idea in practice, $$\mathbf{\mathsf{CLOUD}}$$ imposes structural assumptions on the direct-cause models such as additive noise models ( $$\mathbf{\mathsf{ANM}}$$ s) (Peters et al. in: Proceedings of the thirteenth international conference on artificial intelligence and statistics. JMLR workshop and conference proceedings, pp 597–604, 2010), while allowing the confounded model to represent any joint distribution on ( $$X$$ , $$Y$$ ) by placing no assumptions on $$C$$ . $$\mathbf{\mathsf{CLOUD}}$$ then employs the normalized maximum likelihood (NML) codelength (Shtar’kov in Problemy Peredachi Informatsii 23(3):3–17, 1987) as an information criterion and compares models of varying capacities. This study extends $$\mathbf{\mathsf{CLOUD}}$$ to include all data types. We provide NML formulations and theoretical guarantees for consistency in model selection for mixed and continuous cases. Through extensive experiments on both synthetic and real-world data, we demonstrated that $$\mathbf{\mathsf{CLOUD}}$$ is more effective than existing methods in inferring causal relationships.

Inference of causal structure in random variables from observed data only is a crucial science problem. This study categorizes the causal relationship between two discrete random variables into four categories, which include the case that variables have a common cause and that variables are independent in addition to two directions of the direct causality. Although several existing methods have been proposed for causal inference from a joint distribution of two discrete random variables that can select either direction of the direct causality, methods that can directly infer a causal relationship from the four categories mentioned are limited. We proposed the first method to infer a causal relationship without any assumption on the unobserved confounder in discrete data. Based on the minimum description length (MDL) principle, the proposed method calculates the code length of the observed data for each causal model and then selects a model which yields the minimum code length. We demonstrated that the proposed method is effective in detecting common causes and outperforms the existing methods in terms of the accuracy of inference using synthetic data. We further showed that the proposed method effectively detects an unobserved confounder in real-world data.

In this study, we address a learning problem of probabilistic models that represent high-order interactions among discrete attributes. To include the second-order interaction of discrete attributes, probabilistic models such as Ising models and Boltzmann machines are widely used. Both are regarded as special cases of the log-linear model on partially ordered sets (posets), which can represent not only second-order but also higher-order interactions between discrete attributes. Such a model is also known by its preferable information-geometric structure. We propose a coordinate descent method for efficient learning of the log-linear model on posets and present an information-geometric understanding of its functionality. The proposed method has no hyperparameter, whereas the standard gradient descent method requires the stepsize to be set appropriately. We theoretically and empirically show that our proposed method is faster than the gradient descent method in learning distributions by the log-linear model on posets.

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.

We study the problem of scaling Multinomial Logistic Regression (MLR) to datasets with very large number of data points in the presence of large number of classes. At a scale where neither data nor the parameters are able to fit on a single machine, we argue that simultaneous data and model parallelism (Hybrid Parallelism) is inevitable. The key challenge in achieving such a form of parallelism in MLR is the log-partition function which needs to be computed across all K classes per data point, thus making model parallelism non-trivial. To overcome this problem, we propose a reformulation of the original objective that exploits double-separability, an attractive property that naturally leads to hybrid parallelism. Our algorithm (DS-MLR) is asynchronous and completely de-centralized, requiring minimal communication across workers while keeping both data and parameter workloads partitioned. Unlike standard data parallel approaches, DS-MLR avoids bulk-synchronization by maintaining local normalization terms on each worker and accumulating them incrementally using a token-ring topology. We demonstrate the versatility of DS-MLR under various scenarios in data and model parallelism, through an empirical study consisting of real-world datasets. In particular, to demonstrate scaling via hybrid parallelism, we created a new benchmark dataset (Reddit-Full) by pre-processing 1.7 billion reddit user comments spanning the period 2007-2015. We used DS-MLR to solve an extreme multi-class classification problem of classifying 211 million data points into their corresponding subreddits. Reddit-Full is a massive data set with data occupying 228 GB and 44 billion parameters occupying 358 GB. To the best of our knowledge, no other existing methods can handle MLR in this setting.

Sparse subspace clustering (SSC) represents each data point as a sparse linear combination of other data points in the dataset. In the representation learning step SSC finds a lower dimensional representation of data points, while in the spectral clustering step data points are clustered according to the underlying subspaces. However, both steps suffer from high computational and memory complexity, preventing the application of SSC to large-scale datasets. To overcome this limitation, we introduce Selective Sampling-based Scalable Sparse Subspace Clustering (S5C) algorithm which selects subsamples based on the approximated subgradients and linearly scales with the number of data points in terms of time and memory requirements. Along with the computational advantages, we derive theoretical guarantees for the correctness of S5C. Our theoretical result presents novel contribution for SSC in the case of limited number of subsamples. Extensive experimental results demonstrate effectiveness of our approach.

At present, a large amount of traffic-related data is obtained manually and through sensors and social media, e.g., traffic statistics, accident statistics, road information, and users' comments. In this paper, we propose a novel framework for mining traffic risk from such heterogeneous data. Traffic risk refers to the possibility of occurrence of traffic accidents. Specifically, we focus on two issues: 1) predicting the number of accidents on any road or at intersection and 2) clustering roads to identify risk factors for risky road clusters. We present a unified approach for addressing these issues by means of feature-based non-negative matrix factorization (FNMF). In particular, we develop a new multiplicative update algorithm for the FNMF to handle big traffic data. Using real-traffic data in Tokyo, we demonstrate that the proposed algorithm can be used to predict traffic risk at any location more accurately and efficiently than existing methods, and that a number of clusters of risky roads can be identified and characterized by two risk factors. In summary, our work can be regarded as the first step to a new research area of traffic risk mining.

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 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.

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.

Embedding words in a vector space has gained a lot of attention in recent years.While stateof-the-art methods provide efficient computation of word similarities via a low-dimensional matrix embedding, their motivation is often left unclear.In this paper, we argue that word embedding can be naturally viewed as a ranking problem due to the ranking nature of the evaluation metrics.Then, based on this insight, we propose a novel framework Wor-dRank that efficiently estimates word representations via robust ranking, in which the attention mechanism and robustness to noise are readily achieved via the DCG-like ranking losses.The performance of WordRank is measured in word similarity and word analogy benchmarks, and the results are compared to the state-of-the-art word embedding techniques.Our algorithm is very competitive to the state-of-the-arts on large corpora, while outperforms them by a significant margin when the training set is limited (i.e., sparse and noisy).With 17 million tokens, WordRank performs almost as well as existing methods using 7.2 billion tokens on a popular word similarity benchmark.Our multi-node distributed implementation of WordRank is publicly available for general usage.

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.

We propose a new truncation framework for online supervised learning. Learning a compact predictive model in an online setting has recently attracted a great deal of attention. The combination of online learning with sparsity-inducing regularization enables faster learning with a smaller memory space than a conventional learning framework. However, a simple combination of these triggers the truncation of weights whose corresponding features rarely appear, even if these features are crucial for prediction. Furthermore, it is difficult to emphasize these features in advance while preserving the advantages of online learning. We develop an extensional truncation framework to Dual Averaging, which retains rarely occurring but informative features. Our proposed framework integrates information on all previous sub gradients of the loss functions into a regularization term. Our enhancement of a conventional L1-regularization accomplishes the automatic adjustment of each feature's truncations. This extension enables us to identify and retain rare but informative features without preprocessing. In addition, our framework achieves the same computational complexity and regret bound as standard Dual Averaging. Experiments demonstrated that our framework outperforms other sparse online learning algorithms.

Modern computer hardware offers an elaborate hierarchy of storage subsystems with different speeds, capacities, and costs associated with them. Furthermore, processors are now inherently parallel offering the execution of several diverse threads simultaneously. This paper proposes StreamSVM, the first algorithm for training linear Support Vector Machines (SVMs) which takes advantage of these properties by integrating caching with optimization. StreamSVM works by performing updates in the dual, thus obviating the need to rebalance frequently visited examples. Furthermore we trade off file I/O with data expansion on the fly by generating features on demand. This significantly increases throughput. Experiments show that StreamSVM outperforms other linear SVM solvers, including the award winning work of [38], by orders of magnitude and produces more accurate solutions within a shorter amount of time.

The Passive Aggressive framework [1] is a principled approach to online linear classification that advocates minimal weight updates i.e., the least required so that the current training instance is correctly classified. While the PA framework allows integration with different loss functions, it is yet to be combined with a multiclass loss function that penalizes every class with a score higher than the true class. We call the method of training the classifier with this loss function the Support Class Passive Aggressive Algorithm. In order to obtain a weight update formula, we solve a quadratic optimization problem by using multiple constraints and arrive at a closed-form solution. This lets us obtain a simple but effective algorithm that updates the classifier against multiple classes for which an instance is likely to be mistaken. We call them the support classes. Experiments demonstrated that our method improves the traditional PA algorithms.