Paper Group ANR 544
Recovery guarantee of weighted low-rank approximation via alternating minimization. Practical Algorithms for Learning Near-Isometric Linear Embeddings. Model selection consistency from the perspective of generalization ability and VC theory with an application to Lasso. Feedback Networks. Regression Trees and Random forest based feature selection f …
Recovery guarantee of weighted low-rank approximation via alternating minimization
| Title | Recovery guarantee of weighted low-rank approximation via alternating minimization |
| Authors | Yuanzhi Li, Yingyu Liang, Andrej Risteski |
| Abstract | Many applications require recovering a ground truth low-rank matrix from noisy observations of the entries, which in practice is typically formulated as a weighted low-rank approximation problem and solved by non-convex optimization heuristics such as alternating minimization. In this paper, we provide provable recovery guarantee of weighted low-rank via a simple alternating minimization algorithm. In particular, for a natural class of matrices and weights and without any assumption on the noise, we bound the spectral norm of the difference between the recovered matrix and the ground truth, by the spectral norm of the weighted noise plus an additive error that decreases exponentially with the number of rounds of alternating minimization, from either initialization by SVD or, more importantly, random initialization. These provide the first theoretical results for weighted low-rank via alternating minimization with non-binary deterministic weights, significantly generalizing those for matrix completion, the special case with binary weights, since our assumptions are similar or weaker than those made in existing works. Furthermore, this is achieved by a very simple algorithm that improves the vanilla alternating minimization with a simple clipping step. The key technical challenge is that under non-binary deterministic weights, na"ive alternating steps will destroy the incoherence and spectral properties of the intermediate solutions, which are needed for making progress towards the ground truth. We show that the properties only need to hold in an average sense and can be achieved by the clipping step. We further provide an alternating algorithm that uses a whitening step that keeps the properties via SDP and Rademacher rounding and thus requires weaker assumptions. This technique can potentially be applied in some other applications and is of independent interest. |
| Tasks | Matrix Completion |
| Published | 2016-02-06 |
| URL | http://arxiv.org/abs/1602.02262v2 |
| http://arxiv.org/pdf/1602.02262v2.pdf | |
| PWC | https://paperswithcode.com/paper/recovery-guarantee-of-weighted-low-rank |
| Repo | |
| Framework | |
Practical Algorithms for Learning Near-Isometric Linear Embeddings
| Title | Practical Algorithms for Learning Near-Isometric Linear Embeddings |
| Authors | Jerry Luo, Kayla Shapiro, Hao-Jun Michael Shi, Qi Yang, Kan Zhu |
| Abstract | We propose two practical non-convex approaches for learning near-isometric, linear embeddings of finite sets of data points. Given a set of training points $\mathcal{X}$, we consider the secant set $S(\mathcal{X})$ that consists of all pairwise difference vectors of $\mathcal{X}$, normalized to lie on the unit sphere. The problem can be formulated as finding a symmetric and positive semi-definite matrix $\boldsymbol{\Psi}$ that preserves the norms of all the vectors in $S(\mathcal{X})$ up to a distortion parameter $\delta$. Motivated by non-negative matrix factorization, we reformulate our problem into a Frobenius norm minimization problem, which is solved by the Alternating Direction Method of Multipliers (ADMM) and develop an algorithm, FroMax. Another method solves for a projection matrix $\boldsymbol{\Psi}$ by minimizing the restricted isometry property (RIP) directly over the set of symmetric, postive semi-definite matrices. Applying ADMM and a Moreau decomposition on a proximal mapping, we develop another algorithm, NILE-Pro, for dimensionality reduction. FroMax is shown to converge faster for smaller $\delta$ while NILE-Pro converges faster for larger $\delta$. Both non-convex approaches are then empirically demonstrated to be more computationally efficient than prior convex approaches for a number of applications in machine learning and signal processing. |
| Tasks | Dimensionality Reduction |
| Published | 2016-01-01 |
| URL | http://arxiv.org/abs/1601.00062v2 |
| http://arxiv.org/pdf/1601.00062v2.pdf | |
| PWC | https://paperswithcode.com/paper/practical-algorithms-for-learning-near |
| Repo | |
| Framework | |
Model selection consistency from the perspective of generalization ability and VC theory with an application to Lasso
| Title | Model selection consistency from the perspective of generalization ability and VC theory with an application to Lasso |
| Authors | Ning Xu, Jian Hong, Timothy C. G. Fisher |
| Abstract | Model selection is difficult to analyse yet theoretically and empirically important, especially for high-dimensional data analysis. Recently the least absolute shrinkage and selection operator (Lasso) has been applied in the statistical and econometric literature. Consis- tency of Lasso has been established under various conditions, some of which are difficult to verify in practice. In this paper, we study model selection from the perspective of generalization ability, under the framework of structural risk minimization (SRM) and Vapnik-Chervonenkis (VC) theory. The approach emphasizes the balance between the in-sample and out-of-sample fit, which can be achieved by using cross-validation to select a penalty on model complexity. We show that an exact relationship exists between the generalization ability of a model and model selection consistency. By implementing SRM and the VC inequality, we show that Lasso is L2-consistent for model selection under assumptions similar to those imposed on OLS. Furthermore, we derive a probabilistic bound for the distance between the penalized extremum estimator and the extremum estimator without penalty, which is dominated by overfitting. We also propose a new measurement of overfitting, GR2, based on generalization ability, that converges to zero if model selection is consistent. Using simulations, we demonstrate that the proposed CV-Lasso algorithm performs well in terms of model selection and overfitting control. |
| Tasks | Model Selection |
| Published | 2016-06-01 |
| URL | http://arxiv.org/abs/1606.00142v1 |
| http://arxiv.org/pdf/1606.00142v1.pdf | |
| PWC | https://paperswithcode.com/paper/model-selection-consistency-from-the |
| Repo | |
| Framework | |
Feedback Networks
| Title | Feedback Networks |
| Authors | Amir R. Zamir, Te-Lin Wu, Lin Sun, William Shen, Jitendra Malik, Silvio Savarese |
| Abstract | Currently, the most successful learning models in computer vision are based on learning successive representations followed by a decision layer. This is usually actualized through feedforward multilayer neural networks, e.g. ConvNets, where each layer forms one of such successive representations. However, an alternative that can achieve the same goal is a feedback based approach in which the representation is formed in an iterative manner based on a feedback received from previous iteration’s output. We establish that a feedback based approach has several fundamental advantages over feedforward: it enables making early predictions at the query time, its output naturally conforms to a hierarchical structure in the label space (e.g. a taxonomy), and it provides a new basis for Curriculum Learning. We observe that feedback networks develop a considerably different representation compared to feedforward counterparts, in line with the aforementioned advantages. We put forth a general feedback based learning architecture with the endpoint results on par or better than existing feedforward networks with the addition of the above advantages. We also investigate several mechanisms in feedback architectures (e.g. skip connections in time) and design choices (e.g. feedback length). We hope this study offers new perspectives in quest for more natural and practical learning models. |
| Tasks | |
| Published | 2016-12-30 |
| URL | http://arxiv.org/abs/1612.09508v3 |
| http://arxiv.org/pdf/1612.09508v3.pdf | |
| PWC | https://paperswithcode.com/paper/feedback-networks |
| Repo | |
| Framework | |
Regression Trees and Random forest based feature selection for malaria risk exposure prediction
| Title | Regression Trees and Random forest based feature selection for malaria risk exposure prediction |
| Authors | Bienvenue Kouwayè |
| Abstract | This paper deals with prediction of anopheles number, the main vector of malaria risk, using environmental and climate variables. The variables selection is based on an automatic machine learning method using regression trees, and random forests combined with stratified two levels cross validation. The minimum threshold of variables importance is accessed using the quadratic distance of variables importance while the optimal subset of selected variables is used to perform predictions. Finally the results revealed to be qualitatively better, at the selection, the prediction , and the CPU time point of view than those obtained by GLM-Lasso method. |
| Tasks | Feature Selection, Malaria Risk Exposure Prediction |
| Published | 2016-06-24 |
| URL | http://arxiv.org/abs/1606.07578v1 |
| http://arxiv.org/pdf/1606.07578v1.pdf | |
| PWC | https://paperswithcode.com/paper/regression-trees-and-random-forest-based |
| Repo | |
| Framework | |
Optimal Management of Naturally Regenerating Uneven-aged Forests
| Title | Optimal Management of Naturally Regenerating Uneven-aged Forests |
| Authors | Ankur Sinha, Janne Rämö, Pekka Malo, Markku Kallio, Olli Tahvonen |
| Abstract | A shift from even-aged forest management to uneven-aged management practices leads to a problem rather different from the existing straightforward practice that follows a rotation cycle of artificial regeneration, thinning of inferior trees and a clearcut. A lack of realistic models and methods suggesting how to manage uneven-aged stands in a way that is economically viable and ecologically sustainable creates difficulties in adopting this new management practice. To tackle this problem, we make a two-fold contribution in this paper. The first contribution is the proposal of an algorithm that is able to handle a realistic uneven-aged stand management model that is otherwise computationally tedious and intractable. The model considered in this paper is an empirically estimated size-structured ecological model for uneven-aged spruce forests. The second contribution is on the sensitivity analysis of the forest model with respect to a number of important parameters. The analysis provides us an insight into the behavior of the uneven-aged forest model. |
| Tasks | |
| Published | 2016-08-17 |
| URL | http://arxiv.org/abs/1608.05109v1 |
| http://arxiv.org/pdf/1608.05109v1.pdf | |
| PWC | https://paperswithcode.com/paper/optimal-management-of-naturally-regenerating |
| Repo | |
| Framework | |
Building an Evaluation Scale using Item Response Theory
| Title | Building an Evaluation Scale using Item Response Theory |
| Authors | John P. Lalor, Hao Wu, Hong Yu |
| Abstract | Evaluation of NLP methods requires testing against a previously vetted gold-standard test set and reporting standard metrics (accuracy/precision/recall/F1). The current assumption is that all items in a given test set are equal with regards to difficulty and discriminating power. We propose Item Response Theory (IRT) from psychometrics as an alternative means for gold-standard test-set generation and NLP system evaluation. IRT is able to describe characteristics of individual items - their difficulty and discriminating power - and can account for these characteristics in its estimation of human intelligence or ability for an NLP task. In this paper, we demonstrate IRT by generating a gold-standard test set for Recognizing Textual Entailment. By collecting a large number of human responses and fitting our IRT model, we show that our IRT model compares NLP systems with the performance in a human population and is able to provide more insight into system performance than standard evaluation metrics. We show that a high accuracy score does not always imply a high IRT score, which depends on the item characteristics and the response pattern. |
| Tasks | Natural Language Inference |
| Published | 2016-05-28 |
| URL | http://arxiv.org/abs/1605.08889v2 |
| http://arxiv.org/pdf/1605.08889v2.pdf | |
| PWC | https://paperswithcode.com/paper/building-an-evaluation-scale-using-item |
| Repo | |
| Framework | |
Fast Semantic Image Segmentation with High Order Context and Guided Filtering
| Title | Fast Semantic Image Segmentation with High Order Context and Guided Filtering |
| Authors | Falong Shen, Gang Zeng |
| Abstract | This paper describes a fast and accurate semantic image segmentation approach that encodes not only the discriminative features from deep neural networks, but also the high-order context compatibility among adjacent objects as well as low level image features. We formulate the underlying problem as the conditional random field that embeds local feature extraction, clique potential construction, and guided filtering within the same framework, and provide an efficient coarse-to-fine solver. At the coarse level, we combine local feature representation and context interaction using a deep convolutional network, and directly learn the interaction from high order cliques with a message passing routine, avoiding time-consuming explicit graph inference for joint probability distribution. At the fine level, we introduce a guided filtering interpretation for the mean field algorithm, and achieve accurate object boundaries with 100+ faster than classic learning methods. The two parts are connected and jointly trained in an end-to-end fashion. Experimental results on Pascal VOC 2012 dataset have shown that the proposed algorithm outperforms the state-of-the-art, and that it achieves the rank 1 performance at the time of submission, both of which prove the effectiveness of this unified framework for semantic image segmentation. |
| Tasks | Semantic Segmentation |
| Published | 2016-05-13 |
| URL | http://arxiv.org/abs/1605.04068v1 |
| http://arxiv.org/pdf/1605.04068v1.pdf | |
| PWC | https://paperswithcode.com/paper/fast-semantic-image-segmentation-with-high |
| Repo | |
| Framework | |
Supervised Learning in Spiking Neural Networks for Precise Temporal Encoding
| Title | Supervised Learning in Spiking Neural Networks for Precise Temporal Encoding |
| Authors | Brian Gardner, André Grüning |
| Abstract | Precise spike timing as a means to encode information in neural networks is biologically supported, and is advantageous over frequency-based codes by processing input features on a much shorter time-scale. For these reasons, much recent attention has been focused on the development of supervised learning rules for spiking neural networks that utilise a temporal coding scheme. However, despite significant progress in this area, there still lack rules that have a theoretical basis, and yet can be considered biologically relevant. Here we examine the general conditions under which synaptic plasticity most effectively takes place to support the supervised learning of a precise temporal code. As part of our analysis we examine two spike-based learning methods: one of which relies on an instantaneous error signal to modify synaptic weights in a network (INST rule), and the other one on a filtered error signal for smoother synaptic weight modifications (FILT rule). We test the accuracy of the solutions provided by each rule with respect to their temporal encoding precision, and then measure the maximum number of input patterns they can learn to memorise using the precise timings of individual spikes as an indication of their storage capacity. Our results demonstrate the high performance of FILT in most cases, underpinned by the rule’s error-filtering mechanism, which is predicted to provide smooth convergence towards a desired solution during learning. We also find FILT to be most efficient at performing input pattern memorisations, and most noticeably when patterns are identified using spikes with sub-millisecond temporal precision. In comparison with existing work, we determine the performance of FILT to be consistent with that of the highly efficient E-learning Chronotron, but with the distinct advantage that FILT is also implementable as an online method for increased biological realism. |
| Tasks | |
| Published | 2016-01-14 |
| URL | http://arxiv.org/abs/1601.03649v2 |
| http://arxiv.org/pdf/1601.03649v2.pdf | |
| PWC | https://paperswithcode.com/paper/supervised-learning-in-spiking-neural |
| Repo | |
| Framework | |
Icon: An Interactive Approach to Train Deep Neural Networks for Segmentation of Neuronal Structures
| Title | Icon: An Interactive Approach to Train Deep Neural Networks for Segmentation of Neuronal Structures |
| Authors | Felix Gonda, Verena Kaynig, Ray Thouis, Daniel Haehn, Jeff Lichtman, Toufiq Parag, Hanspeter Pfister |
| Abstract | We present an interactive approach to train a deep neural network pixel classifier for the segmentation of neuronal structures. An interactive training scheme reduces the extremely tedious manual annotation task that is typically required for deep networks to perform well on image segmentation problems. Our proposed method employs a feedback loop that captures sparse annotations using a graphical user interface, trains a deep neural network based on recent and past annotations, and displays the prediction output to users in almost real-time. Our implementation of the algorithm also allows multiple users to provide annotations in parallel and receive feedback from the same classifier. Quick feedback on classifier performance in an interactive setting enables users to identify and label examples that are more important than others for segmentation purposes. Our experiments show that an interactively-trained pixel classifier produces better region segmentation results on Electron Microscopy (EM) images than those generated by a network of the same architecture trained offline on exhaustive ground-truth labels. |
| Tasks | Semantic Segmentation |
| Published | 2016-10-27 |
| URL | http://arxiv.org/abs/1610.09032v1 |
| http://arxiv.org/pdf/1610.09032v1.pdf | |
| PWC | https://paperswithcode.com/paper/icon-an-interactive-approach-to-train-deep |
| Repo | |
| Framework | |
On Robustness of Kernel Clustering
| Title | On Robustness of Kernel Clustering |
| Authors | Bowei Yan, Purnamrita Sarkar |
| Abstract | Clustering is one of the most important unsupervised problems in machine learning and statistics. Among many existing algorithms, kernel k-means has drawn much research attention due to its ability to find non-linear cluster boundaries and its inherent simplicity. There are two main approaches for kernel k-means: SVD of the kernel matrix and convex relaxations. Despite the attention kernel clustering has received both from theoretical and applied quarters, not much is known about robustness of the methods. In this paper we first introduce a semidefinite programming relaxation for the kernel clustering problem, then prove that under a suitable model specification, both the K-SVD and SDP approaches are consistent in the limit, albeit SDP is strongly consistent, i.e. achieves exact recovery, whereas K-SVD is weakly consistent, i.e. the fraction of misclassified nodes vanish. |
| Tasks | |
| Published | 2016-06-06 |
| URL | http://arxiv.org/abs/1606.01869v3 |
| http://arxiv.org/pdf/1606.01869v3.pdf | |
| PWC | https://paperswithcode.com/paper/on-robustness-of-kernel-clustering |
| Repo | |
| Framework | |
Deep Learning with Energy-efficient Binary Gradient Cameras
| Title | Deep Learning with Energy-efficient Binary Gradient Cameras |
| Authors | Suren Jayasuriya, Orazio Gallo, Jinwei Gu, Jan Kautz |
| Abstract | Power consumption is a critical factor for the deployment of embedded computer vision systems. We explore the use of computational cameras that directly output binary gradient images to reduce the portion of the power consumption allocated to image sensing. We survey the accuracy of binary gradient cameras on a number of computer vision tasks using deep learning. These include object recognition, head pose regression, face detection, and gesture recognition. We show that, for certain applications, accuracy can be on par or even better than what can be achieved on traditional images. We are also the first to recover intensity information from binary spatial gradient images–useful for applications with a human observer in the loop, such as surveillance. Our results, which we validate with a prototype binary gradient camera, point to the potential of gradient-based computer vision systems. |
| Tasks | Face Detection, Gesture Recognition, Object Recognition |
| Published | 2016-12-03 |
| URL | http://arxiv.org/abs/1612.00986v1 |
| http://arxiv.org/pdf/1612.00986v1.pdf | |
| PWC | https://paperswithcode.com/paper/deep-learning-with-energy-efficient-binary |
| Repo | |
| Framework | |
An ensemble diversity approach to supervised binary hashing
| Title | An ensemble diversity approach to supervised binary hashing |
| Authors | Miguel Á. Carreira-Perpiñán, Ramin Raziperchikolaei |
| Abstract | Binary hashing is a well-known approach for fast approximate nearest-neighbor search in information retrieval. Much work has focused on affinity-based objective functions involving the hash functions or binary codes. These objective functions encode neighborhood information between data points and are often inspired by manifold learning algorithms. They ensure that the hash functions differ from each other through constraints or penalty terms that encourage codes to be orthogonal or dissimilar across bits, but this couples the binary variables and complicates the already difficult optimization. We propose a much simpler approach: we train each hash function (or bit) independently from each other, but introduce diversity among them using techniques from classifier ensembles. Surprisingly, we find that not only is this faster and trivially parallelizable, but it also improves over the more complex, coupled objective function, and achieves state-of-the-art precision and recall in experiments with image retrieval. |
| Tasks | Image Retrieval, Information Retrieval |
| Published | 2016-02-04 |
| URL | http://arxiv.org/abs/1602.01557v1 |
| http://arxiv.org/pdf/1602.01557v1.pdf | |
| PWC | https://paperswithcode.com/paper/an-ensemble-diversity-approach-to-supervised |
| Repo | |
| Framework | |
Optimal Best Arm Identification with Fixed Confidence
| Title | Optimal Best Arm Identification with Fixed Confidence |
| Authors | Aurélien Garivier, Emilie Kaufmann |
| Abstract | We give a complete characterization of the complexity of best-arm identification in one-parameter bandit problems. We prove a new, tight lower bound on the sample complexity. We propose the `Track-and-Stop’ strategy, which we prove to be asymptotically optimal. It consists in a new sampling rule (which tracks the optimal proportions of arm draws highlighted by the lower bound) and in a stopping rule named after Chernoff, for which we give a new analysis. | |
| Tasks | |
| Published | 2016-02-15 |
| URL | http://arxiv.org/abs/1602.04589v2 |
| http://arxiv.org/pdf/1602.04589v2.pdf | |
| PWC | https://paperswithcode.com/paper/optimal-best-arm-identification-with-fixed |
| Repo | |
| Framework | |
Resolving Spatial-Time Conflicts In A Set Of Any-angle Or Angle-constrained Grid Paths
| Title | Resolving Spatial-Time Conflicts In A Set Of Any-angle Or Angle-constrained Grid Paths |
| Authors | Konstantin Yakovlev, Anton Andreychuk |
| Abstract | We study the multi-agent path finding problem (MAPF) for a group of agents which are allowed to move into arbitrary directions on a 2D square grid. We focus on centralized conflict resolution for independently computed plans. We propose an algorithm that eliminates conflicts by using local re-planning and introducing time offsets to the execution of paths by different agents. Experimental results show that the algorithm can find high quality conflict-free solutions at low computational cost. |
| Tasks | Multi-Agent Path Finding |
| Published | 2016-08-09 |
| URL | http://arxiv.org/abs/1608.02763v1 |
| http://arxiv.org/pdf/1608.02763v1.pdf | |
| PWC | https://paperswithcode.com/paper/resolving-spatial-time-conflicts-in-a-set-of |
| Repo | |
| Framework | |
