January 27, 2020

3438 words 17 mins read

Paper Group ANR 1209

Optimal PAC-Bayesian Posteriors for Stochastic Classifiers and their use for Choice of SVM Regularization Parameter. Trans-Sense: Real Time Transportation Schedule Estimation Using Smart Phones. Complexity of Stochastic Dual Dynamic Programming. Reduced network extremal ensemble learning (RenEEL) scheme for community detection in complex networks. …

Optimal PAC-Bayesian Posteriors for Stochastic Classifiers and their use for Choice of SVM Regularization Parameter


Title	Optimal PAC-Bayesian Posteriors for Stochastic Classifiers and their use for Choice of SVM Regularization Parameter
Authors	Puja Sahu, Nandyala Hemachandra
Abstract	PAC-Bayesian set up involves a stochastic classifier characterized by a posterior distribution on a classifier set, offers a high probability bound on its averaged true risk and is robust to the training sample used. For a given posterior, this bound captures the trade off between averaged empirical risk and KL-divergence based model complexity term. Our goal is to identify an optimal posterior with the least PAC-Bayesian bound. We consider a finite classifier set and 5 distance functions: KL-divergence, its Pinsker’s and a sixth degree polynomial approximations; linear and squared distances. Linear distance based model results in a convex optimization problem. We obtain closed form expression for its optimal posterior. For uniform prior, this posterior has full support with weights negative-exponentially proportional to number of misclassifications. Squared distance and Pinsker’s approximation bounds are possibly quasi-convex and are observed to have single local minimum. We derive fixed point equations (FPEs) using partial KKT system with strict positivity constraints. This obviates the combinatorial search for subset support of the optimal posterior. For uniform prior, exponential search on a full-dimensional simplex can be limited to an ordered subset of classifiers with increasing empirical risk values. These FPEs converge rapidly to a stationary point, even for a large classifier set when a solver fails. We apply these approaches to SVMs generated using a finite set of SVM regularization parameter values on 9 UCI datasets. These posteriors yield stochastic SVM classifiers with tight bounds. KL-divergence based bound is the tightest, but is computationally expensive due to non-convexity and multiple calls to a root finding algorithm. Optimal posteriors for all 5 distance functions have lowest 10% test error values on most datasets, with linear distance being the easiest to obtain.
Tasks
Published	2019-12-14
URL	https://arxiv.org/abs/1912.06803v1
PDF	https://arxiv.org/pdf/1912.06803v1.pdf
PWC	https://paperswithcode.com/paper/optimal-pac-bayesian-posteriors-for
Repo
Framework

Trans-Sense: Real Time Transportation Schedule Estimation Using Smart Phones


Title	Trans-Sense: Real Time Transportation Schedule Estimation Using Smart Phones
Authors	Ali AbdelAziz, Amin Shoukry, Walid Gomaa, Moustafa Youssef
Abstract	Developing countries suffer from traffic congestion, poorly planned road/rail networks, and lack of access to public transportation facilities. This context results in an increase in fuel consumption, pollution level, monetary losses, massive delays, and less productivity. On the other hand, it has a negative impact on the commuters feelings and moods. Availability of real-time transit information - by providing public transportation vehicles locations using GPS devices - helps in estimating a passenger’s waiting time and addressing the above issues. However, such solution is expensive for developing countries. This paper aims at designing and implementing a crowd-sourced mobile phones-based solution to estimate the expected waiting time of a passenger in public transit systems, the prediction of the remaining time to get on/off a vehicle, and to construct a real time public transit schedule. Trans-Sense has been evaluated using real data collected for over 800 hours, on a daily basis, by different Android phones, and using different light rail transit lines at different time spans. The results show that Trans-Sense can achieve an average recall and precision of 95.35% and 90.1%, respectively, in discriminating lightrail stations. Moreover, the empirical distributions governing the different time delays affecting a passenger’s total trip time enable predicting the right time of arrival of a passenger to her destination with an accuracy of 91.81%.In addition, the system estimates the stations dimensions with an accuracy of 95.71%.
Tasks
Published	2019-06-14
URL	https://arxiv.org/abs/1906.07575v1
PDF	https://arxiv.org/pdf/1906.07575v1.pdf
PWC	https://paperswithcode.com/paper/trans-sense-real-time-transportation-schedule
Repo
Framework

Complexity of Stochastic Dual Dynamic Programming


Title	Complexity of Stochastic Dual Dynamic Programming
Authors	Guanghui Lan
Abstract	Stochastic dual dynamic programming is a cutting plane type algorithm for multi-stage stochastic optimization originated about 30 years ago. In spite of its popularity in practice, there does not exist any analysis on the convergence rates of this method. In this paper, we first establish the number of iterations, i.e., iteration complexity, required by a basic dynamic cutting plane method for solving relatively simple multi-stage optimization problems, by introducing novel mathematical tools including the saturation of search points. We then refine these basic tools and establish the iteration complexity for both deterministic and stochastic dual dynamic programming methods for solving more general multi-stage stochastic optimization problems under the standard stage-wise independence assumption. Our results indicate that the complexity of these methods mildly increases with the number of stages $T$, in fact linearly dependent on $T$ for discounted problems. Therefore, they are efficient for strategic decision making which involves a large number of stages, but with a relatively small number of decision variables in each stage. Without explicitly discretizing the state and action spaces, these methods might also be pertinent to the related reinforcement learning and stochastic control areas.
Tasks	Decision Making, Stochastic Optimization
Published	2019-12-16
URL	https://arxiv.org/abs/1912.07702v3
PDF	https://arxiv.org/pdf/1912.07702v3.pdf
PWC	https://paperswithcode.com/paper/complexity-of-stochastic-dual-dynamic
Repo
Framework

Reduced network extremal ensemble learning (RenEEL) scheme for community detection in complex networks


Title	Reduced network extremal ensemble learning (RenEEL) scheme for community detection in complex networks
Authors	Jiahao Guo, Pramesh Singh, Kevin E. Bassler
Abstract	We introduce an ensemble learning scheme for community detection in complex networks. The scheme uses a Machine Learning algorithmic paradigm we call Extremal Ensemble Learning. It uses iterative extremal updating of an ensemble of network partitions, which can be found by a conventional base algorithm, to find a node partition that maximizes modularity. At each iteration, core groups of nodes that are in the same community in every ensemble partition are identified and used to form a reduced network. Partitions of the reduced network are then found and used to update the ensemble. The smaller size of the reduced network makes the scheme efficient. We use the scheme to analyze the community structure in a set of commonly studied benchmark networks and find that it outperforms all other known methods for finding the partition with maximum modularity.
Tasks
Published	2019-09-23
URL	https://arxiv.org/abs/1909.10491v1
PDF	https://arxiv.org/pdf/1909.10491v1.pdf
PWC	https://paperswithcode.com/paper/reduced-network-extremal-ensemble-learning
Repo
Framework

On Generalization Bounds of a Family of Recurrent Neural Networks


Title	On Generalization Bounds of a Family of Recurrent Neural Networks
Authors	Minshuo Chen, Xingguo Li, Tuo Zhao
Abstract	Recurrent Neural Networks (RNNs) have been widely applied to sequential data analysis. Due to their complicated modeling structures, however, the theory behind is still largely missing. To connect theory and practice, we study the generalization properties of vanilla RNNs as well as their variants, including Minimal Gated Unit (MGU), Long Short Term Memory (LSTM), and Convolutional (Conv) RNNs. Specifically, our theory is established under the PAC-Learning framework. The generalization bound is presented in terms of the spectral norms of the weight matrices and the total number of parameters. We also establish refined generalization bounds with additional norm assumptions, and draw a comparison among these bounds. We remark: (1) Our generalization bound for vanilla RNNs is significantly tighter than the best of existing results; (2) We are not aware of any other generalization bounds for MGU, LSTM, and Conv RNNs in the exiting literature; (3) We demonstrate the advantages of these variants in generalization.
Tasks
Published	2019-10-28
URL	https://arxiv.org/abs/1910.12947v2
PDF	https://arxiv.org/pdf/1910.12947v2.pdf
PWC	https://paperswithcode.com/paper/on-generalization-bounds-of-a-family-of-1
Repo
Framework

Ultimate Power of Inference Attacks: Privacy Risks of Learning High-Dimensional Graphical Models


Title	Ultimate Power of Inference Attacks: Privacy Risks of Learning High-Dimensional Graphical Models
Authors	Sasi Kumar Murakonda, Reza Shokri, George Theodorakopoulos
Abstract	Models leak information about their training data. This enables attackers to infer sensitive information about their training sets, notably determine if a data sample was part of the model’s training set. The existing works empirically show the possibility of these tracing (membership inference) attacks against complex models with a large number of parameters. However, the attack results are dependent on the specific training data, can be obtained only after the tedious process of training the model and performing the attack, and are missing any measure of the confidence and unused potential power of the attack. A model designer is interested in identifying which model structures leak more information, how adding new parameters to the model increases its privacy risk, and what is the gain of adding new data points to decrease the overall information leakage. The privacy analysis should also enable designing the most powerful inference attack. In this paper, we design a theoretical framework to analyze the maximum power of tracing attacks against high-dimensional models, with the focus on probabilistic graphical models. We provide a tight upper-bound on the power (true positive rate) of these attacks, with respect to their error (false positive rate). The bound, as it should be, is independent of the knowledge and algorithm of any specific attack, as well as the values of particular samples in the training set. It provides a measure of the potential leakage of a model given its structure, as a function of the structure complexity and the size of training set.
Tasks	Inference Attack
Published	2019-05-29
URL	https://arxiv.org/abs/1905.12774v2
PDF	https://arxiv.org/pdf/1905.12774v2.pdf
PWC	https://paperswithcode.com/paper/ultimate-power-of-inference-attacks-privacy
Repo
Framework

Facial Expression Recognition Using Disentangled Adversarial Learning


Title	Facial Expression Recognition Using Disentangled Adversarial Learning
Authors	Kamran Ali, Charles E. Hughes
Abstract	The representation used for Facial Expression Recognition (FER) usually contain expression information along with other variations such as identity and illumination. In this paper, we propose a novel Disentangled Expression learning-Generative Adversarial Network (DE-GAN) to explicitly disentangle facial expression representation from identity information. In this learning by reconstruction method, facial expression representation is learned by reconstructing an expression image employing an encoder-decoder based generator. This expression representation is disentangled from identity component by explicitly providing the identity code to the decoder part of DE-GAN. The process of expression image reconstruction and disentangled expression representation learning is improved by performing expression and identity classification in the discriminator of DE-GAN. The disentangled facial expression representation is then used for facial expression recognition employing simple classifiers like SVM or MLP. The experiments are performed on publicly available and widely used face expression databases (CK+, MMI, Oulu-CASIA). The experimental results show that the proposed technique produces comparable results with state-of-the-art methods.
Tasks	Facial Expression Recognition, Image Reconstruction, Representation Learning
Published	2019-09-28
URL	https://arxiv.org/abs/1909.13135v1
PDF	https://arxiv.org/pdf/1909.13135v1.pdf
PWC	https://paperswithcode.com/paper/facial-expression-recognition-using-1
Repo
Framework

From Bilingual to Multilingual Neural Machine Translation by Incremental Training


Title	From Bilingual to Multilingual Neural Machine Translation by Incremental Training
Authors	Carlos Escolano, Marta R. Costa-Jussà, José A. R. Fonollosa
Abstract	Multilingual Neural Machine Translation approaches are based on the use of task-specific models and the addition of one more language can only be done by retraining the whole system. In this work, we propose a new training schedule that allows the system to scale to more languages without modification of the previous components based on joint training and language-independent encoder/decoder modules allowing for zero-shot translation. This work in progress shows close results to the state-of-the-art in the WMT task.
Tasks	Machine Translation
Published	2019-06-28
URL	https://arxiv.org/abs/1907.00735v2
PDF	https://arxiv.org/pdf/1907.00735v2.pdf
PWC	https://paperswithcode.com/paper/from-bilingual-to-multilingual-neural-machine
Repo
Framework

Voice Biometrics Security: Extrapolating False Alarm Rate via Hierarchical Bayesian Modeling of Speaker Verification Scores


Title	Voice Biometrics Security: Extrapolating False Alarm Rate via Hierarchical Bayesian Modeling of Speaker Verification Scores
Authors	Alexey Sholokhov, Tomi Kinnunen, Ville Vestman, Kong Aik Lee
Abstract	How secure automatic speaker verification (ASV) technology is? More concretely, given a specific target speaker, how likely is it to find another person who gets falsely accepted as that target? This question may be addressed empirically by studying naturally confusable pairs of speakers within a large enough corpus. To this end, one might expect to find at least some speaker pairs that are indistinguishable from each other in terms of ASV. To a certain extent, such aim is mirrored in the standardized ASV evaluation benchmarks. However, the number of speakers in such evaluation benchmarks represents only a small fraction of all possible human voices, making it challenging to extrapolate performance beyond a given corpus. Furthermore, the impostors used in performance evaluation are usually selected randomly. A potentially more meaningful definition of an impostor - at least in the context of security-driven ASV applications - would be closest (most confusable) other speaker to a given target. We put forward a novel performance assessment framework to address both the inadequacy of the random-impostor evaluation model and the size limitation of evaluation corpora by addressing ASV security against closest impostors on arbitrarily large datasets. The framework allows one to make a prediction of the safety of given ASV technology, in its current state, for arbitrarily large speaker database size consisting of virtual (sampled) speakers. As a proof-of-concept, we analyze the performance of two state-of-the-art ASV systems, based on i-vector and x-vector speaker embeddings (as implemented in the popular Kaldi toolkit), on the recent VoxCeleb 1 & 2 corpora. We found that neither the i-vector or x-vector system is immune to increased false alarm rate at increased impostor database size.
Tasks	Speaker Verification
Published	2019-11-04
URL	https://arxiv.org/abs/1911.01182v1
PDF	https://arxiv.org/pdf/1911.01182v1.pdf
PWC	https://paperswithcode.com/paper/voice-biometrics-security-extrapolating-false
Repo
Framework

Adaptive Music Composition for Games


Title	Adaptive Music Composition for Games
Authors	Patrick Hutchings, Jon McCormack
Abstract	The generation of music that adapts dynamically to content and actions has an important role in building more immersive, memorable and emotive game experiences. To date, the development of adaptive music systems for video games is limited by both the nature of algorithms used for real-time music generation and the limited modelling of player action, game world context and emotion in current games. We propose that these issues must be addressed in tandem for the quality and flexibility of adaptive game music to significantly improve. Cognitive models of knowledge organisation and emotional affect are integrated with multi-modal, multi-agent composition techniques to produce a novel Adaptive Music System (AMS). The system is integrated into two stylistically distinct games. Gamers reported an overall higher immersion and correlation of music with game-world concepts with the AMS than with the original game soundtracks in both games.
Tasks	Music Generation
Published	2019-07-02
URL	https://arxiv.org/abs/1907.01154v1
PDF	https://arxiv.org/pdf/1907.01154v1.pdf
PWC	https://paperswithcode.com/paper/adaptive-music-composition-for-games
Repo
Framework

MediaEval 2019: Concealed FGSM Perturbations for Privacy Preservation


Title	MediaEval 2019: Concealed FGSM Perturbations for Privacy Preservation
Authors	Panagiotis Linardos, Suzanne Little, Kevin McGuinness
Abstract	This work tackles the Pixel Privacy task put forth by MediaEval 2019. Our goal is to manipulate images in a way that conceals them from automatic scene classifiers while preserving the original image quality. We use the fast gradient sign method, which normally has a corrupting influence on image appeal, and devise two methods to minimize the damage. The first approach uses a map of pixel locations that are either salient or flat, and directs perturbations away from them. The second approach subtracts the gradient of an aesthetics evaluation model from the gradient of the attack model to guide the perturbations towards a direction that preserves appeal. We make our code available at: https://git.io/JesXr.
Tasks
Published	2019-10-25
URL	https://arxiv.org/abs/1910.11603v1
PDF	https://arxiv.org/pdf/1910.11603v1.pdf
PWC	https://paperswithcode.com/paper/mediaeval-2019-concealed-fgsm-perturbations
Repo
Framework

Engineered Self-Organization for Resilient Robot Self-Assembly with Minimal Surprise


Title	Engineered Self-Organization for Resilient Robot Self-Assembly with Minimal Surprise
Authors	Tanja Katharina Kaiser, Heiko Hamann
Abstract	In collective robotic systems, the automatic generation of controllers for complex tasks is still a challenging problem. Open-ended evolution of complex robot behaviors can be a possible solution whereby an intrinsic driver for pattern formation and self-organization may prove to be important. We implement such a driver in collective robot systems by evolving prediction networks as world models in pair with action-selection networks. Fitness is given for good predictions which causes a bias towards easily predictable environments and behaviors in the form of emergent patterns, that is, environments of minimal surprise. There is no task-dependent bias or any other explicit predetermination for the different qualities of the emerging patterns. A careful configuration of actions, sensor models, and the environment is required to stimulate the emergence of complex behaviors. We study self-assembly to increase the scenario’s complexity for our minimal surprise approach and, at the same time, limit the complexity of our simulations to a grid world to manage the feasibility of this approach. We investigate the impact of different swarm densities and the shape of the environment on the emergent patterns. Furthermore, we study how evolution can be biased towards the emergence of desired patterns. We analyze the resilience of the resulting self-assembly behaviors by causing damages to the assembled pattern and observe the self-organized reassembly of the structure. In summary, we evolved swarm behaviors for resilient self-assembly and successfully engineered self-organization in simulation. In future work, we plan to transfer our approach to a swarm of real robots.
Tasks
Published	2019-02-14
URL	https://arxiv.org/abs/1902.05485v3
PDF	https://arxiv.org/pdf/1902.05485v3.pdf
PWC	https://paperswithcode.com/paper/engineered-self-organization-for-resilient
Repo
Framework

Capacity Bounded Differential Privacy


Title	Capacity Bounded Differential Privacy
Authors	Kamalika Chaudhuri, Jacob Imola, Ashwin Machanavajjhala
Abstract	Differential privacy, a notion of algorithmic stability, is a gold standard for measuring the additional risk an algorithm’s output poses to the privacy of a single record in the dataset. Differential privacy is defined as the distance between the output distribution of an algorithm on neighboring datasets that differ in one entry. In this work, we present a novel relaxation of differential privacy, capacity bounded differential privacy, where the adversary that distinguishes output distributions is assumed to be capacity-bounded – i.e. bounded not in computational power, but in terms of the function class from which their attack algorithm is drawn. We model adversaries in terms of restricted f-divergences between probability distributions, and study properties of the definition and algorithms that satisfy them.
Tasks
Published	2019-07-03
URL	https://arxiv.org/abs/1907.02159v1
PDF	https://arxiv.org/pdf/1907.02159v1.pdf
PWC	https://paperswithcode.com/paper/capacity-bounded-differential-privacy
Repo
Framework

Distributionally Robust Formulation and Model Selection for the Graphical Lasso


Title	Distributionally Robust Formulation and Model Selection for the Graphical Lasso
Authors	Pedro Cisneros-Velarde, Sang-Yun Oh, Alexander Petersen
Abstract	Building on a recent framework for distributionally robust optimization, we consider estimation of the inverse covariance matrix for multivariate data. We provide a novel notion of a Wasserstein ambiguity set specifically tailored to this estimation problem, leading to a tractable class of regularized estimators. Special cases include penalized likelihood estimators for Gaussian data, specifically the graphical lasso estimator. As a consequence of this formulation, the radius of the Wasserstein ambiguity set is directly related to the regularization parameter in the estimation problem. Using this relationship, the level of robustness of the estimation procedure can be shown to correspond to the level of confidence with which the ambiguity set contains a distribution with the population covariance. Furthermore, a unique feature of our formulation is that the radius can be expressed in closed-form as a function of the ordinary sample covariance matrix. Taking advantage of this finding, we develop a simple algorithm to determine a regularization parameter for graphical lasso, using only the bootstrapped sample covariance matrices, meaning that computationally expensive repeated evaluation of the graphical lasso algorithm is not necessary. Alternatively, the distributionally robust formulation can also quantify the robustness of the corresponding estimator if one uses an off-the-shelf method such as cross-validation. Finally, we numerically study the obtained regularization criterion and analyze the robustness of other automated tuning procedures used in practice.
Tasks	Model Selection
Published	2019-05-22
URL	https://arxiv.org/abs/1905.08975v2
PDF	https://arxiv.org/pdf/1905.08975v2.pdf
PWC	https://paperswithcode.com/paper/distributionally-robust-formulation-and-model
Repo
Framework

Event-Based Motion Segmentation by Motion Compensation


Title	Event-Based Motion Segmentation by Motion Compensation
Authors	Timo Stoffregen, Guillermo Gallego, Tom Drummond, Lindsay Kleeman, Davide Scaramuzza
Abstract	In contrast to traditional cameras, whose pixels have a common exposure time, event-based cameras are novel bio-inspired sensors whose pixels work independently and asynchronously output intensity changes (called “events”), with microsecond resolution. Since events are caused by the apparent motion of objects, event-based cameras sample visual information based on the scene dynamics and are, therefore, a more natural fit than traditional cameras to acquire motion, especially at high speeds, where traditional cameras suffer from motion blur. However, distinguishing between events caused by different moving objects and by the camera’s ego-motion is a challenging task. We present the first per-event segmentation method for splitting a scene into independently moving objects. Our method jointly estimates the event-object associations (i.e., segmentation) and the motion parameters of the objects (or the background) by maximization of an objective function, which builds upon recent results on event-based motion-compensation. We provide a thorough evaluation of our method on a public dataset, outperforming the state-of-the-art by as much as 10%. We also show the first quantitative evaluation of a segmentation algorithm for event cameras, yielding around 90% accuracy at 4 pixels relative displacement.
Tasks	Motion Compensation, Motion Segmentation
Published	2019-04-02
URL	https://arxiv.org/abs/1904.01293v4
PDF	https://arxiv.org/pdf/1904.01293v4.pdf
PWC	https://paperswithcode.com/paper/event-based-motion-segmentation-by-motion
Repo
Framework