Home

Students

Publications

Google Scholar Page

CV

Contact

Mohsen Bayati Assistant Professor of Operations, Information and Technology at Graduate School of Business Assistant Professor of Electrical Engineering (by courtesy) Advising faculty in Biomedical Informatics Stanford University

Announcements

I co-organize OIT Seminar and a bi-weekly seminar on Data, Inference, and Society at GSB.

I am a program committee member for AMIA 2013 and Nicholson Competition.

Research

My main research areas of interest include:

• Data-driven healthcare: predictions and dynamic decisions.
• Graphical models and message-passing algorithms.
• Probabilistic and statistical methods for inference from large-scale data.

Teaching

• Spring 2015: OIT 673Data-driven Decision Making and Applications in Healthcare (PhD)

• Winter 2015: OIT 536 Data for Action: From Insights to Applications (MBA Elective)

• Winters 2013-2015: OIT 367 Business Intelligence from Big Data (MBA Core)

• Spring 2012: OIT 267 Data and Decisions - Accelerated (MBA Core)

Selected Projects (for a complete list click here)

Data-Driven Decision Making in Healthcare

1. M. Bayati, M. Braverman, M. Gillam, K. Mack, G. Ruiz, M. Smith, and E. Horvitz, Data-Driven Decisions for Reducing Readmissions for Heart Failure: General Methodology and Case Study , PLoS ONE, DOI: 10.1371/journal.pone.0109264, 2014.
2. J. Goh, M. Bayati, S. Zenios, S. Singh, and D. Moore, Data Uncertainty in Markov Chains: Application to Cost-effectiveness Analyses of Medical Innovations , Working paper.
   Co-Winner of the William Pierskalla best paper award in health care.
3. N. Baker, M. Bayati, R. Torguson, K. Mack, H. Rappaport, E. Horvitz, R. Waksman, Identifying Patients at High Risk for Readmission following Treatment for Acute Myocardial Infarction: a Data-Centric Approach , American Heart Association Conference, Chicago 2014.
4. M. Braverman, M. Bayati, E. Horvitz, and M. Gillam, Health care policy development and execution, US Patent application, June 2010.

Summary: Rehospitalization -patient admission to a hospital soon after the discharge- is both common and costly. Nearly one in every five patients is readmitted to the hospital within 30 days of their discharge. The estimated cost of unplanned rehospitalizations to Medicare in 2004 was around $17.4 billion. Research shows that hospital initiatives such as: patient education programs, follow-up home visits by pharmacists, extensive discharge packages, etc., can avert many rehospitalizations. However, proper allocation of these costly and limited resources is a challenging problem. The first paper above represent a project on applications of statistical learning for identifying patients with highest risk of being rehospitalized and obtaining a decision support mechanism for allocating scarce resources to post-discharge support. The result is an automated risk prediction system that is currently in use in several hospitals across US and Europe. Here is a short video describing this project. can be found here.

The second paper develops a theoretical framework for cost-effectiveness analysis of medical innovations challenged by data inadequacy. When Markov chains are used as a computational tool for such studies, a possible consequence of this lack of data is that the transition matrix of the chain cannot be estimated precisely. This paper shows, how to compute maximal and minimal values for the discounted value of the chain (with respect to a vector of state-wise costs or rewards) as these uncertain transition parameters jointly vary within a given uncertainty set. It shows that these problems are computationally tractable if the uncertainty set has a row-wise structure. Conversely, It proves that if the row-wise structure is relaxed slightly, the problems become computationally intractable (NP-hard). The developed model is used to assess the cost-effectiveness of fecal immunochemical testing (FIT), a new screening method for colorectal cancer. The results show that despite the large uncertainty in existing data on FIT's performance, it is a cost-effective alternative screening modality to colonoscopy.

Graphical Models, Approximate Message Passing, and Statistical Learning

1. M. Bayati, and A. Montanari, The dynamics of message passing on dense graphs, with applications to compressed sensing, IEEE Transcations on Information Theory, Vol. 57, No. 2, 2011.
2. M. Bayati, and A. Montanari, The LASSO risk for gaussian matrices, IEEE Transcations on Information Theory, Vol. 58, No. 4, 2012.
3. M. Bayati, M. Lelarge and A. Montanari, Universality in Polytope Phase Transitions and Message Passing Algorithms, Accepted to Annals of Applied Probability, 2013.
4. M Bayati, M. A. Erdogdu, and A. Montanari, Estimating LASSO risk and noise level, NIPS, 2013.

Summary: Recently, Donoho, Maleki and Montanari introduced approximate message passing (AMP) as an extremely effective algorithm for reconstructing high dimensional sparse signals from a small number of observations. They also showed (through extensive numerical experiments) that dynamics of AMP is accurately tracked by a simple one-dimensional iteration termed "state evolution". In these papers we provided the first rigorous foundation to state evolution. We proved that indeed it holds asymptotically in the large system limit for sensing matrices with i.i.d. gaussian entries. Our techniques also provide a new approach for the analysis of message-passing algorithms on dense graphs.

In the second paper, we applied our results to the popular approach for dimensionality reduction known as the LASSO. We proved asymptotically sharp predictions and explicit expressions for operating characteristics of the LASSO (e.g., mean square error) that is the first rigorous derivation of such explicit formulas for random instances. Through simulations on real data matrices (gene expression data and hospital medical records) we observed that these results can be relevant in a broad array of practical applications.

The third paper extends the first paper beyond the gaussian assumption. In particular it proves a slightly weaker form of the result for sensing matrices with i.i.d. distribution with subgaussian tail and using this a conjecture from polytope geometry due to Donoho and Tanner is resolved. The fourth paper extends the results of the second paper to the more realistic situations when the distribution of original signal and noise variance are unknown. It also obtains a consistent estimate for the noise variance which outperforms existing estimate methods.

Modeling of Large Networks with Given Constraints

1. M. Bayati, J. H. Kim and A. Saberi, A sequential algorithm for generating random graphs, Algorithmica, Vol. 58, No. 4, 2010.
   Software (by David Gleich)
2. M. Bayati, A. Montanari, and A. Saberi, Generating Random Graphs without Short Cycles, Submitted 2013.

Summary: A central hurdle in working with large networks is the lack of good random graph models that capture their specific properties. Such random graph models can be useful for example in simulating algorithms for the Internet or detecting motifs (patterns) in biological systems. Unfortunately, the existing algorithms for generating random graphs with given degrees have large running times (quadratic on problem size), making them impractical to use for networks with millions of nodes. The first paper provides the fastest (almost linear running time) algorithm and proved its correctness when the node degrees are in certain range. The second paper extends that algorithm (with a different analysis technique that yields sharper bounds) to design an efficient algorithm for generating random graphs with no short cycles These graphs are used to construct high performance codes that can achieve the Shannon capacity.

Belief Propagation Algorithm for Distributed Optimization: Theory and Applications

1. M Bayati, C. Borgs, J. Chayes, R. Zecchina, Belief-Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions SIAM Journal in Discrete Math, 25, pp. 989-1011, 2011.
2. M.Bayati, D. Shah and M. Sharma, Max-product for maximum weight matching: convergence, correctness and LP duality, IEEE Transactions on Information Theory, Vol. 54, No 3, 2008.
3. M. Bayati, C. Borgs, A. Braunstein, J. Chayes, A. Ramezanpour, and R. Zecchina, Statistical Mechanics of Steiner Trees, Physical Review Letters (PRL), 101, 037208, 2008.
4. M Bayati, D. F. Gleich, A. Saberi, Y. Wang, Message-passing algorithms for sparse network alignment, ACM Transactions of Knowledge Discovery and Data mining (TKDD), vol 7, pages 3:1-3-31, 2013.
   Software and Data

Summary: Belief propagation (BP) is a distributed algorithm that has been very successfully used in many areas including machine learning and optimization. Despite its spectacular success, the BP algorithm is known to be correct only in cycle-free networks. However, in practice, the (loopy) BP algorithm works rather well in networks that have many cycles. The first two papers use BP algorithm for solving the well-known maximum weight matchings (MWM) problem. They prove that BP solves this problem correctly on all graphs when the linear programming (LP) relaxation of the problem has integer solutions. They also prove that BP and LP are equivalent for finding MWM. The proof technique gives a better understanding of the often noted, but poorly understood connection between BP and LP.

The third paper uses BP for the NP-hard problem of finding minimum weight Steiner tree and obtains a very efficient algorithm. The algorithm is effective in systems biology for finding previously undetected protein associations in cell signaling, as well as in data clustering.



The fourth paper applies BP method to the network alignment problem that generalizes and unifies several approaches for forming a matching or alignment between the nodes of two networks. The paper proposes a mathematical programming framework for network alignment problem and a sparse variation of it where only a small number of matches between the nodes of the two networks are possible. It proposes new message passing algorithms that allow to compute, very efficiently, near optimal solutions to the sparse network alignment problems with network sizes as large as hundreds of thousands of nodes. Using (rigorous) linear programming upper-bounds it shows that the proposed algorithms produce near optimal solutions on problems in bioinformatics, in ontology matching, and on synthetic problems.

Contact Info