\section{Technical Approach and Method}

\subsection{Measure of Compactness for a Representation}\label{sec:lossy-coding}
Although the above  properties are all highly desirable for the latent representation $\z$, they are by no means easy to obtain: Are these properties compatible so that we can expect to achieve them all at once? If so, is there  a {\em simple but principled} objective that can measure the goodness of the resulting representations in terms of all these properties? The key to  these questions {is to find} a principled ``measure of compactness'' for the distribution of a random variable $\z$ or from its finite samples $\Z$. Such a measure should directly and accurately characterize intrinsic geometric or statistical properties of the distribution, in terms of its intrinsic dimension or {volume}. Unlike cross-entropy \eqref{eqn:cross-entropy} or information bottleneck \eqref{eqn:information-bottleneck}, such a measure should not depend explicitly on class labels so that it can work in all supervised, self-supervised, semi-supervised, and unsupervised settings.  


\textbf{Low-dimensional degenerate distributions.} In information theory \cite{Thomas-Cover}, the notion of entropy $H(\z)$ is designed to be such a measure.\footnote{given the probability density $p(\z)$ of a random variable, $H(\z) \doteq - \int p(\z) \log p(\z) \, d\z.$} However, entropy is not  well-defined for continuous random variables with degenerate distributions.\footnote{The same difficulty resides with evaluating mutual information $I(\x, \z)$ for degenerate distributions.} This is unfortunately the case here. To alleviate this difficulty, another related concept in information theory, more specifically in lossy data compression, that measures the ``compactness'' of a random distribution is the so-called {\em rate distortion} \cite{Thomas-Cover}: {Given a random variable $\z$ and a prescribed precision $\epsilon >0$, the rate distortion $R(\z, \epsilon)$ is the minimal number of binary bits needed to encode $\z$ such that the expected decoding error\footnote{Say in terms of the $\ell^2$-norm, we have $\mathbb E[\|\z - \widehat \z \|_2] \le \epsilon$ for the decoded $\widehat \z$.} is less than $\epsilon$. Although this framework has been successful in explaining feature selection in deep networks \cite{rate-distortion}, the rate distortion of a random variable is difficult, if not impossible to compute, except for simple distributions such as discrete and Gaussian. }


\textbf{Nonasymptotic rate distortion for finite samples.} When evaluating the lossy coding rate $R$, one practical difficulty is that we normally do not know the distribution of $\z$.  Instead, we have a finite number of samples as learned representations where $\z_{i} = f(\x_i, \theta) \in \R^{d}, i = 1,\ldots, m$, for the given data samples $\X = [\x_1, \ldots, \x_m]$. Fortunately, \cite{ma2007segmentation} provides a precise estimate on the number of binary bits needed to encoded finite samples from a subspace-like distribution. In order to encode the learned representation $\Z = [\z_1, \dots, \z_m]$ up to a precision $\epsilon$, the total number of bits needed is given by the following expression\footnote{This formula can be derived either by packing $\epsilon$-balls into the space spanned by $\Z$ or by computing the number of bits needed to quantize the SVD of $\Z$ subject to the precision, see \cite{ma2007segmentation} for proofs.}:  $\cL(\Z, \epsilon) \doteq \left(\frac{m + d}{2}\right)\log \det\left(\I + \frac{d}{m\epsilon^{2}}\Z\Z^{\top}\right)$. Therefore, the compactness of learned features {\em as a whole} can be measured in terms of the average coding length per sample (as the sample size $m$ is large),  a.k.a. the {\em coding rate} subject to the distortion $\epsilon$:
\begin{equation}
R(\Z,\epsilon) \doteq \frac{1}{2}\log\det\left(\I + \frac{d}{m\epsilon^{2}}\Z\Z^{\top}\right).
\label{eqn:coding-length-eval}
\end{equation} 


\textbf{Rate distortion of data with a mixed distribution.} {In general,}  the features $\Z$ of multi-class data may belong to multiple low-dimensional subspaces. To evaluate the rate distortion of such mixed data {\em more accurately}, we may partition the data $\Z$ into multiple subsets: $\Z = \Z_1 \cup \cdots \cup \Z_k$, {with} each in one low-dim subspace. So the above coding rate \eqref{eqn:coding-length-eval} is accurate for each subset. For convenience, let $\bm{\Pi} = \{\bm{\Pi}_j \in \Re^{m \times m}\}_{j=1}^{k}$ be a set of diagonal matrices whose diagonal entries encode the membership of the $m$ samples in the $k$ classes.\footnote{That is, the diagonal entry $\bm \Pi_j(i,i)$ of $\bm \Pi_j$ indicates the probability of sample $i$ belonging to subset $j$. Therefore $\bm{\Pi}$ lies in a simplex: ${\Omega} \doteq \{\bm{\Pi} \mid \bm{\Pi}_j \ge \mathbf{0}, \; \bm{\Pi}_1 + \cdots + \bm{\Pi}_k = \I\}.$} Then, according to \cite{ma2007segmentation}, with respect to this partition, the average number of bits per sample (the coding rate) is
\begin{equation}
R^c(\Z,  \epsilon \mid \bm{\Pi}) \doteq \sum_{j=1}^{k}
\frac{\tr(\bm{\Pi}_j)}{2m}\log\det\left(\I + \frac{d}{\tr(\bm{\Pi}_j)\epsilon^{2}}\Z\bm{\Pi}_j\Z^{\top}\right).
\label{eqn:compress-loss-eval}
\end{equation}
Notice that when $\Z$ is given, $R^c(\Z, \epsilon \mid \bm{\Pi})$ is a concave function of $\bm{\Pi}$.
The function $\log\det(\cdot)$ in the above expressions has been long known as an effective heuristic for rank minimization problems, with guaranteed convergence to local minimum \cite{fazel2003log-det}. {As it nicely characterizes the rate distortion of Gaussian or subspace-like distributions, $\log\det(\cdot)$ can be very effective in clustering or classification of mixed data \cite{ma2007segmentation,wright2008classification,kang2015logdet}.} We will soon reveal more desired properties of this function. 


\subsection{Principle of Maximal Coding Rate Reduction}\label{sec:principle-mcr2}
On one hand, for learned features to be discriminative, features of different classes/clusters are preferred to be {\em maximally incoherent} to each other. Hence they together should span a space of the largest possible volume (or dimension) and the coding rate of the whole set $\Z$ should be as large as possible. On the other hand, learned features of the same class/cluster should be highly correlated and coherent. Hence, each class/cluster should only span a space (or subspace) of a very small volume and the coding rate should be as small as possible. Therefore, a good representation $\Z$ of $\X$ is one such that, given a partition $\bm{\Pi}$ of $\Z$, achieves a large difference between the coding rate for the whole and that for all the subsets:
\begin{equation}
\Delta R(\Z, \bm{\Pi}, \epsilon) \doteq R(\Z, \epsilon) - R^c(\Z, \epsilon \mid  \bm{\Pi}).
\label{eqn:coding-length-reduction}
\end{equation}
If we choose our feature mapping $\z = f(\x,\theta)$ to be a deep neural network, the overall process of the feature representation and the resulting rate reduction w.r.t. certain partition $\bm{\Pi}$ can be illustrated by the following diagram:
\begin{equation}
    \X 
    \xrightarrow{\hspace{2mm} f(\x, \theta)\hspace{2mm}} \Z(\theta) \xrightarrow{\hspace{2mm} \bm{\Pi},\epsilon \hspace{2mm}} \Delta R(\Z(\theta), \bm{\Pi}, \epsilon).
    \label{eqn:flow}
\end{equation}

Note that $\Delta R$ is {\em monotonic} in the scale of the features $\Z$. So to make the amount of reduction comparable between different representations,\footnote{Here different representations can be either representations associated with different network parameters or representations learned after different layers of the same deep network.} we need to {\em normalize the scale} of the learned features, either by imposing the Frobenius norm of each class $\Z_j$ to scale with the number of features in $\Z_j \in \mathbb R^{d \times m_j}$: $\|\Z_j\|_F^2 = m_j$ or by normalizing each feature to be on the unit sphere: $\z_i \in \mathbb{S}^{d-1}$. This formulation offers a natural justification for the need of ``batch normalization'' in the practice of 
training deep neural networks \cite{ioffe2015batch}. An alternative, arguably simpler, way to normalize the scale of learned representations is to ensure that the mapping of each layer of the network is approximately {\em isometric} \cite{ISOnet}.

Once the representations are comparable, our goal becomes to learn a set of features $\Z(\theta) = f(\X, \theta)$ and their partition $\bm \Pi$ (if not given in advance) such that they maximize the reduction between the coding rate of all features and that of the sum of features w.r.t. their classes:
\vspace*{0.05in} 
\begin{equation}
 \max_{\theta, \bm{\Pi}} \;  \Delta R\big(\Z(\theta), \bm{\Pi}, \epsilon\big) = R(\Z(\theta), \epsilon) - R^c(\Z(\theta),  \epsilon \mid \bm{\Pi}), \quad \mbox{s.t.} \ \ \,  \|\Z_j(\theta)\|_F^2 = m_j, \, \bm{\Pi} \in {\Omega}.
\label{eqn:maximal-rate-reduction}
\end{equation}
We refer to this as the principle of {\em maximal coding rate reduction} (MCR$^2$), 
{an embodiment of Aristotle's famous quote:  ``{\em the whole is greater than the sum of the  parts.}''}  Note that for the clustering purpose alone, one may only care about the sign of $\Delta R$ for deciding whether to partition the data or not, which leads to the greedy algorithm in \cite{ma2007segmentation}.\footnote{Strictly speaking, in the context of clustering {\em finite} samples, one needs to use the more precise measure of the coding length mentioned earlier, see \cite{ma2007segmentation} for more details.} Here to seek or learn the best representation, we further desire the whole is {\em maximally} greater than its parts. 


\textbf{Relationship to  information gain.} 
The maximal coding rate reduction can be viewed as a generalization to {\em Information Gain} (IG), which aims to maximize the reduction of entropy of a random variable, say $\bm z$, with respect to an observed attribute, say $\bm \pi$:
$
\max_{\bm \pi} \; \mbox{IG}(\bm z, \bm \pi) \doteq H(\bm z) - H(\bm z \mid \bm \pi),
$
i.e., the {\em mutual information} between $\z$ and $\bm \pi$ \cite{Thomas-Cover}. Maximal information gain has been widely used in areas such as decision trees \cite{decision-trees}. However, MCR$^2$ is used differently in several ways: 1) One typical setting of MCR$^2$ is when the data class labels are given, i.e. $\bm \Pi$ is known, MCR$^2$ focuses on learning representations $\bm z(\theta)$ rather than fitting labels. 2) In traditional settings of IG, the number of attributes in $\bm z$ cannot be so large and their values are discrete (typically binary). Here the ``attributes'' $\bm \Pi$  represent the probability of a multi-class partition for all samples and their values can even be continuous. 3) As mentioned before, entropy $H(\bm z)$ or mutual information $I(\bm z, \bm \pi)$ \cite{hjelm2018learning} is not well-defined for degenerate continuous distributions whereas the rate distortion $R(\bm z, \epsilon)$ is and can be accurately and efficiently computed for (mixed)  subspaces, at least. 


\begin{figure}
\begin{center}

\includegraphics[width=0.65\textwidth]{Figures/pack.pdf}


\end{center}
\vskip -0.05in
\caption{\small Comparison of two learned representations $\Z$ and $\Z'$ via reduced rates: $R$ is the number of $\epsilon$-balls packed in the joint distribution and $R^c$ is the sum of the numbers for all the subspaces (the green balls). $\Delta R$ is their difference (the number of blue balls). The MCR$^2$ principle prefers $\Z$ (the left one).}\label{fig:sphere-packing}
\vskip -0.15in
\end{figure}


\subsection{Properties of the Rate Reduction Function}  
In theory, the MCR$^2$ principle \eqref{eqn:maximal-rate-reduction} benefits from great generalizability and can be applied to representations $\Z$ of {\em any} distributions with {\em any} attributes $\bm \Pi$ as long as the rates $R$ and $R^c$ for the distributions can be accurately and efficiently evaluated. The optimal representation $\Z^*$ and partition $\bm \Pi^*$ should have some interesting geometric and statistical properties. We here reveal nice properties of the optimal representation with the special case of subspaces, which have many important use  cases in machine learning. When the desired representation for $\Z$ is multiple subspaces, the rates $R$ and $R^c$ in \eqref{eqn:maximal-rate-reduction} are given by \eqref{eqn:coding-length-eval}
and \eqref{eqn:compress-loss-eval}, respectively. At the maximal rate reduction, MCR$^2$ achieves its optimal representations, denoted as $\Z^* = \Z_1^*\cup \cdots \cup \Z_k^* \subset \Re^d$ with $\rank{(\Z^*_j)}\le d_j$. One can show that $\Z^*$ has the following desired properties (see Appendix \ref{ap:rate-reduction} for a formal statement and detailed proofs).

\begin{theorem}[Informal Statement]
Suppose $\Z^* = \Z_1^*\cup \cdots \cup \Z_k^*$ is the optimal solution that maximizes the rate reduction~\eqref{eqn:maximal-rate-reduction}. We have:

\begin{itemize}
\item {\em Between-class Discriminative}: As long as the ambient space is adequately large ($d \ge \sum_{j=1}^{k} d_j$), the subspaces are all orthogonal to each other, {\em i.e.} $(\Z_i^*)^{\top} \Z_{j}^* = \bm 0$ for $i \not= j$.

\item {\em Maximally Diverse Representation}: 
As long as the coding precision is adequately high, i.e., $\epsilon ^4 < \min_{j}\left\{ \frac{m_j}{m}\frac{d^2}{d_j^2}\right\}$, each subspace achieves its maximal dimension, i.e. $\rank{(\Z^{*}_{j})}= d_j$. In addition, the largest $d_j - 1$ singular values of $\Z^{*}_{j}$ are equal. 
\label{thm:MCR2-properties}
\end{itemize}

\end{theorem}

In other words, in the case of subspaces, the MCR$^2$ principle promotes embedding of data into multiple independent subspaces, with features distributed {\em isotropically}  in each subspace (except for possibly one dimension). In addition, among all such discriminative representations, it prefers the one with the highest dimensions in the ambient space. This is substantially different from the objective of information bottleneck~\eqref{eqn:information-bottleneck}.


\textbf{Comparison to the geometric OLE loss.} To encourage the learned features to be uncorrelated between classes, the work of \cite{lezama2018ole} has proposed to maximize the difference between the nuclear norm of the whole $\Z$ and its subsets $\Z_j$, called the {\em orthogonal low-rank embedding} (OLE) loss:
$
    \max_{\theta}\,
    \mbox{OLE}(\Z(\theta), \bm \Pi) \doteq  \|\Z(\theta)\|_* - \sum_{j=1}^k \|\Z_j(\theta)\|_*,
$
added as a regularizer to the cross-entropy loss \eqref{eqn:cross-entropy}. The nuclear norm $\|\cdot \|_*$ is a {\em nonsmooth convex}\footnote{Nonsmoothness poses additional difficulties in using this loss to learn features via gradient descent.} surrogate for low-rankness, whereas $\log\det(\cdot)$ is {\em smooth  concave} instead. Unlike the rate reduction $\Delta R$, OLE is always {\em negative} and achieves the maximal value $0$ when the subspaces are orthogonal, regardless of their dimensions. So in contrast to $\Delta R$, this loss serves as a geometric heuristic and does not promote diverse representations.  In fact, OLE typically promotes learning one-dim representations per class, whereas MCR$^2$ encourages learning subspaces with maximal dimensions (Figure~7 of \cite{lezama2018ole} versus our Figure~\ref{fig:pca-plot}).

\textbf{Relation to contrastive learning.}
If samples are {\em evenly} drawn from $k$ classes, a randomly chosen pair $(\x_i, \x_j)$ is of high probability belonging to difference classes if $k$ is large.\footnote{For example, when $k \ge 100$, a random pair is of probability 99\% belonging to different classes.} We may view the learned features of two samples together with their their augmentations $\Z_i$ and $\Z_j$ as two classes. Then the rate reduction $\Delta R_{ij} = R(\Z_i\cup \Z_j, \epsilon) - \frac{1}{2}(R(\Z_i, \epsilon) + R(\Z_j, \epsilon))$ gives a ``distance'' measure for how far the two sample sets are. We may try to further ``expand'' pairs that likely belong to different classes. From Theorem \ref{thm:MCR2-properties},  the (averaged) rate reduction $\Delta R_{ij}$ is maximized  when features from different samples are uncorrelated $\Z_i^\top \Z_j = \bm 0$  (see Figure~\ref{fig:sphere-packing}) and features $\Z_i$ from the same sample are highly correlated. Hence, when applied to sample pairs, MCR$^2$ naturally conducts the so-called {\em contrastive learning} \cite{hadsell2006dimensionality,oord2018representation,he2019momentum}. But  MCR$^2$ is {\em not} limited to expand (or compress) pairs of samples and can uniformly conduct ``contrastive learning'' for a subset with {\em any number} of samples as long as we know they likely belong to different (or the same) classes, say by randomly sampling subsets from a large number of classes or with a good clustering method.
{"config": "arxiv", "file": "2006.08558/TexFiles/sec2_formulation.tex"}