<p>I am seeking to augment <a href="https://en.wikipedia.org/wiki/Random_forest" rel="nofollow noreferrer">random forest classification</a> using <a href="https://en.wikipedia.org/wiki/Mutual_information" rel="nofollow noreferrer">Shannon-Weaver mutual information</a> as a <a href="https://en.wikipedia.org/wiki/Metaheuristic" rel="nofollow noreferrer">metaheuristic</a> 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.</p>

<p>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) &gt; 0$ for ${kx,ky} \in K$. Additionally, we hypothesize that <a href="https://en.wikipedia.org/wiki/Multivariate_mutual_information" rel="nofollow noreferrer">multivariate mutual information</a> $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.</p>

<p>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. </p>

<p>We would then prune output data set using a fixed cutoff value, $v$, retaining only connections where $I(kx,...) &gt; 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.</p>

<p><br/>
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.</p>

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

<p>(<a href="https://stats.stackexchange.com/questions/25039/tractability-of-mutual-information-augmented-ensemble-classification-algorithms">Crossposted to Stats.SE</a>)</p>

CC BY-SA 3.0
2012-03-21T01:57:20.697Z
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
CC BY-SA 3.0
2012-03-21T02:13:01.393Z
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
CC BY-SA 3.0
2012-03-21T21:09:19.063Z
@SureshVenkat Thank you. I've done so: http://stats.stackexchange.com/questions/25039/tractability-of-mutual-information-augmented-ensemble-classification-algorithms
MrGomez
<graph-theory><co.combinatorics><machine-learning><it.information-theory><heuristics>
Tractability of mutual information-augmented ensemble classification algorithms
MrGomez
# Tractability of mutual information-augmented ensemble classification algorithms

(Asked by: username_0 on 2012-03-21)

I am seeking to augment [random forest classification](https://en.wikipedia.org/wiki/Random_forest) using [Shannon-Weaver mutual information](https://en.wikipedia.org/wiki/Mutual_information) as a [metaheuristic](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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?

([Crossposted to Stats.SE](https://stats.stackexchange.com/questions/25039/tractability-of-mutual-information-augmented-ensemble-classification-algorithms))

**Tags:** graph-theory, co.combinatorics, machine-learning, it.information-theory, heuristics

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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  
> **username_0**: @SureshVenkat Thank you. I've done so: http://stats.stackexchange.com/questions/25039/tractability-of-mutual-information-augmented-ensemble-classification-algorithms  

---

## 0 answers

