Sparse Matrix Belief Propagation
| dc.contributor.author | Bixler, Reid Morris | en |
| dc.contributor.committeechair | Huang, Bert | en |
| dc.contributor.committeemember | Wang, Gang Alan | en |
| dc.contributor.committeemember | Huang, Jia-Bin | en |
| dc.contributor.department | Computer Science | en |
| dc.date.accessioned | 2018-05-12T08:00:24Z | en |
| dc.date.available | 2018-05-12T08:00:24Z | en |
| dc.date.issued | 2018-05-11 | en |
| dc.description.abstract | We propose sparse-matrix belief propagation, which executes loopy belief propagation in Markov random fields by replacing indexing over graph neighborhoods with sparse-matrix operations. This abstraction allows for seamless integration with optimized sparse linear algebra libraries, including those that perform matrix and tensor operations on modern hardware such as graphical processing units (GPUs). The sparse-matrix abstraction allows the implementation of belief propagation in a high-level language (e.g., Python) that is also able to leverage the power of GPU parallelization. We demonstrate sparse-matrix belief propagation by implementing it in a modern deep learning framework (PyTorch), measuring the resulting massive improvement in running time, and facilitating future integration into deep learning models. | en |
| dc.description.abstractgeneral | We propose sparse-matrix belief propagation, a modified form of loopy belief propagation that encodes the structure of a graph with sparse matrices. Our modifications replace a potentially complicated design of indexing over graph neighborhoods with more optimized and easily interpretable sparse-matrix operations. These operations, available in sparse linear algebra libraries, can also be performed on modern hardware such as graphical processing units (GPUs). By abstracting away the original index-based design with sparse-matrices it is possible to implement belief propagation in a high-level language such as Python that can also use the power of GPU parallelization, rather than rely on abstruse low-level language implementations. We show that sparse-matrix belief propagation, when implemented in a modern deep learning framework (PyTorch), results in massive improvements irunning time when compared against the original index-based version. Additionally this implementation facilitates future integration into deep learning models for wider adoption and use by data scientists. | en |
| dc.description.degree | Master of Science | en |
| dc.format.medium | ETD | en |
| dc.identifier.other | vt_gsexam:15270 | en |
| dc.identifier.uri | http://hdl.handle.net/10919/83228 | en |
| dc.publisher | Virginia Tech | en |
| dc.rights | In Copyright | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject | belief propagation | en |
| dc.subject | inference | en |
| dc.subject | GPU | en |
| dc.subject | sparse matrix | en |
| dc.title | Sparse Matrix Belief Propagation | en |
| dc.type | Thesis | en |
| thesis.degree.discipline | Computer Science and Applications | en |
| thesis.degree.grantor | Virginia Polytechnic Institute and State University | en |
| thesis.degree.level | masters | en |
| thesis.degree.name | Master of Science | en |
Files
Original bundle
1 - 1 of 1