See discussions, stats, and author profiles for this publication at: [Link]

net/publication/291229469

Domain based classification

Article · January 2016

DOI: 10.48550/arXiv.1601.04530 · Source: arXiv

CITATIONS READS
0 193

2 authors, including:

Robert Duin
Delft University of Technology
410 PUBLICATIONS 39,199 CITATIONS

SEE PROFILE

All content following this page was uploaded by Robert Duin on 20 September 2016.

The user has requested enhancement of the downloaded file.

 Domain based classification

Robert P.W. Duin [Link]@[Link]

ICT group, Faculty of Electr. Eng., Mathematics and Computer Science
Delft University of Technology, The Netherlands
Elzbieta Pekalska [Link]@[Link]
arXiv:1601.04530v1 [[Link]] 18 Jan 2016

ICT group, Faculty of Electr. Eng., Mathematics and Computer Science

Delft University of Technology, The Netherlands

Abstract nown, one, therefore,

Pn minimizes the empirical error
Eemp (f ) = n1 i=1 L(yi , f (xi )). Additionally, a trade-
The majority of traditional classification ru-
off between the function complexity and the fit to the
les minimizing the expected probability of er-
data has to be kept, as a small empirical error does
ror (0-1 loss) are inappropriate if the class
not yet guarantee a small true error. This is achieved
probability distributions are ill-defined or im-
by adding a suitable penalty or regularization func-
possible to estimate. We argue that in such
tion as proposed in the structural risk minimization or
cases class domains should be used instead of
regularization principles.
class distributions or densities to construct a
reliable decision function. Proposals are pre- Although these principles are mathematically well-
sented for some evaluation criteria and classi- founded, they rely on very strong, though general, as-
fier learning schemes, illustrated by an exam- sumptions. They impose a fixed (stationary) distri-
ple. bution from which vectors, representing objects, are
drawn. Moreover, the training set is believed to be
representative for the task. Usually, it is a random
1. Introduction subset of some large target set, such as a set of all
objects in an application. Such assumptions are often
Probabilistic framework is often employed to solve le- violated in practice, not only due to differences in me-
arning problems. One conveniently assumes that real- asurements caused by variability between sensors or
world objects or phenomena are represented as (or, in a difference in calibration of measuring devices, but,
fact, reduced to) vectors x in a suitable vector space X . more importantly, due to the lack of information on
The learning task relies on finding an unknown func- class distributions or impossibility of gathering a re-
tional dependency between x and some outputs y ∈ Y. presentative sample. Some examples are:
Vectors x are assumed to be iid, i.e. drawn independen-
tly from a fixed, but unknown probability distribution • In the application of face detection, the distribu-
p(x). The function f is given as a fixed conditional tion of non-faces cannot be determined, as it may
density p(y|x), which is also unknown. To search for be unknown for which type of images and in which
the ideal function f ∗ , a general space of hypothesis environments such a detector is going to be used.
functions F = {f : X → Y} is considered. f ∗ is con-
sidered optimal according to some loss function L : • In machine diagnostics and industrial inspection
X ×Y → [0, M ], M > 0, measuring the discrepancy be- some of the classes have to be artificially induced
tween the true and estimated values. The learning pro- in order to obtain sufficient examples for training.
blem is Rthen formulated as minimizing the true error Whether they reflect the true distribution may be
E(f ) = X ×Y L(y, f (x))p(x, y)dx dy, given a finite iid unknown.
sample, i.e. the training set {(xi , yi )}, i = 1, 2, . . . , n.
As the joint probability p(x, y) = p(x)p(y|x) is unk- • In geological exploration for mining purposes, a
large set of examples may be easily obtained in
one area on earth, but its distribution might be
entirely different than in another area, whose sam-
Unpublished paper, March 2005. Copyright by the authors.
ple will not be provided due to the related costs.
In human learning, a random sampling of the distribu- design learning procedures and how to evaluate them?
tion of the target set does not seem to be a plausible Can classifiers output confidences? How to judge whe-
approach, as it is usually not very helpful to encoun- ther a given training set is representative for the do-
ter multiple copies of the same object among training main? Are any further assumptions needed or advan-
examples. For instance, in studying the difference be- tageous? Can cluster analysis or feature selection be
tween the paintings of Rembrandt and Velasquez it applied? The goal of this paper is to raise interest in
makes no sense to consider copies of the same pain- domain learning. As the first step, we introduce the
ting. Even very similar ones may be superfluous, in problem, discuss a few issues and propose some appro-
spite of the fact that they may represent some mode aches.
in the distribution of paintings. On the contrary, it
may be better to emphasize the tails or the borders 2. Performance criteria
of the distribution, especially in the situations, where
the classes seem to be hard to distinguish. Suppose a classifier f (x) is designed that assigns ob-
jects to one of the given classes. A labeled evaluation
Although the probabilistic framework is applied to
set or a test set S is usually used to estimate the per-
many learning problems, there are many practical situ-
formance of f (x) by counting the number of incorrect
ations, where alternative paradigms are necessary due
assignments. This, however, demands that the set S
to the nature of ill-sampled data or ill-defined distri-
is representative for the distribution of the target set,
butions. Which may be an appropriate model for the
which conflicts with our assumption.
relation between a training set of examples and the
target set of objects to be classified1 if we cannot or For a set of objects to be representative for the class
do not want to assume that the distribution of the tra- domains it may be assumed that the objects are well
ining set is an approximation of the distribution of the spread over these domains. For the test set S, it means
target set? This paper focusses on this aspect. Our that there is no object x in any of the classes that has
basic assumption is that the training sample is repre- a large distance d(x, xs ) to its nearest objects xs ∈ S.
sentative for the domain of the target set (all examples Therefore, for a domain representative test set S holds
in the given application) instead of being drawn from that
a fixed probability distribution. dmax = max min d(x, xs ) (1)
x xs ∈S
Consider a representation space, called also input
space, X , endowed with some metric d. This is the is small ∀x. The usefulness of this approach relies on
space, in which objects are represented as vectors and the fact that the distances as given in the input space
the learning takes place. A domain is a bounded set are meaningful for the application. Consequently, for a
A in X , i.e. ∃r > 0 ∀x, z ∈ A d(x, z) ≤ r. (We do not as- well-performing classifier, none of the erroneously clas-
sume that the domain is totally bounded.) This is not sified objects is far away (at the wrong side) from the
new as one usually expects that classes are represented decision boundary. If the classes are separable, the test
by a set of vectors in (possibly convex and) bounded objects should also be as far away from the decision
subsets of some space. Here, we will focus on vector boundary as possible. Therefore, our proposal is to
space representations constructed by features, dissimi- follow the worst-case scenario and to judge a classifier
larities or kernels. As the class domains are bounded by the object that is the most misleading. This will
in this representation, for each class ωj , there exists be judged by its distance to the decision boundary.
some indicator function Gj (x) of the object2 x such Consider a two-class problem with the labels y ∈
that Gj (x) = 1 if x is accepted as a member of ωj and {−1, +1}, where y(x) denotes the true label of x. (This
Gj (x) = 0, otherwise. Given a training set of labeled notation is the consequence of our assumption that
examples {(xi , yi )}, Gj (xi ) = 1 if xi belongs to the different objects with different labels may be repre-
class ωj . We will assume that each object belongs to sented in the same point x). Let f (x) yield the si-
a single class, however, identical objects with different gned distance of x to the decision boundary induced
labels are permitted. This allows classes to overlap. by the classifier. Note that the unsigned distance of x
Given the above model, several questions arise. How to to the decision boundary is related to the functional
form of f . Then
1
In classification problems, yi is a class label and L
is the 0-1 loss, L(yi , f (xi )) = I(yi 6= f (xi )), where I is η(S|g) = min y(xs )f (xs ) (2)
the indicator function. Classifiers minimize the expected xs ∈S
classification error (0-1 loss).
2
By an object we mean its representation x in the con- is the signed distance to the decision boundary of the
sidered vector space. ’worst’ classified object from the test set S. Having
introduced this, a classifier f1 (x) is judged to be bet- 3.1. Discriminants
ter than a classifier f2 (x) if η(S|f1 ) > η(S|f2 ). The
Consider a two-class problem. If classes are separable
main argument supporting this criterion follows from
by a polynomial or when a kernel transformation is ap-
the fact that if the vector space representation and the
plied, a discriminant function can be found by solving
distance measure are appropriate for the learning pro-
a set of linear inequalities over the training set X, e.g.
blem, then for small values of η(S|f ), the test set S
contains objects that are similar to the objects in a
yi (αT K(X, xi ) + α0 ) > 0, ∀xi ∈ X, (3)
wrong class. As the data and the learning procedure
are not based on probabilities, it is difficult to make
K(X, xi ) is the column vector of all kernel values
a statement about the probability of errors instead of
K(x, xi ), ∀x ∈ X. The resulting weights α ∈ Rn define
the seriousness of their contributions.
the classifier f in the following way:
As a consequence, outliers should be avoided, since
they cannot be detected by statistical means. Still, Assign x to ω1 , if f (x) = αT K(X, x) + α0 ≥ 0,
objects that have large distances to all other objects (4)
Assign x to ω2 , if f (x) = αT K(X, x) + α0 < 0.
(in comparison to their nearest neighbor distances) in-
dicate that the domain is not well sampled. If the This decision function finds a solution if the classes are
sampling is proper, all objects have to be considered separable in the Hilbert space induced by the kernel
as equally important, as they are examples of valid K and fails if they are not. Since no model used to
representations. Copies of the same object do not in- optimize the decision boundary, this decision function
fluence the learning procedures and may, therefore, be is independent of the use of domains or densities.
removed.
In the traditional probabilistic approach to pattern
If classes overlap such that the overlapping domain can recognition, the nearest mean classifier (NMC) and
be estimated and a class of possible density functions Fisher’s linear discriminant (FLD) are two frequen-
is provided, then it might be possible to determine ge- tly used classifiers. Given class means estimated over
neralization bounds for the classification error or to the training set, the NMC assigns each object to the
estimate the expected error over the class of density class of its nearest mean. In a domain approach, class
functions. Both tasks are, however, not straightfor- means should be replaced by the class centers. These
ward, neither estimating the domain of the class over- are vectors µj in the vector space Rm that yield the
lap, nor defining an appropriate class of density func- minimum distance to the most remote object in Xj :
tions. As we only sketch the problem, we will restrict
ourselves to classifiers that maximize criterion (2). µ̂j = arg min max kx − x∗ k (5)
x∗∈Rm x∈Xj
3. Classifier proposals Class centers may be found by a procedure like the
A number of possible domain based decision functions Support Vector Data Description (?; ?), in agre-
will be introduced in this section. We will start by pre- ement to criterion (5). Such a center is determined
senting the domain versions of some well-known proba- by m+ 1 training objects at most, and usually much
bilistic classifiers. It should be emphasized once again less. An approximation can be also based on a feature-
that in the probabilistic framework, any averaging over by-feature computation. Additionally, for sufficiently
objects or their functional dependencies relies on their large data, a single training object may be a sufficien-
distribution. So, averaging cannot be used in domain tly good approximation of the center:
based learning procedures. It has to be replaced by
µ̂j = arg min max kx − x∗ k. (6)
appropriate operators such as minimum, maximum or x∗∈X x∈Xj
domain center.
This can be determined fast from the pairwise distance
Consider a vector space Rm , in which objects x are re-
matrix computed between the training examples (?).
presented e.g. by features. Let X = {x1 , x2 , . . . , xn } be
Given the class centers, the Nearest Center Classifier
a training set with the labels Y = {y1 , y2 , . . . , yn }. As-
(NCC) is now defined as:
sume k classes ω1 , . . . , ωk . If k = 2, then yi ∈ {−1, +1}
are assumed. Let Xj be a S subset of X containing all
Assign x to ωi , if i = arg min kx − µˆj k. (7)
members of ωj . Then, X = j Xj . j

This classifier is optimal (it maximizes criterion 2) if

the class domains are hyperspheres with identical radii.
A traditional criterion for judging the goodness of a 3.2. Model based, parametric decision
single feature is the Fisher Criterion: functions

(µ1 − µ2 )2 Two of the methods described in the previous section

JF = (8) aim at finding discriminants by some separability crite-
σ1 2 + σ2 2
rion such as the difference in class centers or the Fisher
in which µj and σj2 are the class means and variances, distance. They appear to be optimal for identically
shaped class domains, hyperspheres and, respectively,
respectively, as computed for the single feature. A
ellipsoids. Here, instead of considering a functional
domain based version is defined by substituting the
mean with the class center and the variance with the form of a classifier, we will start from some class do-
main models and then determine the classifier.
squared class range. For the k-th feature, σj 2 can be
then estimated as: Class domains are defined by their boundaries. If du-
ring a training process some objects are placed out-
σ̂j2 = (max(xik ) − min(xik ))2 (9) side the domain, the boundaries have to be adjusted.
i i
This is permitted only if the nearest objects inside the
Herewith, a Fisher Linear Domain Discriminant domain are close to the boundaries or their parts (if
(FLDD) can be defined by a weight vector in the distinguishable). ’Unreasonably far away’ objects sho-
feature space for which the domain version of (8) uld not play a role in positioning of the domain bo-
is maximum. We expect that this direction will be undaries. They have to be determined with respect
determined by the minimum-volume ellipsoid enclo- to the demand that objects should sample the domain
sing X c , the pooled data shifted by the class centers well. So, the distance from the domain boundary to
Xjc = {x − µj : x ∈ Xj }. It is defined by the positive the nearest objects should be comparable to the ne-
semi-definite matrix G, such that xT Gx < 1, ∀x ∈ X c . arest neighbor distances between the objects. In fact,
Consequently, one has: this is the basic learning problem (?). A significant
difference to many later studies (?), however, is that
Assign x to ω1 , in domain learning probabilities or densities cannot be
if (x − µ2 )T G−1 (x − µ2 ) ≥ (x − µ1 )T G−1 (x − µ1 ), used.
Assign x to ω2 , Formally, the problem may be stated as follows. Let
if (x − µ2 )T G−1 (x − µ2 ) < (x − µ1 )T G−1 (x − µ1 ). Dj (x, θ) = 0 be some parametric domain description
(10) (with the parameters θ for the class ωj and let Xj be
The FLDD can then be written as: a set of examples from ωj . Then, θ should be cho-
sen such that the maximum distance from the domain
f (x) = (µ2 − µ1 )T G−1 x. (11) boundary to its nearest neighbor in the training set
is minimized under the condition that all training ob-
This classifier is optimal according to criterion (2) if jects are inside the domain at some suitable distance
the two classes are described by the identical ellipsoids δ to the border:
except for the position of their centers. The estimation
of G in the problem of finding the minimum volume minθ maxx∗ minx∈Xj kx∗ − xk,
ellipsoid enclosing the data X is a convex optimization s.t. (a) D(x∗ , θ) = 0,
problem which is only tractable in special cases (?; ?). (12)
An approximation is possible when the joint covariance s.t. (b) Dj (x, θ) < 0, ∀x ∈ Xj
matrix is used for pre-whitening the data (which, ho- (c) kx∗ − xk > δ, ∀x ∈ Xj
wever, conflicts with the concept of a domain classifier)
and then deriving a hypersphere instead of an ellipsoid.
This is a nonlinear optimization. As indicated above,
As a third possibility in this section we will mention such problems are intractable already for simple do-
the binary decision tree classifier based on the pu- mains like arbitrary ellipsoids (?). The challenge, the-
rity criterion (?), capturing aspects of partitioning of refore, is to find approximate and feasible solutions.
examples relevant to good classification. In each node Examples can be found in the area of one-class classi-
of the tree, the feature and a threshold are determined fiers (?; ?). A very problematic issue, however, is the
to distinguish the largest pure part (i.e. a range be- constraint (c) in (12) indicating that the domain bor-
longing to just one of the classes) of the training set. der should fit loosely, but in a restricted way around
Other more advanced ways of finding a domain based the training examples in the feature space. The diffi-
learner will be discussed below. culty arises as kx∗ − xk > δ is a non-convex constraint,
hence the entire formulation is non-convex3. In do- mean square error over the training set (?):
main learning, new algorithms have to be designed to
solve the formulated problems. 1 X
θ̂ = arg min (net(x, θ) − t(x))2 , (15)
θ n
Once class domains have been found, the problem of a x∈X
proper class assignment arises if objects get multiple where net(x, θ) is the network output for x and t(x) is
memberships or if they are rejected by all classes. If a the target, which is y(x) here. As the network function
unique decision is demanded in such cases, a discrimi- is nonlinear, training is done in small steps following
nant has to be determined, as discussed in section 3.1. a gradient descent approach. The summation over the
Alternatively, during classification, the distances to all training examples, however, conflicts with the domain
domain boundaries have to be found and the smallest, learning idea. If it is replaced by the maximum opera-
in the case of reject, or the largest, in the case of mul- tor, the network will be updated such that the ’worst’
tiple acceptance, has to be used for the final decision. object, i.e. the object closest to the domain of the other
Again, the criterion (2) is used. class, makes as smallest error as possible (it is as close
as possible to the decision border):
3.3. Model based, non-parametric decision
functions θ̂ = arg min max (net(x, θ) − t(x))2 (16)
θ x∈X
Instead of estimating the parameters of some postula-
ted model, such a model might be also directly con- A severe drawback, however, is that instead of opti-
structed from the training set, in analogy to the kernel mizing the distance to the decision boundary in the
density (Parzen) estimators (?) in statistical learning. input space, the largest deviation in the network out-
For a domain description, the sum of kernel functions, put space is optimized. Unless the network is linear,
however, may be replaced by a maximum, or, equiva- such as a traditional perceptron, this will yield a signi-
lently, by the union of the kernel domains. In order to ficantly different neural net.
restrict the class domains, the kernel domain should
be bounded. Let Φ(x, xi , h) define the domain for a 3.5. Support vector machines
kernel associated with xi , e.g. all points within a hy-
persphere with the radius h, then the domain estimate The key principle behind the support vector machine
for the class ωj is: (SVM), the structural risk minimization leading to the
maximum margin classifier, makes it an ideal candi-
[ date for domain learning. Thanks to the reproducing
Dj (x, h) = {Φ(x, xi , h)}. (13) property of kernels, in the case of non-overlapping clas-
xi ∈Xj ses, the SVM is a maximum margin hyperplane in a
Hilbert space induced by the specified kernel (?). The
The value of the kernel width h can be estimated by
margin is determined only by support vectors. These
the leave-one-out procedure. h is found as the smallest
are the boundary objects, i.e. the objects closest to the
value for which all training objects belong to the do-
decision boundary f (x, θ) (?; ?). As such, the SVM is
main which is estimated by all training objects except
independent of class density models:
the one to be classified. This width is equal to the
largest nearest neighbor distance found in the training f (x, θ) = arg max min y(x)f (x, θ). (17)
set: θ x∈X
ĥ = max min kxi − xl k. (14) Multiple copies of the same object added to the tra-
i l6=i
ining set do not contribute to the construction of the
Also in this case it is not straightforward how the di- SVM, as they do for classifiers based on some probabi-
stance to the domain boundary should be computed. listic model. Moreover, the SVM is also not affected if
objects which are further away from the decision bo-
3.4. Neural networks undary are disregarded or if objects of the same class
are added there. This decision function is, thereby,
The iterative way neural networks are trained make
truly domain based.
them suitable for domain learning. Traditionally, the
weights of a neural network are chosen to minimize the For nonlinear classifiers f (x, θ) defined on nonlinear
3 kernels, the SVM has, however, a similar drawback as
Convex optimization deals with a well-behaved set of
problems that have advantageous theoretical properties the nonlinear neural network. The distances to the
such as the duality theory and for which efficient algori- decision boundary are computed in the output Hilbert
thms exist. This is not true for non-convex problems. space defined by the kernel and not in the input space.
A second problem is that the soft-margin formulation
(?), the traditional solution to overlapping classes is 10
not domain based. The optimization problem for a
linear classifier f (x) = wT x + w0 is rewritten into: 5
P
minw ||w||2 + xi ∈X ξ(xi ),

Feature 2
s.t. yi f (xi ) ≥ 1 − ξ(xi ), (18) 0
ξ(xi ) ≥ 0
P
in which the term xi ∈X ξ(xi ) is an upper bound of −5
the misclassification error on the training set, hence it
is responsible for minimizing a sum of error contribu-
tions. Adding a copy of an erroneously assigned object −10
will affect the sum and, thereby, will influence the so- −15 −10 −5 0 5 10
ught optimum w. The result is, thereby, dependent on Feature 1
the distribution of objects, not just on their domain.
Figure 1. Example of the projection of a small set of ob-
For a proper domain based solution, formulation (17)
jects on a nonlinear decision boundary.
should be solved as it is for the case of overlapping do-
mains, resulting in the negative margin support vector
machine. This means that the distance of the fur- for the output space of nonlinear decision functions.
thest away misclassified object should be minimized. Still, well-performing classifiers may be obtained. The
As the signed distance is negative, the negative margin question, however, arises how evaluation and a com-
is obtained. In the probabilistic approach this classi- parison of classifiers that establish different nonline-
fier is unpopular as it will be sensitive to outliers. As arities,e.g. a linear classifier, a neural network and a
explained in the introduction, in domain learning, the support vector machine should be done.
existence of outliers should be neglected. This implies
that, if they exist, they should be removed before, as The only way various classification functions can be
they can only be detected on distribution information. compared is in their common input space, as their
output spaces may differ. In the introduction, crite-
rion (2) was adopted stating that the performance of a
4. Evaluation procedure domain based classifier is determined by the classifica-
tion of the most difficult example. It is determined by
In the previous section a number of possible domain
the distance in the input space from that object to the
based classifiers has been discussed, inspired by well
decision boundary. For linear classifiers the computa-
known probabilistic procedures. This is just an at-
tion of this distance is straightforward. For analytical
tempt to illustrate the key points of domain learning
nonlinear classifiers the computation of this distance is
approaches. Some of them are feasible, like the nearest
not trivial, but might be defined based on some opti-
center rule and the maximum error neural network.
mization procedure over the decision boundary. For
Others seem to be almost intractable as the question
arbitrary decision function, there is no way to derive
of determining multidimensional domains that fit aro-
this distance directly. In order to compare classifiers
und a given set of points lead to hard optimization
of various nature we propose the following heuristic
problems. Dropping the assumption that the proba-
procedure based on a stochastic approximation of the
bility distribution of the objects is representative for
distance of an object to the decision boundary:
the distribution of the target objects to be classified is
apparently very significant. The consequence is that
the statistical approach has to be replaced by an es- 1. Let f be a classifier found in the input space Rm .
timate of the shape of the class domains. The pro- Given an independent test set S, generate a large
blem of defining consistent classification procedures is set of objects R ∈ Rm that lie in the neighborhood
not the only one in domain learning. As it was alre- of the test examples.
ady noticed, for a proper optimization, the distance
2. Label the objects in S and R by the classifier f .
from the objects to the decision boundary or to the
domain boundary should be determined in the input 3. For each object xs in S find the k nearest objects
space. Here, the original object representation is defi- xir in R that are assigned different labels.
ned for the application, so the distances measured in
this space are related in a meaningful way to the dif- 4. Enrich this set {xir , i = 1, 2, . . . , k} by interpola-
ferences between objects. This relation does not hold tion.
 10 0
Nearest Center
Domain Fisherc −2
Decision Tree
5 NegMarginSVC−1 −4
NegMarginSVC−3

Performance
−6
Feature 2

0
−8

−10
−5 Nearest Center
−12 Domain Fisher
Decision Tree
−14 NegMarginSVC−1
−10 NegMarginSVC−3
−15 −10 −5 0 5 10 −16
0 10 20 30 40 50
Feature 1
Size training set per class

Figure 2. Five domain based classifiers on artificial data. Figure 3. Learning curves for the five domain based classi-
The three support objects of the linear Negative Margin fiers. As classes overlap, the performance (19) is negative.
SVM are indicated by circles. Higher performance indicates better results.

5. Use successive bisection to find the points xic that Negative Margin SVM using a linear kernel. As
are on the lines between xs and all xir such that the optimization problem is not quadratic, we im-
they are almost on the decision boundary induced plemented this classifier using boosting (?).
by f . Negative Margin SVM using a 3rd order polyno-
mial kernel.
6. Find the point xc in {xic } that is nearest to xs .

7. Use the distance d(xs , xc ) between xs and xc as a Two slightly overlapping artificial banana shaped clas-
measure for the confidence in the classification of ses are generated in two dimensions. Fig. 2 shows an
xs . If the true label of xs is known the distance example for 50 objects per class. The decision bo-
to xc may be given a sign: positive for a correct undaries for the above mentioned classifiers are also
label, negative for an incorrect one. presented there.
The following experiment is performed using a fixed
8. Use test set of 200 examples per class. Training sets of
eS = minxs ∈S d(xs , xc ) (19) the cardinalities up to 50 objects per class are genera-
ted, such that smaller sets are contained in the larger
as a performance measure for the evaluated clas- ones. For each training set the above classifiers are
sifier f given the test set S. determined and evaluated using the procedure discus-
sed in section 4. This is repeated 10 times and the
This proposed procedure has to be further evaluated. performances is averaged.
An example of the result of the projection of a small
test set on a given classifier is shown in fig. 1. Fig. 3 presents the results as a function of the cardina-
lity of the training set. These are the learning curves
of five classifiers showing an increasing performance as
5. Example a function of the training size. As the classes slightly
overlap, the performance (19) is negative. This is cau-
We implemented the following domain based classi-
sed by the fact that the ’worst’ classified object in the
fiers:
test set is erroneously labeled and is, thereby on the
wrong side of the decision boundary.
Nearest Center, NCC, based on (5).
The curves indicate that our implementation of the
Domain Fisher based on (11), using an heuristic es- Domain Fisher Discriminant is bad, at least for these
timate of G by pre-whitening the data followed by data. This might be understood that it is sensitive
the NCC to determine the class centers. for all class boundary points, to all sides. Enlarging
the dataset may yield more disturbances. The simpler
Decision Tree using the purity criterion. Nearest Center classifier performs much better and is
 about similar to the linear SVM. The nonlinear SVM vector machines and other kernel-based learning me-
as well as the Decision Tree yield very good results. thods. UK: Cambridge University Press.
Our evaluation procedure should bad for overlapping
training sets classified by the Decision Tree, as small Hochbaum and Shmoys][1985]Hochbaum85 Hoch-
regions separated out in different classes disturb the baum, D., & Shmoys, D. (1985). A best possible
procedure. They are, however, not detected if there heuristic for the k-center problem. Mathematics of
size is really small. The probability that inside such Operations Research, 10, 180–184.
a region a point is generated (compare the procedure Kulkarni and Zeitouni][1993]KulkarniZ93 Kulkarni,
discussed in section 4 may be too small. S. R., & Zeitouni, O. (1993). On probably correct
classification of concepts. COLT (pp. 111–116).
6. Conclusions
Parzen][1962]Parzen62 Parzen, E. (1962). On the esti-
Traditional ways of learning are inappropriate or in- mation of a probability density function and mode.
accurate if training sets are only representative for Annals of Math. Statistics, 33, 1065–1076.
the domain, but not for the distribution of the tar-
get objects. In this paper, a number of domain based Schapire][2002]Schapire02 Schapire, R. (2002). The
classifiers have been discussed. Instead of minimizing boosting approach to machine learning: An ove-
the expected number of classification errors, the mini- rview. MSRI Workshop on Nonlinear Estimation
mum distance to the decision boundary is proposed as and Classification.
a criterion. This is difficult to compute for arbitrary Schölkopf et al.][2001]Scholkopf01 Schölkopf, B., Platt,
nonlinear classifiers. A heuristic procedure based on J., Smola, A., & Williamson, R. (2001). Estimating
generating points close to the decision boundary is pro- the support of a high-dimensional distribution. Neu-
posed for classifier evaluation. ral Computation, 13, 1443–1471.
This paper is restricted to an introduction to domain
Tax][2001]Tax2001 Tax, D. (2001). One-class classi-
learning. It formulates the problem, points towards
fication. Doctoral dissertation, Delft University of
possible solutions and gives some examples. A first se-
Technology, The Netherlands.
ries of domain based classifiers has been implemented.
Much research has to be done to make the domain ba- Tax and Duin][1999]TaxDui1999a Tax, D., & Duin, R.
sed classification approach ready for applications. As (1999). Support vector domain description. Pattern
there is a large need for novel approaches in this area, Recognition Letters, 20, 1191–1199.
we believe that an important new theoretical direction
for further investigation is identified. Valiant][1984]Valiant84 Valiant, L. G. (1984). A the-
ory of the learnable. Commun. ACM, 27, 1134–1142.
Acknowledgments Vandenberghe and Boyd][1996]BerBoy1996 Vanden-
berghe, L., & Boyd, S. (1996). Semidefinite pro-
This work is supported by the Dutch Organization for
gramming. SIAM Review, 38, 49–95.
Scientific Research (NWO).
Vapnik][1998]Vapnik Vapnik, V. (1998). Statistical le-
References arning theory. John Wiley & Sons, Inc.

Bishop][1995]Bishop95 Bishop, C. (1995). Neural ne-

tworks for pattern recognition. Oxford: Oxford Uni-
versity Press.

Boyd and Vandenberghe][2004]BoyBer2004 Boyd, S.,

& Vandenberghe, L. (2004). Convex optimization.
Cambridge University Press.

Breiman et al.][1984]Breiman84 Breiman, L., et al.

(1984). Classification and regression trees. Wad-
sworth.

Cristianini and Shawe-Taylor][2000]Cristianini00 Cri-

stianini, N., & Shawe-Taylor, J. (2000). Support

View publication stats