NAG FL Interface
h05abf (best_​subset_​given_​size)

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

1: $\mathbf{mincr}$ – Integer Input

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}$ – Integer Input

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

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

3: $\mathbf{ip}$ – Integer Input

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

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

4: $\mathbf{nbest}$ – Integer Input

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}$ – Integer Output

On exit: the number of best subsets returned.

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

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 array Output

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

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)

C++ Header Interface

#include <nag.h> extern "C" { 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}$ – Integer Input

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

2: $\mathbf{drop}$ – Integer Input

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}$ – Integer Input

On entry: the number of features stored in z.

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

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}$ – Integer Input

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 array Input

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) array Output

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 array User Workspace

9: $\mathbf{ruser}\left(*\right)$ – Real (Kind=nag_wp) array User 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}$ – Integer Input/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}$ – Integer Input

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) array Input

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 array User Workspace

13: $\mathbf{ruser}\left(*\right)$ – Real (Kind=nag_wp) array User 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}$ – Integer Input/Output

On entry: ifail must be set to $0$, $-1$ or $1$ to set behaviour on detection of an error; these values have no effect when no error is detected.

A value of $0$ causes the printing of an error message and program execution will be halted; otherwise program execution continues. A value of $-1$ means that an error message is printed while a value of $1$ means that it is not.

If halting is not appropriate, the value $-1$ or $1$ is recommended. If message printing is undesirable, then the value $1$ is recommended. Otherwise, the value $0$ is recommended. When the value $-\mathbf{1}$ 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 7 in the Introduction to the NAG Library FL Interface for further information.

$\mathbf{ifail}=-399$

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

See Section 8 in the Introduction to the NAG Library FL Interface for further information.

$\mathbf{ifail}=-999$

Dynamic memory allocation failed.

See Section 9 in the Introduction to the NAG Library FL Interface for further information.

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results