OpenRaiser/Intern-Atlas huggingface dataset:
Multilevel LDPC Lattices with Efficient Encoding and Decoding and a Generalization of Construction D'
Venue: arXiv cs.IT 2018
Year: 2018

Lattice codes are elegant and powerful structures that not only can achieve the capacity of the AWGN channel but are also a key ingredient to many multiterminal schemes that exploit linearity properties. However, constructing lattice codes that can realize these benefits with low complexity is still a challenging problem. In this paper, efficient encoding and decoding algorithms are proposed for multilevel binary LDPC lattices constructed via Construction D' whose complexity is linear in the total number of coded bits. Moreover, a generalization of Construction D' is proposed that relaxes some of the nesting constraints on the parity-check matrices of the component codes, leading to a simpler and improved design. Based on this construction, low-complexity multilevel LDPC lattices are designed whose performance under multistage decoding is comparable to that of polar lattices and close to that of low-density lattice codes (LDLC) on the power-unconstrained AWGN channel.
Event-based Failure Prediction in Distributed Business Processes
Venue: arXiv cs.DC 2018
Year: 2018

Traditionally, research in Business Process Management has put a strong focus on centralized and intra-organizational processes. However, today's business processes are increasingly distributed, deviating from a centralized layout, and therefore calling for novel methodologies of detecting and responding to unforeseen events, such as errors occurring during process runtime. In this article, we demonstrate how to employ event-based failure prediction in business processes. This approach allows to make use of the best of both traditional Business Process Management Systems and event-based systems. Our approach employs machine learning techniques and considers various types of events. We evaluate our solution using two business process data sets, including one from a real-world event log, and show that we are able to detect errors and predict failures with high accuracy.
Probabilistic Eigenvalue Shaping for Nonlinear Fourier Transform Transmission
Venue: arXiv cs.IT 2018
Year: 2018

We consider a nonlinear Fourier transform (NFT)-based transmission scheme, where data is embedded into the imaginary part of the nonlinear discrete spectrum. Inspired by probabilistic amplitude shaping, we propose a probabilistic eigenvalue shaping (PES) scheme as a means to increase the data rate of the system. We exploit the fact that for an NFT-based transmission scheme the pulses in the time domain are of unequal duration by transmitting them with a dynamic symbol interval and find a capacity-achieving distribution. The PES scheme shapes the information symbols according to the capacity-achieving distribution and transmits them together with the parity symbols at the output of a low-density parity-check encoder, suitably modulated, via time-sharing. We furthermore derive an achievable rate for the proposed PES scheme. We verify our results with simulations of the discrete-time model as well as with split-step Fourier simulations.
Sparse Graphs for Belief Propagation Decoding of Polar Codes
Venue: arXiv cs.IT 2018
Year: 2018

We describe a novel approach to interpret a polar code as a low-density parity-check (LDPC)-like code with an underlying sparse decoding graph. This sparse graph is based on the encoding factor graph of polar codes and is suitable for conventional belief propagation (BP) decoding. We discuss several pruning techniques based on the check node decoder (CND) and variable node decoder (VND) update equations, significantly reducing the size (i.e., decoding complexity) of the parity-check matrix. As a result, iterative polar decoding can then be conducted on a sparse graph, akin to the traditional well-established LDPC decoding, e.g., using a fully parallel sum-product algorithm (SPA). This facilitates the systematic analysis and design of polar codes using the well-established tools known from analyzing LDPC codes. We show that the proposed iterative polar decoder has a negligible performance loss for short-to-intermediate codelengths compared to Arikan's original BP decoder. Finally, the proposed decoder is shown to benefit from both reduced complexity and reduced memory requirements and, thus, is more suitable for hardware implementations.
Longest common substring with approximately $k$ mismatches
Venue: arXiv cs.DS 2018
Year: 2018

In the longest common substring problem, we are given two strings of length $n$ and must find a substring of maximal length that occurs in both strings. It is well known that the problem can be solved in linear time, but the solution is not robust and can vary greatly when the input strings are changed even by one character. To circumvent this, Leimeister and Morgenstern introduced the problem of the longest common substring with $k$ mismatches. Lately, this problem has received a lot of attention in the literature. In this paper, we first show a conditional lower bound based on the SETH hypothesis implying that there is little hope to improve existing solutions. We then introduce a new but closely related problem of the longest common substring with approximately $k$ mismatches and use locality-sensitive hashing to show that it admits a solution with strongly subquadratic running time. We also apply these results to obtain a strongly subquadratic-time 2-approximation algorithm for the longest common substring with $k$ mismatches problem and show conditional hardness of improving its approximation ratio.
DeepPicar: A Low-cost Deep Neural Network-based Autonomous Car
Venue: arXiv cs.OH 2018
Year: 2018

We present DeepPicar, a low-cost deep neural network based autonomous car platform. DeepPicar is a small scale replication of a real self-driving car called DAVE-2 by NVIDIA. DAVE-2 uses a deep convolutional neural network (CNN), which takes images from a front-facing camera as input and produces car steering angles as output. DeepPicar uses the same network architecture---9 layers, 27 million connections and 250K parameters---and can drive itself in real-time using a web camera and a Raspberry Pi 3 quad-core platform. Using DeepPicar, we analyze the Pi 3's computing capabilities to support end-to-end deep learning based real-time control of autonomous vehicles. We also systematically compare other contemporary embedded computing platforms using the DeepPicar's CNN-based real-time control workload. We find that all tested platforms, including the Pi 3, are capable of supporting the CNN-based real-time control, from 20 Hz up to 100 Hz, depending on hardware platform. However, we find that shared resource contention remains an important issue that must be considered in applying CNN models on shared memory based embedded computing platforms; we observe up to 11.6X execution time increase in the CNN based control loop due to shared resource contention. To protect the CNN workload, we also evaluate state-of-the-art cache partitioning and memory bandwidth throttling techniques on the Pi 3. We find that cache partitioning is ineffective, while memory bandwidth throttling is an effective solution.
Quantized Precoding for Multi-Antenna Downlink Channels with MAGIQ
Venue: arXiv cs.IT 2018
Year: 2018

A multi-antenna, greedy, iterative, and quantized (MAGIQ) precoding algorithm is proposed for downlink channels. MAGIQ allows a straightforward integration with orthogonal frequency-division multiplexing (OFDM). MAGIQ is compared to three existing algorithms in terms of information rates and complexity: quantized linear precoding (QLP), SQUID, and an ADMM-based algorithm. The information rate is measured by using a lower bound for finite modulation sets, and the complexity is measured by the number of multiplications and comparisons. MAGIQ and ADMM achieve similar information rates with similar complexity for Rayleigh flat-fading channels and one-bit quantization per real dimension, and they outperform QLP and SQUID for higher order modulation.
On the Properties of the Compound Nodal Admittance Matrix of Polyphase Power Systems
Venue: arXiv cs.SY 2018
Year: 2018

Most techniques for power system analysis model the grid by exact electrical circuits. For instance, in power flow study, state estimation, and voltage stability assessment, the use of admittance parameters (i.e., the nodal admittance matrix) and hybrid parameters is common. Moreover, network reduction techniques (e.g., Kron reduction) are often applied to decrease the size of large grid models (i.e., with hundreds or thousands of state variables), thereby alleviating the computational burden. However, researchers normally disregard the fact that the applicability of these methods is not generally guaranteed. In reality, the nodal admittance must satisfy certain properties in order for hybrid parameters to exist and Kron reduction to be feasible. Recently, this problem was solved for the particular cases of monophase and balanced triphase grids. This paper investigates the general case of unbalanced polyphase grids. Firstly, conditions determining the rank of the so-called compound nodal admittance matrix and its diagonal subblocks are deduced from the characteristics of the electrical components and the network graph. Secondly, the implications of these findings concerning the feasibility of Kron reduction and the existence of hybrid parameters are discussed. In this regard, this paper provides a rigorous theoretical foundation for various applications in power system analysis
Strongly Hierarchical Factorization Machines and ANOVA Kernel Regression
Venue: arXiv cs.LG 2018
Year: 2018

High-order parametric models that include terms for feature interactions are applied to various data mining tasks, where ground truth depends on interactions of features. However, with sparse data, the high- dimensional parameters for feature interactions often face three issues: expensive computation, difficulty in parameter estimation and lack of structure. Previous work has proposed approaches which can partially re- solve the three issues. In particular, models with factorized parameters (e.g. Factorization Machines) and sparse learning algorithms (e.g. FTRL-Proximal) can tackle the first two issues but fail to address the third. Regarding to unstructured parameters, constraints or complicated regularization terms are applied such that hierarchical structures can be imposed. However, these methods make the optimization problem more challenging. In this work, we propose Strongly Hierarchical Factorization Machines and ANOVA kernel regression where all the three issues can be addressed without making the optimization problem more difficult. Experimental results show the proposed models significantly outperform the state-of-the-art in two data mining tasks: cold-start user response time prediction and stock volatility prediction.
Who is Smarter? Intelligence Measure of Learning-based Cognitive Radios
Venue: arXiv cs.NI 2018
Year: 2018

Cognitive radio (CR) is considered as a key enabling technology for dynamic spectrum access to improve spectrum efficiency. Although the CR concept was invented with the core idea of realizing cognition, the research on measuring CR cognitive capabilities and intelligence is largely open. Deriving the intelligence measure of CR not only can lead to the development of new CR technologies, but also makes it possible to better configure the networks by integrating CRs with different cognitive capabilities. In this paper, for the first time, we propose a data-driven methodology to quantitatively measure the intelligence factors of the CR with learning capabilities. The basic idea of our methodology is to run various tests on the CR in different spectrum environments under different settings and obtain various performance data on different metrics. Then we apply factor analysis on the performance data to identify and quantize the intelligence factors and cognitive capabilities of the CR. More specifically, we present a case study consisting of 144 different types of CRs. The CRs are different in terms of learning-based dynamic spectrum access strategies, number of sensors, sensing accuracy, processing speed, and algorithmic complexity. Five intelligence factors are identified for the CRs through our data analysis.We show that these factors comply well with the nature of the tested CRs, which validates the proposed intelligence measure methodology.
Cache-Aided Non-Orthogonal Multiple Access
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we propose a novel joint caching and non-orthogonal multiple access (NOMA) scheme to facilitate advanced downlink transmission for next generation cellular networks. In addition to reaping the conventional advantages of caching and NOMA transmission, the proposed cache-aided NOMA scheme also exploits cached data for interference cancellation which is not possible with separate caching and NOMA transmission designs. Furthermore, as caching can help to reduce the residual interference power, several decoding orders are feasible at the receivers, and these decoding orders can be flexibly selected for performance optimization. We characterize the achievable rate region of cache-aided NOMA and investigate its benefits for minimizing the time required to complete video file delivery. Our simulation results reveal that, compared to several baseline schemes, the proposed cache-aided NOMA scheme significantly expands the achievable rate region for downlink transmission, which translates into substantially reduced file delivery times.
Memory-Efficient Deep Salient Object Segmentation Networks on Gridized Superpixels
Venue: arXiv cs.CV 2018
Year: 2018

Computer vision algorithms with pixel-wise labeling tasks, such as semantic segmentation and salient object detection, have gone through a significant accuracy increase with the incorporation of deep learning. Deep segmentation methods slightly modify and fine-tune pre-trained networks that have hundreds of millions of parameters. In this work, we question the need to have such memory demanding networks for the specific task of salient object segmentation. To this end, we propose a way to learn a memory-efficient network from scratch by training it only on salient object detection datasets. Our method encodes images to gridized superpixels that preserve both the object boundaries and the connectivity rules of regular pixels. This representation allows us to use convolutional neural networks that operate on regular grids. By using these encoded images, we train a memory-efficient network using only 0.048\% of the number of parameters that other deep salient object detection networks have. Our method shows comparable accuracy with the state-of-the-art deep salient object detection methods and provides a faster and a much more memory-efficient alternative to them. Due to its easy deployment, such a network is preferable for applications in memory limited devices such as mobile phones and IoT devices.
New bounds for range closest-pair problems
Venue: arXiv cs.CG 2018
Year: 2018

Given a dataset $S$ of points in $\mathbb{R}^2$, the range closest-pair (RCP) problem aims to preprocess $S$ into a data structure such that when a query range $X$ is specified, the closest-pair in $S \cap X$ can be reported efficiently. The RCP problem can be viewed as a range-search version of the classical closest-pair problem, and finds applications in many areas. Due to its non-decomposability, the RCP problem is much more challenging than many traditional range-search problems. This paper revisits the RCP problem, and proposes new data structures for various query types including quadrants, strips, rectangles, and halfplanes. Both worst-case and average-case analyses (in the sense that the data points are drawn uniformly and independently from the unit square) are applied to these new data structures, which result in new bounds for the RCP problem. Some of the new bounds significantly improve the previous results, while the others are entirely new.
Designing Fair Ranking Schemes
Venue: arXiv cs.DB 2018
Year: 2018

Items from a database are often ranked based on a combination of multiple criteria. A user may have the flexibility to accept combinations that weigh these criteria differently, within limits. On the other hand, this choice of weights can greatly affect the fairness of the produced ranking. In this paper, we develop a system that helps users choose criterion weights that lead to greater fairness. We consider ranking functions that compute the score of each item as a weighted sum of (numeric) attribute values, and then sort items on their score. Each ranking function can be expressed as a vector of weights, or as a point in a multi-dimensional space. For a broad range of fairness criteria, we show how to efficiently identify regions in this space that satisfy these criteria. Using this identification method, our system is able to tell users whether their proposed ranking function satisfies the desired fairness criteria and, if it does not, to suggest the smallest modification that does. We develop user-controllable approximation that and indexing techniques that are applied during preprocessing, and support sub-second response times during the online phase. Our extensive experiments on real datasets demonstrate that our methods are able to find solutions that satisfy fairness criteria effectively and efficiently.
Toward Continual Learning for Conversational Agents
Venue: arXiv cs.CL 2018
Year: 2018

While end-to-end neural conversation models have led to promising advances in reducing hand-crafted features and errors induced by the traditional complex system architecture, they typically require an enormous amount of data due to the lack of modularity. Previous studies adopted a hybrid approach with knowledge-based components either to abstract out domain-specific information or to augment data to cover more diverse patterns. On the contrary, we propose to directly address the problem using recent developments in the space of continual learning for neural models. Specifically, we adopt a domain-independent neural conversational model and introduce a novel neural continual learning algorithm that allows a conversational agent to accumulate skills across different tasks in a data-efficient way. To the best of our knowledge, this is the first work that applies continual learning to conversation systems. We verified the efficacy of our method through a conversational skill transfer from either synthetic dialogs or human-human dialogs to human-computer conversations in a customer support domain.
Interesting Paths in the Mapper
Venue: arXiv cs.CG 2018
Year: 2018

The Mapper produces a compact summary of high dimensional data as a simplicial complex. We study the problem of quantifying the interestingness of subpopulations in a Mapper, which appear as long paths, flares, or loops. First, we create a weighted directed graph G using the 1-skeleton of the Mapper. We use the average values at the vertices of a target function to direct edges (from low to high). The difference between the average values at vertices (high-low) is set as the edge's weight. Covariation of the remaining h functions (independent variables) is captured by a h-bit binary signature assigned to the edge. An interesting path in G is a directed path whose edges all have the same signature. We define the interestingness score of such a path as a sum of its edge weights multiplied by a nonlinear function of their ranks in the path. Second, we study three optimization problems on this graph G. In the problem Max-IP, we seek an interesting path in G with the maximum interestingness score. We show that Max-IP is NP-complete. For the special case when G is a directed acyclic graph (DAG), we show that Max-IP can be solved in polynomial time - in O(mnd_i) where d_i is the maximum indegree of a vertex in G. In the more general problem IP, the goal is to find a collection of edge-disjoint interesting paths such that the overall sum of their interestingness scores is maximized. We also study a variant of IP termed k-IP, where the goal is to identify a collection of edge-disjoint interesting paths each with k edges, and their total interestingness score is maximized. While k-IP can be solved in polynomial time for k <= 2, we show k-IP is NP-complete for k >= 3 even when G is a DAG. We develop polynomial time heuristics for IP and k-IP on DAGs.
Deep Learning Interior Tomography for Region-of-Interest Reconstruction
Venue: arXiv cs.CV 2018
Year: 2018

Interior tomography for the region-of-interest (ROI) imaging has advantages of using a small detector and reducing X-ray radiation dose. However, standard analytic reconstruction suffers from severe cupping artifacts due to existence of null space in the truncated Radon transform. Existing penalized reconstruction methods may address this problem but they require extensive computations due to the iterative reconstruction. Inspired by the recent deep learning approaches to low-dose and sparse view CT, here we propose a deep learning architecture that removes null space signals from the FBP reconstruction. Experimental results have shown that the proposed method provides near-perfect reconstruction with about 7-10 dB improvement in PSNR over existing methods in spite of significantly reduced run-time complexity.
Modal analysis of graphene-based structures for large deformations, contact and material nonlinearities
Venue: arXiv cs.CE 2018
Year: 2018

The nonlinear frequencies of pre-stressed graphene-based structures, such as flat graphene sheets and carbon nanotubes, are calculated. These structures are modeled with a nonlinear hyperelastic shell model. The model is calibrated with quantum mechanics data and is valid for high strains. Analytical solutions of the natural frequencies of various plates are obtained for the Canham bending model by assuming infinitesimal strains. These solutions are used for the verification of the numerical results. The performance of the model is illustrated by means of several examples. Modal analysis is performed for square plates under pure dilatation or uniaxial stretch, circular plates under pure dilatation or under the effects of an adhesive substrate, and carbon nanotubes under uniaxial compression or stretch. The adhesive substrate is modeled with van der Waals interaction (based on the Lennard-Jones potential) and a coarse grained contact model. It is shown that the analytical natural frequencies underestimate the real ones, and this should be considered in the design of devices based on graphene structures.
Diversity Analysis of Millimeter-Wave Massive MIMO Systems
Venue: arXiv cs.IT 2018
Year: 2018

This paper is concerned with asymptotic diversity analysis for millimeter-wave (mmWave) massive MIMO systems. First, for a single-user mmWave system employing distributed antenna subarray architecture in which the transmitter and receiver consist of Kt and Kr subarrays, respectively, a diversity gain theorem is established when the numbers of antennas at subarrays go to infinity. Specifically, assuming that all subchannels have the same number of propagation paths L, the theorem states that by employing such a distributed antenna-subarray architecture, a diversity gain of KrKtL-Ns+1 can be achieved, where Ns is the number of data streams. This result means that compared to the co-located antenna architecture, using the distributed antenna-subarray architecture can scale up the diversity gain or multiplexing gain proportionally to KrKt. The diversity gain analysis is then extended to the multiuser scenario as well as the scenario with conventional partially-connected RF structure in the literature. Simulation results obtained with the hybrid analog/digital processing corroborate the analysis results and show that the distributed subarray architecture indeed yields significantly better diversity performance than the co-located antenna architectures.