naginterfaces.library.mip.best_​subset_​given_​size_​revcomm

naginterfaces.library.mip.best_subset_given_size_revcomm(irevcm, mincr, m, ip, nbest, drop, lz, z, la, a, bscore, bz, mincnt, gamma, acc, comm, io_manager=None)

Given a set of $m$ features and a scoring mechanism for any subset of those features, best_subset_given_size_revcomm selects the best $n$ subsets of size $p$ using a reverse communication branch and bound algorithm.

For full information please refer to the NAG Library document for h05aa

https://support.nag.com/numeric/nl/nagdoc_30.2/flhtml/h/h05aaf.html

Parameters

irevcmint

On initial entry: must be set to $0$.

On intermediate entry: $irevcm$ must remain unchanged.

mincrint

Flag indicating whether the scoring function $f$ is increasing or decreasing.

$mincr=1$

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

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

mint

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

ipint

$p$, the number of features in the subset of interest.

nbestint

$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\ne nbest$ then $errno$ = 53 is returned.

dropint

On initial entry: $drop$ need not be set.

On intermediate entry: $drop$ must remain unchanged.

lzint

On initial entry: $lz$ need not be set.

On intermediate entry: $lz$ must remain unchanged.

zint, ndarray, shape $(m-ip)$, modified in place

On initial entry: $z$ need not be set.

On intermediate exit: $z[\text{i}-1]$, for $\text{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 entry: $z$ must remain unchanged.

On final exit: $z$ is undefined.

laint

On initial entry: $la$ need not be set.

On intermediate entry: $la$ must remain unchanged.

aint, ndarray, shape $(max(nbest,m))$, modified in place

On initial entry: $a$ need not be set.

On intermediate exit: $a[\text{j}-1]$, for $\text{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 entry: $a$ must remain unchanged.

On final exit: $a$ is undefined.

bscorefloat, ndarray, shape $(max(nbest,m))$, modified in place

On initial entry: $bscore$ need not be set.

On intermediate exit: $bscore$ is undefined.

On intermediate entry: $bscore[j-1]$ 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$.

bzint, ndarray, shape $(m-ip,nbest)$, modified in place

On initial entry: $bz$ need not be set.

On intermediate exit: $bz$ is used for storage between calls to best_subset_given_size_revcomm.

On intermediate entry: $bz$ must remain unchanged.

On final exit: the $j$th best subset is constructed by dropping the features specified in $bz[\text{i}-1,\text{j}-1]$, for $\text{j}=1,2,\dots ,la$, for $\text{i}=1,2,\dots ,m-ip$, from the set of all features, $\Omega$. The score for the $j$th best subset is given in $bscore[j-1]$.

mincntint

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

If $k=0$ then $f(S-\left\{x_i\right\})$ is never estimated.

If $mincnt<0$ then $k$ is set to $1$.

gammafloat

$\gamma$, the scaling factor used when estimating scores. If $gamma<0$ then $\gamma =1$ is used.

accfloat, array-like, shape $\left(2\right)$

A measure of the accuracy of the scoring function, $f$.

Letting $a_i={ϵ}_1\left|f\left(S_i\right)\right|+{ϵ}_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 acc\left[0\right]\le 1$ then ${ϵ}_1=acc\left[0\right]$, otherwise ${ϵ}_1=0$.

If $acc\left[1\right]\ge 0$ then ${ϵ}_2=acc\left[1\right]$, 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.

commdict, communication object, modified in place

Communication structure.

On initial entry: need not be set.

io_managerFileObjManager, optional

Manager for I/O in this routine.

Returns

irevcmint

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-1]$ from the full set of features, $\Omega$. 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-1]$ to the empty set, $\varnothing$. 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 best_subset_given_size_revcomm.

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

The score associated with the $j$th subset must be returned in $bscore[j-1]$.

On final exit: $irevcm=0$, and the algorithm has terminated.

dropint

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 final exit: $drop$ is undefined.

lzint

On intermediate exit: the number of features stored in $z$.

On final exit: $lz$ is undefined.

laint

On intermediate exit: if $la>0$, the number of subsets for which a score must be returned.

If $la=0$, the score for a single subset should be returned.

See $irevcm$ for additional details.

On final exit: the number of best subsets returned.

Raises

NagValueError

(errno $11$)

On entry, $irevcm=⟨value⟩$.

Constraint: $irevcm=0$ or $1$.

(errno $21$)

On entry, $mincr=⟨value⟩$.

Constraint: $mincr=0$ or $1$.

(errno $22$)

$mincr$ has changed between calls.

On intermediate entry, $mincr=⟨value⟩$.

On initial entry, $mincr=⟨value⟩$.

(errno $31$)

On entry, $m=⟨value⟩$.

Constraint: $m\ge 2$.

(errno $32$)

$m$ has changed between calls.

On intermediate entry, $m=⟨value⟩$.

On initial entry, $m=⟨value⟩$.

(errno $41$)

On entry, $ip=⟨value⟩$ and $m=⟨value⟩$.

Constraint: $1\le ip\le m$.

(errno $42$)

$ip$ has changed between calls.

On intermediate entry, $ip=⟨value⟩$.

On initial entry, $ip=⟨value⟩$.

(errno $51$)

On entry, $nbest=⟨value⟩$.

Constraint: $nbest\ge 1$.

(errno $52$)

$nbest$ has changed between calls.

On intermediate entry, $nbest=⟨value⟩$.

On initial entry, $nbest=⟨value⟩$.

(errno $61$)

$drop$ has changed between calls.

On intermediate entry, $drop=⟨value⟩$.

On initial entry, $drop=⟨value⟩$.

(errno $71$)

$lz$ has changed between calls.

On entry, $lz=⟨value⟩$.

On previous exit, $lz=⟨value⟩$.

(errno $91$)

$la$ has changed between calls.

On entry, $la=⟨value⟩$.

On previous exit, $la=⟨value⟩$.

(errno $111$)

$bscore[⟨value⟩]=⟨value⟩$, which is inconsistent with the score for the parent node. Score for the parent node is $⟨value⟩$.

(errno $131$)

$mincnt$ has changed between calls.

On intermediate entry, $mincnt=⟨value⟩$.

On initial entry, $mincnt=⟨value⟩$.

(errno $141$)

$gamma$ has changed between calls.

On intermediate entry, $gamma=⟨value⟩$.

On initial entry, $gamma=⟨value⟩$.

(errno $151$)

$acc\left[0\right]$ has changed between calls.

On intermediate entry, $acc\left[0\right]=⟨value⟩$.

On initial entry, $acc\left[0\right]=⟨value⟩$.

(errno $152$)

$acc\left[1\right]$ has changed between calls.

On intermediate entry, $acc\left[1\right]=⟨value⟩$.

On initial entry, $acc\left[1\right]=⟨value⟩$.

(errno $161$)

$comm$[‘icomm’] has been corrupted between calls.

(errno $181$)

$comm$[‘rcomm’] has been corrupted between calls.

Warns

NagAlgorithmicWarning

(errno $53$)

On entry, $nbest=⟨value⟩$.

But only $⟨value⟩$ best subsets could be calculated.

Notes

Given $\Omega =\{x_i:i\in Z,1\le i\le m\}$, a set of $m$ unique features and a scoring mechanism $f\left(S\right)$ defined for all $S\subseteq \Omega$ then best_subset_given_size_revcomm is designed to find $S_{o1}\subseteq \Omega ,\left|S_{o1}\right|=p$, an optimal subset of size $p$. Here $\left|S_{o1}\right|$ denotes the cardinality of $S_{o1}$, the number of elements in the set.

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

$$\begin{array}{cc}f\left(S_i\right)\le f\left(S_j\right)\text{,}& \text{for all}{S}_j\subseteq \Omega \text{and}{S}_i\subseteq S_j\end{array}$$

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

$${\text{maximize}}_{S\subseteq \Omega }f\left(S\right)\text{subject to}\left|S\right|=p$$

else if

$$\begin{array}{cc}f\left(S_i\right)\ge f\left(S_j\right)\text{,}& \text{for all}{S}_j\subseteq \Omega \text{and}{S}_i\subseteq S_j\end{array}$$

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

$${\text{minimize}}_{S\subseteq \Omega }f\left(S\right)\text{subject to}\left|S\right|=p\text{.}$$

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

As well as returning the optimal subset, $S_{o1}$, best_subset_given_size_revcomm can return the best $n$ solutions of size $p$. If $S_{o\text{i}}$ denotes the $\text{i}$th best subset, for $\text{i}=1,2,\dots ,n-1$, then the $(i+1)$th best subset is defined as the solution to either

$${\text{maximize}}_{S\subseteq \Omega -\{S_{oj}:j\in Z,1\le j\le i\}}f\left(S\right)\text{subject to}\left|S\right|=p$$

or

$${\text{minimize}}_{S\subseteq \Omega -\{S_{oj}:j\in Z,1\le j\le i\}}f\left(S\right)\text{subject to}\left|S\right|=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 $\Omega$. Assuming that [equation] holds then a particular node, defined by subset $S_i$, can be trimmed from the tree if $f\left(S_i\right)<\hat{f}\left(S_{on}\right)$ where $\hat{f}\left(S_{on}\right)$ 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 [equation] 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 [equation] 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 best_subset_given_size_revcomm 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{\mu }}_i$, an estimate of the contribution of that feature. An initial value of zero is used for both $c_i$ and ${\hat{\mu }}_i$. At any stage of the algorithm where both $f\left(S\right)$ and $f(S-\left\{x_i\right\})$ have been calculated (as opposed to estimated), the estimated contribution of the feature $x_i$ is updated to

$$\frac{c_i{\hat{\mu }}_i+[f\left(S\right)-f(S-\left\{x_j\right\})]}{c_i+1}$$

and $c_i$ is incremented by $1$, therefore, at each stage ${\hat{\mu }}_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\ge k$, for the user-supplied constant $k$, then rather than calculating $f(S-\left\{x_i\right\})$ this function estimates it using $\hat{f}(S-\left\{x_i\right\})=f\left(S\right)-\gamma {\hat{\mu }}_i$ or $\hat{f}\left(S\right)-\gamma {\hat{\mu }}_i$ if $f\left(S\right)$ has been estimated, where $\gamma$ 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 function 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\left(S\right)$ must have been calculated before $f(S-\left\{x_i\right\})$ can be calculated.

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