OpenRaiser/Intern-Atlas huggingface dataset:
Egocentric Bias and Doubt in Cognitive Agents
Venue: arXiv cs.AI 2019
Year: 2019

Modeling social interactions based on individual behavior has always been an area of interest, but prior literature generally presumes rational behavior. Thus, such models may miss out on capturing the effects of biases humans are susceptible to. This work presents a method to model egocentric bias, the real-life tendency to emphasize one's own opinion heavily when presented with multiple opinions. We use a symmetric distribution centered at an agent's own opinion, as opposed to the Bounded Confidence (BC) model used in prior work. We consider a game of iterated interactions where an agent cooperates based on its opinion about an opponent. Our model also includes the concept of domain-based self-doubt, which varies as the interaction succeeds or not. An increase in doubt makes an agent reduce its egocentricity in subsequent interactions, thus enabling the agent to learn reactively. The agent system is modeled with factions not having a single leader, to overcome some of the issues associated with leader-follower factions. We find that agents belonging to factions perform better than individual agents. We observe that an intermediate level of egocentricity helps the agent perform at its best, which concurs with conventional wisdom that neither overconfidence nor low self-esteem brings benefits.
Improving Device-Edge Cooperative Inference of Deep Learning via 2-Step Pruning
Venue: arXiv cs.NI 2019
Year: 2019

Deep neural networks (DNNs) are state-of-the-art solutions for many machine learning applications, and have been widely used on mobile devices. Running DNNs on resource-constrained mobile devices often requires the help from edge servers via computation offloading. However, offloading through a bandwidth-limited wireless link is non-trivial due to the tight interplay between the computation resources on mobile devices and wireless resources. Existing studies have focused on cooperative inference where DNN models are partitioned at different neural network layers, and the two parts are executed at the mobile device and the edge server, respectively. Since the output data size of a DNN layer can be larger than that of the raw data, offloading intermediate data between layers can suffer from high transmission latency under limited wireless bandwidth. In this paper, we propose an efficient and flexible 2-step pruning framework for DNN partition between mobile devices and edge servers. In our framework, the DNN model only needs to be pruned once in the training phase where unimportant convolutional filters are removed iteratively. By limiting the pruning region, our framework can greatly reduce either the wireless transmission workload of the device or the total computation workload. A series of pruned models are generated in the training phase, from which the framework can automatically select to satisfy varying latency and accuracy requirements. Furthermore, coding for the intermediate data is added to provide extra transmission workload reduction. Our experiments show that the proposed framework can achieve up to 25.6$\times$ reduction on transmission workload, 6.01$\times$ acceleration on total computation and 4.81$\times$ reduction on end-to-end latency as compared to partitioning the original DNN model without pruning.
Unsupervised Data Imputation via Variational Inference of Deep Subspaces
Venue: arXiv cs.CV 2019
Year: 2019

A wide range of systems exhibit high dimensional incomplete data. Accurate estimation of the missing data is often desired, and is crucial for many downstream analyses. Many state-of-the-art recovery methods involve supervised learning using datasets containing full observations. In contrast, we focus on unsupervised estimation of missing image data, where no full observations are available - a common situation in practice. Unsupervised imputation methods for images often employ a simple linear subspace to capture correlations between data dimensions, omitting more complex relationships. In this work, we introduce a general probabilistic model that describes sparse high dimensional imaging data as being generated by a deep non-linear embedding. We derive a learning algorithm using a variational approximation based on convolutional neural networks and discuss its relationship to linear imputation models, the variational auto encoder, and deep image priors. We introduce sparsity-aware network building blocks that explicitly model observed and missing data. We analyze proposed sparsity-aware network building blocks, evaluate our method on public domain imaging datasets, and conclude by showing that our method enables imputation in an important real-world problem involving medical images. The code is freely available as part of the \verb|neuron| library at http://github.com/adalca/neuron.
The One-Way Communication Complexity of Dynamic Time Warping Distance
Venue: arXiv cs.DS 2019
Year: 2019

We resolve the randomized one-way communication complexity of Dynamic Time Warping (DTW) distance. We show that there is an efficient one-way communication protocol using $\widetilde{O}(n/α)$ bits for the problem of computing an $α$-approximation for DTW between strings $x$ and $y$ of length $n$, and we prove a lower bound of $Ω(n / α)$ bits for the same problem. Our communication protocol works for strings over an arbitrary metric of polynomial size and aspect ratio, and we optimize the logarithmic factors depending on properties of the underlying metric, such as when the points are low-dimensional integer vectors equipped with various metrics or have bounded doubling dimension. We also consider linear sketches of DTW, showing that such sketches must have size $Ω(n)$.
PTracer: A Linux Kernel Patch Trace Bot
Venue: arXiv cs.SE 2019
Year: 2019

We present PTracer, a Linux kernel patch trace bot based on an improved PatchNet. PTracer continuously monitors new patches in the git repository of the mainline Linux kernel, filters out unconcerned ones, classifies the rest as bug-fixing or non bug-fixing patches, and reports bug-fixing patches to the kernel experts of commercial operating systems. We use the patches in February 2019 of the mainline Linux kernel to perform the test. As a result, PTracer recommended 151 patches to CGEL kernel experts out of 5,142, and 102 of which were accepted. PTracer has been successfully applied to a commercial operating system and has the advantages of improving software quality and saving labor cost.
DMON: A Distributed Heterogeneous N-Variant System
Venue: arXiv cs.CR 2019
Year: 2019

N-Variant Execution (NVX) systems utilize software diversity techniques for enhancing software security. The general idea is to run multiple different variants of the same program alongside each other while monitoring their run-time behavior. If the internal disparity between the running variants causes observable differences in response to malicious inputs, the monitor can detect such divergences in execution and then raise an alert and/or terminate execution. Existing NVX systems execute multiple, artificially diversified program variants on a single host. This paper presents a novel, distributed NVX design that executes program variants across multiple heterogeneous host computers; our prototype implementation combines an x86-64 host with an ARMv8 host. Our approach greatly increases the level of "internal different-ness" between the simultaneously running variants that can be supported, encompassing different instruction sets, endianness, calling conventions, system call interfaces, and potentially also differences in hardware security features. A major challenge to building such a heterogeneous distributed NVX system is performance. We present solutions to some of the main performance challenges. We evaluate our prototype system implementing these ideas to show that it can provide reasonable performance on a wide range of realistic workloads.
Lenses and Learners
Venue: arXiv cs.LG 2019
Year: 2019

Lenses are a well-established structure for modelling bidirectional transformations, such as the interactions between a database and a view of it. Lenses may be symmetric or asymmetric, and may be composed, forming the morphisms of a monoidal category. More recently, the notion of a learner has been proposed: these provide a compositional way of modelling supervised learning algorithms, and again form the morphisms of a monoidal category. In this paper, we show that the two concepts are tightly linked. We show both that there is a faithful, identity-on-objects symmetric monoidal functor embedding a category of asymmetric lenses into the category of learners, and furthermore there is such a functor embedding the category of learners into a category of symmetric lenses.
Polar Coding with Chemical Reaction Networks
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we propose a new polar coding scheme with molecular programming, which is capable of highly parallel implementation at a nano-scale without a need of electrical power sources. We designed chemical reaction networks (CRN) to employ either successive cancellation (SC) or maximum-likelihood (ML) decoding schemes for short polar codes. From ordinary differential equation (ODE) analysis of the proposed CRNs, we demonstrate that SC and ML decoding achieve accurate computations across fully-parallel chemical reactions. We also make a comparison in terms of the number of required chemical reactions and species, where the superiority of ML decoder over SC decoder is observed for very short block lengths.
Post-Quantum Cryptographic Hardware Primitives
Venue: arXiv cs.CR 2019
Year: 2019

The development and implementation of post-quantum cryptosystems have become a pressing issue in the design of secure computing systems, as general quantum computers have become more feasible in the last two years. In this work, we introduce a set of hardware post-quantum cryptographic primitives (PCPs) consisting of four frequently used security components, i.e., public-key cryptosystem (PKC), key exchange (KEX), oblivious transfer (OT), and zero-knowledge proof (ZKP). In addition, we design a high speed polynomial multiplier to accelerate these primitives. These primitives will aid researchers and designers in constructing quantum-proof secure computing systems in the post-quantum era.
A tractable ellipsoidal approximation for voltage regulation problems
Venue: arXiv cs.SY 2019
Year: 2019

We present a machine learning approach to the solution of chance constrained optimizations in the context of voltage regulation problems in power system operation. The novelty of our approach resides in approximating the feasible region of uncertainty with an ellipsoid. We formulate this problem using a learning model similar to Support Vector Machines (SVM) and propose a sampling algorithm that efficiently trains the model. We demonstrate our approach on a voltage regulation problem using standard IEEE distribution test feeders.
Interpreting and Understanding Graph Convolutional Neural Network using Gradient-based Attribution Method
Venue: arXiv cs.LG 2019
Year: 2019

To solve the problem that convolutional neural networks (CNNs) are difficult to process non-grid type relational data like graphs, Kipf et al. proposed a graph convolutional neural network (GCN). The core idea of the GCN is to perform two-fold informational fusion for each node in a given graph during each iteration: the fusion of graph structure information and the fusion of node feature dimensions. Because of the characteristic of the combinatorial generalizations, GCN has been widely used in the fields of scene semantic relationship analysis, natural language processing and few-shot learning etc. However, due to its two-fold informational fusion involves mathematical irreversible calculations, it is hard to explain the decision reason for the prediction of the each node classification. Unfortunately, most of the existing attribution analysis methods concentrate on the models like CNNs, which are utilized to process grid-like data. It is difficult to apply those analysis methods to the GCN directly. It is because compared with the independence among CNNs input data, there is correlation between the GCN input data. This resulting in the existing attribution analysis methods can only obtain the partial model contribution from the central node features to the final decision of the GCN, but ignores the other model contribution from central node features and its neighbor nodes features to that decision. To this end, we propose a gradient attribution analysis method for the GCN called Node Attribution Method (NAM), which can get the model contribution from not only the central node but also its neighbor nodes to the GCN output. We also propose the Node Importance Visualization (NIV) method to visualize the central node and its neighbor nodes based on the value of the contribution...
Logic Rules Powered Knowledge Graph Embedding
Venue: arXiv cs.AI 2019
Year: 2019

Large scale knowledge graph embedding has attracted much attention from both academia and industry in the field of Artificial Intelligence. However, most existing methods concentrate solely on fact triples contained in the given knowledge graph. Inspired by the fact that logic rules can provide a flexible and declarative language for expressing rich background knowledge, it is natural to integrate logic rules into knowledge graph embedding, to transfer human knowledge to entity and relation embedding, and strengthen the learning process. In this paper, we propose a novel logic rule-enhanced method which can be easily integrated with any translation based knowledge graph embedding model, such as TransE . We first introduce a method to automatically mine the logic rules and corresponding confidences from the triples. And then, to put both triples and mined logic rules within the same semantic space, all triples in the knowledge graph are represented as first-order logic. Finally, we define several operations on the first-order logic and minimize a global loss over both of the mined logic rules and the transformed first-order logics. We conduct extensive experiments for link prediction and triple classification on three datasets: WN18, FB166, and FB15K. Experiments show that the rule-enhanced method can significantly improve the performance of several baselines. The highlight of our model is that the filtered Hits@1, which is a pivotal evaluation in the knowledge inference task, has a significant improvement (up to 700% improvement).
Timed Systems through the Lens of Logic
Venue: arXiv cs.LO 2019
Year: 2019

In this paper, we analyze timed systems with data structures, using a rich interplay of logic and properties of graphs. We start by describing behaviors of timed systems using graphs with timing constraints. Such a graph is called realizable if we can assign time-stamps to nodes or events so that they are consistent with the timing constraints. The logical definability of several graph properties has been a challenging problem, and we show, using a highly non-trivial argument, that the realizability property for collections of graphs with strict timing constraints is logically definable in a class of propositional dynamic logic (EQ-ICPDL), which is strictly contained in MSO. Using this result, we propose a novel, algorithmically efficient and uniform proof technique for the analysis of timed systems enriched with auxiliary data structures, like stacks and queues. Our technique unravels new results (for emptiness checking as well as model checking) for timed systems with richer features than considered so far, while also recovering existing results.
Fifty Shades of Congestion Control: A Performance and Interactions Evaluation
Venue: arXiv cs.NI 2019
Year: 2019

Congestion control algorithms are crucial in achieving high utilization while preventing overloading the network. Over the years, many different congestion control algorithms have been developed, each trying to improve in specific situations. However, their interactions and co-existence has, to date, not been thoroughly evaluated, which is the focus of this paper. Through head-to-head comparisons of representatives from loss-based, delay-based and hybrid types of congestion control algorithms, we reveal that fairness in resources claimed is often not attained, especially when flows sharing a link have different RTTs.
Continuous-time Signal Temporal Logic Planning with Control Barrier Function
Venue: arXiv cs.SY 2019
Year: 2019

Temporal Logic (TL) guided control problems have gained interests in recent years. By using the TL, one can specify a wide range of temporal constraints on the system and is widely used in cyber-physical systems. On the other hand, Control Barrier Functions have also gained interests in the context of safety critical applications. However, most of the existing approaches only focus on discrete-time dynamical systems. In this paper, we propose an offline trajectory planner for linear systems subject to safety and temporal specifications. Such specifications can be expressed as logical junctions or disjunctions of linear CBFs, or as STL specifications with linear predicates. Our planner produces trajectories that are valid in continuous time, while assuming only discrete-time control updates and arbitrary time interval in the STL formula. Our planner is based on a Mixed Integer Quadratic Programming (MIQP) formulation, where the linear STL predicates are encoded as set of linear constraints to guarantee satisfaction at on a finite discrete set of time instants, while we use CBFs to derive constraints that guarantee continuous satisfaction between time instants. Moreover, we have shown the predicates can be encoded as time-based CBF constraints for system with any relative degrees. We validate our theoretical results and formulation through numerical simulations.
Neural Network Model Extraction Attacks in Edge Devices by Hearing Architectural Hints
Venue: arXiv cs.CR 2019
Year: 2019

As neural networks continue their reach into nearly every aspect of software operations, the details of those networks become an increasingly sensitive subject. Even those that deploy neural networks embedded in physical devices may wish to keep the inner working of their designs hidden -- either to protect their intellectual property or as a form of protection from adversarial inputs. The specific problem we address is how, through heavy system stack, given noisy and imperfect memory traces, one might reconstruct the neural network architecture including the set of layers employed, their connectivity, and their respective dimension sizes. Considering both the intra-layer architecture features and the inter-layer temporal association information introduced by the DNN design empirical experience, we draw upon ideas from speech recognition to solve this problem. We show that off-chip memory address traces and PCIe events provide ample information to reconstruct such neural network architectures accurately. We are the first to propose such accurate model extraction techniques and demonstrate an end-to-end attack experimentally in the context of an off-the-shelf Nvidia GPU platform with full system stack. Results show that the proposed techniques achieve a high reverse engineering accuracy and improve the one's ability to conduct targeted adversarial attack with success rate from 14.6\%$\sim$25.5\% (without network architecture knowledge) to 75.9\% (with extracted network architecture).
Processing Data Where It Makes Sense: Enabling In-Memory Computation
Venue: arXiv cs.AR 2019
Year: 2019

Today's systems are overwhelmingly designed to move data to computation. This design choice goes directly against at least three key trends in systems that cause performance, scalability and energy bottlenecks: (1) data access from memory is already a key bottleneck as applications become more data-intensive and memory bandwidth and energy do not scale well, (2) energy consumption is a key constraint in especially mobile and server systems, (3) data movement is very expensive in terms of bandwidth, energy and latency, much more so than computation. At the same time, conventional memory technology is facing many scaling challenges in terms of reliability, energy, and performance. As a result, memory system architects are open to organizing memory in different ways and making it more intelligent, at the expense of higher cost. The emergence of 3D-stacked memory plus logic as well as the adoption of error correcting codes inside DRAM chips, and the necessity for designing new solutions to serious reliability and security issues, such as the RowHammer phenomenon, are an evidence of this trend. Recent research aims to practically enable computation close to data. We discuss at least two promising directions for processing-in-memory (PIM): (1) performing massively-parallel bulk operations in memory by exploiting the analog operational properties of DRAM, with low-cost changes, (2) exploiting the logic layer in 3D-stacked memory technology to accelerate important data-intensive applications. In both approaches, we describe and tackle relevant cross-layer research, design, and adoption challenges in devices, architecture, systems, and programming models. Our focus is on the development of in-memory processing designs that can be adopted in real computing platforms at low cost.
DCSYNTH: Guided Reactive Synthesis with Soft Requirements
Venue: arXiv cs.LO 2019
Year: 2019

In reactive controller synthesis, a number of implementations (controllers) are possible for a given specification because of the incomplete nature of specification. To choose the most desirable one from the various options, we need to specify additional properties which can guide the synthesis. In this paper, We propose a technique for guided controller synthesis from regular requirements which are specified using an interval temporal logic QDDC. We find that QDDC is well suited for guided synthesis due to its superiority in dealing with both qualitative and quantitative specifications. Our framework allows specification consisting of both hard and soft requirements as QDDC formulas. We have also developed a method and a tool DCSynth, which computes a controller that invariantly satisfies the hard requirement and it optimally meets the soft requirement. The proposed technique is also useful in dealing with conflicting i.e., unrealizable requirements, by making some of them as soft requirements. Case studies are carried out to demonstrate the effectiveness of the soft requirement guided synthesis in obtaining high-quality controllers. The quality of the synthesized controllers is compared using metrics measuring both the guaranteed and the expected case behaviour of the controlled system. Tool DCSynth facilitates such comparison.