OpenRaiser/Intern-Atlas huggingface dataset:
An O^*(2.619^k) algorithm for 4-path vertex cover
Venue: arXiv cs.DS 2019
Year: 2019

In the 4-path vertex cover problem, the input is an undirected graph $G$ and an integer $k$. The goal is to decide whether there is a set of vertices $S$ of size at most $k$ such that every path with 4 vertices in $G$ contains at least one vertex of $S$. In this paper we give a parameterized algorithm for 4-path vertex cover whose time complexity is $O^*(2.619^k)$.
Federated Learning for Mobile Keyboard Prediction
Venue: arXiv cs.CL 2019
Year: 2019

We train a recurrent neural network language model using a distributed, on-device learning framework called federated learning for the purpose of next-word prediction in a virtual keyboard for smartphones. Server-based training using stochastic gradient descent is compared with training on client devices using the Federated Averaging algorithm. The federated algorithm, which enables training on a higher-quality dataset for this use case, is shown to achieve better prediction recall. This work demonstrates the feasibility and benefit of training language models on client devices without exporting sensitive user data to servers. The federated learning environment gives users greater control over the use of their data and simplifies the task of incorporating privacy by default with distributed training and aggregation across a population of client devices.
Bisimilarity of Open Terms in Stream GSOS
Venue: arXiv cs.LO 2019
Year: 2019

Stream GSOS is a specification format for operations and calculi on infinite sequences. The notion of bisimilarity provides a canonical proof technique for equivalence of closed terms in such specifications. In this paper, we focus on open terms, which may contain variables, and which are equivalent whenever they denote the same stream for every possible instantiation of the variables. Our main contribution is to capture equivalence of open terms as bisimilarity on certain Mealy machines, providing a concrete proof technique. Moreover, we introduce an enhancement of this technique, called bisimulation up-to substitutions, and show how to combine it with other up-to techniques to obtain a powerful method for proving equivalence of open terms.
Adaptive Task Allocation for Mobile Edge Learning
Venue: arXiv cs.DC 2019
Year: 2019

This paper aims to establish a new optimization paradigm for implementing realistic distributed learning algorithms, with performance guarantees, on wireless edge nodes with heterogeneous computing and communication capacities. We will refer to this new paradigm as `Mobile Edge Learning (MEL)'. The problem of dynamic task allocation for MEL is considered in this paper with the aim to maximize the learning accuracy, while guaranteeing that the total times of data distribution/aggregation over heterogeneous channels, and local computing iterations at the heterogeneous nodes, are bounded by a preset duration. The problem is first formulated as a quadratically-constrained integer linear problem. Being an NP-hard problem, the paper relaxes it into a non-convex problem over real variables. We thus proposed two solutions based on deriving analytical upper bounds of the optimal solution of this relaxed problem using Lagrangian analysis and KKT conditions, and the use of suggest-and-improve starting from equal batch allocation, respectively. The merits of these proposed solutions are exhibited by comparing their performances to both numerical approaches and the equal task allocation approach.
EASYFLOW: Keep Ethereum Away From Overflow
Venue: arXiv cs.SE 2019
Year: 2019

While Ethereum smart contracts enabled a wide range of blockchain applications, they are extremely vulnerable to different forms of security attacks. Due to the fact that transactions to smart contracts commonly involve cryptocurrency transfer, any successful attacks can lead to money loss or even financial disorder. In this paper, we focus on the overflow attacks in Ethereum , mainly because they widely rooted in many smart contracts and comparatively easy to exploit. We have developed EASYFLOW , an overflow detector at Ethereum Virtual Machine level. The key insight behind EASYFLOW is a taint analysis based tracking technique to analyze the propagation of involved taints. Specifically, EASYFLOW can not only divide smart contracts into safe contracts, manifested overflows, well-protected overflows and potential overflows, but also automatically generate transactions to trigger potential overflows. In our preliminary evaluation, EASYFLOW managed to find potentially vulnerable Ethereum contracts with little runtime overhead.
Skeptical Deep Learning with Distribution Correction
Venue: arXiv cs.LG 2019
Year: 2019

Recently deep neural networks have been successfully used for various classification tasks, especially for problems with massive perfectly labeled training data. However, it is often costly to have large-scale credible labels in real-world applications. One solution is to make supervised learning robust with imperfectly labeled input. In this paper, we develop a distribution correction approach that allows deep neural networks to avoid overfitting imperfect training data. Specifically, we treat the noisy input as samples from an incorrect distribution, which will be automatically corrected during our training process. We test our approach on several classification datasets with elaborately generated noisy labels. The results show significantly higher prediction and recovery accuracy with our approach compared to alternative methods.
Changing the Image Memorability: From Basic Photo Editing to GANs
Venue: arXiv cs.CV 2019
Year: 2019

Memorability is considered to be an important characteristic of visual content, whereas for advertisement and educational purposes it is often crucial. Despite numerous studies on understanding and predicting image memorability, there are almost no achievements in memorability modification. In this work, we study two approaches to image editing - GAN and classical image processing - and show their impact on memorability. The visual features which influence memorability directly stay unknown till now, hence it is impossible to control it manually. As a solution, we let GAN learn it deeply using labeled data, and then use it for conditional generation of new images. By analogy with algorithms which edit facial attributes, we consider memorability as yet another attribute and operate with it in the same way. Obtained data is also interesting for analysis, simply because there are no real-world examples of successful change of image memorability while preserving its other attributes. We believe this may give many new answers to the question "what makes an image memorable?" Apart from that we also study the influence of conventional photo-editing tools (Photoshop, Instagram, etc.) used daily by a wide audience on memorability. In this case, we start from real practical methods and study it using statistics and recent advances in memorability prediction. Photographers, designers, and advertisers will benefit from the results of this study directly.
MD-GAN: Multi-Discriminator Generative Adversarial Networks for Distributed Datasets
Venue: arXiv cs.LG 2019
Year: 2019

A recent technical breakthrough in the domain of machine learning is the discovery and the multiple applications of Generative Adversarial Networks (GANs). Those generative models are computationally demanding, as a GAN is composed of two deep neural networks, and because it trains on large datasets. A GAN is generally trained on a single server. In this paper, we address the problem of distributing GANs so that they are able to train over datasets that are spread on multiple workers. MD-GAN is exposed as the first solution for this problem: we propose a novel learning procedure for GANs so that they fit this distributed setup. We then compare the performance of MD-GAN to an adapted version of Federated Learning to GANs, using the MNIST and CIFAR10 datasets. MD-GAN exhibits a reduction by a factor of two of the learning complexity on each worker node, while providing better performances than federated learning on both datasets. We finally discuss the practical implications of distributing GANs.
An Overview of Computational Approaches for Interpretation Analysis
Venue: arXiv cs.AI 2019
Year: 2019

It is said that beauty is in the eye of the beholder. But how exactly can we characterize such discrepancies in interpretation? For example, are there any specific features of an image that makes person A regard an image as beautiful while person B finds the same image displeasing? Such questions ultimately aim at explaining our individual ways of interpretation, an intention that has been of fundamental importance to the social sciences from the beginning. More recently, advances in computer science brought up two related questions: First, can computational tools be adopted for analyzing ways of interpretation? Second, what if the "beholder" is a computer model, i.e., how can we explain a computer model's point of view? Numerous efforts have been made regarding both of these points, while many existing approaches focus on particular aspects and are still rather separate. With this paper, in order to connect these approaches we introduce a theoretical framework for analyzing interpretation, which is applicable to interpretation of both human beings and computer models. We give an overview of relevant computational approaches from various fields, and discuss the most common and promising application areas. The focus of this paper lies on interpretation of text and image data, while many of the presented approaches are applicable to other types of data as well.
Feedback-Aware Precoding for Millimeter Wave Massive MIMO Systems
Venue: arXiv cs.IT 2019
Year: 2019

Millimeter wave (mmWave) communication is a promising solution for coping with the ever-increasing mobile data traffic because of its large bandwidth. To enable a sufficient link margin, a large antenna array employing directional beamforming, which is enabled by the availability of channel state information at the transmitter (CSIT), is required. However, CSIT acquisition for mmWave channels introduces a huge feedback overhead due to the typically large number of transmit and receive antennas. Leveraging properties of mmWave channels, this paper proposes a precoding strategy which enables a flexible adjustment of the feedback overhead. In particular, the optimal unconstrained precoder is approximated by selecting a variable number of elements from a basis that is constructed as a function of the transmitter array response, where the number of selected basis elements can be chosen according to the feedback constraint. Simulation results show that the proposed precoding scheme can provide a near-optimal solution if a higher feedback overhead can be afforded. For a low overhead, it can still provide a good approximation of the optimal precoder.
Understanding the Motivations, Challenges and Needs of Blockchain Software Developers: A Survey
Venue: arXiv cs.SE 2019
Year: 2019

The blockchain technology has potential applications in various areas such as smart-contracts, Internet of Things (IoT), land registry, supply chain management, storing medical data, and identity management. Although the Github currently hosts more than six thousand active Blockchain software (BCS) projects, few software engineering research has investigated these projects and its' contributors. Although the number of BCS projects is growing rapidly, the motivations, challenges, and needs of BCS developers remain a puzzle. Therefore, the primary objective of this study is to understand the motivations, challenges, and needs of BCS developers and analyze the differences between BCS and non-BCS development. On this goal, we sent an online survey to 1,604 active BCS developers identified via mining the Github repositories of 145 popular BCS projects. The survey received 156 responses that met our criteria for analysis. The results suggest that the majority of the BCS developers are experienced in non-BCS development and are primarily motivated by the ideology of creating a decentralized financial system. Although most of the BCS projects are Open Source Software (OSS) projects by nature, more than 93% of our respondents found BCS development somewhat different from a non-BCS development as BCS projects have higher emphasis on security and reliability than most of the non-BCS projects. Other differences include: higher costs of defects, decentralized and hostile environment, technological complexity, and difficulty in upgrading the software after release. Software development tools that are tuned for non-BCS development are inadequate for BCS and the ecosystem needs an array of new or improved tools, such as: customized IDE for BCS development tasks, debuggers for smart-contracts, testing support, easily deployable simulators, and BCS domain specific design notations.
Integrating Multiple Receptive Fields through Grouped Active Convolution
Venue: arXiv cs.CV 2019
Year: 2019

Convolutional networks have achieved great success in various vision tasks. This is mainly due to a considerable amount of research on network structure. In this study, instead of focusing on architectures, we focused on the convolution unit itself. The existing convolution unit has a fixed shape and is limited to observing restricted receptive fields. In earlier work, we proposed the active convolution unit (ACU), which can freely define its shape and learn by itself. In this paper, we provide a detailed analysis of the previously proposed unit and show that it is an efficient representation of a sparse weight convolution. Furthermore, we extend an ACU to a grouped ACU, which can observe multiple receptive fields in one layer. We found that the performance of a naive grouped convolution is degraded by increasing the number of groups; however, the proposed unit retains the accuracy even though the number of parameters decreases. Based on this result, we suggest a depthwise ACU, and various experiments have shown that our unit is efficient and can replace the existing convolutions.
Massive MIMO-based Localization and Mapping Exploiting Phase Information of Multipath Components
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we present a robust multipath-based localization and mapping framework that exploits the phases of specular multipath components (MPCs) using a massive multiple-input multiple-output (MIMO) array at the base station. Utilizing the phase information related to the propagation distances of the MPCs enables the possibility of localization with extraordinary accuracy even with limited bandwidth. The specular MPC parameters along with the parameters of the noise and the dense multipath component (DMC) are tracked using an extended Kalman filter (EKF), which enables to preserve the distance-related phase changes of the MPC complex amplitudes. The DMC comprises all non-resolvable MPCs, which occur due to finite measurement aperture. The estimation of the DMC parameters enhances the estimation quality of the specular MPCs and therefore also the quality of localization and mapping. The estimated MPC propagation distances are subsequently used as input to a distance-based localization and mapping algorithm. This algorithm does not need prior knowledge about the surrounding environment and base station position. The performance is demonstrated with real radio-channel measurements using an antenna array with 128 ports at the base station side and a standard cellular signal bandwidth of 40 MHz. The results show that high accuracy localization is possible even with such a low bandwidth.
Minimizing Energy Consumption and Peak Power of Series Elastic Actuators: a Convex Optimization Framework for Elastic Element Design
Venue: arXiv cs.RO 2019
Year: 2019

Compared to rigid actuators, Series Elastic Actuators (SEAs) offer a potential reduction of motor energy consumption and peak power, though these benefits are highly dependent on the design of the torque-elongation profile of the elastic element. In the case of linear springs, natural dynamics is a traditional method for this design, but it has two major limitations: arbitrary load trajectories are difficult or impossible to analyze and it does not consider actuator constraints. Parametric optimization is also a popular design method that addresses these limitations, but solutions are only optimal within the space of the parameters. To overcome these limitations, we propose a non-parametric convex optimization program for the design of the nonlinear elastic element that minimizes energy consumption and peak power for an arbitrary periodic reference trajectory. To obtain convexity, we introduce a convex approximation to the expression of peak power; energy consumption is shown to be convex without approximation. The combination of peak power and energy consumption in the cost function leads to a multiobjective convex optimization framework that comprises the main contribution of this paper. As a case study, we recover the elongation-torque profile of a cubic spring, given its natural oscillation as the reference load. We then design nonlinear SEAs for an ankle prosthesis that minimize energy consumption and peak power for different trajectories and extend the range of achievable tasks when subject to actuator constraints.
Approximating minimum representations of key Horn functions
Venue: arXiv cs.DS 2019
Year: 2019

Horn functions form a subclass of Boolean functions and appear in many different areas of computer science and mathematics as a general tool to describe implications and dependencies. Finding minimum sized representations for such functions with respect to most commonly used measures is a computationally hard problem that remains hard even for the important subclass of key Horn functions. In this paper we provide logarithmic factor approximation algorithms for key Horn functions with respect to all measures studied in the literature for which the problem is known to be hard.
A Phase Variable Approach for Improved Rhythmic and Non-Rhythmic Control of a Powered Knee-Ankle Prosthesis
Venue: arXiv cs.RO 2019
Year: 2019

Although there has been recent progress in control of multi-joint prosthetic legs for rhythmic tasks such as walking, control of these systems for non-rhythmic motions and general real-world maneuvers is still an open problem. In this article, we develop a new controller that is capable of both rhythmic (constant-speed) walking, transitions between speeds and/or tasks, and some common volitional leg motions. We introduce a new piecewise holonomic phase variable, which, through a finite state machine, forms the basis of our controller. The phase variable is constructed by measuring the thigh angle, and the transitions in the finite state machine are formulated through sensing foot contact along with attributes of a nominal reference gait trajectory. The controller was implemented on a powered knee-ankle prosthesis and tested with a transfemoral amputee subject, who successfully performed a wide range of rhythmic and non-rhythmic tasks, including slow and fast walking, quick start and stop, backward walking, walking over obstacles, and kicking a soccer ball. Use of the powered leg resulted in clinically significant reductions in amputee compensations for rhythmic tasks (including vaulting and hip circumduction) when compared to use of the take-home passive leg. In addition, considerable improvements were also observed in the performance for non-rhythmic tasks. The proposed approach is expected to provide a better understanding of rhythmic and non-rhythmic motions in a unified framework, which in turn can lead to more reliable control of multi-joint prostheses for a wider range of real-world tasks.
Team NimbRo at MBZIRC 2017: Fast Landing on a Moving Target and Treasure Hunting with a Team of MAVs
Venue: arXiv cs.RO 2019
Year: 2019

The Mohamed Bin Zayed International Robotics Challenge (MBZIRC) 2017 has defined ambitious new benchmarks to advance the state-of-the-art in autonomous operation of ground-based and flying robots. This article covers our approaches to solve the two challenges that involved micro aerial vehicles (MAV). Challenge 1 required reliable target perception, fast trajectory planning, and stable control of an MAV in order to land on a moving vehicle. Challenge 3 demanded a team of MAVs to perform a search and transportation task, coined "Treasure Hunt", which required mission planning and multi-robot coordination as well as adaptive control to account for the additional object weight. We describe our base MAV setup and the challenge-specific extensions, cover the camera-based perception, explain control and trajectory-planning in detail, and elaborate on mission planning and team coordination. We evaluated our systems in simulation as well as with real-robot experiments during the competition in Abu Dhabi. With our system, we-as part of the larger team NimbRo-won the MBZIRC Grand Challenge and achieved a third place in both subchallenges involving flying robots.
Aequitas: A Bias and Fairness Audit Toolkit
Venue: arXiv cs.LG 2019
Year: 2019

Recent work has raised concerns on the risk of unintended bias in AI systems being used nowadays that can affect individuals unfairly based on race, gender or religion, among other possible characteristics. While a lot of bias metrics and fairness definitions have been proposed in recent years, there is no consensus on which metric/definition should be used and there are very few available resources to operationalize them. Therefore, despite recent awareness, auditing for bias and fairness when developing and deploying AI systems is not yet a standard practice. We present Aequitas, an open source bias and fairness audit toolkit that is an intuitive and easy to use addition to the machine learning workflow, enabling users to seamlessly test models for several bias and fairness metrics in relation to multiple population sub-groups. Aequitas facilitates informed and equitable decisions around developing and deploying algorithmic decision making systems for both data scientists, machine learning researchers and policymakers.
Controllability, Multiplexing, and Transfer Learning in Networks using Evolutionary Learning
Venue: arXiv cs.NE 2019
Year: 2019

Networks are fundamental building blocks for representing data, and computations. Remarkable progress in learning in structurally defined (shallow or deep) networks has recently been achieved. Here we introduce evolutionary exploratory search and learning method of topologically flexible networks under the constraint of producing elementary computational steady-state input-output operations. Our results include; (1) the identification of networks, over four orders of magnitude, implementing computation of steady-state input-output functions, such as a band-pass filter, a threshold function, and an inverse band-pass function. Next, (2) the learned networks are technically controllable as only a small number of driver nodes are required to move the system to a new state. Furthermore, we find that the fraction of required driver nodes is constant during evolutionary learning, suggesting a stable system design. (3), our framework allows multiplexing of different computations using the same network. For example, using a binary representation of the inputs, the network can readily compute three different input-output functions. Finally, (4) the proposed evolutionary learning demonstrates transfer learning. If the system learns one function A, then learning B requires on average less number of steps as compared to learning B from tabula rasa. We conclude that the constrained evolutionary learning produces large robust controllable circuits, capable of multiplexing and transfer learning. Our study suggests that network-based computations of steady-state functions, representing either cellular modules of cell-to-cell communication networks or internal molecular circuits communicating within a cell, could be a powerful model for biologically inspired computing. This complements conceptualizations such as attractor based models, or reservoir computing.