6be7d8ee
 Francisco Coelho
Organised text
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
# Probabilistic Answer Set Programming
## Non-stratified programs
> Minimal example of **non-stratified program**.
The following annotated LP, with clauses $c_1, c_2, c_3$ respectively, is non-stratified (because has a cycle with negated arcs) but no head is disjunctive:
```prolog
0.3::a. % c1
s :- not w, not a. % c2
w :- not s. % c3
```
This program has three stable models:
$$
\begin{aligned}
m_1 &= \set{ a, w } \cr
m_2 &= \set{ \neg a, s } \cr
m_3 &= \set{ \neg a, w }
\end{aligned}
$$
The probabilistic clause `0.3::a.` defines a **total choice**
$$
\Theta = \set{
\theta_1 = \set{ a },
\theta_2 = \set{ \neg a }
}
$$
such that
$$
\begin{aligned}
P(\Theta = \set{ a }) &= 0.3\cr
P(\Theta = \set{ \neg a }) &= 0.7 \cr
\end{aligned}
$$
> While it is natural to extend $P( m_1 ) = 0.3$ from $P(\theta_1) = 0.3$ there is no clear way to assign $P(m_2), P(m_3)$ since both models result from the total choice $\theta_2$.
Under the **CWA**, $\sim\!\!q \models \neg q$, so $c_2, c_3$ induce probabilities:
$$
\begin{aligned}
p_a &= P(a | \Theta) \cr
p_s &= P(s | \Theta) &= (1 - p_w)(1 - p_a) \cr
p_w &= P(w | \Theta) &= (1 - p_w)
\end{aligned}
$$
from which results
$$
\begin{equation}
p_s = p_s(1 - p_a).
\end{equation}
$$
So, if $\Theta = \theta_1 = \set{ a }$ (one stable model):
- We have $p_a = P(a | \Theta = \set{ a }) = 1$.
- Equation (1) becomes $p_s = 0$.
- From $p_w = 1 - p_s$ we get $P(w | \Theta) = 1$.
and if $\Theta = \theta_2 = \set{ \neg a }$ (two stable models):
- We have $p_a = P(a | \Theta = \set{ \neg a }) = 0$.
- Equation (1) becomes $p_s = p_s$; Since we know nothing about $p_s$, we let $p_s = \alpha \in \left[0, 1\right]$.
- We still have the relation $p_w = 1 - p_s$ so $p_w = 1 - \alpha$.
We can now define the **marginals** for $s, w$:
$$
\begin{aligned}
P(s) &=\sum_\theta P(s|\theta)P(\theta)= 0.7\alpha \cr
P(w) &=\sum_\theta P(s|\theta)P(\theta)= 0.3 + 0.7(1 - \alpha) \cr
\alpha &\in\left[ 0, 1 \right]
\end{aligned}
$$
> The parameter $\alpha$ not only **expresses insufficient information** to sharply define $p_s$ but also **relates** $p_s$ and $p_w$.
## Disjunctive heads
> Minimal example of **disjunctive heads** program.
Consider this LP
```prolog
0.3::a.
b ; c :- a.
```
with three stable models:
$$
\begin{aligned}
m_1 &= \set{ \neg a } \cr
m_2 &= \set{ a, b } \cr
m_3 &= \set{ a, c }
\end{aligned}
$$
Again, $P(m_1) = 0.3$ is quite natural but there are no clear assignments for $P(m_2), P(m_3)$.
The total choices here are
$$
\Theta = \set{
\theta_1 = \set{ a }
\theta_2 = \set{ \neg a }
}
$$
such that
$$
\begin{aligned}
P(\Theta = \set{ a }) &= 0.3\cr
P(\Theta = \set{ \neg a }) &= 0.7 \cr
\end{aligned}
$$
and the LP induces
$$
P(b \vee c | \Theta) = P(a | \Theta).
$$
Since the disjunctive expands as
$$
\begin{equation}
P(b \vee c | \Theta) = P(b | \Theta) + P( c | \Theta) - P(b \wedge c | \Theta)
\end{equation}
$$
and we know that $P(b \vee c | \Theta) = P(a | \Theta)$ we need two independent parameters, for example
$$
\begin{aligned}
P(b | \Theta) &= \beta \cr
P(c | \Theta) &= \gamma \cr
\end{aligned}
$$
where
$$
\begin{aligned}
\alpha & \in \left[0, 0.3\right] \cr
\beta & \in \left[0, \alpha\right]
\end{aligned}
$$
This example also calls for reconsidering the CWA since it entails that **we should assume that $b$ and $c$ are conditionally independent given $a$.**
|