Histogram

PortfolioOptimisers.AbstractBins — Type
abstract type AbstractBins <: AbstractAlgorithm

Abstract supertype for all histogram binning algorithms.

The histogram estimates of the mutual information and the variation of information get their bin count from a subtype of AbstractBins. The library has four of them: Knuth, FreedmanDiaconis, Scott and HacineGharbiRavier. An Integer in place of an algorithm fixes the count, as Int_Bin states.

An algorithm selects one bin count for each pair of variables, not for each variable, because the measures that read the count estimate a joint histogram.

Interfaces

To add a binning algorithm, subtype AbstractBins, keep its parameters in the fields of the struct, and add this method:

  • calc_num_bins(bins::AbstractBins, xj::VecNum, xi::VecNum, j::Integer, i::Integer, T::Integer) -> Integer: Returns the number of histogram bins for the pair (xj, xi).

Arguments

  • bins: Binning algorithm or fixed number of bins.
  • xj: Data vector for variable j.
  • xi: Data vector for variable i.
  • j: Index of variable j.
  • i: Index of variable i.
  • T: Number of observations.

Returns

  • nbins::Integer: Number of histogram bins for the variable pair.

Examples

The example below defines a minimal binning algorithm that always selects four bins.

julia> struct MyBins <: PortfolioOptimisers.AbstractBins endjulia> function PortfolioOptimisers.calc_num_bins(bins::MyBins, xj::PortfolioOptimisers.VecNum,                                                  xi::PortfolioOptimisers.VecNum, j::Integer,                                                  i::Integer, T::Integer)           return 4       endjulia> PortfolioOptimisers.calc_num_bins(MyBins(), [1.0, 2.0, 3.0], [3.0, 2.0, 1.0], 1, 2, 3)4

Related

source
PortfolioOptimisers.BinWidthBins — Type
abstract type BinWidthBins <: AbstractBins

Abstract supertype for all histogram binning algorithms based on a bin width selection rule.

A subtype of BinWidthBins computes a bin width from the data, and the bin count follows from that width. The library has three of them: Knuth, FreedmanDiaconis and Scott.

A subtype computes the bin width of one variable. The shared calc_num_bins method turns that width into a bin count for the pair, so a subtype has no calc_num_bins method of its own.

Interfaces

To add a bin width rule, subtype BinWidthBins, keep its parameters in the fields of the struct, and add this method:

  • bin_width(bins::BinWidthBins, x::VecNum) -> Number: Returns the histogram bin width of x under the rule.

Arguments

  • bins: Binning algorithm or fixed number of bins.
  • x: Data vector.

Returns

  • dx::Number: Optimal histogram bin width.

Examples

The example below defines a minimal bin width rule that divides the range of the data into four bins.

julia> struct MyWidth <: PortfolioOptimisers.BinWidthBins endjulia> function PortfolioOptimisers.bin_width(bins::MyWidth, x::PortfolioOptimisers.VecNum)           return (maximum(x) - minimum(x)) / 4       endjulia> PortfolioOptimisers.calc_num_bins(MyWidth(), [1.0, 2.0, 3.0], [3.0, 2.0, 1.0], 1, 2, 3)4

Related

source
PortfolioOptimisers.Knuth — Type
struct Knuth{__T_args, __T_kwargs} <: BinWidthBins

Histogram binning algorithm using Knuth's rule.

Knuth selects the number of bins that maximises the posterior probability of a piecewise-constant density model, given the data [44]. bin_width states the posterior and the search for its maximiser.

Fields

  • args: Additional positional arguments passed to the optimisation function.
  • kwargs: Additional keyword arguments passed to the optimisation function.

Constructors

Knuth(;  args::Tuple = (Optim.NelderMead(),),  kwargs::NamedTuple = (;)) -> Knuth

Examples

julia> Knuth()Knuth    args ┼ Tuple{Optim.NelderMead{Optim.AffineSimplexer, Optim.AdaptiveParameters}}: (Optim.NelderMead{Optim.AffineSimplexer, Optim.AdaptiveParameters}(Optim.AffineSimplexer(0.025, 0.5), Optim.AdaptiveParameters(1.0, 1.0, 0.75, 1.0)),)  kwargs ┴ @NamedTuple{}: NamedTuple()

Related

References

  • [44] K. H. Knuth. Optimal data-based binning for histograms and histogram-based probability density models. Digital Signal Processing 95, 102581 (2019). Section 2.3, Equations 31 and 32.
source
PortfolioOptimisers.FreedmanDiaconis — Type
struct FreedmanDiaconis <: BinWidthBins

Histogram binning algorithm using the Freedman-Diaconis rule.

FreedmanDiaconis selects the bin width from the interquartile range of the data and the number of observations [45]. The interquartile range reads the middle half of the sorted data, so a change to the value of the largest or the smallest observation does not change the width. The standard deviation that Scott reads does change.

Constructors

FreedmanDiaconis() -> FreedmanDiaconis

Examples

julia> FreedmanDiaconis()FreedmanDiaconis()

Related

References

  • [45] D. Freedman and P. Diaconis. On the histogram as a density estimator: L2 theory. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 57, 453–476 (1981). Section 1, Rule 1.8.
source
PortfolioOptimisers.Scott — Type
struct Scott <: BinWidthBins

Histogram binning algorithm using Scott's rule.

Scott selects the bin width from the standard deviation of the data and the number of observations [46]. The width minimises the integrated squared error of the histogram when the data are normal, as bin_width states.

Constructors

Scott() -> Scott

Examples

julia> Scott()Scott()

Related

References

  • [46] D. W. Scott. On optimal and data-based histograms. Biometrika 66, 605–610 (1979). Section 5, Equation 6.
source
PortfolioOptimisers.HacineGharbiRavier — Type
struct HacineGharbiRavier <: AbstractBins

Histogram binning algorithm using the Hacine-Gharbi-Ravier rule.

HacineGharbiRavier selects the bin count from the sample size and the Pearson correlation of the pair. The count minimises the mean square error of the estimate of the joint entropy. It is the default bins of mutual_info, variation_info and MutualInfoCovariance.

Mathematical definition

The Pearson correlation $\rho$ of the pair selects one of two closed forms. For $\rho^2 \neq 1$ the bi-histogram formula applies:

\[\begin{align} M &= \left[\frac{1}{\sqrt{2}} \sqrt{1 + \sqrt{1 + \frac{24 T}{1 - \rho^2}}}\right]\,. \end{align}\]

The form is singular at $\rho^2 = 1$, which is both ends of the correlation range, and it grows without bound as $\rho^2$ approaches 1. At $\rho^2 = 1$ one variable is a linear function of the other, so the joint histogram holds no information that one marginal does not hold. The library then applies the univariate formula, which is the formula for the marginal entropy:

\[\begin{align} z &= \sqrt[3]{8 + 324 T + 12 \sqrt{36 T + 729 T^2}}\,, \\ M &= \left[\frac{z}{6} + \frac{2}{3 z} + \frac{1}{3}\right]\,. \end{align}\]

Where:

  • $M$: Number of bins.
  • $T$: Number of observations.
  • $\rho$: Pearson correlation between the two series.
  • $[\cdot]$: Rounding to the nearest integer.

Equation 13 of [47] states the univariate form, and its Section 3.1 says that no earlier work on histogram estimation used that approach. Equations 36 and 37 of [48] state it again, as the bin count that minimises the mean square error. Equation 19 of [49] states the bi-histogram form, and its Equation 20 restates the univariate one from [47]. Snippet 3.3 in Section 3.9 of [26] gives both closed forms as code, and this method follows that code with one change. At sample sizes of 50, 250 and 1000, the method returns the bin counts that the two formulas give for the correlations of the pairs. The change is the guard at $\rho^2 = 1$, which the library adds. No equation of the cited works covers that case, and Snippet 3.3 applies the bi-histogram form at every correlation. Equation 16 of [47] and Equation 26 of [48] give a different bi-histogram form for the mutual information. The library does not use that form.

Constructors

HacineGharbiRavier() -> HacineGharbiRavier

Examples

julia> HacineGharbiRavier()HacineGharbiRavier()

Related

References

  • [47] A. Hacine-Gharbi, P. Ravier, R. Harba and T. Mohamadi. Low bias histogram-based estimation of mutual information for feature selection. Pattern Recognition Letters 33, 1302–1308 (2012). Section 3.1, Equation 13.
  • [48] A. Hacine-Gharbi, M. Deriche, P. Ravier, R. Harba and T. Mohamadi. A new histogram-based estimation technique of entropy and mutual information using mean squared error minimization. Computers & Electrical Engineering 39, 918–933 (2013). Section 3.2, Equations 36 and 37.
  • [49] A. Hacine-Gharbi and P. Ravier. A binning formula of bi-histogram for joint entropy estimation using mean square error minimization. Pattern Recognition Letters 101, 21–28 (2018). Section 2.2, Equation 19, and Section 3.1, Equation 20.
  • [26] M. M. De Prado. Machine learning for asset managers (Cambridge University Press, 2020). Section 3.9, Snippet 3.3.
source
PortfolioOptimisers.bin_width — Function
bin_width(::Scott, x::VecNum)

Compute the histogram bin width of x with Scott's rule [46].

Mathematical definition

\[\begin{align} \Delta_x &= \sigma_x \left(\frac{24 \sqrt{\pi}}{n}\right)^{1/3}\,. \end{align}\]

Where:

  • $\Delta_x$: Bin width.
  • $\sigma_x$: Uncorrected standard deviation of the data.
  • $n$: Number of observations.

Theorem 1.6 of [45] gives the width that minimises the integrated squared error of a histogram as $(6 / \gamma)^{1/3} n^{-1/3}$, with $\gamma = \int f'(x)^{2}\,\mathrm{d}x$. A normal density has $\gamma = 1 / (4\sqrt{\pi}\,\sigma^{3})$, which gives the formula above and the constant $(24\sqrt{\pi})^{1/3} \approx 3.4908$. Section 1 of that work names [46] as a formal computation of the same result. Equation 5 of [46] states the optimal width, and its Section 3 gives $2 \cdot 3^{1/3} \pi^{1/6} \sigma n^{-1/3}$ for Gaussian data, which equals $(24\sqrt{\pi})^{1/3} \sigma n^{-1/3}$. Equation 6 states the rule with the constant rounded to $3.49$ and an estimate in place of the standard deviation. The library keeps the exact constant. The work does not say which estimate of the standard deviation to use, and the library uses the uncorrected one.

Arguments

  • x: Data vector.

Returns

  • dx::Number: Optimal histogram bin width.

Related

References

  • [46] D. W. Scott. On optimal and data-based histograms. Biometrika 66, 605–610 (1979). Section 3, Equation 5, and Section 5, Equation 6.
  • [45] D. Freedman and P. Diaconis. On the histogram as a density estimator: L2 theory. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 57, 453–476 (1981). Section 1, Theorem 1.6.
source
bin_width(::FreedmanDiaconis, x::VecNum)

Compute the histogram bin width of x with the Freedman-Diaconis rule [45].

Mathematical definition

\[\begin{align} \Delta_x &= \frac{2 \, \mathrm{IQR}(x)}{n^{1/3}}\,. \end{align}\]

Where:

  • $\Delta_x$: Bin width.
  • $\mathrm{IQR}(x)$: Interquartile range of the data.
  • $n$: Number of observations.

A zero interquartile range gives a zero width, and so an infinite bin count. Data with many repeated values do this, for example a return series that is zero on most observations. The width is then the range of x divided by five, so the range holds five bins.

Arguments

  • x: Data vector.

Returns

  • dx::Number: Optimal histogram bin width.

Related

References

  • [45] D. Freedman and P. Diaconis. On the histogram as a density estimator: L2 theory. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 57, 453–476 (1981). Section 1, Rule 1.8.
source
bin_width(bins::Knuth, x::VecNum)

Compute the histogram bin width of x with Knuth's rule [44].

Mathematical definition

The bin width is the range of x divided by the bin count $M$ that maximises the marginal posterior probability of a piecewise-constant density model with $M$ equal-width bins over that range:

\[\begin{align} F(M) &= n \log M + \log\Gamma\!\left(\frac{M}{2}\right) - M \log\Gamma\!\left(\frac{1}{2}\right) - \log\Gamma\!\left(n + \frac{M}{2}\right) + \sum_{k=1}^{M} \log\Gamma\!\left(n_k + \frac{1}{2}\right)\,. \end{align}\]

Where:

  • $M$: Number of bins.
  • $n$: Number of observations.
  • $n_k$: Number of observations in bin $k$.

The maximiser is an integer, so no closed form gives it. The method searches for it.

Algorithm

  1. Read the range of x into rx, the difference of its two extrema. A constant x has a zero rx, and the method returns it as the width.
  2. Build the objective f, which takes a one-element vector Ms, floors its entry into the bin count M, and returns Inf when M is outside $[1, n]$. Data with many repeated values, such as a return series that is zero on most observations, make the posterior rise as the bins narrow, and the bound stops the count at one bin per observation.
  3. Inside f, bin the data into the counts nk over M equal-width bins of the range, and return the negated posterior of the mathematical definition. The optimiser minimises, so f changes the sign.
  4. Take the start point M0 from the bin count that the Freedman-Diaconis rule gives for x, plus one, and cap it at $n + 1/2$, so that it floors to at most $n$.
  5. Minimise f from M0 with Optim.optimize, which gets bins.args and bins.kwargs. The default args is a Nelder-Mead simplex.
  6. Floor the minimiser into a bin count, clamp it to $[1, n]$, and return the range divided by it.

Arguments

  • bins: Binning algorithm or fixed number of bins.
  • x: Data vector.

Returns

  • dx::Number: Optimal histogram bin width.

Related

References

  • [44] K. H. Knuth. Optimal data-based binning for histograms and histogram-based probability density models. Digital Signal Processing 95, 102581 (2019). Section 2.3, Equations 31 and 32.
source
PortfolioOptimisers.calc_num_bins — Function
calc_num_bins(bins::BinWidthBins, xj::VecNum, xi::VecNum, j::Integer, i::Integer,
              args...)
calc_num_bins(bins::HacineGharbiRavier, xj::VecNum, xi::VecNum, j::Integer,
              i::Integer, T::Integer)
calc_num_bins(bins::Integer, args...)

Compute the number of histogram bins for a pair of variables with a binning algorithm.

The function dispatches on the type of bins, and the three methods read different arguments. Only the HacineGharbiRavier method reads T, and the Integer method reads none of them.

Algorithm

The BinWidthBins method turns a bin width into a bin count.

  1. Read the range of xj into rxj, and divide it by bin_width of xj. The result is k1. A constant xj has a zero range and a zero width, and their quotient is NaN, so k1 is one bin.
  2. When j and i differ, repeat step 1 for xi to get k2, and select the larger of k1 and k2. The joint histogram is square, so one count is for both axes, and the larger of the two keeps the finer resolution. When j and i are equal, the pair is a variable against itself, so select k1 and do not read xi.
  3. Round the selected value to the nearest integer, and return it.

The HacineGharbiRavier method reads the pair instead of a width.

  1. Take the Pearson correlation of the pair into corr.
  2. Return one bin when corr is NaN. The correlation of a pair is 0 / 0 when one variable is constant, and one bin holds a constant, as in step 1 of the BinWidthBins method.
  3. Select the closed form of HacineGharbiRavier that corr falls under.
  4. Round the selected value to the nearest integer, and return it.

The Integer method returns bins unchanged.

Arguments

  • bins: Binning algorithm or fixed number of bins.
  • xj: Data vector for variable j.
  • xi: Data vector for variable i.
  • j: Index of variable j.
  • i: Index of variable i.
  • T: Number of observations.
  • args...: Ignored arguments, so that the three methods share one call site.

Returns

  • nbins::Integer: Number of histogram bins for the variable pair.

Related

source

References

[26]
M. M. De Prado. Machine learning for asset managers (Cambridge University Press, 2020).
[44]
K. H. Knuth. Optimal data-based binning for histograms and histogram-based probability density models. Digital Signal Processing 95, 102581 (2019).
[45]
D. Freedman and P. Diaconis. On the histogram as a density estimator: L2 theory. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 57, 453–476 (1981).
[46]
D. W. Scott. On optimal and data-based histograms. Biometrika 66, 605–610 (1979).
[47]
A. Hacine-Gharbi, P. Ravier, R. Harba and T. Mohamadi. Low bias histogram-based estimation of mutual information for feature selection. Pattern Recognition Letters 33, 1302–1308 (2012).
[48]
A. Hacine-Gharbi, M. Deriche, P. Ravier, R. Harba and T. Mohamadi. A new histogram-based estimation technique of entropy and mutual information using mean squared error minimization. Computers & Electrical Engineering 39, 918–933 (2013).
[49]
A. Hacine-Gharbi and P. Ravier. A binning formula of bi-histogram for joint entropy estimation using mean square error minimization. Pattern Recognition Letters 101, 21–28 (2018).