January 26, 2020

3279 words 16 mins read

Paper Group ANR 1601

Online k-means Clustering. On resampling vs. adjusting probabilistic graphical models in estimation of distribution algorithms. Amplifying Rényi Differential Privacy via Shuffling. Deep Recurrent Factor Model: Interpretable Non-Linear and Time-Varying Multi-Factor Model. Med2Meta: Learning Representations of Medical Concepts with Meta-Embeddings. D …

Online k-means Clustering


Title	Online k-means Clustering
Authors	Vincent Cohen-Addad, Benjamin Guedj, Varun Kanade, Guy Rom
Abstract	We study the problem of online clustering where a clustering algorithm has to assign a new point that arrives to one of $k$ clusters. The specific formulation we use is the $k$-means objective: At each time step the algorithm has to maintain a set of k candidate centers and the loss incurred is the squared distance between the new point and the closest center. The goal is to minimize regret with respect to the best solution to the $k$-means objective ($\mathcal{C}$) in hindsight. We show that provided the data lies in a bounded region, an implementation of the Multiplicative Weights Update Algorithm (MWUA) using a discretized grid achieves a regret bound of $\tilde{O}(\sqrt{T})$ in expectation. We also present an online-to-offline reduction that shows that an efficient no-regret online algorithm (despite being allowed to choose a different set of candidate centres at each round) implies an offline efficient algorithm for the $k$-means problem. In light of this hardness, we consider the slightly weaker requirement of comparing regret with respect to $(1 + \epsilon) \mathcal{C}$ and present a no-regret algorithm with runtime $O\left(T(\mathrm{poly}(log(T),k,d,1/\epsilon)^{k(d+O(1))}\right)$. Our algorithm is based on maintaining an incremental coreset and an adaptive variant of the MWUA. We show that na"{i}ve online algorithms, such as \emph{Follow The Leader}, fail to produce sublinear regret in the worst case. We also report preliminary experiments with synthetic and real-world data.
Tasks
Published	2019-09-15
URL	https://arxiv.org/abs/1909.06861v1
PDF	https://arxiv.org/pdf/1909.06861v1.pdf
PWC	https://paperswithcode.com/paper/online-k-means-clustering
Repo
Framework

On resampling vs. adjusting probabilistic graphical models in estimation of distribution algorithms


Title	On resampling vs. adjusting probabilistic graphical models in estimation of distribution algorithms
Authors	Mohamed El Yafrani, Marcella S. R. Martins, Myriam R. B. S. Delgado, Inkyung Sung, Ricardo Lüders, Markus Wagner
Abstract	The Bayesian Optimisation Algorithm (BOA) is an Estimation of Distribution Algorithm (EDA) that uses a Bayesian network as probabilistic graphical model (PGM). Determining the optimal Bayesian network structure given a solution sample is an NP-hard problem. This step should be completed at each iteration of BOA, resulting in a very time-consuming process. For this reason most implementations use greedy estimation algorithms such as K2. However, we show in this paper that significant changes in PGM structure do not occur so frequently, and can be particularly sparse at the end of evolution. A statistical study of BOA is thus presented to characterise a pattern of PGM adjustments that can be used as a guide to reduce the frequency of PGM updates during the evolutionary process. This is accomplished by proposing a new BOA-based optimisation approach (FBOA) whose PGM is not updated at each iteration. This new approach avoids the computational burden usually found in the standard BOA. The results compare the performances of both algorithms on an NK-landscape optimisation problem using the correlation between the ruggedness and the expected runtime over enumerated instances. The experiments show that FBOA presents competitive results while significantly saving computational time.
Tasks	Bayesian Optimisation
Published	2019-02-15
URL	http://arxiv.org/abs/1902.05946v1
PDF	http://arxiv.org/pdf/1902.05946v1.pdf
PWC	https://paperswithcode.com/paper/on-resampling-vs-adjusting-probabilistic
Repo
Framework

Amplifying Rényi Differential Privacy via Shuffling


Title	Amplifying Rényi Differential Privacy via Shuffling
Authors	Eloïse Berthier, Sai Praneeth Karimireddy
Abstract	Differential privacy is a useful tool to build machine learning models which do not release too much information about the training data. We study the R'enyi differential privacy of stochastic gradient descent when each training example is sampled without replacement (also known as cyclic SGD). Cyclic SGD is typically faster than traditional SGD and is the algorithm of choice in large-scale implementations. We recover privacy guarantees for cyclic SGD which are competitive with those known for sampling with replacement. Our proof techniques make no assumptions on the model or on the data and are hence widely applicable.
Tasks
Published	2019-07-11
URL	https://arxiv.org/abs/1907.05156v3
PDF	https://arxiv.org/pdf/1907.05156v3.pdf
PWC	https://paperswithcode.com/paper/amplifying-renyi-differential-privacy-via
Repo
Framework

Deep Recurrent Factor Model: Interpretable Non-Linear and Time-Varying Multi-Factor Model


Title	Deep Recurrent Factor Model: Interpretable Non-Linear and Time-Varying Multi-Factor Model
Authors	Kei Nakagawa, Tomoki Ito, Masaya Abe, Kiyoshi Izumi
Abstract	A linear multi-factor model is one of the most important tools in equity portfolio management. The linear multi-factor models are widely used because they can be easily interpreted. However, financial markets are not linear and their accuracy is limited. Recently, deep learning methods were proposed to predict stock return in terms of the multi-factor model. Although these methods perform quite well, they have significant disadvantages such as a lack of transparency and limitations in the interpretability of the prediction. It is thus difficult for institutional investors to use black-box-type machine learning techniques in actual investment practice because they should show accountability to their customers. Consequently, the solution we propose is based on LSTM with LRP. Specifically, we extend the linear multi-factor model to be non-linear and time-varying with LSTM. Then, we approximate and linearize the learned LSTM models by LRP. We call this LSTM+LRP model a deep recurrent factor model. Finally, we perform an empirical analysis of the Japanese stock market and show that our recurrent model has better predictive capability than the traditional linear model and fully-connected deep learning methods.
Tasks
Published	2019-01-20
URL	http://arxiv.org/abs/1901.11493v1
PDF	http://arxiv.org/pdf/1901.11493v1.pdf
PWC	https://paperswithcode.com/paper/deep-recurrent-factor-model-interpretable-non
Repo
Framework

Med2Meta: Learning Representations of Medical Concepts with Meta-Embeddings


Title	Med2Meta: Learning Representations of Medical Concepts with Meta-Embeddings
Authors	Shaika Chowdhury, Chenwei Zhang, Philip S. Yu, Yuan Luo
Abstract	Distributed representations of medical concepts have been used to support downstream clinical tasks recently. Electronic Health Records (EHR) capture different aspects of patients’ hospital encounters and serve as a rich source for augmenting clinical decision making by learning robust medical concept embeddings. However, the same medical concept can be recorded in different modalities (e.g., clinical notes, lab results)-with each capturing salient information unique to that modality-and a holistic representation calls for relevant feature ensemble from all information sources. We hypothesize that representations learned from heterogeneous data types would lead to performance enhancement on various clinical informatics and predictive modeling tasks. To this end, our proposed approach makes use of meta-embeddings, embeddings aggregated from learned embeddings. Firstly, modality-specific embeddings for each medical concept is learned with graph autoencoders. The ensemble of all the embeddings is then modeled as a meta-embedding learning problem to incorporate their correlating and complementary information through a joint reconstruction. Empirical results of our model on both quantitative and qualitative clinical evaluations have shown improvements over state-of-the-art embedding models, thus validating our hypothesis.
Tasks	Decision Making
Published	2019-12-06
URL	https://arxiv.org/abs/1912.03366v2
PDF	https://arxiv.org/pdf/1912.03366v2.pdf
PWC	https://paperswithcode.com/paper/med2meta-learning-representations-of-medical
Repo
Framework

Deep Learning for Human Affect Recognition: Insights and New Developments


Title	Deep Learning for Human Affect Recognition: Insights and New Developments
Authors	Philipp V. Rouast, Marc T. P. Adam, Raymond Chiong
Abstract	Automatic human affect recognition is a key step towards more natural human-computer interaction. Recent trends include recognition in the wild using a fusion of audiovisual and physiological sensors, a challenging setting for conventional machine learning algorithms. Since 2010, novel deep learning algorithms have been applied increasingly in this field. In this paper, we review the literature on human affect recognition between 2010 and 2017, with a special focus on approaches using deep neural networks. By classifying a total of 950 studies according to their usage of shallow or deep architectures, we are able to show a trend towards deep learning. Reviewing a subset of 233 studies that employ deep neural networks, we comprehensively quantify their applications in this field. We find that deep learning is used for learning of (i) spatial feature representations, (ii) temporal feature representations, and (iii) joint feature representations for multimodal sensor data. Exemplary state-of-the-art architectures illustrate the progress. Our findings show the role deep architectures will play in human affect recognition, and can serve as a reference point for researchers working on related applications.
Tasks
Published	2019-01-09
URL	http://arxiv.org/abs/1901.02884v1
PDF	http://arxiv.org/pdf/1901.02884v1.pdf
PWC	https://paperswithcode.com/paper/deep-learning-for-human-affect-recognition
Repo
Framework

PODDP: Partially Observable Differential Dynamic Programming for Latent Belief Space Planning


Title	PODDP: Partially Observable Differential Dynamic Programming for Latent Belief Space Planning
Authors	Dicong Qiu, Yibiao Zhao, Chris L. Baker
Abstract	Autonomous agents are limited in their ability to observe the world state. Partially observable Markov decision processes (POMDPs) formally model the problem of planning under world state uncertainty, but POMDPs with continuous actions and nonlinear dynamics suitable for robotics applications are challenging to solve. In this paper, we present an efficient differential dynamic programming (DDP) algorithm for belief space planning in POMDPs with uncertainty over a discrete latent state, and continuous states, actions, observations, and nonlinear dynamics. This representation allows planning of dynamic trajectories which are sensitive to structured uncertainty over discrete latent world states. We develop dynamic programming techniques to optimize a contingency plan over a tree of possible observations and belief space trajectories, and also derive a hierarchical version of the algorithm. Our method is applicable to problems with uncertainty over the cost or reward function (e.g., the configuration of goals or obstacles), uncertainty over the dynamics (e.g., the dynamical mode of a hybrid system), and uncertainty about interactions, where other agents’ behavior is conditioned on latent intentions. Benchmarks show that our algorithm outperforms popular heuristic approaches to planning under uncertainty, and results from an autonomous lane changing task demonstrate that our algorithm can synthesize robust interactive trajectories.
Tasks
Published	2019-12-14
URL	https://arxiv.org/abs/1912.06787v1
PDF	https://arxiv.org/pdf/1912.06787v1.pdf
PWC	https://paperswithcode.com/paper/poddp-partially-observable-differential
Repo
Framework

Evaluating the Transferability and Adversarial Discrimination of Convolutional Neural Networks for Threat Object Detection and Classification within X-Ray Security Imagery


Title	Evaluating the Transferability and Adversarial Discrimination of Convolutional Neural Networks for Threat Object Detection and Classification within X-Ray Security Imagery
Authors	Yona Falinie A. Gaus, Neelanjan Bhowmik, Samet Akcay, Toby P. Breckon
Abstract	X-ray imagery security screening is essential to maintaining transport security against a varying profile of threat or prohibited items. Particular interest lies in the automatic detection and classification of weapons such as firearms and knives within complex and cluttered X-ray security imagery. Here, we address this problem by exploring various end-to-end object detection Convolutional Neural Network (CNN) architectures. We evaluate several leading variants spanning the Faster R-CNN, Mask R-CNN, and RetinaNet architectures to explore the transferability of such models between varying X-ray scanners with differing imaging geometries, image resolutions and material colour profiles. Whilst the limited availability of X-ray threat imagery can pose a challenge, we employ a transfer learning approach to evaluate whether such inter-scanner generalisation may exist over a multiple class detection problem. Overall, we achieve maximal detection performance using a Faster R-CNN architecture with a ResNet$_{101}$ classification network, obtaining 0.88 and 0.86 of mean Average Precision (mAP) for a three-class and two class item from varying X-ray imaging sources. Our results exhibit a remarkable degree of generalisability in terms of cross-scanner performance (mAP: 0.87, firearm detection: 0.94 AP). In addition, we examine the inherent adversarial discriminative capability of such networks using a specifically generated adversarial dataset for firearms detection - with a variable low false positive, as low as 5%, this shows both the challenge and promise of such threat detection within X-ray security imagery.
Tasks	Object Detection, Transfer Learning
Published	2019-11-20
URL	https://arxiv.org/abs/1911.08966v1
PDF	https://arxiv.org/pdf/1911.08966v1.pdf
PWC	https://paperswithcode.com/paper/evaluating-the-transferability-and
Repo
Framework

Microblog Hashtag Generation via Encoding Conversation Contexts


Title	Microblog Hashtag Generation via Encoding Conversation Contexts
Authors	Yue Wang, Jing Li, Irwin King, Michael R. Lyu, Shuming Shi
Abstract	Automatic hashtag annotation plays an important role in content understanding for microblog posts. To date, progress made in this field has been restricted to phrase selection from limited candidates, or word-level hashtag discovery using topic models. Different from previous work considering hashtags to be inseparable, our work is the first effort to annotate hashtags with a novel sequence generation framework via viewing the hashtag as a short sequence of words. Moreover, to address the data sparsity issue in processing short microblog posts, we propose to jointly model the target posts and the conversation contexts initiated by them with bidirectional attention. Extensive experimental results on two large-scale datasets, newly collected from English Twitter and Chinese Weibo, show that our model significantly outperforms state-of-the-art models based on classification. Further studies demonstrate our ability to effectively generate rare and even unseen hashtags, which is however not possible for most existing methods.
Tasks	Topic Models
Published	2019-05-18
URL	https://arxiv.org/abs/1905.07584v1
PDF	https://arxiv.org/pdf/1905.07584v1.pdf
PWC	https://paperswithcode.com/paper/microblog-hashtag-generation-via-encoding
Repo
Framework

Generative training of quantum Boltzmann machines with hidden units


Title	Generative training of quantum Boltzmann machines with hidden units
Authors	Nathan Wiebe, Leonard Wossnig
Abstract	In this article we provide a method for fully quantum generative training of quantum Boltzmann machines with both visible and hidden units while using quantum relative entropy as an objective. This is significant because prior methods were not able to do so due to mathematical challenges posed by the gradient evaluation. We present two novel methods for solving this problem. The first proposal addresses it, for a class of restricted quantum Boltzmann machines with mutually commuting Hamiltonians on the hidden units, by using a variational upper bound on the quantum relative entropy. The second one uses high-order divided difference methods and linear-combinations of unitaries to approximate the exact gradient of the relative entropy for a generic quantum Boltzmann machine. Both methods are efficient under the assumption that Gibbs state preparation is efficient and that the Hamiltonian are given by a sparse row-computable matrix.
Tasks
Published	2019-05-23
URL	https://arxiv.org/abs/1905.09902v1
PDF	https://arxiv.org/pdf/1905.09902v1.pdf
PWC	https://paperswithcode.com/paper/generative-training-of-quantum-boltzmann
Repo
Framework

Depth Map Estimation for Free-Viewpoint Television


Title	Depth Map Estimation for Free-Viewpoint Television
Authors	Dawid Mieloch, Olgierd Stankiewicz, Marek Domański
Abstract	The paper presents a new method of depth estimation dedicated for free-viewpoint television (FTV). The estimation is performed for segments and thus their size can be used to control a trade-off between the quality of depth maps and the processing time of their estimation. The proposed algorithm can take as its input multiple arbitrarily positioned views which are simultaneously used to produce multiple inter view consistent output depth maps. The presented depth estimation method uses novel parallelization and temporal consistency enhancement methods that significantly reduce the processing time of depth estimation. An experimental assessment of the proposals has been performed, based on the analysis of virtual view quality in FTV. The results show that the proposed method provides an improvement of the depth map quality over the state of-the-art method, simultaneously reducing the complexity of depth estimation. The consistency of depth maps, which is crucial for the quality of the synthesized video and thus the quality of experience of navigating through a 3D scene, is also vastly improved.
Tasks	Depth Estimation
Published	2019-09-05
URL	https://arxiv.org/abs/1909.02294v1
PDF	https://arxiv.org/pdf/1909.02294v1.pdf
PWC	https://paperswithcode.com/paper/depth-map-estimation-for-free-viewpoint
Repo
Framework

Optimal Decision-Making in Mixed-Agent Partially Observable Stochastic Environments via Reinforcement Learning


Title	Optimal Decision-Making in Mixed-Agent Partially Observable Stochastic Environments via Reinforcement Learning
Authors	Roi Ceren
Abstract	Optimal decision making with limited or no information in stochastic environments where multiple agents interact is a challenging topic in the realm of artificial intelligence. Reinforcement learning (RL) is a popular approach for arriving at optimal strategies by predicating stimuli, such as the reward for following a strategy, on experience. RL is heavily explored in the single-agent context, but is a nascent concept in multiagent problems. To this end, I propose several principled model-free and partially model-based reinforcement learning approaches for several multiagent settings. In the realm of normative reinforcement learning, I introduce scalable extensions to Monte Carlo exploring starts for partially observable Markov Decision Processes (POMDP), dubbed MCES-P, where I expand the theory and algorithm to the multiagent setting. I first examine MCES-P with probably approximately correct (PAC) bounds in the context of multiagent setting, showing MCESP+PAC holds in the presence of other agents. I then propose a more sample-efficient methodology for antagonistic settings, MCESIP+PAC. For cooperative settings, I extend MCES-P to the Multiagent POMDP, dubbed MCESMP+PAC. I then explore the use of reinforcement learning as a methodology in searching for optima in realistic and latent model environments. First, I explore a parameterized Q-learning approach in modeling humans learning to reason in an uncertain, multiagent environment. Next, I propose an implementation of MCES-P, along with image segmentation, to create an adaptive team-based reinforcement learning technique to positively identify the presence of phenotypically-expressed water and pathogen stress in crop fields.
Tasks	Decision Making, Q-Learning, Semantic Segmentation
Published	2019-01-04
URL	http://arxiv.org/abs/1901.01325v1
PDF	http://arxiv.org/pdf/1901.01325v1.pdf
PWC	https://paperswithcode.com/paper/optimal-decision-making-in-mixed-agent
Repo
Framework

Detecting Compromised Implicit Association Test Results Using Supervised Learning


Title	Detecting Compromised Implicit Association Test Results Using Supervised Learning
Authors	Brendon Boldt, Zack While, Eric Breimer
Abstract	An implicit association test is a human psychological test used to measure subconscious associations. While widely recognized by psychologists as an effective tool in measuring attitudes and biases, the validity of the results can be compromised if a subject does not follow the instructions or attempts to manipulate the outcome. Compared to previous work, we collect training data using a more generalized methodology. We train a variety of different classifiers to identify a participant’s first attempt versus a second possibly compromised attempt. To compromise the second attempt, participants are shown their score and are instructed to change it using one of five randomly selected deception methods. Compared to previous work, our methodology demonstrates a more robust and practical framework for accurately identifying a wide variety of deception techniques applicable to the IAT.
Tasks
Published	2019-09-03
URL	https://arxiv.org/abs/1909.01304v1
PDF	https://arxiv.org/pdf/1909.01304v1.pdf
PWC	https://paperswithcode.com/paper/detecting-compromised-implicit-association
Repo
Framework

Learning an Action-Conditional Model for Haptic Texture Generation


Title	Learning an Action-Conditional Model for Haptic Texture Generation
Authors	Negin Heravi, Wenzhen Yuan, Allison M. Okamura, Jeannette Bohg
Abstract	Rich haptic sensory feedback in response to user interactions is desirable for an effective, immersive virtual reality or teleoperation system. However, this feedback depends on material properties and user interactions in a complex, non-linear manner. Therefore, it is challenging to model the mapping from material and user interactions to haptic feedback in a way that generalizes over many variations of the user’s input. Current methodologies are typically conditioned on user interactions, but require a separate model for each material. In this paper, we present a learned action-conditional model that uses data from a vision-based tactile sensor (GelSight) and user’s action as input. This model predicts an induced acceleration that could be used to provide haptic vibration feedback to a user. We trained our proposed model on a publicly available dataset (Penn Haptic Texture Toolkit) that we augmented with GelSight measurements of the different materials. We show that a unified model over all materials outperforms previous methods and generalizes to new actions and new instances of the material categories in the dataset.
Tasks	Texture Synthesis
Published	2019-09-28
URL	https://arxiv.org/abs/1909.13025v1
PDF	https://arxiv.org/pdf/1909.13025v1.pdf
PWC	https://paperswithcode.com/paper/learning-an-action-conditional-model-for
Repo
Framework

Towards Interpretable and Learnable Risk Analysis for Entity Resolution


Title	Towards Interpretable and Learnable Risk Analysis for Entity Resolution
Authors	Zhaoqiang Chen, Qun Chen, Boyi Hou, Tianyi Duan, Zhanhuai Li, Guoliang Li
Abstract	Machine-learning-based entity resolution has been widely studied. However, some entity pairs may be mislabeled by machine learning models and existing studies do not study the risk analysis problem – predicting and interpreting which entity pairs are mislabeled. In this paper, we propose an interpretable and learnable framework for risk analysis, which aims to rank the labeled pairs based on their risks of being mislabeled. We first describe how to automatically generate interpretable risk features, and then present a learnable risk model and its training technique. Finally, we empirically evaluate the performance of the proposed approach on real data. Our extensive experiments have shown that the learning risk model can identify the mislabeled pairs with considerably higher accuracy than the existing alternatives.
Tasks	Entity Resolution
Published	2019-12-06
URL	https://arxiv.org/abs/1912.02947v1
PDF	https://arxiv.org/pdf/1912.02947v1.pdf
PWC	https://paperswithcode.com/paper/towards-interpretable-and-learnable-risk
Repo
Framework