Exact computation of shortest paths in weighted graphs has been traditionally studied in one of two settings. First, one can assume that the edge weights are real numbers and all the performed operations on reals (typically comparisons and additions) take constant time. Classical Dijkstra's and Bellman-Ford algorithms have been described in this setting. More efficient exact shortest paths algorithms have been obtained for integer-weighted graphs. Integrality assumption not only enables faster algorithms but also allows implementing the aforementioned algorithms in a much more realistic word RAM model where only arithmetic operations on $O(\log{n})$-bit integers are performed in constant time. On the word RAM one can as efficiently exactly encode even \emph{rational-weighted} instances with $O(\log{n})$-bit numerators and denominators. However, the known exact real-weighted shortest paths algorithms, run on such a rational input, can easily encounter intermediate values of $\Theta(n)$ bits if represented exactly. This leads to a factor-$\Omega(n)$ slowdown on the word RAM. At the same time, the scaling algorithms suited for integer weights do not produce exact solutions for rational inputs without dramatically increasing their accuracy. In this paper, we design randomized exact single-source shortest paths algorithms for rational-weighted graphs on the word RAM. Most importantly, in the non-negative case, we obtain a near-linear time algorithm matching Dijkstra's algorithm running time up to polylogarithmic factors. In presence of negative weights, we give an $\tilde{O}(n^{2.5})$-time algorithm breaking through the best known strongly polynomial bound attained by Bellman-Ford for sufficiently dense graphs.
相關內容
Gaussian processes (GPs) are the most common formalism for defining probability distributions over spaces of functions. While applications of GPs are myriad, a comprehensive understanding of GP sample paths, i.e. the function spaces over which they define a probability measure on, is lacking. In practice, GPs are not constructed through a probability measure, but instead through a mean function and a covariance kernel. In this paper we provide necessary and sufficient conditions on the covariance kernel for the sample paths of the corresponding GP to attain a given regularity. We use the framework of H\"older regularity as it grants us particularly straightforward conditions, which simplify further in the cases of stationary and isotropic GPs. We then demonstrate that our results allow for novel and unusually tight characterisations of the sample path regularities of the GPs commonly used in machine learning applications, such as the Mat\'ern GPs.
The issue of generative pretraining for vision models has persisted as a long-standing conundrum. At present, the text-to-image (T2I) diffusion model demonstrates remarkable proficiency in generating high-definition images matching textual inputs, a feat made possible through its pre-training on large-scale image-text pairs. This leads to a natural inquiry: can diffusion models be utilized to tackle visual perception tasks? In this paper, we propose a simple yet effective scheme to harness a diffusion model for visual perception tasks. Our key insight is to introduce learnable embeddings (meta prompts) to the pre-trained diffusion models to extract proper features for perception. The effect of meta prompts are two-fold. First, as a direct replacement of the text embeddings in the T2I models, it can activate task-relevant features during feature extraction. Second, it will be used to re-arrange the extracted features to ensures that the model focuses on the most pertinent features for the task on hand. Additionally, we design a recurrent refinement training strategy that fully leverages the property of diffusion models, thereby yielding stronger visual features. Extensive experiments across various benchmarks validate the effectiveness of our approach. Our approach achieves new performance records in depth estimation tasks on NYU depth V2 and KITTI, and in semantic segmentation task on CityScapes. Concurrently, the proposed method attains results comparable to the current state-of-the-art in semantic segmentation on ADE20K and pose estimation on COCO datasets, further exemplifying its robustness and versatility.
Classical mathematical statistics deals with models that are parametrized by a Euclidean, i.e. finite dimensional, parameter. Quite often such models have been and still are chosen in practical situations for their mathematical simplicity and tractability. However, these models are typically inappropriate since the implied distributional assumptions cannot be supported by hard evidence. It is natural then to relax these assumptions. This leads to the class of semiparametric models. These models have been studied in a local asymptotic setting, in which the Convolution Theorem yields bounds on the performance of regular estimators. Alternatively, local asymptotics can be based on the Local Asymptotic Minimax Theorem and on the Local Asymptotic Spread Theorem, both valid for any sequence of estimators. This Local Asymptotic Spread Theorem is a straightforward consequence of a Finite Sample Spread Inequality, which has some intrinsic value for estimation theory in general. We will discuss both the Finite Sample and Local Asymptotic Spread Theorem, as well as the Convolution Theorem.
A Gr\"obner basis computation for the Weyl algebra with respect to a tropical term order and by using a homogenization-dehomogenization technique is sufficiently sluggish. A significant number of reductions to zero occur. To improve the computation, a tropical F5 algorithm is developed for this context. As a member of the family of signature-based algorithms, this algorithm keeps track of where Weyl algebra elements come from to anticipate reductions to zero. The total order for ordering module monomials or signatures in this paper is designed as close as possible to the definition of the tropical term order. As in Vaccon et al. (2021), this total order is not compatible with the tropical term order.
Generative models can serve as surrogates for some real data sources by creating synthetic training datasets, but in doing so they may transfer biases to downstream tasks. We focus on protecting quality and diversity when generating synthetic training datasets. We propose quality-diversity generative sampling (QDGS), a framework for sampling data uniformly across a user-defined measure space, despite the data coming from a biased generator. QDGS is a model-agnostic framework that uses prompt guidance to optimize a quality objective across measures of diversity for synthetically generated data, without fine-tuning the generative model. Using balanced synthetic datasets generated by QDGS, we first debias classifiers trained on color-biased shape datasets as a proof-of-concept. By applying QDGS to facial data synthesis, we prompt for desired semantic concepts, such as skin tone and age, to create an intersectional dataset with a combined blend of visual features. Leveraging this balanced data for training classifiers improves fairness while maintaining accuracy on facial recognition benchmarks. Code available at: //github.com/Cylumn/qd-generative-sampling
Finding the exact spanning ratio of a Delaunay graph has been one of the longstanding open problems in Computational Geometry. Currently there are only four convex shapes for which the exact spanning ratio of their Delaunay graph is known: the equilateral triangle, the square, the regular hexagon and the rectangle. In this paper, we show the exact spanning ratio of the parallelogram Delaunay graph, making the parallelogram the fifth convex shape for which an exact bound is known. The worst-case spanning ratio is exactly $$\frac{\sqrt{2}\sqrt{1+A^2+2A\cos(\theta_0)+(A+\cos(\theta_0))\sqrt{1+A^2+2A\cos(\theta_0)}}}{\sin(\theta_0)} .$$ where $A$ is the aspect ratio and $\theta_0$ is the non-obtuse angle of the parallelogram. Moreover, we show how to construct a parallelogram Delaunay graph whose spanning ratio matches the above mentioned spanning ratio.
Visual recognition is currently one of the most important and active research areas in computer vision, pattern recognition, and even the general field of artificial intelligence. It has great fundamental importance and strong industrial needs. Deep neural networks (DNNs) have largely boosted their performances on many concrete tasks, with the help of large amounts of training data and new powerful computation resources. Though recognition accuracy is usually the first concern for new progresses, efficiency is actually rather important and sometimes critical for both academic research and industrial applications. Moreover, insightful views on the opportunities and challenges of efficiency are also highly required for the entire community. While general surveys on the efficiency issue of DNNs have been done from various perspectives, as far as we are aware, scarcely any of them focused on visual recognition systematically, and thus it is unclear which progresses are applicable to it and what else should be concerned. In this paper, we present the review of the recent advances with our suggestions on the new possible directions towards improving the efficiency of DNN-related visual recognition approaches. We investigate not only from the model but also the data point of view (which is not the case in existing surveys), and focus on three most studied data types (images, videos and points). This paper attempts to provide a systematic summary via a comprehensive survey which can serve as a valuable reference and inspire both researchers and practitioners who work on visual recognition problems.
Spectral clustering (SC) is a popular clustering technique to find strongly connected communities on a graph. SC can be used in Graph Neural Networks (GNNs) to implement pooling operations that aggregate nodes belonging to the same cluster. However, the eigendecomposition of the Laplacian is expensive and, since clustering results are graph-specific, pooling methods based on SC must perform a new optimization for each new sample. In this paper, we propose a graph clustering approach that addresses these limitations of SC. We formulate a continuous relaxation of the normalized minCUT problem and train a GNN to compute cluster assignments that minimize this objective. Our GNN-based implementation is differentiable, does not require to compute the spectral decomposition, and learns a clustering function that can be quickly evaluated on out-of-sample graphs. From the proposed clustering method, we design a graph pooling operator that overcomes some important limitations of state-of-the-art graph pooling techniques and achieves the best performance in several supervised and unsupervised tasks.
We propose a novel method for automatic reasoning on knowledge graphs based on debate dynamics. The main idea is to frame the task of triple classification as a debate game between two reinforcement learning agents which extract arguments -- paths in the knowledge graph -- with the goal to promote the fact being true (thesis) or the fact being false (antithesis), respectively. Based on these arguments, a binary classifier, called the judge, decides whether the fact is true or false. The two agents can be considered as sparse, adversarial feature generators that present interpretable evidence for either the thesis or the antithesis. In contrast to other black-box methods, the arguments allow users to get an understanding of the decision of the judge. Since the focus of this work is to create an explainable method that maintains a competitive predictive accuracy, we benchmark our method on the triple classification and link prediction task. Thereby, we find that our method outperforms several baselines on the benchmark datasets FB15k-237, WN18RR, and Hetionet. We also conduct a survey and find that the extracted arguments are informative for users.
Object detection typically assumes that training and test data are drawn from an identical distribution, which, however, does not always hold in practice. Such a distribution mismatch will lead to a significant performance drop. In this work, we aim to improve the cross-domain robustness of object detection. We tackle the domain shift on two levels: 1) the image-level shift, such as image style, illumination, etc, and 2) the instance-level shift, such as object appearance, size, etc. We build our approach based on the recent state-of-the-art Faster R-CNN model, and design two domain adaptation components, on image level and instance level, to reduce the domain discrepancy. The two domain adaptation components are based on H-divergence theory, and are implemented by learning a domain classifier in adversarial training manner. The domain classifiers on different levels are further reinforced with a consistency regularization to learn a domain-invariant region proposal network (RPN) in the Faster R-CNN model. We evaluate our newly proposed approach using multiple datasets including Cityscapes, KITTI, SIM10K, etc. The results demonstrate the effectiveness of our proposed approach for robust object detection in various domain shift scenarios.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191