Combining model-based and instance-based learning for first order regression

ABSTRACT

The introduction of relational reinforcement learning and the RRL algorithm gave rise to the development of several first order regression algorithms. So far, these algorithms have employed either a model-based approach or an instance-based approach. As a consequence, they suffer from the typical drawbacks of model-based learning such as coarse function approximation or those of lazy learning such as high computational intensity.In this paper we develop a new regression algorithm that combines the strong points of both approaches and tries to avoid the normally inherent draw-backs. By combining model-based and instance-based learning, we produce an incremental first order regression algorithm that is both computationally efficient and produces better predictions earlier in the learning experiment.

REFERENCES

• 1: David W. Aha , Dennis Kibler , Marc K. Albert, Instance-Based Learning Algorithms, Machine Learning, v.6 n.1, p.37-66, Jan. 1991 [doi>10.1023/A:1022689900470]
• 2: Christopher G. Atkeson , Andrew W. Moore , Stefan Schaal, Locally Weighted Learning, Artificial Intelligence Review, v.11 n.1-5, p.11-73, Feb. 1997 [doi>10.1023/A:1006559212014]
• 3: Hendrik Blockeel , Luc De Raedt, Top-down induction of first-order logical decision trees, Artificial Intelligence, v.101 n.1-2, p.285-297, May 1998 [doi>10.1016/S0004-3702(98)00034-4]
• 4: Pedro Domingos, Unifying instance-based and rule-based induction, Machine Learning, v.24 n.2, p.141-168, Aug. 1996 [doi>10.1023/A:1018006431188]
• 5: Kurt Driessens , Sašo Džeroski, Integrating Guidance into Relational Reinforcement Learning, Machine Learning, v.57 n.3, p.271-304, December 2004 [doi>10.1023/B:MACH.0000039779.47329.3a]
• 6: Driessens, K., & Ramon, J. (2003). Relational instance based regression for relational reinforcement learning. Proceedings of the Twentieth International Conference on Machine Learning (pp. 123--130). AAAI Press.
• 7: Kurt Driessens , Jan Ramon , Hendrik Blockeel, Speeding Up Relational Reinforcement Learning through the Use of an Incremental First Order Decision Tree Learner, Proceedings of the 12th European Conference on Machine Learning, p.97-108, September 05-07, 2001
• 8: Sošo Džeroski , Luc De Raedt , Kurt Driessens, Relational reinforcement learning, Machine Learning, v.43 n.1/2, p.7-52, April/May 2001 [doi>10.1023/A:1007694015589]
• 9: Saso Dzeroski , Luc De Raedt , Hendrik Blockeel, Relational Reinforcement Learning, Proceedings of the Fifteenth International Conference on Machine Learning, p.136-143, July 24-27, 1998
• 10: Jerome H. Freidman , Jon Louis Bentley , Raphael Ari Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.209-226, Sept. 1977 [doi>10.1145/355744.355745]
• 11: Gärtner, T., Driessens, K., & Ramon, J. (2003). Graph kernels and Gaussian processes for relational reinforcement learning. Inductive Logic Programming, 13th International Conference, ILP 2003, Proceedings (pp. 146--163). Springer.
• 12: Moore, A. (1991). An introductory tutorial on kd-trees (Technical Report). Robotics Institute, Carnegie Mellon University.
• 13: Quinlan, J. (1993). Combining instance-based and model-based learning. Proceedings of the 10th International Conference on Machine Learning. Morgan Kaufmann.
• 14: Jan Ramon , Maurice Bruynooghe, A polynomial time computable metric between point sets, Acta Informatica, v.37 n.10, p.765-780, July 2001 [doi>10.1007/PL00013304]
• 15: Steven Salzberg, A Nearest Hyperrectangle Learning Method, Machine Learning, v.6 n.3, p.251-276, May 1991 [doi>10.1023/A:1022661727670]
• 16: Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]