Ktisis Cyprus University of Technologyhttps://ktisis.cut.ac.cyThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Sun, 25 Jul 2021 23:20:56 GMT2021-07-25T23:20:56Z50121Branch-and-bound algorithms for computing the best-subset regression modelshttps://ktisis.cut.ac.cy/handle/10488/6766Title: Branch-and-bound algorithms for computing the best-subset regression models
Authors: Gatu, Cristian; Kontoghiorghes, Erricos John
Abstract: An efficient branch-and-bound algorithm for computing the best-subset regression models is proposed. The algorithm avoids the computation of the whole regression tree that generates all possible subset models. It is formally shown that if the branch-and-bound test holds, then the current subtree together with its right-hand side subtrees are cut. This reduces significantly the computational burden of the proposed algorithm when compared to an existing leaps-and-bounds method which generates two trees. Specifically, the proposed algorithm, which is based on orthogonal transformations, outperforms by O(n 3) the leaps-and-bounds strategy. The criteria used in identifying the best subsets are based on monotone functions of the residual sum of squares (RSS) such as R 2, adjusted R 2, mean square error of prediction, and C p. Strategies and heuristics that improve the computational performance of the proposed algorithm are investigated. A computationally efficient heuristic version of the branch-and-bound strategy which decides to cut subtrees using a tolerance parameter is proposed. The heuristic algorithm derives models close to the best ones. However, it is shown analytically that the relative error of the RSS, and consequently the corresponding statistic, of the computed subsets is smaller than the value of the tolerance parameter which lies between zero and one. Computational results and experiments on random and real data are presented and analyzed.
Wed, 01 Mar 2006 00:00:00 GMThttps://ktisis.cut.ac.cy/handle/10488/67662006-03-01T00:00:00ZEstimating all possible sur models with permuted exogenous data matrices derived from a var processhttps://ktisis.cut.ac.cy/handle/10488/6740Title: Estimating all possible sur models with permuted exogenous data matrices derived from a var process
Authors: Gatu, Cristian; Kontoghiorghes, Erricos John
Abstract: The Vector Autoregressive (VAR) process with zero coefficient constraints can be formulated as a Seemingly Unrelated Regressions (SUR) model. Within the context of subset VAR model selection a computationally efficient strategy to generate and estimate all G ! SUR models when permuting the exogenous data matrices is proposed, where G is the number of the regression equations. The combinatorial algorithm is based on orthogonal transformations, exploits the particular structure of the modified models and avoids the estimation of these models afresh by utilizing previous computation. Theoretical measurements of complexity are derived to prove the efficiency of the proposed algorithm.
Mon, 01 May 2006 00:00:00 GMThttps://ktisis.cut.ac.cy/handle/10488/67402006-05-01T00:00:00ZlmSubsets: Exact Variable-Subset Selection in Linear Regression for Rhttps://ktisis.cut.ac.cy/handle/10488/19427Title: lmSubsets: Exact Variable-Subset Selection in Linear Regression for R
Authors: Hofmann, Marc; Gatu, Cristian; Kontoghiorghes, Erricos John; Colubi, Ana; Zeileis, Achim
Abstract: An R package for computing the all-subsets regression problem is presented. The proposed algorithms are based on computational strategies recently developed. A novel algorithm for the best-subset regression problem selects subset models based on a pre-determined criterion. The package user can choose from exact and from approximation algorithms. The core of the package is written in C++ and provides an efficient implementation of all the underlying numerical computations. A case study and benchmark results illustrate the usage and the computational efficiency of the package.
Wed, 01 Apr 2020 00:00:00 GMThttps://ktisis.cut.ac.cy/handle/10488/194272020-04-01T00:00:00ZAn exact least trimmed squares algorithm for a range of coverage valueshttps://ktisis.cut.ac.cy/handle/10488/6712Title: An exact least trimmed squares algorithm for a range of coverage values
Authors: Hofmann, Marc H.; Gatu, Cristian; Kontoghiorghes, Erricos John
Abstract: A new algorithm to solve exact least trimmed squares (LTS) regression is presented. The adding row algorithm (ARA) extends existing methods that compute the LTS estimator for a given coverage. It employs a tree-based strategy to compute a set of LTS regressors for a range of coverage values. Thus, prior knowledge of the optimal coverage is not required. New nodes in the regression tree are generated by updating the QR decomposition of the data matrix after adding one observation to the regression model. The ARA is enhanced by employing a branch and bound strategy. The branch and bound algorithm is an exhaustive algorithm that uses a cutting test to prune nonoptimal subtrees. It significantly improves over the ARA in computational performance. Observation preordering throughout the traversal of the regression tree is investigated. A computationally efficient and numerically stable calculation of the bounds using Givens rotations is designed around the QR decomposition, avoiding the need to explicitly update the triangular factor when an observation is added. This reduces the overall computational load of the preordering device by approximately half. A solution is proposed to allow preordering when the model is underdetermined. It employs pseudo-orthogonal rotations to downdate the QR decomposition. The strategies are illustrated by example. Experimental results confirm the computational efficiency of the proposed algorithms. Supplemental materials (R package and formal proofs) are available online
Fri, 01 Jan 2010 00:00:00 GMThttps://ktisis.cut.ac.cy/handle/10488/67122010-01-01T00:00:00ZA graph approach to generate all possible regression submodelshttps://ktisis.cut.ac.cy/handle/10488/6743Title: A graph approach to generate all possible regression submodels
Authors: Gatu, Cristian; Yanev, Petko I.; Kontoghiorghes, Erricos John
Abstract: A regression graph to enumerate and evaluate all possible subset regression models is introduced. The graph is a generalization of a regression tree. All the spanning trees of the graph are minimum spanning trees and provide an optimal computational procedure for generating all possible submodels. Each minimum spanning tree has a different structure and characteristics. An adaptation of a branch-and-bound algorithm which computes the best-subset models using the regression graph framework is proposed. Experimental results and comparison with an existing method based on a regression tree are presented and discussed.
Mon, 15 Oct 2007 00:00:00 GMThttps://ktisis.cut.ac.cy/handle/10488/67432007-10-15T00:00:00ZEfficient algorithms for computing the best subset regression models for large-scale problemshttps://ktisis.cut.ac.cy/handle/10488/6744Title: Efficient algorithms for computing the best subset regression models for large-scale problems
Authors: Hofmann, Marc H.; Gatu, Cristian; Kontoghiorghes, Erricos John
Abstract: Several strategies for computing the best subset regression models are proposed. Some of the algorithms are modified versions of existing regression-tree methods, while others are new. The first algorithm selects the best subset models within a given size range. It uses a reduced search space and is found to outperform computationally the existing branch-and-bound algorithm. The properties and computational aspects of the proposed algorithm are discussed in detail. The second new algorithm preorders the variables inside the regression tree. A radius is defined in order to measure the distance of a node from the root of the tree. The algorithm applies the preordering to all nodes which have a smaller distance than a certain radius that is given a priori. An efficient method of preordering the variables is employed. The experimental results indicate that the algorithm performs best when preordering is employed on a radius of between one quarter and one third of the number of variables. The algorithm has been applied with such a radius to tackle large-scale subset-selection problems that are considered to be computationally infeasible by conventional exhaustive-selection methods. A class of new heuristic strategies is also proposed. The most important of these is one that assigns a different tolerance value to each subset model size. This strategy with different kind of tolerances is equivalent to all exhaustive and heuristic subset-selection strategies. In addition the strategy can be used to investigate submodels having noncontiguous size ranges. Its implementation provides a flexible tool for tackling large scale models.
Sat, 15 Sep 2007 00:00:00 GMThttps://ktisis.cut.ac.cy/handle/10488/67442007-09-15T00:00:00ZAn efficient branch-and-bound strategy for subset vector autoregressive model selectionhttps://ktisis.cut.ac.cy/handle/10488/6728Title: An efficient branch-and-bound strategy for subset vector autoregressive model selection
Authors: Gatu, Cristian; Gilli, Manfred H.; Kontoghiorghes, Erricos John
Abstract: A computationally efficient branch-and-bound strategy for finding the subsets of the most statistically significant variables of a vector autoregressive (VAR) model from a given search subspace is proposed. Specifically, the candidate submodels are obtained by deleting columns from the coefficient matrices of the full-specified VAR process. The strategy is based on a regression tree and derives the best-subset VAR models without computing the whole tree. The branch-and-bound cutting test is based on monotone statistical selection criteria which are functions of the determinant of the estimated residual covariance matrix. Experimental results confirm the computational efficiency of the proposed algorithm.
Tue, 01 Jan 2008 00:00:00 GMThttps://ktisis.cut.ac.cy/handle/10488/67282008-01-01T00:00:00ZParallel algorithms for computing all possible subset regression models using the qr decompositionhttps://ktisis.cut.ac.cy/handle/10488/6780Title: Parallel algorithms for computing all possible subset regression models using the qr decomposition
Authors: Gatu, Cristian; Kontoghiorghes, Erricos John
Abstract: Efficient parallel algorithms for computing all possible subset regression models are proposed. The algorithms are based on the dropping columns method that generates a regression tree. The properties of the tree are exploited in order to provide an efficient load balancing which results in no inter-processor communication. Theoretical measures of complexity suggest linear speedup. The parallel algorithms are extended to deal with the general linear and seemingly unrelated regression models. The case where new variables are added to the regression model is also considered. Experimental results on a shared memory machine are presented and analyzed.
Tue, 01 Apr 2003 00:00:00 GMThttps://ktisis.cut.ac.cy/handle/10488/67802003-04-01T00:00:00ZA fast algorithm for non-negativity model selectionhttps://ktisis.cut.ac.cy/handle/10488/9916Title: A fast algorithm for non-negativity model selection
Authors: Gatu, Cristian; Kontoghiorghes, Erricos John
Abstract: An efficient optimization algorithm for identifying the best least squares regression model under the condition of non-negative coefficients is proposed. The algorithm exposits an innovative solution via the unrestricted least squares and is based on the regression tree and branch-and-bound techniques for computing the best subset regression. The aim is to filling a gap in computationally tractable solutions to the non-negative least squares problem and model selection. The proposed method is illustrated with a real dataset. Experimental results on real and artificial random datasets confirm the computational efficacy of the new strategy and demonstrates its ability to solve large model selection problems that are subject to non-negativity constrains.
Tue, 01 Jan 2013 00:00:00 GMThttps://ktisis.cut.ac.cy/handle/10488/99162013-01-01T00:00:00ZEfficient strategies for deriving the subset var modelshttps://ktisis.cut.ac.cy/handle/10488/6773Title: Efficient strategies for deriving the subset var models
Authors: Gatu, Cristian; Kontoghiorghes, Erricos John
Abstract: Algorithms for computing the subset Vector Autoregressive (VAR) models are proposed. These algorithms can be used to choose a subset of the most statistically-significant variables of a VAR model. In such cases, the selection criteria are based on the residual sum of squares or the estimated residual covariance matrix. The VAR model with zero coefficient restrictions is formulated as a Seemingly Unrelated Regressions (SUR) model. Furthermore, the SUR model is transformed into one of smaller size, where the exogenous matrices comprise columns of a triangular matrix. Efficient algorithms which exploit the common columns of the exogenous matrices, sparse structure of the variance-covariance of the disturbances and special properties of the SUR models are investigated. The main computational tool of the selection strategies is the generalized QR decomposition and its modification
Tue, 01 Nov 2005 00:00:00 GMThttps://ktisis.cut.ac.cy/handle/10488/67732005-11-01T00:00:00ZSpecial issue on computational statisticshttps://ktisis.cut.ac.cy/handle/10488/14731Title: Special issue on computational statistics
Authors: Colubi, Ana; Kontoghiorghes, Erricos John; Gatu, Cristian
Sat, 02 Apr 2016 00:00:00 GMThttps://ktisis.cut.ac.cy/handle/10488/147312016-04-02T00:00:00ZA Generalized Singular Value Decomposition Strategy for Estimating the Block Recursive Simultaneous Equations Modelhttps://ktisis.cut.ac.cy/handle/10488/9209Title: A Generalized Singular Value Decomposition Strategy for Estimating the Block Recursive Simultaneous Equations Model
Authors: Cosbuc, Mircea I.; Gatu, Cristian; Colubi, Ana; Kontoghiorghes, Erricos John
Abstract: A new strategy for deriving the three-stage least squares (3SLS) estimator of the simultaneous equations model (SEM) is proposed. The main numerical tool employed is the generalized singular value decomposition. This provides a numerical estimation procedure which can tackle efficiently the particular case when the variance-covariance matrix is singular. The proposed algorithm is further adapted to deal with the special case of the block-recursive SEM. The block diagonal structure of the variance-covariance matrix is exploited in order to reduce significantly the computational burden. Experimental results are presented to illustrate the computational efficiency of the new estimation strategy when compared with the equivalent method that ignores the block-recursive structure of the SEM.
Sun, 01 Oct 2017 00:00:00 GMThttps://ktisis.cut.ac.cy/handle/10488/92092017-10-01T00:00:00Z