Ein Algorithmus zum Erlernen von geschalteten linearen Dynamiken aus Daten

Wir stellen einen Algorithmus zum Erlernen geschalteter linearer dynamischer Systeme in diskreter Zeit aus verrauschten Beobachtungen des vollständigen Zustands oder Ausgangs des Systems vor. Geschaltete lineare Systeme verwenden mehrere lineare dynamische Modi, um die Daten innerhalb einer gewünschten Toleranz anzupassen. Sie treten in Anwendungen in Robotik und cyber-physischen Systemen auf ganz natürliche Weise auf. Das Erlernen geschalteter Systeme aus Daten ist ein NP-schweres Problem, das dem k-linearen Regressionsproblem, bei dem k > 1 lineare Modelle an die Daten angepasst werden, nahezu identisch ist. Ein direkter Mixed-Integer-Linear-Programming-(MILP)-Ansatz führt zu einer Zeitkomplexität, die exponentiell in der Anzahl der Datenpunkte ist. In diesem Papier modifizieren wir die Problemformulierung, sodass ein Algorithmus entsteht, der linear in der Größe der Daten ist, während er exponentiell in der Anzahl der Zustandsvariablen und der gewünschten Anzahl der Modi bleibt. Dazu kombinieren wir klassische Ideen aus der Ellipsoidmethode zur Lösung konvexer Optimierungsprobleme mit bekannten Orakel-Trennungsergebnissen in der nicht-glatten Optimierung. Wir demonstrieren unseren Ansatz anhand einiger Mikrobenchmarks und einiger interessanter realer Probleme. Unsere Auswertung legt nahe, dass die Vorteile dieses Algorithmus auch gegenüber hochoptimierten handelsüblichen MILP-Solvern praktisch nutzbar sind.