OpenRaiser/Intern-Atlas huggingface dataset:
Deep Static Modeling of invokedynamic
Venue: arXiv cs.PL 2020
Year: 2020

Java 7 introduced programmable dynamic linking in the form of the invokedynamic framework. Static analysis of code containing programmable dynamic linking has often been cited as a significant source of unsoundness in the analysis of Java programs. For example, Java lambdas, introduced in Java 8, are a very popular feature, which is, however, resistant to static analysis, since it mixes invokedynamic with dynamic code generation. These techniques invalidate static analysis assumptions: programmable linking breaks reasoning about method resolution while dynamically generated code is, by definition, not available statically. In this paper, we show that a static analysis can predictively model uses of invokedynamic while also cooperating with extra rules to handle the runtime code generation of lambdas. Our approach plugs into an existing static analysis and helps eliminate all unsoundness in the handling of lambdas (including associated features such as method references) and generic invokedynamic uses. We evaluate our technique on a benchmark suite of our own and on third-party benchmarks, uncovering all code previously unreachable due to unsoundness, highly efficiently.
Do As I Do: Transferring Human Motion and Appearance between Monocular Videos with Spatial and Temporal Constraints
Venue: arXiv cs.CV 2020
Year: 2020

Creating plausible virtual actors from images of real actors remains one of the key challenges in computer vision and computer graphics. Marker-less human motion estimation and shape modeling from images in the wild bring this challenge to the fore. Although the recent advances on view synthesis and image-to-image translation, currently available formulations are limited to transfer solely style and do not take into account the character's motion and shape, which are by nature intermingled to produce plausible human forms. In this paper, we propose a unifying formulation for transferring appearance and retargeting human motion from monocular videos that regards all these aspects. Our method synthesizes new videos of people in a different context where they were initially recorded. Differently from recent appearance transferring methods, our approach takes into account body shape, appearance, and motion constraints. The evaluation is performed with several experiments using publicly available real videos containing hard conditions. Our method is able to transfer both human motion and appearance outperforming state-of-the-art methods, while preserving specific features of the motion that must be maintained (e.g., feet touching the floor, hands touching a particular object) and holding the best visual quality and appearance metrics such as Structural Similarity (SSIM) and Learned Perceptual Image Patch Similarity (LPIPS).
Automatic Generation of Efficient Sparse Tensor Format Conversion Routines
Venue: arXiv cs.MS 2020
Year: 2020

This paper shows how to generate code that efficiently converts sparse tensors between disparate storage formats (data layouts) such as CSR, DIA, ELL, and many others. We decompose sparse tensor conversion into three logical phases: coordinate remapping, analysis, and assembly. We then develop a language that precisely describes how different formats group together and order a tensor's nonzeros in memory. This lets a compiler emit code that performs complex remappings of nonzeros when converting between formats. We also develop a query language that can extract statistics about sparse tensors, and we show how to emit efficient analysis code that computes such queries. Finally, we define an abstract interface that captures how data structures for storing a tensor can be efficiently assembled given specific statistics about the tensor. Disparate formats can implement this common interface, thus letting a compiler emit optimized sparse tensor conversion code for arbitrary combinations of many formats without hard-coding for any specific combination. Our evaluation shows that the technique generates sparse tensor conversion routines with performance between 1.00 and 2.01$\times$ that of hand-optimized versions in SPARSKIT and Intel MKL, two popular sparse linear algebra libraries. And by emitting code that avoids materializing temporaries, which both libraries need for many combinations of source and target formats, our technique outperforms those libraries by 1.78 to 4.01$\times$ for CSC/COO to DIA/ELL conversion.
Peer-to-Peer based Social Networks: A Comprehensive Survey
Venue: arXiv cs.SI 2020
Year: 2020

Online social networks, such as Facebook and twitter, are a growing phenomenon in today's world, with various platforms providing capabilities for individuals to collaborate through messaging and chatting as well as sharing of content such as videos and photos. Most, if not all, of these platforms are based on centralized computing systems, meaning that the control and management of the systems lies in the hand of one provider, which must be trusted to treat the data and communication traces securely. While users aim for privacy and data sovereignty, often the providers aim to monetize the data they store. Even, federated privately run social networks require a few enthusiasts that serve the community and have, through that, access to the data they manage. As a zero-trust alternative, peer-to-peer (P2P) technologies promise networks that are self organizing and secure-by-design, in which the final data sovereignty lies at the corresponding user. Such networks support end-to-end communication, uncompromising access control, anonymity and resilience against censorship and massive data leaks through misused trust. The goals of this survey are three-fold. Firstly, the survey elaborates the properties of P2P-based online social networks and defines the requirements for such (zero-trust) platforms. Secondly, it elaborates on the building blocks for P2P frameworks that allow the creation of such sophisticated and demanding applications, such as user/identity management, reliable data storage, secure communication, access control and general-purpose extensibility, features that are not addressed in other P2P surveys. As a third point, it gives an overview of proposed P2P-based online social network applications, frameworks and architectures. In specific, it explores the technical details, inter-dependencies and maturity of the available solutions.
Don't Forget The Past: Recurrent Depth Estimation from Monocular Video
Venue: arXiv cs.CV 2020
Year: 2020

Autonomous cars need continuously updated depth information. Thus far, depth is mostly estimated independently for a single frame at a time, even if the method starts from video input. Our method produces a time series of depth maps, which makes it an ideal candidate for online learning approaches. In particular, we put three different types of depth estimation (supervised depth prediction, self-supervised depth prediction, and self-supervised depth completion) into a common framework. We integrate the corresponding networks with a ConvLSTM such that the spatiotemporal structures of depth across frames can be exploited to yield a more accurate depth estimation. Our method is flexible. It can be applied to monocular videos only or be combined with different types of sparse depth patterns. We carefully study the architecture of the recurrent network and its training strategy. We are first to successfully exploit recurrent networks for real-time self-supervised monocular depth estimation and completion. Extensive experiments show that our recurrent method outperforms its image-based counterpart consistently and significantly in both self-supervised scenarios. It also outperforms previous depth estimation methods of the three popular groups. Please refer to https://www.trace.ethz.ch/publications/2020/rec_depth_estimation/ for details.
Albert, an intermediate smart-contract language for the Tezos blockchain
Venue: arXiv cs.PL 2020
Year: 2020

Tezos is a smart-contract blockchain. Tezos smart contracts are written in a low-level stack-based language called Michelson. In this article we present Albert, an intermediate language for Tezos smart contracts which abstracts Michelson stacks as linearly typed records. We also describe its compiler to Michelson, written in Coq, that targets Mi-Cho-Coq, a formal specification of Michelson implemented in Coq.
DeepRecSys: A System for Optimizing End-To-End At-scale Neural Recommendation Inference
Venue: arXiv cs.DC 2020
Year: 2020

Neural personalized recommendation is the corner-stone of a wide collection of cloud services and products, constituting significant compute demand of the cloud infrastructure. Thus, improving the execution efficiency of neural recommendation directly translates into infrastructure capacity saving. In this paper, we devise a novel end-to-end modeling infrastructure, DeepRecInfra, that adopts an algorithm and system co-design methodology to custom-design systems for recommendation use cases. Leveraging the insights from the recommendation characterization, a new dynamic scheduler, DeepRecSched, is proposed to maximize latency-bounded throughput by taking into account characteristics of inference query size and arrival patterns, recommendation model architectures, and underlying hardware systems. By doing so, system throughput is doubled across the eight industry-representative recommendation models. Finally, design, deployment, and evaluation in at-scale production datacenter shows over 30% latency reduction across a wide variety of recommendation models running on hundreds of machines.
A Unified Framework for Coupled Tensor Completion
Venue: arXiv cs.LG 2020
Year: 2020

Coupled tensor decomposition reveals the joint data structure by incorporating priori knowledge that come from the latent coupled factors. The tensor ring (TR) decomposition is invariant under the permutation of tensors with different mode properties, which ensures the uniformity of decomposed factors and mode attributes. The TR has powerful expression ability and achieves success in some multi-dimensional data processing applications. To let coupled tensors help each other for missing component estimation, in this paper we utilize TR for coupled completion by sharing parts of the latent factors. The optimization model for coupled TR completion is developed with a novel Frobenius norm. It is solved by the block coordinate descent algorithm which efficiently solves a series of quadratic problems resulted from sampling pattern. The excess risk bound for this optimization model shows the theoretical performance enhancement in comparison with other coupled nuclear norm based methods. The proposed method is validated on numerical experiments on synthetic data, and experimental results on real-world data demonstrate its superiority over the state-of-the-art methods in terms of recovery accuracy.
Improved Analysis of Higher Order Random Walks and Applications
Venue: arXiv cs.DS 2020
Year: 2020

The motivation of this work is to extend the techniques of higher order random walks on simplicial complexes to analyze mixing times of Markov chains for combinatorial problems. Our main result is a sharp upper bound on the second eigenvalue of the down-up walk on a pure simplicial complex, in terms of the second eigenvalues of its links. We show some applications of this result in analyzing mixing times of Markov chains, including sampling independent sets of a graph and sampling common independent sets of two partition matroids.
Multiplex Word Embeddings for Selectional Preference Acquisition
Venue: arXiv cs.CL 2020
Year: 2020

Conventional word embeddings represent words with fixed vectors, which are usually trained based on co-occurrence patterns among words. In doing so, however, the power of such representations is limited, where the same word might be functionalized separately under different syntactic relations. To address this limitation, one solution is to incorporate relational dependencies of different words into their embeddings. Therefore, in this paper, we propose a multiplex word embedding model, which can be easily extended according to various relations among words. As a result, each word has a center embedding to represent its overall semantics, and several relational embeddings to represent its relational dependencies. Compared to existing models, our model can effectively distinguish words with respect to different relations without introducing unnecessary sparseness. Moreover, to accommodate various relations, we use a small dimension for relational embeddings and our model is able to keep their effectiveness. Experiments on selectional preference acquisition and word similarity demonstrate the effectiveness of the proposed model, and a further study of scalability also proves that our embeddings only need 1/20 of the original embedding size to achieve better performance.
Semi-supervised Learning via Conditional Rotation Angle Estimation
Venue: arXiv cs.CV 2020
Year: 2020

Self-supervised learning (SlfSL), aiming at learning feature representations through ingeniously designed pretext tasks without human annotation, has achieved compelling progress in the past few years. Very recently, SlfSL has also been identified as a promising solution for semi-supervised learning (SemSL) since it offers a new paradigm to utilize unlabeled data. This work further explores this direction by proposing to couple SlfSL with SemSL. Our insight is that the prediction target in SemSL can be modeled as the latent factor in the predictor for the SlfSL target. Marginalizing over the latent factor naturally derives a new formulation which marries the prediction targets of these two learning processes. By implementing this idea through a simple-but-effective SlfSL approach -- rotation angle prediction, we create a new SemSL approach called Conditional Rotation Angle Estimation (CRAE). Specifically, CRAE is featured by adopting a module which predicts the image rotation angle conditioned on the candidate image class. Through experimental evaluation, we show that CRAE achieves superior performance over the other existing ways of combining SlfSL and SemSL. To further boost CRAE, we propose two extensions to strengthen the coupling between SemSL target and SlfSL target in basic CRAE. We show that this leads to an improved CRAE method which can achieve the state-of-the-art SemSL performance.
Resolving the Scope of Speculation and Negation using Transformer-Based Architectures
Venue: arXiv cs.CL 2020
Year: 2020

Speculation is a naturally occurring phenomena in textual data, forming an integral component of many systems, especially in the biomedical information retrieval domain. Previous work addressing cue detection and scope resolution (the two subtasks of speculation detection) have ranged from rule-based systems to deep learning-based approaches. In this paper, we apply three popular transformer-based architectures, BERT, XLNet and RoBERTa to this task, on two publicly available datasets, BioScope Corpus and SFU Review Corpus, reporting substantial improvements over previously reported results (by at least 0.29 F1 points on cue detection and 4.27 F1 points on scope resolution). We also experiment with joint training of the model on multiple datasets, which outperforms the single dataset training approach by a good margin. We observe that XLNet consistently outperforms BERT and RoBERTa, contrary to results on other benchmark datasets. To confirm this observation, we apply XLNet and RoBERTa to negation detection and scope resolution, reporting state-of-the-art results on negation scope resolution for the BioScope Corpus (increase of 3.16 F1 points on the BioScope Full Papers, 0.06 F1 points on the BioScope Abstracts) and the SFU Review Corpus (increase of 0.3 F1 points).
Towards Coding for Human and Machine Vision: A Scalable Image Coding Approach
Venue: arXiv cs.CV 2020
Year: 2020

The past decades have witnessed the rapid development of image and video coding techniques in the era of big data. However, the signal fidelity-driven coding pipeline design limits the capability of the existing image/video coding frameworks to fulfill the needs of both machine and human vision. In this paper, we come up with a novel image coding framework by leveraging both the compressive and the generative models, to support machine vision and human perception tasks jointly. Given an input image, the feature analysis is first applied, and then the generative model is employed to perform image reconstruction with features and additional reference pixels, in which compact edge maps are extracted in this work to connect both kinds of vision in a scalable way. The compact edge map serves as the basic layer for machine vision tasks, and the reference pixels act as a sort of enhanced layer to guarantee signal fidelity for human vision. By introducing advanced generative models, we train a flexible network to reconstruct images from compact feature representations and the reference pixels. Experimental results demonstrate the superiority of our framework in both human visual quality and facial landmark detection, which provide useful evidence on the emerging standardization efforts on MPEG VCM (Video Coding for Machine).
Online Memorization of Random Firing Sequences by a Recurrent Neural Network
Venue: arXiv cs.IT 2020
Year: 2020

This paper studies the capability of a recurrent neural network model to memorize random dynamical firing patterns by a simple local learning rule. Two modes of learning/memorization are considered: The first mode is strictly online, with a single pass through the data, while the second mode uses multiple passes through the data. In both modes, the learning is strictly local (quasi-Hebbian): At any given time step, only the weights between the neurons firing (or supposed to be firing) at the previous time step and those firing (or supposed to be firing) at the present time step are modified. The main result of the paper is an upper bound on the probability that the single-pass memorization is not perfect. It follows that the memorization capacity in this mode asymptotically scales like that of the classical Hopfield model (which, in contrast, memorizes static patterns). However, multiple-rounds memorization is shown to achieve a higher capacity (with a nonvanishing number of bits per connection/synapse). These mathematical findings may be helpful for understanding the functions of short-term memory and long-term memory in neuroscience.
Privacy-Preserving Deep Learning Computation for Geo-Distributed Medical Big-Data Platforms
Venue: arXiv cs.LG 2020
Year: 2020

This paper proposes a distributed deep learning framework for privacy-preserving medical data training. In order to avoid patients' data leakage in medical platforms, the hidden layers in the deep learning framework are separated and where the first layer is kept in platform and others layers are kept in a centralized server. Whereas keeping the original patients' data in local platforms maintain their privacy, utilizing the server for subsequent layers improves learning performance by using all data from each platform during training.
Poly-time universality and limitations of deep learning
Venue: arXiv cs.LG 2020
Year: 2020

The goal of this paper is to characterize function distributions that deep learning can or cannot learn in poly-time. A universality result is proved for SGD-based deep learning and a non-universality result is proved for GD-based deep learning; this also gives a separation between SGD-based deep learning and statistical query algorithms: (1) {\it Deep learning with SGD is efficiently universal.} Any function distribution that can be learned from samples in poly-time can also be learned by a poly-size neural net trained with SGD on a poly-time initialization with poly-steps, poly-rate and possibly poly-noise. Therefore deep learning provides a universal learning paradigm: it was known that the approximation and estimation errors could be controlled with poly-size neural nets, using ERM that is NP-hard; this new result shows that the optimization error can also be controlled with SGD in poly-time. The picture changes for GD with large enough batches: (2) {\it Result (1) does not hold for GD:} Neural nets of poly-size trained with GD (full gradients or large enough batches) on any initialization with poly-steps, poly-range and at least poly-noise cannot learn any function distribution that has super-polynomial {\it cross-predictability,} where the cross-predictability gives a measure of ``average'' function correlation -- relations and distinctions to the statistical dimension are discussed. In particular, GD with these constraints can learn efficiently monomials of degree $k$ if and only if $k$ is constant. Thus (1) and (2) point to an interesting contrast: SGD is universal even with some poly-noise while full GD or SQ algorithms are not (e.g., parities).
Blockchain-based Smart-IoT Trust Zone Measurement Architecture
Venue: arXiv cs.CR 2020
Year: 2020

With a rapid growth in the IT industry, Internet of Things (IoT) has gained a tremendous attention and become a central aspect of our environment. In IoT the things (devices) communicate and exchange the data without the act of human intervention. Such autonomy and proliferation of IoT ecosystem make the devices more vulnerable to attacks. In this paper, we propose a behavior monitor in IoT-Blockchain setup which can provide trust-confidence to outside networks. Behavior monitor extracts the activity of each device and analyzes the behavior using deep auto-encoders. In addition, we also incorporate Trusted Execution Technology (Intel SGX) in order to provide a secure execution environment for applications and data on blockchain. Finally, in evaluation we analyze three IoT devices data that is infected by mirai attack. The evaluation results demonstrate the ability of our proposed method in terms of accuracy and time required for detection.
Achieving Competitiveness in Online Problems
Venue: arXiv cs.DS 2020
Year: 2020

In the setting of online algorithms, the input is initially not present but rather arrive one-by-one over time and after each input, the algorithm has to make a decision. Depending on the formulation of the problem, the algorithm might be allowed to change its previous decisions or not at a later time. We analyze two problems to show that it is possible for an online algorithm to become more competitive by changing its former decisions. We first consider the online edge orientation in which the edges arrive one-by-one to an empty graph and the aim is to orient them in a way such that the maximum in-degree is minimized. We then consider the online bipartite b-matching. In this problem, we are given a bipartite graph where one side of the graph is initially present and where the other side arrive online. The goal is to maintain a matching set such that the maximum degree in the set is minimized. For both of the problems, the best achievable competitive ratio is $Θ(\log n)$ over n input arrivals when decisions are irreversible. We study three algorithms for these problems, two for the former and one for the latter, that achieve O(1) competitive ratio by changing O(n) of their decisions over n arrivals. In addition to that, we analyze one of the algorithms, the shortest path algorithm, against an adversary. Through that, we prove some new results about algorithms performance.