OpenRaiser/Intern-Atlas huggingface dataset:
Polynomial Matrix Completion for Missing Data Imputation and Transductive Learning
Venue: arXiv cs.LG 2019
Year: 2019

This paper develops new methods to recover the missing entries of a high-rank or even full-rank matrix when the intrinsic dimension of the data is low compared to the ambient dimension. Specifically, we assume that the columns of a matrix are generated by polynomials acting on a low-dimensional intrinsic variable, and wish to recover the missing entries under this assumption. We show that we can identify the complete matrix of minimum intrinsic dimension by minimizing the rank of the matrix in a high dimensional feature space. We develop a new formulation of the resulting problem using the kernel trick together with a new relaxation of the rank objective, and propose an efficient optimization method. We also show how to use our methods to complete data drawn from multiple nonlinear manifolds. Comparative studies on synthetic data, subspace clustering with missing data, motion capture data recovery, and transductive learning verify the superiority of our methods over the state-of-the-art.
Small Connected Planar Graph with 1-Cop-Move Number 4
Venue: arXiv cs.DM 2019
Year: 2019

This paper describes a 720-vertex connected planar graph G such that cop1(G), denoting the minimum number of cops needed to catch the robber in the 1-cop-move game on G, is at least 4 and at most 7. Furthermore, G has a connected subgraph H such that cop1(H) is exactly 4, meaning that 4 cops are barely sufficient to catch the robber in the 1-cop-move game on H. This is a significant improvement over the graph given by Gao and Yang in 2017.
Multi-User Opportunistic Beamforming using Reconfigurable Surfaces
Venue: arXiv cs.IT 2019
Year: 2019

Multi-user (MU) diversity yields sum-rate gains by scheduling a user for transmission at times when its channel is near its peak. The only information required at the base station (BS) for scheduling is the users' signal-to-noise ratios (SNR)s. MU diversity gains are limited in environments with line-of-sight (LoS) channel components and/or spatial correlation. To remedy this, previous works have proposed opportunistic beamforming (OBF) using multiple antennas at the BS to transmit the same signal, modulated by time-varying gains, to the best user at each time slot. In this paper, we propose reconfigurable surface (RS)-assisted OBF to increase the range of channel fluctuations in a single-antenna broadcast channel (BC), where opportunistic scheduling (OS) strategy achieves the sum-rate capacity. The RS is abstracted as an array of passive reflecting elements, and is dumb in the sense that it only induces random phase shifts onto the impinging electromagnetic waves, without requiring any channel state information. We develop the sum-rate scaling laws under Rayleigh, Rician and correlated Rayleigh fading and show that RS-assisted OBF with only a single-antenna BS outperforms multi-antenna BS-assisted OBF. We also extend our results to OFDMA systems and the multi-antenna BC.
Optimal Multi-Level Interval-based Checkpointing for Exascale Stream Processing Systems
Venue: arXiv cs.DC 2019
Year: 2019

State-of-the-art stream processing platforms make use of checkpointing to support fault tolerance, where a "checkpoint tuple" flows through the topology to all operators, indicating a checkpoint and triggering a checkpoint operation. The checkpoint will enable recovering from any kind of failure, be it as localized as a process fault or as wide spread as power supply loss to an entire rack of machines. As we move towards Exascale computing, it is becoming clear that this kind of "single-level" checkpointing is too inefficient to scale. Some HPC researchers are now investigating multi-level checkpointing, where checkpoint operations at each level are tailored to specific kinds of failure to address the inefficiencies of single-level checkpointing. Multi-level checkpointing has been shown in practice to be superior, giving greater efficiency in operation over single-level checkpointing. However, to date there is no theoretical basis that provides optimal parameter settings for an interval-based coordinated multi-level checkpointing approach. This paper presents a theoretical framework for determining optimal parameter settings in an interval-based multi-level periodic checkpointing system, that is applicable to stream processing. Our approach is stochastic, where at a given checkpoint interval, a level is selected with some probability for checkpointing. We derive the optimal checkpoint interval and associated optimal checkpoint probabilities for a multi-level checkpointing system, that considers failure rates, checkpoint costs, restart costs and possible failure during restarting, at every level. We confirm our results with stochastic simulation and practical experimentation.
PixelRL: Fully Convolutional Network with Reinforcement Learning for Image Processing
Venue: arXiv cs.CV 2019
Year: 2019

This paper tackles a new problem setting: reinforcement learning with pixel-wise rewards (pixelRL) for image processing. After the introduction of the deep Q-network, deep RL has been achieving great success. However, the applications of deep reinforcement learning (RL) for image processing are still limited. Therefore, we extend deep RL to pixelRL for various image processing applications. In pixelRL, each pixel has an agent, and the agent changes the pixel value by taking an action. We also propose an effective learning method for pixelRL that significantly improves the performance by considering not only the future states of the own pixel but also those of the neighbor pixels. The proposed method can be applied to some image processing tasks that require pixel-wise manipulations, where deep RL has never been applied. Besides, it is possible to visualize what kind of operation is employed for each pixel at each iteration, which would help us understand why and how such an operation is chosen. We also believe that our technology can enhance the explainability and interpretability of the deep neural networks. In addition, because the operations executed at each pixels are visualized, we can change or modify the operations if necessary. We apply the proposed method to a variety of image processing tasks: image denoising, image restoration, local color enhancement, and saliency-driven image editing. Our experimental results demonstrate that the proposed method achieves comparable or better performance, compared with the state-of-the-art methods based on supervised learning. The source code is available on https://github.com/rfuruta/pixelRL.
Prospect Theory for Human-Centric Communications
Venue: arXiv cs.IT 2019
Year: 2019

Entering the 5G/6G era, the core concept of human-centric communications has intensified the search effort into analytical frameworks for integrating technological and non-technological domains. Among non-technological domains, human behavioral, psychological, and socio-economic contexts are widely considered as indispensable elements for characterizing user experience (UE). In this study, we introduce the prospect theory as a promising methodology for modeling UE and perceptual measurements for human-centric communications. As the founding pillar of behavioral economics, the prospect theory proposes the non-linear quantity and probability perception of human psychology, which extends to five fundamental behavioral attributes that have profound implications for diverse disciplines. By expatiating on the prospect theoretic framework, we aim to provide a guideline for developing human-centric communications and articulate a novel interdisciplinary research area for further investigation.
Misconfiguration Management of Network Security Components
Venue: arXiv cs.CR 2019
Year: 2019

Many companies and organizations use firewalls to control the access to their network infrastructure. Firewalls are network security components which provide means to filter traffic within corporate networks, as well as to police incoming and outcoming interaction with the Internet. For this purpose, it is necessary to configure firewalls with a set of filtering rules. Nevertheless, the existence of errors in a set of filtering rules is very likely to degrade the network security policy. The discovering and removal of these configuration errors is a serious and complex problem to solve. In this paper, we present a set of algorithms for such a management. Our approach is based on the analysis of relationships between the set of filtering rules. Then, a subsequent rewriting of rules will derive from an initial firewall setup -- potentially misconfigured -- to an equivalent one completely free of errors. At the same time, the algorithms will detect useless rules in the initial firewall configuration.
Optimized Tracking of Topic Evolution
Venue: arXiv cs.CL 2019
Year: 2019

Topic evolution modeling has been researched for a long time and has gained considerable interest. A state-of-the-art method has been recently using word modeling algorithms in combination with community detection mechanisms to achieve better results in a more effective way. We analyse results of this approach and discuss the two major challenges that this approach still faces. Although the topics that have resulted from the recent algorithm are good in general, they are very noisy due to many topics that are very unimportant because of their size, words, or ambiguity. Additionally, the number of words defining each topic is too large, making it difficult to analyse them in their unsorted state. In this paper, we propose approaches to tackle these challenges by adding topic filtering and network analysis metrics to define the importance of a topic. We test different combinations of these metrics to see which combination yields the best results. Furthermore, we add word filtering and ranking to each topic to identify the words with the highest novelty automatically. We evaluate our enhancement methods in two ways: human qualitative evaluation and automatic quantitative evaluation. Moreover, we created two case studies to test the quality of the clusters and words. In the quantitative evaluation, we use the pairwise mutual information score to test the coherency of topics. The quantitative evaluation also includes an analysis of execution times for each part of the program. The results of the experimental evaluations show that the two evaluation methods agree on the positive feasibility of the algorithm. We then show possible extensions in the form of usability and future improvements to the algorithm.
Semantic Similarity To Improve Question Understanding in a Virtual Patient
Venue: arXiv cs.CL 2019
Year: 2019

In medicine, a communicating virtual patient or doctor allows students to train in medical diagnosis and develop skills to conduct a medical consultation. In this paper, we describe a conversational virtual standardized patient system to allow medical students to simulate a diagnosis strategy of an abdominal surgical emergency. We exploited the semantic properties captured by distributed word representations to search for similar questions in the virtual patient dialogue system. We created two dialogue systems that were evaluated on datasets collected during tests with students. The first system based on hand-crafted rules obtains $92.29\%$ as $F1$-score on the studied clinical case while the second system that combines rules and semantic similarity achieves $94.88\%$. It represents an error reduction of $9.70\%$ as compared to the rules-only-based system.
Scale-dependent Relationships in Natural Language
Venue: arXiv cs.CL 2019
Year: 2019

Natural language exhibits statistical dependencies at a wide range of scales. For instance, the mutual information between words in natural language decays like a power law with the temporal lag between them. However, many statistical learning models applied to language impose a sampling scale while extracting statistical structure. For instance, Word2Vec constructs a vector embedding that maximizes the prediction between a target word and the context words that appear nearby in the corpus. The size of the context is chosen by the user and defines a strong scale; relationships over much larger temporal scales would be invisible to the algorithm. This paper examines the family of Word2Vec embeddings generated while systematically manipulating the sampling scale used to define the context around each word. The primary result is that different linguistic relationships are preferentially encoded at different scales. Different scales emphasize different syntactic and semantic relations between words.Moreover, the neighborhoods of a given word in the embeddings change significantly depending on the scale. These results suggest that any individual scale can only identify a subset of the meaningful relationships a word might have, and point toward the importance of developing scale-free models of semantic meaning.
Spatial-Temporal Self-Attention Network for Flow Prediction
Venue: arXiv cs.LG 2019
Year: 2019

Flow prediction (e.g., crowd flow, traffic flow) with features of spatial-temporal is increasingly investigated in AI research field. It is very challenging due to the complicated spatial dependencies between different locations and dynamic temporal dependencies among different time intervals. Although measurements of both dependencies are employed, existing methods suffer from the following two problems. First, the temporal dependencies are measured either uniformly or bias against long-term dependencies, which overlooks the distinctive impacts of short-term and long-term temporal dependencies. Second, the existing methods capture spatial and temporal dependencies independently, which wrongly assumes that the correlations between these dependencies are weak and ignores the complicated mutual influences between them. To address these issues, we propose a Spatial-Temporal Self-Attention Network (ST-SAN). As the path-length of attending long-term dependency is shorter in the self-attention mechanism, the vanishing of long-term temporal dependencies is prevented. In addition, since our model relies solely on attention mechanisms, the spatial and temporal dependencies can be simultaneously measured. Experimental results on real-world data demonstrate that, in comparison with state-of-the-art methods, our model reduces the root mean square errors by 9% in inflow prediction and 4% in outflow prediction on Taxi-NYC data, which is very significant compared to the previous improvement.
Coordination in Adversarial Sequential Team Games via Multi-Agent Deep Reinforcement Learning
Venue: arXiv cs.AI 2019
Year: 2019

Many real-world applications involve teams of agents that have to coordinate their actions to reach a common goal against potential adversaries. This paper focuses on zero-sum games where a team of players faces an opponent, as is the case, for example, in Bridge, collusion in poker, and collusion in bidding. The possibility for the team members to communicate before gameplay---that is, coordinate their strategies ex ante---makes the use of behavioral strategies unsatisfactory. We introduce Soft Team Actor-Critic (STAC) as a solution to the team's coordination problem that does not require any prior domain knowledge. STAC allows team members to effectively exploit ex ante communication via exogenous signals that are shared among the team. STAC reaches near-optimal coordinated strategies both in perfectly observable and partially observable games, where previous deep RL algorithms fail to reach optimal coordinated behaviors.
Industrial robot ransomware: Akerbeltz
Venue: arXiv cs.CR 2019
Year: 2019

Cybersecurity lessons have not been learnt from the dawn of other technological industries. In robotics, the existing insecurity landscape needs to be addressed immediately. Several manufacturers profiting from the lack of general awareness are systematically ignoring their responsibilities by claiming their insecure (open) systems facilitate system integration, disregarding the safety, privacy and ethical consequences that their (lack of) actions have. In an attempt to raise awareness and illustrate the "insecurity by design in robotics" we have created Akerbeltz, the first known instance of industrial robot ransomware. Our malware is demonstrated using a leading brand for industrial collaborative robots, Universal Robots. We describe the rationale behind our target and discuss the general flow of the attack including the initial cyber-intrusion, lateral movement and later control phase. We urge security researchers to adopt some sort of disclosure policy that forces manufacturers to react promptly. We advocate against security by obscurity and encourage the release of similar actions once vulnerability reports fall into a dead-end. Actions are now to be taken to abide a future free of zero-days for robotics.
Incorporating Unlabeled Data into Distributionally Robust Learning
Venue: arXiv cs.LG 2019
Year: 2019

We study a robust alternative to empirical risk minimization called distributionally robust learning (DRL), in which one learns to perform against an adversary who can choose the data distribution from a specified set of distributions. We illustrate a problem with current DRL formulations, which rely on an overly broad definition of allowed distributions for the adversary, leading to learned classifiers that are unable to predict with any confidence. We propose a solution that incorporates unlabeled data into the DRL problem to further constrain the adversary. We show that this new formulation is tractable for stochastic gradient-based optimization and yields a computable guarantee on the future performance of the learned classifier, analogous to -- but tighter than -- guarantees from conventional DRL. We examine the performance of this new formulation on 14 real datasets and find that it often yields effective classifiers with nontrivial performance guarantees in situations where conventional DRL produces neither. Inspired by these results, we extend our DRL formulation to active learning with a novel, distributionally-robust version of the standard model-change heuristic. Our active learning algorithm often achieves superior learning performance to the original heuristic on real datasets.
Continuous Speech Recognition using EEG and Video
Venue: arXiv cs.LG 2019
Year: 2019

In this paper we investigate whether electroencephalography (EEG) features can be used to improve the performance of continuous visual speech recognition systems. We implemented a connectionist temporal classification (CTC) based end-to-end automatic speech recognition (ASR) model for performing recognition. Our results demonstrate that EEG features are helpful in enhancing the performance of continuous visual speech recognition systems.
PDQ & TMK + PDQF -- A Test Drive of Facebook's Perceptual Hashing Algorithms
Venue: arXiv cs.CV 2019
Year: 2019

Efficient and reliable automated detection of modified image and multimedia files has long been a challenge for law enforcement, compounded by the harm caused by repeated exposure to psychologically harmful materials. In August 2019 Facebook open-sourced their PDQ and TMK + PDQF algorithms for image and video similarity measurement, respectively. In this report, we review the algorithms' performance on detecting commonly encountered transformations on real-world case data, sourced from contemporary investigations. We also provide a reference implementation to demonstrate the potential application and integration of such algorithms within existing law enforcement systems.
SGVAE: Sequential Graph Variational Autoencoder
Venue: arXiv cs.LG 2019
Year: 2019

Generative models of graphs are well-known, but many existing models are limited in scalability and expressivity. We present a novel sequential graphical variational autoencoder operating directly on graphical representations of data. In our model, the encoding and decoding of a graph as is framed as a sequential deconstruction and construction process, respectively, enabling the the learning of a latent space. Experiments on a cycle dataset show promise, but highlight the need for a relaxation of the distribution over node permutations.
Valley-Coupled-Spintronic Non-Volatile Memories with Compute-In-Memory Support
Venue: arXiv cs.ET 2019
Year: 2019

In this work, we propose valley-coupled spin-hall memories (VSH-MRAMs) based on monolayer WSe2. The key features of the proposed memories are (a) the ability to switch magnets with perpendicular magnetic anisotropy (PMA) via VSH effect and (b) an integrated gate that can modulate the charge/spin current (IC/IS) flow. The former attribute results in high energy efficiency (compared to the Giant-Spin Hall (GSH) effect-based devices with in-plane magnetic anisotropy (IMA) magnets). The latter feature leads to a compact access transistor-less memory array design. We experimentally measure the gate controllability of the current as well as the nonlocal resistance associated with VSH effect. Based on the measured data, we develop a simulation framework (using physical equations) to propose and analyze single-ended and differential VSH effect based magnetic memories (VSH-MRAM and DVSH-MRAM, respectively). At the array level, the proposed VSH/DVSH-MRAMs achieve 50%/ 11% lower write time, 59%/ 67% lower write energy and 35%/ 41% lower read energy at iso-sense margin, compared to single ended/differential (GSH/DGSH)-MRAMs. System level evaluation in the context of general purpose processor and intermittently-powered system shows up to 3.14X and 1.98X better energy efficiency for the proposed (D)VSH-MRAMs over (D)GSH-MRAMs respectively. Further, the differential sensing of the proposed DVSH-MRAM leads to natural and simultaneous in-memory computation of bit-wise AND and NOR logic functions. Using this feature, we design a computation-in-memory (CiM) architecture that performs Boolean logic and addition (ADD) with a single array access. System analysis performed by integrating our DVSH-MRAM: CiM in the Nios II processor across various application benchmarks shows up to 2.66X total energy savings, compared to DGSH-MRAM: CiM.
$\ell_0$ Regularized Structured Sparsity Convolutional Neural Networks
Venue: arXiv cs.CV 2019
Year: 2019

Deepening and widening convolutional neural networks (CNNs) significantly increases the number of trainable weight parameters by adding more convolutional layers and feature maps per layer, respectively. By imposing inter- and intra-group sparsity onto the weights of the layers during the training process, a compressed network can be obtained with accuracy comparable to a dense one. In this paper, we propose a new variant of sparse group lasso that blends the $\ell_0$ norm onto the individual weight parameters and the $\ell_{2,1}$ norm onto the output channels of a layer. To address the non-differentiability of the $\ell_0$ norm, we apply variable splitting resulting in an algorithm that consists of executing stochastic gradient descent followed by hard thresholding for each iteration. Numerical experiments are demonstrated on LeNet-5 and wide-residual-networks for MNIST and CIFAR 10/100, respectively. They showcase the effectiveness of our proposed method in attaining superior test accuracy with network sparsification on par with the current state of the art.