OpenRaiser/Intern-Atlas huggingface dataset:
Composite Re-Ranking for Efficient Document Search with BERT
Venue: arXiv cs.IR 2022
Year: 2022

Although considerable efforts have been devoted to transformer-based ranking models for document search, the relevance-efficiency tradeoff remains a critical problem for ad-hoc ranking. To overcome this challenge, this paper presents BECR (BERT-based Composite Re-Ranking), a composite re-ranking scheme that combines deep contextual token interactions and traditional lexical term-matching features. In particular, BECR exploits a token encoding mechanism to decompose the query representations into pre-computable uni-grams and skip-n-grams. By applying token encoding on top of a dual-encoder architecture, BECR separates the attentions between a query and a document while capturing the contextual semantics of a query. In contrast to previous approaches, this framework does not perform expensive BERT computations during online inference. Thus, it is significantly faster, yet still able to achieve high competitiveness in ad-hoc ranking relevance. Finally, an in-depth comparison between BECR and other start-of-the-art neural ranking baselines is described using the TREC datasets, thereby further demonstrating the enhanced relevance and efficiency of BECR.
Learning to Optimize DAG Scheduling in Heterogeneous Environment
Venue: arXiv cs.DC 2022
Year: 2022

Scheduling job flows efficiently and rapidly on distributed computing clusters is one of huge challenges for daily operation of data centers. In a practical scenario, a single job consists of numerous stages with complex dependency relation represented as a Directed Acyclic Graph (DAG) structure. Nowadays a data center usually equips with a cluster of heterogeneous computing servers which are different in the hardware/software configuration. From both the cost saving and environmental friendliness, the data centers could benefit a lot from optimizing the job scheduling problems in the heterogeneous environment. Thus the problem has attracted more and more attention from both the industry and academy. In this paper, we propose a task-duplication based learning algorithm, namely \lachesis \footnote{The second of the Three Fates in ancient Greek mythology, who determines destiny.}, aiming to optimize the problem. In the proposed approach, it first perceives the topological dependencies between jobs using a reinforcement learning framework and a specially designed graph neural network (GNN) to select the most promising task to be executed. Then the task is assigned to a specific executor with the consideration of duplicating all its precedent tasks according to an expert-designed rules. We have conducted extensive experiments over standard workloads to evaluate the proposed solution. The experimental results suggest that \lachesisquad can achieve at most 26.7\% reduction of makespan and 35.2\% improvement of speedup ratio over seven strong baseline algorithms, including the state-of-the-art heuristics methods and a variety of deep reinforcement learning based algorithms.
S2AND: A Benchmark and Evaluation System for Author Name Disambiguation
Venue: arXiv cs.DL 2022
Year: 2022

Author Name Disambiguation (AND) is the task of resolving which author mentions in a bibliographic database refer to the same real-world person, and is a critical ingredient of digital library applications such as search and citation analysis. While many AND algorithms have been proposed, comparing them is difficult because they often employ distinct features and are evaluated on different datasets. In response to this challenge, we present S2AND, a unified benchmark dataset for AND on scholarly papers, as well as an open-source reference model implementation. Our dataset harmonizes eight disparate AND datasets into a uniform format, with a single rich feature set drawn from the Semantic Scholar (S2) database. Our evaluation suite for S2AND reports performance split by facets like publication year and number of papers, allowing researchers to track both global performance and measures of fairness across facet values. Our experiments show that because previous datasets tend to cover idiosyncratic and biased slices of the literature, algorithms trained to perform well on one on them may generalize poorly to others. By contrast, we show how training on a union of datasets in S2AND results in more robust models that perform well even on datasets unseen in training. The resulting AND model also substantially improves over the production algorithm in S2, reducing error by over 50% in terms of $B^3$ F1. We release our unified dataset, model code, trained models, and evaluation suite to the research community. https://github.com/allenai/S2AND/
Fooling Gaussian PTFs via Local Hyperconcentration
Venue: arXiv cs.CC 2022
Year: 2022

We give a pseudorandom generator that fools degree-$d$ polynomial threshold functions over $n$-dimensional Gaussian space with seed length $\mathrm{poly}(d)\cdot \log n$. All previous generators had a seed length with at least a $2^d$ dependence on $d$. The key new ingredient is a Local Hyperconcentration Theorem, which shows that every degree-$d$ Gaussian polynomial is hyperconcentrated almost everywhere at scale $d^{-O(1)}$.
Reinforcement Learning with Algorithms from Probabilistic Structure Estimation
Venue: arXiv cs.LG 2022
Year: 2022

Reinforcement learning (RL) algorithms aim to learn optimal decisions in unknown environments through experience of taking actions and observing the rewards gained. In some cases, the environment is not influenced by the actions of the RL agent, in which case the problem can be modeled as a contextual multi-armed bandit and lightweight myopic algorithms can be employed. On the other hand, when the RL agent's actions affect the environment, the problem must be modeled as a Markov decision process and more complex RL algorithms are required which take the future effects of actions into account. Moreover, in practice, it is often unknown from the outset whether or not the agent's actions will impact the environment and it is therefore not possible to determine which RL algorithm is most fitting. In this work, we propose to avoid this difficult decision entirely and incorporate a choice mechanism into our RL framework. Rather than assuming a specific problem structure, we use a probabilistic structure estimation procedure based on a likelihood-ratio (LR) test to make a more informed selection of learning algorithm. We derive a sufficient condition under which myopic policies are optimal, present an LR test for this condition, and derive a bound on the regret of our framework. We provide examples of real-world scenarios where our framework is needed and provide extensive simulations to validate our approach.
Take a Bite of the Reality Sandwich: Revisiting the Security of Progressive Message Authentication Codes
Venue: arXiv cs.CR 2022
Year: 2022

Message authentication guarantees the integrity of messages exchanged over untrusted channels. However, to achieve this goal, message authentication considerably expands packet sizes, which is especially problematic in constrained wireless environments. To address this issue, progressive message authentication provides initially reduced integrity protection that is often sufficient to process messages upon reception. This reduced security is then successively improved with subsequent messages to uphold the strong guarantees of traditional integrity protection. However, contrary to previous claims, we show in this paper that existing progressive message authentication schemes are highly susceptible to packet loss induced by poor channel conditions or jamming attacks. Thus, we consider it imperative to rethink how authentication tags depend on the successful reception of surrounding packets. To this end, we propose R2-D2, which uses randomized dependencies with parameterized security guarantees to increase the resilience of progressive authentication against packet loss. To deploy our approach to resource-constrained devices, we introduce SP-MAC, which implements R2-D2 using efficient XOR operations. Our evaluation shows that SP-MAC is resilient to sophisticated network-level attacks and operates as resources-conscious and fast as existing, yet insecure, progressive message authentication schemes.
Kinematic Motion Retargeting via Neural Latent Optimization for Learning Sign Language
Venue: arXiv cs.RO 2022
Year: 2022

Motion retargeting from a human demonstration to a robot is an effective way to reduce the professional requirements and workload of robot programming, but faces the challenges resulting from the differences between humans and robots. Traditional optimization-based methods are time-consuming and rely heavily on good initialization, while recent studies using feedforward neural networks suffer from poor generalization to unseen motions. Moreover, they neglect the topological information in human skeletons and robot structures. In this paper, we propose a novel neural latent optimization approach to address these problems. Latent optimization utilizes a decoder to establish a mapping between the latent space and the robot motion space. Afterward, the retargeting results that satisfy robot constraints can be obtained by searching for the optimal latent vector. Alongside with latent optimization, neural initialization exploits an encoder to provide a better initialization for faster and better convergence of optimization. Both the human skeleton and the robot structure are modeled as graphs to make better use of topological information. We perform experiments on retargeting Chinese sign language, which involves two arms and two hands, with additional requirements on the relative relationships among joints. Experiments include retargeting various human demonstrations to YuMi, NAO, and Pepper in the simulation environment and to YuMi in the real-world environment. Both efficiency and accuracy of the proposed method are verified.
Are deep learning models superior for missing data imputation in large surveys? Evidence from an empirical comparison
Venue: arXiv cs.LG 2022
Year: 2022

Multiple imputation (MI) is a popular approach for dealing with missing data arising from non-response in sample surveys. Multiple imputation by chained equations (MICE) is one of the most widely used MI algorithms for multivariate data, but it lacks theoretical foundation and is computationally intensive. Recently, missing data imputation methods based on deep learning models have been developed with encouraging results in small studies. However, there has been limited research on evaluating their performance in realistic settings compared to MICE, particularly in big surveys. We conduct extensive simulation studies based on a subsample of the American Community Survey to compare the repeated sampling properties of four machine learning based MI methods: MICE with classification trees, MICE with random forests, generative adversarial imputation networks, and multiple imputation using denoising autoencoders. We find the deep learning imputation methods are superior to MICE in terms of computational time. However, with the default choice of hyperparameters in the common software packages, MICE with classification trees consistently outperforms, often by a large margin, the deep learning imputation methods in terms of bias, mean squared error, and coverage under a range of realistic settings.
Optimizing Edge Sets in Networks to Produce Ground Truth Communities Based on Modularity
Venue: arXiv cs.SI 2022
Year: 2022

We consider two new problems regarding the impact of edge addition or removal on the modularity of partitions (or community structures) in a network. The first problem seeks to add edges to enforce that a desired partition is the partition that maximizes modularity. The second problem seeks to find the sparsest representation of a network that has the same partition with maximum modularity as the original network. We present integer programming formulations, a row generation algorithm, and heuristic algorithms to solve these problems. Further, we demonstrate a counter-intuitive behavior of modularity that makes the development of heuristics for general networks difficult. We then present results on a selection of social and illicit networks from the literature.
Learning migration models for supporting incremental language migrations of software applications
Venue: arXiv cs.SE 2022
Year: 2022

Context: A Legacy system can be defined as a system that significantly resists modification and evolution. According to the literature, there are two main strategies to migrate a legacy system: (a) to replace the legacy system by a new one, (b) to incrementally migrate parts from the legacy system to the new one. Incremental migration allows developers to better control the risks that may occur during the migration process. However, this strategy is more complex because it requires decomposition of the legacy system into different parts, e.g. a set of files, and to define the order of migration of them along the migration process. To our knowledge, there is no approach to support developers on those activities. Objective: This paper presents an approach, named MigrationExp, to support incremental language migrations of applications from one source language to another target language. MigrationExp recommends the files that should be migrated first in a particular migration iteration. As a novelty, our approach relies on a ranking model learned, using a learning-to-rank algorithm, from migrations made by developers. Method: We validate our approach in the context of the migrations of Android apps, from Java to Kotlin, a new official language for Android. We train our model using migrations of Java code to Kotlin written by developers on open-source applications. Results: The results show that, on the task of proposing files to migrate, our approach outperforms a previous migration strategy proposed by Google, in terms of its ability to accurately predict empirically observed migration orders. Conclusion: Since most Android applications are written in Java, we conclude that approaches to support developers such as MigrationExp may significantly impact the development of Android applications.
Some New Constructions of Generalized Plateaued Functions
Venue: arXiv cs.IT 2022
Year: 2022

Plateaued functions as an extension of bent functions play a significant role in cryptography, coding theory, sequences and combinatorics. In \cite{Mesnager9}, Mesnager \emph{et al.} introduced generalized plateaued functions in order to study plateaued functions in the general context of generalized $p$-ary functions. In this paper, we focus on the constructions of generalized $p$-ary $s$-plateaued functions from $V_{n}$ to $\mathbb{Z}_{p^k}$, where $V_{n}$ is an $n$-dimensional vector space over $\mathbb{F}_{p}$, $p$ is a prime, $k\geq 1$ and $n+s$ is even when $p=2$. In particular, when $k=1$, the constructions in this paper are applicable for plateaued functions. Firstly, inspired by the work of Hodžić \emph{et al}. \cite{Hodzic3} for Boolean plateaued functions, we characterize generalized plateaued functions with affine Walsh supports and provide constructions of generalized plateaued functions with (non)-affine Walsh supports by spectral method. When $p=2, k=1$, our constructions of Boolean plateaued functions with (non)-affine Walsh supports provide an answer to the Open Problem 2 proposed in \cite{Hodzic3}. Secondly, based on what we called generalized indirect sum, we give constructions of generalized plateaued functions, which are also applicable for (non)-weakly regular generalized bent functions. In the end, we discuss the constructions of pairwise disjoint spectra generalized plateaued functions with (non)-affine Walsh supports and we present a construction of generalized bent functions by using pairwise disjoint spectra generalized plateaued functions as building blocks.
Exploring the relationship between journals indexed from a country and its research output: An empirical investigation
Venue: arXiv cs.DL 2022
Year: 2022

Scientific journals are currently the primary medium used by researchers to report their research findings. The transformation of print journals into e-journals has simplified the process of submissions to journals and also their access has become wider. Journals are usually published by commercial publishers, learned societies as well as Universities. There are different number of journals published from different countries. This paper attempts to explore whether the number of journals published from a country influences its research output. Scopus master journal list is analysed to identify journals published from 50 selected countries with significant volume of research output. The following relationship are analysed: (a) number of journals from a country and its research output, (b) growth rate of journals and research output for different countries, (c) global share of journals and research output for different countries, and (d) subject area-wise number of journals and research output in that subject area for different countries. Factors like journal packing density are also analysed. The results obtained show that for majority of the countries, the number of journals is positively correlated to their research output volume, though some other factors also play a role in growth of research output. The study at the end presents a discussion of the analytical outcomes and provides useful suggestions on policy perspectives for different countries.
DataLens: Scalable Privacy Preserving Training via Gradient Compression and Aggregation
Venue: arXiv cs.LG 2022
Year: 2022

Recent success of deep neural networks (DNNs) hinges on the availability of large-scale dataset; however, training on such dataset often poses privacy risks for sensitive training information. In this paper, we aim to explore the power of generative models and gradient sparsity, and propose a scalable privacy-preserving generative model DATALENS. Comparing with the standard PATE privacy-preserving framework which allows teachers to vote on one-dimensional predictions, voting on the high dimensional gradient vectors is challenging in terms of privacy preservation. As dimension reduction techniques are required, we need to navigate a delicate tradeoff space between (1) the improvement of privacy preservation and (2) the slowdown of SGD convergence. To tackle this, we take advantage of communication efficient learning and propose a novel noise compression and aggregation approach TOPAGG by combining top-k compression for dimension reduction with a corresponding noise injection mechanism. We theoretically prove that the DATALENS framework guarantees differential privacy for its generated data, and provide analysis on its convergence. To demonstrate the practical usage of DATALENS, we conduct extensive experiments on diverse datasets including MNIST, Fashion-MNIST, and high dimensional CelebA, and we show that, DATALENS significantly outperforms other baseline DP generative models. In addition, we adapt the proposed TOPAGG approach, which is one of the key building blocks in DATALENS, to DP SGD training, and show that it is able to achieve higher utility than the state-of-the-art DP SGD approach in most cases. Our code is publicly available at https://github.com/AI-secure/DataLens.
Deepened Graph Auto-Encoders Help Stabilize and Enhance Link Prediction
Venue: arXiv cs.LG 2022
Year: 2022

Graph neural networks have been used for a variety of learning tasks, such as link prediction, node classification, and node clustering. Among them, link prediction is a relatively under-studied graph learning task, with current state-of-the-art models based on one- or two-layer of shallow graph auto-encoder (GAE) architectures. In this paper, we focus on addressing a limitation of current methods for link prediction, which can only use shallow GAEs and variational GAEs, and creating effective methods to deepen (variational) GAE architectures to achieve stable and competitive performance. Our proposed methods innovatively incorporate standard auto-encoders (AEs) into the architectures of GAEs, where standard AEs are leveraged to learn essential, low-dimensional representations via seamlessly integrating the adjacency information and node features, while GAEs further build multi-scaled low-dimensional representations via residual connections to learn a compact overall embedding for link prediction. Empirically, extensive experiments on various benchmarking datasets verify the effectiveness of our methods and demonstrate the competitive performance of our deepened graph models for link prediction. Theoretically, we prove that our deep extensions inclusively express multiple polynomial filters with different orders.
Secure list decoding and its application to bit-string commitment
Venue: arXiv cs.IT 2022
Year: 2022

We propose a new concept of secure list decoding, which is related to bit-string commitment. While the conventional list decoding requires that the list contains the transmitted message, secure list decoding requires the following additional security conditions to work as a modification of bit-string commitment. The first additional security condition is the receiver's uncertainty for the transmitted message, which is stronger than the impossibility of the correct decoding, even though the transmitted message is contained in the list. The other additional security condition is the impossibility for the sender to estimate another element of the decoded list except for the transmitted message. The first condition is evaluated by the equivocation rate. The asymptotic property is evaluated by three parameters, the rates of the message and list sizes, and the equivocation rate. We derive the capacity region of this problem. We show that the combination of hash function and secure list decoding yields the conventional bit-string commitment. Our results hold even when the input and output systems are general probability spaces including continuous systems. When the input system is a general probability space, we formulate the abilities of the honest sender and the dishonest sender in a different way.
Autonomous Flight in Unknown GNSS-denied Environments for Disaster Examination
Venue: arXiv cs.RO 2022
Year: 2022

Micro aerial vehicles (MAVs) have high potential for information gathering tasks to support situation awareness in search and rescue scenarios. Manually controlling MAVs in such scenarios requires experienced pilots and is error-prone, especially in stressful situations of real emergencies. The conditions of disaster scenarios are also challenging for autonomous MAV systems. The environment is usually not known in advance and GNSS might not always be available. We present a system for autonomous MAV flights in unknown environments which does not rely on global positioning systems. The method is evaluated in multiple search and rescue scenarios and allows for safe autonomous flights, even when transitioning between indoor and outdoor areas.