May 7, 2019

3017 words 15 mins read

Paper Group ANR 106

Multiplayer Games for Learning Multirobot Coordination Algorithms. Doubly stochastic large scale kernel learning with the empirical kernel map. The DLVHEX System for Knowledge Representation: Recent Advances (System Description). When is Clustering Perturbation Robust?. Identifying Stable Patterns over Time for Emotion Recognition from EEG. Computa …

Multiplayer Games for Learning Multirobot Coordination Algorithms


Title	Multiplayer Games for Learning Multirobot Coordination Algorithms
Authors	Arash Tavakoli, Haig Nalbandian, Nora Ayanian
Abstract	Humans have an impressive ability to solve complex coordination problems in a fully distributed manner. This ability, if learned as a set of distributed multirobot coordination strategies, can enable programming large groups of robots to collaborate towards complex coordination objectives in a way similar to humans. Such strategies would offer robustness, adaptability, fault-tolerance, and, importantly, distributed decision-making. To that end, we have designed a networked gaming platform to investigate human group behavior, specifically in solving complex collaborative coordinated tasks. Through this platform, we are able to limit the communication, sensing, and actuation capabilities provided to the players. With the aim of learning coordination algorithms for robots in mind, we define these capabilities to mimic those of a simple ground robot.
Tasks	Decision Making
Published	2016-04-20
URL	http://arxiv.org/abs/1604.05942v1
PDF	http://arxiv.org/pdf/1604.05942v1.pdf
PWC	https://paperswithcode.com/paper/multiplayer-games-for-learning-multirobot
Repo
Framework

Doubly stochastic large scale kernel learning with the empirical kernel map


Title	Doubly stochastic large scale kernel learning with the empirical kernel map
Authors	Nikolaas Steenbergen, Sebastian Schelter, Felix Bießmann
Abstract	With the rise of big data sets, the popularity of kernel methods declined and neural networks took over again. The main problem with kernel methods is that the kernel matrix grows quadratically with the number of data points. Most attempts to scale up kernel methods solve this problem by discarding data points or basis functions of some approximation of the kernel map. Here we present a simple yet effective alternative for scaling up kernel methods that takes into account the entire data set via doubly stochastic optimization of the emprical kernel map. The algorithm is straightforward to implement, in particular in parallel execution settings; it leverages the full power and versatility of classical kernel functions without the need to explicitly formulate a kernel map approximation. We provide empirical evidence that the algorithm works on large data sets.
Tasks	Stochastic Optimization
Published	2016-09-02
URL	http://arxiv.org/abs/1609.00585v2
PDF	http://arxiv.org/pdf/1609.00585v2.pdf
PWC	https://paperswithcode.com/paper/doubly-stochastic-large-scale-kernel-learning
Repo
Framework

The DLVHEX System for Knowledge Representation: Recent Advances (System Description)


Title	The DLVHEX System for Knowledge Representation: Recent Advances (System Description)
Authors	Christoph Redl
Abstract	The DLVHEX system implements the HEX-semantics, which integrates answer set programming (ASP) with arbitrary external sources. Since its first release ten years ago, significant advancements were achieved. Most importantly, the exploitation of properties of external sources led to efficiency improvements and flexibility enhancements of the language, and technical improvements on the system side increased user’s convenience. In this paper, we present the current status of the system and point out the most important recent enhancements over early versions. While existing literature focuses on theoretical aspects and specific components, a bird’s eye view of the overall system is missing. In order to promote the system for real-world applications, we further present applications which were already successfully realized on top of DLVHEX. This paper is under consideration for acceptance in Theory and Practice of Logic Programming.
Tasks
Published	2016-07-29
URL	http://arxiv.org/abs/1607.08864v2
PDF	http://arxiv.org/pdf/1607.08864v2.pdf
PWC	https://paperswithcode.com/paper/the-dlvhex-system-for-knowledge
Repo
Framework

When is Clustering Perturbation Robust?


Title	When is Clustering Perturbation Robust?
Authors	Margareta Ackerman, Jarrod Moore
Abstract	Clustering is a fundamental data mining tool that aims to divide data into groups of similar items. Generally, intuition about clustering reflects the ideal case – exact data sets endowed with flawless dissimilarity between individual instances. In practice however, these cases are in the minority, and clustering applications are typically characterized by noisy data sets with approximate pairwise dissimilarities. As such, the efficacy of clustering methods in practical applications necessitates robustness to perturbations. In this paper, we perform a formal analysis of perturbation robustness, revealing that the extent to which algorithms can exhibit this desirable characteristic is inherently limited, and identifying the types of structures that allow popular clustering paradigms to discover meaningful clusters in spite of faulty data.
Tasks
Published	2016-01-22
URL	http://arxiv.org/abs/1601.05900v1
PDF	http://arxiv.org/pdf/1601.05900v1.pdf
PWC	https://paperswithcode.com/paper/when-is-clustering-perturbation-robust
Repo
Framework

Identifying Stable Patterns over Time for Emotion Recognition from EEG


Title	Identifying Stable Patterns over Time for Emotion Recognition from EEG
Authors	Wei-Long Zheng, Jia-Yi Zhu, Bao-Liang Lu
Abstract	In this paper, we investigate stable patterns of electroencephalogram (EEG) over time for emotion recognition using a machine learning approach. Up to now, various findings of activated patterns associated with different emotions have been reported. However, their stability over time has not been fully investigated yet. In this paper, we focus on identifying EEG stability in emotion recognition. To validate the efficiency of the machine learning algorithms used in this study, we systematically evaluate the performance of various popular feature extraction, feature selection, feature smoothing and pattern classification methods with the DEAP dataset and a newly developed dataset for this study. The experimental results indicate that stable patterns exhibit consistency across sessions; the lateral temporal areas activate more for positive emotion than negative one in beta and gamma bands; the neural patterns of neutral emotion have higher alpha responses at parietal and occipital sites; and for negative emotion, the neural patterns have significant higher delta responses at parietal and occipital sites and higher gamma responses at prefrontal sites. The performance of our emotion recognition system shows that the neural patterns are relatively stable within and between sessions.
Tasks	EEG, Emotion Recognition, Feature Selection
Published	2016-01-10
URL	http://arxiv.org/abs/1601.02197v1
PDF	http://arxiv.org/pdf/1601.02197v1.pdf
PWC	https://paperswithcode.com/paper/identifying-stable-patterns-over-time-for
Repo
Framework

Computational Complexity of Testing Proportional Justified Representation


Title	Computational Complexity of Testing Proportional Justified Representation
Authors	Haris Aziz, Shenwei Huang
Abstract	We consider a committee voting setting in which each voter approves of a subset of candidates and based on the approvals, a target number of candidates are selected. Aziz et al. (2015) proposed two representation axioms called justified representation and extended justified representation. Whereas the former can be tested as well as achieved in polynomial time, the latter property is coNP-complete to test and no polynomial-time algorithm is known to achieve it. Interestingly, S{'a}nchez-Fern{'a}ndez et~al. (2016) proposed an intermediate property called proportional justified representation that admits a polynomial-time algorithm to achieve. The complexity of testing proportional justified representation has remained an open problem. In this paper, we settle the complexity by proving that testing proportional justified representation is coNP-complete. We complement the complexity result by showing that the problem admits efficient algorithms if any of the following parameters are bounded: (1) number of voters (2) number of candidates (3) maximum number of candidates approved by a voter (4) maximum number of voters approving a given candidate.
Tasks
Published	2016-12-20
URL	http://arxiv.org/abs/1612.06476v2
PDF	http://arxiv.org/pdf/1612.06476v2.pdf
PWC	https://paperswithcode.com/paper/computational-complexity-of-testing
Repo
Framework

Words, Concepts, and the Geometry of Analogy


Title	Words, Concepts, and the Geometry of Analogy
Authors	Stephen McGregor, Matthew Purver, Geraint Wiggins
Abstract	This paper presents a geometric approach to the problem of modelling the relationship between words and concepts, focusing in particular on analogical phenomena in language and cognition. Grounded in recent theories regarding geometric conceptual spaces, we begin with an analysis of existing static distributional semantic models and move on to an exploration of a dynamic approach to using high dimensional spaces of word meaning to project subspaces where analogies can potentially be solved in an online, contextualised way. The crucial element of this analysis is the positioning of statistics in a geometric environment replete with opportunities for interpretation.
Tasks
Published	2016-08-04
URL	http://arxiv.org/abs/1608.01403v1
PDF	http://arxiv.org/pdf/1608.01403v1.pdf
PWC	https://paperswithcode.com/paper/words-concepts-and-the-geometry-of-analogy
Repo
Framework

Learning Semantically Coherent and Reusable Kernels in Convolution Neural Nets for Sentence Classification


Title	Learning Semantically Coherent and Reusable Kernels in Convolution Neural Nets for Sentence Classification
Authors	Madhusudan Lakshmana, Sundararajan Sellamanickam, Shirish Shevade, Keerthi Selvaraj
Abstract	The state-of-the-art CNN models give good performance on sentence classification tasks. The purpose of this work is to empirically study desirable properties such as semantic coherence, attention mechanism and reusability of CNNs in these tasks. Semantically coherent kernels are preferable as they are a lot more interpretable for explaining the decision of the learned CNN model. We observe that the learned kernels do not have semantic coherence. Motivated by this observation, we propose to learn kernels with semantic coherence using clustering scheme combined with Word2Vec representation and domain knowledge such as SentiWordNet. We suggest a technique to visualize attention mechanism of CNNs for decision explanation purpose. Reusable property enables kernels learned on one problem to be used in another problem. This helps in efficient learning as only a few additional domain specific filters may have to be learned. We demonstrate the efficacy of our core ideas of learning semantically coherent kernels and leveraging reusable kernels for efficient learning on several benchmark datasets. Experimental results show the usefulness of our approach by achieving performance close to the state-of-the-art methods but with semantic and reusable properties.
Tasks	Sentence Classification
Published	2016-08-01
URL	http://arxiv.org/abs/1608.00466v2
PDF	http://arxiv.org/pdf/1608.00466v2.pdf
PWC	https://paperswithcode.com/paper/learning-semantically-coherent-and-reusable
Repo
Framework

Demonstrating Hybrid Learning in a Flexible Neuromorphic Hardware System


Title	Demonstrating Hybrid Learning in a Flexible Neuromorphic Hardware System
Authors	Simon Friedmann, Johannes Schemmel, Andreas Gruebl, Andreas Hartel, Matthias Hock, Karlheinz Meier
Abstract	We present results from a new approach to learning and plasticity in neuromorphic hardware systems: to enable flexibility in implementable learning mechanisms while keeping high efficiency associated with neuromorphic implementations, we combine a general-purpose processor with full-custom analog elements. This processor is operating in parallel with a fully parallel neuromorphic system consisting of an array of synapses connected to analog, continuous time neuron circuits. Novel analog correlation sensor circuits process spike events for each synapse in parallel and in real-time. The processor uses this pre-processing to compute new weights possibly using additional information following its program. Therefore, learning rules can be defined in software giving a large degree of flexibility. Synapses realize correlation detection geared towards Spike-Timing Dependent Plasticity (STDP) as central computational primitive in the analog domain. Operating at a speed-up factor of 1000 compared to biological time-scale, we measure time-constants from tens to hundreds of micro-seconds. We analyze variability across multiple chips and demonstrate learning using a multiplicative STDP rule. We conclude, that the presented approach will enable flexible and efficient learning as a platform for neuroscientific research and technological applications.
Tasks
Published	2016-04-18
URL	http://arxiv.org/abs/1604.05080v2
PDF	http://arxiv.org/pdf/1604.05080v2.pdf
PWC	https://paperswithcode.com/paper/demonstrating-hybrid-learning-in-a-flexible
Repo
Framework

Learning Visual N-Grams from Web Data


Title	Learning Visual N-Grams from Web Data
Authors	Ang Li, Allan Jabri, Armand Joulin, Laurens van der Maaten
Abstract	Real-world image recognition systems need to recognize tens of thousands of classes that constitute a plethora of visual concepts. The traditional approach of annotating thousands of images per class for training is infeasible in such a scenario, prompting the use of webly supervised data. This paper explores the training of image-recognition systems on large numbers of images and associated user comments. In particular, we develop visual n-gram models that can predict arbitrary phrases that are relevant to the content of an image. Our visual n-gram models are feed-forward convolutional networks trained using new loss functions that are inspired by n-gram models commonly used in language modeling. We demonstrate the merits of our models in phrase prediction, phrase-based image retrieval, relating images and captions, and zero-shot transfer.
Tasks	Image Retrieval, Language Modelling
Published	2016-12-29
URL	http://arxiv.org/abs/1612.09161v2
PDF	http://arxiv.org/pdf/1612.09161v2.pdf
PWC	https://paperswithcode.com/paper/learning-visual-n-grams-from-web-data
Repo
Framework

Entity Type Recognition using an Ensemble of Distributional Semantic Models to Enhance Query Understanding


Title	Entity Type Recognition using an Ensemble of Distributional Semantic Models to Enhance Query Understanding
Authors	Walid Shalaby, Khalifeh Al Jadda, Mohammed Korayem, Trey Grainger
Abstract	We present an ensemble approach for categorizing search query entities in the recruitment domain. Understanding the types of entities expressed in a search query (Company, Skill, Job Title, etc.) enables more intelligent information retrieval based upon those entities compared to a traditional keyword-based search. Because search queries are typically very short, leveraging a traditional bag-of-words model to identify entity types would be inappropriate due to the lack of contextual information. Our approach instead combines clues from different sources of varying complexity in order to collect real-world knowledge about query entities. We employ distributional semantic representations of query entities through two models: 1) contextual vectors generated from encyclopedic corpora like Wikipedia, and 2) high dimensional word embedding vectors generated from millions of job postings using word2vec. Additionally, our approach utilizes both entity linguistic properties obtained from WordNet and ontological properties extracted from DBpedia. We evaluate our approach on a data set created at CareerBuilder; the largest job board in the US. The data set contains entities extracted from millions of job seekers/recruiters search queries, job postings, and resume documents. After constructing the distributional vectors of search entities, we use supervised machine learning to infer search entity types. Empirical results show that our approach outperforms the state-of-the-art word2vec distributional semantics model trained on Wikipedia. Moreover, we achieve micro-averaged F 1 score of 97% using the proposed distributional representations ensemble.
Tasks	Information Retrieval
Published	2016-04-04
URL	http://arxiv.org/abs/1604.00933v1
PDF	http://arxiv.org/pdf/1604.00933v1.pdf
PWC	https://paperswithcode.com/paper/entity-type-recognition-using-an-ensemble-of
Repo
Framework

The Shallow End: Empowering Shallower Deep-Convolutional Networks through Auxiliary Outputs


Title	The Shallow End: Empowering Shallower Deep-Convolutional Networks through Auxiliary Outputs
Authors	Yong Guo, Jian Chen, Qing Du, Anton Van Den Hengel, Qinfeng Shi, Mingkui Tan
Abstract	Depth is one of the key factors behind the success of convolutional neural networks (CNNs). Since ResNet, we are able to train very deep CNNs as the gradient vanishing issue has been largely addressed by the introduction of skip connections. However, we observe that, when the depth is very large, the intermediate layers (especially shallow layers) may fail to receive sufficient supervision from the loss due to the severe transformation through a long backpropagation path. As a result, the representation power of intermediate layers can be very weak and the model becomes very redundant with limited performance. In this paper, we first investigate the supervision vanishing issue in existing backpropagation (BP) methods. And then, we propose to address it via an effective method, called Multi-way BP (MW-BP), which relies on multiple auxiliary losses added to the intermediate layers of the network. The proposed MW-BP method can be applied to most deep architectures with slight modifications, such as ResNet and MobileNet. Our method often gives rise to much more compact models (denoted by “Mw+Architecture”) than existing methods. For example, MwResNet-44 with 44 layers performs better than ResNet-110 with 110 layers on CIFAR-10 and CIFAR-100. More critically, the resultant models even outperform the light models obtained by state-of-the-art model compression methods. Last, our method inherently produces multiple compact models with different depths at the same time, which is helpful for model selection.
Tasks	Model Compression, Model Selection
Published	2016-11-06
URL	https://arxiv.org/abs/1611.01773v6
PDF	https://arxiv.org/pdf/1611.01773v6.pdf
PWC	https://paperswithcode.com/paper/the-shallow-end-empowering-shallower-deep
Repo
Framework

UTSig: A Persian Offline Signature Dataset


Title	UTSig: A Persian Offline Signature Dataset
Authors	Amir Soleimani, Kazim Fouladi, Babak N. Araabi
Abstract	The pivotal role of datasets in signature verification systems motivates researchers to collect signature samples. Distinct characteristics of Persian signature demands for richer and culture-dependent offline signature datasets. This paper introduces a new and public Persian offline signature dataset, UTSig, that consists of 8280 images from 115 classes. Each class has 27 genuine signatures, 3 opposite-hand signatures, and 42 skilled forgeries made by 6 forgers. Compared with the other public datasets, UTSig has more samples, more classes, and more forgers. We considered various variables including signing period, writing instrument, signature box size, and number of observable samples for forgers in the data collection procedure. By careful examination of main characteristics of offline signature datasets, we observe that Persian signatures have fewer numbers of branch points and end points. We propose and evaluate four different training and test setups for UTSig. Results of our experiments show that training genuine samples along with opposite-hand samples and random forgeries can improve the performance in terms of equal error rate and minimum cost of log likelihood ratio.
Tasks
Published	2016-03-10
URL	http://arxiv.org/abs/1603.03235v4
PDF	http://arxiv.org/pdf/1603.03235v4.pdf
PWC	https://paperswithcode.com/paper/utsig-a-persian-offline-signature-dataset
Repo
Framework

Spectral Methods for Correlated Topic Models


Title	Spectral Methods for Correlated Topic Models
Authors	Forough Arabshahi, Animashree Anandkumar
Abstract	In this paper, we propose guaranteed spectral methods for learning a broad range of topic models, which generalize the popular Latent Dirichlet Allocation (LDA). We overcome the limitation of LDA to incorporate arbitrary topic correlations, by assuming that the hidden topic proportions are drawn from a flexible class of Normalized Infinitely Divisible (NID) distributions. NID distributions are generated through the process of normalizing a family of independent Infinitely Divisible (ID) random variables. The Dirichlet distribution is a special case obtained by normalizing a set of Gamma random variables. We prove that this flexible topic model class can be learned via spectral methods using only moments up to the third order, with (low order) polynomial sample and computational complexity. The proof is based on a key new technique derived here that allows us to diagonalize the moments of the NID distribution through an efficient procedure that requires evaluating only univariate integrals, despite the fact that we are handling high dimensional multivariate moments. In order to assess the performance of our proposed Latent NID topic model, we use two real datasets of articles collected from New York Times and Pubmed. Our experiments yield improved perplexity on both datasets compared with the baseline.
Tasks	Topic Models
Published	2016-05-30
URL	http://arxiv.org/abs/1605.09080v5
PDF	http://arxiv.org/pdf/1605.09080v5.pdf
PWC	https://paperswithcode.com/paper/spectral-methods-for-correlated-topic-models
Repo
Framework

Approximate Near Neighbors for General Symmetric Norms


Title	Approximate Near Neighbors for General Symmetric Norms
Authors	Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya Razenshteyn, Erik Waingarten
Abstract	We show that every symmetric normed space admits an efficient nearest neighbor search data structure with doubly-logarithmic approximation. Specifically, for every $n$, $d = n^{o(1)}$, and every $d$-dimensional symmetric norm $\cdot$, there exists a data structure for $\mathrm{poly}(\log \log n)$-approximate nearest neighbor search over $\cdot$ for $n$-point datasets achieving $n^{o(1)}$ query time and $n^{1+o(1)}$ space. The main technical ingredient of the algorithm is a low-distortion embedding of a symmetric norm into a low-dimensional iterated product of top-$k$ norms. We also show that our techniques cannot be extended to general norms.
Tasks
Published	2016-11-18
URL	http://arxiv.org/abs/1611.06222v2
PDF	http://arxiv.org/pdf/1611.06222v2.pdf
PWC	https://paperswithcode.com/paper/approximate-near-neighbors-for-general
Repo
Framework