Computational learning theory: Difference between revisions

Revision as of 23:10, 30 April 2005

Revision as of 11:31, 21 June 2005

Line 4:

In addition to performance bounds, computational learning theorists study the time complexity and feasibility of learning. In computational learning theory, a computation is considered feasible if it can be done in polynomial time. There are two kinds of time complexity results:

#Positive results --- Showing thethat a certain class of functionfunctions is learnable in polynomial time.

#Negative results - Showing that certain classes cannot be learned in polynomial time.

Negative results are proven only by assumption. The assumptions the are common in negative results are: