title: Structured, Constrained and Creative Learning
Creators: name: Vlastelica, Marin
Publisher: name: Universität Tübingen
Year: 2025
Subjects: subject: Operante Konditionierung , Maschinelles Lernen , Deep Learning , Künstliche Intelligenz , Generalisierung
subject: 000
subject: 004
subject: 500
subject: Implizite Schichten
subject: Kombinatorische Optimierung
subject: Imitation
subject: reinforcement learning
subject: imitation
subject: generalization
subject: combinatorial optimization
subject: implicit layers
subject: deep learning

description: Das Gebiet des Deep Learning hat in den letzten Jahren einen erheblichen Wandel durchlaufen. Verbesserungen auf der Ebene der Modellarchitekturen haben durch ihre spezifischen induktiven Verzerrungen und dank ihrer funktionalen Form leistungsstarke Generalisierungsfähigkeiten für neuronale Netze ermöglicht. Aufgrund der beträchtlichen Menge an Daten und Rechenressourcen haben sie eine weite Verbreitung gefunden und zeigen beeindruckende Leistungen bei einer Vielzahl von Aufgaben wie Sprach- und Bildgenerierung. Darüber hinaus haben Deep-Learning-Modelle die Fähigkeit gezeigt, selbst in Spielen, die komplexes Denkvermögen erfordern, menschliche Spieler zu übertreffen. Trotzdem gibt es in wichtigen Anwendungen viele ungelöste Probleme. Verschiedene Probleme erfordern ein Denken in Räumen, die reich an Struktur sind und gleichzeitig stark eingeschränkt. Ein einfaches Beispiel ist das Planungsproblem, das keine erschöpfende Suche nach allen möglichen Abfolgen erreichbarer Zustände erfordert, sondern eine Suche nach gültigen Pfaden, die möglicherweise nur eine kleine Teilmenge bilden. Dies deutet darauf hin, dass die Generalisierungsfähigkeit von Lernsystemen durch die Einbeziehung von strukturierter Vorhersage und Einschränkungen verbessert werden kann. Im Gegensatz dazu ist es für diese Systeme unerlässlich, Flexibilität und Innovation zu zeigen, was im Widerspruch zu Einschränkungen ihrer Vorhersagen steht. Kreativität und Anpassungsfähigkeit sind in der Tat wesentliche Elemente der Intelligenz. Sie befähigen Systeme, neue Lösungen zu formulieren und sich effizient an neue oder unvorhergesehene Umstände anzupassen. In dieser Arbeit versuchen wir, Struktur und Einschränkungen einzuführen, damit intelligente Systeme uns plausible Vorschläge zur Entscheidungsfindung machen können, während sie dennoch anpassungsfähig bleiben. Im ersten Teil betrachten wir das Hinzufügen von Struktur durch kombinatorische implizite Schichten und zeigen, dass dies eine wichtige induktive Verzerrung für die Bewältigung von Problemen mit “verborgener” kombinatorischer Struktur ist. Um dies zu erreichen, ist es notwendig, eine Parameter-Aktualisierungsrichtung zu verwenden, die sich von der traditionellen Gradientenabstiegsrichtung unterscheidet, da die Zielfunktion aufgrund der endlichen Natur der zulässigen Menge stückweise konstant wird. Es stellt sich heraus, dass es einen effizienten Weg gibt, eine informative Aktualisierungsrichtung zu berechnen, die eine Ableitung einer stückweise affinen Interpolation der ursprünglichen stückweise konstanten Funktion ist. Dies erfordert nur einen zusätzlichen Aufruf des kombinatorischen Solvers im Backpropagation. Wir nennen diese Methode BBBP, um hervorzuheben, dass wir keine Informationen über das zugrunde liegende kombinatorische Problem verwenden oder versuchen, es aufzurollen und zu differenzieren. Eine Alternative dazu besteht darin, die implizite Schicht im Rückwärtsgang als negativen Identitätsblock zu behandeln, was eng mit dem ursprünglichen Ansatz der stückweise affinen Interpolation verbunden ist. Wie wir sehen werden, enthalten viele praktische Anwendungen von Interesse kombinatorische Strukturen. Einige der Problemstellungen, die wir untersuchen werden, sind die Planung von Bildern und die Optimierung von Rang-basierten Metriken. Im zweiten Teil richten wir unser Augenmerk auf eine wichtige Komponente intelligenter Systeme, die sequentielle Entscheidungsfindung. Wir untersuchen sowohl Online-Szenarien, in denen eine Policy mit der Umgebung interagieren darf, um ihre Verhaltensweise zu verbessern, als auch das Offline-Setting, in dem ein fester Datensatz gegeben ist und die Aufgabe darin besteht, eine optimale Policy zu extrahieren. Im Online-Setting erweist sich ein modellbasierter Ansatz als besonders vorteilhaft, um Sicherheitsbeschränkungen und Risikoaversion durch ein Trajektorienoptimierungsverfahren einzuführen, das die Trennung von epistemischer und aleatorischer Unsicherheit nutzt. Für diesen Fall wird die Policy implizit gegeben und löst ein Optimierungsproblem, um eine Aktion zu erzeugen, wobei der Vorteil darin besteht, dass wir nur die Modelldynamik lernen müssen, was mit beliebigen Daten erfolgen kann. Durch die Nutzung von epistemischen Boni und einer Risikostrafe findet diese Methode ein Gleichgewicht zwischen Exploration und Ausbeutung und erleichtert so das effiziente Lernen des Modells. Im Gegensatz dazu ist das Offline-Setting interessant aus der Perspektive, dass es dem ähnelt, was wir heute sehen, große Modelle, die Daten aus verschiedenen Quellen nutzen. Bis jetzt lag der Fokus darauf, Policies aus den Daten zu extrahieren, die nicht halluzinieren und gut außerhalb der Verteilung generalisieren. Jedoch wurde die Vielfalt solcher Policys vernachlässigt, und wir argumentieren, dass intelligente Systeme kreative Problemlöser sein müssen, um nützlich zu sein, da viele Probleme mehrere Lösungen haben, von denen einige mehr oder weniger robust sein könnten. Dies gilt insbesondere, wenn Demonstrationen von externen Quellen wie einem Menschen stammen. Wir bestimmen dieses Problem als die Nachahmung eines Lernproblems, bei dem wir Zugang zu Offline-Aktionen haben, die nicht von Expertendemonstrationen stammen, sondern von einer beliebigen Policy. Der Experte darf uns nur Sequenzen von Zuständen demonstrieren. Dies erfordert eine andere Strategie, da das Fehlen direkter Anweisungen von optimalen Aktionen den Lernprozess erschwert. Die Formulierung beinhaltet die Maximierung eines Diversitätsziels unter f-Divergenz Einschränkungen für Zustandsbelegungsverteilungen. Durch geschickte Nutzung der Fenchel-Dualität lösen wir ein duales Problem, um Importance Ratios zu erhalten, die es uns ermöglichen, Erwartungen in Bezug auf optimale Policy-Zustands-Aktionsbelegungen zu schätzen. Dies validieren wir in einem Sim-to-Real Quadruped-Benchmark. Abschließend bestätigen wir, dass die Einführung dieser Arten von Struktur und Einschränkungen für dateneffiziente Generalisierung und robuste Entscheidungsfindung notwendig ist.
description: The field of deep learning has undergone a substantial transformation in recent years, with improvements being made on the level of model architectures which through specific inductive biases thanks to their functional form give powerful generalization capabilities to neural networks. Due to the substantial amount of data and computing resources, they have received wide-spread adoption with impressive performance on a wide range of tasks such as language and image generation. Furthermore, deep learning models have shown the capability to even surpass human players in games that require higher-level reasoning capabilities. Despite this, there are many outstanding issues in important applications. Various problems require reasoning in spaces that are rich in structure and are highly constrained, a simple example is the planning problem which doesn’t require exhaustive search of all possible sequences of visited states, but rather a search over valid paths, which form a possibly small subset. This indicates that the generalization capability of learning systems can be enhanced by incorporating structured prediction and constraints. Conversely, it is imperative for these systems to demonstrate flexibility and innovation, which is somewhat at odds with constraining their predictions. Creativity and adaptability are, indeed, quintessential elements of intelligence, they empower systems to formulate novel solutions and adapt efficiently to new or unforeseen circumstances. In this work, we attempt to introduce structure and constraints such that intelligent systems can provide us with plausible suggestions in order to make critical decisions, while still remaining adaptable. In the first part we consider adding structure by means of combinatorial implicit layers, showing that this is a critical inductive bias for dealing with problems containing “hidden” combinatorial structure. To achieve this, it is necessary to employ a parameter update direction distinct from the traditional gradient descent direction, as the objective function becomes piecewise-constant given the finite nature of the feasible set. It turns out that there is an efficient way to compute an informative update direction, which is a derivative of a piecewise-affine interpolation of the original piecewise-constant function. This involves only one additional call to the combinatorial solver on the backward pass. We name this method Blackbox Backpropagation (BBBP), to highlight the fact that we don’t make use of any information about the underlying combinatorial problem, or try to unroll it and differentiate. An alternative to this will be treating the implicit layer as a negative identity block on the backward pass, which is connected intimately to the initial piecewise-affine interpolation approach. As we shall see, many practical applications of interest contain combinatorial structure, some of the settings that we shall explore are planning from images and optimizing rank-based metrics. In the second part, we shift our attention to an important component of intelligent systems, sequential decision-making. We examine both online scenarios, where a policy is allowed to collect samples from the environment in order to improve, and the offline setting, where one fixed dataset is given and the task is to extract an optimal policy. In the online setting, employing a model-based approach emerges as particularly advantageous for introducing safety constraints and risk-averseness through a trajectory optimization method that makes use of epistemic and aleatoric uncertainty separation. For this case, the policy is given implicitly and is solving an optimization problem to produce an action, the benefit of this being that we only need to learn model dynamics, which can be done from arbitrary data. By making use of epistemic bonus and a risk penalty, this method strikes a balance between exploration and exploitation, facilitating efficient learning of the model. In contrast, the offline setting is interesting from the perspective that it resembles much of what we see today, large models making use of data collected from various sources. Up until now, the focus was on extracting policies from the data that do not hallucinate and generalize well out-of-distribution. However, the diversity of such policies has been neglected, and we argue that intelligent systems need to be creative problem solvers in order to be useful, since many problems have multiple solutions, some of which might be more or less robust. This is in particular true when demonstrations are coming from external sources, such as a human. We frame this problem as an imitation learning problem, where we have access to offline actions which are not coming from expert demonstrations, but rather from an arbitrary behavior policy. The expert is only allowed to demonstrate by showing us a sequences of states. This scenario necessitates a different strategy, as the absence of direct guidance from optimal actions complicates the learning process. Concretely, the formulation involves maximizing a diversity objective subject to f-divergence constraints on state occupancy distributions. By clever use of Fenchel duality, we solve a dual problem to obtain importance ratios that allow us to estimate expectations with respect to optimal policy state-action occupancies. This we validate in a sim-to-real quadruped benchmark. Finally, we confirm that introducing these types of structure and constraints is necessary for data-efficient generalization and robust decision making.