OpenRaiser/Intern-Atlas huggingface dataset:
Training and Inference with Integers in Deep Neural Networks
Venue: arXiv cs.LG 2018
Year: 2018

Researches on deep neural networks with discrete parameters and their deployment in embedded systems have been active and promising topics. Although previous works have successfully reduced precision in inference, transferring both training and inference processes to low-bitwidth integers has not been demonstrated simultaneously. In this work, we develop a new method termed as "WAGE" to discretize both training and inference, where weights (W), activations (A), gradients (G) and errors (E) among layers are shifted and linearly constrained to low-bitwidth integers. To perform pure discrete dataflow for fixed-point devices, we further replace batch normalization by a constant scaling layer and simplify other components that are arduous for integer implementation. Improved accuracies can be obtained on multiple datasets, which indicates that WAGE somehow acts as a type of regularization. Empirically, we demonstrate the potential to deploy training in hardware systems such as integer-based deep learning accelerators and neuromorphic chips with comparable accuracy and higher energy efficiency, which is crucial to future AI applications in variable scenarios with transfer and continual learning demands.
Proof systems: from nestings to sequents and back
Venue: arXiv cs.LO 2018
Year: 2018

In this work, we explore proof theoretical connections between sequent, nested and labelled calculi. In particular, we show a general algorithm for transforming a class of nested systems into sequent calculus systems, passing through linear nested systems. Moreover, we show a semantical characterisation of intuitionistic, multi-modal and non-normal modal logics for all these systems, via a case-by-case translation between labelled nested to labelled sequent systems.
DataBright: Towards a Global Exchange for Decentralized Data Ownership and Trusted Computation
Venue: arXiv cs.ET 2018
Year: 2018

It is safe to assume that, for the foreseeable future, machine learning, especially deep learning will remain both data- and computation-hungry. In this paper, we ask: Can we build a global exchange where everyone can contribute computation and data to train the next generation of machine learning applications? We present an early, but running prototype of DataBright, a system that turns the creation of training examples and the sharing of computation into an investment mechanism. Unlike most crowdsourcing platforms, where the contributor gets paid when they submit their data, DataBright pays dividends whenever a contributor's data or hardware is used by someone to train a machine learning model. The contributor becomes a shareholder in the dataset they created. To enable the measurement of usage, a computation platform that contributors can trust is also necessary. DataBright thus merges both a data market and a trusted computation market. We illustrate that trusted computation can enable the creation of an AI market, where each data point has an exact value that should be paid to its creator. DataBright allows data creators to retain ownership of their contribution and attaches to it a measurable value. The value of the data is given by its utility in subsequent distributed computation done on the DataBright computation market. The computation market allocates tasks and subsequent payments to pooled hardware. This leads to the creation of a decentralized AI cloud. Our experiments show that trusted hardware such as Intel SGX can be added to the usual ML pipeline with no additional costs. We use this setting to orchestrate distributed computation that enables the creation of a computation market. DataBright is available for download at https://github.com/ds3lab/databright.
Distribution-free Junta Testing
Venue: arXiv cs.CC 2018
Year: 2018

We study the problem of testing whether an unknown $n$-variable Boolean function is a $k$-junta in the distribution-free property testing model, where the distance between functions is measured with respect to an arbitrary and unknown probability distribution over $\{0,1\}^n$. Our first main result is that distribution-free $k$-junta testing can be performed, with one-sided error, by an adaptive algorithm that uses $\tilde{O}(k^2)/ε$ queries (independent of $n$). Complementing this, our second main result is a lower bound showing that any non-adaptive distribution-free $k$-junta testing algorithm must make $Ω(2^{k/3})$ queries even to test to accuracy $ε=1/3$. These bounds establish that while the optimal query complexity of non-adaptive $k$-junta testing is $2^{Θ(k)}$, for adaptive testing it is $\text{poly}(k)$, and thus show that adaptivity provides an exponential improvement in the distribution-free query complexity of testing juntas.
Efficient Discovery of Variable-length Time Series Motifs with Large Length Range in Million Scale Time Series
Venue: arXiv cs.DS 2018
Year: 2018

Detecting repeated variable-length patterns, also called variable-length motifs, has received a great amount of attention in recent years. Current state-of-the-art algorithm utilizes fixed-length motif discovery algorithm as a subroutine to enumerate variable-length motifs. As a result, it may take hours or days to execute when enumeration range is large. In this work, we introduce an approximate algorithm called HierarchIcal based Motif Enumeration (HIME) to detect variable-length motifs with a large enumeration range in million-scale time series. We show in the experiments that the scalability of the proposed algorithm is significantly better than that of the state-of-the-art algorithm. Moreover, the motif length range detected by HIME is considerably larger than previous sequence-matching based approximate variable-length motif discovery approach. We demonstrate that HIME can efficiently detect meaningful variable-length motifs in long, real world time series.
Context-Specific Validation of Data-Driven Models
Venue: arXiv cs.SY 2018
Year: 2018

With an increasing use of data-driven models to control robotic systems, it has become important to develop a methodology for validating such models before they can be deployed to design a controller for the actual system. Specifically, it must be ensured that the controller designed for a learned model would perform as expected on the actual physical system. We propose a context-specific validation framework to quantify the quality of a learned model based on a distance measure between the closed-loop actual system and the learned model. We then propose an active sampling scheme to compute a probabilistic upper bound on this distance in a sample-efficient manner. The proposed framework validates the learned model against only those behaviors of the system that are relevant for the purpose for which we intend to use this model, and does not require any a priori knowledge of the system dynamics. Several simulations illustrate the practicality of the proposed framework for validating the models of real-world systems, and consequently, for controller synthesis.
Energy Spatio-Temporal Pattern Prediction for Electric Vehicle Networks
Venue: arXiv cs.LG 2018
Year: 2018

Information about the spatio-temporal pattern of electricity energy carried by EVs, instead of EVs themselves, is crucial for EVs to establish more effective and intelligent interactions with the smart grid. In this paper, we propose a framework for predicting the amount of the electricity energy stored by a large number of EVs aggregated within different city-scale regions, based on spatio-temporal pattern of the electricity energy. The spatial pattern is modeled via using a neural network based spatial predictor, while the temporal pattern is captured via using a linear-chain conditional random field (CRF) based temporal predictor. Two predictors are fed with spatial and temporal features respectively, which are extracted based on real trajectories data recorded in Beijing. Furthermore, we combine both predictors to build the spatio-temporal predictor, by using an optimal combination coefficient which minimizes the normalized mean square error (NMSE) of the predictions. The prediction performance is evaluated based on extensive experiments covering both spatial and temporal predictions, and the improvement achieved by the combined spatio-temporal predictor. The experiment results show that the NMSE of the spatio-temporal predictor is maintained below 0.1 for all investigate regions of Beijing. We further visualize the prediction and discuss the potential benefits can be brought to smart grid scheduling and EV charging by utilizing the proposed framework.
Graph2Seq: Scalable Learning Dynamics for Graphs
Venue: arXiv cs.LG 2018
Year: 2018

Neural networks have been shown to be an effective tool for learning algorithms over graph-structured data. However, graph representation techniques---that convert graphs to real-valued vectors for use with neural networks---are still in their infancy. Recent works have proposed several approaches (e.g., graph convolutional networks), but these methods have difficulty scaling and generalizing to graphs with different sizes and shapes. We present Graph2Seq, a new technique that represents vertices of graphs as infinite time-series. By not limiting the representation to a fixed dimension, Graph2Seq scales naturally to graphs of arbitrary sizes and shapes. Graph2Seq is also reversible, allowing full recovery of the graph structure from the sequences. By analyzing a formal computational model for graph representation, we show that an unbounded sequence is necessary for scalability. Our experimental results with Graph2Seq show strong generalization and new state-of-the-art performance on a variety of graph combinatorial optimization problems.
Multiterminal Secret Key Agreement at Asymptotically Zero Discussion Rate
Venue: arXiv cs.IT 2018
Year: 2018

In the multiterminal secret key agreement problem, a set of users want to discuss with each other until they share a common secret key independent of their discussion. We want to characterize the maximum secret key rate, called the secrecy capacity, asymptotically when the total discussion rate goes to zero. In the case of only two users, the capacity is equal to the Gács-Körner common information. However, when there are more than two users, the capacity is unknown. It is plausible that a multivariate extension of the Gács-Körner common information is the capacity, however, proving the converse is challenging. We resolved this for the hypergraphical sources and finite linear sources, and provide efficiently computable characterizations. We also give some ideas of extending the techniques to more general source models.
Craig Interpolation and Access Interpolation with Clausal First-Order Tableaux
Venue: arXiv cs.LO 2018
Year: 2018

We develop foundations for computing Craig interpolants and similar intermediates of two given formulas with first-order theorem provers that construct clausal tableaux. Provers that can be understood in this way include efficient machine-oriented systems based on calculi of two families: goal-oriented like model elimination and the connection method, and bottom-up like the hyper tableau calculus. The presented method for Craig-Lyndon interpolation involves a lifting step where terms are replaced by quantified variables, similar as known for resolution-based interpolation, but applied to a differently characterized ground formula and proven correct more abstractly on the basis of Herbrand's theorem, independently of a particular calculus. Access interpolation is a recent form of interpolation for database query reformulation that applies to first-order formulas with relativized quantifiers and constrains the quantification patterns of predicate occurrences. It has been previously investigated in the framework of Smullyan's non-clausal tableaux. Here, in essence, we simulate these with the more machine-oriented clausal tableaux through structural constraints that can be ensured either directly by bottom-up tableau construction methods or, for closed clausal tableaux constructed with arbitrary calculi, by postprocessing with restructuring transformations.
Recursive Chaining of Reversible Image-to-image Translators For Face Aging
Venue: arXiv cs.CV 2018
Year: 2018

This paper addresses the modeling and simulation of progressive changes over time, such as human face aging. By treating the age phases as a sequence of image domains, we construct a chain of transformers that map images from one age domain to the next. Leveraging recent adversarial image translation methods, our approach requires no training samples of the same individual at different ages. Here, the model must be flexible enough to translate a child face to a young adult, and all the way through the adulthood to old age. We find that some transformers in the chain can be recursively applied on their own output to cover multiple phases, compressing the chain. The structure of the chain also unearths information about the underlying physical process. We demonstrate the performance of our method with precise and intuitive metrics, and visually match with the face aging state-of-the-art.
Dealing with Difficult Minority Labels in Imbalanced Mutilabel Data Sets
Venue: arXiv cs.LG 2018
Year: 2018

Multilabel classification is an emergent data mining task with a broad range of real world applications. Learning from imbalanced multilabel data is being deeply studied latterly, and several resampling methods have been proposed in the literature. The unequal label distribution in most multilabel datasets, with disparate imbalance levels, could be a handicap while learning new classifiers. In addition, this characteristic challenges many of the existent preprocessing algorithms. Furthermore, the concurrence between imbalanced labels can make harder the learning from certain labels. These are what we call \textit{difficult} labels. In this work, the problem of difficult labels is deeply analyzed, its influence in multilabel classifiers is studied, and a novel way to solve this problem is proposed. Specific metrics to assess this trait in multilabel datasets, called \textit{SCUMBLE} (\textit{Score of ConcUrrence among iMBalanced LabEls}) and \textit{SCUMBLELbl}, are presented along with REMEDIAL (\textit{REsampling MultilabEl datasets by Decoupling highly ImbAlanced Labels}), a new algorithm aimed to relax label concurrence. How to deal with this problem using the R mldr package is also outlined.
A Blockchain Based Liability Attribution Framework for Autonomous Vehicles
Venue: arXiv cs.CR 2018
Year: 2018

The advent of autonomous vehicles is envisaged to disrupt the auto insurance liability model.Compared to the the current model where liability is largely attributed to the driver,autonomous vehicles necessitate the consideration of other entities in the automotive ecosystem including the auto manufacturer,software provider,service technician and the vehicle owner.The proliferation of sensors and connecting technologies in autonomous vehicles enables an autonomous vehicle to gather sufficient data for liability attribution,yet increased connectivity exposes the vehicle to attacks from interacting entities.These possibilities motivate potential liable entities to repudiate their involvement in a collision event to evade liability. While the data collected from vehicular sensors and vehicular communications is an integral part of the evidence for arbitrating liability in the event of an accident,there is also a need to record all interactions between the aforementioned entities to identify potential instances of negligence that may have played a role in the accident.In this paper,we propose a BlockChain(BC) based framework that integrates the concerned entities in the liability model and provides untampered evidence for liability attribution and adjudication.We first describe the liability attribution model, identify key requirements and describe the adversarial capabilities of entities. Also,we present a detailed description of data contributing to evidence.Our framework uses permissioned BC and partitions the BC to tailor data access to relevant BC participants.Finally,we conduct a security analysis to verify that the identified requirements are met and resilience of our proposed framework to identified attacks.
Understanding Book Popularity on Goodreads
Venue: arXiv cs.SI 2018
Year: 2018

Goodreads has launched the Readers Choice Awards since 2009 where users are able to nominate/vote books of their choice, released in the given year. In this work, we question if the number of votes that a book would receive (aka the popularity of the book) can be predicted based on the characteristics of various entities on Goodreads. We are successful in predicting the popularity of the books with high prediction accuracy (correlation coefficient ~0.61) and low RMSE (~1.25). User engagement and author's prestige are found to be crucial factors for book popularity.
Sub-logarithmic Distributed Oblivious RAM with Small Block Size
Venue: arXiv cs.CR 2018
Year: 2018

Oblivious RAM (ORAM) is a cryptographic primitive that allows a client to securely execute RAM programs over data that is stored in an untrusted server. Distributed Oblivious RAM is a variant of ORAM, where the data is stored in $m>1$ servers. Extensive research over the last few decades have succeeded to reduce the bandwidth overhead of ORAM schemes, both in the single-server and the multi-server setting, from $O(\sqrt{N})$ to $O(1)$. However, all known protocols that achieve a sub-logarithmic overhead either require heavy server-side computation (e.g. homomorphic encryption), or a large block size of at least $Ω(\log^3 N)$. In this paper, we present a family of distributed ORAM constructions that follow the hierarchical approach of Goldreich and Ostrovsky [GO96]. We enhance known techniques, and develop new ones, to take better advantage of the existence of multiple servers. By plugging efficient known hashing schemes in our constructions, we get the following results: 1. For any $m\geq 2$, we show an $m$-server ORAM scheme with $O(\log N/\log\log N)$ overhead, and block size $Ω(\log^2 N)$. This scheme is private even against an $(m-1)$-server collusion. 2. A 3-server ORAM construction with $O(ω(1)\log N/\log\log N)$ overhead and a block size almost logarithmic, i.e. $Ω(\log^{1+ε}N)$. We also investigate a model where the servers are allowed to perform a linear amount of light local computations, and show that constant overhead is achievable in this model, through a simple four-server ORAM protocol.
Channel Reconstruction-Based Hybrid Precoding for Millimeter Wave Multi-User MIMO Systems
Venue: arXiv cs.IT 2018
Year: 2018

The focus of this paper is on multi-user MIMO transmissions for millimeter wave systems with a hybrid precoding architecture at the base-station. To enable multi-user transmissions, the base-station uses a cell-specific codebook of beamforming vectors over an initial beam alignment phase. Each user uses a user-specific codebook of beamforming vectors to learn the top-P (where P >= 1) beam pairs in terms of the observed SNR in a single-user setting. The top-P beam indices along with their SNRs are fed back from each user and the base-station leverages this information to generate beam weights for simultaneous transmissions. A typical method to generate the beam weights is to use only the best beam for each user and either steer energy along this beam, or to utilize this information to reduce multi-user interference. The other beams are used as fall back options to address blockage or mobility. Such an approach completely discards information learned about the channel condition(s) even though each user feeds back this information. With this background, this work develops an advanced directional precoding structure for simultaneous transmissions at the cost of an additional marginal feedback overhead. This construction relies on three main innovations: 1) Additional feedback to allow the base-station to reconstruct a rank-P approximation of the channel matrix between it and each user, 2) A zeroforcing structure that leverages this information to combat multi-user interference by remaining agnostic of the receiver beam knowledge in the precoder design, and 3) A hybrid precoding architecture that allows both amplitude and phase control at low-complexity and cost to allow the implementation of the zeroforcing structure. Numerical studies show that the proposed scheme results in a significant sum rate performance improvement over naive schemes even with a coarse initial beam alignment codebook.
Internet Location Verification: Challenges and Solutions
Venue: arXiv cs.CR 2018
Year: 2018

This thesis addresses the problem of verifying the geographic locations of Internet clients. First, we demonstrate how current state-of-the-art delay-based geolocation techniques are susceptible to evasion through delay manipulations, which involve both increasing and decreasing the Internet delays that are observed between a client and a remote measuring party. We then propose Client Presence Verification (CPV) as a delay-based technique to verify an assertion about a client's physical presence in a prescribed geographic region. Three verifiers geographically encapsulating a client's asserted location are used to corroborate that assertion by measuring the delays between themselves and the client. CPV infers geographic distances from these delays and thus, using the smaller of the forward and reverse one-way delay between each verifier and the client is expected to result in a more accurate distance inference than using the conventional round-trip times. Accordingly, we devise a novel protocol for accurate one-way delay measurements between the client and the three verifiers to be used by CPV, taking into account that the client could manipulate the measurements to defeat the verification process. We evaluate CPV through extensive real-world experiments with legitimate clients (those truly present at where they asserted to be) modeled to use both wired and wireless access networks. Wired evaluation is done using the PlanetLab testbed, during which we examine various factors affecting CPV's efficacy, such as the client's geographical nearness to the verifiers. For wireless evaluation, we leverage the Internet delay information collected for wired clients from PlanetLab, and model additional delays representing the last-mile wireless link. Finally, we reinforce CPV against a (hypothetical) middlebox that an adversary specifically customizes to defeat CPV.