[thebeast] r736 committed - more work on StarAI paper
codesite...@google.com
Author: sebastian.riedel
Date: Wed Mar 24 22:06:14 2010
Log: more work on StarAI paper
http://code.google.com/p/thebeast/source/detail?r=736
Modified:
/branches/thefuture-modules/thebeast-core/src/main/lyx/starai.lyx
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/Env.scala
/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/tuples/TupleTerm.scala
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/learn/OnlineLearner.scala
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/solve/ArgmaxSolver.scala
=======================================
--- /branches/thefuture-modules/thebeast-core/src/main/lyx/starai.lyx Mon
Mar 22 22:37:56 2010
+++ /branches/thefuture-modules/thebeast-core/src/main/lyx/starai.lyx Wed
Mar 24 22:06:14 2010
@@ -47,21 +47,10 @@
\begin_body
\begin_layout Title
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-lang{}
+Declarative Probabilistic Programming for Undirected Graphical Models: Open
+ Up to Scale Up
\end_layout
-\end_inset
-
-: Open Up to Scale Up
-\end_layout
-
\begin_layout Abstract
While many probabilistic programming language focus on restricting
expressivenes
s to achieve complexity guarantees, we argue that we should rather design
@@ -78,7 +67,7 @@
more concise
\emph default
programs.
- More importantly, we argue that it can also lead to
+ More importantly, we argue and show that it can also lead to
\emph on
more efficient
\emph default
@@ -87,7 +76,7 @@
compositional
\emph default
inference methods that can exploit building-block specific sub-routines.
- We present
+ To this end we present
\begin_inset ERT
status open
@@ -100,10 +89,7 @@
\end_inset
-, a open-ended language to describe complex factor graphs, and extend it
- with projective spanning tree constraint.
- This constraint is used in place of a first order representation in a
dependenc
-y parsing application, and leads to dramatic speed ups.
+, a open-ended language to describe complex probabilistic models.
\end_layout
\begin_layout Section
@@ -198,7 +184,36 @@
building blocks such as a projective spanning tree constraint.
We show empirically that this allows us to implement a dramatically more
efficient dependency parser than in pure Markov Logic.
-
+\end_layout
+
+\begin_layout Standard
+Note as running example we use dependency parsing.
+ Here we need to find the syntactic relations between the tokens of a
sentence.
+ For example, in
+\begin_inset Quotes eld
+\end_inset
+
+the man walks
+\begin_inset Quotes erd
+\end_inset
+
+ man is the subject of walks, and
+\begin_inset Quotes eld
+\end_inset
+
+the
+\begin_inset Quotes erd
+\end_inset
+
+ is the determiner of
+\begin_inset Quotes eld
+\end_inset
+
+man.
+\begin_inset Quotes erd
+\end_inset
+
+
\end_layout
\begin_layout Section
@@ -231,9 +246,13 @@
\family typewriter
Domain[T]
\family default
- contains (Scala) objects we want to talk about; implementations of Domain
- usually need to provide an iterator over their objects, as well as a
+ contains (Scala) objects of type
\family typewriter
+T
+\family default
+ we want to talk about; implementations of Domain usually need to provide
+ an iterator over their objects, as well as a
+\family typewriter
contains
\family default
method to indicate Domain membership.
@@ -262,20 +281,24 @@
\end_layout
\begin_layout LyX-Code
-Val Bools = Values(false,true)
+val Parses = (Tokens x Tokens) -> Bools
\end_layout
-\begin_layout LyX-Code
-val Parses = (Tokens x Labels) -> Bools
-\end_layout
-
\begin_layout Standard
+\begin_inset Note Note
+status collapsed
+
+\begin_layout Plain Layout
Ultimately we want to reason about the objects of our domains, using
generic
knowledge independent of their actual identity.
To do so we need placeholders that allow us to speak about objects in an
abstract fashion.
This is generally achieved by variables.
- In
+\end_layout
+
+\end_inset
+
+In
\begin_inset ERT
status open
@@ -323,7 +346,7 @@
, Parses)
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
One can understand each variable as a question about the world we seek to
model.
In this sense each assignment to our variables refers to a possible state
@@ -354,12 +377,26 @@
\family typewriter
resolveVar
\family default
-: it returns the object the variable is assigned to, or
+: it returns the object the variable is assigned to.
+\begin_inset Foot
+status collapsed
+
+\begin_layout Plain Layout
+or
\family typewriter
None
\family default
- if no such object exists (for partial worlds).
- To construct worlds we can use
+ if no such object exists (for partial worlds)
+\end_layout
+
+\end_inset
+
+
+\begin_inset Note Note
+status collapsed
+
+\begin_layout Plain Layout
+To construct worlds we can use
\family typewriter
MutableWorld
\family default
@@ -382,13 +419,18 @@
world.close(parse)
\end_layout
+\end_inset
+
+
+\end_layout
+
\begin_layout Section
-Terms and Factors
+Terms
\end_layout
\begin_layout Standard
Intuitively, a term is a symbolic expression that is, given a possible
world,
- evaluated to a value.
+ evaluated to an object.
In
\begin_inset ERT
status open
@@ -406,78 +448,157 @@
\family typewriter
Term
\family default
- trait that has to implement a
+ trait that has to implement an
\family typewriter
evaluate(world)
\family default
- that defines how the term maps worlds to values.
- It also needs to provide a list of
+ method.
+ It defines how the term maps worlds to values.
+ A simple example of a term is the following:
+\end_layout
+
+\begin_layout LyX-Code
+Exp(Indicator(FunApp(edge,Tuple(root,5)))
+\end_layout
+
+\begin_layout Standard
+It is actually a composed term with an
\family typewriter
+Indicator
+\family default
+ term on its top-level.
+ An indicator (or iverson bracket) evaluates to 1 if the boolean term
inside
+ evaluates to
+\family typewriter
+TRUE
+\family default
+, and 0 otherwise.
+ The
+\family typewriter
+FunApp
+\family default
+ term applies the result of evaluating the first argument to the result
+ of evaluating the second.
+ The edge term is the
+\family typewriter
Var
\family default
- objects that it depends on.
+ object we defined earlier.
+ It evaluates to the function the variable is bound to in the given world.
+ The other terms are defined accordingly.
\end_layout
\begin_layout Standard
-The core built-in Term classes are
+Scala allows us to use a lot syntactic sugar to make code more concise.
+ In our case we can use this to alternatively write
\end_layout
-\begin_layout Enumerate
-
+\begin_layout LyX-Code
+exp(${edge(root,5)})
+\end_layout
+
+\begin_layout Standard
+The terms so far provide no means of abstraction.
+ To change this, we simply add
\family typewriter
-Var
+Quantification
\family default
-: evaluates to the value it is assigned to
+ terms which evaluate subterms for all objects of a given domain.
+ A simple case is
\end_layout
-\begin_layout Enumerate
-
-\family typewriter
-Constant()
-\family default
-: evaluates to the given constant
+\begin_layout LyX-Code
+sum(Tokens){i=> ${tag(i,VB)->edge(root,i)}}
+\end_layout
+
+\begin_layout Standard
+This term is evaluated as follows: we replace i in the inner term with each
+ possible value in Tokens, 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 already have an (unnormalized) MLN.
+
\end_layout
-\begin_layout Enumerate
-
+\begin_layout Standard
+Terms are the main building blocks of probabilistic models.
+ For most users, working with
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+lang{}
+\end_layout
+
+\end_inset
+
+ means composing terms into more complex terms, and use them to describe
+ probabilistic models.
+ Just as traditional logics allow them to compose terms into boolean
formulae
+ that describe the world.
+ Some users, however, will design and implement new terms.
+ In our running example, one could add a projective spanning tree
constraint
+
\family typewriter
-FunApp(f,a)
+PTree
\family default
-: evaluates to the result of applying f.evaluate to a.evaluate
+:
\end_layout
-\begin_layout Enumerate
+\begin_layout LyX-Code
+exp(${edge(root,5)})*PTree(edge,root)
+\end_layout
+
+\begin_layout Standard
\family typewriter
-Quantification(o,v,f)
+PTree(edge)
\family default
-: ...
+ returns 1 if the function in
+\family typewriter
+edge
+\family default
+ 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 Standard
-It should be clear that the above terms can be used to create a wide array
- of composite terms.
- For example...
+\begin_layout Section
+Compositional Inference
\end_layout
\begin_layout Standard
-Terms are the core building blocks we use to construct probability
distributions
- over possible worlds.
- In our framework, a probability distribution is nothing more than a term
- that evaluates to real values between 0 and 1 that sum up to 1 for all
- possible assignments of its contained variables.
- Once your term fulfills this contract, we can apply basic brute-force
inference
- algorithms to calculate expectations and find most likely assignments.
+We could also write some logical formulae to express the projective
spanning
+ tree constraint above.
+ However, introducing an own term for this makes our model more concise.
+ More importantly though, it can also make inference more tractable.
+
\end_layout
\begin_layout Standard
-Obviously any exhaustive inference scheme becomes intractable when the
number
- of variables in a term is large.
- However, inference is generally more tractable if terms factor into a
product
- of sub-terms.
- In this case we can apply methods such as Belief Propagation that avoid
- summing over all possible worlds.
+To illustrate this let us look at the case of Belief Propagation.
+ Smith and Eisner have shown how efficient dynamic programming methods can
+ be used to calculate the messages of a projective tree constraint factor.
In
\begin_inset ERT
status open
@@ -491,72 +612,62 @@
\end_inset
- such terms are instances of the
+ 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
-Factorizable
+message
\family default
- trait, and need to provide a
+ method that calculates its outgoing messages during BP.
+
+\end_layout
+
+\begin_layout Standard
+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, or
+ even Integer Linear Programming, and other type of graphical structures.
+ Moreover, note that we can follow a similar approach for inference methods
+ that do not unroll the full graph.
+ For example, terms can have a
\family typewriter
-factorize
+separate
\family default
- method that returns all terms the term factors in.
-
+ method for Cutting Plane Inference that returns all factors that are not
+
+\emph on
+maximally satisfied
+\emph default
+ in a given world.
\end_layout
\begin_layout Section
-Compositional Inference
+Related Work
\end_layout
\begin_layout Standard
-Belief Propagation lends itsell well to compositional inference.
- Both in the case of Sum-Product BP
-\begin_inset space ~
-\end_inset
-
-
-\begin_inset CommandInset citation
-LatexCommand cite
-key "smith08dependency"
-
-\end_inset
-
- and Max-Product BP
-\begin_inset space ~
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+lang{}
+\end_layout
+
\end_inset
-
-\begin_inset CommandInset citation
-LatexCommand cite
-key "Duchi07usingcombinatorial"
-
-\end_inset
-
- is has been shown how to rewrite the BP update equations so that
calculating
- outgoing factor messages amounts to performing marginal inference for the
- given factor alone (plus some local factors on each variable).
- Here we present the case of Sum-Product BP, but note that Max-Product BP
- has a very similar formulation.
+ is closely related to Markov Logic: it is declarative, and focuses on
loglinear
+ 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.
\end_layout
\begin_layout Standard
-In its canocial form, BP requires us to marginalize a variable for a factor
- term multiplied with the incoming messages from all but the current
variable
- node.
- However, this marginalization can be rewritten as follows:
-\end_layout
-
-\begin_layout Standard
-\begin_inset Formula \begin{equation}
-\#\#\label{eq:BP-CI}\end{equation}
-
-\end_inset
-
-
-\end_layout
-
-\begin_layout Standard
-In
+The possibility of incorporating tailor-made inference is also present in
+ FACTORIE; But while FACTORIE focuses on imperative constructs,
\begin_inset ERT
status open
@@ -569,51 +680,44 @@
\end_inset
- BP is therefore supported by a
+ is primarily declarative and requires imperative coding only for a few
+ extension designers.
+ In this sense it is actually close languages like Figaro or Blog, which
+ allow inclusion of tailor-made proposal functions.
+ However, these languages are a) primarily generative, and b) limit
themselves
+ to MCMC.
+
\end_layout
-\begin_layout LyX-Code
-
-\family typewriter
-marginalize(incoming:Beliefs):Beliefs
+\begin_layout Section
+Results and 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: ....
\end_layout
\begin_layout Standard
-method for real valued terms
-\family typewriter
-Term[Double]
-\family default
-.
- This method performs the calculation in equation
-\begin_inset CommandInset ref
-LatexCommand ref
-reference "eq:BP-CI"
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+\begin_inset CommandInset bibtex
+LatexCommand bibtex
+bibfiles "/Users/riedelcastro/projects/papers.fresh/bibtex/riedel"
+options "plain"
\end_inset
-, and
-\family typewriter
-incoming
-\family default
- provides local beliefs for each variable contained in the term.
- By default this method exhaustively goes through all variable states of
- the variables in the term and sums up probabilities (or scores) for each
- variable as defined by
-\begin_inset CommandInset ref
-LatexCommand ref
-reference "eq:BP-CI"
+
+\end_layout
\end_inset
-.
- However, for simple terms (such as weighted CNF terms) or more complicated
- ones (like a spanning tree constraint), we can provide tailor-made
inference
- and gain efficiencies.
-
-\end_layout
-
-\begin_layout Section
-Results
+
\end_layout
\begin_layout Standard
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/Env.scala
Thu Oct 29 21:57:40 2009
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/Env.scala
Wed Mar 24 22:06:14 2010
@@ -19,6 +19,10 @@
def mask(hiddenVariables: Set[EnvVar[_]]) = new MaskedEnv(this,
hiddenVariables);
+ /**
+ * uses the bindings of the overlayed env for all the variables it has
bindings for, and otherwise
+ * the bindings of this env.
+ */
def overlay(over: Env) = new OverlayedEnv(this, over)
def variables: Set[EnvVar[_]]
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/Term.scala
Wed Mar 24 00:09:51 2010
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/Term.scala
Wed Mar 24 22:06:14 2010
@@ -1,6 +1,7 @@
package org.riedelcastro.thebeast.env
import booleans.Equality
+import collection.immutable.Set
/**
@@ -44,7 +45,7 @@
/**
* Return a term that evaluates to true iff this and that term evaluate
to the same value
*/
- def ===[V>:T](that:Term[V]) = Equality(this,that)
+ def ===[V >: T](that: Term[V]) = Equality(this, that)
/**
* Are there no free variables in this term
@@ -56,7 +57,6 @@
*/
def subterms: Seq[Term[Any]]
-
/**
* todo: This method creates a clone of this object, but with the given
set of subterms
@@ -71,34 +71,47 @@
* take a sequence of members and create a new composite term, and
* how to return the composite members.
*/
-trait Composite[V,T<:Term[V], M<:Term[_]] extends Term[V] {
-
- def members:Seq[M]
- def build(members:Seq[M]):T
+trait Composite[V, T <: Term[V], M <: Term[_]] extends Term[V] {
+ def members: Seq[M]
+
+ def build(members: Seq[M]): T
override def ground(env: Env): T =
build(members.map(_.ground(env).asInstanceOf[M]))
override def isGround: Boolean = members.forall(_.isGround)
}
-trait Composite1[V,T<:Term[V],M<:Term[_]] extends Composite[V,T,M] {
-
- def build(member:M):T
+trait Composite1[V, T <: Term[V], M <: Term[_]] extends Composite[V, T, M]
{
+ def build(member: M): T
def build(members: Seq[M]): T = build(members(0))
def member: M
def members: Seq[M] = Seq(member)
+
+ def variables: Set[EnvVar[Any]] = members.foldLeft(Set[EnvVar[Any]]())
{(a,m)=> a ++ m.variables}
}
+trait Composite2[V, T <: Term[V], M <: Term[_], M1 <: M, M2 <: M] extends
Composite[V, T, M] {
+ def build(member1: M1, member2: M2): T
+
+ def build(members: Seq[M]): T = build(members(0).asInstanceOf[M1],
members(1).asInstanceOf[M2])
+
+ def member1: M1
+
+ def member2: M2
+
+ def members: Seq[M] = Seq(member1, member2)
+}
+
/**
* Grounded is a pattern matcher that matches terms which are ground (no
variables), and extracts
* the value the term evaluates to.
*/
object Grounded {
- def unapply[T](term: Term[T]):Option[T] =
+ def unapply[T](term: Term[T]): Option[T] =
if (term.isGround) EmptyEnv.eval(term)
else None
}
@@ -123,7 +136,7 @@
def subterms = Seq()
override def equals(obj: Any): Boolean = obj match {
- case Constant(v)=> v == value
+ case Constant(v) => v == value
case _ => false
}
@@ -136,11 +149,11 @@
object EnvVarMatch {
- def unapply[T](term:Term[T]):Option[EnvVar[T]] = {
+ def unapply[T](term: Term[T]): Option[EnvVar[T]] = {
term match {
- case x:EnvVar[_] => Some(x)
- case app @ FunApp(EnvVarMatch(f),Grounded(arg))
=>Some(app.asFunAppVar)
- case _=> None
+ case x: EnvVar[_] => Some(x)
+ case app@FunApp(EnvVarMatch(f), Grounded(arg)) =>
Some(app.asFunAppVar)
+ case _ => None
}
}
}
@@ -179,9 +192,10 @@
def cloneWithNewSubterms(subterms: Seq[Term[Any]]) = this
override def hashCode = 31 * name.hashCode + values.hashCode
+
override def equals(obj: Any) = obj match {
- case Var(n,v)=> name == n && values == v
- case _=> false
+ case Var(n, v) => name == n && values == v
+ case _ => false
}
}
@@ -190,7 +204,7 @@
}
case class Predicate[T](override val name: String, domain: Values[T])
- extends FunctionVar(name, FunctionValues(domain,
TheBeastImplicits.Bools))
+ extends FunctionVar(name, FunctionValues(domain,
TheBeastImplicits.Bools))
case class FunApp[T, R](val function: Term[T => R], val arg: Term[T])
extends Term[R] {
override def eval(env: Env) = {
@@ -225,8 +239,8 @@
}
def isAtomic: Boolean = arg.simplify.isInstanceOf[Constant[_]] &&
- (function.isInstanceOf[EnvVar[_]] ||
- (function.isInstanceOf[FunApp[_, _]] &&
function.asInstanceOf[FunApp[_, _]].isAtomic))
+ (function.isInstanceOf[EnvVar[_]] ||
+ (function.isInstanceOf[FunApp[_, _]] &&
function.asInstanceOf[FunApp[_, _]].isAtomic))
def asFunAppVar: FunAppVar[T, R] =
if (function.isInstanceOf[EnvVar[_]])
@@ -241,8 +255,8 @@
def subterms = Seq(function, arg)
- override def equals(obj:Any) = obj match {
- case FunApp(f,a) => this.function == f && this.arg == a
+ override def equals(obj: Any) = obj match {
+ case FunApp(f, a) => this.function == f && this.arg == a
case _ => false
}
@@ -268,7 +282,7 @@
}
}
- def simplify:Term[R] = Fold(function,args.map(_.simplify),init)
+ def simplify: Term[R] = Fold(function, args.map(_.simplify), init)
def variables = function.variables ++ init.variables ++ args.flatMap(a
=> a.variables)
@@ -291,28 +305,28 @@
subterms match {
case Seq(function, init, args@_*) =>
Fold(function.asInstanceOf[Term[R => (R => R)]],
- args.map(_.asInstanceOf[Term[R]]),
- init.asInstanceOf[Term[R]])
+ args.map(_.asInstanceOf[Term[R]]),
+ init.asInstanceOf[Term[R]])
case _ => error("subterms incompatible")
}
override def equals(obj: Any): Boolean = obj match {
- case Fold(f,a,i) => function == f && init == i &&
- args.size == a.size && (0 until args.size).forall(i=>args(i)
== a(i))
+ case Fold(f, a, i) => function == f && init == i &&
+ args.size == a.size && (0 until args.size).forall(i => args(i)
== a(i))
case _ => false
}
}
case class Quantification[R, V](val function: Term[R => (R => R)], val
variable: Var[V], val formula: Term[R], val init: Term[R])
- extends Term[R] {
+ extends Term[R] {
lazy val unroll = {
val env = new MutableEnv
Fold(function, variable.values.map(value => {env += variable -> value;
formula.ground(env)}).toSeq, init)
}
- def unrollUncertain = Fold(function, unroll.args.filter(arg
=> !arg.simplify.isGround),init)
+ def unrollUncertain = Fold(function, unroll.args.filter(arg
=> !arg.simplify.isGround), init)
def simplify = unroll.simplify
@@ -320,7 +334,7 @@
def values = unroll.values
- def ground(env: Env):Term[R] = unroll.ground(env)
+ def ground(env: Env): Term[R] = unroll.ground(env)
def eval(env: Env) = unroll.eval(env)
@@ -344,13 +358,13 @@
}
case class FunAppVar[T, R](val funVar: EnvVar[T => R], val argValue: T)
- extends FunApp(funVar, Constant(argValue))
- with EnvVar[R] {
-
+ extends FunApp(funVar, Constant(argValue))
+ with EnvVar[R] {
override def hashCode = 31 * funVar.hashCode + argValue.hashCode
+
override def equals(obj: Any) = obj match {
- case FunAppVar(f,a)=> funVar == f && argValue == a
- case _=> false
+ case FunAppVar(f, a) => funVar == f && argValue == a
+ case _ => false
}
}
@@ -377,6 +391,24 @@
object Singleton extends SingletonClass {
override def toString = "Singleton"
}
+
+
+
+case class InEnv[T](term:Term[T],env:Env) extends Term[T] with
Composite1[T,InEnv[T],Term[T]] {
+ def eval(env: Env): Option[T] = {
+ term.eval(env.overlay(this.env))
+ }
+
+ def values: Values[T] = term.values
+
+ def simplify: Term[T] = term.simplify match {case c:Constant[_] => c;
case x => InEnv(x,env)}
+
+ def member: Term[T] = term
+
+ def build(member: Term[T]): InEnv[T] = InEnv(member,env)
+
+ def subterms: Seq[Term[Any]] = Seq(term)
+}
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/doubles/DoubleTerm.scala
Sun Mar 21 13:01:44 2010
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/doubles/DoubleTerm.scala
Wed Mar 24 22:06:14 2010
@@ -104,6 +104,9 @@
override def simplify: DoubleTerm = Sum(args.map(_.simplify))
}
+
+case class SumOverGroundings[+T<:DoubleTerm](term:T,envs:Seq[Env])
+ extends Sum[DoubleTerm](envs.map(term.ground(_)))
object SumHelper {
def sum(terms: Collection[DoubleTerm], env: Env) = terms.foldLeft(0.0)
{(s, t) => s + env(t)}
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/tuples/TupleTerm.scala
Mon Oct 26 21:57:59 2009
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/tuples/TupleTerm.scala
Wed Mar 24 22:06:14 2010
@@ -1,5 +1,7 @@
package org.riedelcastro.thebeast.env.tuples
+import org.riedelcastro.thebeast.env._
+
/**
* @author Sebastian Riedel
*/
@@ -9,8 +11,6 @@
def subterms: Seq[Term[Any]] = {
for (i <- 0 until productArity) yield
productElement(i).asInstanceOf[Term[Any]]
}
-
-
override def toString = (for (i <- 0 until productArity) yield
productElement(i)).mkString(",")
}
@@ -21,9 +21,10 @@
case 3 => TupleTerm3(args(0),args(1),args(2))
case _ => error("Can't do tuples with more than 3 arguments yet")
}
-
//def apply(args:Term[Any]*): Term[Any] = apply(args.toSeq)
}
+
+
case class TupleTerm2[T1,T2](_1:Term[T1],_2:Term[T2]) extends
Term[Tuple2[T1,T2]] with TupleTerm {
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/learn/OnlineLearner.scala
Fri Sep 25 23:42:36 2009
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/learn/OnlineLearner.scala
Wed Mar 24 22:06:14 2010
@@ -1,21 +1,32 @@
package org.riedelcastro.thebeast.learn
-import env._
-import solve.{ExhaustiveSearch, ArgmaxSolver}
-import util.Trackable
-import vectors.{VectorTerm, Vector}
+import org.riedelcastro.thebeast.solve.{ExhaustiveSearch, ArgmaxSolver}
+import org.riedelcastro.thebeast.env.MaskedEnv
+import org.riedelcastro.thebeast.env.vectors.{VectorTerm, Vector}
+import org.riedelcastro.thebeast.util.Trackable
+import org.riedelcastro.thebeast.env.doubles.{LogLinear, Normalize,
SumOverGroundings, DoubleTerm}
+
/**
* @author Sebastian Riedel
*/
-class OnlineLearner extends Trackable {
+class OnlineLearner extends ArgmaxSolver with Trackable {
var solver: ArgmaxSolver = ExhaustiveSearch
var updateRule: UpdateRule = new PerceptronUpdateRule
var maxEpochs: Int = 1
+
+
+ def argmax(term: DoubleTerm): ArgmaxResult = {
+ term match {
+ case SumOverGroundings(Normalize(LogLinear(feature, weights, _)),
data)
+ if (Set(weights) == term.variables) => CantSolve
+ case _ => CantSolve
+ }
+ }
def learn(featureVector: VectorTerm, trainingSet: Seq[MaskedEnv]):
Vector = {
- |**("Learning");
+ |**("Learning");
var weights = new Vector
for (epoch <- 0 until maxEpochs) {
for (instance <- trainingSet) {
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/solve/ArgmaxSolver.scala
Fri Sep 25 23:42:36 2009
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/solve/ArgmaxSolver.scala
Wed Mar 24 22:06:14 2010
@@ -1,8 +1,8 @@
package org.riedelcastro.thebeast.solve
-
+import org.riedelcastro.thebeast._
import env.doubles.DoubleTerm
-import env.{Env}
+import env.{Var, Env}
/**
* @author Sebastian Riedel
@@ -10,17 +10,28 @@
trait ArgmaxSolver {
+ /**
+ * Returns the possible world that maximizes the given term
+ */
def argmax(term:DoubleTerm) : ArgmaxResult
+
+ //def argmax[T](variable:Var[T]) : T = null
+
object Status extends Enumeration {
type Status = Value
val Solved, CantDo, Infeasible = Value
}
+
import Status._
case class ArgmaxResult(val result:Env, val status:Status, val
score:Double) {
}
+
+ object CantSolve extends ArgmaxResult(null, CantDo, Math.NEG_INF_DOUBLE)
+
+
}