% tw=78:ts=2:sw=2:expandtab % Paper Journal for Machine Learning Research 2001. % % using Brodatz texture images. \documentclass[twoside,11pt,letter]{article} \usepackage{jmlr2e} %\usepackage{dxd,amsmath} \usepackage{amsmath,xspace} % Heading arguments are {volume}{year}{pages}{submitted}{published}{authors} \jmlrheading{2}{2001}{153-171}{3/01}{12/01}{D.M.J. Tax and R.P.W. Duin} \ShortHeadings{Uniform object generation}{Tax and Duin} \firstpageno{155} %\setcounter{topnumber}{4} %\setcounter{bottomnumber}{4} %\renewcommand{\textfraction}{0.0} %\renewcommand{\topfraction}{0.999} \renewcommand{\vec}[1]{{\ensuremath{\bf #1 }}} \newcommand{\vecx}{{\ensuremath{\bf x}}} \newcommand{\vecz}{{\ensuremath{\bf z}}} \newcommand{\vecci}{\boldsymbol{\xi}} \newcommand{\ai}{\alpha_i^{}} \newcommand{\aj}{\alpha_j^{}} \newcommand{\ci}{\xi_i^{}} \newcommand{\gi}{\gamma_i^{}} \newcommand{\vecai}{\boldsymbol{\alpha}} \newcommand{\vecgi}{\boldsymbol{\gamma}} \newcommand{\fTr}{\ensuremath{f_{T-}}\xspace} \newcommand{\fOa}{\ensuremath{f_{O+}}\xspace} \newcommand{\err}[1]{\ensuremath{\mathcal{E}_{\textrm{#1}}}} \begin{document} \title{Uniform Object Generation for Optimizing One-class Classifiers} \author{\name David M.J. Tax \email davidt@ph.tn.tudelft.nl\\ \name Robert P.W. Duin \email bob@ph.tn.tudelft.nl\\ \addr Pattern Recognition Group, Delft University of Technology \\ Lorentzweg 1, 2628 CJ Delft, The Netherlands} \editor{Nello Cristianini, John Shawe-Taylor and Bob Williamson} \maketitle \begin{abstract}% In one-class classification, one class of data, called the target class, has to be distinguished from the rest of the feature space. It is assumed that only examples of the target class are available. This classifier has to be constructed such that objects \emph{not} originating from the target set, by definition outlier objects, are not classified as target objects. In previous research the support vector data description (SVDD) is proposed to solve the problem of one-class classification. It models a hypersphere around the target set, and by the introduction of kernel functions, more flexible descriptions are obtained. In the original optimization of the SVDD, two parameters have to be given beforehand by the user. To automatically optimize the values for these parameters, the error on both the target and outlier data has to be estimated. Because no outlier examples are available, we propose a method for generating artificial outliers, uniformly distributed in a hypersphere. An (relative) efficient estimate for the volume covered by the one-class classifiers is obtained, and so an estimate for the outlier error. Results are shown for artificial data and for real world data. \end{abstract} \begin{keywords} Support vector classifiers, one-class classification, novelty detection, outlier detection \end{keywords} \section{Introduction\label{sec:intro}} In one-class classification, the problem is to distinguish one class of data from the rest of the feature space. In one-class classification we assume that we have examples from just one of the classes, called the target class and that all other possible objects, per definition the outlier objects, are uniformly distributed around the target class. In this type of classification problems, one of the classes is characterized well, while for the other class (almost) no measurements are available. This situation can occur, for instance, when we want to monitor a machine. A classifier should detect when the machine is showing abnormal, faulty behavior. Measurements on the normal operation of the machine are easy to obtain. In faulty situations, on the other hand, the machine might be destroyed completely. In general, the problem of one-class classification is harder than the problem of conventional two-class classification. In conventional classification problems the decision boundary is supported from both sides by examples of both classes. Because in the case of one-class classification only one set of data is available, only one side of the boundary is supported. It is therefore hard to decide, on the basis of just one class, how strictly the boundary should fit around the data in each of the feature directions. This one-class classification problem is often solved by estimating the target density \citep{Moya2}, or by fitting a model to the data support vector classifier \citep{Vapnik}. Instead of using a hyperplane, to distinguish between two classes, a hypersphere around the target set is used. The volume of the hypersphere is minimized directly. This method is called the support vector data description (SVDD), developed by \cite{Tax5}.\footnote{A comparable method using a separating hyperplane is presented in \citet{Scholkopf3}, fitting a hypersphere is mentioned in \citet{Scholkopf5, Burges}.} It has the possibility to reject a fraction of the training objects, when this sufficiently decreases the volume of the hypersphere (a more complete explanation will be given in Section \ref{sec:SVDD}). Unfortunately, the user has to supply a trade-off parameter $C$. Furthermore, the hypersphere model of the SVDD can be made more flexible by introducing kernel functions. Although it gives the possibility of making more flexible and better fitting descriptions, the user has to give the value of another parameter, called the kernel-width parameter $s$, which will be defined later. The choice for these parameters is not intuitive, but they have large influence on the final one-class classifier. To find good values for these parameters $s$ and $C$, an error criterion has to be defined, which contains both an error on the target set and an error on the outlier set. Because the training set only contains training objects from the target set, the error on the outlier set has to be estimated in another way. In this paper we choose to generate artificial outliers uniformly in and around the target set. The fraction of the outliers which is then accepted by the one-class classifier, is now an estimate of the volume in the feature space covered by the one-class classifier. The problem is that in high dimensional feature spaces, it becomes very inefficient. When the outlier distribution is not very tightly defined around the target set, the chance that an outlier object is in the target distribution becomes very small. In that case, huge amounts of artificial outliers have to be generated before a confident estimate of the error on the outlier class can be made. Instead of using a hyperbox (from which it is very easy to generate objects uniformly), we propose to use a hyperspherical distribution which, we hope, fits better around the target set. When it fits better, this error criterion using the artificial outliers can be used in high dimensional feature spaces. In this paper, we focus on the problem of the determination of the two free variables $s$ and $C$ using the artificial outlier objects. In Section \ref{sec:SVDD} we will explain the SVDD, and introduce the free variables. In Section \ref{sec:opt_s_c} we show how $s$ and $C$ can be optimized using artificial outlier objects. We will generate example outliers uniformly distributed in a hypersphere in Section \ref{sec:gen_sphere}. The optimization of the free parameters using the artificial outliers is applied in Section \ref{sec:exp} to some classification tasks. %DXD There we will also show that the data description obtained thus by the SVDD is comparable with one obtained using a density estimator (Mixture of Gaussians). We end with conclusions in Section \ref{sec:conclusions}. \section{Support vector data description\label{sec:SVDD}} First we give a short derivation of the support vector data description. It is a one-class classifier inspired by the support vector classifier \citep{Vapnik}. To describe the domain of a dataset, we enclose the data with a hypersphere with minimum volume (this is identical to the approach which is used in \citet{Burges} to estimate the VC-dimension of a classifier which is bounded by the diameter of the smallest sphere enclosing the data). By minimizing the volume of the captured feature space, we hope to minimize the chance of accepting outlier objects. Assume we have a data set containing $N$ data objects, $\{\vecx_i, i=1,..,N\}$ and the hypersphere is described by center $\vec{a}$ and radius $R$. To fit the hypersphere to the data, we minimize an error function $L$ containing the volume of the hypersphere and the distance from the boundary of the outlier objects. We constrain the solution with the requirement that (almost) all data is within the hypersphere. To allow the possibility of outliers in the training set, the distance from $\vecx_i$ to the center $\vec{a}$ should not be strictly smaller than $R$, but larger distances should be penalized. Therefore, we introduce slack variables $\vecci$ which measure the distance to the boundary, if an object is outside the description. An extra parameter $C$ has to be introduced for the trade-off between the volume of the hypersphere and the errors. This results in the following error and constraints: \begin{eqnarray} L(R,\vec{a},\vecci) = R^2 + C\sum_i\ci \label{eq:error}\\ \| \vecx_i - \vec{a}\|^2 \leq R^2 + \ci, \quad \quad \forall_i \label{eq:constr} \end{eqnarray} \cite{Scholkopf3} proposed another approach which is called the $\nu$-support vector classifier. Here a hyperplane is placed such that it separates the dataset from the origin with maximal margin (the parameter $\nu$ will be explained in the coming sections). Although this is not a closed boundary around the data, it gives identical solutions when the data is preprocessed to have unit norm. The constraints \eqref{eq:constr} can be incorporated in the error \eqref{eq:error} by applying Lagrange multipliers \citep{Bishop}. The following Lagrangian is obtained: \begin{equation} L(R,\vec{a},\vecci,\vecai,\vecgi) = R^2 + C \sum_i \ci \label{eq:L} \quad- \sum_i \ai \{R^2 - (\vecx_i^2 - 2\vec{a}\cdot\vecx_i + \vec{a}^2)\} - \sum_i \gi \ci \nonumber \end{equation} with Lagrange multipliers $\ai \geq 0$ and $\gi \geq 0$. This function has to be minimized with respect to $R,\vec{a}$ and $\ci$ and maximized with respect to $\ai$ and $\gi$. Setting the partial derivatives of $L$ to $R$ and $\vec{a}$ to zero, and using that $\ai\geq 0, \gi\geq 0$, we obtain: \begin{equation} \sum_i \ai = 1, \quad \vec{a} = \sum_i \ai \vecx_i, \quad 0 \leq \ai \leq C,\, \forall_i \label{eq:finalconstr} \end{equation} Resubstituting these values in the Lagrangian \eqref{eq:L} gives to maximize with respect to $\vecai$: \begin{eqnarray} L &=& \sum_i \ai (\vecx_i\cdot \vecx_i) - \sum_{i,j} \ai \aj (\vecx_i\cdot \vecx_j) \label{eq:orgL} \end{eqnarray} with $0 \leq \ai \leq C$, $\sum_i \ai = 1$. This error function is in a standard quadratic form, and combined with the constraints, it gives a quadratic optimization problem (analogous to the original formulation of the support vector classifier by \cite{Vapnik}). In the maximization of error \eqref{eq:orgL} it appears that a large fraction of the $\ai$ becomes zero. For a small fraction $\ai>0$. The corresponding vectors (or objects) are called support vectors $SV$ (or support objects). These vectors lie on the boundary. We see that the center of the hypersphere depends just on the few support vectors. The objects with $\ai=0$ can be disregarded in the description of the data. The fraction of objects which become support vector is a leave-one-out estimate of the error on the target set \citep{Tax5}: \begin{equation} E\left[P(\text{error target set})\right] = \frac{\# SV}{N} \label{eq:err_est} \end{equation} where $\# SV$ indicates the number of support vectors. Object $\vecz$ is accepted by the description when the distance from the object $\vecz$ to the center of the sphere $\vec{a}$ is smaller or equal to the radius: \begin{equation} \|\vecz-\vec{a}\|^2 = (\vecz\cdot \vecz) -2\sum_i \ai (\vecz\cdot \vecx_i) +\sum_{i,j} \ai\aj (\vecx_i \cdot \vecx_j) \leq R^2 \label{eq:newtestz} \end{equation} Radius $R$ can be determined by calculating the distance from the center $\vec{a}$ to a support vector $\vecx_i$ on the boundary. Here the model of a hypersphere is assumed for the boundary of the dataset and this will not always be satisfied. Analogous to the method of \citet{Vapnik}, we can replace the inner products $(\vecx\cdot\vec{y})$ in Equations (\ref{eq:orgL}) and in (\ref{eq:newtestz}) by kernel functions $K(\vecx,\vec{y})$ which gives a much more flexible method. When we replace the inner products by, for instance, Gaussian kernels, we obtain: \begin{equation} (\vecx\cdot \vec{y}) \rightarrow K(\vecx,\vec{y}) = \exp( -\|\vecx-\vec{y}\|^2/s^2) \label{eq:gaussK} \end{equation} Other kernel functions can be used (a polynomial kernel) but this Gaussian kernel appears to produce particular tight data descriptions \citep{Tax9}. Therefore we will use this kernel in the rest of the paper. Error \eqref{eq:orgL} changes into: \begin{equation} L = 1 - \sum_i {\ai}^2 - \sum_{i \neq j} \ai \aj K(\vecx_i,\vecx_j) \label{eq:gaussL} \end{equation} From \eqref{eq:newtestz}, we see that to evaluate a novel object $\vecz$ to see if this lies within the hypersphere, it should hold that: \begin{equation} \sum_i \ai K(\vecz,\vecx_i) \leq \frac{1}{2}\left(1-R + \sum_{i,j} \ai\aj K(\vecx_i, \vecx_j)\right) \label{eq:finaltestz} \end{equation} Using the possibilities to reject objects from the training set and to introduce kernel functions, two free parameters are introduced. This Gaussian kernel contains the first free parameter, the width parameter $s$ in the kernel (from definition (\ref{eq:gaussK})). For small values of $s$ almost all $\ai>0$ and the SVDD resembles a Parzen density estimation. For large $s$, on the other hand, the original hypersphere solution is obtained \citep{Tax5}. As shown in \citet{Tax5} this parameter can a priori be set by using the maximal allowed rejection rate of the target set, that is the error on the target set. Secondly, we also have to determine the trade-off parameter $C$. We can define a new variable $\nu$: \begin{equation} \nu = \frac{1}{NC} \label{eq:def_nu} \end{equation} \citet{Scholkopf1} showed that this is an upper bound for the fraction of target class objects outside the description. Because the parameter $\nu$ is easier to interpret, we will use $\nu$ instead of $C$ in the rest of the paper. The exact influence of $s$ and $\nu$ (or $C$) on the SVDD is investigated in the next section. The estimation of the error by Equation \eqref{eq:err_est} immediately points out that in this support vector data description, it cannot be avoided that errors on the target class are made (that is target objects are rejected). The probability of rejecting target objects even cannot be decreased to zero, because there will always be a minimum number of support vectors necessary for the data description. This merely indicates that, given the data, the boundary cannot be estimated better. Only when a large training dataset is available, the error on the target set can be made very small. %DXD more?? \section{Optimization of $s$ and $\nu$} \label{sec:opt_s_c} \begin{figure*}[htb] \begin{center} \includegraphics[width=10cm]{all_s_C} \end{center} \vspace*{-2mm} \caption{Decision boundaries of a simple 2-dimensional dataset, with different choices of $s$ and $\nu$.} \label{fig:all_s_C} \end{figure*} One intuitive parameter for the user is the fraction of the target objects which can be rejected by the description, \fTr. Assume the user is satisfied with an error of $5\%$ on the target set. Then, one parameter ($s$ or $\nu$) can be optimized, using estimate \eqref{eq:err_est}, such that $5\%$ of the training objects become support vector. The SVDD will then have approximately $\fTr=0.05$. Unfortunately, this will not uniquely define both parameters $s$ and $\nu$, but just one of them. In this section, we will argue that, to have a unique solution for both $s$ and $\nu$, we have to introduce an extra constraint. We will choose to minimize the volume occupied in feature space by the one-class classifier. This will then automatically result in an error we can minimize. In Figure \ref{fig:all_s_C} the decision boundaries of the SVDD for different choices of $s$ and $\nu$ are shown for an artificial, 2-dimensional banana-shaped target set. The Figure shows that for smaller $s$, small details in the data are followed. On the other hand, when $s$ is very large (in the order of the size of the complete dataset), only a spherical solution is found (for $s\rightarrow \infty$ the rigid hypersphere solution is obtained, \citep[as shown in][]{Tax5}. For $\nu=0$ ($C=\infty$) no target objects are allowed outside the description. All objects, including the remote object at $(10,0)$, are accepted. When $\nu=\frac{1}{4}$ about one quarter of the target data can be outside the description. When enough data is available, a more robust estimate of the boundary is obtained. In general, when $s$ is large and $\nu$ is small, a spacious data description is obtained. For this 2-dimensional dataset it is possible to judge the boundary visually and to pick reasonable values for $s$ and $\nu$. For higher dimensional data this is not possible. In these cases other measures have to be invented to judge the quality of the description. For a good data description, we have two requirements: (1) a low target rejection rate \fTr and (2) a low outlier acceptance rate \fOa. When we are only given examples of the target set, the first term can be estimated by the number of support vectors that we obtain as a solution of Lagrangian \eqref{eq:gaussL}. Minimizing just the error on the target set, \fTr, is not sufficient. The solution would be to accept the complete feature space. To estimate the outlier acceptance rate without example outliers, we have to assume an outlier distribution. When we assume the outliers are uniformly distributed in the part of the feature space we are interested in, we should minimize the volume which the description occupies. To minimize this, we have to estimate the volume of the description. This can be done by creating a large set of (artificial) outlier objects around the target dataset. When these outliers are uniformly distributed, the fraction of the outliers that is accepted, gives an estimate of the volume of the data description with respect to the volume of the outlier distribution. Unfortunately, this procedure may become very expensive in high dimensional feature spaces. Assume that the target set is distributed in a hypercube with edges of unit length and that the outliers come from a hypercube with $10\%$ larger edges (that means edges of length $1.1$). In 10 dimensions the outlier distribution has $2.6$ times the volume of the target set, but in 20-D this is already more than $3000$ times! When data is generated in this outlier distribution, the chance that one of them falls in the target set, is about $0.3\%$. Of course, the target data can have different shapes, but it will always hold that the volumes of the target and outlier set will diverge with increasing dimensionality of the data. For high dimensional data it is therefore essential that the outliers are tightly distributed (in and) around the target class to avoid that for the estimation of the target volume, a very high fraction of test outliers will be rejected and no confident target volume estimation can be made. It would be very easy to create objects uniformly from a hyperblock in $d$ dimensions, but it is not very likely that this distribution will fit very tightly around the target class. Many outlier objects will be generated in the corners of the box instead of into the data description. In this paper we propose to use the rigid hypersphere solution from formula \eqref{eq:constr}. We hope this will fit tighter around the target set than the hyperbox. When data is generated uniformly from this area, the fraction of these objects that is accepted by the description, is now an estimate of the volume that is occupied by the description. We can now define the error for a one-class classifier: \begin{equation} \Lambda(s, \nu) = \lambda \frac{\#SV}{N} + (1-\lambda) \frac{\#{\text{outlier objects accepted}}} {\#{\text{outlier objects}}} = \lambda \frac{\#SV}{N} + (1-\lambda) \fOa \label{eq:tot_error} \end{equation} where a new parameter $\lambda$ is introduced. Using this formula, we can optimize both $s$ and $\nu$ to get minimum $\Lambda$. When we take $\lambda=\frac{1}{2}$, errors on the fraction of target and outlier objects are weighted equally. In the optimal solution, the fraction of target objects that is rejected, is equal to the volume fraction of the outlier area which is occupied by the target set. Finally, generating samples which are uniformly distributed in a $d$-dimensional hypersphere is not easy. In the next section we propose a method to do this. \section{Generating samples uniformly from a hypersphere} \label{sec:gen_sphere} Although a uniform hyperspherical outlier distribution might fit tighter around the target class than a hyperbox distribution, it is not trivial to draw objects from a uniform hyperspherical distribution \citep{Luban}. Our key idea for the generation of these samples, is to use a $d$-dimensional Gaussian distribution. The direction of the object vectors from the origin will not be changed, but we rescale the norm of the object vectors. The generation is in several steps: \begin{enumerate} \item Generate data $\vecx$ from Gaussian distribution (with zero mean and unit variance), \begin{equation} \vecx \sim \mathcal{N}(\boldsymbol{0},\boldsymbol{1}) \nonumber \end{equation} \item Calculate the squared Euclidean distance from each sample to the origin, $r^2$. This squared distance is distributed as $\chi^2$ with $d$ degrees of freedom \citep{Ullman}. \begin{equation} r^2 = \|\vecx\|^2 \nonumber \end{equation} \item Use the cumulative distribution of $\chi^2_d$, $X^2_d$, to transform the $r^2$ distribution in a uniform distribution between 0 and 1. This results in a uniform distribution of $\rho^2$: \begin{equation} \rho^2= X^2_d(r^2) = X^2_d(\|\vecx\|^2) \nonumber \end{equation} \item Rescale $\rho^2$ by $r' = (\rho^2)^{\frac{2}{d}}$ such that $r'$ is distributed as $r' \sim r^d$ for $r$ between $0$ and $1$. \begin{equation} r' = \left(\rho^2\right)^{\frac{2}{d}} = \left(X^2_d(\|\vecx\|^2)\right)^{\frac{2}{d}} \nonumber \end{equation} \item Rescale all objects $\vecx$ with this factor: \begin{equation} \vecx' = \frac{r'}{\|\vecx\|} \vecx \nonumber \end{equation} \end{enumerate} Now $\vecx'$ are uniformly distributed in a unit hypersphere in $d$ dimensions. This is used to generate uniformly objects in any $d$-dimensional hypersphere by rescaling and shifting the data. Given this outlier generation algorithm, it is possible to train a conventional classifier on these two classes. Although it is possible, one has to be careful. One has to generate enough artificial data to have objects around the target class in all feature directions. Second, one has to use a classifier which is local, i.e. a classifier which will generate a closed boundary around the target class and which will not classify remote objects as target objects. Finally, the classifier should be robust against large class-overlap, because by this method of generation of outlier objects, it cannot be avoided that outliers are generated within the target distribution. Even worse, because it is likely that a large set of outliers has to be generated for a good coverage over the target class, the two classes will be very imbalanced. Still the classifier should have small error on the target class (which is the only 'real' data we have) and therefore the classifier should also be able to handle the difference in significance of the target and outlier objects. \section{Experiments \label{sec:exp}} Given the error \eqref{eq:tot_error} and the possibility of efficiently generating outlier objects around the target data (and a value for $\lambda$!), we are able to optimize the free parameters $s$ and $\nu$ in the SVDD (with error \eqref{eq:gaussL} and evaluation formula \eqref{eq:finaltestz}). In this section we want to investigate if the optimization of \eqref{eq:tot_error} results in reasonable values for $s$ and $\nu$. In all cases we will optimize such that an equal fraction of the target and outlier objects is erroneously classified, which means we will use $\lambda=\frac{1}{2}$. %DXD At the end of this section we will check if the classification results are reasonable, which means comparable with a data description using a density estimator. \subsection{Artificial example} In Section \ref{sec:opt_s_c} we showed a simple banana-shaped dataset which contained one clear outlier at $(10,0)$. Using this dataset, we generate $1000$ outlier objects. We find simultaneously $s$ and $\nu$ by minimizing error \eqref{eq:tot_error} (using a Matlab optimization routine) and we obtain the final data description. \begin{figure}[ht] \begin{center} \includegraphics[width=6cm]{opt_outliers} \includegraphics[width=6cm]{opt_s_C} \end{center} \caption{Left: Artificial outlier data generated around the banana-shaped target set from Figure \ref{fig:all_s_C}. Right: SVDD decision boundary for optimized $s$ and $\nu$.} \label{fig:opt_s_c} \end{figure} The results are shown in Figure \ref{fig:opt_s_c}. The left subplot shows the artificial outlier data generated around the banana-shaped target set. In the right subplot the decision boundary for the SVDD with the optimized $s$ and $\nu$ is shown. Note that we fitted the hypersphere to the training data. It can easily happen that the testing data is distributed somewhat around the training data and that therefore the hypersphere does not cover the testing set completely. Without using the testset it is not possible to find this out and we ignore this problem in this paper. Because the errors for the target and outlier objects are equally weighted, the boundary of the dataset is not exactly \emph{around} the data, but a fraction of the target data is rejected. On the other hand, the data description gives a good impression of the shape of the data. When the error on the target set should be smaller, the $\lambda$ in formula \eqref{eq:tot_error} can be adapted, or the threshold value (the right term in inequality \eqref{eq:finaltestz}) can be changed. \subsection{Handwritten digits} \begin{figure}[ht] \begin{center} \includegraphics[width=12cm,height=3cm]{con_tst_3_pca75_2} % \vspace*{-2mm} \end{center} \caption{Testing target objects rejected by the data description.} \label{fig:con_tst_3} \end{figure} To see if we can find outlier objects in a real world dataset, we trained a SVDD on a handwritten digits dataset \cite[the Concordia dataset, which is also used, for instance, by][]{Cho}. This dataset contains handwritten digits (size $32\times 32$), with 400 objects per class in a training set and 200 objects per class in a testing set. The data dimensionality was reduced from $1024$ to about $30$ using PCA, retaining $75\%$ of the variance in the data. An SVDD was trained on the class representing the threes. The $s$ and $\nu$ were optimized simultaneously by minimizing error \eqref{eq:tot_error} ($\lambda = \frac{1}{2}$) using $100,000$ artificially generated outlier objects (this large amount of outlier objects was necessary in order to obtain a reasonable confident estimate of the target class volume). The SVDD was tested on the 200 testing handwritten threes. In Figure \ref{fig:con_tst_3} the test objects are shown, which are rejected by the SVDD. From the 400 training objects $11\%$ became support vector ($\ai>0$). This fraction corresponds well with the error on the test set, where $24$ of the $200$ testing objects are rejected, i.e. an error of $12\%$. Surprisingly, some reasonable threes are rejected (the upper left three, for instance), but also a real segmentation error was detected (the thirteen in the lower left). Note that only information about the target class is used, and that no extra preprocessing was done (except for using $75\%$ PCA). \begin{figure}[thb] \begin{center} \includegraphics[width=55mm]{art_box} \hspace*{1cm} \includegraphics[width=55mm]{art_sph} \end{center} \caption{Artificial objects (images of handwritten threes) generated from a box-shaped distribution around the target set (left subplot) and from a spherical-shaped distribution (right subplot).} \label{fig:con_reconstr} \end{figure} To show the difference between the generation of artificial objects from a spherical and a rectangular distribution around the target set, we generated a few random objects and mapped them back to the original image space ($32\times 32$ dimensional). The results are shown in Figure \ref{fig:con_reconstr}. The left subplot shows 9 images from the box-distribution, the right suplot from the spherical distribution. Although the images of both distributions are not 'crisp' (caused by the PCA), the images from the box-distribution have backgrounds with very different gray values. This indicates that the images are distributed in (relative) remote parts in the feature space. The images from the spherical outlier distribution are closer to the real training images, especially considering the background which is now dark. In this experiment it is even harder than in the 2-dimensional example, to judge if these results are good. Here no ground truth is available, i.e. an object is a genuine three, or an outlier three. In the next section we investigate an example where ground truth is available. \subsection{Texture segmentation} \begin{figure}[ht] \begin{center} {}\,\fbox{\includegraphics[width=34mm]{../auto_s_c/comgt}} \includegraphics[width=34mm,height=34mm]{com_n_1}\,\emph{1} \includegraphics[width=34mm,height=34mm]{com_n_2}\,\emph{2} \includegraphics[width=34mm,height=34mm]{com_n_13}\,\emph{3} \end{center} \caption{Texture segmentation. The texture in the cross shaped region in the middle is used as target class (left figure). The next three images are examples of textures used.} \label{fig:texture_seg} \end{figure} In this application we try to describe one texture and distinguish it from other textures. For this we use some test images, containing two types of textures where we know beforehand the ground truth of both textures. In Figure \ref{fig:texture_seg} the ground truth (first subplot) and the three texture images with varying classification complexity are shown (next subplots). The cross-shaped, dark area contains the target texture, all other pixels are per definition outlier objects. To classify a pixel from the image, an image-patch containing $16\times 16=256$ pixels is drawn around this pixel. Therefore, an object (one pixel) is characterized by a 256-dimensional feature vector. In the experiments, the SVDD is trained on a training set, which is sampled from the complete target region. 400 objects are used for training. A few outliers can be in the training set, because when a patch in the neighborhood of the boundary of the target class is used, a part of the outlier texture can be included in the patch. We compare the results of the SVDD where we (1) set manually the fraction of objects that is on the boundary and outside the boundary, and (2) where we just optimize formula \eqref{eq:tot_error}. When we manually set the parameters, we set $C$ to a prespecified fraction of objects which is \emph{outside} the description, according to Equation \eqref{eq:def_nu}. Objects outside the boundary automatically have $\ai=C$. We will use $\nu=0.0, 0.1$ and $0.2$. The width parameter $s$ is optimized such that a prespecified fraction of the objects will be \emph{on} the boundary. This means that the Lagrange multiplier $\ai$ corresponding to the support vector $\vecx_i$ has $0<\ai