Pruning

aus Wikipedia, der freien Enzyklopädie

Pruning ist der englische Ausdruck für die Beschneidung von abgestorbenen, überreifen, oder aus anderen Gründen unerwünschten Teilen von Bäumen und Sträuchern. In der Informatik wird er oft für Verfahren verwendet, die bewusst bestimmte Informationen ignorieren, um eine höhere Effizienz zu erreichen.

• Bei Suchverfahren verwendet man verschiedene Pruning-Methoden zur Vorwärtsabschneidung von Suchbäumen, wenn der Algorithmus auf Grund der bereits gesammelten Daten weiß (bzw. bei spekulativem Pruning davon ausgeht), dass diese Teilbäume das gesuchte Objekt nicht enthalten (angewandt zum Beispiel bei Schachprogrammen). Wichtige Pruning-Techniken für Minimax- oder Alpha-Beta-Suchen, die zur Lösung von Zwei Personen Nullsummenspiele mit vollständiger Information eingesetzt werden können, sind zum Beispiel:
  • Nullmove Pruning
  • Verified Nullmove Pruning
  • Killer-Heuristik
  • History-Heuristik

• Im Maschinellen Lernen bezeichnet Pruning den Vorgang der Vereinfachung einer gelernten Hypothese, mit dem Ziel, eine Überanpassung (Overfitting) der Hypothese an die Trainings-Daten zu verhindern. Dabei wird zwischen zwei Pruning-Arten unterschieden:
  • Pre-Pruning: Eine Hypothese wird während des Lernvorganges gepruned, wenn durch weiteres Lernen keine Verbesserung mehr abzusehen ist.
  • Post-Pruning: Eine Hypothese wird zuerst vollständig erlernt und nachher gepruned.

Pruning findet insbesondere bei Verfahren zum Lernen von Entscheidungsbäumen Einsatz.

• Bei Forensoftware bewirkt die Einstellung Pruning das automatische Löschen von alten Themen (Topics), um Speicherplatz zu sparen, die CPU-Last zu verringern und dadurch die Schnelligkeit des Forums zu erhöhen.