OpenRaiser/Intern-Atlas huggingface dataset:
"Is it a Qoincidence?": An Exploratory Study of QAnon on Voat
Venue: arXiv cs.CY 2021
Year: 2021

Online fringe communities offer fertile grounds for users seeking and sharing ideas fueling suspicion of mainstream news and conspiracy theories. Among these, the QAnon conspiracy theory emerged in 2017 on 4chan, broadly supporting the idea that powerful politicians, aristocrats, and celebrities are closely engaged in a global pedophile ring. Simultaneously, governments are thought to be controlled by "puppet masters," as democratically elected officials serve as a fake showroom of democracy. This paper provides an empirical exploratory analysis of the QAnon community on Voat.co, a Reddit-esque news aggregator, which has captured the interest of the press for its toxicity and for providing a platform to QAnon followers. More precisely, we analyze a large dataset from /v/GreatAwakening, the most popular QAnon-related subverse (the Voat equivalent of a subreddit), to characterize activity and user engagement. To further understand the discourse around QAnon, we study the most popular named entities mentioned in the posts, along with the most prominent topics of discussion, which focus on US politics, Donald Trump, and world events. We also use word embeddings to identify narratives around QAnon-specific keywords. Our graph visualization shows that some of the QAnon-related ones are closely related to those from the Pizzagate conspiracy theory and so-called drops by "Q." Finally, we analyze content toxicity, finding that discussions on /v/GreatAwakening are less toxic than in the broad Voat community.
News Recommender System: A review of recent progress, challenges, and opportunities
Venue: arXiv cs.IR 2021
Year: 2021

Nowadays, more and more news readers tend to read news online where they have access to millions of news articles from multiple sources. In order to help users to find the right and relevant content, news recommender systems (NRS) are developed to relieve the information overload problem and suggest news items that users might be interested in. In this paper, we highlight the major challenges faced by the news recommendation domain and identify the possible solutions from the state-of-the-art. Due to the rapid growth of building recommender systems using deep learning models, we divide our discussion in two parts. In the first part, we present an overview of the conventional recommendation solutions, datasets, evaluation criteria beyond accuracy and recommendation platforms being used in NRS. In the second part, we explain the deep learning-based recommendation solutions applied in NRS. Different from previous surveys, we also study the effects of news recommendations on user behavior and try to suggest the possible remedies to mitigate these effects. By providing the state-of-the-art knowledge, this survey can help researchers and practical professionals in their understanding of developments in news recommendation algorithms. It also sheds light on potential new directions
Quick Streaming Algorithms for Maximization of Monotone Submodular Functions in Linear Time
Venue: arXiv cs.DS 2021
Year: 2021

We consider the problem of monotone, submodular maximization over a ground set of size $n$ subject to cardinality constraint $k$. For this problem, we introduce the first deterministic algorithms with linear time complexity; these algorithms are streaming algorithms. Our single-pass algorithm obtains a constant ratio in $\lceil n / c \rceil + c$ oracle queries, for any $c \ge 1$. In addition, we propose a deterministic, multi-pass streaming algorithm with a constant number of passes that achieves nearly the optimal ratio with linear query and time complexities. We prove a lower bound that implies no constant-factor approximation exists using $o(n)$ queries, even if queries to infeasible sets are allowed. An empirical analysis demonstrates that our algorithms require fewer queries (often substantially less than $n$) yet still achieve better objective value than the current state-of-the-art algorithms, including single-pass, multi-pass, and non-streaming algorithms.
Ebb-and-Flow Protocols: A Resolution of the Availability-Finality Dilemma
Venue: arXiv cs.CR 2021
Year: 2021

The CAP theorem says that no blockchain can be live under dynamic participation and safe under temporary network partitions. To resolve this availability-finality dilemma, we formulate a new class of flexible consensus protocols, ebb-and-flow protocols, which support a full dynamically available ledger in conjunction with a finalized prefix ledger. The finalized ledger falls behind the full ledger when the network partitions but catches up when the network heals. Gasper, the current candidate protocol for Ethereum 2.0's beacon chain, combines the finality gadget Casper FFG with the LMD GHOST fork choice rule and aims to achieve this property. However, we discovered an attack in the standard synchronous network model, highlighting a general difficulty with existing finality-gadget-based designs. We present a construction of provably secure ebb-and-flow protocols with optimal resilience. Nodes run an off-the-shelf dynamically available protocol, take snapshots of the growing available ledger, and input them into a separate off-the-shelf BFT protocol to finalize a prefix. We explore connections with flexible BFT and improve upon the state-of-the-art for that problem.
Embodied Visual Navigation with Automatic Curriculum Learning in Real Environments
Venue: arXiv cs.RO 2021
Year: 2021

We present NavACL, a method of automatic curriculum learning tailored to the navigation task. NavACL is simple to train and efficiently selects relevant tasks using geometric features. In our experiments, deep reinforcement learning agents trained using NavACL significantly outperform state-of-the-art agents trained with uniform sampling -- the current standard. Furthermore, our agents can navigate through unknown cluttered indoor environments to semantically-specified targets using only RGB images. Obstacle-avoiding policies and frozen feature networks support transfer to unseen real-world environments, without any modification or retraining requirements. We evaluate our policies in simulation, and in the real world on a ground robot and a quadrotor drone. Videos of real-world results are available in the supplementary material.
Unit Test Case Generation with Transformers and Focal Context
Venue: arXiv cs.SE 2021
Year: 2021

Automated unit test case generation tools facilitate test-driven development and support developers by suggesting tests intended to identify flaws in their code. Existing approaches are usually guided by the test coverage criteria, generating synthetic test cases that are often difficult for developers to read or understand. In this paper we propose AthenaTest, an approach that aims to generate unit test cases by learning from real-world focal methods and developer-written testcases. We formulate unit test case generation as a sequence-to-sequence learning task, adopting a two-step training procedure consisting of denoising pretraining on a large unsupervised Java corpus, and supervised finetuning for a downstream translation task of generating unit tests. We investigate the impact of natural language and source code pretraining, as well as the focal context information surrounding the focal method. Both techniques provide improvements in terms of validation loss, with pretraining yielding 25% relative improvement and focal context providing additional 11.1% improvement. We also introduce Methods2Test, the largest publicly available supervised parallel corpus of unit test case methods and corresponding focal methods in Java, which comprises 780K test cases mined from 91K open-source repositories from GitHub. We evaluate AthenaTest on five defects4j projects, generating 25K passing test cases covering 43.7% of the focal methods with only 30 attempts. We execute the test cases, collect test coverage information, and compare them with test cases generated by EvoSuite and GPT-3, finding that our approach outperforms GPT-3 and has comparable coverage w.r.t. EvoSuite. Finally, we survey professional developers on their preference in terms of readability, understandability, and testing effectiveness of the generated tests, showing overwhelmingly preference towards AthenaTest.
On topology optimization of design-dependent pressure-loaded three-dimensional structures and compliant mechanisms
Venue: arXiv cs.CE 2021
Year: 2021

This paper presents a density-based topology optimization method for designing three-dimensional (3D) compliant mechanisms and loadbearing structures with design-dependent pressure loading. Instead of interface-tracking techniques, the Darcy law in conjunction with a drainage term is employed to obtain pressure field as a function of the design vector. To ensure continuous transition of pressure loads as the design evolves, the flow coefficient of a finite element is defined using a smooth Heaviside function. The obtained pressure field is converted into consistent nodal loads using a transformation matrix. The presented approach employs the standard finite element formulation and also, allows consistent and computationally inexpensive calculation of load sensitivities using the adjoint-variable method. For compliant mechanism design, a multi-criteria objective is minimized, whereas minimization of compliance is performed for designing loadbearing structures. Efficacy and robustness of the presented approach is demonstrated by designing various pressure-actuated 3D compliant mechanisms and structures.
Extracting Optimal Solution Manifolds using Constrained Neural Optimization
Venue: arXiv cs.NE 2021
Year: 2021

Constrained Optimization solution algorithms are restricted to point based solutions. In practice, single or multiple objectives must be satisfied, wherein both the objective function and constraints can be non-convex resulting in multiple optimal solutions. Real world scenarios include intersecting surfaces as Implicit Functions, Hyperspectral Unmixing and Pareto Optimal fronts. Local or global convexification is a common workaround when faced with non-convex forms. However, such an approach is often restricted to a strict class of functions, deviation from which results in sub-optimal solution to the original problem. We present neural solutions for extracting optimal sets as approximate manifolds, where unmodified, non-convex objectives and constraints are defined as modeler guided, domain-informed $L_2$ loss function. This promotes interpretability since modelers can confirm the results against known analytical forms in their specific domains. We present synthetic and realistic cases to validate our approach and compare against known solvers for bench-marking in terms of accuracy and computational efficiency.
Sparsity of weighted networks: measures and applications
Venue: arXiv cs.DM 2021
Year: 2021

A majority of real life networks are weighted and sparse. The present article aims at characterization of weighted networks based on sparsity, as a measure of inherent diversity, of different network parameters. It utilizes sparsity index defined on ordered degree sequence of simple networks and derives further properties of this index. The range of possible values of sparsity index of any connected network, with edge-count in specific intervals, is worked out analytically in terms of node-count; a pattern is uncovered in corresponding degree sequences to produce highest sparsities. Given the edge-weight frequency distribution of a network, we have formulated an expression of the sparsity index of edge-weights. Its properties are analyzed under different distributions of edge-weights. For example, the upper and lower bounds of sparsity index of edge-weights of a network, having all distinct edge-weights, is determined in terms of its node-count and edge density. The article highlights that this summary index with low computational cost, computed on different network parameters, is useful to reveal different structural and organizational aspects of networks for performing analysis. An application of this index has been demonstrated through overlapping community detection of networks. The results validated on artificial and real-world networks show its efficacy.
Beneficial and Harmful Explanatory Machine Learning
Venue: arXiv cs.AI 2021
Year: 2021

Given the recent successes of Deep Learning in AI there has been increased interest in the role and need for explanations in machine learned theories. A distinct notion in this context is that of Michie's definition of Ultra-Strong Machine Learning (USML). USML is demonstrated by a measurable increase in human performance of a task following provision to the human of a symbolic machine learned theory for task performance. A recent paper demonstrates the beneficial effect of a machine learned logic theory for a classification task, yet no existing work to our knowledge has examined the potential harmfulness of machine's involvement for human comprehension during learning. This paper investigates the explanatory effects of a machine learned theory in the context of simple two person games and proposes a framework for identifying the harmfulness of machine explanations based on the Cognitive Science literature. The approach involves a cognitive window consisting of two quantifiable bounds and it is supported by empirical evidence collected from human trials. Our quantitative and qualitative results indicate that human learning aided by a symbolic machine learned theory which satisfies a cognitive window has achieved significantly higher performance than human self learning. Results also demonstrate that human learning aided by a symbolic machine learned theory that fails to satisfy this window leads to significantly worse performance than unaided human learning.
Federated Generalized Bayesian Learning via Distributed Stein Variational Gradient Descent
Venue: arXiv cs.LG 2021
Year: 2021

This paper introduces Distributed Stein Variational Gradient Descent (DSVGD), a non-parametric generalized Bayesian inference framework for federated learning. DSVGD maintains a number of non-random and interacting particles at a central server to represent the current iterate of the model global posterior. The particles are iteratively downloaded and updated by one of the agents with the end goal of minimizing the global free energy. By varying the number of particles, DSVGD enables a flexible trade-off between per-iteration communication load and number of communication rounds. DSVGD is shown to compare favorably to benchmark frequentist and Bayesian federated learning strategies, also scheduling a single device per iteration, in terms of accuracy and scalability with respect to the number of agents, while also providing well-calibrated, and hence trustworthy, predictions.
Into the Unknown: Active Monitoring of Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

Neural-network classifiers achieve high accuracy when predicting the class of an input that they were trained to identify. Maintaining this accuracy in dynamic environments, where inputs frequently fall outside the fixed set of initially known classes, remains a challenge. The typical approach is to detect inputs from novel classes and retrain the classifier on an augmented dataset. However, not only the classifier but also the detection mechanism needs to adapt in order to distinguish between newly learned and yet unknown input classes. To address this challenge, we introduce an algorithmic framework for active monitoring of a neural network. A monitor wrapped in our framework operates in parallel with the neural network and interacts with a human user via a series of interpretable labeling queries for incremental adaptation. In addition, we propose an adaptive quantitative monitor to improve precision. An experimental evaluation on a diverse set of benchmarks with varying numbers of classes confirms the benefits of our active monitoring framework in dynamic scenarios.
Pilot: Winner of the Human-Agent Negotiation Challenge at IJCAI 2020
Venue: arXiv cs.HC 2021
Year: 2021

This document describes our agent Pilot, winner of the Human-Agent Negotiation Challenge at ANAC, IJCAI 2020. Pilot is a virtual human that participates in a sequence of three negotiations with a human partner. Our system is based on the Interactive Arbitration Guide Online (IAGO) negotiation framework. We leverage prior Affective Computing and Psychology research in negotiations to guide various key principles that define the behavior and personality of our agent.
Managing network congestion with a tradable credit scheme: a trip-based MFD approach
Venue: arXiv cs.GT 2021
Year: 2021

This study investigates the efficiency and effectiveness of an area-based tradable credit scheme (TCS) using the trip-based Macroscopic Fundamental Diagram model for the morning commute problem. In the proposed TCS, the regulator distributes initial credits to all travelers and designs a time-varying and trip length specific credit tariff. Credits are traded between travelers and the regulator via a credit market, and the credit price is determined by the demand and supply of credits. The heterogeneity of travelers is considered in terms of desired arrival time, trip length and departure-time choice preferences. The TCS is incorporated into a day-to-day modelling framework to examine the travelers' learning process, the evolution of network, and the properties of the credit market. The existence of an equilibrium solution and the uniqueness of the credit price at the equilibrium state are established analytically. Furthermore, an open-source simulation framework is developed to validate the analytical properties of the proposed TCS and compare it with alternative control strategies in terms of mobility, network performance, and social welfare. Bayesian optimization is then adopted to optimize the credit toll scheme. The numerical results demonstrate that the proposed TCS outperforms the no-control case and matches the performance of the time-of-day pricing strategy, while maintaining revenue-neutral nature.
New Instances of Quadratic APN Functions
Venue: arXiv cs.IT 2021
Year: 2021

In a recent work, Beierle, Brinkmann and Leander presented a recursive tree search for finding APN permutations with linear self-equivalences in small dimensions. In this paper, we describe how this search can be adapted to find many new instances of quadratic APN functions. In particular, we found 12,921 new quadratic APN functions in dimension eight, 35 new quadratic APN functions in dimension nine and five new quadratic APN functions in dimension ten up to CCZ-equivalence. Remarkably, two of the 35 new APN functions in dimension nine are APN permutations. Among the 8-bit APN functions, there are three extended Walsh spectra that do not correspond to any of the previously-known quadratic 8-bit APN functions and, surprisingly, there exist at least four CCZ-inequivalent 8-bit APN functions with linearity $2^7$, i.e., the highest possible non-trivial linearity for quadratic functions in dimension eight.
Constrained Labeling for Weakly Supervised Learning
Venue: arXiv cs.LG 2021
Year: 2021

Curation of large fully supervised datasets has become one of the major roadblocks for machine learning. Weak supervision provides an alternative to supervised learning by training with cheap, noisy, and possibly correlated labeling functions from varying sources. The key challenge in weakly supervised learning is combining the different weak supervision signals while navigating misleading correlations in their errors. In this paper, we propose a simple data-free approach for combining weak supervision signals by defining a constrained space for the possible labels of the weak signals and training with a random labeling within this constrained space. Our method is efficient and stable, converging after a few iterations of gradient descent. We prove theoretical conditions under which the worst-case error of the randomized label decreases with the rank of the linear constraints. We show experimentally that our method outperforms other weak supervision methods on various text- and image-classification tasks.
Neuro-symbolic Neurodegenerative Disease Modeling as Probabilistic Programmed Deep Kernels
Venue: arXiv cs.LG 2021
Year: 2021

We present a probabilistic programmed deep kernel learning approach to personalized, predictive modeling of neurodegenerative diseases. Our analysis considers a spectrum of neural and symbolic machine learning approaches, which we assess for predictive performance and important medical AI properties such as interpretability, uncertainty reasoning, data-efficiency, and leveraging domain knowledge. Our Bayesian approach combines the flexibility of Gaussian processes with the structural power of neural networks to model biomarker progressions, without needing clinical labels for training. We run evaluations on the problem of Alzheimer's disease prediction, yielding results that surpass deep learning in both accuracy and timeliness of predicting neurodegeneration, and with the practical advantages of Bayesian nonparametrics and probabilistic programming.
Distilled One-Shot Federated Learning
Venue: arXiv cs.LG 2021
Year: 2021

Current federated learning algorithms take tens of communication rounds transmitting unwieldy model weights under ideal circumstances and hundreds when data is poorly distributed. Inspired by recent work on dataset distillation and distributed one-shot learning, we propose Distilled One-Shot Federated Learning (DOSFL) to significantly reduce the communication cost while achieving comparable performance. In just one round, each client distills their private dataset, sends the synthetic data (e.g. images or sentences) to the server, and collectively trains a global model. The distilled data look like noise and are only useful to the specific model weights, i.e., become useless after the model updates. With this weight-less and gradient-less design, the total communication cost of DOSFL is up to three orders of magnitude less than FedAvg while preserving between 93% to 99% performance of a centralized counterpart. Afterwards, clients could switch to traditional methods such as FedAvg to finetune the last few percent to fit personalized local models with local datasets. Through comprehensive experiments, we show the accuracy and communication performance of DOSFL on both vision and language tasks with different models including CNN, LSTM, Transformer, etc. We demonstrate that an eavesdropping attacker cannot properly train a good model using the leaked distilled data, without knowing the initial model weights. DOSFL serves as an inexpensive method to quickly converge on a performant pre-trained model with less than 0.1% communication cost of traditional methods.
More Embeddings, Better Sequence Labelers?
Venue: arXiv cs.CL 2021
Year: 2021

Recent work proposes a family of contextual embeddings that significantly improves the accuracy of sequence labelers over non-contextual embeddings. However, there is no definite conclusion on whether we can build better sequence labelers by combining different kinds of embeddings in various settings. In this paper, we conduct extensive experiments on 3 tasks over 18 datasets and 8 languages to study the accuracy of sequence labeling with various embedding concatenations and make three observations: (1) concatenating more embedding variants leads to better accuracy in rich-resource and cross-domain settings and some conditions of low-resource settings; (2) concatenating additional contextual sub-word embeddings with contextual character embeddings hurts the accuracy in extremely low-resource settings; (3) based on the conclusion of (1), concatenating additional similar contextual embeddings cannot lead to further improvements. We hope these conclusions can help people build stronger sequence labelers in various settings.