next up previous
Next: Proof of Lemma 2 Up: Appendix A Previous: Proof of Lemma 1

Proof of Theorem 6

To avoid confusion, we call $Z'$ the value of $Z$ computed over the transformed set of examples, and $U(\vec{u})$ for $U\in \{Z, Z'\}$ and $\vec{u}\in\{\vec{v}^*,\vec{v}\}$ as the value of criterion $U$ using vector $\vec{u}$. It is simple to obtain a ``sufficient'' bound to check the theorem. We have

$\displaystyle Z(\vec{v})$ $\textstyle =$ $\displaystyle Z'(\vec{v}) - \sum_{
\begin{array}{c}
S\subseteq V\\
\vert S\ver...
...times \sum_{j\in S\backslash \{i\}} {e^{-\frac{1}{2}\vec{v}[j]}}}\right)} \:\:,$ (30)
$\displaystyle Z'(\vec{v}^*)$ $\textstyle =$ $\displaystyle Z(\vec{v}^*) + \sum_{
\begin{array}{c}
S\subseteq V\\
\vert S\ve...
...mes \sum_{j\in S\backslash \{i\}} {e^{-\frac{1}{2}\vec{v}^*[j]}}}\right)} \:\:.$ (31)

Here, $W_S$ is the sum of weights of the examples in the original set, whose vectors have ``1'' matching the elements of $S$. Note that $Z'(\vec{v}) \leq Z'(\vec{v}^*)$, since our algorithm is optimal, and we obtain

\begin{eqnarray*}
\lefteqn{Z(\vec{v})}\\
& \leq & Z(\vec{v}^*) + \sum_{
\begin...
...kslash \{i\}} {e^{-\frac{1}{2}\vec{v}[j]}}\right]}\right)} \:\:.
\end{eqnarray*}



By taking only the positive part of the right-hand side, and remarking that we get

\begin{eqnarray*}
Z(\vec{v}) & \leq & Z(\vec{v}^*) + \sum_{
\begin{array}{c}
S\s...
...< & Z(\vec{v}^*) \left(1+\left(\frac{e}{c-k}\right)\right) \:\:,
\end{eqnarray*}



as claimed.


next up previous
Next: Proof of Lemma 2 Up: Appendix A Previous: Proof of Lemma 1
2002 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.