OpenRaiser/Intern-Atlas huggingface dataset:
Parallel solutions for ordinal scheduling with a small number of machines
Venue: arXiv cs.DS 2022
Year: 2022

We study ordinal makespan scheduling on small numbers of identical machines, with respect to two parallel solutions. In ordinal scheduling, it is known that jobs are sorted by non-increasing sizes, but the specific sizes are not known in advance. For problems with two parallel solutions, it is required to design two solutions, and the performance of algorithm is tested for each input using the best solution of the two. We find tight results for makespan minimization on two and three machines, and algorithms that have strictly better competitive ratios than the best possible algorithm with a single solution also for four and five machines. To prove upper bounds, we use a new approach of considering pairs of machines from the two solutions.
Pretrained Transformers Do not Always Improve Robustness
Venue: arXiv cs.CL 2022
Year: 2022

Pretrained Transformers (PT) have been shown to improve Out of Distribution (OOD) robustness than traditional models such as Bag of Words (BOW), LSTMs, Convolutional Neural Networks (CNN) powered by Word2Vec and Glove embeddings. How does the robustness comparison hold in a real world setting where some part of the dataset can be noisy? Do PT also provide more robust representation than traditional models on exposure to noisy data? We perform a comparative study on 10 models and find an empirical evidence that PT provide less robust representation than traditional models on exposure to noisy data. We investigate further and augment PT with an adversarial filtering (AF) mechanism that has been shown to improve OOD generalization. However, increase in generalization does not necessarily increase robustness, as we find that noisy data fools the AF method powered by PT.
Full-Stack Bioacoustics: Field Kit to AI to Action (Workshop report)
Venue: arXiv cs.SD 2022
Year: 2022

Acoustic data (sound recordings) are a vital source of evidence for detecting, counting, and distinguishing wildlife. This domain of "bioacoustics" has grown in the past decade due to the massive advances in signal processing and machine learning, recording devices, and the capacity of data processing and storage. Numerous research papers describe the use of Raspberry Pi or similar devices for acoustic monitoring, and other research papers describe automatic classification of animal sounds by machine learning. But for most ecologists, zoologists, conservationists, the pieces of the puzzle do not come together: the domain is fragmented. In this Lorentz workshop we bridge this gap by bringing together leading exponents of open hardware and open-source software for bioacoustic monitoring and machine learning, as well as ecologists and other field researchers. We share skills while also building a vision for the future development of "bioacoustic AI". This report contains an overview of the workshop aims and structure, as well as reports from the six groups.
Designing a general library for convolutions
Venue: arXiv cs.LO 2022
Year: 2022

We will discuss our experiences and design decisions obtained from building a formal library for the convolution of two functions. Convolution is a fundamental concept with applications throughout mathematics. We will focus on the design decisions we made to make the convolution general and easy to use, and the incorporation of this development in Lean's mathematical library mathlib.
A Lightweight Moving Target Defense Framework for Multi-purpose Malware Affecting IoT Devices
Venue: arXiv cs.CR 2022
Year: 2022

Malware affecting Internet of Things (IoT) devices is rapidly growing due to the relevance of this paradigm in real-world scenarios. Specialized literature has also detected a trend towards multi-purpose malware able to execute different malicious actions such as remote control, data leakage, encryption, or code hiding, among others. Protecting IoT devices against this kind of malware is challenging due to their well-known vulnerabilities and limitation in terms of CPU, memory, and storage. To improve it, the moving target defense (MTD) paradigm was proposed a decade ago and has shown promising results, but there is a lack of IoT MTD solutions dealing with multi-purpose malware. Thus, this work proposes four MTD mechanisms changing IoT devices' network, data, and runtime environment to mitigate multi-purpose malware. Furthermore, it presents a lightweight and IoT-oriented MTD framework to decide what, when, and how the MTD mechanisms are deployed. Finally, the efficiency and effectiveness of the framework and MTD mechanisms are evaluated in a real-world scenario with one IoT spectrum sensor affected by multi-purpose malware.
DroneARchery: Human-Drone Interaction through Augmented Reality with Haptic Feedback and Multi-UAV Collision Avoidance Driven by Deep Reinforcement Learning
Venue: arXiv cs.RO 2022
Year: 2022

We propose a novel concept of augmented reality (AR) human-drone interaction driven by RL-based swarm behavior to achieve intuitive and immersive control of a swarm formation of unmanned aerial vehicles. The DroneARchery system developed by us allows the user to quickly deploy a swarm of drones, generating flight paths simulating archery. The haptic interface LinkGlide delivers a tactile stimulus of the bowstring tension to the forearm to increase the precision of aiming. The swarm of released drones dynamically avoids collisions between each other, the drone following the user, and external obstacles with behavior control based on deep reinforcement learning. The developed concept was tested in the scenario with a human, where the user shoots from a virtual bow with a real drone to hit the target. The human operator observes the ballistic trajectory of the drone in an AR and achieves a realistic and highly recognizable experience of the bowstring tension through the haptic display. The experimental results revealed that the system improves trajectory prediction accuracy by 63.3% through applying AR technology and conveying haptic feedback of pulling force. DroneARchery users highlighted the naturalness (4.3 out of 5 point Likert scale) and increased confidence (4.7 out of 5) when controlling the drone. We have designed the tactile patterns to present four sliding distances (tension) and three applied force levels (stiffness) of the haptic display. Users demonstrated the ability to distinguish tactile patterns produced by the haptic display representing varying bowstring tension(average recognition rate is of 72.8%) and stiffness (average recognition rate is of 94.2%). The novelty of the research is the development of an AR-based approach for drone control that does not require special skills and training from the operator.
Simpson's Paradox in Recommender Fairness: Reconciling differences between per-user and aggregated evaluations
Venue: arXiv cs.IR 2022
Year: 2022

There has been a flurry of research in recent years on notions of fairness in ranking and recommender systems, particularly on how to evaluate if a recommender allocates exposure equally across groups of relevant items (also known as provider fairness). While this research has laid an important foundation, it gave rise to different approaches depending on whether relevant items are compared per-user/per-query or aggregated across users. Despite both being established and intuitive, we discover that these two notions can lead to opposite conclusions, a form of Simpson's Paradox. We reconcile these notions and show that the tension is due to differences in distributions of users where items are relevant, and break down the important factors of the user's recommendations. Based on this new understanding, practitioners might be interested in either notions, but might face challenges with the per-user metric due to partial observability of the relevance and user satisfaction, typical in real-world recommenders. We describe a technique based on distribution matching to estimate it in such a scenario. We demonstrate on simulated and real-world recommender data the effectiveness and usefulness of such an approach.
Prompt Conditioned VAE: Enhancing Generative Replay for Lifelong Learning in Task-Oriented Dialogue
Venue: arXiv cs.CL 2022
Year: 2022

Lifelong learning (LL) is vital for advanced task-oriented dialogue (ToD) systems. To address the catastrophic forgetting issue of LL, generative replay methods are widely employed to consolidate past knowledge with generated pseudo samples. However, most existing generative replay methods use only a single task-specific token to control their models. This scheme is usually not strong enough to constrain the generative model due to insufficient information involved. In this paper, we propose a novel method, prompt conditioned VAE for lifelong learning (PCLL), to enhance generative replay by incorporating tasks' statistics. PCLL captures task-specific distributions with a conditional variational autoencoder, conditioned on natural language prompts to guide the pseudo-sample generation. Moreover, it leverages a distillation process to further consolidate past knowledge by alleviating the noise in pseudo samples. Experiments on natural language understanding tasks of ToD systems demonstrate that PCLL significantly outperforms competitive baselines in building LL models.
EfficientVLM: Fast and Accurate Vision-Language Models via Knowledge Distillation and Modal-adaptive Pruning
Venue: arXiv cs.CL 2022
Year: 2022

Pre-trained vision-language models (VLMs) have achieved impressive results in a range of vision-language tasks. However, popular VLMs usually consist of hundreds of millions of parameters which brings challenges for fine-tuning and deployment in real-world applications due to space, memory, and latency constraints. In this work, we introduce a distilling then pruning framework to compress large vision-language models into smaller, faster, and more accurate ones. We first shrink the size of a pre-trained large VLM and apply knowledge distillation in the vision-language pre-training stage to obtain a task-agnostic compact VLM. Then we propose a modal-adaptive pruning algorithm to automatically infer the importance of vision and language modalities for different downstream tasks and adaptively remove redundant structures and neurons in different encoders with controllable target sparsity. We apply our framework to train EfficientVLM, a fast and accurate vision-language model consisting of 6 vision layers, 3 text layers, and 3 cross-modal fusion layers, accounting for only 93 million parameters in total, which is 44.3% of the teacher model. EfficientVLM retains 98.4% performance of the teacher model and accelerates its inference speed by 2.2x. EfficientVLM achieves a large absolute improvement over previous SoTA efficient VLMs of similar sizes by a large margin on various vision-language tasks, including VQAv2 (+4.9%), NLVR2 (+5.6%), ITR (R@1 on TR +17.2%, on IR + 15.6% ) and COCO caption generation (CIDEr +6.5), demonstrating a large potential on training lightweight VLMs.
Multiple Choice Hard Thresholding Pursuit (MCHTP) for Simultaneous Sparse Recovery and Sparsity Order Estimation
Venue: arXiv cs.IT 2022
Year: 2022

We address the problem of sparse recovery using greedy compressed sensing recovery algorithms, without explicit knowledge of the sparsity. Estimating the sparsity order is a crucial problem in many practical scenarios, e.g., wireless communications, where exact value of the sparsity order of the unknown channel may be unavailable a priori. In this paper we have proposed a new greedy algorithm, referred to as the Multiple Choice Hard Thresholding Pursuit (MCHTP), which modifies the popular hard thresholding pursuit (HTP) suitably to iteratively recover the unknown sparse vector along with the sparsity order of the unknown vector. We provide provable performance guarantees which ensures that MCHTP can estimate the sparsity order exactly, along with recovering the unknown sparse vector exactly with noiseless measurements. The simulation results corroborate the theoretical findings, demonstrating that even without exact sparsity knowledge, with only the knowledge of a loose upper bound of the sparsity, MCHTP exhibits outstanding recovery performance, which is almost identical to that of the conventional HTP with exact sparsity knowledge. Furthermore, simulation results demonstrate much lower computational complexity of MCHTP compared to other state-of-the-art techniques like MSP.
SAILOR: Scaling Anchors via Insights into Latent Object Representation
Venue: arXiv cs.CV 2022
Year: 2022

LiDAR 3D object detection models are inevitably biased towards their training dataset. The detector clearly exhibits this bias when employed on a target dataset, particularly towards object sizes. However, object sizes vary heavily between domains due to, for instance, different labeling policies or geographical locations. State-of-the-art unsupervised domain adaptation approaches outsource methods to overcome the object size bias. Mainstream size adaptation approaches exploit target domain statistics, contradicting the original unsupervised assumption. Our novel unsupervised anchor calibration method addresses this limitation. Given a model trained on the source data, we estimate the optimal target anchors in a completely unsupervised manner. The main idea stems from an intuitive observation: by varying the anchor sizes for the target domain, we inevitably introduce noise or even remove valuable object cues. The latent object representation, perturbed by the anchor size, is closest to the learned source features only under the optimal target anchors. We leverage this observation for anchor size optimization. Our experimental results show that, without any retraining, we achieve competitive results even compared to state-of-the-art weakly-supervised size adaptation approaches. In addition, our anchor calibration can be combined with such existing methods, making them completely unsupervised.
A Recommendation Approach based on Similarity-Popularity Models of Complex Networks
Venue: arXiv cs.IR 2022
Year: 2022

Recommender systems have become an essential tool for providers and users of online services and goods, especially with the increased use of the Internet to access information and purchase products and services. This work proposes a novel recommendation method based on complex networks generated by a similarity-popularity model to predict ones. We first construct a model of a network having users and items as nodes from observed ratings and then use it to predict unseen ratings. The prospect of producing accurate rating predictions using a similarity-popularity model with hidden metric spaces and dot-product similarity is explored. The proposed approach is implemented and experimentally compared against baseline and state-of-the-art recommendation methods on 21 datasets from various domains. The experimental results demonstrate that the proposed method produces accurate predictions and outperforms existing methods. We also show that the proposed approach produces superior results in low dimensions, proving its effectiveness for data visualization and exploration.
Parameter-Free Average Attention Improves Convolutional Neural Network Performance (Almost) Free of Charge
Venue: arXiv cs.CV 2022
Year: 2022

Visual perception is driven by the focus on relevant aspects in the surrounding world. To transfer this observation to the digital information processing of computers, attention mechanisms have been introduced to highlight salient image regions. Here, we introduce a parameter-free attention mechanism called PfAAM, that is a simple yet effective module. It can be plugged into various convolutional neural network architectures with a little computational overhead and without affecting model size. PfAAM was tested on multiple architectures for classification and segmentic segmentation leading to improved model performance for all tested cases. This demonstrates its wide applicability as a general easy-to-use module for computer vision tasks. The implementation of PfAAM can be found on https://github.com/nkoerb/pfaam.
PedFormer: Pedestrian Behavior Prediction via Cross-Modal Attention Modulation and Gated Multitask Learning
Venue: arXiv cs.CV 2022
Year: 2022

Predicting pedestrian behavior is a crucial task for intelligent driving systems. Accurate predictions require a deep understanding of various contextual elements that potentially impact the way pedestrians behave. To address this challenge, we propose a novel framework that relies on different data modalities to predict future trajectories and crossing actions of pedestrians from an ego-centric perspective. Specifically, our model utilizes a cross-modal Transformer architecture to capture dependencies between different data types. The output of the Transformer is augmented with representations of interactions between pedestrians and other traffic agents conditioned on the pedestrian and ego-vehicle dynamics that are generated via a semantic attentive interaction module. Lastly, the context encodings are fed into a multi-stream decoder framework using a gated-shared network. We evaluate our algorithm on public pedestrian behavior benchmarks, PIE and JAAD, and show that our model improves state-of-the-art in trajectory and action prediction by up to 22% and 13% respectively on various metrics. The advantages brought by components of our model are investigated via extensive ablation studies.
Model-checking lock-sharing systems against regular constraints
Venue: arXiv cs.FL 2022
Year: 2022

We study the verification of distributed systems where processes are finite automata with access to a shared pool of locks. We consider objectives that are boolean combinations of local regular constraints. We show that the problem, PSPACE-complete in general, falls in NP with the right assumptions on the system. We use restrictions on the number of locks a process can access and the order in which locks can be released. We provide tight complexity bounds, as well as a subcase of interest that can be solved in PTIME.
A Note on Fourier-Motzkin Elimination with Three Eliminating Variables
Venue: arXiv cs.IT 2022
Year: 2022

In this note, we show how difficult the brute-force Fourier-Motzkin elimination is, even in a simple case with three eliminating variables. Specifically, we first give a theorem, which plays quite an important role in the study of information-theoretic security for a multiple access wiretap (MAC-WT) channel, and then prove it for the case with three users by directly using the Fourier-Motzkin procedure. It is shown that large amounts of inequalities are generated in the elimination procedure while most of them are redundant. Actually, the number of generated inequalities grows doubly exponentially with the number of users or eliminating variables. It thus becomes unmanageable to directly prove the theorem in this brute-force way. Besides the great complexity, another disadvantage of the direct strategy is that it works only if the number of users is given. Obviously, this makes the strategy inappropriate for the proof of the theorem since it is a general result for any number of users. It is thus urgent and challenging to generally prove the theorem.
PseudoReasoner: Leveraging Pseudo Labels for Commonsense Knowledge Base Population
Venue: arXiv cs.CL 2022
Year: 2022

Commonsense Knowledge Base (CSKB) Population aims at reasoning over unseen entities and assertions on CSKBs, and is an important yet hard commonsense reasoning task. One challenge is that it requires out-of-domain generalization ability as the source CSKB for training is of a relatively smaller scale (1M) while the whole candidate space for population is way larger (200M). We propose PseudoReasoner, a semi-supervised learning framework for CSKB population that uses a teacher model pre-trained on CSKBs to provide pseudo labels on the unlabeled candidate dataset for a student model to learn from. The teacher can be a generative model rather than restricted to discriminative models as previous works. In addition, we design a new filtering procedure for pseudo labels based on influence function and the student model's prediction to further improve the performance. The framework can improve the backbone model KG-BERT (RoBERTa-large) by 3.3 points on the overall performance and especially, 5.3 points on the out-of-domain performance, and achieves the state-of-the-art. Codes and data are available at https://github.com/HKUST-KnowComp/PseudoReasoner.
MiQA: A Benchmark for Inference on Metaphorical Questions
Venue: arXiv cs.CL 2022
Year: 2022

We propose a benchmark to assess the capability of large language models to reason with conventional metaphors. Our benchmark combines the previously isolated topics of metaphor detection and commonsense reasoning into a single task that requires a model to make inferences by accurately selecting between the literal and metaphorical register. We examine the performance of state-of-the-art pre-trained models on binary-choice tasks and find a large discrepancy between the performance of small and very large models, going from chance to near-human level. We also analyse the largest model in a generative setting and find that although human performance is approached, careful multiple-shot prompting is required.
Trajectory Prediction for Vehicle Conflict Identification at Intersections Using Sequence-to-Sequence Recurrent Neural Networks
Venue: arXiv cs.AI 2022
Year: 2022

Surrogate safety measures in the form of conflict indicators are indispensable components of the proactive traffic safety toolbox. Conflict indicators can be classified into past-trajectory-based conflicts and predicted-trajectory-based conflicts. While the calculation of the former class of conflicts is deterministic and unambiguous, the latter category is computed using predicted vehicle trajectories and is thus more stochastic. Consequently, the accuracy of prediction-based conflicts is contingent on the accuracy of the utilized trajectory prediction algorithm. Trajectory prediction can be a challenging task, particularly at intersections where vehicle maneuvers are diverse. Furthermore, due to limitations relating to the road user trajectory extraction pipelines, accurate geometric representation of vehicles during conflict analysis is a challenging task. Misrepresented geometries distort the real distances between vehicles under observation. In this research, a prediction-based conflict identification methodology was proposed. A sequence-to-sequence Recurrent Neural Network was developed to sequentially predict future vehicle trajectories for up to 3 seconds ahead. Furthermore, the proposed network was trained using the CitySim Dataset to forecast both future vehicle positions and headings to facilitate the prediction of future bounding boxes, thus maintaining accurate vehicle geometric representations. It was experimentally determined that the proposed method outperformed frequently used trajectory prediction models for conflict analysis at intersections. A comparison between Time-to-Collision (TTC) conflict identification using vehicle bounding boxes versus the commonly used vehicle center points for geometric representation was conducted. Compared to the bounding box method, the center point approach often failed to identify TTC conflicts or underestimated their severity.