OpenRaiser/Intern-Atlas huggingface dataset:
Cold-start recommendations in Collective Matrix Factorization
Venue: arXiv cs.IR 2020
Year: 2020

This work explores the ability of collective matrix factorization models in recommender systems to make predictions about users and items for which there is side information available but no feedback or interactions data, and proposes a new formulation with a faster cold-start prediction formula that can be used in real-time systems. While these cold-start recommendations are not as good as warm-start ones, they were found to be of better quality than non-personalized recommendations, and predictions about new users were found to be more reliable than those about new items. The formulation proposed here resulted in improved cold-start recommendations in many scenarios, at the expense of worse warm-start ones.
A Roadmap for Robust End-to-End Alignment
Venue: arXiv cs.AI 2020
Year: 2020

This paper discussed the {\it robust alignment} problem, that is, the problem of aligning the goals of algorithms with human preferences. It presented a general roadmap to tackle this issue. Interestingly, this roadmap identifies 5 critical steps, as well as many relevant aspects of these 5 steps. In other words, we have presented a large number of hopefully more tractable subproblems that readers are highly encouraged to tackle. Hopefully, this combination allows to better highlight the most pressing problems, how every expertise can be best used to, and how combining the solutions to subproblems might add up to solve robust alignment.
On the Need of Preserving Order of Data When Validating Within-Project Defect Classifiers
Venue: arXiv cs.SE 2020
Year: 2020

[Context] The use of defect prediction models, such as classifiers, can support testing resource allocations by using data of the previous releases of the same project for predicting which software components are likely to be defective. A validation technique, hereinafter technique defines a specific way to split available data in training and test sets to measure a classifier accuracy. Time-series techniques have the unique ability to preserve the temporal order of data; i.e., preventing the testing set to have data antecedent to the training set. [Aim] The aim of this paper is twofold: first we check if there is a difference in the classifiers accuracy measured by time-series versus non-time-series techniques. Afterward, we check for a possible reason for this difference, i.e., if defect rates change across releases of a project. [Method] Our method consists of measuring the accuracy, i.e., AUC, of 10 classifiers on 13 open and two closed projects by using three validation techniques, namely cross validation, bootstrap, and walk-forward, where only the latter is a time-series technique. [Results] We find that the AUC of the same classifier used on the same project and measured by 10-fold varies compared to when measured by walk-forward in the range [-0.20, 0.22], and it is statistically different in 45% of the cases. Similarly, the AUC measured by bootstrap varies compared to when measured by walk-forward in the range [-0.17, 0.43], and it is statistically different in 56% of the cases. [Conclusions] We recommend choosing the technique to be used by carefully considering the conclusions to draw, the property of the available datasets, and the level of realism with the classifier usage scenario.
Information-Theoretic Privacy in Distributed Average Consensus
Venue: arXiv cs.SY 2020
Year: 2020

We present a distributed average consensus protocol that preserves the privacy of agents' inputs. Unlike the differential privacy mechanisms, the presented protocol does not affect the accuracy of the output. It is shown that the protocol preserves the information-theoretic privacy of the agents' inputs against colluding passive adversarial (or honest-but-curious) agents in the network, if the adversarial agents do not constitute a vertex cut in the underlying communication network. This implies that we can guarantee information-theoretic privacy of all the honest agents' inputs against $t$ arbitrary colluding passive adversarial agents if the network is $(t+1)$-connected. The protocol is constructed by composing a distributed privacy mechanism that we propose with any (non-private) distributed average consensus algorithm.
Are adversarial examples inevitable?
Venue: arXiv cs.LG 2020
Year: 2020

A wide range of defenses have been proposed to harden neural networks against adversarial attacks. However, a pattern has emerged in which the majority of adversarial defenses are quickly broken by new attacks. Given the lack of success at generating robust defenses, we are led to ask a fundamental question: Are adversarial attacks inevitable? This paper analyzes adversarial examples from a theoretical perspective, and identifies fundamental bounds on the susceptibility of a classifier to adversarial attacks. We show that, for certain classes of problems, adversarial examples are inescapable. Using experiments, we explore the implications of theoretical guarantees for real-world problems and discuss how factors such as dimensionality and image complexity limit a classifier's robustness against adversarial examples.
Weak Control for Human-in-the-loop Systems
Venue: arXiv cs.SY 2020
Year: 2020

In this letter, we propose a control framework for human-in-the-loop systems, in which many human decision makers are involved in the feedback loop composed of a plant and a controller. The novelty of the framework is that the decision makers are weakly controlled; in other words, they receive a set of admissible control actions from the controller and choose one of them in accordance with their private preferences. For example, the decision makers can decide their actions to minimize their own costs or by simply relying on their experience and intuition. A class of controllers which output set-valued signals is proposed, and it is shown that the overall control system is stable independently of the decisions made by the humans. Finally, a learning algorithm is applied to the controller that updates the controller parameters to reduce the achievable minimal costs for the decision makers. Effective use of the algorithm is demonstrated in a numerical experiment.
Analysis of the Generalization Error: Empirical Risk Minimization over Deep Artificial Neural Networks Overcomes the Curse of Dimensionality in the Numerical Approximation of Black-Scholes Partial Differential Equations
Venue: arXiv cs.LG 2020
Year: 2020

The development of new classification and regression algorithms based on empirical risk minimization (ERM) over deep neural network hypothesis classes, coined deep learning, revolutionized the area of artificial intelligence, machine learning, and data analysis. In particular, these methods have been applied to the numerical solution of high-dimensional partial differential equations with great success. Recent simulations indicate that deep learning-based algorithms are capable of overcoming the curse of dimensionality for the numerical solution of Kolmogorov equations, which are widely used in models from engineering, finance, and the natural sciences. The present paper considers under which conditions ERM over a deep neural network hypothesis class approximates the solution of a $d$-dimensional Kolmogorov equation with affine drift and diffusion coefficients and typical initial values arising from problems in computational finance up to error $\varepsilon$. We establish that, with high probability over draws of training samples, such an approximation can be achieved with both the size of the hypothesis class and the number of training samples scaling only polynomially in $d$ and $\varepsilon^{-1}$. It can be concluded that ERM over deep neural network hypothesis classes overcomes the curse of dimensionality for the numerical solution of linear Kolmogorov equations with affine coefficients.
Combining imagination and heuristics to learn strategies that generalize
Venue: arXiv cs.AI 2020
Year: 2020

Deep reinforcement learning can match or exceed human performance in stable contexts, but with minor changes to the environment artificial networks, unlike humans, often cannot adapt. Humans rely on a combination of heuristics to simplify computational load and imagination to extend experiential learning to new and more challenging environments. Motivated by theories of the hierarchical organization of the human prefrontal networks, we have developed a model of hierarchical reinforcement learning that combines both heuristics and imagination into a stumbler-strategist network. We test performance of this network using Wythoff's game, a gridworld environment with a known optimal strategy. We show that a heuristic labeling of each position as hot or cold, combined with imagined play, both accelerates learning and promotes transfer to novel games, while also improving model interpretability.
Improved Basic Block Reordering
Venue: arXiv cs.PL 2020
Year: 2020

Basic block reordering is an important step for profile-guided binary optimization. The state-of-the-art goal for basic block reordering is to maximize the number of fall-through branches. However, we demonstrate that such orderings may impose suboptimal performance on instruction and I-TLB caches. We propose a new algorithm that relies on a model combining the effects of fall-through and caching behavior. As details of modern processor caching is quite complex and often unknown, we show how to use machine learning in selecting parameters that best trade off different caching effects to maximize binary performance. An extensive evaluation on a variety of applications, including Facebook production workloads, the open-source compilers Clang and GCC, and SPEC CPU benchmarks, indicate that the new method outperforms existing block reordering techniques, improving the resulting performance of applications with large code size. We have open sourced the code of the new algorithm as a part of a post-link binary optimization tool, BOLT.
Channel Polarization through the Lens of Blackwell Measures
Venue: arXiv cs.IT 2020
Year: 2020

Each memoryless binary-input channel (BIC) can be uniquely described by its Blackwell measure, which is a probability distribution on the unit interval $[0,1]$ with mean $1/2$. Conversely, any such probability distribution defines a BIC. The evolution of the Blackwell measure under Arikan's polar transform is derived for general BICs, and is analogous to density evolution as cited in the literature. The present analysis emphasizes functional equations. Consequently, the evolution of a variety of channel functionals is characterized, including the symmetric capacity, Bhattacharyya parameter, moments of information density, Hellinger affinity, Gallager's reliability function, the Hirschfeld-Gebelein-Renyi maximal correlation, and the Bayesian information gain. The evolution of measure is specialized for symmetric BICs according to their decomposition into binary symmetric (sub)-channels (BSCs), which simplifies iterative computations and the construction of polar codes. It is verified that, as a consequence of the Blackwell--Sherman--Stein theorem, all channel functionals $\mathrm{I}_f$ that can be expressed as an expectation of a convex function $f$ with respect to the Blackwell measure of a channel polarize in each iteration due to the polar transformation on the class of symmetric BICs. Moreover, for $f$ either convex or non-convex, a necessary and sufficient condition is established to determine whether the random process associated with each $\mathrm{I}_f$ is a martingale, submartingale, or supermartingale. Represented via functional inequalities in terms of $f$, this condition is numerically verifiable for all $\mathrm{I}_f$, and can generate analytical proofs. To exhibit one such proof, it is shown that the random process associated with the squared maximal correlation parameter is a supermartingale, and converges almost surely on the unit interval $[0,1]$.
High Throughput Cryptocurrency Routing in Payment Channel Networks
Venue: arXiv cs.NI 2020
Year: 2020

Despite growing adoption of cryptocurrencies, making fast payments at scale remains a challenge. Payment channel networks (PCNs) such as the Lightning Network have emerged as a viable scaling solution. However, completing payments on PCNs is challenging: payments must be routed on paths with sufficient funds. As payments flow over a single channel (link) in the same direction, the channel eventually becomes depleted and cannot support further payments in that direction; hence, naive routing schemes like shortest-path routing can deplete key payment channels and paralyze the system. Today's PCNs also route payments atomically, worsening the problem. In this paper, we present Spider, a routing solution that "packetizes" transactions and uses a multi-path transport protocol to achieve high-throughput routing in PCNs. Packetization allows Spider to complete even large transactions on low-capacity payment channels over time, while the multi-path congestion control protocol ensures balanced utilization of channels and fairness across flows. Extensive simulations comparing Spider with state-of-the-art approaches shows that Spider requires less than 25% of the funds to successfully route over 95% of transactions on balanced traffic demands, and offloads 4x more transactions onto the PCN on imbalanced demands.
Analysis of Population Functional Connectivity Data via Multilayer Network Embeddings
Venue: arXiv cs.SI 2020
Year: 2020

Population analyses of functional connectivity have provided a rich understanding of how brain function differs across time, individual, and cognitive task. An important but challenging task in such population analyses is the identification of reliable features that describe the function of the brain, while accounting for individual heterogeneity. Our work is motivated by two particularly important challenges in this area: first, how can one analyze functional connectivity data over populations of individuals, and second, how can one use these analyses to infer group similarities and differences. Motivated by these challenges, we model population connectivity data as a multilayer network and develop the multi-node2vec algorithm, an efficient and scalable embedding method that automatically learns continuous node feature representations from multilayer networks. We use multi-node2vec to analyze resting state fMRI scans over a group of 74 healthy individuals and 60 patients with schizophrenia. We demonstrate how multilayer network embeddings can be used to visualize, cluster, and classify functional regions of the brain for these individuals. We furthermore compare the multilayer network embeddings of the two groups. We identify significant differences between the groups in the default mode network and salience network - findings that are supported by the triple network model theory of cognitive organization. Our findings reveal that multi-node2vec is a powerful and reliable method for analyzing multilayer networks.
Is rotation forest the best classifier for problems with continuous features?
Venue: arXiv cs.LG 2020
Year: 2020

In short, our experiments suggest that yes, on average, rotation forest is better than the most common alternatives when all the attributes are real-valued. Rotation forest is a tree based ensemble that performs transforms on subsets of attributes prior to constructing each tree. We present an empirical comparison of classifiers for problems with only real-valued features. We evaluate classifiers from three families of algorithms: support vector machines; tree-based ensembles; and neural networks tuned with a large grid search. We compare classifiers on unseen data based on the quality of the decision rule (using classification error) the ability to rank cases (area under the receiver operating characteristic) and the probability estimates (using negative log likelihood). We conclude that, in answer to the question posed in the title, yes, rotation forest is significantly more accurate on average than competing techniques when compared on three distinct sets of datasets. Further, we assess the impact of the design features of rotation forest through an ablative study that transforms random forest into rotation forest. We identify the major limitation of rotation forest as its scalability, particularly in number of attributes. To overcome this problem we develop a model to predict the train time of the algorithm and hence propose a contract version of rotation forest where a run time cap is imposed {\em a priori}. We demonstrate that on large problems rotation forest can be made an order of magnitude faster without significant loss of accuracy. We also show that there is no real benefit (on average) from tuning rotation forest. We maintain that without any domain knowledge to indicate an algorithm preference, rotation forest should be the default algorithm of choice for problems with continuous attributes.
Bridging the Gap Between Safety and Real-Time Performance in Receding-Horizon Trajectory Design for Mobile Robots
Venue: arXiv cs.RO 2020
Year: 2020

To operate with limited sensor horizons in unpredictable environments, autonomous robots use a receding-horizon strategy to plan trajectories, wherein they execute a short plan while creating the next plan. However, creating safe, dynamically-feasible trajectories in real time is challenging; and, planners must ensure persistent feasibility, meaning a new trajectory is always available before the previous one has finished executing. Existing approaches make a tradeoff between model complexity and planning speed, which can require sacrificing guarantees of safety and dynamic feasibility. This work presents the Reachability-based Trajectory Design (RTD) method for trajectory planning. RTD begins with an offline Forward Reachable Set (FRS) computation of a robot's motion when tracking parameterized trajectories; the FRS provably bounds tracking error. At runtime, the FRS is used to map obstacles to parameterized trajectories, allowing RTD to select a safe trajectory at every planning iteration. RTD prescribes an obstacle representation to ensure that obstacle constraints can be created and evaluated in real time while maintaining safety. Persistent feasibility is achieved by prescribing a minimum sensor horizon and a minimum duration for the planned trajectories. A system decomposition approach is used to improve the tractability of computing the FRS, allowing RTD to create more complex plans at runtime. RTD is compared in simulation with Rapidly-Exploring Random Trees and Nonlinear Model-Predictive Control. RTD is also demonstrated in randomly-crafted environments on two hardware platforms: a differential-drive Segway, and a car-like Rover. The proposed method is safe and persistently feasible across thousands of simulations and dozens of real-world hardware demos.
Bayesian functional optimisation with shape prior
Venue: arXiv cs.LG 2020
Year: 2020

Real world experiments are expensive, and thus it is important to reach a target in minimum number of experiments. Experimental processes often involve control variables that changes over time. Such problems can be formulated as a functional optimisation problem. We develop a novel Bayesian optimisation framework for such functional optimisation of expensive black-box processes. We represent the control function using Bernstein polynomial basis and optimise in the coefficient space. We derive the theory and practice required to dynamically adjust the order of the polynomial degree, and show how prior information about shape can be integrated. We demonstrate the effectiveness of our approach for short polymer fibre design and optimising learning rate schedules for deep networks.
Combinatorial and Structural Results for gamma-Psi-dimensions
Venue: arXiv cs.LG 2020
Year: 2020

This article deals with the generalization performance of margin multi-category classifiers, when minimal learnability hypotheses are made. In that context, the derivation of a guaranteed risk is based on the handling of capacity measures belonging to three main families: Rademacher/Gaussian complexities, metric entropies and scale-sensitive combinatorial dimensions. The scale-sensitive combinatorial dimensions dedicated to the classifiers of this kind are the gamma-Psi-dimensions. We introduce the combinatorial and structural results needed to involve them in the derivation of guaranteed risks and establish the corresponding upper bounds on the metric entropies and the Rademacher complexity. Two major conclusions can be drawn: 1. the gamma-Psi-dimensions always bring an improvement compared to the use of the fat-shattering dimension of the class of margin functions; 2. thanks to their capacity to take into account basic features of the classifier, they represent a promising alternative to performing the transition from the multi-class case to the binary one with covering numbers.
A Survey of Learning Causality with Data: Problems and Methods
Venue: arXiv cs.AI 2020
Year: 2020

This work considers the question of how convenient access to copious data impacts our ability to learn causal effects and relations. In what ways is learning causality in the era of big data different from -- or the same as -- the traditional one? To answer this question, this survey provides a comprehensive and structured review of both traditional and frontier methods in learning causality and relations along with the connections between causality and machine learning. This work points out on a case-by-case basis how big data facilitates, complicates, or motivates each approach.
Underwater Caging and Capture for Autonomous Underwater Vehicles
Venue: arXiv cs.RO 2020
Year: 2020

In this paper, we consider the problem of caging and eventual capture of an underwater entity using multiple Autonomous Underwater Vehicles (AUVs) in a 3D water volume We solve this problem both with and without taking bathymetry into account. Our proposed algorithm for range-limited sensing in 3D environments captures a finite-speed entity based on sparse and irregular observations. After an isolated initial sighting of the entity, the uncertainty of its whereabouts grows while deployment of the AUV system is underway. To contain the entity, an initial cage, or barrier of sensing footprints, is created around the initial sighting, using islands and other terrain as part of the cage if available. After the initial cage is established, the system waits for a second sighting, and the possible opportunity to create a smaller, shrinkable cage. This process continues until at some point it is possible to create this smaller cage, resulting in capture, meaning the entity is sensed directly and continuously. We present a set of algorithms for addressing the scenario above, and illustrate their performance on a set of examples. The proposed algorithm is a combination of solutions to the min-cut problem, the set cover problem, the linear bottleneck assignment problem and the Thomson problem.