OpenRaiser/Intern-Atlas huggingface dataset:
SANST: A Self-Attentive Network for Next Point-of-Interest Recommendation
Venue: arXiv cs.IR 2020
Year: 2020

Next point-of-interest (POI) recommendation aims to offer suggestions on which POI to visit next, given a user's POI visit history. This problem has a wide application in the tourism industry, and it is gaining an increasing interest as more POI check-in data become available. The problem is often modeled as a sequential recommendation problem to take advantage of the sequential patterns of user check-ins, e.g., people tend to visit Central Park after The Metropolitan Museum of Art in New York City. Recently, self-attentive networks have been shown to be both effective and efficient in general sequential recommendation problems, e.g., to recommend products, video games, or movies. Directly adopting self-attentive networks for next POI recommendation, however, may produce sub-optimal recommendations. This is because vanilla self-attentive networks do not consider the spatial and temporal patterns of user check-ins, which are two critical features in next POI recommendation. To address this limitation, in this paper, we propose a model named SANST that incorporates spatio-temporal patterns of user check-ins into self-attentive networks. To incorporate the spatial patterns, we encode the relative positions of POIs into their embeddings before feeding the embeddings into the self-attentive network. To incorporate the temporal patterns, we discretize the time of POI check-ins and model the temporal relationship between POI check-ins by a relation-aware self-attention module. We evaluate the performance of our SANST model with three real-world datasets. The results show that SANST consistently outperforms the state-of-theart models, and the advantage in nDCG@10 is up to 13.65%.
Graph Neighborhood Attentive Pooling
Venue: arXiv cs.LG 2020
Year: 2020

Network representation learning (NRL) is a powerful technique for learning low-dimensional vector representation of high-dimensional and sparse graphs. Most studies explore the structure and metadata associated with the graph using random walks and employ an unsupervised or semi-supervised learning schemes. Learning in these methods is context-free, because only a single representation per node is learned. Recently studies have argued on the sufficiency of a single representation and proposed a context-sensitive approach that proved to be highly effective in applications such as link prediction and ranking. However, most of these methods rely on additional textual features that require RNNs or CNNs to capture high-level features or rely on a community detection algorithm to identify multiple contexts of a node. In this study, without requiring additional features nor a community detection algorithm, we propose a novel context-sensitive algorithm called GAP that learns to attend on different parts of a node's neighborhood using attentive pooling networks. We show the efficacy of GAP using three real-world datasets on link prediction and node clustering tasks and compare it against 10 popular and state-of-the-art (SOTA) baselines. GAP consistently outperforms them and achieves up to ~9% and ~20% gain over the best performing methods on link prediction and clustering tasks, respectively.
NAS-Bench-1Shot1: Benchmarking and Dissecting One-shot Neural Architecture Search
Venue: arXiv cs.LG 2020
Year: 2020

One-shot neural architecture search (NAS) has played a crucial role in making NAS methods computationally feasible in practice. Nevertheless, there is still a lack of understanding on how these weight-sharing algorithms exactly work due to the many factors controlling the dynamics of the process. In order to allow a scientific study of these components, we introduce a general framework for one-shot NAS that can be instantiated to many recently-introduced variants and introduce a general benchmarking framework that draws on the recent large-scale tabular benchmark NAS-Bench-101 for cheap anytime evaluations of one-shot NAS methods. To showcase the framework, we compare several state-of-the-art one-shot NAS methods, examine how sensitive they are to their hyperparameters and how they can be improved by tuning their hyperparameters, and compare their performance to that of blackbox optimizers for NAS-Bench-101.
Evaluation of the Handshake Turing Test for anthropomorphic Robots
Venue: arXiv cs.RO 2020
Year: 2020

Handshakes are fundamental and common greeting and parting gestures among humans. They are important in shaping first impressions as people tend to associate character traits with a person's handshake. To widen the social acceptability of robots and make a lasting first impression, a good handshaking ability is an important skill for social robots. Therefore, to test the human-likeness of a robot handshake, we propose an initial Turing-like test, primarily for the hardware interface to future AI agents. We evaluate the test on an android robot's hand to determine if it can pass for a human hand. This is an important aspect of Turing tests for motor intelligence where humans have to interact with a physical device rather than a virtual one. We also propose some modifications to the definition of a Turing test for such scenarios taking into account that a human needs to interact with a physical medium.
MGCN: Descriptor Learning using Multiscale GCNs
Venue: arXiv cs.GR 2020
Year: 2020

We propose a novel framework for computing descriptors for characterizing points on three-dimensional surfaces. First, we present a new non-learned feature that uses graph wavelets to decompose the Dirichlet energy on a surface. We call this new feature wavelet energy decomposition signature (WEDS). Second, we propose a new multiscale graph convolutional network (MGCN) to transform a non-learned feature to a more discriminative descriptor. Our results show that the new descriptor WEDS is more discriminative than the current state-of-the-art non-learned descriptors and that the combination of WEDS and MGCN is better than the state-of-the-art learned descriptors. An important design criterion for our descriptor is the robustness to different surface discretizations including triangulations with varying numbers of vertices. Our results demonstrate that previous graph convolutional networks significantly overfit to a particular resolution or even a particular triangulation, but MGCN generalizes well to different surface discretizations. In addition, MGCN is compatible with previous descriptors and it can also be used to improve the performance of other descriptors, such as the heat kernel signature, the wave kernel signature, or the local point signature.
Real-time Out-of-distribution Detection in Learning-Enabled Cyber-Physical Systems
Venue: arXiv cs.LG 2020
Year: 2020

Cyber-physical systems (CPS) greatly benefit by using machine learning components that can handle the uncertainty and variability of the real-world. Typical components such as deep neural networks, however, introduce new types of hazards that may impact system safety. The system behavior depends on data that are available only during runtime and may be different than the data used for training. Out-of-distribution data may lead to a large error and compromise safety. The paper considers the problem of efficiently detecting out-of-distribution data in CPS control systems. Detection must be robust and limit the number of false alarms while being computational efficient for real-time monitoring. The proposed approach leverages inductive conformal prediction and anomaly detection for developing a method that has a well-calibrated false alarm rate. We use variational autoencoders and deep support vector data description to learn models that can be used efficiently compute the nonconformity of new inputs relative to the training set and enable real-time detection of out-of-distribution high-dimensional inputs. We demonstrate the method using an advanced emergency braking system and a self-driving end-to-end controller implemented in an open source simulator for self-driving cars. The simulation results show very small number of false positives and detection delay while the execution time is comparable to the execution time of the original machine learning components.
Peeling Close to the Orientability Threshold: Spatial Coupling in Hashing-Based Data Structures
Venue: arXiv cs.DS 2020
Year: 2020

In multiple-choice data structures each element $x$ in a set $S$ of $m$ keys is associated with a random set $e(x) \subseteq [n]$ of buckets with capacity $\ell \geq 1$ by hash functions. This setting is captured by the hypergraph $H = ([n],\{e(x) \mid x \in S\})$. Accomodating each key in an associated bucket amounts to finding an $\ell$-orientation of $H$ assigning to each hyperedge an incident vertex such that each vertex is assigned at most $\ell$ hyperedges. If each subhypergraph of $H$ has minimum degree at most $\ell$, then an $\ell$-orientation can be found greedily and $H$ is called $\ell$-peelable. Peelability has a central role in invertible Bloom lookup tables and can speed up the construction of retrieval data structures, perfect hash functions and cuckoo hash tables. Many hypergraphs exhibit sharp density thresholds with respect to $\ell$-orientability and $\ell$-peelability, i.e. as the density $c = \frac{m}{n}$ grows past a critical value, the probability of these properties drops from almost $1$ to almost $0$. In fully random $k$-uniform hypergraphs the thresholds $c_{k,\ell}^*$ for $\ell$-orientability significantly exceed the thresholds for $\ell$-peelability. In this paper, for every $k \geq 2$ and $\ell \geq 1$ with $(k,\ell) \neq (2,1)$ and every $z > 0$, we construct a new family of random $k$-uniform hypergraphs with i.i.d. random hyperedges such that both the $\ell$-peelability and the $\ell$-orientability thresholds approach $c_{k,\ell}^*$ as $z \rightarrow \infty$. We exploit the phenomenon of threshold saturation via spatial coupling discovered in the context of low-density parity-check codes. Once the connection to data structures is in plain sight, a framework by Kudekar, Richardson and Urbanke (2015) does the heavy lifting in our proof.
Computing the Fréchet distance of trees and graphs of bounded tree width
Venue: arXiv cs.CG 2020
Year: 2020

We give algorithms to compute the Fréchet distance of trees and graphs with bounded tree width. Our algorithms run in $O(n^2)$ time for trees of bounded degree, and $O(n^2\sqrt{n \log n})$ time for trees of arbitrary degree. For graphs of bounded tree width we show one can compute the Fréchet distance in FPT (fixed parameter tractable) time.
Landmark2Vec: An Unsupervised Neural Network-Based Landmark Positioning Method
Venue: arXiv cs.LG 2020
Year: 2020

A Neural Network-based method for unsupervised landmarks map estimation from measurements taken from landmarks is introduced. The measurements needed for training the network are the signals observed/received from landmarks by an agent. The definition of landmarks, agent, and the measurements taken by agent from landmarks is rather broad here: landmarks can be visual objects, e.g., poles along a road, with measurements being the size of landmark in a visual sensor mounted on a vehicle (agent), or they can be radio transmitters, e.g., WiFi access points inside a building, with measurements being the Received Signal Strength (RSS) heard from them by a mobile device carried by a person (agent). The goal of the map estimation is then to find the positions of landmarks up to a scale, rotation, and shift (i.e., the topological map of the landmarks). Assuming that there are $L$ landmarks, the measurements will be $L \times 1$ vectors collected over the area. A shallow network then will be trained to learn the map without any ground truth information.
IoT Behavioral Monitoring via Network Traffic Analysis
Venue: arXiv cs.NI 2020
Year: 2020

Smart homes, enterprises, and cities are increasingly being equipped with a plethora of Internet of Things (IoT), ranging from smart-lights to security cameras. While IoT networks have the potential to benefit our lives, they create privacy and security challenges not seen with traditional IT networks. Due to the lack of visibility, operators of such smart environments are not often aware of their IoT assets, let alone whether each IoT device is functioning properly safe from cyber-attacks. This thesis is the culmination of our efforts to develop techniques to profile the network behavioral pattern of IoTs, automate IoT classification, deduce their operating context, and detect anomalous behavior indicative of cyber-attacks. We begin this thesis by surveying IoT ecosystem, while reviewing current approaches to vulnerability assessments, intrusion detection, and behavioral monitoring. For our first contribution, we collect traffic traces and characterize the network behavior of IoT devices via attributes from traffic patterns. We develop a robust machine learning-based inference engine trained with these attributes and demonstrate real-time classification of 28 IoT devices with over 99% accuracy. Our second contribution enhances the classification by reducing the cost of attribute extraction while also identifying IoT device states. Prototype implementation and evaluation demonstrate the ability of our supervised machine learning method to detect behavioral changes for five IoT devices. Our third and final contribution develops a modularized unsupervised inference engine that dynamically accommodates the addition of new IoT devices and/or updates to existing ones, without requiring system-wide retraining of the model. We demonstrate via experiments that our model can automatically detect attacks and firmware changes in ten IoT devices with over 94% accuracy.
qBSA: Logic Design of a 32-bit Block-Skewed RSFQ Arithmetic Logic Unit
Venue: arXiv cs.AR 2020
Year: 2020

Single flux quantum (SFQ) circuits are an attractive beyond-CMOS technology because they promise two orders of magnitude lower power at clock frequencies exceeding 25 GHz.However, every SFQ gate is clocked creating very deep gate-level pipelines that are difficult to keep full, particularly for sequences that include data-dependent operations. This paper proposes to increase the throughput of SFQ pipelines by re-designing the datapath to accept and operate on least-significant bits (LSBs) clock cycles earlier than more significant bits. This skewed datapath approach reduces the latency of the LSB side which can be feedback earlier for use in subsequent data-dependent operations increasing their throughput. In particular,we propose to group the bits into 4-bit blocks that are operatedon concurrently and create block-skewed datapath units for 32-bit operation. This skewed approach allows a subsequent data-dependent operation to start evaluating as soon as the first 4-bit block completes. Using this general approach, we developa block-skewed MIPS-compatible 32-bit ALU. Our gate-level Verilog design improves the throughput of 32-bit data dependent operations by 2x and 1.5x compared to previously proposed 4-bit bit-slice and 32-bit Ladner-Fischer ALUs respectively.
Investigation of Numerical Dispersion with Time Step of The FDTD Methods: Avoiding Erroneous Conclusions
Venue: arXiv cs.CE 2020
Year: 2020

It is widely thought that small time steps lead to small numerical errors in the finite-difference time-domain (FDTD) simulations. In this paper, we investigated how time steps impact on numerical dispersion of two FDTD methods including the FDTD(2,2) method and the FDTD(2,4) method. Through rigorously analytical and numerical analysis, it is found that small time steps of the FDTD methods do not always have small numerical errors. Our findings reveal that these two FDTD methods present different behaviors with respect to time steps: (1) for the FDTD(2,2) method, smaller time steps limited by the Courant-Friedrichs-Lewy (CFL) condition increase numerical dispersion and lead to larger simulation errors; (2) for the FDTD(2,4) method, as time step increases, numerical dispersion errors first decrease and then increase. Our findings are also comprehensively validated from one- to three-dimensional cases through several numerical examples including wave propagation, resonant frequencies of cavities and a practical electromagnetic compatibility (EMC) problem.
Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

We consider the problem of off-policy evaluation for reinforcement learning, where the goal is to estimate the expected reward of a target policy $π$ using offline data collected by running a logging policy $μ$. Standard importance-sampling based approaches for this problem suffer from a variance that scales exponentially with time horizon $H$, which motivates a splurge of recent interest in alternatives that break the "Curse of Horizon" (Liu et al. 2018, Xie et al. 2019). In particular, it was shown that a marginalized importance sampling (MIS) approach can be used to achieve an estimation error of order $O(H^3/ n)$ in mean square error (MSE) under an episodic Markov Decision Process model with finite states and potentially infinite actions. The MSE bound however is still a factor of $H$ away from a Cramer-Rao lower bound of order $Ω(H^2/n)$. In this paper, we prove that with a simple modification to the MIS estimator, we can asymptotically attain the Cramer-Rao lower bound, provided that the action space is finite. We also provide a general method for constructing MIS estimators with high-probability error bounds.
Software Logging for Machine Learning
Venue: arXiv cs.SE 2020
Year: 2020

System logs perform a critical function in software-intensive systems as logs record the state of the system and significant events in the system at important points in time. Unfortunately, log entries are typically created in an ad-hoc, unstructured and uncoordinated fashion, limiting their usefulness for analytics and machine learning. In this paper, we present the main challenges of contemporary approaches to generating and storing system logs data for large, complex, software-intensive systems based on an in-depth case study at a world-leading telecommunications company. Second, we present a systematic and structured approach for generating log data that does not suffer from the aforementioned challenges and is optimized for use in machine learning. Third, we provide validation of the approach based on expert interviews that confirms that the approach addresses the identified challenges and problems.
Reproducibility Challenge NeurIPS 2019 Report on "Competitive Gradient Descent"
Venue: arXiv cs.LG 2020
Year: 2020

This is a report for reproducibility challenge of NeurlIPS 2019 on the paper Competitive Gradient Descent (Schafer et al., 2019). The paper introduces a novel algorithm for the numerical computation of Nash equilibria of competitive two-player games. It avoids oscillatory and divergent behaviours seen in alternating gradient descent. The purpose of this report is to critically examine the reproducibility of the work by (Schafer et al., 2019), within the framework of the NeurIPS 2019 Reproducibility Challenge. The experiments replicated in this report confirms the results of the original study. Moreover, this project offers a Python (Pytorch based) implementation of the proposed CGD algorithm which can be found at the following public git repository: (https://github.com/GopiKishan14/Reproducibility_Challenge_NeurIPS_2019)
A Cramér-Rao Type Bound for Bayesian Risk with Bregman Loss
Venue: arXiv cs.IT 2020
Year: 2020

A general class of Bayesian lower bounds when the underlying loss function is a Bregman divergence is demonstrated. This class can be considered as an extension of the Weinstein--Weiss family of bounds for the mean squared error and relies on finding a variational characterization of Bayesian risk. The approach allows for the derivation of a version of the Cramér--Rao bound that is specific to a given Bregman divergence. The new generalization of the Cramér--Rao bound reduces to the classical one when the loss function is taken to be the Euclidean norm. The effectiveness of the new bound is evaluated in the Poisson noise setting and the Binomial noise setting.
The Tensor Brain: Semantic Decoding for Perception and Memory
Venue: arXiv cs.AI 2020
Year: 2020

We analyse perception and memory, using mathematical models for knowledge graphs and tensors, to gain insights into the corresponding functionalities of the human mind. Our discussion is based on the concept of propositional sentences consisting of \textit{subject-predicate-object} (SPO) triples for expressing elementary facts. SPO sentences are the basis for most natural languages but might also be important for explicit perception and declarative memories, as well as intra-brain communication and the ability to argue and reason. A set of SPO sentences can be described as a knowledge graph, which can be transformed into an adjacency tensor. We introduce tensor models, where concepts have dual representations as indices and associated embeddings, two constructs we believe are essential for the understanding of implicit and explicit perception and memory in the brain. We argue that a biological realization of perception and memory imposes constraints on information processing. In particular, we propose that explicit perception and declarative memories require a semantic decoder, which, in a simple realization, is based on four layers: First, a sensory memory layer, as a buffer for sensory input, second, an index layer representing concepts, third, a memoryless representation layer for the broadcasting of information ---the "blackboard", or the "canvas" of the brain--- and fourth, a working memory layer as a processing center and data buffer. We discuss the operations of the four layers and relate them to the global workspace theory. In a Bayesian brain interpretation, semantic memory defines the prior for observable triple statements. We propose that ---in evolution and during development--- semantic memory, episodic memory, and natural language evolved as emergent properties in agents' process to gain a deeper understanding of sensory information.
Physics-Guided Machine Learning for Scientific Discovery: An Application in Simulating Lake Temperature Profiles
Venue: arXiv cs.LG 2020
Year: 2020

Physics-based models of dynamical systems are often used to study engineering and environmental systems. Despite their extensive use, these models have several well-known limitations due to simplified representations of the physical processes being modeled or challenges in selecting appropriate parameters. While-state-of-the-art machine learning models can sometimes outperform physics-based models given ample amount of training data, they can produce results that are physically inconsistent. This paper proposes a physics-guided recurrent neural network model (PGRNN) that combines RNNs and physics-based models to leverage their complementary strengths and improves the modeling of physical processes. Specifically, we show that a PGRNN can improve prediction accuracy over that of physics-based models, while generating outputs consistent with physical laws. An important aspect of our PGRNN approach lies in its ability to incorporate the knowledge encoded in physics-based models. This allows training the PGRNN model using very few true observed data while also ensuring high prediction accuracy. Although we present and evaluate this methodology in the context of modeling the dynamics of temperature in lakes, it is applicable more widely to a range of scientific and engineering disciplines where physics-based (also known as mechanistic) models are used, e.g., climate science, materials science, computational chemistry, and biomedicine.