The ambition of Arti cial Intelligence is to solve problems without human intervention. Often the problem description is given in human (natural) language. Therefore it is crucial to nd an automatic way to understand a text written by a human. The research eld concerned with the interactions between computers and natural languages is known under the name of Natural Language Processing (NLP), one of the most studied elds of Arti cial Intelligence. In this paper we show that Probabilistic Logic Programming (PLP) is a suitable approach for NLP in various scenarios. For this purpose we use cplint on SWISH, a web application for Probabilistic Logic Programming. cplint on SWISH allows users to perform inference and learning with the framework cplint using just a web browser, with the computation performed on the server.
Probabilistic Logic Programming (PLP) [
Many systems have been proposed for reasoning with PLP. Even if they are
freely available for download, using them usually requires a complex installation
process and a steep learning curve. In order to mitigate these problems, we
developed cplint on SWISH [
cplint on SWISH uses the reasoning algorithms included in the cplint suite, including exact and approximate inference and parameter and structure learning.
The paper is organized as follows. Section 2 provides an overview of the distribution semantics, Section 3 illustrates some examples of how to represent some of the most famous NLP models in PLPs. Finally, section 5 concludes the paper.
All the examples in the paper named as <name>.pl can be accessed online at http://cplint.lamping.unife.it/example/inference/<name>.pl. 2
The distribution semantics [11] is one of the most successful approaches for representing probabilistic information in Logic Programming and it is at the basis of many languages, such as Independent Choice Logic, PRISM, Logic Programs with Annotated Disjunctions (LPADs) and ProbLog.
We consider rst the discrete version of probabilistic logic programming languages. In this version, each atom is associated with a Boolean random variable that can assume values true or false representing the its presence or absence in the program. The facts and rules of the program specify the dependences among the truth value of atoms and the main inference task is to compute the probability that a ground query is true, often conditioned on the truth of another ground goal, the evidence. All the languages following the distribution semantics allow the speci cation of alternatives either for facts and/or for clauses. We present here the syntax of LPADs because it is the most general [18].
An LPAD is a nite set of annotated disjunctive clauses of the form hi1 : i1; : : : ; hini : ini :- bi1; : : : ; bimi : where bi1; : : : ; bimi are literals, hi1; : : : hini are atoms and i1; : : : ; ini are real numbers in the interval [0; 1]. This clause can be interpreted as \if bi1; : : : ; bimi is true, then hi1 is true with probability i1 or . . . or hini is true with probability ini ."
Given an LPAD P , the grounding ground (P ) is obtained by replacing variables with terms from the Herbrand universe in all possible ways. If P does not contain function symbols and P is nite, ground (P ) is nite as well.
ground (P ) is still an LPAD from which we can obtain a normal logic program by selecting a head atom for each ground clause. This normal program, called \world", is assigned a probability by multiplying the probabilities of all the head atoms chosen. In this way we get a probability distribution over worlds from which we can de ne a probability distribution over the truth values of a ground atom: the probability of an atom q being true is the sum of the probabilities of the worlds where q is true, that can be checked because the worlds are normal programs that we assume have a two-valued well-founded model.
This semantics can be given also a sampling interpretation: the probability of a query q is the fraction of worlds, sampled from the distribution over worlds, where q is true. To sample from the distribution over worlds, you simply randomly select a head atom for each clause according to the probabilistic annotations. Note that you don't even need to sample a complete world: if the samples you have taken ensure the truth value of q is determined, you don't need to sample more clauses.
To compute the conditional probability P (qje) of a query q given evidence e, you can use the de nition of conditional probability, P (qje) = P (q; e)=P (e), and compute rst the probability of q; e (the sum of probabilities of worlds where both q and e are true) and the probability of e and then divide the two.
If the program P contains function symbols, a more complex de nition of the
semantics is necessary, because ground (P ) is in nite, a world would be obtained
by making an in nite number of choices and so its probability, the product of
in nite numbers all smaller than one, would be 0. In this case you have to work
with sets of worlds and use Kolmogorov's de nition of probability space [
NLP
In NLP two common tasks are to check whether a sentence respects a grammar or to tag each word of a sentence with a part-of-speech (POS) tag. For NLP the grammars that are used in the theory of formal languages such as context free grammars or left corner grammars do not work well because the rules are too strict. Natural language is more exible and is characterized by many exceptions to rules. To model natural language, probabilistic versions of the grammars above have been developed, such as Probabilistic Context Free Grammars or Probabilistic Left Corner Grammars. Similarly, for POS tagging, statistical tools such as Hidden Markov Models give good results. 3.1
A Probabilistic Context-Free Grammar (PCFG) consists of:
! 1. A context-free grammar G = (N; ; I; R) where N is a nite set of nonterminal symbols, is a nite set of terminal symbols, I 2 N is a distinguished start symbol, R is a nite set of rules of the form X ! Y1; : : : ; Yn, where X 2 N and Yi 2 (N [ ). 2. A parameter for each rule ! 2 R. Therefore we have probabilistic rules of the form :
This kind of models can be represented by PLPs. For instance consider the program pcfg.pl (adapted from [15]) shown below. It represents the PCFG f0:2 : S ! aS; 0:2 : S ! bS; 0:3 : S ! a; 0:3 : S ! bg, where fSg is N and fa; bg is . pcfg(L):- pcfg(['S'],[],_Der,L,[]). pcfg([A|R],Der0,Der,L0,L2):rule(A,Der0,RHS), pcfg(RHS,[rule(A,RHS)|Der0],Der1,L0,L1), pcfg(R,Der1,Der,L1,L2). pcfg([A|R],Der0,Der,[A|L1],L2):\+ rule(A,_,_), pcfg(R,Der0,Der,L1,L2). pcfg([],Der,Der,L,L). rule('S',Der,[a,'S']):0.2; rule('S',Der,[b,'S']):0.2; rule('S',Der,[a]):0.3; rule('S',Der,[b]):0.3.
In this example if we want to perform exact inference and we want to ask for the probability of the string \abaa", we have to submit to cplint on SWISH the query prob(pcfg([a,b,a,a]),Prob). and we obtain 0.0024 (In this case the string is not ambiguous so there exists only one derivation with probability 0:2 0:2 0:2 0:3 = 0:0024). 3.2
A Probabilistic Left Corner Grammar (PLCG) is a probabilistic version of leftcorner grammar which uses the same set of rules as a PCFG. Whereas PCFGs assume top-down parsing, PLCGs are based on bottom-up parsing. PLCGs set probabilities not to expansion of non-terminals but to three elementary operations in bottom-up parsing, i.e. shift, attach and project. As a result they de ne a di erent class of distributions from PCFGs.
Programs for PLCGs look very di erent from those for PCFGs. The program plcg.pl (adapted from [14]) represent a PLCG that has as CFG rules fS ! SS; S ! a; S ! bg, where fSg is N and fa; bg is plc(Ws) :- g_call(['S'],Ws,[],[],_Der). g_call([],L,L,Der,Der). g_call([G|R], [G|L],L2,Der0,Der) :- % shift terminal(G), g_call(R,L,L2,Der0,Der). g_call([G|R], [Wd|L] ,L2,Der0,Der) :\+ terminal(G), first(G,Der0,Wd), lc_call(G,Wd,L,L1,[first(G,Wd)|Der0],Der1), g_call(R,L1,L2,Der1,Der). lc_call(G,B,L,L1,Der0,Der) :- % attach lc(G,B,Der0,rule(G, [B|RHS2])), attach_or_project(G,Der0,attach), g_call(RHS2,L,L1,[lc(G,B,rule(G, [B|RHS2])),attach|Der0],Der). lc_call(G,B,L,L2,Der0,Der) :- % project lc(G,B,Der0,rule(A, [B|RHS2])), attach_or_project(G,Der0,project), g_call(RHS2,L,L1,[lc(G,B,rule(A, [B|RHS2])),project|Der0],Der1), lc_call(G,A,L1,L2,Der1,Der). lc_call(G,B,L,L2,Der0,Der) :\+ lc(G,B,Der0,rule(G,[B|_])), lc(G,B,Der0,rule(A, [B|RHS2])), g_call(RHS2,L,L1,[lc(G,B,rule(A, [B|RHS2]))|Der0],Der1), lc_call(G,A,L1,L2,Der1,Der). attach_or_project(A,Der,Op) :
lc(A,A,Der,_), attach(A,Der,Op). attach_or_project(A,Der,attach) :
\+ lc(A,A,Der,_). lc('S','S',_Der,rule('S',['S','S'])). lc('S',a,_Der,rule('S',[a])). lc('S',b,_Der,rule('S',[b])). first('S',Der,a):0.5; first('S',Der,b):0.5. attach('S',Der,attach):0.5; attach('S',Der,project):0.5. terminal(a). terminal(b).
Besides exact inference, cplint o ers also approximate inference by Monte Carlo sampling. If we want to know the probability that the string 'ab' is generated by the grammar, we have to write the query mc prob(plc([a,b]),P). and cplint on SWISH will return 0:031. 3.3
In a Hidden Markov Model (HMM) there are states, transitions between states, and symbols emitted by the states. Usually there are two kinds of probabilities in a HMM: transition probabilities, i.e. the probability of a transition from one state to another, and emission or output probabilities, i.e. the probability of a certain state emitting a certain symbol.
HMM can be used for POS tagging words can be considered as output symbols and a sentence the sequence of output symbols emitted by an HMM. In this case, the states are POS tags and the sequence of states that most probably gave the sentence as the sequence of output symbols can be considered as the POS tagging of the sentence.
In the program hmmpos.pl (adapted from http://www.ling.gu.se/~lager/
Spaghetti/spaghetti.html, [
trans(start,Q0,[]),hmm(Q0,[],S0,O),reverse(S0,S). hmm(Q,S0,S,[L|O]):trans(Q,Q1,S0), out(L,Q,S0), hmm(Q1,[Q|S0],S,O). hmm(_,S,S,[]). trans(start,det,_):0.30; trans(start,aux,_):0.20; trans(start,v,_):0.10; trans(start,n,_):0.10; trans(start,pron,_):0.30. trans(det,det,_):0.20; trans(det,aux,_):0.01; trans(det,v,_):0.01; trans(det,n,_):0.77; trans(det,pron,_):0.01. trans(aux,det,_):0.18; trans(aux,aux,_):0.10; trans(aux,v,_):0.50; trans(aux,n,_):0.01; trans(aux,pron,_):0.21. trans(v,det,_):0.36; trans(v,aux,_):0.01; trans(v,v,_):0.01; trans(v,n,_):0.26; trans(v,pron,_):0.36. trans(n,det,_):0.01; trans(n,aux,_):0.25; trans(n,v,_):0.39; trans(n,n,_):0.34; trans(n,pron,_):0.01. trans(pron,det,_):0.01; trans(pron,aux,_):0.45; trans(pron,v,_):0.52; trans(pron,n,_):0.01; trans(pron,pron,_):0.01. out(a,det,_). out(can,aux,_). out(can,v,_). out(can,n,_). out(he,pron,_).
For instance we want to know the most frequent state sequence for the sentence \he can can a can". In this case it corresponds to the most frequent part-of-speech sequence for that sentence. By using the cplint syntax we query mc sample arg( hmm(S,[he,can,can,a,can]),100,S,O)., we should obtain the sequence [pron, aux, v, det, n]. 4
PRISM [12] is one of the most in uential systems for the application of PLP to NLP. PRISM uses a symbolic-statistical modeling language that follows the distribution semantics that di ers from ICL/LPADs/ProbLog because the programs are required to satisfy some constraints, namely that clauses have mutually exclusive bodies and literals in the body of clauses are mutually independent. This restriction is satis ed by all the models presented in this paper and in fact all of them are inspired by models for the PRISM system. However, the restriction severely limits the expressiveness and may prove too constraining for more complex models.
In [
Other approaches for parameter learning exploit counting for PLCGs starting
from a parse tree [
Applying (probabilistic) inductive logic programming (ILP) to NLP was
investigated in [
PCFGs, PLCGs and HMMs are some of the most widely used models in NLP. In this paper we show that is possible to represent these models with Probabilistic Logic Programs. All the proposed examples are available in cplint on SWISH, a web application for PLP.
A complete online tutorial of cplint on SWISH [
We are currently considering a version of probabilistic De nite Clause Grammars, where the probability distribution is de ned on the possible non-terminals with the same expansion, rather than on the possible expansions of a nonterminal. This extension could be mapped naturally on LPADs, and could be applied to probabilistic parsing of ambiguous grammars.
Acknowledgement This work was supported by the \GNCS-INdAM". 10. Roark, B., Johnson, M.: E cient probabilistic top-down and left-corner parsing.
CoRR cs.CL/0008017 (2000) 11. Sato, T.: A statistical learning method for logic programs with distribution semantics. In: Sterling, L. (ed.) ICLP-95. pp. 715{729. MIT Press, Cambridge, Massachusetts (1995) 12. Sato, T., Kameya, Y.: PRISM: a language for symbolic-statistical modeling. In:
IJCAI 97. vol. 97, pp. 1330{1339 (1997) 13. Sato, T., Kameya, Y.: Parameter learning of logic programs for symbolic-statistical modeling. J. Artif. Intell. Res. 15, 391{454 (2001) 14. Sato, T., Kameya, Y., Kurihara, K.: Variational bayes via propositionalized probability computation in prism. Ann. Math. Artif. Intell. 54(1-3), 135{158 (2008) 15. Sato, T., Kubota, K.: Viterbi training in prism. Theor. Pract. Log. Prog. 15(02), 147{168 (2015) 16. Uytsel, D.H.V., Compernolle, D.V.: Language modeling with probabilistic left corner parsing. Computer Speech & Language 19(2), 171{204 (2005) 17. Van Uytsel, D.H., Van Compernolle, D., Wambacq, P.: Maximum-likelihood training of the plcg-based language model. In: ASRU-2001. pp. 210{213. IEEE (2001) 18. Vennekens, J., Verbaeten, S., Bruynooghe, M.: Logic Programs With Annotated Disjunctions. In: Demoen, B., Lifschitz, V. (eds.) Logic Programming: 20th International Conference, ICLP 2004, Saint-Malo, France, September 6-10, 2004. Proceedings. LNCS, vol. 3132, pp. 431{445. Springer Berlin Heidelberg, Berlin Heidelberg, Germany (2004), http://dx.doi.org/10.1007/978-3-540-27775-0_30