Graphical Model Structure Learning with Regularization

Mark Schmidt

Description

Graphical Model Structure Learning with 1-Regularization Mark Schmidt July 27, 2010 1

• mac league


• hockey


• pc win


• undirected graphical


• graphical model


• directed graphical


• structure learning

Sujets

• Schmidt
• Hockey
• Graphical model

Informations

• Publié par: pefav
• Nombre de lectures: 22
• Langue: English

Extrait

Graphical Model Structure Learning with
‘ -Regularization1
Mark Schmidt
July 27, 2010
1Outline
1. Introduction
2. Optimization with ‘ -Regularization1
3. Optimization with Group ‘ -Regularization1
4. Directed Graphical Model Structure Learning
5. Undirected Graphical Model Structure Learning
6. Hierarchical Log-Linear Model Structure Learning
7. Discussion
2What words are related?
Is a post with (car,drive,hockey,pc,win) spam?
What is p(carjdrive)? What about p(carjdrive; les)?
Given the values of some variables, what is the most likely
way to ll-in the other variables?
Motivation for Graphical Model Structure Learning
car drive les hockey mac league pc win
0 0 1 0 1 0 1 0
0 0 0 1 0 1 0 1
1 1 0 0 0 0 0 0
0 1 1 0 1 0 0 0
0 0 1 0 0 0 1 1
3Is a post with (car,drive,hockey,pc,win) spam?
What is p(carjdrive)? What about p(carjdrive; les)?
Given the values of some variables, what is the most likely
way to ll-in the other variables?
Motivation for Graphical Model Structure Learning
car drive les hockey mac league pc win
0 0 1 0 1 0 1 0
0 0 0 1 0 1 0 1
1 1 0 0 0 0 0 0
0 1 1 0 1 0 0 0
0 0 1 0 0 0 1 1
What words are related?
3What is p(carjdrive)? What about p(carjdrive; les)?
Given the values of some variables, what is the most likely
way to ll-in the other variables?
Motivation for Graphical Model Structure Learning
car drive les hockey mac league pc win
0 0 1 0 1 0 1 0
0 0 0 1 0 1 0 1
1 1 0 0 0 0 0 0
0 1 1 0 1 0 0 0
0 0 1 0 0 0 1 1
What words are related?
Is a post with (car,drive,hockey,pc,win) spam?
3Given the values of some variables, what is the most likely
way to ll-in the other variables?
Motivation for Graphical Model Structure Learning
car drive les hockey mac league pc win
0 0 1 0 1 0 1 0
0 0 0 1 0 1 0 1
1 1 0 0 0 0 0 0
0 1 1 0 1 0 0 0
0 0 1 0 0 0 1 1
What words are related?
Is a post with (car,drive,hockey,pc,win) spam?
What is p(carjdrive)? What about p(carjdrive; les)?
3Motivation for Graphical Model Structure Learning
car drive les hockey mac league pc win
0 0 1 0 1 0 1 0
0 0 0 1 0 1 0 1
1 1 0 0 0 0 0 0
0 1 1 0 1 0 0 0
0 0 1 0 0 0 1 1
What words are related?
Is a post with (car,drive,hockey,pc,win) spam?
What is p(carjdrive)? What about p(carjdrive; les)?
Given the values of some variables, what is the most likely
way to ll-in the other variables?
3Example of Learned Graph Structure
case children bible health
course christian insurance
computer evidence
disk email display card fact earth
files graphics government god
dos format help data image video gun human car president israel jesus
drive memory number power law engine dealer jews baseball
ftp mac scsi problem rights war religion games fans
pc program phone nasa state question hockey
software research shuttle league nhl
launch moon science orbit players
space university world season
system driver team
version technology win
windows won
4case children bible health
course christian insurance
computer evidence
disk email display card fact earth
case children bible health
files graphics government god
course christian insurance
dos format help data image video gun human car president israel jesus
Example of Learned Graph Structure
drive memory number power law engine dealer jews baseball
computer evidence
ftp mac scsi problem rights war religion games fans
disk email display card fact earth
pc program phone nasa state question hockey
files graphics government god
software research shuttle league nhl
launch moon science orbit players dos format help data image video gun human car president israel jesus
space university world season
drive memory number power law engine dealer jews baseball
system driver team
ftp mac scsi problem rights war religion games fans
version technology win
pc program phone nasa state question hockey
windows won
5
software research shuttle league nhl
launch moon science orbit players
space university world season
system driver team
version technology win
windows wonThere has been growing interest in ‘ -regularization:1
Gives regularized estimate (like ‘ -regularization).2
Gives sparse estimate (like subset selection).
Formulated as a convex optimization.
Graphical Model Structure Learning with ‘ -Regularization1
X X1 1X X5 5
X X8 8X2 X2
X X6 6
X3 X3
X9 X9
X X7 7X X4 4
We consider parameter estimation in graphical models without
a known structure.
6