Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
Greedy algorithms (also called “Hill Climbing”) are algorithms that are iterative in nature and choose a best solution from a range of possible candidate solutions at each iteration until a stopping criterion is met (usually when there is no improvement seen). As a result, greedy algorithms get stuck at local optima and are unable to improve beyond these optima. Many different types of methods (metaheuristics) have been introduced to overcome these shortcomings, from the mundanely simple (Random Restart) to clever attempts at mimicking nature’s ability to solve problems (Ant Colony Optimization). Widening is a new metaheuristic that uses diversity among parallel workers to improve on greedy algorithms. Bayesian Networks are probabilistic graphical models used in a variety of applications from medical diagnosis to document classification, among many others. When learning the structure of Bayesian networks from data, the hypothesis space grows superexponentially with the number of features in the dataset, making their hypothesis space an interesting use case for understanding the effects of Widening on greedy learning algorithms from those datasets. This dissertation describes Widening as a metaheuristic and places it in context to other metaheuristics. Widening is inherently parallel and can take advantage of the rapid growth of parallel resources available today. The key element of Widening is its use of diversity to ensure that the parallel workers explore different regions of the hypothesis space. Widening can be realized by explicitly enforcing diversity among the parallel workers at each iterative step, called here Diverse Top-k Widening. It can also be realized by methods where the hypothesis space is partitioned and each parallel worker is restricted to a specific partition, thus enabling the parallel workers to proceed without exchanging information among themselves, called here Communication-free Widening. This dissertation covers one method of Diverse Top-k Widening, where a diversity measure, ...