Machine Learning. Basisexpansion und Regularisierung

Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.
Bitte klicken Sie für eine vollständige Ansicht auf das obige Cover.

Inhaltsverzeichnis

1 Einführung ... 1

2 Stückweise Polynome und Splines ... 2
2.1 Natürliche kubische Splines ... 5
2.2 B-Splines ... 6

3 Regularisierung ... 7
3.1 Geglättete Splines ... 7
3.2 Glättungsrnatrix und Anzahl der Freiheitsgrade ... 9
3.3 Der Tradeoff zwischen Bias und Varianz ... 12
3.4 Monotone P-Splines ... 14

4 Anwendungsbeispiele ... 15
4.1 Relative Rechenleistung von Prozessoren ... 15
4.2 Beschleunigungskurve bei Motorradunfällen ... 16

5 Fazit ... 17

1 Einführung

Lineare Modelle erfreuen sich bei quantitativen Analysen, wie beispielsweise in der Ökonometrie, großer Beliebtheit. Die Schätzergebnisse sind nämlich stabil und lassen sich leicht interpretieren. Außerdem lässt sich jedes nichtlineare Regressionsproblem [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] durch eine Taylorapproximation erster Ordnung lokal approximieren und als lineares Modell darstellen. Liegt nur eine kleine Stichprobe vor oder sollen viele Parameter geschätzt werden, kann häufig auch nicht mehr als ein lineares Modell geschätzt werden. In den seltensten Fällen wird jedoch der zugrundeliegende datengenerierende Mechanismus tatsächlich linear in den erklärenden Variablen sein, womit jede lineare Modellierung in einem solchen Fall fehlspezifiziert ist und verzerrte Ergebnisse liefert.

Es existieren nun sehr viele Möglichkeiten für nichtlineare Modelle. Eine beliebte Methode ist, die erklärenden Variablen in X mit nichtlinearen Transformationen g(X) zu erweitern bzw. zu ersetzen und ein Modell zu spezifizieren, das linear in den daraus erhaltenen Variablen ist. Sei [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] Transformation von [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.], dann ist eine lineare Basisexpansion gegeben durch die Modellierung

[Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.]

Der Raum der auf diese Weise modellierbaren Funktionen [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] ist ein Vektorraum, dessen Basis durch die Transformationen [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] gegeben ist. Mit diesem Ansatz lassen sich sehr flexibel verschiedene nichtlineare Einflüsse von X modellieren und mit den üblichen Eigenschaften eines linearen Modells schätzen. Sehr geläufig ist (z.B. bei der Schätzung von Gravitationsmodellen) die Transformation [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] aber auch quadratische oder gemischte Terme werden häufig verwendet: [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] Dies lässt sich beliebig erweitern, beispielsweise mit zusätzlichen Potenzen, um auch Taylorapproximationen höherer Ordnung zu erhalten. Allerdings wächst die Anzahl der zu schätzenden Parameter exponentiell mit dem Grad des Polynoms, weshalb dieses Vorgehen recht bald an seine Grenzen stößt. Polynome dieser Art haben außerdem die Eigenschaft, dass sie zwar eine Funktion lokal relativ gut approximieren können, sich in entfernteren Bereichen allerdings ausgesprochen instabil verhalten und damit in diesen Bereichen nicht mehr für einen Lernprozess geeignet sind. Basisexpansionen lassen sich aber auch verwenden, um global eine flexible Modellierung für f(X) zu erhalten. Stückweise Polynome und Splines sind gängige Verfahren, um die Funktion f(X) lokal durch Polynome zu beschreiben.

Die Menge [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] der hierfür verwendeten Basisfunktionen ist für eine Schätzung typischerweise zu mächtig, weshalb Methoden gebraucht werden, um die Kom­plexität eines Modells, das [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] verwendet, zu reduzieren. Eine Möglichkeit ist, im Voraus die Klasse der möglichen Funktionen zu beschränken, wie das z.B. bei additiven Modellen der Fall ist. Eine andere Möglichkeit besteht darin, nur Basisfunktionen aus [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] zu verwenden, die in der Schätzung signifikanten Einfluss haben. Die ganze Menge [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] zu verwenden, den Koeffizienten dabei allerdings Restriktionen aufzuerlegen, ist eine dritte Möglichkeit.

Diese Methoden gewinnen durch die zunehmende Verfügbarkeit von Daten aller Art immer mehr an Bedeutung. Ziel dieser Arbeit ist, einen Einblick in die Methode der Basisexpansion und deren Regularisierung anhand von stückweisen Polynomen und Splines geben. Inhaltlich basiert diese Arbeit dabei auf Kapitel 5 von Hastie et al. (2009) und beschränkt sich, da es um die Vorstellung einer Methode geht, auf die Darstellung im eindimensionalen Fall.

Diese Arbeit gliedert sich in fünf Abschnitte. Nach der Einleitung werden im zweiten Abschnitt stückweise Polynome und Splines vorgestellt. Der dritte Abschnitt beschäftigt sich mit Regularisierung. Es werden Verfahren vorgestellt, wie Splines geglättet und den Koeffizienten Restriktionen auferlegt werden können, sodass Verläufe wie Monotonie resultieren. Im Anschluss werden in Abschnitt vier zwei Anwendungsbeispiele gegeben. Das Fazit (Abschnitt 5) gibt nochmal eine kurze Zusammenfassung.

2 Stückweise Polynome und Splines

Sei [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.]ein zusammenhängendes Intervall und [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] eine eindimensionale Variable. Eine stückweise polynomiale Funktion f(X) ergibt sich, indem man den Definitionsbereich [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] in zusammenhängende Teilintervalle [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] teilt und [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] separat auf jedem Teilintervall durch ein Polynom darstellt. Die Punkte [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] heißen Knoten und sind neben der Ordnung der Polyno­me entscheidend für die Flexibilität der Anpassung. Als Maß hierfür verwenden wir die Anzahl der zu schätzenden Parameter, welche sich aus der Anzahl der Knoten, dem Grad des Polynoms wie auch bestimmten Restriktionen ergibt. Anzahl der Knoten, Ordnung der lokalen Polynome sowie auferlegte Restriktionen definieren eindeutig einen Vektorraum, dessen Dimension der Anzahl der zu schätzenden Parameter entspricht. Die Dimension dieses Vektorraums ist Maß für die Flexibilität der Anpassung und wir sagen auch, eine Anpassung mit q zu schätzenden Parametern hat q Freiheitsgrade.

Abbildung 1 zeigt stückweise Polynome verschiedenen Grades und mit un­terschiedlichen Restriktionen bezüglich der Kontinuität. Im Bild links oben ist ein stückweises Polynom nullten Grades (stückweise konstant) abgebildet. Mit zwei inneren Knoten [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] werden hierfür drei Basisfunktionen benötigt:

[Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.], wobei [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.]

die Indikatorfunktion ist. Eine Schätzung mit kleinsten Quadraten für [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] liefert Koeffizienten [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.], welche gerade dem Mittelwert [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] der m-ten Region entsprechen.

Erweitert man die Basis um drei weitere Basisfunktionen [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.], ergibt sich eine stückweise lineare Funktion mit sechs Freiheitsgraden (Abbildung 1 oben Mitte), die an den Knoten allerdings noch nicht stetig ist. Stetigkeit an den inneren Knoten und [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] (Abbildung 1 oben rechts) erhält man mit den Restriktionen [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.]. Für den Knoten [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] impliziert dies beispielsweise, dass für die Koeffizienten [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] gelten muss. Anstatt den Parametern lineare Restriktionen aufzuerlegen, kann man auch direkt eine Basis benutzen, welche diese Restriktionen beinhaltet:

[Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.],

wobei [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.]. Anschaulich kann man diese Basis so sehen, dass ab jedem Knoten ein Polynom zusätzlich addiert wird, wobei dieses Polynom eine Nullstelle an dem entsprechenden Knoten hat, damit die resultierende Funktion stetig ist. Durch diese beiden Restriktion erhalten wir sozusagen zwei Parameter zurück, es bleiben damit vier freie Parameter.

Häufig verlangt die Anwendung allerdings eine glattere Anpassung. Dies wird durch eine höhere Ordnung der lokalen Polynome und mit der Restriktion, dass die ersten k Ableitungen an den Knoten stetig sind, erreicht. In der unteren Hälfte von Abbildung 1 sind stückweise kubische Polynome abgebildet. Die angepasste Funktion im linken Bild ist noch nicht stetig und ergibt sich aus einer Basis mit 12 Basisfunktionen:

[Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.]

Lässt man analog zum obigen Fall die konstanten Basisfunktionen der an den Knoten hinzukommenden Polynome (hier sind das [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.]) weg, ergibt sich damit eine kubische Anpassung, die an den inneren Knoten keine Sprungstellen mehr aufweist (mittleres Bild). Entfernt man zusätzlich die linearen Terme ([Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.]), resultiert eine Anpassung mit stetiger erster Ableitung (rechtes Bild), da die Ableitung der hinzukommenden Polynome an den jeweiligen Knoten eine Nullstelle haben.

Soll auch die zweite Ableitung stetig sein, reduziert sich für unseren kubischen Fall mit zwei inneren Knoten die Basis damit ganz analog auf sechs Basisfunktionen:

[Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.]

Eine solche Funktion nennt man auch kubischen Spline. Würde man hier noch einen höheren Grad an Kontinuität fordern, erhielte man ein globales kubisches Polynom. Allgemein ist ein Spline M-ter Ordnung mit inneren Knoten [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] ein stückweises Polynom M-ter Ordnung, dessen Ableitungen bis zur Ordnung M — 2 an den Knoten stetig sind. Eine Basis für einen solchen Spline ist gegeben durch:

[Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.]

womit der Vektorraum für Splines der Ordnung M und mit K Knoten M + K Dimensionen hat.

2.1 Natürliche kubische Splines

Polynome, die beispielsweise mit kleinsten Quadraten an Daten angepasst werden, verhalten sich an den Rändern meist sehr unkontrolliert. Vorhersagen, die außerhalb dieser Grenzen liegen, führen darum tendenziell in die Irre. Bei Splines verstärkt sich dieser Effekt nochmals, was recht anschaulich anhand der punktweisen Varianz einer Anpassung mittels kleinster Quadrate gezeigt werden kann. Abbildung 2 zeigt einen Vergleich für die punktweise Varianz der gefitteten Kurve für verschiedene Modelle. Für das lineare Modell ist diese Varianz fast überall am geringsten und steigt auch an den Rändern nur sehr wenig an. Im Fall der höheren Polynome ist deutlich erkennbar, wie die Varianz an den Rändern stark ansteigt und für den kubischen Spline nahezu explodiert.

Natürliche kubische Splines beinhalten aus diesem Grund zusätzliche Re­striktionen, und zwar, dass die Funktion über die Ränder hinaus linear ist. Geht man von der allgemeinen Basis (1) eines kubischen Splines, also von der Modellierung

[Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.]

aus, und wendet dann die Randbedingungen für natürliche kubische Splines [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] an, ergeben sich daraus vier lineare Restriktionen, wodurch sich die Basis auf die K Basisfunktionen

[Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.]

reduziert.¹

Zwar führt eine Modellierung mit natürlichen kubischen Splines an den Rändern durch diese zusätzlichen Restriktionen zu Verzerrungen, was allerdings angesichts der Tatsache, dass an den Rändern weniger Information vorliegt, nicht so stark ins Gewicht fällt wie die explodierende Varianz. Ein positiver Nebeneffekt ist die Freigabe weiterer vier Parameter; diese können für zusätzliche Knoten im inneren Bereich, wo dichtere Information vorliegt, verwendet werden.

2.2 B-Splines

Die bisher vorgestellten (sogenannten truncated-power-) Basen sind zwar intuitiv und lassen sich außerdem einfach berechnen, in der numerischen Praxis erweisen sie sich jedoch als nicht so günstig. Anschaulich gesprochen wird nämlich jede Basisfunktion „bis zum Ende mitgeschleppt“ und die Potenzen von großen Zahlen können dann schnell zu Rundungsfehlern führen. Für jeden Vektorraum gibt es jedoch eine unendlich große Menge von Basen, die diesen Vektorraum erzeugen. Attraktiv wäre also eine Basis, die numerisch stabil und effizient zu berechnen ist. Diese Eigenschaften werden von der D-Spline-Basis erfüllt, welche aus diesem Grund breite Anwendung erfährt.

Seien [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] Randknoten und [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] innere Knoten. Für einen B-Spline der Ordnung M definieren wir nun eine erweiterte Knotensequenz [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] durch

[Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.]

Die Werte für die zusätzlichen Knoten außerhalb der Randknoten sind unerheblich und werden üblicherweise mit den Randknoten gleichgesetzt.

Bezeichne nun [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] die [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] B-Spline-Basisfunktion mit Ordnung [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] zur Knotensequenz [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.]. Diese ergeben sich rekursiv über das Schema der dividierten Differenzen durch [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] Da nicht ausgeschlossen ist, dass Knoten auch doppelt vorkommen können, und damit in der Rekursionsformel Divisionen durch Null auftreten können, besteht hier Konvention, dass in einem solchen Fall [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] mit Induktion gilt, dass [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.].

Abbildung 3 zeigt B-Spline-Basisfunktionen bis zur vierten Ordnung auf dem Einheitsintervall mit elf gleichmäßig verteilten Knoten. Die Basisfunktionen sind allesamt nicht-negativ, ergeben in der Summe stets 1 und besitzen einen kompakten Träger, d.h. sie sind nur auf einem beschränkten Teilintervall von Null [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] verschieden. Dies hat Vorteile für die numerische Praxis, die resultierende Funktion ergibt sich nämlich lokal aus einer gewichteten Summe weniger Basisfunktionen, somit werden nicht alle Basisfunktionen „mitgeschleppt“.

Wir verwenden aufgrund dieser Vorzüge in den folgenden Abschnitten aus­schließlich B-Splines, obwohl die vorgestellten Regularisierungsverfahren genauso auch für natürliche Splines und sonstige Kurven anwendbar sind.

3 Regularisierung

Eine zentrale Frage bei der Verwendung von Splines ist, wie groß der Grad der Anpassungsflexibilität (Freiheitsgrade) zu wählen ist. Bisher haben wir das über die Anzahl der Knoten und die Ordnung der Basisfunktionen kontrolliert. Stan­dardmäßig finden jedoch hauptsächlich kubische Basisfunktionen Anwendung, da diese hinreichend glatt für die meisten Anwendungen sind. Es bleibt also die Frage, wie viele Knoten verwendet werden sollen. In Abbildung 4 sind Daten, die mit der violetten Funktion generiert wurden, abgebildet. An diese Daten wurden Kurven mit verschiedener Anzahl an Knoten angepasst. Offenbar ist ein innerer Knoten (entspricht fünf ² Freiheitsgraden) zu restriktiv, da mit zwei in­neren Knoten (sechs Freiheitsgrade) zu den gleichen Daten eine weniger verzerrte Anpassung erreicht werden kann. Werden mehr Knoten verwendet, wird die gefittete Kurve zunehmend instabil, da die Kurve von einzelnen Punkten stärker beeinflusst wird. Wir bevorzugen stabilere Anpassungen und würden darum in diesem Fall (auch weil wir die wahre Funktion kennen) wohl intuitiv zwischen zwei und fünf Knoten wählen. Möchte man das nicht immer trivial zu lösende Problem der Knotenwahl umgehen und wünscht dennoch stabile Anpassungen, kann man das auch durch Regularisierung mit den im Folgenden beschriebenen Glättungsverfahren - trotz einer maximalen Anzahl an Knoten - erreichen.

3.1 Geglättete Splines

Geglättet werden Splines, indem die gesuchte Anpassung ein Minimierungsproblem löst, in dem neben der Abweichung von den Daten auch die zweite Ableitung der Anpassung berücksichtigt wird: Sei V der N-dimensionale Funktionenraum kubischer B-Splines zu [Diese Leseprobe ist für die Suchmaschinen. Formeln und Abbildungen werden nicht angezeigt.] inneren Knoten.

[...]

---

[1] Eine Herleitung dieser Basis findet sich im Anhang.