OpenRaiser/Intern-Atlas huggingface dataset:
On the Connection Between Learning Two-Layers Neural Networks and Tensor Decomposition
Venue: arXiv cs.LG 2018
Year: 2018

We establish connections between the problem of learning a two-layer neural network and tensor decomposition. We consider a model with feature vectors $\boldsymbol x \in \mathbb R^d$, $r$ hidden units with weights $\{\boldsymbol w_i\}_{1\le i \le r}$ and output $y\in \mathbb R$, i.e., $y=\sum_{i=1}^r σ( \boldsymbol w_i^{\mathsf T}\boldsymbol x)$, with activation functions given by low-degree polynomials. In particular, if $σ(x) = a_0+a_1x+a_3x^3$, we prove that no polynomial-time learning algorithm can outperform the trivial predictor that assigns to each example the response variable $\mathbb E(y)$, when $d^{3/2}\ll r\ll d^2$. Our conclusion holds for a `natural data distribution', namely standard Gaussian feature vectors $\boldsymbol x$, and output distributed according to a two-layer neural network with random isotropic weights, and under a certain complexity-theoretic assumption on tensor decomposition. Roughly speaking, we assume that no polynomial-time algorithm can substantially outperform current methods for tensor decomposition based on the sum-of-squares hierarchy. We also prove generalizations of this statement for higher degree polynomial activations, and non-random weight vectors. Remarkably, several existing algorithms for learning two-layer networks with rigorous guarantees are based on tensor decomposition. Our results support the idea that this is indeed the core computational difficulty in learning such networks, under the stated generative model for the data. As a side result, we show that under this model learning the network requires accurate learning of its weights, a property that does not hold in a more general setting.
Robustness in Consensus Networks
Venue: arXiv cs.SY 2018
Year: 2018

We consider the problem of robustness in large consensus networks that occur in many areas such as distributed optimization. Robustness, in this context, is the scaling of performance measures, e.g. H2-norm, as a function of network dimension. We provide a formal framework to quantify the relation between such performance scaling and the convergence speed of the network. Specifically, we provide upper and lower bounds for the convergence speed in terms of robustness and discuss how these bounds scale with the network topology. The main contribution of this work is that we obtain tight bounds, that hold regardless of network topology. The work here also encompasses some results in convergence time analysis in previous literature.
Cooperative Robot Localization Using Event-triggered Estimation
Venue: arXiv cs.RO 2018
Year: 2018

This paper describes a novel communication-spare cooperative localization algorithm for a team of mobile unmanned robotic vehicles. Exploiting an event-based estimation paradigm, robots only send measurements to neighbors when the expected innovation for state estimation is high. Since agents know the event-triggering condition for measurements to be sent, the lack of a measurement is thus also informative and fused into state estimates. The robots use a Covariance Intersection (CI) mechanism to occasionally synchronize their local estimates of the full network state. In addition, heuristic balancing dynamics on the robots' CI-triggering thresholds ensure that, in large diameter networks, the local error covariances remains below desired bounds across the network. Simulations on both linear and nonlinear dynamics/measurement models show that the event-triggering approach achieves nearly optimal state estimation performance in a wide range of operating conditions, even when using only a fraction of the communication cost required by conventional full data sharing. The robustness of the proposed approach to lossy communications, as well as the relationship between network topology and CI-based synchronization requirements, are also examined.
Free complete Wasserstein algebras
Venue: arXiv cs.LO 2018
Year: 2018

We present an algebraic account of the Wasserstein distances $W_p$ on complete metric spaces, for $p \geq 1$. This is part of a program of a quantitative algebraic theory of effects in programming languages. In particular, we give axioms, parametric in $p$, for algebras over metric spaces equipped with probabilistic choice operations. The axioms say that the operations form a barycentric algebra and that the metric satisfies a property typical of the Wasserstein distance $W_p$. We show that the free complete such algebra over a complete metric space is that of the Radon probability measures with finite moments of order $p$, equipped with the Wasserstein distance as metric and with the usual binary convex sums as operations.
3LC: Lightweight and Effective Traffic Compression for Distributed Machine Learning
Venue: arXiv cs.LG 2018
Year: 2018

The performance and efficiency of distributed machine learning (ML) depends significantly on how long it takes for nodes to exchange state changes. Overly-aggressive attempts to reduce communication often sacrifice final model accuracy and necessitate additional ML techniques to compensate for this loss, limiting their generality. Some attempts to reduce communication incur high computation overhead, which makes their performance benefits visible only over slow networks. We present 3LC, a lossy compression scheme for state change traffic that strikes balance between multiple goals: traffic reduction, accuracy, computation overhead, and generality. It combines three new techniques---3-value quantization with sparsity multiplication, quartic encoding, and zero-run encoding---to leverage strengths of quantization and sparsification techniques and avoid their drawbacks. It achieves a data compression ratio of up to 39--107X, almost the same test accuracy of trained models, and high compression speed. Distributed ML frameworks can employ 3LC without modifications to existing ML algorithms. Our experiments show that 3LC reduces wall-clock training time of ResNet-110--based image classifiers for CIFAR-10 on a 10-GPU cluster by up to 16--23X compared to TensorFlow's baseline design.
Investigating Rumor News Using Agreement-Aware Search
Venue: arXiv cs.IR 2018
Year: 2018

Recent years have witnessed a widespread increase of rumor news generated by humans and machines. Therefore, tools for investigating rumor news have become an urgent necessity. One useful function of such tools is to see ways a specific topic or event is represented by presenting different points of view from multiple sources. In this paper, we propose Maester, a novel agreement-aware search framework for investigating rumor news. Given an investigative question, Maester will retrieve related articles to that question, assign and display top articles from agree, disagree, and discuss categories to users. Splitting the results into these three categories provides the user a holistic view towards the investigative question. We build Maester based on the following two key observations: (1) relatedness can commonly be determined by keywords and entities occurring in both questions and articles, and (2) the level of agreement between the investigative question and the related news article can often be decided by a few key sentences. Accordingly, we use gradient boosting tree models with keyword/entity matching features for relatedness detection, and leverage recurrent neural network to infer the level of agreement. Our experiments on the Fake News Challenge (FNC) dataset demonstrate up to an order of magnitude improvement of Maester over the original FNC winning solution, for agreement-aware search.
Conditional Adversarial Synthesis of 3D Facial Action Units
Venue: arXiv cs.CV 2018
Year: 2018

Employing deep learning-based approaches for fine-grained facial expression analysis, such as those involving the estimation of Action Unit (AU) intensities, is difficult due to the lack of a large-scale dataset of real faces with sufficiently diverse AU labels for training. In this paper, we consider how AU-level facial image synthesis can be used to substantially augment such a dataset. We propose an AU synthesis framework that combines the well-known 3D Morphable Model (3DMM), which intrinsically disentangles expression parameters from other face attributes, with models that adversarially generate 3DMM expression parameters conditioned on given target AU labels, in contrast to the more conventional approach of generating facial images directly. In this way, we are able to synthesize new combinations of expression parameters and facial images from desired AU labels. Extensive quantitative and qualitative results on the benchmark DISFA dataset demonstrate the effectiveness of our method on 3DMM facial expression parameter synthesis and data augmentation for deep learning-based AU intensity estimation.
Non-Asymptotic Bounds and a General Formula for the Rate-Distortion Region of the Successive Refinement Problem
Venue: arXiv cs.IT 2018
Year: 2018

In the successive refinement problem, a fixed-length sequence emitted from an information source is encoded into two codewords by two encoders in order to give two reconstructions of the sequence. One of two reconstructions is obtained by one of two codewords, and the other reconstruction is obtained by all two codewords. For this coding problem, we give non-asymptotic inner and outer bounds on pairs of numbers of codewords of two encoders such that each probability that a distortion exceeds a given distortion level is less than a given probability level. We also give a general formula for the rate-distortion region for general sources, where the rate-distortion region is the set of rate pairs of two encoders such that each maximum value of possible distortions is less than a given distortion level.
Emergence of Structured Behaviors from Curiosity-Based Intrinsic Motivation
Venue: arXiv cs.LG 2018
Year: 2018

Infants are experts at playing, with an amazing ability to generate novel structured behaviors in unstructured environments that lack clear extrinsic reward signals. We seek to replicate some of these abilities with a neural network that implements curiosity-driven intrinsic motivation. Using a simple but ecologically naturalistic simulated environment in which the agent can move and interact with objects it sees, the agent learns a world model predicting the dynamic consequences of its actions. Simultaneously, the agent learns to take actions that adversarially challenge the developing world model, pushing the agent to explore novel and informative interactions with its environment. We demonstrate that this policy leads to the self-supervised emergence of a spectrum of complex behaviors, including ego motion prediction, object attention, and object gathering. Moreover, the world model that the agent learns supports improved performance on object dynamics prediction and localization tasks. Our results are a proof-of-principle that computational models of intrinsic motivation might account for key features of developmental visuomotor learning in infants.
A Dual Tableau-based Decision Procedure for a Relational Logic with the Universal Relation (Extended Version)
Venue: arXiv cs.LO 2018
Year: 2018

We present a first result towards the use of entailment in- side relational dual tableau-based decision procedures. To this end, we introduce a fragment of RL(1) which admits a restricted form of composition, (R ; S) or (R ; 1), where the left subterm R of (R ; S) is only allowed to be either the constant 1, or a Boolean term neither containing the complement operator nor the constant 1, while in the case of (R ; 1), R can only be a Boolean term involving relational variables and the operators of intersection and of union. We prove the decidability of the fragment by defining a dual tableau- based decision procedure with a suitable blocking mechanism and where the rules to decompose compositional formulae are modified so to deal with the constant 1 while preserving termination. The fragment properly includes the logics presented in previous work and, therefore, it allows one to express, among others, the multi-modal logic K with union and intersection of accessibility relations, and the description logic ALC with union and intersection of roles.
Modelling Microbial Fuel Cells using lattice Boltzmann methods
Venue: arXiv cs.CE 2018
Year: 2018

An accurate modelling of bio-electrochemical processes that govern Microbial Fuel Cells (MFCs) and mapping their behaviour according to several parameters will enhance the development of MFC technology and enable their successful implementation in well defined applications. The geometry of the electrodes is among key parameters determining efficiency of MFCs due to the formation of a biofilm of anodophilic bacteria on the anode electrode, which is a decisive factor for the functionality of the device. We simulate the bio-electrochemical processes in an MFC while taking into account the geometry of the electrodes. Namely, lattice Boltzmann methods are used to simulate the fluid dynamics and the advection-diffusion phenomena in the anode compartment. The model is verified on voltage and current outputs of a single MFC derived from laboratory experiments under continuous flow.
Stochastic Model Predictive Control of Air Conditioning System for Electric Vehicles: Sensitivity Study, Comparison and Improvement
Venue: arXiv cs.SY 2018
Year: 2018

A stochastic model predictive controller (SMPC) of air conditioning (AC) system is proposed to improve the energy efficiency of electric vehicles (EV). A Markov-chain based velocity predictor is adopted to provide a sense of the future disturbances over the SMPC control horizon. The sensitivity of electrified AC plant to solar radiation, ambient temperature and relative air flow speed is quantificationally analyzed from an energy efficiency perspective. Three control approaches are compared in terms of the electricity consumption, cabin temperature, and comfort fluctuation, which are (i) the proposed SMPC method, (ii) a generally used bang-bang controller and (iii) dynamic programming (DP) as the benchmark. Real solar radiation and ambient temperature data are measured to validate the effectiveness of the SMPC. Comparison results illustrate that SMPC is able to improve the AC energy economy by 12% than rule-based controller. The cabin temperature variation is reduced by over 50.4%, resulting with a much better cabin comfort.
Segmentation of Bleeding Regions in Wireless Capsule Endoscopy Images an Approach for inside Capsule Video Summarization
Venue: arXiv cs.CV 2018
Year: 2018

Wireless capsule endoscopy (WCE) is an effective means of diagnosis of gastrointestinal disorders. Detection of informative scenes by WCE could reduce the length of transmitted videos and can help with the diagnosis. In this paper we propose a simple and efficient method for segmentation of the bleeding regions in WCE captured images. Suitable color channels are selected and classified by a multi-layer perceptron (MLP) structure. The MLP structure is quantized such that the implementation does not require multiplications. The proposed method is tested by simulation on WCE bleeding image dataset. The proposed structure is designed considering hardware resource constrains that exist in WCE systems.
The Signpost Platform for City-Scale Sensing
Venue: arXiv cs.CY 2018
Year: 2018

City-scale sensing holds the promise of enabling a deeper understanding of our urban environments. However, a city-scale deployment requires physical installation, power management, and communications---all challenging tasks standing between a good idea and a realized one. This indicates the need for a platform that enables easy deployment and experimentation for applications operating at city scale. To address these challenges, we present Signpost, a modular, energy-harvesting platform for city-scale sensing. Signpost simplifies deployment by eliminating the need for connection to wired infrastructure and instead harvesting energy from an integrated solar panel. The platform furnishes the key resources necessary to support multiple, pluggable sensor modules while providing fair, safe, and reliable sharing in the face of dynamic energy constraints. We deploy Signpost with several sensor modules, showing the viability of an energy-harvesting, multi-tenant, sensing system, and evaluate its ability to support sensing applications. We believe Signpost reduces the difficulty inherent in city-scale deployments, enables new experimentation, and provides improved insights into urban health.
Formalizing and Implementing Distributed Ledger Objects
Venue: arXiv cs.DC 2018
Year: 2018

Despite the hype about blockchains and distributed ledgers, no formal abstraction of these objects has been proposed. To face this issue, in this paper we provide a proper formulation of a distributed ledger object. In brief, we define a ledger object as a sequence of records, and we provide the operations and the properties that such an object should support. Implementation of a ledger object on top of multiple (possibly geographically dispersed) computing devices gives rise to the distributed ledger object. In contrast to the centralized object, distribution allows operations to be applied concurrently on the ledger, introducing challenges on the consistency of the ledger in each participant. We provide the definitions of three well known consistency guarantees in terms of the operations supported by the ledger object: (1) atomic consistency (linearizability), (2) sequential consistency, and (3) eventual consistency. We then provide implementations of distributed ledgers on asynchronous message passing crash-prone systems using an Atomic Broadcast service, and show that they provide eventual, sequential or atomic consistency semantics. We conclude with a variation of the ledger - the validated ledger - which requires that each record in the ledger satisfies a particular validation rule.
Proper Semirings and Proper Convex Functors
Venue: arXiv cs.LO 2018
Year: 2018

Esik and Maletti introduced the notion of a proper semiring and proved that some important (classes of) semirings -- Noetherian semirings, natural numbers -- are proper. Properness matters as the equivalence problem for weighted automata over a semiring which is proper and finitely and effectively presented is decidable. Milius generalised the notion of properness from a semiring to a functor. As a consequence, a semiring is proper if and only if its associated "cubic functor" is proper. Moreover, properness of a functor renders soundness and completeness proofs for axiomatizations of equivalent behaviour. In this paper we provide a method for proving properness of functors, and instantiate it to cover both the known cases and several novel ones: (1) properness of the semirings of positive rationals and positive reals, via properness of the corresponding cubic functors; and (2) properness of two functors on (positive) convex algebras. The latter functors are important for axiomatizing trace equivalence of probabilistic transition systems. Our proofs rely on results that stretch all the way back to Hilbert and Minkowski.
xView: Objects in Context in Overhead Imagery
Venue: arXiv cs.CV 2018
Year: 2018

We introduce a new large-scale dataset for the advancement of object detection techniques and overhead object detection research. This satellite imagery dataset enables research progress pertaining to four key computer vision frontiers. We utilize a novel process for geospatial category detection and bounding box annotation with three stages of quality control. Our data is collected from WorldView-3 satellites at 0.3m ground sample distance, providing higher resolution imagery than most public satellite imagery datasets. We compare xView to other object detection datasets in both natural and overhead imagery domains and then provide a baseline analysis using the Single Shot MultiBox Detector. xView is one of the largest and most diverse publicly available object-detection datasets to date, with over 1 million objects across 60 classes in over 1,400 km^2 of imagery.
Regional Multi-Armed Bandits
Venue: arXiv cs.LG 2018
Year: 2018

We consider a variant of the classic multi-armed bandit problem where the expected reward of each arm is a function of an unknown parameter. The arms are divided into different groups, each of which has a common parameter. Therefore, when the player selects an arm at each time slot, information of other arms in the same group is also revealed. This regional bandit model naturally bridges the non-informative bandit setting where the player can only learn the chosen arm, and the global bandit model where sampling one arms reveals information of all arms. We propose an efficient algorithm, UCB-g, that solves the regional bandit problem by combining the Upper Confidence Bound (UCB) and greedy principles. Both parameter-dependent and parameter-free regret upper bounds are derived. We also establish a matching lower bound, which proves the order-optimality of UCB-g. Moreover, we propose SW-UCB-g, which is an extension of UCB-g for a non-stationary environment where the parameters slowly vary over time.
Adversarial Learning for Semi-Supervised Semantic Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

We propose a method for semi-supervised semantic segmentation using an adversarial network. While most existing discriminators are trained to classify input images as real or fake on the image level, we design a discriminator in a fully convolutional manner to differentiate the predicted probability maps from the ground truth segmentation distribution with the consideration of the spatial resolution. We show that the proposed discriminator can be used to improve semantic segmentation accuracy by coupling the adversarial loss with the standard cross entropy loss of the proposed model. In addition, the fully convolutional discriminator enables semi-supervised learning through discovering the trustworthy regions in predicted results of unlabeled images, thereby providing additional supervisory signals. In contrast to existing methods that utilize weakly-labeled images, our method leverages unlabeled images to enhance the segmentation model. Experimental results on the PASCAL VOC 2012 and Cityscapes datasets demonstrate the effectiveness of the proposed algorithm.
Actigraphy-based Sleep/Wake Pattern Detection using Convolutional Neural Networks
Venue: arXiv cs.LG 2018
Year: 2018

Common medical conditions are often associated with sleep abnormalities. Patients with medical disorders often suffer from poor sleep quality compared to healthy individuals, which in turn may worsen the symptoms of the disorder. Accurate detection of sleep/wake patterns is important in developing personalized digital markers, which can be used for objective measurements and efficient disease management. Big Data technologies and advanced analytics methods hold the promise to revolutionize clinical research processes, enabling the effective blending of digital data into clinical trials. Actigraphy, a non-invasive activity monitoring method is heavily used to detect and evaluate activities and movement disorders, and assess sleep/wake behavior. In order to study the connection between sleep/wake patterns and a cluster headache disorder, activity data was collected using a wearable device in the course of a clinical trial. This study presents two novel modeling schemes that utilize Deep Convolutional Neural Networks (CNN) to identify sleep/wake states. The proposed methods are a sequential CNN, reminiscent of the bi-directional CNN for slot filling, and a Multi-Task Learning (MTL) based model. Furthermore, we expand standard "Sleep" and "Wake" activity states space by adding the "Falling asleep" and "Siesta" states. We show that the proposed methods provide promising results in accurate detection of the expanded sleep/wake states. Finally, we explore the relations between the detected sleep/wake patterns and onset of cluster headache attacks, and present preliminary observations.