OpenRaiser/Intern-Atlas huggingface dataset:
Bit-Slicing the Hilbert Space: Scaling Up Accurate Quantum Circuit Simulation to a New Level
Venue: arXiv cs.ET 2020
Year: 2020

Quantum computing is greatly advanced in recent years and is expected to transform the computation paradigm in the near future. Quantum circuit simulation plays a key role in the toolchain for the development of quantum hardware and software systems. However, due to the enormous Hilbert space of quantum states, simulating quantum circuits with classical computers is extremely challenging despite notable efforts have been made. In this paper, we enhance quantum circuit simulation in two dimensions: accuracy and scalability. The former is achieved by using an algebraic representation of complex numbers; the latter is achieved by bit-slicing the number representation and replacing matrix-vector multiplication with symbolic Boolean function manipulation. Experimental results demonstrate that our method can be superior to the state-of-the-art for various quantum circuits and can simulate certain benchmark families with up to tens of thousands of qubits.
Unsupervised Shape Normality Metric for Severity Quantification
Venue: arXiv cs.CV 2020
Year: 2020

This work describes an unsupervised method to objectively quantify the abnormality of general anatomical shapes. The severity of an anatomical deformity often serves as a determinant in the clinical management of patients. However, experiential bias and distinctive random residuals among specialist individuals bring variability in diagnosis and patient management decisions, irrespective of the objective deformity degree. Therefore, supervised methods are prone to be misled given insufficient labeling of pathological samples that inevitably preserve human bias and inconsistency. Furthermore, subjects demonstrating a specific pathology are naturally rare relative to the normal population. To avoid relying on sufficient pathological samples by fully utilizing the power of normal samples, we propose the shape normality metric (SNM), which requires learning only from normal samples and zero knowledge about the pathology. We represent shapes by landmarks automatically inferred from the data and model the normal group by a multivariate Gaussian distribution. Extensive experiments on different anatomical datasets, including skulls, femurs, scapulae, and humeri, demonstrate that SNM can provide an effective normality measurement, which can significantly detect and indicate pathology. Therefore, SNM offers promising value in a variety of clinical applications.
An Entropic Relevance Measure for Stochastic Conformance Checking in Process Mining
Venue: arXiv cs.AI 2020
Year: 2020

Given an event log as a collection of recorded real-world process traces, process mining aims to automatically construct a process model that is both simple and provides a useful explanation of the traces. Conformance checking techniques are then employed to characterize and quantify commonalities and discrepancies between the log's traces and the candidate models. Recent approaches to conformance checking acknowledge that the elements being compared are inherently stochastic - for example, some traces occur frequently and others infrequently - and seek to incorporate this knowledge in their analyses. Here we present an entropic relevance measure for stochastic conformance checking, computed as the average number of bits required to compress each of the log's traces, based on the structure and information about relative likelihoods provided by the model. The measure penalizes traces from the event log not captured by the model and traces described by the model but absent in the event log, thus addressing both precision and recall quality criteria at the same time. We further show that entropic relevance is computable in time linear in the size of the log, and provide evaluation outcomes that demonstrate the feasibility of using the new approach in industrial settings.
Additive Approximation Schemes for Load Balancing Problems
Venue: arXiv cs.DS 2020
Year: 2020

In this paper we introduce the concept of additive approximation schemes and apply it to load balancing problems. Additive approximation schemes aim to find a solution with an absolute error in the objective of at most $εh$ for some suitable parameter $h$. In the case that the parameter $h$ provides a lower bound an additive approximation scheme implies a standard multiplicative approximation scheme and can be much stronger when $h \ll$ OPT. On the other hand, when no PTAS exists (or is unlikely to exist), additive approximation schemes can provide a different notion for approximation. We consider the problem of assigning jobs to identical machines with lower and upper bounds for the loads of the machines. This setting generalizes problems like makespan minimization, the Santa Claus problem (on identical machines), and the envy-minimizing Santa Claus problem. For the last problem, in which the objective is to minimize the difference between the maximum and minimum load, the optimal objective value may be zero and hence it is NP-hard to obtain any multiplicative approximation guarantee. For this class of problems we present additive approximation schemes for $h = p_{\max}$, the maximum processing time of the jobs. Our technical contribution is two-fold. First, we introduce a new relaxation based on integrally assigning slots to machines and fractionally assigning jobs to the slots (the slot-MILP). We identify structural properties of (near-)optimal solutions of the slot-MILP, which allow us to solve it efficiently, assuming that there are $O(1)$ different lower and upper bounds on the machine loads (which is the relevant setting for the three problems mentioned above). The second technical contribution is a local-search based algorithm which rounds a solution to the slot-MILP introducing an additive error on the target load intervals of at most $ε\cdot p_{\max}$.
Toward a Deep Learning-Driven Intrusion Detection Approach for Internet of Things
Venue: arXiv cs.CR 2020
Year: 2020

Internet of Things (IoT) has brought along immense benefits to our daily lives encompassing a diverse range of application domains that we regularly interact with, ranging from healthcare automation to transport and smart environments. However, due to the limitation of constrained resources and computational capabilities, IoT networks are prone to various cyber attacks. Thus, defending the IoT network against adversarial attacks is of vital importance. In this paper, we present a novel intrusion detection approach for IoT networks through the application of a deep learning technique. We adopt a cutting-edge IoT dataset comprising IoT traces and realistic attack traffic, including denial of service, distributed denial of service, reconnaissance and information theft attacks. We utilise the header field information in individual packets as generic features to capture general network behaviours, and develop a feed-forward neural networks model with embedding layers (to encode high-dimensional categorical features) for multi-class classification. The concept of transfer learning is subsequently adopted to encode high-dimensional categorical features to build a binary classifier. Results obtained through the evaluation of the proposed approach demonstrate a high classification accuracy for both binary and multi-class classifiers.
A Robust Interactive Facial Animation Editing System
Venue: arXiv cs.GR 2020
Year: 2020

Over the past few years, the automatic generation of facial animation for virtual characters has garnered interest among the animation research and industry communities. Recent research contributions leverage machine-learning approaches to enable impressive capabilities at generating plausible facial animation from audio and/or video signals. However, these approaches do not address the problem of animation edition, meaning the need for correcting an unsatisfactory baseline animation or modifying the animation content itself. In facial animation pipelines, the process of editing an existing animation is just as important and time-consuming as producing a baseline. In this work, we propose a new learning-based approach to easily edit a facial animation from a set of intuitive control parameters. To cope with high-frequency components in facial movements and preserve a temporal coherency in the animation, we use a resolution-preserving fully convolutional neural network that maps control parameters to blendshapes coefficients sequences. We stack an additional resolution-preserving animation autoencoder after the regressor to ensure that the system outputs natural-looking animation. The proposed system is robust and can handle coarse, exaggerated edits from non-specialist users. It also retains the high-frequency motion of the facial animation.
Differentially Private Mechanisms for Count Queries
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we consider the problem of responding to a count query (or any other integer-valued queries) evaluated on a dataset containing sensitive attributes. To protect the privacy of individuals in the dataset, a standard practice is to add continuous noise to the true count. We design a differentially-private mechanism which adds integer-valued noise allowing the released output to remain integer. As a trade-off between utility and privacy, we derive privacy parameters $\eps$ and $δ$ in terms of the the probability of releasing an erroneous count under the assumption that the true count is no smaller than half the support size of the noise. We then numerically demonstrate that our mechanism provides higher privacy guarantee compared to the discrete Gaussian mechanism that is recently proposed in the literature.
RISMA: Reconfigurable Intelligent Surfaces Enabling Beamforming for IoT Massive Access
Venue: arXiv cs.IT 2020
Year: 2020

Massive access for Internet-of-Things (IoT) in beyond 5G networks represents a daunting challenge for conventional bandwidth-limited technologies. Millimeter-wave technologies (mmWave)---which provide large chunks of bandwidth at the cost of more complex wireless processors in harsher radio environments---is a promising alternative to accommodate massive IoT but its cost and power requirements are an obstacle for wide adoption in practice. In this context, meta-materials arise as a key innovation enabler to address this challenge by Re-configurable Intelligent Surfaces (RISs). In this paper we take on the challenge and study a beyond 5G scenario consisting of a multi-antenna base station (BS) serving a large set of single-antenna user equipments (UEs) with the aid of RISs to cope with non-line-of-sight paths. Specifically, we build a mathematical framework to jointly optimize the precoding strategy of the BS and the RIS parameters in order to minimize the system sum mean squared error (SMSE). This novel approach reveals convenient properties used to design two algorithms, RISMA and Lo-RISMA, which are able to either find simple and efficient solutions to our problem (the former) or accommodate practical constraints with low-resolution RISs (the latter). Numerical results show that our algorithms outperform conventional benchmarks that do not employ RIS (even with low-resolution meta-surfaces) with gains that span from 20% to 120% in sum rate performance.
Optimizing Off-Chain Payment Networks in Cryptocurrencies
Venue: arXiv cs.GT 2020
Year: 2020

Off-chain transaction channels represent one of the leading techniques to scale the transaction throughput in cryptocurrencies such as Bitcoin. They allow multiple agents to route payments through one another. So far, the topology and construction of payment networks has not been explored much. Participants are expected to minimize costs that are due to the allocation of liquidity as well as blockchain record fees. In this paper we study the optimization of maintenance costs of such networks. We present for the first time, a closed model for symmetric off-chain channels, and provide efficient algorithms for constructing minimal cost spanning-tree networks under this model. We prove that for any network demands, a simple hub topology provides a 2-approximation to the minimal maintenance cost showing that spanning trees in general are efficient. We also show an unbounded price of anarchy in a greedy game between the transactors, when each player wishes to minimize his costs by changing the network's structure. Finally, we simulate and compare the costs of payment networks with scale free demand topologies.
Analysis of Bayesian Networks via Prob-Solvable Loops
Venue: arXiv cs.AI 2020
Year: 2020

Prob-solvable loops are probabilistic programs with polynomial assignments over random variables and parametrised distributions, for which the full automation of moment-based invariant generation is decidable. In this paper we extend Prob-solvable loops with new features essential for encoding Bayesian networks (BNs). We show that various BNs, such as discrete, Gaussian, conditional linear Gaussian and dynamic BNs, can be naturally encoded as Prob-solvable loops. Thanks to these encodings, we can automatically solve several BN related problems, including exact inference, sensitivity analysis, filtering and computing the expected number of rejecting samples in sampling-based procedures. We evaluate our work on a number of BN benchmarks, using automated invariant generation within Prob-solvable loop analysis.
Feature Pyramid Transformer
Venue: arXiv cs.CV 2020
Year: 2020

Feature interactions across space and scales underpin modern visual recognition systems because they introduce beneficial visual contexts. Conventionally, spatial contexts are passively hidden in the CNN's increasing receptive fields or actively encoded by non-local convolution. Yet, the non-local spatial interactions are not across scales, and thus they fail to capture the non-local contexts of objects (or parts) residing in different scales. To this end, we propose a fully active feature interaction across both space and scales, called Feature Pyramid Transformer (FPT). It transforms any feature pyramid into another feature pyramid of the same size but with richer contexts, by using three specially designed transformers in self-level, top-down, and bottom-up interaction fashion. FPT serves as a generic visual backbone with fair computational overhead. We conduct extensive experiments in both instance-level (i.e., object detection and instance segmentation) and pixel-level segmentation tasks, using various backbones and head networks, and observe consistent improvement over all the baselines and the state-of-the-art methods.
MIX'EM: Unsupervised Image Classification using a Mixture of Embeddings
Venue: arXiv cs.CV 2020
Year: 2020

We present MIX'EM, a novel solution for unsupervised image classification. MIX'EM generates representations that by themselves are sufficient to drive a general-purpose clustering algorithm to deliver high-quality classification. This is accomplished by building a mixture of embeddings module into a contrastive visual representation learning framework in order to disentangle representations at the category level. It first generates a set of embedding and mixing coefficients from a given visual representation, and then combines them into a single embedding. We introduce three techniques to successfully train MIX'EM and avoid degenerate solutions; (i) diversify mixture components by maximizing entropy, (ii) minimize instance conditioned component entropy to enforce a clustered embedding space, and (iii) use an associative embedding loss to enforce semantic separability. By applying (i) and (ii), semantic categories emerge through the mixture coefficients, making it possible to apply (iii). Subsequently, we run K-means on the representations to acquire semantic classification. We conduct extensive experiments and analyses on STL10, CIFAR10, and CIFAR100-20 datasets, achieving state-of-the-art classification accuracy of 78\%, 82\%, and 44\%, respectively. To achieve robust and high accuracy, it is essential to use the mixture components to initialize K-means. Finally, we report competitive baselines (70\% on STL10) obtained by applying K-means to the "normalized" representations learned using the contrastive loss.
Active Deception using Factored Interactive POMDPs to Recognize Cyber Attacker's Intent
Venue: arXiv cs.MA 2020
Year: 2020

This paper presents an intelligent and adaptive agent that employs deception to recognize a cyber adversary's intent. Unlike previous approaches to cyber deception, which mainly focus on delaying or confusing the attackers, we focus on engaging with them to learn their intent. We model cyber deception as a sequential decision-making problem in a two-agent context. We introduce factored finitely nested interactive POMDPs (I-POMDPx) and use this framework to model the problem with multiple attacker types. Our approach models cyber attacks on a single honeypot host across multiple phases from the attacker's initial entry to reaching its adversarial objective. The defending I-POMDPx-based agent uses decoys to engage with the attacker at multiple phases to form increasingly accurate predictions of the attacker's behavior and intent. The use of I-POMDPs also enables us to model the adversary's mental state and investigate how deception affects their beliefs. Our experiments in both simulation and on a real host show that the I-POMDPx-based agent performs significantly better at intent recognition than commonly used deception strategies on honeypots.
A $2^{n/2}$-Time Algorithm for $\sqrt{n}$-SVP and $\sqrt{n}$-Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP
Venue: arXiv cs.DS 2020
Year: 2020

We show a $2^{n/2+o(n)}$-time algorithm that finds a (non-zero) vector in a lattice $\mathcal{L} \subset \mathbb{R}^n$ with norm at most $\tilde{O}(\sqrt{n})\cdot \min\{λ_1(\mathcal{L}), \det(\mathcal{L})^{1/n}\}$, where $λ_1(\mathcal{L})$ is the length of a shortest non-zero lattice vector and $\det(\mathcal{L})$ is the lattice determinant. Minkowski showed that $λ_1(\mathcal{L}) \leq \sqrt{n} \det(\mathcal{L})^{1/n}$ and that there exist lattices with $λ_1(\mathcal{L}) \geq Ω(\sqrt{n}) \cdot \det(\mathcal{L})^{1/n}$, so that our algorithm finds vectors that are as short as possible relative to the determinant (up to a polylogarithmic factor). The main technical contribution behind this result is new analysis of (a simpler variant of) an algorithm from arXiv:1412.7994, which was only previously known to solve less useful problems. To achieve this, we rely crucially on the ``reverse Minkowski theorem'' (conjectured by Dadush arXiv:1606.06913 and proven by arXiv:1611.05979), which can be thought of as a partial converse to the fact that $λ_1(\mathcal{L}) \leq \sqrt{n} \det(\mathcal{L})^{1/n}$. Previously, the fastest known algorithm for finding such a vector was the $2^{.802n + o(n)}$-time algorithm due to [Liu, Wang, Xu, and Zheng, 2011], which actually found a non-zero lattice vector with length $O(1) \cdot λ_1(\mathcal{L})$. Though we do not show how to find lattice vectors with this length in time $2^{n/2+o(n)}$, we do show that our algorithm suffices for the most important application of such algorithms: basis reduction. In particular, we show a modified version of Gama and Nguyen's slide-reduction algorithm [Gama and Nguyen, STOC 2008], which can be combined with the algorithm above to improve the time-length tradeoff for shortest-vector algorithms in nearly all regimes, including the regimes relevant to cryptography.
Learning to Play Cup-and-Ball with Noisy Camera Observations
Venue: arXiv cs.RO 2020
Year: 2020

Playing the cup-and-ball game is an intriguing task for robotics research since it abstracts important problem characteristics including system nonlinearity, contact forces and precise positioning as terminal goal. In this paper, we present a learning model based control strategy for the cup-and-ball game, where a Universal Robots UR5e manipulator arm learns to catch a ball in one of the cups on a Kendama. Our control problem is divided into two sub-tasks, namely $(i)$ swinging the ball up in a constrained motion, and $(ii)$ catching the free-falling ball. The swing-up trajectory is computed offline, and applied in open-loop to the arm. Subsequently, a convex optimization problem is solved online during the ball's free-fall to control the manipulator and catch the ball. The controller utilizes noisy position feedback of the ball from an Intel RealSense D435 depth camera. We propose a novel iterative framework, where data is used to learn the support of the camera noise distribution iteratively in order to update the control policy. The probability of a catch with a fixed policy is computed empirically with a user specified number of roll-outs. Our design guarantees that probability of the catch increases in the limit, as the learned support nears the true support of the camera noise distribution. High-fidelity Mujoco simulations and preliminary experimental results support our theoretical analysis.
Fast Adaptable Mobile Robot Navigation in Dynamic Environment
Venue: arXiv cs.RO 2020
Year: 2020

Autonomous navigation in dynamic environment heavily depends on the environment and its topology. Prior knowledge of the environment is not usually accurate as the environment keeps evolving in time. Since robot is continuously evaluating the environment as it proceeds, deciding the optimal way to traverse the environment to get to the goal, computationally efficient yet mathematically adaptive navigation algorithms are needed. In this paper, a navigation scheme for mobile robot, capable of dealing with time variant environment is proposed. This approach consists of a global planner (A*) and local planner (VFH) to assure an optimal and collision-free robot motion. The algorithm is tested both in simulation and experimentation in different environments that are known to result in failures in VFH and ROS navigation stack, for comparison purposes. Overall, the algorithm enables the robot to get to the goal faster and also produces a smoother path while doing so.
Massive Access in Cell-Free Massive MIMO-Based Internet of Things: Cloud Computing and Edge Computing Paradigms
Venue: arXiv cs.IT 2020
Year: 2020

This paper studies massive access in cell-free massive multi-input multi-output (MIMO) based Internet of Things and solves the challenging active user detection (AUD) and channel estimation (CE) problems. For the uplink transmission, we propose an advanced frame structure design to reduce the access latency. Moreover, by considering the cooperation of all access points (APs), we investigate two processing paradigms at the receiver for massive access: cloud computing and edge computing. For cloud computing, all APs are connected to a centralized processing unit (CPU), and the signals received at all APs are centrally processed at the CPU. While for edge computing, the central processing is offloaded to part of APs equipped with distributed processing units, so that the AUD and CE can be performed in a distributed processing strategy. Furthermore, by leveraging the structured sparsity of the channel matrix, we develop a structured sparsity-based generalized approximated message passing (SS-GAMP) algorithm for reliable joint AUD and CE, where the quantization accuracy of the processed signals is taken into account. Based on the SS-GAMP algorithm, a successive interference cancellation-based AUD and CE scheme is further developed under two paradigms for reduced access latency. Simulation results validate the superiority of the proposed approach over the state-of-the-art baseline schemes. Besides, the results reveal that the edge computing can achieve the similar massive access performance as the cloud computing, and the edge computing is capable of alleviating the burden on CPU, having a faster access response, and supporting more flexible AP cooperation.