Lade Inhalt...

Datenbasierte Optimierung, R Programmierung und Anwendung

Ein inexaktes Newton-Verfahren für die LASSO-Regression

Hausarbeit 2017 29 Seiten

Zusammenfassung

Dieser Beitrag widmet sich der datenbasierten Optimierung und deren konkreten Anwendung. Für diesen Zweck wird eine Lösungsmethode aufgestellt, in der die Pseudo-Huber-Regularisierung, die inexakte Newton-Methode, das GMRES Verfahren und die Armijo-Regel angewandt werden.

Ziel dabei ist, die Leistung einer Lösungsmethode auf Basis der inexakten Newton-Verfahren für die LASSO-Regression anhand einer Programmiersequenz in R zu implementieren und zu bewerten.

Leseprobe

Inhaltsverzeichnis

Inhaltsverzeichnis

1 Einleitung

2 LASSO-Regression
2.1 Grundlagen
2.2 Über die Methode der kleinsten Quadrate hinaus
2.3 Formulierung einer Lasso-Regression

3 Eine Newton-GMRES Methode für die LASSO-Regression
3.1 Newton-GMRES-verfahren
3.2 Das Schrittweitenverfahren von Armijo

4 Implementierung der Lösungsmethode
4.1 Datensätze und experimentelle Parameter
4.2 R-Programmierung, Bibliotheken (linear algebra) und R Packages

5 Auswertung der Ergebnisse
5.1 Verifikation
5.2 Auswertung der Genauigkeit
5.3 Auswertung der Ausführungszeit

6 Zusammenfassung und Ausblick

Literaturverzeichnis

1 Einleitung

Die statistische Analyse von Datensätzen ermöglicht die Gewinnung von Erkenntnissen und ist ein empirisches Instrument zur Untersuchung von diversen Sachverhalten. Das Wissen, welches durch Datenanalyse erhalten wird, treibt die Wissenschaft und das Ingenieurwesen voran. 1

In dem Wirtschafts- und Finanzbereich erlaubt die statistische Analyse fundierte Ent­scheidungen auf der Grundlage der ausgewerteten Daten zu treffen. Die Macht des Wissens ist heute nach wie vor allgegenwärtig anzutreffen. 2

Mit der Erweiterung und Weitererforschung der Methoden zur Datenanalyse profitiert die Industrie, der Finanzsektor und die Wissenschaft. Als Anwendung der Datenana­lyse sind folgende Beispiele zu erwähnen: 3

- Die Vorhersage der Rückfälligkeit bei einem Herzinfarktpatienten.
- Die Vorhersage eines Aktienpreises auf Basis finanzieller Berichte.
- Datenbasierte Portfoliooptimierung
- Optimierung für maschinelles Lernen
- Krebsrisikoschätzung.

Es stehen bereits viele statistische Methoden zur Verfügung, jedoch nicht alle sind für die Datenanalyse von sehr großen Datensätzen brauchbar. Die Bewältigung von der sogenannten Big Data und deren Herausforderungen ist in diesem Sinne eine sehr wichtige Aufgabe der heutigen statistischen Analyse. 1

Big data beinhaltet Komplexität nicht nur in Hinsicht auf die großen Datenmengen (Volume), sondern auch in Hinsicht auf die strukturierte, semistrukturierte und un­strukturierte Form, in der die Daten vorliegen (Variety). 2 Der kontinuierliche Emp­fang von neuen Daten (Velocity) stellt ebenso neue Anforderungen an die statistische Analyse. 4

Angesichts dieser Komplexität sollten die statistischen Instrumente optimiert werden, um schnellere Erkenntnisse zu gewinnen. Demnach müssen die Algorithmen sowohl konzeptionell, als auch für die Implementierung an Big Data angepasst werden. 2

In diesem Sinne widmet sich dieser Beitrag, der datenbasierte Optimierung und de­ren konkreten Anwendung. Für diesen Zweck wird eine Lösungsmethode aufgestellt, in der die Pseudo-Huber-Regularisierung, die inexakte Newton-Methode, das GMRES- Verfahren und die Armijo-Regel angewandt werden.

Das Ziel dabei ist, die Leistung einer Lösungsmethode auf Basis der inexakten Newton­Verfahren für die LASSO-Regression anhand einer Programmiersequenz in R zu im­plementieren und zu bewerten.

Die erreichte Modellpräzision und CPU-Verarbeitungszeit bei einer bestimmten Da­tenmenge wird dabei als Kriterium für die Auswertung fungieren.

Die Validierung erfolgt, indem die Resultate der selbst implementierten Lösungsmetho­de und die Resultate einer anderen Methode gegenübergestellt werden. Da das Trust­Region-Verfahren in der Literatur als sehr ressourceneffizient erwiesen hat, dient es als Referenz in diesem Beitrag. 5

Um eine inhaltliche Strukturierung vorzunehmen wird die Arbeit in vier Kapitel ein­geteilt.

Das erste Kapitel widmet sich der Regression als mathematisches Konstrukt. Die häu­figsten Anwendungen der Regression und die Problematik der Überanpassung werden in diesem Kapitel ebenfalls ausführlich behandelt. Anschließend wird im zweiten Ka­pitel die LASSO-Regression vorgestellt, wobei auf die Eigenschaften und Schwierigkeit der Lösung der LASSO-Regression eingegangen wird. Im dritten Kapitel wird die Lö­sungsmethode aufgestellt. Dafür werden die Pseudo-Huber-Regularisierung, Newton­Verfahren, GMRES-Verfahren und die Armijo-Regel behandelt. Abschließend werden die Ergebnisse der R-basierte Implementierung und die Ergebnisse des Trust-Region­Verfahrens hinsichtlich die Modellpräzision und CPU-Verarbeitungszeit gegenüberge­stellt.

2 LASSO-Regression

2.1 Grundlagen

Eine der häufigsten statistischen Methoden zur Analyse empirischer Fragenstellungen ist heute nach wie vor die Regressionsanalyse.

Die Methoden zur linearen Regression wurden bereits vor der computerunterstützen Datenverarbeitung behandelt. Dennoch sind sie heute noch ein sehr wichtiges Instru­ment der statistischen Analyse, weil sie adäquate und interpretierbare Input-Output­Zusammenhänge mit relativ geringem Aufwand ermöglichen.

Bei einer linearen Regression handelt sich um eine statistische Modellformulierung. Im Gegensatz zu anderen theoretischen Modellen, die auf der Grundlage physikalischer und mathematischer Gesetzmäßigkeiten zustande kommen, werden die Modellgrößen bei einer linearen Regression geschätzt. 6 Aus dieser Tatsache leitet sich eine wesent­liche Eigenschaft der Regressionsfragestellungen ab. Eine stochastische Komponente ist im Modell, aufgrund von zufälligen Störungen, vorhanden.

Der Zusammenhang zwischen den Zielgrößen yi und den Kovariablen xi ist in einer linearen Regression nicht exakt gegeben, weil er durch zufällige Störungen überlagert wird. Die Zielgröße y ist also eine Zufallsvariable, deren Verteilung von den Regresso- ren abhängt. 7

Das mathematische Konstrukt eines linearen Regressionsmodells ist: 8

Abbildung in dieser Leseprobe nicht enthalten

Hierbei bezeichnet xi=(xi,1,xi,2,xi,p)T die Regressoren, ß = (ß1,ß2,ß3, •••,ßp)T die Re­gressionskoeffizienten und yi die Zielgröße bzw. die Zielvariable der i-ten Beobachtung. In der Matrixform wird ein lineares Regressionmodell wie folgt notiert. 7

Abbildung in dieser Leseprobe nicht enthalten

Eine sehr wichtige Annahme der linearen Regression ist logischerweise die Lineari­tät der geschätzten Funktion. Es wird also davon ausgegangen, dass die erklärenden Variablen linear in das Modell eingehen oder dass ein lineares Modell eine gute Ap­proximation des betrachteten Problems ist. 3 "Das lineare Regressionsmodell ist ins­besondere dann sinnvoll einsetzbar, wenn die Zielvariable y steigt und wenn möglich approximativ normalverteilt ist". 7

Bei £ handet sich um die zufällige Störgröße, welche die stochastische Komponete des Modells wiederspiegeln. Sie ist als zufällige nicht von den Regressoren erklärte Abwei­chung zu interpretieren. 7

2.2 Über die Methode der kleinsten Quadrate hinaus

Eine der gängigsten Methoden zur Lösung einer linearen Regression ist die Methode der kleinsten Quadrate, deren Erfindung auf Legendre und Gauß bereits in 18. Jahr­hundert zurückzuführen ist. 7 Die Methode bietet aus zwei verschiedenen Gründen keine zufriedenstellenden Ergebnisse. 3

Der erste Grund ist die resultierende Präzision der Prognose. Die Schätzung durch die Methode der kleinsten Quadrate hat eine niedrige Verzerrung (Bias) aber eine sehr große Varianz. Die Präzision der Prognose kann durch Schrumpfung1 verbessert wer­den. Hierbei wird das Bias etwas erhöht, um die Varianz der Prognosen zu reduzieren, was zur einer besseren Präzision der gesamten Prognose führt. 3

Der zweite Grund ist, dass mit der Methode der kleinsten Quadrate eine große Anzahl an Regressoren geschätzt wird, was die Interpretation erheblich erschwert. 3

Eine sinnvolle Regressionsanalyse ist nur dann nachvollziehbar und übersichtlich, wenn in die Regressionsmodellierung nur die Variablen aufgenommen werden, deren Be­deutsamkeit aus analytischen oder theoretischen Prinzipien abgeleitet werden kann. 6 Demzufolge ist es erwünscht auf einige Regressoren zu verzichten, um die Inter- pretierbarkeit des Modells zu verbessern und ein besseres Verständnis der wichtigsten Zusammenhänge zu erhalten. 3

Als Konsequenz einer sehr großen Anzahl an Regressoren tritt die Überanpassung auf, weil das geschätzte Modell irrelevante Regressoren enthält. 9 Die resultierende Spe­zifität des geschätzten Modells ist so hoch, dass die Prognosen die zufällige Streuung wiederspiegeln. Ein Modell, welches mit Überanpassung behaftet ist, ist keine gute Grundlage für die Vorhersage neuer Beobachtungen. 10

Da die Mehode der kleinsten Quadrate nicht immer zu einer verlässlichen Progno­
se führt, wurden zwei Methoden entwickelt, deren Ziel es ist, die Interpretierbarkeit und Vorhersagegenauigkeit zu verbessern. Diese sind die Variablenselektion2 und die Schrumpfung von Parametern. 10

In der Variablenselektion wird nur eine Gruppe von Regressoren behalten. Die ir­relevanten Regressoren werden verworfen. Diese Vorgehensweise verbessert zwar die Interpretierbarkeit und die Präsizion der Prognose, aber sie impliziert einen diskreten Prozess. Demzufolge wird die Präzision des gesamten Modells nur marginal verbessert.

Die Schrumpfung von Parametern ist eine statistische Schätzungsmethode, welche die Regressionskoeffizienten durch eine l1 oder l2 Penalisation in Richtung Ursprung treibt. 10 Sie stellt keinen diskreten Prozess wie die Variablenselektion dar, stattdessen be­sitzt sie einen kontinuierlichen Charakter.3

2.3 Formulierung einer Lasso-Regression

Gegeben ist eine lineare Regression mit den Regressoren und Zielgrößen y für i = 1,2,...,N. Die Lasso-Regression (Least absolute schrinkange and selection opera­tors) stellt ein li penaliziertes Regressionsproblem dar, in dem die Regressionskoeffi­zienten ß über die Minimierung der Lasso-Schätzung (ßlasso) ermittelt werden. Diese Minimierung lässt sich in der folgenden Lagrange-Form ausdrücken. 3

Abbildung in dieser Leseprobe nicht enthalten

Dieser matematischer Ausdruck besteht aus der Summe der Quadrate und einer Re­striktion der Form X! \ßj\ < s, welcher die l1 Penalisierung beinhaltet. Die Ridge- Regression hat eine ähnliche Formulierung, wobei die Restriktion Xj ß2 < t. berück­sichtigt wird. 11

Abbildung in dieser Leseprobe nicht enthalten

Hier ist A die Designmatrix, b der Vektor der Zielgröße und x der Verktor der Re- gressionskoeffizien. Da die Schätzung X gesucht wird, wird im weiteren Verlauf diese Notierung verwendet.

Aufgrund der Form der l1 Penalisierung wird durch die Lasso-Regression nicht nur eine Schätzung der Regressionskoeffizienten, sondern auch eine Variablenselektion vor­genommen. 11

Das ist logisch nachvollziehbar, wenn die graphische Interpretation einer l1 Regulari­zation batrachtet wird. Die Abbildung 2.1 zeigt die Lasso- und die Ridge-Regression bei zwei Parametern. "Die RSS3 hat eliptische Höhenlinien, die um den Punkt der kleinsten-Quadrate-Schätzung (ß) herum verlaufen. Der zulässige Bereich, der von der Restriktion definiert ist, bildet in dem Fall der Ridge-Regression einen Kreis ß1 + ß| < t. Bei der Lasso-Regression hat der Zulässigkeitsbereich die Form eines Diamanten |ßi| + |ß2| < t. Beide Methoden finden ein Optimum in dem Punkt, in dem die Höhenlinien den zulässigen Bereich treffen. Durch den diamantförmigen Zu­lässigkeitsbereich bei der Lasso-Regression, ist es möglich, dass die Lösung in einer Ecke stattfindet. Wenn das passiert, ist der respektive Regressionskoeffizient ßj gleich null. Bei einem größeren Modell mit p > 2 nimmt der Zulässigkeitsbereich die Form eines Rhomboids mit sehr vielen Ecken und Kanten ein. Dies ermöglich die Selekti­on der wichtigsten Variablen."3 Obwohl die Ridge-Regression einem kontinuierlichen

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Schätzungsbild für Lasso- (links) und Ridge-Regression (rechts)3

Selektionprozess dient, ist es durch die l2 Penalisation so, dass die Regressionskoeffi­zienten nicht unbedingt null gesetzt werden, was die Interpretierbarkeit des Modells erschwert. Demgegenüber ist die Lasso-Regression ein Kompromiss, weil sie die posi­tiven Eigenschaften der Variablenselektion und der Ridge-Regression aufweist. Diese Methode reduziert weitestgehend die Regressionkoeffizienten und setzt irrelevante Re­gressionskoeffizienten gleich null. 8

3 Eine Newton-GMRES Methode für die LASSO-Regression

Die Lösung der LASSO-Regression hat sehr viel Interesse im Bereich des maschinellen Learnings geweckt und ist heute ein gut erforschtes Thema.

Als mögliche Lösung der LASSO-Regression wird in der Literatur auf den Least-Angle- Regressions Algorithmus (LARS) verwiesen. LARS ist ein Selektionsalgorithmus, wel­cher mit einer einfachen Modifizierung, die Implementierung einer LASSO-Regression ermöglicht. 13

Das LASSO-Problem kann dennoch als ein nicht lineares Optimierungsproblem be­trachtet werden. Eine Lösung kann daher durch Methoden erster oder zweiter Ordnung bestimmt werden.

Während die Methoden zweiter Ordnung eine zweite Differentiation benötigen, ist bei den Methoden erster Ordnung nur die Ermittlung der ersten Ableitung erforderlich. 14 Da in diesem Beitrag der Fokus auf eine Methode zweiter Ordnung über das inexakte Newton Verfahren liegt, müssen die erste und zweite Ableitung des bereits formulierten LASSO-Problems aufgestellt werden.

Die Nichtdifferenzierbarkeit der li Penalisation hindert die direkte Anwendung des inexakten Newton Verfahren. Daher ist eine Approximation der li-Norm durch eine Glättungsfunktion erforderlich. Bei den Lösungsmethoden erster Ordnung wird die li-Norm durch die Hubert-Penalisierung ][]m=l ^ß(x{) ersetzt, indem ß(x^ wie folgt er­mittelt wird. 15

Abbildung in dieser Leseprobe nicht enthalten

Je kleiner der Parameter ß der Huber-Funktion ist umso besser ist die Approximation der l1-Norm. Die Huber-Funktion kann nur einmal abgeleitet werden. Aus diesem Grund kann die gegebene Hubert-Funktion für eine Methode der zweiten Ordnung nicht verwendet werden. Stattdessen wird die Pseudo-Huber-Funktion verwendet, weil die Ableitung in allen Graden ermittelt werden kann. Die Pseudo-Huber-Funktion wird mit ß > 0 parametrisiert. Deren entsprechende Formel ist 15:

Abbildung in dieser Leseprobe nicht enthalten

Eine Gegenüberstellung zwischen Huber- und Pseudo-Hubert-Funktion kann anhand folgender Abbildung vorgenommen werden. In der linken Grafik wird die Qualität der Approximation der beiden Funktionen bei dem identischen Parameter ß gezeigt. Die Pseudo-Huber-Funktion ist, im Vergleich zu der Huber-Funktion, weiter vom Verlauf der b-Norm entfernt. Dennoch ist der Grad der Näherung durch den Parameter ß ein­stellbar. Die Pseudo-Hubert-Funktion kann also jeden Präzisionsgrad erreichen, wenn der Parameter ß der gewählten Präzision entspricht (siehe Abbildung 3.1 rechts).

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.1: Vergleich der Huber- und Pseudo-Hubert-Funktion [15])

Die erste und die zweite Ableitung der Pseudo-Hubert-Funktion werden der folgenden Form aufgestellt 15:

Abbildung in dieser Leseprobe nicht enthalten

Wenn die Pseudo-Hubert-Funktion in die bereits formulierte LASSO-Regression ein­gesetzt wird, wird folgender Ausdruck erhalten:

Abbildung in dieser Leseprobe nicht enthalten

Daraus folgt die erste und zweite Differentiation.

Abbildung in dieser Leseprobe nicht enthalten

[...]


1 engl. Schrinkage

2 engl. Subset selection

3 engl. residual sum of squares

Details

Seiten
29
Jahr
2017
ISBN (eBook)
9783346471505
ISBN (Paperback)
9783346471512
Sprache
Deutsch
Institution / Hochschule
Technische Universität Ilmenau
Erscheinungsdatum
2021 (August)
Note
1,3
Schlagworte
inexaktes Newton-Verfahren LASSO-Regression Newton-GMRES-verfahren Schrittweitenverfahren von Armijo

Autor

Zurück

Titel: Datenbasierte Optimierung, R Programmierung und Anwendung