# Tractability of mutual information-augmented ensemble classification algorithms

I am seeking to augment random forest classification using Shannon-Weaver mutual information as a metaheuristic to partition candidate datasets. Specifically, I am trying to determine if such an approach is both tractable and offers an improved convergence time over bruteforce methods and random forest classification on its own without a major reduction in classification.

Suppose we have a collection of data sets, $K$, that contains rows $\{k1, k2, ..., kn\}$. Each of these rows carries an unknown language $L$ in the context of an unknown, uniformly-applied noise function. Our hypothesis is that at least some subset of these data rows share information: that is, for some rows, $I(kx,ky) > 0$ for ${kx,ky} \in K$. Additionally, we hypothesize that multivariate mutual information $I(kx,ky,...) \not= 0$ for some set of multivariate relations. That is, that our graph contains compositions that are more informative in the context of multiply-chained relationships, or contain some XOR-shaped relationship.

If we attempt to bruteforce this space, because mutual information is commutative, we require n-binomial-n time and space. That is to say, to compute the mutual information of all combinations within collection $D$, we require $\sum\limits_{x=1}^n\binom{n}{x}$ time, assuming for simplicity that the comparison of each row is an $O(1)$ operation.

We would then prune output data set using a fixed cutoff value, $v$, retaining only connections where $I(kx,...) > v$. We would then sort this set in descending order of the number of terms and use this to construct an undirected graph, by connecting features that share positive mutual information and forming branches when multivariate mutual information is negative.

The obvious reduction to this complexity, at an error-bound cost in robustness, is to use random forest analysis. I wish to simplify this computation further, by computing the pairspace mutual information for each pair of rows, then using a cutoff value similar to $v$, construct sets that only contain the participating nodes of each of these graphs. These sets would then be fed into our random forest classifier to determine the shape of the graphs, at an expected reduced time for convergence.

Is this approach tractable? Even if so, are there better approaches to the pruning stage of this problem?

-
This question is extremely cross-disciplinary and research level. As a result, I felt this to be the most correct StackExchange for it to live within, ousting even Stats.SE. –  MrGomez Mar 21 '12 at 1:57
It's debatable. you might get some feedback here, but it sounds like you're looking for practical experience with the heuristics, and stats.SE might be slightly better on that front. This might be one of the few instances where simultaneous cross posting isn't a bad thing –  Suresh Venkat Mar 21 '12 at 2:13
@SureshVenkat Thank you. I've done so: stats.stackexchange.com/questions/25039/… –  MrGomez Mar 21 '12 at 21:09
add comment