OpenRaiser/Intern-Atlas huggingface dataset:
Real-Time Object Detection and Localization in Compressive Sensed Video on Embedded Hardware
Venue: arXiv cs.CV 2021
Year: 2021

Every day around the world, interminable terabytes of data are being captured for surveillance purposes. A typical 1-2MP CCTV camera generates around 7-12GB of data per day. Frame-by-frame processing of such enormous amount of data requires hefty computational resources. In recent years, compressive sensing approaches have shown impressive results in signal processing by reducing the sampling bandwidth. Different sampling mechanisms were developed to incorporate compressive sensing in image and video acquisition. Pixel-wise coded exposure is one among the promising sensing paradigms for capturing videos in the compressed domain, which was also realized into an all-CMOS sensor \cite{Xiong2017}. Though cameras that perform compressive sensing save a lot of bandwidth at the time of sampling and minimize the memory required to store videos, we cannot do much in terms of processing until the videos are reconstructed to the original frames. But, the reconstruction of compressive-sensed (CS) videos still takes a lot of time and is also computationally expensive. In this work, we show that object detection and localization can be possible directly on the CS frames (easily upto 20x compression). To our knowledge, this is the first time that the problem of object detection and localization on CS frames has been attempted. Hence, we also created a dataset for training in the CS domain. We were able to achieve a good accuracy of 46.27\% mAP(Mean Average Precision) with the proposed model with an inference time of 23ms directly on the compressed frames(approx. 20 original domain frames), this facilitated for real-time inference which was verified on NVIDIA TX2 embedded board. Our framework will significantly reduce the communication bandwidth, and thus reduction in power as the video compression will be done at the image sensor processing core.
On the algebraic structure of quasi group codes
Venue: arXiv cs.IT 2021
Year: 2021

In this note, an intrinsic description of some families of linear codes with symmetries is given, showing that they can be described more generally as quasi group codes, that is, as linear codes allowing a group of permutation automorphisms which acts freely on the set of coordinates. An algebraic description, including the concatenated structure, of such codes is presented. This allows to construct quasi group codes from codes over rings, and vice versa. The last part of the paper is dedicated to the investigation of self-duality of quasi group codes.
Benchmarking Discrete Optimization Heuristics with IOHprofiler
Venue: arXiv cs.NE 2021
Year: 2021

Automated benchmarking environments aim to support researchers in understanding how different algorithms perform on different types of optimization problems. Such comparisons provide insights into the strengths and weaknesses of different approaches, which can be leveraged into designing new algorithms and into the automation of algorithm selection and configuration. With the ultimate goal to create a meaningful benchmark set for iterative optimization heuristics, we have recently released IOHprofiler, a software built to create detailed performance comparisons between iterative optimization heuristics. With this present work we demonstrate that IOHprofiler provides a suitable environment for automated benchmarking. We compile and assess a selection of 23 discrete optimization problems that subscribe to different types of fitness landscapes. For each selected problem we compare performances of twelve different heuristics, which are as of now available as baseline algorithms in IOHprofiler. We also provide a new module for IOHprofiler which extents the fixed-target and fixed-budget results for the individual problems by ECDF results, which allows one to derive aggregated performance statistics for groups of problems.
MG-WFBP: Merging Gradients Wisely for Efficient Communication in Distributed Deep Learning
Venue: arXiv cs.DC 2021
Year: 2021

Distributed synchronous stochastic gradient descent has been widely used to train deep neural networks (DNNs) on computer clusters. With the increase of computational power, network communications generally limit the system scalability. Wait-free backpropagation (WFBP) is a popular solution to overlap communications with computations during the training process. In this paper, we observe that many DNNs have a large number of layers with only a small amount of data to be communicated at each layer in distributed training, which could make WFBP inefficient. Based on the fact that merging some short communication tasks into a single one can reduce the overall communication time, we formulate an optimization problem to minimize the training time in pipelining communications and computations. We derive an optimal solution that can be solved efficiently without affecting the training performance. We then apply the solution to propose a distributed training algorithm named merged-gradient WFBP (MG-WFBP) and implement it in two platforms Caffe and PyTorch. Extensive experiments in three GPU clusters are conducted to verify the effectiveness of MG-WFBP. We further exploit trace-based simulations of 4 to 2048 GPUs to explore the potential scaling efficiency of MG-WFBP. Experimental results show that MG-WFBP achieves much better scaling performance than existing methods.
Traffic-aware Gateway Placement for High-capacity Flying Networks
Venue: arXiv cs.NI 2021
Year: 2021

The ability to operate virtually anywhere and carry payload makes Unmanned Aerial Vehicles (UAVs) perfect platforms to carry communications nodes, including Wi-Fi Access Points (APs) and cellular Base Stations (BSs). This is paving the way to the deployment of flying networks that enable communications to ground users on demand. Still, flying networks impose significant challenges in order to meet the Quality of Experience expectations. State of the art works addressed these challenges, but have been focused on routing and the placement of the UAVs as APs and BSs serving the ground users, overlooking the backhaul network design. The main contribution of this paper is a centralized traffic-aware Gateway UAV Placement (GWP) algorithm for flying networks with controlled topology. GWP takes advantage of the knowledge of the offered traffic and the future topologies of the flying network to enable backhaul communications paths with high enough capacity. The performance achieved using the GWP algorithm is evaluated using ns-3 simulations. The obtained results demonstrate significant gains regarding aggregate throughput and delay.
Stubborn Set Reduction for Two-Player Reachability Games
Venue: arXiv cs.LO 2021
Year: 2021

Partial order reductions have been successfully applied to model checking of concurrent systems and practical applications of the technique show nontrivial reduction in the size of the explored state space. We present a theory of partial order reduction based on stubborn sets in the game-theoretical setting of 2-player games with reachability objectives. Our stubborn reduction allows us to prune the interleaving behaviour of both players in the game, and we formally prove its correctness on the class of games played on general labelled transition systems. We then instantiate the framework to the class of weighted Petri net games with inhibitor arcs and provide its efficient implementation in the model checker TAPAAL. Finally, we evaluate our stubborn reduction on several case studies and demonstrate its efficiency.
A Swiss Army Knife for Dynamic Caching in Small Cell Networks
Venue: arXiv cs.NI 2021
Year: 2021

We consider a dense cellular network, in which a limited-size cache is available at every base station (BS). Coordinating content allocation across the different caches can lead to significant performance gains, but is a difficult problem even when full information about the network and the request process is available. In this paper we present qLRU-$Δ$, a general-purpose dynamic caching policy that can be tailored to optimize different performance metrics also in presence of coordinated multipoint transmission techniques. The policy requires neither direct communication among BSs, nor a priori knowledge of content popularity and, under stationary request processes, has provable performance guarantees.
Learning Variable Ordering Heuristics for Solving Constraint Satisfaction Problems
Venue: arXiv cs.AI 2021
Year: 2021

Backtracking search algorithms are often used to solve the Constraint Satisfaction Problem (CSP). The efficiency of backtracking search depends greatly on the variable ordering heuristics. Currently, the most commonly used heuristics are hand-crafted based on expert knowledge. In this paper, we propose a deep reinforcement learning based approach to automatically discover new variable ordering heuristics that are better adapted for a given class of CSP instances. We show that directly optimizing the search cost is hard for bootstrapping, and propose to optimize the expected cost of reaching a leaf node in the search tree. To capture the complex relations among the variables and constraints, we design a representation scheme based on Graph Neural Network that can process CSP instances with different sizes and constraint arities. Experimental results on random CSP instances show that the learned policies outperform classical hand-crafted heuristics in terms of minimizing the search tree size, and can effectively generalize to instances that are larger than those used in training.
Fast and energy-efficient neuromorphic deep learning with first-spike times
Venue: arXiv cs.NE 2021
Year: 2021

For a biological agent operating under environmental pressure, energy consumption and reaction times are of critical importance. Similarly, engineered systems are optimized for short time-to-solution and low energy-to-solution characteristics. At the level of neuronal implementation, this implies achieving the desired results with as few and as early spikes as possible. With time-to-first-spike coding both of these goals are inherently emerging features of learning. Here, we describe a rigorous derivation of a learning rule for such first-spike times in networks of leaky integrate-and-fire neurons, relying solely on input and output spike times, and show how this mechanism can implement error backpropagation in hierarchical spiking networks. Furthermore, we emulate our framework on the BrainScaleS-2 neuromorphic system and demonstrate its capability of harnessing the system's speed and energy characteristics. Finally, we examine how our approach generalizes to other neuromorphic platforms by studying how its performance is affected by typical distortive effects induced by neuromorphic substrates.
Decision Making in Star Networks with Incorrect Beliefs
Venue: arXiv cs.IT 2021
Year: 2021

Consider a Bayesian binary decision-making problem in star networks, where local agents make selfish decisions independently, and a fusion agent makes a final decision based on aggregated decisions and its own private signal. In particular, we assume all agents have private beliefs for the true prior probability, based on which they perform Bayesian decision making. We focus on the Bayes risk of the fusion agent and counterintuitively find that incorrect beliefs could achieve a smaller risk than that when agents know the true prior. It is of independent interest for sociotechnical system design that the optimal beliefs of local agents resemble human probability reweighting models from cumulative prospect theory. We also consider asymptotic characterization of the optimal beliefs and fusion agent's risk in the number of local agents. We find that the optimal risk of the fusion agent converges to zero exponentially fast as the number of local agents grows. Furthermore, having an identical constant belief is asymptotically optimal in the sense of the risk exponent. For additive Gaussian noise, the optimal belief turns out to be a simple function of only error costs and the risk exponent can be explicitly characterized.
Near-Optimal Schedules for Simultaneous Multicasts
Venue: arXiv cs.DS 2021
Year: 2021

We study the store-and-forward packet routing problem for simultaneous multicasts, in which multiple packets have to be forwarded along given trees as fast as possible. This is a natural generalization of the seminal work of Leighton, Maggs and Rao, which solved this problem for unicasts, i.e. the case where all trees are paths. They showed the existence of asymptotically optimal $O(C + D)$-length schedules, where the congestion $C$ is the maximum number of packets sent over an edge and the dilation $D$ is the maximum depth of a tree. This improves over the trivial $O(CD)$ length schedules. We prove a lower bound for multicasts, which shows that there do not always exist schedules of non-trivial length, $o(CD)$. On the positive side, we construct $O(C+D+\log^2 n)$-length schedules in any $n$-node network. These schedules are near-optimal, since our lower bound shows that this length cannot be improved to $O(C+D) + o(\log n)$.
Multi-transversals for Triangles and the Tuza's Conjecture
Venue: arXiv cs.DM 2021
Year: 2021

In this paper, we study a primal and dual relationship about triangles: For any graph $G$, let $ν(G)$ be the maximum number of edge-disjoint triangles in $G$, and $τ(G)$ be the minimum subset $F$ of edges such that $G \setminus F$ is triangle-free. It is easy to see that $ν(G) \leq τ(G) \leq 3 ν(G)$, and in fact, this rather obvious inequality holds for a much more general primal-dual relation between $k$-hyper matching and covering in hypergraphs. Tuza conjectured in $1981$ that $τ(G) \leq 2 ν(G)$, and this question has received attention from various groups of researchers in discrete mathematics, settling various special cases such as planar graphs and generalized to bounded maximum average degree graphs, some cases of minor-free graphs, and very dense graphs. Despite these efforts, the conjecture in general graphs has remained wide open for almost four decades. In this paper, we provide a proof of a non-trivial consequence of the conjecture; that is, for every $k \geq 2$, there exist a (multi)-set $F \subseteq E(G): |F| \leq 2k ν(G)$ such that each triangle in $G$ overlaps at least $k$ elements in $F$. Our result can be seen as a strengthened statement of Krivelevich's result on the fractional version of Tuza's conjecture (and we give some examples illustrating this.) The main technical ingredient of our result is a charging argument, that locally identifies edges in $F$ based on a local view of the packing solution. This idea might be useful in further studying the primal-dual relations in general and the Tuza's conjecture in particular.
FrequentNet: A Novel Interpretable Deep Learning Model for Image Classification
Venue: arXiv cs.CV 2021
Year: 2021

This paper has proposed a new baseline deep learning model of more benefits for image classification. Different from the convolutional neural network(CNN) practice where filters are trained by back propagation to represent different patterns of an image, we are inspired by a method called "PCANet" in "PCANet: A Simple Deep Learning Baseline for Image Classification?" to choose filter vectors from basis vectors in frequency domain like Fourier coefficients or wavelets without back propagation. Researchers have demonstrated that those basis in frequency domain can usually provide physical insights, which adds to the interpretability of the model by analyzing the frequencies selected. Besides, the training process will also be more time efficient, mathematically clear and interpretable compared with the "black-box" training process of CNN.
Towards Automatic Threat Detection: A Survey of Advances of Deep Learning within X-ray Security Imaging
Venue: arXiv cs.CV 2021
Year: 2021

X-ray security screening is widely used to maintain aviation/transport security, and its significance poses a particular interest in automated screening systems. This paper aims to review computerised X-ray security imaging algorithms by taxonomising the field into conventional machine learning and contemporary deep learning applications. The first part briefly discusses the classical machine learning approaches utilised within X-ray security imaging, while the latter part thoroughly investigates the use of modern deep learning algorithms. The proposed taxonomy sub-categorises the use of deep learning approaches into supervised, semi-supervised and unsupervised learning, with a particular focus on object classification, detection, segmentation and anomaly detection tasks. The paper further explores well-established X-ray datasets and provides a performance benchmark. Based on the current and future trends in deep learning, the paper finally presents a discussion and future directions for X-ray security imagery.
Towards Practical Encrypted Network Traffic Pattern Matching for Secure Middleboxes
Venue: arXiv cs.CR 2021
Year: 2021

Network Function Virtualisation (NFV) advances the adoption of composable software middleboxes. Accordingly, cloud data centres become major NFV vendors for enterprise traffic processing. Due to the privacy concern of traffic redirection to the cloud, secure middlebox systems (e.g., BlindBox) draw much attention; they can process encrypted packets against encrypted rules directly. However, most of the existing systems supporting pattern matching based network functions require the enterprise gateway to tokenise packet payloads via sliding windows. Such tokenisation induces a considerable communication overhead, which can be over 100$\times$ to the packet size. To overcome this bottleneck, in this paper, we propose the first bandwidth-efficient encrypted pattern matching protocol for secure middleboxes. We resort to a primitive called symmetric hidden vector encryption (SHVE), and propose a variant of it, aka SHVE+, to achieve constant and moderate communication cost. To speed up, we devise encrypted filters to reduce the number of accesses to SHVE+ during matching highly. We formalise the security of our proposed protocol and conduct comprehensive evaluations over real-world rulesets and traffic dumps. The results show that our design can inspect a packet over 20k rules within 100 $μ$s. Compared to prior work, it brings a saving of $94\%$ in bandwidth consumption.
Automatic Melody Harmonization with Triad Chords: A Comparative Study
Venue: arXiv cs.SD 2021
Year: 2021

Several prior works have proposed various methods for the task of automatic melody harmonization, in which a model aims to generate a sequence of chords to serve as the harmonic accompaniment of a given multiple-bar melody sequence. In this paper, we present a comparative study evaluating and comparing the performance of a set of canonical approaches to this task, including a template matching based model, a hidden Markov based model, a genetic algorithm based model, and two deep learning based models. The evaluation is conducted on a dataset of 9,226 melody/chord pairs we newly collect for this study, considering up to 48 triad chords, using a standardized training/test split. We report the result of an objective evaluation using six different metrics and a subjective study with 202 participants.
On Interpretability of Artificial Neural Networks: A Survey
Venue: arXiv cs.LG 2021
Year: 2021

Deep learning as represented by the artificial deep neural networks (DNNs) has achieved great success in many important areas that deal with text, images, videos, graphs, and so on. However, the black-box nature of DNNs has become one of the primary obstacles for their wide acceptance in mission-critical applications such as medical diagnosis and therapy. Due to the huge potential of deep learning, interpreting neural networks has recently attracted much research attention. In this paper, based on our comprehensive taxonomy, we systematically review recent studies in understanding the mechanism of neural networks, describe applications of interpretability especially in medicine, and discuss future directions of interpretability research, such as in relation to fuzzy logic and brain science.
Fundamental Limits of Prediction, Generalization, and Recursion: An Entropic-Innovations Perspective
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we examine the fundamental performance limits of prediction, with or without side information. More specifically, we derive generic lower bounds on the $\mathcal{L}_p$ norms of the prediction errors that are valid for any prediction algorithms and for any data distributions. Meanwhile, we combine the entropic analysis from information theory and the innovations approach from prediction/estimation theory to characterize the conditions (in terms of, e.g., directed information or mutual information) to achieve the bounds. We also investigate the implications of the results in analyzing the fundamental limits of generalization in fitting (learning) problems from the perspective of prediction with side information, as well as the fundamental limits of recursive algorithms by viewing them as generalized prediction problems.
Characterizing the Root Landscape of Certificate Transparency Logs
Venue: arXiv cs.NI 2021
Year: 2021

Internet security and privacy stand on the trustworthiness of public certificates signed by Certificate Authorities (CAs). However, software products do not trust the same CAs and therefore maintain different root stores, each typically containing hundreds of trusted roots capable of issuing "trusted" certificates for any domain. Incidents with misissued certificates motivated Google to implement and enforce Certificate Transparency (CT). CT logs archive certificates in a public, auditable and append-only manner. The adoption of CT changed the trust landscape. As a part of this change, CT logs started to maintain their own root lists and log certificates that chain back to one of the trusted roots. In this paper, we present the first characterization of this emerging CT root store landscape, as well as the tool that we developed for data collection, visualization, and analysis of the root stores. We compare the logs' root stores and quantify their changes with respect to both each other and the root stores of major software vendors, look at evolving vendor CT policies, and show that root store mismanagement may be linked to log misbehavior. Finally, we present and discuss the results of a survey that we have sent to the log operators participating in Apple's and Google's CT log programs.
Generic Decoding in the Sum-Rank Metric
Venue: arXiv cs.IT 2021
Year: 2021

We propose the first non-trivial generic decoding algorithm for codes in the sum-rank metric. The new method combines ideas of well-known generic decoders in the Hamming and rank metric. For the same code parameters and number of errors, the new generic decoder has a larger expected complexity than the known generic decoders for the Hamming metric and smaller than the known rank-metric decoders. Furthermore, we give a formal hardness reduction, providing evidence that generic sum-rank decoding is computationally hard. As a by-product of the above, we solve some fundamental coding problems in the sum-rank metric: we give an algorithm to compute the exact size of a sphere of a given sum-rank radius, and also give an upper bound as a closed formula; and we study erasure decoding with respect to two different notions of support.