Anthony G. Francis, Jr. and Ashwin Ram
Case-based reasoning systems may suffer from the utility problem, which occurs when knowledge learned in an attempt to improve a system’s performaw.e degrades performance instead. There are two main classes of utility problems: performance utility problems and search-space utility problems. Search-space utility pmblealm, such as the branching problem in some macm-(~mtor systems [ETZIONI 1992] are a symptom of poorly designed learning algorithms. Performarr~ utility probk~ns, in contrast, are a direct consequence of increased cost of memory accessing and matching as the size of the knowledge base or of learned items increase. Leaming algorithms that do not take this ove~ad into account can cause a system to slow down more than the average speedup provided by individual learned rules. For example, the cost of matching individual items in the Soar system caused the expensive chunks problem [TAMBE Err AL 1990], and the cost of matching a whole rulebase in Profflgy caused the swamping problem [MINTON 1988].