May 6, 2019

2691 words 13 mins read

Paper Group ANR 408

Robust Learning of Fixed-Structure Bayesian Networks. Frankenstein: Learning Deep Face Representations using Small Data. Fast Cosine Transform to increase speed-up and efficiency of Karhunen-Loeve Transform for lossy image compression. INSIGHT-1 at SemEval-2016 Task 4: Convolutional Neural Networks for Sentiment Classification and Quantification. B …

Robust Learning of Fixed-Structure Bayesian Networks


Title	Robust Learning of Fixed-Structure Bayesian Networks
Authors	Yu Cheng, Ilias Diakonikolas, Daniel Kane, Alistair Stewart
Abstract	We investigate the problem of learning Bayesian networks in a robust model where an $\epsilon$-fraction of the samples are adversarially corrupted. In this work, we study the fully observable discrete case where the structure of the network is given. Even in this basic setting, previous learning algorithms either run in exponential time or lose dimension-dependent factors in their error guarantees. We provide the first computationally efficient robust learning algorithm for this problem with dimension-independent error guarantees. Our algorithm has near-optimal sample complexity, runs in polynomial time, and achieves error that scales nearly-linearly with the fraction of adversarially corrupted samples. Finally, we show on both synthetic and semi-synthetic data that our algorithm performs well in practice.
Tasks
Published	2016-06-23
URL	http://arxiv.org/abs/1606.07384v2
PDF	http://arxiv.org/pdf/1606.07384v2.pdf
PWC	https://paperswithcode.com/paper/robust-learning-of-fixed-structure-bayesian
Repo
Framework

Frankenstein: Learning Deep Face Representations using Small Data


Title	Frankenstein: Learning Deep Face Representations using Small Data
Authors	Guosheng Hu, Xiaojiang Peng, Yongxin Yang, Timothy Hospedales, Jakob Verbeek
Abstract	Deep convolutional neural networks have recently proven extremely effective for difficult face recognition problems in uncontrolled settings. To train such networks, very large training sets are needed with millions of labeled images. For some applications, such as near-infrared (NIR) face recognition, such large training datasets are not publicly available and difficult to collect. In this work, we propose a method to generate very large training datasets of synthetic images by compositing real face images in a given dataset. We show that this method enables to learn models from as few as 10,000 training images, which perform on par with models trained from 500,000 images. Using our approach we also obtain state-of-the-art results on the CASIA NIR-VIS2.0 heterogeneous face recognition dataset.
Tasks	Face Recognition, Heterogeneous Face Recognition
Published	2016-03-21
URL	http://arxiv.org/abs/1603.06470v3
PDF	http://arxiv.org/pdf/1603.06470v3.pdf
PWC	https://paperswithcode.com/paper/frankenstein-learning-deep-face
Repo
Framework

Fast Cosine Transform to increase speed-up and efficiency of Karhunen-Loeve Transform for lossy image compression


Title	Fast Cosine Transform to increase speed-up and efficiency of Karhunen-Loeve Transform for lossy image compression
Authors	Mario Mastriani, Juliana Gambini
Abstract	In this work, we present a comparison between two techniques of image compression. In the first case, the image is divided in blocks which are collected according to zig-zag scan. In the second one, we apply the Fast Cosine Transform to the image, and then the transformed image is divided in blocks which are collected according to zig-zag scan too. Later, in both cases, the Karhunen-Loeve transform is applied to mentioned blocks. On the other hand, we present three new metrics based on eigenvalues for a better comparative evaluation of the techniques. Simulations show that the combined version is the best, with minor Mean Absolute Error (MAE) and Mean Squared Error (MSE), higher Peak Signal to Noise Ratio (PSNR) and better image quality. Finally, new technique was far superior to JPEG and JPEG2000.
Tasks	Image Compression
Published	2016-07-11
URL	http://arxiv.org/abs/1607.03164v1
PDF	http://arxiv.org/pdf/1607.03164v1.pdf
PWC	https://paperswithcode.com/paper/fast-cosine-transform-to-increase-speed-up
Repo
Framework

INSIGHT-1 at SemEval-2016 Task 4: Convolutional Neural Networks for Sentiment Classification and Quantification


Title	INSIGHT-1 at SemEval-2016 Task 4: Convolutional Neural Networks for Sentiment Classification and Quantification
Authors	Sebastian Ruder, Parsa Ghaffari, John G. Breslin
Abstract	This paper describes our deep learning-based approach to sentiment analysis in Twitter as part of SemEval-2016 Task 4. We use a convolutional neural network to determine sentiment and participate in all subtasks, i.e. two-point, three-point, and five-point scale sentiment classification and two-point and five-point scale sentiment quantification. We achieve competitive results for two-point scale sentiment classification and quantification, ranking fifth and a close fourth (third and second by alternative metrics) respectively despite using only pre-trained embeddings that contain no sentiment information. We achieve good performance on three-point scale sentiment classification, ranking eighth out of 35, while performing poorly on five-point scale sentiment classification and quantification. An error analysis reveals that this is due to low expressiveness of the model to capture negative sentiment as well as an inability to take into account ordinal information. We propose improvements in order to address these and other issues.
Tasks	Sentiment Analysis
Published	2016-09-09
URL	http://arxiv.org/abs/1609.02746v1
PDF	http://arxiv.org/pdf/1609.02746v1.pdf
PWC	https://paperswithcode.com/paper/insight-1-at-semeval-2016-task-4
Repo
Framework

Bottom-up Instance Segmentation using Deep Higher-Order CRFs


Title	Bottom-up Instance Segmentation using Deep Higher-Order CRFs
Authors	Anurag Arnab, Philip H. S. Torr
Abstract	Traditional Scene Understanding problems such as Object Detection and Semantic Segmentation have made breakthroughs in recent years due to the adoption of deep learning. However, the former task is not able to localise objects at a pixel level, and the latter task has no notion of different instances of objects of the same class. We focus on the task of Instance Segmentation which recognises and localises objects down to a pixel level. Our model is based on a deep neural network trained for semantic segmentation. This network incorporates a Conditional Random Field with end-to-end trainable higher order potentials based on object detector outputs. This allows us to reason about instances from an initial, category-level semantic segmentation. Our simple method effectively leverages the great progress recently made in semantic segmentation and object detection. The accurate instance-level segmentations that our network produces is reflected by the considerable improvements obtained over previous work.
Tasks	Instance Segmentation, Object Detection, Scene Understanding, Semantic Segmentation
Published	2016-09-08
URL	http://arxiv.org/abs/1609.02583v1
PDF	http://arxiv.org/pdf/1609.02583v1.pdf
PWC	https://paperswithcode.com/paper/bottom-up-instance-segmentation-using-deep
Repo
Framework

Multiplierless 16-point DCT Approximation for Low-complexity Image and Video Coding


Title	Multiplierless 16-point DCT Approximation for Low-complexity Image and Video Coding
Authors	T. L. T. Silveira, R. S. Oliveira, F. M. Bayer, R. J. Cintra, A. Madanayake
Abstract	An orthogonal 16-point approximate discrete cosine transform (DCT) is introduced. The proposed transform requires neither multiplications nor bit-shifting operations. A fast algorithm based on matrix factorization is introduced, requiring only 44 additions—the lowest arithmetic cost in literature. To assess the introduced transform, computational complexity, similarity with the exact DCT, and coding performance measures are computed. Classical and state-of-the-art 16-point low-complexity transforms were used in a comparative analysis. In the context of image compression, the proposed approximation was evaluated via PSNR and SSIM measurements, attaining the best cost-benefit ratio among the competitors. For video encoding, the proposed approximation was embedded into a HEVC reference software for direct comparison with the original HEVC standard. Physically realized and tested using FPGA hardware, the proposed transform showed 35% and 37% improvements of area-time and area-time-squared VLSI metrics when compared to the best competing transform in the literature.
Tasks	Image Compression
Published	2016-06-23
URL	http://arxiv.org/abs/1606.07414v1
PDF	http://arxiv.org/pdf/1606.07414v1.pdf
PWC	https://paperswithcode.com/paper/multiplierless-16-point-dct-approximation-for
Repo
Framework

Conformalized density- and distance-based anomaly detection in time-series data


Title	Conformalized density- and distance-based anomaly detection in time-series data
Authors	Evgeny Burnaev, Vladislav Ishimtsev
Abstract	Anomalies (unusual patterns) in time-series data give essential, and often actionable information in critical situations. Examples can be found in such fields as healthcare, intrusion detection, finance, security and flight safety. In this paper we propose new conformalized density- and distance-based anomaly detection algorithms for a one-dimensional time-series data. The algorithms use a combination of a feature extraction method, an approach to assess a score whether a new observation differs significantly from a previously observed data, and a probabilistic interpretation of this score based on the conformal paradigm.
Tasks	Anomaly Detection, Intrusion Detection, Time Series
Published	2016-08-16
URL	http://arxiv.org/abs/1608.04585v1
PDF	http://arxiv.org/pdf/1608.04585v1.pdf
PWC	https://paperswithcode.com/paper/conformalized-density-and-distance-based
Repo
Framework

Anomaly detection and classification for streaming data using PDEs


Title	Anomaly detection and classification for streaming data using PDEs
Authors	Bilal Abbasi, Jeff Calder, Adam M. Oberman
Abstract	Nondominated sorting, also called Pareto Depth Analysis (PDA), is widely used in multi-objective optimization and has recently found important applications in multi-criteria anomaly detection. Recently, a partial differential equation (PDE) continuum limit was discovered for nondominated sorting leading to a very fast approximate sorting algorithm called PDE-based ranking. We propose in this paper a fast real-time streaming version of the PDA algorithm for anomaly detection that exploits the computational advantages of PDE continuum limits. Furthermore, we derive new PDE continuum limits for sorting points within their nondominated layers and show how the new PDEs can be used to classify anomalies based on which criterion was more significantly violated. We also prove statistical convergence rates for PDE-based ranking, and present the results of numerical experiments with both synthetic and real data.
Tasks	Anomaly Detection
Published	2016-08-15
URL	http://arxiv.org/abs/1608.04348v2
PDF	http://arxiv.org/pdf/1608.04348v2.pdf
PWC	https://paperswithcode.com/paper/anomaly-detection-and-classification-for
Repo
Framework

Learning Local Dependence In Ordered Data


Title	Learning Local Dependence In Ordered Data
Authors	Guo Yu, Jacob Bien
Abstract	In many applications, data come with a natural ordering. This ordering can often induce local dependence among nearby variables. However, in complex data, the width of this dependence may vary, making simple assumptions such as a constant neighborhood size unrealistic. We propose a framework for learning this local dependence based on estimating the inverse of the Cholesky factor of the covariance matrix. Penalized maximum likelihood estimation of this matrix yields a simple regression interpretation for local dependence in which variables are predicted by their neighbors. Our proposed method involves solving a convex, penalized Gaussian likelihood problem with a hierarchical group lasso penalty. The problem decomposes into independent subproblems which can be solved efficiently in parallel using first-order methods. Our method yields a sparse, symmetric, positive definite estimator of the precision matrix, encoding a Gaussian graphical model. We derive theoretical results not found in existing methods attaining this structure. In particular, our conditions for signed support recovery and estimation consistency rates in multiple norms are as mild as those in a regression problem. Empirical results show our method performing favorably compared to existing methods. We apply our method to genomic data to flexibly model linkage disequilibrium. Our method is also applied to improve the performance of discriminant analysis in sound recording classification.
Tasks
Published	2016-04-25
URL	http://arxiv.org/abs/1604.07451v3
PDF	http://arxiv.org/pdf/1604.07451v3.pdf
PWC	https://paperswithcode.com/paper/learning-local-dependence-in-ordered-data
Repo
Framework


Title	RedQueen: An Online Algorithm for Smart Broadcasting in Social Networks
Authors	Ali Zarezade, Utkarsh Upadhyay, Hamid Rabiee, Manuel Gomez Rodriguez
Abstract	Users in social networks whose posts stay at the top of their followers’{} feeds the longest time are more likely to be noticed. Can we design an online algorithm to help them decide when to post to stay at the top? In this paper, we address this question as a novel optimal control problem for jump stochastic differential equations. For a wide variety of feed dynamics, we show that the optimal broadcasting intensity for any user is surprisingly simple – it is given by the position of her most recent post on each of her follower’s feeds. As a consequence, we are able to develop a simple and highly efficient online algorithm, RedQueen, to sample the optimal times for the user to post. Experiments on both synthetic and real data gathered from Twitter show that our algorithm is able to consistently make a user’s posts more visible over time, is robust to volume changes on her followers’ feeds, and significantly outperforms the state of the art.
Tasks
Published	2016-10-18
URL	http://arxiv.org/abs/1610.05773v1
PDF	http://arxiv.org/pdf/1610.05773v1.pdf
PWC	https://paperswithcode.com/paper/redqueen-an-online-algorithm-for-smart
Repo
Framework

Clustering Financial Time Series: How Long is Enough?


Title	Clustering Financial Time Series: How Long is Enough?
Authors	Gautier Marti, Sébastien Andler, Frank Nielsen, Philippe Donnat
Abstract	Researchers have used from 30 days to several years of daily returns as source data for clustering financial time series based on their correlations. This paper sets up a statistical framework to study the validity of such practices. We first show that clustering correlated random variables from their observed values is statistically consistent. Then, we also give a first empirical answer to the much debated question: How long should the time series be? If too short, the clusters found can be spurious; if too long, dynamics can be smoothed out.
Tasks	Time Series
Published	2016-03-13
URL	http://arxiv.org/abs/1603.04017v2
PDF	http://arxiv.org/pdf/1603.04017v2.pdf
PWC	https://paperswithcode.com/paper/clustering-financial-time-series-how-long-is
Repo
Framework

Wayfinding and cognitive maps for pedestrian models


Title	Wayfinding and cognitive maps for pedestrian models
Authors	Erik Andresen, David Haensel, Mohcine Chraibi, Armin Seyfried
Abstract	Usually, routing models in pedestrian dynamics assume that agents have fulfilled and global knowledge about the building’s structure. However, they neglect the fact that pedestrians possess no or only parts of information about their position relative to final exits and possible routes leading to them. To get a more realistic description we introduce the systematics of gathering and using spatial knowledge. A new wayfinding model for pedestrian dynamics is proposed. The model defines for every pedestrian an individual knowledge representation implying inaccuracies and uncertainties. In addition, knowledge-driven search strategies are introduced. The presented concept is tested on a fictive example scenario.
Tasks
Published	2016-02-05
URL	http://arxiv.org/abs/1602.01971v1
PDF	http://arxiv.org/pdf/1602.01971v1.pdf
PWC	https://paperswithcode.com/paper/wayfinding-and-cognitive-maps-for-pedestrian
Repo
Framework

Contextual Visual Similarity


Title	Contextual Visual Similarity
Authors	Xiaofang Wang, Kris M. Kitani, Martial Hebert
Abstract	Measuring visual similarity is critical for image understanding. But what makes two images similar? Most existing work on visual similarity assumes that images are similar because they contain the same object instance or category. However, the reason why images are similar is much more complex. For example, from the perspective of category, a black dog image is similar to a white dog image. However, in terms of color, a black dog image is more similar to a black horse image than the white dog image. This example serves to illustrate that visual similarity is ambiguous but can be made precise when given an explicit contextual perspective. Based on this observation, we propose the concept of contextual visual similarity. To be concrete, we examine the concept of contextual visual similarity in the application domain of image search. Instead of providing only a single image for image similarity search (\eg, Google image search), we require three images. Given a query image, a second positive image and a third negative image, dissimilar to the first two images, we define a contextualized similarity search criteria. In particular, we learn feature weights over all the feature dimensions of each image such that the distance between the query image and the positive image is small and their distances to the negative image are large after reweighting their features. The learned feature weights encode the contextualized visual similarity specified by the user and can be used for attribute specific image search. We also show the usefulness of our contextualized similarity weighting scheme for different tasks, such as answering visual analogy questions and unsupervised attribute discovery.
Tasks	Image Retrieval, Image Similarity Search
Published	2016-12-08
URL	http://arxiv.org/abs/1612.02534v1
PDF	http://arxiv.org/pdf/1612.02534v1.pdf
PWC	https://paperswithcode.com/paper/contextual-visual-similarity
Repo
Framework

Interpolated Discretized Embedding of Single Vectors and Vector Pairs for Classification, Metric Learning and Distance Approximation


Title	Interpolated Discretized Embedding of Single Vectors and Vector Pairs for Classification, Metric Learning and Distance Approximation
Authors	Ofir Pele, Yakir Ben-Aliz
Abstract	We propose a new embedding method for a single vector and for a pair of vectors. This embedding method enables: a) efficient classification and regression of functions of single vectors; b) efficient approximation of distance functions; and c) non-Euclidean, semimetric learning. To the best of our knowledge, this is the first work that enables learning any general, non-Euclidean, semimetrics. That is, our method is a universal semimetric learning and approximation method that can approximate any distance function with as high accuracy as needed with or without semimetric constraints. The project homepage including code is at: http://www.ariel.ac.il/sites/ofirpele/ID
Tasks	Metric Learning
Published	2016-08-08
URL	http://arxiv.org/abs/1608.02484v1
PDF	http://arxiv.org/pdf/1608.02484v1.pdf
PWC	https://paperswithcode.com/paper/interpolated-discretized-embedding-of-single
Repo
Framework

On a convergent off -policy temporal difference learning algorithm in on-line learning environment


Title	On a convergent off -policy temporal difference learning algorithm in on-line learning environment
Authors	Prasenjit Karmakar, Rajkumar Maity, Shalabh Bhatnagar
Abstract	In this paper we provide a rigorous convergence analysis of a “off”-policy temporal difference learning algorithm with linear function approximation and per time-step linear computational complexity in “online” learning environment. The algorithm considered here is TDC with importance weighting introduced by Maei et al. We support our theoretical results by providing suitable empirical results for standard off-policy counterexamples.
Tasks
Published	2016-05-19
URL	http://arxiv.org/abs/1605.06076v1
PDF	http://arxiv.org/pdf/1605.06076v1.pdf
PWC	https://paperswithcode.com/paper/on-a-convergent-off-policy-temporal
Repo
Framework