NAG Library Routine Document

h05abf  (best_subset_given_size)

1

Purpose

2

Specification

3

Description

4

References

5

Arguments

1:     $\mathbf{mincr}$ – IntegerInput

On entry: flag indicating whether the scoring function $f$ is increasing or decreasing.

$\mathbf{mincr}=1$

$f\left(S_i\right)\le f\left(S_j\right)$, i.e., the subsets with the largest score will be selected.

$\mathbf{mincr}=0$

$f\left(S_i\right)\ge f\left(S_j\right)$, i.e., the subsets with the smallest score will be selected.

For all $S_j\subseteq \Omega$ and $S_i\subseteq S_j$.

Constraint: $\mathbf{mincr}=0$ or $1$.

2:     $\mathbf{m}$ – IntegerInput

On entry: $m$, the number of features in the full feature set.

Constraint: $\mathbf{m}\ge 2$.

3:     $\mathbf{ip}$ – IntegerInput

On entry: $p$, the number of features in the subset of interest.

Constraint: $1\le \mathbf{ip}\le \mathbf{m}$.

4:     $\mathbf{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 $\mathbf{la}\ne \mathbf{nbest}$ then $\mathbf{ifail}=\mathbf{42}$ is returned.

Constraint: $\mathbf{nbest}\ge 1$.

5:     $\mathbf{la}$ – IntegerOutput

On exit: the number of best subsets returned.

6:     $\mathbf{bscore}\left(\mathbf{nbest}\right)$ – Real (Kind=nag_wp) arrayOutput

On exit: holds the score for the la best subsets returned in bz.

7:     $\mathbf{bz}\left(\mathbf{m}-\mathbf{ip},\mathbf{nbest}\right)$ – Integer arrayOutput

On exit: the $j$th best subset is constructed by dropping the features specified in $\mathbf{bz}\left(\mathit{i},\mathit{j}\right)$, for $\mathit{i}=1,2,\dots ,\mathbf{m}-\mathbf{ip}$ and $\mathit{j}=1,2,\dots ,\mathbf{la}$, from the set of all features, $\Omega$. The score for the $j$th best subset is given in $\mathbf{bscore}\left(j\right)$.

8:     $\mathbf{f}$ – Subroutine, supplied by the user.External Procedure

f must evaluate the scoring function $f$.

The specification of f is:

Fortran Interface

Subroutine f ( m, drop, lz, z, la, a, score, iuser, ruser, info) Integer, Intent (In) :: m, drop, lz, z(lz), la, a(la) Integer, Intent (Inout) :: iuser(*), info Real (Kind=nag_wp), Intent (Inout) :: ruser(*) Real (Kind=nag_wp), Intent (Out) :: score(max(la,1))

C Header Interface

#include nagmk26.h void  f ( const Integer *m, const Integer *drop, const Integer *lz, const Integer z[], const Integer *la, const Integer a[], double score[], Integer iuser[], double ruser[], Integer *info)

1:     $\mathbf{m}$ – IntegerInput

On entry: $m=\left|\Omega \right|$, the number of features in the full feature set.

2:     $\mathbf{drop}$ – IntegerInput

On entry: flag indicating whether the intermediate subsets should be constructed by dropping features from the full set ($\mathbf{drop}=1$) or adding features to the empty set ($\mathbf{drop}=0$). See score for additional details.

3:     $\mathbf{lz}$ – IntegerInput

On entry: the number of features stored in z.

4:     $\mathbf{z}\left(\mathbf{lz}\right)$ – Integer arrayInput

On entry: $\mathbf{z}\left(\mathit{i}\right)$, for $\mathit{i}=1,2,\dots ,\mathbf{lz}$, contains the list of features which, along with those specified in a, define the subsets whose score is required. See score for additional details.

5:     $\mathbf{la}$ – IntegerInput

On entry: if $\mathbf{la}>0$, the number of subsets for which a score must be returned.

If $\mathbf{la}=0$, the score for a single subset should be returned. See score for additional details.

6:     $\mathbf{a}\left(\mathbf{la}\right)$ – Integer arrayInput

On entry: $\mathbf{a}\left(\mathit{j}\right)$, for $\mathit{j}=1,2,\dots ,\mathbf{la}$, contains the list of features which, along with those specified in z, define the subsets whose score is required. See score for additional details.

7:     $\mathbf{score}\left(\max \left(\mathbf{la},1\right)\right)$ – Real (Kind=nag_wp) arrayOutput

On exit: the value $f\left(S_{\mathit{j}}\right)$, for $\mathit{j}=1,2,\dots ,\mathbf{la}$, the score associated with the $j$th subset. $S_j$ is constructed as follows:

$\mathbf{drop}=1$

$S_j$ is constructed by dropping the features specified in the first lz elements of z and the single feature given in $\mathbf{a}\left(j\right)$ from the full set of features, $\Omega$. The subset will therefore contain $\mathbf{m}-\mathbf{lz}-1$ features.

$\mathbf{drop}=0$

$S_j$ is constructed by adding the features specified in the first lz elements of z and the single feature specified in $\mathbf{a}\left(j\right)$ to the empty set, $\varnothing$. The subset will therefore contain $\mathbf{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, chosen by you prior to calling h05abf. For example, $1$ might refer to the first variable in a particular set of data, $2$ the second, etc..

If $\mathbf{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. If $\mathbf{lz}=0$, this subset will either be $\Omega$ or $\varnothing$.

8:     $\mathbf{iuser}\left(*\right)$ – Integer arrayUser Workspace

9:     $\mathbf{ruser}\left(*\right)$ – Real (Kind=nag_wp) arrayUser Workspace

f is called with the arguments iuser and ruser as supplied to h05abf. You should use the arrays iuser and ruser to supply information to f.

10:   $\mathbf{info}$ – IntegerInput/Output

On entry: $\mathbf{info}=0$.

On exit: set info to a nonzero value if you wish h05abf to terminate with $\mathbf{ifail}=\mathbf{82}$.

f must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which h05abf is called. Arguments denoted as Input must not be changed by this procedure.

Note: f should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by h05abf. If your code inadvertently does return any NaNs or infinities, h05abf is likely to produce unexpected results.

9:     $\mathbf{mincnt}$ – IntegerInput

On entry: $k$, the minimum number of times the effect of each feature, $x_i$, must have been observed before $f\left(S-\left\{x_i\right\}\right)$ is estimated from $f\left(S\right)$ as opposed to being calculated directly.

If $k=0$ then $f\left(S-\left\{x_i\right\}\right)$ is never estimated. If $\mathbf{mincnt}<0$ then $k$ is set to $1$.

10:   $\mathbf{gamma}$ – Real (Kind=nag_wp)Input

On entry: $\gamma$, the scaling factor used when estimating scores. If $\mathbf{gamma}<0$ then $\gamma =1$ is used.

11:   $\mathbf{acc}\left(2\right)$ – Real (Kind=nag_wp) arrayInput

On entry: a measure of the accuracy of the scoring function, $f$.

Letting $a_i={\epsilon }_1\left|f\left(S_i\right)\right|+{\epsilon }_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\left(S_i\right)\pm a_i$ are treated as being numerically equivalent.

If $0\le \mathbf{acc}\left(1\right)\le 1$ then ${\epsilon }_1=\mathbf{acc}\left(1\right)$, otherwise ${\epsilon }_1=0$.

If $\mathbf{acc}\left(2\right)\ge 0$ then ${\epsilon }_2=\mathbf{acc}\left(2\right)$, otherwise ${\epsilon }_2=0$.

In most situations setting both ${\epsilon }_1$ and ${\epsilon }_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.

12:   $\mathbf{iuser}\left(*\right)$ – Integer arrayUser Workspace

13:   $\mathbf{ruser}\left(*\right)$ – Real (Kind=nag_wp) arrayUser Workspace

iuser and ruser are not used by h05abf, but are passed directly to f and may be used to pass information to this routine.

14:   $\mathbf{ifail}$ – IntegerInput/Output

On entry: ifail must be set to $0$, $-1\text{ or }1$. If you are unfamiliar with this argument you should refer to Section 3.4 in How to Use the NAG Library and its Documentation for details.

For environments where it might be inappropriate to halt program execution when an error is detected, the value $-1\text{ or }1$ is recommended. If the output of error messages is undesirable, then the value $1$ is recommended. Otherwise, if you are not familiar with this argument, the recommended value is $0$. When the value $-\mathbf{1}\text{ or }\mathbf{1}$ is used it is essential to test the value of ifail on exit.

On exit: $\mathbf{ifail}=\mathbf{0}$ unless the routine detects an error or a warning has been flagged (see Section 6).

6

Error Indicators and Warnings

$\mathbf{ifail}=11$

On entry, $\mathbf{mincr}=〈\mathit{\text{value}}〉$.
Constraint: $\mathbf{mincr}=0$ or $1$.

$\mathbf{ifail}=21$

On entry, $\mathbf{m}=〈\mathit{\text{value}}〉$.
Constraint: $\mathbf{m}\ge 2$.

$\mathbf{ifail}=31$

On entry, $\mathbf{ip}=〈\mathit{\text{value}}〉$ and $\mathbf{m}=〈\mathit{\text{value}}〉$.
Constraint: $1\le \mathbf{ip}\le \mathbf{m}$.

$\mathbf{ifail}=41$

On entry, $\mathbf{nbest}=〈\mathit{\text{value}}〉$.
Constraint: $\mathbf{nbest}\ge 1$.

$\mathbf{ifail}=42$

On entry, $\mathbf{nbest}=〈\mathit{\text{value}}〉$.
But only $〈\mathit{\text{value}}〉$ best subsets could be calculated.

$\mathbf{ifail}=81$

On exit from f, $\mathbf{score}\left(〈\mathit{\text{value}}〉\right)=〈\mathit{\text{value}}〉$, which is inconsistent with the score for the parent node. Score for the parent node is $〈\mathit{\text{value}}〉$.

$\mathbf{ifail}=82$

A nonzero value for info has been returned: $\mathbf{info}=〈\mathit{\text{value}}〉$.

$\mathbf{ifail}=-99$

An unexpected error has been triggered by this routine. Please contact NAG.

See Section 3.9 in How to Use the NAG Library and its Documentation for further information.

$\mathbf{ifail}=-399$

Your licence key may have expired or may not have been installed correctly.

See Section 3.8 in How to Use the NAG Library and its Documentation for further information.

$\mathbf{ifail}=-999$

Dynamic memory allocation failed.

See Section 3.7 in How to Use the NAG Library and its Documentation for further information.

7

Accuracy

8

Parallelism and Performance

9

Further Comments

10

Example

10.1

Program Text

Program Text (h05abfe.f90)

10.2

Program Data

Program Data (h05abfe.d)

10.3

Program Results

Program Results (h05abfe.r)