[thebeast] r719 committed - spanning tree now allows order
codesite...@google.com
Author: sebastian.riedel
Date: Tue Mar 16 19:15:51 2010
Log: spanning tree now allows order
http://code.google.com/p/thebeast/source/detail?r=719
Modified:
/branches/thefuture-modules/thebeast-apps/src/main/scala/org/riedelcastro/thebeast/apps/DependencyParsing.scala
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/TheBeastEnv.scala
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/Values.scala
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/booleans/BooleanTerm.scala
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/combinatorics/SpanningTreeConstraint.scala
/branches/thefuture-modules/thebeast-core/src/test/scala/org/riedelcastro/thebeast/env/combinatorics/SpanningTreeConstraintSpecification.scala
=======================================
---
/branches/thefuture-modules/thebeast-apps/src/main/scala/org/riedelcastro/thebeast/apps/DependencyParsing.scala
Tue Mar 16 12:52:51 2010
+++
/branches/thefuture-modules/thebeast-apps/src/main/scala/org/riedelcastro/thebeast/apps/DependencyParsing.scala
Tue Mar 16 19:15:51 2010
@@ -35,7 +35,7 @@
val posPair = vectorSum(Tokens, Tokens, Tags, Tags) {(h, m, h_pos,
m_pos) =>
$(pos(h, h_pos) && pos(m, m_pos) && link(h, m)) * unit(h_pos, m_pos)}
- val treeConstraint = SpanningTreeConstraint(link, token, 0)
+ val treeConstraint = SpanningTreeConstraint(link, token, 0,
LessThan(Tokens))
val weightVar = VectorVar("weights")
//val linearModel = ((wordPair + posPair + bias) dot weightVar) +
treeConstraint
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/TheBeastEnv.scala
Sun Mar 14 23:39:26 2010
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/TheBeastEnv.scala
Tue Mar 16 19:15:51 2010
@@ -50,7 +50,10 @@
//implicit def value2constant[T](value: T) = Constant(value)
- implicit def function2constant[T1, T2](value: T1 => T2) = Constant(value)
+ implicit def function2constant[T1, R](value: T1 => R) = Constant(value)
+
+ implicit def function22constant[T1, T2, R](value: (T1,T2) => R) =
Constant(value)
+
implicit def tuple2toTupleTerm2[T1, T2](value: (Term[T1], Term[T2])) =
TupleTerm2(value._1, value._2)
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/Values.scala
Sun Mar 14 17:41:16 2010
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/Values.scala
Tue Mar 16 19:15:51 2010
@@ -1,10 +1,11 @@
package org.riedelcastro.thebeast.env
+import booleans.Bools
import collection.mutable.{HashSet, MapProxy}
import ints.IntConstant
-import tuples.TupleValues
import org.riedelcastro.thebeast.util.{GlobalRandom, Util}
+import tuples.{TupleValues2, TupleValues}
/**
* @author Sebastian Riedel
@@ -18,6 +19,8 @@
def createVariable(name: String): Var[T] = new Var(name, this)
+ def compare[R>:T](x:R,y:R) = false
+
def size: Int = toSeq.size
def arity = this match {
@@ -66,7 +69,12 @@
}
object Ints {
- def apply(values: Collection[Int]) = new ValuesProxy(Seq.empty ++ values)
+ def apply(values: Collection[Int]) = new ValuesProxy(Seq.empty ++
values){
+ override def compare[R>:Int](x: R, y: R) = (x,y) match {
+ case (x:Int,y:Int) => x < y
+ case _ => false
+ }
+ }
}
@@ -111,6 +119,18 @@
}
}
+case class LessThanFunction[T](domain:Values[T]) extends
FunctionValue[(T,T),Boolean]{
+
+ val signature = new FunctionValues(TupleValues2(domain,domain),Bools)
+
+ def apply(pair:(T,T)): Boolean = false//domain.compare(pair._1,pair._2)
+
+ def getSources(r: Option[Boolean]): Iterable[(T,T)] = null
+}
+
+case class LessThan[T](domain:Values[T]) extends
Constant(LessThanFunction(domain))
+
+
class MutableFunctionValue[T, R](val signature: FunctionValues[T, R])
extends scala.collection.mutable.HashMap[T, R] with
FunctionValue[T, R] {
def getSources(r: Option[R]): Iterable[T] = {
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/booleans/BooleanTerm.scala
Sun Mar 14 17:41:16 2010
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/booleans/BooleanTerm.scala
Tue Mar 16 19:15:51 2010
@@ -187,6 +187,9 @@
def ground(env: Env) = Equality(lhs.ground(env),rhs.ground(env))
}
+
+
+
case class BooleanConstant(override val value: Boolean) extends
BoundedConstant(value) with BooleanTerm {
override def ground(env: Env) = this
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/combinatorics/SpanningTreeConstraint.scala
Tue Mar 16 12:52:51 2010
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/combinatorics/SpanningTreeConstraint.scala
Tue Mar 16 19:15:51 2010
@@ -7,60 +7,62 @@
/**
*.A SpanningTreeConstraint is a term that maps graphs to 1 if they are
- * spanning trees over the set of vertices, and to 0 otherwise. Note
+ * projective spanning trees over the set of vertices, and to 0 otherwise.
Note
* that for efficient processing vertices and root need to be ground
* and edges needs to be a predicate.
*/
case class SpanningTreeConstraint[V](edges: Term[FunctionValue[(V, V),
Boolean]],
vertices: Term[FunctionValue[V,
Boolean]],
- root: Term[V]) extends DoubleTerm {
+ root: Term[V],
+ order: Term[FunctionValue[(V, V),
Boolean]]) extends DoubleTerm {
def ground(env: Env): DoubleTerm = {
-
SpanningTreeConstraint(edges.ground(env),vertices.ground(env),root.ground(env))
+ SpanningTreeConstraint(edges.ground(env), vertices.ground(env),
root.ground(env), order.ground(env))
}
def simplify: DoubleTerm = {
- val simplified =
SpanningTreeConstraint(edges.simplify,vertices.simplify, root.simplify)
+ val simplified = SpanningTreeConstraint(edges.simplify,
vertices.simplify, root.simplify, order.simplify)
val constant = simplified.eval(EmptyEnv)
if (constant.isDefined) DoubleConstant(constant.get) else simplified
}
def upperBound = 1.0
- def subterms = Seq(edges, vertices,root)
+ def subterms = Seq(edges, vertices, root)
def eval(env: Env): Option[Double] = {
//get edges map
val v = Set() ++ env(vertices).getSources(Some(true))
val e = env(edges).getSources(Some(true)).filter(edge => v(edge._1) &&
v(edge._2))
val r = env(root)
- val heads = new HashMap[V,V]
- for (edge <- e){
+ val heads = new HashMap[V, V]
+ for (edge <- e) {
if (heads.contains(edge._2)) return Some(0.0)
heads(edge._2) = edge._1
}
- val indices = new HashMap[V,Int]
- val lowlinks = new HashMap[V,Int]
+ if (v.exists(vertex => vertex != r && !heads.isDefinedAt(vertex)))
return Some(0.0)
+ val indices = new HashMap[V, Int]
+ val lowlinks = new HashMap[V, Int]
val stack = new Stack[V]
val roots = new HashSet[V]
var index = 0
- for (vertex <- v){
+ for (vertex <- v) {
if (!indices.isDefinedAt(vertex)) tarjan(vertex)
if (!roots.isEmpty) return Some(0.0)
}
- def tarjan(vertex:V) {
+ def tarjan(vertex: V) {
indices(vertex) = index
lowlinks(vertex) = index
index += 1
stack.push(vertex)
- for (head <- heads.get(vertex)){
+ for (head <- heads.get(vertex)) {
if (!indices.isDefinedAt(head)) {
tarjan(head)
- lowlinks(vertex)=Math.min(lowlinks(vertex),lowlinks(head))
- } else if (stack.contains(head)){
- lowlinks(vertex)=Math.min(lowlinks(vertex),indices(head))
+ lowlinks(vertex) = Math.min(lowlinks(vertex), lowlinks(head))
+ } else if (stack.contains(head)) {
+ lowlinks(vertex) = Math.min(lowlinks(vertex), indices(head))
}
}
- if (lowlinks(vertex) == indices(vertex)){
+ if (lowlinks(vertex) == indices(vertex)) {
if (stack.top != vertex) roots += vertex
var top = vertex
do {
@@ -71,24 +73,38 @@
}
Some(1.0)
}
-
def values = Values(0.0, 1.0)
def variables = {
if (vertices.isGround && root.isGround &&
edges.isInstanceOf[Predicate[_]]) {
- val pred = edges.asInstanceOf[Predicate[(V,V)]]
- val v = EmptyEnv(vertices).getSources(Some(true))
- val r = EmptyEnv(root)
- Set() ++ (for (source <- v; dest <- v; if (dest != r && dest !=
source))
- yield FunAppVar(pred,(source,dest)))
-
+ linkVariables.asInstanceOf[Set[EnvVar[Any]]]
} else
edges.variables ++ vertices.variables ++ root.variables
}
-
+ private def linkVariables:Set[FunAppVar[(V,V),Boolean]] = {
+ val pred = edges.asInstanceOf[Predicate[(V, V)]]
+ val v = EmptyEnv(vertices).getSources(Some(true))
+ val r = EmptyEnv(root)
+ Set() ++ (for (source <- v; dest <- v; if (dest != r && dest !=
source))
+ yield FunAppVar(pred, (source, dest)))
+ }
+
+
+ override def marginalize(incoming: Beliefs[Any, EnvVar[Any]]):
Beliefs[Any, EnvVar[Any]] = {
+ if (vertices.isGround && root.isGround &&
edges.isInstanceOf[Predicate[_]]) {
+ case class
Signature(from:Int,to:Int,leftParentWithin:Boolean,rightParentWithin:Boolean)
+ val links = linkVariables
+ val vertices = EmptyEnv(this.vertices)
+ val root = EmptyEnv(this.root)
+ val inside = new HashMap[Signature,Double]
+ val outside = new HashMap[Signature,Double]
+ super.marginalize(incoming)
+ } else
+ super.marginalize(incoming)
+ }
}
/*
=======================================
---
/branches/thefuture-modules/thebeast-core/src/test/scala/org/riedelcastro/thebeast/env/combinatorics/SpanningTreeConstraintSpecification.scala
Tue Mar 16 12:52:51 2010
+++
/branches/thefuture-modules/thebeast-core/src/test/scala/org/riedelcastro/thebeast/env/combinatorics/SpanningTreeConstraintSpecification.scala
Tue Mar 16 19:15:51 2010
@@ -3,7 +3,7 @@
import org.specs.Specification
import org.riedelcastro.thebeast.DependencyParsingFixtures
import org.specs.runner.{JUnit4}
-import org.riedelcastro.thebeast.env.{FunAppVar, TheBeastEnv}
+import org.riedelcastro.thebeast.env.{Constant, LessThan, FunAppVar,
TheBeastEnv}
/**
* @author sriedel
@@ -16,19 +16,47 @@
val fixtures = new DependencyParsingFixtures
import fixtures._
val sentence = createTheManIsFast
- val constraint = new SpanningTreeConstraint(link, token, 0)
+ val constraint = new SpanningTreeConstraint[Int](link, token, 0,
LessThan(Tokens))
sentence(constraint) must_== 1.0
}
+ "return 0 if the the graph has a cycle" in {
+ val fixtures = new DependencyParsingFixtures
+ import fixtures._
+ val sentence = createSentence(
+ List("root","the","man" ,"walks"),
+ List("root","DT","NN", "VB"),
+ List((0,3),(1,2),(2,1)))
+ val constraint = new SpanningTreeConstraint(link, token, 0,
LessThan(Tokens))
+ sentence(constraint) must_== 0.0
+ }
+ "return 0 if the the graph has a vertices with multiple parents" in {
+ val fixtures = new DependencyParsingFixtures
+ import fixtures._
+ val sentence = createSentence(
+ List("root","the","man" ,"walks"),
+ List("root","DT","NN", "VB"),
+ List((0,3),(1,2),(3,2)))
+ val constraint = new SpanningTreeConstraint(link, token, 0,
LessThan(Tokens))
+ sentence(constraint) must_== 0.0
+ }
+ "return 0 if the the graph is not spanning all vertices" in {
+ val fixtures = new DependencyParsingFixtures
+ import fixtures._
+ val sentence = createSentence(
+ List("root","the","man" ,"walks"),
+ List("root","DT","NN", "VB"),
+ List((0,3),(3,2)))
+ val constraint = new SpanningTreeConstraint(link, token, 0,
LessThan(Tokens))
+ sentence(constraint) must_== 0.0
+ }
"return only edge variables that could be part of a spanning tree if
root and vertices are grounded" in {
val fixtures = new DependencyParsingFixtures
import fixtures._
val sentence = createTheMan
- val constraint = new SpanningTreeConstraint(link, token, 0)
+ val constraint = new SpanningTreeConstraint(link, token, 0,
LessThan(Tokens))
val expected =
Set(FunAppVar(link,(0,1)),FunAppVar(link,(0,2)),FunAppVar(link,(1,2)),FunAppVar(link,(2,1)))
val result = constraint.ground(sentence.mask(Set(link))).variables
result must_== expected
-
-
}
}