May 6, 2019

2630 words 13 mins read

Paper Group ANR 162

Makespan Optimal Solving of Cooperative Path-Finding via Reductions to Propositional Satisfiability. Learning to Optimize. Demystifying ResNet. An Improved System for Sentence-level Novelty Detection in Textual Streams. A Comprehensive Comparative Study of Word and Sentence Similarity Measures. Classifying Variable-Length Audio Files with All-Convo …

Makespan Optimal Solving of Cooperative Path-Finding via Reductions to Propositional Satisfiability


Title	Makespan Optimal Solving of Cooperative Path-Finding via Reductions to Propositional Satisfiability
Authors	Pavel Surynek
Abstract	The problem of makespan optimal solving of cooperative path finding (CPF) is addressed in this paper. The task in CPF is to relocate a group of agents in a non-colliding way so that each agent eventually reaches its goal location from the given initial location. The abstraction adopted in this work assumes that agents are discrete items moving in an undirected graph by traversing edges. Makespan optimal solving of CPF means to generate solutions that are as short as possi-ble in terms of the total number of time steps required for the execution of the solution. We show that reducing CPF to propositional satisfiability (SAT) represents a viable option for obtaining makespan optimal solutions. Several encodings of CPF into propositional formulae are suggested and experimentally evaluated. The evaluation indicates that SAT based CPF solving outperforms other makespan optimal methods significantly in highly constrained situations (environments that are densely occupied by agents).
Tasks
Published	2016-10-18
URL	http://arxiv.org/abs/1610.05452v1
PDF	http://arxiv.org/pdf/1610.05452v1.pdf
PWC	https://paperswithcode.com/paper/makespan-optimal-solving-of-cooperative-path
Repo
Framework

Learning to Optimize


Title	Learning to Optimize
Authors	Ke Li, Jitendra Malik
Abstract	Algorithm design is a laborious process and often requires many iterations of ideation and validation. In this paper, we explore automating algorithm design and present a method to learn an optimization algorithm, which we believe to be the first method that can automatically discover a better algorithm. We approach this problem from a reinforcement learning perspective and represent any particular optimization algorithm as a policy. We learn an optimization algorithm using guided policy search and demonstrate that the resulting algorithm outperforms existing hand-engineered algorithms in terms of convergence speed and/or the final objective value.
Tasks
Published	2016-06-06
URL	http://arxiv.org/abs/1606.01885v1
PDF	http://arxiv.org/pdf/1606.01885v1.pdf
PWC	https://paperswithcode.com/paper/learning-to-optimize
Repo
Framework

Demystifying ResNet


Title	Demystifying ResNet
Authors	Sihan Li, Jiantao Jiao, Yanjun Han, Tsachy Weissman
Abstract	The Residual Network (ResNet), proposed in He et al. (2015), utilized shortcut connections to significantly reduce the difficulty of training, which resulted in great performance boosts in terms of both training and generalization error. It was empirically observed in He et al. (2015) that stacking more layers of residual blocks with shortcut 2 results in smaller training error, while it is not true for shortcut of length 1 or 3. We provide a theoretical explanation for the uniqueness of shortcut 2. We show that with or without nonlinearities, by adding shortcuts that have depth two, the condition number of the Hessian of the loss function at the zero initial point is depth-invariant, which makes training very deep models no more difficult than shallow ones. Shortcuts of higher depth result in an extremely flat (high-order) stationary point initially, from which the optimization algorithm is hard to escape. The shortcut 1, however, is essentially equivalent to no shortcuts, which has a condition number exploding to infinity as the number of layers grows. We further argue that as the number of layers tends to infinity, it suffices to only look at the loss function at the zero initial point. Extensive experiments are provided accompanying our theoretical results. We show that initializing the network to small weights with shortcut 2 achieves significantly better results than random Gaussian (Xavier) initialization, orthogonal initialization, and shortcuts of deeper depth, from various perspectives ranging from final loss, learning dynamics and stability, to the behavior of the Hessian along the learning process.
Tasks
Published	2016-11-03
URL	http://arxiv.org/abs/1611.01186v2
PDF	http://arxiv.org/pdf/1611.01186v2.pdf
PWC	https://paperswithcode.com/paper/demystifying-resnet
Repo
Framework

An Improved System for Sentence-level Novelty Detection in Textual Streams


Title	An Improved System for Sentence-level Novelty Detection in Textual Streams
Authors	Xinyu Fu, Eugene Ch’ng, Uwe Aickelin, Lanyun Zhang
Abstract	Novelty detection in news events has long been a difficult problem. A number of models performed well on specific data streams but certain issues are far from being solved, particularly in large data streams from the WWW where unpredictability of new terms requires adaptation in the vector space model. We present a novel event detection system based on the Incremental Term Frequency-Inverse Document Frequency (TF-IDF) weighting incorporated with Locality Sensitive Hashing (LSH). Our system could efficiently and effectively adapt to the changes within the data streams of any new terms with continual updates to the vector space model. Regarding miss probability, our proposed novelty detection framework outperforms a recognised baseline system by approximately 16% when evaluating a benchmark dataset from Google News.
Tasks
Published	2016-04-30
URL	http://arxiv.org/abs/1605.00122v1
PDF	http://arxiv.org/pdf/1605.00122v1.pdf
PWC	https://paperswithcode.com/paper/an-improved-system-for-sentence-level-novelty
Repo
Framework

A Comprehensive Comparative Study of Word and Sentence Similarity Measures


Title	A Comprehensive Comparative Study of Word and Sentence Similarity Measures
Authors	Issa Atoum, Ahmed Otoom, Narayanan Kulathuramaiyer
Abstract	Sentence similarity is considered the basis of many natural language tasks such as information retrieval, question answering and text summarization. The semantic meaning between compared text fragments is based on the words semantic features and their relationships. This article reviews a set of word and sentence similarity measures and compares them on benchmark datasets. On the studied datasets, results showed that hybrid semantic measures perform better than both knowledge and corpus based measures.
Tasks	Information Retrieval, Question Answering, Text Summarization
Published	2016-02-17
URL	http://arxiv.org/abs/1610.04533v1
PDF	http://arxiv.org/pdf/1610.04533v1.pdf
PWC	https://paperswithcode.com/paper/a-comprehensive-comparative-study-of-word-and
Repo
Framework

Classifying Variable-Length Audio Files with All-Convolutional Networks and Masked Global Pooling


Title	Classifying Variable-Length Audio Files with All-Convolutional Networks and Masked Global Pooling
Authors	Lars Hertel, Huy Phan, Alfred Mertins
Abstract	We trained a deep all-convolutional neural network with masked global pooling to perform single-label classification for acoustic scene classification and multi-label classification for domestic audio tagging in the DCASE-2016 contest. Our network achieved an average accuracy of 84.5% on the four-fold cross-validation for acoustic scene recognition, compared to the provided baseline of 72.5%, and an average equal error rate of 0.17 for domestic audio tagging, compared to the baseline of 0.21. The network therefore improves the baselines by a relative amount of 17% and 19%, respectively. The network only consists of convolutional layers to extract features from the short-time Fourier transform and one global pooling layer to combine those features. It particularly possesses neither fully-connected layers, besides the fully-connected output layer, nor dropout layers.
Tasks	Acoustic Scene Classification, Audio Tagging, Multi-Label Classification, Scene Classification, Scene Recognition
Published	2016-07-11
URL	http://arxiv.org/abs/1607.02857v1
PDF	http://arxiv.org/pdf/1607.02857v1.pdf
PWC	https://paperswithcode.com/paper/classifying-variable-length-audio-files-with
Repo
Framework

Gradient Descent Converges to Minimizers


Title	Gradient Descent Converges to Minimizers
Authors	Jason D. Lee, Max Simchowitz, Michael I. Jordan, Benjamin Recht
Abstract	We show that gradient descent converges to a local minimizer, almost surely with random initialization. This is proved by applying the Stable Manifold Theorem from dynamical systems theory.
Tasks
Published	2016-02-16
URL	http://arxiv.org/abs/1602.04915v2
PDF	http://arxiv.org/pdf/1602.04915v2.pdf
PWC	https://paperswithcode.com/paper/gradient-descent-converges-to-minimizers
Repo
Framework

Deep Cross Residual Learning for Multitask Visual Recognition


Title	Deep Cross Residual Learning for Multitask Visual Recognition
Authors	Brendan Jou, Shih-Fu Chang
Abstract	Residual learning has recently surfaced as an effective means of constructing very deep neural networks for object recognition. However, current incarnations of residual networks do not allow for the modeling and integration of complex relations between closely coupled recognition tasks or across domains. Such problems are often encountered in multimedia applications involving large-scale content recognition. We propose a novel extension of residual learning for deep networks that enables intuitive learning across multiple related tasks using cross-connections called cross-residuals. These cross-residuals connections can be viewed as a form of in-network regularization and enables greater network generalization. We show how cross-residual learning (CRL) can be integrated in multitask networks to jointly train and detect visual concepts across several tasks. We present a single multitask cross-residual network with >40% less parameters that is able to achieve competitive, or even better, detection performance on a visual sentiment concept detection problem normally requiring multiple specialized single-task networks. The resulting multitask cross-residual network also achieves better detection performance by about 10.4% over a standard multitask residual network without cross-residuals with even a small amount of cross-task weighting.
Tasks	Object Recognition
Published	2016-04-05
URL	http://arxiv.org/abs/1604.01335v2
PDF	http://arxiv.org/pdf/1604.01335v2.pdf
PWC	https://paperswithcode.com/paper/deep-cross-residual-learning-for-multitask
Repo
Framework

Combinatorial semi-bandit with known covariance


Title	Combinatorial semi-bandit with known covariance
Authors	Rémy Degenne, Vianney Perchet
Abstract	The combinatorial stochastic semi-bandit problem is an extension of the classical multi-armed bandit problem in which an algorithm pulls more than one arm at each stage and the rewards of all pulled arms are revealed. One difference with the single arm variant is that the dependency structure of the arms is crucial. Previous works on this setting either used a worst-case approach or imposed independence of the arms. We introduce a way to quantify the dependency structure of the problem and design an algorithm that adapts to it. The algorithm is based on linear regression and the analysis develops techniques from the linear bandit literature. By comparing its performance to a new lower bound, we prove that it is optimal, up to a poly-logarithmic factor in the number of pulled arms.
Tasks
Published	2016-12-06
URL	http://arxiv.org/abs/1612.01859v1
PDF	http://arxiv.org/pdf/1612.01859v1.pdf
PWC	https://paperswithcode.com/paper/combinatorial-semi-bandit-with-known
Repo
Framework

Computational Estimate Visualisation and Evaluation of Agent Classified Rules Learning System


Title	Computational Estimate Visualisation and Evaluation of Agent Classified Rules Learning System
Authors	Kennedy E. Ehimwenma, Martin Beer, Paul Crowther
Abstract	Student modelling and agent classified rules learning as applied in the development of the intelligent Preassessment System has been presented in [10],[11]. In this paper, we now demystify the theory behind the development of the pre-assessment system followed by some computational experimentation and graph visualisation of the agent classified rules learning algorithm in the estimation and prediction of classified rules. In addition, we present some preliminary results of the pre-assessment system evaluation. From the results, it is gathered that the system has performed according to its design specification.
Tasks
Published	2016-05-28
URL	http://arxiv.org/abs/1605.08878v1
PDF	http://arxiv.org/pdf/1605.08878v1.pdf
PWC	https://paperswithcode.com/paper/computational-estimate-visualisation-and
Repo
Framework

Expressive Completeness of Existential Rule Languages for Ontology-based Query Answering


Title	Expressive Completeness of Existential Rule Languages for Ontology-based Query Answering
Authors	Heng Zhang, Yan Zhang, Jia-Huai You
Abstract	Existential rules, also known as data dependencies in Databases, have been recently rediscovered as a promising family of languages for Ontology-based Query Answering. In this paper, we prove that disjunctive embedded dependencies exactly capture the class of recursively enumerable ontologies in Ontology-based Conjunctive Query Answering (OCQA). Our expressive completeness result does not rely on any built-in linear order on the database. To establish the expressive completeness, we introduce a novel semantic definition for OCQA ontologies. We also show that neither the class of disjunctive tuple-generating dependencies nor the class of embedded dependencies is expressively complete for recursively enumerable OCQA ontologies.
Tasks
Published	2016-04-18
URL	http://arxiv.org/abs/1604.05006v2
PDF	http://arxiv.org/pdf/1604.05006v2.pdf
PWC	https://paperswithcode.com/paper/expressive-completeness-of-existential-rule
Repo
Framework

A max-cut approach to heterogeneity in cryo-electron microscopy


Title	A max-cut approach to heterogeneity in cryo-electron microscopy
Authors	Yariv Aizenbud, Yoel Shkolnisky
Abstract	The field of cryo-electron microscopy has made astounding advancements in the past few years, mainly due to advancements in electron detectors’ technology. Yet, one of the key open challenges of the field remains the processing of heterogeneous data sets, produced from samples containing particles at several different conformational states. For such data sets, the algorithms must include some classification procedure to identify homogeneous groups within the data, so that the images in each group correspond to the same underlying structure. The fundamental importance of the heterogeneity problem in cryo-electron microscopy has drawn many research efforts, and resulted in significant progress in classification algorithms for heterogeneous data sets. While these algorithms are extremely useful and effective in practice, they lack rigorous mathematical analysis and performance guarantees. In this paper, we attempt to make the first steps towards rigorous mathematical analysis of the heterogeneity problem in cryo-electron microscopy. To that end, we present an algorithm for processing heterogeneous data sets, and prove accuracy and stability bounds for it. We also suggest an extension of this algorithm that combines the classification and reconstruction steps. We demonstrate it on simulated data, and compare its performance to the state-of-the-art algorithm in RELION.
Tasks
Published	2016-09-05
URL	https://arxiv.org/abs/1609.01100v2
PDF	https://arxiv.org/pdf/1609.01100v2.pdf
PWC	https://paperswithcode.com/paper/a-max-cut-approach-to-heterogeneity-in-cryo
Repo
Framework

Application of Ontologies in Cloud Computing: The State-Of-The-Art


Title	Application of Ontologies in Cloud Computing: The State-Of-The-Art
Authors	Fahim T. Imam
Abstract	This paper presents a systematic survey on existing literature and seminal works relevant to the application of ontologies in different aspects of Cloud computing. Our hypothesis is that ontologies along with their reasoning capabilities can have significant impact on improving various aspects of the Cloud computing phenomena. Ontologies can promote intelligent decision support mechanisms for various Cloud based services. They can also provide effective interoperability among the Cloud based systems and resources. This survey can promote a comprehensive understanding on the roles and significance of ontologies within the overall domain of Cloud Computing. Also, this project can potentially form the basis of new research area and possibilities for both ontology and Cloud computing communities.
Tasks
Published	2016-10-06
URL	http://arxiv.org/abs/1610.02333v1
PDF	http://arxiv.org/pdf/1610.02333v1.pdf
PWC	https://paperswithcode.com/paper/application-of-ontologies-in-cloud-computing
Repo
Framework

A General Characterization of the Statistical Query Complexity


Title	A General Characterization of the Statistical Query Complexity
Authors	Vitaly Feldman
Abstract	Statistical query (SQ) algorithms are algorithms that have access to an {\em SQ oracle} for the input distribution $D$ instead of i.i.d.~ samples from $D$. Given a query function $\phi:X \rightarrow [-1,1]$, the oracle returns an estimate of ${\bf E}{ x\sim D}[\phi(x)]$ within some tolerance $\tau\phi$ that roughly corresponds to the number of samples. In this work we demonstrate that the complexity of solving general problems over distributions using SQ algorithms can be captured by a relatively simple notion of statistical dimension that we introduce. SQ algorithms capture a broad spectrum of algorithmic approaches used in theory and practice, most notably, convex optimization techniques. Hence our statistical dimension allows to investigate the power of a variety of algorithmic approaches by analyzing a single linear-algebraic parameter. Such characterizations were investigated over the past 20 years in learning theory but prior characterizations are restricted to the much simpler setting of classification problems relative to a fixed distribution on the domain (Blum et al., 1994; Bshouty and Feldman, 2002; Yang, 2001; Simon, 2007; Feldman, 2012; Szorenyi, 2009). Our characterization is also the first to precisely characterize the necessary tolerance of queries. We give applications of our techniques to two open problems in learning theory and to algorithms that are subject to memory and communication constraints.
Tasks
Published	2016-08-07
URL	http://arxiv.org/abs/1608.02198v3
PDF	http://arxiv.org/pdf/1608.02198v3.pdf
PWC	https://paperswithcode.com/paper/a-general-characterization-of-the-statistical
Repo
Framework

Employing traditional machine learning algorithms for big data streams analysis: the case of object trajectory prediction


Title	Employing traditional machine learning algorithms for big data streams analysis: the case of object trajectory prediction
Authors	Angelos Valsamis, Konstantinos Tserpes, Dimitrios Zissis, Dimosthenis Anagnostopoulos, Theodora Varvarigou
Abstract	In this paper, we model the trajectory of sea vessels and provide a service that predicts in near-real time the position of any given vessel in 4’, 10’, 20’ and 40’ time intervals. We explore the necessary tradeoffs between accuracy, performance and resource utilization are explored given the large volume and update rates of input data. We start with building models based on well-established machine learning algorithms using static datasets and multi-scan training approaches and identify the best candidate to be used in implementing a single-pass predictive approach, under real-time constraints. The results are measured in terms of accuracy and performance and are compared against the baseline kinematic equations. Results show that it is possible to efficiently model the trajectory of multiple vessels using a single model, which is trained and evaluated using an adequately large, static dataset, thus achieving a significant gain in terms of resource usage while not compromising accuracy.
Tasks	Trajectory Prediction
Published	2016-09-01
URL	http://arxiv.org/abs/1609.00203v1
PDF	http://arxiv.org/pdf/1609.00203v1.pdf
PWC	https://paperswithcode.com/paper/employing-traditional-machine-learning
Repo
Framework