[thebeast] r747 committed - final changes

[codesite...@google.com]

Revision: 747
Author: sebastian.riedel
Date: Wed Apr 28 13:03:19 2010
Log: final changes
http://code.google.com/p/thebeast/source/detail?r=747

Added:
/branches/thefuture-modules/thebeast-core/src/main/lyx/starai.tex
Modified:
/branches/thefuture-modules/thebeast-core/src/main/lyx/starai.lyx

/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/Term.scala

/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/doubles/DoubleTerm.scala

/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/vectors/VectorTerm.scala

=======================================
--- /dev/null
+++ /branches/thefuture-modules/thebeast-core/src/main/lyx/starai.tex Wed
Apr 28 13:03:19 2010
@@ -0,0 +1,228 @@
+%% LyX 1.6.5 created this file. For more info, see http://www.lyx.org/.
+%% Do not edit unless you really know what you are doing.
+\documentclass[english]{article}
+\usepackage[T1]{fontenc}
+\usepackage[latin9]{inputenc}
+
+\makeatletter
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
+\newcommand{\noun}[1]{\textsc{#1}}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
+\newenvironment{lyxcode}
+{\par\begin{list}{}{
+\setlength{\rightmargin}{\leftmargin}
+\setlength{\listparindent}{0pt}% needed for AMS classes
+\raggedright
+\setlength{\itemsep}{0pt}
+\setlength{\parsep}{0pt}
+\normalfont\ttfamily}%
+ \item[]}
+{\end{list}}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
+\usepackage{aaai}
+\newcommand{\lang}{\textsc{DFacto}}
+\newcommand{\definition}{Declarative Factor Graphs, Open.}
+
+\makeatother
+
+\usepackage{babel}
+
+\begin{document}
+
+\title{Declarative Probabilistic Programming for Undirected Graphical
Models:
+Open Up to Scale Up}
+\maketitle
+\begin{abstract}
+We argue that probabilistic programming with undirected models, in
+order to scale up, needs to \emph{open up}. That is, instead of focussing
+on minimal sets of generic building blocks such as universal quantification
+or logical connectives, languages should \emph{grow} to include specific
+building blocks for as many uses cases as necessary. We argue that
+this can not only lead to more consise models, but also to\emph{ more
+efficient} inference if we use methods that can exploit building-block
+specific sub-routines. As embodyment of this paradigm we present \lang{},
+a framework for undirected graphical models that allows languages
+to grow.
+\end{abstract}
+
+\section{Introduction}
+
+Probabilistic Programming languages for undirected models, such as
+Markov Logic~\cite{richardson06markov} and Relational Markov
Networks~\cite{taskar02discriminative},
+are very expressive. Many statistical models of interest can be readily
+described in terms of these languages. However, often the generic
+inference routines will either be too slow, too inaccurate, or both.
+For example, it is possible to use Markov Logic for encoding probability
+distributions over the set of possible syntactic dependency trees
+of a sentence. Yet, generic inference in these models is very inefficient,
+in particular due to deterministic factors which ensure that the set
+of predicted edges is a spanning tree over the words of the sentence.
+
+Here we argue that probabilistic programming, in order to scale up,
+needs to \emph{open up}. That is, instead of focusing on minimal sets
+of generic building blocks such as universal quantification and logical
+connectives, languages should \emph{grow} to eventually include specific
+building blocks for as many uses cases as necessary. For example,
+we should provide a spanning tree constraint as part of our language
+that can be used whenever we want to extract dependency trees, of
+model hierarchical structures in general.%
+\footnote{Spanning trees also appear in image segmentation, and general
clustering
+of objects.%
+}
+
+On first sight, this is not more than syntactic sugar. However, we
+argue that it can also lead to\emph{ more efficient} inference if
+we use inference methods that can exploit building-block specific
+sub-routines. For example, Belief Propagation requires summation over
+the variables of each factor. For a spanning tree constraint this
+can be done very efficiently.
+
+Clearly, we do not want to design a language with all constructs we
+could ever need in advance. Instead, we need to provide the glue for
+an ever-increasing set of language \emph{extensions}. In the following
+we will present \lang{}, an attempt to provide this glue.
+
+Like Markov Logic\inputencoding{latin1}{, }\inputencoding{latin9}\lang{}
+is declarative and focuses on undirected models. However, it is not
+limited to logical connectives and quantification; rather, it serves
+as a framework for extensions such as cardinality constraints, or
+the tree constraint discussed above. \lang{} supports user-provided
+inference routines akin to the (primarily) imperative language
\noun{Factorie}~\cite{mccallum09factorie},
+but does so in a declarative setting. \lang{} is also similar to
+recent approaches such as \noun{Church}~\cite{goodman08church} and
+\noun{Figaro}~\cite{pfeffer09figaro}, which support tailor-made
+proposal functions. However, these languages focus on generative models
+and MCMC.
+
+
+\section{Domains, Variables, Worlds}
+
+The glue that \lang{} provides are object-oriented interfaces for
+building blocks. Most inference and learning methods (not a focus
+here) can be work purely in terms of these interfaces. We will describe
+them using classes and traits of Scala, a hybrid functional object-oriented
+programming language.
+
+A \texttt{Domain{[}T{]}} contains the (Scala) objects of type \texttt{T}
+we want to talk about; it needs to provide an iterator over its objects,
+as well as a \texttt{contains} method to indicate Domain membership.
+Three built-in types of domains are \texttt{Values, Tuples,} and
\texttt{Functions}.
+The first simply represents a user-defined set of objects; the second
+tuples values, and the third all functions from a domain to a target.
+
+For example, in
+\begin{lyxcode}
+val~Tokens~=~Values(0,1,2,3,4,5)
+
+val~Graph~=~(Tokens~x~Tokens)~->~Bools~
+\end{lyxcode}
+the first domain \texttt{Tokens} contains all integers from 0 to 5
+(and represent word indices in a sentence), and the second domain
+all functions that map token pairs to booleans (and represent directed
+graphs over the tokens).
+
+In \lang{} a variable is represented by objects of the class
\texttt{Var{[}T{]}}.
+Each variable has a name and a domain that specifies which values
+the variable can possibly take on. For example, in the following
+snippet \texttt{edge} is a graph over tokens:
+\begin{lyxcode}
+val~edge~=~Var({}``edge'',~Graph)
+\end{lyxcode}
+Finally, a variable binding is a (possible) \texttt{World}.%
+\footnote{This amounts to possible worlds in Markov Logic for bindings of
function
+variables that map into booleans. %
+} Its core method is \texttt{resolveVar(v)} and returns the object
+the variable \texttt{v} is assigned to.
+
+
+\section{Terms}
+
+A term is a symbolic expression that is, given a possible world, evaluated
+to an object. In \lang{} a term is an instance of a \texttt{Term{[}T{]}}
+trait that has to implement an \texttt{evaluate(world)} method which
+maps the binding \texttt{world} to a value of type \texttt{T}. Terms
+in \lang{} can serve as boolean formulae (when they evaluate into
+booleans). Crucially, when they evaluate into real values they also
+serve as probabilistic models.
+
+A simple example term is:
+\begin{lyxcode}
+Indicator(FunApp(edge,Tuple(0,5))
+\end{lyxcode}
+\texttt{Indicator} evaluates to 1 if the boolean term inside evaluates
+to \texttt{TRUE}, and 0 otherwise. The \texttt{FunApp} term applies
+the result of evaluating the first argument to the result of evaluating
+the second. \texttt{edge} refers to the \texttt{Var} object we defined
+earlier and evaluates to the function the variable is bound to. The
+other terms are defined accordingly. Scala's syntactic sugar, and
+\texttt{\$\{$\cdot$\}} as the indicator function, can be used to
+alternatively write
+\begin{lyxcode}
+\$\{edge(0,5)\}
+\end{lyxcode}
+To support abstraction, we provide quantified operations that are
+applied to all objects of a given domain. For example, to evaluate
+\begin{lyxcode}
+Sum(Tokens,i=>\$\{tag(i,VB)->edge(0,i)\})
+\end{lyxcode}
+we replace \emph{i} in the inner term with each possible value in
+\texttt{Tokens}, then we evaluate the inner term, get a real value
+$x_{i}$, and sum over all values $x_{i}$. Note that the term amounts
+to the logarithm of a simple MLN (without normalization) that encourages
+worlds where verbs (tokens with tag/part-of-speech VB) are children
+of 0 (by convention the root of the tree). Generic MLNs can be formulated
+accordingly.
+
+For most users, working with \lang{} means assembling terms of existing
+types into probabilistic models. Some users, however, will provide
+new types of terms. For example, we can add a spanning tree constraint
+\texttt{Tree(edge)} for which \texttt{eval} returns 1 if the function
+in \texttt{edge} corresponds to a spanning tree over objects in
\texttt{Tokens},
+and 0 otherwise.
+
+
+\section{Inference}
+
+Real valued terms also implement a \texttt{factorize} method that
+returns a set of terms it factors into. This method, together with
+\texttt{eval}, is sufficient to implement most (propositional) factor
+graph inference methods such as Belief Propagation and its variants.
+
+However, working purely in terms of \texttt{eval} will often be very
+inefficient. For example, calculating outgoing BP messages for
\texttt{Tree(edge)}
+is intractable because \texttt{eval} needs to be called for every
+possible assignment to \texttt{edge}. We therefore introduce a
\texttt{message}
+method that terms implement if outgoing messages can be calculated
+more efficiently. For our tree constraint factor this is possible
+in cubic time~\cite{smith08dependency}.
+
+Note that similar approaches can be used for algorithms such as Max
+Product BP~\cite{Duchi07usingcombinatorial} or methods that do not
+unroll the full graph. For example, quantified terms can have a
\texttt{separate}
+method for Cutting Plane Inference~\cite{riedel08improving} that
+returns all factors not \emph{maximally satisfied} in a given world.
+
+
+\section{Conclusion}
+
+We have presented \lang{}, an object-oriented framework for declarative
+probabilistic programming with undirected models. It supports user-provided
+extensions and is centered around a small set of interface definition
+that allow extensions to provide their semantics (through the \texttt{eval}
+method) and suitable inference routines (e.g., through the \texttt{message}
+method). We believe that this approach will make probabilistic programming
+with undirected models more applicable to real-world problems (such
+as dependency parsing) because we can leverage existing specialized
+as well as generic means of inference.
+
+{\footnotesize \bibliographystyle{aaai}
+\bibliography{/Users/riedelcastro/projects/papers.fresh/bibtex/riedel}
+}{\footnotesize \par}
+
+
+
+
+\end{document}
=======================================
--- /branches/thefuture-modules/thebeast-core/src/main/lyx/starai.lyx Sun
Mar 28 19:29:00 2010
+++ /branches/thefuture-modules/thebeast-core/src/main/lyx/starai.lyx Wed
Apr 28 13:03:19 2010
@@ -6,6 +6,7 @@
\begin_preamble
\usepackage{aaai}
\newcommand{\lang}{\textsc{DFacto}}
+\newcommand{\definition}{Declarative Factor Graphs, Open.}
\end_preamble
\use_default_options true
\language english
@@ -52,31 +53,26 @@
\end_layout

\begin_layout Abstract
-We argue that probabilistic programming, in order to scale up, needs to
-
+We argue that probabilistic programming with undirected models, in order
+ to scale up, needs to
\emph on
open up
\emph default
.
That is, instead of focussing on minimal sets of generic building blocks
- such as universal quantification and logical connectives, languages should
+ such as universal quantification or logical connectives, languages should

\emph on
grow
\emph default
to include specific building blocks for as many uses cases as necessary.
- On first sight this is not more than syntactic sugar to make models
-\emph on
-more concise
-\emph default
-.
- However, we argue and show that it can also lead to
+ We argue that this can not only lead to more consise models, but also to
\emph on
more efficient
\emph default
- inference if we use inference methods that can exploit building-block
specific
- sub-routines.
- To this end we present
+ inference if we use methods that can exploit building-block specific
sub-routin
+es.
+ As embodyment of this paradigm we present
\begin_inset ERT
status open

@@ -89,7 +85,7 @@

\end_inset

-, a open-ended framework for Undirected Graphical Models.
+, a framework for undirected graphical models that allows languages to
grow.
\end_layout

\begin_layout Section
@@ -97,7 +93,8 @@
\end_layout

\begin_layout Standard
-Probabilistic Programming languages such as Markov Logic
+Probabilistic Programming languages for undirected models, such as Markov
+ Logic
\begin_inset space ~
\end_inset

@@ -108,17 +105,28 @@

\end_inset

- and ? are very expressive.
- Many statistical models of interest can be readily described using the
- generic building blocks of these languages.
- However, in many cases the generic inference routines of the language
interpret
-er will either be too slow, too inaccurate, or both.
- For example, it is possible (albeit slightly convoluted) to use Markov
- Logic for encoding probability distributions over the set of possible
syntactic
- dependency trees of a sentence.
+ and Relational Markov Networks
+\begin_inset space ~
+\end_inset
+
+
+\begin_inset CommandInset citation
+LatexCommand cite
+key "taskar02discriminative"
+
+\end_inset
+
+, are very expressive.
+ Many statistical models of interest can be readily described in terms of
+ these languages.
+ However, often the generic inference routines will either be too slow,
+ too inaccurate, or both.
+ For example, it is possible to use Markov Logic for encoding probability
+ distributions over the set of possible syntactic dependency trees of a
+ sentence.
Yet, generic inference in these models is very inefficient, in particular
- due to deterministic factors such as the spanning tree constraint that
- induce high tree-width and strong interactions between variables.
+ due to deterministic factors which ensure that the set of predicted edges
+ is a spanning tree over the words of the sentence.

\end_layout

@@ -129,7 +137,7 @@
open up
\emph default
.
- That is, instead of focussing on minimal sets of generic building blocks
+ That is, instead of focusing on minimal sets of generic building blocks
such as universal quantification and logical connectives, languages should

\emph on
@@ -139,20 +147,30 @@
necessary.
For example, we should provide a spanning tree constraint as part of our
language that can be used whenever we want to extract dependency trees,
- of model hierachical structures in general.
+ of model hierarchical structures in general.
+\begin_inset Foot
+status collapsed
+
+\begin_layout Plain Layout
+Spanning trees also appear in image segmentation, and general clustering
+ of objects.
+\end_layout
+
+\end_inset
+

\end_layout

\begin_layout Standard
On first sight, this is not more than syntactic sugar.
- However, we argue and show that it can also lead to
+ However, we argue that it can also lead to
\emph on
more efficient
\emph default
inference if we use inference methods that can exploit building-block
specific
sub-routines.
- For example, Belief Propagation essentially requires each factor to
marginalize
- itself.
+ For example, Belief Propagation requires summation over the variables of
+ each factor.
For a spanning tree constraint this can be done very efficiently.
\end_layout

@@ -194,8 +212,8 @@
weighted first order logic to describe Markov Networks of repetitive
structure.
It is one of the most expressive languages as it can describe arbitrary
Markov Networks.
- Its expressiveness comes at a price: we loose any complexity guaranteees
- that less expressive langauges tend to give.
+ Its expressiveness comes at a price: we loose any complexity guarantees
+ that less expressive languages tend to give.
If the user designs the
\begin_inset Quotes eld
\end_inset
@@ -213,11 +231,11 @@
\begin_inset Quotes erd
\end_inset

- model for the same task, there are cleary times when this is not the case.
+ model for the same task, there are clearly times when this is not the
case.
One example is dependency parsing, where we are required to model relation
structure that represents projective trees.
Formulating this in Markov Logic leads to graphical models with very high
- treewidth, and hence high complexity.
+ tree-width, and hence high complexity.
\end_layout

\begin_layout Plain Layout
@@ -261,17 +279,42 @@
\end_inset

,
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
\begin_inset Foot
+status collapsed
+
+\begin_layout Plain Layout
+\begin_inset ERT
status open

\begin_layout Plain Layout
-Declarative Factor Graphs, Open.
+
+
+\backslash
+definition{}
\end_layout

+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
\end_inset

an attempt to provide this glue.
- Like Markov Logic
+
+\end_layout
+
+\begin_layout Standard
+Like Markov Logic
,
\lang english

@@ -288,10 +331,10 @@
\end_inset

is declarative and focuses on undirected models.
- However, it is not limited to the logical connectives and quantifications
- present in ML; rather, it serves as a framework for extensions such as
- cardinality constraints, or the tree constraint presented here.
- Like FACTORIE,
+ However, it is not limited to logical connectives and quantification;
rather,
+ it serves as a framework for extensions such as cardinality constraints,
+ or the tree constraint discussed above.
+
\begin_inset ERT
status open

@@ -304,7 +347,23 @@

\end_inset

- supports tailor-made inference, but while FACTORIE is primarily
imperative,
+ supports user-provided inference routines akin to the (primarily)
imperative
+ language
+\noun on
+Factorie
+\noun default
+
+\begin_inset space ~
+\end_inset
+
+
+\begin_inset CommandInset citation
+LatexCommand cite
+key "mccallum09factorie"
+
+\end_inset
+
+, but does so in a declarative setting.

\begin_inset ERT
status open
@@ -318,15 +377,43 @@

\end_inset

- is purely declarative (for all but language extension designers).
- It is also similar to recent generative approaches, such as Church or
Figaro,
- which supprt tailor-made proposal functions.
- However, these languages are a) (primarily) generative, and b) limit
themselves
- to MCMC.
-
-\end_layout
-
-\begin_layout Standard
+ is also similar to recent approaches such as
+\noun on
+Church
+\noun default
+
+\begin_inset space ~
+\end_inset
+
+
+\begin_inset CommandInset citation
+LatexCommand cite
+key "goodman08church"
+
+\end_inset
+
+ and
+\noun on
+Figaro
+\noun default
+
+\begin_inset space ~
+\end_inset
+
+
+\begin_inset CommandInset citation
+LatexCommand cite
+key "pfeffer09figaro"
+
+\end_inset
+
+, which support tailor-made proposal functions.
+ However, these languages focus on generative models and MCMC.
+
+\begin_inset Note Note
+status collapsed
+
+\begin_layout Plain Layout
We have used
\begin_inset ERT
status open
@@ -382,6 +469,11 @@

\end_layout

+\end_inset
+
+
+\end_layout
+
\begin_layout Section
Domains, Variables, Worlds
\end_layout
@@ -400,11 +492,14 @@

\end_inset

- provides are abstract datatypes for building blocks, as well as a set of
- initial constructs.
- Most Machine Learning infrastructure (inference and learning) can be
formulated
- purely in terms of these interfaces.
+ provides are object-oriented interfaces for building blocks.
+ Most inference and learning methods (not a focus here) can be work purely
+ in terms of these interfaces.
We will describe them using classes and traits of Scala
+\begin_inset Note Note
+status collapsed
+
+\begin_layout Plain Layout
\begin_inset space ~
\end_inset

@@ -413,6 +508,11 @@
LatexCommand cite
key "odersky08programming"

+\end_inset
+
+
+\end_layout
+
\end_inset

, a hybrid functional object-oriented programming language.
@@ -434,6 +534,10 @@
contains
\family default
method to indicate Domain membership.
+\begin_inset Note Note
+status collapsed
+
+\begin_layout Plain Layout
\begin_inset Foot
status collapsed

@@ -448,29 +552,45 @@

\end_layout

-\begin_layout Standard
-The three core types of domains are
+\end_inset
+
+ Three built-in types of domains are
\family typewriter
-Values, Tuples,
+Values, Tuples,
\family default
-and
+ and
\family typewriter
Functions
\family default
.
- The former simply represents a user-defined set of objects of type T; the
- latter a the set of all functions from a domain to a target.
+ The first simply represents a user-defined set of objects; the second
tuples
+ values, and the third all functions from a domain to a target.

\end_layout

+\begin_layout Standard
+For example, in
+\end_layout
+
\begin_layout LyX-Code
-val Tokens = Values(0,1,2,3,4,5,...)
+val Tokens = Values(0,1,2,3,4,5)
\end_layout

\begin_layout LyX-Code
-val Parses = (Tokens x Tokens) -> Bools
+val Graph = (Tokens x Tokens) -> Bools
\end_layout

+\begin_layout Standard
+the first domain
+\family typewriter
+Tokens
+\family default
+ contains all integers from 0 to 5 (and represent word indices in a
sentence),
+ and the second domain all functions that map token pairs to booleans (and
+ represent directed graphs over the tokens).
+
+\end_layout
+
\begin_layout Standard
\begin_inset Note Note
status collapsed
@@ -509,41 +629,33 @@
status collapsed

\begin_layout Plain Layout
-Variables can be simple (referring to simple objects) or complex (refering
+Variables can be simple (referring to simple objects) or complex (referring
to functions) :
\end_layout

\end_inset

-
+ For example, in the following snippet
+\family typewriter
+edge
+\family default
+ is a graph over tokens:
\end_layout

\begin_layout LyX-Code
-val root = Var(
+val edge = Var(
\begin_inset Quotes eld
\end_inset

-root
+edge
\begin_inset Quotes erd
\end_inset

-, Tokens)
+, Graph)
\end_layout

-\begin_layout LyX-Code
-val parse = Var(
-\begin_inset Quotes eld
-\end_inset
-
-parse
-\begin_inset Quotes erd
-\end_inset
-
-, Parses)
-\end_layout
-
\begin_layout Standard
-A variable binding is a (possible)
+Finally, a variable binding is a (possible)
\family typewriter
World
\family default
@@ -552,8 +664,8 @@
status collapsed

\begin_layout Plain Layout
-Note that this is a generalization of possible worlds in Markov Logic if
- one considers bindings of function variables that map into booleans.
+This amounts to possible worlds in Markov Logic for bindings of function
+ variables that map into booleans.

\end_layout

@@ -568,6 +680,10 @@
v
\family default
is assigned to.
+\begin_inset Note Note
+status collapsed
+
+\begin_layout Plain Layout
\begin_inset Foot
status collapsed

@@ -579,6 +695,11 @@
if no such object exists (for partial worlds)
\end_layout

+\end_inset
+
+
+\end_layout
+
\end_inset


@@ -642,7 +763,7 @@
\family typewriter
evaluate(world)
\family default
- method that maps the binding
+ method which maps the binding
\family typewriter
world
\family default
@@ -651,7 +772,7 @@
T
\family default
.
- Crucially, terms in
+ Terms in
\begin_inset ERT
status open

@@ -664,16 +785,27 @@

\end_inset

- also serve as formulae (then they evaluate into booleans) and
probabilistic
- models (then they evaluate into real values).
+ can serve as boolean formulae (when they evaluate into booleans).
+ Crucially, when they evaluate into real values they also serve as
probabilistic
+ models.
+\begin_inset Note Note
+status collapsed
+
+\begin_layout Plain Layout
+ Hence defining probabilistic models amounts to assembling terms.
\end_layout

+\end_inset
+
+
+\end_layout
+
\begin_layout Standard
A simple example term is:
\end_layout

\begin_layout LyX-Code
-Exp(Indicator(FunApp(edge,Tuple(root,5)))
+Indicator(FunApp(edge,Tuple(0,5))
\end_layout

\begin_layout Standard
@@ -703,20 +835,7 @@
object we defined earlier and evaluates to the function the variable is
bound to.
The other terms are defined accordingly.
-
-\end_layout
-
-\begin_layout Standard
-We will use Scala's syntactic sugar to make code more concise.
- In our case we can use this to alternatively write
-\end_layout
-
-\begin_layout LyX-Code
-exp(${edge(root,5)})
-\end_layout
-
-\begin_layout Standard
-where
+ Scala's syntactic sugar, and
\family typewriter
${
\begin_inset Formula $\cdot$
@@ -724,10 +843,13 @@

}
\family default
- is the indicator function.
-
+ as the indicator function, can be used to alternatively write
\end_layout

+\begin_layout LyX-Code
+${edge(0,5)}
+\end_layout
+
\begin_layout Standard
To support abstraction, we provide quantified operations that are applied
to all objects of a given domain.
@@ -735,39 +857,66 @@
\end_layout

\begin_layout LyX-Code
-Sum(Tokens,i=>${tag(i,VB)->edge(root,i)})
+Sum(Tokens,i=>${tag(i,VB)->edge(0,i)})
\end_layout

\begin_layout Standard
-we replace i in the inner term with each possible value in
+we replace
+\emph on
+i
+\emph default
+ in the inner term with each possible value in
\family typewriter
Tokens
\family default
-, then we evaluate the inner term, get a real value, and sum up these
values.
- It should be clear that by placing this term into the exponential function
- we have an (unnormalized) MLN.
- Also note that by replacing the add operation with
-\begin_inset Quotes eld
+, then we evaluate the inner term, get a real value
+\begin_inset Formula $x_{i}$
\end_inset

-or
-\begin_inset Quotes erd
+, and sum over all values
+\begin_inset Formula $x_{i}$
\end_inset

+.
+\begin_inset Note Note
+status collapsed
+
+\begin_layout Plain Layout
+\begin_inset Foot
+status collapsed
+
+\begin_layout Plain Layout
+Note that by replacing the
+\family typewriter
+add
+\family default
+ operation with
+\family typewriter
+or
+\family default
and
-\begin_inset Quotes eld
+\family typewriter
+and
+\family default
+ we get existential and universal quantification.
+
+\end_layout
+
\end_inset

-and
-\begin_inset Quotes erd
+
+\end_layout
+
\end_inset

- we get existential and universal quantification.
+ Note that the term amounts to the logarithm of a simple MLN (without
normalizat
+ion) that encourages worlds where verbs (tokens with tag/part-of-speech
+ VB) are children of 0 (by convention the root of the tree).
+ Generic MLNs can be formulated accordingly.
\end_layout

\begin_layout Standard
-Terms are the main building blocks of probabilistic models.
- For most users, working with
+For most users, working with
\begin_inset ERT
status open

@@ -780,25 +929,15 @@

\end_inset

- means composing terms into more complex terms, and use them to describe
- probabilistic models.
- Some users, however, will design and implement new terms.
- In our running example, one could add a projective spanning tree
constraint
-
+ means assembling terms of existing types into probabilistic models.
+ Some users, however, will provide new types of terms.
+ For example, we can add a spanning tree constraint
\family typewriter
-PTree
+Tree(edge)
\family default
-:
-\end_layout
-
-\begin_layout LyX-Code
-${edge(root,5)}*PTree(edge,root)
-\end_layout
-
-\begin_layout Standard
-
+ for which
\family typewriter
-PTree(edge)
+eval
\family default
returns 1 if the function in
\family typewriter
@@ -807,22 +946,8 @@
corresponds to a spanning tree over objects in
\family typewriter
Tokens
-\family default
- rooted at
-\family typewriter
-root
\family default
, and 0 otherwise.
- Hence the above term will return 1 iff
-\family typewriter
-edge
-\family default
- is a spanning tree and if the
-\family typewriter
-root
-\family default
- value is linked to token 5.
-
\end_layout

\begin_layout Section
@@ -830,53 +955,62 @@
\end_layout

\begin_layout Standard
-\begin_inset Note Note
-status collapsed
-
-\begin_layout Plain Layout
-Introducing an own term for spanning tree makes our model more concise.
- More importantly though, it also makes inference more tractable.
- To illustrate this let us look at the case of Belief Propagation.
+Real valued terms also implement a
+\family typewriter
+factorize
+\family default
+ method that returns a set of terms it factors into.
+ This method, together with
+\family typewriter
+eval
+\family default
+, is sufficient to implement most (propositional) factor graph inference
+ methods such as Belief Propagation and its variants.

\end_layout

+\begin_layout Standard
+However, working purely in terms of
+\family typewriter
+eval
+\family default
+ will often be very inefficient.
+ For example, calculating outgoing BP messages for
+\family typewriter
+Tree(edge)
+\family default
+ is intractable because
+\family typewriter
+eval
+\family default
+ needs to be called for every possible assignment to
+\family typewriter
+edge
+\family default
+.
+ We therefore introduce a
+\family typewriter
+message
+\family default
+ method that terms implement if outgoing messages can be calculated more
+ efficiently.
+ For our tree constraint factor this is possible in cubic time
+\begin_inset space ~
\end_inset


\begin_inset CommandInset citation
-LatexCommand citet
+LatexCommand cite
key "smith08dependency"

\end_inset

- have shown how efficient dynamic programming methods can be used to
calculate
- the outgoing messages of a projective tree constraint factor.
- In
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-lang{}
+.
\end_layout

-\end_inset
-
- we allow the inference engine to make use of this.
- When the language designer adds a new term, he can also override a
-\family typewriter
-message
-\family default
- method that calculates its outgoing messages during BP.
-
-\end_layout
-
\begin_layout Plain Layout
-Note that this type of compositional inference is not exclusive to Sum
Product
- BP, and the spanning tree factor.
- Similar approaches can be used for algorithms such as Max Product BP
+Note that similar approaches can be used for algorithms such as Max Product
+ BP
\begin_inset space ~
\end_inset

@@ -903,13 +1037,13 @@

\end_inset

- that returns all factors that are not
+ that returns all factors not
\emph on
maximally satisfied
\emph default
in a given world.
\begin_inset Note Note
-status open
+status collapsed

\begin_layout Section
Related Work
@@ -978,23 +1112,50 @@

\end_inset

-
+
\end_layout

\begin_layout Section
-Results and Conclusion
+Conclusion
\end_layout

\begin_layout Standard
-To show the dramatic impact that these tailor-made terms can yield, we
compared
- a model with PTree constraint to a model that uses FOL formulae to achieve
- the same.
- For sentences longer than 10, our speed-ups were dramatic: ....
+We have presented
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+lang{}
\end_layout

+\end_inset
+
+, an object-oriented framework for declarative probabilistic programming
+ with undirected models.
+ It supports user-provided extensions and is centered around a small set
+ of interface definition that allow extensions to provide their semantics
+ (through the
+\family typewriter
+eval
+\family default
+ method) and suitable inference routines (e.g., through the
+\family typewriter
+message
+\family default
+ method).
+ We believe that this approach will make probabilistic programming with
+ undirected models more applicable to real-world problems (such as
dependency
+ parsing) because we can leverage existing specialized as well as generic
+ means of inference.
+
+\end_layout
+
\begin_layout Standard

-\size small
+\size footnotesize
\begin_inset CommandInset bibtex
LatexCommand bibtex
bibfiles "/Users/riedelcastro/projects/papers.fresh/bibtex/riedel"
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/Term.scala
Sun Mar 28 19:29:00 2010
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/Term.scala
Wed Apr 28 13:03:19 2010
@@ -133,10 +133,11 @@
override def eval(env: Env) = Some(value)

override def toString = value match {
- case x:Integer => x.toString
- case x:Product => x.toString
- case x:String => x.toString
- case x:AnyRef => x.getClass().getSimpleName
+ case x: Var[_]#GroundedConstant => "#" + x.variable.toString
+ case x: Integer => x.toString
+ case x: Product => x.toString
+ case x: String => x.toString
+ case x: AnyRef => x.getClass().getSimpleName
case x => x.toString
}

@@ -166,6 +167,7 @@
}
}
}
+


case class Var[+T](val name: String, override val values: Values[T])
extends Term[T] with EnvVar[T] {
@@ -181,13 +183,17 @@
funapps
}

+ trait GroundedConstant {
+ def variable = Var.this
+ }
def simplify = this

override def toString = name

def ground(env: Env) = {
val x = env.eval(this);
- if (x.isDefined) Constant(x.get) else this
+ if (x.isDefined) new Constant(x.get) with GroundedConstant
+ else this
}

override def eval(env: Env) = env.resolveVar[T](this)
@@ -412,7 +418,7 @@
case class DependsOn[V, T <: Term[V]](term: T, hidden: Set[EnvVar[_]])
extends Composite1[V, DependsOn[V, T], T] {
def values: Values[V] = term.values

- def simplify: Term[V] = DependsOn[V,Term[V]](term.simplify, hidden)
+ def simplify: Term[V] = DependsOn[V, Term[V]](term.simplify, hidden)

def eval(env: Env): Option[V] = {
val closed = new MutableEnv
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/doubles/DoubleTerm.scala
Thu Mar 25 20:55:13 2010
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/doubles/DoubleTerm.scala
Wed Apr 28 13:03:19 2010
@@ -48,7 +48,7 @@
extends Var[Double](name, values) with DoubleTerm {
def upperBound = Math.POS_INF_DOUBLE

- override def ground(env: Env) =
env.eval(this).map(DoubleConstant(_)).getOrElse(this)
+ override def ground(env: Env) = env.eval(this).map(new DoubleConstant(_)
with GroundedConstant).getOrElse(this)


override def simplify = this
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/vectors/VectorTerm.scala
Sun Mar 14 23:39:26 2010
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/vectors/VectorTerm.scala
Wed Apr 28 13:03:19 2010
@@ -91,7 +91,7 @@

case class VectorVar(override val name: String)
extends Var[Vector](name, VectorValues) with VectorTerm {
- override def ground(env: Env) =
env.eval(this).map(VectorConstant(_)).getOrElse(this)
+ override def ground(env: Env) = env.eval(this).map(new VectorConstant(_)
with GroundedConstant).getOrElse(this)

override def simplify = this
}

--
You received this message because you are subscribed to the Google Groups "thebeast-commit" group.
To post to this group, send email to thebeas...@googlegroups.com.
To unsubscribe from this group, send email to thebeast-comm...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/thebeast-commit?hl=en.