0
$\begingroup$

I am learning about ensemble classifiers and on a lot of websites and books, they all state the assumption that the classifiers are independent and the error rates are not correlated. The error probability is then calculated by

formula

However, is the binomial distribution the only probability distribution that can be used? Are there cases in which the binomial distribution has to be modified or even changed to another one like poisson, for example?

$\endgroup$
1
  • $\begingroup$ What's wrong with binomial? As about Poisson, binomial converges to Poisson as $n \to \infty$, so Poisson could be used to approximate binomial -- but what for since binomial is more flexible? $\endgroup$
    – Tim
    Nov 9, 2016 at 9:35

1 Answer 1

1
$\begingroup$

Theoretically, the error of an ensemble depends on the distribution of the error between the classifiers and the fusion/selection rule (e.g. early fusion, late fusion, average combination, etc).

I recommend the book "Combining Pattern Classifiers" by L. Kuncheva. The following is based on that book.

The fusion rule, or combination rule, defines the combination of the classifiers to a single output. There are two main types: Integration and Selection.

  1. Integration: for each pattern all the classifiers contribute to the final decision. This method assumes competitive classifiers.

  2. Selection: for each pattern just a single classifier is responsible for the final decision. This method assumes complementary classifiers.

It is very intuitive that fusion is only useful if the combined classifiers differ. This can be illustrated by the following worst case scenario: imagine all classifiers produce exactly the same output for a given input, i.e. they are all the same. Fusing them would not result in any improvement. The selected ensemble classifiers should have a high accuracy and high diversity. The required degree of diversity depends highly on the fusion strategy. When using integrations functions, e.g. a majority vote fusing, obviously the majority of the classifiers should always be correct. Given a selection function, there should be at least one correct classifier for each pattern.

Before we take a look at the fusion strategies, a few assumptions are made:

  1. All classifiers produce soft labels, i.e. $c_i \in [0, 1]$
  2. There are only two classes $\Omega = \{\omega_1, \omega_2 \}$.
  3. A classification error occurs if the sample $x$ has been assigned label $\omega_2$, even though the true posterior probability is $P(x \vert \omega_1) > 0.5$.
  4. The classifiers make independent errors in estimating the class label. The errors are identically distributed.

The error distribution can be determined as follows. Let $c_j$ be the output of classifier $C_j$ and $\hat{c_j} = f(c_1, \dots, c_n)$ the fused result, i.e. the estimate of $P(x \vert \omega_1)$. It follows directly, that the posterior probability for $\omega_2$ is $1 - c_j$ (assumption 2) and $P(x \vert \omega_2) = f(1 - c_1, \dots, 1 - c_n)$.

The Min/Max Fusion Rule

As the name suggests, this fusion rule approximates the posterior probability by selecting the maximum (or minimum) over $c$, i.e. $\hat{P_i} = max_{j}(c_j), \forall i \in \{1, 2\}$. Kuncheva showed that the min and the max fusion rule are identical for the two class case. The theoretical probability of an error $P_e$ is:

\begin{eqnarray} P_e = P(\epsilon_{min} + \epsilon_{max} < 1 - 2p) \\ P_e = F_s(1 - 2p), \label{eq:proberrorminmax} \end{eqnarray}

where $\epsilon_{min}$ and $\epsilon_{max}$ are the (unknown) deviations of the minimal and maximal estimated posterior probabilities, i.e. a margin of error. $F_s(t)$ is the cumulative distribution function of $s = \epsilon_{min} + \epsilon_{max}$. Kuncheva states, that for normally distributed $P_j$, the $\epsilon$ values are also normally distributed. But one can not assume that this holds also for $s$, because $\epsilon_{min}$ and $\epsilon_{max}$ are not independent. If the $P_j$ estimates are uniformly distributed, the probability density function of the midrange value $\frac{\epsilon_{min} + \epsilon_{max}}{2}$ can be computed as follows:

\begin{equation} F_s(t) = \begin{cases} \frac{1}{2} (\frac{t}{2b} + 1)^N & \textrm{if } t \in [-2b, 0] \\ 1 - \frac{1}{2} (\frac{t}{2b} + 1)^N & \textrm{if } t \in [0, 2b] \end{cases} \label{eq:cdf} \end{equation}

Where $N$ is the number of samples and $b$ is bound of the clipped uniform distribution of $P_j$. Clipping refers to setting all values outside the interval [$p - b, p + b$] to 0 or 1, respectively. With $p \geq 0.5$, it follows that $t \leq 0$ and the theoretical probability of error is then:

\begin{equation} P_e = F_s(1 - 2p) = \frac{1}{2}\left(\frac{1-2p}{2b} + 1\right)^N \label{eq:proberrorminmaxtotal} \end{equation}

The Average Fusion Rule

Using this rule, the most probable class label $\hat{P}$ is computed by averaging the $N$ responses given by the ensemble members:

\begin{equation} \hat{P} = \frac{1}{N} \sum^N_{i=1}{P_i} \label{eq:averagefusion} \end{equation}

Assuming the posterior probabilities $P_i$ are normally distributed, the theoretical probability of error is then defined as:

\begin{equation} P_e = P(\hat{P} < 0.5) = \Phi \left( \frac{\sqrt{3N} (0.5 - p)}{b} \right) \label{eq:probaverage} \end{equation}

Where $\Phi(x)$ defines the probability density function of the normal distribution, i.e. \ $\hat{P} $\textasciitilde$\mathcal{N}(p, \frac{\sigma^2}{N})$.

The Majority Fusion Rule

Assuming the correct class label is $\omega_1$, the majority fusion rule will assign that label, if at least $\frac{N + 1}{2}$ classifiers vote for $\omega_1$. It other words, the ensemble will make an error if at least $\frac{N + 1}{2}$ vote for $\omega_2$. The theoretical error probability that a single classifier is wrong, depends on the distribution. If the the posterior probabilities are normally distributed, the theoretical error can be computed as:

\begin{equation} P_e = \Phi \left( \frac{0.5 - p}{\sigma}\right) \label{eq:errornormsingle} \end{equation}

And for the uniform distribution as:

\begin{equation} P_e = \frac{0.5 - p + b}{2b} \label{eq:errorunisingle} \end{equation}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.