OpenRaiser/Intern-Atlas huggingface dataset:
A Survey of Information Cascade Analysis: Models, Predictions, and Recent Advances
Venue: arXiv cs.SI 2021
Year: 2021

The deluge of digital information in our daily life -- from user-generated content, such as microblogs and scientific papers, to online business, such as viral marketing and advertising -- offers unprecedented opportunities to explore and exploit the trajectories and structures of the evolution of information cascades. Abundant research efforts, both academic and industrial, have aimed to reach a better understanding of the mechanisms driving the spread of information and quantifying the outcome of information diffusion. This article presents a comprehensive review and categorization of information popularity prediction methods, from feature engineering and stochastic processes, through graph representation, to deep learning-based approaches. Specifically, we first formally define different types of information cascades and summarize the perspectives of existing studies. We then present a taxonomy that categorizes existing works into the aforementioned three main groups as well as the main subclasses in each group, and we systematically review cutting-edge research work. Finally, we summarize the pros and cons of existing research efforts and outline the open challenges and opportunities in this field.
Internal Parametricity for Cubical Type Theory
Venue: arXiv cs.LO 2021
Year: 2021

We define a computational type theory combining the contentful equality structure of cartesian cubical type theory with internal parametricity primitives. The combined theory supports both univalence and its relational equivalent, which we call relativity. We demonstrate the use of the theory by analyzing polymorphic functions between higher inductive types, observe how cubical equality regularizes parametric type theory, and examine the similarities and discrepancies between cubical and parametric type theory, which are closely related. We also abstract a formal interface to the computational interpretation and show that this also has a presheaf model.
Automatic Discovery of Interpretable Planning Strategies
Venue: arXiv cs.LG 2021
Year: 2021

When making decisions, people often overlook critical information or are overly swayed by irrelevant information. A common approach to mitigate these biases is to provide decision-makers, especially professionals such as medical doctors, with decision aids, such as decision trees and flowcharts. Designing effective decision aids is a difficult problem. We propose that recently developed reinforcement learning methods for discovering clever heuristics for good decision-making can be partially leveraged to assist human experts in this design process. One of the biggest remaining obstacles to leveraging the aforementioned methods is that the policies they learn are opaque to people. To solve this problem, we introduce AI-Interpret: a general method for transforming idiosyncratic policies into simple and interpretable descriptions. Our algorithm combines recent advances in imitation learning and program induction with a new clustering method for identifying a large subset of demonstrations that can be accurately described by a simple, high-performing decision rule. We evaluate our new algorithm and employ it to translate information-acquisition policies discovered through metalevel reinforcement learning. The results of large behavioral experiments showed that prividing the decision rules generated by AI-Interpret as flowcharts significantly improved people's planning strategies and decisions across three diferent classes of sequential decision problems. Moreover, another experiment revealed that this approach is significantly more effective than training people by giving them performance feedback. Finally, a series of ablation studies confirmed that AI-Interpret is critical to the discovery of interpretable decision rules. We conclude that the methods and findings presented herein are an important step towards leveraging automatic strategy discovery to improve human decision-making.
AlphaPilot: Autonomous Drone Racing
Venue: arXiv cs.RO 2021
Year: 2021

This paper presents a novel system for autonomous, vision-based drone racing combining learned data abstraction, nonlinear filtering, and time-optimal trajectory planning. The system has successfully been deployed at the first autonomous drone racing world championship: the 2019 AlphaPilot Challenge. Contrary to traditional drone racing systems, which only detect the next gate, our approach makes use of any visible gate and takes advantage of multiple, simultaneous gate detections to compensate for drift in the state estimate and build a global map of the gates. The global map and drift-compensated state estimate allow the drone to navigate through the race course even when the gates are not immediately visible and further enable to plan a near time-optimal path through the race course in real time based on approximate drone dynamics. The proposed system has been demonstrated to successfully guide the drone through tight race courses reaching speeds up to 8m/s and ranked second at the 2019 AlphaPilot Challenge.
Kernel Self-Attention in Deep Multiple Instance Learning
Venue: arXiv cs.LG 2021
Year: 2021

Not all supervised learning problems are described by a pair of a fixed-size input tensor and a label. In some cases, especially in medical image analysis, a label corresponds to a bag of instances (e.g. image patches), and to classify such bag, aggregation of information from all of the instances is needed. There have been several attempts to create a model working with a bag of instances, however, they are assuming that there are no dependencies within the bag and the label is connected to at least one instance. In this work, we introduce Self-Attention Attention-based MIL Pooling (SA-AbMILP) aggregation operation to account for the dependencies between instances. We conduct several experiments on MNIST, histological, microbiological, and retinal databases to show that SA-AbMILP performs better than other models. Additionally, we investigate kernel variations of Self-Attention and their influence on the results.
TRIE: End-to-End Text Reading and Information Extraction for Document Understanding
Venue: arXiv cs.CV 2021
Year: 2021

Since real-world ubiquitous documents (e.g., invoices, tickets, resumes and leaflets) contain rich information, automatic document image understanding has become a hot topic. Most existing works decouple the problem into two separate tasks, (1) text reading for detecting and recognizing texts in images and (2) information extraction for analyzing and extracting key elements from previously extracted plain text. However, they mainly focus on improving information extraction task, while neglecting the fact that text reading and information extraction are mutually correlated. In this paper, we propose a unified end-to-end text reading and information extraction network, where the two tasks can reinforce each other. Specifically, the multimodal visual and textual features of text reading are fused for information extraction and in turn, the semantics in information extraction contribute to the optimization of text reading. On three real-world datasets with diverse document images (from fixed layout to variable layout, from structured text to semi-structured text), our proposed method significantly outperforms the state-of-the-art methods in both efficiency and accuracy.
Asynchronous Reconfiguration with Byzantine Failures
Venue: arXiv cs.DC 2021
Year: 2021

Replicated services are inherently vulnerable to failures and security breaches. In a long-running system, it is, therefore, indispensable to maintain a reconfiguration mechanism that would replace faulty replicas with correct ones. An important challenge is to enable reconfiguration without affecting the availability and consistency of the replicated data: the clients should be able to get correct service even when the set of service replicas is being updated. In this paper, we address the problem of reconfiguration in the presence of Byzantine failures: faulty replicas or clients may arbitrarily deviate from their expected behavior. We describe a generic technique for building asynchronous and Byzantine fault-tolerant reconfigurable objects: clients can manipulate the object data and issue reconfiguration calls without reaching consensus on the current configuration. With the help of forward-secure digital signatures, our solution makes sure that superseded and possibly compromised configurations are harmless, that slow clients cannot be fooled into reading stale data, and that Byzantine clients cannot cause a denial of service by flooding the system with reconfiguration requests. Our approach is modular and based on dynamic Byzantine lattice agreement abstraction, and we discuss how to extend it to enable Byzantine fault-tolerant implementations of a large class of reconfigurable replicated services.
A Distributed Multi-GPU System for Large-Scale Node Embedding at Tencent
Venue: arXiv cs.DC 2021
Year: 2021

Real-world node embedding applications often contain hundreds of billions of edges with high-dimension node features. Scaling node embedding systems to efficiently support these applications remains a challenging problem. In this paper we present a high-performance multi-GPU node embedding system. It uses model parallelism to split node embeddings onto each GPU's local parameter server, and data parallelism to train these embeddings on different edge samples in parallel. We propose a hierarchical data partitioning strategy and an embedding training pipeline to optimize both communication and memory usage on a GPU cluster. With the decoupled design of CPU tasks (random walk) and GPU tasks (embedding training), our system is highly flexible and can fully utilize all computing resources on a GPU cluster. Comparing with the current state-of-the-art multi-GPU single-node embedding system, our system achieves 5.9x-14.4x speedup on average with competitive or better accuracy on open datasets. Using 40 NVIDIA V100 GPUs on a network with almost three hundred billion edges and more than one billion nodes, our implementation requires only 3 minutes to finish one training epoch.
Analysis of Tree-Algorithms with Multi-Packet Reception
Venue: arXiv cs.NI 2021
Year: 2021

In this paper, we analyze binary-tree algorithms in a setup in which the receiver can perform multi-packet reception (MPR) of up to and including K packets simultaneously. The analysis addresses both traffic-independent performance as well as performance under Poisson arrivals. For the former case, we show that the throughput, when normalized with respect to the assumed linear increase in resources required to achieve K-MPR capability, tends to the same value that holds for the single-reception setup. However, when coupled with Poisson arrivals in the windowed access scheme, the normalized throughput increases with K, and we present evidence that it asymptotically tends to 1. We also provide performance results for the modified tree algorithm with K-MPR in the clipped access scheme. To the best of our knowledge, this is the first paper that provides an analytical treatment and a number of fundamental insights in the performance of tree-algorithms with MPR.
An Analytical Model for Molecular Communication over a Non-linear Reaction-Diffusion Medium
Venue: arXiv cs.IT 2021
Year: 2021

One of the main challenges in diffusion-based molecular communication is dealing with the non-linearity of reaction-diffusion chemical equations. While numerical methods can be used to solve these equations, a change in the input signals or the parameters of the medium requires one to redo the simulations. This makes it difficult to design modulation schemes and practically impossible to prove the optimality of a given transmission strategy. In this paper, we provide an analytical technique for modeling the non-linearity of chemical reaction equations based on the perturbation method. The perturbation method expresses the solution in terms of an infinite power series. An approximate solution can be found by keeping the leading terms of the power series. The approximate solution is shown to track the true solution if either the simulation time interval or the reaction rate is sufficiently small. Approximate solutions for long time intervals are also discussed. An illustrative example is given. For this example, it is shown that when the reaction rate (or the total time interval) is low, instead of using a continuous release waveform, it is optimal for the transmitters to release molecules at two time instances.
Complexity of Maximum Cut on Interval Graphs
Venue: arXiv cs.CC 2021
Year: 2021

We resolve the longstanding open problem concerning the computational complexity of Max Cut on interval graphs by showing that it is NP-complete.
Fair Cake Division Under Monotone Likelihood Ratios
Venue: arXiv cs.GT 2021
Year: 2021

This work develops algorithmic results for the classic cake-cutting problem in which a divisible, heterogeneous resource (modeled as a cake) needs to be partitioned among agents with distinct preferences. We focus on a standard formulation of cake cutting wherein each agent must receive a contiguous piece of the cake. While multiple hardness results exist in this setup for finding fair/efficient cake divisions, we show that, if the value densities of the agents satisfy the monotone likelihood ratio property (MLRP), then strong algorithmic results hold for various notions of fairness and economic efficiency. Addressing cake-cutting instances with MLRP, first we develop an algorithm that finds cake divisions (with connected pieces) that are envy-free, up to an arbitrary precision. The time complexity of our algorithm is polynomial in the number of agents and the bit complexity of an underlying Lipschitz constant. We obtain similar positive results for maximizing social (utilitarian) and egalitarian welfare. In addition, we show that, under MLRP, the problem of maximizing Nash social welfare admits a fully polynomial-time approximation scheme (FPTAS). Many distribution families bear MLRP. In particular, this property holds if all the value densities belong to any one of the following families: Gaussian (with the same variance), linear, binomial, Poisson, and exponential distributions. Furthermore, it is known that linear translations of any log-concave function satisfy MLRP. Therefore, our results also hold when the value densities of the agents are linear translations of the following (log-concave) distributions: Laplace, gamma, beta, Subbotin, chi-square, Dirichlet, and logistic. Hence, through MLRP, the current work obtains novel cake-cutting algorithms for multiple distribution families.
Locally Differentially Private (Contextual) Bandits Learning
Venue: arXiv cs.LG 2021
Year: 2021

We study locally differentially private (LDP) bandits learning in this paper. First, we propose simple black-box reduction frameworks that can solve a large family of context-free bandits learning problems with LDP guarantee. Based on our frameworks, we can improve previous best results for private bandits learning with one-point feedback, such as private Bandits Convex Optimization, and obtain the first result for Bandits Convex Optimization (BCO) with multi-point feedback under LDP. LDP guarantee and black-box nature make our frameworks more attractive in real applications compared with previous specifically designed and relatively weaker differentially private (DP) context-free bandits algorithms. Further, we extend our $(\varepsilon, δ)$-LDP algorithm to Generalized Linear Bandits, which enjoys a sub-linear regret $\tilde{O}(T^{3/4}/\varepsilon)$ and is conjectured to be nearly optimal. Note that given the existing $Ω(T)$ lower bound for DP contextual linear bandits (Shariff & Sheffe, 2018), our result shows a fundamental difference between LDP and DP contextual bandits learning.
Structured Multimodal Attentions for TextVQA
Venue: arXiv cs.CV 2021
Year: 2021

In this paper, we propose an end-to-end structured multimodal attention (SMA) neural network to mainly solve the first two issues above. SMA first uses a structural graph representation to encode the object-object, object-text and text-text relationships appearing in the image, and then designs a multimodal graph attention network to reason over it. Finally, the outputs from the above modules are processed by a global-local attentional answering module to produce an answer splicing together tokens from both OCR and general vocabulary iteratively by following M4C. Our proposed model outperforms the SoTA models on TextVQA dataset and two tasks of ST-VQA dataset among all models except pre-training based TAP. Demonstrating strong reasoning ability, it also won first place in TextVQA Challenge 2020. We extensively test different OCR methods on several reasoning models and investigate the impact of gradually increased OCR performance on TextVQA benchmark. With better OCR results, different models share dramatic improvement over the VQA accuracy, but our model benefits most blessed by strong textual-visual reasoning ability. To grant our method an upper bound and make a fair testing base available for further works, we also provide human-annotated ground-truth OCR annotations for the TextVQA dataset, which were not given in the original release. The code and ground-truth OCR annotations for the TextVQA dataset are available at https://github.com/ChenyuGAO-CS/SMA
Ranking Papers by their Short-Term Scientific Impact
Venue: arXiv cs.DL 2021
Year: 2021

The constantly increasing rate at which scientific papers are published makes it difficult for researchers to identify papers that currently impact the research field of their interest. Hence, approaches to effectively identify papers of high impact have attracted great attention in the past. In this work, we present a method that seeks to rank papers based on their estimated short-term impact, as measured by the number of citations received in the near future. Similar to previous work, our method models a researcher as she explores the paper citation network. The key aspect is that we incorporate an attention-based mechanism, akin to a time-restricted version of preferential attachment, to explicitly capture a researcher's preference to read papers which received a lot of attention recently. A detailed experimental evaluation on four real citation datasets across disciplines, shows that our approach is more effective than previous work in ranking papers based on their short-term impact.
Amnesic Probing: Behavioral Explanation with Amnesic Counterfactuals
Venue: arXiv cs.CL 2021
Year: 2021

A growing body of work makes use of probing to investigate the working of neural models, often considered black boxes. Recently, an ongoing debate emerged surrounding the limitations of the probing paradigm. In this work, we point out the inability to infer behavioral conclusions from probing results and offer an alternative method that focuses on how the information is being used, rather than on what information is encoded. Our method, Amnesic Probing, follows the intuition that the utility of a property for a given task can be assessed by measuring the influence of a causal intervention that removes it from the representation. Equipped with this new analysis tool, we can ask questions that were not possible before, e.g. is part-of-speech information important for word prediction? We perform a series of analyses on BERT to answer these types of questions. Our findings demonstrate that conventional probing performance is not correlated to task importance, and we call for increased scrutiny of claims that draw behavioral or causal conclusions from probing results.
Improved SVRG for quadratic functions
Venue: arXiv cs.LG 2021
Year: 2021

We analyse an iterative algorithm to minimize quadratic functions whose Hessian matrix $H$ is the expectation of a random symmetric $d\times d$ matrix. The algorithm is a variant of the stochastic variance reduced gradient (SVRG). In several applications, including least-squares regressions, ridge regressions, linear discriminant analysis and regularized linear discriminant analysis, the running time of each iteration is proportional to $d$. Under smoothness and convexity conditions, the algorithm has linear convergence. When applied to quadratic functions, our analysis improves the state-of-the-art performance of SVRG up to a logarithmic factor. Furthermore, for well-conditioned quadratic problems, our analysis improves the state-of-the-art running times of accelerated SVRG, and is better than the known matching lower bound, by a logarithmic factor. Our theoretical results are backed with numerical experiments.
A Smooth Representation of Belief over SO(3) for Deep Rotation Learning with Uncertainty
Venue: arXiv cs.CV 2021
Year: 2021

Accurate rotation estimation is at the heart of robot perception tasks such as visual odometry and object pose estimation. Deep neural networks have provided a new way to perform these tasks, and the choice of rotation representation is an important part of network design. In this work, we present a novel symmetric matrix representation of the 3D rotation group, SO(3), with two important properties that make it particularly suitable for learned models: (1) it satisfies a smoothness property that improves convergence and generalization when regressing large rotation targets, and (2) it encodes a symmetric Bingham belief over the space of unit quaternions, permitting the training of uncertainty-aware models. We empirically validate the benefits of our formulation by training deep neural rotation regressors on two data modalities. First, we use synthetic point-cloud data to show that our representation leads to superior predictive accuracy over existing representations for arbitrary rotation targets. Second, we use image data collected onboard ground and aerial vehicles to demonstrate that our representation is amenable to an effective out-of-distribution (OOD) rejection technique that significantly improves the robustness of rotation estimates to unseen environmental effects and corrupted input images, without requiring the use of an explicit likelihood loss, stochastic sampling, or an auxiliary classifier. This capability is key for safety-critical applications where detecting novel inputs can prevent catastrophic failure of learned models.
Greedy Scheduling: A Neural Network Method to Reduce Task Failure in Software Crowdsourcing
Venue: arXiv cs.DC 2021
Year: 2021

Context: Highly dynamic and competitive crowdsourcing software development (CSD) marketplaces may experience task failure due to unforeseen reasons, such as increased competition over shared supplier resources, or uncertainty associated with a dynamic worker supply. Existing analysis reveals an average task failure ratio of 15.7\% in software crowdsourcing markets. Goal: The objective of this study is to provide a task scheduling recommendation model for software crowdsourcing platforms in order to improve the success and efficiency of software crowdsourcing. Method: We propose a task scheduling method based on neural networks, and develop a system that can predict and analyze task failure probability upon arrival. More specifically, the model uses a range of input variables, including the number of open tasks in the platform, the average task similarity between arriving tasks and open tasks, the winner's monetary prize, and task duration, to predict the probability of task failure on the planned arrival date and two surplus days. This prediction will offer the recommended day associated with the lowest task failure probability to post the task. The proposed model is based on the workflow and data of Topcoder, one of the primary software crowdsourcing platforms. Results: We present a model that suggests the best recommended arrival dates for any task in the project with surplus of two days per task in the project. The model on average provided 4\% lower failure ratio per project.