Search

In the field of decision trees, most previous studies have difficulty ensuring the statistical optimality of a prediction of new data and suffer from overfitting because trees are usually used only to represent prediction functions to be constructed from given data. In contrast, some studies, including this paper, used the trees to represent stochastic data observation processes behind given data. Moreover, they derived the statistically optimal prediction, which is robust against overfitting, based on the Bayesian decision theory by assuming a prior distribution for the trees. However, these studies still have a problem in computing this Bayes optimal prediction because it involves an infeasible summation for all division patterns of a feature space, which is represented by the trees and some parameters. In particular, an open problem is a summation with respect to combinations of division axes, i.e., the assignment of features to inner nodes of the tree. We solve this by a Markov chain Monte Carlo method, whose step size is adaptively tuned according to a posterior distribution for the trees.

We propose an algorithm for computing Stratonovich's value of information (VoI) that can be regarded as an analogue of the distortion-rate function. We construct an alternating optimization algorithm for VoI under a general information leakage constraint and derive a convergence condition. Furthermore, we discuss algorithms for computing VoI under specific information leakage constraints, such as Shannon's mutual information (MI), $f$-leakage, Arimoto's MI, Sibson's MI, and Csiszar's MI.

早大学位記番号:新9034