Concept formation from structural examples

Our work on the Heracles algorithm addresses three problems of Inductive Logic Programming:

• The NP-completeness of theta-subsumption results in an extremely high computational effort for logic deduction, i.e. it is hard to decide whether a hypothesis explains a given observation. An extension of the deterministical theta-subsumption that is inspired from graph theory makes theta-subsumption possible in polynomial time for a larger class of clauses.

• The lgg of clauses is growing exponentially with the number of clauses generalized. A principle of generalization also inspired from graph theory has a constant description length and yet is not necessarily more general than the lgg.

• Logic based on the syntactical principle of subsumption is not well suited to handle real valued attributes. I am developing a system that learns constraints by generalization and uses a neural algorithm to adjust the constraints.

References

• Tobias Scheffer, Ralf Herbrich, and Fritz Wysotzki. Efficient theta-subsumption based on graph algorithms. . In Proceedings International Workshop on Inductive Logic Programming, pages 312-329, 1996. (PostScript)  .