next up previous
Next: Pruning a DC Up: Calculating Rule Vectors using Previous: Optimizing in our Setting

Explicit Solution in the Two-Classes Case

For the sake of simplicity, rename $W_0^+=W^-$ and $W_1^+=W^+$ representing the fraction of examples from the negative and positive class respectively, satisfying $t$. The rule to choose $\vec{v}$ is the following:

Lemma 2   The following table gives the rule to choose $\vec{v}$ :
If then we choose
$ \frac{W_+}{W_-} \geq e^{\frac{3}{2}}$ $\vec{v} = (-1, +1)$
$ \sqrt{e} \leq \frac{W_+}{W_-} < e^{\frac{3}{2}}$ $\vec{v} = (-1, 0)$ or $\vec{v} = (0, +1)$
$\frac{1}{\sqrt{e}} \leq \frac{W_+}{W_-} < \sqrt{e}$ $\vec{v} = (-1, -1)$ or $\vec{v} = (0, 0)$ or $\vec{v} = (+1, +1)$
$\frac{1}{e^\frac{3}{2}} \leq \frac{W_+}{W_-} < \frac{1}{\sqrt{e}}$ $\vec{v} = (0, -1)$ or $\vec{v} = (+1, 0)$
$\frac{W_+}{W_-} < \frac{1}{e^\frac{3}{2}}$ $\vec{v} = (+1, -1)$

Proof: See the Appendix. $\hbox{\vrule width 0.8pt
\vbox to6pt{\hrule depth 0.8pt width 5.2pt
\vfill\hrule depth 0.8pt}\vrule width 0.8pt}$



2002 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.