OpenRaiser/Intern-Atlas huggingface dataset:
Personalized Federated Learning for Heterogeneous Clients with Clustered Knowledge Transfer
Venue: arXiv cs.LG 2021
Year: 2021

Personalized federated learning (FL) aims to train model(s) that can perform well for individual clients that are highly data and system heterogeneous. Most work in personalized FL, however, assumes using the same model architecture at all clients and increases the communication cost by sending/receiving models. This may not be feasible for realistic scenarios of FL. In practice, clients have highly heterogeneous system-capabilities and limited communication resources. In our work, we propose a personalized FL framework, PerFed-CKT, where clients can use heterogeneous model architectures and do not directly communicate their model parameters. PerFed-CKT uses clustered co-distillation, where clients use logits to transfer their knowledge to other clients that have similar data-distributions. We theoretically show the convergence and generalization properties of PerFed-CKT and empirically show that PerFed-CKT achieves high test accuracy with several orders of magnitude lower communication cost compared to the state-of-the-art personalized FL schemes.
Studying Up Machine Learning Data: Why Talk About Bias When We Mean Power?
Venue: arXiv cs.HC 2021
Year: 2021

Research in machine learning (ML) has primarily argued that models trained on incomplete or biased datasets can lead to discriminatory outputs. In this commentary, we propose moving the research focus beyond bias-oriented framings by adopting a power-aware perspective to "study up" ML datasets. This means accounting for historical inequities, labor conditions, and epistemological standpoints inscribed in data. We draw on HCI and CSCW work to support our argument, critically analyze previous research, and point at two co-existing lines of work within our community -- one bias-oriented, the other power-aware. This way, we highlight the need for dialogue and cooperation in three areas: data quality, data work, and data documentation. In the first area, we argue that reducing societal problems to "bias" misses the context-based nature of data. In the second one, we highlight the corporate forces and market imperatives involved in the labor of data workers that subsequently shape ML datasets. Finally, we propose expanding current transparency-oriented efforts in dataset documentation to reflect the social contexts of data design and production.
Efficient Decentralized Learning Dynamics for Extensive-Form Coarse Correlated Equilibrium: No Expensive Computation of Stationary Distributions Required
Venue: arXiv cs.GT 2021
Year: 2021

While in two-player zero-sum games the Nash equilibrium is a well-established prescriptive notion of optimal play, its applicability as a prescriptive tool beyond that setting is limited. Consequently, the study of decentralized learning dynamics that guarantee convergence to correlated solution concepts in multiplayer, general-sum extensive-form (i.e., tree-form) games has become an important topic of active research. The per-iteration complexity of the currently known learning dynamics depends on the specific correlated solution concept considered. For example, in the case of extensive-form correlated equilibrium (EFCE), all known dynamics require, as an intermediate step at each iteration, to compute the stationary distribution of multiple Markov chains, an expensive operation in practice. Oppositely, in the case of normal-form coarse correlated equilibrium (NFCCE), simple no-external-regret learning dynamics that amount to a linear-time traversal of the tree-form decision space of each agent suffice to guarantee convergence. This paper focuses on extensive-form coarse correlated equilibrium (EFCCE), an intermediate solution concept that is a subset of NFCCE and a superset of EFCE. Being a superset of EFCE, any learning dynamics for EFCE automatically guarantees convergence to EFCCE. However, since EFCCE is a simpler solution concept, this begs the question: do learning dynamics for EFCCE that avoid the expensive computation of stationary distributions exist? This paper answers the previous question in the positive. Our learning dynamics only require the orchestration of no-external-regret minimizers, thus showing that EFCCE is more akin to NFCCE than to EFCE from a learning perspective. Our dynamics guarantees that the empirical frequency of play after $T$ iteration is a $O(1/\sqrt{T})$-approximate EFCCE with high probability, and an EFCCE almost surely in the limit.
The Accuracy and Efficiency of Posit Arithmetic
Venue: arXiv cs.AR 2021
Year: 2021

Motivated by the increasing interest in the posit numeric format, in this paper we evaluate the accuracy and efficiency of posit arithmetic in contrast to the traditional IEEE 754 32-bit floating-point (FP32) arithmetic. We first design and implement a Posit Arithmetic Unit (PAU), called POSAR, with flexible bit-sized arithmetic suitable for applications that can trade accuracy for savings in chip area. Next, we analyze the accuracy and efficiency of POSAR with a series of benchmarks including mathematical computations, ML kernels, NAS Parallel Benchmarks (NPB), and Cifar-10 CNN. This analysis is done on our implementation of POSAR integrated into a RISC-V Rocket Chip core in comparison with the IEEE 754-based Floting Point Unit (FPU) of Rocket Chip. Our analysis shows that POSAR can outperform the FPU, but the results are not spectacular. For NPB, 32-bit posit achieves better accuracy than FP32 and improves the execution by up to 2%. However, POSAR with 32-bit posit needs 30% more FPGA resources compared to the FPU. For classic ML algorithms, we find that 8-bit posits are not suitable to replace FP32 because they exhibit low accuracy leading to wrong results. Instead, 16-bit posit offers the best option in terms of accuracy and efficiency. For example, 16-bit posit achieves the same Top-1 accuracy as FP32 on a Cifar-10 CNN with a speedup of 18%.
Inclusion and Exclusion Criteria in Software Engineering Tertiary Studies: A Systematic Mapping and Emerging Framework
Venue: arXiv cs.SE 2021
Year: 2021

Context: Tertiary studies in software engineering (TS@SE) are widely used to synthesise evidence on a research topic systematically. As part of their protocol, TS@SE define inclusion and exclusion criteria (IC/EC) aimed at selecting those secondary studies (SS) to be included in the analysis. Aims: To provide a state of the art on the definition and application of IC/EC in TS@SE, and from the results of this analysis, we outline an emerging framework, TSICEC, to be used by SE researchers. Method: To provide the state of the art, we conducted a systematic mapping (SM) combining automatic search and snowballing over the body of SE scientific literature, which led to 50 papers after application of our own IC/EC. The extracted data was synthesised using content analysis. The results were used to define a first version of TSICEC. Results: The SM resulted in a coding schema, and a thorough analysis of the selected papers on the basis of this coding. Our TSICEC framework includes guidelines for the definition of IC/EC in TS@SE. Conclusion: This paper is a step forward establishing a foundation for researchers in two ways. As authors, understanding the different possibilities to define IC/EC and apply them to select SS. As readers, having an instrument to understand the methodological rigor upon which TS@SE may claim their findings.
A computationally efficient framework for vector representation of persistence diagrams
Venue: arXiv cs.CV 2021
Year: 2021

In Topological Data Analysis, a common way of quantifying the shape of data is to use a persistence diagram (PD). PDs are multisets of points in $\mathbb{R}^2$ computed using tools of algebraic topology. However, this multi-set structure limits the utility of PDs in applications. Therefore, in recent years efforts have been directed towards extracting informative and efficient summaries from PDs to broaden the scope of their use for machine learning tasks. We propose a computationally efficient framework to convert a PD into a vector in $\mathbb{R}^n$, called a vectorized persistence block (VPB). We show that our representation possesses many of the desired properties of vector-based summaries such as stability with respect to input noise, low computational cost and flexibility. Through simulation studies, we demonstrate the effectiveness of VPBs in terms of performance and computational cost within various learning tasks, namely clustering, classification and change point detection.
A Note on Occur-Check
Venue: arXiv cs.LO 2021
Year: 2021

Most known results on avoiding the occur-check are based on the notion of "not subject to occur-check" (NSTO). It means that unification is performed only on such pairs of atoms for which the occur-check never succeeds in any run of a nondeterministic unification algorithm. Here we show that this requirement is too strong. We show how to weaken it, and present some related sufficient conditions under which the occur-check may be safely omitted. We show examples for which the proposed approach provides more general results than the approaches based on well-moded and nicely moded programs (this includes cases to which the latter approaches are inapplicable).
Generating Concurrent Programs From Sequential Data Structure Knowledge Using Answer Set Programming
Venue: arXiv cs.PL 2021
Year: 2021

We tackle the problem of automatically designing concurrent data structure operations given a sequential data structure specification and knowledge about concurrent behavior. Designing concurrent code is a non-trivial task even in simplest of cases. Humans often design concurrent data structure operations by transforming sequential versions into their respective concurrent versions. This requires an understanding of the data structure, its sequential behavior, thread interactions during concurrent execution and shared memory synchronization primitives. We mechanize this design process using automated commonsense reasoning. We assume that the data structure description is provided as axioms alongside the sequential code of its algebraic operations. This information is used to automatically derive concurrent code for that data structure, such as dictionary operations for linked lists and binary search trees. Knowledge in our case is expressed using Answer Set Programming (ASP), and we employ deduction and abduction -- just as humans do -- in the reasoning involved. ASP allows for succinct modeling of first order theories of pointer data structures, run-time thread interactions and shared memory synchronization. Our reasoner can systematically make the same judgments as a human reasoner, while constructing provably safe concurrent code. We present several reasoning challenges involved in transforming the sequential data structure into its equivalent concurrent version. All the reasoning tasks are encoded in ASP and our reasoner can make sound judgments to transform sequential code into concurrent code. To the best of our knowledge, our work is the first one to use commonsense reasoning to automatically transform sequential programs into concurrent code. We also have developed a tool that we describe that relies on state-of-the-art ASP solvers and performs the reasoning tasks involved to generate concurrent code.
Flexible and Explainable Solutions for Multi-Agent Path Finding Problems
Venue: arXiv cs.AI 2021
Year: 2021

The multi-agent path finding (MAPF) problem is a combinatorial search problem that aims at finding paths for multiple agents (e.g., robots) in an environment (e.g., an autonomous warehouse) such that no two agents collide with each other, and subject to some constraints on the lengths of paths. The real-world applications of MAPF require flexibility (e.g., solving variations of MAPF) as well as explainability. In this study, both of these challenges are addressed and some flexible and explainable solutions for MAPF and its variants are introduced.
Compilation of Aggregates in ASP
Venue: arXiv cs.LO 2021
Year: 2021

Answer Set Programming (ASP) is a well-known problem-solving formalism in computational logic. Nowadays, ASP is used in many real world scenarios thanks to ASP solvers. Standard evaluation of ASP programs suffers from an intrinsic limitation, knows as Grounding Bottleneck, due to the grounding of some rules that could fit all the available memory. As a result, there exist instances of real world problems that are untractable using the standard Ground and Solve approach. In order to tackle this problem, different strategies have been proposed. Among them we focus on a recent approach based on compilation of problematic constraints as propagators, which revealed to be very promising but is currently limited to constraints without aggregates. Since aggregates are widely used in ASP, in this paper we extend such an approach also to constraints containing aggregates. Good results, that proof the effectiveness of the proposed approach, have been reached.
The Optimal Way to Play the Most Difficult Repeated Coordination Games
Venue: arXiv cs.GT 2021
Year: 2021

This paper investigates repeated win-lose coordination games (WLC-games). We analyse which protocols are optimal for these games, covering both the worst case and average case scenarios, i,e., optimizing the guaranteed and expected coordination times. We begin by analysing Choice Matching Games (CM-games) which are a simple yet fundamental type of WLC-games, where the goal of the players is to pick the same choice from a finite set of initially indistinguishable choices. We give a fully complete classification of optimal expected and guaranteed coordination times in two-player CM-games and show that the corresponding optimal protocols are unique in every case - except in the CM-game with four choices, which we analyse separately. Our results on CM-games are essential for proving a more general result on the difficulty of all WLC-games: we provide a complete analysis of least upper bounds for optimal expected coordination times in all two-player WLC-games as a function of game size. We also show that CM-games can be seen as the most difficult games among all two-player WLC-games, as they turn out to have the greatest optimal expected coordination times.
New Algorithms for Combinations of Objectives using Separating Automata
Venue: arXiv cs.GT 2021
Year: 2021

The notion of separating automata was introduced by Bojanczyk and Czerwinski for understanding the first quasipolynomial time algorithm for parity games. In this paper we show that separating automata is a powerful tool for constructing algorithms solving games with combinations of objectives. We construct two new algorithms: the first for disjunctions of parity and mean payoff objectives, matching the best known complexity, and the second for disjunctions of mean payoff objectives, improving on the state of the art. In both cases the algorithms are obtained through the construction of small separating automata, using as black boxes the existing constructions for parity objectives and for mean payoff objectives.
Games for Succinctness of Regular Expressions
Venue: arXiv cs.LO 2021
Year: 2021

We present a version of so called formula size games for regular expressions. These games characterize the equivalence of languages up to expressions of a given size. We use the regular expression size game to give a simple proof of a known non-elementary succinctness gap between first-order logic and regular expressions. We also use the game to only count the number of stars in an expression instead of the overall size. For regular expressions this measure trivially gives a hierarchy in terms of expressive power. We obtain such a hierarchy also for what we call RE over star-free expressions, where star-free expressions, that is ones with complement but no stars, are combined using the operations of regular expressions.
Cross-layer Visualization and Profiling of Network and I/O Communication for HPC Clusters
Venue: arXiv cs.GR 2021
Year: 2021

Understanding and visualizing the full-stack performance trade-offs and interplay between HPC applications, MPI libraries, the communication fabric, and the file system is a challenging endeavor. Designing a holistic profiling and visualization method for HPC communication networks is challenging since different levels of communication coexist and interact with each other on the communication fabric. A breakdown of traffic is essential to understand the interplay of different layers along with the application's communication behavior without losing a general view of network traffic. Unfortunately, existing profiling tools are disjoint and either focus on only profiling and visualizing a few levels of the HPC stack, which limits the insights they can provide, or they provide extremely detailed information which necessitates a steep learning curve to understand. We target our profiling tool visualization to provide holistic and real-time insights into HPC communication stacks. In this paper, we propose and implement our visualization methods to enable holistic insight for representing the cross-stack metrics. Moreover, we propose and implement a low-overhead I/O profiling inside the communication library, collect and store the profiling information, and then study the correlation and evaluation of I/O traffic with MPI communication using a cross-stack approach by INAM. Through experimental evaluations and use cases, we demonstrate novel benefits of our cross-stack communication analysis in real-time to detect bottlenecks and understand communication performance.
THyMe+: Temporal Hypergraph Motifs and Fast Algorithms for Exact Counting
Venue: arXiv cs.SI 2021
Year: 2021

Group interactions arise in our daily lives (email communications, on-demand ride sharing, comment interactions on online communities, to name a few), and they together form hypergraphs that evolve over time. Given such temporal hypergraphs, how can we describe their underlying design principles? If their sizes and time spans are considerably different, how can we compare their structural and temporal characteristics? In this work, we define 96 temporal hypergraph motifs (TH-motifs), and propose the relative occurrences of their instances as an answer to the above questions. TH-motifs categorize the relational and temporal dynamics among three connected hyperedges that appear within a short time. For scalable analysis, we develop THyMe+, a fast and exact algorithm for counting the instances of TH-motifs in massive hypergraphs, and show that THyMe+ is at most 2,163X faster while requiring less space than baseline. Using it, we investigate 11 real-world temporal hypergraphs from various domains. We demonstrate that TH-motifs provide important information useful for downstream tasks and reveal interesting patterns, including the striking similarity between temporal hypergraphs from the same domain.
An Interpretable Framework for Drug-Target Interaction with Gated Cross Attention
Venue: arXiv cs.LG 2021
Year: 2021

In silico prediction of drug-target interactions (DTI) is significant for drug discovery because it can largely reduce timelines and costs in the drug development process. Specifically, deep learning-based DTI approaches have been shown promising results in terms of accuracy and low cost for the prediction. However, they pay little attention to the interpretability of their prediction results and feature-level interactions between a drug and a target. In this study, we propose a novel interpretable framework that can provide reasonable cues for the interaction sites. To this end, we elaborately design a gated cross-attention mechanism that crossly attends drug and target features by constructing explicit interactions between these features. The gating function in the method enables neural models to focus on salient regions over entire sequences of drugs and proteins, and the byproduct from the function, which is the attention map, could serve as interpretable factors. The experimental results show the efficacy of the proposed method in two DTI datasets. Additionally, we show that gated cross-attention can sensitively react to the mutation, and this result could provide insights into the identification of novel drugs targeting mutant proteins.
Robust Trajectory Planning for Spatial-Temporal Multi-Drone Coordination in Large Scenes
Venue: arXiv cs.RO 2021
Year: 2021

In this paper, we describe a robust multi-drone planning framework for high-speed trajectories in large scenes. It uses a free-space-oriented map to free the optimization from cumbersome environment data. A capsule-like safety constraint is designed to avoid reciprocal collisions when vehicles deviate from their nominal flight progress under disturbance. We further show the minimum-singularity differential flatness of our drone dynamics with nonlinear drag effects involved. Leveraging the flatness map, trajectory optimization is efficiently conducted on the flat outputs while still subject to physical limits considering drag forces at high speeds. The robustness and effectiveness of our framework are both validated in large-scale simulations. It can compute collision-free trajectories satisfying high-fidelity vehicle constraints for hundreds of drones in a few minutes.
Heterogeneous download times in bandwidth-homogeneous BitTorrent swarms
Venue: arXiv cs.NI 2021
Year: 2021

Modeling and understanding BitTorrent (BT) dynamics is a recurrent research topic mainly due to its high complexity and tremendous practical efficiency. Over the years, different models have uncovered various phenomena exhibited by the system, many of which have direct impact on its performance. In this paper we identify and characterize a phenomenon that has not been previously observed: homogeneous peers (with respect to their upload capacities) experience heterogeneous download times. This behavior has direct impact on peer and system performance, such as high variability of download times, unfairness with respect to peer arrival order, bursty departures and content synchronization. Detailed packet-level simulations and prototype-based experiments on the Internet were performed to characterize this phenomenon. We also develop a mathematical model that accurately predicts the heterogeneous download rates of the homogeneous peers as a function of their content. In addition, we apply the model to calculate lower and upper bounds to the number of departures that occur in a burst. The heterogeneous download rates are more prevalent in unpopular swarms (very few peers). Although few works have addressed this kind of swarm, these by far represent the most common type of swarm in BT.
What we see and What we don't see: Imputing Occluded Crowd Structures from Robot Sensing
Venue: arXiv cs.RO 2021
Year: 2021

We consider the navigation of mobile robots in crowded environments, for which onboard sensing of the crowd is typically limited by occlusions. We address the problem of inferring the human occupancy in the space around the robot, in blind spots, beyond the range of its sensing capabilities. This problem is rather unexplored in spite of the important impact it has on the robot crowd navigation efficiency and safety, which requires the estimation and the prediction of the crowd state around it. In this work, we propose the first solution to sample predictions of possible human presence based on the state of a fewer set of sensed people around the robot as well as previous observations of the crowd activity.