May 6, 2019

3194 words 15 mins read

Paper Group ANR 157

Hierarchical Partitioning of the Output Space in Multi-label Data. Barzilai-Borwein Step Size for Stochastic Gradient Descent. Funnel Libraries for Real-Time Robust Feedback Motion Planning. Difficulty Adjustable and Scalable Constrained Multi-objective Test Problem Toolkit. Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Resu …

Hierarchical Partitioning of the Output Space in Multi-label Data


Title	Hierarchical Partitioning of the Output Space in Multi-label Data
Authors	Yannis Papanikolaou, Ioannis Katakis, Grigorios Tsoumakas
Abstract	Hierarchy Of Multi-label classifiers (HOMER) is a multi-label learning algorithm that breaks the initial learning task to several, easier sub-tasks by first constructing a hierarchy of labels from a given label set and secondly employing a given base multi-label classifier (MLC) to the resulting sub-problems. The primary goal is to effectively address class imbalance and scalability issues that often arise in real-world multi-label classification problems. In this work, we present the general setup for a HOMER model and a simple extension of the algorithm that is suited for MLCs that output rankings. Furthermore, we provide a detailed analysis of the properties of the algorithm, both from an aspect of effectiveness and computational complexity. A secondary contribution involves the presentation of a balanced variant of the k means algorithm, which serves in the first step of the label hierarchy construction. We conduct extensive experiments on six real-world datasets, studying empirically HOMER’s parameters and providing examples of instantiations of the algorithm with different clustering approaches and MLCs, The empirical results demonstrate a significant improvement over the given base MLC.
Tasks	Multi-Label Classification, Multi-Label Learning
Published	2016-12-19
URL	http://arxiv.org/abs/1612.06083v1
PDF	http://arxiv.org/pdf/1612.06083v1.pdf
PWC	https://paperswithcode.com/paper/hierarchical-partitioning-of-the-output-space
Repo
Framework

Barzilai-Borwein Step Size for Stochastic Gradient Descent


Title	Barzilai-Borwein Step Size for Stochastic Gradient Descent
Authors	Conghui Tan, Shiqian Ma, Yu-Hong Dai, Yuqiu Qian
Abstract	One of the major issues in stochastic gradient descent (SGD) methods is how to choose an appropriate step size while running the algorithm. Since the traditional line search technique does not apply for stochastic optimization algorithms, the common practice in SGD is either to use a diminishing step size, or to tune a fixed step size by hand, which can be time consuming in practice. In this paper, we propose to use the Barzilai-Borwein (BB) method to automatically compute step sizes for SGD and its variant: stochastic variance reduced gradient (SVRG) method, which leads to two algorithms: SGD-BB and SVRG-BB. We prove that SVRG-BB converges linearly for strongly convex objective functions. As a by-product, we prove the linear convergence result of SVRG with Option I proposed in [10], whose convergence result is missing in the literature. Numerical experiments on standard data sets show that the performance of SGD-BB and SVRG-BB is comparable to and sometimes even better than SGD and SVRG with best-tuned step sizes, and is superior to some advanced SGD variants.
Tasks	Stochastic Optimization
Published	2016-05-13
URL	http://arxiv.org/abs/1605.04131v2
PDF	http://arxiv.org/pdf/1605.04131v2.pdf
PWC	https://paperswithcode.com/paper/barzilai-borwein-step-size-for-stochastic
Repo
Framework

Funnel Libraries for Real-Time Robust Feedback Motion Planning


Title	Funnel Libraries for Real-Time Robust Feedback Motion Planning
Authors	Anirudha Majumdar, Russ Tedrake
Abstract	We consider the problem of generating motion plans for a robot that are guaranteed to succeed despite uncertainty in the environment, parametric model uncertainty, and disturbances. Furthermore, we consider scenarios where these plans must be generated in real-time, because constraints such as obstacles in the environment may not be known until they are perceived (with a noisy sensor) at runtime. Our approach is to pre-compute a library of “funnels” along different maneuvers of the system that the state is guaranteed to remain within (despite bounded disturbances) when the feedback controller corresponding to the maneuver is executed. We leverage powerful computational machinery from convex optimization (sums-of-squares programming in particular) to compute these funnels. The resulting funnel library is then used to sequentially compose motion plans at runtime while ensuring the safety of the robot. A major advantage of the work presented here is that by explicitly taking into account the effect of uncertainty, the robot can evaluate motion plans based on how vulnerable they are to disturbances. We demonstrate and validate our method using extensive hardware experiments on a small fixed-wing airplane avoiding obstacles at high speed (~12 mph), along with thorough simulation experiments of ground vehicle and quadrotor models navigating through cluttered environments. To our knowledge, these demonstrations constitute one of the first examples of provably safe and robust control for robotic systems with complex nonlinear dynamics that need to plan in real-time in environments with complex geometric constraints.
Tasks	Motion Planning
Published	2016-01-15
URL	http://arxiv.org/abs/1601.04037v3
PDF	http://arxiv.org/pdf/1601.04037v3.pdf
PWC	https://paperswithcode.com/paper/funnel-libraries-for-real-time-robust
Repo
Framework

Difficulty Adjustable and Scalable Constrained Multi-objective Test Problem Toolkit


Title	Difficulty Adjustable and Scalable Constrained Multi-objective Test Problem Toolkit
Authors	Zhun Fan, Wenji Li, Xinye Cai, Hui Li, Caimin Wei, Qingfu Zhang, Kalyanmoy Deb, Erik D. Goodman
Abstract	Multi-objective evolutionary algorithms (MOEAs) have progressed significantly in recent decades, but most of them are designed to solve unconstrained multi-objective optimization problems. In fact, many real-world multi-objective problems contain a number of constraints. To promote research on constrained multi-objective optimization, we first propose a problem classification scheme with three primary types of difficulty, which reflect various types of challenges presented by real-world optimization problems, in order to characterize the constraint functions in constrained multi-objective optimization problems (CMOPs). These are feasibility-hardness, convergence-hardness and diversity-hardness. We then develop a general toolkit to construct difficulty-adjustable and scalable CMOPs (DAS-CMOPs, or DAS-CMaOPs when the number of objectives is greater than three) with three types of parameterized constraint functions developed to capture the three proposed types of difficulty. Based on this toolkit, we suggest nine difficulty-adjustable and scalable CMOPs and nine CMaOPs. The experimental results reveal that mechanisms in MOEA/D-CDP may be more effective in solving convergence-hard DAS-CMOPs, while mechanisms of NSGA-II-CDP may be more effective in solving DAS-CMOPs with simultaneous diversity-, feasibility- and convergence-hardness. Mechanisms in C-NSGA-III may be more effective in solving feasibility-hard CMaOPs, while mechanisms of C-MOEA/DD may be more effective in solving CMaOPs with convergence-hardness. In addition, none of them can solve these problems efficiently, which stimulates us to continue to develop new CMOEAs and CMaOEAs to solve the suggested DAS-CMOPs and DAS-CMaOPs.
Tasks
Published	2016-12-21
URL	https://arxiv.org/abs/1612.07603v3
PDF	https://arxiv.org/pdf/1612.07603v3.pdf
PWC	https://paperswithcode.com/paper/difficulty-adjustable-and-scalable
Repo
Framework

Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences


Title	Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences
Authors	Chi Jin, Yuchen Zhang, Sivaraman Balakrishnan, Martin J. Wainwright, Michael Jordan
Abstract	We provide two fundamental results on the population (infinite-sample) likelihood function of Gaussian mixture models with $M \geq 3$ components. Our first main result shows that the population likelihood function has bad local maxima even in the special case of equally-weighted mixtures of well-separated and spherical Gaussians. We prove that the log-likelihood value of these bad local maxima can be arbitrarily worse than that of any global optimum, thereby resolving an open question of Srebro (2007). Our second main result shows that the EM algorithm (or a first-order variant of it) with random initialization will converge to bad critical points with probability at least $1-e^{-\Omega(M)}$. We further establish that a first-order variant of EM will not converge to strict saddle points almost surely, indicating that the poor performance of the first-order method can be attributed to the existence of bad local maxima rather than bad saddle points. Overall, our results highlight the necessity of careful initialization when using the EM algorithm in practice, even when applied in highly favorable settings.
Tasks
Published	2016-09-04
URL	http://arxiv.org/abs/1609.00978v1
PDF	http://arxiv.org/pdf/1609.00978v1.pdf
PWC	https://paperswithcode.com/paper/local-maxima-in-the-likelihood-of-gaussian
Repo
Framework

Learning Deep Representations Using Convolutional Auto-encoders with Symmetric Skip Connections


Title	Learning Deep Representations Using Convolutional Auto-encoders with Symmetric Skip Connections
Authors	Jianfeng Dong, Xiao-Jiao Mao, Chunhua Shen, Yu-Bin Yang
Abstract	Unsupervised pre-training was a critical technique for training deep neural networks years ago. With sufficient labeled data and modern training techniques, it is possible to train very deep neural networks from scratch in a purely supervised manner nowadays. However, unlabeled data is easier to obtain and usually of very large scale. How to make use of them better to help supervised learning is still a well-valued topic. In this paper, we investigate convolutional denoising auto-encoders to show that unsupervised pre-training can still improve the performance of high-level image related tasks such as image classification and semantic segmentation. The architecture we use is a convolutional auto-encoder network with symmetric shortcut connections. We empirically show that symmetric shortcut connections are very important for learning abstract representations via image reconstruction. When no extra unlabeled data are available, unsupervised pre-training with our network can regularize the supervised training and therefore lead to better generalization performance. With the help of unsupervised pre-training, our method achieves very competitive results in image classification using very simple all-convolution networks. When labeled data are limited but extra unlabeled data are available, our method achieves good results in several semi-supervised learning tasks.
Tasks	Denoising, Image Classification, Image Reconstruction, Semantic Segmentation
Published	2016-11-28
URL	http://arxiv.org/abs/1611.09119v2
PDF	http://arxiv.org/pdf/1611.09119v2.pdf
PWC	https://paperswithcode.com/paper/learning-deep-representations-using
Repo
Framework

Fast and Accurate Algorithm for Eye Localization for Gaze Tracking in Low Resolution Images


Title	Fast and Accurate Algorithm for Eye Localization for Gaze Tracking in Low Resolution Images
Authors	Anjith George, Aurobinda Routray
Abstract	Iris centre localization in low-resolution visible images is a challenging problem in computer vision community due to noise, shadows, occlusions, pose variations, eye blinks, etc. This paper proposes an efficient method for determining iris centre in low-resolution images in the visible spectrum. Even low-cost consumer-grade webcams can be used for gaze tracking without any additional hardware. A two-stage algorithm is proposed for iris centre localization. The proposed method uses geometrical characteristics of the eye. In the first stage, a fast convolution based approach is used for obtaining the coarse location of iris centre (IC). The IC location is further refined in the second stage using boundary tracing and ellipse fitting. The algorithm has been evaluated in public databases like BioID, Gi4E and is found to outperform the state of the art methods.
Tasks
Published	2016-05-17
URL	http://arxiv.org/abs/1605.05272v1
PDF	http://arxiv.org/pdf/1605.05272v1.pdf
PWC	https://paperswithcode.com/paper/fast-and-accurate-algorithm-for-eye
Repo
Framework

Semi-Automated Annotation of Discrete States in Large Video Datasets


Title	Semi-Automated Annotation of Discrete States in Large Video Datasets
Authors	Lex Fridman, Bryan Reimer
Abstract	We propose a framework for semi-automated annotation of video frames where the video is of an object that at any point in time can be labeled as being in one of a finite number of discrete states. A Hidden Markov Model (HMM) is used to model (1) the behavior of the underlying object and (2) the noisy observation of its state through an image processing algorithm. The key insight of this approach is that the annotation of frame-by-frame video can be reduced from a problem of labeling every single image to a problem of detecting a transition between states of the underlying objected being recording on video. The performance of the framework is evaluated on a driver gaze classification dataset composed of 16,000,000 images that were fully annotated over 6,000 hours of direct manual annotation labor. On this dataset, we achieve a 13x reduction in manual annotation for an average accuracy of 99.1% and a 84x reduction for an average accuracy of 91.2%.
Tasks
Published	2016-12-03
URL	http://arxiv.org/abs/1612.01035v1
PDF	http://arxiv.org/pdf/1612.01035v1.pdf
PWC	https://paperswithcode.com/paper/semi-automated-annotation-of-discrete-states
Repo
Framework

Spectral algorithms for tensor completion


Title	Spectral algorithms for tensor completion
Authors	Andrea Montanari, Nike Sun
Abstract	In the tensor completion problem, one seeks to estimate a low-rank tensor based on a random sample of revealed entries. In terms of the required sample size, earlier work revealed a large gap between estimation with unbounded computational resources (using, for instance, tensor nuclear norm minimization) and polynomial-time algorithms. Among the latter, the best statistical guarantees have been proved, for third-order tensors, using the sixth level of the sum-of-squares (SOS) semidefinite programming hierarchy (Barak and Moitra, 2014). However, the SOS approach does not scale well to large problem instances. By contrast, spectral methods — based on unfolding or matricizing the tensor — are attractive for their low complexity, but have been believed to require a much larger sample size. This paper presents two main contributions. First, we propose a new unfolding-based method, which outperforms naive ones for symmetric $k$-th order tensors of rank $r$. For this result we make a study of singular space estimation for partially revealed matrices of large aspect ratio, which may be of independent interest. For third-order tensors, our algorithm matches the SOS method in terms of sample size (requiring about $rd^{3/2}$ revealed entries), subject to a worse rank condition ($r\ll d^{3/4}$ rather than $r\ll d^{3/2}$). We complement this result with a different spectral algorithm for third-order tensors in the overcomplete ($r\ge d$) regime. Under a random model, this second approach succeeds in estimating tensors of rank $d\le r \ll d^{3/2}$ from about $rd^{3/2}$ revealed entries.
Tasks
Published	2016-12-23
URL	http://arxiv.org/abs/1612.07866v1
PDF	http://arxiv.org/pdf/1612.07866v1.pdf
PWC	https://paperswithcode.com/paper/spectral-algorithms-for-tensor-completion
Repo
Framework

A Unified Convex Surrogate for the Schatten-$p$ Norm


Title	A Unified Convex Surrogate for the Schatten-$p$ Norm
Authors	Chen Xu, Zhouchen Lin, Hongbin Zha
Abstract	The Schatten-$p$ norm ($0<p<1$) has been widely used to replace the nuclear norm for better approximating the rank function. However, existing methods are either 1) not scalable for large scale problems due to relying on singular value decomposition (SVD) in every iteration, or 2) specific to some $p$ values, e.g., $1/2$, and $2/3$. In this paper, we show that for any $p$, $p_1$, and $p_2 >0$ satisfying $1/p=1/p_1+1/p_2$, there is an equivalence between the Schatten-$p$ norm of one matrix and the Schatten-$p_1$ and the Schatten-$p_2$ norms of its two factor matrices. We further extend the equivalence to multiple factor matrices and show that all the factor norms can be convex and smooth for any $p>0$. In contrast, the original Schatten-$p$ norm for $0<p<1$ is non-convex and non-smooth. As an example we conduct experiments on matrix completion. To utilize the convexity of the factor matrix norms, we adopt the accelerated proximal alternating linearized minimization algorithm and establish its sequence convergence. Experiments on both synthetic and real datasets exhibit its superior performance over the state-of-the-art methods. Its speed is also highly competitive.
Tasks	Matrix Completion
Published	2016-11-25
URL	http://arxiv.org/abs/1611.08372v1
PDF	http://arxiv.org/pdf/1611.08372v1.pdf
PWC	https://paperswithcode.com/paper/a-unified-convex-surrogate-for-the-schatten-p
Repo
Framework

Large-Scale Strategic Games and Adversarial Machine Learning


Title	Large-Scale Strategic Games and Adversarial Machine Learning
Authors	Tansu Alpcan, Benjamin I. P. Rubinstein, Christopher Leckie
Abstract	Decision making in modern large-scale and complex systems such as communication networks, smart electricity grids, and cyber-physical systems motivate novel game-theoretic approaches. This paper investigates big strategic (non-cooperative) games where a finite number of individual players each have a large number of continuous decision variables and input data points. Such high-dimensional decision spaces and big data sets lead to computational challenges, relating to efforts in non-linear optimization scaling up to large systems of variables. In addition to these computational challenges, real-world players often have limited information about their preference parameters due to the prohibitive cost of identifying them or due to operating in dynamic online settings. The challenge of limited information is exacerbated in high dimensions and big data sets. Motivated by both computational and information limitations that constrain the direct solution of big strategic games, our investigation centers around reductions using linear transformations such as random projection methods and their effect on Nash equilibrium solutions. Specific analytical results are presented for quadratic games and approximations. In addition, an adversarial learning game is presented where random projection and sampling schemes are investigated.
Tasks	Decision Making
Published	2016-09-21
URL	http://arxiv.org/abs/1609.06438v1
PDF	http://arxiv.org/pdf/1609.06438v1.pdf
PWC	https://paperswithcode.com/paper/large-scale-strategic-games-and-adversarial
Repo
Framework

Siamese CBOW: Optimizing Word Embeddings for Sentence Representations


Title	Siamese CBOW: Optimizing Word Embeddings for Sentence Representations
Authors	Tom Kenter, Alexey Borisov, Maarten de Rijke
Abstract	We present the Siamese Continuous Bag of Words (Siamese CBOW) model, a neural network for efficient estimation of high-quality sentence embeddings. Averaging the embeddings of words in a sentence has proven to be a surprisingly successful and efficient way of obtaining sentence embeddings. However, word embeddings trained with the methods currently available are not optimized for the task of sentence representation, and, thus, likely to be suboptimal. Siamese CBOW handles this problem by training word embeddings directly for the purpose of being averaged. The underlying neural network learns word embeddings by predicting, from a sentence representation, its surrounding sentences. We show the robustness of the Siamese CBOW model by evaluating it on 20 datasets stemming from a wide variety of sources.
Tasks	Sentence Embeddings, Word Embeddings
Published	2016-06-15
URL	http://arxiv.org/abs/1606.04640v1
PDF	http://arxiv.org/pdf/1606.04640v1.pdf
PWC	https://paperswithcode.com/paper/siamese-cbow-optimizing-word-embeddings-for
Repo
Framework

Neural Associative Memory for Dual-Sequence Modeling


Title	Neural Associative Memory for Dual-Sequence Modeling
Authors	Dirk Weissenborn
Abstract	Many important NLP problems can be posed as dual-sequence or sequence-to-sequence modeling tasks. Recent advances in building end-to-end neural architectures have been highly successful in solving such tasks. In this work we propose a new architecture for dual-sequence modeling that is based on associative memory. We derive AM-RNNs, a recurrent associative memory (AM) which augments generic recurrent neural networks (RNN). This architecture is extended to the Dual AM-RNN which operates on two AMs at once. Our models achieve very competitive results on textual entailment. A qualitative analysis demonstrates that long range dependencies between source and target-sequence can be bridged effectively using Dual AM-RNNs. However, an initial experiment on auto-encoding reveals that these benefits are not exploited by the system when learning to solve sequence-to-sequence tasks which indicates that additional supervision or regularization is needed.
Tasks	Natural Language Inference
Published	2016-06-13
URL	http://arxiv.org/abs/1606.03864v2
PDF	http://arxiv.org/pdf/1606.03864v2.pdf
PWC	https://paperswithcode.com/paper/neural-associative-memory-for-dual-sequence
Repo
Framework

Critical Points for Two-view Triangulation


Title	Critical Points for Two-view Triangulation
Authors	Hon-Leung Lee
Abstract	Two-view triangulation is a problem of minimizing a quadratic polynomial under an equality constraint. We derive a polynomial that encodes the local minimizers of this problem using the theory of Lagrange multipliers. This offers a simpler derivation of the critical points that are given in Hartley-Sturm [6].
Tasks
Published	2016-08-19
URL	http://arxiv.org/abs/1608.05512v1
PDF	http://arxiv.org/pdf/1608.05512v1.pdf
PWC	https://paperswithcode.com/paper/critical-points-for-two-view-triangulation
Repo
Framework

Viziometrics: Analyzing Visual Information in the Scientific Literature


Title	Viziometrics: Analyzing Visual Information in the Scientific Literature
Authors	Po-shen Lee, Jevin D. West, Bill Howe
Abstract	Scientific results are communicated visually in the literature through diagrams, visualizations, and photographs. These information-dense objects have been largely ignored in bibliometrics and scientometrics studies when compared to citations and text. In this paper, we use techniques from computer vision and machine learning to classify more than 8 million figures from PubMed into 5 figure types and study the resulting patterns of visual information as they relate to impact. We find that the distribution of figures and figure types in the literature has remained relatively constant over time, but can vary widely across field and topic. Remarkably, we find a significant correlation between scientific impact and the use of visual information, where higher impact papers tend to include more diagrams, and to a lesser extent more plots and photographs. To explore these results and other ways of extracting this visual information, we have built a visual browser to illustrate the concept and explore design alternatives for supporting viziometric analysis and organizing visual information. We use these results to articulate a new research agenda – viziometrics – to study the organization and presentation of visual information in the scientific literature.
Tasks
Published	2016-05-16
URL	http://arxiv.org/abs/1605.04951v2
PDF	http://arxiv.org/pdf/1605.04951v2.pdf
PWC	https://paperswithcode.com/paper/viziometrics-analyzing-visual-information-in
Repo
Framework