Software-Projekt SW12

- N a v i g a t i o n - - - - - - - -

- VI-ANEC

- Über das Institut

- Software-Projekte

- Hardware-Projekte

- Best-Paper-Best-Program-Awards

- Sponsoring

- Dienste

- Kontakt

Evolutionäre Algorithmen und selbstadaptive Bias-Varianz

Wie das Beispiel pulskodierter Neuronaler Netze (Software-Projekt SW11) im allgemeinen und das Berger-Liaw-NN im speziellen zeigen, besitzt die Repräsentation einen wesentlichen Einfluss auf die Adaptions- und Lernfähigkeit eines Systems. D.h. es existieren Repräsentationsformen eines Problems, die leicht zu lernen sind, und es existieren Repräsentationsformen, die durch einen Adaptionsalgorithmus schwer zu lernen sind. Zu diesem Ergebnis kommen auch Geman et al. (1992:51), wenn sie Anderson & Rosenfeld (1988) zitieren mit: "A good representation does most of the work".

Geman et al. (1992) behandeln die Frage der Repräsentation im Zusammenhang mit der Bias-Varianz-Problematik, wobei die Wahl einer Repräsentationsart eine Form von Bias einführt, die Repräsentations-Bias (oder Language-Bias). Diese Festlegung führt zu einer potentiell besseren Kontrolle der Varianz (Geman et al. (1992:50f)), da entsprechend der additiven Zerlegung des Mittleren Quadratischen Fehlers (MSE) in eine Bias-Quadrat- und eine Varianz-Komponente, eine Biaserhöhung zu einer Varianzverringerung führt. Diese Argumentation ist jedoch nicht konstruktiv, da durch sie nicht entschieden werden kann, welche alternativen Repräsentationsformen existieren und welche in einem konkreten Problemfall ausgewählt werden sollen.

Die Repräsentations-Bias ist eine Form der Bias, die in Lernsystemen auftritt. Daneben existieren Explorations-Bias und Evaluations-Bias (siehe Neri (1997:39)), die zusammen in einer nicht linearen Weise in eine Gesamt-Bias eingehen.

Repräsentations- und Evaluations-Bias hängen in besonderer Weise zusammen, da die Evaluations-Bias sich auf die Fitnesslandschaft (Fitnessraum) und ihre Eigenschaften bezieht, während die Repräsentations-Bias sich auf den Inputraum und seine Eigenschaften bezieht, der ein Unterraum des Fitnessraumes ist. Bei einer Ein-Ziel-Optimierung wird jedem Punkt des n-dimensionalen metrischen Inputraumes ein, in der Regel reeller Wert, als Fitnessbewertung zugeordnet, sodass sich ein metrischer (n+1)-dimensionaler Raum ergibt, der als Fitnessraum bezeichnet wird. Zu beachten ist, dass die Metrik im Inputraum und im Fitnessraum verschieden sein kann, wobei sie jedoch vereinfachend meist als gleich betrachtet wird.

Man könnte auch die Repräsentations-Bias als Oberbegriff verwenden, und Bias bei der Formulierung des Inputraumes und des Fitnessraumes als Unterbegriffe I-Repräsentations-Bias und F-Repräsentations-Bias einführen, d.h. die Evaluations-Bias wird als F-Repräsentations-Bias bezeichnet.

Mit der F-Repräsentation eng verbunden ist die Frage der Beschreibung der Fitnesslandschaft durch Kennzahlen, wie die Autokorrelationsfunktion, Korrelationslänge, Korrelationskoefizient, Informations- und Entropiemasse, Fraktale Dimensionen und die durchschnittliche Länge von Hill-Climbing-Suchen nach dem nächsten lokalen Minimum (siehe Hordijk (1995), Lipsitch (1991), Manderick et al. (1991), Vassilev (1997), Rochet et al. (1998), Nissen (1994:126ff)). Ziel dieser Untersuchungen ist es, den Grad an Schwierigkeit der Optimierung einer Funktion durch einen bestimmten EA durch Kennzahlen der Fitnesslandschaft zu schätzen.

Im Rahmen von EA bestanden die Hauptbemühungen in der Vergangenheit (und Gegenwart) hauptsächlich darin, Einfluss auf die Explorations-Bias zu gewinnen, indem immer neue EA-Varianten entworfen, und an gegebenen Problemen mit einer festen Repräsentation getestet wurden. Es existieren auch vereinzelt Ansätze, bei denen Meta-Verfahren bezüglich des Suchverfahrens betrachtet werden, d.h. es wird aus einer endlich gegebenen, oder einer parametrisierten Menge von Suchverfahren das oder die ermittelt, die bezüglich eines Problems und einer Repräsentation des Problems gut geeignet sind, extremale Punkte im Fitnessraum zu finden.

Zu beachten ist, dass ES mit seinen selbstadaptiven Schrittweitenvektoren bereits eine Form von parametrisiertem Meta-Verfahren ist, da jedes Individuum mit seinem eigenen Schrittweitenvektor und der für alle geltenden Mutationsfunktion (meist Gaussfunktion) ein Suchverfahren repräsentiert. Die ES gehören somit zu den reaktiven Suchverfahren (Reactive Search), die vergangene Ereignisse innerhalb eines Suchlaufes oder vergangene Suchläufe innerhalb einer Problemdomäne analysieren und verwenden, um die weitere Suche effizienter und effektiver zu gestalten wie z.B. die Reactive-Tabu-Search. Reaktive Suchverfahren sind somit Versuche zur selbstadaptiven Regelung der Explorations-Bias in einem Suchlauf oder einer Sequenz von Suchläufen.

Es existieren auch Ansätze innerhalb der Genetischen Algorithmen (GA), die in der Basisversion nicht-reaktiv sind, selbstadaptive Operatoren einzuführen, wie z.B. die evolutionäre Suche nach geeigneten Crossover-Punkten bei der Rekombination innerhalb von GAs.

Gegenüber den Bemühungen bezüglich der Explorations-Bias sind die Bemühungen bezüglich der beiden Repräsentations-Bias-Typen gering.

Die Einführung einer Pulskodierungsfunktion, die Inputwerte und somit den Inputraum transformieren, sowie Ansätze zum "Making Problems EA-friendy" von Sebald & Chellapilla (1998a,b), bei denen Metriken und Koordinatensystemtransformationen evolutionär gesucht wurden, können als Ansätze zur Beeinflussung der I-Repräsentations-Bias interpretiert werden.

Ansätze zu den "Progressiven Evaluationsumgebungen" (Hikage et al. (1998)), sowie Fitness-Approximationsmodelle (Bachelier (1999d)) können als Ansätze zur Beeinflussung der F-Repräsentations-Bias interpretiert werden.

Der Einfluss auf die Explorations-Bias im Rahmen des GP/HP ist schon dadurch nachzuvollziehen, dass hybride Ansätze verwendet werden, die alle die Variation betreffen, d.h. die Erzeugung von Nachkommen, wenn beispielsweise Tabulisten oder Tabutemplates erzeugt werden, die regeln, welche Konstrukte in Nachkommen für einen bestimmten Zeitraum nicht enthalten sein dürfen.

Die I-Repräsentations-Bias wird durch die Auswahl der Programmstruktur und der Sprachelemente getroffen, beispielsweise durch die Auswahl einer minimalen Menge von arithmetischen und logischen Maschinenbefehlen beim CGP/CHP, verbunden mit einem String als Programmstruktur.

Die F-Repräsentations-Bias ist abhängig von der Auswahl der Fitnescases, sowie der Aggregations-Metrik, mit der die Ergebnisse der einzelnen Fitnesscases zu einem Fitnesswert oder einem Fitnessintervall aggregiert werden.

Betrachtet man diese Darstellungen, so sollen im Rahmen dieses Software-Projektes aktiv-evolutionäre Verfahren zur Selbstadaption der einzelnen Biastypen in das EA-System integriert werden, das im Software-Projekt SW01 begonnen, und durch eine Reihe von Software-Projekten wie z.B. SW07 erweitert wurde.

Dabei sollte das Konzept der Wiederverwendbarkeit in Domänen berücksichtigt werden, d.h. die gefundenen Repräsentationsformen und Suchverfahren, die bei einer Probleminstanz als besonders erfolgreich war, sollte sich auch bei anderen Instanzen der gleichen Problemdomäne bewähren. Eine solche Forderung kann nur erfüllt werden, wenn die Repräsentationsformen und Suchverfahren auf einer Reihe von Instanzen der Domäne getestet werden, bzw. wenn die Selbstadaption der Biastypen über einer Menge von Instanzen durchgeführt wird.

Wie bereits oben dargestellt wurde, behandeln Geman et al. (1992) die Frage der Repräsentation im Rahmen der Bias-Varianz-Problematik, wobei die Wahl einer guten Repräsentation zu einem angemessenen Mass an Bias führt, wobei die dabei entstehende Varianz als gut beherrschbar betrachtet wird.

In Naftaly et al. (1997) wird innerhalb einer Resampling-Combining-Strategie (siehe auch Software-Projekt SW04) der Vorschlag gemacht, die einzelnen (NN-)Modelle so lange zu trainieren, bis eine Übergeneralisierung eintritt, d.h. die einzelnen Modelle besitzen eine kleine Bias. Die einzelnen Biaswerte rühren von unterschiedlichen Lernmengen her, sodass es unterschiedliche Bias-Formen sind, die jedoch nicht unterschieden werden können, da die Bias-Definition in Geman et al. (1992) über die einzelne Deltawerte aggregiert. Würde ein Biasvektor definiert, dessen Komponenten die einzelnen Deltawerte der Fitnesscases enthält, so könnten die Biasvektoren der einzelnen Modelle unterschieden werden, worauf hier jedoch nicht näher eingegangen werden soll. Werden die Ergebnisse der einzelnen Modelle im Rahmen einer Resampling-Combining-Strategie aggregiert, indem beispielsweise eine Bootstrap-Gesamtschätzung aus den Bootstrap-Einzelschätzungen der unterschiedlichen Modelle durch Bildung des arithmetischen Mittelwertes erzeugt wird, so wird auf diese Weise die Varianz der Gesamtschätzung verringert. D.h. durch das Übertraining der Einzelmodelle wird deren Bias verringert, während durch die Aggregation zu einer Gesamtschätzung die Varianz des Composing-Modells verkleinert wird. Dabei wird implizit angenommen, dass durch die Aggregation die Bias des Composing-Modells nicht erhöht wird.

Ansätze wie in Naftaly et al. (1997) gehen davon aus, dass eine Minimierung von Bias und Varianz zu einem optimalen Modell führen wird, wobei berücksichtigt werden muss, dass beide Variablen invers miteinander verknüpft sind, d.h. eine Verringerung der Bias führt zu einer Erhöhung der Varianz und umgekehrt.

Gegeben sei ein metrischer Modellraum, dessen Punkte Lösungen für ein zu betrachtendes Problem darstellen. Hierbei können parametrisierte Modelle verwendet werden, wie z.B. Local-Weighted-Regression-Modelle mit unterschiedlichen Stützpunkten und lokalen Gewichtungsfunktionen. Es sind aber auch nicht-parametrisierte Ansätze im Rahmen des GP durch eine Symbolic Regression möglich, wobei Programme Element eines metrischen Programmraumes sind. Jedem dieser Modelle kann durch ein oder mehrere Qualitätsmasse eine Bewertung zugeordnet werden, die eine erste Klassifizierung in hinreichend gute und abzulehnende Modelle ermöglicht. Betrachtet wird der carthesische Raum aus dem Lösungsraum und dem zwei-dimensionalen Bias-Varianzraum, wenn jedem der Lösungsmodelle ein Bias- und ein Varianzwert zugeordnet werden. Aus der Menge der hinreichend guten Modelle kann die Paretomenge der Modelle ermittelt werden, d.h. die Menge von Modellen, die alle anderen dominieren, aber untereinander nicht-dominierend sind.

Diese Überlegung berücksichtigt die Tatsache, dass der MSE auch anders in einen Bias- und einen Varianzwert zerlegt werden kann, als dies in Geman et al. (1992) als ungewichtete Summe durchgeführt wurde. Eine alternative Zerlegung findet sich in Wolpert (1997), der neben Bias und Varianz auch einen Kovarianzterm einführt. Im allgemeinen kann der MSE als nichtlineare Funktion aus Bias und Varianz betrachtet werden. Wird das Paretokriterium verwendet, so muss keine externe Spezifizierung dieser Funktion durchgeführt werden, da die Paretomenge eine rationale Spezifizierung darstellt.

Dies steht in direktem Zusammenhang mit der Problemstellung des "Modell-Generation and Modell-Selection", wobei erkannt wurde, dass zu einer endlichen Lernmenge unendlich viele Modelle erzeugt werden können, die diese Lernmenge in der einen oder anderen Weise optimal repräsentieren, dass es jedoch schwierig ist, ein Modell aus dieser Modellmenge zu selektieren und für Anwendungen zu verwenden.

Combining-Strategien realisieren diese Erkenntnis, indem eine Modellmenge als Lösung des Ursprungsproblems betrachtet wird, wobei der Output der Einzelmodelle durch eine Aggregationsfunktion zu einem Output des Gesamtmodells zusammengefasst wird.

Die prinzipielle Frage nach der Auswahl von geeigneten Einzelmodellen muss in einem solchen Kontext noch beantwortet werden. In Naftaly et al. (1997) sowie in einer Vielzahl von anderen Ansätzen werden Modelle als Experten betrachtet, d.h. ein Einzel-Modell besitzt bestimmte herausragende Fähigkeiten in dem betreffenden Phänomenbereich, während es andere Dinge schlecht kann. Erst durch die Aggregation entsteht ein Gesamtmodell, von dem erwartet wird, dass es herausragende Fähigkeiten in all den Teilbereichen besitzt, die von Einzel-Experten abgedeckt werden. Es entsteht somit eine Form von Divide-and-Conquer. Wird ein Experte durch die Begriffe Bias und Varianz beschrieben, so besitzt er durch seine Spezialisierung eine geringe Bias für sein Spezialgebiet, aber eine grosse Varianz bezüglich anderen Spezialgebieten.

Die Hypothese im Rahmen einer Mehr-Ziel-Strategie mit Eigenschaften wie Bias und Varianz ist, dass die Paretomenge bezüglich der betrachteten Eigenschaften eine geeignete Menge darstellt, um ein Gesamtmodell mit dem richtigem Mass an Bias und an Varianz für den betrachteten Phänomenbereich durch ein selbstadaptives Combining-Verfahren zu erzeugen.

Die Verwendung einer Modellmenge bzw. einer Population von Modellen als Lösung für das Ursprungsproblem besitzt bezüglich der Robustheit, Fehlertoleranz und Anpassungsfähigkeit ausserordentliche Vorteile, wie schon Layzell (1998:55) erkannt hat. Besonders für nicht-stationäre Umgebungen und offene Welten, bei denen Vorhersagen nicht den Charakter von Hypothesen mit Wahrscheinlichkeiten besitzen, erscheint eine Modellmenge eine geeignete Lösungsstrategie.

Diese Eigenschaften werden realisiert durch die Aggregations- bzw. Gewichtungsfunktion auf der Modellebene, mit der Einzelmodelle ihren Einzel-Output zu einem Gesamtmodell-Output vereinen, was eine zweite Selbstadaptionsebene begründet. Ein Ausfall einzelner Modelle kann durch die Aggregationsfunktion kompensiert werden. Interpretierbar ist diese Konfiguration in einem konnektionistischen Rahmen als Netz von Modulen bzw. als Netz von Neuronalen Netzen. Genauso wie der Ausfall eines Einzel-Neurons in einem Neuronalen Netz die Gesamtleistung wenig beeinflusst, so ist der Ausfall eines Gesamtmoduls ein wesentlich unwahrscheinlicheres Ereignis, das zudem die Leistung des Gesamtmodells wenig beeinflusst, wenn eine selbstadaptive Aggregationsfunktion existiert.

Konzepte wie der Neuronale Darvinismus (Selektion von Neuronalen Gruppen, Edelman (1987)) stehen damit ebenfalls in Verbindung, wobei Selektion als eine Sonderform von Gewichtung betrachtet werden kann, bei der alle Gewichtungsfaktoren bis auf einen auf Null gesetzt werden.

Anderson, J.A.; Rosenfeld, E.: Neurocomputing. Foundation of Research. 1988, S. 587.

Bäck, Thomas: (ed.): Proceedings of the Seventh International Conference on Genetic Algorithms. Michigan State University, East Lansing, MI, Morgan Kaufmann, ISBN 1-55860-487-1, 1997.

Belew, R. K.; Booker, L. B. (eds.): Proceedings of the Fourth International Conference on Genetic Algorithms. San Mateo, CA, Morgan Kaufmann, 1991.

Edelman, Gerald H.: Neural Darvinism, 1987.

Geman, S.; Bienenstock, E. Doursat, R.: Neural Networks and the Bias/Variance Dilemma. In: Neural Computation, 4, S. 1 -58, 1992.

Hao, J.-K.; Lutton, E.; Ronald, E.; Schoenauer, M.; Snyers, D. (eds.): Artificial Evolution. Third European Conference, AE'97, Springer Verlag, LNCS 1363, 1998.

Hikage, T.; Hemmi, H.; Shimohara, K.: Comparison of Evolutionary Methods for Smoother Evolution. In: Sipper, Moshe; Mange, Daniel; Perez-Uribe, Andres (eds.): Evolvable Systems: From Biology to Hardware (ICES98), S.115 - 124.

Hikage, T.; Hemmi, H.; Shimohara, K.: Hardware EvolutionSystem AdAM. Communications of the ACM Vol. 42, Nr. 4, S. 64f, 1999.

Hordijk, Wim: A Measure of Landscapes. Santafe-TR 95-05-049, 1995.

Layzell, Paul : A New Research Tool for Intrinsic Hardware Evolution. In: Proceedings of Second Int. Conf. on Evolvable Systems: From Biology to Hardware (ICES98)  September, 1998.

Lipsitch, Marc: Adaptation on Rugged Landscapes Generated by Iterated Local Interactions of Neighboring Genes. In: Belew & Booker (1991), S. 128 - 135.

Manderick, B; de Weger, M.; Spiessens, P.: The Genetic Algorithm and the Structure of the Fitness Landscape. In: Belew & Booker (1991), S. 143 - 150.

Naftaly, Ury; Intrator, Nathan, Horn, David: Optimal ensemble averaging of neural networks. Comput Neural Syst 8 (1997), S. 283 - 296 (siehe auch: New Journal of Physics, Deutsche Physikalische Gesellschaft & Institute of Physics, ISSN: 1367-2630).

Neri, Filippo: First Order Logic Concept Learning by means of a Distributed Genetic Algorithm. Dissertation, CS, Universität Turin (Italien), 1997.

Nissen, Volker: Evolutionäre Algorithmen, Wiesbaden, 1994.

Rechenberg, Ingo: Evolutionsstrategie '94, Stuttgart, 1994.

Rochet, S.; Venturini, G.; Slimane, M.; El Kharoubi, E.M.: A Critical and Empirical Study of Epistasis Measures for Predicting GA Performances: A Summary. In: Hao et al. (1998).

Sebald, A.; Chellapilla, Kumar: On Making Problems Evolutionarily Friendly Part 1: Evolving the Most Convenient Representations. In: The Seventh International Conference on Evolutionary Programming, EP98, Mar 25-27, 1998a, Mission Valley Marriott, San Diego, CA, S. 271 - 280

Sebald, A.; Chellapilla, Kumar: On Making Problems Evolutionarily Friendly Part 2: Evolving the Most Convenient Representations. In: The Seventh International Conference on Evolutionary Programming, EP98, Mar 25-27, 1998b, Mission Valley Marriott, San Diego, CA, S 281 - 290.

Vassilev, Vesselin K.: An Information Measure of Landscapes. In: Bäck (1997) ICGA7, S. 49 - 56.

Wolpert, D. H.: On Bias plus Variance. In: Neural Computation, 9: 6, S. 1211 - 1243, 1997. (Auch als SFI TR 95-007, Santa Fe Institute, 1995.