OpenRaiser/Intern-Atlas huggingface dataset:
Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
Venue: arXiv cs.LG 2018
Year: 2018

Random Fourier features is one of the most popular techniques for scaling up kernel methods, such as kernel ridge regression. However, despite impressive empirical results, the statistical properties of random Fourier features are still not well understood. In this paper we take steps toward filling this gap. Specifically, we approach random Fourier features from a spectral matrix approximation point of view, give tight bounds on the number of Fourier features required to achieve a spectral approximation, and show how spectral matrix approximation bounds imply statistical guarantees for kernel ridge regression. Qualitatively, our results are twofold: on the one hand, we show that random Fourier feature approximation can provably speed up kernel ridge regression under reasonable assumptions. At the same time, we show that the method is suboptimal, and sampling from a modified distribution in Fourier space, given by the leverage function of the kernel, yields provably better performance. We study this optimal sampling distribution for the Gaussian kernel, achieving a nearly complete characterization for the case of low-dimensional bounded datasets. Based on this characterization, we propose an efficient sampling scheme with guarantees superior to random Fourier features in this regime.
System Description of CITlab's Recognition & Retrieval Engine for ICDAR2017 Competition on Information Extraction in Historical Handwritten Records
Venue: arXiv cs.IR 2018
Year: 2018

We present a recognition and retrieval system for the ICDAR2017 Competition on Information Extraction in Historical Handwritten Records which successfully infers person names and other data from marriage records. The system extracts information from the line images with a high accuracy and outperforms the baseline. The optical model is based on Neural Networks. To infer the desired information, regular expressions are used to describe the set of feasible words sequences.
Towards a Viewpoint-specific Metamodel for Model-driven Development of Microservice Architecture
Venue: arXiv cs.SE 2018
Year: 2018

Microservice Architecture (MSA) is a service-based architectural style with a strong emphasis on high cohesion and loose coupling. It is commonly regarded as a descendant of Service-oriented Architecture (SOA) and thus might draw on existing findings of SOA research. This paper presents a metamodel for Model-driven Development (MDD) of MSA, which is deduced from existing SOA modeling approaches, but also incorporates MSA-specific modeling concepts. It is divided into the three viewpoints Data, Service and Operation, each of which encapsulates concepts related to a certain aspect of MSA. The metamodel aims to support DevOps-based MSA development and automatic transformation of metamodel instances into MSA implementations.
Design and Implementation of a Remote Care Application Based on Microservice Architecture
Venue: arXiv cs.SE 2018
Year: 2018

Microservice Architecture (MSA) is an architectural style for service-based software systems. MSA puts a strong emphasis on high cohesion and loose coupling of the services that provide systems' functionalities. As a result of this, MSA-based software architectures exhibit increased scalability and extensibility, and facilitate the application of continuous integration techniques. This paper presents a case study of an MSA-based Remote Care Application (RCA) that allows caregivers to remotely access smart home devices. The goal of the RCA is to assist persons being cared in Activities of Daily Living. Employing MSA for the realization of the RCA yielded several lessons learned, e.g., (i) direct transferability of domain models based on Domain-driven Design; (ii) more efficient integration of features; (iii) speedup of feature delivery due to MSA facilitating automated deployment.
It Is Easy to Be Wise After the Event: Communicating Finite-State Machines Capture First-Order Logic with "Happened Before"
Venue: arXiv cs.LO 2018
Year: 2018

Message sequence charts (MSCs) naturally arise as executions of communicating finite-state machines (CFMs), in which finite-state processes exchange messages through unbounded FIFO channels. We study the first-order logic of MSCs, featuring Lamport's happened-before relation. We introduce a star-free version of propositional dynamic logic (PDL) with loop and converse. Our main results state that (i) every first-order sentence can be transformed into an equivalent star-free PDL sentence (and conversely), and (ii) every star-free PDL sentence can be translated into an equivalent CFM. This answers an open question and settles the exact relation between CFMs and fragments of monadic second-order logic. As a byproduct, we show that first-order logic over MSCs has the three-variable property.
Format Abstraction for Sparse Tensor Algebra Compilers
Venue: arXiv cs.MS 2018
Year: 2018

This paper shows how to build a sparse tensor algebra compiler that is agnostic to tensor formats (data layouts). We develop an interface that describes formats in terms of their capabilities and properties, and show how to build a modular code generator where new formats can be added as plugins. We then describe six implementations of the interface that compose to form the dense, CSR/CSF, COO, DIA, ELL, and HASH tensor formats and countless variants thereof. With these implementations at hand, our code generator can generate code to compute any tensor algebra expression on any combination of the aforementioned formats. To demonstrate our technique, we have implemented it in the taco tensor algebra compiler. Our modular code generator design makes it simple to add support for new tensor formats, and the performance of the generated code is competitive with hand-optimized implementations. Furthermore, by extending taco to support a wider range of formats specialized for different application and data characteristics, we can improve end-user application performance. For example, if input data is provided in the COO format, our technique allows computing a single matrix-vector multiplication directly with the data in COO, which is up to 3.6$\times$ faster than by first converting the data to CSR.
Centralized Caching and Delivery of Correlated Contents over a Gaussian Broadcast Channel
Venue: arXiv cs.IT 2018
Year: 2018

Content delivery in a multi-user cache-aided broadcast network is studied, where a server holding a database of correlated contents communicates with the users over a Gaussian broadcast channel (BC). The minimum transmission power required to satisfy all possible demand combinations is studied, when the users are equipped with caches of equal size. A lower bound on the required transmit power is derived, assuming uncoded cache placement, as a function of the cache capacity. A centralized joint cache and channel coding scheme is proposed, which not only utilizes the user's local caches, but also exploits the correlation among the contents in the database. This scheme provides an upper bound on the minimum required transmit power for a given cache capacity. Our results indicate that exploiting the correlations among the contents in a cache-aided Gaussian BC can provide significant energy savings.
Two-Stream Binocular Network: Accurate Near Field Finger Detection Based On Binocular Images
Venue: arXiv cs.CV 2018
Year: 2018

Fingertip detection plays an important role in human computer interaction. Previous works transform binocular images into depth images. Then depth-based hand pose estimation methods are used to predict 3D positions of fingertips. Different from previous works, we propose a new framework, named Two-Stream Binocular Network (TSBnet) to detect fingertips from binocular images directly. TSBnet first shares convolutional layers for low level features of right and left images. Then it extracts high level features in two-stream convolutional networks separately. Further, we add a new layer: binocular distance measurement layer to improve performance of our model. To verify our scheme, we build a binocular hand image dataset, containing about 117k pairs of images in training set and 10k pairs of images in test set. Our methods achieve an average error of 10.9mm on our test set, outperforming previous work by 5.9mm (relatively 35.1%).
Weighted model counting beyond two-variable logic
Venue: arXiv cs.LO 2018
Year: 2018

It was recently shown by van den Broeck at al. that the symmetric weighted first-order model counting problem (WFOMC) for sentences of two-variable logic FO2 is in polynomial time, while it is Sharp-P_1 complete for some FO3-sentences. We extend the result for FO2 in two independent directions: to sentences of the form "phi and \forall\exists^=1 psi" with phi and psi in FO2, and to sentences formulated in the uniform one-dimensional fragment of FO, a recently introduced extension of two-variable logic with the capacity to deal with relation symbols of all arities. Note that the former generalizes the extension of FO2 with a functional relation symbol. We also identify a complete classification of first-order prefix classes according to whether WFOMC is in polynomial time or Sharp-P_1 complete.
Edit Distance between Unrooted Trees in Cubic Time
Venue: arXiv cs.DS 2018
Year: 2018

Edit distance between trees is a natural generalization of the classical edit distance between strings, in which the allowed elementary operations are contraction, uncontraction and relabeling of an edge. Demaine et al. [ACM Trans. on Algorithms, 6(1), 2009] showed how to compute the edit distance between rooted trees on $n$ nodes in $\mathcal{O}(n^{3})$ time. However, generalizing their method to unrooted trees seems quite problematic, and the most efficient known solution remains to be the previous $\mathcal{O}(n^{3}\log n)$ time algorithm by Klein [ESA 1998]. Given the lack of progress on improving this complexity, it might appear that unrooted trees are simply more difficult than rooted trees. We show that this is, in fact, not the case, and edit distance between unrooted trees on $n$ nodes can be computed in $\mathcal{O}(n^{3})$ time. A significantly faster solution is unlikely to exist, as Bringmann et al. [SODA 2018] proved that the complexity of computing the edit distance between rooted trees cannot be decreased to $\mathcal{O}(n^{3-ε})$ unless some popular conjecture fails, and the lower bound easily extends to unrooted trees. We also show that for two unrooted trees of size $m$ and $n$, where $m\le n$, our algorithm can be modified to run in $\mathcal{O}(nm^2(1+\log\frac nm))$. This, again, matches the complexity achieved by Demaine et al. for rooted trees, who also showed that this is optimal if we restrict ourselves to the so-called decomposition algorithms.
Moment analysis of linear time-varying dynamical systems with renewal transitions
Venue: arXiv cs.SY 2018
Year: 2018

Stochastic dynamics of several systems can be modeled via piecewise deterministic time evolution of the state, interspersed by random discrete events. Within this general class of systems, we consider time-triggered stochastic hybrid systems (TTSHS), where the state evolves continuously according to a linear time-varying dynamical system. Discrete events occur based on an underlying renewal process (timer), and the intervals between successive events follow an arbitrary continuous probability density function. Moreover, whenever the event occurs, the state is reset based on a linear affine transformation that allows for the inclusion of state-dependent and independent noise terms. Our key contribution is derivation of necessary and sufficient conditions for the stability of statistical moments, along with exact analytical expressions for the steady-state moments. These results are illustrated on an example from cell biology, where deterministic synthesis and decay of a gene product (RNA or protein) is coupled to random timing of cell-division events. As experimentally observed, cell-division events occur based on an internal timer that measures the time elapsed since the start of cell cycle (i.e., last event). Upon division, the gene product level is halved, together with a state-dependent noise term that arises due to randomness in the partitioning of molecules between two daughter cells. We show that the TTSHS framework is conveniently suited to capture the time evolution of gene product levels, and derive unique formulas connecting its mean and variance to underlying model parameters and noise mechanisms. Systematic analysis of the formulas reveal counterintuitive insights, such as, if the partitioning noise is large then making the timing of cell division more random reduces noise in gene product levels.
Pushing the Limits of Unconstrained Face Detection: a Challenge Dataset and Baseline Results
Venue: arXiv cs.CV 2018
Year: 2018

Face detection has witnessed immense progress in the last few years, with new milestones being surpassed every year. While many challenges such as large variations in scale, pose, appearance are successfully addressed, there still exist several issues which are not specifically captured by existing methods or datasets. In this work, we identify the next set of challenges that requires attention from the research community and collect a new dataset of face images that involve these issues such as weather-based degradations, motion blur, focus blur and several others. We demonstrate that there is a considerable gap in the performance of state-of-the-art detectors and real-world requirements. Hence, in an attempt to fuel further research in unconstrained face detection, we present a new annotated Unconstrained Face Detection Dataset (UFDD) with several challenges and benchmark recent methods. Additionally, we provide an in-depth analysis of the results and failure cases of these methods. The dataset as well as baseline results will be made publicly available in due time. The UFDD dataset as well as baseline results are available at: www.ufdd.info/
From product recommendation to cyber-attack prediction: Generating attack graphs and predicting future attacks
Venue: arXiv cs.IR 2018
Year: 2018

Modern information society depends on reliable functionality of information systems infrastructure, while at the same time the number of cyber-attacks has been increasing over the years and damages have been caused. Furthermore, graphs can be used to show paths than can be exploited by attackers to intrude into systems and gain unauthorized access through vulnerability exploitation. This paper presents a method that builds attack graphs using data supplied from the maritime supply chain infrastructure. The method delivers all possible paths that can be exploited to gain access. Then, a recommendation system is utilized to make predictions about future attack steps within the network. We show that recommender systems can be used in cyber defense by predicting attacks. The goal of this paper is to identify attack paths and show how a recommendation method can be used to classify future cyber-attacks in terms of risk management. The proposed method has been experimentally evaluated and validated, with the results showing that it is both practical and effective.
Adaptive Sensing for Learning Nonstationary Environment Models
Venue: arXiv cs.LG 2018
Year: 2018

Most environmental phenomena, such as wind profiles, ozone concentration and sunlight distribution under a forest canopy, exhibit nonstationary dynamics i.e. phenomenon variation change depending on the location and time of occurrence. Non-stationary dynamics pose both theoretical and practical challenges to statistical machine learning algorithms aiming to accurately capture the complexities governing the evolution of such processes. In this paper, we address the sampling aspects of the problem of learning nonstationary spatio-temporal models, and propose an efficient yet simple algorithm - LISAL. The core idea in LISAL is to learn two models using Gaussian processes (GPs) wherein the first is a nonstationary GP directly modeling the phenomenon. The second model uses a stationary GP representing a latent space corresponding to changes in dynamics, or the nonstationarity characteristics of the first model. LISAL involves adaptively sampling the latent space dynamics using information theory quantities to reduce the computational cost during the learning phase. The relevance of LISAL is extensively validated using multiple real world datasets.
Success Probability and Area Spectral Efficiency of a VANET Modeled as a Cox Process
Venue: arXiv cs.IT 2018
Year: 2018

This paper analyzes the performance of a vehicular ad hoc network (VANET) modeled as a Cox process, where the spatial layout of the roads is modeled by a Poisson line process (PLP) and the locations of nodes on each line are modeled as a 1D Poisson point process (PPP). For this setup, we characterize the success probability of a typical link and the area spectral efficiency (ASE) of the network assuming slotted ALOHA as the channel access scheme. We then concretely establish that the success probability of a typical link in a VANET modeled using a Cox process converges to that of a 1D and 2D PPP for some extreme values of the line and node densities. We also study the trends in success probability as a function of the system parameters and show that the optimum transmission probability that maximizes the ASE for this Cox process model differs significantly from those of the relatively-simpler 1D and 2D PPP models used commonly in the literature to model vehicular networks.
Universal approximations of invariant maps by neural networks
Venue: arXiv cs.NE 2018
Year: 2018

We describe generalizations of the universal approximation theorem for neural networks to maps invariant or equivariant with respect to linear representations of groups. Our goal is to establish network-like computational models that are both invariant/equivariant and provably complete in the sense of their ability to approximate any continuous invariant/equivariant map. Our contribution is three-fold. First, in the general case of compact groups we propose a construction of a complete invariant/equivariant network using an intermediate polynomial layer. We invoke classical theorems of Hilbert and Weyl to justify and simplify this construction; in particular, we describe an explicit complete ansatz for approximation of permutation-invariant maps. Second, we consider groups of translations and prove several versions of the universal approximation theorem for convolutional networks in the limit of continuous signals on euclidean spaces. Finally, we consider 2D signal transformations equivariant with respect to the group SE(2) of rigid euclidean motions. In this case we introduce the "charge--conserving convnet" -- a convnet-like computational model based on the decomposition of the feature space into isotypic representations of SO(2). We prove this model to be a universal approximator for continuous SE(2)--equivariant signal transformations.
Local module identification in dynamic networks: do more inputs guarantee smaller variance?
Venue: arXiv cs.SY 2018
Year: 2018

Recent developments in science and engineering have motivated control systems to be considered as interconnected and networked systems. From a system identification point of view, modelling of a local module in such a structured system is a relevant and interesting problem. This work focuses on the quality, in terms of variance, of an estimate of a local module. We analyse which predictor input signals are relevant and contribute to variance reduction, while still guaranteeing the consistency of the estimate. For a targeted local module, a comparison of its estimate variance is made between a full-MISO approach and an immersed network setting, where a reduced number of inputs is used, while still guaranteeing consistency. A case study of a four-node network is considered and it is shown that a smaller set of predictor inputs can, under some conditions, result in a smaller variance compared to the full-MISO approach.
An adaptive self-organizing fuzzy logic controller in a serious game for motor impairment rehabilitation
Venue: arXiv cs.HC 2018
Year: 2018

Rehabilitation robotics combined with video game technology provides a means of assisting in the rehabilitation of patients with neuromuscular disorders by performing various facilitation movements. The current work presents ReHabGame, a serious game using a fusion of implemented technologies that can be easily used by patients and therapists to assess and enhance sensorimotor performance and also increase the activities in the daily lives of patients. The game allows a player to control avatar movements through a Kinect Xbox, Myo armband and rudder foot pedal, and involves a series of reach-grasp-collect tasks whose difficulty levels are learnt by a fuzzy interface. The orientation, angular velocity, head and spine tilts and other data generated by the player are monitored and saved, whilst the task completion is calculated by solving an inverse kinematics algorithm which orientates the upper limb joints of the avatar. The different values in upper body quantities of movement provide fuzzy input from which crisp output is determined and used to generate an appropriate subsequent rehabilitation game level. The system can thus provide personalised, autonomously-learnt rehabilitation programmes for patients with neuromuscular disorders with superior predictions to guide the development of improved clinical protocols compared to traditional theraputic activities.
Delay-Energy Joint Optimization for Task Offloading in Mobile Edge Computing
Venue: arXiv cs.NI 2018
Year: 2018

Mobile-edge computing (MEC) has been envisioned as a promising paradigm to meet ever-increasing resource demands of mobile users, prolong battery lives of mobile devices, and shorten request response delays experienced by users. An MEC environment consists of many MEC servers and ubiquitous access points interconnected into an edge cloud network. Mobile users can offload their computing-intensive tasks to one or multiple MEC servers for execution to save their batteries. Due to large numbers of MEC servers deployed in MEC, selecting a subset of servers to serve user tasks while satisfying delay requirements of their users is challenging. In this paper, we formulate a novel delay-energy joint optimization problem through jointly considering the CPU-cycle frequency scheduling at mobile devices, server selection to serve user offloading tasks, and task allocations to the selected servers. To this end, we first formulate the problem as a mixed-integer nonlinear programming, due to the hardness to solve this nonlinear programming, we instead then relax the problem into a nonlinear programming problem that can be solved in polynomial time. We also show how to derive a feasible solution to the original problem from the solution of this relaxed solution. We finally conduct experiments to evaluate the performance of the proposed algorithm. Experimental results demonstrate that the proposed algorithm is promising.