Histogram
PortfolioOptimisers.AbstractBins — Type
abstract type AbstractBins <: AbstractAlgorithmAbstract 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 variablej.xi: Data vector for variablei.j: Index of variablej.i: Index of variablei.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)4Related
PortfolioOptimisers.BinWidthBins — Type
abstract type BinWidthBins <: AbstractBinsAbstract 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 ofxunder 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)4Related
PortfolioOptimisers.Knuth — Type
struct Knuth{__T_args, __T_kwargs} <: BinWidthBinsHistogram 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 = (;)) -> KnuthExamples
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.
PortfolioOptimisers.FreedmanDiaconis — Type
struct FreedmanDiaconis <: BinWidthBinsHistogram 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() -> FreedmanDiaconisExamples
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.
PortfolioOptimisers.Scott — Type
struct Scott <: BinWidthBinsHistogram 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() -> ScottExamples
julia> Scott()Scott()Related
References
- [46] D. W. Scott. On optimal and data-based histograms. Biometrika 66, 605–610 (1979). Section 5, Equation 6.
PortfolioOptimisers.HacineGharbiRavier — Type
struct HacineGharbiRavier <: AbstractBinsHistogram 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() -> HacineGharbiRavierExamples
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.
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.
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.
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
- Read the range of
xintorx, the difference of its two extrema. A constantxhas a zerorx, and the method returns it as the width. - Build the objective
f, which takes a one-element vectorMs, floors its entry into the bin countM, and returnsInfwhenMis 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. - Inside
f, bin the data into the countsnkoverMequal-width bins of the range, and return the negated posterior of the mathematical definition. The optimiser minimises, sofchanges the sign. - Take the start point
M0from the bin count that the Freedman-Diaconis rule gives forx, plus one, and cap it at $n + 1/2$, so that it floors to at most $n$. - Minimise
ffromM0withOptim.optimize, which getsbins.argsandbins.kwargs. The defaultargsis a Nelder-Mead simplex. - 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.
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.
- Read the range of
xjintorxj, and divide it bybin_widthofxj. The result isk1. A constantxjhas a zero range and a zero width, and their quotient isNaN, sok1is one bin. - When
jandidiffer, repeat step 1 forxito getk2, and select the larger ofk1andk2. The joint histogram is square, so one count is for both axes, and the larger of the two keeps the finer resolution. Whenjandiare equal, the pair is a variable against itself, so selectk1and do not readxi. - Round the selected value to the nearest integer, and return it.
The HacineGharbiRavier method reads the pair instead of a width.
- Take the Pearson correlation of the pair into
corr. - Return one bin when
corrisNaN. The correlation of a pair is0 / 0when one variable is constant, and one bin holds a constant, as in step 1 of theBinWidthBinsmethod. - Select the closed form of
HacineGharbiRavierthatcorrfalls under. - 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 variablej.xi: Data vector for variablei.j: Index of variablej.i: Index of variablei.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
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).