2020, issue 3, p. 14-24
Received 11.10.2020; Revised 19.10.2020; Accepted 23.10.2020
Published 27.10.2020; First Online 05.11.2020
https://doi.org/10.34229/2707-451X.20.3.2
Previous | Full text (in Ukrainian) | Next
Ellipsoid Method for Linear Regression Parameters Determination
V. Stovba
V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. Linear regression parameters determination can be formulated as a non-smooth function minimization problem, which is Lp-norm of residual of the linear equations system. To solve it non-smooth function minimization methods can be used, e.g. subgradient methods. The article [7] considers ellipsoid method application for finding Lp-solution of redefined linear equations system with 1≤p≤2.
The purpose of the paper is to extend the algorithm based on the ellipsoid method for a linear regression parameters determination problem with an arbitrary value of parameter p≥2 so that under big values of p the solution of the problem equals minimax method solution, which corresponds to p=∞ case. To describe the formulation of observation approximation problem with quadratic function as linear regression parameters determination problem. To analyze algorithm work results for great number of observations and outliers. To compare the minimax method and the ellipsoid method algorithm work results for linear regression parameters determination problem with big values of parameter p.
Results. The way of calculation of objective function and its subgradient values with large values of parameter p was developed and verified on example of observation approximation containing outliers with linear function. Algorithm based on ellipsoid method changes linear function parameters monotonically using parameter p adjusting, thereby permits to reject or consider these or those observations. It is shown in [3] that Least Absolute Deviations method (LAD) is advised to be used as far as it ignores outliers and reconstructs linear function accurately. Experiment results with big number of observations and outliers using p=1 confirmed that conclusion: LAD ignores outlier groups and approximates observations with linear function adequately. Least Square Method (LSM) deviates from optimal linear function if a group of outliers is present in particular area. In case of using big values of parameter p problem solution converges to minimax method solution.
Conclusions. Algorithm based on ellipsoid method permits to determine linear regression parameters with arbitrary value of parameter p≥1. So, three known methods can be used – LAD, LSM and minimax method – as its special cases. Moreover, directing p to 1, intensity of outliers ignoring can be regulated, that gives a possibility to use external sources of information (expert opinions, measuring devices readings, statistical forecasts, etc.) for more correct and adequate approximation function reconstruction.
Keywords: ellipsoid method, linear regression, outliers.
Cite as: Stovba V. Ellipsoid Method for Linear Regression Parameters Determination. Cybernetics and Computer Technologies. 2020. 3. P. 14–24. (in Ukrainian) https://doi.org/10.34229/2707-451X.20.3.2
References
1. Demydenko E.Z. Linear and non-linear regression. М.: Finansy i statistika, 1981. 304 p. (in Russian)
2. Shor N.Z., Stetsyuk P.I. Constructing Utility Functions by Methods of Nondifferentiable Optimization. In: Constructing and Appling Objective Functions, Lecture Notes in Economics and Mathematical Systems. V. 510. Berlin: Springer-Verlag, 2002. P. 215–232. https://doi.org/10.1007/978-3-642-56038-5_10
3. Stetsyuk P.I., Kolesnik Y.S., Leibovych M.M. On robustness of least absolute deviations. Kompyuternaya matematika. 2002. P. 114–123. (in Russian)
4. Stetsyuk P.I., Kolesnik Y.S. To the issue of selection of observation approximation method. Intellektualnye informacionno-analiticheskie sistemy i kompleksy. 2000. P. 62–67. (in Russian)
5. Stetsyuk P.I., Stovba V.A., Martynyuk I.S. Algorithms of ellipsoid method for finding Lp-solution of linear equations system. Teoriia optymalnykh rishen. 2017. P. 139–146. (in Russian) http://dspace.nbuv.gov.ua/handle/123456789/131449
6. Shor N.Z. Cut-off method with space extension in convex programming problems. Cybern Syst Anal. 1977. 1. P. 94–95. https://doi.org/10.1007/BF01071394
7. Stetsyuk P.I., Stovba V.A., Zhmud A.A. Ellipsoid method for finding solution of linear equations system. Teoriia optymalnykh rishen. 2018. 17. P. 115–123. (in Russian) http://dspace.nbuv.gov.ua/handle/123456789/144980
8. Stetsyuk P.I., Bila G.D., Stovba V.A. Ellipsoid method for finding Lp-solution of linear equations system. Proceedings of the VIII All-Ukrainian scientific and practical conference Informatyka Ta Systemni Nauky (ISN-2017). Poltava, Ukraine, March 16–18, 2017. (in Russian)
9. Clarke F. Optimization and non-smooth analysis. М.: Nauka, 1988. 280 p. (in Russian)
10. Gruber J. Opening Remarks: A Retrospection over 35 Years of Work. Constructing and Appling Objective Functions, Lecture Notes in Economics and Mathematical Systems. V. 510. Berlin: Springer-Verlag, 2002. P. 3–13. https://doi.org/10.1007/978-3-642-56038-5_1
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | Full text (in Ukrainian) | Next