May 5, 2019

3180 words 15 mins read

Paper Group ANR 508

On Sampling and Greedy MAP Inference of Constrained Determinantal Point Processes. Random matrices meet machine learning: a large dimensional analysis of LS-SVM. Smart broadcasting: Do you want to be seen?. Detecting weak changes in dynamic events over networks. Noisy subspace clustering via matching pursuits. Alzheimer’s Disease Diagnostics by a D …

On Sampling and Greedy MAP Inference of Constrained Determinantal Point Processes


Title	On Sampling and Greedy MAP Inference of Constrained Determinantal Point Processes
Authors	Tarun Kathuria, Amit Deshpande
Abstract	Subset selection problems ask for a small, diverse yet representative subset of the given data. When pairwise similarities are captured by a kernel, the determinants of submatrices provide a measure of diversity or independence of items within a subset. Matroid theory gives another notion of independence, thus giving rise to optimization and sampling questions about Determinantal Point Processes (DPPs) under matroid constraints. Partition constraints, as a special case, arise naturally when incorporating additional labeling or clustering information, besides the kernel, in DPPs. Finding the maximum determinant submatrix under matroid constraints on its row/column indices has been previously studied. However, the corresponding question of sampling from DPPs under matroid constraints has been unresolved, beyond the simple cardinality constrained k-DPPs. We give the first polynomial time algorithm to sample exactly from DPPs under partition constraints, for any constant number of partitions. We complement this by a complexity theoretic barrier that rules out such a result under general matroid constraints. Our experiments indicate that partition-constrained DPPs offer more flexibility and more diversity than k-DPPs and their naive extensions, while being reasonably efficient in running time. We also show that a simple greedy initialization followed by local search gives improved approximation guarantees for the problem of MAP inference from k- DPPs on well-conditioned kernels. Our experiments show that this improvement is significant for larger values of k, supporting our theoretical result.
Tasks	Point Processes
Published	2016-07-06
URL	http://arxiv.org/abs/1607.01551v1
PDF	http://arxiv.org/pdf/1607.01551v1.pdf
PWC	https://paperswithcode.com/paper/on-sampling-and-greedy-map-inference-of
Repo
Framework

Random matrices meet machine learning: a large dimensional analysis of LS-SVM


Title	Random matrices meet machine learning: a large dimensional analysis of LS-SVM
Authors	Zhenyu Liao, Romain Couillet
Abstract	This article proposes a performance analysis of kernel least squares support vector machines (LS-SVMs) based on a random matrix approach, in the regime where both the dimension of data $p$ and their number $n$ grow large at the same rate. Under a two-class Gaussian mixture model for the input data, we prove that the LS-SVM decision function is asymptotically normal with means and covariances shown to depend explicitly on the derivatives of the kernel function. This provides improved understanding along with new insights into the internal workings of SVM-type methods for large datasets.
Tasks
Published	2016-09-07
URL	http://arxiv.org/abs/1609.02020v2
PDF	http://arxiv.org/pdf/1609.02020v2.pdf
PWC	https://paperswithcode.com/paper/random-matrices-meet-machine-learning-a-large
Repo
Framework

Smart broadcasting: Do you want to be seen?


Title	Smart broadcasting: Do you want to be seen?
Authors	Mohammad Reza Karimi, Erfan Tavakoli, Mehrdad Farajtabar, Le Song, Manuel Gomez-Rodriguez
Abstract	Many users in online social networks are constantly trying to gain attention from their followers by broadcasting posts to them. These broadcasters are likely to gain greater attention if their posts can remain visible for a longer period of time among their followers’ most recent feeds. Then when to post? In this paper, we study the problem of smart broadcasting using the framework of temporal point processes, where we model users feeds and posts as discrete events occurring in continuous time. Based on such continuous-time model, then choosing a broadcasting strategy for a user becomes a problem of designing the conditional intensity of her posting events. We derive a novel formula which links this conditional intensity with the visibility of the user in her followers’ feeds. Furthermore, by exploiting this formula, we develop an efficient convex optimization framework for the when-to-post problem. Our method can find broadcasting strategies that reach a desired visibility level with provable guarantees. We experimented with data gathered from Twitter, and show that our framework can consistently make broadcasters’ post more visible than alternatives.
Tasks	Point Processes
Published	2016-05-22
URL	http://arxiv.org/abs/1605.06855v1
PDF	http://arxiv.org/pdf/1605.06855v1.pdf
PWC	https://paperswithcode.com/paper/smart-broadcasting-do-you-want-to-be-seen
Repo
Framework

Detecting weak changes in dynamic events over networks


Title	Detecting weak changes in dynamic events over networks
Authors	Shuang Li, Yao Xie, Mehrdad Farajtabar, Apurv Verma, Le Song
Abstract	Large volume of networked streaming event data are becoming increasingly available in a wide variety of applications, such as social network analysis, Internet traffic monitoring and healthcare analytics. Streaming event data are discrete observation occurred in continuous time, and the precise time interval between two events carries a great deal of information about the dynamics of the underlying systems. How to promptly detect changes in these dynamic systems using these streaming event data? In this paper, we propose a novel change-point detection framework for multi-dimensional event data over networks. We cast the problem into sequential hypothesis test, and derive the likelihood ratios for point processes, which are computed efficiently via an EM-like algorithm that is parameter-free and can be computed in a distributed fashion. We derive a highly accurate theoretical characterization of the false-alarm-rate, and show that it can achieve weak signal detection by aggregating local statistics over time and networks. Finally, we demonstrate the good performance of our algorithm on numerical examples and real-world datasets from twitter and Memetracker.
Tasks	Change Point Detection, Point Processes
Published	2016-03-29
URL	http://arxiv.org/abs/1603.08981v2
PDF	http://arxiv.org/pdf/1603.08981v2.pdf
PWC	https://paperswithcode.com/paper/detecting-weak-changes-in-dynamic-events-over
Repo
Framework

Noisy subspace clustering via matching pursuits


Title	Noisy subspace clustering via matching pursuits
Authors	Michael Tschannen, Helmut Bölcskei
Abstract	Sparsity-based subspace clustering algorithms have attracted significant attention thanks to their excellent performance in practical applications. A prominent example is the sparse subspace clustering (SSC) algorithm by Elhamifar and Vidal, which performs spectral clustering based on an adjacency matrix obtained by sparsely representing each data point in terms of all the other data points via the Lasso. When the number of data points is large or the dimension of the ambient space is high, the computational complexity of SSC quickly becomes prohibitive. Dyer et al. observed that SSC-OMP obtained by replacing the Lasso by the greedy orthogonal matching pursuit (OMP) algorithm results in significantly lower computational complexity, while often yielding comparable performance. The central goal of this paper is an analytical performance characterization of SSC-OMP for noisy data. Moreover, we introduce and analyze the SSC-MP algorithm, which employs matching pursuit (MP) in lieu of OMP. Both SSC-OMP and SSC-MP are proven to succeed even when the subspaces intersect and when the data points are contaminated by severe noise. The clustering conditions we obtain for SSC-OMP and SSC-MP are similar to those for SSC and for the thresholding-based subspace clustering (TSC) algorithm due to Heckel and B"olcskei. Analytical results in combination with numerical results indicate that both SSC-OMP and SSC-MP with a data-dependent stopping criterion automatically detect the dimensions of the subspaces underlying the data. Moreover, experiments on synthetic and on real data show that SSC-MP compares very favorably to SSC, SSC-OMP, TSC, and the nearest subspace neighbor algorithm, both in terms of clustering performance and running time. In addition, we find that, in contrast to SSC-OMP, the performance of SSC-MP is very robust with respect to the choice of parameters in the stopping criteria.
Tasks
Published	2016-12-11
URL	http://arxiv.org/abs/1612.03450v2
PDF	http://arxiv.org/pdf/1612.03450v2.pdf
PWC	https://paperswithcode.com/paper/noisy-subspace-clustering-via-matching
Repo
Framework

Alzheimer’s Disease Diagnostics by a Deeply Supervised Adaptable 3D Convolutional Network


Title	Alzheimer’s Disease Diagnostics by a Deeply Supervised Adaptable 3D Convolutional Network
Authors	Ehsan Hosseini-Asl, Georgy Gimel’farb, Ayman El-Baz
Abstract	Early diagnosis, playing an important role in preventing progress and treating the Alzheimer’s disease (AD), is based on classification of features extracted from brain images. The features have to accurately capture main AD-related variations of anatomical brain structures, such as, e.g., ventricles size, hippocampus shape, cortical thickness, and brain volume. This paper proposes to predict the AD with a deep 3D convolutional neural network (3D-CNN), which can learn generic features capturing AD biomarkers and adapt to different domain datasets. The 3D-CNN is built upon a 3D convolutional autoencoder, which is pre-trained to capture anatomical shape variations in structural brain MRI scans. Fully connected upper layers of the 3D-CNN are then fine-tuned for each task-specific AD classification. Experiments on the \emph{ADNI} MRI dataset with no skull-stripping preprocessing have shown our 3D-CNN outperforms several conventional classifiers by accuracy and robustness. Abilities of the 3D-CNN to generalize the features learnt and adapt to other domains have been validated on the \emph{CADDementia} dataset.
Tasks	Skull Stripping
Published	2016-07-02
URL	http://arxiv.org/abs/1607.00556v1
PDF	http://arxiv.org/pdf/1607.00556v1.pdf
PWC	https://paperswithcode.com/paper/alzheimers-disease-diagnostics-by-a-deeply
Repo
Framework

Mining Arguments from Cancer Documents Using Natural Language Processing and Ontologies


Title	Mining Arguments from Cancer Documents Using Natural Language Processing and Ontologies
Authors	Adrian Groza, Oana Popa
Abstract	In the medical domain, the continuous stream of scientific research contains contradictory results supported by arguments and counter-arguments. As medical expertise occurs at different levels, part of the human agents have difficulties to face the huge amount of studies, but also to understand the reasons and pieces of evidences claimed by the proponents and the opponents of the debated topic. To better understand the supporting arguments for new findings related to current state of the art in the medical domain we need tools able to identify arguments in scientific papers. Our work here aims to fill the above technological gap. Quite aware of the difficulty of this task, we embark to this road by relying on the well-known interleaving of domain knowledge with natural language processing. To formalise the existing medical knowledge, we rely on ontologies. To structure the argumentation model we use also the expressivity and reasoning capabilities of Description Logics. To perform argumentation mining we formalise various linguistic patterns in a rule-based language. We tested our solution against a corpus of scientific papers related to breast cancer. The run experiments show a F-measure between 0.71 and 0.86 for identifying conclusions of an argument and between 0.65 and 0.86 for identifying premises of an argument.
Tasks
Published	2016-07-27
URL	http://arxiv.org/abs/1607.08074v1
PDF	http://arxiv.org/pdf/1607.08074v1.pdf
PWC	https://paperswithcode.com/paper/mining-arguments-from-cancer-documents-using
Repo
Framework

Spatiotemporal Articulated Models for Dynamic SLAM


Title	Spatiotemporal Articulated Models for Dynamic SLAM
Authors	Suren Kumar, Vikas Dhiman, Madan Ravi Ganesh, Jason J. Corso
Abstract	We propose an online spatiotemporal articulation model estimation framework that estimates both articulated structure as well as a temporal prediction model solely using passive observations. The resulting model can predict future mo- tions of an articulated object with high confidence because of the spatial and temporal structure. We demonstrate the effectiveness of the predictive model by incorporating it within a standard simultaneous localization and mapping (SLAM) pipeline for mapping and robot localization in previously unexplored dynamic environments. Our method is able to localize the robot and map a dynamic scene by explaining the observed motion in the world. We demonstrate the effectiveness of the proposed framework for both simulated and real-world dynamic environments.
Tasks	Simultaneous Localization and Mapping
Published	2016-04-12
URL	http://arxiv.org/abs/1604.03526v1
PDF	http://arxiv.org/pdf/1604.03526v1.pdf
PWC	https://paperswithcode.com/paper/spatiotemporal-articulated-models-for-dynamic
Repo
Framework

Generalized Statistical Tests for mRNA and Protein Subcellular Spatial Patterning against Complete Spatial Randomness


Title	Generalized Statistical Tests for mRNA and Protein Subcellular Spatial Patterning against Complete Spatial Randomness
Authors	Jonathan H. Warrell, Anca F. Savulescu, Robyn Brackin, Musa M. Mhlanga
Abstract	We derive generalized estimators for a number of spatial statistics that have been used in the analysis of spatially resolved omics data, such as Ripley’s K, H and L functions, clustering index, and degree of clustering, which allow these statistics to be calculated on data modelled by arbitrary random measures (RMs). Our estimators generalize those typically used to calculate these statistics on point process data, allowing them to be calculated on RMs which assign continuous values to spatial regions, for instance to model protein intensity. The clustering index (H) compares Ripley’s H function calculated empirically to its distribution under complete spatial randomness (CSR), leading us to consider CSR null hypotheses for RMs which are not point-processes when generalizing this statistic. We thus consider restricted classes of completely random measures which can be simulated directly (Gamma processes and Marked Poisson Processes), as well as the general class of all CSR RMs, for which we derive an exact permutation-based H estimator. We establish several properties of the estimators, including bounds on the accuracy of our general Ripley K estimator, its relationship to a previous estimator for the cross-correlation measure, and the relationship of our generalized H* estimator to previous statistics. To test the ability of our approach to identify spatial patterning, we use Fluorescent In Situ Hybridization (FISH) and Immunofluorescence (IF) data to probe for mRNA and protein subcellular localization patterns respectively in polarizing mouse fibroblasts on micropattened cells. We observe correlated patterns of clustering over time for corresponding mRNAs and proteins, suggesting a deterministic effect of mRNA localization on protein localization for several pairs tested, including one case in which spatial patterning at the mRNA level has not been previously demonstrated.
Tasks	Point Processes
Published	2016-02-20
URL	http://arxiv.org/abs/1602.06429v3
PDF	http://arxiv.org/pdf/1602.06429v3.pdf
PWC	https://paperswithcode.com/paper/generalized-statistical-tests-for-mrna-and
Repo
Framework

Neural Networks and Continuous Time


Title	Neural Networks and Continuous Time
Authors	Frieder Stolzenburg, Florian Ruh
Abstract	The fields of neural computation and artificial neural networks have developed much in the last decades. Most of the works in these fields focus on implementing and/or learning discrete functions or behavior. However, technical, physical, and also cognitive processes evolve continuously in time. This cannot be described directly with standard architectures of artificial neural networks such as multi-layer feed-forward perceptrons. Therefore, in this paper, we will argue that neural networks modeling continuous time are needed explicitly for this purpose, because with them the synthesis and analysis of continuous and possibly periodic processes in time are possible (e.g. for robot behavior) besides computing discrete classification functions (e.g. for logical reasoning). We will relate possible neural network architectures with (hybrid) automata models that allow to express continuous processes.
Tasks
Published	2016-06-14
URL	http://arxiv.org/abs/1606.04466v1
PDF	http://arxiv.org/pdf/1606.04466v1.pdf
PWC	https://paperswithcode.com/paper/neural-networks-and-continuous-time
Repo
Framework

Online Bayesian Collaborative Topic Regression


Title	Online Bayesian Collaborative Topic Regression
Authors	Chenghao Liu, Tao Jin, Steven C. H. Hoi, Peilin Zhao, Jianling Sun
Abstract	Collaborative Topic Regression (CTR) combines ideas of probabilistic matrix factorization (PMF) and topic modeling (e.g., LDA) for recommender systems, which has gained increasing successes in many applications. Despite enjoying many advantages, the existing CTR algorithms have some critical limitations. First of all, they are often designed to work in a batch learning manner, making them unsuitable to deal with streaming data or big data in real-world recommender systems. Second, the document-specific topic proportions of LDA are fed to the downstream PMF, but not reverse, which is sub-optimal as the rating information is not exploited in discovering the low-dimensional representation of documents and thus can result in a sub-optimal representation for prediction. In this paper, we propose a novel scheme of Online Bayesian Collaborative Topic Regression (OBCTR) which is efficient and scalable for learning from data streams. Particularly, we {\it jointly} optimize the combined objective function of both PMF and LDA in an online learning fashion, in which both PMF and LDA tasks can be reinforced each other during the online learning process. Our encouraging experimental results on real-world data validate the effectiveness of the proposed method.
Tasks	Recommendation Systems
Published	2016-05-28
URL	http://arxiv.org/abs/1605.08872v1
PDF	http://arxiv.org/pdf/1605.08872v1.pdf
PWC	https://paperswithcode.com/paper/online-bayesian-collaborative-topic
Repo
Framework


Title	Detecting “Smart” Spammers On Social Network: A Topic Model Approach
Authors	Linqing Liu, Yao Lu, Ye Luo, Renxian Zhang, Laurent Itti, Jianwei Lu
Abstract	Spammer detection on social network is a challenging problem. The rigid anti-spam rules have resulted in emergence of “smart” spammers. They resemble legitimate users who are difficult to identify. In this paper, we present a novel spammer classification approach based on Latent Dirichlet Allocation(LDA), a topic model. Our approach extracts both the local and the global information of topic distribution patterns, which capture the essence of spamming. Tested on one benchmark dataset and one self-collected dataset, our proposed method outperforms other state-of-the-art methods in terms of averaged F1-score.
Tasks
Published	2016-04-28
URL	http://arxiv.org/abs/1604.08504v2
PDF	http://arxiv.org/pdf/1604.08504v2.pdf
PWC	https://paperswithcode.com/paper/detecting-smart-spammers-on-social-network-a
Repo
Framework

Identifiability Assumptions and Algorithm for Directed Graphical Models with Feedback


Title	Identifiability Assumptions and Algorithm for Directed Graphical Models with Feedback
Authors	Gunwoong Park, Garvesh Raskutti
Abstract	Directed graphical models provide a useful framework for modeling causal or directional relationships for multivariate data. Prior work has largely focused on identifiability and search algorithms for directed acyclic graphical (DAG) models. In many applications, feedback naturally arises and directed graphical models that permit cycles occur. In this paper we address the issue of identifiability for general directed cyclic graphical (DCG) models satisfying the Markov assumption. In particular, in addition to the faithfulness assumption which has already been introduced for cyclic models, we introduce two new identifiability assumptions, one based on selecting the model with the fewest edges and the other based on selecting the DCG model that entails the maximum number of d-separation rules. We provide theoretical results comparing these assumptions which show that: (1) selecting models with the largest number of d-separation rules is strictly weaker than the faithfulness assumption; (2) unlike for DAG models, selecting models with the fewest edges does not necessarily result in a milder assumption than the faithfulness assumption. We also provide connections between our two new principles and minimality assumptions. We use our identifiability assumptions to develop search algorithms for small-scale DCG models. Our simulation study supports our theoretical results, showing that the algorithms based on our two new principles generally out-perform algorithms based on the faithfulness assumption in terms of selecting the true skeleton for DCG models.
Tasks
Published	2016-02-14
URL	http://arxiv.org/abs/1602.04418v2
PDF	http://arxiv.org/pdf/1602.04418v2.pdf
PWC	https://paperswithcode.com/paper/identifiability-assumptions-and-algorithm-for
Repo
Framework

Discovering Conversational Dependencies between Messages in Dialogs


Title	Discovering Conversational Dependencies between Messages in Dialogs
Authors	Wenchao Du, Pascal Poupart, Wei Xu
Abstract	We investigate the task of inferring conversational dependencies between messages in one-on-one online chat, which has become one of the most popular forms of customer service. We propose a novel probabilistic classifier that leverages conversational, lexical and semantic information. The approach is evaluated empirically on a set of customer service chat logs from a Chinese e-commerce website. It outperforms heuristic baselines.
Tasks
Published	2016-12-08
URL	http://arxiv.org/abs/1612.02801v1
PDF	http://arxiv.org/pdf/1612.02801v1.pdf
PWC	https://paperswithcode.com/paper/discovering-conversational-dependencies
Repo
Framework

Balancing New Against Old Information: The Role of Surprise in Learning


Title	Balancing New Against Old Information: The Role of Surprise in Learning
Authors	Mohammadjavad Faraji, Kerstin Preuschoff, Wulfram Gerstner
Abstract	Surprise describes a range of phenomena from unexpected events to behavioral responses. We propose a measure of surprise and use it for surprise-driven learning. Our surprise measure takes into account data likelihood as well as the degree of commitment to a belief via the entropy of the belief distribution. We find that surprise-minimizing learning dynamically adjusts the balance between new and old information without the need of knowledge about the temporal statistics of the environment. We apply our framework to a dynamic decision-making task and a maze exploration task. Our surprise minimizing framework is suitable for learning in complex environments, even if the environment undergoes gradual or sudden changes and could eventually provide a framework to study the behavior of humans and animals encountering surprising events.
Tasks	Decision Making
Published	2016-06-17
URL	http://arxiv.org/abs/1606.05642v2
PDF	http://arxiv.org/pdf/1606.05642v2.pdf
PWC	https://paperswithcode.com/paper/balancing-new-against-old-information-the
Repo
Framework