Optimierung, also das Maximieren oder Minimieren einer Zielfunktion unter Nebenbedingungen, steht im Zentrum vieler Anwendungen. So ist es wenig erstaunlich, dass Optimierung in unserer Software decídalo eine wichtige Rolle spielt.  Das Text-to-Skills Feature wäre ohne passende Optimierungsalgorithmen ebenso wenig denkbar wie das Projektplanungsmodul.

Den Nutzen generischer Optimierung kann man gut am Beispiel der Projekteinsatzplanung für Consultants verstehen, da sich hier Zielfunktion und Nebenbedingungen mit wechselnden Anforderungen ändern. Das hat zur Folge, dass auch die Software zur Lösung der resultierenden Optimierungsprobleme angepasst werden muss.

Seien x(i,j,k) Variablen, die den Einsatz von Consultant i auf dem Projekt j am Tag k modellieren. Ein naheliegendes Ziel ist, die Auslastung der Consultants zu maximieren. In einem sehr einfachen Modell können Consultants jeden Tag für maximal acht Stunden auf Projekte gebucht werden. In diesem Fall können die Variablen alle Werte zwischen 0 und 8 annehmen und es muss gelten, dass die Summe der Variablen x(i,j,k) für jeden Consultant und jeden Tag über alle Projekte höchstens 8 sein darf. Das Problem wird interessanter, wenn wir weitere Nebenbedingungen hinzunehmen. Meistens steht für jedes Projekt j nur ein gegebenes Budget d(j) an Stunden zur Verfügung, d.h. die Summe der Variablen x(i,j,k) über alle Tage und alle Consultants darf höchstens den Wert d(j) annehmen. In der Praxis kommen viele weitere Nebenbedingungen hinzu, die das Problem schwieriger machen. Hat z.B. Consultant i am Tag k Urlaub, kann er an diesem Tag auf keinem Projekt arbeiten und dementsprechend muss x(i,j,k)=0 für alle Projekte j gelten. In der Zielfunktion maximieren wir nun die Summe der Variablen unter allen Nebenbedingungen. Das resultierende Optimierungsproblem für das obige Beispiel ist ein sogenanntes lineares Programm, zu dessen Lösung viele effiziente Algorithmen bekannt sind.

In einem etwas komplexeren Szenario nehmen wir an, dass Consultant i einen speziellen Skill hat, der in vielen Projekten nachgefragt ist. Ziel könnte es nun sein, den Einsatz des Consultants gleichmäßig über alle Projekte, die seine Qualifikation nachfragen, zu verteilen. Das kann man erreichen, indem man eine Entropiefunktion maximiert. Hier wollen wir die Entropiefunktion nicht näher beschreiben. Wichtig für uns ist nur, dass die Funktion nichtlinear, aber konvex ist. Konvexe Optimierungsprobleme können effizient gelöst werden, aber Software zur Lösung konvexer Probleme ist viel schlechter verfügbar als Software zur Lösung linearer Programme. Oft blieb einem nichts anderes übrig, als eigene Software zur Lösung des Problems zu schreiben. Ändert sich das Problem, z.B. in dem man weitere Nebenbedingungen hinzufügt, muss die Software angepasst werden, was zeitaufwendig ist.

Das ist der Grund, warum wir einen effizienten Lösungsalgorithmus für eine sehr allgemeine Klasse von Optimierungsproblemen implementiert haben. Diesen Algorithmus machen wir mittels einer einfachen Modellierungssprache verfügbar. Mit diesem Ansatz können wir die Entwicklungszeit für viele Optimierungsverfahren dramatisch verkürzen. Es genügt, die zugrundeliegenden Probleme in der Modellierungssprache zu spezifizieren. Die Optimierungssoftware wird automatisch aus der Spezifikation generiert.

Die Kombination aus Modellierungssprache und Lösungsalgorithmen bezeichnen wir als generische Optimierung. Generische Optierung wird schon seit vielen Jahren erfolgreich im Operations Research, also der betrieblichen Planung, eingesetzt.  Die verfügbaren Lösungen skalieren allerdings nicht zu den im maschinellen Lernen auftretenden Problemgrößen, weshalb wir einen eigenen Ansatz zur generischen Optimierung entwickelt haben. Der Ansatz basiert auf unserem Matrix Calculus Algorithmus zum symbolischen Ausrechnen von Gradienten und ist für Anwendungen aus dem maschinellen Lernen mehrere Größenordnungen effizienter als die bislang verwendeten Verfahren. Diesen Ansatz haben wir auf der diesjährigen Conference on Neural Information Processing Systems (NeurIPS) in Vancouver vorgestellt.

Veröffentlichung: GENO — GENeric Optimization for Classical Machine Learning. Proceedings of the 33d Annual Conference on Neural Information Processing Systems (NeurIPS), (2019)