Implementing Delegable Inference for Graphical Models

Abstract

Factor graphs are a versatile tool with a wide range of applications from multilinear algorithm design to the study quantum many-body systems. However, exact inference in factor graphs is #P-hard in general. This motivates the development of inference algorithms which can be robustly delegated to extensive and possibly unreliable computational infrastructure. Building on noninteractive proof systems and error-correcting polynomial codes, Karimi et al. recently presented such a framework for delegable exact inference for factor graphs. The framework enables a delegator to recover and probabilistically verify the results of delegated inference, with tolerance for errors in the delegated computations. The main contribution of this thesis is a library implementing Karimi et al.’s framework. We review some of the theoretical foundations upon which Karimi et al.’s framework is built and outline the key aspects of our implementation. The full source code of the library is available online. We evaluate our library on the tasks of matrix multiplication and computing matrix permanents, by reducing them to the task of inference in factor graphs. We show empirically that the desirable theoretical properties of Karimi et al.’s framework hold; in particular, the complexity of verification was found to be negligible relative to the complexity of performing inference. However, the library’s overall performance was found to fall short of being competitive. Fortunately, the inference framework admits massive parallelism beyond what our implementation exploited, implying that large speedups are possible. We identify performance bottlenecks and provide suggestions for how to extend the library to improve its performance.

Faktorigraafit ovat monipuolinen työkalu, jolla on laajasti sovelluksia monilineaarisesta algoritmisuunnittelusta kvanttijärjestelmien tutkimiseen. Kuitenkin tarkka päättely faktorigraafeissa on yleisesti #P-vaikeaa. Tämä motivoi kehittämään päättelyalgoritmeja, jotka voidaan delegoida laajamittaisen ja mahdollisesti epäluotettavan laskentainfrastruktuurin suoritettavaksi. Pohjautuen ei-vuorovaikutteisiin todistusjärjestelmiin ja virheenkorjauspolynomikoodeihin, Karimi et al. hiljattain esittivät kyseisenlaisen algoritmin delegoitaville tarkalle päättelylle faktorigraafeille. Algoritmi mahdollistaa päättelytehtävän delegoinnin ja päättelyn tuloksen probabilistisen tarkistamisen, tarjoten myös toleranssia virheille delegoidussa päättelyssä. Tämän opinnäytetyön pääkontribuutio on Karimi et al.:n algoritmin toteuttava kirjasto. Käymme läpi joitain teoreettisia perusteita, joille Karimi et al.:n algoritmi on rakennettu, ja annamme yhteenvedon toteutuksen keskeisistä kohdista. Kirjaston lähdekoodi on saatavilla verkossa. Arvioimme kirjastomme toimivuutta kahdella laskennallisella tehtävällä---matriisikertolaskulla sekä matriisipermanentin laskemisella---redusoimalla ne päättelyksi faktorigraafeissa. Todennamme Karimi et al.:n algoritmin toivottavat teoreettiset ominaisuudet empiirisesti; erityisesti delegoidun tuloksen tarkistamisen kompleksisuuden havaittiin olevan mitätön verrattuna itse päätelyn suorittamisen kompleksisuuteen. Kirjaston yleisen suorituskyvyn todettiin kuitenkin olevan vähemmän kuin kilpailukykyinen. Karimi et al.:n algoritmi kuitenkin mahdollistaisi korkea-asteisen rinnakkaisuuden, jota toteutuksemme ei hyödyntänyt; toteutuksesta voisi siis tehdä paljon nopeamman. Identifioimme suorituskyvyn pullonkaulat ja annamme ehdotuksia, kuinka kirjastoa voisi kehittää sen suorituskyvyn parantamiseksi.