OpenRaiser/Intern-Atlas huggingface dataset:
Deep Cross-Subject Mapping of Neural Activity
Venue: arXiv cs.NE 2022
Year: 2022

Objective. In this paper, we consider the problem of cross-subject decoding, where neural activity data collected from the prefrontal cortex of a given subject (destination) is used to decode motor intentions from the neural activity of a different subject (source). Approach. We cast the problem of neural activity mapping in a probabilistic framework where we adopt deep generative modelling. Our proposed algorithm uses deep conditional variational autoencoder to infer the representation of the neural activity of the source subject into an adequate feature space of the destination subject where neural decoding takes place. Results. We verify our approach on an experimental data set in which two macaque monkeys perform memory-guided visual saccades to one of eight target locations. The results show a peak cross-subject decoding improvement of $8\%$ over subject-specific decoding. Conclusion. We demonstrate that a neural decoder trained on neural activity signals of one subject can be used to robustly decode the motor intentions of a different subject with high reliability. This is achieved in spite of the non-stationary nature of neural activity signals and the subject-specific variations of the recording conditions. Significance. The findings reported in this paper are an important step towards the development of cross-subject brain-computer that generalize well across a population.
COVID-19 Twitter Dataset with Latent Topics, Sentiments and Emotions Attributes
Venue: arXiv cs.CL 2022
Year: 2022

This paper describes a large global dataset on people's discourse and responses to the COVID-19 pandemic over the Twitter platform. From 28 January 2020 to 1 June 2022, we collected and processed over 252 million Twitter posts from more than 29 million unique users using four keywords: "corona", "wuhan", "nCov" and "covid". Leveraging probabilistic topic modelling and pre-trained machine learning-based emotion recognition algorithms, we labelled each tweet with seventeen attributes, including a) ten binary attributes indicating the tweet's relevance (1) or irrelevance (0) to the top ten detected topics, b) five quantitative emotion attributes indicating the degree of intensity of the valence or sentiment (from 0: extremely negative to 1: extremely positive) and the degree of intensity of fear, anger, sadness and happiness emotions (from 0: not at all to 1: extremely intense), and c) two categorical attributes indicating the sentiment (very negative, negative, neutral or mixed, positive, very positive) and the dominant emotion (fear, anger, sadness, happiness, no specific emotion) the tweet is mainly expressing. We discuss the technical validity and report the descriptive statistics of these attributes, their temporal distribution, and geographic representation. The paper concludes with a discussion of the dataset's usage in communication, psychology, public health, economics, and epidemiology.
Lifting Constructions of PDAs for Coded Caching with Linear Subpacketization
Venue: arXiv cs.IT 2022
Year: 2022

Coded caching is a technique where multicasting and coding opportunities are utilized to achieve better rate-memory tradeoff in cached networks. A crucial parameter in coded caching is subpacketization, which is the number of parts a file is to be split into for coding purposes. The original Maddah-Ali-Niesen scheme has order-optimal rate at a subpacketization growing exponentially with the number of users. In contrast, placement and delivery schemes in coded caching, designed using placement delivery arrays (PDAs), can have linear subpacketization with a penalty in rate. In this work, we propose several constructions of efficient PDAs through lifting, where a base PDA is expanded by replacing each entry by another PDA. By proposing and using the notion of Blackburn-compatibility of PDAs, we provide multiple lifting constructions with increasing coding gains. We compare the constructed coded caching schemes with other existing schemes for moderately high number of users and show that the proposed constructions are versatile and achieve a good rate-memory tradeoff at low subpacketizations.
The Big-O Problem
Venue: arXiv cs.FL 2022
Year: 2022

Given two weighted automata, we consider the problem of whether one is big-O of the other, i.e., if the weight of every finite word in the first is not greater than some constant multiple of the weight in the second. We show that the problem is undecidable, even for the instantiation of weighted automata as labelled Markov chains. Moreover, even when it is known that one weighted automaton is big-O of another, the problem of finding or approximating the associated constant is also undecidable. Our positive results show that the big-O problem is polynomial-time solvable for unambiguous automata, coNP-complete for unlabelled weighted automata (i.e., when the alphabet is a single character) and decidable, subject to Schanuel's conjecture, when the language is bounded (i.e., a subset of $w_1^*\dots w_m^*$ for some finite words $w_1,\dots,w_m$) or when the automaton has finite ambiguity. On labelled Markov chains, the problem can be restated as a ratio total variation distance, which, instead of finding the maximum difference between the probabilities of any two events, finds the maximum ratio between the probabilities of any two events. The problem is related to $\varepsilon$-differential privacy, for which the optimal constant of the big-O notation is exactly $\exp(\varepsilon)$.
Adapting the Directed Grid Theorem into an FPT Algorithm
Venue: arXiv cs.DS 2022
Year: 2022

The Grid Theorem of Robertson and Seymour [JCTB, 1986], is one of the most important tools in the field of structural graph theory, finding numerous applications in the design of algorithms for undirected graphs. An analogous version of the Grid Theorem in digraphs was conjectured by Johnson et al. [JCTB, 2001], and proved by Kawarabayashi and Kreutzer [STOC, 2015]. Namely, they showed that there is a function $f(k)$ such that every digraph of directed tree-width at least $f(k)$ contains a cylindrical grid of size $k$ as a butterfly minor and stated that their proof can be turned into an XP algorithm, with parameter $k$, that either constructs a decomposition of the appropriate width, or finds the claimed large cylindrical grid as a butterfly minor. In this paper, we adapt some of the steps of the proof of Kawarabayashi and Kreutzer to improve this XP algorithm into an FPT algorithm. Towards this, our main technical contributions are two FPT algorithms with parameter $k$. The first one either produces an arboreal decomposition of width $3k-2$ or finds a haven of order $k$ in a digraph $D$, improving on the original result for arboreal decompositions by Johnson et al. The second algorithm finds a well-linked set of order $k$ in a digraph $D$ of large directed tree-width. As tools to prove these results, we show how to solve a generalized version of the problem of finding balanced separators for a given set of vertices $T$ in FPT time with parameter $|T|$, a result that we consider to be of its own interest.
Directed Shortest Paths via Approximate Cost Balancing
Venue: arXiv cs.DS 2022
Year: 2022

We present an $O(nm)$ algorithm for all-pairs shortest paths computations in a directed graph with $n$ nodes, $m$ arcs, and nonnegative integer arc costs. This matches the complexity bound attained by Thorup \cite{Thorup1999} for the all-pairs problems in undirected graphs. The main insight is that shortest paths problems with approximately balanced directed cost functions can be solved similarly to the undirected case. The algorithm finds an approximately balanced reduced cost function in an $O(m\sqrt{n}\log n)$ preprocessing step. Using these reduced costs, every shortest path query can be solved in $O(m)$ time using an adaptation of Thorup's component hierarchy method. The balancing result can also be applied to the $\ell_\infty$-matrix balancing problem.
Optimal Coreset for Gaussian Kernel Density Estimation
Venue: arXiv cs.DS 2022
Year: 2022

Given a point set $P\subset \mathbb{R}^d$, the kernel density estimate of $P$ is defined as \[ \overline{\mathcal{G}}_P(x) = \frac{1}{\left|P\right|}\sum_{p\in P}e^{-\left\lVert x-p \right\rVert^2} \] for any $x\in\mathbb{R}^d$. We study how to construct a small subset $Q$ of $P$ such that the kernel density estimate of $P$ is approximated by the kernel density estimate of $Q$. This subset $Q$ is called a coreset. The main technique in this work is constructing a $\pm 1$ coloring on the point set $P$ by discrepancy theory and we leverage Banaszczyk's Theorem. When $d>1$ is a constant, our construction gives a coreset of size $O\left(\frac{1}{\varepsilon}\right)$ as opposed to the best-known result of $O\left(\frac{1}{\varepsilon}\sqrt{\log\frac{1}{\varepsilon}}\right)$. It is the first result to give a breakthrough on the barrier of $\sqrt{\log}$ factor even when $d=2$.
Dynamics of Mobile Manipulators using Dual Quaternion Algebra
Venue: arXiv cs.RO 2022
Year: 2022

This paper presents two approaches to obtain the dynamical equations of mobile manipulators using dual quaternion algebra. The first one is based on a general recursive Newton-Euler formulation and uses twists and wrenches, which are propagated through high-level algebraic operations and works for any type of joints and arbitrary parameterizations. The second approach is based on Gauss's Principle of Least Constraint (GPLC) and includes arbitrary equality constraints. In addition to showing the connections of GPLC with Gibbs-Appell and Kane's equations, we use it to model a nonholonomic mobile manipulator. Our current formulations are more general than their counterparts in the state of the art, although GPLC is more computationally expensive, and simulation results show that they are as accurate as the classic recursive Newton-Euler algorithm.
Artificial Fingerprinting for Generative Models: Rooting Deepfake Attribution in Training Data
Venue: arXiv cs.CR 2022
Year: 2022

Photorealistic image generation has reached a new level of quality due to the breakthroughs of generative adversarial networks (GANs). Yet, the dark side of such deepfakes, the malicious use of generated media, raises concerns about visual misinformation. While existing research work on deepfake detection demonstrates high accuracy, it is subject to advances in generation techniques and adversarial iterations on detection countermeasure techniques. Thus, we seek a proactive and sustainable solution on deepfake detection, that is agnostic to the evolution of generative models, by introducing artificial fingerprints into the models. Our approach is simple and effective. We first embed artificial fingerprints into training data, then validate a surprising discovery on the transferability of such fingerprints from training data to generative models, which in turn appears in the generated deepfakes. Experiments show that our fingerprinting solution (1) holds for a variety of cutting-edge generative models, (2) leads to a negligible side effect on generation quality, (3) stays robust against image-level and model-level perturbations, (4) stays hard to be detected by adversaries, and (5) converts deepfake detection and attribution into trivial tasks and outperforms the recent state-of-the-art baselines. Our solution closes the responsibility loop between publishing pre-trained generative model inventions and their possible misuses, which makes it independent of the current arms race. Code and models are available at https://github.com/ningyu1991/ArtificialGANFingerprints .
Backdoor Learning: A Survey
Venue: arXiv cs.CR 2022
Year: 2022

Backdoor attack intends to embed hidden backdoor into deep neural networks (DNNs), so that the attacked models perform well on benign samples, whereas their predictions will be maliciously changed if the hidden backdoor is activated by attacker-specified triggers. This threat could happen when the training process is not fully controlled, such as training on third-party datasets or adopting third-party models, which poses a new and realistic threat. Although backdoor learning is an emerging and rapidly growing research area, its systematic review, however, remains blank. In this paper, we present the first comprehensive survey of this realm. We summarize and categorize existing backdoor attacks and defenses based on their characteristics, and provide a unified framework for analyzing poisoning-based backdoor attacks. Besides, we also analyze the relation between backdoor attacks and relevant fields ($i.e.,$ adversarial attacks and data poisoning), and summarize widely adopted benchmark datasets. Finally, we briefly outline certain future research directions relying upon reviewed works. A curated list of backdoor-related resources is also available at \url{https://github.com/THUYimingLi/backdoor-learning-resources}.
Multi-Stage Hybrid Federated Learning over Large-Scale D2D-Enabled Fog Networks
Venue: arXiv cs.NI 2022
Year: 2022

Federated learning has generated significant interest, with nearly all works focused on a "star" topology where nodes/devices are each connected to a central server. We migrate away from this architecture and extend it through the network dimension to the case where there are multiple layers of nodes between the end devices and the server. Specifically, we develop multi-stage hybrid federated learning (MH-FL), a hybrid of intra- and inter-layer model learning that considers the network as a multi-layer cluster-based structure. MH-FL considers the topology structures among the nodes in the clusters, including local networks formed via device-to-device (D2D) communications, and presumes a semi-decentralized architecture for federated learning. It orchestrates the devices at different network layers in a collaborative/cooperative manner (i.e., using D2D interactions) to form local consensus on the model parameters and combines it with multi-stage parameter relaying between layers of the tree-shaped hierarchy. We derive the upper bound of convergence for MH-FL with respect to parameters of the network topology (e.g., the spectral radius) and the learning algorithm (e.g., the number of D2D rounds in different clusters). We obtain a set of policies for the D2D rounds at different clusters to guarantee either a finite optimality gap or convergence to the global optimum. We then develop a distributed control algorithm for MH-FL to tune the D2D rounds in each cluster over time to meet specific convergence criteria. Our experiments on real-world datasets verify our analytical results and demonstrate the advantages of MH-FL in terms of resource utilization metrics.
Understanding and Mitigating the Limitations of Prioritized Experience Replay
Venue: arXiv cs.AI 2022
Year: 2022

Prioritized Experience Replay (ER) has been empirically shown to improve sample efficiency across many domains and attracted great attention; however, there is little theoretical understanding of why such prioritized sampling helps and its limitations. In this work, we take a deep look at the prioritized ER. In a supervised learning setting, we show the equivalence between the error-based prioritized sampling method for mean squared error and uniform sampling for cubic power loss. We then provide theoretical insight into why it improves convergence rate upon uniform sampling during early learning. Based on the insight, we further point out two limitations of the prioritized ER method: 1) outdated priorities and 2) insufficient coverage of the sample space. To mitigate the limitations, we propose our model-based stochastic gradient Langevin dynamics sampling method. We show that our method does provide states distributed close to an ideal prioritized sampling distribution estimated by the brute-force method, which does not suffer from the two limitations. We conduct experiments on both discrete and continuous control problems to show our approach's efficacy and examine the practical implication of our method in an autonomous driving application.
Software Development Analytics in Practice: A Systematic Literature Review
Venue: arXiv cs.SE 2022
Year: 2022

Context:Software Development Analytics is a research area concerned with providing insights to improve product deliveries and processes. Many types of studies, data sources and mining methods have been used for that purpose. Objective:This systematic literature review aims at providing an aggregate view of the relevant studies on Software Development Analytics in the past decade, with an emphasis on its application in practical settings. Method:Definition and execution of a search string upon several digital libraries, followed by a quality assessment criteria to identify the most relevant papers. On those, we extracted a set of characteristics (study type, data source, study perspective, development life-cycle activities covered, stakeholders, mining methods, and analytics scope) and classified their impact against a taxonomy. Results:Source code repositories, experimental case studies, and developers are the most common data sources, study types, and stakeholders, respectively. Product and project managers are also often present, but less than expected. Mining methods are evolving rapidly and that is reflected in the long list identified. Descriptive statistics are the most usual method followed by correlation analysis. Being software development an important process in every organization, it was unexpected to find that process mining was present in only one study. Most contributions to the software development life cycle were given in the quality dimension. Time management and costs control were lightly debated. The analysis of security aspects suggests it is an increasing topic of concern for practitioners. Risk management contributions are scarce. Conclusions:There is a wide improvement margin for software development analytics in practice. For instance, mining and analyzing the activities performed by software developers in their actual workbench, the IDE.
Hierarchical Contrastive Motion Learning for Video Action Recognition
Venue: arXiv cs.CV 2022
Year: 2022

One central question for video action recognition is how to model motion. In this paper, we present hierarchical contrastive motion learning, a new self-supervised learning framework to extract effective motion representations from raw video frames. Our approach progressively learns a hierarchy of motion features that correspond to different abstraction levels in a network. This hierarchical design bridges the semantic gap between low-level motion cues and high-level recognition tasks, and promotes the fusion of appearance and motion information at multiple levels. At each level, an explicit motion self-supervision is provided via contrastive learning to enforce the motion features at the current level to predict the future ones at the previous level. Thus, the motion features at higher levels are trained to gradually capture semantic dynamics and evolve more discriminative for action recognition. Our motion learning module is lightweight and flexible to be embedded into various backbone networks. Extensive experiments on four benchmarks show that the proposed approach consistently achieves superior results.
Domain Generalization via Optimal Transport with Metric Similarity Learning
Venue: arXiv cs.CV 2022
Year: 2022

Generalizing knowledge to unseen domains, where data and labels are unavailable, is crucial for machine learning models. We tackle the domain generalization problem to learn from multiple source domains and generalize to a target domain with unknown statistics. The crucial idea is to extract the underlying invariant features across all the domains. Previous domain generalization approaches mainly focused on learning invariant features and stacking the learned features from each source domain to generalize to a new target domain while ignoring the label information, which will lead to indistinguishable features with an ambiguous classification boundary. For this, one possible solution is to constrain the label-similarity when extracting the invariant features and to take advantage of the label similarities for class-specific cohesion and separation of features across domains. Therefore we adopt optimal transport with Wasserstein distance, which could constrain the class label similarity, for adversarial training and also further deploy a metric learning objective to leverage the label information for achieving distinguishable classification boundary. Empirical results show that our proposed method could outperform most of the baselines. Furthermore, ablation studies also demonstrate the effectiveness of each component of our method.
Split and Expand: An inference-time improvement for Weakly Supervised Cell Instance Segmentation
Venue: arXiv cs.CV 2022
Year: 2022

We consider the problem of segmenting cell nuclei instances from Hematoxylin and Eosin (H&E) stains with weak supervision. While most recent works focus on improving the segmentation quality, this is usually insufficient for instance segmentation of cell instances clumped together or with a small size. In this work, we propose a two-step post-processing procedure, Split and Expand, that directly improves the conversion of segmentation maps to instances. In the Split step, we split clumps of cells from the segmentation map into individual cell instances with the guidance of cell-center predictions through Gaussian Mixture Model clustering. In the Expand step, we find missing small cells using the cell-center predictions (which tend to capture small cells more consistently as they are trained using reliable point annotations), and utilize Layer-wise Relevance Propagation (LRP) explanation results to expand those cell-center predictions into cell instances. Our Split and Expand post-processing procedure is training-free and is executed at inference-time only. To further improve the performance of our method, a feature re-weighting loss based on LRP is proposed. We test our procedure on the MoNuSeg and TNBC datasets and show that our proposed method provides statistically significant improvements on object-level metrics. Our code will be made available.
Three-stage intelligent support of clinical decision making for higher trust, validity, and explainability
Venue: arXiv cs.AI 2022
Year: 2022

The paper presents an approach for building consistent and applicable clinical decision support systems (CDSSs) using a data-driven predictive model aimed at resolving the problem of low applicability and scalability of CDSSs in real-world applications. The approach is based on a threestage application of domain-specific and data-driven supportive procedures that are to be integrated into clinical business processes with higher trust and explainability of the prediction results and recommendations. Within the considered three stages, the regulatory policy, data-driven modes, and interpretation procedures are integrated to enable natural domain-specific interaction with decisionmakers with sequential narrowing of the intelligent decision support focus. The proposed methodology enables a higher level of automation, scalability, and semantic interpretability of CDSSs. The approach was implemented in software solutions and tested within a case study in T2DM prediction, enabling us to improve known clinical scales (such as FINDRISK) while keeping the problem-specific reasoning interface similar to existing applications. Such inheritance, together with the three-staged approach, provide higher compatibility of the solution and leads to trust, valid, and explainable application of data-driven solutions in real-world cases.