Another issue is the time required to recognise the signs. However, performing tests on time is extremely subjective, and depends heavily on architecture used, other jobs running simultaneously, algorithm used, extent of optimisation and so on. This makes it difficult to form a complete comparison. Furthermore, do we judge time on the time required to learn the data or the time required to make a decision as to the class, assuming that the time required to make a decision is constant, which of course it isn't?
IBL1 and C4.5 tend to be at opposite end of the spectrum with respect
to learning and testing time. IBL1 takes very little time to learn,
since all it is effectively doing is reading a giant array of
attribute values. C4.5 takes the attributes, considers the gain that a
particular comparison results in, chooses the most effective decision
and repeats the process until it gets to a leaf node in all cases --
which can take a significant amount of time. On the other hand when
testing occurs, C4.5 is trivial, simply traversing a tree, which can
be done very quickly. It is unusual for a tree to have a depth greater
than 20, so there is a nice upper bound. IBL, however, must find the
instance that is closest to it. If a brute force algorithm is used,
then it has to check every instance in the data set. Fortunately, as
illustrated in [WK91], algorithms exist that allow
this search in 
manner, using a method known as k-d
trees.
C4.5 is only one example of a symbolic decision tree learner. The implementation of the IBL algorithm used does not employ k-d tree. It uses an optimised search based on collecting all instances of the same class together and maintaining some information about the mean and range of those instances, generously provided by Simon Warfield ([Waron]). So the applicability of the results to other domains is limited.
The tests were performed on a Sun SuperSparc server running Solaris with two 60 MHz processors and 256 Mb of RAM. Only one processor was used for each algorithm, however, and there were a number of other users making use of the system simultaneously. This fact was adjusted for by using the ``time'' command to report the time used. The ``CPU time'' measure was used for all computations. This returns only the amount of CPU time used by the process alone for actual calculations, not I/O and so on. Even so, the figures are meant to give only a rough guide to the time taken.
As a measure of performance, the calculations are based on the average training and test time for each element of the test set -- i.e. (test time + training time)/(number of test cases).
First we considered the effects on time of increasing the number of samples, as was discussed in section 6.3.1. This shows how as we add signs the time taken increases.
Figure 6.6: The relationship between the number of
samples per sign and the error rate.
The effects appear unusual at first. It appears that the IBL algorithm is taking constant time under all circumstances. This is a result of the algorithm used. The optimisations used are that all instances from a given class are treated together -- the mean and range for each feature is stored. Calculations are then performed on the means and ranges to eliminate bad class candidates automatically. This usually leaves a very small collection of classes that a test example can take, which are tested as usual. Since the number of classes is the same whether we have 2 samples for each class or 14, then this optimisation will take approximately the same time. As we will see when looking at the way it behave when given more signs, rather than more instances of that sign, it is still sensitive to the number of signs being taught.
Also note that while C4.5 is always faster in the cases shown than IBL, it is showing a tendency to grow faster than linearly. This is not a good thing to happen of course, since it means the more samples the more C4.5 would slow down, and in fact, it would slow down faster than the signs are being added (at least that's what the results here indicated). It also means that at some point (at a rough guess, less than one hundred samples) IBL would be faster than C4.5. If C4.5 were to be used for large lexicon systems, this would need to be dealt with, and some pre-processing to eliminate unnecessary instances (which is almost identical to what IBL3 does) would have to be employed. This is not usually an efficient task in itself and is not a good indication. It must be remembered that this is a very simplified view, and that we are looking at a combination of test and training times, and it is possible that training times are the dominant factor.
We then considered how the error rate changes with the number of signs learnt. This is shown in figure 6.7.
Figure 6.7: The time per test example and its
relationship with the number of signs being learnt.
As we can see, both systems take similar time with low sign count, but
C4.5 takes less time for larger number of signs than IBL. This should
not, however be taken as definitive. In particular, it is possible to
write IBL algorithms that runs in 
time, rather than the
algorithm here which was 
. However, none of the algorithms
appear to be worse than linear -- both having what appear to
near-linear performance. Also, we can see that these
systems, with their inefficient algorithms are near to real-time, even
with 90 signs, with C4.5 taking 0.7 seconds and IBL taking around 1.4
seconds. It must be remembered that this includes both testing and
training.
In conclusion, these results should not be taken as definitive and only approximate. However, it can be seen that C4.5 is probably no longer viable, because of the increase in time required to learn with increasing number of samples, and a greater number of samples leads to a smaller error rate (although only logarithmically). But C4.5 is only one example of a decision tree builder, and similarly the implementation of IBL used here is only one instance. The results as far as timing are concerned are thus not all that useful. Nonetheless, we have at least illustrated that both algorithms can at least be used with what appears to be a linear increase in time with increasing number of signs. Given that computing power grows exponentially, even if other algorithms do not exist that perform better, it is viable at some future point that a real-time system would be possible.