October 20, 2019

2835 words 14 mins read

Paper Group ANR 73

Adaptive Independence Tests with Geo-Topological Transformation. An efficient $k$-means-type algorithm for clustering datasets with incomplete records. Roster Evaluation Based on Classifiers for the Nurse Rostering Problem. Efficient Principal Subspace Projection of Streaming Data Through Fast Similarity Matching. Robust Spectral Filtering and Anom …

Adaptive Independence Tests with Geo-Topological Transformation


Title	Adaptive Independence Tests with Geo-Topological Transformation
Authors	Baihan Lin, Nikolaus Kriegeskorte
Abstract	Testing two potentially multivariate variables for statistical dependence on the basis finite samples is a fundamental statistical challenge. Here we explore a family of tests that adapt to the complexity of the relationship between the variables, promising robust power across scenarios. Building on the distance correlation, we introduce a family of adaptive independence criteria based on nonlinear monotonic transformations of distances. We show that these criteria, like the distance correlation and RKHS-based criteria, provide dependence indicators. We propose a class of adaptive (multi-threshold) test statistics, which form the basis for permutation tests. These tests empirically outperform some of the established tests in average and worst-case statistical sensitivity across a range of univariate and multivariate relationships and might deserve further exploration.
Tasks
Published	2018-10-06
URL	https://arxiv.org/abs/1810.02923v2
PDF	https://arxiv.org/pdf/1810.02923v2.pdf
PWC	https://paperswithcode.com/paper/adaptive-independence-tests-with-geo
Repo
Framework

An efficient $k$-means-type algorithm for clustering datasets with incomplete records


Title	An efficient $k$-means-type algorithm for clustering datasets with incomplete records
Authors	Andrew Lithio, Ranjan Maitra
Abstract	The $k$-means algorithm is arguably the most popular nonparametric clustering method but cannot generally be applied to datasets with incomplete records. The usual practice then is to either impute missing values under an assumed missing-completely-at-random mechanism or to ignore the incomplete records, and apply the algorithm on the resulting dataset. We develop an efficient version of the $k$-means algorithm that allows for clustering in the presence of incomplete records. Our extension is called $k_m$-means and reduces to the $k$-means algorithm when all records are complete. We also provide initialization strategies for our algorithm and methods to estimate the number of groups in the dataset. Illustrations and simulations demonstrate the efficacy of our approach in a variety of settings and patterns of missing data. Our methods are also applied to the analysis of activation images obtained from a functional Magnetic Resonance Imaging experiment.
Tasks
Published	2018-02-23
URL	http://arxiv.org/abs/1802.08363v2
PDF	http://arxiv.org/pdf/1802.08363v2.pdf
PWC	https://paperswithcode.com/paper/an-efficient-k-means-type-algorithm-for
Repo
Framework

Roster Evaluation Based on Classifiers for the Nurse Rostering Problem


Title	Roster Evaluation Based on Classifiers for the Nurse Rostering Problem
Authors	Roman Václavík, Přemysl Šůcha, Zdeněk Hanzálek
Abstract	The personnel scheduling problem is a well-known NP-hard combinatorial problem. Due to the complexity of this problem and the size of the real-world instances, it is not possible to use exact methods, and thus heuristics, meta-heuristics, or hyper-heuristics must be employed. The majority of heuristic approaches are based on iterative search, where the quality of intermediate solutions must be calculated. Unfortunately, this is computationally highly expensive because these problems have many constraints and some are very complex. In this study, we propose a machine learning technique as a tool to accelerate the evaluation phase in heuristic approaches. The solution is based on a simple classifier, which is able to determine whether the changed solution (more precisely, the changed part of the solution) is better than the original or not. This decision is made much faster than a standard cost-oriented evaluation process. However, the classification process cannot guarantee 100% correctness. Therefore, our approach, which is illustrated using a tabu search algorithm in this study, includes a filtering mechanism, where the classifier rejects the majority of the potentially bad solutions and the remaining solutions are then evaluated in a standard manner. We also show how the boosting algorithms can improve the quality of the final solution compared with a simple classifier. We verified our proposed approach and premises, based on standard and real-world benchmark instances, to demonstrate the significant speedup obtained with comparable solution quality.
Tasks
Published	2018-04-13
URL	http://arxiv.org/abs/1804.05002v1
PDF	http://arxiv.org/pdf/1804.05002v1.pdf
PWC	https://paperswithcode.com/paper/roster-evaluation-based-on-classifiers-for
Repo
Framework

Efficient Principal Subspace Projection of Streaming Data Through Fast Similarity Matching


Title	Efficient Principal Subspace Projection of Streaming Data Through Fast Similarity Matching
Authors	Andrea Giovannucci, Victor Minden, Cengiz Pehlevan, Dmitri B. Chklovskii
Abstract	Big data problems frequently require processing datasets in a streaming fashion, either because all data are available at once but collectively are larger than available memory or because the data intrinsically arrive one data point at a time and must be processed online. Here, we introduce a computationally efficient version of similarity matching, a framework for online dimensionality reduction that incrementally estimates the top K-dimensional principal subspace of streamed data while keeping in memory only the last sample and the current iterate. To assess the performance of our approach, we construct and make public a test suite containing both a synthetic data generator and the infrastructure to test online dimensionality reduction algorithms on real datasets, as well as performant implementations of our algorithm and competing algorithms with similar aims. Among the algorithms considered we find our approach to be competitive, performing among the best on both synthetic and real data.
Tasks	Dimensionality Reduction
Published	2018-08-06
URL	http://arxiv.org/abs/1808.02083v1
PDF	http://arxiv.org/pdf/1808.02083v1.pdf
PWC	https://paperswithcode.com/paper/efficient-principal-subspace-projection-of
Repo
Framework

Robust Spectral Filtering and Anomaly Detection


Title	Robust Spectral Filtering and Anomaly Detection
Authors	Jakub Marecek, Tigran Tchrakian
Abstract	We consider a setting, where the output of a linear dynamical system (LDS) is, with an unknown but fixed probability, replaced by noise. There, we present a robust method for the prediction of the outputs of the LDS and identification of the samples of noise, and prove guarantees on its statistical performance. One application lies in anomaly detection: the samples of noise, unlikely to have been generated by the dynamics, can be flagged to operators of the system for further study.
Tasks	Anomaly Detection
Published	2018-08-03
URL	http://arxiv.org/abs/1808.01181v1
PDF	http://arxiv.org/pdf/1808.01181v1.pdf
PWC	https://paperswithcode.com/paper/robust-spectral-filtering-and-anomaly
Repo
Framework

Unsupervised vehicle recognition using incremental reseeding of acoustic signatures


Title	Unsupervised vehicle recognition using incremental reseeding of acoustic signatures
Authors	Justin Sunu, Blake Hunter, Allon G. Percus
Abstract	Vehicle recognition and classification have broad applications, ranging from traffic flow management to military target identification. We demonstrate an unsupervised method for automated identification of moving vehicles from roadside audio sensors. Using a short-time Fourier transform to decompose audio signals, we treat the frequency signature in each time window as an individual data point. We then use a spectral embedding for dimensionality reduction. Based on the leading eigenvectors, we relate the performance of an incremental reseeding algorithm to that of spectral clustering. We find that incremental reseeding accurately identifies individual vehicles using their acoustic signatures.
Tasks	Dimensionality Reduction
Published	2018-02-17
URL	http://arxiv.org/abs/1802.06287v1
PDF	http://arxiv.org/pdf/1802.06287v1.pdf
PWC	https://paperswithcode.com/paper/unsupervised-vehicle-recognition-using
Repo
Framework

CascadeCNN: Pushing the Performance Limits of Quantisation in Convolutional Neural Networks


Title	CascadeCNN: Pushing the Performance Limits of Quantisation in Convolutional Neural Networks
Authors	Alexandros Kouris, Stylianos I. Venieris, Christos-Savvas Bouganis
Abstract	This work presents CascadeCNN, an automated toolflow that pushes the quantisation limits of any given CNN model, aiming to perform high-throughput inference. A two-stage architecture tailored for any given CNN-FPGA pair is generated, consisting of a low- and high-precision unit in a cascade. A confidence evaluation unit is employed to identify misclassified cases from the excessively low-precision unit and forward them to the high-precision unit for re-processing. Experiments demonstrate that the proposed toolflow can achieve a performance boost up to 55% for VGG-16 and 48% for AlexNet over the baseline design for the same resource budget and accuracy, without the need of retraining the model or accessing the training data.
Tasks
Published	2018-07-13
URL	http://arxiv.org/abs/1807.05053v1
PDF	http://arxiv.org/pdf/1807.05053v1.pdf
PWC	https://paperswithcode.com/paper/cascadecnn-pushing-the-performance-limits-of-1
Repo
Framework

Streaming Kernel PCA with $\tilde{O}(\sqrt{n})$ Random Features


Title	Streaming Kernel PCA with $\tilde{O}(\sqrt{n})$ Random Features
Authors	Enayat Ullah, Poorya Mianjy, Teodor V. Marinov, Raman Arora
Abstract	We study the statistical and computational aspects of kernel principal component analysis using random Fourier features and show that under mild assumptions, $O(\sqrt{n} \log n)$ features suffices to achieve $O(1/\epsilon^2)$ sample complexity. Furthermore, we give a memory efficient streaming algorithm based on classical Oja’s algorithm that achieves this rate.
Tasks
Published	2018-08-02
URL	http://arxiv.org/abs/1808.00934v2
PDF	http://arxiv.org/pdf/1808.00934v2.pdf
PWC	https://paperswithcode.com/paper/streaming-kernel-pca-with-tildeosqrtn-random
Repo
Framework

Stochastic Learning of Nonstationary Kernels for Natural Language Modeling


Title	Stochastic Learning of Nonstationary Kernels for Natural Language Modeling
Authors	Sahil Garg, Greg Ver Steeg, Aram Galstyan
Abstract	Natural language processing often involves computations with semantic or syntactic graphs to facilitate sophisticated reasoning based on structural relationships. While convolution kernels provide a powerful tool for comparing graph structure based on node (word) level relationships, they are difficult to customize and can be computationally expensive. We propose a generalization of convolution kernels, with a nonstationary model, for better expressibility of natural languages in supervised settings. For a scalable learning of the parameters introduced with our model, we propose a novel algorithm that leverages stochastic sampling on k-nearest neighbor graphs, along with approximations based on locality-sensitive hashing. We demonstrate the advantages of our approach on a challenging real-world (structured inference) problem of automatically extracting biological models from the text of scientific papers.
Tasks	Language Modelling
Published	2018-01-11
URL	http://arxiv.org/abs/1801.03911v2
PDF	http://arxiv.org/pdf/1801.03911v2.pdf
PWC	https://paperswithcode.com/paper/stochastic-learning-of-nonstationary-kernels
Repo
Framework

Reinforcement Learning based Dynamic Model Selection for Short-Term Load Forecasting


Title	Reinforcement Learning based Dynamic Model Selection for Short-Term Load Forecasting
Authors	Cong Feng, Jie Zhang
Abstract	With the growing prevalence of smart grid technology, short-term load forecasting (STLF) becomes particularly important in power system operations. There is a large collection of methods developed for STLF, but selecting a suitable method under varying conditions is still challenging. This paper develops a novel reinforcement learning based dynamic model selection (DMS) method for STLF. A forecasting model pool is first built, including ten state-of-the-art machine learning based forecasting models. Then a Q-learning agent learns the optimal policy of selecting the best forecasting model for the next time step, based on the model performance. The optimal DMS policy is applied to select the best model at each time step with a moving window. Numerical simulations on two-year load and weather data show that the Q-learning algorithm converges fast, resulting in effective and efficient DMS. The developed STLF model with Q-learning based DMS improves the forecasting accuracy by approximately 50%, compared to the state-of-the-art machine learning based STLF models.
Tasks	Load Forecasting, Model Selection, Q-Learning
Published	2018-11-05
URL	http://arxiv.org/abs/1811.01846v1
PDF	http://arxiv.org/pdf/1811.01846v1.pdf
PWC	https://paperswithcode.com/paper/reinforcement-learning-based-dynamic-model
Repo
Framework

Model Selection for Nonnegative Matrix Factorization by Support Union Recovery


Title	Model Selection for Nonnegative Matrix Factorization by Support Union Recovery
Authors	Zhaoqiang Liu
Abstract	Nonnegative matrix factorization (NMF) has been widely used in machine learning and signal processing because of its non-subtractive, part-based property which enhances interpretability. It is often assumed that the latent dimensionality (or the number of components) is given. Despite the large amount of algorithms designed for NMF, there is little literature about automatic model selection for NMF with theoretical guarantees. In this paper, we propose an algorithm that first calculates an empirical second-order moment from the empirical fourth-order cumulant tensor, and then estimates the latent dimensionality by recovering the support union (the index set of non-zero rows) of a matrix related to the empirical second-order moment. By assuming a generative model of the data with additional mild conditions, our algorithm provably detects the true latent dimensionality. We show on synthetic examples that our proposed algorithm is able to find an approximately correct number of components.
Tasks	Model Selection
Published	2018-10-23
URL	http://arxiv.org/abs/1810.10078v1
PDF	http://arxiv.org/pdf/1810.10078v1.pdf
PWC	https://paperswithcode.com/paper/model-selection-for-nonnegative-matrix
Repo
Framework

A Deep Cascade Model for Multi-Document Reading Comprehension


Title	A Deep Cascade Model for Multi-Document Reading Comprehension
Authors	Ming Yan, Jiangnan Xia, Chen Wu, Bin Bi, Zhongzhou Zhao, Ji Zhang, Luo Si, Rui Wang, Wei Wang, Haiqing Chen
Abstract	A fundamental trade-off between effectiveness and efficiency needs to be balanced when designing an online question answering system. Effectiveness comes from sophisticated functions such as extractive machine reading comprehension (MRC), while efficiency is obtained from improvements in preliminary retrieval components such as candidate document selection and paragraph ranking. Given the complexity of the real-world multi-document MRC scenario, it is difficult to jointly optimize both in an end-to-end system. To address this problem, we develop a novel deep cascade learning model, which progressively evolves from the document-level and paragraph-level ranking of candidate texts to more precise answer extraction with machine reading comprehension. Specifically, irrelevant documents and paragraphs are first filtered out with simple functions for efficiency consideration. Then we jointly train three modules on the remaining texts for better tracking the answer: the document extraction, the paragraph extraction and the answer extraction. Experiment results show that the proposed method outperforms the previous state-of-the-art methods on two large-scale multi-document benchmark datasets, i.e., TriviaQA and DuReader. In addition, our online system can stably serve typical scenarios with millions of daily requests in less than 50ms.
Tasks	Machine Reading Comprehension, Question Answering, Reading Comprehension
Published	2018-11-28
URL	http://arxiv.org/abs/1811.11374v1
PDF	http://arxiv.org/pdf/1811.11374v1.pdf
PWC	https://paperswithcode.com/paper/a-deep-cascade-model-for-multi-document
Repo
Framework


Title	Emergence of Altruism Behavior for Multi Feeding Areas in Army Ant Social Evolutionary System
Authors	Takumi Ichimura, Takuya Uemoto, Akira Hara
Abstract	Army ants perform the altruism that an ant sacrifices its own well-being for the benefit of another ants. Army ants build bridges using their own bodies along the path from a food to the nest. We developed the army ant inspired social evolutionary system which can perform the altruism. The system has 2 kinds of ant agents, `Major ant' and` Minor ant’ and the ants communicate with each other via pheromones. One ants can recognize them as the signals from the other ants. The pheromones evaporate with the certain ratio and diffused into the space of neighbors stochastically. If the optimal bridge is found, the path through the bridge is the shortest route from foods to the nest. We define the probability for an ant to leave a bridge at a low occupancy condition of ants and propose the constructing method of the optimal route. In this paper, the behaviors of ant under the environment with two or more feeding spots are observed. Some experimental results show the behaviors of great interest with respect to altruism of ants. The description in some computer simulation is reported in this paper.
Tasks
Published	2018-07-10
URL	http://arxiv.org/abs/1807.04118v1
PDF	http://arxiv.org/pdf/1807.04118v1.pdf
PWC	https://paperswithcode.com/paper/emergence-of-altruism-behavior-for-multi
Repo
Framework

Learning Deep Representations for Semantic Image Parsing: a Comprehensive Overview


Title	Learning Deep Representations for Semantic Image Parsing: a Comprehensive Overview
Authors	Lili Huang, Jiefeng Peng, Ruimao Zhang, Guanbin Li, Liang Lin
Abstract	Semantic image parsing, which refers to the process of decomposing images into semantic regions and constructing the structure representation of the input, has recently aroused widespread interest in the field of computer vision. The recent application of deep representation learning has driven this field into a new stage of development. In this paper, we summarize three aspects of the progress of research on semantic image parsing, i.e., category-level semantic segmentation, instance-level semantic segmentation, and beyond segmentation. Specifically, we first review the general frameworks for each task and introduce the relevant variants. The advantages and limitations of each method are also discussed. Moreover, we present a comprehensive comparison of different benchmark datasets and evaluation metrics. Finally, we explore the future trends and challenges of semantic image parsing.
Tasks	Representation Learning, Semantic Segmentation
Published	2018-10-10
URL	http://arxiv.org/abs/1810.04377v1
PDF	http://arxiv.org/pdf/1810.04377v1.pdf
PWC	https://paperswithcode.com/paper/learning-deep-representations-for-semantic
Repo
Framework

Fine-grained Classification using Heterogeneous Web Data and Auxiliary Categories


Title	Fine-grained Classification using Heterogeneous Web Data and Auxiliary Categories
Authors	Li Niu, Ashok Veeraraghavan, Ashu Sabharwal
Abstract	Fine-grained classification remains a very challenging problem, because of the absence of well-labeled training data caused by the high cost of annotating a large number of fine-grained categories. In the extreme case, given a set of test categories without any well-labeled training data, the majority of existing works can be grouped into the following two research directions: 1) crawl noisy labeled web data for the test categories as training data, which is dubbed as webly supervised learning; 2) transfer the knowledge from auxiliary categories with well-labeled training data to the test categories, which corresponds to zero-shot learning setting. Nevertheless, the above two research directions still have critical issues to be addressed. For the first direction, web data have noisy labels and considerably different data distribution from test data. For the second direction, zero-shot learning is struggling to achieve compelling results compared with conventional supervised learning. The issues of the above two directions motivate us to develop a novel approach which can jointly exploit both noisy web training data from test categories and well-labeled training data from auxiliary categories. In particular, on one hand, we crawl web data for test categories as noisy training data. On the other hand, we transfer the knowledge from auxiliary categories with well-labeled training data to test categories by virtue of free semantic information (e.g., word vector) of all categories. Moreover, given the fact that web data are generally associated with additional textual information (e.g., title and tag), we extend our method by using the surrounding textual information of web data as privileged information. Extensive experiments show the effectiveness of our proposed methods.
Tasks	Zero-Shot Learning
Published	2018-11-19
URL	http://arxiv.org/abs/1811.07567v1
PDF	http://arxiv.org/pdf/1811.07567v1.pdf
PWC	https://paperswithcode.com/paper/fine-grained-classification-using
Repo
Framework