OpenRaiser/Intern-Atlas huggingface dataset:
Moving Target Interception Considering Dynamic Environment
Venue: arXiv cs.RO 2022
Year: 2022

The interception of moving targets is a widely studied issue. In this paper, we propose an algorithm of intercepting the moving target with a wheeled mobile robot in a dynamic environment. We first predict the future position of the target through polynomial fitting. The algorithm then generates an interception trajectory with path and speed decoupling. We use Hybrid A* search to plan a path and optimize it via gradient decent method. To avoid the dynamic obstacles in the environment, we introduce ST graph for speed planning. The speed curve is represented by piecewise Bézier curves for further optimization. Compared with other interception algorithms, we consider a dynamic environment and plan a safety trajectory which satisfies the kinematic characteristics of the wheeled robot while ensuring the accuracy of interception. Simulation illustrates that the algorithm successfully achieves the interception tasks and has high computational efficiency.
Average-Case Hardness of Proving Tautologies and Theorems
Venue: arXiv cs.CC 2022
Year: 2022

We consolidate two widely believed conjectures about tautologies -- no optimal proof system exists, and most require superpolynomial size proofs in any system -- into a $p$-isomorphism-invariant condition satisfied by all paddable $\textbf{coNP}$-complete languages or none. The condition is: for any Turing machine (TM) $M$ accepting the language, $\textbf{P}$-uniform input families requiring superpolynomial time by $M$ exist (equivalent to the first conjecture) and appear with positive upper density in an enumeration of input families (implies the second). In that case, no such language is easy on average (in $\textbf{AvgP}$) for a distribution applying non-negligible weight to the hard families. The hardness of proving tautologies and theorems is likely related. Motivated by the fact that arithmetic sentences encoding "string $x$ is Kolmogorov random" are true but unprovable with positive density in a finitely axiomatized theory $\mathcal{T}$ (Calude and J{ü}rgensen), we conjecture that any propositional proof system requires superpolynomial size proofs for a dense set of $\textbf{P}$-uniform families of tautologies encoding "there is no $\mathcal{T}$ proof of size $\leq t$ showing that string $x$ is Kolmogorov random". This implies the above condition. The conjecture suggests that there is no optimal proof system because undecidable theories help prove tautologies and do so more efficiently as axioms are added, and that constructing hard tautologies seems difficult because it is impossible to construct Kolmogorov random strings. Similar conjectures that computational blind spots are manifestations of noncomputability would resolve other open problems.
GraphHD: Efficient graph classification using hyperdimensional computing
Venue: arXiv cs.LG 2022
Year: 2022

Hyperdimensional Computing (HDC) developed by Kanerva is a computational model for machine learning inspired by neuroscience. HDC exploits characteristics of biological neural systems such as high-dimensionality, randomness and a holographic representation of information to achieve a good balance between accuracy, efficiency and robustness. HDC models have already been proven to be useful in different learning applications, especially in resource-limited settings such as the increasingly popular Internet of Things (IoT). One class of learning tasks that is missing from the current body of work on HDC is graph classification. Graphs are among the most important forms of information representation, yet, to this day, HDC algorithms have not been applied to the graph learning problem in a general sense. Moreover, graph learning in IoT and sensor networks, with limited compute capabilities, introduce challenges to the overall design methodology. In this paper, we present GraphHD$-$a baseline approach for graph classification with HDC. We evaluate GraphHD on real-world graph classification problems. Our results show that when compared to the state-of-the-art Graph Neural Networks (GNNs) the proposed model achieves comparable accuracy, while training and inference times are on average 14.6$\times$ and 2.0$\times$ faster, respectively.
Federated Anomaly Detection over Distributed Data Streams
Venue: arXiv cs.LG 2022
Year: 2022

Sharing of telecommunication network data, for example, even at high aggregation levels, is nowadays highly restricted due to privacy legislation and regulations and other important ethical concerns. It leads to scattering data across institutions, regions, and states, inhibiting the usage of AI methods that could otherwise take advantage of data at scale. It creates the need to build a platform to control such data, build models or perform calculations. In this work, we propose an approach to building the bridge among anomaly detection, federated learning, and data streams. The overarching goal of the work is to detect anomalies in a federated environment over distributed data streams. This work complements the state-of-the-art by adapting the data stream algorithms in a federated learning setting for anomaly detection and by delivering a robust framework and demonstrating the practical feasibility in a real-world distributed deployment scenario.
Loss Landscape Engineering via Data Regulation on PINNs
Venue: arXiv cs.LG 2022
Year: 2022

Physics-Informed Neural Networks have shown unique utility in parameterising the solution of a well-defined partial differential equation using automatic differentiation and residual losses. Though they provide theoretical guarantees of convergence, in practice the required training regimes tend to be exacting and demanding. Through the course of this paper, we take a deep dive into understanding the loss landscapes associated with a PINN and how that offers some insight as to why PINNs are fundamentally hard to optimise for. We demonstrate how PINNs can be forced to converge better towards the solution, by way of feeding in sparse or coarse data as a regulator. The data regulates and morphs the topology of the loss landscape associated with the PINN to make it easily traversable for the minimiser. Data regulation of PINNs helps ease the optimisation required for convergence by invoking a hybrid unsupervised-supervised training approach, where the labelled data pushes the network towards the vicinity of the solution, and the unlabelled regime fine-tunes it to the solution.
AdaCap: Adaptive Capacity control for Feed-Forward Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

The capacity of a ML model refers to the range of functions this model can approximate. It impacts both the complexity of the patterns a model can learn but also memorization, the ability of a model to fit arbitrary labels. We propose Adaptive Capacity (AdaCap), a training scheme for Feed-Forward Neural Networks (FFNN). AdaCap optimizes the capacity of FFNN so it can capture the high-level abstract representations underlying the problem at hand without memorizing the training dataset. AdaCap is the combination of two novel ingredients, the Muddling labels for Regularization (MLR) loss and the Tikhonov operator training scheme. The MLR loss leverages randomly generated labels to quantify the propensity of a model to memorize. We prove that the MLR loss is an accurate in-sample estimator for out-of-sample generalization performance and that it can be used to perform Hyper-Parameter Optimization provided a Signal-to-Noise Ratio condition is met. The Tikhonov operator training scheme modulates the capacity of a FFNN in an adaptive, differentiable and data-dependent manner. We assess the effectiveness of AdaCap in a setting where DNN are typically prone to memorization, small tabular datasets, and benchmark its performance against popular machine learning methods.
Privacy Enhancement for Cloud-Based Few-Shot Learning
Venue: arXiv cs.LG 2022
Year: 2022

Requiring less data for accurate models, few-shot learning has shown robustness and generality in many application domains. However, deploying few-shot models in untrusted environments may inflict privacy concerns, e.g., attacks or adversaries that may breach the privacy of user-supplied data. This paper studies the privacy enhancement for the few-shot learning in an untrusted environment, e.g., the cloud, by establishing a novel privacy-preserved embedding space that preserves the privacy of data and maintains the accuracy of the model. We examine the impact of various image privacy methods such as blurring, pixelization, Gaussian noise, and differentially private pixelization (DP-Pix) on few-shot image classification and propose a method that learns privacy-preserved representation through the joint loss. The empirical results show how privacy-performance trade-off can be negotiated for privacy-enhanced few-shot learning.
Design and Implement an Enhanced Simulator for Autonomous Delivery Robot
Venue: arXiv cs.RO 2022
Year: 2022

As autonomous driving technology is getting more and more mature today, autonomous delivery companies like Starship, Marble, and Nuro has been making progress in the tests of their autonomous delivery robots. While simulations and simulators are very important for the final product landing of the autonomous delivery robots since the autonomous delivery robots need to navigate on the sidewalk, campus, and other urban scenarios, where the simulations can avoid real damage to pedestrians and properties in the real world caused by any algorithm failures and programming errors and thus accelerate the whole developing procedure and cut down the cost. In this case, this study proposes an open-source simulator based on our autonomous delivery robot ZebraT to accelerate the research on autonomous delivery. The simulator developing procedure is illustrated step by step. What is more, the applications on the simulator that we are working on are also introduced, which includes autonomous navigation in the simulated urban environment, cooperation between an autonomous vehicle and an autonomous delivery robot, and reinforcement learning practice on the task training in the simulator. We have published the proposed simulator in Github.
Expert Systems with Logic#. A Novel Modeling Framework for Logic Programming in an Object-Oriented Context of C#
Venue: arXiv cs.AI 2022
Year: 2022

We present a novel approach how logic programming for expert systems can be declared directly in an object-oriented language.
Lost in Compression: the Impact of Lossy Image Compression on Variable Size Object Detection within Infrared Imagery
Venue: arXiv cs.CV 2022
Year: 2022

Lossy image compression strategies allow for more efficient storage and transmission of data by encoding data to a reduced form. This is essential enable training with larger datasets on less storage-equipped environments. However, such compression can cause severe decline in performance of deep Convolution Neural Network (CNN) architectures even when mild compression is applied and the resulting compressed imagery is visually identical. In this work, we apply the lossy JPEG compression method with six discrete levels of increasing compression {95, 75, 50, 15, 10, 5} to infrared band (thermal) imagery. Our study quantitatively evaluates the affect that increasing levels of lossy compression has upon the performance of characteristically diverse object detection architectures (Cascade-RCNN, FSAF and Deformable DETR) with respect to varying sizes of objects present in the dataset. When training and evaluating on uncompressed data as a baseline, we achieve maximal mean Average Precision (mAP) of 0.823 with Cascade R-CNN across the FLIR dataset, outperforming prior work. The impact of the lossy compression is more extreme at higher compression levels (15, 10, 5) across all three CNN architectures. However, re-training models on lossy compressed imagery notably ameliorated performances for all three CNN models with an average increment of ~76% (at higher compression level 5). Additionally, we demonstrate the relative sensitivity of differing object areas {tiny, small, medium, large} with respect to the compression level. We show that tiny and small objects are more sensitive to compression than medium and large objects. Overall, Cascade R-CNN attains the maximal mAP across most of the object area categories.
A Survey on Semantics in Automated Data Science
Venue: arXiv cs.AI 2022
Year: 2022

Data Scientists leverage common sense reasoning and domain knowledge to understand and enrich data for building predictive models. In recent years, we have witnessed a surge in tools and techniques for {\em automated machine learning}. While data scientists can employ various such tools to help with model building, many other aspects such as {\em feature engineering} that require semantic understanding of concepts, remain manual to a large extent. In this paper we discuss important shortcomings of current automated data science solutions and machine learning. We discuss how leveraging basic semantic reasoning on data in combination with novel tools for data science automation can help with consistent and explainable data augmentation and transformation. Moreover, semantics can assist data scientists in a new manner by helping with challenges related to {\em trust}, {\em bias}, and {\em explainability}.
Partial Product Aware Machine Learning on DNA-Encoded Libraries
Venue: arXiv cs.LG 2022
Year: 2022

DNA encoded libraries (DELs) are used for rapid large-scale screening of small molecules against a protein target. These combinatorial libraries are built through several cycles of chemistry and DNA ligation, producing large sets of DNA-tagged molecules. Training machine learning models on DEL data has been shown to be effective at predicting molecules of interest dissimilar from those in the original DEL. Machine learning chemical property prediction approaches rely on the assumption that the property of interest is linked to a single chemical structure. In the context of DNA-encoded libraries, this is equivalent to assuming that every chemical reaction fully yields the desired product. However, in practice, multi-step chemical synthesis sometimes generates partial molecules. Each unique DNA tag in a DEL therefore corresponds to a set of possible molecules. Here, we leverage reaction yield data to enumerate the set of possible molecules corresponding to a given DNA tag. This paper demonstrates that training a custom GNN on this richer dataset improves accuracy and generalization performance.
The Hamiltonian Path Graph is Connected for Simple $s,t$ Paths in Rectangular Grid Graphs
Venue: arXiv cs.DM 2022
Year: 2022

A \emph{simple} $s,t$ path $P$ in a rectangular grid graph $\mathbb{G}$ is a Hamiltonian path from the top-left corner $s$ to the bottom-right corner $t$ such that each \emph{internal} subpath of $P$ with both endpoints $a$ and $b$ on the boundary of $\mathbb{G}$ has the minimum number of bends needed to travel from $a$ to $b$ (i.e., $0$, $1$, or $2$ bends, depending on whether $a$ and $b$ are on opposite, adjacent, or the same side of the bounding rectangle). Here, we show that $P$ can be reconfigured to any other simple $s,t$ path of $\mathbb{G}$ by \emph{switching $2\times 2$ squares}, where at most ${5}|\mathbb{G}|/{4}$ such operations are required. Furthermore, each \emph{square-switch} is done in $O(1)$ time and keeps the resulting path in the same family of simple $s,t$ paths. Our reconfiguration result proves that the \emph{Hamiltonian path graph} $\cal{G}$ for simple $s,t$ paths is connected and has diameter at most ${5}|\mathbb{G}|/{4}$ which is asymptotically tight.
Browser-based Hyperbolic Visualization of Graphs
Venue: arXiv cs.GR 2022
Year: 2022

Hyperbolic geometry offers a natural focus + context for data visualization and has been shown to underlie real-world complex networks. However, current hyperbolic network visualization approaches are limited to special types of networks and do not scale to large datasets. With this in mind, we designed, implemented, and analyzed three methods for hyperbolic visualization of networks in the browser based on inverse projections, generalized force-directed algorithms, and hyperbolic multi-dimensional scaling (H-MDS). A comparison with Euclidean MDS shows that H-MDS produces embeddings with lower distortion for several types of networks. All three methods can handle node-link representations and are available in fully functional web-based systems.
Shape complexity in cluster analysis
Venue: arXiv cs.LG 2022
Year: 2022

In cluster analysis, a common first step is to scale the data aiming to better partition them into clusters. Even though many different techniques have throughout many years been introduced to this end, it is probably fair to say that the workhorse in this preprocessing phase has been to divide the data by the standard deviation along each dimension. Like division by the standard deviation, the great majority of scaling techniques can be said to have roots in some sort of statistical take on the data. Here we explore the use of multidimensional shapes of data, aiming to obtain scaling factors for use prior to clustering by some method, like k-means, that makes explicit use of distances between samples. We borrow from the field of cosmology and related areas the recently introduced notion of shape complexity, which in the variant we use is a relatively simple, data-dependent nonlinear function that we show can be used to help with the determination of appropriate scaling factors. Focusing on what might be called "midrange" distances, we formulate a constrained nonlinear programming problem and use it to produce candidate scaling-factor sets that can be sifted on the basis of further considerations of the data, say via expert knowledge. We give results on some iconic data sets, highlighting the strengths and potential weaknesses of the new approach. These results are generally positive across all the data sets used.
A Survey on Machine Learning for Geo-Distributed Cloud Data Center Management
Venue: arXiv cs.DC 2022
Year: 2022

Cloud workloads today are typically managed in a distributed environment and processed across geographically distributed data centers. Cloud service providers have been distributing data centers globally to reduce operating costs while also improving quality of service by using intelligent workload and resource management strategies. Such large scale and complex orchestration of software workload and hardware resources remains a difficult problem to solve efficiently. Researchers and practitioners have been trying to address this problem by proposing a variety of cloud management techniques. Mathematical optimization techniques have historically been used to address cloud management issues. But these techniques are difficult to scale to geo-distributed problem sizes and have limited applicability in dynamic heterogeneous system environments, forcing cloud service providers to explore intelligent data-driven and Machine Learning (ML) based alternatives. The characterization, prediction, control, and optimization of complex, heterogeneous, and ever-changing distributed cloud resources and workloads employing ML methodologies have received much attention in recent years. In this article, we review the state-of-the-art ML techniques for the cloud data center management problem. We examine the challenges and the issues in current research focused on ML for cloud management and explore strategies for addressing these issues. We also discuss advantages and disadvantages of ML techniques presented in the recent literature and make recommendations for future research directions.
Reasoning About Vectors using an SMT Theory of Sequences
Venue: arXiv cs.LO 2022
Year: 2022

Dynamic arrays, also referred to as vectors, are fundamental data structures used in many programs. Modeling their semantics efficiently is crucial when reasoning about such programs. The theory of arrays is widely supported but is not ideal, because the number of elements is fixed (determined by its index sort) and cannot be adjusted, which is a problem, given that the length of vectors often plays an important role when reasoning about vector programs. In this paper, we propose reasoning about vectors using a theory of sequences. We introduce the theory, propose a basic calculus adapted from one for the theory of strings, and extend it to efficiently handle common vector operations. We prove that our calculus is sound and show how to construct a model when it terminates with a saturated configuration. Finally, we describe an implementation of the calculus in cvc5 and demonstrate its efficacy by evaluating it on verification conditions for smart contracts and benchmarks derived from existing array benchmarks.
Deterministic 3-Server on a Circle and the Limitation of Canonical Potentials
Venue: arXiv cs.DS 2022
Year: 2022

The deterministic $k$-server conjecture states that there is a $k$-competitive deterministic algorithm for the $k$-server problem for any metric space. We show that the work function algorithm is $3$-competitive for the $3$-server problem on circle metrics, a case left open by Coester and Koutsoupias (2021). Our analysis follows the existing framework but introduces a new potential function which may be viewed as a relaxation of the counterpart by Coester and Koutsoupias (2021). We further notice that the new potential function and many existing ones can be rewritten in a canonical form. Through a computer-aided verification, however, we find that no such canonical potential function can resolve the deterministic $3$-server conjecture for general metric spaces under the current analysis framework.
On the Use of Refactoring in Security Vulnerability Fixes: An Exploratory Study on Maven Libraries
Venue: arXiv cs.SE 2022
Year: 2022

Third-party library dependencies are commonplace in today's software development. With the growing threat of security vulnerabilities, applying security fixes in a timely manner is important to protect software systems. As such, the community developed a list of software and hardware weakness known as Common Weakness Enumeration (CWE) to assess vulnerabilities. Prior work has revealed that maintenance activities such as refactoring code potentially correlate with security-related aspects in the source code. In this work, we explore the relationship between refactoring and security by analyzing refactoring actions performed jointly with vulnerability fixes in practice. We conducted a case study to analyze 143 maven libraries in which 351 known vulnerabilities had been detected and fixed. Surprisingly, our exploratory results show that developers incorporate refactoring operations in their fixes, with 31.9% (112 out of 351) of the vulnerabilities paired with refactoring actions. We envision this short paper to open up potential new directions to motivate automated tool support, allowing developers to deliver fixes faster, while maintaining their code.
Design of Joint Source-Channel Codes Based on a Generic Protograph
Venue: arXiv cs.IT 2022
Year: 2022

In this paper, we propose using a generic protograph to design joint source-channel codes (JSCCs). We present a generalized algorithm, called protograph extrinsic information transfer for JSCC algorithm (PEXIT-JSCC algorithm), for analyzing the channel threshold of the proposed JSCC. We also propose a source generic protograph EXIT (SGP-EXIT) algorithm, which is more appropriate than the generalized source protograph extrinsic information transfer (GSP-EXIT) algorithm, for evaluating the source threshold of a generic protograph. Moreover, a collaborative optimization method based on the SGP-EXIT and PEXIT-JSCC algorithms is proposed to construct generic-protograph JSCCs with good source and channel thresholds. Finally, we construct generic-protograph JSCCs, analyze their decoding thresholds, and compare their theoretical and error performance with JSCC systems based on optimized double-protographs. Results show that our proposed codes can attain channel thresholds within 1 dB from the Shannon limit and outperform double-protograph-based JSCCs.