October 19, 2019

2845 words 14 mins read

Paper Group ANR 120

Paper Group ANR 120

Entropic Spectral Learning for Large-Scale Graphs. Connectivity in Random Annulus Graphs and the Geometric Block Model. Discretizing Logged Interaction Data Biases Learning for Decision-Making. Evaluating Text GANs as Language Models. Stochastic Block Models with Multiple Continuous Attributes. Instance Optimal Decoding and the Restricted Isometry …

Entropic Spectral Learning for Large-Scale Graphs

Title Entropic Spectral Learning for Large-Scale Graphs
Authors Diego Granziol, Binxin Ru, Stefan Zohren, Xiaowen Dong, Michael Osborne, Stephen Roberts
Abstract Graph spectra have been successfully used to classify network types, compute the similarity between graphs, and determine the number of communities in a network. For large graphs, where an eigen-decomposition is infeasible, iterative moment matched approximations to the spectra and kernel smoothing are typically used. We show that the underlying moment information is lost when using kernel smoothing. We further propose a spectral density approximation based on the method of Maximum Entropy, for which we develop a new algorithm. This method matches moments exactly and is everywhere positive. We demonstrate its effectiveness and superiority over existing approaches in learning graph spectra, via experiments on both synthetic networks, such as the Erd\H{o}s-R'{e}nyi and Barab'{a}si-Albert random graphs, and real-world networks, such as the social networks for Orkut, YouTube, and Amazon from the SNAP dataset.
Tasks Community Detection
Published 2018-04-18
URL http://arxiv.org/abs/1804.06802v2
PDF http://arxiv.org/pdf/1804.06802v2.pdf
PWC https://paperswithcode.com/paper/entropic-spectral-learning-in-large-scale
Repo
Framework

Connectivity in Random Annulus Graphs and the Geometric Block Model

Title Connectivity in Random Annulus Graphs and the Geometric Block Model
Authors Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, Barna Saha
Abstract We provide new connectivity results for {\em vertex-random graphs} or {\em random annulus graphs} which are significant generalizations of random geometric graphs. Random geometric graphs (RGG) are one of the most basic models of random graphs for spatial networks proposed by Gilbert in 1961, shortly after the introduction of the Erd\H{o}s-R'{en}yi random graphs. They resemble social networks in many ways (e.g. by spontaneously creating cluster of nodes with high modularity). The connectivity properties of RGG have been studied since its introduction, and analyzing them has been significantly harder than their Erd\H{o}s-R'{en}yi counterparts due to correlated edge formation. Our next contribution is in using the connectivity of random annulus graphs to provide necessary and sufficient conditions for efficient recovery of communities for {\em the geometric block model} (GBM). The GBM is a probabilistic model for community detection defined over an RGG in a similar spirit as the popular {\em stochastic block model}, which is defined over an Erd\H{o}s-R'{en}yi random graph. The geometric block model inherits the transitivity properties of RGGs and thus models communities better than a stochastic block model. However, analyzing them requires fresh perspectives as all prior tools fail due to correlation in edge formation. We provide a simple and efficient algorithm that can recover communities in GBM exactly with high probability in the regime of connectivity.
Tasks Community Detection
Published 2018-04-12
URL http://arxiv.org/abs/1804.05013v2
PDF http://arxiv.org/pdf/1804.05013v2.pdf
PWC https://paperswithcode.com/paper/connectivity-in-random-annulus-graphs-and-the
Repo
Framework

Discretizing Logged Interaction Data Biases Learning for Decision-Making

Title Discretizing Logged Interaction Data Biases Learning for Decision-Making
Authors Peter Schulam, Suchi Saria
Abstract Time series data that are not measured at regular intervals are commonly discretized as a preprocessing step. For example, data about customer arrival times might be simplified by summing the number of arrivals within hourly intervals, which produces a discrete-time time series that is easier to model. In this abstract, we show that discretization introduces a bias that affects models trained for decision-making. We refer to this phenomenon as discretization bias, and show that we can avoid it by using continuous-time models instead.
Tasks Decision Making, Time Series
Published 2018-10-06
URL http://arxiv.org/abs/1810.03025v1
PDF http://arxiv.org/pdf/1810.03025v1.pdf
PWC https://paperswithcode.com/paper/discretizing-logged-interaction-data-biases
Repo
Framework

Evaluating Text GANs as Language Models

Title Evaluating Text GANs as Language Models
Authors Guy Tevet, Gavriel Habib, Vered Shwartz, Jonathan Berant
Abstract Generative Adversarial Networks (GANs) are a promising approach for text generation that, unlike traditional language models (LM), does not suffer from the problem of ``exposure bias’'. However, A major hurdle for understanding the potential of GANs for text generation is the lack of a clear evaluation metric. In this work, we propose to approximate the distribution of text generated by a GAN, which permits evaluating them with traditional probability-based LM metrics. We apply our approximation procedure on several GAN-based models and show that they currently perform substantially worse than state-of-the-art LMs. Our evaluation procedure promotes better understanding of the relation between GANs and LMs, and can accelerate progress in GAN-based text generation. |
Tasks Text Generation
Published 2018-10-30
URL http://arxiv.org/abs/1810.12686v2
PDF http://arxiv.org/pdf/1810.12686v2.pdf
PWC https://paperswithcode.com/paper/evaluating-text-gans-as-language-models
Repo
Framework

Stochastic Block Models with Multiple Continuous Attributes

Title Stochastic Block Models with Multiple Continuous Attributes
Authors Natalie Stanley, Thomas Bonacci, Roland Kwitt, Marc Niethammer, Peter J. Mucha
Abstract The stochastic block model (SBM) is a probabilistic model for community structure in networks. Typically, only the adjacency matrix is used to perform SBM parameter inference. In this paper, we consider circumstances in which nodes have an associated vector of continuous attributes that are also used to learn the node-to-community assignments and corresponding SBM parameters. While this assumption is not realistic for every application, our model assumes that the attributes associated with the nodes in a network’s community can be described by a common multivariate Gaussian model. In this augmented, attributed SBM, the objective is to simultaneously learn the SBM connectivity probabilities with the multivariate Gaussian parameters describing each community. While there are recent examples in the literature that combine connectivity and attribute information to inform community detection, our model is the first augmented stochastic block model to handle multiple continuous attributes. This provides the flexibility in biological data to, for example, augment connectivity information with continuous measurements from multiple experimental modalities. Because the lack of labeled network data often makes community detection results difficult to validate, we highlight the usefulness of our model for two network prediction tasks: link prediction and collaborative filtering. As a result of fitting this attributed stochastic block model, one can predict the attribute vector or connectivity patterns for a new node in the event of the complementary source of information (connectivity or attributes, respectively). We also highlight two biological examples where the attributed stochastic block model provides satisfactory performance in the link prediction and collaborative filtering tasks.
Tasks Community Detection, Link Prediction
Published 2018-03-07
URL http://arxiv.org/abs/1803.02726v1
PDF http://arxiv.org/pdf/1803.02726v1.pdf
PWC https://paperswithcode.com/paper/stochastic-block-models-with-multiple
Repo
Framework

Instance Optimal Decoding and the Restricted Isometry Property

Title Instance Optimal Decoding and the Restricted Isometry Property
Authors Nicolas Keriven, Rémi Gribonval
Abstract In this paper, we address the question of information preservation in ill-posed, non-linear inverse problems, assuming that the measured data is close to a low-dimensional model set. We provide necessary and sufficient conditions for the existence of a so-called instance optimal decoder, i.e., that is robust to noise and modelling error. Inspired by existing results in compressive sensing, our analysis is based on a (Lower) Restricted Isometry Property (LRIP), formulated in a non-linear fashion. We also provide sufficient conditions for non-uniform recovery with random measurement operators, with a new formulation of the LRIP. We finish by describing typical strategies to prove the LRIP in both linear and non-linear cases, and illustrate our results by studying the invertibility of a one-layer neural net with random weights.
Tasks Compressive Sensing
Published 2018-02-27
URL http://arxiv.org/abs/1802.09905v2
PDF http://arxiv.org/pdf/1802.09905v2.pdf
PWC https://paperswithcode.com/paper/instance-optimal-decoding-and-the-restricted
Repo
Framework

LSTM-Based Goal Recognition in Latent Space

Title LSTM-Based Goal Recognition in Latent Space
Authors Leonardo Amado, João Paulo Aires, Ramon Fraga Pereira, Maurício C. Magnaguagno, Roger Granada, Felipe Meneguzzi
Abstract Approaches to goal recognition have progressively relaxed the requirements about the amount of domain knowledge and available observations, yielding accurate and efficient algorithms capable of recognizing goals. However, to recognize goals in raw data, recent approaches require either human engineered domain knowledge, or samples of behavior that account for almost all actions being observed to infer possible goals. This is clearly too strong a requirement for real-world applications of goal recognition, and we develop an approach that leverages advances in recurrent neural networks to perform goal recognition as a classification task, using encoded plan traces for training. We empirically evaluate our approach against the state-of-the-art in goal recognition with image-based domains, and discuss under which conditions our approach is superior to previous ones.
Tasks
Published 2018-08-15
URL http://arxiv.org/abs/1808.05249v2
PDF http://arxiv.org/pdf/1808.05249v2.pdf
PWC https://paperswithcode.com/paper/lstm-based-goal-recognition-in-latent-space
Repo
Framework

On Asymptotic Covariances of A Few Unrotated Factor Solutions

Title On Asymptotic Covariances of A Few Unrotated Factor Solutions
Authors Xingwei Hu
Abstract In this paper, we provide explicit formulas, in terms of the covariances of sample covariances or sample correlations, for the asymptotic covariances of unrotated factor loading estimates and unique variance estimates. These estimates are extracted from least square, principal, iterative principal component, alpha or image factor analysis. If the sample is taken from a multivariate normal population, these formulas, together with the delta methods, will produce the standard errors for the rotated loading estimates. A simulation study shows that the formulas provide reasonable results.
Tasks
Published 2018-11-12
URL http://arxiv.org/abs/1811.05336v1
PDF http://arxiv.org/pdf/1811.05336v1.pdf
PWC https://paperswithcode.com/paper/on-asymptotic-covariances-of-a-few-unrotated
Repo
Framework

Graph-based Security and Privacy Analytics via Collective Classification with Joint Weight Learning and Propagation

Title Graph-based Security and Privacy Analytics via Collective Classification with Joint Weight Learning and Propagation
Authors Binghui Wang, Jinyuan Jia, Neil Zhenqiang Gong
Abstract Many security and privacy problems can be modeled as a graph classification problem, where nodes in the graph are classified by collective classification simultaneously. State-of-the-art collective classification methods for such graph-based security and privacy analytics follow the following paradigm: assign weights to edges of the graph, iteratively propagate reputation scores of nodes among the weighted graph, and use the final reputation scores to classify nodes in the graph. The key challenge is to assign edge weights such that an edge has a large weight if the two corresponding nodes have the same label, and a small weight otherwise. Although collective classification has been studied and applied for security and privacy problems for more than a decade, how to address this challenge is still an open question. In this work, we propose a novel collective classification framework to address this long-standing challenge. We first formulate learning edge weights as an optimization problem, which quantifies the goals about the final reputation scores that we aim to achieve. However, it is computationally hard to solve the optimization problem because the final reputation scores depend on the edge weights in a very complex way. To address the computational challenge, we propose to jointly learn the edge weights and propagate the reputation scores, which is essentially an approximate solution to the optimization problem. We compare our framework with state-of-the-art methods for graph-based security and privacy analytics using four large-scale real-world datasets from various application scenarios such as Sybil detection in social networks, fake review detection in Yelp, and attribute inference attacks. Our results demonstrate that our framework achieves higher accuracies than state-of-the-art methods with an acceptable computational overhead.
Tasks Graph Classification
Published 2018-12-04
URL http://arxiv.org/abs/1812.01661v2
PDF http://arxiv.org/pdf/1812.01661v2.pdf
PWC https://paperswithcode.com/paper/graph-based-security-and-privacy-analytics
Repo
Framework

High Temperature Structure Detection in Ferromagnets

Title High Temperature Structure Detection in Ferromagnets
Authors Yuan Cao, Matey Neykov, Han Liu
Abstract This paper studies structure detection problems in high temperature ferromagnetic (positive interaction only) Ising models. The goal is to distinguish whether the underlying graph is empty, i.e., the model consists of independent Rademacher variables, versus the alternative that the underlying graph contains a subgraph of a certain structure. We give matching upper and lower minimax bounds under which testing this problem is possible/impossible respectively. Our results reveal that a key quantity called graph arboricity drives the testability of the problem. On the computational front, under a conjecture of the computational hardness of sparse principal component analysis, we prove that, unless the signal is strong enough, there are no polynomial time tests which are capable of testing this problem. In order to prove this result we exhibit a way to give sharp inequalities for the even moments of sums of i.i.d. Rademacher random variables which may be of independent interest.
Tasks
Published 2018-09-21
URL https://arxiv.org/abs/1809.08204v2
PDF https://arxiv.org/pdf/1809.08204v2.pdf
PWC https://paperswithcode.com/paper/high-temperature-structure-detection-in
Repo
Framework

Using Statistical and Semantic Models for Multi-Document Summarization

Title Using Statistical and Semantic Models for Multi-Document Summarization
Authors Divyanshu Daiya, Anukarsh Singh, Mukesh Jadon
Abstract We report a series of experiments with different semantic models on top of various statistical models for extractive text summarization. Though statistical models may better capture word co-occurrences and distribution around the text, they fail to detect the context and the sense of sentences /words as a whole. Semantic models help us gain better insight into the context of sentences. We show that how tuning weights between different models can help us achieve significant results on various benchmarks. Learning pre-trained vectors used in semantic models further, on given corpus, can give addition spike in performance. Using weighing techniques in between different statistical models too further refines our result. For Statistical models, we have used TF/IDF, TextRAnk, Jaccard/Cosine Similarities. For Semantic Models, we have used WordNet-based Model and proposed two models based on Glove Vectors and Facebook’s InferSent. We tested our approach on DUC 2004 dataset, generating 100-word summaries. We have discussed the system, algorithms, analysis and also proposed and tested possible improvements. ROUGE scores were used to compare to other summarizers.
Tasks Document Summarization, Multi-Document Summarization, Text Summarization
Published 2018-05-11
URL http://arxiv.org/abs/1805.04579v2
PDF http://arxiv.org/pdf/1805.04579v2.pdf
PWC https://paperswithcode.com/paper/using-statistical-and-semantic-models-for
Repo
Framework

A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitions

Title A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitions
Authors Pratik Gajane, Ronald Ortner, Peter Auer
Abstract We consider reinforcement learning in changing Markov Decision Processes where both the state-transition probabilities and the reward functions may vary over time. For this problem setting, we propose an algorithm using a sliding window approach and provide performance guarantees for the regret evaluated against the optimal non-stationary policy. We also characterize the optimal window size suitable for our algorithm. These results are complemented by a sample complexity bound on the number of sub-optimal steps taken by the algorithm. Finally, we present some experimental results to support our theoretical analysis.
Tasks
Published 2018-05-25
URL http://arxiv.org/abs/1805.10066v1
PDF http://arxiv.org/pdf/1805.10066v1.pdf
PWC https://paperswithcode.com/paper/a-sliding-window-algorithm-for-markov
Repo
Framework

Deep Cross Polarimetric Thermal-to-visible Face Recognition

Title Deep Cross Polarimetric Thermal-to-visible Face Recognition
Authors Seyed Mehdi Iranmanesh, Ali Dabouei, Hadi Kazemi, Nasser M. Nasrabadi
Abstract In this paper, we present a deep coupled learning frame- work to address the problem of matching polarimetric ther- mal face photos against a gallery of visible faces. Polariza- tion state information of thermal faces provides the miss- ing textural and geometrics details in the thermal face im- agery which exist in visible spectrum. we propose a coupled deep neural network architecture which leverages relatively large visible and thermal datasets to overcome the problem of overfitting and eventually we train it by a polarimetric thermal face dataset which is the first of its kind. The pro- posed architecture is able to make full use of the polari- metric thermal information to train a deep model compared to the conventional shallow thermal-to-visible face recogni- tion methods. Proposed coupled deep neural network also finds global discriminative features in a nonlinear embed- ding space to relate the polarimetric thermal faces to their corresponding visible faces. The results show the superior- ity of our method compared to the state-of-the-art models in cross thermal-to-visible face recognition algorithms.
Tasks Face Recognition
Published 2018-01-04
URL http://arxiv.org/abs/1801.01486v1
PDF http://arxiv.org/pdf/1801.01486v1.pdf
PWC https://paperswithcode.com/paper/deep-cross-polarimetric-thermal-to-visible
Repo
Framework

E-commerce Anomaly Detection: A Bayesian Semi-Supervised Tensor Decomposition Approach using Natural Gradients

Title E-commerce Anomaly Detection: A Bayesian Semi-Supervised Tensor Decomposition Approach using Natural Gradients
Authors Anil R. Yelundur, Srinivasan H. Sengamedu, Bamdev Mishra
Abstract Anomaly Detection has several important applications. In this paper, our focus is on detecting anomalies in seller-reviewer data using tensor decomposition. While tensor-decomposition is mostly unsupervised, we formulate Bayesian semi-supervised tensor decomposition to take advantage of sparse labeled data. In addition, we use Polya-Gamma data augmentation for the semi-supervised Bayesian tensor decomposition. Finally, we show that the P'olya-Gamma formulation simplifies calculation of the Fisher information matrix for partial natural gradient learning. Our experimental results show that our semi-supervised approach outperforms state of the art unsupervised baselines. And that the partial natural gradient learning outperforms stochastic gradient learning and Online-EM with sufficient statistics.
Tasks Anomaly Detection, Data Augmentation
Published 2018-04-11
URL http://arxiv.org/abs/1804.03836v3
PDF http://arxiv.org/pdf/1804.03836v3.pdf
PWC https://paperswithcode.com/paper/e-commerce-anomaly-detection-a-bayesian-semi
Repo
Framework

Improving Topic Models with Latent Feature Word Representations

Title Improving Topic Models with Latent Feature Word Representations
Authors Dat Quoc Nguyen, Richard Billingsley, Lan Du, Mark Johnson
Abstract Probabilistic topic models are widely used to discover latent topics in document collections, while latent feature vector representations of words have been used to obtain high performance in many NLP tasks. In this paper, we extend two different Dirichlet multinomial topic models by incorporating latent feature vector representations of words trained on very large corpora to improve the word-topic mapping learnt on a smaller corpus. Experimental results show that by using information from the external corpora, our new models produce significant improvements on topic coherence, document clustering and document classification tasks, especially on datasets with few or short documents.
Tasks Document Classification, Topic Models
Published 2018-10-15
URL http://arxiv.org/abs/1810.06306v1
PDF http://arxiv.org/pdf/1810.06306v1.pdf
PWC https://paperswithcode.com/paper/improving-topic-models-with-latent-feature
Repo
Framework
comments powered by Disqus