OpenRaiser/Intern-Atlas huggingface dataset:
Utility-Based Graph Summarization: New and Improved
Venue: arXiv cs.DS 2020
Year: 2020

A fundamental challenge in graph mining is the ever-increasing size of datasets. Graph summarization aims to find a compact representation resulting in faster algorithms and reduced storage needs. The flip side of graph summarization is the loss of utility which diminishes its usability. The key questions we address in this paper are: (1)How to summarize a graph without any loss of utility? (2)How to summarize a graph with some loss of utility but above a user-specified threshold? (3)How to query graph summaries without graph reconstruction?} We also aim at making graph summarization available for the masses by efficiently handling web-scale graphs using only a consumer-grade machine. Previous works suffer from conceptual limitations and lack of scalability. In this work, we make three key contributions. First, we present a utility-driven graph summarization method, based on a clique and independent set decomposition, that produces significant compression with zero loss of utility. The compression provided is significantly better than state-of-the-art in lossless graph summarization, while the runtime is two orders of magnitude lower. Second, we present a highly scalable algorithm for the lossy case, which foregoes the expensive iterative process that hampers previous work. Our algorithm achieves this by combining a memory reduction technique and a novel binary-search approach. In contrast to the competition, we are able to handle web-scale graphs in a single machine without a performance impediment as the utility threshold (and size of summary) decreases. Third, we show that our graph summaries can be used as-is to answer several important classes of queries, such as triangle enumeration, Pagerank, and shortest paths. This is in contrast to other works that incrementally reconstruct the original graph for answering queries, thus incurring additional time costs.
On the Hardness of Problems Involving Negator Relationships in an Artificial Hormone System
Venue: arXiv cs.AI 2020
Year: 2020

The Artificial Hormone System (AHS) is a self-organizing middleware to allocate tasks in a distributed system. We extended it by so-called negator hormones to enable conditional task structures. However, this extension increases the computational complexity of seemingly simple decision problems in the system: In [1] and [2], we defined the problems Negator-Path and Negator-Sat and proved their NP-completeness. In this supplementary report to these papers, we show examples of Negator-Path and Negator-Sat, introduce the novel problem Negator-Stability and explain why all of these problems involving negators are hard to solve algorithmically.
FastDrain: Removing Page Victimization Overheads in NVMe Storage Stack
Venue: arXiv cs.OS 2020
Year: 2020

Host-side page victimizations can easily overflow the SSD internal buffer, which interferes I/O services of diverse user applications thereby degrading user-level experiences. To address this, we propose FastDrain, a co-design of OS kernel and flash firmware to avoid the buffer overflow, caused by page victimizations. Specifically, FastDrain can detect a triggering point where a near-future page victimization introduces an overflow of the SSD internal buffer. Our new flash firmware then speculatively scrubs the buffer space to accommodate the requests caused by the page victimization. In parallel, our new OS kernel design controls the traffic of page victimizations by considering the target device buffer status, which can further reduce the risk of buffer overflow. To secure more buffer spaces, we also design a latency-aware FTL, which dumps the dirty data only to the fast flash pages. Our evaluation results reveal that FastDrain reduces the 99th response time of user applications by 84%, compared to a conventional system.
Lio -- A Personal Robot Assistant for Human-Robot Interaction and Care Applications
Venue: arXiv cs.RO 2020
Year: 2020

Lio is a mobile robot platform with a multi-functional arm explicitly designed for human-robot interaction and personal care assistant tasks. The robot has already been deployed in several health care facilities, where it is functioning autonomously, assisting staff and patients on an everyday basis. Lio is intrinsically safe by having full coverage in soft artificial-leather material as well as having collision detection, limited speed and forces. Furthermore, the robot has a compliant motion controller. A combination of visual, audio, laser, ultrasound and mechanical sensors are used for safe navigation and environment understanding. The ROS-enabled setup allows researchers to access raw sensor data as well as have direct control of the robot. The friendly appearance of Lio has resulted in the robot being well accepted by health care staff and patients. Fully autonomous operation is made possible by a flexible decision engine, autonomous navigation and automatic recharging. Combined with time-scheduled task triggers, this allows Lio to operate throughout the day, with a battery life of up to 8 hours and recharging during idle times. A combination of powerful on-board computing units provides enough processing power to deploy artificial intelligence and deep learning-based solutions on-board the robot without the need to send any sensitive data to cloud services, guaranteeing compliance with privacy requirements. During the COVID-19 pandemic, Lio was rapidly adjusted to perform additional functionality like disinfection and remote elevated body temperature detection. It complies with ISO13482 - Safety requirements for personal care robots, meaning it can be directly tested and deployed in care facilities.
The SPPD System for Schema Guided Dialogue State Tracking Challenge
Venue: arXiv cs.CL 2020
Year: 2020

This paper introduces one of our group's work on the Dialog System Technology Challenges 8 (DSTC8), the SPPD system for Schema Guided dialogue state tracking challenge. This challenge, named as Track 4 in DSTC8, provides a brand new and challenging dataset for developing scalable multi-domain dialogue state tracking algorithms for real world dialogue systems. We propose a zero-shot dialogue state tracking system for this task. The key components of the system is a number of BERT based zero-shot NLU models that can effectively capture semantic relations between natural language descriptions of services' schemas and utterances from dialogue turns. We also propose some strategies to make the system better to exploit information from longer dialogue history and to overcome the slot carryover problem for multi-domain dialogues. The experimental results show that the proposed system achieves a significant improvement compared with the baseline system.
Quantum simulation and circuit design for solving multidimensional Poisson equations
Venue: arXiv cs.ET 2020
Year: 2020

Many methods solve Poisson equations by using grid techniques which discretize the problem in each dimension. Most of these algorithms are subject to the curse of dimensionality, so that they need exponential runtime. In the paper "Quantum algorithm and circuit design solving the Poisson equation" a quantum algorithm is shown running in polylog time to produce a quantum state representing the solution of the Poisson equation. In this paper a quantum simulation of an extended circuit design based on this algorithm is made on a classical computer. Our purpose is to test an efficient circuit design which can break the curse of dimensionality on a quantum computer. Due to the exponential rise of the Hilbert space this design is optimized on a small number of qubits. We use Microsoft's Quantum Development Kit and its simulator of an ideal quantum computer to validate the correctness of this algorithm.
CUHK at SemEval-2020 Task 4: CommonSense Explanation, Reasoning and Prediction with Multi-task Learning
Venue: arXiv cs.CL 2020
Year: 2020

This paper describes our system submitted to task 4 of SemEval 2020: Commonsense Validation and Explanation (ComVE) which consists of three sub-tasks. The task is to directly validate the given sentence whether or not it makes sense and require the model to explain it. Based on BERTarchitecture with a multi-task setting, we propose an effective and interpretable "Explain, Reason and Predict" (ERP) system to solve the three sub-tasks about commonsense: (a) Validation, (b)Reasoning, and (c) Explanation. Inspired by cognitive studies of common sense, our system first generates a reason or understanding of the sentences and then chooses which one statement makes sense, which is achieved by multi-task learning. During the post-evaluation, our system has reached 92.9% accuracy in subtask A (rank 11), 89.7% accuracy in subtask B (rank 9), andBLEU score of 12.9 in subtask C (rank 8)
Results of the seventh edition of the BioASQ Challenge
Venue: arXiv cs.CL 2020
Year: 2020

The results of the seventh edition of the BioASQ challenge are presented in this paper. The aim of the BioASQ challenge is the promotion of systems and methodologies through the organization of a challenge on the tasks of large-scale biomedical semantic indexing and question answering. In total, 30 teams with more than 100 systems participated in the challenge this year. As in previous years, the best systems were able to outperform the strong baselines. This suggests that state-of-the-art systems are continuously improving, pushing the frontier of research.
The Number of Confirmed Cases of Covid-19 by using Machine Learning: Methods and Challenges
Venue: arXiv cs.SI 2020
Year: 2020

Covid-19 is one of the biggest health challenges that the world has ever faced. Public health policy makers need the reliable prediction of the confirmed cases in future to plan medical facilities. Machine learning methods learn from the historical data and make a prediction about the event. Machine learning methods have been used to predict the number of confirmed cases of Covid-19. In this paper, we present a detailed review of these research papers. We present a taxonomy that groups them in four categories. We further present the challenges in this field. We provide suggestions to the machine learning practitioners to improve the performance of machine learning methods for the prediction of confirmed cases of Covid-19.
A Hybrid Natural Language Generation System Integrating Rules and Deep Learning Algorithms
Venue: arXiv cs.CL 2020
Year: 2020

This paper proposes an enhanced natural language generation system combining the merits of both rule-based approaches and modern deep learning algorithms, boosting its performance to the extent where the generated textual content is capable of exhibiting agile human-writing styles and the content logic of which is highly controllable. We also come up with a novel approach called HMCU to measure the performance of the natural language processing comprehensively and precisely.
FFR v1.1: Fon-French Neural Machine Translation
Venue: arXiv cs.CL 2020
Year: 2020

All over the world and especially in Africa, researchers are putting efforts into building Neural Machine Translation (NMT) systems to help tackle the language barriers in Africa, a continent of over 2000 different languages. However, the low-resourceness, diacritical, and tonal complexities of African languages are major issues being faced. The FFR project is a major step towards creating a robust translation model from Fon, a very low-resource and tonal language, to French, for research and public use. In this paper, we introduce FFR Dataset, a corpus of Fon-to-French translations, describe the diacritical encoding process, and introduce our FFR v1.1 model, trained on the dataset. The dataset and model are made publicly available at https://github.com/ bonaventuredossou/ffr-v1, to promote collaboration and reproducibility.
DSDANet: Deep Siamese Domain Adaptation Convolutional Neural Network for Cross-domain Change Detection
Venue: arXiv cs.CV 2020
Year: 2020

Change detection (CD) is one of the most vital applications in remote sensing. Recently, deep learning has achieved promising performance in the CD task. However, the deep models are task-specific and CD data set bias often exists, hence it is inevitable that deep CD models would suffer degraded performance after transferring it from original CD data set to new ones, making manually label numerous samples in the new data set unavoidable, which costs a large amount of time and human labor. How to learn a transferable CD model in the data set with enough labeled data (original domain) but can well detect changes in another data set without labeled data (target domain)? This is defined as the cross-domain change detection problem. In this paper, we propose a novel deep siamese domain adaptation convolutional neural network (DSDANet) architecture for cross-domain CD. In DSDANet, a siamese convolutional neural network first extracts spatial-spectral features from multi-temporal images. Then, through multi-kernel maximum mean discrepancy (MK-MMD), the learned feature representation is embedded into a reproducing kernel Hilbert space (RKHS), in which the distribution of two domains can be explicitly matched. By optimizing the network parameters and kernel coefficients with the source labeled data and target unlabeled data, DSDANet can learn transferrable feature representation that can bridge the discrepancy between two domains. To the best of our knowledge, it is the first time that such a domain adaptation-based deep network is proposed for CD. The theoretical analysis and experimental results demonstrate the effectiveness and potential of the proposed method.
Towards Deductive Verification of Control Algorithms for Autonomous Marine Vehicles
Venue: arXiv cs.SE 2020
Year: 2020

The use of autonomous vehicles in real-world applications is often precluded by the difficulty of providing safety guarantees for their complex controllers. The simulation-based testing of these controllers cannot deliver sufficient safety guarantees, and the use of formal verification is very challenging due to the hybrid nature of the autonomous vehicles. Our work-in-progress paper introduces a formal verification approach that addresses this challenge by integrating the numerical computation of such a system (in GNU/Octave) with its hybrid system verification by means of a proof assistant (Isabelle). To show the effectiveness of our approach, we use it to verify differential invariants of an Autonomous Marine Vehicle with a controller switching between multiple modes.
Density of States Estimation for Out-of-Distribution Detection
Venue: arXiv cs.LG 2020
Year: 2020

Perhaps surprisingly, recent studies have shown probabilistic model likelihoods have poor specificity for out-of-distribution (OOD) detection and often assign higher likelihoods to OOD data than in-distribution data. To ameliorate this issue we propose DoSE, the density of states estimator. Drawing on the statistical physics notion of ``density of states,'' the DoSE decision rule avoids direct comparison of model probabilities, and instead utilizes the ``probability of the model probability,'' or indeed the frequency of any reasonable statistic. The frequency is calculated using nonparametric density estimators (e.g., KDE and one-class SVM) which measure the typicality of various model statistics given the training data and from which we can flag test points with low typicality as anomalous. Unlike many other methods, DoSE requires neither labeled data nor OOD examples. DoSE is modular and can be trivially applied to any existing, trained model. We demonstrate DoSE's state-of-the-art performance against other unsupervised OOD detectors on previously established ``hard'' benchmarks.
Novel Randomized Placement for FPGA Based Robust ROPUF with Improved Uniqueness
Venue: arXiv cs.CR 2020
Year: 2020

The physical unclonable functions (PUF) are used to provide software as well as hardware security for the cyber-physical systems. They have been used for performing significant cryptography tasks such as generating keys, device authentication, securing against IP piracy, and to produce the root of trust as well. However, they lack in reliability metric. We present a novel approach for improving the reliability as well as the uniqueness of the field programmable gated arrays (FPGAs) based ring oscillator PUF and derive a random number, consuming very small area (< 1%) concerning look-up tables (LUTs). We use frequency profiling method for distributing frequency variations in ring oscillators (RO), spatially placed all across the FPGA floor. We are able to spot suitable locations for RO mapping, which leads to enhanced ROPUF reliability. We have evaluated the proposed methodology on Xilinx -7 series FPGAs and tested the robustness against environmental variations, e.g. temperature and supply voltage variations, simultaneously. The proposed approach achieves significant improvement (i) in uniqueness value upto 49:90%, within 0.1% of the theoretical value (ii) in the reliability value upto 99:70%, which signifies that less than 1 bit flipping has been observed on average, and (iii) in randomness, signified by passing NIST test suite. The response generated through the ROPUF passes all the applicable relevant tests of NIST uniformity statistical test suite.
Leveraging the Information Contained in Theory Presentations
Venue: arXiv cs.LO 2020
Year: 2020

A theorem prover without an extensive library is much less useful to its potential users. Algebra, the study of algebraic structures, is a core component of such libraries. Algebraic theories also are themselves structured, the study of which was started as Universal Algebra. Various constructions (homomorphism, term algebras, products, etc) and their properties are both universal and constructive. Thus they are ripe for being automated. Unfortunately, current practice still requires library builders to write these by hand. We first highlight specific redundancies in libraries of existing systems. Then we describe a framework for generating these derived concepts from theory definitions. We demonstrate the usefulness of this framework on a test library of 227 theories.
CC-Light eQASM Architecture Specification
Venue: arXiv cs.PL 2020
Year: 2020

This document is the specification of the CC-Light instantiation of executable QASM (eQASM), a quantum instruction set architecture (QISA) developed in QuTech targeting to control a seven-qubit superconducting quantum processor. This document can serve as a reference manual for low-level programmers, compiler backend developers, and microarchitecture implementers of eQASM. The design of CC-Light eQASM is under the Apache 2.0 License.
Unsupervised Pansharpening Based on Self-Attention Mechanism
Venue: arXiv cs.CV 2020
Year: 2020

Pansharpening is to fuse a multispectral image (MSI) of low-spatial-resolution (LR) but rich spectral characteristics with a panchromatic image (PAN) of high-spatial-resolution (HR) but poor spectral characteristics. Traditional methods usually inject the extracted high-frequency details from PAN into the up-sampled MSI. Recent deep learning endeavors are mostly supervised assuming the HR MSI is available, which is unrealistic especially for satellite images. Nonetheless, these methods could not fully exploit the rich spectral characteristics in the MSI. Due to the wide existence of mixed pixels in satellite images where each pixel tends to cover more than one constituent material, pansharpening at the subpixel level becomes essential. In this paper, we propose an unsupervised pansharpening (UP) method in a deep-learning framework to address the above challenges based on the self-attention mechanism (SAM), referred to as UP-SAM. The contribution of this paper is three-fold. First, the self-attention mechanism is proposed where the spatial varying detail extraction and injection functions are estimated according to the attention representations indicating spectral characteristics of the MSI with sub-pixel accuracy. Second, such attention representations are derived from mixed pixels with the proposed stacked attention network powered with a stick-breaking structure to meet the physical constraints of mixed pixel formulations. Third, the detail extraction and injection functions are spatial varying based on the attention representations, which largely improves the reconstruction accuracy. Extensive experimental results demonstrate that the proposed approach is able to reconstruct sharper MSI of different types, with more details and less spectral distortion as compared to the state-of-the-art.
Managing Consensus-Based Cooperative Task Allocation for IIoT Networks
Venue: arXiv cs.NI 2020
Year: 2020

Current IoT services include industry-oriented services, which often require objects to run more than one task. However, the exponential growth of objects in IoT poses the challenge of distributing and managing task allocation among objects. One of the main goals of task allocation is to improve the quality of information and maximize the tasks to be performed. Although there are approaches that optimize and manage the dynamics of nodes, not all consider the quality of information and the distributed allocation over the cluster service. This paper proposes the mechanism CONTASKI for task allocation in IIoT networks to distribute tasks among objects. It relies on collaborative consensus to allocate tasks and similarity capabilities to know which objects can play in accomplishing those tasks. CONTASKI was evaluated on NS-3 and achieved 100% of allocated tasks incases with 75 and 100 nodes, and, on average, more than 80% clusters performed tasks in a low response time.
A Note on the Global Convergence of Multilayer Neural Networks in the Mean Field Regime
Venue: arXiv cs.LG 2020
Year: 2020

In a recent work, we introduced a rigorous framework to describe the mean field limit of the gradient-based learning dynamics of multilayer neural networks, based on the idea of a neuronal embedding. There we also proved a global convergence guarantee for three-layer (as well as two-layer) networks using this framework. In this companion note, we point out that the insights in our previous work can be readily extended to prove a global convergence guarantee for multilayer networks of any depths. Unlike our previous three-layer global convergence guarantee that assumes i.i.d. initializations, our present result applies to a type of correlated initialization. This initialization allows to, at any finite training time, propagate a certain universal approximation property through the depth of the neural network. To achieve this effect, we introduce a bidirectional diversity condition.
A Study of Compositional Generalization in Neural Models
Venue: arXiv cs.LG 2020
Year: 2020

Compositional and relational learning is a hallmark of human intelligence, but one which presents challenges for neural models. One difficulty in the development of such models is the lack of benchmarks with clear compositional and relational task structure on which to systematically evaluate them. In this paper, we introduce an environment called ConceptWorld, which enables the generation of images from compositional and relational concepts, defined using a logical domain specific language. We use it to generate images for a variety of compositional structures: 2x2 squares, pentominoes, sequences, scenes involving these objects, and other more complex concepts. We perform experiments to test the ability of standard neural architectures to generalize on relations with compositional arguments as the compositional depth of those arguments increases and under substitution. We compare standard neural networks such as MLP, CNN and ResNet, as well as state-of-the-art relational networks including WReN and PrediNet in a multi-class image classification setting. For simple problems, all models generalize well to close concepts but struggle with longer compositional chains. For more complex tests involving substitutivity, all models struggle, even with short chains. In highlighting these difficulties and providing an environment for further experimentation, we hope to encourage the development of models which are able to generalize effectively in compositional, relational domains.