Eine leistungsstarke, aber unauffällige Methode zur Datenzusammenfassung – erklärbare KI
Obwohl die MMD-Critic-Methode ein leistungsfähiges Werkzeug zur Datenzusammenfassung ist, ist ihre Anwendung und Abdeckung überraschend gering. Vielleicht liegt dies daran, dass es einfachere und etabliertere Methoden zur Datenzusammenfassung gibt (z. B. Ok-Medoide, siehe (1) oder einfacher die Wikipedia-Seite), oder vielleicht liegt es daran, dass (bisher) kein Python-Paket für die Methode existierte. Unabhängig davon sind die in der Originalpapier (2) rechtfertigen mehr Verwendung als MMD-Critic derzeit. Daher werde ich die MMD-Critic-Methode hier so klar wie möglich erklären. Ich habe auch eine Open-Supply-Python-Paket mit einer Implementierung der Technik, damit Sie sie einfach verwenden können.
Bevor wir uns mit der MMD-Critic-Methode selbst befassen, sollten wir uns zunächst einmal damit befassen, was wir damit erreichen wollen. Letztendlich möchten wir einen Datensatz nehmen und Beispiele finden, die repräsentativ für die Daten sind (Prototypen) sowie Grenzfallbeispiele, die unsere maschinellen Lernmodelle durcheinander bringen könnten (Kritik).
Es gibt viele Gründe, warum dies nützlich sein kann:
- Wir können eine sehr schöne zusammengefasste Ansicht unseres Datensatzes erhalten, indem wir sowohl stereotype als auch atypische Beispiele betrachten
- Wir können Modelle anhand der Kritikpunkte testen, um zu sehen, wie sie mit Randfällen umgehen (das ist aus offensichtlichen Gründen sehr wichtig).
- Obwohl es vielleicht nicht so nützlich ist, können wir Prototypen verwenden, um einen natürlich erklärbaren Ok-Means-ähnlichen Algorithmus zu erstellen, bei dem der dem neuen Datenpunkt am nächsten kommende Prototyp verwendet wird, um ihn zu kennzeichnen. Dann sind die Erklärungen einfach, da wir dem Benutzer nur den ähnlichsten Datenpunkt zeigen.
- Mehr
Siehe Abschnitt 6.3 in dieses Buch Weitere Informationen zu den Anwendungen finden Sie hier (und auch eine ausführliche Erklärung von MMD-Critic). Es genügt jedoch zu sagen, dass das Auffinden dieser Beispiele aus einer Vielzahl von Gründen nützlich ist. MMD-Critic ermöglicht uns dies.
Leider kann ich nicht behaupten, ein hyper-rigoroses Verständnis der maximalen mittleren Diskrepanz (MMD) zu haben, da ein solches Verständnis einen starken Hintergrund in der Funktionsanalyse erfordern würde. Wenn Sie über einen solchen Hintergrund verfügen, finden Sie das Papier, in dem das Maß eingeführt wurde Hier.
Vereinfacht ausgedrückt ist MMD jedoch eine Methode, um den Unterschied zwischen zwei Wahrscheinlichkeitsverteilungen zu bestimmen. Formal gilt für zwei Wahrscheinlichkeitsverteilungen P Und Qdefinieren wir den MMD der beiden als
Hier, F ist irgendein Veranstaltungsfläche — das heißt, jede Menge von Funktionen mit derselben Domäne und demselben Wertebereich. Beachten Sie auch, dass die Notation x~P bedeutet, dass wir behandeln X als ob es eine Zufallsvariable aus der Verteilung wäre P — das heißt, X Ist beschrieben durch P. Diese Formel findet additionally den größten Unterschied in den Erwartungswerten von X Und Y wenn sie durch eine Funktion aus unserem Raum transformiert werden F.
Das ist vielleicht ein wenig schwer zu verstehen, aber hier ist ein Beispiel. Angenommen, X Ist Uniform(0, 1) (d. h. eine Verteilung, die der Auswahl einer Zufallszahl zwischen 0 und 1 entspricht) und Y Ist Uniform(-1, 1) . Lassen wir auch F eine ziemlich einfache Familie mit drei Funktionen sein — f(x) = 0, f(x) = xUnd f(x) = x². Wenn wir über jede Funktion in unserem Raum iterieren, erhalten wir:
- Im f(x) = 0 Fall, E(f(x)), wenn x ~ P ist 0, da egal was X wir wählen, f(x) wird 0 sein. Dasselbe gilt, wenn x ~ Q. Somit erhalten wir eine mittlere Diskrepanz von 0
- Im f(x) = x In diesem Fall haben wir E(f(x)) = 0,5 für die P Fall und 0 für den Q Fall, additionally beträgt unsere mittlere Diskrepanz 0,5
- Im f(x) = x² Fall stellen wir fest, dass
additionally erhalten wir im P-Fall
und im Q-Fall erhalten wir
daher ist unsere Diskrepanz in diesem Fall auch 0. Das Supremum über unserem Funktionenraum ist additionally 0,5, das ist additionally unser MMD.
Sie werden jetzt vielleicht ein paar Probleme mit unserem MMD bemerken. Es scheint stark von unserer Wahl des Funktionsraums abhängig zu sein und scheint auch sehr teuer (oder sogar unmöglich) zu berechnen für einen großen oder unendlichen Funktionsraum. Nicht nur das, es erfordert auch, dass wir unsere Verteilungen kennen P Und Qwas nicht realistisch ist.
Das letztere Downside lässt sich leicht lösen, da wir unsere MMD-Metrik so umschreiben können, dass sie Schätzungen von P und Q basierend auf unserem Datensatz verwendet:
Hier, unsere Xsind unsere Beispiele aus dem Datensatz aus Pund die jsind die Proben aus Q.
Die ersten beiden Probleme sind mit ein wenig zusätzlicher Mathematik lösbar. Ohne zu sehr ins Element zu gehen, stellt sich heraus, dass wenn F ist etwas, das man Reproduktion des Kernel-Hilbert-Raums (RKHS) wissen wir im Voraus, welche Funktion uns unseren MMD liefern wird. Es ist nämlich die folgende Funktion, genannt Zeugenfunktion:
Wo okay ist das Kernel (inneres Produkt) im Zusammenhang mit dem RKHS¹. Intuitiv „bezeugt“ diese Funktion die Diskrepanz zwischen P Und Q an dem Punkt X.
Wir müssen additionally nur einen ausreichend ausdrucksstarken RKHS/Kernel wählen — normalerweise wird der RBF-Kernel verwendet, der die Kernelfunktion hat
Dies führt im Allgemeinen zu recht intuitiven Ergebnissen. Hier ist beispielsweise die Darstellung der Zeugenfunktion mit dem RBF-Kernel, wenn sie (auf die gleiche Weise wie zuvor erwähnt, d. h. durch Ersetzen der Erwartungen durch eine Summe) auf zwei Datensätzen geschätzt wird, die aus Uniform(-0.5, 0.5) Und Uniform(-1, 1) :
Der Code zum Generieren der obigen Grafik lautet hier:
import numpy as np
import matplotlib.pyplot as plt
import seaborn as snsdef rbf(v1, v2, sigma=0.5):
return np.exp(-(v2 - v1) ** 2/(2 * sigma**0.5))
def comp_wit_fn(x, d1, d2):
return 1/len(d1) * sum((rbf(x, dp) for dp in d1)) - 1/len(d2) * sum((rbf(x, dp) for dp in d2))
low1, high1 = -0.5, 0.5 # Vary for the primary uniform distribution
low2, high2 = -1, 1 # Vary for the second uniform distribution
# Generate information for the uniform distributions
data1 = np.random.uniform(low1, high1, 10000)
data2 = np.random.uniform(low2, high2, 10000)
# Generate a variety of x values for which to compute comp_wit_fn
x_values = np.linspace(min(low1 * 2, low2 * 2), max(high1 * 2, high2 * 2), 100)
comp_wit_values = (comp_wit_fn(x, data1, data2) for x in x_values)
sns.kdeplot(data1, label=f'Uniform({low1}, {high1})', shade='blue', fill=True)
sns.kdeplot(data2, label=f'Uniform({low2}, {high2})', shade='crimson', fill=True)
plt.plot(x_values, comp_wit_values, label='Witness Operate', shade='inexperienced')
plt.xlabel('Worth')
plt.ylabel('Density / Wit Fn')
plt.legend()
plt.present()
Die Idee hinter MMD-Critic ist nun ziemlich einfach: Wenn wir finden wollen okay Prototypen müssen wir den Satz von Prototypen finden, der am besten der Verteilung des ursprünglichen Datensatzes entspricht, die durch ihre quadrierten MMD gegeben ist. Mit anderen Worten, wir möchten eine Teilmenge finden P der Kardinalität okay unseres Datensatzes, der minimiert MMD²(F, X, P). Ohne zu sehr ins Element zu gehen, warum, ist das Quadrat MMD gegeben durch
Nachdem wir diese Prototypen gefunden haben, wählen wir als Kritikpunkte die Punkte aus, an denen die hypothetische Verteilung unserer Prototypen am stärksten von unserer Datensatzverteilung abweicht. Wie wir bereits gesehen haben, kann der Unterschied zwischen zwei Verteilungen an einem Punkt durch unsere Zeugenfunktion gemessen werden. Wir suchen additionally nur nach Punkten, die ihren absoluten Wert im Kontext von maximieren. X Und PMit anderen Worten definieren wir unseren Kritik-„Rating“ als
Oder in der brauchbareren Näherungsform:
Um die gewünschte Anzahl an Kritikpunkten zu finden, sagen wir M Von ihnen wollen wir einfach die Menge finden C der Größe M das maximiert
Um die Auswahl vielfältigerer Kritiken zu fördern, schlägt das Papier auch vor, einen Regularisierungsterm hinzuzufügen, der dazu anregt, dass ausgewählte Kritiken so weit wie möglich auseinander liegen. Der im Papier vorgeschlagene Regularisierer ist der Log-Determinanten-Regularisierer, obwohl dies nicht erforderlich ist. Ich werde hier nicht näher darauf eingehen, da dies nicht kritisch ist, aber das Papier schlägt vor, (6) zu lesen.².
Damit realisieren wir eine äußerst naiv MMD-Kritik ohne Kritik-Regularisierung wie folgt (verwenden Sie dies NICHT):
import math
import itertoolsdef euc_distance(p1, p2):
return math.sqrt(sum((x - y) ** 2 for x, y in zip(p1, p2)))
def rbf(v1, v2, sigma=0.5):
return math.exp(-euc_distance(v1, v2) ** 2/(2 * sigma**0.5))
def mmd_sq(X, Y, sigma=0.5):
sm_xx = 0
for x in X:
for x2 in X:
sm_xx += rbf(x, x2, sigma)
sm_xy = 0
for x in X:
for y in Y:
sm_xy += rbf(x, y, sigma)
sm_yy = 0
for y in Y:
for y2 in Y:
sm_yy += rbf(y, y2, sigma)
return 1/(len(X) ** 2) * sm_xx
- 2/(len(X) * len(Y)) * sm_xy
+ 1/(len(Y) ** 2) * sm_yy
def select_protos(X, n, sigma=0.5):
min_score, min_sub = math.inf, None
for subset in itertools.mixtures(X, n):
new_mmd = mmd_sq(X, subset, sigma)
if new_mmd < min_score:
min_score = new_mmd
min_sub = subset
return min_sub
def criticism_score(criticism, prototypes, X, sigma=0.5):
return abs(1/len(X) * sum((rbf(criticism, x, sigma) for x in X))
- 1/len(prototypes) * sum((rbf(criticism, p, sigma) for p in prototypes)))
def select_criticisms(X, P, n, sigma=0.5):
candidates = (c for c in X if c not in P)
max_score, crits = -math.inf, ()
for subset in itertools.mixtures(candidates, n):
new_score = sum((criticism_score(c, P, X, sigma) for c in subset))
if new_score > max_score:
max_score = new_score
crits = subset
return crits
Die obige Implementierung ist so unpraktisch, dass ich bei der Ausführung nicht in der Lage conflict, in einem Datensatz mit 25 Punkten in angemessener Zeit 5 Prototypen zu finden. Dies liegt daran, dass unsere MMD-Berechnung O(max(|X|, |Y|)²)und die Iteration über jede Teilmenge der Länge n ist O(C(|X|, n)) (wobei C die Auswahlfunktion ist), was zu einer furchtbaren Laufzeitkomplexität führt.
Wenn wir nicht auf effizientere Berechnungsmethoden zurückgreifen (z. B. reine Numpy/Numexpr/Matrix-Berechnungen anstelle von Schleifen/was auch immer) und wiederholte Berechnungen zwischenspeichern, können wir auf theoretischer Ebene einige Optimierungen vornehmen. Erstens ist die offensichtlichste Verlangsamung, die wir haben, das Schleifen über die C(|X|, n) Teilmengen in unseren Prototyp- und Kritikmethoden. Stattdessen können wir eine Näherung verwenden, die eine Schleife durchläuft N mal, wobei wir jedes Mal gierig den besten Prototypen auswählen. Dadurch können wir unseren Prototypenauswahlcode ändern in
def select_protos(X, n, sigma=0.5):
protos = ()
for _ in vary(n):
min_score, min_proto = math.inf, None
for cand in X:
if cand in protos:
proceed
new_score = mmd_sq(X, protos + (cand), sigma)
if new_score < min_score:
min_score = new_score
min_proto = cand
protos.append(min_proto)
return protos
und ähnliches gilt für die Kritik.
Es gibt noch ein weiteres wichtiges Lemma, das dieses Downside viel optimierbarer macht. Es stellt sich heraus, dass wir die Kostenfunktion sehr effizient mit Matrixoperationen berechnen können, indem wir unsere Prototypauswahl in ein Minimierungsproblem umwandeln und den Kosten einen Regularisierungsterm hinzufügen. Ich werde hier nicht näher darauf eingehen, aber Sie können sich für weitere Einzelheiten das Originalpapier ansehen.
Nachdem wir nun die MMD-Critic-Methode verstanden haben, können wir endlich damit experimentieren! Sie können sie installieren, indem Sie
pip set up mmd-critic
Die Implementierung im Paket selbst ist viel schneller als die hier vorgestellte, additionally keine Sorge.
Wir können ein ziemlich einfaches Beispiel mit Blobs wie diesen ausführen:
from sklearn.datasets import make_blobs
from mmd_critic import MMDCritic
from mmd_critic.kernels import RBFKerneln_samples = 50 # Whole variety of samples
facilities = 4 # Variety of clusters
cluster_std = 1 # Commonplace deviation of the clusters
X, _ = make_blobs(n_samples=n_samples, facilities=facilities, cluster_std=cluster_std, n_features=2, random_state=42)
X = X.tolist()
# MMD critic with the kernel used for the prototypes being an RBF with sigma=1,
# for the criticisms one with sigma=0.025
critic = MMDCritic(X, RBFKernel(1), RBFKernel(0.025))
protos, _ = critic.select_prototypes(facilities)
criticisms, _ = critic.select_criticisms(10, protos)
Wenn wir dann die Punkte und Kritikpunkte auflisten, erhalten wir
Sie werden feststellen, dass ich die Möglichkeit bereitgestellt habe, einen separaten Kernel für die Auswahl von Prototypen und Kritiken zu verwenden. Dies liegt daran, dass ich festgestellt habe, dass insbesondere die Ergebnisse für Kritiken äußerst empfindlich gegenüber dem Sigma-Hyperparameter. Dies ist eine bedauerliche Einschränkung der MMD Critic-Methode und der Kernelmethoden im Allgemeinen. Insgesamt habe ich gute Ergebnisse erzielt, indem ich für Prototypen ein großes Sigma und für Kritiken ein kleineres verwendet habe.
Wir können natürlich auch einen komplizierteren Datensatz verwenden. Hier ist zum Beispiel die Methode, die bei MNIST verwendet wurde³:
from sklearn.datasets import fetch_openml
import numpy as np
from mmd_critic import MMDCritic
from mmd_critic.kernels import RBFKernel# Load MNIST information
mnist = fetch_openml('mnist_784', model=1)
photos = (mnist('information').astype(np.float32)).to_numpy() / 255.0
labels = mnist('goal').astype(np.int64)
critic = MMDCritic(photos(:15000), RBFKernel(2.5), RBFKernel(0.025))
protos, _ = critic.select_prototypes(40)
criticisms, _ = critic.select_criticisms(40, protos)
was uns zu den folgenden Prototypen bringt
und Kritik
Ziemlich cool, oder?
Und das conflict es auch schon mit der MMD-Critic-Methode. Sie ist im Kern recht einfach und lässt sich intestine verwenden, abgesehen davon, dass man mit dem Sigma-Hyperparameter herumspielen muss. Ich hoffe, dass das neu veröffentlichte Python-Paket ihr mehr Verwendungsmöglichkeiten bietet.
Bei Fragen wenden Sie sich bitte an mchak@calpoly.edu. Alle Bilder stammen vom Autor, sofern nicht anders angegeben.