今日学术视野(2017.10.31)

astro-ph.EP - 地球与行星天体
cs.AI - 人工智能
cs.AR - 硬件体系结构
cs.CL - 计算与语言
cs.CV - 机器视觉与模式识别
cs.CY - 计算与社会
cs.DC - 分布式、并行与集群计算
cs.DL - 数字图书馆
cs.DM - 离散数学
cs.DS - 数据结构与算法
cs.HC - 人机接口
cs.IR - 信息检索
cs.IT - 信息论
cs.LG - 自动学习
cs.NE - 神经与进化计算
cs.RO - 机器人学
cs.SD - 声音处理
cs.SI - 社交网络与信息网络
cs.SY - 系统与控制
eess.SP - 信号处理
math.OC - 优化与控制
math.ST - 统计理论
quant-ph - 量子物理
stat.AP - 应用统计
stat.ME - 统计方法论
stat.ML - (统计)机器学习

• [astro-ph.EP]Exoplanet Atmosphere Retrieval using Multifractal Analysis of Reflectance Spectra
• [cs.AI]Advanced LSTM: A Study about Better Time Dependency Modeling in Emotion Recognition
• [cs.AI]An efficient SAT formulation for learning multiple criteria non-compensatory sorting rules from examples
• [cs.AI]BridgeNets: Student-Teacher Transfer Learning Based on Recursive Neural Networks and its Application to Distant Speech Recognition
• [cs.AI]Distributional Reinforcement Learning with Quantile Regression
• [cs.AI]Enhancements of linked data expressiveness for ontologies
• [cs.AI]On modeling vagueness and uncertainty in data-to-text systems through fuzzy sets
• [cs.AI]Towards a new paradigm for assistive technology at home: research challenges, design issues and performance assessment
• [cs.AR]A Single-Channel Architecture for Algebraic Integer Based 8$\times$8 2-D DCT Computation
• [cs.CL]CANDiS: Coupled & Attention-Driven Neural Distant Supervision
• [cs.CL]Tensor network language model
• [cs.CL]Understanding Grounded Language Learning Agents
• [cs.CV]Beyond Finite Layer Neural Networks: Bridging Deep Architectures and Numerical Differential Equations
• [cs.CV]Deep Learning for Accelerated Ultrasound Imaging
• [cs.CV]Detection and Analysis of Human Emotions through Voice and Speech Pattern Processing
• [cs.CV]Deterministic Approximate Methods for Maximum Consensus Robust Fitting
• [cs.CV]Dual Path Networks for Multi-Person Human Pose Estimation
• [cs.CV]Enhanced Biologically Inspired Model for Image Recognition Based on a Novel Patch Selection Method with Moment
• [cs.CV]Fine-Grained Pattern Matching Over Streaming Time Series
• [cs.CV]High-Quality Facial Photo-Sketch Synthesis Using Multi-Adversarial Networks
• [cs.CV]Image Compression: Sparse Coding vs. Bottleneck Autoencoders
• [cs.CV]Image matting with normalized weight and semi-supervised learning
• [cs.CV]PoseTrack: A Benchmark for Human Pose Estimation and Tracking
• [cs.CV]SEGMENT3D: A Web-based Application for Collaborative Segmentation of 3D images used in the Shoot Apical Meristem
• [cs.CV]SceneFlowFields: Dense Interpolation of Sparse Scene Flow Correspondences
• [cs.CY]An Online Consent Maturity Model: Moving from Acceptable Use towards Ethical Practice
• [cs.CY]Audiovisual Analytics Vocabulary and Ontology (AAVO): initial core and example expansion
• [cs.CY]EduCTX: A blockchain-based higher education credit platform
• [cs.CY]Group Fairness in Multiwinner Voting
• [cs.CY]Incorporating Reality into Social Choice
• [cs.DC]Edge-as-a-Service: Towards Distributed Cloud Architectures
• [cs.DC]Exploiting Commutativity For Practical Fast Replication
• [cs.DL]New Methods for Metadata Extraction from Scientific Literature
• [cs.DM]Convolutional neural networks on irregular domains through approximate translations on inferred graphs
• [cs.DS]External Memory Pipelining Made Easy With TPIE
• [cs.DS]Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes
• [cs.HC]Optimal Crowdsourced Classification with a Reject Option in the Presence of Spammers
• [cs.IR]Combining Aspects of Genetic Algorithms with Weighted Recommender Hybridization
• [cs.IT]Flexible Multi-Group Single-Carrier Modulation: Optimal Subcarrier Grouping and Rate Maximization
• [cs.IT]Low-Complexity Equalization for Orthogonal Time and Frequency Signaling (OTFS)
• [cs.IT]Near-Optimal Straggler Mitigation for Distributed Gradient Methods
• [cs.IT]Optimizing Caching Policy at Base Stations by Exploiting User Preference and Spatial Locality
• [cs.IT]Polar Coding for the Cognitive Interference Channel with Confidential Messages
• [cs.IT]Recovery of Structured Signals with Prior Information via Maximizing Correlation
• [cs.IT]Sequential Empirical Coordination Under an Output Entropy Constraint
• [cs.IT]Sparse recovery using the preservability of the null space property under random measurements
• [cs.LG]Generalization Tower Network: A Novel Deep Neural Network Architecture for Multi-Task Learning
• [cs.LG]Gradient Sparsification for Communication-Efficient Distributed Optimization
• [cs.LG]Improving Deep Learning by Inverse Square Root Linear Units (ISRLUs)
• [cs.LG]Not-So-Random Features
• [cs.LG]Online linear optimization with the log-determinant regularizer
• [cs.LG]SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data
• [cs.LG]Stochastic Conjugate Gradient Algorithm with Variance Reduction
• [cs.LG]The Error Probability of Random Fourier Features is Dimensionality Independent
• [cs.LG]Transform-Invariant Non-Parametric Clustering of Covariance Matrices and its Application to Unsupervised Joint Segmentation and Action Discovery
• [cs.NE]Data-driven Feature Sampling for Deep Hyperspectral Classification and Segmentation
• [cs.NE]Phase Transitions in Image Denoising via Sparsely Coding Convolutional Neural Networks
• [cs.NE]Progressive Growing of GANs for Improved Quality, Stability, and Variation
• [cs.RO]A Decomposition-Based Approach to Reasoning about Free Space Path-Connectivity for Rigid Objects in 2D
• [cs.RO]DoShiCo: a Domain Shift Challenge for Control
• [cs.RO]Inverse Reinforcement Learning Under Noisy Observations
• [cs.RO]RRT-CoLearn: towards kinodynamic planning without numerical trajectory optimization
• [cs.RO]Trajectory Deformations from Physical Human-Robot Interaction
• [cs.SD]Direction of arrival estimation for multiple sound sources using convolutional recurrent neural network
• [cs.SI]Computing the Line Index of Balance Using Integer Programming Optimisation
• [cs.SY]Online Learning of Power Transmission Dynamics
• [eess.SP]Unified Functorial Signal Representation III: Foundations, Redundancy, $L^0$ and $L^2$ functors
• [math.OC]Regularization via Mass Transportation
• [math.OC]Zeroth Order Nonconvex Multi-Agent Optimization over Networks
• [math.ST]Generating global network structures by triad types
• [math.ST]Matrix Completion Methods for Causal Panel Data Models
• [math.ST]On the Optimal Reconstruction of Partially Observed Functional Data
• [math.ST]Quantifying the Estimation Error of Principal Components
• [quant-ph]Optimized quantum f-divergences and data processing
• [stat.AP]Bayesian Nonparametric Models for Biomedical Data Analysis
• [stat.AP]Estimating the coefficients of variation of Freundlich parameters with weighted least squares analysis
• [stat.AP]Single Iteration Conditional Based DSE Considering Spatial and Temporal Correlation
• [stat.ME]Bayesian Pairwise Estimation Under Dependent Informative Sampling
• [stat.ME]Diagonal Likelihood Ratio Test for Equality of Mean Vectors in High-Dimensional Data
• [stat.ME]Evaluation of Treatment Effect Modification by Biomarkers Measured Pre- and Post-randomization in the Presence of Non-monotone Missingness
• [stat.ME]New asymptotic properties for $M$-estimators
• [stat.ML]Energy Clustering
• [stat.ML]On denoising modulo 1 samples of a function

·····································

• [astro-ph.EP]Exoplanet Atmosphere Retrieval using Multifractal Analysis of Reflectance Spectra
Sahil Agarwal, John S. Wettlaufer
http://arxiv.org/abs/1710.09870v1

We extend a data-based model-free multifractal method of exoplanet detection to probe exoplanetary atmospheres. Whereas the transmission spectrum is studied during the primary eclipse, we analyze what we call the reflectance spectrum, which is taken during the secondary eclipse phase, allowing a probe of the atmospheric limb. In addition to the spectral structure of exoplanet atmospheres, the approach provides information on phenomena such as hydrodynamical flows, tidal-locking behavior, and the dayside-nightside redistribution of energy. The approach is demonstrated using Spitzer data for exoplanet HD189733b. The central advantage of the method is the lack of model assumptions in the detection and observational schemes.

• [cs.AI]Advanced LSTM: A Study about Better Time Dependency Modeling in Emotion Recognition
Fei Tao, Gang Liu
http://arxiv.org/abs/1710.10197v1

Long short-term memory (LSTM) is normally used in recurrent neural network (RNN) as basic recurrent unit. However,conventional LSTM assumes that the state at current time step depends on previous time step. This assumption constraints the time dependency modeling capability. In this study, we propose a new variation of LSTM, advanced LSTM (A-LSTM), for better temporal context modeling. We employ A-LSTM in weighted pooling RNN for emotion recognition. The A-LSTM outperforms the conventional LSTM by 5.5% relatively. The A-LSTM based weighted pooling RNN can also complement the state-of-the-art emotion classification framework. This shows the advantage of A-LSTM.

• [cs.AI]An efficient SAT formulation for learning multiple criteria non-compensatory sorting rules from examples
K. Belahcène, C. Labreuche, N. Maudet, V. Mousseau, W. Ouerdane
http://arxiv.org/abs/1710.10098v1

The literature on Multiple Criteria Decision Analysis (MCDA) proposes several methods in order to sort alternatives evaluated on several attributes into ordered classes. Non Compensatory Sorting models (NCS) assign alternatives to classes based on the way they compare to multicriteria profiles separating the consecutive classes. Previous works have proposed approaches to learn the parameters of a NCS model based on a learning set. Exact approaches based on mixed integer linear programming ensures that the learning set is best restored, but can only handle datasets of limited size. Heuristic approaches can handle large learning sets, but do not provide any guarantee about the inferred model. In this paper, we propose an alternative formulation to learn a NCS model. This formulation, based on a SAT problem, guarantees to find a model fully consistent with the learning set (whenever it exists), and is computationally much more efficient than existing exact MIP approaches.

• [cs.AI]BridgeNets: Student-Teacher Transfer Learning Based on Recursive Neural Networks and its Application to Distant Speech Recognition
Jaeyoung Kim, Mostafa El-Khamy, Jungwon Lee
http://arxiv.org/abs/1710.10224v1

Despite the remarkable progress achieved on automatic speech recognition, recognizing far-field speeches mixed with various noise sources is still a challenging task. In this paper, we introduce novel student-teacher transfer learning, BridgeNet which can provide a solution to improve distant speech recognition. There are two key features in BridgeNet. First, BridgeNet extends traditional student-teacher frameworks by providing multiple hints from a teacher network. Hints are not limited to the soft labels from a teacher network. Teacher's intermediate feature representations can better guide a student network to learn how to denoise or dereverberate noisy input. Second, the proposed recursive architecture in the BridgeNet can iteratively improve denoising and recognition performance. The experimental results of BridgeNet showed significant improvements in tackling the distant speech recognition problem, where it achieved up to 13.24% relative WER reductions on AMI corpus compared to a baseline neural network without teacher's hints.

• [cs.AI]Distributional Reinforcement Learning with Quantile Regression
Will Dabney, Mark Rowland, Marc G. Bellemare, Rémi Munos
http://arxiv.org/abs/1710.10044v1

In reinforcement learning an agent interacts with the environment by taking actions and observing the next state and reward. When sampled probabilistically, these state transitions, rewards, and actions can all induce randomness in the observed long-term return. Traditionally, reinforcement learning algorithms average over this randomness to estimate the value function. In this paper, we build on recent work advocating a distributional approach to reinforcement learning in which the distribution over returns is modeled explicitly instead of only estimating the mean. That is, we examine methods of learning the value distribution instead of the value function. We give results that close a number of gaps between the theoretical and algorithmic results given by Bellemare, Dabney, and Munos (2017). First, we extend existing results to the approximate distribution setting. Second, we present a novel distributional reinforcement learning algorithm consistent with our theoretical formulation. Finally, we evaluate this new algorithm on the Atari 2600 games, observing that it significantly outperforms many of the recent improvements on DQN, including the related distributional algorithm C51.

• [cs.AI]Enhancements of linked data expressiveness for ontologies
Renato Fabbri
http://arxiv.org/abs/1710.09952v1

The semantic web has received many contributions of researchers as ontologies which, in this context, i.e. within RDF linked data, are formalized conceptualizations that might use different protocols, such as RDFS, OWL DL and OWL FULL. In this article, we describe new expressive techniques which were found necessary after elaborating dozens of OWL ontologies for the scientific academy, the State and the civil society. They consist in: 1) stating possible uses a property might have without incurring into axioms or restrictions; 2) assigning a level of priority for an element (class, property, triple); 3) correct depiction in diagrams of relations between classes, between individuals which are imperative, and between individuals which are optional; 4) a convenient association between OWL classes and SKOS concepts. We propose specific rules to accomplish these enhancements and exemplify both its use and the difficulties that arise because these techniques are currently not established as standards to the ontology designer.

• [cs.AI]On modeling vagueness and uncertainty in data-to-text systems through fuzzy sets
A. Ramos-Soto, M. Pereira-Fariña
http://arxiv.org/abs/1710.10093v1

Vagueness and uncertainty management is counted among one of the challenges that remain unresolved in systems that generate texts from non-linguistic data, known as data-to-text systems. In the last decade, work in fuzzy linguistic summarization and description of data has raised the interest of using fuzzy sets to model and manage the imprecision of human language in data-to-text systems. However, despite some research in this direction, there has not been an actual clear discussion and justification on how fuzzy sets can contribute to data-to-text for modeling vagueness and uncertainty in words and expressions. This paper intends to bridge this gap by answering the following questions: What does vagueness mean in fuzzy sets theory? What does vagueness mean in data-to-text contexts? In what ways can fuzzy sets theory contribute to improve data-to-text systems? What are the challenges that researchers from both disciplines need to address for a successful integration of fuzzy sets into data-to-text systems? In what cases should the use of fuzzy sets be avoided in D2T? For this, we review and discuss the state of the art of vagueness modeling in natural language generation and data-to-text, describe potential and actual usages of fuzzy sets in data-to-text contexts, and provide some additional insights about the engineering of data-to-text systems that make use of fuzzy set-based techniques.

• [cs.AI]Towards a new paradigm for assistive technology at home: research challenges, design issues and performance assessment
Luca Buoncompagni, Barbara Bruno, Antonella Giuni, Fulvio Mastrogiovanni, Renato Zaccaria
http://arxiv.org/abs/1710.10164v1

Providing elderly and people with special needs, including those suffering from physical disabilities and chronic diseases, with the possibility of retaining their independence at best is one of the most important challenges our society is expected to face. Assistance models based on the home care paradigm are being adopted rapidly in almost all industrialized and emerging countries. Such paradigms hypothesize that it is necessary to ensure that the so-called Activities of Daily Living are correctly and regularly performed by the assisted person to increase the perception of an improved quality of life. This chapter describes the computational inference engine at the core of Arianna, a system able to understand whether an assisted person performs a given set of ADL and to motivate him/her in performing them through a speech-mediated motivational dialogue, using a set of nearables to be installed in an apartment, plus a wearable to be worn or fit in garments.

• [cs.AR]A Single-Channel Architecture for Algebraic Integer Based 8$\times$8 2-D DCT Computation
A. Edirisuriya, A. Madanayake, R. J. Cintra, V. S. Dimitrov
http://arxiv.org/abs/1710.09975v1

An area efficient row-parallel architecture is proposed for the real-time implementation of bivariate algebraic integer (AI) encoded 2-D discrete cosine transform (DCT) for image and video processing. The proposed architecture computes 8$\times$8 2-D DCT transform based on the Arai DCT algorithm. An improved fast algorithm for AI based 1-D DCT computation is proposed along with a single channel 2-D DCT architecture. The design improves on the 4-channel AI DCT architecture that was published recently by reducing the number of integer channels to one and the number of 8-point 1-D DCT cores from 5 down to 2. The architecture offers exact computation of 8$\times$8 blocks of the 2-D DCT coefficients up to the FRS, which converts the coefficients from the AI representation to fixed-point format using the method of expansion factors. Prototype circuits corresponding to FRS blocks based on two expansion factors are realized, tested, and verified on FPGA-chip, using a Xilinx Virtex-6 XC6VLX240T device. Post place-and-route results show a 20% reduction in terms of area compared to the 2-D DCT architecture requiring five 1-D AI cores. The area-time and area-time${}^2$ complexity metrics are also reduced by 23% and 22% respectively for designs with 8-bit input word length. The digital realizations are simulated up to place and route for ASICs using 45 nm CMOS standard cells. The maximum estimated clock rate is 951 MHz for the CMOS realizations indicating 7.608$\cdot$10$^9$ pixels/seconds and a 8$\times$8 block rate of 118.875 MHz.

• [cs.CL]CANDiS: Coupled & Attention-Driven Neural Distant Supervision
Tushar Nagarajan, Sharmistha, Partha Talukdar
http://arxiv.org/abs/1710.09942v1

Distant Supervision for Relation Extraction uses heuristically aligned text data with an existing knowledge base as training data. The unsupervised nature of this technique allows it to scale to web-scale relation extraction tasks, at the expense of noise in the training data. Previous work has explored relationships among instances of the same entity-pair to reduce this noise, but relationships among instances across entity-pairs have not been fully exploited. We explore the use of inter-instance couplings based on verb-phrase and entity type similarities. We propose a novel technique, CANDiS, which casts distant supervision using inter-instance coupling into an end-to-end neural network model. CANDiS incorporates an attention module at the instance-level to model the multi-instance nature of this problem. CANDiS outperforms existing state-of-the-art techniques on a standard benchmark dataset.

• [cs.CL]Tensor network language model
Vasily Pestun, Yiannis Vlassopoulos
http://arxiv.org/abs/1710.10248v1

We propose a new statistical model suitable for machine learning tasks of systems with long distance correlations such as human languages. The model is based on directed acyclic graph decorated by multi-linear tensor maps in the vertices and vector spaces in the edges, called tensor network. Such tensor networks have been previously employed for effective numerical computation of the renormalization group flow on the space of effective quantum field theories and lattice models of statistical mechanics. We provide explicit algebro-geometric analysis of the parameter moduli space for tree graphs, discuss model properties and applications such as statistical translation.

• [cs.CL]Understanding Grounded Language Learning Agents
Felix Hill, Karl Moritz Hermann, Phil Blunsom, Stephen Clark
http://arxiv.org/abs/1710.09867v1

Neural network-based systems can now learn to locate the referents of words and phrases in images, answer questions about visual scenes, and even execute symbolic instructions as first-person actors in partially-observable worlds. To achieve this so-called grounded language learning, models must overcome certain well-studied learning challenges that are also fundamental to infants learning their first words. While it is notable that models with no meaningful prior knowledge overcome these learning obstacles, AI researchers and practitioners currently lack a clear understanding of exactly how they do so. Here we address this question as a way of achieving a clearer general understanding of grounded language learning, both to inform future research and to improve confidence in model predictions. For maximum control and generality, we focus on a simple neural network-based language learning agent trained via policy-gradient methods to interpret synthetic linguistic instructions in a simulated 3D world. We apply experimental paradigms from developmental psychology to this agent, exploring the conditions under which established human biases and learning effects emerge. We further propose a novel way to visualise and analyse semantic representation in grounded language learning agents that yields a plausible computational account of the observed effects.

• [cs.CV]Beyond Finite Layer Neural Networks: Bridging Deep Architectures and Numerical Differential Equations
Yiping Lu, Aoxiao Zhong, Quanzheng Li, Bin Dong
http://arxiv.org/abs/1710.10121v1

In our work, we bridge deep neural network design with numerical differential equations. We show that many effective networks, such as ResNet, PolyNet, FractalNet and RevNet, can be interpreted as different numerical discretizations of differential equations. This finding brings us a brand new perspective on the design of effective deep architectures. We can take advantage of the rich knowledge in numerical analysis to guide us in designing new and potentially more effective deep networks. As an example, we propose a linear multi-step architecture (LM-architecture) which is inspired by the linear multi-step method solving ordinary differential equations. The LM-architecture is an effective structure that can be used on any ResNet-like networks. In particular, we demonstrate that LM-ResNet and LM-ResNeXt (i.e. the networks obtained by applying the LM-architecture on ResNet and ResNeXt respectively) can achieve noticeably higher accuracy than ResNet and ResNeXt on both CIFAR and ImageNet with comparable numbers of trainable parameters. In particular, on both CIFAR and ImageNet, LM-ResNet/LM-ResNeXt can significantly compress ($>50$%) the original networks while maintaining a similar performance. This can be explained mathematically using the concept of modified equation from numerical analysis. Last but not least, we also establish a connection between stochastic control and noise injection in the training process which helps to improve generalization of the networks. Furthermore, by relating stochastic training strategy with stochastic dynamic system, we can easily apply stochastic training to the networks with the LM-architecture. As an example, we introduced stochastic depth to LM-ResNet and achieve significant improvement over the original LM-ResNet on CIFAR10.

• [cs.CV]Deep Learning for Accelerated Ultrasound Imaging
Yeo Hun Yoon, Jong Chul Ye
http://arxiv.org/abs/1710.10006v1

In portable, 3-D, or ultra-fast ultrasound (US) imaging systems, there is an increasing demand to reconstruct high quality images from limited number of data. However, the existing solutions require either hardware changes or computationally expansive algorithms. To overcome these limitations, here we propose a novel deep learning approach that interpolates the missing RF data by utilizing the sparsity of the RF data in the Fourier domain. Extensive experimental results from sub-sampled RF data from a real US system confirmed that the proposed method can effectively reduce the data rate without sacrificing the image quality.

• [cs.CV]Detection and Analysis of Human Emotions through Voice and Speech Pattern Processing
Poorna Banerjee Dasgupta
http://arxiv.org/abs/1710.10198v1

The ability to modulate vocal sounds and generate speech is one of the features which set humans apart from other living beings. The human voice can be characterized by several attributes such as pitch, timbre, loudness, and vocal tone. It has often been observed that humans express their emotions by varying different vocal attributes during speech generation. Hence, deduction of human emotions through voice and speech analysis has a practical plausibility and could potentially be beneficial for improving human conversational and persuasion skills. This paper presents an algorithmic approach for detection and analysis of human emotions with the help of voice and speech processing. The proposed approach has been developed with the objective of incorporation with futuristic artificial intelligence systems for improving human-computer interactions.

• [cs.CV]Deterministic Approximate Methods for Maximum Consensus Robust Fitting
Huu Le, Tat-Jun Chin, Anders Eriksson, David Suter
http://arxiv.org/abs/1710.10003v1

Maximum consensus estimation plays a critically important role in robust fitting problems in computer vision. Currently, the most prevalent algorithms for consensus maximization draw from the class of randomized hypothesize-and-verify algorithms, which are cheap but can usually deliver only rough approximate solutions. On the other extreme, there are exact algorithms which are exhaustive search in nature and can be costly for practical-sized inputs. This paper fills the gap between the two extremes by proposing deterministic algorithms to approximately optimize the maximum consensus criterion. Our work begins by reformulating consensus maximization with linear complementarity constraints. Then, we develop two novel algorithms: one based on non-smooth penalty method with a Frank-Wolfe style optimization scheme, the other based on the Alternating Direction Method of Multipliers (ADMM). Both algorithms solve convex subproblems to efficiently perform the optimization. We demonstrate the capability of our algorithms to greatly improve a rough initial estimate, such as those obtained using least squares or a randomized algorithm. Compared to the exact algorithms, our approach is much more practical on realistic input sizes. Further, our approach is naturally applicable to estimation problems with geometric residuals

• [cs.CV]Dual Path Networks for Multi-Person Human Pose Estimation
Guanghan Ning, Zhihai He
http://arxiv.org/abs/1710.10192v1

The task of multi-person human pose estimation in natural scenes is quite challenging. Existing methods include both top-down and bottom-up approaches. The main advantage of bottom-up methods is its excellent tradeoff between estimation accuracy and computational cost. We follow this path and aim to design smaller, faster, and more accurate neural networks for the regression of keypoints and limb association vectors. These two regression tasks are naturally dependent on each other. In this work, we propose a dual-path network specially designed for multi-person human pose estimation, and compare our performance with the openpose network in aspects of model size, forward speed, and estimation accuracy.

• [cs.CV]Enhanced Biologically Inspired Model for Image Recognition Based on a Novel Patch Selection Method with Moment
Yan-Feng Lu, Li-Hao Jia, Hong Qaio, Yi Li
http://arxiv.org/abs/1710.10188v1

Biologically inspired model (BIM) for image recognition is a robust computational architecture, which has attracted widespread attention. BIM can be described as a four-layer structure based on the mechanisms of the visual cortex. Although the performance of BIM for image recognition is robust, it takes the randomly selected ways for the patch selection, which is sightless, and results in heavy computing burden. To address this issue, we propose a novel patch selection method with oriented Gaussian-Hermite moment (PSGHM), and we enhanced the BIM based on the proposed PSGHM, named as PBIM. In contrast to the conventional BIM which adopts the random method to select patches within the feature representation layers processed by multi-scale Gabor filter banks, the proposed PBIM takes the PSGHM way to extract a small number of representation features while offering promising distinctiveness. To show the effectiveness of the proposed PBIM, experimental studies on object categorization are conducted on the CalTech05, TU Darmstadt (TUD), and GRAZ01 databases. Experimental results demonstrate that the performance of PBIM is a significant improvement on that of the conventional BIM.

• [cs.CV]Fine-Grained Pattern Matching Over Streaming Time Series
Rong Kang, Chen Wang, Peng Wang, Yuting Ding, Jianmin Wang
http://arxiv.org/abs/1710.10088v1

Processing of streaming time series data from sensors with lower latency and limited computing resource comes to a critical problem as the growth of Industry 4.0 and Industry Internet of Things(IIoT). To tackle the real world challenge in this area, like equipment health monitoring by comparing the incoming data stream with known fault patterns, we formulate a new problem, called "fine-grained pattern matching". It allows users to define varied deviations to different segments of a given pattern, and fuzzy breakpoint of adjunct segments, which urges the dramatically increased complexity against traditional pattern matching problem over stream. In this paper, we propose a novel 2-phase approach to solve this problem. In pruning phase, we propose ELB(Equal Length Block) Representation and BSP (Block-Skipping Pruning) policy, which efficiently filter the unmatched subsequence with the guarantee of no-false dismissals. In post-processing phase, we provide an algorithm to further examine the possible matches in linear complexity. We conducted an extensive experimental evaluation on synthetic and real-world datasets, which illustrates that our algorithm outperforms the brute-force method and MSM, a multi-step filter mechanism over the multi-scaled representation, by orders of magnitude.

• [cs.CV]High-Quality Facial Photo-Sketch Synthesis Using Multi-Adversarial Networks
Lidan Wang, Vishwanath A. Sindagi, Vishal M. Patel
http://arxiv.org/abs/1710.10182v1

Synthesizing face sketches from real photos and its inverse are well studied problems and they have many applications in digital forensics and entertainment. However, photo/sketch synthesis remains a challenging problem due to the fact that photo and sketch have different characteristics. In this work, we consider this task as an image-to-image translation problem and explore the recently popular generative models (GANs) to generate high-quality realistic photos from sketches and sketches from photos. Recent methods such as Pix2Pix, CycleGAN and DualGAN have shown promising results on image-to-image translation problems and photo-to-sketch synthesis in particular, however, they are known to have limited abilities in generating high-resolution realistic images. To this end, we propose a novel synthesis framework called Photo-Sketch Synthesis using Multi-Adversarial Networks, (PS\textsuperscript{2}-MAN) that iteratively generates low resolution to high resolution images in an adversarial way. The hidden layers of the generator are supervised to first generate lower resolution images followed by implicit refinement in the network to generate higher resolution images. Furthermore, since photo-sketch synthesis is a coupled/paired translation problem where photo-sketch and sketch-photo are equally important, we leverage the pair information in the CycleGAN framework. Evaluation of the proposed method is performed on two datasets: CUHK and CUFSF. Both Image Quality Assessment (IQA) and Photo-Sketch Matching experiments are conducted to demonstrate the superior performance of our framework in comparison to existing state-of-the-art solutions. Additionally, ablation studies are conducted to verify the effectiveness iterative synthesis and various loss functions.

• [cs.CV]Image Compression: Sparse Coding vs. Bottleneck Autoencoders
Yijing Watkins, Mohammad Sayeh, Oleksandr Iaroshenko, Garrett Kenyon
http://arxiv.org/abs/1710.09926v1

Bottleneck autoencoders have been actively researched as a solution to image compression tasks. In this work, we explore the ability of sparse coding to improve reconstructed image quality for the same degree of compression. We observe that sparse image compression provides qualitatively superior visual quality of reconstructed images but has lower values of PSNR and SSIM compared to bottleneck autoencoders. We hypothesized that there should be another evaluational criterion to support our subjective observations. To test this hypothesis, we fed reconstructed images from both the bottleneck autoencoder and sparse coding into a DCNN classifier and discovered that the images reconstructed from the sparse coding compression obtained on average 1.5% higher classification accuracy compared to bottleneck autoencoders, implying that sparse coding preserves more content-relevant information.

• [cs.CV]Image matting with normalized weight and semi-supervised learning
Ping Li, Tingyan Duan, Yongfeng Cao
http://arxiv.org/abs/1710.10101v1

Image matting is an important vision problem. The main stream methods for it combine sampling-based methods and propagation-based methods. In this paper, we deal with the combination with a normalized weighting parameter, which could well control the relative relationship between information from sampling and from propagation. A reasonable value range for this parameter is given based on statistics from the standard benchmark dataset. The matting is further improved by introducing semi-supervised learning iterations, which automatically refine the trimap without user's interaction. This is especially beneficial when the trimap is coarse. The experimental results on standard benchmark dataset have shown that both the normalized weighting parameter and the semi-supervised learning iteration could significantly improve the matting performance.

• [cs.CV]PoseTrack: A Benchmark for Human Pose Estimation and Tracking
Mykhaylo Andriluka, Umar Iqbal, Anton Milan, Eldar Insafutdinov, Leonid Pishchulin, Juergen Gall, Bernt Schiele
http://arxiv.org/abs/1710.10000v1

Human poses and motions are important cues for analysis of videos with people and there is strong evidence that representations based on body pose are highly effective for a variety of tasks such as activity recognition, content retrieval and social signal processing. In this work, we aim to further advance the state of the art by establishing "PoseTrack" , a new large-scale benchmark for video-based human pose estimation and articulated tracking, and bringing together the community of researchers working on visual human analysis. The benchmark encompasses three competition tracks focusing on i) single-frame multi-person pose estimation, ii) multi-person pose estimation in videos, and iii) multi-person articulated tracking. To facilitate the benchmark and challenge we collect, annotate and release a new %large-scale benchmark dataset that features videos with multiple people labeled with person tracks and articulated pose. A centralized evaluation server is provided to allow participants to evaluate on a held-out test set. We envision that the proposed benchmark will stimulate productive research both by providing a large and representative training dataset as well as providing a platform to objectively evaluate and compare the proposed methods. The benchmark is freely accessible at https://posetrack.net.

• [cs.CV]SEGMENT3D: A Web-based Application for Collaborative Segmentation of 3D images used in the Shoot Apical Meristem
Thiago V. Spina, Johannes Stegmaier, Alexandre X. Falcão, Elliot Meyerowitz, Alexandre Cunha
http://arxiv.org/abs/1710.09933v1

The quantitative analysis of 3D confocal microscopy images of the shoot apical meristem helps understanding the growth process of some plants. Cell segmentation in these images is crucial for computational plant analysis and many automated methods have been proposed. However, variations in signal intensity across the image mitigate the effectiveness of those approaches with no easy way for user correction. We propose a web-based collaborative 3D image segmentation application, SEGMENT3D, to leverage automatic segmentation results. The image is divided into 3D tiles that can be either segmented interactively from scratch or corrected from a pre-existing segmentation. Individual segmentation results per tile are then automatically merged via consensus analysis and then stitched to complete the segmentation for the entire image stack. SEGMENT3D is a comprehensive application that can be applied to other 3D imaging modalities and general objects. It also provides an easy way to create supervised data to advance segmentation using machine learning models.

• [cs.CV]SceneFlowFields: Dense Interpolation of Sparse Scene Flow Correspondences
René Schuster, Oliver Wasenmüller, Georg Kuschk, Christian Bailer, Didier Stricker
http://arxiv.org/abs/1710.10096v1

While most scene flow methods use either variational optimization or a strong rigid motion assumption, we show for the first time that scene flow can also be estimated by dense interpolation of sparse matches. To this end, we find sparse matches across two stereo image pairs that are detected without any prior regularization and perform dense interpolation preserving geometric and motion boundaries by using edge information. A few iterations of variational energy minimization are performed to refine our results, which are thoroughly evaluated on the KITTI benchmark and additionally compared to state-of-the-art on MPI Sintel. For application in an automotive context, we further show that an optional ego-motion model helps to boost performance and blends smoothly into our approach to produce a segmentation of the scene into static and dynamic parts.

• [cs.CY]An Online Consent Maturity Model: Moving from Acceptable Use towards Ethical Practice
Vivien M. Rooney, Simon N. Foley
http://arxiv.org/abs/1710.10022v1

The particular characteristics associated with qualitative longitudinal research in the disciplines of psychology and social science have prompted the development of informed consent. There are analogies between these characteristics and the collection and analysis of data in online settings. How and why informed consent has developed in qualitative longitudinal research, both theoretically and practically, can provide a useful resource for considering what informed consent means in online settings. Building on this analogy, criteria are proposed that can be used to provide an ethical judgement on consent practices in an online data handling activity, and form the basis for a consent maturity model. It is argued that if we are to learn from from the history of informed consent in qualitative longitudinal research, then we should strive for an Ethics of Virtue approach to informed consent online, the highest level of maturity.

• [cs.CY]Audiovisual Analytics Vocabulary and Ontology (AAVO): initial core and example expansion
Renato Fabbri, Maria Cristina Ferreira de Oliveira
http://arxiv.org/abs/1710.09954v1

Visual Analytics might be defined as data mining assisted by interactive visual interfaces. The field has been receiving prominent consideration by researchers, developers and the industry. The literature, however, is complex because it involves multiple fields of knowledge and is considerably recent. In this article we describe an initial tentative organization of the knowledge in the field as an OWL ontology and a SKOS vocabulary. This effort might be useful in many ways that include conceptual considerations and software implementations. Within the results and discussions, we expose a core and an example expansion of the conceptualization, and incorporate design issues that enhance the expressive power of the abstraction.

• [cs.CY]EduCTX: A blockchain-based higher education credit platform
Muhamed Turkanović, Marko Hölbl, Kristjan Košič, Marjan Heričko, Aida Kamišalić
http://arxiv.org/abs/1710.09918v1

Blockchain technology enables the creation of a decentralized environment where transactions and data are not under the control of any third party organization. Any transaction ever completed is recorded in a public ledger in a verifiable and permanent way. Based on blockchain technology, we propose a global higher education credit platform, named EduCTX. This platform is based on the concept of the European Credit Transfer and Accumulation System (ECTS). It constitutes a globally trusted, decentralized higher education credit and grading system that can offer a globally unified viewpoint for students and higher education institutions (HEIs), as well as for other potential stakeholders such as companies, institutions, and organizations. As a proof of concept, we present a prototype implementation of the environment, based on the open-source Ark Blockchain Platform. Based on a globally distributed peer-to-peer network, EduCTX will process, manage and control ECTX tokens, which represent credits that students gain for completed courses such as ECTS. HEIs are the peers of the blockchain network. The platform is a first step towards a more transparent and technologically advanced form of higher education systems. The EduCTX platform represents the basis of the EduCTX initiative which anticipates that various HEIs would join forces in order to create a globally efficient, simplified and ubiquitous environment in order to avoid language and administrative barriers. Therefore we invite and encourage HEIs to join the EduCTX initiative and the EduCTX blockchain network.

• [cs.CY]Group Fairness in Multiwinner Voting
L. Elisa Celis, Lingxiao Huang, Nisheeth K. Vishnoi
http://arxiv.org/abs/1710.10057v1

We study multiwinner voting problems when there is an additional requirement that the selected committee should be fair with respect to attributes such as gender, ethnicity, or political parties. Every setting of an attribute gives rise to a group, and the goal is to ensure that each group is neither over nor under represented in the selected committee. Prior work has largely focused on designing specialized score functions that lead to a precise level of representation with respect to disjoint attributes (e.g., only political affiliation). Here we propose a general algorithmic framework that allows the use of any score function and can guarantee flexible notions of fairness with respect to multiple, non-disjoint attributes (e.g., political affiliation and gender). Technically, we study the complexity of this constrained multiwinner voting problem subject to group-fairness constraints for monotone submodular score functions. We present approximation algorithms and hardness of approximation results for various attribute set structures and score functions.

• [cs.CY]Incorporating Reality into Social Choice
Ehud Shapiro, Nimrod Talmon
http://arxiv.org/abs/1710.10117v1

When voting on a proposal one in fact chooses between two alternatives: (i) A new hypothetical social state depicted by the proposal and (ii) the status quo (henceforth: Reality); a Yes vote favors a transition to the proposed hypothetical state, while a No vote favors Reality. Social Choice theory generalizes voting on one proposal to ranking multiple proposed alternatives; we remorse that during this generalization, Reality was neglected.Here we propose to rectify this state of affairs by incorporating Reality into Social Choice. We do so by (i) recognizing Reality as an ever-present distinguished social state and (ii) always including Reality as one of the social states under consideration or vote (elections in which the incumbent is not running for reelection being a special case). We argue that incorporating Reality into Social Choice is natural and useful and that many scenarios are not treated correctly in its absence. We show that incorporating Reality into Social Choice necessitates revisiting its foundation, as Arrow's theorem and the Condorcet voting paradox do not carry over. We then discuss the plethora of research directions opened by taking Reality into consideration: New models of Social Choice (we discuss two such models); new axioms (we discuss one such axiom); new voting rules (we mention one such rule); new types of domain restrictions; and new game-theoretic questions related to strategic voting (we discuss one such game). Arrow's theorem was taken to show that democracy, conceived as government by the will of the people, is an incoherent illusion. As Reality-aware Social Choice renders Arrow's theorem vacuous and resolves the Condorcet voting paradox, it may clear this intellectual blemish on democracy; pave the way for a broad application of ranked voting according to the Condorcet criterion; and, more generally, may help restore trust in democracy.

• [cs.DC]Edge-as-a-Service: Towards Distributed Cloud Architectures
Blesson Varghese, Nan Wang, Jianyu Li, Dimitrios S. Nikolopoulos
http://arxiv.org/abs/1710.10090v1

We present an Edge-as-a-Service (EaaS) platform for realising distributed cloud architectures and integrating the edge of the network in the computing ecosystem. The EaaS platform is underpinned by (i) a lightweight discovery protocol that identifies edge nodes and make them publicly accessible in a computing environment, and (ii) a scalable resource provisioning mechanism for offloading workloads from the cloud on to the edge for servicing multiple user requests. We validate the feasibility of EaaS on an online game use-case to highlight the improvement in the QoS of the application hosted on our cloud-edge platform. On this platform we demonstrate (i) low overheads of less than 6%, (ii) reduced data traffic to the cloud by up to 95% and (iii) minimised application latency between 40%-60%.

• [cs.DC]Exploiting Commutativity For Practical Fast Replication
Seo Jin Park, John Ousterhout
http://arxiv.org/abs/1710.09921v1

Traditional approaches to replication require client requests to be ordered before making them durable by copying them to replicas. As a result, clients must wait for two round-trip times (RTTs) before updates complete. In this paper, we show that this entanglement of ordering and durability is unnecessary for strong consistency. Consistent Unordered Replication Protocol (CURP) allows clients to replicate requests that have not yet been ordered, as long as they are commutative. This strategy allows most operations to complete in 1 RTT (the same as an unreplicated system). We implemented CURP in the Redis and RAMCloud storage systems. In RAMCloud, CURP improved write latency by ~2x (13.8 us -> 7.3 us) and write throughput by 4x. Compared to unreplicated RAMCloud, CURP's latency overhead for 3-way replication is just 0.4 us (6.9 us vs 7.3 us). CURP transformed a non-durable Redis cache into a consistent and durable storage system with only a small performance overhead.

• [cs.DL]New Methods for Metadata Extraction from Scientific Literature
Dominika Tkaczyk
http://arxiv.org/abs/1710.10201v1

Within the past few decades we have witnessed digital revolution, which moved scholarly communication to electronic media and also resulted in a substantial increase in its volume. Nowadays keeping track with the latest scientific achievements poses a major challenge for the researchers. Scientific information overload is a severe problem that slows down scholarly communication and knowledge propagation across the academia. Modern research infrastructures facilitate studying scientific literature by providing intelligent search tools, proposing similar and related documents, visualizing citation and author networks, assessing the quality and impact of the articles, and so on. In order to provide such high quality services the system requires the access not only to the text content of stored documents, but also to their machine-readable metadata. Since in practice good quality metadata is not always available, there is a strong demand for a reliable automatic method of extracting machine-readable metadata directly from source documents. This research addresses these problems by proposing an automatic, accurate and flexible algorithm for extracting wide range of metadata directly from scientific articles in born-digital form. Extracted information includes basic document metadata, structured full text and bibliography section. Designed as a universal solution, proposed algorithm is able to handle a vast variety of publication layouts with high precision and thus is well-suited for analyzing heterogeneous document collections. This was achieved by employing supervised and unsupervised machine-learning algorithms trained on large, diverse datasets. The evaluation we conducted showed good performance of proposed metadata extraction algorithm. The comparison with other similar solutions also proved our algorithm performs better than competition for most metadata types.

• [cs.DM]Convolutional neural networks on irregular domains through approximate translations on inferred graphs
Bastien Pasdeloup, Vincent Gripon, Jean-Charles Vialatte, Dominique Pastor
http://arxiv.org/abs/1710.10035v1

We propose a generalization of convolutional neural networks (CNNs) to irregular domains, through the use of an inferred graph structure. In more details, we introduce a three-step methodology to create convolutional layers that are adapted to the signals to process: 1) From a training set of signals, infer a graph representing the topology on which they evolve; 2) Identify translation operators in the vertex domain; 3) Emulate a convolution operator by translating a localized kernel on the graph. Using these layers, a convolutional neural network is built, and is trained on the initial signals to perform a classification task. Contributions are twofold. First, we adapt a definition of translations on graphs to make them more robust to irregularities, and to take into account locality of the kernel. Second, we introduce a procedure to build CNNs from data. We apply our methodology on a scrambled version of the CIFAR-10 and Haxby datasets. Without using any knowledge on the signals, we significantly outperform existing methods. Moreover, our approach extends classical CNNs on images in the sense that such networks are a particular case of our approach when the inferred graph is a grid.

• [cs.DS]External Memory Pipelining Made Easy With TPIE
Lars Arge, Mathias Rav, Svend C. Svendsen, Jakob Truelsen
http://arxiv.org/abs/1710.10091v1

When handling large datasets that exceed the capacity of the main memory, movement of data between main memory and external memory (disk), rather than actual (CPU) computation time, is often the bottleneck in the computation. Since data is moved between disk and main memory in large contiguous blocks, this has led to the development of a large number of I/O-efficient algorithms that minimize the number of such block movements. TPIE is one of two major libraries that have been developed to support I/O-efficient algorithm implementations. TPIE provides an interface where list stream processing and sorting can be implemented in a simple and modular way without having to worry about memory management or block movement. However, if care is not taken, such streaming-based implementations can lead to practically inefficient algorithms since lists of data items are typically written to (and read from) disk between components. In this paper we present a major extension of the TPIE library that includes a pipelining framework that allows for practically efficient streaming-based implementations while minimizing I/O-overhead between streaming components. The framework pipelines streaming components to avoid I/Os between components, that is, it processes several components simultaneously while passing output from one component directly to the input of the next component in main memory. TPIE automatically determines which components to pipeline and performs the required main memory management, and the extension also includes support for parallelization of internal memory computation and progress tracking across an entire application. The extended library has already been used to evaluate I/O-efficient algorithms in the research literature and is heavily used in I/O-efficient commercial terrain processing applications by the Danish startup SCALGO.

• [cs.DS]Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes
Aaron Sidford, Mengdi Wang, Xian Wu, Yinyu Ye
http://arxiv.org/abs/1710.09988v1

In this paper we provide faster algorithms for approximately solving discounted Markov Decision Processes in multiple parameter regimes. Given a discounted Markov Decision Process (DMDP) with $|S|$ states, $|A|$ actions, discount factor $\gamma\in(0,1)$, and rewards in the range $[-M, M]$, we show how to compute an $\epsilon$-optimal policy, with probability $1 - \delta$ in time [ \tilde{O} \left( \left(|S|^2 |A| + \frac{|S| |A|}{(1 - \gamma)^3} \right) \log\left( \frac{M}{\epsilon} \right) \log\left( \frac{1}{\delta} \right) \right) ] This contribution reflects the first nearly linear time, nearly linearly convergent algorithm for solving DMDP's for intermediate values of $\gamma$. We also show how to obtain improved sublinear time algorithms and provide an algorithm which computes an $\epsilon$-optimal policy with probability $1 - \delta$ in time [ \tilde{O} \left(\frac{|S| |A| M^2}{(1 - \gamma)^4 \epsilon^2} \log \left(\frac{1}{\delta}\right) \right) ] provided we can sample from the transition function in $O(1)$ time. Interestingly, we obtain our results by a careful modification of approximate value iteration. We show how to combine classic approximate value iteration analysis with new techniques in variance reduction. Our fastest algorithms leverage further insights to ensure that our algorithms make monotonic progress towards the optimal value. This paper is one of few instances in using sampling to obtain a linearly convergent linear programming algorithm and we hope that the analysis may be useful more broadly.

• [cs.HC]Optimal Crowdsourced Classification with a Reject Option in the Presence of Spammers
Qunwei Li, Pramod K. Varshney
http://arxiv.org/abs/1710.09901v1

We explore the design of an effective crowdsourcing system for an $M$-ary classification task. Crowd workers complete simple binary microtasks whose results are aggregated to give the final decision. We consider the scenario where the workers have a reject option so that they are allowed to skip microtasks when they are unable to or choose not to respond to binary microtasks. We present an aggregation approach using a weighted majority voting rule, where each worker's response is assigned an optimized weight to maximize crowd's classification performance.

• [cs.IR]Combining Aspects of Genetic Algorithms with Weighted Recommender Hybridization
Juergen Mueller
http://arxiv.org/abs/1710.10177v1

Recommender systems are established means to inspire users to watch interesting movies, discover baby names, or read books. The recommendation quality further improves by combining the results of multiple recommendation algorithms using hybridization methods. In this paper, we focus on the task of combining unscored recommendations into a single ensemble. Our proposed method is inspired by genetic algorithms. It repeatedly selects items from the recommendations to create a population of items that will be used for the final ensemble. We compare our method with a weighted voting method and test the performance of both in a movie- and name-recommendation scenario. We were able to outperform the weighted method on both datasets by 20.3 % and 31.1 % and decreased the overall execution time by up to 19.9 %. Our results do not only propose a new kind of hybridization method, but introduce the field of recommender hybridization to further work with genetic algorithms.

• [cs.IT]Flexible Multi-Group Single-Carrier Modulation: Optimal Subcarrier Grouping and Rate Maximization
Yifei Yang, Shuowen Zhang, Joni Polili Lie, Rui Zhang
http://arxiv.org/abs/1710.10001v1

Orthogonal frequency division multiplexing (OFDM) and single-carrier frequency domain equalization (SC-FDE) are two commonly adopted modulation schemes for frequency-selective channels. Compared to SC-FDE, OFDM generally achieves higher data rate, but at the cost of higher transmit signal peak-to-average power ratio (PAPR) that leads to lower power amplifier efficiency. This paper proposes a new modulation scheme, called flexible multi-group single-carrier (FMG-SC), which encapsulates both OFDM and SC-FDE as special cases, thus achieving more flexible rate-PAPR trade-offs between them. Specifically, a set of frequency subcarriers are flexibly divided into orthogonal groups based on their channel gains, and SC-FDE is applied over each of the groups to send different data streams in parallel. We aim to maximize the achievable sum-rate of all groups by optimizing the subcarrier-group mapping. We propose two low-complexity subcarrier grouping methods and show via simulation that they perform very close to the optimal grouping by exhaustive search. Simulation results also show the effectiveness of the proposed FMG-SC modulation scheme with optimized subcarrier grouping in improving the rate-PAPR trade-off over conventional OFDM and SC-FDE.

• [cs.IT]Low-Complexity Equalization for Orthogonal Time and Frequency Signaling (OTFS)
Thomas Zemen, Markus Hofer, David Loeschenbrand
http://arxiv.org/abs/1710.09916v1

Recently, a new precoding technique called orthogonal time-frequency signaling (OTFS) has been proposed for time- and frequency-selective communication channels. OTFS precodes a data frame with a complete set of spreading sequences and transmits the results via orthogonal frequency division multiplexing (OFDM). OTFS uses two dimensional (2D) linear spreading sequences in time and frequency which are the basis functions of a symplectic Fourier transform. OTFS allows the utilization of time- and frequency-diversity but requires maximum likelihood decoding to achieve full diversity. In this paper we show performance results of a low-complexity equalizer using soft-symbol feedback for interference cancellation after an initial minimum-mean square error equalization step. Performance results for an implementation in the delay-Doppler domain and in the time-frequency domain are compared. With our equalizer, OTFS achieves a gain of 5dB compared to OFDM for a bit error rate of $10^{-4}$ and a velocity of $200,\text{km/h}$.

• [cs.IT]Near-Optimal Straggler Mitigation for Distributed Gradient Methods
Songze Li, Seyed Mohammadreza Mousavi Kalan, A. Salman Avestimehr, Mahdi Soltanolkotabi
http://arxiv.org/abs/1710.09990v1

Modern learning algorithms use gradient descent updates to train inferential models that best explain data. Scaling these approaches to massive data sizes requires proper distributed gradient descent schemes where distributed worker nodes compute partial gradients based on their partial and local data sets, and send the results to a master node where all the computations are aggregated into a full gradient and the learning model is updated. However, a major performance bottleneck that arises is that some of the worker nodes may run slow. These nodes a.k.a. stragglers can significantly slow down computation as the slowest node may dictate the overall computational time. We propose a distributed computing scheme, called Batched Coupon's Collector (BCC) to alleviate the effect of stragglers in gradient methods. We prove that our BCC scheme is robust to a near optimal number of random stragglers. We also empirically demonstrate that our proposed BCC scheme reduces the run-time by up to 85.4% over Amazon EC2 clusters when compared with other straggler mitigation strategies. We also generalize the proposed BCC scheme to minimize the completion time when implementing gradient descent-based algorithms over heterogeneous worker nodes.

• [cs.IT]Optimizing Caching Policy at Base Stations by Exploiting User Preference and Spatial Locality
Dong Liu, Chenyang Yang
http://arxiv.org/abs/1710.09983v1

Most prior works of proactive caching at wireless edge optimize caching policies under the following assumptions: the preference of each user is identical to content popularity, all users request contents with the same active level and at uniformly-distributed locations. In this paper, we investigate what happens without these assumptions. To this end, we establish a framework to optimize caching policy at base stations exploiting user preference, active level, and spatial locality. We obtain optimal caching policy to minimize the weighted sum of the file download time averaged over all file requests and user locations in the network (reflecting network performance) and the maximal weighted download time averaged over possible file requests and locations of each user (reflecting user fairness). To investigate how user preference similarity and active level skewness affect the optimal caching policy, we then provide a method to synthesize user preference for given content popularity and user active level. The analysis and simulation results show that exploiting user preference can improve both network performance and user fairness remarkably compared with priori works. The gain of exploiting user preference increases with user preference heterogeneity, user spatial locality, and skewness of user active level.

• [cs.IT]Polar Coding for the Cognitive Interference Channel with Confidential Messages
Mengfan Zheng, Wen Chen, Cong Ling
http://arxiv.org/abs/1710.10202v1

In this paper, we propose a low-complexity, secrecy capacity achieving polar coding scheme for the cognitive interference channel with confidential messages (CICC) under the strong secrecy criterion. Existing polar coding schemes for interference channels rely on the use of polar codes for the multiple access channel, the code construction problem of which can be complicated. We show that the whole secrecy capacity region of the CICC can be achieved by simple point-to-point polar codes due to the cognitivity, and our proposed scheme requires the minimum rate of randomness at the encoder.

• [cs.IT]Recovery of Structured Signals with Prior Information via Maximizing Correlation
Xu Zhang, Wei Cui, Yulong Liu
http://arxiv.org/abs/1710.10062v1

This paper considers the problem of recovering a structured signal from a relatively small number of noisy measurements with the aid of a similar signal which is known beforehand. We propose a new approach to integrate prior information into the standard recovery procedure by maximizing the correlation between the prior knowledge and the desired signal. We then establish performance guarantees (in terms of the number of measurements) for the proposed method under sub-Gaussian measurements. Specific structured signals including sparse vectors, block-sparse vectors, and low-rank matrices are also analyzed. Furthermore, we present an interesting geometrical interpretation for the proposed procedure. Our results demonstrate that if prior information is good enough, then the proposed approach can (remarkably) outperform the standard recovery procedure. Simulations are provided to verify our results.

• [cs.IT]Sequential Empirical Coordination Under an Output Entropy Constraint
Ehsan Shafieepoorfard, Maxim Raginsky
http://arxiv.org/abs/1710.10255v1

This paper considers the problem of sequential empirical coordination, where the objective is to achieve a given value of the expected uniform deviation between state-action empirical averages and statistical expectations under a given strategic probability measure, with respect to a given universal Glivenko-Cantelli class of test functions. A communication constraint is imposed on the Shannon entropy of the resulting action sequence. It is shown that the fundamental limit on the output entropy is given by the minimum of the mutual information between the state and the action processes under all strategic measures that have the same marginal state process as the target measure and approximate the target measure to desired accuracy with respect to the underlying Glivenko-Cantelli seminorm. The fundamental limit is shown to be asymptotically achievable by tree-structured codes.

• [cs.IT]Sparse recovery using the preservability of the null space property under random measurements
Pete Casazza, Xuemei Chen, Richard Lynch
http://arxiv.org/abs/1710.09972v1

The field of compressed sensing has become a major tool in high-dimensional analysis, with the realization that vectors can be recovered from relatively very few linear measurements as long as the vectors lie in a low-dimensional structure, typically the vectors that are zero in most coordinates with respect to a basis. However, there are many applications where we instead want to recover vectors that are sparse not with respect to a basis, but rather to a general dictionary. That is, the vector can be written as the linear combination of very few columns of a matrix $\mathbf{D}$, where the columns of $\mathbf{D}$ form a (typically overcomplete) spanning set. In this direction, we show that as an matrix $\mathbf{D}$ stays bounded away from zero in norm on a set $S$ and a provided map ${\boldsymbol \Phi}$ comprised of i.i.d. subgaussian rows has number of measurements at least proportional to the square of $w(\mathbf{D}S)$, the Gaussian width of the related set $\mathbf{D}S$, then with high probability the composition ${\boldsymbol \Phi} \mathbf{D}$ also stays bounded away from zero in norm on $S$ with bound proportional to $w(\mathbf{D}S)$. This result has potential as a powerful tool in dimension reduction analysis. As a specific application, we obtain that the null space property is preserved under such subgaussian maps with high probability. This result is nearly optimal in the sense that we require only a minimal condition on $\mathbf{D}$. Consequently we obtain stable recovery guarantees for dictionary-sparse signals via the $\ell_1$-synthesis method, which is typically challenging, even with random measurements.

• [cs.LG]Generalization Tower Network: A Novel Deep Neural Network Architecture for Multi-Task Learning
Yuhang Song, Main Xu, Songyang Zhang, Liangyu Huo
http://arxiv.org/abs/1710.10036v1

Deep learning (DL) advances state-of-the-art reinforcement learning (RL), by incorporating deep neural networks in learning representations from the input to RL. However, the conventional deep neural network architecture is limited in learning representations for multi-task RL (MT-RL), as multiple tasks can refer to different kinds of representations. In this paper, we thus propose a novel deep neural network architecture, namely generalization tower network (GTN), which can achieve MT-RL within a single learned model. Specifically, the architecture of GTN is composed of both horizontal and vertical streams. In our GTN architecture, horizontal streams are used to learn representation shared in similar tasks. In contrast, the vertical streams are introduced to be more suitable for handling diverse tasks, which encodes hierarchical shared knowledge of these tasks. The effectiveness of the introduced vertical stream is validated by experimental results. Experimental results further verify that our GTN architecture is able to advance the state-of-the-art MT-RL, via being tested on 51 Atari games.

• [cs.LG]Gradient Sparsification for Communication-Efficient Distributed Optimization
Jianqiao Wangni, Jialei Wang, Ji Liu, Tong Zhang
http://arxiv.org/abs/1710.09854v1

Modern large scale machine learning applications require stochastic optimization algorithms to be implemented on distributed computational architectures. A key bottleneck is the communication overhead for exchanging information such as stochastic gradients among different workers. In this paper, to reduce the communication cost we propose a convex optimization formulation to minimize the coding length of stochastic gradients. To solve the optimal sparsification efficiently, several simple and fast algorithms are proposed for approximate solution, with theoretical guaranteed for sparseness. Experiments on $\ell_2$ regularized logistic regression, support vector machines, and convolutional neural networks validate our sparsification approaches.

• [cs.LG]Improving Deep Learning by Inverse Square Root Linear Units (ISRLUs)
Brad Carlile, Guy Delamarter, Paul Kinney, Akiko Marti, Brian Whitney
http://arxiv.org/abs/1710.09967v1

We introduce the "inverse square root linear unit" (ISRLU) to speed up learning in deep neural networks. ISRLU has better performance than ELU but has many of the same benefits. ISRLU and ELU have similar curves and characteristics. Both have negative values, allowing them to push mean unit activation closer to zero, and bring the normal gradient closer to the unit natural gradient, ensuring a noise-robust deactivation state, lessening the over fitting risk. The significant performance advantage of ISRLU on traditional CPUs also carry over to more efficient HW implementations on HW/SW codesign for CNNs/RNNs. In experiments with TensorFlow, ISRLU leads to faster learning and better generalization than ReLU on CNNs. This work also suggests a computationally efficient variant called the "inverse square root unit" (ISRU) which can be used for RNNs. Many RNNs use either long short-term memory (LSTM) and gated recurrent units (GRU) which are implemented with tanh and sigmoid activation functions. ISRU has less com- putational complexity but still has a similar curve to tanh and sigmoid.

• [cs.LG]Not-So-Random Features
Brian Bullins, Cyril Zhang, Yi Zhang
http://arxiv.org/abs/1710.10230v1

We propose a principled method for kernel learning, which relies on a Fourier-analytic characterization of translation-invariant or rotation-invariant kernels. Our method produces a sequence of feature maps, iteratively refining the SVM margin. We provide rigorous guarantees for optimality and generalization, interpreting our algorithm as online equilibrium-finding dynamics in a certain two-player min-max game. Evaluations on synthetic and real-world datasets demonstrate scalability and consistent improvements over related random features-based methods.

• [cs.LG]Online linear optimization with the log-determinant regularizer
Ken-ichiro Moridomi, Kohei Hatano, Eiji Takimoto
http://arxiv.org/abs/1710.10002v1

We consider online linear optimization over symmetric positive semi-definite matrices, which has various applications including the online collaborative filtering. The problem is formulated as a repeated game between the algorithm and the adversary, where in each round t the algorithm and the adversary choose matrices X_t and L_t, respectively, and then the algorithm suffers a loss given by the Frobenius inner product of X_t and L_t. The goal of the algorithm is to minimize the cumulative loss. We can employ a standard framework called Follow the Regularized Leader (FTRL) for designing algorithms, where we need to choose an appropriate regularization function to obtain a good performance guarantee. We show that the log-determinant regularization works better than other popular regularization functions in the case where the loss matrices L_t are all sparse. Using this property, we show that our algorithm achieves an optimal performance guarantee for the online collaborative filtering. The technical contribution of the paper is to develop a new technique of deriving performance bounds by exploiting the property of strong convexity of the log-determinant with respect to the loss matrices, while in the previous analysis the strong convexity is defined with respect to a norm. Intuitively, skipping the norm analysis results in the improved bound. Moreover, we apply our method to online linear optimization over vectors and show that the FTRL with the Burg entropy regularizer, which is the analogue of the log-determinant regularizer in the vector case, works well.

• [cs.LG]SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data
Alon Brutzkus, Amir Globerson, Eran Malach, Shai Shalev-Shwartz
http://arxiv.org/abs/1710.10174v1

Neural networks exhibit good generalization behavior in the over-parameterized regime, where the number of network parameters exceeds the number of observations. Nonetheless, current generalization bounds for neural networks fail to explain this phenomenon. In an attempt to bridge this gap, we study the problem of learning a two-layer over-parameterized neural network, when the data is generated by a linearly separable function. In the case where the network has Leaky ReLU activations, we provide both optimization and generalization guarantees for over-parameterized networks. Specifically, we prove convergence rates of SGD to a global minimum and provide generalization guarantees for this global minimum that are independent of the network size. Therefore, our result clearly shows that the use of SGD for optimization both finds a global minimum, and avoids overfitting despite the high capacity of the model. This is the first theoretical demonstration that SGD can avoid overfitting, when learning over-specified neural network classifiers.

• [cs.LG]Stochastic Conjugate Gradient Algorithm with Variance Reduction
Xiao-Bo Jin, Xu-Yao Zhang, Kaizhu Huang, Guang-Gang Geng
http://arxiv.org/abs/1710.09979v1

Conjugate gradient methods are a class of important methods for solving linear equations and nonlinear optimization. In our work, we propose a new stochastic conjugate gradient algorithm with variance reduction (CGVR) and prove its linear convergence with the Fletcher and Revves method for strongly convex and smooth functions. We experimentally demonstrate that the CGVR algorithm converges faster than its counterparts for six large-scale optimization problems that may be convex, non-convex or non-smooth, and its AUC (Area Under Curve) performance with $L2$-regularized $L2$-loss is comparable to that of LIBLINEAR but with significant improvement in computational efficiency.

• [cs.LG]The Error Probability of Random Fourier Features is Dimensionality Independent
Jean Honorio, Yu-Jun Li
http://arxiv.org/abs/1710.09953v1

We show that the error probability of reconstructing kernel matrices from Random Fourier Features for any shift-invariant kernel function is at most $\mathcal{O}(\exp(-D))$, where $D$ is the number of random features. We also provide a matching information-theoretic method-independent lower bound of $\Omega(\exp(-D))$ for standard Gaussian distributions. Compared to prior work, we are the first to show that the error probability for random Fourier features is independent of the dimensionality of data points as well as the size of their domain. As applications of our theory, we obtain dimension-independent bounds for kernel ridge regression and support vector machines.

• [cs.LG]Transform-Invariant Non-Parametric Clustering of Covariance Matrices and its Application to Unsupervised Joint Segmentation and Action Discovery
Nadia Figueroa, Aude Billard
http://arxiv.org/abs/1710.10060v1

In this work, we tackle the problem of transform-invariant unsupervised learning in the space of Covariance matrices and applications thereof. We begin by introducing the Spectral Polytope Covariance Matrix (SPCM) Similarity function; a similarity function for Covariance matrices, invariant to any type of transformation. We then derive the SPCM-CRP mixture model, a transform-invariant non-parametric clustering approach for Covariance matrices that leverages the proposed similarity function, spectral embedding and the distance-dependent Chinese Restaurant Process (dd-CRP) (Blei and Frazier, 2011). The scalability and applicability of these two contributions is extensively validated on real-world Covariance matrix datasets from diverse research fields. Finally, we couple the SPCM-CRP mixture model with the Bayesian non-parametric Indian Buffet Process (IBP) - Hidden Markov Model (HMM) (Fox et al., 2009), to jointly segment and discover transform-invariant action primitives from complex sequential data. Resulting in a topic-modeling inspired hierarchical model for unsupervised time-series data analysis which we call ICSC-HMM (IBP Coupled SPCM-CRP Hidden Markov Model). The ICSC-HMM is validated on kinesthetic demonstrations of uni-manual and bi-manual cooking tasks; achieving unsupervised human-level decomposition of complex sequential tasks.

• [cs.NE]Data-driven Feature Sampling for Deep Hyperspectral Classification and Segmentation
William M. Severa, Jerilyn A. Timlin, Suraj Kholwadwala, Conrad D. James, James B. Aimone
http://arxiv.org/abs/1710.09934v1

The high dimensionality of hyperspectral imaging forces unique challenges in scope, size and processing requirements. Motivated by the potential for an in-the-field cell sorting detector, we examine a $\textit{Synechocystis sp.}$ PCC 6803 dataset wherein cells are grown alternatively in nitrogen rich or deplete cultures. We use deep learning techniques to both successfully classify cells and generate a mask segmenting the cells/condition from the background. Further, we use the classification accuracy to guide a data-driven, iterative feature selection method, allowing the design neural networks requiring 90% fewer input features with little accuracy degradation.

• [cs.NE]Phase Transitions in Image Denoising via Sparsely Coding Convolutional Neural Networks
Jacob Carroll, Nils Carlson, Garrett T. Kenyon
http://arxiv.org/abs/1710.09875v1

Neural networks are analogous in many ways to spin glasses, systems which are known for their rich set of dynamics and equally complex phase diagrams. We apply well-known techniques in the study of spin glasses to a convolutional sparsely encoding neural network and observe power law finite-size scaling behavior in the sparsity and reconstruction error as the network denoises 32$\times$32 RGB CIFAR-10 images. This finite-size scaling indicates the presence of a continuous phase transition at a critical value of this sparsity. By using the power law scaling relations inherent to finite-size scaling, we can determine the optimal value of sparsity for any network size by tuning the system to the critical point and operate the system at the minimum denoising error.

• [cs.NE]Progressive Growing of GANs for Improved Quality, Stability, and Variation
Tero Karras, Timo Aila, Samuli Laine, Jaakko Lehtinen
http://arxiv.org/abs/1710.10196v1

We describe a new training methodology for generative adversarial networks. The key idea is to grow both the generator and discriminator progressively: starting from a low resolution, we add new layers that model increasingly fine details as training progresses. This both speeds the training up and greatly stabilizes it, allowing us to produce images of unprecedented quality, e.g., CelebA images at 1024^2. We also propose a simple way to increase the variation in generated images, and achieve a record inception score of 8.80 in unsupervised CIFAR10. Additionally, we describe several implementation details that are important for discouraging unhealthy competition between the generator and discriminator. Finally, we suggest a new metric for evaluating GAN results, both in terms of image quality and variation. As an additional contribution, we construct a higher-quality version of the CelebA dataset.

• [cs.RO]A Decomposition-Based Approach to Reasoning about Free Space Path-Connectivity for Rigid Objects in 2D
Anastasiia Varava, J. Frederico Carvalho, Danica Kragic, Florian T. Pokorny
http://arxiv.org/abs/1710.10089v1

In this paper, we compute a conservative approximation of the path-connected components of the free space of a rigid object in a 2D workspace in order to solve two closely related problems: to determine whether there exists a collision-free path between two given configurations, and to verify whether an object can escape arbitrarily far from its initial configuration -- i.e., whether the object is caged. Furthermore, we consider two quantitative characteristics of the free space: the volume of path-connected components and the width of narrow passages. To address these problems, we decompose the configuration space into a set of two-dimensional slices, approximate them as two-dimensional alpha-complexes, and then study the relations between them. This significantly reduces the computational complexity compared to a direct approximation of the free space. We implement our algorithm and run experiments in a three-dimensional configuration space of a simple object showing runtime of less than 2 seconds.

• [cs.RO]DoShiCo: a Domain Shift Challenge for Control
Klaas Kelchtermans, Tinne Tuytelaars
http://arxiv.org/abs/1710.09860v1

Training deep neural control networks end-to-end for real-world applications typically requires big demonstration datasets in the real world or big sets consisting of a large variety of realistic and closely related 3D CAD models. These real or virtual data should, moreover, have very similar characteristics to the conditions expected at test time. These stringent requirements and the time consuming data collection processes that they entail, are probably the most important impediment that keeps deep neural policies from being deployed in real-world applications. Therefore, in this work we advocate an alternative approach, where instead of avoiding any domain shift by carefully selecting the training data, the goal is to learn a policy that can cope with it. To this end, we propose a new challenge: to train a model in very basic synthetic environments, far from realistic, in a way that it can fly in more realistic environments as well as take the control decisions on real-world data. We collected a benchmark dataset and implemented a baseline method, exploiting depth prediction as an auxiliary task to help overcome the domain shift. Even though the policy is trained in very basic environments, it can learn to fly in a very different realistic simulated environment. It is even capable to compete and in some cases outperform a policy trained in the more realistic environment when testing on real-world data.

• [cs.RO]Inverse Reinforcement Learning Under Noisy Observations
Shervin Shahryari, Prashant Doshi
http://arxiv.org/abs/1710.10116v1

We consider the problem of performing inverse reinforcement learning when the trajectory of the expert is not perfectly observed by the learner. Instead, a noisy continuous-time observation of the trajectory is provided to the learner. This problem exhibits wide-ranging applications and the specific application we consider here is the scenario in which the learner seeks to penetrate a perimeter patrolled by a robot. The learner's field of view is limited due to which it cannot observe the patroller's complete trajectory. Instead, we allow the learner to listen to the expert's movement sound, which it can also use to estimate the expert's state and action using an observation model. We treat the expert's state and action as hidden data and present an algorithm based on expectation maximization and maximum entropy principle to solve the non-linear, non-convex problem. Related work considers discrete-time observations and an observation model that does not include actions. In contrast, our technique takes expectations over both state and action of the expert, enabling learning even in the presence of extreme noise and broader applications.

• [cs.RO]RRT-CoLearn: towards kinodynamic planning without numerical trajectory optimization
Wouter Wolfslag, Mukunda Bharatheesha, Thomas Moerland, Martijn Wisse
http://arxiv.org/abs/1710.10122v1

Sampling-based kinodynamic planners, such as Rapidly-exploring Random Trees (RRTs), pose two fundamental challenges: computing a reliable (pseudo-)metric for the distance between two randomly sampled nodes, and computing a steering input to connect the nodes. The core of these challenges is a Two Point Boundary Value Problem, which is known to be NP-hard. Recently, the distance metric has been approximated using supervised learning, reducing computation time drastically. The previous work on such learning RRTs use direct optimal control to generate the data for supervised learning. This paper proposes to use indirect optimal control instead, because it provides two benefits: it reduces the computational effort to generate the data, and it provides a low dimensional parametrization of the action space. The latter allows us to learn both the distance metric and the steering input to connect two nodes. This eliminates the need for a local planner in learning RRTs. Experimental results on a pendulum swing up show 10-fold speed-up in both the offline data generation and the online planning time, leading to at least a 10-fold speed-up in the overall planning time.

• [cs.RO]Trajectory Deformations from Physical Human-Robot Interaction
Dylan P. Losey, Marcia K. O'Malley
http://arxiv.org/abs/1710.09871v1

Robots are finding new applications where physical interaction with a human is necessary: manufacturing, healthcare, and social tasks. Accordingly, the field of physical human-robot interaction (pHRI) has leveraged impedance control approaches, which support compliant interactions between human and robot. However, a limitation of traditional impedance control is that---despite provisions for the human to modify the robot's current trajectory---the human cannot affect the robot's future desired trajectory through pHRI. In this paper, we present an algorithm for physically interactive trajectory deformations which, when combined with impedance control, allows the human to modulate both the actual and desired trajectories of the robot. Unlike related works, our method explicitly deforms the future desired trajectory based on forces applied during pHRI, but does not require constant human guidance. We present our approach and verify that this method is compatible with traditional impedance control. Next, we use constrained optimization to derive the deformation shape. Finally, we describe an algorithm for real time implementation, and perform simulations to test the arbitration parameters. Experimental results demonstrate reduction in the human's effort and improvement in the movement quality when compared to pHRI with impedance control alone.

• [cs.SD]Direction of arrival estimation for multiple sound sources using convolutional recurrent neural network
Sharath Adavanne, Archontis Politis, Tuomas Virtanen
http://arxiv.org/abs/1710.10059v1

This paper proposes a deep neural network for estimating the directions of arrival (DOA) of multiple sound sources. The proposed stacked convolutional and recurrent neural network (DOAnet) generates a spatial pseudo-spectrum along with the DOA estimates in both azimuth and elevation. We avoid any explicit feature extraction step by using the magnitude and phase of the spectrogram as input to the network. The proposed DOAnet is evaluated by estimating the DOAs of multiple concurrently present sources in anechoic, matched and unmatched reverberant conditions. The results show that the proposed DOAnet is capable of estimating the number of sources and their respective DOAs with good precision and generate SPS with high signal-to-noise ratio.

• [cs.SI]Computing the Line Index of Balance Using Integer Programming Optimisation
Samin Aref, Andrew J. Mason, Mark C. Wilson
http://arxiv.org/abs/1710.09876v1

An important measure of a signed graph is the line index of balance which has several applications in many fields. However, this graph-theoretic measure was underused for decades because of the inherent complexity in its computation which is closely related to solving NP-hard graph optimisation problems like MAXCUT. We develop new quadratic and linear programming models to compute the line index of balance exactly. Using the Gurobi integer programming optimisation solver, we evaluate the line index of balance on real-world and synthetic datasets. The synthetic data involves Erd\H{o}s-R'enyi graphs, Barab'asi-Albert graphs, and specially structured random graphs. We also use well known datasets from the sociology literature, such as signed graphs inferred from students' choice and rejection as well as datasets from the biology literature including gene regulatory networks. The results show that exact values of the line index of balance in relatively large signed graphs can be efficiently computed using our suggested optimisation models. We find that most real-world social networks and some biological networks have small line index of balance which indicates that they are close to balanced.

• [cs.SY]Online Learning of Power Transmission Dynamics
Andrey Y. Lokhov, Marc Vuffray, Dmitry Shemetov, Deepjyoti Deka, Michael Chertkov
http://arxiv.org/abs/1710.10021v1

We consider the problem of reconstructing the dynamic state matrix of transmission power grids from time-stamped PMU measurements in the regime of ambient fluctuations. Using a maximum likelihood based approach, we construct a family of convex estimators that adapt to the structure of the problem depending on the available prior information. The proposed method is fully data-driven and does not assume any knowledge of system parameters. It can be implemented in near real-time and requires a small amount of data. Our learning algorithms can be used for model validation and calibration, and can also be applied to related problems of system stability, detection of forced oscillations, generation re-dispatch, as well as to the estimation of the system state.

• [eess.SP]Unified Functorial Signal Representation III: Foundations, Redundancy, $L^0$ and $L^2$ functors
Salil Samant, Shiv Dutt Joshi
http://arxiv.org/abs/1710.10227v1

In this paper we propose and lay the foundations of a functorial framework for representing signals. By incorporating additional category-theoretic relative and generative perspective alongside the classic set-theoretic measure theory the fundamental concepts of redundancy, compression are formulated in a novel authentic arrow-theoretic way. The existing classic framework representing a signal as a vector of appropriate linear space is shown as a special case of the proposed framework. Next in the context of signal-spaces as a categories we study the various covariant and contravariant forms of $L^0$ and $L^2$ functors using categories of measurable or measure spaces and their opposites involving Boolean and measure algebras along with partial extension. Finally we contribute a novel definition of intra-signal redundancy using general concept of isomorphism arrow in a category covering the translation case and others as special cases. Through category-theory we provide a simple yet precise explanation for the well-known heuristic of lossless differential encoding standards yielding better compressions in image types such as line drawings, iconic image, text etc; as compared to classic representation techniques such as JPEG which choose bases or frames in a global Hilbert space.

• [math.OC]Regularization via Mass Transportation
Soroosh Shafieezadeh-Abadeh, Daniel Kuhn, Peyman Mohajerin Esfahani
http://arxiv.org/abs/1710.10016v1

The goal of regression and classification methods in supervised learning is to minimize the empirical risk, that is, the expectation of some loss function quantifying the prediction error under the empirical distribution. When facing scarce training data, overfitting is typically mitigated by adding regularization terms to the objective that penalize hypothesis complexity. In this paper we introduce new regularization techniques using ideas from distributionally robust optimization, and we give new probabilistic interpretations to existing techniques. Specifically, we propose to minimize the worst-case expected loss, where the worst case is taken over the ball of all (continuous or discrete) distributions that have a bounded transportation distance from the (discrete) empirical distribution. By choosing the radius of this ball judiciously, we can guarantee that the worst-case expected loss provides an upper confidence bound on the loss on test data, thus offering new generalization bounds. We prove that the resulting regularized learning problems are tractable and can be tractably kernelized for many popular loss functions. We validate our theoretical out-of-sample guarantees through simulated and empirical experiments.

• [math.OC]Zeroth Order Nonconvex Multi-Agent Optimization over Networks
Davood Hajinezhad, Mingyi Hong, Alfredo Garcia
http://arxiv.org/abs/1710.09997v1

In this paper we consider distributed optimization problems over a multi-agent network, where each agent can only partially evaluate the objective function, and it is allowed to exchange messages with its immediate neighbors. Differently from all existing works on distributed optimization, our focus is given to optimizing a class of difficult non-convex problems, and under the challenging setting where each agent can only access the zeroth-order information (i.e., the functional values) of its local functions. For different types of network topologies such as undirected connected networks or star networks, we develop efficient distributed algorithms and rigorously analyze their convergence and rate of convergence (to the set of stationary solutions). Numerical results are provided to demonstrate the efficiency of the proposed algorithms.

• [math.ST]Generating global network structures by triad types
Marjan Cugmas, Anuška Ferligoj, Aleš Žiberna
http://arxiv.org/abs/1710.10042v1

This paper addresses the question of whether it is possible to generate networks with a given global structure (defined by selected blockmodels, i.e., cohesive, core-periphery, hierarchical and transitivity), considering only different types of triads. Two methods are used to generate networks: (i) the method of relocating links; and (ii) the Monte Carlo Multi Chain algorithm implemented in the "ergm" package implemented in R. Although all types of triads can generate networks with the selected blockmodel types, the selection of only a subset of triads improves the generated networks' blockmodel structure. However, in the case of a hierarchical blockmodel without complete blocks on the diagonal, additional local structures are needed to achieve the desired global structure of generated networks. This shows that blockmodels can emerge based on only local processes that do not take attributes into account.

• [math.ST]Matrix Completion Methods for Causal Panel Data Models
Susan Athey, Mohsen Bayati, Nikolay Doudchenko, Guido Imbens, Khashayar Khosravi
http://arxiv.org/abs/1710.10251v1

In this paper we develop new methods for estimating causal effects in settings with panel data, where a subset of units are exposed to a treatment during a subset of periods, and the goal is estimating counterfactual (untreated) outcomes for the treated unit/period combinations. We develop a class of estimators that uses the observed elements of the matrix of control outcomes corresponding to untreated unit/periods to predict the "missing" elements of the matrix, corresponding to treated units/periods. The approach estimates a matrix that well-approximates the original (incomplete) matrix, but has lower complexity according to a matrix norm, where we consider the family of Schatten norms based on the singular values of the matrix. The proposed methods have attractive computational properties. From a technical perspective, we generalize results from the matrix completion literature by allowing the patterns of missing data to have a time series dependency structure. We also present new insights concerning the connections between the interactive fixed effects models and the literatures on program evaluation under unconfoundedness as well as on synthetic control methods. If there are few time periods and many units, our method approximates a regression approach where counterfactual outcomes are estimated through a regression of current outcomes on lagged outcomes for the same unit. In contrast, if there are few units and many periods, our proposed method approximates a synthetic control estimator where counterfactual outcomes are estimated through a regression of the lagged outcomes for the treated unit on lagged outcomes for the control units. The advantage of our proposed method is that it moves seamlessly between these two different approaches, utilizing both cross-sectional and within-unit patterns in the data.

• [math.ST]On the Optimal Reconstruction of Partially Observed Functional Data
Alois Kneip, Dominik Liebl
http://arxiv.org/abs/1710.10099v1

We propose a new reconstruction operator that aims to recover the missing parts of a function given the observed parts. This new operator belongs to a new, very large class of functional operators which includes the classical regression operators as a special case. We show the optimality of our reconstruction operator and demonstrate that the usually considered regression operators generally cannot be optimal reconstruction operators. Our estimation theory allows for autocorrelated functional data and considers the practically relevant situation in which each of the $n$ functions is observed at $m$ discretization points. We derive rates of consistency for our nonparametric estimation procedures using a double asymptotic ($n\to\infty, m\to\infty$). For data situations, as in our real data application where $m$ is considerably smaller than $n$, we show that our functional principal components based estimator can provide better rates of convergence than any conventional nonparametric smoothing method.

• [math.ST]Quantifying the Estimation Error of Principal Components
Raphael Hauser, Raul Kangro, Jüri Lember, Heinrich Matzinger
http://arxiv.org/abs/1710.10124v1

Principal component analysis is an important pattern recognition and dimensionality reduction tool in many applications. Principal components are computed as eigenvectors of a maximum likelihood covariance $\widehat{\Sigma}$ that approximates a population covariance $\Sigma$, and these eigenvectors are often used to extract structural information about the variables (or attributes) of the studied population. Since PCA is based on the eigendecomposition of the proxy covariance $\widehat{\Sigma}$ rather than the ground-truth $\Sigma$, it is important to understand the approximation error in each individual eigenvector as a function of the number of available samples. The recent results of Kolchinskii and Lounici yield such bounds. In the present paper we sharpen these bounds and show that eigenvectors can often be reconstructed to a required accuracy from a sample of strictly smaller size order.

• [quant-ph]Optimized quantum f-divergences and data processing
Mark M. Wilde
http://arxiv.org/abs/1710.10252v1

The quantum relative entropy is a measure of the distinguishability of two quantum states, and it is a unifying concept in quantum information theory: many information measures such as entropy, conditional entropy, mutual information, and entanglement measures can be realized from it. As such, there has been broad interest in generalizing the notion to further understand its most basic properties, one of which is the data processing inequality. The quantum f-divergence of Petz is one generalization of the quantum relative entropy, and it also leads to other relative entropies, such as the Petz-Renyi relative entropies. In this paper, I introduce the optimized quantum f-divergence as a related generalization of quantum relative entropy. I prove that it satisfies the data processing inequality, and the method of proof relies upon the operator Jensen inequality, similar to Petz's original approach. Interestingly, the sandwiched Renyi relative entropies are particular examples of the optimized f-divergence. Thus, one benefit of this paper is that there is now a single, unified approach for establishing the data processing inequality for both the Petz-Renyi and sandwiched Renyi relative entropies, for the full range of parameters for which it is known to hold. This paper discusses other aspects of the optimized f-divergence, such as the classical case, the classical-quantum case, and how to construct optimized f-information measures.

• [stat.AP]Bayesian Nonparametric Models for Biomedical Data Analysis
Tianjian Zhou
http://arxiv.org/abs/1710.09890v1

In this dissertation, we develop nonparametric Bayesian models for biomedical data analysis. In particular, we focus on inference for tumor heterogeneity and inference for missing data. First, we present a Bayesian feature allocation model for tumor subclone reconstruction using mutation pairs. The key innovation lies in the use of short reads mapped to pairs of proximal single nucleotide variants (SNVs). In contrast, most existing methods use only marginal reads for unpaired SNVs. In the same context of using mutation pairs, in order to recover the phylogenetic relationship of subclones, we then develop a Bayesian treed feature allocation model. In contrast to commonly used feature allocation models, we allow the latent features to be dependent, using a tree structure to introduce dependence. Finally, we propose a nonparametric Bayesian approach to monotone missing data in longitudinal studies with non-ignorable missingness. In contrast to most existing methods, our method allows for incorporating information from auxiliary covariates and is able to capture complex structures among the response, missingness and auxiliary covariates. Our models are validated through simulation studies and are applied to real-world biomedical datasets.

• [stat.AP]Estimating the coefficients of variation of Freundlich parameters with weighted least squares analysis
Jos J. T. I. Boesten
http://arxiv.org/abs/1710.10023v1

The Freundlich isotherm has been used widely to describe sorption of solutes to soils for many decades. The Freundlich parameters are often estimated using unweighted least squares (ULS) analysis after log-log transformation. Estimating the accuracy of these parameters (characterized by their coefficient of variation, CV) is an essential element of the use of these parameters. Accurate CVs can be derived with weighted least squares (WLS), but only if proper weights are assigned to the residuals in the fitting procedure. This work presents the derivation of an analytical approximation of these weights which were found to decrease with increasing concentration, increasing Freundlich exponent, and increasing CVs of the initial and equilibrium concentrations. Monte-Carlo simulations for a wide range of Freundlich systems based on known values of the CVs of the initial and equilibrium concentrations confirmed the accuracy of this analytical approximation. Unfortunately, in practice, the CVs of the initial and equilibrium concentrations are unknown a priori. Simulations showed that the accuracy of the estimated CVs of the Freundlich parameters was distinctly lower if the CVs of the initial and equilibrium concentrations were estimated from the isotherm data. However, this accuracy was still considerably better than when using ULS. It is recommended to use this analytical approximation whenever these CVs are relevant for the further use and interpretation of the estimated Freundlich parameters.

• [stat.AP]Single Iteration Conditional Based DSE Considering Spatial and Temporal Correlation
Mehdi Shafiei, Ghavameddin Nourbakhsh, Ali Arefi, Gerard Ledwich, Houman Pezeshki
http://arxiv.org/abs/1710.10024v1

Active players are introducing significant challenges in electric distribution systems management. One of the key components of the distribution system management is state estimator. This paper proposes an efficient and accurate single iteration distribution system state estimation technique only requiring a limited number of real measurement units. A method based on conditional multivariate complex Gaussian distribution (CMCGD) is proposed to include spatial and temporal correlation into estimator and to improve the accuracy of pseudo measurements for unmeasured buses. The quality, accuracy, standard deviation and computational time are improved due to combined spatial and temporal correlation and using an efficient direct solution that only has a single iteration for the solution. Three case studies are used in this paper to examine and demonstrate the effectiveness of the proposed technique.

• [stat.ME]Bayesian Pairwise Estimation Under Dependent Informative Sampling
Matthew R. Williams, Terrance D. Savitsky
http://arxiv.org/abs/1710.10102v1

An informative sampling design leads to the selection of units whose inclusion probabilities are correlated with the response variable of interest. Model inference performed on the resulting observed sample will be biased for the population generative model. One approach that produces asymptotically unbiased inference employs marginal inclusion probabilities to form sampling weights used to exponentiate each likelihood contribution of a pseudo likelihood used to form a pseudo posterior distribution. Conditions for posterior consistency restrict applicable sampling designs to those under which pairwise inclusion dependencies asymptotically limit to 0. There are many sampling designs excluded by this restriction; for example, a multi-stage design that samples individuals within households. Viewing each household as a population, the dependence among individuals does not attenuate. We propose a more targeted approach in this paper for inference focused on pairs of individuals or sampled units; for example, the substance use of one spouse in a shared household, conditioned on the substance use of the other spouse. We formulate the pseudo likelihood with weights based on pairwise or second order probabilities and demonstrate consistency, removing the requirement for asymptotic independence and replacing it with restrictions on higher order selection probabilities. Our approach provides a nearly automated estimation procedure applicable to any model specified by the data analyst. We demonstrate our method on the National Survey on Drug Use and Health.

• [stat.ME]Diagonal Likelihood Ratio Test for Equality of Mean Vectors in High-Dimensional Data
Zongliang Hu, Tiejun Tong, Marc G. Genton
http://arxiv.org/abs/1710.09982v1

We propose a likelihood ratio test framework for testing normal mean vectors in high-dimensional data under two common scenarios: the one-sample test and the two-sample test with equal covariance matrices. We derive the test statistics under the assumption that the covariance matrices follow a diagonal matrix structure. In comparison with the diagonal Hotelling's tests, our proposed test statistics display some interesting characteristics. In particular, they are a summation of the log-transformed squared t-statistics rather than a direct summation of those components. More importantly, to derive the asymptotic normality of our test statistics under the null and local alternative hypotheses, we do not require the assumption that the covariance matrix follows a diagonal matrix structure. As a consequence, our proposed test methods are very flexible and can be widely applied in practice. Finally, simulation studies and a real data analysis are also conducted to demonstrate the advantages of our likelihood ratio test method.

• [stat.ME]Evaluation of Treatment Effect Modification by Biomarkers Measured Pre- and Post-randomization in the Presence of Non-monotone Missingness
Yingying Zhuang, Ying Huang, Peter B. Gilbert
http://arxiv.org/abs/1710.09923v1

In vaccine studies, investigators are often interested in studying effect modifiers of clinical treatment efficacy by biomarker-based principal strata, which is useful for selecting biomarker study endpoints for evaluating treatments in new trials, exploring biological mechanisms of clinical treatment efficacy, and studying mediators of clinical treatment efficacy. However, in trials where participants may enter the study with prior exposure therefore with variable baseline biomarker values, clinical treatment efficacy may depend jointly on a biomarker measured at baseline and measured at a fixed time after vaccination. Therefore, it is of interest to conduct a bivariate effect modification analysis by biomarker-based principal strata and baseline biomarker values. Previous methods allow this assessment if participants who have the biomarker measured at the the fixed time point post randomization would also have the biomarker measured at baseline. However, additional complications in study design could happen in practice. For example, in the Dengue correlates study, baseline biomarker values were only available from a fraction of participants who have biomarkers measured post-randomization. How to conduct the bivariate effect modification analysis in these studies remains an open research question. In this article, we propose an estimated likelihood method to utilize the sub-sampled baseline biomarker in the effect modification analysis and illustrate our method with datasets from two dengue phase 3 vaccine efficacy trials.

• [stat.ME]New asymptotic properties for $M$-estimators
Gordana Draskovic, Frederic Pascal
http://arxiv.org/abs/1710.09945v1

In the context of robust covariance matrix estimation, this paper proposes a new approach to understanding the behavior of scatter matrix M-estimators introduced during the 70's in the statistics community. During the last decade, a renewed interest for robust estimators appeared in the signal processing community, mainly due to their flexibility to the statistical model and their robustness to outliers and/or missing data. However, the behavior of these estimators still remains unclear and not understood well enough. A major disadvantage is that they are described by fixed-point equations that make their statistical analysis very difficult. To fill this gap, the main contribution of this work is to compare these estimators to the well-known sample covariance matrix (SCM) in order to infer more accurately their statistical behaviors. Indeed, under the Gaussian assumption, the SCM follows a Wishart distribution. However, when observations turn to be non-Gaussian, the SCM performance can be seriously degraded. In this article, we propose to use robust estimators, more adapted to the case of non-Gaussian models and presence of outliers, and to rely on the SCM properties in a Gaussian framework for establishing their theoretical analysis. To confirm our claims we also present results for a widely used function of $M$-estimators, the Mahalanobis distance. Finally, Monte Carlo simulations for various robust scatter matrix estimators are presented to validate theoretical results.

• [stat.ML]Energy Clustering
Guilherme França, Joshua T. Vogelstein
http://arxiv.org/abs/1710.09859v1

Energy statistics was proposed by Sz'{e}kely in the 80's inspired by the Newtonian gravitational potential from classical mechanics, and it provides a hypothesis test for equality of distributions. It was further generalized from Euclidean spaces to metric spaces of strong negative type, and more recently, a connection with reproducing kernel Hilbert spaces (RKHS) was established. Here we consider the clustering problem from an energy statistics theory perspective, providing a precise mathematical formulation yielding a quadratically constrained quadratic program (QCQP) in the associated RKHS, thus establishing the connection with kernel methods. We show that this QCQP is equivalent to kernel $k$-means optimization problem once the kernel is fixed. These results imply a first principles derivation of kernel $k$-means from energy statistics. However, energy statistics fixes a family of standard kernels. Furthermore, we also consider a weighted version of energy statistics, making connection to graph partitioning problems. To find local optimizers of such QCQP we propose an iterative algorithm based on Hartigan's method, which in this case has the same computational cost as kernel $k$-means algorithm, based on Lloyd's heuristic, but usually with better clustering quality. We provide carefully designed numerical experiments showing the superiority of the proposed method compared to kernel $k$-means, spectral clustering, standard $k$-means, and Gaussian mixture models in a variety of settings.

• [stat.ML]On denoising modulo 1 samples of a function
Mihai Cucuringu, Hemant Tyagi
http://arxiv.org/abs/1710.10210v1

Consider an unknown smooth function $f: [0,1] \rightarrow \mathbb{R}$, and say we are given $n$ noisy mod 1 samples of $f$, i.e., $y_i = (f(x_i) + \eta_i)\mod 1$ for $x_i \in [0,1]$, where $\eta_i$ denotes noise. Given the samples $(x_i,y_i)_{i=1}^{n}$, our goal is to recover smooth, robust estimates of the clean samples $f(x_i) \bmod 1$. We formulate a natural approach for solving this problem which works with angular embeddings of the noisy mod 1 samples over the unit complex circle, inspired by the angular synchronization framework. Our approach amounts to solving a quadratically constrained quadratic program (QCQP) which is NP-hard in its basic form, and therefore we consider its relaxation which is a trust region sub-problem and hence solvable efficiently. We demonstrate its robustness to noise via extensive numerical simulations on several synthetic examples, along with a detailed theoretical analysis. To the best of our knowledge, we provide the first algorithm for denoising mod 1 samples of a smooth function, which comes with robustness guarantees.