Arrow Research search

Author name cluster

Hiroki Arimura

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.

8 papers
1 author row

Possible papers

8

TCS Journal 2021 Journal Article

A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number

  • Kazuhiro Kurita
  • Kunihiro Wasa
  • Takeaki Uno
  • Hiroki Arimura

In this study, we address the independent set enumeration problem. Although several efficient enumeration algorithms and careful analyses have been proposed for maximal independent sets, no fine-grained analysis has been given for the non-maximal variant. As the main result, we propose an enumeration algorithm for the non-maximal variant that runs in O ( q ) amortized time and linear space, where q is the clique number, i. e. , the maximum size of a clique in an input graph. Note that the proposed algorithm works correctly even if the exact value of q is unknown. It is optimal for graphs with a bounded clique number, such as, triangle-free graphs, bipartite graphs, planar graphs, bounded degenerate graphs, nowhere dense graphs, and F-free graphs for any fixed graph F, where a F-free graph is a graph that has no copy of F as a subgraph. Furthermore, with a slight modification of our proposed algorithm, we can enumerate independent sets with the size at most k in the same time and space complexity. This problem is a generalization of the original problem since this is equal to the original problem if k = n.

Details DOI

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

IJCAI Conference 2017 Conference Paper

Discovering Relevance-Dependent Bicluster Structure from Relational Data

  • Iku Ohama
  • Takuya Kida
  • Hiroki Arimura

In this paper, we propose a statistical model for relevance-dependent biclustering to analyze relational data. The proposed model factorizes relational data into bicluster structure with two features: (1) each object in a cluster has a relevance value, which indicates how strongly the object relates to the cluster and (2) all clusters are related to at least one dense block. These features simplify the task of understanding the meaning of each cluster because only a few highly relevant objects need to be inspected. We introduced the Relevance-Dependent Bernoulli Distribution (R-BD) as a prior for relevance-dependent binary matrices and proposed the novel Relevance-Dependent Infinite Biclustering (R-IB) model, which automatically estimates the number of clusters. Posterior inference can be performed efficiently using a collapsed Gibbs sampler because the parameters of the R-IB model can be fully marginalized out. Experimental results show that the R-IB extracts more essential bicluster structure with better computational efficiency than conventional models. We further observed that the biclustering results obtained by R-IB facilitate interpretation of the meaning of each cluster.

PDF Details

NeurIPS Conference 2017 Conference Paper

On the Model Shrinkage Effect of Gamma Process Edge Partition Models

  • Iku Ohama
  • Issei Sato
  • Takuya Kida
  • Hiroki Arimura

The edge partition model (EPM) is a fundamental Bayesian nonparametric model for extracting an overlapping structure from binary matrix. The EPM adopts a gamma process ($\Gamma$P) prior to automatically shrink the number of active atoms. However, we empirically found that the model shrinkage of the EPM does not typically work appropriately and leads to an overfitted solution. An analysis of the expectation of the EPM's intensity function suggested that the gamma priors for the EPM hyperparameters disturb the model shrinkage effect of the internal $\Gamma$P. In order to ensure that the model shrinkage effect of the EPM works in an appropriate manner, we proposed two novel generative constructions of the EPM: CEPM incorporating constrained gamma priors, and DEPM incorporating Dirichlet priors instead of the gamma priors. Furthermore, all DEPM's model parameters including the infinite atoms of the $\Gamma$P prior could be marginalized out, and thus it was possible to derive a truly infinite DEPM (IDEPM) that can be efficiently inferred using a collapsed Gibbs sampler. We experimentally confirmed that the model shrinkage of the proposed models works well and that the IDEPM indicated state-of-the-art performance in generalization ability, link prediction accuracy, mixing efficiency, and convergence speed.

PDF Details