NIPS Workshop on Algebraic and Combinatorial Methods in Machine Learning, Whistler 2008

Algebraic statistics for random graph models: Markov bases and their uses

author: Sonja Petrović, The University of Illinois at Chicago
author: Alessandro Rinaldo, Carnegie Mellon University
author: Stephen E. Fienberg, Carnegie Mellon University
published: Dec. 20, 2008, recorded: December 2008, views: 1168

Slides

Slides
0:00	Algebraic Statistics of p1 Network Models: Markov Bases and Their Uses
1:03	Context (1)
1:28	Context (2)
1:48	Context (3)
1:51	Context (4)
2:38	Context (4)
2:52	Context (6)
3:02	General framework for networks evolving over time (1)
3:20	General framework for networks evolving over time (2)
3:50	General framework for networks evolving over time (3)
4:07	General framework for networks evolving over time (4)
4:15	General framework for networks evolving over time (5)
4:23	General framework for networks evolving over time (6)
4:48	Example: The Framingham "Obesity" Study (1)
6:29	Example: The Framingham "Obesity" Study (2)
7:08	Example: The Collective Dynamics of Smoking in a Large Social Network
7:38	Example: Monks in a Monastery
8:33	Holland and Leinhardt's p1 model (1)
9:20	Holland and Leinhardt's p1 model (2)
9:38	Holland and Leinhardt's p1 model (3)
10:25	Holland and Leinhardt's p1 model (4)
11:10	Estimation for p1
13:36	Aside - The Normal Distribution was 275 Years Old
13:57	Hotteling and the Normal Distribution
14:13	p1 in Log-linear Form
15:49	Primer: Algebraic Representation and Computer Algebra Tools
17:20	Algebraic Version of p1 in Log-linear Form (1)
17:29	Algebraic Version of p1 in Log-linear Form (2)
17:35	Algebraic Version of p1 in Log-linear Form (3)
17:47	p1 as a toric variety (1)
17:51	p1 as a toric variety (2)
18:02	p1 as a toric variety (3)
18:11	p1 as a toric variety (4)
18:34	p1 as a toric variety (5)
18:39	p1 as a toric variety (6)
18:45	Toric ideal of simplification of p1 (1)
18:54	Toric ideal of simplification of p1 (2)
19:12	Toric ideal of simplification of p1 (3)
19:26	Main Theorem - toric ideal of p1 (1)
19:45	Main Theorem - toric ideal of p1 (2)
19:49	Main Theorem - toric ideal of p1 (3)
19:57	Main Theorem - toric ideal of p1 (4)
20:05	Example with 4 nodes (1)
20:25	Example with 4 nodes (2)
20:34	3-node network (1)
20:51	3-node network (2)
20:58	3-node network (3)
21:23	3-node network (4)
21:31	4-node network: constant (1)
21:48	4-node network: constant (2)
21:57	4-node network: constant (3)
22:03	4-node network: constant (4)
22:08	4-node network: constant (5)
22:28	4-node network: constant (6)
22:45	4-node network: edge-dependent (1)
22:50	4-node network: edge-dependent (2)
22:57	4-node network: edge-dependent (3)
23:00	4-node network: edge-dependent (4)
23:03	4-node network: edge-dependent (5)
23:05	4-node network: edge-dependent (6)
23:10	4-node network: edge-dependent (7)
23:15	4-node network: edge-dependent (8)
23:19	4-node network: edge-dependent (9)
23:24	4-node network: edge-dependent (10)
23:30	Summary
28:58	Questions

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

Lecture popularity: You need to login to cast your vote.

Description

We use algebraic geometry to study a statistical model for the analysis of networks represented by graphs with directed edges due to Holland and Leinhardt, known as p1, which allows for differential attraction (popularity) and expansiveness, as well as an additional effect due to reciprocation. In particular, we attempt to derive Markov bases for p1 and to link these to the results on Markov bases for working with log-linear models for contingency tables. Because of the contingency table representation for p1 we expect some form of congruence. Markov bases and related algebraic geometry notions are useful for at least two statistical problems: (i) determining condition for the existence of maximum likelihood estimates, and (ii) using them to traverse conditional (given minimal sufficient statistics) sample spaces, and thus generating ``exact'' distributions useful for assessing goodness of fit. We outline some of these potential uses for the algebraic representation of p1.