Transduktion (maschinelles Lernen) – Wikipedia

In Logik, statistischer Inferenz und überwachtem Lernen
Transduktion oder transduktive Inferenz ist eine Argumentation von beobachteten, spezifischen (Trainings-) Fällen zu spezifischen (Test-) Fällen. Im Gegensatz dazu ist die Induktion eine Argumentation von beobachteten Trainingsfällen zu allgemeinen Regeln, die dann auf die Testfälle angewendet werden. Die Unterscheidung ist am interessantesten in Fällen, in denen die Vorhersagen des transduktiven Modells von keinem induktiven Modell erreicht werden können. Beachten Sie, dass dies durch transduktive Inferenz auf verschiedenen Testsätzen verursacht wird, die zu inkonsistenten Vorhersagen führen.

Die Transduktion wurde in den 1990er Jahren von Vladimir Vapnik eingeführt, motiviert durch seine Ansicht, dass die Transduktion der Induktion vorzuziehen ist, da die Induktion seiner Meinung nach die Lösung eines allgemeineren Problems (Ableiten einer Funktion) erfordert, bevor ein spezifischeres Problem gelöst wird (Berechnung der Ergebnisse für neue Fälle) ): “Wenn Sie ein Problem von Interesse lösen, lösen Sie kein allgemeineres Problem als Zwischenschritt. Versuchen Sie, die Antwort zu erhalten, die Sie wirklich brauchen, aber keine allgemeinere.” Eine ähnliche Beobachtung hatte Bertrand Russell zuvor gemacht: “Wir werden zu dem Schluss kommen, dass Sokrates mit einem größeren Ansatz zur Gewissheit sterblich ist, wenn wir unsere Argumentation rein induktiv machen, als wenn wir über ‘alle Menschen sind sterblich’ gehen und dann verwenden Abzug “(Russell 1912, Kap. VII).

Ein Beispiel für Lernen, das nicht induktiv ist, wäre die binäre Klassifizierung, bei der die Eingaben dazu neigen, sich in zwei Gruppen zu gruppieren. Eine große Anzahl von Testeingaben kann beim Auffinden der Cluster hilfreich sein und somit nützliche Informationen zu den Klassifizierungsbezeichnungen liefern. Die gleichen Vorhersagen wären nicht aus einem Modell erhältlich, das eine Funktion induziert, die nur auf den Trainingsfällen basiert. Einige Leute nennen dies vielleicht ein Beispiel für das eng verwandte halbüberwachte Lernen, da Vapniks Motivation ganz anders ist. Ein Beispiel für einen Algorithmus in dieser Kategorie ist die Transductive Support Vector Machine (TSVM).

Eine dritte mögliche Motivation, die zur Transduktion führt, ergibt sich aus der Notwendigkeit der Annäherung. Wenn eine genaue Inferenz rechnerisch untragbar ist, kann man zumindest versuchen, sicherzustellen, dass die Approximationen an den Testeingaben gut sind. In diesem Fall könnten die Testeingaben aus einer beliebigen Verteilung stammen (die nicht unbedingt mit der Verteilung der Trainingseingaben zusammenhängt), die beim halbüberwachten Lernen nicht zulässig wäre. Ein Beispiel für einen Algorithmus, der in diese Kategorie fällt, ist die Bayesian Committee Machine (BCM).

Beispiel Problem[edit]

Das folgende Beispielproblem stellt einige der einzigartigen Eigenschaften der Transduktion gegen die Induktion gegenüber.

Es wird eine Sammlung von Punkten angegeben, sodass einige der Punkte beschriftet sind (A, B oder C), die meisten Punkte jedoch nicht beschriftet sind (?). Ziel ist es, geeignete Beschriftungen für alle unbeschrifteten Punkte vorherzusagen.

Der induktive Ansatz zur Lösung dieses Problems besteht darin, die markierten Punkte zum Trainieren eines überwachten Lernalgorithmus zu verwenden und dann Beschriftungen für alle unbeschrifteten Punkte vorhersagen zu lassen. Bei diesem Problem verfügt der überwachte Lernalgorithmus jedoch nur über fünf markierte Punkte, die als Grundlage für die Erstellung eines Vorhersagemodells verwendet werden können. Es wird sicherlich schwierig sein, ein Modell zu erstellen, das die Struktur dieser Daten erfasst. Wenn beispielsweise ein Algorithmus für den nächsten Nachbarn verwendet wird, werden die Punkte in der Nähe der Mitte mit “A” oder “C” bezeichnet, obwohl offensichtlich ist, dass sie zu demselben Cluster gehören wie der mit “B” bezeichnete Punkt.

Die Transduktion hat den Vorteil, dass bei der Ausführung der Beschriftungsaufgabe alle Punkte berücksichtigt werden können, nicht nur die markierten Punkte. In diesem Fall würden transduktive Algorithmen die unbeschrifteten Punkte gemäß den Clustern kennzeichnen, zu denen sie natürlich gehören. Die Punkte in der Mitte würden daher höchstwahrscheinlich als “B” bezeichnet, da sie sehr nahe an diesem Cluster gepackt sind.

Ein Vorteil der Transduktion besteht darin, dass sie möglicherweise mit weniger markierten Punkten bessere Vorhersagen treffen kann, da die natürlichen Brüche in den nicht markierten Punkten verwendet werden. Ein Nachteil der Transduktion besteht darin, dass sie kein Vorhersagemodell erstellt. Wenn der Menge ein zuvor unbekannter Punkt hinzugefügt wird, müsste der gesamte transduktive Algorithmus mit allen Punkten wiederholt werden, um eine Markierung vorherzusagen. Dies kann rechenintensiv sein, wenn die Daten in einem Stream schrittweise verfügbar gemacht werden. Außerdem kann dies dazu führen, dass sich die Vorhersagen einiger der alten Punkte ändern (die je nach Anwendung gut oder schlecht sein können). Ein überwachter Lernalgorithmus hingegen kann neue Punkte mit sehr geringem Rechenaufwand sofort kennzeichnen.

Transduktionsalgorithmen[edit]

Transduktionsalgorithmen können grob in zwei Kategorien unterteilt werden: diejenigen, die unbeschrifteten Punkten diskrete Beschriftungen zuweisen möchten, und diejenigen, die fortlaufende Beschriftungen für unbeschriftete Punkte zurückführen möchten. Algorithmen, die diskrete Bezeichnungen vorhersagen möchten, werden in der Regel durch Hinzufügen einer teilweisen Überwachung zu einem Clustering-Algorithmus abgeleitet. Diese können weiter in zwei Kategorien unterteilt werden: diejenigen, die sich durch Partitionierung gruppieren, und diejenigen, die sich durch Agglomerieren gruppieren. Algorithmen, die kontinuierliche Markierungen vorhersagen möchten, werden in der Regel durch Hinzufügen einer Teilüberwachung zu einem vielfältigen Lernalgorithmus abgeleitet.

Partitionierung der Transduktion[edit]

Die Partitionierung der Transduktion kann als Top-Down-Transduktion betrachtet werden. Es ist eine halbüberwachte Erweiterung des partitionbasierten Clusters. Es wird typischerweise wie folgt durchgeführt:

Consider the set of all points to be one large partition.
While any partition P contains two points with conflicting labels:
  Partition P into smaller partitions.
For each partition P:
  Assign the same label to all of the points in P.

Natürlich könnte mit diesem Algorithmus jede vernünftige Partitionierungstechnik verwendet werden. Zu diesem Zweck sind Partitionsschemata mit maximalem Durchfluss und minimalem Schnitt sehr beliebt.

Agglomerative Transduktion[edit]

Agglomerative Transduktion kann als Bottom-Up-Transduktion betrachtet werden. Es ist eine halbüberwachte Erweiterung der agglomerativen Clusterbildung. Es wird typischerweise wie folgt durchgeführt:

Compute the pair-wise distances, D, between all the points.
Sort D in ascending order.
Consider each point to be a cluster of size 1.
For each pair of points {a,b} in D:
  If (a is unlabeled) or (b is unlabeled) or (a and b have the same label)
    Merge the two clusters that contain a and b.
    Label all points in the merged cluster with the same label.

Verteilertransduktion[edit]

Die auf vielfältigem Lernen basierende Transduktion ist noch ein sehr junges Forschungsgebiet.

Siehe auch[edit]

Verweise[edit]

• VN Vapnik. Statistische Lerntheorie. New York: Wiley, 1998. (Siehe Seiten 339-371)
• V. Tresp. Eine Bayesianische Komiteemaschine, Neural Computation, 12, 2000, pdf.
• B. Russell. Die Probleme der Philosophie, Home University Library, 1912. [1].

Externe Links[edit]

• Ein Gammerman, V. Vovk, V. Vapnik (1998). “”Lernen durch Transduktion“Eine frühe Erklärung des transduktiven Lernens.
• “”Eine Diskussion über halbüberwachtes Lernen und Transduktion, “Kapitel 25 von Halbüberwachtes Lernen, Olivier Chapelle, Bernhard Schölkopf und Alexander Zien, Hrsg. (2006). MIT Press. Eine Diskussion über den Unterschied zwischen SSL und Transduktion.
• Waffeln ist eine Open-Source-C ++ – Bibliothek von Algorithmen für maschinelles Lernen, einschließlich Transduktionsalgorithmen, auch Waffeln.
• SVMlight ist ein Allzweck-SVM-Paket, das die transduktive SVM-Option enthält.