April 2, 2020

3337 words 16 mins read

Paper Group ANR 202

Estimating Aggregate Properties In Relational Networks With Unobserved Data. Learning Graph Embedding with Limited Labeled Data: An Efficient Sampling Approach. Robust Estimation, Prediction and Control with Linear Dynamics and Generic Costs. Risk-Averse Learning by Temporal Difference Methods. Multi-Class Classification from Noisy-Similarity-Label …

Estimating Aggregate Properties In Relational Networks With Unobserved Data


Title	Estimating Aggregate Properties In Relational Networks With Unobserved Data
Authors	Varun Embar, Sriram Srinivasan, Lise Getoor
Abstract	Aggregate network properties such as cluster cohesion and the number of bridge nodes can be used to glean insights about a network’s community structure, spread of influence and the resilience of the network to faults. Efficiently computing network properties when the network is fully observed has received significant attention (Wasserman and Faust 1994; Cook and Holder 2006), however the problem of computing aggregate network properties when there is missing data attributes has received little attention. Computing these properties for networks with missing attributes involves performing inference over the network. Statistical relational learning (SRL) and graph neural networks (GNNs) are two classes of machine learning approaches well suited for inferring missing attributes in a graph. In this paper, we study the effectiveness of these approaches in estimating aggregate properties on networks with missing attributes. We compare two SRL approaches and three GNNs. For these approaches we estimate these properties using point estimates such as MAP and mean. For SRL-based approaches that can infer a joint distribution over the missing attributes, we also estimate these properties as an expectation over the distribution. To compute the expectation tractably for probabilistic soft logic, one of the SRL approaches that we study, we introduce a novel sampling framework. In the experimental evaluation, using three benchmark datasets, we show that SRL-based approaches tend to outperform GNN-based approaches both in computing aggregate properties and predictive accuracy. Specifically, we show that estimating the aggregate properties as an expectation over the joint distribution outperforms point estimates.
Tasks	Relational Reasoning
Published	2020-01-16
URL	https://arxiv.org/abs/2001.05617v2
PDF	https://arxiv.org/pdf/2001.05617v2.pdf
PWC	https://paperswithcode.com/paper/estimating-aggregate-properties-in-relational
Repo
Framework

Learning Graph Embedding with Limited Labeled Data: An Efficient Sampling Approach


Title	Learning Graph Embedding with Limited Labeled Data: An Efficient Sampling Approach
Authors	Qirui Li, Xiaoming Liu, Chao Shen, Xi Peng, Yadong Zhou, Xiaohong Guan
Abstract	Semi-supervised graph embedding methods represented by graph convolutional network has become one of the most popular methods for utilizing deep learning approaches to process the graph-based data for applications. Mostly existing work focus on designing novel algorithm structure to improve the performance, but ignore one common training problem, i.e., could these methods achieve the same performance with limited labelled data? To tackle this research gap, we propose a sampling-based training framework for semi-supervised graph embedding methods to achieve better performance with smaller training data set. The key idea is to integrate the sampling theory and embedding methods by a pipeline form, which has the following advantages: 1) the sampled training data can maintain more accurate graph characteristics than uniformly chosen data, which eliminates the model deviation; 2) the smaller scale of training data is beneficial to reduce the human resource cost to label them; The extensive experiments show that the sampling-based method can achieve the same performance only with 10$%$-50$%$ of the scale of training data. It verifies that the framework could extend the existing semi-supervised methods to the scenarios with the extremely small scale of labelled data.
Tasks	Graph Embedding
Published	2020-03-13
URL	https://arxiv.org/abs/2003.06100v1
PDF	https://arxiv.org/pdf/2003.06100v1.pdf
PWC	https://paperswithcode.com/paper/learning-graph-embedding-with-limited-labeled
Repo
Framework

Robust Estimation, Prediction and Control with Linear Dynamics and Generic Costs


Title	Robust Estimation, Prediction and Control with Linear Dynamics and Generic Costs
Authors	Edouard Leurent, Denis Efimov, Odalric-Ambrym Maillard
Abstract	We develop a framework for the adaptive model predictive control of a linear system with unknown parameters and arbitrary bounded costs, in a critical setting where failures are costly and should be prevented at all time. Our approach builds on two ideas: first, we incorporate prior knowledge of the dynamics in the form of a known structure that shapes uncertainty, which can be tightened as we collect interaction data by building high-confidence regions through least-square regression. Second, in order to handle this uncertainty we formulate a robust control objective. Leveraging tools from the interval prediction literature, we convert the confidence regions on parameters into confidence sets on trajectories induced by the controls. These controls are then optimised resorting to tree-based planning methods. We eventually relax our modeling assumptions with a multi-model extension based on a data-driven robust model selection mechanism. The full procedure is designed to produce reasonable and safe behaviours at deployment while recovering an asymptotic optimality. We illustrate it on a practical case of autonomous driving at a crossroads intersection among vehicles with uncertain behaviours.
Tasks	Autonomous Driving, Model Selection
Published	2020-02-25
URL	https://arxiv.org/abs/2002.10816v1
PDF	https://arxiv.org/pdf/2002.10816v1.pdf
PWC	https://paperswithcode.com/paper/robust-estimation-prediction-and-control-with
Repo
Framework

Risk-Averse Learning by Temporal Difference Methods


Title	Risk-Averse Learning by Temporal Difference Methods
Authors	Umit Kose, Andrzej Ruszczynski
Abstract	We consider reinforcement learning with performance evaluated by a dynamic risk measure. We construct a projected risk-averse dynamic programming equation and study its properties. Then we propose risk-averse counterparts of the methods of temporal differences and we prove their convergence with probability one. We also perform an empirical study on a complex transportation problem.
Tasks
Published	2020-03-02
URL	https://arxiv.org/abs/2003.00780v1
PDF	https://arxiv.org/pdf/2003.00780v1.pdf
PWC	https://paperswithcode.com/paper/risk-averse-learning-by-temporal-difference
Repo
Framework

Multi-Class Classification from Noisy-Similarity-Labeled Data


Title	Multi-Class Classification from Noisy-Similarity-Labeled Data
Authors	Songhua Wu, Xiaobo Xia, Tongliang Liu, Bo Han, Mingming Gong, Nannan Wang, Haifeng Liu, Gang Niu
Abstract	A similarity label indicates whether two instances belong to the same class while a class label shows the class of the instance. Without class labels, a multi-class classifier could be learned from similarity-labeled pairwise data by meta classification learning. However, since the similarity label is less informative than the class label, it is more likely to be noisy. Deep neural networks can easily remember noisy data, leading to overfitting in classification. In this paper, we propose a method for learning from only noisy-similarity-labeled data. Specifically, to model the noise, we employ a noise transition matrix to bridge the class-posterior probability between clean and noisy data. We further estimate the transition matrix from only noisy data and build a novel learning system to learn a classifier which can assign noise-free class labels for instances. Moreover, we theoretically justify how our proposed method generalizes for learning classifiers. Experimental results demonstrate the superiority of the proposed method over the state-of-the-art method on benchmark-simulated and real-world noisy-label datasets.
Tasks
Published	2020-02-16
URL	https://arxiv.org/abs/2002.06508v1
PDF	https://arxiv.org/pdf/2002.06508v1.pdf
PWC	https://paperswithcode.com/paper/multi-class-classification-from-noisy
Repo
Framework


Title	Predicting event attendance exploring social influence
Authors	Fatemeh Salehi Rizi, Michael Granitzer
Abstract	The problem of predicting people’s participation in real-world events has received considerable attention as it offers valuable insights for human behavior analysis and event-related advertisement. Today social networks (e.g. Twitter) widely reflect large popular events where people discuss their interest with friends. Event participants usually stimulate friends to join the event which propagates a social influence in the network. In this paper, we propose to model the social influence of friends on event attendance. We consider non-geotagged posts besides structures of social groups to infer users’ attendance. To leverage the information on network topology we apply some of recent graph embedding techniques such as node2vec, HARP and Poincar`e. We describe the approach followed to design the feature space and feed it to a neural network. The performance evaluation is conducted using two large music festivals datasets, namely the VFestival and Creamfields. The experimental results show that our classifier outperforms the state-of-the-art baseline with 89% accuracy observed for the VFestival dataset. \|
Tasks	Graph Embedding
Published	2020-02-16
URL	https://arxiv.org/abs/2002.06665v1
PDF	https://arxiv.org/pdf/2002.06665v1.pdf
PWC	https://paperswithcode.com/paper/predicting-event-attendance-exploring-social
Repo
Framework

Vehicle-Human Interactive Behaviors in Emergency: Data Extraction from Traffic Accident Videos


Title	Vehicle-Human Interactive Behaviors in Emergency: Data Extraction from Traffic Accident Videos
Authors	Wansong Liu, Danyang Luo, Changxu Wu, Minghui Zheng
Abstract	Currently, studying the vehicle-human interactive behavior in the emergency needs a large amount of datasets in the actual emergent situations that are almost unavailable. Existing public data sources on autonomous vehicles (AVs) mainly focus either on the normal driving scenarios or on emergency situations without human involvement. To fill this gap and facilitate related research, this paper provides a new yet convenient way to extract the interactive behavior data (i.e., the trajectories of vehicles and humans) from actual accident videos that were captured by both the surveillance cameras and driving recorders. The main challenge for data extraction from real-time accident video lies in the fact that the recording cameras are un-calibrated and the angles of surveillance are unknown. The approach proposed in this paper employs image processing to obtain a new perspective which is different from the original video’s perspective. Meanwhile, we manually detect and mark object feature points in each image frame. In order to acquire a gradient of reference ratios, a geometric model is implemented in the analysis of reference pixel value, and the feature points are then scaled to the object trajectory based on the gradient of ratios. The generated trajectories not only restore the object movements completely but also reflect changes in vehicle velocity and rotation based on the feature points distributions.
Tasks	Autonomous Vehicles
Published	2020-03-02
URL	https://arxiv.org/abs/2003.02059v1
PDF	https://arxiv.org/pdf/2003.02059v1.pdf
PWC	https://paperswithcode.com/paper/vehicle-human-interactive-behaviors-in
Repo
Framework

Automatic Signboard Detection from Natural Scene Image in Context of Bangladesh Google Street View


Title	Automatic Signboard Detection from Natural Scene Image in Context of Bangladesh Google Street View
Authors	Md. Sadrul Islam Toaha, Chowdhury Rafeed Rahman, Sakib Bin Asad, Tashin Ahmed, Mahfuz Ara Proma, S. M. Shahriar Haque
Abstract	Automatic signboard region detection is the first step of information extraction about establishments from an image, especially when there is a complex background and multiple signboard regions are present in the image. Automatic signboard detection in Bangladesh is a challenging task because of low quality street view image, presence of overlapping objects and presence of signboard like objects which are not actually signboards. In this research, we provide a novel dataset from the perspective of Bangladesh city streets with an aim of signboard detection, namely Bangladesh Street View Signboard Objects (BSVSO) image dataset. We introduce a novel approach to detect signboard accurately by applying smart image processing techniques and statistically determined hyperparameter based deep learning method, Faster R-CNN. Comparison of different variations of this segmentation based learning method have also been performed in this research.
Tasks
Published	2020-03-04
URL	https://arxiv.org/abs/2003.01936v2
PDF	https://arxiv.org/pdf/2003.01936v2.pdf
PWC	https://paperswithcode.com/paper/automatic-signboard-detection-from-natural
Repo
Framework

Convergence to Second-Order Stationarity for Non-negative Matrix Factorization: Provably and Concurrently


Title	Convergence to Second-Order Stationarity for Non-negative Matrix Factorization: Provably and Concurrently
Authors	Ioannis Panageas, Stratis Skoulakis, Antonios Varvitsiotis, Xiao Wang
Abstract	Non-negative matrix factorization (NMF) is a fundamental non-convex optimization problem with numerous applications in Machine Learning (music analysis, document clustering, speech-source separation etc). Despite having received extensive study, it is poorly understood whether or not there exist natural algorithms that can provably converge to a local minimum. Part of the reason is because the objective is heavily symmetric and its gradient is not Lipschitz. In this paper we define a multiplicative weight update type dynamics (modification of the seminal Lee-Seung algorithm) that runs concurrently and provably avoids saddle points (first order stationary points that are not second order). Our techniques combine tools from dynamical systems such as stability and exploit the geometry of the NMF objective by reducing the standard NMF formulation over the non-negative orthant to a new formulation over (a scaled) simplex. An important advantage of our method is the use of concurrent updates, which permits implementations in parallel computing environments.
Tasks
Published	2020-02-26
URL	https://arxiv.org/abs/2002.11323v2
PDF	https://arxiv.org/pdf/2002.11323v2.pdf
PWC	https://paperswithcode.com/paper/convergence-to-second-order-stationarity-for
Repo
Framework

An interpretable semi-supervised classifier using two different strategies for amended self-labeling


Title	An interpretable semi-supervised classifier using two different strategies for amended self-labeling
Authors	Isel Grau, Dipankar Sengupta, Maria M. Garcia Lorenzo, Ann Nowe
Abstract	In the context of some machine learning applications, obtaining data instances is a relatively easy process but labeling them could become quite expensive or tedious. Such scenarios lead to datasets with few labeled instances and a larger number of unlabeled ones. Semi-supervised classification techniques combine labeled and unlabeled data during the learning phase in order to increase classifier’s generalization capability. Regrettably, most successful semi-supervised classifiers do not allow explaining their outcome, thus behaving like black boxes. However, there is an increasing number of problem domains in which experts demand a clear understanding of the decision process. In this paper, we report on an extended experimental study presenting an interpretable self-labeling grey-box classifier that uses a black box to estimate the missing class labels and a white box to make the final predictions. Two different approaches for amending the self-labeling process are explored: a first one based on the confidence of the black box and the latter one based on measures from Rough Set Theory. The results of the extended experimental study support the interpretability by means of transparency and simplicity of our classifier, while attaining superior prediction rates when compared with state-of-the-art self-labeling classifiers reported in the literature.
Tasks
Published	2020-01-26
URL	https://arxiv.org/abs/2001.09502v1
PDF	https://arxiv.org/pdf/2001.09502v1.pdf
PWC	https://paperswithcode.com/paper/an-interpretable-semi-supervised-classifier
Repo
Framework

Discovery of Self-Assembling $π$-Conjugated Peptides by Active Learning-Directed Coarse-Grained Molecular Simulation


Title	Discovery of Self-Assembling $π$-Conjugated Peptides by Active Learning-Directed Coarse-Grained Molecular Simulation
Authors	Kirill Shmilovich, Rachael A. Mansbach, Hythem Sidky, Olivia E. Dunne, Sayak Subhra Panda, John D. Tovar, Andrew L. Ferguson
Abstract	Electronically-active organic molecules have demonstrated great promise as novel soft materials for energy harvesting and transport. Self-assembled nanoaggregates formed from $\pi$-conjugated oligopeptides composed of an aromatic core flanked by oligopeptide wings offer emergent optoelectronic properties within a water soluble and biocompatible substrate. Nanoaggregate properties can be controlled by tuning core chemistry and peptide composition, but the sequence-structure-function relations remain poorly characterized. In this work, we employ coarse-grained molecular dynamics simulations within an active learning protocol employing deep representational learning and Bayesian optimization to efficiently identify molecules capable of assembling pseudo-1D nanoaggregates with good stacking of the electronically-active $\pi$-cores. We consider the DXXX-OPV3-XXXD oligopeptide family, where D is an Asp residue and OPV3 is an oligophenylene vinylene oligomer (1,4-distyrylbenzene), to identify the top performing XXX tripeptides within all 20$^3$ = 8,000 possible sequences. By direct simulation of only 2.3% of this space, we identify molecules predicted to exhibit superior assembly relative to those reported in prior work. Spectral clustering of the top candidates reveals new design rules governing assembly. This work establishes new understanding of DXXX-OPV3-XXXD assembly, identifies promising new candidates for experimental testing, and presents a computational design platform that can be generically extended to other peptide-based and peptide-like systems.
Tasks	Active Learning
Published	2020-01-27
URL	https://arxiv.org/abs/2002.01563v1
PDF	https://arxiv.org/pdf/2002.01563v1.pdf
PWC	https://paperswithcode.com/paper/discovery-of-self-assembling-conjugated
Repo
Framework

Learning Non-Markovian Reward Models in MDPs


Title	Learning Non-Markovian Reward Models in MDPs
Authors	Gavin Rens, Jean-François Raskin
Abstract	There are situations in which an agent should receive rewards only after having accomplished a series of previous tasks. In other words, the reward that the agent receives is non-Markovian. One natural and quite general way to represent history-dependent rewards is via a Mealy machine; a finite state automaton that produces output sequences (rewards in our case) from input sequences (state/action observations in our case). In our formal setting, we consider a Markov decision process (MDP) that models the dynamic of the environment in which the agent evolves and a Mealy machine synchronised with this MDP to formalise the non-Markovian reward function. While the MDP is known by the agent, the reward function is unknown from the agent and must be learnt. Learning non-Markov reward functions is a challenge. Our approach to overcome this challenging problem is a careful combination of the Angluin’s L* active learning algorithm to learn finite automata, testing techniques for establishing conformance of finite model hypothesis and optimisation techniques for computing optimal strategies in Markovian (immediate) reward MDPs. We also show how our framework can be combined with classical heuristics such as Monte Carlo Tree Search. We illustrate our algorithms and a preliminary implementation on two typical examples for AI.
Tasks	Active Learning
Published	2020-01-25
URL	https://arxiv.org/abs/2001.09293v1
PDF	https://arxiv.org/pdf/2001.09293v1.pdf
PWC	https://paperswithcode.com/paper/learning-non-markovian-reward-models-in-mdps
Repo
Framework

Projection based Active Gaussian Process Regression for Pareto Front Modeling


Title	Projection based Active Gaussian Process Regression for Pareto Front Modeling
Authors	Zhengqi Gao, Jun Tao, Yangfeng Su, Dian Zhou, Xuan Zeng
Abstract	Pareto Front (PF) modeling is essential in decision making problems across all domains such as economics, medicine or engineering. In Operation Research literature, this task has been addressed based on multi-objective optimization algorithms. However, without learning models for PF, these methods cannot examine whether a new provided point locates on PF or not. In this paper, we reconsider the task from Data Mining perspective. A novel projection based active Gaussian process regression (P- aGPR) method is proposed for efficient PF modeling. First, P- aGPR chooses a series of projection spaces with dimensionalities ranking from low to high. Next, in each projection space, a Gaussian process regression (GPR) model is trained to represent the constraint that PF should satisfy in that space. Moreover, in order to improve modeling efficacy and stability, an active learning framework has been developed by exploiting the uncertainty information obtained in the GPR models. Different from all existing methods, our proposed P-aGPR method can not only provide a generative PF model, but also fast examine whether a provided point locates on PF or not. The numerical results demonstrate that compared to state-of-the-art passive learning methods the proposed P-aGPR method can achieve higher modeling accuracy and stability.
Tasks	Active Learning, Decision Making
Published	2020-01-20
URL	https://arxiv.org/abs/2001.07072v1
PDF	https://arxiv.org/pdf/2001.07072v1.pdf
PWC	https://paperswithcode.com/paper/projection-based-active-gaussian-process
Repo
Framework

A Difference-of-Convex Programming Approach With Parallel Branch-and-Bound For Sentence Compression Via A Hybrid Extractive Model


Title	A Difference-of-Convex Programming Approach With Parallel Branch-and-Bound For Sentence Compression Via A Hybrid Extractive Model
Authors	Yi-Shuai Niu, Yu You, Wenxu Xu, Wentao Ding, Junpeng Hu
Abstract	Sentence compression is an important problem in natural language processing with wide applications in text summarization, search engine and human-AI interaction system etc. In this paper, we design a hybrid extractive sentence compression model combining a probability language model and a parse tree language model for compressing sentences by guaranteeing the syntax correctness of the compression results. Our compression model is formulated as an integer linear programming problem, which can be rewritten as a Difference-of-Convex (DC) programming problem based on the exact penalty technique. We use a well known efficient DC algorithm – DCA to handle the penalized problem for local optimal solutions. Then a hybrid global optimization algorithm combining DCA with a parallel branch-and-bound framework, namely PDCABB, is used for finding global optimal solutions. Numerical results demonstrate that our sentence compression model can provide excellent compression results evaluated by F-score, and indicate that PDCABB is a promising algorithm for solving our sentence compression model.
Tasks	Language Modelling, Sentence Compression, Text Summarization
Published	2020-02-02
URL	https://arxiv.org/abs/2002.01352v1
PDF	https://arxiv.org/pdf/2002.01352v1.pdf
PWC	https://paperswithcode.com/paper/a-difference-of-convex-programming-approach
Repo
Framework

GRET: Global Representation Enhanced Transformer


Title	GRET: Global Representation Enhanced Transformer
Authors	Rongxiang Weng, Haoran Wei, Shujian Huang, Heng Yu, Lidong Bing, Weihua Luo, Jiajun Chen
Abstract	Transformer, based on the encoder-decoder framework, has achieved state-of-the-art performance on several natural language generation tasks. The encoder maps the words in the input sentence into a sequence of hidden states, which are then fed into the decoder to generate the output sentence. These hidden states usually correspond to the input words and focus on capturing local information. However, the global (sentence level) information is seldom explored, leaving room for the improvement of generation quality. In this paper, we propose a novel global representation enhanced Transformer (GRET) to explicitly model global representation in the Transformer network. Specifically, in the proposed model, an external state is generated for the global representation from the encoder. The global representation is then fused into the decoder during the decoding process to improve generation quality. We conduct experiments in two text generation tasks: machine translation and text summarization. Experimental results on four WMT machine translation tasks and LCSTS text summarization task demonstrate the effectiveness of the proposed approach on natural language generation.
Tasks	Machine Translation, Text Generation, Text Summarization
Published	2020-02-24
URL	https://arxiv.org/abs/2002.10101v1
PDF	https://arxiv.org/pdf/2002.10101v1.pdf
PWC	https://paperswithcode.com/paper/gret-global-representation-enhanced
Repo
Framework