A framework for statistical network modeling

Statistical network models are often specified through their finite sampling distributions, which are usually chosen to accommodate known limiting behavior, such as sparsity, as well as to possess reasonable invariance properties, such as exchangeability. In many cases, it is mathematically impossible to specify a consistent family of finite sampling distributions with the desired invariance and limiting properties, e.g., exchangeability and sparsity are incompatible, creating tension between logical and empirical aspects of network modeling and limiting the scope of statistical inferences from network data. To address these issues, we show that every statistical network model fits into a universal framework: a {\em relatively exchangeable data generating process} governs the genesis of the population network from which a {\em sampling mechanism} generates the observed network data. Under this framework, a statistical network model is specified by a sampling mechanism in addition to its finite sampling distributions. The concept of relative exchangeability is central to the construction, as it permits models that reflect known structural properties and remain valid for inference. The sampling mechanism permits bias, e.g., preferential attachment or size-biased sampling, that is often responsible for heterogeneity in observed network structure. We illustrate the above framework with explicit examples from the literature and discuss implications for inference.

Adaptive sequential Monte Carlo for multiple changepoint analysis

Process monitoring and control requires detection of structural changes in a data stream in real time. This article introduces an efficient sequential Monte Carlo algorithm designed for learning unknown changepoints in continuous time. The method is intuitively simple: new changepoints for the latest window of data are proposed by conditioning only on data observed since the most recent estimated changepoint, as these carry most of the information about the state of the process prior to the update. The proposed method shows improved performance over the current state of the art. Another advantage of the proposed algorithm is that it can be made adaptive, varying the number of particles according to the apparent local complexity of the target changepoint probability distribution. This saves valuable computing time when changes in the change- point distribution are negligible, and enables re-balancing of the importance weights of ex- isting particles when a significant change in the target distribution is encountered. The plain and adaptive versions of the method are illustrated using the canonical con- tinuous time changepoint problem of inferring the intensity of an inhomogeneous Poisson process. Performance is demonstrated using both conjugate and non-conjugate Bayesian models for the intensity.

Bayesian Estimators in Uncertain Nested Error Regression Models

This paper suggests the nested error regression model, with use of uncertain random effects, which means that the random effects in each area are expressed as a mixture of a normal distribution and a positive mass at 0. For estimation of model parameters and prediction of random effects, we consider Bayesian yet objective inference by setting improper prior distributions on the model parameters. We show under the mild sufficient condition that the posterior distribution is proper and the posterior variances are finite to confirm validity of posterior inference. To generate samples from the posterior distribution, we provide the Gibbs sampling method. The full conditional distributions of the posterior distribution are all familiar forms such that the proposed methodology is easy to implement. This paper also addresses the problem of prediction of finite population means and we provide a sampling based method to tackle this issue. We compare the proposed model with the conventional nested error regression model through simulation and empirical studies.

Compressive spectral embedding: sidestepping the SVD

Spectral embedding based on the Singular Value Decomposition (SVD) is a widely used ‘preprocessing’ step in many learning tasks, typically leading to dimensionality reduction by projecting onto a number of dominant singular vectors and rescaling the coordinate axes (by a predefined function of the singular value). However, the number of such vectors required to capture problem structure grows with problem size, and even partial SVD computation becomes a bottleneck. In this paper, we propose a low-complexity it compressive spectral embedding algorithm, which employs random projections and finite order polynomial expansions to compute approximations to SVD-based embedding. For an m times n matrix with T non-zeros, its time complexity is O((T+m+n)log(m+n)), and the embedding dimension is O(log(m+n)), both of which are independent of the number of singular vectors whose effect we wish to capture. To the best of our knowledge, this is the first work to circumvent this dependence on the number of singular vectors for general SVD-based embeddings. The key to sidestepping the SVD is the observation that, for downstream inference tasks such as clustering and classification, we are only interested in using the resulting embedding to evaluate pairwise similarity metrics derived from the euclidean norm, rather than capturing the effect of the underlying matrix on arbitrary vectors as a partial SVD tries to do. Our numerical results on network datasets demonstrate the efficacy of the proposed method, and motivate further exploration of its application to large-scale inference tasks.

Deep Trans-layer Unsupervised Networks for Representation Learning

Learning features from massive unlabelled data is a vast prevalent topic for high-level tasks in many machine learning applications. The recent great improvements on benchmark data sets achieved by increasingly complex unsupervised learning methods and deep learning models with lots of parameters usually requires many tedious tricks and much expertise to tune. However, filters learned by these complex architectures are quite similar to standard hand-crafted features visually. In this paper, unsupervised learning methods, such as PCA or auto-encoder, are employed as the building block to learn filter banks at each layer. The lower layer responses are transferred to the last layer (trans-layer) to form a more complete representation retaining more information. In addition, some beneficial methods such as local contrast normalization and whitening are added to the proposed deep trans-layer networks to further boost performance. The trans-layer representations are followed by block histograms with binary encoder schema to learn translation and rotation invariant representations, which are utilized to do high-level tasks such as recognition and classification. Compared to traditional deep learning methods, the implemented feature learning method has much less parameters and is validated in several typical experiments, such as digit recognition on MNIST and MNIST variations, object recognition on Caltech 101 dataset and face verification on LFW dataset. The deep trans-layer unsupervised learning achieves 99.45% accuracy on MNIST dataset, 67.11% accuracy on 15 samples per class and 75.98% accuracy on 30 samples per class on Caltech 101 dataset, 87.10% on LFW dataset.

Discriminative Learning of the Prototype Set for Nearest Neighbor Classification

The nearest neighbor classifier is one of the most widely used models for classification. The selection of prototype instances is an important problem for its applications, as the efficiency of the model largely depends on the compactness of the prototype set. The existing studies on prototype selection have been primarily motivated by instance-based analyses of the class distribution and consistency among local neighbors. In this paper, we explore an approximation and a parametrization of the nearest neighbor rule, which allows us to formulate the violation of the rule over the training set with regards to the prototypes and take advantage of a discriminative learning principle. We show that our approach reduces to a large-margin learning based on a sparse representation of the relations among the neighbors. We demonstrate the advantage of the proposed algorithm by empirical comparison with the recent state-of-the-art methods over a collection of public benchmarks.

Encoding Reality: Prediction-Assisted Cortical Learning Algorithm in Hierarchical Temporal Memory

In the decade since Jeff Hawkins proposed Hierarchical Temporal Memory (HTM) as a model of neocortical computation, the theory and the algorithms have evolved dramatically. This paper presents a detailed description of HTM’s Cortical Learning Algorithm (CLA), including for the first time a rigorous mathematical formulation of all aspects of the computations. Prediction Assisted CLA (paCLA), a refinement of the CLA is presented, which is both closer to the neuroscience and adds significantly to the computational power. Finally, we summarise the key functions of neocortex which are expressed in paCLA implementations.

Feature Selection for classification of hyperspectral data by minimizing a tight bound on the VC dimension

Hyperspectral data consists of large number of features which require sophisticated analysis to be extracted. A popular approach to reduce computational cost, facilitate information representation and accelerate knowledge discovery is to eliminate bands that do not improve the classification and analysis methods being applied. In particular, algorithms that perform band elimination should be designed to take advantage of the specifics of the classification method being used. This paper employs a recently proposed filter-feature-selection algorithm based on minimizing a tight bound on the VC dimension. We have successfully applied this algorithm to determine a reasonable subset of bands without any user-defined stopping criteria on widely used hyperspectral images and demonstrate that this method outperforms state-of-the-art methods in terms of both sparsity of feature set as well as accuracy of classification.\end{abstract}

Mixture Modeling based Probabilistic Situation Awareness

The problem of situational awareness (SAW) is investigated from the probabilistic modeling point of view. Taking the situation as a hidden variable, we introduce a hidden Markov model (HMM) and an extended state space model (ESSM) to mathematically express the dynamic evolution law of the situation and the relationships between the situation and the observable quantities. We use the Gaussian mixture model (GMM) to formulate the expert knowledge, which is needed in building the HMM and ESSM. We show that the ESSM model is preferable as compared with HMM, since using ESSM, we can also get a real time estimate of the pivot variable that connects the situation with the observable quantities. The effectiveness and efficiency of both models are tested through a simulated experiment about threaten surveillance.

Modeling Curiosity in a Mobile Robot for Long-Term Autonomous Exploration and Monitoring

This paper presents a novel approach to modeling curiosity in a mobile robot, which is useful for monitoring and adaptive data collection tasks, especially in the context of long term autonomous missions where pre-programmed missions are likely to have limited utility. We use a realtime topic modeling technique to build a semantic perception model of the environment, using which, we plan a path through the locations in the world with high semantic information content. The life-long learning behavior of the proposed perception model makes it suitable for long-term exploration missions. We validate the approach using simulated exploration experiments using aerial and underwater data, and demonstrate an implementation on the Aqua underwater robot in a variety of scenarios. We find that the proposed exploration paths that are biased towards locations with high topic perplexity, produce better terrain models with high discriminative power. Moreover, we show that the proposed algorithm implemented on Aqua robot is able to do tasks such as coral reef inspection, diver following, and sea floor exploration, without any prior training or preparation.

Optimal Copula Transport for Clustering Multivariate Time Series

This paper presents a new methodology for clustering multivariate time series leveraging optimal transport between copulas. Copulas are used to encode both (i) intra-dependence of a multivariate time series, and (ii) inter-dependence between two time series. Then, optimal copula transport allows us to define two distances between multivariate time series: (i) one for measuring intra-dependence dissimilarity, (ii) another one for measuring inter-dependence dissimilarity based on a new multivariate dependence coefficient which is robust to noise, deterministic, and which can target specified dependencies.

Overlapping Community Detection via Local Spectral Clustering

Large graphs arise in a number of contexts and understanding their structure and extracting information from them is an important research area. Early algorithms on mining communities have focused on the global structure, and often run in time functional to the size of the entire graph. Nowadays, as we often explore networks with billions of vertices and find communities of size hundreds, it is crucial to shift our attention from macroscopic structure to microscopic structure in large networks. A growing body of work has been adopting local expansion methods in order to identify the community members from a few exemplary seed members. In this paper, we propose a novel approach for finding overlapping communities called LEMON (Local Expansion via Minimum One Norm). The algorithm finds the community by seeking a sparse vector in the span of the local spectra such that the seeds are in its support. We show that LEMON can achieve the highest detection accuracy among state-of-the-art proposals. The running time depends on the size of the community rather than that of the entire graph. The algorithm is easy to implement, and is highly parallelizable. We further provide theoretical analysis on the local spectral properties, bounding the measure of tightness of extracted community in terms of the eigenvalues of graph Laplacian. Moreover, given that networks are not all similar in nature, a comprehensive analysis on how the local expansion approach is suited for uncovering communities in different networks is still lacking. We thoroughly evaluate our approach using both synthetic and real-world datasets across different domains, and analyze the empirical variations when applying our method to inherently different networks in practice. In addition, the heuristics on how the seed set quality and quantity would affect the performance are provided.

Probably certifiably correct k-means clustering

Recently, Bandeira [arXiv:1509.00824] introduced a new type of algorithm (the so-called probably certifiably correct algorithm) that combines fast solvers with the optimality certificates provided by convex relaxations. In this paper, we devise such an algorithm for the problem of k-means clustering. First, we prove that a certain semidefinite relaxation of k-means is tight with high probability under a distribution of planted clusters called the stochastic ball model. Our proof follows from a new dual certificate for integral solutions of this semidefinite program. Next, we show how to test the optimality of a proposed k-means solution using this dual certificate in quasilinear time. Finally, we propose and analyze a version of spectral clustering that is designed to solve k-means in the case of two clusters. In particular, we show that this method has quasilinear complexity and typically recovers planted clusters under the stochastic ball model.

Temporal Regularized Matrix Factorization

Matrix factorization approaches have been applied to a variety of applications, from recommendation systems to multi-label learning. Standard low rank matrix factorization methods fail in cases when the data can be modeled as a time series, since they do not take into account the dependencies among factors, while EM algorithms designed for time series data are inapplicable to large multiple time series data. To overcome this, matrix factorization approaches are augmented with dynamic linear model based regularization frameworks. A major drawback in such approaches is that the exact dependencies between the latent factors are assumed to be known. In this paper, we introduce a Temporal Regularized Matrix Factorization (TRMF) method, an efficient alternating minimization scheme that not only learns the latent time series factors, but also the dependencies among the latent factors. TRMF is highly general, and subsumes several existing matrix factorization approaches for time series data. We make interesting connections to graph based matrix factorization methods in the context of learning the dependencies. Experiments on both real and synthetic data show that TRMF is highly scalable, and outperforms several existing approaches used for common large scale time series tasks.

Theoretical Analysis of the Optimal Free Responses of Graph-Based SFA for the Design of Training Graphs

Slow feature analysis (SFA) is an unsupervised learning algorithm that extracts slowly varying features from a time series. Graph-based SFA (GSFA) is a supervised extension that can solve regression problems if followed by a post-processing regression algorithm. A training graph specifies arbitrary connections between the training samples. The connections in current graphs, however, only depend on the rank of the involved labels. Exploiting the exact label values makes further improvements in estimation accuracy possible. In this article, we propose the exact label learning (ELL) method to create a graph that codes the desired label explicitly, so that GSFA is able to extract a normalized version of it directly. The ELL method is used for three tasks: (1) We estimate gender from artificial images of human faces (regression) and show the advantage of coding additional labels, particularly skin color. (2) We analyze two existing graphs for regression. (3) We extract compact discriminative features to classify traffic sign images. When the number of output features is limited, a higher classification rate is obtained compared to a graph equivalent to nonlinear Fisher discriminant analysis. The method is versatile, directly supports multiple labels, and provides higher accuracy compared to current graphs for the problems considered.

Weaver: A High-Performance, Transactional Graph Store Based on Refinable Timestamps

Distributed systems for storing and processing large graphs have become an increasingly common infrastructure component. Yet existing systems either operate on offline snapshots, provide poor consistency guarantees for dynamically changing graphs, or employ expensive concurrency control techniques that limit performance. In this paper, we introduce a new distributed graph store, called Weaver, which enables efficient, transactional graph analyses as well as strictly serializable read-write transactions on dynamic graphs. The key insight that enables Weaver to combine strict serializability with horizontal scalability and high performance is a novel request ordering mechanism called refinable timestamps. This technique couples coarse-grained vector timestamps with a fine-grained timeline oracle to pay the overhead of strong consistency only when needed. Experiments show that Weaver enables a Bitcoin blockchain explorer that is 8x faster than Blockchain.info, and achieves 12x higher throughput than the Titan graph database on social network workloads and 4x lower latency than GraphLab on offline graph traversal workloads.

$k$-Tuple Total Domination Number of Cartesian Product Graphs

A Computational Framework for Multivariate Convex Regression and its Variants

A Dynamical Systems Framework for Resilience in Ecology

A General Solution to (Free) Deterministic Equivalents

A note on dynamic fair division of multiple resources

A remark on a result of Xia Chen

A Revisit of Infinite Population Models for Evolutionary Algorithms on Continuous Optimization Problems

A testing-based approach to the discovery of differentially correlated variable sets

Adaptive Rejection Sampling with fixed number of nodes

Algorithms for Linear Bandits on Polyhedral Sets

Amplification and Derandomization Without Slowdown

An Efficient Derivative-Free Milstein Scheme for Stochastic Partial Differential Equations with Commutative Noise

An Innovative Approach for online Meta Search Engine Optimization

Analysis of A Splitting Approach for the Parallel Solution of Linear Systems on GPU Cards

Analysis of Intelligent Classifiers and Enhancing the Detection Accuracy for Intrusion Detection System

Approaching Single-Hop Performance in Multi-Hop Networks: End-To-End Known-Interference Cancellation (E2E-KIC)

Approximation and Heuristic Algorithms for Probabilistic Physical Search on General Graphs

Atypical scaling behavior persists in real world interaction networks

Backtesting forecast accuracy

Bayesian Multiple Testing Under Sparsity for Polynomial-Tailed Distributions

Bayesian sequential parameter estimation with a Laplace type approximation

Berline-Vergne valuation and generalized permutohedra

Betti posets and the Stanley depth

Blocking Strategies and Stability of Particle Gibbs Samplers

Building a Virtual HPC Cluster with Auto Scaling by the Docker

Clinical trial design enabling ε-optimal treatment rules

Coherence of Noisy Oscillators with Delayed Feedback Inducing Multistability

Combining allele frequency uncertainty and population substructure corrections in forensic DNA calculations

Contractivity and ground state domination properties for non-local Schrödinger operators

Convergence rates in precise asymptotics for a kind of complete moment convergence

Counting zero kernel pairs over a finite field

Definability Equals Recognizability for $k$-Outerplanar Graphs

Diffusion and localization of relative strategy scores in the Minority Game

Double pants decompositions revisited

Double posets and the antipode of QSym

Effects of dynamic synapses on noise-delayed response latency of a single neuron

Efficient Empowerment

Empirical Processes and Schatte Model

End-to-End Text-Dependent Speaker Verification

Ensemble UCT Needs High Exploitation

Evasion and Hardening of Tree Ensemble Classifiers

Exact ABC using Importance Sampling

Excess of Social Behavior Reduces the Capacity to Respond to Perturbations

Explicit Solutions for Optimal Stopping of Maximum Process with Absorbing Boundary that Varies with It

External Memory Three-Sided Range Reporting and Top-$k$ Queries with Sublogarithmic Updates

Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations

Finding a majority ball with majority answers

Fredholm theory for cofinite sets

Handicap hypothesis implies emergence of dimorphic mating displays

Helly-type theorems for the diameter

Inserting Multiple Edges into a Planar Graph

Lower bound theorems for general polytopes

Maxima of branching random walks with piecewise constant variance

Monte Carlo Simulations of the site-diluted 3d XY model with superexchange interaction: application to Fe[Se$_2$CN(C$_2$H$_5$)$_2$]$_2$Cl — Zn[S$_2$CN(C$_2$H$_5$)$_2$]$_2$ diluted magnets

Multi-threaded Graph Coloring Algorithm in Shared Memory Architecture

Multivariate Chebyshev Inequality with Estimated Mean and Variance

Noise sensitivity in bootstrap percolation

Non-asymptotic Analysis of $\ell_1$-norm Support Vector Machines

Novel Zagreb Indices-Based Inequalities with Particular Regard to Semiregular and Generalized Semiregular Graphs

On Delaunay’s classification theorem on faces of parallelohedra of codimension three

On energy dissipation in a friction-controlled slide of a body excited by random motions of a foundation

On Orbits of Order Ideals of Minuscule Posets II: Homomesy

On the geometry of border rank algorithms for n x 2 by 2 x 2 matrix multiplication

On the strong approximations of partial sums of f(nkx)

Online Object Tracking, Learning and Parsing with And-Or Graphs

Optimal Release Time Decision from Fuzzy Mathematical Programming Perspective

Parallel Metropolis chains with cooperative adaptation

Pattern Avoidance for Random Permutations

Quantile Search: A Distance-Penalized Active Learning Algorithm for Spatial Sampling

Relating multi-sequence longitudinal intensity profiles and clinical covariates in new multiple sclerosis lesions

Representation and approximation of ambit fields in Hilbert space

Representation Benefits of Deep Feedforward Networks

Reputation Management in Peer-to-Peer Networks: A Control-Theoretical Perspective

Sticky processes, local and true martingales

Stochastic Quantum Zeno by Large Deviation Theory

Strangely dual orbifold equivalence I

Super-Resolution Off the Grid

Targeted Fused Ridge Estimation of Inverse Covariance Matrices from Multiple High-Dimensional Data Classes

Testing High Dimensional Mean Under Sparsity

The Marshall-Olkin-Kumarswamy-G family of distributions

Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement

Towards Robust and Specific Causal Discovery from fMRI

Unbiased Bayesian Inference for Population Markov Jump Processes via Random Truncations

Virtualization map for the Littelmann path model