OpenRaiser/Intern-Atlas huggingface dataset:
On Polymorphic Sessions and Functions: A Tale of Two (Fully Abstract) Encodings
Venue: arXiv cs.LO 2018
Year: 2018

This work exploits the logical foundation of session types to determine what kind of type discipline for the pi-calculus can exactly capture, and is captured by, lambda-calculus behaviours. Leveraging the proof theoretic content of the soundness and completeness of sequent calculus and natural deduction presentations of linear logic, we develop the first mutually inverse and fully abstract processes-as-functions and functions-as-processes encodings between a polymorphic session pi-calculus and a linear formulation of System F. We are then able to derive results of the session calculus from the theory of the lambda-calculus: (1) we obtain a characterisation of inductive and coinductive session types via their algebraic representations in System F; and (2) we extend our results to account for value and process passing, entailing strong normalisation.
Energy-Aware Virtual Machine Management in Inter-datacenter Networks over Elastic Optical Infrastructure
Venue: arXiv cs.NI 2018
Year: 2018

Datacenters (DCs), deployed in a large scale to support the ever increasing demand for data processing applications, consume tremendous energy. Powering DCs with renewable energy can effectively reduce the brown energy consumption. Owing to geographically distributed deployment of DCs, the renewable energy generation and the data processing demands usually vary in different DCs. Migrating virtual machines (VMs) among DCs according to the availability of renewable energy helps match the energy demands and the renewable energy generation in DCs, and thus maximizes the utilization of renewable energy. We first elicit the renewable energy-aware inter-datacenter (inter-DC) VM migration problem in an inter-DC network over the elastic optical infrastructure, present it as a many-manycast communications problem, and then formulate it as an integer linear programming problem. The objective is to minimize the total cost of the brown energy consumption of DCs in such inter-DC network via VM migration. We use CVX and Gurobi to solve this problem for small network configurations, and we propose a few heuristic algorithms that approximate the optimal solution for large network configurations. Through extensive simulations, we show that the proposed algorithms, by migrating VM among DCs, can reduce up to 19.7% cost of the brown energy consumption.
In-Bed Pose Estimation: Deep Learning with Shallow Dataset
Venue: arXiv cs.CV 2018
Year: 2018

Although human pose estimation for various computer vision (CV) applications has been studied extensively in the last few decades, yet in-bed pose estimation using camera-based vision methods has been ignored by the CV community because it is assumed to be identical to the general purpose pose estimation methods. However, in-bed pose estimation has its own specialized aspects and comes with specific challenges including the notable differences in lighting conditions throughout a day and also having different pose distribution from the common human surveillance viewpoint. In this paper, we demonstrate that these challenges significantly lessen the effectiveness of existing general purpose pose estimation models. In order to address the lighting variation challenge, infrared selective (IRS) image acquisition technique is proposed to provide uniform quality data under various lighting conditions. In addition, to deal with unconventional pose perspective, a 2-end histogram of oriented gradient (HOG) rectification method is presented. In this work, we explored the idea of employing a pre-trained convolutional neural network (CNN) model trained on large public datasets of general human poses and fine-tuning the model using our own shallow in-bed IRS dataset. We developed an IRS imaging system and collected IRS image data from several realistic life-size mannequins in a simulated hospital room environment. A pre-trained CNN called convolutional pose machine (CPM) was repurposed for in-bed pose estimation by fine-tuning its specific intermediate layers. Using the HOG rectification method, the pose estimation performance of CPM significantly improved by 26.4% in PCK0.1 criteria compared to the model without such rectification.
Motion Artifact Detection in Confocal Laser Endomicroscopy Images
Venue: arXiv cs.CV 2018
Year: 2018

Confocal Laser Endomicroscopy (CLE), an optical imaging technique allowing non-invasive examination of the mucosa on a (sub)cellular level, has proven to be a valuable diagnostic tool in gastroenterology and shows promising results in various anatomical regions including the oral cavity. Recently, the feasibility of automatic carcinoma detection for CLE images of sufficient quality was shown. However, in real world data sets a high amount of CLE images is corrupted by artifacts. Amongst the most prevalent artifact types are motion-induced image deteriorations. In the scope of this work, algorithmic approaches for the automatic detection of motion artifact-tainted image regions were developed. Hence, this work provides an important step towards clinical applicability of automatic carcinoma detection. Both, conventional machine learning and novel, deep learning-based approaches were assessed. The deep learning-based approach outperforms the conventional approaches, attaining an AUC of 0.90.
Constant Approximation for $k$-Median and $k$-Means with Outliers via Iterative Rounding
Venue: arXiv cs.DS 2018
Year: 2018

In this paper, we present a new iterative rounding framework for many clustering problems. Using this, we obtain an $(α_1 + ε\leq 7.081 + ε)$-approximation algorithm for $k$-median with outliers, greatly improving upon the large implicit constant approximation ratio of Chen [Chen, SODA 2018]. For $k$-means with outliers, we give an $(α_2+ε\leq 53.002 + ε)$-approximation, which is the first $O(1)$-approximation for this problem. The iterative algorithm framework is very versatile; we show how it can be used to give $α_1$- and $(α_1 + ε)$-approximation algorithms for matroid and knapsack median problems respectively, improving upon the previous best approximations ratios of $8$ [Swamy, ACM Trans. Algorithms] and $17.46$ [Byrka et al, ESA 2015]. The natural LP relaxation for the $k$-median/$k$-means with outliers problem has an unbounded integrality gap. In spite of this negative result, our iterative rounding framework shows that we can round an LP solution to an almost-integral solution of small cost, in which we have at most two fractionally open facilities. Thus, the LP integrality gap arises due to the gap between almost-integral and fully-integral solutions. Then, using a pre-processing procedure, we show how to convert an almost-integral solution to a fully-integral solution losing only a constant-factor in the approximation ratio. By further using a sparsification technique, the additive factor loss incurred by the conversion can be reduced to any $ε> 0$.
Conditional Task and Motion Planning through an Effort-based Approach
Venue: arXiv cs.RO 2018
Year: 2018

This paper proposes a preliminary work on a Conditional Task and Motion Planning algorithm able to find a plan that minimizes robot efforts while solving assigned tasks. Unlike most of the existing approaches that replan a path only when it becomes unfeasible (e.g., no collision-free paths exist), the proposed algorithm takes into consideration a replanning procedure whenever an effort-saving is possible. The effort is here considered as the execution time, but it is extensible to the robot energy consumption. The computed plan is both conditional and dynamically adaptable to the unexpected environmental changes. Based on the theoretical analysis of the algorithm, authors expect their proposal to be complete and scalable. In progress experiments aim to prove this investigation.
Investigations of a Robotic Testbed with Viscoelastic Liquid Cooled Actuators
Venue: arXiv cs.SY 2018
Year: 2018

We design, build, and thoroughly test a new type of actuator dubbed viscoelastic liquid cooled actuator (VLCA) for robotic applications. VLCAs excel in the following five critical axes of performance: energy efficiency, torque density, impact resistence, joint position and force controllability. We first study the design objectives and choices of the VLCA to enhance the performance on the needed criteria. We follow by an investigation on viscoelastic materials in terms of their damping, viscous and hysteresis properties as well as parameters related to the long- term performance. As part of the actuator design, we configure a disturbance observer to provide high-fidelity force control to enable a wide range of impedance control capabilities. We proceed to design a robotic system capable to lift payloads of 32.5 kg, which is three times larger than its own weight. In addition, we experiment with Cartesian trajectory control up to 2 Hz with a vertical range of motion of 32 cm while carrying a payload of 10 kg. Finally, we perform experiments on impedance control and mechanical robustness by studying the response of the robotics testbed to hammering impacts and external force interactions.
Optimal transport maps for distribution preserving operations on latent spaces of Generative Models
Venue: arXiv cs.LG 2018
Year: 2018

Generative models such as Variational Auto Encoders (VAEs) and Generative Adversarial Networks (GANs) are typically trained for a fixed prior distribution in the latent space, such as uniform or Gaussian. After a trained model is obtained, one can sample the Generator in various forms for exploration and understanding, such as interpolating between two samples, sampling in the vicinity of a sample or exploring differences between a pair of samples applied to a third sample. In this paper, we show that the latent space operations used in the literature so far induce a distribution mismatch between the resulting outputs and the prior distribution the model was trained on. To address this, we propose to use distribution matching transport maps to ensure that such latent space operations preserve the prior distribution, while minimally modifying the original operation. Our experimental results validate that the proposed operations give higher quality samples compared to the original operations.
Integer Programming in Parameterized Complexity: Three Miniatures
Venue: arXiv cs.DS 2018
Year: 2018

Powerful results from the theory of integer programming have recently led to substantial advances in parameterized complexity. However, our perception is that, except for Lenstra's algorithm for solving integer linear programming in fixed dimension, there is still little understanding in the parameterized complexity community of the strengths and limitations of the available tools. This is understandable: it is often difficult to infer exact runtimes or even the distinction between FPT and XP algorithms, and some knowledge is simply unwritten folklore in a different community. We wish to make a step in remedying this situation. To that end, we first provide an easy to navigate quick reference guide of integer programming algorithms from the perspective of parameterized complexity. Then, we show their applications in three case studies, obtaining FPT algorithms with runtime $f(k)poly(n)$. We focus on: * Modeling: since the algorithmic results follow by applying existing algorithms to new models, we shift the focus from the complexity result to the modeling result, highlighting common patterns and tricks which are used. * Optimality program: after giving an FPT algorithm, we are interested in reducing the dependence on the parameter; we show which algorithms and tricks are often useful for speed-ups. * Minding the poly(n): reducing $f(k)$ often has the unintended consequence of increasing poly(n); so we highlight the common trade-offs and show how to get the best of both worlds. Specifically, we consider graphs of bounded neighborhood diversity which are in a sense the simplest of dense graphs, and we show several FPT algorithms for Capacitated Dominating Set, Sum Coloring, and Max-q-Cut by modeling them as convex programs in fixed dimension, n-fold integer programs, bounded dual treewidth programs, and indefinite quadratic programs in fixed dimension.
Fully-Dynamic Bin Packing with Limited Repacking
Venue: arXiv cs.DS 2018
Year: 2018

We study the classic Bin Packing problem in a fully-dynamic setting, where new items can arrive and old items may depart. We want algorithms with low asymptotic competitive ratio \emph{while repacking items sparingly} between updates. Formally, each item $i$ has a \emph{movement cost} $c_i\geq 0$, and we want to use $α\cdot OPT$ bins and incur a movement cost $γ\cdot c_i$, either in the worst case, or in an amortized sense, for $α, γ$ as small as possible. We call $γ$ the \emph{recourse} of the algorithm. This is motivated by cloud storage applications, where fully-dynamic Bin Packing models the problem of data backup to minimize the number of disks used, as well as communication incurred in moving file backups between disks. Since the set of files changes over time, we could recompute a solution periodically from scratch, but this would give a high number of disk rewrites, incurring a high energy cost and possible wear and tear of the disks. In this work, we present optimal tradeoffs between number of bins used and number of items repacked, as well as natural extensions of the latter measure.
Deep density networks and uncertainty in recommender systems
Venue: arXiv cs.IR 2018
Year: 2018

Building robust online content recommendation systems requires learning complex interactions between user preferences and content features. The field has evolved rapidly in recent years from traditional multi-arm bandit and collaborative filtering techniques, with new methods employing Deep Learning models to capture non-linearities. Despite progress, the dynamic nature of online recommendations still poses great challenges, such as finding the delicate balance between exploration and exploitation. In this paper we show how uncertainty estimations can be incorporated by employing them in an optimistic exploitation/exploration strategy for more efficient exploration of new recommendations. We provide a novel hybrid deep neural network model, Deep Density Networks (DDN), which integrates content-based deep learning models with a collaborative scheme that is able to robustly model and estimate uncertainty. Finally, we present online and offline results after incorporating DNN into a real world content recommendation system that serves billions of recommendations per day, and show the benefit of using DDN in practice.
Exploration in NetHack With Secret Discovery
Venue: arXiv cs.AI 2018
Year: 2018

Roguelike games generally feature exploration problems as a critical, yet often repetitive element of gameplay. Automated approaches, however, face challenges in terms of optimality, as well as due to incomplete information, such as from the presence of secret doors. This paper presents an algorithmic approach to exploration of roguelike dungeon environments. Our design aims to minimize exploration time, balancing coverage and discovery of secret areas with resource cost. Our algorithm is based on the concept of occupancy maps popular in robotics, adapted to encourage efficient discovery of secret access points. Through extensive experimentation on NetHack maps we show that this technique is significantly more efficient than simpler greedy approaches and an existing automated player. We further investigate optimized parameterization for the algorithm through a comprehensive data analysis. These results point towards better automation for players as well as heuristics applicable to fully automated gameplay.
Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization
Venue: arXiv cs.LG 2018
Year: 2018

Data-driven algorithm design, that is, choosing the best algorithm for a specific application, is a crucial problem in modern data science. Practitioners often optimize over a parameterized algorithm family, tuning parameters based on problems from their domain. These procedures have historically come with no guarantees, though a recent line of work studies algorithm selection from a theoretical perspective. We advance the foundations of this field in several directions: we analyze online algorithm selection, where problems arrive one-by-one and the goal is to minimize regret, and private algorithm selection, where the goal is to find good parameters over a set of problems without revealing sensitive information contained therein. We study important algorithm families, including SDP-rounding schemes for problems formulated as integer quadratic programs, and greedy techniques for canonical subset selection problems. In these cases, the algorithm's performance is a volatile and piecewise Lipschitz function of its parameters, since tweaking the parameters can completely change the algorithm's behavior. We give a sufficient and general condition, dispersion, defining a family of piecewise Lipschitz functions that can be optimized online and privately, which includes the functions measuring the performance of the algorithms we study. Intuitively, a set of piecewise Lipschitz functions is dispersed if no small region contains many of the functions' discontinuities. We present general techniques for online and private optimization of the sum of dispersed piecewise Lipschitz functions. We improve over the best-known regret bounds for a variety of problems, prove regret bounds for problems not previously studied, and give matching lower bounds. We also give matching upper and lower bounds on the utility loss due to privacy. Moreover, we uncover dispersion in auction design and pricing problems.
Scalable and massively parallel Monte Carlo photon transport simulations for heterogeneous computing platforms
Venue: arXiv cs.DC 2018
Year: 2018

We present a highly scalable Monte Carlo (MC) three-dimensional photon transport simulation platform designed for heterogeneous computing systems. Through the development of a massively parallel MC algorithm using the Open Computing Language (OpenCL) framework, this research extends our existing graphics processing unit (GPU)-accelerated MC technique to a highly scalable vendor-independent heterogeneous computing environment, achieving significantly improved performance and software portability. A number of parallel computing techniques are investigated to achieve portable performance over a wide range of computing hardware. Furthermore, multiple thread-level and device-level load-balancing strat- egies are developed to obtain efficient simulations using multiple central processing units (CPUs) and GPUs.
ANCHOR: logically-centralized security for Software-Defined Networks
Venue: arXiv cs.NI 2018
Year: 2018

While the centralization of SDN brought advantages such as a faster pace of innovation, it also disrupted some of the natural defenses of traditional architectures against different threats. The literature on SDN has mostly been concerned with the functional side, despite some specific works concerning non-functional properties like 'security' or 'dependability'. Though addressing the latter in an ad-hoc, piecemeal way, may work, it will most likely lead to efficiency and effectiveness problems. We claim that the enforcement of non-functional properties as a pillar of SDN robustness calls for a systemic approach. As a general concept, we propose ANCHOR, a subsystem architecture that promotes the logical centralization of non-functional properties. To show the effectiveness of the concept, we focus on 'security' in this paper: we identify the current security gaps in SDNs and we populate the architecture middleware with the appropriate security mechanisms, in a global and consistent manner. Essential security mechanisms provided by anchor include reliable entropy and resilient pseudo-random generators, and protocols for secure registration and association of SDN devices. We claim and justify in the paper that centralizing such mechanisms is key for their effectiveness, by allowing us to: define and enforce global policies for those properties; reduce the complexity of controllers and forwarding devices; ensure higher levels of robustness for critical services; foster interoperability of the non-functional property enforcement mechanisms; and promote the security and resilience of the architecture itself. We discuss design and implementation aspects, and we prove and evaluate our algorithms and mechanisms, including the formalisation of the main protocols and the verification of their core security properties using the Tamarin prover.
Z2Z4-Additive Cyclic Codes: Kernel and Rank
Venue: arXiv cs.IT 2018
Year: 2018

A Z2Z4-additive code C subset of Z_2^alpha x Z_4^beta is called cyclic if the set of coordinates can be partitioned into two subsets, the set of Z_2 and the set of Z_4 coordinates, such that any cyclic shift of the coordinates of both subsets leaves the code invariant. Let Phi(C) be the binary Gray image of C. We study the rank and the dimension of the kernel of a Z2Z4-additive cyclic code C, that is, the dimensions of the binary linear codes <Phi(C)> and ker(Phi(C)). We give upper and lower bounds for these parameters. It is known that the codes <Phi(C)> and ker(Phi(C)) are binary images of Z2Z4-additive codes R(C) and K(C), respectively. Moreover, we show that R(C) and K(C) are also cyclic and we determine the generator polynomials of these codes in terms of the generator polynomials of the code C.
Adversarial Training for Disease Prediction from Electronic Health Records with Missing Data
Venue: arXiv cs.LG 2018
Year: 2018

Electronic health records (EHRs) have contributed to the computerization of patient records and can thus be used not only for efficient and systematic medical services, but also for research on biomedical data science. However, there are many missing values in EHRs when provided in matrix form, which is an important issue in many biomedical EHR applications. In this paper, we propose a two-stage framework that includes missing data imputation and disease prediction to address the missing data problem in EHRs. We compared the disease prediction performance of generative adversarial networks (GANs) and conventional learning algorithms in combination with missing data prediction methods. As a result, we obtained a level of accuracy of 0.9777, sensitivity of 0.9521, specificity of 0.9925, area under the receiver operating characteristic curve (AUC-ROC) of 0.9889, and F-score of 0.9688 with a stacked autoencoder as the missing data prediction method and an auxiliary classifier GAN (AC-GAN) as the disease prediction method. The comparison results show that a combination of a stacked autoencoder and an AC-GAN significantly outperforms other existing approaches. Our results suggest that the proposed framework is more robust for disease prediction from EHRs with missing data.