Hat ein Algorithmus mit Musik zu tun?
Februar 29, 2020
Aus dem Unterricht des CAS AI Management mit Dozent Dr. Tim Nonner berichtet Student Lorand Frank:
Ein Algorithmus hat nichts mit Musik am Hut….aber was ist denn ein Algorithmus (nachfolgend im Blog mit AR abgekürzt) und für was brauchen wir es in AI?
Wir brauchen AR um Modelle zu trainieren!
…und was ist ein AR: Anbei die englische Definition “Formalized steps to solve a problem”.
Und für AI brauchen wir eine spezielle Klasse von Algorithmen.
Wir kennen alle die Bedienungsanleitungen von Ikea oder jeder von uns hat bereits mit einem Kochrezept ein leckeres Menu gezaubert.
Gleich verhält es sich mit einer Maschine, die eine haargenaue Instruktion benötigt, um das gewünschte Ergebnis liefern zu können.
Die Vorteile liegen dabei auf der Hand mit einem optimierten Algorithmus:
- die Maschine liefert die Ergebnisse viel schneller
- die Ressourcen (z.B. CPU) werden bestmöglich geschont
- die Maschine nimmt dem Menschen die repetitive Arbeit ab
- die politische Brisanz wird entschärft durch einen immer gleichen Algorithmus im gleichen Massstab
und die subjektive menschliche Sicht (Bias) dadurch rausgenommen.
Ein Optimierungs-Algorithmus im AI wird auch als ‘Needle-in-Haystack‘ Problem betrachtet. Im Alltag findet sich ein solcher AR im automatisierten Trading, Empfehlungssystem, Zug-Fahrplan, der Internet Suche und Online Werbung uvm.
Dabei läuft der AR vom Prinzip immer gleich ab.
Hier einige Beispiele von Algorithmen:
Haystack Problems Examples
Der einfachste AR ist Brute Force: probieren, messen und aufhören sobald die beste gefunden ist.
Der grosse Nachteil: dieser AR kann schnell teuer werden und kann u.U. auch sehr viel Rechenzeit beanspruchen.
Folgende 4 Grund-AR-Designprinzipien gelten für alle AI-Algorithmen:
Four Algoritthm Design Principles to Rule All
Im obigen Beispiel wird ein simplizierter Navigationspfad angegeben und die 4 Design Prinzipien anhand des Beispiels von Tim erklärt:
- Die Brute Force Methode ist in diesem Beispiel praktikabel.
- Die Methode Greedy würde bedeuten, immer die kleinere Kante bis zum nächsten Knotenpunkt zu wählen.
Für echte Navigationssysteme wäre diese Methode zu langsam. - Mit Local Search wird irgendwo angefangen und mit einer Lösung gestartet und diese sukzessive verbessert.
In diesem Beispiel wäre die lokale Suche nicht mehr auf den beste Lösung gestossen falls es die obersten Kanten gewählt hätte. - Dynamic Programming unterteilt das Probleme in Subteile und löst diese Stück für Stück.
Zusammengefasst ist ein guter AR möglichst einfach, hat möglichst wenig Code und ist effizient.
Spielerisch wurde uns anhand des Cases “Sorting” die Programmierung eines effizienten AR von Tim demonstriert.
Dabei hatten wir die Chance, selbständig in der Klasse herauszutüfteln. Dank der Anleitung von Tim hatten wir schlussendlich den Dreh raus.
Sortierung eines Algorithm im Frontalunterricht
Weitere Problemkreise wie Matching, Inventory Management, Yaos MinMax Principle und Machine Learning gaben uns einen erweiterten Einblick in die logische Welt der ARs. Dabei kämpft der AR immer gegen den Worst Case und gegen Big Numbers. Daher sollte das richtige AR-Prinzip sorgfältig und klug gewählt sein, damit wir die Maschine nicht in endlose Kalkulationen schicken. Gescheite Leute haben bereits den Nobelpreis für AR erhalten (z.B. Shapley & Roth “for the theory of stable allocations and the practice of market design”).
Der interessante Nachmittag wurde mit dem Inventory Management gekrönt wo wir in Gruppen gegeneinander und gegen den optimierten AR antreten durften. Dabei konnten wir nachvollziehen, welche Faktoren für eine möglichst gutes Ergebnis relevant sind.
Danke Tim für deine leidenschaftlichen Ausführungen und die vielen spannenden Momente, die wir erleben durften.