OpenRaiser/Intern-Atlas huggingface dataset:
Multi-target detection with application to cryo-electron microscopy
Venue: arXiv cs.IT 2019
Year: 2019

We consider the multi-target detection problem of recovering a set of signals that appear multiple times at unknown locations in a noisy measurement. In the low noise regime, one can estimate the signals by first detecting occurrences, then clustering and averaging them. In the high noise regime however, neither detection nor clustering can be performed reliably, so that strategies along these lines are destined to fail. Notwithstanding, using autocorrelation analysis, we show that the impossibility to detect and cluster signal occurrences in the presence of high noise does not necessarily preclude signal estimation. Specifically, to estimate the signals, we derive simple relations between the autocorrelations of the observation and those of the signals. These autocorrelations can be estimated accurately at any noise level given a sufficiently long measurement. To recover the signals from the observed autocorrelations, we solve a set of polynomial equations through nonlinear least-squares. We provide analysis regarding well-posedness of the task, and demonstrate numerically the effectiveness of the method in a variety of settings. The main goal of this work is to provide theoretical and numerical support for a recently proposed framework to image 3-D structures of biological macromolecules using cryo-electron microscopy in extreme noise levels.
Normal 6-edge-colorings of some bridgeless cubic graphs
Venue: arXiv cs.DM 2019
Year: 2019

In an edge-coloring of a cubic graph, an edge is poor or rich, if the set of colors assigned to the edge and the four edges adjacent it, has exactly five or exactly three distinct colors, respectively. An edge is normal in an edge-coloring if it is rich or poor in this coloring. A normal $k$-edge-coloring of a cubic graph is an edge-coloring with $k$ colors such that each edge of the graph is normal. We denote by $χ'_{N}(G)$ the smallest $k$, for which $G$ admits a normal $k$-edge-coloring. Normal edge-colorings were introduced by Jaeger in order to study his well-known Petersen Coloring Conjecture. It is known that proving $χ'_{N}(G)\leq 5$ for every bridgeless cubic graph is equivalent to proving Petersen Coloring Conjecture. Moreover, Jaeger was able to show that it implies classical conjectures like Cycle Double Cover Conjecture and Berge-Fulkerson Conjecture. Recently, two of the authors were able to show that any simple cubic graph admits a normal $7$-edge-coloring, and this result is best possible. In the present paper, we show that any claw-free bridgeless cubic graph, permutation snark, tree-like snark admits a normal $6$-edge-coloring. Finally, we show that any bridgeless cubic graph $G$ admits a $6$-edge-coloring such that at least $\frac{7}{9}\cdot |E|$ edges of $G$ are normal.
Using Machine Learning and Big Data Analytics to Prioritize Outpatients in HetNets
Venue: arXiv cs.CY 2019
Year: 2019

In this paper, we introduce machine learning approaches that are used to prioritize outpatients (OP) according to their current health state, resulting in self-optimizing heterogeneous networks (HetNet) that intelligently adapt according to users' needs. We use a naïve Bayesian classifier to analyze data acquired from OPs' medical records, alongside data from medical Internet of Things (IoT) sensors that provide the current state of the OP. We use this machine learning algorithm to calculate the likelihood of a life-threatening medical condition, in this case an imminent stroke. An OP is assigned high-powered resource blocks (RBs) according to the seriousness of their current health state, enabling them to remain connected and send their critical data to the designated medical facility with minimal delay. Using a mixed integer linear programming formulation (MILP), we present two approaches to optimizing the uplink side of a HetNet in terms of user-RB assignment: a Weighted Sum Rate Maximization (WSRMax) approach and a Proportional Fairness (PF) approach. Using these approaches, we illustrate the utility of the proposed system in terms of providing reliable connectivity to medical IoT sensors, enabling the OPs to maintain the quality and speed of their connection. Moreover, we demonstrate how system response can change according to alterations in the OPs' medical conditions.
Analysis of Privacy Policies to Enhance Informed Consent (Extended Version)
Venue: arXiv cs.CR 2019
Year: 2019

In this report, we present an approach to enhance informed consent for the processing of personal data. The approach relies on a privacy policy language used to express, compare and analyze privacy policies. We describe a tool that automatically reports the privacy risks associated with a given privacy policy in order to enhance data subjects' awareness and to allow them to make more informed choices. The risk analysis of privacy policies is illustrated with an IoT example.
Are My Invariants Valid? A Learning Approach
Venue: arXiv cs.SE 2019
Year: 2019

Ensuring that a program operates correctly is a difficult task in large, complex systems. Enshrining invariants -- desired properties of correct execution -- in code or comments can support maintainability and help sustain correctness. Tools that can automatically infer and recommend invariants can thus be very beneficial. However, current invariant-suggesting tools, such as Daikon, suffer from high rates of false positives, in part because they only leverage traced program values from available test cases, rather than directly exploiting knowledge of the source code per se. We propose a machine-learning approach to judging the validity of invariants, specifically of method pre- and post-conditions, based directly on a method's source code. We introduce a new, scalable approach to creating labeled invariants: using programs with large test-suites, we generate Daikon invariants using traces from subsets of these test-suites, and then label these as valid/invalid by cross-validating them with held-out tests. This process induces a large set of labels that provide a form of noisy supervision, which is then used to train a deep neural model, based on gated graph neural networks. Our model learns to map the lexical, syntactic, and semantic structure of a given method's body into a probability that a candidate pre- or post-condition on that method's body is correct and is able to accurately label invariants based on the noisy signal, even in cross-project settings. Most importantly, it performs well on a hand-curated dataset of invariants.
State complexity of the multiples of the Thue-Morse set
Venue: arXiv cs.FL 2019
Year: 2019

The Thue-Morse set is the set of those nonnegative integers whose binary expansions have an even number of $1$. We obtain an exact formula for the state complexity of the multiplication by a constant of the Thue-Morse set $\mathcal{T}$ with respect with any base $b$ which is a power of $2$. Our proof is constructive and we are able to explicitly provide the minimal automaton of the language of all $2^p$-expansions of the set of integers $m\mathcal{T}$ for any positive integers $m$ and $p$.
LiDAR-Camera Calibration under Arbitrary Configurations: Observability and Methods
Venue: arXiv cs.RO 2019
Year: 2019

LiDAR-camera calibration is a precondition for many heterogeneous systems that fuse data from LiDAR and camera. However, the constraint from common field of view and the requirement for strict time synchronization make the calibration a challenging problem. In this paper, we propose a novel LiDAR-camera calibration method aiming to eliminate these two constraints. Specifically, we capture a scan of 3D LiDAR when both the environment and the sensors are stationary, then move the camera to reconstruct the 3D environment using the sequentially obtained images. Finally, we align 3D visual points to the laser scan based on tightly couple graph optimization method to calculate the extrinsic parameters between LiDAR and camera. Under this design, the configuration of these two sensors are free from the common field of view constraint owing to the extended view from the moving camera. And we also eliminate the requirement for strict time synchronization as we only use the single scan of laser data when the sensors are stationary. We theoretically derive the conditions of minimal observability for our method and prove that the accuracy of calibration is improved by collecting more observations from multiple scattered calibration targets. We validate our method on both simulation platform and real-world datasets. Experiments show that our method achieves higher accuracy than other comparable methods, which is in accordance with our theoretical analysis. In addition, the proposed method is beneficial to not only plane measurement error based chessboard, but also other point measurement error based calibration targets, such as boxes and polygonal boards.
LIKE Patterns and Complexity
Venue: arXiv cs.CC 2019
Year: 2019

We investigate the expressive power and complexity questions for the LIKE operator in SQL.
Architecture-Aware, High Performance Transaction for Persistent Memory
Venue: arXiv cs.DC 2019
Year: 2019

Byte-addressable non-volatile main memory (NVM) demands transactional mechanisms to access and manipulate data on NVM atomically. Those transaction mechanisms often employ a logging mechanism (undo logging or redo logging). However, the logging mechanisms can bring large runtime overhead (8%-49% in our evaluation), and 41%-78% of the overhead attributes to the frequent cache-line flushing. Such large overhead significantly diminishes the performance benefits offered by NVM. In this paper, we introduce a new method to reduce the overhead of cache-line flushing for logging-based transactions. Different from the traditional method that works at the program level and leverages program semantics to reduce the logging overhead, we introduce architecture awareness. In particular, we do not flush certain cache blocks, as long as they are estimated to be eliminated out of the cache because of the hardware caching mechanism (e.g., the cache replacement algorithm). Furthermore, we coalesce those cache blocks with low dirtiness to improve the efficiency of cache-line flushing. We implement an architecture-aware, high performance transaction runtime system for persistent memory, Archapt. Our results show that comparing with an undo logging (PMDK) and a redo logging (Mnemosyne), Archapt reduces cache-line flushing by 66% and improves system throughput by 19% on average (42% at most). Our crash tests with four hardware caching policies show that Archapt provides a strong guarantee on crash consistency.
A Formal Verification Technique for Architecture-based Embedded Systems in EAST-ADL
Venue: arXiv cs.SE 2019
Year: 2019

Development of quality assured software-intensive systems, such as automotive embedded systems, is an increasing challenge as the complexity of these systems significantly increases. EAST-ADL is an architecture description language developed to specify automotive embedded system architectures at multiple abstraction levels in the development of safety-critical automotive products. In this paper, we propose an architecture-based verification technique which enhances the model-based development process supported by EAST-ADL by adapting model-checking to EAST-ADL specifications. We employ UPPAAL as a verification tool to ensure that predicted function behaviors of the models in EAST-ADL satisfy functional and real-time requirements. The criteria for this architecture-based verification is presented and the transformation rules which comply with this criteria are derived. This enables us to extract the relevant information from EAST-ADL specifications and to generate analyzable UPPAAL models. The formal semantics of EAST-ADL is defined which is essential to automate the verification of EAST-ADL specifications. Our approach is demonstrated by verifying the safety of the steering truck system units.
Mixture Modeling of Global Shape Priors and Autoencoding Local Intensity Priors for Left Atrium Segmentation
Venue: arXiv cs.CV 2019
Year: 2019

Difficult image segmentation problems, for instance left atrium MRI, can be addressed by incorporating shape priors to find solutions that are consistent with known objects. Nonetheless, a single multivariate Gaussian is not an adequate model in cases with significant nonlinear shape variation or where the prior distribution is multimodal. Nonparametric density estimation is more general, but has a ravenous appetite for training samples and poses serious challenges in optimization, especially in high dimensional spaces. Here, we propose a maximum-a-posteriori formulation that relies on a generative image model by incorporating both local intensity and global shape priors. We use deep autoencoders to capture the complex intensity distribution while avoiding the careful selection of hand-crafted features. We formulate the shape prior as a mixture of Gaussians and learn the corresponding parameters in a high-dimensional shape space rather than pre-projecting onto a low-dimensional subspace. In segmentation, we treat the identity of the mixture component as a latent variable and marginalize it within a generalized expectation-maximization framework. We present a conditional maximization-based scheme that alternates between a closed-form solution for component-specific shape parameters that provides a global update-based optimization strategy, and an intensity-based energy minimization that translates the global notion of a nonlinear shape prior into a set of local penalties. We demonstrate our approach on the left atrial segmentation from gadolinium-enhanced MRI, which is useful in quantifying the atrial geometry in patients with atrial fibrillation.
Toward Imitating Visual Attention of Experts in Software Development Tasks
Venue: arXiv cs.SE 2019
Year: 2019

Expert programmers' eye-movements during source code reading are valuable sources that are considered to be associated with their domain expertise. We advocate a vision of new intelligent systems incorporating expertise of experts for software development tasks, such as issue localization, comment generation, and code generation. We present a conceptual framework of neural autonomous agents based on imitation learning (IL), which enables agents to mimic the visual attention of an expert via his/her eye movement. In this framework, an autonomous agent is constructed as a context-based attention model that consists of encoder/decoder network and trained with state-action sequences generated by an experts' demonstration. Challenges to implement an IL-based autonomous agent specialized for software development task are discussed in this paper.
Co-Contagion Diffusion on Multilayer Networks
Venue: arXiv cs.SI 2019
Year: 2019

This study examines the interface of three elements during co-contagion diffusion: the \textbf{synergy} between contagions, the \textbf{dormancy} rate of each individual contagion, and the \textbf{multiplex network topology}. Dormancy is defined as a weaker form of "immunity," where dormant nodes no longer actively participate in diffusion, but are still susceptible to infection. The proposed model extends the literature on threshold models, and demonstrates intricate interdependencies between different graph structures. Our simulations show that first, the faster contagion induces branching on the slower contagion; second, shorter characteristic path lengths diminish the impact of dormancy in lowering diffusion. Third, when two long-range graphs are paired, the faster contagion depends on both dormancy rates, whereas the slower contagion depends only on its own; fourth, synergistic contagions are less sensitive to dormancy, and have a wider window to diffuse. Furthermore, when long-range and spatially constrained graphs are paired, ring vaccination occurs on the spatial graph and produces partial diffusion, due to dormant, surrounding nodes. The spatial contagion depends on both dormancy rates whereas the long-range contagion depends on only its own.
Flickr1024: A Large-Scale Dataset for Stereo Image Super-Resolution
Venue: arXiv cs.CV 2019
Year: 2019

With the popularity of dual cameras in recently released smart phones, a growing number of super-resolution (SR) methods have been proposed to enhance the resolution of stereo image pairs. However, the lack of high-quality stereo datasets has limited the research in this area. To facilitate the training and evaluation of novel stereo SR algorithms, in this paper, we present a large-scale stereo dataset named Flickr1024, which contains 1024 pairs of high-quality images and covers diverse scenarios. We first introduce the data acquisition and processing pipeline, and then compare several popular stereo datasets. Finally, we conduct crossdataset experiments to investigate the potential benefits introduced by our dataset. Experimental results show that, as compared to the KITTI and Middlebury datasets, our Flickr1024 dataset can help to handle the over-fitting problem and significantly improves the performance of stereo SR methods. The Flickr1024 dataset is available online at: https://yingqianwang.github.io/Flickr1024.
Unsupervised Deep Transfer Feature Learning for Medical Image Classification
Venue: arXiv cs.CV 2019
Year: 2019

The accuracy and robustness of image classification with supervised deep learning are dependent on the availability of large-scale, annotated training data. However, there is a paucity of annotated data available due to the complexity of manual annotation. To overcome this problem, a popular approach is to use transferable knowledge across different domains by: 1) using a generic feature extractor that has been pre-trained on large-scale general images (i.e., transfer-learned) but which not suited to capture characteristics from medical images; or 2) fine-tuning generic knowledge with a relatively smaller number of annotated images. Our aim is to reduce the reliance on annotated training data by using a new hierarchical unsupervised feature extractor with a convolutional auto-encoder placed atop of a pre-trained convolutional neural network. Our approach constrains the rich and generic image features from the pre-trained domain to a sophisticated representation of the local image characteristics from the unannotated medical image domain. Our approach has a higher classification accuracy than transfer-learned approaches and is competitive with state-of-the-art supervised fine-tuned methods.
AccFlow: Defending Against the Low-Rate TCP DoS Attack in Wireless Sensor Networks
Venue: arXiv cs.CR 2019
Year: 2019

Because of the open nature of the Wireless Sensor Networks (WSN), the Denial of the Service (DoS) becomes one of the most serious threats to the stability of the resourceconstrained sensor nodes. In this paper, we develop AccFlow which is an incrementally deployable Software-Defined Networking based protocol that is able to serve as a countermeasure against the low-rate TCP DoS attack. The main idea of AccFlow is to make the attacking flows accountable for the congestion by dropping their packets according to their loss rates. The larger their loss rates, the more aggressively AccFlow drops their packets. Through extensive simulations, we demonstrate that AccFlow can effectively defend against the low-rate TCP DoS attack even if attackers vary their strategies by attacking at different scales and data rates. Furthermore, while AccFlow is designed to solve the low-rate TCP DoS attack, we demonstrate that AccFlow can also effectively defend against general DoS attacks which do not rely on the TCP retransmission timeout mechanism but cause denial of service to legitimate users by consistently exhausting the network resources. Finally, we consider the scalability of AccFlow and its deployment in real networks.
A Faster Algorithm Enumerating Relevant Features over Finite Fields
Venue: arXiv cs.LG 2019
Year: 2019

We consider the problem of enumerating relevant features hidden in other irrelevant information for multi-labeled data, which is formalized as learning juntas. A $k$-junta function is a function which depends on only $k$ coordinates of the input. For relatively small $k$ w.r.t. the input size $n$, learning $k$-junta functions is one of fundamental problems both theoretically and practically in machine learning. For the last two decades, much effort has been made to design efficient learning algorithms for Boolean junta functions, and some novel techniques have been developed. However, in real world, multi-labeled data seem to be obtained in much more often than binary-labeled one. Thus, it is a natural question whether these techniques can be applied to more general cases about the alphabet size. In this paper, we expand the Fourier detection techniques for the binary alphabet to any finite field $\mathbb{F}_q$, and give, roughly speaking, an $O(n^{0.8k})$-time learning algorithm for $k$-juntas over $\mathbb{F}_q$. Note that our algorithm is the first non-trivial (i.e., non-brute force) algorithm for such a class even in the case where $q=3$ and we give an affirmative answer to the question posed by Mossel et al. Our algorithm consists of two reductions: (1) from learning juntas to LDME which is a variant of the learning with errors (LWE) problems introduced by Regev, and (2) from LDME to the light bulb problem (LBP) introduced by L.Valiant. Since the reduced problem (i.e., LBP) is a kind of binary problem regardless of the alphabet size of the original problem (i.e., learning juntas), we can directly apply the techniques for the binary case in the previous work.
Cloud-Edge Coordinated Processing: Low-Latency Multicasting Transmission
Venue: arXiv cs.IT 2019
Year: 2019

Recently, edge caching and multicasting arise as two promising technologies to support high-data-rate and low-latency delivery in wireless communication networks. In this paper, we design three transmission schemes aiming to minimize the delivery latency for cache-enabled multigroup multicasting networks. In particular, full caching bulk transmission scheme is first designed as a performance benchmark for the ideal situation where the caching capability of each enhanced remote radio head (eRRH) is sufficient large to cache all files. For the practical situation where the caching capability of each eRRH is limited, we further design two transmission schemes, namely partial caching bulk transmission (PCBT) and partial caching pipelined transmission (PCPT) schemes. In the PCBT scheme, eRRHs first fetch the uncached requested files from the baseband unit (BBU) and then all requested files are simultaneously transmitted to the users. In the PCPT scheme, eRRHs first transmit the cached requested files while fetching the uncached requested files from the BBU. Then, the remaining cached requested files and fetched uncached requested files are simultaneously transmitted to the users. The design goal of the three transmission schemes is to minimize the delivery latency, subject to some practical constraints. Efficient algorithms are developed for the low-latency cloud-edge coordinated transmission strategies. Numerical results are provided to evaluate the performance of the proposed transmission schemes and show that the PCPT scheme outperforms the PCBT scheme in terms of the delivery latency criterion.