OpenRaiser/Intern-Atlas huggingface dataset:
Channel Estimation and Transmission for Intelligent Reflecting Surface Assisted THz Communications
Venue: arXiv cs.IT 2020
Year: 2020

Intelligent reflecting surface (IRS) is envisioned as a promising technology to broaden signal coverage and enhance transmission in terahertz (THz) communications. Due to the passivity of IRS, the channel measurement can not be achieved by traditional pilot manner and the subsequent cooperative transmission design remains an open problem. This paper investigates the channel estimation and transmission solutions for massive multiple input multiple output (MIMO) IRS-assisted THz system. The channel estimation is realized by beam training and the quantization error is analyzed for evaluating performance. In addition, a novel hierarchical search codebook design is proposed as a low-complexity basis of beam training. Based on above foundations, we propose a cooperative channel estimation procedure to tactfully acquire the channel knowledge. Finally, by leveraging obtained channel information, the designs of IRS and transceivers are directly provided in closed form without reconstructing the full channel matrix or additional optimization. Simulation and numerical results are presented to illustrate the minimum signal to noise ratio (SNR) required for beam training and the efficacy of the proposed transmission solutions.
Can Neural Networks Learn Symbolic Rewriting?
Venue: arXiv cs.AI 2020
Year: 2020

This work investigates if the current neural architectures are adequate for learning symbolic rewriting. Two kinds of data sets are proposed for this research -- one based on automated proofs and the other being a synthetic set of polynomial terms. The experiments with use of the current neural machine translation models are performed and its results are discussed. Ideas for extending this line of research are proposed, and its relevance is motivated.
Optical Proof of Work
Venue: arXiv cs.CR 2020
Year: 2020

Most cryptocurrencies rely on Proof-of-Work (PoW) "mining" for resistance to Sybil and double-spending attacks, as well as a mechanism for currency issuance. Hashcash PoW has successfully secured the Bitcoin network since its inception, however, as the network has expanded to take on additional value storage and transaction volume, Bitcoin PoW's heavy reliance on electricity has created scalability issues, environmental concerns, and systemic risks. Mining efforts have concentrated in areas with low electricity costs, creating single points of failure. Although PoW security properties rely on imposing a trivially verifiable economic cost on miners, there is no fundamental reason for it to consist primarily of electricity cost. The authors propose a novel PoW algorithm, Optical Proof of Work (oPoW), to eliminate energy as the primary cost of mining. Proposed algorithm imposes economic difficulty on the miners, however, the cost is concentrated in hardware (capital expense-CAPEX) rather than electricity (operating expenses-OPEX). The oPoW scheme involves minimal modifications to Hashcash-like PoW schemes, inheriting safety/security properties from such schemes. Rapid growth and improvement in silicon photonics over the last two decades has led to the commercialization of silicon photonic co-processors (integrated circuits that use photons instead of electrons to perform specialized computing tasks) for low-energy deep learning. oPoW is optimized for this technology such that miners are incentivized to use specialized, energy-efficient photonics for computation. Beyond providing energy savings, oPoW has the potential to improve network scalability, enable decentralized mining outside of low electricity cost areas, and democratize issuance. Due to the CAPEX dominance of mining costs, oPoW hashrate will be significantly less sensitive to underlying coin price declines.
Learning Non-Parametric Invariances from Data with Permanent Random Connectomes
Venue: arXiv cs.LG 2020
Year: 2020

One of the fundamental problems in supervised classification and in machine learning in general, is the modelling of non-parametric invariances that exist in data. Most prior art has focused on enforcing priors in the form of invariances to parametric nuisance transformations that are expected to be present in data. Learning non-parametric invariances directly from data remains an important open problem. In this paper, we introduce a new architectural layer for convolutional networks which is capable of learning general invariances from data itself. This layer can learn invariance to non-parametric transformations and interestingly, motivates and incorporates permanent random connectomes, thereby being called Permanent Random Connectome Non-Parametric Transformation Networks (PRC-NPTN). PRC-NPTN networks are initialized with random connections (not just weights) which are a small subset of the connections in a fully connected convolution layer. Importantly, these connections in PRC-NPTNs once initialized remain permanent throughout training and testing. Permanent random connectomes make these architectures loosely more biologically plausible than many other mainstream network architectures which require highly ordered structures. We motivate randomly initialized connections as a simple method to learn invariance from data itself while invoking invariance towards multiple nuisance transformations simultaneously. We find that these randomly initialized permanent connections have positive effects on generalization, outperform much larger ConvNet baselines and the recently proposed Non-Parametric Transformation Network (NPTN) on benchmarks that enforce learning invariances from the data itself.
Decidable Inductive Invariants for Verification of Cryptographic Protocols with Unbounded Sessions
Venue: arXiv cs.LO 2020
Year: 2020

We develop a theory of decidable inductive invariants for an infinite-state variant of the Applied pi-calculus, with applications to automatic verification of stateful cryptographic protocols with unbounded sessions/nonces. Since the problem is undecidable in general, we introduce depth-bounded protocols, a strict generalisation of a class from the literature, for which our decidable analysis is sound and complete. Our core contribution is a procedure to check that an invariant is inductive, which implies that every reachable configuration satisfies it. Our invariants can capture security properties like secrecy, can be inferred automatically, and represent an independently checkable certificate of correctness. We provide a prototype implementation and we report on its performance on some textbook examples.
Correlated Feature Selection for Tweet Spam Classification
Venue: arXiv cs.SI 2020
Year: 2020

The identification of spam messages on social networks is a very challenging task. Social media sites like Twitter \& Facebook attracts a lot of users and companies to advertise and attract users of personal gains. These advertisements most of the time leads to spamming, which in return leads to poor user experience. The purpose of this paper is to undertake the analysis of spamming on Twitter. To classify spams efficiently, it is necessary to first understand the features of the spam tweets as well as identify attributes of the spammer. We extract both tweet based features and user-based features for our analysis and observe the correlation between these features. This step is necessary as we can reduce the training time if we combine the highly correlated features. Our proposed approach uses a classification model based on artificial neural networks to classify the tweets as spam or non-spam giving the highest accuracy of 97.57\% when compared with four other standard classifiers namely, SVM, K Nearest Neighbours, Naive Bayes, and Random Forest.
All-Spin Bayesian Neural Networks
Venue: arXiv cs.ET 2020
Year: 2020

Probabilistic machine learning enabled by the Bayesian formulation has recently gained significant attention in the domain of automated reasoning and decision-making. While impressive strides have been made recently to scale up the performance of deep Bayesian neural networks, they have been primarily standalone software efforts without any regard to the underlying hardware implementation. In this paper, we propose an "All-Spin" Bayesian Neural Network where the underlying spintronic hardware provides a better match to the Bayesian computing models. To the best of our knowledge, this is the first exploration of a Bayesian neural hardware accelerator enabled by emerging post-CMOS technologies. We develop an experimentally calibrated device-circuit-algorithm co-simulation framework and demonstrate $24\times$ reduction in energy consumption against an iso-network CMOS baseline implementation.
Programmable View Update Strategies on Relations
Venue: arXiv cs.DB 2020
Year: 2020

View update is an important mechanism that allows updates on a view by translating them into the corresponding updates on the base relations. The existing literature has shown the ambiguity of translating view updates. To address this ambiguity, we propose a robust language-based approach for making view update strategies programmable and validatable. Specifically, we introduce a novel approach to use Datalog to describe these update strategies. We propose a validation algorithm to check the well-behavedness of the written Datalog programs. We present a fragment of the Datalog language for which our validation is both sound and complete. This fragment not only has good properties in theory but is also useful for solving practical view updates. Furthermore, we develop an algorithm for optimizing user-written programs to efficiently implement updatable views in relational database management systems. We have implemented our proposed approach. The experimental results show that our framework is feasible and efficient in practice.
Multi-domain Dialogue State Tracking as Dynamic Knowledge Graph Enhanced Question Answering
Venue: arXiv cs.CL 2020
Year: 2020

Multi-domain dialogue state tracking (DST) is a critical component for conversational AI systems. The domain ontology (i.e., specification of domains, slots, and values) of a conversational AI system is generally incomplete, making the capability for DST models to generalize to new slots, values, and domains during inference imperative. In this paper, we propose to model multi-domain DST as a question answering problem, referred to as Dialogue State Tracking via Question Answering (DSTQA). Within DSTQA, each turn generates a question asking for the value of a (domain, slot) pair, thus making it naturally extensible to unseen domains, slots, and values. Additionally, we use a dynamically-evolving knowledge graph to explicitly learn relationships between (domain, slot) pairs. Our model has a 5.80% and 12.21% relative improvement over the current state-of-the-art model on MultiWOZ 2.0 and MultiWOZ 2.1 datasets, respectively. Additionally, our model consistently outperforms the state-of-the-art model in domain adaptation settings. (Code is released at https://github.com/alexa/dstqa )
Beyond Textual Data: Predicting Drug-Drug Interactions from Molecular Structure Images using Siamese Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Predicting and discovering drug-drug interactions (DDIs) is an important problem and has been studied extensively both from medical and machine learning point of view. Almost all of the machine learning approaches have focused on text data or textual representation of the structural data of drugs. We present the first work that uses drug structure images as the input and utilizes a Siamese convolutional network architecture to predict DDIs.
Reconciling Event Structures with Modern Multiprocessors
Venue: arXiv cs.PL 2020
Year: 2020

Weakestmo is a recently proposed memory consistency model that uses event structures to resolve the infamous "out-of-thin-air" problem. Although it has been shown to have important benefits over other memory models, its established compilation schemes are suboptimal in that they add more fences than necessary. In this paper, we prove the correctness in Coq of the intended compilation schemes for Weakestmo to a range of hardware memory models (x86, POWER, ARMv7, ARMv8, RISC-V). Our proof is the first that establishes correctness of compilation of an event-structure-based model that forbids "thin-air" behaviors, as well as the first mechanized compilation proof of a weak memory model supporting sequentially consistent accesses to such a range of hardware platforms. Our compilation proof goes via the recent Intermediate Memory Model (IMM), which we suitably extend with sequentially consistent accesses.
Catch & Carry: Reusable Neural Controllers for Vision-Guided Whole-Body Tasks
Venue: arXiv cs.AI 2020
Year: 2020

We address the longstanding challenge of producing flexible, realistic humanoid character controllers that can perform diverse whole-body tasks involving object interactions. This challenge is central to a variety of fields, from graphics and animation to robotics and motor neuroscience. Our physics-based environment uses realistic actuation and first-person perception -- including touch sensors and egocentric vision -- with a view to producing active-sensing behaviors (e.g. gaze direction), transferability to real robots, and comparisons to the biology. We develop an integrated neural-network based approach consisting of a motor primitive module, human demonstrations, and an instructed reinforcement learning regime with curricula and task variations. We demonstrate the utility of our approach for several tasks, including goal-conditioned box carrying and ball catching, and we characterize its behavioral robustness. The resulting controllers can be deployed in real-time on a standard PC. See overview video, https://youtu.be/2rQAW-8gQQk .
Improving Graph Neural Network Representations of Logical Formulae with Subgraph Pooling
Venue: arXiv cs.AI 2020
Year: 2020

Recent advances in the integration of deep learning with automated theorem proving have centered around the representation of logical formulae as inputs to deep learning systems. In particular, there has been a growing interest in adapting structure-aware neural methods to work with the underlying graph representations of logical expressions. While more effective than character and token-level approaches, graph-based methods have often made representational trade-offs that limited their ability to capture key structural properties of their inputs. In this work we propose a novel approach for embedding logical formulae that is designed to overcome the representational limitations of prior approaches. Our architecture works for logics of different expressivity; e.g., first-order and higher-order logic. We evaluate our approach on two standard datasets and show that the proposed architecture achieves state-of-the-art performance on both premise selection and proof step classification.
Parametric Graph-based Separable Transforms for Video Coding
Venue: arXiv cs.MM 2020
Year: 2020

In many video coding systems, separable transforms (such as two-dimensional DCT-2) have been used to code block residual signals obtained after prediction. This paper proposes a parametric approach to build graph-based separable transforms (GBSTs) for video coding. Specifically, a GBST is derived from a pair of line graphs, whose weights are determined based on two non-negative parameters. As certain choices of those parameters correspond to the discrete sine and cosine transform types used in recent video coding standards (including DCT-2, DST-7 and DCT-8), this paper further optimizes these graph parameters to better capture residual block statistics and improve video coding efficiency. The proposed GBSTs are tested on the Versatile Video Coding (VVC) reference software, and the experimental results show that about 0.4% average coding gain is achieved over the existing set of separable transforms constructed based on DCT-2, DST-7 and DCT-8 in VVC.
Automatic Annotation of Hip Anatomy in Fluoroscopy for Robust and Efficient 2D/3D Registration
Venue: arXiv cs.CV 2020
Year: 2020

Fluoroscopy is the standard imaging modality used to guide hip surgery and is therefore a natural sensor for computer-assisted navigation. In order to efficiently solve the complex registration problems presented during navigation, human-assisted annotations of the intraoperative image are typically required. This manual initialization interferes with the surgical workflow and diminishes any advantages gained from navigation. We propose a method for fully automatic registration using annotations produced by a neural network. Neural networks are trained to simultaneously segment anatomy and identify landmarks in fluoroscopy. Training data is obtained using an intraoperatively incompatible 2D/3D registration of hip anatomy. Ground truth 2D labels are established using projected 3D annotations. Intraoperative registration couples an intensity-based strategy with annotations inferred by the network and requires no human assistance. Ground truth labels were obtained in 366 fluoroscopic images across 6 cadaveric specimens. In a leave-one-subject-out experiment, networks obtained mean dice coefficients for left and right hemipelves, left and right femurs of 0.86, 0.87, 0.90, and 0.84. The mean 2D landmark error was 5.0 mm. The pelvis was registered within 1 degree for 86% of the images when using the proposed intraoperative approach with an average runtime of 7 seconds. In comparison, an intensity-only approach without manual initialization, registered the pelvis to 1 degree in 18% of images. We have created the first accurately annotated, non-synthetic, dataset of hip fluoroscopy. By using these annotations as training data for neural networks, state of the art performance in fluoroscopic segmentation and landmark localization was achieved. Integrating these annotations allows for a robust, fully automatic, and efficient intraoperative registration during fluoroscopic navigation of the hip.
Graph-Revised Convolutional Network
Venue: arXiv cs.LG 2020
Year: 2020

Graph Convolutional Networks (GCNs) have received increasing attention in the machine learning community for effectively leveraging both the content features of nodes and the linkage patterns across graphs in various applications. As real-world graphs are often incomplete and noisy, treating them as ground-truth information, which is a common practice in most GCNs, unavoidably leads to sub-optimal solutions. Existing efforts for addressing this problem either involve an over-parameterized model which is difficult to scale, or simply re-weight observed edges without dealing with the missing-edge issue. This paper proposes a novel framework called Graph-Revised Convolutional Network (GRCN), which avoids both extremes. Specifically, a GCN-based graph revision module is introduced for predicting missing edges and revising edge weights w.r.t. downstream tasks via joint optimization. A theoretical analysis reveals the connection between GRCN and previous work on multigraph belief propagation. Experiments on six benchmark datasets show that GRCN consistently outperforms strong baseline methods by a large margin, especially when the original graphs are severely incomplete or the labeled instances for model training are highly sparse.
Working Memory Graphs
Venue: arXiv cs.LG 2020
Year: 2020

Transformers have increasingly outperformed gated RNNs in obtaining new state-of-the-art results on supervised tasks involving text sequences. Inspired by this trend, we study the question of how Transformer-based models can improve the performance of sequential decision-making agents. We present the Working Memory Graph (WMG), an agent that employs multi-head self-attention to reason over a dynamic set of vectors representing observed and recurrent state. We evaluate WMG in three environments featuring factored observation spaces: a Pathfinding environment that requires complex reasoning over past observations, BabyAI gridworld levels that involve variable goals, and Sokoban which emphasizes future planning. We find that the combination of WMG's Transformer-based architecture with factored observation spaces leads to significant gains in learning efficiency compared to baseline architectures across all tasks. WMG demonstrates how Transformer-based models can dramatically boost sample efficiency in RL environments for which observations can be factored.
Learning Query Inseparable ELH Ontologies
Venue: arXiv cs.AI 2020
Year: 2020

We investigate the complexity of learning query inseparable ELH ontologies in a variant of Angluin's exact learning model. Given a fixed data instance A* and a query language Q, we are interested in computing an ontology H that entails the same queries as a target ontology T on A*, that is, H and T are inseparable w.r.t. A* and Q. The learner is allowed to pose two kinds of questions. The first is `Does (T,A)\models q?', with A an arbitrary data instance and q and query in Q. An oracle replies this question with `yes' or `no'. In the second, the learner asks `Are H and T inseparable w.r.t. A* and Q?'. If so, the learning process finishes, otherwise, the learner receives (A*,q) with q in Q, (T,A*)\models q and (H,A*)\not\models q (or vice-versa). Then, we analyse conditions in which query inseparability is preserved if A* changes. Finally, we consider the PAC learning model and a setting where the algorithms learn from a batch of classified data, limiting interactions with the oracles.
Finding the Exact Distribution of (Peak) Age of Information for Queues of PH/PH/1/1 and M/PH/1/2 Type
Venue: arXiv cs.IT 2020
Year: 2020

Bufferless and single-buffer queueing systems have recently been shown to be effective in coping with escalated Age of Information (AoI) figures arising in single-source status update systems with large buffers and FCFS scheduling. In this paper, for the single-source scenario, we propose a numerical algorithm for obtaining the exact distributions of both the AoI and the peak AoI (PAoI) in (i) the bufferless $PH/PH/1/1/P(p)$ queue with probabilistic preemption with preemption probability $p$, $0 \leq p \leq 1,$ and (ii) the single buffer $M/PH/1/2/R(r)$ queue with probabilistic replacement of the packet in the queue by the new arrival with replacement probability $r$, $0 \leq r \leq 1$. The proposed exact models are based on the well-established theory of Markov Fluid Queues (MFQ) and the numerical algorithms are matrix-analytical and they rely on numerically stable and efficient vector-matrix operations. Moreover, the obtained exact distributions are in matrix exponential form, making it amenable to calculate the tail probabilities and the associated moments straightforwardly. Firstly, we validate the accuracy of the proposed method with simulations, and for sume sub-cases, with existing closed-form results. We then comparatively study the AoI performance of the queueing systems of interest under varying traffic parameters.