Enlarging the Margins in Perceptron Decision Trees.
Capacity control in perceptron decision trees is typically performed by controlling their size. We prove that other quantities can be as relevant to reduce their flexibility and combat overfitting. In particular, we provide an upper bound on the generalization error which depends both on the size of the tree and on the margin of the decision nodes. So enlarging the margin in perceptron decision trees will reduce the upper bound on generalization error. Based on this analysis, we introduce three new algorithms, which can induce large margin perceptron decision trees. To assess the effect of the large margin bias, OC1 (Journal of Artificial Intelligence Research, 1994, 2, 132.) of Murthy, Kasif and Salzberg, a well-known system for inducing perceptron decision trees, is used as the baseline algorithm. An extensive experimental study on real world data showed that all three new algorithms perform better or at least not significantly worse than OC1 on almost every dataset with only one exception. OC1 performed worse than the best margin-based method on every dataset.
Introduction
Perceptron Decision Trees (PDT) have been introduced by a number of authors under different
names [17, 6, 7, 8, 10, 11, 27, 18]. They are decision trees in which each internal
node is associated with a hyperplane in general position in the input space. They have been
used in many real world pattern classification tasks, with good results [7, 18, 9]. Given their
high flexibility, a feature that they share with more standard decision trees such as the ones
produced by C4.5 [20], they tend to overfit the data if their complexity is not somehow kept
under control. The standard approach to controlling their complexity is to limit their size,
with early stopping or pruning procedures.
In this paper we introduce a novel approach to complexity control in PDTs, based on the
concept of the margin (namely, the distance between the decision boundaries and the training
points). The control of this quantity is at the basis of the e#ectiveness of other systems,
such as Vapnik's Support Vector Machines [12], Adaboost [24], and some Bayesian Classifiers
[13]. We prove that this quantity can be as important as the tree-size as a capacity control
parameter.
The theoretical motivations behind this approach lie in the Data-Dependent Structural Risk
Minimization [25]: the scale of the cover used in VC theory to provide a bound on the generalization
error depends on the margin and hence the hierarchy of classes is chosen in response
to the data. Of course the two complexity control criteria can be used together, combining
a pruning phase with the bias towards large margins, to obtain a better performance.
These results motivate a new class of PDT learning algorithms, aimed at producing large
margin trees. We propose three such algorithms: FAT, MOC1 and MOC2, and compare
their performance with that of OC1, one of the best known PDT learning systems. All three
large-margin systems outperform OC1 on most of the real world data-sets we have used,
indicating that overfitting in PDTs can be e#ciently combatted by enlarging the margin of
the decision boundaries on the training data.
Perceptron Decision Trees
The most common decision trees, in which each node checks the value of a single attribute,
could be defined as axis parallel, because the tests associated with each node are equivalent
to axis-parallel hyperplanes in the input space. Many variations of this simple model have
been proposed, since the introduction of such systems in the early '80s. Some of them involve
more complex tests at the decision nodes, usually testing more than one attribute.
Decision Trees whose nodes test a linear combination of the attributes have been proposed
by di#erent researchers under di#erent names: Linear Combination Trees, multivariate DT
[11], oblique DTs [18], Perceptron Decision Trees [27], etc. The first of such systems was
proposed by Breiman, who incorporated it into the package CART[10]. The tests associated
at each node are equivalent to hyperplanes in general position, and they partition the input
space into polyhedra as illustrated in Figure 1. They obviously include as a special case the
more common decision trees output by systems like C4.5.
x
x
x
x
x
x
x
x
x
x
x
x
x
x

Figure

1: A Perceptron Decision Tree and the way it splits the input space
The extreme flexibility of such systems makes them particularly exposed to the risk of
overfitting. This is why e#cient methods for controlling their expressive power (typically
pruning techniques) have always to be used in combination with the standard TopDown
growth algorithms.
The class of functions computed by PDTs is formally defined as follows.
Definition 2.1 Generalized Decision Trees (GDT). Given a space X and a set of boolean
functions the class GDT(F) of Generalized Decision Trees over
F are functions which can be implemented using a binary tree where each internal node is
labeled with an element of F , and each leaf is labeled with either 1 or 0.
To evaluate a particular tree T on input x # X, all the boolean functions associated to the
nodes are assigned the same argument x # X, which is the argument of T (x). The values
assumed by them determine a unique path from the root to a leaf: at each internal node
the left (respectively right) edge to a child is taken if the output of the function associated
to that internal node is 0 (respectively 1). This path is known as the evaluation path. The
value of the function T (x) is the value associated to the leaf reached. We say that input x
reaches a node of the tree, if that node is on the evaluation path for x.
In the following, the nodes are the internal nodes of the binary tree, and the leaves are its
external ones.
Examples.
. Given Tree (BDT) is a GDT over
. Given Tree (CDT) is a GDT over
This kind of decision tree defined on a continuous space are the output of common
algorithms like C4.5 and CART, and we will refer to them as CDTs.
. Given Tree (PDT) is a GDT over
where we have assumed that the inputs have been augmented with a coordinate of
constant value, hence implementing a thresholded perceptron.
PDTs are generally induced by means of a TopDown growth procedure, which starts from the
root node and greedily chooses a perceptron which maximizes some cost function, usually a
measure of the "impurity" of the subsamples implicitly defined by the split. This maximization
is usually hard to perform, and sometimes replaced by randomized (sub)optimization.
The subsamples are then mapped to the two children nodes. The procedure is then recursively
applied to the nodes, and the tree is grown until some stopping criterion is met. Such
a tree is then used as a starting point for a "BottomUp" search, performing a pruning of the
tree. This implies eliminating the nodes which are redundant, or which are unable to "pay
for themselves" in terms of the cost function. Generally pruning an overfitting tree produces
better classifiers than those obtained with early stopping, since this makes it possible to
check if promising directions were in fact worth exploring, and if locally good solutions were
on the contrary a dead-end. So, while the standard TopDown algorithm is an extremely
greedy procedure, with the introduction of pruning it can be possible to look-ahead: this
allows for discovery of more hidden structure.
The capacity control in PDTs is hence completely achieved by controlling the size of the tree,
that is the complexity of the overall classifier. We will propose an alternative method, which
on the contrary focuses on reducing the complexity of the node classifiers, independently
of the tree size. This will be possible thanks to a theoretical analysis of generalization
performance of the function class defined by PDTs, in the framework of VC theory.
Theoretical Analysis of Generalization
The generalization performance of a learning machine can be studied by means of uniform
convergence bounds, with a technique introduced by Vapnik and Chervonenkis [30]. The
central concept in such an analysis is the "e#ective capacity" of the class of hypotheses
accessible by the machine: the richer such a class, the higher the risk of overfitting. This
feature of a learning machine is often referred to as its flexibility or capacity. The issue of
preventing overfitting by allowing just the right amount of flexibility is therefore known as
capacity control.
The notion of e#ective cardinality of a function class is captured by its "growth function"
for Boolean classes or "covering numbers" for real valued functions. The size of the covering
numbers depends on the accuracy of the covering as well as the function class itself. The
larger the margin the less accuracy is required in the covering.
In the following we will be concerned with estimating the capacity of the class of PDTs. We
will see that the margin does a#ect the flexibility of such a hypothesis class, as does the
tree-size. This will motivate some alternative techniques for controlling overfitting which -
albeit conceptually similar to pruning - act on the complexity of the node classifiers rather
than on the complexity of the overall tree.
We begin with the definition of the fat-shattering dimension, which was first introduced in
[15], and has been used for several problems in learning since [1, 4, 2, 3].
Definition 3.1 Let F be a set of real valued functions. We say that a set of points X is
#-shattered by F relative to there are real numbers r x indexed by x # X such
that for all binary vectors b indexed by X, there is a function f b # F satisfying
The fat shattering dimension fat F of the set F is a function from the positive real numbers
to the integers which maps a value # to the size of the largest #-shattered set, if this is finite,
or infinity otherwise.
As an example which will be relevant to the subsequent analysis consider the class:
We quote the following result from [5](see also [12]).
Theorem 3.2 [5] Let F lin be restricted to points in a ball of n dimensions of radius R about
the origin. Then
The following theorem bounds the generalization of a classifier in terms of the fat shattering
dimension rather than the usual Vapnik-Chervonenkis or Pseudo dimension.
Let T # denote the threshold function at #: T # For a class
of functions F , T #
Theorem 3.3 [25] Consider a real valued function class F having fat shattering function
bounded above by the function afat : R # N which is continuous from the right. Fix # R. If
a learner correctly classifies m independently generated examples z with
such that the train error is zero and then with confidence 1 - # the
expected error of h is bounded from above by
#(m, k, #) =m
8em
The importance of this theorem is that it can be used to explain how a classifier can give
better generalization than would be predicted by a classical analysis of its VC dimension.
Essentially expanding the margin performs an automatic capacity control for function classes
with small fat shattering dimensions. The theorem shows that when a large margin is
achieved it is as if we were working in a lower VC class.
We should stress that in general the bounds obtained should be better for cases where a large
margin is observed, but that a priori there is no guarantee that such a margin will occur.
Therefore a priori only the classical VC bound can be used. In view of corresponding lower
bounds on the generalization error in terms of the VC dimension, the a posteriori bounds
depend on a favorable probability distribution making the actual learning task easier. Hence,
the result will only be useful if the distribution is favorable or at least not adversarial. In this
sense the result is a distribution dependent result, despite not being distribution dependent
in the traditional sense that assumptions about the distribution have had to be made in
its derivation. The benign behavior of the distribution is automatically estimated in the
learning process.
In order to perform a similar analysis for perceptron decision trees we will consider the set
of margins obtained at each of the nodes, bounding the generalization as a function of these
values.
It turns out that bounding the fat shattering dimension of PDT's viewed as real function
classifiers is di#cult. We will therefore do a direct generalization analysis mimicking the
proof of Theorem 3.3 but taking into account the margins at each of the decision nodes in
the tree.
Definition 3.4 Let (X, d) be a (pseudo-) metric space, let A be a subset of X and # > 0. A
set is an #-cover for A if, for every a # A, there exists b # B such that d(a, b) < #.
The #-covering number of A, N d (#, A), is the minimal cardinality of an #-cover for A (if
there is no such finite cover then it is defined to be #).
We for the #-covering number of F with respect to the # pseudo-metric
measuring the maximum discrepancy on the sample x, that is with respect to the distance
F . These numbers are bounded in the following
Lemma, which we present for historical reasons, though in fact we will require the slightly
more general corollary.
Lemma 3.5 (Alon et al. [1]) Let F be a class of functions X # [0, 1] and P a distribution
over X. Choose 0 < # < 1 and let
where the expectation E is taken w.r.t. a sample x drawn according to P m .
Corollary 3.6 [25] Let F be a class of functions X # [a, b] and P a distribution over X.
Choose
where the expectation E is over samples x drawn according to P m .
We are now in a position to tackle the main lemma which bounds the probability over
a double sample that the first half has zero error and the second error greater than an
appropriate #. Here, error is interpreted as being di#erently classified at the output of the
tree. In order to simplify the notation in the following lemma we assume that the decision
tree has K nodes and we denote fat F lin (#) by fat(#).
Lemma 3.7 Let T be a perceptron decision tree with K decision nodes with margins # 1 , # 2 , . , # K
at the decision nodes satisfying k If it has correctly classified m labeled examples
x generated independently according to the unknown (but fixed) distribution P with support
in a ball of radius R and y is a second m sample, then we can bound the following probability
to be less than #,
xy: # a tree correctly classifies x,
fraction of y misclassified > #(m, K, #)
< #,
where #(m, K,
(D log(8m)
Using the standard permutation argument (as in [30]), we may fix a sequence xy
and bound the probability under the uniform distribution on swapping permutations that
the sequence satisfies the condition stated. We consider generating minimal # k /2-covers
xy for each value of k, where # Suppose that for node i of
the tree the margin # i of the hyperplane w i satisfies . We can therefore find
xy whose output values are within # i /2 of w i . We now consider the tree T # obtained
by replacing the node perceptrons w i of T with the corresponding f i . This tree performs the
same classification function on the first half of the sample, and the margin at node i remains
larger than # i
a point in the second half of the sample is incorrectly
classified by T it will either still be incorrectly classified by the adapted tree T # or will at
one of the decision nodes i in T # be closer to the decision boundary than # k i /2. The point is
thus distinguishable from left hand side points which are both correctly classified and have
margin greater than # k i /2 at node i. Hence, that point must be kept on the right hand side
in order for the condition to be satisfied. Hence, the fraction of permutations that can be
allowed for one choice of the functions from the covers is 2 -#m . We must take the union
bound over all choices of the functions from the covers. Using the techniques of [25] the
numbers of these choices is bounded by Corollary 3.6 as follows
The value of # in the lemma statement therefore ensures
that the union bound is less than #
Lemma 3.7 applies to a particular tree with a specified number of nodes, architecture and
fat shattering dimensions for each node. In practice we will observe these quantities after
running the learning algorithm which generates the tree. Hence, to obtain a bound that can
be applied in practice we must bound the probabilities uniformly over all of the possible
architectures and dimensions that can arise. Before giving the theorem that will give this
bound we require two results. The first is due to Vapnik [28, page 168] and is the key to
bounding error probabilities in terms of the probabilities of discrepancies on a double sample.
Lemma 3.8 Let X be a set and S a system of sets on X, and P a probability measure on
X. For x
A#S
A#S
The second result gives a bound on the number of di#erent tree architectures that have a
given number of computational nodes.
Theorem 3.9 [21] The number S k of k node Decision Tree skeletons is
# .
Combining these two results with Lemma 3.7 we obtain the following theorem.
Theorem 3.10 Suppose we are able to classify an m sample of labeled examples using a
perceptron decision tree and suppose that the tree obtained contained K decision nodes with
margins # i at node i, then we can bound the generalization error with probability greater than
to be less than
where
, and R is the radius of a sphere containing the support of the distribution
We must bound the probabilities over di#erent architectures of trees and di#erent
margins. We first use Lemma 3.8 to bound the probability of error in terms of the probability
of the discrepancy between the performance on two halves of a double sample. In order to
apply Lemma 3.7 we must consider all possible architectures that can occur and for each
architecture the di#erent patterns of k i 's over the decision nodes. For a fixed value of K
Theorem 3.9 gives the number of decision tree skeletons. The largest allowed value of k i is
m and so for fixed K we can bound the number of possibilities
counts the possible labeling of the K+1 leaf nodes. Hence, there are this number
of applications of Lemma 3.7 for a fixed K. Since the largest value that K can take is m,
we can let # so that the sum
Choosing
in the applications of Lemma 3.7, ensures that the probability of any of the statements
failing to hold is less than #/2. Note that we have replaced the constant 8
order to ensure the continuity from the right required for the application of Theorem 3.3
and have upperbounded log(4em/k i ) by log(4em). Hence, applying Lemma 3.8 in each case
the probability that the statement of the theorem fails to hold is less than #
4 Experimental Results
From the theory presented in the previous section, it follows that large-margin PDTs are
more likely to generalize well. A bias toward large-margin trees can be implemented in a
number of di#erent ways, either as a post-processing phase of existing trees or as a brand new
impurity measure to determine splitting/stopping criteria in TopDown growth algorithms.
To facilitate comparisons, we have implemented three such algorithms as modifications of
one of the best-known PDT learning systems OC1 [18] of Murthy, Kasif and Salzberg, which
is freely available over the Internet. The e#ect of the large-margin bias can hence be directly
assessed, by running the margin-arbitrary version of the same algorithm on the same data.
The first such algorithm, FAT, accepts in input a PDT constructed using OC1 and outputs
a large margin version of the same tree. The other two, MOC1 and MOC2, have di#erent
impurity measures which take into consideration the margins. All three algorithms work for
multi-class data.
The three systems have been compared with OC1 on 10 benchmarking data sets. The results
confirm the predictions of the theoretical model, clearly indicating that the generalization is
improved by enlarging the margin.
The data sets we have used for the study are 6 data sets used in the original OC1 paper[18],
and 4 other data sets, which are publicly available in the UCI data repository [31]. The
data sets studied in [18] are Dim, Bright, Wisconsin Breast Cancer, Pima Indians Diabetes,
Boston Housing and Iris. The four additional data sets are Bupa, Sonar, Heart and Wisconsin
Breast Cancer Prognosis. The data sets di#er greatly from subjects, sizes and number of
attributes, the subjects of data sets range from medical to astronomical, sizes from 150 to
4192, number of attributes from 4 to 60 1 . For details of these data sets see [18, 31]. For
each data set, a single run of 10-fold cross-validation is carried out. The relevant quantity, in
this experiment, is the di#erence in the test accuracy between PDTs with arbitrary margins
constructed by OC1 and the PDTs with large margins on the same data.
Comparing learning algorithms has drawn extensive attention recently [16, 14, 23, 19]. A
single run of 10-fold cross-validation on a reasonable number of data sets is still a preferred
1 The number of (attributes, points) of each data set is as following: Bright(14,2462), Bupa(6,345), Can-
cer(9, 682), Dim(14, 4192), Heart(13, 297) Housing( 13,506), Iris(4, 150), Pima(8, 768), Prognosis(32,198),
practical approach. It is prone to detect the di#erence of two algorithms. We basically
followed the approach recommended in [23].
In the rest of this section, first we will briefly review the OC1 system, then present our three
large margin algorithms, and compare their performances with OC1.
4.1 Review of OC1
OC1 [18] is a randomized algorithm, which performs a randomized hill-climbing search for
learning the perceptrons, and builds the tree TopDown. Starting from the root node, the
system chooses the hyperplane which minimizes a predefined "impurity" measure (e.g. information
gain [20], or Gini index [10], or the Twoing Rule [10, 18], etc. The system is greedy
because at each stage it chooses the best split available, and randomized because such a
best split is not obtained by means of exhaustive search but with a randomized hill-climbing
process.
Throughout this study we use the twoing rule as the impurity measure, for OC1, FAT, and
MOC1. MOC2 uses a modified twoing rule as impurity measure. Other impurity measures
can also be applied in FAT and MOC1 without change, while MOC2 would need minor
changes.
The Twoing Rule
(1)
where
total number of instances at current node
number of classes, for two class problems,
number of instances on the left of the split, i.e. w
number of instances on the right of the split i.e. w
number of instances in category i on the the left of the split
number of instances in category i on the the right of the split
This is a goodness measure rather than an impurity one, and OC1 attempts to maximize it
at each split during the tree growth via minimizing 1/TwoingV alue. Further details about
the randomization, the pruning, and the splitting criteria can be found in [18].
4.2 Results of FAT
Description of algorithm FAT
The algorithm FAT uses the tree produced by OC1 as a starting point, and maximizes
its margins. This involves finding - for each node - the hyperplane which performs the
same split as performed by the OC1 tree but with the maximal margin. This can be done
by considering the subsample reaching each node as perfectly divided into two parts, and
feeding the data accordingly relabeled to an algorithm which finds the optimal separating
separating hyperplane with maximal margin in this now linearly separable data.
The optimal separating hyperplanes are then placed in the corresponding decision nodes and
the new tree is tested on the same test data. Note that, the PDT produced by FAT will
have the same tree structure and training accuracy as the original PDT constructed by OC1.
They will only di#er on test accuracy. We use the Support Vector Machine (SVM) algorithm
[29] to find the optimal separating hyperplane. To conform with the definition of a PDT,
no kernel is used in the SVM, the optimal separating hyperplane is constructed in the input
space.
Algorithm for FAT
1. Construct a decision tree using OC1, call it OC1-PDT.
2. Starting from root of OC1-PDT, traverses through all the non-leaf nodes. At each
node,
. Relabel the points at this node with # T x class right, the other points
at this node as class left.
. Find the perceptron (optimal separating hyperplane)
separates class right and class left perfectly with maximal margin.
. replace the original perceptron with the new one.
3. Output the FAT-PDT.
Optimal Separating Hyperplane - SVM algorithm for the linearly separable case
The following problems are solved at each node, to find the optimal separating hyperplane
for linearly separable data [29].
min
subject to y i (w T x
corresponds to class right and y corresponds to class left and # is the
number of points reaching the decision node.
For computational reason we usually solve the dual problem of (2):
min
subject to #
FAT-PDT has a generalization error bounded by theorem 3.10. We observed that FAT completely
relied on and was restricted by the perceptron decision tree induced by OC1. In
many cases, the margins in the splits found by OC1 are very small, so FAT has little scope
for optimization. In general, if there is a big margin in the top split at the root node, FAT
will generalize much better. It implies that the greedy algorithm OC1 is not a good tree
inducer for FAT, in the sense of the margin. We need to find a better non-greedy tree inducer
for FAT. On the other hand, FAT provides a new approach to applying the Support Vector
Machine for multi-class classification tasks.
Comparison of FAT and OC1
For each dataset, 10-fold cross-validation is used to measure the learning ability of the
algorithm FAT and OC1. A paired t-test is used to test the di#erence of the means of FAT
and OC1.
10-fold cross-validation results: FAT vs OC1
OC1 10-fold CV average accuracy
FAT
10-fold
average
accuracy
significant
not significant
x=y

Figure

2: Comparison of the 10-fold CV results of FAT versus OC1. If the point is above
the line, it indicates the 10-fold CV mean of FAT is higher than that of OC1, and vice versa.
The figure shows that FAT outperforms OC1 on 9 out of 10 data sets and is outperformed
only on 1 data set.
From

Figure

2, we can see that, FAT outperforms OC1 on 9 out of the 10 data sets, and
outperforms OC1 on all the 6 data sets studied in [18]. The 10-fold cross-validation mean
di#erences of FAT and OC1 on those 9 data sets are all significant when a paired t-test is
applied. On one data set Prognosis, OC1 outperforms FAT and the di#erence is significant.
We also observed that, except in one case (Prognosis), FAT performs as good as or better than
OC1 in every fold of 10-fold cross-validation. So when FAT has a higher mean than OC1, it
is significant at a small # level for the paired t-test even though the di#erence is small. This
is a strong indication that Perceptron Decision Trees with large margins generalize better.
The 10-fold cross-validation means and p values are summarized in Table 2.
4.3 Results of MOC1
Description of MOC1
MOC1 (Margin OC1) is a variation of OC1, which modifies the objective function of OC1
to consider the size of the margin. The underlying philosophy is to find a separating plane
with a tradeo# between training accuracy and the size of margin at each node. This idea
is motivated by the Support Vector Machine for the linearly non-separable case, which
minimizes the classification error and maximizes the margin at the same time. SVM with
soft margin minimizes the sum of misclassification errors and a constant C multiplying the
reciprocal of the soft margin. SVM tries to find a split with high classification accuracy
and large soft margin. Analagously, SVM minimizes the sum of the impurity measure and a
constant times the reciprocal of the hard margin.
The MOC1 algorithm minimizes the following objective function:
where
Objective is the impurity measure of OC1, in this study, the default twoing
rule is used as impurity measure.
current margin is the sum of perpendicular distances to the hyperplane of two
nearest points on the di#erent side of the current separating hyperplane.
- # is a scalar weight, # [0, 1]
of points at current node)}
# determines how much the large margin is weighted in selecting the split. Tuning # could
improve the performance. When determining the weight of the margin, we also take the
number of points at the current node into consideration. The idea is that a constant weight
of margin for all nodes is not good. The weight should be able to adapt to the position of
current node and size of training examples at the current node. Since we are not particularly
interested in finding the tree with highest possible accuracy, but rather demonstrating that
large margins can improve the generalization, we did not tune the # for each data set to
achieve the highest possible accuracy. We set data sets. In other words, the
results of MOC1 presented below are not the best results possible.
Comparison of MOC1 and OC1
As in the previous section, we use 10-fold cross-validation to measure the learning ability
of the algorithm MOC1 and OC1. To test the di#erence between the means of MOC1 and
OC1, here again a paired t-test is used.
From figure 3, we can see that MOC1 has higher 10-fold cross-validation mean than that
of OC1 on 8 of the 10 data sets, and 5 of them are significantly higher; OC1 has higher
means on the other two data sets (Cancer, Prognosis), the di#erences are tiny and both are
not significant. Overall, MOC1 outperforms OC1 on 6 of the 10 data sets and as good as
OC1 on the other four. Of the six data sets studied in [18], MOC1 outperforms OC1 on five
of them and performs as well as OC1 on the final one (Cancer). See table 2 for respective
means and p values.
OC1 10-CV average accuracy
MOC1
average
accuracy
significant
not significant
x=y

Figure

3: Comparison of the 10-fold CV results of MOC1 versus OC1. If the point is above
the line, it indicates the 10-fold CV average of MOC1 is higher than that of OC1, and vice
versa. The figure shows that MOC1 outperforms OC1 on 6 out of 10 data sets, and performs
as good as OC1 on the other four data sets.
4.4 Results of MOC2
Description of MOC2
MOC2 uses a modified twoing rule, which directly incorporates the idea of large margin to the
impurity measure. Unlike MOC1, MOC2 uses a soft margin. It treats points falling within
the margin and outside of the margin di#erently. Only the impurity measure is altered. The
rest is same as in the standard OC1 algorithm.
The modified twoing rule
|MTR |
where
total number of instances at current node
number of classes, for two class problems
number of instances on the left of the split, i.e. w
number of instances on the right of the split i.e. w
number of instances in category i on the left of the split
number of instances in category i on the the right of the split
number of instances on the left of the split, w
|MTR | - number of instances on the right of the split w
number of instances in category i with w
number of instances in category i with w
In the modified twoing rule, our goal is, at each node, to find a split with fewer points falling
within the margin (in between accuracy outside the margin
and good overall accuracy. Here again, we try to achieve a balance of classification accuracy
and size of margin. By doing this, we want to push apart the two classes from the the
separating hyperplane as far as possible while maintaining a reasonable good classification
accuracy, hence, improve the generalization of the induced decision tree. The advantage of
MOC2 is that there are no free parameters to tune.
Comparison of MOC2 and OC1
As in previous section, 10-fold cross-validation is used to measure the learning ability of the
algorithms MOC2 and OC1. Paired t-tests are used to test the di#erence of the means of
MOC2 and OC1.
From

Figure

4 we can see that MOC2 has higher mean on 9 out of the 10 data sets, and has
slightly lower mean on only one data set (Housing). Of the 9 higher means, 5 are significantly
higher. The one lower mean is not significant. Overall, MOC2 outperforms OC1 on 5 out of
OC1 10-CV average accuracy
MOC2
average
accuracy
10-fold cross validation results: MOC2 vs OC1
significant
not significant
x=y

Figure

4: Comparison of the 10-fold CV results of MOC2 versus OC1. If the point is above
the line, it indicates the 10-fold CV mean of MOC2 is higher than that of OC1 on that data
set, and vice versa. The figure shows that MOC2 outperforms OC1 on 5 out of 10 data sets,
and performs as well as OC1 on the other 5 data sets.
the 10 data sets and performs as well as OC1 on the other 5. Of the six data sets studied in
[18], MOC2 outperformed OC1 on three of them, and perform as well as OC1 on the other
three. The respective means and p values are summarized in Table 2
The modified twoing rule opens a new way of measuring the goodness of a split, which
directly incorporates the generalization factor into the measure. In our experiments, it has
been proven to be a useful measure.
4.5 Tree Sizes
For FAT, the tree sizes are exactly the same as OC1, since FAT PDT has the same tree
structure as OC1 PDT. FAT only replaces splits at nodes of the OC1 PDT with large-
margin perceptrons which perform exactly the same splits. Of the ten data sets, MOC1
induced five smaller trees, one the same size tree, and four larger trees when compared with
Leaves Depth Leaves Depth Leaves Depth
Bright 5.40 2.80 6.20 3.20 5.70 2.90
Bupa 5.00 2.80 2.10 1.10 7.40 3.60
Cancer 2.50 1.30 4.00 2.50 2.90 1.50
Heart 6.10 2.10 3.30 2.00 2.10 1.10
Housing 10.00 4.20 7.10 3.80 6.40 3.00
Iris 3.20 2.10 3.20 2.10 3.00 2.00
Prognosis 3.60 2.00 2.30 1.20 2.20 1.10
Sonar 4.30 2.60 6.10 3.30 5.90 2.90

Table

1: 10-fold CV average tree size of OC1, FAT, MOC1 and MOC2
x (p value) -
x (p value) -
x (p value) classifier
Bright 98.46 98.62 (.05) 98.94 (.10) 98.82 (.10) MOC1
Cancer 95.89 96.48 (.05) 95.60 95.89 FAT
Heart 73.40 76.43 (.12) 75.76 (.21) 77.78 (.10) MOC2
Housing 81.03 83.20 (.05) 82.02 80.23 FAT
Iris 95.33 96.00 (.17) 95.33 96.00 FAT
Pima 71.09 71.48 (.04) 73.18 (.08) 72.53 (.23) MOC1
Prognosis 78.91 74.15 78.23 79.59 MOC2

Table

2: 10-fold CV means of OC1, FAT, MOC1 and MOC2
OC1. MOC2 induced five smaller trees and five bigger trees compared with OC1. We did
not find consistent pattern of tree sizes. Table 1 list the tree sizes of OC1, FAT, MOC1 and
MOC2.
4.6 Summary of experimental results
The theory states that maximizing the margins between the data points on each side of
separating hyperplane in the perceptron decision tree will improve the error bounds, the
perceptron decision tree will be more likely to generalize better. But the theory does not
guarantee a specific classifier has a low error rate.
From the 10-fold cross-validation results of the 10 data sets, FAT has 9 higher means than
OC1 and they are all significantly higher; MOC1 has 7 higher means, and 6 of them are
significantly higher; MOC2 has 8 higher means and 5 of them are significantly higher. Equal
or lower means only happened on 3 data sets, Cancer, MOC1 has a slightly smaller mean
than OC1 on it, MOC2 has the same mean as OC1 on it; Housing, MOC2 has slightly smaller
mean than OC1 on it; Prognosis, FAT has a significantly smaller mean on it, MOC1 also has
a slightly smaller mean but the di#erence is not significant. Of the classifiers with highest
mean, FAT produced four, MOC1 and MOC2 each produced three, and OC1 produced none.
From the experiments, we believe that PDTs with large margin are more likely to have
smaller variance of performance too. In our experiments, in most of the cases, FAT, MOC1
and MOC2 produce classifiers with smaller variances, and many of them are significantly
smaller, though very occasionally they produce classifiers with significantly larger variance.
However, we cannot draw any confident conclusion about the variances. We therefore did
not present our study on variances here.
In short, the experimental results show that finding the separating hyperplane with large
margin at each node of a perceptron decision tree can improve the error bound, hence the
PDT is more likely to have a higher average accuracy, i.e. generalizes better. Furthermore,
we believe, by improving error bounds through margin maximization, the learning algorithm
will perform more consistently, and be more likely to have smaller variance as well.
Conclusions
The experimental results presented in this paper clearly show that enlarging the margin
does improve the generalization, and that this bias can be inserted into the growth algorithm
itself, providing trees which are specifically built to minimize the theoretical bound
on generalization error. Such trees do not lose any of their other desirable features, such as
readability, ease of maintenance and updating, flexibility and speed.
Furthermore, the theoretical analysis of the algorithms shows that the dimension of the
input space does not a#ect the generalization performance: it is hence possible to conceive
of Perceptron Decision Trees in a high-dimensional feature space, which take advantage of
kernels and margin-maximization such as Support Vector Machines. This would provide
as a side e#ect a very natural approach to multi-class classification with Support Vector
Machines.
Other theoretical results exist indicating that the tree size is not necessarily a good measure of
capacity. Our analysis also shows how to take advantage of this theoretical observation, and
design learning algorithms which control hypothesis complexity by acting on the complexity
of the node-classifiers and hence that of the whole tree. All three of the proposed approaches,
the post-processing method FAT, and the two with margin based splitting criteria MOC1
and MOC2 led to significant improvement over the baseline OC1 method. It is an open
question which method is best, but maximizing margins should be a consideration of every
PDT algorithm.



--R


Function learning from interpolation


Generalization performance of Support Vector Machines and other pattern classifiers.
Robust Linear Programming discrimination of two linearly inseparable sets
Multicategory discrimination via linear program- ming
Serial and parallel multicategory discrimination
On Support Vector Decision Trees for Database Marketing
Olshen R.


Bayesian Classifiers are Large Margin Hyperplanes in a Hilbert Space
Approximate Statistical Tests for Comparing Supervised Classification Learning Algorithms.

A study of Cross-Validation and Bootstraping for Accuracy Estimation and Model Selection
Pattern Recognition via Linear Pro- gramming: Theory and application to medical diagnosis
Kasif S.
Assessing Relevance Determination Methods Using DELVE Generalization in Neural Networks and Machine Learning

Learning Decision Trees Using the Minimum Description Lenght Principle
Growing and Pruning Neural Tree Networks
On Comparing Classifiers: Pitfalls to Avoid and a Recommended Approach.
Boosting the Margin: A New Explanation for the E
Structural Risk Minimization over Data-Dependent Hierarchies
"Neural trees: a new tool for classification"

Estimation of Dependences Based on Empirical Data
The Nature of Statistical Learning Theory
On the Uniform Convergence of Relative Frequencies of Events to their Probabilities
University of California
--TR
Inferring decision trees using the minimum description length principle
C4.5: programs for machine learning
Multivariate Decision Trees
The nature of statistical learning theory
Networks
Fat-shattering and the learnability of real-valued functions
Scale-sensitive dimensions, uniform convergence, and learnability
Generalization performance of support vector machines and other pattern classifiers
Approximate statistical tests for comparing supervised classification learning algorithms
On Comparing Classifiers
Growing and Pruning Neural Tree Networks
Boosting the margin
Bayesian Classifiers Are Large Margin Hyperplanes in a Hilbert Space
Function learning from interpolation

--CTR
Volkan Vural , Jennifer G. Dy, A hierarchical method for multi-class support vector machines, Proceedings of the twenty-first international conference on Machine learning, p.105, July 04-08, 2004, Banff, Alberta, Canada
Nello Cristianini , Colin Campbell , Chris Burges, Editorial: Kernel Methods: Current Research and Future Directions, Machine Learning, v.46 n.1-3, p.5-9, 2002
Laurence Hirsch , Robin Hirsch , Masoud Saeedi, Evolving Lucene search queries for text classification, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England
Martin Anthony, On the generalization error of fixed combinations of classifiers, Journal of Computer and System Sciences, v.73 n.5, p.725-734, August, 2007
Martin Anthony, Generalization Error Bounds for Threshold Decision Lists, The Journal of Machine Learning Research, 5, p.189-217, 12/1/2004
perceptron;learning theory;capacity control;decision trees;learning algorithm