Author name cluster

Takuya Takagi

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers

2 author rows

AAAI Conference 2026 Conference Paper

I-CAM-UV: Integrating Causal Graphs over Non-Identical Variable Sets Using Causal Additive Models with Unobserved Variables

Hirofumi Suzuki
Kentaro Kanamori
Takuya Takagi
Thong Pham
Takashi Nicholas Maeda
Shohei Shimizu

Causal discovery from observational data is a fundamental tool in various fields of science. While existing approaches are typically designed for a single dataset, we often need to handle multiple datasets with non-identical variable sets in practice. One straightforward approach is to estimate a causal graph from each dataset and construct a single causal graph by overlapping. However, this approach identifies limited causal relationships because unobserved variables in each dataset can be confounders, and some variable pairs may be unobserved in any dataset. To address this issue, we leverage Causal Additive Models with Unobserved Variables (CAM-UV) that provide causal graphs having information related to unobserved variables. We show that the ground truth causal graph has structural consistency with the information of CAM-UV on each dataset. As a result, we propose an approach named I-CAM-UV to integrate CAM-UV results by enumerating all consistent causal graphs. We also provide an efficient combinatorial search algorithm and demonstrate the usefulness of I-CAM-UV against existing methods.

PDF Details DOI

AAAI Conference 2026 Conference Paper

Sparse Additive Model Pruning for Order-Based Causal Structure Learning

Kentaro Kanamori
Hirofumi Suzuki
Takuya Takagi

Causal structure learning, also known as causal discovery, aims to estimate causal relationships between variables as a form of a causal directed acyclic graph (DAG) from observational data. One of the major frameworks is the order-based approach that first estimates a topological order of the underlying DAG and then prunes spurious edges from the fully-connected DAG induced by the estimated topological order. Previous studies often focus on the former ordering step because it can dramatically reduce the search space of DAGs. In practice, the latter pruning step is equally crucial for ensuring both computational efficiency and estimation accuracy. Most existing methods employ a pruning technique based on generalized additive models and hypothesis testing, commonly known as CAM-pruning. However, this approach can be a computational bottleneck as it requires repeatedly fitting additive models for all variables. Furthermore, it may harm estimation quality due to multiple testing. To address these issues, we introduce a new pruning method based on sparse additive models, which enables direct pruning of redundant edges without relying on hypothesis testing. We propose an efficient algorithm for learning sparse additive models by combining the randomized tree embedding technique with group-wise sparse regression. Experimental results on both synthetic and real datasets demonstrated that our method is significantly faster than existing pruning methods while maintaining comparable or superior accuracy.

PDF Details DOI

ICML Conference 2025 Conference Paper

Algorithmic Recourse for Long-Term Improvement

Kentaro Kanamori
Ken Kobayashi
Satoshi Hara 0001
Takuya Takagi

Algorithmic recourse aims to provide a recourse action for altering an unfavorable prediction given by a model into a favorable one (e. g. , loan approval). In practice, it is also desirable to ensure that an action makes the real-world outcome better (e. g. , loan repayment). We call this requirement improvement. Unfortunately, existing methods cannot ensure improvement unless we know the true oracle. To address this issue, we propose a framework for suggesting improvement-oriented actions from a long-term perspective. Specifically, we introduce a new online learning task of assigning actions to a given sequence of instances. We assume that we can observe delayed feedback on whether the past suggested action achieved improvement. Using the feedback, we estimate an action that can achieve improvement for each instance. To solve this task, we propose two approaches based on contextual linear bandit and contextual Bayesian optimization. Experimental results demonstrated that our approaches could assign improvement-oriented actions to more instances than the existing methods.

Details

NeurIPS Conference 2025 Conference Paper

Learning Gradient Boosted Decision Trees with Algorithmic Recourse

Kentaro Kanamori
Ken Kobayashi
Takuya Takagi

This paper proposes a new algorithm for learning gradient boosted decision trees while ensuring the existence of recourse actions. Algorithmic recourse aims to provide a recourse action for altering the undesired prediction result given by a model. While existing studies often focus on extracting valid and executable actions from a given learned model, such reasonable actions do not always exist for models optimized solely for predictive accuracy. To address this issue, recent studies proposed a framework for learning a model while guaranteeing the existence of reasonable actions with high probability. However, these methods can not be applied to gradient boosted decision trees, which are renowned as one of the most popular models for tabular datasets. We propose an efficient gradient boosting algorithm that takes recourse guarantee into account, while maintaining the same time complexity as the standard ones. We also propose a post-processing method for refining a learned model under the constraint of a recourse guarantee and provide a PAC-style analysis of the refined model. Experimental results demonstrated that our method successfully provided reasonable actions to more instances than the baselines without significantly degrading accuracy and computational efficiency.

PDF Details

ICML Conference 2024 Conference Paper

Learning Decision Trees and Forests with Algorithmic Recourse

Kentaro Kanamori
Takuya Takagi
Ken Kobayashi
Yuichi Ike

This paper proposes a new algorithm for learning accurate tree-based models while ensuring the existence of recourse actions. Algorithmic Recourse (AR) aims to provide a recourse action for altering the undesired prediction result given by a model. Typical AR methods provide a reasonable action by solving an optimization task of minimizing the required effort among executable actions. In practice, however, such actions do not always exist for models optimized only for predictive performance. To alleviate this issue, we formulate the task of learning an accurate classification tree under the constraint of ensuring the existence of reasonable actions for as many instances as possible. Then, we propose an efficient top-down greedy algorithm by leveraging the adversarial training techniques. We also show that our proposed algorithm can be applied to the random forest, which is known as a popular framework for learning tree ensembles. Experimental results demonstrated that our method successfully provided reasonable actions to more instances than the baselines without significantly degrading accuracy and computational efficiency.

Details

TCS Journal 2024 Journal Article

Linear time online algorithms for constructing linear-size suffix trie

Diptarama Hendrian
Takuya Takagi
Shunsuke Inenaga
Keisuke Goto
Mitsuru Funakoshi

The suffix trees are fundamental data structures for various kinds of string processing. The suffix tree of a text string T of length n has O ( n ) nodes and edges, and the string label of each edge is encoded by a pair of positions in T. Thus, even after the tree is built, the input string T needs to be kept stored and random access to T is still needed. The linear-size suffix tries (LSTs), proposed by Crochemore et al. [Linear-size suffix tries, TCS 638: 171-178, 2016], are a “stand-alone” alternative to the suffix trees. Namely, the LST of an input text string T of length n occupies O ( n ) total space, and supports pattern matching and other tasks with the same efficiency as the suffix tree without the need to store the input text string T. Crochemore et al. proposed an offline algorithm which transforms the suffix tree of T into the LST of T in O ( n log ⁡ σ ) time and O ( n ) space, where σ is the alphabet size. In this paper, we present two types of online algorithms which “directly” construct the LST, from right to left, and from left to right, without constructing the suffix tree as an intermediate structure. Both algorithms construct the LST incrementally when a new symbol is read, and do not access the previously read symbols. Both of the right-to-left construction algorithm and the left-to-right construction algorithm work in O ( n log ⁡ σ ) time and O ( n ) space. The main feature of our algorithms is that the input text string does not need to be stored.

Details DOI

CLeaR Conference 2022 Conference Paper

A Multivariate Causal Discovery based on Post-Nonlinear Model

Kento Uemura
Takuya Takagi
Kambayashi Takayuki
Hiroyuki Yoshida
Shohei Shimizu

Understanding causal relations of systems is a fundamental problem in science. The study of causal discovery aims to infer the underlying causal structure from uncontrolled observational samples. One major approach is to assume that causal structures follow structural equation models (SEMs), such as the additive noise model (ANM) and the post-nonlinear (PNL) model, and to identify these causal structures by estimating the SEMs. Although the PNL model is the most general SEM for causal discovery, its estimation method has not been well-developed except for the bivariate case. In this paper, we propose a new causal discovery method based on the multivariate PNL model. We extend the bivariate method to estimate multi-cause PNL models and combine it with the iterative sink search scheme used for the ANM. We apply the proposed method to synthetic and real-world causal discovery problems and show its effectiveness.

PDF Details

AAAI Conference 2022 Conference Paper

Explainable and Local Correction of Classification Models Using Decision Trees

Hirofumi Suzuki
Hiroaki Iwashita
Takuya Takagi
Keisuke Goto
Yuta Fujishige
Satoshi Hara

In practical machine learning, models are frequently updated, or corrected, to adapt to new datasets. In this study, we pose two challenges to model correction. First, the effects of corrections to the end-users need to be described explicitly, similar to standard software where the corrections are described as release notes. Second, the amount of corrections need to be small so that the corrected models perform similarly to the old models. In this study, we propose the first model correction method for classification models that resolves these two challenges. Our idea is to use an additional decision tree to correct the output of the old models. Thanks to the explainability of decision trees, the corrections are describable to the end-users, which resolves the first challenge. We resolve the second challenge by incorporating the amount of corrections when training the additional decision tree so that the effects of corrections to be small. Experiments on real data confirm the effectiveness of the proposed method compared to existing correction methods.

PDF Details

NeurIPS Conference 2022 Conference Paper

Exploring the Whole Rashomon Set of Sparse Decision Trees

Rui Xin
Chudi Zhong
Zhi Chen
Takuya Takagi
Margo Seltzer
Cynthia Rudin

In any given machine learning problem, there may be many models that could explain the data almost equally well. However, most learning algorithms return only one of these models, leaving practitioners with no practical way to explore alternative models that might have desirable properties beyond what could be expressed within a loss function. The Rashomon set is the set of these all almost-optimal models. Rashomon sets can be extremely complicated, particularly for highly nonlinear function classes that allow complex interaction terms, such as decision trees. We provide the first technique for completely enumerating the Rashomon set for sparse decision trees; in fact, our work provides the first complete enumeration of any Rashomon set for a non-trivial problem with a highly nonlinear discrete function class. This allows the user an unprecedented level of control over model choice among all models that are approximately equally good. We represent the Rashomon set in a specialized data structure that supports efficient querying and sampling. We show three applications of the Rashomon set: 1) it can be used to study variable importance for the set of almost-optimal trees (as opposed to a single tree), 2) the Rashomon set for accuracy enables enumeration of the Rashomon sets for balanced accuracy and F1-score, and 3) the Rashomon set for a full dataset can be used to produce Rashomon sets constructed with only subsets of the data set. Thus, we are able to examine Rashomon sets across problems with a new lens, enabling users to choose models rather than be at the mercy of an algorithm that produces only a single model.

PDF Details

AAAI Conference 2021 Conference Paper

Ordered Counterfactual Explanation by Mixed-Integer Linear Optimization

Kentaro Kanamori
Takuya Takagi
Ken Kobayashi
Yuichi Ike
Kento Uemura
Hiroki Arimura

Post-hoc explanation methods for machine learning models have been widely used to support decision-making. One of the popular methods is Counterfactual Explanation (CE), also known as Actionable Recourse, which provides a user with a perturbation vector of features that alters the prediction result. Given a perturbation vector, a user can interpret it as an “action” for obtaining one’s desired decision result. In practice, however, showing only a perturbation vector is often insufficient for users to execute the action. The reason is that if there is an asymmetric interaction among features, such as causality, the total cost of the action is expected to depend on the order of changing features. Therefore, practical CE methods are required to provide an appropriate order of changing features in addition to a perturbation vector. For this purpose, we propose a new framework called Ordered Counterfactual Explanation (OrdCE). We introduce a new objective function that evaluates a pair of an action and an order based on feature interaction. To extract an optimal pair, we propose a mixedinteger linear optimization approach with our objective function. Numerical experiments on real datasets demonstrated the effectiveness of our OrdCE in comparison with unordered CE methods.

PDF Details

IJCAI Conference 2020 Conference Paper

DACE: Distribution-Aware Counterfactual Explanation by Mixed-Integer Linear Optimization

Kentaro Kanamori
Takuya Takagi
Ken Kobayashi
Hiroki Arimura

Counterfactual Explanation (CE) is one of the post-hoc explanation methods that provides a perturbation vector so as to alter the prediction result obtained from a classifier. Users can directly interpret the perturbation as an "action" for obtaining their desired decision results. However, an action extracted by existing methods often becomes unrealistic for users because they do not adequately care about the characteristics corresponding to the empirical data distribution such as feature-correlations and outlier risk. To suggest an executable action for users, we propose a new framework of CE for extracting an action by evaluating its reality on the empirical data distribution. The key idea of our proposed method is to define a new cost function based on the Mahalanobis' distance and the local outlier factor. Then, we propose a mixed-integer linear optimization approach to extracting an optimal action by minimizing our cost function. By experiments on real datasets, we confirm the effectiveness of our method in comparison with existing methods for CE.

PDF Details DOI

TCS Journal 2019 Journal Article

On the size of the smallest alphabet for Lyndon trees

Yuto Nakashima
Takuya Takagi
Shunsuke Inenaga
Hideo Bannai
Masayuki Takeda

We consider the problem of reverse-engineering the Lyndon tree, i. e. , given a full binary ordered tree T with n leaves as input, we are to compute a string w of length n of which Lyndon tree is isomorphic to the input tree T. Hereby we call such a string a solution string. Although the problem is easily solvable in linear time for binary alphabets and unbounded-size alphabets, it is not known how to efficiently find the smallest alphabet size for a solution string. In this paper, we show several new observations concerning this problem. Namely, we show that: 1) For any positive integer n, there exists a full binary ordered tree T with n leaves, s. t. the smallest alphabet size of a solution string for T is ⌊ n 2 ⌋ + 1. 2) For any full binary ordered tree T with n leaves, there exists a solution string w over an alphabet of size at most ⌊ n 2 ⌋ + 1. 3) For any full binary ordered tree T, there exists a solution string w over an alphabet of size at most h + 1, where h is the height of T. 4) For any complete binary ordered tree T with 2 k leaves, there exists a solution string w over an alphabet of size at most 4.

Details DOI