Not logged in.

Quick Search - Contribution

Contribution Details

Type Master's Thesis
Scope Discipline-based scholarship
Title Using Genetic Programming and SimPack to Learn Global Similarity Measures
Organization Unit
Authors
  • Manuel Kägi
Supervisors
  • Christoph Kiefer
  • Abraham Bernstein
Institution University of Zurich
Faculty Faculty of Economics, Business Administration and Information Technology
Date 2006
Abstract Text For a growing number of applications good similarity measures are crucial to ensure that the applications works as desired. Similarity measures can be used to find the most similar object to another one, or can be used to perform a categorisation task, whereby the calculated similarity value will be used to determine the category. But manually defining a good similarity measure, especially if complex and domain specific objects have to be compared, can be a difficult task. A lot of domain knowledge combined with knowledge in computer science (namely how these similarity measures work internally) is needed, and there exists no approved methodology to do this. Therefore the global goal in this diploma thesis is, instead of manually defining similarity measures, to learn them and to evaluate the achieved results.To be able to learn similarity measures, an universal framework is used, the Local/Global Framework. The idea is to use the Local/Global principle to compare complex objects, whereby the local similarity measures and the amalgamation function can be learned. Another precondition for this is to have an evaluation method to estimate a particular similarity measure's soundness. Typically this is done by comparing the similarity measure's results with a so-called gold standard.To learn, the evolutionary principles observed in nature will be exploited in an artificial evolution. This artificial evolution can be implemented as a genetic algorithm or a genetic programming approach can be used. In the first case parameters of similarity measures will be learned, in the second case, using the genetic programming approach, the algorithms themselves are learned. In both cases the goal is to find similarity measures, which will show only a small deviation to the gold standard. In the case of using a similarity measure to do a categorisation, the goal will be to properly identify the category an object or a pair of objects (the two compared ones) belongs to.
Zusammenfassung Für eine wachsende Zahl von Anwendungen ist es essentiell gute Ähnlichkeitsmasse zu haben, um zu erreichen, dass diese Applikationen ihren Zweck erfüllen. Ähnlichkeitsmasse können dazu verwendet werden, das ähnlichste Objekt zu einem gegebenen Objekt zu bestimmen, oder um eine Kategorisierung vorzunehmen, wobei in diesem Fall die berechneten Ähnlichkeitswerte dazu verwendet werden um die Kategorie zu bestimmen. Aber diese Ähnlichkeitsmasse genau zu definieren, vor allem wenn diese komplexe, sachgebietspezifische Objekte vergleichen sollen, kann eine schwierige Aufgabe sein. Gute Kenntnisse über das Sachgebiet, auf das sich die Objekte beziehen, kombiniert mit Informatikkenntissen (über die internen Vorgänge der Ähnlichkeitsmasse) sind nötig und es gibt keine standardisierte Vorgehensweise solche Ähnlichkeitsmasse zu definieren. Deshalb ist es das Ziel dieser Diplomarbeit, anstatt Ähnlichkeitsmasse zu definieren, solche zu lernen und die erreichten Resultate zu evaluieren.Um Ähnlichkeitsmasse zu lernen, wird ein Framework benutzt, das Local/Global Framework. Die Idee ist es, das Local/Global Prinzip zu nutzen, um komplexe Objekte zu vergleichen. Dabei können die lokalen Ähnlichkeitsmasse und die Vereinigungsfunktion gelernt werden. Eine weitere Voraussetzung ist es, eine Evaluationsmethode zu haben um die erreichte Zweckmässigkeit eines Ähnlichkeitsmasses abzuschätzen. Dies wird üblicherweise gemacht indem die Resultate des Ähnlichkeitsmasses mit einem sogenannten Gold-Standard verglichen werden.Um diese Masse zu lernen, werden die Prinzipien der natürlichen Evolution ausgenutzt. Diese künstliche Evolution kann als genetischer Algorithmus oder mit dem Ansatz der genetischen Programmierung realisiert werden. Im ersten Fall werden die Parameterwerte für die Ähnlichkeitsmasse erlernt, im zweiten Fall, wo der Ansatz der genetischen Programmierung verwendet wird, wird ein Algorithmus erlernt. In beiden Fällen ist es immer das Ziel, ein Mass zu finden, dass eine möglichst geringe Abweichung zum Gold-Standard aufweist. Wenn die Ähnlichkeitsmasse verwendet werden um eine Kategorisierung durchzuführen, ist das Ziel, die Kategorie, zu der ein Objekt oder Objektpaar (die beiden verglichenen) gehört, korrekt anzugeben.
PDF File Download
Export BibTeX