OpenRaiser/Intern-Atlas huggingface dataset:
Differential Temporal Difference Learning
Venue: arXiv cs.LG 2020
Year: 2020

Value functions derived from Markov decision processes arise as a central component of algorithms as well as performance metrics in many statistics and engineering applications of machine learning techniques. Computation of the solution to the associated Bellman equations is challenging in most practical cases of interest. A popular class of approximation techniques, known as Temporal Difference (TD) learning algorithms, are an important sub-class of general reinforcement learning methods. The algorithms introduced in this paper are intended to resolve two well-known difficulties of TD-learning approaches: Their slow convergence due to very high variance, and the fact that, for the problem of computing the relative value function, consistent algorithms exist only in special cases. First we show that the gradients of these value functions admit a representation that lends itself to algorithm design. Based on this result, a new class of differential TD-learning algorithms is introduced. For Markovian models on Euclidean space with smooth dynamics, the algorithms are shown to be consistent under general conditions. Numerical results show dramatic variance reduction when compared to standard methods.
FPDeep: Scalable Acceleration of CNN Training on Deeply-Pipelined FPGA Clusters
Venue: arXiv cs.LG 2020
Year: 2020

Deep Neural Networks (DNNs) have revolutionized numerous applications, but the demand for ever more performance remains unabated. Scaling DNN computations to larger clusters is generally done by distributing tasks in batch mode using methods such as distributed synchronous SGD. Among the issues with this approach is that to make the distributed cluster work with high utilization, the workload distributed to each node must be large, which implies nontrivial growth in the SGD mini-batch size. In this paper, we propose a framework called FPDeep, which uses a hybrid of model and layer parallelism to configure distributed reconfigurable clusters to train DNNs. This approach has numerous benefits. First, the design does not suffer from batch size growth. Second, novel workload and weight partitioning leads to balanced loads of both among nodes. And third, the entire system is a fine-grained pipeline. This leads to high parallelism and utilization and also minimizes the time features need to be cached while waiting for back-propagation. As a result, storage demand is reduced to the point where only on-chip memory is used for the convolution layers. We evaluate FPDeep with the Alexnet, VGG-16, and VGG-19 benchmarks. Experimental results show that FPDeep has good scalability to a large number of FPGAs, with the limiting factor being the FPGA-to-FPGA bandwidth. With 6 transceivers per FPGA, FPDeep shows linearity up to 83 FPGAs. Energy efficiency is evaluated with respect to GOPs/J. FPDeep provides, on average, 6.36x higher energy efficiency than comparable GPU servers.
Mutual Context Network for Jointly Estimating Egocentric Gaze and Actions
Venue: arXiv cs.CV 2020
Year: 2020

In this work, we address two coupled tasks of gaze prediction and action recognition in egocentric videos by exploring their mutual context. Our assumption is that in the procedure of performing a manipulation task, what a person is doing determines where the person is looking at, and the gaze point reveals gaze and non-gaze regions which contain important and complementary information about the undergoing action. We propose a novel mutual context network (MCN) that jointly learns action-dependent gaze prediction and gaze-guided action recognition in an end-to-end manner. Experiments on public egocentric video datasets demonstrate that our MCN achieves state-of-the-art performance of both gaze prediction and action recognition.
Resource Allocation in One-dimensional Distributed Service Networks
Venue: arXiv cs.PF 2020
Year: 2020

We consider assignment policies that allocate resources to users, where both resources and users are located on a one-dimensional line. First, we consider unidirectional assignment policies that allocate resources only to users located to their left. We propose the Move to Right (MTR) policy, which scans from left to right assigning nearest rightmost available resource to a user, and contrast it to the Unidirectional Gale-Shapley (UGS) matching policy. While both these policies are optimal among all unidirectional policies, we show that they are equivalent with respect to the expected distance traveled by a request (request distance), although MTR is fairer. Moreover, we show that when user and resource locations are modeled by statistical point processes, and resources are allowed to satisfy more than one user, the spatial system under unidirectional policies can be mapped into bulk service queuing systems, thus allowing the application of a plethora of queuing theory results that yield closed form expressions. As we consider a case where different resources can satisfy different numbers of users, we also generate new results for bulk service queues. We also consider bidirectional policies where there are no directional restrictions on resource allocation and develop an algorithm for computing the optimal assignment which is more efficient than known algorithms in the literature when there are more resources than users. Finally, numerical evaluation of performance of unidirectional and bidirectional allocation schemes yields design guidelines beneficial for resource placement.
Reduce Transmission Delay for Cache-Aided Two-Layer Network
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we consider a cache-aided relay network, where a single server consisting of a library of N files connects with K1 relays through a shared noiseless link, and each relay connects with K2 users through a shared noiseless link. Each relay and user are equipped with a cache memory of M1 and M2 files, respectively. We propose a centralized and a decentralized coded caching scheme that exploit the spared transmission time resource by allowing concurrent transmission between the two layers. It is shown that both caching schemes are approximately optimal, and greatly reduce the transmission delay compared to the previously known caching schemes. Surprisingly, we show that when the relay's caching size is equal to a threshold that is strictly smaller than N (e.g. M1=0.382N under the decentralized setup and (K1-1)N/K1 under the centralized setup, when K1=2), our schemes achieve the same delay as if each relay had access to the full library. To our best knowledge, this is the first result showing that even the caching size is strictly smaller than the library's size, increasing the caching size is wasteful in reducing the transmission latency.
Hand Segmentation and Fingertip Tracking from Depth Camera Images Using Deep Convolutional Neural Network and Multi-task SegNet
Venue: arXiv cs.CV 2020
Year: 2020

Hand segmentation and fingertip detection play an indispensable role in hand gesture-based human-machine interaction systems. In this study, we propose a method to discriminate hand components and to locate fingertips in RGB-D images. The system consists of three main steps: hand detection using RGB images providing regions which are considered as promising areas for further processing, hand segmentation, and fingertip detection using depth image and our modified SegNet, a single lightweight architecture that can process two independent tasks at the same time. The experimental results show that our system is a promising method for hand segmentation and fingertip detection which achieves a comparable performance while model complexity is suitable for real-time applications.
Passage Re-ranking with BERT
Venue: arXiv cs.IR 2020
Year: 2020

Recently, neural models pretrained on a language modeling task, such as ELMo (Peters et al., 2017), OpenAI GPT (Radford et al., 2018), and BERT (Devlin et al., 2018), have achieved impressive results on various natural language processing tasks such as question-answering and natural language inference. In this paper, we describe a simple re-implementation of BERT for query-based passage re-ranking. Our system is the state of the art on the TREC-CAR dataset and the top entry in the leaderboard of the MS MARCO passage retrieval task, outperforming the previous state of the art by 27% (relative) in MRR@10. The code to reproduce our results is available at https://github.com/nyu-dl/dl4marco-bert
Linear complementary dual, maximum distance separable codes
Venue: arXiv cs.IT 2020
Year: 2020

Linear complementary dual (LCD) maximum distance separable (MDS) codes are constructed to given specifications. For given $n$ and $r<n$, with $n$ or $r$ (or both) odd, MDS LCD $(n,r)$ codes are constructed over finite fields whose characteristic does not divide $n$. Series of LCD MDS codes are constructed to required rate and required error-correcting capability. Given the field $GF(q)$ and $n/(q-1)$, LCD MDS codes of length $n$ and dimension $r$ are explicitly constructed over $GF(q)$ for all $r<n$ when $n$ is odd and for all odd $r<n$ when $n$ is even. For given dimension and given error-correcting capability LCD MDS codes are constructed to these specifications with smallest possible length. Series of asymptotically good LCD MDS codes are explicitly constructed. Efficient encoding and decoding algorithms exist for all the constructed codes. Linear complementary dual codes have importance in data storage, communications' systems and security.
Uncovering Vulnerable Industrial Control Systems from the Internet Core
Venue: arXiv cs.NI 2020
Year: 2020

Industrial control systems (ICS) are managed remotely with the help of dedicated protocols that were originally designed to work in walled gardens. Many of these protocols have been adapted to Internet transport and support wide-area communication. ICS now exchange insecure traffic on an inter-domain level, putting at risk not only common critical infrastructure but also the Internet ecosystem (e.g., DRDoS~attacks). In this paper, we uncover unprotected inter-domain ICS traffic at two central Internet vantage points, an IXP and an ISP. This traffic analysis is correlated with data from honeypots and Internet-wide scans to separate industrial from non-industrial ICS traffic. We provide an in-depth view on Internet-wide ICS communication. Our results can be used i) to create precise filters for potentially harmful non-industrial ICS traffic, and ii) to detect ICS sending unprotected inter-domain ICS traffic, being vulnerable to eavesdropping and traffic manipulation attacks.
Comparing Knowledge-based Reinforcement Learning to Neural Networks in a Strategy Game
Venue: arXiv cs.AI 2020
Year: 2020

The paper reports on an experiment, in which a Knowledge-Based Reinforcement Learning (KB-RL) method was compared to a Neural Network (NN) approach in solving a classical Artificial Intelligence (AI) task. In contrast to NNs, which require a substantial amount of data to learn a good policy, the KB-RL method seeks to encode human knowledge into the solution, considerably reducing the amount of data needed for a good policy. By means of Reinforcement Learning (RL), KB-RL learns to optimize the model and improves the output of the system. Furthermore, KB-RL offers the advantage of a clear explanation of the taken decisions as well as transparent reasoning behind the solution. The goal of the reported experiment was to examine the performance of the KB-RL method in contrast to the Neural Network and to explore the capabilities of KB-RL to deliver a strong solution for the AI tasks. The results show that, within the designed settings, KB-RL outperformed the NN, and was able to learn a better policy from the available amount of data. These results support the opinion that Artificial Intelligence can benefit from the discovery and study of alternative approaches, potentially extending the frontiers of AI.
A wireless secure key distribution system with no couriers: a One-Time-Pad Revival
Venue: arXiv cs.CR 2020
Year: 2020

Among the problems to guarantee secrecy for in-transit information, the difficulties involved in renewing cryptographic keys in a secure way using couriers, the perfect secrecy encryption method known as One-Time-Pad (OTP) became almost obsolete. Pure quantum key distribution (QKD) ideally offers security for key distribution and could revive OTP. However, special networks that may need optical fibers, satellite, relay stations, expensive detection equipment compared with telecom technology and the slow protocol offer powerful obstacles for widespread use of QKD. Classical encryption methods flood the secure communication landscape. Many of them rely its security on historical difficulties such as factoring of large numbers -- their alleged security sometimes are presented as the difficulty to brake encryption by brute force. The possibility for a mathematical breakthrough that could make factoring trivial are poorly discussed. This work proposes a solution to bring perfect secrecy to in-transit communication and without the above problems. It shows the key distribution scheme (nicknamed KeyBITS Platform) based on classical signals carrying information but that carry with them recordings of quantum noise. Legitimate users start with a shared information of the coding bases used that gives them an information advantage that allows easy signal recovery. The recorded noise protects the legitimate users and block the attacker's access. This shared information is refreshed at the end of each batch of keys sent providing the secret shared information for the next round. With encryption keys distilled from securely transmitted signals at each round OTP can be revived and at fast speeds.
RepChain: A Reputation-based Secure, Fast and High Incentive Blockchain System via Sharding
Venue: arXiv cs.CR 2020
Year: 2020

In today's blockchain system, designing a secure and high throughput blockchain on par with a centralized payment system is a difficult task. Sharding is one of the most worthwhile emerging technologies for improving the system throughput while maintain high security level. However, previous sharding related designs have two main limitations: Firstly, the throughput of their random-based sharding system is not high enough as they did not leverage the heterogeneity among validators. Secondly, to design an incentive mechanism to promote cooperation could incur a huge overhead on their system. In this paper, we propose RepChain, a reputation-based secure and fast blockchain system via sharding, which also provides high incentive to stimulate node cooperation. RepChain utilizes reputation to explicitly characterize the heterogeneity among the validators and lay the foundation for the incentive mechanism. We propose a new double-chain architecture which includes transaction chain and reputation chain. For transaction chain, a Raft-based synchronous consensus that can achieve high throughput has been presented. For reputation chain, the synchronous Byzantine fault tolerance that combines collective signing has been utilized to achieve a consensus on both reputation score and the related transaction blocks. It supports a high throughput transaction chain with moderate generation speed. Moreover, we propose a reputation-based sharding and leader selection scheme. To analyze the security of RepChain, we propose a recursive formula to calculate the epoch security within only O(km^2) time. Furthermore, we implement and evaluate RepChain on the Amazon Web Service platform. The results show our solution can enhance both throughout and security level of the existing sharding-based blockchain system.
Coded Caching based on Combinatorial Designs
Venue: arXiv cs.IT 2020
Year: 2020

We consider the standard broadcast setup with a single server broadcasting information to a number of clients, each of which contains local storage (called \textit{cache}) of some size, which can store some parts of the available files at the server. The centralized coded caching framework, consists of a caching phase and a delivery phase, both of which are carefully designed in order to use the cache and the channel together optimally. In prior literature, various combinatorial structures have been used to construct coded caching schemes. In this work, we propose a binary matrix model to construct the coded caching scheme. The ones in such a \textit{caching matrix} indicate uncached subfiles at the users. Identity submatrices of the caching matrix represent transmissions in the delivery phase. Using this model, we then propose several novel constructions for coded caching based on the various types of combinatorial designs. While most of the schemes constructed in this work (based on existing designs) have a high cache requirement (uncached fraction being $Θ(\frac{1}{\sqrt{K}})$ or $Θ(\frac{1}{K})$, $K$ being the number of users), they provide a rate that is either constant or decreasing ($O(\frac{1}{K})$) with increasing $K$, and moreover require competitively small levels of subpacketization (being $O(K^i), 1\leq i\leq 3$), which is an extremely important parameter in practical applications of coded caching. We mark this work as another attempt to exploit the well-developed theory of combinatorial designs for the problem of constructing caching schemes, utilizing the binary caching model we develop.
Modeling Latent Sentence Structure in Neural Machine Translation
Venue: arXiv cs.CL 2020
Year: 2020

Recently it was shown that linguistic structure predicted by a supervised parser can be beneficial for neural machine translation (NMT). In this work we investigate a more challenging setup: we incorporate sentence structure as a latent variable in a standard NMT encoder-decoder and induce it in such a way as to benefit the translation task. We consider German-English and Japanese-English translation benchmarks and observe that when using RNN encoders the model makes no or very limited use of the structure induction apparatus. In contrast, CNN and word-embedding-based encoders rely on latent graphs and force them to encode useful, potentially long-distance, dependencies.
A Pre-Expectation Calculus for Probabilistic Sensitivity
Venue: arXiv cs.LO 2020
Year: 2020

Sensitivity properties describe how changes to the input of a program affect the output, typically by upper bounding the distance between the outputs of two runs by a monotone function of the distance between the corresponding inputs. When programs are probabilistic, the distance between outputs is a distance between distributions. The Kantorovich lifting provides a general way of defining a distance between distributions by lifting the distance of the underlying sample space; by choosing an appropriate distance on the base space, one can recover other usual probabilistic distances, such as the Total Variation distance. We develop a relational pre-expectation calculus to upper bound the Kantorovich distance between two executions of a probabilistic program. We illustrate our methods by proving algorithmic stability of a machine learning algorithm, convergence of a reinforcement learning algorithm, and fast mixing for card shuffling algorithms. We also consider some extensions: proving lower bounds on the Total Variation distance and convergence to the uniform distribution. Finally, we describe an asynchronous extension of our calculus to reason about pairs of program executions with different control flow.
Minimum Age of Information in the Internet of Things with Non-uniform Status Packet Sizes
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, a real-time Internet of Things (IoT) monitoring system is considered in which the IoT devices are scheduled to sample underlying physical processes and send the status updates to a common destination. In a real-world IoT, due to the possibly different dynamics of each physical process, the sizes of the status updates for different devices are often different and each status update typically requires multiple transmission slots. By taking into account such multi-time slot transmissions with non-uniform sizes of the status updates under noisy channels, the problem of joint device scheduling and status sampling is studied in order to minimize the average age of information (AoI) at the destination. This stochastic problem is formulated as an infinite horizon average cost Markov decision process (MDP). The monotonicity of the value function of the MDP is characterized and then used to show that the optimal scheduling and sampling policy is threshold-based with respect to the AoI at each device. To overcome the curse of dimensionality, a low-complexity suboptimal policy is proposed through a semi-randomized base policy and linear approximated value functions. The proposed suboptimal policy is shown to exhibit a similar structure to the optimal policy, which provides a structural base for its effective performance. A structure-aware algorithm is then developed to obtain the suboptimal policy. The analytical results are further extended to the IoT monitoring system with random status update arrivals, for which, the optimal scheduling and sampling policy is also shown to be threshold-based with the AoI at each device. Simulation results illustrate the structures of the optimal policy and show a near-optimal AoI performance resulting from the proposed suboptimal solution approach.
SIMCom: Statistical Sniffing of Inter-Module Communications for Run-time Hardware Trojan Detection
Venue: arXiv cs.CR 2020
Year: 2020

Timely detection of Hardware Trojans (HTs) has become a major challenge for secure integrated circuits. We present a run-time methodology for HT detection that employs a multi-parameter statistical traffic modeling of the communication channel in a given System-on-Chip (SoC), named as SIMCom. The main idea is to model the communication using multiple side-channel information like the Hurst exponent, the standard deviation of the injection distribution, and the hop distribution jointly to accurately identify HT-based online anomalies (that affects the communication without affecting the protocols or control signals). At design time, our methodology employs a "property specification language" to define and embed assertions in the RTL, specifying the correct communication behavior of a given SoC. At run-time, it monitors the anomalies in the communication behavior by checking the execution patterns against these assertions. For illustration, we evaluate SIMCom for three SoCs, i.e., SoC1 ( four single-core MC8051 and UART modules), SoC2 (four single-core MC8051, AES, ethernet, memctrl, BasicRSA, RS232 modules), and SoC3 (four single-core LEON3 connected with each other and AES, ethernet, memctrl, BasicRSA, RS23s modules microcontrollers). The experimental results show that with the combined analysis of multiple statistical parameters, SIMCom is able to detect all the benchmark Trojans (available on trust-hub) with less than 1% area and power overhead.