Re: Heuristic backtrack in Prolog?

I
"Panu Kalliokoski" <panu.kalliokoski@xxxxxxxxxxx> wrote in message
news:5A8bi.37$M32.16@xxxxxxxxxxxxxxxx

Another execution environment I've needed is a heuristic parser where each
alternative parse has a probability. When we are making a parse in a
branch whose current probability is, say, 0.6, and we have an alternative
whose probability is, say, 0.3, we give the alternative a combined
probability of 0.18 and jump to some other branch of execution if its
probability is higher. Ordinary Prolog backtracking is a special case of
such an environment where fail :- probability(0). Code would look
something like:

np(In, Parse, Out) :-
article(In, Art, Out1),
probability(0.9),
attribute(Out1, Attr, Out2),
np(Out2, Rest, Out),
Parse = np(Attr, Rest).

np(In, Parse, Out) :-
attribute(In, Attr, Out1),
probability(0.3),
np(Out1, Rest, Out),
Parse = np(Attr, Rest).

np(In, Parse, Out) :-
probability(0.2),
noun(In, Parse, Out).

I know approximately how to do this in Scheme using continuations, but how
do I write the probability/1 predicate in Prolog, or something similar?

Please take a look at PRISM (http://sato-www.cs.titech.ac.jp/prism/), which
is an extension of Prolog with support of probabilistic reasoning and
learning. You can not only do probabilistic parsing using given probability
distributions, but also learning to estimate probability distributions from
given data. I am sure your life will be much easier if you use PRISM instead
of Scheme.

Cheers,
Neng-Fa




.

Relevant Pages

  • Re: what robots see
    ... A more general image parser formultates a) grouping ... grouping hypotheses can be nested, so a parse ... The idea is to find a most probable parse. ... regions to pull up detail (eg. probability distributions over sets of ...
    (comp.ai.philosophy)
  • Heuristic backtrack in Prolog?
    ... I'm trying to learn Prolog because it's a very interesting language and seems to be on par with LISP with respect to freedom of expression:) My own experience with Prolog is limited to writing some parsers and recursive predicates such as permutations and so on. ... Another execution environment I've needed is a heuristic parser where each alternative parse has a probability. ... Ordinary Prolog backtracking is a special case of such an environment where fail:- probability. ...
    (comp.lang.prolog)
  • Re: Heuristic backtrack in Prolog?
    ... which is an extension of Prolog with support of probabilistic reasoning and learning. ... You can not only do probabilistic parsing using given probability distributions, but also learning to estimate probability distributions from given data. ... because I like the elegance of Prolog a lot. ...
    (comp.lang.prolog)
  • Re: Heuristic backtrack in Prolog?
    ... You can not only do probabilistic parsing using given probability ... distributions, but also learning to estimate probability distributions from ... That shows how to implement an A* heuristic search in prolog. ...
    (comp.lang.prolog)