OpenRaiser/Intern-Atlas huggingface dataset:
On the Derivative Imbalance and Ambiguity of Functions
Venue: arXiv cs.IT 2018
Year: 2018

In 2007, Carlet and Ding introduced two parameters, denoted by $Nb_F$ and $NB_F$, quantifying respectively the balancedness of general functions $F$ between finite Abelian groups and the (global) balancedness of their derivatives $D_a F(x)=F(x+a)-F(x)$, $a\in G\setminus\{0\}$ (providing an indicator of the nonlinearity of the functions). These authors studied the properties and cryptographic significance of these two measures. They provided for S-boxes inequalities relating the nonlinearity $\mathcal{NL}(F)$ to $NB_F$, and obtained in particular an upper bound on the nonlinearity which unifies Sidelnikov-Chabaud-Vaudenay's bound and the covering radius bound. At the Workshop WCC 2009 and in its postproceedings in 2011, a further study of these parameters was made; in particular, the first parameter was applied to the functions $F+L$ where $L$ is affine, providing more nonlinearity parameters. In 2010, motivated by the study of Costas arrays, two parameters called ambiguity and deficiency were introduced by Panario \emph{et al.} for permutations over finite Abelian groups to measure the injectivity and surjectivity of the derivatives respectively. These authors also studied some fundamental properties and cryptographic significance of these two measures. Further studies followed without that the second pair of parameters be compared to the first one. In the present paper, we observe that ambiguity is the same parameter as $NB_F$, up to additive and multiplicative constants (i.e. up to rescaling). We make the necessary work of comparison and unification of the results on $NB_F$, respectively on ambiguity, which have been obtained in the five papers devoted to these parameters. We generalize some known results to any Abelian groups and we more importantly derive many new results on these parameters.
High-Quality Shared-Memory Graph Partitioning
Venue: arXiv cs.DS 2018
Year: 2018

Partitioning graphs into blocks of roughly equal size such that few edges run between blocks is a frequently needed operation in processing graphs. Recently, size, variety, and structural complexity of these networks has grown dramatically. Unfortunately, previous approaches to parallel graph partitioning have problems in this context since they often show a negative trade-off between speed and quality. We present an approach to multi-level shared-memory parallel graph partitioning that guarantees balanced solutions, shows high speed-ups for a variety of large graphs and yields very good quality independently of the number of cores used. For example, on 31 cores, our algorithm partitions our largest test instance into 16 blocks cutting less than half the number of edges than our main competitor when both algorithms are given the same amount of time. Important ingredients include parallel label propagation for both coarsening and improvement, parallel initial partitioning, a simple yet effective approach to parallel localized local search, and fast locality preserving hash tables.
Tensor Matched Subspace Detection
Venue: arXiv cs.NA 2018
Year: 2018

The problem of testing whether a signal lies within a given subspace, also named matched subspace detection, has been well studied when the signal is represented as a vector. However, the matched subspace detection methods based on vectors can not be applied to the situations that signals are naturally represented as multi-dimensional data arrays or tensors. Considering that tensor subspaces and orthogonal projections onto these subspaces are well defined in the recently proposed transform-based tensor model, which motivates us to investigate the problem of matched subspace detection in high dimensional case. In this paper, we propose an approach for tensor matched subspace detection based on the transform-based tensor model with tubal-sampling and elementwise-sampling, respectively. First, we construct estimators based on tubal-sampling and elementwise-sampling to estimate the energy of a signal outside a given subspace of a third-order tensor and then give the probability bounds of our estimators, which show that our estimators work effectively when the sample size is greater than a constant. Secondly, the detectors both for noiseless data and noisy data are given, and the corresponding detection performance analyses are also provided. Finally, based on discrete Fourier transform (DFT) and discrete cosine transform (DCT), the performance of our estimators and detectors are evaluated by several simulations, and simulation results verify the effectiveness of our approach.
Serving deep learning models in a serverless platform
Venue: arXiv cs.DC 2018
Year: 2018

Serverless computing has emerged as a compelling paradigm for the development and deployment of a wide range of event based cloud applications. At the same time, cloud providers and enterprise companies are heavily adopting machine learning and Artificial Intelligence to either differentiate themselves, or provide their customers with value added services. In this work we evaluate the suitability of a serverless computing environment for the inferencing of large neural network models. Our experimental evaluations are executed on the AWS Lambda environment using the MxNet deep learning framework. Our experimental results show that while the inferencing latency can be within an acceptable range, longer delays due to cold starts can skew the latency distribution and hence risk violating more stringent SLAs.
Harnessing the Power of Many: Extensible Toolkit for Scalable Ensemble Applications
Venue: arXiv cs.DC 2018
Year: 2018

Many scientific problems require multiple distinct computational tasks to be executed in order to achieve a desired solution. We introduce the Ensemble Toolkit (EnTK) to address the challenges of scale, diversity and reliability they pose. We describe the design and implementation of EnTK, characterize its performance and integrate it with two distinct exemplar use cases: seismic inversion and adaptive analog ensembles. We perform nine experiments, characterizing EnTK overheads, strong and weak scalability, and the performance of two use case implementations, at scale and on production infrastructures. We show how EnTK meets the following general requirements: (i) implementing dedicated abstractions to support the description and execution of ensemble applications; (ii) support for execution on heterogeneous computing infrastructures; (iii) efficient scalability up to O(10^4) tasks; and (iv) fault tolerance. We discuss novel computational capabilities that EnTK enables and the scientific advantages arising thereof. We propose EnTK as an important addition to the suite of tools in support of production scientific computing.
Context Aware Robot Navigation using Interactively Built Semantic Maps
Venue: arXiv cs.RO 2018
Year: 2018

We discuss the process of building semantic maps, how to interactively label entities in them, and how to use them to enable context-aware navigation behaviors in human environments. We utilize planar surfaces, such as walls and tables, and static objects, such as door signs, as features for our semantic mapping approach. Users can interactively annotate these features by having the robot follow him/her, entering the label through a mobile app, and performing a pointing gesture toward the landmark of interest. Our gesture based approach can reliably estimate which object is being pointed at and detect ambiguous gestures with probabilistic modeling. Our person following method attempts to maximize future utility by a search for future actions assuming constant velocity model for the human. We describe a method to extract metric goals from a semantic map landmark and to plan a human aware path that takes into account the personal spaces of people. Finally, we demonstrate context-awareness for person following in two scenarios: interactive labeling and door passing. We believe that future navigation approaches and service robotics applications can be made more effective by further exploiting the structure of human environments.
Near-Optimal Noisy Group Testing via Separate Decoding of Items
Venue: arXiv cs.IT 2018
Year: 2018

The group testing problem consists of determining a small set of defective items from a larger set of items based on a number of tests, and is relevant in applications such as medical testing, communication protocols, pattern matching, and more. In this paper, we revisit an efficient algorithm for noisy group testing in which each item is decoded separately (Malyutov and Mateev, 1980), and develop novel performance guarantees via an information-theoretic framework for general noise models. For the special cases of no noise and symmetric noise, we find that the asymptotic number of tests required for vanishing error probability is within a factor $\log 2 \approx 0.7$ of the information-theoretic optimum at low sparsity levels, and that with a small fraction of allowed incorrectly decoded items, this guarantee extends to all sublinear sparsity levels. In addition, we provide a converse bound showing that if one tries to move slightly beyond our low-sparsity achievability threshold using separate decoding of items and i.i.d. randomized testing, the average number of items decoded incorrectly approaches that of a trivial decoder.
Robust Photometric Stereo via Dictionary Learning
Venue: arXiv cs.CV 2018
Year: 2018

Photometric stereo is a method that seeks to reconstruct the normal vectors of an object from a set of images of the object illuminated under different light sources. While effective in some situations, classical photometric stereo relies on a diffuse surface model that cannot handle objects with complex reflectance patterns, and it is sensitive to non-idealities in the images. In this work, we propose a novel approach to photometric stereo that relies on dictionary learning to produce robust normal vector reconstructions. Specifically, we develop two formulations for applying dictionary learning to photometric stereo. We propose a model that applies dictionary learning to regularize and reconstruct the normal vectors from the images under the classic Lambertian reflectance model. We then generalize this model to explicitly model non-Lambertian objects. We investigate both approaches through extensive experimentation on synthetic and real benchmark datasets and observe state-of-the-art performance compared to existing robust photometric stereo methods.
Statistical considerations on limitations of supercomputers
Venue: arXiv cs.DC 2018
Year: 2018

Supercomputer building is a many sceene, many authors game, comprising a lot of different technologies, manufacturers and ideas. Checking data available in the public database in a systematic way, some general tendencies and limitations can be concluded, both for the past and the future. The feasibility of building exa-scale computers as well as their limitations and utilization are also discussed. The statistical considerations provide a strong support for the conclusions.
Approximate Span Liftings
Venue: arXiv cs.PL 2018
Year: 2018

We develop new abstractions for reasoning about relaxations of differential privacy: Rényi differential privacy, zero-concentrated differential privacy, and truncated concentrated differential privacy, which express different bounds on statistical divergences between two output probability distributions. In order to reason about such properties compositionally, we introduce approximate span-lifting, a novel construction extending the approximate relational lifting approaches previously developed for standard differential privacy to a more general class of divergences, and also to continuous distributions. As an application, we develop a program logic based on approximate span-liftings capable of proving relaxations of differential privacy and other statistical divergence properties.
Weighting Scheme for a Pairwise Multi-label Classifier Based on the Fuzzy Confusion Matrix
Venue: arXiv cs.LG 2018
Year: 2018

In this work we addressed the issue of applying a stochastic classifier and a local, fuzzy confusion matrix under the framework of multi-label classification. We proposed a novel solution to the problem of correcting label pairwise ensembles. The main step of the correction procedure is to compute classifier-specific competence and cross-competence measures, which estimates error pattern of the underlying classifier. At the fusion phase we employed two weighting approaches based on information theory. The classifier weights promote base classifiers which are the most susceptible to the correction based on the fuzzy confusion matrix. During the experimental study, the proposed approach was compared against two reference methods. The comparison was made in terms of six different quality criteria. The conducted experiments reveals that the proposed approach eliminates one of main drawbacks of the original FCM-based approach i.e. the original approach is vulnerable to the imbalanced class/label distribution. What is more, the obtained results shows that the introduced method achieves satisfying classification quality under all considered quality criteria. Additionally, the impact of fluctuations of data set characteristics is reduced.
Caching at Base Stations with Heterogeneous User Demands and Spatial Locality
Venue: arXiv cs.IT 2018
Year: 2018

Existing proactive caching policies are designed by assuming that all users request contents with identical activity level at uniformly-distributed or known locations, among which most of the policies are optimized by assuming that user preference is identical to content popularity. However, these assumptions are not true based on recent data analysis. In this paper, we investigate what happens without these assumptions. To this end, we establish a framework to optimize caching policy for base stations exploiting heterogeneous user preference, activity level, and spatial locality. We derive success probability and average rate of each user as utility function, respectively, and obtain the optimal caching policy maximizing a weighted sum of average utility (reflecting network performance) and minimal utility of users (reflecting user fairness). To investigate the intertwined impact of individual user request behavior on caching, we provide an algorithm to synthesize user preference from given content popularity and activity level with controlled preference similarity, and validate the algorithm with real datasets. Analysis and simulation results show that exploiting individual user behavior can improve both network performance and user fairness, and the gain increases with the skewness of spatial locality, and the heterogeneity of user preference and activity level.
Investigation of Frame Alignments for GMM-based Digit-prompted Speaker Verification
Venue: arXiv cs.SD 2018
Year: 2018

Frame alignments can be computed by different methods in GMM-based speaker verification. By incorporating a phonetic Gaussian mixture model (PGMM), we are able to compare the performance using alignments extracted from the deep neural networks (DNN) and the conventional hidden Markov model (HMM) in digit-prompted speaker verification. Based on the different characteristics of these two alignments, we present a novel content verification method to improve the system security without much computational overhead. Our experiments on the RSR2015 Part-3 digit-prompted task show that, the DNN based alignment performs on par with the HMM alignment. The results also demonstrate the effectiveness of the proposed Kullback-Leibler (KL) divergence based scoring to reject speech with incorrect pass-phrases.
Intelligent Interference Exploitation for Heterogeneous Cellular Networks against Eavesdropping
Venue: arXiv cs.IT 2018
Year: 2018

This paper explores the co-existence of a macro cell and a small cell for heterogeneous cellular networks, where a macro base station (MBS) and small base station (SBS) transmit to respective macro user (MU) and small user (SU) through their shared spectrum in the face of a common eavesdropper. We consider two spectrum sharing mechanisms, namely the overlay spectrum sharing (OSS) and underlay spectrum sharing (USS). In the OSS, MBS and SBS take turns to access their shared spectrum. By contrast, the USS allows MBS and SBS to simultaneously transmit over the shared spectrum with the aid of power control for limiting their mutual interference, thus called interference-limited USS (IL-USS). In order to take advantage of mutual interference in confusing the eavesdropper without causing adverse effect on the MU, we propose an interference-canceled USS (IC-USS) scheme. Closed-form expressions of overall outage probability and intercept probability are derived for OSS, IL-USS and IC-USS schemes by taking into account both MBS-MU and SBS-SU transmissions. The secrecy diversity analysis is also carried out by characterizing an asymptotic behavior of the overall outage probability with a given intercept probability in the high signal-to-noise ratio region. It is shown that the secrecy diversity gains of conventional OSS and IL-USS are zero, whereas the proposed IC-USS achieves a higher secrecy diversity gain of one. This implies that with an arbitrarily low overall intercept probability, the conventional OSS and IL-USS methods converge to their respective outage probability floors, however the proposed IC-USS scheme can make the overall outage probability asymptotically decrease to zero by simply increasing the transmit power. Additionally, numerical results demonstrate an obvious advantage of the proposed IC-USS over OSS and IL-USS against eavesdropping.
Exact Topology and Parameter Estimation in Distribution Grids with Minimal Observability
Venue: arXiv cs.SY 2018
Year: 2018

Limited presence of nodal and line meters in distribution grids hinders their optimal operation and participation in real-time markets. In particular lack of real-time information on the grid topology and infrequently calibrated line parameters (impedances) adversely affect the accuracy of any operational power flow control. This paper suggests a novel algorithm for learning the topology of distribution grid and estimating impedances of the operational lines with minimal observational requirements - it provably reconstructs topology and impedances using voltage and injection measured only at the terminal (end-user) nodes of the distribution grid. All other (intermediate) nodes in the network may be unobserved/hidden. Furthermore no additional input (e.g., number of grid nodes, historical information on injections at hidden nodes) is needed for the learning to succeed. Performance of the algorithm is illustrated in numerical experiments on the IEEE and custom power distribution models.
Integrating Small Satellite Communication in an Autonomous Vehicle Network: A Case for Oceanography
Venue: arXiv cs.NI 2018
Year: 2018

Small satellites and autonomous vehicles have greatly evolved in the last few decades. Hundreds of small satellites have been launched with increasing functionalities, in the last few years. Likewise, numerous autonomous vehicles have been built, with decreasing costs and form-factor payloads. Here we focus on combining these two multifaceted assets in an incremental way, with an ultimate goal of alleviating the logistical expenses in remote oceanographic operations. The first goal is to create a highly reliable and constantly available communication link for a network of autonomous vehicles, taking advantage of the small satellite lower cost, with respect to conventional spacecraft, and its higher flexibility. We have developed a test platform as a proving ground for this network, by integrating a satellite software defined radio on an unmanned air vehicle, creating a system of systems, and several tests have been run successfully, over land. As soon as the satellite is fully operational, we will start to move towards a cooperative network of autonomous vehicles and small satellites, with application in maritime operations, both \textit{in-situ} and remote sensing.
Machine Translation of Low-Resource Spoken Dialects: Strategies for Normalizing Swiss German
Venue: arXiv cs.CL 2018
Year: 2018

The goal of this work is to design a machine translation (MT) system for a low-resource family of dialects, collectively known as Swiss German, which are widely spoken in Switzerland but seldom written. We collected a significant number of parallel written resources to start with, up to a total of about 60k words. Moreover, we identified several other promising data sources for Swiss German. Then, we designed and compared three strategies for normalizing Swiss German input in order to address the regional diversity. We found that character-based neural MT was the best solution for text normalization. In combination with phrase-based statistical MT, our solution reached 36% BLEU score when translating from the Bernese dialect. This value, however, decreases as the testing data becomes more remote from the training one, geographically and topically. These resources and normalization techniques are a first step towards full MT of Swiss German dialects.
Grad-CAM++: Improved Visual Explanations for Deep Convolutional Networks
Venue: arXiv cs.CV 2018
Year: 2018

Over the last decade, Convolutional Neural Network (CNN) models have been highly successful in solving complex vision problems. However, these deep models are perceived as "black box" methods considering the lack of understanding of their internal functioning. There has been a significant recent interest in developing explainable deep learning models, and this paper is an effort in this direction. Building on a recently proposed method called Grad-CAM, we propose a generalized method called Grad-CAM++ that can provide better visual explanations of CNN model predictions, in terms of better object localization as well as explaining occurrences of multiple object instances in a single image, when compared to state-of-the-art. We provide a mathematical derivation for the proposed method, which uses a weighted combination of the positive partial derivatives of the last convolutional layer feature maps with respect to a specific class score as weights to generate a visual explanation for the corresponding class label. Our extensive experiments and evaluations, both subjective and objective, on standard datasets showed that Grad-CAM++ provides promising human-interpretable visual explanations for a given CNN architecture across multiple tasks including classification, image caption generation and 3D action recognition; as well as in new settings such as knowledge distillation.