Eigengame

Eigengame

• re-implementation in Python based on XXX (references)

EigenGame is a method of performing principal component analysis developed by DeepMind. The original paper is here. I will give a walkthrough of the code, which is shown below:

import numpy as np

def calc_penalties(data, vectors, index):
    
    vec = vectors[:, index]
    penalties = np.zeros_like(np.dot(data, vectors[:, 0]))
    
    for i in range(index):
        result = np.dot(data, vectors[:, i])
        penalties += (np.dot(np.dot(data, vec), result) /
         np.dot(result, result)
        ) * result

    return penalties 
     
def eigengame(data, n_components, epochs=100, learning_rate=0.1):
    
    dim = data.shape[1]
    vectors = np.ones((dim, n_components))
    for t in range(n_components):
        for epoch in range(epochs):
            rewards = np.dot(data, vectors[:, t])
            penalties = calc_penalties(data, vectors, t)
            
            delta_v = 2*np.dot(data.T, rewards - penalties)
            vectors[:, t] = vectors[:, t] + learning_rate * delta_v
            vectors[:, t] = vectors[:, t] / np.linalg.norm(vectors[:, t])
            
    return vectors

eigengame() is the main function, while calc_penalties() is a helper function used by eigengame(). In a nutshell, eigengame() takes in an array of data of the form (features x samples), then calculates and returns the eigenvectors of the covariance matrix of that data. The number of eigenvectors to calculate is specified by the n_components parameter.

The first step is to initialize our eigenvectors:

dim = data.shape[1]
vectors = np.ones((dim, n_components))

They are initially set to vectors of all ones, but the algorithm will converge them to their correct values. We then step into a nested for loop. The outer layer goes through each of the eigenvectors, and the inner loop cycles through a set amount of iterations. With each iteration, the current eigenvector will move a bit closer to its correct value.

for t in range(n_components):
   for epoch in range(epochs):
      ...
      ...   

We calculate the rewards vector. This can be thought of as how well our estimated eigenvector passes for an actual eigenvector. We want to increase the reward i.e. increasing this vector's magnitude.

rewards = np.dot(data, vectors[:, t])

The following image shows where the analog of this line of code is written in the paper:

Next we calculate the penalties vector. This measures how parallel the current eigenvector is with respect to every other eigenvector. The goal is to push every eigenvector to be orthogonal with every other eigenvector (we want to reduce the parallel-ness!). Hence we want the penalties vector to be as low as possible, ideally zero.

In the code, this is where the helper function calc_penalties comes into play. We pass into the helper function our input data, the set of eigenvectors, and the index of the eigenvector which needs to have its parallel-ness with every other eigenvector calculated.

penalties = calc_penalties(data, vectors, t)

Here is the function:

def calc_penalties(data, vectors, index):
    vec = vectors[:, index] #Grab the relevant vector
    penalties = np.zeros_like(np.dot(data, vectors[:, 0])) #Create a vector of zeros in the shape of an eigenvector
    
    #Cycle through the eigenvectors that come BEFORE the relevant eigenvector and calculate the parallel-ness between the two.
    #This penalty is aggregated into the penalties vector.

    for i in range(index): 

        result = np.dot(data, vectors[:, i])
        penalties += (np.dot(np.dot(data, vec), result) /
         np.dot(result, result)
        ) * result
    
    #Return the penalties vector
    return penalties 

With respect to the paper, here is the associated line:

We then take the difference between rewards and penalties, matrix-multiply it with our data, then store it in the delta_v vector. This vector points toward the direction that we want to update our eigenvector in!

delta_v = 2*np.dot(data.T, rewards - penalties)

We then add this update vector times a learning rate constant to our eigenvector. We then normalize our eigenvector to maintain a length of 1.

vectors[:, t] = vectors[:, t] + learning_rate * delta_v
vectors[:, t] = vectors[:, t] / np.linalg.norm(vectors[:, t])

These lines of code are mirrored by the following lines of pseudocode in the paper:

That concludes a single iteration for a single eigenvector. By default the function will run 100 iterations for each eigenvector.

After the nested for loop finishes, the transpose of our eigenvector matrix is returned:

return vectors.T