OpenRaiser/Intern-Atlas huggingface dataset:
Lower Bounds and Improved Algorithms for Asymmetric Streaming Edit Distance and Longest Common Subsequence
Venue: arXiv cs.DS 2021
Year: 2021

In this paper, we study edit distance (ED) and longest common subsequence (LCS) in the asymmetric streaming model, introduced by Saks and Seshadhri [SS13]. As an intermediate model between the random access model and the streaming model, this model allows one to have streaming access to one string and random access to the other string. Our first main contribution is a systematic study of space lower bounds for ED and LCS in the asymmetric streaming model. Previously, there are no explicitly stated results in this context, although some lower bounds about LCS can be inferred from the lower bounds for longest increasing subsequence (LIS) in [SW07][GG10][EJ08]. Yet these bounds only work for large alphabet size. In this paper, we develop several new techniques to handle ED in general and LCS for small alphabet size, thus establishing strong lower bounds for both problems. In particular, our lower bound for ED provides an exponential separation between edit distance and Hamming distance in the asymmetric streaming model. Our lower bounds also extend to LIS and longest non-decreasing sequence (LNS) in the standard streaming model. Together with previous results, our bounds provide an almost complete picture for these two problems. As our second main contribution, we give improved algorithms for ED and LCS in the asymmetric streaming model. For ED, we improve the space complexity of the constant factor approximation algorithms in [FHRS20][CJLZ20] from $\tilde{O}(\frac{n^δ}δ)$ to $O(\frac{d^δ}δ\;\mathsf{polylog}(n))$, where $n$ is the length of each string and $d$ is the edit distance between the two strings. For LCS, we give the first $1/2+ε$ approximation algorithm with space $n^δ$ for any constant $δ>0$, over a binary alphabet.
On Causal Semantics of Petri Nets
Venue: arXiv cs.LO 2021
Year: 2021

We consider approaches for causal semantics of Petri nets, explicitly representing dependencies between transition occurrences. For one-safe nets or condition/event-systems, the notion of process as defined by Carl Adam Petri provides a notion of a run of a system where causal dependencies are reflected in terms of a partial order. A well-known problem is how to generalise this notion for nets where places may carry several tokens. Goltz and Reisig have defined such a generalisation by distinguishing tokens according to their causal history. However, this so-called individual token interpretation is often considered too detailed. A number of approaches have tackled the problem of defining a more abstract notion of process, thereby obtaining a so-called collective token interpretation. Here we give a short overview on these attempts and then identify a subclass of Petri nets, called structural conflict nets, where the interplay between conflict and concurrency due to token multiplicity does not occur. For this subclass, we define abstract processes as equivalence classes of Goltz-Reisig processes. We justify this approach by showing that we obtain exactly one maximal abstract process if and only if the underlying net is conflict-free with respect to a canonical notion of conflict.
Deep Colormap Extraction from Visualizations
Venue: arXiv cs.HC 2021
Year: 2021

This work presents a new approach based on deep learning to automatically extract colormaps from visualizations. After summarizing colors in an input visualization image as a Lab color histogram, we pass the histogram to a pre-trained deep neural network, which learns to predict the colormap that produces the visualization. To train the network, we create a new dataset of 64K visualizations that cover a wide variety of data distributions, chart types, and colormaps. The network adopts an atrous spatial pyramid pooling module to capture color features at multiple scales in the input color histograms. We then classify the predicted colormap as discrete or continuous and refine the predicted colormap based on its color histogram. Quantitative comparisons to existing methods show the superior performance of our approach on both synthetic and real-world visualizations. We further demonstrate the utility of our method with two use cases,i.e., color transfer and color remapping.
Reasons, Values, Stakeholders: A Philosophical Framework for Explainable Artificial Intelligence
Venue: arXiv cs.CY 2021
Year: 2021

The societal and ethical implications of the use of opaque artificial intelligence systems for consequential decisions, such as welfare allocation and criminal justice, have generated a lively debate among multiple stakeholder groups, including computer scientists, ethicists, social scientists, policy makers, and end users. However, the lack of a common language or a multi-dimensional framework to appropriately bridge the technical, epistemic, and normative aspects of this debate prevents the discussion from being as productive as it could be. Drawing on the philosophical literature on the nature and value of explanations, this paper offers a multi-faceted framework that brings more conceptual precision to the present debate by (1) identifying the types of explanations that are most pertinent to artificial intelligence predictions, (2) recognizing the relevance and importance of social and ethical values for the evaluation of these explanations, and (3) demonstrating the importance of these explanations for incorporating a diversified approach to improving the design of truthful algorithmic ecosystems. The proposed philosophical framework thus lays the groundwork for establishing a pertinent connection between the technical and ethical aspects of artificial intelligence systems.
Polynesia: Enabling Effective Hybrid Transactional/Analytical Databases with Specialized Hardware/Software Co-Design
Venue: arXiv cs.AR 2021
Year: 2021

An exponential growth in data volume, combined with increasing demand for real-time analysis (i.e., using the most recent data), has resulted in the emergence of database systems that concurrently support transactions and data analytics. These hybrid transactional and analytical processing (HTAP) database systems can support real-time data analysis without the high costs of synchronizing across separate single-purpose databases. Unfortunately, for many applications that perform a high rate of data updates, state-of-the-art HTAP systems incur significant drops in transactional (up to 74.6%) and/or analytical (up to 49.8%) throughput compared to performing only transactions or only analytics in isolation, due to (1) data movement between the CPU and memory, (2) data update propagation, and (3) consistency costs. We propose Polynesia, a hardware-software co-designed system for in-memory HTAP databases. Polynesia (1) divides the HTAP system into transactional and analytical processing islands, (2) implements custom algorithms and hardware to reduce the costs of update propagation and consistency, and (3) exploits processing-in-memory for the analytical islands to alleviate data movement. Our evaluation shows that Polynesia outperforms three state-of-the-art HTAP systems, with average transactional/analytical throughput improvements of 1.70X/3.74X, and reduces energy consumption by 48% over the prior lowest-energy system.
Online anomaly detection using statistical leverage for streaming business process events
Venue: arXiv cs.LG 2021
Year: 2021

While several techniques for detecting trace-level anomalies in event logs in offline settings have appeared recently in the literature, such techniques are currently lacking for online settings. Event log anomaly detection in online settings can be crucial for discovering anomalies in process execution as soon as they occur and, consequently, allowing to promptly take early corrective actions. This paper describes a novel approach to event log anomaly detection on event streams that uses statistical leverage. Leverage has been used extensively in statistics to develop measures to identify outliers and it has been adapted in this paper to the specific scenario of event stream data. The proposed approach has been evaluated on both artificial and real event streams.
Self-supervised Low Light Image Enhancement and Denoising
Venue: arXiv cs.CV 2021
Year: 2021

This paper proposes a self-supervised low light image enhancement method based on deep learning, which can improve the image contrast and reduce noise at the same time to avoid the blur caused by pre-/post-denoising. The method contains two deep sub-networks, an Image Contrast Enhancement Network (ICE-Net) and a Re-Enhancement and Denoising Network (RED-Net). The ICE-Net takes the low light image as input and produces a contrast enhanced image. The RED-Net takes the result of ICE-Net and the low light image as input, and can re-enhance the low light image and denoise at the same time. Both of the networks can be trained with low light images only, which is achieved by a Maximum Entropy based Retinex (ME-Retinex) model and an assumption that noises are independently distributed. In the ME-Retinex model, a new constraint on the reflectance image is introduced that the maximum channel of the reflectance image conforms to the maximum channel of the low light image and its entropy should be the largest, which converts the decomposition of reflectance and illumination in Retinex model to a non-ill-conditioned problem and allows the ICE-Net to be trained with a self-supervised way. The loss functions of RED-Net are carefully formulated to separate the noises and details during training, and they are based on the idea that, if noises are independently distributed, after the processing of smoothing filters (\eg mean filter), the gradient of the noise part should be smaller than the gradient of the detail part. It can be proved qualitatively and quantitatively through experiments that the proposed method is efficient.
A Bioinspired Approach-Sensitive Neural Network for Collision Detection in Cluttered and Dynamic Backgrounds
Venue: arXiv cs.RO 2021
Year: 2021

Rapid, accurate and robust detection of looming objects in cluttered moving backgrounds is a significant and challenging problem for robotic visual systems to perform collision detection and avoidance tasks. Inspired by the neural circuit of elementary motion vision in the mammalian retina, this paper proposes a bioinspired approach-sensitive neural network (ASNN) that contains three main contributions. Firstly, a direction-selective visual processing module is built based on the spatiotemporal energy framework, which can estimate motion direction accurately via only two mutually perpendicular spatiotemporal filtering channels. Secondly, a novel approach-sensitive neural network is modeled as a push-pull structure formed by ON and OFF pathways, which responds strongly to approaching motion while insensitivity to lateral motion. Finally, a method of directionally selective inhibition is introduced, which is able to suppress the translational backgrounds effectively. Extensive synthetic and real robotic experiments show that the proposed model is able to not only detect collision accurately and robustly in cluttered and dynamic backgrounds but also extract more collision information like position and direction, for guiding rapid decision making.
Separating ABPs and Some Structured Formulas in the Non-Commutative Setting
Venue: arXiv cs.CC 2021
Year: 2021

The motivating question for this work is a long standing open problem, posed by Nisan (1991), regarding the relative powers of algebraic branching programs (ABPs) and formulas in the non-commutative setting. Even though the general question continues to remain open, we make some progress towards its resolution. To that effect, we generalise the notion of ordered polynomials in the non-commutative setting (defined by \Hrubes, Wigderson and Yehudayoff (2011)) to define abecedarian polynomials and models that naturally compute them. Our main contribution is a possible new approach towards separating formulas and ABPs in the non-commutative setting, via lower bounds against abecedarian formulas. In particular, we show the following. There is an explicit n-variate degree d abecedarian polynomial $f_{n,d}(x)$ such that 1. $f_{n, d}(x)$ can be computed by an abecedarian ABP of size O(nd); 2. any abecedarian formula computing $f_{n, \log n}(x)$ must have size that is super-polynomial in n. We also show that a super-polynomial lower bound against abecedarian formulas for $f_{\log n, n}(x)$ would separate the powers of formulas and ABPs in the non-commutative setting.
Computationally Efficient Wasserstein Loss for Structured Labels
Venue: arXiv cs.LG 2021
Year: 2021

The problem of estimating the probability distribution of labels has been widely studied as a label distribution learning (LDL) problem, whose applications include age estimation, emotion analysis, and semantic segmentation. We propose a tree-Wasserstein distance regularized LDL algorithm, focusing on hierarchical text classification tasks. We propose predicting the entire label hierarchy using neural networks, where the similarity between predicted and true labels is measured using the tree-Wasserstein distance. Through experiments using synthetic and real-world datasets, we demonstrate that the proposed method successfully considers the structure of labels during training, and it compares favorably with the Sinkhorn algorithm in terms of computation time and memory usage.
Anticipation Next -- System-sensitive technology development and integration in work contexts
Venue: arXiv cs.HC 2021
Year: 2021

When discussing future concerns within socio-technical systems in work contexts, we often find descriptions of missed technology development and integration. The experience of technology that fails whilst being integrated is often rooted in dysfunctional epistemological approaches within the research and development process. Thus, ultimately leading to sustainable technology-distrust in work contexts. This is true for organizations that integrate new technologies and for organizations that invent them. Organizations in which we find failed technology development and integrations are, in their very nature, social systems. Nowadays, those complex social systems act within an even more complex environment. This urges the development of new anticipation methods for technology development and integration. Gathering of and dealing with complex information in the described context is what we call Anticipation Next. This explorative work uses existing literature from the adjoining research fields of system theory, organizational theory, and socio-technical research to combine various concepts. We deliberately aim at a networked way of thinking in scientific contexts and thus combine multidisciplinary subject areas in one paper to present an innovative way to deal with multi-faceted problems in a human-centred way. We end with suggesting a conceptual framework that should be used in the very early stages of technology development and integration in work contexts.
Collaborative Recognition of Feasible Region with Aerial and Ground Robots through DPCN
Venue: arXiv cs.RO 2021
Year: 2021

Ground robots always get collision in that only if they get close to the obstacles, can they sense the danger and take actions, which is usually too late to avoid the crash, causing severe damage to the robots. To address this issue, we present collaboration of aerial and ground robots in recognition of feasible region. Taking the aerial robots' advantages of having large scale variance of view points of the same route which the ground robots is on, the collaboration work provides global information of road segmentation for the ground robot, thus enabling it to obtain feasible region and adjust its pose ahead of time. Under normal circumstance, the transformation between these two devices can be obtained by GPS yet with much error, directly causing inferior influence on recognition of feasible region. Thereby, we utilize the state-of-the-art research achievements in matching heterogeneous sensor measurements called deep phase correlation network(DPCN), which has excellent performance on heterogeneous mapping, to refine the transformation. The network is light-weighted and promising for better generalization. We use Aero-Ground dataset which consists of heterogeneous sensor images and aerial road segmentation images. The results show that our collaborative system has great accuracy, speed and stability.
The Rise of a New Digital Third Space Professional in Higher Education: Recognising Research Software Engineering
Venue: arXiv cs.CY 2021
Year: 2021

Research Software Engineering is the application of professional software skills to research problems. Those who do this are called Research Software Engineers or RSEs for short. RSEs work closely with researchers in a collaborative fashion rather than just offering a standalone function (c.f. the traditional IT workforce or Librarians working to provide a general set of services to the University community such as research, teaching or administrative functions). It is this overlap with academic researchers that make the RSE and the RSE management a new type of third space professional in the higher education sector. We explore aspects of knowledge, relationships, legitimacies and language in relation to the model constructed by Whitchurch in Reconstructing Identities in Higher Education to explore how these relate to the RSE role and go on to highlight open problems that need resolving to put RSEs on a firmer organisational footing.
Computing the Information Content of Trained Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

How much information does a learning algorithm extract from the training data and store in a neural network's weights? Too much, and the network would overfit to the training data. Too little, and the network would not fit to anything at all. Naïvely, the amount of information the network stores should scale in proportion to the number of trainable weights. This raises the question: how can neural networks with vastly more weights than training data still generalise? A simple resolution to this conundrum is that the number of weights is usually a bad proxy for the actual amount of information stored. For instance, typical weight vectors may be highly compressible. Then another question occurs: is it possible to compute the actual amount of information stored? This paper derives both a consistent estimator and a closed-form upper bound on the information content of infinitely wide neural networks. The derivation is based on an identification between neural information content and the negative log probability of a Gaussian orthant. This identification yields bounds that analytically control the generalisation behaviour of the entire solution space of infinitely wide networks. The bounds have a simple dependence on both the network architecture and the training data. Corroborating the findings of Valle-Pérez et al. (2019), who conducted a similar analysis using approximate Gaussian integration techniques, the bounds are found to be both non-vacuous and correlated with the empirical generalisation behaviour at finite width.
On the Cost of Unsuccessful Searches in Search Trees with Two-way Comparisons
Venue: arXiv cs.DS 2021
Year: 2021

Search trees are commonly used to implement access operations to a set of stored keys. If this set is static and the probabilities of membership queries are known in advance, then one can precompute an optimal search tree, namely one that minimizes the expected access cost. For a non-key query, a search tree can determine its approximate location by returning the inter-key interval containing the query. This is in contrast to other dictionary data structures, like hash tables, that only report a failed search. We address the question "what is the additional cost of determining approximate locations for non-key queries"? We prove that for two-way comparison trees this additional cost is at most 1. Our proof is based on a novel probabilistic argument that involves converting a search tree that does not identify non-key queries into a random tree that does.
Automatic Cell Counting in Flourescent Microscopy Using Deep Learning
Venue: arXiv cs.CV 2021
Year: 2021

Counting cells in fluorescent microscopy is a tedious, time-consuming task that researchers have to accomplish to assess the effects of different experimental conditions on biological structures of interest. Although such objects are generally easy to identify, the process of manually annotating cells is sometimes subject to arbitrariness due to the operator's interpretation of the borderline cases. We propose a Machine Learning approach that exploits a fully-convolutional network in a binary segmentation fashion to localize the objects of interest. Counts are then retrieved as the number of detected items. Specifically, we adopt a UNet-like architecture leveraging residual units and an extended bottleneck for enlarging the field-of-view. In addition, we make use of weighted maps that penalize the errors on cells boundaries increasingly with overcrowding. These changes provide more context and force the model to focus on relevant features during pixel-wise classification. As a result, the model performance is enhanced, especially in presence of clumping cells, artifacts and confounding biological structures. Posterior assessment of the results with domain experts confirms that the model detects cells of interest correctly. The model demonstrates a human-level ability inasmuch even erroneous predictions seem to fall within the limits of operator interpretation. This qualitative assessment is also corroborated by quantitative metrics as an ${F_1}$ score of 0.87. Despite some difficulties in interpretation, results are also satisfactory with respect to the counting task, as testified by mean and median absolute error of, respectively, 0.8 and 1.
Towards 6G with Connected Sky: UAVs and Beyond
Venue: arXiv cs.IT 2021
Year: 2021

The large-scale and ever-growing use of unmanned aerial vehicles (UAVs) in a wide range of applications is foreseen to be a major part of beyond 5G and 6G wireless networks in the next decade. The effective support of such massive deployment of UAVs requires offering reliable, secure, and cost-effective wireless connectivity. In this regard, cellular networks play essential roles in serving UAVs acting as flying user equipments. While the cellular networks provide promising connectivity solutions for UAVs, enabling robust UAV operations faces several challenges. In this paper, an overview of key barriers and design considerations of widespread commercial use of flying UAVs are presented along with their potential solutions. In addition, we discuss how cellular networks can support UAVs by relying on their advanced features, network intelligence, key enabling technologies for beyond 5G and 6G, and exploiting new tools from machine learning. Finally, we shed light on offering wireless services to high altitudes and the integration of non-terrestrial networks with terrestrial networks towards limitless connectivity in 6G.