Probabilistic Soft Logic
CC-BY
Fabian M. Suchanek
27
Statements with weights
Amal Clooney is a human rights lawyer.
Propositional Logic or First‐Order Logic
Amal Clooney is rich. [70%]
Fuzzy Logic
If X is a lawyer, then X is rich. [60%]
Weighted Logics
Amal Clooney retires next year. [20%]
Probabilistic Logic
If X is a lawyer, then X is rich to degree >40%. [60%]
Probabilistic Soft Logic
->Markov-logic
2
->Propositional-logic
->Weighted-max-sat
->Fuzzy-logic
Contradictory formulas
Amal Clooney is successful.
Usually, people who are successful are not beautiful.
3
Let’s consider a contradictory set of formulas.
Contradictory formulas
Amal Clooney is successful.
Amal Clooney is successful => Amal Clooney is not beautiful.
4
Let’s consider a contradictory set of formulas.
Contradictory formulas
Amal Clooney is successful.
Amal Clooney is successful => Amal Clooney is not beautiful.
Amal Clooney is beautiful.
5
Let’s consider a contradictory set of formulas.
Contradictory formulas
Amal Clooney is successful.
Amal Clooney is successful => Amal Clooney is not beautiful.
Amal Clooney is beautiful.
6
Let’s consider a contradictory set of formulas.
Let’s consider the question which statements have to be true in order to satisfy the most formulas.
- it is not a fuzzy inference system, because the formulas contain negation
- it is a MAX SAT Problem
Here not very interesting, because there is a simple choice
to omit one of the three formulas...
Contradictory formulas with weights
7
Let’s consider a contradictory set of formulas with weights.
Let’s consider the question which statements have to be true in order to maximize the sum
of the weights of the satisfied formulas: a Weighted MAX SAT Problem.
Amal Clooney is successful [7].
Amal Clooney is successful => Amal Clooney is not beautiful [8].
Amal Clooney is beautiful [10].
8
Let’s consider a contradictory set of formulas with weights.
Let’s consider the question which statements have to be true in order to maximize the sum
of the weights of the satisfied formulas: a Weighted MAX SAT Problem.
Amal Clooney is successful [7].
Amal Clooney is successful => Amal Clooney is not beautiful [8].
Amal Clooney is beautiful [10].
Amal Clooney is successful
Amal Clooney is beautiful
World 1
0
0
World 2
0
1
World 3
1
0
World 4
1
1
Weighted MAX SAT
9
Let’s consider a contradictory set of formulas with weights.
Let’s consider the question which statements have to be true in order to maximize the sum
of the weights of the satisfied formulas: a Weighted MAX SAT Problem.
Amal Clooney is successful
Amal Clooney is beautiful
Sum of weights of sat. form.
World 1
0
0
8
World 2
0
1
18
World 3
1
0
15
World 4
1
1
17
Amal Clooney is successful [7].
Amal Clooney is successful => Amal Clooney is not beautiful [8].
Amal Clooney is beautiful [10].
Is there are way to do it faster?
Weighted MAX SAT
10
Let’s consider a contradictory set of formulas with weights.
Let’s consider the question which statements have to be true in order to maximize the sum
of the weights of the satisfied formulas: a Weighted MAX SAT Problem.
Amal Clooney is successful [7].
Amal Clooney is successful => Amal Clooney is not beautiful [8].
Amal Clooney is beautiful [10].
Weighted MAX SAT generalizes MAX SAT,
which generalizes SAT, which is NP-complete.
The Weighted MAX SAT Problem cannot be solved faster than
trying out all possible values (in general).
Weighted MAX SAT
->Weighted-max-sat
A relaxed Weighted MAX SAT problem
11
{ Amal is successful } [7]
{ ¬ Amal is successful, ¬ Amal is beautiful } [8]
{ Amal is beautiful } [10]
With the Łukasiewicz T-norm, the degree of truth of a clause ｛ａ， ｂ｝ is ｍｉｎ（ａ＋ｂ，１） .
Let’s consider a set of clauses with weights.
(For what follows, we consider the S-Implication, not the R-Implication.)
A relaxed Weighted MAX SAT problem
12
Let’s consider a set of clauses with weights.
Degrees of truth:
Amal is successful: 30%
Amal is beautiful: 70%.
With the Łukasiewicz T-norm, the degree of truth of a clause ｛ａ， ｂ｝ is ｍｉｎ（ａ＋ｂ，１） .
{ Amal is successful }:
{ ¬ Amal is successful, ¬ Amal is beautiful }:
{ Amal is beautiful }:
{ Amal is successful } [7]
{ ¬ Amal is successful, ¬ Amal is beautiful } [8]
{ Amal is beautiful } [10]
A relaxed Weighted MAX SAT problem
13
Let’s consider a set of clauses with weights.
Degrees of truth:
With the Łukasiewicz T-norm, the degree of truth of a clause ｛ａ， ｂ｝ is ｍｉｎ（ａ＋ｂ，１） .
Amal is successful: 30%
Amal is beautiful: 70%.
{ Amal is successful }: 30%
{ ¬ Amal is successful, ¬ Amal is beautiful }: 100%
{ Amal is beautiful }: 70%
{ Amal is successful } [7]
{ ¬ Amal is successful, ¬ Amal is beautiful } [8]
{ Amal is beautiful } [10]
What is the sum of the
weights of the
satisfied formulas?
A relaxed Weighted MAX SAT problem
14
Let’s consider a set of clauses with weights.
Degrees of truth:
Weighted sum:
× 7 =
2.1
× 8 =
8
× 10 =
7
17.1
With the Łukasiewicz T-norm, the degree of truth of a clause ｛ａ， ｂ｝ is ｍｉｎ（ａ＋ｂ，１） .
Amal is successful: 30%
Amal is beautiful: 70%.
{ Amal is successful }: 30%
{ ¬ Amal is successful, ¬ Amal is beautiful }: 100%
{ Amal is beautiful }: 70%
{ Amal is successful } [7]
{ ¬ Amal is successful, ¬ Amal is beautiful } [8]
{ Amal is beautiful } [10]
A relaxed Weighted MAX SAT problem
15
Let’s consider a set of clauses with weights.
With the Łukasiewicz T-norm, the degree of truth of a clause ｛ａ， ｂ｝ is ｍｉｎ（ａ＋ｂ，１） .
The degree of truth of a clause
is ...
{ Amal is successful } [7]
{ ¬ Amal is successful, ¬ Amal is beautiful } [8]
{ Amal is beautiful } [10]
(Compute
, split cases by ｂ＋ｃ＞１ )
A relaxed Weighted MAX SAT problem
16
Let’s consider a set of clauses with weights.
With the Łukasiewicz T-norm, the degree of truth of a clause ｛ａ， ｂ｝ is ｍｉｎ（ａ＋ｂ，１） .
The degree of truth of a clause
is ...
＝ ｍｉｎ（ａ ＋ ｂ， １）
＝ ｍｉｎ（ａ ＋ ｍｉｎ（ｂ＋ｃ，１）， １）
＝ ｂ＋ｃ＞１ ? ｍｉｎ（ａ＋１，１） ： ｍｉｎ（ａ＋ｂ＋ｃ， １）
＝ ｂ＋ｃ＞１? １： ｍｉｎ（ａ＋ｂ＋ｃ， １）
＝ ｂ＋ｃ＞１? ｍｉｎ（ａ＋ｂ＋ｃ， １） ： ｍｉｎ（ａ＋ｂ＋ｃ， １）
＝ ｍｉｎ（ａ＋ｂ＋ｃ，１）
(Follows also from the associativity of T-conorms.)
{ Amal is successful } [7]
{ ¬ Amal is successful, ¬ Amal is beautiful } [8]
{ Amal is beautiful } [10]
A relaxed Weighted MAX SAT problem
17
Let’s consider a set of clauses with weights.
With the Łukasiewicz T-norm, the degree of truth of a clause ｛ａ， ｂ｝ is ｍｉｎ（ａ＋ｂ，１） .
The degree of truth of a clause
is
.
Given a set Ｓ of statements with degrees of truth ｙ：Ｓ→［０，１］ ,
the degree of truth of a clause Ｃ is
.
Amal is successful: 30%; Amal is beautiful: 70%; Amal is rich: 80%
{ Amal is successful } [7]
{ ¬ Amal is successful, ¬ Amal is beautiful } [8]
{ Amal is beautiful } [10]
{ ¬ Amal is successful, ¬ Amal is beautiful }:
A relaxed Weighted MAX SAT problem
18
Let’s consider a set of clauses with weights.
With the Łukasiewicz T-norm, the degree of truth of a clause ｛ａ， ｂ｝ is ｍｉｎ（ａ＋ｂ，１） .
The degree of truth of a clause
is
.
Given a set Ｓ of statements with degrees of truth ｙ：Ｓ→［０，１］ ,
the degree of truth of a clause Ｃ is
.
Amal is successful: 30%; Amal is beautiful: 70%; Amal is rich: 80%
{ Amal is successful } [7]
{ ¬ Amal is successful, ¬ Amal is beautiful } [8]
{ Amal is beautiful } [10]
{ ¬ Amal is successful, ¬ Amal is beautiful }: 100%
Probabilistic Soft Logic in its simplest form
19
Given a set of statements Ｓ , a set Ｃ of clauses over Ｓ , and weights ｗ：Ｃ→ Ｒ ,
{ Amal is successful } [7]
{ ¬ Amal is successful, ¬ Amal is beautiful } [8]
{ Amal is beautiful } [10]
a
Probabilistic Soft Logic Inference Problem
, in its simplest form, is the task of finding truth values
ｙ：Ｓ→［０，１］ that maximize
subject to constraints of the form ｙ（ｓ）≤ｖ , where ｓ is a statement and ｖ is a real value.
[Bach et al: “Hinge-loss markov random fields and probabilistic soft logic”, JMLR, 2017]
Probabilistic Soft Logic Inference
20
{ Amal is successful } [7]
{ ¬ Amal is successful, ¬ Amal is beautiful } [8]
{ Amal is beautiful } [10]
A Probabilistic Soft Logic Inference Problem is a convex problem:
Amal is beautiful
Amal
is successful
Hit and Run
21
A Probabilistic Soft Logic Inference Problem can be solved in polynomial time
by the
“hit and run” algorithm
:
{ Amal is successful } [7]
{ ¬ Amal is successful, ¬ Amal is beautiful } [8]
{ Amal is beautiful } [10]
1)
Start at some combination of variable values
that fulfill the constraints
ｘ
ｙ
Hit and Run
22
{ Amal is successful } [7]
{ ¬ Amal is successful, ¬ Amal is beautiful } [8]
{ Amal is beautiful } [10]
1)
Start at some combination of variable values
that fulfill the constraints
2)
Pick a variable
ｘ
ｙ
A Probabilistic Soft Logic Inference Problem can be solved in polynomial time
by the
“hit and run” algorithm
:
Hit and Run
23
{ Amal is successful } [7]
{ ¬ Amal is successful, ¬ Amal is beautiful } [8]
{ Amal is beautiful } [10]
1)
Start at some combination of variable values
that fulfill the constraints
2)
Pick a variable
3)
Change its value until you find the best
ｘ
ｙ
A Probabilistic Soft Logic Inference Problem can be solved in polynomial time
by the
“hit and run” algorithm
:
Hit and Run
24
{ Amal is successful } [7]
{ ¬ Amal is successful, ¬ Amal is beautiful } [8]
{ Amal is beautiful } [10]
1)
Start at some combination of variable values
that fulfill the constraints
2)
Pick a variable
3)
Change its value until you find the best
ｘ
ｙ
A Probabilistic Soft Logic Inference Problem can be solved in polynomial time
by the
“hit and run” algorithm
:
Hit and Run
25
{ Amal is successful } [7]
{ ¬ Amal is successful, ¬ Amal is beautiful } [8]
{ Amal is beautiful } [10]
1)
Start at some combination of variable values
that fulfill the constraints
2)
Pick a variable
3)
Change its value until you find the best
4)
Repeat Steps 2-3 until convergence
ｘ
ｙ
A Probabilistic Soft Logic Inference Problem can be solved in polynomial time
by the
“hit and run” algorithm
:
Probabilistic Soft Logic
26
{ Amal is successful } [7]
{ ¬ Amal is successful, ¬ Amal is beautiful } [8]
{ Amal is beautiful } [10]
Probabilistic Soft Logic can also
-
deal with other types of potential functions instead of the Łukasiewicz T-norm
-
deal with more complex arithmetic constraints
-
be used in a Prolog-like programming language that allows expressing constraints in a
rather legible way
-
be used with an efficient solver that is specifically tailored to probabilistic soft logic
In any case:
Inference in Probabilistic Soft Logic is solvable in polynomial time!
Probabilistic Soft Logic: Summary
27
{ Amal is successful } [7]
{ ¬ Amal is successful, ¬ Amal is beautiful } [8]
{ Amal is beautiful } [10]
Inference
is the task of finding the truth values that
maximize the weighted sum of formula satisfactions.
Inference can be solved in polynomial time by
the
“hit and run” algorithm
.
In
Probabilistic Soft Logic
, formulas can have weights and statements can have fuzzy truth values.