OpenRaiser/Intern-Atlas huggingface dataset:
ARS-DETR: Aspect Ratio-Sensitive Detection Transformer for Aerial Oriented Object Detection
Venue: arXiv cs.CV 2024
Year: 2024

Existing oriented object detection methods commonly use metric AP$_{50}$ to measure the performance of the model. We argue that AP$_{50}$ is inherently unsuitable for oriented object detection due to its large tolerance in angle deviation. Therefore, we advocate using high-precision metric, e.g. AP$_{75}$, to measure the performance of models. In this paper, we propose an Aspect Ratio Sensitive Oriented Object Detector with Transformer, termed ARS-DETR, which exhibits a competitive performance in high-precision oriented object detection. Specifically, a new angle classification method, calling Aspect Ratio aware Circle Smooth Label (AR-CSL), is proposed to smooth the angle label in a more reasonable way and discard the hyperparameter that introduced by previous work (e.g. CSL). Then, a rotated deformable attention module is designed to rotate the sampling points with the corresponding angles and eliminate the misalignment between region features and sampling points. Moreover, a dynamic weight coefficient according to the aspect ratio is adopted to calculate the angle loss. Comprehensive experiments on several challenging datasets show that our method achieves competitive performance on the high-precision oriented object detection task.
Exploiting Contextual Structure to Generate Useful Auxiliary Tasks
Venue: arXiv cs.AI 2024
Year: 2024

Reinforcement learning requires interaction with an environment, which is expensive for robots. This constraint necessitates approaches that work with limited environmental interaction by maximizing the reuse of previous experiences. We propose an approach that maximizes experience reuse while learning to solve a given task by generating and simultaneously learning useful auxiliary tasks. To generate these tasks, we construct an abstract temporal logic representation of the given task and leverage large language models to generate context-aware object embeddings that facilitate object replacements. Counterfactual reasoning and off-policy methods allow us to simultaneously learn these auxiliary tasks while solving the given target task. We combine these insights into a novel framework for multitask reinforcement learning and experimentally show that our generated auxiliary tasks share similar underlying exploration requirements as the given task, thereby maximizing the utility of directed exploration. Our approach allows agents to automatically learn additional useful policies without extra environment interaction.
Direct Access for Answers to Conjunctive Queries with Aggregation
Venue: arXiv cs.DB 2024
Year: 2024

We study the fine-grained complexity of conjunctive queries with grouping and aggregation. For common aggregate functions (e.g., min, max, count, sum), such a query can be phrased as an ordinary conjunctive query over a database annotated with a suitable commutative semiring. We investigate the ability to evaluate such queries by constructing in loglinear time a data structure that provides logarithmic-time direct access to the answers ordered by a given lexicographic order. This task is nontrivial since the number of answers might be larger than loglinear in the size of the input, so the data structure needs to provide a compact representation of the space of answers. In the absence of aggregation and annotation, past research established a sufficient tractability condition on queries and orders. For queries without self-joins, this condition is not just sufficient, but also necessary (under conventional lower-bound assumptions in fine-grained complexity). We show that all past results continue to hold for annotated databases, assuming that the annotation itself does not participate in the lexicographic order. Yet, past algorithms do not apply to the count-distinct aggregation, which has no efficient representation as a commutative semiring; for this aggregation, we establish the corresponding tractability condition. We then show how the complexity of the problem changes when we include the aggregate and annotation value in the order. We also study the impact of having all relations but one annotated by the multiplicative identity (one), as happens when we translate aggregate queries into semiring annotations, and having a semiring with an idempotent addition, such as the case of min, max, and count-distinct over a logarithmic-size domain.
A Convex Hull Cheapest Insertion Heuristic for Precedence Constrained Traveling Salesperson Problems or Sequential Ordering Problems
Venue: arXiv cs.RO 2024
Year: 2024

The convex hull cheapest insertion heuristic is a well-known method that efficiently generates good solutions to the Traveling Salesperson Problem. However, this heuristic has not been adapted to account for precedence constraints that restrict the order in which locations can be visited. Such constraints result in the precedence constrained traveling salesperson problem or the sequential ordering problem, which are commonly encountered in applications where items have to be picked up before they are delivered. In this paper, we present an adapted version of this heuristic that accounts for precedence constraints in the problem definition. This algorithm is compared with the widely used Nearest Neighbor heuristic on the TSPLIB benchmark data with added precedence constraints. It is seen that the proposed algorithm is particularly well suited to cases where delivery nodes are centrally positioned, with pickup nodes located in the periphery, outperforming the Nearest Neighbor algorithm in 97\% of the examined instances.
Exploring New Topologies for the Theory of Clones
Venue: arXiv cs.LO 2024
Year: 2024

Clones of operations of arity omega (referred to as omega-operations) have been employed by Neumann to represent varieties of infinitary algebras defined by operations of at most arity omega. More recently, clone algebras have been introduced to study clones of functions, including omega-operations, within the framework of one-sorted universal algebra. Additionally, polymorphisms of arity omega, which are omega-operations preserving the relations of a given first-order structure, have recently been used to establish model theory results with applications in the field of complexity of CSP problems. In this paper, we undertake a topological and algebraic study of polymorphisms of arity omega and their corresponding invariant relations. Given a set A and a Boolean ideal X on the set of omega-sequences of elements of A, we propose a method to endow the set of omega-operations on A with a topology, which we refer to as X-topology. Notably, the topology of pointwise convergence can be retrieved as a special case of this approach. Polymorphisms and invariant relations are then defined parametrically, with respect to the X-topology. We characterise the X-closed clones of omega-operations in terms of polymorphisms and invariant relations of arity omega, and present a method to relate those infinitary invariant relation and polymorphisms to the classical (finitary) Inv-Pol.
LEDetection: A Simple Framework for Semi-Supervised Few-Shot Object Detection
Venue: arXiv cs.CV 2024
Year: 2024

Few-shot object detection (FSOD) is a challenging problem aimed at detecting novel concepts from few exemplars. Existing approaches to FSOD all assume abundant base labels to adapt to novel objects. This paper studies the new task of semi-supervised FSOD by considering a realistic scenario in which both base and novel labels are simultaneously scarce. We explore the utility of unlabeled data within our proposed label-efficient detection framework and discover its remarkable ability to boost semi-supervised FSOD by way of region proposals. Motivated by this finding, we introduce SoftER Teacher, a robust detector combining pseudo-labeling with consistency learning on region proposals, to harness unlabeled data for improved FSOD without relying on abundant labels. Rigorous experiments show that SoftER Teacher surpasses the novel performance of a strong supervised detector using only 10% of required base labels, without catastrophic forgetting observed in prior approaches. Our work also sheds light on a potential relationship between semi-supervised and few-shot detection suggesting that a stronger semi-supervised detector leads to a more effective few-shot detector.
Uncovering the Handwritten Text in the Margins: End-to-end Handwritten Text Detection and Recognition
Venue: arXiv cs.CV 2024
Year: 2024

The pressing need for digitization of historical documents has led to a strong interest in designing computerised image processing methods for automatic handwritten text recognition. However, not much attention has been paid on studying the handwritten text written in the margins, i.e. marginalia, that also forms an important source of information. Nevertheless, training an accurate and robust recognition system for marginalia calls for data-efficient approaches due to the unavailability of sufficient amounts of annotated multi-writer texts. Therefore, this work presents an end-to-end framework for automatic detection and recognition of handwritten marginalia, and leverages data augmentation and transfer learning to overcome training data scarcity. The detection phase involves investigation of R-CNN and Faster R-CNN networks. The recognition phase includes an attention-based sequence-to-sequence model, with ResNet feature extraction, bidirectional LSTM-based sequence modeling, and attention-based prediction of marginalia. The effectiveness of the proposed framework has been empirically evaluated on the data from early book collections found in the Uppsala University Library in Sweden. Source code and pre-trained models are available at Github.
A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms
Venue: arXiv cs.LG 2024
Year: 2024

In this paper we propose a general methodology to derive regret bounds for randomized multi-armed bandit algorithms. It consists in checking a set of sufficient conditions on the sampling probability of each arm and on the family of distributions to prove a logarithmic regret. As a direct application we revisit two famous bandit algorithms, Minimum Empirical Divergence (MED) and Thompson Sampling (TS), under various models for the distributions including single parameter exponential families, Gaussian distributions, bounded distributions, or distributions satisfying some conditions on their moments. In particular, we prove that MED is asymptotically optimal for all these models, but also provide a simple regret analysis of some TS algorithms for which the optimality is already known. We then further illustrate the interest of our approach, by analyzing a new Non-Parametric TS algorithm (h-NPTS), adapted to some families of unbounded reward distributions with a bounded h-moment. This model can for instance capture some non-parametric families of distributions whose variance is upper bounded by a known constant.
HiNet: Novel Multi-Scenario & Multi-Task Learning with Hierarchical Information Extraction
Venue: arXiv cs.IR 2024
Year: 2024

Multi-scenario & multi-task learning has been widely applied to many recommendation systems in industrial applications, wherein an effective and practical approach is to carry out multi-scenario transfer learning on the basis of the Mixture-of-Expert (MoE) architecture. However, the MoE-based method, which aims to project all information in the same feature space, cannot effectively deal with the complex relationships inherent among various scenarios and tasks, resulting in unsatisfactory performance. To tackle the problem, we propose a Hierarchical information extraction Network (HiNet) for multi-scenario and multi-task recommendation, which achieves hierarchical extraction based on coarse-to-fine knowledge transfer scheme. The multiple extraction layers of the hierarchical network enable the model to enhance the capability of transferring valuable information across scenarios while preserving specific features of scenarios and tasks. Furthermore, a novel scenario-aware attentive network module is proposed to model correlations between scenarios explicitly. Comprehensive experiments conducted on real-world industrial datasets from Meituan Meishi platform demonstrate that HiNet achieves a new state-of-the-art performance and significantly outperforms existing solutions. HiNet is currently fully deployed in two scenarios and has achieved 2.87% and 1.75% order quantity gain respectively.
Full State Estimation of Continuum Robots from Tip Velocities: A Cosserat-Theoretic Boundary Observer
Venue: arXiv cs.RO 2024
Year: 2024

State estimation of robotic systems is essential to implementing feedback controllers, which usually provide better robustness to modeling uncertainties than open-loop controllers. However, state estimation of soft robots is very challenging because soft robots have theoretically infinite degrees of freedom while existing sensors only provide a limited number of discrete measurements. This work focuses on soft robotic manipulators, also known as continuum robots. We design an observer algorithm based on the well-known Cosserat rod theory, which models continuum robots by nonlinear partial differential equations (PDEs) evolving in geometric Lie groups. The observer can estimate all infinite-dimensional continuum robot states, including poses, strains, and velocities, by only sensing the tip velocity of the continuum robot, and hence it is called a ``boundary'' observer. More importantly, the estimation error dynamics is formally proven to be locally input-to-state stable. The key idea is to inject sequential tip velocity measurements into the observer in a way that dissipates the energy of the estimation errors through the boundary. The distinct advantage of this PDE-based design is that it can be implemented using any existing numerical implementation for Cosserat rod models. All theoretical convergence guarantees will be preserved, regardless of the discretization method. We call this property ``one design for any discretization''. Extensive numerical studies are included and suggest that the domain of attraction is large and the observer is robust to uncertainties of tip velocity measurements and model parameters.
Enhancing MAP-Elites with Multiple Parallel Evolution Strategies
Venue: arXiv cs.NE 2024
Year: 2024

With the development of fast and massively parallel evaluations in many domains, Quality-Diversity (QD) algorithms, that already proved promising in a large range of applications, have seen their potential multiplied. However, we have yet to understand how to best use a large number of evaluations as using them for random variations alone is not always effective. High-dimensional search spaces are a typical situation where random variations struggle to effectively search. Another situation is uncertain settings where solutions can appear better than they truly are and naively evaluating more solutions might mislead QD algorithms. In this work, we propose MAP-Elites-Multi-ES (MEMES), a novel QD algorithm based on Evolution Strategies (ES) designed to exploit fast parallel evaluations more effectively. MEMES maintains multiple (up to 100) simultaneous ES processes, each with its own independent objective and reset mechanism designed for QD optimisation, all on just a single GPU. We show that MEMES outperforms both gradient-based and mutation-based QD algorithms on black-box optimisation and QD-Reinforcement-Learning tasks, demonstrating its benefit across domains. Additionally, our approach outperforms sampling-based QD methods in uncertain domains when given the same evaluation budget. Overall, MEMES generates reproducible solutions that are high-performing and diverse through large-scale ES optimisation on easily accessible hardware.
An Implementation of the Optimal Scheme for Energy Efficient Bus Encoding
Venue: arXiv cs.IT 2024
Year: 2024

In computer system buses, most of the energy is spent to change the voltage of each line from high to low or vice versa. Bus encoding schemes aim to improve energy efficiency by limiting the number of transitions between successive uses of the bus. We propose an implementation of the optimal code with reduced number of clock cycles.
Extending global-local view alignment for self-supervised learning with remote sensing imagery
Venue: arXiv cs.CV 2024
Year: 2024

Since large number of high-quality remote sensing images are readily accessible, exploiting the corpus of images with less manual annotation draws increasing attention. Self-supervised models acquire general feature representations by formulating a pretext task that generates pseudo-labels for massive unlabeled data to provide supervision for training. While prior studies have explored multiple self-supervised learning techniques in remote sensing domain, pretext tasks based on local-global view alignment remain underexplored, despite achieving state-of-the-art results on natural imagery. Inspired by DINO, which employs an effective representation learning structure with knowledge distillation based on global-local view alignment, we formulate two pretext tasks for self-supervised learning on remote sensing imagery (SSLRS). Using these tasks, we explore the effectiveness of positive temporal contrast as well as multi-sized views on SSLRS. We extend DINO and propose DINO-MC which uses local views of various sized crops instead of a single fixed size in order to alleviate the limited variation in object size observed in remote sensing imagery. Our experiments demonstrate that even when pre-trained on only 10% of the dataset, DINO-MC performs on par or better than existing state-of-the-art SSLRS methods on multiple remote sensing tasks, while using less computational resources. All codes, models, and results are released at https://github.com/WennyXY/DINO-MC.
Protecting Quantum Procrastinators with Signature Lifting: A Case Study in Cryptocurrencies
Venue: arXiv cs.CR 2024
Year: 2024

Current solutions to quantum vulnerabilities of widely used cryptographic schemes involve migrating users to post-quantum schemes before quantum attacks become feasible. This work deals with protecting quantum procrastinators: users that failed to migrate to post-quantum cryptography in time. To address this problem in the context of digital signatures, we introduce a technique called signature lifting, that allows us to lift a deployed pre-quantum signature scheme satisfying a certain property to a post-quantum signature scheme that uses the same keys. Informally, the said property is that a post-quantum one-way function is used "somewhere along the way" to derive the public-key from the secret-key. Our constructions of signature lifting relies heavily on the post-quantum digital signature scheme Picnic (Chase et al., CCS'17). Our main case-study is cryptocurrencies, where this property holds in two scenarios: when the public-key is generated via a key-derivation function or when the public-key hash is posted instead of the public-key itself. We propose a modification, based on signature lifting, that can be applied in many cryptocurrencies for securely spending pre-quantum coins in presence of quantum adversaries. Our construction improves upon existing constructions in two major ways: it is not limited to pre-quantum coins whose ECDSA public-key has been kept secret (and in particular, it handles all coins that are stored in addresses generated by HD wallets), and it does not require access to post-quantum coins or using side payments to pay for posting the transaction.
Synergizing Beyond Diagonal Reconfigurable Intelligent Surface and Rate-Splitting Multiple Access
Venue: arXiv cs.IT 2024
Year: 2024

This work focuses on the synergy of rate-splitting multiple access (RSMA) and beyond diagonal reconfigurable intelligent surface (BD-RIS) to enlarge the coverage, improve the performance, and save on antennas. Specifically, we employ a multi-sector BD-RIS modeled as a prism, which can achieve highly directional full-space coverage, in a multiuser multiple input single output communication system. With the multi-sector BD-RIS aided RSMA model, we jointly design the transmit precoder and BD-RIS matrix under the imperfect channel state information (CSI) conditions. The robust design is performed by solving a stochastic average sum-rate maximization problem. With sample average approximation and weighted minimum mean square error-rate relationship, the stochastic problem is transformed into a deterministic one with multiple blocks, each of which is iteratively designed. Simulation results show that multi-sector BD-RIS aided RSMA outperforms space division multiple access schemes. More importantly, synergizing multi-sector BD-RIS with RSMA is an efficient strategy to reduce the number of active antennas at the transmitter and the number of passive antennas in BD-RIS.
Complexity and equivalency of multiset dimension and ID-colorings
Venue: arXiv cs.DM 2024
Year: 2024

This investigation is firstly focused into showing that two metric parameters represent the same object in graph theory. That is, we prove that the multiset resolving sets and the ID-colorings of graphs are the same thing. We also consider some computational and combinatorial problems of the multiset dimension, or equivalently, the ID-number of graphs. We prove that the decision problem concerning finding the multiset dimension of graphs is NP-complete. We consider the multiset dimension of king grids and prove that it is bounded above by 4. We also give a characterization of the strong product graphs with one factor being a complete graph, and whose multiset dimension is not infinite.
Thinking Upstream: Ethics and Policy Opportunities in AI Supply Chains
Venue: arXiv cs.CY 2024
Year: 2024

After children were pictured sewing its running shoes in the early 1990s, Nike at first disavowed the "working conditions in its suppliers' factories", before public pressure led them to take responsibility for ethics in their upstream supply chain. In 2023, OpenAI responded to criticism that Kenyan workers were paid less than $2 per hour to filter traumatic content from its ChatGPT model by stating in part that it had outsourced the work to a subcontractor, who managed workers' payment and mental health concerns. In this position paper, we argue that policy interventions for AI Ethics must consider AI as a supply chain problem, given how the political economy and intra-firm relations structure AI production, in particular examining opportunities upstream.