Papers

List of papers published/submitted to peer reviewed conferences/journals. Please click on the paper to read the abstract and link to full paper.

  • [1] Manzil Zaheer, Michael Wick, Jean-Baptiste Tristan, Alexander J Smola, Guy L Steele Jr, “Exponential Stochastic Cellular Automata for Massively Parallel Inference,” [accepted at AISTATS 2016]

    Abstract: We propose an embarrassingly parallel, memory efficient inference algorithm for latent variable models in which the complete data likelihood is in the exponential family. The algorithm is a stochastic cellular automaton and converges to a valid maximum a posteriori fixed point. Applied to latent Dirichlet allocation we find that our algorithm is over an order or magnitude faster than the fastest current approaches. A simple C++/MPI implementation on a 8-node cluster samples 570 million tokens per second. We process 3 billion documents and achieve predictive power competitive with collapsed Gibbs sampling and variational inference.

    PDF CODE SLIDES

  • [2] Manzil Zaheer, Amr Ahmed, Ha Loc Do, Jay-Yoon Lee, Sujith Ravi, Alexander J Smola, “Fast Sampling Algorithms for Sparse Latent Variable Models,” [submitted to JMLR 2015]

    Abstract: Latent variable models have become a staple of statistical modelling. Due to their size, inference in these models presents a formidable challenge. In particular, it is difficult to exploit object sparsity, whenever the overall generative model is large and dense. We survey a broad range of MCMC sampling algorithms for topic model inference and investigate their performance both theoretically and experimentally. In particular, we describe the Metropolis-Hastings-Walker method, a novel decomposition based on Fenwick trees and their extension to the Hierarchical Dirichlet Process. Our analysis includes detailed measurements in terms of mixing properties, multithreading, their suitability for modern microprocessors. The associated code is both fast and scalable, and available as open source. A single server beats established distributed solutions.

    PDF CODE SLIDES

  • [3] Rajarshi Das*, Manzil Zaheer*, Christopher J Dyer, “Gaussian LDA for Topic Models with Word Embeddings,” In Proceedings of the 53th Annual Meeting of the Association for Computational Linguistics: Long Papers-Volume 1, pp. 795-804. Association for Computational Linguistics, 2015.

    Abstract: Continuous space word embeddings learned from large, unstructured corpora have been shown to be effective at capturing semantic regularities in language. In this paper we replace LDA's parameterization of "topics" as categorical distributions over opaque word types with multivariate Gaussian distributions on the embedding space. This encourages the model to group words that are a-priori known to be semantically related into topics. To perform inference, we introduce a fast collapsed Gibbs sampling algorithm based on Cholesky decompositions of covariance matrices of the posterior predictive distributions. We further derive a scalable algorithm that draws samples from stale posterior predictive distributions and corrects them with a Metropolis--Hastings step. Using vectors learned from a domain-general corpus (English Wikipedia), we report results on two document collections (20-newsgroups and NIPS). Qualitatively, Gaussian LDA infers different (but still very sensible) topics relative to standard LDA. Quantitatively, our technique outperforms existing models at dealing with OOV words in held-out documents.

    PDF CODE SLIDES

  • [4] Jay-Yoon Lee*, Manzil Zaheer*, Stephan Günnemann, Alexander J Smola, “Preferential Attachments in Graphs with Affinities,” In Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, pp. 571-580. 2015.

    Abstract: Preferential attachment models for random graphs are successful in capturing many characteristics of real networks such as power law behavior. At the same time they lack flexibility to take vertex to vertex affinities into account, a feature that is commonly used in many link recommendation algorithms. We propose a random graph model based on both node attributes and preferential attachment. This approach overcomes the limitation of existing models on expressing vertex affinity and on reflecting properties of different subgraphs. We analytically prove that our model preserves the power law behavior in the degree distribution as expressed by natural graphs and we show that it satisfies the small world property. Experiments show that our model provides an excellent fit of many natural graph statistics and we provide an algorithm to infer the associated affinity function efficiently.

    PDF CODE SLIDES

  • [5] Fa Wang, Manzil Zaheer, Xin Li, Jean-Olivier Plouchart and Alberto Valdes-Garcia, “Co-Learning Bayesian Model Fusion: Efficient Performance Modeling of Analog and Mixed-Signal Circuits Using Side Information,” In Proceedings of the 2015 IEEE/ACM International Conference on Computer-Aided Design, pp. x-x. IEEE Press, 2015.

    Abstract: Efficient performance modeling of today's analog and mixed-signal (AMS) circuits is an important yet challenging task. In this paper, we propose a novel performance modeling algorithm that is referred to as Co-Learning Bayesian Model Fusion (CL-BMF). The key idea of CL-BMF is to take advantage of the additional information collected from simulation and/or measurement to reduce the performance modeling cost. Different from the traditional performance modeling approaches which focus on the prior information of model coefficients (i.e. the coefficient side information) only, CL-BMF takes advantage of another new form of prior knowledge: the performance side information. In particular, CL-BMF combines the coefficient side information, the performance side information and a small number of training samples through Bayesian inference based on a graphical model. Two circuit examples designed in a commercial 32nm SOI CMOS process demonstrate that CL-BMF achieves up to 5X speed-up over other state-of-the-art performance modeling techniques without surrendering any accuracy.

    PDF CODE SLIDES

  • [6] Manzil Zaheer, Chenjie Gu, Xin Li, “mTunes: efficient post-silicon tuning of mixed-signal/RF integrated circuits based on Markov decision process.” In Proceedings of the 52nd Annual Design Automation Conference, p. 170. ACM, 2015.

    Abstract: Uncertainty prevails in IC manufacturing and circuit operation. In particular, process variability has a huge impact on circuit performance, especially for mixed-signal/RF circuits, leading to unacceptable yields. Additionally, environmental uncertainties, such as temperature fluctuation and channel variation, further deteriorate performances in field. To combat variability, circuits are often made reconfigurable by adding tunable knobs to recover circuit performance in the post-manufacturing stage. However, as the number of knobs increases, knob tuning becomes challenging due to the huge search space. In fact, knob-tuning policies can have an observable impact on final performance and power consumption. In this paper, we propose mTunes, a method based on the Markov decision process for dynamically choosing the “right” knob tuning sub-routine from a pre-defined set achieving a balance between performance and power constraints. The proposed method has been applied to a reconfigurable RF front-end design, showing 60% improvement in yield compared to static tuning policies.

    PDF CODE SLIDES

  • [7] Hsiao-Yu Fish Tung, Chao-Yuan Wu, Manzil Zaheer, Alexander J Smola, “Spectral Methods for Hierarchical Dirichlet Process,” NIPS Workshop on Nonparametric Methods for Large Scale Representation Learning, 2015.

    Abstract: The Hierarchical Dirichlet Process (HDP) is a versatile, albeit computationally expensive tool for statistical modeling of mixture models. In this paper, we introduce a spectral algorithm. We show that it is both computationally and statistically efficient. In particular, we derive the lower-order moments of the HDP and give reconstruction guarantees. Moreover, we show that hierarchical spectral method is able to generate a better results regarding likelihood performance.

    PDF CODE SLIDES

  • [8] Manzil Zaheer, Michael Wick, Jean-Baptiste Tristan, Alexander J Smola, Guy L Steele Jr, “Exponential Stochastic Cellular Automata for Massively Parallel Inference,” NIPS Workshop on Machine Learning Systems, 2015.

    Abstract: We propose an embarrassingly parallel, memory efficient inference algorithm for latent variable models in which the complete data likelihood is in the exponential family. The algorithm is a stochastic cellular automaton and converges to a valid maximum a posteriori fixed point. Applied to latent Dirichlet allocation we find that our algorithm is over an order of magnitude faster than the fastest current approaches. A simple C++/MPI implementation on a 8-node cluster samples 503 million tokens per second. We process 3 billion documents and achieve predictive power competitive with collapsed Gibbs sampling and variational inference.

    PDF CODE SLIDES

  • [9] Manzil Zaheer, Michael Wick, Satwik Kottur, Jean-Baptiste Tristan “Comparing Gibbs, EM and SEM for MAP Inference in Mixture Models,” NIPS Workshop on Optimization for Machine Learning, 2015.

    Abstract: Classic inference algorithms such as Gibbs sampling and EM often perform well in practice, but selecting between them when scaling a model to large datasets is difficult. In particular, Gibbs sampling is easy to distribute, but difficult to parallelize, while EM is easy parallelize, but difficult to distribute. Remarkably, the relatively obscure stochastic EM (SEM) combines the computational strengths of the two methods, without inheriting any of their weaknesses. Indeed, we highlight these strengths by deriving the three algorithms on a simple, yet representative (of the general class) mixture model. We also demonstrate empirically that the MAP solutions found by the three algorithms are comparable across a wide variety of parameter settings; further, SEM appears more robust to poor initialization.

    PDF CODE SLIDES

  • [10] Manzil Zaheer, Xin Li and Chenjie Gu, “MPME-DP: Bayesian Model Fusion on Dirichlet Process for Multi-Population Moment Estimation of Analogue/Mixed-Signal Circuits,” In Proceedings of the 2014 IEEE/ACM International Conference on Computer-Aided Design, pp. 316-323. IEEE Press, 2014.

    Abstract: Moment estimation is one of the most important tasks to appropriately characterize the performance variability of today’s nanoscale integrated circuits. In this paper, we propose an efficient algorithm of multi-population moment estimation via Dirichlet Process (MPME-DP) for validation of analog and mixed-signal circuits with extremely small sample size. The key idea is to partition all populations (e.g., different environmental conditions, setup configurations, etc.) into groups. The populations within the same group are similar and their common knowledge can be extracted to improve the accuracy of moment estimation. As will be demonstrated by the silicon measurement data of a high-speed I/O link, MPME-DP reduces the moment estimation error by up to 65% compared to other conventional estimators.

    PDF CODE SLIDES

  • [11] Chenjie Gu, Manzil Zaheer and Xin Li, “Multiple-Population Moment Estimation: Exploiting Inter-Population Correlation for Efficient Moment Estimation in Analog/Mixed-Signal Validation,” Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on 33, no. 7 (2014): 961-974.

    Abstract: Moment estimation is an important problem during circuit validation, in both presilicon and postsilicon stages. From the estimated moments, the probability of failure and parametric yield can be estimated at each circuit configuration and corner, and these metrics are used for design optimization and making product qualification decisions. The problem is especially difficult if only a very small sample size is allowed for measurement or simulation, as is the case for complex analog/mixed-signal circuits. In this paper, we propose an efficient moment estimation method, called multiple-population moment estimation (MPME), that significantly improves estimation accuracy under small sample size. The key idea is to leverage the data collected under different corners/configurations to improve the accuracy of moment estimation at each individual corner/configuration. Mathematically, we employ the hierarchical Bayesian framework to exploit the underlying correlation in the data. We apply the proposed method to several datasets including postsilicon measurements of a commercial high-speed I/O link, and demonstrate an average error reduction of up to 2×, which can be equivalently translated to significant reduction of validation time and cost.

    PDF CODE SLIDES

  • [12] Manzil Zaheer and Anup K Gogoi, “Mellin-Fourier Transform based Communication Scheme for Wideband Linear Time Varying Channels,” Advanced Communication Technology (ICACT), 2013 15th International Conference on, 27-30 January 2013 [Accepted, but not presented]

    Abstract: This paper proposes a novel communication scheme designed for wideband linear time varying channels. It is based upon a combination of Mellin and Fourier transforms. The proposed scheme is able to equalize simultaneous Doppler and delay spread introduced by wideband linear time varying channel. The proposed method eliminates need of large memory requirements for buffering or intensive computational requirements of contemporary systems. Analytical development of the proposed system is presented along with computer simulations demonstrating the effectiveness of the same.

    PDF CODE SLIDES

  • [13] Andreas Reinhardt, Dominic Burkhardt, Manzil Zaheer and Ralf Steinmetz, “Electric Appliance Classification Based on Distributed High Resolution Current Sensing,” Local Computer Networks (LCN), 2012 IEEE 37th Conference on, pp. 1003-1009, 22-25 October 2012.

    Abstract: Today's solutions to inform residents about their electricity consumption are mostly confined to displaying aggregate readings collected at meter level. A reliable identification of appliances that require disproportionate amounts of energy for their operation is generally unsupported by these systems, or at least requires significant manual configuration efforts. We address this challenge by placing low-cost measurement and actuation units into the mains connection of appliances. The distributed sensors capture the current flow of individual appliances at a sampling rate of 1.6kHz and apply local signal processing to the readings in order to extract characteristic fingerprints. These fingerprints are communicated wirelessly to the evaluation server, thus keeping the required airtime and energy demand of the transmission low. The evaluation server employs machine learning techniques and caters for the actual classification of attached electric appliances based on their fingerprints, enabling the correlation of consumption data and the appliance identity. Our evaluation is based on more than 3,000 current consumption fingerprints, which we have captured for a range of household appliances. The results indicate that a high accuracy is achieved when locally extracted current consumption fingerprints are used to classify appliances.

    PDF CODE SLIDES

  • [14] Manzil Zaheer, Jaspreet Singh Suri and Harshal B Nemade, “Primary Side Control based Inductively Coupled Powering Scheme for Biomedical Implants,” EMBS Biomedical Health Informatics, 2012 IEEE International Conference on, pp. 174-179, 2-7 January 2012.

    Abstract: This paper proposes a novel and easy technique to implement primary control for inductively coupled power transfer systems. With the proposed design, the control law boils down simply to a multiplication of voltages across two capacitors in the primary side. The advantages include easy implementation and the topology is favourable for biomedical application, as any chance of heating due to presence of power flow controller in secondary side is eliminated. The effectiveness of the proposed power pickup and its applicability to general wireless power transfer applications has been demonstrated by both simulation and experimental results.

    PDF CODE SLIDES

  • [15] Andreas Reinhardt, Dominic Burkhardt, Parag S Mogre, Manzil Zaheer and Ralf Steinmetz, “SmartMeter.KOM: A low-cost wireless sensor for distributed power metering,” Local Computer Networks (LCN), 2011 IEEE 36th Conference on, pp. 1032-1039, 4-7 October 2011

    Abstract: Most current smart metering solutions aim at increasing user awareness for their household’s electrical energy consumption. Although some smart meters make use of wireless data transfers between their sensor and display units, their integration into existing wireless sensor networks is hampered by proprietary communication interfaces and their lack of reprogrammability. Furthermore, the sole availability of aggregate consumption values renders current meters insufficient for novel application scenarios like smart home automation, for which information at device-level granularity and high resolution is vital. We address these shortcomings of existing solutions by presenting SmartMeter.KOM, our wireless sensor node capable of determining the current consumption of individual electrical appliances at high resolution. The platform is based on low-power hardware and incorporates a reprogrammable microcontroller which allows developers to easily deploy new algorithms. Its IEEE 802.15.4-compliant radio transceiver makes its integration with existing sensor networks possible, and thus enables their integration in smart buildings. We demonstrate the versatility of SmartMeter.KOM by presenting prototypical implementations of smart applications and identifying further research directions.

    PDF CODE SLIDES

  • [16] Manzil Zaheer, Nitish Patel and Aiguo Patrick Hu, “Parallel tuned contactless power pickup using saturable core reactor,” Sustainable Energy Technologies (ICSET), 2010 IEEE International Conference on, pp. 1-6, 6-9 December 2010

    Abstract: This paper proposes a novel contactless secondary power pickup designed for inductively coupled contactless power transfer systems. It is based upon parallel LC tuning with the equivalent capacitance varied by a saturable core reactor (SCR). The proposed technique allows the power pickup to achieve full-range operation for power flow regulation and maintain constant output voltage at a high quality factor Q. The method eliminates the tedious fine-tuning process associated with traditional fixed power pickup tuning methods and eases the component selection. Moreover, it can overcome the online circuit parameter variations and automatically achieve the maximum power transfer capacity when required. In order to meet dynamic load demands, the SCR is controlled to be a variable inductor. A simple algorithm is developed to change the tuning condition of the power pickup. The effectiveness of the proposed power pickup and its applicability to general wireless power transfer applications has been demonstrated by both simulation and experimental results.

    PDF CODE SLIDES

Project Reports

Here are some of the course project reports I could get hold of.

  • [1] Manzil Zaheer, Carlos Ramirez, Soumya Batra, Mladen Kolar, “Large Scale Structure Learning of Conditional Gaussian Graphical Models,” Probabilistic Graphical Models Course taught by Prof Eric Xing.

    PDF CODE SLIDES

  • [2] Manzil Zaheer, Abhinav Mourya, “Mining Interesting Local Structure from Tensors,” Data mining and multimedia database Course taught by Prof Christos Falutsos.

    PDF CODE SLIDES

  • [3] Sahil Single, Manzil Zaheer, “Local List-Decoding of Reed-Muller Codes over Binary Field,” Coding Theory Course taught by Prof Venkat Guruswami.

    PDF CODE SLIDES

  • [4] Manzil Zaheer, Jay-Yoon Lee, “Gaussian-Stick Breaking Process,” Statistical Machine Learning Course taught by Prof Larry Wasserman.

    PDF CODE SLIDES

  • [5] Manzil Zaheer,“Does Information always represent quantity meant?”

    PDF CODE SLIDES

Homework

Here I will put some of the course homework with nonconventional solutions I came up with.