May 7, 2019

3059 words 15 mins read

Paper Group ANR 120

Feature Encoding in Band-limited Distributed Surveillance Systems. Matrix Variate RBM Model with Gaussian Distributions. Revealing Structure in Large Graphs: Szemerédi’s Regularity Lemma and its Use in Pattern Recognition. Clustering Algorithms: A Comparative Approach. Online Learning with Low Rank Experts. An application of incomplete pairwise com …

Feature Encoding in Band-limited Distributed Surveillance Systems


Title	Feature Encoding in Band-limited Distributed Surveillance Systems
Authors	Alireza Rahimpour, Ali Taalimi, Hairong Qi
Abstract	Distributed surveillance systems have become popular in recent years due to security concerns. However, transmitting high dimensional data in bandwidth-limited distributed systems becomes a major challenge. In this paper, we address this issue by proposing a novel probabilistic algorithm based on the divergence between the probability distributions of the visual features in order to reduce their dimensionality and thus save the network bandwidth in distributed wireless smart camera networks. We demonstrate the effectiveness of the proposed approach through extensive experiments on two surveillance recognition tasks.
Tasks
Published	2016-12-19
URL	http://arxiv.org/abs/1612.06423v3
PDF	http://arxiv.org/pdf/1612.06423v3.pdf
PWC	https://paperswithcode.com/paper/feature-encoding-in-band-limited-distributed
Repo
Framework

Matrix Variate RBM Model with Gaussian Distributions


Title	Matrix Variate RBM Model with Gaussian Distributions
Authors	Simeng Liu, Yanfeng Sun, Yongli Hu, Junbin Gao, Baocai Yin
Abstract	Restricted Boltzmann Machine (RBM) is a particular type of random neural network models modeling vector data based on the assumption of Bernoulli distribution. For multi-dimensional and non-binary data, it is necessary to vectorize and discretize the information in order to apply the conventional RBM. It is well-known that vectorization would destroy internal structure of data, and the binary units will limit the applying performance due to fickle real data. To address the issue, this paper proposes a Matrix variate Gaussian Restricted Boltzmann Machine (MVGRBM) model for matrix data whose entries follow Gaussian distributions. Compared with some other RBM algorithm, MVGRBM can model real value data better and it has good performance in image classification.
Tasks	Image Classification
Published	2016-09-21
URL	http://arxiv.org/abs/1609.06417v2
PDF	http://arxiv.org/pdf/1609.06417v2.pdf
PWC	https://paperswithcode.com/paper/matrix-variate-rbm-model-with-gaussian
Repo
Framework

Revealing Structure in Large Graphs: Szemerédi’s Regularity Lemma and its Use in Pattern Recognition


Title	Revealing Structure in Large Graphs: Szemerédi’s Regularity Lemma and its Use in Pattern Recognition
Authors	Marcello Pelillo, Ismail Elezi, Marco Fiorucci
Abstract	Introduced in the mid-1970’s as an intermediate step in proving a long-standing conjecture on arithmetic progressions, Szemer'edi’s regularity lemma has emerged over time as a fundamental tool in different branches of graph theory, combinatorics and theoretical computer science. Roughly, it states that every graph can be approximated by the union of a small number of random-like bipartite graphs called regular pairs. In other words, the result provides us a way to obtain a good description of a large graph using a small amount of data, and can be regarded as a manifestation of the all-pervading dichotomy between structure and randomness. In this paper we will provide an overview of the regularity lemma and its algorithmic aspects, and will discuss its relevance in the context of pattern recognition research.
Tasks
Published	2016-09-21
URL	http://arxiv.org/abs/1609.06583v1
PDF	http://arxiv.org/pdf/1609.06583v1.pdf
PWC	https://paperswithcode.com/paper/revealing-structure-in-large-graphs
Repo
Framework

Clustering Algorithms: A Comparative Approach


Title	Clustering Algorithms: A Comparative Approach
Authors	Mayra Z. Rodriguez, Cesar H. Comin, Dalcimar Casanova, Odemir M. Bruno, Diego R. Amancio, Francisco A. Rodrigues, Luciano da F. Costa
Abstract	Many real-world systems can be studied in terms of pattern recognition tasks, so that proper use (and understanding) of machine learning methods in practical applications becomes essential. While a myriad of classification methods have been proposed, there is no consensus on which methods are more suitable for a given dataset. As a consequence, it is important to comprehensively compare methods in many possible scenarios. In this context, we performed a systematic comparison of 7 well-known clustering methods available in the R language. In order to account for the many possible variations of data, we considered artificial datasets with several tunable properties (number of classes, separation between classes, etc). In addition, we also evaluated the sensitivity of the clustering methods with regard to their parameters configuration. The results revealed that, when considering the default configurations of the adopted methods, the spectral approach usually outperformed the other clustering algorithms. We also found that the default configuration of the adopted implementations was not accurate. In these cases, a simple approach based on random selection of parameters values proved to be a good alternative to improve the performance. All in all, the reported approach provides subsidies guiding the choice of clustering algorithms.
Tasks
Published	2016-12-26
URL	http://arxiv.org/abs/1612.08388v1
PDF	http://arxiv.org/pdf/1612.08388v1.pdf
PWC	https://paperswithcode.com/paper/clustering-algorithms-a-comparative-approach
Repo
Framework

Online Learning with Low Rank Experts


Title	Online Learning with Low Rank Experts
Authors	Elad Hazan, Tomer Koren, Roi Livni, Yishay Mansour
Abstract	We consider the problem of prediction with expert advice when the losses of the experts have low-dimensional structure: they are restricted to an unknown $d$-dimensional subspace. We devise algorithms with regret bounds that are independent of the number of experts and depend only on the rank $d$. For the stochastic model we show a tight bound of $\Theta(\sqrt{dT})$, and extend it to a setting of an approximate $d$ subspace. For the adversarial model we show an upper bound of $O(d\sqrt{T})$ and a lower bound of $\Omega(\sqrt{dT})$.
Tasks
Published	2016-03-21
URL	http://arxiv.org/abs/1603.06352v2
PDF	http://arxiv.org/pdf/1603.06352v2.pdf
PWC	https://paperswithcode.com/paper/online-learning-with-low-rank-experts
Repo
Framework

An application of incomplete pairwise comparison matrices for ranking top tennis players


Title	An application of incomplete pairwise comparison matrices for ranking top tennis players
Authors	Sándor Bozóki, László Csató, József Temesi
Abstract	Pairwise comparison is an important tool in multi-attribute decision making. Pairwise comparison matrices (PCM) have been applied for ranking criteria and for scoring alternatives according to a given criterion. Our paper presents a special application of incomplete PCMs: ranking of professional tennis players based on their results against each other. The selected 25 players have been on the top of the ATP rankings for a shorter or longer period in the last 40 years. Some of them have never met on the court. One of the aims of the paper is to provide ranking of the selected players, however, the analysis of incomplete pairwise comparison matrices is also in the focus. The eigenvector method and the logarithmic least squares method were used to calculate weights from incomplete PCMs. In our results the top three players of four decades were Nadal, Federer and Sampras. Some questions have been raised on the properties of incomplete PCMs and remains open for further investigation.
Tasks	Decision Making
Published	2016-11-02
URL	http://arxiv.org/abs/1611.00538v1
PDF	http://arxiv.org/pdf/1611.00538v1.pdf
PWC	https://paperswithcode.com/paper/an-application-of-incomplete-pairwise
Repo
Framework

Theoretical Aspects of Cyclic Structural Causal Models


Title	Theoretical Aspects of Cyclic Structural Causal Models
Authors	Stephan Bongers, Jonas Peters, Bernhard Schölkopf, Joris M. Mooij
Abstract	Structural causal models (SCMs), also known as (non-parametric) structural equation models (SEMs), are widely used for causal modeling purposes. A large body of theoretical results is available for the special case in which cycles are absent (i.e., acyclic SCMs, also known as recursive SEMs). However, in many application domains cycles are abundantly present, for example in the form of feedback loops. In this paper, we provide a general and rigorous theory of cyclic SCMs. The paper consists of two parts: the first part gives a rigorous treatment of structural causal models, dealing with measure-theoretic and other complications that arise in the presence of cycles. In contrast with the acyclic case, in cyclic SCMs solutions may no longer exist, or if they exist, they may no longer be unique, or even measurable in general. We give several sufficient and necessary conditions for the existence of (unique) measurable solutions. We show how causal reasoning proceeds in these models and how this differs from the acyclic case. Moreover, we give an overview of the Markov properties that hold for cyclic SCMs. In the second part, we address the question of how one can marginalize an SCM (possibly with cycles) to a subset of the endogenous variables. We show that under a certain condition, one can effectively remove a subset of the endogenous variables from the model, leading to a more parsimonious marginal SCM that preserves the causal and counterfactual semantics of the original SCM on the remaining variables. Moreover, we show how the marginalization relates to the latent projection and to latent confounders, i.e. latent common causes.
Tasks
Published	2016-11-18
URL	http://arxiv.org/abs/1611.06221v2
PDF	http://arxiv.org/pdf/1611.06221v2.pdf
PWC	https://paperswithcode.com/paper/theoretical-aspects-of-cyclic-structural
Repo
Framework

Towards better decoding and language model integration in sequence to sequence models


Title	Towards better decoding and language model integration in sequence to sequence models
Authors	Jan Chorowski, Navdeep Jaitly
Abstract	The recently proposed Sequence-to-Sequence (seq2seq) framework advocates replacing complex data processing pipelines, such as an entire automatic speech recognition system, with a single neural network trained in an end-to-end fashion. In this contribution, we analyse an attention-based seq2seq speech recognition system that directly transcribes recordings into characters. We observe two shortcomings: overconfidence in its predictions and a tendency to produce incomplete transcriptions when language models are used. We propose practical solutions to both problems achieving competitive speaker independent word error rates on the Wall Street Journal dataset: without separate language models we reach 10.6% WER, while together with a trigram language model, we reach 6.7% WER.
Tasks	Language Modelling, Speech Recognition
Published	2016-12-08
URL	http://arxiv.org/abs/1612.02695v1
PDF	http://arxiv.org/pdf/1612.02695v1.pdf
PWC	https://paperswithcode.com/paper/towards-better-decoding-and-language-model
Repo
Framework

The (1+1) Elitist Black-Box Complexity of LeadingOnes


Title	The (1+1) Elitist Black-Box Complexity of LeadingOnes
Authors	Carola Doerr, Johannes Lengler
Abstract	One important goal of black-box complexity theory is the development of complexity models allowing to derive meaningful lower bounds for whole classes of randomized search heuristics. Complementing classical runtime analysis, black-box models help us understand how algorithmic choices such as the population size, the variation operators, or the selection rules influence the optimization time. One example for such a result is the $\Omega(n \log n)$ lower bound for unary unbiased algorithms on functions with a unique global optimum [Lehre/Witt, GECCO 2010], which tells us that higher arity operators or biased sampling strategies are needed when trying to beat this bound. In lack of analyzing techniques, almost no non-trivial bounds are known for other restricted models. Proving such bounds therefore remains to be one of the main challenges in black-box complexity theory. With this paper we contribute to our technical toolbox for lower bound computations by proposing a new type of information-theoretic argument. We regard the permutation- and bit-invariant version of \textsc{LeadingOnes} and prove that its (1+1) elitist black-box complexity is $\Omega(n^2)$, a bound that is matched by (1+1)-type evolutionary algorithms. The (1+1) elitist complexity of \textsc{LeadingOnes} is thus considerably larger than its unrestricted one, which is known to be of order $n\log\log n$ [Afshani et al., 2013].
Tasks
Published	2016-04-08
URL	http://arxiv.org/abs/1604.02355v1
PDF	http://arxiv.org/pdf/1604.02355v1.pdf
PWC	https://paperswithcode.com/paper/the-11-elitist-black-box-complexity-of
Repo
Framework

The ontogeny of discourse structure mimics the development of literature


Title	The ontogeny of discourse structure mimics the development of literature
Authors	Natalia Bezerra Mota, Sylvia Pinheiro, Mariano Sigman, Diego Fernandez Slezak, Guillermo Cecchi, Mauro Copelli, Sidarta Ribeiro
Abstract	Discourse varies with age, education, psychiatric state and historical epoch, but the ontogenetic and cultural dynamics of discourse structure remain to be quantitatively characterized. To this end we investigated word graphs obtained from verbal reports of 200 subjects ages 2-58, and 676 literary texts spanning ~5,000 years. In healthy subjects, lexical diversity, graph size, and long-range recurrence departed from initial near-random levels through a monotonic asymptotic increase across ages, while short-range recurrence showed a corresponding decrease. These changes were explained by education and suggest a hierarchical development of discourse structure: short-range recurrence and lexical diversity stabilize after elementary school, but graph size and long-range recurrence only stabilize after high school. This gradual maturation was blurred in psychotic subjects, who maintained in adulthood a near-random structure. In literature, monotonic asymptotic changes over time were remarkable: While lexical diversity, long-range recurrence and graph size increased away from near-randomness, short-range recurrence declined, from above to below random levels. Bronze Age texts are structurally similar to childish or psychotic discourses, but subsequent texts converge abruptly to the healthy adult pattern around the onset of the Axial Age (800-200 BC), a period of pivotal cultural change. Thus, individually as well as historically, discourse maturation increases the range of word recurrence away from randomness.
Tasks
Published	2016-12-27
URL	http://arxiv.org/abs/1612.09268v1
PDF	http://arxiv.org/pdf/1612.09268v1.pdf
PWC	https://paperswithcode.com/paper/the-ontogeny-of-discourse-structure-mimics
Repo
Framework

Learning Shallow Detection Cascades for Wearable Sensor-Based Mobile Health Applications


Title	Learning Shallow Detection Cascades for Wearable Sensor-Based Mobile Health Applications
Authors	Hamid Dadkhahi, Nazir Saleheen, Santosh Kumar, Benjamin Marlin
Abstract	The field of mobile health aims to leverage recent advances in wearable on-body sensing technology and smart phone computing capabilities to develop systems that can monitor health states and deliver just-in-time adaptive interventions. However, existing work has largely focused on analyzing collected data in the off-line setting. In this paper, we propose a novel approach to learning shallow detection cascades developed explicitly for use in a real-time wearable-phone or wearable-phone-cloud systems. We apply our approach to the problem of cigarette smoking detection from a combination of wrist-worn actigraphy data and respiration chest band data using two and three stage cascades.
Tasks
Published	2016-07-13
URL	http://arxiv.org/abs/1607.03730v1
PDF	http://arxiv.org/pdf/1607.03730v1.pdf
PWC	https://paperswithcode.com/paper/learning-shallow-detection-cascades-for
Repo
Framework

Coalition-based Planning of Military Operations: Adversarial Reasoning Algorithms in an Integrated Decision Aid


Title	Coalition-based Planning of Military Operations: Adversarial Reasoning Algorithms in an Integrated Decision Aid
Authors	Larry Ground, Alexander Kott, Ray Budd
Abstract	Use of knowledge-based planning tools can help alleviate the challenges of planning a complex operation by a coalition of diverse parties in an adversarial environment. We explore these challenges and potential contributions of knowledge-based tools using as an example the CADET system, a knowledge-based tool capable of producing automatically (or with human guidance) battle plans with realistic degree of detail and complexity. In ongoing experiments, it compared favorably with human planners. Interleaved planning, scheduling, routing, attrition and consumption processes comprise the computational approach of this tool. From the coalition operations perspective, such tools offer an important aid in rapid synchronization of assets and actions of heterogeneous assets belonging to multiple organizations, potentially with distinct doctrine and rules of engagement. In this paper, we discuss the functionality of the tool, provide a brief overview of the technical approach and experimental results, and outline the potential value of such tools.
Tasks
Published	2016-01-22
URL	http://arxiv.org/abs/1601.06069v1
PDF	http://arxiv.org/pdf/1601.06069v1.pdf
PWC	https://paperswithcode.com/paper/coalition-based-planning-of-military
Repo
Framework

Decentralized Frank-Wolfe Algorithm for Convex and Non-convex Problems


Title	Decentralized Frank-Wolfe Algorithm for Convex and Non-convex Problems
Authors	Hoi-To Wai, Jean Lafond, Anna Scaglione, Eric Moulines
Abstract	Decentralized optimization algorithms have received much attention due to the recent advances in network information processing. However, conventional decentralized algorithms based on projected gradient descent are incapable of handling high dimensional constrained problems, as the projection step becomes computationally prohibitive to compute. To address this problem, this paper adopts a projection-free optimization approach, a.k.a.~the Frank-Wolfe (FW) or conditional gradient algorithm. We first develop a decentralized FW (DeFW) algorithm from the classical FW algorithm. The convergence of the proposed algorithm is studied by viewing the decentralized algorithm as an inexact FW algorithm. Using a diminishing step size rule and letting $t$ be the iteration number, we show that the DeFW algorithm’s convergence rate is ${\cal O}(1/t)$ for convex objectives; is ${\cal O}(1/t^2)$ for strongly convex objectives with the optimal solution in the interior of the constraint set; and is ${\cal O}(1/\sqrt{t})$ towards a stationary point for smooth but non-convex objectives. We then show that a consensus-based DeFW algorithm meets the above guarantees with two communication rounds per iteration. Furthermore, we demonstrate the advantages of the proposed DeFW algorithm on low-complexity robust matrix completion and communication efficient sparse learning. Numerical results on synthetic and real data are presented to support our findings.
Tasks	Matrix Completion, Sparse Learning
Published	2016-12-05
URL	http://arxiv.org/abs/1612.01216v3
PDF	http://arxiv.org/pdf/1612.01216v3.pdf
PWC	https://paperswithcode.com/paper/decentralized-frank-wolfe-algorithm-for
Repo
Framework

Mutual Exclusivity Loss for Semi-Supervised Deep Learning


Title	Mutual Exclusivity Loss for Semi-Supervised Deep Learning
Authors	Mehdi Sajjadi, Mehran Javanmardi, Tolga Tasdizen
Abstract	In this paper we consider the problem of semi-supervised learning with deep Convolutional Neural Networks (ConvNets). Semi-supervised learning is motivated on the observation that unlabeled data is cheap and can be used to improve the accuracy of classifiers. In this paper we propose an unsupervised regularization term that explicitly forces the classifier’s prediction for multiple classes to be mutually-exclusive and effectively guides the decision boundary to lie on the low density space between the manifolds corresponding to different classes of data. Our proposed approach is general and can be used with any backpropagation-based learning method. We show through different experiments that our method can improve the object recognition performance of ConvNets using unlabeled data.
Tasks	Object Recognition
Published	2016-06-09
URL	http://arxiv.org/abs/1606.03141v1
PDF	http://arxiv.org/pdf/1606.03141v1.pdf
PWC	https://paperswithcode.com/paper/mutual-exclusivity-loss-for-semi-supervised
Repo
Framework

Pareto Efficient Multi Objective Optimization for Local Tuning of Analogy Based Estimation


Title	Pareto Efficient Multi Objective Optimization for Local Tuning of Analogy Based Estimation
Authors	Mohammad Azzeh, Ali Bou Nassif, Shadi Banitaan, Fadi Almasalha
Abstract	Analogy Based Effort Estimation (ABE) is one of the prominent methods for software effort estimation. The fundamental concept of ABE is closer to the mentality of expert estimation but with an automated procedure in which the final estimate is generated by reusing similar historical projects. The main key issue when using ABE is how to adapt the effort of the retrieved nearest neighbors. The adaptation process is an essential part of ABE to generate more successful accurate estimation based on tuning the selected raw solutions, using some adaptation strategy. In this study we show that there are three interrelated decision variables that have great impact on the success of adaptation method: (1) number of nearest analogies (k), (2) optimum feature set needed for adaptation, and (3) adaptation weights. To find the right decision regarding these variables, one need to study all possible combinations and evaluate them individually to select the one that can improve all prediction evaluation measures. The existing evaluation measures usually behave differently, presenting sometimes opposite trends in evaluating prediction methods. This means that changing one decision variable could improve one evaluation measure while it is decreasing the others. Therefore, the main theme of this research is how to come up with best decision variables that improve adaptation strategy and thus, the overall evaluation measures without degrading the others. The impact of these decisions together has not been investigated before, therefore we propose to view the building of adaptation procedure as a multi-objective optimization problem. The Particle Swarm Optimization Algorithm (PSO) is utilized to find the optimum solutions for such decision variables based on optimizing multiple evaluation measures
Tasks
Published	2016-11-29
URL	http://arxiv.org/abs/1701.01675v1
PDF	http://arxiv.org/pdf/1701.01675v1.pdf
PWC	https://paperswithcode.com/paper/pareto-efficient-multi-objective-optimization
Repo
Framework