OpenRaiser/Intern-Atlas huggingface dataset:
Investigating the discrepancy property of de Bruijn sequences
Venue: arXiv cs.DM 2021
Year: 2021

The discrepancy of a binary string refers to the maximum (absolute) difference between the number of ones and the number of zeroes over all possible substrings of the given binary string. We provide an investigation of the discrepancy of known simple constructions of de Bruijn sequences. Furthermore, we demonstrate constructions that attain the lower bound of $Θ(n)$ and a new construction that attains the previously known upper bound of $Θ(\frac{2^n}{\sqrt{n}})$. This extends the work of Cooper and Heitsch~[\emph{Discrete Mathematics}, 310 (2010)].
Renormalized Mutual Information for Artificial Scientific Discovery
Venue: arXiv cs.LG 2021
Year: 2021

We derive a well-defined renormalized version of mutual information that allows to estimate the dependence between continuous random variables in the important case when one is deterministically dependent on the other. This is the situation relevant for feature extraction, where the goal is to produce a low-dimensional effective description of a high-dimensional system. Our approach enables the discovery of collective variables in physical systems, thus adding to the toolbox of artificial scientific discovery, while also aiding the analysis of information flow in artificial neural networks.
Automatic Generation of RAMS Analyses from Model-based Functional Descriptions using UML State Machines
Venue: arXiv cs.SE 2021
Year: 2021

In today's industrial practice, safety, reliability or availability artifacts such as fault trees, Markov models or FMEAs are mainly created manually by experts, often distinctively decoupled from systems engineering activities. Significant efforts, costs and timely requirements are involved to conduct the required analyses. In this paper, we describe a novel integrated model-based approach of systems engineering and dependability analyses. The behavior of system components is specified by UML state machines determining intended/correct and undesired/faulty behavior. Based on this information, our approach automatically generates different dependability analyses in the form of fault trees. Hence, alternative system layouts can easily be evaluated. The same applies for simple variations of the logical input-output relations of logical units such as controllers. We illustrate the feasibility of our approach with the help of simple examples using a prototypical implementation of the presented concepts.
Grid Drawings of Graphs with Constant Edge-Vertex Resolution
Venue: arXiv cs.DS 2021
Year: 2021

We study the algorithmic problem of computing drawings of graphs in which $(i)$ each vertex is a disk with fixed radius $ρ$, $(ii)$ each edge is a straight-line segment connecting the centers of the two disks representing its end-vertices, $(iii)$ no two disks intersect, and $(iv)$ the distance between an edge segment and the center of a non-incident disk, called \emph{edge-vertex resolution}, is at least $ρ$. We call such drawings \emph{disk-link drawings}. In this paper we focus on the case of constant edge-vertex resolution, namely $ρ=\frac{1}{2}$ (i.e., disks of unit diameter). We prove that star graphs, which trivially admit straight-line drawings in linear area, require quadratic area in any such disk-link drawing. On the positive side, we present constructive techniques that yield improved upper bounds for the area requirements of disk-link drawings for several (planar and nonplanar) graph classes, including bounded bandwidth, complete, and planar graphs. In particular, the presented bounds for complete and planar graphs are asymptotically tight.
Data Augmentation via Mixed Class Interpolation using Cycle-Consistent Generative Adversarial Networks Applied to Cross-Domain Imagery
Venue: arXiv cs.CV 2021
Year: 2021

Machine learning driven object detection and classification within non-visible imagery has an important role in many fields such as night vision, all-weather surveillance and aviation security. However, such applications often suffer due to the limited quantity and variety of non-visible spectral domain imagery, in contrast to the high data availability of visible-band imagery that readily enables contemporary deep learning driven detection and classification approaches. To address this problem, this paper proposes and evaluates a novel data augmentation approach that leverages the more readily available visible-band imagery via a generative domain transfer model. The model can synthesise large volumes of non-visible domain imagery by image-to-image (I2I) translation from the visible image domain. Furthermore, we show that the generation of interpolated mixed class (non-visible domain) image examples via our novel Conditional CycleGAN Mixup Augmentation (C2GMA) methodology can lead to a significant improvement in the quality of non-visible domain classification tasks that otherwise suffer due to limited data availability. Focusing on classification within the Synthetic Aperture Radar (SAR) domain, our approach is evaluated on a variation of the Statoil/C-CORE Iceberg Classifier Challenge dataset and achieves 75.4% accuracy, demonstrating a significant improvement when compared against traditional data augmentation strategies (Rotation, Mixup, and MixCycleGAN).
On Failure Diagnosis of the Storage Stack
Venue: arXiv cs.OS 2021
Year: 2021

Diagnosing storage system failures is challenging even for professionals. One example is the "When Solid State Drives Are Not That Solid" incident occurred at Algolia data center, where Samsung SSDs were mistakenly blamed for failures caused by a Linux kernel bug. With the system complexity keeps increasing, such obscure failures will likely occur more often. As one step to address the challenge, we present our on-going efforts called X-Ray. Different from traditional methods that focus on either the software or the hardware, X-Ray leverages virtualization to collects events across layers, and correlates them to generate a correlation tree. Moreover, by applying simple rules, X-Ray can highlight critical nodes automatically. Preliminary results based on 5 failure cases shows that X-Ray can effectively narrow down the search space for failures.
CCA2-secure Lattice-based Public Key Encryption with Equality Test in Standard Model
Venue: arXiv cs.CR 2021
Year: 2021

With the rapid growth of cloud storage and cloud computing services, many organisations and users choose to store the data on a cloud server for saving costs. However, due to security concerns, data of users would be encrypted before sending to the cloud. However, this hinders a problem of computation on encrypted data in the cloud, especially in the case of performing data matching in various medical scenarios. Public key encryption with equality test (PKEET) is a powerful tool that allows the authorized cloud server to check whether two ciphertexts are generated by the same message. PKEET has then become a promising candidate for many practical applications like efficient data management on encrypted databases. Lee et al. (Information Sciences 2020) proposed a generic construction of PKEET schemes in the standard model and hence it is possible to yield the first instantiation of post-quantum PKEET schemes based on lattices. At ACISP 2019, Duong et al. proposed a direct construction of PKEET over integer lattices in the standard model. However, their scheme does not reach the CCA2-security. In this paper, we propose an efficient CCA2-secure PKEET scheme based on ideal lattices. In addition, we present a modification of the scheme by Duong et al. over integer lattices to attain the CCA2-security. Both schemes are proven secure in the standard model, and they enjoy the security in the upcoming quantum computer era.
Soft Interference Cancellation for Random Coding in Massive Gaussian Multiple-Access
Venue: arXiv cs.IT 2021
Year: 2021

In 2017, Polyanskiy [1] showed that the trade-off between power and bandwidth efficiency for massive Gaussian random access is governed by two fundamentally different regimes: low power and high power. For both regimes, tight performance bounds were found by Zadik et al. [2], in 2019. This work utilizes recent results on the exact block error probability of Gaussian random codes in additive white Gaussian noise to propose practical methods based on iterative soft decoding to closely approach the bounds in [2]. In the low power regime, this work finds that orthogonal random codes can be applied directly. In the high power regime, a more sophisticated effort is needed. This work shows that power-profile optimization by means of linear programming as pioneered by Caire et al. [3], in 2001, is a promising strategy to apply. The proposed combination of orthogonal random coding and iterative soft decoding even outperforms the existence bounds of Zadik et al. [2] in the low power regime and is very close to the non-existence bounds for message lengths around 100 and above. Finally, the approach of power optimization by linear programming proposed for the high power regime is found to benefit from power imbalances due to fading which makes is even more attractive for typical mobile radio channels.
Heidelberg Colorectal Data Set for Surgical Data Science in the Sensor Operating Room
Venue: arXiv cs.CV 2021
Year: 2021

Image-based tracking of medical instruments is an integral part of surgical data science applications. Previous research has addressed the tasks of detecting, segmenting and tracking medical instruments based on laparoscopic video data. However, the proposed methods still tend to fail when applied to challenging images and do not generalize well to data they have not been trained on. This paper introduces the Heidelberg Colorectal (HeiCo) data set - the first publicly available data set enabling comprehensive benchmarking of medical instrument detection and segmentation algorithms with a specific emphasis on method robustness and generalization capabilities. Our data set comprises 30 laparoscopic videos and corresponding sensor data from medical devices in the operating room for three different types of laparoscopic surgery. Annotations include surgical phase labels for all video frames as well as information on instrument presence and corresponding instance-wise segmentation masks for surgical instruments (if any) in more than 10,000 individual frames. The data has successfully been used to organize international competitions within the Endoscopic Vision Challenges 2017 and 2019.
Synthesizing Safe Policies under Probabilistic Constraints with Reinforcement Learning and Bayesian Model Checking
Venue: arXiv cs.AI 2021
Year: 2021

We propose to leverage epistemic uncertainty about constraint satisfaction of a reinforcement learner in safety critical domains. We introduce a framework for specification of requirements for reinforcement learners in constrained settings, including confidence about results. We show that an agent's confidence in constraint satisfaction provides a useful signal for balancing optimization and safety in the learning process.
Layer-wise training convolutional neural networks with smaller filters for human activity recognition using wearable sensors
Venue: arXiv cs.CV 2021
Year: 2021

Recently, convolutional neural networks (CNNs) have set latest state-of-the-art on various human activity recognition (HAR) datasets. However, deep CNNs often require more computing resources, which limits their applications in embedded HAR. Although many successful methods have been proposed to reduce memory and FLOPs of CNNs, they often involve special network architectures designed for visual tasks, which are not suitable for deep HAR tasks with time series sensor signals, due to remarkable discrepancy. Therefore, it is necessary to develop lightweight deep models to perform HAR. As filter is the basic unit in constructing CNNs, it deserves further research whether re-designing smaller filters is applicable for deep HAR. In the paper, inspired by the idea, we proposed a lightweight CNN using Lego filters for HAR. A set of lower-dimensional filters is used as Lego bricks to be stacked for conventional filters, which does not rely on any special network structure. The local loss function is used to train model. To our knowledge, this is the first paper that proposes lightweight CNN for HAR in ubiquitous and wearable computing arena. The experiment results on five public HAR datasets, UCI-HAR dataset, OPPORTUNITY dataset, UNIMIB-SHAR dataset, PAMAP2 dataset, and WISDM dataset collected from either smartphones or multiple sensor nodes, indicate that our novel Lego CNN with local loss can greatly reduce memory and computation cost over CNN, while achieving higher accuracy. That is to say, the proposed model is smaller, faster and more accurate. Finally, we evaluate the actual performance on an Android smartphone.
Semi-Supervised Multi-aspect Detection of Misinformation using Hierarchical Joint Decomposition
Venue: arXiv cs.SI 2021
Year: 2021

Distinguishing between misinformation and real information is one of the most challenging problems in today's interconnected world. The vast majority of the state-of-the-art in detecting misinformation is fully supervised, requiring a large number of high-quality human annotations. However, the availability of such annotations cannot be taken for granted, since it is very costly, time-consuming, and challenging to do so in a way that keeps up with the proliferation of misinformation. In this work, we are interested in exploring scenarios where the number of annotations is limited. In such scenarios, we investigate how tapping on a diverse number of resources that characterize a news article, henceforth referred to as "aspects" can compensate for the lack of labels. In particular, our contributions in this paper are twofold: 1) We propose the use of three different aspects: article content, context of social sharing behaviors, and host website/domain features, and 2) We introduce a principled tensor based embedding framework that combines all those aspects effectively. We propose HiJoD a 2-level decomposition pipeline which not only outperforms state-of-the-art methods with F1-scores of 74% and 81% on Twitter and Politifact datasets respectively but also is an order of magnitude faster than similar ensemble approaches.
Enhancing LGMD's Looming Selectivity for UAV with Spatial-temporal Distributed Presynaptic Connections
Venue: arXiv cs.AI 2021
Year: 2021

Collision detection is one of the most challenging tasks for Unmanned Aerial Vehicles (UAVs). This is especially true for small or micro UAVs, due to their limited computational power. In nature, flying insects with compact and simple visual systems demonstrate their remarkable ability to navigate and avoid collision in complex environments. A good example of this is provided by locusts. They can avoid collisions in a dense swarm through the activity of a motion based visual neuron called the Lobula Giant Movement Detector (LGMD). The defining feature of the LGMD neuron is its preference for looming. As a flying insect's visual neuron, LGMD is considered to be an ideal basis for building UAV's collision detecting system. However, existing LGMD models cannot distinguish looming clearly from other visual cues such as complex background movements caused by UAV agile flights. To address this issue, we proposed a new model implementing distributed spatial-temporal synaptic interactions, which is inspired by recent findings in locusts' synaptic morphology. We first introduced the locally distributed excitation to enhance the excitation caused by visual motion with preferred velocities. Then radially extending temporal latency for inhibition is incorporated to compete with the distributed excitation and selectively suppress the non-preferred visual motions. Systematic experiments have been conducted to verify the performance of the proposed model for UAV agile flights. The results have demonstrated that this new model enhances the looming selectivity in complex flying scenes considerably, and has potential to be implemented on embedded collision detection systems for small or micro UAVs.
Estimating g-Leakage via Machine Learning
Venue: arXiv cs.CR 2021
Year: 2021

This paper considers the problem of estimating the information leakage of a system in the black-box scenario. It is assumed that the system's internals are unknown to the learner, or anyway too complicated to analyze, and the only available information are pairs of input-output data samples, possibly obtained by submitting queries to the system or provided by a third party. Previous research has mainly focused on counting the frequencies to estimate the input-output conditional probabilities (referred to as frequentist approach), however this method is not accurate when the domain of possible outputs is large. To overcome this difficulty, the estimation of the Bayes error of the ideal classifier was recently investigated using Machine Learning (ML) models and it has been shown to be more accurate thanks to the ability of those models to learn the input-output correspondence. However, the Bayes vulnerability is only suitable to describe one-try attacks. A more general and flexible measure of leakage is the g-vulnerability, which encompasses several different types of adversaries, with different goals and capabilities. In this paper, we propose a novel approach to perform black-box estimation of the g-vulnerability using ML. A feature of our approach is that it does not require to estimate the conditional probabilities, and that it is suitable for a large class of ML algorithms. First, we formally show the learnability for all data distributions. Then, we evaluate the performance via various experiments using k-Nearest Neighbors and Neural Networks. Our results outperform the frequentist approach when the observables domain is large.
Access Structures Determined by Uniform Polymatroids
Venue: arXiv cs.CR 2021
Year: 2021

An access structure is said to be multipartite, if the set of participants is divided into several parts and all participants in the same part play an equivalent role. The search for ideal secret sharing schemes for some special interesting families of multipartite access structures, has been carried out by many authors. In this paper a new concept of study of ideal access structures is proposed. We do not consider special classes of access structures defined by imposing certain prescribed assumptions, but we investigate all access structures obtained from uniform polymatroids using the method developed by Farràs, Martí-Farré and Padró. They satisfy necessary condition to be ideal, i.e., they are matroid ports. Moreover some objects in this family can be useful for the applications of secret sharing. The choice of uniform polymatroids is motivated by the fact that each such polymatroid defines ideal access structures. The method presented in this article is universal and can be continued with other classes of polymatroids in further similar studies. Here we are especially interested in hierarchy of participants determined by the access structure and we distinguish two main classes: they are compartmented and hierarchical access structures. The vast majority of papers discussing hierarchical access structures consider access structures which are compartment or totally hierarchical. The main results are summarized in Section 4, which presents situations where partial hierarchy properties may arise. In particular, hierarchical orders of obtained structures are described. It is surprising, that the hierarchical orders of access structures obtained from uniform polymatroids are flat, i.e., every chain has at most 2 elements. The ideality of some families of hierarchical access structures is proved in Section 5.
Reaching Your Goal Optimally by Playing at Random
Venue: arXiv cs.GT 2021
Year: 2021

Shortest-path games are two-player zero-sum games played on a graph equipped with integer weights. One player, that we call Min, wants to reach a target set of states while minimising the total weight, and the other one has an antagonistic objective. This combination of a qualitative reachability objective and a quantitative total-payoff objective is one of the simplest setting where Min needs memory (pseudo-polynomial in the weights) to play optimally. In this article, we aim at studying a tradeoff allowing Min to play at random, but using no memory. We show that Min can achieve the same optimal value in both cases. In particular, we compute a randomised memoryless $\varepsilon$-optimal strategy when it exists, where probabilities are parametrised by $\varepsilon$. We then characterise, and decide in polynomial time, the class of games admitting an optimal randomised memoryless strategy.
Framing Effects on Strategic Information Design under Receiver Distrust and Unknown State
Venue: arXiv cs.GT 2021
Year: 2021

Strategic information design is a framework where a sender designs information strategically to steer its receiver's decision towards a desired choice. Traditionally, such frameworks have always assumed that the sender and the receiver comprehends the state of the choice environment, and that the receiver always trusts the sender's signal. This paper deviates from these assumptions and re-investigates strategic information design in the presence of distrustful receiver and when both sender and receiver cannot observe/comprehend the environment state space. Specifically, we assume that both sender and receiver has access to non-identical beliefs about choice rewards (with sender's belief being more accurate), but not the environment state that determines these rewards. Furthermore, given that the receiver does not trust the sender, we also assume that the receiver updates its prior in a non-Bayesian manner. We evaluate the Stackelberg equilibrium and investigate effects of information framing (i.e. send complete signal, or just expected value of the signal) on the equilibrium. Furthermore, we also investigate trust dynamics at the receiver, under the assumption that the receiver minimizes regret in hindsight. Simulation results are presented to illustrate signaling effects and trust dynamics in strategic information design.
Angular Triplet Loss-based Camera Network for ReID
Venue: arXiv cs.CV 2021
Year: 2021

Person re-identification (ReID) is a challenging crosscamera retrieval task to identify pedestrians. Many complex network structures are proposed recently and many of them concentrate on multi-branch features to achieve high performance. However, they are too heavy-weight to deploy in realworld applications. Additionally, pedestrian images are often captured by different surveillance cameras, so the varied lights, perspectives and resolutions result in inevitable multi-camera domain gaps for ReID. To address these issues, this paper proposes ATCN, a simple but effective angular triplet loss-based camera network, which is able to achieve compelling performance with only global features. In ATCN, a novel angular distance is introduced to learn a more discriminative feature representation in the embedding space. Meanwhile, a lightweight camera network is designed to transfer global features to more discriminative features. ATCN is designed to be simple and flexible so it can be easily deployed in practice. The experiment results on various benchmark datasets show that ATCN outperforms many SOTA approaches.
Strong Asymptotic Composition Theorems for Mutual Information Measures
Venue: arXiv cs.IT 2021
Year: 2021

We characterize the growth of the Sibson and Arimoto mutual informations and $α$-maximal leakage, of any order that is at least unity, between a random variable and a growing set of noisy, conditionally independent and identically-distributed observations of the random variable. Each of these measures increases exponentially fast to a limit that is order- and measure-dependent, with an exponent that is order- and measure-independent.