Tim Shi

In this paper, we develop a new aggregation technique to reduce the cost of surveying. Our method aims to jointly estimate a vector of target quantities such as public opinion or voter intent across time and maintain good estimates when using only a fraction of the data. Inspired by the James-Stein estimator, we resolve this challenge by shrinking the estimates to a global mean which is assumed to have a sparse representation in some known basis. This assumption has lead to two different methods… Show more

In this paper, we develop a new aggregation technique to reduce the cost of surveying. Our method aims to jointly estimate a vector of target quantities such as public opinion or voter intent across time and maintain good estimates when using only a fraction of the data. Inspired by the James-Stein estimator, we resolve this challenge by shrinking the estimates to a global mean which is assumed to have a sparse representation in some known basis. This assumption has lead to two different methods for estimating the global mean: orthogonal matching pursuit and deep learning. Both of which significantly reduce the number of samples needed to achieve good estimates of the true means of the data and, in the case of presidential elections, can estimate the outcome of the 2012 United States elections while saving hundreds of thousands of samples and maintaining accuracy. Show less

In structured prediction, most inference algorithms allocate a homogeneous amount of computation to all parts of the output, which can be wasteful when different parts vary widely in terms of difficulty. In this paper, we propose a heterogeneous approach that dynamically allocates computation to the different parts. Given a pre-trained model, we tune its inference algorithm (a sampler) to increase test-time throughput. The inference algorithm is parametrized by a meta-model and trained via… Show more

In structured prediction, most inference algorithms allocate a homogeneous amount of computation to all parts of the output, which can be wasteful when different parts vary widely in terms of difficulty. In this paper, we propose a heterogeneous approach that dynamically allocates computation to the different parts. Given a pre-trained model, we tune its inference algorithm (a sampler) to increase test-time throughput. The inference algorithm is parametrized by a meta-model and trained via reinforcement learning, where actions correspond to sampling candidate parts of the output, and rewards are log- likelihood improvements. The meta-model is based on a set of domain-general meta-features capturing the progress of the sampler. We test our approach on five datasets and show that it attains the same accuracy as Gibbs sampling but is 2 to 5 times faster. Show less

We present online Bayesian Passive-Aggressive (BayesPA) learning, a generic online learning framework for hierarchical Bayesian models with max-margin posterior regularization. We provide provable Bayesian regret bounds for both averaging classifiers and Gibbs classifiers. We show that BayesPA subsumes the standard online Passive-Aggressive (PA) learning and more importantly extends naturally to incorporate latent variables for both parametric and nonparametric Bayesian inference, therefore… Show more

We present online Bayesian Passive-Aggressive (BayesPA) learning, a generic online learning framework for hierarchical Bayesian models with max-margin posterior regularization. We provide provable Bayesian regret bounds for both averaging classifiers and Gibbs classifiers. We show that BayesPA subsumes the standard online Passive-Aggressive (PA) learning and more importantly extends naturally to incorporate latent variables for both parametric and nonparametric Bayesian inference, therefore providing great flexibility for explorative analysis. As an important example, we apply BayesPA to topic modeling and derive efficient online learning algorithms for max-margin topic models. We further develop nonparametric BayesPA topic models to resolve the unknown number of topics. Experimental results on 20newsgroups and a large Wikipedia multi-label data set (with 1.1 millions of training documents and 0.9 million of unique terms in the vocabulary) show that our approaches significantly improve time efficiency while maintaining comparable results with the batch counterpart methods. Show less

Given n independent random variables X_1, X_2, ..., X_n and an integer C, we study the fundamental problem of computing the probability that the sum X=X_1+X_2+...+X_n is at most C. We assume that each random variable X_i is implicitly given by an oracle which, given an input value k, returns the probability X_i\leq k. We give the first deterministic fully polynomial-time approximation scheme (FPTAS) to estimate the probability up to a relative error of 1\pm \epsilon. Our algorithm is based on… Show more

Given n independent random variables X_1, X_2, ..., X_n and an integer C, we study the fundamental problem of computing the probability that the sum X=X_1+X_2+...+X_n is at most C. We assume that each random variable X_i is implicitly given by an oracle which, given an input value k, returns the probability X_i\leq k. We give the first deterministic fully polynomial-time approximation scheme (FPTAS) to estimate the probability up to a relative error of 1\pm \epsilon. Our algorithm is based on the idea developed for approximately counting knapsack solutions in [Gopalan et al. FOCS11]. Show less

We consider the problem of recovering sparse correlated data on networks. To improve accuracy and reduce costs, it is strongly desirable to take the potentially useful side-information of network structure into consideration. In this paper we present a novel correlated compressive sensing method called CorrCS for networked data. By naturally extending Bayesian compressive sensing, we extract correlations from network topology and encode them into a graphical model as prior. Then we derive… Show more

We consider the problem of recovering sparse correlated data on networks. To improve accuracy and reduce costs, it is strongly desirable to take the potentially useful side-information of network structure into consideration. In this paper we present a novel correlated compressive sensing method called CorrCS for networked data. By naturally extending Bayesian compressive sensing, we extract correlations from network topology and encode them into a graphical model as prior. Then we derive posterior inference algorithms for the recovery of jointly sparse and correlated networked data. First, we design algorithms to recover the data based on pairwise correlations between neighboring nodes in the network. Next, we generalize this model through a diffusion process to capture higher-order correlations. Both real-valued and binary data are considered. Our models are extensively tested on several real datasets from social and sensor networks and are shown to outperform baseline compressive sensing models in terms of recovery performance. Show less

A number of psychological and physiological evidences suggest that early visual attention works in a coarse-to-fine way, which lays a basis for the reverse hierarchy theory (RHT). This theory states that attention propagates from the top level of the visual hierarchy that processes gist and abstract information of input, to the bottom level that processes local details. Inspired by the theory, we develop a computational model for saliency detection in images. First, the original image is… Show more

A number of psychological and physiological evidences suggest that early visual attention works in a coarse-to-fine way, which lays a basis for the reverse hierarchy theory (RHT). This theory states that attention propagates from the top level of the visual hierarchy that processes gist and abstract information of input, to the bottom level that processes local details. Inspired by the theory, we develop a computational model for saliency detection in images. First, the original image is downsampled to different scales to constitute a pyramid. Then, saliency on each layer is obtained by image super-resolution reconstruction from the layer above, which is defined as unpredictability from this coarse-to-fine reconstruction. Finally, saliency on each layer of the pyramid is fused into stochastic fixations through a probabilistic model, where attention initiates from the top layer and propagates downward through the pyramid. Extensive experiments on two standard eye-tracking datasets show that the proposed method can achieve competitive results with state-of-the-art models. Show less