The Utility Problem in Case-Based Reasoning
Anthony G. Francis Jr., Ashwin Ram · 1993
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]. Massive parallelism is often offered as a potential solution to the performance utility problem, reducing match cost to nearly constant time. Retrieval of memory items requires both parallel matching of cases and indices and selecting the best case. Unfortunately, the cost of matching can grow arbitrarily large as the size of individual cases increases; furthermore, selection algorithms that provide constant-time performance fail to scale up m large case bases. Theoretical considerations of parallel architectures enforce a lower bound of f~(lg n)