May 6, 2019

3168 words 15 mins read

Paper Group ANR 280

Unsupervised Video Segmentation via Spatio-Temporally Nonlocal Appearance Learning. Click Carving: Segmenting Objects in Video with Point Clicks. Adaptive Maximization of Pointwise Submodular Functions With Budget Constraint. Predicting Student Dropout in Higher Education. A Combinatorial Solution to Non-Rigid 3D Shape-to-Image Matching. Learning h …

Unsupervised Video Segmentation via Spatio-Temporally Nonlocal Appearance Learning


Title	Unsupervised Video Segmentation via Spatio-Temporally Nonlocal Appearance Learning
Authors	Kaihua Zhang, Xuejun Li, Qingshan Liu
Abstract	Video object segmentation is challenging due to the factors like rapidly fast motion, cluttered backgrounds, arbitrary object appearance variation and shape deformation. Most existing methods only explore appearance information between two consecutive frames, which do not make full use of the usefully long-term nonlocal information that is helpful to make the learned appearance stable, and hence they tend to fail when the targets suffer from large viewpoint changes and significant non-rigid deformations. In this paper, we propose a simple yet effective approach to mine the long-term sptatio-temporally nonlocal appearance information for unsupervised video segmentation. The motivation of our algorithm comes from the spatio-temporal nonlocality of the region appearance reoccurrence in a video. Specifically, we first generate a set of superpixels to represent the foreground and background, and then update the appearance of each superpixel with its long-term sptatio-temporally nonlocal counterparts generated by the approximate nearest neighbor search method with the efficient KD-tree algorithm. Then, with the updated appearances, we formulate a spatio-temporal graphical model comprised of the superpixel label consistency potentials. Finally, we generate the segmentation by optimizing the graphical model via iteratively updating the appearance model and estimating the labels. Extensive evaluations on the SegTrack and Youtube-Objects datasets demonstrate the effectiveness of the proposed method, which performs favorably against some state-of-art methods.
Tasks	Semantic Segmentation, Video Object Segmentation, Video Semantic Segmentation
Published	2016-12-24
URL	http://arxiv.org/abs/1612.08169v1
PDF	http://arxiv.org/pdf/1612.08169v1.pdf
PWC	https://paperswithcode.com/paper/unsupervised-video-segmentation-via-spatio
Repo
Framework

Click Carving: Segmenting Objects in Video with Point Clicks


Title	Click Carving: Segmenting Objects in Video with Point Clicks
Authors	Suyog Dutt Jain, Kristen Grauman
Abstract	We present a novel form of interactive video object segmentation where a few clicks by the user helps the system produce a full spatio-temporal segmentation of the object of interest. Whereas conventional interactive pipelines take the user’s initialization as a starting point, we show the value in the system taking the lead even in initialization. In particular, for a given video frame, the system precomputes a ranked list of thousands of possible segmentation hypotheses (also referred to as object region proposals) using image and motion cues. Then, the user looks at the top ranked proposals, and clicks on the object boundary to carve away erroneous ones. This process iterates (typically 2-3 times), and each time the system revises the top ranked proposal set, until the user is satisfied with a resulting segmentation mask. Finally, the mask is propagated across the video to produce a spatio-temporal object tube. On three challenging datasets, we provide extensive comparisons with both existing work and simpler alternative methods. In all, the proposed Click Carving approach strikes an excellent balance of accuracy and human effort. It outperforms all similarly fast methods, and is competitive or better than those requiring 2 to 12 times the effort.
Tasks	Semantic Segmentation, Video Object Segmentation, Video Semantic Segmentation
Published	2016-07-05
URL	http://arxiv.org/abs/1607.01115v1
PDF	http://arxiv.org/pdf/1607.01115v1.pdf
PWC	https://paperswithcode.com/paper/click-carving-segmenting-objects-in-video
Repo
Framework

Adaptive Maximization of Pointwise Submodular Functions With Budget Constraint


Title	Adaptive Maximization of Pointwise Submodular Functions With Budget Constraint
Authors	Nguyen Viet Cuong, Huan Xu
Abstract	We study the worst-case adaptive optimization problem with budget constraint that is useful for modeling various practical applications in artificial intelligence and machine learning. We investigate the near-optimality of greedy algorithms for this problem with both modular and non-modular cost functions. In both cases, we prove that two simple greedy algorithms are not near-optimal but the best between them is near-optimal if the utility function satisfies pointwise submodularity and pointwise cost-sensitive submodularity respectively. This implies a combined algorithm that is near-optimal with respect to the optimal algorithm that uses half of the budget. We discuss applications of our theoretical results and also report experiments comparing the greedy algorithms on the active learning problem.
Tasks	Active Learning
Published	2016-03-30
URL	http://arxiv.org/abs/1603.09029v2
PDF	http://arxiv.org/pdf/1603.09029v2.pdf
PWC	https://paperswithcode.com/paper/adaptive-maximization-of-pointwise-submodular
Repo
Framework

Predicting Student Dropout in Higher Education


Title	Predicting Student Dropout in Higher Education
Authors	Lovenoor Aulck, Nishant Velagapudi, Joshua Blumenstock, Jevin West
Abstract	Each year, roughly 30% of first-year students at US baccalaureate institutions do not return for their second year and over $9 billion is spent educating these students. Yet, little quantitative research has analyzed the causes and possible remedies for student attrition. Here, we describe initial efforts to model student dropout using the largest known dataset on higher education attrition, which tracks over 32,500 students’ demographics and transcript records at one of the nation’s largest public universities. Our results highlight several early indicators of student attrition and show that dropout can be accurately predicted even when predictions are based on a single term of academic transcript data. These results highlight the potential for machine learning to have an impact on student retention and success while pointing to several promising directions for future work.
Tasks
Published	2016-06-20
URL	http://arxiv.org/abs/1606.06364v4
PDF	http://arxiv.org/pdf/1606.06364v4.pdf
PWC	https://paperswithcode.com/paper/predicting-student-dropout-in-higher
Repo
Framework

A Combinatorial Solution to Non-Rigid 3D Shape-to-Image Matching


Title	A Combinatorial Solution to Non-Rigid 3D Shape-to-Image Matching
Authors	Florian Bernard, Frank R. Schmidt, Johan Thunberg, Daniel Cremers
Abstract	We propose a combinatorial solution for the problem of non-rigidly matching a 3D shape to 3D image data. To this end, we model the shape as a triangular mesh and allow each triangle of this mesh to be rigidly transformed to achieve a suitable matching to the image. By penalising the distance and the relative rotation between neighbouring triangles our matching compromises between image and shape information. In this paper, we resolve two major challenges: Firstly, we address the resulting large and NP-hard combinatorial problem with a suitable graph-theoretic approach. Secondly, we propose an efficient discretisation of the unbounded 6-dimensional Lie group SE(3). To our knowledge this is the first combinatorial formulation for non-rigid 3D shape-to-image matching. In contrast to existing local (gradient descent) optimisation methods, we obtain solutions that do not require a good initialisation and that are within a bound of the optimal solution. We evaluate the proposed method on the two problems of non-rigid 3D shape-to-shape and non-rigid 3D shape-to-image registration and demonstrate that it provides promising results.
Tasks	Image Registration
Published	2016-11-16
URL	http://arxiv.org/abs/1611.05241v2
PDF	http://arxiv.org/pdf/1611.05241v2.pdf
PWC	https://paperswithcode.com/paper/a-combinatorial-solution-to-non-rigid-3d
Repo
Framework

Learning heat diffusion graphs


Title	Learning heat diffusion graphs
Authors	Dorina Thanou, Xiaowen Dong, Daniel Kressner, Pascal Frossard
Abstract	Effective information analysis generally boils down to properly identifying the structure or geometry of the data, which is often represented by a graph. In some applications, this structure may be partly determined by design constraints or pre-determined sensing arrangements, like in road transportation networks for example. In general though, the data structure is not readily available and becomes pretty difficult to define. In particular, the global smoothness assumptions, that most of the existing works adopt, are often too general and unable to properly capture localized properties of data. In this paper, we go beyond this classical data model and rather propose to represent information as a sparse combination of localized functions that live on a data structure represented by a graph. Based on this model, we focus on the problem of inferring the connectivity that best explains the data samples at different vertices of a graph that is a priori unknown. We concentrate on the case where the observed data is actually the sum of heat diffusion processes, which is a quite common model for data on networks or other irregular structures. We cast a new graph learning problem and solve it with an efficient nonconvex optimization algorithm. Experiments on both synthetic and real world data finally illustrate the benefits of the proposed graph learning framework and confirm that the data structure can be efficiently learned from data observations only. We believe that our algorithm will help solving key questions in diverse application domains such as social and biological network analysis where it is crucial to unveil proper geometry for data understanding and inference.
Tasks
Published	2016-11-04
URL	http://arxiv.org/abs/1611.01456v1
PDF	http://arxiv.org/pdf/1611.01456v1.pdf
PWC	https://paperswithcode.com/paper/learning-heat-diffusion-graphs
Repo
Framework

Enforcing Relational Matching Dependencies with Datalog for Entity Resolution


Title	Enforcing Relational Matching Dependencies with Datalog for Entity Resolution
Authors	Zeinab Bahmani, Leopoldo Bertossi
Abstract	Entity resolution (ER) is about identifying and merging records in a database that represent the same real-world entity. Matching dependencies (MDs) have been introduced and investigated as declarative rules that specify ER policies. An ER process induced by MDs over a dirty instance leads to multiple clean instances, in general. General “answer sets programs” have been proposed to specify the MD-based cleaning task and its results. In this work, we extend MDs to “relational MDs”, which capture more application semantics, and identify classes of relational MDs for which the general ASP can be automatically rewritten into a stratified Datalog program, with the single clean instance as its standard model.
Tasks	Entity Resolution
Published	2016-11-21
URL	http://arxiv.org/abs/1611.06951v2
PDF	http://arxiv.org/pdf/1611.06951v2.pdf
PWC	https://paperswithcode.com/paper/enforcing-relational-matching-dependencies
Repo
Framework

Spontaneous vs. Posed smiles - can we tell the difference?


Title	Spontaneous vs. Posed smiles - can we tell the difference?
Authors	Bappaditya Mandal, Nizar Ouarti
Abstract	Smile is an irrefutable expression that shows the physical state of the mind in both true and deceptive ways. Generally, it shows happy state of the mind, however, smiles' can be deceptive, for example people can give a smile when they feel happy and sometimes they might also give a smile (in a different way) when they feel pity for others. This work aims to distinguish spontaneous (felt) smile expressions from posed (deliberate) smiles by extracting and analyzing both global (macro) motion of the face and subtle (micro) changes in the facial expression features through both tracking a series of facial fiducial markers as well as using dense optical flow. Specifically the eyes and lips features are captured and used for analysis. It aims to automatically classify all smiles into either spontaneous’ or `posed’ categories, by using support vector machines (SVM). Experimental results on large database show promising results as compared to other relevant methods. \|
Tasks	Optical Flow Estimation
Published	2016-05-23
URL	http://arxiv.org/abs/1605.07026v1
PDF	http://arxiv.org/pdf/1605.07026v1.pdf
PWC	https://paperswithcode.com/paper/spontaneous-vs-posed-smiles-can-we-tell-the
Repo
Framework

Random-Key Cuckoo Search for the Travelling Salesman Problem


Title	Random-Key Cuckoo Search for the Travelling Salesman Problem
Authors	Aziz Ouaarab, B. Ahiod, Xin-She Yang
Abstract	Combinatorial optimization problems are typically NP-hard, and thus very challenging to solve. In this paper, we present the random key cuckoo search (RKCS) algorithm for solving the famous Travelling Salesman Problem (TSP). We used a simplified random-key encoding scheme to pass from a continuous space (real numbers) to a combinatorial space. We also consider the displacement of a solution in both spaces using Levy flights. The performance of the proposed RKCS is tested against a set of benchmarks of symmetric TSP from the well-known TSPLIB library. The results of the tests show that RKCS is superior to some other metaheuristic algorithms.
Tasks	Combinatorial Optimization
Published	2016-04-14
URL	http://arxiv.org/abs/1607.04324v1
PDF	http://arxiv.org/pdf/1607.04324v1.pdf
PWC	https://paperswithcode.com/paper/random-key-cuckoo-search-for-the-travelling
Repo
Framework

Fast Algorithms for Demixing Sparse Signals from Nonlinear Observations


Title	Fast Algorithms for Demixing Sparse Signals from Nonlinear Observations
Authors	Mohammadreza Soltani, Chinmay Hegde
Abstract	We study the problem of demixing a pair of sparse signals from noisy, nonlinear observations of their superposition. Mathematically, we consider a nonlinear signal observation model, $y_i = g(a_i^Tx) + e_i, \ i=1,\ldots,m$, where $x = \Phi w+\Psi z$ denotes the superposition signal, $\Phi$ and $\Psi$ are orthonormal bases in $\mathbb{R}^n$, and $w, z\in\mathbb{R}^n$ are sparse coefficient vectors of the constituent signals, and $e_i$ represents the noise. Moreover, $g$ represents a nonlinear link function, and $a_i\in\mathbb{R}^n$ is the $i$-th row of the measurement matrix, $A\in\mathbb{R}^{m\times n}$. Problems of this nature arise in several applications ranging from astronomy, computer vision, and machine learning. In this paper, we make some concrete algorithmic progress for the above demixing problem. Specifically, we consider two scenarios: (i) the case when the demixing procedure has no knowledge of the link function, and (ii) the case when the demixing algorithm has perfect knowledge of the link function. In both cases, we provide fast algorithms for recovery of the constituents $w$ and $z$ from the observations. Moreover, we support these algorithms with a rigorous theoretical analysis, and derive (nearly) tight upper bounds on the sample complexity of the proposed algorithms for achieving stable recovery of the component signals. We also provide a range of numerical simulations to illustrate the performance of the proposed algorithms on both real and synthetic signals and images.
Tasks
Published	2016-08-03
URL	http://arxiv.org/abs/1608.01234v3
PDF	http://arxiv.org/pdf/1608.01234v3.pdf
PWC	https://paperswithcode.com/paper/fast-algorithms-for-demixing-sparse-signals
Repo
Framework

An Ensemble Blocking Scheme for Entity Resolution of Large and Sparse Datasets


Title	An Ensemble Blocking Scheme for Entity Resolution of Large and Sparse Datasets
Authors	Janani Balaji, Faizan Javed, Mayank Kejriwal, Chris Min, Sam Sander, Ozgur Ozturk
Abstract	Entity Resolution, also called record linkage or deduplication, refers to the process of identifying and merging duplicate versions of the same entity into a unified representation. The standard practice is to use a Rule based or Machine Learning based model that compares entity pairs and assigns a score to represent the pairs’ Match/Non-Match status. However, performing an exhaustive pair-wise comparison on all pairs of records leads to quadratic matcher complexity and hence a Blocking step is performed before the Matching to group similar entities into smaller blocks that the matcher can then examine exhaustively. Several blocking schemes have been developed to efficiently and effectively block the input dataset into manageable groups. At CareerBuilder (CB), we perform deduplication on massive datasets of people profiles collected from disparate sources with varying informational content. We observed that, employing a single blocking technique did not cover the base for all possible scenarios due to the multi-faceted nature of our data sources. In this paper, we describe our ensemble approach to blocking that combines two different blocking techniques to leverage their respective strengths.
Tasks	Entity Resolution
Published	2016-09-20
URL	http://arxiv.org/abs/1609.06265v2
PDF	http://arxiv.org/pdf/1609.06265v2.pdf
PWC	https://paperswithcode.com/paper/an-ensemble-blocking-scheme-for-entity
Repo
Framework

Learning Combinatorial Functions from Pairwise Comparisons


Title	Learning Combinatorial Functions from Pairwise Comparisons
Authors	Maria-Florina Balcan, Ellen Vitercik, Colin White
Abstract	A large body of work in machine learning has focused on the problem of learning a close approximation to an underlying combinatorial function, given a small set of labeled examples. However, for real-valued functions, cardinal labels might not be accessible, or it may be difficult for an expert to consistently assign real-valued labels over the entire set of examples. For instance, it is notoriously hard for consumers to reliably assign values to bundles of merchandise. Instead, it might be much easier for a consumer to report which of two bundles she likes better. With this motivation in mind, we consider an alternative learning model, wherein the algorithm must learn the underlying function up to pairwise comparisons, from pairwise comparisons. In this model, we present a series of novel algorithms that learn over a wide variety of combinatorial function classes. These range from graph functions to broad classes of valuation functions that are fundamentally important in microeconomic theory, the analysis of social networks, and machine learning, such as coverage, submodular, XOS, and subadditive functions, as well as functions with sparse Fourier support.
Tasks
Published	2016-05-30
URL	http://arxiv.org/abs/1605.09227v1
PDF	http://arxiv.org/pdf/1605.09227v1.pdf
PWC	https://paperswithcode.com/paper/learning-combinatorial-functions-from
Repo
Framework

Robust Time-Series Retrieval Using Probabilistic Adaptive Segmental Alignment


Title	Robust Time-Series Retrieval Using Probabilistic Adaptive Segmental Alignment
Authors	Shahriar Shariat, Vladimir Pavlovic
Abstract	Traditional pairwise sequence alignment is based on matching individual samples from two sequences, under time monotonicity constraints. However, in many application settings matching subsequences (segments) instead of individual samples may bring in additional robustness to noise or local non-causal perturbations. This paper presents an approach to segmental sequence alignment that jointly segments and aligns two sequences, generalizing the traditional per-sample alignment. To accomplish this task, we introduce a distance metric between segments based on average pairwise distances and then present a modified pair-HMM (PHMM) that incorporates the proposed distance metric to solve the joint segmentation and alignment task. We also propose a relaxation to our model that improves the computational efficiency of the generic segmental PHMM. Our results demonstrate that this new measure of sequence similarity can lead to improved classification performance, while being resilient to noise, on a variety of sequence retrieval problems, from EEG to motion sequence classification.
Tasks	EEG, Time Series
Published	2016-09-26
URL	http://arxiv.org/abs/1609.08201v1
PDF	http://arxiv.org/pdf/1609.08201v1.pdf
PWC	https://paperswithcode.com/paper/robust-time-series-retrieval-using
Repo
Framework

Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes


Title	Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes
Authors	Nima Anari, Shayan Oveis Gharan, Alireza Rezaei
Abstract	Strongly Rayleigh distributions are natural generalizations of product and determinantal probability distributions and satisfy strongest form of negative dependence properties. We show that the “natural” Monte Carlo Markov Chain (MCMC) is rapidly mixing in the support of a {\em homogeneous} strongly Rayleigh distribution. As a byproduct, our proof implies Markov chains can be used to efficiently generate approximate samples of a $k$-determinantal point process. This answers an open question raised by Deshpande and Rademacher.
Tasks	Point Processes
Published	2016-02-16
URL	http://arxiv.org/abs/1602.05242v3
PDF	http://arxiv.org/pdf/1602.05242v3.pdf
PWC	https://paperswithcode.com/paper/monte-carlo-markov-chain-algorithms-for
Repo
Framework

Supervised Adverse Drug Reaction Signalling Framework Imitating Bradford Hill’s Causality Considerations


Title	Supervised Adverse Drug Reaction Signalling Framework Imitating Bradford Hill’s Causality Considerations
Authors	Jenna Marie Reps, Jonathan M. Garibaldi, Uwe Aickelin, Jack E. Gibson, Richard B. Hubbard
Abstract	Big longitudinal observational medical data potentially hold a wealth of information and have been recognised as potential sources for gaining new drug safety knowledge. Unfortunately there are many complexities and underlying issues when analysing longitudinal observational data. Due to these complexities, existing methods for large-scale detection of negative side effects using observational data all tend to have issues distinguishing between association and causality. New methods that can better discriminate causal and non-causal relationships need to be developed to fully utilise the data. In this paper we propose using a set of causality considerations developed by the epidemiologist Bradford Hill as a basis for engineering features that enable the application of supervised learning for the problem of detecting negative side effects. The Bradford Hill considerations look at various perspectives of a drug and outcome relationship to determine whether it shows causal traits. We taught a classifier to find patterns within these perspectives and it learned to discriminate between association and causality. The novelty of this research is the combination of supervised learning and Bradford Hill’s causality considerations to automate the Bradford Hill’s causality assessment. We evaluated the framework on a drug safety gold standard know as the observational medical outcomes partnership’s nonspecified association reference set. The methodology obtained excellent discriminate ability with area under the curves ranging between 0.792-0.940 (existing method optimal: 0.73) and a mean average precision of 0.640 (existing method optimal: 0.141). The proposed features can be calculated efficiently and be readily updated, making the framework suitable for big observational data.
Tasks
Published	2016-07-21
URL	http://arxiv.org/abs/1607.06198v1
PDF	http://arxiv.org/pdf/1607.06198v1.pdf
PWC	https://paperswithcode.com/paper/supervised-adverse-drug-reaction-signalling
Repo
Framework