OpenRaiser/Intern-Atlas huggingface dataset:
Characterizing English Variation across Social Media Communities with BERT
Venue: arXiv cs.CL 2021
Year: 2021

Much previous work characterizing language variation across Internet social groups has focused on the types of words used by these groups. We extend this type of study by employing BERT to characterize variation in the senses of words as well, analyzing two months of English comments in 474 Reddit communities. The specificity of different sense clusters to a community, combined with the specificity of a community's unique word types, is used to identify cases where a social group's language deviates from the norm. We validate our metrics using user-created glossaries and draw on sociolinguistic theories to connect language variation with trends in community behavior. We find that communities with highly distinctive language are medium-sized, and their loyal and highly engaged users interact in dense networks.
Fluctuation-response theorem for Kullback-Leibler divergences to quantify causation
Venue: arXiv cs.IT 2021
Year: 2021

We define a new measure of causation from a fluctuation-response theorem for Kullback-Leibler divergences, based on the information-theoretic cost of perturbations. This information response has both the invariance properties required for an information-theoretic measure and the physical interpretation of a propagation of perturbations. In linear systems, the information response reduces to the transfer entropy, providing a connection between Fisher and mutual information.
Distilling Double Descent
Venue: arXiv cs.LG 2021
Year: 2021

Distillation is the technique of training a "student" model based on examples that are labeled by a separate "teacher" model, which itself is trained on a labeled dataset. The most common explanations for why distillation "works" are predicated on the assumption that student is provided with \emph{soft} labels, \eg probabilities or confidences, from the teacher model. In this work, we show, that, even when the teacher model is highly overparameterized, and provides \emph{hard} labels, using a very large held-out unlabeled dataset to train the student model can result in a model that outperforms more "traditional" approaches. Our explanation for this phenomenon is based on recent work on "double descent". It has been observed that, once a model's complexity roughly exceeds the amount required to memorize the training data, increasing the complexity \emph{further} can, counterintuitively, result in \emph{better} generalization. Researchers have identified several settings in which it takes place, while others have made various attempts to explain it (thus far, with only partial success). In contrast, we avoid these questions, and instead seek to \emph{exploit} this phenomenon by demonstrating that a highly-overparameterized teacher can avoid overfitting via double descent, while a student trained on a larger independent dataset labeled by this teacher will avoid overfitting due to the size of its training set.
Sequential prediction under log-loss with side information
Venue: arXiv cs.IT 2021
Year: 2021

The problem of online prediction with sequential side information under logarithmic loss is studied, and general upper and lower bounds on the minimax regret incurred by the predictor is established. The upper bounds on the minimax regret are obtained by providing and analyzing a probability assignment inspired by mixture probability assignments in universal compression, and the lower bounds are obtained by way of a redundancy-capacity theorem. The tight characterization of the regret is provided in some special settings.
Adversarial Unsupervised Domain Adaptation Guided with Deep Clustering for Face Presentation Attack Detection
Venue: arXiv cs.CV 2021
Year: 2021

Face Presentation Attack Detection (PAD) has drawn increasing attentions to secure the face recognition systems that are widely used in many applications. Conventional face anti-spoofing methods have been proposed, assuming that testing is from the same domain used for training, and so cannot generalize well on unseen attack scenarios. The trained models tend to overfit to the acquisition sensors and attack types available in the training data. In light of this, we propose an end-to-end learning framework based on Domain Adaptation (DA) to improve PAD generalization capability. Labeled source-domain samples are used to train the feature extractor and classifier via cross-entropy loss, while unsupervised data from the target domain are utilized in adversarial DA approach causing the model to learn domain-invariant features. Using DA alone in face PAD fails to adapt well to target domain that is acquired in different conditions with different devices and attack types than the source domain. And so, in order to keep the intrinsic properties of the target domain, deep clustering of target samples is performed. Training and deep clustering are performed end-to-end, and experiments performed on several public benchmark datasets validate that our proposed Deep Clustering guided Unsupervised Domain Adaptation (DCDA) can learn more generalized information compared with the state-of-the-art classification error on the target domain.
Adaptive Synchronisation of Pushdown Automata
Venue: arXiv cs.FL 2021
Year: 2021

We introduce the notion of adaptive synchronisation for pushdown automata, in which there is an external observer who has no knowledge about the current state of the pushdown automaton, but can observe the contents of the stack. The observer would then like to decide if it is possible to bring the automaton from any state into some predetermined state by giving inputs to it in an \emph{adaptive} manner, i.e., the next input letter to be given can depend on how the contents of the stack changed after the current input letter. We show that for non-deterministic pushdown automata, this problem is 2-EXPTIME-complete and for deterministic pushdown automata, we show EXPTIME-completeness. To prove the lower bounds, we first introduce (different variants of) subset-synchronisation and show that these problems are polynomial-time equivalent with the adaptive synchronisation problem. We then prove hardness results for the subset-synchronisation problems. For proving the upper bounds, we consider the problem of deciding if a given alternating pushdown system has an accepting run with at most $k$ leaves and we provide an $n^{O(k^2)}$ time algorithm for this problem.
Modelling Cooperation in Network Games with Spatio-Temporal Complexity
Venue: arXiv cs.MA 2021
Year: 2021

The real world is awash with multi-agent problems that require collective action by self-interested agents, from the routing of packets across a computer network to the management of irrigation systems. Such systems have local incentives for individuals, whose behavior has an impact on the global outcome for the group. Given appropriate mechanisms describing agent interaction, groups may achieve socially beneficial outcomes, even in the face of short-term selfish incentives. In many cases, collective action problems possess an underlying graph structure, whose topology crucially determines the relationship between local decisions and emergent global effects. Such scenarios have received great attention through the lens of network games. However, this abstraction typically collapses important dimensions, such as geometry and time, relevant to the design of mechanisms promoting cooperation. In parallel work, multi-agent deep reinforcement learning has shown great promise in modelling the emergence of self-organized cooperation in complex gridworld domains. Here we apply this paradigm in graph-structured collective action problems. Using multi-agent deep reinforcement learning, we simulate an agent society for a variety of plausible mechanisms, finding clear transitions between different equilibria over time. We define analytic tools inspired by related literatures to measure the social outcomes, and use these to draw conclusions about the efficacy of different environmental interventions. Our methods have implications for mechanism design in both human and artificial agent systems.
Beamformer Design with Smooth Constraint-Free Approximation in Downlink Cloud Radio Access Networks
Venue: arXiv cs.IT 2021
Year: 2021

It is known that data rates in standard cellular networks are limited due to inter-cell interference. An effective solution of this problem is to use the multi-cell cooperation idea. In Cloud Radio Access Network, which is a candidate solution in 5G and beyond, cooperation is applied by means of central processors (CPs) connected to simple remote radio heads with finite capacity fronthaul links. In this study, we consider a downlink scenario and aim to minimize total power spent by designing beamformers. We consider the case where perfect channel state information is not available in the CP. The original problem includes discontinuous terms with many constraints. We propose a novel method which transforms the problem into a smooth constraint-free form and a solution is found by the gradient descent approach. As a comparison, we consider the optimal method solving an extensive number of convex sub-problems, a known heuristic search algorithm and some sparse solution techniques. Heuristic search methods find a solution by solving a subset of all possible convex sub-problems. Sparse techniques apply some norm approximation ($\ell_0/\ell_1, \ell_0/\ell_2$) or convex approximation to make the objective function more tractable. We also derive a theoretical performance bound in order to observe how far the proposed method performs off the optimal method when running the optimal method is prohibitive due to computational complexity. Detailed simulations show that the performance of the proposed method is close to the optimal one, and it outperforms other methods analyzed.
A Theoretical Performance Bound for Joint Beamformer Design of Wireless Fronthaul and Access Links in Downlink C-RAN
Venue: arXiv cs.IT 2021
Year: 2021

It is known that data rates in standard cellular networks are limited due to inter-cell interference. An effective solution of this problem is to use the multi-cell cooperation idea. In Cloud Radio Access Network (C-RAN), which is a candidate solution in 5G and future communication networks, cooperation is applied by means of central processors (CPs) connected to simple remote radio heads with finite capacity fronthaul links. In this study, we consider a downlink C-RAN with a wireless fronthaul and aim to minimize total power spent by jointly designing beamformers for fronthaul and access links. We consider the case where perfect channel state information is not available in the CP. We first derive a novel theoretical performance bound for the problem defined. Then we propose four algorithms with different complexities to show the tightness of the bound. The first two algorithms apply successive convex optimizations with semi-definite relaxation idea where other two are adapted from well-known beamforming design methods. The detailed simulations under realistic channel conditions show that as the complexity of the algorithm increases, the corresponding performance becomes closer to the bound.
Strong Call-by-Value is Reasonable, Implosively
Venue: arXiv cs.LO 2021
Year: 2021

Whether the number of beta-steps in the lambda-calculus can be taken as a reasonable time cost model (that is, polynomially related to the one of Turing machines) is a delicate problem, which depends on the notion of evaluation strategy. Since the nineties, it is known that weak (that is, out of abstractions) call-by-value evaluation is a reasonable strategy while Lévy's optimal parallel strategy, which is strong (that is, it reduces everywhere), is not. The strong case turned out to be subtler than the weak one. In 2014 Accattoli and Dal Lago have shown that strong call-by-name is reasonable, by introducing a new form of useful sharing and, later, an abstract machine with an overhead quadratic in the number of beta-steps. Here we show that also strong call-by-value evaluation is reasonable for time, via a new abstract machine realizing useful sharing and having a linear overhead. Moreover, our machine uses a new mix of sharing techniques, adding on top of useful sharing a form of implosive sharing, which on some terms brings an exponential speed-up. We give examples of families that the machine executes in time logarithmic in the number of beta-steps.
Optimal Streaming Algorithms for Graph Matching
Venue: arXiv cs.DS 2021
Year: 2021

We present parameterized streaming algorithms for the graph matching problem in both the dynamic and the insert-only models. For the dynamic streaming model, we present a one-pass algorithm that, with high probability, computes a maximum-weight $k$-matching of a weighted graph in $\tilde{O}(Wk^2)$ space and that has $\tilde{O}(1)$ update time, where $W$ is the number of distinct edge weights and the notation $\tilde{O}()$ hides a poly-logarithmic factor in the input size. For the insert-only streaming model, we present a one-pass algorithm that runs in $O(k^2)$ space and has $O(1)$ update time, and that, with high probability, computes a maximum-weight $k$-matching of a weighted graph. The space complexity and the update-time complexity achieved by our algorithms for unweighted $k$-matching in the dynamic model and for weighted $k$-matching in the insert-only model are optimal. A notable contribution of this paper is that the presented algorithms {\it do not} rely on the apriori knowledge/promise that the cardinality of \emph{every} maximum-weight matching of the input graph is upper bounded by the parameter $k$. This promise has been a critical condition in previous works, and lifting it required the development of new tools and techniques.
Impact of h-index on authors ranking: A comparative analysis of Scopus and WoS
Venue: arXiv cs.DL 2021
Year: 2021

In academia, the research performance of the faculty members is either evaluated by the number of publications or the number of citations. Most of the time h-index is widely used during the hiring process or the faculty performance evaluation. The calculation of the h-index is shown in various databases; however, there is no recent or systematic evidence about the differences between them. In this study, we compare the difference in the h-index compiled with Scopus and Web of Science (WoS) with the aim of analyzing the ranking of the authors within a university. We analyze the publication records of 350 authors from Monash University (Australia). We also investigate the discipline wise variation in the authors ranking. 31% of the author's profiles show no variation in the two datasets whereas 55% of the author's profiles show a higher count in Scopus and 9% in WoS. The maximum difference in h-index count among Scopus and WoS is 3. On average 12.4% of publications per author are unique in Scopus and 4.1% in WoS. 53.5% of publications are common in both Scopus and WoS. Despite larger unique publications in Scopus, there is no difference shown in the Spearman correlation coefficient between WoS and Scopus citation counts and h-index.
Almost-linear-time Weighted $\ell_p$-norm Solvers in Slightly Dense Graphs via Sparsification
Venue: arXiv cs.DS 2021
Year: 2021

We give almost-linear-time algorithms for constructing sparsifiers with $n\ poly(\log n)$ edges that approximately preserve weighted $(\ell^{2}_2 + \ell^{p}_p)$ flow or voltage objectives on graphs. For flow objectives, this is the first sparsifier construction for such mixed objectives beyond unit $\ell_p$ weights, and is based on expander decompositions. For voltage objectives, we give the first sparsifier construction for these objectives, which we build using graph spanners and leverage score sampling. Together with the iterative refinement framework of [Adil et al, SODA 2019], and a new multiplicative-weights based constant-approximation algorithm for mixed-objective flows or voltages, we show how to find $(1+2^{-\text{poly}(\log n)})$ approximations for weighted $\ell_p$-norm minimizing flows or voltages in $p(m^{1+o(1)} + n^{4/3 + o(1)})$ time for $p=ω(1),$ which is almost-linear for graphs that are slightly dense ($m \ge n^{4/3 + o(1)}$).
Discounting the Past
Venue: arXiv cs.GT 2021
Year: 2021

Stochastic games with discounted payoff, introduced by Shapley, model adversarial interactions in stochastic environments where two players try to optimize a discounted sum of rewards. In this model, long-term weights are geometrically attenuated based on the delay in their occurrence. We propose a temporally dual notion -- called past-discounting -- where agents have geometrically decaying memory of the rewards encountered during a play of the game. We study objective functions based on past-discounted weight sequences and examine the corresponding stochastic games with liminf, discounted, and mean payoffs. For objectives specified as the limit inferior of past-discounted reward sequences, we show that positional determinacy fails and that optimal strategies may require unbounded memory. To overcome this obstacle, we study an approximate windowed objective based on the idea of using sliding windows of finite length to examine infinite plays. On the other hand, for objectives specified as the discounted and average limits of past-discounted reward sequences we establish determinacy in mixed stationary strategies in the setting of concurrent stochastic games and show how the values of these games may be computed via reductions to standard discounted and mean-payoff games.
The first large scale collection of diverse Hausa language datasets
Venue: arXiv cs.CL 2021
Year: 2021

Hausa language belongs to the Afroasiatic phylum, and with more first-language speakers than any other sub-Saharan African language. With a majority of its speakers residing in the Northern and Southern areas of Nigeria and the Republic of Niger, respectively, it is estimated that over 100 million people speak the language. Hence, making it one of the most spoken Chadic language. While Hausa is considered well-studied and documented language among the sub-Saharan African languages, it is viewed as a low resource language from the perspective of natural language processing (NLP) due to limited resources to utilise in NLP-related tasks. This is common to most languages in Africa; thus, it is crucial to enrich such languages with resources that will support and speed the pace of conducting various downstream tasks to meet the demand of the modern society. While there exist useful datasets, notably from news sites and religious texts, more diversity is needed in the corpus. We provide an expansive collection of curated datasets consisting of both formal and informal forms of the language from refutable websites and online social media networks, respectively. The collection is large and more diverse than the existing corpora by providing the first and largest set of Hausa social media data posts to capture the peculiarities in the language. The collection also consists of a parallel dataset, which can be used for tasks such as machine translation with applications in areas such as the detection of spurious or inciteful online content. We describe the curation process -- from the collection, preprocessing and how to obtain the data -- and proffer some research problems that could be addressed using the data.
FaSTrack: a Modular Framework for Real-Time Motion Planning and Guaranteed Safe Tracking
Venue: arXiv cs.RO 2021
Year: 2021

Real-time, guaranteed safe trajectory planning is vital for navigation in unknown environments. However, real-time navigation algorithms typically sacrifice robustness for computation speed. Alternatively, provably safe trajectory planning tends to be too computationally intensive for real-time replanning. We propose FaSTrack, Fast and Safe Tracking, a framework that achieves both real-time replanning and guaranteed safety. In this framework, real-time computation is achieved by allowing any trajectory planner to use a simplified \textit{planning model} of the system. The plan is tracked by the system, represented by a more realistic, higher-dimensional \textit{tracking model}. We precompute the tracking error bound (TEB) due to mismatch between the two models and due to external disturbances. We also obtain the corresponding tracking controller used to stay within the TEB. The precomputation does not require prior knowledge of the environment. We demonstrate FaSTrack using Hamilton-Jacobi reachability for precomputation and three different real-time trajectory planners with three different tracking-planning model pairs.
Query-by-Example Keyword Spotting system using Multi-head Attention and Softtriple Loss
Venue: arXiv cs.CL 2021
Year: 2021

This paper proposes a neural network architecture for tackling the query-by-example user-defined keyword spotting task. A multi-head attention module is added on top of a multi-layered GRU for effective feature extraction, and a normalized multi-head attention module is proposed for feature aggregation. We also adopt the softtriple loss - a combination of triplet loss and softmax loss - and showcase its effectiveness. We demonstrate the performance of our model on internal datasets with different languages and the public Hey-Snips dataset. We compare the performance of our model to a baseline system and conduct an ablation study to show the benefit of each component in our architecture. The proposed work shows solid performance while preserving simplicity.
Costly Features Classification using Monte Carlo Tree Search
Venue: arXiv cs.LG 2021
Year: 2021

We consider the problem of costly feature classification, where we sequentially select the subset of features to make a balance between the classification error and the feature cost. In this paper, we first cast the task into a MDP problem and use Advantage Actor Critic algorithm to solve it. In order to further improve the agent's performance and make the policy explainable, we employ the Monte Carlo Tree Search to update the policy iteratively. During the procedure, we also consider its performance on the unbalanced dataset and its sensitivity to the missing value. We evaluate our model on multiple datasets and find it outperforms other methods.
IMF: Iterative Max-Flow for Node Localizability Detection in Barycentric Linear Localization
Venue: arXiv cs.NI 2021
Year: 2021

Determining whether nodes can be uniquely localized, called localizability detection, is a concomitant problem of network localization. Localizability under traditional Non-Linear Localization (NLL) schema has been well explored, whereas localizability under the emerging Barycentric coordinate-based Linear Localization (BLL) schema has not been well touched. In this paper, we investigate the deficiency of existing localizability theories and algorithms in BLL, and then propose a necessary condition and a sufficient condition for BLL node localizability. Based on these two conditions, an efficient iterative maximum flow (IMF) algorithm is designed to identify BLL localizable nodes. Finally, our algorithms are validated by both theoretical analysis and experimental evaluations.
Machine Learning Methods for the Design and Operation of Liquid Rocket Engines -- Research Activities at the DLR Institute of Space Propulsion
Venue: arXiv cs.LG 2021
Year: 2021

The last years have witnessed an enormous interest in the use of artificial intelligence methods, especially machine learning algorithms. This also has a major impact on aerospace engineering in general, and the design and operation of liquid rocket engines in particular, and research in this area is growing rapidly. The paper describes current machine learning applications at the DLR Institute of Space Propulsion. Not only applications in the field of modeling are presented, but also convincing results that prove the capabilities of machine learning methods for control and condition monitoring are described in detail. Furthermore, the advantages and disadvantages of the presented methods as well as current and future research directions are discussed.