OpenRaiser/Intern-Atlas huggingface dataset:
Error Analysis on Graph Laplacian Regularized Estimator
Venue: arXiv cs.LG 2019
Year: 2019

We provide a theoretical analysis of the representation learning problem aimed at learning the latent variables (design matrix) $Θ$ of observations $Y$ with the knowledge of the coefficient matrix $X$. The design matrix is learned under the assumption that the latent variables $Θ$ are smooth with respect to a (known) topological structure $\mathcal{G}$. To learn such latent variables, we study a graph Laplacian regularized estimator, which is the penalized least squares estimator with penalty term proportional to a Laplacian quadratic form. This type of estimators has recently received considerable attention due to its capability in incorporating underlying topological graph structure of variables into the learning process. While the estimation problem can be solved efficiently by state-of-the-art optimization techniques, its statistical consistency properties have been largely overlooked. In this work, we develop a non-asymptotic bound of estimation error under the classical statistical setting, where sample size is larger than the ambient dimension of the latent variables. This bound illustrates theoretically the impact of the alignment between the data and the graph structure as well as the graph spectrum on the estimation accuracy. It also provides theoretical evidence of the advantage, in terms of convergence rate, of the graph Laplacian regularized estimator over classical ones (that ignore the graph structure) in case of a smoothness prior. Finally, we provide empirical results of the estimation error to corroborate the theoretical analysis.
A Minimal Template for Interactive Web-based Demonstrations of Musical Machine Learning
Venue: arXiv cs.HC 2019
Year: 2019

New machine learning algorithms are being developed to solve problems in different areas, including music. Intuitive, accessible, and understandable demonstrations of the newly built models could help attract the attention of people from different disciplines and evoke discussions. However, we notice that it has not been a common practice for researchers working on musical machine learning to demonstrate their models in an interactive way. To address this issue, we present in this paper an template that is specifically designed to demonstrate symbolic musical machine learning models on the web. The template comes with a small codebase, is open source, and is meant to be easy to use by any practitioners to implement their own demonstrations. Moreover, its modular design facilitates the reuse of the musical components and accelerates the implementation. We use the template to build interactive demonstrations of four exemplary music generation models. We show that the built-in interactivity and real-time audio rendering of the browser make the demonstration easier to understand and to play with. It also helps researchers to gain insights into different models and to A/B test them.
New Algorithms and Improved Guarantees for One-Bit Compressed Sensing on Manifolds
Venue: arXiv cs.IT 2019
Year: 2019

We study the problem of approximately recovering signals on a manifold from one-bit linear measurements drawn from either a Gaussian ensemble, partial circulant ensemble, or bounded orthonormal ensemble and quantized using Sigma-Delta or distributed noise shaping schemes. We assume we are given a Geometric Multi-Resolution Analysis, which approximates the manifold, and we propose a convex optimization algorithm for signal recovery. We prove an upper bound on the recovery error which outperforms prior works that use memoryless scalar quantization, requires a simpler analysis, and extends the class of measurements beyond Gaussians. Finally, we illustrate our results with numerical experiments.
Discrimination in the Age of Algorithms
Venue: arXiv cs.CY 2019
Year: 2019

The law forbids discrimination. But the ambiguity of human decision-making often makes it extraordinarily hard for the legal system to know whether anyone has actually discriminated. To understand how algorithms affect discrimination, we must therefore also understand how they affect the problem of detecting discrimination. By one measure, algorithms are fundamentally opaque, not just cognitively but even mathematically. Yet for the task of proving discrimination, processes involving algorithms can provide crucial forms of transparency that are otherwise unavailable. These benefits do not happen automatically. But with appropriate requirements in place, the use of algorithms will make it possible to more easily examine and interrogate the entire decision process, thereby making it far easier to know whether discrimination has occurred. By forcing a new level of specificity, the use of algorithms also highlights, and makes transparent, central tradeoffs among competing values. Algorithms are not only a threat to be regulated; with the right safeguards in place, they have the potential to be a positive force for equity.
COST Action IC 1402 ArVI: Runtime Verification Beyond Monitoring -- Activity Report of Working Group 1
Venue: arXiv cs.SE 2019
Year: 2019

This report presents the activities of the first working group of the COST Action ArVI, Runtime Verification beyond Monitoring. The report aims to provide an overview of some of the major core aspects involved in Runtime Verification. Runtime Verification is the field of research dedicated to the analysis of system executions. It is often seen as a discipline that studies how a system run satisfies or violates correctness properties. The report exposes a taxonomy of Runtime Verification (RV) presenting the terminology involved with the main concepts of the field. The report also develops the concept of instrumentation, the various ways to instrument systems, and the fundamental role of instrumentation in designing an RV framework. We also discuss how RV interplays with other verification techniques such as model-checking, deductive verification, model learning, testing, and runtime assertion checking. Finally, we propose challenges in monitoring quantitative and statistical data beyond detecting property violation.
Semantic Label Reduction Techniques for Autonomous Driving
Venue: arXiv cs.LG 2019
Year: 2019

Semantic segmentation maps can be used as input to models for maneuvering the controls of a car. However, not all labels may be necessary for making the control decision. One would expect that certain labels such as road lanes or sidewalks would be more critical in comparison with labels for vegetation or buildings which may not have a direct influence on the car's driving decision. In this appendix, we evaluate and quantify how sensitive and important the different semantic labels are for controlling the car. Labels that do not influence the driving decision are remapped to other classes, thereby simplifying the task by reducing to only labels critical for driving of the vehicle.
Finite-time influence systems and the Wisdom of Crowd effect
Venue: arXiv cs.SY 2019
Year: 2019

Recent contributions have studied how an influence system may affect the wisdom of crowd phenomenon. In the so-called naive learning setting, a crowd of individuals holds opinions that are statistically independent estimates of an unknown parameter; the crowd is wise when the average opinion converges to the true parameter in the limit of infinitely many individuals. Unfortunately, even starting from wise initial opinions, a crowd subject to certain influence systems may lose its wisdom. It is of great interest to characterize when an influence system preserves the crowd wisdom effect. In this paper we introduce and characterize numerous wisdom preservation properties of the basic French-DeGroot influence system model. Instead of requiring complete convergence to consensus as in the previous naive learning model by Golub and Jackson, we study finite-time executions of the French-DeGroot influence process and establish in this novel context the notion of prominent families (as a group of individuals with outsize influence). Surprisingly, finite-time wisdom preservation of the influence system is strictly distinct from its infinite-time version. We provide a comprehensive treatment of various finite-time wisdom preservation notions, counterexamples to meaningful conjectures, and a complete characterization of equal-neighbor influence systems.
Progressive Focus Search for the Static and Stochastic VRPTW with both Random Customers and Reveal Times
Venue: arXiv cs.AI 2019
Year: 2019

Static stochastic VRPs aim at modeling real-life VRPs by considering uncertainty on data. In particular, the SS-VRPTW-CR considers stochastic customers with time windows and does not make any assumption on their reveal times, which are stochastic as well. Based on customer request probabilities, we look for an a priori solution composed preventive vehicle routes, minimizing the expected number of unsatisfied customer requests at the end of the day. A route describes a sequence of strategic vehicle relocations, from which nearby requests can be rapidly reached. Instead of reoptimizing online, a so-called recourse strategy defines the way the requests are handled, whenever they appear. In this paper, we describe a new recourse strategy for the SS-VRPTW-CR, improving vehicle routes by skipping useless parts. We show how to compute the expected cost of a priori solutions, in pseudo-polynomial time, for this recourse strategy. We introduce a new meta-heuristic, called Progressive Focus Search (PFS), which may be combined with any local-search based algorithm for solving static stochastic optimization problems. PFS accelerates the search by using approximation factors: from an initial rough simplified problem, the search progressively focuses to the actual problem description. We evaluate our contributions on a new, real-world based, public benchmark.
MorteX method for contact along real and embedded surfaces: coupling X-FEM with the Mortar method
Venue: arXiv cs.CE 2019
Year: 2019

A method to treat frictional contact problems along embedded surfaces in the finite element framework is developed. Arbitrarily shaped embedded surfaces, cutting through finite element meshes, are handled by the X-FEM. The frictional contact problem is solved using the monolithic augmented Lagrangian method within the mortar framework which was adapted for handling embedded surfaces. We report that the resulting mixed formulation is prone to mesh locking in case of high elastic and mesh density contrasts across the contact interface. The mesh locking manifests itself in spurious stress oscillations in the vicinity of the contact interface. We demonstrate that in the classical patch test, these oscillations can be removed simply by using triangular blending elements. In a more general case, the triangulation is shown inefficient, therefore stabilization of the problem is achieved by adopting a recently proposed coarse-graining interpolation of Lagrange multipliers. Moreover, we demonstrate that the coarse-graining is also beneficial for the classical mortar method to avoid spurious oscillations for contact interfaces with high elastic contrast. The performance of this novel method, called MorteX, is demonstrated on several examples which show as accurate treatment of frictional contact along embedded surfaces as the classical mortar method along boundary fitted surfaces.
Efficient Randomized Test-And-Set Implementations
Venue: arXiv cs.DC 2019
Year: 2019

We study randomized test-and-set (TAS) implementations from registers in the asynchronous shared memory model with n processes. We introduce the problem of group election, a natural variant of leader election, and propose a framework for the implementation of TAS objects from group election objects. We then present two group election algorithms, each yielding an efficient TAS implementation. The first implementation has expected max-step complexity $O(\log^\ast k)$ in the location-oblivious adversary model, and the second has expected max-step complexity $O(\log\log k)$ against any read/write-oblivious adversary, where $k\leq n$ is the contention. These algorithms improve the previous upper bound by Alistarh and Aspnes [2] of $O(\log\log n)$ expected max-step complexity in the oblivious adversary model. We also propose a modification to a TAS algorithm by Alistarh, Attiya, Gilbert, Giurgiu, and Guerraoui [5] for the strong adaptive adversary, which improves its space complexity from super-linear to linear, while maintaining its $O(\log n)$ expected max-step complexity. We then describe how this algorithm can be combined with any randomized TAS algorithm that has expected max-step complexity $T(n)$ in a weaker adversary model, so that the resulting algorithm has $O(\log n)$ expected max-step complexity against any strong adaptive adversary and $O(T(n))$ in the weaker adversary model. Finally, we prove that for any randomized 2-process TAS algorithm, there exists a schedule determined by an oblivious adversary such that with probability at least $(1/4)^t$ one of the processes needs at least t steps to finish its TAS operation. This complements a lower bound by Attiya and Censor-Hillel [7] on a similar problem for $n\geq 3$ processes.
Reactive Control Meets Runtime Verification: A Case Study of Navigation
Venue: arXiv cs.RO 2019
Year: 2019

This paper presents an application of specification based runtime verification techniques to control mobile robots in a reactive manner. In our case study, we develop a layered control architecture where runtime monitors constructed from formal specifications are embedded into the navigation stack. We use temporal logic and regular expressions to describe safety requirements and mission specifications, respectively. An immediate benefit of our approach is that it leverages simple requirements and objectives of traditional control applications to more complex specifications in a non-intrusive and compositional way. Finally, we demonstrate a simulation of robots controlled by the proposed architecture and we discuss further extensions of our approach.
Registration-free Face-SSD: Single shot analysis of smiles, facial attributes, and affect in the wild
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we present a novel single shot face-related task analysis method, called Face-SSD, for detecting faces and for performing various face-related (classification/regression) tasks including smile recognition, face attribute prediction and valence-arousal estimation in the wild. Face-SSD uses a Fully Convolutional Neural Network (FCNN) to detect multiple faces of different sizes and recognise/regress one or more face-related classes. Face-SSD has two parallel branches that share the same low-level filters, one branch dealing with face detection and the other one with face analysis tasks. The outputs of both branches are spatially aligned heatmaps that are produced in parallel - therefore Face-SSD does not require that face detection, facial region extraction, size normalisation, and facial region processing are performed in subsequent steps. Our contributions are threefold: 1) Face-SSD is the first network to perform face analysis without relying on pre-processing such as face detection and registration in advance - Face-SSD is a simple and a single FCNN architecture simultaneously performing face detection and face-related task analysis - those are conventionally treated as separate consecutive tasks; 2) Face-SSD is a generalised architecture that is applicable for various face analysis tasks without modifying the network structure - this is in contrast to designing task-specific architectures; and 3) Face-SSD achieves real-time performance (21 FPS) even when detecting multiple faces and recognising multiple classes in a given image. Experimental results show that Face-SSD achieves state-of-the-art performance in various face analysis tasks by reaching a recognition accuracy of 95.76% for smile detection, 90.29% for attribute prediction, and Root Mean Square (RMS) error of 0.44 and 0.39 for valence and arousal estimation.
Multi-tier Caching Analysis in CDN-based Over-the-top Video Streaming Systems
Venue: arXiv cs.NI 2019
Year: 2019

Internet video traffic has been been rapidly increasing and is further expected to increase with the emerging 5G applications such as higher definition videos, IoT and augmented/virtual reality applications. As end-users consume video in massive amounts and in an increasing number of ways, the content distribution network (CDN) should be efficiently managed to improve the system efficiency. The streaming service can include multiple caching tiers, at the distributed servers and the edge routers, and efficient content management at these locations affect the quality of experience (QoE) of the end users. In this paper, we propose a model for video streaming systems, typically composed of a centralized origin server, several CDN sites, and edge-caches located closer to the end user. We comprehensively consider different systems design factors including the limited caching space at the CDN sites, allocation of CDN for a video request, choice of different ports (or paths) from the CDN and the central storage, bandwidth allocation, the edge-cache capacity, and the caching policy. We focus on minimizing a performance metric, stall duration tail probability (SDTP), and present a novel and efficient algorithm accounting for the multiple design flexibilities. The theoretical bounds with respect to the SDTP metric are also analyzed and presented. The implementation on a virtualized cloud system managed by Openstack demonstrate that the proposed algorithms can significantly improve the SDTP metric, compared to the baseline strategies.
BERT has a Mouth, and It Must Speak: BERT as a Markov Random Field Language Model
Venue: arXiv cs.CL 2019
Year: 2019

We show that BERT (Devlin et al., 2018) is a Markov random field language model. This formulation gives way to a natural procedure to sample sentences from BERT. We generate from BERT and find that it can produce high-quality, fluent generations. Compared to the generations of a traditional left-to-right language model, BERT generates sentences that are more diverse but of slightly worse quality.
Psi-Net: Shape and boundary aware joint multi-task deep network for medical image segmentation
Venue: arXiv cs.CV 2019
Year: 2019

Image segmentation is a primary task in many medical applications. Recently, many deep networks derived from U-Net have been extensively used in various medical image segmentation tasks. However, in most of the cases, networks similar to U-net produce coarse and non-smooth segmentations with lots of discontinuities. To improve and refine the performance of U-Net like networks, we propose the use of parallel decoders which along with performing the mask predictions also perform contour prediction and distance map estimation. The contour and distance map aid in ensuring smoothness in the segmentation predictions. To facilitate joint training of three tasks, we propose a novel architecture called Psi-Net with a single encoder and three parallel decoders (thus having a shape of $Ψ$), one decoder to learns the segmentation mask prediction and other two decoders to learn the auxiliary tasks of contour detection and distance map estimation. The learning of these auxiliary tasks helps in capturing the shape and the boundary information. We also propose a new joint loss function for the proposed architecture. The loss function consists of a weighted combination of Negative Log likelihood and Mean Square Error loss. We have used two publicly available datasets: 1) Origa dataset for the task of optic cup and disc segmentation and 2) Endovis segment dataset for the task of polyp segmentation to evaluate our model. We have conducted extensive experiments using our network to show our model gives better results in terms of segmentation, boundary and shape metrics.
Evaluation of Transfer Learning for Classification of: (1) Diabetic Retinopathy by Digital Fundus Photography and (2) Diabetic Macular Edema, Choroidal Neovascularization and Drusen by Optical Coherence Tomography
Venue: arXiv cs.LG 2019
Year: 2019

Deep learning has been successfully applied to a variety of image classification tasks. There has been keen interest to apply deep learning in the medical domain, particularly specialties that heavily utilize imaging, such as ophthalmology. One issue that may hinder application of deep learning to the medical domain is the vast amount of data necessary to train deep neural networks (DNNs). Because of regulatory and privacy issues associated with medicine, and the generally proprietary nature of data in medical domains, obtaining large datasets to train DNNs is a challenge, particularly in the ophthalmology domain. Transfer learning is a technique developed to address the issue of applying DNNs for domains with limited data. Prior reports on transfer learning have examined custom networks to fully train or used a particular DNN for transfer learning. However, to the best of my knowledge, no work has systematically examined a suite of DNNs for transfer learning for classification of diabetic retinopathy, diabetic macular edema, and two key features of age-related macular degeneration. This work attempts to investigate transfer learning for classification of these ophthalmic conditions. Part I gives a condensed overview of neural networks and the DNNs under evaluation. Part II gives the reader the necessary background concerning diabetic retinopathy and prior work on classification using retinal fundus photographs. The methodology and results of transfer learning for diabetic retinopathy classification are presented, showing that transfer learning towards this domain is feasible, with promising accuracy. Part III gives an overview of diabetic macular edema, choroidal neovascularization and drusen (features associated with age-related macular degeneration), and presents results for transfer learning evaluation using optical coherence tomography to classify these entities.
ReStoCNet: Residual Stochastic Binary Convolutional Spiking Neural Network for Memory-Efficient Neuromorphic Computing
Venue: arXiv cs.CV 2019
Year: 2019

In this work, we propose ReStoCNet, a residual stochastic multilayer convolutional Spiking Neural Network (SNN) composed of binary kernels, to reduce the synaptic memory footprint and enhance the computational efficiency of SNNs for complex pattern recognition tasks. ReStoCNet consists of an input layer followed by stacked convolutional layers for hierarchical input feature extraction, pooling layers for dimensionality reduction, and fully-connected layer for inference. In addition, we introduce residual connections between the stacked convolutional layers to improve the hierarchical feature learning capability of deep SNNs. We propose Spike Timing Dependent Plasticity (STDP) based probabilistic learning algorithm, referred to as Hybrid-STDP (HB-STDP), incorporating Hebbian and anti-Hebbian learning mechanisms, to train the binary kernels forming ReStoCNet in a layer-wise unsupervised manner. We demonstrate the efficacy of ReStoCNet and the presented HB-STDP based unsupervised training methodology on the MNIST and CIFAR-10 datasets. We show that residual connections enable the deeper convolutional layers to self-learn useful high-level input features and mitigate the accuracy loss observed in deep SNNs devoid of residual connections. The proposed ReStoCNet offers >20x kernel memory compression compared to full-precision (32-bit) SNN while yielding high enough classification accuracy on the chosen pattern recognition tasks.