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

Optimizing $Z$ in the Setting of Schapire $\&$ Singer (1998)

In the case where each component of $\vec{v}$ is restricted to the set $\{-1,+1\}$, Schapire $\&$ Singer (1998) give a way to choose $\alpha$ to minimize $Z$ for any possible choice of $\vec{v}$ (using our notation):


$\displaystyle \alpha$ $\textstyle =$ $\displaystyle \frac{1}{2} \log\left(\frac{W^+}{W^-}\right) \:\:,$ (4)

with:
$\displaystyle W^+$ $\textstyle =$ $\displaystyle \sum_{o,k,j} {w((o,k,j))[\hspace{-0.055cm}[\vec{v}[j] - \vec{v}[k] = 2]\hspace{-0.055cm}]} \:\:,$ (5)
$\displaystyle W^-$ $\textstyle =$ $\displaystyle \sum_{o,k,j} {w((o,k,j))[\hspace{-0.055cm}[\vec{v}[j] - \vec{v}[k] = -2]\hspace{-0.055cm}]} \:\:.$ (6)

Replacing this value of $\alpha$ in eq. (2), gives the following new expression for $Z$:
$\displaystyle Z$ $\textstyle =$ $\displaystyle W^0 + 2\sqrt{W^+ W^-} \:\:,$ (7)

with $W^0=\sum_{o,k,j} {w((o,k,j))[\hspace{-0.055cm}[\vec{v}[j] - \vec{v}[k] = 0]\hspace{-0.055cm}]}$. Schapire $\&$ Singer (1998) raise the problem of minimizing $Z$ as defined in equations (2) and (7). We now show that it is polynomial.

Theorem 4   Minimizing $Z$ as defined either in equations (2), (3) or (7) is polynomial when the components of $\vec{v}_i$ are restricted to the set $\{-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}$
A rather striking result given the conjecture of Schapire $\&$ Singer (1998) is that it is the maximization of $Z$, and not its minimization, which is $NP$-Hard. While this is not the purpose of the present paper (we are interested in minimizing $Z$), we have chosen to give here a brief proof sketch of the result, which uses classical reductions from well-known $NP$-Hard problems.

Theorem 5   Maximizing $Z$ as defined either in equations (2), (3) or (7) is $NP$-Hard when the components of $\vec{v}_i$ are restricted to the set $\{-1,+1\}$.

Proof sketch: 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}$


next up previous
Next: Optimizing in our Setting Up: Calculating Rule Vectors using Previous: Calculating Rule Vectors using
2002 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.