Source-linked AI summary
The random Tukey depth
J. A. Cuesta-Albertos, A. Nieto-Reyes
TL;DR
Tukey depth is computationally demanding because it considers all one-dimensional projections. The paper approximates it with a finite number of random projections, finding similar results to more involved depths while requiring little computation and extending to functional settings.
Problem
Tukey depth requires considering all one-dimensional projections, making its computation demanding even in low-dimensional spaces.
Method
The paper replaces Tukey depth's infimum over all projections with a minimum over finitely many randomly selected projections and extends the construction to Hilbert-valued data.
Results
The random Tukey depth obtains results similar to more involved depths, with 36 projections sufficient for samples of at most 1,000 under the reported comparisons.
Takeaways & Limitations
Under the considered conditions, the random Tukey depth is an alternative worth considering because it requires small computational time while producing similar results.
Takeaways & Limitations
In functional data, the paper reports no known gold standard for comparing depths.
Abstract
from arXiv · showhide
The computation of the Tukey depth, also called halfspace depth, is very demanding, even in low dimensional spaces, because it requires the consideration of all possible one-dimensional projections. In this paper we propose a random depth which approximates the Tukey depth. It only takes into account a finite number of one-dimensional projections which are chosen at random. Thus, this random depth requires a very small computation time even in high dimensional spaces. Moreover, it is easily extended to cover the functional framework. We present some simulations indicating how many projections should be considered depending on the sample size and on the dimension of the sample space. We also compare this depth with some others proposed in the literature. It is noteworthy that the random depth, based on a very low number of projections, obtains results very similar to those obtained with other depths.
1 Introduction
The paper introduces a computationally simple random approximation to Tukey depth by replacing all projections with finitely many random ones, extending the approach to functional data. Simulations assess projection counts across sample sizes and dimensions, with favorable computation time and comparable depth-based results.
- Motivation: Tukey depth orders points using the minimum one-dimensional depth over all projections, but its computation becomes prohibitive as dimension increases.The paper notes that computation is reasonable for p = 2 but prohibitive even for p = 8.
- Method: The proposed random Tukey depth replaces the infimum over all projections with a minimum over finitely many randomly selected projections.The random vectors are independent and identically distributed according to an absolutely continuous distribution ν.
- Method: The method is random by construction, and sufficiently large projection counts are expected to make the randomness's effect negligible.The paper emphasizes that choosing k too large would undermine the definition's usefulness, motivating an empirical selection procedure.
- Selecting k: For elliptical distributions, the paper selects k by examining when resemblance between random Tukey depth and a monotone function of Mahalanobis depth stabilizes.Because the underlying distribution is unknown in practice, the procedure is adapted to random samples using empirical distributions.
- Results: 36 projections are the maximum required when the sample size is below 1,000 in the reported comparisons.The comparisons cover several sample sizes, dimensions, and elliptical distributions.
- Extensions and evaluation: The random depth applies wherever projections can be computed, including separable Hilbert spaces, and its computation time compares favorably with Mahalanobis depth.The paper compares the method with functional-depth results in a classification problem, while noting the absence of a functional gold standard.
2 How many random projections? Testing homogeneity
The paper selects the number of random projections by comparing random Tukey depth with Mahalanobis depth in elliptical settings, using empirical rank resemblance and simulation-based stability. The resulting guidance examines sample size, dimension, distribution, testing performance, and computation time.
- Choosing k: The study estimates k0 where the rank resemblance between DT,k and DM stabilizes, replacing P with the empirical distribution when only a random sample is available.For elliptical P, rk,P is strictly increasing; with empirical data, k0 is identified where rk,Pn begins to oscillate.
- Simulation design: 10,000 simulations varied distributions, dimensions p = 2, 4, 8, 25, 50, and sample sizes n = 25, 50, 100, 250, 500, 1, 000.The simulations used Gaussian, independent double exponential, and independent Cauchy marginals.
- Simulation results: Optimum k increases with sample size, while for Gaussian and exponential distributions it first increases with dimension and then decreases after a sample-size-dependent change point.The later decrease is linked to worsening dispersion-matrix estimation at fixed sample size, which adds noise to the comparison.
- Simulation results: The Gaussian covariance-determinant analysis links decreasing covariance-estimation quality to the point where the 95% percentile of k begins to decrease; the same behavior occurs for Double Exponential data.For Cauchy data, the estimated dispersion determinant does not fall below the stated threshold for the considered settings.
- Choosing k: 36 projections is the maximum required when the sample size is below 1,000, based on the 95% percentile of optimum k values.The selection uses the maximum 95% percentile across relevant distributions and sample sizes or dimensions.
- Testing and computation: The random Tukey depth produced no important rejection-rate differences from Tukey depth despite using far fewer directions, while its computation scales more favorably with dimension because k is bounded.Mahalanobis computation is dominated by covariance-matrix inversion, whereas random Tukey computation is dominated by obtaining projections and increasing k.
3 Functional random Tukey depth. Functional classification
The random Tukey depth extends naturally to functional data in a separable Hilbert space and is evaluated on growth-curve classification. The study replaces functional depths with the random Tukey depth while using L2[0, 1] rather than L1[0, 1].
- The random Tukey depth can be straightforwardly extended to functional spaces whose sample space is a separable Hilbert space.
- For a sample size n in an infinite-dimensional Hilbert space, k can be chosen as the maximum value recommended for that sample size in Table 2.1.
- The classification experiment uses growth curves from 39 boys and 54 girls, measured 31 times between ages 1 and 18, to classify sex.
- The functional analysis replaces prior functional depths with random Tukey depth, represents curves in L2[0, 1], and skips spline smoothing.
1.- Distance to the trimmed mean (M)
The distance-to-trimmed-mean method represents each group by its deepest retained observations and classifies a new curve using distances to those trimmed means.
- For each sample, the α-trimmed mean is the mean of the n × (1 − α) deepest points.
- The method uses separate trimming parameters α and β for the two groups’ trimmed means.
- A new curve Z is assigned to the first group when its distance to the first trimmed mean satisfies the method’s comparison rule; otherwise it enters the second group.
2.- Weighted average distance (AM)
The weighted-average-distance method compares a new curve with group members using depth-weighted distances rather than only comparing group trimmed means.
- Method M represents each group by its trimmed mean, whereas AM uses a weighted mean of distances from Z to the group members.
- The weights assigned to group members are their depths, so deeper observations contribute more directly to the group-distance calculation.
- The depths for the two groups are computed relative to the empirical distributions associated with their corresponding samples.
3.- Trimmed weighted average distance (TAM)
The TAM evaluation addresses unequal sample sizes, uses cross-validation on growth-curve classification, and compares random Tukey depth with previously studied functional depths. Despite using few projections, the random Tukey depth gives similar results, with AM the global winner.
- 3.- Trimmed weighted average distance (TAM): When sample sizes differ, TAM introduces l ≤ min(n, m) to reduce the influence of unequal group sizes.
- 3.- Trimmed weighted average distance (TAM): The method orders observations within each sample by depth, with X(1) and Y(1) denoting the deepest points.
- 3.- Trimmed weighted average distance (TAM): The reported experiment uses cross-validation, and random Tukey depth produces less variation in error rates across train-validation splits than reported in the earlier study.
- 3.- Trimmed weighted average distance (TAM): With a bigger sample size around 50, the experiment uses k = 10 random directions.
- 3.- Trimmed weighted average distance (TAM): The comparison table reports cross-validation mistake rates for the shown methods and depths; despite few projections, results are similar to, and AM is the global winner.
4 Discussion
The paper introduces a computationally efficient random approximation to Tukey depth that extends to Hilbert-valued data. Simulations and comparisons indicate that few random projections can produce results similar to more involved depths, including in infinite-dimensional settings.
- The random depth approximates Tukey depth while requiring little computational effort and extending to Hilbert-valued data.
- For sample sizes of at most 1,000, simulations suggest that 36 projections suffice across dimensions.
- With fixed dimension, the required number of projections increases with sample size because small samples introduce substantial randomness.
- With fixed sample size, the required number increases with dimension until distribution estimation becomes unreliable, after which it decreases.
- Comparisons show no important differences between the random Tukey depth and the other considered depths, including in the infinite-dimensional setting.