LiNGAM determines the variable order from cause to effect using additive noise models; however, it encounters challenges with confounding factors. Previous methods retained LiNGAM's core structure while attempting to identify and miti-gate variables affected by confounding. These methods demanded substantial computational resources, irrespective of the presence of confounding, and did not guarantee the detection of all types of confounding. In contrast, this paper presents an enhancement to LiNGAM, introducing LiNGAM-MMI. This new method quantifies the extent of confounding using KL divergence and rearranges the variables to minimize its impact. LiNGAM-MMI efficiently achieves an optimal global variable order through the formulation of a shortest path problem. It processes data as efficiently as the traditional LiNGAM in scenarios without confounding and effectively addresses situations with confounding. Our experimental results indicate that LiNGAM-MMI more precisely determines the correct variable order in both scenarios with and without confounding. This article is a summary of the paper with the same title. The paper, which includes the experiments, is available at https://arxiv.org/abs/2401.16661.

We address estimating the mutual information of variables X, Y from data. In particular, we consider a procedure that generates a sequence of contingency tables of quantized variables of X, Y, estimate the mutual information value for each of the contingency tables, and choose the largest value. This method estimates the mutual information regardless of whether each of X, Y is either discrete or continuous, and it was proved that the mutual information estimate is zero if and only if X, Y are independent, with probability one, as the sample size grows (independence detection). In this paper, we prove this method's strong consistency under a mild condition after deriving a formula of the probability that the estimate is positive when X, Y are discrete and independent. We also provide a simplified proof of independence detection using the formula.

This paper considers structure learning from data with n samples of p variables, assuming that the structure is a forest, using the Chow-Liu algorithm. Specifically, for incomplete data, we construct two model selection algorithms that complete in O(p2) steps: one obtains a forest with the maximum posterior probability given the data and the other obtains a forest that converges to the true one as n increases. We show that the two forests are generally different when some values are missing. In addition, we present estimations for benchmark data sets to demonstrate that both algorithms work in realistic situations. Moreover, we derive the conditional entropy provided that no value is missing, and we evaluate the per-sample expected redundancy for the universal coding of incomplete data in terms of the number of non-missing samples.

This paper considers structure learning from incomplete data with n samples of N variables assuming that the structure is a forest using the Chow-Liu algorithm. We construct two model selection algorithms that complete in O(N2) steps: one obtains a forest with the maximum posterior probability given the data, and the other obtains a forest that converges to the true one as n increases. We show that the two forests are generally different when some values are missing. Moreover, we derive the conditional entropy given that no value is missing, and we evaluate the per-sample expected redundancy for universal coding of incomplete data in terms of the number of non-missing samples.

In the minimum description length (MDL) and Bayesian criteria, we construct description length of data zn= z1... znof length n such that the length divided by n almost converges to its entropy rate as n → ∞, assuming Ziis in a finite set A. In model selection, if we knew the true conditional probability P(zn|F) of zn∈ Angiven each F, we would choose F such that the posterior probability P(F|zn) of F given z" is maximized. But, in many situations, we use Q : An→ [0,1] such that ΣznϵAnQ(zn|F) ≤ 1 rather than P because only data znare available. In this paper, we consider an extension such that each of the attributes in data can be either discrete or continuous. The main issue is what Q is qualified to be an alternative to P in the generalized situations. We propose the condition in terms of the Radon-Nikodym derivative of P with respect to Q, and give the procedure of constructing Q in the general setting. As a result, we obtain the MDL/Bayesian criteria in a general sense.

We consider estimation of Bayesian network structures given a finite number of examples when both discrete and continuous random variables are present in a Bayesian network. It is not hard to estimate Bayesian network structures based on the MDL/Bayesian criteria if each variable takes a finite value. On the other hand, because continuous data contain infinite precisions, its posterior probability cannot be evaluated in a well defined manner. We extend the notion of the MDL/Bayesian criteria in the most general setting in terms of Radon-Nikodym derivatives, and propose a method to estimate Bayesian network structures without assuming each variable to be either discrete or continuous.

Summary form only given. We derive the most generalized universal coding and consider its application to the MDL principle.

This paper considers model selection in classification. In many applications such as pattern recognition, probabilistic inference using a Bayesian network, prediction of the next in a sequence based on a Markov chain, the conditional probability P(Y=y|X=x) of class yisinY given attribute value xisinX is utilized. By model we mean the equivalence relation in X: for x,x'isinXx~x'hArrP(Y=y|X=x)=P(Y=y|X=x'), forall yisinY. By classification we mean the number of such equivalence classes is finite. We estimate the model from n samples zn=(xi,yi)i=1nisin(XtimesY)n, using information criteria in the form empirical entropy H plus penalty term (k/2)dn(the model such that H+(k/2)dnis minimized is the estimated model), where k is the number of independent parameters in the model, and {dn}n=1infinis a real nonnegative sequence such that lim supndn/n=0. For autoregressive processes, although the definitions of H and k are different, it is known that the estimated model almost surely coincides with the true model as nrarrinfin if {dn}n=1infin>{2loglogn}n=1infin, and that it does not if {dn}n=1infinn=1infin(Hannan and Quinn). The problem whether the same property is true for classification was open. This paper solves the problem in the affirmative

We analyse the convergence of a GA when the mutation probability is low and the selection pressure is high, for arbitrary crossover types and probabilities. We succeed in mathematically proving that the stationary distribution associated with the Markov chain concentrates on uniform populations of the best individuals, as would be expected. Categories and Subject Descriptors G.1.6 [Numerical Analysis]: Optimization—simulated annealing, stochastic programming; G.3[Probability and Statistics]:

We consider coding infinite sequences of a finite alphabet. The source is defined as a set of sequences (combinatorial source). The problem is to minimize the worst asymptotic compression ratio between each sequence and its coding output among the sequences in the combinatorial source. Ryabko showed that the optimal value coincides with the Hausdorff dimension of the combinatorial source. This correspondence extends the previous work in that the input and output costs are expressed in terms of not lengths but generalized costs. The essential quantity turns out to be the Hausdorff dimension with respect to the measure associated with the input cost. We construct an asymptotically optimal coding procedure, and also show that no coding scheme can beat the lower bound.

This paper shows a theoretical property on the Markov chain of genetic algorithms: the stationary distribution focuses on the uniform population with the optimal solution as mutation and crossover probabilities go to zero and some selective pressure defined in this paper goes to infinity. Moreover, as a result, a sufficient condition for ergodicity is derived when a simulated annealing-like strategy is considered. Additionally, the uniform crossover counterpart of the Vose-Liepins formula is derived using the Markov chain model.

This paper addresses a modified version of the context tree weighting (CTW) scheme for FV noiseless universal coding. The CTW assumes that the source is some tree source. Although it is known that the computation of the CTW in coding/decoding is O(Dn), the redundancy gets worse in the case where the source is outside the tree sources. The proposed scheme deals with a more wider source class.

This paper addresses a Markov chain analysis of genetic algorithms (GAs), in particular for a variety called a modified elitist strategy. The modified elitist strategy generates the current population of M individuals by reserving the individual with the highest fitness value from the previous generation and generating M-1 individuals through a generation change. The author's analysis is based on a Markov chain: by assuming a simple GA in which the genetic operation in the generation changes is restricted to selection, crossover, and mutation, and by evaluating the eigenvalues of the transition matrix of the Markov chain, the convergence rate of the GAs is computed in terms of a mutation probability /spl mu/. In this way, the authors show the probability that the population includes the individual with the highest fitness value is lower-bounded by 1-O(|/spl lambda/*|/sup n/), |/spl lambda/*|>