NAG Library Function Document

nag_best_subset_given_size (h05abc)

1  Purpose

2  Specification

3  Description

4  References

5  Arguments

1:     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:     m – IntegerInput

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

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

3:     ip – IntegerInput

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

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

4:     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{fail}\mathbf{.}\mathbf{code}=$ NE_TOO_MANY is returned.

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

5:     la – Integer *Output

On exit: the number of best subsets returned.

6:     bscore[nbest] – doubleOutput

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

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

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:     f – function, supplied by the userExternal 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:     m – IntegerInput

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

2:     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:     lz – IntegerInput

On entry: the number of features stored in z.

4:     z[lz] – const IntegerInput

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:     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:     a[la] – const IntegerInput

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:     score[$\max \left(\mathbf{la},1\right)$] – doubleOutput

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 nag_best_subset_given_size (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:     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 nag_best_subset_given_size (h05abc) you may allocate memory and initialize these pointers with various quantities for use by f when called from nag_best_subset_given_size (h05abc) (see Section 3.2.1.1 in the Essential Introduction).

9:     info – Integer *Input/Output

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

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

9:     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:   gamma – doubleInput

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

11:   acc[$2$] – const doubleInput

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:   comm – Nag_Comm *Communication Structure

The NAG communication argument (see Section 3.2.1.1 in the Essential Introduction).

13:   fail – NagError *Input/Output

The NAG error argument (see Section 3.6 in the Essential Introduction).

6  Error Indicators and Warnings

NE_ALLOC_FAIL

Dynamic memory allocation failed.

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.

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

Program Text (h05abce.c)

10.2  Program Data

Program Data (h05abce.d)

10.3  Program Results

Program Results (h05abce.r)