May 6, 2019

3121 words 15 mins read

Paper Group ANR 342

Encoding monotonic multi-set preferences using CI-nets: preliminary report. Low Latency Anomaly Detection and Bayesian Network Prediction of Anomaly Likelihood. Combining complex networks and data mining: why and how. A New Hierarchical Redundancy Eliminated Tree Augmented Naive Bayes Classifier for Coping with Gene Ontology-based Features. Distrib …

Encoding monotonic multi-set preferences using CI-nets: preliminary report


Title	Encoding monotonic multi-set preferences using CI-nets: preliminary report
Authors	Martin Diller, Anthony Hunter
Abstract	CP-nets and their variants constitute one of the main AI approaches for specifying and reasoning about preferences. CI-nets, in particular, are a CP-inspired formalism for representing ordinal preferences over sets of goods, which are typically required to be monotonic. Considering also that goods often come in multi-sets rather than sets, a natural question is whether CI-nets can be used more or less directly to encode preferences over multi-sets. We here provide some initial ideas on how to achieve this, in the sense that at least a restricted form of reasoning on our framework, which we call “confined reasoning”, can be efficiently reduced to reasoning on CI-nets. Our framework nevertheless allows for encoding preferences over multi-sets with unbounded multiplicities. We also show the extent to which it can be used to represent preferences where multiplicites of the goods are not stated explicitly (“purely qualitative preferences”) as well as a potential use of our generalization of CI-nets as a component of a recent system for evidence aggregation.
Tasks
Published	2016-11-09
URL	http://arxiv.org/abs/1611.02885v1
PDF	http://arxiv.org/pdf/1611.02885v1.pdf
PWC	https://paperswithcode.com/paper/encoding-monotonic-multi-set-preferences
Repo
Framework

Low Latency Anomaly Detection and Bayesian Network Prediction of Anomaly Likelihood


Title	Low Latency Anomaly Detection and Bayesian Network Prediction of Anomaly Likelihood
Authors	Derek Farren, Thai Pham, Marco Alban-Hidalgo
Abstract	We develop a supervised machine learning model that detects anomalies in systems in real time. Our model processes unbounded streams of data into time series which then form the basis of a low-latency anomaly detection model. Moreover, we extend our preliminary goal of just anomaly detection to simultaneous anomaly prediction. We approach this very challenging problem by developing a Bayesian Network framework that captures the information about the parameters of the lagged regressors calibrated in the first part of our approach and use this structure to learn local conditional probability distributions.
Tasks	Anomaly Detection, Time Series
Published	2016-11-11
URL	http://arxiv.org/abs/1611.03898v1
PDF	http://arxiv.org/pdf/1611.03898v1.pdf
PWC	https://paperswithcode.com/paper/low-latency-anomaly-detection-and-bayesian
Repo
Framework

Combining complex networks and data mining: why and how


Title	Combining complex networks and data mining: why and how
Authors	M. Zanin, D. Papo, P. A. Sousa, E. Menasalvas, A. Nicchi, E. Kubik, S. Boccaletti
Abstract	The increasing power of computer technology does not dispense with the need to extract meaningful in- formation out of data sets of ever growing size, and indeed typically exacerbates the complexity of this task. To tackle this general problem, two methods have emerged, at chronologically different times, that are now commonly used in the scientific community: data mining and complex network theory. Not only do complex network analysis and data mining share the same general goal, that of extracting information from complex systems to ultimately create a new compact quantifiable representation, but they also often address similar problems too. In the face of that, a surprisingly low number of researchers turn out to resort to both methodologies. One may then be tempted to conclude that these two fields are either largely redundant or totally antithetic. The starting point of this review is that this state of affairs should be put down to contingent rather than conceptual differences, and that these two fields can in fact advantageously be used in a synergistic manner. An overview of both fields is first provided, some fundamental concepts of which are illustrated. A variety of contexts in which complex network theory and data mining have been used in a synergistic manner are then presented. Contexts in which the appropriate integration of complex network metrics can lead to improved classification rates with respect to classical data mining algorithms and, conversely, contexts in which data mining can be used to tackle important issues in complex network theory applications are illustrated. Finally, ways to achieve a tighter integration between complex networks and data mining, and open lines of research are discussed.
Tasks
Published	2016-04-29
URL	https://arxiv.org/abs/1604.08816v2
PDF	https://arxiv.org/pdf/1604.08816v2.pdf
PWC	https://paperswithcode.com/paper/combining-complex-networks-and-data-mining
Repo
Framework

A New Hierarchical Redundancy Eliminated Tree Augmented Naive Bayes Classifier for Coping with Gene Ontology-based Features


Title	A New Hierarchical Redundancy Eliminated Tree Augmented Naive Bayes Classifier for Coping with Gene Ontology-based Features
Authors	Cen Wan, Alex A. Freitas
Abstract	The Tree Augmented Naive Bayes classifier is a type of probabilistic graphical model that can represent some feature dependencies. In this work, we propose a Hierarchical Redundancy Eliminated Tree Augmented Naive Bayes (HRE-TAN) algorithm, which considers removing the hierarchical redundancy during the classifier learning process, when coping with data containing hierarchically structured features. The experiments showed that HRE-TAN obtains significantly better predictive performance than the conventional Tree Augmented Naive Bayes classifier, and enhanced the robustness against imbalanced class distributions, in aging-related gene datasets with Gene Ontology terms used as features.
Tasks
Published	2016-07-06
URL	http://arxiv.org/abs/1607.01690v1
PDF	http://arxiv.org/pdf/1607.01690v1.pdf
PWC	https://paperswithcode.com/paper/a-new-hierarchical-redundancy-eliminated-tree
Repo
Framework

Distributed Clustering of Linear Bandits in Peer to Peer Networks


Title	Distributed Clustering of Linear Bandits in Peer to Peer Networks
Authors	Nathan Korda, Balazs Szorenyi, Shuai Li
Abstract	We provide two distributed confidence ball algorithms for solving linear bandit problems in peer to peer networks with limited communication capabilities. For the first, we assume that all the peers are solving the same linear bandit problem, and prove that our algorithm achieves the optimal asymptotic regret rate of any centralised algorithm that can instantly communicate information between the peers. For the second, we assume that there are clusters of peers solving the same bandit problem within each cluster, and we prove that our algorithm discovers these clusters, while achieving the optimal asymptotic regret rate within each one. Through experiments on several real-world datasets, we demonstrate the performance of proposed algorithms compared to the state-of-the-art.
Tasks
Published	2016-04-26
URL	http://arxiv.org/abs/1604.07706v3
PDF	http://arxiv.org/pdf/1604.07706v3.pdf
PWC	https://paperswithcode.com/paper/distributed-clustering-of-linear-bandits-in
Repo
Framework

Transferring Object-Scene Convolutional Neural Networks for Event Recognition in Still Images


Title	Transferring Object-Scene Convolutional Neural Networks for Event Recognition in Still Images
Authors	Limin Wang, Zhe Wang, Yu Qiao, Luc Van Gool
Abstract	Event recognition in still images is an intriguing problem and has potential for real applications. This paper addresses the problem of event recognition by proposing a convolutional neural network that exploits knowledge of objects and scenes for event classification (OS2E-CNN). Intuitively, it stands to reason that there exists a correlation among the concepts of objects, scenes, and events. We empirically demonstrate that the recognition of objects and scenes substantially contributes to the recognition of events. Meanwhile, we propose an iterative selection method to identify a subset of object and scene classes, which help to more efficiently and effectively transfer their deep representations to event recognition. Specifically, we develop three types of transferring techniques: (1) initialization-based transferring, (2) knowledge-based transferring, and (3) data-based transferring. These newly designed transferring techniques exploit multi-task learning frameworks to incorporate extra knowledge from other networks and additional datasets into the training procedure of event CNNs. These multi-task learning frameworks turn out to be effective in reducing the effect of over-fitting and improving the generalization ability of the learned CNNs. With OS2E-CNN, we design a multi-ratio and multi-scale cropping strategy, and propose an end-to-end event recognition pipeline. We perform experiments on three event recognition benchmarks: the ChaLearn Cultural Event Recognition dataset, the Web Image Dataset for Event Recognition (WIDER), and the UIUC Sports Event dataset. The experimental results show that our proposed algorithm successfully adapts object and scene representations towards the event dataset and that it achieves the current state-of-the-art performance on these challenging datasets.
Tasks	Multi-Task Learning
Published	2016-09-01
URL	http://arxiv.org/abs/1609.00162v1
PDF	http://arxiv.org/pdf/1609.00162v1.pdf
PWC	https://paperswithcode.com/paper/transferring-object-scene-convolutional
Repo
Framework

Identifying global optimality for dictionary learning


Title	Identifying global optimality for dictionary learning
Authors	Lei Le, Martha White
Abstract	Learning new representations of input observations in machine learning is often tackled using a factorization of the data. For many such problems, including sparse coding and matrix completion, learning these factorizations can be difficult, in terms of efficiency and to guarantee that the solution is a global minimum. Recently, a general class of objectives have been introduced-which we term induced dictionary learning models (DLMs)-that have an induced convex form that enables global optimization. Though attractive theoretically, this induced form is impractical, particularly for large or growing datasets. In this work, we investigate the use of practical alternating minimization algorithms for induced DLMs, that ensure convergence to global optima. We characterize the stationary points of these models, and, using these insights, highlight practical choices for the objectives. We then provide theoretical and empirical evidence that alternating minimization, from a random initialization, converges to global minima for a large subclass of induced DLMs. In particular, we take advantage of the existence of the (potentially unknown) convex induced form, to identify when stationary points are global minima for the dictionary learning objective. We then provide an empirical investigation into practical optimization choices for using alternating minimization for induced DLMs, for both batch and stochastic gradient descent.
Tasks	Dictionary Learning, Matrix Completion
Published	2016-04-17
URL	http://arxiv.org/abs/1604.04942v4
PDF	http://arxiv.org/pdf/1604.04942v4.pdf
PWC	https://paperswithcode.com/paper/identifying-global-optimality-for-dictionary
Repo
Framework

Dynamic Assortment Personalization in High Dimensions


Title	Dynamic Assortment Personalization in High Dimensions
Authors	Nathan Kallus, Madeleine Udell
Abstract	We study the problem of dynamic assortment personalization with large, heterogeneous populations and wide arrays of products, and demonstrate the importance of structural priors for effective, efficient large-scale personalization. Assortment personalization is the problem of choosing, for each individual (type), a best assortment of products, ads, or other offerings (items) so as to maximize revenue. This problem is central to revenue management in e-commerce and online advertising where both items and types can number in the millions. We formulate the dynamic assortment personalization problem as a discrete-contextual bandit with $m$ contexts (types) and exponentially many arms (assortments of the $n$ items). We assume that each type’s preferences follow a simple parametric model with $n$ parameters. In all, there are $mn$ parameters, and existing literature suggests that order optimal regret scales as $mn$. However, the data required to estimate so many parameters is orders of magnitude larger than the data available in most revenue management applications; and the optimal regret under these models is unacceptably high. In this paper, we impose a natural structure on the problem – a small latent dimension, or low rank. In the static setting, we show that this model can be efficiently learned from surprisingly few interactions, using a time- and memory-efficient optimization algorithm that converges globally whenever the model is learnable. In the dynamic setting, we show that structure-aware dynamic assortment personalization can have regret that is an order of magnitude smaller than structure-ignorant approaches. We validate our theoretical results empirically.
Tasks
Published	2016-10-18
URL	https://arxiv.org/abs/1610.05604v3
PDF	https://arxiv.org/pdf/1610.05604v3.pdf
PWC	https://paperswithcode.com/paper/dynamic-assortment-personalization-in-high
Repo
Framework

Learning To Score Olympic Events


Title	Learning To Score Olympic Events
Authors	Paritosh Parmar, Brendan Tran Morris
Abstract	Estimating action quality, the process of assigning a “score” to the execution of an action, is crucial in areas such as sports and health care. Unlike action recognition, which has millions of examples to learn from, the action quality datasets that are currently available are small – typically comprised of only a few hundred samples. This work presents three frameworks for evaluating Olympic sports which utilize spatiotemporal features learned using 3D convolutional neural networks (C3D) and perform score regression with i) SVR, ii) LSTM, and iii) LSTM followed by SVR. An efficient training mechanism for the limited data scenarios is presented for clip-based training with LSTM. The proposed systems show significant improvement over existing quality assessment approaches on the task of predicting scores of Olympic events {diving, vault, figure skating}. While the SVR-based frameworks yield better results, LSTM-based frameworks are more natural for describing an action and can be used for improvement feedback.
Tasks	Temporal Action Localization
Published	2016-11-16
URL	http://arxiv.org/abs/1611.05125v3
PDF	http://arxiv.org/pdf/1611.05125v3.pdf
PWC	https://paperswithcode.com/paper/learning-to-score-olympic-events
Repo
Framework

Constructive Preference Elicitation by Setwise Max-margin Learning


Title	Constructive Preference Elicitation by Setwise Max-margin Learning
Authors	Stefano Teso, Andrea Passerini, Paolo Viappiani
Abstract	In this paper we propose an approach to preference elicitation that is suitable to large configuration spaces beyond the reach of existing state-of-the-art approaches. Our setwise max-margin method can be viewed as a generalization of max-margin learning to sets, and can produce a set of “diverse” items that can be used to ask informative queries to the user. Moreover, the approach can encourage sparsity in the parameter space, in order to favor the assessment of utility towards combinations of weights that concentrate on just few features. We present a mixed integer linear programming formulation and show how our approach compares favourably with Bayesian preference elicitation alternatives and easily scales to realistic datasets.
Tasks
Published	2016-04-20
URL	http://arxiv.org/abs/1604.06020v1
PDF	http://arxiv.org/pdf/1604.06020v1.pdf
PWC	https://paperswithcode.com/paper/constructive-preference-elicitation-by
Repo
Framework

Robust Classification of Graph-Based Data


Title	Robust Classification of Graph-Based Data
Authors	Carlos M. Alaíz, Michaël Fanuel, Johan A. K. Suykens
Abstract	A graph-based classification method is proposed for semi-supervised learning in the case of Euclidean data and for classification in the case of graph data. Our manifold learning technique is based on a convex optimization problem involving a convex quadratic regularization term and a concave quadratic loss function with a trade-off parameter carefully chosen so that the objective function remains convex. As shown empirically, the advantage of considering a concave loss function is that the learning problem becomes more robust in the presence of noisy labels. Furthermore, the loss function considered here is then more similar to a classification loss while several other methods treat graph-based classification problems as regression problems.
Tasks
Published	2016-12-21
URL	http://arxiv.org/abs/1612.07141v3
PDF	http://arxiv.org/pdf/1612.07141v3.pdf
PWC	https://paperswithcode.com/paper/robust-classification-of-graph-based-data
Repo
Framework

Consistent Discretization and Minimization of the L1 Norm on Manifolds


Title	Consistent Discretization and Minimization of the L1 Norm on Manifolds
Authors	Alex Bronstein, Yoni Choukroun, Ron Kimmel, Matan Sela
Abstract	The L1 norm has been tremendously popular in signal and image processing in the past two decades due to its sparsity-promoting properties. More recently, its generalization to non-Euclidean domains has been found useful in shape analysis applications. For example, in conjunction with the minimization of the Dirichlet energy, it was shown to produce a compactly supported quasi-harmonic orthonormal basis, dubbed as compressed manifold modes. The continuous L1 norm on the manifold is often replaced by the vector l1 norm applied to sampled functions. We show that such an approach is incorrect in the sense that it does not consistently discretize the continuous norm and warn against its sensitivity to the specific sampling. We propose two alternative discretizations resulting in an iteratively-reweighed l2 norm. We demonstrate the proposed strategy on the compressed modes problem, which reduces to a sequence of simple eigendecomposition problems not requiring non-convex optimization on Stiefel manifolds and producing more stable and accurate results.
Tasks
Published	2016-09-18
URL	http://arxiv.org/abs/1609.05434v1
PDF	http://arxiv.org/pdf/1609.05434v1.pdf
PWC	https://paperswithcode.com/paper/consistent-discretization-and-minimization-of
Repo
Framework

Extensions and Limitations of the Neural GPU


Title	Extensions and Limitations of the Neural GPU
Authors	Eric Price, Wojciech Zaremba, Ilya Sutskever
Abstract	The Neural GPU is a recent model that can learn algorithms such as multi-digit binary addition and binary multiplication in a way that generalizes to inputs of arbitrary length. We show that there are two simple ways of improving the performance of the Neural GPU: by carefully designing a curriculum, and by increasing model size. The latter requires a memory efficient implementation, as a naive implementation of the Neural GPU is memory intensive. We find that these techniques increase the set of algorithmic problems that can be solved by the Neural GPU: we have been able to learn to perform all the arithmetic operations (and generalize to arbitrarily long numbers) when the arguments are given in the decimal representation (which, surprisingly, has not been possible before). We have also been able to train the Neural GPU to evaluate long arithmetic expressions with multiple operands that require respecting the precedence order of the operands, although these have succeeded only in their binary representation, and not with perfect accuracy. In addition, we gain insight into the Neural GPU by investigating its failure modes. We find that Neural GPUs that correctly generalize to arbitrarily long numbers still fail to compute the correct answer on highly-symmetric, atypical inputs: for example, a Neural GPU that achieves near-perfect generalization on decimal multiplication of up to 100-digit long numbers can fail on $000000\dots002 \times 000000\dots002$ while succeeding at $2 \times 2$. These failure modes are reminiscent of adversarial examples.
Tasks
Published	2016-11-02
URL	http://arxiv.org/abs/1611.00736v2
PDF	http://arxiv.org/pdf/1611.00736v2.pdf
PWC	https://paperswithcode.com/paper/extensions-and-limitations-of-the-neural-gpu
Repo
Framework

Quantifying the probable approximation error of probabilistic inference programs


Title	Quantifying the probable approximation error of probabilistic inference programs
Authors	Marco F Cusumano-Towner, Vikash K Mansinghka
Abstract	This paper introduces a new technique for quantifying the approximation error of a broad class of probabilistic inference programs, including ones based on both variational and Monte Carlo approaches. The key idea is to derive a subjective bound on the symmetrized KL divergence between the distribution achieved by an approximate inference program and its true target distribution. The bound’s validity (and subjectivity) rests on the accuracy of two auxiliary probabilistic programs: (i) a “reference” inference program that defines a gold standard of accuracy and (ii) a “meta-inference” program that answers the question “what internal random choices did the original approximate inference program probably make given that it produced a particular result?” The paper includes empirical results on inference problems drawn from linear regression, Dirichlet process mixture modeling, HMMs, and Bayesian networks. The experiments show that the technique is robust to the quality of the reference inference program and that it can detect implementation bugs that are not apparent from predictive performance.
Tasks
Published	2016-05-31
URL	http://arxiv.org/abs/1606.00068v1
PDF	http://arxiv.org/pdf/1606.00068v1.pdf
PWC	https://paperswithcode.com/paper/quantifying-the-probable-approximation-error
Repo
Framework

Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completion


Title	Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completion
Authors	Ming Yuan, Cun-Hui Zhang
Abstract	In this paper, we investigate the sample size requirement for a general class of nuclear norm minimization methods for higher order tensor completion. We introduce a class of tensor norms by allowing for different levels of coherence, which allows us to leverage the incoherence of a tensor. In particular, we show that a $k$th order tensor of rank $r$ and dimension $d\times\cdots\times d$ can be recovered perfectly from as few as $O((r^{(k-1)/2}d^{3/2}+r^{k-1}d)(\log(d))^2)$ uniformly sampled entries through an appropriate incoherent nuclear norm minimization. Our results demonstrate some key differences between completing a matrix and a higher order tensor: They not only point to potential room for improvement over the usual nuclear norm minimization but also highlight the importance of explicitly accounting for incoherence, when dealing with higher order tensors.
Tasks
Published	2016-06-10
URL	http://arxiv.org/abs/1606.03504v1
PDF	http://arxiv.org/pdf/1606.03504v1.pdf
PWC	https://paperswithcode.com/paper/incoherent-tensor-norms-and-their
Repo
Framework