OpenRaiser/Intern-Atlas huggingface dataset:
Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial
Venue: arXiv cs.DS 2021
Year: 2021

We revisit the minimum dominating set problem on graphs with arboricity bounded by $α$. Bansal and Umboh [BU17] gave an $O(α)$-approximation LP rounding algorithm, which also translates into a near-linear time algorithm using general-purpose approximation results for explicit mixed packing and covering or pure covering LPs [KY14, You14, AZO19, Qua10]. Moreover, [BU17] showed that it is NP-hard to achieve an asymptotic improvement for the approximation factor. On the other hand, the previous two non-LP-based algorithms, by Lenzen and Wattenhofer [LW10], and Jones et al. [JLR+13], achieve an approximation factor of $O(α^2)$ in linear time. There is a similar situation in the distributed setting: While there is an $O(\log^2 n)$-round LP-based $O(α)$-approximation algorithm implied in [KMW06], the best non-LP-based algorithm by Lenzen and Wattenhofer [LW10] is an implementation of their centralized algorithm, providing an $O(α^2)$-approximation within $O(\log n)$ rounds. We address the questions of whether one can achieve an $O(α)$-approximation algorithm that is not LP-based, either in the centralized setting or in the distributed setting. We resolve both questions in the affirmative, and en route achieve algorithms that are faster than the state-of-the-art LP-based algorithms. More specifically, our contribution is two-fold: 1. In the centralized setting, we provide a surprisingly simple combinatorial algorithm that is asymptotically optimal in terms of both approximation factor and running time: an $O(α)$-approximation in linear time. 2. Based on our centralized algorithm, we design a distributed combinatorial $O(α)$-approximation algorithm in the CONGEST model that runs in $O(α\log n )$ rounds with high probability.
Essential Characteristics of Approximate matching algorithms: A Survey of Practitioners Opinions and requirement regarding Approximate Matching
Venue: arXiv cs.CY 2021
Year: 2021

Digital forensic investigation has become more challenging due to the rapid growth in the volume of encountered data. It is difficult for an investigator to examine the entire volume of encountered data manually. Approximate Matching algorithms are being used to serve the purpose by automatically filtering correlated and relevant data that an investigator needs to examine manually. Presently there are several prominent approximate matching tools and technique those are being used to assist critical investigation process. However, to measure the guarantees of a tool, it is important to understand the exact requirement of an investigator regarding these algorithms. This paper presents the findings of a closed survey conducted among a highly experienced group of federal state and local law enforcement practitioners and researchers, aimed to understand the practitioner and researcher's opinion regarding approximate matching algorithms. The study provides the baseline attributes of approximate matching tools that a scheme should possess to meet the real requirement of an investigator.
Two-Point Voltage Fingerprinting: Increasing Detectability of ECU Masquerading Attacks
Venue: arXiv cs.CR 2021
Year: 2021

Automotive systems continuously increase their dependency on Electronic Control Units (ECUs) and become more interconnected to improve safety, comfort and Advanced Driving Assistance Systems (ADAS) functions to passengers and drivers. As a consequence of that trend, there is an expanding attack surface which may potentially expose vehicle's critical functions to cyberattacks. It is possible for an adversary to reach the underlying Control Area Network (CAN) through a compromised node or external-facing network interface, and launch masquerading attacks that can compromise road and passenger safety. Due to lack of native authentication in the CAN protocol, an approach to detect masquerading attacks is to use ECU voltage fingerprinting schemes to verify that the messages are sent by authentic ECUs. Though effective against simple masquerading attacks, prior work is unable to detect attackers such as hardware Trojans, which can mimic ECU voltages in addition to spoofing messages. We introduce a novel Two-point ECU Fingerprinting scheme and demonstrate efficacy in a controlled lab setting and on a moving vehicle. Our results show that our proposed two-point fingerprinting scheme is capable of an overall F1-score over 99.4%. The proposed approach raises the bar for attackers trying to compromise automotive security both remotely and physically, therefore improving security and safety of autonomous vehicles.
Analyzing Cross Validation In Compressed Sensing With Mixed Gaussian And Impulse Measurement Noise With L1 Errors
Venue: arXiv cs.IT 2021
Year: 2021

Compressed sensing (CS) involves sampling signals at rates less than their Nyquist rates and attempting to reconstruct them after sample acquisition. Most such algorithms have parameters, for example the regularization parameter in LASSO, which need to be chosen carefully for optimal performance. These parameters can be chosen based on assumptions on the noise level or signal sparsity, but this knowledge may often be unavailable. In such cases, cross validation (CV) can be used to choose these parameters in a purely data-driven fashion. Previous work analysing the use of CV in CS has been based on the $\ell_2$ cross-validation error with Gaussian measurement noise. But it is well known that the $\ell_2$ error is not robust to impulse noise and provides a poor estimate of the recovery error, failing to choose the best parameter. Here we propose using the $\ell_1$ CV error which provides substantial performance benefits given impulse measurement noise. Most importantly, we provide a detailed theoretical analysis and error bounds for the use of $\ell_1$ CV error in CS reconstruction. We show that with high probability, choosing the parameter that yields the minimum $\ell_1$ CV error is equivalent to choosing the minimum recovery error (which is not observable in practice). To our best knowledge, this is the first paper which theoretically analyzes $\ell_1$-based CV in CS.
Quantifying Variational Approximation for the Log-Partition Function
Venue: arXiv cs.DS 2021
Year: 2021

Variational approximation, such as mean-field (MF) and tree-reweighted (TRW), provide a computationally efficient approximation of the log-partition function for a generic graphical model. TRW provably provides an upper bound, but the approximation ratio is generally not quantified. As the primary contribution of this work, we provide an approach to quantify the approximation ratio through the property of the underlying graph structure. Specifically, we argue that (a variant of) TRW produces an estimate that is within factor $\frac{1}{\sqrt{κ(G)}}$ of the true log-partition function for any discrete pairwise graphical model over graph $G$, where $κ(G) \in (0,1]$ captures how far $G$ is from tree structure with $κ(G) = 1$ for trees and $2/N$ for the complete graph over $N$ vertices. As a consequence, the approximation ratio is $1$ for trees, $\sqrt{(d+1)/2}$ for any graph with maximum average degree $d$, and $\stackrel{β\to\infty}{\approx} 1+1/(2β)$ for graphs with girth (shortest cycle) at least $β\log N$. In general, $κ(G)$ is the solution of a max-min problem associated with $G$ that can be evaluated in polynomial time for any graph. Using samples from the uniform distribution over the spanning trees of G, we provide a near linear-time variant that achieves an approximation ratio equal to the inverse of square-root of minimal (across edges) effective resistance of the graph. We connect our results to the graph partition-based approximation method and thus provide a unified perspective. Keywords: variational inference, log-partition function, spanning tree polytope, minimum effective resistance, min-max spanning tree, local inference
Symbol-Level Synchronisation Channel Modelling With Real-World Application: From Davey-Mackay, Fritchman to Markov
Venue: arXiv cs.IT 2021
Year: 2021

Errors in realistic channels contain not only substitution errors, but synchronisation errors as well. Moreover, these errors are rarely statistically independent in nature. By extending on the idea of the Fritchman channel model, a novel error category-based methodology in determining channel characteristics is described for memory channels which contain insertion, deletion, and substitution errors. The practicality of such a methodology is reinforced by making use of real communication data from a visible light communication system. Simulation results show that the error-free and error runs using this new method of defining the channel clearly deviates from the Davey-Mackay synchronisation model which is memoryless in nature. This further emphasises the inherent memory in these synchronisation channels which we are now able to characterise. Additionally, a new method to determine the parameters of a synchronisation memory channel using the Levenshtein distance metric is detailed. This method of channel modelling allows for more realistic communication models to be simulated and can easily extend to other areas of research such as DNA barcoding in the medical domain.
Merly.jl: Web Framework in Julia
Venue: arXiv cs.SE 2021
Year: 2021

Merly.jl is a package for creating web applications in Julia. It presents features such as the creation of endpoints with function notation and with macro notation, handling of static files, use of path parameters, processing of data sent by a web client in the body in a personalized way, handling of CORS and compatibility with the use of middleware. It presents a familiar syntax with the rest of the most popular web frameworks without neglecting the execution performance. This manuscript mentions the operation and main features of Merly.jl
Multilingual Answer Sentence Reranking via Automatically Translated Data
Venue: arXiv cs.CL 2021
Year: 2021

We present a study on the design of multilingual Answer Sentence Selection (AS2) models, which are a core component of modern Question Answering (QA) systems. The main idea is to transfer data, created from one resource rich language, e.g., English, to other languages, less rich in terms of resources. The main findings of this paper are: (i) the training data for AS2 translated into a target language can be used to effectively fine-tune a Transformer-based model for that language; (ii) one multilingual Transformer model it is enough to rank answers in multiple languages; and (iii) mixed-language question/answer pairs can be used to fine-tune models to select answers from any language, where the input question is just in one language. This highly reduces the complexity and technical requirement of a multilingual QA system. Our experiments validate the findings above, showing a modest drop, at most 3%, with respect to the state-of-the-art English model.
On Proximal Policy Optimization's Heavy-tailed Gradients
Venue: arXiv cs.LG 2021
Year: 2021

Modern policy gradient algorithms such as Proximal Policy Optimization (PPO) rely on an arsenal of heuristics, including loss clipping and gradient clipping, to ensure successful learning. These heuristics are reminiscent of techniques from robust statistics, commonly used for estimation in outlier-rich (``heavy-tailed'') regimes. In this paper, we present a detailed empirical study to characterize the heavy-tailed nature of the gradients of the PPO surrogate reward function. We demonstrate that the gradients, especially for the actor network, exhibit pronounced heavy-tailedness and that it increases as the agent's policy diverges from the behavioral policy (i.e., as the agent goes further off policy). Further examination implicates the likelihood ratios and advantages in the surrogate reward as the main sources of the observed heavy-tailedness. We then highlight issues arising due to the heavy-tailed nature of the gradients. In this light, we study the effects of the standard PPO clipping heuristics, demonstrating that these tricks primarily serve to offset heavy-tailedness in gradients. Thus motivated, we propose incorporating GMOM, a high-dimensional robust estimator, into PPO as a substitute for three clipping tricks. Despite requiring less hyperparameter tuning, our method matches the performance of PPO (with all heuristics enabled) on a battery of MuJoCo continuous control tasks.
Millimeter-wave and Terahertz Spectrum for 6G Wireless
Venue: arXiv cs.IT 2021
Year: 2021

With the standardization of 5G, commercial millimeter wave (mmWave) communications has become a reality despite all the concerns about the unfavorable propagation characteristics of these frequencies. Even though the 5G systems are still being rolled out, it is argued that their gigabits per second rates may fall short in supporting many emerging applications, such as 3D gaming and extended reality. Such applications will require several hundreds of gigabits per second to several terabits per second data rates with low latency and high reliability, which are expected to be the design goals of the next generation 6G communications systems. Given the potential of terahertz (THz) communications systems to provide such data rates over short distances, they are widely regarded to be the next frontier for the wireless communications research. The primary goal of this chapter is to equip readers with sufficient background about the mmWave and THz bands so that they are able to both appreciate the necessity of using these bands for commercial communications in the current wireless landscape and to reason the key design considerations for the communications systems operating in these bands. Towards this goal, this chapter provides a unified treatment of these bands with particular emphasis on their propagation characteristics, channel models, design and implementation considerations, and potential applications to 6G wireless. A brief summary of the current standardization activities related to the use of these bands for commercial communications applications is also provided.
Artificial Intelligence Enhanced Rapid and Efficient Diagnosis of Mycoplasma Pneumoniae Pneumonia in Children Patients
Venue: arXiv cs.LG 2021
Year: 2021

Artificial intelligence methods have been increasingly turning into a potentially powerful tool in the diagnosis and management of diseases. In this study, we utilized logistic regression (LR), decision tree (DT), gradient boosted decision tree (GBDT), support vector machine (SVM), and multilayer perceptron (MLP) as machine learning models to rapidly diagnose the mycoplasma pneumoniae pneumonia (MPP) in children patients. The classification task was carried out after applying the preprocessing procedure to the MPP dataset. The most efficient results are obtained by GBDT. It provides the best performance with an accuracy of 93.7%. In contrast to standard raw feature weighting, the feature importance takes the underlying correlation structure of the features into account. The most crucial feature of GBDT is the "pulmonary infiltrates range" with a score of 0.5925, followed by "cough" (0.0953) and "pleural effusion" (0.0492). We publicly share our full implementation with the dataset and trained models at https://github.com/zhenguonie/2021_AI4MPP.
On guarding polygons with holes
Venue: arXiv cs.CG 2021
Year: 2021

There is an old conjecture by Shermer \cite{sher} that in a polygon with $n$ vertices and $h$ holes, $\lfloor \dfrac{n+h}{3} \rfloor$ vertex guards are sufficient to guard the entire polygon. The conjecture is proved for $h=1$ by Shermer \cite{sher} and Aggarwal \cite{aga} seperately. In this paper, we prove a theorem similar to the Shermer's conjecture for a special case where the goal is to guard the vertices of the polygon (not the entire polygon) which is equivalent to finding a dominating set for the visibility graph of the polygon. Our proof also guarantees that the selected vertex guards also cover the entire outer boundary (outer perimeter of the polygon) as well.
Stability and Resilience of Distributed Information Spreading in Aggregate Computing
Venue: arXiv cs.DC 2021
Year: 2021

Spreading information through a network of devices is a core activity for most distributed systems. As such, self-stabilizing algorithms implementing information spreading are one of the key building blocks enabling aggregate computing to provide resilient coordination in open complex distributed systems. This paper improves a general spreading block in the aggregate computing literature by making it resilient to network perturbations, establishes its global uniform asymptotic stability and proves that it is ultimately bounded under persistent disturbances. The ultimate bounds depend only on the magnitude of the largest perturbation and the network diameter, and three design parameters trade off competing aspects of performance. For example, as in many dynamical systems, values leading to greater resilience to network perturbations slow convergence and vice versa.
Exploring Knowledge Distillation of a Deep Neural Network for Multi-Script identification
Venue: arXiv cs.CV 2021
Year: 2021

Multi-lingual script identification is a difficult task consisting of different language with complex backgrounds in scene text images. According to the current research scenario, deep neural networks are employed as teacher models to train a smaller student network by utilizing the teacher model's predictions. This process is known as dark knowledge transfer. It has been quite successful in many domains where the final result obtained is unachievable through directly training the student network with a simple architecture. In this paper, we explore dark knowledge transfer approach using long short-term memory(LSTM) and CNN based assistant model and various deep neural networks as the teacher model, with a simple CNN based student network, in this domain of multi-script identification from natural scene text images. We explore the performance of different teacher models and their ability to transfer knowledge to a student network. Although the small student network's limited size, our approach obtains satisfactory results on a well-known script identification dataset CVSI-2015.
How To Train Your HERON
Venue: arXiv cs.RO 2021
Year: 2021

In this paper we apply Deep Reinforcement Learning (Deep RL) and Domain Randomization to solve a navigation task in a natural environment relying solely on a 2D laser scanner. We train a model-based RL agent in simulation to follow lake and river shores and apply it on a real Unmanned Surface Vehicle in a zero-shot setup. We demonstrate that even though the agent has not been trained in the real world, it can fulfill its task successfully and adapt to changes in the robot's environment and dynamics. Finally, we show that the RL agent is more robust, faster, and more accurate than a state-aware Model-Predictive-Controller.
CellTrack R-CNN: A Novel End-To-End Deep Neural Network for Cell Segmentation and Tracking in Microscopy Images
Venue: arXiv cs.CV 2021
Year: 2021

Cell segmentation and tracking in microscopy images are of great significance to new discoveries in biology and medicine. In this study, we propose a novel approach to combine cell segmentation and cell tracking into a unified end-to-end deep learning based framework, where cell detection and segmentation are performed with a current instance segmentation pipeline and cell tracking is implemented by integrating Siamese Network with the pipeline. Besides, tracking performance is improved by incorporating spatial information into the network and fusing spatial and visual prediction. Our approach was evaluated on the DeepCell benchmark dataset. Despite being simple and efficient, our method outperforms state-of-the-art algorithms in terms of both cell segmentation and cell tracking accuracies.
Raising Security Awareness using Cybersecurity Challenges in Embedded Programming Courses
Venue: arXiv cs.SE 2021
Year: 2021

Security bugs are errors in code that, when exploited, can lead to serious software vulnerabilities. These bugs could allow an attacker to take over an application and steal information. One of the ways to address this issue is by means of awareness training. The Sifu platform was developed in the industry, for the industry, with the aim to raise software developers' awareness of secure coding. This paper extends the Sifu platform with three challenges that specifically address embedded programming courses, and describes how to implement these challenges, while also evaluating the usefulness of these challenges to raise security awareness in an academic setting. Our work presents technical details on the detection mechanisms for software vulnerabilities and gives practical advice on how to implement them. The evaluation of the challenges is performed through two trial runs with a total of 16 participants. Our preliminary results show that the challenges are suitable for academia, and can even potentially be included in official teaching curricula. One major finding is an indicator of the lack of awareness of secure coding by undergraduates. Finally, we compare our results with previous work done in the industry and extract advice for practitioners.
Unsupervised Medical Image Alignment with Curriculum Learning
Venue: arXiv cs.CV 2021
Year: 2021

We explore different curriculum learning methods for training convolutional neural networks on the task of deformable pairwise 3D medical image registration. To the best of our knowledge, we are the first to attempt to improve performance by training medical image registration models using curriculum learning, starting from an easy training setup in the first training stages, and gradually increasing the complexity of the setup. On the one hand, we consider two existing curriculum learning approaches, namely curriculum dropout and curriculum by smoothing. On the other hand, we propose a novel and simple strategy to achieve curriculum, namely to use purposely blurred images at the beginning, then gradually transit to sharper images in the later training stages. Our experiments with an underlying state-of-the-art deep learning model show that curriculum learning can lead to superior results compared to conventional training. Additionally, we show that curriculum by input blur has the best accuracy versus speed trade-off among the compared curriculum learning approaches.
Customized Slicing for 6G: Enforcing Artificial Intelligence on Resource Management
Venue: arXiv cs.NI 2021
Year: 2021

Next generation wireless networks are expected to support diverse vertical industries and offer countless emerging use cases. To satisfy stringent requirements of diversified services, network slicing is developed, which enables service-oriented resource allocation by tailoring the infrastructure network into multiple logical networks. However, there are still some challenges in cross-domain multi-dimensional resource management for end-to-end (E2E) slices under the dynamic and uncertain environment. Trading off the revenue and cost of resource allocation while guaranteeing service quality is significant to tenants. Therefore, this article introduces a hierarchical resource management framework, utilizing deep reinforcement learning in admission control of resource requests from different tenants and resource adjustment within admitted slices for each tenant. Particularly, we first discuss the challenges in customized resource management of 6G. Second, the motivation and background are presented to explain why artificial intelligence (AI) is applied in resource customization of multi-tenant slicing. Third, E2E resource management is decomposed into two problems, multi-dimensional resource allocation decision based on slice-level feedback and real-time slice adaption aimed at avoiding service quality degradation. Simulation results demonstrate the effectiveness of AI-based customized slicing. Finally, several significant challenges that need to be addressed in practical implementation are investigated.