Page 209 - Classification Parameter Estimation & State Estimation An Engg Approach Using MATLAB

198 FEATURE EXTRACTION AND SELECTION

unnecessary to consider the nodes below F i (n). The reason is that the
performance measure for these nodes can only become less than J(F i (n))
^
and thus less than JJ.
The following algorithm traverses the tree structure according to a
depth first search with a backtrack mechanism. In this algorithm the
best performance measure found so far at level n ¼ D is stored in a
^
^
variable JJ. Branches whose performance measure is bounded by J are
J
skipped. Therefore, relative to exhaustive search the algorithm is much
more computationally efficient. The variable S denotes a subset. Initially
^
J
this subset is empty, and J is set to 0. As soon as a combination of D
elements has been found that exceeds the current performance, this
^
combination is stored in S and the corresponding measure in JJ.
Algorithm 6.1: Branch-and-bound search
Input: a labelled training set on which a performance measure J() is
defined.

^
J
1. Initiate: J ¼ 0 and S ¼ ;
2. Explore-node(F 1 (N));
^
Output: The maximum performance measure stored in J with the asso-
J
ciated subset of F 1 (N) stored in S.
Procedure: Explore-node(F i (n))

^
1. If (J(F i (n)) JJ) then return;
2. If (n ¼ D) then
^
2.1. If ( J(F i (n)) > JJ) then
^
J
2.1.1. J ¼ J(F i (n));
2.1.2. S ¼ F i (n);
2.1.3. return;
3. For all (F j (n 1) F i (n)) do Explore-node(F j (n 1));
4. return;

The algorithm is recursive. The procedure ‘Explore-node()’ explores the
node given in its argument list. If the node is not a leaf, all its children
nodes are explored by calling the procedure recursively. The first call is
with the full set F(N) as argument.
The algorithm listed above does not specify the exact structure of the
tree. The structure follows from the specific implementation of the loop