Open Collections

Fast methods for inference in graphical models and beat tracking the graphical model way

University of British Columbia

This thesis presents two related bodies of work. The first is about methods for speeding up inference in graphical models, and the second is an application of the graphical model framework to the beat tracking problem in sampled music. Graphical models have become ubiquitous modelling tools; they are commonly used in computer vision, bioinformatics, coding theory, speech recognition, and are central to many machine learning techniques. Graphical models allow statistical independence relationships between random variables to be expressed in a flexible, powerful, and intuitive manner. Given observations, there are standard algorithms to compute probability distributions over unknown states (marginals) or to find the most likely configuration (maximum a posteriori, MAP, state). However, if each node in the graphical model has TV states, then these computations cost O (N²). This is a particular concern when dealing with continuous (or large discrete) state spaces. In such state spaces, Monte Carlo methods are of great use, but typically produce better answers as N increases. There is therefore a need for algorithms to speed up these computations. We review the graphical model framework and explain the algorithms that we consider: Belief Propagation, Maximum-Belief Propagation, and Particle Filtering and Smoothing. We review existing fast methods for speeding up these computations, and present a new fast method, some analysis, corrections, and improvements to existing methods, and an empirical evaluation of the fast methods with respect to a variety of parameters. Finally, we point out other applications to which this fast machinery can be applied. The second body of work is an application of the graphical model framework to a common problem in music analysis: beat tracking. The goal of beat tracking is to determine the tempo track of a piece of sampled music, and to determine the points in time at which beats occur. While fairly simple, our graphical model performs remarkably well on a difficult and varied set of songs.

Thesis/Dissertation

application/pdf

2009-11-24

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/15604

Computer Science

University of British Columbia

UBCV

DSpace