Boosting bei der Analyse von Konjunkturzyklen

Inhaltsverzeichnis

Einleitung

Bezeichnungen

Kapitel 1: Grundlagen
1.1 Das Klassifikationsproblem
1.2 Der CART-Algorithmus
1.3 Das PAC-Lern-Modell
1.4 Das dynamische Modell und die Integration von Hintergrundwissen

Kapitel 2: Boosting
2.1 Entstehungsgeschichte und Wurzeln von Boosting
2.2 Bisherige Anwendungsgebiete und Bewährung von Boosting
2.3 Erklärung verschiedener Algorithmen
2.4 Gradientenboosting

Kapitel 3: Wirtschaftliches Szenario
3.1 Beschreibung des RWI-Datensatzes
3.2 Problemstellung des Projektes B3 im Rahmen des SFB 475
3.3 Stand der Forschung bei der Auswertung der RWI-Datensatzes

Kapitel 4: Implementierung und Anwendung von MART
4.1 Aufrufparameter von MART
4.2 Anwendung auf den RWI-Datensatz

Kapitel 5: Ergebnis
5.1 Ergebnisdarstellung
5.2 Vergleich von CART und MART

Kapitel 6: Zusammenfassung und Ausblick

Anhang

Literaturverzeichnis

Einleitung

Das statistische Problem der Klassifikation beschäftigt sich mit der Zuordnung von Objekten zu Klassen. Jedes Objekt ist charakterisiert durch eine Anzahl von Variablenausprägungen und soll eindeutig in eine Klasse eingeordnet werden. Ein Klassifikationsalgorithmus oder Klassifikator trainiert zunächst auf einer Menge von bereits klassifizierten Objekten. Dann ordnet er Objekte, von denen nur die Variablenausprägungen, aber nicht die Klassenzugehörigkeiten bekannt sind, einer Klasse zu. Eine beliebte Form der Klassifikation ist diejenige anhand von binären Entscheidungsbäumen. Dabei wird eine Einteilung von Objekten mit Hilfe von einfachen Ja/Nein-Fragen erreicht.

Diese grundlegenden Begriffe der Klassifikation werden zusammen mit dem CARTAlgorithmus, dem PAC-Lern-Modell und den Überlegungen über die Einbeziehung von Hintergrundwissen in Klassifikationsalgorithmen im ersten Kapitel erläutert.

In Kapitel 2 findet sich die Definition, Erklärung und Geschichte von Boosting, zusätzlich eine Beschreibung verschiedener Boostingalgorithmen, einschließlich dem für eine spätere Analyse vorgesehenen MART-Algorithmus.

Der stark von den Wirtschaftswissenschaften geprägte Teil der Diplomarbeit ist in Kapitel 3 realisiert, nämlich der Beschreibung des RWI-Datensatzes, seiner Bedeutung und seiner bisherigen Analyse und Interpretation im Rahmen des Sonderforschungsbereichs 475 „Komplexitätsreduktion in multivariaten Datenstrukturen“.

Kapitel 4 widmet sich ausführlich dem in Kapitel 2 ausgewählten MART-Algorithmus, seinen Einstellungsparametern und der Beantwortung der Frage, nach welchen Analysevorschriften er auf den RWI-Datensatz angewendet wird.

Die Ergebnisse dieser Analyse sind in Kapitel 5 dargestellt, ein Ausblick in Kapitel 6 bildet den Abschluß.

Bezeichnungen

Abbildung in dieser Leseprobe nicht enthalten

Kapitel 1: Grundlagen

Klassifikation ist eines der statistischen Probleme, die intuitiv einsichtig, gut vorstellbar und leicht nachzuvollziehen sind. Jeder kann sich vorstellen, das es wichtig und notwendig ist, Objekte (z. B. Früchte) anhand von Eigenschaften (z.B. Form, Farbe, Geruch) mit größtmöglicher Sicherheit in Klassen (z.B. essbar, unbekömmlich, giftig) einzuteilen.

Wünschenswert ist eine Funktion, Klassifikator genannt, die es erlaubt, nur durch die Ausprägungen der Eigenschaften eines Objektes (z.B. runde Form, rote Farbe, süßlicher Geruch) dieses Objekt in eine der drei Klassen (z.B. essbar) einzuordnen. Eine Kirsche erfüllt die obige Beschreibung und wird somit - richtigerweise - als essbar eingestuft, eine Tollkirsche allerdings auch, was eine Fehlklassifikation darstellt!

1.1 Das Klassifikationsproblem

In diesem Rahmen werden die Bezeichnungen und Definitionen von Friedman [Friedman et al., 1998] für die Darstellung eines Klassifikationsproblems verwendet, da diese den Sachver- halt knapp und prägnant darstellen und auch mit den in den späteren Kapiteln verwendeten Begriffen übereinstimmen. Sie ähneln der Notation für das Konzeptlernen, die im Anschluß dargestellt ist.

Zwei-Klassen Klassifikationsproblem:

Seien Beispiele (xi, yi)∈B gegeben. Die xi sind die Beobachtungen am Objekt oi, yi bezeichnet seine Klasse oder die Antwort. xi und yi werden dabei als die Realisationen der Zufallsvariab- len Xi und Yi betrachtet, die für alle i einer gemeinsamen Wahrscheinlichkeitsverteilung W genügen.

Man versucht nun, basierend auf den Beispielen eine Klassifikationsfunktion oder einen Klas- sifikator f(xi) ∈ {0, 1} zu produzieren und zwar derart, daß der Generalisationsfehler R(f)

Abbildung in dieser Leseprobe nicht enthalten

möglichst klein ist.

Analog zu diesem Erklärungsansatz läßt sich die Problemstellung auch durch den Begriff Konzeptlernen beleuchten. Gegeben sei eine Menge von Objekten oi∈Ω mit den Eigenschaf- ten xi∈M, auf denen ein Zielkonzept c : M → {0, 1} gelernt werden soll. Für alle xi sind die Werte c(xi) bekannt und determinieren die Zugehörigkeit des Objektes oi zum Zielkonzept. Ist c(xi) = 1, so heißt (xi, c(xi)) positives Beispiel, ist c(xi) = 0 nennt man (xi, c(xi)) negatives Beispiel. Gesucht ist eine Hypothese h, für die gilt: h(xi) = c(xi) für alle xi ∈ M.

1.2 Der CART-Algorithmus

Die Abkürzung CART (Classification and Regression Trees) geht zurück auf das gleichnamige wegweisende Buch von Breiman [Breiman et al., 1984] aus dem Jahr 1984. Seitdem ist der darauf aufbauende Algorithmus CART ein weitverbreitetes Werkzeug zur Klassifikation und Regression mittels Entscheidungsbäumen [Salford Systems, 2002].

Die technische Funktionsweise von CART beruht auf binärer rekursiver Partition; d.h. jeder Vaterknoten wird immer in genau zwei Kinderknoten geteilt (binär) und dieser Prozeß kann wiederum auf jeden Kinderknoten angewandt werden (rekursiv). Das Herzstück der CARTAnalyse ist eine Menge von Regeln, die sicherstellen, daß:

- jeder Knoten in einen Baum aufgesplittet werden kann,
- eindeutig entschieden werden kann, ob ein Baum vollständig aufgebaut ist (oder ob weitere Splits erforderlich sind) und
- jedem Endknoten eine Klassenzugehörigkeit zugeordnet werden kann (oder einem Vorhersagewert bei Regression).

Splitregeln: Um einen Knoten in zwei Kinder zu spalten, benutzt CART immer eine soge- nannte Bool’sche Variable, die nur die Ausprägungen „ja“ und „nein“ kennt. CART-Analyse basiert auf der Methode, alle möglichen Splits für alle in die Analyse involvierten Variablen durchzuführen. Hat man beispielsweise ein Datenset mit 200 Beobachtungen und 13 Variab- len, dann wählt CART aus 200⋅13 = 2600 möglichen Splits den ersten Split aus. Jedes Prob- lem hat eine endliche, aber vielleicht auch sehr große Menge möglicher Splits, welche CART konsequent durchgeht.

Splitauswahl: Der nächste Schritt ist die Anordnung der vorgeschlagenen Splits nach der Splitgüte und anschließende Auswahl des besten Splits. Dazu ist ein Maß nötig, um die Splits qualitativ anzuordnen. Die Default-Einstellung des Algorithmus ist meistens die GINI-Regel. Dabei wird der sogenannte Gini-Index für die beiden potenziellen Kinderknoten für jeden in Frage kommenden Split berechnet und derjenige Split ausgewählt, der die Kinderknoten möglichst "klassenrein" gestaltet. Der Gini-Index in einem Knoten kann Werte zwischen 0 und 1 annehmen, wobei 0 ereicht wird, wenn in dem Knoten alle Beobachtungen in die glei- che Klasse gehören.

Klassenzugehörigkeit: Sobald die beste Splittung gefunden wurde, wird dieser Suchprozess für jeden Kinderknoten rekursiv durchgeführt, bis weiteres Splitting nicht mehr möglich ist oder der CART-Algorithmus künstlich gestoppt wird (wenn die extern vorgegebene Durch- laufzahl erreicht ist). Verschiedene Abbruchkriterien sind denkbar, z.B. wenn in einem Kno- ten nur noch ein möglicher Fall existiert oder alle Fälle untereinander gleich sind. Ist ein Endknoten erreicht, muß über die Klassifizierung entschieden werden; die einfachste Metho- de ist die Pluralitätsregel: die Gruppe mit der stärksten Repräsentation bestimmt die Klassen- zugehörigkeit. Natürlich sind auch andere Methoden denkbar und möglich (z.B. eine Einbe- ziehung von Mißklassifikationskosten). Anders als frühere Baumklassifikatoren baut CART immer zunächst einen kompletten Entscheidungsbaum auf, d.h. jeder Zweig wird zur Gänze bis zu allen Endknoten entwickelt und auf vorzeitiges Abschneiden ("Prunen") wird verzich- tet.

Pruning: CART produziert also einen sogenannten Maximalbaum, ohne in einem einzelnen Knoten zu entscheiden, ob er ein Endknoten ist oder nicht. Statt dessen werden im Nachhinein durch das „Pruning“ (englisch für Beschneiden) von Zweigen kleinere Bäume aus dem Maximalbaum für eine bessere Vorhersagequalität erzeugt.

Test: CART sucht nun aus der Menge der so entstandenen Unterbäume anhand von Fehler- raten oder Mißklassifikationskosten den Besten heraus. Für den einfachen Fall, daß genügend Daten vorhanden sind, wird die Datenmenge in Lern- und Testmenge aufgeteilt. Die Lern- menge wird zum Aufbau eines übergroßen Baumes benutzt und die Testmenge zur Berech- nung des Klassifikationsfehlers (evtl. unter Einbeziehung von Mißklassifikationskosten). Der beste Unterbaum ist der mit den geringsten Kosten; dieser kann unter Umständen gemessen am Maximalbaum relativ klein sein.

Kreuzvalidierung: Bei kleinen Datenmengen wendet CART die rechenintensive Methode der Kreuzvalidierung an. Dabei wird die gesamte Datenmenge zum Aufbau eines Entscheidungsbaums benutzt und danach die Datenmenge in zehn etwa gleich große Teile aufgeteilt. Dann werden jeweils neun Teile der Datenmenge zum Aufbau eines Baums verwertet und auf dem zehnten Teil wird getestet. So dient jeder der zehn Teile nacheinander als Testmenge und die erhaltenen Fehlerraten werden mit der des vorher aufgebauten Baumes verglichen. Dadurch kann ein Eindruck von der Güte des Entscheidungsbaumes zu Vorhersagezwecken gewonnen werden, ohne das - wie im oben beschriebenen Fall - genügend Daten vorhanden sind, um eine empirische Fehlerrate berechnen zu können.

In der statistischen Praxis ist der CART-Algorithmus ein oft und erfolgreich eingesetztes Werkzeug. Zahlreiche Vorteile erklären diese weite Verbreitung; hier eine Auswahl aus der reichlich zu diesem Thema vorhandenen Literatur:

- CART ist eine nicht-parametrische Prozedur und braucht keine Spezifikation in einer funktionalen Form.
- CART benötigt keine im Vorhinein ausgewählten Variablen, auch wenn Variablennumerierungen aus der Analyse herausgenommen werden sollten und die Performance durch eine „vernünftige“ Auswahl stark erhöht werden kann.
- Die Ergebnisse sind invariant bezüglich monotoner Transformationen der unab- hängigen Variablen. Damit muß man die Variablen nicht komplizierten Transformationen unterziehen, nur um CART anwenden zu können.
- CART kann komplizierte Datenstrukturen handhaben. Je mehr Daten vorhanden sind, desto mehr kann CART sich gegenüber anderen Analysemethoden auf sol- chen Strukturen durchsetzen.
- CART ist sehr robust gegenüber Ausreißern.
- CART kann sowohl kategorische als auch stetige Variablen behandeln.
- CART kann Linearkombinationen von Variablen nutzen, um Splits zu determinie- ren.
- Sind bestimmte Klassen überrepräsentiert, kann CART dies durch Gewichte an- gleichen.
- CART entdeckt Zusammenhänge und Interaktionen zwischen Variablen.
- CART kann auf unvollständigen Datensätzen arbeiten.

Das Konzept von Boosting basiert auf dem „probably approximately correct“ - Modell des Lernens [oder kurz: PAC-Lern-Modell] von Valiant [Valiant, 1984] und von Vapnik und Chervonenkis [Vapnik/Chervonenkis, 1971]. Es ist zum Verständnis von Boosting entscheidend, da die Möglichkeit, einen bestimmten Lernalgorithmus boosten zu können, und auch die Güte der Verbesserung, entscheidend von einigen grundlegenden Eigenschaften des Algorithmus selbst abhängt. Diese Eigenschaften (PAC-Lernbarkeit und Konsistenz) fußen auf der Begriffswelt des PAC-Lern-Modells.

1.3 Das PAC-Lern-Modell

Die von Valiant [Valiant, 1984] eingeführte Idee des wahrscheinlich annähernd korrekten Lernens geht von der Überlegung aus, das die Forderung nach einem korrekten und vollstän- digen Lernalgorithmus, der nach Verarbeitung eine bestimmten Menge von Beispielen ein- deutig und sicher das richtige Ergebnis ausgibt, aussichtslos und realitätsfremd ist. Stattdessen schwächt man die Forderung nach völliger Korrektheit ab und fordert, daß das Lernergebnis nur mit einer bestimmten Wahrscheinlichkeit annähernd richtig ist, wobei ein Fehler von höchstens ε toleriert wird. Dafür soll der Lernalgorithmus in polynomiell beschränkter Re- chenzeit und nach der Verarbeitung endlich vieler Trainingsbeispiele zu einem Ergebnis kommen.

Die Intention des PAC-Lern-Modells ist die Annäherung eines unbekannten Zielkonzepts c durch eine Hypothese h, die mit hoher Wahrscheinlichkeit das Zielkonzept approximiert. Mit den im vorangegangenen Kapitel definierten Begriffen läßt sich dieser Sachverhalt genauer darstellen.

Zwei wichtige Mengen von {0, 1}-wertigen Funktionen, die auf M definiert sind, werden nun vorgestellt: zum einen der Konzeptraum C (daher kommt das Zielkonzept c) und zum anderen der Hypothesenraum H (dieser umfaßt alle auf einem gegebenen Neuronalen Netz überhaupt lernbaren Konzepte). H ist also die Menge von Funktionen, die von einer bestimmten NNArchitektur berechenbar sind. Man betrachtet einen Lernalgorithmus l : P(M) → H, der auf der Potenzmenge von M operiert und ein Hypothese h auswählt. l wird auch als (C, H)Lernalgorithmus bezeichnet. Um die Güte eines Lernalgorithmus l zu bestimmen, muß ein Maß für den Abstand einer Hypothese h∈H zu dem Zielkonzept c∈C gefunden werden. Wir definieren dazu auf der Menge aller Objekte D, die einer Wahrscheinlichkeitsverteilung W unterliegen, den Fehler errorW(h, c) als die Wahrscheinlichkeit, daß ein zufällig ausgewähltes Objekt oi mit Realisation xi von h falsch klassifiziert wird. Also:

errorW(h, c) = PW({o∈D : h(x) ≠ y}).

Wenn c eindeutig durch den Kontext erklärt ist, benutzt man auch die Bezeichnung errorW(h).

Die Stichprobe S∈P(M) wird gemäß der Wahrscheinlichkeitsverteilung W zusammengestellt und die Hypothese l(S)∈H soll bezüglich c einen möglichst kleinen Fehler haben. l(S) ist dabei ein abkürzende Schreibweise für folgenden Zusammenhang: l lernt bezüglich einer bestimmten Stichprobe S eine Hypothese h∈H, die auf dieser Stichprobe den Fehler errorW(h, c) minimiert.

Abbildung in dieser Leseprobe nicht enthalten

Ein alternativer Ansatz zum Verständnis der komplexen Theorie von Valiant [Valiant, 1984] findet sich in der Arbeit von Morik [Morik, 1999]: PAC-Lernen wird hier als wahrscheinlich annähernd korrekte Lernbarkeit eines Konzeptraumes C durch einen Hypothesenraum H aufgefasst. Dabei heißt ein Konzeptraum C (PAC-)lernbar durch einen Hypothesenraum H auf einer Menge ausgewählter Objekte D, wenn es einen Algorithmus l(δ, ε) gibt, der

- bei allen beliebigen, aber festen Wahrscheinlichkeitsverteilungen über D
- für alle Zielkonzepte c aus der Menge C
- in einer durch ein Polynom über 1/ε, 1/δ, |c|, |x| begrenzten Zeit
- mit einer Wahrscheinlichkeit von mindestens 1 - δ eine Hypothese h∈H ausgibt, deren Fehler nicht größer ist als ε.

Dabei sollen ε und δ zwischen 0 und 1/2 liegen; |c| bezeichnet ein Maß für die Komplexität einer Funktion, z.B. ihre Verarbeitungsgeschwindigkeit bei einer Darstellung in effizienter Codierung. Entsprechend ist |x| ein Maß für die Verarbeitungsgeschwindigkeit der größten Realisation aus M.

Ein weiterer entscheidender Begriff zum Verständnis des Zusammenhangs von Boosting und dem PAC-Lern-Modells ist die sogenannte Konsistenz eines Lernalgorithmus:

Definition (Konsistenz): Der (H, H)-Lernalgorithmus l heißt konsistent (wobei H endlich sein soll) mit einer gegebenen Stichprobe S, wenn die Funktionen l(S) und c auf S für jedes x übereinstimmen.

Besonders beachtenswert ist hierbei die Interdependenz zwischen Konsistenz und PACLernbarkeit, denn es gilt:

Jeder konsistente (H, H)-Lernalgorithmus ist PAC.

Diese kurze Übersicht über die Begriffswelt des PAC-Lern-Modells zeigt die Wurzeln und Grundlagen für ein breites Spektrum unterschiedlicher Algorithmen und Erklärungsansätze (dargestellt in den Kapiteln 2.1 und 2.2), die alle mit Boosting und damit auch mit seinem zugrunde liegenden Modell in Zusammenhang stehen. Der Nutzen des Modell selbst ist aller- dings fragwürdig [Haussler, 1990], Haussler sieht ihn hauptsächlich in den erwähnten An- wendungen.

1.4 Das dynamische Modell und die Integration von Hintergrundwissen

In der Arbeit von Sondhauss und Weihs [Sondhauss/Weihs, 2001a] werden die bisherigen Klassifikationsmethoden bzgl. des RWI-Datensatzes (beschrieben in Kapitel 3) dargestellt und Vorschläge zur Integration von Hintergrundwissen in die Klassifikationsregeln ausgear- beitet. Wie dies im Einzelnen zu verwirklichen ist und eine aus den unten beschriebenen Modellierungen resultierende Analyse aussieht, wird in Kapitel 4.2 ausführlich dargelegt; an dieser Stelle wird beschrieben, auf welche Art Hintergrundwissen über eine zyklische Struk- tur der Klassendurchläufe modelliert werden kann.

Notation: Sei X ein K-dimensionaler reellwertiger Vektor der Zufallsvariablen X1, ..., XK, dessen Realisation (x1, ..., xK) = x genau einer Klasse s∈S := {1, ..., J} zugeordnet werden soll. Im Spezialfall „Konjunkturphasen“ werden nicht verschiedene Objekte klassifiziert, sondern ein sogenanntes System zu verschiedenen Zeitpunkten t = 1, ..., T beobachtet und einem Zustand s zugeordnet. Die chronologische Reihenfolge, in der das System die Zustände durchläuft, ist fest vorgegeben. Befindet sich das System zum Zeitpunkt t - 1 im Zustand st-1, so kann es entweder zum Zeitpunkt t in diesem Zustand verweilen, oder in einen bestimmten Zustand s [Abbildung in dieser Leseprobe nicht enthalten] wechseln. Die meisten Klassifikationsmethoden basieren auf einer Transformati- t −1 on m(s, •) der beobachteten Variablen in die reellen Zahlen für jede der Klassen, wobei die Größe der Transformation die Stärke der Mitgliedschaft zu der jeweiligen Klasse repräsentiert. Somit wird m(s, x) als Zugehörigkeitswert des Objektes o mit Realisation x zur Klasse s interpretiert. Für alle Bayes-Regeln beispielsweise sind die Zugehörigkeitswerte die geschätzten bedingten Klassenwahrscheinlichkeiten.

Anwendung: Die bekannten Klassifikationsregeln werden dahingehend abgeändert, daß nicht nur diese bedingte Wahrscheinlichkeit in die Betrachtung einfließt, sondern zusätzlich auch die bedingte Wahrscheinlichkeit eines Zustandes, gegeben den vorangegangenen Zustand. Betrachtet man - ausgehend von einem letzten bekannten Zustand s0 des Systems - jeden aufgrund von [Abbildung in dieser Leseprobe nicht enthalten] und [Abbildung in dieser Leseprobe nicht enthalten] vorhergesagten Zustand ˆ als "wahr" [Abbildung in dieser Leseprobe nicht enthalten] und bewegt sich h 1 nur entlang eines Pfades erlaubter Zustände h [Abbildung in dieser Leseprobe nicht enthalten] so wird dies Klassifikation mit 0 1 t exakten Übergängen genannt.

Berechnet man hingegen die Wahrscheinlichkeit, sich zum Zeitpunkt t im Zustand [Abbildung in dieser Leseprobe nicht enthalten] zu t befinden, als Summe der Wahrscheinlichkeiten aller Pfade vom letzten bekannten Zustand s0 bis zum Zustand [Abbildung in dieser Leseprobe nicht enthalten], so bezeichnet man dies als Klassifikation mit propagierter Evidenz.

Über die zyklische Struktur hinaus können auch weitere zeitliche Abhängigkeiten einbezogen werden. Vorlage ist dabei das sogenannte Rakemodell (nachzulesen bei Sondhauss und Weihs [Sondhauss/Weihs, 2001a]), welches sich als dynamisches Bayes-Netz mit zwei Zeitschichten beschreiben läßt. Dabei ist die multivariate Verteilung von Eigenschaften und Zuständen in bestimmter Weise abhängig von deren Realisationen in der vorangehenden Zeitschicht. Genauer ist das Rakemodell eine multivariate Version des sogenannten Markov regime switching model nach Hamilton [Hamilton, 1989].

Die Verteilung der (zeitabhängigen) Zufallsvariablen Xt,k wird als abhängig vom aktuellen Zustand st und zusätzlich vom Vorgänger Xt-1, k (t = 1, ..., T) modelliert. Gleichzeitig ist sie unabhängig von allen anderen (vergangenen oder aktuellen) Variablen. Genauso ist der aktuelle Zustand des Systems nur von dem direkten Vorgänger abhängig, nicht hingegen von allen anderen vorhergehenden Zuständen.

Dadurch vereinfachen sich die Zusammenhänge wesentlich und eine Berechnung der aktuellen Zustandswahrscheinlichkeiten zum Zeitpunkt t, gegeben aller bis dahin beobachteten Hintergrundinformationen, wird möglich (siehe zu den Einzelheiten wiederum Sondhauß und Weihs [Sondhauss/Weihs, 2001a]).

[...]