OpenRaiser/Intern-Atlas huggingface dataset:
A graded dependent type system with a usage-aware semantics (extended version)
Venue: arXiv cs.PL 2021
Year: 2021

Graded Type Theory provides a mechanism to track and reason about resource usage in type systems. In this paper, we develop GraD, a novel version of such a graded dependent type system that includes functions, tensor products, additive sums, and a unit type. Since standard operational semantics is resource-agnostic, we develop a heap-based operational semantics and prove a soundness theorem that shows correct accounting of resource usage. Several useful properties, including the standard type soundness theorem, non-interference of irrelevant resources in computation and single pointer property for linear resources, can be derived from this theorem. We hope that our work will provide a base for integrating linearity, irrelevance and dependent types in practical programming languages like Haskell.
A Synthetic Over-sampling method with Minority and Majority classes for imbalance problems
Venue: arXiv cs.LG 2021
Year: 2021

Class imbalance is a substantial challenge in classifying many real-world cases. Synthetic over-sampling methods have been effective to improve the performance of classifiers for imbalance problems. However, most synthetic over-sampling methods generate non-diverse synthetic instances within the convex hull formed by the existing minority instances as they only concentrate on the minority class and ignore the vast information provided by the majority class. They also often do not perform well for extremely imbalanced data as the fewer the minority instances, the less information to generate synthetic instances. Moreover, existing methods that generate synthetic instances using the majority class distributional information cannot perform effectively when the majority class has a multi-modal distribution. We propose a new method to generate diverse and adaptable synthetic instances using Synthetic Over-sampling with Minority and Majority classes (SOMM). SOMM generates synthetic instances diversely within the minority data space. It updates the generated instances adaptively to the neighbourhood including both classes. Thus, SOMM performs well for both binary and multiclass imbalance problems. We examine the performance of SOMM for binary and multiclass problems using benchmark data sets for different imbalance levels. The empirical results show the superiority of SOMM compared to other existing methods.
An APTAS for Bin Packing with Clique-graph Conflicts
Venue: arXiv cs.DS 2021
Year: 2021

We study the following variant of the classic {\em bin packing} problem. Given a set of items of various sizes, partitioned into groups, find a packing of the items in a minimum number of identical (unit-size) bins, such that no two items of the same group are assigned to the same bin. This problem, known as {\em bin packing with clique-graph conflicts}, has natural applications in storing file replicas, security in cloud computing and signal distribution. Our main result is an {\em asymptotic polynomial time approximation scheme (APTAS)} for the problem, improving upon the best known ratio of $2$. %In particular, for any instance $I$ and a fixed $\eps \in (0,1)$, the items are packed in at most $(1+\eps)OPT(I) +1$ bins, where $OPT(I)$ is the minimum number of bins required for packing the instance. As a key tool, we apply a novel {\em Shift \& Swap} technique which generalizes the classic linear shifting technique to scenarios allowing conflicts between items. The major challenge of packing {\em small} items using only a small number of extra bins is tackled through an intricate combination of enumeration and a greedy-based approach that utilizes the rounded solution of a {\em linear program}.
BayGo: Joint Bayesian Learning and Information-Aware Graph Optimization
Venue: arXiv cs.LG 2021
Year: 2021

This article deals with the problem of distributed machine learning, in which agents update their models based on their local datasets, and aggregate the updated models collaboratively and in a fully decentralized manner. In this paper, we tackle the problem of information heterogeneity arising in multi-agent networks where the placement of informative agents plays a crucial role in the learning dynamics. Specifically, we propose BayGo, a novel fully decentralized joint Bayesian learning and graph optimization framework with proven fast convergence over a sparse graph. Under our framework, agents are able to learn and communicate with the most informative agent to their own learning. Unlike prior works, our framework assumes no prior knowledge of the data distribution across agents nor does it assume any knowledge of the true parameter of the system. The proposed alternating minimization based framework ensures global connectivity in a fully decentralized way while minimizing the number of communication links. We theoretically show that by optimizing the proposed objective function, the estimation error of the posterior probability distribution decreases exponentially at each iteration. Via extensive simulations, we show that our framework achieves faster convergence and higher accuracy compared to fully-connected and star topology graphs.
A Syntactic Approach to Studying Strongly Equivalent Logic Programs
Venue: arXiv cs.LO 2021
Year: 2021

In the field of Answer Set Programming (ASP), two logic programs are strongly equivalent if they are ordinarily equivalent under any extensions. This property provides a theoretical foundation for studying many aspects of logic programs such as program simplification and transformation etc. Therefore, strong equivalence has been investigated extensively for ASP and its extensions such as LPMLN. In this paper, we present a syntactic approach to studying the strong equivalence of logic programs, which provides several interesting results and would help us understand the strong equivalence from a new perspective. Firstly, we present the notions of independent sets and five kinds of syntactic transformations (S-* transformations) for logic programs. And we investigate the strong equivalence (SE) and non-strong equivalence (NSE) preserving properties of the S-* transformations in the contexts of ASP and LPMLN. Secondly, based on the properties of the S-* transformations, we present a fully automatic algorithm to discover syntactic conditions that preserve strong equivalences (SE-conditions) of ASP and LPMLN programs. To discover the SE-conditions efficiently, we present four kinds of approaches to improve the algorithm. Thirdly, we present a preliminary method to simplify the discovered SE-conditions and report the simplified SE-conditions of several kinds of LPMLN programs. After that, we present a discussion on the discovered SE-conditions and some existing problems. Finally, we present a comparison between SE-conditions discovering approaches in this paper and in the related work.
Deep Learning for Flight Demand Forecasting
Venue: arXiv cs.LG 2021
Year: 2021

Inspired by the success of deep learning (DL) in natural language processing (NLP), we applied cutting-edge DL techniques to predict flight departure demand in a strategic time horizon (4 hours or longer). This work was conducted in support of a MITRE-developed mobile application, Pacer, which displays predicted departure demand to general aviation (GA) flight operators so they can have better situation awareness of the potential for departure delays during busy periods. Field demonstrations involving Pacer's previously designed rule-based prediction method showed that the prediction accuracy of departure demand still has room for improvement. This research strives to improve prediction accuracy from two key aspects: better data sources and robust forecasting algorithms. We leveraged two data sources, Aviation System Performance Metrics (ASPM) and System Wide Information Management (SWIM), as our input. We then trained forecasting models with DL techniques of sequence to sequence (seq2seq) and seq2seq with attention. The case study has shown that our seq2seq with attention performs best among four forecasting algorithms tested. In addition, with better data sources, seq2seq with attention can reduce mean squared error (mse) over 60%, compared to the classical autoregressive (AR) forecasting method.
Deep reinforcement learning for RAN optimization and control
Venue: arXiv cs.NI 2021
Year: 2021

Due to the high variability of the traffic in the radio access network (RAN), fixed network configurations are not flexible enough to achieve optimal performance. Our vendors provide several settings of the eNodeB to optimize the RAN performance, such as media access control scheduler, loading balance, etc. But the detailed mechanisms of the eNodeB configurations are usually very complicated and not disclosed, not to mention the large key performance indicators (KPIs) space needed to be considered. These make constructing a simulator, offline tuning, or rule-based solutions difficult. We aim to build an intelligent controller without strong assumption or domain knowledge about the RAN and can run 24/7 without supervision. To achieve this goal, we first build a closed-loop control testbed RAN in a lab environment with one eNodeB provided by one of the largest wireless vendors and four smartphones. Next, we build a double Q network agent trained with the live feedback of the key performance indicators from the RAN. Our work proved the effectiveness of applying deep reinforcement learning to improve network performance in a real RAN network environment.
A Fast and Reliable Pick-and-Place Application with a Spherical Soft Robotic Arm
Venue: arXiv cs.RO 2021
Year: 2021

This paper presents the application of a learning control approach for the realization of a fast and reliable pick-and-place application with a spherical soft robotic arm. The arm is characterized by a lightweight design and exhibits compliant behavior due to the soft materials deployed. A soft, continuum joint is employed, which allows for simultaneous control of one translational and two rotational degrees of freedom in a single joint. This allows us to axially approach and pick an object with the attached suction cup during the pick-and-place application. A control allocation based on pressure differences and the antagonistic actuator configuration is introduced, allowing decoupling of the system dynamics and simplifying the modeling and control. A linear parameter-varying model is identified, which is parametrized by the attached load mass and a parameter related to the joint stiffness. A gain-scheduled feedback controller is proposed, which asymptotically stabilizes the robotic system for aggressive tuning and over large variations of the parameters considered. The control architecture is augmented with an iterative learning control scheme enabling accurate tracking of aggressive trajectories involving set point transitions of 60 degrees within 0.3 seconds (no mass attached) to 0.6 seconds (load mass attached). The modeling and control approach proposed results in a reliable realization of a pick-and-place application and is experimentally demonstrated.
AI Poincaré: Machine Learning Conservation Laws from Trajectories
Venue: arXiv cs.LG 2021
Year: 2021

We present AI Poincaré, a machine learning algorithm for auto-discovering conserved quantities using trajectory data from unknown dynamical systems. We test it on five Hamiltonian systems, including the gravitational 3-body problem, and find that it discovers not only all exactly conserved quantities, but also periodic orbits, phase transitions and breakdown timescales for approximate conservation laws.
Probabilistic Indistinguishability and the Quality of Validity in Byzantine Agreement
Venue: arXiv cs.DC 2021
Year: 2021

Lower bounds and impossibility results in distributed computing are both intellectually challenging and practically important. Hundreds if not thousands of proofs appear in the literature, but surprisingly, the vast majority of them apply to deterministic algorithms only. Probabilistic protocols have been around for at least four decades and are receiving a lot of attention with the emergence of blockchain systems. Nonetheless, we are aware of only a handful of randomized lower bounds. In this paper we provide a formal framework for reasoning about randomized distributed algorithms. We generalize the notion of indistinguishability, the most useful tool in deterministic lower bounds, to apply to a probabilistic setting. We apply this framework to prove a result of independent interest. Namely, we completely characterize the quality of decisions that protocols for a randomized multi-valued Consensus problem can guarantee in an asynchronous environment with Byzantine faults. We use the new notion to prove a lower bound on the probability at which it can be guaranteed that honest parties will not decide on a possibly bogus value. Finally, we show that the bound is tight by providing a protocol that matches it.
LinCbO: fast algorithm for computation of the Duquenne-Guigues basis
Venue: arXiv cs.DS 2021
Year: 2021

We propose and evaluate a novel algorithm for computation of the Duquenne-Guigues basis which combines Close-by-One and LinClosure algorithms. This combination enables us to reuse attribute counters used in LinClosure and speed up the computation. Our experimental evaluation shows that it is the most efficient algorithm for computation of the Duquenne-Guigues basis.
CircuitBot: Learning to Survive with Robotic Circuit Drawing
Venue: arXiv cs.RO 2021
Year: 2021

Robots with the ability to actively acquire power from surroundings will be greatly beneficial for long-term autonomy, and to survive in dynamic, uncertain environments. In this work, a scenario is presented where a robot has limited energy, and the only way to survive is to access the energy from a power source. With no cables or wires available, the robot learns to construct an electrical path and avoid potential obstacles during the connection. We present this robot, capable of drawing connected circuit patterns with graphene-based conductive ink. A state-of-the-art Mix-Variable Bayesian Optimization is adopted to optimize the placement of conductive shapes to maximize the power this robot receives. Our results show that, within a small number of trials, the robot learns to build parallel circuits to maximize the voltage received and avoid obstacles which steal energy from the robot.
Is Private Learning Possible with Instance Encoding?
Venue: arXiv cs.CR 2021
Year: 2021

A private machine learning algorithm hides as much as possible about its training data while still preserving accuracy. In this work, we study whether a non-private learning algorithm can be made private by relying on an instance-encoding mechanism that modifies the training inputs before feeding them to a normal learner. We formalize both the notion of instance encoding and its privacy by providing two attack models. We first prove impossibility results for achieving a (stronger) model. Next, we demonstrate practical attacks in the second (weaker) attack model on InstaHide, a recent proposal by Huang, Song, Li and Arora [ICML'20] that aims to use instance encoding for privacy.
Learning ODE Models with Qualitative Structure Using Gaussian Processes
Venue: arXiv cs.LG 2021
Year: 2021

Recent advances in learning techniques have enabled the modelling of dynamical systems for scientific and engineering applications directly from data. However, in many contexts explicit data collection is expensive and learning algorithms must be data-efficient to be feasible. This suggests using additional qualitative information about the system, which is often available from prior experiments or domain knowledge. We propose an approach to learning a vector field of differential equations using sparse Gaussian Processes that allows us to combine data and additional structural information, like Lie Group symmetries and fixed points. We show that this combination improves extrapolation performance and long-term behaviour significantly, while also reducing the computational cost.
Predicting Water Temperature Dynamics of Unmonitored Lakes with Meta Transfer Learning
Venue: arXiv cs.LG 2021
Year: 2021

Most environmental data come from a minority of well-monitored sites. An ongoing challenge in the environmental sciences is transferring knowledge from monitored sites to unmonitored sites. Here, we demonstrate a novel transfer learning framework that accurately predicts depth-specific temperature in unmonitored lakes (targets) by borrowing models from well-monitored lakes (sources). This method, Meta Transfer Learning (MTL), builds a meta-learning model to predict transfer performance from candidate source models to targets using lake attributes and candidates' past performance. We constructed source models at 145 well-monitored lakes using calibrated process-based modeling (PB) and a recently developed approach called process-guided deep learning (PGDL). We applied MTL to either PB or PGDL source models (PB-MTL or PGDL-MTL, respectively) to predict temperatures in 305 target lakes treated as unmonitored in the Upper Midwestern United States. We show significantly improved performance relative to the uncalibrated process-based General Lake Model, where the median RMSE for the target lakes is $2.52^{\circ}C$. PB-MTL yielded a median RMSE of $2.43^{\circ}C$; PGDL-MTL yielded $2.16^{\circ}C$; and a PGDL-MTL ensemble of nine sources per target yielded $1.88^{\circ}C$. For sparsely monitored target lakes, PGDL-MTL often outperformed PGDL models trained on the target lakes themselves. Differences in maximum depth between the source and target were consistently the most important predictors. Our approach readily scales to thousands of lakes in the Midwestern United States, demonstrating that MTL with meaningful predictor variables and high-quality source models is a promising approach for many kinds of unmonitored systems and environmental variables.
CAN: Feature Co-Action for Click-Through Rate Prediction
Venue: arXiv cs.IR 2021
Year: 2021

Feature interaction has been recognized as an important problem in machine learning, which is also very essential for click-through rate (CTR) prediction tasks. In recent years, Deep Neural Networks (DNNs) can automatically learn implicit nonlinear interactions from original sparse features, and therefore have been widely used in industrial CTR prediction tasks. However, the implicit feature interactions learned in DNNs cannot fully retain the complete representation capacity of the original and empirical feature interactions (e.g., cartesian product) without loss. For example, a simple attempt to learn the combination of feature A and feature B <A, B> as the explicit cartesian product representation of new features can outperform previous implicit feature interaction models including factorization machine (FM)-based models and their variations. In this paper, we propose a Co-Action Network (CAN) to approximate the explicit pairwise feature interactions without introducing too many additional parameters. More specifically, giving feature A and its associated feature B, their feature interaction is modeled by learning two sets of parameters: 1) the embedding of feature A, and 2) a Multi-Layer Perceptron (MLP) to represent feature B. The approximated feature interaction can be obtained by passing the embedding of feature A through the MLP network of feature B. We refer to such pairwise feature interaction as feature co-action, and such a Co-Action Network unit can provide a very powerful capacity to fitting complex feature interactions. Experimental results on public and industrial datasets show that CAN outperforms state-of-the-art CTR models and the cartesian product method. Moreover, CAN has been deployed in the display advertisement system in Alibaba, obtaining 12\% improvement on CTR and 8\% on Revenue Per Mille (RPM), which is a great improvement to the business.
Duality-Induced Regularizer for Tensor Factorization Based Knowledge Graph Completion
Venue: arXiv cs.LG 2021
Year: 2021

Tensor factorization based models have shown great power in knowledge graph completion (KGC). However, their performance usually suffers from the overfitting problem seriously. This motivates various regularizers -- such as the squared Frobenius norm and tensor nuclear norm regularizers -- while the limited applicability significantly limits their practical usage. To address this challenge, we propose a novel regularizer -- namely, DUality-induced RegulArizer (DURA) -- which is not only effective in improving the performance of existing models but widely applicable to various methods. The major novelty of DURA is based on the observation that, for an existing tensor factorization based KGC model (primal), there is often another distance based KGC model (dual) closely associated with it. Experiments show that DURA yields consistent and significant improvements on benchmarks.
Semi-Structured Deep Piecewise Exponential Models
Venue: arXiv cs.LG 2021
Year: 2021

We propose a versatile framework for survival analysis that combines advanced concepts from statistics with deep learning. The presented framework is based on piecewise exponential models and thereby supports various survival tasks, such as competing risks and multi-state modeling, and further allows for estimation of time-varying effects and time-varying features. To also include multiple data sources and higher-order interaction effects into the model, we embed the model class in a neural network and thereby enable the simultaneous estimation of both inherently interpretable structured regression inputs as well as deep neural network components which can potentially process additional unstructured data sources. A proof of concept is provided by using the framework to predict Alzheimer's disease progression based on tabular and 3D point cloud data and applying it to synthetic data.
On 3-Coloring of $(2P_4,C_5)$-Free Graphs
Venue: arXiv cs.DS 2021
Year: 2021

The 3-coloring of hereditary graph classes has been a deeply-researched problem in the last decade. A hereditary graph class is characterized by a (possibly infinite) list of minimal forbidden induced subgraphs $H_1,H_2,\ldots$; the graphs in the class are called $(H_1,H_2,\ldots)$-free. The complexity of 3-coloring is far from being understood, even for classes defined by a few small forbidden induced subgraphs. For $H$-free graphs, the complexity is settled for any $H$ on up to seven vertices. There are only two unsolved cases on eight vertices, namely $2P_4$ and $P_8$. For $P_8$-free graphs, some partial results are known, but to the best of our knowledge, $2P_4$-free graphs have not been explored yet. In this paper, we show that the 3-coloring problem is polynomial-time solvable on $(2P_4,C_5)$-free graphs.
Motion Generation Using Bilateral Control-Based Imitation Learning with Autoregressive Learning
Venue: arXiv cs.RO 2021
Year: 2021

Robots that can execute various tasks automatically on behalf of humans are becoming an increasingly important focus of research in the field of robotics. Imitation learning has been studied as an efficient and high-performance method, and imitation learning based on bilateral control has been proposed as a method that can realize fast motion. However, because this method cannot implement autoregressive learning, this method may not generate desirable long-term behavior. Therefore, in this paper, we propose a method of autoregressive learning for bilateral control-based imitation learning. A new neural network model for implementing autoregressive learning is proposed. In this study, three types of experiments are conducted to verify the effectiveness of the proposed method. The performance is improved compared to conventional approaches; the proposed method has the highest rate of success. Owing to the structure and autoregressive learning of the proposed model, the proposed method can generate the desirable motion for successful tasks and have a high generalization ability for environmental changes.