|
|
|
A computational algebraic-geometry method for conditional-independence inference |
Benchong LI, Shoufeng CAI, Jianhua GUO( ) |
| Key Laboratory for Applied Statistics of MOE and School of Mathematics and Statistics, Northeast Normal University, Changchun 130024, China |
|
|
|
|
Abstract We consider the problems of semi-graphoid inference and of independence implication from a set of conditional-independence statements. Based on ideas from R. Hemmecke et al. [Combin. Probab. Comput., 2008, 17: 239-257], we present algebraic-geometry characterizations of these two problems, and propose two corresponding algorithms. These algorithms can be realized with any computer algebra system when the number of variables is small.
|
| Keywords
Conditional independence
independence implication
radical membership
semi-graphoid inference
structural imset
|
|
Corresponding Author(s):
GUO Jianhua,Email:jhguo@nenu.edu.cn
|
|
Issue Date: 01 June 2013
|
|
| 1 |
4ti2 team: 4ti2—A software package for algebraic, geometric and combinatorial problems on linear spaces. www.4ti2.de.
|
| 2 |
Baioletti M, Busanello G, Vantaggi B. Conditional independence structure and its closure: Inference rules and algorithms. Int J Approx Reason , 2009, 50: 1097-1114
doi: 10.1016/j.ijar.2009.05.002
|
| 3 |
Bouckaert R R, Hemmecke R, Lindner S, Studeny M. Efficient algorithms for conditional independence inference. J Mach Learn Res , 2010, 11: 3453-3479
|
| 4 |
Bouckaert R R, Studeny M. Racing algorithms for conditional independence inference. Int J Approx Reason , 2007, 45: 386-401
doi: 10.1016/j.ijar.2006.06.018
|
| 5 |
Bruns W, Hemmecke R, Ichim B, K?ppe M, S?ger C. Challenging computations of Hilbert bases of cones associated with algebraic statistics. Experiment Math , 2011, 20: 25-33
doi: 10.1080/10586458.2011.544574
|
| 6 |
Chickering D M. Optimal structure identification with greedy search. J Mach Learn Res , 2002, 3: 507-554
|
| 7 |
Cowell R G, Dawid A P, Lauritzen S L, Spiegelhalter D G. Probabilistic Network and Expert System. New York: Springer-Verlag, 1999
|
| 8 |
Cox D, Little J, O’ Shea D. Ideals, Varieties, and Algorithms. 3rd ed. Undergrad Texts Math . New York: Springer, 2007
|
| 9 |
Cox D R, Wermuth N. Multivariate Dependencies: Models Analysis and Interpretation. London: Chapman & Hall, 1993
|
| 10 |
Dawid A P. Conditional independence in statistical theory. J Roy Statist Soc Ser B , 1979, 41: 1-31
|
| 11 |
Dawid A P. Separoids: a mathematical framework for conditional independence and irrelevance. Ann Math Artif Intell , 2001, 32: 335-372
doi: 10.1023/A:1016734104787
|
| 12 |
Decker W, Greuel G M, Pfister G, Sch?nemann H. Singular 3-1-1—A computer algebra system for polynomial computations. http://www.singular.uni-kl.de, 2011
|
| 13 |
Drton M, Sturmdels B, Sullivant S. Lectures on Algebraic Statistics. Oberwolfach Seminars , Vol 39. Berlin: Springer, 2009
doi: 10.1007/978-3-7643-8905-5
|
| 14 |
Edwards D. Introduction to Graphical Modelling. 2nd ed. Berlin: Springer-Verlag, 2000
doi: 10.1007/978-1-4612-0493-0
|
| 15 |
Hemmecke R, Morton J, Shiu A, Sturmfels B, Wienand O. Three counterexamples on semigraphoids. Combin Probab Comput , 2008, 17: 239-257
|
| 16 |
Lauritzen S L. Graphical Models. Oxford: Clarendon Press, 1996
|
| 17 |
Matú? F. Conditional independences among four random variables III: Final conclusion. Combin Probab Comput , 1999, 8: 269-276
doi: 10.1017/S0963548399003740
|
| 18 |
Matú? F. Lengths of semigraphoid inferences. Ann Math Artif Intell , 2002, 35: 287-294
doi: 10.1023/A:1014525817725
|
| 19 |
Matú? F. Towards classification of semi-graphoids. Discrete Math , 2004, 277: 115-145
doi: 10.1016/S0012-365X(03)00155-9
|
| 20 |
Matú? F. Conditional independences in Gaussian vectors and rings of polynomials. In: Kern-Isberner G, Rodder W, Kulmann F, eds. Proceedings of WCII 2002, Lect Notes Artif Intell, 3301 . Berlin, Heidelberg: Springer-Verlag, 2005, 152-161
|
| 21 |
Neapolitan R E. Learning Bayesian Networks. Upper Saddle River: Pearson Prentice Hall, 2004
|
| 22 |
Niepert M. Logical inference algorithms and matrix representations for probabilistic conditional independence. In: Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence , 2009. 2009, 428-435
|
| 23 |
Niepert M, Gucht D V, Gyssens M. On the conditional independence implication problem: a lattice-theoretic approach. In: Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence , 2008. 2008, 435-443
|
| 24 |
Pearl J. Probabilistic Reasoning in Intelligent Systems. Burlington: Morgan Kaufmann, 1988
|
| 25 |
Shenoy P P. Conditional independence in valuation-based systems. Int J Approx Reason , 1994, 10: 203-234
doi: 10.1016/0888-613X(94)90001-9
|
| 26 |
Studeny M. Conditional independence relations have no finite complete characterization. In: Kubik S, Visek J A, eds. Information Theory, Statistical Decision Functions and Random Processes , Vol B. Dordrecht: Kluwer, 1992, 377-396
|
| 27 |
Studeny M. Semigraphoids and structures of probabilistic conditional independence. Ann Math Artif Intell , 1997, 21: 71-98
doi: 10.1023/A:1018905100242
|
| 28 |
Studeny M. Complexity of structural models. In: Proceedings of the Prague Stochastics ’ 98, Prague . 1998, 521-528
|
| 29 |
Studeny M. Probabilistic Conditional Independence Structures. Berlin: Springer- Verlag, 2005
|
| 30 |
Studeny M, Bouckaert R R, Kocka T. Extreme Supermodular Set Functions Over Five Variables. Prague: Institute of Information Theory and Automation, 2000
|
| 31 |
Verma T, Pearl J. Causal networks, semantics and expressiveness. In: Shachter R D, Lewitt T S, Kanal L N, Lemmer J F, eds. Uncertainty in Artificial Intelligence, 4 . Amsterdam: North-Holland, 1990, 69-76
|
| 32 |
Whittaker J. Graphical Models in Applied Multivariate Statistics. New York: Wiley, 1990
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
