May 5, 2019

3290 words 16 mins read

Paper Group ANR 459

Kernel Alignment Inspired Linear Discriminant Analysis. Consistency Ensuring in Social Web Services Based on Commitments Structure. From Dependence to Causation. Neurohex: A Deep Q-learning Hex Agent. Moving Beyond the Turing Test with the Allen AI Science Challenge. Markov Chain Truncation for Doubly-Intractable Inference. Kernel Balancing: A flex …

Kernel Alignment Inspired Linear Discriminant Analysis


Title	Kernel Alignment Inspired Linear Discriminant Analysis
Authors	Shuai Zheng, Chris Ding
Abstract	Kernel alignment measures the degree of similarity between two kernels. In this paper, inspired from kernel alignment, we propose a new Linear Discriminant Analysis (LDA) formulation, kernel alignment LDA (kaLDA). We first define two kernels, data kernel and class indicator kernel. The problem is to find a subspace to maximize the alignment between subspace-transformed data kernel and class indicator kernel. Surprisingly, the kernel alignment induced kaLDA objective function is very similar to classical LDA and can be expressed using between-class and total scatter matrices. This can be extended to multi-label data. We use a Stiefel-manifold gradient descent algorithm to solve this problem. We perform experiments on 8 single-label and 6 multi-label data sets. Results show that kaLDA has very good performance on many single-label and multi-label problems.
Tasks
Published	2016-10-14
URL	http://arxiv.org/abs/1610.04576v1
PDF	http://arxiv.org/pdf/1610.04576v1.pdf
PWC	https://paperswithcode.com/paper/kernel-alignment-inspired-linear-discriminant
Repo
Framework


Title	Consistency Ensuring in Social Web Services Based on Commitments Structure
Authors	Marzieh Adelnia, Mohammad Reza Khayyambashi
Abstract	Web Service is one of the most significant current discussions in information sharing technologies and one of the examples of service oriented processing. To ensure accurate execution of web services operations, it must be adaptable with policies of the social networks in which it signs up. This adaptation implements using controls called ‘Commitment’. This paper describes commitments structure and existing research about commitments and social web services, then suggests an algorithm for consistency of commitments in social web services. As regards the commitments may be executed concurrently, a key challenge in web services execution based on commitment structure is consistency ensuring in execution time. The purpose of this research is providing an algorithm for consistency ensuring between web services operations based on commitments structure.
Tasks
Published	2016-10-01
URL	http://arxiv.org/abs/1610.00086v1
PDF	http://arxiv.org/pdf/1610.00086v1.pdf
PWC	https://paperswithcode.com/paper/consistency-ensuring-in-social-web-services
Repo
Framework

From Dependence to Causation


Title	From Dependence to Causation
Authors	David Lopez-Paz
Abstract	Machine learning is the science of discovering statistical dependencies in data, and the use of those dependencies to perform predictions. During the last decade, machine learning has made spectacular progress, surpassing human performance in complex tasks such as object recognition, car driving, and computer gaming. However, the central role of prediction in machine learning avoids progress towards general-purpose artificial intelligence. As one way forward, we argue that causal inference is a fundamental component of human intelligence, yet ignored by learning algorithms. Causal inference is the problem of uncovering the cause-effect relationships between the variables of a data generating system. Causal structures provide understanding about how these systems behave under changing, unseen environments. In turn, knowledge about these causal dynamics allows to answer “what if” questions, describing the potential responses of the system under hypothetical manipulations and interventions. Thus, understanding cause and effect is one step from machine learning towards machine reasoning and machine intelligence. But, currently available causal inference algorithms operate in specific regimes, and rely on assumptions that are difficult to verify in practice. This thesis advances the art of causal inference in three different ways. First, we develop a framework for the study of statistical dependence based on copulas and random features. Second, we build on this framework to interpret the problem of causal inference as the task of distribution classification, yielding a family of novel causal inference algorithms. Third, we discover causal structures in convolutional neural network features using our algorithms. The algorithms presented in this thesis are scalable, exhibit strong theoretical guarantees, and achieve state-of-the-art performance in a variety of real-world benchmarks.
Tasks	Causal Inference, Object Recognition
Published	2016-07-12
URL	http://arxiv.org/abs/1607.03300v1
PDF	http://arxiv.org/pdf/1607.03300v1.pdf
PWC	https://paperswithcode.com/paper/from-dependence-to-causation
Repo
Framework

Neurohex: A Deep Q-learning Hex Agent


Title	Neurohex: A Deep Q-learning Hex Agent
Authors	Kenny Young, Ryan Hayward, Gautham Vasan
Abstract	DeepMind’s recent spectacular success in using deep convolutional neural nets and machine learning to build superhuman level agents — e.g. for Atari games via deep Q-learning and for the game of Go via Reinforcement Learning — raises many questions, including to what extent these methods will succeed in other domains. In this paper we consider DQL for the game of Hex: after supervised initialization, we use selfplay to train NeuroHex, an 11-layer CNN that plays Hex on the 13x13 board. Hex is the classic two-player alternate-turn stone placement game played on a rhombus of hexagonal cells in which the winner is whomever connects their two opposing sides. Despite the large action and state space, our system trains a Q-network capable of strong play with no search. After two weeks of Q-learning, NeuroHex achieves win-rates of 20.4% as first player and 2.1% as second player against a 1-second/move version of MoHex, the current ICGA Olympiad Hex champion. Our data suggests further improvement might be possible with more training time.
Tasks	Atari Games, Game of Go, Q-Learning
Published	2016-04-24
URL	http://arxiv.org/abs/1604.07097v2
PDF	http://arxiv.org/pdf/1604.07097v2.pdf
PWC	https://paperswithcode.com/paper/neurohex-a-deep-q-learning-hex-agent
Repo
Framework

Moving Beyond the Turing Test with the Allen AI Science Challenge


Title	Moving Beyond the Turing Test with the Allen AI Science Challenge
Authors	Carissa Schoenick, Peter Clark, Oyvind Tafjord, Peter Turney, Oren Etzioni
Abstract	Given recent successes in AI (e.g., AlphaGo’s victory against Lee Sedol in the game of GO), it’s become increasingly important to assess: how close are AI systems to human-level intelligence? This paper describes the Allen AI Science Challenge—an approach towards that goal which led to a unique Kaggle Competition, its results, the lessons learned, and our next steps.
Tasks	Game of Go
Published	2016-04-14
URL	http://arxiv.org/abs/1604.04315v3
PDF	http://arxiv.org/pdf/1604.04315v3.pdf
PWC	https://paperswithcode.com/paper/moving-beyond-the-turing-test-with-the-allen
Repo
Framework

Markov Chain Truncation for Doubly-Intractable Inference


Title	Markov Chain Truncation for Doubly-Intractable Inference
Authors	Colin Wei, Iain Murray
Abstract	Computing partition functions, the normalizing constants of probability distributions, is often hard. Variants of importance sampling give unbiased estimates of a normalizer Z, however, unbiased estimates of the reciprocal 1/Z are harder to obtain. Unbiased estimates of 1/Z allow Markov chain Monte Carlo sampling of “doubly-intractable” distributions, such as the parameter posterior for Markov Random Fields or Exponential Random Graphs. We demonstrate how to construct unbiased estimates for 1/Z given access to black-box importance sampling estimators for Z. We adapt recent work on random series truncation and Markov chain coupling, producing estimators with lower variance and a higher percentage of positive estimates than before. Our debiasing algorithms are simple to implement, and have some theoretical and empirical advantages over existing methods.
Tasks
Published	2016-10-15
URL	http://arxiv.org/abs/1610.05672v2
PDF	http://arxiv.org/pdf/1610.05672v2.pdf
PWC	https://paperswithcode.com/paper/markov-chain-truncation-for-doubly
Repo
Framework

Kernel Balancing: A flexible non-parametric weighting procedure for estimating causal effects


Title	Kernel Balancing: A flexible non-parametric weighting procedure for estimating causal effects
Authors	Chad Hazlett
Abstract	In the absence of unobserved confounders, matching and weighting methods are widely used to estimate causal quantities including the Average Treatment Effect on the Treated (ATT). Unfortunately, these methods do not necessarily achieve their goal of making the multivariate distribution of covariates for the control group identical to that of the treated, leaving some (potentially multivariate) functions of the covariates with different means between the two groups. When these “imbalanced” functions influence the non-treatment potential outcome, the conditioning on observed covariates fails, and ATT estimates may be biased. Kernel balancing, introduced here, targets a weaker requirement for unbiased ATT estimation, specifically, that the expected non-treatment potential outcome for the treatment and control groups are equal. The conditional expectation of the non-treatment potential outcome is assumed to fall in the space of functions associated with a choice of kernel, implying a set of basis functions in which this regression surface is linear. Weights are then chosen on the control units such that the treated and control group have equal means on these basis functions. As a result, the expectation of the non-treatment potential outcome must also be equal for the treated and control groups after weighting, allowing unbiased ATT estimation by subsequent difference in means or an outcome model using these weights. Moreover, the weights produced are (1) precisely those that equalize a particular kernel-based approximation of the multivariate distribution of covariates for the treated and control, and (2) equivalent to a form of stabilized inverse propensity score weighting, though it does not require assuming any model of the treatment assignment mechanism. An R package, KBAL, is provided to implement this approach.
Tasks
Published	2016-04-30
URL	http://arxiv.org/abs/1605.00155v1
PDF	http://arxiv.org/pdf/1605.00155v1.pdf
PWC	https://paperswithcode.com/paper/kernel-balancing-a-flexible-non-parametric
Repo
Framework

Online Nonnegative Matrix Factorization with General Divergences


Title	Online Nonnegative Matrix Factorization with General Divergences
Authors	Renbo Zhao, Vincent Y. F. Tan, Huan Xu
Abstract	We develop a unified and systematic framework for performing online nonnegative matrix factorization under a wide variety of important divergences. The online nature of our algorithm makes it particularly amenable to large-scale data. We prove that the sequence of learned dictionaries converges almost surely to the set of critical points of the expected loss function. We do so by leveraging the theory of stochastic approximations and projected dynamical systems. This result substantially generalizes the previous results obtained only for the squared-$\ell_2$ loss. Moreover, the novel techniques involved in our analysis open new avenues for analyzing similar matrix factorization problems. The computational efficiency and the quality of the learned dictionary of our algorithm are verified empirically on both synthetic and real datasets. In particular, on the tasks of topic learning, shadow removal and image denoising, our algorithm achieves superior trade-offs between the quality of learned dictionary and running time over the batch and other online NMF algorithms.
Tasks	Denoising, Image Denoising
Published	2016-07-30
URL	http://arxiv.org/abs/1608.00075v2
PDF	http://arxiv.org/pdf/1608.00075v2.pdf
PWC	https://paperswithcode.com/paper/online-nonnegative-matrix-factorization-with
Repo
Framework

Proposal of fault-tolerant tomographic image reconstruction


Title	Proposal of fault-tolerant tomographic image reconstruction
Authors	Hiroyuki Kudo, Keita Takaki, Fukashi Yamazaki, Takuya Nemoto
Abstract	This paper deals with tomographic image reconstruction under the situation where some of projection data bins are contaminated with abnormal data. Such situations occur in various instances of tomography. We propose a new reconstruction algorithm called the Fault-Tolerant reconstruction outlined as follows. The least-squares (L2-norm) error function Ax-b_2^2 used in ordinary iterative reconstructions is sensitive to the existence of abnormal data. The proposed algorithm utilizes the L1-norm error function Ax-b_1^1 instead of the L2-norm, and we develop a row-action-type iterative algorithm using the proximal splitting framework in convex optimization fields. We also propose an improved version of the L1-norm reconstruction called the L1-TV reconstruction, in which a weak Total Variation (TV) penalty is added to the cost function. Simulation results demonstrate that reconstructed images with the L2-norm were severely damaged by the effect of abnormal bins, whereas images with the L1-norm and L1-TV reconstructions were robust to the existence of abnormal bins.
Tasks	Image Reconstruction
Published	2016-09-20
URL	http://arxiv.org/abs/1609.06020v1
PDF	http://arxiv.org/pdf/1609.06020v1.pdf
PWC	https://paperswithcode.com/paper/proposal-of-fault-tolerant-tomographic-image
Repo
Framework

Automatic Bridge Bidding Using Deep Reinforcement Learning


Title	Automatic Bridge Bidding Using Deep Reinforcement Learning
Authors	Chih-Kuan Yeh, Hsuan-Tien Lin
Abstract	Bridge is among the zero-sum games for which artificial intelligence has not yet outperformed expert human players. The main difficulty lies in the bidding phase of bridge, which requires cooperative decision making under partial information. Existing artificial intelligence systems for bridge bidding rely on and are thus restricted by human-designed bidding systems or features. In this work, we propose a pioneering bridge bidding system without the aid of human domain knowledge. The system is based on a novel deep reinforcement learning model, which extracts sophisticated features and learns to bid automatically based on raw card data. The model includes an upper-confidence-bound algorithm and additional techniques to achieve a balance between exploration and exploitation. Our experiments validate the promising performance of our proposed model. In particular, the model advances from having no knowledge about bidding to achieving superior performance when compared with a champion-winning computer bridge program that implements a human-designed bidding system.
Tasks	Decision Making
Published	2016-07-12
URL	http://arxiv.org/abs/1607.03290v1
PDF	http://arxiv.org/pdf/1607.03290v1.pdf
PWC	https://paperswithcode.com/paper/automatic-bridge-bidding-using-deep
Repo
Framework

Domain Adaptation by Mixture of Alignments of Second- or Higher-Order Scatter Tensors


Title	Domain Adaptation by Mixture of Alignments of Second- or Higher-Order Scatter Tensors
Authors	Piotr Koniusz, Yusuf Tas, Fatih Porikli
Abstract	In this paper, we propose an approach to the domain adaptation, dubbed Second- or Higher-order Transfer of Knowledge (So-HoT), based on the mixture of alignments of second- or higher-order scatter statistics between the source and target domains. The human ability to learn from few labeled samples is a recurring motivation in the literature for domain adaptation. Towards this end, we investigate the supervised target scenario for which few labeled target training samples per category exist. Specifically, we utilize two CNN streams: the source and target networks fused at the classifier level. Features from the fully connected layers fc7 of each network are used to compute second- or even higher-order scatter tensors; one per network stream per class. As the source and target distributions are somewhat different despite being related, we align the scatters of the two network streams of the same class (within-class scatters) to a desired degree with our bespoke loss while maintaining good separation of the between-class scatters. We train the entire network in end-to-end fashion. We provide evaluations on the standard Office benchmark (visual domains), RGB-D combined with Caltech256 (depth-to-rgb transfer) and Pascal VOC2007 combined with the TU Berlin dataset (image-to-sketch transfer). We attain state-of-the-art results.
Tasks	Domain Adaptation
Published	2016-11-24
URL	http://arxiv.org/abs/1611.08195v2
PDF	http://arxiv.org/pdf/1611.08195v2.pdf
PWC	https://paperswithcode.com/paper/domain-adaptation-by-mixture-of-alignments-of
Repo
Framework

A Stochastic Large Deformation Model for Computational Anatomy


Title	A Stochastic Large Deformation Model for Computational Anatomy
Authors	Alexis Arnaudon, Darryl D. Holm, Akshay Pai, Stefan Sommer
Abstract	In the study of shapes of human organs using computational anatomy, variations are found to arise from inter-subject anatomical differences, disease-specific effects, and measurement noise. This paper introduces a stochastic model for incorporating random variations into the Large Deformation Diffeomorphic Metric Mapping (LDDMM) framework. By accounting for randomness in a particular setup which is crafted to fit the geometrical properties of LDDMM, we formulate the template estimation problem for landmarks with noise and give two methods for efficiently estimating the parameters of the noise fields from a prescribed data set. One method directly approximates the time evolution of the variance of each landmark by a finite set of differential equations, and the other is based on an Expectation-Maximisation algorithm. In the second method, the evaluation of the data likelihood is achieved without registering the landmarks, by applying bridge sampling using a stochastically perturbed version of the large deformation gradient flow algorithm. The method and the estimation algorithms are experimentally validated on synthetic examples and shape data of human corpora callosa.
Tasks
Published	2016-12-16
URL	http://arxiv.org/abs/1612.05323v1
PDF	http://arxiv.org/pdf/1612.05323v1.pdf
PWC	https://paperswithcode.com/paper/a-stochastic-large-deformation-model-for
Repo
Framework

Statistical limits of spiked tensor models


Title	Statistical limits of spiked tensor models
Authors	Amelia Perry, Alexander S. Wein, Afonso S. Bandeira
Abstract	We study the statistical limits of both detecting and estimating a rank-one deformation of a symmetric random Gaussian tensor. We establish upper and lower bounds on the critical signal-to-noise ratio, under a variety of priors for the planted vector: (i) a uniformly sampled unit vector, (ii) i.i.d. $\pm 1$ entries, and (iii) a sparse vector where a constant fraction $\rho$ of entries are i.i.d. $\pm 1$ and the rest are zero. For each of these cases, our upper and lower bounds match up to a $1+o(1)$ factor as the order $d$ of the tensor becomes large. For sparse signals (iii), our bounds are also asymptotically tight in the sparse limit $\rho \to 0$ for any fixed $d$ (including the $d=2$ case of sparse PCA). Our upper bounds for (i) demonstrate a phenomenon reminiscent of the work of Baik, Ben Arous and P'ech'e: an eigenvalue' of a perturbed tensor emerges from the bulk at a strictly lower signal-to-noise ratio than when the perturbation itself exceeds the bulk; we quantify the size of this effect. We also provide some general results for larger classes of priors. In particular, the large $d$ asymptotics of the threshold location differs between problems with discrete priors versus continuous priors. Finally, for priors (i) and (ii) we carry out the replica prediction from statistical physics, which is conjectured to give the exact information-theoretic threshold for any fixed $d$. Of independent interest, we introduce a new improvement to the second moment method for contiguity, on which our lower bounds are based. Our technique conditions away from rare bad’ events that depend on interactions between the signal and noise. This enables us to close $\sqrt{2}$-factor gaps present in several previous works.
Tasks
Published	2016-12-22
URL	http://arxiv.org/abs/1612.07728v2
PDF	http://arxiv.org/pdf/1612.07728v2.pdf
PWC	https://paperswithcode.com/paper/statistical-limits-of-spiked-tensor-models
Repo
Framework

Predictive Clinical Decision Support System with RNN Encoding and Tensor Decoding


Title	Predictive Clinical Decision Support System with RNN Encoding and Tensor Decoding
Authors	Yinchong Yang, Peter A. Fasching, Markus Wallwiener, Tanja N. Fehm, Sara Y. Brucker, Volker Tresp
Abstract	With the introduction of the Electric Health Records, large amounts of digital data become available for analysis and decision support. When physicians are prescribing treatments to a patient, they need to consider a large range of data variety and volume, making decisions increasingly complex. Machine learning based Clinical Decision Support systems can be a solution to the data challenges. In this work we focus on a class of decision support in which the physicians’ decision is directly predicted. Concretely, the model would assign higher probabilities to decisions that it presumes the physician are more likely to make. Thus the CDS system can provide physicians with rational recommendations. We also address the problem of correlation in target features: Often a physician is required to make multiple (sub-)decisions in a block, and that these decisions are mutually dependent. We propose a solution to the target correlation problem using a tensor factorization model. In order to handle the patients’ historical information as sequential data, we apply the so-called Encoder-Decoder-Framework which is based on Recurrent Neural Networks (RNN) as encoders and a tensor factorization model as a decoder, a combination which is novel in machine learning. With experiments with real-world datasets we show that the proposed model does achieve better prediction performances.
Tasks
Published	2016-12-02
URL	http://arxiv.org/abs/1612.00611v1
PDF	http://arxiv.org/pdf/1612.00611v1.pdf
PWC	https://paperswithcode.com/paper/predictive-clinical-decision-support-system
Repo
Framework

Simple Black-Box Adversarial Perturbations for Deep Networks


Title	Simple Black-Box Adversarial Perturbations for Deep Networks
Authors	Nina Narodytska, Shiva Prasad Kasiviswanathan
Abstract	Deep neural networks are powerful and popular learning models that achieve state-of-the-art pattern recognition performance on many computer vision, speech, and language processing tasks. However, these networks have also been shown susceptible to carefully crafted adversarial perturbations which force misclassification of the inputs. Adversarial examples enable adversaries to subvert the expected system behavior leading to undesired consequences and could pose a security risk when these systems are deployed in the real world. In this work, we focus on deep convolutional neural networks and demonstrate that adversaries can easily craft adversarial examples even without any internal knowledge of the target network. Our attacks treat the network as an oracle (black-box) and only assume that the output of the network can be observed on the probed inputs. Our first attack is based on a simple idea of adding perturbation to a randomly selected single pixel or a small set of them. We then improve the effectiveness of this attack by carefully constructing a small set of pixels to perturb by using the idea of greedy local-search. Our proposed attacks also naturally extend to a stronger notion of misclassification. Our extensive experimental results illustrate that even these elementary attacks can reveal a deep neural network’s vulnerabilities. The simplicity and effectiveness of our proposed schemes mean that they could serve as a litmus test for designing robust networks.
Tasks
Published	2016-12-19
URL	http://arxiv.org/abs/1612.06299v1
PDF	http://arxiv.org/pdf/1612.06299v1.pdf
PWC	https://paperswithcode.com/paper/simple-black-box-adversarial-perturbations
Repo
Framework