[UseMoney=30]

[/UseMoney]

书名On Probabilistic Conditional Independence Structures

作者Michael Jordan

出版商Springer

出版时间2005

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Motivational thoughts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Goals of the monograph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Structure of the book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1 Conditional independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Semi-graphoid properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Formal independence models . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.2 Semi-graphoids. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.3 Elementary independence statements . . . . . . . . . . . . . . . . 15
2.2.4 Problem of axiomatic characterization . . . . . . . . . . . . . . . 16
2.3 Classes of probability measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.1 Marginally continuous measures . . . . . . . . . . . . . . . . . . . . . 19
2.3.2 Factorizable measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.3 Multiinformation and conditional product . . . . . . . . . . . . 24
2.3.4 Properties of multiinformation function . . . . . . . . . . . . . . 27
2.3.5 Positive measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.6 Gaussian measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.7 Basic construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.4 Imsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3 Graphical Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.1 Undirected graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2 Acyclic directed graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3 Classic chain graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4 Within classic graphical models . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.4.1 Decomposable models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.4.2 Recursive causal graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.4.3 Lattice conditional independence models . . . . . . . . . . . . . 56
3.4.4 Bubble graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

3.5 Advanced graphical models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.5.1 General directed graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.5.2 Reciprocal graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.5.3 Joint-response chain graphs . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.5.4 Covariance graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.5.5 Alternative chain graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.5.6 Annotated graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.5.7 Hidden variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.5.8 Ancestral graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.5.9 MC graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.6 Incompleteness of graphical approaches. . . . . . . . . . . . . . . . . . . . . 63
4 Structural Imsets: Fundamentals . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.1 Basic class of distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.1.1 Discrete measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.1.2 Regular Gaussian measures . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.1.3 Conditional Gaussian measures. . . . . . . . . . . . . . . . . . . . . . 66
4.2 Classes of structural imsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.2.1 Elementary imsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.2.2 Semi-elementary and combinatorial imsets . . . . . . . . . . . . 71
4.2.3 Structural imsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.3 Product formula induced by a structural imset . . . . . . . . . . . . . . 74
4.3.1 Examples of reference systems of measures. . . . . . . . . . . . 75
4.3.2 Topological assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.4 Markov condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.4.1 Semi-graphoid induced by a structural imset . . . . . . . . . . 78
4.4.2 Markovian measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

4.5 Equivalence result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5 Description of Probabilistic Models . . . . . . . . . . . . . . . . . . . . . . . . 87
5.1 Supermodular set functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.1.1 Semi-graphoid produced by a supermodular function . . . 88
5.1.2 Quantitative equivalence of supermodular functions . . . . 90
5.2 Skeletal supermodular functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.2.1 Skeleton. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.2.2 Significance of skeletal imsets . . . . . . . . . . . . . . . . . . . . . . . 95
5.3 Description of models by structural imsets . . . . . . . . . . . . . . . . . . 99
5.4 Galois connection. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.4.1 Formal concept analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.4.2 Lattice of structural models . . . . . . . . . . . . . . . . . . . . . . . . . 104

6 Equivalence and Implication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.1 Two concepts of equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.1.1 Independence and Markov equivalence . . . . . . . . . . . . . . . 113
6.2 Independence implication. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.2.1 Direct characterization of independence implication . . . . 115
6.2.2 Skeletal characterization of independence implication . . 118
6.3 Testing independence implication . . . . . . . . . . . . . . . . . . . . . . . . . . 120
6.3.1 Testing structural imsets . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
6.3.2 Grade. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.4 Invariants of independence equivalence . . . . . . . . . . . . . . . . . . . . . 124
6.5 Adaptation to a distribution framework . . . . . . . . . . . . . . . . . . . . 126
7 The Problem of Representative Choice . . . . . . . . . . . . . . . . . . . . 131
7.1 Baricentral imsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
7.2 Standard imsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
7.2.1 Translation of DAG models . . . . . . . . . . . . . . . . . . . . . . . . . 135
7.2.2 Translation of decomposable models . . . . . . . . . . . . . . . . . 137
7.3 Imsets of the smallest degree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
7.3.1 Decomposition implication . . . . . . . . . . . . . . . . . . . . . . . . . . 142
7.3.2 Minimal generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

7.4 Span . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
7.4.1 Determining and unimarginal classes . . . . . . . . . . . . . . . . . 145
7.4.2 Imsets with the least lower class . . . . . . . . . . . . . . . . . . . . . 146
7.4.3 Exclusivity of standard imsets . . . . . . . . . . . . . . . . . . . . . . 148
7.5 Dual description. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
7.5.1 Coportraits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
7.5.2 Dual baricentral imsets and global view . . . . . . . . . . . . . . 152
8 Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
8.1 Two approaches to learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
8.2 Quality criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
8.2.1 Criteria for learning DAG models . . . . . . . . . . . . . . . . . . . 163
8.2.2 Score equivalent criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
8.2.3 Decomposable criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
8.2.4 Regular criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
8.3 Inclusion neighborhood. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
8.4 Standard imsets and learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
8.4.1 Inclusion neighborhood characterization . . . . . . . . . . . . . . 181
8.4.2 Regular criteria and standard imsets . . . . . . . . . . . . . . . . . 184
9 Open Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
9.1 Theoretical problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
9.1.1 Miscellaneous topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
9.1.2 Classification of skeletal imsets . . . . . . . . . . . . . . . . . . . . . . 195
9.2 Operations with structural models . . . . . . . . . . . . . . . . . . . . . . . . . 199

9.2.1 Reductive operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
9.2.2 Expansive operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
9.2.3 Cumulative operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
9.2.4 Decomposition of structural models . . . . . . . . . . . . . . . . . . 203
9.3 Implementation tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
9.4 Interpretation and learning tasks . . . . . . . . . . . . . . . . . . . . . . . . . . 209
9.4.1 Meaningful description of structural models . . . . . . . . . . . 209
9.4.2 Tasks concerning distribution frameworks . . . . . . . . . . . . 210
9.4.3 Learning tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
A.1 Classes of sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
A.2 Posets and lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
A.3 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
A.4 Topological concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
A.5 Finite-dimensional subspaces and convex cones . . . . . . . . . . . . . . 222
A.5.1 Linear subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
A.5.2 Convex sets and cones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
A.6 Measure-theoretical concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
A.6.1 Measure and integral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
A.6.2 Basic measure-theoretical results . . . . . . . . . . . . . . . . . . . . 228
A.6.3 Information-theoretical concepts . . . . . . . . . . . . . . . . . . . . . 230
A.6.4 Conditional probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
A.7 Conditional independence in terms of σ-algebras. . . . . . . . . . . . . 234
A.8 Concepts from multivariate analysis . . . . . . . . . . . . . . . . . . . . . . . . 236
A.8.1 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
A.8.2 Statistical characteristics of probability measures . . . . . . 238

A.8.3 Multivariate Gaussian distributions . . . . . . . . . . . . . . . . . . 239
A.9 Elementary statistical concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
A.9.1 Empirical concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
A.9.2 Statistical conception . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
A.9.3 Likelihood function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
A.9.4 Testing statistical hypotheses . . . . . . . . . . . . . . . . . . . . . . . 246
A.9.5 Distribution framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
List of Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
List of Lemmas, Propositions etc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273