[thebeast] r727 committed - dependency parsing application now uses ptree

[codesite...@google.com]

Revision: 727
Author: sebastian.riedel
Date: Sun Mar 21 11:26:30 2010
Log: dependency parsing application now uses ptree
http://code.google.com/p/thebeast/source/detail?r=727

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/combinatorics/SpanningTreeConstraint.scala

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

/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/util/Logging.scala

=======================================
---
/branches/thefuture-modules/thebeast-apps/src/main/scala/org/riedelcastro/thebeast/apps/DependencyParsing.scala
Tue Mar 16 19:15:51 2010
+++
/branches/thefuture-modules/thebeast-apps/src/main/scala/org/riedelcastro/thebeast/apps/DependencyParsing.scala
Sun Mar 21 11:26:30 2010
@@ -40,7 +40,7 @@
val weightVar = VectorVar("weights")
//val linearModel = ((wordPair + posPair + bias) dot weightVar) +
treeConstraint
val linearModel = ((wordPair + posPair + bias) dot weightVar)
- val probModel = normalize(exp(linearModel))
+ val probModel = normalize(exp(linearModel) *
ptree(link,token,0,LessThan(Tokens)))

//some example data
val sentence1 = new MutableEnv
@@ -48,9 +48,11 @@
sentence1.atoms(word) ++=
List("Root", "The", "man", "is", "fast").zipWithIndex.map(_.swap)
sentence1.atoms(pos) ++=
List("Root", "DT", "NN", "VB", "AD").zipWithIndex.map(_.swap)
sentence1.atoms(link) ++= List((0,3),(3,2),(3,4),(2,1))
+ sentence1.atoms(token) ++= (0 until 5)
sentence1.close(word,true)
sentence1.close(pos,true)
sentence1.close(link,true)
+ sentence1.close(token,true)

val weights = new Vector
weights("bias") = -2.0
@@ -72,6 +74,13 @@

println(marginals)
+
+ var sum = 0.0
+ for (h <- 0 until 5; if (h != 1)) {
+ sum += marginals.belief(FunAppVar(link,(h,1))).belief(true)
+ }
+ println(sum)
+
}

}
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/TheBeastEnv.scala
Tue Mar 16 19:15:51 2010
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/TheBeastEnv.scala
Sun Mar 21 11:26:30 2010
@@ -1,5 +1,6 @@
package org.riedelcastro.thebeast.env

+import combinatorics.SpanningTreeConstraint
import doubles._
import ints._
import booleans._
@@ -12,7 +13,6 @@
*/

object TheBeastImplicits extends TheBeastEnv {
-
}

trait TheBeastEnv {
@@ -32,13 +32,18 @@

def normalize(arg: DoubleTerm) = Normalize(arg)

+ def ptree[V](edges: Term[FunctionValue[(V, V), Boolean]],
+ vertices: Term[FunctionValue[V, Boolean]],
+ root: Term[V],
+ order: Term[FunctionValue[(V, V), Boolean]]) =
SpanningTreeConstraint(edges,vertices,root,order)
+
implicit def string2varbuilder(name: String) = new {
def <~[T](values: Values[T]) = Var(name, values)

//def in[T, R](values: FunctionValues[T, R]) = FunVar(name, values)
}

- implicit def varDouble2DoubleVar(varDouble:Var[Double]) =
DoubleVar(varDouble.name,varDouble.values)
+ implicit def varDouble2DoubleVar(varDouble: Var[Double]) =
DoubleVar(varDouble.name, varDouble.values)

//def ground(variable:Var[T], t:T)

@@ -52,7 +57,7 @@

implicit def function2constant[T1, R](value: T1 => R) = Constant(value)

- implicit def function22constant[T1, T2, R](value: (T1,T2) => 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)
@@ -66,7 +71,7 @@
// }

- implicit def term2SingletonConditionedTerm[T](term : Term[T]) = new
ConditionedTerm(term,Singleton)
+ implicit def term2SingletonConditionedTerm[T](term: Term[T]) = new
ConditionedTerm(term, Singleton)

implicit def term2ConditionedTermBuilder[T](term: Term[T]) = new {

@@ -81,19 +86,19 @@
def |||[C1, C2](c1: Term[C1], c2: Term[C2]): ConditionedTerm[T,
Tuple2[C1, C2]] = ConditionedTerm(term, TupleTerm2(c1, c2))
}

- implicit def tupleterm2toConditionedTermBuilder[T1,T2](term:
Tuple2[Term[T1],Term[T2]]) = new {
+ implicit def tupleterm2toConditionedTermBuilder[T1, T2](term:
Tuple2[Term[T1], Term[T2]]) = new {

/**
* Creates a conditioned term, useful for CPDs.
*/
- def |||[C1](condition: Term[C1]): ConditionedTerm[(T1,T2), C1] =
- ConditionedTerm(TupleTerm2(term._1,term._2), condition)
+ def |||[C1](condition: Term[C1]): ConditionedTerm[(T1, T2), C1] =
+ ConditionedTerm(TupleTerm2(term._1, term._2), condition)

/**
* Creates a conditioned term, useful for CPDs.
*/
- def |||[C1, C2](c1: Term[C1], c2: Term[C2]): ConditionedTerm[(T1,T2),
Tuple2[C1, C2]] =
- ConditionedTerm(TupleTerm2(term._1,term._2), TupleTerm2(c1, c2))
+ def |||[C1, C2](c1: Term[C1], c2: Term[C2]): ConditionedTerm[(T1, T2),
Tuple2[C1, C2]] =
+ ConditionedTerm(TupleTerm2(term._1, term._2), TupleTerm2(c1, c2))
}

//implicit def termtuple2toTupleTerm2[T1,T2](tuple:
Tuple2[Term[T1],Term[T2]]) = TupleTerm2(tuple._1, tuple._2)
@@ -129,33 +134,33 @@
def apply(t: Term[T]) = FunApp(fun, t)
}

-// implicit def term2groundFunAppBuilder[T, R](fun: FunctionVar[T,R]) =
new (T => GroundFunApp[T, R]) {
-// def apply(t: T) = GroundFunApp(fun, t)
-// }
+ // implicit def term2groundFunAppBuilder[T, R](fun: FunctionVar[T,R]) =
new (T => GroundFunApp[T, R]) {
+ // def apply(t: T) = GroundFunApp(fun, t)
+ // }

implicit def term2doubleFunAppBuilder[T](fun: Term[T => Double]) = new
(Term[T] => DoubleFunApp[T]) {
def apply(t: Term[T]) = DoubleFunApp(fun, t)
}

-// implicit def term2booleanFunAppBuilder[T >: AnyVal](fun: Term[T =>
Boolean]) = new (Term[T] => BooleanFunApp[T]) {
-// def apply(t: Term[T]) = BooleanFunApp(fun, t)
-// }
+ // implicit def term2booleanFunAppBuilder[T >: AnyVal](fun: Term[T =>
Boolean]) = new (Term[T] => BooleanFunApp[T]) {
+ // def apply(t: Term[T]) = BooleanFunApp(fun, t)
+ // }

implicit def term2booleanFunAppBuilder(fun: Term[Any => Boolean]) = new
(Term[Any] => BooleanFunApp[Any]) {
def apply(t: Term[Any]) = BooleanFunApp(fun, t)
}

- def genericTerm2booleanFunAppBuilder[T](fun:
Term[FunctionValue[T,Boolean]]) = new (Term[T] => BooleanFunApp[T]) {
+ def genericTerm2booleanFunAppBuilder[T](fun: Term[FunctionValue[T,
Boolean]]) = new (Term[T] => BooleanFunApp[T]) {
def apply(t: Term[T]) = BooleanFunApp(fun, t)
}

- implicit def intTerm2booleanFunAppBuilder[T](fun:
Term[FunctionValue[Int,Boolean]]) =
+ implicit def intTerm2booleanFunAppBuilder[T](fun:
Term[FunctionValue[Int, Boolean]]) =
genericTerm2booleanFunAppBuilder(fun)

-// implicit def anyterm2booleanFunAppBuilder[T1, T2](fun:
Term[FunctionValue[Any, Boolean]]) = new {
-// def apply(t: TupleTerm2[Any, Any]) = BooleanFunApp(fun, t)
-// def apply(t1: Term[Any], t2: Term[Any]) = BooleanFunApp(fun,
TupleTerm2(t1, t2))
-// }
+ // implicit def anyterm2booleanFunAppBuilder[T1, T2](fun:
Term[FunctionValue[Any, Boolean]]) = new {
+ // def apply(t: TupleTerm2[Any, Any]) = BooleanFunApp(fun, t)
+ // def apply(t1: Term[Any], t2: Term[Any]) = BooleanFunApp(fun,
TupleTerm2(t1, t2))
+ // }

implicit def tuple2term2booleanFunAppBuilder[T1, T2](fun:
Term[FunctionValue[(T1, T2), Boolean]]) = new (TupleTerm2[T1, T2] =>
BooleanFunApp[(T1, T2)]) {
@@ -202,6 +207,7 @@

implicit def intTerm2IntAppBuilder(lhs: Term[Int]) = new {
def +(rhs: Term[Int]) = FunApp(FunApp(Constant(IntAdd), lhs), rhs)
+
def <(rhs: Term[Int]) = BooleanFunApp(FunApp(Constant(IntLT), lhs),
rhs)
}

@@ -224,6 +230,7 @@
}

def $(term: BooleanTerm) = Indicator(term)
+
def $$(term: BooleanTerm) = AlchemyIndicator(term)

@@ -252,7 +259,7 @@
def vectorSum[T1, T2, T3](v1: Values[T1], v2: Values[T2], v3:
Values[T3])(formula: (Var[T1], Var[T2], Var[T3]) => VectorTerm):
QuantifiedVectorSum[T1] =
vectorSum(v1) {x1 => vectorSum(v2, v3) {(x2, x3) => formula(x1, x2,
x3)}}

- def vectorSum[T1, T2, T3, T4](v1: Values[T1], v2: Values[T2], v3:
Values[T3], v4:Values[T4])(formula: (Var[T1], Var[T2], Var[T3], Var[T4]) =>
VectorTerm): QuantifiedVectorSum[T1] =
+ def vectorSum[T1, T2, T3, T4](v1: Values[T1], v2: Values[T2], v3:
Values[T3], v4: Values[T4])(formula: (Var[T1], Var[T2], Var[T3], Var[T4])
=> VectorTerm): QuantifiedVectorSum[T1] =
vectorSum(v1) {x1 => vectorSum(v2, v3, v4) {(x2, x3, x4) =>
formula(x1, x2, x3, x4)}}

def forall[T](values: Values[T])(formula: Var[T] => Term[Boolean]) = {
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/combinatorics/SpanningTreeConstraint.scala
Sat Mar 20 23:45:31 2010
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/combinatorics/SpanningTreeConstraint.scala
Sun Mar 21 11:26:30 2010
@@ -301,256 +301,3 @@

}

-
-/*
-
-David's Ptree factor
-
-class TreeFactor : public Factor {
-public:
- TreeFactor(const string& name, int slen, bool multirooted)
- : Factor(name), slen_(slen), multirooted_(multirooted) {
- int max_dim = slen_ + 1;
- worksize = max_dim * max_dim;
- tkirmat = (double *)malloc((worksize + max_dim) * sizeof(double));
- gradmat = (double *)malloc((worksize + max_dim) * sizeof(double));
- }
- virtual ~TreeFactor() {
- if ( tkirmat ) free(tkirmat);
- if ( gradmat ) free(gradmat);
- }
-
- virtual double compute_messages(Vertex v, Graph& g, double damp) {
- // cerr << "# compute_messages TreeFactor" << endl;
- EdgeIterator e = out_edges(v, g).first;
- vector<int> heads(slen_);
- for ( int kid = 1; kid <= slen_; ++kid ) {
- int tkoff = kid * slen_;
- tkirmat[tkoff + kid - 1] = 0;
- int trues = 0, trueMom = -1;
- for ( int mom = 0; mom <= slen_; ++mom ) {
- if ( mom == kid ) continue;
- const dvec& m = g[*e++].v2f;
- // cerr << "# " << mom << " -> " << kid << ": " << m << endl;
- if ( m(0) == 0 ) {
- ++trues;
- trueMom = mom;
- continue;
- }
- double score = m(1) / m(0);
- tkirmat[mom * slen_ + kid - 1] = -score;
- tkirmat[tkoff + kid - 1] += score;
- }
- if ( trues == 1 ) {
- heads[kid-1] = trueMom;
- tkirmat[tkoff + kid - 1] = 1;
- for ( int mom = 0; mom <= slen_; ++mom ) {
- if ( kid == mom ) continue;
- tkirmat[mom * slen_ + kid - 1] = ( mom == trueMom ) ? -1 : 0;
- }
- } else if ( trues > 1 ) {
- heads[kid-1] = -2;
- } else {
- heads[kid-1] = -1;
- }
- }
- slog Z = sum_tree();
- e = out_edges(v, g).first;
- if ( Z == 0 ) {
- for ( int kid = 1; kid <= slen_; ++kid ) {
- double Z = tkirmat[kid * (slen_ + 1) - 1];
- int koff = (kid - 1) * slen_;
- int head = heads[kid-1];
- for ( int mom = 0; mom <= slen_; ++mom ) {
- if ( kid != mom ) {
- dvec m(2);
- if ( head == -2 ) {
- m(1) = R_NaN;
- m(0) = R_NaN;
- } else if ( head == -1 ) {
- m(1) = 1;
- m(0) = Z + tkirmat[mom * slen_ + kid - 1];
- m /= sum(m);
- } else if ( head == mom ) {
- m = 0, 1;
- } else {
- m = 1, 0;
- }
- damp_assign(g[*e++].f2v, m, damp);
- }
- }
- }
- return 0;
- }
- for ( int kid = 1; kid <= slen_; ++kid ) {
- int koff = (kid - 1) * slen_;
- int tkoff = kid * slen_;
- int head = heads[kid-1];
- for ( int mom = 0; mom <= slen_; ++mom ) {
- if ( mom == kid ) continue;
- dvec m(2);
- if ( head == -2 ) {
- m(1) = R_NaN;
- m(0) = R_NaN;
- } else if ( head == -1 ) {
- m(1) = gradmat[koff + mom - ((mom > kid) ? 1 : 0)];
- m(0) = 1 + tkirmat[mom * slen_ + kid - 1] * m(1); // tkirmat neg
- } else if ( head == mom ) {
- m = 0, 1;
- } else {
- m = 1, 0;
- }
- damp_assign(g[*e++].f2v, m, damp);
- }
- }
- return 0;
- }
-
-private:
- virtual slog sum_tree() {}
-
-protected:
- int slen_;
- bool multirooted_;
- int worksize;
- double *tkirmat, *gradmat;
-};
-
-
-
-class PTreeFactor : public TreeFactor {
-public:
- PTreeFactor(const string& name, int slen, bool multirooted)
- : TreeFactor(name, slen, multirooted),
- sch(extents[slen+1][slen+1]),
- gch(extents[slen+1][slen+1]) {}
-
-private:
- virtual slog sum_tree() {
- int r;
- double res;
- for ( int i = 0; i < slen_*slen_; ++i ) gradmat[i] = R_NegInf;
- for ( int s = 0; s <= slen_; ++s )
- for ( int i = 0; i <= 1; ++i )
- for ( int j = 0; j <= 1; ++j )
- sch[s][s].val[i][j] = 0;
- int start = multirooted_ ? 0 : 1;
- for ( int width = 1; width <= slen_; ++width ) {
- for ( int s = start; s <= slen_; ++s ) {
- int t = s + width;
- if ( t > slen_ ) break;
- scell *cc = &sch[s][t];
- for ( int i = 0; i <= 1; ++i )
- for ( int j = 0; j <= 1; ++j )
- cc->val[i][j] = R_NegInf;
- if ( s > 0 ) {
- double lkid = log(-tkirmat[t * slen_ + s-1]);
- for ( r = s; r < t; ++r ) {
- log_incr(cc->val[0][0],
- sch[s][r].val[1][1] + sch[r+1][t].val[0][1] + lkid);
- }
- }
- double rkid = log(-tkirmat[s * slen_ + t-1]);
- for ( r = s; r < t; ++r ) {
- log_incr(cc->val[1][0],
- sch[s][r].val[1][1] + sch[r+1][t].val[0][1] + rkid);
- }
- for ( r = s; r < t; ++r ) {
- log_incr(cc->val[0][1], sch[s][r].val[0][1] + sch[r][t].val[0][0]);
- }
- for ( r = s+1; r <= t; ++r ) {
- log_incr(cc->val[1][1], sch[s][r].val[1][0] + sch[r][t].val[1][1]);
- }
- }
- }
- if ( !multirooted_ ) {
- scell *cc = &sch[0][slen_];
- cc->val[1][1] = R_NegInf;
- for ( r = 1; r <= slen_; ++r ) {
- log_incr(cc->val[1][1],
- sch[1][r].val[0][1] + sch[r][slen_].val[1][1] + log(-tkirmat[r - 1]));
- }
- }
- res = sch[0][slen_].val[1][1];
- for ( int s = 0; s <= slen_; ++s ) {
- for ( int t = s; t <= slen_; ++t ) {
- for ( int i = 0; i <= 1; ++i ) {
- for ( int j = 0; j <= 1; ++j ) {
- gch[s][t].val[i][j] = R_NegInf;
- }
- }
- }
- }
- gch[0][slen_].val[1][1] = -res;
- if ( !multirooted_ ) {
- for ( r = 1; r <= slen_; ++r ) {
- log_incr(gch[1][r].val[0][1],
- -res + sch[r][slen_].val[1][1] + log(-tkirmat[r - 1]));
- log_incr(gch[r][slen_].val[1][1],
- -res + sch[1][r].val[0][1] + log(-tkirmat[r - 1]));
- log_incr(gradmat[(r - 1) * slen_],
- -res + sch[1][r].val[0][1] + sch[r][slen_].val[1][1]);
-
- }
- }
- for ( int width = slen_; width >= 1; --width ) {
- for ( int s = start; s <= slen_; ++s ) {
- int t = s + width;
- if ( t > slen_ ) break;
- scell *gc = &gch[s][t];
- double gpar = gc->val[1][1];
- for ( r = s+1; r <= t; ++r ) {
- log_incr(gch[s][r].val[1][0], gpar + sch[r][t].val[1][1]);
- log_incr(gch[r][t].val[1][1], gpar + sch[s][r].val[1][0]);
- }
- gpar = gc->val[0][1];
- for ( r = s; r < t; ++r ) {
- log_incr(gch[s][r].val[0][1], gpar + sch[r][t].val[0][0]);
- log_incr(gch[r][t].val[0][0], gpar + sch[s][r].val[0][1]);
- }
-
- if ( s > 0 ) {
- double lgrad = R_NegInf;
- double lkid = log(-tkirmat[t * slen_ + s-1]);
- gpar = gc->val[0][0];
- for ( r = s; r < t; ++r ) {
- log_incr(gch[s][r].val[1][1],
- gpar + sch[r+1][t].val[0][1] + lkid);
- log_incr(gch[r+1][t].val[0][1],
- gpar + sch[s][r].val[1][1] + lkid);
- log_incr(lgrad,
- gpar + sch[s][r].val[1][1] + sch[r+1][t].val[0][1]);
- }
- log_incr(gradmat[(s-1) * slen_ + t-1], lgrad);
- }
-
- double rkid = log(-tkirmat[s * slen_ + t-1]);
- double rgrad = R_NegInf;
- gpar = gc->val[1][0];
- for ( r = s; r < t; ++r ) {
- log_incr(gch[s][r].val[1][1],
- gpar + sch[r+1][t].val[0][1] + rkid);
- log_incr(gch[r+1][t].val[0][1],
- gpar + sch[s][r].val[1][1] + rkid);
- log_incr(rgrad,
- gpar + sch[s][r].val[1][1] + sch[r+1][t].val[0][1]);
- }
- log_incr(gradmat[(t-1) * slen_ + s], rgrad);
- }
- }
-
- for ( int i = 0; i < slen_*slen_; ++i ) gradmat[i] = exp(gradmat[i]);
-
- return slog(res, 1);
-
- }
-
- struct scell {
- double val[2][2];
- };
- multi_array<scell, 2> sch;
- multi_array<scell, 2> gch;
-};
-
-
-*/
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/doubles/Factorizer.scala
Mon Mar 15 10:46:14 2010
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/doubles/Factorizer.scala
Sun Mar 21 11:26:30 2010
@@ -9,7 +9,7 @@
object Factorizer {
def toMultiplication(term: DoubleTerm): Multiplication[DoubleTerm] = {
unroll(term).flatten match {
- case m:Multiplication[_] => m
+ case Multiplication(args) =>
Multiplication(args.flatMap(toMultiplication(_).args))
case Exp(Sum(args)) => Multiplication(args.map(Exp(_)))
case Exp(v: VectorDotApp) =>
Multiplication(v.distribute.asInstanceOf[Sum[DoubleTerm]].args.map(Exp(_)))
case x => Multiplication(Seq(x))
@@ -17,6 +17,7 @@
}

private def unroll(term: DoubleTerm): DoubleTerm = term match {
+ case Multiplication(args) => Multiplication(args.map(unroll(_)))
case Sum(args) => Sum(args.map(unroll(_)))
case x: QuantifiedSum[_] => x.unroll
case Normalize(x) => Normalize(unroll(x))
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/util/Logging.scala
Sat Feb 27 22:30:51 2010
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/util/Logging.scala
Sun Mar 21 11:26:30 2010
@@ -21,7 +21,7 @@

var level: Level = INFO

- def isActive(level: Level) = level.level <= this.level.level
+ def isActive(level: Level) = level.level >= this.level.level

var logger: (Level, String, Class[_]) => Unit = (level, text, clazz) => {
println("%s@%s: %s".format(level.name,clazz.getName, text))