Paper Group ANR 865
A Fast and Easy Regression Technique for k-NN Classification Without Using Negative Pairs. Multi-Task Active Learning for Neural Semantic Role Labeling on Low Resource Conversational Corpus. Forgetting Memories and their Attractiveness. Weak Semi-Markov CRFs for NP Chunking in Informal Text. Deep Bilevel Learning. Clustering to Reduce Spatial Data …
A Fast and Easy Regression Technique for k-NN Classification Without Using Negative Pairs
| Title | A Fast and Easy Regression Technique for k-NN Classification Without Using Negative Pairs |
| Authors | Yutaro Shigeto, Masashi Shimbo, Yuji Matsumoto |
| Abstract | This paper proposes an inexpensive way to learn an effective dissimilarity function to be used for $k$-nearest neighbor ($k$-NN) classification. Unlike Mahalanobis metric learning methods that map both query (unlabeled) objects and labeled objects to new coordinates by a single transformation, our method learns a transformation of labeled objects to new points in the feature space whereas query objects are kept in their original coordinates. This method has several advantages over existing distance metric learning methods: (i) In experiments with large document and image datasets, it achieves $k$-NN classification accuracy better than or at least comparable to the state-of-the-art metric learning methods. (ii) The transformation can be learned efficiently by solving a standard ridge regression problem. For document and image datasets, training is often more than two orders of magnitude faster than the fastest metric learning methods tested. This speed-up is also due to the fact that the proposed method eliminates the optimization over “negative” object pairs, i.e., objects whose class labels are different. (iii) The formulation has a theoretical justification in terms of reducing hubness in data. |
| Tasks | Metric Learning |
| Published | 2018-06-11 |
| URL | http://arxiv.org/abs/1806.03945v1 |
| http://arxiv.org/pdf/1806.03945v1.pdf | |
| PWC | https://paperswithcode.com/paper/a-fast-and-easy-regression-technique-for-k-nn |
| Repo | |
| Framework | |
Multi-Task Active Learning for Neural Semantic Role Labeling on Low Resource Conversational Corpus
| Title | Multi-Task Active Learning for Neural Semantic Role Labeling on Low Resource Conversational Corpus |
| Authors | Fariz Ikhwantri, Samuel Louvan, Kemal Kurniawan, Bagas Abisena, Valdi Rachman, Alfan Farizki Wicaksono, Rahmad Mahendra |
| Abstract | Most Semantic Role Labeling (SRL) approaches are supervised methods which require a significant amount of annotated corpus, and the annotation requires linguistic expertise. In this paper, we propose a Multi-Task Active Learning framework for Semantic Role Labeling with Entity Recognition (ER) as the auxiliary task to alleviate the need for extensive data and use additional information from ER to help SRL. We evaluate our approach on Indonesian conversational dataset. Our experiments show that multi-task active learning can outperform single-task active learning method and standard multi-task learning. According to our results, active learning is more efficient by using 12% less of training data compared to passive learning in both single-task and multi-task setting. We also introduce a new dataset for SRL in Indonesian conversational domain to encourage further research in this area. |
| Tasks | Active Learning, Multi-Task Learning, Semantic Role Labeling |
| Published | 2018-06-05 |
| URL | http://arxiv.org/abs/1806.01523v1 |
| http://arxiv.org/pdf/1806.01523v1.pdf | |
| PWC | https://paperswithcode.com/paper/multi-task-active-learning-for-neural |
| Repo | |
| Framework | |
Forgetting Memories and their Attractiveness
| Title | Forgetting Memories and their Attractiveness |
| Authors | Enzo Marinari |
| Abstract | We study numerically the memory which forgets, introduced in 1986 by Parisi by bounding the synaptic strength, with a mechanism which avoid confusion, allows to remember the pattern learned more recently and has a physiologically very well defined meaning. We analyze a number of features of the learning at finite number of neurons and finite number of patterns. We discuss how the system behaves in the large but finite N limit. We analyze the basin of attraction of the patterns that have been learned, and we show that it is exponentially small in the age of the pattern. This is a clearly non physiological feature of the model. |
| Tasks | |
| Published | 2018-05-31 |
| URL | http://arxiv.org/abs/1805.12368v1 |
| http://arxiv.org/pdf/1805.12368v1.pdf | |
| PWC | https://paperswithcode.com/paper/forgetting-memories-and-their-attractiveness |
| Repo | |
| Framework | |
Weak Semi-Markov CRFs for NP Chunking in Informal Text
| Title | Weak Semi-Markov CRFs for NP Chunking in Informal Text |
| Authors | Aldrian Obaja Muis, Wei Lu |
| Abstract | This paper introduces a new annotated corpus based on an existing informal text corpus: the NUS SMS Corpus (Chen and Kan, 2013). The new corpus includes 76,490 noun phrases from 26,500 SMS messages, annotated by university students. We then explored several graphical models, including a novel variant of the semi-Markov conditional random fields (semi-CRF) for the task of noun phrase chunking. We demonstrated through empirical evaluations on the new dataset that the new variant yielded similar accuracy but ran in significantly lower running time compared to the conventional semi-CRF. |
| Tasks | Chunking |
| Published | 2018-10-19 |
| URL | http://arxiv.org/abs/1810.08567v1 |
| http://arxiv.org/pdf/1810.08567v1.pdf | |
| PWC | https://paperswithcode.com/paper/weak-semi-markov-crfs-for-np-chunking-in |
| Repo | |
| Framework | |
Deep Bilevel Learning
| Title | Deep Bilevel Learning |
| Authors | Simon Jenni, Paolo Favaro |
| Abstract | We present a novel regularization approach to train neural networks that enjoys better generalization and test error than standard stochastic gradient descent. Our approach is based on the principles of cross-validation, where a validation set is used to limit the model overfitting. We formulate such principles as a bilevel optimization problem. This formulation allows us to define the optimization of a cost on the validation set subject to another optimization on the training set. The overfitting is controlled by introducing weights on each mini-batch in the training set and by choosing their values so that they minimize the error on the validation set. In practice, these weights define mini-batch learning rates in a gradient descent update equation that favor gradients with better generalization capabilities. Because of its simplicity, this approach can be integrated with other regularization methods and training schemes. We evaluate extensively our proposed algorithm on several neural network architectures and datasets, and find that it consistently improves the generalization of the model, especially when labels are noisy. |
| Tasks | bilevel optimization |
| Published | 2018-09-05 |
| URL | http://arxiv.org/abs/1809.01465v1 |
| http://arxiv.org/pdf/1809.01465v1.pdf | |
| PWC | https://paperswithcode.com/paper/deep-bilevel-learning |
| Repo | |
| Framework | |
Clustering to Reduce Spatial Data Set Size
| Title | Clustering to Reduce Spatial Data Set Size |
| Authors | Geoff Boeing |
| Abstract | Traditionally it had been a problem that researchers did not have access to enough spatial data to answer pressing research questions or build compelling visualizations. Today, however, the problem is often that we have too much data. Spatially redundant or approximately redundant points may refer to a single feature (plus noise) rather than many distinct spatial features. We use a machine learning approach with density-based clustering to compress such spatial data into a set of representative features. |
| Tasks | |
| Published | 2018-03-21 |
| URL | http://arxiv.org/abs/1803.08101v1 |
| http://arxiv.org/pdf/1803.08101v1.pdf | |
| PWC | https://paperswithcode.com/paper/clustering-to-reduce-spatial-data-set-size |
| Repo | |
| Framework | |
Multiple-Step Greedy Policies in Online and Approximate Reinforcement Learning
| Title | Multiple-Step Greedy Policies in Online and Approximate Reinforcement Learning |
| Authors | Yonathan Efroni, Gal Dalal, Bruno Scherrer, Shie Mannor |
| Abstract | Multiple-step lookahead policies have demonstrated high empirical competence in Reinforcement Learning, via the use of Monte Carlo Tree Search or Model Predictive Control. In a recent work \cite{efroni2018beyond}, multiple-step greedy policies and their use in vanilla Policy Iteration algorithms were proposed and analyzed. In this work, we study multiple-step greedy algorithms in more practical setups. We begin by highlighting a counter-intuitive difficulty, arising with soft-policy updates: even in the absence of approximations, and contrary to the 1-step-greedy case, monotonic policy improvement is not guaranteed unless the update stepsize is sufficiently large. Taking particular care about this difficulty, we formulate and analyze online and approximate algorithms that use such a multi-step greedy operator. |
| Tasks | |
| Published | 2018-05-21 |
| URL | http://arxiv.org/abs/1805.07956v2 |
| http://arxiv.org/pdf/1805.07956v2.pdf | |
| PWC | https://paperswithcode.com/paper/multiple-step-greedy-policies-in-online-and |
| Repo | |
| Framework | |
Follow Me at the Edge: Mobility-Aware Dynamic Service Placement for Mobile Edge Computing
| Title | Follow Me at the Edge: Mobility-Aware Dynamic Service Placement for Mobile Edge Computing |
| Authors | Tao Ouyang, Zhi Zhou, Xu Chen |
| Abstract | Mobile edge computing is a new computing paradigm, which pushes cloud computing capabilities away from the centralized cloud to the network edge. However, with the sinking of computing capabilities, the new challenge incurred by user mobility arises: since end-users typically move erratically, the services should be dynamically migrated among multiple edges to maintain the service performance, i.e., user-perceived latency. Tackling this problem is non-trivial since frequent service migration would greatly increase the operational cost. To address this challenge in terms of the performance-cost trade-off, in this paper we study the mobile edge service performance optimization problem under long-term cost budget constraint. To address user mobility which is typically unpredictable, we apply Lyapunov optimization to decompose the long-term optimization problem into a series of real-time optimization problems which do not require a priori knowledge such as user mobility. As the decomposed problem is NP-hard, we first design an approximation algorithm based on Markov approximation to seek a near-optimal solution. To make our solution scalable and amenable to future 5G application scenario with large-scale user devices, we further propose a distributed approximation scheme with greatly reduced time complexity, based on the technique of best response update. Rigorous theoretical analysis and extensive evaluations demonstrate the efficacy of the proposed centralized and distributed schemes. |
| Tasks | |
| Published | 2018-09-14 |
| URL | http://arxiv.org/abs/1809.05239v1 |
| http://arxiv.org/pdf/1809.05239v1.pdf | |
| PWC | https://paperswithcode.com/paper/follow-me-at-the-edge-mobility-aware-dynamic |
| Repo | |
| Framework | |
VideoMatch: Matching based Video Object Segmentation
| Title | VideoMatch: Matching based Video Object Segmentation |
| Authors | Yuan-Ting Hu, Jia-Bin Huang, Alexander G. Schwing |
| Abstract | Video object segmentation is challenging yet important in a wide variety of applications for video analysis. Recent works formulate video object segmentation as a prediction task using deep nets to achieve appealing state-of-the-art performance. Due to the formulation as a prediction task, most of these methods require fine-tuning during test time, such that the deep nets memorize the appearance of the objects of interest in the given video. However, fine-tuning is time-consuming and computationally expensive, hence the algorithms are far from real time. To address this issue, we develop a novel matching based algorithm for video object segmentation. In contrast to memorization based classification techniques, the proposed approach learns to match extracted features to a provided template without memorizing the appearance of the objects. We validate the effectiveness and the robustness of the proposed method on the challenging DAVIS-16, DAVIS-17, Youtube-Objects and JumpCut datasets. Extensive results show that our method achieves comparable performance without fine-tuning and is much more favorable in terms of computational time. |
| Tasks | Semantic Segmentation, Video Object Segmentation, Video Semantic Segmentation |
| Published | 2018-09-04 |
| URL | http://arxiv.org/abs/1809.01123v1 |
| http://arxiv.org/pdf/1809.01123v1.pdf | |
| PWC | https://paperswithcode.com/paper/videomatch-matching-based-video-object |
| Repo | |
| Framework | |
Multiresolution Tensor Decomposition for Multiple Spatial Passing Networks
| Title | Multiresolution Tensor Decomposition for Multiple Spatial Passing Networks |
| Authors | Shaobo Han, David B. Dunson |
| Abstract | This article is motivated by soccer positional passing networks collected across multiple games. We refer to these data as replicated spatial passing networks—to accurately model such data it is necessary to take into account the spatial positions of the passer and receiver for each passing event. This spatial registration and replicates that occur across games represent key differences with usual social network data. As a key step before investigating how the passing dynamics influence team performance, we focus on developing methods for summarizing different team’s passing strategies. Our proposed approach relies on a novel multiresolution data representation framework and Poisson nonnegative block term decomposition model, which automatically produces coarse-to-fine low-rank network motifs. The proposed methods are applied to detailed passing record data collected from the 2014 FIFA World Cup. |
| Tasks | |
| Published | 2018-03-03 |
| URL | http://arxiv.org/abs/1803.01203v1 |
| http://arxiv.org/pdf/1803.01203v1.pdf | |
| PWC | https://paperswithcode.com/paper/multiresolution-tensor-decomposition-for |
| Repo | |
| Framework | |
A Hierarchical Approach to Neural Context-Aware Modeling
| Title | A Hierarchical Approach to Neural Context-Aware Modeling |
| Authors | Patrick Huber, Jan Niehues, Alex Waibel |
| Abstract | We present a new recurrent neural network topology to enhance state-of-the-art machine learning systems by incorporating a broader context. Our approach overcomes recent limitations with extended narratives through a multi-layered computational approach to generate an abstract context representation. Therefore, the developed system captures the narrative on word-level, sentence-level, and context-level. Through the hierarchical set-up, our proposed model summarizes the most salient information on each level and creates an abstract representation of the extended context. We subsequently use this representation to enhance neural language processing systems on the task of semantic error detection. To show the potential of the newly introduced topology, we compare the approach against a context-agnostic set-up including a standard neural language model and a supervised binary classification network. The performance measures on the error detection task show the advantage of the hierarchical context-aware topologies, improving the baseline by 12.75% relative for unsupervised models and 20.37% relative for supervised models. |
| Tasks | Language Modelling |
| Published | 2018-07-27 |
| URL | http://arxiv.org/abs/1807.11582v2 |
| http://arxiv.org/pdf/1807.11582v2.pdf | |
| PWC | https://paperswithcode.com/paper/a-hierarchical-approach-to-neural-context |
| Repo | |
| Framework | |
Active Reinforcement Learning with Monte-Carlo Tree Search
| Title | Active Reinforcement Learning with Monte-Carlo Tree Search |
| Authors | Sebastian Schulze, Owain Evans |
| Abstract | Active Reinforcement Learning (ARL) is a twist on RL where the agent observes reward information only if it pays a cost. This subtle change makes exploration substantially more challenging. Powerful principles in RL like optimism, Thompson sampling, and random exploration do not help with ARL. We relate ARL in tabular environments to Bayes-Adaptive MDPs. We provide an ARL algorithm using Monte-Carlo Tree Search that is asymptotically Bayes optimal. Experimentally, this algorithm is near-optimal on small Bandit problems and MDPs. On larger MDPs it outperforms a Q-learner augmented with specialised heuristics for ARL. By analysing exploration behaviour in detail, we uncover obstacles to scaling up simulation-based algorithms for ARL. |
| Tasks | |
| Published | 2018-03-13 |
| URL | http://arxiv.org/abs/1803.04926v3 |
| http://arxiv.org/pdf/1803.04926v3.pdf | |
| PWC | https://paperswithcode.com/paper/active-reinforcement-learning-with-monte |
| Repo | |
| Framework | |
Moving Object Segmentation in Jittery Videos by Stabilizing Trajectories Modeled in Kendall’s Shape Space
| Title | Moving Object Segmentation in Jittery Videos by Stabilizing Trajectories Modeled in Kendall’s Shape Space |
| Authors | Geethu Miriam Jacob, Sukhendu Das |
| Abstract | Moving Object Segmentation is a challenging task for jittery/wobbly videos. For jittery videos, the non-smooth camera motion makes discrimination between foreground objects and background layers hard to solve. While most recent works for moving video object segmentation fail in this scenario, our method generates an accurate segmentation of a single moving object. The proposed method performs a sparse segmentation, where frame-wise labels are assigned only to trajectory coordinates, followed by the pixel-wise labeling of frames. The sparse segmentation involving stabilization and clustering of trajectories in a 3-stage iterative process. At the 1st stage, the trajectories are clustered using pairwise Procrustes distance as a cue for creating an affinity matrix. The 2nd stage performs a block-wise Procrustes analysis of the trajectories and estimates Frechet means (in Kendall’s shape space) of the clusters. The Frechet means represent the average trajectories of the motion clusters. An optimization function has been formulated to stabilize the Frechet means, yielding stabilized trajectories at the 3rd stage. The accuracy of the motion clusters are iteratively refined, producing distinct groups of stabilized trajectories. Next, the labels obtained from the sparse segmentation are propagated for pixel-wise labeling of the frames, using a GraphCut based energy formulation. Use of Procrustes analysis and energy minimization in Kendall’s shape space for moving object segmentation in jittery videos, is the novelty of this work. Second contribution comes from experiments performed on a dataset formed of 20 real-world natural jittery videos, with manually annotated ground truth. Experiments are done with controlled levels of artificial jitter on videos of SegTrack2 dataset. Qualitative and quantitative results indicate the superiority of the proposed method. |
| Tasks | Semantic Segmentation, Video Object Segmentation, Video Semantic Segmentation |
| Published | 2018-08-14 |
| URL | http://arxiv.org/abs/1808.04551v1 |
| http://arxiv.org/pdf/1808.04551v1.pdf | |
| PWC | https://paperswithcode.com/paper/moving-object-segmentation-in-jittery-videos |
| Repo | |
| Framework | |
CDM: Compound dissimilarity measure and an application to fingerprinting-based positioning
| Title | CDM: Compound dissimilarity measure and an application to fingerprinting-based positioning |
| Authors | Caifa Zhou, Andreas Wieser |
| Abstract | A non-vector-based dissimilarity measure is proposed by combining vector-based distance metrics and set operations. This proposed compound dissimilarity measure (CDM) is applicable to quantify similarity of collections of attribute/feature pairs where not all attributes are present in all collections. This is a typical challenge in the context of e.g., fingerprinting-based positioning (FbP). Compared to vector-based distance metrics (e.g., Minkowski), the merits of the proposed CDM are i) the data do not need to be converted to vectors of equal dimension, ii) shared and unshared attributes can be weighted differently within the assessment, and iii) additional degrees of freedom within the measure allow to adapt its properties to application needs in a data-driven way. We indicate the validity of the proposed CDM by demonstrating the improvements of the positioning performance of fingerprinting-based WLAN indoor positioning using four different datasets, three of them publicly available. When processing these datasets using CDM instead of conventional distance metrics the accuracy of identifying buildings and floors improves by about 5% on average. The 2d positioning errors in terms of root mean squared error (RMSE) are reduced by a factor of two, and the percentage of position solutions with less than 2m error improves by over 10%. |
| Tasks | |
| Published | 2018-05-16 |
| URL | http://arxiv.org/abs/1805.06208v2 |
| http://arxiv.org/pdf/1805.06208v2.pdf | |
| PWC | https://paperswithcode.com/paper/cdm-compound-dissimilarity-measure-and-an |
| Repo | |
| Framework | |
Convex Clustering: Model, Theoretical Guarantee and Efficient Algorithm
| Title | Convex Clustering: Model, Theoretical Guarantee and Efficient Algorithm |
| Authors | Defeng Sun, Kim-Chuan Toh, Yancheng Yuan |
| Abstract | Clustering is a fundamental problem in unsupervised learning. Popular methods like K-means, may suffer from poor performance as they are prone to get stuck in its local minima. Recently, the sum-of-norms (SON) model (also known as the clustering path) has been proposed in Pelckmans et al. (2005), Lindsten et al. (2011) and Hocking et al. (2011). The perfect recovery properties of the convex clustering model with uniformly weighted all pairwise-differences regularization have been proved by Zhu et al. (2014) and Panahi et al. (2017). However, no theoretical guarantee has been established for the general weighted convex clustering model, where better empirical results have been observed. In the numerical optimization aspect, although algorithms like the alternating direction method of multipliers (ADMM) and the alternating minimization algorithm (AMA) have been proposed to solve the convex clustering model (Chi and Lange, 2015), it still remains very challenging to solve large-scale problems. In this paper, we establish sufficient conditions for the perfect recovery guarantee of the general weighted convex clustering model, which include and improve existing theoretical results as special cases. In addition, we develop a semismooth Newton based augmented Lagrangian method for solving large-scale convex clustering problems. Extensive numerical experiments on both simulated and real data demonstrate that our algorithm is highly efficient and robust for solving large-scale problems. Moreover, the numerical results also show the superior performance and scalability of our algorithm comparing to the existing first-order methods. In particular, our algorithm is able to solve a convex clustering problem with 200,000 points in $\mathbb{R}^3$ in about 6 minutes. |
| Tasks | |
| Published | 2018-10-04 |
| URL | http://arxiv.org/abs/1810.02677v1 |
| http://arxiv.org/pdf/1810.02677v1.pdf | |
| PWC | https://paperswithcode.com/paper/convex-clustering-model-theoretical-guarantee |
| Repo | |
| Framework | |
