It is proposed a modification of the “piramidal” algorithm of small time series forecasting. “Piramidal” approach was developed in recent years, numerical results show advantages of this method in comparison with known approaches to extrapolation, based on the using of polynomials, including Newton's extrapolation. But this approach was tested only on deterministic time series. In this paper piramidal approach is applied to construct prognoses in the case where the time series contains a random component. It is studied the procedure for constructing the forecast value in accordance with the pyramidal method and improved the main criteria of this method . The main idea of the method improving is to find special patterns in the table of finite differences. The improved method is used for the number of patients with COVID-19 forecasting in Ukraine.
Today, forecasting is one of the most important tasks in the study of various processes. We would like always to look into the future. There is a number of methods of time-series forecasting. In many tasks, it becomes necessary to find patterns in large volumes of data and use them for forecasting [3]. Data mining as well as predictive modeling is used in many fields of scientific research. In the case of large amount of data it can be useful wellknown statistical approaches [17]-[21]. But what to do when very little is known? In the case of small time series many specific features arise. It is often impossible to determine what is the nature of the process from the point of view of determinism, what is the ratio of the deterministic and random components of the process. In the deterministic case according to the observation data can be built some mathematical model which is used to obtain the predicted value.
There is a number of methods for solving the extrapolation problem. For the extrapolation various interpolation functions can be used such as: generalized polynoms based on the systems of Chebyshev functions – polynomials [1], exponential, trigonometric functions[12]; flat radial basis functions [14]; splines – cubic, B-spline; Bezier curves [4]; special analytic functions and trend analysis [9]-[13],[15]. Neural networks also are widely used for extrapolation [8]. But how to choose the optimal model corresponding to a finite set of experimental data? It is obvious that an infinite set of curves passes through a finite set of points on the plane, and each of them can be a model of the process.
In the paper [1] it was proposed a new method of short time series extrapolation which was called “piramidal”. The aim of the authors is to develop a forecasting method that would not use specific classes of functions or any mathematical models. “Piramidal” method is based on the procedure of finding special conditions in the data obtained as special finite differences. The results of calculations for test functions showed the advantages of this method in comparison with approaches to extrapolate, based on the use of intarpolation polynomials. But piramidal approuch is comparatively new and requires deep in-depth research and data series validation.
In this paper, we have attempted to apply a piramidal approach to construct prognoses in the case when the time series contains a random component. We study the procedure of forecast value constructing in accordance with the pyramidal method and improve the main criteria of the optimal row choosing. The main idea of this method improving is based on finding patterns in the table of finite differences. Our modification makes possible use pyramidal approach in the case of data with stochastic component. 2. “Piramidal” algorithm without midpoints use another notatin follows:
“Piramidal” method of data extrapolation was proposed in work [1] . The main feature of this method is to construct a special divided differences and find their order, for which a better predicted value in a certain sense can be found. Then the value of the original function at the point located outside the interpolation interval is based on the predictive value for the divided differences using a special computational procedure. In works [1],[12] this method has been described taking into account additional interpolation at intermediate points. Since such interpolation did not play a significant role, here we consider an analogue of the corresponding algorithm without midpoints and
Let f1 , f 2 ,…, f n be any time-series, x1 , x2 ,… , xn are points of time respectively. It is needed to estimate the future observation f n+1 at the point x > xn . Consider the finite differences modified as 1 ∆ =
+2 − , = 1, − 1, computational procedure:
It is obvious that the finite differences (
Let’s consider such modification of the finite differences:
∆ −2 +1 = ∆ −2 −2( −2)−∆ −2
−2( −2)−1−∆ −2 − +2− − +1 −2( −2)−1−∆ −2
−2( −2)−2 − +1− − ( − +2− − )/2
In general case we have: where = 1, , = 1, − , = , = 1, − 2, , = 1, − 3, 2 ∆ =
3 ∆ = +2 − 1 2 ∆ +2 − ∆ +3 − +1 ∆ +2 − ∆ 1 2 +4 − +2
… −1 2 , = 2 + 1, −2 2 , = 2 .
∆ =
∆ −1 +2−∆ −1 ,
+ +1− + −1
(
( − −2)/2 Fig. 1), = 2 , ∆2 −3 =
2 It is obvious, that ∆
−3 approach is to find an additional condition when it is satisfied the equation:
is a discrete analogue of the second derivative. The main idea of this
Considering (
∆ −2 +1 = ∆ −1 −2 +3−∆ −1 −2 +1,
− +2− − ∆ −1 −2 +3 − ∆ −1 −2 +1
− +2 − − =
− +2 − − +1 From the last equation we get: −
2 − +2 − −
− +1 − − ∆ −2 −2( −2) − ∆ −2 −2( −2)−1
∆ −2 −2( −2)−1 − ∆ −2 −2( −2)−2 ∆ −2 −2 +5 − ∆ −2 −2 +3
− +3 − − +1 = 2 ∆ −2 −2( −2)−∆ −2 −2( −2)−1 − − +2− − +1 ∆ −2 −2( −2)−1−∆ −2 −2( −2)−2 − +1− − (4) .
(5) = = f 1 x 1
1 ∆ f
1 f 2 x 2
2 ∆ f
1 ∆ f 1 2 f 3 x 3
3 ∆ f
2 ∆ f
1 ∆ f 1 2 3 f 4 x 4 … … … … … …
3 ∆ f n−6
2 ∆ f n−5
1 ∆ f n−4 f n−3 xn−3 ~
3 ∆ f n−5
2 ∆ f n−4
1 ∆ f n−3 f n−2 xn−2 ~
2 ∆ f n−3
1 ∆ f n−2 f n−1 xn−1 ~
1 ∆ f n−1 f n x n f n+1 xn+1
The method is based on the search for conditions under which the error |∆ −2 +1 − ∆ −2 +1|
In [1],[6] was proposed the following algorithm Ξ , which consists of the next steps.
1. Construction the table of finite differences according to (
i
k = arg min | Δi−1 f n−2i+1 −
(Δi−2 f n−2i+3 − Δi−2 f n−2i+2 )| .
4. Building predictive value according to the procedure (
Spatial generalization of the "pyramidal" method was proposed in [12]. To construct the "predictive" value of some surface at the selected point, it is proposed to consider paths passing through lattice nodes, where the values of the corresponding surface are known and a special parameter (measure) of the predictability of the function is determined. Then, a predictive value is the result of one-dimensional "pyramidal" approach for the function values through the path for which the degree of predictability is maximal.
Without loss of generality we can consider uniform grid, xk − xk −1 = 0.5 . In this case finite
differences (
4∆k fl+3 − 8∆k fl+2 + 4∆k fl+1 + + (∆k f l+2 − ∆k f l ) , k ∆ fl+4 =4∆k fl+3 − 8∆k fl+2 + 4∆k fl+1 + (∆k fl+2 − ∆k fl ) + ∆k fl+2 = = 4∆k fl+3 − 6∆k fl+2 + 4∆k fl+1 − ∆k fl . ∆k f l+4 ∆k fl+3
k ∆ fl+2 ∆k fl+1
k ∆ f l
4∆k f l+3 − 8∆k f l+2 + 4∆k f l+1 + + (∆k f l+2 − ∆k f l ) ∆k fl+3 - ∆k fl+1 ∆k fl+2 - ∆k f l 4∆k f l+3 − 8∆k f l+2 + 4∆k f l+1 sufficient conditions for the fulfillment of the relation (4). last four points and predictable fifth point, equation (4) is satisfied.
We can use two results. In [3] it is investigated that procedure of building prediction according ещ
formula (4) is equivalent to the cubic extrapolation . Thus, the task of determining the forecast value
in the corresponding row of the pyramidal method is equivalent to the cubic forecast based on the last
(
xn−i+2 − xn−i+1
(Δi−2 f n−2i+4 − Δi−2 f n−2i+3 )), (xn−i+2 , (Δi−2 f n−2i+5 − Δi−2 f n−2i+3 ))
(7)
Thus, we have two criteria of (
Let us analyze a cases when parabola or a cubic curve gives the best forecast. It is obvious such property that faster interpolation curve grows on the forecast interval, the greater is probability of extrapolation error based on this curve.
Let us consider first three points of series (7) for the “quadratic” criteria or four points ( − −3, ∆ −2 −3), ( − −2, ∆ −2 −2), ( − −1, ∆ −2 −1,), ( − , ∆ −2 ) for the “cubic” one.
Let the point data sequence and the rate change are increasing. In this case, the quadratic or cubic forecast will also give an increase, but the real function may increase according to a significantly different law and error of the forecasting may be large. Let the point data sequence is increasing and the rate of change decreases. Then the nature of the uncertainty will significantly depend on the rate of growth and approach to a corresponding local extremum, the farther the extremum point from the observed interval, degree of uncertainty of the real function increases.
Let the abscissa of the point of the local extremum is inside the observed interval. In this case, the quadratic or cubic prediction is in the region of exiting from the zone of small change of function. The uncertainty can be large.
Let the quadratic or cubic interpolation curve have an extremum that coincides with the last observed point. In this case, the uncertainty is minimal, because if the real function also has a local extremum there, then the error is minimal. At the same time, if the real function does not have a local extremum at the last point, but it still reduces the growth rate. The curve optimally predicts a certain sequence of data if the forecast interval is in the area of a local extremum.
Thus, we can propose the following modification of the finite difference table row selection
procedure, for which an unknown predictive value is constructed by formula (
Condition β. In piramidal algorithm instead of condition (6) it is selected that line of the table of finite differences for which last observation point deviates minimally from the point of local extremum, determined by the cubic or quadratic interpolation curve.
Note that condition (6) describes a partial case of condition β. It can be proved that under condition (6) the points ( − −3, ∆ −2 −3), ( − −2, ∆ −2 −2), ( − −1, ∆ −2 −1,) lie on one line. This means that the function that passes through these points changes the convexity. Then the cubic polynomial at the last point has either an approach to the local extremum, or a rapid increase in the function, which will lead to a larger prediction error.
To illustrate our method, let’s consider data set on the incidence of COVID-19 in Ukraine (Official statistics of the Ministry of Health of Ukraine, ttps://www.pravda.com.ua/cdn/covid-19/cpa/). Let consider statistics from 22.12.20 until 10.01.21. We have input time series: 6545, 8513, 10136, 11490, 11035, 7709, 6113, 4385, 6988, 7986, 9699, 9432, 5038, 4576, 4158, 5334, 6911, 8997, 5676, 4846, 5011. Results of the evaluation according to our modified piramidal algorithm are in Fig. 4.
According to the condition β, we analyze distanсes from the last observation point ((xn−k+2 + xn−k+1 ) / 2,
(Δk−2 f n−2k+4 − Δk−2 f n−2k+3 )) (xn−k+2, ∆k−2fn−2+4k,) for cubic extrapolation or point xn−k+2 − xn−k+1 for the quadratic extrapolation to the point of corresponding local extremum.
The illustration of the process of finite differences is presented in the Fig. 4. Small distance was found for the row 8 for the quadratic extrapolation, = 8 , optimal distance –for the row 2. Graphs of the corresponding interpolation curves for the first case (row 8) are on the Fig. 5. You can see that both extrapolation curves give good results, last points are not far from the points of the corresponding local extremums.
Our predictive value is 4023, real value-4288.
We can also consider for this data set another row number 2 in the Fig. 6. This is optimal situation, for the quadratic extrapolation distanсe from the last observation point to the point of local extremum tends to 0 (see Fig. 5). Cubic extrapolation also gives good result. Our predictive value is 4675. 0
Let’s consider next value 4288 (number of COVID incidence in Ukraine 11.01.21) and add it to our data set. If we try to build prediction using piramidal approuch , there is not good situation according to the condition β for all roads of table of finite differences, predictive value is 794 (see Fig. 8), it is far from reality. This means that we cannot find predictive patterns in such dataset. In such situation we must use another method.
Let us consider other points of observation: 5116, 6409. We also can find good situation for the forecasting (see Fig. 11), predictive value is 7081 (see Fig. 10), real observation is7925. Let us consider next point 7925 and add it to our data set . Result of the forecasting is in the Fig. 12, 9422. Real value is 9699. -20000
The peculiarity of this example is that we have good compliance with the condition β only by quadratic extrapolation. Cubic extrapolation shows (see Fig. 13) that forecast point is in zone of convexity changing. This gives a good agreement with the quadratic extrapolation. But cubic extrapolation cannot be used independently, since it is impossible to assert by four points that the fifth is in the zone of convexity changes for the predicted function .
Thus, it is presented a new modification of the “piramidal” algorithm of data forecasting. Keeping the basic idea of the pyramidal approach, we have changed the procedure for selecting a row in the finite difference table where predicted value is found. The improved procedure allowed us to efficiently use the previously proposed piramidal approach for forecasting time series containing a stochastic component. Our approach works by finding certain patterns in a small series of data.
To illustrate our method, we consider data set on the incidence of COVID-19 in Ukraine from 22.12.2020 until 14.01.21. Numerical results have demonstrated the high efficiency of our technique of forecasting. Relative forecasting errors are within 2,8%-10,5%. Note that the errors could also be associated with inaccuracies in recording the number of cases in different regions of Ukraine.
In the process of the algorithm justification we obtaine interesting additional results. For example, equivalence of the prediction procedure according to the formula (4) and cubic extrapolation makes it possible to significantly improve, in the context of computational complexity, the classical method for constructing a forecast based on a cubic interpolation polynomial. Indeed, there is no need to compose a system of 4 algebraic equations and solve it to find the parameters of a cubic polynomial. It is enough to construct Fig. 3 and perform simple corresponding calculations which are described in detail in paragraph 2 (abscissa of the first interpolation point can be arbitrary, but the distances between the abscissas of all points must be the same).
The proposed method is generic and can be used to extrapolate the time series in arbitrary areas of research, including the construction of series of short-term forecasts of economic dynamics. 6. References [4] A.S. Kostinsky, On the principles of a spline extrapolation concerning geophysical data. Reports of the National Academy of Sciences of Ukraine 2 (2014) 111–117. doi:10.15407/dopovidi2014.02.111 [5] Z. Zhan, R Yang, Z Xi, et al., A Bayesian Inference based Model Interpolation and
Extrapolation. SAE Int. J. Mater. Manf. 5.2 (2012) 357-364. doi:10.4271/2012-01-0223 [6] Y. Turbal, A. Bomba, A. Sokh, O. Radoveniuk, M. Turbal, Spatial generalization of the pyramidal data etrapolation, Bulletin of Taras Shevchenko National University of Kyiv. Series Physics & Mathematics 2 (2017) 146-151. [7] Y. Turbal, M. Turbal, A.A.Driwi, S. Al Shukri, On the equivalence of the forecast value construction in the “pyramidal” extrapolation method and cubic forecast, MCIT 4 (2020) 67–70. doi.org/10.31713/MCIT.2020.15 [8] K. Xu, M. Zhang, J. Li, S. S. Du, K. Kawarabayashi, S. Jegelka, How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks, in: Proceedings of the International Conference on Learning Representations ICLR, Vienna Austria (2021) URL: http://arXiv:2009.11848v5 [9] J. I. Monroe, H. W. Hatch, N. A. Mahynski, M. S. Shell, V. K. Shen, Extrapolation and interpolation strategies for efficiently estimating structural observables as a function of temperature and density, J. Chem. Phys. 153 (2020) 144101. doi:10.1063/5.0014282. [10] N. A. Mahynski, J. R. Errington, V. K. Shen, Multivariable extrapolation of grand canonical free energy landscapes, J. Chem. Phys. 147 (2017) 234111. doi:10.1063/1.5006906. [11] L-Y. Wang, W-C. Lee, One-step extrapolation of the prediction performance of a gene signature derived from a small study, BMJ Open, 5:e007170 (2014). doi:10.1136/bmjopen-2014-007170 [12] N. P. Bakas, Numerical Solution for the Extrapolation Problem of Analytic Functions, Research
Volume 2019. doi:10.34133/2019/3903187
[13] T. CoşKun, Approximation of analytic functions of several variables by linear k-positive
operators. Turkish Journal of Mathematics 41 (
Methods Med Res 24(