Was ist Inductive Logic Programming?

Johannes Rabold

Gesina Schwalbe

Heute tauchen wir ein in ein Spezialfeld des Maschinellen Lernens, und zwar: Inductive Logic Programming (ILP). ILP umfasst Methoden und Algorithmen zum automatisierten Lernen von logischen Regeln und Zusammenhängen.

Zusammenfassung: Ganz kurz für Beepo

• ILP benötigt relativ wenig Trainingsbeispiele. Diese müssen aber in Form von expliziten Prädikaten vorliegen.
• Gelernte Regeln sind (im Gegensatz zu Neuronalen Netzen) meist einfacher für Menschen interpretierbar

Ein kleiner Exkurs in die formale Logik

• Teilgebiet der Mathematik für das Modellieren der Welt mit wahren oder falschen Statements (hier: Prädikatenlogik)
  • Martin ist männlich; Anna und Nina sind weiblich (Attribute)
  • Martin und Anna sind Elternteile von Nina (Relationen)
  • Martin ist der Vater von Nina; Anna ist nicht der Vater von Nina (Negation)
  • X ist Vater von Y, wenn X ein Elternteil von Y ist und X männlich ist. (Abstrakte logische Regel mit Variablen)
• ILP möchte solche Regeln automatisch erlernen
• Als Basis dazu benötigen wir:
  • Positive und negative Beispiele für das Konzept (hier „Vater“)
  • Ein Pool von wahren Statements in unserer Welt (hier wahre Elternteil- und Geschlechts-Statements)

Typische Ansätze

• Was ist eine gute Regel?
  • Kümmert sich um möglichst viele positive Beispiele
  • Meidet möglichst viele negative Beispiele
  • Ist so allgemein wie möglich
• Generate-and-Test Verfahren
  • FOIL (Quinlan)
    • Generiere Regelkandidaten und entferne in jedem Schritt die gecoverten positiven Beispiele
    • Erst wird versucht, eine Regel dadurch aufzubauen, dass mehr und mehr Vorbedingungen für die Regel gefunden werden (Hier wird ein statistisches Maß zur Beurteilung der Güte von Literalen verwendet).
    • Wenn diese Regel nicht ausreicht, um alle Beispiele korrekt zu klassifizieren, werden mit dem selben Verfahren weitere Regeln gefunden.
  • ALEPH (Srinivasan)
    • Wähle ein positives Beispiel aus
    • Baue die spezifischste Klausel
    • Suche nach einer generelleren Klausel
    • Entferne redundante Beispiele
  • Negative Beispiele mit Bedacht wählen. Starke Abgrenzung zu positiven Beispielen an den wichtigen Stellen ist essenziell für ein effizientes Lernen.

Anwendungsgebiete

• Relationale Problemstellungen
  • Mutagenizität (Eine der ersten Anwendungen)
  • Stabilität (z.B. AI Birds)
  • Funktioniert auch bei wenig Beispielen gut!
• Erklärbare KI
  • Post-Hoc-Erklärverfahren: Nehme ein effektives aber undurchsichtiges neuronales Netz und erkläre es durch ILP
    • Finde zunächst wichtige Bausteine im Input oder im gelernten Netz und finde dann aussagekräftige ILP-Regeln, die das Zusammenspiel dieser erklären.
  • Safety im autonomen Fahren: Werden vorgegebene logische Regeln von einem trainierten neuronalen Netz eingehalten?
• Die Wichtigkeit guter negativer Beispiele!
  • Man könnte verleitet werden, nur positive Beispiele (z.B. für Katze) zu geben.
  • Kleinkinder haben aber dann Probleme, wenn z.B. ein Hund kommt.
  • In der Psychologie sieht man, dass einige wenige, gut gewählte negative Beispiele ein Konzept besser beschreiben (Das ist keine Katze, das ist ein Hund)
  • Eltern erklären intuitiv mit Sprache, warum das keine Katze, sondern ein Hund ist (größer, bellt, weniger Schnurrhaare etc.)
  • Dualität zwischen Lernen und Erklären
• Heimassistenten
  • Vorhandenes Wissen über den Haushalt mit Logik modellieren
  • Regeln mit ILP lernen, welche aussagen, ob bestimmte Situationen vorliegen
  • Wenn Situation vorliegt, passende Aktionen schalten

Weitere Links und Quellen

• Muggleton and de Raedt (1994): Inductive Logic Programming: Theory and Methods
• Muggleton, Schmid, Zeller (2018): Ultra-strong Machine Learning: Comprehensibility of Programs Learned with ILP
• Wikipedia-Artikel zu FOIL: hier
• Haupt-Webseite zu ALEPH: hier
• Wikipedia-Artikel zur Prädikatenlogik erster Stufe: hier
• Srinivasan, Muggleton, King, Sternberg (1994): Mutagenesis: ILP Experiments in a Non-determinate Biological Domain
• Rabold, Deininger, Siebers, Schmid (2019): Enriching Visual with Verbal Explanations for Relational Concepts – Combining LIME with Aleph
• Rabold, Schwalbe, Schmid (2020): Expressive Explanations of DNNs by Combining Concept Analysis with ILP
• Rabold, Siebers, Schmid (2021): Generating Contrastive Explanations for Inductive Logic Programming Based on a Near Miss Approach
• Schwalbe, Wirth, Schmid (2021): Concept Embeddings for Fuzzy Logic Verification of Deep Neural Networks in Perception Tasks, https://arxiv.org/abs/2201.00572
  (Paper von Gesina zu Sicherheitsüberprüfungen an DNNs mithilfe logischer Regeln)