OpenRaiser/Intern-Atlas huggingface dataset:
Algorithmic Polarization for Hidden Markov Models
Venue: arXiv cs.IT 2018
Year: 2018

Using a mild variant of polar codes we design linear compression schemes compressing Hidden Markov sources (where the source is a Markov chain, but whose state is not necessarily observable from its output), and to decode from Hidden Markov channels (where the channel has a state and the error introduced depends on the state). We give the first polynomial time algorithms that manage to compress and decompress (or encode and decode) at input lengths that are polynomial $\it{both}$ in the gap to capacity and the mixing time of the Markov chain. Prior work achieved capacity only asymptotically in the limit of large lengths, and polynomial bounds were not available with respect to either the gap to capacity or mixing time. Our results operate in the setting where the source (or the channel) is $\it{known}$. If the source is $\it{unknown}$ then compression at such short lengths would lead to effective algorithms for learning parity with noise -- thus our results are the first to suggest a separation between the complexity of the problem when the source is known versus when it is unknown.
Sparse Winograd Convolutional neural networks on small-scale systolic arrays
Venue: arXiv cs.DC 2018
Year: 2018

The reconfigurability, energy-efficiency, and massive parallelism on FPGAs make them one of the best choices for implementing efficient deep learning accelerators. However, state-of-art implementations seldom consider the balance between high throughput of computation power and the ability of the memory subsystem to support it. In this paper, we implement an accelerator on FPGA by combining the sparse Winograd convolution, clusters of small-scale systolic arrays, and a tailored memory layout design. We also provide an analytical model analysis for the general Winograd convolution algorithm as a design reference. Experimental results on VGG16 show that it achieves very high computational resource utilization, 20x ~ 30x energy efficiency, and more than 5x speedup compared with the dense implementation.
Turning Lemons into Peaches using Secure Computation
Venue: arXiv cs.GT 2018
Year: 2018

In many cases, assessing the quality of goods is hard. For example, when purchasing a car, it is hard to measure how pollutant the car is since there are infinitely many driving conditions to be tested. Typically, these situations are considered under the umbrella of information asymmetry and as Akelrof showed may lead to a market of lemons. However, we argue that in many of these situations, the problem is not the missing information but the computational challenge of obtaining it. In a nut-shell, if verifying the value of goods requires a large amount of computation or even infinite amounts of computation, the buyer is forced to use a finite test that samples, in some sense, the quality of the goods. However, if the seller knows the test, then the seller can over-fit the test and create goods that pass the quality test despite not having the desired quality. We show different solutions to this situation including a novel approach that uses secure computation to hide the test from the seller to prevent over-fitting.
Towards Fast and Energy-Efficient Binarized Neural Network Inference on FPGA
Venue: arXiv cs.LG 2018
Year: 2018

Binarized Neural Network (BNN) removes bitwidth redundancy in classical CNN by using a single bit (-1/+1) for network parameters and intermediate representations, which has greatly reduced the off-chip data transfer and storage overhead. However, a large amount of computation redundancy still exists in BNN inference. By analyzing local properties of images and the learned BNN kernel weights, we observe an average of $\sim$78% input similarity and $\sim$59% weight similarity among weight kernels, measured by our proposed metric in common network architectures. Thus there does exist redundancy that can be exploited to further reduce the amount of on-chip computations. Motivated by the observation, in this paper, we proposed two types of fast and energy-efficient architectures for BNN inference. We also provide analysis and insights to pick the better strategy of these two for different datasets and network models. By reusing the results from previous computation, much cycles for data buffer access and computations can be skipped. By experiments, we demonstrate that 80% of the computation and 40% of the buffer access can be skipped by exploiting BNN similarity. Thus, our design can achieve 17% reduction in total power consumption, 54% reduction in on-chip power consumption and 2.4$\times$ maximum speedup, compared to the baseline without applying our reuse technique. Our design also shows 1.9$\times$ more area-efficiency compared to state-of-the-art BNN inference design. We believe our deployment of BNN on FPGA leads to a promising future of running deep learning models on mobile devices.
FSS++ Workshop Report: Handling Uncertainty for Data Quality Management
Venue: arXiv cs.OH 2018
Year: 2018

This report describes the results of the eSCF Awareness Workshop on Handling Uncertainty for Data Quality Management - Challenges from Transport and Supply Chain Management that was held on June 5, 2018 in Heeze, The Netherlands. The goal of this workshop was to create and enhance awareness into data quality management issues that are encountered in practice, for business organizations that aim to integrate a data-analytical mind set into their operations.
Real Differences between OT and CRDT for Co-Editors
Venue: arXiv cs.DC 2018
Year: 2018

OT (Operational Transformation) was invented for supporting real-time co-editors in the late 1980s and has evolved to become a core technique used in today's working co-editors and adopted in major industrial products. CRDT (Commutative Replicated Data Type) for co-editors was first proposed around 2006, under the name of WOOT (WithOut Operational Transformation). Follow-up CRDT variations are commonly labeled as "post-OT" techniques capable of making concurrent operations natively commutative, and have made broad claims of superiority over OT solutions, in terms of correctness, time and space complexity, simplicity, etc. Over one decade later, however, CRDT solutions are rarely found in working co-editors, while OT solutions remain the choice for building the vast majority of co-editors. Contradictions between this reality and CRDT's purported advantages have been the source of much debate and confusion in co-editing research and developer communities. What is CRDT really to co-editing? What are the real differences between OT and CRDT for co-editors? What are the key factors that may have affected the adoption of and choice between OT and CRDT for co-editors in the real world? In this paper, we report our discoveries, in relation to these questions and beyond, from a comprehensive review and comparison study on representative OT and CRDT solutions and working co-editors based on them. Moreover, this work reveals facts and presents evidences that refute CRDT claimed advantages over OT. We hope the results reported in this paper will help clear up common myths, misconceptions, and confusions surrounding alternative co-editing techniques, and accelerate progress in co-editing technology for real world applications.
On the Performance of Space-Time MIMO Multiplexing for Free Space Optical Communications
Venue: arXiv cs.IT 2018
Year: 2018

Due to the relatively high cost of deploying optical fibers, free space optical (FSO) links have been developed as a cost-effective alternative technology for next generation cellular networks. However, in order to have a practical role in the physical layer of future communication systems, data rate of FSO links must be improved. To this aim, in this paper we employ a multiple-input multiple-output (MIMO) multiplexing scheme with two transceivers to increase the data rate of the considered FSO system. Unlike MIMO diversity case, the performance of MIMO multiplexing is significantly affected by interference be- tween parallel channels. To solve this problem, we propose a novel space-time scheme which significantly reduces the interference between parallel channels. We analyze the performance of the proposed scheme in terms of BER and outage probability.
Ergodic Capacity of Triple-Hop All-Optical Amplify-and-Forward Relaying over Free-Space Optical Channels
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we propose a comprehensive research over triple hop all-optical relaying free-space optical (FSO) systems in the presence of all main noise sources including background, thermal and amplified spontaneous emission (ASE) noise and by considering the effect of the optical degree-of- freedom (DoF). Using full CSI relaying, we derive the exact expressions for the noise variance at the destination. Then, in order to simplify the analytical expressions of full CSI relaying, we also propose and investigate the validity of different approximations over noise variance at the destination. Finally, we evaluate the the performance of considered triple-hop all-optical relaying FSO system in term of ergodic capacity.
DATA Agent
Venue: arXiv cs.AI 2018
Year: 2018

This paper introduces DATA Agent, a system which creates murder mystery adventures from open data. In the game, the player takes on the role of a detective tasked with finding the culprit of a murder. All characters, places, and items in DATA Agent games are generated using open data as source content. The paper discusses the general game design and user interface of DATA Agent, and provides details on the generative algorithms which transform linked data into different game objects. Findings from a user study with 30 participants playing through two games of DATA Agent show that the game is easy and fun to play, and that the mysteries it generates are straightforward to solve.
Concept-drifting Data Streams are Time Series; The Case for Continuous Adaptation
Venue: arXiv cs.LG 2018
Year: 2018

Learning from data streams is an increasingly important topic in data mining, machine learning, and artificial intelligence in general. A major focus in the data stream literature is on designing methods that can deal with concept drift, a challenge where the generating distribution changes over time. A general assumption in most of this literature is that instances are independently distributed in the stream. In this work we show that, in the context of concept drift, this assumption is contradictory, and that the presence of concept drift necessarily implies temporal dependence; and thus some form of time series. This has important implications on model design and deployment. We explore and highlight the these implications, and show that Hoeffding-tree based ensembles, which are very popular for learning in streams, are not naturally suited to learning \emph{within} drift; and can perform in this scenario only at significant computational cost of destructive adaptation. On the other hand, we develop and parameterize gradient-descent methods and demonstrate how they can perform \emph{continuous} adaptation with no explicit drift-detection mechanism, offering major advantages in terms of accuracy and efficiency. As a consequence of our theoretical discussion and empirical observations, we outline a number of recommendations for deploying methods in concept-drifting streams.
Performance Analysis of NOMA for Ultra-Reliable and Low-Latency Communications
Venue: arXiv cs.NI 2018
Year: 2018

Grant-free non-orthogonal multiple access (NOMA) has been regarded as a key-enabler technology for ultra-reliable and low-latency communications (URLLC). In this paper, we analyse the performance of NOMA with short packet communications for URLLC. In this regard, the overall packet loss probability consists of transmission error probability and queueing-delay violation probability. Queueing-delay has been modelled using the effective bandwidth. Due to short transmission time, the infinite block-length has been replaced with finite blocklength of the channel codes which rules out the application of Shannon's formula. The achievable effective bandwidth of the system is derived, and then, the transmission error probability has been analysed. The derivations are validated through extensive simulations, which shows the variations of the signal-to-noise ratio (SNR) requirements of the system for various transmission-error probability, QoS exponent, and the transmission packet size.
Direct Prediction of Cardiovascular Mortality from Low-dose Chest CT using Deep Learning
Venue: arXiv cs.CV 2018
Year: 2018

Cardiovascular disease (CVD) is a leading cause of death in the lung cancer screening population. Chest CT scans made in lung cancer screening are suitable for identification of participants at risk of CVD. Existing methods analyzing CT images from lung cancer screening for prediction of CVD events or mortality use engineered features extracted from the images combined with patient information. In this work we propose a method that automatically predicts 5-year cardiovascular mortality directly from chest CT scans without the need for hand-crafting image features. A set of 1,583 participants of the National Lung Screening Trial was included (1,188 survivors, 395 non-survivors). Low-dose chest CT images acquired at baseline were analyzed and the follow-up time was 5 years. To limit the analysis to the heart region, the heart was first localized by our previously developed algorithm for organ localization exploiting convolutional neural networks. Thereafter, a convolutional autoencoder was used to encode the identified heart region. Finally, based on the extracted encodings subjects were classified into survivors or non-survivors using a support vector machine classifier. The performance of the method was assessed in eight cross-validation experiments with 1,433 images used for training, 50 for validation and 100 for testing. The method achieved a performance with an area under the ROC curve of 0.72. The results demonstrate that prediction of cardiovascular mortality directly from low-dose screening chest CT scans, without hand-crafted features, is feasible, allowing identification of subjects at risk of fatal CVD events.
Progressive Feature Fusion Network for Realistic Image Dehazing
Venue: arXiv cs.CV 2018
Year: 2018

Single image dehazing is a challenging ill-posed restoration problem. Various prior-based and learning-based methods have been proposed. Most of them follow a classic atmospheric scattering model which is an elegant simplified physical model based on the assumption of single-scattering and homogeneous atmospheric medium. The formulation of haze in realistic environment is more complicated. In this paper, we propose to take its essential mechanism as "black box", and focus on learning an input-adaptive trainable end-to-end dehazing model. An U-Net like encoder-decoder deep network via progressive feature fusions has been proposed to directly learn highly nonlinear transformation function from observed hazy image to haze-free ground-truth. The proposed network is evaluated on two public image dehazing benchmarks. The experiments demonstrate that it can achieve superior performance when compared with popular state-of-the-art methods. With efficient GPU memory usage, it can satisfactorily recover ultra high definition hazed image up to 4K resolution, which is unaffordable by many deep learning based dehazing algorithms.
Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications
Venue: arXiv cs.DS 2018
Year: 2018

In this paper we provide nearly linear time algorithms for several problems closely associated with the classic Perron-Frobenius theorem, including computing Perron vectors, i.e. entrywise non-negative eigenvectors of non-negative matrices, and solving linear systems in asymmetric M-matrices, a generalization of Laplacian systems. The running times of our algorithms depend nearly linearly on the input size and polylogarithmically on the desired accuracy and problem condition number. Leveraging these results we also provide improved running times for a broader range of problems including computing random walk-based graph kernels, computing Katz centrality, and more. The running times of our algorithms improve upon previously known results which either depended polynomially on the condition number of the problem, required quadratic time, or only applied to special cases. We obtain these results by providing new iterative methods for reducing these problems to solving linear systems in Row-Column Diagonally Dominant (RCDD) matrices. Our methods are related to the classic shift-and-invert preconditioning technique for eigenvector computation and constitute the first alternative to the result in Cohen et al. (2016) for reducing stationary distribution computation and solving directed Laplacian systems to solving RCDD systems.
First-order interpretations of bounded expansion classes
Venue: arXiv cs.DM 2018
Year: 2018

The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with structurally bounded expansion, defined as first-order interpretations of classes of bounded expansion. As a first step towards their algorithmic treatment, we provide their characterization analogous to the characterization of classes of bounded expansion via low treedepth decompositions, replacing treedepth by its dense analogue called shrubdepth.
Comment on `Detecting Topology Variations in Networks of Linear Dynamical Systems'
Venue: arXiv cs.SY 2018
Year: 2018

Conditions for the detectability of topology variations in dynamical networks are developed in a recent article in the IEEE Transactions on Control of Network Systems [1]. Here, an example is presented which illustrates an error in the network-theoretic conditions for detectability developed in [1].
Seamless Parametrization with Arbitrarily Prescribed Cones
Venue: arXiv cs.GR 2018
Year: 2018

Seamless global parametrization of surfaces is a key operation in geometry processing, e.g. for high-quality quad mesh generation. A common approach is to prescribe the parametric domain structure, in particular the locations of parametrization singularities (cones), and solve a non-convex optimization problem minimizing a distortion measure, with local injectivity imposed through either constraints or barrier terms. In both cases, an initial valid parametrization is essential to serve as feasible starting point for obtaining an optimized solution. While convexified versions of the constraints eliminate this initialization requirement, they narrow the range of solutions, causing some problem instances that actually do have a solution to become infeasible. We demonstrate that for arbitrary given sets of topologically admissible parametric cones with prescribed curvature, a global seamless parametrization always exists (with the exception of one well-known case). Importantly, our proof is constructive and directly leads to a general algorithm for computing such parametrizations. Most distinctively, this algorithm is bootstrapped with a convex optimization problem (solving for a conformal map), in tandem with a simple linear equation system (determining a seamless modification of this map). This initial map can then serve as valid starting point and be optimized with respect to application specific distortion measures using existing injectivity preserving methods.
Service Quality Improvement of Mobile Users in Vehicular Environment by Mobile Femtocell Network Deployment
Venue: arXiv cs.NI 2018
Year: 2018

The femto-access-point (FAP), a low power small cellular base station provides better signal quality for the indoor users. The mobile users in the vehicular environment suffer for the low quality signal from the outside wireless networks. The deployment of femtocells in the vehicular environment can solve the low level signal-to-noise plus interference problem. In this paper, we propose new application of the femtocell technology. The femtocells are deployed in the vehicular environment. Short distance between the user and the FAP provides better signal quality. The inside FAPs are connected to the core network through the outside macrocellular networks or the satellite networks. One stronger transceiver is installed at outside the vehicle. This transceiver is connected to FAPs using wired connection and to macrocellular or the satellite access networks through wireless link. The capacity and the outage probability are analyzed. The simulation results show that the proposed mobile femtocell deployment significantly enhances the service quality of mobile users in the vehicular environment.
Popularity based Bandwidth Allocation for Video Broadcast/Multicast over Wireless Networks
Venue: arXiv cs.NI 2018
Year: 2018

Recently, video broadcast/multicast over wireless networks has created a significant interest in the field of wireless communication. However, the wireless resources have limitations to broadcast/multicast many video sessions at the same time with the best quality. Hence, during the video transmission through wireless networks, it is very important to make the best utilization of the limited bandwidth. When the system bandwidth is not sufficient to allocate the demanded bandwidth for all of the active broadcasting/multicasting video sessions, instead of allocating equal bandwidth to each of them, our proposed scheme allocates bandwidth per video session based on popularity of the video program. Using the mathematical and simulation analyses, we show that the proposed scheme maximizes average user satisfaction level. The simulation results also indicate that a large number of subscribers can receive a significantly improved quality of video. To improve the video quality for large number of subscribers, the only tradeoff is that a very few subscribers receive slightly degraded video quality.
An Edge-Computing Based Architecture for Mobile Augmented Reality
Venue: arXiv cs.IT 2018
Year: 2018

In order to mitigate the long processing delay and high energy consumption of mobile augmented reality (AR) applications, mobile edge computing (MEC) has been recently proposed and is envisioned as a promising means to deliver better quality of experience (QoE) for AR consumers. In this article, we first present a comprehensive AR overview, including the indispensable components of general AR applications, fashionable AR devices, and several existing techniques for overcoming the thorny latency and energy consumption problems. Then, we propose a novel hierarchical computation architecture by inserting an edge layer between the conventional user layer and cloud layer. Based on the proposed architecture, we further develop an innovated operation mechanism to improve the performance of mobile AR applications. Three key technologies are also discussed to further assist the proposed AR architecture. Simulation results are finally provided to verify that our proposals can significantly improve the latency and energy performance as compared against existing baseline schemes.