From: bharat@cs.uiuc.edu (R. Bharat Rao)
Subject: Re: Inductive Learning and Relational Databases
Reply-To: bharat@cs.uiuc.edu
Organization: University of Illinois, Dept. of Comp. Sci., Urbana, IL
Date: Wed, 30 Sep 1992 14:45:27 GMT

John.Roddick@levels.unisa.edu.au writes:

>              INDUCTIVE LEARNING ALGORITHMS AND RELATIONAL DATA

>I'm currently looking at some aspects of incorporating Inductive Learning into
>Relational Database Systems and I'm after any references on previous work in
>the area.  I already have a number of references but will post a (more)
>complete list given sufficient demand.

The latest AI Magazine (Vol 13, No. 3, Fall 1992), hot off the presses
(just arrived yesterday) has an article on "Knowledge DIscovery in
Databses: An Overview" by Frawley, Piatesky-Shapiro, and Matheus.  An
excellent book by the same authors ("Knowledge DIscovery in Databases"
covers the topic in greater detail.  Also, check out the papers on
Data Mining in the VLDB conference at Toronto...

>In order to set the scene, here are some of the parameters I consider
>necessary to place on any inductive learning algorithm using relaional
>database data.

>i.    There is no negative training data available.  Machine learning

>ii.   The algorithms used must run without operator interaction.  In

>iii.  The algorithms do not necessarily need to find all solutions.  The

>iv.   Allied to points ii. and iii. above is the need for the algorithm to
>      report their inductive findings as they find them rather than waiting
>      until the algorithm runs to completion.  Often, especially with large
>      database systems, running to completion may be impractical.

This would be a very good thing to do....

>v.    If possible, temporal support should be accommodated but I have found

>vi.   The database data, at least for my purposes, may be considered
>      accurate.  Many algorithms do not make this assumption and employ
>      probabilistic methods of concept formation.

One reason for probabilistic concepts is that the database may be
inaccurate, but that is NOT the only source of noise.  In real world
problems it is impossible to measure all the relevant variables, and
so you model the learned function as y = f(X) + N(0,s) where N is a
noise function.  In the case of a classification problem this may mean
that if you learn rules 100% accurate rules, you learn unnecessary
complex concepts, essentially overfitting the data.

However, you may have meant that your database is both correct and
complete -- in that event, learning a perfect model that has zero
resubstitution error would be correct.

>vii.  My method of storage and the nature of the relational data itself is
>      such that disjunctive classification rules are required.

>viii. All information is available to the algorithm at all times but there
>      will be more data than can be reasonably held in storage.  Both
>      incremental and non-incremental learners can thus be employed
>      although breadth-first searching through the entire search space, as
>      employed in some non-incremental learners, may be infeasible.

Please post your existing bibliography to the net; I would be very
interested and I so would many others...

>Thanks in advance,

>John.

>John Roddick                               | Phone: (08) 302 3463

Bharat
--
R. Bharat Rao                          E-mail: bharat@cs.uiuc.edu 
AI Group, Beckman Institute for Advanced Science and Technology
405 N. Mathews, Urbana, IL 61801  (217)-244-1263 (O) 337-6498(H)
Electrical & Computer Engineering, University of Illinois, Urbana
Newsgroups: comp.databases.theory