# Optimizing Contrastive Learning with Semi-Online Triplet Mining
## 3 Method
In our dataset, examples (shoes) that have the same identity (coming from the same pair) always go together. Therefore, reordering the dataset means changing the order of the identities (pairs). The method described below operates on a set of points in \(n\)-dimensional space and returns an ordered list of these points. The structure of the dataset is more complicated, as it comprises photos grouped into identities. As examples within an identity are (by definition) similar, we simply select the first example from every identity to be its representative. Then, after the processing of the photographs using an embedding network, the photographs become points, and the proposed point-reordering method is applied, so that the identity order is established. As a final step, the initial dataset is reordered to match the newly calculated order. Considering that the embeddings are points located on a multi-dimensional unit sphere, ordering them is a considerable task. There is no obvious way to do it. Even the principle of \"similar identities should go close to each other\" can be formalized in countless ways. The tasks has much in common with the traveling salesman problem (TSP) [22]--although differences can be observed. First, in the TSP, the path forms a loop, which is not required in our scenario. Second, the TSP would penalize jumping between very remote clusters in suboptimal order; in our problem, this is unimportant. When presented with three groups of shoes--chucks, wellingtons, and derbys--the order of the groups is irrelevant as long as similar chucks, for example, are close to each other. The TSP, on the other hand, would focus on optimizing the path between such remote clusters, as the distance between them is large and would affect the length of the total path markedly. This observation hints that local similarity should be given more attention than global similarity in the ordering problem. This second property, \"local proximity first\", is the reason why manifold learning techniques like t-SNE [23] and UMAP [24] were dropped: finely controlling this property within them would be challenging. To fulfill these requirements, we have devised a two-step approach. The first step involves clustering the embeddings in a way that enforces \"local proximity first.\" As we have no prior knowledge of the expected number of clusters, the clustering method should not need specify that. Considering the above, we opted to use hierarchical agglomerative clustering (HAC) [25]. \"Hierarchical\" means that this method creates clusters from other clusters, constructing a tree of clusters in the process. \"Agglomerative\" indicates that a bottom-up approach is used in contrast to a divisive one. The algorithm is simple. Initially, each embedding is put in a single element cluster--a leaf node in the tree. From that point, the two most similar clusters are selected and merged. That process continues until there is a single cluster, which can be treated as the root of the tree of clusters. In the context of hierarchical clustering, such similarity is often calledlinkage. A wide variety of linkages are proposed in the literature. Single linkage involves two clusters that are as similar as the minimum length between their two points. Complete or maximum linkage is based on the maximum distances between all observations of the two sets. Average linkage uses the average distance between points in two clusters. Ward linkage minimizes the variance of the clusters being merged. We tested all of them to discover that despite linkages behaving differently on intentionally created corner-cased benchmarks, all types performed similarly on our datasets. The second step involves ordering the embeddings from the leaves of the tree. As the most similar clusters were connected first, they are connected lower (closer to the leaves) in the tree. Figure 3 presents an example of this process. The closer to the root the two branches fork, the more different embeddings they contain.