%\subsection{One class SVM}

\citet{Scholkopf1}suggested a method of adapting the 
%Sch\"{o}lkopf et al \citep{Scholkopf1}suggested a method of adapting the 
SVM methodology to the one-class classification problem.

Essentially,  after transforming the feature via a kernel,
they treat the origin as the only member of the second class.
Then using ``relaxation parameters" they separate the image of the 
one class from the origin.
%Another possible approach would be to work first in the feature space,
%and assume that not only the origin is in the second class, but all
%data points ``close enough" to the origin to be considered as noise
%or outliers and also classified as not in the first class.
Then the standard two-class SVM techniques are employed.

They framed the problem in the following way:

Suppose that a dataset has a probability distribution $P$ in the
feature space.  Find a ``simple" subset $S$ of the feature space such that
the probability that a test point from $P$ lies outside $S$ is bounded
by some a priori specified value.

Supposing that there is a dataset drawn from an underlying probability
distribution $P$, one needs to estimate a ``simple" subset $S$ of the input
space such that the probability that a test point from $P$ lies outside
of $S$ is bounded by some a prior specified $v\in(0,1)$ .

The solution for this problem is obtained by estimating a function $f$
which is positive on $S$ and negative on the complement  $\overline S$.
In other words, Sch\"{o}lkopf et al , developed an algorithm which
returns a function $f$ that takes
the value +1 in a ``small" region capturing most of the data vectors, and -1
elsewhere.




The algorithm can be summarized as mapping the data into
a feature space $H$ using an appropriate  kernel function,
and then trying to separate the mapped vectors
from the origin with maximum margin. (See Figure \ref{fig-svmoneclass1}.)

%\begin{eqnarray}
%\label{eq-svm-f}
\[ f(x) = \left\{ \begin{array}{ll}
     +1  & \mbox{if  $x\in S$} \\
     -1  & \mbox{if  $x\in \overline S$ }
   \end{array}\right. \]

%\end{eqnarray}

\begin{figure}
\caption{One-class SVM}

\label{fig-svmoneclass1}
%\centerline{\psfig{file=svm-oneclass-outliers.eps,height=5cm}}
\centerline{\psfig{file=oneclass.eps,height=7cm}}
\end{figure}

In our context,
let $x_1,x_2, \dots ,x_l$ be  training examples belonging  to one class $X$,
where $X$ is a compact subset of $R^N$.
Let $\Phi: X \longrightarrow H $ be
a kernel map which transforms the training examples to another space.

Then,
to separate the data set from the origin, one needs to solve the
following quadratic programming problem:

%\begin{eqnarray}
%\label{eq-}
 $$  min {1 \over 2} \|w\|^2 +\frac{1}{vl} \sum_{i=1}^l\xi_i -\rho \nonumber $$
  subject to 
 $$  (w \cdot \Phi(x_i) )  \ge \rho-\xi_i  \quad i=1 ,2 , ..., l \quad \xi_i \ge 0 $$
%\end{eqnarray}

\ \\

If $w$ and $\rho$ solve this problem, then the decision function
$$f(x)=sign((w \cdot \Phi(x))- \rho )$$
will be positive for most examples $x_i$ contained in the training set.




In our research we used the LIBSVM (version 2.0), where this is an integrated
tool for support vector classification and regression. This version
can handle one-class SVM using the Sholkopf etc algorithms. The LIBSVM
2.0 is available at {\it http://www.csie.ntu.edu.tw/\~{}cjlin/libsvm}.
We used the standard parameters of the algorithm.
%We implemented both of these methods, the first is called 
%``one-class SVM" in the sequel, while the second is called ``outlier-SVM".

For this ``one-class SVM", one has to choose the original 
frequency representation,  (e.g. the number of features),
the appropriate kernel, and for each kernel the appropriate parameters.



%For the ``outlier-SVM", one also has to choose the original frequency
%representation,  and how far from the origin a point can be 
%(in our case, in Hamming distance) before being classified as an 
%outlier.


%We investigated both algorithms in this setting under a variety of 
%choices.   Our experiments were more extensive for the one-class SVM
%methodology. 

We allowed, linear, sigmoid, polynomial and
radial basis  kernels; each chosen with the standard parameters.

For the original feature representation, we used binary, tf-idf and
Hadamard representations.

For the number of features we tried  10, 20, 40, 60 and 100 features for the 
one-class SVM.   

%For the outlier SVM we tried 10 and 20, for binary representations.
%(We did sample runs with other parameters, but since the results were
%clearly poor, did not complete the experiments.)


%The results are presented in tables xxxx- xxxx .

%1.  The best representation was clearly binary in all cases, both for
%one-class SVM and for outlier SVM.    
%2.  The best number of features for one class SVM was 10; 
%however it did depend on the kind of kernel used.   Moreover, the difference
%was dramatic.   Note in table ... the return for the radial basis kernel 
%was .519 overall with vector length 10; while for vector length 20, the
%results were a catastrophic .126.   On the other hand the polynomial
%kernel gave poor results (.238) with vector length 10, yet imporved to 
%.460 for polynomial kernel.     As far as we can tell from our results,
%the linear kernel seemed more stable.
%
%3.  The outlier SVM  in general performed worse than the one-class SVM.
%Except for the proper definition of outlier, its results seemed less
%sensitive to the choice of parameters.   The definition of outlier
%{\em was} crucial, however, note that this can be analyzed and performed
%automatically.
%
%















%They framed the problem in the following way:

%Suppose that a dataset has a probability distribution $P$ in the 
%feature space.  Find a ``simple" subset $S$ of feature space such that
%the probability that a test point from $P$ lies outside $S$ is bounded
%by some a priori specified value.

%Suppose that one have some dataset drawn from an underlying probability
%distribuation $P$, we need to estimate a ``simple" subset $S$ of input
%space such that the probability that a test point from $P$ lies outside
%of $S$ is bounded by some a prior specified $v\in(0,1)$ .

%The solution for this problem is obtained by estimating a function $f$
%which is positive on $S$ and negative on the complement  $\overline S$. 
%In other words, Sch\"{o}lkopf etc , developed an algorithm which 
%returns a function $f$ that takes
%the value +1 in a ``small" region capturing most of the data vectors, and -1
%elsewhere. 




%The algorithm can be summarized as maping the data into
%a feature space $H$ using an appropriate  kernel function, 
%and then trying to separate the mapped vectors
%from the origin with maximum margin.

%\begin{eqnarray}
%\label{eq-svm-f}
%\[ f(x) = \left\{ \begin{array}{ll}
%     +1  & \mbox{if  $x\in S$} \\
%     -1  & \mbox{if  $x\in \overline S$ }
%   \end{array}\right. \]

%%\end{eqnarray}

%\begin{figure}
%\caption{A svm for one class}
%\label{fig-svmoneclass1}
%\centerline{\psfig{file=svm-oneclass1.eps,height=5cm}}
%\end{figure}
%
%In our context, 
%let $x_1,x_2,..,x_l$ be  training examples belonging  to one class $X$, 
%where $X$ is a compact subset of $R^N$.
%Let $\Phi: X \longleftarrow H $ be
%a kernel map which transforms the training examples to another space. 
%
%Then,
%To separate the data set from the origin, one need to solve the
%following quadratic programming problem:
%
%\begin{eqnarray}
%\label{eq-}
% $$  min {1 \over 2} \|w\|^2 +\frac{1}{vl} \sum_{i=1}^l\xi_i -\rho \nonumber \\
%   (w \cdot \Phi(x_i) )  \ge \rho-\xi_i  \quad i=1 ,2 , ..., l \nonumber \\
%   \xi_i \ge 0 $$
%\end{eqnarray}

%If $w$ and $\rho$ solve this problem, then the decision function
%$$f(x)=sign((w \cdot \Phi(x))- \rho )$$
%will be positive for most examples $x_i$ contained in the training set.

%In our research we use the LIBSVM (version 2.0) , where this is an integrated
%tool for support vector classification and regression. This version
%can handle one-class SVM using the Sholkopf etc algorithms. The LIBSVM
%2.0 is available at {\it http://www.csie.ntu.edu.tw/~cjlin/libsvm}.

