OpenRaiser/Intern-Atlas huggingface dataset:
Monotone Complexity of Spanning Tree Polynomial Re-visited
Venue: arXiv cs.CC 2021
Year: 2021

We prove two results that shed new light on the monotone complexity of the spanning tree polynomial, a classic polynomial in algebraic complexity and beyond. First, we show that the spanning tree polynomials having $n$ variables and defined over constant-degree expander graphs, have monotone arithmetic complexity $2^{Ω(n)}$. This yields the first strongly exponential lower bound on the monotone arithmetic circuit complexity for a polynomial in VP. Before this result, strongly exponential size monotone lower bounds were known only for explicit polynomials in VNP (Gashkov-Sergeev'12, Raz-Yehudayoff'11, Srinivasan'20, Cavalar-Kumar-Rossman'20, Hrubes-Yehudayoff'21). Recently, Hrubes'20 initiated a program to prove lower bounds against general arithmetic circuits by proving $ε$-sensitive lower bounds for monotone arithmetic circuits for a specific range of values for $ε\in (0,1)$. We consider the spanning tree polynomial $ST_{n}$ defined over the complete graph on $n$ vertices and show that the polynomials $F_{n-1,n} - ε\cdot ST_{n}$ and $F_{n-1,n} + ε\cdot ST_{n}$ defined over $n^2$ variables, have monotone circuit complexity $2^{Ω(n)}$ if $ε\geq 2^{-Ω(n)}$ and $F_{n-1,n} = \prod_{i=2}^n (x_{i,1} +\cdots + x_{i,n})$ is the complete set-multilinear polynomial. This provides the first $ε$-sensitive exponential lower bound for a family of polynomials inside VP. En-route, we consider a problem in 2-party, best partition communication complexity of deciding whether two sets of oriented edges distributed among Alice and Bob form a spanning tree or not. We prove that there exists a fixed distribution, under which the problem has low discrepancy with respect to every nearly-balanced partition. This result could be of interest beyond algebraic complexity.
Searching for More Efficient Dynamic Programs
Venue: arXiv cs.CL 2021
Year: 2021

Computational models of human language often involve combinatorial problems. For instance, a probabilistic parser may marginalize over exponentially many trees to make predictions. Algorithms for such problems often employ dynamic programming and are not always unique. Finding one with optimal asymptotic runtime can be unintuitive, time-consuming, and error-prone. Our work aims to automate this laborious process. Given an initial correct declarative program, we search for a sequence of semantics-preserving transformations to improve its running time as much as possible. To this end, we describe a set of program transformations, a simple metric for assessing the efficiency of a transformed program, and a heuristic search procedure to improve this metric. We show that in practice, automated search -- like the mental search performed by human programmers -- can find substantial improvements to the initial program. Empirically, we show that many common speed-ups described in the NLP literature could have been discovered automatically by our system.
Grounding-aware RRT* for Path Planning and Safe Navigation of Marine Crafts in Confined Waters
Venue: arXiv cs.RO 2021
Year: 2021

The paper presents a path planning algorithm based on RRT* that addresses the risk of grounding during evasive manoeuvres to avoid collision. The planner achieves this objective by integrating a collective navigation experience with the systematic use of water depth information from the electronic navigational chart. Multivariate kernel density estimation is applied to historical AIS data to generate a probabilistic model describing seafarer's best practices while sailing in confined waters. This knowledge is then encoded into the RRT* cost function to penalize path deviations that would lead own ship to sail in shallow waters. Depth contours satisfying the own ship draught define the actual navigable area, and triangulation of this non-convex region is adopted to enable uniform sampling. This ensures the optimal path deviation.
NOPE: A Corpus of Naturally-Occurring Presuppositions in English
Venue: arXiv cs.CL 2021
Year: 2021

Understanding language requires grasping not only the overtly stated content, but also making inferences about things that were left unsaid. These inferences include presuppositions, a phenomenon by which a listener learns about new information through reasoning about what a speaker takes as given. Presuppositions require complex understanding of the lexical and syntactic properties that trigger them as well as the broader conversational context. In this work, we introduce the Naturally-Occurring Presuppositions in English (NOPE) Corpus to investigate the context-sensitivity of 10 different types of presupposition triggers and to evaluate machine learning models' ability to predict human inferences. We find that most of the triggers we investigate exhibit moderate variability. We further find that transformer-based models draw correct inferences in simple cases involving presuppositions, but they fail to capture the minority of exceptional cases in which human judgments reveal complex interactions between context and triggers.
Personalization, Privacy, and Me
Venue: arXiv cs.CY 2021
Year: 2021

News recommendation and personalization is not a solved problem. People are growing concerned of their data being collected in excess in the name of personalization and the usage of it for purposes other than the ones they would think reasonable. Our experience in building personalization products for publishers while adhering to safeguard user privacy led us to investigate more on the user perspective of privacy and personalization. We conducted a survey to explore people's experience with personalization and privacy and the viewpoints of different age groups. In this paper, we share our major findings with publishers and the community that can inform algorithmic design and implementation of the next generation of news recommender systems, which must put the human at its core and reach a balance between personalization experiences and privacy to reap the benefits of both.
Koopman Linearization for Data-Driven Batch State Estimation of Control-Affine Systems
Venue: arXiv cs.RO 2021
Year: 2021

We present the Koopman State Estimator (KoopSE), a framework for model-free batch state estimation of control-affine systems that makes no linearization assumptions, requires no problem-specific feature selections, and has an inference computational cost that is independent of the number of training points. We lift the original nonlinear system into a higher-dimensional Reproducing Kernel Hilbert Space (RKHS), where the system becomes bilinear. The time-invariant model matrices can be learned by solving a least-squares problem on training trajectories. At test time, the system is algebraically manipulated into a linear time-varying system, where standard batch linear state estimation techniques can be used to efficiently compute state means and covariances. Random Fourier Features (RFF) are used to combine the computational efficiency of Koopman-based methods and the generality of kernel-embedding methods. KoopSE is validated experimentally on a localization task involving a mobile robot equipped with ultra-wideband receivers and wheel odometry. KoopSE estimates are more accurate and consistent than the standard model-based extended Rauch-Tung-Striebel (RTS) smoother, despite KoopSE having no prior knowledge of the system's motion or measurement models.
A Three Step Training Approach with Data Augmentation for Morphological Inflection
Venue: arXiv cs.CL 2021
Year: 2021

We present the BME submission for the SIGMORPHON 2021 Task 0 Part 1, Generalization Across Typologically Diverse Languages shared task. We use an LSTM encoder-decoder model with three step training that is first trained on all languages, then fine-tuned on each language families and finally finetuned on individual languages. We use a different type of data augmentation technique in the first two steps. Our system outperformed the only other submission. Although it remains worse than the Transformer baseline released by the organizers, our model is simpler and our data augmentation techniques are easily applicable to new languages. We perform ablation studies and show that the augmentation techniques and the three training steps often help but sometimes have a negative effect.
Written Justifications are Key to Aggregate Crowdsourced Forecasts
Venue: arXiv cs.CL 2021
Year: 2021

This paper demonstrates that aggregating crowdsourced forecasts benefits from modeling the written justifications provided by forecasters. Our experiments show that the majority and weighted vote baselines are competitive, and that the written justifications are beneficial to call a question throughout its life except in the last quarter. We also conduct an error analysis shedding light into the characteristics that make a justification unreliable.
Avengers Ensemble! Improving Transferability of Authorship Obfuscation
Venue: arXiv cs.LG 2021
Year: 2021

Stylometric approaches have been shown to be quite effective for real-world authorship attribution. To mitigate the privacy threat posed by authorship attribution, researchers have proposed automated authorship obfuscation approaches that aim to conceal the stylometric artefacts that give away the identity of an anonymous document's author. Recent work has focused on authorship obfuscation approaches that rely on black-box access to an attribution classifier to evade attribution while preserving semantics. However, to be useful under a realistic threat model, it is important that these obfuscation approaches work well even when the adversary's attribution classifier is different from the one used internally by the obfuscator. Unfortunately, existing authorship obfuscation approaches do not transfer well to unseen attribution classifiers. In this paper, we propose an ensemble-based approach for transferable authorship obfuscation. Our experiments show that if an obfuscator can evade an ensemble attribution classifier, which is based on multiple base attribution classifiers, it is more likely to transfer to different attribution classifiers. Our analysis shows that ensemble-based authorship obfuscation achieves better transferability because it combines the knowledge from each of the base attribution classifiers by essentially averaging their decision boundaries.
Coalition Game based User Association for mmWave Mobile Relay Systems in Rail Traffic Scenarios
Venue: arXiv cs.IT 2021
Year: 2021

Rail transportation, especially, high-speed rails (HSR), is an important infrastructure for the development of national economy and the promotion of passenger experience. Due to the large bandwidth, millimeter wave (mmWave) communication is regarded as a promising technology to meet the demand of high data rates. However, since mmWave communication has the characteristic of high attenuation, mobile relay (MR) is considered in this paper. Also, full-duplex (FD) communications have been proposed to improve the spectral efficiency. However, because of the high speed, as well as the problem of penetration loss, passengers on the train have a poor quality of service. Consequently, an effective user association scheme for HSR in mmWave band is necessary. In this paper, we investigate the user association optimization problem in mmWave mobilerelay systems where the MRs operate in the FD mode. To maximize the system capacity, we propose a cooperative user association approach based on coalition formation game, and develop a coalition formation algorithm to solve the challenging NP-hard problem. We also prove the convergence and Nashstable property of the proposed algorithm. Extensive simulations are done to show the system performance of the proposed scheme under various network settings. It is demonstrated that the proposed distributed low complexity scheme achieves a nearoptimal performance and outperforms two baseline schemes in terms of average system throughput.
The Elliptic Net Algorithm Revisited
Venue: arXiv cs.CR 2021
Year: 2021

Pairings have been widely used since their introduction to cryptography. They can be applied to identity-based encryption, tripartite Diffie-Hellman key agreement, blockchain and other cryptographic schemes. The Acceleration of pairing computations is crucial for these cryptographic schemes or protocols. In this paper, we will focus on the Elliptic Net algorithm which can compute pairings in polynomial time, but it requires more storage than Miller's algorithm. We use several methods to speed up the Elliptic Net algorithm. Firstly, we eliminate the inverse operation in the improved Elliptic Net algorithm. In some circumstance, this finding can achieve further improvements. Secondly, we apply lazy reduction technique to the Elliptic Net algorithm, which helps us achieve a faster implementation. Finally, we propose a new derivation of the formulas for the computation of the Optimal Ate pairing on the twisted curve. Results show that the Elliptic Net algorithm can be significantly accelerated especially on the twisted curve. The algorithm can be $80\%$ faster than the previous ones on the twisted 381-bit BLS12 curve and $71.5\%$ faster on the twisted 676-bit KSS18 curve respectively.
Scalable Cell-Free Massive MIMO Systems with Finite Resolution ADCs/DACs over Spatially Correlated Rician Fading Channels
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, an analytical framework for evaluating the performance of scalable cell-free massive MIMO (SCF-mMIMO) systems in which all user equipments (UEs) and access points (APs) employ finite resolution digital-to-analog converters (DACs) and analog-to-digital converters (ADCs) and operates under correlated Rician fading, is presented. By using maximal-ratio combining (MRC) detection, generic expressions for the uplink (UL) spectral efficiency (SE) for both distributed and centralized schemes are derived. In order to further reduce the computational complexity (CC) of the original local partial MMSE (LP-MMSE) and partial MMSE (P-MMSE) detectors, two novel scalable low complexity MMSE detectors are proposed for distributed and centralized schemes respectively, which achieves very similar SE performance. Furthermore, for the distributed scheme a novel partial large-scale fading decoding (P-LSFD) weighting vector is introduced and its analytical SE performance is very similar to the performance of an equivalent unscalable LSFD vector. Finally, a scalable algorithm jointly consisting of AP cluster formation, pilot assignment, and power control is proposed, which outperforms the conventional random pilot assignment and user-group based pilot assignment policies and, contrary to an equal power transmit strategy, it guarantees quality of service (QoS) fairness for all accessing UEs.
DSOR: A Scalable Statistical Filter for Removing Falling Snow from LiDAR Point Clouds in Severe Winter Weather
Venue: arXiv cs.CV 2021
Year: 2021

For autonomous vehicles to viably replace human drivers they must contend with inclement weather. Falling rain and snow introduce noise in LiDAR returns resulting in both false positive and false negative object detections. In this article we introduce the Winter Adverse Driving dataSet (WADS) collected in the snow belt region of Michigan's Upper Peninsula. WADS is the first multi-modal dataset featuring dense point-wise labeled sequential LiDAR scans collected in severe winter weather; weather that would cause an experienced driver to alter their driving behavior. We have labelled and will make available over 7 GB or 3.6 billion labelled LiDAR points out of over 26 TB of total LiDAR and camera data collected. We also present the Dynamic Statistical Outlier Removal (DSOR) filter, a statistical PCL-based filter capable or removing snow with a higher recall than the state of the art snow de-noising filter while being 28\% faster. Further, the DSOR filter is shown to have a lower time complexity compared to the state of the art resulting in an improved scalability. Our labeled dataset and DSOR filter will be made available at https://bitbucket.org/autonomymtu/dsor_filter
What Does The User Want? Information Gain for Hierarchical Dialogue Policy Optimisation
Venue: arXiv cs.LG 2021
Year: 2021

The dialogue management component of a task-oriented dialogue system is typically optimised via reinforcement learning (RL). Optimisation via RL is highly susceptible to sample inefficiency and instability. The hierarchical approach called Feudal Dialogue Management takes a step towards more efficient learning by decomposing the action space. However, it still suffers from instability due to the reward only being provided at the end of the dialogue. We propose the usage of an intrinsic reward based on information gain to address this issue. Our proposed reward favours actions that resolve uncertainty or query the user whenever necessary. It enables the policy to learn how to retrieve the users' needs efficiently, which is an integral aspect in every task-oriented conversation. Our algorithm, which we call FeudalGain, achieves state-of-the-art results in most environments of the PyDial framework, outperforming much more complex approaches. We confirm the sample efficiency and stability of our algorithm through experiments in simulation and a human trial.
Parallel Constraint-Driven Inductive Logic Programming
Venue: arXiv cs.AI 2021
Year: 2021

Multi-core machines are ubiquitous. However, most inductive logic programming (ILP) approaches use only a single core, which severely limits their scalability. To address this limitation, we introduce parallel techniques based on constraint-driven ILP where the goal is to accumulate constraints to restrict the hypothesis space. Our experiments on two domains (program synthesis and inductive general game playing) show that (i) parallelisation can substantially reduce learning times, and (ii) worker communication (i.e. sharing constraints) is important for good performance.
Learning to Match Job Candidates Using Multilingual Bi-Encoder BERT
Venue: arXiv cs.CL 2021
Year: 2021

In this talk, we will show how we used Randstad history of candidate placements to generate labeled CV-vacancy pairs dataset. Afterwards we fine-tune a multilingual BERT with bi encoder structure over this dataset, by adding a cosine similarity log loss layer. We will explain how using the mentioned structure helps us overcome most of the challenges described above, and how it enables us to build a maintainable and scalable pipeline to match CVs and vacancies. In addition, we show how we gain a better semantic understanding, and learn to bridge the vocabulary gap. Finally, we highlight how multilingual transformers help us handle cross language barrier and might reduce discrimination.
A Comparison of Code Embeddings and Beyond
Venue: arXiv cs.SE 2021
Year: 2021

Program representation learning is a fundamental task in software engineering applications. With the availability of "big code" and the development of deep learning techniques, various program representation learning models have been proposed to understand the semantic properties of programs and applied on different software engineering tasks. However, no previous study has comprehensively assessed the generalizability of these deep models on different tasks, so that the pros and cons of the models are unclear. In this experience paper, we try to bridge this gap by systemically evaluating the performance of eight program representation learning models on three common tasks, where six models are based on abstract syntax trees and two models are based on plain text of source code. We kindly explain the criteria for selecting the models and tasks, as well as the method for enabling end-to-end learning in each task. The results of performance evaluation show that they perform diversely in each task and the performance of the AST-based models is generally unstable over different tasks. In order to further explain the results, we apply a prediction attribution technique to find what elements are captured by the models and responsible for the predictions in each task. Based on the findings, we discuss some general principles for better capturing the information in the source code, and hope to inspire researchers to improve program representation learning methods for software engineering tasks.
Target Languages (vs. Inductive Biases) for Learning to Act and Plan
Venue: arXiv cs.AI 2021
Year: 2021

Recent breakthroughs in AI have shown the remarkable power of deep learning and deep reinforcement learning. These developments, however, have been tied to specific tasks, and progress in out-of-distribution generalization has been limited. While it is assumed that these limitations can be overcome by incorporating suitable inductive biases, the notion of inductive biases itself is often left vague and does not provide meaningful guidance. In the paper, I articulate a different learning approach where representations do not emerge from biases in a neural architecture but are learned over a given target language with a known semantics. The basic ideas are implicit in mainstream AI where representations have been encoded in languages ranging from fragments of first-order logic to probabilistic structural causal models. The challenge is to learn from data the representations that have traditionally been crafted by hand. Generalization is then a result of the semantics of the language. The goals of this paper are to make these ideas explicit, to place them in a broader context where the design of the target language is crucial, and to illustrate them in the context of learning to act and plan. For this, after a general discussion, I consider learning representations of actions, general policies, and subgoals ("intrinsic rewards"). In these cases, learning is formulated as a combinatorial problem but nothing prevents the use of deep learning techniques instead. Indeed, learning representations over languages with a known semantics provides an account of what is to be learned, while learning representations with neural nets provides a complementary account of how representations can be learned. The challenge and the opportunity is to bring the two together.
Life-Long Multi-Task Learning of Adaptive Path Tracking Policy for Autonomous Vehicle
Venue: arXiv cs.RO 2021
Year: 2021

This paper proposes a life-long adaptive path tracking policy learning method for autonomous vehicles that can self-evolve and self-adapt with multi-task knowledge. Firstly, the proposed method can learn a model-free control policy for path tracking directly from the historical driving experience, where the property of vehicle dynamics and corresponding control strategy can be learned simultaneously. Secondly, by utilizing the life-long learning method, the proposed method can learn the policy with task-incremental knowledge without encountering catastrophic forgetting. Thus, with continual multi-task knowledge learned, the policy can iteratively adapt to new tasks and improve its performance with knowledge from new tasks. Thirdly, a memory evaluation and updating method is applied to optimize memory structure for life-long learning which enables the policy to learn toward selected directions. Experiments are conducted using a high-fidelity vehicle dynamic model in a complex curvy road to evaluate the performance of the proposed method. Results show that the proposed method can effectively evolve with continual multi-task knowledge and adapt to the new environment, where the performance of the proposed method can also surpass two commonly used baseline methods after evolving.