Constructive Probabilistic Learning

Konstruktives Probabilistisches Lernen ist eine Methode zur Datenanalyse, die in dieser Arbeit eingeführt wird. Der Name wird nach dem englischen Constructive Probabilistic Learning mit Cepel abgekürzt. Die Methode basiert auf der Prämisse, dass eine genaue Analyse von Daten nur möglich ist, wenn Expertenwissen einbezogen wird. Dies ist bei den meisten Lernverfahren durch die Festlegung von Kriterien und Parametern möglich, z.B. durch die schwachen Klassifikatoren beim Boosting oder die Topologie eines Neuronalen Netzes. Dabei kann aber immer nur der Teil des Expertenwissens genutzt werden, der in einer Form vorliegt, die mit dem Verfahren kompatibel ist. Für einen Großteil des Wissens trifft dies nicht zu und er kann daher nicht eingebracht werden. Cepel hingegen wurde speziell dafür entwickelt, um verschiedenste Arten von Expertenwissen einzubinden. Dadurch kann bei vielen Analysen eine deutlich höhere Genauigkeit erzielt werden, als durch alternative Lernverfahren. Am Anfang dieser Arbeit steht die Frage, in welcher Form Expertenwissen üblicherweise vorliegt. Es wird gezeigt, dass sich Expertenwissen häufig in Wahrscheinlichkeitsverteilungen einzelner Werte zerlegen lässt. Diese marginalen Wahrscheinlichkeiten können nicht nur von einzelnen Merkmalen berechnet werden, sondern auch durch lineare Projektionen oder beliebige nicht-lineare Abbildungen der Daten. Auf diese Art lässt sich z.B. jedes Abstands- und Ähnlichkeitsmaß oder die Distanz zur Klassifikationsebene als Projektion der Daten beschreiben. Die Grundidee von Cepel ist, die marginalen Wahrscheinlichkeitsschätzungen zu einer hochdimensionalen Wahrscheinlichkeit zu kombinieren. Der Anwender nutzt sein Wissen über eine Aufgabe, um die Projektionen auszuwählen und sie zu kombinieren. Anders als eine Schätzung im hochdimensionalen Merkmalsraum, ist das resultierende Modell visualisierbar und intuitiv verständlich. Zur Umsetzung dieser Idee werden verschiedene Algorithmen neu entwickelt und bestehende Verfahren verbessert. Beispielsweise wird eine eindimensionale Verteilungsschätzung ausgearbeitet, die sich bei einer Evaluierung auf synthetischen und realen Daten als die bisher genauste Methode erweist. Sie basiert auf einem weiterentwickelten adaptiven Kerndichteschätzer, dessen Parameter durch ein normalisiertes Leave-One-Out Likelihood Cross-Validation gewählt wird. Das Verfahren erlaubt auch die häufig kritische Abschätzung von diskreten und gerundeten Daten. Ein weiterer Schwerpunkt liegt auf Algorithmen zur schnellen Berechnung großer Datenbestände. Durch verschiedene Verfahren wie Sample Scale Space, Kernelscope und Parsel wird eine annähernd lineare Aufwandsklasse erreicht. Die Arbeit beschreibt vielfältige Beispiele für Anwendungen von Cepel. So wird etwa eine Bildsegmentierung entwickelt, die das drittgenaueste Ergebnis auf dem Standarddatensatz der Berkeley University erzielt. Dabei wird lediglich ein Bruchteil der Trainingsdaten benötigt und es werden nur sehr einfache Merkmale verwendet. Eine zweites Anwendungsbeispiel ist ein Data Mining Verfahren, mit dem Zusammenhänge, wie Linearität, Unabhängigkeit oder Cluster, automatisch aus komplexen Messwerten extrahiert werden können. Weitere Anwendungen sind beispielsweise eine Merkmalsselektion, die Analyse koronarer Herzkrankheiten und eine Pumpenauswahl in der Schwerindustrie.A key ingredient to modern data analysis is probability estimation. However, it is well known that the curse of dimensionality prevents a proper estimation of probability in high dimensions. The problem is typically circumvented by using a fixed set of assumptions about the data, e.g., by assuming partial independence of features, data on a manifold or a customized kernel. These fixed assumptions limit the applicability of a method. This thesis introduces a new method for data analysis called Cepel, which is an abbreviation for Constructive Probabilistic Learning. It uses a flexible set of assumptions to tailor a model to various problems. The approach estimates the complete probability distribution of data by means of 1d-decomposition. It achieves a fast runtime and is not limited by the curse of dimensionality as all estimations are performed in 1d-space. Various new or improved algorithms are introduced to implement this approach. One example is a method for automatic probability estimation of 1d-distributions. It combines an adaptive kernel density and a frequency estimator with a normalized leave-one-out likelihood cross-validation. A thorough evaluation demonstrates that this method achieves the highest precision on synthetic and real data. Another crucial problem addressed is the overall runtime of the approach. By developing various algorithms like Sample Scale Space, Kernelscope and Parsel the runtime is reduced to a close to linear complexity. Throughout the thesis the wide range of applications of Cepel is demonstrated. Examples range from a feature selection strategy and an analysis of coronary heart disease to a pump selection for heavy industry. Another application is an image segmentation method. It achieves state of the art performance on a benchmark dataset although it requires only a fraction of the training data and very simple features. Finally, a unique software for automatic data mining is realized. It allows the fully automatic discovery of patterns in tabular data. The software is publicly available for evaluation