Extended Histogram-based Outlier Score (EHBOS)

Tanvir Islam

REVIEW 4 major objections 4 minor 3 references

Extended Histogram-based Outlier Score (EHBOS)

T0 review · 4 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read EHBOS detects dependency-driven outliers by averaging normalized 1D and 2D histogram scores, beating HBOS on glass, cardio, and satellite.

desk verdict EHBOS is a plausible but thinly supported incremental extension of HBOS; the missing empty-bin rule for 2D histograms makes the reported AUC gains unverifiable as stated. read the letter →

arxiv 2502.05719 v3 pith:36TR5LQ7 submitted 2025-02-08 cs.LG cs.AIstat.ML

Tanvir Islam This is my paper · ORCID

classification cs.LGcs.AIstat.ML

keywords outlierdetectionanomalyhistogram-basedscoreHBOSEHBOStwo-dimensionalhistogramfeaturedependenciesROCAUC

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proposes EHBOS, a variant of the histogram-based outlier score HBOS. HBOS scores each feature independently, so it misses points that are anomalous only in how features combine. EHBOS adds a two-dimensional histogram for every feature pair, normalizes the resulting score, and averages it with the normalized HBOS score. On 17 benchmark datasets, EHBOS raises ROC AUC on several sets where feature interactions matter, including glass, cardio, and satellite, while staying close to HBOS on most others. The payoff is a cheap, interpretable detector that catches contextual and dependency-driven anomalies without fitting a model.

What carries the argument

The load-bearing object is the EHBOS score, the average of a normalized one-dimensional histogram score and a normalized two-dimensional histogram score. The 2D histogram of a feature pair estimates joint density by counting points in rectangular bins and dividing by bin area; taking the negative logarithm turns sparse joint regions into large outlier contributions, and summing over all pairs lets the score respond to deviations in the relationship between two features rather than in either feature alone.

What would settle it

Take a two-feature dataset where a known outlier lies in an empty 2D bin while all normal points have nonzero bin counts: if EHBOS gives that outlier an infinite or default-capped score, the result is decided by the binning grid rather than by dependency structure. Alternatively, rerun the reported mnist and optdigits experiments with an explicit empty-bin rule such as Laplace smoothing, a floor density, or skipping empty bins; if the drops from 0.6140 to 0.4647 and from 0.8279 to 0.6267 change materially, the averaging claim is not robust to binning artifacts.

Watch

Extended reading notes

Core claim

The central claim is that $s_{\mathrm{EHBOS}} = (s_{\mathrm{1D}} + s_{\mathrm{2D}})/2$ identifies outliers that HBOS misses, specifically when anomalies are defined by pairwise feature interactions. EHBOS computes the usual per-feature density estimates as HBOS does; for every pair $(j,k)$ with $j<k$ it builds a two-dimensional histogram, converts low joint density into high scores via negative log density, and accumulates normalized pairwise scores. In the reported experiments EHBOS beats HBOS in ROC AUC on glass (0.8515 vs. 0.7003), cardio (0.9037 vs. 0.8511), satellite (0.7886 vs. 0.7516), satimage-2, shuttle, and vowels, while losing on lympho, mnist, and optdigits. The paper reads the gains as evidence that pairwise dependence carries anomaly structure that univariate histograms cannot see, and it reports empirical runtimes consistent with $O(n d^2)$ complexity.

Load-bearing premise

The method assumes every two-dimensional histogram bin it scores has at least one data point; the paper never says what happens to the score when a bin is empty, and an empty bin would make the log-density term infinite and dominate the average.

Editorial extensions

If this is right

On datasets whose anomalies are defined by feature interactions, EHBOS assigns higher outlier scores than HBOS, as shown on the two synthetic examples and on glass, cardio, and satellite.
EHBOS's ROC AUC gains come at a computational cost of $O(n d^2)$ rather than HBOS's $O(n d)$, so the method is most practical when the number of features is moderate.
The method stays close to HBOS on datasets where anomalies are mostly univariate, with small differences on pima, pendigits, and wbc, and it degrades on lympho, mnist, and optdigits.
The 1D/2D mixture can be treated as a tunable hyperparameter, so a user can weight the pairwise component more heavily when dependencies are known to matter.
Because EHBOS is built from counting and binning, it remains interpretable and requires no training, fitting the same niche as HBOS.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A direct extension would replace the fixed equal-weight average with learned, rank-based, or weighted fusion of the 1D and 2D scores; the paper does not test whether the equal-weight average is optimal.
The same 1D-plus-2D averaging idea transfers to other density estimators, such as kernel density estimates, which would soften the empty-bin problem at higher computational cost.
On high-dimensional datasets like mnist, optdigits, and musk, most pairwise bins are likely empty; an explicit empty-bin policy could change rankings substantially, meaning the reported underperformance may be a binning artifact rather than a property of the averaging.
Selecting feature pairs before building 2D histograms could recover some of the $O(n d^2)$ cost and focus scoring on genuinely dependent pairs; the paper lists adaptive feature selection as a future direction.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The core idea is simple: take HBOS's univariate scores, add pairwise 2D histogram scores, normalize both, and average. That is a natural extension, and the paper is honest that it is an extension rather than a new paradigm. The two synthetic examples clearly illustrate why HBOS misses contextual outliers, and the 2D score does fix those cases. The empirical section compares against plain HBOS on 17 datasets with adaptive binning, and the paper cites the closest prior work (Sathe & Aggarwal, Aryal et al.) rather than ignoring it. So the author knows the literature and the positioning is fair.

The soft spots are real but concentrated. The load-bearing issue is that the 2D score in Section 3 is defined as -log h_jk, with no rule for empty bins. If a sample lands in an empty cell, its score is +infinity, which makes the averaged final score infinite and ROC AUC undefined. On high-dimensional datasets like mnist (d=100), optdigits (d=64), and musk (d=166), most pairwise bins will be empty under any fixed binning, so the finite numbers in Table 2 require an undocumented convention. The fact that EHBOS does much worse than HBOS on exactly those high-dimensional datasets suggests the empty-bin handling is not a minor detail but is affecting the results. This needs to be specified and the experiments re-run with a stated pseudocount, floor, or skip rule.

The secondary issues are thinner evidence: no error bars, no significance tests, no code, and no comparison to the subspace-histogram or PCA-based HBOS variants. The complexity notation is also sloppy: it says O(n·d^3) but all feature pairs are O(n·d^2); the text calls it quadratic, which is right, so d^3 is a typo. The arbitrary 0.5 weighting is a design choice, not a flaw.

Who is this for? Practitioners who want a quick, interpretable way to add pairwise interactions to HBOS. The method is well motivated and the idea is sound, but the current paper does not provide enough detail to reproduce the claimed improvements. I would not cite it as a reliable empirical result until the empty-bin issue is resolved, but I would reference it as a related extension.

My recommendation: this deserves a serious referee rather than a desk reject, but only with major revisions. The author should specify the empty-bin handling, provide code or at least a precise algorithmic description, and add confidence intervals or significance tests on the key comparisons. Without those, the central empirical claim is not supported.

Referee Report

4 major / 4 minor

Summary. The paper introduces EHBOS, an extension of the histogram-based outlier score HBOS that adds pairwise two-dimensional histograms to the original independent-feature histograms. The final EHBOS score is defined as the average of a normalized one-dimensional HBOS score and a normalized two-dimensional score over all feature pairs. The authors motivate the method with two synthetic examples where HBOS fails to detect contextual and dependency-driven outliers, present an algorithm and a claimed O(n*d^3) time complexity, and report ROC AUC results on 17 benchmark datasets, mostly in comparison with HBOS alone. The central claim is that EHBOS outperforms HBOS on datasets where feature interactions matter, such as glass, cardio, and satellite, while remaining competitive elsewhere.

Significance. If the empirical claims hold, EHBOS would be a simple, interpretable, and computationally modest extension of a widely used baseline, and the two synthetic demonstrations are pedagogically useful. The method is defined before evaluation and does not fit parameters to the anomaly labels, so there is no circularity in the main comparison. The paper is also honest about cases where EHBOS underperforms, notably on lympho, mnist, and optdigits. However, the central claim is currently not well supported: the 2D score has an undefined behavior for empty histogram bins, the normalization of scores is unspecified, the reported AUC values lack uncertainty quantification, and no comparison is made with the HBOS extensions cited in the introduction. These issues are load-bearing for the paper's main conclusion and need to be resolved before the reported improvements can be accepted.

major comments (4)

[Section 3, 2D score equation] The definition s2(i) = sum_{j<k} -log h_jk(x_ij, x_ik) is undefined when a 2D histogram bin is empty, because -log(0) is +infinity and such a score would dominate the final average. The manuscript states no pseudocount, floor value, or skip-empty rule, yet Table 2 reports finite ROC AUC values. For high-dimensional datasets in Table 1 (mnist with d=100, optdigits with d=64, musk with d=166), many feature pairs have empty cells under any reasonable binning, so the reported improvements may be artifacts of an implicit convention rather than of the EHBOS construction. Please specify the empty-bin handling and report the sensitivity of Table 2 to that choice.
[Section 3, Algorithm steps 02 and 07] The algorithm says to normalize the 1D scores and to accumulate normalized 2D scores, but no normalization procedure is defined. If min-max normalization is used, an infinite 2D score makes the normalized score undefined; if rank or z-score normalization is used, the relative contribution of the 2D component changes. Since the final score is the average of these normalized components, the exact form of normalization can determine whether EHBOS improves over HBOS on a given dataset. Please state the normalization formulas and justify them.
[Section 4.2, Table 2] Table 2 reports a single ROC AUC value per method and dataset, with no repeated runs, confidence intervals, or significance tests. Several reported differences are very small (pima 0.6956 vs 0.6954, pendigits 0.9283 vs 0.9238, wbc 0.9583 vs 0.9533) and cannot support claims of improvement or robustness. Moreover, the paper cites three existing HBOS extensions (multi-step histogram scores, subspace histograms, and PCA-based histograms) but does not compare against any of them, so the incremental contribution over the closest baselines is not established. Please add uncertainty estimates and comparisons with at least the most directly related HBOS variants.
[Section 4.3 and Section 3, complexity claim] The paper claims that EHBOS has time complexity O(n*d^3), but the algorithm computes one 2D histogram for each of the d(d-1)/2 feature pairs, which gives O(n*d^2) after the per-pair binning. The text in Section 4.3 also says 'scaling quadratically in O(n*d^3)', which is internally inconsistent. The complexity claim should be corrected to O(n*d^2), and the empirical scaling plot in Figure 6 should be redrawn with the correct theoretical cost metric.

minor comments (4)

[Section 3, formulas] Several equations use corrupted mathematical notation (e.g., X∈R!×#, h$+x%,$-, s%(3-), O(n⋅d3)), making it difficult for a reader to parse the exact definitions. Please use standard typography for all formulas.
[Section 4.1, Figures 3 and 4] Figures 3 and 4 are referenced as showing comparisons for both example datasets, but the text only describes one figure at a time and refers to 'the second example dataset' without explicitly distinguishing the two figures. Please make the figure references and captions clearer.
[Section 4.2, Table 2] For the lympho dataset, EHBOS drops from a perfect HBOS AUC of 1.0000 to 0.8556; this is a substantial degradation, not a negligible one, and it deserves explicit discussion rather than the blanket statement that underperformance is 'slight'.
[Section 4.3] The text says the runtime evaluation uses a fixed bin-width setting, whereas the earlier experiments use the Birgé-Rozenholc adaptive binning. Please clarify whether the runtime experiments use a different binning protocol and whether this affects the complexity comparison.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: EHBOS is an unsupervised extension of HBOS whose final score is defined before any benchmark evaluation, and its reported improvements are empirically contingent rather than forced by construction.

full rationale

The paper's derivation chain is self-contained and non-circular. EHBOS is defined in Section 3 by combining the normalized 1D HBOS score with normalized 2D histogram scores over all feature pairs, and the final score is simply their average. No parameter is fitted to anomaly labels, and no self-citation is used to justify the method's validity. The empirical claim that EHBOS improves ROC AUC on datasets such as glass, cardio, and satellite is a posteriori benchmark evidence, not a consequence of the definition: EHBOS actually underperforms HBOS on lympho, mnist, optdigits, pendigits, and wbc, which shows the improvement is not structurally guaranteed. The reuse of HBOS as both the 1D component and the baseline is an overlap in method lineage, but it does not make the comparison circular because the 2D pairwise scores add information not present in the 1D baseline and the aggregation weights are fixed rather than tuned to the target variable. The missing empty-bin handling in the 2D histogram log-density is a real correctness risk that could affect the numerical results, but it is a robustness issue, not a circularity issue.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the histogram density model, the pairwise-only interaction assumption, and the benchmark labels. The only hand-chosen number is the equal mixing weight; no parameter is fitted to anomaly labels.

free parameters (1)

mixing weight w for 1D and 2D scores = 0.5 (equal average)
The final EHBOS score is defined as the arithmetic mean of the 1D and 2D normalized scores. The paper notes the choice between using the 2D score alone or the averaged final score can be treated as a tunable hyperparameter, but experiments use only equal weights.

assumptions (4)

domain assumption Histogram density estimates with adaptively chosen bin counts provide a valid model of the underlying data distribution for anomaly scoring.
The method's scores are log inverse bin heights; if histograms are poor density estimators, scores are misleading. Invoked in Section 3 and Section 4.2.
domain assumption Pairwise feature dependencies are sufficient to capture the anomalies of interest; higher-order interactions are ignored.
EHBOS only builds 2D histograms, so anomalies defined by triple or higher interactions are not modeled. Stated implicitly in Section 3.
domain assumption The benchmark datasets provide ground-truth labels that correctly identify anomalies, and ROC AUC is an appropriate evaluation metric.
Used in Section 4.2 to compute ROC AUC; no discussion of label noise or metric choice.
standard math Standard arithmetic and logarithmic properties used in the score formulas.
The derivation of score from density uses log of inverse. No exotic math.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Extended Histogram-based Outlier Score (EHBOS)." pith.science (2026). https://pith.science/paper/36TR5LQ7

@misc{pith2026250205719,
  author       = {Pith},
  title        = {Pith review of: Extended Histogram-based Outlier Score (EHBOS)},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/36TR5LQ7}},
  note         = {Machine review of arXiv:2502.05719}
}

read the original abstract

Histogram-Based Outlier Score (HBOS) is a widely used outlier or anomaly detection method known for its computational efficiency and simplicity. However, its assumption of feature independence limits its ability to detect anomalies in datasets where interactions between features are critical. In this paper, we propose the Extended Histogram-Based Outlier Score (EHBOS), which enhances HBOS by incorporating two-dimensional histograms to capture dependencies between feature pairs. This extension allows EHBOS to identify contextual and dependency-driven anomalies that HBOS fails to detect. We evaluate EHBOS on 17 benchmark datasets, demonstrating its effectiveness and robustness across diverse anomaly detection scenarios. EHBOS outperforms HBOS on several datasets, particularly those where feature interactions are critical in defining the anomaly structure, achieving notable improvements in ROC AUC. These results highlight that EHBOS can be a valuable extension to HBOS, with the ability to model complex feature dependencies. EHBOS offers a powerful new tool for anomaly detection, particularly in datasets where contextual or relational anomalies play a significant role.

Figures

Figures reproduced from arXiv: 2502.05719 by the authors.

**Figure 1.** Examples of two datasets illustrating the limitations of HBOS. (Left) A clustered dataset with two localized outliers that are anomalous in the joint feature space but not in individual marginal distributions. (Right) A regression-based dataset where normal data follows a strong linear dependency, and two outliers deviate from this relationship while remaining within typical marginal ranges. The second example consi… view at source ↗

**Figure 2.** Histogram-based outlier scores assigned by HBOS for the datasets in [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** Comparison between HBOS and EHBOS (2D) outlier scores for the first example dataset. In the local outliers dataset, EHBOS recognizes that the outliers deviate significantly from the joint [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: Comparison between HBOS and EHBOS (2D) outlier scores for the second example dataset. These results underscore the importance of modeling feature interactions for effective anomaly detection in datasets where anomalies are defined by deviations from joint feature distr…

**Figure 5.** Figure 5: Comparison of HBOS and EHBOS outlier scores on the Satellite dataset, reduced to 2D using PCA. The third subplot shows the ground truth, highlighting how EHBOS scores better align with true anomalies. As an example, we provide a comparative visualization of HBOS and EH…

**Figure 6.** Figure 6: Empirical wall‐clock runtimes of HBOS (top) and EHBOS (bottom) on all 17 benchmark datasets. 5 Conclusion In this paper, we have introduced the Extended Histogram-Based Outlier Score (EHBOS), a novel extension of the Histogram-Based Outlier Score (HBOS) that incorporat…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

3 extracted references · 3 canonical work pages

[1]

However, its assumption of feature independence limits its ability to detect anomalies in datasets where interactions between features are critical

Journal of Statistical Theory and Practice (2025) Version of Record: https://doi.org/10.1007/s42519-025-00469-9 Extended Histogram-based Outlier Score (EHBOS) Tanvir Islam Okta Bellevue, WA, USA tanvir.islam@okta.com Abstract Histogram-Based Outlier Score (HBOS) is a widely used outlier or anomaly detection method known for its computational efficiency an...

work page doi:10.1007/s42519-025-00469-9 2025
[3]

Improved histogram-based anomaly detector with the extended principal component features

Due to its independent feature analysis, HBOS fails to differentiate the outliers from normal points, resulting in low anomaly scores. This demonstrates HBOS’s inability to detect anomalies arising from feature interactions. In both examples, HBOS demonstrates its inability to detect anomalies that arise from deviations in feature relationships rather tha...

work page Pith review arXiv 2023
[2001]

and Isolation Forest (Liu et al., 2008), learn decision boundaries or partitions to separate anomalies. Neural network methods, notably 2 autoencoders (Sakurada & Yairi, 2014), excel in high-dimensional spaces by reconstructing inputs and flagging outliers via reconstruction error; they capture complex interactions but require significant computational re...

work page 2023

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.

[1] [1]

However, its assumption of feature independence limits its ability to detect anomalies in datasets where interactions between features are critical

Journal of Statistical Theory and Practice (2025) Version of Record: https://doi.org/10.1007/s42519-025-00469-9 Extended Histogram-based Outlier Score (EHBOS) Tanvir Islam Okta Bellevue, WA, USA tanvir.islam@okta.com Abstract Histogram-Based Outlier Score (HBOS) is a widely used outlier or anomaly detection method known for its computational efficiency an...

work page doi:10.1007/s42519-025-00469-9 2025

[2] [3]

Improved histogram-based anomaly detector with the extended principal component features

Due to its independent feature analysis, HBOS fails to differentiate the outliers from normal points, resulting in low anomaly scores. This demonstrates HBOS’s inability to detect anomalies arising from feature interactions. In both examples, HBOS demonstrates its inability to detect anomalies that arise from deviations in feature relationships rather tha...

work page Pith review arXiv 2023

[3] [2001]

and Isolation Forest (Liu et al., 2008), learn decision boundaries or partitions to separate anomalies. Neural network methods, notably 2 autoencoders (Sakurada & Yairi, 2014), excel in high-dimensional spaces by reconstructing inputs and flagging outliers via reconstruction error; they capture complex interactions but require significant computational re...

work page 2023