Data Science and Machine Learning

Topics

Data driven discovery of sparse dynamics

Rachel Ward and collaborator Giang Tran (former Bing Instructor in the UT Mathematics department) are investigating the identification of a dynamical system (say, within the class of polynomial systems of ordinary differential equations) given snapshots of the system in time. Such problems prove challenging when there is a high level of noise on the data. In the paper Exact recovery of Chaotic systems from highly corrupted data, they show that if the underlying trajectory exhibits ergodicy or chaos, and if the underlying dynamics have a sparse representation with respect to the polynomial basis, then a LASSO / l1 type algorithm will exactly recover the underlying dynamics even when most of the data is highly corrupted. This establishes a new link between the areas of dynamical systems and machine learning / sparse recovery, and many interesting questions remain.

Detecting planted communities in random graphs

The stochastic block model (aka. planted partition model) is a popular model for representing networks with communities. Elchanan Mossel, Joe Neeman, and Allan Sly have been investigating algorithms and fundamental limits for detecting and recovering these communities. They established sharp transitions for the problem of extracting non-trivial information and the problem of exactly recovering communities. They also gave a new algorithm that obtains provably optimal accuracy for the problem of detecting communities in “Consistency thresholds for the planted bisection model” and “Belief propagation, robust reconstruction, and optimal recovery of block models“.

Mathematics of social networks

Avhishek Chatterjee, François Baccelli and Sriram Vishwanath proposed a stochastic extension of the bounded confidence model where opinions take their values in the Euclidean space and where friendship and interactions are dynamically defined through time varying and random neighborhoods. Two basic sub-models are defined: the influencing model where each agent is an attractor to the opinions of its neighbors and the listening model where each agent gathers information from others to update its own opinions. The general model contains a rich set of variants for which they proposed a classification. They analyzed the stability of its dynamics. The analysis highlights the need of certain leaders with heavy tailed neighborhoods for stability to hold. See Pairwise Stochastic Bounded Confidence Opinion Dynamics: Heavy Tails and Stability

On the Steady State of Continuous Time Stochastic Opinion Dynamics

François Baccelli, Sriram Vishwanath and Jae Oh Woo proposed a computational framework for continuous time opinion dynamics with additive noise. They derived a non-local partial differential equation for the distribution of opinions differences. They used Mellin transforms to solve the stationary solution of this equation in closed form. This approach can be applied both to linear dynamics on an interaction graph and to bounded confidence dynamics in the Euclidean space. To the best of our knowledge, the closed form expression on the stationary distribution of the bounded confidence model is the first quantitative result on the equilibria of this class of models.

Members

Jae Oh Woo

Department of Mathematics and Department of Electrical and Computer Engineering, UT Austin
jaeoh.woo@utexas.edu
Read More »

Rachel Ward

Department of Mathematics, UT Austin
rward@math.utexas.edu
Read More »

Anastasios Kyrillidis

Department of Electrical and Computer Engineering, UT Austin
anastasios@utexas.edu
Read More »

Constantine Caramanis

Department of Electrical and Computer Engineering, UT Austin
constantine@utexas.edu
512 471 9269
Read More »

Sujay Sanghavi

Department of Electrical and Computer Engineering, UT Austin
sanghavi@mail.utexas.edu
512 475 9798
Read More »

Sanjay Shakkottai

Department of Electrical and Computer Engineering, UT Austin
shakkott@austin.utexas.edu
512 471 5376
Read More »

Joe Neeman

Department of Electrical and Computer Engineering and Department of Mathematics, UT Austin
joeneeman@gmail.com
Read More »

Abishek Sankararaman

Department of Electrical and Computer Engineering, UT Austin
abishek@utexas.edu
Read More »

Avhishek Chatterjee

Department of Electrical and Computer Engineering, UT Austin
avhishek@utexas.edu
Read More »

Sriram Vishwanath

Department of Electrical and Computer Engineering, UT Austin
sriram@ece.utexas.edu
512 471 1190
Read More »

Gustavo de Veciana

Department of Electrical and Computer Engineering, UT Austin
gustavo@ece.utexas.edu
512 471 1573
Read More »

François Baccelli

Department of Mathematics and Deparment of Electrical and Computer Engineering, UT Austin
baccelli@math.utexas.edu
512 471 17 54
Read More »

Publications

2017-05-09_1000911

Pairwise Stochastic Bounded Confidence Opinion Dynamics: Heavy Tails and Stability

François Baccelli, Avhishek Chatterjee, and Sriram Vishwanath To appear in IEEE Transactions Automatic Control
Download PDF
2016-06-15_1000936

Exact Recovery of Chaotic Systems from Highly Corrupted Data

Giang Tran, Rachel Ward To appear in SIAM Multiscale Modeling and Simulation
Download PDF
2015-06-16_1000329

Consistency thresholds for the planted bisection model

Elchanan Mossel, Joe Neeman and Allan Sly To appear in Symposium on the Theory of Computer Science 2015
Download PDF
2015-04-30_1000324

Pairwise Stochastic Bounded Confidence Opinion Dynamics: Heavy Tails and Stability

François Baccelli, Avhishek Chatterjee and Sriram Vishwanath Proceedings IEEE Infocom 2015
2014-06-18_1000333

Belief propagation, robust reconstruction, and optimal recovery of block models

Elchanan Mossel, Joe Neeman and Allan Sly Conference on Learning Theory 2014
Download PDF