NAG CL Interface
h05abc (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{fail}\mathbf{.}\mathbf{code}=$ NE_TOO_MANY 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]$ – double Output

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

7: $\mathbf{bz}\left[\left(\mathbf{m}-\mathbf{ip}\right)\times \mathbf{nbest}\right]$ – Integer Output

Note: where $\mathbf{BZ}\left(i,j\right)$ appears in this document, it refers to the array element $\mathbf{bz}\left[\left(j-1\right)\times \left(\mathbf{m}-\mathbf{ip}\right)+i-1\right]$.

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-1\right]$.

8: $\mathbf{f}$ – function, supplied by the user External Function

f must evaluate the scoring function $f$.

The specification of f is:

void  f (Integer m, Integer drop, Integer lz, const Integer z[], Integer la, const Integer a[], double score[], Nag_Comm *comm, 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[\mathit{dim}\right]$ – const Integer Input

On entry: $\mathbf{z}\left[\mathit{i}-1\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]$ – const Integer Input

On entry: $\mathbf{a}\left[\mathit{j}-1\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]$ – double 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-1\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-1\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 h05abc. 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{comm}$ – Nag_Comm *

Pointer to structure of type Nag_Comm; the following members are relevant to f.

user – double *

iuser – Integer *

p – Pointer 

The type Pointer will be void *. Before calling h05abc you may allocate memory and initialize these pointers with various quantities for use by f when called from h05abc (see Section 3.1.1 in the Introduction to the NAG Library CL Interface).

9: $\mathbf{info}$ – Integer * Input/Output

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

On exit: set info to a nonzero value if you wish h05abc to terminate with $\mathbf{fail}\mathbf{.}\mathbf{code}=$ NE_USER_STOP.

Note: f should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by h05abc. If your code inadvertently does return any NaNs or infinities, h05abc 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}$ – double 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]$ – const double 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[0\right]\le 1$ then ${\epsilon }_1=\mathbf{acc}\left[0\right]$, otherwise ${\epsilon }_1=0$.

If $\mathbf{acc}\left[1\right]\ge 0$ then ${\epsilon }_2=\mathbf{acc}\left[1\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{comm}$ – Nag_Comm *

The NAG communication argument (see Section 3.1.1 in the Introduction to the NAG Library CL Interface).

13: $\mathbf{fail}$ – NagError * Input/Output

The NAG error argument (see Section 7 in the Introduction to the NAG Library CL Interface).

6 Error Indicators and Warnings

NE_ALLOC_FAIL

Dynamic memory allocation failed.
See Section 3.1.2 in the Introduction to the NAG Library CL Interface for further information.

NE_BAD_PARAM

On entry, argument $〈\mathit{\text{value}}〉$ had an illegal value.

NE_INT

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

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

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

NE_INT_2

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

NE_INTERNAL_ERROR

An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
See Section 7.5 in the Introduction to the NAG Library CL Interface for further information.

NE_NO_LICENCE

Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library CL Interface for further information.

NE_REAL

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}}〉$.

NE_TOO_MANY

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

NE_USER_STOP

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

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results