TY  - THES
AB  - Die Qualität und Laufzeit eines Algorithmus hängen maßgeblich von seinen internen Parametern ab, die in der Regel vom Benutzer vorab festgelegt werden müssen. Da es oft eine herausfordernde oder sogar unlösbare Aufgabe ist, optimale Werte für diese Parameter zu identifizieren, hat sich das Forschungsfeld der automatischen Algorithmenkonfiguration (engl. Algorithm Configuration) entwickelt. Allerdings fehlen den meisten bestehenden Methoden theoretische Garantien bezüglich der Qualität ihrer vorgeschlagenen Parameterkonfigurationen, was es den Nutzern erschwert, den Ergebnissen zu vertrauen. Im Gegensatz dazu bieten die wenigen Methoden, die nachweisbare Qualitätsgarantien für ihre Konfigurationen liefern, oft nicht die Ressourceneffizienz heuristischer Ansätze. Ein Ansatz zur Herleitung theoretischer Garantien besteht darin, Methoden aus gut erforschten theoretischen Kontexten, wie Mehrarmigen Banditen (engl. Multi-Armed Bandits), auf Algorithmenkonfigurationsprobleme anzuwenden und anzupassen. Solche Garantien stärken das Vertrauen der Nutzer in die Ergebnisse und stellen Ressourceneffizienz sicher, wenn das vom Konfigurator benötigte Budget eng mit der unteren Grenze übereinstimmt, die für die Lösung des Problems erforderlich ist. Dadurch bleibt die Vertrauenswürdigkeit gewahrt, ohne dass übermäßige Rechenkosten entstehen. Allerdings macht die Vielzahl an Varianten von Mehrarmigen Banditen – die für unterschiedliche Parallelisierungsmethoden, Beobachtungen oder Kriterien zur Auswahl des besten Arms konzipiert wurden – es schwierig, die geeignetste Methode für Algorithmenkonfiguration zu identifizieren. Zudem sollte ein idealer Konfigurator in der Lage sein, eine Vielzahl von Szenarien abzudecken, wie beispielsweise verschiedene Arten von Beobachtungen. Während spezialisierte Bereiche der Algorithmenkonfiguration, wie die Hyperparameteroptimierung (engl. Hyperparameter Optimization), bereits von Mehrarmigen Banditen-basierten Methoden wie Hyperband profitieren, die in der Praxis gut funktionieren und mit theoretischen Garantien ausgestattet sind, existiert für die allgemeinere Algorithmenkonfiguration derzeit keine vergleichbare Methode. Eine Herausforderung bei der Entwicklung von Algorithmenkonfigurationsmethoden mit theoretischen Garantien besteht darin, dass strikte Einhaltung theoretischer Grenzen nicht immer zu ressourceneffizienten Verfahren führt. Insbesondere die fehlende Kenntnis des Parameterkonfigurationsraums erfordert eine umfassende Exploration, was oft zu einer konservativ hohen Stichprobenanzahl führt. Diese Arbeit entwickelt Mehrarmige Banditen-basierte Algorithmenkonfigurationsmethoden in zwei Richtungen weiter, um sowohl die Ressourceneffizienz als auch die Vertrauenswürdigkeit zu verbessern. Erstens schlagen wir ein allgemeines Mehrarmiges Banditen-Framework vor und wenden es auf das Algorithmenkonfigurationsproblem an, während wir die Ressourceneffizienz durch theoretisch abgeleitete Budgetgrenzen wahren. Zweitens passen wir den bestehenden Hyperparameteroptimierungsalgorithmus Hyperband einschließlich seiner Mehrarmigen Banditen Subroutine Successive Halving an, um die Ressourceneffizienz weiter zu steigern und gleichzeitig die Vertrauenswürdigkeit durch theoretische Einschränkungen sicherzustellen. Konkret führen wir ein allgemeines kombinatorisches Banditen-Framework ein, bei dem in jedem Zeitschritt eine feste, aber zufällig große Menge von Armen parallel gespielt wird. Dieses Framework unterstützt sowohl numerische Belohnungen als auch präferenzbasierte Beobachtungen und identifiziert nachweislich einen optimalen Arm, wenn das verfügbare Budget für Armziehungen ausreichend groß ist. Darüber hinaus entspricht das erforderliche Budget der abgeleiteten unteren Grenze für solche Algorithmen, bis auf einen logarithmischen Faktor. Wir haben diese Methode zudem auf Algorithmenkonfiguration erweitert und die theoretischen Garantien übertragen. Insbesondere haben wir bewiesen, dass unser vorgeschlagener Konfigurator mit hoher Wahrscheinlichkeit eine nahezu optimale Konfiguration findet, wenn das Budget ausreichend ist, und empirisch gezeigt, dass unsere Methode die Leistungslücke zwischen heuristischen und theoretisch fundierten Konfiguratoren weiter schließt. Darüber hinaus stellt diese Arbeit eine Modifikation der bestehenden Mehrarmigen Banditenmethode Successive Halving (SHA) vor, die es ermöglicht, Beobachtungen aus vorherigen Läufen mit kleineren Budgets wiederzuverwenden. Dadurch werden nur minimale neue Stichproben benötigt. Wir haben gezeigt, dass dieselben theoretischen Garantien für den zurückgegebenen Arm gelten, als würde der Algorithmus von Grund auf mit vollständig neuen Stichproben ausgeführt. Außerdem haben wir diese Garantien mit denen verglichen, die wir für asynchrone Erweiterungen von SHA hergeleitet haben, die bisher nicht analysiert wurden. Schließlich haben wir unseren Algorithmus als Subroutine innerhalb des Hyperparameteroptimierungsgerüst Hyperband integriert, eine theoretische Analyse durchgeführt und seine verbesserte Effizienz durch experimentelle Studien validiert.
AU  - Brandt, Jasmin
CY  - Paderborn
DO  - 10.17619/UNIPB/1-2270
DP  - Universität Paderborn
LA  - eng
N1  - Tag der Verteidigung: 19.05.2025
N1  - Universität Paderborn, Dissertation, 2025
PB  - Veröffentlichungen der Universität
PY  - 2025
SP  - 1 Online-Ressource (xii, 164 Seiten)
T2  - Institut für Informatik
TI  - Multi-armed bandits for trustworthy and resource-efficient algorithm configuration
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:466:2-54833
Y2  - 2025-07-09T00:17:12
ER  -