GitHub

Separation

PortfolioOptimisers.HopCountQuantile — Type
struct HopCountQuantile{__T_q} <: HopCountAlgorithm

Places the hop budget at a quantile of the observed hop separations.

The shipped HopCountAlgorithm. HopCount(; n = HopCountQuantile(; q = 0.25)) asks for the hop budget that relates about a quarter of the reachable pairs, instead of naming a number of hops that was right for one universe.

What it holds still

A stated n holds the number of hops still and lets the related-pair count move with the graph. This rule holds the count still — about q of the reachable pairs — and lets the number of hops move. On a cross-validation fold or a subproblem of a meta optimiser the second is usually what the caller meant, because the constraint strength a downstream consumer feels is the cardinality, not the hop number.

The rounding is where the two stop matching

A hop count is an Integer and the quantile is not, so the budget is rounded to the nearest hop. The related-pair count therefore lands near q rather than on it, and on a small graph the shells are coarse enough that it can miss by a lot — a hop budget can only ever select one of a handful of cardinalities. PathLengthQuantile has no such step and hits q closely; that is the sharpest practical difference between the two separations.

It pays for a traversal, but not for a structure

Resolving this rule runs separation_matrix once, which the hop-ball branch of _phylogeny_matrix does not otherwise do — it walks matrix powers instead. A dynamic budget costs one all-pairs traversal that a stated one does not.

It does not cost a second structure. The rule is handed the graph its consumer already built, through separation_graph, so the distance derivation — 98% of clusterise's runtime under VariationInfoDistance — is paid once per consumer call whether the budget is a rule or a number.

Algorithm

The steps below are the call operator's, which resolve_separation invokes.

  1. Measure the hop separations over g with separation_matrix, giving d. A bare HopCount is the probe, because that kernel dispatches on the separation's type and reads no field of it.
  2. Take the q-quantile of the reachable off-diagonal entries of d with separation_quantile.
  3. Round that quantile to the nearest Int, giving the hop budget. The smallest off-diagonal hop separation is 1, so the quantile never falls below one and the round never has to be clamped up to HopCount's floor.

Fields

  • q: Quantile of the observed separations to take as the budget. The reachable off-diagonal pairs are the population, so q is the fraction of them the budget relates.

Constructors

HopCountQuantile(;    q::Number = 0.25) -> HopCountQuantile

Keywords correspond to the struct's fields.

Validation

  • 0 <= q <= 1.

Examples

julia> HopCountQuantile()HopCountQuantile  q ┴ Float64: 0.25

Related

source
PortfolioOptimisers.PathLengthQuantile — Type
struct PathLengthQuantile{__T_q} <: PathLengthAlgorithm

Places the path-length budget at a quantile of the observed path separations.

The shipped PathLengthAlgorithm, and the direct answer to PathLength's own complaint that nobody has an intuition for a summed path in the units an AbstractDistanceEstimator emits. dmax = 0.37 is not a number a caller can reason about; "the budget that relates a quarter of the reachable pairs" is.

What it holds still

A stated dmax holds the radius still and lets the related-pair count move with the graph. This rule holds the count still and lets the radius move. Both are refitted per fold, so neither is stable in both senses at once — the choice is which of the two a downstream consumer is sensitive to, and for SemiDefinitePhylogeny and IntegerPhylogeny the constraint strength is the cardinality.

It reaches the cardinalities a hop count cannot

This is where the radius ball's one real gain becomes reachable by name. A hop budget steps through a handful of shell cardinalities and cannot stop between them; q is continuous, so PathLengthQuantile(; q = 0.3) asks for a cardinality directly and lands on it closely.

Algorithm

The steps below are the call operator's, which resolve_separation invokes.

  1. Measure the path separations over g with separation_matrix, giving d. A bare PathLength is the probe, for the same reason as on the hop rule.
  2. Take the q-quantile of the reachable off-diagonal entries of d with separation_quantile. That quantile is the radius budget, and it takes no rounding.

Fields

  • q: Quantile of the observed separations to take as the budget. The reachable off-diagonal pairs are the population, so q is the fraction of them the budget relates.

Constructors

PathLengthQuantile(;    q::Number = 0.25) -> PathLengthQuantile

Keywords correspond to the struct's fields.

Validation

  • 0 <= q <= 1.

Examples

julia> PathLengthQuantile()PathLengthQuantile  q ┴ Float64: 0.25

Related

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

One third of the extension contract of AbstractSeparationAlgorithm; separation_graph and separation_budget are the other two.

The graph-taking form is the interface

The separations depend on the structure alone, so separation_matrix(sep, g) is where each member's method lives and the estimator-taking form is a wrapper that calls separation_graph first. A consumer holding a graph — because it built one for resolve_separation, or because a test chose one — enters at the graph, and pays for one structure rather than two.

The wrapper is generic rather than per-member: it is separation_graph that knows which structure the member reads, so there is nothing left for a member to say here.

The unreachable sentinel

An unreachable pair carries whatever sentinel the underlying routine uses, not a repaired value: Graphs.gdistances reports typemax(Int) for HopCount, and Graphs.floyd_warshall_shortest_paths reports typemax(T) for PathLength, which on the Float64 weights it is handed is Inf. A consumer therefore reads an entry through is_related rather than comparing it against the budget itself, and keeps the evaluation of anything it scores the entry with inside a short-circuiting branch — an ifelse evaluates both arms, and ReciprocalDecay overflows 1 + d at typemax(Int), which a fractional power turns into a DomainError rather than a discarded number.

The two shipped members read the same structure differently

HopCount counts the edges of the binarised structure; PathLength sums the distances along them. Which structure each reads is separation_graph's answer, not this function's. All-pairs shortest paths come from one floyd_warshall_shortest_paths call rather than a Dijkstra per vertex — measured about 7 times faster on this shape, and within about 1.3 times of the breadth-first loop the hop count uses.

Algorithm

  1. Build the structure with separation_graph. The graph-taking methods are handed g and start at step 2.

  2. Measure every pair over that structure, through the branch that sep selects.

    • HopCount: one Graphs.gdistances breadth-first traversal per vertex, whose answer becomes that vertex's column of a dense Matrix{Int}.
    • PathLength: one Graphs.floyd_warshall_shortest_paths call over the whole graph, whose dists field is the matrix.

Arguments

  • sep: Separation algorithm. Its budget is not read; a member whose budget is still a rule measures the same separations.
  • g: Structure to measure over, from separation_graph.
  • nte: Network estimator. On the wrapper only, where the structure is derived from X on every call.
  • X: Data matrix (observations × assets).
  • dims: Dimension along which to perform the computation.
  • kwargs...: Additional keyword arguments forwarded to the underlying phylogeny routines.

Returns

  • d::Matrix: Square matrix of separations. d[i, k] is the separation between assets i and k, d[i, i] is zero, and an unreachable pair carries the sentinel above.

Related

source
PortfolioOptimisers.separation_budget — Function
separation_budget(sep::HopCount, nte::AbstractNetworkEstimator, d::MatNum)
separation_budget(sep::PathLength, nte::AbstractNetworkEstimator, d::MatNum)

Resolve the separation budget in scope: the separation beyond which a pair counts as unrelated.

One third of the extension contract of AbstractSeparationAlgorithm; separation_graph and separation_matrix are the other two. Split from separation_matrix because a consumer needs the budget on its own — to probe a decay before entering the assets × assets loop, or to threshold a matrix it already holds.

The separations are passed in, not recomputed

d is the matrix separation_matrix produced, so a member whose budget is observed rather than configured — the diameter of what the graph actually turned out to be — can read it without a second traversal. That is why the argument is the matrix and not a diameter: finding the largest finite entry is itself the assets² reduction, so passing a diameter would charge HopCount for one it ignores. Handing over d pushes the reduction into PathLength, the member that wants it.

nte is inert for what ships: it is the channel through which an extension budget can see the estimator that owns it. Inert arguments have precedent here — separation_decay's dmax is read by only one of five members.

The observed diameter is a ceiling, not only a default

PathLength clamps a chosen dmax to the observed diameter as well as substituting the diameter for nothing. The clamp truncates nothing — no pair sits beyond the diameter — so it is a scale-top correction and is visible only through LinearDecay, the one decay reading the budget. Without it, dmax = 100 on a graph of diameter 3.5 would flatten the scores towards a constant while forbidding no pair at all.

Algorithm

  1. Refuse a separation whose budget is still a rule. A HopCount carrying a HopCountAlgorithm, and a PathLength carrying a PathLengthAlgorithm, each throw here.

  2. Answer the budget, through the branch that sep selects.

    • HopCount: sep.n, the number of hops the caller stated. d is not read.
    • PathLength: walk d, keep the largest entry is_reachable admits, and call it delta, the observed diameter. Answer delta when sep.dmax is nothing, and the smaller of sep.dmax and delta otherwise.

Arguments

  • sep: Separation algorithm.
  • nte: Network estimator that owns sep. Inert for the shipped members.
  • d: Separation matrix from separation_matrix. Inert for HopCount, whose budget is configured rather than observed; read by PathLength, whose budget is capped by what the graph turned out to be.

Validation

  • Throws an ArgumentError if sep carries a budget rule rather than a value. Call resolve_separation first.

Returns

  • dmax::Number: Separation budget. Stated in the units sep measures in — hops for HopCount, the distance estimator's units for PathLength — so it is only ever compared against entries of d.

Related

source
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::AbstractSeparationAlgorithm, nte::AbstractNetworkEstimator,
                   X::MatNum; dims::Int = 1, kwargs...)
resolve_separation(sep::Union{<:HopCount{<:HopCountRule},
                              <:PathLength{<:PathLengthRule}},
                   nte::AbstractNetworkEstimator, X::MatNum; dims::Int = 1, kwargs...)

Replace a separation whose budget is a rule by one whose budget is a value.

The fourth kernel of AbstractSeparationAlgorithm, and the only one an extension does not have to write: the fallback on the abstract type returns sep unchanged, so a member whose budget is already a number passes through at no cost and gains nothing to maintain.

It is called by the consumer, not by the other kernels

Every shipped consumer of a network resolves nte.sep first and passes the resolved separation to separation_matrix and separation_budget — phylogeny_matrix, both clusterise methods, and phylogeny_features for Proximity.

The alternative was to resolve inside separation_budget, and it does not work: that kernel takes the separation matrix rather than the data, deliberately, so that HopCount never pays for a diameter reduction it ignores. A rule needs the structure, which is the one thing the budget kernel does not have. So separation_budget refuses an unresolved separation instead, and this kernel is where the structure is still in hand.

The rule is handed the structure, not asked to build one

g is separation_graph's structure, and the graph-taking methods are the interface: a consumer builds once, 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 estimator-taking methods are wrappers, and the resolved case has one of its own so that a stated budget builds nothing at all. Dispatching the wrapper on the rule-carrying parameterisation is what keeps that true — a single generic wrapper would derive a structure before discovering that the fallback ignores it.

The return check is a run-time one, and it has to be

A functor's return type is not part of its signature, so a HopCountAlgorithm cannot promise an Integer in the type system. This kernel checks the value and throws otherwise. The check earns its place: three readers use 0:n as a matrix-power count, where 0:1.5 drops a power silently.

Resolution goes back through the ordinary constructor, so the rule's answer meets exactly the validation a stated budget meets — n >= 1, n <= RESOURCE_LIMITS[].max_hop_count, and dmax > 0. That is why the resource cap needs no second check here: a rule that returns an absurd hop count is rejected by the same assert_resource_cap a stated one meets.

Algorithm

  1. Answer sep unchanged when its budget is already a value. The wrapper carries a method of its own for this case, so a stated budget builds no structure at all.
  2. Build the structure the rule measures over with separation_graph, on the wrapper. The graph-taking methods are handed g and start at step 3.
  3. Call the rule in the budget field with nte, X and g, forwarding dims and kwargs, giving the budget the rule answers.
  4. Check the type of that answer. A HopCount rule must answer with an Integer, and a PathLength rule with a Number. Throw an ArgumentError otherwise.
  5. Rebuild the member through its ordinary constructor, carrying the answer as its budget.

Arguments

  • sep: Separation algorithm, resolved or not.
  • nte: Network estimator that owns sep, handed to the rule as the channel to anything the graph does not carry.
  • X: Data matrix (observations × assets).
  • g: Structure the rule measures over, from separation_graph. Derived from X by the wrappers.
  • dims: Dimension along which to perform the computation.
  • kwargs...: Additional keyword arguments, forwarded to the rule.

Validation

  • A HopCountAlgorithm or Function in HopCount's n must return an Integer.
  • A PathLengthAlgorithm or Function in PathLength's dmax must return a Number. nothing is a stated budget, not a computed one.

Returns

  • sep::AbstractSeparationAlgorithm: The same member with a resolved budget. sep itself when the budget was already a value.

Related

source