A Framework for Comparing Groups of Documents

We present a general framework for comparing multiple groups of documents. A bipartite graph model is proposed where document groups are represented as one node set and the comparison criteria are represented as the other node set. Using this model, we present basic algorithms to extract insights into similarities and differences among the document groups. Finally, we demonstrate the versatility of our framework through an analysis of NSF funding programs for basic research.

An Empirical Comparison of Multiple Imputation Methods for Categorical Data

Multiple imputation is a common approach for dealing with missing values in statistical databases. The imputer fills in missing values with draws from predictive models estimated from the observed data, resulting in multiple, completed versions of the database. Researchers have developed a variety of default routines to implement multiple imputation; however, there has been limited research comparing the performance of these methods, particularly for categorical data. We use simulation studies to compare repeated sampling properties of three default multiple imputation methods for categorical data, including chained equations using generalized linear models, chained equations using classification and regression trees, and a fully Bayesian joint distribution based on Dirichlet Process mixture models. We base the simulations on categorical data from the American Community Survey. The results suggest that default chained equations approaches based on generalized linear models are dominated by the default regression tree and mixture model approaches. They also suggest competing advantages for the regression tree and mixture model approaches, making both reasonable default engines for multiple imputation of categorical data.

Another Look at DWD: Thrifty Algorithm and Bayes Risk Consistency in RKHS

Distance weighted discrimination (DWD) is a margin-based classifier with an interesting geometric motivation. DWD was originally proposed as a superior alternative to the support vector machine (SVM), however DWD is yet to be popular compared with the SVM. The main reasons are twofold. First, the state-of-the-art algorithm for solving DWD is based on the second-order-cone programming (SOCP), while the SVM is a quadratic programming problem which is much more efficient to solve. Second, the current statistical theory of DWD mainly focuses on the linear DWD for the high-dimension-low-sample-size setting and data-piling, while the learning theory for the SVM mainly focuses on the Bayes risk consistency of the kernel SVM. In fact, the Bayes risk consistency of DWD is presented as an open problem in the original DWD paper. In this work, we advance the current understanding of DWD from both computational and theoretical perspectives. We propose a novel efficient algorithm for solving DWD, and our algorithm can be several hundred times faster than the existing state-of-the-art algorithm based on the SOCP. In addition, our algorithm can handle the generalized DWD, while the SOCP algorithm only works well for a special DWD but not the generalized DWD. Furthermore, we consider a natural kernel DWD in a reproducing kernel Hilbert space and then establish the Bayes risk consistency of the kernel DWD. We compare DWD and the SVM on several benchmark data sets and show that the two have comparable classification accuracy, but DWD equipped with our new algorithm can be much faster to compute than the SVM.

Empirical AUC for evaluating probabilistic forecasts

Scoring functions are used to evaluate and compare partially probabilistic forecasts. We investigate the use of rank-sum functions such as empirical Area Under the Curve (AUC), a widely-used measure of classification performance, as a scoring function for the prediction of probabilities of a set of binary outcomes. It is shown that the AUC is not generally a proper scoring function, that is, under certain circumstances it is possible to improve on the expected AUC by modifying the quoted probabilities from their true values. However with some restrictions, or with certain modifications, it can be made proper.

Extreme Dependence Models

Extreme values of real phenomena are events that occur with low frequency, but can have a large impact on real life. These are, in many practical problems, high-dimensional by nature (e.g. Tawn, 1990; Coles and Tawn, 1991). To study these events is of fundamental importance. For this purpose, probabilistic models and statistical methods are in high demand. There are several approaches to modelling multivariate extremes as described in Falk et al. (2011), linked to some extent. We describe an approach for deriving multivariate extreme value models and we illustrate the main features of some flexible extremal dependence models. We compare them by showing their utility with a real data application, in particular analyzing the extremal dependence among several pollutants recorded in the city of Leeds, UK.

Fast Asynchronous Parallel Stochastic Gradient Decent

Stochastic gradient descent~(SGD) and its variants have become more and more popular in machine learning due to their efficiency and effectiveness. To handle large-scale problems, researchers have recently proposed several parallel SGD methods for multicore systems. However, existing parallel SGD methods cannot achieve satisfactory performance in real applications. In this paper, we propose a fast asynchronous parallel SGD method, called AsySVRG, by designing an asynchronous strategy to parallelize the recently proposed SGD variant called stochastic variance reduced gradient~(SVRG). Both theoretical and empirical results show that AsySVRG can outperform existing state-of-the-art parallel SGD methods like Hogwild! in terms of convergence rate and computation cost.

Multi-round Master-Worker Computing: a Repeated Game Approach

We consider a computing system where a master processor assigns tasks for execution to worker processors through the Internet. We model the workers decision of whether to comply (compute the task) or not (return a bogus result to save the computation cost) as a mixed extension of a strategic game among workers. That is, we assume that workers are rational in a game-theoretic sense, and that they randomize their strategic choice. Workers are assigned multiple tasks in subsequent rounds. We model the system as an infinitely repeated game of the mixed extension of the strategic game. In each round, the master decides stochastically whether to accept the answer of the majority or verify the answers received, at some cost. Incentives and/or penalties are applied to workers accordingly. Under the above framework, we study the conditions in which the master can reliably obtain tasks results, exploiting that the repeated games model captures the effect of long-term interaction. That is, workers take into account that their behavior in one computation will have an effect on the behavior of other workers in the future. Indeed, should a worker be found to deviate from some agreed strategic choice, the remaining workers would change their own strategy to penalize the deviator. Hence, being rational, workers do not deviate. We identify analytically the parameter conditions to induce a desired worker behavior, and we evaluate experi- mentally the mechanisms derived from such conditions. We also compare the performance of our mechanisms with a previously known multi-round mechanism based on reinforcement learning.

MultiView Diffusion Maps

In this study we consider learning a reduced dimensionality representation from datasets obtained under multiple views. Such multiple views of datasets can be obtained, for example, when the same underlying process is observed using several different modalities, or measured with different instrumentation. Our goal is to effectively exploit the availability of such multiple views for various purposes, such as non-linear embedding, manifold learning, spectral clustering, anomaly detection and non-linear system identification. Our proposed method exploits the intrinsic relation within each view, as well as the mutual relations between views. We do this by defining a cross-view model, in which an implied Random Walk process between objects is restrained to hop between the different views. Our method is robust to scaling of each dataset, and is insensitive to small structural changes in the data. Within this framework, we define new diffusion distances and analyze the spectra of the implied kernels. We demonstrate the applicability of the proposed approach on both artificial and real data sets.

Non-Metric Space Library Manual

This document describes a library for similarity searching. Even though the library contains a variety of metric-space access methods, our main focus is on search methods for non-metric spaces. Because there are fewer exact solutions for non-metric spaces, many of our methods give only approximate answers. Thus, the methods are evaluated in terms of efficiency-effectiveness trade-offs rather than merely in terms of their efficiency. Our goal is, therefore, to provide not only state-of-the-art approximate search methods for both non-metric and metric spaces, but also the tools to measure search quality. We concentrate on technical details, i.e., how to compile the code, run the benchmarks, evaluate results, and use our code in other applications. Additionally, we explain how to extend the code by adding new search methods and spaces.

StochasticNet: Forming Deep Neural Networks via Stochastic Connectivity

Deep neural networks is a branch in machine learning that has seen a meteoric rise in popularity due to its powerful abilities to represent and model high-level abstractions in highly complex data. One area in deep neural networks that is ripe for exploration is neural connectivity formation. A pivotal study on the brain tissue of rats found that synaptic formation for specific functional connectivity in neocortical neural microcircuits can be surprisingly well modeled and predicted as a random formation. Motivated by this intriguing finding, we introduce the concept of StochasticNet, where deep neural networks are formed via stochastic connectivity between neurons. Such stochastic synaptic formations in a deep neural network architecture can potentially allow for efficient utilization of neurons for performing specific tasks. To evaluate the feasibility of such a deep neural network architecture, we train a StochasticNet using three image datasets. Experimental results show that a StochasticNet can be formed that provides comparable accuracy and reduced overfitting when compared to conventional deep neural networks with more than two times the number of neural connections.

The wild bootstrap for multilevel models

In this paper we study the performance of the most popular bootstrap schemes for multilevel data. Also, we propose a modified version of the wild bootstrap procedure for hierarchical data structures. The wild bootstrap does not require homoscedasticity or assumptions on the distribution of the error processes. Hence, it is a valuable tool for robust inference in a multilevel framework. We assess the finite size performances of the schemes through a Monte Carlo study. The results show that for big sample sizes it always pays off to adopt an agnostic approach as the wild bootstrap outperforms other techniques.

Towards Neural Network-based Reasoning

We propose Neural Reasoner, a framework for neural network-based reasoning over natural language sentences. Given a question, Neural Reasoner can infer over multiple supporting facts and find an answer to the question in specific forms. Neural Reasoner has 1) a specific interaction-pooling mechanism, allowing it to examine multiple facts, and 2) a deep architecture, allowing it to model the complicated logical relations in reasoning tasks. Assuming no particular structure exists in the question and facts, Neural Reasoner is able to accommodate different types of reasoning and different forms of language expressions. Despite the model complexity, Neural Reasoner can still be trained effectively in an end-to-end manner. Our empirical studies show that Neural Reasoner can outperform existing neural reasoning systems with remarkable margins on two difficult artificial tasks (Positional Reasoning and Path Finding) proposed in [8]. For example, it improves the accuracy on Path Finding(10K) from 33.4% [6] to over 98%.

A $N$-Body Solver for Square Root Iteration

A Dichotomy Theorem for Circular Colouring Reconfiguration

A generalized characterization of algorithmic probability

A joint model for authors characteristics and collaboration pattern in bibliometric networks: a Bayesian approach

A new convergence analysis and perturbation resilience of some accelerated proximal forward-backward algorithms with errors

A Note on Spherical Needlets

A note on the complexity of the causal ordering problem

A Power Variance Test for Nonstationarity in Complex-Valued Signals

A Practical O(R\log\log n+n) time Algorithm for Computing the Longest Common Subsequence

A representation of antimatroids by Horn rules and its application to educational systems

A space-time conditional intensity model for invasive meningococcal disease occurrence

A stochastic two-stage innovation diffusion model on a lattice

About the infinite dimensional skew and obliquely reflected Ornstein-Uhlenbeck process

Additive equations in dense variables, and truncated restriction estimates

An adaptive kriging method for solving nonlinear inverse statistical problems

An evolutionary approach to the identification of Cellular Automata based on partial observations

An HJB Approach to a General Continuous-Time Mean-Variance Stochastic Control Problem

An Ordinary Differential Equation Model for Fish Schooling

Asymptotic bases and probabilistic representation functions

Asymptotic Theory for Estimating the Singular Vectors and Values of a Partially-observed Low Rank Matrix with Noise

Bayesian approach to inverse problems for functions with variable index Besov prior

Bayesian Detection of Image Boundaries

Bayesian Hypothesis Testing for Block Sparse Signal Recovery

Beyond subjective and objective in statistics

Can the tail for maximum of continuous random field be significantly more heavy than maximum of tails?

Cell complexes, poset topology and the representation theory of algebras arising in algebraic combinatorics and discrete geometry

Chaining, Interpolation, and Convexity

Comments on the estimate for Pareto Distribution

Complexity of Anticipated Rejection Algorithms and the Darling-Mandelbrot Distribution

Concentration of Measure Techniques and Applications

Critical Groups of Graphs with Dihedral Actions II

Disproving the normal graph conjecture

Distant set distinguishing total colourings of graphs

Echoes of Persuasion: The Effect of Euphony in Persuasive Communication

Emergence of coexisting percolating clusters in networks

Evaluating the quality of survey and administrative data with generalized multitrait-multimethod models

Feature Sensitive and Automated Curve Registration

Flocking and non-flocking behavior in a stochastic Cucker-Smale system

Forbidding Hamilton cycles in uniform hypergraphs

Gaussian Mixture Reduction Using Reverse Kullback-Leibler Divergence

Generalised polygons admitting a point-primitive almost simple group of Suzuki or Ree type

Hyperdiffusion of quantum waves in random photonic lattices

Integral equations for Rost’s reversed barriers: existence and uniqueness results

Joint Modeling of Longitudinal Drug Using Pattern and Time to First Relapse in Cocaine Dependence Treatment Data

Laplacian State Transfer in Coronas

Lattice approximation to the dynamical $Φ_3^4$ model

Learning of couplings for random asymmetric kinetic Ising models revisited: random correlation matrices and learning curves

Local Spectral Density of the Sum of Random Matrices

Localization errors in solving stochastic partial differential equations in the whole space

Many-Body Localization in a Two-Dimensional Anderson-Hubbard Model

Models of Markov processes with a random transition mechanism

Multivariate trend-cycle extraction with the Hodrick-Prescott filter

Necessary and Sufficient Conditions and a Provably Efficient Algorithm for Separable Topic Discovery

Non-fixation of symmetric Activated Random Walk on the line for small sleep rate

Normal Binary Hierarchical Models

Note on the Erdos-Faber-Lovasz Conjecture and commutative quasigroups

On a characterization of infinitely divisible distributions with Gaussian component

On the asymptotic distribution of block-modified random matrices

On the Displacement for Covering a $d-$dimensional Cube with Randomly Placed Sensors

On the extremal total reciprocal edge-eccentricity of trees

On the wedge product of table algebras and applications to association schemes

Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions

Population Annealing: Theory and Application in Spin Glasses

Regression modeling on stratified data: automatic and covariate-specific selection of the reference stratum with simple $L_1$-norm penalties

replikativ.io: Composable consistency primitives for a scalable and robust global replication system

Reticulation-Visible Networks

Robust sparse Gaussian graphical modeling

Scalable Bayes via Barycenter in Wasserstein Space

Searching for significant patterns in stratified data

Separation with restricted families of sets

Sets with few differences in abelian groups

Slow $k$-Nim

Socially-Aware Distributed Hash Tables for Decentralized Online Social Networks

Some contributions to the study of stochastic processes of the classes $Σ(H)$ and $(Σ)$

Stability and Localization of inter-individual differences in functional connectivity

Stochastic Behavior of the Nonnegative Least Mean Fourth Algorithm for Stationary Gaussian Inputs and Slow Learning

Tensor Powers of the Defining Representation of $S_n$

The $Z_2$ Index of Disordered Topological Insulators with Time Reversal Symmetry

The Cohomology of Quaternionic Hyperplane Complements

The Hamiltonian problem and $t$-path traceable graphs

The Max $K$-Armed Bandit: A PAC Lower Bound and tighter Algorithms

The Union-Closed Sets Conjecture for Small Families

The ‘who’ and ‘what’ of #diabetes on Twitter

Thermodynamics of dilute XX chain in a field

Transience in growing subgraphs via evolving sets

Variance and Covariance of Several Simultaneous Outputs of a Markov Chain

Wavelet transforms and their applications to MHD and plasma turbulence: a review