Randomised search cross validation: private API

PortfolioOptimisers.make_p_grid — Function
make_p_grid(ps::Union{AbstractDict, AbstractVector{<:Pair}}, n_iter::Integer,
            rng::Random.AbstractRNG)
make_p_grid(pss::AbstractVector{<:Union{AbstractDict, AbstractVector{<:Pair}}},
            n_iter::Integer, rng::Random.AbstractRNG)

Draw the trials of a randomised search, at most n_iter points of the search space, each a joint value of every key of one parameter set.

The output is a grid of one-point parameter sets, so the grid search of the trials scores each trial once, and no two trials combine into a new candidate.

Mathematical definition

When every value of every parameter set is a vector:

\[\begin{align} \Lambda^{(l)} &= V_1 \times V_2 \times \cdots \times V_k\,, \quad l = 1, \ldots, m\,, \\ \Lambda &= \Lambda^{(1)} \Vert \Lambda^{(2)} \Vert \cdots \Vert \Lambda^{(m)}\,, \\ \Theta &\sim \mathcal{U}\left\{ S \subseteq \Lambda : |S| = \min\left(n, |\Lambda|\right) \right\}\,. \end{align}\]

When a value is a distribution:

\[\begin{align} l_t &\sim \mathcal{U}\{1, \ldots, m\}\,, \quad t = 1, \ldots, n\,, \\ \lambda_{tj} &\sim D_j\,, \quad j = 1, \ldots, k\,, \\ \theta_t &= \left(\lambda_{t1}, \ldots, \lambda_{tk}\right)\,. \end{align}\]

In the first form $V_j$ and $k$ belong to the $l$-th parameter set. In the second form $D_j$ and $k$ belong to the set $l_t$.

Where:

  • $\Lambda^{(l)}$: Space of the $l$-th parameter set, the product of its value vectors.
  • $V_j$: Candidate values of the $j$-th key of one parameter set, the value vector that the set gives the key.
  • $k$: Key count of one parameter set.
  • $m$: Parameter set count, the count of the parameter sets that the search concatenates.
  • $\Lambda$: Search space, the concatenation of the spaces of the parameter sets. It is the grid that GridSearchCrossValidation scores for the same p.
  • $\Vert$: Concatenation of two sequences.
  • $\Theta$: Trial sequence, the points of the search space that make_p_grid draws. It is the grid that the grid search of the trials scores.
  • $n$: Trial count, the field n_iter.
  • $\mathcal{U}$: Uniform law over a finite set.
  • $l_t$: Parameter set of trial $t$.
  • $\lambda_{tj}$: Trial value, the value of the $j$-th key at trial $t$.
  • $D_j$: Law of the $j$-th key of one parameter set. It is the distribution that the set gives the key, or the uniform law over the entries of its value vector.
  • $\theta_t$: Trial $t$, one value of every key of its parameter set.

[226] draws independent trials from the space that a grid spans. The first form departs from it in one point: it draws the points of a finite space without replacement, so no fit repeats. It keeps the order of $\Lambda$, so when $n \geq |\Lambda|$, $\Theta$ is the grid of GridSearchCrossValidation in its own order. The second form draws the trials independently, so two trials can be equal. It picks a parameter set with equal probability, because a set that holds a distribution has no count of points to weight it by.

Algorithm

  1. Check that no value vector is empty.
  2. If a value of any parameter set is a distribution, do steps 3 and 4. Otherwise, do steps 5 to 8.
  3. Check n_iter through assert_search_grid_cap.
  4. For each of the n_iter trials, pick a parameter set uniformly, and draw one value of each of its keys through draw_search_point.
  5. Count the grid points of each parameter set, giving sizes, and their sum N, both as BigInt.
  6. Set M = min(n_iter, N), and check it through assert_search_grid_cap.
  7. Draw M distinct positions of 1:N in ascending order through sample_grid_positions, giving idx. When M == N, idx is 1:N.
  8. Decode each position into its grid point through search_grid_point.
  9. Return one parameter set per trial, each key with a vector of its one value.

Arguments

  • ps: One parameter set, a vector of key => value pairs or a dictionary from key to value. A value is a vector of candidate values or a Distributions.Distribution.
  • pss: A vector of parameter sets, each of the form of ps.
  • n_iter: The trial count $n$.
  • rng: The random number generator of the draw.

Validation

  • Every value vector holds at least one value. Otherwise an IsEmptyError names the key.
  • The trial count holds at most RESOURCE_LIMITS[].max_search_grid candidates, through assert_search_grid_cap. The check reads the count of the trials, not the count of $\Lambda$, because the search scores the trials alone.

Returns

  • trials::AbstractVector{<:AbstractVector{<:Pair}}: One parameter set per trial, in the order of $\Theta$. The value of each key is a vector of one value.

Related

References

  • [226] J. Bergstra and Y. Bengio. Random search for hyper-parameter optimization. Journal of Machine Learning Research 13, 281–305 (2012). Section 1, Equation 4.
source
PortfolioOptimisers.sample_grid_positions — Function
sample_grid_positions(rng::Random.AbstractRNG, N::Integer, M::Integer)

Draw M distinct positions of 1:N uniformly, in ascending order.

Each subset of M positions has the same probability. When N fits in an Int, StatsBase.sample draws without replacement. A larger N overflows its sampler, so the draw repeats a uniform pick of 1:N and skips a position that it already holds. make_p_grid caps M at RESOURCE_LIMITS[].max_search_grid, which is far below typemax(Int), so a skip almost never happens on that branch.

Algorithm

  1. If N <= typemax(Int), draw M positions of 1:N without replacement through StatsBase.sample, in ascending order, and return them.
  2. Otherwise, draw positions of 1:N uniformly and add each new one to a set, until the set holds M positions.
  3. Return the positions of the set in ascending order.

Arguments

  • rng: The random number generator of the draw.
  • N: The count of the positions.
  • M: The count of the positions to draw, with M <= N.

Returns

  • idx::AbstractVector{<:Integer}: The M positions, in ascending order.

Related

source
PortfolioOptimisers.draw_search_point — Function
draw_search_point(rng::Random.AbstractRNG, ps)

Draw one trial of the parameter set ps, as a parameter set whose keys each hold a vector of one value.

Each key draws on its own with rand. A distribution gives one draw, and a value vector gives one of its entries with equal probability. A multivariate distribution gives one vector.

Algorithm

  1. For each key of ps in its order of iteration, draw one value from its distribution or its value vector with rand.
  2. Return the keys, each with a vector of its value.

Arguments

  • rng: The random number generator of the draw.
  • ps: One parameter set, a vector of key => value pairs or a dictionary from key to value. A value is a vector of candidate values or a Distributions.Distribution.

Returns

  • point::AbstractVector{<:Pair}: One key => [value] pair per key of ps.

Related

source
PortfolioOptimisers.search_grid_point — Function
search_grid_point(pss::AbstractVector, sizes::AbstractVector{<:Integer}, i::Integer)

Give point i of the concatenated grid of the parameter sets pss, as a parameter set whose keys each hold a vector of one value.

The order of the points is the order of lens_val_grid. The sets come in the order of pss, and inside one set the first key varies fastest.

Algorithm

  1. Subtract the sizes of the sets before point i from i, giving the set l and the position r of the point in that set, from 0.
  2. For each key of set l in its order of iteration, take the remainder of r divided by the length of its value vector as the offset of the value, and set r to the quotient.
  3. Return the keys of set l, each with a vector of its value.

Arguments

  • pss: The parameter sets, each a vector of key => values pairs or a dictionary from key to values.
  • sizes: The count of the grid points of each set, the product of the lengths of its value vectors.
  • i: The position of the point in the concatenated grid, from 1 to sum(sizes).

Returns

  • point::AbstractVector{<:Pair}: One key => [value] pair per key of set l.

Related

source

References

[226]
J. Bergstra and Y. Bengio. Random search for hyper-parameter optimization. Journal of Machine Learning Research 13, 281–305 (2012).