A new perspective on principal component analysis: PCA as a Nash equilibrium
Principal component analysis (PCA) is a method used in machine-learning contexts to find a set of vectors (principal components) that explain a significant portion of the variance in a dataset. A common problem that many data scientists face with datasets is that the number of features tends to be very large, and it is hard to visualize how exactly that data looks in such high dimensions. In fact, many distance-based algorithms suffer when high-dimensional data is input due to the “curse of dimensionality”: the idea that distances become further apart and more concentrated in higher dimensions. PCA allows us, in some cases, to find a lower-dimensional subspace that the data lie upon, which helps alleviate concerns with the curse of dimensionality and, in many cases, improve algorithmic performance.
The common way to find the set of principal components that define this lower-dimensional subspace is through an eigendecomposition of the covariance matrix, or a singular-value decomposition of the data matrix. However, the authors in this paper propose an alternative approach to finding these vectors: by treating PCA as a game where each eigenvector is controlled by an agent, with the goal of maximizing some utility function. The solution to PCA happens to be the Nash equilibrium of this game, the authors claim.
A Nash equilibrium specifies a set of strategies by each player such that no player can improve their expected utility if they deviate from their current strategy. If we look at this in terms of how the principal components are computed using a decomposition, this interpretation makes sense: any principal component should be orthogonal to all previous principal components (otherwise, it would explain some variance that has already been accounted for, which does not count). Additionally, the principal components are determined in order: the first principal component is a general direction in the high-dimensional space with maximum explanation of the variance in the data, and any future principal components are affected by our choice of the first principal component.
The calculation of variance for each principal component in PCA is simple: it is proportional to the eigenvalue corresponding to the eigenvector in the eigendecomposition of the covariance matrix. Thus, a natural utility function to use should somehow relate to the calculated eigenvalues in the final solution of PCA: wavering from the current principal components will decrease explained variance and hence, decrease utility.
Ultimately, the authors were able to develop an “eigengame” that learns the principal components in order by maximizing utility with a Nash interpretation, additionally guaranteeing convergence. Hence, a fresh interpretation of the PCA problem is provided, and this new view, as the authors state, could be incredibly useful for further algorithmic developments.
Resources:
https://doi.org/10.48550/arXiv.2010.00554 – EigenGame: PCA as a Nash Equilibrium
https://doi.org/10.1098/rsta.2015.0202 – Principal component analysis: a review and recent developments