TU Darmstadt / ULB / TUprints

Heuristic Rule Learning

Janssen, Frederik (2012)
Heuristic Rule Learning.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
PDF
dissertation.pdf
Copyright Information: CC BY-NC-ND 2.5 Generic - Creative Commons, Attribution, NonCommercial, NoDerivs .

Download (2MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Heuristic Rule Learning
Language: English
Referees: Fürnkranz, Prof. Dr. Johannes ; Lavesson, PhD, Prof. Niklas
Date: 17 October 2012
Place of Publication: Darmstadt
Date of oral examination: 10 October 2012
Abstract:

The primary goal of the research reported in this thesis is to identify what criteria are responsible for the good performance of a heuristic rule evaluation function in a greedy top-down covering algorithm both in classification and regression. We first argue that search heuristics for inductive rule learning algorithms typically trade off consistency and coverage, and we investigate this trade-off by determining optimal parameter settings for five different parametrized heuristics for classification. In order to avoid biasing our study by known functional families, we also investigate the potential of using metalearning for obtaining alternative rule learning heuristics. The key results of this experimental study are not only practical default values for commonly used heuristics and a broad comparative evaluation of known and novel rule learning heuristics, but we also gain theoretical insights into factors that are responsible for a good performance. Additionally, we evaluate the spectrum of different search strategies to see whether separate-and-conquer rule learning algorithms are able to gain performance in terms of predictive accuracy or theory size by using more powerful search strategies like beam search or exhaustive search. Unlike previous results that demonstrated that rule learning algorithms suffer from oversearching, our work pays particular attention to the interaction between the search heuristic and the search strategy. Our results show that exhaustive search has primarily the effect of finding longer, but nevertheless more general rules than hill-climbing search.

A second objective is the design of a regression rule learning algorithm. To do so, a novel parametrized regression heuristic is introduced and its parameter is tuned in the same way as before. A new splitpoint generation method is introduced for the efficient handling of numerical attributes. We show that this metric-based algorithm performs comparable to several other regression algorithms. Furthermore, we propose a novel approach for learning regression rules by transforming the regression problem into a classification problem. The key idea is to dynamically define a region around the target value predicted by the rule, and considering all examples within that region as positive and all examples outside that region as negative. In this way, conventional rule learning heuristics may be used for inducing regression rules. Our results show that our heuristic algorithm outperforms approaches that use a static discretization of the target variable, and performs en par with other comparable rule-based approaches, albeit without reaching the performance of statistical approaches.

In the end, two case studies on real world problems are presented. The first one deals with the problem of predicting skin cancer and the second one is about deciding whether or not students have to be invited to a counseling session. For reasons of interpretability, rules were perfectly suited to work with in both case studies. The results show that the derived rule-based algorithms are able to find rules that are very diverse, proved to be interesting and are also sufficiently accurate. All experiments were performed in the SECO-framework, a new versatile framework for heuristic rule learning, which allows for an easy configuration of a wide range of different components rule learners consist of.

Alternative Abstract:
Alternative AbstractLanguage

Das hauptsächliche Forschungsziel dieser Dissertation ist, Kriterien zu identifizieren, die für eine gute Performanz von heuristischen Evaluationsfunktionen in einem Greedy Top-Down Covering Algorithmus verantwortlich sind. Dies wurde sowohl für Klassifikation als auch für Regression untersucht. Zu Beginn wird argumentiert, dass Suchheuristiken für induktive Regel-Lern-Algorithmen typischerweise zwischen Konsistenz und Abdeckung abwägen. Es werden Parameter für fünf verschiedene Heuristiken für Klassifikation zur optimalen Abwägung dieser beiden Ziele bestimmt. Diese Parameterwerte sind von praktischer Relevanz da sie als Standardwerte für Regel-Lern-Algorithmen verwendet werden können. Um aber eine Beeinflussung durch bereits bekannte Funktionsfamilien auszuschließen, wird das Potential von Meta-Lernverfahren untersucht, um alternative Regel-Lern-Heuristiken zu erhalten. Hervorzuheben ist, dass theoretische Einblicke in Faktoren, die für eine gute Performanz verantwortlich sind, in beiden Studien gewonnen wurden. Des Weiteren wurde das Spektrum verschiedener Suchstrategien analysiert, um festzustellen ob Separate-and-Conquer Algorithmen von mächtigeren Suchstrategien wie z.B. einer Beam-Suche oder einer vollständigen Suche im Hinblick auf Genauigkeit oder Theoriegröße profitieren können. Im Gegensatz zu bisherigen Resultaten aus der Literatur, in welchen festgestellt wurde, dass Regel- Lern-Algorithmen am sog. "Oversearching" leiden, wird in dieser Arbeit besonderes Augenmerk auf das Zusammenspiel zwischen der Suchheuristik sowie der Suchstrategie gelegt. Die Ergebnisse verdeutlichen, dass eine vollständige Suche den vorrangigen Effekt hat längere, aber trotzdem generellere Regeln als eine Hill-Climbing Suche zu finden.

Ein zweites Ziel dieser Dissertation ist die Erstellung eines Regel-Lern-Algorithmus für Regression. Um dieses Ziel zu erreichen wird eine parametrisierbare Regressionsheuristik entworfen und der Parameter wird in der gleichen Weise wie zuvor angepasst. Eine effiziente Methode um Splitpoints zu generieren wird ebenfalls eingeführt, da man auf aus der Klassifikation bekannte Verfahren nicht zurückgreifen kann. Es wird gezeigt, dass dieser Metrik-basierte Algorithmus vergleichbar gut wie andere Regressionsalgorithmen funktioniert, obwohl er ein deutlich simpleres Modell für die Regeln verwendet. Im Weiteren wird eine neuartige Methode präsentiert mit welcher Regressionsregeln gelernt werden können indem Regression in ein Klassifikationsproblem transformiert wird. Die Kernidee ist, dynamisch eine Region um den Vorhersagewert der Regel zu definieren, innerhalb dieser alle Beispiele als positiv zu betrachten sind und alle die außerhalb liegen als negativ. So können konventionelle Regel-Lern-Heuristiken verwendet werden, um Regressionsregeln zu lernen. Die Experimente zeigen, dass der entwickelte heuristische Algorithmus signifikant bessere Ergebnisse als eine statische Diskretisierung liefert. Zudem ist das Verfahren ähnlich gut wie andere regelbasierte Ansätze wenn auch nicht so gut wie statistische Verfahren.

Zuletzt werden zwei Fallstudien präsentiert, die auf realen Daten durchgeführt werden. Das Ziel der ersten Studie ist das Hautkrebsrisiko eines Patienten vorherzusagen. In der zweiten Studie geht es um die Entscheidung, ob Studierende entsprechend verschiedener persönlicher Daten zu einem Beratungsgespräch eingeladen werden müssen. Aus Gründen der guten Interpretierbarkeit sind Regeln optimal geeignet um diese beiden Probleme zu lösen. Die Resultate zeigen, dass die in dieser Dissertation eingeführten Regel-Lern-Algorithmen geeignet sind, Regeln zu finden die sehr unterschiedlich, die für Domänenexperten interessant und die trotzdem noch ausreichend genau sind. Alle Experimente wurden im sog. SECO-framework durchgeführt, einem neuartigen vielseitigen Framework für heuristisches Regel-Lernen welches eine bequeme Konfiguration verschiedenster Komponenten eines Regel-Lern-Algorithmus erlaubt.

German
Uncontrolled Keywords: heuristics, regression, meta-learning, parameter tuning, coverage space, search algorithms, oversearching, reduction
Alternative keywords:
Alternative keywordsLanguage
Heuristiken, Regression, Meta-Lernen, Parameteroptimierung, Coverage Space, Suchalgorithmen, Oversearching, ReduktionGerman
URN: urn:nbn:de:tuda-tuprints-31352
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Knowl­edge En­gi­neer­ing
Date Deposited: 26 Nov 2012 13:13
Last Modified: 09 Jul 2020 00:13
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/3135
PPN: 313416338
Export:
Actions (login required)
View Item View Item