Minimizing the Average Query Complexity of Learning Monotone Boolean Functions

References

• Ben-David A. Automatic generation of symbolic multiattribute ordinal knowledge-based DSSs: methodology and applications. Decision Sciences (1992) 23:1357–1372Crossref, Google Scholar
• Bioch J. C., Ibaraki T. Complexity of identification and dualization of positive Boolean functions. Information and Computation (1995) 123:50–63Crossref, Google Scholar
• Bloch D. A., Silverman B. W. Monotone discriminant functions and their applications in rheumatology. Journal of the American Statistical Association (1997) 92:144–153Crossref, Google Scholar
• Boros E., Hammer P. L., Hooker J. N. Predicting cause-effect relationships from incomplete discrete observations. SIAM Journal on Discrete Mathematics (1994) 7:531–543Crossref, Google Scholar
• Boros E., Hammer P. L., Ibaraki T., Makino K. Polynomialtime recognition of 2-monotonic positive Boolean functions given by an oracle. SIAM Journal on Computing (1997) 26:93–109Crossref, Google Scholar
• Church R. Numerical analysis of certain free distributive structures. Duke Mathematical Journal (1940) 6:732–734Crossref, Google Scholar
• Church R. Enumeration by rankof the free distributive lattice with 7 generators. Notices of the American Mathematical Society (1965) 11:724Google Scholar
• Dedekind R. über zerlegungen von zahlen durch ihre grössten gemeinsamen teiler. Festschrift Hoch. Brauhnschweig u. ges Werke II (1897) 103–148in GermanGoogle Scholar
• Eiter T., Gottlob G. Identifying the minimal transversals of a hypergraph and related problems. SIAM Journal on Computing (1995) 24:1278–1304Crossref, Google Scholar
• Engel K.Encyclopedia of Mathematics and its Applications 65: Sperner Theory (1997) (Cambridge University Press, Cambridge, MA) Google Scholar
• Fellegi I. P., Sunter A. B. A theory for record linkage. Journal of the American Statistical Association (1969) 64:1183–1210Crossref, Google Scholar
• Fredman M. L., Khachiyan L. On the complexity of dualization of monotone disjunctive normal forms. Journal of Algorithms (1996) 21:618–628Crossref, Google Scholar
• Gainanov D. N. On one criterion of the optimality of an algorithm for evaluating monotonic Boolean functions. U.S.S.R. Computational Mathematics and Mathematical Physics (1984) 24:176–181Crossref, Google Scholar
• Hansel G. Sur le nombre des foncions Booleenes monotones de n variables. C. R. Acad. Sci. Paris (1966) 262:1088–1090in FrenchGoogle Scholar
• Horvitz D. G., Thompson D. J. A generalization of sampling without replacement from a finite universe. Journal of the American Statistical Association (1952) 47:663–685Crossref, Google Scholar
• Judson D. H.On the Inference of Semi-Coherent Structures from Data (1999) . Master's thesis, Dept. of Mathematics, University of Nevada, Reno, NVGoogle Scholar
• Judson D. H. A partial order approach to record linkage. Federal Committee on Statistical Methodology Conference, Arlington, VA, November (2001) 14–16Google Scholar
• Korshunov A. D. On the number of monotone Boolean functions. Problemy Kibernetiki (1981) 38:5–108in RussianGoogle Scholar
• Kovalerchuk B., Triantaphyllou E., Deshpande A. S. Interactive learning of monotone Boolean functions. Information Sciences (1996) 94:87–118Crossref, Google Scholar
• Kovalerchuk B., Triantaphyllou E., Ruiz J. F., I Torvik V., Vitayev E. The reliability issue of computer-aided breast cancer diagnosis. Computers and Biomedical Research (2000a) 33:296–313Crossref, Google Scholar
• Kovalerchuk B., Vityaev E.Data Mining in Finance (2000b) (Kluwer Academic Publishers, Boston, MA) Google Scholar
• Makino K., Ibaraki T. A fast and simple algorithm for identifying 2-monotonic positive Boolean functions. Proceedings of ISAACS'95, Algorithms and Computation (1995) (Springer-Verlag, Berlin, Germany) 291–300Crossref, Google Scholar
• Makino K., Ibaraki T. The maximum latency and identification of positive Boolean functions. SIAM Journal on Computing (1997) 26:1363–1383Crossref, Google Scholar
• Makino K., Suda T., Ono H., Ibaraki T. Data analysis by positive decision trees. IEICE Transactions on Information and Systems (1999) E82-D:76–88Google Scholar
• Shmulevich I.Properties and Applications of Monotone Boolean Functions and Stack Filters (1997) . Ph.D. dissertation, Dept. of Electrical Engineering, Purdue University, West Lafayette, INGoogle Scholar
• Sokolov N. A. On the optimal evaluation of monotonic Boolean functions. U.S.S.R. Computational Mathematics and Mathematical Physics (1982) 22:207–220Crossref, Google Scholar
• Thompson S. K.Sampling (1992) (John Wiley & Sons, New York) Google Scholar
• Torvik V. I., Triantaphyllou E. Guided inference of stochastic monotone Boolean functions. (2001a) . Working paper, Dept. of Psychiatry, University of Illinois at ChicagoGoogle Scholar
• Torvik V. I., Triantaphyllou E. Guided inference of nested monotone Boolean functions. (2001b) . Working paper, Dept. of Psychiatry, University of Illinois at ChicagoGoogle Scholar
• Torvik V. I.Data Mining and Knowledge Discovery: A Guided Approach Based on Monotone Boolean Functions (2002) . Ph.D. dissertation, Dept. of Industrial Engineering, Louisiana State University, Baton Rouge, LAGoogle Scholar
• Valiant L. G. A theory of the learnable. Communications of the ACM (1984) 27:1134–1142Crossref, Google Scholar
• Ward M. Note on the order of the free distributive lattice. Bulletin of the American Mathematical Society (1946) 52:423Crossref, Google Scholar
• Wiedemann D. A computation of the eight dedekind number. Order (1991) 8:5–6Crossref, Google Scholar
• Winkler W., Cox B. G., Binder D. A., Chinnappa B. N. Matching and record linkage. Business Survey Methods (1995) (John Wiley & Sons, New York) Crossref, Google Scholar