OpenRaiser/Intern-Atlas huggingface dataset:
Cascaded Channel Estimation for Large Intelligent Metasurface Assisted Massive MIMO
Venue: arXiv cs.IT 2019
Year: 2019

In this letter, we consider the problem of channel estimation for large intelligent metasurface (LIM) assisted massive multiple-input multiple-output (MIMO) systems. The main challenge of this problem is that the LIM integrated with a large number of low-cost metamaterial antennas can only passively reflect the incident signal by a certain phase shift, and does not have any signal processing capability. To deal with this, we introduce a general framework for the estimation of the transmitter-LIM and LIM-receiver cascaded channel, and propose a two-stage algorithm that includes a sparse matrix factorization stage and a matrix completion stage. Simulation results illustrate that the proposed method can achieve accurate channel estimation for LIM-assisted massive MIMO systems.
The TrieJax Architecture: Accelerating Graph Operations Through Relational Joins
Venue: arXiv cs.DB 2019
Year: 2019

Graph pattern matching (e.g., finding all cycles and cliques) has become an important component in many critical domains such as social networks, biology, and cyber-security. This development motivated research to develop faster algorithms that target graph pattern matching. In recent years, the database community has shown that mapping graph pattern matching problems to a new class of relational join algorithms provides an efficient framework for computing these problems. In this paper, we argue that this new class of relational join algorithms is highly amenable to specialized hardware acceleration thanks to two fundamental properties: improved locality and inherent concurrency. The improved locality is a result of the provably bound number of intermediate results these algorithms generate, which results in smaller working sets. In addition, their inherent concurrency can be leveraged for effective hardware acceleration and hiding memory latency. We demonstrate the hardware amenability of this new class of algorithms by introducing TrieJax, a hardware accelerator for graph pattern matching. The TrieJax design leverages the improved locality and high concurrency properties to dramatically accelerate graph pattern matching, and can be tightly integrated into existing manycore processors. We evaluate TrieJax on a set standard graph pattern matching queries and datasets. Our evaluation shows that TrieJax outperforms recently proposed hardware accelerators for graph and database processing that do not employ the new class of algorithms by 7-63x on average (up to 539x), while consuming 15-179x less energy (up to 1750x). systems that do incorporate modern relational join algorithms by 9-20x on average (up to 45x), while consuming 59-110x less energy (up to 372x).
Safety vs. Security: Attacking Avionic Systems with Humans in the Loop
Venue: arXiv cs.CR 2019
Year: 2019

Many wireless communications systems found in aircraft lack standard security mechanisms, leaving them fundamentally vulnerable to attack. With affordable software-defined radios available, a novel threat has emerged, allowing a wide range of attackers to easily interfere with wireless avionic systems. Whilst these vulnerabilities are known, concrete attacks that exploit them are still novel and not yet well understood. This is true in particular with regards to their kinetic impact on the handling of the attacked aircraft and consequently its safety. To investigate this, we invited 30 Airbus A320 type-rated pilots to fly simulator scenarios in which they were subjected to attacks on their avionics. We implement and analyse novel wireless attacks on three safety-related systems: Traffic Collision Avoidance System (TCAS), Ground Proximity Warning System (GPWS) and the Instrument Landing System (ILS). We found that all three analysed attack scenarios created significant control impact and cost of disruption through turnarounds, avoidance manoeuvres, and diversions. They further increased workload, distrust in the affected system, and in 38% of cases caused the attacked safety system to be switched off entirely. All pilots felt the scenarios were useful, with 93.3% feeling that simulator training for wireless attacks could be valuable.
Distributed Algorithms for Subgraph-Centric Graph Platforms
Venue: arXiv cs.DC 2019
Year: 2019

Graph analytics for large scale graphs has gained interest in recent years. Many graph algorithms have been designed for vertex-centric distributed graph processing frameworks to operate on large graphs with 100 M vertices and edges, using commodity clusters and Clouds. Subgraph-centric programming models have shown additional performance benefits than vertex-centric models. But direct mapping of vertex-centric and shared-memory algorithms to subgraph-centric frameworks are either not possible, or lead to inefficient algorithms. In this paper, we present three subgraph-centric distributed graph algorithms for triangle counting, clustering and minimum spanning forest, using variations of shared and vertex-centric models. These augment existing subgraph-centric algorithms that exist in literature, and allow a broader evaluation of these three classes of graph processing algorithms and platforms.
The Twin-System Approach as One Generic Solution for XAI: An Overview of ANN-CBR Twins for Explaining Deep Learning
Venue: arXiv cs.AI 2019
Year: 2019

The notion of twin systems is proposed to address the eXplainable AI (XAI) problem, where an uninterpretable black-box system is mapped to a white-box 'twin' that is more interpretable. In this short paper, we overview very recent work that advances a generic solution to the XAI problem, the so called twin system approach. The most popular twinning in the literature is that between an Artificial Neural Networks (ANN ) as a black box and Case Based Reasoning (CBR) system as a white-box, where the latter acts as an interpretable proxy for the former. We outline how recent work reviving this idea has applied it to deep learning methods. Furthermore, we detail the many fruitful directions in which this work may be taken; such as, determining the most (i) accurate feature-weighting methods to be used, (ii) appropriate deployments for explanatory cases, (iii) useful cases of explanatory value to users.
Image Captioning based on Deep Learning Methods: A Survey
Venue: arXiv cs.CV 2019
Year: 2019

Image captioning is a challenging task and attracting more and more attention in the field of Artificial Intelligence, and which can be applied to efficient image retrieval, intelligent blind guidance and human-computer interaction, etc. In this paper, we present a survey on advances in image captioning based on Deep Learning methods, including Encoder-Decoder structure, improved methods in Encoder, improved methods in Decoder, and other improvements. Furthermore, we discussed future research directions.
DARC: Differentiable ARchitecture Compression
Venue: arXiv cs.LG 2019
Year: 2019

In many learning situations, resources at inference time are significantly more constrained than resources at training time. This paper studies a general paradigm, called Differentiable ARchitecture Compression (DARC), that combines model compression and architecture search to learn models that are resource-efficient at inference time. Given a resource-intensive base architecture, DARC utilizes the training data to learn which sub-components can be replaced by cheaper alternatives. The high-level technique can be applied to any neural architecture, and we report experiments on state-of-the-art convolutional neural networks for image classification. For a WideResNet with $97.2\%$ accuracy on CIFAR-10, we improve single-sample inference speed by $2.28\times$ and memory footprint by $5.64\times$, with no accuracy loss. For a ResNet with $79.15\%$ Top1 accuracy on ImageNet, we improve batch inference speed by $1.29\times$ and memory footprint by $3.57\times$ with $1\%$ accuracy loss. We also give theoretical Rademacher complexity bounds in simplified cases, showing how DARC avoids overfitting despite over-parameterization.
Partial Redundancy Elimination using Lazy Code Motion
Venue: arXiv cs.PL 2019
Year: 2019

Partial Redundancy Elimination (PRE) is a compiler optimization that eliminates expressions that are redundant on some but not necessarily all paths through a program. In this project, we implemented a PRE optimization pass in LLVM and measured results on a variety of applications. We chose PRE because it is a powerful technique that subsumes Common Subexpression Elimination (CSE) and Loop Invariant Code Motion (LICM), and hence has the potential to greatly improve performance.
Increasing the Security of Weak Passwords: the SPARTAN Interface
Venue: arXiv cs.CR 2019
Year: 2019

Password authentication suffers from the well-known tradeoff between security and usability. Secure passwords are difficult for users to remember, and memorable passwords are often easy to guess. SPARse Two-dimensional AuthenticatioN (SPARTAN) allows users to input their textual passwords in a two-dimensional grid instead of a linear textbox. This interface enables relatively short passwords to have a higher calculated level of security due to the need for an attacker to determine both the text of the password and the location of each character in the grid. We created a SPARTAN prototype and conducted a preliminary user study to evaluate the actual usability and security of the SPARTAN interface compared to the linear password entry interface. We find that while user-created SPARTAN passwords tend to be shorter than their linear counterparts, the calculated security of user-created SPARTAN passwords is higher than that of user-created linear passwords. We also asked participants to complete a survey on the usability of the SPARTAN interface and identified some areas of improvement, while prototype interaction provided evidence of users becoming more familiar with SPARTAN over time. Finally, we performed an investigation into password-cracking tools, and assert that SPARTAN passwords require more resources to crack than their linear counterparts. These findings suggest that SPARTAN is a promising alternative to linear passwords from a security standpoint. Usability of the interface and memorability of SPARTAN passwords is an interesting research question and should be further investigated in future work.
Drone Shadow Tracking
Venue: arXiv cs.CV 2019
Year: 2019

Aerial videos taken by a drone not too far above the surface may contain the drone's shadow projected on the scene. This deteriorates the aesthetic quality of videos. With the presence of other shadows, shadow removal cannot be directly applied, and the shadow of the drone must be tracked. Tracking a drone's shadow in a video is, however, challenging. The varying size, shape, change of orientation and drone altitude pose difficulties. The shadow can also easily disappear over dark areas. However, a shadow has specific properties that can be leveraged, besides its geometric shape. In this paper, we incorporate knowledge of the shadow's physical properties, in the form of shadow detection masks, into a correlation-based tracking algorithm. We capture a test set of aerial videos taken with different settings and compare our results to those of a state-of-the-art tracking algorithm.
Patch-based 3D Human Pose Refinement
Venue: arXiv cs.CV 2019
Year: 2019

State-of-the-art 3D human pose estimation approaches typically estimate pose from the entire RGB image in a single forward run. In this paper, we develop a post-processing step to refine 3D human pose estimation from body part patches. Using local patches as input has two advantages. First, the fine details around body parts are zoomed in to high resolution for preciser 3D pose prediction. Second, it enables the part appearance to be shared between poses to benefit rare poses. In order to acquire informative representation of patches, we explore different input modalities and validate the superiority of fusing predicted segmentation with RGB. We show that our method consistently boosts the accuracy of state-of-the-art 3D human pose methods.
Safe and Chaotic Compilation for Hidden Deterministic Hardware Aliasing
Venue: arXiv cs.SE 2019
Year: 2019

Hardware aliasing occurs when the same logical address can access different physical memory locations. This is a problem for software on some embedded systems and more generally when hardware becomes faulty in irretrievable locations, such as on a Mars Lander. We show how to work around the hardware problem with software logic, compiling code so it works on any platform with hardware aliasing with hidden determinism. That is: (i) a copy of an address accesses the same location, and (ii) repeating an address calculation exactly will repeat the same access again. Stuck bits can mean that even adding zero to an address can make a difference in that environment so nothing but a systematic approach has a chance of working. The technique is extended to generate aliasing as well as compensate for it, in so-called chaotic compilation, and a sketch proof is included to show it may produce object code that is secure against discovery of the programmer's intention. A prototype compiler implementing the technology covers all of ANSI C except longjmp/setjmp.
Better Technical Debt Detection via SURVEYing
Venue: arXiv cs.SE 2019
Year: 2019

Software analytics can be improved by surveying; i.e. rechecking and (possibly) revising the labels offered by prior analysis. Surveying is a time-consuming task and effective surveyors must carefully manage their time. Specifically, they must balance the cost of further surveying against the additional benefits of that extra effort. This paper proposes SURVEY0, an incremental Logistic Regression estimation method that implements cost/benefit analysis. Some classifier is used to rank the as-yet-unvisited examples according to how interesting they might be. Humans then review the most interesting examples, after which their feedback is used to update an estimator for estimating how many examples are remaining. This paper evaluates SURVEY0 in the context of self-admitted technical debt. As software project mature, they can accumulate "technical debt" i.e. developer decisions which are sub-optimal and decrease the overall quality of the code. Such decisions are often commented on by programmers in the code; i.e. it is self-admitted technical debt (SATD). Recent results show that text classifiers can automatically detect such debt. We find that we can significantly outperform prior results by SURVEYing the data. Specifically, for ten open-source JAVA projects, we can find 83% of the technical debt via SURVEY0 using just 16% of the comments (and if higher levels of recall are required, SURVEY0can adjust towards that with some additional effort).
A Neural Network Architecture for Learning Word-Referent Associations in Multiple Contexts
Venue: arXiv cs.LG 2019
Year: 2019

This article proposes a biologically inspired neurocomputational architecture which learns associations between words and referents in different contexts, considering evidence collected from the literature of Psycholinguistics and Neurolinguistics. The multi-layered architecture takes as input raw images of objects (referents) and streams of word's phonemes (labels), builds an adequate representation, recognizes the current context, and associates label with referents incrementally, by employing a Self-Organizing Map which creates new association nodes (prototypes) as required, adjusts the existing prototypes to better represent the input stimuli and removes prototypes that become obsolete/unused. The model takes into account the current context to retrieve the correct meaning of words with multiple meanings. Simulations show that the model can reach up to 78% of word-referent association accuracy in ambiguous situations and approximates well the learning rates of humans as reported by three different authors in five Cross-Situational Word Learning experiments, also displaying similar learning patterns in the different learning conditions.
Behavior Identification and Prediction for a Probabilistic Risk Framework
Venue: arXiv cs.RO 2019
Year: 2019

Operation in a real world traffic requires autonomous vehicles to be able to plan their motion in complex environments (multiple moving participants). Planning through such environment requires the right search space to be provided for the trajectory or maneuver planners so that the safest motion for the ego vehicle can be identified. Given the current states of the environment and its participants, analyzing the risks based on the predicted trajectories of all the traffic participants provides the necessary search space for the planning of motion. This paper provides a fresh taxonomy of safety / risks that an autonomous vehicle should be able to handle while navigating through traffic. It provides a reference system architecture that needs to be implemented as well as describes a novel way of identifying and predicting the behaviors of the traffic participants using classic Multi Model Adaptive Estimation (MMAE). Preliminary simulation results of the implemented model are included.
Efficient Synthesis with Probabilistic Constraints
Venue: arXiv cs.PL 2019
Year: 2019

We consider the problem of synthesizing a program given a probabilistic specification of its desired behavior. Specifically, we study the recent paradigm of distribution-guided inductive synthesis (DIGITS), which iteratively calls a synthesizer on finite sample sets from a given distribution. We make theoretical and algorithmic contributions: (i) We prove the surprising result that DIGITS only requires a polynomial number of synthesizer calls in the size of the sample set, despite its ostensibly exponential behavior. (ii) We present a property-directed version of DIGITS that further reduces the number of synthesizer calls, drastically improving synthesis performance on a range of benchmarks.
Stopping time signatures for some algorithms in cryptography
Venue: arXiv cs.CR 2019
Year: 2019

We consider the normalized distribution of the overall running times of some cryptographic algorithms, and what information they reveal about the algorithms. Recent work of Deift, Menon, Olver, Pfrang, and Trogdon has shown that certain numerical algorithms applied to large random matrices exhibit a characteristic distribution of running times, which depends only on the algorithm but are independent of the choice of probability distributions for the matrices. Different algorithms often exhibit different running time distributions, and so the histograms for these running time distributions provide a time-signature for the algorithms, making it possible, in many cases, to distinguish one algorithm from another. In this paper we extend this analysis to cryptographic algorithms, and present examples of such algorithms with time-signatures that are indistinguishable, and others with time-signatures that are clearly distinct.
Offloading Deadline-Constrained Cellular Traffic
Venue: arXiv cs.IT 2019
Year: 2019

In this work we study the problem of hard-deadline constrained data offloading in cellular networks. A single-Base-Station (BS) single-frequency-channel downlink system is studied where users request the same packet from the BS at the beginning of each time slot. Packets have a hard deadline of one time slot. The slot is divided into two phases. Out of those users having high channel gain allowing them to decode the packet in the first phase, one is chosen to rebroadcast it to the remaining users in the second phase. This gives the remaining users a second opportunity to potentially decode this packet before the deadline passes. By this, the BS has offloaded the packet to a `local network of users' which eliminates unnecessary BS retransmissions. The problem is modeled as a rate-adaptation and scheduling optimization problem to maximize the duration of this second phase such that each user receives a certain percentage of the packets. We show that the proposed algorithm has a polynomial complexity in the number of users with optimal performance.
Personality and Behavior in Role-based Online Games
Venue: arXiv cs.HC 2019
Year: 2019

Both offline and online human behaviors are affected by personality. Of special interests are online games, where players have to impersonate specific roles and their behaviors are extensively tracked by the game. In this paper, we propose to study the relationship between players' personality and game behavior in League of Legends (LoL), one of the most popular Multiplayer Online Battle Arena (MOBA) games. We use linear mixed effects (LME) models to describe relationships between players' personality traits (measured by the Five Factor Model) and two major aspects of the game: the impersonated roles and in-game actions. On the one hand, we study relationships within the game environment by modeling role attributes from match behaviors and vice versa. On the other hand, we analyze the relationship between a player's five personality traits and their game behavior by showing significant correlations between each personality trait and the set of corresponding behaviors. Our findings suggest that personality and behavior are highly entangled and provide a new perspective to understand how personality can affect behavior in role-based online games.
A Seq-to-Seq Transformer Premised Temporal Convolutional Network for Chinese Word Segmentation
Venue: arXiv cs.CL 2019
Year: 2019

The prevalent approaches of Chinese word segmentation task almost rely on the Bi-LSTM neural network. However, the methods based the Bi-LSTM have some inherent drawbacks: hard to parallel computing, little efficient in applying the Dropout method to inhibit the Overfitting and little efficient in capturing the character information at the more distant site of a long sentence for the word segmentation task. In this work, we propose a sequence-to-sequence transformer model for Chinese word segmentation, which is premised a type of convolutional neural network named temporal convolutional network. The model uses the temporal convolutional network to construct an encoder, and uses one layer of fully-connected neural network to build a decoder, and applies the Dropout method to inhibit the Overfitting, and captures the character information at the distant site of a sentence by adding the layers of the encoder, and binds Conditional Random Fields model to train parameters, and uses the Viterbi algorithm to infer the final result of the Chinese word segmentation. The experiments on traditional Chinese corpora and simplified Chinese corpora show that the performance of Chinese word segmentation of the model is equivalent to the performance of the methods based the Bi-LSTM, and the model has a tremendous growth in parallel computing than the models based the Bi-LSTM.
Fundamental Limits of Coded Caching: The Memory Rate Pair (K-1-1/K, 1/(K-1))
Venue: arXiv cs.IT 2019
Year: 2019

Maddah-Ali and Niesen, in a seminal paper, introduced the notion of coded caching. The exact nature of the fundamental limits in this context has remained elusive even as several approximate characterizations have been found. A new optimal scheme for the (3, 3) cache network, operating at the memory rate pair (5/3, 1/2) for the demand where all the users request for distinct files, was introduced recently to partially address this issue. In this paper, an extension of this scheme to the general (K, K) cache network, operating at the memory rate pair (K-1-1/K, 1/(K-1)), is proposed. A new lower bound is also derived which demonstrates the optimality of the proposed scheme for the demand where all the users request for distinct files.