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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
http://arxiv.org/pdf/1810.06306v1.pdf | |
PWC | https://paperswithcode.com/paper/improving-topic-models-with-latent-feature |
Repo | |
Framework | |