## 3 Information-Theoretic Large-Scale Semi-Supervised Metric Learning via Proxies
### Learning From Proxy Vectors  
SEPAPH approach relies on the pairwise distance to construct the probability model, which has the following two drawbacks: (1) the time complexity of SERAPH has a quadratic dependence on the number of unlabeled data, which means it cannot scale to large-scale datasets; (2) SERAPH is a global metric learning method and SERAPH is sensitivity to the outlier in the dataset. To solve these problems, suppose that there are multiple proxy vectors anchoring around the whole instance space, and these vectors can be expressed as a set: \(\mathcal{Z}=\{\mathbf{z}_{1},\mathbf{z}_{2},\cdots,\mathbf{z}_{m}\}\), where \(m\) is the number of vectors. The function of the proxy vector can be considered as the mean center of each class, or anchor that aggregates the local similarity information of some local instances [30]. By aligning the relevant instances to their corresponding proxy vectors, the problem of the outlier instances inside the dataset as well as the high time complexity can be efficiently settled. Similar to proxy-NCA [31], for any instance \(\mathbf{x}\), its corresponding proxy vector can be estimated by:  
\[p(\mathbf{x})=\operatorname*{arg\,min}_{\mathbf{p}\in\mathcal{Z}}d_{\mathbf{M}}^{2}( \mathbf{x},\mathbf{z}), \tag{5}\]  
where \(d_{\mathbf{M}}^{2}(\mathbf{x},\mathbf{z})\) is the Mahalanobis distance between \(\mathbf{x}\) and \(\mathbf{z}\). Equation (5) means that the proxy vector of an instance is the proxy vector that is closest to the instance under the metric \(\mathbf{M}\).  
Instead of directly constructing the probabilistic model from the pairwise Mahalanobis distance, we utilize the pairwise distances among the instance and all the proxy vectors to form the NCA-style [32] probabilistic model. More specifically, for any instance, \(\mathbf{x}_{i}\), its probability of randomly choosing a proxy vector can be estimated via:  
\[q_{ij}=\frac{\exp\big{(}-d_{\mathbf{M}}^{2}\big{(}\mathbf{x}_{i},\mathbf{z}_{j}\big{)} \big{)}}{\sum_{j=1}^{m}\exp\big{(}-d_{\mathbf{M}}^{2}\big{(}\mathbf{x}_{i},\mathbf{z}_ {j}\big{)}\big{)}}. \tag{6}\]  
\(q_{ij}\) can reflect the closeness between \(\mathbf{x}_{i}\) and \(\mathbf{z}_{j}\); the closer \(\mathbf{x}_{i}\) to \(\mathbf{z}_{j}\), the bigger the value. All the \(q_{ij}\) (\(j=1,2,\cdots,m\)) form a valid discrete probability distribution:  
\[\mathbf{q}_{i}=(q_{i1},q_{i2},\cdots,q_{im})^{T}. \tag{7}\]  
Suppose that the weakly-supervised information is provided in the form of pairwise constraint forms. For any two instances \(\big{(}\mathbf{x}_{i},\mathbf{x}_{j}\big{)}\) from \(\mathcal{S}\), we aim to minimize the distance between \(\mathbf{x}_{i}\) and the proxy vector of \(\mathbf{x}_{j}\), and, in the meanwhile, keep a large distance from the other proxy vectors. Such an idea can be expressed as:  
\[\max_{\mathbf{M}\in\mathcal{S}_{+}^{l}}\frac{1}{|\mathcal{S}|}\sum_{\big{(}\bm {x}_{i},\mathbf{x}_{j}\big{)}\in\mathcal{S}}\log\Bigg{(}\frac{\exp\big{(}-d_{ \mathbf{M}}^{2}\big{(}\mathbf{x}_{i},\mathbf{p}\big{(}\mathbf{x}_{j}\big{)}\big{)}\big{)}}{ \sum_{j=1}^{m}\exp\big{(}-d_{\mathbf{M}}^{2}\big{(}\mathbf{x}_{i},\mathbf{z}_{j}\big{)} \big{)}}\Bigg{)}. \tag{8}\]where \(|\mathcal{S}|\) denotes the cardinality of \(\mathcal{S}\). \(\mathcal{S}_{+}^{d}\) is the set of all the \(d\times d\) PSD (Positive Semi-Definite) matrices. Maximizing Equation (8) will push \(\mathbf{x}_{i}\) toward \(p\big{(}\mathbf{x}_{j}\big{)}\). In contrast to the SERAPH algorithm, ISMLP converts the pairwise distance to that of the instance and the corresponding proxy vector. The proxy vector can be viewed as aggregating the local similarity information of local instances. Therefore, the proposed method can exhibit more robust behavior than SERAPH.