cicyt UNIZAR

Computer Science

New submissions

[ total of 227 entries: 1-227 ]
[ showing up to 2000 entries per page: fewer | more ]

New submissions for Fri, 23 Feb 18

[1]  arXiv:1802.07740 [pdf, other]
Title: Machine Theory of Mind
Comments: 21 pages, 15 figures
Subjects: Artificial Intelligence (cs.AI)

Theory of mind (ToM; Premack & Woodruff, 1978) broadly refers to humans' ability to represent the mental states of others, including their desires, beliefs, and intentions. We propose to train a machine to build such models too. We design a Theory of Mind neural network -- a ToMnet -- which uses meta-learning to build models of the agents it encounters, from observations of their behaviour alone. Through this process, it acquires a strong prior model for agents' behaviour, as well as the ability to bootstrap to richer predictions about agents' characteristics and mental states using only a small number of behavioural observations. We apply the ToMnet to agents behaving in simple gridworld environments, showing that it learns to model random, algorithmic, and deep reinforcement learning agents from varied populations, and that it passes classic ToM tasks such as the "Sally-Anne" test (Wimmer & Perner, 1983; Baron-Cohen et al., 1985) of recognising that others can hold false beliefs about the world. We argue that this system -- which autonomously learns how to model other agents in its world -- is an important step forward for developing multi-agent AI systems, for building intermediating technology for machine-human interaction, and for advancing the progress on interpretable AI.

[2]  arXiv:1802.07769 [pdf]
Title: Lossless Compression of Angiogram Foreground with Visual Quality Preservation of Background
Comments: 4 pages , 7 figures
Subjects: Computer Vision and Pattern Recognition (cs.CV)

By increasing the volume of telemedicine information, the need for medical image compression has become more important. In angiographic images, a small ratio of the entire image usually belongs to the vasculature that provides crucial information for diagnosis. Other parts of the image are diagnostically less important and can be compressed with higher compression ratio. However, the quality of those parts affect the visual perception of the image as well. Existing methods compress foreground and background of angiographic images using different techniques. In this paper we first utilize convolutional neural network to segment vessels and then represent a hierarchical block processing algorithm capable of both eliminating the background redundancies and preserving the overall visual quality of angiograms.

[3]  arXiv:1802.07770 [pdf, other]
Title: Generalizable Adversarial Examples Detection Based on Bi-model Decision Mismatch
Subjects: Computer Vision and Pattern Recognition (cs.CV)

Deep neural networks (DNNs) have shown phenomenal success in a wide range of applications. However, recent studies have discovered that they are vulnerable to Adversarial Examples, i.e., original samples with added subtle perturbations. Such perturbations are often too small and imperceptible to humans, yet they can easily fool the neural networks. Few defense techniques against adversarial examples have been proposed, but they require modifying the target model or prior knowledge of adversarial examples generation methods. Likewise, their performance remarkably drops upon encountering adversarial example types not used during the training stage. In this paper, we propose a new framework that can be used to enhance DNNs' robustness by detecting adversarial examples. In particular, we employ the decision layer of independently trained models as features for posterior detection. The proposed framework doesn't require any prior knowledge of adversarial examples generation techniques, and can be directly augmented with unmodified off-the-shelf models. Experiments on the standard MNIST and CIFAR10 datasets show that it generalizes well across not only different adversarial examples generation methods but also various additive perturbations. Specifically, distinct binary classifiers trained on top of our proposed features can achieve a high detection rate (>90%) in a set of white-box attacks and maintain this performance when tested against unseen attacks.

[4]  arXiv:1802.07778 [pdf]
Title: Left Ventricle Segmentation in Cardiac MR Images Using Fully Convolutional Network
Comments: 4 pages, 3 figures
Subjects: Computer Vision and Pattern Recognition (cs.CV)

Medical image analysis, especially segmenting a specific organ, has an important role in developing clinical decision support systems. In cardiac magnetic resonance (MR) imaging, segmenting the left and right ventricles helps physicians diagnose different heart abnormalities. There are challenges for this task, including the intensity and shape similarity between left ventricle and other organs, inaccurate boundaries and presence of noise in most of the images. In this paper we propose an automated method for segmenting the left ventricle in cardiac MR images. We first automatically extract the region of interest, and then employ it as an input of a fully convolutional network. We train the network accurately despite the small number of left ventricle pixels in comparison with the whole image. Thresholding on the output map of the fully convolutional network and selection of regions based on their roundness are performed in our proposed post-processing phase. The Dice score of our method reaches 87.24% by applying this algorithm on the York dataset of heart images.

[5]  arXiv:1802.07779 [pdf, other]
Title: Path-Based Function Embedding and its Application to Specification Mining
Comments: 11 pages, 8 figures
Subjects: Software Engineering (cs.SE)

Relationships among program elements is useful for program understanding, debugging, and analysis. One such kind of relationship is synonymous functions. Function synonyms are functions that play a similar role in code; examples include functions that perform initialization for different device drivers, and functions that implement different symmetric-key encryption schemes. Function synonyms are not necessarily semantically equivalent and can be syntactically dissimilar; consequently, approaches for identifying code clones or functional equivalence cannot be used to identify them. This paper presents func2vec, an algorithm that maps each function to a vector in a vector space such that function synonyms are grouped together. We compute the function embedding by training a neural network using sentences generated using random walks of the interprocedural control-flow graph. We show the effectiveness of func2vec in identifying function synonyms in the Linux kernel. Furthermore, we show how knowing function synonyms enables mining error-handling specifications with high support in Linux file systems and drivers.

[6]  arXiv:1802.07781 [pdf]
Title: Lossless Image Compression Algorithm for Wireless Capsule Endoscopy by Content-Based Classification of Image Blocks
Comments: 4 pages, 5 figures
Subjects: Computer Vision and Pattern Recognition (cs.CV)

Recent advances in capsule endoscopy systems have introduced new methods and capabilities. The capsule endoscopy system, by observing the entire digestive tract, has significantly improved diagnosing gastrointestinal disorders and diseases. The system has challenges such as the need to enhance the quality of the transmitted images, low frame rates of transmission, and battery lifetime that need to be addressed. One of the important parts of a capsule endoscopy system is the image compression unit. Better compression of images increases the frame rate and hence improves the diagnosis process. In this paper a high precision compression algorithm with high compression ratio is proposed. In this algorithm we use the similarity between frames to compress the data more efficiently.

[7]  arXiv:1802.07782 [pdf]
Title: Artificial Intelligence and Legal Liability
Authors: John Kingston
Comments: In: Bramer, Max and Petridis, Miltiadis, eds. Research and Development in Intelligent Systems XXXIII: Incorporating Applications and Innovations in Intelligent Systems XXIV. Springer Verlag, Cambridge, UK, pp. 269-279. ISBN 9783319471747
Subjects: Artificial Intelligence (cs.AI); Computers and Society (cs.CY)

A recent issue of a popular computing journal asked which laws would apply if a self-driving car killed a pedestrian. This paper considers the question of legal liability for artificially intelligent computer systems. It discusses whether criminal liability could ever apply; to whom it might apply; and, under civil law, whether an AI program is a product that is subject to product design legislation or a service to which the tort of negligence applies. The issue of sales warranties is also considered. A discussion of some of the practical limitations that AI systems are subject to is also included.

[8]  arXiv:1802.07786 [pdf]
Title: Reversible Image Watermarking for Health Informatics Systems Using Distortion Compensation in Wavelet Domain
Comments: 4 pages, 5 figures
Subjects: Computer Vision and Pattern Recognition (cs.CV)

Reversible image watermarking guaranties restoration of both original cover and watermark logo from the watermarked image. Capacity and distortion of the image under reversible watermarking are two important parameters. In this study a reversible watermarking is investigated with focusing on increasing the embedding capacity and reducing the distortion in medical images. Integer wavelet transform is used for embedding where in each iteration, one watermark bit is embedded in one transform coefficient. We devise a novel approach that when a coefficient is modified in an iteration, the produced distortion is compensated in the next iteration. This distortion compensation method would result in low distortion rate. The proposed method is tested on four types of medical images including MRI of brain, cardiac MRI, MRI of breast, and intestinal polyp images. Using a one-level wavelet transform, maximum capacity of 1.5 BPP is obtained. Experimental results demonstrate that the proposed method is superior to the state-of-the-art works in terms of capacity and distortion.

[9]  arXiv:1802.07788 [pdf]
Title: Segmentation of Bleeding Regions in Wireless Capsule Endoscopy Images an Approach for inside Capsule Video Summarization
Comments: 4 pages, 3 figures
Subjects: Computer Vision and Pattern Recognition (cs.CV)

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.

[10]  arXiv:1802.07789 [pdf, other]
Title: Semantic Segmentation Refinement by Monte Carlo Region Growing of High Confidence Detections
Subjects: Computer Vision and Pattern Recognition (cs.CV)

Despite recent improvements using fully convolutional networks, in general, the segmentation produced by most state-of-the-art semantic segmentation methods does not show satisfactory adherence to the object boundaries. We propose a method to refine the segmentation results generated by such deep learning models. Our method takes as input the confidence scores generated by a pixel-dense segmentation network and re-labels pixels with low confidence levels. The re-labeling approach employs a region growing mechanism that aggregates these pixels to neighboring areas with high confidence scores and similar appearance. In order to correct the labels of pixels that were incorrectly classified with high confidence level by the semantic segmentation algorithm, we generate multiple region growing steps through a Monte Carlo sampling of the seeds of the regions. Our method improves the accuracy of a state-of-the-art fully convolutional semantic segmentation approach on the publicly available COCO and PASCAL datasets, and it shows significantly better results on selected sequences of the finely-annotated DAVIS dataset.

[11]  arXiv:1802.07793 [pdf, ps, other]
Title: Optimal Multi-User Scheduling of Buffer-Aided Relay Systems
Comments: Accepted by IEEE ICC 2018, Kansas City,USA
Subjects: Information Theory (cs.IT)

Multi-User scheduling is a challenging problem under the relaying scenarios. Traditional schemes, which are based on the instantaneous signal-to-interference-plus-noises ratios (SINRs), cannot solve the inherent disparities of the qualities between different links. Hence, the system performance is always limited by the weaker links. In this paper, from the whole system throughput view, we propose an optimal multi-user scheduling scheme for the multi-user full-duplex (FD) buffer aided relay systems. We first formulate the throughput maximization problem. Then, according to the characteristics of the Karush-Kuhn-Tucker conditions, we obtain the optimal decision functions and the optimal weighted factors of different links of the proposed scheme. Simulation results show that the proposed scheme not only solves the disparities of the qualities between $S_i$-$R$ and $R$-$D_i$ links, but also that between different $S_{i}$-$R$ or $D_{i}$-$R$ links, which can be used as guidance in the design of the practical systems.

[12]  arXiv:1802.07794 [pdf]
Title: Liver Segmentation in Abdominal CT Images by Adaptive 3D Region Growing
Comments: 5 pages, 3 figures, 1 table
Subjects: Computer Vision and Pattern Recognition (cs.CV)

Automatic liver segmentation plays an important role in computer-aided diagnosis and treatment. Manual segmentation of organs is a difficult and tedious task and so prone to human errors. In this paper, we propose an adaptive 3D region growing with subject-specific conditions. For this aim we use the intensity distribution of most probable voxels in prior map along with location prior. We also incorporate the boundary of target organs to restrict the region growing. In order to obtain strong edges and high contrast, we propose an effective contrast enhancement algorithm to facilitate more accurate segmentation. In this paper, 92.56% Dice score is achieved. We compare our method with the method of hard thresholding on Deeds prior map and also with the majority voting on Deeds registration with 13 organs.

[13]  arXiv:1802.07796 [pdf, other]
Title: Continuous Relaxation of MAP Inference: A Nonconvex Perspective
Comments: Accepted for publication at the 2018 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
Subjects: Computer Vision and Pattern Recognition (cs.CV); Learning (cs.LG); Machine Learning (stat.ML)

In this paper, we study a nonconvex continuous relaxation of MAP inference in discrete Markov random fields (MRFs). We show that for arbitrary MRFs, this relaxation is tight, and a discrete stationary point of it can be easily reached by a simple block coordinate descent algorithm. In addition, we study the resolution of this relaxation using popular gradient methods, and further propose a more effective solution using a multilinear decomposition framework based on the alternating direction method of multipliers (ADMM). Experiments on many real-world problems demonstrate that the proposed ADMM significantly outperforms other nonconvex relaxation based methods, and compares favorably with state of the art MRF optimization algorithms in different settings.

[14]  arXiv:1802.07800 [pdf]
Title: Liver segmentation in CT images using three dimensional to two dimensional fully connected network
Comments: 5 pages, 2 figures
Subjects: Computer Vision and Pattern Recognition (cs.CV)

The need for CT scan analysis is growing for pre-diagnosis and therapy of abdominal organs. Automatic organ segmentation of abdominal CT scan can help radiologists analyze the scans faster and segment organ images with fewer errors. However, existing methods are not efficient enough to perform the segmentation process for victims of accidents and emergencies situations. In this paper we propose an efficient liver segmentation with our 3D to 2D fully connected network (3D-2D-FCN). The segmented mask is enhanced by means of conditional random field on the organ's border. Consequently, we segment a target liver in less than a minute with Dice score of 93.52.

[15]  arXiv:1802.07801 [pdf, ps, other]
Title: A New Hybrid Half-Duplex/Full-Duplex Relaying System with Antenna Diversity
Comments: 13 pages, 7 figures
Subjects: Information Theory (cs.IT)

The hybrid half-duplex/full-duplex (HD/FD) relaying scheme is an effective paradigm to overcome the negative effects of the self-interference incurred by the full-duplex (FD) mode. However, traditional hybrid HD/FD scheme does not consider the diversity gain incurred by the multiple antennas of the FD node when the system works in the HD mode, leading to the waste of the system resources. In this paper, we propose a new hybrid HD/FD relaying scheme, which utilizes both the antennas of the FD relay node for reception and transmission when the system works in the HD mode. With multiple antennas, the maximum ratio combining/maximum ratio transmission is adopted to process the signals at the relay node. Based on this scheme, we derive the exact closed-form system outage probability and conduct various numerical simulations. The results show that the proposed scheme remarkably improves the system outage performance over the traditional scheme, and demonstrate that the proposed scheme can more effectively alleviate the adverse effects of the residual self-interference.

[16]  arXiv:1802.07802 [pdf, other]
Title: Protecting Sensory Data against Sensitive Inferences
Comments: 6 pages
Subjects: Learning (cs.LG)

There is growing concern about how personal data are used when users grant applications direct access to the sensors in their mobile devices. For example, time-series data generated by motion sensors reflect directly users' activities and indirectly their personalities. It is therefore important to design privacy-preserving data analysis methods that can run on mobile devices. In this paper, we propose a feature learning architecture that can be deployed in distributed environments to provide flexible and negotiable privacy-preserving data transmission. It should be flexible because the internal architecture of each component can be independently changed according to users or service providers needs. It is negotiable because expected privacy and utility can be negotiated based on the requirements of the data subject and underlying application. For the specific use-case of activity recognition, we conducted experiments on two real-world datasets of smartphone's motion sensors, one of them is collected by the authors and will be publicly available by this paper for the first time. Results indicate the proposed framework establishes a good trade-off between application's utility and data subjects' privacy. We show that it maintains the usefulness of the transformed data for activity recognition (with around an average loss of three percentage points) while almost eliminating the possibility of gender classification (from more than 90\% to around 50\%, the target random guess). These results also have implication for moving from the current binary setting of granting permission to mobile apps or not, toward a situation where users can grant each application permission over a limited range of inferences according to the provided services.

[17]  arXiv:1802.07804 [pdf]
Title: Low complexity convolutional neural network for vessel segmentation in portable retinal diagnostic devices
Comments: 5 pages, 6 figures
Subjects: Computer Vision and Pattern Recognition (cs.CV)

Retinal vessel information is helpful in retinal disease screening and diagnosis. Retinal vessel segmentation provides useful information about vessels and can be used by physicians during intraocular surgery and retinal diagnostic operations. Convolutional neural networks (CNNs) are powerful tools for classification and segmentation of medical images. Complexity of CNNs makes it difficult to implement them in portable devices such as binocular indirect ophthalmoscopes. In this paper a simplification approach is proposed for CNNs based on combination of quantization and pruning. Fully connected layers are quantized and convolutional layers are pruned to have a simple and efficient network structure. Experiments on images of the STARE dataset show that our simplified network is able to segment retinal vessels with acceptable accuracy and low complexity.

[18]  arXiv:1802.07805 [pdf, other]
Title: The Signpost Platform for City-Scale Sensing
Comments: Published in the proceedings of the 17th ACM/IEEE Conference on Information Processing in Sensor Networks (IPSN'18)
Subjects: Computers and Society (cs.CY)

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.

[19]  arXiv:1802.07810 [pdf, other]
Title: Manipulating and Measuring Model Interpretability
Subjects: Artificial Intelligence (cs.AI); Computers and Society (cs.CY)

Despite a growing body of research focused on creating interpretable machine learning methods, there have been few empirical studies verifying whether interpretable methods achieve their intended effects on end users. We present a framework for assessing the effects of model interpretability on users via pre-registered experiments in which participants are shown functionally identical models that vary in factors thought to influence interpretability. Using this framework, we ran a sequence of large-scale randomized experiments, varying two putative drivers of interpretability: the number of features and the model transparency (clear or black-box). We measured how these factors impact trust in model predictions, the ability to simulate a model, and the ability to detect a model's mistakes. We found that participants who were shown a clear model with a small number of features were better able to simulate the model's predictions. However, we found no difference in multiple measures of trust and found that clear models did not improve the ability to correct mistakes. These findings suggest that interpretability research could benefit from more emphasis on empirically verifying that interpretable models achieve all their intended effects.

[20]  arXiv:1802.07814 [pdf, other]
Title: Learning to Explain: An Information-Theoretic Perspective on Model Interpretation
Subjects: Learning (cs.LG); Artificial Intelligence (cs.AI); Machine Learning (stat.ML)

We introduce instancewise feature selection as a methodology for model interpretation. Our method is based on learning a function to extract a subset of features that are most informative for each given example. This feature selector is trained to maximize the mutual information between selected features and the response variable, where the conditional distribution of the response variable given the input is the model to be explained. We develop an efficient variational approximation to the mutual information, and show that the resulting method compares favorably to other model explanation methods on a variety of synthetic and real data sets using both quantitative metrics and human evaluation.

[21]  arXiv:1802.07817 [pdf, other]
Title: Formalizing and Implementing Distributed Ledger Objects
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC)

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.

[22]  arXiv:1802.07830 [pdf, ps, other]
Title: Proper Semirings and Proper Convex Functors
Comments: FoSSaCS 2018
Subjects: Logic in Computer Science (cs.LO)

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.

[23]  arXiv:1802.07832 [pdf, other]
Title: Comparative study of finite element methods using the Time-Accuracy-Size (TAS) spectrum analysis
Subjects: Mathematical Software (cs.MS); Performance (cs.PF)

We present a performance analysis appropriate for comparing algorithms using different numerical discretizations. By taking into account the total time-to-solution, numerical accuracy with respect to an error norm, and the computation rate, a cost-benefit analysis can be performed to determine which algorithm and discretization are particularly suited for an application. This work extends the performance spectrum model in Chang et. al. 2017 for interpretation of hardware and algorithmic tradeoffs in numerical PDE simulation. As a proof-of-concept, popular finite element software packages are used to illustrate this analysis for Poisson's equation.

[24]  arXiv:1802.07833 [pdf, ps, other]
Title: Variational Inference for Policy Gradient
Authors: Tianbing Xu
Comments: 7 pages
Subjects: Learning (cs.LG); Artificial Intelligence (cs.AI); Machine Learning (stat.ML)

Inspired by the seminal work on Stein Variational Inference and Stein Variational Policy Gradient, we derived a method to generate samples from the posterior variational parameter distribution by \textit{explicitly} minimizing the KL divergence to match the target distribution in an amortize fashion. Consequently, we applied this varational inference technique into vanilla policy gradient, TRPO and PPO with Bayesian Neural Network parameterizations for reinforcement learning problems.

[25]  arXiv:1802.07839 [pdf, other]
Title: CoVeR: Learning Covariate-Specific Vector Representations with Tensor Decompositions
Comments: 11 pages
Subjects: Computation and Language (cs.CL)

Word embedding is a useful approach to capture co-occurrence structures in a large corpus of text. In addition to the text data itself, we often have additional covariates associated with individual documents in the corpus---e.g. the demographic of the author, time and venue of publication, etc.---and we would like the embedding to naturally capture the information of the covariates. In this paper, we propose CoVeR, a new tensor decomposition model for vector embeddings with covariates. CoVeR jointly learns a base embedding for all the words as well as a weighted diagonal transformation to model how each covariate modifies the base embedding. To obtain the specific embedding for a particular author or venue, for example, we can then simply multiply the base embedding by the transformation matrix associated with that time or venue. The main advantages of our approach is data efficiency and interpretability of the covariate transformation matrix. Our experiments demonstrate that our joint model learns substantially better embeddings conditioned on each covariate compared to the standard approach of learning a separate embedding for each covariate using only the relevant subset of data, as well as other related methods. Furthermore, CoVeR encourages the embeddings to be "topic-aligned" in the sense that the dimensions have specific independent meanings. This allows our covariate-specific embeddings to be compared by topic, enabling downstream differential analysis. We empirically evaluate the benefits of our algorithm on several datasets, and demonstrate how it can be used to address many natural questions about the effects of covariates.

[26]  arXiv:1802.07840 [pdf, other]
Title: CECT: Computationally Efficient Congestion-avoidance and Traffic Engineering in Software-defined Cloud Data Centers
Subjects: Networking and Internet Architecture (cs.NI)

The proliferation of cloud data center applications and network function virtualization (NFV) boosts dynamic and QoS dependent traffic into the data centers network. Currently, lots of network routing protocols are requirement agnostic, while other QoS-aware protocols are computationally complex and inefficient for small flows. In this paper, a computationally efficient congestion avoidance scheme, called CECT, for software-defined cloud data centers is proposed. The proposed algorithm, CECT, not only minimizes network congestion but also reallocates the resources based on the flow requirements. To this end, we use a routing architecture to reconfigure the network resources triggered by two events: 1) the elapsing of a predefined time interval, or, 2) the occurrence of congestion. Moreover, a forwarding table entries compression technique is used to reduce the computational complexity of CECT. In this way, we mathematically formulate an optimization problem and define a genetic algorithm to solve the proposed optimization problem. We test the proposed algorithm on real-world network traffic. Our results show that CECT is computationally fast and the solution is feasible in all cases. In order to evaluate our algorithm in term of throughput, CECT is compared with ECMP (where the shortest path algorithm is used as the cost function). Simulation results confirm that the throughput obtained by running CECT is improved up to 3x compared to ECMP while packet loss is decreased up to 2x.

[27]  arXiv:1802.07842 [pdf, other]
Title: Convergent Actor-Critic Algorithms Under Off-Policy Training and Function Approximation
Authors: Hamid Reza Maei
Subjects: Artificial Intelligence (cs.AI)

We present the first class of policy-gradient algorithms that work with both state-value and policy function-approximation, and are guaranteed to converge under off-policy training. Our solution targets problems in reinforcement learning where the action representation adds to the-curse-of-dimensionality; that is, with continuous or large action sets, thus making it infeasible to estimate state-action value functions (Q functions). Using state-value functions helps to lift the curse and as a result naturally turn our policy-gradient solution into classical Actor-Critic architecture whose Actor uses state-value function for the update. Our algorithms, Gradient Actor-Critic and Emphatic Actor-Critic, are derived based on the exact gradient of averaged state-value function objective and thus are guaranteed to converge to its optimal solution, while maintaining all the desirable properties of classical Actor-Critic methods with no additional hyper-parameters. To our knowledge, this is the first time that convergent off-policy learning methods have been extended to classical Actor-Critic methods with function approximation.

[28]  arXiv:1802.07845 [pdf, other]
Title: Detecting Small, Densely Distributed Objects with Filter-Amplifier Networks and Loss Boosting
Subjects: Computer Vision and Pattern Recognition (cs.CV)

Detecting small, densely distributed objects is a significant challenge: small objects often contain less distinctive information compared to larger ones, and finer-grained precision of bounding box boundaries are required. In this paper, we propose two techniques for addressing this problem. First, we estimate the likelihood that each pixel belongs to an object boundary rather than predicting coordinates of bounding boxes (as YOLO, Faster-RCNN and SSD do), by proposing a new architecture called Filter-Amplifier Networks (FANs). Second, we introduce a technique called Loss Boosting (LB) which attempts to soften the loss imbalance problem on each image. We test our algorithm on the problem of detecting electrical components on a new, realistic, diverse dataset of printed circuit boards (PCBs), as well as the problem of detecting vehicles in the Vehicle Detection in Aerial Imagery (VEDAI) dataset.
Experiments show that our method works significantly better than current state-of-the-art algorithms with respect to accuracy, recall and average IoU.

[29]  arXiv:1802.07846 [pdf, other]
Title: Cross-Modality Synthesis from CT to PET using FCN and GAN Networks for Improved Automated Lesion Detection
Comments: Preprint submitted to Engineering applications of artificial intelligence
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI)

In this work we present a novel system for generation of virtual PET images using CT scans. We combine a fully convolutional network (FCN) with a conditional generative adversarial network (GAN) to generate simulated PET data from given input CT data. The synthesized PET can be used for false-positive reduction in lesion detection solutions. Clinically, such solutions may enable lesion detection and drug treatment evaluation in a CT-only environment, thus reducing the need for the more expensive and radioactive PET/CT scan. Our dataset includes 60 PET/CT scans from Sheba Medical center. We used 23 scans for training and 37 for testing. Different schemes to achieve the synthesized output were qualitatively compared. Quantitative evaluation was conducted using an existing lesion detection software, combining the synthesized PET as a false positive reduction layer for the detection of malignant lesions in the liver. Current results look promising showing a 28% reduction in the average false positive per case from 2.9 to 2.1. The suggested solution is comprehensive and can be expanded to additional body organs, and different modalities.

[30]  arXiv:1802.07849 [pdf, ps, other]
Title: Clones in Social Networks
Comments: 12 pages, 2 figures, 2 tables
Subjects: Social and Information Networks (cs.SI)

It is well known that any bipartite (social) network can be regarded as a formal context $(G,M,I)$. Therefore, such networks give raise to formal concept lattices which can be investigated utilizing the toolset of Formal Concept Analysis (FCA). In particular, the notion of clones in closure systems on $M$, i.e., pairwise interchangeable attributes that leave the closure system unchanged, suggests itself naturally as a candidate to be analyzed in the realm of FCA based social network analysis. In this study, we investigate the notion of clones in social networks. After building up some theoretical background for the clone relation in formal contexts we try to find clones in real word data sets. To this end, we provide an experimental evaluation on nine mostly well known social networks and provide some first insights on the impact of clones. We conclude our work by nourishing the understanding of clones by generalizing those to permutations of higher order.

[31]  arXiv:1802.07851 [pdf, ps, other]
Title: Data Privacy for a $ρ$-Recoverable Function
Subjects: Information Theory (cs.IT)

A user's data is represented by a finite-valued random variable. Given a function of the data, a querier is required to recover, with at least a prescribed probability, the value of the function based on a query response provided by the user. The user devises the query response, subject to the recoverability requirement, so as to maximize privacy of the data from the querier. Privacy is measured by the probability of error incurred by the querier in estimating the data from the query response. We analyze single and multiple independent query responses, with each response satisfying the recoverability requirement, that provide maximum privacy to the user. Achievability schemes with explicit randomization mechanisms for query responses are given and their privacy compared with converse upper bounds.

[32]  arXiv:1802.07852 [pdf]
Title: An Affordable Bio-Sensing and Activity Tagging Platform for HCI Research
Subjects: Human-Computer Interaction (cs.HC)

We present a novel multi-modal bio-sensing platform capable of integrating multiple data streams for use in real-time applications. The system is composed of a central compute module and a companion headset. The compute node collects, time-stamps and transmits the data while also providing an interface for a wide range of sensors including electroencephalogram, photoplethysmogram, electrocardiogram, and eye gaze among others. The companion headset contains the gaze tracking cameras. By integrating many of the measurements systems into an accessible package, we are able to explore previously unanswerable questions ranging from open-environment interactions to emotional response studies. Though some of the integrated sensors are designed from the ground-up to fit into a compact form factor, we validate the accuracy of the sensors and find that they perform similarly to, and in some cases better than, alternatives.

[33]  arXiv:1802.07854 [pdf]
Title: Driver Hand Localization and Grasp Analysis: A Vision-based Real-time Approach
Subjects: Computer Vision and Pattern Recognition (cs.CV)

Extracting hand regions and their grasp information from images robustly in real-time is critical for occupants' safety and in-vehicular infotainment applications. It must however, be noted that naturalistic driving scenes suffer from rapidly changing illumination and occlusion. This is aggravated by the fact that hands are highly deformable objects, and change in appearance frequently. This work addresses the task of accurately localizing driver hands and classifying the grasp state of each hand. We use a fast ConvNet to first detect likely hand regions. Next, a pixel-based skin classifier that takes into account the global illumination changes is used to refine the hand detections and remove false positives. This step generates a pixel-level mask for each hand. Finally, we study each such masked regions and detect if the driver is grasping the wheel, or in some cases a mobile phone. Through evaluation we demonstrate that our method can outperform state-of-the-art pixel based hand detectors, while running faster (at 35 fps) than other deep ConvNet based frameworks even for grasp analysis. Hand mask cues are shown to be crucial when analyzing a set of driver hand gestures (wheel/mobile phone grasp and no-grasp) in naturalistic driving settings. The proposed detection and localization pipeline hence can act as a general framework for real-time hand detection and gesture classification.

[34]  arXiv:1802.07855 [pdf, other]
Title: RT-DAP: A Real-Time Data Analytics Platform for Large-scale Industrial Process Monitoring and Control
Subjects: Networking and Internet Architecture (cs.NI); Performance (cs.PF)

In most process control systems nowadays, process measurements are periodically collected and archived in historians. Analytics applications process the data, and provide results offline or in a time period that is considerably slow in comparison to the performance of the manufacturing process. Along with the proliferation of Internet-of-Things (IoT) and the introduction of "pervasive sensors" technology in process industries, increasing number of sensors and actuators are installed in process plants for pervasive sensing and control, and the volume of produced process data is growing exponentially. To digest these data and meet the ever-growing requirements to increase production efficiency and improve product quality, there needs to be a way to both improve the performance of the analytics system and scale the system to closely monitor a much larger set of plant resources. In this paper, we present a real-time data analytics platform, called RT-DAP, to support large-scale continuous data analytics in process industries. RT-DAP is designed to be able to stream, store, process and visualize a large volume of realtime data flows collected from heterogeneous plant resources, and feedback to the control system and operators in a realtime manner. A prototype of the platform is implemented on Microsoft Azure. Our extensive experiments validate the design methodologies of RT-DAP and demonstrate its efficiency in both component and system levels.

[35]  arXiv:1802.07856 [pdf, other]
Title: xView: Objects in Context in Overhead Imagery
Comments: Initial submission
Subjects: Computer Vision and Pattern Recognition (cs.CV)

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.

[36]  arXiv:1802.07858 [pdf, other]
Title: MPST: A Corpus of Movie Plot Synopses with Tags
Comments: Accepted at LREC 2018
Subjects: Computation and Language (cs.CL)

Social tagging of movies reveals a wide range of heterogeneous information about movies, like the genre, plot structure, soundtracks, metadata, visual and emotional experiences. Such information can be valuable in building automatic systems to create tags for movies. Automatic tagging systems can help recommendation engines to improve the retrieval of similar movies as well as help viewers to know what to expect from a movie in advance. In this paper, we set out to the task of collecting a corpus of movie plot synopses and tags. We describe a methodology that enabled us to build a fine-grained set of around 70 tags exposing heterogeneous characteristics of movie plots and the multi-label associations of these tags with some 14K movie plot synopses. We investigate how these tags correlate with movies and the flow of emotions throughout different types of movies. Finally, we use this corpus to explore the feasibility of inferring tags from plot synopses. We expect the corpus will be useful in other tasks where analysis of narratives is relevant.

[37]  arXiv:1802.07859 [pdf, other]
Title: Modelling spatiotemporal variation of positive and negative sentiment on Twitter to improve the identification of localised deviations
Comments: 14 pages, 5 figures
Subjects: Social and Information Networks (cs.SI); Computation and Language (cs.CL)

Studies examining how sentiment on social media varies over time and space appear to produce inconsistent results. Analysing 16.54 million English-language tweets from 100 cities posted between 13 July and 30 November 2017, our aim was to clarify how spatiotemporal and social factors contributed to variation in sentiment on Twitter. We estimated positive and negative sentiment for each of the cities using dictionary-based sentiment analysis and constructed models to explain differences in sentiment using time of day, day of week, weather, interaction type (social or non-social), and city as factors. Tests in a distinct but contiguous period of time showed that all factors were independently associated with sentiment. In the full multivariable model of positive (Pearson's R in test data 0.236; 95% CI 0.231-0.241), and negative (Pearson's R in test data 0.306 95% CI 0.301-0.310) sentiment, city and time of day explained more of the variance than other factors. Extreme differences between observed and expected sentiment using the full model appeared to be better aligned with international news events than degenerate models. In applications that aim to detect localised events using the sentiment of Twitter populations, it is useful to account for baseline differences before looking for unexpected changes.

[38]  arXiv:1802.07860 [pdf, other]
Title: Neural Predictive Coding using Convolutional Neural Networks towards Unsupervised Learning of Speaker Characteristics
Subjects: Sound (cs.SD); Computation and Language (cs.CL); Audio and Speech Processing (eess.AS)

Learning speaker-specific features is vital in many applications like speaker recognition, diarization and speech recognition. This paper provides a novel approach, we term Neural Predictive Coding (NPC), to learn speaker-specific characteristics in a completely unsupervised manner from large amounts of unlabeled training data that even contain multi-speaker audio streams. The NPC framework exploits the proposed short-term active-speaker stationarity hypothesis which assumes two temporally-close short speech segments belong to the same speaker, and thus a common representation that can encode the commonalities of both the segments, should capture the vocal characteristics of that speaker. We train a convolutional deep siamese network to produce "speaker embeddings" by optimizing a loss function that increases between-speaker variability and decreases within-speaker variability. The trained NPC model can produce these embeddings by projecting any test audio stream into a high dimensional manifold where speech frames of the same speaker come closer than they do in the raw feature space. Results in the frame-level speaker classification experiment along with the visualization of the embeddings manifest the distinctive ability of the NPC model to learn short-term speaker-specific features as compared to raw MFCC features and i-vectors. The utterance-level speaker classification experiments show that concatenating simple statistics of the short-term NPC embeddings over the whole utterance with the utterance-level i-vectors can give useful complimentary information to the i-vectors and boost the classification accuracy. The results also show the efficacy of this technique to learn those characteristics from large amounts of unlabeled training set which has no prior information about the environment of the test set.

[39]  arXiv:1802.07862 [pdf, other]
Title: Multimodal Named Entity Recognition for Short Social Media Posts
Subjects: Computation and Language (cs.CL)

We introduce a new task called Multimodal Named Entity Recognition (MNER) for noisy user-generated data such as tweets or Snapchat captions, which comprise short text with accompanying images. These social media posts often come in inconsistent or incomplete syntax and lexical notations with very limited surrounding textual contexts, bringing significant challenges for NER. To this end, we create a new dataset for MNER called SnapCaptions (Snapchat image-caption pairs submitted to public and crowd-sourced stories with fully annotated named entities). We then build upon the state-of-the-art Bi-LSTM word/character based NER models with 1) a deep image network which incorporates relevant visual context to augment textual information, and 2) a generic modality-attention module which learns to attenuate irrelevant modalities while amplifying the most informative ones to extract contexts from, adaptive to each sample and token. The proposed MNER model with modality attention significantly outperforms the state-of-the-art text-only NER models by successfully leveraging provided visual contexts, opening up potential applications of MNER on myriads of social media platforms.

[40]  arXiv:1802.07863 [pdf, other]
Title: Efficient Enumeration of Dominating Sets for Sparse Graphs
Subjects: Data Structures and Algorithms (cs.DS)

Dominating sets are fundamental graph structures. However, enumeration of dominating sets has not received much attention. This study aims to propose two efficient enumeration algorithms for sparse graphs. The first algorithm enumerates all the dominating sets for $k$-degenerate graphs in $O(k)$ time per solution using $O(n + m)$ space. Since planar graphs have a constant degeneracy, this algorithm can enumerate all such sets for planar graphs in constant time per solution. The other algorithm enumerates all the dominating sets in constant time per solution for input graphs with a girth of at least nine.

[41]  arXiv:1802.07866 [pdf]
Title: Multi-Sensor Integration for Indoor 3D Reconstruction
Authors: Jacky C.K. Chow
Comments: PhD Thesis, 2014, University of Calgary (Canada), this http URL
Subjects: Computer Vision and Pattern Recognition (cs.CV); Robotics (cs.RO)

Outdoor maps and navigation information delivered by modern services and technologies like Google Maps and Garmin navigators have revolutionized the lifestyle of many people. Motivated by the desire for similar navigation systems for indoor usage from consumers, advertisers, emergency rescuers/responders, etc., many indoor environments such as shopping malls, museums, casinos, airports, transit stations, offices, and schools need to be mapped. Typically, the environment is first reconstructed by capturing many point clouds from various stations and defining their spatial relationships. Currently, there is a lack of an accurate, rigorous, and speedy method for relating point clouds in indoor, urban, satellite-denied environments. This thesis presents a novel and automatic way for fusing calibrated point clouds obtained using a terrestrial laser scanner and the Microsoft Kinect by integrating them with a low-cost inertial measurement unit. The developed system, titled the Scannect, is the first joint static-kinematic indoor 3D mapper.

[42]  arXiv:1802.07869 [pdf, other]
Title: End-to-end learning of keypoint detector and descriptor for pose invariant 3D matching
Comments: 10 pages, 9 figures, 3 tables, CVPR 2018
Subjects: Computer Vision and Pattern Recognition (cs.CV)

Finding correspondences between images or 3D scans is at the heart of many computer vision and image retrieval applications and is often enabled by matching local keypoint descriptors. Various learning approaches have been applied in the past to different stages of the matching pipeline, considering detector, descriptor, or metric learning objectives. These objectives were typically addressed separately and most previous work has focused on image data. This paper proposes an end-to-end learning framework for keypoint detection and its representation (descriptor) for 3D depth maps or 3D scans, where the two can be jointly optimized towards task-specific objectives without a need for separate annotations. We employ a Siamese architecture augmented by a sampling layer and a novel score loss function which in turn affects the selection of region proposals. The positive and negative examples are obtained automatically by sampling corresponding region proposals based on their consistency with known 3D pose labels. Matching experiments with depth data on multiple benchmark datasets demonstrate the efficacy of the proposed approach, showing significant improvements over state-of-the-art methods.

[43]  arXiv:1802.07876 [pdf, other]
Title: Federated Meta-Learning for Recommendation
Subjects: Learning (cs.LG); Information Retrieval (cs.IR)

Recommender systems have been widely studied from the machine learning perspective, where it is crucial to share information among users while preserving user privacy. In this work, we present a federated meta-learning framework for recommendation in which user information is shared at the level of algorithm, instead of model or data adopted in previous approaches. In this framework, user-specific recommendation models are locally trained by a shared parameterized algorithm, which preserves user privacy and at the same time utilizes information from other users to help model training. Interestingly, the model thus trained exhibits a high capacity at a small scale, which is energy- and communication-efficient. Experimental results show that recommendation models trained by meta-learning algorithms in the proposed framework outperform the state-of-the-art in accuracy and scale. For example, on a production dataset, a shared model under Google Federated Learning (McMahan et al., 2017) with 900,000 parameters has prediction accuracy 76.72%, while a shared algorithm under federated meta-learning with less than 30,000 parameters achieves accuracy of 86.23%.

[44]  arXiv:1802.07877 [pdf, other]
Title: Pooling homogeneous ensembles to build heterogeneous ensembles
Subjects: Learning (cs.LG); Artificial Intelligence (cs.AI); Machine Learning (stat.ML)

In ensemble methods, the outputs of a collection of diverse classifiers are combined in the expectation that the global prediction be more accurate than the individual ones. Heterogeneous ensembles consist of predictors of different types, which are likely to have different biases. If these biases are complementary, the combination of their decisions is beneficial. In this work, a family of heterogeneous ensembles is built by pooling classifiers from M homogeneous ensembles of different types of size T. Depending on the fraction of base classifiers of each type, a particular heterogeneous combination in this family is represented by a point in a regular simplex in M dimensions. The M vertices of this simplex represent the different homogeneous ensembles. A displacement away from one of these vertices effects a smooth transformation of the corresponding homogeneous ensemble into a heterogeneous one. The optimal composition of such heterogeneous ensemble can be determined using cross-validation or, if bootstrap samples are used to build the individual classifiers, out-of-bag data. An empirical analysis of such combinations of bootstraped ensembles composed of neural networks, SVMs, and random trees (i.e. from a standard random forest) illustrates the gains that can be achieved by this heterogeneous ensemble creation method.

[45]  arXiv:1802.07881 [pdf, other]
Title: Diversity regularization in deep ensembles
Comments: 6 pages
Subjects: Learning (cs.LG)

Calibrating the confidence of supervised learning models is important for a variety of contexts where the certainty over predictions should be reliable. However, it has been reported that deep neural network models are often too poorly calibrated for achieving complex tasks requiring reliable uncertainty estimates in their prediction. In this work, we are proposing a strategy for training deep ensembles with a diversity function regularization, which improves the calibration property while maintaining a similar prediction accuracy.

[46]  arXiv:1802.07887 [pdf, other]
Title: Nonlinear Online Learning with Adaptive Nyström Approximation
Subjects: Learning (cs.LG)

Use of nonlinear feature maps via kernel approximation has led to success in many online learning tasks. As a popular kernel approximation method, Nystr\"{o}m approximation, has been well investigated, and various landmark points selection methods have been proposed to improve the approximation quality. However, these improved Nystr\"{o}m methods cannot be directly applied to the online learning setting as they need to access the entire dataset to learn the landmark points, while we need to update model on-the-fly in the online setting. To address this challenge, we propose Adaptive Nystr\"{o}m approximation for solving nonlinear online learning problems. The key idea is to adaptively modify the landmark points via online kmeans and adjust the model accordingly via solving least square problem followed by a gradient descent step. We show that the resulting algorithm outperforms state-of-the-art online learning methods under the same budget.

[47]  arXiv:1802.07888 [pdf, other]
Title: Improved Techniques For Weakly-Supervised Object Localization
Subjects: Computer Vision and Pattern Recognition (cs.CV)

We propose an improved technique for weakly-supervised object localization. Conventional methods have a limitation that they focus only on most discriminative parts of the target objects. The recent study addressed this issue and resolved this limitation by augmenting the training data for less discriminative parts. To this end, we employ an effective data augmentation for improving the accuracy of the object localization. In addition, we introduce improved learning methods by optimizing Convolutional Neural Networks (CNN) based on the state-of-the-art model. Based on extensive experiments, we evaluate the effectiveness of the proposed approach, and demonstrate that our method actually improves the accuracy of the object localization, both quantitatively and qualitatively.

[48]  arXiv:1802.07889 [pdf, ps, other]
Title: Entropy Rate Estimation for Markov Chains with Large State Space
Subjects: Learning (cs.LG); Statistics Theory (math.ST); Machine Learning (stat.ML)

Estimating the entropy based on data is one of the prototypical problems in distribution property testing and estimation. For estimating the Shannon entropy of a distribution on $S$ elements with independent samples, [Paninski2004] showed that the sample complexity is sublinear in $S$, and [Valiant--Valiant2011] showed that consistent estimation of Shannon entropy is possible if and only if the sample size $n$ far exceeds $\frac{S}{\log S}$. In this paper we consider the problem of estimating the entropy rate of a stationary reversible Markov chain with $S$ states from a sample path of $n$ observations. We show that:
(1) As long as the Markov chain mixes not too slowly, i.e., the relaxation time is at most $O(\frac{S}{\ln^3 S})$, consistent estimation is achievable when $n \gg \frac{S^2}{\log S}$.
(2) As long as the Markov chain has some slight dependency, i.e., the relaxation time is at least $1+\Omega(\frac{\ln^2 S}{\sqrt{S}})$, consistent estimation is impossible when $n \lesssim \frac{S^2}{\log S}$.
Under both assumptions, the optimal estimation accuracy is shown to be $\Theta(\frac{S^2}{n \log S})$. In comparison, the empirical entropy rate requires at least $\Omega(S^2)$ samples to be consistent, even when the Markov chain is memoryless. In addition to synthetic experiments, we also apply the estimators that achieve the optimal sample complexity to estimate the entropy rate of the English language in the Penn Treebank and the Google One Billion Words corpora, which provides a natural benchmark for language modeling and relates it directly to the widely used perplexity measure.

[49]  arXiv:1802.07891 [pdf, other]
Title: A New Design of Binary MDS Array Codes with Asymptotically Weak-Optimal Repair
Subjects: Information Theory (cs.IT)

Binary maximum distance separable (MDS) array codes are a special class of erasure codes for distributed storage that not only provide fault tolerance with minimum storage redundancy but also achieve low computational complexity. They are constructed by encoding $k$ information columns into $r$ parity columns, in which each element in a column is a bit, such that any $k$ out of the $k+r$ columns suffice to recover all information bits. In addition to providing fault tolerance, it is critical to improve repair performance in practical applications. If one column of an MDS code is failed, it is known that we need to download at least $1/(d-k+1)$ fraction of the data stored in each of $d$ healthy columns. If this lower bound is achieved for the repair of the failure column from accessing arbitrary $d$ healthy columns, we say that the MDS code has optimal repair. However, if such lower bound is only achieved by $d$ specific healthy columns, then we say the MDS code has weak-optimal repair. Existing binary MDS array codes that achieve high data rate (i.e., $k/(k+r)>1/2$) and optimal repair of information column only support double fault tolerance (i.e., $r=2$), which is insufficient for failure-prone distributed storage environments in practice. This paper fills the void by proposing two explicit constructions of binary MDS array codes with more parity columns (i.e., $r\geq 3$) that achieve asymptotically weak-optimal repair, where $k+1\leq d\leq k+\lfloor(r-1)/2\rfloor$. Codes in the first construction have odd number of parity columns and asymptotically weak-optimal repair for any one information failure, while codes in the second construction have even number of parity columns and asymptotically weak-optimal repair for any one column failure.

[50]  arXiv:1802.07895 [pdf, ps, other]
Title: Learning Mixtures of Linear Regressions with Nearly Optimal Complexity
Subjects: Learning (cs.LG)

Mixtures of Linear Regressions (MLR) is an important mixture model with many applications. In this model, each observation is generated from one of the several unknown linear regression components, where the identity of the generated component is also unknown. Previous works either assume strong assumptions on the data distribution or have high complexity. This paper proposes a fixed parameter tractable algorithm for the problem under general conditions, which achieves global convergence and the sample complexity scales nearly linearly in the dimension. In particular, different from previous works that require the data to be from the standard Gaussian, the algorithm allows the data from Gaussians with different covariances. When the conditional number of the covariances and the number of components are fixed, the algorithm has nearly optimal sample complexity $N = \tilde{O}(d)$ as well as nearly optimal computational complexity $\tilde{O}(Nd)$, where $d$ is the dimension of the data space. To the best of our knowledge, this approach provides the first such recovery guarantee for this general setting.

[51]  arXiv:1802.07896 [pdf, ps, other]
Title: L2-Nonexpansive Neural Networks
Subjects: Artificial Intelligence (cs.AI); Learning (cs.LG)

This paper proposes a class of well-conditioned neural networks in which a unit amount of change in the inputs causes at most a unit amount of change in the outputs or any of the internal layers. We develop the known methodology of controlling Lipschitz constants to realize its full potential in maximizing robustness: our linear and convolution layers subsume those in the previous Parseval networks as a special case and allow greater degrees of freedom; aggregation, pooling, splitting and other operators are adapted in new ways, and a new loss function is proposed, all for the purpose of improving robustness. With MNIST and CIFAR-10 classifiers, we demonstrate a number of advantages. Without needing any adversarial training, the proposed classifiers exceed the state of the art in robustness against white-box L2-bounded adversarial attacks. Their outputs are quantitatively more meaningful than ordinary networks and indicate levels of confidence. They are also free of exploding gradients, among other desirable properties.

[52]  arXiv:1802.07898 [pdf, other]
Title: Glimpse Clouds: Human Activity Recognition from Unstructured Feature Points
Comments: To appear in CVPR 2018
Subjects: Computer Vision and Pattern Recognition (cs.CV)

We propose a method for human activity recognition from RGB data which does not rely on any pose information during test time, and which does not explicitly calculate pose information internally. Instead, a visual attention module learns to predict glimpse sequences in each frame. These glimpses correspond to interest points in the scene which are relevant to the classified activities. No spatial coherence is forced on the glimpse locations, which gives the module liberty to explore different points at each frame and better optimize the process of scrutinizing visual information. Tracking and sequentially integrating this kind of unstructured data is a challenge, which we address by separating the set of glimpses from a set of recurrent tracking/recognition workers. These workers receive the glimpses, jointly performing subsequent motion tracking and prediction of the activity itself. The glimpses are soft-assigned to the workers, optimizing coherence of the assignments in space, time and feature space using an external memory module. No hard decisions are taken, i.e. each glimpse point is assigned to all existing workers, albeit with different importance. Our methods outperform state-of-the-art methods on the largest human activity recognition dataset available to-date; NTU RGB+D Dataset, and on a smaller human action recognition dataset Northwestern-UCLA Multiview Action 3D Dataset.

[53]  arXiv:1802.07916 [pdf, ps, other]
Title: Guaranteed-cost consensus for multiagent networks with Lipschitz nonlinear dynamics and switching topologies
Comments: 16 pages
Subjects: Systems and Control (cs.SY)

Guaranteed-cost consensus for high-order nonlinear multi-agent networks with switching topologies is investigated. By constructing a time-varying nonsingular matrix with a specific structure, the whole dynamics of multi-agent networks is decomposed into the consensus and disagreement parts with nonlinear terms, which is the key challenge to be dealt with. An explicit expression of the consensus dynamics, which contains the nonlinear term, is given and its initial state is determined. Furthermore, by the structure property of the time-varying nonsingular transformation matrix and the Lipschitz condition, the impacts of the nonlinear term on the disagreement dynamics are linearized and the gain matrix of the consensus protocol is determined on the basis of the Riccati equation. Moreover, an approach to minimize the guaranteed cost is given in terms of linear matrix inequalities. Finally, the numerical simulation is shown to demonstrate the effectiveness of theoretical results.

[54]  arXiv:1802.07917 [pdf, ps, other]
Title: Regional Multi-Armed Bandits
Comments: AISTATS 2018
Subjects: Learning (cs.LG); Machine Learning (stat.ML)

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.

[55]  arXiv:1802.07918 [pdf, other]
Title: Video Person Re-identification by Temporal Residual Learning
Comments: Submitted to IEEE Transactions on Image Processing, including 5 figures and 4 tables. The first two authors contribute equally to this work
Subjects: Computer Vision and Pattern Recognition (cs.CV)

In this paper, we propose a novel feature learning framework for video person re-identification (re-ID). The proposed framework largely aims to exploit the adequate temporal information of video sequences and tackle the poor spatial alignment of moving pedestrians. More specifically, for exploiting the temporal information, we design a temporal residual learning (TRL) module to simultaneously extract the generic and specific features of consecutive frames. The TRL module is equipped with two bi-directional LSTM (BiLSTM), which are respectively responsible to describe a moving person in different aspects, providing complementary information for better feature representations. To deal with the poor spatial alignment in video re-ID datasets, we propose a spatial-temporal transformer network (ST^2N) module. Transformation parameters in the ST^2N module are learned by leveraging the high-level semantic information of the current frame as well as the temporal context knowledge from other frames. The proposed ST^2N module with less learnable parameters allows effective person alignments under significant appearance changes. Extensive experimental results on the large-scale MARS, PRID2011, ILIDS-VID and SDU-VID datasets demonstrate that the proposed method achieves consistently superior performance and outperforms most of the very recent state-of-the-art methods.

[56]  arXiv:1802.07923 [pdf, ps, other]
Title: Dynamic Output Feedback Guaranteed-Cost Synchronization for Multiagent Networks with Given Cost Budgets
Comments: 12 pages
Subjects: Systems and Control (cs.SY); Distributed, Parallel, and Cluster Computing (cs.DC)

The current paper addresses the distributed guaranteed-cost synchronization problems for general high-order linear multiagent networks. Existing works on the guaranteed-cost synchronization usually require all state information of neighboring agents and cannot give the cost budget previously. For both leaderless and leader-following interaction topologies, the current paper firstly proposes a dynamic output feedback synchronization protocol with guaranteed-cost constraints, which can realize the tradeoff design between the energy consumption and the synchronization regulation performance with the given cost budget. Then, according to different structure features of interaction topologies, leaderless and leader-following guaranteed-cost synchronization analysis and design criteria are presented, respectively, and an algorithm is proposed to deal with the impacts of nonlinear terms by using both synchronization analysis and design criteria. Especially, an explicit expression of the synchronization function is shown for leaderless cases, which is independent of protocol states and the given cost budget. Finally, numerical examples are presented to demonstrate theoretical results.

[57]  arXiv:1802.07926 [pdf, ps, other]
Title: Exploiting Inter-User Interference for Secure Massive Non-Orthogonal Multiple Access
Journal-ref: IEEE Journal on Seleted Areas in Communications, 2018
Subjects: Information Theory (cs.IT)

This paper considers the security issue of the fifth-generation (5G) wireless networks with massive connections, where multiple eavesdroppers aim to intercept the confidential messages through active eavesdropping. To realize secure massive access, non-orthogonal channel estimation (NOCE) and non-orthogonal multiple access (NOMA) techniques are combined to enhance the signal quality at legitimate users, while the inter-user interference is harnessed to deliberately confuse the eavesdroppers even without exploiting artificial noise (AN). We first analyze the secrecy performance of the considered secure massive access system and derive a closed-form expression for the ergodic secrecy rate. In particular, we reveal the impact of some key system parameters on the ergodic secrecy rate via asymptotic analysis with respect to a large number of antennas and a high transmit power at the base station (BS). Then, to fully exploit the inter-user interference for security enhancement, we propose to optimize the transmit powers in the stages of channel estimation and multiple access. Finally, extensive simulation results validate the effectiveness of the proposed secure massive access scheme.

[58]  arXiv:1802.07929 [pdf, other]
Title: Graph-Based Blind Image Deblurring From a Single Photograph
Subjects: Computer Vision and Pattern Recognition (cs.CV)

Blind image deblurring, i.e., deblurring without knowledge of the blur kernel, is a highly ill-posed problem. The problem can be solved in two parts: i) estimate a blur kernel from the blurry image, and ii) given estimated blur kernel, de-convolve blurry input to restore the target image. In this paper, we propose a graph-based blind image deblurring algorithm by interpreting an image patch as a signal on a weighted graph. Specifically, we first argue that a skeleton image---a proxy that retains the strong gradients of the target but smooths out the details---can be used to accurately estimate the blur kernel and has a unique bi-modal edge weight distribution. Then, we design a reweighted graph total variation (RGTV) prior that can efficiently promote a bi-modal edge weight distribution given a blurry patch. Further, to analyze RGTV in the graph frequency domain, we introduce a new weight function to represent RGTV as a graph $l_1$-Laplacian regularizer. This leads to a graph spectral filtering interpretation of the prior with desirable properties, including robustness to noise and blur, strong piecewise smooth (PWS) filtering and sharpness promotion. Minimizing a blind image deblurring objective with RGTV results in a non-convex non-differentiable optimization problem. We leverage the new graph spectral interpretation for RGTV to design an efficient algorithm that solves for the skeleton image and the blur kernel alternately. Specifically for Gaussian blur, we propose a further speedup strategy for blind Gaussian deblurring using accelerated graph spectral filtering. Finally, with the computed blur kernel, recent non-blind image deblurring algorithms can be applied to restore the target image. Experimental results demonstrate that our algorithm successfully restores latent sharp images and outperforms state-of-the-art methods quantitatively and qualitatively.

[59]  arXiv:1802.07931 [pdf, other]
Title: Where's YOUR focus: Personalized Attention
Authors: Sikun Lin, Pan Hui
Subjects: Computer Vision and Pattern Recognition (cs.CV)

Human visual attention is subjective and biased according to the personal preference of the viewer, however, current works of saliency detection are general and objective, without counting the factor of the observer. This will make the attention prediction for a particular person not accurate enough. In this work, we present the novel idea of personalized attention prediction and develop Personalized Attention Network (PANet), a convolutional network that predicts saliency in images with personal preference. The model consists of two streams which share common feature extraction layers, and one stream is responsible for saliency prediction, while the other is adapted from the detection model and used to fit user preference. We automatically collect user preference from their albums and leaves them freedom to define what and how many categories their preferences are divided into. To train PANet, we dynamically generate ground truth saliency maps upon existing detection labels and saliency labels, and the generation parameters are based upon our collected datasets consists of 1k images. We evaluate the model with saliency prediction metrics and test the trained model on different preference vectors. The results have shown that our system is much better than general models in personalized saliency prediction and is efficient to use for different preferences.

[60]  arXiv:1802.07932 [pdf, ps, other]
Title: Faster integer multiplication using short lattice vectors
Comments: 16 pages
Subjects: Symbolic Computation (cs.SC); Data Structures and Algorithms (cs.DS); Number Theory (math.NT)

We prove that $n$-bit integers may be multiplied in $O(n \log n \, 4^{\log^* n})$ bit operations. This complexity bound had been achieved previously by several authors, assuming various unproved number-theoretic hypotheses. Our proof is unconditional, and depends in an essential way on Minkowski's theorem concerning lattice vectors in symmetric convex sets.

[61]  arXiv:1802.07934 [pdf, other]
Title: Adversarial Learning for Semi-Supervised Semantic Segmentation
Comments: Code and models available at this https URL
Subjects: Computer Vision and Pattern Recognition (cs.CV)

We propose a method for semi-supervised semantic segmentation using the 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 the performance on semantic segmentation by coupling the adversarial loss with the standard cross entropy loss on the segmentation network. In addition, the fully convolutional discriminator enables the semi-supervised learning through discovering the trustworthy regions in prediction results of unlabeled images, providing additional supervisory signals. In contrast to existing methods that utilize weakly-labeled images, our method leverages unlabeled images without any annotation to enhance the segmentation model. Experimental results on both the PASCAL VOC 2012 dataset and the Cityscapes dataset demonstrate the effectiveness of our algorithm.

[62]  arXiv:1802.07936 [pdf, ps, other]
Title: Two theorems on distribution of Gaussian quadratic forms
Comments: Problems of Information Transmission, v. 53, no. 3, pp. 3--15, 2017
Subjects: Information Theory (cs.IT); Probability (math.PR)

New results on comparison of distributions of Gaussian quadratic forms are presented

[63]  arXiv:1802.07938 [pdf, other]
Title: Aspect-Aware Latent Factor Model: Rating Prediction with Ratings and Reviews
Comments: This paper has been accepted by the WWW 2018 Conference
Subjects: Information Retrieval (cs.IR)

Although latent factor models (e.g., matrix factorization) achieve good accuracy in rating prediction, they suffer from several problems including cold-start, non-transparency, and suboptimal recommendation for local users or items. In this paper, we employ textual review information with ratings to tackle these limitations. Firstly, we apply a proposed aspect-aware topic model (ATM) on the review text to model user preferences and item features from different aspects, and estimate the aspect importance of a user towards an item. The aspect importance is then integrated into a novel aspect-aware latent factor model (ALFM), which learns user's and item's latent factors based on ratings. In particular, ALFM introduces a weighted matrix to associate those latent factors with the same set of aspects discovered by ATM, such that the latent factors could be used to estimate aspect ratings. Finally, the overall rating is computed via a linear combination of the aspect ratings, which are weighted by the corresponding aspect importance. To this end, our model could alleviate the data sparsity problem and gain good interpretability for recommendation. Besides, an aspect rating is weighted by an aspect importance, which is dependent on the targeted user's preferences and targeted item's features. Therefore, it is expected that the proposed method can model a user's preferences on an item more accurately for each user-item pair locally. Comprehensive experimental studies have been conducted on 19 datasets from Amazon and Yelp 2017 Challenge dataset. Results show that our method achieves significant improvement compared with strong baseline methods, especially for users with only few ratings. Moreover, our model could interpret the recommendation results in depth.

[64]  arXiv:1802.07940 [pdf, ps, other]
Title: On detection of Gaussian stochastic sequences
Comments: Problems of Information Transmission, vol. 53, no. 4, pp. 47--66, 2017
Subjects: Information Theory (cs.IT)

The problem of minimax detection of Gaussian random signal vector in White Gaussian additive noise is considered. It is supposed that an unknown vector $\boldsymbol{\sigma}$ of the signal vector intensities belong to the given set ${\mathcal E}$. It is investigated when it is possible to replace the set ${\mathcal E}$ by a smaller set ${\mathcal E}_{0}$ without loss of quality (and, in particular, to replace it by a single point $\boldsymbol{\sigma}_{0}$).

[65]  arXiv:1802.07942 [pdf, other]
Title: Numerical integration in arbitrary-precision ball arithmetic
Comments: 8 pages, 1 figure
Subjects: Mathematical Software (cs.MS); Numerical Analysis (cs.NA)

We present an implementation of arbitrary-precision numerical integration with rigorous error bounds in the Arb library. Rapid convergence is ensured for piecewise complex analytic integrals by use of the Petras algorithm, which combines adaptive bisection with adaptive Gaussian quadrature where error bounds are determined via complex magnitudes without evaluating derivatives. The code is general, easy to use, and efficient, often outperforming existing non-rigorous software.

[66]  arXiv:1802.07944 [pdf, other]
Title: The Clever Shopper Problem
Comments: 15 pages, 3 figures, to appear at the 13th International Computer Science Symposium in Russia (CSR 2018)
Subjects: Data Structures and Algorithms (cs.DS)

We investigate a variant of the so-called "Internet Shopping Problem" introduced by Blazewicz et al. (2010), where a customer wants to buy a list of products at the lowest possible total cost from shops which offer discounts when purchases exceed a certain threshold. Although the problem is NP-hard, we provide exact algorithms for several cases, e.g. when each shop sells only two items, and an FPT algorithm for the number of items, or for the number of shops when all prices are equal. We complement each result with hardness proofs in order to draw a tight boundary between tractable and intractable cases. Finally, we give an approximation algorithm and hardness results for the problem of maximising the sum of discounts.

[67]  arXiv:1802.07945 [pdf]
Title: Actigraphy-based Sleep/Wake Pattern Detection using Convolutional Neural Networks
Subjects: Learning (cs.LG)

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.

[68]  arXiv:1802.07956 [pdf, other]
Title: Stereo obstacle detection for unmanned surface vehicles by IMU-assisted semantic segmentation
Comments: 14 pages, 18 figures, new publicly available multi-modal obstacle detection dataset
Subjects: Robotics (cs.RO); Computer Vision and Pattern Recognition (cs.CV)

A new obstacle detection algorithm for unmanned surface vehicles (USVs) is presented. A state-of-the-art graphical model for semantic segmentation is extended to incorporate boat pitch and roll measurements from the on-board inertial measurement unit (IMU), and a stereo verification algorithm that consolidates tentative detections obtained from the segmentation is proposed. The IMU readings are used to estimate the location of horizon line in the image, which automatically adjusts the priors in the probabilistic semantic segmentation model. We derive the equations for projecting the horizon into images, propose an efficient optimization algorithm for the extended graphical model, and offer a practical IMU-camera-USV calibration procedure. Using an USV equipped with multiple synchronized sensors, we captured a new challenging multi-modal dataset, and annotated its images with water edge and obstacles. Experimental results show that the proposed algorithm significantly outperforms the state of the art, with nearly 30% improvement in water-edge detection accuracy, an over 21% reduction of false positive rate, an almost 60% reduction of false negative rate, and an over 65% increase of true positive rate, while its Matlab implementation runs in real-time.

[69]  arXiv:1802.07957 [pdf, other]
Title: Non-rigid Object Tracking via Deep Multi-scale Spatial-Temporal Discriminative Saliency Maps
Comments: Submitted to IEEE Transactions on Image Processing, including 12 pages, 9 figures and 1 table. Now under view
Subjects: Computer Vision and Pattern Recognition (cs.CV)

In this paper we propose an effective non-rigid object tracking method based on spatial-temporal consistent saliency detection. In contrast to most existing trackers that use a bounding box to specify the tracked target, the proposed method can extract the accurate regions of the target as tracking output, which achieves better description of the non-rigid objects while reduces background pollution to the target model. Furthermore, our model has several unique features. First, a tailored deep fully convolutional neural network (TFCN) is developed to model the local saliency prior for a given image region, which not only provides the pixel-wise outputs but also integrates the semantic information. Second, a multi-scale multi-region mechanism is proposed to generate local region saliency maps that effectively consider visual perceptions with different spatial layouts and scale variations. Subsequently, these saliency maps are fused via a weighted entropy method, resulting in a final discriminative saliency map. Finally, we present a non-rigid object tracking algorithm based on the proposed saliency detection method by utilizing a spatial-temporal consistent saliency map (STCSM) model to conduct target-background classification and using a simple fine-tuning scheme for online updating. Numerous experimental results demonstrate that the proposed algorithm achieves competitive performance in comparison with state-of-the-art methods for both saliency detection and visual tracking, especially outperforming other related trackers on the non-rigid object tracking datasets.

[70]  arXiv:1802.07966 [pdf, other]
Title: Incremental and Iterative Learning of Answer Set Programs from Mutually Distinct Examples
Subjects: Artificial Intelligence (cs.AI); Learning (cs.LG); Logic in Computer Science (cs.LO)

Over these years the Artificial Intelligence (AI) community has produced several datasets which have given the machine learning algorithms the opportunity to learn various skills across various domains. However, a subclass of these machine learning algorithms that aimed at learning logic programs, namely the Inductive Logic Programming algorithms, have often failed at the task due to the vastness of these datasets. This has impacted the usability of knowledge representation and reasoning techniques in the development of AI systems. In this research, we try to address this scalability issue for the algorithms that learn Answer Set Programs. We present a sound and complete algorithm which takes the input in a slightly different manner and perform an efficient and more user controlled search for a solution. We show via experiments that our algorithm can learn from two popular datasets from machine learning community, namely bAbl (a question answering dataset) and MNIST (a dataset for handwritten digit recognition), which to the best of our knowledge was not previously possible. The system is publicly available at https://goo.gl/KdWAcV.

[71]  arXiv:1802.07967 [pdf, ps, other]
Title: Near Isometric Terminal Embeddings for Doubling Metrics
Subjects: Data Structures and Algorithms (cs.DS); Computational Geometry (cs.CG)

Given a metric space $(X,d)$, a set of terminals $K\subseteq X$, and a parameter $t\ge 1$, we consider metric structures (e.g., spanners, distance oracles, embedding into normed spaces) that preserve distances for all pairs in $K\times X$ up to a factor of $t$, and have small size (e.g. number of edges for spanners, dimension for embeddings). While such terminal (aka source-wise) metric structures are known to exist in several settings, no terminal spanner or embedding with distortion close to 1, i.e., $t=1+\epsilon$ for some small $0<\epsilon<1$, is currently known.
Here we devise such terminal metric structures for {\em doubling} metrics, and show that essentially any metric structure with distortion $1+\epsilon$ and size $s(|X|)$ has its terminal counterpart, with distortion $1+O(\epsilon)$ and size $s(|K|)+1$. In particular, for any doubling metric on $n$ points, a set of $k=o(n)$ terminals, and constant $0<\epsilon<1$, there exists:
(1) A spanner with stretch $1+\epsilon$ for pairs in $K\times X$, with $n+o(n)$ edges.
(2) A labeling scheme with stretch $1+\epsilon$ for pairs in $K\times X$, with label size $\approx \log k$.
(3) An embedding into $\ell_\infty^d$ with distortion $1+\epsilon$ for pairs in $K\times X$, where $d=O(\log k)$.
Moreover, surprisingly, the last two results apply if only $K$ is a doubling metric, while $X$ can be arbitrary.

[72]  arXiv:1802.07971 [pdf, other]
Title: Robustness of classifiers to uniform $\ell\_p$ and Gaussian noise
Journal-ref: 21st International Conference on Artificial Intelligence and Statistics (AISTATS) 2018, Apr 2018, Playa Blanca, Spain. 2018, \&\#x3008;http://www.aistats.org/\&\#x3009
Subjects: Learning (cs.LG); Computer Vision and Pattern Recognition (cs.CV); Machine Learning (stat.ML)

We study the robustness of classifiers to various kinds of random noise models. In particular, we consider noise drawn uniformly from the $\ell\_p$ ball for $p \in [1, \infty]$ and Gaussian noise with an arbitrary covariance matrix. We characterize this robustness to random noise in terms of the distance to the decision boundary of the classifier. This analysis applies to linear classifiers as well as classifiers with locally approximately flat decision boundaries, a condition which is satisfied by state-of-the-art deep neural networks. The predicted robustness is verified experimentally.

[73]  arXiv:1802.07974 [pdf]
Title: Evolution in complex objects
Authors: Mourad Oussalah
Subjects: Software Engineering (cs.SE)

This paper describes work carried out on a model for the evolution of graph classes in complex objects. By defining evolution rules and propagation strategies on graph classes, we aim to define a user-definable means to manage data evolution model which tackles the complex nature of the classes managed, using the concepts defined in object systems. So, depending on their needs and on those of the targeted application, designers can choose the evolution mechanism they consider to suit them best. They can either create new evolutions or reuse predefined ones to respond to a given need.

[74]  arXiv:1802.07975 [pdf, other]
Title: Options for encoding names for data linking at the Australian Bureau of Statistics
Comments: University of Melbourne Research Contract 85449779. After receiving a draft of this report, ABS conducted a further assessment of Options 2 and 3, which will be published on their website
Subjects: Cryptography and Security (cs.CR)

Publicly, ABS has said it would use a cryptographic hash function to convert names collected in the 2016 Census of Population and Housing into an unrecognisable value in a way that is not reversible. In 2016, the ABS engaged the University of Melbourne to provide expert advice on cryptographic hash functions to meet this objective.
For complex unit-record level data, including Census data, auxiliary data can be often be used to link individual records, even without names. This is the basis of ABS's existing bronze linking. This means that records can probably be re-identified without the encoded name anyway. Protection against re-identification depends on good processes within ABS.
The undertaking on the encoding of names should therefore be considered in the full context of auxiliary data and ABS processes. There are several reasonable interpretations:
1. That the encoding cannot be reversed except with a secret key held by ABS. This is the property achieved by encryption (Option 1), if properly implemented;
2. That the encoding, taken alone without auxiliary data, cannot be reversed to a single value. This is the property achieved by lossy encoding (Option 2), if properly implemented;
3. That the encoding doesn't make re-identification easier, or increase the number of records that can be re-identified, except with a secret key held by ABS. This is the property achieved by HMAC-based linkage key derivation using subsets of attributes (Option 3), if properly implemented.
We explain and compare the privacy and accuracy guarantees of five possible approaches. Options 4 and 5 investigate more sophisticated options for future data linking. We also explain how some commonly-advocated techniques can be reversed, and hence should not be used.

[75]  arXiv:1802.07980 [pdf, ps, other]
Title: Learning to Route with Sparse Trajectory Sets---Extended Version
Subjects: Learning (cs.LG)

Motivated by the increasing availability of vehicle trajectory data, we propose learn-to-route, a comprehensive trajectory-based routing solution. Specifically, we first construct a graph-like structure from trajectories as the routing infrastructure. Second, we enable trajectory-based routing given an arbitrary (source, destination) pair.
In the first step, given a road network and a collection of trajectories, we propose a trajectory-based clustering method that identifies regions in a road network. If a pair of regions are connected by trajectories, we maintain the paths used by these trajectories and learn a routing preference for travel between the regions. As trajectories are skewed and sparse, many region pairs are not connected by trajectories. We thus transfer routing preferences from region pairs with sufficient trajectories to such region pairs and then use the transferred preferences to identify paths between the regions. In the second step, we exploit the above graph-like structure to achieve a comprehensive trajectory-based routing solution. Empirical studies with two substantial trajectory data sets offer insight into the proposed solution, indicating that it is practical. A comparison with a leading routing service offers evidence that the paper's proposal is able to enhance routing quality.
This is an extended version of "Learning to Route with Sparse Trajectory Sets" [1], to appear in IEEE ICDE 2018.

[76]  arXiv:1802.07982 [pdf]
Title: Shared Services Center for E-Government Policy
Comments: Proceedings of eGov-Interop'05 Conference 23-24 February 2005, Geneva (Switzerland)
Subjects: Software Engineering (cs.SE)

It is a general opinion that applicative cooperation represents a useful vehicle for the development of e-government. At the architectural level, solutions for applicative cooperation are quite stable, but organizational and methodological problems prevent the expected and needed development of cooperation among different administrations. Moreover, the introduction of the digital government requires a considerable involvement of resources that can be unsustainable for small public administrations. This work shows how the above mentioned problems can be (partially) solved with the introduction of a Shared Services Center (SSC).

[77]  arXiv:1802.07983 [pdf, other]
Title: Tapir: Automation Support of Exploratory Testing Using Model Reconstruction of the System Under Test
Subjects: Software Engineering (cs.SE)

For a considerable number of software projects, the creation of effective test cases is hindered by design documentation that is either lacking, incomplete or obsolete. The exploratory testing approach can serve as a sound method in such situations. However, the efficiency of this testing approach strongly depends on the method, the documentation of explored parts of a system, the organization and distribution of work among individual testers on a team, and the minimization of potential (very probable) duplicities in performed tests. In this paper, we present a framework for replacing and automating a portion of these tasks. A screen-flow-based model of the tested system is incrementally reconstructed during the exploratory testing process by tracking testers' activities. With additional metadata, the model serves for an automated navigation process for a tester. Compared with the exploratory testing approach, which is manually performed in two case studies, the proposed framework allows the testers to explore a greater extent of the tested system and enables greater detection of the defects present in the system. The results show that the time efficiency of the testing process improved with framework support. This efficiency can be increased by team-based navigational strategies that are implemented within the proposed framework, which is documented by another case study presented in this paper.

[78]  arXiv:1802.07997 [pdf, other]
Title: Generating High-Quality Query Suggestion Candidates for Task-Based Search
Comments: Advances in Information Retrieval. Proceedings of the 40th European Conference on Information Retrieval (ECIR '18), 2018
Subjects: Information Retrieval (cs.IR); Artificial Intelligence (cs.AI); Computation and Language (cs.CL)

We address the task of generating query suggestions for task-based search. The current state of the art relies heavily on suggestions provided by a major search engine. In this paper, we solve the task without reliance on search engines. Specifically, we focus on the first step of a two-stage pipeline approach, which is dedicated to the generation of query suggestion candidates. We present three methods for generating candidate suggestions and apply them on multiple information sources. Using a purpose-built test collection, we find that these methods are able to generate high-quality suggestion candidates.

[79]  arXiv:1802.08005 [pdf, other]
Title: Employment of Multiple Algorithms for Optimal Path-based Test Selection Strategy
Subjects: Software Engineering (cs.SE)

Executing various sequences of system functions in a system under test represents one of the primary techniques in software testing. The natural way to create effective, consistent and efficient test sequences is to model the system under test and employ an algorithm to generate the tests that satisfy a defined test coverage criterion. Several criteria of test set optimality can be defined. In addition, to optimize the test set from an economic viewpoint, the priorities of the various parts of the system model under test must be defined. Using this prioritization, the test cases exercise the high priority parts of the system under test more intensely than those with low priority. Evidence from the literature and our observations confirm that finding a universal algorithm that produces an optimal test set for all test coverage and test set optimality criteria is a challenging task. Moreover, for different individual problem instances, different algorithms provide optimal results. In this paper, we present a path-based strategy to perform optimal test selection. The strategy first employs a set of current algorithms to generate test sets; then, it assesses the optimality of each test set by the selected criteria, and finally, chooses the optimal test set. The experimental results confirm the validity and usefulness of this strategy. For individual instances of 50 system under test models, different algorithms provided optimal results; these results varied by the required test coverage level, the size of the priority parts of the model, and the selected test set optimality criteria.

[80]  arXiv:1802.08008 [pdf, other]
Title: Sounderfeit: Cloning a Physical Model with Conditional Adversarial Autoencoders
Authors: Stephen Sinclair
Comments: Published in the Brazilian Symposium on Computer Music (SBCM 2017)
Journal-ref: Proc. Brazilian Symp. on Comp. Music., 2017. p. 67--74
Subjects: Sound (cs.SD); Learning (cs.LG); Audio and Speech Processing (eess.AS)

An adversarial autoencoder conditioned on known parameters of a physical modeling bowed string synthesizer is evaluated for use in parameter estimation and resynthesis tasks. Latent dimensions are provided to capture variance not explained by the conditional parameters. Results are compared with and without the adversarial training, and a system capable of "copying" a given parameter-signal bidirectional relationship is examined. A real-time synthesis system built on a generative, conditioned and regularized neural network is presented, allowing to construct engaging sound synthesizers based purely on recorded data.

[81]  arXiv:1802.08009 [pdf, ps, other]
Title: Iterate averaging as regularization for stochastic gradient descent
Subjects: Learning (cs.LG); Machine Learning (stat.ML)

We propose and analyze a variant of the classic Polyak-Ruppert averaging scheme, broadly used in stochastic gradient methods. Rather than a uniform average of the iterates, we consider a weighted average, with weights decaying in a geometric fashion. In the context of linear least squares regression, we show that this averaging scheme has a the same regularizing effect, and indeed is asymptotically equivalent, to ridge regression. In particular, we derive finite-sample bounds for the proposed approach that match the best known results for regularized stochastic gradient methods.

[82]  arXiv:1802.08010 [pdf, other]
Title: Towards an Understanding of Entity-Oriented Search Intents
Comments: Advances in Information Retrieval. Proceedings of the 40th European Conference on Information Retrieval (ECIR '18), 2018
Subjects: Information Retrieval (cs.IR); Artificial Intelligence (cs.AI); Computation and Language (cs.CL)

Entity-oriented search deals with a wide variety of information needs, from displaying direct answers to interacting with services. In this work, we aim to understand what are prominent entity-oriented search intents and how they can be fulfilled. We develop a scheme of entity intent categories, and use them to annotate a sample of queries. Specifically, we annotate unique query refiners on the level of entity types. We observe that, on average, over half of those refiners seek to interact with a service, while over a quarter of the refiners search for information that may be looked up in a knowledge base.

[83]  arXiv:1802.08013 [pdf, other]
Title: Intrinsic Motivation and Mental Replay enable Efficient Online Adaptation in Stochastic Recurrent Networks
Comments: Preprint submitted to Neural Networks
Subjects: Artificial Intelligence (cs.AI); Learning (cs.LG); Robotics (cs.RO); Machine Learning (stat.ML)

Autonomous robots need to interact with unknown, unstructured and changing environments, constantly facing novel challenges. Therefore, continuous online adaptation for lifelong-learning and the need of sample-efficient mechanisms to adapt to changes in the environment, the constraints, the tasks, or the robot itself are crucial. In this work, we propose a novel framework for probabilistic online motion planning with online adaptation based on a bio-inspired stochastic recurrent neural network. By using learning signals which mimic the intrinsic motivation signal cognitive dissonance in addition with a mental replay strategy to intensify experiences, the stochastic recurrent network can learn from few physical interactions and adapts to novel environments in seconds. We evaluate our online planning and adaptation framework on an anthropomorphic KUKA LWR arm. The rapid online adaptation is shown by learning unknown workspace constraints sample-efficiently from few physical interactions while following given via points.

[84]  arXiv:1802.08014 [pdf, ps, other]
Title: Finding Top-k Optimal Sequenced Routes -- Full Version
Subjects: Databases (cs.DB); Data Structures and Algorithms (cs.DS)

Motivated by many practical applications in logistics and mobility-as-a-service, we study the top-k optimal sequenced routes (KOSR) querying on large, general graphs where the edge weights may not satisfy the triangle inequality, e.g., road network graphs with travel times as edge weights. The KOSR querying strives to find the top-k optimal routes (i.e., with the top-k minimal total costs) from a given source to a given destination, which must visit a number of vertices with specific vertex categories (e.g., gas stations, restaurants, and shopping malls) in a particular order (e.g., visiting gas stations before restaurants and then shopping malls).
To efficiently find the top-k optimal sequenced routes, we propose two algorithms PruningKOSR and StarKOSR. In PruningKOSR, we define a dominance relationship between two partially-explored routes. The partially-explored routes that can be dominated by other partially-explored routes are postponed being extended, which leads to a smaller searching space and thus improves efficiency. In StarKOSR, we further improve the efficiency by extending routes in an A* manner. With the help of a judiciously designed heuristic estimation that works for general graphs, the cost of partially explored routes to the destination can be estimated such that the qualified complete routes can be found early. In addition, we demonstrate the high extensibility of the proposed algorithms by incorporating Hop Labeling, an effective label indexing technique for shortest path queries, to further improve efficiency. Extensive experiments on multiple real-world graphs demonstrate that the proposed methods significantly outperform the baseline method. Furthermore, when k=1, StarKOSR also outperforms the state-of-the-art method for the optimal sequenced route queries.

[85]  arXiv:1802.08020 [pdf, ps, other]
Title: On Rational Delegations in Liquid Democracy
Subjects: Multiagent Systems (cs.MA); Computer Science and Game Theory (cs.GT)

Liquid democracy is a proxy voting method where proxies are delegable. We propose and study a game-theoretic model of liquid democracy to address the following question: when is it rational for a voter to delegate her vote? We study the existence of pure-strategy Nash equilibria in this model, and how group accuracy is affected by them. We complement these results by means of simulations to study the effect of network structures on group's accuracy, and various aspects of the patterns of delegations that emerge in this type of interaction.

[86]  arXiv:1802.08021 [pdf, other]
Title: SparCML: High-Performance Sparse Communication for Machine Learning
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC); Machine Learning (stat.ML)

One of the main drivers behind the rapid recent advances in machine learning has been the availability of efficient system support. This comes both through hardware acceleration, but also in the form of efficient software frameworks and programming models. Despite significant progress, scaling compute-intensive machine learning workloads to a large number of compute nodes is still a challenging task, with significant latency and bandwidth demands. In this paper, we address this challenge, by proposing SPARCML, a general, scalable communication layer for machine learning applications. SPARCML is built on the observation that many distributed machine learning algorithms either have naturally sparse communication patters, or have updates which can be sparsified in a structured way for improved performance, without any convergence or accuracy loss. To exploit this insight, we design and implement a set of communication efficient protocols for sparse input data, in conjunction with efficient machine learning algorithms which can leverage these primitives. Our communication protocols generalize standard collective operations, by allowing processes to contribute sparse input data vectors, of heterogeneous sizes. We call these operations sparse-input collectives, and present efficient practical algorithms with strong theoretical bounds on their running time and communication cost. Our generic communication layer is enriched with additional features, such support for non-blocking (asynchronous) operations, and support for low-precision data representations. We validate our algorithmic results experimentally on a range of large-scale machine learning applications and target architectures, showing that we can leverage sparsity for order- of-magnitude runtime savings, compared to state-of-the art methods and frameworks.

[87]  arXiv:1802.08022 [pdf, other]
Title: Equalizer 2.0 - Convergence of a Parallel Rendering Framework
Subjects: Graphics (cs.GR)

Developing complex, real world graphics applications which leverage multiple GPUs and computers for interactive 3D rendering tasks is a complex task. It requires expertise in distributed systems and parallel rendering in addition to the application domain itself. We present a mature parallel rendering framework which provides a large set of features, algorithms and system integration for a wide range of real-world research and industry applications. Using the Equalizer parallel rendering framework, we show how a wide set of generic algorithms can be integrated in the framework to help application scalability and development in many different domains, highlighting how concrete applications benefit from the diverse aspects and use cases of Equalizer. We present novel parallel rendering algorithms, powerful abstractions for large visualization setups and virtual reality, as well as new experimental results for parallel rendering and data distribution.

[88]  arXiv:1802.08023 [pdf, other]
Title: The Best of Both Worlds: Asymptotically Efficient Mechanisms with a Guarantee on the Expected Gains-From-Trade
Subjects: Computer Science and Game Theory (cs.GT)

The seminal impossibility result of Myerson and Satterthwaite (1983) states that for bilateral trade, there is no mechanism that is individually rational (IR), incentive compatible (IC), weakly budget balanced, and efficient. This has led follow-up work on two-sided trade settings to weaken the efficiency requirement and consider approximately efficient simple mechanisms, while still demanding the other properties. The current state-of-the-art of such mechanisms for two-sided markets can be categorized as giving one (but not both) of the following two types of approximation guarantees on the gains from trade: a constant ex-ante guarantee, measured with respect to the second-best efficiency benchmark, or an asymptotically optimal ex-post guarantee, measured with respect to the first-best efficiency benchmark. Here the second-best efficiency benchmark refers to the highest gains from trade attainable by any IR, IC and weakly budget balanced mechanism, while the first-best efficiency benchmark refers to the maximum gains from trade (attainable by the VCG mechanism, which is not weakly budget balanced).
In this paper, we construct simple mechanisms for double-auction and matching markets that simultaneously achieve both types of guarantees: these are ex-post IR, Bayesian IC, and ex-post weakly budget balanced mechanisms that 1) ex-ante guarantee a constant fraction of the gains from trade of the second-best, and 2) ex-post guarantee a realization-dependent fraction of the gains from trade of the first-best, such that this realization-dependent fraction converges to 1 (full efficiency) as the market grows large.

[89]  arXiv:1802.08026 [pdf, other]
Title: Complex-valued Neural Networks with Non-parametric Activation Functions
Comments: Submitted to IEEE Transactions on Emerging Topics in Computational Intelligence
Subjects: Neural and Evolutionary Computing (cs.NE)

Complex-valued neural networks (CVNNs) are a powerful modeling tool for domains where data can be naturally interpreted in terms of complex numbers. However, several analytical properties of the complex domain (e.g., holomorphicity) make the design of CVNNs a more challenging task than their real counterpart. In this paper, we consider the problem of flexible activation functions (AFs) in the complex domain, i.e., AFs endowed with sufficient degrees of freedom to adapt their shape given the training data. While this problem has received considerable attention in the real case, a very limited literature exists for CVNNs, where most activation functions are generally developed in a split fashion (i.e., by considering the real and imaginary parts of the activation separately) or with simple phase-amplitude techniques. Leveraging over the recently proposed kernel activation functions (KAFs), and related advances in the design of complex-valued kernels, we propose the first fully complex, non-parametric activation function for CVNNs, which is based on a kernel expansion with a fixed dictionary that can be implemented efficiently on vectorized hardware. Several experiments on common use cases, including prediction and channel equalization, validate our proposal when compared to real-valued neural networks and CVNNs with fixed activation functions.

[90]  arXiv:1802.08037 [pdf, other]
Title: Are Two (Samples) Really Better Than One? On the Non-Asymptotic Performance of Empirical Revenue Maximization
Subjects: Computer Science and Game Theory (cs.GT)

The literature on "mechanism design from samples," which has flourished in recent years at the interface of economics and computer science, offers a bridge between the classic computer-science approach of worst-case analysis (corresponding to "no samples") and the classic economic approach of average-case analysis for a given Bayesian prior (conceptually corresponding to the number of samples tending to infinity). Nonetheless, the two directions studied so far are two extreme and almost diametrically opposed directions: that of asymptotic results where the number of samples grows large, and that where only a single sample is available. In this paper, we take a first step toward understanding the middle ground that bridges these two approaches: that of a fixed number of samples greater than one. In a variety of contexts, we ask what is possibly the most fundamental question in this direction: "are two samples really better than one sample?". We present a few surprising negative result, and complement them with our main result: showing that the worst-case, over all regular distributions, expected-revenue guarantee of the Empirical Revenue Maximization algorithm given two samples is greater than that of this algorithm given one sample. The proof is technically challenging, and provides the first result that shows that some deterministic mechanism constructed using two samples can guarantee more than one half of the optimal revenue.

[91]  arXiv:1802.08039 [pdf]
Title: Comparative analysis of SVIT and Skype features in e-Learning process
Comments: in Russian
Subjects: Computers and Society (cs.CY)

The article discusses capabilities of the SVIT and Skype programs in terms of use in e-Learning process. Also various types of connections, image and sound quality were investigated.

[92]  arXiv:1802.08040 [pdf, other]
Title: Inverse analysis of traction-separation relationship based on sequentially linear approach
Subjects: Computational Engineering, Finance, and Science (cs.CE)

Traction-separation relationship is an important material characteristic describing the fracture behaviour of quasi-brittle solids. A new numerical scheme for identification of the traction-separation relation by inverse analysis of data obtained from various types of fracture tests is proposed. Due to employing the concept of sequentially linear analysis, the method exhibits a superior numerical stability and versatility. The applicability and effectiveness of the proposed method is demonstrated on examples involving identification of the traction-separation relationship using experimental data from various test configurations.

[93]  arXiv:1802.08047 [pdf, other]
Title: When Renewable Energy Meets Building Thermal Mass: A Real-time Load Management Scheme
Subjects: Systems and Control (cs.SY)

We consider the optimal power management in renewable driven smart building MicroGrid under noise corrupted conditions as a stochastic optimization problem. We first propose our user satisfaction and electricity consumption balanced (USECB) profit model as the objective for optimal power management. We then cast the problem in noise corrupted conditions into the class of expectation maximizing in stochastic optimization problem with convex constraints. For this task, we design a Bregemen projection based mirror decent algorithm as an approximation solution to our stochastic optimization problem. Convergence and upper-bound of our algorithm with proof are also provided in our paper. We then conduct a broad type of experiment in our simulation to test the justification of our model as well as the effectiveness of our algorithm.

[94]  arXiv:1802.08052 [pdf]
Title: Data Consistency Simulation Tool for NoSQL Database Systems
Authors: Nazim Faour
Subjects: Databases (cs.DB)

Various data consistency levels have an important part in the integrity of data and also affect performance especially the data that is replicated many times across or over the cluster. Based on BASE and the theorem of CAP tradeoffs, most systems of NoSQL have more relaxed consistency guarantees than another kind of databases which implement ACID. Most systems of NoSQL gave different methods to adjust a required level of consistency to ensure the minimal numbering of the replicas accepted in each operation. Simulations are always depending on a simplified model and ignore many details and facts about the real system. Therefore, a simulation can only work as an estimation or an explanation vehicle for observed behavior. So to create simulation tool, I have to characterize a model, identify influence factors and simply implement that depending on a (modeled) workload. In this paper, I have a model of simulation to measure the consistency of the data and to detect the data consistency violations in simulated network partition settings. So workloads are needed with the set of users who make requests and then put the results for analysis.

[95]  arXiv:1802.08054 [pdf, other]
Title: VBALD - Variational Bayesian Approximation of Log Determinants
Subjects: Learning (cs.LG); Information Theory (cs.IT)

Evaluating the log determinant of a positive definite matrix is ubiquitous in machine learning. Applications thereof range from Gaussian processes, minimum-volume ellipsoids, metric learning, kernel learning, Bayesian neural networks, Determinental Point Processes, Markov random fields to partition functions of discrete graphical models. In order to avoid the canonical, yet prohibitive, Cholesky $\mathcal{O}(n^{3})$ computational cost, we propose a novel approach, with complexity $\mathcal{O}(n^{2})$, based on a constrained variational Bayes algorithm. We compare our method to Taylor, Chebyshev and Lanczos approaches and show state of the art performance on both synthetic and real-world datasets.

[96]  arXiv:1802.08055 [pdf, other]
Title: A Learning Based Approach for Uncertainty Analysis in Numerical Weather Prediction Models
Comments: 23 pages, 5 figures, 4 tables
Subjects: Numerical Analysis (cs.NA); Atmospheric and Oceanic Physics (physics.ao-ph)

Complex numerical weather prediction models incorporate a variety of physical processes, each described by multiple alternative physical schemes with specific parameters. The selection of the physical schemes and the choice of the corresponding physical parameters during model configuration can significantly impact the accuracy of model forecasts. There is no combination of physical schemes that works best for all times, at all locations, and under all conditions. It is therefore of considerable interest to understand the interplay between the choice of physics and the accuracy of the resulting forecasts under different conditions. This paper demonstrates the use of machine learning techniques to study the uncertainty in numerical weather prediction models due to the interaction of multiple physical processes. The first problem addressed herein is the estimation of systematic model errors in output quantities of interest at future times, and the use of this information to improve the model forecasts. The second problem considered is the identification of those specific physical processes that contribute most to the forecast uncertainty in the quantity of interest under specified meteorological conditions.
The discrepancies between model results and observations at past times are used to learn the relationships between the choice of physical processes and the resulting forecast errors. Numerical experiments are carried out with the Weather Research and Forecasting (WRF) model. The output quantity of interest is the model precipitation, a variable that is both extremely important and very challenging to forecast. The physical processes under consideration include various micro-physics schemes, cumulus parameterizations, short wave, and long wave radiation schemes. The experiments demonstrate the strong potential of machine learning approaches to aid the study of model errors.

[97]  arXiv:1802.08057 [pdf, other]
Title: MagnifyMe: Aiding Cross Resolution Face Recognition via Identity Aware Synthesis
Subjects: Computer Vision and Pattern Recognition (cs.CV)

Enhancing low resolution images via super-resolution or image synthesis for cross-resolution face recognition has been well studied. Several image processing and machine learning paradigms have been explored for addressing the same. In this research, we propose Synthesis via Deep Sparse Representation algorithm for synthesizing a high resolution face image from a low resolution input image. The proposed algorithm learns multi-level sparse representation for both high and low resolution gallery images, along with an identity aware dictionary and a transformation function between the two representations for face identification scenarios. With low resolution test data as input, the high resolution test image is synthesized using the identity aware dictionary and transformation which is then used for face recognition. The performance of the proposed SDSR algorithm is evaluated on four databases, including one real world dataset. Experimental results and comparison with existing seven algorithms demonstrate the efficacy of the proposed algorithm in terms of both face identification and image quality measures.

[98]  arXiv:1802.08064 [pdf, ps, other]
Title: Computing the concurrency threshold of sound free-choice workflow nets
Subjects: Logic in Computer Science (cs.LO)

Workflow graphs extend classical flow charts with concurrent fork and join nodes. They constitute the core of business processing languages such as BPMN or UML Activity Diagrams. The activities of a workflow graph are executed by humans or machines, generically called resources. If concurrent activities cannot be executed in parallel by lack of resources, the time needed to execute the workflow increases. We study the problem of computing the minimal number of resources necessary to fully exploit the concurrency of a given workflow, and execute it as fast as possible (i.e., as fast as with unlimited resources).
We model this problem using free-choice Petri nets, which are known to be equivalent to workflow graphs. We analyze the computational complexity of two versions of the problem: computing the resource and concurrency thresholds. We use the results to design an algorithm to approximate the concurrency threshold, and evaluate it on a benchmark suite of 642 industrial examples. We show that it performs very well in practice: It always provides the exact value, and never takes more than 30 milliseconds for any workflow, even for those with a huge number of reachable markings.

[99]  arXiv:1802.08066 [pdf, other]
Title: Reputation Systems for News on Twitter: A Large-Scale Study
Subjects: Social and Information Networks (cs.SI)

Social networks offer a ready channel for fake and misleading news to spread and exert influence. This paper examines the performance of different reputation algorithms when applied to a large and statistically significant portion of the news that are spread via Twitter. Our main result is that simple algorithms based on the identity of the users spreading the news, as well as the words appearing in the titles and descriptions of the linked articles, are able to identify a large portion of fake or misleading news, while incurring only very low (<1%) false positive rates for mainstream websites. We believe that these algorithms can be used as the basis of practical, large-scale systems for indicating to consumers which news sites deserve careful scrutiny and skepticism.

[100]  arXiv:1802.08068 [pdf, other]
Title: Learning Hyperedge Replacement Grammars for Graph Generation
Comments: 27 pages, accepted at IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI). arXiv admin note: substantial text overlap with arXiv:1608.03192
Subjects: Social and Information Networks (cs.SI); Formal Languages and Automata Theory (cs.FL)

The discovery and analysis of network patterns are central to the scientific enterprise. In the present work, we developed and evaluated a new approach that learns the building blocks of graphs that can be used to understand and generate new realistic graphs. Our key insight is that a graph's clique tree encodes robust and precise information. We show that a Hyperedge Replacement Grammar (HRG) can be extracted from the clique tree, and we develop a fixed-size graph generation algorithm that can be used to produce new graphs of a specified size. In experiments on large real-world graphs, we show that graphs generated from the HRG approach exhibit a diverse range of properties that are similar to those found in the original networks. In addition to graph properties like degree or eigenvector centrality, what a graph "looks like" ultimately depends on small details in local graph substructures that are difficult to define at a global level. We show that the HRG model can also preserve these local substructures when generating new graphs.

[101]  arXiv:1802.08070 [pdf, ps, other]
Title: A New Foundation for Finitary Corecursion and Iterative Algebras
Comments: arXiv admin note: substantial text overlap with arXiv:1601.01532
Subjects: Logic in Computer Science (cs.LO)

This paper contributes to a theory of the behaviour of "finite-state" systems that is generic in the system type. We propose that such systems are modeled as coalgebras with a finitely generated carrier for an endofunctor on a locally finitely presentable category. Their behaviour gives rise to a new fixpoint of the coalgebraic type functor called locally finite fixpoint (LFF). We prove that if the given endofunctor preserves monomorphisms then the LFF always exists and is a subcoalgebra of the final coalgebra (unlike the rational fixpoint previously studied by Ad\'amek, Milius, and Velebil). Moreover, we show that the LFF is characterized by two universal properties: (1) as the final locally finitely generated coalgebra, and (2) as the initial fg-iterative algebra. As instances of the LFF we first obtain the known instances of the rational fixpoint, e.g. regular languages, rational streams and formal power-series, regular trees etc. And we obtain a number of new examples, e.g. (realtime deterministic resp. non-deterministic) context-free languages, constructively S-algebraic formal power-series (and any other instance of the generalized powerset construction by Silva, Bonchi, Bonsangue, and Rutten) and the monad of Courcelle's algebraic trees.

[102]  arXiv:1802.08077 [pdf, other]
Title: Discriminative Label Consistent Domain Adaptation
Comments: 12 pages, 7 figures. arXiv admin note: text overlap with arXiv:1712.10042
Subjects: Computer Vision and Pattern Recognition (cs.CV)

Domain adaptation (DA) is transfer learning which aims to learn an effective predictor on target data from source data despite data distribution mismatch between source and target. We present in this paper a novel unsupervised DA method for cross-domain visual recognition which simultaneously optimizes the three terms of a theoretically established error bound. Specifically, the proposed DA method iteratively searches a latent shared feature subspace where not only the divergence of data distributions between the source domain and the target domain is decreased as most state-of-the-art DA methods do, but also the inter-class distances are increased to facilitate discriminative learning. Moreover, the proposed DA method sparsely regresses class labels from the features achieved in the shared subspace while minimizing the prediction errors on the source data and ensuring label consistency between source and target. Data outliers are also accounted for to further avoid negative knowledge transfer. Comprehensive experiments and in-depth analysis verify the effectiveness of the proposed DA method which consistently outperforms the state-of-the-art DA methods on standard DA benchmarks, i.e., 12 cross-domain image classification tasks.

[103]  arXiv:1802.08080 [pdf, other]
Title: Classification of Breast Cancer Histology using Deep Learning
Comments: 8 pages. Submitted to the ICIAR 2018 conference
Subjects: Computer Vision and Pattern Recognition (cs.CV)

Breast Cancer is a major cause of death worldwide among women. Hematoxylin and Eosin (H&E) stained breast tissue samples from biopsies are observed under microscopes for the primary diagnosis of breast cancer. In this paper, we propose a deep learning-based method for classification of H&E stained breast tissue images released for BACH challenge 2018 by fine-tuning Inception-v3 convolutional neural network (CNN) proposed by Szegedy et al. These images are to be classified into four classes namely, i) normal tissue, ii) benign tumor, iii) in-situ carcinoma and iv) invasive carcinoma. Our strategy is to extract patches based on nuclei density instead of random or grid sampling, along with rejection of patches that are not rich in nuclei (non-epithelial) regions for training and testing. Every patch (nuclei-dense region) in an image is classified in one of the four above mentioned categories. The class of the entire image is determined using majority voting over the nuclear classes. We obtained an average four class accuracy of 85% and an average two class (non-cancer vs. carcinoma) accuracy of 93%, which improves upon a previous benchmark by Araujo et al.

[104]  arXiv:1802.08091 [pdf, other]
Title: Deep Online Video Stabilization
Comments: 8 pages
Subjects: Graphics (cs.GR)

Video stabilization technique is essential for most hand-held captured videos due to high-frequency shakes. Several 2D-, 2.5D- and 3D-based stabilization techniques are well studied, but to our knowledge, no solutions based on deep neural networks had been proposed. The reason for this is mostly the shortage of training data, as well as the challenge of modeling the problem using neural networks. In this paper, we solve the video stabilization problem using a convolutional neural network (ConvNet). Instead of dealing with offline holistic camera path smoothing based on feature matching, we focus on low-latency real-time camera path smoothing without explicitly representing the camera path. Our network, called StabNet, learns a transformation for each input unsteady frame progressively along the time-line, while creating a more stable latent camera path. To train the network, we create a dataset of synchronized steady/unsteady video pairs via a well designed hand-held hardware. Experimental results shows that the proposed online method (without using future frames) performs comparatively to traditional offline video stabilization methods, while running about 30 times faster. Further, the proposed StabNet is able to handle night-time and blurry videos, where existing methods fail in robust feature matching.

[105]  arXiv:1802.08102 [pdf, other]
Title: Understanding the Performance of Ceph Block Storage for Hyper-Converged Cloud with All Flash Storage
Authors: Moo-Ryong Ra (AT&T Labs Research)
Comments: 9 pages, 11 figures
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC)

Hyper-converged cloud refers to an architecture that an operator runs compute and storage services on the same set of physical servers. Although the hyper-converged design comes with a number of benefits, it makes crucial operational tasks, such as capacity planning and cost analysis, fairly complicated. The problem becomes more onerous if we consider a complex distributed system, such as Ceph, for the cloud with the proliferation of SSD drives. In this paper, we aim to answer some of these questions based on comprehensive microbenchmarks, and consequently better understand the behavior of Ceph in a hyper-converged cloud with all-flash storage. We reported our findings based on the study, devised a cost model and compared the cost of hyper-converged architecture with dedicated storage architecture. Additionally we summarized our experience based on the interactions with many teams at AT&T in the past couple of years.

[106]  arXiv:1802.08112 [pdf, ps, other]
Title: Rational consumer decisions in a peak time rebate program
Journal-ref: Vuelvas, J., & Ruiz, F. (2017). Rational consumer decisions in a peak time rebate program. Electric Power Systems Research, 143. https://doi.org/10.1016/j.epsr.2016.11.001
Subjects: Systems and Control (cs.SY)

A rational behavior of a consumer is analyzed when the user participates in a Peak Time Rebate (PTR) mechanism, which is a demand response (DR) incentive program based on a baseline. A multi-stage stochastic programming is proposed from the demand side in order to understand the rational decisions. The consumer preferences are modeled as a risk-averse function under additive uncertainty. The user chooses the optimal consumption profile to maximize his economic benefits for each period. The stochastic optimization problem is solved backward in time. A particular situation is developed when the System Operator (SO) uses consumption of the previous interval as the household-specific baseline for the DR program. It is found that a rational consumer alters the baseline in order to increase the well-being when there is an economic incentive. As results, whether the incentive is lower than the retail price, the user shifts his load requirement to the baseline setting period. On the other hand, if the incentive is greater than the regular energy price, the optimal decision is that the user spends the maximum possible energy in the baseline setting period and reduces the consumption at the PTR time. This consumer behavior produces more energy consumption in total considering all periods. In addition, the user with high uncertainty level in his energy pattern should spend less energy than a predictable consumer when the incentive is lower than the retail price.

[107]  arXiv:1802.08115 [pdf, other]
Title: Novel differential quadrature element method for higher order strain gradient elasticity theory
Comments: arXiv admin note: text overlap with arXiv:1802.05541
Subjects: Computational Engineering, Finance, and Science (cs.CE)

In this paper, we propose a novel and efficient differential quadrature element based on Lagrange interpolation to solve a sixth order partial differential equations encountered in non-classical beam theories. These non-classical theories render displacement, slope and curvature as degrees of freedom for an Euler-Bernoulli beam. A generalize scheme is presented herein to implementation the multi-degrees degrees of freedom associated with these non-classical theories in a simplified and efficient way. The proposed element has displacement as the only degree of freedom in the domain, whereas, at the boundaries it has displacement, slope and curvature. Further, we extend this methodology and formulate two novel versions of plate element for gradient elasticity theory. In the first version, Lagrange interpolation is assumed in $x$ and $y$ directions and the second version is based on mixed interpolation, with Lagrange interpolation in $x$ direction and Hermite interpolation in $y$ direction. The procedure to compute the modified weighting coefficients by incorporating the classical and non-classical boundary conditions is explained. The efficiency of the proposed elements is demonstrated through numerical examples on static analysis of gradient elastic beams and plates for different boundary conditions.

[108]  arXiv:1802.08122 [pdf, other]
Title: Harmonious Attention Network for Person Re-Identification
Comments: Accepted in CVPR 2018
Subjects: Computer Vision and Pattern Recognition (cs.CV)

Existing person re-identification (re-id) methods either assume the availability of well-aligned person bounding box images as model input or rely on constrained attention selection mechanisms to calibrate misaligned images. They are therefore sub-optimal for re-id matching in arbitrarily aligned person images potentially with large human pose variations and unconstrained auto-detection errors. In this work, we show the advantages of jointly learning attention selection and feature representation in a Convolutional Neural Network (CNN) by maximising the complementary information of different levels of visual attention subject to re-id discriminative learning constraints. Specifically, we formulate a novel Harmonious Attention CNN (HA-CNN) model for joint learning of soft pixel attention and hard regional attention along with simultaneous optimisation of feature representations, dedicated to optimise person re-id in uncontrolled (misaligned) images. Extensive comparative evaluations validate the superiority of this new HA-CNN model for person re-id over a wide variety of state-of-the-art methods on three large-scale benchmarks including CUHK03, Market-1501, and DukeMTMC-ReID.

[109]  arXiv:1802.08129 [pdf, other]
Title: Multimodal Explanations: Justifying Decisions and Pointing to the Evidence
Comments: arXiv admin note: text overlap with arXiv:1612.04757
Subjects: Artificial Intelligence (cs.AI); Computation and Language (cs.CL); Computer Vision and Pattern Recognition (cs.CV)

Deep models that are both effective and explainable are desirable in many settings; prior explainable models have been unimodal, offering either image-based visualization of attention weights or text-based generation of post-hoc justifications. We propose a multimodal approach to explanation, and argue that the two modalities provide complementary explanatory strengths. We collect two new datasets to define and evaluate this task, and propose a novel model which can provide joint textual rationale generation and attention visualization. Our datasets define visual and textual justifications of a classification decision for activity recognition tasks (ACT-X) and for visual question answering tasks (VQA-X). We quantitatively show that training with the textual explanations not only yields better textual justification models, but also better localizes the evidence that supports the decision. We also qualitatively show cases where visual explanation is more insightful than textual explanation, and vice versa, supporting our thesis that multimodal explanation models offer significant benefits over unimodal approaches.

[110]  arXiv:1802.08130 [pdf, ps, other]
Title: A novel incentive-based demand response model for Cournot competition in electricity markets
Journal-ref: Vuelvas, J. & Ruiz, F. Energy Syst (2018). https://doi.org/10.1007/s12667-018-0271-2
Subjects: Computer Science and Game Theory (cs.GT)

This paper presents an analysis of competition between generators when incentive-based demand response is employed in an electricity market. Thermal and hydropower generation are considered in the model. A smooth inverse demand function is designed using a sigmoid and two linear functions for modeling the consumer preferences under incentive-based demand response program. Generators compete to sell energy bilaterally to consumers and system operator provides transmission and arbitrage services. The profit of each agent is posed as an optimization problem, then the competition result is found by solving simultaneously Karush-Kuhn-Tucker conditions for all generators. A Nash-Cournot equilibrium is found when the system operates normally and at peak demand times when DR is required. Under this model, results show that DR diminishes the energy consumption at peak periods, shifts the power requirement to off-peak times and improves the net consumer surplus due to incentives received for participating in DR program. However, the generators decrease their profit due to the reduction of traded energy and market prices.

[111]  arXiv:1802.08138 [pdf, other]
Title: Reliable Intersection Control in Non-cooperative Environments
Comments: Extended version (including proofs of theorems and lemmas) of the paper: M. O. Sayin, C.-W. Lin, S. Shiraishi, and T. Basar, "Reliable intersection control in non-cooperative environments", to appear in the Proceedings of American Control Conference, 2018
Subjects: Artificial Intelligence (cs.AI); Computer Science and Game Theory (cs.GT); Systems and Control (cs.SY)

We propose a reliable intersection control mechanism for strategic autonomous and connected vehicles (agents) in non-cooperative environments. Each agent has access to his/her earliest possible and desired passing times, and reports a passing time to the intersection manager, who allocates the intersection temporally to the agents in a First-Come-First-Serve basis. However, the agents might have conflicting interests and can take actions strategically. To this end, we analyze the strategic behaviors of the agents and formulate Nash equilibria for all possible scenarios. Furthermore, among all Nash equilibria we identify a socially optimal equilibrium that leads to a fair intersection allocation, and correspondingly we describe a strategy-proof intersection mechanism, which achieves reliable intersection control such that the strategic agents do not have any incentive to misreport their passing times strategically.

[112]  arXiv:1802.08141 [pdf]
Title: Connecting KOSs and the LOD Cloud
Comments: accepted for the 15th INTERNATIONAL ISKO CONFERENCE, Porto, Portugal, 9 to 11 July 2018, this http URL
Subjects: Digital Libraries (cs.DL)

This paper describes a specific project, the current situation leading to it, its project design and first results. In particular, we will examine the terminology employed in the Linked Open Data cloud and compare this to the terminology employed in both the Universal Decimal Classification and the Basic Concepts Classification. We will explore whether these classifications can encourage greater consistency in LOD terminology. We thus hope to link the largely distinct scholarly literatures that address LOD and KOSs.

[113]  arXiv:1802.08148 [pdf, other]
Title: LIDIOMS: A Multilingual Linked Idioms Data Set
Comments: Accepted for publication in Language Resources and Evaluation Conference (LREC) 2018
Subjects: Computation and Language (cs.CL)

In this paper, we describe the LIDIOMS data set, a multilingual RDF representation of idioms currently containing five languages: English, German, Italian, Portuguese, and Russian. The data set is intended to support natural language processing applications by providing links between idioms across languages. The underlying data was crawled and integrated from various sources. To ensure the quality of the crawled data, all idioms were evaluated by at least two native speakers. Herein, we present the model devised for structuring the data. We also provide the details of linking LIDIOMS to well-known multilingual data sets such as BabelNet. The resulting data set complies with best practices according to Linguistic Linked Open Data Community.

[114]  arXiv:1802.08150 [pdf, other]
Title: RDF2PT: Generating Brazilian Portuguese Texts from RDF Data
Comments: Accepted for publication in Language Resources and Evaluation Conference (LREC) 2018
Subjects: Computation and Language (cs.CL)

The generation of natural language from Resource Description Framework (RDF) data has recently gained significant attention due to the continuous growth of Linked Data. A number of these approaches generate natural language in languages other than English, however, no work has been proposed to generate Brazilian Portuguese texts out of RDF. We address this research gap by presenting RDF2PT, an approach that verbalizes RDF data to Brazilian Portuguese language. We evaluated RDF2PT in an open questionnaire with 44 native speakers divided into experts and non-experts. Our results suggest that RDF2PT is able to generate text which is similar to that generated by humans and can hence be easily understood.

[115]  arXiv:1802.08157 [pdf, other]
Title: High order time integrators for the simulation of charged particle motion in magnetic quadrupoles
Comments: 39 pages, 18 figures
Subjects: Computational Engineering, Finance, and Science (cs.CE); Accelerator Physics (physics.acc-ph)

Magnetic quadrupoles are essential components of particle accelerators like the Large Hadron Collider. In order to study numerically the stability of the particle beam crossing a quadrupole, a large number of particle revolutions in the accelerator must be simulated, thus leading to the necessity to preserve numerically invariants of motion over a long time interval and to a substantial computational cost, mostly related to the repeated evaluation of the magnetic vector potential. In this paper, in order to reduce this cost, we first consider a specific gauge transformation that allows to reduce significantly the number of vector potential evaluations. We then analyze the sensitivity of the numerical solution to the interpolation procedure required to compute magnetic vector potential data from gridded precomputed values at the locations required by high order time integration methods. Finally, we compare several high order integration techniques, in order to assess their accuracy and efficiency for these long term simulations. Explicit high order Lie methods are considered, along with implicit high order symplectic integrators and conventional explicit Runge Kutta methods. Among symplectic methods, high order Lie integrators yield optimal results in terms of cost/accuracy ratios, but non symplectic Runge Kutta methods perform remarkably well even in very long term simulations. Furthermore, the accuracy of the field reconstruction and interpolation techniques are shown to be limiting factors for the accuracy of the particle tracking procedures.

[116]  arXiv:1802.08159 [pdf, other]
Title: Collaboratively Learning the Best Option, Using Bounded Memory
Subjects: Learning (cs.LG); Distributed, Parallel, and Cluster Computing (cs.DC)

We consider multi-armed bandit problems in social groups wherein each individual has bounded memory and shares the common goal of learning the best arm/option. We say an individual learns the best option if eventually (as $t \to \infty$) it pulls only the arm with the highest average reward. While this goal is provably impossible for an isolated individual, we show that, in social groups, this goal can be achieved easily with the aid of social persuasion, i.e., communication. Specifically, we study the learning dynamics wherein an individual sequentially decides on which arm to pull next based on not only its private reward feedback but also the suggestions provided by randomly chosen peers. Our learning dynamics are hard to analyze via explicit probabilistic calculations due to the stochastic dependency induced by social interaction. Instead, we employ the mean-field approximation method from statistical physics and we show:
(1) With probability $\to 1$ as the social group size $N \to \infty $, every individual in the social group learns the best option.
(2) Over an arbitrary finite time horizon $[0, T]$, with high probability (in $N$), the fraction of individuals that prefer the best option grows to 1 exponentially fast as $t$ increases ($t\in [0, T]$).
A major innovation of our mean-filed analysis is a simple yet powerful technique to deal with absorbing states in the interchange of limits $N \to \infty$ and $t \to \infty $. The mean-field approximation method allows us to approximate the probabilistic sample paths of our learning dynamics by a deterministic and smooth trajectory that corresponds to the unique solution of a well-behaved system of ordinary differential equations (ODEs). Such an approximation is desired because the analysis of a system of ODEs is relatively easier than that of the original stochastic system.

[117]  arXiv:1802.08176 [pdf, other]
Title: Analyzing Real-Time Multimedia Content From Network Cameras: Using CPUs and GPUs in the Cloud
Comments: Accepted at MIPR 2018
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC)

Millions of network cameras are streaming real-time multimedia content (images or videos) for various environments (e.g., highways and malls) and can be used for a variety of applications. Analyzing the content from many network cameras requires significant amounts of computing resources. Cloud vendors offer resources in the form of cloud instances with different capabilities and hourly costs. Some instances include GPUs that can accelerate analysis programs. Doing so incurs additional monetary cost because instances with GPUs are more expensive. It is a challenging problem to reduce the overall monetary cost of using the cloud to analyze the real-time multimedia content from network cameras while meeting the desired analysis frame rates. This paper describes a cloud resource manager that solves this problem by estimating the resource requirements of executing analysis programs using CPU or GPU, formulating the resource allocation problem as a multiple-choice vector bin packing problem, and solving it using an existing algorithm. The experiments show that the manager can reduce up to 61\% of the cost compared with other allocation strategies.

[118]  arXiv:1802.08182 [pdf, other]
Title: User Perceptions of Privacy in Smart Homes
Subjects: Human-Computer Interaction (cs.HC)

Despite the increasing presence of Internet of Things (IoT) devices inside the home, we know little about how users feel about their privacy living with Internet-connected devices that continuously monitor and collect data in their homes. To gain insight into this state of affairs, we conducted eleven semi-structured interviews with owners of smart homes, investigating privacy values and expectations. In this paper, we present the findings that emerged from our study: First, users prioritize the convenience and connectedness of their smart homes, and these values dictate their privacy opinions and behaviors. Second, user opinions about who should have access to their smart home data depend on the perceived benefit. Third, users assume their privacy is protected because they trust the manufacturers of their IoT devices. Our findings bring up several implications for IoT privacy, which include the need for design for privacy and evaluation standards.

[119]  arXiv:1802.08189 [pdf, ps, other]
Title: Complexity of the Steiner Network Problem with Respect to the Number of Terminals
Subjects: Discrete Mathematics (cs.DM)

In the Directed Steiner Network problem we are given an arc-weighted digraph $G$, a set of terminals $T \subseteq V(G)$, and an (unweighted) directed request graph $R$ with $V(R)=T$. Our task is to output a subgraph $G' \subseteq G$ of the minimum cost such that there is a directed path from $s$ to $t$ in $G'$ for all $st \in A(R)$.
It is known that the problem can be solved in time $|V(G)|^{O(|A(R)|)}$ [Feldman&Ruhl, SIAM J. Comput. 2006] and cannot be solved in time $|V(G)|^{o(|A(R)|)}$ even if $G$ is planar, unless Exponential-Time Hypothesis (ETH) fails [Chitnis et al., SODA 2014]. However, as this reduction (and other reductions showing hardness of the problem) only shows that the problem cannot be solved in time $|V(G)|^{o(|T|)}$ unless ETH fails, there is a significant gap in the complexity with respect to $|T|$ in the exponent.
We show that Directed Steiner Network is solvable in time $f(R)\cdot |V(G)|^{O(c_g \cdot |T|)}$, where $c_g$ is a constant depending solely on the genus of $G$ and $f$ is a computable function. We complement this result by showing that there is no $f(R)\cdot |V(G)|^{o(|T|^2/ \log |T|)}$ algorithm for any function $f$ for the problem on general graphs, unless ETH fails.

[120]  arXiv:1802.08195 [pdf, other]
Title: Adversarial Examples that Fool both Human and Computer Vision
Subjects: Learning (cs.LG); Computer Vision and Pattern Recognition (cs.CV); Neurons and Cognition (q-bio.NC); Machine Learning (stat.ML)

Machine learning models are vulnerable to adversarial examples: small changes to images can cause computer vision models to make mistakes such as identifying a school bus as an ostrich. However, it is still an open question whether humans are prone to similar mistakes. Here, we create the first adversarial examples designed to fool humans, by leveraging recent techniques that transfer adversarial examples from computer vision models with known parameters and architecture to other models with unknown parameters and architecture, and by modifying models to more closely match the initial processing of the human visual system. We find that adversarial examples that strongly transfer across computer vision models influence the classifications made by time-limited human observers.

[121]  arXiv:1802.08201 [pdf, ps, other]
Title: A Polynomial Time Subsumption Algorithm for Nominal Safe $\mathcal{ELO}_\bot$ under Rational Closure
Subjects: Artificial Intelligence (cs.AI)

Description Logics (DLs) under Rational Closure (RC) is a well-known framework for non-monotonic reasoning in DLs. In this paper, we address the concept subsumption decision problem under RC for nominal safe $\mathcal{ELO}_\bot$, a notable and practically important DL representative of the OWL 2 profile OWL 2 EL.
Our contribution here is to define a polynomial time subsumption procedure for nominal safe $\mathcal{ELO}_\bot$ under RC that relies entirely on a series of classical, monotonic $\mathcal{EL}_\bot$ subsumption tests. Therefore, any existing classical monotonic $\mathcal{EL}_\bot$ reasoner can be used as a black box to implement our method. We then also adapt the method to one of the known extensions of RC for DLs, namely Defeasible Inheritance-based DLs without losing the computational tractability.

[122]  arXiv:1802.08204 [pdf, other]
Title: SCRank: Spammer and Celebrity Ranking in Directed Social Networks
Subjects: Social and Information Networks (cs.SI)

Many online social networks allow directed edges: Alice can unilaterally add an "edge" to Bob, typically indicating interest in Bob or Bob's content, without Bob's permission or reciprocation. In directed social networks we observe the rise of two distinctive classes of users: celebrities who accrue unreciprocated incoming links, and follow spammers, who generate unreciprocated outgoing links. Identifying users in these two classes is important for abuse detection, user and content ranking, privacy choices, and other social network features.
In this paper we develop SCRank, an iterative algorithm to identify such users. We analyze SCRank both theoretically and experimentally. The spammer-celebrity definition is not amenable to analysis using standard power iteration, so we develop a novel potential function argument to show convergence to an approximate equilibrium point for a class of algorithms including SCRank. We then use experimental evaluation on a real global-scale social network and on synthetically generated graphs to observe that the algorithm converges quickly and consistently. Using synthetic data with built-in ground truth, we also experimentally show that the algorithm provides a good approximation to planted celebrities and spammers.

[123]  arXiv:1802.08209 [pdf, other]
Title: Data-driven Tactile Sensing using Spatially Overlapping Signals
Comments: 15 pages, 12 figures, 6 tables
Subjects: Robotics (cs.RO)

Traditional methods for achieving high localization accuracy on tactile sensors usually involve a matrix of miniaturized individual sensors distributed on the area of interest. This approach usually comes at a price of increased complexity in fabrication and circuitry, and can be hard to adapt to non-planar geometries. We propose a method where sensing terminals are embedded in a volume of soft material. Mechanical strain in this material results in a measurable signal between any two given terminals. By having multiple terminals and pairing them against each other in all possible combinations, we obtain a rich signal set using few wires. We mine this data to learn the mapping between the signals we extract and the contact parameters of interest. Our approach is general enough that it can be applied with different transduction methods, and achieves high accuracy in identifying indentation location and depth. Moreover, this method lends itself to simple fabrication techniques and makes no assumption about the underlying geometry, potentially simplifying future integration in robot hands.

[124]  arXiv:1802.08215 [pdf, other]
Title: ArduSoar: an Open-Source Thermalling Controller for Resource-Constrained Autopilots
Subjects: Robotics (cs.RO); Systems and Control (cs.SY)

Autonomous soaring capability has the potential to significantly increase time aloft for fixed-wing UAVs. In this paper, we introduce ArduSoar, the first soaring controller integrated into a major autopilot software suite for small UAVs. We describe ArduSoar from the algorithmic standpoint, outline its integration with the ArduPlane autopilot, and discuss tuning procedures and parameter choices for it.

[125]  arXiv:1802.08216 [pdf, other]
Title: ChatPainter: Improving Text to Image Generation using Dialogue
Subjects: Computer Vision and Pattern Recognition (cs.CV)

Synthesizing realistic images from text descriptions on a dataset like Microsoft Common Objects in Context (MS COCO), where each image can contain several objects, is a challenging task. Prior work has used text captions to generate images. However, captions might not be informative enough to capture the entire image and insufficient for the model to be able to understand which objects in the images correspond to which words in the captions. We show that adding a dialogue that further describes the scene leads to significant improvement in the inception score and in the quality of generated images on the MS COCO dataset.

[126]  arXiv:1802.08217 [pdf, ps, other]
Title: A new model for Cerebellar computation
Authors: Reza Moazzezi
Comments: 5 pages
Subjects: Neural and Evolutionary Computing (cs.NE); Neurons and Cognition (q-bio.NC)

The standard state space model is widely believed to account for the cerebellar computation in motor adaptation tasks [1]. Here we show that several recent experiments [2-4] where the visual feedback is irrelevant to the motor response challenge the standard model. Furthermore, we propose a new model that accounts for the the results presented in [2-4]. According to this new model, learning and forgetting are coupled and are error size dependent. We also show that under reasonable assumptions, our proposed model is the only model that accounts for both the classical adaptation paradigm as well as the recent experiments [2-4].

[127]  arXiv:1802.08218 [pdf, other]
Title: VizWiz Grand Challenge: Answering Visual Questions from Blind People
Subjects: Computer Vision and Pattern Recognition (cs.CV); Computation and Language (cs.CL); Human-Computer Interaction (cs.HC)

The study of algorithms to automatically answer visual questions currently is motivated by visual question answering (VQA) datasets constructed in artificial VQA settings. We propose VizWiz, the first goal-oriented VQA dataset arising from a natural VQA setting. VizWiz consists of over 31,000 visual questions originating from blind people who each took a picture using a mobile phone and recorded a spoken question about it, together with 10 crowdsourced answers per visual question. VizWiz differs from the many existing VQA datasets because (1) images are captured by blind photographers and so are often poor quality, (2) questions are spoken and so are more conversational, and (3) often visual questions cannot be answered. Evaluation of modern algorithms for answering visual questions and deciding if a visual question is answerable reveals that VizWiz is a challenging dataset. We introduce this dataset to encourage a larger community to develop more generalized algorithms that can assist blind people.

[128]  arXiv:1802.08219 [pdf, other]
Title: Tensor Field Networks: Rotation- and Translation-Equivariant Neural Networks for 3D Point Clouds
Subjects: Learning (cs.LG); Artificial Intelligence (cs.AI); Computer Vision and Pattern Recognition (cs.CV); Neural and Evolutionary Computing (cs.NE)

We introduce tensor field networks, which are locally equivariant to 3D rotations and translations (and invariant to permutations of points) at every layer. 3D rotation equivariance removes the need for data augmentation to identify features in arbitrary orientations. Our network uses filters built from spherical harmonics; due to the mathematical consequences of this filter choice, each layer accepts as input (and guarantees as output) scalars, vectors, and higher-order tensors, in the geometric sense of these terms. We demonstrate how tensor field networks learn to model simple physics (Newtonian gravitation and moment of inertia), classify simple 3D shapes (trained on one orientation and tested on shapes in arbitrary orientations), and, given a small organic molecule with an atom removed, replace the correct element at the correct location in space.

[129]  arXiv:1802.08223 [pdf, ps, other]
Title: Achievable Rate of Private Function Retrieval from MDS Coded Databases
Comments: 5 pages, 1 table, submitted for publication
Subjects: Information Theory (cs.IT); Information Retrieval (cs.IR)

We study the problem of private function retrieval (PFR) in a distributed storage system. In PFR the user wishes to retrieve a linear combination of $M$ messages stored in non-colluding $(N,K)$ MDS coded databases while revealing no information about the coefficients of the intended linear combination to any of the individual databases. We present an achievable scheme for MDS coded PFR with a rate that matches the capacity for coded private information retrieval derived recently, $R=(1+R_c+R_c^2+\dots+R_c^{M-1})^{-1}=\frac{1-R_c}{1-R_c^M}$, where $R_c=\frac{K}{N}$ is the rate of the MDS code. This achievable rate is tight in some special cases.

[130]  arXiv:1802.08232 [pdf, other]
Title: The Secret Sharer: Measuring Unintended Neural Network Memorization & Extracting Secrets
Subjects: Learning (cs.LG); Artificial Intelligence (cs.AI); Cryptography and Security (cs.CR)

Machine learning models based on neural networks and deep learning are being rapidly adopted for many purposes. What those models learn, and what they may share, is a significant concern when the training data may contain secrets and the models are public -- e.g., when a model helps users compose text messages using models trained on all users' messages.
This paper presents exposure: a simple-to-compute metric that can be applied to any deep learning model for measuring the memorization of secrets. Using this metric, we show how to extract those secrets efficiently using black-box API access. Further, we show that unintended memorization occurs early, is not due to over-fitting, and is a persistent issue across different types of models, hyperparameters, and training strategies. We experiment with both real-world models (e.g., a state-of-the-art translation model) and datasets (e.g., the Enron email dataset, which contains users' credit card numbers) to demonstrate both the utility of measuring exposure and the ability to extract secrets.
Finally, we consider many defenses, finding some ineffective (like regularization), and others to lack guarantees. However, by instantiating our own differentially-private recurrent model, we validate that by appropriately investing in the use of state-of-the-art techniques, the problem can be resolved, with high utility.

[131]  arXiv:1802.08233 [pdf, other]
Title: Pattern-based Modeling of Multiresilience Solutions for High-Performance Computing
Comments: 2018 ACM/SPEC International Conference on Performance Engineering (ICPE '18) Berlin, Germany
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC)

Resiliency is the ability of large-scale high-performance computing (HPC) applications to gracefully handle errors, and recover from failures. In this paper, we propose a pattern-based approach to constructing resilience solutions that handle multiple error modes. Using resilience patterns, we evaluate the performance and reliability characteristics of detection, containment and mitigation techniques for transient errors that cause silent data corruptions and techniques for fail-stop errors that result in process failures. We demonstrate the design and implementation of the multiresilience solution based on patterns instantiated across multiple layers of the system stack. The patterns are integrated to work together to achieve resiliency to different error types in a performance-efficient manner.

[132]  arXiv:1802.08234 [pdf, other]
Title: What's the Over/Under? Probabilistic Bounds on Information Leakage
Subjects: Programming Languages (cs.PL)

Quantitative information flow (QIF) is concerned with measuring how much of a secret is leaked to an adversary who observes the result of a computation that uses it. Prior work has shown that QIF techniques based on abstract interpretation with probabilistic polyhedra can be used to analyze the worst-case leakage of a query, on-line, to determine whether that query can be safely answered. While this approach can provide precise estimates, it does not scale well. This paper shows how to solve the scalability problem by augmenting the baseline technique with sampling and symbolic execution. We prove that our approach never underestimates a query's leakage (it is sound), and detailed experimental results show that we can match the precision of the baseline technique but with orders of magnitude better performance.

[133]  arXiv:1802.08235 [pdf, other]
Title: Vector Field Based Neural Networks
Comments: 6 pages, 5 figures. To appear in the Proceedings of the 26th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning
Subjects: Learning (cs.LG); Artificial Intelligence (cs.AI); Machine Learning (stat.ML)

A novel Neural Network architecture is proposed using the mathematically and physically rich idea of vector fields as hidden layers to perform nonlinear transformations in the data. The data points are interpreted as particles moving along a flow defined by the vector field which intuitively represents the desired movement to enable classification. The architecture moves the data points from their original configuration to anew one following the streamlines of the vector field with the objective of achieving a final configuration where classes are separable. An optimization problem is solved through gradient descent to learn this vector field.

[134]  arXiv:1802.08236 [pdf, other]
Title: NetChain: Scale-Free Sub-RTT Coordination (Extended Version)
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC)

Coordination services are a fundamental building block of modern cloud systems, providing critical functionalities like configuration management and distributed locking. The major challenge is to achieve low latency and high throughput while providing strong consistency and fault-tolerance. Traditional server-based solutions require multiple round-trip times (RTTs) to process a query. This paper presents NetChain, a new approach that provides scale-free sub-RTT coordination in datacenters. NetChain exploits recent advances in programmable switches to store data and process queries entirely in the network data plane. This eliminates the query processing at coordination servers and cuts the end-to-end latency to as little as half of an RTT---clients only experience processing delay from their own software stack plus network delay, which in a datacenter setting is typically much smaller. We design new protocols and algorithms based on chain replication to guarantee strong consistency and to efficiently handle switch failures. We implement a prototype with four Barefoot Tofino switches and four commodity servers. Evaluation results show that compared to traditional server-based solutions like ZooKeeper, our prototype provides orders of magnitude higher throughput and lower latency, and handles failures gracefully.

[135]  arXiv:1802.08237 [pdf, ps, other]
Title: Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
Subjects: Data Structures and Algorithms (cs.DS); Distributed, Parallel, and Cluster Computing (cs.DC)

We present $O(\log\log n)$-round algorithms in the Massively Parallel Computation (MPC) model, with $\tilde{O}(n)$ memory per machine, that compute a maximal independent set, a $1+\epsilon$ approximation of maximum matching, and a $2+\epsilon$ approximation of minimum vertex cover, for any $n$-vertex graph and any constant $\epsilon>0$. These improve the state of the art as follows:
-- Our MIS algorithm leads to a simple $O(\log\log \Delta)$-round MIS algorithm in the Congested Clique model of distributed computing. This result improves exponentially on the $\tilde{O}(\sqrt{\log \Delta})$-round algorithm of Ghaffari [PODC'17].
-- Our $O(\log\log n)$-round $(1+\epsilon)$-approximate maximum matching algorithm simplifies and improves on a rather complex $O(\log^2\log n)$-round $(1+\epsilon)$-approximation algorithm of Czumaj et al. [STOC'18].
-- Our $O(\log\log n)$-round $(2+\epsilon)$-approximate minimum vertex cover algorithm improves on an $O(\log\log n)$-round $O(1)$-approximation of Assadi et al. [arXiv'17].

[136]  arXiv:1802.08241 [pdf, other]
Title: Hessian-based Analysis of Large Batch Training and Robustness to Adversaries
Comments: 24 pages, 13 figures
Subjects: Computer Vision and Pattern Recognition (cs.CV); Learning (cs.LG); Machine Learning (stat.ML)

Large batch size training of Neural Networks has been shown to incur accuracy loss when trained with the current methods. The precise underlying reasons for this are still not completely understood. Here, we study large batch size training through the lens of the Hessian operator and robust optimization. In particular, we perform a Hessian based study to analyze how the landscape of the loss functional is different for large batch size training. We compute the true Hessian spectrum, without approximation, by back-propagating the second derivative. Our results on multiple networks show that, when training at large batch sizes, one tends to stop at points in the parameter space with noticeably higher/larger Hessian spectrum, i.e., where the eigenvalues of the Hessian are much larger. We then study how batch size affects robustness of the model in the face of adversarial attacks. All the results show that models trained with large batches are more susceptible to adversarial attacks, as compared to models trained with small batch sizes. Furthermore, we prove a theoretical result which shows that the problem of finding an adversarial perturbation is a saddle-free optimization problem. Finally, we show empirical results that demonstrate that adversarial training leads to areas with smaller Hessian spectrum. We present detailed experiments with five different network architectures tested on MNIST, CIFAR-10, and CIFAR-100 datasets.

[137]  arXiv:1802.08245 [pdf]
Title: Arbitrarily Substantial Number Representation for Complex Number
Subjects: Computer Vision and Pattern Recognition (cs.CV)

Researchers are often perplexed when their machine learning algorithms are required to deal with complex number. Various strategies are commonly employed to project complex number into real number, although it is frequently sacrificing the information contained in the complex number. This paper proposes a new method and four techniques to represent complex number as real number, without having to sacrifice the information contained. The proposed techniques are also capable of retrieving the original complex number from the representing real number, with little to none of information loss. The promising applicability of the proposed techniques has been demonstrated and worth to receive further exploration in representing the complex number.

Cross-lists for Fri, 23 Feb 18

[138]  arXiv:1802.05427 (cross-list from eess.SP) [pdf, other]
Title: Implementation of Massive MIMO Uplink Receiver on RaPro Prototyping Platform
Comments: 14 pages, 10 figures
Subjects: Signal Processing (eess.SP); Information Theory (cs.IT)

The updated physical layer standard of the fifth generation wireless communication suggests the necessity of a rapid prototyping platform. To this end, we develop RaPro, a multi-core general purpose processor-based massive multiple-input-multiple-output (MIMO) prototyping platform. To enhance RaPro, high performance detection and beamforming are needed, whereas both of them request for accurate channel state information (CSI). In this paper, linear minimum mean square error (LMMSE)-based channel estimator is adopted and encapsulated inside RaPro to gain more accurate CSI. Considering the high comlexity and unknown of channel statistics, we design low-complexity LMMSE channel estimator to alleviate the rising complexity along with increasing antenna number and set more computational resource aside for massive MIMO uplink detection and downlink beamforming. Simulation results indicate the high mean square error performance and robustness of designed low-complexity method. Indoor and corridor scenario tests show prominent improvement in bit error rate performance. Time cost analysis proves the practical use and real-time transmission ability of the implemented uplink receiver on RaPro.

[139]  arXiv:1802.07756 (cross-list from stat.ML) [pdf]
Title: Determining the best classifier for predicting the value of a boolean field on a blood donor database
Authors: Ritabrata Maiti
Subjects: Machine Learning (stat.ML); Learning (cs.LG)

Motivation: Thanks to digitization, we often have access to large databases, consisting of various fields of information, ranging from numbers to texts and even boolean values. Such databases lend themselves especially well to machine learning, classification and big data analysis tasks. We are able to train classifiers, using already existing data and use them for predicting the values of a certain field, given that we have information regarding the other fields. Most specifically, in this study, we look at the Electronic Health Records (EHRs) that are compiled by hospitals. These EHRs are convenient means of accessing data of individual patients, but there processing as a whole still remains a task. However, EHRs that are composed of coherent, well-tabulated structures lend themselves quite well to the application to machine language, via the usage of classifiers. In this study, we look at a Blood Transfusion Service Center Data Set (Data taken from the Blood Transfusion Service Center in Hsin-Chu City in Taiwan). We used scikit-learn machine learning in python. From Support Vector Machines(SVM), we use Support Vector Classification(SVC), from the linear model we import Perceptron. We also used the K.neighborsclassifier and the decision tree classifiers. We segmented the database into the 2 parts. Using the first, we trained the classifiers and the next part was used to verify if the classifier prediction matched that of the actual values.
Contact: ritabratamaiti@hiretrex.com

[140]  arXiv:1802.07773 (cross-list from math.ST) [pdf, other]
Title: Counting Motifs with Graph Sampling
Subjects: Statistics Theory (math.ST); Discrete Mathematics (cs.DM); Machine Learning (stat.ML)

Applied researchers often construct a network from a random sample of nodes in order to infer properties of the parent network. Two of the most widely used sampling schemes are subgraph sampling, where we sample each vertex independently with probability $p$ and observe the subgraph induced by the sampled vertices, and neighborhood sampling, where we additionally observe the edges between the sampled vertices and their neighbors.
In this paper, we study the problem of estimating the number of motifs as induced subgraphs under both models from a statistical perspective. We show that: for any connected $h$ on $k$ vertices, to estimate $s=\mathsf{s}(h,G)$, the number of copies of $h$ in the parent graph $G$ of maximum degree $d$, with a multiplicative error of $\epsilon$, (a) For subgraph sampling, the optimal sampling ratio $p$ is $\Theta_{k}(\max\{ (s\epsilon^2)^{-\frac{1}{k}}, \; \frac{d^{k-1}}{s\epsilon^{2}} \})$, achieved by Horvitz-Thompson type of estimators. (b) For neighborhood sampling, we propose a family of estimators, encompassing and outperforming the Horvitz-Thompson estimator and achieving the sampling ratio $O_{k}(\min\{ (\frac{d}{s\epsilon^2})^{\frac{1}{k-1}}, \; \sqrt{\frac{d^{k-2}}{s\epsilon^2}}\})$. This is shown to be optimal for all motifs with at most $4$ vertices and cliques of all sizes.
The matching minimax lower bounds are established using certain algebraic properties of subgraph counts. These results quantify how much more informative neighborhood sampling is than subgraph sampling, as empirically verified by experiments on both synthetic and real-world data. We also address the issue of adaptation to the unknown maximum degree, and study specific problems for parent graphs with additional structures, e.g., trees or planar graphs.

[141]  arXiv:1802.07795 (cross-list from quant-ph) [pdf, ps, other]
Title: Communication Complexity of One-Shot Remote State Preparation
Comments: 36 pages
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC)

Quantum teleportation uses prior shared entanglement and classical communication to send an unknown quantum state from one party to another. Remote state preparation (RSP) is a similar distributed task in which the sender knows the entire classical description of the state to be sent. (This may also be viewed as the task of non-oblivious compression of a single sample from an ensemble of quantum states.) We study the communication complexity of approximate remote state preparation, in which the goal is to prepare an approximation of the desired quantum state. Jain [Quant. Inf. & Comp., 2006] showed that the worst-case communication complexity of approximate RSP can be bounded from above in terms of the maximum possible information in an encoding. He also showed that this quantity is a lower bound for communication complexity of (exact) remote state preparation. In this work, we tightly characterize the worst-case and average-case communication complexity of remote state preparation in terms of non-asymptotic information-theoretic quantities. We also show that the average-case communication complexity of RSP can be much smaller than the worst-case one. In the process, we show that n bits cannot be communicated with less than n transmitted bits in LOCC protocols. This strengthens a result due to Nayak and Salzman [J. ACM, 2006] and may be of independent interest.

[142]  arXiv:1802.07834 (cross-list from q-bio.PE) [pdf, other]
Title: Learning to Gather without Communication
Comments: Preliminary version, presented at the 5th Biological Distributed Algorithms Workshop. Washington D.C, July 28th, 2017
Subjects: Populations and Evolution (q-bio.PE); Distributed, Parallel, and Cluster Computing (cs.DC); Learning (cs.LG); Multiagent Systems (cs.MA); Machine Learning (stat.ML)

A standard belief on emerging collective behavior is that it emerges from simple individual rules. Most of the mathematical research on such collective behavior starts from imperative individual rules, like always go to the center. But how could an (optimal) individual rule emerge during a short period within the group lifetime, especially if communication is not available. We argue that such rules can actually emerge in a group in a short span of time via collective (multi-agent) reinforcement learning, i.e learning via rewards and punishments. We consider the gathering problem: several agents (social animals, swarming robots...) must gather around a same position, which is not determined in advance. They must do so without communication on their planned decision, just by looking at the position of other agents. We present the first experimental evidence that a gathering behavior can be learned without communication in a partially observable environment. The learned behavior has the same properties as a self-stabilizing distributed algorithm, as processes can gather from any initial state (and thus tolerate any transient failure). Besides, we show that it is possible to tolerate the brutal loss of up to 90\% of agents without significant impact on the behavior.

[143]  arXiv:1802.07885 (cross-list from physics.soc-ph) [pdf, other]
Title: On the economics of electrical storage for variable renewable energy sources
Subjects: Physics and Society (physics.soc-ph); Other Computer Science (cs.OH)

The use of renewable energy sources is a major strategy to mitigate climate change. Yet Sinn (2017) argues that excessive electrical storage requirements could limit the further expansion of variable wind and solar energy. We question, and alter, strong implicit assumptions of Sinn's approach and find that storage needs are considerably lower, up to two orders of magnitude. First, we move away from corner solutions by allowing for combinations of storage and renewable curtailment. Second, we specify a parsimonious model to derive first-best outcomes. We conclude that electrical storage is unlikely to limit the transition to renewable energy.

[144]  arXiv:1802.07903 (cross-list from math.OC) [pdf, other]
Title: Safety-Aware Optimal Control of Stochastic Systems Using Conditional Value-at-Risk
Comments: Extended version of a 2018 ACC paper
Subjects: Optimization and Control (math.OC); Systems and Control (cs.SY)

In this paper, we consider a multi-objective control problem for stochastic systems that seeks to minimize a cost of interest while ensuring safety. We introduce a novel measure of safety risk using the conditional value-at-risk and a set distance to formulate a safety risk-constrained optimal control problem. Our reformulation method using an extremal representation of the safety risk measure provides a computationally tractable dynamic programming solution. A useful byproduct of the proposed solution is the notion of a risk-constrained safe set, which is a new stochastic safety verification tool. We also establish useful connections between the risk-constrained safe sets and the popular probabilistic safe sets. The tradeoff between the risk tolerance and the mean performance of our controller is examined through an inventory control problem.

[145]  arXiv:1802.07927 (cross-list from stat.ML) [pdf, other]
Title: The Hidden Vulnerability of Distributed Learning in Byzantium
Subjects: Machine Learning (stat.ML); Distributed, Parallel, and Cluster Computing (cs.DC); Learning (cs.LG)

While machine learning is going through an era of celebrated success, concerns have been raised about the vulnerability of its backbone: stochastic gradient descent (SGD). Recent approaches have been proposed to ensure the robustness of distributed SGD against adversarial (Byzantine) workers sending poisoned gradients during the training phase. Some of these approaches have been proven Byzantine-resilient: they ensure the convergence of SGD despite the presence of a minority of adversarial workers.
We show in this paper that convergence is not enough. In high dimension $d \gg 1$, an adver\-sary can build on the loss function's non--convexity to make SGD converge to ineffective models. More precisely, we bring to light that existing Byzantine--resilient schemes leave a margin of poisoning of $\Omega\left(f(d)\right)$, where $f(d)$ increases at least like $\sqrt[p]{d~}$. Based on this leeway, we build a simple attack, and experimentally show its strong to utmost effectivity on CIFAR--10 and MNIST.
We introduce Bulyan, and prove it significantly reduces the attackers leeway to a narrow $O( \frac{1}{\sqrt{d~}})$ bound. We empirically show that Bulyan does not suffer the fragility of existing aggregation rules and, at a reasonable cost in terms of required batch size, achieves convergence as if only non--Byzantine gradients had been used to update the model.

[146]  arXiv:1802.07928 (cross-list from stat.ML) [pdf, other]
Title: Asynchronous Byzantine Machine Learning
Subjects: Machine Learning (stat.ML); Distributed, Parallel, and Cluster Computing (cs.DC); Learning (cs.LG)

Asynchronous distributed machine learning solutions have proven very effective so far, but always assuming perfectly functioning workers. In practice, some of the workers can however exhibit Byzantine behavior, caused by hardware failures, software bugs, corrupt data, or even malicious attacks. We introduce \emph{Kardam}, the first distributed asynchronous stochastic gradient descent (SGD) algorithm that copes with Byzantine workers. Kardam consists of two complementary components: a filtering and a dampening component. The first is scalar-based and ensures resilience against $\frac{1}{3}$ Byzantine workers. Essentially, this filter leverages the Lipschitzness of cost functions and acts as a self-stabilizer against Byzantine workers that would attempt to corrupt the progress of SGD. The dampening component bounds the convergence rate by adjusting to stale information through a generic gradient weighting scheme. We prove that Kardam guarantees almost sure convergence in the presence of asynchrony and Byzantine behavior, and we derive its convergence rate. We evaluate Kardam on the CIFAR-100 and EMNIST datasets and measure its overhead with respect to non Byzantine-resilient solutions. We empirically show that Kardam does not introduce additional noise to the learning procedure but does induce a slowdown (the cost of Byzantine resilience) that we both theoretically and empirically show to be less than $f/n$, where $f$ is the number of Byzantine failures tolerated and $n$ the total number of workers. Interestingly, we also empirically observe that the dampening component is interesting in its own right for it enables to build an SGD algorithm that outperforms alternative staleness-aware asynchronous competitors in environments with honest workers.

[147]  arXiv:1802.07954 (cross-list from stat.ML) [pdf, other]
Title: The State of the Art in Integrating Machine Learning into Visual Analytics
Journal-ref: Computer Graphics Forum, Wiley, 2017, 36 (8), pp.458 - 486. \&\#x3008;10.1111/cgf.13092\&\#x3009
Subjects: Machine Learning (stat.ML); Human-Computer Interaction (cs.HC); Learning (cs.LG)

Visual analytics systems combine machine learning or other analytic techniques with interactive data visualization to promote sensemaking and analytical reasoning. It is through such techniques that people can make sense of large, complex data. While progress has been made, the tactful combination of machine learning and data visualization is still under-explored. This state-of-the-art report presents a summary of the progress that has been made by highlighting and synthesizing select research advances. Further, it presents opportunities and challenges to enhance the synergy between machine learning and visual analytics for impactful future research directions.

[148]  arXiv:1802.07990 (cross-list from math.OC) [pdf, other]
Title: Joint Antenna Selection and Phase-Only Beamforming Using Mixed-Integer Nonlinear Programming
Comments: to be presented at WSA 2018
Subjects: Optimization and Control (math.OC); Information Theory (cs.IT)

In this paper, we consider the problem of joint antenna selection and analog beamformer design in downlink single-group multicast networks. Our objective is to reduce the hardware costs by minimizing the number of required phase shifters at the transmitter while fulfilling given distortion limits at the receivers. We formulate the problem as an L0 minimization problem and devise a novel branch-and-cut based algorithm to solve the resulting mixed-integer nonlinear program to optimality. We also propose a suboptimal heuristic algorithm to solve the above problem approximately with a low computational complexity. Computational results illustrate that the solutions produced by the proposed heuristic algorithm are optimal in most cases. The results also indicate that the performance of the optimal methods can be significantly improved by initializing with the result of the suboptimal method.

[149]  arXiv:1802.08012 (cross-list from stat.ML) [pdf, other]
Title: Learning Topic Models by Neighborhood Aggregation
Authors: Ryohei Hisano
Subjects: Machine Learning (stat.ML); Learning (cs.LG)

Topic models are one of the most frequently used models in machine learning due to its high interpretability and modular structure. However extending the model to include supervisory signal, incorporate pre-trained word embedding vectors and add nonlinear output function to the model is not an easy task because one has to resort to highly intricate approximate inference procedure. In this paper, we show that topic models could be viewed as performing a neighborhood aggregation algorithm where the messages are passed through a network defined over words. Under the network view of topic models, nodes corresponds to words in a document and edges correspond to either a relationship describing co-occurring words in a document or a relationship describing same word in the corpus. The network view allows us to extend the model to include supervisory signals, incorporate pre-trained word embedding vectors and add nonlinear output function to the model in a simple manner. Moreover, we describe a simple way to train the model that is well suited in a semi-supervised setting where we only have supervisory signals for some portion of the corpus and the goal is to improve prediction performance in the held-out data. Through careful experiments we show that our approach outperforms state-of-the-art supervised Latent Dirichlet Allocation implementation in both held-out document classification tasks and topic coherence.

[150]  arXiv:1802.08061 (cross-list from econ.EM) [pdf, ps, other]
Title: Algorithmic Collusion in Cournot Duopoly Market: Evidence from Experimental Economics
Comments: 22 pages, 7 figures; algorithmic collusion; Cournot duopoly model; experimental economics; game theory; collusion algorithm design; iterated prisoner's dilemma; antitrust; mechanism design
Subjects: Econometrics (econ.EM); Computer Science and Game Theory (cs.GT); Applications (stat.AP); Machine Learning (stat.ML)

Algorithmic collusion is an emerging concept in current artificial intelligence age. Whether algorithmic collusion is a creditable threat remains as an argument. In this paper, we propose an algorithm which can extort its human rival to collude in a Cournot duopoly competing market. In experiments, we show that, the algorithm can successfully extorted its human rival and gets higher profit in long run, meanwhile the human rival will fully collude with the algorithm. As a result, the social welfare declines rapidly and stably. Both in theory and in experiment, our work confirms that, algorithmic collusion can be a creditable threat. In application, we hope, the frameworks, the algorithm design as well as the experiment environment illustrated in this work, can be an incubator or a test bed for researchers and policymakers to handle the emerging algorithmic collusion.

[151]  arXiv:1802.08089 (cross-list from math.OC) [pdf, ps, other]
Title: Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem
Authors: Andre Wibisono
Comments: 44 pages
Subjects: Optimization and Control (math.OC); Information Theory (cs.IT); Learning (cs.LG); Machine Learning (stat.ML)

We study sampling as optimization in the space of measures. We focus on gradient flow-based optimization with the Langevin dynamics as a case study. We investigate the source of the bias of the unadjusted Langevin algorithm (ULA) in discrete time, and consider how to remove or reduce the bias. We point out the difficulty is that the heat flow is exactly solvable, but neither its forward nor backward method is implementable in general, except for Gaussian data. We propose the symmetrized Langevin algorithm (SLA), which should have a smaller bias than ULA, at the price of implementing a proximal gradient step in space. We show SLA is in fact consistent for Gaussian target measure, whereas ULA is not. We also illustrate various algorithms explicitly for Gaussian target measure, including gradient descent, proximal gradient, and Forward-Backward, and show they are all consistent.

[152]  arXiv:1802.08105 (cross-list from math.NT) [pdf, ps, other]
Title: Linear complexity of Ding-Helleseth generalized cyclotomic sequences of order eight
Comments: 18 pages, 7 tables
Subjects: Number Theory (math.NT); Cryptography and Security (cs.CR)

During the last two decades, many kinds of periodic sequences with good pseudo-random properties have been constructed from classical and generalized cyclotomic classes, and used as keystreams for stream ciphers and secure communications. Among them are a family DH-GCS$_{d}$ of generalized cyclotomic sequences on the basis of Ding and Helleseth's generalized cyclotomy, of length $pq$ and order $d=\mathrm{gcd}(p-1,q-1)$ for distinct odd primes $p$ and $q$. The linear complexity (or linear span), as a valuable measure of unpredictability, is precisely determined for DH-GCS$_{8}$ in this paper. Our approach is based on Edemskiy and Antonova's computation method with the help of explicit expressions of Gaussian classical cyclotomic numbers of order $8$. Our result for $d=8$ is compatible with Yan's low bound $(pq-1)/2$ of the linear complexity for any order $d$, which means high enough to resist security attacks of the Berlekamp-Massey algorithm. Finally, we include SageMath codes to illustrate the validity of our result by examples.

[153]  arXiv:1802.08113 (cross-list from math.OC) [pdf, other]
Title: Adaptive synchronisation of unknown nonlinear networked systems with prescribed performance
Comments: arXiv admin note: text overlap with arXiv:1802.07253
Journal-ref: International Journal of Systems Science 48, no. 4 (2017): 885-898
Subjects: Optimization and Control (math.OC); Systems and Control (cs.SY); Dynamical Systems (math.DS)

This paper proposes an adaptive tracking control with prescribed performance function for distributive cooperative control of highly nonlinear multi-agent systems. The use of such approach confines the tracking error within a large predefined set to a predefined smaller set. The key idea is to transform the constrained system into unconstrained one through the transformation of the output error. Agents' dynamics are assumed unknown, and the controller is developed for a strongly connected structured network. The proposed controller allows all agents to follow the trajectory of the leader node, while satisfying the necessary dynamic requirements. The proposed approach guarantees uniform ultimate boundedness for the transformed error as well as a bounded adaptive estimate of the unknown parameters and dynamics. Simulations include two examples to validate the robustness and smoothness of the proposed controller against highly nonlinear heterogeneous multi-agent system with uncertain time-variant parameters and external disturbances.

[154]  arXiv:1802.08151 (cross-list from math.DS) [pdf, other]
Title: New Results on Finite-Time Stability: Geometric Conditions and Finite-Time Controllers
Comments: 2018 American Control Conference, Milwaukee, Wisconsin, June 2018
Subjects: Dynamical Systems (math.DS); Systems and Control (cs.SY)

This paper presents a novel controller that yields finite-time stability for linear systems. We first present a necessary and sufficient condition for the origin of a scalar system to be finite-time stable. Then we present novel finite-time controllers based on vector fields and barrier functions to demonstrate the utility of this geometric condition. We also consider the general class of linear controllable systems, and present a continuous feedback control law to stabilize the origin of the system in finite time. Finally, we present simulation results for each of these controllers, showing the efficacy of the designed control laws.

[155]  arXiv:1802.08154 (cross-list from eess.SP) [pdf, other]
Title: Sliding Bidirectional Recurrent Neural Networks for Sequence Detection in Communication Systems
Comments: accepted for publication in the proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) 2018. arXiv admin note: text overlap with arXiv:1802.02046 and arXiv:1705.08044
Subjects: Signal Processing (eess.SP); Information Theory (cs.IT); Learning (cs.LG)

The design and analysis of communication systems typically rely on the development of mathematical models that describe the underlying communication channel. However, in some systems, such as molecular communication systems where chemical signals are used for transfer of information, the underlying channel models are unknown. In these scenarios, a completely new approach to design and analysis is required. In this work, we focus on one important aspect of communication systems, the detection algorithms, and demonstrate that by using tools from deep learning, it is possible to train detectors that perform well without any knowledge of the underlying channel models. We propose a technique we call sliding bidirectional recurrent neural network (SBRNN) for real-time sequence detection. We evaluate this algorithm using experimental data that is collected by a chemical communication platform, where the channel model is unknown and difficult to model analytically. We show that deep learning algorithms perform significantly better than a detector proposed in previous works, and the SBRNN outperforms other techniques considered in this work.

[156]  arXiv:1802.08183 (cross-list from stat.ML) [pdf, other]
Title: Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity
Subjects: Machine Learning (stat.ML); Artificial Intelligence (cs.AI); Data Structures and Algorithms (cs.DS); Learning (cs.LG)

Online optimization has been a successful framework for solving large-scale problems under computational constraints and partial information. Current methods for online convex optimization require either a projection or exact gradient computation at each step, both of which can be prohibitively expensive for large-scale applications. At the same time, there is a growing trend of non-convex optimization in machine learning community and a need for online methods. Continuous submodular functions, which exhibit a natural diminishing returns condition, have recently been proposed as a broad class of non-convex functions which may be efficiently optimized. Although online methods have been introduced, they suffer from similar problems. In this work, we propose Meta-Frank-Wolfe, the first online projectionfree algorithm that uses stochastic gradient estimates. The algorithm relies on a careful sampling of gradients in each round and achieves the optimal $O(\sqrt{T})$ adversarial regret bounds for convex and continuous submodular optimization. We also propose One-Shot Frank-Wolfe, a simpler algorithm which requires only a single stochastic gradient estimate in each round and achieves a $O(T^{2/3})$ stochastic regret bound for convex and continuous submodular optimization. We apply our methods to develop a novel "lifting" framework for the online discrete submodular maximization and also see that they outperform current state of the art techniques on an extensive set of experiments.

[157]  arXiv:1802.08227 (cross-list from quant-ph) [pdf, other]
Title: Quantum linear systems algorithms: a primer
Comments: 55 pages, 5 figures, comments welcome
Subjects: Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS); Numerical Analysis (math.NA)

The Harrow-Hassidim-Lloyd (HHL) quantum algorithm for sampling from the solution of a linear system provides an exponential speed-up over its classical counterpart. The problem of solving a system of linear equations has a wide scope of applications, and thus HHL constitutes an important algorithmic primitive. In these notes, we present the HHL algorithm and its improved versions in detail, including explanations of the constituent sub- routines. More specifically, we discuss various quantum subroutines such as quantum phase estimation and amplitude amplification, as well as the important question of loading data into a quantum computer, via quantum RAM. The improvements to the original algorithm exploit variable-time amplitude amplification as well as a method for implementing linear combinations of unitary operations (LCUs) based on a decomposition of the operators using Fourier and Chebyshev series. Finally, we discuss a linear solver based on the quantum singular value estimation (QSVE) subroutine.

[158]  arXiv:1802.08242 (cross-list from stat.ME) [pdf, other]
Title: Structured low-rank matrix completion for forecasting in time series analysis
Comments: 25 pages, 12 figures
Subjects: Methodology (stat.ME); Systems and Control (cs.SY); Numerical Analysis (math.NA); Machine Learning (stat.ML)

In this paper we consider the low-rank matrix completion problem with specific application to forecasting in time series analysis. Briefly, the low-rank matrix completion problem is the problem of imputing missing values of a matrix under a rank constraint. We consider a matrix completion problem for Hankel matrices and a convex relaxation based on the nuclear norm. Based on new theoretical results and a number of numerical and real examples, we investigate the cases when the proposed approach can work. Our results highlight the importance of choosing a proper weighting scheme for the known observations.

[159]  arXiv:1802.08246 (cross-list from stat.ML) [pdf, other]
Title: Characterizing Implicit Bias in Terms of Optimization Geometry
Subjects: Machine Learning (stat.ML); Learning (cs.LG)

We study the bias of generic optimization methods, including Mirror Descent, Natural Gradient Descent and Steepest Descent with respect to different potentials and norms, when optimizing underdetermined linear regression or separable linear classification problems. We ask the question of whether the global minimum (among the many possible global minima) reached by optimization algorithms can be characterized in terms of the potential or norm, and independently of hyperparameter choices such as step size and momentum.

Replacements for Fri, 23 Feb 18

[160]  arXiv:1407.6169 (replaced) [pdf, ps, other]
Title: Multiplicative Complexity of Vector Valued Boolean Functions
Comments: Extended version of the paper "The Relationship Between Multiplicative Complexity and Nonlinearity", MFCS2014
Subjects: Computational Complexity (cs.CC)
[161]  arXiv:1502.07209 (replaced) [pdf, other]
Title: Exploiting Feature and Class Relationships in Video Categorization with Regularized Deep Neural Networks
Comments: Please cite the officially published IEEE TPAMI version if you find this work helpful
Journal-ref: IEEE TPAMI 40.2 (2018): 352-364
Subjects: Computer Vision and Pattern Recognition (cs.CV); Multimedia (cs.MM)
[162]  arXiv:1604.00424 (replaced) [pdf, other]
Title: Local sparsity and recovery of fusion frames structured signals
Comments: 7 figures, 24 pages
Subjects: Information Theory (cs.IT)
[163]  arXiv:1604.05636 (replaced) [pdf, ps, other]
Title: Pattern-Based Approach to the Workflow Satisfiability Problem with User-Independent Constraints
Subjects: Artificial Intelligence (cs.AI); Computational Complexity (cs.CC)
[164]  arXiv:1609.06782 (replaced) [pdf, other]
Title: Deep Learning for Video Classification and Captioning
Comments: Book chapter in Frontiers of Multimedia Research
Subjects: Computer Vision and Pattern Recognition (cs.CV); Multimedia (cs.MM)
[165]  arXiv:1611.02683 (replaced) [pdf, other]
Title: Unsupervised Pretraining for Sequence to Sequence Learning
Comments: Updated to accepted EMNLP 2017 version
Subjects: Computation and Language (cs.CL); Learning (cs.LG); Neural and Evolutionary Computing (cs.NE)
[166]  arXiv:1611.07191 (replaced) [pdf, other]
Title: Distributable Consistent Multi-Graph Matching
Subjects: Data Structures and Algorithms (cs.DS); Computer Vision and Pattern Recognition (cs.CV)
[167]  arXiv:1611.07583 (replaced) [pdf, other]
Title: Alternating Direction Graph Matching
Comments: Accepted for publication at the 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
Subjects: Computer Vision and Pattern Recognition (cs.CV)
[168]  arXiv:1701.07522 (replaced) [pdf, other]
Title: Joint Uplink-Downlink Cell Associations for Interference Networks with Local Connectivity
Comments: 10 pages, Part of this work was in proc. 55th Annual Allerton Conference on Communication, Control, and Computing, Oct. 2017. Also, part of this work is submitted to International Symposium of Information Theory (ISIT 2018)
Subjects: Information Theory (cs.IT)
[169]  arXiv:1701.07879 (replaced) [pdf]
Title: A Radically New Theory of how the Brain Represents and Computes with Probabilities
Authors: Gerard Rinkus
Comments: 33 pages, 10 figures - Sec. explaining single cell tuning fns as artifacts of embedding SDRs in superposition removed (for future paper) - Clarified that a given SDR code represents the whole likelihood distribution over stored hypotheses at a coarsely-ranked level of fidelity (Submitted for review)
Subjects: Neurons and Cognition (q-bio.NC); Computer Vision and Pattern Recognition (cs.CV); Neural and Evolutionary Computing (cs.NE)
[170]  arXiv:1702.07309 (replaced) [pdf, ps, other]
Title: Bounding the inefficiency of compromise in opinion formation
Comments: 36 pages, 10 figures
Subjects: Computer Science and Game Theory (cs.GT)
[171]  arXiv:1702.08431 (replaced) [pdf, other]
Title: Boundary-Seeking Generative Adversarial Networks
Subjects: Machine Learning (stat.ML); Learning (cs.LG)
[172]  arXiv:1703.01610 (replaced) [pdf, ps, other]
Title: Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications
Authors: Qinshi Wang, Wei Chen
Comments: This is the full version of the paper accepted at NIPS'2017
Subjects: Learning (cs.LG); Machine Learning (stat.ML)
[173]  arXiv:1703.05045 (replaced) [pdf, ps, other]
Title: Average whenever you meet: Opportunistic protocols for community detection
Subjects: Discrete Mathematics (cs.DM); Distributed, Parallel, and Cluster Computing (cs.DC); Social and Information Networks (cs.SI)
[174]  arXiv:1703.05916 (replaced) [pdf, other]
Title: Construction of a Japanese Word Similarity Dataset
Comments: LREC 2018; 4 pages
Subjects: Computation and Language (cs.CL)
[175]  arXiv:1703.10897 (replaced) [pdf, ps, other]
Title: Multi-unit Assignment under Dichotomous Preferences
Authors: Josue Ortega
Comments: 26 pages
Subjects: Economics (q-fin.EC); Computer Science and Game Theory (cs.GT)
[176]  arXiv:1704.01665 (replaced) [pdf, other]
Title: Learning Combinatorial Optimization Algorithms over Graphs
Comments: NIPS 2017
Subjects: Learning (cs.LG); Machine Learning (stat.ML)
[177]  arXiv:1704.07987 (replaced) [pdf, other]
Title: Training L1-Regularized Models with Orthant-Wise Passive Descent Algorithms
Authors: Jianqiao Wangni
Comments: Accepted to The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18). Feb 2018, New Orleans
Subjects: Learning (cs.LG); Machine Learning (stat.ML)
[178]  arXiv:1705.04293 (replaced) [pdf, other]
Title: Bayesian Approaches to Distribution Regression
Comments: Final version to be published at AISTATS 2018
Subjects: Machine Learning (stat.ML); Learning (cs.LG)
[179]  arXiv:1705.10119 (replaced) [pdf, other]
Title: Kernel Implicit Variational Inference
Comments: Published as a conference paper at ICLR 2018
Subjects: Machine Learning (stat.ML); Artificial Intelligence (cs.AI); Learning (cs.LG); Neural and Evolutionary Computing (cs.NE)
[180]  arXiv:1705.10513 (replaced) [pdf, other]
Title: IRGAN: A Minimax Game for Unifying Generative and Discriminative Information Retrieval Models
Comments: 12 pages; appendix added
Subjects: Information Retrieval (cs.IR); Learning (cs.LG)
[181]  arXiv:1706.06491 (replaced) [pdf, other]
Title: Data-Efficient Reinforcement Learning with Probabilistic Model Predictive Control
Comments: Accepted at AISTATS 2018,
Subjects: Systems and Control (cs.SY); Machine Learning (stat.ML)
[182]  arXiv:1706.09339 (replaced) [pdf, other]
Title: Lossy Kernels for Connected Dominating Set on Sparse Graphs
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM)
[183]  arXiv:1707.06315 (replaced) [pdf, other]
Title: FLAME: A Fast Large-scale Almost Matching Exactly Approach to Causal Inference
Subjects: Machine Learning (stat.ML); Databases (cs.DB)
[184]  arXiv:1708.01403 (replaced) [pdf, ps, other]
Title: Optimal Throughput Fairness Trade-offs for Downlink Non-Orthogonal Multiple Access over Fading Channels
Comments: 35 pages, 10 figures, 3 tables, the longer version of the paper with the same title
Subjects: Information Theory (cs.IT); Networking and Internet Architecture (cs.NI)
[185]  arXiv:1709.00402 (replaced) [pdf, other]
Title: Isogeometric analysis of thin Reissner-Mindlin plates and shells: locking phenomena and B-bar method
Comments: 32 pages, 21 figures
Subjects: Computational Engineering, Finance, and Science (cs.CE)
[186]  arXiv:1709.04057 (replaced) [pdf, other]
Title: Parallelizing Linear Recurrent Neural Nets Over Sequence Length
Comments: 9 pages. Published as a conference paper at ICLR 2018
Subjects: Neural and Evolutionary Computing (cs.NE); Artificial Intelligence (cs.AI); Learning (cs.LG)
[187]  arXiv:1709.05188 (replaced) [pdf, other]
Title: Masquer Hunter: Adversarial Occlusion-aware Face Detection
Subjects: Computer Vision and Pattern Recognition (cs.CV)
[188]  arXiv:1709.06758 (replaced) [pdf, other]
Title: A shared latent space matrix factorisation method for recommending new trial evidence for systematic review updates
Comments: Accepted in the Journal of Biomedical Informatics 2018
Journal-ref: J Biomed Inform. 2018
Subjects: Information Retrieval (cs.IR)
[189]  arXiv:1710.02873 (replaced) [pdf]
Title: Foundations of e-Democracy
Authors: Ehud Shapiro
Subjects: Computers and Society (cs.CY)
[190]  arXiv:1710.03322 (replaced) [pdf, other]
Title: XYZ Privacy
Comments: arXiv admin note: text overlap with arXiv:1708.01884
Subjects: Cryptography and Security (cs.CR)
[191]  arXiv:1710.04640 (replaced) [pdf, other]
Title: Hard and Easy Instances of L-Tromino Tilings
Comments: 15 pages, 17 figures. In v2 all theorems were generalized to aztec rectangles and the exposition of most proofs were improved. Also added Manjil P. Saikia as a new coauthor
Subjects: Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
[192]  arXiv:1710.04908 (replaced) [pdf, other]
Title: Graph Convolutional Networks for Classification with a Structured Label Space
Subjects: Learning (cs.LG); Machine Learning (stat.ML)
[193]  arXiv:1710.05373 (replaced) [pdf, other]
Title: Robust Locally-Linear Controllable Embedding
Comments: 13 pages
Subjects: Learning (cs.LG)
[194]  arXiv:1710.07283 (replaced) [pdf, other]
Title: Decomposition of Uncertainty in Bayesian Deep Learning for Efficient and Risk-sensitive Learning
Comments: This paper supersedes arXiv:1706.08495
Subjects: Machine Learning (stat.ML); Learning (cs.LG)
[195]  arXiv:1710.07654 (replaced) [pdf, other]
Title: Deep Voice 3: Scaling Text-to-Speech with Convolutional Sequence Learning
Comments: Published as a conference paper at ICLR 2018. (v3 changed paper title)
Subjects: Sound (cs.SD); Artificial Intelligence (cs.AI); Computation and Language (cs.CL); Learning (cs.LG); Audio and Speech Processing (eess.AS)
[196]  arXiv:1710.08255 (replaced) [pdf, ps, other]
Title: Communication Efficient Checking of Big Data Operations
Subjects: Data Structures and Algorithms (cs.DS); Distributed, Parallel, and Cluster Computing (cs.DC)
[197]  arXiv:1710.08864 (replaced) [pdf, other]
Title: One pixel attack for fooling deep neural networks
Subjects: Learning (cs.LG); Computer Vision and Pattern Recognition (cs.CV); Machine Learning (stat.ML)
[198]  arXiv:1710.08951 (replaced) [pdf, ps, other]
Title: Statistical considerations on limitations of supercomputers
Authors: János Végh
Comments: 10 figures
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC)
[199]  arXiv:1710.10224 (replaced) [pdf, other]
Title: BridgeNets: Student-Teacher Transfer Learning Based on Recursive Neural Networks and its Application to Distant Speech Recognition
Comments: Accepted to 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP 2018)
Subjects: Computation and Language (cs.CL); Sound (cs.SD); Audio and Speech Processing (eess.AS)
[200]  arXiv:1710.10704 (replaced) [pdf, other]
Title: Training Probabilistic Spiking Neural Networks with First-to-spike Decoding
Comments: A shorter version will be published on Proc. IEEE ICASSP 2018
Subjects: Machine Learning (stat.ML); Artificial Intelligence (cs.AI); Information Theory (cs.IT); Learning (cs.LG); Neural and Evolutionary Computing (cs.NE)
[201]  arXiv:1711.00740 (replaced) [pdf, other]
Title: Learning to Represent Programs with Graphs
Comments: Published in ICLR 2018. arXiv admin note: text overlap with arXiv:1705.07867
Subjects: Learning (cs.LG); Artificial Intelligence (cs.AI); Programming Languages (cs.PL); Software Engineering (cs.SE)
[202]  arXiv:1711.03477 (replaced) [pdf, other]
Title: Achievable Rates and Training Overheads for a Measured LOS Massive MIMO Channel
Comments: 4 pages, 5 figures
Journal-ref: IEEE Wireless Communications Letters 2018
Subjects: Information Theory (cs.IT)
[203]  arXiv:1711.05345 (replaced) [pdf, other]
Title: Supervised and Unsupervised Transfer Learning for Question Answering
Comments: Accepted to NAACL HLT 2018 (long paper); camera-ready version
Subjects: Computation and Language (cs.CL)
[204]  arXiv:1711.08198 (replaced) [pdf, other]
Title: A multiobjective deep learning approach for predictive classification in Neuroblastoma
Comments: NIPS ML4H workshop 2017 & MAQC 2018
Subjects: Quantitative Methods (q-bio.QM); Learning (cs.LG)
[205]  arXiv:1711.08824 (replaced) [pdf, ps, other]
Title: The Nearest Neighbor Information Estimator is Adaptively Near Minimax Rate-Optimal
Subjects: Machine Learning (stat.ML); Information Theory (cs.IT)
[206]  arXiv:1712.00070 (replaced) [pdf, other]
Title: When and how much the altruism impacts your privileged information? Proposing a new paradigm in game theory: The boxers game
Comments: 16 pages, 6 figures
Subjects: Statistical Mechanics (cond-mat.stat-mech); Computer Science and Game Theory (cs.GT)
[207]  arXiv:1712.05591 (replaced) [pdf, other]
Title: Dynamic smooth compressed quadtrees (Fullversion)
Comments: Full version of the accepted SOCG submission
Subjects: Computational Geometry (cs.CG)
[208]  arXiv:1712.09203 (replaced) [pdf, ps, other]
Title: Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations
Comments: changed the title and added new results on neural networks with quadratic activations
Subjects: Learning (cs.LG)
[209]  arXiv:1801.01788 (replaced) [pdf, ps, other]
Title: A Reliability Theory of Truth
Authors: Karl Schlechta
Subjects: Artificial Intelligence (cs.AI)
[210]  arXiv:1801.03290 (replaced) [pdf, other]
Title: Efficient Machine-type Communication using Multi-metric Context-awareness for Cars used as Mobile Sensors in Upcoming 5G Networks
Subjects: Networking and Internet Architecture (cs.NI)
[211]  arXiv:1801.04003 (replaced) [pdf, ps, other]
Title: Some techniques in density estimation
Comments: 18 pages; new version includes tight results on mixtures of general Gaussians
Subjects: Statistics Theory (math.ST); Learning (cs.LG)
[212]  arXiv:1801.04504 (replaced) [pdf, other]
Title: Non-Orthogonal Multiple Access for mmWave Drone Networks with Limited Feedback
Subjects: Information Theory (cs.IT)
[213]  arXiv:1801.04695 (replaced) [pdf, other]
Title: Sparsity-based Defense against Adversarial Attacks on Linear Classifiers
Comments: Submitted to IEEE International Symposium on Information Theory (ISIT) 2018. ZM and SG are joint first authors
Subjects: Machine Learning (stat.ML); Information Theory (cs.IT); Learning (cs.LG)
[214]  arXiv:1801.05458 (replaced) [pdf, other]
Title: Deep Network for Simultaneous Decomposition and Classification in UWB-SAR Imagery
Subjects: Image and Video Processing (eess.IV); Computer Vision and Pattern Recognition (cs.CV)
[215]  arXiv:1802.00526 (replaced) [pdf, ps, other]
Title: Toward Optimal Coupon Allocation in Social Networks: An Approximate Submodular Optimization Approach
Authors: Shaojie Tang
Subjects: Social and Information Networks (cs.SI); Computer Science and Game Theory (cs.GT)
[216]  arXiv:1802.01433 (replaced) [pdf, other]
Title: Interactive Grounded Language Acquisition and Generalization in a 2D World
Comments: ICLR 2018
Subjects: Computation and Language (cs.CL); Artificial Intelligence (cs.AI); Learning (cs.LG)
[217]  arXiv:1802.03569 (replaced) [pdf, other]
Title: Riemannian Manifold Kernel for Persistence Diagrams
Authors: Tam Le, Makoto Yamada
Comments: fixed a misleading typo (p.6)
Subjects: Machine Learning (stat.ML); Learning (cs.LG); Algebraic Topology (math.AT)
[218]  arXiv:1802.04587 (replaced) [pdf, other]
Title: Mobility as an Alternative Communication Channel: A Survey
Subjects: Networking and Internet Architecture (cs.NI)
[219]  arXiv:1802.04852 (replaced) [pdf, other]
Title: Persistence Codebooks for Topological Data Analysis
Subjects: Machine Learning (stat.ML); Learning (cs.LG); Algebraic Topology (math.AT)
[220]  arXiv:1802.05465 (replaced) [pdf, other]
Title: Massivizing Computer Systems: a Vision to Understand, Design, and Engineer Computer Ecosystems through and beyond Modern Distributed Systems
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC); Software Engineering (cs.SE)
[221]  arXiv:1802.05544 (replaced) [pdf, ps, other]
Title: Integration in terms of exponential integrals and incomplete gamma functions I
Authors: Waldemar Hebisch
Subjects: Number Theory (math.NT); Symbolic Computation (cs.SC)
[222]  arXiv:1802.06424 (replaced) [pdf, ps, other]
Title: End-to-end Audiovisual Speech Recognition
Comments: Accepted to ICASSP 2018
Subjects: Computer Vision and Pattern Recognition (cs.CV)
[223]  arXiv:1802.06430 (replaced) [pdf, other]
Title: DARTS: Deceiving Autonomous Cars with Toxic Signs
Comments: Submitted to PACM IMWUT;
Subjects: Cryptography and Security (cs.CR); Computer Vision and Pattern Recognition (cs.CV)
[224]  arXiv:1802.06474 (replaced) [pdf, other]
Title: A Closed-form Solution to Photorealistic Image Stylization
Comments: 11 pages, 14 figures
Subjects: Computer Vision and Pattern Recognition (cs.CV)
[225]  arXiv:1802.06767 (replaced) [pdf]
Title: The problem of the development ontology-driven architecture of intellectual software systems
Comments: in Russian; "Bibliography" section updated for correct identification of references by the Google Scholar parser software; 6 pages; 6 figures
Journal-ref: Visnik of the Volodymyr Dahl East ukrainian national university 13 (2011) 179-184 Luhansk
Subjects: Artificial Intelligence (cs.AI)
[226]  arXiv:1802.07375 (replaced) [pdf, ps, other]
Title: Periodicity in Data Streams with Wildcards
Comments: To appear at CSR 2018
Subjects: Data Structures and Algorithms (cs.DS)
[227]  arXiv:1802.07486 (replaced) [pdf, other]
Title: Data-Driven Forecasting of High-Dimensional Chaotic Systems with Long-Short Term Memory Networks
Comments: 25 pages
Subjects: Computational Physics (physics.comp-ph); Learning (cs.LG); Chaotic Dynamics (nlin.CD)
[ total of 227 entries: 1-227 ]
[ showing up to 2000 entries per page: fewer | more ]

Disable MathJax (What is MathJax?)