Graphics Reference
In-Depth Information
definition, an incremental algorithm should be able to handle new instances as they
become available without all of them being present at the beginning. Neverthe-
less, some recent incremental approaches are order-independent because they add
instances to
S
in a somewhat incremental fashion, but they examine all available
instances to help select which instance to add next. This makes the algorithms not
truly incremental as we have defined above, although we will also consider them
as incremental approaches.
One advantage of an incremental scheme is that if instances are made available
later, after training is complete, they can continue to be added to
S
according to
the same criteria. This capability could be very helpful when dealing with data
streams or online learning. Another advantage is that they can be faster and use
less storage during the learning phase than non-incremental algorithms. The main
disadvantage is that incremental algorithms must make decisions based on little
information and are therefore prone to errors until more information is available.
•
Decremental:
The decremental search begins with
S
TR
, and then searches
for instances to remove from
S
. Again, the order of presentation is important,
but unlike the incremental process, all of the training examples are available for
examination at any time.
One disadvantage with the decremental rule is that it presents a higher compu-
tational cost than incremental algorithms. Furthermore, the learning stage must
be done in an off-line fashion because decremental approaches need all possible
data. However, if the application of a decremental algorithm can result in greater
storage reduction, then the extra computation during learning (which is done just
once) can be well worth the computational savings during execution thereafter.
=
•
Batch:
Another way to apply a PS process is in batch mode. This involves deciding
if each instance meets the removal criteria before removing any of them. Then all
those that do meet the criteria are removed at once. As with decremental algo-
rithms, batch processing suffers from increased time complexity over incremental
algorithms.
•
Mixed:
A mixed search begins with a pre-selected subset
S
(randomly or selected
by an incremental or decremental process) and iteratively can add or remove any
instance which meets the specific criterion. This type of search allows rectifications
to already done operations and its main advantage is to make it easy to obtain good
accuracy-suited subsets of instances. It usually suffers from the same drawbacks
reported in decremental algorithms, but this depends to a great extent on the specific
proposal. Note that these kinds of algorithms are closely related to the order-
independent incremental approaches but, in this case, instance removal from
S
is
allowed.
•
Fixed:
A fixed search is a subfamily of mixed search in which the number of
additions and removals remains the same. Thus, the number of final prototypes is
determined at the beginning of the learning phase and is never changed.
