Soutenance Thèse Philippe Lemoisson - LIRMM – 15.12.2006 1 construction collaborative de théorie … vers une machine abstraite conversationnelle Philippe

Soutenance Thèse Philippe Lemoisson - LIRMM – 15.12.2006 1

constructioncollaborativede théorie… vers une machine abstraite conversationnelle

Philippe

LEMOISSON

LIRMM -

15.12.2006


1. Formulation du problème abordé dans la thèse

2. Proposition : la machine abstraite AUSTiN

3. Mise en perspective de la proposition

Construction collaborative de théorie: vers une machine abstraite conversationnelle

1.1. un cadre pour la construction collaborative de

théorie

1.2. assister la composition automatique des

raisonnements ?







théorie


raisonnements ?


Climat : flux et stocks de CARBONEunités : GigaTonne (GT); GT/ansource : IPPC 1995extrait de : “L’avenir climatique” Jean-Marc Jancovici


Biomassemarine

IndustrieSols +

Végétaux

Océanprofond

Océansurface

stocks carbone (océan surface) = 1020 GT

stocks carbone (sols + végétaux) = 2190 GT

stocks carbone (océan profond) = 30800 GT

stocks carbone (atmosphère) = 750 GT

Données

Calculs

Climat : flux et stocks de CARBONE

‘n’ fragments1 théorie ?

Atmosphère

(|)

(|)

(|)

(|)

(|) Raisonnements

Connaissances


processus …à plusieurs

(|)

(|)

(|)

(|)

(|)


3 mondes

c h a n g e m e n t s d’ é t a t

• événements avant leur description(Science Physique = premier niveau de description )

e x p r e s s i o n s

• schémas stables et partagés

c o m m u n i c a t i o n

• alphabets & jeux de règles finis langages formels

d é d u c t i o n

a s s o c i a t i o n si n t i m e s

• graphe connexe de neurones & synapses• individuel, changeant• re-entrée entre « structures » associativité• forte redondance adaptabilité• pas accessible de l’extérieur aucun codage

p e n s é e s é l e c t i o n n i s t e

cerveau: 10 11 neuronescortex: 3*1010 neurones; 10 15 synapses

Le « monde physique »des objets et

des instruments

Le « monde intérieur »

Le « monde du langage »

un fait

(|)

une théorie

concentrationen carbone dans

l’océan de surface ?

stocks carbone (océan surface) = 1020 GT

Atmosphère

Océanprofond

Biomassemarine

Océansurface

stocks carbone (atmosphère) = 750 GT


(|)(|)

(|)

(|)

(|)

s o u r c e s …

() ()()

()

Gerald M. Edelman (1929 )

Charles Sanders Peirce

(1839 – 1914)

Karl Raimund Popper

(1902 – 1994)


m o n d ei n t é r i e u r

m o n d ed u l a n g a g

e

m o n d ep h y s i q u e

existencevalidité syntaxique

fragment de théorie

événements

causalitédéduction

prédictions

(|)

jugement

dans les traces de Peirce, Edelman …

observations

penséesélectionniste


fragments de théorie

dans les traces de Peirce, Edelman … et Popper

m o n d ed u l a n g a g

e


événements

causalité

observations

déduction

prédictions

(|)

(|)

fragments de théorie

penséesélectioniste


T h é o r i e : définition semi-formelle …

1. un jeu d’expressions décrivant des observations et des prédictions, basé sur un alphabet initial fini et un ensemble fini de règles d’assemblage statique;

2. un jeu d’expressions permettant de raisonner logiquement à partir des faits, basé sur un ensemble fini de règles d’assemblage dynamique;

3. un ensemble fini de règles de composition des raisonnements.

Supposons un langage formel consistant en :

Supposons un groupe de personnes chacune dotée de son propre jugement en accord sur le langage formel constituant collectivement un ‘oracle’ capable d’arbitrer

sur la véracité ou la fausseté des expressions. (|)(|)

(|)


…T h é o r i e : définition semi-formelle

Une théorie est un ensemble d’expressions vraies du langage formel tel que l’application composée des raisonnements aux faits produise des expressions vraies.

*1 , *2(|)

(|)

(|)

*1 les « fragments de théorie » sont des théories

*2 définition inspirée de [Shapiro, 1991] E. Shapiro, “Inductive inference of theories from facts/ Computational logic (essays in honour of Alan Robinson)”, Chap7, edited by Jean-Louis Lassez and Gordon Plotkin, The MIT Press, 1991.


machine abstraite : intelligibilité / codification ?

théorie

prédictions

m a c h i n ea b s t r a i t e

m o n d ei n t é r i e u r

(|)

m a c h i n ep h y s i q u e

événements

causalitéobservations

déduction



{prédictions} 1

{prédictions} 5

{prédictions} 4

{prédictions} 3

{prédictions} 2 (|)

(|)

(|)

(|) (|)

{observations}

1

1 5

4

32

22

compositionalité ?


(|)

(|)

(|)

(|) (|)

{prédictions}

{observations}

1

1 5

4

32

22

compositionalité ?







théorie


raisonnements ?


Acceptation d’un langage conceptuel pour les observations et prédictions

Acceptation d’algorithmes à étapes pour les raisonnements

Composition globalement déterministe des raisonnements

Chaque calcul doit être une déduction formelle

Si échec à l’articulation des raisonnements, aide au diagnostic


Cahier des charges pour une machine abstraitequi compose automatiquement les raisonnements







théorie


raisonnements ?


(|)(|)

(|)

(|)

(|)

s o u r c e s …

() ()()

()

John McCarthy (1927 )

John Langshaw Austin

(1911 –1960)


Composition de fragments de théorie …

rouge triangletriangle petit

rouge petit


… à travers une conversation

objets rouges ?objets verts ?objets bleus ?

objets petits ?objets grands ?

forme taille

couleur forme

* *1 2

promessequestion

propriété ‘x’ ?

propriété ‘y’

rouge

petit

rouge triangle

assertion

triangle petit

t=1 t=2 t=3

0 0

0

0 1

1 1

0 1

1 0

t=0

0

0 1

1 1

t=2

rejected (1,1,1,2)

accepted (0,1,1,2)

(1,0)

(0,0)

(1,1)

(0,1)

accepted (1,0,1,2)

1-Sudoku: un langage simple S0

22

Sudoku

[row : CO-ORDINATE : 0 ][column : CO-ORDINATE : 1 ][accepted : VALUE : ? ][when : STATE : ? ]

question( )

[row : CO-ORDINATE : 0 ][column : CO-ORDINATE : 1 ][accepted : VALUE : 1 ] [when : STATE : 2 ]

( )assertion

[row : CO-ORDINATE : * ][column : CO-ORDINATE : * ][accepted : VALUE : * ][when : STATE : * ]

( )promesse

accepted (0,1,?,?)

t=2

0 1

1 1

intelligibilité / codification ?

23

accepted (0,1,1,2)

accepted (*,*,*,*)

AUSTiN

accepted (x,y,z,t) answerFor accepted (x,y,?,t)

rejected (0,1,0,t) answerFor rejected (?,?,?,?)

accepted (x,y,*,*) reductionOf accepted (*,*,*,*)

accepted (x,y,*,t) reductionOf accepted (x,y,*,*)

accepted (x,y,z,t) reductionOf accepted (x,y,*,*)

rejected (0,1,?,t) reductionOf rejected (*,*,?,*)

accepted (x,y,z,t) triggerFor accepted (*,*,*,*)

rejected (x,y,?,t) triggerFor rejected (*,*,?,*)

3 “actes de langage” … + 3 relations …

0 1

1 1

rejected (1,1,1,t)

accepted (0,1,1,t)

accepted (1,0,1,t)

pré-conditions de patterns

assertionquestionpromesse

24

(i): accepted (x,y,z,t) answerFor accepted (x,y,?,t)

… + déduction interne à

AUSTiN !

(ii): accepted (x,y,z,t) reductionOf accepted (x,y,*,*)

(i) (ii): accepted (x,y,*,*) potentialAnswerFor accepted (x,y,?,t)

(iii): accepted (x,y,z,t) triggerFor accepted (*,*,*,*)

(ii) (iii): accepted (x,y,*,*) potentialTriggerFor accepted (*,*,*,*)

assertionquestionpromessestarter

25

accepted (*,*,?,*)rejected (*,*,?,*)accepted (*,*,*,*)rejected (*,*,*,*)

réécritures (réductions) successives chez CELL

0


26

context (x,y,t)

accepted (x,y,?,t)rejected (x,y,?,t)accepted (x,y,*,t+1)rejected (x,1-y,*,t+1)rejected (1-x,y,*,t+1)

1

(x,y)

(1-x,y)

(x,1-y)

accepted (x,y,*,t)rejected (x,y,*,t)

A={accepted(x,y,zi,t)}R={rejected(x,y,zk,t)}

si A=R=, alors: sinon: accepted (x,y,z0,t+1) rejected (x,1-y,z0,t+1) rejected (1-x,y,z0,t+1)

2

z0

Z0

Z0

2

1

context(*,*,*)

les patterns conversationnels

Q1: accepted (*,*,?,*)Q2: rejected (*,*,?,*)

accepted (*,*,*,*)rejected (*,*,*,*)

accepted (x,y,*,t+1)rejected (x,1-y,*,t+1)rejected (1-x,y,*,t+1)

27

{answers to Q1,Q2}accepted (x,y,z,t+1)rejected (1-x,y,z, t+1)rejected (x, 1-y,z, t+1)

2

Q1: accepted (x,y,?,t)Q2: rejected (x,y,?,t)

context(x,y,t)

1


résolution du 1-Sudoku

cont (0,0,0) cont (0,0,1) cont (0,0,2) cont (0,1,0) cont (0,1,1) cont (0,1,2) cont (1,0,0) cont (1,0,1) cont (1,0,2) cont (1,1,0) cont (1,1,1) cont (1,1,2)

acceptd(0,0,?,0) rejected(0,0,?,0)












accepted(0,0,*,1) rejected(0,1,*,1) rejected(1,0,*,1)












acceptd(0,0,0,1) rejected(0,1,0,1) rejected(1,0,0,1)

WAIT WAIT WAIT WAIT WAIT WAIT WAIT WAIT

ENDaccepted(0,0,*,2) rejected(0,1,*,2) rejected(1,0,*,2)









WAITacceptd(0,1,1,2) rejected(0,0,1,2) rejected(1,1,1,2)

WAITacceptd(1,0,1,2) rejected(0,0,1,2) rejected(1,1,1,2)

WAIT WAIT









END END END END

accepted (0,0,0,0)

accepted (*,*,?,*) rejected (*,*,?,*) accepted (*,*,*,*) rejected (*,*,*,*)

END

END END END

0

0 0

0

1 1

1 1

1 11

1 1

0 0

0

0 0

0 0

1 1

1 1

1 11

1 1

0 0

0

61 2 345 6

P R O G R A M M E 1 + P R O G R A M M E 2

PROGRAMME 2

3-Sudoku / AUSTiN-Java

Sudoku « Le Monde » n° 53

PROGRAMME 1

CELL

3 81invocations

SET

3 x 27invocations

8 1 94 3

9 2 66

2 72 8 6 94 7 2

5 33 6 2 4

8 1 94 3

9 2 66

2 72 8 6 94 7 2

5 33 6 2 4

8 1 94 3 7

9 2 66

2 72 8 6 94 7 2

5 33 6 2 4

8 1 99 4 3 7 2

9 2 66

2 72 8 6 94 7 2 9

5 33 5 6 2 4

8 14 3 7 2

9 5

30

AUSTiN : 3 transitions assertionquestionpromesse

starter

triggerForanswerForreductionOf

revoke ( )

activate ( )

invoke ( or )

+ 3 tests

31

AUSTiN : concurrence des tests & transitions

inv.

act.

rev.act.

rev.

rev.

rev.

act.inv.

transition pipe

test-I

test-A

test-A

test-I

test-R

test pipe

transition

testInvoke

testActivate

testRevoke

test-A

test-R

test-I

test-Itest-I

32

propriétés formelles d’AUSTiN / 1

Théorème 1:

Soit un ensemble de patterns tel que le graphe de la

relation « potentialTriggerFor » soit sans cycles,

Alors le calcul s’achève en un nombre fini de

transitions.

33


a

b

d

cThéorème 2:

Le calcul est confluent.

34

promessestarter

questionassertion


composition automatique des groupes de patterns

35


A U S T i N

inputoutput

déduction

Construction collaborative d’une théorie



DEADLOCK DEADLOCK







théorie


raisonnements ?


Un langage conceptuel Représentation des connaissances

?

triggerFor{ }

answerFor{ }

triggerFor{ }

{ }{ }{ }


des graphes conceptuels …

( )f

cd

e

b

a

assertion

( )?

c?

?

?

a

question

( )*

c*

*

b

*

promesse

answerFor

reductionOf

… encapsulés dans des actes de langage


Raisonnements à étapes

AUSTiN est un « blackboard » dont le contrôle est basé sur des actes de langage

triggerFor{ }

potentialAnswersFor{ }=

answerFor{ }

potentialTriggersFor{ }=

triggerFor{ }


Composition … Déduction

Composition automatique de fragments de théories … le point de départ est un langage partagé! articulation d’un nombre fini de raisonnements à nombre fini d’étapes où chaque étape est un « réducteur » contrôle confluent sur une conversation qui se propage en avant

Aspects logiques du déroulement du calcul: « décroissance » garantie par « reductionOf » transitions pilotées par événements (triggerFor ; answerFor) second ordre (les réducteurs sont eux-mêmes réduits)

Autres principes structurants « triggerFor » : traitement CONCURRENT de tous les contextes de raisonnements « answerFor » : attente de la TOTALITE des réponses potentielles avant le passage à l’étape suivante

La trace de la conversation est un chemin logique entre le contexte initial et les nouveaux énoncés, qui articule les

raisonnements posés au début.


AUSTiN : expérimentations potentielles

Modèles au carrefour de plusieurs expertises

Progiciels organisés en “services” autonomes

Code distribué parallélisable

inv.

act.rev.act.

rev.

rev.

rev.

act.inv.

test-I

test-Atest-A test-I

test-Rtest-A

test-I

transition test

(|)Océan

Atmosphère

(|)(|)


Perspectives

Publier [Lemoisson, Cerri, Sallantin, 2005] P. Lemoisson, S.A. Cerri and J. Sallantin , “Conversational Interactions

Among Rational Agents”, in Towards the Learning GRID: Advances in Human Learning Services , IOS Press

2005.

[Lemoisson and Cerri, 2005] P. Lemoisson, and S.A Cerri, “Interactive Knowledge Construction in the

Collaborative Building of an Encyclopedia”, in Applied Artificial Intelligence Journal, Vol. 19, n.9-10, pp.

933-966, 2005.

Approfondir les aspects liés à la concurrence au sein du calcul

Approfondir l’examen d’AUSTiN à travers un ou des

formalisme(s) classique(s)… Pb: « assertions », « questions », « promesses », « answerFor », « triggerFor » sont

omniprésents dans le contrôle du calcul

Replacer la conversation dans un cadre plus large, moins contraignant … non-

confluent?... non monotone?


merci

Ph

oto

gra

ph

ie :

I-F

an

g L

in

Lem

ois

son


Documents

Soutenance Thèse Philippe Lemoisson - LIRMM – 15.12.2006 1 construction collaborative de théorie … vers une machine abstraite conversationnelle Philippe