The Libra Toolkit for Probabilistic Models
\name Daniel Lowd \email lowd@cs.uoregon.edu
\addr Department of Computer and Information Science
University of Oregon
Eugene
OR 97403
USA \AND \name Amirmohammad Rooshenas \email pedram@cs.uoregon.edu
\addr Department of Computer and Information Science
University of Oregon
Eugene
OR 97403
USA
% <- trailing '%' for backward compatibility of .sty file The Libra Toolkit is a collection of algorithms for learning and inference with discrete probabilistic models, including Bayesian networks, Markov networks, dependency networks, and sum-product networks. Compared to other toolkits, Libra places a greater emphasis on learning the structure of tractable models in which exact inference is efficient. It also includes a variety of algorithms for learning graphical models in which inference is potentially intractable, and for performing exact and approximate inference. Libra is released under a 2-clause BSD license to encourage broad use in academia and industry.
lowd15a1.tex
\documentclass[twoside,11pt]{article}

% Any additional packages needed should be included after jmlr2e.
% Note that jmlr2e.sty includes epsfig, amssymb, natbib and graphicx,
% and defines many common macros, such as 'proof' and 'example'.
%
% It also sets the bibliographystyle to plainnat; for more information on
% natbib citation styles, see the natbib documentation, a copy of which
% is archived at http://www.jmlr.org/format/natbib.pdf

\usepackage{jmlr2e}
\usepackage{algorithmic}
\usepackage{algorithm}
\usepackage[cmex10]{amsmath}
\usepackage{amssymb}
\usepackage{ifpdf}
\usepackage{rotating}

\usepackage{url}
\usepackage[usenames,dvipsnames]{color}


\newcommand{\eat}[1]{}
\newcommand{\oldversion}[1]{}
\newcommand{\pedram}[1]{\textcolor{Blue}{\emph{[Pedram: #1]}}}
\newcommand{\daniel}[1]{\textcolor{Red}{\emph{[Daniel: #1]}}}
\newcommand{\mc}{\multicolumn}


\newcommand{\dataset}{{\cal D}}
\newcommand{\fracpartial}[2]{\frac{\partial #1}{\partial  #2}}

% Heading arguments are {volume}{year}{pages}{submitted}{published}{author-full-names}

%\jmlrheading{1}{2012}{1-48}{9/12}{?/??}{Daniel Lowd and Amirmohammad Rooshenas}

% Short headings should be running head and authors last names

\ShortHeadings{The Libra Toolkit for Probabilistic Models}{Lowd and Rooshenas}
\firstpageno{1}

\begin{document}

\title{The Libra Toolkit for Probabilistic Models}

\author{\name Daniel Lowd \email lowd@cs.uoregon.edu \\
       \addr Department of Computer and Information Science\\
       University of Oregon\\
       Eugene, OR 97403, USA
       \AND
       \name Amirmohammad Rooshenas \email pedram@cs.uoregon.edu \\
       \addr Department of Computer and Information Science\\
       University of Oregon\\
       Eugene, OR 97403, USA}

\editor{??}

\maketitle

\begin{abstract}%   <- trailing '%' for backward compatibility of .sty file
The Libra Toolkit is a collection of algorithms for
learning and inference with discrete probabilistic models, including
Bayesian networks, Markov networks, dependency networks, and
sum-product networks.  Compared to other toolkits, Libra places a
greater emphasis on learning the structure of tractable models in
which exact inference is efficient.  It also includes a variety of
algorithms for learning graphical models in which inference is 
potentially intractable, and for performing exact and approximate 
inference.  Libra is released under a 2-clause BSD license
to encourage broad use in academia and industry.
\end{abstract}

\begin{keywords}
Probabilistic graphical models, structure learning, inference
\end{keywords}

\section{Introduction}

The Libra Toolkit is a collection of algorithms for learning and
inference with probabilistic models in discrete domains.  What
distinguishes Libra from other toolkits is the types of methods and
models it supports.  Libra includes a number of algorithms for {\em
structure learning for tractable probabilistic models} in which exact
inference can be done efficiently.  Such models include sum-product
networks (SPN), mixtures of trees (MT), and Bayesian and Markov
networks with compact arithmetic circuits (AC).  These learning
algorithms are not available in any other open-source toolkit.  Libra
also supports {\em structure learning for graphical models}, such as
Bayesian networks (BN), Markov networks (MN), and dependency networks
(DN), in which inference is not necessarily tractable.  Some of these
methods are unique to Libra as well, such as using dependency networks
to learn Markov networks.  Libra provides a variety of exact and
approximate inference algorithms for answering probabilistic queries
in learned or manually specified models.  Many of these are designed
to exploit local structure, such as conjunctive feature functions or
tree-structured conditional probability distributions.

The overall goal of Libra is to make these methods available to
researchers, practitioners, and students for use in experiments,
applications, and education.  Each algorithm in Libra is implemented
in a command-line program suitable for interactive use or scripting,
with consistent options and file formats throughout the toolkit.
Libra also supports the development of new algorithms through modular
code organization, including shared libraries for different
representations and file formats.  

Libra is available under a modified (2-clause) BSD license, which
allows modification and reuse in both academia and industry.

\section{Functionality}

Libra includes a variety of learning and inference algorithms, many of
which are not available in any other open-source toolkit.
See Table~\ref{tab:functionality} for a brief overview.

\newcommand{\pcite}[1]{\protect{\citep{#1}}}

\begin{table}
\begin{center}
\begin{scriptsize}
\begin{tabular}{|lll|}
\hline
\multicolumn{3}{|c|}{Learning General Models} \\
\hline
$\circ$   & BN structure with tree CPDs & \pcite{chickering&al97} \\
          & DN structure with tree/boosted tree/LR CPDs & \pcite{heckerman&al00} \\
$\bullet$ & MN structure from DNs & \pcite{lowd12} \\
          & MN parameters (pseudo-likelihood) & \\
\hline
\multicolumn{3}{|c|}{Learning Tractable Models} \\
\hline
$\bullet$ & Tractable BN/AC structure & \pcite{lowd&domingos08} \\
$\bullet$ & Tractable MN/AC structure & \pcite{lowd&rooshenas13} \\
$\bullet$ & Mixture of trees (MT) & \pcite{meila&jordan00} \\
$\bullet$ & SPN structure (ID-SPN algorithm) & \pcite{rooshenas&lowd14} \\
          %& SPN structure (LearnSPN algorithm) & \pcite{gens&domingos13} \\
          & Chow-Liu algorithm & \pcite{chow&liu68} \\
$\bullet$ & AC parameters (maximum likelihood) & \\
\hline
\multicolumn{3}{|c|}{Approximate Inference} \\
\hline
          & Gibbs sampling (BN,MN,$\bullet$DN) & \pcite{heckerman&al00} (DN) \\
          & Mean field (BN,MN,$\bullet$DN) & \pcite{lowd&shamaei11} (DN) \\
          & Loopy belief propagation (BN,MN) & \\
          & Max-product (BN,MN) & \\
          & Iterated conditional modes (BN,MN,$\bullet$DN) & \\
$\bullet$ & Variational optimization of ACs & \pcite{lowd&domingos10} \\
\hline
\multicolumn{3}{|c|}{Exact Inference} \\
\hline
$\circ$ & AC variable elimination (BN,MN) & \pcite{chavira&darwiche07} \\
$\circ$ & Marginal and MAP inference (AC,SPN,MT) & \pcite{darwiche03} \\
\hline
\end{tabular}
\end{scriptsize}
\end{center}
\caption{Learning and inference algorithms implemented in Libra.
Filled circles ($\bullet$) indicate algorithms that are unique to
Libra, and hollow circles ($\circ$) indicate algorithms with no other
open-source implementation.}
\label{tab:functionality}
\end{table}

Libra's command-line syntax is designed to be simple. For example, to
learn a tractable BN, run the command: ``{\tt libra acbn -i
train.data -mo model.bn -o model.ac}'' where {\tt train.data} is the
input data, {\tt model.bn} is the filename for saving the learned BN,
and {\tt model.ac} is the filename for the corresponding AC
representation, which allows for efficient, exact inference.  To
compute exact conditional marginals in the learned model: ``{\tt libra
acquery -m model.ac -ev test.ev -marg}''.  To compute approximate
marginals in the BN with loopy belief propagation: ``{\tt libra bp -m
model.bn -ev test.ev}''.  Additional command-line parameters can be
used to specify other options, such as the priors and heuristics used
by {\tt acbn} or the maximum number of iterations for {\tt bp}.  These
are just three of more than twenty commands included in Libra.

Libra supports a variety of file formats.  For data instances, Libra
uses comma separated values, where each value is a zero-based index
indicating the discrete value of the corresponding variable.  For
evidence and query files, unknown or missing values are represented
with the special value ``\verb|*|''.  For model files, Libra supports
the XMOD representation from the WinMine Toolkit, the Bayesian
interchange format (BIF), and the simple representation from the UAI
inference competition.  Libra converts among these different formats
using the provided {\tt mconvert} utility, as well as to its own
internal formats for BNs, MNs, and DNs ({\tt .bn}, {\tt .mn}, {\tt
.dn}).  Libra has additional representations for ACs and SPNs ({\tt
.ac}, {\tt .spn}).  These formats are designed to be easy for
humans to read and programs to parse.

Libra is implemented in OCaml.  OCaml is a statically typed language
that supports functional and imperative programming styles, compiles
to native machine code on multiple platforms, and uses type inference
and garbage collection to reduce programmer errors and effort.  OCaml
has a good foreign function interface, which Libra uses for linking to
C libraries and implementing some memory-intensive subroutines more
efficiently in C.  The code to Libra includes nine support libraries,
which provide modules for input, output, and representation of
different types of models, as well as commonly used algorithms and
utility methods.  

\section{Comparison to Other Toolkits}

In Table~\ref{tab:comparison}, we compare Libra to other toolkits in
terms of representation, learning, and inference.

\begin{table}
\begin{center}
\begin{scriptsize}
\begin{tabular}{|l|ll|ll|ll|}
\hline
& \multicolumn{2}{c}{Representation} & \multicolumn{2}{c}{Inference} & \multicolumn{2}{c|}{Learning} \\
Toolkit & Model Types       & Factors          & Exact & Approx. & Param.               & Structure  \\
\hline
Libra                & BN,MN,DN,SPN,AC & Tree,Feature & ACVE & G,BP,MF & ML,PL & BN,\dots,AC \\
\hline              
FastInf              & BN,MN & Table       & JT      & Many & ML,EM & - \\
libDAI               & BN,MN & Table       & JT,E    & Many & ML,EM & - \\
OpenGM2              & BN,MN & Sparse      & -       & Many & -     & - \\
\hline               
Banjo                & BN,DBN    & Table       & -       & -              & -     & BN \\
BNT                  & BN,DBN,ID & LR,OR,NN    & JT,VE,E & G,LW,BP        & ML,EM & BN \\
Deal                 & BN        & Table       & -       & -              & -     & BN \\
OpenMarkov           & BN,MN,ID  & Tree,ADD,OR & JT      & LW             & ML    & BN,MN \\
SMILE                & BN,DBN,ID & Table       & JT      & Sampling       & ML,EM & BN \\ 
UnBBayes             & BN,ID     & Table       & JT      & G,LW           & -     & BN \\
\hline
\end{tabular}
\end{scriptsize}
\end{center}
\caption{Comparison of Libra to several other probabilistic inference and learning toolkits.}
\label{tab:comparison}
\end{table}

In terms of representation, Libra is the only open-source software
package that supports ACs and one of a very small number that support
DNs or SPNs.  Libra does not currently support dynamic Bayesian
networks (DBN) or influence diagrams (ID).  For factors, Libra
supports tables, trees, and arbitrary conjunctive feature functions.
BNT~\citep{murphy01} and OpenMarkov~(CISIAD, 2013)
\nocite{openmarkov13} also support additional types of CPDs, such as
logistic regression, noisy-OR, neural networks, and algebraic decision
diagrams, but they only support tabular CPDs for structure learning.
OpenGM2~\citep{opengm2} supports sparse factors, but iterates through
all factor states during inference.  Libra is unique in its ability to
learn models with local structure and exploit that structure in
inference.

For exact inference, the most common algorithms are junction tree
(JT), enumeration (E), and variable elimination (VE).  Libra provides
ACVE~\citep{chavira&darwiche07}, which is similar to building a
junction tree, but it can exploit structured factors to run inference
in many high-treewidth models.  For approximate inference, Libra
provides Gibbs sampling (G), loopy belief propagation (BP), and mean
field (MF), all of which are optimized for structured factors.  A few
learning toolkits offer likelihood weighting (LW) or additional
sampling algorithms for BNs.  FastInf~\citep{jaimovich&al10},
libDAI~\citep{mooij10}, and OpenGM2 offer the most algorithms but only
support tables.

For learning, Libra supports maximum likelihood (ML) parameter
learning for BNs, ACs, and SPNs, and pseudo-likelihood (PL)
optimization for MNs and DNs.  Libra does not yet support expectation
maximization (EM) for learning with missing values.  Structure
learning is one of Libra's greatest strengths.  Most toolkits only
provide algorithms for learning BNs with tabular CPDs or MNs using the
PC algorithm~\citep{spirtes&al93}.  Libra includes methods for learning
BNs, MNs, DNs, SPNs, and ACs, and all of its algorithms support
learning with local structure.

In experiments on grid-structured MNs, Libra's implementations of BP
and Gibbs sampling were at least as fast as libDAI, a popular C++
implementation of many inference algorithms.  The accuracy of both
toolkits was equivalent.  Parameter settings, such as the number of
iterations, were identical.  See Figure~\ref{fig:libdai} for more
details.

\begin{figure}
\begin{center}
\includegraphics[scale=0.5]{runtime.pdf}
\vspace{-0.3in}
\end{center}
\caption{Running time of belief propagation and Gibbs sampling in
Libra and libDAI, evaluated on grid-structured MNs of various sizes.}
\label{fig:libdai}
\end{figure}

\section{Conclusion}

The Libra Toolkit provides algorithms for learning and inference in a
variety of probabilistic models, including BNs, MNs, DNs, SPNs, and
ACs.  Many of these algorithms are not available in any other
open-source software.  Libra's greatest strength is its support for
tractable probabilistic models, for which very little other software
exists.  Libra makes it easy to use these state-of-the-art methods in
experiments and applications, which we hope will accelerate the
development and deployment of probabilistic methods.

\acks{The development of Libra was partially supported by ARO grant
W911NF-08-1-0242, NSF grant IIS-1118050, NIH grant R01GM103309, 
and a Google Faculty Research Award.  The views and conclusions 
contained in this document are those
of the authors and should not be interpreted as necessarily
representing the official policies, either expressed or implied, of
ARO, NIH, or the United States Government.}

\newcommand{\jmlr}{JMLR}

%\bibliography{all}
\begin{thebibliography}{18}
\providecommand{\natexlab}[1]{#1}
\providecommand{\url}[1]{\texttt{#1}}
\expandafter\ifx\csname urlstyle\endcsname\relax
  \providecommand{\doi}[1]{doi: #1}\else
  \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi

\bibitem[Andres et~al.(2012)Andres, Beier, and Kappes]{opengm2}
B.~Andres, T.~Beier, and J.~H. Kappes.
\newblock {OpenGM}: A {C++} library for discrete graphical models.
\newblock \emph{ArXiv e-prints}, 2012.
\newblock URL \url{http://arxiv.org/abs/1206.0111}.

\bibitem[Chavira and Darwiche(2007)]{chavira&darwiche07}
M.~Chavira and A.~Darwiche.
\newblock Compiling {B}ayesian networks using variable elimination.
\newblock In \emph{IJCAI}, pages 2443--2449, 2007.

\bibitem[Chickering et~al.(1997)Chickering, Heckerman, and
  Meek]{chickering&al97}
D.~Chickering, D.~Heckerman, and C.~Meek.
\newblock A {Bayesian} approach to learning {Bayesian} networks with local
  structure.
\newblock In \emph{UAI}, pages 80--89, 1997.

\bibitem[Chow and Liu(1968)]{chow&liu68}
C.~K. Chow and C.~N Liu.
\newblock Approximating discrete probability distributions with dependence
  trees.
\newblock \emph{{IEEE} Transactions on Information Theory}, 14:\penalty0
  462--467, 1968.

\bibitem[(CISIAD)(2013)]{openmarkov13}
{Research Center on Intelligent Decision-Support Systems} (CISIAD).
\newblock {OpenMarkov} 0.1.3.
\newblock 2013.
\newblock http://www.openmarkov.org.

\bibitem[Darwiche(2003)]{darwiche03}
A.~Darwiche.
\newblock A differential approach to inference in {B}ayesian networks.
\newblock \emph{JACM}, 50\penalty0 (3):\penalty0 280--305, 2003.

\bibitem[Heckerman et~al.(2000)Heckerman, Chickering, Meek, Rounthwaite, and
  Kadie]{heckerman&al00}
D.~Heckerman, D.~M. Chickering, C.~Meek, R.~Rounthwaite, and C.~Kadie.
\newblock Dependency networks for inference, collaborative filtering, and data
  visualization.
\newblock \emph{\jmlr}, 1:\penalty0 49--75,
  2000.

\bibitem[Jaimovich et~al.(2010)Jaimovich, Meshi, McGraw, and
  Elidan]{jaimovich&al10}
A.~Jaimovich, O.~Meshi, I.~McGraw, and G.~Elidan.
\newblock FastInf: An efficient approximate inference library.
\newblock \emph{\jmlr}, 11:\penalty0 1733--1736,
  2010.

\bibitem[Lowd(2012)]{lowd12}
D.~Lowd.
\newblock Closed-form learning of {M}arkov networks from dependency networks.
\newblock In \emph{UAI}, 2012.

\bibitem[Lowd and Domingos(2008)]{lowd&domingos08}
D.~Lowd and P.~Domingos.
\newblock Learning arithmetic circuits.
\newblock In \emph{UAI}, 2008.

\bibitem[Lowd and Domingos(2010)]{lowd&domingos10}
D.~Lowd and P.~Domingos.
\newblock Approximate inference by compilation to arithmetic circuits.
\newblock In \emph{NIPS}, 2010.

\bibitem[Lowd and Rooshenas(2013)]{lowd&rooshenas13}
D.~Lowd and A.~Rooshenas.
\newblock Learning {M}arkov networks with arithmetic circuits.
\newblock In \emph{AISTATS}, 2013.

\bibitem[Lowd and Shamaei(2011)]{lowd&shamaei11}
D.~Lowd and A.~Shamaei.
\newblock Mean field inference in dependency networks: An empirical study.
\newblock In \emph{AAAI}, 2011.

\bibitem[Meila and Jordan(2000)]{meila&jordan00}
M.~Meila and M.~Jordan.
\newblock Learning with mixtures of trees.
\newblock \emph{\jmlr}, 1:\penalty0 1--48, 2000.

\bibitem[Mooij(2010)]{mooij10}
Joris~M. Mooij.
\newblock lib{DAI}: A free and open source {C++} library for discrete
  approximate inference in graphical models.
\newblock \emph{\jmlr}, 11:\penalty0 2169--2173,
  2010.

\bibitem[Murphy(2001)]{murphy01}
K.~Murphy.
\newblock The {B}ayes net toolbox for {MATLAB}.
\newblock \emph{Computing Sci.\ and Statistics}, 33:\penalty0 2001.

\bibitem[Rooshenas and Lowd(2014)]{rooshenas&lowd14}
A.~Rooshenas and D.~Lowd.
\newblock Learning sum-product networks with direct and indirect interactions.
\newblock In \emph{ICML}, 2014.

\bibitem[Spirtes et~al.(1993)Spirtes, Glymour, and Scheines]{spirtes&al93}
P.~Spirtes, C.~Glymour, and R.~Scheines.
\newblock \emph{Causation, Prediction, and Search}.
\newblock Springer, New York, NY, 1993.

\end{thebibliography}

\end{document}

1504.00110.extracted_bib
[Andres et~al.(2012)Andres, Beier, and Kappes]{opengm2 B.~Andres, T.~Beier, and J.~H. Kappes. \newblock {OpenGM: A {C++ library for discrete graphical models. \newblock ArXiv e-prints, 2012. \newblock URL \url{http://arxiv.org/abs/1206.0111.
1504.00110.extracted_bib
[Chavira and Darwiche(2007)]{chavira&darwiche07 M.~Chavira and A.~Darwiche. \newblock Compiling {Bayesian networks using variable elimination. \newblock In IJCAI, pages 2443--2449, 2007.
1504.00110.extracted_bib
[Chickering et~al.(1997)Chickering, Heckerman, and Meek]{chickering&al97 D.~Chickering, D.~Heckerman, and C.~Meek. \newblock A {Bayesian approach to learning {Bayesian networks with local structure. \newblock In UAI, pages 80--89, 1997.
1504.00110.extracted_bib
[Chow and Liu(1968)]{chow&liu68 C.~K. Chow and C.~N Liu. \newblock Approximating discrete probability distributions with dependence trees. \newblock {IEEE Transactions on Information Theory, 14:\penalty0 462--467, 1968.
1504.00110.extracted_bib
[(CISIAD)(2013)]{openmarkov13 {Research Center on Intelligent Decision-Support Systems (CISIAD). \newblock {OpenMarkov 0.1.3. \newblock 2013. \newblock http://www.openmarkov.org.
1504.00110.extracted_bib
[Darwiche(2003)]{darwiche03 A.~Darwiche. \newblock A differential approach to inference in {Bayesian networks. \newblock JACM, 50\penalty0 (3):\penalty0 280--305, 2003.
1504.00110.extracted_bib
[Heckerman et~al.(2000)Heckerman, Chickering, Meek, Rounthwaite, and Kadie]{heckerman&al00 D.~Heckerman, D.~M. Chickering, C.~Meek, R.~Rounthwaite, and C.~Kadie. \newblock Dependency networks for inference, collaborative filtering, and data visualization. \newblock \jmlr, 1:\penalty0 49--75, 2000.
1504.00110.extracted_bib
[Jaimovich et~al.(2010)Jaimovich, Meshi, McGraw, and Elidan]{jaimovich&al10 A.~Jaimovich, O.~Meshi, I.~McGraw, and G.~Elidan. \newblock FastInf: An efficient approximate inference library. \newblock \jmlr, 11:\penalty0 1733--1736, 2010.
1504.00110.extracted_bib
[Lowd(2012)]{lowd12 D.~Lowd. \newblock Closed-form learning of {Markov networks from dependency networks. \newblock In UAI, 2012.
1504.00110.extracted_bib
[Lowd and Domingos(2008)]{lowd&domingos08 D.~Lowd and P.~Domingos. \newblock Learning arithmetic circuits. \newblock In UAI, 2008.
1504.00110.extracted_bib
[Lowd and Domingos(2010)]{lowd&domingos10 D.~Lowd and P.~Domingos. \newblock Approximate inference by compilation to arithmetic circuits. \newblock In NIPS, 2010.
1504.00110.extracted_bib
[Lowd and Rooshenas(2013)]{lowd&rooshenas13 D.~Lowd and A.~Rooshenas. \newblock Learning {Markov networks with arithmetic circuits. \newblock In AISTATS, 2013.
1504.00110.extracted_bib
[Lowd and Shamaei(2011)]{lowd&shamaei11 D.~Lowd and A.~Shamaei. \newblock Mean field inference in dependency networks: An empirical study. \newblock In AAAI, 2011.
1504.00110.extracted_bib
[Meila and Jordan(2000)]{meila&jordan00 M.~Meila and M.~Jordan. \newblock Learning with mixtures of trees. \newblock \jmlr, 1:\penalty0 1--48, 2000.
1504.00110.extracted_bib
[Mooij(2010)]{mooij10 Joris~M. Mooij. \newblock lib{DAI: A free and open source {C++ library for discrete approximate inference in graphical models. \newblock \jmlr, 11:\penalty0 2169--2173, 2010.
1504.00110.extracted_bib
[Murphy(2001)]{murphy01 K.~Murphy. \newblock The {Bayes net toolbox for {MATLAB. \newblock Computing Sci.\ and Statistics, 33:\penalty0 2001.
1504.00110.extracted_bib
[Rooshenas and Lowd(2014)]{rooshenas&lowd14 A.~Rooshenas and D.~Lowd. \newblock Learning sum-product networks with direct and indirect interactions. \newblock In ICML, 2014.
1504.00110.extracted_bib
[Spirtes et~al.(1993)Spirtes, Glymour, and Scheines]{spirtes&al93 P.~Spirtes, C.~Glymour, and R.~Scheines. \newblock Causation, Prediction, and Search. \newblock Springer, New York, NY, 1993.