OpenRaiser/Intern-Atlas huggingface dataset:
MaskFace: multi-task face and landmark detector
Venue: arXiv cs.CV 2020
Year: 2020

Currently in the domain of facial analysis single task approaches for face detection and landmark localization dominate. In this paper we draw attention to multi-task models solving both tasks simultaneously. We present a highly accurate model for face and landmark detection. The method, called MaskFace, extends previous face detection approaches by adding a keypoint prediction head. The new keypoint head adopts ideas of Mask R-CNN by extracting facial features with a RoIAlign layer. The keypoint head adds small computational overhead in the case of few faces in the image while improving the accuracy dramatically. We evaluate MaskFace's performance on a face detection task on the AFW, PASCAL face, FDDB, WIDER FACE datasets and a landmark localization task on the AFLW, 300W datasets. For both tasks MaskFace achieves state-of-the-art results outperforming many of single-task and multi-task models.
Integer Linear Programming for the Tutor Allocation Problem: A Practical Case in a British University
Venue: arXiv cs.CY 2020
Year: 2020

In the Tutor Allocation Problem, the objective is to assign a set of tutors to a set of workshops in order to maximize tutors' preferences. The problem is solved every year by many universities, each having its own specific set of constraints. In this work, we study the tutor allocation in the School of Mathematics at the University of Edinburgh, and solve it with an integer linear programming model. We tested the model on the 2019/2020 case, obtaining a significant improvement with respect to the manual assignment in use. Further tests on randomly created instances show that the model can be used to address cases of broad interest. We also provide meaningful insights on how input parameters, such as the number of workshop locations and the length of the tutors' preference list, might affect the performance of the model and the average number of preferences satisfied.
Experience Augmentation: Boosting and Accelerating Off-Policy Multi-Agent Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

Exploration of the high-dimensional state action space is one of the biggest challenges in Reinforcement Learning (RL), especially in multi-agent domain. We present a novel technique called Experience Augmentation, which enables a time-efficient and boosted learning based on a fast, fair and thorough exploration to the environment. It can be combined with arbitrary off-policy MARL algorithms and is applicable to either homogeneous or heterogeneous environments. We demonstrate our approach by combining it with MADDPG and verifing the performance in two homogeneous and one heterogeneous environments. In the best performing scenario, the MADDPG with experience augmentation reaches to the convergence reward of vanilla MADDPG with 1/4 realistic time, and its convergence beats the original model by a significant margin. Our ablation studies show that experience augmentation is a crucial ingredient which accelerates the training process and boosts the convergence.
k-sums: another side of k-means
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, the decades-old clustering method k-means is revisited. The original distortion minimization model of k-means is addressed by a pure stochastic minimization procedure. In each step of the iteration, one sample is tentatively reallocated from one cluster to another. It is moved to another cluster as long as the reallocation allows the sample to be closer to the new centroid. This optimization procedure converges faster to a better local minimum over k-means and many of its variants. This fundamental modification over the k-means loop leads to the redefinition of a family of k-means variants. Moreover, a new target function that minimizes the summation of pairwise distances within clusters is presented. We show that it could be solved under the same stochastic optimization procedure. This minimization procedure built upon two minimization models outperforms k-means and its variants considerably with different settings and on different datasets.
Applying Genetic Programming to Improve Interpretability in Machine Learning Models
Venue: arXiv cs.LG 2020
Year: 2020

Explainable Artificial Intelligence (or xAI) has become an important research topic in the fields of Machine Learning and Deep Learning. In this paper, we propose a Genetic Programming (GP) based approach, named Genetic Programming Explainer (GPX), to the problem of explaining decisions computed by AI systems. The method generates a noise set located in the neighborhood of the point of interest, whose prediction should be explained, and fits a local explanation model for the analyzed sample. The tree structure generated by GPX provides a comprehensible analytical, possibly non-linear, symbolic expression which reflects the local behavior of the complex model. We considered three machine learning techniques that can be recognized as complex black-box models: Random Forest, Deep Neural Network and Support Vector Machine in twenty data sets for regression and classifications problems. Our results indicate that the GPX is able to produce more accurate understanding of complex models than the state of the art. The results validate the proposed approach as a novel way to deploy GP to improve interpretability.
RIOT-POLICE: An implementation of spatial memory safety for the RIOT operating system
Venue: arXiv cs.PL 2020
Year: 2020

We present an integration of a safe C dialect, Checked C, for the Internet of Things operating system RIOT. We utilize this integration to convert parts of the RIOT network stack to Checked C, thereby achieving spatial memory safety in these code parts. Similar to prior research done on IoT operating systems and safe C dialects, our integration of Checked C remains entirely optional, i.e. compilation with a standard C compiler not supporting the Checked C language extension is still possible. We believe this to be the first proposed integration of a safe C dialect for the RIOT operating system. We present an incremental process for converting RIOT modules to Checked C, evaluate the overhead introduced by the conversions, and discuss our general experience with utilizing Checked C in the Internet of Things domain.
Efficient Process-to-Node Mapping Algorithms for Stencil Computations
Venue: arXiv cs.DC 2020
Year: 2020

Good process-to-compute-node mappings can be decisive for well performing HPC applications. A special, important class of process-to-node mapping problems is the problem of mapping processes that communicate in a sparse stencil pattern to Cartesian grids. By thoroughly exploiting the inherently present structure in this type of problem, we devise three novel distributed algorithms that are able to handle arbitrary stencil communication patterns effectively. We analyze the expected performance of our algorithms based on an abstract model of inter- and intra-node communication. An extensive experimental evaluation on several HPC machines shows that our algorithms are up to two orders of magnitude faster in running time than a (sequential) high-quality general graph mapping tool, while obtaining similar results in communication performance. Furthermore, our algorithms also achieve significantly better mapping quality compared to previous state-of-the-art Cartesian grid mapping algorithms. This results in up to a threefold performance improvement of an MPI_Neighbor_alltoall exchange operation. Our new algorithms can be used to implement the MPI_Cart_create functionality.
On repetitiveness measures of Thue-Morse words
Venue: arXiv cs.DS 2020
Year: 2020

We show that the size $γ(t_n)$ of the smallest string attractor of the $n$th Thue-Morse word $t_n$ is 4 for any $n\geq 4$, disproving the conjecture by Mantaci et al. [ICTCS 2019] that it is $n$. We also show that $δ(t_n) = \frac{10}{3+2^{4-n}}$ for $n \geq 3$, where $δ(w)$ is the maximum over all $k = 1,\ldots,|w|$, the number of distinct substrings of length $k$ in $w$ divided by $k$, which is a measure of repetitiveness recently studied by Kociumaka et al. [LATIN 2020]. Furthermore, we show that the number $z(t_n)$ of factors in the self-referencing Lempel-Ziv factorization of $t_n$ is exactly $2n$.
InterFaceGAN: Interpreting the Disentangled Face Representation Learned by GANs
Venue: arXiv cs.CV 2020
Year: 2020

Although Generative Adversarial Networks (GANs) have made significant progress in face synthesis, there lacks enough understanding of what GANs have learned in the latent representation to map a random code to a photo-realistic image. In this work, we propose a framework called InterFaceGAN to interpret the disentangled face representation learned by the state-of-the-art GAN models and study the properties of the facial semantics encoded in the latent space. We first find that GANs learn various semantics in some linear subspaces of the latent space. After identifying these subspaces, we can realistically manipulate the corresponding facial attributes without retraining the model. We then conduct a detailed study on the correlation between different semantics and manage to better disentangle them via subspace projection, resulting in more precise control of the attribute manipulation. Besides manipulating the gender, age, expression, and presence of eyeglasses, we can even alter the face pose and fix the artifacts accidentally made by GANs. Furthermore, we perform an in-depth face identity analysis and a layer-wise analysis to evaluate the editing results quantitatively. Finally, we apply our approach to real face editing by employing GAN inversion approaches and explicitly training feed-forward models based on the synthetic data established by InterFaceGAN. Extensive experimental results suggest that learning to synthesize faces spontaneously brings a disentangled and controllable face representation.
The Lazarus Effect: Healing Compromised Devices in the Internet of Small Things
Venue: arXiv cs.CR 2020
Year: 2020

We live in a time when billions of IoT devices are being deployed and increasingly relied upon. This makes ensuring their availability and recoverability in case of a compromise a paramount goal. The large and rapidly growing number of deployed IoT devices make manual recovery impractical, especially if the devices are dispersed over a large area. Thus, there is a need for a reliable and scalable remote recovery mechanism that works even after attackers have taken full control over devices, possibly misusing them or trying to render them useless. To tackle this problem, we present Lazarus, a system that enables the remote recovery of compromised IoT devices. With Lazarus, an IoT administrator can remotely control the code running on IoT devices unconditionally and within a guaranteed time bound. This makes recovery possible even in case of severe corruption of the devices' software stack. We impose only minimal hardware requirements, making Lazarus applicable even for low-end constrained off-the-shelf IoT devices. We isolate Lazarus's minimal recovery trusted computing base from untrusted software both in time and by using a trusted execution environment. The temporal isolation prevents secrets from being leaked through side-channels to untrusted software. Inside the trusted execution environment, we place minimal functionality that constrains untrusted software at runtime. We implement Lazarus on an ARM Cortex-M33-based microcontroller in a full setup with an IoT hub, device provisioning and secure update functionality. Our prototype can recover compromised embedded OSs and bare-metal applications and prevents attackers from bricking devices, for example, through flash wear out. We show this at the example of FreeRTOS, which requires no modifications but only a single additional task. Our evaluation shows negligible runtime performance impact and moderate memory requirements.
Optimal Resource Allocation for Elastic and Inelastic Jobs
Venue: arXiv cs.PF 2020
Year: 2020

Modern data centers are tasked with processing heterogeneous workloads consisting of various classes of jobs. These classes differ in their arrival rates, size distributions, and job parallelizability. With respect to paralellizability, some jobs are elastic, meaning they can parallelize linearly across many servers. Other jobs are inelastic, meaning they can only run on a single server. Although job classes can differ drastically, they are typically forced to share a single cluster. When sharing a cluster among heterogeneous jobs, one must decide how to allocate servers to each job at every moment in time. In this paper, we design and analyze allocation policies which aim to minimize the mean response time across jobs, where a job's response time is the time from when it arrives until it completes. We model this problem in a stochastic setting where each job may be elastic or inelastic. Job sizes are drawn from exponential distributions, but are unknown to the system. We show that, in the common case where elastic jobs are larger on average than inelastic jobs, the optimal allocation policy is Inelastic-First, giving inelastic jobs preemptive priority over elastic jobs. We obtain this result by introducing a novel sample path argument. We also show that there exist cases where Elastic-First (giving priority to elastic jobs) performs better than Inelastic-First. We then provide the first analysis of mean response time under both Elastic-First and Inelastic-First by leveraging recent techniques for solving high-dimensional Markov chains.
Adapting a Kidney Exchange Algorithm to Align with Human Values
Venue: arXiv cs.AI 2020
Year: 2020

The efficient and fair allocation of limited resources is a classical problem in economics and computer science. In kidney exchanges, a central market maker allocates living kidney donors to patients in need of an organ. Patients and donors in kidney exchanges are prioritized using ad-hoc weights decided on by committee and then fed into an allocation algorithm that determines who gets what--and who does not. In this paper, we provide an end-to-end methodology for estimating weights of individual participant profiles in a kidney exchange. We first elicit from human subjects a list of patient attributes they consider acceptable for the purpose of prioritizing patients (e.g., medical characteristics, lifestyle choices, and so on). Then, we ask subjects comparison queries between patient profiles and estimate weights in a principled way from their responses. We show how to use these weights in kidney exchange market clearing algorithms. We then evaluate the impact of the weights in simulations and find that the precise numerical values of the weights we computed matter little, other than the ordering of profiles that they imply. However, compared to not prioritizing patients at all, there is a significant effect, with certain classes of patients being (de)prioritized based on the human-elicited value judgments.
A Computational Analysis of Polarization on Indian and Pakistani Social Media
Venue: arXiv cs.SI 2020
Year: 2020

Between February 14, 2019 and March 4, 2019, a terrorist attack in Pulwama, Kashmir followed by retaliatory airstrikes led to rising tensions between India and Pakistan, two nuclear-armed countries. In this work, we examine polarizing messaging on Twitter during these events, particularly focusing on the positions of Indian and Pakistani politicians. We use a label propagation technique focused on hashtag co-occurrences to find polarizing tweets and users. Our analysis reveals that politicians in the ruling political party in India (BJP) used polarized hashtags and called for escalation of conflict more so than politicians from other parties. Our work offers the first analysis of how escalating tensions between India and Pakistan manifest on Twitter and provides a framework for studying polarizing messages.
Computations and Complexities of Tarski's Fixed Points and Supermodular Games
Venue: arXiv cs.GT 2020
Year: 2020

We consider two models of computation for Tarski's order preserving function f related to fixed points in a complete lattice: the oracle function model and the polynomial function model. In both models, we find the first polynomial time algorithm for finding a Tarski's fixed point. In addition, we provide a matching oracle bound for determining the uniqueness in the oracle function model and prove it is Co-NP hard in the polynomial function model. The existence of the pure Nash equilibrium in supermodular games is proved by Tarski's fixed point theorem. Exploring the difference between supermodular games and Tarski's fixed point, we also develop the computational results for finding one pure Nash equilibrium and determining the uniqueness of the equilibrium in supermodular games.
Multitask Learning with Single Gradient Step Update for Task Balancing
Venue: arXiv cs.LG 2020
Year: 2020

Multitask learning is a methodology to boost generalization performance and also reduce computational intensity and memory usage. However, learning multiple tasks simultaneously can be more difficult than learning a single task because it can cause imbalance among tasks. To address the imbalance problem, we propose an algorithm to balance between tasks at the gradient level by applying gradient-based meta-learning to multitask learning. The proposed method trains shared layers and task-specific layers separately so that the two layers with different roles in a multitask network can be fitted to their own purposes. In particular, the shared layer that contains informative knowledge shared among tasks is trained by employing single gradient step update and inner/outer loop training to mitigate the imbalance problem at the gradient level. We apply the proposed method to various multitask computer vision problems and achieve state-of-the-art performance.
Time-optimal Loosely-stabilizing Leader Election in Population Protocols
Venue: arXiv cs.DC 2020
Year: 2020

We consider the leader election problem in population protocol models. In pragmatic settings of population protocols, self-stabilization is a highly desired feature owing to its fault resilience and the benefit of initialization freedom. However, the design of self-stabilizing leader election is possible only under a strong assumption (i.e. the knowledge of the \emph{exact} size of a network) and rich computational resources (i.e. the number of states). Loose-stabilization, introduced by Sudo et al [Theoretical Computer Science, 2012], is a promising relaxed concept of self-stabilization to address the aforementioned issue. Loose-stabilization guarantees that starting from any configuration, the network will reach a safe configuration where a single leader exists within a short time, and thereafter it will maintain the single leader for a long time, but not forever. The main contribution of the paper is a time-optimal loosely-stabilizing leader election protocol. While the shortest convergence time achieved so far in loosely-stabilizing leader election is $O(\log^3 n)$ parallel time, the proposed protocol with design parameter $τ\ge 1$ attains $O(τ\log n)$ parallel convergence time and $Ω(n^τ)$ parallel holding time (i.e. the length of the period keeping the unique leader), both in expectation. This protocol is time-optimal in the sense of both the convergence and holding times in expectation because any loosely-stabilizing leader election protocol with the same length of the holding time is known to require $Ω(τ\log n)$ parallel time.
Development of a Shape-memorable Adaptive Pin Array Fixture
Venue: arXiv cs.RO 2020
Year: 2020

This paper proposes an adaptive pin-array fixture. The key idea of this research is to use the shape-memorable mechanism of pin array to fix multiple different shaped parts with common pin configuration. The clamping area consists of a matrix of passively slid-able pins that conform themselves to the contour of the target object. Vertical motion of the pins enables the fixture to encase the profile of the object. The shape memorable mechanism is realized by the combination of the rubber bush and fixing mechanism of a pin. Several physical peg-in-hole tasks is conducted to verify the feasibility of the fixture.
Deep learning with 4D spatio-temporal data representations for OCT-based force estimation
Venue: arXiv cs.CV 2020
Year: 2020

Estimating the forces acting between instruments and tissue is a challenging problem for robot-assisted minimally-invasive surgery. Recently, numerous vision-based methods have been proposed to replace electro-mechanical approaches. Moreover, optical coherence tomography (OCT) and deep learning have been used for estimating forces based on deformation observed in volumetric image data. The method demonstrated the advantage of deep learning with 3D volumetric data over 2D depth images for force estimation. In this work, we extend the problem of deep learning-based force estimation to 4D spatio-temporal data with streams of 3D OCT volumes. For this purpose, we design and evaluate several methods extending spatio-temporal deep learning to 4D which is largely unexplored so far. Furthermore, we provide an in-depth analysis of multi-dimensional image data representations for force estimation, comparing our 4D approach to previous, lower-dimensional methods. Also, we analyze the effect of temporal information and we study the prediction of short-term future force values, which could facilitate safety features. For our 4D force estimation architectures, we find that efficient decoupling of spatial and temporal processing is advantageous. We show that using 4D spatio-temporal data outperforms all previously used data representations with a mean absolute error of 10.7mN. We find that temporal information is valuable for force estimation and we demonstrate the feasibility of force prediction.
Benchmarking of a software stack for autonomous racing against a professional human race driver
Venue: arXiv cs.HC 2020
Year: 2020

The way to full autonomy of public road vehicles requires the step-by-step replacement of the human driver, with the ultimate goal of replacing the driver completely. Eventually, the driving software has to be able to handle all situations that occur on its own, even emergency situations. These particular situations require extreme combined braking and steering actions at the limits of handling to avoid an accident or to diminish its consequences. An average human driver is not trained to handle such extreme and rarely occurring situations and therefore often fails to do so. However, professional race drivers are trained to drive a vehicle utilizing the maximum amount of possible tire forces. These abilities are of high interest for the development of autonomous driving software. Here, we compare a professional race driver and our software stack developed for autonomous racing with data analysis techniques established in motorsports. The goal of this research is to derive indications for further improvement of the performance of our software and to identify areas where it still fails to meet the performance level of the human race driver. Our results are used to extend our software's capabilities and also to incorporate our findings into the research and development of public road autonomous vehicles.