Separation
PortfolioOptimisers.separation_matrix — Function
separation_matrix(sep::HopCount, g::Graphs.AbstractGraph)
separation_matrix(sep::PathLength, g::Graphs.AbstractGraph)
separation_matrix(sep::AbstractSeparationAlgorithm, nte::AbstractNetworkEstimator,
X::MatNum; dims::Int = 1, kwargs...)Compute the dense assets × assets matrix of separations under a separation algorithm.
This function is one of the three kernels that a member of AbstractSeparationAlgorithm implements. separation_graph and separation_budget are the other two.
The method that takes a graph is the interface
The separations depend on the structure alone. Each member implements separation_matrix(sep, g), and the method that takes nte is a wrapper that first calls separation_graph. A consumer that holds a graph calls the method that takes g, and builds one structure and not two. It can hold a graph because it built one for resolve_separation, or because a test selected one.
One wrapper serves every member. separation_graph selects the structure that the member reads, so a member has nothing to add here.
The unreachable sentinel
An unreachable pair keeps the sentinel of the routine that measures it, and the function does not repair it. Graphs.gdistances gives typemax(Int) for HopCount. Graphs.floyd_warshall_shortest_paths gives typemax(T) for PathLength, which is Inf for its Float64 weights. A consumer reads an entry through is_related, and does not compare it with the budget itself.
A consumer must also put the score of an entry inside a branch that short-circuits. An ifelse evaluates both arms. ReciprocalDecay overflows 1 + d at typemax(Int), and a fractional power then raises a DomainError.
The two shipped members read the same structure differently
HopCount counts the edges of the binary structure. PathLength sums the distances along them. separation_graph selects the structure that each member reads. One call to floyd_warshall_shortest_paths gives the shortest paths of all pairs, and the function does not run Dijkstra from each vertex. On this shape, the measured call is about 7 times faster than Dijkstra, and about 1.3 times slower than the breadth-first loop of the hop count.
Algorithm
Build the structure with
separation_graph. The methods that takegreceive it and start at step 2.Measure every pair over that structure, through the branch that
sepselects.HopCount: one breadth-first traversal withGraphs.gdistancesfrom each vertex. Its answer is the column of that vertex in a denseMatrix{Int}.PathLength: one call toGraphs.floyd_warshall_shortest_pathsover the whole graph. Itsdistsfield is the matrix.
Arguments
sep: Separation algorithm. The function does not read its budget, so a member whose budget is a rule measures the same separations.g: Structure to measure over, fromseparation_graph.nte: Network estimator. Only the wrapper takes it, and the wrapper builds the structure fromXon every call.X: Data matrixobservations × assetsif thedimskeyword does not exist ordims = 1,assets × observationswhendims = 2.dims: Dimension along which the computation runs.kwargs...: Keyword arguments that the wrapper passes toseparation_graph.
Returns
d::Matrix: Square matrix of separations.d[i, k]is the separation between assetsiandk,d[i, i]is zero, and an unreachable pair carries the sentinel above.
Related
PortfolioOptimisers.separation_budget — Function
separation_budget(sep::HopCount, nte::AbstractNetworkEstimator, d::MatNum)
separation_budget(sep::PathLength, nte::AbstractNetworkEstimator, d::MatNum)Return the separation budget, the separation beyond which a pair counts as unrelated.
This function is one of the three kernels that a member of AbstractSeparationAlgorithm implements. separation_graph and separation_matrix are the other two. It is separate from separation_matrix, because a consumer can need the budget alone. The consumer can test a decay before its loop over the assets × assets pairs, or apply a threshold to a matrix that it already holds.
The function takes the separations, and does not compute them again
d is the matrix that separation_matrix made. A member can observe its budget from the graph, and not take it from the configuration. The diameter of the graph is such a budget, and the member reads it from d with no second traversal. This is why the argument is the matrix, and not a diameter. The largest finite entry is a reduction over assets² entries, and a diameter argument makes HopCount pay for a reduction that it does not read. With d, only PathLength, the member that needs the reduction, does it.
The shipped members do not read nte. It lets the budget of an extension read the estimator that owns it. separation_decay has a similar argument, because only one of its four members reads dmax.
The observed diameter is a ceiling, not only a default
PathLength puts the observed diameter in place of dmax = nothing. It also clamps a stated dmax to the observed diameter. The clamp removes no pair, because no pair is beyond the diameter. It corrects the top of the scale, and only LinearDecay, the one decay that reads the budget, shows it. Without the clamp, dmax = 100 on a graph of diameter 3.5 moves every score near to one constant, and refuses no pair.
Algorithm
Refuse a separation whose budget is not resolved. A
HopCountthat holds aFractionOfor aHopCountAlgorithm, and aPathLengththat holds aFractionOfor aPathLengthAlgorithm, each throw here.Return the budget, through the branch that
sepselects.HopCount:sep.n.val, the number of hops of itsCountOf. The method does not readd.PathLength: finddelta, the largest entry ofdthatis_reachableadmits. It is the observed diameter. Returndeltawhensep.dmaxisnothing, and the smaller ofsep.dmaxanddeltaotherwise.
Arguments
sep: Separation algorithm.nte: Network estimator that ownssep. The shipped members do not read it.d: Separation matrix fromseparation_matrix.HopCountdoes not read it, because its budget comes from the configuration.PathLengthreads it, because the observed diameter caps its budget.
Validation
- Throws an
ArgumentErrorifsepholds a fraction or a budget rule and not a value. Callresolve_separationfirst.
Returns
dmax::Number: Separation budget, in the units ofsep. The unit is the hop forHopCount, and the unit of the distance estimator forPathLength. A consumer compares it only with entries ofd.
Related
PortfolioOptimisers.resolve_separation — Function
resolve_separation(sep::AbstractSeparationAlgorithm, nte::AbstractNetworkEstimator,
X::MatNum, g::Graphs.AbstractGraph; dims::Int = 1, kwargs...)
resolve_separation(sep::HopCount{<:HopCountRule}, nte::AbstractNetworkEstimator,
X::MatNum, g::Graphs.AbstractGraph; dims::Int = 1, kwargs...)
resolve_separation(sep::PathLength{<:PathLengthRule}, nte::AbstractNetworkEstimator,
X::MatNum, g::Graphs.AbstractGraph; dims::Int = 1, kwargs...)
resolve_separation(sep::HopCount{<:FractionOf}, nte::AbstractNetworkEstimator,
X::MatNum, g::Graphs.AbstractGraph; kwargs...)
resolve_separation(sep::PathLength{<:FractionOf}, nte::AbstractNetworkEstimator,
X::MatNum, g::Graphs.AbstractGraph; kwargs...)
resolve_separation(sep::AbstractSeparationAlgorithm, nte::AbstractNetworkEstimator,
X::MatNum; dims::Int = 1, kwargs...)
resolve_separation(sep::Union{HopCount{<:Union{HopCountRule, FractionOf}},
PathLength{<:Union{PathLengthRule, FractionOf}}},
nte::AbstractNetworkEstimator, X::MatNum; dims::Int = 1, kwargs...)Replace a separation whose budget is a fraction or a rule by one whose budget is a value.
This function is the fourth kernel of AbstractSeparationAlgorithm, and the only one that an extension does not have to implement. The method on the abstract type returns sep unchanged. A member whose budget is a number costs nothing here, and needs no method of its own.
A fraction is a quantile of the separations
A FractionOf budget names the share of the reachable pairs that the budget relates. The kernel measures the separations over g with separation_matrix, and takes their quantile at val over the reachable off-diagonal pairs with separation_quantile. HopCount rounds the quantile to the nearest Int, because a hop count is an Integer. The smallest off-diagonal hop separation is 1, so the rounded value is never below one. PathLength takes the quantile as its radius, with no rounding.
The fraction costs one traversal of all pairs, and a stated budget does not. The hop branch of _phylogeny_matrix does not run the traversal otherwise, because that branch sums matrix powers. The fraction does not cost a second structure, because it reads the graph that its consumer built. Under VariationInfoDistance, the distance is 98% of the run time of clusterise.
The consumer calls it, and the other kernels do not
Every shipped consumer of a network first resolves nte.sep. It then passes the resolved separation to separation_matrix and separation_budget. The consumers are phylogeny_matrix, both clusterise methods, and phylogeny_features for Proximity.
separation_budget cannot resolve a fraction or a rule. It takes the separation matrix and not the data, so that HopCount does not pay for a reduction to a diameter that it does not read. A fraction and a rule need the structure, and the budget kernel does not have it. separation_budget refuses a separation that is not resolved, and this kernel resolves it while the structure is available.
The rule receives the structure, and does not build one
g is the structure of separation_graph, and the methods that take g are the interface. A consumer builds the structure one time. It resolves the rule against that graph, and measures the separations over the same graph. The rule reads what it needs through separation_matrix(sep, g).
The methods that take only nte and X are wrappers. The resolved case has a wrapper of its own, so that a stated budget builds no structure. The wrapper for a rule dispatches on the type parameter that holds the rule. One generic wrapper builds a structure before it finds that the method on the abstract type does not read it.
The check of the return value runs at run time, and it must
The return type of a functor is not part of its signature, so the type system cannot make a HopCountAlgorithm return an Integer. This kernel checks the value, and throws if it is not an Integer. The check is necessary. Three readers use 0:n.val as a count of matrix powers, and 0:1.5 removes a power with no error.
The kernel builds the resolved member through its usual constructor, which wraps a hop count in a CountOf. The answer of a fraction or a rule meets the same checks as a stated budget: n.val >= 1, n.val <= RESOURCE_LIMITS[].max_hop_count and dmax > 0. For this reason, the resource cap needs no second check here. The same assert_resource_cap refuses a hop count that is too large, from a rule or from the caller.
Algorithm
- Return
sepunchanged when its budget is a value. The wrapper has a method of its own for this case, so a stated budget builds no structure. - In the wrapper, build the structure that the fraction or the rule measures over with
separation_graph. The methods that takegreceive it and start at step 3. - For a
FractionOf, measured = separation_matrix(sep, g)and takeseparation_quantile(sep, d, val). Round it to the nearestIntfor aHopCount. Go to step 6. - For a rule, call it with
nte,Xandg, and pass ondimsandkwargs. The rule returns the budget. - Check the type of that answer. A
HopCountrule must return anInteger, and aPathLengthrule must return aNumber. Throw anArgumentErrorotherwise. - Build the member again through its usual constructor, with the answer as its budget.
Arguments
sep: Separation algorithm, resolved or not.nte: Network estimator that ownssep. A rule receives it, and can read from it what the graph does not hold. A fraction does not read it.X: Data matrixobservations × assetsif thedimskeyword does not exist ordims = 1,assets × observationswhendims = 2.g: Structure that the fraction or the rule measures over, fromseparation_graph. The wrappers build it fromX.dims: Dimension along which the computation runs.kwargs...: Keyword arguments that the function passes to the rule.
Validation
- A
HopCountAlgorithmorFunctioninHopCount'snmust return anInteger. - A
PathLengthAlgorithmorFunctioninPathLength'sdmaxmust return aNumber.nothingis a stated budget, not a computed one. - A fraction needs at least one reachable pair of distinct assets.
separation_quantilethrows anArgumentErrorotherwise.
Returns
sep::AbstractSeparationAlgorithm: The same member with a resolved budget. It issepwhen the budget is a value.
Related