Embedding Dimension Lower Bounds for Universality of Deep Sets and Janossy Pooling

Technische Zusammenfassung: Untere Schranken für die Einbettungsdimension zur Universalität von Deep Sets und Janossy Pooling

Problemstellung
Der Artikel behandelt die theoretische Frage der Universalität in permutationsinvarianten neuronalen Netzwerkarchitekturen, insbesondere Deep Sets und dessen Verallgemeinerung, Janossy Pooling. Zwar ist erwiesen, dass diese Architekturen jede stetige permutationsinvariante Funktion approximieren können, doch bleibt ein kritisches offenes Problem bestehen: die Bestimmung der minimalen Einbettungsdimension $M$ (der latenten Dimension), die erforderlich ist, um diese Universalität zu garantieren.

Vorherige Arbeiten lieferten obere Schranken (z. B. $M \le 2nd + 1$ für Deep Sets mit $d>1$) und triviale untere Schranken (z. B. $M \ge n$ für $d=1$). Für Deep Sets mit $d > 1$ und für $k$-stelliges Janossy Pooling mit $k > 1$ waren jedoch keine nicht-trivialen unteren Schranken bekannt, die mit der umgebenden Dimension $d$ skalieren. Der Artikel konzentriert sich auf den Fall skalaren Ausgabes ($p=1$) über dem Bereich $K = [0, 1]^d$ und definiert $M_{univ}(d, n, k)$ als die für die Universalität erforderliche minimale Einbettungsdimension.

Methodik
Die Autoren führen eine neuartige Technik ein, die auf dem Borsuk-Ulam-Theorem basiert, um untere Schranken für die Einbettungsdimension zu etablieren. Die Methodik verläuft über mehrere Schlüsselschritte:

1. Reduktion auf indiziertes Janossy Pooling: Die Autoren zeigen zunächst, dass, falls die standardmäßige $k$-stellige Janossy-Architektur universell ist, dies die Universalität einer größeren, nicht-invarianten Klasse namens „indiziertes Janossy Pooling" impliziert. Bei dieser indizierten Variante dürfen die Encoder-Funktionen $\phi_{i_1, \dots, i_k}$ von den spezifischen Indizes des Eingabetupels abhängen, anstatt über alle Permutationen hinweg geteilt zu werden. Diese Reduktion ermöglicht es den Autoren, untere Schranken für die indizierte Klasse zu beweisen, die automatisch auf die ursprüngliche symmetrische Klasse anwendbar sind.
2. Finite-Difference-Rigidität: Ein entscheidendes Lemma wird etabliert, das zeigt, dass indizierte Janossy-latente Abbildungen eine spezifische „Finite-Difference-Rigidität" erfüllen. Wenn die Abbildung auf einer „achsigen" Teilmenge eines Gitters übereinstimmt (wobei mindestens eine Koordinate null ist), muss sie auf dem gesamten Gitter übereinstimmen. Diese Eigenschaft verknüpft das Verhalten des Encoders auf einer dünn besetzten Menge von Eingaben mit seinem Verhalten auf einem dichten Gitter.
3. Borsuk-Ulam-Konstruktion: Um die untere Schranke zu beweisen, konstruieren die Autoren zwei disjunkte kompakte Mengen, $E_+$ und $E_-$, innerhalb des Eingaberaums. Sie nutzen das Borsuk-Ulam-Theorem, um zu zeigen, dass, wenn die Einbettungsdimension $M$ zu klein ist (speziell, wenn $M$ unterhalb eines abgeleiteten Schwellenwerts liegt), jeder stetige Encoder $\Phi$, der nach $\mathbb{R}^M$ abbildet, ein Paar antipodaler Punkte (einen aus $E_+$ und einen aus $E_-$) auf denselben latenten Vektor abbilden muss.
4. Kollisionsargument: Durch die Konstruktion einer stetigen Zielfunktion $g$, die auf $E_-$ bzw. $E_+$ verschiedene Werte (0 und 1) annimmt, zeigen die Autoren, dass, wenn der Encoder Punkte aus diesen Mengen auf denselben latenten Vektor abbildet, kein Decoder $\rho$ in der Lage ist, $g$ mit einem Fehler kleiner als $1/2$ zu approximieren. Dieser Widerspruch beweist, dass die angenommene Dimension $M$ für die Universalität unzureichend ist.

Hauptbeiträge und Ergebnisse

• Neue untere Schranke für Deep Sets ($k=1$): Der Artikel beweist, dass für Deep Sets, die auf Mengen von $n$ Punkten in $\mathbb{R}^d$ wirken, die minimale Einbettungsdimension die folgende Bedingung erfüllt:
  $$M_{univ}(d, n, 1) \ge d(n - 1)$$
  Dies ist die erste untere Schranke für $d > 1$, die mit der umgebenden Dimension $d$ wächst. In Kombination mit der bestehenden oberen Schranke von $2nd + 1$ (von Dym–Gortler) wird damit festgestellt, dass die erforderliche Dimension bis auf konstante Faktoren als $\Theta(nd)$ skaliert. Für $d=1$ ergibt die Schranke $n-1$ und stellt damit die bekannte lineare Abhängigkeit von $n$ bis auf eine additive Konstante wieder her.

• Erste nicht-triviale untere Schranke für $k$-stelliges Janossy Pooling ($k > 1$): Für allgemeines $k$-stelliges Janossy Pooling leiten die Autoren die erste nicht-triviale untere Schranke ab, die von $d$ abhängt. Das Ergebnis lautet:
  $$M_{univ}(d, n, k) \gtrsim_k (d(n - k))^{1/k}$$
  Dieses Ergebnis zeigt, dass selbst bei Interaktionen endlicher Ordnung ($k > 1$) die erforderliche latente Dimension sowohl mit der umgebenden Dimension $d$ als auch mit der Mengengröße $n$ wachsen muss.

• Technischer Rahmen: Der Artikel liefert einen rigorosen Rahmen zur Analyse der Universalität, indem symmetrische Architekturen auf indizierte reduziert und topologische Hindernisse (Borsuk-Ulam) auf Abbildungen des latenten Raums angewendet werden.

Bedeutung und Einschränkungen
Der Artikel behauptet, dass diese Ergebnisse ein signifikantes offenes Problem lösen, das in der vorherigen Literatur bezüglich der Dimensionsanforderungen für permutationsinvariante Netzwerke hervorgehoben wurde. Insbesondere wird bestätigt, dass für Deep Sets die Einbettungsdimension sowohl linear mit $n$ als auch mit $d$ skalieren muss, wodurch frühere Lücken korrigiert werden, in denen nur $n$-abhängige Schranken für $d>1$ bekannt waren. Für $k$-stelliges Pooling wird etabliert, dass Interaktionen die Notwendigkeit eines Dimensionswachstums mit $d$ nicht eliminieren.

Die Autoren weisen auf spezifische Einschränkungen in ihrer aktuellen Konstruktion hin:

• Für Deep Sets ($k=1$) beträgt die Schranke $d(n-1)$ statt $dn$. Dieser „Verlust" eines Punktes ergibt sich daraus, dass die Beweisstrategie einen Variablblock benötigt, um die beiden im Borsuk-Ulam-Argument verwendeten disjunkten kompakten Mengen zu trennen.
• Für $k > 1$ ist der Exponent $1/k$ in der unteren Schranke eine Einschränkung der aktuellen Konstruktion, die $k$ Basisvariablen verwendet, um Regionen auf einer Sphäre zu kennzeichnen. Dies lässt eine erhebliche Lücke zwischen der abgeleiteten unteren Schranke und der vererbten oberen Schranke von $O(nd)$ aus Deep Sets bestehen.

Der Artikel kommt zu dem Schluss, dass die Bestimmung der exakten Abhängigkeit von $d$, $n$ und $k$ sowie der Beweis übereinstimmender oberer und unterer Schranken für Janossy Pooling endlicher Ordnung ein offenes Problem bleibt.