Grundlagen Statistik & Algorithmen, Teil 8

Der Approximationsalgorithmus

| Autor / Redakteur: Michael Matzer / Nico Litzel

Beispiel für einen maximalen Schnitt
Beispiel für einen maximalen Schnitt (Bild: / Miym / CC BY-SA 3.0)

Für verschiedene Probleme lassen sich nur durch Annäherung bzw. Approximation optimale Lösungen finden. Durch einen geeigneten Approximationsalgorithmus versuchen Informatiker, sich dem optimalen Ergebnis anzunähern, so etwa in der Graphentheorie, die Beziehungen in Netzwerken darstellt.

In der Informatik und der Betriebswirtschaftslehre sind Approximationsalgorithmen effiziente Berechnungsmethoden, um angenäherte Lösungen für NP-harte Optimierungsprobleme zu finden. Diese Lösungen müssen beweisbare Garantien hinsichtlich der Entfernung der gelieferten Lösung von der optimalen vorlegen.

„Im Banking werden Approximationsalgorithmen für das Kredit-Scoring genutzt“, sagt Benjamin Aunkofer, Chief Data Scientist bei Datanomiq. „Als Anwendungsfall ist Kredit-Scoring zwar alt, kann aber eine stetige Verbesserung mit Machine Learning vorweisen.“ Aunkofer zählt weitere Use Cases auf, so etwa im Versicherungswesen: „Da geht es um Schadensprognosen.“

In der Industrie tauchen Approximationsalgorithmen in der prädiktiven Wartung alias Predictive Maintenance auf. „Hier geht es um die Beobachtung der Abnutzung und die anschließende Vorhersage der idealen Wartungsintervalle.“ Eine optimale Wartung kann über Menschenleben entscheiden.

Im Handel werden sehr große Summen umgesetzt, aber nur minimale Margen erzielt. Daher lohnt sich jeder Prozentpunkt hinterm Komma, um die Marge zu vergrößern. „Approximationsalgorithmen lassen sich hier zur Vorhersage der Nachfrage und der Retouren nutzen, also von der Produkt-Ebene über die Shop-Ebene bis hin zur Kunden-Ebene. Sie geben die Retouren-Wahrscheinlichkeit für jede einzelne Kundenbestellung an. Es lassen sich also Verlustrisiken ebenso berechnen wie die Kundenbevorzugung – etwa in einem Bonusprogramm – steuern.

Erstaunliche Theorien

In der theoretischen Informatik ergeben sich Approximationsalgorithmen aus der weithin akzeptierten Vermutung, dass P ungleich NP. Aufgrund dieser Vermutung lässt sich eine große Klasse von Optimierungsprobleme nicht in polynomieller Zeit lösen. Approximationsalgorithmen versuchen daher, sich optimalen Lösungen für solche Probleme in polynomieller Zeit zu nähern.

In der großen Mehrheit aller Fälle wird die o. a. Garantie durch Multiplikationsalgorithmen ausgedrückt: als Annäherungsrate oder -faktor. Das heißt, die die optimale Lösung liegt innerhalb eines (festgelegten) Multiplikationsfaktors der gelieferten Lösung. Auch die Addition lässt sich für diesen Zweck heranziehen.

Ein erwähnenswertes Beispiel für einen Approximationsalgorithmus, der beide Methoden mit Lösungen nutzt, ist der klassische Approximationsalgorithmus von Lenstra, Shmoys und Tardos namens „Scheduling on Unrelated Parallel Machines“. Dabei werden Maschinen, Aufgaben und Kosten miteinander korreliert. Man sieht: Es gibt handfeste Anwendungsgebiete für diese scheinbar so abstrakte Methode, wie die auch die oben genannten Anwendungsfälle illustrieren.

Weitere Optimierungsprobleme

In der theoretischen Informatik gibt es mehrere Optimierungsprobleme. So wird etwa nach einem Algorithmus gesucht, der hinsichtlich des Metric-Traveling-Salesman-Problems (TSP) den „1,5-Approximationsalgorithmus“ von Christofides übertrifft. Siehe dazu den ersten Teil über das TSP-Problem. Das TSP-Problem spielt überall in der Logistik eine bedeutende Rolle. Ein weiteres Beispiel ist der Algorithmus für „Maximalen Schnitt“. Dieser Algorithmus löst ein theoretisches Graphen-Problem mithilfe von hochdimensionaler Geometrie (siehe Anblaufbild).

Das Problem des Handlungsreisenden und seine praktischen Anwendungen

Grundlagen Statistik & Algorithmen, Teil 1

Das Problem des Handlungsreisenden und seine praktischen Anwendungen

18.06.18 - Ob beim Design von künstlichen Neuronalen Netzwerken fürs Deep Learning, in der Logistik oder beim Layout von Leiterplatten – überall stößt man auf das mathematisch lösbare Problem des Handlungsreisenden: Wie lässt sich eine Tour mit mehreren Stationen auf dem kürzesten Weg und mit dem geringsten Aufwand bewältigen? lesen

Ein einfaches Beispiel für einen Approximationsalgorithmus ist die Lösung für das Minimum-Vertex-Cover-Problem, wobei Vertex ein Begriff aus der Graphentheorie sein kann, der einen Knoten bezeichnet. Dabei gibt es erstaunlicherweise einen konstant großen Faktor für den Approximationsalgorithmus, nämlich genau 2. Berücksichtigt man die Vermutung für einzigartige Spiele (Unique Games Conjecture), dann ist dieser Faktor sogar der bestmögliche. Die Graphentheorie wird auf alle Arten von vernetzten Beziehungen angewandt, so etwa in sozialen Netzwerken wie Facebook.

So verfeinert das Bayes-Theorem Spam-Filter – und mehr

Grundlagen Statistik & Algorithmen, Teil 2

So verfeinert das Bayes-Theorem Spam-Filter – und mehr

25.06.18 - Mithilfe des Satzes von Bayes lassen sich Parameter schätzen und Hypothesen induktiv testen. In einem Spamfilter können so wahrscheinliche Spam-Mails ermittelt werden. Und aus den Symptomen, die bei einem bekannten Test auftreten, lassen sich wahrscheinliche Krankheitsursachen aufspüren. Der Satz von Bayes, der bedingte Wahrscheinlichkeiten beschreibt, ist also ein nahezu universell nutzbares Werkzeug der Statistik. lesen

Güte von Approximationsalgorithmen

Um die Optimierung beurteilen und verwalten zu können, muss der Nutzer herausfinden, was sein Approximationsalgorithmus überhaupt taugt. Das herauszufinden, ist kein Hexenwerk. Man muss nur ein paar Faktoren und Variablen formulieren und in den Algorithmus einsetzen.

Es sei S ( I ) die zu einer Eingabe I gehörige Menge zulässiger Lösungen. Zu jeder möglichen Lösung y ∈ S ( I )\ in S(I) sei v ( y ) der Wert der Zielfunktion für y. Der Zielfunktionswert einer optimalen Lösung für Eingabe I sei v *. Ein Approximationsalgorithmus (oder Approximationsverfahren) gibt bei Eingabe I eine Lösung y ∈ S aus, sodass (v ( y ) relativ nah an v * liegt.

Ist die von einem Approximationsverfahren für die Eingabe berechnete Lösung, so ist die Güte des Approximationsverfahrens bei der Eingabe

  • bei Maximierungsaufgaben als r l = v * v ( y ) frac {v^{*}}{v(y)}}} und bei
  • Minimierungsaufgaben als r l = v ( y ) v * frac {v(y)}{v^{*}}}} definiert.

Es ist also immer r l ≥ 1. Gilt r l = 1, liefert der Algorithmus eine optimale Lösung für I .

Hat ein Approximationsverfahren für alle möglichen Eingaben I eine Güte von r l höchstens α, so spricht man von einer α-Approximation.

Speed für Mustererkennung mit dem Rete-Algorithmus

Grundlagen Statistik & Algorithmen, Teil 3

Speed für Mustererkennung mit dem Rete-Algorithmus

02.07.18 - Geschäftsregeln halten zahlreiche Unternehmensprozesse am Laufen, deshalb können sie mitunter sehr umfangreich werden. Der Umfang macht ihre Ausführung zeitaufwendig, weshalb jede Methode, sie zu beschleunigen, willkommen ist. Der Rete-Algorithmus beschleunigte 1979 die damals bestehenden Systeme für die Verarbeitung von Business Rules um den Faktor 3.000. Er ist bis heute die Grundlage zahlreicher Expertensysteme, etwa in der Mustererkennung. lesen

Klassen von Approximationsalgorithmen

Optimierungsprobleme werden in der Theoretischen Informatik in verschiedene Approximationsklassen unterschieden, je nachdem welcher Grad an Approximation möglich ist:

1. APX

Die Abkürzung APX steht für „approximable“ und deutet an, dass das Optimierungsproblem, zumindest bis zu einem gewissen Grad, effizient approximierbar ist. Ein Problem liegt innerhalb der Klasse APX, wenn eine Zahl r und ein polynomieller Algorithmus, der bei jeder zulässigen Eingabe I eine Lösung mit einer Güte ≤ r liefert, existieren.

2. PTAS/PAS

PTAS oder PAS steht für „polynomial time approximation scheme“. Anders als bei der Klasse APX wird hier für jedes δ ∈ ( 0 , 1) gefordert, dass ein polynomieller Algorithmus existiert, der bei jeder zulässigen Eingabe eine Lösung mit einer Güte r ≤ 1 + δ liefert. Der Algorithmus muss also nicht nur für eine bestimmte Güte, sondern für jede Approximationsgüte (s. o.) effizient sein.

3. FPTAS

FPTAS steht für „fully polynomial time approximation scheme“. Hier wird gefordert, dass sich der Algorithmus nicht nur polynomiell zur Eingabe, sondern auch zur Güte der Approximation verhält; Dass er also zu jeder Eingabe I und jedem k ∈ N eine Lösung mit der Güte r ≤ 1 + 1 / k ausgibt und seine Laufzeit polynomiell in x und k ist.

Es gilt: P O ⊆ F P T A S ⊆ P T A S ⊆ A P X ⊆ N P O .

Der Monte-Carlo-Algorithmus und -Simulationen

Grundlagen Statistik & Algorithmen, Teil 4

Der Monte-Carlo-Algorithmus und -Simulationen

10.09.18 - Eine Reihe von Algorithmen dient der Suche von Lösungen, ohne vorher die Antwort zu kennen, und von Entscheidungen, die nach „wahrscheinlich richtig oder falsch“ beurteilt werden. Das ist sinnvoll für das Risiko-Management, aber auch für die Nutzung von Supercomputern. Ein solcher Algorithmus ist der Monte-Carlo-Algorithmus und die darauf basierenden Simulationen lesen

Unter der Annahme P ≠ N P sind die obigen Inklusionsabbildungen echte Inklusionen. Das heißt, es gibt zum Beispiel mindestens ein Optimierungsproblem, das in der Klasse PTAS liegt, aber nicht in der Klasse FPTAS. Unter dieser Annahme existiert auch mindestens ein Optimierungsproblem, das nicht in APX liegt.

FPTAS-Beispiel: das Cliquenproblem

Das oben Gesagte lässt sich unter der Annahme P ⊊ N P zum Beispiel für das Cliquenproblem zeigen. Dieses Entscheidungsproblem der Graphentheorie liefert seit rund fünfzig Jahren zahlreiche interessante Lösungen.

Eine Clique bezeichnet in der Graphentheorie eine Teilmenge von Knoten in einem ungerichteten Graphen, bei der jedes Knotenpaar durch eine Kante verbunden ist. Zu entscheiden, ob ein Graph eine Clique einer bestimmten Mindestgröße enthält, wird „Cliquenproblem“ genannt und gilt, wie das Finden von größten Cliquen, als algorithmisch schwierig.

Optimale Clusteranalyse und Segmentierung mit dem k-Means-Algorithmus

Grundlagen Statistik & Algorithmen, Teil 5

Optimale Clusteranalyse und Segmentierung mit dem k-Means-Algorithmus

19.11.18 - Der k-Means-Algorithmus ist ein Rechenverfahren, das sich für die Gruppierung von Objekten, die sogenannte Clusteranalyse, einsetzen lässt. Dank der effizienten Berechnung der Clusterzentren und dem geringen Speicherbedarf eignet sich der Algorithmus sehr gut für die Analyse großer Datenmengen, wie sie im Big-Data-Umfeld üblich sind, so etwa in der Bildverarbeitung und in der Kundensegmentierung. lesen

Es ist gefragt, ob es zu einem einfachen Graphen G und einer Zahl n eine Clique der Mindestgröße n in G gibt; das heißt, ob G zumindest n Knoten hat, die alle untereinander paarweise verbunden sind. Das Optimierungsproblem fragt nach der Cliquenzahl eines Graphen: Wie viele kann er enthalten?

Das zugehörige Suchproblem fragt nach einer größten Clique. Eine größte Clique lässt sich unter bestimmten Bedingungen in polynomieller Zeit berechnen, dauert also nicht ewig. Die Berechnung einer maximalen Clique gelingt bereits mit einem einfachen Greedy-Algorithmus. Dieser wird Gegenstand eines weiteren Grundlagenartikels sein.

Die Ereigniszeitanalyse – wenn Anfang und Ende die Erfolgsrate bestimmen

Grundlagen Statistik & Algorithmen, Teil 6

Die Ereigniszeitanalyse – wenn Anfang und Ende die Erfolgsrate bestimmen

04.02.19 - Die Ereigniszeitanalyse bzw. Survival Analysis umfasst eine Reihe von Werkzeugen der Statistik, mit denen die Zeit bis zum Eintritt eines bestimmten Ereignisses zwischen Gruppen verglichen wird. Auf diese Weise will man die Wirkung von prognostischen Faktoren, einer medizinischen Behandlung oder von schädlichen Einflüssen abschätzen. Bei dem Ereignis kann es sich um etwas so Endgültiges wie den Tod handeln, aber auch um den Verlust einer Arbeitsstelle, eine Scheidung oder einen Beginn, etwa um eine Geburt oder einen Heilungseintritt. lesen

„BI-Systeme sind noch weitgehend frei von Approximationsalgorithmen“, befindet Benjamin Aunkofer. „BI-Systeme bestehen heute noch im Wesentlichen aus Data Warehousing (= saubere Datenbereitstellung) und Dashboarding (= Nutzung dieser Daten via Standard Reporting). Zukünftig werden BI-Systeme aber vermehrt Predictive Analytics aufnehmen.“

So deckt der Local Outlier Factor Anomalien auf

Grundlagen Statistik & Algorithmen, Teil 7

So deckt der Local Outlier Factor Anomalien auf

29.04.19 - Um Trends zu erkennen, wird oft die Clusteranalyse herangezogen. Der k-Means-Algorithmus etwa zeigt an, wo sich Analyseergebnisse in einer Normalverteilung ballen. Für manche Zwecke ist es aber aufschlussreicher, Ausreißer zu untersuchen, denn sie bilden die Antithese zum „Normalen“, etwa im Betrugswesen. Der Local-Outlier-Factor-Algorithmus (LOF) ist in der Lage, den Abstand von Ausreißern zu ihren Nachbarn zu berechnen und deckt so Anomalien auf. lesen

Kommentare werden geladen....

Kommentar zu diesem Artikel abgeben

Der Kommentar wird durch einen Redakteur geprüft und in Kürze freigeschaltet.

Anonym mitdiskutieren oder einloggen Anmelden

Avatar
Zur Wahrung unserer Interessen speichern wir zusätzlich zu den o.g. Informationen die IP-Adresse. Dies dient ausschließlich dem Zweck, dass Sie als Urheber des Kommentars identifiziert werden können. Rechtliche Grundlage ist die Wahrung berechtigter Interessen gem. Art 6 Abs 1 lit. f) DSGVO.
  1. Avatar
    Avatar
    Bearbeitet von am
    Bearbeitet von am
    1. Avatar
      Avatar
      Bearbeitet von am
      Bearbeitet von am

Kommentare werden geladen....

Kommentar melden

Melden Sie diesen Kommentar, wenn dieser nicht den Richtlinien entspricht.

Kommentar Freigeben

Der untenstehende Text wird an den Kommentator gesendet, falls dieser eine Email-hinterlegt hat.

Freigabe entfernen

Der untenstehende Text wird an den Kommentator gesendet, falls dieser eine Email-hinterlegt hat.

copyright

Dieser Beitrag ist urheberrechtlich geschützt. Sie wollen ihn für Ihre Zwecke verwenden? Infos finden Sie unter www.mycontentfactory.de (ID: 45946450 / Analytics)