Prädikatenlogik erster Stufe

Was ist Prädikatenlogik erster Stufe?

Die Prädikatenlogik erster Stufe oder auch First-Order Logic (FOL) ist eine, an die Mathematik angelehnte Methode, um einem Objekt eindeutige Eigenschaften zuordnen zu können. Dabei wird jeder Satz/Aussage in sein Subjekt und sein Prädikat zerlegt. Die Beziehung zwischen ihnen erfolgt in der Prädikatenlogik erster Stufe durch P(x), wobei P für Prädikat und die Variable x für das entsprechende Subjekt steht.

Zu beachten ist, dass die Prädikate in der First-Order Logic sich nur auf jeweils ein Subjekt beziehen. Anders als in der Sprachwissenschaft ist ein Prädikat nicht zwingend ein Verb, sondern liefert lediglich relevante Informationen über das betreffende Subjekt. Die Verwendung der Prädikate erlaubt es zudem Relationen herzustellen; beispielsweise durch Vergleiche (größer/kleiner als, gleich usw.).

In der Prädikatenlogik erster Stufe werden Quantoren eingesetzt und durch die Symbole ∀ (universeller Quantor; gelesen: „für alle“) und ∃ (Existenzquantor; gelesen: „es existiert“ oder „für einige“) dargestellt. Die Darstellung erfolgt in der First-Order Logic durch mathematische Symbole und besteht aus:

  • Termen: Mensch, Tier, Pflanze etc.
  • Namen von Objekten. Diese können im sprachlichen Sinn sowohl Objekte als auch Subjekte sein!
  • Variablen a, b, c, …, x, y, z etc.

Diese stehen für noch nicht bekannte Objekte.

Prädikate [rot, duftet, ist eine Blume etc.] stehen für Eigenschaften und Relationen, die sprachlich mit Verben oder Attributen vergleichbar sind.

Quantoren [∀, ∃] erlauben Aussagen über Mengen von Objekten, für die das Prädikat gilt.

Beziehungen [∧ (und), ∨ (oder), →(impliziert), ⇒ (daraus folgt), ⇔ (ist äquivalent zu), == (Gleichheits – Operator)] geben Rückschlüsse über Relationen.

Beispiel für eine Prädikatenlogik erster Stufe

Die Rose ist rot.

P(x) = rot(Rose)

Die Rose duftet.

P(x) = duftet(Rose)

Die Rose ist eine Blume.

P(x) = Blume(Rose)

Wir erfahren über die Rose, dass sie rot ist, duftet und eine Blume ist.

Daraus resultiert für ∀:

Alle Rosen sind rot.

Alle Rosen duften.

Alle Rosen sind Blumen.

Es sind jedoch nicht alle Rosen rot und nicht jede Rose duftet.

Dass alle Rosen Blumen sind, ist hingegen eine wahre Aussage.

∀(x) Rose(x) → Blume(x)

Damit die beiden anderen Aussagen auf ihre Richtigkeit hin überprüft werden können, kommen nun Existenzquantoren zum Einsatz.

Aus den beiden Aussagen:

„Alle Rosen sind rot.“ und „Alle Rosen duften.“ werden durch Verwendung von ∃:

„Einige Rosen sind rot.“ und „Einige Rosen duften.“

Um sie in eine Formel erster Ordnung zu übersetzen, müssen wir eine Variable x definieren:

Ein Prädikat A(x), wobei x der Rose entspricht, und einem Prädikat G(x), welches für x ist, rot bzw. duftet.

∃(x) Rose(x) → rot(x)

bzw.

∃(x) Rose(x) → duftet(x)

Dadurch erfährt man, dass es Rosen gibt, die rot sind und Rosen existieren, die duften. Logisch ergibt sich daraus, dass es demnach auch Rosen geben muss, die nicht rot sind bzw. die nicht duften.

Pathfinding

Was ist Pathfinding?

Unter Pathfinding versteht man in der Informatik Algorithmen, mit welchen der optimale Weg zwischen zwei oder mehreren Punkten gefunden werden soll. Dabei kann der optimale Weg anhand von unterschiedlichen Parametern definiert werden.

Der optimale Weg ist immer vom jeweiligen Anwendungsfall abhängig. Neben dem kürzesten Weg kann beispielsweise auch der kostengünstigste Weg als Optimum definiert werden. Beispielsweise können auch andere Nebenbedingungen wie das Vermeiden von gewissen Wegpunkten oder Streckenabschnitten die Bestimmung des optimalen Weges beeinflussen.

Dieses Verhalten ist im Allgemeinen bei Routenplanern bekannt, wenn Autobahnen oder Mautstraßen vermieden werden sollen.

Algorithmen

Je nach Anforderung der Zielsetzung lassen sich im Rahmen des Pathfinding verschiedene Algorithmen anwenden.

Beim A*-Algorithmus handelt es sich um einen sogenannten informierten Suchalgorithmus, welcher den kürzesten Graphen zwischen zwei Punkten mithilfe einer Schätzfunktion/Heuristik ermittelt. Bei der Suche wird (vom Startpunkt aus gesehen) jener Folgeknoten untersucht, welcher wahrscheinlich schnell zum Ziel führt bzw. die Entfernung zum Zielknoten verringert. Ist eine Untersuchung eines Knotens nicht zielführend, wird dieser als solcher markiert und die Suche wird mit einem anderen Knoten fortgesetzt. Gemäß diesem Algorithmus wird der kürzeste Weg zum Zielknoten untersucht.

Ein weiterer Algorithmus zur Ermittlung des kürzesten Pfades ist der Algorithmus von Dijkstra. Dieser basiert nicht auf Heuristik, sondern auf Basis der Vorgehensweise, dass vom Startknoten ausgehend alle Knoten mit den kürzesten Teilstrecken zueinander zur Optimallösung führen, indem die Summe der kürzesten Teilstrecken zum insgesamt kürzesten Gesamtpfad führt. Somit funktioniert die Vorgehensweise in Form der aussichtsreichsten Teillösung.

Im Gegensatz zu den bisher beschriebenen Vorgehensweisen erlaubt der Bellman-Ford-Algorithmus (bzw. Moore-Bellman-Ford-Algorithmus) auch die Betrachtung von Graphen mit negativen Kantengewichten zur Ermittlung der kürzesten Pfade. Dies bedeutet, dass die Kosten (z. B. Zeit) zwischen zwei Knoten auch negativ sein können. Es muss jedoch sichergestellt sein, dass Zyklen durch negative Gewichte ausgeschlossen werden, da sich ansonsten der Pfad durch wiederholtes Durchlaufen der negativen Kantengewichte verringert. Alle bisher betrachteten Vorgehensweisen optimieren den Pfad von einem bestimmten Knoten aus gesehen.

Der Min-Plus-Matrixmultiplikations-Algorithmus sucht hingegen das Optimum sämtlicher Knotenpaare zueinander.

Gleiches gilt für den Floyd-Warshall-Algorithmus. Das Verfahren macht sich dabei die Vorgehensweise der dynamischen Programmierung zunutze. Zur Findung des Optimums wird das Gesamtproblem in gleichartige Teilprobleme geteilt und anschließend durch die Lösung und Speicherung dieser zu einer Optimierung des Gesamtproblems übergeführt. Die Funktionsweise ist zweigeteilt, wobei der Teil von Floyd dafür sorgt, dass die kürzesten Distanzen zwischen den Knoten berechnet werden, während der Teil von Warshall für die Konstruktion der kürzesten Pfade zuständig ist. Auch die Betrachtung von negativen Kantengewichten ist bei diesem Algorithmus möglich.

Während manche Verfahren die Optimierung zwischen zwei Knotenpunkten als Zielsetzung haben, optimieren andere sämtliche Knotenpunkte zueinander. Dies führt natürlich zu einer Erhöhung der Rechenleistung. Deshalb ist neben der Betrachtung der Zielsetzung bei der Wahl des Algorithmus mitunter auch die Beanspruchung der Ressourcen ein ausschlaggebender Faktor. Neben der Rechenleistung können auch der benötigte Speicherplatz und die Laufzeit relevante Größen bei der Wahl des Verfahrens darstellen.

Für manche der beschriebenen Verfahren bestehen vorgefertigte Algorithmen, welche in eigene Lösungen implementiert werden können. So kann unter anderem die Bibliothek NetworkX in Python implementiert und als Framework für die Pathfinding-Probleme genutzt werden.

Beispiele für die Anwendung von Pathfinding in der Praxis

Die Anwendungsmöglichkeiten von Pathfinding sind vielfältig. Sie reichen von einfachen sowie komplexen Steuerungen und Routenplanungen im Computerspiel-Sektor bis hin zur Lösung von Transportlogistikproblemen und der Optimierung von Routing-Problemen im Netzwerk-Sektor. Zur Unterstützung der Optimierungslösungen können auch Teilbereiche der Künstlichen Intelligenz implementiert werden.

Wie eingangs erwähnt, kann das zu erreichende Optimum individuell definiert sein. Die Begrenzung der Kostengröße kann durch Minimierung des Faktors Zeit, Geld, Zwischenstopps und vielen anderen Parametern dargestellt werden.

PyTorch

PyTorch ist ein Open-Source-Framework für Machine Learning (maschinelles Lernen) und basiert auf der Programmiersprache Python und der Bibliothek Torch. Entwickelt wurde es 2016 von einem Forscherteam für künstliche Intelligenz von Facebook, um die Effizienz der Entwicklung und Bereitstellung von Forschungsprototypen zu verbessern. PyTorch rechnet mit Tensoren, welche durch Grafikprozessoren (kurz GPU) beschleunigt werden. Es können über 200 verschiedene mathematische Operationen mit dem Framework genutzt werden.

Heute ist PyTorch eine der beliebtesten Plattformen für Forschungen im Bereich von Deep Learning und wird hauptsächlich für künstliche Intelligenz (KI), Datenwissenschaft und Forschung genutzt. PyTorch wird immer beliebter, weil sich damit vergleichsweise einfach Modelle für künstliche neuronale Netze (KNN) erstellen lassen. Und auch für Reinforcement Learning (bestärkendes Lernen) lässt sich PyTorch nutzen. Es kann bei GitHub kostenlos als Open Source heruntergeladen werden.

Was ist PyTorch Lightning?

PyTorch Lightning ist eine Open-Source-Bibliothek für Python und bietet eine High-Level-Schnittstelle für PyTorch. Der Schwerpunkt liegt auf Flexibilität und Leistung, um Forschern, Datenwissenschaftlern und Machine-Learning-Ingenieuren die Möglichkeit zu geben, passende und vor allem skalierbare ML-Systeme zu erstellen. PyTorch Lightning steht ebenfalls als Open Source zum Download bei GitHub bereit.

Was sind die Funktionen und Vorteile von PyTorch?

Dynamische Graphenberechnung

Das Netzwerkverhalten kann spontan geändert werden und es muss dafür nicht der komplette Code ausgeführt werden.

Automatische Differenzierung

Mittels Rückwärtsdurchläufe in neuronalen Netzen wird die Ableitung einer Funktion numerisch berechnet.

Benutzerfreundliche Oberfläche

Sie wird TorchScript genannt und macht das nahtlose Wechseln zwischen den Modi möglich. Es bietet Funktionalität, Geschwindigkeit, Flexibilität und Benutzerfreundlichkeit.

Python-Unterstützung

Da PyTorch auf Python basiert, ist es leicht zu erlernen und zu programmieren und es können alle mit Python kompatiblen Bibliotheken wie zum Beispiel NumPy oder SciPy genutzt werden. Außerdem ist ein unkompliziertes Debugging mit Python-Tools möglich.

Skalierbarkeit

Es findet auf wichtigen Cloud-Plattformen eine gute Unterstützung und ist somit gut zu skalieren.

Dataset und DataLoader

Es besteht die Möglichkeit, ein eigenes Dataset für PyTorch zu erstellen, um alle nötigen Daten zu speichern. Das Dataset wird mittels DataLoader verwaltet. Der DataLoader kann unter anderem die Daten durchlaufen, Batches verwalten und Daten transformieren.

Zusätzlich kann PyTorch Lernmodelle im Open Neural Network Exchange (ONNX) Standardformat exportieren und besitzt eine C++ Front-End-Schnittstellenoption.

Was sind Beispiele für die Anwendung von PyTorch?

  • Objekterkennung (object detection)
  • Segmentierung (semantic segmentation)
  • LSTM (Long Short-Term Memory, zu Deutsch: langes Kurzzeitgedächtnis)
  • Transformer

PyTorch vs. Tensorflow

Tensorflow ist ebenfalls ein Deep-Learning-Framework und wurde von Google entwickelt. Es existiert bereits länger als PyTorch und hat deswegen eine größere Entwickler-Community und mehr Dokumentation. Beide Frameworks haben ihre Vor- und Nachteile, da sie für unterschiedliche Projekte gedacht sind.

Während Tensorflow die Rechendiagramme auf statische Weise definiert, verfolgt PyTorch einen dynamischen Ansatz. Auch können die dynamischen Graphen bei PyTorch in Echtzeit manipuliert werden und bei Tensorflow nur am Ende. Daher eignet sich PyTorch durch seine einfache und leichte Handhabung besonders für eine unkomplizierte Erstellung von Prototypen und für Forschungsarbeiten. Tensorflow hingegen ist vor allem für Projekte geeignet, die skalierbare Produktionsmodelle benötigen.

PyTorch vs. scikit-learn

Scikit-learn (auch Sklearn genannt) ist eine freie Bibliothek für Python und ist auf Machine Learning (maschinelles Lernen) spezialisiert. Es bietet eine Reihe an Klassifikations-, Regressions- und Clustering-Algorithmen, wie zum Beispiel Random Forest, Support-Vektor-Maschinen oder k-means an. Scikit-learn bietet eine effiziente und unkomplizierte Datenanalyse und eignet sich besonders zum Definieren von Algorithmen, ist aber für ein End-to-End-Training tiefer neuronaler Netze eher ungeeignet, wofür hingegen PyTorch sehr gut genutzt werden kann.

Pythia (Software)

Das Computerprogramm Pythia wird in der Teilchenphysik eingesetzt. Hier dient es dazu, an Teilchenbeschleunigern wie z. B. CERN Kollisionen zu simulieren bzw. zu generieren. Damit ist die Software gleichzeitig der am häufigsten eingesetzte Monte-Carlo-Ereignisgenerator. Die Berechnungen erfolgen auf Basis der Algorithmen der Wahrscheinlichkeitstheorie.

Es wird über die Pythia Software Zufallsproben einer Verteilung mit Zufallsexperimenten gezogen. Dies ist insbesondere dann hilfreich, um herauszufinden, durch welche Signale sich bei vom Standard abweichenden Physikmodellen am Teilchenbeschleuniger bemerkbar machen. Es ist sinnvoll, die Modelle über die Pythia Software vorab numerisch zu simulieren.

Für welche Simulationen wird die Pythia Software genutzt?

Klassisches Einsatzgebiet der Pythia Software ist die Teilchenphysik mit ihren unterschiedlichsten Anwendungsbereichen. Wenn beispielsweise ein Physikmodell ein neues Teilchen vorhersagt, können Annahmen vorgeschaltet werden. Sie helfen vor der Experimentierphase Hinweise auf die Signale zu erhalten, die im Experiment gesucht werden. Gegebenenfalls können die Detektoren der Simulation darauf optimiert werden.

Grundüberlegungen, die im Vorfeld angestellt werden können:

  • Welche Teilchen können produziert werden und wie sollen diese im Modell zerfallen?
  • Wie komplex und begrenzt ist die Messbarkeit von Zerfallsprodukten?

Die Simulation mit der Pythia Software erstellt ein klares Signal. Dieses beschreibt die Anzahl und Impulse der ankommenden Teilchen aus der Kollision. Mit dem Ziel, dass die Detektoren die entstandenen Teilchen im Rahmen des Beschleunigungsexperimentes nachweisen.

Experimente in Teilchenbeschleunigern gehören zu den wichtigsten Quellen zur Entdeckung von neuen physikalischen Phänomenen. Schwierig wird es, da die Experimente über Jahrzehnte immer größer gewordenen sind. Hier helfen Programme wie die Pythia Software bei der Suche nach neuen Teilchen. Die Pythia Software hat ein umfangreiches Portfolio an Einstellungen und Funktionalitäten. Pythia ermöglicht die Simulation unterschiedlicher Szenarien bei der Erforschung physikalischer Ereignisse.

In der daraus resultierenden Anwendung werden in Teilchenbeschleunigern, die Protonen auf eine enorme Geschwindigkeit beschleunigt. Sie prallen in einem der Detektoren aufeinander. Dabei wird die im Teilchen enthaltene Energie auf minimalem Raum in extrem kurzer Zeit in neue Partikel umgewandelt. Wenn sie auf die Detektoren treffen, beginnt die Datenanalyse. So werden ab hier Spuren ausgewertet und Fährten zu lesen versucht, um die Ereignisse der Kollision zu rekonstruieren.

Die dabei anfallenden Datenmengen sind exorbitant. Schon seit Jahren ist die Physik dabei, sie mithilfe von künstlicher Intelligenz zu klassifizieren, sortieren und zu ordnen.

Predictive Maintenance

Predictive Maintenance (PdM) ist eine Weiterentwicklung des zustandsbasierten Ansatzes, da es um mehr als nur die Analyse des Ist-Zustandes geht. Das Ziel ist nicht mehr nur die frühzeitige Erkennung von degenerativen Prozessen, sondern vielmehr die zusätzliche tiefere Diagnose, um das erwartete anomale Prozessverhalten vorherzusagen.

Predictive Maintenance hilft somit bei der Abschätzung, wann eine Wartung der Maschine durchgeführt werden soll. Im Vergleich zu routinemäßigen oder zeitbasierten Wartungsstrategien können mit PdM Kosten eingespart werden.