Jump Like A Squirrel: Optimized Execution Step Order for Anytime Random Forest Inference

Die Arbeit stellt einen neuen Ansatz vor, der Random Forests als Anytime-Algorithmen auf der Granularität einzelner Entscheidungsschritte implementiert und durch heuristische Schrittordnungen wie die „Backward Squirrel Order" die Vorhersagegenauigkeit bei unterbrochener Inferenz auf ressourcenbeschränkten Systemen signifikant optimiert.

Das Wesentliche

Die Grundidee: Der Wald, der nie fertig wird

Stell dir vor, du hast einen riesigen Wald voller 100 Wegweiser (das ist der „Random Forest"). Jeder Wegweiser ist ein Baum, der dir sagt, ob du links oder rechts abbiegen sollst, um dein Ziel zu erreichen (z. B. „Ist diese E-Mail Spam?" oder „Ist das Bild eine Katze?").

Normalerweise musst du einen ganzen Baum von oben bis unten durchlaufen, um eine Antwort zu bekommen. Wenn du aber nur wenige Sekunden Zeit hast (weil dein Handy Akku spart oder du im Stau stehst), hast du ein Problem:

• Der alte Weg: Du fängst einen Baum an, läufst ihn komplett durch, machst den nächsten fertig usw. Wenn die Zeit abläuft, hast du vielleicht nur 3 Bäume fertig. Die restlichen 97 Bäume? Die ignorierst du komplett. Alles, was du in den 3 Bäumen schon gelernt hast, ist gut, aber du hast die Hälfte der Information in den anderen Bäumen, die du gerade nicht durchlaufen konnt, einfach verworfen.

Die neue Idee: Der Eichhörnchen-Sprung

Die Autoren dieses Papers sagen: „Warum müssen wir einen ganzen Baum fertig machen, bevor wir zum nächsten springen?"

Stell dir vor, du bist ein Eichhörnchen. Du kletterst nicht einen Baum komplett runter, bevor du zum nächsten springst. Stattdessen machst du einen kleinen Sprung auf dem ersten Baum, dann einen Sprung auf dem zweiten, dann auf dem dritten.

• Wenn die Zeit abläuft, hast du vielleicht 50 kleine Sprünge auf 50 verschiedenen Bäumen gemacht.
• Der Clou: Du hast bei jedem Sprung schon eine kleine Information gesammelt. Du verlierst nichts! Du kannst sofort eine Antwort geben, die auf all diesen kleinen Sprüngen basiert.

Das Problem: In welcher Reihenfolge springen?

Jetzt kommt die große Frage: In welcher Reihenfolge springen die Eichhörnchen?
Gibt es einen „perfekten" Weg, um die Bäume zu erklimmen, damit man bei jeder beliebigen Zeitstopp-Möglichkeit die beste Antwort hat?

Die Forscher haben drei Strategien entwickelt:

1. Der „Optimale Plan" (Optimal Order):

   • Wie es funktioniert: Ein super-intelligenter Computer rechnet alles durch und findet den absolut perfekten Sprungplan.
   • Das Problem: Das dauert ewig. Bei einem großen Wald müsste der Computer länger rechnen als das Universum alt ist, um den Plan zu finden. Das ist wie wenn du für eine 10-minütige Fahrt eine Route planst, die 10 Jahre dauert, nur um 1 Minute zu sparen.

2. Der „Vorwärts-Eichhörnchen-Plan" (Forward Squirrel Order):

   • Wie es funktioniert: Das Eichhörnchen schaut nach vorne. „Welcher nächste Sprung bringt mir jetzt gerade die meiste Sicherheit?" Es springt dorthin, wo es am meisten bringt, und wiederholt das.
   • Das Ergebnis: Es ist schnell, aber nicht immer perfekt.

3. Der „Rückwärts-Eichhörnchen-Plan" (Backward Squirrel Order) – Der Gewinner:

   • Wie es funktioniert: Das ist der Trick! Stell dir vor, du weißt, wie der Weg am Ende aussieht (wenn alle Bäume fertig sind). Jetzt gehst du rückwärts vom Ziel aus. Du fragst dich: „Welcher letzte Sprung war der wichtigste, um das Ergebnis zu verbessern?"
   • Die Analogie: Stell dir vor, du baust ein Haus. Der Vorwärts-Plan fragt: „Was bauen wir als Erstes?" Der Rückwärts-Plan fragt: „Was brauchen wir als Letztes, damit das Haus steht?" Oft ist es klüfer, zuerst das Fundament zu legen (die wichtigsten Schritte), auch wenn man das Haus von oben betrachtet.
   • Das Ergebnis: Dieser Plan ist super schnell zu berechnen (wie ein einfacher Daumenkino-Trick) und liefert fast genauso gute Ergebnisse wie der perfekte, aber unmögliche Plan.

Was haben die Forscher herausgefunden?

Sie haben das auf echten Daten getestet (z. B. um Spam-E-Mails zu erkennen oder Bilder zu klassifizieren).

• Ergebnis: Wenn man die Bäume wie Eichhörnchen springen lässt, wird die Vorhersage mit jedem Sprung besser.
• Der Vergleich: Der „Rückwärts-Eichhörnchen-Plan" ist 99 % so gut wie alle anderen dummen Methoden (wie einfach nur zufällig springen oder Baum für Baum abzuarbeiten).
• Der Vergleich mit dem „Perfekten Plan": Er ist 94 % so gut wie der theoretisch perfekte Plan, braucht aber nur einen winzigen Bruchteil der Rechenzeit, um erstellt zu werden.

Fazit für den Alltag

Stell dir vor, du hast eine Aufgabe, die du nicht zu 100 % fertig machen kannst, weil die Zeit knapp ist.

• Die alte Methode: Du machst 3 Aufgaben komplett fertig und ignorierst den Rest.
• Die neue Methode („Jump Like A Squirrel"): Du machst von jeder Aufgabe ein kleines Stück. Wenn die Zeit abläuft, hast du von allen Aufgaben etwas verstanden und kannst eine sehr gute Gesamtschätzung abgeben.

Die Autoren haben gezeigt, dass man durch geschicktes „Springen" zwischen den Aufgaben (den Bäumen) immer die bestmögliche Antwort bekommt, egal wie kurz die Zeit ist. Und der „Rückwärts-Eichhörnchen-Plan" ist der beste Weg, um diesen Sprungplan zu finden.

Technische Zusammenfassung

1. Problemstellung

Random Forests (Zufallswälder) und Entscheidungsbäume sind aufgrund ihrer Effizienz und Kompaktheit beliebte Modelle für Klassifizierungsaufgaben auf ressourcenbeschränkten Systemen. Ein zentrales Problem in solchen Umgebungen ist jedoch, dass die verfügbare Ausführungszeit für die Inferenz oft nicht ausreicht, um das gesamte Modell vollständig abzuarbeiten.

Bestehende „Anytime"-Ansätze (Algorithmen, die zu jedem Zeitpunkt ein brauchbares Ergebnis liefern) für Random Forests arbeiten auf der Granularität ganzer Bäume: Sie führen Bäume nacheinander aus und stoppen nach einem bestimmten Baum. Der Nachteil hierbei ist, dass alle Informationen, die während der Abarbeitung des aktuell laufenden Baums (innerhalb der inneren Knoten) gesammelt wurden, verloren gehen, sobald die Ausführung vorzeitig gestoppt wird.

Da bei Entscheidungsbäumen die Vorhersagekonfidenz mit jedem weiteren Schritt (Knoten) steigt, wäre es ideal, die Ausführung auf der Granularität einzelner Schritte innerhalb der Bäume zu unterbrechen. Dies erfordert jedoch eine neue Strategie zur Festlegung der Ausführungsreihenfolge (Step Order), um die mittlere Genauigkeit über alle möglichen Unterbrechungszeitpunkte hinweg zu maximieren.

2. Methodik

Das Paper schlägt vor, Random Forests als Anytime-Algorithmen auf der Ebene einzelner Schritte (Knoten) in den Bäumen zu realisieren. Dabei wird die Vorhersageinformation in den inneren Knoten (basierend auf den Trainingsdaten, die diesen Knoten erreichen) gespeichert, sodass eine Vorhersage auch vor Erreichen eines Blattknotens möglich ist.

Um die mittlere Genauigkeit zu optimieren, wird die Reihenfolge, in der Schritte in den verschiedenen Bäumen des Waldes ausgeführt werden, als Optimierungsproblem formuliert. Es werden drei Hauptansätze vorgestellt:

A. Optimal Order (Optimale Reihenfolge)

Dieser Ansatz sucht diejenige Schrittfolge, die die mittlere Genauigkeit auf einem speziellen „Ordering-Set" (Validierungsdatensatz) maximiert.

• Modellierung: Der Suchraum wird als gewichteter, gerichteter azyklischer Graph (DAG) modelliert. Ein Knoten im Graph repräsentiert einen Zustand (Anzahl der Schritte in jedem Baum). Kanten repräsentieren einen weiteren Schritt in einem der Bäume.
• Algorithmus: Die Suche nach dem Pfad mit maximaler mittlerer Genauigkeit wird als Suche nach dem Pfad mit minimaler mittlerer Ungenauigkeit formuliert. Dijkstras Algorithmus wird verwendet, um den optimalen Pfad zu finden.
• Komplexität: Die Laufzeit ist exponentiell bezüglich der Baumtiefe und der Anzahl der Bäume ($O((d+1)^t \cdot \log((d+1)^t))$), was dies für große Wälder unpraktisch macht.

B. Squirrel Order (Heuristische Ansätze)

Da die Berechnung der Optimalen Reihenfolge für große Wälder nicht skalierbar ist, werden zwei polynomielle Heuristiken entwickelt, die auf einem gierigen (greedy) Tiefensuch-Prinzip basieren:

1. Forward Squirrel Order: Beginnt beim Startzustand (0 Schritte) und wählt iterativ den nächsten Schritt aus, der die höchste Genauigkeit für den nächsten Zustand liefert (Vorwärtsrichtung).
2. Backward Squirrel Order: Beginnt beim Endzustand (alle Schritte abgeschlossen) und arbeitet rückwärts bis zum Startzustand. In jedem Schritt wird der vorherige Zustand gewählt, der die höchste Genauigkeit für den aktuellen Zustand liefert (Rückwärtsrichtung).

• Vorteil: Diese Methoden müssen den vollständigen Graphen nicht explizit konstruieren, sondern berechnen nur die relevanten Nachfolgezustände. Die Laufzeit beträgt $O(d \cdot t^2)$.

C. Technische Implementierung

Für die praktische Umsetzung wird vorgeschlagen, die Inferenz nicht als rekursiven Aufruf, sondern als Schleife über ein Array zu realisieren, das die Schrittfolge speichert. Ein Index-Array hält den aktuellen Knoten in jedem Baum. Bei einem vorzeitigen Abbruch (Timer-Interrupt) werden die Vorhersagevektoren der aktuellen Knoten aller Bäume aggregiert, um das Endergebnis zu berechnen. Dies ist effizienter als herkömmliche if-else-Implementierungen, da der Sprung zwischen Bäumen einfacher zu handhaben ist.

3. Wichtige Beiträge

• Granularitätswechsel: Erstmalige Realisierung von Random Forests als Anytime-Algorithmen auf der Granularität einzelner Schritte in Bäumen, anstatt ganzer Bäume. Dies verhindert den Verlust von bereits gesammelter Vorhersageinformation.
• Optimierungsframework: Einführung des Problems der Schrittfolgenoptimierung zur Maximierung der mittleren Genauigkeit unter der Annahme einer gleichverteilten Abbruchwahrscheinlichkeit.
• Algorithmen: Entwicklung der Optimal Order (exakte Lösung) und der Squirrel Order-Heuristiken (Forward und Backward) mit polynomieller Laufzeit.
• Implementierung: Demonstration einer effizienten technischen Umsetzung, die es erlaubt, zu jedem Zeitpunkt eine sinnvolle Vorhersage zu liefern.

4. Ergebnisse

Die Evaluation erfolgte auf 9 Datensätzen (z. B. Adult, MNIST, Covertype) mit verschiedenen Baumzahlen und Tiefen auf Hochleistungs-CPUs und eingebetteten Systemen (ESP32).

• Genauigkeitsverlauf: Die Genauigkeit steigt mit jedem zusätzlichen Schritt an, was die Eignung von Random Forests für Anytime-Inferenz bestätigt.
• Vergleich der Reihenfolgen:
  • Die Backward Squirrel Order erreicht ca. 94 % der Leistung der Optimal Order und ca. 99 % im Vergleich zu allen anderen getesteten Reihenfolgen (einschließlich intuitiver Ansätze wie Depth-First oder Breadth-First).
  • Die Forward Squirrel Order performt etwas schlechter als die Backward-Variante.
  • Intuitive Ansätze (wie Depth-Order oder Pruning-basierte Reihenfolgen) schneiden je nach Datensatz (binär vs. multi-klass) unterschiedlich gut ab, sind aber weniger robust als die Squirrel-Methoden.
• Laufzeit: Die Generierung der Backward Squirrel Order ist deutlich schneller als die der Optimal Order und skaliert gut auf große Wälder, während die Optimal Order bereits bei moderater Größe (ca. 8 Bäume) an Speicher- und Zeitgrenzen stößt.
• Zeit vs. Schritte: Es wurde eine weitgehend lineare Beziehung zwischen der Anzahl der Schritte und der Ausführungszeit festgestellt, was die Abstraktion von Schritten als Zeitmaß rechtfertigt.

5. Bedeutung und Fazit

Das Paper zeigt, dass Random Forests durch die Speicherung von Vorhersageinformationen in inneren Knoten und die Optimierung der Ausführungsreihenfolge effizient als Anytime-Algorithmen eingesetzt werden können.

Der Backward Squirrel Order stellt einen besonders vielversprechenden Ansatz dar: Er bietet eine nahezu optimale mittlere Genauigkeit (ähnlich der theoretisch besten Lösung), ist jedoch in der Generierung extrem schnell und skalierbar. Dies ermöglicht den Einsatz von Random Forests in Echtzeitsystemen mit unvorhersehbaren Zeitbudgets, ohne dass die Vorhersagequalität bei vorzeitiger Unterbrechung drastisch einbricht. Die Methode ist besonders wertvoll für ressourcenbeschränkte Umgebungen, wo eine garantierte Ausführungszeit nicht gegeben ist.