NON-PARAMETRIC ALGORITHMS OF RECONSTRUCTION OF MUTUALLY AMBIGUOUS FUNCTIONS FROM OBSERVATIONS

Full Text

Introduction. The problem of function reconstruction from observations when the studied process is described by mutually ambiguous characteristics is considered. This task comes to a problem of approximation, the main feature of which is the lack of aprior information about a parametrical structure of the studied process model. Nonparametric estimation of mutually ambiguous charac- teristics, some modification and results of numerical studies are offered. At reconstruction of regression functions from obser- vations nonparametric estimates are often used. At the same time it is supposed that the nature of its dependence is unambiguous on an argument. Hereafter, the problem of function reconstruction from observations at mutually ambiguous dependence is considered. This demanded the introductoin of some changes into the known estimation of Nadaraya-Watson [1]. Aprior information. Aprior information - a set of known in advance data of the studied process, criteria of optimality and restrictions. The criterion of optimality expresses those requirements which have to be best satisfied and restrictions define our opportunities. Thus, the aprior information known to the researcher at an initial stage is a basis for a mathematical formulation of the task [2]. And in essence substantially predetermines a research method [3]. In various computer systems of modelling an impor- tant role belongs to reconstruction of functions from ob- servations, in particular to mutually ambiguous function which can be applied at creation of, for example, robots, robotic systems moving on in an unknown area (the area with an unknown terrain). The levels of aprior information are important during the modelling and control of discrete continuous process- ses. The processes proceeding continuously in time but the variables of which are controlled at discrete time points are related to such processes. Let us point out the following levels of aprior information [4]: 1. Systems with full information. In this case an op- erator of the process is exactly known, and the casual dis- turbances affecting an object and connection channels are absent. During the solution of identification and control problems, the methods of mathematical theory of opti- mum processes and also other methods of synthesis and analysis of control systems can be used. 2. Systems with incomplete information. These are systems with independent (passive) accumulation of information. In this case, the effect of input influence is perceived as simply random influence. Disrurbances are usually assumed in the theory of stochastic systems as random impact on an object. Besides, the class of opera- tors is not known exactly but the assumptions of density of distribution of all random factors are necessary. The density of probability of random factors affecting an ob- ject and in channels of variables measurement are usually assumed normal and additive. It is clear that in this case the existence of selection of input and output variables of an object is necessary and observations are statistically independent. Systems with incomplete information are related to the class of open or neutral systems. 3. Systems with active accumulation of information. The characteristic of these systems is that problems of identification and the task of control can be integrated because sample units of measurements consistently come to the training model and a control system. Thus in case of association of these tasks, the elaboration of control impacts has ambivalent (dual) character - they have to be both exploring and controlling [2; 3]. However if the dis- turbances operating the process are additive in channels of measurement as well, then in general the system of dual control can become open, its rate of information accumu- lation does not depend on values of input variables. Such systems are called leading to open or neutral. But there exists a class of non-neutral systems, i. e. a class of irre- ducible systems. 4. Systems with parametric ideterminacy. A paramet- ric level of aprior information assumes the existence of a model parametrical structure and some characteristics of random disturbances, such as zero mathematical expec- tation and limited dispersion which are usual. For estima- tion of parameters various iterative probabilistic proce- dures are used more often. Under these conditions the problem of identification in narrow sense, as well as in all previous cases, is also solved. 5. Systems with nonparametric uncertainty. A non- parametric level of aprior information does not assume the existence of a model but demands the existence of some data of qualitative character about the process, for example, unambiguity or ambiguity of its characteristics, linearity (for dynamic processes) or the nature of its nonlinearity. Methods of nonparametric statistics are ap- plied to the problem of identification at this level of aprior information solving (identification in a broad sense [5]). 6. Systems with parametric and nonparametric uncer- tainty. From the point of view of practice, the tasks of identification of multivariable systems under conditions when the volume of initial information does not correspond to any of the above described levels are important. For example, for separate characteristics of a multivariable process on the basis of physical-chemical and energy regularities, a law of conservation of mass, balance ratios parametrical regularities can be deduced, but for others The blurring parameter cs tions: meets the following condican not be deduced. Thus, we are in the situation when the task of identification is formulated under conditions of both parametric and nonparametric aprior information. Then models represent the interdependent system of pa- rametric and nonparametric ratios. Nonparametric approach. Nonparametric estimates of probability density of p(x) from observations xi, i = 1, s are the basis of this approach. Nonparametric estimates of multidimensional probability density were considered cs > 0 , lims®¥ s(cs )k =¥ , lims®¥ cs = 0 . (4) Nonparametric estimation of regression function from observations. For reconstruction of function of regression of M{y|x} from observations {xi,yi, i = 1, s } we use nonparametric estimates of density of probability (1). As, M{y|x} looks as follows: ò yp(x, y)dy in [1; 6] in details and are given as: M{y | x} = W( y ) . (5) 1 s 1 k æ x j - x j ö ò p(x, y)dy Ps (x) = å ÕФ çç i ÷÷, (1) W( y ) s i-1 cs j =1 è cs ø where Ps(x) - estimation of density of elements distribu- tion; s - sample size; k - a vector lenth x. Replacing in (5) p(x,y) by nonparametric estimates (1) and using property: Here Ф(v) - a kernel - the finite bell-shaped function integrating with a square which satisfies the conditions [1; 4; 6]: 1 ò yФæ y - yi ö dy = y , i = 1, s, c ç c ÷ i s W( y) è s ø (6) 0 < Ф(v) < ¥ "v Î Ç(v) , 1 Фæ x - xi ö dx = 1 , c ò ç ÷ s è cs ø it is easy to receive nonparametric estimation of function of Nadaraya-Watson regression which for a one- dimensional case looks as follows: lim 1 Фæ x - xi ö = d( x - x ) , (2) s æ x - x ö n®¥ c ç c ÷ i å yiФç i ÷ s è s ø i =1 è cs ø where cs - a blurring parameter defining the size of the Ys (x) = s , æ x - x ö (7) carrier and “delta-shape” of a kernel Ф(v) [4]. In a computing experiment the bell-shaped functions Ф(v) of different types are used, for example: åФç i ÷ i =1 è cs ø and for a case if x a k-dimensional vector it is equal: í Rectangular kernel: Ф(v) = ì0.5, 0, v £ 1, v s k æ x j - xi ö î > 1. å y ÕФ ç j ÷ Подпись: i ç ø ìï1- v , v £ 1, = i=1 Y (x) j =1 è cs ÷ , (8) Triangular kernel : Ф(v) = í 0, v > 1. (3) s s k æ x - xi ö îï åÕФ ç j j ÷ ìï0.75(1- v)2, v £ 1, i =1 j =1 ç cs ÷ Parabolic kernel: Ф(v) = í ïî0, v > 1. è ø where x , y , i = 1, s sample of observations; Ф(v) - a bell- In fig. 1, 2 function Ф(x/c )/c constructed for three i i s s shaped function; v - unspecified variable; cs - a blurring values of a blurring parameter cs = 0.2, 0.4, 0.6. is pre- sented. parameter. Fig. 1. Parabolic kernel Fig. 2. Triangular kernel Рис. 1. Параболическое ядро Рис. 2. Треугольное ядро At reconstruction of mutually ambiguous function of regression Nadaraya-Watson’s estimation has to be changed as follows [7; 8]: Ys (xt ) = yiФç c ÷Фç c ÷Фç c ÷ ås æ xt - xi ö æ x t -1- xi-1 ö æ yt -1 - yi-1 ö corresponding the given control task is possible. Blocks with the basic purpose of reconstruction of mutually ambiguous characteristics according to the experimental data can occur to be a constituent of the received control systems. We give the results of some computing experi- ment for a similar element of system below, exactly, the reconstruction of mutually ambiguous characteristics = i=1 è s ø è s ø è s ø , Фç c ÷Фç c ÷Фç c ÷ ås æ xt - xi ö æ x t -1- xi-1 ö æ yt -1 - yi-1 ö (9) from observations. When carrying out a computing experiment mutually ambiguous characteristics can have various shapes: circles, ellipses and others. Without violai=1 è s ø è s ø è s ø where xt-1, yt-1 values of coordinates of regression function of generality, we will accept mutually ambiguous characteristic of dependence y(x) (for simplicity reasons) tion on the previous step of its estimation. As numerous computing experiments showed it is worthwhile (7) to correct a bit as follows: Ys (xt ) = in the shape of a circle: x2 + y2 = r 2, where r - a circle radius. (13) s æ xt - xi ö 0 æ x t -1- xi-1 ö 0 æ yt -1 - yi-1 ö In this case the training sample was formed in the folc c c å yiФç ÷Ф ç ÷Ф ç ÷ = i=1 è s ø è s ø è s ø , (10) lowing way: the initial point x' was set on a random basis and y'(x) was calculated according to (13). As a result, s æ xt - xi ö 0 æ x t -1- xi-1 ö 0 æ yt -1 - yi-1 ö the sample x , y , i = 1, s was formed. Note that x could be åФç c ÷Ф ç c ÷Ф ç c ÷ i i i i=1 è s ø è s ø è s ø defined as a result of a stable step Δx on x Î W(x) or of where Ф0(v) with an accuracy to coefficient repeats Ф(v), and Ф0(v) = 1, if v < 1 and 0 in other cases. In this case Ф0(v) will not affect a reconstruction error but will allow “to record” an algorithm in the previous point of the movement at estimation of every subsequent point. If x vector of dimension of k: (x1, …, xk)Î Rk, the training sample in this case is: x1i, …, xki, yi, i = 1, s . At reconstruc- tion of mutually ambiguous function of regression non- parametric estimation has to be changed as follows: a random number detector xi Î W(x) , i = 1, s . During the process of computer research other mutually ambiguous characteristics of dependence y(x) were also used. At reconstruction of mutually ambiguous characteris- tic from observations unknown to the researcher, the question of the choice of the direction of movement is important, though, in principle, it can be arbitrary at an initial stage. But all subsequent changes of the current variable x are in rigorous dependence of the previous one. s k æ xj -xj ö k æ xj -xj ö æ y -y ö The processes characterized by mutually ambiguous åyiÕФç t i ÷ÕФç t-1 i-1÷ Фç t-1 i-1÷ dependences have such feature that values xt, t = 1,2… Y (x ) = i=1 j=1 è cs ø j=1 è cs ø è cs ø, appear strictly sequentially in this or that direction. In fig. 3 s t s k æ xj -xj ö k æ xj -xj ö æ y -y ö (11) such process is presented. Let, for example, on the first ç ÷ ç ÷ åÕФ t i ÕФ t-1 i-1 Фç t-1 i-1÷ i=1 j=1 è cs øj=1 è cs ø è cs ø step of x = x1, then x2 etc. Values xt appear only after xt-1, that is “movement” xt in the arbitrary direction takes where xj , yj values of coordinates of regression funcplace. Emergence of values begins at some point of xt t-1 t-1 tion on the previous step of its estimation. Nonparametric estimation (11) can be modified as fol- lows: and moves sequentially, passing points t2, t3. At the same time transition of x1, for example, to x5 is impossible until the previous four points are passed. Thus, the entity of the offered estimates (9), (10), is that at estimation of the next k 0 æ x jt - x ji ö k 0 æ x j t -1-x ji-1 ö point, “fixing” to the previous point in the corresponding s yiÕФ çç å j=1 è cs ç ÷ i=1 ´ Ф0 æ yt -1 - yi-1 ö c ÷÷ÕФ çç c ø j=1 è s ÷÷´ ø algorithms takes place (9), (10). In fig. 3 the process representing a circle is given. The movement along a variable happens from right to left and from left to right, what characterizes serial emergence Y (x ) = è s ø , (12) s t k æ x j - x j ö k æ x j -x j ö of sample values. s ÕФ0 çç t i ÷÷ÕФ0 çç t -1 i-1 ÷÷ ´ å j=1 è cs ø j=1 è cs ø On the following step random impact of h from observations yi was added i=1 ´Ф0 æ yt -1 - yi-1 ö hi = lyix, (14) ç ÷ è cs ø where xÎ[-1,1] , disturbances level l = 0, 5,10 %. where Ф0(v) is same as above. A computing experiment. First, we will consider some ideas of the control theory. The key feature is that the existing theory of control needs to present the object equation with an accuracy to a vector [9-11]. Proceeding As a criterion of accuracy of nonparametric estimation the ratio was used: Подпись: s å yi - ys (xi ) from it, regulators can be synthesized: adaptive, self- adjusting and others [12; 13]. At application of the opti- mum theory of control [2; 14; 15] getting the regulators w = i=1 , s å yi - y i=1 (15) where = 1 s - arithmetic mean; y (x ) - nonparais equal to 50, 100, 500 elements; the disturbances level s y å yi i =1 s i is equal to 0 %; the experiment was conducted in the mode of the sliding examination. metric estimation; yi - true sample received according to a formula (13). We will give the results of a numerical research illus- trating effectiveness of an algorithm. As a bell-shaped finite function the triangular kernel was used. The algo- rithm was tested on the training samples of various sizes, at the same time serial increase in a sample size was per- formed by addition of new elements to already available: s = 50, 100, 500. In all drawings we designate figure (1) - the training sample, (2) - nonparametric estimation. The operation of an algorithm (9) in fig. 4-6 under various conditions is shown: when the sample size In fig. 7 the dependence of an error values of recon- struction of size at various disterbance levels is presented. In computing experiments other mutually ambiguous characteristics were also used. Some fragments of a re- search are given below. In fig. 8, 9 the experiment under various conditions was conducted: the sample size is equal to 100, 200 elements; the disturbance level is equal to 0 %; the experiment was made in the mode of the sliding examination. In fig. 10-15 it is well visible how the error of recon- struction depends on a disturbance level and on a sample size for a circle and for amore composite figure. Fig. 3. This sample is presented Рис. 3. Представлена данная выборка Fig. 4. S = 50; w = 0.1098 Fig. 5. S = 100; w = 0.0469 Рис. 4. S = 50; w = 0,1098 Рис. 5. S = 100; w = 0,0469 Fig. 6. S = 500; w = 0.0068 Рис. 6. S = 500; w = 0,0068 Fig. 7. Dependence of the recovery errors on the volume at different levels of interference Рис. 7. Зависимость значений ошибки восстановления от объема при различных уровнях помех Fig. 8. S = 100; w = 0.042 Fig. 9. S = 200; w = 0.018 515 Рис. 8. S = 100; w = 0,042 Рис. 9. S = 200; w = 0,018 Fig. 10. S = 50; l = 5 %; w = 0.2173 Fig. 11. S = 50; l = 10 %; w = 0.2926 Рис. 10. S = 50; l = 5 %; w = 0,2173 Рис. 11. S = 50; l = 10 %; w = 0,2926 Fig. 12. S = 100; l = 5 %; w = 0.0602 Fig. 13. S = 100; l = 10 %; w = 0.0845 Рис. 12. S = 100; l = 5 %; w = 0,0602 Рис. 13. S = 100; l = 10 %; w = 0,0845 Fig. 14. S = 200; l = 5 %; w = 0.0308 Fig. 15. S = 200; l = 10 %; w = 0.0011 516 Рис. 14. S = 200; l = 5 %; w = 0,0308 Рис. 15. S = 200; l = 10 %; w = 0,0011 For descriptive reasons, we will change places of yi and xi in estimation (9) in fig. 16, 17. We will be convinced that estimation differs a bit at points of intersection of the graph and an abscissa axis as could seem from fig. 10-13. We will demonstrate the work modified algorithm (10), under the following conditions: at a disturbance level equal to 5 and 10 %; with a sample size equal to 100 ele- ments; in the mode of the sliding examination. Comparing errors of reconstruction we look at fig. 12, 13 and 18, 19 and we see a small improvement. In fig. 18, 19 we see that an error of reconstruction is a little less than in fig. 12, 13. This means that nonpara- metric estimation has became more accurate. Also in a case with a more composite function in fig. 20, 21 it is visible that an error of reconstruction is a little less than in fig. 14, 15. This means that nonparametric estimation has became more accurate. It should be noted that: with decrease of an error reconstruction (w) the accuracy of estimation increases; with the increase of a sample size (s) the error of recon- struction (w) decreases; the size of an error grows at increase of a disturbance level (l). The following question is possible: “Why was the circle used to check the work of an algorithm?”, because there are a lot of more composite shapes, and the answer is simple - the chsracteristic of this algorithm is its uni- versality. This means that it is not essential for an algo- rithm what function to reconstruct, whether it is a circle, an ellipse, an Archimedes spiral or a Cassini’s oval. “Being fixed” in the previous xt point, that is in a xt-1 point, and following the sense of a rotation, it is always possible to get a nonparametric estimation of mutually ambiguous functions. Fig. 16. S = 500; l = 5 %; w = 0.0283 Fig. 17. S = 500; l = 10 %; w = 0.055 Рис. 16. S = 500; l = 5 %; w = 0,0283 Рис. 17. S = 500; l = 10 %; w = 0,055 Fig. 18. S = 100; l = 5 %; w = 0.057 Fig. 19. S = 100; l = 10 %; w = 0.0817 Рис. 18. S = 100; l = 5 %; w = 0,057 Рис. 19. S = 100; l = 10 %; w = 0,0817 Fig. 20. S = 200; l = 5 %; w = 0.0301 Fig. 21. S = 200; l = 10 %; w = 0.0009 Рис. 20. S = 200; l = 5 %; w = 0,0301 Рис. 21. S = 200; l = 10 %; w = 0,0009 Conclusion. The main result of the present article is an introduction of a new class nonparametric estimation of mutually ambiguous functions from observations with errors. It distinguishes the problems of nonparametric estimation from the known nonparametric estimates of the function of Nadaraya-Vatsona regression. Some modifica- tions of nonparametric estimates are given, under such conditions the attention is drawn to a method of bypassing of entered nonparametric estimates along a trajectory determined by elements of the training sample. For simplicity of a numerical research the function described by a circle was taken, though it is not essential to the offered algorithm. In other words, the algorithms offered are suitable for reconstruction of the ambiguous dependences described by more composite curves, the character of which is apriori unknown, only a sample of observations of the studied process is known.

About the authors

A. A. Korneeva

Siberian Federal University, Institute of space and information technologies

26b, Academica Kirenskogo Str., 660074, Russian Federation

S. S. Chernova

Siberian Federal University, Institute of space and information technologies

Email: chsvetlanas@gmail.com
26b, Academica Kirenskogo Str., 660074, Russian Federation

A. V. Shishkina

Siberian Federal University, Institute of space and information technologies

26b, Academica Kirenskogo Str., 660074, Russian Federation

References

Supplementary files