OpenRaiser/Intern-Atlas huggingface dataset:
D2S: Representing sparse descriptors and 3D coordinates for camera relocalization
Venue: arXiv cs.CV 2024
Year: 2024

State-of-the-art visual localization methods mostly rely on complex procedures to match local descriptors and 3D point clouds. However, these procedures can incur significant costs in terms of inference, storage, and updates over time. In this study, we propose a direct learning-based approach that utilizes a simple network named D2S to represent complex local descriptors and their scene coordinates. Our method is characterized by its simplicity and cost-effectiveness. It solely leverages a single RGB image for localization during the testing phase and only requires a lightweight model to encode a complex sparse scene. The proposed D2S employs a combination of a simple loss function and graph attention to selectively focus on robust descriptors while disregarding areas such as clouds, trees, and several dynamic objects. This selective attention enables D2S to effectively perform a binary-semantic classification for sparse descriptors. Additionally, we propose a simple outdoor dataset to evaluate the capabilities of visual localization methods in scene-specific generalization and self-updating from unlabeled observations. Our approach outperforms the previous regression-based methods in both indoor and outdoor environments. It demonstrates the ability to generalize beyond training data, including scenarios involving transitions from day to night and adapting to domain shifts. The source code, trained models, dataset, and demo videos are available at the following link: https://thpjp.github.io/d2s.
Point Clouds Are Specialized Images: A Knowledge Transfer Approach for 3D Understanding
Venue: arXiv cs.CV 2024
Year: 2024

Self-supervised representation learning (SSRL) has gained increasing attention in point cloud understanding, in addressing the challenges posed by 3D data scarcity and high annotation costs. This paper presents PCExpert, a novel SSRL approach that reinterprets point clouds as "specialized images". This conceptual shift allows PCExpert to leverage knowledge derived from large-scale image modality in a more direct and deeper manner, via extensively sharing the parameters with a pre-trained image encoder in a multi-way Transformer architecture. The parameter sharing strategy, combined with a novel pretext task for pre-training, i.e., transformation estimation, empowers PCExpert to outperform the state of the arts in a variety of tasks, with a remarkable reduction in the number of trainable parameters. Notably, PCExpert's performance under LINEAR fine-tuning (e.g., yielding a 90.02% overall accuracy on ScanObjectNN) has already approached the results obtained with FULL model fine-tuning (92.66%), demonstrating its effective and robust representation capability.
Bike Assisted Evacuation on a Line of Robots with Communication Faults
Venue: arXiv cs.DC 2024
Year: 2024

Two autonomous mobile robots and a non-autonomous one, also called bike, are placed at the origin of an infinite line. The autonomous robots can travel with maximum speed $1$. When a robot rides the bike its speed increases to $v>1$, however only exactly one robot at a time can ride the bike and the bike is non-autonomous in that it cannot move on its own. An Exit is placed on the line at an unknown location and at distance $d$ from the origin. The robots have limited communication behavior; one robot is a sender (denoted by S) in that it can send information wirelessly at any distance and receive messages only in F2F (Face-to-Face), while the other robot is a receiver (denoted by R) in that it can receive information wirelessly but can send information only F2F. The bike has no communication capabilities of its own. We refer to the resulting communication model of the ensemble of the two autonomous robots and the bike as S/R. Our general goal is to understand the impact of the non-autonomous robot in assisting the evacuation of the two autonomous faulty robots. Our main contribution is to provide a new evacuation algorithm that enables both robots to evacuate from the unknown Exit in the S/R model. We also analyze the resulting evacuation time as a function of the bike's speed $v$ and give upper and lower bounds on the competitive ratio of the resulting algorithm for the entire range of possible values of $v$.
Human-Like Implicit Intention Expression for Autonomous Driving Motion Planning: A Method Based on Learning Human Intention Priors
Venue: arXiv cs.RO 2024
Year: 2024

One of the key factors determining whether autonomous vehicles (AVs) can be seamlessly integrated into existing traffic systems is their ability to interact smoothly and efficiently with human drivers and communicate their intentions. While many studies have focused on enhancing AVs' human-like interaction and communication capabilities at the behavioral decision-making level, a significant gap remains between the actual motion trajectories of AVs and the psychological expectations of human drivers. This discrepancy can seriously affect the safety and efficiency of AV-HV (Autonomous Vehicle-Human Vehicle) interactions. To address these challenges, we propose a motion planning method for AVs that incorporates implicit intention expression. First, we construct a trajectory space constraint based on human implicit intention priors, compressing and pruning the trajectory space to generate candidate motion trajectories that consider intention expression. We then apply maximum entropy inverse reinforcement learning to learn and estimate human trajectory preferences, constructing a reward function that represents the cognitive characteristics of drivers. Finally, using a Boltzmann distribution, we establish a probabilistic distribution of candidate trajectories based on the reward obtained, selecting human-like trajectory actions. We validated our approach on a real trajectory dataset and compared it with several baseline methods. The results demonstrate that our method excels in human-likeness, intention expression capability, and computational efficiency.
Fully $1\times1$ Convolutional Network for Lightweight Image Super-Resolution
Venue: arXiv cs.CV 2024
Year: 2024

Deep models have achieved significant process on single image super-resolution (SISR) tasks, in particular large models with large kernel ($3\times3$ or more). However, the heavy computational footprint of such models prevents their deployment in real-time, resource-constrained environments. Conversely, $1\times1$ convolutions bring substantial computational efficiency, but struggle with aggregating local spatial representations, an essential capability to SISR models. In response to this dichotomy, we propose to harmonize the merits of both $3\times3$ and $1\times1$ kernels, and exploit a great potential for lightweight SISR tasks. Specifically, we propose a simple yet effective fully $1\times1$ convolutional network, named Shift-Conv-based Network (SCNet). By incorporating a parameter-free spatial-shift operation, it equips the fully $1\times1$ convolutional network with powerful representation capability while impressive computational efficiency. Extensive experiments demonstrate that SCNets, despite its fully $1\times1$ convolutional structure, consistently matches or even surpasses the performance of existing lightweight SR models that employ regular convolutions. The code and pre-trained models can be found at https://github.com/Aitical/SCNet.
Adaptive learning of density ratios in RKHS
Venue: arXiv cs.LG 2024
Year: 2024

Estimating the ratio of two probability densities from finitely many observations of the densities is a central problem in machine learning and statistics with applications in two-sample testing, divergence estimation, generative modeling, covariate shift adaptation, conditional density estimation, and novelty detection. In this work, we analyze a large class of density ratio estimation methods that minimize a regularized Bregman divergence between the true density ratio and a model in a reproducing kernel Hilbert space (RKHS). We derive new finite-sample error bounds, and we propose a Lepskii type parameter choice principle that minimizes the bounds without knowledge of the regularity of the density ratio. In the special case of quadratic loss, our method adaptively achieves a minimax optimal error rate. A numerical illustration is provided.
You Shall Pass: Dealing with the Zero-Gradient Problem in Predict and Optimize for Convex Optimization
Venue: arXiv cs.LG 2024
Year: 2024

Predict and optimize is an increasingly popular decision-making paradigm that employs machine learning to predict unknown parameters of optimization problems. Instead of minimizing the prediction error of the parameters, it trains predictive models using task performance as a loss function. The key challenge to train such models is the computation of the Jacobian of the solution of the optimization problem with respect to its parameters. For linear problems, this Jacobian is known to be zero or undefined; hence, approximations are usually employed. For non-linear convex problems, however, it is common to use the exact Jacobian. This paper demonstrates that the zero-gradient problem appears in the non-linear case as well -- the Jacobian can have a sizeable null space, thereby causing the training process to get stuck in suboptimal points. Through formal proofs, this paper shows that smoothing the feasible set resolves this problem. Combining this insight with known techniques from the literature, such as quadratic programming approximation and projection distance regularization, a novel method to approximate the Jacobian is derived. In simulation experiments, the proposed method increases the performance in the non-linear case and at least matches the existing state-of-the-art methods for linear problems.
A multiscale and multicriteria Generative Adversarial Network to synthesize 1-dimensional turbulent fields
Venue: arXiv cs.LG 2024
Year: 2024

This article introduces a new Neural Network stochastic model to generate a 1-dimensional stochastic field with turbulent velocity statistics. Both the model architecture and training procedure ground on the Kolmogorov and Obukhov statistical theories of fully developed turbulence, so guaranteeing descriptions of 1) energy distribution, 2) energy cascade and 3) intermittency across scales in agreement with experimental observations. The model is a Generative Adversarial Network with multiple multiscale optimization criteria. First, we use three physics-based criteria: the variance, skewness and flatness of the increments of the generated field that retrieve respectively the turbulent energy distribution, energy cascade and intermittency across scales. Second, the Generative Adversarial Network criterion, based on reproducing statistical distributions, is used on segments of different length of the generated field. Furthermore, to mimic multiscale decompositions frequently used in turbulence's studies, the model architecture is fully convolutional with kernel sizes varying along the multiple layers of the model. To train our model we use turbulent velocity signals from grid turbulence at Modane wind tunnel.
CDUL: CLIP-Driven Unsupervised Learning for Multi-Label Image Classification
Venue: arXiv cs.CV 2024
Year: 2024

This paper presents a CLIP-based unsupervised learning method for annotation-free multi-label image classification, including three stages: initialization, training, and inference. At the initialization stage, we take full advantage of the powerful CLIP model and propose a novel approach to extend CLIP for multi-label predictions based on global-local image-text similarity aggregation. To be more specific, we split each image into snippets and leverage CLIP to generate the similarity vector for the whole image (global) as well as each snippet (local). Then a similarity aggregator is introduced to leverage the global and local similarity vectors. Using the aggregated similarity scores as the initial pseudo labels at the training stage, we propose an optimization framework to train the parameters of the classification network and refine pseudo labels for unobserved labels. During inference, only the classification network is used to predict the labels of the input image. Extensive experiments show that our method outperforms state-of-the-art unsupervised methods on MS-COCO, PASCAL VOC 2007, PASCAL VOC 2012, and NUS datasets and even achieves comparable results to weakly supervised classification methods.
KoBBQ: Korean Bias Benchmark for Question Answering
Venue: arXiv cs.CL 2024
Year: 2024

The Bias Benchmark for Question Answering (BBQ) is designed to evaluate social biases of language models (LMs), but it is not simple to adapt this benchmark to cultural contexts other than the US because social biases depend heavily on the cultural context. In this paper, we present KoBBQ, a Korean bias benchmark dataset, and we propose a general framework that addresses considerations for cultural adaptation of a dataset. Our framework includes partitioning the BBQ dataset into three classes--Simply-Transferred (can be used directly after cultural translation), Target-Modified (requires localization in target groups), and Sample-Removed (does not fit Korean culture)-- and adding four new categories of bias specific to Korean culture. We conduct a large-scale survey to collect and validate the social biases and the targets of the biases that reflect the stereotypes in Korean culture. The resulting KoBBQ dataset comprises 268 templates and 76,048 samples across 12 categories of social bias. We use KoBBQ to measure the accuracy and bias scores of several state-of-the-art multilingual LMs. The results clearly show differences in the bias of LMs as measured by KoBBQ and a machine-translated version of BBQ, demonstrating the need for and utility of a well-constructed, culturally-aware social bias benchmark.
Evaluating Correctness and Faithfulness of Instruction-Following Models for Question Answering
Venue: arXiv cs.CL 2024
Year: 2024

Retriever-augmented instruction-following models are attractive alternatives to fine-tuned approaches for information-seeking tasks such as question answering (QA). By simply prepending retrieved documents in its input along with an instruction, these models can be adapted to various information domains and tasks without additional fine-tuning. While the model responses tend to be natural and fluent, the additional verbosity makes traditional QA evaluation metrics such as exact match (EM) and F1 unreliable for accurately quantifying model performance. In this work, we investigate the performance of instruction-following models across three information-seeking QA tasks. We use both automatic and human evaluation to evaluate these models along two dimensions: 1) how well they satisfy the user's information need (correctness), and 2) whether they produce a response based on the provided knowledge (faithfulness). Guided by human evaluation and analysis, we highlight the shortcomings of traditional metrics for both correctness and faithfulness. We then propose simple token-overlap based and model-based metrics that reflect the true performance of these models. Our analysis reveals that instruction-following models are competitive, and sometimes even outperform fine-tuned models for correctness. However, these models struggle to stick to the provided knowledge and often hallucinate in their responses. We hope our work encourages a more holistic evaluation of instruction-following models for QA. Our code and data is available at https://github.com/McGill-NLP/instruct-qa
MTUncertainty: Assessing the Need for Post-editing of Machine Translation Outputs by Fine-tuning OpenAI LLMs
Venue: arXiv cs.CL 2024
Year: 2024

Translation Quality Evaluation (TQE) is an essential step of the modern translation production process. TQE is critical in assessing both machine translation (MT) and human translation (HT) quality without reference translations. The ability to evaluate or even simply estimate the quality of translation automatically may open significant efficiency gains through process optimisation. This work examines whether the state-of-the-art large language models (LLMs) can be used for this purpose. We take OpenAI models as the best state-of-the-art technology and approach TQE as a binary classification task. On eight language pairs including English to Italian, German, French, Japanese, Dutch, Portuguese, Turkish, and Chinese, our experimental results show that fine-tuned gpt3.5 can demonstrate good performance on translation quality prediction tasks, i.e. whether the translation needs to be edited. Another finding is that simply increasing the sizes of LLMs does not lead to apparent better performances on this task by comparing the performance of three different versions of OpenAI models: curie, davinci, and gpt3.5 with 13B, 175B, and 175B parameters, respectively.
Monotonicity of Equilibria in Nonatomic Congestion Games
Venue: arXiv cs.GT 2024
Year: 2024

This paper studies the monotonicity of equilibrium costs and equilibrium loads in nonatomic congestion games, in response to variations of the demands. The main goal is to identify conditions under which a paradoxical non-monotone behavior can be excluded. In contrast to routing games with a single commodity, where the network topology is the sole determinant factor for monotonicity, for general congestion games with multiple commodities the structure of the strategy sets plays a crucial role. We frame our study in the general setting of congestion games, with a special focus on singleton congestion games, for which we establish the monotonicity of equilibrium loads with respect to every demand. We then provide conditions for comonotonicity of the equilibrium loads, i.e., we investigate when they jointly increase or decrease after variations of the demands. We finally extend our study from singleton congestion games to the larger class of constrained series-parallel congestion games, whose structure is reminiscent of the concept of a series-parallel network.
Structural Parameterizations of the Biclique-Free Vertex Deletion Problem
Venue: arXiv cs.DS 2024
Year: 2024

In this work, we study the Biclique-Free Vertex Deletion problem: Given a graph $G$ and integers $k$ and $i \le j$, find a set of at most $k$ vertices that intersects every (not necessarily induced) biclique $K_{i, j}$ in $G$. This is a natural generalization of the Bounded-Degree Deletion problem, wherein one asks whether there is a set of at most $k$ vertices whose deletion results in a graph of a given maximum degree $r$. The two problems coincide when $i = 1$ and $j = r + 1$. We show that Biclique-Free Vertex Deletion is fixed-parameter tractable with respect to $k + d$ for the degeneracy $d$ by developing a $2^{O(d k^2)} \cdot n^{O(1)}$-time algorithm. We also show that it can be solved in $2^{O(f k)} \cdot n^{O(1)}$ time for the feedback vertex number $f$ when $i \ge 2$. In contrast, we find that it is W[1]-hard for the treedepth for any integer $i \ge 1$. Finally, we show that Biclique-Free Vertex Deletion has a polynomial kernel for every $i \ge 1$ when parameterized by the feedback edge number. Previously, for this parameter, its fixed-parameter tractability for $i = 1$ was known (Betzler et al., 2012) but the existence of polynomial kernel was open.
Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
Venue: arXiv cs.DS 2024
Year: 2024

The dynamic set cover problem has been subject to extensive research since the pioneering works of [Bhattacharya et al, 2015] and [Gupta et al, 2017]. The input is a set system $(U, S)$ on a fixed collection $S$ of sets and a dynamic universe of elements, where each element appears in a most $f$ sets and the cost of each set lies in the range $[1/C, 1]$, and the goal is to efficiently maintain an approximately-minimum set cover under insertions and deletions of elements. Most previous work considers the low-frequency regime, namely $f = O(\log n)$, and this line of work has culminated with a deterministic $(1+ε)f$-approximation algorithm with amortized update time $O(\frac{f^2}{ε^3} + \frac{f}{ε^2}\log C)$ [Bhattacharya et al, 2021]. In the high-frequency regime of $f = Ω(\log n)$, an $O(\log n)$-approximation algorithm with amortized update time $O(f\log n)$ was given by [Gupta et al, 2017]. Interestingly, at the intersection of the two regimes, i.e., $f = Θ(\log n)$, the state-of-the-art results coincide: approximation $Θ(f) = Θ(\log n)$ with amortized update time $O(f^2) = O(f \log n) = O(\log^2 n)$. Up to this date, no previous work achieved update time of $o(f^2)$. In this paper we break the $Ω(f^2)$ update time barrier via the following results: (1) $(1+ε)f$-approximation can be maintained in $O\left(\frac{f}{ε^3}\log^*f + \frac{f}{ε^3}\log C\right) = O_{ε,C}(f \log^* f)$ expected amortized update time; our algorithm works against an adaptive adversary. (2) $(1+ε)f$-approximation can be maintained deterministically in $O\left(\frac{1}εf\log f + \frac{f}{ε^3} + \frac{f\log C}{ε^2}\right) = O_{ε,C}(f \log f)$ amortized update time.
Synthetic Instance Segmentation from Semantic Image Segmentation Masks
Venue: arXiv cs.CV 2024
Year: 2024

In recent years, instance segmentation has garnered significant attention across various applications. However, training a fully-supervised instance segmentation model requires costly both instance-level and pixel-level annotations. In contrast, weakly-supervised instance segmentation methods, such as those using image-level class labels or point labels, often struggle to satisfy the accuracy and recall requirements of practical scenarios. In this paper, we propose a novel paradigm called Synthetic Instance Segmentation (SISeg). SISeg achieves instance segmentation results by leveraging image masks generated by existing semantic segmentation models, and it is highly efficient as we do not require additional training for semantic segmentation or the use of instance-level image annotations. In other words, the proposed model does not need extra manpower or higher computational expenses. Specifically, we first obtain a semantic segmentation mask of the input image via an existent semantic segmentation model. Then, we calculate a displacement field vector for each pixel based on the segmentation mask, which can indicate representations belonging to the same class but different instances, i.e., obtaining the instance-level object information. Finally, the instance segmentation results are refined by a learnable category-agnostic object boundary branch. Extensive experimental results on two challenging datasets highlight the effectiveness of SISeg in achieving competitive results when compared to state-of-the-art methods, especially fully-supervised methods. The code will be released at: SISeg
On the Metric Temporal Logic for Continuous Stochastic Processes
Venue: arXiv cs.LO 2024
Year: 2024

In this paper, we prove measurability of event for which a general continuous-time stochastic process satisfies continuous-time Metric Temporal Logic (MTL) formula. Continuous-time MTL can define temporal constrains for physical system in natural way. Then there are several researches that deal with probability of continuous MTL semantics for stochastic processes. However, proving measurability for such events is by no means an obvious task, even though it is essential. The difficulty comes from the semantics of "until operator", which is defined by logical sum of uncountably many propositions. Given the difficulty involved in proving the measurability of such an event using classical measure-theoretic methods, we employ a theorem from stochastic analysis. This theorem is utilized to prove the measurability of hitting times for stochastic processes, and it stands as a profound result within the theory of capacity. Next, we provide an example that illustrates the failure of probability approximation when discretizing the continuous semantics of MTL formulas with respect to time. Additionally, we prove that the probability of the discretized semantics converges to that of the continuous semantics when we impose restrictions on diamond operators to prevent nesting.