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

FEATURE SELECTION 197

6.2.1 Branch-and-bound

The search process is accomplished systematically by means of a tree
structure. See Figure 6.4. The tree consists of N D þ 1 levels. Each
level is enumerated by a variable n with n varying from D up to N.
A level consists of a number of nodes. A node i at level n corresponds to
a subset F i (n). At the highest level, n ¼ N, there is only one node
corresponding to the full set F(N). At the lowest level n ¼ D there are
q(D) nodes corresponding to the q(D) subsets among which the solution
must be found. Levels in between have a number of nodes that is less
than or equal to q(n). A node at level n is connected to one node at level
n þ 1 (except the node F(N) at level N). In addition, each node at level n
is connected to one or more nodes at level n 1 (except the nodes at
level D). In the example of Figure 6.4, N ¼ 6 and D ¼ 2.
A prerequisite of the branch-and-bound strategy is that the perform-
ance measure is a monotonically increasing function of the dimension D.
The assumption behind it is that if we remove one element from a
measurement vector, the performance can only become worse. In prac-
tice, this requirement is not always satisfied. If the training set is finite,
problems in estimating large numbers of parameters may result in an
actual performance increase when fewer measurements are used (see
Figure 6.1).
The search process takes place from the highest level (n ¼ N)by
systematically traversing all levels until finally the lowest level (n ¼ D)
is reached. Suppose that one branch of the tree has been explored up
to the lowest level, and suppose that the best performance measure
^
found so far at level n ¼ D is JJ. Consider a node F i (l) (at a level
^
n > D) which has not been explored as yet. Then, if J(F i (n)) JJ, it is

n = N =5 z z z z z
0 1 2 3 4
0 1 2 3 4
n =4 z z z z z z z z z z z z z z z z z z z z
0 1 2 3
1 2 3 4
0 2 3 4
0 1 3 4
0 1 2 4
1 2 3 4 2 3 4 3 4 4
n =3 z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z
0 3 4
0 1 3
0 2 4
2 3 4
0 2 3
1 2 4
0 1 2
1 3 4
0 1 4
1 2 3
2 3 4 3 4 4 3 4 4 4
n = D =2 z z z z z z z z z z z z z z z z z z z z
0 1
0 2
0 3
2 4
2 3
0 4
3 4
1 2
1 3
1 4
Figure 6.4 A top-down tree structure in behalf of feature selection