Intel·ligència Artificial. Programació

TREBALL DE RECERCA

JOSEP CARNER MARSAL

ESCOLA PIA, BATXILLERAT TECNOLÒGIC

TUTOR: SANTIAGO MALINOWSKI

Gràcies, en primer lloc, al Santi Malinowski i a l’Anna Brescó, pel seguiment del treball. A Pedro Meseguer i Miquel Sánchez per les

entrevistes. Als meus pares pel suport moral en els moments més crítics. A en Carles

Marmelada, Ignasi Sos, Joan Enric Taló i Anna Fernández per revisions i opinions puntuals.

IA: Intel∙ligència Artificial ÍNDEX

BLOC I: INTRODUCCIÓ [p.001]

BLOC II: RECURSOS DE PROGRAMACIÓ UTILITZATS EN LA IN-TEL·LIGÈNCIA ARTIFICIAL [p.004] I. CONCEPTES BÀSICS.......................................................................................................p.001

1. Què és la IA?..............................................................................................................p.001 2. Història i desenvolupament........................................................................................p.001

2.1. El terme IA..........................................................................................................p.001 2.2. Història...............................................................................................................p.001

2.2.1. Període clàssic o inicis..............................................................................p.001 2.2.2. Període “romàntic”.....................................................................................p.001 2.2.3. Període modern (1975-actualitat)..............................................................p.001

2.3. Actualitat i futur...................................................................................................p.001 3. Aplicacions.................................................................................................................p.001 4. La ment humana........................................................................................................p.001

4.1. El coneixement i la intel·ligència. Fonament psicològic.....................................p.001 4.2. La transmissió d’informació. Fonament biològic.................................................p.001

4.2.1. El sistema nerv iós.....................................................................................p.001 4.2.2. La neurona i la sinapsis.............................................................................p.001

5. Diferències entre la intel·ligència natural i arti ficial....................................................p.001 6. Avaluació d’un sis tema intel·ligent.............................................................................p.001

6.1. El test de Turing.................................................................................................p.001 II. PROGRAMACIÓ DE LA INTEL·LIGÈNCIA: CRITERIS GENERALS...............................p.001

1. Objectiu: Què?...........................................................................................................p.001 2. Metodologia: Com?....................................................................................................p.001

III. RECERCA SENSE INFORMACIÓ DEL DOMINI..............................................................p.001 1. Caracterís tiques.........................................................................................................p.001 2. Elements....................................................................................................................p.001 3. Requisits.....................................................................................................................p.001 4. Cerca en amplitud......................................................................................................p.001

4.1. Caracterís tiques.................................................................................................p.001 4.2. Procediment.......................................................................................................p.001 4.3. Complex itat.........................................................................................................p.001 4.4. Avantatges i inconvenients.................................................................................p.001

5. Cerca en profunditat...................................................................................................p.001 5.1. Caracterís tiques.................................................................................................p.001 5.2. Procediment.......................................................................................................p.001 5.3. Complex itat........................................................................................................p.001

p.005 p.005 p.006 p.006 p.007 p.008 p.008 p.008 p.009 p.011 p.011 p.012 p.014 p.014 p.015 p.016 p.017 p.018 p.019 p.019 p.020 p.022 p.022 p.023 p.024 p.025 p.025 p.025 p.026 p.026 p.027 p.027 p.027 p.028


5.4. Avantatges i inconvenients.................................................................................p.001 6. Cerca en retrocés.......................................................................................................p.001

6.1. Caracterís tiques.................................................................................................p.001 6.2. Procediment.......................................................................................................p.001 6.3. Complex itat.........................................................................................................p.001 6.4. Avantatges i inconvenients.................................................................................p.001

7. Mètodes derivats........................................................................................................p.001 7.1. Cerca en profunditat progressiva.......................................................................p.001 7.2. Cerca bidireccional.............................................................................................p.001

7.2.1. Caracterís tiques........................................................................................p.001 7.2.2. Procediment..............................................................................................p.001 7.2.3. Complex itat...............................................................................................p.001 7.2.4. Avantatges i inconvenients........................................................................p.001

8. Algoritme general per a la cerca sense informació del domini...................................p.001 IV. RECERCA HEURÍSTICA...................................................................................................p.001

1. Caracterís tiques......................................................................................................... 2. Elements..................................................................................................................... 3. Mètode irrevocable: mètode del gradient....................................................................

3.1. Caracterís tiques................................................................................................. 3.2. Procediment........................................................................................................ 3.3. Avantatges i inconvenients.................................................................................

4. Estratègies d’exploració d’alternatives....................................................................... 4.1. Cerca de “primer el millor”.................................................................................

4.1.1. Caracterís tiques........................................................................................ 4.1.2. Procediment............................................................................................. 4.1.3. Avantatges i inconvenients........................................................................

4.2. Cerca en feix (Beam Search)........................................................................... 4.3. Algoritme A*........................................................................................................

4.3.1. Caracterís tiques........................................................................................ 4.3.2. Procediment............................................................................................... 4.3.3. Avantatges i inconvenients..........................................................................

5. Cerca amb adversaris................................................................................................. 5.1. Descripció.......................................................................................................... 5.2. Dues possibles etiquetes....................................................................................

5.2.1. Etiquetes segons MÀX............................................................................... 5.2.2. Etiquetes MMValor....................................................................................

5.3. Mètode MIN-MAX............................................................................................... 5.3.1. Caracterís tiques..............................................................................................

p.028 p.029 p.029 p.029 p.030 p.030 p.030 p.030 p.030 p.031 p.031 p.031 p.032 p.032 p.034 p.034 p.034 p.035 p.035 p.036 p.036 p.036 p.036 p.036 p.037 p.038 p.038 p.038 p.038 p.039 p.041 p.041 p.041 p.042 p.042 p.042 p.043 p.043


5.3.2. Procediment.................................................................................................. 5.3.3. Avantatges i inconvenients............................................................................

V. LÒGICA ................................................................................................................................ 1. Introducció...................................................................................................................... 2. La lògica com a ciència.....................................................................................................

2.1. Definició i Objecte..................................................................................................... 2.2. Tipus de lògica........................................................................................................ 2.3. Elements de la lògica............................................................................................. 2.4. Principis.................................................................................................................. 2.5. Propietats.................................................................................................................

3. Lògica d’enunciats......................................................................................................... 3.1. Caracterís tiques..................................................................................................... 3.2. Veritat de proposicions.............................................................................................. 3.3. Regles d’inferència......................................................................................................

4. Lògica de predicats........................................................................................................... 4.1. Elements................................................................................................................. 4.2. Regles d’inferència...................................................................................................

5. Lògica modal....................................................................................................................... 5.1. Elements i caracterís tiques..................................................................................... 5.2. Regles d’inferència..................................................................................................

6. Lògica difusa.................................................................................................................. 6.1. Introducció................................................................................................................ 6.2. Elements: conjunts borrosos i funció de pertinència.................................................

6.2.1. Operacions amb conjunts borrosos.............................................................. 6.3. Modificadors lingüís tics.......................................................................................... 6.4. Regles d’inferència.................................................................................................

VI. REGLES ................................................................................................................................ 1. Introducció...................................................................................................................... 2. Elements............................................................................................................................ 3. Procés d’inferència......................................................................................................... 4. Dependència.................................................................................................................... 5. Inferència i encadenament................................................................................................

5.1. Encadenament endavant............................................................................................ 5.2. Encadenament endarrere...........................................................................................

6. Control del raonament..................................................................................................... 6.1. Necessitat............................................................................................................... 6.2. Mètodes.................................................................................................................

7. Recerca de regles...........................................................................................................



7.1. Cerca en retrocés................................................................................................. 7.2. Algoritme RETE.........................................................................................................

8. Avantatges i inconvenients........................................................................................... 8.1. Avantatges ................................................................................................................. 8.2. Inconvenients........................................................................................................

VII. XARXES ASSOCIATIVES.................................................................................................... 1. Introducció......................................................................................................................... 2. Definició de xarxa................................................................................................................ 3. Xarxes semàntiques...........................................................................................................

3.1. Definició i utili tat.......................................................................................................... 3.2. Model de memòria Semàntica de Quillian...............................................................

3.2.1. Caracterís tiques.......................................................................................... 3.2.2. Tipus d’enllaç....................................................................................................

3.3. Grafs de dependència conceptual de Schank........................................................... 3.3.1. Caracterís tiques........................................................................................... 3.3.2. Categories conceptuals............................................................................... 3.3.3. Relacions........................................................................................................... 3.3.4. Modificadors d’enllaços..................................................................................... 3.3.5. Tipus d’accions primitives..................................................................................

4. Xarxes proposicionals......................................................................................................... 4.1. Xarxes de Shapiro i grafs de Sowa........................................................................

5. Xarxes de classificació................................................................................................... 6. Xarxes causals...............................................................................................................

6.1. Xarxes Bayesianes................................................................................................. VIII.MARCS I GUIONS................................................................................................................

1. Introducció........................................................................................................................... 2. Marcs............................................................................................................................

2.1. Definició...................................................................................................................... 2.2. Descripció...................................................................................................................

2.2.1. Dues concepcions............................................................................................. 2.3. Elements....................................................................................................................

2.3.1. Facetes.......................................................................................................... 2.3.2. Dimonis........................................................................................................

2.4. Programació orientada a objectes............................................................................. 2.5. Representació.........................................................................................................

3. Guions............................................................................................................................... 3.1. Caracterís tiques.................................................................................................... 3.2. Elements......................................................................................................................



3.2.1. Escenes.................................................................................................... 3.2.2. Rols, objectes i llocs................................................................................. 3.2.3. Resultats................................................................................................... 3.2.4. Capçaleres................................................................................................

3.2.4.1. Que donen nom al guió.................................................................... 3.2.4.2. Que representen condicions............................................................ 3.2.4.3. Que representen instruments.............................................................. 3.2.4.4. Que representen llocs.....................................................................

3.3. Inferència........................................................................................................... 3.4. Avantatges i inconvenients.................................................................................

IX. INTEGRACIÓ.....................................................................................................................p.001 1. Introducció................................................................................................................. 2. Definició i característiques d’un sis tema integrat............................................................ 3. Propietats d’un sistema integrat................................................................................ 4. Arquitectures integrades............................................................................................ 5. Esquema d’una arquitectura integrada.....................................................................

5.1. Caracterís tiques estructurals.............................................................................. 5.2. Caracterís tiques funcionals...............................................................................

X. APRENENTATGE.............................................................................................................. 1. Introducció................................................................................................................ 2. Què és aprendre?...................................................................................................... 3. Perquè?...................................................................................................................... 4. Tipus d’aprenentatge.................................................................................................

4.1. Segons el procediment........................................................................................ 4.2. Segons la modificació.......................................................................................

BLOC III: ELS ESCACS: APLICACIÓ I EXPERIMENTACIÓ (PART PRÀCTICA) [p.103]

1. Aplicació dels conceptes al funcionament dels escacs............................................ 2. Experimentació amb els escacs................................................................................ 3. Conclusió......................................................................................................................

BLOC IV: CONCLUSIONS [p.121]

BLOC V: GLOSSARI [p.124]

BLOC VI: BIBLIOGRAFIA [p.128]

p.088 p.088 p.088 p.089 p.089 p.089 p.089 p.089 p.089 p.090 p.091 p.091 p.092 p.093 p.093 p.094 p.094 p.096 p.098 p.098 p.098 p.099 p.100 p.100 p.102

p.104 p.114 p.119

BLOG I. INTRODUCCIÓ

1

IA: Intel∙ligència Artificial INTRODUCCIÓ

Si bé el títol és IA: Intel∙ligència Artificial, per una raó purament estètica, podria dir que el treball

té un altre caire. La meva recerca es centra en la programació de la IA, en els mètodes utilitzats en

aquesta disciplina. Força sofisticada actualment (tenint en compte la joventut d’aquesta ciència),

pretenc donar resposta a una inquietud que podria ser resumida en la següent pregunta:

“Quines tècniques, algorismes utilitzen els especialistes per programar la IA? Dit d’una manera

més vulgar, com es programa una màquina perquè sembli intel∙ligent?”

Com es pot comprendre, aquesta recerca no pot ser entesa i valorada correctament sinó ens dins

d’un marc teòric. Evidentment, segueix sent un treball de recerca, però davant la impossibilitat

d’enfocar‐lo experimentalment (degut a la complexitat d’ell mateix i a la gran quantitat de

coneixements que es requereixen) o humanísticosocialment (degut que simplement no em volia

centrar en aquest aspecte, que tot i així podria ser possible), el meu treball ha de ser valorat dins

d’un context molt “de taula i cadira”. Descobrir els diferents algorismes i estratègies de

programació de la IA no es pot fer sinó que llegint, informant‐se, preguntant, enviant correus, i

llegint encara més. Però no per això ha de faltar “recerca”, sinó que aquesta consisteix en una

recerca no experimental, simplement molt analítica (literàriament parlant). Això, opino, és encara

més difícil, ja requereix una quantitat enorme de temps per la recerca de la informació, la lectura,

la comprensió, la síntesi i al organització, que en altres casos no hi és. Tot i això, he incorporat una

part pràctica per aplicar i valorar experimentalment tots els coneixements obtinguts.

El principal problema que m’he trobat és que aquesta especialització de la informàtica és,

precisament, una especialització. Els coneixements són molt tècnics, i és per tant molt difícil

aprofundir en un terreny tant complicat, degut als coneixements de base que es requereixen i que

un estudiant de batxillerat no té. A més a més, l’aprofundiment en algun cas no ha sigut possible

no només per aquest fet, sinó també degut a la falta d’espai. Tot això es podrà veure pel fet que a

mesura que avança el treball, els capítols contenen informació menys tècnica (no es compleix al

peu de la lletra, evidentment, i sobretot es fa present en els capítols 9 i 10), únicament per

aquesta raó: la temàtica és molt més tècnica a cada capítol que s’avança i indefinida (extensa).

Pel que fa a l’estructura, la primera part del treball conté el cos propi. El primer capítol constitueix

una breu introducció per familiaritzar‐se amb la IA: què, quan, com... El segon suposa una

introducció a la resta, una petita i breu explicació de com es programa un sistema intel∙ligent,

atenent als criteris generals. Del tercer fins el novè s’expliquen els mètodes bàsics de

2

IA: Intel∙ligència Artificial INTRODUCCIÓ

programació. Dic bàsics perquè actualment la situació està molt “difusa” i força desgeneralitzada.

Però és clar, és la base de tota l’actualitat, i no podria haver començat la casa per la teulada. De

l’actualitat només parlo de l’aprenentatge i la integració (capítol IX‐X), ja que intentar englobar‐ho

tot seria com impossible. Tot i això, aquests dos últims potser són els menys profunds, per les

raons que ja he comentat, sobretot tenint en compte que són els dos més actualitzats. El bloc III

constitueix la part pràctica, on es posaran en pràctica els coneixements adquirits analitzant

(experimentalment) la IA utilitzada en els escacs. Tant des d’una perspectiva interna com

històrica. Les conclusions suposen una reflexió de tot el treball i l’esforç i l’anàlisi‐resultat final. El

glossari conté totes les paraules de difícil comprensió, marcades en color blau en la seva primera

aparició. A algunes s’hi dedicarà un capítol sencer més tard, però es tracta de poder fer un esbós

el primer cop que les veiem i poder comprendre el que s’està dient aleshores, no més tard. Per

últim, la bibliografia conté, com és usual, les fonts d’informació.

I precisament, les fonts d’informació són molt variades. He consultat llibres (la majoria de

currículum universitari), diapositives (de professors d’universitat també), documents pdf, webs (la

majoria especialitzades), documentals i articles. També he mantingut entrevistes, i enviat més de

40 correus electrònics. Evidentment, m’he desplaçat en molts casos per obtindre aquesta

informació, i molta estava també en anglès. El cas, per això, és que en cap moment he transcrit

una sola paraula (excepte en algun cas especial com és un algorisme concret o algun exemple

d’un marc), doncs tot el treball és únicament sortit de la meva mà.

Per últim, crec interessant explicar el perquè de la tria. Sovint la naturalesa dels treballs de

recerca al∙ludeixen al nom (“treball de recerca”) però no a l’objectiu. En el meu cas, he considerat

sempre molt més important aquest últim. L’objectiu d’un treball de recerca ha de ser aprendre

(així ho proposa la Conselleria d’Educació), i per això, donat que la ja fa temps que vaig decidir

que en un futur m’agradaria especialitzar‐me en aquest camp com a enginyer, la meva recerca

s’ha centrat en investigar un territori que em serà útil. I que en un futur, hauré d’acabar

investigant igualment. No cal dir també, que és un tema que m’agrada, per això m’hi vull dedicar

d’aquí uns anys.

3

BLOG II. RECURSOS DE PROGRAMACIÓ UTILITZATS EN LA INTEL·LIGÈNCIA ARTIFICIAL

4

IA: Intel∙ligència Artificial I. CONCEPTES BÀSICS

I.CONCEPTES BÀSICS

1. Què és la IA? Entenem com a intel∙ligència artificial “IA”, aquell procés artificial que pretén recrear en una

màquina el comportament humà intel∙ligent.

Com que la IA, encara avui en dia, té un camp d’extensió força indefinit, diverses interpretacions

han donat lloc a definicions diferents. Alguns exemples poden ser:

‒ «La intel∙ligència artificial respon a l’art de crear màquines amb capacitat de realitzar

funcions que realitzades per l’home requereixen el que anomenem intel∙ligència»

(Kurzweil, 1990)

‒ «La intel∙ligència artificial és la ciència que estudia com realitzar accions que de moment

són realitzades de millor manera per l’home» (Rich y Knight, 1991)

‒ «La intel∙ligència artificial correspon a l’estudi de les facultats mentals mitjançant l’ús de

models computacionals» (Charniak y McDermott, 1985)

Tot i diverses interpretacions històriques, avui en dia s’entén a la intel∙ligència artificial com a una

disciplina dintre el gènere de la informàtica, i sovint s’hi associa inconscientment. Tot i estar‐hi

inclòs, la diferència entre informàtica i IA ha sigut objecte de moltes discussions, ja que encara avui

en dia no sabem ben bé on comença un i on acaba l’altre. Podríem dir que, actualment, intentar

que una màquina es comporti com un humà simplement consisteix en aplicar les tècniques de

programació conegudes, i la complexitat d’un sistema intel∙ligent serà la complexitat del seu

programa intern. Per tant, com distingim entre un sistema intel∙ligent i un sistema informàtic? En

molts casos és difícil, i es sostenen diverses teories sobre la independència entre aquests dos

camps. A grans trets, un joc d’ordinador podria ser una màquina intel∙ligent, o un sistema de rec

programat, o una calculadora... Tot i això, s’estudia dins un marc teòric molt més ampli del que és a

la pràctica, ja que fora de discussions, a la realitat necessitarem experts en intel∙ligència artificial

5

IA: Intel∙ligè

tan so

inform

El co

elabo

la el

l’info

simul

progr

huma

elabo

Un ex

Inform

d’un

respo

inform

2. 2.1El ter

hem

consi

ocasi

que

s’hav

Percmed

•

1Cal di

intel∙lig

ència Artificia

ols per a pro

màtic sense

onjunt (i a la

oració d’una

paper par

rmàtica) en

lació artifici

ramació teò

ans, sinó de

oració d’una

xemple amb

màtica) rep

sistema pro

osta podria s

màtic (escrip

Histò El termrme intel∙ligè

comentat m

dera el seu

ons al llarg d

responen au

via parlat de

cepció del di

•Informàtica i Electrònica

r que en algun ca

gent”, però gener

al

ocessos a pa

parar‐nos a

a vegada la

resposta da

rticular que

el conjunt.

al del com

riques1. Cal

el procés in

resposta:

b aquest patr

la senyal, s’e

ogramat int

ser efectuar

ptura d’un m

òria i dme IA ència artificia

més amunt, l

naixement

de la història

utomàticame

IA dins un m

Transmissla percep

•Ele

as quan, com per

ralment no

rtir d’un cert

pensar si est

finalitat) q

vant d’un pr

e realitzarà

Per tant, se

portament

remarcar, p

nformàtic qu

ró podria se

envia mitjan

el∙ligent, es

r un movime

missatge en u

desenv

al ha sofert

a intel∙ligènc

lligat a aqu

a. És clar, ja

ent a actes,

marc teòric, c

sió de pció

ctrònica

exemple, en els

t nivell, i per

tà aplicant IA

ue persegui

roblema, i pe

la intel∙ligè

egurament s

humà, i la

per tant, que

ue això req

r el d’un lec

çant un proc

transmet l

ent mecànic

na pantalla,

volup

varies interp

cia artificial

uestes; tamb

no des del p

com podria

om a capacit

Anàlisis i elabd'una respost

•Inform(IA)

avanços en l’actu

r nivells infer

A o no.

m sempre e

er tant caldr

ència artific

eria més co

IA simplem

e quan parle

uereix. Vege

ctor de targe

cés electròni

a resposta

(aixecar un

reproducció

pamen

pretacions al

deriva de le

bé s’ha parl

punt de vista

a ser, un sis

tat d’imitar l

boració ta

màtica

ualitat, parlarem

riors serà rea

en una màq

à distingir en

cial (integra

rrecte dir qu

ment en rea

em de IA no

em l’esquem

etes. La visió

ic, s’elabora

via electròn

a porta), o

ó d’un so).

nt

l llarg de la h

s ciències de

lat sobre aq

a informàtic,

stema eòlic.

a ment hum

Transmissió de la resposta

•Electrònica

de IA com tot el

I. CONCEPT

alitzada la fe

quina intel∙li

ntre la tasca

da dins el

ue el conjun

alitza les fu

o parlem de

ma del conj

artificial (El

una respost

nica un altre

bé realitzar

història. Si b

e la computa

quest terme

, sinó com a

També per

mana. Vegem

Efectula res

••

conjunt, com tot

TES BÀSICS

eina per un

gent és la

conjunta i

camp de

nt busca la

uncions de

imitar els

junt en la

ectrònica i

ta en mans

e cop, i la

un procés

é ara, com

ació, i se’n

en varies

a màquines

r exemple,

‐ho:

uació de sposta

MecànicaInformàtica

“l’aparell

6

IA: Intel∙ligè

2.2Cons

Aque

això,

ciènc

L’any

nomb

bases

abstr

consi

probl

El 19

les m

sistem

corre

McCu

articl

parla

Ja de

indep

Kte

2No és3 Cal es

ència Artificia

Històriiderem el n

esta va dona

cal esmenta

cia, tots ells r

y 1937, Alan

bres calculab

s de la inform

racte que er

dera la pre

lemes els qu

40 i 1941 es

màquines int

ma program

esponent, el

ulloch i Walt

e Computing

rem més end

es de la co

pendent i rec

300 a.CAristòtil250 a.C.

esibios d'Alex1315

Ramon Llu1879

Gottlob Fre1903

Lee De For

que la lògica sig

smentar que els o

al

ia aixement de

r‐li nom, va

ar l’existènc

relacionats a

Turing, mate

bles”, el qua

màtica teòric

ra capaç de

cursora de

als les comp

s construeixe

el∙ligents3, p

mable, men

lankalkül.

ter Pitts, i fin

g Machinery

davant.

nferència, o

coneguda, i a

xandria

ull

ege

rest

ui un tipus d’inte

ordinadors comu

e la IA el 19

establir‐ne l

cia de divers

mb les mate

emàtic brità

al tindrà una

ca i es parlav

llegir una c

les comput

putadores no

en les prime

per Alan Tur

ntres que Z

El 1943 es

nalment el 1

y and Intellig

on van assis

a partir d’aqu

•Parla de la estudia els

•Inventa un

•Desenvolu

•Perfeccionprimer ord

•Construeix

el∙ligència artificia

uns són un exemp

956, durant

les bases, i e

sos antecede

emàtiques, e

nic consider

a enorme in

va de la màq

cinta perfora

adores. En

o podran reso

eres computa

ring i Konrad

Zuse va af

crea la pri

1950 Alan Tu

gence, on es

stir nombros

uí en disting

intel∙ligència principis form

a màquina au

pa la idea de

a els coneixemre, molt més

x el tríode, tam

al primitiva, sinó q

ple de màquines

la conferèn

en resum, la

ents abans d

l naixement

at el pare de

nfluència de

quina de Turi

ada i interpr

aquest artic

oldre mai.

adores elect

d Zuse respe

fegir‐hi el

mera neuro

uring parla d

stableix el se

ses celebrita

im diferents

com a conjunmals del conei

utoregulada se

que el raonam

ments existencomplexa

mbé anomena

que és el primer

intel∙ligents

ncia a Darm

va consolid

de la consol

de la inform

e la IA public

s d’aleshore

ing (M.T.), un

retar‐ne una

cle també d

romecàniqu

ectivament. T

seu llengua

ona artificial

e IA per prim

eu famós Te

ats, parlem

períodes du

nt de silogismexement humà

egons el flux h

ment pot ser e

ns sobre la lòg

at vàlvula del

pas per imitar la

I. CONCEPT

outh college

ar com a ciè

lidació de la

màtica i el rao

ca un article

es. En ell s’e

n dispositiu

a resposta. L

demostrava

es, que són

Turing va in

atge de pr

l,en mans d

mera vegada

est de Turing

de IA com

urant la seva

es, i crea la lògà

hidràulic

efectuat artifi

ica i crea la lò

buit

intel∙ligència, co

TES BÀSICS

e (EE.UU.).

ència. Tot i

a IA com a

onament.

sobre “els

establia les

matemàtic

La M.T. es

que hi ha

la base de

ntroduir un

rogramació

de Warren

a en el seu

g, del qual

a ciència

història.

gica2, que

cialment

ògica de

nèixer‐la

7


2.2.1 Període clàssic o inicis (1956-1965) A partir del naixement a la conferència, es dóna especial importància a la realització de jocs

(escacs, dames, tres en ratlla..) i a la demostració de teoremes matemàtics sense atendre a la

necessitat de saber matemàtiques. També s’explora la possibilitat de realitzar taques lògiques

simples, sense arribar a un programa amb un coneixement del domini específic prou gran.

Cal destacar doncs el descobriment i desenvolupament de les xarxes neuronals associatives,

l’explosió combinatòria, l’heurística i en general, els mètodes simbòlics. És també quan es crea el

laboratori de IA a M.I.T. (Massachussets Institute of Technology).

Entre els èxits d’aquesta època es troba el GPS (General Problem solver), que resolia problemes

simples de sentit comú; el primer joc de dames intel∙ligent (aprenia dels errors) i STUDENT, creat

per resoldre problemes algebraics de secundària.

2.2.2 Període “romàntic” (1965-1975) Tot i l’èxit assolit en la primera etapa, entre 1965‐1970 la nova ciència sofreix uns anys obscurs,

doncs les previsions a 10 anys vista mai complides (proposades el 1956 a la conferència)

provocaren l’abandó pràcticament total d’aquest camp. Tot i això, s’acaben assolint interessants

avanços en la percepció (visió i parla), la comprensió del llenguatge natural, l’ús de les xarxes

semàntiques, la representació de dominis generals i el camp de la lògica. També es desenvolupen

els prototips (Marvin Minsky) i els perceptrons (Minsky i Seymour Papert).

Entre els assoliments cal esmentar ELIZA, un programa interactiu capaç de dialogar amb les

persones (tot i que sense entendre allò que diu); el Shakey robot, resultat de la unió de la

locomoció, percepció i raonament i solució de problemes i l’SCHOLAR, el primer tutorial d’escola

intel∙ligent.

2.2.3 Període modern (1975-actualitat) És en aquesta època quan la IA sofreix el segon boom més important després dels seus inicis. Les

investigacions s’expandeixen, entren en contacte amb altres camps i se’ls hi busca aplicacions

“reals”, fusionant‐se amb la medicina, la enginyeria, les finances, la exploració... És també l’època

8


de gran comercialització, empreses com General Motors utilitzen sistemes experts, i gran part de

l’activitat econòmico‐tecnològica sorgeix de la IA. Es desenvolupen els sistemes experts basats en el

coneixement (aprenentatge), el reconeixement de veu (més avançat), la lògica difusa (incertesa), i

es torna a les xarxes neuronals, juntament amb els algoritmes genètics.

Cal destacar el Deep Blue, el programa que va aconseguir derrotar l’aleshores campió mundial

d’escacs; el MYCIN, detector de malalties infeccioses a la sang; els míssils amb visió creats per a la

guerra del Golf; i nombrosos implants biònics, com receptors auditius per a persones sordes de

naixement.

2.3 Actualitat i futur Com ja hem comentat, actualment la IA gira entorn a la fusió amb altres camps, i les investigacions

principals se centren en l’aplicació dels resultats en el dia a dia (salut, negocis, ...). Destaquem

doncs, que cada cop més apuntem cap a la fusió entre la biologia i la tecnologia, ja que un cop

superada la primera fase de la enginyeria aplicada (la fase inorgànica: electrònica, mecànica,

química, informàtica, òptica,...), els humans volem aspirar a més, i ens estem endinsant en el món

orgànic, el món que ens permetrà algun dia superar‐nos a nosaltres mateixos.

I és que realment s’estan aconseguint avanços extraordinaris, doncs ens trobem actualment en fase

exponencial: dia a dia s’assoleixen nous reptes, i de la mà de la biologia, la medicina, i altres camps

s’estan desenvolupant projectes impressionants, sobretot en matèria de percepció d’estímuls.

Actualment ja tenim milers de ciborgs caminant pel carrer gràcies a l’ull biònic i els implants

auditius; i les primeres experimentacions amb animals apunten cap a nanorobots intel∙ligents de la

mida d’un glòbul vermell circulant per les nostres venes en busca de malalties infeccioses. Un dels

altres èxits interessants (fill d’Estats Units, com la majoria) és l’estudi detallat dels costums en la

vida diària (ja sigui el nombre de cops que t’aixeques del llit diàriament, el to de veu,..) per a la

creació d’un programa intel∙ligent capaç de detectar anomalies, com per exemple, un càncer.

També seria interessant comentar el funcionament d’un dels avanços citats poques línies més

amunt, l’ull biònic. L’ull biònic és la simulació de l’òrgan natural però de manera electrònica per

aquelles persones cegues de naixement. Després d’haver perfeccionat un xip, aquest s’implanta a

l’interior de la retina connectat al nervi òptic perquè enviï impulsos al cervell. Aquests impulsos són

9


rebuts en forma d’ones des d’unes ulleres que

integren un emissor i una càmera. El resultat seria

l’observat a la fotografia. Ens poc semblar poca

cosa, tot i així ens donem compte del gran avanç que suposa.

Però això només és el principi, ja que degut a la fase en que ens trobem, els avanços seran cada cop

més ràpids i eficaços. Segons la llei de rendiments accelerats de Raymond Kurzweil, un dels experts

pioners en aquest camp i el millor futurista4 del món, una ciència passa d’un creixement lineal a

exponencial quan es codifica les lleis que la regeixen. Es canvia el mètode d’assaig‐error pel de

desenvolupament a partir de models teòrics. I sinó observem la física, amb dos grans detonants

codificadors: les lleis de Newton i la mecànica quàntica. Precisament això és el que està passant,

ens estem accelerant, de tal manera que la situació d’aquí 10 anys serà 100 vegades més avançada.

Segons R.Kurzweil, el següent pas és la substitució de les neurones naturals per neurones

artificials. Això permetrà millorar les nostres capacitats (més intel∙ligència, eficàcia..), al pas que

podrem crear mons virtuals ja que els estímuls rebuts al cervell procediran de codificacions

informàtiques manipulables, no de reals. Així, podrem comunicar‐nos a través d’una xarxa virtual i

crear ambients fictícis. I per si fos poc, podrem arribar a realitzar còpies de seguretat del nostre

cervell, i la gent no entendrà com al 2010 ens passejàvem tan tranquils sense tenir la informació

resguardada. El més sorprenent de tot, per això, és que tot això està previst pel 2030

aproximadament.

I ja apuntant a final de segle, els resultats seran encara més sorprenents. Haurem arribat a la

singularitat, i a l’haver desxifrat totalment la mecànica quàntica i els processos biològics, serem

capaços de computar el material inanimat, de tal manera que programarem pedres, en les quals el

resultat efectiu dependrà de la quantitat d’energia que posseeixin. Com? Segons Einstein, d’una

pedra de 80 kg en podrem obtenir la mateixa energia que de la bomba d’hidrogen, gràcies a la

famosa equació E=mc2. A partir d’aquí obrirem nous camins a l’exploració espacial, i la enginyeria

s’estendrà a la mecànica celeste, modificant‐la al nostre gust com hem fet fins ara amb la majoria

de les propietats de la matèria al nostre abast. I gràcies a tot aquest conjunt, crearem un univers

intel∙ligent, transmetent al mateix temps tot el que coneixem al llarg de tot el territori que haurem

dominat.

4 En aquest cas, el que prediu basant‐se en estudis científics, no aleatòriament

10


Tot això ens pot semblar futurista, llunyà i poc creïble, però cal remarcar que aquest geni amb

especulacions desbordants ha predit, en vàries ocasions, “coses” que realment acabarien passant

(parlant en termes de tecnologia).

3. Aplicacions El primer que cal que recordem és que la IA forma part d’un “conjunt” (esmentat anteriorment)

amb una finalitat concreta.

Per això, no té sentit parlar de l’aplicació de la IA en particular, sinó que cal fer‐ho des d’un altre

punt de vista, tot explicant en quins “conjunts” es podria utilitzar, com per exemple:

‒ Lingüística computacional: creació de dispositius artificials amb habilitats lingüístiques.

‒ Mineria de dades: recol∙lecció, anàlisis i manipulació d’aquestes.

‒ Industrials: organització de sistemes de producció.

‒ Mèdiques: tals com detecció de malalties infeccioses, suplantació d’òrgans receptius

originals,...

‒ Mons virtuals: respon a la creació de cervells artificials , i en conseqüent manipular la

informació que hi circula per ells i crear mons no reals.

‒ Processament del llenguatge natural: captació, codificació i interpretació d’aquest.

‒ Robòtica: creació d’aparells que es comporten com humans i que realitzen les funcions

d’aquests.

‒ Sistemes de recolzament a la decisió: que ajuden a prendre decisions estudiant les

diferents variables, les possibilitats, els beneficis i els inconvenients.

‒ Videojocs: que simulen el comportament intel∙ligent de les interfícies, identitats o objectes

integrants.

4. La ment humana Com ja hem dit, l’objectiu primordial de la IA és simular el raonament humà. El tret característic

que el distingeix del de les altres espècies és l’existència d’intel∙ligència. Per tant, és lògic que per

codificar la ment humana, el primer que cal investigar és l’estructura d’aquesta, és a dir, del

11


coneixement i el funcionament de la intel∙ligència, per així aplicar‐ho a les màquines. Difícilment

podrem simular un comportament científic intel∙ligent si no som capaços de descriure’l.

4.1 La intel·ligència i el coneixement. Fonament psicològic És útil estudiar el procés intel∙ligent des d’una vessant psicològica perquè, ara per ara, és l’únic

mètode a partir del qual podrem codificar aquest procés i imitar‐lo. Cal recordar que, el que

realment ens interessa és la manipulació intel∙ligent de la informació que el nostre cap realitza,

però que aquesta forma part d’un procés (solucionar el problema en qüestió) més ampli, que no

podem oblidar i que ens és interessant en aquest apartat per tal d’aplicar‐lo a investigacions més

extenses sobre la IA en la seva integritat, no només en el treball de raonament i presa de decisions

que aquí treballem. El procés és el següent:

Però un cop descrit el procés, què és exactament la intel∙ligència, que és el que realment ens

incumbeix?

Definim intel∙ligència com aquella capacitat pròpia dels humans per adquirir informació i manejar‐

los en benefici propi. Per obtenir aquest benefici caldrà utilitzar els atributs, elements o capacitats

de la intel∙ligència:

‐ Organització i classificació: ens permet ordenar i trobar el sentit lògic de l’ordre per a

facilitar la comprensió i la memòria.

‐ Comprensió i assimilació: ens permet entendre millor les coses per a poder raonar.

12


‐ Raonament i operació: ens permet pensar, desglossar i estudiar les opcions, variables o

informacions que hem percebut per a poder obtenir millor benefici final.

‐ Criteri: ens permet diferenciar de les diferents propietats positives i negatives de les coses.

‐ Memòria: ens permet obtindre amb més o menys el coneixement i emmagatzemar‐lo.

‐ Rapidesa i fluïdesa: ens permet realitzar totes les operacions anteriors amb menys o més

habilitat.

‐ Creativitat, originalitat: ens permet manipular la informació mitjançant l’adició de factors

no captats.

En conseqüència, el grau de intel∙ligència serà proporcional al grau de benefici propi que s’obtingui,

considerant com a variables positives del benefici la rapidesa, la qualitat i la quantitat. Tot i això,

actualment es parla de vuit tipus d’intel∙ligència, que responen a vuit prototips de situacions o

problemes concrets i diferents en que caldrà utilitzar aquestes habilitats per obtindre el “benefici”.

Tot i això, la definició i l’extensió del concepte intel∙ligència és encara avui en dia bastant difusa i

controvèrsia: si n’hi ha 2 o 8 tipus, si és innat o es pot desenvolupar, etc...

La memòria, per això, és un dels trets més distintius de la intel∙ligència, i en conseqüent, un dels

més difícils de “codificar” per la IA. La memòria obté el coneixement, i els primers estudis en el

camp de la IA van demostrar que la intel∙ligència necessita del coneixement. I és lògic, un nadó de 4

dies és intel∙ligent, però la seva intel∙ligència no és efectiva degut a que no pot aplicar‐la, falta

coneixement. Per això, si volem que una màquina intel∙ligent, el primer que em d’estudiar és

l’emmagatzematge d’informació, l’aprenentatge, i posteriorment, procedirem a estudiar la

manipulació de la informació, i la conseqüent simulació de la intel∙ligència en el seu estat complet.

Algunes propietats del coneixement (poc desitjables per part dels experts), i que dificulten la

codificació d’aquest són les següents:

‐ És voluminós: seríem capaços de recordar TOT allò que hem après al llarg de la vida?

‐ És difícil de caracteritzar: com definiríem, per exemple, les propietats de l’aprenentatge

escolar respecte a l’aprenentatge del dia a dia, “l’experiència”?

‐ Canvia: per exemple, al errar, donem per suposat que aquell coneixement no és vàlid i el

transformem. També, a vegades el “creem”.

13

IA: Intel∙ligè

‐

4.2Tot i

intel∙

pràct

neuro

(cèl∙lu

trans

conse

4.2.Pode

òrgan

quad

S

Encè

C

C

Trl’e

5 Tract

ència Artificia

S’organit

diferents

La tranque ara ens

ligent (degu

ticament des

ona artificia

ula) de la qu

smissió d’aq

eqüent i tran

.1 El sistm subdividir

ns interns de

re de les fun

istema nervcentral

èfal

Cervell

Cerebel

ronc de encèfal

Me

tat aquí de forma

al

tza respecte

tipus de con

nsmissis és poc pràc

ut bàsicamen

sconegut), l’e

l idènticame

ual està form

quests, proc

nsmissió d’aq

tema ner‐lo de la seg

e funcions i

ncions desglo

Sistema

viós

Medul∙la espinal

a molt breu, degu

a la manera

neixement.

ió d’infoctic el coneix

nt a que, av

estudiem, ja

ent a la nat

mat el sistem

cessament

questa. Preci

erviós5

güent maner

nvoluntàries

ossades de to

nerviós

Sistemper

Sistema somàtic

Sistemsimpàt

Sisteparasim

ut a que el seu co

a que s’utilit

ormacióxement dels

vui en dia i d

a que possib

tural. I parl

ma nerviós, l

de la infor

isament el q

a:

s) i del siste

ot el sistema

a nerviósrifèric

a ic

ema mpàtic

Sistemautòno

onjunt en profund

tzarà: ja que

ó. Fonas factors biol

des d’una v

lement un d

em de neu

l’encarregat

rmació capt

ue intenta e

I

p

S

im

tr

c

e

l’

p

u

T

si

ma somàtic

a nerviós:

a m

ditat no és el més

en situacion

ament blògics que in

essant biolò

dia puguem a

rones perqu

de la captac

tada, elabo

mular la IA (

pel que fa

podríem dir

.N.C. proces

mportants,

ransmet els

onté l’òrgan

l cos, el

encèfal, i la

protegida pe

neix el S.N

Tanmateix, e

istema autò

(externs i v

s important per a

I. CONCEPT

ns diferents

biològicntervenen en

ògica, el raon

arribar a con

uè és la un

ció d’estímu

ració d’una

conjunt).

al seu func

que ment

ssa les fun

el S.N.P.

s estímuls.

n més import

cervell, qu

medul∙la es

r la columna

N.C amb el

el segon c

ònom (conn

voluntaris).

aquesta memòria

TES BÀSICS

utilitzarem

c n el procés

nament és

nstruir una

itat bàsica

uls externs,

a resposta

cionament,

re que el

cions més

capta i

El primer

tant de tot

ue integra

spinal, que

a vertebral

perifèric.

consta del

necta amb

Vegem un

a

14


Sistema nerviós central Sistema nerviós perifèric

Encèfal Sistema autònom6 Sistema somàtic

Cervell

‐ Raonament

‐ Respostes

‐ Processament informació

‐ Vida psíquica

‐ Vida emocional

‐ Funcions primàries (son, gana...)

Sistema

parasimpàtic

‐ Contracció de la pupil∙la

‐ Estimula la salivació

‐ Redueix el batec cardíac

‐ Contrau els bronquis

‐ Estimula l’activitat digestiva

‐ Estimula la vesícula biliar

‐ Relaxa el recte

‐ Olfacte

‐ Visió

‐ Músculs de l’ull

‐ Músculs masticatoris

‐ Músculs de la cara

‐ Audició

‐ Equilibri

‐ Orientiació

‐ Gust

‐ Músculs de la llengua

Cerebel

‐ Equilibri

‐ Activitat motora (esports, pràctica

d’un instrument...)

‐ Control de músculs Sistema

simpàtic

‐ Dilatació de la pupil∙la

‐ Inhibeix la salivació

‐ Augmenta el batec cardíac

‐ Relaxa els bronquis

‐ Inhibeix l’activitat digestiva

‐ Secreció de glucosa pel fetge

‐ Contrau el recte

Tronc

de

l’encèfal

‐ Funcions fisiològiques

‐ Actes reflexos

‐ Dolor

‐ Estats de dependència

4.2.2 La neurona i la sinapsis La neurona és la cèl∙lula a partir de la qual està

constituït tot el sistema nerviós. Consta del nucli

amb ramificacions (dendrites), de la

prolongació(axó) i el final (“cua”). Per

transmetre la informació, les neurones s’envien

impulsos electroquímics entre elles, des de la

cua de la emissora fins al cap de les receptores, ja que l’espai que existeix entre elles és mil∙limètric.

Això és possible gràcies a la diferència de càrrega entre l’interior de la neurona i l’exterior

(polarització) . L’interior consta de nombroses molècules de càrrega negativa, mentre que l’exterior

està rodejat de ions positius, els potàssics (K+) amb lliure circulació entre l’interior i l’exterior, i els

sòdics (Na+). Un cop emès l’estímul,aquest es transmet degut a això de la següent manera:

Els ions potàssics penetren a l’interior de la cèl∙lula com a conseqüència de la repulsió originada per

l’impuls elèctric, i aquests produeixen un canvi en la constitució de la membrana, la qual es torna

permeable als ions sodi. Al penetrar aquests a l’interior de la membrana, la cèl∙lula es despolaritza, i

degut a la càrrega originada a l’interior del nucli (positiva), anomenada potencial d’acció i la càrrega

DENDRITES

NUCLI CUA

AXÓ

6 Entenent funcions aquí com “funcions de les quals transmeten la informació”

15


natural de la neurona a la cua (negativa), s’origina una diferència de potencial que transmet

l’impuls al llarg de la cèl∙lula.

La transmissió de l’impuls de la cua al cap de la següent neurona és possible gràcies a que una

vegada ha arribat la senyal elèctrica a aquestes, s’estimulen les vesícules presinàptiques, que

segreguen neurotransmissors. Aquests s’uneixen a receptors específics que creen la despolarització

de la neurona, per tal de tornar a repetir el cicle.

5. Diferències entre la intel·ligència natural i artificial Línies amunt hem descrit els atributs de la intel∙ligència natural. Si bé se suposa que la IA el que

pretén és imitar‐los, sempre existirà diferències entre un tipus i l’altre, conseqüència dels buits

tecnològics que encara trobem, fins que arribem al que hem denominat com a singularitat. Vegem‐

ne per tant les diferències que trobem avui en dia:

‒ Si la velocitat dels nostres impulsos és de 30 m/s, els electrònics viatgen a la velocitat de la

llum

‒ Mentre que la ment humana pot absorbir quantitats d’informació indeterminades en molt

poc temps i amb poca exactitud, els sistemes artificials necessiten informació molt

concreta, exacte i molt més temps per processar‐la.

‒ Si bé que en els humans la freqüència de l’impuls pot variar, en les computadores la

freqüència de transmissió és inalterable i ve donada per el rellotge intern del sistema.

‒ La sinapsis transmet varies informacions de cop, mentre que les comportes lògiques tenen

una sola funció determinada.

‒ D’una banda, la memòria natural és de tipus associatiu i no sabem on quedarà guardada,

però de forma contrària, la memòria artificial té un directori localitzable.

16


I no cal anomenar que també trobem moltes similituds, ja que és precisament el que busquem. Tot

i això, la actualitat està lluny de complir el famós Test de Turing7 per arribar a la singularitat.

6. Avaluació d’un sistema intel·ligent Tradicionalment, no sabem de l’èxit d’alguna activitat, procés, aparell o qualsevol concepte fins que

no en verifiquem els resultats nosaltres mateixos els resultats o confiem en les paraules dels que

l’han verificat. Per exemple, no sabrem si el mètode d’argumentació que fem servir per a convèncer

algú és productiu fins que realment no aconseguim convèncer algú (o ens creguem alguna persona

que ho hagi aconseguit). D’aquesta manera, per verificar l’èxit d’un programa o dispositiu humà

l’únic mètode del que disposem és el mètode d’assaig‐error o la credulitat.

I un cop verificat, per mesurar qualitativament els resultats obtinguts els haurem de comparar amb

els resultats que obtindríem en mans d’un ésser humà, prenent com a punt de referència aquests

últims (un bon mètode és el test de Turing, que s’exposa tot seguit). Si els sobrepassa, el programa

o dispositiu serà més eficient que un ésser humà, i serà tot un èxit. Si l’iguala, serà simplement un

èxit. Però si realment no ho aconsegueix, aquest haurà fracassat.

Tot i això, el fracàs no sempre s’ha d’interpretar negativament, ja que possiblement el que

preteníem no era igualar‐ho completament (també podríem fixar el llistó en un altre lloc que no fos

la naturalesa humana), ja que per això en molts casos encara falten anys, i a més a més, que hagi

fracassat en un aspecte, no vol dir que hagi fracassat en tot, doncs podem avaluar molts aspectes,

entre els quals cal destacar:

1) Efectivitat: respon a l’èxit assolit quan s’hagin obtingut els resultats esperats.

2) Eficiència: respon a l’èxit assolit quan s’hagi realitzat la tasca amb les millors condicions

possibles (econòmiques, de temps, tècniques...).

3) Interès: respon a l’èxit assolit quan s’hagi resolt un problema interessant.

4) Utilitat: respon a l’èxit assolit quan s’hagi resolt un problema útil.

7 L’exposarem a continuació

17


Per tant, per verificar l’èxit d’un dispositiu amb IA integrant, caldrà avaluar aquests aspectes

seguint els mètodes que acabem d’exposar.

6.1 El test de Turing Correspon a un mètode establert per Alan Turing, de qui ja hem

parlat, com a objectiu d’avaluar els aspectes convenients en

referència a un humà, que com hem comentat, serà el punt de

referència.

El test consisteix en una prova molt simple, en que un humà

interactua amb una pantalla fent‐li preguntes. Segons Turing, quan

aquest no sàpiga distingir qui és el que li respon (home o màquina), el programa serà tot un èxit.

Aquest mètode va ser publicat en la revista mind l’any 1950.

18

IA: Intel∙ligència Artificial II. PROGRAMACIÓ DE LA INTEL∙LIGÈNCIA: CRITERIS GENERALS

II. PROGRAMACIÓ DE LA

INTEL.LIGÈNCIA;

CRITERIS GENERALS

Un cop vist els conceptes més generals i “assequibles” sobre el camp de la IA, en els pròxims

capítols exposarem com treballa realment la IA. És a dir, quins són els mètodes que utilitza per

simular el comportament humà en un dispositiu. Aquests mètodes seran explicats per separat

en cada capítol, especificant les situacions idònies en les que podrien ser utilitzats. I per últim,

en el capítol “Integració” es donarà una perspectiva àmplia per englobar tots els mètodes

treballats en una situació concreta, que és com realment sorgeixen en la vida real, no per

separat com fins aleshores els haurem vist.

Tot i això, aquest capítol parlarem dels criteris generals amb els quals treballa la IA, aquells que

són comuns independentment del mètode utilitzat: ordre, objectius,...

1. Objectiu: Què?

El primer que ens hem de plantejar al realitzar aquest treball és: per a què serveix la ment

humana? És a dir, perquè la volem imitar? Com hem dit en apartats anteriors, l’objectiu de la

intel∙ligència és l’obtenció de benefici per part del qui la posseeix, i per tant, lògicament això

serà també el que perseguirà la computadora.

El benefici s’obté bàsicament amb la manipulació d’alguna cosa (situació, idea,..) el que en

termes de IA anomenarem estat per tal d’arribar o generar a una altra “cosa” (idea, acció,

conclusió,...). Per fer‐ho, es parteix de la base sempre de que s’haurà de solucionar el que

s’anomena problemes.

19


Per tant, qualsevol situació s’estructurarà en forma de problema i serà tractada i estudiada com

a tal, de la mateixa manera que els mètodes de resolució seran pensats en base a problemes,

amb les resolucions i el tractament respectiu. Això sembla banal, però resulta molt important

des del moment que necessitem una estructuració, i més avui en dia, quan la metodologia es

torba tant diversificada.

En general, podem afirmar que un problema és, o posseeix,

- Una descripció de la situació de la que es comença.

- Una descripció de la situació a la que es vol arribar.

- Una descripció dels mitjans dels quals disposem per aconseguir en nostre objectiu.

2. Metodologia: Com?

Cal tindre en compte com a criteri general és que el programa seguirà el procés següent de

desglossament de la informació que ens arriba, imitant el que succeeix en la ment humana:

Un cop obtenida la informació pertintent i necessària, el que caldrà fer és interpretar‐la i

entendre el que ens demanen. És evident que no es pot solucionar una tasca sense atendre a la

comprensió de la mateixa naturalesa d’aquesta.

Execució i verificació

Establiment de mètode de resolució

Subdivisió en tasques

elementalsInterpretació

Informació

Tasca 1 Mètode seleccionat

Execució amb errors

Execució òptima

Tasca 2 Mètode 2

Biblioteca de mètodes Modificació

20


Posteriorment, caldrà desglossar la tasca en tasques més elementals. Ja no s’estudia la IA des

d’una vessant “definida”, com en els inicis, en que les tasques eren enteses com un conjunt

simple que requerien una sola solució determinada. Sinó que ara, s’atén a les tasques com a

objectius de naturalesa múltiple, les quals han de ser desglossades i ramificades fins a arribar a

tasques primitives elementals.

Tot seguit, caldrà establir el mètode de solució o d’elecció de la solució per a cada tasca

descomposta, que serà buscat a la biblioteca de mètodes. La biblioteca de mètodes serà l’espai

abstracte on emmagatzarem els diferents mètodes per a la resolució (en els quals es basa tot

aquest treball), i cal esmentar que aquests podran ser modificats al pas que el programa

evoluciona, ja que com hem comentat, l’actualitat aprofundeix en la naturalesa de

l’aprenentatge dels sistemes (i això implicarà modificar la naturalesa interna). Per tant,

distingirem entre els termes programa fix i programa modificat per el problema.

Per últim, cada tasca i cada mètode respectiu seran efectuats. Els mètodes aplicaran un

raonament, una operació, o qualsevol procés necessari per a la resolució del que ens demanen,

un cop executat, es procedirà a la avaluació interna per part de la computadora (si aquesta

considerés que la resolució té lògica o no, per exemple), i segons els resultats obtinguts, es

procediria a crear un programa modificat i executar la resposta o simplement executar‐la

directament. Cal distingir entre dos tipus de escoles o mètodes generals de resolució o aplicació:

‐ Bottom‐up: construir rèpliques del cervell humà (neurones artificials)

‐ Top‐down: simular el comportament humà mitjançant programes informàtics

Cal esmentar, per això, que els mètodes de resolució és la part més substanciosa de la IA, i que

aquests seran tractats de forma individual i aprofundida en els següents capítols.

21

IA: Intel∙ligència Artificial III.RECERCA SENSE INFORMACIÓ DEL DOMINI

III. RECERCA SENSE

INFORMACIÓ DEL DOMINI

1. Característiques De tots els mètodes que coneixem, el mètode de recerca sense informació és possiblement el

més senzill en quan a funcionament de tots els que coneixem. Per això, va ser el primer en ser

utilitzat a la dècada dels cinquanta‐seixanta (inicis).

Aquest mètode és utilitzat en els problemes on a partir d’un estat inicial volem arribar a un estat

final, i no sabem quin camí elegir, és a dir, quins canvis fer. Computacionalment, consisteix en

partir d’un estat inicial explorant els diferents estats o possibilitats que es podrien generar i

l’elecció del camí òptim que condueix al estat on volem arribar. Tanmateix, l’exploració no atén

a la naturalesa del domini, és a dir, no coneix les diferents opcions ni estats els quals analitza.

Per això, simplement consistirà en un pur desenvolupament combinatori, donant exactament la

mateixa importància a tots els estats i analitzant‐los tots (es clar, no se’n pot saltar cap, doncs

no coneix la naturalesa d’aquests).

Com ja he dit, les bases d’aquest mètode troben el seu fonament (matemàtic) en la

combinatòria, i en conseqüència s’utilitza per a processos reals molt senzills o bé idealitzats, en

els que el raonament es podria comparar amb una simple elecció entre varies opcions.

Malgrat tot, si bé l’objectiu és trobar un estat concret, existeixen diversos mètodes d’exploració,

els quals veurem a continuació, juntament amb els elements i requisits que tenen en comú els

diferents mètodes, és a dir, els elements propis de la recerca sense domini de la informació.

22


2. Elements Per a la recerca sense informació del domini es requereix un arbre (graf) a través del qual

realitzarem l’exploració. Aquest arbre constarà d’un estat inicial i d’una sèrie d’operadors

(accions que modifiquen l’estat) que generaran els altres estats. La recerca consistirà en trobar

l’estat que correspon a l’estat meta (estat al qual volem arribar, que serà la solució al problema)

segons el mètode d’exploració utilitzat. Un arbre té els següents elements o conceptes:

− Node: Representa un estat

− Arc: Representa un operador. Un arc enllaça dos nodes

− Expandir un node: Generar tots els nodes successors possibles (a través de l’aplicació de

diferents operadors)

− Node o estat tancat: Aquell que ja ha estat expandit

− Node o estat obert: Aquell que no ha estat expandit parcialment o totalment

− Cost d’un arc: Valor del temps requerit per aplicar un operador a un estat (per defecte

1)

− Cost d’un node: Valor del temps requerit per enllaçar l’estat o node inicial fins al node

en qüestió

− Espai d’estats: Conjunt dels mateixos que es podria obtenir al aplicar tots els operadors

possibles a cada estat. És a dir, el conjunt total d’estats.

− Factor de ramificació: Nombre mig de nodes descendents (o fills) d’un node concret

− Longitud de trajectòria: Nombre de nodes generats en un camí o trajectòria

− Profunditat: Distància més curta entre el estat inicial i la meta

Cal destacar que pot ser que a un estat no se li pugui aplicar tots els operador disponibles, és a

dir, que a cada estat se li puguin aplicar només uns operadors concrets. I a més a més, perquè

un arbre sigui apte per aquest mètode, cal que es compleixi els següents aspectes: no ha cicles

ni bucles ; que existeixi un node que no té avantpassats (pares) i que ho sigui de tots els demés

(node inicial) ; i que cada node excepte la arrel (node inicial) tingui un pare.

23


Un exemple adequat que reflecteixi tot això podria ser el problema de les garrafes de vi. Aquest

problema típic consisteix en: tenint una garrafa de 4 ℓ i una de 3 ℓ, i podent només buidar i

omplir totalment i passar d’una garrafa a l’altre, s’ha d’obtenir qualsevol garrafa amb 2 ℓ (la

gràcia és que no tenim instruments de mesura). Doncs bé, sent l’estat inicial 2 garrafes buides i

sent els operadors buidar, omplir i passar, l’arbre corresponent (que la computadora hauria de

desenvolupar i explorar fins a trobar l’estat “4 o 3 tenen 2 ℓ” tot tornant la solució) seria el

següent:

3. Requisits Per utilitzar el mètode exposat en aquest capítol per a la resolució d’un problema, cal que el

problema compleixi les següents condicions:

− Que hi hagi la possibilitat d’associar un conjunt d’estats a les diferents situacions

possibles de tots els components del problema.

− Hi ha un estat inicial des del qual podem començar el procés.

− Existeixen operadors, tals que, com hem comentat, aplicats als estats produeixen estats

nous.

PASSAR 1 A 2

OPERADOR: OMPLIR 1 OMPLIR 2

OMPLIR 2 BUIDAR 1

PASSAR 2 A 1

OMPLIR 2

PASSAR 1 A 2

ESTAT FINAL

Etc … …

…

…

…

24


4. Cerca en amplitud 4.1 Característiques

És aquell tipus de mètode d’exploració de recerca sense

informació en que es revisa totes les trajectòries d’una

determinada longitud abans de crear‐ne una de nova. És a

dir, és aquell mètode que analitza per nivells, i no expandirà

els nodes al nivell n fins que no hagi revisat el nivell n‐1 (tal

com mostra la figura). Per fer‐ho, es crea una llista de nodes

oberts denominada ABIERTA, on s’emmagatzemaràn tots els nodes revisats que es vulguin

expandir posteriorment.

Aquest mètode és de tipus cua o FIFO (First in First Out). Aquest nom fa referència a que es dóna

prioritat i s’analitzen primer els nodes que primer s’han creat.

4.2 Procediment

Per a aquest mètode, caldrà seguir el següent algoritme, que seran els passos que programarem

a la computadora amb el llenguatge corresponent:

1. Crear una llista de nodes anomenada ABIERTA i inicialitzar‐la amb un únic node arrel, al

que se li assigna l'estat inicial del problema plantejat.

2. Fins que ABIERTA estigui buida (no té més nodes per expandir, és a dir, no té solució) o

es trobi una meta realitzar les següents accions:

2.1. Extreure el primer node d'ABIERTA, i anomenar‐lo m.

2.2. Expandir m. Per a cada operador aplicable i cada forma d'aplicació (un cop

analitzats tots es torna a 2):

2.2.1. Aplicar a m, crear un punter des de l'estat creat a m.

25


4.3 Complexitat

Defineix quant de complex és un graf analitzat segons aquest mètode, i s’expressa com

O(fórmula). Pot ser de dos tipus:

− Temporal: respon al temps invertit per a trobar la solució. Depèn del factor de

ramificació (explicat a l’apartat 2 d’aquest capítol) i de la profunditat de la solució (nivell

en el que es troba). Si n és el factor de ramificació i p el nivell de profunditat, la

complexitat respon a la potencia O(np). Per exemple, si es dóna el cas que la mitjana de

nodes descendents des del node inicial és 3 i la solució està al nivell 4, la complexitat

serà 34, doncs haurem hagut d’invertir 34 nodes fins a arribar al node meta.

− Espacial: respon a l’espai requerit (d’emmagatzematge) per a trobar la solució. Depèn

dels mateixos factors que la temporal, i coincideix, ja que en aquest sistema l’espai

recorregut és igual al temps transcorregut, doncs el camí total (complexitat espacial)

desenvolupat fins a trobar la solució s’ha agut d’explorar tot.

4.4 Avantatges i inconvenients

− Avantatges: si el problema té solució aquest procediment garanteix trobar‐la ,i en el cas

d’existir diverses metes troba la de menor cost o profunditat.

− Inconvenients: si el nivell de profunditat és menor que el nivell de ramificació

s'expandeixen molts nodes inútilment, doncs fins a arribar al nivell 15 s’hauran agut de

desenvolupar també els altres 15 nivells del node inicial i els seus fills. Per això, diem

que el seu principal desavantatge és l'espai d'emmagatzematge requerit (pràcticament

inviable).

2.2.2. Si el nou estat és l’estat meta sortir del procés iteratiu iniciat en 2.2 i tornar al

programa aquest estat, sinó, 2.2.3. Incloure el nou estat en ABIERTA (doncs l’expandirem més tard)

26


Per tant, aquest sistema serà més efectiu quan l’estat meta es trobi en un nivell immediat al de

l’estat inicial, independentment del desplaçament horitzontal, si dreta o esquerra.

5. Cerca en profunditat 5.1 Característiques

Aquest sistema es diferència del primer (cerca en amplitud) pel

fet de que no recorre el graf de manera horitzontal, sinó vertical

(tal com es mostra en la figura). Per tant, l’arbre s’explora per

nodes, i no s’expandirà un altre node fins haver acabat de revisar‐

ne primer un (independentment del nivell). Per exemple, en la figura, no expandirem el node 2.2

fins no haver revisat el 2.1, i el 1.2 fins haver revisat el 1.1, i així successivament. A més a més, se

sol establir el límit d’exploració, que marcarà la màxima profunditat (lp) que pot adquirir un

camí des del node inicial. Saber‐lo, ens pot ajudar a raonar si és òptim aplicar aquest mètode (lp

no molt llarg) o no (lp llarg). Cal recordar que aquí també s’utilitzarà una llista de nodes

denominada ABIERTA on s’emmagatzemaran tots els nodes expandits per analitzar.

Aquest mètode és de tipus pila o LIFO (Last in first out), ja que s’analitza sempre l’últim node

generat.

5.2 Procediment

L’algoritme corresponent seria el següent:



2. Fins que ABIERTA estigui buida o es trobi una meta realitzar les següents accions:


27


5.3 Complexitat

− Temporal: serà la mateixa que en la cerca en amplitud, donat que segueix els mateixos

criteris explicats allà, i pot aplicar‐se el mateix exemple que allà.

− Espacial: com que, a diferència de la cerca en amplitud, no és necessari recórrer tots els

nivells inferiors a la meta, la C es defineix aquí per O(n∙p), sent p la profunditat de la

solució i n el factor de ramificació. Per exemple, si tenim que la profunditat de la solució

en 4 i per cada node a partir de l’inicial es dóna una mitja de 3 sucessors, dons haurem

hagut de recórrer un espai de 3∙4 nodes.

5.4 Avantatges i inconvenients − Avantatges: poca complexitat espacial respecte a la cerca en amplitud. A més a més,

com més solucions existeixin, més eficient és el mètode.

− Inconvenients: el temps recorregut, ja que si el algoritme avança per una branca sense

solució es perd una quantitat considerable de temps. Per tant, per això és útil per aquest

mètode determinar lp. Si és molt més gran que la profunditat de la solució, el mètode

seria ineficient, i si fos més petit això significaria no trobar mai la solució, ja que no

existiria.

2.2. Si la profunditat de m és igual a lp, tornar al pas 2 (doncs ja no hi hauran més nodes

per analitzar aquí)

2.3. Expandir m i emmagatzemar tots els successors a ABIERTA

2.3.1. Si algún successor de m és meta, tornar el camí a la solución

2.3.2. Si algún successor de m no té més fills, eliminarl‐lo de ABIERTA, doncs no

podrem expandir‐lo

28


6. Cerca en retrocés 6.1 Característiques

La cerca en retrocés neix de la ja comentada cerca en profunditat, i en conseqüència hi guarda

una estreta similitud. L’ordre de recorregut dels nodes és el mateix, i per tant la imatge

corresponent seria la mateixa. L’única diferència seria que en comptes de generar tots els

successors en arribar a un node que no és meta o punt mort (no té successors) i

emmagatzemar‐los a ABIERTA per a ser explorats després, simplement es genera un node (el

que serà explorat) per a cada pas, estalviant així tot l’espai que suposa l’acumulació de dades de

ABIERTA.

6.2 Procediment

L’algoritme seria el següent:



2. Fins que ABIERTA estigui buida o es trobi una meta realitzar les següents accions:


2.2. Si la profunditat de m és igual a lp, o si simplement no té més successors possibles,

eliminar‐lo de oberta i tornar al pas 2. Sinó,

2.3. Generar un nou successor m’ i senyalar que la branca ha estat considerada

2.3.1. Si m’ és meta abandonar i tornar la solució

2.3.2. Si m’ es troba en un carreró sense sortida elminar‐lo de oberta

2.3.3. Si no compleix cap dels requisits anteriors, tornar a 2.

29


6.3 Complexitat

− Temporal: exactament igual que en els mètodes anteriors [O(np)], doncs per molt que

haguem eliminat els nodes “inútils”, haurem hagut d’invertir el temps en explorar‐los.

− Espacial: com que només és necessari emmagatzemar els nodes correctes, la

complexitat espacial serà de l’ordre O(p), donat el cas que coincidirà amb la profunditat

del node meta.

6.4 Avantatges i inconvenients

− Avantatges: ja es pot deduir que un dels principals punts positius d’aquest mètode és la

poca complexitat espacial requerida.

− Inconvenients: no poder conèixer‐se el límit de profunditat lp (no sabem si el camí

explorat és el més llarg o no). L’eficiència temporal queda limitada pel seu caràcter

fortuït, a causa de la inexistència d’ordre d’exploració.

7. Mètodes derivats 7.1 Cerca en profunditat progressiva

Aquest mètode no és més que una cerca en profunditat per nivells on el límit d’exploració va

augmentant progressivament una unitat per nivell. Dit d’una altra manera, consisteix en repetir

la cerca en profunditat, augmentant d’un en un el límit de profunditat amb el que es realitza la

recerca anterior. Aquest es el mètode de menor cost i més eficient, de complexitat temporal

O(np) i espacial de l’ordre de O(p).

7.2 Cerca bidireccional

Tot i tenir prou consistència, aquest mètode s’exposa aquí degut a ser una combinació de varis

mètodes anteriors.

30


7.2.1 Característiques

En la cerca bidireccional no es pretén trobar el camí a l’estat meta des de l’estat inicial, sinó que

a més a més, es pretén trobar el camí des de l’estat meta a l’estat inicial (sentit contrari) amb

una exploració paral∙lela. Quan obtinguem el primer punt en comú entre els dos camins, es

tracta de fusionar les dos trajectòries per obtindre el recorregut des del node primer fins al node

meta. Per garantir la convergència l’únic requisit existent és que almenys un dels dos mètodes

d’exploració correspongui a la cerca en amplitud.

7.2.2 Procediment

Caldrà introduir el següent algoritme:

7.2.3 Complexitat

− Temporal: la complexitat temporal és de l’ordre O(np/2), doncs reduirem el nivell “final”

o “solució” (en aquest cas no correspon al nivell de l’estat meta) a la meitat, gràcies al

fet de tenir l’altra cerca treballant al mateix temps.

− Espacial: la condició imposada per la convergència (comentada anteriorment) permet

afirmar que la complexitat espacial respondrà a la magnitud O(np/2), ja que necessitarem

la meitat de nivells espacials per trobar la solució.

1. Inicialitzar dos grafs de recerca. En el primer (A.1), el node arrel serà el estat inicial del

problema

2. Plantejat, i el segon (A.2) tindrà com arrel la meta del problema en qüestió

3. Inicialitzar el límit d’ exploració lp=1.

4. Continuar la cerca en (A.1) fins lp.

5. Continuar la cerca en (A.2) fins lp.

6. Comprovar si algun dels estats generats coincideixen, sí és així tornar la solució, sinó

tornar al pas 2.

31


7.2.4 Avantatges i inconvenients

− Avantatges: la divisió del factor exponencial de la complexitat n’és un dels principals

avantatges.

− Inconvenients: el límit d’exploració, ja que el nombre de iteracions abans de canviar el

sentit de la recerca és un paràmetre crític per aquest mètode. Un altre dels

inconvenients és el fet de no disposar d’algun criteri addicional per poder ordenar la

selecció de nodes meta al llarg del procés.

8. Algoritme general per la cerca en grafs Deixant de banda tot el que s’ha explicat línies més amunt, és important, independentment del

mètode utilitzat, procurar que no es repeteixi cap exploració d’un node ja explorat (nascut com

a conseqüència de que a l’expandir un estat mitjançant un operador, generi un estat ja revisat

anteriorment). Per això, com a complementació del sistema de recerca (és combinable), cal

introduir‐hi un algoritme anomenat “algoritme general per a la cerca en grafs”, que evita que la

computadora caigui en un cicle.

Aquest algoritme parteix de la base de que a part de la llista ABIERTA, on emmagatzemarem els

nodes generats però que encara no hauran estat expandits (degut a que s’està expandint un

altre node també generat al mateix temps, i no podem realitzar dos funcions al mateix temps),

també crearem una altra llista anomenada CERRADA. En aquesta última s’emmagatzemen els

nodes d’ABIERTA seleccionats per a l’expansió. Aquesta selecció es pot fer per un criteri

heurístic (com per exemple, “menor distància estimada a la meta”), i el conjunt serveix per no

repetir l’expansió d’un node existent a CERRADA.

Un cop establert el criteri per evitar la repetició, es convenient en qualsevol recerca en un graf

crear un arbre alternatiu que marqui quin és el camí més curt per a accedir a un node. Això ens

permetrà, quan es doni el cas de repetició a l’expandir un node, continuar treballant a partir del

menys costós, és a dir, a partir del de menor profunditat. Quan passi això, es poden donar tres

situacions, segons el tipus de node repetit, a les quals respondrem de la següent manera:

32


− Que el node generat no estigui ni a ABIERTA ni a CERRADA: En aquest cas simplement

l’enllaçarem amb el seu pare i no caldrà seleccionar quin dels dos seleccionar, ja que

com que no està a cap de les dues llistes no haurem de treballar amb ell, és a dir, no

l’haurem d’expandir.

− Que el node generat estigui a ABIERTA: En aquest cas hi haurà un nou camí (el del

segon node, el repetit), i haurem d’elegir entre els dos per a continuar treballant.

− Que el node generat ja estigués a CERRADA: A part de realitzar el procés anterior,

caldrà explorar els descendents d’aquest per si s’hagués de realitzar el mateix procés en

algun dels seus descendents, donat que podria ara existir un camí més curt per als

descendents.

Un cop explicat com funciona l’algoritme general, anem a determinar‐lo:

1. Crear un arbre d’exploració G que conté un node amb la descripció del problema. Crear

tot seguit una llista ABIERTA i assignar‐li el node en qüestió.

2. Crear CERRADA, que inicialment estarà buida.

3. Fins que es trobi la meta o es ABIERTA estigui buida, realitzar el següent:

3.1. Eliminar el primer node de ABIERTA i traspassar‐lo a CERRADA amb el nom de m.

3.2. Expandir m:

3.2.1. Generar el conjunt M de tots els seus successors que no siguin avantpassats, i

introduir‐los com a successors de m a G.

3.2.2. Si algun dels generats és meta, tornar la solució amb el recorregut

corresponent. Sinó,

3.2.3. Posar un punter des de m (que ens marcarà la profunditat) fins els nodes

generats i moure’ls a ABIERTA, doncs seran expandits (o no) posteriorment

3.2.4. Per cada node repetit, decidir si es canvia el punter, és a dir, si es s’utilitza un o

l’altre segons els criteris explicats més amunt.

3.3. Reordenar la llista ABIERTA en cas d’algun canvi, aplicant algun criteri heurístic.

33

IA: Intel∙ligència Artificial IV. RECERCA HEURÍSTICA

IV. RECERCA Heurística

1. Característiques Un dels principals problemes de la recerca sense informació del domini és la quantitat d’espai

que necessita. Per exemple, en un problema d’un tauler amb 8 fitxes i 1 espai i on volem a

arribar a una determinada combinació d’aquestes (movent‐les), existirien, ni més ni menys que

362880 combinacions disponibles (9!=9x8x7x6x5x4x3x2x1, ja que podem moure 9 caselles, i

d’aquestes 9 després en podrem moure 81, i després 7.. es llegeix 9 factorial i respon a 362880

opcions). I naturalment, això resulta pràcticament inviable per a la memòria del computador si

volem obtenir certs nivells d’eficiència temporal i espacial.

Per aquest motiu, el que pretén la recerca heurística és facilitar el desplaçament (o l’exploració)

per l’arbre (aplicat al mateix tipus de problemes que el mètode del capítol III), seleccionant a

través d’uns criteris determinats algun camí o node preferent. Per això, es diu que aquesta, a

diferència de l’anterior, si que posseeix coneixement sobre el domini del problema, ja que

aquest coneixement serà el que ens guiarà a preferir un camí o l’altre.

Si bé que amb aquest sistema no cal desenvolupar camins “inútils” i estalviem espai, haurem de

sacrificar eficiència per efectivitat, ja que la cerca heurística no permet sempre trobar la solució

més òptima, si més no alguna que s’hi aproximi2 3.

A més a més, igual que en la recerca sense informació del domini, existeixen diferents

estratègies d’exploració, és a dir, maneres, ordres i procediments de recórrer un graf.

2. Elements En primer lloc, cal recordar que en aquest tipus de problemes tenim els mateixos elements que

en el primer mètode. A més a més, però, per a seleccionar els nodes preferents o aplicar

qualsevol procés d’elecció per tal de fer menys costós el camí, existeixen diferents elements:

− Regles de control heurístic: són les que operen per tal de decidir entre un camí o l’altre.

1 Cada pas és una opció menys que seria l’opció des de on venim, ja que si la repetíssim, tornaríem a l’estat anterior i l’arbre seria infinit 2 Això és degut a que els mètodes d’avaluació heurística utilitzen criteris per seleccionar un camí o l’altre aproximats, i es poden equivocar 3 Tot i això, hi ha mètodes que si que permeten trobar la solució més òptima

34


− Funcions d’avaluació heurística: són les que assignen a cada node un valor de la funció

que estimarà la proximitat o llunyania a la meta, per tal de determinar un camí o l’altre.

S’expressa en ƒ(x)= Y, on x és la variable dependent corresponent al node en qüestió i Y

és el valor de la funció en aquell node. Per tant, a cada estat li atorgarà un valor per tal

de tenir una idea aproximada sobre la proximitat d’aquest a la meta, i així decidir i elegir

després si accedir‐hi per aquesta via.

Tot i això, és necessari anomenar que depenent de la situació s’utilitzarà un o l’altra. Aquesta

elecció dependrà de la estratègia d’exploració utilitzada o del problema.

En aquest capítol s’exposen únicament mètodes que utilitzen funcions heurístiques per a

determinar un camí o l’altre.

3. Mètode Irrevocable: mètode del gradient 3.1 Característiques

Aquest és el primer mètode de recerca heurística. Utilitza

una funció d’avaluació la qual assigna a cada estat un

valor amb relació a la meta, a través del que la

computadora elegirà en cada pas quin node successor

(camí) elegir. Aquest valor tant pot ser de màxim (e.

inicial) a mínim (estat meta), com viceversa. Per tant,

aquesta estratègia anirà recorrent els nodes,

seleccionant per l’expansió aquells el valor de la funció heurística dels quals sigui més elevada (o

menys, depenent del sistema de referència), tal com es mostra en la imatge superior. I

precisament es diu irrevocable perquè un cop elegit un camí, ja no hi ha volta enrere.

Per tal de que aquest algoritme pugui ser aplicat, s’ha de complir que per cada node n existeixi

un successor n’ que tingui un valor menor (o major) assignat a la funció heurística, és a dir ƒ(n)≥

ƒ(n’) o ƒ(n)≤ ƒ(n’).

35


3.2 Procediment L’algoritme seria el següent:

3.3 Avantatges i inconvenients ‒ Avantatges: la principal n’és la senzillesa. Només és necessari emmagatzemar el estat

elegit, sense necessitat de recordar el camí.

‒ Inconvenients: la dependència de ƒ. Únicament ens guiem pel recorregut a través del

valor de ƒ. Per això, si aquest és poc precís i comet un error, el mètode es torna ineficaç.

4. Estratègies d’exploració d’alternatives Són les més utilitzades, ja que no són irrevocables, fet que permet tornar enrere i considerar

altres “alternatives” d’exploració.

4.1 Cerca de “primer el millor”

4.1.1 Característiques Consisteix en recórrer el graf elegint entre els possibles successors el que tingui un valor més

elevat de ƒ, el qual marcarà la distància a la meta (per tant ƒ(e.i.)=màx ; ƒ(e.f.)=mín o 0). Tot i

això, si en algun cas ens trobem que el camí elegit té més distància a la meta que un node de

1. Denominar m a l’estat inicial del problema plantejat i crear una variable elegit.

2. Assignar m com a valor de la variable.

3. Fins que es trobi “meta” o es torni error ,realitzar les següents accions:

3.1. Expandir m amb tots els seus successors. Per a cada sucessor n

3.1.1. Si el nou estat és meta, tornar la solució.

3.1.2. Si el nou estat conté un valor de ƒ(n) millor que ƒ(m), assignar el valor de la

variable elegit a n, i canviar‐lo per m.

3.1.3. Si no es compleix cap de les condicions anteriors en cap successor, tornar error.

36


ABIERTA no expandit, es pot reconsiderar el camí i tornar

enrere per poder realitzar una nova elecció. Per exemple,

en la figura observem que un cop elegit el camí A‐C,

perquè estima una distància menor que A‐B, A‐B és

menor que A‐C‐F o que A‐C‐G, per tant tornaríem enrere

per agafar A‐B.

Aquest mètode guarda estretes similituds amb el procediment general de la cerca en grafs,

doncs la possibilitat de reconsiderar un camí elegit i tornar enrere és possible gràcies a la

reordenació de la llista ABIERTA o CERRADA en cada cas. Com ja sabem, en ABIERTA guardarem

els nodes que podríem expandir, i en CERRADA els nodes seleccionats per l’expansió. Per tant, si

en algun moment veiem que el valor de ƒ d’un altre node d’ABIERTA anterior no expandit és

més prometedor que el camí elegit, podem reordenar les llistes, afegir‐lo a CERRADA i continuar

l’exploració des d’aquest.

4.1.2 Procediment

1. Crear una llista de nodes denominada ABIERTA, i inicialitzar‐la amb el node que conté la

descripció del problema (estat inicial)

2. Crear la llista CERRADA que inicialment estarà buida

3. Fins que es trobi “meta” o es torni error, realitzar els següents passos:

3.1. Si ABIERTA està buida acabar amb error, sinó,

3.2. Eliminar el primer node d’ABIERTA, denominar‐lo m i passar‐lo a CERRADA

3.3. Expandir m creant punters a tots els seus successors

3.4. Si algun successor és meta, tornar la solució i el camí

3.5. Per a cada successor n de m calcular ƒ(n) tot tenint en compte:

3.5.1. Si n és nou (podria ja ser‐hi i que haguéssim reconsiderat un camí) calcular ƒ(n) i

introduir‐lo a ABIERTA

37


4.1.3 Avantatges i inconvenients ‒ Avantatges: sabem segur que tard o d’hora es trobarà la solució òptima, a diferència del

mètode irrevocable, doncs pot ser que aquest es deixi guiar per uns valors prometedors

que simplement siguin mínims (o màxims) locals, no absoluts.

‒ Inconvenients: la funció no considera el camí recorregut, i podria ser que amb el joc de

tornar enrere per agafar un altre camí, estiguéssim cometent un error i haguéssim de

reconsiderar el camí seleccionat més tard. Això suposaria més temps i la possibilitat

d’agafar un camí que no sigui el més curt, sinó més aviat fruit de recorreguts més

extensos degut a tantes “reconsideracions” per culpa de nodes que enganyen.

4.2 Cerca en feix (beam search) Correspon a una variant del mètode “primer el millor”. El que pretén és accelerar el procés

d’exploració reduint a cada pas de l’algoritme el nombre de nodes generats de ABIERTA que

podrien ser expandits posteriorment, seleccionant‐los segons dos criteris diferents possibles:

‒ Permetent que només un nombre fix de nodes, els més prometedors, siguin expandits

més endavant.

‒ Establint el valor llindar (ƒo) de la funció d’avaluació heurística per sota de la qual (o per

sobre, depenent del sistema de referència o criteri) cap node generat podrà ser

expandit.

3.5.2. En cas contrari:

3.5.2.1. Si ƒ(n) és major que ƒ(m), d

3.5.2.2. Sinó, canviar n i assignar‐li la variable m. Si aquest ja estava a

CERRADA actualitzar el cost dels descendents, ja que podrien veure

reduït el seu valor.

38


4.3 Algoritme A* 4.3.1 Característiques Semblant a l’estratègia ja esmentada de “primer el millor” (n’és un derivat perfeccionat), però

en aquesta la funció d’avaluació heurística no només té en compte la distància estimada a la

meta, sinó també la distància recorreguda. Així podem salvar els petits desavantatges que

sorgeixen en primer mètode. Per tant, la funció d’avaluació heurística que guiarà el procediment

és la següent:

ƒ(n)= g(n)+h(n)

On g(n) és la funció que avalua el cost del camí més curt des de l’ inici fins la meta, i h(n) és la

que n’estima el cost fins la meta. El que això ens aportarà és la selecció d’aquell node el camí

des de l’estat inicial fins la meta del qual sigui el millor passant per aquell node. D’aquesta

manera, evitarem haver de reconsiderar decisions per haver‐nos guiat per un camí més llarg

(fruit dels inconvenients ja explicats en el mètode primitiu), ja que es té en compte que la

distància estimada a la meta compensi amb la distància recorreguda (sempre que la distància

estimada estigui ben calculada).

Per tant, no és estrany que aquest mètode sigui millor que del que deriva, i consta de diverses

propietats que el fan òptim i el més utilitzat, com per exemple:

‒ Aquest mètode sempre acaba trobant el camí de la solució, ja que com hem comentat,

compensa també amb el camí recorregut, i no admet anar‐nos‐en pels “descosits” amb

camins inútils. Per això es diu que es una estratègia completa

‒ A part de trobar el camí de la solució, troba també el més òptim quan la funció és

monòtona. Això significa que h(n) (distància estimada a la meta) és menor que h*(n)

(distància real a la meta). És a dir, quan el camí estimat no sigui més gran que el camí

real. També es diu que la funció es admissible.

‒ Entre tots els mètodes heurístics existents que utilitzen la funció h(n) i que troben la

solució òptima, aquest és que expandeix el menor nombre de nodes.

39


4.3.2 Procediment

1. Crear una llista de nodes anomenats ABIERTA i assignar‐li el node arrel, que representa el estat

inicial del problema plantejat. Anomenar r a aquest element i assignar‐li g(r)=0

2. Crear una llista de nodes CERRADA que inicialment estigui buida.

3. Fins que es trobi la meta o es torni error, realitzar les següents accions:

3.1. Si ABIERTA està buida, acabar amb error, en cas contrari, continuar

3.2. Eliminar el node de ABIERTA que tingui un valor mínim de ƒ, anomenar‐lo m i introduir‐lo a

CERRADA

3.3. Si m és meta, abandonar el procés iteratiu de 3 i tornar el camí de la solució que s’obté

recorrent els punters dels seus avantpassats (creats a 3.5)

3.4. En cas contrari, expandir m generant tots els seus successors.

3.5. Per cada successor n’ :

3.5.1. Crear un punter n’‐m

3.5.2. Calcular g n , que s’obté sumant g(m) i el cost de passar de m a n’

3.5.3. Si n’ està a ABIERTA (és a dir, si ja l’havíem trobat en un altre cas i no l’havíem

expandit), anomenar n al node trobat en aquesta llista i afegir als successor de m i

realitzar:

3.5.3.1. Si g(n’) és més petit que g(n),és a dir, si hi ha menys distància des de l’estat

inicial fins el node nou que l’antic, canviar el punter de n per n’, i calcular ƒ(n’)

3.5.4. Si n’ no està a ABIERTA, comprovar si està a CERRADA, anomenar n al node ja existent

de la llista i realitzar els següents passos:

3.5.4.1. Realitzar la mateixa comprovació que en l’apartat 3.5.3.1 ; i en cas negatiu,

abandonar el pas 3.5.4 ; en cas afirmatiu, actualitzar els punters i el valor de

g i ƒ no tan sols per el node en qüestió, sinó també dels seus successors, per

el mètode de recorregut en profunditat, fins que s’arribi a un node sense

successors o a un g(n’)=g(n), que en aquest cas s’hauria produït un cicle i

hauríem d’acabar igualment

3.5.5. Si n’ no està ni a ABIERTA ni a CERRADA, calcular ƒ(n’) (h+g), introduir‐lo a

ABIERTA i fer‐lo constar com a successor de m.

40


4.3.3 Avantatges i inconvenients ‒ Avantatges: a partir de les propietats descrites anteriorment, podem afirmar que és un

mètode complet i admissible.

‒ Desavantatges: degut a la propietat d’admissibilitat que presenta, en molts casos es

gasten esforços innecessaris per la tria entre dos camins pràcticament iguals, fet que ens

porta a considerar una solució molt més realista la qual consisteix en acotar l’elecció a

un marge d’error relatiu determinat.

5. Cerca amb adversaris 5.1 Descripció Fora dels problemes típics vistos fins ara (gràfics d’exploració senzills amb un estat inicial, i un

final), la realitat és molt més àmplia. Per exemple, una situació molt corrent i que s’ha explotat

ja des dels inicis seria una partida entre dos adversaris; com per exemple, un joc d’escacs.

Aquesta situació dista de les anteriors en vàries coses: s’ha de considerar dos “ments” oposades,

i la realitat és molt més complexa, existint gran varietat d’alternatives i variant aquestes a cada

pas del contrincant. A més a més, no es pretén donar un camí de la solució, , ja que aquest no

tan sols depèn de nosaltres, sinó de l’altre adversari, i per tant són infinits; sinó que també es vol

donar el node fill seleccionat en cada pas. Ens seria impossible fer ús d’algun dels mètodes

anteriors, i menys d’algun sense informació del domini, ja sigui per la incapacitat d’adaptar‐se a

la situació plantejada o per la complexitat que aquesta presenta, doncs possiblement s’acabés

sempre amb una explosió combinatòria.

Per això, ja des d’un bon principi es va desenvolupar un mètode òptim per a aquest tipus de

situacions comentades. El primer tret distintiu d’aquest és la subdivisió en una doble jugada,

utilitzant tanmateix un sol graf. El segon és l’establiment d’un límit d’exploració mitjançant una

funció heurística, que ens permetrà frenar aquesta expansió enorme estimant on es podria

acabar la partida. Per això, es desenvolupa un graf on cada nivell suposa el pas d’un jugador, el

41


qual elegirà el moviment que més li benefici (els hi doni avantatge respecte a la meta), tot

analitzant la jugada i fent ús duna funció d’avaluació que determini la possible distància fins a al

meta de cada jugada.

Si bé aquest apartat podria exposar‐se en un altre capítol, s’inclou aquí pel fet d’utilitzar

funcions heurístiques avaluadores.

Tot i haver establit un mètode per a aquest tipus de problemes amb una sèrie de criteris

generals, existeixen una sèrie d’estratègies (com de costum) per recórrer el graf (sempre

d’acord amb les característiques exposades de la cerca amb adversaris)

5.2 Dues possibles etiquetes Com ja hem comentat, en la recerca amb adversaris tenim un graf i dos adversaris. Per això, i

com que a cada node se li assigna un valor ƒ(n), hem de saber determinar si aquest valor ens és

positiu o negatiu, ja que per un mateix node amb un sol valor han de sorgir dues

interpretacions, corresponents a els dos jugadors en qüestió. Per tant, independentment de la

estratègia utilitzada, podem etiquetar (interpretar) als valors de ƒ(n) de dues maneres:

5.2.1 Etiquetes segons MÀX En aquest mètode es consideren totes les jugades respecte al jugador anomenat MÀX (l’altre el

denominarem MIN). Per tant, s’etiqueten totes les jugades en relació amb el benefici que

aportaran al jugador MÀX, independentment del jugador al que corresponguin. Per això, des

d’un node MÀX s’elegirà la jugada que contingui més valor associat de ƒ , mentre que l’elecció

del node MIN correspondrà al menor valor associat.

5.2.2 Etiquetes segons MMValor En aquest altre mètode es parteix de que si una jugada és prometedora per un, significarà ser

perjudicial en la mateixa proporció per l’altre. Per tant, s’estableixen les jugades en funció del

signe de ƒ . És a dir, determinarem que si per un jugador es considera ƒ d’una jugada com a

benefactora per a l’altre es considerarà – ƒ (i per tant s’haurà de canviar el signe segons el

jugador), perjudicial, i cada un actuarà en conseqüència, associant‐hi el mateix valor a favor o en

contra.

42


5.3 Mètode MINIMAX

5.3.1 Característiques Aquest mètode simplement consisteix en determinar la jugada (o node elegit) en funció de ƒ.

Clar que la interpretació d’aquesta ƒ es basarà en base a un dels dos criteris d’etiqueta exposats.

Per tant, elegirem el node el valor de ƒ del qual sigui el més prometedor (no el més alt, ja que

pot variar segons el criteri utilitzat)

5.3.2 Procediment El algoritme per a cada nivell del graf (jugada) serà el següent:

5.3.3 Avantatges i inconvenients ‒ Avantatges: es tracta d’un mètode general i senzill.

‒ Inconvenients: es considera poc eficient, ja que és massa exhaustiu.

1. Si m no té successors o es considera arribat a el límit de profunditat, retornar el valor de la

funció en relació a l’etiqueta establerta. Sinó,

2. Generar els successors de m.

2.1. Inicialitzar la variable millor amb el valor mínim de ƒ que aquesta pugui tenir.

2.2. Per a cada successor n de m:

2.2.1. M(n)=MINIMAX(n, profunditat+1, C(jugador)); sent C(jugador) una funció que

canvia de jugador.

2.2.2. millor= max[‐M(n), millor]

3. Una vegada analitzats recursivament tots els successors d'un determinat nivell, es retorna

el que posseeixi un valor millor.

43

IA: Intel∙ligència Artificial V. LÒGICA

v. LÒGICA

1. Característiques En els capítols anteriors parlàvem sobre situacions en un món “idealitzat”, ja que els problemes

que ens englobaven eren senzills, i simplement preteníem recórrer una sèrie d’estats per tal

d’arribar a uns situació coneguda, sense cap mena de “destorb” extern, és a dir, real.

Però com ja sabem, la realitat problemàtica que requereix solució s’estén molt més enllà, i

aquests només són un petit conjunt de tot els casos que ens envolten. En la majoria de

problemes o decisions del dia a dia no ens trobem davant d’una situació que requereixi arribar a

un estat concret, ja que això més aviat suposaria casos molt poc usuals. En canvi, podem trobar

nombroses ocasions en que ens cal prendre una decisió i interpretar. Per tant, ja fora d’un

primer bloc de IA on “no ens cal” pràcticament analitzar la situació (doncs per exemple, en el

problema de les gerres d’aigua podríem únicament dedicar‐nos a “provar” el que fer) i

simplement pretenem a arribar a un lloc, comencem un segon bloc, la base del qual es troba en

la lògica. Aquest bloc pretén acostar‐nos a situacions molt més comunes, la característica dels

quals és que requereixen modelar el coneixement. Com ja havíem dit, el coneixement és la part

més complexa de la intel∙ligència, i si bé els primers mètodes vistos no en requereixen per ser

efectuats, veurem que tots els que sorgeixen a partir dels anys 70 (i que exposarem en els

pròxims capítols) sí que n’exigeixen.

La lògica, ara sí, és la ciència que s’encarrega de l’estudi del raonament que es considera vàlid.

Tot i que va ser considerada per primer cop per el gran Aristòtil, ara els experts l’han adoptat

com a mètode per la IA. El que es pretén utilitzant la lògica és per tant solucionar un tipus de

problemes en els quals es requereixi extreure conclusions mitjançant el raonament. Així doncs,

la utilitzarem per aquells problemes on a partir d’una sèrie de coneixement existent vulguem

obtenir‐ne de nou pel nostre compte, és a dir, vulguem extreure les pròpies conclusions. Diem

que és la base perquè a partir d’aquí explotarem les conclusions obtingudes integrant‐les o

ajudant‐se en els altres mètodes.

44


Primerament analitzarem la lògica com a ciència tot atenent als elements i a una explicació

prèvia per establir‐ne les bases. Posteriorment veurem els mètodes de raonament que utilitza

per extreure conclusions perquè puguin ser aplicats a la IA1.

2. La lògica com a ciència 2.1 Definició i objecte Comunament afirmem que una cosa és lògica quan s’hi pot accedir a través del sentit comú. Si

més no, tot i que la definició hi està relacionada, també s’entén “lògica” com una disciplina o

ciència de la filosofia que estudia els raonaments; és a dir, la validesa i la naturalesa d’aquests. Si

més no, no atén al contingut del que raonem, sinó simplement com ho raonem. Per exemple:

Tots els habitants de mart beuen te.

Totes les balenes viuen a mart.

‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐

Totes les balenes beuen te.

El primer que se’ns passa pel cap és que tot això és poc “lògic”, tanmateix, està ben raonat. Per

tant, afirmarem que potser no és vertader, i que el significat de les oracions és incoherent, però

el raonament és vàlid, i això és el que importa.

Malgrat tot, el primer que pensa un alumne de batxillerat quan s’obre aquest tema és: perquè

serveix? Doncs bé, com ja havíem comentat en el capítol I, el primer que cal fer per imitar la

ment humana és estudiar com funciona. I si una part molt important d’aquesta és la capacitat de

raonar, caldrà conèixer‐la per poder‐la programar després.

2.2 Tipus de lògica Si bé la lògica és una disciplina amb unes bases comunes, existeixen moltes subdivisions, molts

tipus de lògica. I es que és clar, no tots els raonaments poden ser efectuats de la mateixa

manera, doncs ja de per sí aquests solen tenir naturaleses molt diferents. Per tant, vegem un

esquema amb els diferents tipus:

1 És molt important tindre en compte que no tractarem de com programar un arxiu que extregui conclusions, sinó només de les bases teòriques que això requereix.

45

IAA: Intel∙ligèn

lògique

de la lò

2.3 ECom ja

terme

són el

Si A és

treuen

−

−

Lògic

ncia Artificial

es modals, q

ògica clàssica

Elemena hem dit, l’o

mitjançant l

pilar bàsic de

s B i B és C,

bones note

Premisses:

les dades d

Conclusió:

expressa u

premisses

ca

Lòg

Lògiq

Lò

ue responen

a.

nts de laobjecte de la

les regles d’

e la lògica. P

aleshores A

s, per tant e

: conjunt d’e

de les quals p

enunciat

una nova inf

i les regles d

giques clàssiq

ques no clàss

ògiques moda

n a un altre t

a lògicaa lògica és el

inferència, q

er exemple:

és C (regla

n Joan treu b

enunciats qu

partim.

final obt

formació a t

’inferència.

ques

L

iques

L

als

tipus de lògic

a realitzar rao

que ens perm

d’inferència

bones notes.

ue expressen

tingut que

través de les

Lògica d'enu

Lògica de pr

Lògica de c

ògica de seg

Lògica dif

Lògica relle

Lògica quà

Lògica no mo

Lògica mo

Lògica deò

Lògica tem

Lògica epist

ca que no re

onaments. A

meten obten

) (Aplicaci

. Per tant, en

n

e

s

unciats

edicats

lasses

gon ordre

fusa

evant

àntica

onòtona

odal

òntica

mporal

tèmica

La lògica cl

utilitzada,

per respon

que veurem

Dintre d’a

(entre les m

lògica d’

estudia la

raonament

la veritat de

i la lògica

analitza l’e

dels anuncia

Per altra

lògica no

specta els tr

Aquests raon

nir conclusio

ió) En Joan é

n tot raonam

V

làssica és la

i es caract

dre a 3 pri

m més enda

aquesta tr

més importan

enunciats,

a validesa

tenint en co

els seus enu

de predicat

structura in

ats.

banda, teni

clàssica

res principis

aments es d

ons, i que pe

és llest, els l

ment tindrem

V. LÒGICA

a més

teritza

incipis

avant.

robem

nts) la

que

del

ompte

nciats

s que

nterna

im la

i les

bàsics

duen a

er tant

lestos

m:

46


Ambdues per això, estan compostos d’enunciats, que són les afirmacions amb les que es

constitueix tot raonament. Aquests poden ser:

− Atòmics: aquells que no es poden descompondre en altres enunciats. Per exemple : “el

gos borda”.

− Moleculars o complexos: aquells que es poden descompondre en enunciats simples “el

gos borda i el gat miola”, o en altres enunciats moleculars, om per exemple: “si el gos

d’en Joan borda i la gata de la Maria no s’espanta aleshores o és sorda o està

acostumada”.

Tot i els elements, la lògica utilitza un llenguatge propi per a treballar i facilitar‐ne la

manipulació. Els elements propis d’aquest llenguatge serien els següents:

− Vocabulari: grafies a partir de les quals s’expressa. En una equivalència al llenguatge

natural correspondria a les paraules. Distingim:

o Lletres (m,p,x,a...): representen enunciats o noms. Per exemple, “si sortissis de

tant en quant, no estaries tant amargat”, es traduiria “si p, aleshores q”. Cal

recordar que l’important és la validesa del raonament, per això el contingut és

reduït a lletres.

o Signes (∀,∧,→,...): indiquen la relació entre els enunciats i termes. Per exemple,

l’exemple anterior podria ser expressat de la següent manera: “p→q”. cal

destacar:

∀: es llegeix “ per tot “x” ”. Per exemple: “Tots els animals (A) mengen

per subsistir (M)” S’expressaria “∀x, si x=A aleshores x=M”

∃: es llegeix “ existeix algun “x” ”. Per exemple “Algun animal (A) menja

per plaer (M)” s’expressaria “∃(x), si x=A aleshores x=M”

∈: indica “pertànyer a”. Per exemple: “Tots els animals (A) són éssers

vius (E)” s’expressaria “A∈E”

∧: es llegeix “i”. Per exemple: “Els animals dormen (p) i les persones

parlen (q)” s’expressaria “p ∧ q”

47


∨: es llegeix “o”. Per exemple: “Els animals dormen (p) o les persones

parlen (q)” s’expressaria “p ∨ q”

→: es llegeix “si..aleshores”. Per exemple: “Si els animals dormen (p)

aleshores les persones parlen (q)” s’expressaria “q→p”

↔: es llegeix “si i només si..aleshores” o “únicament si... aleshores”. Per

exemple: “Únicament si els animals dormen (p) aleshores les persones

parlen (q)” s’expressaria “q↔p”

¬: es llegeix “no”. Per exemple: “Els animals dormen (p) i les persones

no parlen (les persones parlen=q)” s’expressaria “p ∧ ¬q”

− Regles de formació: són aquelles que estableixen quines combinacions o expressions

són correctes i quines no. Correspondrien a la gramàtica d’una llengua. Per exemple,

mentre que [ (p→q ∧ r→p)∨ q ] és correcte, [ →pq ∧ r→p∨q] no ho és, de la mateixa

manera que no ho seria “gos el dorm”.

− Regles de transformació o regles d’inferència: són les més importants, les que

estudiarem i les que ens serveixen per dur a terme el raonament. Ens diuen com operar

amb els enunciats, com en el primer exemple d’aquest apartat. Tot i això, cal dir que

cada tipus de lògica posseeix unes regles de transformació concretes.

2.4 Principis Tot i que parlem de principis generals de la lògica, cal dir que només són específics de la lògica

clàssica, i que per exemple, la lògica difusa no compleix el tercer principi. Malgrat tot, els

exposem aquí entre les bases generals perquè són importants, i si bé no totes les lògiques

segueixen els tres, n’acostumen a seguir algun. Tanmateix, és necessari remarcar que aquestes

lògiques sorgeixen totes de la clàssica. Els principis de la lògica clàssica per tant, són els

següents:

− Principi d’identitat: tota cosa és idèntica a ella mateixa. A és A.

48


− Principi de no‐contradicció: cap cosa pot ser i no ser alguna cosa a la vegada en el

mateix sentit i al mateix temps. Res pot ser A i no A a la vegada, en el mateix sentit i al

mateix temps.

− Principi del tercer exclòs o de bivalència: Tot enunciat és o vertader o fals. Tot és o no

és A.

Aquests principis tenen una característica molt essencial: pels raonaments en els quals es poden

aplicar, resulta impossible no complir‐los, són inherents a la naturalesa del mateix raonament.

2.5 Propietats Totes les característiques dels sistemes formals lògics que hem estat veient fan que aquests

tinguin unes propietats ben definides, independentment del tipus de lògica utilitzat, i que els hi

atribueixen característiques positives. Són les següents:

− Consistència: no hi ha contradicció dintre del sistema formal. És a dir, totes les lleis són

vàlides i naturals, per tant, no és possible obtindre un raonament no vàlid.

− Completesa: totes les fórmules són deduïbles a partir de les regles de transformació. Per

això el sistema és complet, doncs conté totes les fórmules o la possibilitat de inferir‐les.

− Decidibilitat: El sistema té un procediment mecànic i accessible que permet decidir si

una fórmula o raonament és correcte o no.

Un cop vistes les característiques bàsiques de la lògica i el seu sistema, començarem a veure el

funcionament d’aquesta per aplicar‐la. En primer lloc veurem el funcionament de la lògica

d’enunciats o lògica de proposicions.

3. Lògica d’enunciats 3.1 Característiques Aquest és el tipus més elemental i primitiu. Forma part de la lògica clàssica, la primera en ser

estudiada, i respon a les qüestions més simples i més senzilles d’analitzar. Per tant, la lògica

d’enunciats (o de proposicions) ens servirà per respondre als raonaments menys complicats.

49


Aquests raonaments tenen la característica d’estar formats per enunciats (atòmics o

moleculars), i s’estableixen a partir de les diferents relacions existents. És a dir, el que pretén la

lògica de proposicions és extreure conclusions analitzant les relacions entre els diferents

enunciats, no pas atenent al que ens diuen aquests. Per exemple, la proposició molecular “Si

vens al cine et compraré crispetes” seria pròpia de l’estudi d’aquest tipus de lògica, dons

s’estableix una relació “venir al cine → comprar crispetes”, i podríem concloure, per exemple, a

través d’una altra relació (“qui compra crispetes als altres és generós”), que jo sóc generós.

Tanmateix, no s’atén al contingut dels enunciats, dons no podem estudiar si són poques o

moltes les crispetes, ni si és necessari que et compri crispetes, etc.. ja que això ho tractarà un

altre tipus de lògica.

Per altra banda, en la lògica d’enunciats trobem dues aplicacions bàsiques. La primera, exclusiva

d’aquest tipus de lògica, s’escapa una mica del “estàndard” premissa‐conclusió, i pretén

determinar si les proposicions són veritat (per exemple, raonar si “Els nois llestos estudien i els

nois irresponsables no estudien” és veritat). El segon (lleis d’inferència) pretén extreure nous

enunciats (conclusions) a partir dels anteriors, com en qualsevol tipus de lògica.

3.2 Veritat de proposicions Com hem dit anteriorment, distingim entre proposicions atòmiques i proposicions moleculars.

Per saber si una proposició atòmica és vertadera, únicament cal creure‐s’ho. Precisament per

això havíem comentat que la lògica no atén a la naturalesa de les proposicions, ja que ni

nosaltres podrem determinar des d’un punt de vista lògic si una proposició és certa ni, en el

fons, tampoc ens interessa. Únicament cal atendre a si obtenim p com a cert o com a fals, i serà

a partir d’on operarem. Per tant, si ens diuen “El Pere va al cinema i la Marta el persegueix”,

només ens interessarà si p (en Pere...) i q (la marta..) són certs, ni el perquè ni el com, i a més a

més, tampoc ho podrem determinar, sinó que ens vindrà ja determinat.

Pel que fa a les proposicions moleculars, sabem que s’uneixen per signes (específics del

llenguatge lògic) i que aquests determinen una relació concreta entre els diferents enunciats

atòmic del conjunt. Per tant, la veracitat de la proposició molecular dependrà dels signes

integrants i de la veracitat de les proposicions atòmiques o primitives (precissament per això ho

aborda quest tipus de lògica). Vegem les diferents normes per a determinar la veracitat de les

50


proposicions moleculars que s’estableixen entre dues proposicions simples per a cada tipus de

signe (els més simples), tenint en compte que si el nombre d’enunciats excedeix de dos,

actuarem similar a com ho fem seguint el conveni matemàtic de signes “ () ; [] ; + ; − ; x ; etc..”

p q Conjunt Explicació2

p ∧ q

V V V Si el Joan juga i la Maria dorm, serà veritat que el Joan juga i la

Maria dorm

V F F Si el Joan juga però la Maria no dorm, serà mentida que el Joan

juga i la Maria dorm

F V F Si el Joan no juga però la Maria dorm, serà mentida que el Joan

juga i la Maria dorm

F F F Si ni el Joan juga ni la Maria dorm, serà mentida que el Joan juga i

la Maria dorm

p ∨ q

V V V Si el Joan juga i la Maria dorm, serà veritat que el Joan juga o la

Maria dorm

V F V Si el Joan juga però la Maria no dorm, serà veritat que el Joan juga

o la Maria dorm

F V V Si el Joan no juga però la Maria dorm, serà veritat que el Joan juga

o la Maria dorm

F F F Si ni el Joan juga ni la Maria dorm, serà mentida que el Joan juga o

la Maria dorm

p → q

V V V Si el Joan juga i la Maria dorm, serà veritat que si el Joan juga

aleshores la Maria dorm

V F F Si el Joan juga però la Maria no dorm, serà mentida que si el Joan

juga aleshores la Maria dorm

F V V Si el Joan no juga però la Maria dorm, serà veritat que si el Joan

juga aleshores la Maria dorm3

F F V Si ni el Joan juga ni la Maria dorm, serà veritat que si el Joan juga

aleshores la Maria dorm

p ↔ q

V V V Si el Joan juga i la Maria dorm, serà veritat que únicament si el Joan

juga aleshores la Maria dorm

V F F Si el Joan juga però la Maria no dorm, serà mentida que únicament

si el Joan juga aleshores la Maria dorm

F V F Si el Joan no juga però la Maria dorm, serà mentida que únicament

si el Joan juga aleshores la Maria dorm

F F V Si ni el Joan juga ni la Maria dorm, serà veritat que únicament si el

Joan juga aleshores la Maria dorm

Cal comentar que la negació únicament inverteix l’ordre de veritat d’una variable o conjunt de

variables. Així per exemple, “p ∧¬ q” serà veritat únicament quan p=V i q=F, doncs s’invertirà q

obtenint ¬q=V i la proposició molecular quedarà vertadera.

3.3 Lleis d’inferència Les lleis de raonament4 (o per saber si aquests són vàlids) serien les següents:

2 Sent p “El Joan juga” i q “La Maria dorm” 3 El condicional → expressa condició suficient, no necessària. Així per exemple, no és necessari que el Joan jugui perquè la amaria dormi, només és suficient 4 Sempre que tots els enunciats siguin vertaders

51


Nom i abreviació Esquema Exemple4

Doble negació (DN) ¬¬A A

A . ¬¬A

Si tenim que “És fals que el Joan no hi és” podem concloure que “El Joan hi és”

Introducció de la conjunció (IC)

A B . A ∧ B

A B . B ∧ A

Si tenim d’una banda avui plou i de l’altra demà sortirà el sol, podem concloure que avui plou i dema

sortirà el sol

Eliminació de la conjunció (EC)

A ∧ B . B

A ∧ B . A

Si tenim que “En Marius va venir a la festa i es va menjar tots els gelats”, podem concloure tant que

“En Màrius va venir a la festa” com que “En Màrius es va menjar els gelats

Introducció de la disjunció (ID)

A . A ∨ B

Si tenim que “Copenhaguen és la capital de Dinamarca”, podem afirmar que “Copenhaguen és la

capital de Dinamarca o qualsevol altra cosa (exemple: els gats saben parlar)”

Sil∙logisme disjuntiu (SD)

A ∨ B ¬A . B

Si tenim que “Has amagat les claus o les has perdut” i que “No les has perdut”, podem concloure que les

has amagat

Regla del bicondicional (RB)

A ↔ B . A →B

A ↔ B . B → A

Si tenim que “Anem al cinema únicament si em compres crispetes” podem afirmar tant que “Si anem al cinema em compraràs crispetes” com que “Si em

compres crispetes, anirem al cinema”

Modus ponens (MP)

A → B A . B

Si tenim d’una banda que “Si les vaques estan boges s’acosta la fi del món” i de l’altra que “les vaques estan boges”, podem concloure que “S’acosta la fi

del món”

Modus tollens (MT) A → B ¬B . ¬A

Si tenim d’una banda que “Si els nens vénen de Paris els nens parlen francès” i de l’altra que “Els nens no parlen francès”, podem concloure que “Els nens no

vénen de París”

Regla de transitivitat (RT)

A → B B → C . A → C

Si tenim d’una banda que “Si corro em canso” i de l’altre que “Si em canso tinc ganes de dormir”,

podem concloure que “Si corro tinc ganes de dormir”

Regla del dilema (RD)

A ∨ B A → C B → D. C ∨ D

Si tenim d’una banda que “Aniré al cinema o em quedaré estudiant” i de l’altra que “Si vaig al cinema

m’ho passaré bé” i que “Si em quedo estudiant aprovaré l’examen”, podem concloure que “M’ho

passaré bé o aprovaré l’examen

Regles de De Morgan

¬(A ∨ B) ¬A ∧ ¬B

¬(A ∨ B) ¬A ∧ ¬B

Si tenim d’una banda que “No és cert que o vaig a la platja o vaig a la muntanya”, podem concloure que “No vaig a la platja i a la muntanya”. Per altra banda, si tenim que “No és cert que vaig a la platja i a la

muntanya”, podem concloure que “No vaig a la platja o no vaig a la muntanya”

4. Lògica de predicats A diferència de la lògica d’enunciats que acabem de veure, al lògica de predicats descriu un

llenguatge quantificador dels elements d’un conjunt. És a dir, si bé fins ara hem vist un tipus de

52


lògica que ens permet estudiar el raonament descrivint les relacions existents dels diferents

anunciats, tot seguit veurem el raonament descrivint les propietats internes d’aquests. Per

exemple, com inferiríem en un enunciat com aquest: “Els arbres són vegetals”? Des de la lògica

d’enunciats no podem fer‐ho. En canvi, podem expressar‐ho així des de la lògica de predicats:

“A∈V” com una equivalència de “A=V”, o el que seria el mateix, Av.

En resum, podem afirmar per tant que el que pretén la lògica de predicats (o lògica de primer

ordre) és efectuar un raonament sobre les descripcions internes dels enunciats, no pas de les

relacions que s’estableixen entre aquests. La descripció interna atén a dos elements: “què

afirmem” i “de qui ho afirmem”

4.1 Elements Per descriure les proposicions des de una vessant “interna”, caldrà introduir nous conceptes o

elements, utilitzats en aquest tipus de lògica, a part dels ja exposats en l’apartat 2. Els elements

essencials que formaran cada predicat (enunciat) sobre el qual treballarem són els següents:

− Variables: expressen un objecte o element determinat (Maria), es simbolitzen per les

primeres lletres del alfabet (a,b,c,..)

− Constants: expressen un objecte en general (“x” Per tot “x”,...), i es simbolitzen

mitjançant els últims caràcters de l’abecedari (x,y,z...)

− Funcions: expressen relació. Aquesta relació pot ser entre les constants [per exemple, el

pare de la maria p(m)], entre qualitat‐constant [per exemple,estimar a la Maria

e(m)], etc.. i es simbolitza per f(x) o qualsevol lletra típica d’una funció matemàtica

(g,h,...)

A part, convé també anomenar diferents elements que estableixen relació entre aquests

conceptes (=,∧,∀,..)

4.2 Lleis d’inferència Existeixen quatre lleis bàsiques de raonament en aquest camp:

− La primera, modus ponens, heretada de la lògica d’enunciats. En aquest cas, per això,

podem definir‐la com:

53


∀x (Px→Tx) Per a tot individu x: si x és un pesat, aleshores és terrible

Pa . L’individu a és un pesat

Ta a és terrible

− La segona, llei de la generalització universal, que es defineix com: sempre que tinguem

“A” , podrem escriure en el següent pas “∀xA” i viceversa (llei especificació universal)

− La tercera, llei de la generalització existencial, que es defineix com: sempre que tinguem

“A”, podrem deduir “ x A” i viceversa (llei especificació existencial)

− La quarta, que diu que a=a sempre és cert, sigui quina sigui la constant “a”

5. Lògica modal 5.1 Característiques i elements La lògica modal suposa una extensió a la lògica de predicats. Si bé aquesta es limitava a un verb

simple “L’home és un ésser viu” , la lògica modal ofereix la possibilitat, precisament, de comptar

amb un verb modal. Per tant, suposarà un afegit per fer front als predicats de caràcter modal.

Definiríem un verb modal com aquell que (en català) forma les anomenades perífrasis modals

(sent el verb conjugat), que poden ser de necessitat, obligació, possibilitat, probabilitat,

consell,etc...

Cal, per això, introduir nous elements per poder expressar correctament aquest tipus de

llenguatge:

− : es llegeix “és necessari”. Per exemple, “És necessari que hi hagin països pobres (P)”,

es podria expressar “ P”

− ◊: es llegeix “és possible”. Per exemple, “ És possible que acomiadin al secretari (A)”, es

podria expressar “◊A”

Per tal d’entendre, tractar i explicar aquests conceptes, la lògica modal recolza els seus estudis

en “móns”. Un món és una descripció completa i consistent de com les coses podrien ser, o de

fet, són. Per tant, un enunciat necessari serà aquell que és cert en tots els móns, inclòs el real.

Per altra banda, definirem un enunciat possible com aquell que és cert en algun possible món,

54


però no té perquè ser el real. Per últim, un enunciat vertader (no exposat en els conceptes

d’aquest punt), és aquell que és cert en el món real.

5.2 Lleis d’inferència Els raonaments (o lleis d’inferència) que utilitza aquest tipus de lògica, útils per a ser programats

després, són els següents:

Representació Exemple

¬◊A ¬A

Si tenim que “No és possible que l’home perfecte”, podem afirmar que “És necessari que no hi hagi l’home perfecte”

¬ A ◊¬A

Si tenim que “No és necessari que hi hagi mal”, podem afirmar que “És possible que no hi hagi mal

A A

Si tenim que “És necessari que si hi ha matèria hi hagi mal”, podem afirmar que “Si hi ha matèria hi haurà mal”

◊A A

Si tenim que “És possible que si hi ha matèria hi hagi mal”, podem afirmar que “Si hi ha matèria hi haurà mal”

6. Lògica difusa 6.1 Introducció La lògica clàssica no ofereix un marc de representació adequat per oracions poc precises i

subjectives. És a dir, no permet fer raonaments amb enunciats on hem de tenir en compte la

incertesa. Per exemple, un predicat com “Les persones altes generalment són bastant pesades”,

no pot ser analitzada des de la lògica clàssica per vàries raons:

1. No podríem desglossar el terme “alt”. Com sabríem quan una persona és alta o no? Per

tant, ens seria impossible fer una dissecció de la propietat “alt” per estudiar‐la.

2. L’adverbi “generalment” quantifica la habitualitat de l’enunciat. És a dir, pot ser cert o

no, i per tant hauríem de treballar amb termes de “possibilitat” i incertesa, els quals no

són abordats per la lògica de primer ordre.

3. Com podem definir si és molt pesat o poc?Una altra incertesa.

55


Per tant, tractarem enunciats on els seus elements naveguen en un mar poc definit en el qual

no podem afirmar quasi res amb seguretat. Per això, la lògica difusa (o lògica fuzzy) conté uns

elements quantificadors per definir aquesta “incertesa”, que ens fan possible treballar amb

aquest tipus d’informació, analitzar‐la i poder raonar‐hi òptimament. Veurem per tant els

elements més importants que ens permetin abordar algunes de les dificultats exposades en els 3

punts.

6.2 Elements: conjunts borrosos i funció de pertinència Per abordar el primer problema, és a dir, per establir quan podem afirmar que algú és alt, s’han

ideat els conjunts borrosos C, que pretenen determinar el nivell d’una qualitat. Aquesta qualitat

(altura), s’expressa en forma de valors que integren el conjunt de l’univers U. Per exemple,

vegem l’univers U possible per a la qualitat altura (expressat en metres):

U={1, 1.10, 1.20, 1.30, 1.40, 1.50, 1.60, 1.70, 1.80, 1.90}

Així doncs, per determinar quan una persona posseeix una qualitat, es fa ús de l’anomenada

funció de pertinència. La funció de pertinència (μ) expressa en tant per u (0’X) en quina mesura

es posseeix una qualitat. Per exemple, a una persona de 2 metres se li podria afirmar una μ de 1.

En conseqüència, podem determinar un conjunt borrós com una “guia” que marca la relació

entre U i μ. Vegem un conjunt borrós de la altura:

C={1|0, 1.10|0.1, 1.20|0.2, 1.30|0.3, 1.40|0.4, 1.50|0.5, 1.60|0.6, 1.70|0.7, 1.80|0.8, 1.90|0.9}

Com a criteri general, per tant es definirà conjunt borrós com a:

C={x|μ(x) ∀x∈U si μ(x)≠0}

Un cop vistos els elements principals veurem les operacions pertinents a aquests, heretades

directament de la teoria de conjunts matemàtics.

6.2.1 Operacions sobre conjunts borrosos Per tal de treballar amb els conjunts borrosos explicats, existeixen les següents operacions per a

dos conjunts borrosos (F i G):

− INCLUSIÓ: F⊂G. És possible quan μF(x)≤μG(x) ∀x∈U. El resultat vindrà determinat per

{x|μF⊂G(x) ∀x∈U}.

56


− IGUALTAT: F=G. És possible quan μF(x)=μG(x) ∀x∈U. El resultat vindrà determinat per

{x|μF=G(x) ∀x∈U},

− DESIGUALTAT: F≠G. És possible quan μF(x)≠μG(x) ∀x∈U. El resultat vindrà determinat

per {x|μF≠G(x) ∀x∈U},

− UNIÓ: F∪G. Sempre és possible. El resultat vindrà determinat per {x|μF∪G(x) ∀x∈U}, o el

que seria el mateix, {x|màx=(μF(x), μG(x)) ∀x∈U}.

− INTERSECCIÓ: F∩G. Sempre és possible. El resultat vindrà determinat per {x|μF∩G(x)

∀x∈U}, o el que seria el mateix, {x|màx=(μF(x), μG(x)) ∀x∈U}.

6.3 Modificadors lingüístics Un cop vistos els diferents conceptes creats per tal d’abordar el problema número 1 que sorgia,

veurem com els utilitzem per solucionar també el problema número 3, que requeria expressar

quantitativament una qualitat. Per exemple, si tenim la qualitat alt, amb una μ que determina

quan un home és alt (suposem per exemple 0,5), com determinem quan algú és bastant alt?

Doncs a través d’aquesta taula, que mostra com els connectors lingüístics s’expressen de la

següent manera en funció de μ:

MODIFICADOR DIFÚS

OPERACIÓ ASSOCIADA CÀLCULS NECESSARIS

No NEG(μ(x)) NEG(μ(x))= 1‐μ(x)

Molt CON(μ(x)) CON(μ(x))= μ2(x)

Bastant INT(CON(μ(x))) INT(μ(x))= 2μ2(x) si 0 ≤μ(x)≤ 0.5

1‐2(1‐μ(x))2 si μ(x)> 0.5

Una mica DIL(μ(x)) DIL(μ(x))= 2μ(x)‐ μ2(x)

Quasi DIL(DIL(μ(x)))

57


6.4 Mètodes d’inferència Un cop vistos els diferents elements necessaris per a estudiar les frases que hem definit com a

“difuses”, vegem les diferents lleis bàsiques d’inferència per aquestes:

Nom Esquema Explicació

Principi d’herència A(x) A⊂B . B(x)

Si tenim un conjunt A associat a un predicat, subconjunt borrós de B, qualsevol element amb la

propietat A hereta la propietat B

Modus ponens genralitzat

A (x) B(x)→ C(y). (A° (BxC))(y)

Posseeix el mateix raonament que el modus ponens de al lògica de primer ordre. Tanmateix, és BxC la matriu que contindrà A files i B columnes, i ° és

composició

Modus tollens (MT) D(y) B(x) → C(y). (D°(CxB))(x)

Posseeix el mateix raonament que el modus tollens de al lògica de primer ordre. Tanmateix, és CxB la

matriu que contindrà A files i B columnes

Sil∙logisme hipotètic

A(x) → B(y) B(y) → C(z) . ((AxB)°(BxC)(x,z)

Semblant a la regla de la transitivitat, simplement que el resultat opera amb matriues de AxB i BxC

58

IA: Intel∙ligència Artificial VI. REGLES

VI. REGLES

1. Característiques Un dels principals problemes de la lògica és la monotonia (raonaments monòtons) i la

ineficiència. Un raonament és monòton quan no es contradiuen mai la informació inicial amb la

final, però cal pensar que la vida real no és així, i en molts raonaments hauríem de considerar

poder esborrar premisses degut a noves conclusions. A més a més, en la lògica cal abordar una

gran quantitat de lleis d’inferència que determinaran solucions a problemes diversos, a part del

conjunt d’informació necessària per executar‐les.

Per això, en una últim període de la IA, del qual ja hem comentat el fet comercial, es

desenvolupa un sistema més simplificat i eficaç per a ser integrat a problemes més “útils”, tals

com el diagnòstic mèdic. Aquest sistema s’anomena regles, i és una versió millorada (podríem

dir més “aplicable”) del seu predecessor, la lògica. Diem que és millorat precisament perquè es

redueix el sistema d’inferència per tal augmentar el coneixement del domini, fet que ens apropa

més a la realitat. I és que en el dia a dia, la majoria de problemes són abordats no pas per un

gran procés de raonament, sinó més aviat per una gran experiència “emmagatzemada”, una

gran informació de l’entorn (domini).

Per tant, el que aconsegueixen els sistemes basats en regles (dels quals la major aplicació seran

els sistemes experts, que emula un “professional” humà) és reduir tot el sistema operatiu a una

inferència bàsica de antecedent – conseqüent, donant molta importància a tot el bloc de regles

emmagatzemades (per exemple, Si Tª és 40 ºC, aleshores febre). En conseqüència, l’objectiu de

les regles serà el mateix que en la lògica, és a dir, obtindre una sèrie d’informació a partir de

l’existent, però de manera més simple i directa. Dit d’una altra manera, l’aplicarem a situacions

on a partir d’una informació inicial se’n requereixi una de final.

Podríem concloure, per tant, que en les regles sacrificarem expressivitat per eficiència. Les

regles constitueixen un sistema més simple, menys expressiu, però més productiu (i remarco a

més a més el seu caràcter no monòton altre cop).

59

IAA: Intel∙ligèn

2. EUn sist

−

−

−

−

ncia Artificial

Elemetema basat e

Base de c

(coneixeme

representa

coneixeme

ALESHORE

Interfície d

informació

Base d’afir

el cas del

“Resposta1

corregides

Motor d’in

sistema.

ents en regles (SB

coneixement

ent), és a d

ar el conei

ents d’un si

S resposta1=

d’usuari: la q

ó.

rmacions: co

exemple lín

1=A ; Respo

automàticam

nferència: q

Interfícd'usua

R) conté els

ts: és on s’

dir, el conju

xement. Pe

stema de c

=correcta”.

que connecta

onjunt d’info

nies més am

osta2=C ; ...”

ment pel sist

que coordin

d

co

cie ari

següents ele

’emmagatze

unt de regle

er exemple,

correcció au

a el sistema a

ormació inicia

munt, la bas

” (Respostes

tema).

a la inform

Motor 'inferència

Base de neixemen

ements que e

ema el conj

es determina

, una regla

tomàtic de

a “l’exterior”

al amb la qu

e d’afirmaci

s d’un alumn

mació preced

a

ts

Bd'afir

el caracteritz

unt d’inform

ades de cad

a possible

tests seria

” tot sol∙licita

al es plantej

ions corresp

ne qualsevo

dent de la

Base macions

V

zen:

mació del d

da sistema

de la bas

“SI respost

ant‐hi o don

ja el problem

ponent podr

ol, les quals

resta mòdu

I. REGLES

domini

per a

se de

ta1=A,

ant‐hi

ma. En

ria ser

seran

ls del

60

IAA: Intel∙ligèn

3. PCom ja

obtind

abans

estruct

On IF s

el cons

Com a

compa

Tanma

conclu

Això li

marc m

està ob

cas “IF

“IF por

conclu

−

−

Al ser

emmag

és reté

del cu

malalti

ncia Artificial

Procéa hem come

re nova info

d’una simpl

tura:

serà el antec

seqüent o pa

a anteceden

ració, una re

ateix, si fins

sions , cal di

atorga certa

molt “teòric”

berta s’ha de

F porta=ober

rta=oberta T

sions:

Afirmació:

subjecte=m

Acció: refe

la regla l’ú

gatzemat en

é el conjunt

rs habitual

ia”.

s d’inentat, l’objec

rmació. Tanm

ificació del

cedent o par

art dreta (acc

t poden fig

elació, una ig

s ara hem

r que l’objec

a avantatge r

”. Per exemp

e tancar ; la

rta, THEN s’h

THEN acció=t

tals com les

malalt”

erent a realitz

únic sistema

la base de c

d’informació

de l’organi

nferènctiu d’un sis

mateix, aque

mètode), an

t esquerra (c

cions a estab

gurar diverso

gualtat, etc..

estat parla

ctiu d’una reg

respecte a la

ple, si havíem

porta està o

ha de tanca

tancar porta

s presents en

zar un procé

d’inferènci

coneixement

ó d’una form

sme”, sinó

IF

cia stema basat

esta inferènc

nomenat pre

condicions n

blir un cop s’e

os tipus d’in

.

ant d’un pr

gla pot ser t

a lògica, dom

m parlat fins

oberta ; alesh

ar porta”, po

a”. En conse

n les inferènc

és, com “THE

a conegut p

ts es reté pre

ma afirmativa

més aviat

T

en regles é

cia correspon

ecisament re

necessàries p

executi la reg

nformació, t

océs de ra

també un rao

mini del qual

s ara de infe

hores la port

odem introdu

qüència, po

cies lògiques

EN, activar se

per aquest

ecisament e

a del tipus “

“SI anomali

THEN

s realitzar u

n a un únic p

egla, que po

per a executa

gla).

tals com un

onament pe

onament des

queda limita

erències del

ta s’ha de ta

uir un nou c

dem determ

s. Per exemp

ensors”

mètode, tot

n forma de r

“Una malaltia

ia en organ

N

V

una inferènc

prototip (par

osseeix la se

ar la regla) i

na afirmació

er tal d’obt

stinat a una

at únicamen

tipus “Si la

ncar” o en a

concepte del

minar dos tip

le “THEN

t el coneixe

regles. És a d

a és una alte

nisme ALESH

I. REGLES

ia per

làvem

egüent

THEN

ó, una

tindre

acció.

t a un

porta

aquest

tipus

pus de

ement

dir, no

eració

HORES

61


4. Dependència Com ja hem dit, una de les característiques de les regles és el seu caràcter no monòton. Parlem

de caràcter no monòton perquè en molts casos es produeix una contradicció de la informació

inferida a la base d’afirmacions. Vegem un exemple:

1. IF x dóna classe de matemàtiques, THEN x=matemàtic. En Joan dóna classe de

matemàtiques En Joan és matemàtic.

2. El següent pas podria ser que la interfície d’usuari preguntés en quina universitat va

estudiar per determinar el nivell (valoració) a priori de la persona. Obtenim a la base

d’informació “UB Facultat de Física i Química”.

3. Per altra banda tenim una regla que determina que “IF x ha estudiat a UB Facultat de

Física i Química, THEN x= Físic o Químic”.

I aquí sorgeix la contradicció. Davant d’un cas on el conseqüent es contradiu amb les premisses,

fet que ens portaria a eliminar‐les, es pot considerar dues opcions a realitzar amb les

conclusions obtingudes a partir d’aquestes premisses (en el cas de l’exemple no hi hauria

problema, doncs no hem realitzat cap inferència a partir de “En Joan és matemàtic”). Parlem per

tant de dos tipus de dependència que possibles a establir per tant entre conclusions i informació

base errònia:

− Dependència reversible: estableix una dependència de premissa falsa – conclusió falsa.

Per tant, si en qualsevol instant els antecedents són anul∙lats, caldrà anular els

conseqüents.

− Dependència irreversible: estableix una dependència de premissa falsa – conclusió no

té per que ser falsa. Per tant, un cop inferit un fet, aquest no podrà ser rebatut o

invalidat.

5. Inferència i encadenament Un cop vistos l’estructura i característiques d’una regla (unitat bàsica d’inferència) i un sistema

de regles, tractarem aquí el procés d’inferència complet com a tal.

62


El primer que cal tenir en compte en un procés inferència de SBR és que aquest té forma de

cicle. És a dir, un cop generades noves conclusions s’activen noves regles a partir d’aquesta. A

més a més, la utilització d’una regla té un caràcter molt variable. Això significa que un procés

d’inferència no té un objectiu clar, únic i concret: degut a la immensitat de regles (i la majoria

compostes del tipus “IF mal de coll AND dificultats per empassar AND febre THEN angines”), i la

coincidència d’alguns antecedents d’aquestes, existeixen múltiples possibilitats a l’hora de

seleccionar quina regla serà executada. Per aquest motiu, s’han establert diverses estratègies

d’inferència o encadenaments, no tant pel fet de solucionar l’elecció entre dues regles possibles

en algun cas concret (fet que tractarem en el següent capítol), sinó per establir un mètode (un

ordre) d’aplicació d’aquestes regles.

Per tant, existeixen varis tipus d’encadenaments de regles, que definiran en quin ordre i quin

tipus de regles aplicarem a cada procés d’inferència.

5.1 Encadenament endavant Aquest sistema estableix el mètode més senzill i lògic d’aplicació de regles: executar tan sols

aquelles que puguin ser aplicades en aquell instant. És a dir, aquelles els antecedents dels quals

disposem en aquell moment. Per exemple, si a la base d’afirmacions s’hi troba registrat un

antecedent el qual podria ser “Ara plou”, només executarem una regla la part esquerra de la

qual sigui “IF ara plou”. Sembla absurd i de sentit comú, i per això diem que aquest és el mètode

més “natural”, si més no, cal considerar altres opcions o encadenaments que veurem més

endavant. Vegem un exemple (abstracte) del tipus d’encadenament endavant:

Donat un sistema amb el següent registre a la base de coneixements:

Regla 1 (R1): IF h2 i h5 aleshores h1

Regla 1 (R2): IF h4 i h3 aleshores h2

Regla 1 (R3): IF h6 aleshores h3

I la base d’afirmacions del qual és: h6, h7, h9, h8, h4, h5. El procés d’aplicació de les regles (o

encadenament seria el següent: com que segons aquest sistema solament s’apliquen aquelles

regles que “podem aplicar”, en una primera instància únicament podríem aplicar R3, i un cop

63


executada aquesta, el següent pas de la cadena correspondria a R2, seguit de R1, fet que

ocasionaria el final del cicle d’aquest SBR.

5.2 Encadenament endarrere Si bé el primer tipus d’encadenament ens sembla lògic i potser creiem que no en caldria

l’explicació, s’exposa per ressaltar el contrast amb l’altre mètode existent, l’encadenament

endarrere. En aquest, el sentit que li donem a l’aplicació és contrari, no executem les regles en

funció de les premisses, sinó en funció de les conclusions. Per exemple, si en comptes de

determinar la malaltia a partir dels símptomes se’n volgués verificar l’existència o l’absència

d’una concreta, aplicaríem aquest sistema.

Per fer‐ho, seleccionaríem la regla que contingui la condició desitjada, i l’aplicaríem, si fos

possible, per inferir les conclusions esperades (“x” té angines). Si ens fos impossible degut a la

falta dels antecedents requerits a la base d’informació, hauríem d’iniciar una altra regla que

contingui aquests antecedents com a conclusions. Per exemple, en el cas de les angines, si no

poguéssim executar la regla per falta d’una informació continguda en la base d’afirmacions que

expressi que “x té febre”, podríem buscar una altra regla que ens infereixi que subjecte “x” té

febre, per exemple “IF x està a 39º, THEN x té febre”, si aquesta tampoc pogués ser aplicada per

falta d’antecedents, repetiríem el procés fins a trobar un antecedent vàlid per a una regla que

ens permetés, en forma d’encadenament, inferir fins al final el resultat desitjat.

També es podria donar el cas d’arribar a un punt on no restés cap regla amb una conclusió

desitjada, fet que significaria la impossibilitat de demostrar el conseqüent final desitjat en aquell

cas. És a dir, si per exemple seguint el mecanisme anterior no trobéssim cap regla el conseqüent

de la qual fos “x està a 39º”, no podríem demostrar que el subjecte “x” te febre i per tant, no

podríem inferir que aquest mateix té angines.

Vegem un exemple complet d’encadenament endarrere, seguint el mateix problema que en el

punt 5.1.

Base de coneixement Base d’afirmacions R1: IF h2 i h5 aleshores h1 R2: IF h4 i h3 aleshores h2 R3: IF h6 aleshores h3

h6, h7, h9, h8, h4, h5

64


El procés d’encadenament a partir de la regla 1 seria el següent: com que per aplicar R1

requerim h2 i no existeix a la base d’afirmacions, caldria cercar una regla a partir de la qual es

pogués inferir h2. El resultat seria R2, i aquesta al seu temps necessitaria disposar de h3, que

finalment seria inferit al aplicar R3. A partir d’aquí inferiríem totes aquestes regles per arribar

fins a R1, la desitjada.

6. Control de raonament Hem estat exposant fins ara els diferents ordres o metodologies en que es poden aplicar les

regles, però, què passa si en qualsevol dels encadenaments ens trobem en algun moment

l’existència de dues possibles regles aplicables? És a dir, per exemple, què passaria si en el

encadenament endavant es donés el cas de dues regles que contenen els mateixos antecedents

(els quals s’han d’aplicar), o de dues conclusions en el cas de l’altre sistema?

Quan existeix tal controvèrsia, cal dur a terme una elecció entre les candidates, el que

s’anomena establir un control del raonament.

6.1 Necessitat Les raons diverses que expliquen el perquè de la necessitat d’aquest control són les següents:

− Contingut de la inferència: les conclusions poden dependre de l’ordre d’aplicació de les

regles. Per tant, una elecció aleatòria possiblement ens porti més inconvenients que

avantatges.

− Eficiència: l’aplicació de la regla adequada portarà més ràpid a la conclusió.

− Lògica: cal establir un control per allargar‐te amb regles innecessàries i absurdes, i

aquest ha de ser lògic i raonable, fet que ocasionarà un augment de l’eficiència

comentada.

65


6.2 Mètodes Per dur a terme tal elecció, es poden aplicar diferents mètodes atenent a criteris distints:

− Ordenació de regles: el més senzill i poc “elegant”, doncs estableix que es col∙loquin

primer aquelles regles que es vulguin examinar abans. Té un cost de manteniment

elevat, i només pot ser aplicat a programes simples on les regles es troben en forma de

llista consultada cíclicament.

− Ordenació de les clàusules dintre de cada regla: únicament aplicable a sistemes que

utilitzin encadenament endarrere. Aquest determina col∙locar primer aquelles regles

que tinguin més possibilitats de fallar per tal d’optimitzar la recerca.

− Introducció de clàusules: es pretén introduir clàusules al principi de cada regla,

aquestes aportant algun referent, que serà a partir del qual el programa es guiarà per

determinar si aplicar la regla o no, en funció de la informació aportada.

− Selecció segons actualitat: consisteix en executar primer aquelles regles l’antecedent de

les quals es basa en informació més recent. Perquè pugui ser aplicat el motor

d’inferència haurà de registrar en quin moment s’ha generat cada afirmació.

− Selecció segons especificitat: aplicarà aquelles regles més específiques. Per exemple:

o R1: IF a THEN b

o R2: IF a AND d THEN e

En aquest cas seria més específica R2 per disposar de més clàusules (antecedents)

− Control d’agendes: es crea una agenda que conté totes les regles en forma de variable

(“instanciació”), a la qual li és assignada un valor en funció de la prioritat d’execució de

cada regla.

− Metarregles: consisteix en crear un conjunt de regles (metarregles) que estableixin

diversos criteris d’aplicació de la resta de regles. Dit d’una altra manera, un conjunt de

regles que expliquin com aplicar les demés de regles.

66

IAA: Intel∙ligèn

7. RAcabem

segons

bases

coneixe

summa

exhaus

qualsev

a soluc

7.1 CJa vist

aquest

mateix

amb p

perfecc

idònia

7.2 AUsat e

organit

d’optim

haurem

Tema

ncia Artificial

Recerm d’explicar

s quin criteri

i la idea de

ements al lla

ament nece

stiva en cada

vol problem

cionar aques

Cerca een el capíto

t tipus de ce

x procés, fins

ossibilitats d

ció amb l’en

per al cas: c

Algoritmen els encad

tzació d’arbr

mització de l

m d’examina

"x" està a

rmòmetre arca 39 ºC

ca de els diferent

efectuarem

e les priorita

arg de la infe

ssari, ja que

a cas exami

a resultaria

t problema,

en retrool 3, s’utilitz

rca s’elegia u

s a arribar a

d’expansió p

ncadenamen

cada node su

me RETdenaments

re per explo

a recerca de

r en cada ca

"x"

39 ºC

front de "x" estáa 39 ºC

"x" e

reglets tipus d’en

m l’aplicació d

ats i el mèt

erència per d

e si un cop

nant tota la

inviable deg

corresponen

océs a en els sist

un node i se

un carreró s

per a poder c

t endarrere,

uccessor rep

TE endavant i

rar les regle

e les regles e

s serà la que

té febre

á

està malalt

es ncadenamen

de les regles

ode, cal efe

desenterrar l

p elegit l’en

informació

gut al temps.

nts als dos ti

temes d’enc

e’n expandia

ense sortida

continuar. Ja

, doncs l’estr

resenta l’ant

desenvolup

es, sinó més

en l’algoritm

e respongui a

"x" té la temperatura elevada

t utilitzats p

s. Tanmateix

ectuar una r

es regles apl

cadenament

existent a c

Existeixen,

pus d’encade

adenament

un únic succ

a per a poder

a es veu que

ructuració d

tecedent ne

anterio

figura),

regla m

aplicar.

que ex

l’elegit

at per Cha

aviat per ap

e parteix de

a la situació

per a un SBR

x, un cop ass

recerca efici

licables a cad

t realitzéssim

cada momen

per tant, du

enament.

endarrere. R

cessor, del q

r retrocedir f

e aquest mè

e l’arbre i la

cessari per a

r (tal com

fins arribar

mare que vo

I precisam

xpandirem e

d’entre els p

arles Forgy,

plicar‐les. Tan

e la base que

nova. És a d

V

R, que estab

sentades aqu

ient a la ba

da instant. A

m una explo

nt, la resoluc

es estratègie

Recordem q

qual s’efectu

fins a l’últim

ètode encaix

a recerca en

a aplicar a la

es mostra

al node inic

olem demost

ment el succ

en cada cas

possibles.

no proposa

nmateix, el s

e l’única regl

ir, en una pr

I. REGLES

leixen

uestes

se de

Això és

oració

ció de

es per

ue en

ava el

node

xa a la

ell és

a regla

en la

cial, la

trar o

cessor

s serà

a una

secret

la que

rimera

67

IAA: Intel∙ligèn

instànc

servirà

referèn

un siste

A més

sistem

(antece

no, i d

d’aque

com a

regla,

casos a

graf RE

ncia Artificial

cia realitzare

com a pre

ncia als canv

ema de selec

a més, pel

a d’arbre, d

edents semb

després es p

est capítol en

node inicial

activa el cam

anomenat no

ETE:

em una expl

emissa en e

vis nous, no p

cció de regle

que fa a l’a

doncs un co

blants), es de

podria proce

n el cas de c

l, i sent cad

mí que com

ode fulla) qu

loració conc

el pròxim pa

pas a tot el d

es òptim i un

aplicació de

op seleccion

eterminarà a

dir a elegir‐

onflicte. L’ar

a successor

mpleixi totes

ue contindrà

reta, però u

as, només b

emès. Vegem

que no ho s

regles, ja e

nades totes

a partir de l’

ne una mitj

rbre mostra

les diferent

les condicio

la regla apli

un cop infer

buscarem en

m un exemp

sigui:

em comenta

les regles

arbre quina

ançant els c

la condició

s condicions

ons, conduin

cada. Vegem

ida la prime

ntre les reg

le gràfic de l

at que és all

adequades

regla pot se

criteris expo

comú de tot

s que disting

nt al node

m un exempl

V

era conclusió

gles les que

la diferència

là on s’utilit

per a un in

er aplicada i

sats en el p

ts els antece

geixen entre

meta (en aq

le en castellà

I. REGLES

ó, que

facin

entre

tza un

nstant

quina

punt 6

edents

e cada

quests

à d’un

68


8. Avantatges i inconvenients Entre els avantatges i els inconvenients dels SBR cal destacar:

8.1 Avantatges − Uniformitat: presenten una caràcter o sistema uniforme i universal que en facilita la

manipulació.

− Naturalitat: posseeixen un caràcter natural i poc complicat que en facilita la

comprensió.

− Modularitat: presenten una modularitat (capacitat que posseeix un sistema de ser

estudiat) elevada, degut a la seva naturalitat comentada, que en facilita l’anàlisi i estudi.

− Caràcter declaratiu: presenten un caràcter declaratiu (afirmatiu), i no pas, per exemple,

interrogatori com en algun cas la lògica.

8.2 Inconvenients − Inexpressivitat: presenten molt poca expressivitat, a diferència, com havíem comentat,

de per exemple la lògica.

− Opacitat: posseeixen una naturalesa que dificulta el seguiment del procés deductiu.

− Cobertura del domini: requereixen una quantitat molt elevada d’informació del domini

(o de memòria), i tot i que en el cas dels sistemes experts és un inconvenient fins i tot

per la intel∙ligència natural (requereixen molts estudis), és considera tanmateix una

desavantatge.

− Poca consistència i completud: és un sistema poc consistent i complet.

69

IA: Intel∙ligència Artificial VII. XARXES ASSOCIATIVES

VII. XARXES ASSOCIATIVES

1. Característiques Com ja hem vist, un dels principals interessos rau en la representació del coneixement més que

en la inferència. Ja des d’un principi del període que hem anomenat “romàntic”, les

investigacions van començar a apuntar les seves mirades cap a la representació. Com a

conseqüència, a més a més de les regles naixeran les xarxes associatives, l’ús de les quals està

molt diversificat i costaria de definir de manera precisa. Tanmateix, existeix un punt en comú:

precisament que han estat concebudes per a representar el coneixement. En poques paraules,

entre unes aspiracions i interessos molt alts de representar‐lo de forma adequada i extensa (fet

difícil per les propietats que comentàvem al capítol 1), les xarxes associatives suposaran un

mètode òptim per fer‐ho, organitzant de diferents maneres tot el saber del domini.

Però per a què serveix això? Vull dir, un cop organitzat tot el coneixement, què? Si bé en

aquesta recerca hem estat perseguint constantment la idea de “que les màquines pensin com

humans”, l’organització del coneixement no va ser concebuda com a tal, és a dir, no com a un

mètode operatiu, sinó més aviat com a un instrument. M’explico. A poc a poc, s’anirà avançant

(o si més no s’intentarà avançar) cap a sistemes més generals i per tant, menys concrets que,

per exemple, la recerca heurística. I és que realment, com més capaç d’abarcar sigui un sistema,

més “humà” o “millor” serà. Per això, es desenvoluparan cada cop més no tant tècniques que

abordin processos concrets (recerca, raonament, ..) sinó sistemes d’organització de tot el

conjunt: informació, inferències,.. I aquí serà on entraran en joc les tècniques de representació,

bàsicament les xarxes (associatives), la funció de les quals consistirà en emmagatzemar i

organitzar el coneixement existent dintre d’aquest conjunt. Per tant, les xarxes seran integrades

en altres sistemes més extensos, que constitueixen una combinació d’aquestes i altres

mecanismes (regles, lògica, recerca..) per crear sistemes eficients de “pensament artificial”.

També es podria crear un sistema simple d’inferència concret a partir d’una xarxa qualsevol,

però bé, és poc usual.

70


Tot i això, resulta estrany el fet de que si bé no es comença a pensar en la integració fins a ben

entrats els setanta, vuitanta, les primeres xarxes datin dels anys seixanta o inclús cinquanta. Bé,

la qüestió és que devien perseguir la mateixa idea: tractament del coneixement per utilitzar‐lo

després, però aquest després es devia concebre com a un sistema simple, i no general o “a

part”, tal com s’estudia avui en dia.

Cal comentar per això, que des d’aquí estudiarem únicament com representar les xarxes, no pas

com integrar‐les o utilitzar‐les.

2. Definició de xarxa Un cop explicat per a què van ser ideades i l’objectiu de les xarxes, cal definir, si més no de

manera general i comuna, què es considera una xarxa, és a dir, de quina estructura partim per

realitzar qualsevol sistema de representació del coneixement.

Doncs bé, com a punt comú, i salvant les diferències, una xarxa associativa és qualsevol graf que

conté una sèrie de nodes units entre sí amb enllaços de diferents tipus, amb la característica

especial, per això, que aquests primers representen conceptes i els arcs es correspondríen

generalment a relacions que s’estableixen entre tals. La imatge mostra un exemple d’un tipus de

xarxa associativa qualsevol en espanyol:

Ara procedirem a descriure els diferents tipus de xarxes conegudes, que si bé com hem

comentat tenen una funció comuna de representació el coneixement, l’ús i el funcionament de

cada una un cop integrades en un sistema serà molt divers, doncs el tipus de coneixement que

representaran serà també variat.

71


3. Xarxes semàntiques 3.1 Definició i utilitat Les xarxes semàntiques, el primer tipus de la història, van ser pensades per a representar i

organitzar el tipus de coneixement corresponent al llenguatge, o més ben dit, tal com el seu

nom indica, a la semàntica, ciència que estudia el funcionament del llenguatge. Per tant,

s’utilitzen per a representar el llenguatge natural, tot atenent a les diferents relacions que

s’estableixen entre els seus membres. És a dir, pretenen emmagatzemen els diferents conceptes

necessaris per a desenvolupar una llengua i utilitzar‐la.

Un dels usos més interessant que es deriva d’aquest tipus de xarxa un cop integrat en un

sistema complex pot ser el tractament del llenguatge. És a dir, juntament amb un mecanisme

d’inferència es podria estudiar la comprensió del llenguatge d’entrada, la formulació del

llenguatge de sortida... I així no caldria analitzar la informació en forma de conceptes (fet que

ens obliga a desxifrar‐la a cada instant per poder ser entesa per la computadora), sinó més aviat

en forma purament lingüística, cosa molt més senzilla en quant a utilitat.

Tanmateix, cal fer un petit incís: aquest tipus de xarxes depenen de la llengua. I és que en el fons

és lògic, doncs cada idioma tindrà diferents estructures del seu llenguatge.

3.2 Memòria semàntica de Quillian

3.2.1 Característiques És el primer tipus de xarxa semàntica, desenvolupada als anys seixanta, i dintre del que és el

funcionament del llenguatge, organitza el coneixement que es correspon al significat de les

paraules. Ho fa intentant simular una definició en un diccionari qualsevol. Per a tal fi, es

desenvolupa una estructura amb dos tipus de nodes:

− Node tipus: són els que contenen el concepte que volem definir, i es representa a

l’interior d’un òval.

− Node rèplica: són aquells dels quals es serveix el node tipus per a representar la

definició.

72


3.2.2 Tipus d’enllaç Per a la correcta representació de qualsevol significat, el model de Quillian utilitza una sèrie

d’elements característics, concretament sis tipus d’enllaços entre els diferents nodes, cadascun

per representar les diferents relacions que s’estableixen entre aquests. Són els següents:

− Subclasse: s’utilitza per unir un node tipus amb la classe al qual pertany. Vegem

mitjançant un exemple com s’expressa:

− Modificació: uneix dos nodes rèplica del mateix pla, de tal manera que el segon

modifica al primer. S’expressa:

− Disjunció: S’expressa:

− Conjunció: S’expressa:

− Propietat: uneix la relació que s’estableix entre un objecte i el subjecte al qual hi te

referència, a través d’una propietat qualsevol. S’expressa:

On B és el subjecte, C l’objecte, i A la relació o propietat que s’estableix de C cap a B

73


− Referència al tipus: s’utilitza per representar un node rèplica com a node tipus en un

altre pla. S’expressa

Vegem un exemple complet en castellà d’una xarxa de Quillian, a partir de la qual hem extret els

exemples.

74


3.3 Gràfics de dependència conceptual de Schank

3.3.1 Característiques Els gràfics de dependència conceptual de Schank constitueixen un mètode que dintre del

llenguatge natural pretén analitzar i representar oracions simples (no compostes), és a dir,

conceptes unitaris. Per fer‐ho, estudia i expressa les relacions que s’estableixen entre els

diferents tipus de paraules (desenvolupades per Quillian) dintre d’aquestes i es serveix d’un

sistema bastant semblant a la gramàtica, però de caràcter semàntic.

Per a tal objectiu utilitza diversos elements: categories conceptuals, relacions i modificadors

d’enllaç.

3.3.2 Categories conceptuals Representen les diferents categories a les quals poden pertànyer les paraules de cada xarxa, i

està inspirat en les diferents classes gramaticals (verb, substantiu, adjectiu...). Són les següents,

(amb les seves abreviacions corresponents) i inclouen:

− PP: objectes, persones, animals.. en resum, qualsevol subjecte. (Substantius)

− ACT: accions. (Verbs)

− PA: atributs o propietats dels objectes. (Adjectius)

− AA: atributs o propietats de les accions. (Adverbis de manera, de quantitat,de dubte, de

negació...)

− T: temps. (Adverbis de temps)

− LOC: posicions. (Adverbis de lloc)

3.3.3 Relacions Són les relacions que es poden establir entre les categories anteriors. És a dir, com pot actuar

cada categoria conceptual, semblant a les funcions gramaticals. Són les següents, i es

representen així:

75


− : estableix una relació de subjecte – acció del subjecte. (Subjecte

‐ Verb)

− : estableix una relació de subjecte – propietat del subjecte.

(Sintagma nominal – Complement del nom)

− : estableix una relació de acció – objecte de la acció. (Verb –

Complement directe)

− : estableix una relació de subjecte – acció del subjecte –

receptor de la acció. (Subjecte – verb – complement indirecte /

complement de règim verbal / complement circumstancial de companyia)

− : estableix una relació de subjecte – acció del subjecte –

direcció de la acció. (Subjecte – verb – complement de règim

verbal / complement circumstancial de direcció)

− : estableix una relació de acció – instrument de la acció. (Verb –

complement circumstancial d’instrument)

I les tres relacions que no es corresponen tant a funcions gramaticals sinó a un conjunt

d’aquestes concretes, que les expressem de manera contextualitzades:

− : estableix una relació de “Y” a causat “X”.

− : estableix un canvi d’estat d’un objecte.

− : indica que o bé PP2 és part de PP1 o bé PP2 és el posseïdor de PP1.

76


3.3.4 Modificadors d’enllaç Són els que modifiquen els enllaços per tal d’afegir‐hi una informació addicional, no implícita,

sinó de manera explícita. Es col∙loquen al damunt de la relació en qüestió.

Són els següents, i se simbolitzen per:

− P: transporta a qualsevol estructura o relació al passat.

− F: transporta a qualsevol estructura o relació al futur.

− Ts = x: indica que qualsevol estructura o relació comença a l’instant “x”.

− If = x: indica que qualsevol estructura o relació comença a l’instant “x”.

− C: estableix el valor de condicional en qualsevol estructura o relació. “Si... alsehores...”

− /: neguen tota l’estructura o relació.

− ?: qüestionen tota l’estructura o relació.

3.3.5 Tipus d’accions primitives No és que sigui un altre element utilitzat als grafs de Schank, però s’exposa a part degut a la

seva extensió.

Parlem doncs d’accions primitives per designar els diferents tipus d’accions “ACT” (apartat

3.3.2), que existeixen. Aquestes són, amb el corresponent pseudònim:

− ATRANS: Transferència d'una relació abstracta tal com possessió, propietat, control.

− PTRANS: Canvi de la posició física d'un objecte.

− MTRANS: Transferència d'informació mental (dir, explicar, comunicar)

− PROPEL: Aplicació d'una força física a un objecte.

− MOVEL: Moviment d’una banda del cos.

− GRASP: Acte mitjançant el qual el subjecte agafa un objecte.

− INGEST: Acte d'ingerir.

− CONC: Conceptualització o pensament sobre una idea per un actor.

77


− EXPEL: Expulsió des del cos del subjecte a l'exterior.

− MBUILD: Construcció per part d’un subjecte d'una nova informació a partir d'una altra ja

existent.

− ATTEND: Acció de dirigir un òrgan dels sentits cap a un objecte.

− SPEAK: Acció de produir sons amb la boca.

Vegem ara doncs, un exemple d’una xarxa formada a partir d’alguns dels elements exposats

aquí. Aquesta es correspon a “L’Anna veu vi”

4. Xarxes proposicionals Si bé es podrien incloure dintre les xarxes semàntiques com a fórmula encara més extensa, la

tradició els hi ha donat un nom i un lloc apart. I parlem d’extensa perquè aquestes pretenen

exposar conceptes més amplis, ja no tan sols les relacions que s’estableixen dintre les oracions

simples, sinó les que existeixen dintre de les compostes, i inclús entre vàries oracions, fet que

permet desenvolupar històries senceres.

Tanmateix, estudiarem solament un cas particular, les representacions de Shapiro i Sowa.

4.1 Xarxes de Shapiro i grafs de Sowa Tot i ser exposades en conjunt, van ser concebudes per separat, però el fet és que guarden

estretes similituds (teoria comuna però representació diferenciada), raó per la qual s’estudia

normalment d’aquesta manera.

Aquest tipus de xarxes parteixen de la base de Schank, però amb la diferència que utilitzen un

llenguatge més simplista, assequible i de sentit comú. No distingeixen ni classes de paraules ni

relacions, simplement expressen funcions lèxiques (agent, verb, objecte, destinatari...).

78


A més a més, aquest sistema permet incloure frases simples en sistemes oracionals més

complets, per formar oracions compostes, històries...

Vegem com expressaríem en castellà “En Joan es pensa que l’Andreu s’està menjant un gelat”,

tant des de la concepció de Shapiro com de Sowa:

5. Xarxes de classificació Les xarxes de classificació no duen a terme una organització semàntica del coneixement, sinó

més aviat una de conceptual. En aquest tipus de xarxes es pretén estructurar la informació en

forma de classes i subclasses, per la qual cosa s’estableix l’anomenada jerarquia de conceptes.

Per expressar aquesta dependència utilitzarem un arbre, i es col∙locaran com a descendents

aquells nodes que pertanyin dintre de la classe del node en qüestió. Per tant, el node inicial

constituirà la classe de la qual formaran part tots els descendents del graf. Com a conseqüència,

un arc traçat des de A fins a B expressarà que A és més general que B. Vegem un exemple:

79

IAA: Intel∙ligèn

Una ut

mitjanç

viu.

6. XAquest

de con

aquest

sistem

nodes.

En una

de A. A

B), en

qualsev

1En aqu

diagnos

ncia Artificial

tilitat molt i

çant l’herèn

Xarxest tipus de xa

nceptes), pe

ts grafs orga

a que segue

a xarxa causa

Això el fa prò

situacions co

vol1:

Objecte

M

uest cas, no es qu

sticar càries.

interessant d

cia. És a dir,

s causarxes segueix

rò amb la d

nitzen el co

eixi aquest c

al qualsevol,

òsper per, un

om per exem

e físic

Mal de

ue les càries siguin

d’aquests si

segons aqu

sals xen la matei

diferència qu

neixement a

criteri expres

per tant, un

n cop integra

mple, el diag

Ésser viu

Ésser inanim

queixa

n causades per e

stemes de c

est gràfic, p

ixa metodolo

ue no expre

atenent a le

ssarà una re

n arc dirigit d

at, utilitzar‐lo

gnòstic. Vege

A

mat

Càries

l

l mal de queixal.

cara a la int

odem dedui

ogia o idea q

essen jerarq

s causes que

elació de cau

de A fins a B

o per la infer

em un exem

Planta

Animal

Relleu

Edifici

Ens referim a qu

VII. X

tegració pot

ir que una p

que les ante

uia, sinó ca

e el produei

usa ‐ conseq

B expressarà

rència causa

ple d’un tipu

Elef

Go

Gran

Munt

Va

Ca

Hosp

Forats

e, els forats, sera

ARXES ASSO

t ser la infer

planta és un

eriors (classif

usalitat. És

ixen. Per tan

qüència entr

que B és la

l (A és la cau

us de xarxa c

fant

os

nota

tanya

all

sa

pital

an la causa per a

OCIATIVES

rència

ésser

ficació

a dir,

nt, tot

re dos

causa

usa de

causal

80


6.1 Xarxes Bayesianes Són les xarxes causals més utilitzades, doncs estudien les causes atenent a la probabilitat

d’aquestes mateixes, és a dir, qüestionant si A realment és la causa de B; fet que les fa més

reals. I és que en el fons, el coneixement humà estableix probabilísticament si allò que pensem

ha estat la causa o no. Per exemple, seguint l’exemple anterior, un dentista estimarà

(probabilitat) amb menor o major grau si algú té càries depenent dels indicis observats: no

podrem afirmar amb la mateixa certesa l’existència de càries si partim de la premissa “dolor”

que partint de la premissa “forats”.

Per tant, un graf bayesià, és un graf causal (té l’aparença d’aquest) però “amb probabilitats

incloses”. Per a determinar‐les, s’utilitza el teorema de Bayes, que estudia les probabilitats en

aquests tipus de situacions (en el fons, aquestes xarxes constitueixen una barreja d’un arbre

causal al qual l’hi ha estat aplicat el teorema de Bayes en els seus components). Per calcular tals

probabilitats a cada node, utilitzem la següent fórmula:

| , … ,| … |

∑ | … |

Un aspecte que afirma aquest mètode que cal tenir en compte per dur a terme tal estudi és el

següent “les variables alienes a una altra variable no influiran en la decisió d’aquesta”.

Vegem doncs un exemple el que anàvem comentant (amb un aclariment de l’últim esmentat):

2On d representen les causes i e les conseqüències.

81

IA: Intel∙ligència Artificial VIII. MARCS I GUIONS

VIII. MARCS I GUIONS

1. Característiques Tot el que em vist fins ara ens pot semblar “complet”: ja tenim diferents mètodes d’inferència,

sistemes d’emmagatzematge de la informació, etc... Però bé, el fet és que totes les formes de

representació del coneixement (capítol anterior) vistes fins ara tenen un punt feble: la

organització. És veritat que totes les xarxes posseeixen una coherència interna, però el fet és

que qualsevol sistema multidisciplinari queda limitat a un conjunt massa gran sense cap relació

entre sí, o dit d’una altra manera, sense cap relació externa. A part, sorgeixen problemes típics

de “monotonia”, és a dir, problemes que ens impedeixen representar diverses formes de

coneixement a la vegada, doncs una xarxa estableix una representació d’un únic tipus de

coneixement.

Per això, els anys vuitanta veuen néixer diferents solucions a aquest problema. Proliferen idees

com els marcs i els guions, que si bé els primeres juguen i han jugat un paper més important,

ambdues van ser concebudes com una forma d’organització davant del “caos”. Aquestes

solucions permeten estructurar tot el coneixement en conjunt, gràcies a uns petits canvis a les

formes de representació conegudes fins aleshores, per tal d’efectuar‐ne una millora i poder

abastir els problemes organitzatius que sorgien.

2. Marcs 2.1 Definició Van ser desenvolupats per Minsky el 1975. Com acabem de comentar, els marcs suposen una

millora per fer front als problemes estructurals que presentaven les formes de representació de

la informació fins ara. I es que en realitat, encara avui en dia costa fer una distinció clara entre

marc i xarxa associativa. En general, considerarem un marc quan la informació està ordenada

dintre del conjunt.

82


Dit d’una altra manera, un marc és un conjunt d’informació organitzada que fa referència a un

element, semblant a una xarxa, però la principal aportació és que aquesta informació no

s’expressa en forma de nodes, sinó més aviat en forma d’atributs i de caràcter divers. Això

permet trencar la monotonia de les xarxes associatives, fent referència a diverses

característiques de caire diferent en cada atribut. A més a més, és poc usual veure un marc per

separat, i precisament això ha permès crear sistemes de coneixement eficients i d’abast

considerable.

Un marc s’anomena comunament de la següent manera: NOM_DEL_MARC.

2.2 Descripció Cada marc conté un concepte descrit, amb els atributs (propietats o elements), anomenats

camps, corresponents. Tanmateix, un sistema es torna eficient gràcies a la unificació de diversos

marcs de diferent caràcter creant així una cadena de marcs (parlàvem de l’informació que es

troba organitzada dintre del conjunt, o el que seria el mateix, la cadena), establint relacions que

variaran segons el model, ja que els programes comercials actuals disten molt de la versió

original de Minsky, que explicarem a continuació.

A través d’aquestes relacions, es desenvolupen lògicament també relacions de dependència (per

exemple, entre el marc ANIMAL i el marc LLEÓ), i un sistema d’herència d’atributs entre els

camps dependents. A més a més, si per cada sistema de marcs es mantenen una sèrie de camps

(per exemple, ANIMAL posseeix l’atribut PES), per cada marc canviarà el que anomenem valor

del camp, que precisament és el “valor” que adquireix un atribut (per exemple pes) en cada

marc concret.

2.2.1 Dues concepcions Si bé el concepte de marc ha estat sempre tancat i clar, la relació entre aquests i el seu ús ha

estat una idea bastant fluctuant des de la seva concepció.

En el model original de Minsky, les connexions s’establien exclusivament a partir del fet de que

un marc podia ocupar l’interior d’un altre (per exemple, DORMITORI podia ser un camp de

CASA). S’establia així el que s’anomenava xarxa d’activació, que recorria els diferents marcs del

83

IAA: Intel∙ligèn

conjun

dintre

Tanma

de la c

podria

aquest

caracte

1.

2.

Vegem

ncia Artificial

nt activant aq

del primer.

ateix, les eine

reació d’una

desencaden

tes no dist

erístiques:

Diferenciem

conceptes

conceptes

Tot i que

coneixeme

pretén ser

mecanisme

qual un ca

el marc OF

m un exemple

cam

quells que ho

es comercial

a organitzaci

nar en dos m

tingeixen e

m dos tipus

o entitats

particulars d

han estat

ent, ja vam

r integrada

e com a base

da marc her

FICI posseeix

e d’un marc a

classe VERTE_________

mp NOMBRE_

instà___

cv

camval

camp NO

↑ superclasse

o requeria la

s actuals pre

ó jeràrquica

marcs fills ano

ntre marcs

de marcs:

generals (OF

dels marcs cl

concebuts

comentar e

en sistemes

e per a la inf

reta els camp

un atribut “S

actual expos

class____

ca

camp

EBRATS ____

_DE_POTES

ncia CAMELL __________

amp PESalor: 200

mp HÀBITATlor: desert

OMBRE_DE_POvalor: 4

superclasse ↑

e

a situació, fet

esenten un n

entre els m

omenats VER

actius i

el primer, c

FICIS, per e

asse (ARQUI

com a vers

en el capítol

s més comp

ferència en a

ps dels seus

SALARI”, ARQ

sant els conc

e ANIMAL_________

mp PES

p HÀBITAT

OTES

class_

camp FOR

ca

↑ superc↑

↑ sup

t que provoc

nou tipus de

arcs (per ex

RTEBRATS i I

marcs pass

classes, que

xemple). El

ITECTE, per e

sió millorada

l anterior q

plexos. Per a

aquest sistem

avantpassat

QUITECTE he

eptes vistos

se INVERTEBRA____________

RMA_DE_DESP

instàn_____

camval

camp valor

amp FORMA_valor:

lasse

perclasse

V

caria l’activac

relació que s

emple, un m

INVERTEBRA

sius, però

són aquells

segon, inst

exemple)

a per a la

ue una estr

això, es dot

ma, la herèn

ts en la xarxa

eretarà tal at

fins ara:

ATS

PLAÇAR‐SE

ncia SERP________

mp PESor: 1

HÀBITATr: selva

DE_DESPLAÇAR reptant

VIII. MARCS

ció de nous

s’estableix a

marc arrel AN

ATS). A més a

sorgeixen

que repres

tàncies que

representac

ructura com

ta als marcs

ncia, a través

a (per exem

tribut.

R‐SE

I GUIONS

marcs

partir

NIMAL

a més,

noves

enten

seran

ció de

a tal

s d’un

s de la

ple, si

84


2.3 Elements Un cop vistos les característiques i la forma dels marcs, veurem tot seguit els diferents elements

constitutius que permeten representar‐los.

2.3.1 Facetes Anomenem facetes a tots aquells mecanismes de programació que serveixen per caracteritzar

els diferents camps de cada marc. Les més utilitzades són les següents:

− Valors per defecte: defineix quin valor agafa el camp en el cas que no se li hagi assignat

cap altre valor anteriorment.

− Multivaluat: especifica si el camp admet o no varis valors simultanis

− Restriccions: determina les limitacions que s’imposen al rang de valors que pot adquirir

el camp

− Certesa: fa referència a la credibilitat del valor assignat al camp

− Facetes d’interfície: determinen la interacció amb el usuari.

2.3.2 Dimonis Són aquells elements operatius que s’utilitzen per treballar amb els camps, és a dir, determinats

per a que l’usuari pugui modificar el camp. Són els següents:

− Dimonis de necessitat: s’utilitzen per tal de saber quin es el valor d’un camp que no en

tingui cap d’assignat.

− Dimonis de modificació: s’utilitzen per tal de variar el valor d’un camp.

− Dimonis de borrat: s’utilitzen per tal de eliminar el valor d’un camp.

− Dimonis d’assignació: s’utilitzen per tal de afegir un valor a un camp.

− Dimonis d’accés: s’utilitzen per tal de sol∙licitar el valor a un camp.

85

IAA: Intel∙ligèn

2.5 PUn form

llengua

En un

“object

de sim

Un mè

conten

autom

objecte

interfíc

I preci

organit

proble

arribar

D

superclasse ↑

ncia Artificial

Programmalisme de

atges de prog

entorn en

tes”, el qual

ples qualitat

ètode són pr

nir mètodes t

àticament a

es a través d

cie.

isament això

tzativa, sinó

mes bastant

r a la solució.

De dimensió 0

Punt

Mètodes

Mostrar

↑

mació orepresentac

gramació ori

que es disp

es defineix

ts descriptiv

rocediments

tals com “tir

l produir‐se

el denomina

ò els i dona

ó també co

t semblants

. Vegem un

Lín

Atri

Extr

Mèt

Mos

superclasse

supercla

orientadció de coneix

ientada a ob

posi de tal s

per una inst

es, poden se

s associats a

rar, elegir,..”

un canvi, s

at pas de mis

a un caire d

om a font o

als que veie

exemple d’u

A

Colo

M

Se

De dimens

nea

buts

rems

odes

strar

asse → ←

da a objxement basta

bjectes.

sistema, els

tància que co

er també m

als objectes

. Els mètod

sinó que són

ssatges, la fo

diferent, ja

operativa. U

em al capítol

un desenvolu

Figura

Atributs

or posició del centre

Mètodes

Moure

eleccionar

sió 1

Arc

Atributs

Radi

Angle de sorti

Angle de l'ar

Mètodes

mostrar

← superclasse

jectes ant semblan

marcs pass

onté uns atr

mètodes, fet q

en qüestió.

es, a diferèn

n activats pe

orma de com

no tan sols

Utilitzant‐los,

3 i 4, aplica

upament com

da

c

Nom

superc

super

V

t als marcs s

sen a ser e

ibuts. Aques

que els difer

Per exempl

ncia dels dim

er missatges

municació util

s són conce

, podem tr

ant els mèto

m el que este

De di

Polígon

Atributs

bre de costats

vètex

Mètodes

Mostrar

lasse

rclasse →

VIII. MARCS

són els anom

l que anom

sts atributs,

rència dels m

e, CARTES p

monis, no s’ac

s transmeso

litzada en aq

ebuts com a

obar solucio

odes correcte

em comenta

mensió 2

Cerc

Atribu

Rad

Mètod

Mostr

Rota

← supercla

I GUIONS

menats

menem

a part

marcs.

podria

ctiven

s pels

questa

a font

ons a

es per

nt:

cle

uts

di

des

rar

ar

asse

86


La diferència bàsica entre un llenguatge de programació orientada a objectes i una xarxa de

marcs és per tant que en la perspectiva orientada a objectes els mètodes s’associen a cada

objecte i la arquitectura és plana. Per altra banda, en qualsevol estructura de marcs es parteix

d’una arquitectura multicapa conté objectes estructurats, sense mètodes associats.

2.6 Representació Per a representar un marc digitalment ho farem d’aquesta manera (variable atenent al

llenguatge de programació utilitzat):

3. Guions Ja hem dit que la solució al problema que aborda aquesta unitat té dos cares, la primera la qual

ja hem exposat i la segona que veurem a continuació.

< marc > :: = <classe> | <instància> <classe> :: = classe <nom - clase> es

superclasse <espec-super>; < atributs>

fi <instància> :: = instància <nom - instancia> es

Instància de <espec- super>; < atributs>

fi <espec - super> :: = <nom - classe>{,<nom - classe>}*| nil <atributs> :: = <par - atribut - faceta>{; < par -

atribut - faceta>}*| <buit>

<par - atribut - faceta> :: = <nom - atributo>= (<faceta>{<faceta}*)

<faceta> :: = <nom - faceta> < valor>| dimoni < tipus - de - dimoni > < crida - a - dimoni >

<nom - de faceta> :: = valor | valor - per -defecte < tipus - de -dimoni> :: = si - es - necessita | si – s’afegeix |

si - es - borra < valor > :: = <constant - elemental> | < nom –

instancia > < buit > :: =

87


3.1 Característiques Hem aplicat els marcs per tal d’organitzar el coneixement referent a objectes, però els guions

neixen com a solució destinada a estructurar informació referent a les situacions.

Per tant, un guió és una estructura de coneixement que organitza informació relacionada amb

situacions dinàmiques estereotipades, com poden ser: jugar un partit de futbol, sortir amb els

amics, anar al cine... És un mètode una mica rudimentari, doncs aquest només admet situacions

de seqüència de fets bastant fixa i poc complexa, però bé, permet abastir un coneixement

extens i variat, que això és el que cerquem.

Un guió s’anomena de la següent forma: $NOM_DEL_GUIÓ

3.2 Elements Per tal de dur a terme el objectiu preestablert que ja hem explicat, els guions utilitzen o es

componen de diferents elements, els quals són:

3.2.1 Escenes Són tots els successos descrits en el guió organitzats de forma seqüencial, de manera que la

realització d’una escena ens permetria passar a la següent. Podríem dir per tant que una escena

és el pilar o l’element bàsic d’un guió.

3.2.2 Rols, objectes i llocs Corresponen als personatges típics que intervenen en el guió, els objectes que apareixen

descrits en la seqüència de fets i els llocs on es realitzen les accions pròpies dels guions.

Normalment una persona, objecte o lloc concret ha de complir una sèrie de condicions per

poder formar part del guió, les quals es defineixen a través d’una sèrie de restriccions associades

a cada rol objecte o lloc d’aquest. (Més tard explicarem perquè ens interessa que algú pugui

formar part del guió)

3.2.3 Resultats Són aquell conjunt de fets que es veuran realitzats quan s’hagi completat la successió de fets

que caracteritzen cada guió.

88


3.2.4 Capçaleres Tot i els elements que acabem de veure, que serveixen bàsicament per constituir o descriure el

guió, existeixen una altra sèrie d’elements o mecanismes que s’hi incorporen també. Tanmateix,

aquests permeten determinar si un guió és adequat per explicar certa situació, la qual no ha

estat encara identificada (més tard veurem perquè és útil això). Existeixen varis tipus de

capçaleres:

3.2.4.1 Que donen nom al guió Per determinar si una situació respon al guió, es busca algun indici que coincideixi amb el nom

del guió. Per exemple, la paraula “restaurant” d’un text podria fer‐nos saber que cal activar el

guió $RESTAURANT per utilitzar‐lo per a aquest text.

3.2.4.2 Que representen condicions En aquest cas es busca alguna condició que respongui al guió. Per exemple, el cas de

$RESTAURANT, podria ser activat per “tenir gana”

3.2.4.3 Que representen instruments Es cerca algun instrument que correspongui al guió. Per exemple, el cas de $RESTAURANT podria

ser activat a partir del indici “coberts”.

3.2.4.4 Que representen llocs El cas de $RESTAURANT podria ser activat per una informació del tipus “bufet lliure”, o

“restaurant la sèpia”.

3.3 Inferència Ja sabem que qualsevol forma de representació de coneixement està pensada per a ser

integrada posteriorment en un sistema complet, realitzant doncs una funció de proporcionar i

emmagatzemar el tipus d’informació d’aquest. Per tant, cada tipus d’estructura de tractament

d’informació posseeix unes característiques que al fan òptimes per a ser utilitzat en un tipus de

mecanisme complet determinat, i per tant òptim per un tipus d’inferència.

89


En el cas dels marcs, hem comentat la seva adequació per a inferència mitjançant l’herència, la

qual cosa el feia òptim per a sistemes que volien per exemple raonar.

En el cas dels guions, però, s’utilitzen sobretot per inferir a través de la comparació, per la qual

cosa hem vist que ja incorporen elements que ho faciliten. Aquest tipus d’inferència el fa útil

entre d’altres per a la comprensió del llenguatge natural: per exemple, al llegir una història,

s’activaria un guió (es determinaria si aquest guió correspon a aquella situació), i es comprendria

el text a través del prototip de la història. Per aquesta raó ens interessava comparar i

seleccionar diverses característiques dels guions (capçaleres, personatges..)

3.4 Avantatges i inconvenients Entre els avantatges que incorporen els sistemes basats en guions, cal destacar:

− Són independents al idioma.

− Permeten integrar informació dintre del guió per a realitzar inferències.

Tot i això, presenten una sèrie d’inconvenients, com és ara:

− La rigidesa del mecanisme de representació no permet tractar cap seqüència variable

d’accions, sinó més aviat desenvolupament fixos i preestablerts.

− Els guions són incapaços de compartir informació entre ells.

− Tampoc posseeixen capacitat per representar motivacions interiors.

90

IA: Intel∙ligència Artificial IX. INTEGRACIÓ

IX. Integració

1. Introducció Fins ara hem presentat en el discurs de forma aïllada i per capítols diversos mecanismes

alternatius d’inferència i representació del coneixement per tal d’abordar solucions a problemes

diversos. És més, s’ha emfatitzat en distingir l’aplicació de les diferents estratègies segons els

diferents tipus de problemes que calen abordar. Tanmateix, les situacions reals disten molt de

poder ser afrontades sota una sola perspectiva, ja que aquestes requereixen sempre utilitzar

diverses tècniques diferents combinades, doncs són molt més complexes que les abordades al

llarg d’aquest treball.

Era necessària una visió per separat, ja que no podem manejar les diferents peces d’un

trencaclosques sense conèixer‐les primer individualment. Un cop explicats els diferents mètodes

dels quals disposem, en aquest capítol ens dedicarem a mostrar les tècniques (tot combinant

aquests mètodes) disponibles actualment per fer front als problemes reals (que tenen com a

característica principal la complexitat), tot sabent com manipular les diferents peces d’aquest

“puzzle” vistes fins ara per integrar‐les totes en un mateix sistema.

Per tant, aquest capítol pretén il∙lustrar un doble objectiu: per una banda, s’intenta mostrar com

aplicar per fer front a problemes reals, més que a simples casos particulars com els vistos fins

ara (per exemple, les gerres d’aigua), ja que la investigació d’aquests queda limitada als inicis de

la IA(és clar, no podien construir la casa per la teulada); en segon lloc, es pretén proporcionar

una perspectiva integradora dels diferents mètodes vistos fins ara.

I com integrem les diverses estratègies de programació actualment per complir tal finalitat?

Doncs mitjançant els sistemes integrats, que en el seu estat més simple suposen una versió

millorada dels marcs (ja hem comentat que van esdevenir el primer pas cap a la integració

gràcies a la seva forma), i dels quals cal destacar les arquitectures integrades.

91


2. Definició i característiques d’un sistema integrat Com acabem d’esmentar, els sistemes integrats (S.I. o SI) neixen dels marcs, aprofitant les

propietats organitzatives de les què disposen per fusionar els diversos mètodes d’inferència i

alhora seguir implementant‐los‐hi una representació del coneixement òptima. Per tant, i en el

fons, aquest SI no deixa de ser una ampliació d’un marc tot introduint els mètodes d’inferència

entre els atributs de cada instància. Vegem un exemple:

Evidentment, això suposa

com una idea base, en part

una “plataforma de

llançament”,i cal remarcar

la seva concepció com a un

concepte abstracte a partir

del qual posteriorment

s’obtindran sistemes

integrats molt més

complexes, partint

d’aquesta base

d’implementar mètodes diversos dins d’una estructura organitzativa, per tal de resoldre els

problemes que apareixien en aplicar cada mètode per separat (desorganització i poca aplicació

real). Per això, cal remarcar la capacitat de complementació com a principal característica, ja

que en el fons l’únic que cerquem és introduir dintre d’una realitat organitzativa i teòrica

(coneixement) alguna eina pràctica (inferència). Per exemple, CommonKADS, posseeix una gran

estructura de representació (anàlisis del coneixement, separació en capes, descripció i

reescriptura d’aquest,..) que incorpora mètodes d’inferència combinats.

PERSONA Generalitzacions (mamífers) Edat restringit a (O< x < 130) Nacionalitat herència de Pares Idioma herència de Pares & Residència Residencia instància de País Sexe (Home, Dona} Germans instàncies de Persones Núm. - fills restringit a (O< x < 30) hores - treball restringit a (O< x < 15) Grau - ocupació

Funció LISP: Grau - ocupació (?x. núm-fills, ?x.hores-treball)

Salari rang enters Estado defecte viu

92


3. Propietats d’un sistema integrat Bé, un cop vistes què són i per a què s’utilitzen els SI, vegem quines propietats desitjables en un

formalisme d’aquest tipus:

1. Representació estructurada i uniforme de tots els seus elements, per tal de poder

solucionar els problemes organitzatius que hem plantejat a la introducció d’aquest

capítol.

2. Selecció i ús dels diferents mètodes d’inferència disponibles, per poder fer front a les

situacions reals que comentàvem a través d’una arquitectura ampla en quant a

solucions o opcions.

3. Organització eficient del coneixement adquirit, per poder portar a terme la tasca pròpia

de manera també eficient.

4. Arquitectures integrades Havent definit el què s’entén per integració vegem com es desenvolupa tal fi. Hem parlat d’un

concepte abstracte (podríem comparar‐ho per exemple amb les corrents artístiques del segle

XX, en les quals disposem d’una idea central d’art “abstracte”, “trencador”, “novedós”.. però

que es queda en una idea, a partir de la qual es desenvoluparà tot una ramificació de corrents

més definits). Per tant, una aplicació o definició d’un SI la trobem a les anomenades

arquitectures integrades.

Conceptualment, no trobaríem gaire diferència entre una arquitectura integrada i un SI,

bàsicament aquesta es troba en un fonament d’aplicació. Podríem dir que aquesta és més

definida, i n’és l’aplicació més usual i concreta d’un SI. Per tant anem a matisar algun concepte

que no haguem descrit encara.

Una arquitectura és una estructura informàtica que incorporant IA ha de ser capaç de

proporcionar un entorn genèric de programació en el qual es puguin combinar diferents

elements propis del mètode. Com que hem dit que manté una estreta relació amb el marc,

podem deduir que la seva representació externa és més aviat de modelització del coneixement,

93


no pas inferència, que quedarà en segon pla. Tot i això, cal remarcar que l’entorn informàtic ha

d’incorporar algun mecanisme per transformar l’entrada input al sistema intel∙ligent i elaborar‐

ne alguna ordre per a l’arquitectura. Però en el fons, aquesta teoria de traducció no és part de la

intel∙ligència artificial, o almenys d’un entorn d’inferència d’aquesta, sinó més aviat de la part

que comentàvem en el capítol 1 i 2 que es correspon a la descomposició de la informació (com

en qualsevol procés d’inferència).

Recordem la importància de ser flexibles en un món canviant per poder abastir un domini

general ampli dintre d’un mateix sistema. Per a tal objectiu, qualsevol arquitectura incorporarà

un esquema operatiu bastant general, ja sigui per representar una inferència dintre d’un

concepte (domini de coneixement, per exemple, inferència dintre del marc “persona”), per

representar un problema a solucionar, o un subconcepte dintre d’un concepte d’organització del

saber dintre del sistema. La forma general de les entitats descriptives d’una arquitectura

integrada és la següent (un altre concepte abstracte simplement orientatiu, que variarà en

funció del entorn de programació):

5. Esquema d’una arquitectura integrada Un dels punts claus estructurals de les arquitectures integrades ha de ser la capacitat de

convergència entre el marc i els seus elements. Per tant, ha de proporcionar un marc general

uniforme capaç de representar el coneixement de forma homogènia, de tal manera que els

mètodes seguits per solucionar siguin quins siguin els problemes puguin descriure’s amb les

mateixes estructures de dades.

Cal dir que una de les característiques actualment fonamentals de les arquitectures integrades

és l’aprenentatge, degut a que la complexitat requerida pels sistemes eficaços no podria ser

abastida per un sistema que no aprèn.

5.1 Característiques estructurals Les entitats que integren una arquitectura són les següents:

<entitat atribut valor>

94


− Marc: propi de l’estructuració en la representació de coneixement, subdivideix els

elements conceptuals en un nivell més extern.

− Slot: cada element dintre del marc, semblant als atributs que comentàvem en l’altre

tema, amb la única diferència que ara els slots posseiran un caràcter més

interdisciplinari (ja no solament de representació de coneixement).

− Subslot: bàsicament un slot dintre d’un altre slot (subdivisions internes).

Inferit de la forma general de representació, el esquema concret de representació dintre

d’aquest nivell de l’arquitectura seria la següent:

L'element fonamental dins de l'estructura d'una arquitectura són els "problemes", articulació

bàsica en la IA també. Un problema és qualsevol dubte que volem operar o resoldre, (en el cas

de les arquitectures una pregunta sobre el valor d’un slot), sent aquesta la finalitat primera de

tot sistema intel∙ligent: solucionar problemes.

Operativament, els problemes els expressarem formalment de la següent manera:

, sent la solució del problema

Per exemple, dins d'una arquitectura que volgués expressar una relació familiar, sent cada

element del marc, si volguéssim esbrinar els germans de "x", preguntaríem (<x>

<germans>).

En la mateixa línea, existeixen una sèrie de problemes predeterminats, o un conjunt d'instàncies

de problemes, que són l'aplicació d'un problema de caràcter general, amb un motlle

predeterminat. Per exemple, preguntant per totes les mares que trobarem dins de la família,

utilitzarem una instància general (<?x> <mares>), o simplement <mares>. Per tant,

indicant només el nom de la instància o (slot), s'apel∙la a tots els elements les direccions del qual

segueixin aquest slot.

(<entitat> <slot>)= <valor>

(<entitat> <slot>)

<entitat atribut valor>

95


A més a més, els problemes o les classes de problemes poden ser considerades a la vegada

entitats. Així, podem aplicar elements propis d'un llenguatge de programació concret a un

problema, de la mateixa manera que podem aplicar problemes a problemes. Un exemple del

primer cas és: (<Joan> <pares> existeixen?)1.

Paral∙lelament, l’organtizació dels mètodes d’inferència i derivats s’emmagatzemen de la

mateixa manera. Per exemple, en el cas de preguntar pels pares del Joan, hauríem de tenir

establert dins un marc estructural el mètode associat a aquest tipus d’inferència, per exemple,

el mètode d’herència.

D’aquesta manera, anomenarem a tot el que refereix a un mètode recomanat per una classe de

problema com a “creences” sobre aquell tipus de problema, que seran utilitzats sempre i quan

el slot sobre el que es pregunta no tingui cap valor. Un cop inferit, existeix la possibilitat

d’implementar la solució obtinguda dins del “valor” del marc.

5.2 Característiques funcionals Pel que fa ja no tant a l’estructuració interna, sinó a la funcionalitat d’aquesta (mètodes

d’inferència), predefinirem una estructura per inferir, o el que és el mateix, per obtenir alguna

informació sobre un slot (recordem sempre que qualsevol variació s’atén al llenguatge de

programació utilitzat):

Tanmateix, pel que fa al mètode utilitzat, cal dir que es poden definir mètodes d’inferència

propis, però en el cas de que no fos així o no es trobés cap mètode en intentar inferir algun slot,

utilitzarem els mètodes en aquest ordre:

1. Herència: consisteix en substituir el valor del slot per el del immediatament superior en

l’ordre de la jerarquia. Per exemple, si ens pregunten per la nacionalitat del Joan, la

heretarem del pare.

2. Pèrdua de context: consisteix en perdre el context de la inferència per tal de trobar una

altre procés en un domini semblant i poder solucionar el problema. Per exemple, en el

(dona’m-valor <slot> <entitat>)

1En les respectives paraules de l’idioma de programació

96


cas de no trobar cap mètode per inferir l’hàbitat d’un mamífer, podríem buscar un

mètode per inferir l’hàbitat de qualsevol espècie.

3. Valor per defecte: simplement accedeix al valor del subslot “valor per defecte” de tal

slot.

4. Especialització de context: obté la solució a través d’alguna restricció, preguntant per

algun cas més concret. Per exemple, en comptes de preguntar pels fills del Joan

preguntarien pels fills mascles del Joan.

D’altra banda, cal remarcar podem utilitzar altres paquets d’inferència, com pot ser algun

paquet de raonaments lògic predefinits aplicats per a inferir, com el PROLOG, o el LISP.

Per tant, podríem concloure en aquest apartat que l’únic que fa un mètode de inferència és

senyalar la direcció de cerca dels resultats. El que s’ha de procurar per tant és estructurar la

informació, intentar dotar‐la de la màxima complexitat, i establir‐hi una bona relació i

cohesió tot intentant maximitzar l’eficàcia de la inferència al mateix temps que és crea un

sistema.

97

IA: Intel∙ligència Artificial X. APRENENTATGE

X. APRENENTATGE

1. Introducció Al llarg de tot aquesta recerca s’han anat descrivint en diferents capítols els mètodes bàsics,

podríem dir els pilars de la intel∙ligència artificial. Ja vam veure en el capítol 9 que en la realitat

la situació és molt més difusa, i molt més actualment. Per tant els mètodes “bàsics” podríem dir

que han passat de ser mètodes a ser estratègies purament puntuals. En aquest context, es creen

constantment nous mètodes d’implementació, que parteixen de la base dels que ja hem

explicat, i que evidentment seran molt més complicats. Un d’aquests és l’aprenentatge, que

estant tant desenvolupat com està en el fons podria ser definit purament com un mètode

“propi”o bàsic, però que no s’engloba dins d’aquest marc per una senzilla raó de dependència i

una qüestió històrica.

L’aprenentatge ha estat un dels avanços més importants en la IA, i actualment forma part, i amb

un paper molt important, d’aquesta realitat tant complexa i sinèrgica que és la programació de

la IA. Dins d’aquest treball no aprofundiré en cada mètode actual (o podríem dir “barreja

enginyosa de mètodes primaris”), com és lògic, ja que la meva intenció no és fer de Diderot ni

d’Alembert. Parlarem només de l’aprenentatge, el més important, en el qual tampoc podrem

aprofundir massa (igual que en la resta del treball) per les mateixes raons. A diferència dels

altres capítols no cal que introdueixi massa que és l’aprenentatge, simplement dir que ja no és

tant una funció operativa com de eficiència (per millorar‐la).

2. Què és aprendre? El procés d’aprenentatge en si, al igual que la intel∙ligència, és difícil de definir degut a la seva

amplitud. Sovint s’ha definit per això, com “guanyar coneixement, o comprensió, o habilitat, a

través de l’estudi, la instrucció o l’aprenentatge”, o “modificació de la tendència del teu

comportament a través de l’experiència”. Aquestes dues frases reflecteixen força bé el

contingut d’aquest capítol.

98


En el cas de l’aprenentatge de les màquines, molt semblant a l’aprenentatge animal, aprendre

no significa res més que modificar l’estructura interna del programa (és clar, en els humans

passa una cosa semblant que alguna cosa dins nostre “es modifica”). D’una forma més concreta,

es tracta de crear programes capaços de generalitzar comportaments a partir d’una informació

no estructurada subministrada en forma de in‐puts.

Tot i això, aquests canvis interns són graduals, i igual que en intel∙ligència artificial alguns

parlaran només en casos d’estructures complexes. N. Nilson, de la Universitat d’Stanford, afirma

que “Alguns canvis, com per exemple el fet d’afegir una informació recopilada a una base de

dades no han de ser necessàriament entesos com aprenentatge, sinó per exemple quan una

màquina millora després d’haver sentit una gran quantitat de persones parlant”

Clar per això que en un sistema informàtic existiran moltes maneres d’aprendre, que explicarem

més endavant.

En resum, podríem dir que un sistema que aprèn ho fa a base de rebre entrades, i

paral∙lelament a l’acció “intel∙ligent” que desenvolupa, infereix en el seu sistema nova

informació.

3. Perquè? Podríem pensar que no cal aprendre. Perquè no ens dediquem simplement a experimentar i a

crear algoritmes molt complicats que puguin arribar el més lluny possible? Existeixen unes raons

per les quals és molt important desenvolupar en un sistema un mètode d’aprenentatge:

− La principal és que la perfecció no existeix. Els humans ens equivoquem, i per tant les

màquines construïdes per nosaltres també, entre altres coses perquè molts dels

IN‐PUT ANÀLISIS INFERÈNCIAAPRENENTATGE

MODIFICA

99


resultats no són bons fins que han estat provat i retocats experimentalment. Un sistema

que aprèn permet corregir aquests errors sense un gran esforç econòmic suplementari.

− Precisament aquesta raó econòmica, que ens permetrà estalviar una gran quantitat en

reformes per la raó que sigui (reparació, addicció d’informació, actualització,..)

− Existeix molt coneixement inscrit entre línies en un sistema, sobretot que relaciona la

informació entre ella. És important inferir aquestes noves relacions. (Això és conegut

amb el nom de data mining)

− L’enteniment humà té una capacitat limitada, i moltes vegades no som capaços de

induir o deduir informació degut a la complexitat que aquesta requereix. Una màquina

és mecànica, i per tant infinitament més ràpida a l’hora de realitzar càlculs, fet que li

permet deduir o induir informació que a nosaltres ens requeriria un gran esforç i

investigació.

4. Tipus d’aprenentatge Existeixen varis tipus d’aprenentatge, ja que depenent de la situació en la que ens trobem

requerirem d’un algorisme o un altre. A part de distingir com aprenem també és important

atendre a què aprenem, ja que podem modificar moltes parts internes de l’estructura. Així

doncs, les diferents estructures d’aprenentatge, en les quals no aprofundirem degut a la

complexitat, són les següents:

4.1 Segons el procediment A grans trets, distingim sobretot entre algorismes d’aprenentatge supervisat i no supervisat:

− Els algorismes d’aprenentatge supervisat són els que contenen informació addicional

per a tal procés, és a dir, estant supervisats. D’alguna manera podríem dir que són els

que estan programats per aprendre seguint unes pautes. Per exemple, l’etiquetatge

d’uns vectors determinats atenent a una base de dades seria un algorisme supervisat, ja

que la màquina “aprèn els valors dels vectors” amb un algorisme que el compara amb la

base de dades. Un altre exemple és aquell del algorisme d’aprenentatge dintre d’un

100


SBR, tractat en el capítol 6, que modificarà la base de coneixement atenent a unes

pautes que ja hauran estat marcades prèviament.

− Els algorismes no supervisats, per altra banda, són els que no contenen informació sobre

el procés, no contenen alguna seqüència lògica que els digui com han d’aprendre.

Simplement, i sense informació, es dediquen a observar la realitat i inferir informació.

Per exemple, un sistema de reconeixement de veu podria utilitzar aquest algoritme, ja

que no seria possible indicar quina part del algorisme de funcionament s’ha de modificar

durant l’aprenentatge i amb quin tipus d’informació, sinó que simplement podríem

induir a partir de l’observació.

Per altra banda, existeixen varis mètodes o algorismes pròpiament dits, compatibles amb la

classificació i en moltes altres més (aprenentatge inductiu, deductiu, abductiu,.. per exemple),

que són els següents:

− Aprenentatge mitjançant preguntes. L’algorisme pot interaccionar amb un “instructor”

(ja sigui un humà, una altra computadora o inclús el mateix sistema) fent‐li preguntes, i

rebent respostes sobre un concepte inicialment desconegut. Al final, l’algorisme haurà

d’obtenir una descripció exacta del concepte objectiu, segons un llenguatge establert

prèviament.

− Aprenentatge PAC (Probably Approximately Correct). El més estudiat fins ara,

l’algorisme llançarà exemples aleatoris, que qualificarà de positius o negatius per

aproximar‐se bastant al concepte desconegut. Per exemple, dins d’un sistema de

simulació de parla humana, es podria utilitzar llançant paraules aleatòries per veure el

resultat.

− Aprenentatge mitjançant errors acotats. El algorisme accedeix seqüencialment a una

llista d’exemples i va fent prediccions de com classificar un exemple en relació al

concepte desconegut. Cada predicció és aleshores acceptada o rebutjada per un agent

extern. Seguint amb l’exemple de la simulació de la parla, s’interaccionaria amb un

“professor” que et digués si una frase feta obtinguda d’un diccionari és correcte en un

context o no. El que s’intenta és minimitzar el nombre de prediccions errònies.

101


− Aprenentatge multidisciplinari. S’utilitza coneixement basat en situacions anteriors per

aplicar‐lo a problemes a temps real. També s’anomena raonament basat en casos.

4.2 Segons la modificació Cada algorisme tindrà com a objectiu modificar algun component intern, que evidentment no

sempre serà el mateix, per tant, atenent a l’estructura interna d’un sistema basat en IA,

classificarem els algorismes segons si modifiquen la següent o següents informacions:

‐ Algorismes interns de funcionament, inferència o inclús d’aprenentatge.

‐ Qualsevol tipus de coneixement, ja sigui sobre el domini, coneixement intern

d’estructuració, estats concrets,...

‐ Gramàtiques internes de interacció entre el món real i el món digital.

Tot i això, tots els algorismes, indiferentment del tipus i del tipus de classificació, posseeixen

trets comuns, sobretot quan parlem d’operativitat. El funcionament d’aquests procediments

acostuma a estar regit per un llenguatge o un sistema de definició bastant semblant, basat en

l’àlgebra boolesiana, que tracta de simplificar expressions digitals.

102

BLOG III. ELS ESCACS: APLICACIÓ I EXPERIMENTACIÓ (PART PRÀCTICA)

103

IA: Intel∙ligència Artificial ELS ESCACS: PART PRÀCTICA

L’objectiu d’aquesta part és posar en pràctica tots els coneixements adquirits durant aquest

treball per tal d’analitzar els escacs “intel∙ligents”, o escacs per computadora, aplicació comú en

IA.

1. Aplicació dels conceptes al funcio-nament dels escacs Primer, hem analitzat els algorismes utilitzats usualment en aquest jocs i la seva evolució amb

l’ajuda de dos experts en aquest àmbit: Miquel Sànchez (UPC) i Pedro Meseguer (IIIA).

Entrevista a Miquel Sánchez

P: Bon dia senyor Sànchez.

R: Bon dia Josep.

L’entrevista té com a objectiu analitzar el funcionament intern d’un programa d’escacs intel∙ligent. Primer de tot, quin és l’algorisme o el mètode més utilitzat pels programes d’escacs? Podria explicar‐lo una mica?

La estratègia bàsica és utilitzar algorismes de cerca heurística, que fan servir una funció que

intenta estimar d’alguna forma quant lluny estàs, en aquest cas, d’una posició guanyadora. En el

fons, molts dels problemes que es treballen en intel∙ligència artificial i teoria de jocs d’escacs

utilitzen un algorisme de cerca, els quals partint des d’una situació inicial, intenten arribar a un

estat final, guiats per la funció heurística. D’aquesta manera, l’estratègia bàsica no és res més

que intentar explorar totes les possibilitats o camins existent i elegir‐ne un. És clar, això com

104


deus imaginar‐te és molt complicat degut a l’enorme quantitat de moviments possibles: en el

escacs es calcula una mitjana de 36 per cada situació. (S’aixeca cap a la pissarra i dibuixa un

tauler d’escacs)

Estem en un estat inicial, que en aquest cas seria la partida en la seva situació inicial, i en base a

avaluar quins moviments possibles tenen els jugadors formem tots els possibles moviments (per

exemple, movent un peó o l’altre en el cas de la primera tirada), és a dir, generem totes les

posicions o estats possibles per a nosaltres. L’altra part dels algorismes de cerca és avaluar cada

posició generada. Com ja t’he dit, això es fa mitjançant una funció d’avaluació (heurística), la

qual té en compte la posició relativa de cada peça. És clar, és fonamental el mètode pel qual tu

defineixes quant bona és una posició, ja que aquesta et portarà a fer eleccions més bones o

pitjors.

A partir d’aquí, s’elegeix moviment, i passaríem al torn del contrincant. Un cop hagués mogut, es

revaluaria a partir d’aquesta nova posició quines noves opcions tindríem, i repetiríem el procés.

Ha explicat que un dels punts claus en l’estratègia d’aquest joc és l’avaluació de les posicions.

Quins criteris té en compte la funció?

Normalment es té en compte quantes peces tens tu, la posició en sí d’aquestes (si domines una

posició central del tauler per exemple), etc... Hi ha un munt de coses que pots avaluar i que

formarien part d’aquesta funció, el resultat de la què normalment s’expressa mitjançant un

nombre. Si el valor de la funció és bona, és bo per a tu i dolent per al contrincant, i sinó és tant

bona, la cosa no va bé. Fixa’t per això que les heurístiques sempre suposen que nosaltres estem

fent el millor i que l’oponent quan tiri farà el que és raonable. Per això Kasparov va adonar‐se’n

després de jugar varies partides que Deep Blue feia moviments raonables, i una de les partides

precisament la va guanyar gràcies a això, ja que es va dedicar a fer coses il∙lògiques i va

desconcertar a la màquina.

Vostè ens ha explicat una mica el que seria el prototip d’algorisme que s’utilitza, la cerca en

espai d’estats. Tot i això, existeix algorisme concret pels escacs?

Sí. El que s’ha fet servir més és el MINIMAX. El MINIMAX consisteix en el següent: un cop

avaluada la funció heurística de cada una de les posicions possibles, dius: “quan em toca tirar a

mi, jo vull maximitzar el valor de la funció heurística, i quan li toca a l’altre, minimitzar‐lo. Si

1Deep Blue va ser el primer programa d’escacs que va guanyar al campió mundial, Garry Kasparov

105


aquesta posició d’aquí té un valor màxim per a mi, jo vull intentar arribar aquí, aleshores triaré

aquest camí.

I existeix alguna modificació o algun cas especial d’aquest algorisme?

En general el que ha passat és que cada cop més els algorismes de cerca en els escacs han anat

complementant la expansió i avaluació amb més coses, per exemple, estudiar tot un conjunt

d’obertures predeterminades. És a dir, ja tenir com prefabricades una sèrie d’obertures i

utilitzar‐ne una que, per exemple, sé que em comporta un avantatge posicional. També, en el

cas de les negres, podem estudiar la possibilitat de triar‐ne una (obertura) en funció del que

hagués fet el contrincant. Una cosa que també s’ha fet molt també és no només fer servir tot

això sinó a més a més integrar‐ho amb altres tipus de tècniques que s’utilitzen en intel∙ligència

artificial, com el raonament basat en casos o el que s’anomena fons d’experiència. M’explico

amb un exemple. Si jo tinc guardada alguna partida o alguns moviments claus d’aquesta i arribo

en un estat i el reconec, dic: “mira, aquest estat és igual que el d’aquella partida que ja vaig fer i

sé que en aquest estat si faig això ell probablement farà això i jo faré això i això i em portarà a

guanyar”.

En resum, el que s’ha fet per millorar els sistemes és sobretot integrar més d’una tècnica, no

només l’algorisme de cerca basat en MINIMAX i funcions heurístiques sinó d’altres.

Tot i això, els programes d’escacs no han aconseguit superar als humans al 100%. Quins son

els handicaps dels sistemes actuals?

Un dels punts fluixos dels sistemes actuals és potser el fet que no aprenen massa. Si tu els fessis

jugar contra Kasparov i Kasparov fes els mateixos moviments tota l’estona, i aquests moviments

el portessin a la victòria, ell continuaria responent de al mateixa manera. Un sistema no està

preparat per detectar‐ho i dir “ep que si faig això tornaré a perdre! Potser que en algun moment

faci alguna variació..”. És a dir, jo diria que li falta aquest component d’aprenentatge.

Bé, pel que fa a la ofensiva, com pot calcular la màquina les ofensives?

Un dels problemes en què es troba la intel∙ligència artificial, no ja només en els escacs sinó en

tota la teoria de jocs, és que necessites força coneixement d’aquell problema que estàs

abordant (en aquest cas coneixement sobre escacs). Escac i mats, moviments... tot el que sigui

possible. Per tant, les estratègies es poden fer però han d’estar com “pre‐programades” . És a

106


dir, s’hauria de tenir tot una variant d’estratègies i tenir‐les més o menys predefinides, en el

sentit de que s’hauria de caracteritzar què vol dir cada tipus de tècnica i en què es tradueix. Per

exemple, si es tradueix en intentar eliminar peons, la funció heurística haurà de donar més pes a

eliminar fitxes del contrari. També, si per exemple apliquem una estratègia més posicional, es

valorarà més el fet de tenir les peces més ben posicionades, etc... Treballant amb la funció

heurística i donant‐li pesos pots fer que tingui més en compte un aspecte o l’altre.

En quant a tot el que és l’evolució i la història, quins són els avanços en els últims anys?

Bé, els últims avanços han anat intentant millorar la funció d’avaluació, la incorporació

d’estratègies, però tampoc sé exactament com amb molta profunditat.

I respecte al principi, en què s’ha millorat? Quines diferències històriques trobem?

Bàsicament als inicis els programes eren pura cerca. Cercar fins a un nivell, expandir l’arbre,

mirar d’avaluar‐lo amb una funció heurística i triar mitjançant el MINIMAX quin és el millor

moviment per a tu. Després tot això es va anar millorant: millorant les funcions d’avaluació,

intentant introduir diferents tipus d’obertures, el concepte d’estratègia, mirar de recordar les

partides o moviments, reutilitzar experiència d’altres partides... en fi, una mica el que ja hem

comentat. L’altra diferència notable que també trobem a nivell de càlcul o computació del

processador és que els primers intents eren en un computador normal amb un sol processador.

És clar, amb això pots fer el que pots fer, estàs limitat de memòria per anar generant els

moviments i també a una velocitat de càlcul determinada, però tot això amb el temps es va

anar solucionant. Per exemple, el Deep Blue ja tenia entre 200 i 250 processadors. Així doncs, un

dels grans avanços a Deep Blue van ser els càlculs en paral∙lel. M’explico. Durant una partida, els

càlculs els generava un processador, però al mateix temps un altre processador paral∙lel estava

generant per a la següent tirada tots els successors i així successivament, podent abastar un

nivell considerable amb un temps bo, component molt important, perquè quan es juga tipus

torneig hi ha la restricció del temps, uns 3 minuts crec. A més a més, els últims que ho estan fent

estan seguint la línea d’utilitzar supercomputadors amb vàries memòries (memòria distribuïda),

per facilitar encara més la rapidesa, podent avaluar més posicions i així poder arribar a més

nivell de profunditat en l’exploració de l’arbre de possibles moviments.

107


Bé, per últim, quant creu que queda per avançar? Fins on arribarem?

Bé, jo crec que on més queda per avançar, no només aquí sinó en molts sistemes de IA és en la

integració de diversos mètodes, en aquest cas d’aprenentatge, per exemple. La capacitat

d’aprenentatge en la gran majoria de programes no hi és. Anar millorant totes les funcions

heurístiques, els conceptes d’estratègies, però sobretot això, incorporar aprenentatge i

integració de tècniques. En el fons existeixen moltes tècniques que podríem integrar, com els

algorismes genètics. També es pot intentar millorar la potència de càlcul.

En resum, és complicat, perquè és clar, en intel∙ligència artificial l’objectiu és molt elevat:

intentar fer sistemes que exhibeixen un comportament que sembla intel∙ligent (gran dilema)!

Però és clar, per demostrar aquesta intel∙ligència s’hauria d’aprendre, raonar, tenir coneixement

sobre el domini (que això de fet més o menys ja o tenen), saber cercar, que això també ho fan, i

forces coses.

Bé, doncs això és tot. Gràcies per l’entrevista.

De res home.

Entrevista a Pedro Meseguer

P: Bon dia senyor Meseguer.

R: Bon dia.

108


Bé, l’objectiu d’aquesta entrevista és “desgranar” el funcionament dels escacs per

computadora i analitzar‐lo. En primer lloc, quin és l’algorisme o el mètode principal que

s’utilitza en IA per als escacs?

Bé, abans hi havia més varietat d’algorismes, avui en dia penso que tothom o gairebé tothom

utilitza l’algorisme alfa‐beta, que no és res més que un MINIMAX on s’ordenen els successors.

Podria desenvolupar una mica el funcionament d’aquest algorisme?

T’ho explicaré amb un model bastant teòric i hipotètic. Imagina’t que poguessis desenvolupar

tot l’arbre de jugades fins a posicions guanyadores o perdedores. Aleshores, s’etiquetarien (amb

un nombre) totes les posicions en referència al últim nivell, i faries una cosa que es fa molt en

intel∙ligència artificial: el back propagate. Aquesta tècnica propaga els costos dels nodes cap dalt

en el arbre, intentant minimitzar els errors el màxim possible.

Suposem que li toca tirar al contrincant. Per tant, un cop etiquetats els nodes, sent “1” les

posicions guanyadores per a tu, i “‐1” les posicions guanyadores per l’oponent, utilitzaríem back

propagation, i propagaríem els mínims d’aquests valors. Un cop el teu torn, faries el mateix

raonament però per a tu. I per a tu, el millor que pots fer és propagar el màxim. Propagaries

aquest valor, en el cas hipotètic del que estem parlant 1, i faries el moviment que li correspon.

Fixa’t que tu sempre estàs fent la suposició que l’oponent farà el millor moviment possible per a

ell, sinó és així l’algorisme perdrà efectivitat. Això que t’acabo desenvolupar en un marc teòric

és el MINIMAX. Tot i això, a la realitat el MINIMAX mai no haurà desenvolupat tot l’arbre i

s’utilitzaran funcions heurístiques.

Existeix alguna millora d’aquest algorisme? Dit d’una altra manera, existeix alguna

especialització?

Sí. El MINIMAX es pot millorar amb el alfa‐beta, que ve a ser el mateix però amb una petita

diferència: l’estalvi d’espai (i temps) innecessari. M’explico. Una vegada que hagis recorregut la

part de l’arbre que correspon, i en haver arribat a un node guanyador o òptim, seria una

tonteria explorar tots els nodes al mateix nivell, ja que tu ja tindràs una posició guanyadora.

Aleshores, el que alfa‐beta farà és el següent: havent utilitzat alguna heurística que t’haurà

ordenat la posició en la qual et trobis abans que una de la dreta (si s’explora d’esquerra a dreta),

109


ja que per això estaràs aquí, no et visitarà cap de les branques paral∙leles una vegada hagis

arribat a aquesta situació.

Això és molt important, degut al que s’anomena el branching factor . El branching factor és el

factor de ramificació, el “factor de brancament”, o dit d’una altra manera, el número de

successors que té un estat. Paral∙lelament, el factor de ramificació efectiu és el número de

successors que tu visites. D’aquesta manera, amb alfa‐beta hauràs reduït el factor de ramificació

efectiu de 36 (de mitjana, un node té 36 possibles successors) a 6. T’estalvies 30 successors!

I pel que fa a les heurístiques, com s’ho fa una funció per avaluar lo òptima que és una tirada,

una posició?

La qüestió, la base de les quals parteixen les funcions d’avaluació, és que tu no pots arribar, o no

arribaràs mai, a les posicions guanyadores o perdedores. És a dir, el teu arbre recorregut

acabarà abans d’arribar a aquestes posicions. Aleshores, és necessari avaluar o intentar avaluar

com de bo o dolent és per tu un estat donat en un moment donat, on no hi ha escac i mat, en

relació a aquestes posicions (guanyadores). Per això s’utilitza una funció d’avaluació. Una funció

d’avaluació molt senzilla és calcular la relació entre la diferència de peces entre tu i l’oponent i

dividir‐ho pel total, però n’ hi ha moltíssimes de molt més sofisticades. De fet, Deep Blue tenia

una funció d’avaluació molt més sofisticada que s’havia amb un grup d’experts en escacs.

Tot i haver superat el Deep Blue, podem dir que la feina no està del tot acabada. Actualment,

quins són els handicaps que pateixen els sistemes?

Bé, el gran handicap dels sistemes actuals d’escacs és la mida de l’arbre, que és una passada. Es

diu que l’espai d’estats és d’una mida de 1040 estats diferents, la qual cosa ja et pots imaginar

que és immanejable.

I com es podrà superar això?

Tot el que sigui millores en la forma de cerca i en la potència del hardware podran ajudar a

arribar a la capacitat humana. El que va passar amb Deep Blue no és un miracle, és que

simplement els computadors avancen i cada vegada hi ha més capacitat de cerca i de potència

de càlcul. Gràcies a aquestes sofisticacions van poder guanyar al campió mundial.

110


Tinc entès que precisament el campió mundial Kasparov va perdre contra el Deep Blue al

sacrificar un peó en una espècie “juguesca”, a la qual la màquina no va caure. Com

aconsegueix la màquina superar aquesta lògica tant fonamental i atacar amb alguna

estratègia, amb alguna enganyifa?

No sé si tu has vist una pel∙lícula que es diu 2001 Odisea en el espacio, però l’has de veure, és

una bona pel∙lícula. En aquesta pel∙lícula, l’ordinador de a bord està jugant a escacs contra un

astronauta, i aquest primer li fa una petita emboscada: en una jugada aparentment tonta posa

la seva reina en perill. Acte seguit, quan l’astronauta veu que es pot menjar la reina del

contrincant hi va com un boig i se la carrega, i l’ordinador amb dues o tres jugades li fa escac i

mat. Això a la realitat no passa, és clar, el que no fan els programes actuals és fer aquestes

emboscades. O sigui, un programa actual amb una cerca molt sofisticada pot escapar de les

teves emboscades, però ell no farà una emboscada perquè hi caiguis tu.

A que és degut això?

Doncs simplement a que el funcionament és així, les màquines cerquen quin és el millor

successor, però no tenen aquest nivell de raonament més estratègic, a diferència d’un jugador

d’escacs professional. Un expert jugarà molt diferent contra un neòfit que si està jugant contra

un professional. A un novici li posarà un “regalet”, i possiblement aquest primer caigui a la

trampa, al professional no.

Bé, aleshores no fan cap emboscada, però sí solucionen les teves. Com?

Això simplement és cercar més. És a dir, si tu fas una emboscada i poses un peó o una reina o el

que sigui és perquè l’altre et mengi aquest peó, però faci una mala jugada i es posi en una mala

posició. Fixa’t que si tu fessis un anàlisi suficientment fi, amb suficient profunditat t’adonaries

que aquesta jugada no és bona. Dit d’una altra manera, si tu cerquessis a suficient profunditat

podries preveure que aquesta jugada significaria que després es menjarien les teves peces i que

les posicions finals serien dolentes per tu. D’aquesta mateixa manera, ell sí que pot escapar

d’emboscades de l’altre, però com ja he dit posar emboscades per sí sol actualment és una cosa

complicada.

111


Quins avanços s’han assolit últimament?

A veure, després de Deep Blue la cosa va quedar bastant parada. Però en el mateix Deep Blue,

cal remarcar el tema de les extensions singulars. Hi ha una cosa que és l’efecte horitzó . La idea

és molt senzilla: com que tu no pots cercar fins al final, has de cercar fins a un llindar. Pot ser

que tu (la màquina) et decideixis per una jugada que al final no sigui la millor, degut al poc abast

de la cerca, però bé, com evitar‐ho, com defensar‐te del efecte horitzó? Un mètode molt

utilitzat és les extensions singulars (singular extensions), que t’especifica en quines situacions

has de cercar una mica més enllà. I bé, això va resultar aportar un gran avanç. De fet, la

profunditat de cerca de Deep Blue no és homogènia, variable, i oscil∙la al voltant dels 6 nivells,

però pot cercar més nivells puntualment, en posicions concretes.

I respecte al principi, quines diferències hi ha?

Moltíssimes. Quasi tot. L’algorisme MINIMAX no sé exactament de quin any és, però abans es

feien coses molt “de força bruta”, molt de dedicar‐se a recórrer tot el conjunt d’estats. Els

escacs van ser des de bon principi un objectiu de la intel∙ligència artificial, perquè és una cosa

molt neta i molt ben controlada, les jugades són molt clares, i a més a més se suposa que els

bons jugadors d’escacs són intel∙ligents. Per aquesta raó, tot això va rebre molta atenció, inclús

massa, fins al punt que van acabar trencant‐se les dents, degut a que als anys 50 i 60 van atacar

el problema amb mètodes massa dèbils, a base de cerca amb força bruta, i això no funciona.

Després podríem dir que ja va venir el MINIMAX i l’alfa‐beta, que permeten estalviar‐se molts

nodes, i amb això de les extensions singulars i l’efecte horitzó ja s’ha pogut focalitzar molt més la

cerca en àrees més prometedores.

I pel que fa a la potència de càlcul, al tema de buscar més ràpid i millor, quina diferència

“numèrica” hi ha des del principi?

Deep Blue podia cercar 200 milions d’estats per segon, la qual cosa és una bestialitat (pensa per

això que 1040 és molt més gran). Pel que fa al principi, no t’ho sé dir, suposo que en algun lloc

estarà comptabilitzat l’increment de la potència de càlcul des dels anys 60 fins ara, però

independentment de la potència, pensa que el factor fonamental d’aquest joc segueix sent la

mida de l’espai de cerca. És tant gran que sinó haguessin avançat els algorismes, amb

l’increment de la potència de càlcul no n’hi hagués hagut prou.

112


Ara potser passa això precisament, que un cop superada la potència, cal avançar molt més en

els algorismes, no?

Mira, aquí segueix havent‐hi dos factors, el factor “CPU”, el hardware, i el factor algorismes. Si

no hi hagués algorismes, amb l’increment de potència de càlcul no n’hi hauria prou. Si no hi

hagués el factor CPU, només amb la millora dels algorismes tampoc n’hi hauria prou. El Deep

Blue que va guanyar al Kasparov va fer‐ho amb un súper‐ordenador darrere de no sé quantes

tones, capaç d’explorar dos‐cents milions de posicions per segon. Amb un PC de sobretaula no

ho podries fer. Jo penso que ara estem en aquesta situació, ara podríem repetir la fita i guanyar

al campió mundial, però això també requeriria dels algorismes actuals. Per tant, podríem dir que

es necessiten les dues coses, que una cosa porta a l’altre.

I per últim, quant creu que queda per avançar?

Buf! Queda tot. Mira, hi ha jocs en els quals el campió mundial és un computador. I hi ha jocs en

que això no passa, tot i que l’ordinador està més o menys a prop. En les dames i l’otello, per

exemple, el campió mundial és un programa: no hi ha cap humà que sigui millor, ningú el podrà

guanyar mai. En els escacs passa el contrari, i el campió mundial segueix sent un home, que es

veu derrotat ocasionalment per un computador. Però el campió mundial segueix sent un humà.

En canvi, en altres jocs, com el go, els ordenadors tenen un mal rendiment. Per això s’especula

que la dificultat, i per tant l’avanç té a veure amb el factor de ramificació. En els escacs és de 36,

en les dames de 4 i en el go de tres‐cents i pico. Per tant, ja veus més o menys quan queda.

I què hi podrem fer amb tot això? Algun dia ho aconseguirem?

Jo crec que sí, que és simplement un tema relacionat amb la millora dels algorismes. El

problema és que la intel∙ligència humana no continua millorant. La gent no pot fer un curset o

posar‐se un microxip al cap, simplement hi ha gent molt intel∙ligent, i d’altres que no tant. Però

si els ordenadors continuen millorant (hardware), i la gent es trenca les banyes en els

algorismes, possiblement podrem arribar a ser campions mundials dels escacs. És important per

això jugar amb la psicologia del oponent, ser capaç de fer un joc perspicaç en el qual si jo et poso

una emboscada tu hi caiguis.

Bé, doncs això és tot, gràcies per l’entrevista.

A tu, home.

113


2. Experimentació amb els escacs Ara que ja hem analitzat, am l’ajuda d’aquests dos experts, el funcionament d’un programa

d’escacs, i les principals diferències històriques que això ha comportat, el segon objectiu

d’aquesta part pràctica és provar‐ho experimentalment, observant si podem notar aquestes

diferències gràcies a alguns canvis que ja hem explicat. Malauradament, les nostres úniques

unitats de mesura són el temps, el nivell, el nombre de tirades i la evolució de la partida. Per

tant, podríem dir que passem d’una analítica qualitativa a quantitativa, teòrica a pràctica.

D’aquesta manera, s’han agafat dues versions d’un mateix programa, i ajustant la potència a un

nivell fix en la versió més primitiva i variant‐la gradualment en la segona versió, s’ha jugat varies

partides. Amb això s’ha intentat veure experimentalment com es tradueix aquesta millora

històrica que ja sabem en què consisteix (observant la diferència de nivells per a cada potència),

al mateix temps que veure què suposa ajustar les diferents opcions (és a dir, a la pràctica variar

els diferents “mecanismes”) d’una mateixa versió.

El programa que he elegit per portar tot això a terme és Fritz, un reconegut entre els experts, de

la casa Chessbase. La versió antiga triada, del 1993, és la número 3 (faran de blanques, i per tant

obriran la partida), mentre que l’altre és la número 12 (negres), de l’any 2009. No disposo de les

característiques internes ni dels algorismes de cada un, degut a la dificultat que això suposaria,

ja que darrera hi ha uns interessos comercials molt forts. Per tant, serà una “investigació”

experimental.

A cada partida s’indica:

NÚMERO DE ª PARTIDA Nivell Fritz 3: % al que hem ajustat el programa

Temps: durada de la partida

Victòria: qui ha guanyat

S’ha rendit: s’ha rendit el programa abans de la derrota? (No s’acceptarà mai una rendició

Nombre de tirades: nombre tirades de les negres

Foto del final de la partida

2Les partides s’han fet manualment, obrint els dos programes i anar modificant a cada respectiu el que l’altre feia.

Foto de la funció

l’avaluació de la posició per a cada tirada

respecte a les blanques

114


L’experimentació ha estat realitzada amb el mateix ordenador, força decent, per tal de que

característiques externes com poden ser la diferència de processador o la lentitud d’aquest

mateix no influeixin. Les característiques són les següents:

La fitxa de les diferents partides és:

3ª PARTIDA Nivell Fritz 3: 48% (Jugador d’oci)

Temps: 8 minuts aprox.

Victòria: negres (Fritz 12)

S’ha rendit: minut 4

Nombre de tirades: 22

2ª PARTIDA Nivell Fritz 3: 43 % (Principiant avançat)





1ª PARTIDA Nivell Fritz 3: 35% (Principiant)





115


7ª PARTIDA Nivell Fritz 3: 62% (Jugador de Club Avançat)



S’ha rendit: minut 7 i mig


6ª PARTIDA Nivell Fritz 3: 60% (Jugador de Club)

Temps: 4 min aprox.


S’ha rendit: ‐


5 ª PARTIDA Nivell Fritz 3: 56% (Jugador Experimentat)

Temps: 10 min aprox




4 ª PARTIDA Nivell Fritz 3: 52% (Jugador Avançat)



S’ha rendit: ‐


116


11ª PARTIDA Nivell Fritz 3: 81% (Mestre internacional)



S’ha rendit: ‐


10ª PARTIDA Nivell Fritz 3: 77% (Mestre)

Temps: 8 minuts aprox


S’ha rendit: ‐


9ª PARTIDA Nivell Fritz 3: 70%(Expert)





8ª PARTIDA Nivell Fritz 3: 66% (Jugador de Torneig)



S’ha rendit: minut 8 i mig


117


Aquí les funcions expressades més amunt en forma d’imatge, per interpolació polinòmica de 6è

grau:

F1(x)=0,0000005x6 ‐ 0,0048x5 + 0,1028x4 ‐ 1,0248x3 + 4,6722x2 ‐ 9,1625x + 6,254

F2(x) = 0,000006x6 + 0,0005x5 ‐ 0,0143x4 + 0,1998x3 ‐ 1,3368x2 + 3,8639x ‐ 3,04

F3(x)= 0,00000006x6 ‐ 0,0006x5 + 0,0156x4 ‐ 0,1966x3 + 1,1503x2 ‐ 2,7214x + 1,9221

F4(x)= 0,0000006x6 ‐ 0,0005x5 + 0,0134x4 ‐ 0,1823x3 + 1,1677x2 ‐ 3,0364x + 2,3505

F5(x)= ‐0’7∙10‐9x6 + 7E‐05x5 ‐ 0,0024x4 + 0,0391x3 ‐ 0,3279x2 + 1,0245x ‐ 0,8174

F6(x)= 0,0005x6 ‐ 0,0017x5 + 0,03x4 ‐ 0,2415x3 + 0,9364x2 ‐ 1,6161x + 0,921

F7(x) = 0,00000008x6 ‐ 8E‐06x5 + 0,0004x4 ‐ 0,0108x3 + 0,1071x2 ‐ 0,4228x + 0,4574

F8(x)= 0’006x6 ‐ 0,0002x5 + 0,0076x4 ‐ 0,1268x3 + 0,9749x2 ‐ 2,9297x + 2,4913

F9(x)= 0,000008x6 ‐ 9E‐06x5 + 0,0005x4 ‐ 0,0147x3 + 0,1951x2 ‐ 1,0526x + 1,4819

F10(x)= 0’05x6 + 0,0013x5 ‐ 0,0285x4 + 0,2849x3 ‐ 1,3607x2 + 2,8116x ‐ 1,8192

F11(x)= 0,6x6 – 0.00000005x5 + 0,002x4 ‐ 0,0237x3 + 0,1357x2 ‐ 0,3079x + 0,1986

13ª PARTIDA Nivell Fritz 3: 100% (Mestre Fritz)


Victòria: blanques (Fritz 3)



12ª PARTIDA Nivell Fritz 3: 91%(Gran Mestre)





118


F12(x)= 0,000010x6 – 0’0007x5 + 0’000005x4 ‐ 0,0024x3 + 0,0423x2 ‐ 0,2789x + 0,5389

F13(x)= 0,0008x6 + 0,00000006x5 ‐ 0,0004x4 + 0,0117x3 ‐ 0,1513x2 + 0,8556x ‐ 1,2684

Les conclusions s’exposen juntament amb les conclusions del final, i seran fetes a base (com

hem dit més amunt) d’analitzar les funcions (no cal derivar‐les ja que ja ho veiem gràficament

l’evolució de la funció i la rapidesa del creixement), el temps, el nombre de tirades, la situació

final i la potència relativa.

3. Conclusions Pel que fa a l’experimentació, tots els indicis lògics apuntaven cap a pensar que l’última versió

(les negres) obtindrien majories absolutes i impressionants, i que el temps augmentaria

proporcionalment (o exponencialment) a la potència relativa, mentre que augmentaven el

nombre de tirades. Tanmateix, la gran conclusió és que no és així, i que aquest joc és tant relatiu

que no podem sinó dubtar del resultat per molt diferents que siguin les versions, sent les

millores de cada versió únicament un factor (dels molts que hi ha) més que ajuda a obtenir la

victòria.

Podem obtindre aquesta conclusió degut al següent:

− Si bé totes les partides d’escacs haurien de tendir a la funció exponencial (quan es

comencen a perdre peces cada cop és pitjor), vegem que això no és així, només en

alguns casos (per exemple en la novena partida) és així.

− Si bé algunes són exponencials, la majoria són indefinides i de funció força variable, la

qual cosa emfatitza la relativitat de les partides

− Havent observat les gràfiques i els respectius coeficients de la funció polinòmica

interpolada, podem concloure que si bé per lògica s’hauria d’augmentar el pendent (o la

“base” de la funció exponencial a la qual tendeix), respecte a les tirades (no al gràfic), de

manera proporcional a la potència, veiem que no és així, i que altre cop, és molt variable

119


− Pel que fa al temps, és de lògica que les partides haurien de durar molt més a mesura

que s’avança en potència, però no és així, ans que en cada partida el temps depèn d’un

factor aleatori.

− La relació temps per cada moviment, associada al creixement de la funció respecte a al

variable independent (tirades), hauria de seguir la mateixa lògica que la funció derivada,

i de la mateixa manera que la segona no ho fa, la primera tampoc.

− Tot això queda plasmat (per tant és com una prova de les causes), en que el campió

mundial va ser derrotat per Kasparov només en algunes partides. Per tant, podem dir

que tant aquí com a Amèrica, la ciència de la IA aplicada als escacs no és definitiva i

absoluta, sinó que, com ja hem dit, és un factor, evidentment que molt influent (però no

indubtable).

I pel que fa a les causes, dedueixo que és degut a:

‐ L’ordre de successors d’una moviment és d’una mitjana de 36, i la de tota la partida és

immens, bilions de bilions de bilions (i més). Per tant, és molt difícil crear un programa

amb la capacitat de recórrer tot l’arbre d’estats.

‐ Això, precisament, és degut, a que tal com hem pogut veure en el primer anàlisis teòric

d’aquest capítol, la IA aplicada als escacs té encara un gran camí per recórrer. I és clar,

falta molt perquè l’ordinador aconsegueixi superar indubtablement a l’home.

‐ En un primer instant, vaig especular sobre la possibilitat d’haver fet massa poc partides

en cada potència. Però després de reflexionar‐ho, crec que no és així, ja que tenint en

compte la gran diferència entre totes les altres dades seria estrany que aquest factor fes

variar els altres. Possiblement si hagués elegit una diversitat de repeticions en comptes

de nivells, hauria pensat que la aleatorietat (que segur que hi seria igualment),

dependria de la poca experimentació en nivells.

Per tant, podem dir com a resum que els escacs no són actualment definitius, sinó que

únicament vénen condicionats per la potència del programa, però també per altres factors com

l’espai d’estats. Simplement queda investigar, fins el dia en que, com en molts altres jocs, la

intel∙ligència artificial s’erigirà guanyadora per sobre de la natural.

120

BLOG IV. CONCLUSIONS

121

IA: Intel∙ligència Artificial CONCLUSIONS

Amb les pàgines ja escrites i amb una perspectiva anacrònica, crec que la primera gran conclusió

és que aquesta recerca no es pot entendre ara sinó com un viatge, un viatge al fons de mi

mateix i un viatge en el món que he estat investigant.

En primer lloc, i com a conclusió podríem dir “interior”, ha estat un esforç molt dur. El canvi de

tutor em va obligar a reestructurar i reenfocar el treball sencer, havent d’esborrar més de 20

pàgines ja escrites. Això, evidentment, em va desmotivar moltíssim, fins al punt que vaig

proposar‐me començar de zero a 3 mesos lluny de l’entrega. Tot i això, me n’he sortit i l’he

acabat amb uns resultats que, almenys per a mi, fan que tot l’esforç hagi valgut la pena. A part,

també estic content de tot el progrés, ja que tot i que amb aquest petit sotrac pel mig, ha estat

un treball progressiu, no de pressa i corrent a última hora. Ha estat llarg però ben repartit i

constant (i molt reflexionat i corregit), tret d’alguns mesos durant el curs que em va ser

impossible de continuar. Un dels altres handicaps amb els que m’he trobat és amb els correus

electrònics: més de 20 no me’ls han contestat. Bé, suposo que ja és normal. Seguint amb

aquesta línea, i no està de menys, vull comentar les coses bones. Tot i que en alguns moments,

ja he dit, ha estat difícil, el què m’animava i el què em segueix animant per sentir‐me a gust amb

la feina feta són dues coses: precisament la gran quantitat d’hores i feina feta que s’ha fet, i el

fet de que almenys, m’ha servit per alguna cosa, per no dir per molt. Ja tinc una petita porta

oberta a aquest món i possiblement això algun dia em serveixi de molt.

Bé, un cop feta aquesta petita valoració personal, toca fer la valoració pròpia de la memòria

escrita. La intel∙ligència artificial està força avançada, tenint en compte que no té ni 60 anys. Tot

i això, queda molt per fer. En alguns casos s’està aconseguint que sembli que les màquines

pensin gairebé com ho fan els humans (top‐down), però no que realment ho facin(bottom‐up). I

crec que això no s’aconseguirà si no és incorporant elements pròpiament humans, de la mà de la

biotecnologia. Existeixen algorismes molt complexos, d’acord, i actualment la IA està molt

ramificada, especialitzada, tecnificada i difusa (difícil de definir‐ne els mètodes amb propietat i

generalitat), però tot i així encara ens trobem, crec, en una fase una mica de assaig‐error‐

modifica. Una fase molt brusca en la qual ens dediquem a trencar‐nos el cap per trobar el

mètode matemàtic més complex per poder arribar a la solució més sofisticada. I és clar, la

nostra intel∙ligència (objectiu final), és molt més homogènia: tot són neurones!

122

IA: Intel∙ligència Artificial CONCLUSIONS

Per tant, i com a conclusió de la conclusió, ens trobem en una fase un pèl diversificada, en la

qual molts dels mètodes explicats en aquest treball no s’utilitzen per a res més que com a

mecanismes d’un gran sistema (això no vol dir que deixin de ser importants), fet que dificulta la

definició d’un mètode propi i universal. I precisament això que ja he comentat, doncs que

actualment la IA és un trenca cocos, encara més que en els inicis, on tothom es dedica a veure

qui la fa més grossa (més intel∙ligent i complicada), una espècie de trenca caps per intentar

entre tots arribar a la solució més completa.

Per últim, també voldria ser una mica temerari. Degut al constant progrés de la tecnologia, i de

la informatització del món, del tecnicisme de la vida, crec que la IA és un dels punts claus del

futur: la humanitat avança cap a la comoditat i la rapidesa, i qui ho farà millor que la

Intel∙ligència Artificial, que emula el millor d’aquest planeta (raça humana), però millorat?

I bé, no sé si per sort o per desgràcia, això és tot.

123

BLOG V. GLOSSARI

124

IA: Intel∙ligència Artificial GLOSSARI

Neurona artificial: Dispositiu electrònic simulador d’una neurona natural.

Domini específic / general: Considerem domini com a extensió de coneixement que engloba

un dispositiu de IA. Serà específic si respon a un àmbit estret (p.ex. resolució d’equacions de segon

grau) i serà general si respon a un àmbit ample (p.ex. problemes de sentit comú del dia a dia).

Xarxa neuronal associativa: Mètode que utilitza la IA consistent en la creació de dispositius

electrònics simulant una neurona, que en el seu conjunt significarien una xarxa neuronal.

Explosió combinatòria: Defecte o handicap d’un sistema degut a la seva extensió. Quan el

espai de cerca (o domini) és molt extens i amb moltes variables, el creixement de la mida de la

cerca per cada variable és exponencial (es produeix explosió combinatòria), del qual se’n deriva la

impossibilitat d’obtenir una resposta en un temps acceptable. Per això, en els casos de E.C. s’utilitza

l’heurística (següent entrada).

Heurística (cerca): Capacitat d’un sistema programat per elegir entre varies opcions a les que

aportin més beneficis. Aquests beneficis seran en relació els criteris preestablerts, generalment o

rapidesa o optimització. Per exemple, un tipus d’heurística seria elegir el camí més ràpid.

Mètodes simbòlics: Mètode de programació consistent en sistemes binaris i símbols.

S’utilitzarà els primers anys per passar després a la lògica i altres formes que representen

“coneixemen”.

Xarxa semàntica: Forma de representació del

coneixement lingüístic en que les idees i la seva

interrelació s’associen mitjançant grafs. S’utilitzen per

a representar mapes conceptuals. Un exemple seria:

Prototip (frame language): És un tipus de codi de programació que conté les regles

metalingüístiques. Serveix perquè el aparell electrònic pugui formular frases pel seu compte

correctament.

Perceptró: És la unitat bàsica d’un tipus de xarxa neuronal, és a dir, és la simulació d’un tipus de

neurona, concretament les d’inferència en forma de discriminador lineal.

125


Algoritme o algoritme genètic: Un algoritme, en el camp de la IA i la informàtica, és una sèrie

de passos predeterminats que segueixen un procés. Parlem doncs d’algoritme genètic o evolutiu

quan aquets passos són els que s’apliquen a un ser o comunitat simulant els passos que seguiria el

curs natural de l’evolució.

Ciborg: Persona amb algun implant electrònic que li permet realitzar alguna funció atrofiada.

Funcions fisiològiques: Cada una de les funcions que realitza qualsevol part del teu cos. Les funcions fisiològiques són vitals, i podrien ser, per exemple, el mastegar de les dents.

Estats de dependència: En el que es troba les persones que no poden realitzar les funcions bàsiques per si soles.

Polarització: Propietat segons la qual algunes molècules, com l’aigua, tenen una diferència de

càrrega (positiu‐negatiu) entre les seves parts (H‐O). En aquest cas, per això, parlem de polarització

entre l’exterior i l’interior.

Neurotransmissor: Substància química de l’interior de les vesícules presinàptiques que conté la

informació que s’ha de transmetre entre neurona i neurona.

Singularitat: Estat en el qual les creacions artificials seran íntegrament equiparables a les

naturals. Cal dir que potser això no consisteixi en crear una ment igual a la natural, sinó a crear‐ne

una amb resultats idèntics.

Comportes lògiques: Camí o procés de transmissió de la informació, comparable a la sinapsis

humana.

Cicle o bucle: Quan un node coincideix amb un altre, és a dir quan mitjançant la expansió hem

arribat a un node ja expandit i ho hem tornat a fer. Per tant, es repeteix la mateixa estructura dos

cops.

Tornar: En aquest cas significa “passar‐li la ordre al programa”, és dir, un cop trobat l’estat meta,

es notifica al programa que ja hem acabat.

126


Punter: En informàtica, simplement indica la situació d’algun element, és a dir, ens indica on està

situat (semblant a un vector matemàtic), per poder accedir‐hi. En aquests casos d’algoritmes de

programació de IA, es pot especificar o no el fet de crear un punter per a cada node, però en el fons

tots els nodes hauran d’estar localitzables.

Exhaustiu: Es parla d’exploració exhaustiva quan aquesta es dedica simplement a explotar sense

cap criteri la recerca de totes les opcions. Això, com és normal, és molt costós i s’associa com a

punt “negatiu”.

Enginyeria inversa: és el tipus d’enginyeria (més aviat el sistema d’enginyeria), que estudia el

model d’elements existents, dels quals en desconeixem el funcionament, per crear‐ne d’altres

iguals amb la tecnologia disponible. Per exemple, el cervell humà serà estudiat mitjançant aquest

mètode per crear‐ne de nous artificials.

Augment o implant cibernètic: Qualsevol afegit artificial al sistema biològic humà, com per

exemple, la substitució dels dos ulls d’un cec per uns d’artificials.

LISP: Familia de llenguatges de programació funcionals d’alt nivell, és a dir, que implementen ja

unes estructures concretes pre‐programades per satisfer uns objectius bastant concrets, com pot

ser qualsevol destinat a la IA (en aquest cas).

Direcció: Una direcció d'un slot és el nom de la entitat representada per tal slot.

In-put: información d’entrada a un sistema.

127

BLOG VI. BIBLIOGRAFIA

128


WEBS

Bruce G. Buchanan : «Timeline: A Brief History of Artificial Intelligence»,

http://www.aaai.org/AITopics/pmwiki/pmwiki.php/AITopics/BriefHistory

Coperland, Jack: «What is AI ?», http://www.alanturing.net/turing_archive/pages/Reference%20Articles/What%20is%20AI.html

Pesquera, Alberto : «aprendizaje», http://www.sindominio.net/~apm/articulos/ia/

« Essays on the use of AI», http://library.thinkquest.org/2705/

«History of artificial intelligence», http://en.wikipedia.org/wiki/History_of_artificial_intelligence

« Inteligencia Artificial», http://www.monografias.com/trabajos16/inteligencia‐artificial‐

historia/inteligencia‐artificial‐historia.shtml

« Inteligencia Artificial», http://html.rincondelvago.com/inteligencia‐artificial_9.html

«Introducción a la Inteligencia Artificial», http://dmi.uib.es/~abasolo/intart/1‐introduccion.html

« Introduction to artificial inteligence», http://www.learnartificialneuralnetworks.com/ai.html

« Machine Learning», http://en.wikipedia.org/wiki/Machine_learning

LLIBRES

Escolano, Francisco; et al. «Inteligencia artificial : modelos, técnicas y áreas de aplicación», Ed.

Thomson, 2003.

Fernández, Serverino ; González, Jesús ; Mira, Jose: «Problemas resueltos de inteligencia artificial

aplicada» , Ed. Addison‐Wesley, 1998

Mira, Jose; Delgado, Ana; «Aspectos básicos de la inteligencia artificial», Ed. Sanz y Torres, 1995

Penrose, Roger: «La nueva mente del emperador», Ed. Biblioteca mondatori, Desembre 1991

Autors varis; «Filosofia i ciutadania, 1er batxillerat», Ed. Edebé, 2008

129


ARXIUS ONLINE

«Inteligencia artificial», Redes, Presentador: Eduard punset, TV2, 2010, de

[http://www.youtube.com/watch?v=sgkW_CpEEcY],

[http://www.youtube.com/watch?v=aDl04aD9xtc&feature=related]

[http://www.youtube.com/watch?v=jmbKvM6ObnE&NR=1] (Format audiovisual)

Arciniegas, Santiago: «Inteligencia artificial: un mito convertido en realidad» de [http://www.scribd.com/doc/13317901/Filosofia‐Inteligencia‐Artificial‐2‐bim10‐Ensayo] (Format pdf)

Borrego, Joaquín : de «Lógica de proposicional» de [http://www.cs.us.es/~joaquin/tema‐02.pdf] (Format pdf)

Díaz, Jorge : «Sistemas basados en reglas» de [http://www.aic.uniovi.es/ssii/SSII‐

SistemasBasadosReglas.pdf] (Format pdf)

Fernández, Carmen, «Representación del conocimiento e inferencia» de [http://www.fdi.ucm.es/profesor/carmen/iaic/Marcos.pdf] (Format pdf)

Glez Peña, Daniel: «Representaciones estructurales» de

[http://creaweb.ei.uvigo.es/creaweb/Asignaturas/ISII/apuntes/Modulo2_Tema4.pdf] (Format pdf)

Gómez, Ferran; Godoy, Jose Mª: «Introducción a la inteligencia artificial», de

[http://www.scribd.com/doc/7290343/Introduccion‐Inteligencia‐Artificial](Format pdf)

Gómez, Antonio: «Inteligencia artificial, aprendizaje y minería de datos» [http://www.gsi.dit.upm.es/~anto/SLIDES/980610/ia_apr_kdd.pdf]

Labra, José Emilio ; Fernández, Daniel: «Lógica de predicados» de

[http://www.di.uniovi.es/~labra/FTP/LPRED.pdf] (Format pdf)

Malagón, Constantino: «Sistemas de producción i búsqueda de soluciones» de

[http://www.nebrija.es/~cmalagon/ia/transparencias/busqueda_general_ia.pdf](Format pdf)

Meseguer, Pedro: «Búsqueda heurística», de [http://www.iiia.csic.es/~pedro/busqueda1‐introduccion.pdf] (Format pdf)

130


Nilson, Nils: «Introduction to Machine Learning», de [http://www.scribd.com/doc/29396070/Introduction‐to‐Machine‐Learning‐Nils‐J‐Nilsson], University of Stanford, 2005] (Format pdf)

Pérez, Jorge: «Redes semánticas» de [http://ing.utalca.cl/~jperez/ia_2_2005/documentos/rsem.pdf]

Ruiz Reina, José Luís: «Introducción a las redes Bayesianas» de [ www.cs.us.es/cursos/ia2‐

2005/temas/tema‐08.pdf] (Format pdf)

Wladimir, Rodríguez: «Lógica de predicados» de [http://ceidis.ula.ve/cursos/pgcomp/IA/semestrea03/IA2003‐07.pdf], (Format pdf)

«Lógica difusa» de [http://www.itnuevolaredo.edu.mx/takeyas/Apuntes/Inteligencia%20Artificial/Apuntes/tareas_alumnos/LD/Fuzzy%20%282005‐Verano%29.pdf] (Format pdf)

MULTIMÈDIA

«¿Y tú qué sabes?», Documental, Director: William Artz, 2004

ARTICLES I CITES

«Neurofisiología», Microsoft® Encarta®, 2006, [DVD]

«Sistema nervioso», Microsoft® Encarta®, 2006, [DVD]

131

Intel·ligència Artificial. Programació

Documents

Transcript of Intel·ligència Artificial. Programació