OpenRaiser/Intern-Atlas huggingface dataset:
Approximate Convex Hull of Data Streams
Venue: arXiv cs.CG 2017
Year: 2017

Given a finite set of points $P \subseteq \mathbb{R}^d$, we would like to find a small subset $S \subseteq P$ such that the convex hull of $S$ approximately contains $P$. More formally, every point in $P$ is within distance $ε$ from the convex hull of $S$. Such a subset $S$ is called an $ε$-hull. Computing an $ε$-hull is an important problem in computational geometry, machine learning, and approximation algorithms. In many real world applications, the set $P$ is too large to fit in memory. We consider the streaming model where the algorithm receives the points of $P$ sequentially and strives to use a minimal amount of memory. Existing streaming algorithms for computing an $ε$-hull require $O(ε^{-(d-1)/2})$ space, which is optimal for a worst-case input. However, this ignores the structure of the data. The minimal size of an $ε$-hull of $P$, which we denote by $\text{OPT}$, can be much smaller. A natural question is whether a streaming algorithm can compute an $ε$-hull using only $O(\text{OPT})$ space. We begin with lower bounds that show that it is not possible to have a single-pass streaming algorithm that computes an $ε$-hull with $O(\text{OPT})$ space. We instead propose three relaxations of the problem for which we can compute $ε$-hulls using space near-linear to the optimal size. Our first algorithm for points in $\mathbb{R}^2$ that arrive in random-order uses $O(\log n\cdot \text{OPT})$ space. Our second algorithm for points in $\mathbb{R}^2$ makes $O(\log(\frac{1}ε))$ passes before outputting the $ε$-hull and requires $O(\text{OPT})$ space. Our third algorithm for points in $\mathbb{R}^d$ for any fixed dimension $d$ outputs an $ε$-hull for all but $δ$-fraction of directions and requires $O(\text{OPT} \cdot \log \text{OPT})$ space.
Practical Bayesian optimization in the presence of outliers
Venue: arXiv cs.LG 2017
Year: 2017

Inference in the presence of outliers is an important field of research as outliers are ubiquitous and may arise across a variety of problems and domains. Bayesian optimization is method that heavily relies on probabilistic inference. This allows outstanding sample efficiency because the probabilistic machinery provides a memory of the whole optimization process. However, that virtue becomes a disadvantage when the memory is populated with outliers, inducing bias in the estimation. In this paper, we present an empirical evaluation of Bayesian optimization methods in the presence of outliers. The empirical evidence shows that Bayesian optimization with robust regression often produces suboptimal results. We then propose a new algorithm which combines robust regression (a Gaussian process with Student-t likelihood) with outlier diagnostics to classify data points as outliers or inliers. By using an scheduler for the classification of outliers, our method is more efficient and has better convergence over the standard robust regression. Furthermore, we show that even in controlled situations with no expected outliers, our method is able to produce better results.
Fractal dimension and lower bounds for geometric problems
Venue: arXiv cs.CC 2017
Year: 2017

We study the complexity of geometric problems on spaces of low fractal dimension. It was recently shown by [Sidiropoulos & Sridhar, SoCG 2017] that several problems admit improved solutions when the input is a pointset in Euclidean space with fractal dimension smaller than the ambient dimension. In this paper we prove nearly-matching lower bounds, thus establishing nearly-optimal bounds for various problems as a function of the fractal dimension. More specifically, we show that for any set of $n$ points in $d$-dimensional Euclidean space, of fractal dimension $δ\in (1,d)$, for any $ε>0$ and $c\geq 1$, any $c$-spanner must have treewidth at least $Ω\left( \frac{n^{1-1/(δ- ε)}}{c^{d-1}} \right)$, matching the previous upper bound. The construction used to prove this lower bound on the treewidth of spanners can also be used to derive lower bounds on the running time of algorithms for various problems, assuming the Exponential Time Hypothesis. We provide two prototypical results of this type. For any $δ\in (1,d)$ and any $ε>0$ we show that: 1) $d$-dimensional Euclidean TSP on $n$ points with fractal dimension at most $δ$ cannot be solved in time $2^{O\left(n^{1-1/(δ- ε)} \right)}$. The best-known upper bound is $2^{O(n^{1-1/δ} \log n)}$. 2) The problem of finding $k$-pairwise non-intersecting $d$-dimensional unit balls/axis parallel unit cubes with centers having fractal dimension at most $δ$ cannot be solved in time $f(k)n^{O \left(k^{1-1/(δ- ε)}\right)}$ for any computable function $f$. The best-known upper bound is $n^{O(k^{1-1/δ} \log n)}$. The above results nearly match previously known upper bounds from [Sidiropoulos & Sridhar, SoCG 2017], and generalize analogous lower bounds for the case of ambient dimension due to [Marx & Sidiropoulos, SoCG 2014].
Applying the Residue Number System to Network Inference
Venue: arXiv cs.AR 2017
Year: 2017

This work explores the lesser studied objective of optimizing the multiply-and-accumulates executed during evaluation of the network. In particular, we propose using the Residue Number System (RNS) as the internal number representation across all layer evaluations, allowing us to explore usage of the more power-efficient RNS multipliers and adders. Using results from simulation of our RNS arithmetic block implementations, we show theoretical power advantages of using RNS for an end-to-end evaluator.
The Effectiveness of Data Augmentation in Image Classification using Deep Learning
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we explore and compare multiple solutions to the problem of data augmentation in image classification. Previous work has demonstrated the effectiveness of data augmentation through simple techniques, such as cropping, rotating, and flipping input images. We artificially constrain our access to data to a small subset of the ImageNet dataset, and compare each data augmentation technique in turn. One of the more successful data augmentations strategies is the traditional transformations mentioned above. We also experiment with GANs to generate images of different styles. Finally, we propose a method to allow a neural net to learn augmentations that best improve the classifier, which we call neural augmentation. We discuss the successes and shortcomings of this method on various datasets.
Stochastic Low-Rank Bandits
Venue: arXiv cs.LG 2017
Year: 2017

Many problems in computer vision and recommender systems involve low-rank matrices. In this work, we study the problem of finding the maximum entry of a stochastic low-rank matrix from sequential observations. At each step, a learning agent chooses pairs of row and column arms, and receives the noisy product of their latent values as a reward. The main challenge is that the latent values are unobserved. We identify a class of non-negative matrices whose maximum entry can be found statistically efficiently and propose an algorithm for finding them, which we call LowRankElim. We derive a $\DeclareMathOperator{\poly}{poly} O((K + L) \poly(d) Δ^{-1} \log n)$ upper bound on its $n$-step regret, where $K$ is the number of rows, $L$ is the number of columns, $d$ is the rank of the matrix, and $Δ$ is the minimum gap. The bound depends on other problem-specific constants that clearly do not depend $K L$. To the best of our knowledge, this is the first such result in the literature.
Maze solvers demystified and some other thoughts
Venue: arXiv cs.ET 2017
Year: 2017

There is a growing interest towards implementation of maze solving in spatially-extended physical, chemical and living systems. Several reports of prototypes attracted great publicity, e.g. maze solving with slime mould and epithelial cells, maze navigating droplets. We show that most prototypes utilise one of two phenomena: a shortest path in a maze is a path of the least resistance for fluid and current flow, and a shortest path is a path of the steepest gradient of chemoattractants. We discuss that substrates with so-called maze-solving capabilities simply trace flow currents or chemical diffusion gradients. We illustrate our thoughts with a model of flow and experiments with slime mould. The chapter ends with a discussion of experiments on maze solving with plant roots and leeches which show limitations of the chemical diffusion maze-solving approach.
Can Balloons Produce Li-Fi? A Disaster Management Perspective
Venue: arXiv cs.IT 2017
Year: 2017

Natural calamities and disasters disrupt the conventional communication setups and the wireless bandwidth becomes constrained. A safe and cost-effective solution for communication and data access in such scenarios is long needed. Light-Fidelity (Li-Fi) which promises wireless access to data at high speeds using visible light can be a good option. Visible light being safe to use for wireless access in such affected environments also provides illumination. Importantly, when a Li-Fi unit is attached to an air balloon and a network of such Li-Fi balloons are coordinated to form a Li-Fi balloon network, data can be accessed anytime and anywhere required and hence many lives can be tracked and saved. We propose this idea of a Li-Fi balloon and give an overview of its design using the Philips Li-Fi hardware. Further, we propose the concept of a balloon network and coin it with an acronym, the LiBNet. We consider the balloons to be arranged as a homogeneous Poisson point process in the LiBNet and we derive the mean co-channel interference for such an arrangement.
A High-Level Rule-based Language for Software Defined Network Programming based on OpenFlow
Venue: arXiv cs.NI 2017
Year: 2017

This paper proposes XML-Defined Network policies (XDNP), a new high-level language based on XML notation, to describe network control rules in Software Defined Network environments. We rely on existing OpenFlow controllers specifically Floodlight but the novelty of this project is to separate complicated language- and framework-specific APIs from policy descriptions. This separation makes it possible to extend the current work as a northbound higher level abstraction that can support a wide range of controllers who are based on different programming languages. By this approach, we believe that network administrators can develop and deploy network control policies easier and faster.
Ergodic Capacity Analysis of Wireless Powered AF Relaying Systems over $α$-$μ$ Fading Channels
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we consider a two-hop amplify-and-forward (AF) relaying system, where the relay node is energy-constrained and harvests energy from the source node. In the literature, there are three main energy-harvesting (EH) protocols, namely, time-switching relaying (TSR), power-splitting (PS) relaying (PSR) and ideal relaying receiver (IRR). Unlike the existing studies, in this paper, we consider $α$-$μ$ fading channels. In this respect, we derive accurate unified analytical expressions for the ergodic capacity for the aforementioned protocols over independent but not identically distributed (i.n.i.d) $α$-$μ$ fading channels. Three special cases of the $α$-$μ$ model, namely, Rayleigh, Nakagami-mandWeibull fading channels were investigated. Our analysis is verified through numerical and simulation results. It is shown that finding the optimal value of the PS factor for the PSR protocol and the EH time fraction for the TSR protocol is a crucial step in achieving the best network performance.
Social Media Writing Style Fingerprint
Venue: arXiv cs.CL 2017
Year: 2017

We present our approach for computer-aided social media text authorship attribution based on recent advances in short text authorship verification. We use various natural language techniques to create word-level and character-level models that act as hidden layers to simulate a simple neural network. The choice of word-level and character-level models in each layer was informed through validation performance. The output layer of our system uses an unweighted majority vote vector to arrive at a conclusion. We also considered writing bias in social media posts while collecting our training dataset to increase system robustness. Our system achieved a precision, recall, and F-measure of 0.82, 0.926 and 0.869 respectively.
Real-time Egocentric Gesture Recognition on Mobile Head Mounted Displays
Venue: arXiv cs.CV 2017
Year: 2017

Mobile virtual reality (VR) head mounted displays (HMD) have become popular among consumers in recent years. In this work, we demonstrate real-time egocentric hand gesture detection and localization on mobile HMDs. Our main contributions are: 1) A novel mixed-reality data collection tool to automatic annotate bounding boxes and gesture labels; 2) The largest-to-date egocentric hand gesture and bounding box dataset with more than 400,000 annotated frames; 3) A neural network that runs real time on modern mobile CPUs, and achieves higher than 76% precision on gesture recognition across 8 classes.
Edge Computing Aware NOMA for 5G Networks
Venue: arXiv cs.NI 2017
Year: 2017

With the fast development of Internet of things (IoT), the fifth generation (5G) wireless networks need to provide massive connectivity of IoT devices and meet the demand for low latency. To satisfy these requirements, Non-Orthogonal Multiple Access (NOMA) has been recognized as a promising solution for 5G networks to significantly improve the network capacity. In parallel with the development of NOMA techniques, Mobile Edge Computing (MEC) is becoming one of the key emerging technologies to reduce the latency and improve the Quality of Service (QoS) for 5G networks. In order to capture the potential gains of NOMA in the context of MEC, this paper proposes an edge computing aware NOMA technique which can enjoy the benefits of uplink NOMA in reducing MEC users' uplink energy consumption. To this end, we formulate a NOMA based optimization framework which minimizes the energy consumption of MEC users via optimizing the user clustering, computing and communication resource allocation, and transmit powers. In particular, similar to frequency Resource Blocks (RBs), we divide the computing capacity available at the cloudlet to computing RBs. Accordingly, we explore the joint allocation of the frequency and computing RBs to the users that are assigned to different order indices within the NOMA clusters. We also design an efficient heuristic algorithm for user clustering and RBs allocation, and formulate a convex optimization problem for the power control to be solved independently per NOMA cluster. The performance of the proposed NOMA scheme is evaluated via simulations.
Fourteen Years of Software Engineering at ETH Zurich
Venue: arXiv cs.SE 2017
Year: 2017

A Chair of Software Engineering existed at ETH Zurich, the Swiss Federal Insti-tute of Technology, from 1 October 2001 to 31 January 2016, under my leader-ship. Our work, summarized here, covered a wide range of theoretical and practi-cal topics, with object technology in the Eiffel method as the unifying thread .
Queueing Analysis for Block Fading Rayleigh Channels in the Low SNR Regime
Venue: arXiv cs.IT 2017
Year: 2017

Wireless fading channels suffer from both channel fadings and Additive White Gaussian Noise (AWGN). As a result, it is impossible for fading channels to support a constant rate data stream without using buffers. In this paper, we consider information transmission over an infinite-buffer-aided block Rayleigh fading channel in the low signal-to-noise ratio (SNR) regime. We characterize the transmission capability of the channel in terms of stationary queue length distribution, packet delay, as well as data rate. Based on the memoryless property of the service provided by the channel in each block, we formulate the transmission process as a discrete time discrete state $D/G/1$ queueing problem. The obtained results provide a full characterization of block Rayleigh fading channels and can be extended to the finite-buffer-aided transmissions.
Approximation Algorithms for Replenishment Problems with Fixed Turnover Times
Venue: arXiv cs.DS 2017
Year: 2017

We introduce and study a class of optimization problems we coin replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Nodes with capacity for storing a certain commodity are located at various places; at each node the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Nodes should never run empty, and to prevent this we may schedule nodes for replenishment every day. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a node becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations. Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each store and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives: min-avg minimizes the average tour length and min-max minimizes the maximum tour length over all days. For min-max we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. For min-avg we present a logarithmic approximation on general metrics, 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open.
CIM compliant multiplatform approach for cyber-physical energy system assessment
Venue: arXiv cs.SE 2017
Year: 2017

With high penetration of distributed renewable energy resources along with sophisticated automation and information technology, cyber-physical energy systems (CPES, i.e. Smart Grids here) requires a holistic approach to evaluate the integration at a system level, addressing all relevant domains. Hybrid cloud SCADA (Supervisory, Control And Data Acquisition), allowing laboratories to be linked in a consistent infrastructure can provide the support for such multi-platform experiments. This paper presents the procedure to implement a CIM (Common Information Model) compliant hybrid cloud SCADA, with database and client adaptive to change in system topology, as well as CIM library update. This innovative way ensures interoperability among the partner platforms and provides support to multi-platform holistic approach for CPES assessment.
A Brief Overview of the KTA WCET Tool
Venue: arXiv cs.SE 2017
Year: 2017

KTA (KTH's timing analyzer) is a research tool for performing timing analysis of program code. The currently available toolchain can perform two different kinds of analyses: i) exhaustive fine-grained timing analysis, where timing information can be provided between arbitrary timing program points within a function, and ii) abstract search-based timing analysis, where the tool can perform optimal worst-case execution time (WCET) analysis. The latter is based on a technique that combines divide-and-conquer search and abstract interpretation. The tool is under development and currently supports a subset of the MIPS instruction set architecture.
Quantitative Implementation Strategies for Safety Controllers
Venue: arXiv cs.SY 2017
Year: 2017

We consider the symbolic controller synthesis approach to enforce safety specifications on perturbed, nonlinear control systems. In general, in each state of the system several control values might be applicable to enforce the safety requirement and in the implementation one has the burden of picking a particular control value out of possibly many. We present a class of implementation strategies to obtain a controller with certain performance guarantees. This class includes two existing implementation strategies from the literature, based on discounted payoff and mean-payoff games. We unify both approaches by using games characterized by a single discount factor determining the implementation. We evaluate different implementations from our class experimentally on two case studies. We show that the choice of the discount factor has a significant influence on the average long-term costs, and the best performance guarantee for the symbolic model does not result in the best implementation. Comparing the optimal choice of the discount factor here with the previously proposed values, the costs differ by a factor of up to 50. Our approach therefore yields a method to choose systematically a good implementation for safety controllers with quantitative objectives.
Prevalence of DNSSEC for hospital websites in Illinois
Venue: arXiv cs.CY 2017
Year: 2017

The domain name system translates human friendly web addresses to a computer readable internet protocol address. This basic infrastructure is insecure and can be manipulated. Deployment of technology to secure the DNS system has been slow, reaching about 20% of all web sites based in the USA. Little is known about the efforts hospitals and health systems make to secure the domain name system for their websites. To investigate the prevalence of implementing Domain Name System Security Extensions (DNSSEC), we analyzed the websites of the 210 public hospitals in the state of Illinois, USA. Only one Illinois hospital website was found to have implemented DNSSEC by December, 2017.
SEE: Towards Semi-Supervised End-to-End Scene Text Recognition
Venue: arXiv cs.CV 2017
Year: 2017

Detecting and recognizing text in natural scene images is a challenging, yet not completely solved task. In recent years several new systems that try to solve at least one of the two sub-tasks (text detection and text recognition) have been proposed. In this paper we present SEE, a step towards semi-supervised neural networks for scene text detection and recognition, that can be optimized end-to-end. Most existing works consist of multiple deep neural networks and several pre-processing steps. In contrast to this, we propose to use a single deep neural network, that learns to detect and recognize text from natural images, in a semi-supervised way. SEE is a network that integrates and jointly learns a spatial transformer network, which can learn to detect text regions in an image, and a text recognition network that takes the identified text regions and recognizes their textual content. We introduce the idea behind our novel approach and show its feasibility, by performing a range of experiments on standard benchmark datasets, where we achieve competitive results.