Aufgabe: Kapazität des Skalarproduktes

Das mit dem (Un-)Supervised Learning schauen wir uns nun in einem sehr einfachen Beispiel an und fragen uns
Wieviele Bits kann ein einziges Neuron eigentlich speichern?

Aufgabe (Theorie)

Wir betrachten also die Rekonstruktionen \(\hat y_i\) des Neuron gegeben durch \(f_\omega(x) := w^T\cdot x\) mit Parameter \(\omega\) und Aktivierungsfunktion \(a\): \[ \hat y_i := a\left(f_\omega\left(x_i\right)\right),\qquad a(x) = \left\{\begin{matrix} 1 & x>0\\ 0 & x ≤ 0\end{matrix}\right. \]

Es sei nun \(T(N,K)\) die Anzahl verschiedener Funktionen \(f_\omega\), um eine beliebige aber feste Menge von \(N\) Punkte in \(K\) Dimensionen auf je eine Ausgabe \(\{0,1\}\) abzubilden. (Alle Punkte seien dabei in allgemeiner Lage. Im Prinzip gehen wir so davon aus, dass keine zwei Punkte gleichzeitig auf der so definierten Null-Ebene von \(f_\omega\) liegen).)

1. Unser Ziel ist es, eine Formel für \(T(N,K)\) zu finden: Die folgenden Aufgaben sollen dabei den richtigen Lösungsansatz liefern. (Überspringen Sie diese Teilaufgabe gerne, falls Sie hier stecken bleiben. Eine Rekursive Formel finden Sie im Eingeklappten Bereich "Lösungsansatz".)
   
   
   Lösungsansatz

   1. Beginnen Sie mit \(K=1\) und Datensatz der größe \(N\). Wieviele verschiedene Funktionen von \(N\) Punkten können mit der Familie \(f_\omega\) abgebildet werden?
   2. Nun zum umgekehrten Fall: \(N = 1\), beliebige Dimension \(K\). Wieviele verschiedene Funktionen sind es jetzt?
   3. Es sei nun \(K = 2\) und \(N\) beliebig. Wie groß ist \(T(N,K)\)?
      
      Hinweis: Für \(N≥3\) können nicht mehr alle möglichen Zuweisungen repräsentiert werden. (Beispiel: XOR). Hinweisbild:
      View Exception

      ---

      An Error occured during translation in 'html'-View
      
      

      Traceback

      Traceback (most recent call last):
        File "/usr/local/lib/python3.8/site-packages/luke/views/View.py", line 315, in handle_dict
          return "{}".format(self.translator[mytype](adict, scopes))
        File "/usr/local/lib/python3.8/site-packages/luke/views/View.py", line 81, in translate_x_with_scope
          return translate_x(self, x, scopes, var, run)
        File "/usr/local/lib/python3.8/site-packages/luke/views/View.py", line 550, in translate_tikz
          output = subprocess.check_output(
        File "/usr/local/lib/python3.8/subprocess.py", line 411, in check_output
          return run(*popenargs, stdout=PIPE, timeout=timeout, check=True,
        File "/usr/local/lib/python3.8/subprocess.py", line 489, in run
          with Popen(*popenargs, **kwargs) as process:
        File "/usr/local/lib/python3.8/subprocess.py", line 854, in __init__
          self._execute_child(args, executable, preexec_fn, close_fds,
        File "/usr/local/lib/python3.8/subprocess.py", line 1702, in _execute_child
          raise child_exception_type(errno_num, err_msg, err_filename)
      FileNotFoundError: [Errno 2] No such file or directory: 'pdflatex'
      

      
      
      
   4. Zeigen Sie, dass für beliebige \(K\) and \(N\) die Gleichung \( \begin{align} T(N,K) &= T(N-1,K) + T(N-1,K-1)\\ \end{align} \) gilt.
   5. Leiten Sie entweder eine geschlossene Formel für \(T(N,K)\) her, oder einfacher: bestimmen Sie programmatisch die Anzahl für \(1 \le K \le 100\) und \(1 \le N \le 300\).
   
   
   
2. Bestimmen Sie nun den Quotienten \(\frac{T(N,K)}{2^N}\) und bestimmen Sie Approximativ den Wert in den angegebenen Bereichen \[ \frac{T(N,K)}{2^N} \approx \left\{\begin{matrix} ?, & N≤\phantom{[}K\phantom{2KK} \\ ?, & N\in[K,2K)\\ ?, & N = \phantom{[}2K\phantom{2K)}\\ ?, & N > \phantom{[}2K\phantom{2K)}\\ \end{matrix}\right. \]
   1. Plotten Sie dazu am besten den Graph von \(\frac{T(N,K)}{2^N}\). Etwas besser sichtbar ist das Ganze, wenn Sie in der visualisierung die Achse für \(N\) durch \(N/K\) substituieren bzw. die \(N\)-Achse mit \(1/K\) strecken.
   2. Was können Sie dem Plott entnehmen, etwa im Hinblick die angegebenen Bereiche, insbesondere \(N \approx 2K\).

Aufgabe (Praxis)

Wir drehen die Aufgabe nun um: Wir starten mit dem Skalarprodukt auf einem gegebenen Datensatz, dass diesen möglichst "optimal" löst. Das Ziel ist nun zu bestimmen, wieviele Bits dieses Skalarprodukt in der Praxis tatsächlich speichert bzw. rekonstruieren kann.

Dazu schaun wir uns den Datensatz CIFAR-10 an: Der Datensatz besteht aus 10 Klassen (airplane, automobile, bird, cat, deer, dog, frog, horse, ship, truck) zu je \(12.000\) Farb-Bildern, wiederum jeweils bestehend aus \(32\cdot 32\) Pixeln.

import matplotlib.pyplot as plt
import numpy as np

def imshow(img):
    img = img / 2 + 0.5     # unnormalize
    npimg = img.numpy()
    plt.imshow(np.transpose(npimg, (1, 2, 0)))
    plt.show()

batch_size = 64 # number of images to get for every iteration of trainloader
trainset = torchvision.datasets.CIFAR10(root='./data', train=True, download=True, transform=transform)
trainloader = torch.utils.data.DataLoader(trainset, batch_size=batch_size, shuffle=True, num_workers=2)
classes = ('class-%i' % i for i in range(10))

# get some random training images
dataiter = iter(trainloader)
images, labels = dataiter.next()

# show images
imshow(torchvision.utils.make_grid(images))
# print labels
print(' '.join('%5s' % classes[labels[j]] for j in range(batch_size)))

1. Vorbereitung: Im Falle einer Klasse gleicht das Modell im Grunde dem einer Support-Vector-Maschine (SVM). (Im Falle dass sie den Mechanismus nicht kennen, ist dies nicht so schlimm, gehen Sie einfach davon aus, dass der Algorithmus für uns ein "gutes" Gewicht für das obige Skalarprodukt wählt.
   
   Wir ermitteln also eine SVM, am einfachsten per sklearn.
   
   

   svm = LinearSVC(dual=False, max_iter=25)
   svm.fit(traindata.reshape((num_examples,-1)), trainlabels)
   trainlabels_reconstruct = svm.predict(traindata.reshape((num_examples,-1)))
   
   # übrigens: das Gewicht w können Sie per svm.coeff_ einsehen.
   

   
   
   Als Datensatz wählen wir wieder CIFAR-10.

   trainset = torchvision.datasets.CIFAR10(root='./data', train=True, download=True, transform=torchvision.transforms.ToTensor())
   traindata   = trainset.train_data.numpy()
   trainlabels = trainset.test_labels.numpy()
   

   
   
   Filtern Sie den Datensatz zuerst, sodass nur zwei Klassen enthalten sind, etwa 4 und 7.
2. Nutzen Sie nun predict wie oben angegeben, und Zählen Sie wieviele Punkte (des Trainingssets!) korrekt auswendig gelernt wurden.
3. Wievielen gelernten Bits entspricht das in etwa? Insbesondere: Wie passt das Ergebnis zu unserer theoretisch ermittelten Kapazität von oben zusammen?.