OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Hyperparameter Optimization of Deep Learning Algorithms Using Deterministic RBF Surrogates
Venue: arXiv cs.AI 2017
Year: 2017

Automatically searching for optimal hyperparameter configurations is of crucial importance for applying deep learning algorithms in practice. Recently, Bayesian optimization has been proposed for optimizing hyperparameters of various machine learning algorithms. Those methods adopt probabilistic surrogate models like Gaussian processes to approximate and minimize the validation error function of hyperparameter values. However, probabilistic surrogates require accurate estimates of sufficient statistics (e.g., covariance) of the error distribution and thus need many function evaluations with a sizeable number of hyperparameters. This makes them inefficient for optimizing hyperparameters of deep learning algorithms, which are highly expensive to evaluate. In this work, we propose a new deterministic and efficient hyperparameter optimization method that employs radial basis functions as error surrogates. The proposed mixed integer algorithm, called HORD, searches the surrogate for the most promising hyperparameter values through dynamic coordinate search and requires many fewer function evaluations. HORD does well in low dimensions but it is exceptionally better in higher dimensions. Extensive evaluations on MNIST and CIFAR-10 for four deep neural networks demonstrate HORD significantly outperforms the well-established Bayesian optimization methods such as GP, SMAC, and TPE. For instance, on average, HORD is more than 6 times faster than GP-EI in obtaining the best configuration of 19 hyperparameters.
A Linear Algebraic Approach to Datalog Evaluation
Venue: arXiv cs.AI 2017
Year: 2017

In this paper, we propose a fundamentally new approach to Datalog evaluation. Given a linear Datalog program DB written using N constants and binary predicates, we first translate if-and-only-if completions of clauses in DB into a set Eq(DB) of matrix equations with a non-linear operation where relations in M_DB, the least Herbrand model of DB, are encoded as adjacency matrices. We then translate Eq(DB) into another, but purely linear matrix equations tilde_Eq(DB). It is proved that the least solution of tilde_Eq(DB) in the sense of matrix ordering is converted to the least solution of Eq(DB) and the latter gives M_DB as a set of adjacency matrices. Hence computing the least solution of tilde_Eq(DB) is equivalent to computing M_DB specified by DB. For a class of tail recursive programs and for some other types of programs, our approach achieves O(N^3) time complexity irrespective of the number of variables in a clause since only matrix operations costing O(N^3) or less are used. We conducted two experiments that compute the least Herbrand models of linear Datalog programs. The first experiment computes transitive closure of artificial data and real network data taken from the Koblenz Network Collection. The second one compared the proposed approach with the state-of-the-art symbolic systems including two Prolog systems and two ASP systems, in terms of computation time for a transitive closure program and the same generation program. In the experiment, it is observed that our linear algebraic approach runs 10^1 ~ 10^4 times faster than the symbolic systems when data is not sparse. To appear in Theory and Practice of Logic Programming (TPLP).
Optimization Algorithms for Catching Data Manipulators in Power System Estimation Loops
Venue: arXiv cs.SY 2017
Year: 2017

In this paper we develop a set of algorithms that can detect the identities of malicious data-manipulators in distributed optimization loops for estimating oscillation modes in large power system models. The estimation is posed in terms of a consensus problem among multiple local estimators that jointly solve for the characteristic polynomial of the network model. If any of these local estimates are compromised by a malicious attacker, resulting in an incorrect value of the consensus variable, then the entire estimation loop can be destabilized. We present four iterative algorithms by which this instability can be quickly detected, and the identities of the compromised estimators can be revealed. The algorithms are solely based on the computed values of the estimates, and do not need any information about the model of the power system. Both large and covert attacks are considered. Results are illustrated using simulations of a IEEE 68-bus power system model.
Labeling Topics with Images using Neural Networks
Venue: arXiv cs.CL 2017
Year: 2017

Topics generated by topic models are usually represented by lists of $t$ terms or alternatively using short phrases and images. The current state-of-the-art work on labeling topics using images selects images by re-ranking a small set of candidates for a given topic. In this paper, we present a more generic method that can estimate the degree of association between any arbitrary pair of an unseen topic and image using a deep neural network. Our method has better runtime performance $O(n)$ compared to $O(n^2)$ for the current state-of-the-art method, and is also significantly more accurate.
Server assisted distributed cooperative localization over unreliable communication links
Venue: arXiv cs.RO 2017
Year: 2017

This paper considers the problem of cooperative localization (CL) using inter-robot measurements for a group of networked robots with limited on-board resources. We propose a novel recursive algorithm in which each robot localizes itself in a global coordinate frame by local dead reckoning, and opportunistically corrects its pose estimate whenever it receives a relative measurement update message from a server. The computation and storage cost per robot in terms of the size of the team is of order O(1), and the robots are only required to transmit information when they are involved in a relative measurement. The server also only needs to compute and transmit update messages when it receives an inter-robot measurement. We show that under perfect communication, our algorithm is an alternative but exact implementation of a joint CL for the entire team via Extended Kalman Filter (EKF). The perfect communication however is not a hard requirement. In fact, we show that our algorithm is intrinsically robust with respect to communication failures, with formal guarantees that the updated estimates of the robots receiving the update message are of minimum variance in a first-order approximate sense at that given timestep. We demonstrate the performance of the algorithm in simulation and experiments.
Covert Communication in the Presence of an Uninformed Jammer
Venue: arXiv cs.IT 2017
Year: 2017

Recent work has established that when transmitter Alice wishes to communicate reliably to recipient Bob without detection by warden Willie, with additive white Gaussian noise (AWGN) channels between all parties, communication is limited to $\mathcal{O}(\sqrt{n})$ bits in $n$ channel uses. However, this assumes Willie has an accurate statistical characterization of the channel. When Willie has uncertainty about such and his receiver is limited to a threshold test on the received power, Alice can transmit covertly with a power that does not decrease with $n$, thus conveying $\mathcal{O}(n)$ bits covertly and reliably in $n$ uses of an AWGN channel. Here, we consider covert communication of $\mathcal{O}(n)$ bits in $n$ channel uses while generalizing the environment and removing any restrictions on Willie's receiver. We assume an uninformed "jammer" is present to help Alice, and we consider AWGN and block fading channels. In some scenarios, Willie's optimal detector is a threshold test on the received power. When the channel between the jammer and Willie has multiple fading blocks per codeword, a threshold test on the received power is not optimal. However, we establish that Alice can remain covert with a transmit power that does not decrease with $n$ even when Willie employs an optimal detector.
Smart Contract Templates: foundations, design landscape and research directions
Venue: arXiv cs.CY 2017
Year: 2017

In this position paper, we consider some foundational topics regarding smart contracts (such as terminology, automation, enforceability, and semantics) and define a smart contract as an automatable and enforceable agreement. We explore a simple semantic framework for smart contracts, covering both operational and non-operational aspects, and describe templates and agreements for legally-enforceable smart contracts, based on legal documents. Building upon the Ricardian Contract, we identify operational parameters in the legal documents and use these to connect legal agreements to standardised code. We also explore the design landscape, including increasing sophistication of parameters, increasing use of common standardised code, and long-term research.
Secure Communications in Millimeter Wave Ad Hoc Networks
Venue: arXiv cs.IT 2017
Year: 2017

Wireless networks with directional antennas, like millimeter wave (mmWave) networks, have enhanced security. For a large-scale mmWave ad hoc network in which eavesdroppers are randomly located, however, eavesdroppers can still intercept the confidential messages, since they may reside in the signal beam. This paper explores the potential of physical layer security in mmWave ad hoc networks. Specifically, we characterize the impact of mmWave channel characteristics, random blockages, and antenna gains on the secrecy performance. For the special case of uniform linear array (ULA), a tractable approach is proposed to evaluate the average achievable secrecy rate. We also characterize the impact of artificial noise in such networks. Our results reveal that in the low transmit powerregime, the use of low mmWave frequency achieves better secrecy performance, and when increasing transmit power, a transition from low mmWave frequency to high mmWave frequency is demanded for obtaining a higher secrecy rate. More antennas at the transmitting nodes are needed to decrease the antenna gain obtained by the eavesdroppers when using ULA. Eavesdroppers can intercept more information by using a wide beam pattern. Furthermore, the use of artificial noise may be ineffective for enhancing the secrecy rate.
The real nonnegative inverse eigenvalue problem is NP-hard
Venue: arXiv cs.CC 2017
Year: 2017

A list of complex numbers is realizable if it is the spectrum of a nonnegative matrix. In 1949 Suleimanova posed the nonnegative inverse eigenvalue problem (NIEP): the problem of determining which lists of complex numbers are realizable. The version for reals of the NIEP (RNIEP) asks for realizable lists of real numbers. In the literature there are many sufficient conditions or criteria for lists of real numbers to be realizable. We will present an unified account of these criteria. Then we will see that the decision problem associated to the RNIEP is NP-hard and we will study the complexity for the decision problems associated to known criteria.
Consistent Hashing with Bounded Loads
Venue: arXiv cs.DS 2017
Year: 2017

Designing algorithms for balanced allocation of clients to servers in dynamic settings is a challenging problem for a variety of reasons. Both servers and clients may be added and/or removed from the system periodically, and the main objectives of allocation algorithms are: the uniformity of the allocation, and the number of moves after adding or removing a server or a client. The most popular solution for our dynamic settings is Consistent Hashing. However, the load balancing of consistent hashing is no better than a random assignment of clients to servers, so with $n$ of each, we expect many servers to be overloaded with $Θ(\log n/ \log\log n)$ clients. In this paper, with $n$ clients and $n$ servers, we get a guaranteed max-load of 2 while only moving an expected constant number of clients for each update. We take an arbitrary user specified balancing parameter $c=1+ε>1$. With $m$ balls and $n$ bins in the system, we want no load above $\lceil cm/n\rceil$. Meanwhile we want to bound the expected number of balls that have to be moved when a ball or server is added or removed. Compared with general lower bounds without capacity constraints, we show that in our algorithm when a ball or bin is inserted or deleted, the expected number of balls that have to be moved is increased only by a multiplicative factor $O({1\over ε^2})$ for $ε\le 1$ (Theorem 4) and by a factor $1+O(\frac{\log c}c)$ for $ε\ge 1$ (Theorem 3). Technically, the latter bound is the most challenging to prove. It implies that we for superconstant $c$ only pay a negligible cost in extra moves. We also get the same bounds for the simpler problem where we instead of a user specified balancing parameter have a fixed bin capacity $C$ for all bins.
Pointed computations and Martin-Löf randomness
Venue: arXiv cs.CC 2017
Year: 2017

Schnorr showed that a real is Martin-Loef random if and only if all of its initial segments are incompressible with respect to prefix-free complexity. Fortnow and independently Nies, Stephan and Terwijn noticed that this statement remains true if we can merely require that the initial segments of the real corresponding to a computable increasing sequence of lengths are incompressible. The purpose of this note is to establish the following generalization of this fact. We show that a real is X Martin-Loef random if and only if its initial segments corresponding to a pointedly X-computable sequence (r_n) (where r_n is computable from X in a self-delimiting way, so that at most the first r_n bits of X are queried in the computation) of lengths are incompressible. On the other hand we also show that there are reals which are very far from being Martin-Loef random, yet they compute an increasing sequence of lengths at which their initial segments are incompressible.
HyperLex: A Large-Scale Evaluation of Graded Lexical Entailment
Venue: arXiv cs.CL 2017
Year: 2017

We introduce HyperLex - a dataset and evaluation resource that quantifies the extent of of the semantic category membership, that is, type-of relation also known as hyponymy-hypernymy or lexical entailment (LE) relation between 2,616 concept pairs. Cognitive psychology research has established that typicality and category/class membership are computed in human semantic memory as a gradual rather than binary relation. Nevertheless, most NLP research, and existing large-scale invetories of concept category membership (WordNet, DBPedia, etc.) treat category membership and LE as binary. To address this, we asked hundreds of native English speakers to indicate typicality and strength of category membership between a diverse range of concept pairs on a crowdsourcing platform. Our results confirm that category membership and LE are indeed more gradual than binary. We then compare these human judgements with the predictions of automatic systems, which reveals a huge gap between human performance and state-of-the-art LE, distributional and representation learning models, and substantial differences between the models themselves. We discuss a pathway for improving semantic models to overcome this discrepancy, and indicate future application areas for improved graded LE systems.
Distributed Real-Time Energy Management in Data Center Microgrids
Venue: arXiv cs.DC 2017
Year: 2017

Data center operators are typically faced with three significant problems when running their data centers, i.e., rising electricity bills, growing carbon footprints and unexpected power outages. To mitigate these issues, running data centers in microgrids is a good choice since microgrids can enhance the energy efficiency, sustainability and reliability of electrical services. Thus, in this paper, we investigate the problem of energy management for multiple data center microgrids. Specifically, we intend to minimize the long-term operational cost of data center microgrids by taking into account the uncertainties in electricity prices, renewable outputs and data center workloads. We first formulate a stochastic programming problem with the considerations of many factors, e.g., providing heterogeneous service delay guarantees for batch workloads, interactive workload allocation, batch workload shedding, electricity buying/selling, battery charging/discharging efficiency, and the ramping constraints of backup generators. Then, we design a realtime and distributed algorithm for the formulated problem based on Lyapunov optimization technique and a variant of alternating direction method of multipliers (ADMM). Moreover, the performance guarantees provided by the proposed algorithm are analyzed. Extensive simulation results indicate the effectiveness of the proposed algorithm in operational cost reduction for data center microgrids.
Discriminatively Trained Latent Ordinal Model for Video Classification
Venue: arXiv cs.CV 2017
Year: 2017

We study the problem of video classification for facial analysis and human action recognition. We propose a novel weakly supervised learning method that models the video as a sequence of automatically mined, discriminative sub-events (eg. onset and offset phase for "smile", running and jumping for "highjump"). The proposed model is inspired by the recent works on Multiple Instance Learning and latent SVM/HCRF -- it extends such frameworks to model the ordinal aspect in the videos, approximately. We obtain consistent improvements over relevant competitive baselines on four challenging and publicly available video based facial analysis datasets for prediction of expression, clinical pain and intent in dyadic conversations and on three challenging human action datasets. We also validate the method with qualitative results and show that they largely support the intuitions behind the method.
Multi-task Domain Adaptation for Sequence Tagging
Venue: arXiv cs.CL 2017
Year: 2017

Many domain adaptation approaches rely on learning cross domain shared representations to transfer the knowledge learned in one domain to other domains. Traditional domain adaptation only considers adapting for one task. In this paper, we explore multi-task representation learning under the domain adaptation scenario. We propose a neural network framework that supports domain adaptation for multiple tasks simultaneously, and learns shared representations that better generalize for domain adaptation. We apply the proposed framework to domain adaptation for sequence tagging problems considering two tasks: Chinese word segmentation and named entity recognition. Experiments show that multi-task domain adaptation works better than disjoint domain adaptation for each task, and achieves the state-of-the-art results for both tasks in the social media domain.
Energy Efficient Scheduling of Cloud Application Components with Brownout
Venue: arXiv cs.DC 2017
Year: 2017

It is common for cloud data centers meeting unexpected loads like request bursts, which may lead to overloaded situation and performance degradation. Dynamic Voltage Frequency Scaling and VM consolidation have been proved effective to manage overloads. However, they cannot function when the whole data center is overloaded. Brownout provides a promising direction to avoid overloads through configuring applications to temporarily degrade user experience. Additionally, brownout can also be applied to reduce data center energy consumption. As a complementary option for Dynamic Voltage Frequency Scaling and VM consolidation, our combined brownout approach reduces energy consumption through selectively and dynamically deactivating application optional components, which can also be applied to self-contained microservices. The results show that our approach can save more than 20% energy consumption and there are trade-offs between energy saving and discount offered to users.
Canonical Correlation Inference for Mapping Abstract Scenes to Text
Venue: arXiv cs.CL 2017
Year: 2017

We describe a technique for structured prediction, based on canonical correlation analysis. Our learning algorithm finds two projections for the input and the output spaces that aim at projecting a given input and its correct output into points close to each other. We demonstrate our technique on a language-vision problem, namely the problem of giving a textual description to an "abstract scene".
Residual Networks of Residual Networks: Multilevel Residual Networks
Venue: arXiv cs.CV 2017
Year: 2017

A residual-networks family with hundreds or even thousands of layers dominates major image recognition tasks, but building a network by simply stacking residual blocks inevitably limits its optimization ability. This paper proposes a novel residual-network architecture, Residual networks of Residual networks (RoR), to dig the optimization ability of residual networks. RoR substitutes optimizing residual mapping of residual mapping for optimizing original residual mapping. In particular, RoR adds level-wise shortcut connections upon original residual networks to promote the learning capability of residual networks. More importantly, RoR can be applied to various kinds of residual networks (ResNets, Pre-ResNets and WRN) and significantly boost their performance. Our experiments demonstrate the effectiveness and versatility of RoR, where it achieves the best performance in all residual-network-like structures. Our RoR-3-WRN58-4+SD models achieve new state-of-the-art results on CIFAR-10, CIFAR-100 and SVHN, with test errors 3.77%, 19.73% and 1.59%, respectively. RoR-3 models also achieve state-of-the-art results compared to ResNets on ImageNet data set.
Approximation algorithms for the maximum weight internal spanning tree problem
Venue: arXiv cs.DS 2017
Year: 2017

Given a vertex-weighted connected graph $G = (V, E)$, the maximum weight internal spanning tree (MwIST for short) problem asks for a spanning tree $T$ of $G$ such that the total weight of the internal vertices in $T$ is maximized. The un-weighted variant, denoted as MIST, is NP-hard and APX-hard, and the currently best approximation algorithm has a proven performance ratio $13/17$. The currently best approximation algorithm for MwIST only has a performance ratio $1/3 - ε$, for any $ε> 0$. In this paper, we present a simple algorithm based on a novel relationship between MwIST and the maximum weight matching, and show that it achieves a better approximation ratio of $1/2$. When restricted to claw-free graphs, a special case been previously studied, we design a $7/12$-approximation algorithm.
Recurrent Neural Networks to Correct Satellite Image Classification Maps
Venue: arXiv cs.CV 2017
Year: 2017

While initially devised for image categorization, convolutional neural networks (CNNs) are being increasingly used for the pixelwise semantic labeling of images. However, the proper nature of the most common CNN architectures makes them good at recognizing but poor at localizing objects precisely. This problem is magnified in the context of aerial and satellite image labeling, where a spatially fine object outlining is of paramount importance. Different iterative enhancement algorithms have been presented in the literature to progressively improve the coarse CNN outputs, seeking to sharpen object boundaries around real image edges. However, one must carefully design, choose and tune such algorithms. Instead, our goal is to directly learn the iterative process itself. For this, we formulate a generic iterative enhancement process inspired from partial differential equations, and observe that it can be expressed as a recurrent neural network (RNN). Consequently, we train such a network from manually labeled data for our enhancement task. In a series of experiments we show that our RNN effectively learns an iterative process that significantly improves the quality of satellite image classification maps.