OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Scoring Rule Design under Partial Knowledge
Venue: arXiv cs.GT 2024
Year: 2024

This paper studies the design of optimal proper scoring rules when the principal has partial knowledge of an agent's signal distribution. Recent work characterizes the proper scoring rules that maximize the increase of an agent's payoff when the agent chooses to access a costly signal to refine a posterior belief from her prior prediction, under the assumption that the agent's signal distribution is fully known to the principal. In our setting, the principal only knows about a set of distributions where the agent's signal distribution belongs. We formulate the scoring rule design problem as a max-min optimization that maximizes the worst-case increase in payoff across the set of distributions. We propose an efficient algorithm to compute an optimal scoring rule when the set of distributions is finite, and devise a fully polynomial-time approximation scheme that accommodates various infinite sets of distributions. We further remark that widely used scoring rules, such as the quadratic and log rules, as well as previously identified optimal scoring rules under full knowledge, can be far from optimal in our partial knowledge settings.
Verifying a Realistic Mutable Hash Table
Venue: arXiv cs.SE 2024
Year: 2024

In this work, we verify the mutable LongMap from the Scala standard library, a hash table using open addressing within a single array, using the Stainless program verifier. As a reference implementation, we write an immutable map based on a list of tuples. We then show that LongMap's operations correspond to operations of this association list. To express the resizing of the hash table array, we introduce a new reference swapping construct in Stainless. This allows us to apply the decorator pattern without introducing aliasing. Our verification effort led us to find and fix a bug in the original implementation that manifests for large hash tables. Our performance analysis shows the verified version to be within a 1.5 factor of the original data structure.
Learning Quadruped Locomotion Policies using Logical Rules
Venue: arXiv cs.RO 2024
Year: 2024

Quadruped animals are capable of exhibiting a diverse range of locomotion gaits. While progress has been made in demonstrating such gaits on robots, current methods rely on motion priors, dynamics models, or other forms of extensive manual efforts. People can use natural language to describe dance moves. Could one use a formal language to specify quadruped gaits? To this end, we aim to enable easy gait specification and efficient policy learning. Leveraging Reward Machines~(RMs) for high-level gait specification over foot contacts, our approach is called RM-based Locomotion Learning~(RMLL), and supports adjusting gait frequency at execution time. Gait specification is enabled through the use of a few logical rules per gait (e.g., alternate between moving front feet and back feet) and does not require labor-intensive motion priors. Experimental results in simulation highlight the diversity of learned gaits (including two novel gaits), their energy consumption and stability across different terrains, and the superior sample-efficiency when compared to baselines. We also demonstrate these learned policies with a real quadruped robot. Video and supplementary materials: https://sites.google.com/view/rm-locomotion-learning/home
Learning Geometry-Guided Depth via Projective Modeling for Monocular 3D Object Detection
Venue: arXiv cs.CV 2024
Year: 2024

As a crucial task of autonomous driving, 3D object detection has made great progress in recent years. However, monocular 3D object detection remains a challenging problem due to the unsatisfactory performance in depth estimation. Most existing monocular methods typically directly regress the scene depth while ignoring important relationships between the depth and various geometric elements (e.g. bounding box sizes, 3D object dimensions, and object poses). In this paper, we propose to learn geometry-guided depth estimation with projective modeling to advance monocular 3D object detection. Specifically, a principled geometry formula with projective modeling of 2D and 3D depth predictions in the monocular 3D object detection network is devised. We further implement and embed the proposed formula to enable geometry-aware deep representation learning, allowing effective 2D and 3D interactions for boosting the depth estimation. Moreover, we provide a strong baseline through addressing substantial misalignment between 2D annotation and projected boxes to ensure robust learning with the proposed geometric formula. Experiments on the KITTI dataset show that our method remarkably improves the detection performance of the state-of-the-art monocular-based method without extra data by 2.80% on the moderate test setting. The model and code will be released at https://github.com/YinminZhang/MonoGeo.
I Will Have Order! Optimizing Orders for Fair Reviewer Assignment
Venue: arXiv cs.GT 2024
Year: 2024

We present fast, fair, flexible, and welfare efficient algorithms for assigning reviewers to submitted conference papers. Our approaches extend picking sequence mechanisms, standard tools from the fair allocation literature to ensure approximate envy-freeness (typically envy-freeness up to one item, or EF1). However, fairness often comes at the cost of decreased efficiency. To overcome this challenge, we carefully select approximately optimal picking sequence orders. Applying a relaxation of submodularity, $γ$-weak submodularity, we show our Greedy Reviewer Round Robin (GRRR) approach is EF1 and yields a ${(1+γ)}$-approximation to the maximum welfare attainable by a round-robin picking sequence mechanism under any order. We present a weighted picking sequence mechanism called FairSequence that targets the Weighted EF1 criterion to offer fairness in a more general setting. Using data from three conferences, we show that FairSequence runs an order of magnitude faster and provides approximate envy-freeness guarantees that are violated by existing approaches. Its simple design also makes it very flexible to new assignment constraints. FairSequence is available in the OpenReview conference management platform, giving conference organizers access to faster reviewer assignment with high welfare and envy-freeness guarantees.
Deep Reinforcement Learning for Demand Driven Services in Logistics and Transportation Systems: A Survey
Venue: arXiv cs.LG 2024
Year: 2024

Recent technology development brings the boom of numerous new Demand-Driven Services (DDS) into urban lives, including ridesharing, on-demand delivery, express systems and warehousing. In DDS, a service loop is an elemental structure, including its service worker, the service providers and corresponding service targets. The service workers should transport either people or parcels from the providers to the target locations. Various planning tasks within DDS can thus be classified into two individual stages: 1) Dispatching, which is to form service loops from demand/supply distributions, and 2) Routing, which is to decide specific serving orders within the constructed loops. Generating high-quality strategies in both stages is important to develop DDS but faces several challenges. Meanwhile, deep reinforcement learning (DRL) has been developed rapidly in recent years. It is a powerful tool to solve these problems since DRL can learn a parametric model without relying on too many problem-based assumptions and optimize long-term effects by learning sequential decisions. In this survey, we first define DDS, then highlight common applications and important decision/control problems within. For each problem, we comprehensively introduce the existing DRL solutions. We also introduce open simulation environments for development and evaluation of DDS applications. Finally, we analyze remaining challenges and discuss further research opportunities in DRL solutions for DDS.
Image Inpainting via Conditional Texture and Structure Dual Generation
Venue: arXiv cs.CV 2024
Year: 2024

Deep generative approaches have recently made considerable progress in image inpainting by introducing structure priors. Due to the lack of proper interaction with image texture during structure reconstruction, however, current solutions are incompetent in handling the cases with large corruptions, and they generally suffer from distorted results. In this paper, we propose a novel two-stream network for image inpainting, which models the structure-constrained texture synthesis and texture-guided structure reconstruction in a coupled manner so that they better leverage each other for more plausible generation. Furthermore, to enhance the global consistency, a Bi-directional Gated Feature Fusion (Bi-GFF) module is designed to exchange and combine the structure and texture information and a Contextual Feature Aggregation (CFA) module is developed to refine the generated contents by region affinity learning and multi-scale feature aggregation. Qualitative and quantitative experiments on the CelebA, Paris StreetView and Places2 datasets demonstrate the superiority of the proposed method. Our code is available at https://github.com/Xiefan-Guo/CTSDG.
From Amortized to Worst Case Delay in Enumeration Algorithms
Venue: arXiv cs.CC 2024
Year: 2024

The quality of enumeration algorithms is often measured by their delay, that is, the maximal time spent between the output of two distinct solutions. If the goal is to enumerate $t$ distinct solutions for any given $t$, then another relevant measure is the maximal time needed to output $t$ solutions divided by $t$, a notion we call the amortized delay of the algorithm, since it can be seen as the amortized complexity of the problem of enumerating $t$ elements in the set. In this paper, we study the relation between these two notions of delay, showing different schemes allowing one to transform an algorithm with polynomial amortized delay for which one has a blackbox access into an algorithm with polynomial delay. We complement our results by providing several lower bounds and impossibility theorems in the blackbox model.
From Statistical Relational to Neurosymbolic Artificial Intelligence: a Survey
Venue: arXiv cs.AI 2024
Year: 2024

This survey explores the integration of learning and reasoning in two different fields of artificial intelligence: neurosymbolic and statistical relational artificial intelligence. Neurosymbolic artificial intelligence (NeSy) studies the integration of symbolic reasoning and neural networks, while statistical relational artificial intelligence (StarAI) focuses on integrating logic with probabilistic graphical models. This survey identifies seven shared dimensions between these two subfields of AI. These dimensions can be used to characterize different NeSy and StarAI systems. They are concerned with (1) the approach to logical inference, whether model or proof-based; (2) the syntax of the used logical theories; (3) the logical semantics of the systems and their extensions to facilitate learning; (4) the scope of learning, encompassing either parameter or structure learning; (5) the presence of symbolic and subsymbolic representations; (6) the degree to which systems capture the original logic, probabilistic, and neural paradigms; and (7) the classes of learning tasks the systems are applied to. By positioning various NeSy and StarAI systems along these dimensions and pointing out similarities and differences between them, this survey contributes fundamental concepts for understanding the integration of learning and reasoning.
Renting Servers in the Cloud: The Case of Equal Duration Jobs
Venue: arXiv cs.DS 2024
Year: 2024

Renting servers in the cloud is a generalization of the bin packing problem, motivated by job allocation to servers in cloud computing applications. Jobs arrive in an online manner, and need to be assigned to servers; their duration and size are known at the time of arrival. There is an infinite supply of identical servers, each having one unit of computational capacity per unit of time. A server can be rented at any time and continues to be rented until all jobs assigned to it finish. The cost of an assignment is the sum of durations of rental periods of all servers. The goal is to assign jobs to servers to minimize the overall cost while satisfying server capacity constraints. We focus on analyzing two natural algorithms, NextFit and FirstFit, for the case of jobs of equal duration. It is known that the competitive ratio of NextFit and FirstFit are at most 3 and 4 respectively for this case. We prove a tight bound of 2 on the competitive ratio of NextFit. For FirstFit, we establish a lower bound of 2.519 on the competitive ratio, even when jobs have only two distinct arrival times. For the case when jobs have arrival times 0 and 1 and duration 2, we show a lower bound of 1.89 and an upper bound of 2 on the strict competitive ratio of FirstFit. Finally, using the weight function technique, we obtain stronger results for the case of uniform servers.
Semi-Supervised Crowd Counting from Unlabeled Data
Venue: arXiv cs.CV 2024
Year: 2024

Automatic Crowd behavior analysis can be applied to effectively help the daily transportation statistics and planning, which helps the smart city construction. As one of the most important keys, crowd counting has drawn increasing attention. Recent works achieved promising performance but relied on the supervised paradigm with expensive crowd annotations. To alleviate the annotation cost in real-world transportation scenarios, in this work we proposed a semi-supervised learning framework $S^{4}\textit{Crowd}$, which can leverage both unlabeled/labeled data for robust crowd counting. In the unsupervised pathway, two \textit{self-supervised losses} were proposed to simulate the crowd variations such as scale, illumination, based on which supervised information pseudo labels were generated and gradually refined. We also proposed a crowd-driven recurrent unit \textit{Gated-Crowd-Recurrent-Unit (GCRU)}, which can preserve discriminant crowd information by extracting second-order statistics, yielding pseudo labels with improved quality. A joint loss including both unsupervised/supervised information was proposed, and a dynamic weighting strategy was employed to balance the importance of the unsupervised loss and supervised loss at different training stages. We conducted extensive experiments on four popular crowd counting datasets in semi-supervised settings. Experimental results supported the effectiveness of each proposed component in our $S^{4}$Crowd framework. Our method achieved competitive performance in semi-supervised learning approaches on these crowd counting datasets.
Data Science Kitchen at GermEval 2021: A Fine Selection of Hand-Picked Features, Delivered Fresh from the Oven
Venue: arXiv cs.CL 2024
Year: 2024

This paper presents the contribution of the Data Science Kitchen at GermEval 2021 shared task on the identification of toxic, engaging, and fact-claiming comments. The task aims at extending the identification of offensive language, by including additional subtasks that identify comments which should be prioritized for fact-checking by moderators and community managers. Our contribution focuses on a feature-engineering approach with a conventional classification backend. We combine semantic and writing style embeddings derived from pre-trained deep neural networks with additional numerical features, specifically designed for this task. Classifier ensembles are used to derive predictions for each subtask via a majority voting scheme. Our best submission achieved macro-averaged F1-scores of 66.8\%,\,69.9\% and 72.5\% for the identification of toxic, engaging, and fact-claiming comments.
Novel Time Domain Based Upper-Limb Prosthesis Control using Incremental Learning Approach
Venue: arXiv cs.HC 2024
Year: 2024

The upper limb of the body is a vital for various kind of activities for human. The complete or partial loss of the upper limb would lead to a significant impact on daily activities of the amputees. EMG carries important information of human physique which helps to decode the various functionalities of human arm. EMG signal based bionics and prosthesis have gained huge research attention over the past decade. Conventional EMG-PR based prosthesis struggles to give accurate performance due to off-line training used and incapability to compensate for electrode position shift and change in arm position. This work proposes online training and incremental learning based system for upper limb prosthetic application. This system consists of ADS1298 as AFE (analog front end) and a 32 bit arm cortex-m4 processor for DSP (digital signal processing). The system has been tested for both intact and amputated subjects. Time derivative moment based features have been implemented and utilized for effective pattern classification. Initially, system have been trained for four classes using the on-line training process later on the number of classes have been incremented on user demand till eleven, and system performance has been evaluated. The system yielded a completion rate of 100% for healthy and amputated subjects when four motions have been considered. Further 94.33% and 92% completion rate have been showcased by the system when the number of classes increased to eleven for healthy and amputees respectively. The motion efficacy test is also evaluated for all the subjects. The highest efficacy rate of 91.23% and 88.64% are observed for intact and amputated subjects respectively.
Fast Algorithms for Minimum Homology Basis
Venue: arXiv cs.CG 2024
Year: 2024

We study the problem of finding a minimum homology basis, that is, a lightest set of cycles that generates the $1$-dimensional homology classes with $\mathbb{Z}_2$ coefficients in a given simplicial complex $K$. This problem has been extensively studied in the last few years. For general complexes, the current best deterministic algorithm, by Dey et al., runs in $O(N m^{ω-1} + n m g)$ time, where $N$ denotes the total number of simplices in $K$, $m$ denotes the number of edges in $K$, $n$ denotes the number of vertices in $K$, $g$ denotes the rank of the $1$-homology group of $K$, and $ω$ denotes the exponent of matrix multiplication. In this paper, we present three conceptually simple randomized algorithms that compute a minimum homology basis of a general simplicial complex $K$. The first algorithm runs in $\tilde{O}(m^ω)$ time, the second algorithm runs in $O(N m^{ω-1})$ time and the third algorithm runs in $\tilde{O}(N^2 g + N m g{^2} + m g{^3})$ time which is nearly quadratic time when $g=O(1)$. We also study the problem of finding a minimum cycle basis in an undirected graph $G$ with $n$ vertices and $m$ edges. The best known algorithm for this problem runs in $O(m^ω)$ time. Our algorithm, which has a simpler high-level description, but is slightly more expensive, runs in $\tilde{O}(m^ω)$ time. We also provide a practical implementation of computing the minimum homology basis for general weighted complexes. The implementation is broadly based on the algorithmic ideas described in this paper, differing in its use of practical subroutines. Of these subroutines, the more costly step makes use of a parallel implementation, thus potentially addressing the issue of scale. We compare results against the currently known state of the art implementation (ShortLoop).
Training Fair Models in Federated Learning without Data Privacy Infringement
Venue: arXiv cs.LG 2024
Year: 2024

Training fair machine learning models becomes more and more important. As many powerful models are trained by collaboration among multiple parties, each holding some sensitive data, it is natural to explore the feasibility of training fair models in federated learning so that the fairness of trained models, the data privacy of clients, and the collaboration between clients can be fully respected simultaneously. However, the task of training fair models in federated learning is challenging, since it is far from trivial to estimate the fairness of a model without knowing the private data of the participating parties, which is often constrained by privacy requirements in federated learning. In this paper, we first propose a federated estimation method to accurately estimate the fairness of a model without infringing the data privacy of any party. Then, we use the fairness estimation to formulate a novel problem of training fair models in federated learning. We develop FedFair, a well-designed federated learning framework, which can successfully train a fair model with high performance without data privacy infringement. Our extensive experiments on three real-world data sets demonstrate the excellent fair model training performance of our method.
Pareto-wise Ranking Classifier for Multi-objective Evolutionary Neural Architecture Search
Venue: arXiv cs.LG 2024
Year: 2024

In the deployment of deep neural models, how to effectively and automatically find feasible deep models under diverse design objectives is fundamental. Most existing neural architecture search (NAS) methods utilize surrogates to predict the detailed performance (e.g., accuracy and model size) of a candidate architecture during the search, which however is complicated and inefficient. In contrast, we aim to learn an efficient Pareto classifier to simplify the search process of NAS by transforming the complex multi-objective NAS task into a simple Pareto-dominance classification task. To this end, we propose a classification-wise Pareto evolution approach for one-shot NAS, where an online classifier is trained to predict the dominance relationship between the candidate and constructed reference architectures, instead of using surrogates to fit the objective functions. The main contribution of this study is to change supernet adaption into a Pareto classifier. Besides, we design two adaptive schemes to select the reference set of architectures for constructing classification boundary and regulate the rate of positive samples over negative ones, respectively. We compare the proposed evolution approach with state-of-the-art approaches on widely-used benchmark datasets, and experimental results indicate that the proposed approach outperforms other approaches and have found a number of neural architectures with different model sizes ranging from 2M to 6M under diverse objectives and constraints.
Unsupervised View-Invariant Human Posture Representation
Venue: arXiv cs.CV 2024
Year: 2024

Most recent view-invariant action recognition and performance assessment approaches rely on a large amount of annotated 3D skeleton data to extract view-invariant features. However, acquiring 3D skeleton data can be cumbersome, if not impractical, in in-the-wild scenarios. To overcome this problem, we present a novel unsupervised approach that learns to extract view-invariant 3D human pose representation from a 2D image without using 3D joint data. Our model is trained by exploiting the intrinsic view-invariant properties of human pose between simultaneous frames from different viewpoints and their equivariant properties between augmented frames from the same viewpoint. We evaluate the learned view-invariant pose representations for two downstream tasks. We perform comparative experiments that show improvements on the state-of-the-art unsupervised cross-view action classification accuracy on NTU RGB+D by a significant margin, on both RGB and depth images. We also show the efficiency of transferring the learned representations from NTU RGB+D to obtain the first ever unsupervised cross-view and cross-subject rank correlation results on the multi-view human movement quality dataset, QMAR, and marginally improve on the-state-of-the-art supervised results for this dataset. We also carry out ablation studies to examine the contributions of the different components of our proposed network.