July 27, 2019

3263 words 16 mins read

Paper Group ANR 735

Structure Learning of $H$-colorings. Monocular Navigation in Large Scale Dynamic Environments. Pyramidal Gradient Matching for Optical Flow Estimation. Crowdsourcing Predictors of Residential Electric Energy Usage. On Quadratic Convergence of DC Proximal Newton Algorithm for Nonconvex Sparse Learning in High Dimensions. Ensemble Classifier for Eye …

Structure Learning of $H$-colorings


Title	Structure Learning of $H$-colorings
Authors	Antonio Blanca, Zongchen Chen, Daniel Štefankovič, Eric Vigoda
Abstract	We study the structure learning problem for $H$-colorings, an important class of Markov random fields that capture key combinatorial structures on graphs, including proper colorings and independent sets, as well as spin systems from statistical physics. The learning problem is as follows: for a fixed (and known) constraint graph $H$ with $q$ colors and an unknown graph $G=(V,E)$ with $n$ vertices, given uniformly random $H$-colorings of $G$, how many samples are required to learn the edges of the unknown graph $G$? We give a characterization of $H$ for which the problem is identifiable for every $G$, i.e., we can learn $G$ with an infinite number of samples. We also show that there are identifiable constraint graphs for which one cannot hope to learn every graph $G$ efficiently. We focus particular attention on the case of proper vertex $q$-colorings of graphs of maximum degree $d$ where intriguing connections to statistical physics phase transitions appear. We prove that in the tree uniqueness region (when $q>d$) the problem is identifiable and we can learn $G$ in ${\rm poly}(d,q) \times O(n^2\log{n})$ time. In contrast for soft-constraint systems, such as the Ising model, the best possible running time is exponential in $d$. In the tree non-uniqueness region (when $q\leq d$) we prove that the problem is not identifiable and thus $G$ cannot be learned. Moreover, when $q<d-\sqrt{d} + \Theta(1)$ we prove that even learning an equivalent graph (any graph with the same set of $H$-colorings) is computationally hard—sample complexity is exponential in $n$ in the worst case. We further explore the connection between the efficiency/hardness of the structure learning problem and the uniqueness/non-uniqueness phase transition for general $H$-colorings and prove that under the well-known Dobrushin uniqueness condition, we can learn $G$ in ${\rm poly}(d,q)\times O(n^2\log{n})$ time.
Tasks
Published	2017-08-17
URL	http://arxiv.org/abs/1708.05118v2
PDF	http://arxiv.org/pdf/1708.05118v2.pdf
PWC	https://paperswithcode.com/paper/structure-learning-of-h-colorings
Repo
Framework


Title	Monocular Navigation in Large Scale Dynamic Environments
Authors	Darius Burschka
Abstract	We present a processing technique for a robust reconstruction of motion properties for single points in large scale, dynamic environments. We assume that the acquisition camera is moving and that there are other independently moving agents in a large environment, like road scenarios. The separation of direction and magnitude of the reconstructed motion allows for robust reconstruction of the dynamic state of the objects in situations, where conventional binocular systems fail due to a small signal (disparity) from the images due to a constant detection error, and where structure from motion approaches fail due to unobserved motion of other agents between the camera frames. We present the mathematical framework and the sensitivity analysis for the resulting system.
Tasks
Published	2017-09-07
URL	http://arxiv.org/abs/1709.02285v1
PDF	http://arxiv.org/pdf/1709.02285v1.pdf
PWC	https://paperswithcode.com/paper/monocular-navigation-in-large-scale-dynamic
Repo
Framework

Pyramidal Gradient Matching for Optical Flow Estimation


Title	Pyramidal Gradient Matching for Optical Flow Estimation
Authors	Yuanwei Li
Abstract	Initializing optical flow field by either sparse descriptor matching or dense patch matches has been proved to be particularly useful for capturing large displacements. In this paper, we present a pyramidal gradient matching approach that can provide dense matches for highly accurate and efficient optical flow estimation. A novel contribution of our method is that image gradient is used to describe image patches and proved to be able to produce robust matching. Therefore, our method is more efficient than methods that adopt special features (like SIFT) or patch distance metric. Moreover, we find that image gradient is scalable for optical flow estimation, which means we can use different levels of gradient feature (for example, full gradients or only direction information of gradients) to obtain different complexity without dramatic changes in accuracy. Another contribution is that we uncover the secrets of limited PatchMatch through a thorough analysis and design a pyramidal matching framework based these secrets. Our pyramidal matching framework is aimed at robust gradient matching and effective to grow inliers and reject outliers. In this framework, we present some special enhancements for outlier filtering in gradient matching. By initializing EpicFlow with our matches, experimental results show that our method is efficient and robust (ranking 1st on both clean pass and final pass of MPI Sintel dataset among published methods).
Tasks	Optical Flow Estimation
Published	2017-04-11
URL	http://arxiv.org/abs/1704.03217v1
PDF	http://arxiv.org/pdf/1704.03217v1.pdf
PWC	https://paperswithcode.com/paper/pyramidal-gradient-matching-for-optical-flow
Repo
Framework

Crowdsourcing Predictors of Residential Electric Energy Usage


Title	Crowdsourcing Predictors of Residential Electric Energy Usage
Authors	Mark D. Wagy, Josh C. Bongard, James P. Bagrow, Paul D. H. Hines
Abstract	Crowdsourcing has been successfully applied in many domains including astronomy, cryptography and biology. In order to test its potential for useful application in a Smart Grid context, this paper investigates the extent to which a crowd can contribute predictive hypotheses to a model of residential electric energy consumption. In this experiment, the crowd generated hypotheses about factors that make one home different from another in terms of monthly energy usage. To implement this concept, we deployed a web-based system within which 627 residential electricity customers posed 632 questions that they thought predictive of energy usage. While this occurred, the same group provided 110,573 answers to these questions as they accumulated. Thus users both suggested the hypotheses that drive a predictive model and provided the data upon which the model is built. We used the resulting question and answer data to build a predictive model of monthly electric energy consumption, using random forest regression. Because of the sparse nature of the answer data, careful statistical work was needed to ensure that these models are valid. The results indicate that the crowd can generate useful hypotheses, despite the sparse nature of the dataset.
Tasks
Published	2017-09-08
URL	http://arxiv.org/abs/1709.02739v1
PDF	http://arxiv.org/pdf/1709.02739v1.pdf
PWC	https://paperswithcode.com/paper/crowdsourcing-predictors-of-residential
Repo
Framework

On Quadratic Convergence of DC Proximal Newton Algorithm for Nonconvex Sparse Learning in High Dimensions


Title	On Quadratic Convergence of DC Proximal Newton Algorithm for Nonconvex Sparse Learning in High Dimensions
Authors	Xingguo Li, Lin F. Yang, Jason Ge, Jarvis Haupt, Tong Zhang, Tuo Zhao
Abstract	We propose a DC proximal Newton algorithm for solving nonconvex regularized sparse learning problems in high dimensions. Our proposed algorithm integrates the proximal Newton algorithm with multi-stage convex relaxation based on the difference of convex (DC) programming, and enjoys both strong computational and statistical guarantees. Specifically, by leveraging a sophisticated characterization of sparse modeling structures/assumptions (i.e., local restricted strong convexity and Hessian smoothness), we prove that within each stage of convex relaxation, our proposed algorithm achieves (local) quadratic convergence, and eventually obtains a sparse approximate local optimum with optimal statistical properties after only a few convex relaxations. Numerical experiments are provided to support our theory.
Tasks	Sparse Learning
Published	2017-06-19
URL	http://arxiv.org/abs/1706.06066v3
PDF	http://arxiv.org/pdf/1706.06066v3.pdf
PWC	https://paperswithcode.com/paper/on-quadratic-convergence-of-dc-proximal-1
Repo
Framework

Ensemble Classifier for Eye State Classification using EEG Signals


Title	Ensemble Classifier for Eye State Classification using EEG Signals
Authors	Ali Al-Taei
Abstract	The growing importance and utilization of measuring brain waves (e.g. EEG signals of eye state) in brain-computer interface (BCI) applications highlighted the need for suitable classification methods. In this paper, a comparison between three of well-known classification methods (i.e. support vector machine (SVM), hidden Markov map (HMM), and radial basis function (RBF)) for EEG based eye state classification was achieved. Furthermore, a suggested method that is based on ensemble model was tested. The suggested (ensemble system) method based on a voting algorithm with two kernels: random forest (RF) and Kstar classification methods. The performance was tested using three measurement parameters: accuracy, mean absolute error (MAE), and confusion matrix. Results showed that the proposed method outperforms the other tested methods. For instance, the suggested method’s performance was 97.27% accuracy and 0.13 MAE.
Tasks	EEG
Published	2017-09-25
URL	http://arxiv.org/abs/1709.08590v2
PDF	http://arxiv.org/pdf/1709.08590v2.pdf
PWC	https://paperswithcode.com/paper/ensemble-classifier-for-eye-state
Repo
Framework

Automatic Skin Lesion Segmentation using Semi-supervised Learning Technique


Title	Automatic Skin Lesion Segmentation using Semi-supervised Learning Technique
Authors	S. M. Jaisakthi, Aravindan Chandrabose, P. Mirunalini
Abstract	Skin cancer is the most common of all cancers and each year million cases of skin cancer are treated. Treating and curing skin cancer is easy, if it is diagnosed and treated at an early stage. In this work we propose an automatic technique for skin lesion segmentation in dermoscopic images which helps in classifying the skin cancer types. The proposed method comprises of two major phases (1) preprocessing and (2) segmentation using semi-supervised learning algorithm. In the preprocessing phase noise are removed using filtering technique and in the segmentation phase skin lesions are segmented based on clustering technique. K-means clustering algorithm is used to cluster the preprocessed images and skin lesions are filtered from these clusters based on the color feature. Color of the skin lesions are learned from the training images using histograms calculations in RGB color space. The training images were downloaded from the ISIC 2017 challenge website and the experimental results were evaluated using validation and test sets.
Tasks	Lesion Segmentation
Published	2017-03-13
URL	http://arxiv.org/abs/1703.04301v1
PDF	http://arxiv.org/pdf/1703.04301v1.pdf
PWC	https://paperswithcode.com/paper/automatic-skin-lesion-segmentation-using-semi
Repo
Framework

Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration


Title	Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
Authors	Jason Altschuler, Jonathan Weed, Philippe Rigollet
Abstract	Computing optimal transport distances such as the earth mover’s distance is a fundamental problem in machine learning, statistics, and computer vision. Despite the recent introduction of several algorithms with good empirical performance, it is unknown whether general optimal transport distances can be approximated in near-linear time. This paper demonstrates that this ambitious goal is in fact achieved by Cuturi’s Sinkhorn Distances. This result relies on a new analysis of Sinkhorn iteration, which also directly suggests a new greedy coordinate descent algorithm, Greenkhorn, with the same theoretical guarantees. Numerical simulations illustrate that Greenkhorn significantly outperforms the classical Sinkhorn algorithm in practice.
Tasks
Published	2017-05-26
URL	http://arxiv.org/abs/1705.09634v2
PDF	http://arxiv.org/pdf/1705.09634v2.pdf
PWC	https://paperswithcode.com/paper/near-linear-time-approximation-algorithms-for
Repo
Framework

Image matting with normalized weight and semi-supervised learning


Title	Image matting with normalized weight and semi-supervised learning
Authors	Ping Li, Tingyan Duan, Yongfeng Cao
Abstract	Image matting is an important vision problem. The main stream methods for it combine sampling-based methods and propagation-based methods. In this paper, we deal with the combination with a normalized weighting parameter, which could well control the relative relationship between information from sampling and from propagation. A reasonable value range for this parameter is given based on statistics from the standard benchmark dataset. The matting is further improved by introducing semi-supervised learning iterations, which automatically refine the trimap without user’s interaction. This is especially beneficial when the trimap is coarse. The experimental results on standard benchmark dataset have shown that both the normalized weighting parameter and the semi-supervised learning iteration could significantly improve the matting performance.
Tasks	Image Matting
Published	2017-10-27
URL	http://arxiv.org/abs/1710.10101v1
PDF	http://arxiv.org/pdf/1710.10101v1.pdf
PWC	https://paperswithcode.com/paper/image-matting-with-normalized-weight-and-semi
Repo
Framework

A Hierarchical Image Matting Model for Blood Vessel Segmentation in Fundus images


Title	A Hierarchical Image Matting Model for Blood Vessel Segmentation in Fundus images
Authors	Zhun Fan, Jiewei Lu, Wenji Li, Caimin Wei, Han Huang, Xinye Cai, Xinjian Chen
Abstract	In this paper, a hierarchical image matting model is proposed to extract blood vessels from fundus images. More specifically, a hierarchical strategy utilizing the continuity and extendibility of retinal blood vessels is integrated into the image matting model for blood vessel segmentation. Normally the matting models require the user specified trimap, which separates the input image into three regions manually: the foreground, background and unknown regions. However, since creating a user specified trimap is a tedious and time-consuming task, region features of blood vessels are used to generate the trimap automatically in this paper. The proposed model has low computational complexity and outperforms many other state-ofart supervised and unsupervised methods in terms of accuracy, which achieves a vessel segmentation accuracy of 96:0%, 95:7% and 95:1% in an average time of 10:72s, 15:74s and 50:71s on images from three publicly available fundus image datasets DRIVE, STARE, and CHASE DB1, respectively.
Tasks	Image Matting
Published	2017-01-04
URL	http://arxiv.org/abs/1701.00892v3
PDF	http://arxiv.org/pdf/1701.00892v3.pdf
PWC	https://paperswithcode.com/paper/a-hierarchical-image-matting-model-for-blood
Repo
Framework

The Deep Poincaré Map: A Novel Approach for Left Ventricle Segmentation


Title	The Deep Poincaré Map: A Novel Approach for Left Ventricle Segmentation
Authors	Yuanhan Mo, Fangde Liu, Douglas McIlwraith, Guang Yang, Jingqing Zhang, Taigang He, Yike Guo
Abstract	Precise segmentation of the left ventricle (LV) within cardiac MRI images is a prerequisite for the quantitative measurement of heart function. However, this task is challenging due to the limited availability of labeled data and motion artifacts from cardiac imaging. In this work, we present an iterative segmentation algorithm for LV delineation. By coupling deep learning with a novel dynamic-based labeling scheme, we present a new methodology where a policy model is learned to guide an agent to travel over the the image, tracing out a boundary of the ROI – using the magnitude difference of the Poincar'e map as a stopping criterion. Our method is evaluated on two datasets, namely the Sunnybrook Cardiac Dataset (SCD) and data from the STACOM 2011 LV segmentation challenge. Our method outperforms the previous research over many metrics. In order to demonstrate the transferability of our method we present encouraging results over the STACOM 2011 data, when using a model trained on the SCD dataset.
Tasks
Published	2017-03-27
URL	http://arxiv.org/abs/1703.09200v2
PDF	http://arxiv.org/pdf/1703.09200v2.pdf
PWC	https://paperswithcode.com/paper/the-deep-poincare-map-a-novel-approach-for
Repo
Framework

Weather Forecasting Error in Solar Energy Forecasting


Title	Weather Forecasting Error in Solar Energy Forecasting
Authors	Hossein Sangrody, Morteza Sarailoo, Ning Zhou, Nhu Tran, Mahdi Motalleb, Elham Foruzan
Abstract	As renewable distributed energy resources (DERs) penetrate the power grid at an accelerating speed, it is essential for operators to have accurate solar photovoltaic (PV) energy forecasting for efficient operations and planning. Generally, observed weather data are applied in the solar PV generation forecasting model while in practice the energy forecasting is based on forecasted weather data. In this paper, a study on the uncertainty in weather forecasting for the most commonly used weather variables is presented. The forecasted weather data for six days ahead is compared with the observed data and the results of analysis are quantified by statistical metrics. In addition, the most influential weather predictors in energy forecasting model are selected. The performance of historical and observed weather data errors is assessed using a solar PV generation forecasting model. Finally, a sensitivity test is performed to identify the influential weather variables whose accurate values can significantly improve the results of energy forecasting.
Tasks	Weather Forecasting
Published	2017-09-24
URL	http://arxiv.org/abs/1709.08135v1
PDF	http://arxiv.org/pdf/1709.08135v1.pdf
PWC	https://paperswithcode.com/paper/weather-forecasting-error-in-solar-energy
Repo
Framework

Attributed Network Embedding for Learning in a Dynamic Environment


Title	Attributed Network Embedding for Learning in a Dynamic Environment
Authors	Jundong Li, Harsh Dani, Xia Hu, Jiliang Tang, Yi Chang, Huan Liu
Abstract	Network embedding leverages the node proximity manifested to learn a low-dimensional node vector representation for each node in the network. The learned embeddings could advance various learning tasks such as node classification, network clustering, and link prediction. Most, if not all, of the existing works, are overwhelmingly performed in the context of plain and static networks. Nonetheless, in reality, network structure often evolves over time with addition/deletion of links and nodes. Also, a vast majority of real-world networks are associated with a rich set of node attributes, and their attribute values are also naturally changing, with the emerging of new content patterns and the fading of old content patterns. These changing characteristics motivate us to seek an effective embedding representation to capture network and attribute evolving patterns, which is of fundamental importance for learning in a dynamic environment. To our best knowledge, we are the first to tackle this problem with the following two challenges: (1) the inherently correlated network and node attributes could be noisy and incomplete, it necessitates a robust consensus representation to capture their individual properties and correlations; (2) the embedding learning needs to be performed in an online fashion to adapt to the changes accordingly. In this paper, we tackle this problem by proposing a novel dynamic attributed network embedding framework - DANE. In particular, DANE first provides an offline method for a consensus embedding and then leverages matrix perturbation theory to maintain the freshness of the end embedding results in an online manner. We perform extensive experiments on both synthetic and real attributed networks to corroborate the effectiveness and efficiency of the proposed framework.
Tasks	Link Prediction, Network Embedding, Node Classification
Published	2017-06-06
URL	http://arxiv.org/abs/1706.01860v2
PDF	http://arxiv.org/pdf/1706.01860v2.pdf
PWC	https://paperswithcode.com/paper/attributed-network-embedding-for-learning-in
Repo
Framework


Title	Towards a science of human stories: using sentiment analysis and emotional arcs to understand the building blocks of complex social systems
Authors	Andrew J. Reagan
Abstract	Given the growing assortment of sentiment measuring instruments, it is imperative to understand which aspects of sentiment dictionaries contribute to both their classification accuracy and their ability to provide richer understanding of texts. Here, we perform detailed, quantitative tests and qualitative assessments of 6 dictionary-based methods applied, and briefly examine a further 20 methods. We show that while inappropriate for sentences, dictionary-based methods are generally robust in their classification accuracy for longer texts. Stories often following distinct emotional trajectories, forming patterns that are meaningful to us. By classifying the emotional arcs for a filtered subset of 4,803 stories from Project Gutenberg’s fiction collection, we find a set of six core trajectories which form the building blocks of complex narratives. Of profound scientific interest will be the degree to which we can eventually understand the full landscape of human stories, and data driven approaches will play a crucial role. Finally, we utilize web-scale data from Twitter to study the limits of what social data can tell us about public health, mental illness, discourse around the protest movement of #BlackLivesMatter, discourse around climate change, and hidden networks. We conclude with a review of published works in complex systems that separately analyze charitable donations, the happiness of words in 10 languages, 100 years of daily temperature data across the United States, and Australian Rules Football games.
Tasks	Sentiment Analysis
Published	2017-12-17
URL	http://arxiv.org/abs/1712.06163v1
PDF	http://arxiv.org/pdf/1712.06163v1.pdf
PWC	https://paperswithcode.com/paper/towards-a-science-of-human-stories-using
Repo
Framework

Preferential Bayesian Optimization


Title	Preferential Bayesian Optimization
Authors	Javier Gonzalez, Zhenwen Dai, Andreas Damianou, Neil D. Lawrence
Abstract	Bayesian optimization (BO) has emerged during the last few years as an effective approach to optimizing black-box functions where direct queries of the objective are expensive. In this paper we consider the case where direct access to the function is not possible, but information about user preferences is. Such scenarios arise in problems where human preferences are modeled, such as A/B tests or recommender systems. We present a new framework for this scenario that we call Preferential Bayesian Optimization (PBO) which allows us to find the optimum of a latent function that can only be queried through pairwise comparisons, the so-called duels. PBO extends the applicability of standard BO ideas and generalizes previous discrete dueling approaches by modeling the probability of the winner of each duel by means of a Gaussian process model with a Bernoulli likelihood. The latent preference function is used to define a family of acquisition functions that extend usual policies used in BO. We illustrate the benefits of PBO in a variety of experiments, showing that PBO needs drastically fewer comparisons for finding the optimum. According to our experiments, the way of modeling correlations in PBO is key in obtaining this advantage.
Tasks	Recommendation Systems
Published	2017-04-12
URL	http://arxiv.org/abs/1704.03651v1
PDF	http://arxiv.org/pdf/1704.03651v1.pdf
PWC	https://paperswithcode.com/paper/preferential-bayesian-optimization
Repo
Framework