Deterministic decision trees have difficulty in evaluating uncertainty especially for small samples. To solve this problem, we interpret the decision trees as stochastic models and consider prediction problems in the framework of Bayesian decision theory. Our models have three kinds of parameters: a tree shape, leaf parameters, and inner parameters. To make Bayesian optimal decisions, we have to calculate the posterior distribution of these parameters. Previously, two types of methods have been proposed. One marginalizes out the leaf parameters and samples the tree shape and the inner parameters by Metropolis-Hastings (MH) algorithms. The other marginalizes out both the leaf parameters and the tree shape based on a concept called meta-trees and approximates the posterior distribution for the inner parameters by a bagging-like method. In this paper, we propose a novel MH algorithm where the leaf parameters and the tree shape are marginalized out by using the meta-trees and only the inner parameters are sampled. Moreover, we update all the inner parameters simultaneously in each MH step. This algorithm accelerates the convergence and mixing of the Markov chain. We evaluate our algorithm on various benchmark datasets with other state-of-the-art methods. Further, our model provides a novel statistical evaluation of feature importance.

This study presents alternating optimization (AO) algorithms for computing$\alpha$-mutual information ($\alpha$-MI) and$\alpha$capacity based on variational characterizations of$\alpha$-MI using a reverse channel. Specifically, we derive several variational characterizations of Sibson, Arimoto, Augustin-Csiszár, and LapidothPfister MI and introduce novel AO algorithms for computing$\alpha$MI and$\alpha$-capacity; their performances for computing$\alpha$-capacity are also compared. The comparison results show that the AO algorithm based on the Sibson MI's characterization has the fastest convergence speed. A full version [1] with all proofs, explanations and more discussions is accessible at: https://arxiv.org/abs/2404.10950

The Sibson and Arimoto capacity, which are based on the Sibson and Arimoto mutual information (MI) of order α, respectively, are well-known generalizations of the channel capacity C. In this study, we derive novel alternating optimization algorithms for computing these capacities by providing new variational characterizations of the Sibson and Arimoto MI. Moreover, we prove that all iterative algorithms for computing these capacities are equivalent under appropriate conditions imposed on their initial distributions.

The problem of computing$\alpha$-capacity for$\alpha > 1$is equivalent to that of computing the correct decoding exponent. Various algorithms for computing them have been proposed, such as Arimoto and Jitsumatsu-Oohama algorithm. In this study, we propose a novel alternating optimization algorithm for computing the$\alpha$-capacity for$\alpha > 1$based on a variational characterization of the Augustin-Csiszár mutual information. A comparison of the convergence performance of these algorithms is demonstrated through numerical examples.

A private information retrieval (PIR) is an information retrieval scheme that allows a user to retrieve messages from information databases while keeping secret which one the user wants to retrieve. Sun et al. formulated the download rate and showed that there is an upper limit to it (PIR capacity). Previous construction methods for a capacity-achieving linear PIR (CALPIR) are ad hoc. We show a suffiecient condition of a CALPIR using its extended parity check matrix.