NAG Library Routine Document

H05AAF

INTEGER	IREVCM, MINCR, M, IP, NBEST, DROP, LZ, Z(M-IP), LA, A(max(NBEST,M)), BZ(M-IP,NBEST), MINCNT, ICOMM(LICOMM), LICOMM, LRCOMM, IFAIL
REAL (KIND=nag_wp)	BSCORE(max(NBEST,M)), GAMMA, ACC(2), RCOMM(LRCOMM)

3 Description

Given

Ω = \{x_{i} : i \in ℤ, 1 \leq i \leq m\}

, a set of

m

unique features and a scoring mechanism

f (S)

defined for all

S \subseteq Ω

then H05AAF is designed to find

S_{o 1} \subseteq Ω, |S_{o 1}| = p

, an optimal subset of size

p

. Here

|S_{o 1}|

denotes the cardinality of

S_{o 1}

, the number of elements in the set.

The definition of the optimal subset depends on the properties of the scoring mechanism, if

\begin{matrix} f (S_{i}) \leq f (S_{j}), & for all ​ S_{j} \subseteq Ω ​ and ​ S_{i} \subseteq S_{j} \end{matrix}

(1)

then the optimal subset is defined as one of the solutions to

\underset{S \subseteq Ω}{maximize} f (S) subject to |S| = p

else if

\begin{matrix} f (S_{i}) \geq f (S_{j}), & for all ​ S_{j} \subseteq Ω ​ and ​ S_{i} \subseteq S_{j} \end{matrix}

(2)

then the optimal subset is defined as one of the solutions to

\underset{S \subseteq Ω}{minimize} f (S) subject to |S| = p .

If neither of these properties hold then H05AAF cannot be used.

As well as returning the optimal subset,

S_{o 1}

, H05AAF can return the best

n

solutions of size

p

. If

S_{o i}

denotes the

i

th best subset, for

i = 1, 2, \dots, n - 1

, then the

(i + 1)

th best subset is defined as the solution to either

\underset{S \subseteq Ω - \{S_{o j} : j \in ℤ, 1 \leq j \leq i\}}{maximize} f (S) subject to |S| = p

\underset{S \subseteq Ω - \{S_{o j} : j \in ℤ, 1 \leq j \leq i\}}{minimize} f (S) subject to |S| = p

depending on the properties of

f

The solutions are found using a branch and bound method, where each node of the tree is a subset of

Ω

. Assuming that (1) holds then a particular node, defined by subset

S_{i}

, can be trimmed from the tree if

f (S_{i}) < \hat{f} (S_{o n})

where

\hat{f} (S_{o n})

is the

n

th highest score we have observed so far for a subset of size

p

, i.e., our current best guess of the score for the

n

th best subset. In addition, because of (1) we can also drop all nodes defined by any subset

S_{j}

where

S_{j} \subseteq S_{i}

, thus avoiding the need to enumerate the whole tree. Similar short cuts can be taken if (2) holds. A full description of this branch and bound algorithm can be found in Ridout (1988).

Rather than calculate the score at a given node of the tree H05AAF utilizes the fast branch and bound algorithm of Somol et al. (2004), and attempts to estimate the score where possible. For each feature,

x_{i}

, two values are stored, a count

c_{i}

and

{\hat{μ}}_{i}

, an estimate of the contribution of that feature. An initial value of zero is used for both

c_{i}

and

{\hat{μ}}_{i}

. At any stage of the algorithm where both

f (S)

and

f (S - \{x_{i}\})

have been calculated (as opposed to estimated), the estimated contribution of the feature

x_{i}

is updated to

\frac{c_{i} {\hat{μ}}_{i} + [f (S) - f (S - \{x_{j}\})]}{c_{i} + 1}

and

c_{i}

is incremented by

1

, therefore at each stage

{\hat{μ}}_{i}

is the mean contribution of

x_{i}

observed so far and

c_{i}

is the number of observations used to calculate that mean.

As long as

c_{i} \geq k

, for the user-supplied constant

k

, then rather than calculating

f (S - \{x_{i}\})

this routine estimates it using

\hat{f} (S - \{x_{i}\}) = f (S) - γ {\hat{μ}}_{i}

\hat{f} (S) - γ {\hat{μ}}_{i}

f (S)

has been estimated, where

γ

is a user-supplied scaling factor. An estimated score is never used to trim a node or returned as the optimal score.

Setting

k = 0

in this routine will cause the algorithm to always calculate the scores, returning to the branch and bound algorithm of Ridout (1988). In most cases it is preferable to use the fast branch and bound algorithm, by setting

k > 0

, unless the score function is iterative in nature, i.e.,

f (S)

must have been calculated before

f (S - \{x_{i}\})

can be calculated.

4 References

Narendra P M and Fukunaga K (1977) A branch and bound algorithm for feature subset selection IEEE Transactions on Computers 9 917–922

Ridout M S (1988) Algorithm AS 233: An improved branch and bound algorithm for feature subset selection Journal of the Royal Statistics Society, Series C (Applied Statistics) (Volume 37) 1 139–147

Somol P, Pudil P and Kittler J (2004) Fast branch and bound algorithms for optimal feature selection IEEE Transactions on Pattern Analysis and Machine Intelligence (Volume 26) 7 900–912

5 Parameters

Note: this routine uses reverse communication. Its use involves an initial entry, intermediate exits and re-entries, and a final exit, as indicated by the parameter IREVCM. Between intermediate exits and re-entries, all parameters other than BSCORE must remain unchanged.

1: IREVCM – INTEGERInput/Output

On initial entry: must be set to

0

On intermediate exit:

IREVCM = 1

and before re-entry the scores associated with LA subsets must be calculated and returned in BSCORE.

The LA subsets are constructed as follows:

$DROP = 1$: The $j$ th subset is constructed by dropping the features specified in the first LZ elements of Z and the single feature given in $A (j)$ from the full set of features, $Ω$ . The subset will therefore contain $M - LZ - 1$ features.
$DROP = 0$: The $j$ th subset is constructed by adding the features specified in the first LZ elements of Z and the single feature specified in $A (j)$ to the empty set, $\emptyset$ . The subset will therefore contain $LZ + 1$ features.

In both cases the individual features are referenced by the integers

1

to M with

1

indicating the first feature,

2

the second, etc., for some arbitrary ordering of the features. The same ordering must be used in all calls to H05AAF.

LA = 0

, the score for a single subset should be returned. This subset is constructed by adding or removing only those features specified in the first LZ elements of Z.

LZ = 0

, this subset will either be

Ω

\emptyset

The score associated with the

j

th subset must be returned in

BSCORE (j)

On intermediate re-entry: IREVCM must remain unchanged.

On final exit:

IREVCM = 0

, and the algorithm has terminated.

Constraint:

IREVCM = 0

1

2: MINCR – INTEGERInput

On entry: flag indicating whether the scoring function

f

is increasing or decreasing.

$MINCR = 1$: $f (S_{i}) \leq f (S_{j})$ , i.e., the subsets with the largest score will be selected.
$MINCR = 0$: $f (S_{i}) \geq f (S_{j})$ , i.e., the subsets with the smallest score will be selected.

For all

S_{j} \subseteq Ω

and

S_{i} \subseteq S_{j}

Constraint:

MINCR = 0

1

3: M – INTEGERInput

On entry:

m

, the number of features in the full feature set.

Constraint:

M \geq 2

4: IP – INTEGERInput

On entry:

p

, the number of features in the subset of interest.

Constraint:

1 \leq IP \leq M

5: NBEST – INTEGERInput

On entry:

n

, the maximum number of best subsets required. The actual number of subsets returned is given by LA on final exit. If on final exit

LA \neq NBEST

then

IFAIL = 53

is returned.

Constraint:

NBEST \geq 1

6: DROP – INTEGERInput/Output

On initial entry: DROP need not be set.

On intermediate exit: flag indicating whether the intermediate subsets should be constructed by dropping features from the full set (

DROP = 1

) or adding features to the empty set (

DROP = 0

). See IREVCM for details.

On intermediate re-entry: DROP must remain unchanged.

On final exit: is undefined.

7: LZ – INTEGERInput/Output

On initial entry: LZ need not be set.

On intermediate exit: the number of features stored in Z.

On intermediate re-entry: LZ must remain unchanged.

On final exit: is undefined.

8: Z( $M - IP$ ) – INTEGER arrayInput/Output

On initial entry: Z need not be set.

On intermediate exit:

Z (i)

, for

i = 1, 2, \dots, LZ

, contains the list of features which, along with those specified in A, define the subsets whose score is required. See IREVCM for additional details.

On intermediate re-entry: Z must remain unchanged.

On final exit: is undefined.

9: LA – INTEGERInput/Output

On initial entry: LA need not be set.

On intermediate exit: if

LA > 0

, the number of subsets for which a score must be returned.

LA = 0

, the score for a single subset should be returned. See IREVCM for additional details.

On intermediate re-entry: LA must remain unchanged.

On final exit: the number of best subsets returned.

10: A( $\max (NBEST, M)$ ) – INTEGER arrayInput/Output

On initial entry: A need not be set.

On intermediate exit:

A (j)

, for

j = 1, 2, \dots, LA

, contains the list of features which, along with those specified in Z, define the subsets whose score is required. See IREVCM for additional details.

On intermediate re-entry: A must remain unchanged.

On final exit: is undefined.

11: BSCORE( $\max (NBEST, M)$ ) – REAL (KIND=nag_wp) arrayInput/Output

On initial entry: BSCORE need not be set.

On intermediate exit: is undefined.

On intermediate re-entry:

BSCORE (j)

must hold the score for the

j

th subset as described in IREVCM.

On final exit: holds the score for the LA best subsets returned in BZ.

12: BZ( $M - IP$ ,NBEST) – INTEGER arrayInput/Output

On initial entry: BZ need not be set.

On intermediate exit: is used for storage betweeen calls to H05AAF.

On intermediate re-entry: BZ must remain unchanged.

On final exit: the

j

th best subset is constructed by dropping the features specified in

BZ (i, j)

, for

i = 1, 2, \dots, M - IP

and

j = 1, 2, \dots, LA

, from the set of all features,

Ω

. The score for the

j

th best subset is given in

BSCORE (j)

13: MINCNT – INTEGERInput

On entry:

k

, the minimum number of times the effect of each feature,

x_{i}

, must have been observed before

f (S - \{x_{i}\})

is estimated from

f (S)

as opposed to being calculated directly.

k = 0

then

f (S - \{x_{i}\})

is never estimated. If

MINCNT < 0

then

k

is set to

1

14: GAMMA – REAL (KIND=nag_wp)Input

On entry:

γ

, the scaling factor used when estimating scores. If

GAMMA < 0

then

γ

is set to

1

15: ACC( $2$ ) – REAL (KIND=nag_wp) arrayInput

On entry: a measure of the accuracy of the scoring function,

f

Letting

a_{i} = ε_{1} |f (S_{i})| + ε_{2}

, then when confirming whether the scoring function is strictly increasing or decreasing (as described in MINCR), or when assessing whether a node defined by subset

S_{i}

can be trimmed, then any values in the range

f (S_{i}) \pm a_{i}

are treated as being numerically equivalent.

0 \leq ACC (1) \leq 1

then

ε_{1} = ACC (1)

, otherwise

ε_{1} = 0

ACC (2) \geq 0

then

ε_{2} = ACC (2)

, otherwise

ε_{2} = 0

In most situations setting both

ε_{1}

and

ε_{2}

to zero should be sufficient. Using a nonzero value, when one is not required, can significantly increase the number of subsets that need to be evaluated.

16: ICOMM(LICOMM) – INTEGER arrayCommunication Array

On initial entry: ICOMM need not be set.

On intermediate exit: is used for storage between calls to H05AAF.

On intermediate re-entry: ICOMM must remain unchanged.

On final exit: is not defined. The first two elements,

ICOMM (1)

and

ICOMM (2)

contain the minimum required value for LICOMM and LRCOMM respectively.

17: LICOMM – INTEGERInput

On entry: the length of the array ICOMM. If LICOMM is too small and

LICOMM \geq 2

then

IFAIL = 172

is returned and the minimum value for LICOMM and LRCOMM are given by

ICOMM (1)

and

ICOMM (2)

respectively.

Constraints:

if $MINCNT = 0$ , $LICOMM \geq 2 \times \max (NBEST, M) + M (M + 2) + (M + 1) \times \max (M - IP, 1) + 27$ ;
otherwise $LICOMM \geq 2 \times \max (NBEST, M) + M (M + 3) + (2 M + 1) \times \max (M - IP, 1) + 25$ .

18: RCOMM(LRCOMM) – REAL (KIND=nag_wp) arrayCommunication Array

On initial entry: RCOMM need not be set.

On intermediate exit: is used for storage between calls to H05AAF.

On intermediate re-entry: RCOMM must remain unchanged.

On final exit: is not defined.

19: LRCOMM – INTEGERInput

On entry: the length of the array RCOMM. If LRCOMM is too small and

LICOMM \geq 2

then

IFAIL = 172

is returned and the minimum value for LICOMM and LRCOMM are given by

ICOMM (1)

and

ICOMM (2)

respectively.

Constraints:

if $MINCNT = 0$ , $LRCOMM \geq 9 + NBEST + M \times \max (M - IP, 1)$ ;
otherwise $LRCOMM \geq 8 + M + NBEST + M \times \max (M - IP, 1)$ .

20: IFAIL – INTEGERInput/Output

On initial entry: IFAIL must be set to

0

- 1 ​ or ​ 1

. If you are unfamiliar with this parameter you should refer to Section 3.3 in the Essential Introduction for details.

For environments where it might be inappropriate to halt program execution when an error is detected, the value

- 1 ​ or ​ 1

is recommended. If the output of error messages is undesirable, then the value

1

is recommended. Otherwise, because for this routine the values of the output parameters may be useful even if

IFAIL \neq 0

on exit, the recommended value is

- 1

. When the value $- 1 or 1$ is used it is essential to test the value of IFAIL on exit.

On final exit:

IFAIL = 0

unless the routine detects an error or a warning has been flagged (see Section 6).

6 Error Indicators and Warnings

If on entry

IFAIL = 0

- 1

, explanatory error messages are output on the current error message unit (as defined by X04AAF).

Errors or warnings detected by the routine:

$IFAIL = 11$: On entry, $IREVCM = ⟨value⟩$ .
Constraint: $IREVCM = 0$ or $1$ .

$IFAIL = 21$: On entry, $MINCR = ⟨value⟩$ .
Constraint: $MINCR = 0$ or $1$ .

$IFAIL = 22$: MINCR has changed between calls.
On intermediate entry, $MINCR = ⟨value⟩$ .
On initial entry, $MINCR = ⟨value⟩$ .

$IFAIL = 31$: On entry, $M = ⟨value⟩$ .
Constraint: $M \geq 2$ .

$IFAIL = 32$: M has changed between calls.
On intermediate entry, $M = ⟨value⟩$ .
On initial entry, $M = ⟨value⟩$ .

$IFAIL = 41$: On entry, $IP = ⟨value⟩$ and $M = ⟨value⟩$ .
Constraint: $1 \leq IP \leq M$ . On entry, $IP = ⟨value⟩$ and $M = ⟨value⟩$ .
Constraint: $1 \leq IP \leq M$ .

$IFAIL = 42$: IP has changed between calls.
On intermediate entry, $IP = ⟨value⟩$ .
On initial entry, $IP = ⟨value⟩$ .

$IFAIL = 51$: On entry, $NBEST = ⟨value⟩$ .
Constraint: $NBEST \geq 1$ .

$IFAIL = 52$: NBEST has changed between calls.
On intermediate entry, $NBEST = ⟨value⟩$ .
On initial entry, $NBEST = ⟨value⟩$ .

$IFAIL = 53$: On entry, $NBEST = ⟨value⟩$ .
But only $⟨value⟩$ best subsets could be calculated.

$IFAIL = 61$: DROP has changed between calls.
On intermediate entry, $DROP = ⟨value⟩$ .
On initial entry, $DROP = ⟨value⟩$ .

$IFAIL = 71$: LZ has changed between calls.
On entry, $LZ = ⟨value⟩$ .
On previous exit, $LZ = ⟨value⟩$ .

$IFAIL = 91$: LA has changed between calls.
On entry, $LA = ⟨value⟩$ .
On previous exit, $LA = ⟨value⟩$ .

$IFAIL = 111$: $BSCORE (⟨value⟩) = ⟨value⟩$ , which is inconsistent with the score for the parent node. Score for the parent node is $⟨value⟩$ . $BSCORE (⟨value⟩) = ⟨value⟩$ , which is inconsistent with the score for the parent node. Score for the parent node is $⟨value⟩$ .

$IFAIL = 131$: MINCNT has changed between calls.
On intermediate entry, $MINCNT = ⟨value⟩$ .
On initial entry, $MINCNT = ⟨value⟩$ .

$IFAIL = 141$: GAMMA has changed between calls.
On intermediate entry, $GAMMA = ⟨value⟩$ .
On initial entry, $GAMMA = ⟨value⟩$ .

$IFAIL = 151$: $ACC (1)$ has changed between calls.
On intermediate entry, $ACC (1) = ⟨value⟩$ .
On initial entry, $ACC (1) = ⟨value⟩$ .

$IFAIL = 152$: $ACC (2)$ has changed between calls.
On intermediate entry, $ACC (2) = ⟨value⟩$ .
On initial entry, $ACC (2) = ⟨value⟩$ .

$IFAIL = 161$: ICOMM has been corrupted between calls. ICOMM has been corrupted between calls.

$IFAIL = 171$: On entry, $LICOMM = ⟨value⟩$ , $LRCOMM = ⟨value⟩$ .
Constraint: $LICOMM \geq ⟨value⟩$ , $LRCOMM \geq ⟨value⟩$ .
ICOMM is too small to return the required array sizes.

$IFAIL = 172$: On entry, $LICOMM = ⟨value⟩$ , $LRCOMM = ⟨value⟩$ .
Constraint: $LICOMM \geq ⟨value⟩$ , $LRCOMM \geq ⟨value⟩$ .
The minimum required values for LICOMM and LRCOMM are returned in $ICOMM (1)$ and $ICOMM (2)$ respectively. On entry, $LICOMM = ⟨value⟩$ , $LRCOMM = ⟨value⟩$ .
Constraint: $LICOMM \geq ⟨value⟩$ , $LRCOMM \geq ⟨value⟩$ .
The minimum required values for LICOMM and LRCOMM are returned in $ICOMM (1)$ and $ICOMM (2)$ respectively.

$IFAIL = 181$: RCOMM has been corrupted between calls.

$IFAIL = - 999$: Dynamic memory allocation failed.

7 Accuracy

The subsets returned by H05AAF are guaranteed to be optimal up to the accuracy of your calculated scores.

8 Further Comments

The maximum number of unique subsets of size

p

from a set of

m

features is

N = \frac{m!}{(m - p)! p!}

. The efficiency of the branch and bound algorithm implemented in H05AAF comes from evaluating subsets at internal nodes of the tree, that is subsets with more than

p

features, and where possible trimming branches of the tree based on the scores at these internal nodes as described in Narendra and Fukunaga (1977). Because of this it is possible, in some circumstances, for more than

N

subsets to be evaluated. This will tend to happen when most of the features have a similar effect on the subset score.

If multiple optimal subsets exist with the same score, and NBEST is too small to return them all, then the choice of which of these optimal subsets is returned is arbitrary.

9 Example

This example finds the three linear regression models, with five variables, that have the smallest residual sums of squares when fitted to a supplied dataset. The data used in this example was simulated.

NAG Library Routine DocumentH05AAF

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Parameters

6 Error Indicators and Warnings

7 Accuracy

8 Further Comments

9 Example

9.1 Program Text

9.2 Program Data

9.3 Program Results

NAG Library Routine Document

H05AAF