Cardinality-Constrained Discrete Optimization for Regression
- We consider a linear regression model for which we assume that some of the observed variables are irrelevant for the prediction. Including the wrong variables in the statistical model can either lead to the problem of having too little information to properly estimate the statistic of interest, or having too much information and consequently describing fictitious connections. This thesis considers discrete optimization to conduct a variable selection. In light of this, the subset selection regression method is analyzed. The approach gained a lot of interest in recent years due to its promising predictive performance. A major challenge associated with the subset selection regression is the computational difficulty. In this thesis, we propose several improvements for the efficiency of the method. Novel bounds on the coefficients of the subset selection regression are developed, which help to tighten the relaxation of the associated mixed-integer program, which relies on a Big-M formulation. Moreover, a novel mixed-integer linear formulation for the subset selection regression based on a bilevel optimization reformulation is proposed. Finally, it is shown that the perspective formulation of the subset selection regression is equivalent to a state-of-the-art binary formulation. We use this insight to develop novel bounds for the subset selection regression problem, which show to be highly effective in combination with the proposed linear formulation. In the second part of this thesis, we examine the statistical conception of the subset selection regression and conclude that it is misaligned with its intention. The subset selection regression uses the training error to decide on which variables to select. The approach conducts the validation on the training data, which oftentimes is not a good estimate of the prediction error. Hence, it requires a predetermined cardinality bound. Instead, we propose to select variables with respect to the cross-validation value. The process is formulated as a mixed-integer program with the sparsity becoming subject of the optimization. Usually, a cross-validation is used to select the best model out of a few options. With the proposed program the best model out of all possible models is selected. Since the cross-validation is a much better estimate of the prediction error, the model can select the best sparsity itself. The thesis is concluded with an extensive simulation study which provides evidence that discrete optimization can be used to produce highly valuable predictive models with the cross-validation subset selection regression almost always producing the best results.
- Wir betrachten ein lineares Regressionsmodell, für das wir annehmen, dass einige der beobachteten Variablen für die Vorhersage irrelevant sind. Das Einbeziehen der falschen Variablen in das statistische Modell kann entweder zu dem Problem führen, zu wenig Informationen zu haben, um die interessierende Statistik richtig abzuschätzen, oder zu viel Informationen zu haben und folglich fiktive Zusammenhänge zu beschreiben. In dieser Arbeit wird die diskrete Optimierung zur Durchführung einer Variablenauswahl untersucht. Vor diesem Hintergrund wird die Subset Selection Regression analysiert. Der Ansatz stieß in den letzten Jahren aufgrund seiner vielversprechenden Vorhersagequalität auf großes Interesse. Eine große Herausforderung im Zusammenhang mit der Subset Selection Regression ist die Rechenkomplexität. In dieser Arbeit schlagen wir verschiedene Ansätze zur Verbesserung der Effizienz der Methode vor. Es werden neue Schranken für die Koeffizienten der Subset Selection Regression entwickelt, die dazu beitragen, die Relaxierung des zugehörigen gemischt-ganzzahligen Programms zu verbessern, das auf einer Big-M Formulierung beruht. Darüber hinaus wird eine neuartige gemischt-ganzzahlige lineare Formulierung für die Subset Selection Regression auf der Grundlage einer Bilevel-Optimierungsreformulierung vorgeschlagen. Schließlich wird gezeigt, dass die perspektivische Formulierung der Subset Selection Regression äquivalent zu einer Binärformulierung des Problems ist. Wir verwenden diese Erkenntnis, um neue Schnittebenen für die Subset Selection Regression zu entwickeln, die sich in Kombination mit der vorgeschlagenen linearen Formulierung als besonders wirksam erweisen. Im zweiten Teil dieser Arbeit untersuchen wir die statistische Intention der Subset Selection Regression und folgern, dass die Methode nicht gänzlich mit der Grundidee übereinstimmt. Die Subset Selection Regression entscheidet anhand des Trainingsfehlers, welche Variablen ausgewählt werden sollen. Mit diesem Ansatz wird der Validierungsprozess auf den Trainingsdaten durchgeführt, was häufig keine gute Schätzung des Vorhersagefehlers ist. Daher ist eine vorgegebene Kardinalitätsgrenze erforderlich. Stattdessen schlagen wir vor, Variablen in Bezug auf den Kreuzvalidierungswert auszuwählen. Der Prozess ist als ein gemischt-ganzzahliges Programm formuliert, wobei der Grad der Dünnbesetztheit Teil der Optimierung wird. Normalerweise verwendet man eine Kreuzvalidierung, um aus einigen vorausgewählten Modellen das beste auszuwählen. Mit dem vorgeschlagenen Programm wird das beste Modell aus allen möglichen Modellen ausgewählt. Da die Kreuzvalidierung eine viel bessere Schätzung des Vorhersagefehlers darstellt, kann das Modell die beste Kardinalität selbst auswählen. Die Arbeit wird mit einer umfangreichen Simulationsstudie abgeschlossen, die aufzeigt, dass mit diskreter Optimierung wirksame Vorhersagemodelle bestimmt werden können, wobei die Subset Selection Regression basierend auf der Kreuzvalidierung fast immer die besten Ergebnisse erzielt.
Author: | Dennis Kreber |
---|---|
URN: | urn:nbn:de:hbz:385-1-12094 |
DOI: | https://doi.org/10.25353/ubtr-xxxx-5723-2109 |
Referee: | Sven de Vries, Jan Pablo Burgard, Christoph Buchheim |
Advisor: | Sven de Vries, Jan Pablo Burgard |
Document Type: | Doctoral Thesis |
Language: | English |
Date of completion: | 2019/07/26 |
Publishing institution: | Universität Trier |
Granting institution: | Universität Trier, Fachbereich 4 |
Date of final exam: | 2019/03/26 |
Release Date: | 2019/08/20 |
Tag: | Discrete optimization; Mixed-integer optimization; Prediction; Regression; Subset Selection |
GND Keyword: | Maschinelles Lernen; Optimierung; Regressionsanalyse |
Institutes: | Fachbereich 4 |
Dewey Decimal Classification: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
Licence (German): | CC BY: Creative-Commons-Lizenz 4.0 International |