OpenRaiser/Intern-Atlas huggingface dataset:
Treating Content Delivery in Multi-Antenna Coded Caching as General Message Sets Transmission: A DoF Region Perspective
Venue: arXiv cs.IT 2019
Year: 2019

Coded caching can create coded multicasting thus significantly accelerates content delivery in broadcast channels with receiver caches. While the original delivery scheme in coded caching multicasts each coded message sequentially, it is not optimal for multiple-input multiple-output (MIMO) broadcast channels. This work aims to investigate the full spatial multiplexing gain in multi-antenna coded caching by transmitting all coded messages concurrently. In specific, we propose to treat the content delivery as the transmission problem with general message sets where all possible messages are present, each with different length and intended for different user set. We first obtain inner and outer bounds of the degrees of freedom (DoF) region of a $K$-user $(M,N)$ broadcast channel with general message sets, with $M$ and $N$ being the number of transmit and receive antennas, respectively. Then for any given set of coded messages, we find its minimum normalized delivery time (NDT) by searching the optimal DoF tuple in the DoF regions. The obtained minimum NDT is optimal at antenna configuration $\frac{M}{N} \in (0,1]\cup[K, \infty)$ and is within a multiplicative gap of $\frac{M}{N}$ to optimum at $\frac{M}{N} \in (1,K)$. Our NDT results can be evaluated for any user demand with both centralized and decentralized cache placement.
Benchmarking Neural Network Robustness to Common Corruptions and Surface Variations
Venue: arXiv cs.LG 2019
Year: 2019

In this paper we establish rigorous benchmarks for image classifier robustness. Our first benchmark, ImageNet-C, standardizes and expands the corruption robustness topic, while showing which classifiers are preferable in safety-critical applications. Unlike recent robustness research, this benchmark evaluates performance on commonplace corruptions not worst-case adversarial corruptions. We find that there are negligible changes in relative corruption robustness from AlexNet to ResNet classifiers, and we discover ways to enhance corruption robustness. Then we propose a new dataset called Icons-50 which opens research on a new kind of robustness, surface variation robustness. With this dataset we evaluate the frailty of classifiers on new styles of known objects and unexpected instances of known classes. We also demonstrate two methods that improve surface variation robustness. Together our benchmarks may aid future work toward networks that learn fundamental class structure and also robustly generalize.
A survey on policy search algorithms for learning robot controllers in a handful of trials
Venue: arXiv cs.RO 2019
Year: 2019

Most policy search algorithms require thousands of training episodes to find an effective policy, which is often infeasible with a physical robot. This survey article focuses on the extreme other end of the spectrum: how can a robot adapt with only a handful of trials (a dozen) and a few minutes? By analogy with the word "big-data", we refer to this challenge as "micro-data reinforcement learning". We show that a first strategy is to leverage prior knowledge on the policy structure (e.g., dynamic movement primitives), on the policy parameters (e.g., demonstrations), or on the dynamics (e.g., simulators). A second strategy is to create data-driven surrogate models of the expected reward (e.g., Bayesian optimization) or the dynamical model (e.g., model-based policy search), so that the policy optimizer queries the model instead of the real system. Overall, all successful micro-data algorithms combine these two strategies by varying the kind of model and prior knowledge. The current scientific challenges essentially revolve around scaling up to complex robots (e.g., humanoids), designing generic priors, and optimizing the computing time.
Multi-Scale Coarse-to-Fine Segmentation for Screening Pancreatic Ductal Adenocarcinoma
Venue: arXiv cs.CV 2019
Year: 2019

We propose an intuitive approach of detecting pancreatic ductal adenocarcinoma (PDAC), the most common type of pancreatic cancer, by checking abdominal CT scans. Our idea is named multi-scale segmentation-for-classification, which classifies volumes by checking if at least a sufficient number of voxels is segmented as tumors, by which we can provide radiologists with tumor locations. In order to deal with tumors with different scales, we train and test our volumetric segmentation networks with multi-scale inputs in a coarse-to-fine flowchart. A post-processing module is used to filter out outliers and reduce false alarms. We collect a new dataset containing 439 CT scans, in which 136 cases were diagnosed with PDAC and 303 cases are normal, which is the largest set for PDAC tumors to the best of our knowledge. To offer the best trade-off between sensitivity and specificity, our proposed framework reports a sensitivity of 94.1% at a specificity of 98.5%, which demonstrates the potential to make a clinical impact.
Learning to Index for Nearest Neighbor Search
Venue: arXiv cs.IR 2019
Year: 2019

In this study, we present a novel ranking model based on learning neighborhood relationships embedded in the index space. Given a query point, conventional approximate nearest neighbor search calculates the distances to the cluster centroids, before ranking the clusters from near to far based on the distances. The data indexed in the top-ranked clusters are retrieved and treated as the nearest neighbor candidates for the query. However, the loss of quantization between the data and cluster centroids will inevitably harm the search accuracy. To address this problem, the proposed model ranks clusters based on their nearest neighbor probabilities rather than the query-centroid distances. The nearest neighbor probabilities are estimated by employing neural networks to characterize the neighborhood relationships, i.e., the density function of nearest neighbors with respect to the query. The proposed probability-based ranking can replace the conventional distance-based ranking for finding candidate clusters, and the predicted probability can be used to determine the data quantity to be retrieved from the candidate cluster. Our experimental results demonstrated that the proposed ranking model could boost the search performance effectively in billion-scale datasets.
Fuzzy Logic Interpretation of Quadratic Networks
Venue: arXiv cs.NE 2019
Year: 2019

Over past several years, deep learning has achieved huge successes in various applications. However, such a data-driven approach is often criticized for lack of interpretability. Recently, we proposed artificial quadratic neural networks consisting of second-order neurons in potentially many layers. In each second-order neuron, a quadratic function is used in the place of the inner product in a traditional neuron, and then undergoes a nonlinear activation. With a single second-order neuron, any fuzzy logic operation, such as XOR, can be implemented. In this sense, any deep network constructed with quadratic neurons can be interpreted as a deep fuzzy logic system. Since traditional neural networks and second-order counterparts can represent each other and fuzzy logic operations are naturally implemented in second-order neural networks, it is plausible to explain how a deep neural network works with a second-order network as the system model. In this paper, we generalize and categorize fuzzy logic operations implementable with individual second-order neurons, and then perform statistical/information theoretic analyses of exemplary quadratic neural networks.
Developing Brain Atlas through Deep Learning
Venue: arXiv cs.CV 2019
Year: 2019

Neuroscientists have devoted significant effort into the creation of standard brain reference atlases for high-throughput registration of anatomical regions of interest. However, variability in brain size and form across individuals poses a significant challenge for such reference atlases. To overcome these limitations, we introduce a fully automated deep neural network-based method (SeBRe) for registration through Segmenting Brain Regions of interest with minimal human supervision. We demonstrate the validity of our method on brain images from different mouse developmental time points, across a range of neuronal markers and imaging modalities. We further assess the performance of our method on images from MR-scanned human brains. Our registration method can accelerate brain-wide exploration of region-specific changes in brain development and, by simply segmenting brain regions of interest for high-throughput brain-wide analysis, provides an alternative to existing complex brain registration techniques.
Computing Height Persistence and Homology Generators in $\mathbb{R}^3$ Efficiently
Venue: arXiv cs.CG 2019
Year: 2019

Recently it has been shown that computing the dimension of the first homology group $H_1(K)$ of a simplicial $2$-complex $K$ embedded linearly in $\mathbb{R}^4$ is as hard as computing the rank of a sparse $0-1$ matrix. This puts a major roadblock to computing persistence and a homology basis (generators) for complexes embedded in $\mathbb{R}^4$ and beyond in less than quadratic or even near-quadratic time. But, what about dimension three? It is known that persistence for piecewise linear functions on a complex $K$ with $n$ simplices can be computed in $O(n\log n)$ time and a set of generators of total size $k$ can be computed in $O(n+k)$ time when $K$ is a graph or a surface linearly embedded in $\mathbb{R}^3$. But, the question for general simplicial complexes $K$ linearly embedded in $\mathbb{R}^3$ is not completely settled. No algorithm with a complexity better than that of the matrix multiplication is known for this important case. We show that the persistence for {\em height functions} on such complexes, hence called {\em height persistence}, can be computed in $O(n\log n)$ time. This allows us to compute a basis (generators) of $H_i(K)$, $i=1,2$, in $O(n\log n+k)$ time where $k$ is the size of the output. This improves significantly the current best bound of $O(n^ω)$, $ω$ being the matrix multiplication exponent. We achieve these improved bounds by leveraging recent results on zigzag persistence in computational topology, new observations about Reeb graphs, and some efficient geometric data structures.
Dynamic Allocation of Serverless Functions in IoT Environments
Venue: arXiv cs.DC 2019
Year: 2019

The IoT area has grown significantly in the last few years and is expected to reach a gigantic amount of 50 billion devices by 2020. The appearance of serverless architectures, specifically highlighting FaaS, raises the question of the of using such in IoT environments. Combining IoT with a serverless architectural design can be effective when trying to make use of the local processing power that exists in a local network of IoT devices and creating a fog layer that leverages computational capabilities that are closer to the end-user. In this approach, which is placed between the device and the serverless function, when a device requests for the execution of a serverless function will decide based on previous metrics of execution if the serverless function should be executed locally, in the fog layer of a local network of IoT devices, or if it should be executed remotely, in one of the available cloud servers. Therefore, this approach allows to dynamically allocating functions to the most suitable layer.
Paradoxes in Sequential Voting
Venue: arXiv cs.GT 2019
Year: 2019

We analyse strategic, complete information, sequential voting with ordinal preferences over the alternatives. We consider several voting mechanisms: plurality voting and approval voting with deterministic or uniform tie-breaking rules. We show that strategic voting in these voting procedures may lead to a very undesirable outcome: Condorcet winning alternative might be rejected, Condorcet losing alternative might be elected, and Pareto dominated alternative might be elected. These undesirable phenomena occur already with four alternatives and a small number of voters. For the case of three alternatives we present positive and negative results.
Exploiting statistical dependencies of time series with hierarchical correlation reconstruction
Venue: arXiv cs.LG 2019
Year: 2019

While we are usually focused on forecasting future values of time series, it is often valuable to additionally predict their entire probability distributions, e.g. to evaluate risk, Monte Carlo simulations. On example of time series of $\approx$ 30000 Dow Jones Industrial Averages, there will be presented application of hierarchical correlation reconstruction for this purpose: MSE estimating polynomial as joint density for (current value, context), where context is for example a few previous values. Then substituting the currently observed context and normalizing density to 1, we get predicted probability distribution for the current value. In contrast to standard machine learning approaches like neural networks, optimal polynomial coefficients here have inexpensive direct formula, have controllable accuracy, are unique and independently calculated, each has a specific cumulant-like interpretation, and such approximation can asymptotically approach complete description of any real joint distribution - providing universal tool to quantitatively describe and exploit statistical dependencies in time series, systematically enhancing ARMA/ARCH-like approaches, also based on different distributions than Gaussian which turns out improper for daily log returns. There is also discussed application for non-stationary time series like calculating linear time trend, or adapting coefficients to local statistical behavior.
A quantum-inspired classical algorithm for recommendation systems
Venue: arXiv cs.IR 2019
Year: 2019

We give a classical analogue to Kerenidis and Prakash's quantum recommendation system, previously believed to be one of the strongest candidates for provably exponential speedups in quantum machine learning. Our main result is an algorithm that, given an $m \times n$ matrix in a data structure supporting certain $\ell^2$-norm sampling operations, outputs an $\ell^2$-norm sample from a rank-$k$ approximation of that matrix in time $O(\text{poly}(k)\log(mn))$, only polynomially slower than the quantum algorithm. As a consequence, Kerenidis and Prakash's algorithm does not in fact give an exponential speedup over classical algorithms. Further, under strong input assumptions, the classical recommendation system resulting from our algorithm produces recommendations exponentially faster than previous classical systems, which run in time linear in $m$ and $n$. The main insight of this work is the use of simple routines to manipulate $\ell^2$-norm sampling distributions, which play the role of quantum superpositions in the classical setting. This correspondence indicates a potentially fruitful framework for formally comparing quantum machine learning algorithms to classical machine learning algorithms.
Training Neural Networks Using Features Replay
Venue: arXiv cs.LG 2019
Year: 2019

Training a neural network using backpropagation algorithm requires passing error gradients sequentially through the network. The backward locking prevents us from updating network layers in parallel and fully leveraging the computing resources. Recently, there are several works trying to decouple and parallelize the backpropagation algorithm. However, all of them suffer from severe accuracy loss or memory explosion when the neural network is deep. To address these challenging issues, we propose a novel parallel-objective formulation for the objective function of the neural network. After that, we introduce features replay algorithm and prove that it is guaranteed to converge to critical points for the non-convex problem under certain conditions. Finally, we apply our method to training deep convolutional neural networks, and the experimental results show that the proposed method achieves {faster} convergence, {lower} memory consumption, and {better} generalization error than compared methods.
Journey Beyond Full Abstraction: Exploring Robust Property Preservation for Secure Compilation
Venue: arXiv cs.PL 2019
Year: 2019

(CROPPED TO FIT IN ARXIV'S SILLY LIMIT. SEE PDF FOR COMPLETE ABSTRACT.) We are the first to thoroughly explore a large space of formal secure compilation criteria based on robust property preservation, i.e., the preservation of properties satisfied against arbitrary adversarial contexts. We study robustly preserving various classes of trace properties such as safety, of hyperproperties such as noninterference, and of relational hyperproperties such as trace equivalence. This leads to many new secure compilation criteria, some of which are easier to practically achieve and prove than full abstraction, and some of which provide strictly stronger security guarantees. For each of the studied criteria we propose an equivalent "property-free" characterization that clarifies which proof techniques apply. For relational properties and hyperproperties, which relate the behaviors of multiple programs, our formal definitions of the property classes themselves are novel. We order our criteria by their relative strength and show several collapses and separation results. Finally, we adapt existing proof techniques to show that even the strongest of our secure compilation criteria, the robust preservation of all relational hyperproperties, is achievable for a simple translation from a statically typed to a dynamically typed language.
The latest gossip on BFT consensus
Venue: arXiv cs.DC 2019
Year: 2019

The paper presents Tendermint, a new protocol for ordering events in a distributed network under adversarial conditions. More commonly known as Byzantine Fault Tolerant (BFT) consensus or atomic broadcast, the problem has attracted significant attention in recent years due to the widespread success of blockchain-based digital currencies, such as Bitcoin and Ethereum, which successfully solved the problem in a public setting without a central authority. Tendermint modernizes classic academic work on the subject and simplifies the design of the BFT algorithm by relying on a peer-to-peer gossip protocol among nodes.
Probabilistic Relational Reasoning via Metrics
Venue: arXiv cs.PL 2019
Year: 2019

The Fuzz programming language [Reed and Pierce, 2010] uses an elegant linear type system combined with a monad-like type to express and reason about probabilistic sensitivity properties, most notably $ε$-differential privacy. We show how to extend Fuzz to capture more general relational properties of probabilistic programs, with approximate, or $(ε, δ)$-differential privacy serving as a leading example. Our technical contributions are threefold. First, we introduce the categorical notion of comonadic lifting of a monad to model composition properties of probabilistic divergences. Then, we show how to express relational properties in terms of sensitivity properties via an adjunction we call the path construction. Finally, we instantiate our semantics to model the terminating fragment of Fuzz extended with types carrying information about other divergences between distributions.
Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation
Venue: arXiv cs.DS 2019
Year: 2019

We show optimal lower bounds for spanning forest computation in two different models: * One wants a data structure for fully dynamic spanning forest in which updates can insert or delete edges amongst a base set of $n$ vertices. The sole allowed query asks for a spanning forest, which the data structure should successfully answer with some given (potentially small) constant probability $ε>0$. We prove that any such data structure must use $Ω(n\log^3 n)$ bits of memory. * There is a referee and $n$ vertices in a network sharing public randomness, and each vertex knows only its neighborhood; the referee receives no input. The vertices each send a message to the referee who then computes a spanning forest of the graph with constant probability $ε>0$. We prove the average message length must be $Ω(\log^3 n)$ bits. Both our lower bounds are optimal, with matching upper bounds provided by the AGM sketch [AGM12] (which even succeeds with probability $1 - 1/\mathrm{poly}(n)$). Furthermore, for the first setting we show optimal lower bounds even for low failure probability $δ$, as long as $δ> 2^{-n^{1-ε}}$.
Investigating Order Effects in Multidimensional Relevance Judgment using Query Logs
Venue: arXiv cs.IR 2019
Year: 2019

There is a growing body of research which has investigated relevance judgment in IR being influenced by multiple factors or dimensions. At the same time, the Order Effects in sequential decision making have been quantitatively detected and studied in Mathematical Psychology. Combining the two phenomena, there have been some user studies carried out which investigate the Order Effects and thus incompatibility in different dimensions of relevance. In this work, we propose a methodology for carrying out such an investigation in large scale and real world data using query logs of a web search engine, and device a test to detect the presence of an irrational user behavior in relevance judgment of documents. We further validate this behavior through a Quantum Cognitive explanation of the Order and Context effects.
Pseudo-linear regression identification based on generalized orthonormal transfer functions: Convergence conditions and bias distribution
Venue: arXiv cs.SY 2019
Year: 2019

In this paper we generalize three identification recursive algorithms belonging to the pseudo-linear class, by introducing a predictor established on a generalized orthonormal function basis. Contrary to the existing identification schemes that use such functions, no constraint on the model poles is imposed. Not only this predictor parameterization offers the opportunity to relax the convergence conditions of the associated recursive schemes, but it entails a modification of the bias distribution linked to the basis poles. This result is specific to pseudo-linear regression properties, and cannot be transposed to most of prediction error method algorithms. A detailed bias distribution is provided, using the concept of equivalent prediction error, which reveals strong analogies between the three proposed schemes, corresponding to ARMAX, Output Error and a generalization of ARX models. That leads to introduce an indicator of the basis poles location effect on the bias distribution in the frequency domain. As shown by the simulations, the said basis poles play the role of tuning parameters, allowing to manage the model fit in the frequency domain, and allowing efficient identification of fast sampled or stiff discrete-time systems.
Teaching machines to understand data science code by semantic enrichment of dataflow graphs
Venue: arXiv cs.AI 2019
Year: 2019

Your computer is continuously executing programs, but does it really understand them? Not in any meaningful sense. That burden falls upon human knowledge workers, who are increasingly asked to write and understand code. They deserve to have intelligent tools that reveal the connections between code and its subject matter. Towards this prospect, we develop an AI system that forms semantic representations of computer programs, using techniques from knowledge representation and program analysis. To create the representations, we introduce an algorithm for enriching dataflow graphs with semantic information. The semantic enrichment algorithm is undergirded by a new ontology language for modeling computer programs and a new ontology about data science, written in this language. Throughout the paper, we focus on code written by data scientists and we locate our work within a larger movement towards collaborative, open, and reproducible science.