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
GridSearchCrossValidationscores for the samep. - $\Vert$: Concatenation of two sequences.
- $\Theta$: Trial sequence, the points of the search space that
make_p_griddraws. 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
- Check that no value vector is empty.
- If a value of any parameter set is a distribution, do steps 3 and 4. Otherwise, do steps 5 to 8.
- Check
n_iterthroughassert_search_grid_cap. - For each of the
n_itertrials, pick a parameter set uniformly, and draw one value of each of its keys throughdraw_search_point. - Count the grid points of each parameter set, giving
sizes, and their sumN, both asBigInt. - Set
M = min(n_iter, N), and check it throughassert_search_grid_cap. - Draw
Mdistinct positions of1:Nin ascending order throughsample_grid_positions, givingidx. WhenM == N,idxis1:N. - Decode each position into its grid point through
search_grid_point. - Return one parameter set per trial, each key with a vector of its one value.
Arguments
ps: One parameter set, a vector ofkey => valuepairs or a dictionary from key to value. A value is a vector of candidate values or aDistributions.Distribution.pss: A vector of parameter sets, each of the form ofps.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
IsEmptyErrornames the key. - The trial count holds at most
RESOURCE_LIMITS[].max_search_gridcandidates, throughassert_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
RandomisedSearchCrossValidationdraw_search_pointsample_grid_positionssearch_grid_pointlens_val_gridassert_search_grid_cap
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.
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
- If
N <= typemax(Int), drawMpositions of1:Nwithout replacement throughStatsBase.sample, in ascending order, and return them. - Otherwise, draw positions of
1:Nuniformly and add each new one to a set, until the set holdsMpositions. - 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, withM <= N.
Returns
idx::AbstractVector{<:Integer}: TheMpositions, in ascending order.
Related
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
- For each key of
psin its order of iteration, draw one value from its distribution or its value vector withrand. - 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 ofkey => valuepairs or a dictionary from key to value. A value is a vector of candidate values or aDistributions.Distribution.
Returns
point::AbstractVector{<:Pair}: Onekey => [value]pair per key ofps.
Related
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
- Subtract the sizes of the sets before point
ifromi, giving the setland the positionrof the point in that set, from0. - For each key of set
lin its order of iteration, take the remainder ofrdivided by the length of its value vector as the offset of the value, and setrto the quotient. - Return the keys of set
l, each with a vector of its value.
Arguments
pss: The parameter sets, each a vector ofkey => valuespairs 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, from1tosum(sizes).
Returns
point::AbstractVector{<:Pair}: Onekey => [value]pair per key of setl.
Related
References
- [226]
- J. Bergstra and Y. Bengio. Random search for hyper-parameter optimization. Journal of Machine Learning Research 13, 281–305 (2012).