This module provides algorithms on explanation hypergraphs, based on the ideas
of Sato (in PRISM), Klein and Manning  and Goodman . Also provided
are methods for sampling explanations from their posterior distribution  and
computing the entropy of the posterior distribution using a method which,
to my knowledge, has not been published before.
 D. Klein and C. D. Manning. Parsing and hypergraphs.
In New developments in parsing technology, pages 351–372. Springer, 2004.
 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)
weighted(X) == pair(float,X).
- top_value(+Pairs:list(pair(goal,A)), -X:A) is semidet
- Extract the value associated with the goal
'^top':top from a list
of goal-value pairs. This can be applied to explanation graphs or
the results of graph_fold/4.
- prune_graph(+P:pred(+tcall(F,_,D),-D), +Top:goal, +G1:f_graph(F,A,B,C), -G2:f_graph(F,A,B,C)) is det
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(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
F(E,D) = D (ie no annotation), then P should be (=). Since PlDoc won't accept high-order
type terms, we write
tcall is like
call for types.
- graph_switches(+G:graph, -SWs:list(switch(_))) is det
- Extract list of switches referenced in an explanation graph.
- graph_fold(+SR:sr(A,B,C,T), ?P:params(T), +G:graph, -R:list(pair(goal,W))) is det
- Folds the semiring SR over the explanation graph G. Produces R, a list of pairs
of goals in the original graph with the result of the fold for that goal. Different
semirings can produce many kinds of parsing analysis. The algebra is not strictly a
semiring, as the times and plus operators have 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:
- r(pred(+T, -A), pred(+C, -C), pred(+A, +B, -B), pred(+B, +C, -C))
- A term containing the operators in restricted forms as callable terms.
The unit and zero for the times and plus operators respectively are looked up in m_zero/2.
- Finds the best single explanation for each goal. Parameters are assumed to be probabilities.
- ann(sr(A, B, C, T))
- Annotates the original hypergraph with the results of any semiring analysis.
- sr(A1, B1, C1, T)-sr(A1, B1, C1, T)
- For each goal, return a pair of results from any two semiring analyses.
Various standard analysis can be obtained by using the appropriate semiring:
- r(=, =, mul, add)
- Inside algorithm from linear probabilities.
- r(=, lse, add, cons)
- Inside algorithm with log-scaling from log probabilities
- r(=, =, mul, max)
- Viterbi probabilities.
- graph_inside(+G:graph, ?P:sw_params, -IG:igraph) is det
- igraph_sample_tree(+IG:igraph, +H:goal, -Ts:list(tree)) is det
- Uses prob effect to sample a tree from a graph annotated with inside
probabilities, as produced by graph_inside/3/
- igraph_entropy(+S:scaling, +IG:igraph, -Es:list(pair(goal,float))) is det
- Explanation entropies from annotated explanation graph.
- graph_counts(+Meth:counts_method, +PSc:scaling, +G:graph, P:sw_params, C:sw_params, LP:float) is det
- Compute expected switch counts C from explanation graph G with switch parameters
P. Uses automatic differentiation of the expression for the log of the inside
probability LP of the graph. Params can be unbound - binding them later triggers
the computations required to yield numerical values in the result.
counts_method ---> io(scaling); vit.
- accum_stats(+Acc:pred(fmap(int),fmap(int)), +GSWs:pred(fmap(int),list(switch(_))), -Stats:sw_params) is det
- tree_stats(+T:tree, -C:sw_params) is det
The following predicates are exported, but not or incorrectly documented.
- sw_trees_stats(Arg1, Arg2, Arg3)