Bare Demo of IEEEtran.cls for Conferences
\IEEEauthorblockN{Michael Shell} \IEEEauthorblockA{School of Electrical and
Computer Engineering
Atlanta, Georgia 30332--0250
Email: http://www.michaelshell.org/contact.html}
\IEEEauthorblockN{Homer Simpson} \IEEEauthorblockA{Twentieth Century Fox
Springfield, USA
\IEEEauthorblockN{James Kirk
and Montgomery Scott} \IEEEauthorblockA{Starfleet Academy
San Francisco, California 96678-2391
Telephone: (800) 555--1212
Fax: (888) 555--1212}
%\boldmath The abstract goes here.
bare_conf.tex

%% bare_conf.tex
%% V1.3
%% 2007/01/11
%% by Michael Shell
%% See:
%% http://www.michaelshell.org/
%% for current contact information.
%%
%% This is a skeleton file demonstrating the use of IEEEtran.cls
%% (requires IEEEtran.cls version 1.7 or later) with an IEEE conference paper.
%%
%% Support sites:
%% http://www.michaelshell.org/tex/ieeetran/
%% http://www.ctan.org/tex-archive/macros/latex/contrib/IEEEtran/
%% and
%% http://www.ieee.org/

%%*************************************************************************
%% Legal Notice:
%% This code is offered as-is without any warranty either expressed or
%% implied; without even the implied warranty of MERCHANTABILITY or
%% FITNESS FOR A PARTICULAR PURPOSE! 
%% User assumes all risk.
%% In no event shall IEEE or any contributor to this code be liable for
%% any damages or losses, including, but not limited to, incidental,
%% consequential, or any other damages, resulting from the use or misuse
%% of any information contained here.
%%
%% All comments are the opinions of their respective authors and are not
%% necessarily endorsed by the IEEE.
%%
%% This work is distributed under the LaTeX Project Public License (LPPL)
%% ( http://www.latex-project.org/ ) version 1.3, and may be freely used,
%% distributed and modified. A copy of the LPPL, version 1.3, is included
%% in the base LaTeX documentation of all distributions of LaTeX released
%% 2003/12/01 or later.
%% Retain all contribution notices and credits.
%% ** Modified files should be clearly indicated as such, including  **
%% ** renaming them and changing author support contact information. **
%%
%% File list of work: IEEEtran.cls, IEEEtran_HOWTO.pdf, bare_adv.tex,
%%                    bare_conf.tex, bare_jrnl.tex, bare_jrnl_compsoc.tex
%%*************************************************************************

% *** Authors should verify (and, if needed, correct) their LaTeX system  ***
% *** with the testflow diagnostic prior to trusting their LaTeX platform ***
% *** with production work. IEEE's font choices can trigger bugs that do  ***
% *** not appear when using other class files.                            ***
% The testflow support page is at:
% http://www.michaelshell.org/tex/testflow/



% Note that the a4paper option is mainly intended so that authors in
% countries using A4 can easily print to A4 and see how their papers will
% look in print - the typesetting of the document will not typically be
% affected with changes in paper size (but the bottom and side margins will).
% Use the testflow package mentioned above to verify correct handling of
% both paper sizes by the user's LaTeX system.
%
% Also note that the "draftcls" or "draftclsnofoot", not "draft", option
% should be used if it is desired that the figures are to be displayed in
% draft mode.
%
\documentclass[conference]{IEEEtran}
% Add the compsoc option for Computer Society conferences.
%
% If IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it like:
% \documentclass[conference]{../sty/IEEEtran}





% Some very useful LaTeX packages include:
% (uncomment the ones you want to load)


% *** MISC UTILITY PACKAGES ***
%
%\usepackage{ifpdf}
% Heiko Oberdiek's ifpdf.sty is very useful if you need conditional
% compilation based on whether the output is pdf or dvi.
% usage:
% \ifpdf
%   % pdf code
% \else
%   % dvi code
% \fi
% The latest version of ifpdf.sty can be obtained from:
% http://www.ctan.org/tex-archive/macros/latex/contrib/oberdiek/
% Also, note that IEEEtran.cls V1.7 and later provides a builtin
% \ifCLASSINFOpdf conditional that works the same way.
% When switching from latex to pdflatex and vice-versa, the compiler may
% have to be run twice to clear warning/error messages.






% *** CITATION PACKAGES ***
%
%\usepackage{cite}
% cite.sty was written by Donald Arseneau
% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
% \cite{} output to follow that of IEEE. Loading the cite package will
% result in citation numbers being automatically sorted and properly
% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
% \cite will automatically add leading space, if needed. Use cite.sty's
% noadjust option (cite.sty V3.8 and later) if you want to turn this off.
% cite.sty is already installed on most LaTeX systems. Be sure and use
% version 4.0 (2003-05-27) and later if using hyperref.sty. cite.sty does
% not currently provide for hyperlinked citations.
% The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/cite/
% The documentation is contained in the cite.sty file itself.






% *** GRAPHICS RELATED PACKAGES ***
%
\ifCLASSINFOpdf
  % \usepackage[pdftex]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../pdf/}{../jpeg/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\else
  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  % will default to the driver specified in the system graphics.cfg if no
  % driver is specified.
  % \usepackage[dvips]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../eps/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.eps}
\fi
% graphicx was written by David Carlisle and Sebastian Rahtz. It is
% required if you want graphics, photos, etc. graphicx.sty is already
% installed on most LaTeX systems. The latest version and documentation can
% be obtained at: 
% http://www.ctan.org/tex-archive/macros/latex/required/graphics/
% Another good source of documentation is "Using Imported Graphics in
% LaTeX2e" by Keith Reckdahl which can be found as epslatex.ps or
% epslatex.pdf at: http://www.ctan.org/tex-archive/info/
%
% latex, and pdflatex in dvi mode, support graphics in encapsulated
% postscript (.eps) format. pdflatex in pdf mode supports graphics
% in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure
% that all non-photo figures use a vector format (.eps, .pdf, .mps) and
% not a bitmapped formats (.jpeg, .png). IEEE frowns on bitmapped formats
% which can result in "jaggedy"/blurry rendering of lines and letters as
% well as large increases in file sizes.
%
% You can find documentation about the pdfTeX application at:
% http://www.tug.org/applications/pdftex





% *** MATH PACKAGES ***
%
%\usepackage[cmex10]{amsmath}
% A popular package from the American Mathematical Society that provides
% many useful and powerful commands for dealing with mathematics. If using
% it, be sure to load this package with the cmex10 option to ensure that
% only type 1 fonts will utilized at all point sizes. Without this option,
% it is possible that some math symbols, particularly those within
% footnotes, will be rendered in bitmap form which will result in a
% document that can not be IEEE Xplore compliant!
%
% Also, note that the amsmath package sets \interdisplaylinepenalty to 10000
% thus preventing page breaks from occurring within multiline equations. Use:
%\interdisplaylinepenalty=2500
% after loading amsmath to restore such page breaks as IEEEtran.cls normally
% does. amsmath.sty is already installed on most LaTeX systems. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/amslatex/math/





% *** SPECIALIZED LIST PACKAGES ***
%
%\usepackage{algorithmic}
% algorithmic.sty was written by Peter Williams and Rogerio Brito.
% This package provides an algorithmic environment fo describing algorithms.
% You can use the algorithmic environment in-text or within a figure
% environment to provide for a floating algorithm. Do NOT use the algorithm
% floating environment provided by algorithm.sty (by the same authors) or
% algorithm2e.sty (by Christophe Fiorio) as IEEE does not use dedicated
% algorithm float types and packages that provide these will not provide
% correct IEEE style captions. The latest version and documentation of
% algorithmic.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithms/
% There is also a support site at:
% http://algorithms.berlios.de/index.html
% Also of interest may be the (relatively newer and more customizable)
% algorithmicx.sty package by Szasz Janos:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithmicx/




% *** ALIGNMENT PACKAGES ***
%
%\usepackage{array}
% Frank Mittelbach's and David Carlisle's array.sty patches and improves
% the standard LaTeX2e array and tabular environments to provide better
% appearance and additional user controls. As the default LaTeX2e table
% generation code is lacking to the point of almost being broken with
% respect to the quality of the end results, all users are strongly
% advised to use an enhanced (at the very least that provided by array.sty)
% set of table tools. array.sty is already installed on most systems. The
% latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/tools/


%\usepackage{mdwmath}
%\usepackage{mdwtab}
% Also highly recommended is Mark Wooding's extremely powerful MDW tools,
% especially mdwmath.sty and mdwtab.sty which are used to format equations
% and tables, respectively. The MDWtools set is already installed on most
% LaTeX systems. The lastest version and documentation is available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/mdwtools/


% IEEEtran contains the IEEEeqnarray family of commands that can be used to
% generate multiline equations as well as matrices, tables, etc., of high
% quality.


%\usepackage{eqparbox}
% Also of notable interest is Scott Pakin's eqparbox package for creating
% (automatically sized) equal width boxes - aka "natural width parboxes".
% Available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/eqparbox/





% *** SUBFIGURE PACKAGES ***
%\usepackage[tight,footnotesize]{subfigure}
% subfigure.sty was written by Steven Douglas Cochran. This package makes it
% easy to put subfigures in your figures. e.g., "Figure 1a and 1b". For IEEE
% work, it is a good idea to load it with the tight package option to reduce
% the amount of white space around the subfigures. subfigure.sty is already
% installed on most LaTeX systems. The latest version and documentation can
% be obtained at:
% http://www.ctan.org/tex-archive/obsolete/macros/latex/contrib/subfigure/
% subfigure.sty has been superceeded by subfig.sty.



%\usepackage[caption=false]{caption}
%\usepackage[font=footnotesize]{subfig}
% subfig.sty, also written by Steven Douglas Cochran, is the modern
% replacement for subfigure.sty. However, subfig.sty requires and
% automatically loads Axel Sommerfeldt's caption.sty which will override
% IEEEtran.cls handling of captions and this will result in nonIEEE style
% figure/table captions. To prevent this problem, be sure and preload
% caption.sty with its "caption=false" package option. This is will preserve
% IEEEtran.cls handing of captions. Version 1.3 (2005/06/28) and later 
% (recommended due to many improvements over 1.2) of subfig.sty supports
% the caption=false option directly:
%\usepackage[caption=false,font=footnotesize]{subfig}
%
% The latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/subfig/
% The latest version and documentation of caption.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/caption/




% *** FLOAT PACKAGES ***
%
%\usepackage{fixltx2e}
% fixltx2e, the successor to the earlier fix2col.sty, was written by
% Frank Mittelbach and David Carlisle. This package corrects a few problems
% in the LaTeX2e kernel, the most notable of which is that in current
% LaTeX2e releases, the ordering of single and double column floats is not
% guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
% single column figure to be placed prior to an earlier double column
% figure. The latest version and documentation can be found at:
% http://www.ctan.org/tex-archive/macros/latex/base/



%\usepackage{stfloats}
% stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
% the ability to do double column floats at the bottom of the page as well
% as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
% LaTeX2e). It also provides a command:
%\fnbelowfloat
% to enable the placement of footnotes below bottom floats (the standard
% LaTeX2e kernel puts them above bottom floats). This is an invasive package
% which rewrites many portions of the LaTeX2e float routines. It may not work
% with other packages that modify the LaTeX2e float routines. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/sttools/
% Documentation is contained in the stfloats.sty comments as well as in the
% presfull.pdf file. Do not use the stfloats baselinefloat ability as IEEE
% does not allow \baselineskip to stretch. Authors submitting work to the
% IEEE should note that IEEE rarely uses double column equations and
% that authors should try to avoid such use. Do not be tempted to use the
% cuted.sty or midfloat.sty packages (also by Sigitas Tolusis) as IEEE does
% not format its papers in such ways.





% *** PDF, URL AND HYPERLINK PACKAGES ***
%
%\usepackage{url}
% url.sty was written by Donald Arseneau. It provides better support for
% handling and breaking URLs. url.sty is already installed on most LaTeX
% systems. The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/misc/
% Read the url.sty source comments for usage information. Basically,
% \url{my_url_here}.





% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex).         ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.
% (Unless specifically asked to do so by the journal or conference you plan
% to submit to, of course. )


% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}


\begin{document}
%
% paper title
% can use linebreaks \\ within to get better formatting as desired
\title{Bare Demo of IEEEtran.cls for Conferences}


% author names and affiliations
% use a multiple column layout for up to three different
% affiliations
\author{\IEEEauthorblockN{Michael Shell}
\IEEEauthorblockA{School of Electrical and\\Computer Engineering\\
Georgia Institute of Technology\\
Atlanta, Georgia 30332--0250\\
Email: http://www.michaelshell.org/contact.html}
\and
\IEEEauthorblockN{Homer Simpson}
\IEEEauthorblockA{Twentieth Century Fox\\
Springfield, USA\\
Email: homer@thesimpsons.com}
\and
\IEEEauthorblockN{James Kirk\\ and Montgomery Scott}
\IEEEauthorblockA{Starfleet Academy\\
San Francisco, California 96678-2391\\
Telephone: (800) 555--1212\\
Fax: (888) 555--1212}}

% conference papers do not typically use \thanks and this command
% is locked out in conference mode. If really needed, such as for
% the acknowledgment of grants, issue a \IEEEoverridecommandlockouts
% after \documentclass

% for over three affiliations, or if they all won't fit within the width
% of the page, use this alternative format:
% 
%\author{\IEEEauthorblockN{Michael Shell\IEEEauthorrefmark{1},
%Homer Simpson\IEEEauthorrefmark{2},
%James Kirk\IEEEauthorrefmark{3}, 
%Montgomery Scott\IEEEauthorrefmark{3} and
%Eldon Tyrell\IEEEauthorrefmark{4}}
%\IEEEauthorblockA{\IEEEauthorrefmark{1}School of Electrical and Computer Engineering\\
%Georgia Institute of Technology,
%Atlanta, Georgia 30332--0250\\ Email: see http://www.michaelshell.org/contact.html}
%\IEEEauthorblockA{\IEEEauthorrefmark{2}Twentieth Century Fox, Springfield, USA\\
%Email: homer@thesimpsons.com}
%\IEEEauthorblockA{\IEEEauthorrefmark{3}Starfleet Academy, San Francisco, California 96678-2391\\
%Telephone: (800) 555--1212, Fax: (888) 555--1212}
%\IEEEauthorblockA{\IEEEauthorrefmark{4}Tyrell Inc., 123 Replicant Street, Los Angeles, California 90210--4321}}




% use for special paper notices
%\IEEEspecialpapernotice{(Invited Paper)}




% make the title area
\maketitle


\begin{abstract}
%\boldmath
The abstract goes here.
\end{abstract}
% IEEEtran.cls defaults to using nonbold math in the Abstract.
% This preserves the distinction between vectors and scalars. However,
% if the conference you are submitting to favors bold math in the abstract,
% then you can use LaTeX's standard command \boldmath at the very start
% of the abstract to achieve this. Many IEEE journals/conferences frown on
% math in the abstract anyway.

% no keywords




% For peer review papers, you can put extra information on the cover
% page as needed:
% \ifCLASSOPTIONpeerreview
% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
% \fi
%
% For peerreview papers, this IEEEtran command inserts a page break and
% creates the second title. It will be ignored for other modes.
\IEEEpeerreviewmaketitle



\section{Introduction}
% no \IEEEPARstart
This demo file is intended to serve as a ``starter file''
for IEEE conference papers produced under \LaTeX\ using
IEEEtran.cls version 1.7 and later.
% You must have at least 2 lines in the paragraph with the drop letter
% (should never be an issue)
I wish you the best of success.

\hfill mds
 
\hfill January 11, 2007

\subsection{Subsection Heading Here}
Subsection text here.


\subsubsection{Subsubsection Heading Here}
Subsubsection text here.


% An example of a floating figure using the graphicx package.
% Note that \label must occur AFTER (or within) \caption.
% For figures, \caption should occur after the \includegraphics.
% Note that IEEEtran v1.7 and later has special internal code that
% is designed to preserve the operation of \label within \caption
% even when the captionsoff option is in effect. However, because
% of issues like this, it may be the safest practice to put all your
% \label just after \caption rather than within \caption{}.
%
% Reminder: the "draftcls" or "draftclsnofoot", not "draft", class
% option should be used if it is desired that the figures are to be
% displayed while in draft mode.
%
%\begin{figure}[!t]
%\centering
%\includegraphics[width=2.5in]{myfigure}
% where an .eps filename suffix will be assumed under latex, 
% and a .pdf suffix will be assumed for pdflatex; or what has been declared
% via \DeclareGraphicsExtensions.
%\caption{Simulation Results}
%\label{fig_sim}
%\end{figure}

% Note that IEEE typically puts floats only at the top, even when this
% results in a large percentage of a column being occupied by floats.


% An example of a double column floating figure using two subfigures.
% (The subfig.sty package must be loaded for this to work.)
% The subfigure \label commands are set within each subfloat command, the
% \label for the overall figure must come after \caption.
% \hfil must be used as a separator to get equal spacing.
% The subfigure.sty package works much the same way, except \subfigure is
% used instead of \subfloat.
%
%\begin{figure*}[!t]
%\centerline{\subfloat[Case I]\includegraphics[width=2.5in]{subfigcase1}%
%\label{fig_first_case}}
%\hfil
%\subfloat[Case II]{\includegraphics[width=2.5in]{subfigcase2}%
%\label{fig_second_case}}}
%\caption{Simulation results}
%\label{fig_sim}
%\end{figure*}
%
% Note that often IEEE papers with subfigures do not employ subfigure
% captions (using the optional argument to \subfloat), but instead will
% reference/describe all of them (a), (b), etc., within the main caption.


% An example of a floating table. Note that, for IEEE style tables, the 
% \caption command should come BEFORE the table. Table text will default to
% \footnotesize as IEEE normally uses this smaller font for tables.
% The \label must come after \caption as always.
%
%\begin{table}[!t]
%% increase table row spacing, adjust to taste
%\renewcommand{\arraystretch}{1.3}
% if using array.sty, it might be a good idea to tweak the value of
% \extrarowheight as needed to properly center the text within the cells
%\caption{An Example of a Table}
%\label{table_example}
%\centering
%% Some packages, such as MDW tools, offer better commands for making tables
%% than the plain LaTeX2e tabular which is used here.
%\begin{tabular}{|c||c|}
%\hline
%One & Two\\
%\hline
%Three & Four\\
%\hline
%\end{tabular}
%\end{table}


% Note that IEEE does not put floats in the very first column - or typically
% anywhere on the first page for that matter. Also, in-text middle ("here")
% positioning is not used. Most IEEE journals/conferences use top floats
% exclusively. Note that, LaTeX2e, unlike IEEE journals/conferences, places
% footnotes above bottom floats. This can be corrected via the \fnbelowfloat
% command of the stfloats package.



\section{Conclusion}
The conclusion goes here.




% conference papers do not normally have an appendix


% use section* for acknowledgement
\section*{Acknowledgment}


The authors would like to thank...





% trigger a \newpage just before the given reference
% number - used to balance the columns on the last page
% adjust value as needed - may need to be readjusted if
% the document is modified later
%\IEEEtriggeratref{8}
% The "triggered" command can be changed if desired:
%\IEEEtriggercmd{\enlargethispage{-5in}}

% references section

% can use a bibliography generated by BibTeX as a .bbl file
% BibTeX documentation can be easily obtained at:
% http://www.ctan.org/tex-archive/biblio/bibtex/contrib/doc/
% The IEEEtran BibTeX style support page is at:
% http://www.michaelshell.org/tex/ieeetran/bibtex/
%\bibliographystyle{IEEEtran}
% argument is your BibTeX string definitions and bibliography database(s)
%\bibliography{IEEEabrv,../bib/paper}
%
% <OR> manually copy in the resultant .bbl file
% set second argument of \begin to the number of references
% (used to reserve space for the reference number labels box)
\begin{thebibliography}{1}

\bibitem{IEEEhowto:kopka}
H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
  0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.

\end{thebibliography}




% that's all folks
\end{document}



multiBN_arxiv.tex
\documentclass[conference]{IEEEtran}


% *** CITATION PACKAGES ***
%
\usepackage{cite}
% cite.sty was written by Donald Arseneau
% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
% \cite{} output to follow that of IEEE. Loading the cite package will
% result in citation numbers being automatically sorted and properly
% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
% \cite will automatically add leading space, if needed. Use cite.sty's
% noadjust option (cite.sty V3.8 and later) if you want to turn this off.
% cite.sty is already installed on most LaTeX systems. Be sure and use
% version 4.0 (2003-05-27) and later if using hyperref.sty. cite.sty does
% not currently provide for hyperlinked citations.
% The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/cite/
% The documentation is contained in the cite.sty file itself.


% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}


%% My additions
\usepackage{graphicx}
\usepackage{subfig} 
\graphicspath{{images/}}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\providecommand{\st}{\big{|}} % such that
\providecommand{\abs}[1]{|#1|} % set size
\newenvironment{proofsketch}{\trivlist\item[]\emph{Proof Sketch}:}%


 
\begin{document} 
 
 \title{Bayesian Discovery of Multiple Bayesian Networks\\ via Transfer Learning} 

% author names and affiliations
% use a multiple column layout for up to three different
% affiliations
\author{\IEEEauthorblockN{Diane Oyen}
%\IEEEauthorblockA{Computer Science Department}
\IEEEauthorblockA{University of New Mexico}
\IEEEauthorblockA{doyen@cs.unm.edu}
\and
\IEEEauthorblockN{Terran Lane}
\IEEEauthorblockA{Google, Inc}
\IEEEauthorblockA{terran.lane@gmail.com}
}

% conference papers do not typically use \thanks and this command
% is locked out in conference mode. If really needed, such as for
% the acknowledgment of grants, issue a \IEEEoverridecommandlockouts
% after \documentclass

% for over three affiliations, or if they all won't fit within the width
% of the page, use this alternative format:
% 
%\author{\IEEEauthorblockN{Michael Shell\IEEEauthorrefmark{1},
%Homer Simpson\IEEEauthorrefmark{2},
%James Kirk\IEEEauthorrefmark{3}, 
%Montgomery Scott\IEEEauthorrefmark{3} and
%Eldon Tyrell\IEEEauthorrefmark{4}}
%\IEEEauthorblockA{\IEEEauthorrefmark{1}School of Electrical and Computer Engineering\\
%Georgia Institute of Technology,
%Atlanta, Georgia 30332--0250\\ Email: see http://www.michaelshell.org/contact.html}
%\IEEEauthorblockA{\IEEEauthorrefmark{2}Twentieth Century Fox, Springfield, USA\\
%Email: homer@thesimpsons.com}
%\IEEEauthorblockA{\IEEEauthorrefmark{3}Starfleet Academy, San Francisco, California 96678-2391\\
%Telephone: (800) 555--1212, Fax: (888) 555--1212}
%\IEEEauthorblockA{\IEEEauthorrefmark{4}Tyrell Inc., 123 Replicant Street, Los Angeles, California 90210--4321}}




% use for special paper notices
%\IEEEspecialpapernotice{(Invited Paper)}

\maketitle 
 
\begin{abstract} 
Bayesian network structure learning algorithms with limited data are being used in domains such as systems biology and neuroscience to gain insight into the underlying processes that produce observed data. Learning reliable networks from limited data is difficult, therefore transfer learning can improve the robustness of learned networks by leveraging data from related \emph{tasks}. Existing transfer learning algorithms for Bayesian network structure learning give a single maximum a posteriori estimate of network models. Yet, many other models may be equally likely, and so a more informative result is provided by Bayesian structure discovery. Bayesian structure discovery algorithms estimate posterior probabilities of structural features, such as edges. We present transfer learning for Bayesian structure discovery which allows us to explore the shared and unique structural features among related tasks. Efficient computation requires that our transfer learning objective factors into local calculations, which we prove is given by a broad class of transfer biases. Theoretically, we show the efficiency of our approach. Empirically, we show that compared to single task learning, transfer learning is better able to positively identify true edges. We apply the method to whole-brain neuroimaging data.
\end{abstract} 
 
\section{Introduction}

The discovery of structural features in Bayesian networks is of great interest in scientific domains such as bioinformatics and neuroscience. The goal is to understand the relationships among variables in a system, such as genes in a gene expression network or activity levels of regions of the brain in functional brain networks. However, the data collected is often done in several separate but related experiments. Therefore, the full data set is actually composed of several distinct, but related, subsets of data --- called \emph{tasks} in transfer learning. For each task there may not be enough samples to learn a robust model. Transfer learning leverages information among tasks to smooth learned models \cite{thrun_is_1996,caruana_multitask_1997}. These smoothed models tend to be more robust to sample noise and generalize to holdout data better than models learned without transfer. Furthermore, in unsupervised learning, the set of models learned among tasks will share many features in common, easing interpretation of the models. Differences among the learned task-specific models are more likely to be due to real differences in the generating distribution of the data rather than spurious differences \cite{niculescu-mizil_inductive_2007,zhang_multitask_2010}.

Existing transfer Bayesian network learning algorithms have two major limitations: 1) they use \emph{heuristic} search over the space of sets of graphs; and 2) produce a \emph{single} point maximum a posteriori model. Yet, there may be many other solutions of similar likelihood and therefore a point solution will not give a full picture of likely relationships among variables. A point solution can perform well at predicting future data, but it is misleading to present such a solution to the domain expert as the only model that explains the data. Instead, we would like to learn a posterior distribution over solutions and extract meaningful summary statistics about features of interest. Such algorithms exist for learning individual Bayesian networks and are referred to as \emph{network discovery} \cite{friedman_being_2003,Koivisto:2004:EBS:1005332.1005352}. Extending these algorithms for transfer network learning is not trivial, as we explain in the next paragraph.

Algorithms for estimating the posterior probability distribution for a single network generally fall into two categories: those that search over \emph{structure} space and those that search over \emph{order} space. Structure-space algorithms make small local changes to the learned graph structure (typically, the addition, removal or reversal of a single edge). For these small changes, updating the likelihood of the graph, and therefore the posterior distribution, is fast but covering the full space of structures can be slow and can get stuck in local maxima \cite{madigan1995bayesian,grzegorczyk_improving_2008}. Extending those structure-search algorithms to multiple tasks would explode the model search space exponentially, exacerbating convergence issues. On the other hand, order-search algorithms exploit the tractability of calculating posteriors given a fixed ordering of the variables (described in more detail later). Node order dictates which nodes are allowed to be parents to any given node, and therefore changes in node order are more global than structure-space changes. There are relatively efficient algorithms for calculating exact posteriors of structural features \cite{Koivisto:2004:EBS:1005332.1005352,Parviainen:2009:ESD:1795114.1795165} or approximate posteriors \cite{friedman_being_2003,Niinimaki11} that have been shown to be faster than structure-search. However, there is no \emph{structural} prior provided in these order-space formulations; instead there is a prior over orders. We do not want to impose transfer at the level of \emph{orders}, but rather at the level of structures (a particular edge appearing in one task will be preferred in other tasks).

Our main challenge, therefore, is to incorporate a structural bias term into the order-search formulation. With such a bias term, we can impose a transfer bias to learn more robust networks, while leveraging the most efficient Bayesian discovery algorithms that currently exist. Our major contribution is proving that structural bias can be efficiently incorporated into the order-conditioned network discovery formulation. We prove that our transfer formulation factors into local calculations. Thus, we provide the first transfer algorithm that can calculate \emph{exact} posteriors for multiple networks of moderate size. We are also the first to show how transfer can incorporated into state-of-the-art order-search approximation algorithms for larger networks.

%Another limitation of existing transfer Bayesian network learning algorithms is that they require a parameter that controls the strength of transfer among the tasks. Typically, the parameter is tuned using holdout validation data. However, transfer learning is most beneficial when there is limited data. In such cases, we would prefer to use the entire set of data for training rather than having to reserve some data for tuning a parameter. We show that in transfer network discovery we can apply an uninformative prior to this parameter and give a closed-form solution for the Bayesian model average over the parameter.

Our contribution is a proof that structure bias can be efficiently incorporated into order-conditioned Bayesian structure discovery: a necessary requirement for using the efficient algorithms of network discovery \cite{Koivisto:2004:EBS:1005332.1005352, friedman_being_2003}. This is a finding that can impact many structure discovery problems. We give a specific formulation of \emph{multitask} Bayesian network discovery that uses the structure bias to transfer information among tasks. We further show that we can take a Bayesian approach to average over all possible settings of the transfer parameter rather than needing to select this parameter. Empirical results on networks, of size 8 variables and 37 variables, indicate that our transfer approach learns posterior probabilities that are closer to the optimal values than single-task learning algorithms. We apply our multitask algorithm to neuroimaging data with 150 variables and demonstrate that the multitask algorithm produces fewer spurious edges than the non-multitask algorithm while providing more knowledge discovery information than the standard point solution.


\section{Related Work}

Network structure discovery in the face of limited data is an extensively studied problem. With limited data, the posterior probability of even the optimal network may be quite small, however Friedman and Koller (2003) show that the marginal posterior probabilities over subgraphs or structural features can be quite high given the same data \cite{friedman_being_2003}. They propose the so-called order-MCMC algorithm for estimating such posterior probabilities. Koivisto and Sood (2004)  give a dynamic programming method for calculating exact posterior probabilities of network features conditioned on orders \cite{Koivisto:2004:EBS:1005332.1005352}. Further improvements are made to make the approach more memory efficient \cite{Parviainen:2009:ESD:1795114.1795165} and to produce partial-order MCMC  \cite{Niinimaki11}. We show how to extend these single-task learning approaches to the transfer learning problem.

%While much research has been performed in speeding up convergence of these MCMC-based algorithms, there is one limitation that the algorithm itself cannot address. That is the problem of the uncertainty inference of structural features when the size of the training data set is small. Figure~\ref{fig:posteriors}(a) shows the true adjacency matrix for four Bayesian networks where each network has 5 vertices and 5 edges. We can calculate the posterior probability of each possible edge by enumerating all DAGs with 5 vertices and directly calculating the data likelihood of each possible model (this is only feasible for very small networks because the number of DAGs is super-exponential in the number of vertices). Figure~\ref{fig:posteriors} (b) shows the posterior probability of edges for these networks as calculated from a dataset of 2000 samples. We can only identify the true DAG up to Markov equivalence and so there are several false-positive edges appearing in the posteriors, yet there is still a strong pattern of variable independencies encoded in the posteriors. Note that the middle two networks have identical structures but different data samples. The posteriors do not match which shows the effect of sample noise. Figure~\ref{fig:posteriors} (c) shows the same calculation but from a dataset of only 100 samples per network. Clearly, more data is better. This figure shows the algorithm-independent exact posterior distribution from the data. The only way to improve these posterior probabilities is through more data or better priors.

Transfer and multitask learning leverage information among related problems called \emph{tasks} \cite{thrun_is_1996,caruana_multitask_1997}. Formulations for multitask learning of Bayesian networks exist \cite {niculescu-mizil_inductive_2007,oyen_aaai_2012}. Starting from these, we derive an inductive bias toward similar structures among related tasks. However, the solutions to the multitask problems in these papers are found through heuristic search, producing a point estimate rather than a posterior distribution, which we desire. They also require a parameter that determines the strength of transfer bias. %Furthermore, the optimization procedures employed in these papers do not scale to very large numbers of tasks while our approach does.

Another approach to learning Bayesian networks from limited data uses the concept of network discovery with a prior over structures obtained from domain knowledge \cite{grzegorczyk_improving_2008,werhli2007reconstructing}. However, these approaches resort to using MCMC in structure space (rather than order space) to avoid the difficulties in assigning priors conditioned on orders. Furthermore, they do not solve the problem considered here of multiask learning.

\section{Preliminaries}

First, we introduce background information about Bayesian structure discovery for learning a single task and then describe MAP multitask Bayesian network objectives. We combine ideas from both of these approaches to produce Bayesian structure discovery of multitask Bayesian networks.

Bayesian networks compactly describe joint probability distributions by encoding conditional independencies in multivariate data. A Bayesian network $B = \{G, \theta\}$ describes the joint probability distribution over $n$ random variables $\mathbf{X} = [X_1, X_2, \ldots, X_n]$, where $G$ is a directed acyclic graph (DAG) and the conditional probability distributions are parameterized by $\theta$ \cite{heckerman_learning_1995}. An edge $(X_i,X_j)$ in $G$ means that the child $X_j$ is conditionally independent of all non-descendants given its parent $X_i$. The \emph{structure} of the network, $G $, is of particular interest in many domains as it is easy to interpret and gives valuable information about the interaction of variables.

\subsection{Structural Feature Discovery}

Given a limited amount of data, the posterior probability of any network may be quite small. However, summary statistics regarding structural features of networks may have high posterior even with limited data \cite{friedman_being_2003}. Structural features (such as an edge) can be described by an indicator function $f$ such that for $f(G)=1$ the feature exists in graph $G$, otherwise $f(G)=0$. The posterior probability of the feature is equivalent to the expectation of its indicator, $P(f|D) = \sum_G P(G|D) f(G)$. However, this sum can be intractable, as the number of DAGs is super-exponential in the number of variables.

An important insight to making this sum tractable is that we could fix the \emph{order} of the variables. An order, $\prec$, is a permutation on the indices of the variables $X_{\prec(1)}, X_{\prec(2)}, \ldots, X_{\prec(n)}$ such that parents must precede children in the order, i.e. $X_j$ cannot be a parent of $X_i$ if $\prec \!\! (j) \geq\; \prec \!\! (i)$. Given an order, learning optimal parents for each child factors into local calculations, and summing over DAGs consistent with the order is tractable \cite{buntine1991theory,cooper_bayesian_1992}. \cite{friedman_being_2003} condition on a node order, and then obtain the unconditional posterior by summing over orders:
\begin{equation*}
P(f|D) = \frac{1}{P(D)}\sum_\prec P(\! \prec)\! \sum_{G \subseteq \! \prec}\! P(D|G) P(G | \! \prec) f(G)
\end{equation*}
Note that these two formulations for $P(f|D)$ are not the same, as most DAGs, $G$, will be consistent with multiple orders, $\! \prec$. Typically, this formulation produces an acceptable bias in favor of simpler structures.

\cite{Koivisto:2004:EBS:1005332.1005352} give an efficient method for calculating this sum. The approach is rather involved, so we summarize only the key points here. They make several reasonable assumptions, then break the calculation into three steps. First, we describe the modularity assumptions:
\begin{enumerate}
\item \textbf{Parameter modularity}: Modularity of the Bayesian network parameters must also hold, $P(\theta | G) = \prod_{i=1}^n P(\theta_{i,\pi_i} | \pi_i)$ and $P(X = x | G) = \prod_{i=1}^n P(x_i | x_{\pi_i}, \theta_{i, \pi_i})$.

\item \textbf{Structure prior modularity}: The network model prior must be modular so that $P(G, \! \prec) = c \prod_{i=1}^n P(U_i) P(\pi(X_i))$, where $U_i$ is the set of variables preceding $X_i$ in the order $\! \prec$ (potential parents of $X_i$) and $c$ is a normalization constant.

\item \textbf{Feature modularity}: The features must be modular, $f(G) = \prod_{i=1}^n f_i(\pi(X_i))$ where $\pi(X_i)$ is the parent set of variable $i$.
\end{enumerate}

% giving a total computational complexity of $O(n2^n + n^{r+1} C(m))$ for exact computation. The exponential term can be reduced by using MCMC approximation \cite{Niinimaki11}.

%All formulations are written for a single feature, $f$, but we will actually calculate $P(f|D)$ for all features (edges) simultaneously.  

The most common feature to look for is a directed edge $u \rightarrow v$ s.t. $f = 1 \text{ if } X_u \in \pi_v$, which is clearly modular. If these modularity assumptions hold, then the likelihood over order space factors into local calculations as shown in Eq~\ref{eq:modularSTL} \cite{Koivisto:2004:EBS:1005332.1005352}.
\begin{equation}
%P(f|D) &= \sum_G P(G|D) f(G)\\ 
%&= \sum_{\! \prec} P(\! \prec|D) P(f|D,\! \prec)\\
\begin{split}
P(f, D | \! \prec) &= \prod_{i=1}^n \sum_{\pi_i \subseteq U_i}
	P(\pi_i | U_i) P(x_i | \pi_i) f_i(\pi_i)\\
P(f | D) &= \frac{1}{P(D)} \sum_\prec P(\! \prec) P(f, D | \! \prec)\\
\end{split}
\label{eq:modularSTL}
\end{equation}
where $\pi_i = \pi(X_i)$ is the parent set of variable $i$. The unconditional posterior for the features is obtained by summing over orders, using the following steps:
%Using dynamic programming, the computational complexity of summing over $n!$ orders is reduced to $O(n2^n)$ operations. $O(n^{r+1} C(m))$ \cite{Koivisto:2004:EBS:1005332.1005352}. Our goal is to extend such algorithms to the multitask setting with as little increase in computation as possible. As we describe later, we will need to maintain a modular formulation to accomplish this.
\begin{enumerate}
\item Calculate family scores: $\beta_i(\pi_i) = P(\pi_i) P(x_i | \pi_i) f_i(\pi_i)$ for each node $i$ and potential set of parents $\pi_i$. The computational complexity of each of these is some function $C(m)$ of the number of samples $m$. The maximum number of parents allowed for any node is typically fixed to a small natural number, $r$. Therefore, there are $O(N^{r+1})$ of these functions to calculate for a total complexity of $O(N^{r+1} C(m))$.

\item Calculate local contribution of each subset $U \subseteq V - \{i\}$ of potential parents of $i$: $\alpha_i(U) = \sum_{\pi_i \subseteq U} P(\pi_i) P(x_i | \pi_i) f_i(\pi_i)$. Using a truncated fast M\"{o}bius transform and pre-computed $\beta$'s, all of the $\alpha$ functions are computed in $O(n2^n)$ time.

\item Sum over the subset lattice of the various $U_i$ to obtain the sum over orders $\prec$. Using dynamic programming, this sum takes time $O(n2^n)$.
\end{enumerate}
The total computational complexity for a single task is $O(n2^n + n^{r+1}C(m))$. This is the exact calculation of the posterior. For large networks, roughly $n > 30$, the exponential term is intractible. In these cases, MCMC simulations give an approximation to the posterior probability, so that $P(f|D) \approx \frac{1}{T} \sum_{t=1}^T P(\! \prec_t) P(f | D, \! \prec_t)$ for $\! \prec_t$ sampled from order space \cite{friedman_being_2003} or partial orders \cite{Niinimaki11}.
\label{sec:koivistoAlg}

 %Although the number of orders is $N!$ there is no need to enumerate each order explicitly. The potential parents of each node $i$ depend only on the set of parents $U_i$ that precede it, not on the ordering of the parents within $U_i$. 

\subsection{Multitask Bayesian Networks}

Multitask Bayesian network learning leverages knowledge among a set of related tasks by applying a bias toward learning similar networks among the tasks. The underlying assumption is that much of the network is shared among tasks, yet a few differences may exist. By leveraging information among tasks, we can learn more robust networks than would be possible from a single small sample \cite{niculescu-mizil_inductive_2007}. We will apply a similar bias mechanism for network discovery. First we describe the objective function of existing MAP estimate algorithms, which has been shown to be effective at leveraging information. A set of tasks with data sets $D^{(k)}$ and networks $G^{(k)}$ for $k \in \{1,\ldots, K\}$ can be learned by optimizing:
\begin{equation}
\begin{split}
&P(\mathcal{G} | \mathcal{D}) = P(G^{(1)}, \ldots, G^{(K)} | D^{(1)}, \ldots, D^{(K)} ) =  \\
	&P(D^{(1)}, \ldots, D^{(K)} | G^{(1)}, \ldots, G^{(K)}) \frac{P(\mathcal{G})} {P(\mathcal{D})}
\end{split}
\label{eq:posteriorGeneral}
\end{equation}
%Breaking this into independent single-task learning problems (STL) assumes all tasks are independent of each other, which simplifies Eq~\ref{eq:posteriorGeneral} to:
%\begin{equation*}
%P_{\mathit{STL}}(\mathcal{G} | \mathcal{D}) = \prod_{k=1}^K P(D^{(k)} | G^{(k)}) \frac{P(G^{(k)})}{P(D^{(k)})}
%\label{eq:posteriorSTL}
%\end{equation*}
In existing multitask network learning formulations, the joint structure prior, $P(\mathcal{G})$, is used to encode a bias toward similar structures by penalizing differences in network structure among tasks \cite{niculescu-mizil_inductive_2007,oyen_aaai_2012}. We can assume that $P(D^{(k)} | G^{(k)})$ is independent of all other $G^{(i)}$ so Eq~\ref{eq:posteriorGeneral} simplifies and the joint prior over structures can be described by pairwise sharing of information among tasks as in Eq~\ref{eq:posteriorMTL}.
\begin{equation}
\begin{split}
&P_{\mathit{MTL}}(\mathcal{G} | \mathcal{D}, \lambda) = \frac{P(\mathcal{G} | \lambda)}{P(\mathcal{D})} \prod_{k=1}^K P(D^{(k)} | G^{(k)})\\
&P(\mathcal{G} | \lambda) = \frac{1}{Z} \prod_{k=1}^K P(G^{(k)}) \prod_{i=1}^{k-1} \lambda (1 - \lambda)^{\Delta(G^{(k)}, G^{(i)})}
\end{split}
\label{eq:posteriorMTL}
\end{equation}
where $Z$ is a normalization constant and $\Delta$ is any graph distance metric, such as edit distance, that measures the number of structural differences between graphs $G^{(k)}$ and $G^{(i)}$. %Note that $\lambda \in (0, 1]$ where $\lambda = 1$ forces learned structures to be exactly the same (the only non-zero probability is at $\Delta = 0$) and as $\lambda$ approaches $0$ the networks will be learned independently because all values of $\Delta$ will have equal probability.


\section{Multitask Feature Discovery}

In this section, we present our novel Bayesian approach to structure discovery in multitask Bayesian networks. The challenge is finding a way to bias structures to be similar among tasks, like Eq~\ref{eq:posteriorMTL}, while maintaining the efficiency of calculating feature posteriors that factor into local calculations, like Eq~\ref{eq:modularSTL}. First we formulate the problem, describe structural bias terms that are order-modular, provide a Bayesian approach for handling the strength of the bias, and finally describe practical implementation issues.

\subsection{Problem Formulation}

Instead of learning the feature posteriors from a single task-specific data set, we have $K$ tasks from which we will leverage data. We define the indicator $f^{(k)} = f(G^{(k)})$. Our goal is to learn a feature for each task $P(f^{(k)} | D^{(1)}, \ldots, D^{(K)})$ $\forall k \in \{1, \ldots, K\}$. Again, all formulations are written for a single feature (e.g. a directed edge), but calculating them simultaneously (e.g. all edges in a network) takes the same time. To simplify the development of the objective, we will consider, without loss of generality, the case where $K=2$.
\begin{equation}
\begin{split}
P&(f^{(1)} | D^{(1)}, D^{(2)}) = \\
& = \sum_{\prec} P(\prec) \!\!\!\! \sum_{G^{(1)} \subseteq \prec}\!\!\!\! P(G^{(1)} | D^{(1)}, D^{(2)}) f(G^{(1)}) \\
&= \sum_{\prec}  \sum_{G^{(1)} \subseteq \prec} \!\!\!\! f(G^{(1)}) \times \! \left[ \sum_{G^{(2)} \subseteq \prec}\! P(G^{(1)}, G^{(2)} | D^{(1)}, D^{(2)}) \right] \\
&= \frac{1}{P(D^{(1)}, D^{(2)})} \sum_\prec \sum_{G^{(1)} \subseteq \prec}\! f(G^{(1)}) P(D^{(1)} | G^{(1)}) \times \\
	&\left[ \sum_{G^{(2)} \subseteq \prec}\!\!\!\! P(D^{(2)} | G^{(2)}) P(G^{(1)}, G^{(2)}) \right] \\
\end{split}
\label{eq:formulation}
\end{equation}

For the purpose of calculating the transfer bias, we impose the same order, $\prec$, on both tasks, and then marginalize over orders. This restriction makes computation more efficient, and it seems reasonable to bias a feature contingent on a particular ordering toward the evidence from other tasks while they are restricted to the same set of possible graph structures. Rewriting Eq~\ref{eq:formulation} as a joint probability conditioned on an order, we get the following:
\begin{equation}
\begin{split}
P(f^{(1)}&, D^{(1)}, D^{(2)} | \! \prec) = \sum_{G^{(1)} \subseteq \! \prec} \!\!\!\! f(G^{(1)}) P(D^{(1)} | G^{(1)}) \times \\
&\left[\sum_{G^{(2)} \subseteq \! \prec} \!\!\!\! P(D^{(2)} | G^{(2)}) P(G^{(1)}, G^{(2)} | \! \prec) \right]
\end{split}
\label{eq:conditionalPosterior}
\end{equation}
Our formulation imposes a transfer bias at the level of structure, $P(G^{(1)}, G^{(2)} | \! \prec)$, which is more intuitive than at the level of orders. To calculate this sum efficiently, it is necessary to factor it into a product over local sums. We prove that this is indeed possible, for appropriately chosen structure priors. In addition to the modularity assumptions already stated, we impose an additional modularity assumption, which we call Assumption 4) \textbf{Transfer prior modularity}: $P(G^{(1)}, G^{(2)} | \! \prec) = \prod_{i=1}^n P(\pi_i^{(1)}, \pi_i^{(2)} | U_i)$. Examples of priors that obey this assumption are graph distance measures that count the number of edge additions and deletions, so this is a reasonable requirement.

\begin{theorem}
If $G^{(1)}, \ldots, G^{(K)}$ obey the four assumptions of modularity, then
\begin{equation*}
\begin{split}
P(f^{(1)}, \mathcal{D} &| \! \prec)
	= \prod_{i \in V} \sum_{\pi_i^{(1)} \subseteq U_i} 
	f_i(\pi_i^{(1)}) P(x_i^{(1)} | \pi_i^{(1)}) \times \\
& \left[\sum_{\pi_i^{(2)} \subseteq U_i} P(x_i^{(2)} | \pi_i^{(2)}) P(\pi_i^{(1)}, \pi_i^{(2)} | U_i) \right]\\
\end{split}
\end{equation*}
\label{thm:modularObjective}
\end{theorem}
\begin{proofsketch}
Apply the chain rule and marginalize over graph structure to get Eq~\ref{eq:conditionalPosterior}. Use the modularity properties on each term in the product, and notice that the result factors into the desired form.
\begin{equation*}
\begin{split}
P&(f^{(1)}, \mathcal{D} | \! \prec) = 
	\sum_{G^{(1)} \subseteq \! \prec} f(G^{(1)}) P(D^{(1)} | G^{(1)}) \times \\
&\left[ \sum_{G^{(2)} \subseteq \! \prec} P(D^{(2)} | G^{(2)}) P(G^{(1)}, G^{(2)} | \! \prec) \right]\\
= &\sum_{\pi_1^{(1)} \subseteq U_1} \cdots \sum_{\pi_n^{(1)} \subseteq U_n} \prod_{i=1}^n
	\left[ f_i(\pi_i^{(1)}) P(x_i^{(1)} | \pi_i^{(1)}) \right] \times \\
& \left[ \sum_{\pi_1^{(2)} \subseteq U_1} \cdots \sum_{\pi_n^{(2)} \subseteq U_n} \prod_{i=1}^n
	P(x_i^{(2)} | \pi_i^{(2)}) P(\pi_i^{(1)}, \pi_i^{(2)} | U_i) \right] \\
\end{split}
\end{equation*}
\end{proofsketch}

The details of the proof are straightforward, yet space consuming, and so are omitted. See \cite{Koivisto:2004:EBS:1005332.1005352} for a similar proof.

\subsection{Computational Complexity}
\label{sec:complexity}

The power of Theorem~\ref{thm:modularObjective} is the computational savings that we gain. Using the factored posterior, we only need to change Step 1 of the order-space algorithm outlined in Section~\ref{sec:koivistoAlg}, the calculation of the family scores. The transfer-biased family scores are calculated as:
\begin{equation}
\begin{split}
\beta_{ki}(\pi_i) &= f_i(\pi_i^{(k)}) P(x_i^{(k)} | \pi_i^{(k)}) P(\pi_i^{(k)}, \pi_i^{(j)})\\
	&= f_i(\pi_i^{(k)}) P(x_i^{(k)} | \pi_i^{(k)}) \times \\
	&\left[\sum_{j \neq k} \sum_{\pi_i^{(j)} \subseteq U_i} P(x_i^{(j)} | \pi_i^{(j)}) 
	P(\pi_i^{(k)}, \pi_i^{(j)}) \right]
\end{split}
\end{equation}
There are now $Kn^{r+1}$ of these families to calculate and each one has a sum over $O(Kn^r)$ terms. The computational complexity increases from the single-task time of $O(n^{r+1} C(m))$ to $O(K^2 n^{2r+1} C(m))$. Steps 2 and 3 remain unchanged with an exponential complexity that can be reduced through MCMC approximation.

Even the polynomial term becomes unmanageable for networks with more than 30 or so nodes and must be approximated. We note that in many cases the family scores $P(x_i^{(j)} | \pi_i^{(j)})$ are exponentially larger for some $\pi_i^{(j)} \subseteq U_i$ than others. Therefore, we can use a simple approximation by summing over only the most likely parent sets. While calculating the family scores, we create a set of the highest-scoring families, called set $\mathcal{H}_i^{(k)}$ for each node in each task. To populate this set, we simply include $h$ parent sets that give the highest $P(x_i^{(k)} | \pi_i^{(k)})$, for some constant $h$. Then we use the approximate structural prior:
\begin{equation*}
P_i(\pi_i^{(k)}) \approx \sum_{\pi_i^{(j)} \in \mathcal{H}_i^{(j)}} P(x_i^{(j)} | \pi_i^{(j)}) P(\pi_i^{(k)}, \pi_i^{(j)} | U_i)
\end{equation*}


\subsection{Transfer via Structure Bias}

Now that we know we can incorporate transfer bias, we need to select a modular bias term that transfers knowledge among tasks. The MAP multitask algorithms use a penalty on the number of differences between tasks using a graph distance function. In that case, the number of edges that must be added, deleted, or reversed to edit one graph into the other is penalized. Due to our modularity constraint, our transfer bias must be defined as a function on pairs of parent sets $(\pi_i^{(k)}, \pi_i^{(j)})$, rather than graphs. We choose to penalize the number of edge additions which breaks down into local calculations: the number of parents present in $\pi_i^{(k)}$ that are not present in $\pi_i^{(j)}$. In other words, the size of the set difference $\Delta_{ikj} = \abs{\pi_i^{(k)} \setminus \pi_i^{(j)}}$ will be biased toward small values. To encourage the number of differences to be small, we apply a penalty in the form of a geometric distribution,
\begin{equation}
P(\pi_i^{(k)}, \pi_i^{(j)} | U_i, \lambda) = \frac{1}{Z} (1-\lambda) ^ {\Delta_{ikj}}
\label{eq:structurePrior}
\end{equation}
Calculation of the normalization constant requires summing over an exponential number of possible combinations of parent sets $(\pi_i^{(k)}, \pi_i^{(j)})$. However, we found show how to simplify the sum into an easy closed form. We employ a shortcut by noting that there are a finite number of values that $\Delta_{ikj}$ can take and we find a closed form for calculating the number of parent-set combinations that produce each value of $\Delta_{ikj}$. 
\begin{equation}
\begin{split}
Z &= \sum_{\pi_i^{(k)} \subseteq U_i} \sum_{\pi_i^{(j)} \subseteq U_i} (1-\lambda)^{\Delta_{ikj}} \\
	&= (4 - \lambda)^{\abs{ U_i }} \\
\end{split}
\label{eq:structurePriorNorm}
\end{equation}
Here we give a sketch of the derivation of Eq~\ref{eq:structurePriorNorm}. First, we simplify the inner sum by fixing parent set $\pi_i^{(1)}$ and counting how many parent sets $\pi_i^{(2)}$ will give $\Delta_{ikj} = 0$ ($\pi_i^{(2)}$ can contain any parents from the set $\{U_i \setminus \pi_i^{(1)}\}$ but \emph{none} from $\pi_i^{(1)}$); then how many $\pi_i^{(2)}$ will give $\Delta_{ikj} = 1$ ($\pi_i^{(2)}$ can contain any parents from the set $\{U_i \setminus \pi_i^{(1)}\}$ and \emph{exactly one} from $\pi_i^{(1)}$); etc, up to the maximum of $\Delta_{ikj} = \abs{\pi_i^{(1)}}$. This sum turns out to be a binomial expansion, and so we can write it in closed form. Next, we perform a similar expansion of the outer sum over parent sets $\pi_i^{(1)}$ that have size $\abs{\pi_i^{(1)}} = 0$, and $\abs{\pi_i^{(1)}} = 1$, etc up to the maximum $\abs{\pi_i^{(1)}} = \abs{U_i}$. This sum also turns out to be a binomial expansion and therefore can be simplified into a closed form.\footnote{Algebraic details of this calculation are space consuming and can be supplied in an online supplement.}

Plugging Eq~\ref{eq:structurePriorNorm} into Eq~\ref{eq:structurePrior} gives the structure prior:
\begin{equation}
\begin{split}
P(\pi_i^{(k)}, \pi_i^{(j)} | U_i, \lambda) &=  \frac{(1-\lambda) ^ {\Delta_{ikj}}} {(4 - \lambda)^{\abs{U_i}}} \\
\end{split}
\end{equation}
The parameter $\lambda$, $0 \leq \lambda \leq 1$, controls the strength of transfer bias. When $\lambda = 0$, the prior becomes uniform and therefore there is no transfer. When $\lambda = 1$, the prior is non-zero only when no edge additions occur, and therefore the only parents that are allowed are those that are likely in the other tasks. 


\subsection{Bayesian Model Averaging}

We have just introduced an additional parameter, $\lambda$, which is a bit of a nuisance. Existing MAP algorithms cannot avoid dealing with this, and they typically estimate $\lambda$ by optimizing over a held out validation set. This is computationally expensive and reduces the amount of available data for training. Rather than selecting a fixed value for $\lambda$, we perform Bayesian model averaging over all possible values of $\lambda$. This Bayesian approach is compelling as the true amount of similarity among tasks is unknown, and the ``true" value of $\lambda$ is only incidental to our objective of learning the structure likelihoods. Furthermore, it saves us the computation of running the algorithm for several values of $\lambda$, and we do not need to hold-out data for tuning.

We set an uninformative uniform prior, $p(\lambda | U_i) = 1$ for $0 \leq \lambda \leq 1$, and  marginalize over $\lambda$.
\begin{equation}
\begin{split}
P(\pi_i^{(k)}, \pi_i^{(j)} | U_i) &=  \int_0^1 P(\pi_i^{(k)}, \pi_i^{(j)} | U_i, \lambda) p(\lambda | U_i) d\lambda \\
&=  \int_0^1 \frac{(1-\lambda) ^ { \Delta_{ikj}}} {(4 - \lambda)^{\abs{U_i}}} d\lambda \\
&= \frac{_2\text{F}_1(\abs{U_i}, 1; \Delta_{ikj}+2; 1/4)}{4^{\abs{U_i}} (\Delta_{ikj} + 1)}\\
\end{split}
\label{eq:biasTerm}
\end{equation}
where $_2\text{F}_1$ is the ordinary hypergeometric function:
\begin{equation*}
\begin{split}
_2\text{F}&_1(\abs{U_i}, 1; \Delta_{ikj}+2; 1/4) = \\
 & \sum_{n=0}^\infty \frac{\Gamma(1+n)}{\Gamma(1)} \cdot
	\frac{\Gamma(\abs{U_i} + n)}{\Gamma(\abs{U_i})}  \cdot
	\frac{\Gamma(\Delta_{ikj} + 2)}{\Gamma(\Delta_{ikj} + 2 + n)}  \cdot \frac{1}{4^nn!} \\
\end{split}
\end{equation*}

The last step in Eq~\ref{eq:biasTerm} is obtained by applying an identity given by Euler in 1748 \cite{Bailey1935Generalised-Hyp}. If $\beta$ is the beta function and $_2\text{F}_1$ is the ordinary hypergeometric function, then
\begin{equation*}
\begin{split}
\int_0^1 x^{b-1}(1-x)^{c-b-1}&(1-zx)^{-a} dx = \\
&\beta(b, c-b) _2\text{F}_1 (a, b; c; z)
\end{split}
\end{equation*}
for $\Re(c) > \Re(b) > 0$. We let $x = \lambda$, $a = \abs{U_i}$, $b = 1$, $c = \Delta_{ikj} + 2$, and $z = 1/4$. Then the condition, $\Delta_{ikj} + 2 > 1 > 0$, holds for any $\Delta_{ikj} \geq 0$ which is the valid range for $\Delta_{ikj}$. Plugging these values into the identity gives the solution to the integral as:
\begin{equation*}
\beta(1, \Delta_{ikj} + 1) _2\text{F}_1 (\abs{U_i}, 1; \Delta_{ikj} + 2; 1/4)
\end{equation*}
which simplies to the solution given in Eq~\ref{eq:biasTerm}.



We are only interested in calculating $_2\text{F}_1$ for combinations of integer-values of $\Delta_{ikj}$ and $\abs{U_i}$ for $0 \leq \Delta_{ikj} \leq \abs{U_i} < n$. For these values, $_2\text{F}_1$ is convergent and efficient solvers exist. Thus, we can plug the result of Eq~\ref{eq:biasTerm} into the equation of Theorem~\ref{thm:modularObjective}.

Bayesian model averaging is made possible by conditioning on orders. Existing multitask network learning algorithms that search in DAG space \cite{niculescu-mizil_inductive_2007,oyen_aaai_2012} would be required to calculate a normalization constant like that in Eq~\ref{eq:structurePriorNorm} but with sums over all possible DAGs, and no closed form has been found for such a sum.

\begin{figure}[tb]
\centering
\includegraphics[width=0.6\columnwidth]{largeSampleTo5k.pdf}
\caption{Posterior probability estimate for each edge in the \textit{asia} network from various large sample sets (means calculated from 20 sample sets). Blue curves are true edges, green are reverse of a true edge, pink are non-edges. (Best viewed in color.)}
\label{fig:asiaLargeSamp}
\end{figure}

\section{Experiments}

Multitask learning should be able to identify true edges and non-edges with less data than is possible with traditional single-task learning. We compare our MTL structure discovery algorithm against two baselines. The first baseline is single-task learning (STL), where each network is learned independently of the other tasks. The other baseline (POOL) takes the opposite extreme by pooling data from all tasks together and treating it as a single task. POOL uses the strongest leveraging of data among tasks possible and so it should perform best if the separate tasks are actually the same distribution.  For all approaches, we use the BeanDisco implementation for exact and approximate network discovery \cite{Niinimaki11}. For MTL, the scoring function of BeanDisco is modified as described above. For POOL, the data are merged before applying the algorithm. %We also impose a limit on the size of parent sets, as described for each data set.


\subsection{Benchmark Data}

\begin{figure*}[htb]
\centering
\subfloat[STL]
	{\includegraphics[width=0.32\textwidth]{pedge_STL_pdel01_task2.pdf}
	\label{fig:asiaPedgeSTL}}
	\hfil
\subfloat[MTL]
	{\includegraphics[width=0.32\textwidth]{pedge_MTL_with_legend-crop.pdf}
	\label{fig:asiaPedgeMTL}}
	\hfil
\subfloat[POOL]
	{\includegraphics[width=0.32\textwidth]{pedge_POOL_pdel01_task2.pdf}
	\label{fig:asiaPedgePOOL}}
\caption{Example posterior probability estimate for each edge in a modified \textit{asia} network from various small sample sets (means calculated from 20 sample sets). Up is good for blue and cyan curves. Down is good for red and green curves.}
\label{fig:asiaPedge}
\end{figure*}

Synthetic data is generated from benchmark Bayesian networks, \textit{asia} which has 8 variables \cite{lauritzen1988local} and \textit{alarm} which has 37 variables \cite{beinlich89alarm}. Even when the generative model is known, it is not obvious how to measure the performance of a network discovery algorithm. To give a clear picture of our objective, see Figure~\ref{fig:asiaLargeSamp}. On the small \textit{asia} network we can calculate the true posterior likelihoods of structural features given the data. Sample noise affects the true posterior likelihood of structural features but the posteriors appear to stabilize for large training sets. Even so, one edge has been consistently identified in the reverse direction of the true edge and another true edge represents such a subtle dependency that it is not discernible from this amount of data. Therefore, we use the posterior estimates from large training sets as our ground truth $P^*(f|D)$. In the case of \emph{asia}, $P^*(f|D) = \hat{P}_{\mathit{STL}}(f|D_{5000})$.


We need a set of related networks and so we modify some structures of the given benchmark network to create similar but different networks. We delete each edge with some probability $p_{\mathit{del}}$ and vary $p_{\mathit{del}}$ from 0.1 to 0.5 to create sets of networks with more or less features in common for various experiments. If an edge is deleted, the conditional probability table for the child of the deleted edge is updated by marginalizing over the deleted parent. In our experiments, the full generative model is repeated 10 times to produce 10 different sets of $K$ networks each for a given $p_{\mathit{del}}$.


\subsection{Benchmark Results}

The goal of transfer learning is to accelerate the learning curve at smaller training set sizes by leveraging data among similar tasks. If we look closely at the results for one particular modified \textit{asia} network, we can see what effect multitask learning has. Figure~\ref{fig:asiaPedgeSTL} shows the estimated posteriors from STL at smaller sample sizes. Even at these small sample sizes, the posteriors of the true edges tend to be higher than those of non-edges. However, compared to the estimates from large samples, these posteriors exhibit high variance and many are quite far from the large-sample posterior value (in the figure, error bars omitted for readability). The question is whether multitask learning can produce a steeper learning curve.

Figure~\ref{fig:asiaPedgeMTL} shows the learning curve achieved by MTL on the same network, using data leveraged from one other task, where some but not all edges are in common between the two tasks. This learning curve shows a wider gap between the estimated values of true edges and non-edges. In that sense, the learning curve is better than STL because it is better at separating the true edges from the non-edges at smaller training set sizes. In particular, this gain is achieved through the lower estimates of non-edges. In other words, non-edges are more quickly identified as such through transfer learning than without. On the other hand, the raw estimates of true edges tend to have such high variance (both with STL and with MTL) that it is not possible to say that one algorithm is doing better than the other in terms of converging on the actual $P^*(f|D)$. 

Figure~\ref{fig:asiaPedgePOOL} shows the learning curve obtained by POOL on the same modified \textit{asia} network. POOL combined the data from two modified networks with some edges in common. The algorithm effectively has twice as much data to work with as STL, therefore the learning curves are steeper. Yet there are quite a few non-edges with high posterior values.

\begin{table}[tb]
\centering
\caption{Performance increase for \emph{asia} in terms of AUC given by MTL vs STL and MTL vs POOL}
\label{table:auc}
\begin{footnotesize}
\begin{tabular}{c || r | c || r | c}
  Training & \multicolumn{2}{c||}{MTL vs STL} & \multicolumn{2}{c}{MTL vs POOL} \\
  samples & \% incr & pair-t & \% incr & pair-t \\
  \hline
  5 & 3.06 & - & 10.72 & MTL \\
  10 & 9.02 & MTL & 4.10 & - \\
  20 & 4.90 & MTL & 0.34 & - \\
  30 & 4.98 & MTL & 0.85 & - \\
  40 & 7.60 & MTL & 3.66 & - \\
  50 & 3.00 & MTL & 3.08 & MTL \\
  100 &  1.97 & MTL & 2.96 & MTL \\
  200 & 0.53 & - & 2.82 & MTL \\
  400 & 0.14 & - & 4.14 & MTL \\
  500 & -0.03 & - & 3.72 & MTL \\
 \end{tabular}
 \end{footnotesize}
\end{table}

\begin{figure}[tb]
\centering
\subfloat[10 samples per task]
	{\includegraphics[width=0.48\columnwidth]{roc_asia_thres_pdel03_samp10.pdf}
	\label{fig:asiaRoc10}}
	\hfil
%\subfloat[30 training samples per task]
%	{\includegraphics[width=0.32\textwidth]{roc_asia_thres_pdel03_samp30.pdf}
%	\label{fig:asiaRoc30}}
%	\hfil
\subfloat[50 samples per task]
	{\includegraphics[width=0.48\columnwidth]{roc_asia_thres_pdel03_samp50.pdf}
	\label{fig:asiaRoc50}}
\caption{ROC curves for \textit{asia}. Each point is the (FP rate, TP rate) aggregated over 2 tasks and 10 trials of the generative model, for a particular value of $\tau$. Arrow indicates where STL and POOL curves cross.}
\label{fig:asiaRoc}
\end{figure}

To quantify these results, we measure how well the estimates for true edges separate from the estimates for non-edges. There is potentially a directed edge between each ordered pair of nodes. We call this set of potential edges $E$. We quantify the ground truth using the $P^*(f|D)$ values obtained from large samples and identify the set of ``true" edges $E^* = \{f \in E \: | \: P^*(f|D) > 0.5\}$. %We are interested in looking at how well the estimates for the non-edges $E_{\mathit{non}} = \{E \setminus E^*\}$ separate from $E^*$. 

%To do this, first we show the average of $\hat{P}_M(f|D)$ for each $f \in E_{\mathit{non}}$ for each learning method $M$ over all tasks of all sets of generative models, for various amounts of data and various values of $p_\mathit{del}$. For these non-edges, the best estimate is close to zero, so down is good. We see that the estimates for MTL are consistently lower than STL and POOL for small sample sets, Figure~\ref{NOTE:needFigure}. The primary benefit of MTL stems from this observation. It is better at identifying the non-edges and therefore it is easier to determine which of the edges are true edges, even if the estimated posteriors of those edges are arbitrarily far from the ground truth $P^*(f|D)$.


To differentiate learned edges from learned non-edges, we assign a threshold $\tau$ and call any feature an edge if its posterior is greater than the threshold, $\hat{E} = \{f \in E | \hat{P}(f|D) > \tau\}$. By varying $\tau$, $0\leq \tau \leq 1$, we can investigate the tradeoff between the rates of true-positives (TP) and false-positives (FP) in $\hat{E}$ by constructing an ROC curve (Figure~\ref{fig:asiaRoc}). The TP rate is $\abs{\hat{E} \cap E^*} / \abs{\hat{E}}$. The FP rate is $\abs{\hat{E} \setminus E^*} / (\abs{E} - \abs{\hat{E}})$.



Figure~\ref{fig:asiaRoc} shows that various algorithms have different strengths along the ROC curve. The ROC shows that the patterns indicated in Figure~\ref{fig:asiaPedge} are borne out more generally; that is, STL is slowest to positively identify true edges, while POOL has difficulty eliminating false positives. MTL achieves the greatest overall separation of true edges and non-edges. Initially, at the left end of the ROC curve, with low false positive rates both MTL and STL perform best, finding more true positives than POOL. However, the performance of STL falls off as the false positive rate increases: STL is missing some true positives that both MTL and POOL are able to identify. MTL gives us the best of both worlds, giving the best overall performance.

\begin{figure*}[tb]
\centering
\subfloat[STL]
	{\includegraphics[width=0.32\textwidth]{pedge_small_alarm_STL_pdel05_fold7_task1.pdf}
	\label{fig:alarmPedgeSTL}}
	\hfil
\subfloat[MTL]
	{\includegraphics[width=0.32\textwidth]{pedge_small_alarm_MTL_pdel05_fold7_task1.pdf}
	\label{fig:alarmPedgeMTL}}
	\hfil
\subfloat[POOL]
	{\includegraphics[width=0.32\textwidth]{pedge_small_alarm_POOL_pdel05_fold7_task1.pdf}
	\label{fig:alarmPedgePOOL}}
\caption{Example posterior probability estimate for each edge in a modified \textit{alarm} network from various small sample sets (means calculated from 20 sample sets). Blue curves are true edges shared by both tasks, cyan curves are true edges unique to this task, green are reverse of a true edge, red are non-edges. Up is good for blue and cyan curves. Down is good for red and green curves.}
\label{fig:alarmPedge}
\end{figure*}

Area under the curve (AUC) summarizes the overall performance along the ROC curve. We report AUC for various amounts of training data in Table~\ref{table:auc} across 30 trials of the generative model. With these small training sets, the difficulty of the problem presented by each trial can vary quite a bit, therefore, the performance of each algorithm is compared directly on each trial by looking at how much greater the AUC is for MTL than the other algorithm. This increase in AUC score per trial is then averaged over all trials to give the numbers in Table~\ref{table:auc}. Furthermore, a paired-T test is performed to determine whether this increase in performance is significant at the 5\% confidence level. The winner of the paired-T test is given in Table~\ref{table:auc}.

Similar experiments are performed on the larger \textit{alarm} network. This network is too large for exact posterior computation, therefore we use MCMC approximation. We set MCMC hyper-parameters as recommended by \cite{Niinimaki11}, specifically, bucket size = 10, burn-in samples = 1000, sub-sample interval = 10 and total samples = 100. We tried other values (notably more samples, larger sub-sample interval, and longer burn-in) and found that they give nearly the same results. We also use the transfer approximation described in Section~\ref{sec:complexity}, with $h = 1000$. For the ground truth \textit{alarm} network, we use 10,000 training samples to estimate the true posterior of each feature, $P^*(f|D) = \hat{P}_{\mathit{STL}}(f|D_{10,000})$.


\begin{table}[tb]
\centering
\caption{Performance increase on \emph{alarm} for AUC given by MTL versus STL and MTL versus POOL}
\label{table:aucAlarm}
\begin{footnotesize}
\begin{tabular}{c || r | c || r | c}
  Training & \multicolumn{2}{c||}{MTL vs STL} & \multicolumn{2}{c}{MTL vs POOL} \\
  samples & \% incr & pair-t & \% incr & pair-t \\
  \hline
  25 & -0.12 & - & 0.04 & - \\
  50 & 0.29 & MTL & 1.76 & MTL \\
  75 & 0.43 & MTL & 3.63 & MTL \\
  100 & 0.67 & MTL & 4.49 & MTL \\
  200 & 0.05 & - & 5.19 & MTL \\
  300 & -0.07 & - & 8.68 & MTL \\
  400 &  -0.03 & - & 8.85 & MTL \\
  500 & -0.46 & STL & 10.45 & MTL \\
\end{tabular}
\end{footnotesize}
\end{table}

\begin{figure}[tb]
\centering
\subfloat[50 samples per task]
	{\includegraphics[width=0.48\columnwidth]{roc_alarm_thres_pdel05_samp50.pdf}
	\label{fig:alarmRoc50}}
	\hfil
%\subfloat[75 training samples per task]
%	{\includegraphics[width=0.32\textwidth]{roc_alarm_thres_pdel05_samp75.pdf}
%	\label{fig:alarmRoc75}}
%	\hfil
\subfloat[100 samples per task]
	{\includegraphics[width=0.48\columnwidth]{roc_alarm_thres_pdel05_samp100.pdf}
	\label{fig:alarmRoc100}}
\caption{Example ROC curves for \textit{alarm} data. Each point represents the (FP rate, TP rate) aggregated over 2 tasks and 10 trials of the generative model, for a particular value of $\tau$.}
\label{fig:alarmRoc}
\end{figure}

The alarm network contains 37 variables, therefore there are 1,332 ordered pairs of nodes or potential edges in the set $E$. Of these, only 46 are true edges. We see again that on this data set, MTL estimates lower posteriors for the non-edges than STL or POOL (see Figure~\ref{fig:alarmPedge}). The ROC curves in Figure~\ref{fig:alarmRoc} show that POOL routinely identifies many false positives. The curves for MTL and STL are closer, but again MTL is better at reducing the number of false positives. This makes differentiating the true edges from the false edges easier at small training set sizes, see Table~\ref{table:aucAlarm} for AUC results. MTL dominates STL for small training sets. MTL dominates POOL at all training set sizes.

%\subsection{fMRI Data}

%We are interested in learning the functional brain networks for multiple subjects imaged during multiple sessions of stimuli. We treat this as a multitask network structure discovery problem by treating each subject as a separate task. Four subjects are presented 12 runs of stimuli each \cite{Clark2012TDCS-guided-usi}. The imaging data were parcellated according to the AAL atlas in MNI space \cite{mni_aal_tzourio_2002}. 

%We would expect that the functional brain network of the same subject on different runs would be more similar than the functional brain network of different subjects on different runs. We measure the quality of the structural features learned by measuring the variance of the learned estimates on bootstrapped data.

%\subsection{fMRI Results}

%\begin{figure}[h]
%\centering
%\includegraphics[width=0.8\columnwidth]{graphviz.pdf}
%\caption{fMRI results: Example learned network from for one subject on one run (edges are $f>0.5$).}
%\label{fig:darpa_lambda}
%\end{figure}

\section{Application to Neuroimaging}

Our goal is to find functional brain networks associated with schizophrenia. We start with functional magnetic resonance image (fMRI) data that measure the activity levels in regions of interest (ROI) in the brain. The activity level for each ROI is de-trended using a sliding window mean and then discretized into four levels representing Very Low, Low, High and Very High activity levels (relative to the mean activity level of that ROI). The functional brain network is modeled as a Bayesian network of information sharing using a multinomial of discretized activity level among ROIs. Data has been collected from 86 healthy control subjects (\emph{controls}) and 74 schizophrenia patients (\emph{patients}). For each subject, there are 384 full-brain scans which are the samples in our training data. Brain images are parcellated using the Talaraich atlas giving 150 ROIs. Therefore, for each subject, we have a $150 \times 384$ data matrix. We concatenate the data from several subjects to create the training data for each task. We apply both our MTL algorithm and the standard STL Bayesian structure discovery algorithm. As our goal is to identify different structures between tasks, we do not use the POOL method that learns identical structures for both tasks.

The number of subjects in this study is much larger than in many other studies that we are interested in. We would like to learn reliable networks from small studies, and so we sub-sample the subjects in this study to see how consistent our results are across subsets of subjects. For evaluation purposes, we use the full set of data (86 controls and 74 patients) to learn a large-sample model and use this learned model as the ground truth to measure the small-sample results against. The results show how well learned models over various subsets of subjects are representative of the larger \emph{control} and \emph{patient} populations.

We limit the size of the parent sets to $r = 2$. With this setting, the time to calculate family scores is approximately 3 hours. For MTL family score calculation, we use the approximation method described in Section~\ref{sec:complexity} with $h = $10,000. MCMC approximation is used to estimate the posterior likelihood of edges \cite{Niinimaki11}, with hyper-parameters bucket size = 10, burn-in samples = 5000, sub-sample interval = 10 and total samples = 1000.

\subsection{Small Samples}

\begin{figure}[tb]
\centering
\subfloat[Non-edges]
	{\includegraphics[width=0.48\columnwidth,bb=56 205 524 568]{nonEdgeMCIC.pdf}
	\label{fig:mcicNonedges}}
	\hfil
\subfloat[True edges]
	{\includegraphics[width=0.48\columnwidth,bb=56 205 524 568]{trueEdgeMCIC.pdf}
	\label{fig:mcicTrueEdges}}
\caption{Estimated posterior of features from small subsets of subjects. Points are perturbed horizontally for visibility.}
\label{fig:mcicPedge}
\end{figure}

MTL estimates significantly lower posterior likelihoods on non-edges compared to STL. Evaluating results on real data is complicated by the fact that we do not have ground truth of known networks. Thereroe, we looked at the trend of estimates on smaller subset of the subjects and compare the results against the STL estimate from the full set of data. Figure~\ref{fig:mcicNonedges} shows that for edges that are \emph{not} determined to have real dependencies in the full data set (i.e. non-edges), the posterior estimate is significantly lower for MTL than STL. Significance was determined via a paired-t test at the 95\% confidence level over various subsets of subjects selected. Figure~\ref{fig:mcicTrueEdges} shows that there is no difference between MTL and STL in terms of the posterior estimate of true edges (according to paired-t test at 95\% confidence). Therefore, MTL is able to eliminate the non-edges with less data than STL, corroborating results from the benchmark (\emph{asia} and \emph{alarm}) networks.


\subsection{Learned Dependencies}

\begin{figure*}[tb]
\centering
\subfloat[Patient, 5 subjects]
	{\includegraphics[width=0.32\textwidth]{meanEdgeSchizo5.pdf}
	\label{fig:mcicPatient5}}
	\hfil
\subfloat[Patient, 20 subjects]
	{\includegraphics[width=0.32\textwidth]{meanEdgeSchizo20.pdf}
	\label{fig:mcicPatient20}}
	\hfil
\subfloat[Patient, 74 subjects]
	{\includegraphics[width=0.32\textwidth]{edgeAllDataSchizo.pdf}
	\label{fig:mcicPatientAll}}
	\\
\subfloat[Control, 5 subjects]
	{\includegraphics[width=0.32\textwidth]{meanEdgeControl5.pdf}
	\label{fig:mcicControl5}}
	\hfil
\subfloat[Control, 20 subjects]
	{\includegraphics[width=0.32\textwidth]{meanEdgeControl20.pdf}
	\label{fig:mcicControl20}}
	\hfil
\subfloat[Control, 86 subjects]
	{\includegraphics[width=0.32\textwidth]{edgeAllDataControl.pdf}
	\label{fig:mcicControlAll}}
\caption{Posterior probability estimates for each edge learned from neuroimage data. Means calculated from 10 sample sets.}
\label{fig:mcicPedge}
\end{figure*}

In practice, rather than giving a complete network as a solution to the neuroscientists, the solution is presented as a list of likely dependencies or visualized using network layout software with edge thicknesses proportional to the probability of the dependency. The functional brain networks learned in this paper are large enough the static images are difficult to read. In this paper, we are more concerned with the robustness of learned models rather than the brain networks themselves; therefore, we display the edge likelihoods as an adjacency matrix. Figure~\ref{fig:mcicPedge} shows the mean of the posterior likelihoods across the 10 bootstrap samples of sets of subjects. High probability edges are black squares in the heatmaps. In this experiment, we see that overall the edge likelihoods learned are sparse and they are fairly consistent across subsets of subjects. The likelihoods become ``sharper" (closer to 0 or 1) as the amount of data increases, as expected. However, even for small numbers of subjects, we find clear patterns emerging. We also see that many dependencies are common to both the \emph{control} and \emph{patient} groups of subjects, while a few distinct differences are also visible. Through this type of visualization, a domain expert can gain insight into the possible interactions among variables in the system. The weight of the likelihood of each edge is important information to the domain scientist, which is not available from maximum a posterior multitask learning algorithms.


\section{Discussion}

Our structure bias in the order-modular framework for Bayesian network structure discovery can be applied to many other problems currently being researched. In this paper, we demonstrate the application of structural bias to the problem of multitask learning. We find promising results from our approach and expect that further improvements can be made by tailoring the bias term to the application. Additionally, more sophisticated methods for approximating the transfer bias on large networks could be explored.

Implementation of a structural bias in Bayesian structure discovery is critical for solving other problems as well. \cite{grzegorczyk_improving_2008} propose incorporating prior knowledge about biological networks in the form of a structural feature bias. Rather than using the exact calculation of posteriors that are possible when conditioning on orders, they attempt to find a different MCMC method for approximation. Their motivation was that it is inconvenient to define priors in the space of orders rather than structure. Our Theorem~\ref{thm:modularObjective} shows that it is indeed possible to define structural priors at the structure level to use the efficient algorithms that rely on conditioning on orders.

This structural bias term could also be used to transfer knowledge about the direction of Bayesian network edges from interventional experiments \cite{cooper_causal_1999}. Active learning of Bayesian network structure has been shown to significantly speed the learning of edges, particularly for getting directionality \cite{tong_active_2001-2}. Multitask active learning algorithms would be useful for transferring knowledge from an experiment where interventions are possible to a similar domain where such interventions may be more expensive or impossible. Recent work proposes principled methods for the transfer of causal relationships between domains \cite{Pearl2011Transportabilit}. Our paper provides a critical algorithmic mechanism to implement such transfer of knowledge.


\section{Conclusions}

We have presented a multitask Bayesian network structure algorithm. This algorithm is able to successfully leverage data from related tasks to improve the estimate of network structure features given limited amounts of data. The primary contribution is determining that structural priors that are order-modular can be used to impose inductive bias among tasks. By using local structural priors, we achieve three goals simultaneously: 1) an intuitive inductive bias at the level of structures rather than orders;  2) take advantage of the most efficient structure discovery algorithms; and 3) closed form Bayesian model averaging over the transfer strength parameter. Empirical evidence suggests that multitask learning of Bayesian networks reduces the number of spurious dependencies learned, particularly at small sample set sizes.

\subsubsection*{Acknowledgments}

Thanks to Vincent Clark and the Mind Research Network for providing data and interesting data mining problems. Also, thanks to Eric Eaton and Paul Ruvolo for helpful discussions. Work funded by a grant from ONR N000141110139.

\bibliographystyle{IEEEtran}
\bibliography{MyLibrary}


\end{document} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


multiBN_arxiv.bbl
% Generated by IEEEtran.bst, version: 1.12 (2007/01/11)
\begin{thebibliography}{10}
\providecommand{\url}[1]{#1}
\csname url@samestyle\endcsname
\providecommand{\newblock}{\relax}
\providecommand{\bibinfo}[2]{#2}
\providecommand{\BIBentrySTDinterwordspacing}{\spaceskip=0pt\relax}
\providecommand{\BIBentryALTinterwordstretchfactor}{4}
\providecommand{\BIBentryALTinterwordspacing}{\spaceskip=\fontdimen2\font plus
\BIBentryALTinterwordstretchfactor\fontdimen3\font minus
  \fontdimen4\font\relax}
\providecommand{\BIBforeignlanguage}[2]{{%
\expandafter\ifx\csname l@#1\endcsname\relax
\typeout{** WARNING: IEEEtran.bst: No hyphenation pattern has been}%
\typeout{** loaded for the language `#1'. Using the pattern for}%
\typeout{** the default language instead.}%
\else
\language=\csname l@#1\endcsname
\fi
#2}}
\providecommand{\BIBdecl}{\relax}
\BIBdecl

\bibitem{thrun_is_1996}
S.~Thrun, ``Is learning the n-th thing any easier than learning the first?''
  \emph{Advances in Neural Information Processing Systems}, pp. 640--646, 1996.

\bibitem{caruana_multitask_1997}
R.~Caruana, ``Multitask learning,'' \emph{Machine Learning}, vol.~28, no.~1,
  pp. 41--75, Jul. 1997.

\bibitem{niculescu-mizil_inductive_2007}
A.~{Niculescu-Mizil} and R.~Caruana, ``Inductive transfer for {B}ayesian
  network structure learning,'' in \emph{Eleventh International Conference on
  Artificial Intelligence and Statistics {(AISTATS-07)}}, 2007.

\bibitem{zhang_multitask_2010}
J.~Zhang and C.~Zhang, ``Multitask {Bregman} clustering,'' in
  \emph{{Twenty-Fourth} {AAAI} Conference on Artificial Intelligence}, 2010.

\bibitem{friedman_being_2003}
N.~Friedman and D.~Koller, ``Being {B}ayesian about network structure: A
  {B}ayesian approach to structure discovery in {B}ayesian networks,''
  \emph{Machine Learning}, vol.~50, no.~1, pp. 95--125, 2003.

\bibitem{Koivisto:2004:EBS:1005332.1005352}
M.~Koivisto and K.~Sood, ``Exact {Bayesian} structure discovery in {Bayesian}
  networks,'' \emph{J. Mach. Learn. Res.}, vol.~5, pp. 549--573, 2004.

\bibitem{madigan1995bayesian}
D.~Madigan, J.~York, and D.~Allard, ``Bayesian graphical models for discrete
  data,'' \emph{International Statistical Review}, pp. 215--232, 1995.

\bibitem{grzegorczyk_improving_2008}
M.~Grzegorczyk and D.~Husmeier, ``Improving the structure {MCMC} sampler for
  {B}ayesian networks by introducing a new edge reversal move,'' \emph{Machine
  Learning}, vol.~71, no. 2-3, pp. 265--305, 2008.

\bibitem{Parviainen:2009:ESD:1795114.1795165}
P.~Parviainen and M.~Koivisto, ``Exact structure discovery in {Bayesian}
  networks with less space,'' in \emph{Proceedings of the Twenty-Fifth
  Conference on Uncertainty in Artificial Intelligence}, ser. UAI '09, 2009,
  pp. 436--443.

\bibitem{Niinimaki11}
T.~Niinimaki, P.~Parviainen, and M.~Koivisto, ``Partial order {MCMC} for
  structure discovery in {Bayesian} networks,'' in \emph{Proceedings of the
  Twenty-Seventh Conference Annual Conference on Uncertainty in Artificial
  Intelligence (UAI-11)}, 2011, pp. 557--564.

\bibitem{oyen_aaai_2012}
D.~Oyen and T.~Lane, ``Leveraging domain knowledge in multitask {Bayesian}
  network structure learning,'' in \emph{Proceedings of the {Twenty-Sixth}
  Conference on Artificial Intelligence}, 2012.

\bibitem{werhli2007reconstructing}
A.~Werhli and D.~Husmeier, ``Reconstructing gene regulatory networks with
  {B}ayesian networks by combining expression data with multiple sources of
  prior knowledge,'' \emph{Statistical applications in genetics and molecular
  biology}, vol.~6, no.~1, p.~15, 2007.

\bibitem{heckerman_learning_1995}
D.~Heckerman, D.~Geiger, and D.~M. Chickering, ``Learning {B}ayesian networks:
  The combination of knowledge and statistical data,'' \emph{Machine Learning},
  vol.~20, no.~3, pp. 197--243, 1995.

\bibitem{buntine1991theory}
W.~Buntine, ``Theory refinement on {Bayesian} networks,'' in \emph{Proceedings
  of the Seventh Conference on Uncertainty in Artificial Intelligence}, 1991,
  pp. 52--60.

\bibitem{cooper_bayesian_1992}
G.~F. Cooper and E.~Herskovits, ``A {Bayesian} method for the induction of
  probabilistic networks from data,'' \emph{Machine Learning}, vol.~9, pp.
  309--347, 1992.

\bibitem{Bailey1935Generalised-Hyp}
W.~N. Bailey, \emph{Generalised Hypergeometric Series}.\hskip 1em plus 0.5em
  minus 0.4em\relax Cambridge, England: University Press, 1935.

\bibitem{lauritzen1988local}
S.~Lauritzen and D.~Spiegelhalter, ``Local computations with probabilities on
  graphical structures and their application to expert systems,'' \emph{Journal
  of the Royal Statistical Society. Series B (Methodological)}, pp. 157--224,
  1988.

\bibitem{beinlich89alarm}
I.~A. Beinlich, H.~J. Suermondt, R.~M. Chavez, and G.~F. Cooper, ``The
  {A}{L}{A}{R}{M} monitoring system: A case study with two probabilistic
  inference techniques for belief networks,'' in \emph{Second European
  Conference on Artificial Intelligence in Medicine}, vol.~38, 1989, pp.
  247--256.

\bibitem{cooper_causal_1999}
G.~Cooper and C.~Yoo, ``Causal discovery from a mixture of experimental and
  observational data,'' in \emph{Proc. Fifthteenth Conference on Uncertainty in
  Artificial Intelligence {(UAI'99)}}, 1999, pp. 116--125.

\bibitem{tong_active_2001-2}
S.~Tong and D.~Koller, ``Active learning for structure in {B}ayesian
  networks,'' in \emph{International Joint Conference on Artificial
  Intelligence}, vol.~17, 2001, pp. 863--869.

\bibitem{Pearl2011Transportabilit}
J.~Pearl and E.~Bareinboim, ``Transportability of causal and statistical
  relations: A formal approach,'' in \emph{Proceedings of the Twenty-Fifth
  National Conference on Artificial Intelligence}.\hskip 1em plus 0.5em minus
  0.4em\relax AAAI Press, 2011, pp. 247---254.

\end{thebibliography}
