OpenRaiser/Intern-Atlas huggingface dataset:
Hardness of Approximate Diameter: Now for Undirected Graphs
Venue: arXiv cs.CC 2021
Year: 2021

Approximating the graph diameter is a basic task of both theoretical and practical interest. A simple folklore algorithm can output a 2-approximation to the diameter in linear time by running BFS from an arbitrary vertex. It has been open whether a better approximation is possible in near-linear time. A series of papers on fine-grained complexity have led to strong hardness results for diameter in directed graphs, culminating in a recent tradeoff curve independently discovered by [Li, STOC'21] and [Dalirrooyfard and Wein, STOC'21], showing that under the Strong Exponential Time Hypothesis (SETH), for any integer $k\ge 2$ and $δ>0$, a $2-\frac{1}{k}-δ$ approximation for diameter in directed $m$-edge graphs requires $mn^{1+1/(k-1)-o(1)}$ time. In particular, the simple linear time $2$-approximation algorithm is optimal for directed graphs. In this paper we prove that the same tradeoff lower bound curve is possible for undirected graphs as well, extending results of [Roditty and Vassilevska W., STOC'13], [Li'20] and [Bonnet, ICALP'21] who proved the first few cases of the curve, $k=2,3$ and $4$, respectively. Our result shows in particular that the simple linear time $2$-approximation algorithm is also optimal for undirected graphs. To obtain our result we develop new tools for fine-grained reductions that could be useful for proving SETH-based hardness for other problems in undirected graphs related to distance computation.
Data-driven battery operation for energy arbitrage using rainbow deep reinforcement learning
Venue: arXiv cs.LG 2021
Year: 2021

As the world seeks to become more sustainable, intelligent solutions are needed to increase the penetration of renewable energy. In this paper, the model-free deep reinforcement learning algorithm Rainbow Deep Q-Networks is used to control a battery in a small microgrid to perform energy arbitrage and more efficiently utilise solar and wind energy sources. The grid operates with its own demand and renewable generation based on a dataset collected at Keele University, as well as using dynamic energy pricing from a real wholesale energy market. Four scenarios are tested including using demand and price forecasting produced with local weather data. The algorithm and its subcomponents are evaluated against two continuous control benchmarks with Rainbow able to outperform all other method. This research shows the importance of using the distributional approach for reinforcement learning when working with complex environments and reward functions, as well as how it can be used to visualise and contextualise the agent's behaviour for real-world applications.
Gradual Domain Adaptation in the Wild:When Intermediate Distributions are Absent
Venue: arXiv cs.LG 2021
Year: 2021

We focus on the problem of domain adaptation when the goal is shifting the model towards the target distribution, rather than learning domain invariant representations. It has been shown that under the following two assumptions: (a) access to samples from intermediate distributions, and (b) samples being annotated with the amount of change from the source distribution, self-training can be successfully applied on gradually shifted samples to adapt the model toward the target distribution. We hypothesize having (a) is enough to enable iterative self-training to slowly adapt the model to the target distribution, by making use of an implicit curriculum. In the case where (a) does not hold, we observe that iterative self-training falls short. We propose GIFT, a method that creates virtual samples from intermediate distributions by interpolating representations of examples from source and target domains. We evaluate an iterative-self-training method on datasets with natural distribution shifts, and show that when applied on top of other domain adaptation methods, it improves the performance of the model on the target dataset. We run an analysis on a synthetic dataset to show that in the presence of (a) iterative-self-training naturally forms a curriculum of samples. Furthermore, we show that when (a) does not hold, GIFT performs better than iterative self-training.
PSB2: The Second Program Synthesis Benchmark Suite
Venue: arXiv cs.SE 2021
Year: 2021

For the past six years, researchers in genetic programming and other program synthesis disciplines have used the General Program Synthesis Benchmark Suite to benchmark many aspects of automatic program synthesis systems. These problems have been used to make notable progress toward the goal of general program synthesis: automatically creating the types of software that human programmers code. Many of the systems that have attempted the problems in the original benchmark suite have used it to demonstrate performance improvements granted through new techniques. Over time, the suite has gradually become outdated, hindering the accurate measurement of further improvements. The field needs a new set of more difficult benchmark problems to move beyond what was previously possible. In this paper, we describe the 25 new general program synthesis benchmark problems that make up PSB2, a new benchmark suite. These problems are curated from a variety of sources, including programming katas and college courses. We selected these problems to be more difficult than those in the original suite, and give results using PushGP showing this increase in difficulty. These new problems give plenty of room for improvement, pointing the way for the next six or more years of general program synthesis research.
Exploiting Large-scale Teacher-Student Training for On-device Acoustic Models
Venue: arXiv cs.SD 2021
Year: 2021

We present results from Alexa speech teams on semi-supervised learning (SSL) of acoustic models (AM) with experiments spanning over 3000 hours of GPU time, making our study one of the largest of its kind. We discuss SSL for AMs in a small footprint setting, showing that a smaller capacity model trained with 1 million hours of unsupervised data can outperform a baseline supervised system by 14.3% word error rate reduction (WERR). When increasing the supervised data to seven-fold, our gains diminish to 7.1% WERR; to improve SSL efficiency at larger supervised data regimes, we employ a step-wise distillation into a smaller model, obtaining a WERR of 14.4%. We then switch to SSL using larger student models in low data regimes; while learning efficiency with unsupervised data is higher, student models may outperform teacher models in such a setting. We develop a theoretical sketch to explain this behavior.
Security and Privacy for Healthcare Blockchains
Venue: arXiv cs.CR 2021
Year: 2021

Healthcare blockchains provide an innovative way to store healthcare information, execute healthcare transactions, and build trust for healthcare data sharing and data integration in a decentralized open healthcare network environment. Although the healthcare blockchain technology has attracted broad interests and attention in industry, government and academia, the security and privacy concerns remain the focus of debate when deploying blockchains for information sharing in the healthcare sector from business operation to research collaboration. This paper focuses on the security and privacy requirements for medical data sharing using blockchain, and provides a comprehensive analysis of the security and privacy risks and requirements, accompanied by technical solution techniques and strategies. First, we discuss the security and privacy requirements and attributes required for electronic medical data sharing by deploying the healthcare blockchain. Second, we categorize existing efforts into three reference blockchain usage scenarios for electronic medical data sharing, and discuss the technologies for implementing these security and privacy properties in the three categories of usage scenarios for healthcare blockchain, such as anonymous signatures, attribute-based encryption, zero-knowledge proofs, verification techniques for smart contract security. Finally, we discuss other potential blockchain application scenarios in healthcare sector. We conjecture that this survey will help healthcare professionals, decision makers, and healthcare service developers to gain technical and intuitive insights into the security and privacy of healthcare blockchains in terms of concepts, risks, requirements, development and deployment technologies and systems.
Team RUC_AIM3 Technical Report at ActivityNet 2021: Entities Object Localization
Venue: arXiv cs.CV 2021
Year: 2021

Entities Object Localization (EOL) aims to evaluate how grounded or faithful a description is, which consists of caption generation and object grounding. Previous works tackle this problem by jointly training the two modules in a framework, which limits the complexity of each module. Therefore, in this work, we propose to divide these two modules into two stages and improve them respectively to boost the whole system performance. For the caption generation, we propose a Unified Multi-modal Pre-training Model (UMPM) to generate event descriptions with rich objects for better localization. For the object grounding, we fine-tune the state-of-the-art detection model MDETR and design a post processing method to make the grounding results more faithful. Our overall system achieves the state-of-the-art performances on both sub-tasks in Entities Object Localization challenge at Activitynet 2021, with 72.57 localization accuracy on the testing set of sub-task I and 0.2477 F1_all_per_sent on the hidden testing set of sub-task II.
AI Empowered Resource Management for Future Wireless Networks
Venue: arXiv cs.IT 2021
Year: 2021

Resource management plays a pivotal role in wireless networks, which, unfortunately, leads to challenging NP-hard problems. Artificial Intelligence (AI), especially deep learning techniques, has recently emerged as a disruptive technology to solve such challenging problems in a real-time manner. However, although promising results have been reported, practical design guidelines and performance guarantees of AI-based approaches are still missing. In this paper, we endeavor to address two fundamental questions: 1) What are the main advantages of AI-based methods compared with classical techniques; and 2) Which neural network should we choose for a given resource management task. For the first question, four advantages are identified and discussed. For the second question, \emph{optimality gap}, i.e., the gap to the optimal performance, is proposed as a measure for selecting model architectures, as well as, for enabling a theoretical comparison between different AI-based approaches. Specifically, for $K$-user interference management problem, we theoretically show that graph neural networks (GNNs) are superior to multi-layer perceptrons (MLPs), and the performance gap between these two methods grows with $\sqrt{K}$.
Matching Patterns with Variables under Hamming Distance
Venue: arXiv cs.DS 2021
Year: 2021

A pattern $α$ is a string of variables and terminal letters. We say that $α$ matches a word $w$, consisting only of terminal letters, if $w$ can be obtained by replacing the variables of $α$ by terminal words. The matching problem, i.e., deciding whether a given pattern matches a given word, was heavily investigated: it is NP-complete in general, but can be solved efficiently for classes of patterns with restricted structure. In this paper, we approach this problem in a generalized setting, by considering approximate pattern matching under Hamming distance. More precisely, we are interested in what is the minimum Hamming distance between $w$ and any word $u$ obtained by replacing the variables of $α$ by terminal words. Firstly, we address the class of regular patterns (in which no variable occurs twice) and propose efficient algorithms for this problem, as well as matching conditional lower bounds. We show that the problem can still be solved efficiently if we allow repeated variables, but restrict the way the different variables can be interleaved according to a locality parameter. However, as soon as we allow a variable to occur more than once and its occurrences can be interleaved arbitrarily with those of other variables, even if none of them occurs more than once, the problem becomes intractable.
Improving Take-over Situation by Active Communication
Venue: arXiv cs.HC 2021
Year: 2021

In this short paper an idea is sketched, how to support drivers of an autonomous vehicle in taking back control of the vehicle after a longer section of autonomous cruising. The hypothesis is that a clear communication about the location and behavior of relevant objects in the environment will help the driver to quickly grasp the situational context and thus support drivers in safely handling the ongoing driving situation manually after take-over. Based on this hypothesis, a research concept is sketched, which entails the necessary components as well as the disciplines involved.
States of confusion: Eye and Head tracking reveal surgeons' confusion during arthroscopic surgery
Venue: arXiv cs.HC 2021
Year: 2021

During arthroscopic surgeries, surgeons are faced with challenges like cognitive re-projection of the 2D screen output into the 3D operating site or navigation through highly similar tissue. Training of these cognitive processes takes much time and effort for young surgeons, but is necessary and crucial for their education. In this study we want to show how to recognize states of confusion of young surgeons during an arthroscopic surgery, by looking at their eye and head movements and feeding them to a machine learning model. With an accuracy of over 94\% and detection speed of 0.039 seconds, our model is a step towards online diagnostic and training systems for the perceptual-cognitive processes of surgeons during arthroscopic surgeries.
Stochastic modelling of blockchain consensus
Venue: arXiv cs.DC 2021
Year: 2021

Blockchain and general purpose distributed ledgers are foundational technologies which bring significant innovation in the infrastructures and other underpinnings of our socio-economic systems. These P2P technologies are able to securely diffuse information within and across networks, without need for trustees or central authorities to enforce consensus. In this contribution, we propose a minimalistic stochastic model to understand the dynamics of blockchain-based consensus. By leveraging on random-walk theory, we model block propagation delay on different network topologies and provide a classification of blockchain systems in terms of two emergent properties. Firstly, we identify two performing regimes: a functional regime corresponding to an optimal system function; and a non-functional regime characterised by a congested or branched state of sub-optimal blockchains. Secondly, we discover a phase transition during the emergence of consensus and numerically investigate the corresponding critical point. Our results provide important insights into the consensus mechanism and sub-optimal states in decentralised systems.
How Should Agents Ask Questions For Situated Learning? An Annotated Dialogue Corpus
Venue: arXiv cs.CL 2021
Year: 2021

Intelligent agents that are confronted with novel concepts in situated environments will need to ask their human teammates questions to learn about the physical world. To better understand this problem, we need data about asking questions in situated task-based interactions. To this end, we present the Human-Robot Dialogue Learning (HuRDL) Corpus - a novel dialogue corpus collected in an online interactive virtual environment in which human participants play the role of a robot performing a collaborative tool-organization task. We describe the corpus data and a corresponding annotation scheme to offer insight into the form and content of questions that humans ask to facilitate learning in a situated environment. We provide the corpus as an empirically-grounded resource for improving question generation in situated intelligent agents.
COSTA: Communication-Optimal Shuffle and Transpose Algorithm with Process Relabeling
Venue: arXiv cs.DC 2021
Year: 2021

Communication-avoiding algorithms for Linear Algebra have become increasingly popular, in particular for distributed memory architectures. In practice, these algorithms assume that the data is already distributed in a specific way, thus making data reshuffling a key to use them. For performance reasons, a straightforward all-to-all exchange must be avoided. Here, we show that process relabeling (i.e. permuting processes in the final layout) can be used to obtain communication optimality for data reshuffling, and that it can be efficiently found by solving a Linear Assignment Problem (Maximum Weight Bipartite Perfect Matching). Based on this, we have developed a Communication-Optimal Shuffle and Transpose Algorithm (COSTA): this highly-optimised algorithm implements $A=α\cdot \operatorname{op}(B) + β\cdot A,\ \operatorname{op} \in \{\operatorname{transpose}, \operatorname{conjugate-transpose}, \operatorname{identity}\}$ on distributed systems, where $A, B$ are matrices with potentially different (distributed) layouts and $α, β$ are scalars. COSTA can take advantage of the communication-optimal process relabeling even for heterogeneous network topologies, where latency and bandwidth differ among nodes. The implementation not only outperforms the best available ScaLAPACK redistribute and transpose routines multiple times, but is also able to deal with more general matrix layouts, in particular it is not limited to block-cyclic layouts. Finally, we use COSTA to integrate a communication-optimal matrix multiplication algorithm into the CP2K quantum chemistry simulation package. This way, we show that COSTA can be used to unlock the full potential of recent Linear Algebra algorithms in applications by facilitating interoperability between algorithms with a wide range of data layouts, in addition to bringing significant redistribution speedups.
Spatially Scalable Lossy Coded Caching
Venue: arXiv cs.IT 2021
Year: 2021

We apply the coded caching scheme proposed by Maddah-Ali and Niesen to a multipoint multicasting video paradigm. Partially caching the video files on the wireless devices provides an opportunity to decrease data traffic load in peak hours via sending multicast coded messages to users. In this paper, we propose a two-hop wireless network for video multicasting, where the common coded multicast message is transmitted through different single antenna Edge Nodes (ENs) to multiple antenna users. Each user can decide to decode any EN by using a zero forcing receiver. Motivated by Scalable Video Coding (SVC), we consider successive refinement source coding in order to provide a ``softer'' tradeoff between the number of decoded ENs and the source distortion at each user receiver. The resulting coding scheme can be seen as the concatenation of Maddah-Ali and Niesen coded caching for each source-coded layer, and multiple description coding. Using stochastic geometry, we investigate the tradeoff between delivery time and per-user average source distortion. The proposed system is spatially scalable in the sense that, for given users' and ENs' spatial density, the achieved distortion-delivery time performance is independent of the coverage area (for in the limit of large area).
1st Place Solution for YouTubeVOS Challenge 2021:Video Instance Segmentation
Venue: arXiv cs.CV 2021
Year: 2021

Video Instance Segmentation (VIS) is a multi-task problem performing detection, segmentation, and tracking simultaneously. Extended from image set applications, video data additionally induces the temporal information, which, if handled appropriately, is very useful to identify and predict object motions. In this work, we design a unified model to mutually learn these tasks. Specifically, we propose two modules, named Temporally Correlated Instance Segmentation (TCIS) and Bidirectional Tracking (BiTrack), to take the benefit of the temporal correlation between the object's instance masks across adjacent frames. On the other hand, video data is often redundant due to the frame's overlap. Our analysis shows that this problem is particularly severe for the YoutubeVOS-VIS2021 data. Therefore, we propose a Multi-Source Data (MSD) training mechanism to compensate for the data deficiency. By combining these techniques with a bag of tricks, the network performance is significantly boosted compared to the baseline, and outperforms other methods by a considerable margin on the YoutubeVOS-VIS 2019 and 2021 datasets.
Disrupting Model Training with Adversarial Shortcuts
Venue: arXiv cs.CV 2021
Year: 2021

When data is publicly released for human consumption, it is unclear how to prevent its unauthorized usage for machine learning purposes. Successful model training may be preventable with carefully designed dataset modifications, and we present a proof-of-concept approach for the image classification setting. We propose methods based on the notion of adversarial shortcuts, which encourage models to rely on non-robust signals rather than semantic features, and our experiments demonstrate that these measures successfully prevent deep learning models from achieving high accuracy on real, unmodified data examples.
BRAIN2DEPTH: Lightweight CNN Model for Classification of Cognitive States from EEG Recordings
Venue: arXiv cs.LG 2021
Year: 2021

Several Convolutional Deep Learning models have been proposed to classify the cognitive states utilizing several neuro-imaging domains. These models have achieved significant results, but they are heavily designed with millions of parameters, which increases train and test time, making the model complex and less suitable for real-time analysis. This paper proposes a simple, lightweight CNN model to classify cognitive states from Electroencephalograph (EEG) recordings. We develop a novel pipeline to learn distinct cognitive representation consisting of two stages. The first stage is to generate the 2D spectral images from neural time series signals in a particular frequency band. Images are generated to preserve the relationship between the neighboring electrodes and the spectral property of the cognitive events. The second is to develop a time-efficient, computationally less loaded, and high-performing model. We design a network containing 4 blocks and major components include standard and depth-wise convolution for increasing the performance and followed by separable convolution to decrease the number of parameters which maintains the tradeoff between time and performance. We experiment on open access EEG meditation dataset comprising expert, nonexpert meditative, and control states. We compare performance with six commonly used machine learning classifiers and four state of the art deep learning models. We attain comparable performance utilizing less than 4\% of the parameters of other models. This model can be employed in a real-time computation environment such as neurofeedback.