OpenRaiser/Intern-Atlas huggingface dataset:
Persuasive Technology in Reducing Prolonged Sedentary Behavior at Work: A Systematic Review
Venue: arXiv cs.CY 2018
Year: 2018

Prolonged sedentary behavior is prevalent among office workers and has been found to be detrimental to health. Preventing and reducing prolonged sedentary behavior require interventions, and persuasive technology is expected to make a contribution in this domain. In this paper, we use the framework of persuasive system design (PSD) principles to investigate the utilization and effectiveness of persuasive technology in intervention studies at reducing sedentary behavior at work. This systematic review reveals that reminders are the most frequently used PSD principle. The analysis on reminders shows that hourly PC reminders alone have no significant effect on reducing sedentary behavior at work, while coupling with education or other informative session seems to be promising. Details of deployed persuasive technology with behavioral theories and user experience evaluation are expected to be reported explicitly in the future intervention studies.
Consistent Multiple Graph Matching with Multi-layer Random Walks Synchronization
Venue: arXiv cs.CV 2018
Year: 2018

We address the correspondence search problem among multiple graphs with complex properties while considering the matching consistency. We describe each pair of graphs by combining multiple attributes, then jointly match them in a unified framework. The main contribution of this paper is twofold. First, we formulate the global correspondence search problem of multi-attributed graphs by utilizing a set of multi-layer structures. The proposed formulation describes each pair of graphs as a multi-layer structure, and jointly considers whole matching pairs. Second, we propose a robust multiple graph matching method based on the multi-layer random walks framework. The proposed framework synchronizes movements of random walkers, and leads them to consistent matching candidates. In our extensive experiments, the proposed method exhibits robust and accurate performance over the state-of-the-art multiple graph matching algorithms.
Effective Neural Solution for Multi-Criteria Word Segmentation
Venue: arXiv cs.CL 2018
Year: 2018

We present a simple yet elegant solution to train a single joint model on multi-criteria corpora for Chinese Word Segmentation (CWS). Our novel design requires no private layers in model architecture, instead, introduces two artificial tokens at the beginning and ending of input sentence to specify the required target criteria. The rest of the model including Long Short-Term Memory (LSTM) layer and Conditional Random Fields (CRFs) layer remains unchanged and is shared across all datasets, keeping the size of parameter collection minimal and constant. On Bakeoff 2005 and Bakeoff 2008 datasets, our innovative design has surpassed both single-criterion and multi-criteria state-of-the-art learning results. To the best knowledge, our design is the first one that has achieved the latest high performance on such large scale datasets. Source codes and corpora of this paper are available on GitHub.
The Complexity of Maximum $k$-Order Bounded Component Set Problem
Venue: arXiv cs.DS 2018
Year: 2018

Given a graph $G=(V, E)$ and a positive integer $k$, in Maximum $k$-Order Bounded Component Set (Max-$k$-OBCS), it is required to find a vertex set $S \subseteq V$ of maximum size such that each component in the induced graph $G[S]$ has at most $k$ vertices. We prove that for constant $k$, Max-$k$-OBCS is hard to approximate within a factor of $n^{1 -ε}$, for any $ε> 0$, unless $\mathsf{P} = \mathsf{NP}$. This is an improvement on the previous lower bound of $\sqrt{n}$ for Max-2-OBCS due to Orlovich et al. We provide lower bounds on the approximability when $k$ is not a constant as well. Max-$k$-OBCS can be seen as a generalization of Maximum Independent Set (Max-IS). We generalize Turán's greedy algorithm for Max-IS and prove that it approximates Max-$k$-OBCS within a factor of $(2k - 1)\overline{d} + k$, where $\overline{d}$ is the average degree of the input graph $G$. This approximation factor is a generalization of Turán's approximation factor for Max-IS.
Multi-Scale Video Frame-Synthesis Network with Transitive Consistency Loss
Venue: arXiv cs.CV 2018
Year: 2018

Traditional approaches to interpolate/extrapolate frames in a video sequence require accurate pixel correspondences between images, e.g., using optical flow. Their results stem on the accuracy of optical flow estimation, and could generate heavy artifacts when flow estimation failed. Recently methods using auto-encoder has shown impressive progress, however they are usually trained for specific interpolation/extrapolation settings and lack of flexibility and In order to reduce these limitations, we propose a unified network to parameterize the interest frame position and therefore infer interpolate/extrapolate frames within the same framework. To achieve this, we introduce a transitive consistency loss to better regularize the network. We adopt a multi-scale structure for the network so that the parameters can be shared across multi-layers. Our approach avoids expensive global optimization of optical flow methods, and is efficient and flexible for video interpolation/extrapolation applications. Experimental results have shown that our method performs favorably against state-of-the-art methods.
Caching and Coded Delivery over Gaussian Broadcast Channels for Energy Efficiency
Venue: arXiv cs.IT 2018
Year: 2018

A cache-aided $K$-user Gaussian broadcast channel (BC) is considered. The transmitter has a library of $N$ equal-rate files, from which each user demands one. The impact of the equal-capacity receiver cache memories on the minimum required transmit power to satisfy all user demands is studied. Considering uniformly random demands across the library, both the minimum average power (averaged over all demand combinations) and the minimum peak power (minimum power required to satisfy all demand combinations) are studied. Upper bounds are presented on the minimum required average and peak transmit power as a function of the cache capacity considering both centralized and decentralized caching. The lower bounds on the minimum required average and peak power values are also derived assuming uncoded cache placement. The bounds for both the peak and average power values are shown to be tight in the centralized scenario through numerical simulations. The results in this paper show that proactive caching and coded delivery can provide significant energy savings in wireless networks.
Infinite and Bi-infinite Words with Decidable Monadic Theories
Venue: arXiv cs.LO 2018
Year: 2018

We study word structures of the form $(D,<,P)$ where $D$ is either $\mathbb{N}$ or $\mathbb{Z}$, $<$ is the natural linear ordering on $D$ and $P\subseteq D$ is a predicate on $D$. In particular we show: (a) The set of recursive $ω$-words with decidable monadic second order theories is $Σ_3$-complete. (b) Known characterisations of the $ω$-words with decidable monadic second order theories are transfered to the corresponding question for bi-infinite words. (c) We show that such "tame" predicates $P$ exist in every Turing degree. (d) We determine, for $P\subseteq\mathbb{Z}$, the number of predicates $Q\subseteq\mathbb{Z}$ such that $(\mathbb{Z},\le,P)$ and $(\mathbb{Z},\le,Q)$ are indistinguishable. Through these results we demonstrate similarities and differences between logical properties of infinite and bi-infinite words.
Distributed Bayesian Filtering using Logarithmic Opinion Pool for Dynamic Sensor Networks
Venue: arXiv cs.SY 2018
Year: 2018

The discrete-time Distributed Bayesian Filtering (DBF) algorithm is presented for the problem of tracking a target dynamic model using a time-varying network of heterogeneous sensing agents. In the DBF algorithm, the sensing agents combine their normalized likelihood functions in a distributed manner using the logarithmic opinion pool and the dynamic average consensus algorithm. We show that each agent's estimated likelihood function globally exponentially converges to an error ball centered on the joint likelihood function of the centralized multi-sensor Bayesian filtering algorithm. We rigorously characterize the convergence, stability, and robustness properties of the DBF algorithm. Moreover, we provide an explicit bound on the time step size of the DBF algorithm that depends on the time-scale of the target dynamics, the desired convergence error bound, and the modeling and communication error bounds. Furthermore, the DBF algorithm for linear-Gaussian models is cast into a modified form of the Kalman information filter. The performance and robust properties of the DBF algorithm are validated using numerical simulations.
Toward `verifying' a Water Treatment System
Venue: arXiv cs.AI 2018
Year: 2018

Modeling and verifying real-world cyber-physical systems is challenging, which is especially so for complex systems where manually modeling is infeasible. In this work, we report our experience on combining model learning and abstraction refinement to analyze a challenging system, i.e., a real-world Secure Water Treatment system (SWaT). Given a set of safety requirements, the objective is to either show that the system is safe with a high probability (so that a system shutdown is rarely triggered due to safety violation) or not. As the system is too complicated to be manually modeled, we apply latest automatic model learning techniques to construct a set of Markov chains through abstraction and refinement, based on two long system execution logs (one for training and the other for testing). For each probabilistic safety property, we either report it does not hold with a certain level of probabilistic confidence, or report that it holds by showing the evidence in the form of an abstract Markov chain. The Markov chains can subsequently be implemented as runtime monitors in SWaT.
Deep Learning for IoT Big Data and Streaming Analytics: A Survey
Venue: arXiv cs.NI 2018
Year: 2018

In the era of the Internet of Things (IoT), an enormous amount of sensing devices collect and/or generate various sensory data over time for a wide range of fields and applications. Based on the nature of the application, these devices will result in big or fast/real-time data streams. Applying analytics over such data streams to discover new information, predict future insights, and make control decisions is a crucial process that makes IoT a worthy paradigm for businesses and a quality-of-life improving technology. In this paper, we provide a thorough overview on using a class of advanced machine learning techniques, namely Deep Learning (DL), to facilitate the analytics and learning in the IoT domain. We start by articulating IoT data characteristics and identifying two major treatments for IoT data from a machine learning perspective, namely IoT big data analytics and IoT streaming data analytics. We also discuss why DL is a promising approach to achieve the desired analytics in these types of data and applications. The potential of using emerging DL techniques for IoT data analytics are then discussed, and its promises and challenges are introduced. We present a comprehensive background on different DL architectures and algorithms. We also analyze and summarize major reported research attempts that leveraged DL in the IoT domain. The smart IoT devices that have incorporated DL in their intelligence background are also discussed. DL implementation approaches on the fog and cloud centers in support of IoT applications are also surveyed. Finally, we shed light on some challenges and potential directions for future research. At the end of each section, we highlight the lessons learned based on our experiments and review of the recent literature.
Differentiable lower bound for expected BLEU score
Venue: arXiv cs.CL 2018
Year: 2018

In natural language processing tasks performance of the models is often measured with some non-differentiable metric, such as BLEU score. To use efficient gradient-based methods for optimization, it is a common workaround to optimize some surrogate loss function. This approach is effective if optimization of such loss also results in improving target metric. The corresponding problem is referred to as loss-evaluation mismatch. In the present work we propose a method for calculation of differentiable lower bound of expected BLEU score that does not involve computationally expensive sampling procedure such as the one required when using REINFORCE rule from reinforcement learning (RL) framework.
Decomposing the Univalence Axiom
Venue: arXiv cs.LO 2018
Year: 2018

This paper investigates Voevodsky's univalence axiom in intensional Martin-Löf type theory. In particular, it looks at how univalence can be derived from simpler axioms. We first present some existing work, collected together from various published and unpublished sources; we then present a new decomposition of the univalence axiom into simpler axioms. We argue that these axioms are easier to verify in certain potential models of univalent type theory, particularly those models based on cubical sets. Finally we show how this decomposition is relevant to an open problem in type theory.
An Improved Feedback Coding Scheme for the Wire-tap Channel
Venue: arXiv cs.IT 2018
Year: 2018

The model of wiretap channel (WTC) is important as it constitutes the essence of physical layer security (PLS). Wiretap channel with noiseless feedback (WTC-NF) is especially interesting as it shows what can be done when a private feedback is available. The already existing secret key based feedback coding scheme focuses on generating key from the feedback and using this key to protect part of the transmitted message. It has been shown that this secret key based feedback coding scheme is only optimal for the degraded WTC-NF, and finding an optimal feedback scheme for the general WTC-NF motivates us to exploit other uses of the feedback. In this paper, a new feedback coding scheme for the general WTC-NF is proposed, where the feedback is not only used to generate key, but also used to generate help information which helps the legitimate parties to improve the communication between them. We show that the proposed new feedback scheme performs better than the already existing one, and a binary example is given to further explain the results of this paper.
Evolving Unsupervised Deep Neural Networks for Learning Meaningful Representations
Venue: arXiv cs.NE 2018
Year: 2018

Deep Learning (DL) aims at learning the \emph{meaningful representations}. A meaningful representation refers to the one that gives rise to significant performance improvement of associated Machine Learning (ML) tasks by replacing the raw data as the input. However, optimal architecture design and model parameter estimation in DL algorithms are widely considered to be intractable. Evolutionary algorithms are much preferable for complex and non-convex problems due to its inherent characteristics of gradient-free and insensitivity to local optimum. In this paper, we propose a computationally economical algorithm for evolving \emph{unsupervised deep neural networks} to efficiently learn \emph{meaningful representations}, which is very suitable in the current Big Data era where sufficient labeled data for training is often expensive to acquire. In the proposed algorithm, finding an appropriate architecture and the initialized parameter values for a ML task at hand is modeled by one computational efficient gene encoding approach, which is employed to effectively model the task with a large number of parameters. In addition, a local search strategy is incorporated to facilitate the exploitation search for further improving the performance. Furthermore, a small proportion labeled data is utilized during evolution search to guarantee the learnt representations to be meaningful. The performance of the proposed algorithm has been thoroughly investigated over classification tasks. Specifically, error classification rate on MNIST with $1.15\%$ is reached by the proposed algorithm consistently, which is a very promising result against state-of-the-art unsupervised DL algorithms.
The Sound and the Fury: Hiding Communications in Noisy Wireless Networks with Interference Uncertainty
Venue: arXiv cs.IT 2018
Year: 2018

Covert communication can prevent the adversary from knowing that a wireless transmission has occurred. In the additive white Gaussian noise channels, a square root law is obtained and the result shows that Alice can reliably and covertly transmit $\mathcal{O}(\sqrt{n})$ bits to Bob in $n$ channel uses. If additional "friendly" node near the adversary can inject artificial noise to aid Alice in hiding her transmission attempt, covert throughput can be improved, i.e., Alice can covertly transmit $\mathcal{O}(\min\{n,λ^{α/2}\sqrt{n}\})$ bits to Bob over $n$ uses of the channel ($λ$ is the density of friendly nodes and $α$ is the path loss exponent of wireless channels). In this paper, we consider the covert communication in a noisy wireless network, where Bob and the adversary Willie not only experience the background noise, but also the aggregated interference from other transmitters. Our results show that uncertainty in interference experienced by Willie is beneficial to Alice. When the distance between Alice and Willie $d_{a,w}=ω(n^{δ/4})$ ($δ=2/α$ is stability exponent), Alice can reliably and covertly transmit $\mathcal{O}(\log_2\sqrt{n})$ bits to Bob in $n$ channel uses. Although the covert throughput is lower than the square root law and the friendly jamming scheme, the spatial throughput is higher. From the network perspective, the communications are hidden in "the sound and the fury" of noisy wireless networks, and what Willie sees is merely a "shadow" wireless network. He knows for certain that some nodes are transmitting, but he cannot catch anyone red-handed.
A Hierarchical Recurrent Neural Network for Symbolic Melody Generation
Venue: arXiv cs.SD 2018
Year: 2018

In recent years, neural networks have been used to generate symbolic melodies. However, the long-term structure in the melody has posed great difficulty for designing a good model. In this paper, we present a hierarchical recurrent neural network for melody generation, which consists of three Long-Short-Term-Memory (LSTM) subnetworks working in a coarse-to-fine manner along time. Specifically, the three subnetworks generate bar profiles, beat profiles and notes in turn, and the output of the high-level subnetworks are fed into the low-level subnetworks, serving as guidance for generating the finer time-scale melody components in low-level subnetworks. Two human behavior experiments demonstrate the advantage of this structure over the single-layer LSTM which attempts to learn all hidden structures in melodies. Compared with the state-of-the-art models MidiNet and MusicVAE, the hierarchical recurrent neural network produces better melodies evaluated by humans.
Monotonic Chunkwise Attention
Venue: arXiv cs.CL 2018
Year: 2018

Sequence-to-sequence models with soft attention have been successfully applied to a wide variety of problems, but their decoding process incurs a quadratic time and space cost and is inapplicable to real-time sequence transduction. To address these issues, we propose Monotonic Chunkwise Attention (MoChA), which adaptively splits the input sequence into small chunks over which soft attention is computed. We show that models utilizing MoChA can be trained efficiently with standard backpropagation while allowing online and linear-time decoding at test time. When applied to online speech recognition, we obtain state-of-the-art results and match the performance of a model using an offline soft attention mechanism. In document summarization experiments where we do not expect monotonic alignments, we show significantly improved performance compared to a baseline monotonic attention-based model.
What Can This Robot Do? Learning from Appearance and Experiments
Venue: arXiv cs.AI 2018
Year: 2018

When presented with an unknown robot (subject) how can an autonomous agent (learner) figure out what this new robot can do? The subject's appearance can provide cues to its physical as well as cognitive capabilities. Seeing a humanoid can make one wonder if it can kick balls, climb stairs or recognize faces. What if the learner can request the subject to perform these tasks? We present an approach to make the learner build a model of the subject at a task based on the latter's appearance and refine it by experimentation. Apart from the subject's inherent capabilities, certain extrinsic factors may affect its performance at a task. Based on the subject's appearance and prior knowledge about the task a learner can identify a set of potential factors, a subset of which we assume are controllable. Our approach picks values of controllable factors to generate the most informative experiments to test the subject at. Additionally, we present a metric to determine if a factor should be incorporated in the model. We present results of our approach on modeling a humanoid robot at the task of kicking a ball. Firstly, we show that actively picking values for controllable factors, even in noisy experiments, leads to faster learning of the subject's model for the task. Secondly, starting from a minimal set of factors our metric identifies the set of relevant factors to incorporate in the model. Lastly, we show that the refined model better represents the subject's performance at the task.
Enhancing the performance of a safe controller via supervised learning for truck lateral control
Venue: arXiv cs.SY 2018
Year: 2018

Correct-by-construction techniques, such as control barrier functions (CBFs), can be used to guarantee closed-loop safety by acting as a supervisor of an existing or legacy controller. However, supervisory-control intervention typically compromises the performance of the closed-loop system. On the other hand, machine learning has been used to synthesize controllers that inherit good properties from a training dataset, though safety is typically not guaranteed due to the difficulty of analyzing the associated neural network. In this paper, supervised learning is combined with CBFs to synthesize controllers that enjoy good performance with provable safety. A training set is generated by trajectory optimization that incorporates the CBF constraint for an interesting range of initial conditions of the truck model. A control policy is obtained via supervised learning that maps a feature representing the initial conditions to a parameterized desired trajectory. The learning-based controller is used as the performance controller and a CBF-based supervisory controller guarantees safety. A case study of lane keeping for articulated trucks shows that the controller trained by supervised learning inherits the good performance of the training set and rarely requires intervention by the CBF supervisor
The exploding gradient problem demystified - definition, prevalence, impact, origin, tradeoffs, and solutions
Venue: arXiv cs.LG 2018
Year: 2018

Whereas it is believed that techniques such as Adam, batch normalization and, more recently, SeLU nonlinearities "solve" the exploding gradient problem, we show that this is not the case in general and that in a range of popular MLP architectures, exploding gradients exist and that they limit the depth to which networks can be effectively trained, both in theory and in practice. We explain why exploding gradients occur and highlight the *collapsing domain problem*, which can arise in architectures that avoid exploding gradients. ResNets have significantly lower gradients and thus can circumvent the exploding gradient problem, enabling the effective training of much deeper networks. We show this is a direct consequence of the Pythagorean equation. By noticing that *any neural network is a residual network*, we devise the *residual trick*, which reveals that introducing skip connections simplifies the network mathematically, and that this simplicity may be the major cause for their success.