May 7, 2019

3177 words 15 mins read

Paper Group ANR 55

Algorithms for Learning Sparse Additive Models with Interactions in High Dimensions. Generalization of metric classification algorithms for sequences classification and labelling. CNN for License Plate Motion Deblurring. Learning Dynamic Classes of Events using Stacked Multilayer Perceptron Networks. PCA Method for Automated Detection of Mispronoun …

Algorithms for Learning Sparse Additive Models with Interactions in High Dimensions


Title	Algorithms for Learning Sparse Additive Models with Interactions in High Dimensions
Authors	Hemant Tyagi, Anastasios Kyrillidis, Bernd Gärtner, Andreas Krause
Abstract	A function $f: \mathbb{R}^d \rightarrow \mathbb{R}$ is a Sparse Additive Model (SPAM), if it is of the form $f(\mathbf{x}) = \sum_{l \in \mathcal{S}}\phi_{l}(x_l)$ where $\mathcal{S} \subset [d]$, $\mathcal{S} \ll d$. Assuming $\phi$'s, $\mathcal{S}$ to be unknown, there exists extensive work for estimating $f$ from its samples. In this work, we consider a generalized version of SPAMs, that also allows for the presence of a sparse number of second order interaction terms. For some $\mathcal{S}_1 \subset [d], \mathcal{S}_2 \subset {[d] \choose 2}$, with $\mathcal{S}_1 \ll d, \mathcal{S}_2 \ll d^2$, the function $f$ is now assumed to be of the form: $\sum_{p \in \mathcal{S}_1}\phi_{p} (x_p) + \sum_{(l,l^{\prime}) \in \mathcal{S}_2}\phi_{(l,l^{\prime})} (x_l,x_{l^{\prime}})$. Assuming we have the freedom to query $f$ anywhere in its domain, we derive efficient algorithms that provably recover $\mathcal{S}_1,\mathcal{S}_2$ with finite sample bounds. Our analysis covers the noiseless setting where exact samples of $f$ are obtained, and also extends to the noisy setting where the queries are corrupted with noise. For the noisy setting in particular, we consider two noise models namely: i.i.d Gaussian noise and arbitrary but bounded noise. Our main methods for identification of $\mathcal{S}_2$ essentially rely on estimation of sparse Hessian matrices, for which we provide two novel compressed sensing based schemes. Once $\mathcal{S}_1, \mathcal{S}_2$ are known, we show how the individual components $\phi_p$, $\phi_{(l,l^{\prime})}$ can be estimated via additional queries of $f$, with uniform error bounds. Lastly, we provide simulation results on synthetic data that validate our theoretical findings.
Tasks
Published	2016-05-02
URL	http://arxiv.org/abs/1605.00609v3
PDF	http://arxiv.org/pdf/1605.00609v3.pdf
PWC	https://paperswithcode.com/paper/algorithms-for-learning-sparse-additive
Repo
Framework

Generalization of metric classification algorithms for sequences classification and labelling


Title	Generalization of metric classification algorithms for sequences classification and labelling
Authors	Roman Samarev, Andrey Vasnetsov, Elizaveta Smelkova
Abstract	The article deals with the issue of modification of metric classification algorithms. In particular, it studies the algorithm k-Nearest Neighbours for its application to sequential data. A method of generalization of metric classification algorithms is proposed. As a part of it, there has been developed an algorithm for solving the problem of classification and labelling of sequential data. The advantages of the developed algorithm of classification in comparison with the existing one are also discussed in the article. There is a comparison of the effectiveness of the proposed algorithm with the algorithm of CRF in the task of chunking in the open data set CoNLL2000.
Tasks	Chunking
Published	2016-10-15
URL	http://arxiv.org/abs/1610.04718v2
PDF	http://arxiv.org/pdf/1610.04718v2.pdf
PWC	https://paperswithcode.com/paper/generalization-of-metric-classification
Repo
Framework

CNN for License Plate Motion Deblurring


Title	CNN for License Plate Motion Deblurring
Authors	Pavel Svoboda, Michal Hradis, Lukas Marsik, Pavel Zemcik
Abstract	In this work we explore the previously proposed approach of direct blind deconvolution and denoising with convolutional neural networks in a situation where the blur kernels are partially constrained. We focus on blurred images from a real-life traffic surveillance system, on which we, for the first time, demonstrate that neural networks trained on artificial data provide superior reconstruction quality on real images compared to traditional blind deconvolution methods. The training data is easy to obtain by blurring sharp photos from a target system with a very rough approximation of the expected blur kernels, thereby allowing custom CNNs to be trained for a specific application (image content and blur range). Additionally, we evaluate the behavior and limits of the CNNs with respect to blur direction range and length.
Tasks	Deblurring, Denoising
Published	2016-02-25
URL	http://arxiv.org/abs/1602.07873v1
PDF	http://arxiv.org/pdf/1602.07873v1.pdf
PWC	https://paperswithcode.com/paper/cnn-for-license-plate-motion-deblurring
Repo
Framework

Learning Dynamic Classes of Events using Stacked Multilayer Perceptron Networks


Title	Learning Dynamic Classes of Events using Stacked Multilayer Perceptron Networks
Authors	Nattiya Kanhabua, Huamin Ren, Thomas B. Moeslund
Abstract	People often use a web search engine to find information about events of interest, for example, sport competitions, political elections, festivals and entertainment news. In this paper, we study a problem of detecting event-related queries, which is the first step before selecting a suitable time-aware retrieval model. In general, event-related information needs can be observed in query streams through various temporal patterns of user search behavior, e.g., spiky peaks for popular events, and periodicities for repetitive events. However, it is also common that users search for non-popular events, which may not exhibit temporal variations in query streams, e.g., past events recently occurred, historical events triggered by anniversaries or similar events, and future events anticipated to happen. To address the challenge of detecting dynamic classes of events, we propose a novel deep learning model to classify a given query into a predetermined set of multiple event types. Our proposed model, a Stacked Multilayer Perceptron (S-MLP) network, consists of multilayer perceptron used as a basic learning unit. We assemble stacked units to further learn complex relationships between neutrons in successive layers. To evaluate our proposed model, we conduct experiments using real-world queries and a set of manually created ground truth. Preliminary results have shown that our proposed deep learning model outperforms the state-of-the-art classification models significantly.
Tasks
Published	2016-06-23
URL	http://arxiv.org/abs/1606.07219v2
PDF	http://arxiv.org/pdf/1606.07219v2.pdf
PWC	https://paperswithcode.com/paper/learning-dynamic-classes-of-events-using
Repo
Framework

PCA Method for Automated Detection of Mispronounced Words


Title	PCA Method for Automated Detection of Mispronounced Words
Authors	Zhenhao Ge, Sudhendu R. Sharma, Mark J. T. Smith
Abstract	This paper presents a method for detecting mispronunciations with the aim of improving Computer Assisted Language Learning (CALL) tools used by foreign language learners. The algorithm is based on Principle Component Analysis (PCA). It is hierarchical with each successive step refining the estimate to classify the test word as being either mispronounced or correct. Preprocessing before detection, like normalization and time-scale modification, is implemented to guarantee uniformity of the feature vectors input to the detection system. The performance using various features including spectrograms and Mel-Frequency Cepstral Coefficients (MFCCs) are compared and evaluated. Best results were obtained using MFCCs, achieving up to 99% accuracy in word verification and 93% in native/non-native classification. Compared with Hidden Markov Models (HMMs) which are used pervasively in recognition application, this particular approach is computational efficient and effective when training data is limited.
Tasks
Published	2016-02-25
URL	http://arxiv.org/abs/1602.08128v1
PDF	http://arxiv.org/pdf/1602.08128v1.pdf
PWC	https://paperswithcode.com/paper/pca-method-for-automated-detection-of
Repo
Framework

Evolutionary forces in language change


Title	Evolutionary forces in language change
Authors	Christopher A. Ahern, Mitchell G. Newberry, Robin Clark, Joshua B. Plotkin
Abstract	Languages and genes are both transmitted from generation to generation, with opportunity for differential reproduction and survivorship of forms. Here we apply a rigorous inference framework, drawn from population genetics, to distinguish between two broad mechanisms of language change: drift and selection. Drift is change that results from stochasticity in transmission and it may occur in the absence of any intrinsic difference between linguistic forms; whereas selection is truly an evolutionary force arising from intrinsic differences – for example, when one form is preferred by members of the population. Using large corpora of parsed texts spanning the 12th century to the 21st century, we analyze three examples of grammatical changes in English: the regularization of past-tense verbs, the rise of the periphrastic `do’, and syntactic variation in verbal negation. We show that we can reject stochastic drift in favor of a selective force driving some of these language changes, but not others. The strength of drift depends on a word’s frequency, and so drift provides an alternative explanation for why some words are more prone to change than others. Our results suggest an important role for stochasticity in language change, and they provide a null model against which selective theories of language evolution must be compared. \|
Tasks
Published	2016-08-02
URL	http://arxiv.org/abs/1608.00938v1
PDF	http://arxiv.org/pdf/1608.00938v1.pdf
PWC	https://paperswithcode.com/paper/evolutionary-forces-in-language-change
Repo
Framework

Generalized Online Transfer Learning for Climate Control in Residential Buildings


Title	Generalized Online Transfer Learning for Climate Control in Residential Buildings
Authors	Thomas Grubinger, Georgios Chasparis, Thomas Natschlaeger
Abstract	This paper presents an online transfer learning framework for improving temperature predictions in residential buildings. In transfer learning, prediction models trained under a set of available data from a target domain (e.g., house with limited data) can be improved through the use of data generated from similar source domains (e.g., houses with rich data). Given also the need for prediction models that can be trained online (e.g., as part of a model-predictive-control implementation), this paper introduces the generalized online transfer learning algorithm (GOTL). It employs a weighted combination of the available predictors (i.e., the target and source predictors) and guarantees convergence to the best weighted predictor. Furthermore, the use of Transfer Component Analysis (TCA) allows for using more than a single source domains, since it may facilitate the fit of a single model on more than one source domains (houses). This allows GOTL to transfer knowledge from more than one source domains. We further validate our results through experiments in climate control for residential buildings and show that GOTL may lead to non-negligible energy savings for given comfort levels.
Tasks	Transfer Learning
Published	2016-10-13
URL	http://arxiv.org/abs/1610.04042v1
PDF	http://arxiv.org/pdf/1610.04042v1.pdf
PWC	https://paperswithcode.com/paper/generalized-online-transfer-learning-for
Repo
Framework

An Attention-Driven Approach of No-Reference Image Quality Assessment


Title	An Attention-Driven Approach of No-Reference Image Quality Assessment
Authors	Diqi Chen, Yizhou Wang, Tianfu Wu, Wen Gao
Abstract	In this paper, we present a novel method of no-reference image quality assessment (NR-IQA), which is to predict the perceptual quality score of a given image without using any reference image. The proposed method harnesses three functions (i) the visual attention mechanism, which affects many aspects of visual perception including image quality assessment, however, is overlooked in the NR-IQA literature. The method assumes that the fixation areas on an image contain key information to the process of IQA. (ii) the robust averaging strategy, which is a means -– supported by psychology studies -– to integrating multiple/step-wise evidence to make a final perceptual judgment. (iii) the multi-task learning, which is believed to be an effectual means to shape representation learning and could result in a more generalized model. To exploit the synergy of the three, we consider the NR-IQA as a dynamic perception process, in which the model samples a sequence of “informative” areas and aggregates the information to learn a representation for the tasks of jointly predicting the image quality score and the distortion type. The model learning is implemented by a reinforcement strategy, in which the rewards of both tasks guide the learning of the optimal sampling policy to acquire the “task-informative” image regions so that the predictions can be made accurately and efficiently (in terms of the sampling steps). The reinforcement learning is realized by a deep network with the policy gradient method and trained through back-propagation. In experiments, the model is tested on the TID2008 dataset and it outperforms several state-of-the-art methods. Furthermore, the model is very efficient in the sense that a small number of fixations are used in NR-IQA.
Tasks	Image Quality Assessment, Multi-Task Learning, No-Reference Image Quality Assessment, Representation Learning
Published	2016-12-12
URL	http://arxiv.org/abs/1612.03530v3
PDF	http://arxiv.org/pdf/1612.03530v3.pdf
PWC	https://paperswithcode.com/paper/an-attention-driven-approach-of-no-reference
Repo
Framework

Supervised Learning for Optimal Power Flow as a Real-Time Proxy


Title	Supervised Learning for Optimal Power Flow as a Real-Time Proxy
Authors	Raphael Canyasse, Gal Dalal, Shie Mannor
Abstract	In this work we design and compare different supervised learning algorithms to compute the cost of Alternating Current Optimal Power Flow (ACOPF). The motivation for quick calculation of OPF cost outcomes stems from the growing need of algorithmic-based long-term and medium-term planning methodologies in power networks. Integrated in a multiple time-horizon coordination framework, we refer to this approximation module as a proxy for predicting short-term decision outcomes without the need of actual simulation and optimization of them. Our method enables fast approximate calculation of OPF cost with less than 1% error on average, achieved in run-times that are several orders of magnitude lower than of exact computation. Several test-cases such as IEEE-RTS96 are used to demonstrate the efficiency of our approach.
Tasks
Published	2016-12-20
URL	http://arxiv.org/abs/1612.06623v1
PDF	http://arxiv.org/pdf/1612.06623v1.pdf
PWC	https://paperswithcode.com/paper/supervised-learning-for-optimal-power-flow-as
Repo
Framework

Expectation Propagation performs a smoothed gradient descent


Title	Expectation Propagation performs a smoothed gradient descent
Authors	Guillaume P. Dehaene
Abstract	Bayesian inference is a popular method to build learning algorithms but it is hampered by the fact that its key object, the posterior probability distribution, is often uncomputable. Expectation Propagation (EP) (Minka (2001)) is a popular algorithm that solves this issue by computing a parametric approximation (e.g: Gaussian) to the density of the posterior. However, while it is known empirically to quickly compute fine approximations, EP is extremely poorly understood which prevents it from being adopted by a larger fraction of the community. The object of the present article is to shed intuitive light on EP, by relating it to other better understood methods. More precisely, we link it to using gradient descent to compute the Laplace approximation of a target probability distribution. We show that EP is exactly equivalent to performing gradient descent on a smoothed energy landscape: i.e: the original energy landscape convoluted with some smoothing kernel. This also relates EP to algorithms that compute the Gaussian approximation which minimizes the reverse KL divergence to the target distribution, a link that has been conjectured before but has not been proved rigorously yet. These results can help practitioners to get a better feel for how EP works, as well as lead to other new results on this important method.
Tasks	Bayesian Inference
Published	2016-12-15
URL	http://arxiv.org/abs/1612.05053v1
PDF	http://arxiv.org/pdf/1612.05053v1.pdf
PWC	https://paperswithcode.com/paper/expectation-propagation-performs-a-smoothed
Repo
Framework

On the entropy numbers of the mixed smoothness function classes


Title	On the entropy numbers of the mixed smoothness function classes
Authors	V. Temlyakov
Abstract	Behavior of the entropy numbers of classes of multivariate functions with mixed smoothness is studied here. This problem has a long history and some fundamental problems in the area are still open. The main goal of this paper is to develop a new method of proving the upper bounds for the entropy numbers. This method is based on recent developments of nonlinear approximation, in particular, on greedy approximation. This method consists of the following two steps strategy. At the first step we obtain bounds of the best m-term approximations with respect to a dictionary. At the second step we use general inequalities relating the entropy numbers to the best m-term approximations. For the lower bounds we use the volume estimates method, which is a well known powerful method for proving the lower bounds for the entropy numbers. It was used in a number of previous papers.
Tasks
Published	2016-02-28
URL	http://arxiv.org/abs/1602.08712v1
PDF	http://arxiv.org/pdf/1602.08712v1.pdf
PWC	https://paperswithcode.com/paper/on-the-entropy-numbers-of-the-mixed
Repo
Framework

Distributed Learning with Infinitely Many Hypotheses


Title	Distributed Learning with Infinitely Many Hypotheses
Authors	Angelia Nedić, Alex Olshevsky, César Uribe
Abstract	We consider a distributed learning setup where a network of agents sequentially access realizations of a set of random variables with unknown distributions. The network objective is to find a parametrized distribution that best describes their joint observations in the sense of the Kullback-Leibler divergence. Apart from recent efforts in the literature, we analyze the case of countably many hypotheses and the case of a continuum of hypotheses. We provide non-asymptotic bounds for the concentration rate of the agents’ beliefs around the correct hypothesis in terms of the number of agents, the network parameters, and the learning abilities of the agents. Additionally, we provide a novel motivation for a general set of distributed Non-Bayesian update rules as instances of the distributed stochastic mirror descent algorithm.
Tasks
Published	2016-05-06
URL	http://arxiv.org/abs/1605.02105v1
PDF	http://arxiv.org/pdf/1605.02105v1.pdf
PWC	https://paperswithcode.com/paper/distributed-learning-with-infinitely-many
Repo
Framework

Sherlock: Sparse Hierarchical Embeddings for Visually-aware One-class Collaborative Filtering


Title	Sherlock: Sparse Hierarchical Embeddings for Visually-aware One-class Collaborative Filtering
Authors	Ruining He, Chunbin Lin, Jianguo Wang, Julian McAuley
Abstract	Building successful recommender systems requires uncovering the underlying dimensions that describe the properties of items as well as users’ preferences toward them. In domains like clothing recommendation, explaining users’ preferences requires modeling the visual appearance of the items in question. This makes recommendation especially challenging, due to both the complexity and subtlety of people’s ‘visual preferences,’ as well as the scale and dimensionality of the data and features involved. Ultimately, a successful model should be capable of capturing considerable variance across different categories and styles, while still modeling the commonalities explained by `global’ structures in order to combat the sparsity (e.g. cold-start), variability, and scale of real-world datasets. Here, we address these challenges by building such structures to model the visual dimensions across different product categories. With a novel hierarchical embedding architecture, our method accounts for both high-level (colorfulness, darkness, etc.) and subtle (e.g. casualness) visual characteristics simultaneously. \|
Tasks	Recommendation Systems
Published	2016-04-20
URL	http://arxiv.org/abs/1604.05813v1
PDF	http://arxiv.org/pdf/1604.05813v1.pdf
PWC	https://paperswithcode.com/paper/sherlock-sparse-hierarchical-embeddings-for
Repo
Framework

A Cheap Linear Attention Mechanism with Fast Lookups and Fixed-Size Representations


Title	A Cheap Linear Attention Mechanism with Fast Lookups and Fixed-Size Representations
Authors	Alexandre de Brébisson, Pascal Vincent
Abstract	The softmax content-based attention mechanism has proven to be very beneficial in many applications of recurrent neural networks. Nevertheless it suffers from two major computational limitations. First, its computations for an attention lookup scale linearly in the size of the attended sequence. Second, it does not encode the sequence into a fixed-size representation but instead requires to memorize all the hidden states. These two limitations restrict the use of the softmax attention mechanism to relatively small-scale applications with short sequences and few lookups per sequence. In this work we introduce a family of linear attention mechanisms designed to overcome the two limitations listed above. We show that removing the softmax non-linearity from the traditional attention formulation yields constant-time attention lookups and fixed-size representations of the attended sequences. These properties make these linear attention mechanisms particularly suitable for large-scale applications with extreme query loads, real-time requirements and memory constraints. Early experiments on a question answering task show that these linear mechanisms yield significantly better accuracy results than no attention, but obviously worse than their softmax alternative.
Tasks	Question Answering
Published	2016-09-19
URL	http://arxiv.org/abs/1609.05866v1
PDF	http://arxiv.org/pdf/1609.05866v1.pdf
PWC	https://paperswithcode.com/paper/a-cheap-linear-attention-mechanism-with-fast
Repo
Framework

CUHK & ETHZ & SIAT Submission to ActivityNet Challenge 2016


Title	CUHK & ETHZ & SIAT Submission to ActivityNet Challenge 2016
Authors	Yuanjun Xiong, Limin Wang, Zhe Wang, Bowen Zhang, Hang Song, Wei Li, Dahua Lin, Yu Qiao, Luc Van Gool, Xiaoou Tang
Abstract	This paper presents the method that underlies our submission to the untrimmed video classification task of ActivityNet Challenge 2016. We follow the basic pipeline of temporal segment networks and further raise the performance via a number of other techniques. Specifically, we use the latest deep model architecture, e.g., ResNet and Inception V3, and introduce new aggregation schemes (top-k and attention-weighted pooling). Additionally, we incorporate the audio as a complementary channel, extracting relevant information via a CNN applied to the spectrograms. With these techniques, we derive an ensemble of deep models, which, together, attains a high classification accuracy (mAP $93.23%$) on the testing set and secured the first place in the challenge.
Tasks	Video Classification
Published	2016-08-02
URL	http://arxiv.org/abs/1608.00797v1
PDF	http://arxiv.org/pdf/1608.00797v1.pdf
PWC	https://paperswithcode.com/paper/cuhk-ethz-siat-submission-to-activitynet
Repo
Framework