home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / bit / listserv / csgl / 2237 < prev    next >
Encoding:
Text File  |  1993-01-21  |  4.8 KB  |  151 lines
  1. Comments: Gated by NETNEWS@AUVM.AMERICAN.EDU
  2. Path: sparky!uunet!paladin.american.edu!auvm!CCB.BBN.COM!BNEVIN
  3. Return-Path: <@VMD.CSO.UIUC.EDU:bnevin@ccb.bbn.com>
  4. Message-ID: <CSG-L%93012107351583@VMD.CSO.UIUC.EDU>
  5. Newsgroups: bit.listserv.csg-l
  6. Date:         Thu, 21 Jan 1993 08:26:22 EST
  7. Sender:       "Control Systems Group Network (CSGnet)" <CSG-L@UIUCVMD.BITNET>
  8. From:         "Bruce E. Nevin" <bnevin@CCB.BBN.COM>
  9. Subject:      MDL refs from Boulanger
  10. Lines: 139
  11.  
  12. [From: Bruce Nevin (Thu 930121 08:24:53)]
  13.  
  14. Here is a bibliographical followup by Albert Boulanger, FYI.
  15.  
  16.         Bruce
  17.         bn@bbn.com
  18.  
  19. -=+=-=+=-=+=-=+=-=+=-=+=-=+=-=+=-=+=-=+=-=+=-=+=-=+=-=+=-=+=-=+=-=+=-=+=-
  20. Date: Wed, 20 Jan 93 16:54:02 -0800
  21. From: Michael Pazzani <pazzani@ics.uci.edu>
  22.  
  23.                  Machine Learning List: Vol. 5 No. 1
  24. [ . . . ]
  25. ----------------------------------------------------------------------
  26.  
  27. To: ml@ics.uci.edu
  28. Subject: MDL references
  29. From: aboulang@bbn.COM
  30. Date: Sat, 9 Jan 93 19:49:29 EST
  31.  
  32.  
  33. Several folk, in response to my posting, asked for some references on
  34. MDL-like methods. Some references are incomplete so perhaps you can
  35. help *me* complete them,
  36.  
  37.  
  38. First off, probably one can say the spirit of MDL (stochastic
  39. complexity) methods was in the early work of algorithmic complexity
  40. theory -- especially the work on a general methodology for inductive
  41. inference by Solomonoff. The big problem with algorithmic complexity
  42. is that it is not computable.
  43.  
  44. ****************
  45.  
  46. Akiake's early work on an MDL-like metric for model selection is
  47. notable in that work has been done with it to formally relate it to
  48. cross-validation, asymptotically:
  49.  
  50. "An Asymptotic Equivalence of Choice of Model by Cross-Validation and
  51. Akaike's Criterion". M, Stone, ????, 44-47
  52.  
  53.  
  54.  Akiake did not take into account sample size into his metric.
  55.  
  56. ****************
  57. There is a pair of back-to-back papers in the Journal of the Royal
  58. Statistics Society B(1987), by Jorma Rissanen  and then C.S. Wallace &
  59. P.R. Freeman on their contributions to MDL-like metrics:
  60.  
  61.  
  62. "Stochastic Complexity", Jorma Rissanen, J. R. Statist. Soc B(1987)
  63. 49, No 3, pp 223-239, and 252-265.
  64.  
  65. "Estimation and Inference by Compact Coding", J. R. Statist.  Soc B(1987)
  66. 49, No 3, pp 240-265.
  67.  
  68. These two papers are of interest along with the discussion section on
  69. pages 252-265. The crux of the issue (besides the silly "who published
  70. first") is Rissanen use of a "universal" prior. Wallace does not,
  71. being a die-hard prior believer. (Personally I feel that often the
  72. choice of prior can lead to radically different answers, and any
  73. attempt at making a more "robust" method should be welcomed. This
  74. observation comes from some work I did on a health-risk assessment
  75. program. I realized that misinformation in the system can really screw
  76. things up in using a normal Bayesian framework -- we should seek a
  77. more robust approach.)
  78.  
  79. Two other references to Rissanen are:
  80.  
  81. J. Rissanen, "Universal Coding, Information, Prediction &
  82. Estimation,", IEEE Trans. Inform. Theory, vol 30, pp 629-636, 1984
  83.  
  84.   & his book:
  85.  
  86. J. Rissanen, "Stochastic Complexity in Statistical Inquiry", World
  87. Scientific, N.J., 1989
  88.  
  89.  
  90. ****************
  91.  
  92. An application of MDL to *unsupervised* clustering is:
  93.  
  94. "Finding Natural Clusters Having Minimum Description Length"
  95. Richard S. Wallace & Takeo Kanade, IEEE ???, 438-442, 1990
  96.  
  97. ****************
  98. MDL is the basis for pruning methods for tree classifiers (*supervised*):
  99.  
  100. J. R. Quinlan and R. Riverst, "Inferring Decision Trees Using the
  101. Minimum Description Length Principle," Information and Computation,
  102. 80, 227-248.
  103.  
  104. ****************
  105.  
  106. As I mentioned in the short note, one can push the use of MDL earlier
  107. into the generation phase of machine learning programs. In this paper,
  108. it used for both growing and pruning the decision tree:
  109.  
  110. "Construction of Tree Structured Classifiers by the MDL Principle",
  111. Mati Wax, ICASSP (??) Proceedings, M7.10, 2157-2160, 1990.
  112.  
  113. ****************
  114.  
  115. Padhraic Smyth has applied it for model selection of Markov random
  116. fields, decision tree classifiers, and multilevel feedforward NNets,
  117.  
  118. "Admissible Stochastic Complexity Models for Classification
  119. Problems", ??? 26.1-26.8
  120.  
  121. See also:
  122.  
  123. "A General Selection Criterion for Inductive Inference"
  124. M.P. Geirgeff & C.S. Wallace, Advances in Artificial Intelligence,
  125. T. O'Shea (ed.), Elsevier. ECCAI, 1985.
  126.  
  127. ****************
  128.  
  129. Finally, a really neat thesis of George Hart:
  130.  
  131. "Minimum Information Estimation of Structure"
  132. MIT Lab. of Information and Decision Science, LIDS-TH-1664, April 1987.
  133.  
  134. His main development is the inference of FSMs from strings. The main
  135. application, is a really neat inverse problem -- infer the different
  136. electrical loads of a house only from a recording off a load meter
  137. external to the house.
  138.  
  139. Wallace also applied it to figuring out patterns in Stone Circles.
  140.  
  141.  
  142. ***************
  143.  
  144. Again, I am sorry for the incomplete references.
  145.  
  146. Regards,
  147. Albert Boulanger
  148. aboulanger@bbn.com
  149.  
  150. [ . . . ]
  151.