OpenRaiser/Intern-Atlas huggingface dataset:
Learning to Minimize Age of Information over an Unreliable Channel with Energy Harvesting
Venue: arXiv cs.IT 2021
Year: 2021

The time average expected age of information (AoI) is studied for status updates sent over an error-prone channel from an energy-harvesting transmitter with a finite-capacity battery. Energy cost of sensing new status updates is taken into account as well as the transmission energy cost better capturing practical systems. The optimal scheduling policy is first studied under the hybrid automatic repeat request (HARQ) protocol when the channel and energy harvesting statistics are known, and the existence of a threshold-based optimal policy is shown. For the case of unknown environments, average-cost reinforcement-learning algorithms are proposed that learn the system parameters and the status update policy in real-time. The effectiveness of the proposed methods is demonstrated through numerical results.
Relational VAE: A Continuous Latent Variable Model for Graph Structured Data
Venue: arXiv cs.CE 2021
Year: 2021

Graph Networks (GNs) enable the fusion of prior knowledge and relational reasoning with flexible function approximations. In this work, a general GN-based model is proposed which takes full advantage of the relational modeling capabilities of GNs and extends these to probabilistic modeling with Variational Bayes (VB). To that end, we combine complementary pre-existing approaches on VB for graph data and propose an approach that relies on graph-structured latent and conditioning variables. It is demonstrated that Neural Processes can also be viewed through the lens of the proposed model. We show applications on the problem of structured probability density modeling for simulated and real wind farm monitoring data, as well as on the meta-learning of simulated Gaussian Process data. We release the source code, along with the simulated datasets.
Efficient Sparse Matrix Kernels based on Adaptive Workload-Balancing and Parallel-Reduction
Venue: arXiv cs.DC 2021
Year: 2021

Sparse matrix-vector and matrix-matrix multiplication (SpMV and SpMM) are fundamental in both conventional (graph analytics, scientific computing) and emerging (sparse DNN, GNN) domains. Workload-balancing and parallel-reduction are widely-used design principles for efficient SpMV. However, prior work fails to resolve how to implement and adaptively use the two principles for SpMV/MM. To overcome this obstacle, we first complete the implementation space with optimizations by filling three missing pieces in prior work, including: (1) We show that workload-balancing and parallel-reduction can be combined through a segment-reduction algorithm implemented with SIMD-shuffle primitives. (2) We show that parallel-reduction can be implemented in SpMM through loading the dense-matrix rows with vector memory operations. (3) We show that vectorized loading of sparse rows, being a part of the benefit of parallel-reduction, can co-exist with sequential-reduction in SpMM through temporally caching sparse-matrix elements in the shared memory. In terms of adaptive use, we analyze how the benefit of two principles change with two characteristics from the input data space: the diverse sparsity pattern and dense-matrix width. We find the benefit of the two principles fades along with the increased total workload, i.e. the increased dense-matrix width. We also identify, for SpMV and SpMM, different sparse-matrix features that impact workload-balancing effectiveness. Our design consistently exceeds cuSPARSE by 1.07-1.57x on different GPUs and dense matrix width, and the kernel selection rules involve 5-12% performance loss compared with optimal choices. Our kernel is being integrated into popular graph learning frameworks to accelerate GNN training.
Arduino sensor integrated drone for weather indices: a prototype for pre-flight preparation
Venue: arXiv cs.RO 2021
Year: 2021

Commercial weather stations can effectively collect weather data for a specified area. However, their ground sensors limit the amount of data that can be logged, thus failing to collect precise meteorological data in a local area such as a micro-scale region. This happens because weather conditions at a micro-scale region can vary greatly even with small altitude changes. For now, drone operators must check the local weather conditions to ensure a safe and successful flight. This task is often a part of pre-flight preparations. Since flight conditions (and most important flight safety) are greatly affected by weather, drone operators need a more accurate localized weather map reading for the flight area. In this paper, we present the Arduino Sensor Integrated Drone (ASID) with a built-in meteorological station that logs the weather conditions in the vertical area where the drone will be deployed. ASID is an autonomous drone-based system that monitors weather conditions for pre-flight preparation. The operation of the ASID system is based on the Arduino microcontroller running automatic flight profiles to record meteorological data such as temperature, barometric pressure, humidity, etc. The Arduino microcontroller also takes photos of the horizon for an objective assessment of the visibility, the base, and the number of clouds.
A Comprehensive Survey on STP Approach to Finite Games
Venue: arXiv cs.GT 2021
Year: 2021

Nowadays the semi-tensor product (STP) approach to finite games has become a promising new direction. This paper provides a comprehensive survey on this prosperous field. After a brief introduction for STP and finite (networked) games, a description for the principle and fundamental technique of STP approach to finite games is presented. Then several problems and recent results about theory and applications of finite games via STP are presented. A brief comment about the potential use of STP to artificial intelligence is also proposed.
How can design help enhance trust calibration in public autonomous vehicles?
Venue: arXiv cs.HC 2021
Year: 2021

Trust is a multilayered concept with critical relevance when it comes to introducing new technologies. Understanding how humans will interact with complex vehicle systems and preparing for the functional, societal and psychological aspects of autonomous vehicles' entry into our cities is a pressing concern. Design tools can help calibrate the adequate and affordable level of trust needed for a safe and positive experience. This study focuses on passenger interactions capable of enhancing the system trustworthiness and data accuracy in future shared public transportation.
Affective Image Content Analysis: Two Decades Review and New Perspectives
Venue: arXiv cs.CV 2021
Year: 2021

Images can convey rich semantics and induce various emotions in viewers. Recently, with the rapid advancement of emotional intelligence and the explosive growth of visual data, extensive research efforts have been dedicated to affective image content analysis (AICA). In this survey, we will comprehensively review the development of AICA in the recent two decades, especially focusing on the state-of-the-art methods with respect to three main challenges -- the affective gap, perception subjectivity, and label noise and absence. We begin with an introduction to the key emotion representation models that have been widely employed in AICA and description of available datasets for performing evaluation with quantitative comparison of label noise and dataset bias. We then summarize and compare the representative approaches on (1) emotion feature extraction, including both handcrafted and deep features, (2) learning methods on dominant emotion recognition, personalized emotion prediction, emotion distribution learning, and learning from noisy data or few labels, and (3) AICA based applications. Finally, we discuss some challenges and promising research directions in the future, such as image content and context understanding, group emotion clustering, and viewer-image interaction.
Non-orthogonal HARQ for URLLC Design and Analysis
Venue: arXiv cs.NI 2021
Year: 2021

The fifth-generation (5G) of mobile standards is expected to provide ultra-reliability and low-latency communications (URLLC) for various applications and services, such as online gaming, wireless industrial control, augmented reality, and self driving cars. Meeting the contradictory requirements of URLLC, i.e., ultra-reliability and low-latency, is considered to be very challenging, especially in bandwidth-limited scenarios. Most communication strategies rely on hybrid automatic repeat request (HARQ) to improve reliability at the expense of increased packet latency due to the retransmission of failing packets. To guarantee high-reliability and very low latency simultaneously, we enhance HARQ retransmission mechanism to achieve reliability with guaranteed packet level latency and in-time delivery. The proposed non-orthogonal HARQ (N-HARQ) utilizes non-orthogonal sharing of time slots for conducting retransmission. The reliability and delay analysis of the proposed N-HARQ in the finite block length (FBL) regime shows very high performance gain in packet delivery delay over conventional HARQ in both additive white Gaussian noise (AWGN) and Rayleigh fading channels. We also propose an optimization framework to further enhance the performance of N-HARQ for single and multiple retransmission cases.
String Comparison on a Quantum Computer Using Hamming Distance
Venue: arXiv cs.ET 2021
Year: 2021

The Hamming distance is ubiquitous in computing. Its computation gets expensive when one needs to compare a string against many strings. Quantum computers (QCs) may speed up the comparison. In this paper, we extend an existing algorithm for computing the Hamming distance. The extension can compare strings with symbols drawn from an arbitrary-long alphabet (which the original algorithm could not). We implement our extended algorithm using the QisKit framework to be executed by a programmer without the knowledge of a QC (the code is publicly available). We then provide four pedagogical examples: two from the field of bioinformatics and two from the field of software engineering. We finish by discussing resource requirements and the time horizon of the QCs becoming practical for string comparison.
Integrated Vehicle Routing and Monte Carlo Scheduling Approach for the Home Service Assignment, Routing, and Scheduling Problem
Venue: arXiv cs.AI 2021
Year: 2021

We formulate and solve the H-SARA Problem, a Vehicle Routing and Appointment Scheduling Problem motivated by home services management. We assume that travel times, service durations, and customer cancellations are stochastic. We use a two-stage process that first generates teams and routes using a VRP Solver with optional extensions and then uses an MC Scheduler that determines expected arrival times by teams at customers. We further introduce two different models of cancellation and their associated impacts on routing and scheduling. Finally, we introduce the Route Fracture Metaheuristic that iteratively improves an H-SARA solution by replacing the worst-performing teams. We present insights into the problem and a series of numerical experiments that illustrate properties of the optimal routing, scheduling, and the impact of the Route Fracture Metaheuristic for both models of cancellation.
A Domain-Theoretic Approach to Statistical Programming Languages
Venue: arXiv cs.LO 2021
Year: 2021

We give a domain-theoretic semantics to a statistical programming language, using the plain old category of dcpos, in contrast to some more sophisticated recent proposals. Remarkably, our monad of minimal valuations is commutative, which allows for program transformations that permute the order of independent random draws, as one would expect. A similar property is not known for Jones and Plotkin' s monad of continuous valuations. Instead of working with true real numbers, we work with exact real arithmetic, providing a bridge towards possible implementations. (Implementations by themselves are not addressed here.) Rather remarkably, we show that restricting ourselves to minimal valuations does not restrict us much: all measures on the real line can be modeled by minimal valuations on the domain $\mathbf{I}\mathbb{R}_\bot$ of exact real arithmetic. We give three operational semantics for our language, and we show that they are all adequate with respect to the denotational semantics. We also explore quite a few examples in order to demonstrate that our semantics computes exactly as one would expect, and in order to debunk the myth that a semantics based on continuous maps would not be expressive enough to encode measures with non-compact support using only measures with compact support, or to encode measures via non-continuous density functions, for instance. Our examples also include some useful, non-trivial cases of distributions on higher-order objects.
Improved constructions for succinct affine automata
Venue: arXiv cs.FL 2021
Year: 2021

Affine finite automata (AfA) can be more succinct than probabilistic and quantum finite automata when recognizing some regular languages with bounded-error. In this paper, we improve previously known constructions given for the succinctness of AfAs in three ways. First, we replace some of fixed error bounds with arbitrarily small error bounds. Second, we present new constructions by using less states than the previous constructions. Third, we show that any language recognized by a nondeterministic finite automaton (NFA) is also recognized by bounded-error AfAs having one more state, and so, AfAs inherit all succinct results by NFAs. As a special case, we also show that any language recognized by a NFA is recognized by AfAs with zero error if the number of accepting path(s) for each member is exactly the same number.
Background Knowledge in Schema Matching: Strategy vs. Data
Venue: arXiv cs.DB 2021
Year: 2021

The use of external background knowledge can be beneficial for the task of matching schemas or ontologies automatically. In this paper, we exploit six general-purpose knowledge graphs as sources of background knowledge for the matching task. The background sources are evaluated by applying three different exploitation strategies. We find that explicit strategies still outperform latent ones and that the choice of the strategy has a greater impact on the final alignment than the actual background dataset on which the strategy is applied. While we could not identify a universally superior resource, BabelNet achieved consistently good results. Our best matcher configuration with BabelNet performs very competitively when compared to other matching systems even though no dataset-specific optimizations were made.
Understanding Adversarial Examples Through Deep Neural Network's Response Surface and Uncertainty Regions
Venue: arXiv cs.LG 2021
Year: 2021

Deep neural network (DNN) is a popular model implemented in many systems to handle complex tasks such as image classification, object recognition, natural language processing etc. Consequently DNN structural vulnerabilities become part of the security vulnerabilities in those systems. In this paper we study the root cause of DNN adversarial examples. We examine the DNN response surface to understand its classification boundary. Our study reveals the structural problem of DNN classification boundary that leads to the adversarial examples. Existing attack algorithms can generate from a handful to a few hundred adversarial examples given one clean image. We show there are infinitely many adversarial images given one clean sample, all within a small neighborhood of the clean sample. We then define DNN uncertainty regions and show transferability of adversarial examples is not universal. We also argue that generalization error, the large sample theoretical guarantee established for DNN, cannot adequately capture the phenomenon of adversarial examples. We need new theory to measure DNN robustness.
Agree to Disagree: Subjective Fairness in Privacy-Restricted Decentralised Conflict Resolution
Venue: arXiv cs.MA 2021
Year: 2021

Fairness is commonly seen as a property of the global outcome of a system and assumes centralisation and complete knowledge. However, in real decentralised applications, agents only have partial observation capabilities. Under limited information, agents rely on communication to divulge some of their private (and unobservable) information to others. When an agent deliberates to resolve conflicts, limited knowledge may cause its perspective of a correct outcome to differ from the actual outcome of the conflict resolution. This is subjective unfairness. To enable decentralised, fairness-aware conflict resolution under privacy constraints, we have two contributions: (1) a novel interaction approach and (2) a formalism of the relationship between privacy and fairness. Our proposed interaction approach is an architecture for privacy-aware explainable conflict resolution where agents engage in a dialogue of hypotheses and facts. To measure the privacy-fairness relationship, we define subjective and objective fairness on both the local and global scope and formalise the impact of partial observability due to privacy in these different notions of fairness. We first study our proposed architecture and the privacy-fairness relationship in the abstract, testing different argumentation strategies on a large number of randomised cultures. We empirically demonstrate the trade-off between privacy, objective fairness, and subjective fairness and show that better strategies can mitigate the effects of privacy in distributed systems. In addition to this analysis across a broad set of randomised abstract cultures, we analyse a case study for a specific scenario: we instantiate our architecture in a multi-agent simulation of prioritised rule-aware collision avoidance with limited information disclosure.
Automatic Synthesis of Experiment Designs from Probabilistic Environment Specifications
Venue: arXiv cs.PL 2021
Year: 2021

This paper presents an extension to the probabilistic programming language ProbRobScene, allowing users to automatically synthesize uniform experiment designs directly from environment specifications. We demonstrate its effectiveness on a number of environment specification snippets from tabletop manipulation, and show that our method generates reliably low-discrepancy designs.
One-class Steel Detector Using Patch GAN Discriminator for Visualising Anomalous Feature Map
Venue: arXiv cs.CV 2021
Year: 2021

For steel product manufacturing in indoor factories, steel defect detection is important for quality control. For example, a steel sheet is extremely delicate, and must be accurately inspected. However, to maintain the painted steel parts of the infrastructure around a severe outdoor environment, corrosion detection is critical for predictive maintenance. In this paper, we propose a general-purpose application for steel anomaly detection that consists of the following four components. The first, a learner, is a unit image classification network to determine whether the region of interest or background has been recognised, after dividing the original large sized image into 256 square unit images. The second, an extractor, is a discriminator feature encoder based on a pre-trained steel generator with a patch generative adversarial network discriminator(GAN). The third, an anomaly detector, is a one-class support vector machine(SVM) to predict the anomaly score using the discriminator feature. The fourth, an indicator, is an anomalous probability map used to visually explain the anomalous features. Furthermore, we demonstrated our method through the inspection of steel sheet defects with 13,774 unit images using high-speed cameras, and painted steel corrosion with 19,766 unit images based on an eye inspection of the photographs. Finally, we visualise anomalous feature maps of steel using a strip and painted steel inspection dataset
Improved Analysis of Online Balanced Clustering
Venue: arXiv cs.DS 2021
Year: 2021

In the online balanced graph repartitioning problem, one has to maintain a clustering of $n$ nodes into $\ell$ clusters, each having $k = n / \ell$ nodes. During runtime, an online algorithm is given a stream of communication requests between pairs of nodes: an inter-cluster communication costs one unit, while the intra-cluster communication is free. An algorithm can change the clustering, paying unit cost for each moved node. This natural problem admits a simple $O(\ell^2 \cdot k^2)$-competitive algorithm COMP, whose performance is far apart from the best known lower bound of $Ω(\ell \cdot k)$. One of open questions is whether the dependency on $\ell$ can be made linear; this question is of practical importance as in the typical datacenter application where virtual machines are clustered on physical servers, $\ell$ is of several orders of magnitude larger than $k$. We answer this question affirmatively, proving that a simple modification of COMP is $(\ell \cdot 2^{O(k)})$-competitive. On the technical level, we achieve our bound by translating the problem to a system of linear integer equations and using Graver bases to show the existence of a ``small'' solution.
Multi-Access Coded Caching with Demand Privacy
Venue: arXiv cs.IT 2021
Year: 2021

The demand private coded caching problem in a multi-access network with $K$ users and $K$ caches, where each user has access to $L$ neighbouring caches in a cyclic wrap-around manner, is studied. The additional constraint imposed is that one user should not get any information regarding the demands of the remaining users. A lifting construction of demand private multi-access coded caching scheme from conventional, non-private multi-access scheme is introduced. The demand-privacy for a user is ensured by placing some additional \textit{keys} in a set of caches called the \textit{private set} of that user. For a given $K$ and $L$, a technique is also devised to find the private sets of the users.
E-DSSR: Efficient Dynamic Surgical Scene Reconstruction with Transformer-based Stereoscopic Depth Perception
Venue: arXiv cs.CV 2021
Year: 2021

Reconstructing the scene of robotic surgery from the stereo endoscopic video is an important and promising topic in surgical data science, which potentially supports many applications such as surgical visual perception, robotic surgery education and intra-operative context awareness. However, current methods are mostly restricted to reconstructing static anatomy assuming no tissue deformation, tool occlusion and de-occlusion, and camera movement. However, these assumptions are not always satisfied in minimal invasive robotic surgeries. In this work, we present an efficient reconstruction pipeline for highly dynamic surgical scenes that runs at 28 fps. Specifically, we design a transformer-based stereoscopic depth perception for efficient depth estimation and a light-weight tool segmentor to handle tool occlusion. After that, a dynamic reconstruction algorithm which can estimate the tissue deformation and camera movement, and aggregate the information over time is proposed for surgical scene reconstruction. We evaluate the proposed pipeline on two datasets, the public Hamlyn Centre Endoscopic Video Dataset and our in-house DaVinci robotic surgery dataset. The results demonstrate that our method can recover the scene obstructed by the surgical tool and handle the movement of camera in realistic surgical scenarios effectively at real-time speed.