Did you know ... | Search Documentation: |
Pack ccprism -- prolog/ccprism/graph.pl |
This module provides algorithms on explanation hypergraphs, based on the ideas of Sato (in PRISM), Klein and Manning [1] and Goodman [2]. Also provided are methods for sampling explanations from their posterior distribution [2] and computing the entropy of the posterior distribution using a method which, to my knowledge, has not been published before.
[1] D. Klein and C. D. Manning. Parsing and hypergraphs. In New developments in parsing technology, pages 351–372. Springer, 2004.
[2] J. Goodman. Parsing inside-out. PhD thesis, Division of Engineering and Applied Sciences, Harvard University, 1998.
tree ---> goal - list(tree). igraph == f_graph(pair,float,float,float) == list(pair(goal,weighted(list(weighted(list(weighted(factor))))))) weighted(X) == pair(float,X).
'^top':top
from a list
of goal-value pairs. This can be applied to explanation graphs or
the results of graph_fold/4.f_graph(F,A,B,C) == list(pair(goal,tcall(F,A,list(tcall(F,B,list(tcall(F,C,factor)))))))
Prune a graph or annotated graph to keep only goals reachable from a given top goal.
With apologies, the type is quite complicated. The input and output graphs are lists of goals paired
with annotated explanations. The type of an annotation is described by the type constructor
F: F(E,D)
is the type of a D
annotated with an E
. The first argument P knows how to strip
off any type of annotation and return the D
. This is how we dig down into the annotated explanations
to find out which subgoals are referenced. For example, if F = pair
, then P should be snd
.
If F(E,D) = D
(ie no annotation), then P should be (=). Since PlDoc won't accept high-order
type terms, we write F(E,D)
as tcall(F,E,D)
, where tcall
is like call
for types.
A, B -> B
and B, C -> C
respectively as this makes it easier to avoid unnecessary operations like list appending.
An algebra of type sr(A,B,C,T)
must provide 4 operators and 2 values:
inject : T, factor -> A times : A, B -> B plus : B, C -> C project : goal, C -> A, W unit : B zero : C
Semirings are extensible using multifile predicates sr_inj/4, sr_proj/5, sr_times/4, sr_plus/4, sr_unit/2 and sr_zero/2.
Available semirings in this module:
Various standard analysis can be obtained by using the appropriate semiring:
counts_method ---> io(scaling); vit.
The following predicates are exported, but not or incorrectly documented.