OpenRaiser/Intern-Atlas huggingface dataset:
Deep Learning for System Trace Restoration
Venue: arXiv cs.LG 2019
Year: 2019

Most real-world datasets, and particularly those collected from physical systems, are full of noise, packet loss, and other imperfections. However, most specification mining, anomaly detection and other such algorithms assume, or even require, perfect data quality to function properly. Such algorithms may work in lab conditions when given clean, controlled data, but will fail in the field when given imperfect data. We propose a method for accurately reconstructing discrete temporal or sequential system traces affected by data loss, using Long Short-Term Memory Networks (LSTMs). The model works by learning to predict the next event in a sequence of events, and uses its own output as an input to continue predicting future events. As a result, this method can be used for data restoration even with streamed data. Such a method can reconstruct even long sequence of missing events, and can also help validate and improve data quality for noisy data. The output of the model will be a close reconstruction of the true data, and can be fed to algorithms that rely on clean data. We demonstrate our method by reconstructing automotive CAN traces consisting of long sequences of discrete events. We show that given even small parts of a CAN trace, our LSTM model can predict future events with an accuracy of almost 90%, and can successfully reconstruct large portions of the original trace, greatly outperforming a Markov Model benchmark. We separately feed the original, lossy, and reconstructed traces into a specification mining framework to perform downstream analysis of the effect of our method on state-of-the-art models that use these traces for understanding the behavior of complex systems.
Unsupervised Deep Learning Algorithm for PDE-based Forward and Inverse Problems
Venue: arXiv cs.LG 2019
Year: 2019

We propose a neural network-based algorithm for solving forward and inverse problems for partial differential equations in unsupervised fashion. The solution is approximated by a deep neural network which is the minimizer of a cost function, and satisfies the PDE, boundary conditions, and additional regularizations. The method is mesh free and can be easily applied to an arbitrary regular domain. We focus on 2D second order elliptical system with non-constant coefficients, with application to Electrical Impedance Tomography.
FairVis: Visual Analytics for Discovering Intersectional Bias in Machine Learning
Venue: arXiv cs.LG 2019
Year: 2019

The growing capability and accessibility of machine learning has led to its application to many real-world domains and data about people. Despite the benefits algorithmic systems may bring, models can reflect, inject, or exacerbate implicit and explicit societal biases into their outputs, disadvantaging certain demographic subgroups. Discovering which biases a machine learning model has introduced is a great challenge, due to the numerous definitions of fairness and the large number of potentially impacted subgroups. We present FairVis, a mixed-initiative visual analytics system that integrates a novel subgroup discovery technique for users to audit the fairness of machine learning models. Through FairVis, users can apply domain knowledge to generate and investigate known subgroups, and explore suggested and similar subgroups. FairVis' coordinated views enable users to explore a high-level overview of subgroup performance and subsequently drill down into detailed investigation of specific subgroups. We show how FairVis helps to discover biases in two real datasets used in predicting income and recidivism. As a visual analytics system devoted to discovering bias in machine learning, FairVis demonstrates how interactive visualization may help data scientists and the general public understand and create more equitable algorithmic systems.
Parallel Algorithms Development for Programmable Devices with Application from Cryptography
Venue: arXiv cs.DC 2019
Year: 2019

Reconfigurable devices, such as Field Programmable Gate Arrays (FPGAs), have been witnessing a considerable increase in density. State-of-the-art FPGAs are complex hybrid devices that contain up to several millions of gates. Recently, research effort has been going into higher-level parallelization and hardware synthesis methodologies that can exploit such a programmable technology. In this paper, we explore the effectiveness of one such formal methodology in the design of parallel versions of the Serpent cryptographic algorithm. The suggested methodology adopts a functional programming notation for specifying algorithms and for reasoning about them. The specifications are realized through the use of a combination of function decomposition strategies, data refinement techniques, and off-the-shelf refinements based upon higher-order functions. The refinements are inspired by the operators of Communicating Sequential Processes (CSP) and map easily to programs in Handel-C (a hardware description language). In the presented research, we obtain several parallel Serpent implementations with different performance characteristics. The developed designs are tested under Celoxica's RC-1000 reconfigurable computer with its 2 million gates Virtex-E FPGA. Performance analysis and evaluation of these implementations are included.
Reducing approximate Longest Common Subsequence to approximate Edit Distance
Venue: arXiv cs.DS 2019
Year: 2019

Given a pair of strings, the problems of computing their Longest Common Subsequence and Edit Distance have been extensively studied for decades. For exact algorithms, LCS and Edit Distance (with character insertions and deletions) are equivalent; the state of the art running time is (almost) quadratic and this is tight under plausible fine-grained complexity assumptions. But for approximation algorithms the picture is different: there is a long line of works with improved approximation factors for Edit Distance, but for LCS (with binary strings) only a trivial $1/2$-approximation was known. In this work we give a reduction from approximate LCS to approximate Edit Distance, yielding the first efficient $(1/2+ε)$-approximation algorithm for LCS for some constant $ε>0$.
Instance Segmentation based Semantic Matting for Compositing Applications
Venue: arXiv cs.CV 2019
Year: 2019

Image compositing is a key step in film making and image editing that aims to segment a foreground object and combine it with a new background. Automatic image compositing can be done easily in a studio using chroma-keying when the background is pure blue or green. However, image compositing in natural scenes with complex backgrounds remains a tedious task, requiring experienced artists to hand-segment. In order to achieve automatic compositing in natural scenes, we propose a fully automated method that integrates instance segmentation and image matting processes to generate high-quality semantic mattes that can be used for image editing task. Our approach can be seen both as a refinement of existing instance segmentation algorithms and as a fully automated semantic image matting method. It extends automatic image compositing techniques such as chroma-keying to scenes with complex natural backgrounds without the need for any kind of user interaction. The output of our approach can be considered as both refined instance segmentations and alpha mattes with semantic meanings. We provide experimental results which show improved performance results as compared to existing approaches.
On Code Design for Wireless Channels with Additive Radar Interference
Venue: arXiv cs.IT 2019
Year: 2019

This paper considers the problem of code design for a channel where communications and radar systems coexist, modeled as having both Additive White Gaussian Noise (AWGN) and Additive Radar Interference (ARI). The issue of how to adapt or re-design convolutional codes (decoded by the Viterbi algorithm) and LDPC codes (decoded by the sum-product algorithm and optimized by using the EXIT chart method) to effectively handle the overall non-Gaussian ARI noise is investigated. A decoding metric is derived from the non-Gaussian ARI channel transition probability as a function of the Signal-to-Noise Ratio (SNR) and Interference-to-Noise Ratio (INR). Two design methodologies are benchmarked against a baseline "unaltered legacy system", where a code designed for AWGN-only noise, but used on the non-Gaussian ARI channel, is decoded by using the AWGN-only metric (i.e., as if INR is zero). The methodologies are: M1) codes designed for AWGN-only noise, but decoded with the new metric that accounts for both SNR and INR; and M2) codes optimized for the overall non-Gaussian ARI channel. Both methodologies give better average Bit Error Rate (BER) in the high INR regime compared to the baseline. In the low INR regime, both methodologies perform as the baseline since in this case the radar interference is weak. Interestingly, the performance improvement of M2 over M1 is minimal. In practice, this implies that specifications in terms of channel error correcting codes for commercially available wireless systems need not be changed, and that it suffices to use an appropriate INR-based decoding metric in order to effectively cope with the ARI.
Non-locally Encoder-Decoder Convolutional Network for Whole Brain QSM Inversion
Venue: arXiv cs.AI 2019
Year: 2019

Quantitative Susceptibility Mapping (QSM) reconstruction is a challenging inverse problem driven by ill conditioning of its field-to -susceptibility transformation. State-of-art QSM reconstruction methods either suffer from image artifacts or long computation times, which limits QSM clinical translation efforts. To overcome these limitations, a non-locally encoder-decoder gated convolutional neural network is trained to infer whole brain susceptibility map, using the local field and brain mask as the inputs. The performance of the proposed method is evaluated relative to synthetic data, a publicly available challenge dataset, and clinical datasets. The proposed approach can outperform existing methods on quantitative metrics and visual assessment of image sharpness and streaking artifacts. The estimated susceptibility maps can preserve conspicuity of fine features and suppress streaking artifacts. The demonstrated methods have potential value in advancing QSM clinical research and aiding in the translation of QSM to clinical operations.
Beyond trace reconstruction: Population recovery from the deletion channel
Venue: arXiv cs.DS 2019
Year: 2019

\emph{Population recovery} is the problem of learning an unknown distribution over an unknown set of $n$-bit strings, given access to independent draws from the distribution that have been independently corrupted according to some noise channel. Recent work has intensively studied such problems both for the bit-flip and erasure noise channels. We initiate the study of population recovery under the \emph{deletion channel}, in which each bit is independently \emph{deleted} with some fixed probability and the surviving bits are concatenated and transmitted. This is a far more challenging noise model than bit-flip~noise or erasure noise; indeed, even the simplest case in which the population size is 1 (corresponding to a trivial distribution supported on a single string) corresponds to the \emph{trace reconstruction} problem, a challenging problem that has received much recent attention (see e.g.~\cite{DOS17,NP17,PZ17,HPP18,HHP18}). We give algorithms and lower bounds for population recovery under the deletion channel when the population size is some $\ell>1$. As our main sample complexity upper bound, we show that for any $\ell=o(\log n/\log \log n)$, a population of $\ell$ strings from $\{0,1\}^n$ can be learned under deletion channel noise using $\smash{2^{n^{1/2+o(1)}}}$ samples. On the lower bound side, we show that $n^{Ω(\ell)}$ samples are required to perform population recovery under the deletion channel, for all $\ell \leq n^{1/2-ε}$. Our upper bounds are obtained via a robust multivariate generalization of a polynomial-based analysis, due to Krasikov and Roddity \cite{KR97}, of how the $k$-deck of a bit-string uniquely identifies the string; this is a very different approach from recent algorithms for trace reconstruction (the $\ell=1$ case). Our lower bounds build on moment-matching results of Roos~\cite{Roo00} and Daskalakis and Papadimitriou~\cite{DP15}.
A Processor-Sharing model for the Performance of Virtualized Network Functions
Venue: arXiv cs.PF 2019
Year: 2019

The parallel execution of requests in a Cloud Computing platform, as for Virtualized Network Functions, is modeled by an $M^{[X]}/M/1$ Processor-Sharing (PS) system, where each request is seen as a batch of unit jobs. The performance of such paralleled system can then be measured by the quantiles of the batch sojourn time distribution. In this paper, we address the evaluation of this distribution for the $M^{[X]}/M/1$-PS queue with batch arrivals and geometrically distributed batch size. General results on the residual busy period (after a tagged batch arrival time) and the number of unit jobs served during this residual busy period are first derived. This enables us to provide an approximation for the distribution tail of the batch sojourn time whose accuracy is confirmed by simulation.
Modified online Newton step based on element wise multiplication
Venue: arXiv cs.LG 2019
Year: 2019

The second order method as Newton Step is a suitable technique in Online Learning to guarantee regret bound. The large data is a challenge in Newton method to store second order matrices as hessian. In this paper, we have proposed an modified online Newton step that store first and second order matrices of dimension m (classes) by d (features). we have used element wise arithmetic operation to retain matrices size same. The modified second order matrix size results in faster computations. Also, the mistake rate is at par with respect to popular methods in literature. The experiments outcome indicate that proposed method could be helpful to handle large multi class datasets in common desktop machines using second order method as Newton step.
Efficient LiDAR data compression for embedded V2I or V2V data handling
Venue: arXiv cs.RO 2019
Year: 2019

LiDAR are increasingly being used in intelligent vehicles (IV) or intelligent transportation systems (ITS). Storage and transmission of data generated by LiDAR sensors are one of the most challenging aspects of their deployment. In this paper we present a method that can be used to efficiently compress LiDAR data in order to facilitate storage and transmission in V2V or V2I applications. This method can be used to perform lossless or lossy compression and is specifically designed for embedded applications with low processing power. This method is also designed to be easily applicable to existing processing chains by keeping the structure of the data stream intact. We benchmarked our method using several publicly available datasets and compared it with state-of-the-art LiDAR data compression methods from the literature.
Information Leakage in Encrypted Deduplication via Frequency Analysis: Attacks and Defenses
Venue: arXiv cs.CR 2019
Year: 2019

Encrypted deduplication combines encryption and deduplication to simultaneously achieve both data security and storage efficiency. State-of-the-art encrypted deduplication systems mainly build on deterministic encryption to preserve deduplication effectiveness. However, such deterministic encryption reveals the underlying frequency distribution of the original plaintext chunks. This allows an adversary to launch frequency analysis against the ciphertext chunks and infer the content of the original plaintext chunks. In this paper, we study how frequency analysis affects information leakage in encrypted deduplication storage, from both attack and defense perspectives. Specifically, we target backup workloads, and propose a new inference attack that exploits chunk locality to increase the coverage of inferred chunks. We further combine the new inference attack with the knowledge of chunk sizes and show its attack effectiveness against variable-size chunks. We conduct trace-driven evaluation on both real-world and synthetic datasets and show that our proposed attacks infer a significant fraction of plaintext chunks under backup workloads. To defend against frequency analysis, we present two defense approaches, namely MinHash encryption and scrambling. Our trace-driven evaluation shows that our combined MinHash encryption and scrambling scheme effectively mitigates the severity of the inference attacks, while maintaining high storage efficiency and incurring limited metadata access overhead.
Investigating Retrieval Method Selection with Axiomatic Features
Venue: arXiv cs.IR 2019
Year: 2019

We consider algorithm selection in the context of ad-hoc information retrieval. Given a query and a pair of retrieval methods, we propose a meta-learner that predicts how to combine the methods' relevance scores into an overall relevance score. Inspired by neural models' different properties with regard to IR axioms, these predictions are based on features that quantify axiom-related properties of the query and its top ranked documents. We conduct an evaluation on TREC Web Track data and find that the meta-learner often significantly improves over the individual methods. Finally, we conduct feature and query weight analyses to investigate the meta-learner's behavior.
GP-HD: Using Genetic Programming to Generate Dynamical Systems Models for Health Care
Venue: arXiv cs.NE 2019
Year: 2019

The huge wealth of data in the health domain can be exploited to create models that predict development of health states over time. Temporal learning algorithms are well suited to learn relationships between health states and make predictions about their future developments. However, these algorithms: (1) either focus on learning one generic model for all patients, providing general insights but often with limited predictive performance, or (2) learn individualized models from which it is hard to derive generic concepts. In this paper, we present a middle ground, namely parameterized dynamical systems models that are generated from data using a Genetic Programming (GP) framework. A fitness function suitable for the health domain is exploited. An evaluation of the approach in the mental health domain shows that performance of the model generated by the GP is on par with a dynamical systems model developed based on domain knowledge, significantly outperforms a generic Long Term Short Term Memory (LSTM) model and in some cases also outperforms an individualized LSTM model.
Reducing Communication in Algebraic Multigrid with Multi-step Node Aware Communication
Venue: arXiv cs.DC 2019
Year: 2019

Algebraic multigrid (AMG) is often viewed as a scalable $\mathcal{O}(n)$ solver for sparse linear systems. Yet, parallel AMG lacks scalability due to increasingly large costs associated with communication, both in the initial construction of a multigrid hierarchy as well as the iterative solve phase. This work introduces a parallel implementation of AMG to reduce the cost of communication, yielding an increase in scalability. Standard inter-process communication consists of sending data regardless of the send and receive process locations. Performance tests show notable differences in the cost of intra- and inter-node communication, motivating a restructuring of communication. In this case, the communication schedule takes advantage of the less costly intra-node communication, reducing both the number and size of inter-node messages. Node-centric communication extends to the range of components in both the setup and solve phase of AMG, yielding an increase in the weak and strong scalability of the entire method.
The More the Merrier: Enhancing Reliability of 5G Communication Services with Guaranteed Delay
Venue: arXiv cs.NI 2019
Year: 2019

Although network functions virtualization and software-defined networking offer many dynamic features such as flexibility, scalability, and programmability for easy provisioning of services at a lesser cost and time through service function chaining, it introduces new challenges in terms of reliability, availability, and latency of services. Particularly, softwarization of network and service functions (e.g., virtualization, anything as a service, dynamic virtual chaining, and routing) impose high possibility of network failures due to software issues than hardware. In this letter, we propose a novel solution called eRESERV to enhance the reliability of service chains in 5G while meeting the service level agreements.
Energy-Efficient High-Throughput Data Transfers via Dynamic CPU Frequency and Core Scaling
Venue: arXiv cs.DC 2019
Year: 2019

The energy footprint of global data movement has surpassed 100 terawatt hours, costing more than 20 billion US dollars to the world economy. Depending on the number of switches, routers, and hubs between the source and destination nodes, the networking infrastructure consumes 10% - 75% of the total energy during active data transfers, and the rest is consumed by the end systems. Even though there has been extensive research on reducing the power consumption at the networking infrastructure, the work focusing on saving energy at the end systems has been limited to the tuning of a few application level parameters such as parallelism, pipelining, and concurrency. In this paper, we introduce three novel application-level parameter tuning algorithms which employ dynamic CPU frequency and core scaling, combining heuristics and runtime measurements to achieve energy efficient data transfers. Experimental results show that our proposed algorithms outperform the state-of-the-art solutions, achieving up to 48% reduced energy consumption and 80% higher throughput.
On the Asymptotic Capacity of $X$-Secure $T$-Private Information Retrieval with Graph Based Replicated Storage
Venue: arXiv cs.IT 2019
Year: 2019

The problem of private information retrieval with graph-based replicated storage was recently introduced by Raviv, Tamo and Yaakobi. Its capacity remains open in almost all cases. In this work the asymptotic (large number of messages) capacity of this problem is studied along with its generalizations to include arbitrary $T$-privacy and $X$-security constraints, where the privacy of the user must be protected against any set of up to $T$ colluding servers and the security of the stored data must be protected against any set of up to $X$ colluding servers. A general achievable scheme for arbitrary storage patterns is presented that achieves the rate $(ρ_{\min}-X-T)/N$, where $N$ is the total number of servers, and each message is replicated at least $ρ_{\min}$ times. Notably, the scheme makes use of a special structure inspired by dual Generalized Reed Solomon (GRS) codes. A general converse is also presented. The two bounds are shown to match for many settings, including symmetric storage patterns. Finally, the asymptotic capacity is fully characterized for the case without security constraints $(X=0)$ for arbitrary storage patterns provided that each message is replicated no more than $T+2$ times. As an example of this result, consider PIR with arbitrary graph based storage ($T=1, X=0$) where every message is replicated at exactly $3$ servers. For this $3$-replicated storage setting, the asymptotic capacity is equal to $2/ν_2(G)$ where $ν_2(G)$ is the maximum size of a $2$-matching in a storage graph $G[V,E]$. In this undirected graph, the vertices $V$ correspond to the set of servers, and there is an edge $uv\in E$ between vertices $u,v$ only if a subset of messages is replicated at both servers $u$ and $v$.