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.
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 [
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 [
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 x1, x2,..., xm d . The aim is to find a prediction set E ( x1, x2 ,..., xm ) d resulting into probability p ( xm+1 E ) 1− , where 0 1 is a chosen significance level, so that p ( xm+1 E ) is the confidence level of the predictive set. 2. Hill`s Assumption A(m) As x1, x2 ,..., xm 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 x(1) x(2) ... x(m) , where x(i) is i-th order statistics. The resulting order statistics x(1) , x(2) ,..., x(m) are dependent. The distribution Fk ( x) of the k-th order statistics x(k) can be calculated as m Fk (u) = Cmi F (u)i 1− F (u)m−1 , where F (u) = p ( x u) .
i=k distribution F then
A(m) [19] states that if x(i) is chosen from the population according to p ( xm+1 ( x(i) , x( j) )) = j − i , j i. (1)
m +1
A(n) was proven in papers of Yu.I. Petunin [
− where F (u) and F (u) denote the distribution functions of and , respectively. The probability density of i-th order statistics is:
m m fk (u) = Cmi F (u)i 1− F (u)m−i = Gi (u).
i=k i=k m Hence, Fk(u) = Gi' (u) ,
i=k Gk (u) = Cmk k (F (u))k−1 (1− F (u))m−k f (u) −(F (u))k (m − k )(1− F (u ))m−k−1 f (u ) (3) (4)
−Cmk (m − k ) + Cmk+1 (k +1) = − m!(m − k ) + m!(k +1) (m − k )!k ! (m − k −1)!(k +1)!
( F (u))m (1− F (u))0 (m − m) f (u ) = 0 .
= −
m! + m! (m − k −1)!k! (m − k −1)!k! = 0.
fk (u) = mCmk−−11 F (u)k−1 1− F (u)m−k f (u) .
Let us find p( x x(i) ) and p ( x x( j) ) . Using the above equations, we have 1 p ( x x(i) ) = F (u ) dFi (u ) = mCmi−−11 F (u )i 1− F (u )m−i dF (u ) = mCmi−−11 vi (1− v)m−1 dv.
− − 0
1 x p−1 (1− x)q−1 dx = ( p) (q) 0 ( p + q −1) We can apply this equation as ( p −1)!(q −1)! = ( p + q −1)! . 1 xi+1−1 (1− x)m−i+1−1 dx = B(i +1, m − i +1) = (i +1)(m − i +1) = (i +1)(m − i +1) = i!(m − i)! 0 (i +1+ m +1− i) (m + 2) (m +1)! p ( xm+1 x( j) ) = mCmi−−11 j(!(mm+−1)j!)! = (mm−(mj)!−( 1j)−!(1)j!−m1()m!j+!(1m)(−mj−)!1)! = m +j1.
Previous equation was obtained by multiplying numerator and denominator by (j 1). So, we get p ( xm+1 ( x(i) , x( j) )) = p ( xm+1 xj ) − p ( xm+1 xi ) = m +j1 − mi+1 = mj −+i1.
So, in case a random variable x is independent from x1, x2 ,..., xm and it is chosen by sampling from the same population based on distribution F (u) , then p ( x ( x(1) , x(m) )) = m −1 .
m +1 Remark 1. The confidence level of the tolerance interval ( x(1) , x(m) ) is m −1 , thus for m 39 the m +1 confidence level of this interval is less than 0.05.
The algorithm for construction of the ellipsoid containing the set as m random points with the
probability m −1 was proposed by Yu. I. Petunin. Statistical and geometrical properties of the
m +1
Petunin ellipsoids were investigated in [
Here we applied -dimensional case. First, we find two points farthest from each other xk and xl of the set Mn = x1,..., xm . 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).
By dividing the shorter side length by the longer side length, we can obtain the shrinking coefficient. Translate, rotate and shrink mentioned above rectangle to construct a square covering the given points.
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. Perform inverse transformations of this circle. The result is the Petunin ellipse (Figure 5).
In high-dimensional case, we can construct a minimum volume axis-aligned orthogonal parallelepiped that contains images x1,..., xm of initial points. Perform shrinking transformation from the orthogonal parallelepiped to a hypercube. Find its center and distances from it to x1,..., xm . Next find the maximum distance. After that, construct a hypersphere with the center and radius that is equal to the maximum distance from the center to the images of the points. Perform inverse transformations (translation, rotation and stretching) and obtain the Petunin ellipsoid Em . Hill s assumption A(m) is true, so P ( xm+1 E ) = m −1.
m +1
Since at the last stage of construction of the Petunin ellipsoid we obtain the concentric spheres with one unique point at the surface, using the Petunin ellipsoids we can arrange the points by their statistical depth. The median point of the set (the most probable point) is the point nearest to the center of the Petunin ellipsoid and the outlier is the point at the boundary of the Petunin ellipsoid.
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.
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 to 1.
As we can see, the largest ellipse contains almost all points and areas slowly grow until last 50 points defining largest ellipses.
Exponential with parameters -17, -50 as multipliers for logarithm from random value from 0 to 1. Here the largest ellipse contains almost all points, but ellipse areas grow much faster.
Gamma distribution was used here based on pseudorandom numbers with parameters 50 and 90 for horizontal and vertical values respectively.
Expected probability 0.997760000000000
In this test ellipse contains almost all points and ellipse areas increase very fast after ellipse based on 800 points.
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.
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 35 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.