While continuous diffusion models excel in modeling continuous distributions, their application to categorical data has been less effective. Recent work has shown that ratio-matching through *score-entropy* within a continuous-time discrete Markov chain (CTMC) framework serves as a competitive alternative to autoregressive models in language modeling. To enhance this framework, we first introduce three new theorems concerning the KL divergence between the data and learned distribution. Our results serve as the discrete counterpart to those established for continuous diffusion models and allow us to derive an improved upper bound of the perplexity. Second, we empirically show that ratio-matching performed by minimizing the *denoising cross-entropy* between the clean and corrupted data enables models to outperform those utilizing score-entropy with up to 10\% lower perplexity/generative-perplexity, and 15\% faster training steps. To further support our findings, we introduce and evaluate a novel CTMC transition-rate matrix that allows prediction refinement, and derive the analytic expression for its matrix exponential which facilitates the computation of conditional ratios thus enabling efficient training and generation.

Deep metric learning (DML) aims to minimize empirical expected loss of the pairwise intra-/inter- class proximity violations in the embedding space. We relate DML to feasibility problem of finite chance constraints. We show that minimizer of proxy-based DML satisfies certain chance constraints, and that the worst case generalization performance of the proxy-based methods can be characterized by the radius of the smallest ball around a class proxy to cover the entire domain of the corresponding class samples, suggesting multiple proxies per class helps performance. To provide a scalable algorithm as well as exploiting more proxies, we consider the chance constraints implied by the minimizers of proxy-based DML instances and reformulate DML as finding a feasible point in intersection of such constraints, resulting in a problem to be approximately solved by iterative projections. Simply put, we repeatedly train a regularized proxy-based loss and re-initialize the proxies with the embeddings of the deliberately selected new samples. We applied our method with 4 well-accepted DML losses and show the effectiveness with extensive evaluations on 4 popular DML benchmarks. Code is available at: https://github.com/yetigurbuz/ccp-dml

A common architectural choice for deep metric learning is a convolutional neural network followed by global average pooling (GAP). Albeit simple, GAP is a highly effective way to aggregate information. One possible explanation for the effectiveness of GAP is considering each feature vector as representing a different semantic entity and GAP as a convex combination of them. Following this perspective, we generalize GAP and propose a learnable generalized sum pooling method (GSP). GSP improves GAP with two distinct abilities: i) the ability to choose a subset of semantic entities, effectively learning to ignore nuisance information, and ii) learning the weights corresponding to the importance of each entity. Formally, we propose an entropy-smoothed optimal transport problem and show that it is a strict generalization of GAP, i.e., a specific realization of the problem gives back GAP. We show that this optimization problem enjoys analytical gradients enabling us to use it as a direct learnable replacement for GAP. We further propose a zero-shot loss to ease the learning of GSP. We show the effectiveness of our method with extensive evaluations on 4 popular metric learning benchmarks. Code is available at: GSP-DML Framework

Global average pooling (GAP) is a popular component in deep metric learning (DML) for aggregating features. Its effectiveness is often attributed to treating each feature vector as a distinct semantic entity and GAP as a combination of them. Albeit substantiated, such an explanation’s algorithmic implications to learn generalizable entities to represent unseen classes, a crucial DML goal, remain unclear. To address this, we formulate GAP as a convex combination of learnable prototypes. We then show that the prototype learning can be expressed as a recursive process fitting a linear predictor to a batch of samples. Building on that perspective, we consider two batches of disjoint classes at each iteration and regularize the learning by expressing the samples of a batch with the prototypes that are fitted to the other batch. We validate our approach on 4 popular DML benchmarks.

We propose an end-to-end learning approach to address deinterleaving of patterns in time series, in particular, radar signals. We link signal clustering problem to min-cost flow as an equivalent problem once the proper costs exist. We formulate a bi-level optimization problem involving min-cost flow as a sub-problem to learn such costs from the supervised training data. We then approximate the lower level optimization problem by self-attention based neural networks and provide a trainable framework that clusters the patterns in the input as the distinct flows. We evaluate our method with extensive experiments on a large dataset with several challenging scenarios to show the efficiency.

Minimizers of the typical distance metric learning loss functions can be considered as “feasible points” satisfying a set of constraints imposed by the training data. We reformulate distance metric learning problem as finding a feasible point of a constraint set where the embedding vectors of the training data satisfy desired intra-class and inter-class proximity. The feasible set induced by the constraint set is expressed as the intersection of the relaxed feasible sets which enforce the proximity constraints only for particular samples (a sample from each class) of the training data. Then, the feasible point problem is to be approximately solved by performing alternating projections onto those feasible sets. Such an approach introduces a regularization term and results in minimizing a typical loss function with a systematic batch set construction where these batches are constrained to contain the same sample from each class for a certain number of iterations. The proposed technique is applied with the well-accepted losses and evaluated on three popular benchmark datasets for image retrieval and clustering. Outperforming state-of-the-art, the proposed approach consistently improves the performance of the integrated loss functions with no additional computational cost.

An end-to-end trainable convolutional neural network (CNN) framework which mimics bag of visual words (BoVW) is proposed for image classification. To this end, a new paradigm for histogram-like image representation is introduced and optimal transport (OT) distance is utilized for the similarity assessment. Any patch of an image is considered as a unique visual word and the image is represented as the uniform histogram of the visual words with the histogram bins associated to embedding vectors according to the semantic meanings of the corresponding visual words. Thus, in the CNN framework, the output of the last convolutional block is considered as the global representation of the image and the embeddings are inherently learned within the classification framework. With the proposed formulation, undesired quantization for the BoVW representation is no more required; moreover, the learned CNN features are naturally interpretable. The experiments on CIFAR-10, CIFAR-100 and SVHN datasets show that the replacement of the global pooling and fully connected layers with the proposed representation together with OT distance improves the baseline CNN framework.

Long-term multi-target tracking via tracklet merging in wide area surveillance has crucial importance to improve tracker performances and operational requirements. Min-cost network flow formulation for multi-target tracking is adopted for the tracklet merging problem. In order to improve the continuity of the computed flows by the min-cost network flow framework, a novel tracklet association cost is proposed to be utilized in this network. The proposed cost is based on connecting two tracklets by considering the traffic flow which is estimated from the precomputed tracklets. Such an approach enforces spatial consistencies between tracks by imposing these relations into the association cost. Hence, without violating the min-cost network flow formulation, a constraint to enforce spatial consistency can be implicitly obtained. The proposed cost function can be further exploited to interpolate gaps between the merged tracklets for postprocessing. The experimental results show that proposed association cost improves baseline framework that uses costs considering only two tracklets at a time, as well as some other tracklet merge algorithms from the literature.

Wide Area Surveillance (WAS) systems are capable of providing continuous surveillance of critical areas as wide as city center (approximately 20 km square), mostly as a gray-level video. Utilization of road information for WAS systems increases moving vehicle tracking performance, while reducing the false alarm rates that might occur due to tall buildings, shadows or terrain. Two different novel approaches for automatic road detection from gray values images are presented in this paper. In the first approach, a probabilistic model for the road pixels of a gray-scale WAS image is obtained by utilizing parallel line detection and tubularity estimation. In the second approach, these road probabilities are converted into a graph representation for local areas. These graphs are solved by using graph cut formulation which exploits min-cut, max-flow algorithm. As a result of this solution, the road mask is extracted by applying a hierarchical model that results with a transition from local to global representation. Although the methods in literature mostly utilize multi-spectral images that result wih a smaller resolution yielding surveillance of a limited region, the proposed method uses gray-scale images which enable surveillance of much wider areas. The proposed method was tested some high resolution WAS images and resulted with promising results.

Recursive edge-aware filters have been proved to be one of the most efficient approaches for cost aggregation in stereo matching. However, disparity search space dependency, as a result of full search, is the bottle-neck of these local techniques that prevent further reduction in computation. In this paper, the cost aggregation and correspondence search problems are re-formulated to enable adaptive search for each pixel during recursive operations that provides significant reduction in computational complexity. In that manner, fixed number of disparity candidates are tested for each pixel, regardless of the search space, that are aggregated through sparse recursive filtering. Hierarchical approach is exploited to pick disparity candidates for each pixel. The experimental results show that the proposed approach has linear complexity with the image size and in practice it speeds up the recursive approaches almost four times with a marginal decrease in matching accuracy. Compared to the state-of-the-art techniques, hierarchical sparse recursive aggregation is possibly the fastest approach with a competitive accuracy based on Middlebury benchmarking.