2017 , Volume 22, ¹ 2, p.150-172
Strong compatibility in data fitting problem under interval data uncertainty
The data fitting problem is a popular and practically important problem in which a functional dependency between “input” and “output” variables is to be constructed from empirical data. At the same time, the measurements are almost always subject to uncertainties due to data inadequacy and errors in real-life situations.
Traditionally, when processing the measurement results, models of probability theory are used, which is not always adequate to the problems under study. An alternative way to describe data inaccuracy is to use methods of interval analysis, based on specifying interval bounds of the measurement results. Data fitting problems under interval uncertainty are being solved for about half a century. Most studies in this field rely on the concept of compatibility between parameters and measurement data in which any measurement result is a kind of a large point “inflated” to a box (rectangular parallelepiped with facets parallel to the coordinate axes). The graph of the constructed function passing through such a “point” means a nonempty intersection of the graph with the box. However, in some problems, this natural concept turns out unsatisfactory.
In this work, for the data fitting under interval uncertainty, we introduce the concept of strong compatibility between data and parameters. It is adequate to the situations when measurements of input and output variables are broken in time, and we strive to uniformly take into account the interval results of output measurements. The paper gives a practical interpretation of the new concept. It is shown that the modified formulation of the problem reduces to recognition and further estimation of the so-called tolerable solution set to interval systems of equations constructed from the processed data.
We propose a computational technology for the solution of the data fitting problem under interval uncertainty that satisfies strong compatibility requirement. Finally, we consider generalizations of the concept of strong compatibility.
Keywords: data fitting problem, compatibility between data and parameters, strong compatibility, interval system of linear equations, tolerable solution set, recognizing functional, convex nonsmooth optimization
Shary Sergey Petrovich
Dr. , Senior Scientist
Position: Leading research officer
Office: Institute of Computational Technologies SB RAS
Address: 630090, Russia, Novosibirsk, Ac. Lavrentiev ave, 6
Phone Office: (3832) 30 86 56
 Shary, S.P. Strong compatibility in data fitting problems based on interval data. Bulletin of the South Ural State University. Seriya: Mathematics. Mechanics. Physics. 2017; 9(1):39–48. (In Russ.)
 Kearfott, R.B., Nakao, M., Neumaier, A., Rump, S., Shary, S.P., van Hentenryck, P. Standardized notation in interval analysis. Computational technologies. 2010; 15(1):7–13.
 Kantorovich, L.V. On some new approaches to numerical methods and processing of observation data. Siberian Math. Journal. 1962; 3(5):701–709. (In Russ.)
 Lidov, M.L. Minimax estimation methods. Preprint of Keldysh Institute of Applied Mathemetics. Moscow; 2010(71): 87. (In Russ.)
 Spivak, S.I., Timoshenko, V.I., Slin’ko, M.G. Application of Chebyshev alignment for the construction of kinetic model of complex chemical reaction. Doklady Academii Nauk. 1970; 192(3):580–582. (In Russ.)
 Spivak, S.I., Kantor, O.G., Yunusova, D.S., Kuznetsov, S.I., Kolesov, S.V. Evaluation of measurement accuracy and significance for linear models. Informatics and its Applications. 2015; 9(1):87–97. (In Russ.)
 Voshchinin, A.P. Interval data analysis: development and perspectives. Industrial Laboratory. 2002; 68(1):118–126. (In Russ.)
 Voshchinin, A.P. Problems of analysis with uncertain data — intervality and/or randomness? Proceedings of the International Conference on Computational Mathematics ICCM-2004. Workshops. Novosibirsk: Izdatel'stvo IVMiMG SO RAN; 2004: 147–158. (In Russ.)
 Voshchinin, A.P., Bochkov, A.F., Sotirov, G.R. A method for data analysis under interval nonstatistical error. Industrial Laboratory. 1990; 56(7):76–81. (In Russ.)
 Oskorbin, N.M., Maksimov, A.V., Zhilin, S.I. Construction and analysis of empirical dependences using the uncertainty center method. Izvestiya of Altai State University Journal. 1998; (1):37–40. (In Russ.)
 Noskov, S.I. Tekhnologiya modelirovaniya ob"ektov s nestabil'nym funktsionirovaniem i neopredelennost'yu v dannykh [Modeling Technology for Objects with Nonstable Functioning and Data Uncertainty]. Irkutsk: Oblinformpechat’; 1996: 320. (In Russ.)
 Zhilin, S.I. Nonstatistical models and methods for construction and analysis of dependences. PhD thesis. Barnaul: AltGU; 2004: 119. (In Russ.)
 Zhilin, S.I. On fitting empirical data under interval error. Reliable Computing. 2005; 11(5):433–442.
 Zhilin, S.I. Simple method for outlier detection in fitting experimental data under interval error. Chemometrics and Intellectual Laboratory Systems. 2007; 88(1):60–68.
 Polyak, B.T., Nazin, S.A. Estimation of parameters in linear multidimensional systems under interval uncertainty. Journal of Automation and Information Sciences. 2006; 38(2):19–33.
 Milanese, M., Norton, J., Piet-Lahanier, H., Walter, E. (eds.) Bounding Approaches to System Identification. New York: Plenum Press; 1996: 567.
 Jaulin, L., Kieffer, M., Didrit, O., Walter, E. Applied Interval Analysis. London: Springer; 2001: 379.
 Shary, S. P. Solvability of interval linear equations and data analysis under uncertainty. Automation and Remote Control. 2012; 73(2):310–322. DOI: 10.1134/S0005117912020099
 Shary, S.P., Sharaya, I.A. Recognizing solvability of interval equations and its application to data analysis. Computational Technologies. 2013; 18(3):80–109. (In Russ.)
 Shary, S.P. Maximum consistency method for data fitting under interval uncertainty. Journal of Global Optimization. 2015; 62(3). 16 p.
 Gutowski, M.W. Interval experimental data fitting. Focus on Numerical Analysis. J.P. Liu, editor. New York: Nova Science Publishers; 2006: 27–70.
 Shary, S.P. Solving the linear interval tolerance problem. Mathematics and Computers in Simulation. 1995; (39):53–85.
 Shary, S. P. An interval linear tolerance problem. Automation and Remote Control. 2004; 65(10):1653–1666. DOI: 10.1023/B:AURC.0000044274.25098.da
 Shary, S. P. Konechnomernyy interval'nyy analiz [Finite-Dimensional Interval Analysis]. Novosibirsk: Institute of computational technologies SB RAS; 2016: 617. Available at: http://www.nsc.ru/interval/Library/InteBooks (In Russ.)
 Lyapin, D.S. Programmno-matematicheskie sredstva modelirovaniya sistemnykh svyazey na osnove analiza interval'nykh dannykh [Software and mathematical tools for modeling system relations based in interval data analysis]. PhD thesis. Moscow: Moscow State University of instrument engineering and informatics; 2006: 121. (In Russ.)
 Rohn, J. Inner solutions of linear interval systems. Interval Mathematics 1985. K. Nickel, ed. Lecture Notes in Computer Science 212. Berlin: Springer-Verlag; 1986:157–158.
 Rohn, J. A Handbook of Results on Interval Linear Problems. 2005: 80. Available at: http://www.nsc.ru/interval/Library/Surveys/ILinProblems.pdf
 Sharaya, I.A. Structure of the tolerable solution set of an interval linear system. Computational Technologies. 2005; 10(5):103–119. (In Russ.)
 Schrijver, A. Theory of Linear and Integer Programming. Chichester-New York: Wiley; 1998: 484.
 Shary, S.P. On optimal solution of interval linear equations. SIAM Journal on Numerical Analysis. 1995; 32(2):610-630.
 Sharaya, I.A. Paket IntLinIncR3 dlya vizualizatsii mnozhestv resheniy interval'nykh lineynykh sistem s tremya neizvestnymi [IntLinInc3D, software package for visualization of solution sets to interval linear 3D systems]. Available at: http://www.nsc.ru/interval/sharaya
 Remez, E. Ya. Osnovy chislennykh metodov chebyshevskogo priblizheniya. [Fundamentals for Numerical Methods of Chebyshev Approximation]. Kiev: Naukova Dumka; 1969: 624. (In Russ.)
 Shor, N.Z., Zhurbenko, N.G. Minimization method using operation of space dilatation in the direction towards difference of two sequential gradients. CYBERNETICS AND SYSTEMS ANALYSIS. 1971; (3):51–59. (in Russ.)
 Stetsyuk, P.I. Metody ellipsoidov i r-algoritmy [Ellipsoids methods and r-algorithms]. Kishineu: «Evrika»; 2014: 488. (In Russ.)
 Stetsyuk, P.I. Subgradient methods ralgb5 and ralgb4 for minimization of ravine convex functions. Computational Technologies. 2017; 22(2):127-149. (In Russ.)
 Nurminski, E.A. Separating plane algorithms for convex optimization. Mathematical Programming. 1997; (76):373–391.
 Vorontsova, E. Extended separating plane algorithm and NSO-solutions of PageRank problem. Discrete Optimization and Operations Research. Proceedings of 9th International Conference DOOR 2016, Vladivostok, Russia, September 19-23, 2016. Kochetov, Y., Khachay, M., Beresnev, V., Nurminski, E., Pardalos, P., eds. Lecture Notes in Computer Science. Cham, Switzerland: Springer International; 2016: (9869): 547–560. DOI:10.1007/978- 3-319-44914-2.43.
 Vorontsova, E.A. Linear tolerance problem for input-output models with interval data. Computational Technologies. 2017; 22(2):67-84. (In Russ.)
 Sharyi, S.P. Algebraic approach to analysis of linear static systems with interval uncertainty. JOURNAL OF COMPUTER AND SYSTEMS SCIENCES INTERNATIONAL . 1997; 36(3):378-387.
 Shary, S.P. A new technique in systems analysis under interval uncertainty and ambiguity. Reliable Computing. 2002; 8(5):321–418.
 Sharaya, I. A., Shary, S. P. Reserve of characteristic inclusion as recognizing functional for interval linear systems. Scientific Computing, Computer Arithmetic, and Validated Numerics: 16th International Symposium, SCAN 2014, Wurzburg, Germany, September 21-26, 2014. Revised Selected Papers. Marco Nehmeier, Jurgen Wolff von Gudenberg, Warwick Tucker, editors. Heidelberg: Springer; 2016:148–167.
 Kreinovich, V., Shary, S. P. Interval methods for data fitting under uncertainty: a probabilistic treatment. Reliable Computing. 2016; (23):105–140. Available at: http://interval.louisiana.edu/ reliable-computing-journal/volume-23/reliable-computing-23-pp-105-140.pdf
Shary S.P. Strong compatibility in data fitting problem under interval data uncertainty // Computational technologies. 2017. V. 22. ¹ 2. P. 150-172