Software-Projekt SW04

- - - - - - - -
Sampling	In EA, bei denen die Fitnessfunktion nicht als geschlossene Funktion vorliegt, sondern bei denen eine Menge von Beispielen (fitnes-cases) durchgerechnet werden müssen, ergeben sich Effizienzprobleme, wenn sehr viele Beispiele vorliegen, und wenn für jedes Individuum alle Beispiele durchgerechnet werden sollen. Beispiele solcher Aufgaben sind überwachte Lernprobleme, die durch eine Menge von Lernstimuli gegeben sind. Die Auswahl einer Teilmenge von fitnes-cases aus der Gesamtmenge ist eine naheliegende Strategie zur Effizienzverbesserung, wobei die zufällige Ziehung von Stichproben (Sampling) eine, aus der Statistik wohl bekannte, Verfahrensklasse ist, deren Vor- und Nachteile in der Theorie der Stichproben beschrieben werden. Die Zufallsauswahl von fitnes-cases aus einer Gesamtmenge wird als "stochastic sampling von fitnes-cases" im Rahmen von GP bezeichnet (Banzhaf et al. (1998: 160f), wobei im Extremfall genau ein Stimulus aus der Gesamtmenge zufällig ausgewählt wird, um die Individuen einer Generation zu bewerten. Verschiedenen Individuen können auch verschiedene Teilmengen von fitnes-cases zugeordnet werden, wobei jedoch das Problem der fehlenden Vergleichbarkeit innerhalb der gleichen Generation auftritt. Stochastic Sampling, bei dem die Anzahl der verwendeten fitnes-cases im Generationsverlauf grösser wird, ist ein Beispiel einer progressiven Evaluationsumgebung, die sich dadurch auszeichnet, dass eine Sequenz von Evaluierungsfunktionen im Generationsverlauf verwendet wird, wobei der Aufwand deren Berechnung zu Beginn klein ist, und im Generationsverlauf ansteigt.
Clustering	Neben der Ziehung aus der Gesamtmenge der fitnes-cases besteht die Möglichkeit der Strukturierung der Gesamtmenge, d.h. der Clusterung, gefolgt von einer stochastischen oder deterministischen Strategie, mit der einzelne Stimuli aus den jeweiligen Clustern ausgewählt werden, und die als fitnes-cases in EA oder als Lern-Stimuli in überwachten Lernsystemen wie überwachten SOM-Architekturen eingesetzt werden. Unüberwachte SOM-Architekturen wie die GNG-SOM und in besonderer Weise die SC-GNG-SOM (Bachelier (1998c), s.a. Software-Projekt SW03) bieten die Möglichkeit der Strukturierung mit besonderen Eigenschaften, da der Verbindungsgraph der Gewichtsvektoren ein Delaunay-Graph bzw. ein Subgraph eines Delaunay-Graphen ist, sodass die zugehörige Voronoi-Zerlegung eine Partitionierung des Inputraumes bzw. des kombinierten Input- und Outputraumes ist.
Resampling	Während das Sampling eine Strategie bei dem Vorliegen einer sehr grossen Stimulusmenge ist, ist ein Resampling-Verfahren eine Strategie bei dem Vorliegen einer kleinen Stimulusmenge. Werden bekannte, überwachte Lernverfahren auf eine kleine Menge von Stimuli angewendet, so ergeben sich in der Regel Modelle mit einer grossen Unsicherheit, wenn es sich nicht um ausgewählte Stimuli handelt, die durch Auswahlstrategien aus Clustern oder durch Aktives Lernen (siehe Software-Projekt SW07) festgelegt werden. Mit Hilfe von Resampling-Verfahren können künstliche Stimulusmengen erzeugt werden, die für Lernzwecke verwendet werden, wobei die sich ergebenden Modelle bzw. eine Aggregation der sich ergebenden Modelle (Combining) eine kleine Unsicherheit (Output-Varianz) bzw. kleinere Fehler (Bias) besitzen. Orientierung bieten hier die Implementierungen von Efron & Tibshirani (1993), die neben dem Paiwise- und dem Residual-Bootstrapping, Jackknife und Ansätze zur Approximation von Bootstrap-Konfidenz-Intervallen enthält. Eine weitere Variante, das Wild-Bootstrapping müsste jedoch noch hinzukommen (Mammen (1992)). Ein Überblick über Resampling-Verfahren im Zusammenhang mit der Modellbildung in SOM-Systemem ist auch in Bachelier (1999c) zu finden. Bootstrapping gehört neben Jackknife zu den Resampling-Verfahren, mit denen Schätzungen statistischer aber auch neuronaler und evolutionärer Modelle verbessert werden können. Weiterhin können damit Bias-Schätzungen und -Korrekturen der Modelle und Schätzungen erzeugt, sowie Bias-Konfidenzintervalle berechnet werden. Grundlage ist die Erzeugung von Resamplingmengen bzw. -listen aus einer Gesamtmenge von Lernbeispielen, mit denen jeweils eigene Modelle und eigene Schätzungen erzeugt werden, die zu einer gemeinsamen Schätzung integriert werden. Um statistisch signifikante Aussagen zu erhalten, sind für Resampling-Schätzungen 50 - 100 Einzelmengen notwendig, und für Konfidenzintervalle nochmals ein Vielfaches, sodass verschiedene Approximationsverfahren für die entsprechenden Konfidenzintervalle vorgeschlagen wurden.
Combining	Beim Resampling werden die Einzel-Stimulusmengen dazu verwendet, jeweils ein Modell zu erzeugen, dessen Outputs für einen gegebenen Input aggregiert werden müssen, was eine Form des Combinings ist (s.a. Skalak (1996)). Welche Aggregationsfunktion man für das Combining verwendet, wie z.B. eine Mittelwertsbildung durch einen der OWA-Operatoren (Yager & Kacprzyk (1997)), ist möglicherweise von der betrachteten Domäne bzw. dem Einzelproblem (Task) abhängig.
Resampling- und Combining-Funktion als Unterprogramme	Eine Resampling- und eine Combining-Funktion könnten als Unterprogramme in einem überwachten Lernsystem installiert werden, die durch ein Verfahren aus der Klasse Heuristic-Programming bzw. HIMC spezifiziert werden.
Ansatz 1	In einem ersten Ansatz kann das Lernverfahren konstant gehalten werden, wie z.B. die Verwendung eines Local-Weighted-Regression(LWR)-Verfahrens. Ein Lösungsvorschlag bzw. Individuum besteht dann aus einem Resampling- und einem Combining-Modul, kombiniert mit einem LWR-Modul, das extern festgelegt wurde, und für alle Individuen und Generationen konstant ist. Im Generationsverlauf werden durch GP/HP die Resampling- und Combining-Module rekombiniert und mutiert, ohne dass das LWR-Modul verändert wird. Die Evaluation eines solchen drei-moduligen Individuums erfolgt durch die Bildung von Output-Schätzungen für Evaluations-Stimuli, d.h. die Evaluation erfolgt auf Individuenebene und nicht auf Modulebene. Konkrete Resampling- und Combining-Module besitzen somit keinen eigenen Evaluationswert, was bei der betrachteten Reproduktionsart auch nicht notwendig ist. Faktisch wird somit eine Form von indirekter Selbstadaption der beiden Modultypen durchgeführt, da eine Fitnesswert nur zusammen, und in Kombination mit dem gegebenen LWR-Modul erzeugt und verwendet wird.
Ansatz 2	In einem zweiten Ansatz kann das LWR-Modul ebenfalls einer evolutionären Selbstadaption unterzogen werden, indem die Parameter eines konstanten LWR-Funktionstyps bestimmt werden, oder indem ein geeigneter Funktionstyp gesucht wird.
Ansatz 3	Der am weitest gehende Ansatz verwendet keine vorgegebene Funktion für das überwachte Lernen, sondern das Lern-Modul wird als ein GP- bzw. HP-Programm definiert, dessen interne Struktur durch die evolutionäre Selbstadaption spezifiziert wird (siehe auch Gathercole (1998) oder symbolische Regression durch CGP (Nordin)), sodass mit Resampling, Learning und Combining drei Module erzeugt werden, die zusammen ein Verfahren ergeben, das als Lösungsvorschlag verwendet wird. Naheliegend sind koevolutionäre Verfahren, in denen drei Populationen symbiotisch kooperieren, indem jeweils ein Individuum einer Population als Modul ausgewählt wird, die zu einem Symbiose-Organismus kombiniert werden. Die Fitnessevaluation erfolgt auf der Ebene des Symbiose-Organismus, ebenso wie die Reproduktions- und Selektions-Operationen. Den einzelnen Modulen wird eine Evaluation zugeordnet, was jedoch eine Vereinfachung ist, da es sich dabei wiederum um eine Form der indirekten Selbstadaption handelt. Reproduktion und Selektion zur Übernahme in die Nachfolgepopulation geschehen innerhalb der einzelnen Spezies, d.h. der Modularten.
Ansatz 4	Ein anderer Ansatz ist die Verwendung aller Lernverfahren-Module in der entsprechenden Population, d.h. ein Symbiose-Organismus besteht aus einem Resampling- und einem Combining-Modul, sowie aus my Learning-Modulen. Aus der Grundstimulusmenge werden durch das Resamplingverfahren my Resamplingstimulusmengen erzeugt, denen zufällig ein Learning-Modul zugeordnet wird. Somit wird durch die Paarung eines Resampling- und eines Learning-Moduls ein Modell erzeugt, dessen Output zusammen mit den Outputs der anderen Modelle als Input in das Combining-Modul verwendet wird, das eine Outputschätzung erzeugt, die zur Bewertung des Symbiose-Organismus verwendet wird. Die Selektion zur Reproduktion von Resampling- und Combining-Modulen erfolgt auf der Basis der Bewertung der Symbiose-Organismen. Unabhängig davon ist die Reproduktion der Learning-Module, denen eigene Bewertungen auf der Basis ihrer Outputschätzungen zugeordnet werden.
Lernen im Netz	Sampling-Combining-Strategien bzw. Resampling-Combining-Strategien eignen sich besonders für Lernen in einem Netz. Ein Server kann beispielsweise aus einer Gesamtmenge Teilmengen durch Ziehen mit Zurücklegen erzeugen, die an einzelne Netzknoten verteilt werden. Dort wird jeweils ein unabhängiges Modell durch ein überwachtes Lernverfahren erzeugt. Recall-Stimuli, d.h. Stimuli, zu denen die richtigen Outputs nicht bekannt sind, werden danach zu den einzelnen Knoten versendet. Jedes Modell in einem Knoten erzeugt daraufhin eine Outputschätzung, die zu dem Server gesendet wird, der die einzelnen Schätzungen als Input eines Combining-Moduls verwendet, und daraus eine aggregierte Outputschätzung erzeugt.
Beziehung zu anderen Projekten	Im Rahmen des Software-Projektes sollen existierende und erfolgreiche Sampling-, Clustering-, Resampling- und Combining-Strategien in einer Entwicklungs- und Test-Umgebung integriert werden, wobei es sich damit faktisch um eine Erweiterung der Software-Projekte SW01 und SW03 handelt. Insbesondere die Auswahl von Stimuli aus einer endlichen gegebenen Lernmenge betrift das Aktive Lernen, das im Software-Projekt SW07 betrachtet wird. Ansätze wie z.B. Boosting, rekursive Partitionierung, Divide and Conquer, Voting, ... (siehe Skalak (1996)) sollen ebenfalls betrachtet werden.
- - - - - - - -
Referenzen	Banzhaf, W.; Nordin, P.; Keller, R.E.; Francone, F.D.: Genetic Programming. dpunkt.Verlag, Heidelberg, 1998. Efron, B.; Tibshirani, R.: An introduction to the bootstrap. Chapman & Hall, New York, 1993. Gathercole, Chris: An Investigation of Supervised Learning in Genetic Programming. Dissertation, Universität Edinburgh, 1998. Langdon, William B.: Data Structures and Genetic Programming: Genetic Programming + Data Structures = Automatic Programming! Kluwer, Boston, 1998. Mammen, Enno: When does Bootstrap work? Springer-Verlag, New York, 1992. Skalak, David B.: Prototype Selection for Composite Nearest Neighbor Classifiers. Dissertation, Department of Computer Science, University of Massachusetts, 1996. Yager, R.; Kacprzyk, J.: The Ordered Weighted Averaging Operators. Kluver, 1997.