OpenRaiser/Intern-Atlas huggingface dataset:
Feature-Sharing in Cascade Detection Systems with Multiple Applications
Venue: arXiv cs.SY 2017
Year: 2017

Traditional distributed detection systems are often designed for a single target application. However, with the emergence of the Internet of Things (IoT) paradigm, next-generation systems are expected to be a shared infrastructure for multiple applications. To this end, we propose a modular, cascade design for resource-efficient, multi-task detection systems. Two (classes of) applications are considered in the system, a primary and a secondary one. The primary application has universal features that can be shared with other applications, to reduce the overall feature extraction cost, while the secondary application does not. In this setting, the two applications can collaborate via feature sharing. We provide a method to optimize the operation of the multi-application cascade system based on an accurate resource consumption model. In addition, the inherent uncertainties in feature models are articulated and taken into account. For evaluation, the twin-comparison argument is invoked, and it is shown that, with the optimal feature sharing strategy, a system can achieve 9$\times$ resource saving and 1.43$\times$ improvement in detection performance.
Determinantal Point Processes for Mini-Batch Diversification
Venue: arXiv cs.LG 2017
Year: 2017

We study a mini-batch diversification scheme for stochastic gradient descent (SGD). While classical SGD relies on uniformly sampling data points to form a mini-batch, we propose a non-uniform sampling scheme based on the Determinantal Point Process (DPP). The DPP relies on a similarity measure between data points and gives low probabilities to mini-batches which contain redundant data, and higher probabilities to mini-batches with more diverse data. This simultaneously balances the data and leads to stochastic gradients with lower variance. We term this approach Diversified Mini-Batch SGD (DM-SGD). We show that regular SGD and a biased version of stratified sampling emerge as special cases. Furthermore, DM-SGD generalizes stratified sampling to cases where no discrete features exist to bin the data into groups. We show experimentally that our method results more interpretable and diverse features in unsupervised setups, and in better classification accuracies in supervised setups.
Galois LCD Codes over Finite Fields
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we study the complementary dual codes in more general setting (which are called Galois LCD codes) by a uniform method. A necessary and sufficient condition for linear codes to be Galois LCD codes is determined, and constacyclic codes to be Galois LCD codes are characterized. Some illustrative examples which constacyclic codes are Galois LCD MDS codes are provided as well. In particular, we study Hermitian LCD constacyclic codes. Finally, we present a construction of a class of Hermitian LCD codes which are also MDS codes.
Lesion detection and Grading of Diabetic Retinopathy via Two-stages Deep Convolutional Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

We propose an automatic diabetic retinopathy (DR) analysis algorithm based on two-stages deep convolutional neural networks (DCNN). Compared to existing DCNN-based DR detection methods, the proposed algorithm have the following advantages: (1) Our method can point out the location and type of lesions in the fundus images, as well as giving the severity grades of DR. Moreover, since retina lesions and DR severity appear with different scales in fundus images, the integration of both local and global networks learn more complete and specific features for DR analysis. (2) By introducing imbalanced weighting map, more attentions will be given to lesion patches for DR grading, which significantly improve the performance of the proposed algorithm. In this study, we label 12,206 lesion patches and re-annotate the DR grades of 23,595 fundus images from Kaggle competition dataset. Under the guidance of clinical ophthalmologists, the experimental results show that our local lesion detection net achieve comparable performance with trained human observers, and the proposed imbalanced weighted scheme also be proved to significantly improve the capability of our DCNN-based DR grading algorithm.
Automated Analysis of Voting Systems under an Active Intruder Model in CSP
Venue: arXiv cs.CR 2017
Year: 2017

This article presents a novel intruder model for automated reasoning about anonymity (vote-privacy) and secrecy properties of voting systems. We adapt the lazy spy for this purpose, as it avoids the eagerness of pre-computation of unnecessary deductions, reducing the required state space for the analysis. This powerful intruder behaves as a Dolev-Yao intruder, which not only observes a protocol run but also interacts with the protocol participants, overhears communication channels, intercepts and spoofs any messages that he has learned or generated from any prior knowledge. We make several important modifications in relation to existing channel types and the deductive system. For the former, we define various channel types for different threat models. For the latter, we construct a large deductive system over the space of messages transmitted in the voting system model. The model represents the first formal treatment of the vVote system, which was used in November 2014, in state elections in Victoria, Australia.
Clifford Gates in the Holant Framework
Venue: arXiv cs.CC 2017
Year: 2017

We show that the Clifford gates and stabilizer circuits in the quantum computing literature, which admit efficient classical simulation, are equivalent to affine signatures under a unitary condition. The latter is a known class of tractable functions under the Holant framework.
Sonata: Query-Driven Network Telemetry
Venue: arXiv cs.NI 2017
Year: 2017

Operating networks depends on collecting and analyzing measurement data. Current technologies do not make it easy to do so, typically because they separate data collection (e.g., packet capture or flow monitoring) from analysis, producing either too much data to answer a general question or too little data to answer a detailed question. In this paper, we present Sonata, a network telemetry system that uses a uniform query interface to drive the joint collection and analysis of network traffic. Sonata takes the advantage of two emerging technologies---streaming analytics platforms and programmable network devices---to facilitate joint collection and analysis. Sonata allows operators to more directly express network traffic analysis tasks in terms of a high-level language. The underlying runtime partitions each query into a portion that runs on the switch and another that runs on the streaming analytics platform iteratively refines the query to efficiently capture only the traffic that pertains to the operator's query, and exploits sketches to reduce state in switches in exchange for more approximate results. Through an evaluation of a prototype implementation, we demonstrate that Sonata can support a wide range of network telemetry tasks with less state in the network, and lower data rates to streaming analytics systems, than current approaches can achieve.
Correcting for Non-Markovian Asymptotic Effects using Markovian Representation
Venue: arXiv cs.PF 2017
Year: 2017

Asymptotic properties of Markov Processes, such as steady state probabilities or hazard rate for absorbing states can be efficiently calculated by means of linear algebra even for large-scale problems. This paper discusses the methods for adjusting parameters of the Markov models to account for non-constant transition rates. In particular, transitions with fixed delays are considered along with the transitions that follow Weibull and lognormal distributions. Procedures for both steady-state solutions in the absence of an absorbing state, and for hazard rates to an absorbing state are provided and demonstrated on several examples.
The Iray Light Transport Simulation and Rendering System
Venue: arXiv cs.GR 2017
Year: 2017

While ray tracing has become increasingly common and path tracing is well understood by now, a major challenge lies in crafting an easy-to-use and efficient system implementing these technologies. Following a purely physically-based paradigm while still allowing for artistic workflows, the Iray light transport simulation and rendering system allows for rendering complex scenes by the push of a button and thus makes accurate light transport simulation widely available. In this document we discuss the challenges and implementation choices that follow from our primary design decisions, demonstrating that such a rendering system can be made a practical, scalable, and efficient real-world application that has been adopted by various companies across many fields and is in use by many industry professionals today.
Quantified advantage of discontinuous weight selection in approximations with deep neural networks
Venue: arXiv cs.NE 2017
Year: 2017

We consider approximations of 1D Lipschitz functions by deep ReLU networks of a fixed width. We prove that without the assumption of continuous weight selection the uniform approximation error is lower than with this assumption at least by a factor logarithmic in the size of the network.
Experimental Comparison of Probabilistic Shaping Methods for Unrepeated Fiber Transmission
Venue: arXiv cs.IT 2017
Year: 2017

This paper studies the impact of probabilistic shaping on effective signal-to-noise ratios (SNRs) and achievable information rates (AIRs) in a back-to-back configuration and in unrepeated nonlinear fiber transmissions. For back-to-back, various shaped quadrature amplitude modulation (QAM) distributions are found to have the same implementation penalty as uniform input. By demonstrating in transmission experiments that shaped QAM input leads to lower effective SNR than uniform input at a fixed average launch power, we experimentally confirm that shaping enhances the fiber nonlinearities. However, shaping is ultimately found to increase the AIR, which is the most relevant figure of merit as it is directly related to spectral efficiency. In a detailed study of these shaping gains for the nonlinear fiber channel, four strategies for optimizing QAM input distributions are evaluated and experimentally compared in wavelength division multiplexing (WDM) systems. The first shaping scheme generates a Maxwell-Boltzmann (MB) distribution based on a linear additive white Gaussian noise channel. The second strategy uses the Blahut-Arimoto algorithm to optimize an unconstrained QAM distribution for a split-step Fourier method based channel model. In the third and fourth approach, MB-shaped QAM and unconstrained QAM are optimized via the enhanced Gaussian noise (EGN) model. Although the absolute shaping gains are found to be relatively small, the relative improvements by EGN-optimized unconstrained distributions over linear AWGN optimized MB distributions are up to 59%. This general behavior is observed in 9-channel and fully loaded WDM experiments.
Fast Real-Time DC State Estimation in Electric Power Systems Using Belief Propagation
Venue: arXiv cs.IT 2017
Year: 2017

We propose a fast real-time state estimator based on the belief propagation algorithm for the power system state estimation. The proposed estimator is easy to distribute and parallelize, thus alleviating computational limitations and allowing for processing measurements in real time. The presented algorithm may run as a continuous process, with each new measurement being seamlessly processed by the distributed state estimator. In contrast to the matrix-based state estimation methods, the belief propagation approach is robust to ill-conditioned scenarios caused by significant differences between measurement variances, thus resulting in a solution that eliminates observability analysis. Using the DC model, we numerically demonstrate the performance of the state estimator in a realistic real-time system model with asynchronous measurements. We note that the extension to the AC state estimation is possible within the same framework.
Ternary Neural Networks with Fine-Grained Quantization
Venue: arXiv cs.LG 2017
Year: 2017

We propose a novel fine-grained quantization (FGQ) method to ternarize pre-trained full precision models, while also constraining activations to 8 and 4-bits. Using this method, we demonstrate a minimal loss in classification accuracy on state-of-the-art topologies without additional training. We provide an improved theoretical formulation that forms the basis for a higher quality solution using FGQ. Our method involves ternarizing the original weight tensor in groups of $N$ weights. Using $N=4$, we achieve Top-1 accuracy within $3.7\%$ and $4.2\%$ of the baseline full precision result for Resnet-101 and Resnet-50 respectively, while eliminating $75\%$ of all multiplications. These results enable a full 8/4-bit inference pipeline, with best-reported accuracy using ternary weights on ImageNet dataset, with a potential of $9\times$ improvement in performance. Also, for smaller networks like AlexNet, FGQ achieves state-of-the-art results. We further study the impact of group size on both performance and accuracy. With a group size of $N=64$, we eliminate $\approx99\%$ of the multiplications; however, this introduces a noticeable drop in accuracy, which necessitates fine tuning the parameters at lower precision. We address this by fine-tuning Resnet-50 with 8-bit activations and ternary weights at $N=64$, improving the Top-1 accuracy to within $4\%$ of the full precision result with $<30\%$ additional training overhead. Our final quantized model can run on a full 8-bit compute pipeline using 2-bit weights and has the potential of up to $15\times$ improvement in performance compared to baseline full-precision models.
The Homogeneous Broadcast Problem in Narrow and Wide Strips
Venue: arXiv cs.CG 2017
Year: 2017

Let $P$ be a set of nodes in a wireless network, where each node is modeled as a point in the plane, and let $s\in P$ be a given source node. Each node $p$ can transmit information to all other nodes within unit distance, provided $p$ is activated. The (homogeneous) broadcast problem is to activate a minimum number of nodes such that in the resulting directed communication graph, the source $s$ can reach any other node. We study the complexity of the regular and the hop-bounded version of the problem (in the latter, $s$ must be able to reach every node within a specified number of hops), with the restriction that all points lie inside a strip of width $w$. We almost completely characterize the complexity of both the regular and the hop-bounded versions as a function of the strip width $w$.
Sustaining Moore's Law Through Inexactness
Venue: arXiv cs.CC 2017
Year: 2017

Inexact computing aims to compute good solutions that require considerably less resource -- typically energy -- compared to computing exact solutions. While inexactness is motivated by concerns derived from technology scaling and Moore's law, there is no formal or foundational framework for reasoning about this novel approach to designing algorithms. In this work, we present a fundamental relationship between the quality of computing the value of a boolean function and the energy needed to compute it in a mathematically rigorous and general setting. On this basis, one can study the tradeoff between the quality of the solution to a problem and the amount of energy that is consumed. We accomplish this by introducing a computational model to classify problems based on notions of symmetry inspired by physics. We show that some problems are symmetric in that every input bit is, in a sense, equally important, while other problems display a great deal of asymmetry in the importance of input bits. We believe that our model is novel and provides a foundation for inexact Computing. Building on this, we show that asymmetric problems allow us to invest resources favoring the important bits -- a feature that can be leveraged to design efficient inexact algorithms. On the negative side and in contrast, we can prove that the best inexact algorithms for symmetric problems are no better than simply reducing the resource investment uniformly across all bits. Akin to classical theories concerned with space and time complexity, we believe the ability to classify problems as shown in our paper will serve as a basis for formally reasoning about the effectiveness of inexactness in the context of a range of computational problems with energy being the primary resource.
Neural Models for Information Retrieval
Venue: arXiv cs.IR 2017
Year: 2017

Neural ranking models for information retrieval (IR) use shallow or deep neural networks to rank search results in response to a query. Traditional learning to rank models employ machine learning techniques over hand-crafted IR features. By contrast, neural models learn representations of language from raw text that can bridge the gap between query and document vocabulary. Unlike classical IR models, these new machine learning based approaches are data-hungry, requiring large scale training data before they can be deployed. This tutorial introduces basic concepts and intuitions behind neural IR models, and places them in the context of traditional retrieval models. We begin by introducing fundamental concepts of IR and different neural and non-neural approaches to learning vector representations of text. We then review shallow neural IR methods that employ pre-trained neural term embeddings without learning the IR task end-to-end. We introduce deep neural networks next, discussing popular deep architectures. Finally, we review the current DNN models for information retrieval. We conclude with a discussion on potential future directions for neural IR.
Hybrid Urban Navigation for Smart Cities
Venue: arXiv cs.SY 2017
Year: 2017

This paper proposes a design for a hybrid, city-wide urban navigation system for moving agents demanding dedicated assistance. The hybrid system combines GPS and vehicle-to-vehicle communication from an ad-hoc network of parked cars, and RFID from fixed infrastructure -such as smart traffic lights- to enable a safely navigable city. Applications for such a system include high-speed drone navigation and directing visually impaired pedestrians.
Restart-Based Security Mechanisms for Safety-Critical Embedded Systems
Venue: arXiv cs.CR 2017
Year: 2017

Many physical plants that are controlled by embedded systems have safety requirements that need to be respected at all times - any deviations from expected behavior can result in damage to the system (often to the physical plant), the environment or even endanger human life. In recent times, malicious attacks against such systems have increased - many with the intent to cause physical damage. In this paper, we aim to decouple the safety of the plant from security of the embedded system by taking advantage of the inherent inertia in such systems. In this paper we present a system-wide restart-based framework that combines hardware and software components to (a) maintain the system within the safety region and (b) thwart potential attackers from destabilizing the system. We demonstrate the feasibility of our approach using two realistic systems - an actual 3 degree of freedom (3-DoF) helicopter and a simulated warehouse temperature control unit. Our proof-of-concept implementation is tested against multiple emulated attacks on the control units of these systems.
A Fast Causal Profiler for Task Parallel Programs
Venue: arXiv cs.PL 2017
Year: 2017

This paper proposes TASKPROF, a profiler that identifies parallelism bottlenecks in task parallel programs. It leverages the structure of a task parallel execution to perform fine-grained attribution of work to various parts of the program. TASKPROF's use of hardware performance counters to perform fine-grained measurements minimizes perturbation. TASKPROF's profile execution runs in parallel using multi-cores. TASKPROF's causal profile enables users to estimate improvements in parallelism when a region of code is optimized even when concrete optimizations are not yet known. We have used TASKPROF to isolate parallelism bottlenecks in twenty three applications that use the Intel Threading Building Blocks library. We have designed parallelization techniques in five applications to in- crease parallelism by an order of magnitude using TASKPROF. Our user study indicates that developers are able to isolate performance bottlenecks with ease using TASKPROF.
Demonstrating research subcommunities in mathematical networks
Venue: arXiv cs.SI 2017
Year: 2017

We propose a method for demonstrating sub community structure in scientific networks of relatively small size from analyzing databases of publications. Research relationships between the network members can be visualized as a graph with vertices corresponding to authors and with edges indicating joint authorship. Using a fast clustering algorithm combined with a graph layout algorithm, we demonstrate how to display these clustering results in an attractive and informative way. The small size of the graph allows us to develop tools that keep track of how these research sub communities evolve in time, as well as to present the research articles that create the links between the network members. These tools are included in a web app, where the visitor can easily identify the various sub communities, providing also valuable information for administrational purposes. Our method was developed for the GEAR mathematical network and it can be applied to other networks.
Generative Convolutional Networks for Latent Fingerprint Reconstruction
Venue: arXiv cs.CV 2017
Year: 2017

Performance of fingerprint recognition depends heavily on the extraction of minutiae points. Enhancement of the fingerprint ridge pattern is thus an essential pre-processing step that noticeably reduces false positive and negative detection rates. A particularly challenging setting is when the fingerprint images are corrupted or partially missing. In this work, we apply generative convolutional networks to denoise visible minutiae and predict the missing parts of the ridge pattern. The proposed enhancement approach is tested as a pre-processing step in combination with several standard feature extraction methods such as MINDTCT, followed by biometric comparison using MCC and BOZORTH3. We evaluate our method on several publicly available latent fingerprint datasets captured using different sensors.
Compile-Time Symbolic Differentiation Using C++ Expression Templates
Venue: arXiv cs.SC 2017
Year: 2017

Template metaprogramming is a popular technique for implementing compile time mechanisms for numerical computing. We demonstrate how expression templates can be used for compile time symbolic differentiation of algebraic expressions in C++ computer programs. Given a positive integer $N$ and an algebraic function of multiple variables, the compiler generates executable code for the $N$th partial derivatives of the function. Compile-time simplification of the derivative expressions is achieved using recursive templates. A detailed analysis indicates that current C++ compiler technology is already sufficient for practical use of our results, and highlights a number of issues where further improvements may be desirable.
Uncountable realtime probabilistic classes
Venue: arXiv cs.CC 2017
Year: 2017

We investigate the minimum cases for realtime probabilistic machines that can define uncountably many languages with bounded error. We show that logarithmic space is enough for realtime PTMs on unary languages. On binary case, we follow the same result for double logarithmic space, which is tight. When replacing the worktape with some limited memories, we can follow uncountable results on unary languages for two counters.