Ellipsoidal distribution-free set DmitriyKlyushin dmytroklyushin@knu.ua Taras Shevchenko National University of Kyiv
60 Volodymyrska Street 01033 Kyiv Ukraine
AndriiTymoshenko andriitymoshenko@knu.ua Taras Shevchenko National University of Kyiv
60 Volodymyrska Street 01033 Kyiv Ukraine
Ellipsoidal distribution-free set 1613-0073 C9C859DF0DD3410BF3B757270A51281A GROBID - A machine learning software for extracting information from scholarly documents data mining prediction set Petunin ellipsoid outlier detection 1

This paper introduces a distribution-free approach based on the Hill's assumption and the Petunin ellipsoids. Several distributions are used to generate points and build ellipsoids, which are then used to check if test points with same distribution are created inside largest ellipsoid. As a result, a new prediction set is constructed in the form of Petunin ellipsoid, while confidence level refers to the number of points. The method described here works effectively for chosen distributions. Moreover, statistical analysis of the quantity of points inside is performed. This method is a useful tool for solving many urgent problems of machine learning, e.g. generalization of training samples, effective cross-validation etc.
Introduction

Construction of prediction sets is a popular problem in machine learning, often placed together with neural networks. In recent years many international scientists have discussed prediction sets. For example, Adam Khakhar, Stephen Mell and Osbert Bastani [1] used a trained code generation model in algorithm that leverages an abstract syntax tree based on programming language to create a set of programs with high confidence about the correct program. Another example by Soroush H. Zargarbashi, Mohammad Sadegh Akhondzadeh and Aleksandar Bojchevski [2] derive provably robust sets by defining bounds for the worst-case change related to conformity scores.

Another important idea is to find distribution-free classification and sets. Here we can mention a work by Chirag Gupta, Aleksandr Podkopaev and Aaditya Ramdas [3] where they study calibration and prediction sets combined with confidence intervals. Their research is dedicated to binary classification in case of distribution-free sets. Based on demonstrated theorems, confidence intervals for binned probabilities allow to perform distribution free calibration.

In [4] Hongxiang Qiu, Edgar Dobriban and Eric Tchetgen Tchetgen offer a novel flexible distribution-free method named PredSet-1Step for constructing prediction sets where asymptotic coverage is guaranteed under unknown covariate shift.

As for [5] A.N. Angelopoulos, S. Bates, J. Malik and M.I. Jordan present an algorithm which changes a chosen classifier to determine a predictive set, where the true label is inside with probability set by user. This simple and fast algorithm reminds of Platt scaling but results into a formal finite-sample coverage for every model and dataset.

Approach described in [6] by analysis of a holdout set allows to choose the size of the prediction sets and leads to explicit finite-sample guarantees. As a result, simple, distribution-free and rigorous error control is obtained for many tasks, demonstrated on five large-scale machine learning problems. Some more works related to predictions offer various approaches: prediction based on language models [7], neural networks compared to calibrated predictions [8], distribution-free uncertainty quantification and conformal prediction [9], conformal risk control [10], conformal predictors applied for medical imaging [11], confident prediction in case distributions shift [12], conformal prediction robust to label noise [13], conformal prediction via probabilistic circuits [14].

Not only predictions attract modern scientists. Some related topics are also worth being mentioned: uncertainty quantification is performed over graph using conformalized graph neural networks [15], adversarial robustness applied to randomly smoothed classifiers [16], randomized smoothing for graphs and images [17], adversarially trained smoothed classifiers [18].

The purpose of our paper is to describe a method to construct ellipsoidal prediction set for a set of the randomly generated points, based on chosen distribution. The main tools for our forecast are predictive sets represented by ellipses, constructed using generated points. Test points are generated with same distribution, the more ellipses contain a point the higher probability of belonging to same class can be expected. Consider the problem of creating conformal prediction based on points 12 , ,...,

d m x x

x  . The aim is to find a prediction set ( ) 12 , ,...,

d m E x x

x  resulting into probability ( )

1 1 m p x E +   −  ,

where 01    is a chosen significance level, so that ( )

1 m p x E + 

is the confidence level of the predictive set.

Hill`s Assumption () m

A As 12 , ,..., m x x x we denote a sample drawn from a population generated according to absolutely continuous distribution F. Next, we arrange it in the increasing order and create the variance series

(1)

... x can be calculated as

( ) ( ) ( ) 1 1 m im i km ik F u C F u F u − =         =− 

, where ( ) ( )

F u p x u = . () m

A [19] states that if () i x is chosen from the population according to distribution F then ( ) ( )

1 ( ) ( ) , , . 1 m i j ji p x x x j i m + −  =  +() n

A was proven in papers of Yu.I. Petunin [20] and by several other scientists. Let us recall the proof for random variables  and  . If they are independent, then

( ) ( ) ( ) p F u dF u    − =  ,

where ( )

Fu  and

( )

Fu 

denote the distribution functions of  and  , respectively. The probability density of i-th order statistics is:

( ) ( ) ( ) ( ). 1 mm i m i i k m i i k i k f u C F u F u G u − == ==         − 

Hence, ( ) ( )

' m ki ik F u G u = =   , (11 11 k m k k m k k km G u C k F u F u f u F u m k F u f u − − − −  =−   − − −

) ( )

11 1 1 1 1 2 1 . 1 1 1 1 1 k m k k km k m k k m k k m G u C F u F u C k F u F u f u F u F u m k f u + − − + + − − + − − +    ==    =   − + − − − − −

The second term is compensated by the first term:

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 ! ! 1 !! 1 0. ! ! 1 ! 1 ! 1 ! ! 1 ! ! kk mm m m k m k mm C m k C k m k k m k k m k k m k k + −+ −+ − + = − + = − + = − − − + − − − −

The last term of the previous sum is equal to zero

( )

) ( )

0 10 m F u F u m m f u − − = .

Thus,

( ) ( ) ( ) ( ) 1 1 1 1 k m k k km f u mC F u F u f u −− − −         =− .

Let us find ( )

() i p x x 

and ( )

() j p x x 

. Using the above equations, we have

( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 1 ( ) 1 1 11 0 1 1 . i m i m i i i i i m m p x x F u dF u mC F u F u dF u mC v v dv  − − −− −− − − ==          = − −    It is proven that, ( ) ( ) ( ) ( ) ( ) ( ) (

)

1 1 1 0 1 ! 1 ! 1 1 1 ! q p dx p q p q xx p q p q − − =   − − −=  + − + −  .

We can apply this equation as

( )

)

1 11 11 0 1 1 1 1 ! ! 1 1, 1 1 1 2 1 ! mi i i m i i m i i m i x x dx B i m i i m i m m − + − +−  +  − +  +  − + − − = + − + = = =  + + + −  + +  ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )( ) 1 1 ( ) 1 . ! ! 1 ! 1 ! ! ! 1 ! ! 1 ! 1 1 ! 1 i m j( ) ( ) ( ) ( ) ( ) ( ) 1 1 1 , . 1 1 1 m m j m i ij j j i i p x x x p x x p x x m m m + + +  =  − −  = − = + + +

So, in case a random variable x is independent from 12 , ,..., m

x x x and it is chosen by sampling from the same population based on distribution ( )

Fu, then
Petunin Ellipsoids

The algorithm for construction of the ellipsoid containing the set as m random points with the . Connect them with a line (next mentioned as diameter), then project all the points to the hyperplane orthogonal to this line. To simplify this, we can rotate all objects together around line center to make it horizontal. But then we will need to rotate it back in the end (Figure 1). Next, we need to find the farthest points from the line. Construct lines parallel to the diameter through these points. Create lines that are orthogonal to diameter and pass through the farthest from each other points. As a result, we obtain a rectangle, which covers the given set of points and lies on a two-dimensional plane (Figure 2). Find its center and all distances from the center of the square to every image of point. Then, we need to find maximal distance and create a circle with center same as square center and radius that is equal to maximum distance from the center to the images of points.

Numerical results

In this section testing results are described. First, we generate a chosen distribution-based set of 1000 points and build ellipses through each point. Then we generate 1000 more points with the same distribution and check the number of points inside the largest ellipse. Statistical characteristics of these results are shown below for three different distributions.

Normal distribution

The first test was performed on normal distribution testing, 3 to 1. We generate 12 random numbers from 0 to 1, calculate their sum and subtract 6. Then we modify values by multiplying the result and adding value so that horizontal and vertical coordinate values can be generated in proportion 3 More tests were performed for these distributions with other parameters and results were alike. Ellipse areas increased smoothly at first, but for the last 100-200 most distant points faster increase was reported. As for accuracy, we expected values to be approximately 0.998 and received alike results.

distribution with rectangular area covered.

Conclusion

Constructing Petunin ellipsoid is a useful approach for arranging data and detecting anomalies using statistical depth. According to obtained results, the algorithm leads to effective prediction

Fxwhere () i x is i-th order statistics. The resulting order statistics (1) of the k-th order statistics () k
Previous equation was obtained by multiplying numerator and denominator by (j 1). So, we get
1 .The confidence level of the tolerance interval ( ) this interval is less than 0.05.
Yu. I. Petunin. Statistical and geometrical properties of the Petunin ellipsoids were investigated in[21].Here we applied -dimensional case. First, we find two points farthest from each other k x and l x of the set   1 ,...,
Figure 1 :Figure 1: The furthest from each other points
Figure 2 :Figure 2: Rectangle covering the images of the points
Figure 3 :Figure 3: Square covering the images of the points
Figure 4 :Figure 4: The circle covering the images of the points
Figure 5 :Figure 5: Petunin ellipse covering the initial points
Figure 6 :Figure 6: Average ellipse areas Normal distribution, 100 tests
Figure 7 :Figure 7: Average ellipse areas Exponential distribution, 100 tests
4. 3 .Gamma distributionGamma distribution was used here based on pseudorandom numbers with parameters 50 and 90 for horizontal and vertical values respectively.
Figure 8 :Figure 8: Average ellipse areas Gamma distribution, 100 tests
to 1.Expected probability 0.99762Mean 0.99762Mean Deviation 0.001873Mode 0.996477Median 0.998Standard Deviation 0.0022867Variance 0.0000052279Kurtosis 3.24629Skewness -0.892779Range 0.01Maximum 1Minimum 0.989Geometric Mean 0.9976174Harmonic Mean 0.9976148

sets based on Petunin ellipsoid. The confidence level reached is theoretically precise for tested distributions. It allows us to compute statistical depth based on every point and detect outliers of the set. Experimental results approved theoretical properties of the Petunin ellipses.

Declaration on Generative AI

The authors have not employed any Generative AI tools.

Exponential distribution Exponential with parameters -17, -50 as multipliers for logarithm from random value from 0 to 1 0.998158 Expected probability 0.998158 Mean <idno>.00138457 Mode 0.99943 Median 0.999</idno> </analytic> <monogr> <title level="j">Mean Deviation 0 <idno>0.00000351465 Kurtosis 5.98476568 Skewness -1.5228786 Range 0.01 Maximum 1 Minimum 0.989999</idno> </analytic> <monogr> <title level="j">Standard Deviation 0 18747 Variance </analytic> <monogr> <title level="j">Geometric Mean 0 998 </analytic> <monogr> <title level="j">Harmonic Mean 0 998 PAC Prediction Sets for Large Language Models of Code AKhakhar SMell OBastani 10.48550/arXiv.2302.08703 2023 Robust Yet Efficient Conformal Prediction Sets SHZargarbashi MSAkhondzadeh ABojchevski 10.48550/arXiv.2407.09165 2024 Distribution-free binary classification: prediction sets, confidence intervals and calibration CGupta APodkopaev ARamdas 2020 Prediction sets adaptive to unknown covariate shift HQiu EDobriban ETchetgen 10.1093/jrsssb/qkad069 Journal of the Royal Statistical Society Series B: Statistical Methodology 85 5 1705 2023 Uncertainty sets for image classifiers using conformal prediction AAngelopoulos SBates JMalik MIJordan 2020 Distribution-free, risk-controlling prediction sets SBates AAngelopoulos LLei JMalik MIJordan 2021 Autoregressive structured prediction with language models TLiu YJiang NMonath RCotterell MSachan 2022 Pac confidence sets for deep neural networks via calibrated prediction SPark OBastani NMatni ILee 2020 A gentle introduction to conformal prediction and distributionfree uncertainty quantification ANAngelopoulos SBates 2021 ANAngelopoulos SBates AFisch LLei TSchuster ArXiv, abs/2208.02814 Conformal risk control 2022 Fair conformal predictors for applications in medical imaging CLu ALemay KChang KHobel JKalpathy-Cramer Proceedings of the AAAI Conference on Artificial Intelligence the AAAI Conference on Artificial Intelligence 2022 36 Robust validation: Confident predictions even when distributions shift MCauchois SGupta AAliand JCDuchi arXiv:2008.04267 2020 arXiv preprint Conformal prediction is robust to label noise B.-SEinbinder SBates ANAngelopoulos AGendler YRomano ArXiv, abs/2209.14295 2022 COLEP: Certifiably robust learning-reasoning conformal prediction via probabilistic circuits MKang NMGurel LLi BLi The Twelfth International Conference on Learning Representations 2024 Uncertainty quantification over graph with conformalized graph neural networks KHuang YJin ECandes JLeskovec 2023 Tight certificates of adversarial robustness for randomly smoothed classifiers G.-HLee YYuan SChang TJaakkola Advances in Neural Information Processing Systems 32 2019 Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more ABojchevski JGasteiger SGunnemann International Conference on Machine Learning PMLR 2020 Provably robust deep learning via adversarially trained smoothed classifiers HLi JSalman IRazenshteyn PZhang HZhang SBubeck GYang Advances in Neural Information Processing Systems 32 2019 population Journal of the American Statistical Association 63 1968 Characterization of the uniform distribution using order statistics IMadreimov YuIPetunin Theory of Probability and Mathematiical Statistics 27 1983 Minimal Ellipsoids and Maximal Simplexes in 3D Euclidean Space SILyashko BVRublev 10.1023/B:CASA.0000020224.83374.d7 Cybernetics and Systems Analysis 39 2003