×

zbMATH — the first resource for mathematics

On the possibilistic approach to linear regression models involving uncertain, indeterminate or interval data. (English) Zbl 1357.62237
Summary: We consider linear regression models where both input data (the observations of independent variables) and output data (the observations of the dependent variable) are affected by loss of information caused by uncertainty, indeterminacy, rounding or censoring. Instead of real-valued (crisp) data, only intervals are available. We study a possibilistic generalization of the least squares estimator, so called OLS-set for the interval model. Investigation of the OLS-set allows us to quantify whether the replacement of real-valued (crisp) data by interval values can have a significant impact on our knowledge of the value of the OLS estimator. We show that in the general case, very elementary questions about properties of the OLS-set are computationally intractable (assuming \(\mathrm{P}\neq \mathrm{NP}\)). We also focus on restricted versions of the general interval linear regression model to the crisp input case. Taking the advantage of the fact that in the crisp input – interval output model the OLS-set is a zonotope, we design both exact and approximate methods for its description. We also discuss special cases of the regression model, e.g. a model with repeated observations.

MSC:
62J05 Linear regression; mixed models
62J86 Fuzziness, and linear inference and regression
68Q25 Analysis of algorithms and problem complexity
Software:
INTLAB; VERSOFT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alefeld, G.; Herzberger, J., Introduction to Interval Computations, Computer Science and Applied Mathematics, (1983), Academic Press New York, USA
[2] Alefeld, G.; Mayer, G., New criteria for the feasibility of the Cholesky method with interval data, SIAM Journal on Matrix Analysis and Applications, 30, 1392-1405, (2008) · Zbl 1176.65023
[3] Arora, S.; Barak, B., Computational complexity: A modern approach, (2009), Cambridge University Press UK · Zbl 1193.68112
[4] Avis, D.; Fukuda, K., Reverse search for enumeration, Discrete Applied Mathematics, 65, 21-46, (1996) · Zbl 0854.68070
[5] Bentbib, A. H., Solving the full rank interval least squares problem, Applied Numerical Mathematics, 41, 283-294, (2002) · Zbl 1021.65018
[6] Černý, M., Goffin’s algorithm for zonotopes, Kybernetika, 48, 890-906, (2012) · Zbl 1269.90141
[7] Černý, M.; Hladík, M., The regression tolerance quotient in data analysis, (Houda, M.; Friebelová, J., Proceedings of Mathematical Methods in Economics 2010, (2010), University of South Bohemia Czech Republic), 98-104
[8] M. Černý, M. Rada, A note on linear regression with interval data and linear programming, in: Quantitative Methods in Economics: Multiple Criteria Decision Making XV, Kluwer, Iura Edition, Slovakia, 2010, pp. 276-282.
[9] Černý, M.; Rada, M., On the possibilistic approach to linear regression with rounded or interval-censored data, Measurement Science Review, 11, 34-40, (2011)
[10] Chang, P.-T.; Lee, E. S.; Konz, S. A., Applying fuzzy linear regression to VDT legibility, Fuzzy Sets and Systems, 80, 197-204, (1996)
[11] Chuang, C., Extended support vector interval regression networks for interval input-output data, Information Sciences, 178, 871-891, (2008) · Zbl 1126.68525
[12] Dunyak, J. P.; Wunsch, D., Fuzzy regression by fuzzy number neural networks, Fuzzy Sets and Systems, 112, 371-380, (2000) · Zbl 0948.62049
[13] Dyer, M.; Frieze, A.; Kannan, R., A random polynomial-time algorithm for approximating the volume of convex bodies, Journal of the ACM, 38, 1-17, (1991) · Zbl 0799.68107
[14] Dyer, M.; Gritzmann, P.; Hufnagel, A., On the complexity of computing mixed volumes, SIAM Journal of Computing, 27, 356-400, (1998) · Zbl 0909.68193
[15] Entani, T.; Inuiguchi, M., Group decisions in interval AHP based on interval regression analysis, (Huynh, V.-N.; Nakamori, Y.; Lawry, J.; Inuiguchi, M., Integrated Uncertainty Management and Applications, Advances in Soft Computing, vol. 68, (2010), Springer Germany), 269-280 · Zbl 1197.90251
[16] Ferrez, J.-A.; Fukuda, K.; Liebling, T., Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm, European Journal of Operational Research, 166, 35-50, (2005) · Zbl 1066.90101
[17] Garloff, J., Pivot tightening for the interval Cholesky method, Proceedings in Applied Mathematics and Mechanics (PAMM), 10, 549-550, (2010)
[18] Gay, D. M., Interval least squares—a diagnostic tool, (Moore, R. E., Reliability in Computing: The Role of Interval Methods in Scientific Computing, Perspectives in Computing, vol. 19, (1988), Academic Press Boston, USA), 183-205 · Zbl 0658.65149
[19] Goffin, J. L., Variable metric relaxation methods. part II: the ellipsoid method, Mathematical Programming, 30, 147-162, (1984) · Zbl 0567.90068
[20] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric algorithms and combinatorial optimization, (1993), Springer Germany · Zbl 0837.05001
[21] Guibas, L. J.; Nguyen, A.; Zhang, L., Zonotopes as bounding volumes, Proceeding SODA ’03 Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, (2003), SIAM Pennsylvania
[22] Guo, P.; Tanaka, H., Dual models for possibilistic regression analysis, Computational Statistics and Data Analysis, 51, 253-266, (2006) · Zbl 1157.62469
[23] Hájek, P.; Pudlák, P., Metamathematics of First Order Arithmetic, Perspectives in Mathematical Logic, (1993), Springer Germany · Zbl 0781.03047
[24] Hesmaty, B.; Kandel, A., Fuzzy linear regression and its applications to forecasting in uncertain environment, Fuzzy Sets and Systems, 15, 159-191, (1985) · Zbl 0566.62099
[25] Hladík, M., Description of symmetric and skew-symmetric solution set, SIAM Journal on Matrix Analysis and Applications, 30, 509-521, (2008) · Zbl 1165.65025
[26] Hladík, M., Enclosures for the solution set of parametric interval linear systems, International Journal of Applied Mathematics and Computer Science, 22, 561-574, (2012) · Zbl 1310.65051
[27] Hladík, M., Solution set characterization of linear interval systems with a specific dependence structure, Reliable Computing, 13, 361-374, (2007) · Zbl 1127.65024
[28] Hladík, M., Solution sets of complex linear interval systems of equations, Reliable Computing, 14, 78-87, (2010)
[29] Hladík, M.; Černý, M., Interval regression by tolerance analysis approach, Fuzzy Sets and Systems, 193, 85-107, (2012) · Zbl 1238.62078
[30] M. Hladík, M. Černý, New approach to interval linear regression, in: R. Kasımbeyli, C. Dinçer, S. Özpeynirci, L. Sakalauskas (Eds.), 24th Mini-EURO Conference on Continuous Optimization and Information-Based Technologies in the Financial Sector MEC EurOPT 2010, Selected Papers, Technika, Vilnius, Lithuania, 2010, pp. 167-171.
[31] Huang, C.-H.; Kao, H.-Y., Interval regression analysis with soft-margin reduced support vector machine, Lecture Notes in Computer Science, vol. 5579, (2009), Springer Germany
[32] M. Inuiguchi, H. Fujita, T. Tanino, Robust interval regression analysis based on Minkowski difference, in: SICE 2002: Proceedings of the 41st SICE Annual Conference, vol. 4, Osaka, Japan, 2002, pp. 2346-2351.
[33] H. Ishibuchi, H. Tanaka, Several formulations of interval regression analysis, in: Proceedings of Sino-Japan Joint Meeting on Fuzzy Sets and Systems B2-2, Beijing, China, 1990, pp. 1-4.
[34] Ishibuchi, H.; Tanaka, H.; Okada, H., An architecture of neural networks with interval weights and its application to fuzzy regression analysis, Fuzzy Sets and Systems, 57, 27-39, (1993) · Zbl 0790.62072
[35] Jansson, C., Calculation of exact bounds for the solution set of linear interval systems, Linear Algebra and its Applications, 251, 321-340, (1997) · Zbl 0869.65020
[36] G. Jun-Peng, L. Wen-Hua, Regression analysis of interval data based on error theory, in: Proceedings of 2008 IEEE International Conference on Networking, Sensing and Control ICNSC, Sanya, China, 2008, pp. 552-555.
[37] M. Kaneyoshi, H. Tanaka, M. Kamei, H. Furuta, New system identification technique using fuzzy regression analysis, in: Proceedings of the First International Symposium on Uncertainty Modeling and Analysis, Baltimore, USA, 1990, pp. 528-533.
[38] K. Karlík, The Least Squares Method with Non-precise Data (in Czech), Master thesis, Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University in Prague, 2008.
[39] H. Kashima, K. Yamasaki, A. Inokuchi, H. Saigo, Regression with interval output values, in: 19th International Conference on Pattern Recognition ICPR 2008, Tampa, USA, 2008, pp. 1-4.
[40] Kolev, L. V., Solving linear systems whose elements are nonlinear functions of intervals, Numerical Algorithms, 37, 199-212, (2004) · Zbl 1076.65028
[41] Lee, H.; Tanaka, H., Fuzzy regression analysis by quadratic programming reflecting central tendency, Behaviormetrika, 25, 65-80, (1998)
[42] Lee, H.; Tanaka, H., Upper and lower approximation models in interval regression using regression quantile techniques, European Journal of Operational Research, 116, 653-666, (1999) · Zbl 1180.62107
[43] Li, B.; Li, C.; Si, J.; Abousleman, G., Interval least-squares filtering with applications to robust video target tracking, (2008 IEEE International Conference on Acoustics, Speech and Signal Processing — Proceedings, (2008), IEEE Signal Processing Society Las Vegas, USA), 3397-3400
[44] Lima Neto, E.deA.; de Carvalho, F.de A. T., Constrained linear regression models for symbolic interval-valued variables, Computational Statistics and Data Analysis, 54, 333-347, (2010) · Zbl 1464.62055
[45] P. Liu, Study on a speech learning approach based on interval support vector regression, in: Proceedings of 4th International Conference on Computer Science and Education, Nanning, China, 2009, pp. 1009-1012.
[46] Manteuffel, T. A., An interval analysis approach to rank determination in linear least squares problems, SIAM Journal on Scientific and Statistical Computing, 2, 335-348, (1981) · Zbl 0471.65022
[47] Markov, S. M., Least squares approximations under interval input data, (Ullrich, C., Contributions to Computer Arithmetic and Self-Validating Numerical Methods, IMACS Annals on Computing and Applied Mathematics, vol. 7, (1990), J.C. Baltzer Scientific Publishing Basel), 133-147 · Zbl 0784.65028
[48] Moore, R. E.; Kearfott, R. B.; Cloud, M. J., Introduction to interval analysis, (2009), SIAM Philadelphia, USA · Zbl 1168.65002
[49] Moral-Arce, I.; Rodríguez-Póo, J. M.; Sperlich, S., Low dimensional semiparametric estimation in a censored regression model, Journal of Multivariate Analysis, 102, 118-129, (2011) · Zbl 1206.62075
[50] Nasrabadi, E.; Hashemi, S., Robust fuzzy regression analysis using neural networks, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 16, 579-598, (2008) · Zbl 1151.62337
[51] A. Neumaier, Linear interval equations, in: Proceedings of International Symposium on Interval Mathematics, Freiburg, Germany, 1985, 109-120.
[52] Neumaier, A., Interval methods for systems of equations, (1990), Cambridge University Press UK · Zbl 0706.15009
[53] Ning, S.; Kearfott, R. B., A comparison of some methods for solving linear interval equations, SIAM Journal on Numerical Analysis, 34, 1289-1305, (1997) · Zbl 0889.65022
[54] Odifreddi, P., Classical recursion theory, (1992), Elsevier Amsterdam, Netherlands · Zbl 0931.03057
[55] Pan, W.; Chappell, R., Computation of the NPMLE of distribution functions for interval censored and truncated data with applications to the Cox model, Computational Statistics and Data Analysis, 28, 33-50, (1998) · Zbl 1042.62614
[56] Papadimitriou, C., Computational complexity, (1995), Addison-Wesley Longman · Zbl 0557.68033
[57] Popova, E. D., Parametric interval linear solver, Numerical Algorithms, 37, 345-356, (2004) · Zbl 1074.65044
[58] Popova, E. D., Webcomputing service framework, International Journal on Information Theories and Applications, 13, 246-254, (2006)
[59] Popova, E. D., Solving linear systems whose input data are rational functions of interval parameters, Lecture Notes in Computer Science, 4310, (2007), Springer Germany · Zbl 1137.65334
[60] Renegar, J., On the computational complexity and geometry of the first-order theory of the reals. part I: introduction. preliminaries. the geometry of semi-algebraic sets. the decision problem for the existential theory of the reals, Journal of Symbolic Computation, 13, 255-299, (1992) · Zbl 0763.68042
[61] Renegar, J., On the computational complexity and geometry of the first-order theory of the reals. part II: the general decision problem. preliminaries for quantifier elimination, Journal of Symbolic Computation, 13, 301-327, (1992) · Zbl 0763.68043
[62] Renegar, J., On the computational complexity and geometry of the first-order theory of the reals. part III: quantifier elimination, Journal of Symbolic Computation, 13, 329-352, (1992) · Zbl 0798.68073
[63] J. Rohn, A Handbook of Results on Interval Linear Problems, Czech Academy of Sciences, Prague, Czech Republic, 2005. <http://uivtx.cs.cas.cz/∼rohn/handbook/handbook.zip>.
[64] Rohn, J., Enclosing solutions of overdetermined systems of linear interval equations, Reliable Computing, 2, 167-171, (1996) · Zbl 0855.65037
[65] Rohn, J., Systems of linear interval equations, Linear Algebra and its Applications, 126C, 39-78, (1989) · Zbl 0712.65029
[66] J. Rohn, VERSOFT: Verification Software in MATLAB/ INTLAB, Version 10, 2009. <http://uivtx.cs.cas.cz/∼rohn/matlab/>.
[67] Rump, S. M., INTLAB — interval laboratory, (Csendes, T., Developments in Reliable Computing, (1999), Kluwer Academic Publishers. Dordrecht), 77-104,, <http://www.ti3.tu-harburg.de/rump/> · Zbl 0949.65046
[68] H. Schneeweiss, J. Komlos, Probabilistic Rounding and Sheppard’s Correction, Technical Report 45, Department of Statistics, University of Munich, 2008. <http://epub.ub.uni-muenchen.de/8661/1/tr045.pdf>. · Zbl 1220.62090
[69] Schön, S.; Kutterer, H., Using zonotopes for overestimation-free interval least-squares—some geodetic applications, Reliable Computing, 11, 137-155, (2005) · Zbl 1073.65034
[70] Schrijver, A., Theory of linear and integer programming, (2000), Wiley USA
[71] Sugihara, K.; Ishii, H.; Tanaka, H., Interval priorities in AHP by interval regression analysis, European Journal of Operational Research, 158, 745-754, (2004) · Zbl 1056.90093
[72] H. Tanaka, H. Lee, Fuzzy linear regression combining central tendency and possibilistic properties, in: Proceedings of the Sixth IEEE International Conference on Fuzzy Systems 1, Barcelona, Spain, 1997, pp. 63-68.
[73] Tanaka, H.; Lee, H., Interval regression analysis by quadratic programming approach, IEEE Transactions on Fuzzy Systems, 6, 473-481, (1998)
[74] Tanaka, H.; Watada, J., Possibilistic linear systems and their application to the linear regression model, Fuzzy Sets and Systems, 27, 275-289, (1988) · Zbl 0662.93066
[75] Tarski, A., A decision method for elementary algebra and geometry, (1951), University of California Press Berkeley, USA · Zbl 0044.25102
[76] Zhang, X.; Sun, J., Regression analysis of clustered interval-censored failure time data with informative cluster size, Computational Statistics and Data Analysis, 54, 1817-1823, (2010) · Zbl 1284.62610
[77] Ziegler, G., Lectures on polytopes, (2004), Springer Germany
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.