\relax 
\bibstyle{plainnat}
\citation{Buntine96}
\citation{Heckerman95tut}
\citation{Jordan98}
\citation{Buntine91}
\citation{CH92}
\citation{Suzuki93uai}
\citation{Bouckaert93}
\citation{HGC95}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{445}}
\newlabel{sec:intro}{{1}{445}}
\citation{Chow68}
\citation{VP90}
\citation{CH92}
\citation{Chickering96uai}
\@writefile{toc}{\contentsline {section}{\numberline {2}Background}{446}}
\newlabel{sec:background}{{2}{446}}
\citation{Pearl88}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Bayesian Networks}{447}}
\newlabel{eq:factor}{{1}{447}}
\citation{Akaike74}
\citation{Schwarz78}
\citation{Rissanen86}
\citation{PV91}
\citation{Spirtes93}
\citation{DS93}
\citation{HS95}
\citation{Chickering95a}
\citation{Akaike74}
\citation{Schwarz78}
\citation{Rissanen86}
\citation{Bouckaert93}
\citation{Chickering96lns}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Learning Bayesian Networks}{448}}
\citation{AMP97}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.3}Learning Equivalence Classes vs. Learning DAGs}{449}}
\citation{MAPV96}
\citation{GP01}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces Example of a greedy algorithm applied to the space of DAG models.  }}{450}}
\newlabel{fig:greed}{{1}{450}}
\citation{CH92}
\citation{MC00}
\citation{Meek95uai}
\citation{Spirtes93}
\citation{DD99}
\citation{SM95}
\citation{MB01}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.4}General Notation and Results}{451}}
\citation{VP90}
\newlabel{th:vp}{{1}{452}}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces (a) a PDAG that admits a consistent extension, (b) a consistent extension of the PDAG in (a), and (c) a PDAG that does not admit a consistent extension.  }}{453}}
\newlabel{fig:pdag}{{2}{453}}
\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces (a) a DAG $\unhbox \voidb@x \hbox {$\cal  G$}$ and (b) the completed PDAG for $\unhbox \voidb@x \hbox {$Class$}(\unhbox \voidb@x \hbox {$\cal  G$})$.  }}{453}}
\newlabel{fig:cpdag}{{3}{453}}
\newlabel{lem:unique}{{2}{453}}
\@writefile{toc}{\contentsline {section}{\numberline {3}Converting Between DAGs and PDAGs}{453}}
\newlabel{sec:trans}{{3}{453}}
\citation{AMP97}
\citation{Meek95uai}
\citation{DorTarsi92}
\@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces Algorithm to produce a total ordering over the edges in a DAG. The algorithm is used by Algorithm {\sc  Label-Edges}.  }}{455}}
\newlabel{fig:order-edges}{{4}{455}}
\@writefile{lof}{\contentsline {figure}{\numberline {5}{\ignorespaces Algorithm to label each edge in a DAG with ``compelled'' or ``reversible'', which leads to an immediate implementation of {\sc  DAG-to-CPDAG}.  }}{455}}
\newlabel{fig:label-edges}{{5}{455}}
\citation{CGH95aistats}
\@writefile{toc}{\contentsline {section}{\numberline {4}Heuristic Search for Bayesian-network Structures}{456}}
\newlabel{sec:space}{{4}{456}}
\@writefile{lof}{\contentsline {figure}{\numberline {6}{\ignorespaces States resulting from the application of a single operator in B-space.  }}{457}}
\newlabel{fig:dagops}{{6}{457}}
\newlabel{eq:decompose}{{2}{457}}
\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces E-space operators to be applied to completed PDAGs}}{458}}
\newlabel{tab:operators}{{1}{458}}
\@writefile{lof}{\contentsline {figure}{\numberline {7}{\ignorespaces Diagram depicting how operators are applied. The PDAGs on the bottom give an example for every stage of the process.  }}{458}}
\newlabel{fig:scheme}{{7}{458}}
\@writefile{lof}{\contentsline {figure}{\numberline {8}{\ignorespaces Example of each type of operator.  }}{459}}
\newlabel{fig:pdagops}{{8}{459}}
\newlabel{th:complete}{{4}{459}}
\citation{Chickering96uai}
\@writefile{toc}{\contentsline {section}{\numberline {5}Local Scoring in E-Space}{460}}
\newlabel{sec:main}{{5}{460}}
\newlabel{def:semi-directed}{{5}{460}}
\newlabel{th:insertu-valid}{{6}{461}}
\newlabel{cor:insertu-score}{{7}{461}}
\newlabel{th:deleteu-valid}{{8}{461}}
\newlabel{cor:deleteu-score}{{9}{461}}
\newlabel{th:insertd-valid}{{10}{461}}
\newlabel{cor:insertd-score}{{11}{461}}
\newlabel{th:deleted-valid}{{12}{461}}
\newlabel{cor:deleted-score}{{13}{461}}
\newlabel{th:reversed-valid}{{14}{461}}
\newlabel{cor:reversed-score}{{15}{461}}
\newlabel{th:makev-valid}{{16}{461}}
\newlabel{cor:makev-score}{{17}{462}}
\@writefile{lof}{\contentsline {figure}{\numberline {9}{\ignorespaces Approach taken to prove each of the operator results.  }}{462}}
\newlabel{fig:approach}{{9}{462}}
\@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces Necessary and sufficient validity conditions and (local) change in score for each operator in E-space}}{463}}
\newlabel{tab:main}{{2}{463}}
\@writefile{toc}{\contentsline {section}{\numberline {6}Experimental Results}{464}}
\newlabel{sec:experiments}{{6}{464}}
\newlabel{eq:bdeu}{{3}{464}}
\@writefile{lof}{\contentsline {figure}{\numberline {10}{\ignorespaces Score as a function of time for the six datasets.  }}{466}}
\newlabel{fig:AllResults}{{10}{466}}
\@writefile{lot}{\contentsline {table}{\numberline {3}{\ignorespaces Results for the model selected by the greedy algorithm applied to both spaces.}}{467}}
\newlabel{tab:results}{{3}{467}}
\@writefile{lot}{\contentsline {table}{\numberline {4}{\ignorespaces Average and maximum lower bound on the number of DAGs per equivalence class}}{468}}
\newlabel{tab:count}{{4}{468}}
\@writefile{toc}{\contentsline {section}{\numberline {7}Discussion}{468}}
\newlabel{sec:conclusion}{{7}{468}}
\citation{KBS01}
\citation{Meek97}
\bibstyle{theapa}
\bibcite{Akaike74}{{1}{1974}{{Akaike}}{{}}}
\bibcite{AMP97}{{2}{1997}{{Andersson et~al.}}{{}}}
\bibcite{BlairPeyton93}{{3}{1993}{{Blair and Peyton}}{{}}}
\bibcite{Bouckaert93}{{4}{1993}{{Bouckaert}}{{}}}
\bibcite{Buntine91}{{5}{1991}{{Buntine}}{{}}}
\bibcite{Buntine96}{{6}{1996}{{Buntine}}{{}}}
\bibcite{Chickering95a}{{7}{1995}{{Chickering}}{{}}}
\bibcite{Chickering96lns}{{8}{1996a}{{Chickering}}{{}}}
\bibcite{Chickering96uai}{{9}{1996b}{{Chickering}}{{}}}
\bibcite{CGH95aistats}{{10}{1995}{{Chickering et~al.}}{{}}}
\bibcite{Chow68}{{11}{1968}{{Chow and Liu}}{{}}}
\bibcite{CH92}{{12}{1992}{{Cooper and Herskovits}}{{}}}
\bibcite{DD99}{{13}{1999}{{Dash and Druzdzel}}{{}}}
\bibcite{DorTarsi92}{{14}{1992}{{Dor and Tarsi}}{{}}}
\bibcite{DS93}{{15}{1993}{{Druzdzel and Simon}}{{}}}
\bibcite{GP01}{{16}{2001}{{Gillispie and Perlman}}{{}}}
\bibcite{Heckerman95tut}{{17}{1996}{{Heckerman}}{{}}}
\bibcite{HGC95}{{18}{1995}{{Heckerman et~al.}}{{}}}
\bibcite{HS95}{{19}{1995}{{Heckerman and Shachter}}{{}}}
\bibcite{Jordan98}{{20}{1998}{{Jordan}}{{}}}
\bibcite{KBS01}{{21}{2001}{{Kocka et~al.}}{{}}}
\bibcite{MAPV96}{{22}{1996}{{Madigan et~al.}}{{}}}
\bibcite{Meek95uai}{{23}{1995}{{Meek}}{{}}}
\bibcite{Meek97}{{24}{1997}{{Meek}}{{}}}
\bibcite{MB01}{{25}{2001}{{Munteanu and Bendou}}{{}}}
\bibcite{MC00}{{26}{2000}{{Munteanu and Cau}}{{}}}
\bibcite{Pearl88}{{27}{1988}{{Pearl}}{{}}}
\bibcite{PV91}{{28}{1991}{{Pearl and Verma}}{{}}}
\bibcite{Rissanen86}{{29}{1986}{{Rissanen}}{{}}}
\bibcite{Schwarz78}{{30}{1978}{{Schwarz}}{{}}}
\bibcite{Spirtes93}{{31}{1993}{{Spirtes et~al.}}{{}}}
\bibcite{SM95}{{32}{1995}{{Spirtes and Meek}}{{}}}
\bibcite{Suzuki93uai}{{33}{1993}{{Suzuki}}{{}}}
\bibcite{TY84}{{34}{1984}{{Tarjan and Yannakakis}}{{}}}
\bibcite{VP90}{{35}{1990}{{Verma and Pearl}}{{}}}
\@writefile{toc}{\contentsline {section}{\numberline {A}Detailed Proofs}{472}}
\@writefile{toc}{\contentsline {subsection}{\numberline {A.1}Definitions and Preliminary Results}{473}}
\newlabel{sec:prelim-appendix}{{A.1}{473}}
\newlabel{prop:rule1}{{18}{473}}
\newlabel{prop:rule2}{{19}{473}}
\newlabel{lem:triangle}{{20}{473}}
\newlabel{lem:covered}{{21}{473}}
\newlabel{lem:covered-component}{{22}{473}}
\newlabel{lem:components}{{23}{474}}
\newlabel{lem:localInsert}{{24}{474}}
\newlabel{lem:localDelete}{{25}{474}}
\citation{TY84}
\@writefile{toc}{\contentsline {subsection}{\numberline {A.2}Extracting Consistent Extensions from Completed PDAGs}{475}}
\newlabel{sec:mcs}{{A.2}{475}}
\newlabel{th:chordal}{{26}{475}}
\newlabel{lem:indep-ce}{{27}{475}}
\newlabel{lem:mcs}{{28}{476}}
\newlabel{th:mcsalg}{{29}{476}}
\@writefile{lof}{\contentsline {figure}{\numberline {11}{\ignorespaces Algorithm DAG-MCS which extracts a consistent extension from a completed PDAG.}}{477}}
\newlabel{fig:algmcs}{{11}{477}}
\newlabel{Xlem:mcs-cliqueX}{{30}{477}}
\newlabel{lem:cliqueNeighbors}{{31}{477}}
\newlabel{lem:dpath}{{32}{478}}
\newlabel{cor:dpath}{{33}{479}}
\@writefile{toc}{\contentsline {subsection}{\numberline {A.3}Compelled and Reversible Edge Insertions}{479}}
\newlabel{sec:pain}{{A.3}{479}}
\newlabel{th:pain}{{34}{479}}
\newlabel{prop:no-creverse}{{35}{480}}
\newlabel{lem:stay-compelled}{{36}{480}}
\newlabel{cor:stay-compelled-pdag}{{37}{481}}
\newlabel{cor:stay-compelled}{{38}{481}}
\newlabel{lem:stay-compelled-head}{{39}{481}}
\newlabel{lem:not-covered}{{40}{481}}
\newlabel{lem:stay-reversible}{{41}{482}}
\newlabel{lem:undirected-comp}{{42}{482}}
\newlabel{lem:consistent-insertd}{{43}{483}}
\newlabel{lem:consistent-insertu}{{44}{484}}
\@writefile{toc}{\contentsline {subsection}{\numberline {A.4}The InsertU Operator}{484}}
\newlabel{sec:op1}{{A.4}{484}}
\@writefile{toc}{\contentsline {subsection}{\numberline {A.5}The DeleteU Operator}{485}}
\newlabel{sec:op2}{{A.5}{485}}
\@writefile{toc}{\contentsline {subsection}{\numberline {A.6}The InsertD Operator}{486}}
\newlabel{sec:op3}{{A.6}{486}}
\newlabel{lem:firstu}{{45}{486}}
\newlabel{cor:firstu}{{46}{487}}
\newlabel{cor:twosegnoedge}{{47}{487}}
\@writefile{toc}{\contentsline {subsection}{\numberline {A.7}The DeleteD Operator}{489}}
\newlabel{sec:op4}{{A.7}{489}}
\@writefile{toc}{\contentsline {subsection}{\numberline {A.8}The ReverseD Operator}{490}}
\newlabel{sec:op5}{{A.8}{490}}
\newlabel{lem:semi-neighbor}{{48}{490}}
\@writefile{toc}{\contentsline {subsection}{\numberline {A.9}The MakeV Operator}{492}}
\newlabel{sec:op6}{{A.9}{492}}
\@writefile{toc}{\contentsline {subsection}{\numberline {A.10}Completeness of the Operators}{493}}
\newlabel{sec:complete}{{A.10}{493}}
\citation{BlairPeyton93}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {A.10.1}Deleting All Edges}{494}}
\newlabel{sec:phase-delete}{{A.10.1}{494}}
\newlabel{lem:chordal-clique}{{49}{494}}
\newlabel{cor:chordal-clique}{{50}{494}}
\newlabel{cor:delete-deleteu}{{51}{494}}
\newlabel{lem:phase-delete}{{52}{494}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {A.10.2}Inserting V-Structures}{494}}
\newlabel{sec:phase-v}{{A.10.2}{494}}
\newlabel{prop:v2}{{53}{494}}
\newlabel{prop:v1}{{54}{495}}
\newlabel{lem:phase-v}{{55}{495}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {A.10.3}Inserting Compelled Edges}{496}}
\newlabel{sec:phase-compelled}{{A.10.3}{496}}
\newlabel{prop:2rules}{{56}{496}}
\newlabel{lem:phase-compelled}{{57}{496}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {A.10.4}Inserting Reversible Edges}{497}}
\newlabel{sec:phase-undirected}{{A.10.4}{497}}
\newlabel{prop:delu}{{58}{497}}
\newlabel{lem:phase-reversible}{{59}{497}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {A.10.5}Proof of Theorem 4\hbox {}}{498}}
\newlabel{sec:phase-done}{{A.10.5}{498}}