OpenRaiser/Intern-Atlas huggingface dataset:
Limits on the Universal Method for Matrix Multiplication
Venue: arXiv cs.CC 2019
Year: 2019

In this work, we prove limitations on the known methods for designing matrix multiplication algorithms. Alman and Vassilevska Williams recently defined the Universal Method, which substantially generalizes all the known approaches including Strassen's Laser Method and Cohn and Umans' Group Theoretic Method. We prove concrete lower bounds on the algorithms one can design by applying the Universal Method to many different tensors. Our proofs use new tools for upper bounding the asymptotic slice rank of a wide range of tensors. Our main result is that the Universal method applied to any Coppersmith-Winograd tensor $CW_q$ cannot yield a bound on $ω$, the exponent of matrix multiplication, better than $2.16805$. By comparison, it was previously only known that the weaker `Galactic Method' applied to $CW_q$ could not achieve an exponent of $2$. We also study the Laser Method (which is, in principle, a highly special case of the Universal Method) and prove that it is "complete" for matrix multiplication algorithms: when it applies to a tensor $T$, it achieves $ω= 2$ if and only if it is possible for the Universal method applied to $T$ to achieve $ω= 2$. Hence, the Laser Method, which was originally used as an algorithmic tool, can also be seen as a lower bounding tool. For example, in their landmark paper, Coppersmith and Winograd achieved a bound of $ω\leq 2.376$, by applying the Laser Method to $CW_q$. By our result, the fact that they did not achieve $ω=2$ implies a lower bound on the Universal Method applied to $CW_q$. Indeed, if it were possible for the Universal Method applied to $CW_q$ to achieve $ω=2$, then Coppersmith and Winograd's application of the Laser Method would have achieved $ω=2$.
On the Activity Privacy of Blockchain for IoT
Venue: arXiv cs.CR 2019
Year: 2019

Security is one of the fundamental challenges in the Internet of Things (IoT) due to the heterogeneity and resource constraints of the IoT devices. Device classification methods are employed to enhance the security of IoT by detecting unregistered devices or traffic patterns. In recent years, blockchain has received tremendous attention as a distributed trustless platform to enhance the security of IoT. Conventional device identification methods are not directly applicable in blockchain-based IoT as network layer packets are not stored in the blockchain. Moreover, the transactions are broadcast and thus have no destination IP address and contain a public key as the user identity, and are stored permanently in blockchain which can be read by any entity in the network. We show that device identification in blockchain introduces privacy risks as the malicious nodes can identify users' activity pattern by analyzing the temporal pattern of their transactions in the blockchain. We study the likelihood of classifying IoT devices by analyzing their information stored in the blockchain, which to the best of our knowledge, is the first work of its kind. We use a smart home as a representative IoT scenario. First, a blockchain is populated according to a real-world smart home traffic dataset. We then apply machine learning algorithms on the data stored in the blockchain to analyze the success rate of device classification, modeling both an informed and a blind attacker. Our results demonstrate success rates over 90\% in classifying devices. We propose three timestamp obfuscation methods, namely combining multiple packets into a single transaction, merging ledgers of multiple devices, and randomly delaying transactions, to reduce the success rate in classifying devices. The proposed timestamp obfuscation methods can reduce the classification success rates to as low as 20%.
A new approach to learning in Dynamic Bayesian Networks (DBNs)
Venue: arXiv cs.LG 2019
Year: 2019

In this paper, we revisit the parameter learning problem, namely the estimation of model parameters for Dynamic Bayesian Networks (DBNs). DBNs are directed graphical models of stochastic processes that encompasses and generalize Hidden Markov models (HMMs) and Linear Dynamical Systems (LDSs). Whenever we apply these models to economics and finance, we are forced to make some modeling assumptions about the state dynamics and the graph topology (the DBN structure). These assumptions may be incorrectly specified and contain some additional noise compared to reality. Trying to use a best fit approach through maximum likelihood estimation may miss this point and try to fit at any price these models on data. We present here a new methodology that takes a radical point of view and instead focus on the final efficiency of our model. Parameters are hence estimated in terms of their efficiency rather than their distributional fit to the data. The resulting optimization problem that consists in finding the optimal parameters is a hard problem. We rely on Covariance Matrix Adaptation Evolution Strategy (CMA-ES) method to tackle this issue. We apply this method to the seminal problem of trend detection in financial markets. We see on numerical results that the resulting parameters seem less error prone to over fitting than traditional moving average cross over trend detection and perform better. The method developed here for algorithmic trading is general. It can be applied to other real case applications whenever there is no physical law underlying our DBNs.
A Simple Algorithm for Computing the Document Array
Venue: arXiv cs.DS 2019
Year: 2019

We present a simple algorithm for computing the document array given a string collection and its suffix array as input. Our algorithm runs in linear time using constant additional space for strings from constant alphabets.
Quicker ADC : Unlocking the hidden potential of Product Quantization with SIMD
Venue: arXiv cs.CV 2019
Year: 2019

Efficient Nearest Neighbor (NN) search in high-dimensional spaces is a foundation of many multimedia retrieval systems. A common approach is to rely on Product Quantization, which allows the storage of large vector databases in memory and efficient distance computations. Yet, implementations of nearest neighbor search with Product Quantization have their performance limited by the many memory accesses they perform. Following this observation, André et al. proposed Quick ADC with up to $6\times$ faster implementations of $m\times{}4$ product quantizers (PQ) leveraging specific SIMD instructions. Quicker ADC is a generalization of Quick ADC not limited to $m\times{}4$ codes and supporting AVX-512, the latest revision of SIMD instruction set. In doing so, Quicker ADC faces the challenge of using efficiently 5,6 and 7-bit shuffles that do not align to computer bytes or words. To this end, we introduce (i) irregular product quantizers combining sub-quantizers of different granularity and (ii) split tables allowing lookup tables larger than registers. We evaluate Quicker ADC with multiple indexes including Inverted Multi-Indexes and IVF HNSW and show that it outperforms the reference optimized implementations (i.e., FAISS and polysemous codes) for numerous configurations. Finally, we release an open-source fork of FAISS enhanced with Quicker ADC at http://github.com/nlescoua/faiss-quickeradc.
MI6: Secure Enclaves in a Speculative Out-of-Order Processor
Venue: arXiv cs.CR 2019
Year: 2019

Recent attacks have broken process isolation by exploiting microarchitectural side channels that allow indirect access to shared microarchitectural state. Enclaves strengthen the process abstraction to restore isolation guarantees. We propose MI6, an aggressive, speculative out-of-order processor capable of providing secure enclaves under a threat model that includes an untrusted OS and an attacker capable of mounting any software attack currently considered practical, including control flow speculation attacks. MI6 is inspired by Sanctum [16] and extends its isolation guarantee to more realistic memory hierarchies. It also introduces a purge instruction, which is used only when a secure process is scheduled, and implements it for a complex processor microarchitecture. We model the performance impact of enclaves in MI6 through FPGA emulation on AWS F1 FPGAs by running SPEC CINT2006 benchmarks on top of an untrusted Linux OS. Security comes at the cost of approximately 16.4% average slowdown for protected programs.
Dynamic Online Gradient Descent with Improved Query Complexity: A Theoretical Revisit
Venue: arXiv cs.LG 2019
Year: 2019

We provide a new theoretical analysis framework to investigate online gradient descent in the dynamic environment. Comparing with the previous work, the new framework recovers the state-of-the-art dynamic regret, but does not require extra gradient queries for every iteration. Specifically, when functions are $α$ strongly convex and $β$ smooth, to achieve the state-of-the-art dynamic regret, the previous work requires $O(κ)$ with $κ= \fracβα$ queries of gradients at every iteration. But, our framework shows that the query complexity can be improved to be $O(1)$, which does not depend on $κ$. The improvement is significant for ill-conditioned problems because that their objective function usually has a large $κ$.
Open Power System Data - Frictionless data for electricity system modelling
Venue: arXiv cs.CY 2019
Year: 2019

The quality of electricity system modelling heavily depends on the input data used. Although a lot of data is publicly available, it is often dispersed, tedious to process and partly contains errors. We argue that a central provision of input data for modelling has the character of a public good: it reduces overall societal costs for quantitative energy research as redundant work is avoided, and it improves transparency and reproducibility in electricity system modelling. This paper describes the Open Power System Data platform that aims at realising the efficiency and quality gains of centralised data provision by collecting, checking, processing, aggregating, documenting and publishing data required by most modellers. We conclude that the platform can provide substantial benefits to energy system analysis by raising efficiency of data pre-processing, providing a method for making data pre-processing for energy system modelling traceable, flexible and reproducible and improving the quality of original data published by data providers.
Optimal Secure GDoF of Symmetric Gaussian Wiretap Channel with a Helper
Venue: arXiv cs.IT 2019
Year: 2019

We study a symmetric Gaussian wiretap channel with a helper, where a confidential message is sent from a transmitter to a legitimate receiver, in the presence of a helper and an eavesdropper, under a weak notion of secrecy constraint. For this setting, we characterize the optimal secure generalized degrees-of-freedom (GDoF). The result reveals that, adding a helper can significantly increase the secure GDoF of the wiretap channel. The result is supported by a new converse and a new scheme. In the proposed scheme, the helper sends a cooperative jamming signal at a specific power level and direction. In this way, it minimizes the penalty in GDoF incurred by the secrecy constraint. In the secure rate analysis, the techniques of noise removal and signal separation are used.
A Unified Learning Based Framework for Light Field Reconstruction from Coded Projections
Venue: arXiv cs.CV 2019
Year: 2019

Light field presents a rich way to represent the 3D world by capturing the spatio-angular dimensions of the visual signal. However, the popular way of capturing light field (LF) via a plenoptic camera presents spatio-angular resolution trade-off. Computational imaging techniques such as compressive light field and programmable coded aperture reconstruct full sensor resolution LF from coded projections obtained by multiplexing the incoming spatio-angular light field. Here, we present a unified learning framework that can reconstruct LF from a variety of multiplexing schemes with minimal number of coded images as input. We consider three light field capture schemes: heterodyne capture scheme with code placed near the sensor, coded aperture scheme with code at the camera aperture and finally the dual exposure scheme of capturing a focus-defocus pair where there is no explicit coding. Our algorithm consists of three stages 1) we recover the all-in-focus image from the coded image 2) we estimate the disparity maps for all the LF views from the coded image and the all-in-focus image, 3) we then render the LF by warping the all-in-focus image using disparity maps and refine it. For these three stages we propose three deep neural networks - ViewNet, DispairtyNet and RefineNet. Our reconstructions show that our learning algorithm achieves state-of-the-art results for all the three multiplexing schemes. Especially, our LF reconstructions from focus-defocus pair is comparable to other learning-based view synthesis approaches from multiple images. Thus, our work paves the way for capturing high-resolution LF (~ a megapixel) using conventional cameras such as DSLRs. Please check our supplementary materials $\href{https://docs.google.com/presentation/d/1Vr-F8ZskrSd63tvnLfJ2xmEXY6OBc1Rll3XeOAtc11I/}{online}$ to better appreciate the reconstructed light fields.
Extending TCP for Accelerating Replication on Cluster File Systems over SDNs
Venue: arXiv cs.NI 2019
Year: 2019

This paper explores the changes required of TCP to efficiently support cluster file systems such as Hadoop Distributed File System (HDFS) where the storage nodes are connected through a software defined networking (SDN). Traditional chain replications in these file systems incur large delay and cause inefficient network use. But SDN can cooperate with the cluster file systems to address the problems by pre-arranging a distribution tree, which opens the possibility of parallel replication. Unfortunately, it cannot be realized without extending TCP, to accommodate the parallel transfer on the transport layer. This paper discusses how to extend TCP to make it possible, and demonstrates the feasibility by implementing a prototype in the Linux kernel. The prototype saves the data replication time by 25% while substantially reducing network use.
Neural Architecture Search Over a Graph Search Space
Venue: arXiv cs.LG 2019
Year: 2019

Neural Architecture Search (NAS) enabled the discovery of state-of-the-art architectures in many domains. However, the success of NAS depends on the definition of the search space. Current search spaces are defined as a static sequence of decisions and a set of available actions for each decision. Each possible sequence of actions defines an architecture. We propose a more expressive class of search space: directed graphs. In our formalism, each decision is a vertex and each action is an edge. This allows us to model iterative and branching architecture design decisions. We demonstrate in simulation, and on image classification experiments, basic iterative and branching search structures, and show that the graph representation improves sample efficiency.
Attribute Evaluation on Attack Trees with Incomplete Information
Venue: arXiv cs.CR 2019
Year: 2019

Attack trees are considered a useful tool for security modelling because they support qualitative as well as quantitative analysis. The quantitative approach is based on values associated to each node in the tree, expressing, for instance, the minimal cost or probability of an attack. Current quantitative methods for attack trees allow the analyst to, based on an initial assignment of values to the leaf nodes, derive the values of the higher nodes in the tree. In practice, however, it shows to be very difficult to obtain reliable values for all leaf nodes. The main reasons are that data is only available for some of the nodes, that data is available for intermediate nodes rather than for the leaf nodes, or even that the available data is inconsistent. We address these problems by developing a generalisation of the standard bottom-up calculation method in three ways. First, we allow initial attributions of non-leaf nodes. Second, we admit additional relations between attack steps beyond those provided by the underlying attack tree semantics. Third, we support the calculation of an approximative solution in case of inconsistencies. We illustrate our method, which is based on constraint programming, by a comprehensive case study.
SMPLR: Deep SMPL reverse for 3D human pose and shape recovery
Venue: arXiv cs.CV 2019
Year: 2019

Current state-of-the-art in 3D human pose and shape recovery relies on deep neural networks and statistical morphable body models, such as the Skinned Multi-Person Linear model (SMPL). However, regardless of the advantages of having both body pose and shape, SMPL-based solutions have shown difficulties to predict 3D bodies accurately. This is mainly due to the unconstrained nature of SMPL, which may generate unrealistic body meshes. Because of this, regression of SMPL parameters is a difficult task, often addressed with complex regularization terms. In this paper we propose to embed SMPL within a deep model to accurately estimate 3D pose and shape from a still RGB image. We use CNN-based 3D joint predictions as an intermediate representation to regress SMPL pose and shape parameters. Later, 3D joints are reconstructed again in the SMPL output. This module can be seen as an autoencoder where the encoder is a deep neural network and the decoder is SMPL model. We refer to this as SMPL reverse (SMPLR). By implementing SMPLR as an encoder-decoder we avoid the need of complex constraints on pose and shape. Furthermore, given that in-the-wild datasets usually lack accurate 3D annotations, it is desirable to lift 2D joints to 3D without pairing 3D annotations with RGB images. Therefore, we also propose a denoising autoencoder (DAE) module between CNN and SMPLR, able to lift 2D joints to 3D and partially recover from structured error. We evaluate our method on SURREAL and Human3.6M datasets, showing improvement over SMPL-based state-of-the-art alternatives by about 4 and 25 millimeters, respectively.
ORIGAMI: A Heterogeneous Split Architecture for In-Memory Acceleration of Learning
Venue: arXiv cs.LG 2019
Year: 2019

Memory bandwidth bottleneck is a major challenges in processing machine learning (ML) algorithms. In-memory acceleration has potential to address this problem; however, it needs to address two challenges. First, in-memory accelerator should be general enough to support a large set of different ML algorithms. Second, it should be efficient enough to utilize bandwidth while meeting limited power and area budgets of logic layer of a 3D-stacked memory. We observe that previous work fails to simultaneously address both challenges. We propose ORIGAMI, a heterogeneous set of in-memory accelerators, to support compute demands of different ML algorithms, and also uses an off-the-shelf compute platform (e.g.,FPGA,GPU,TPU,etc.) to utilize bandwidth without violating strict area and power budgets. ORIGAMI offers a pattern-matching technique to identify similar computation patterns of ML algorithms and extracts a compute engine for each pattern. These compute engines constitute heterogeneous accelerators integrated on logic layer of a 3D-stacked memory. Combination of these compute engines can execute any type of ML algorithms. To utilize available bandwidth without violating area and power budgets of logic layer, ORIGAMI comes with a computation-splitting compiler that divides an ML algorithm between in-memory accelerators and an out-of-the-memory platform in a balanced way and with minimum inter-communications. Combination of pattern matching and split execution offers a new design point for acceleration of ML algorithms. Evaluation results across 12 popular ML algorithms show that ORIGAMI outperforms state-of-the-art accelerator with 3D-stacked memory in terms of performance and energy-delay product (EDP) by 1.5x and 29x (up to 1.6x and 31x), respectively. Furthermore, results are within a 1% margin of an ideal system that has unlimited compute resources on logic layer of a 3D-stacked memory.
A High-Performance CNN Method for Offline Handwritten Chinese Character Recognition and Visualization
Venue: arXiv cs.CV 2019
Year: 2019

Recent researches introduced fast, compact and efficient convolutional neural networks (CNNs) for offline handwritten Chinese character recognition (HCCR). However, many of them did not address the problem of network interpretability. We propose a new architecture of a deep CNN with high recognition performance which is capable of learning deep features for visualization. A special characteristic of our model is the bottleneck layers which enable us to retain its expressiveness while reducing the number of multiply-accumulate operations and the required storage. We introduce a modification of global weighted average pooling (GWAP) - global weighted output average pooling (GWOAP). This paper demonstrates how they allow us to calculate class activation maps (CAMs) in order to indicate the most relevant input character image regions used by our CNN to identify a certain class. Evaluating on the ICDAR-2013 offline HCCR competition dataset, we show that our model enables a relative 0.83% error reduction while having 49% fewer parameters and the same computational cost compared to the current state-of-the-art single-network method trained only on handwritten data. Our solution outperforms even recent residual learning approaches.
Comparison between DeepESNs and gated RNNs on multivariate time-series prediction
Venue: arXiv cs.LG 2019
Year: 2019

We propose an experimental comparison between Deep Echo State Networks (DeepESNs) and gated Recurrent Neural Networks (RNNs) on multivariate time-series prediction tasks. In particular, we compare reservoir and fully-trained RNNs able to represent signals featured by multiple time-scales dynamics. The analysis is performed in terms of efficiency and prediction accuracy on 4 polyphonic music tasks. Our results show that DeepESN is able to outperform ESN in terms of prediction accuracy and efficiency. Whereas, between fully-trained approaches, Gated Recurrent Units (GRU) outperforms Long Short-Term Memory (LSTM) and simple RNN models in most cases. Overall, DeepESN turned out to be extremely more efficient than others RNN approaches and the best solution in terms of prediction accuracy on 3 out of 4 tasks.
A Probabilistic and Non-Deterministic Call-by-Push-Value Language
Venue: arXiv cs.LO 2019
Year: 2019

There is no known way of giving a domain-theoretic semantics to higher-order probabilistic languages, in such a way that the involved domains are continuous or quasi-continuous - the latter is required to do any serious mathematics. We argue that the problem naturally disappears for languages with two kinds of types, where one kind is interpreted in a Cartesian-closed category of continuous dcpos, and the other is interpreted in a category that is closed under the probabilistic powerdomain functor. Such a setting is provided by Paul B. Levy's call-by-push-value paradigm. Following this insight, we define a call-by-push-value language, with probabilistic choice sitting inside the value types, and where conversion from a value type to a computation type involves demonic non-determinism. We give both a domain-theoretic semantics and an operational semantics for the resulting language, and we show that they are sound and adequate. With the addition of statistical termination testers and parallel if, we show that the language is even fully abstract - and those two primitives are required for that.