LFIT: Learning from Interpreta2on Transi2on(LFIT: 解釈遷移からの学習)
Katsumi Inoue井上 克⺒

Na2onal Ins2tute of Informa2cs
国⽴情報学研究所

SOKENDAI (The Graduate University for Advanced Studies)
総合研究⼤学院⼤学

Tokyo Ins2tute of Technology
東京⼯業⼤学The 100th JSAI SIG-FPAI Mee1ng
⼈⼯知能学会 第100回⼈⼯知能基本問題研究会

Kumamoto, March 27th, 2016

Members Involved
Katsumi Inoue (NII/SOKENDAI/Tokyo Tech, Japan)
Chiaki Sakama (Wakayama University, Japan)
Tony Ribeiro (SOKENDAI → École Centrale de Nantes,
France)Morgan Magnin (École Centrale de Nantes/NII)David MarSnez (Ins2tut de Robò2ca i Informà2ca
Industrial, Spain)

Enguerrand Gentet (Université Paris-Sud, France)
and their colleagues

Contents• Mo$va$on: Modeling in Dynamic Environments• Principles: LF1T (Learning from 1-Step Transi2ons)– Bo[om-Up Algorithm (generaliza2on)– BDD Op2miza2on– Top-Down Algorithm (specializa2on)• Extensions: LFkT (Learning Markov(k) Systems),
Mul2-Valued/Asynchronous/Probabilis2c Extensions• Applica$ons: Biology, Robo2cs, AGI, etc.
• Ongoing Work: DREAM Challenges, NN-LFIT

Contents• Mo$va$on:– Modeling in Dynamic Environments• Principles• Extensions• Applica$ons• Ongoing WorkAI in Dynamic Environments• Iden2fying the model of a system in dynamic
environments in order to achieve tasks even when
unknown situa2ons are encountered.
– Phase 1: The internal model is constructed by learning fromenvironment and interac2on with other systems.
– Phase 2: The model is used for choosing the next ac2on.
– Phase Update: The eﬀect/result of an ac2on aﬀects theenvironment and updates 2me-series data, history,
experience and goals. Then the model is updated
accordingly.
– The agent also interacts with other agents, and its internal
model is reﬁned by such interac2ons．

AgentBackground
Knowledge?

ModelInternal
State

History/
Experience

Decision
Making

Machine Learning

Goal
Time-Series
Data

Dynamic Transi2on
Model Checking

Ac$on

Other Agents

Dynamic Environments

Ac$on
Ac$on

Vector Representa2ons of Worlds( x1 ,…, xn ) = (a1 ,…, an ) : static
t
1

t

t
1

t

( x ,…, xn ) = (a ,…, an ) : dynamic
Heat map: Transcriptome data for a subset of
eukaryotic TF II B (TFB) perturbations(Facciotti, M., et al., PNAS, Vo.104, 2007)

h[ps://www.tensorﬂow.org/versions/r0.7/tutorials/word2vec/index.html

Network Representa2ons of Models• Mammalian Cell Cycle Network Product ← Rules leading to ac2vity

Each node represents the ac2vity of a key regulatory element, whereas the edges represent
cross-regula2ons. Blunt arrows stand for inhibitory eﬀects, normal arrows for ac2va2ons.
(Fauré et al., Bioinforma1cs, 22, 2006)

Logical Representa2ons of Models• Boolean Networks• Cellular Automata
Game of Lifec( xi, yj, t+1) ← c( xi, yj, t), 2 { c( xi−1, yj−1, t), c( xi, yj−1, t), c( xi+1, yj−1, t), c( xi−1, yj, t),c( xi+1, yj, t), c( xi−1, yj+1, t), c( xi, yj+1, t), c( xi+1, yj+1, t) } 3.
C( xi, yj, t+1) ← not c( xi, yj, t), 3 { c( xi−1, yj−1, t), c( xi, yj−1, t), c( xi+1, yj−1, t), c( xi−1, yj, t),c( xi+1, yj, t), c( xi−1, yj+1, t), c( xi, yj+1, t), c( xi+1, yj+1, t) } 3.

Wolfram’s Rule 30
xit+1 = xi-1t(xit ∨ xi+1t)

The history of the generated
pa[erns with the star2ng
conﬁgura2on (top) that consistsof a 1 surrounded by 0's.

Learning From Interpreta2on Transi2on (LFIT)• Input: Time-Series Data
(Vector-Representa2on)
0-1(Boolean) vectors= interpreta$ons• Output: Dynamical Model(Network/Logical-Representa2on)
Boolean networks= normal logic program
c.f. (Inoue, IJCAI-11)• LFIT—ﬁrstly presented by Inoue and Sakama at
ILP 2012 as a short paper

Contents• Mo$va$on• Principles:
LF1T (Learning from 1-Step Transi2ons)– Bo[om-Up Algorithm (generaliza2on)– BDD Op2miza2on– Top-Down Algorithm (specializa2on)• Extensions• Applica$ons• Ongoing Work

Learning From Interpreta2on Transi2on (LFIT)
Background
Knowledge
History/
Experience

Agent
Model
?

Internal
State

Extensions:• delays (k-Markov system)• mul2-valued variables• asynchronous update
Ac$on• nondeterminis2c/
probabilis2c transi2ons

A[ractor

Time-Series
Data

Dynamic Environments

Normal Logic Programs• A normal logic program (NLP) P is a set of rules:

H ← A1 ∧ … ∧ Am ∧ ¬B1 ∧ … ∧ ¬Bn (m,n ≥ 0)
where H, Ai and Bj are atoms and ¬ is (default) nega1on.
P is deﬁnite if n = 0 for every rule in P.
ground(P) : the set of ground instances of all rules in P.
The Herbrand base HBP is the set of ground atoms in language(P).
An (Herbrand) interpreta1on I of an NLP P: I ⊆ HBP (I ∈ 2HBP).
I ∈ 2HBP sa1sﬁes (╞ ) a ground rule of the form:
H ← A1 ∧ … ∧ Am ∧ ¬B1 ∧ … ∧ ¬Bniﬀ ∀i. Ai ∈ I and ∀j. Bj ∉ I imply that H ∈ I.
• I is an (Herbrand) model of P if I sa2sﬁes all rules in ground(P).
•
•
•
•
•

TP operator• TP (I) := { H | H ← L1 ∧...∧ Ln ∈ ground(P), I ╞ L1 ∧...∧ Ln }.
• When P is a deﬁnite program, I ╞ A1 ∧...∧ Am iﬀ ∀i. Ai ∈ I.
In this case, TP operator is monotone, and the sequence
I0 = {}, In+1 = TP(In) (n=0,...)
reaches the least ﬁxpoint of TP, denoted as I* = TP↑ω: I* = TP (I*).
TP↑ω is the least model of P (van Emden & Kowalski, 1976).
• When P is a normal program,I ╞ A1 ∧…∧ Am ∧ ¬B1 ∧…∧ ¬Bn iﬀ ∀i. Ai ∈ I and ∀j. Bj∉ I.
In this case, TP is non-monotone (Apt, Blair & Walker, 1988).
• The orbit of I wrt P (Blair et al., 1997) is 〈TPk(I)〉k=0,1,2,…,
where TP0(I) = I, TPk+1(I) = TP(TPk(I)) for k = 0, 1, 2, …. .

TP operator, supportedness, comple2on• An interpreta2on I is supported (Apt, Blair & Walker, 1988)
if ∀A ∈ I. ∃(A ←A1∧…∧Am∧¬B1 ∧…∧¬Bn) ∈ ground(P)such that ∀i. Ai ∈ I and ∀j. Bj ∉ I.
• Prop.: An interpreta2on I is a model of P iﬀ TP (I) ⊆ I .
• Prop.: I is supported iﬀ I ⊆ TP (I) .
• Cor.: I is a supported model of P iﬀ I = TP (I) .
• Prop.: I is a model of Comp(P) iﬀ I = TP (I) , where Comp(P)is Clark’s comple2on of P .
• Cor.: I is a supported model of P iﬀ I is a model of Comp(P).

TP operator for NLPs
• p ← q.
• p ← ¬r.
• r ← p ∧ ¬q.

1.
2.
3.
4.
5.
6.

{}
{p}
{p,r}
{r}
{}
repeat 2—5•••

TP is non-monotone.
No ﬁxpoint is reached in general.
No supported model exists here.

Learning Logical Dynamics of Systems• Learning ac2on theories in ILP– Event calculus: Moyle & Muggleton (1997), Moyle (2003)– Logic programs: with situa2on calculus: Otero (2003, 2005)– Ac2on languages: Inoue et al. (2005), Tran & Baral (2009)– Probabilis2c logic programs: Corapi et al. (2011)• Rela2onal reinforcement learning– Logic programs: Džeroski et al. (2001)• Abduc2ve ac2on learning– Abduc2ve event calculus: Eshghi (1988), Shanahan (2000)• Learning Petri nets : Srinivasan et al. (2015)• Ac2ve learning of ac2on models– STRIPS-like: Rodrigues et al. (2011)••

These works suppose applica2ons to robo2cs and bioinforma2cs.
However, it is hard to infer rules of systems dynamics due to presence of
posi2ve and nega2ve feedbacks.

LFIT: Learning from Interpreta2on Transi2ons(Inoue, Ribeiro & Sakama, Machine Learning, 2014)• Herbrand interpreta2on I: a state of the world• Logic program P: a state transi1on system, which maps an
Herbrand interpreta2on into another interpreta2on• Next state TP(I): where TP is the immediate consequence operator(TP operator).
• Learning sezng:– Given: a set of pairs of Herbrand interpreta2ons (I,J) such thatJ = TP(I),– Induce a normal logic program P.
• c.f. learning from interpreta2ons (LFI)– Given: a set S of Herbrand interpreta2ons,– Induce a program P whose models are exactly S.

Subsump2on, least generaliza2on• For two rules R1, R2 with the same head, R1 subsumes R2 if there
is a subs2tu2on θ s.t. b+(R1)θ ⊆ b+(R2) and b−(R1)θ ⊆ b−(R2).
• A rule R is the least (general) generaliza1on (lg) of R1 and R2,
wri[en as R = lg(R1,R2), if R subsumes both R1 and R2 and issubsumed by any rule that subsumes both R1 and R2.
• The lg of two atoms p(s1,… , sn) and q(t1,… , tn) is undeﬁned if p
≠ q; and is p(lg(s1,t1), …, lg(sn,tn)) if p = q.
• The lg of two rules lg(R1,R2) is then wri[en as:lg(h(R1 ), h(R2 )) ←∧lg(L,K )L∈ b+ (R1 ), K∈ b+ (R2 )∧∧L∈ b− (R1 ), K∈ b− (R2 )¬lg(L,K ).

LF1T: Learning from 1-Step Transi2ons• Input: E ⊆ 2HB × 2HB: (posi2ve) examples/observa2ons,
P : an (ini2al) NLP;
• Output: NLP P s.t. J = TP(I) holds for any (I, J) ∈ E
BoVom-Up Algorithm (Inoue et al., 2012;2014)
1. If E = ∅ , then output P and stop;
2. Pick (I, J) ∈ E; put E := E \ {(I, J)};
3. For each A ∈ J, let

RIA := A ← ∧ B∈I B ∧ ∧ C∈HB\I￢C ;1. If RIA is not subsumed by any rule in P, then P := P ∪ {RIA} andsimplify P by generalizing some rules in P and removing all
clauses subsumed by them;
2. Return to 1.

Resolu2on as Generaliza2on• (naïve/ground resolu$on) Let R1 and R2 be two ground rules,
and l be a literal such that h(R1) = h(R2), l ∈ b(R1) and Ī ∈ b(R2).
If (b(R2) \ {Ī }) ⊆ (b(R1) \ {l}) then the ground resolu1on of R1 andR2 (upon l) is deﬁned as

res(R1,R2) := h(R1) ←∧K ∈ b(R )\{l} K
1

In par2cular, if (b(R2) \ {Ī }) = (b(R1) \ {l}) then the ground
resolu2on is called the naïve resolu1on of R1 and R2 (upon l).
• Example. R1 = (p ← q∧r), R2 = (p ← ￢q∧r), R3 = (p ←￢q):res(R1,R2) = res(R1,R3) = (p ← r).
• Proposi$on: The naïve resolu2on of R1 and R2 is the least
generaliza2on of them, e.g., lg(R1,R2) = res(R1,R2).

LF1T (naïve resolu2on) [R := A ← ∧IAB∈I B ∧∧ C∈HB\I￢C]

qr

pr

q

pqr

pq

Step

I→J

Opera$on

Rule

ID

P

Pold

1

qr→pr

Rqrp

p ← ￢p ∧ q ∧ r

1

1

{}

Rqrr

r ← ￢p ∧ q ∧ r

2

1,2
1,2,3

p

ε

r

2

pr→q

Rprq

q ← p ∧ ￢q ∧ r

3

3

q→pr

Rqp

p ← ￢p ∧ q ∧ ￢r4

res(4,1)p ← ￢p ∧ q

5Rqrr ← ￢p ∧ q ∧ ￢r

6

res(6,2)r ← ￢p ∧ q

7

Rpqrp

p ←p∧q∧r

8res(8,1)p ←q∧r9

Rpqrq

q ←p∧q∧r

10res(10,3)q ←p∧r114

pqr→pq

2,3,5

+1,4

3,5,7

+2,6

3,5,7,9+8

5,7,9,11+3,10

Cont. (naïve resolu2on) [R := A ← ∧
I
A

Step

I→J

Opera$on

Rule

ID

5

pq→p

Rpqp

p ← p ∧ q ∧ ￢r12

res(12,5)p ← q ∧ ￢rres(13,9)
6

p→ε

7

ε→r

8

r→r

B∈I B ∧∧ C∈HB\I￢C]

P

Pold

13

5,7,9,11,13

+12

p ←q

14

7,11,14+5,9,13Rεrr ← ￢p ∧ ￢q ∧ ￢r15

res(15,6)r ← ￢p ∧ ￢r

16

7,11,14,16

+15

Rrr

r ← ￢p ∧ ￢q ∧ r

17

res(17,15)r ← ￢p ∧ ￢q

18

7,11,14,16,18+17

res(18,7)r ← ￢p19

11,14,19+7,16,18

p ← q.
q ← p ∧ r.
r ← ￢p.
proposi2onal programp(t+1) ← q(t).
q(t+1) ← p(t) ∧ r(t).
r(t+1) ← ￢p(t).
ﬁrst-order program

LF1T (ground resolu2on) [R := A ← ∧
I
A

qr

pr

pqr

pq

B∈I B ∧∧ C∈HB\I￢C]

q
p

ε

r

Step

I→J

Opera$on

Rule

ID

P

1

qr→pr

Rqrp

p ← ￢p ∧ q ∧ r

1

1

Rqrr

r ← ￢p ∧ q ∧ r

2

1,2
1,2,3

2

pr→q

Rprq

q ← p ∧ ￢q ∧ r

3

3

q→pr

Rqp

p ← ￢p ∧ q ∧ ￢r4

res(4,1)p ← ￢p ∧ q

5Rqrr ← ￢p ∧ q ∧ ￢r

6

res(6,2)r ← ￢p ∧ q

7

Rpqrp

p ←p∧q∧r

8res(8,5)p ←q∧r9

Rpqrq

q ←p∧q∧r

10res(10,3)q ←p∧r114

pqr→pq

2,3,5
3,5,7
3,5,7,9
5,7,9,11

Cont. (ground resolu2on) [R := A ← ∧IAB∈I B ∧∧ C∈HB\I￢C]

Step

I→J

Opera$on

Rule

ID

5

pq→p

Rpqp

p ← p ∧ q ∧ ￢r12

res(12,5)p ← q ∧ ￢r

13

5,7,9,11,13

res(13,9)

p ←q

14

7,11,14Rεrr ← ￢p ∧ ￢q ∧ ￢r15

res(15,7)r ← ￢p ∧ ￢r

16

Rrr

r ← ￢p ∧ ￢q ∧ r

17

res(17,7)r ← ￢p ∧ ￢q

18

7,11,14,16,18

res(18,16)r ← ￢p19

11,14,19

6

p→ε

7

ε→r

8

r→r

p ← q.
q ← p ∧ r.
r ← ￢p.
proposi2onal program

P

7,11,14,16p(t+1) ← q(t).
q(t+1) ← p(t) ∧ r(t).
r(t+1) ← ￢p(t).
ﬁrst-order programWorst-Case Complexity• Theorem: Using naïve resolu2on, the memory use of the LF1T
algorithm is bounded by O(n・3n), and the 2me complexity oflearning is bounded by O(n2・9n), where n = |HB|. On the other
hand, with ground resolu2on, the memory use is bounded by
O(2n), which is the maximum size of P, and the 2me complexity
is bounded by O(4n).
• Corollary: Given the set E of complete state transi2ons, which
has the size O(2n), the complexity of LF1T(E,∅) with ground
resolu2on is bounded by O(|E|2). On the other hand, the worstcase complexity of learning with naïve resolu2on is O(n2・|E|4.5).

Learning Boolean Networks• Benchmarks of Boolean networks are taken from (Dubrova andTeslenko, 2011).
• All possible 1-step state transi2ons of N from all 2|HB| possible
ini2al states I0’s are computed from the benchmarks by ﬁrstly
compu2ng all stable models of τ(N) ∪ I0 using the answer-set
solver clasp, then by running LF1T with these state transi2ons.
• Environment: Intel Core I7 (3610QM, 2.3GHz). Time limit: 1 hour.
• Boos2ng is eﬀec2ve to reduce the size/number of rules.

Learning Robust Boolean Networks

LFIT

Li, F. et al.: The yeast cell-cycle network is
robustly designed, PNAS, 101(14), 2004.

• Most transi2ons from 212 states belong
to the same basin of aerac1on.
• From this state transi2on, LFIT learned
54 state transi2on rules in 0.8 sec.
• An improved learning algorithm using
BDD learned the same rules in 0.18 sec.

Ø Inoue, K., Ribeiro T., Sakama, C.: “Learning from Interpreta2on Transi2on”,
Machine Learning, 94(1):51-79, 2014.
Ø Ribeiro, T., Inoue, K., Sakama, C.: “A BDD-Based Algorithm for Learning fromInterpreta2on Transi2on”, Post-Proc. ILP 2013, LNAI, Vol.8812, pp.47-63, 2014.

Demonstra2on• Bo[om-Up Algorithm (Version 1; 2014.03)
E = {(pqr,pq),(pq,p),(p,_),(_,r),(r,r),(qr,pr),(pr,q),(q,pr)}p:- q.
q:- p, r.
r:- not p, q.
r:- not p, not r.
pqr

pq

p

ε

r
p

qr

pr

q
q

r

Cellular Automata (CA)• A CA consists of a regular grid of cells.
• A cell has a ﬁnite number of possible states.
• The state of each cell changes synchronously in discrete 2me steps
according to local and iden2cal transi2on rules.
• The state of a cell in the next 2me step is determined by its current
state and the states of its surrounding cells (neighborhood).
• 2-state CA is regarded as an instance of Boolean networks.
• CA is a model of emergence and self-organiza2on, which are two
important features of the nature/real-life as a complex system.
• 1-dimensional 2-state CA can simulate Turing Machine (Wolfram).
• Mul2-state CA: Disease Spreading Model—0 (healthy), 1 (infected),values in between (gradually more ill)

Wolfram’s Rule 110

•
•
•
•
•

current pa[ern111 110101 100 011

010

001

000

new state forcenter cell

0

1

1

1

0

1

0

1

c(x,t+1) ← c(x-1,t) ∧ c(x,t) ∧ ￢c(x+1,t). 0tc(x,t+1) ← c(x-1,t) ∧ ￢c(x,t) ∧ c(x+1,t). 1
2
c(x,t+1) ← ￢c(x-1,t) ∧ c(x,t) ∧ c(x+1,t). 3
4c(x,t+1) ← ￢c(x-1,t) ∧ c(x,t) ∧ ￢c(x+1,t). 5
6c(x,t+1) ← ￢c(x-1,t) ∧ ￢c(x,t) ∧ c(x+1,t). 78
9• Rule 110 is known to be Turing-complete.
• The logic program is acyclic (Apt & Bezem, 1990).

0

1

2

3

4

Incorpora2ng Background Theories• Torus world: length 4• c(0, t) ← c(4, t).
• c(5, t) ← c(1, t).

t

(4)

1

0

c(3)
→ c(2), c(3)→ c(1), c(2), c(3)→ c(1), c(3), c(4)a[ractor→ c(1), c(2), c(3) → …

1
2
3
4
5
6

learning rules:
0→1 (4), 1→2 (2), 2→3 (2).
learning posi2ve rules: (2),
(2),
(1).

2

3

4

(1)

Incorpora2ng Induc2ve Bias
• Bias I: The body of each rule exactly contains 3 neighbor literals.
• Bias II: The rules are universal for every 2me step and any posi2on.
• Biases I and II imply that an1-instan1a1on (AI) can be applied
immediately instead of least generaliza2on.
Step

I→J

Op.

Rule

ID

1

0010→0110

R32c(2) ← ￢c(1) ∧ ￢c(2) ∧ c(3)

1

AI(1)

c(x) ← ￢c(x-1) ∧ ￢c(x) ∧ c(x+1)2R33c(3) ← ￢c(2) ∧ c(3) ∧ ￢c(4)

3

AI(3)

c(x) ← ￢c(x-1) ∧ c(x) ∧ ￢c(x+1)4R21c(1) ← ￢c(0) ∧ ￢c(1) ∧ c(2)

5

R232

c(2) ← ￢c(1) ∧ c(2) ∧ c(3)

6

AI(6)

c(x) ← ￢c(x-1) ∧ c(x) ∧ c(x+1)

7

res(7,2)c(x) ← ￢c(x-1) ∧ c(x+1)

84,8res(7,4)c(x) ← ￢c(x-1) ∧ c(x)

9

8,9

2

0110→1110

P
2
2,4

Incorpora2ng Induc2ve Bias (Cont.)
Step

I→J

Op.

Rule

ID

2

0110→1110

R233

c(3) ← c(2) ∧ c(3) ∧ ￢c(4)10

AI(10)

c(x) ← c(x-1) ∧ c(x) ∧ ￢c(x+1)

11

res(11,9)c(x) ← c(x) ∧ ￢c(x+1)

12

R011

c(1) ← ￢c(0) ∧ c(1) ∧ c(2)

13

R344

c(4) ← c(3) ∧ ￢c(4) ∧ c(5)14

AI(14)

c(x) ← c(x-1) ∧ ￢c(x) ∧ c(x+1)

15

res(15,8)c(x) ← ￢c(x) ∧ c(x+1)

16

3

•
•
•
•

1110→1011

c(x,t+1) ← ￢c(x-1,t) ∧ c(x+1,t).
c(x,t+1) ← ￢c(x-1,t) ∧ c(x,t).
c(x,t+1) ← c(x,t) ∧ ￢c(x+1,t).
c(x,t+1) ← ￢c(x,t) ∧ c(x+1,t).

P

8,9,12

8,9,12,16

(8)
(9)
(12)
(16)

These are simpler than the original 5 rules, but s2ll have one redundant rule.

LF1T-BDD(Ribeiro, Inoue and Sakama, ILP 2013)
Idea: use BDD techniques to use less memory and learn faster.
Contribu$on: extend the scalability and the eﬃciency of LF1T.
••

Naïve resolution ≒ symmetric reduction.
New operation was devised for Ground resolution.

P'rules of pqp1

rules of q
p

1

1

NLP P
q

1

1

r

q

1

0

rules of r
1

0
r
1

1

p

q
0

1
r

r
1 0
1

p←q
p ← p∧rq ← p∧￢qq ← p∧rq ← ￢q∧rr ← p∧q∧r
r ← p∧￢q∧￢r

Top-Down LF1T

(Ribeiro and Inoue, ILP 2014)• Idea: Generate rules by specializa2on from the most generalones un2l no nega2ve example is covered.
• Merit: Learn all minimal (prime implicant) rules.
– Unique output, Eﬃcient on real networks• TD-LF1T starts with an ini2al program P0 = {a. | a ∈ HB}.
• For each transi2on (I, J) ∈ E, for each variable A that does notappear in J, A is associated with the set of its an1-support
ΚIA := I ∪ {￢B| B∈ HB \ I};• Each rule with head A is then specialized by the rules each ofwhich is formed by adding one literal from ΚIA to its body.
• Example: from the state transi2on (bc, ac), the rule b. is replacedby three rules: b ←a; b ←￢b; b ←￢c.

Running example

Comparison of 3 algorithms

Contents• Mo$va$on• Principles• Extensions:– LFkT (Learning Markov(k) Systems)– Mul2-Valued LFIT
– Asynchronous LFIT
– Probabilis2c LFIT• Applica$ons• Ongoing WorkWhat is the Nondeterminism? (A possible answer)
When diﬀerent transi1ons are possible, star1ng from asingle state, the pathway followed depends on the valuesof the corresponding transi1on delays.
(Thomas and D'Ari, 1990)
P

B
S

Q

A

R

C

t = -2t = -1

t=0

t=1

t=2

--

P

S

A

B

Q

R

S

A

C

Markov(k) System(Ribeiro, Magnin, Inoue and Sakama, FiBioE 2015)• Let HB be the Herbrand base of a program P and k a natural
number. The 1med Herbrand base HBk of P (with period k) is:k

HBk = ∪ {vt−i |v ∈ HB}
i=1

where t is a constant term (the current 2me step).
• A Markov(k) system S with respect to P is a logic programsa2sfying that, for any rule R ∈ S, h(R) ∈ HB and all atoms
appearing in b(R) belong to HBk.
• Example: S = { a ← bt ∧ bt-1; b ← at-2∧￢bt-2 }is a Markov(2) system.

Markov(2) system• S = {a ← bt ∧ bt-1; b ← at-2∧￢bt-2 }
a

b

b

b

ε

ε

ab

b

a

ab

ε

ε

b

b

a

a

ε

b

ε

b

ε

ε

ε

ε

a

b

ab

ε

(Top-down) LFkT
Input: A set of traces of execu2ons O of a Markov(k) system S. Notethat the op2mum delay is unknown at this point.
Step 1: Ini2alize a logic program P with the fact rules.
Step 2: Pick a trace T from O and update the delay k accordingly:
a. Ini2alize a program with the fact rules for each new delay k.
b. Revise these logic programs with all previous traces.
Step 3: Convert the trace into interpreta2on transi2ons andrevise the programs using least specializa2on.
Step 4: If there is a remaining trace in O, go back to step 2.
Step 5: Merge all logic programs into one by avoiding rule subsump2on.
Step 6: Remove all rules that are not necessary to explain O.
Output: A set of rules with the op2mum delay which realizes O.

Experiments of a Markov(5) system
A 2me-delayed gene regulatory networks of thehuman HeLa cell cycling (Li et al., 2006).

• LFkT input goes from 10 to 106 traces.

Mul2-Valued LFIT

(Ribeiro, Magnin, Inoue and Sakama, ICMLA 2015)• Atoms of a logic program to the form varval . We consider amul2-valued logic program as a set of rules of the form:

vval ← v1val1 ∧...∧ vnvaln(v=val ← v1=val1 ∧...∧ vn=valn)
where vval and vivali are atoms (n ≥ 0).
• Example: P = {a1 ← a0 ∧ b2 ; b1 ← a1∧b0 }.
• A mul1-valued interpreta1on I is a set of assignments such that
I contains one and only one ground atom vval for any v∈V.
• Note: no nega$on: deﬁnite programs (or equa2onal theory)• Generaliza2on and specializa2on can be rediﬁned accordingly.

Other extensions• From synchronous to asynchronous updates• From determinis2c to probabilis2c and nondeterminis2ctransi2ons (MarSnez et al., ICLP 2015; ICAPS 2016)• And their delayed and/or mul2-valued versions• Open Ques2on: When there are incompa1ble transi1ons,
which models should be selected?
– delay, synchronicity, noise, nondeterminism, uncertainty, etc.

Contents• Mo$va$on• Principles• Extensions• Applica$ons:– Biology– Cellular Automata– Robo2cs (learning ac2on rules)– AGI (learning agents’ logics)• Ongoing WorkTwo types of changes• Endogenous change:– natural growth– physical dynamics– biological development– internal change in the closed system• Exogenous change:– ac2on– external event– enzyma2c reac2on– decision/choice with free will

Revising Plans in Adap2ve Systems
3
pickup0.9

Domainmodel

move(4)

0.1

5

5a

5b

0.7

4

model revisionactionEnvironment

Systemreaction

Behavioural model revision through probabilis$c rule learning– ac2on rules are learned from logs of trails using ASP
Ø Sykes, D., Corapi, D., Magee, J., Kramer, J., Russo, A., Inoue, K.: “Learning
revised models for planning in adap2ve systems”, ICSE 2013: 63-71.

Learning Uncertain Ac$ons in Stochas$c
Domains for Robot Planning(joint work with David MarSnez and his colleagues in CSIC-UPC)

LearnerModel

Planner
Experiences

Perception
Robot

ActionLearning Uncertain Ac2ons through LFIT
(MarSnez et al., ICLP 2015; ICAPS 2016)
Groundedtransitions

Symbolictransitions

Interpretationtransitions

Input observations

Symbolicinterpretation

Interpretationtransitions
LFITBest RDDL operators

Symbolic planning
operators

Operator
optimization

Probabilistic
propositional rules

Probabilistic
propositional rules

Ac2on Learning with LFIT
Learn from transi2ons (statet, ac2ont, statet+1)
Learned rule:p= 0.3 : robot-at(X,Z) ← robot-at(X,Y) ∧￢obstacle-at(X,Z) ∧ move-north

Probability Head = Eﬀect

x1,y1

Body = Precondi2ons

x1,y1

+

Ac2on

IPPC 2014 Domains (MarSnez et al., ICAPS 2016)•••

Triangle Tireworld. (Easiest) Uncertain effects, no exogenous effects,
5 predicates, 3 actions, 7 operators with max 2 terms.
Crossing Traffic. (Intermediate) Uncertain effects, exogenous effects,
8 predicates, 4 actions, 6 operators with max 3 terms.
Elevators. (Hard) Uncertain effects, exogenous effects, 10 predicates,
4 actions, 17 operators with max 3 terms.

“Can Machines Learn Logics?”
Input

Agent A (human/computer)

Output

S: formulas

Logical System L

T (⊆Th(S ))Machine M(S , T)•••

Learning System C

KGiven input (S, T), a machine M produces an axioma2c system K.
It is possible to learn meta-level one-step deduc2on rules, e.g., MP.
Would be applied to learning abduc2on and other non-standard logics.

Ø Sakama, C., Inoue, K.: “Can Machines Learn Logics?”, 8th Int’l Conf.
Ar1ﬁcial General Intelligence (AGI 2015).

Learning Deduc$on Rules by LF1T
(Sakama, Ribeiro and Inoue, ILP 2015)• We assume a deduc2on system L represented by ametalogic program P that provides transi2ons (I, J)
sa2sfying J = TP(I).
• Given (I, J) as an input, our goal is to examine
whether LF1T can reproduce correct inference rulesof L represented by meta-rules in P.
IP(I , J)

LF1T

J

L

Example• Given the Herbrand base:
B={ hold(p), hold(q), hold(r), hold(p→r) },a rule with hold(r) in the head is constructed as follows.
• Step 0: LF1T starts with the most general rule:hold(r)←(1)• Step 1: The transi2on ({},{}) is given. (1) is inconsistent
with this (namely, {} should produce {hold(r)} under (1)),
so (1) is minimally specialized by introducing an atomfrom B:hold(r)←hold(p)(2)
hold(r)←hold(q)(3)
hold(r)←hold(r)(4)
hold(r)←hold(p→r)(5)

Example• Step 2: The transi2on ({hold(p)},{hold(p)}) is given.
hold(r)←hold(p)(2)
is inconsistent with this, so (2) is specialized intohold(r)←hold(p), hold(q)hold(r)←hold(p), hold(r)hold(r)←hold(p), hold(p→r)
These rules are respec2vely subsumed byhold(r)←hold(q)(3)
hold(r)←hold(r)(4)
hold(r)←hold(p→r)(5)
hence removed. As a result, (3),(4) and (5) remain.

Example• Step 3: The transi2on ({hold(q)},{hold(q)}) is given.
hold(r)←hold(q)(3)
is inconsistent with this, so (3) is specialized intohold(r)←hold(q), hold(p) (6)hold(r)←hold(q), hold(r)hold(r)←hold(q), hold(p→r)
The last two rules are respec2vely subsumed byhold(r)←hold(r)(4)
hold(r)←hold(p→r)(5)
and removed. As a result, (4), (5) and (6) remain.

inputoutput({}, {})

hold(r)←hold(p)hold(r)←hold(r)hold(r)←hold(q)hold(r)←hold(p→r)({hold(p)},{hold(p)})

hold(r)←hold(p)hold(r)←hold(r)hold(r)←hold(q)hold(r)←hold(p→r)({hold(q)},{hold(q)})

hold(r)←hold(q)hold(r)←hold(r)hold(r)←hold(p→r) hold(r) ←hold(p),hold(q)({hold(p→r)},{hold(p→r)})hold(r)←hold(r)hold(r)←hold(p→r)
hold(r) ←hold(p),hold(q)hold(r)←hold(p→r),hold(p)hold(r)←hold(p→r),hold(q)({hold(p),hold(q)},{hold(p),hold(q)})

hold(r)←hold(r)hold(r) ←hold(p),hold(q)hold(r)←hold(p→r),hold(p)hold(r)←hold(p→r),hold(q)({hold(p→r),hold(q)},{hold(p→r),hold(q)})

hold(r)←hold(r)hold(r)←hold(p→r),hold(p)hold(r)←hold(p→r),hold(q)({hold(p→r),hold(p)}, {hold(p),hold(r)})

hold(r)←hold(r) :Repe$$on
hold(r)←hold(p→r),hold(p) :Modus Ponens

Experimental Results
Given B={ hold(p), hold(￢p), hold(q), hold(￢q), hold(p→q), hold(q→r),hold(p→r) }, LF1T produces:– hold(￢p) ← hold(￢q) ∧ hold(p→q) : Modus Tollens– hold(p→r) ← hold(p→q) ∧ hold(q→r) : Hypothe$cal Syllogism• Given B={ hold(p), hold(￢p), hold(q), hold(￢q), hold(p∨q),hold(￢p∨￢q), hold(r∨s), hold(￢r∨￢s), hold(p→r), hold(q→s) },LF1T produces:– hold(p) ← hold(p∨q) ∧ hold(￢q) : Disjunc$ve Syllogism– hold(r∨s) ← hold(p∨q) ∧ hold(p→r) ∧ hold(q→s): Construc$ve Dilemma– hold(￢p∨￢q) ← hold(￢r∨￢s) ∧ hold(p→r) ∧ hold(q→s): Destruc$ve Dilemma• Given a transi$on (I,J)=({hold(p→q), hold(q)}, {hold(p)}), LF1T produces– hold(p) ← hold(q)∧hold(p→q): Fallacy of Aﬃrming the Consequence (a rule for Abduc$on)•

Contents• Mo$va$on• Principles• Extensions• Applica$ons• Ongoing Work:– DREAM Challenges– NN-LFITScien$ﬁc Challenge(Ongoing work with Morgan Magnin, Tony Ribeiro, Olivier Roux)

Goals:•Build predic$ve dynamic models from $me series data
•Assess the eﬃciency of the approach by taking part to an open
Machine Learning challenge.
•Mo[o: Logical modeling has its own merits compared with
con2nuous approaches (e.g., ODE)

Underlying ques$ons:•What would be eﬃcient algorithms for discre$za$on and learning?
•What is a good predic2ve model?
•How to validate the beneﬁts of the algorithms on "real-life" data?

Abstrac2on of systems to build qualita2ve dynamic models

Discre2za2on of
the expression

LFIT

Time series data
Regulatory networks: up to
45.000 genes over 48 2mepoints for every gene
Logic programA wide range of possible models andinference algorithms• Expression discre$za$on- Boolean- Mul2-valued• Time discre$za$on- Event-driven model- Discrete-2me model- Dense-2me model• Seman$cs of discrete transi$ons- Synchronous- Par2ally synchronous (a set of transi2ons can be ﬁred
altogether)- Asynchronous (one at a 2me)
• Determinism of discrete transi$ons : yes or no• Markov property: yes or no

Two main targets
DREAM Challenges data:•Predict steady states and associated model (without signs):• DREAM4 (2009): 100 genes over 21 2me points [synthe1c data]• DREAM5 (2010): 1000 genes over 17 2me points [real data]•Predict trajectories and associated model:
DREAM8 (2013): 40 genes over 8 2mes points [real data]
Circadian rhythm (French ANR-funded project): predict trajectories andassociated model (with nature of interac2ons)
Input: expression data (Delaunay et al.) [real data]• 45.000 genes• 4 datasets (1 normal + 3 perturba2ons)• 48 2me points for every gene• Start: 2006

• Periodicity: Annual• DREAM = "Dialogue for Reverse Engineering Assessments andMethods”: Reverse engineering for regulatory, signaling, andmetabolic networks• Aim: encourage the design of new eﬃcient computa2onal
models and methods to analyze systems from biology• URL: h[p://dreamchallenges.org• A wide range of partners (IBM Research, Sage Bionetworks, …)• Main compe2tor: kaggle• Reward: no ﬁnancial prize, but publica2ons in journals• Main issue: how to rank methods?
• Scoring commiVee for each challenge• Evalua$on criteria: Predic2ve power with speciﬁc metrics:
AUPvR, AUROC

Predic2on problems issued in DREAM••

Structure of the network
Behavioral predic$on with regard to speciﬁc condi2ons (e.g.,knockouts) or ini2al states• Steady states• Trajectories• Judges are blind to the approach that is used, i.e., only thepredic2on results counts… (at least at short-term perspec2ve)• Computa$onal $me is not a criterion that is assessed in this kindof challenge.
• Most methods tend to lie in the range of minutes to hours.
• But some others could take up to 48h per gene.

About DREAM4 data
• Targeted systems (adapted from E. coli and yeast network):• 5 diﬀerent systems each composed of 10 genes• 5 diﬀerent systems composed of 100 genes• Datasets available for each system of 10 genes (resp. 100):• 5 (resp. 10) $me series data with 21 $me points corresponding

to diﬀerent perturba$ons• Steady state at wild type, i.e. 1 steady state• Steady state aŠer knocking out each gene, i.e. 10 steady states(resp. 100)

• Steady state aŠer knocking down each gene (transcrip2on rate at50%), i.e. 10 steady states (resp. 100)

• Steady states aŠer some random mul2factorial perturba2ons,

i.e. 10 steady states

Learning experiments with LFkT
• Learn independently each series with LFkT
• Evaluate rules on all series (full cross-valida2on)

Evalua2on on DREAM4 data
• Goal: Given an ini$al state and {5 for networks of 10 genes; 20 for
networks with 100 genes} diﬀerent condi$ons of dual genes to be
knockout simultaneously, predict point aVractors• Evalua$on of precision: mean square error of the diﬀerence
between predicted/expected values

Experiments run on a processor Intel Xeon (X5650, 2.67GHz) with 12GB of RAM

Comparison with other methods

Ar2ﬁcial Neural Networks: learning transi2on(Ongoing work with Enguerrand Gentet )• Advantages:-

Con2nuous variables
Good generaliza2onInter-variables learning
Manage delays eﬃciently (RNN)• Challenges:- Architecture choice- Rule extrac$on

Rules?

x1(t)x1(t+1)x2(t)x2(t+1)x3(t)x3(t+1)x4(t)x4(t+1)xn(t)xn(t+1)transi2on

Ar2ﬁcial Neural Networks: ongoing work
Ongoing: NN-LFIT- Learning Boolean networks- 4-layer NN (2 hidden layers)- No delays

Results:- Successful learning- Good generaliza2on

Training on the whole set of transi2on:
all the transi2ons are successfully learned

Plans:- con2nuous values- rule extrac2on- delays
Training on 60% of transi2ons:
0% error on the remaining 40%

Training on 30% of transi2ons:
0.5% error on the remaining 70%

LFIT: Summary• Mo$va$on: Modeling in Dynamic Environments• Principles: LF1T (Learning from 1-Step Transi2ons)– Bo[om-Up Algorithm (generaliza2on)– BDD Op2miza2on– Top-Down Algorithm (specializa2on)• Extensions: LFkT (Learning Markov(k) Systems),
Mul2-Valued/Asynchronous/Probabilis2c Extensions• Applica$ons: Biology, Robo2cs, AGI, etc.
• Ongoing Work: DREAM Challenges, NN-LFIT

Publica2on (1/2)
•
•

•

•
•
•

•

•

Katsumi Inoue: Logic Programming for Boolean Networks, in: Proceedings of the 22ndInterna1onal Joint Conference on Ar1ﬁcial Intelligence (IJCAI-11), pp.924-930, AAAI (2011)
Katsumi Inoue, Chiaki Sakama: Oscilla2ng Behavior of Logic Programs, in: Correct
Reasoning—Essays on Logic-Based AI in Honour of Vladimir Lifschitz, LNAI, Vol.7625, pp.
345-362, Springer (2012)
Daniel Sykes, Domenico Corapi, Jeﬀ Magee, Jeﬀ Kramer, Alessandra Russo, Katsumi Inoue:
Learning Revised Models for Planning in Adap2ve Systems, in: Proceedings of the 35th
Interna1onal Conference on Sorware Engineering (ICSE ’13), pp.63-71, IEEE/ACM (2013)
Chiaki Sakama, Katsumi Inoue: Abduc2on, Unpredictability and Garden of Eden, Logic
Journal of the IGPL, 21(6):980-998 (2013)
Katsumi Inoue, Tony Ribeiro, Chiaki Sakama: Learning from Interpreta2on Transi2on,
Machine Learning, 94(1):51-79 (2014)
Tony Ribeiro, Katsumi Inoue, Chiaki Sakama:
A BDD-Based Algorithm for Learning from Interpreta2on Transi2on, in: Post-Proceedingsof ILP 2013, LNAI, Vol.8812, pp.47-63, Springer (2014)
Tony Ribeiro, Katsumi Inoue:
Learning Prime Implicant Condi2ons from Interpreta2on Transi2on, in Post-Proceedings of
ILP 2014, LNAI, Vol.9046, pp.108-125, Springer (2015)
Tony Ribeiro, Morgan Magnin, Katsumi Inoue, Chiaki Sakama:
Learning Delayed Inﬂuences of Biological Systems, Fron1ers in Bioengineering andBiotechnology, 2:81 (2015)

Publica2on (2/2)
•

•

•

•

•

•

Tony Ribeiro, Morgan Magnin, Katsumi Inoue, Chiaki Sakama:
Learning Mul2-Valued Biological Models with Delayed Inﬂuence from Time-Series
Observa2ons, in: Proceedings of the IEEE 14th Interna1onal Conference on Machine
Learning and Applica1ons (ICMLA 2015), pp.25-31, IEEE (2015)
Marcus Völker, Katsumi Inoue: Logic Programming for Cellular Automata, in: TechnicalCommunica1ons of the 31st Interna1onal Conference on Logic Programming (ICLP 2015),
CEUR Workshop Proceedings, Vol.1433 (2015)
David MarSnez, Tony Ribeiro, Katsumi Inoue, Guillem Alenyà, Carme Torras:
Learning Probabilis2c Ac2on Models from Interpreta2on Transi2ons, in: TechnicalCommunica1ons of the 31st Interna1onal Conference on Logic Programming (ICLP 2015),
CEUR Workshop Proceedings, Vol.1433 (2015)
David MarSnez, Tony Ribeiro, Katsumi Inoue, Guillem Alenyà, Carme Torras: Learning
Rela2onal Dynamics of Stochas2c Domains for Planning, in: Proceedings of the 26th
Interna1onal Conference on Automated Planning and Scheduling (ICAPS ’16), to appear,
AAAI (2016)
Chiaki Sakama, Katsumi Inoue: Can Machines Learn Logics? in: Proceedings of the 8thInterna1onal Conference on Ar1ﬁicial General Intelligence (AGI 2015), LNAI, Vol.9205, pp.
341-351, Springer (2015)
Chiaki Sakama, Tony Ribeiro, Katsumi Inoue: Learning Inference by Induc2on, in: PostProceedings of ILP 2015, LNAI, Vol.9575, to appear, Springer (2016)