OpenRaiser/Intern-Atlas huggingface dataset:
Spatial Bias for Attention-free Non-local Neural Networks
Venue: arXiv cs.CV 2023
Year: 2023

In this paper, we introduce the spatial bias to learn global knowledge without self-attention in convolutional neural networks. Owing to the limited receptive field, conventional convolutional neural networks suffer from learning long-range dependencies. Non-local neural networks have struggled to learn global knowledge, but unavoidably have too heavy a network design due to the self-attention operation. Therefore, we propose a fast and lightweight spatial bias that efficiently encodes global knowledge without self-attention on convolutional neural networks. Spatial bias is stacked on the feature map and convolved together to adjust the spatial structure of the convolutional features. Therefore, we learn the global knowledge on the convolution layer directly with very few additional resources. Our method is very fast and lightweight due to the attention-free non-local method while improving the performance of neural networks considerably. Compared to non-local neural networks, the spatial bias use about 10 times fewer parameters while achieving comparable performance with 1.6 ~ 3.3 times more throughput on a very little budget. Furthermore, the spatial bias can be used with conventional non-local neural networks to further improve the performance of the backbone model. We show that the spatial bias achieves competitive performance that improves the classification accuracy by +0.79% and +1.5% on ImageNet-1K and cifar100 datasets. Additionally, we validate our method on the MS-COCO and ADE20K datasets for downstream tasks involving object detection and semantic segmentation.
Fast Convergence of $k$-Opinion Undecided State Dynamics in the Population Protocol Model
Venue: arXiv cs.DC 2023
Year: 2023

We analyze the convergence of the $k$-opinion Undecided State Dynamics (USD) in the population protocol model. For $k$=2 opinions it is well known that the USD reaches consensus with high probability within $O(n \log n)$ interactions. Proving that the process also quickly solves the consensus problem for $k>2$ opinions has remained open, despite analogous results for larger $k$ in the related parallel gossip model. In this paper we prove such convergence: under mild assumptions on $k$ and on the initial number of undecided agents we prove that the USD achieves plurality consensus within $O(k n \log n)$ interactions with high probability, regardless of the initial bias. Moreover, if there is an initial additive bias of at least $Ω(\sqrt{n} \log n)$ we prove that the initial plurality opinion wins with high probability, and if there is a multiplicative bias the convergence time is further improved. Note that this is the first result for $k > 2$ for the USD in the population protocol model. Furthermore, it is the first result for the unsynchronized variant of the USD with $k>2$ which does not need any initial bias.
Implicit Temporal Reasoning for Evidence-Based Fact-Checking
Venue: arXiv cs.CL 2023
Year: 2023

Leveraging contextual knowledge has become standard practice in automated claim verification, yet the impact of temporal reasoning has been largely overlooked. Our study demonstrates that time positively influences the claim verification process of evidence-based fact-checking. The temporal aspects and relations between claims and evidence are first established through grounding on shared timelines, which are constructed using publication dates and time expressions extracted from their text. Temporal information is then provided to RNN-based and Transformer-based classifiers before or after claim and evidence encoding. Our time-aware fact-checking models surpass base models by up to 9% Micro F1 (64.17%) and 15% Macro F1 (47.43%) on the MultiFC dataset. They also outperform prior methods that explicitly model temporal relations between evidence. Our findings show that the presence of temporal information and the manner in which timelines are constructed greatly influence how fact-checking models determine the relevance and supporting or refuting character of evidence documents.
EvoTorch: Scalable Evolutionary Computation in Python
Venue: arXiv cs.NE 2023
Year: 2023

Evolutionary computation is an important component within various fields such as artificial intelligence research, reinforcement learning, robotics, industrial automation and/or optimization, engineering design, etc. Considering the increasing computational demands and the dimensionalities of modern optimization problems, the requirement for scalable, re-usable, and practical evolutionary algorithm implementations has been growing. To address this requirement, we present EvoTorch: an evolutionary computation library designed to work with high-dimensional optimization problems, with GPU support and with high parallelization capabilities. EvoTorch is based on and seamlessly works with the PyTorch library, and therefore, allows the users to define their optimization problems using a well-known API.
T-Phenotype: Discovering Phenotypes of Predictive Temporal Patterns in Disease Progression
Venue: arXiv cs.LG 2023
Year: 2023

Clustering time-series data in healthcare is crucial for clinical phenotyping to understand patients' disease progression patterns and to design treatment guidelines tailored to homogeneous patient subgroups. While rich temporal dynamics enable the discovery of potential clusters beyond static correlations, two major challenges remain outstanding: i) discovery of predictive patterns from many potential temporal correlations in the multi-variate time-series data and ii) association of individual temporal patterns to the target label distribution that best characterizes the underlying clinical progression. To address such challenges, we develop a novel temporal clustering method, T-Phenotype, to discover phenotypes of predictive temporal patterns from labeled time-series data. We introduce an efficient representation learning approach in frequency domain that can encode variable-length, irregularly-sampled time-series into a unified representation space, which is then applied to identify various temporal patterns that potentially contribute to the target label using a new notion of path-based similarity. Throughout the experiments on synthetic and real-world datasets, we show that T-Phenotype achieves the best phenotype discovery performance over all the evaluated baselines. We further demonstrate the utility of T-Phenotype by uncovering clinically meaningful patient subgroups characterized by unique temporal patterns.
Improving the Data Efficiency of Multi-Objective Quality-Diversity through Gradient Assistance and Crowding Exploration
Venue: arXiv cs.NE 2023
Year: 2023

Quality-Diversity (QD) algorithms have recently gained traction as optimisation methods due to their effectiveness at escaping local optima and capability of generating wide-ranging and high-performing solutions. Recently, Multi-Objective MAP-Elites (MOME) extended the QD paradigm to the multi-objective setting by maintaining a Pareto front in each cell of a map-elites grid. MOME achieved a global performance that competed with NSGA-II and SPEA2, two well-established Multi-Objective Evolutionary Algorithms (MOEA), while also acquiring a diverse repertoire of solutions. However, MOME is limited by non-directed genetic search mechanisms which struggle in high-dimensional search spaces. In this work, we present Multi-Objective MAP-Elites with Policy-Gradient Assistance and Crowding-based Exploration (MOME-PGX): a new QD algorithm that extends MOME to improve its data efficiency and performance. MOME-PGX uses gradient-based optimisation to efficiently drive solutions towards higher performance. It also introduces crowding-based mechanisms to create an improved exploration strategy and to encourage uniformity across Pareto fronts. We evaluate MOME-PGX in four simulated robot locomotion tasks and demonstrate that it converges faster and to a higher performance than all other baselines. We show that MOME-PGX is between 4.3 and 42 times more data-efficient than MOME and doubles the performance of MOME, NSGA-II and SPEA2 in challenging environments.
Older Adults' Task Preferences for Robot Assistance in the Home
Venue: arXiv cs.RO 2023
Year: 2023

Artificial intelligence technologies that can assist with at-home tasks have the potential to help older adults age in place. Robot assistance in particular has been applied towards physical and cognitive support for older adults living independently at home. Surveys, questionnaires, and group interviews have been used to understand what tasks older adults want robots to assist them with. We build upon prior work exploring older adults' task preferences for robot assistance through field interviews situated within older adults' aging contexts. Our findings support results from prior work indicating older adults' preference for physical assistance over social and care-related support from robots and indicating their preference for control when adopting robot assistance, while highlighting the variety of individual constraints, boundaries, and needs that may influence their preferences.
LightTS: Lightweight Time Series Classification with Adaptive Ensemble Distillation -- Extended Version
Venue: arXiv cs.LG 2023
Year: 2023

Due to the sweeping digitalization of processes, increasingly vast amounts of time series data are being produced. Accurate classification of such time series facilitates decision making in multiple domains. State-of-the-art classification accuracy is often achieved by ensemble learning where results are synthesized from multiple base models. This characteristic implies that ensemble learning needs substantial computing resources, preventing their use in resource-limited environments, such as in edge devices. To extend the applicability of ensemble learning, we propose the LightTS framework that compresses large ensembles into lightweight models while ensuring competitive accuracy. First, we propose adaptive ensemble distillation that assigns adaptive weights to different base models such that their varying classification capabilities contribute purposefully to the training of the lightweight model. Second, we propose means of identifying Pareto optimal settings w.r.t. model accuracy and model size, thus enabling users with a space budget to select the most accurate lightweight model. We report on experiments using 128 real-world time series sets and different types of base models that justify key decisions in the design of LightTS and provide evidence that LightTS is able to outperform competitors.
Enhancing Trace Visualizations for Microservices Performance Analysis
Venue: arXiv cs.SE 2023
Year: 2023

Performance analysis of microservices can be a challenging task, as a typical request to these systems involves multiple Remote Procedure Calls (RPC) spanning across independent services and machines. Practitioners primarily rely on distributed tracing tools to closely monitor microservices performance. These tools enable practitioners to trace, collect, and visualize RPC workflows and associated events in the context of individual end-to-end requests. While effective for analyzing individual end-to-end requests, current distributed tracing visualizations often fall short in providing a comprehensive understanding of the system's overall performance. To address this limitation, we propose a novel visualization approach that enables aggregate performance analysis of multiple end-to-end requests. Our approach builds on a previously developed technique for comparing structural differences of request pairs and extends it for aggregate performance analysis of sets of requests. This paper presents our proposal and discusses our preliminary ongoing progress in developing this innovative approach.
Machine Learning-based Low Overhead Congestion Control Algorithm for Industrial NoCs
Venue: arXiv cs.AR 2023
Year: 2023

Network-on-Chip (NoC) congestion builds up during heavy traffic load and cripples the system performance by stalling the cores. Moreover, congestion leads to wasted link bandwidth due to blocked buffers and bouncing packets. Existing approaches throttle the cores after congestion is detected, reducing efficiency and wasting line bandwidth unnecessarily. In contrast, we propose a lightweight machine learning-based technique that helps predict congestion in the network. Specifically, our proposed technique collects the features related to traffic at each destination. Then, it labels the features using a novel time reversal approach. The labeled data is used to design a low overhead and an explainable decision tree model used at runtime congestion control. Experimental evaluations with synthetic and real traffic on industrial 6$\times$6 NoC show that the proposed approach increases fairness and memory read bandwidth by up to 114\% with respect to existing congestion control technique while incurring less than 0.01\% of overhead.
Set-theoretic Types for Erlang
Venue: arXiv cs.PL 2023
Year: 2023

Erlang is a functional programming language with dynamic typing. The language offers great flexibility for destructing values through pattern matching and dynamic type tests. Erlang also comes with a type language supporting parametric polymorphism, equi-recursive types, as well as union and a limited form of intersection types. However, type signatures only serve as documentation, there is no check that a function body conforms to its signature. Set-theoretic types and semantic subtyping fit Erlang's feature set very well. They allow expressing nearly all constructs of its type language and provide means for statically checking type signatures. This article brings set-theoretic types to Erlang and demonstrates how existing Erlang code can be statically typechecked without or with only minor modifications to the code. Further, the article formalizes the main ingredients of the type system in a small core calculus, reports on an implementation of the system, and compares it with other static typecheckers for Erlang.
The Micro-Paper: Towards cheaper, citable research ideas and conversations
Venue: arXiv cs.DL 2023
Year: 2023

Academic, peer-reviewed short papers are a common way to present a late-breaking work to the academic community that outlines preliminary findings, research ideas, and novel conversations. By comparison, blogging or writing posts on social media are an unstructured and open way to discuss ideas and start new conversations. Both have limitations in the proliferation of research ideas. The short paper format relies on the conference and journal submission process while blogging does not operate within a structured format or set of expectations at all. However, at times the demand exists for late-breaking ideas and conversations to arise in a raw form or with urgency but should still be archived and recorded in a way that promotes citational honesty and integrity. To address this, I present: The Micro-Paper, as a micro-paper itself. The Micro-Paper is a small, cheap, accessible, digital document that is self-published and archived, akin to a pre-print of a short paper. This meta micro-paper discusses the context, goals, and considerations of micro-paper authoring.
RLSS: Real-time, Decentralized, Cooperative, Networkless Multi-Robot Trajectory Planning using Linear Spatial Separations
Venue: arXiv cs.RO 2023
Year: 2023

Trajectory planning for multiple robots in shared environments is a challenging problem especially when there is limited communication available or no central entity. In this article, we present Real-time planning using Linear Spatial Separations, or RLSS: a real-time decentralized trajectory planning algorithm for cooperative multi-robot teams in static environments. The algorithm requires relatively few robot capabilities, namely sensing the positions of robots and obstacles without higher-order derivatives and the ability of distinguishing robots from obstacles. There is no communication requirement and the robots' dynamic limits are taken into account. RLSS generates and solves convex quadratic optimization problems that are kinematically feasible and guarantees collision avoidance if the resulting problems are feasible. We demonstrate the algorithm's performance in real-time in simulations and on physical robots. We compare RLSS to two state-of-the-art planners and show empirically that RLSS does avoid deadlocks and collisions in forest-like and maze-like environments, significantly improving prior work, which result in collisions and deadlocks in such environments.
autofz: Automated Fuzzer Composition at Runtime
Venue: arXiv cs.CR 2023
Year: 2023

Fuzzing has gained in popularity for software vulnerability detection by virtue of the tremendous effort to develop a diverse set of fuzzers. Thanks to various fuzzing techniques, most of the fuzzers have been able to demonstrate great performance on their selected targets. However, paradoxically, this diversity in fuzzers also made it difficult to select fuzzers that are best suitable for complex real-world programs, which we call selection burden. Communities attempted to address this problem by creating a set of standard benchmarks to compare and contrast the performance of fuzzers for a wide range of applications, but the result was always a suboptimal decision - the best-performing fuzzer on average does not guarantee the best outcome for the target of a user's interest. To overcome this problem, we propose an automated, yet non-intrusive meta-fuzzer, called autofz, to maximize the benefits of existing state-of-the-art fuzzers via dynamic composition. To an end user, this means that, instead of spending time on selecting which fuzzer to adopt, one can simply put all of the available fuzzers to autofz, and achieve the best, optimal result. The key idea is to monitor the runtime progress of the fuzzers, called trends (similar in concept to gradient descent), and make a fine-grained adjustment of resource allocation. This is a stark contrast to existing approaches - autofz deduces a suitable set of fuzzers of the active workload in a fine-grained manner at runtime. Our evaluation shows that autofz outperforms any best-performing individual fuzzers in 11 out of 12 available benchmarks and beats the best, collaborative fuzzing approaches in 19 out of 20 benchmarks. Moreover, on average, autofz found 152% more bugs than individual fuzzers, and 415% more bugs than collaborative fuzzing.
NoPPA: Non-Parametric Pairwise Attention Random Walk Model for Sentence Representation
Venue: arXiv cs.CL 2023
Year: 2023

We propose a novel non-parametric/un-trainable language model, named Non-Parametric Pairwise Attention Random Walk Model (NoPPA), to generate sentence embedding only with pre-trained word embedding and pre-counted word frequency. To the best we know, this study is the first successful attempt to break the constraint on bag-of-words assumption with a non-parametric attention mechanism. We evaluate our method on eight different downstream classification tasks. The experiment results show that NoPPA outperforms all kinds of bag-of-words-based methods in each dataset and provides a comparable or better performance than the state-of-the-art non-parametric methods on average. Furthermore, visualization supports that NoPPA can understand contextual topics, common phrases, and word causalities. Our model is available at https://github.com/JacksonWuxs/NoPPA.
Linking Streets in OpenStreetMap to Persons in Wikidata
Venue: arXiv cs.AI 2023
Year: 2023

Geographic web sources such as OpenStreetMap (OSM) and knowledge graphs such as Wikidata are often unconnected. An example connection that can be established between these sources are links between streets in OSM to the persons in Wikidata they were named after. This paper presents StreetToPerson, an approach for connecting streets in OSM to persons in a knowledge graph based on relations in the knowledge graph and spatial dependencies. Our evaluation shows that we outperform existing approaches by 26 percentage points. In addition, we apply StreetToPerson on all OSM streets in Germany, for which we identify more than 180,000 links between streets and persons.
Map-and-Conquer: Energy-Efficient Mapping of Dynamic Neural Nets onto Heterogeneous MPSoCs
Venue: arXiv cs.DC 2023
Year: 2023

Heterogeneous MPSoCs comprise diverse processing units of varying compute capabilities. To date, the mapping strategies of neural networks (NNs) onto such systems are yet to exploit the full potential of processing parallelism, made possible through both the intrinsic NNs' structure and underlying hardware composition. In this paper, we propose a novel framework to effectively map NNs onto heterogeneous MPSoCs in a manner that enables them to leverage the underlying processing concurrency. Specifically, our approach identifies an optimal partitioning scheme of the NN along its `width' dimension, which facilitates deployment of concurrent NN blocks onto different hardware computing units. Additionally, our approach contributes a novel scheme to deploy partitioned NNs onto the MPSoC as dynamic multi-exit networks for additional performance gains. Our experiments on a standard MPSoC platform have yielded dynamic mapping configurations that are 2.1x more energy-efficient than the GPU-only mapping while incurring 1.7x less latency than DLA-only mapping.
TS-Cabinet: Hierarchical Storage for Cloud-Edge-End Time-series Database
Venue: arXiv cs.DB 2023
Year: 2023

Hierarchical data storage is crucial for cloud-edge-end time-series database. Efficient hierarchical storage will directly reduce the storage space of local databases at each side and improve the access hit rate of data. However, no effective hierarchical data management strategy for cloud-edge-end time-series database has been proposed. To solve this problem, this paper proposes TS-Cabinet, a hierarchical storage scheduler for cloud-edge-end time-series database based on workload forecasting. To the best of our knowledge, it is the first work for hierarchical storage of cloud-edge-end time-series database. By building a temperature model, we calculate the current temperature for the timeseries data, and use the workload forecasting model to predict the data's future temperature. Finally, we perform hierarchical storage according to the data migration policy. We validate it on a public dataset, and the experimental results show that our method can achieve about 94% hit rate for data access on the cloud side and edge side, which is 12% better than the existing methods. TS-Cabinet can help cloud-edge-end time-series database avoid the storage overhead caused by storing the full amount of data at all three sides, and greatly reduce the data transfer overhead between each side when collaborative query processing.
A Homotopy Invariant Based on Convex Dissection Topology and a Distance Optimal Path Planning Algorithm
Venue: arXiv cs.RO 2023
Year: 2023

The concept of path homotopy has received widely attention in the field of path planning in recent years. In this article, a homotopy invariant based on convex dissection for a two-dimensional bounded Euclidean space is developed, which can efficiently encode all homotopy path classes between any two points. Thereafter, the optimal path planning task consists of two steps: (i) search for the homotopy path class that may contain the optimal path, and (ii) obtain the shortest homotopy path in this class. Furthermore, an optimal path planning algorithm called CDT-RRT* (Rapidly-exploring Random Tree Star based on Convex Division Topology) is proposed. We designed an efficient sampling formula for CDT-RRT*, which gives it a tendency to actively explore unknown homotopy classes, and incorporated the principles of the Elastic Band algorithm to obtain the shortest path in each class. Through a series of experiments, it was determined that the performance of the proposed algorithm is comparable with state-of-the-art path planning algorithms. Hence, the application significance of the developed homotopy invariant in the field of path planning was verified.