Construction and learnability of canonical Horn formulas. (English) Zbl 1237.68106
Summary: We describe an alternative construction of an existing canonical representation for definite Horn theories, the Guigues-Duquenne basis (or GD basis), which minimizes a natural notion of implicational size. We extend the canonical representation to general Horn, by providing a reduction from definite to general Horn CNF. Using these tools, we provide a new, simpler validation of the classic Horn query learning algorithm of Angluin, Frazier, and Pitt, and we prove that this algorithm always outputs the GD basis regardless of the counterexamples it receives.
References:
| [1] | Angluin, D. (1987). Learning regular sets from queries and counterexamples. Information and Computation, 75(2), 87-106. · Zbl 0636.68112 · doi:10.1016/0890-5401(87)90052-6 |
| [2] | Angluin, D., & Kharitonov, M. (1995). When won’t membership queries help? Journal of Computer and System Sciences, 50(2), 336-355. · Zbl 0827.68039 · doi:10.1006/jcss.1995.1026 |
| [3] | Angluin, D., Frazier, M., & Pitt, L. (1992). Learning conjunctions of Horn clauses. Machine Learning, 9, 147-164. · Zbl 0766.68107 |
| [4] | Arias, M.; Balcázar, J. L., Query learning and certificates in lattices, No. 5254, 303-315 (2008) · Zbl 1156.68410 |
| [5] | Arias, M.; Balcázar, J. L., Canonical Horn representations and query learning, No. 5809, 156-170 (2009) · Zbl 1262.68059 |
| [6] | Arias, M., & Khardon, R. (2002). Learning closed Horn expressions. Information and Computation, 178(1), 214-240. · Zbl 1012.68151 |
| [7] | Arias, M., Feigelson, A., Khardon, R., & Servedio, R. A. (2006). Polynomial certificates for propositional classes. Information and Computation, 204(5), 816-834. · Zbl 1110.68053 · doi:10.1016/j.ic.2006.03.001 |
| [8] | Arias, M., Khardon, R., & Maloberti, J. (2007). Learning Horn expressions with LogAn-H. Journal of Machine Learning Research, 8, 587. · Zbl 1222.68135 |
| [9] | Balcázar, J. L., Query learning of Horn formulas revisited (2005) |
| [10] | Bertet, K., & Monjardet, B. (2010). The multiple facets of the canonical direct unit implicational basis. Theoretical Computer Science, 411(22-24), 2155-2166. · Zbl 1209.68187 · doi:10.1016/j.tcs.2009.12.021 |
| [11] | Chang, C. L., & Lee, R. (1973). Symbolic logic and mechanical theorem proving. Orlando: Academic Press. · Zbl 0263.68046 |
| [12] | Frazier, M.; Pitt, L., Learning from entailment: an application to propositional Horn sentences, Amherst, MA, San Mateo |
| [13] | Frazier, M., & Pitt, L. (1996). CLASSIC learning. Machine Learning, 25, 151-193. · Zbl 0869.68090 · doi:10.1023/A:1026443024002 |
| [14] | Gaintzarain, J.; Hermo, M.; Navarro, M., On learning conjunctions of Horn⊃ clauses (2005) · Zbl 1156.68326 |
| [15] | Guigues, J. L., & Duquenne, V. (1986). Familles minimales d’implications informatives resultants d’un tableau de données binaires. Mathématiques Et Sciences Humaines, 95, 5-18. · Zbl 1504.68217 |
| [16] | Hellerstein, L., Pillaipakkamnatt, K., Raghavan, V., & Wilkins, D. (1996). How many queries are needed to learn? Journal of the ACM, 43(5), 840-862. · Zbl 0885.68123 · doi:10.1145/234752.234755 |
| [17] | Hermo, M.; Lavín, V., Negative results on learning dependencies with queries (2002) · Zbl 1260.68191 |
| [18] | Horn, A. (1956). On sentences which are true of direct unions of algebras. The Journal of Symbolic Logic, 16, 14-21. · Zbl 0043.24801 · doi:10.2307/2268661 |
| [19] | Khardon, R., & Roth, D. (1996). Reasoning with models. Artificial Intelligence, 87(1-2), 187-213. · Zbl 1506.68149 · doi:10.1016/S0004-3702(96)00006-9 |
| [20] | Kivinen, J., & Mannila, H. (1995). Approximate inference of functional dependencies from relations. Theoretical Computer Science, 149(1), 129-149. · Zbl 0874.68247 · doi:10.1016/0304-3975(95)00028-U |
| [21] | Kleine Büning, H., & Lettmann, T. (1999). Propositional logic: deduction and algorithms. Cambridge: Cambridge University Press. · Zbl 0957.03001 |
| [22] | Maier, D. (1980). Minimum covers in relational database model. Journal of the ACM, 27, 664-674. · Zbl 0466.68085 · doi:10.1145/322217.322223 |
| [23] | McKinsey, J. C. C. (1943). The decision problem for some classes of sentences without quantifiers. The Journal of Symbolic Logic, 8, 61-76. · Zbl 0063.03864 · doi:10.2307/2268172 |
| [24] | Rouveirol, C. (1994). Flattening and saturation: two representation changes for generalization. Machine Learning, 14(1), 219-232. · Zbl 0804.68024 · doi:10.1023/A:1022678217288 |
| [25] | Selman, B., & Kautz, H. (1996). Knowledge compilation and theory approximation. Journal of the ACM, 43(2), 193-224. · Zbl 0882.68137 · doi:10.1145/226643.226644 |
| [26] | Valiant, L. G. (1984). A theory of the learnable. Communications of the ACM, 27(11), 1134-1142. · Zbl 0587.68077 · doi:10.1145/1968.1972 |
| [27] | Wang, H. (1960). Toward mechanical mathematics. IBM Journal for Research and Development, 4, 2-22. · Zbl 0097.00404 · doi:10.1147/rd.41.0002 |
| [28] | Wild, M. (1994). A theory of finite closure spaces based on implications. Advances in Mathematics, 108, 118-139. · Zbl 0863.54002 · doi:10.1006/aima.1994.1069 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
