OpenRaiser/Intern-Atlas huggingface dataset:
Embedding Alignment for Unsupervised Federated Learning via Smart Data Exchange
Venue: arXiv cs.LG 2022
Year: 2022

Federated learning (FL) has been recognized as one of the most promising solutions for distributed machine learning (ML). In most of the current literature, FL has been studied for supervised ML tasks, in which edge devices collect labeled data. Nevertheless, in many applications, it is impractical to assume existence of labeled data across devices. To this end, we develop a novel methodology, Cooperative Federated unsupervised Contrastive Learning (CF-CL), for FL across edge devices with unlabeled datasets. CF-CL employs local device cooperation where data are exchanged among devices through device-to-device (D2D) communications to avoid local model bias resulting from non-independent and identically distributed (non-i.i.d.) local datasets. CF-CL introduces a push-pull smart data sharing mechanism tailored to unsupervised FL settings, in which, each device pushes a subset of its local datapoints to its neighbors as reserved data points, and pulls a set of datapoints from its neighbors, sampled through a probabilistic importance sampling technique. We demonstrate that CF-CL leads to (i) alignment of unsupervised learned latent spaces across devices, (ii) faster global convergence, allowing for less frequent global model aggregations; and (iii) is effective in extreme non-i.i.d. data settings across the devices.
Creative Wand: A System to Study Effects of Communications in Co-Creative Settings
Venue: arXiv cs.AI 2022
Year: 2022

Recent neural generation systems have demonstrated the potential for procedurally generating game content, images, stories, and more. However, most neural generation algorithms are "uncontrolled" in the sense that the user has little say in creative decisions beyond the initial prompt specification. Co-creative, mixed-initiative systems require user-centric means of influencing the algorithm, especially when users are unlikely to have machine learning expertise. The key to co-creative systems is the ability to communicate ideas and intent from the user to the agent, as well as from the agent to the user. Key questions in co-creative AI include: How can users express their creative intentions? How can creative AI systems communicate their beliefs, explain their moves, or instruct users to act on their behalf? When should creative AI systems take initiative? The answer to such questions and more will enable us to develop better co-creative systems that make humans more capable of expressing their creative intents. We introduce CREATIVE-WAND, a customizable framework for investigating co-creative mixed-initiative generation. CREATIVE-WAND enables plug-and-play injection of generative models and human-agent communication channels into a chat-based interface. It provides a number of dimensions along which an AI generator and humans can communicate during the co-creative process. We illustrate the CREATIVE-WAND framework by using it to study one dimension of co-creative communication-global versus local creative intent specification by the user-in the context of storytelling.
Interpretable Distribution Shift Detection using Optimal Transport
Venue: arXiv cs.LG 2022
Year: 2022

We propose a method to identify and characterize distribution shifts in classification datasets based on optimal transport. It allows the user to identify the extent to which each class is affected by the shift, and retrieves corresponding pairs of samples to provide insights on its nature. We illustrate its use on synthetic and natural shift examples. While the results we present are preliminary, we hope that this inspires future work on interpretable methods for analyzing distribution shifts.
Solving the Baby Intuitions Benchmark with a Hierarchically Bayesian Theory of Mind
Venue: arXiv cs.AI 2022
Year: 2022

To facilitate the development of new models to bridge the gap between machine and human social intelligence, the recently proposed Baby Intuitions Benchmark (arXiv:2102.11938) provides a suite of tasks designed to evaluate commonsense reasoning about agents' goals and actions that even young infants exhibit. Here we present a principled Bayesian solution to this benchmark, based on a hierarchically Bayesian Theory of Mind (HBToM). By including hierarchical priors on agent goals and dispositions, inference over our HBToM model enables few-shot learning of the efficiency and preferences of an agent, which can then be used in commonsense plausibility judgements about subsequent agent behavior. This approach achieves near-perfect accuracy on most benchmark tasks, outperforming deep learning and imitation learning baselines while producing interpretable human-like inferences, demonstrating the advantages of structured Bayesian models of human social cognition.
Offensive Alliances in Graphs
Venue: arXiv cs.DS 2022
Year: 2022

A set $S\subseteq V$ of vertices is an offensive alliance in an undirected graph $G=(V,E)$ if each $v\in N(S)$ has at least as many neighbours in $S$ as it has neighbours (including itself) not in $S$. We study the classical and parameterized complexity of the Offensive Alliance problem, where the aim is to find a minimum size offensive alliance. Our focus here lies on natural parameter as well as parameters that measure the structural properties of the input instance. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, treewidth, pathwidth, and treedepth of the input graph; we thereby resolve an open question stated by Bernhard Bliem and Stefan Woltran (2018) concerning the complexity of Offensive Alliance parameterized by treewidth, (2) unless ETH fails, Offensive Alliance problem cannot be solved in time $\mathcal{O}^{*}(2^{o(k \log k)})$ where $k$ is the solution size, (3) Offensive Alliance problem does not admit a polynomial kernel parameterized by solution size and vertex cover of the input graph. On the positive side we prove that (4) Offensive Alliance can be solved in time $\mathcal{O}^{*}(\tt{vc(G)}^{\mathcal{O}(\tt{vc(G)})})$ where $\tt{vc(G)}$ is the vertex cover number of the input graph. In terms of classical complexity, we prove that (5) Offensive Alliance problem cannot be solved in time $2^{o(n)}$ even when restricted to bipartite graphs, unless ETH fails, (6) Offensive Alliance problem cannot be solved in time $2^{o(\sqrt{n})}$ even when restricted to apex graphs, unless ETH fails. We also prove that (7) Offensive Alliance problem is NP-complete even when restricted to bipartite, chordal, split and circle graphs.
A Cooperation Graph Approach for Multiagent Sparse Reward Reinforcement Learning
Venue: arXiv cs.AI 2022
Year: 2022

Multiagent reinforcement learning (MARL) can solve complex cooperative tasks. However, the efficiency of existing MARL methods relies heavily on well-defined reward functions. Multiagent tasks with sparse reward feedback are especially challenging not only because of the credit distribution problem, but also due to the low probability of obtaining positive reward feedback. In this paper, we design a graph network called Cooperation Graph (CG). The Cooperation Graph is the combination of two simple bipartite graphs, namely, the Agent Clustering subgraph (ACG) and the Cluster Designating subgraph (CDG). Next, based on this novel graph structure, we propose a Cooperation Graph Multiagent Reinforcement Learning (CG-MARL) algorithm, which can efficiently deal with the sparse reward problem in multiagent tasks. In CG-MARL, agents are directly controlled by the Cooperation Graph. And a policy neural network is trained to manipulate this Cooperation Graph, guiding agents to achieve cooperation in an implicit way. This hierarchical feature of CG-MARL provides space for customized cluster-actions, an extensible interface for introducing fundamental cooperation knowledge. In experiments, CG-MARL shows state-of-the-art performance in sparse reward multiagent benchmarks, including the anti-invasion interception task and the multi-cargo delivery task.
A Preliminary Data-driven Analysis of Common Errors Encountered by Novice SPARC Programmers
Venue: arXiv cs.CY 2022
Year: 2022

Answer Set Programming (ASP), a modern development of Logic Programming, enables a natural integration of Computing with STEM subjects. This integration addresses a widely acknowledged challenge in K-12 education, and early empirical results on ASP-based integration are promising. Although ASP is considered a simple language when compared with imperative programming languages, programming errors can still be a significant barrier for students. This is particularly true for K-12 students who are novice users of ASP. Categorizing errors and measuring their difficulty has yielded insights into imperative languages like Java. However, little is known about the types and difficulty of errors encountered by K-12 students using ASP. To address this, we collected high school student programs submitted during a 4-session seminar teaching an ASP language known as SPARC. From error messages in this dataset, we identify a collection of error classes, and measure how frequently each class occurs and how difficult it is to resolve.
A Design of Low-Projection SCMA Codebooks for Ultra-Low Decoding Complexity in Downlink IoT Networks
Venue: arXiv cs.IT 2022
Year: 2022

This paper conceives a novel sparse code multiple access (SCMA) codebook design which is motivated by the strong need for providing ultra-low decoding complexity and good error performance in downlink Internet-of-things (IoT) networks, in which a massive number of low-end and low-cost IoT communication devices are served. By focusing on the typical Rician fading channels, we analyze the pair-wise probability of superimposed SCMA codewords and then deduce the design metrics for multi-dimensional constellation construction and sparse codebook optimization. For significant reduction of the decoding complexity, we advocate the key idea of projecting the multi-dimensional constellation elements to a few overlapped complex numbers in each dimension, called low projection (LP). An emerging modulation scheme, called golden angle modulation (GAM), is considered for multi-stage LP optimization, where the resultant multi-dimensional constellation is called LP-GAM. Our analysis and simulation results show the superiority of the proposed LP codebooks (LPCBs) including one-shot decoding convergence and excellent error rate performance. In particular, the proposed LPCBs lead to decoding complexity reduction by at least $97\%$ compared to that of the conventional codebooks, whilst owning large minimum Euclidean distance. Some examples of the proposed LPCBs are available at \url{https://github.com/ethanlq/SCMA-codebook}.
Asymptotically consistent and computationally efficient modeling of short-ranged molecular interactions between curved slender fibers undergoing large 3D deformations
Venue: arXiv cs.CE 2022
Year: 2022

This article proposes a novel computational modeling approach for short-ranged molecular interactions between curved slender fibers undergoing large 3D deformations, and gives a detailed overview how it fits into the framework of existing fiber or beam interaction models, either considering microscale molecular or macroscale contact effects. The direct evaluation of a molecular interaction potential between two general bodies in 3D space would require to integrate molecule densities over two 3D volumes, leading to a sixfold integral to be solved numerically. By exploiting the short-range nature of the considered class of interaction potentials as well as the fundamental kinematic assumption of undeformable fiber cross-sections, as typically applied in mechanical beam theories, a recently derived, closed-form analytical solution is applied for the interaction potential between a given section of the first fiber (slave beam) and the entire second fiber (master beam). This novel approach based on a pre-defined section-beam interaction potential (SBIP) requires only one single integration step along the slave beam length to be performed numerically. In terms of accuracy, the total beam-beam interaction potential resulting from this approach is shown to exhibit an asymptotically consistent angular and distance scaling behavior. In addition to elementary two-fiber systems, carefully chosen to verify accuracy and asymptotic consistence of the proposed SBIP approach, a potential practical application in form of adhesive nanofiber-grafted surfaces is studied. Involving a large number of helicoidal fibers undergoing large 3D deformations, arbitrary mutual fiber orientations as well as frequent local fiber pull-off and snap-into-contact events, this example demonstrates the robustness and computational efficiency of the new approach.
Hardless: A Generalized Serverless Compute Architecture for Hardware Processing Accelerators
Venue: arXiv cs.DC 2022
Year: 2022

The increasing use of hardware processing accelerators tailored for specific applications, such as the Vision Processing Unit (VPU) for image recognition, further increases developers' configuration, development, and management overhead. Developers have successfully used fully automated elastic cloud services such as serverless computing to counter these additional efforts and shorten development cycles for applications running on CPUs. Unfortunately, current cloud solutions do not yet provide these simplifications for applications that require hardware acceleration. However, as the development of specialized hardware acceleration continues to provide performance and cost improvements, it will become increasingly important to enable ease of use in the cloud. In this paper, we present an initial design and implementation of Hardless, an extensible and generalized serverless computing architecture that can support workloads for arbitrary hardware accelerators. We show how Hardless can scale across different commodity hardware accelerators and support a variety of workloads using the same execution and programming model common in serverless computing today.
Low-Resource Dense Retrieval for Open-Domain Question Answering: A Comprehensive Survey
Venue: arXiv cs.CL 2022
Year: 2022

Dense retrieval (DR) approaches based on powerful pre-trained language models (PLMs) achieved significant advances and have become a key component for modern open-domain question-answering systems. However, they require large amounts of manual annotations to perform competitively, which is infeasible to scale. To address this, a growing body of research works have recently focused on improving DR performance under low-resource scenarios. These works differ in what resources they require for training and employ a diverse set of techniques. Understanding such differences is crucial for choosing the right technique under a specific low-resource scenario. To facilitate this understanding, we provide a thorough structured overview of mainstream techniques for low-resource DR. Based on their required resources, we divide the techniques into three main categories: (1) only documents are needed; (2) documents and questions are needed; and (3) documents and question-answer pairs are needed. For every technique, we introduce its general-form algorithm, highlight the open issues and pros and cons. Promising directions are outlined for future research.
Improving Task Generalization via Unified Schema Prompt
Venue: arXiv cs.CL 2022
Year: 2022

Task generalization has been a long standing challenge in Natural Language Processing (NLP). Recent research attempts to improve the task generalization ability of pre-trained language models by mapping NLP tasks into human-readable prompted forms. However, these approaches require laborious and inflexible manual collection of prompts, and different prompts on the same downstream task may receive unstable performance. We propose Unified Schema Prompt, a flexible and extensible prompting method, which automatically customizes the learnable prompts for each task according to the task input schema. It models the shared knowledge between tasks, while keeping the characteristics of different task schema, and thus enhances task generalization ability. The schema prompt takes the explicit data structure of each task to formulate prompts so that little human effort is involved. To test the task generalization ability of schema prompt at scale, we conduct schema prompt-based multitask pre-training on a wide variety of general NLP tasks. The framework achieves strong zero-shot and few-shot generalization performance on 16 unseen downstream tasks from 8 task types (e.g., QA, NLI, etc). Furthermore, comprehensive analyses demonstrate the effectiveness of each component in the schema prompt, its flexibility in task compositionality, and its ability to improve performance under a full-data fine-tuning setting.
Learning programs with magic values
Venue: arXiv cs.LG 2022
Year: 2022

A magic value in a program is a constant symbol that is essential for the execution of the program but has no clear explanation for its choice. Learning programs with magic values is difficult for existing program synthesis approaches. To overcome this limitation, we introduce an inductive logic programming approach to efficiently learn programs with magic values. Our experiments on diverse domains, including program synthesis, drug design, and game playing, show that our approach can (i) outperform existing approaches in terms of predictive accuracies and learning times, (ii) learn magic values from infinite domains, such as the value of pi, and (iii) scale to domains with millions of constant symbols.
Atlas: Few-shot Learning with Retrieval Augmented Language Models
Venue: arXiv cs.CL 2022
Year: 2022

Large language models have shown impressive few-shot results on a wide range of tasks. However, when knowledge is key for such results, as is the case for tasks such as question answering and fact checking, massive parameter counts to store knowledge seem to be needed. Retrieval augmented models are known to excel at knowledge intensive tasks without the need for as many parameters, but it is unclear whether they work in few-shot settings. In this work we present Atlas, a carefully designed and pre-trained retrieval augmented language model able to learn knowledge intensive tasks with very few training examples. We perform evaluations on a wide range of tasks, including MMLU, KILT and NaturalQuestions, and study the impact of the content of the document index, showing that it can easily be updated. Notably, Atlas reaches over 42% accuracy on Natural Questions using only 64 examples, outperforming a 540B parameters model by 3% despite having 50x fewer parameters.
Going Beyond Approximation: Encoding Constraints for Explainable Multi-hop Inference via Differentiable Combinatorial Solvers
Venue: arXiv cs.AI 2022
Year: 2022

Integer Linear Programming (ILP) provides a viable mechanism to encode explicit and controllable assumptions about explainable multi-hop inference with natural language. However, an ILP formulation is non-differentiable and cannot be integrated into broader deep learning architectures. Recently, Thayaparan et al. (2021a) proposed a novel methodology to integrate ILP with Transformers to achieve end-to-end differentiability for complex multi-hop inference. While this hybrid framework has been demonstrated to deliver better answer and explanation selection than transformer-based and existing ILP solvers, the neuro-symbolic integration still relies on a convex relaxation of the ILP formulation, which can produce sub-optimal solutions. To improve these limitations, we propose Diff-Comb Explainer, a novel neuro-symbolic architecture based on Differentiable BlackBox Combinatorial solvers (DBCS) (Pogančić et al., 2019). Unlike existing differentiable solvers, the presented model does not require the transformation and relaxation of the explicit semantic constraints, allowing for direct and more efficient integration of ILP formulations. Diff-Comb Explainer demonstrates improved accuracy and explainability over non-differentiable solvers, Transformers and existing differentiable constraint-based multi-hop inference frameworks.
Blockchain in Dynamic Networks
Venue: arXiv cs.DC 2022
Year: 2022

We consider blockchain in dynamic networks. We define the Blockchain Decision Problem. It requires miners that maintain the blockchain to confirm whether a particular block is accepted. We establish the necessary conditions for the existence of a solution. We, however, prove that the solution, even under these necessary conditions is, in general, impossible. We then present two algorithms that solve the Blockchain Decision Problem under either the knowledge of the maximum source pool propagation time or the knowledge of the source pool membership. We evaluate the performance of the two algorithms.
An Overview of Structural Coverage Metrics for Testing Neural Networks
Venue: arXiv cs.SE 2022
Year: 2022

Deep neural network (DNN) models, including those used in safety-critical domains, need to be thoroughly tested to ensure that they can reliably perform well in different scenarios. In this article, we provide an overview of structural coverage metrics for testing DNN models, including neuron coverage (NC), k-multisection neuron coverage (kMNC), top-k neuron coverage (TKNC), neuron boundary coverage (NBC), strong neuron activation coverage (SNAC) and modified condition/decision coverage (MC/DC). We evaluate the metrics on realistic DNN models used for perception tasks (including LeNet-1, LeNet-4, LeNet-5, and ResNet20) as well as on networks used in autonomy (TaxiNet). We also provide a tool, DNNCov, which can measure the testing coverage for all these metrics. DNNCov outputs an informative coverage report to enable researchers and practitioners to assess the adequacy of DNN testing, compare different coverage measures, and to more conveniently inspect the model's internals during testing.
PC-Expo: A Metrics-Based Interactive Axes Reordering Method for Parallel Coordinate Displays
Venue: arXiv cs.GR 2022
Year: 2022

The axes ordering in PCP presents a particular story from the data based on the user perception of PCP polylines. Existing works focus on directly optimizing for PCP axes ordering based on some common analysis tasks like clustering, neighborhood, and correlation. However, direct optimization for PCP axes based on these common properties is restrictive because it does not account for multiple properties occurring between the axes, and for local properties that occur in small regions in the data. Also, many of these techniques do not support the human-in-the-loop (HIL) paradigm, which is crucial (i) for explainability and (ii) in cases where no single reordering scheme fits the user goals. To alleviate these problems, we present PC-Expo, a real-time visual analytics framework for all-in-one PCP line pattern detection, and axes reordering. We studied the connection of line patterns in PCPs with different data analysis tasks and datasets. PC-Expo expands prior work on PCP axes reordering by developing real-time, local detection schemes for the 12 most common analysis tasks (properties). Users can choose the story they want to present with PCPs by optimizing directly over their choice of properties. These properties can be ranked, or combined using individual weights, creating a custom optimization scheme for axes reordering. Users can control the granularity at which they want to work with their detection scheme in the data, allowing exploration of local regions. PC-Expo also supports HIL axes reordering via local-property visualization, which shows the regions of granular activity for every axis pair. Local-property visualization is helpful for PCP axes reordering based on multiple properties, when no single reordering scheme fits the user goals.