OpenRaiser/Intern-Atlas huggingface dataset:
Proving Expected Sensitivity of Probabilistic Programs with Randomized Variable-Dependent Termination Time
Venue: arXiv cs.PL 2019
Year: 2019

The notion of program sensitivity (aka Lipschitz continuity) specifies that changes in the program input result in proportional changes to the program output. For probabilistic programs the notion is naturally extended to expected sensitivity. A previous approach develops a relational program logic framework for proving expected sensitivity of probabilistic while loops, where the number of iterations is fixed and bounded. In this work, we consider probabilistic while loops where the number of iterations is not fixed, but randomized and depends on the initial input values. We present a sound approach for proving expected sensitivity of such programs. Our sound approach is martingale-based and can be automated through existing martingale-synthesis algorithms. Furthermore, our approach is compositional for sequential composition of while loops under a mild side condition. We demonstrate the effectiveness of our approach on several classical examples from Gambler's Ruin, stochastic hybrid systems and stochastic gradient descent. We also present experimental results showing that our automated approach can handle various probabilistic programs in the literature.
Mathematical Notions vs. Human Perception of Fairness: A Descriptive Approach to Fairness for Machine Learning
Venue: arXiv cs.CY 2019
Year: 2019

Fairness for Machine Learning has received considerable attention, recently. Various mathematical formulations of fairness have been proposed, and it has been shown that it is impossible to satisfy all of them simultaneously. The literature so far has dealt with these impossibility results by quantifying the tradeoffs between different formulations of fairness. Our work takes a different perspective on this issue. Rather than requiring all notions of fairness to (partially) hold at the same time, we ask which one of them is the most appropriate given the societal domain in which the decision-making model is to be deployed. We take a descriptive approach and set out to identify the notion of fairness that best captures \emph{lay people's perception of fairness}. We run adaptive experiments designed to pinpoint the most compatible notion of fairness with each participant's choices through a small number of tests. Perhaps surprisingly, we find that the most simplistic mathematical definition of fairness---namely, demographic parity---most closely matches people's idea of fairness in two distinct application scenarios. This conclusion remains intact even when we explicitly tell the participants about the alternative, more complicated definitions of fairness, and we reduce the cognitive burden of evaluating those notions for them. Our findings have important implications for the Fair ML literature and the discourse on formalizing algorithmic fairness.
A bistable soft gripper with mechanically embedded sensing and actuation for fast closed-loop grasping
Venue: arXiv cs.RO 2019
Year: 2019

Soft robotic grippers are shown to be high effective for grasping unstructured objects with simple sensing and control strategies. However, they are still limited by their speed, sensing capabilities and actuation mechanism. Hence, their usage have been restricted in highly dynamic grasping tasks. This paper presents a soft robotic gripper with tunable bistable properties for sensor-less dynamic grasping. The bistable mechanism allows us to store arbitrarily large strain energy in the soft system which is then released upon contact. The mechanism also provides flexibility on the type of actuation mechanism as the grasping and sensing phase is completely passive. Theoretical background behind the mechanism is presented with finite element analysis to provide insights into design parameters. Finally, we experimentally demonstrate sensor-less dynamic grasping of an unknown object within 0.02 seconds, including the time to sense and actuate.
The Graph Structure of the Internet at the Autonomous Systems Level during Ten Years
Venue: arXiv cs.NI 2019
Year: 2019

We study how the graph structure of the Internet at the Autonomous Systems (AS) level evolved during a decade. For each year of the period 2008-2017 we consider a snapshot of the AS graph and examine how many features related to structure, connectivity and centrality changed over time. The analysis of these metrics provides topological and data traffic information and allows to clarify some assumptions about the models concerning the evolution of the Internet graph structure. We find that the size of the Internet roughly doubled. The overall trend of the average connectivity is an increase over time, while that of the shortest path length is a decrease over time. The internal core of the Internet is composed of a small fraction of big AS and is more stable and connected that external cores. A hierarchical organization emerges where a small fraction of big hubs are connected to many regions with high internal cohesiveness, poorly connected among them and containing AS with low and medium number of links. Centrality measurements indicate that the average number of shortest paths crossing an AS or containing a link between two of them decreased over time.
Business Process Privacy Analysis in Pleak
Venue: arXiv cs.CR 2019
Year: 2019

Pleak is a tool to capture and analyze privacy-enhanced business process models to characterize and quantify to what extent the outputs of a process leak information about its inputs. Pleak incorporates an extensible set of analysis plugins, which enable users to inspect potential leakages at multiple levels of detail.
Fast Parallel Integer Adder in Binary Representation
Venue: arXiv cs.AR 2019
Year: 2019

An integer adder for integers in the binary representation is one of the basic operations of any digital processor. For adding two integers of N bits each, the serial adder takes as many clock ticks. For achieving higher speeds, parallel circuits are discussed in the literature, and these circuits usually operate in two levels. At the lower level, integers represented by blocks of smaller number of bits are added, and in a cascade of stages in the next level, the carries produced in previous addition operations are summed to the augends. In this paper, we describe a fast method and an improvement of it. The first attempt resembles the operation method of the merge sort algorithm, from which some important properties of carries produced in each stage are analysed and assimilated, resulting in a parallel adder that runs in time comparable to the existing methods. After that, the crucial insights are brought to fruition in an improved design, which takes 2 clock ticks to perform the addition operation requiring only O(square(N)) space. The number of bits N is chosen usually to be a positive integer power of 2. The speedup is achieved by special purpose circuits for increment operations by i-th power of 2 , for i = 0, 1, ..., N-1, each operation taking only a single clock tick to complete. The usefulness of this adder for multiplication operation is discussed. The standard multiplication method utilizes quantizer and 3-bit to 2-bit consolidation circuits to produce an integer that represents in binary the number of 1s in a column corresponding to a place (weighted coefficient) of nonnegative integer power of 2. The last two consolidated integers are added by an adder in the end.
DeeperLab: Single-Shot Image Parser
Venue: arXiv cs.CV 2019
Year: 2019

We present a single-shot, bottom-up approach for whole image parsing. Whole image parsing, also known as Panoptic Segmentation, generalizes the tasks of semantic segmentation for 'stuff' classes and instance segmentation for 'thing' classes, assigning both semantic and instance labels to every pixel in an image. Recent approaches to whole image parsing typically employ separate standalone modules for the constituent semantic and instance segmentation tasks and require multiple passes of inference. Instead, the proposed DeeperLab image parser performs whole image parsing with a significantly simpler, fully convolutional approach that jointly addresses the semantic and instance segmentation tasks in a single-shot manner, resulting in a streamlined system that better lends itself to fast processing. For quantitative evaluation, we use both the instance-based Panoptic Quality (PQ) metric and the proposed region-based Parsing Covering (PC) metric, which better captures the image parsing quality on 'stuff' classes and larger object instances. We report experimental results on the challenging Mapillary Vistas dataset, in which our single model achieves 31.95% (val) / 31.6% PQ (test) and 55.26% PC (val) with 3 frames per second (fps) on GPU or near real-time speed (22.6 fps on GPU) with reduced accuracy.
A framework for synchronizing a team of aerial robots in communication-limited environments
Venue: arXiv cs.RO 2019
Year: 2019

This paper addresses a synchronization problem that arises when a team of aerial robots (ARs) need to communicate while performing assigned tasks in a cooperative scenario. Each robot has a limited communication range and flies within a previously assigned closed trajectory. When two robots are close enough, a communication link may be established, allowing the robots to exchange information. The goal is to schedule the flights such that the entire system can be synchronized for maximum information exchange, that is, every pair of neighbors always visit the feasible communication link at the same time. We propose an algorithm for scheduling a team of robots in this scenario and propose a robust framework in which the synchronization of a large team of robots is assured. The approach allows us to design a fault-tolerant system that can be used for multiple tasks such as surveillance, area exploration, searching for targets in a hazardous environment, and assembly and structure construction, to name a few.
Multi-task learning with compressible features for Collaborative Intelligence
Venue: arXiv cs.MM 2019
Year: 2019

A promising way to deploy Artificial Intelligence (AI)-based services on mobile devices is to run a part of the AI model (a deep neural network) on the mobile itself, and the rest in the cloud. This is sometimes referred to as collaborative intelligence. In this framework, intermediate features from the deep network need to be transmitted to the cloud for further processing. We study the case where such features are used for multiple purposes in the cloud (multi-tasking) and where they need to be compressible in order to allow efficient transmission to the cloud. To this end, we introduce a new loss function that encourages feature compressibility while improving system performance on multiple tasks. Experimental results show that with the compression-friendly loss, one can achieve around 20% bitrate reduction without sacrificing the performance on several vision-related tasks.
Long and Short Memory Balancing in Visual Co-Tracking using Q-Learning
Venue: arXiv cs.CV 2019
Year: 2019

Employing one or more additional classifiers to break the self-learning loop in tracing-by-detection has gained considerable attention. Most of such trackers merely utilize the redundancy to address the accumulating label error in the tracking loop, and suffer from high computational complexity as well as tracking challenges that may interrupt all classifiers (e.g. temporal occlusions). We propose the active co-tracking framework, in which the main classifier of the tracker labels samples of the video sequence, and only consults auxiliary classifier when it is uncertain. Based on the source of the uncertainty and the differences of two classifiers (e.g. accuracy, speed, update frequency, etc.), different policies should be taken to exchange the information between two classifiers. Here, we introduce a reinforcement learning approach to find the appropriate policy by considering the state of the tracker in a specific sequence. The proposed method yields promising results in comparison to the best tracking-by-detection approaches.
Flash: Efficient Dynamic Routing for Offchain Networks
Venue: arXiv cs.NI 2019
Year: 2019

Offchain networks emerge as a promising solution to address the scalability challenge of blockchain. Participants directly make payments through a network of payment channels without the overhead of committing onchain transactions. Routing is critical to the performance of offchain networks. Existing solutions use either static routing with poor performance or dynamic routing with high overhead to obtain the dynamic channel balance information. In this paper, we propose Flash, a new dynamic routing solution that leverages the unique characteristics of transactions in offchain networks to strike a better tradeoff between path optimality and probing overhead. By studying the traces of real offchain networks, we find that the payment sizes are heavy-tailed, and most payments are highly recurrent. Flash thus differentiates the treatment of elephant payments from mice payments. It uses a modified max-flow algorithm for elephant payments to find paths with sufficient capacity, and strategically routes the payment across paths to minimize the transaction fees. Mice payments are directly sent by looking up a routing table with a few precomputed paths to reduce probing overhead. Testbed experiments and data-driven simulations show that Flash improves the success volume of payments by up to 2.3x compared to the state-of-the-art routing algorithm.
Introducing Yet Another REversible Language
Venue: arXiv cs.PL 2019
Year: 2019

Yarel is a core reversible programming language that implements a class of permutations, defined recursively, which are primitive recursive complete. The current release of Yarel syntax and operational semantics, implemented by compiling Yarel to Java, is 0.1.0, according to Semantic Versioning 2.0.0. Yarel comes with Yarel-IDE, developed as an Eclipse plug-in by means of XText.
Simultaneous x, y Pixel Estimation and Feature Extraction for Multiple Small Objects in a Scene: A Description of the ALIEN Network
Venue: arXiv cs.CV 2019
Year: 2019

We present a deep-learning network that detects multiple small objects (hundreds to thousands) in a scene while simultaneously estimating their x,y pixel locations together with a characteristic feature-set (for instance, target orientation and color). All estimations are performed in a single, forward pass which makes implementing the network fast and efficient. In this paper, we describe the architecture of our network --- nicknamed ALIEN --- and detail its performance when applied to vehicle detection.
DeepIrisNet2: Learning Deep-IrisCodes from Scratch for Segmentation-Robust Visible Wavelength and Near Infrared Iris Recognition
Venue: arXiv cs.CV 2019
Year: 2019

We first, introduce a deep learning based framework named as DeepIrisNet2 for visible spectrum and NIR Iris representation. The framework can work without classical iris normalization step or very accurate iris segmentation; allowing to work under non-ideal situation. The framework contains spatial transformer layers to handle deformation and supervision branches after certain intermediate layers to mitigate overfitting. In addition, we present a dual CNN iris segmentation pipeline comprising of a iris/pupil bounding boxes detection network and a semantic pixel-wise segmentation network. Furthermore, to get compact templates, we present a strategy to generate binary iris codes using DeepIrisNet2. Since, no ground truth dataset are available for CNN training for iris segmentation, We build large scale hand labeled datasets and make them public; i) iris, pupil bounding boxes, ii) labeled iris texture. The networks are evaluated on challenging ND-IRIS-0405, UBIRIS.v2, MICHE-I, and CASIA v4 Interval datasets. Proposed approach significantly improves the state-of-the-art and achieve outstanding performance surpassing all previous methods.
Deep Learning for Bridge Load Capacity Estimation in Post-Disaster and -Conflict Zones
Venue: arXiv cs.CV 2019
Year: 2019

Many post-disaster and -conflict regions do not have sufficient data on their transportation infrastructure assets, hindering both mobility and reconstruction. In particular, as the number of aging and deteriorating bridges increase, it is necessary to quantify their load characteristics in order to inform maintenance and prevent failure. The load carrying capacity and the design load are considered as the main aspects of any civil structures. Human examination can be costly and slow when expertise is lacking in challenging scenarios. In this paper, we propose to employ deep learning as method to estimate the load carrying capacity from crowd sourced images. A new convolutional neural network architecture is trained on data from over 6000 bridges, which will benefit future research and applications. We tackle significant variations in the dataset (e.g. class interval, image completion, image colour) and quantify their impact on the prediction accuracy, precision, recall and F1 score. Finally, practical optimisation is performed by converting multiclass classification into binary classification to achieve a promising field use performance.
Semi-Supervised and Task-Driven Data Augmentation
Venue: arXiv cs.CV 2019
Year: 2019

Supervised deep learning methods for segmentation require large amounts of labelled training data, without which they are prone to overfitting, not generalizing well to unseen images. In practice, obtaining a large number of annotations from clinical experts is expensive and time-consuming. One way to address scarcity of annotated examples is data augmentation using random spatial and intensity transformations. Recently, it has been proposed to use generative models to synthesize realistic training examples, complementing the random augmentation. So far, these methods have yielded limited gains over the random augmentation. However, there is potential to improve the approach by (i) explicitly modeling deformation fields (non-affine spatial transformation) and intensity transformations and (ii) leveraging unlabelled data during the generative process. With this motivation, we propose a novel task-driven data augmentation method where to synthesize new training examples, a generative network explicitly models and applies deformation fields and additive intensity masks on existing labelled data, modeling shape and intensity variations, respectively. Crucially, the generative model is optimized to be conducive to the task, in this case segmentation, and constrained to match the distribution of images observed from labelled and unlabelled samples. Furthermore, explicit modeling of deformation fields allow synthesizing segmentation masks and images in exact correspondence by simply applying the generated transformation to an input image and the corresponding annotation. Our experiments on cardiac magnetic resonance images (MRI) showed that, for the task of segmentation in small training data scenarios, the proposed method substantially outperforms conventional augmentation techniques.
Yelp Food Identification via Image Feature Extraction and Classification
Venue: arXiv cs.CV 2019
Year: 2019

Yelp has been one of the most popular local service search engine in US since 2004. It is powered by crowd-sourced text reviews and photo reviews. Restaurant customers and business owners upload photo images to Yelp, including reviewing or advertising either food, drinks, or inside and outside decorations. It is obviously not so effective that labels for food photos rely on human editors, which is an issue should be addressed by innovative machine learning approaches. In this paper, we present a simple but effective approach which can identify up to ten kinds of food via raw photos from the challenge dataset. We use 1) image pre-processing techniques, including filtering and image augmentation, 2) feature extraction via convolutional neural networks (CNN), and 3) three ways of classification algorithms. Then, we illustrate the classification accuracy by tuning parameters for augmentations, CNN, and classification. Our experimental results show this simple but effective approach to identify up to 10 food types from images.
Search and Rescue in the Face of Uncertain Threats
Venue: arXiv cs.DS 2019
Year: 2019

We consider a search problem in which one or more targets must be rescued by a search party, or Searcher. The targets may be survivors of some natural disaster, or prisoners held by an adversary. The targets are hidden among a finite set of locations, but when a location is searched, there is a known probability that the search will come to an end, perhaps because the Searcher becomes trapped herself, or is captured by the adversary. If this happens before all the targets have been recovered, then the rescue attempt is deemed a failure. The objective is to find the search that maximizes the probability of recovering all the targets. We present and solve a game theoretic model for this problem, by placing it in a more general framework that encompasses another game previously introduced by the author. We also consider an extension to the game in which the targets are hidden on the vertices of a graph. In the case that there is only one target, we give a solution of the game played on a tree.
Redundant Loads: A Software Inefficiency Indicator
Venue: arXiv cs.PF 2019
Year: 2019

Modern software packages have become increasingly complex with millions of lines of code and references to many external libraries. Redundant operations are a common performance limiter in these code bases. Missed compiler optimization opportunities, inappropriate data structure and algorithm choices, and developers' inattention to performance are some common reasons for the existence of redundant operations. Developers mainly depend on compilers to eliminate redundant operations. However, compilers' static analysis often misses optimization opportunities due to ambiguities and limited analysis scope; automatic optimizations to algorithmic and data structural problems are out of scope. We develop LoadSpy, a whole-program profiler to pinpoint redundant memory load operations, which are often a symptom of many redundant operations. The strength of LoadSpy exists in identifying and quantifying redundant load operations in programs and associating the redundancies with program execution contexts and scopes to focus developers' attention on problematic code. LoadSpy works on fully optimized binaries, adopts various optimization techniques to reduce its overhead, and provides a rich graphic user interface, which make it a complete developer tool. Applying LoadSpy showed that a large fraction of redundant loads is common in modern software packages despite highest levels of automatic compiler optimizations. Guided by LoadSpy, we optimize several well-known benchmarks and real-world applications, yielding significant speedups.
Assurance of System Safety: A Survey of Design and Argument Patterns
Venue: arXiv cs.SE 2019
Year: 2019

The specification, design, and assurance of safety encompasses various concepts and best practices, subject of reuse in form of patterns. This work summarizes applied research on such concepts and practices with a focus on the last two decades and on the state-of-the-art of patterns in safety-critical system design and assurance argumentation. We investigate several aspects of such patterns, for example, where and when they are applied, their characteristics and purposes, and how they are related. For each aspect, we provide an overview of relevant studies and synthesize a taxonomy of first principles underlying these patterns. Furthermore, we comment on how these studies address known challenges and we discuss suggestions for further research. Our findings disclose a lack of research on how patterns improve system safety claims and, vice versa, on the decomposition of system safety into separated local concerns, and on the impact of security on safety.