intel·ligència artificial. programació
TRANSCRIPT
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
IA: Intel∙ligència Artificial ÍNDEX
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
IA: Intel∙ligència Artificial ÍNDEX
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...........................................................................................................
p.043 p.043 p.044 p.044 p.045 p.045 p.045 p.046 p.048 p.049 p.049 p.049 p.050 p.051 p.052 p.053 p.053 p.054 p.054 p.055 p.055 p.055 p.056 p.056 p.057 p.058 p.059 p.059 p.060 p.061 p.062 p.062 p.063 p.064 p.065 p.065 p.066 p.067
IA: Intel∙ligència Artificial ÍNDEX
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......................................................................................................................
p.067 p.067 p.069 p.069 p.069 p.070 p.070 p.071 p.072 p.072 p.072 p.072 p.073 p.075 p.075 p.075 p.075 p.077 p.077 p.078 p.078 p.079 p.080 p.081 p.082 p.082 p.082 p.082 p.083 p.083 p.085 p.085 p.085 p.086 p.087 p.087 p.088 p.088
IA: Intel∙ligència Artificial ÍNDEX
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
IA: Intel∙ligència Artificial I. CONCEPTES BÀSICS
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
IA: Intel∙ligència Artificial I. CONCEPTES BÀSICS
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
IA: Intel∙ligència Artificial I. CONCEPTES BÀSICS
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
IA: Intel∙ligència Artificial I. CONCEPTES BÀSICS
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
IA: Intel∙ligència Artificial I. CONCEPTES BÀSICS
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
IA: Intel∙ligència Artificial I. CONCEPTES BÀSICS
‐ 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
IA: Intel∙ligència Artificial I. CONCEPTES BÀSICS
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
IA: Intel∙ligència Artificial I. CONCEPTES BÀSICS
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
IA: Intel∙ligència Artificial I. CONCEPTES BÀSICS
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
IA: Intel∙ligència Artificial I. CONCEPTES BÀSICS
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
IA: Intel∙ligència Artificial II. PROGRAMACIÓ DE LA INTEL∙LIGÈNCIA: CRITERIS GENERALS
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
IA: Intel∙ligència Artificial II. PROGRAMACIÓ DE LA INTEL∙LIGÈNCIA: CRITERIS GENERALS
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
IA: Intel∙ligència Artificial III.RECERCA SENSE INFORMACIÓ DEL DOMINI
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
IA: Intel∙ligència Artificial III.RECERCA SENSE INFORMACIÓ DEL DOMINI
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
IA: Intel∙ligència Artificial III.RECERCA SENSE INFORMACIÓ DEL DOMINI
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
IA: Intel∙ligència Artificial III.RECERCA SENSE INFORMACIÓ DEL DOMINI
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
IA: Intel∙ligència Artificial III.RECERCA SENSE INFORMACIÓ DEL DOMINI
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:
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 o es trobi una meta realitzar les següents accions:
2.1. Extreure el primer node d'ABIERTA, i anomenar‐lo m.
27
IA: Intel∙ligència Artificial III.RECERCA SENSE INFORMACIÓ DEL DOMINI
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
IA: Intel∙ligència Artificial III.RECERCA SENSE INFORMACIÓ DEL DOMINI
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:
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 o es trobi una meta realitzar les següents accions:
2.1. Extreure el primer node d'ABIERTA, i anomenar‐lo m.
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
IA: Intel∙ligència Artificial III.RECERCA SENSE INFORMACIÓ DEL DOMINI
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
IA: Intel∙ligència Artificial III.RECERCA SENSE INFORMACIÓ DEL DOMINI
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
IA: Intel∙ligència Artificial III.RECERCA SENSE INFORMACIÓ DEL DOMINI
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
IA: Intel∙ligència Artificial III.RECERCA SENSE INFORMACIÓ DEL DOMINI
− 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
IA: Intel∙ligència Artificial IV. RECERCA HEURÍSTICA
− 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
IA: Intel∙ligència Artificial IV. RECERCA HEURÍSTICA
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
IA: Intel∙ligència Artificial IV. RECERCA HEURÍSTICA
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
IA: Intel∙ligència Artificial IV. RECERCA HEURÍSTICA
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
IA: Intel∙ligència Artificial IV. RECERCA HEURÍSTICA
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
IA: Intel∙ligència Artificial IV. RECERCA HEURÍSTICA
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
IA: Intel∙ligència Artificial IV. RECERCA HEURÍSTICA
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
IA: Intel∙ligència Artificial IV. RECERCA HEURÍSTICA
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
IA: Intel∙ligència Artificial IV. RECERCA HEURÍSTICA
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
IA: Intel∙ligència Artificial V. LÒGICA
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
IA: Intel∙ligència Artificial V. LÒGICA
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
IA: Intel∙ligència Artificial V. LÒGICA
∨: 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
IA: Intel∙ligència Artificial V. LÒGICA
− 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
IA: Intel∙ligència Artificial V. LÒGICA
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
IA: Intel∙ligència Artificial V. LÒGICA
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
IA: Intel∙ligència Artificial V. LÒGICA
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
IA: Intel∙ligència Artificial V. LÒGICA
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
IA: Intel∙ligència Artificial V. LÒGICA
∀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
IA: Intel∙ligència Artificial V. LÒGICA
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
IA: Intel∙ligència Artificial V. LÒGICA
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
IA: Intel∙ligència Artificial V. LÒGICA
− 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
IA: Intel∙ligència Artificial V. LÒGICA
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
IA: Intel∙ligència Artificial VI. REGLES
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
IA: Intel∙ligència Artificial VI. REGLES
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
IA: Intel∙ligència Artificial VI. REGLES
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
IA: Intel∙ligència Artificial VI. REGLES
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
IA: Intel∙ligència Artificial VI. REGLES
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
IA: Intel∙ligència Artificial VI. REGLES
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
IA: Intel∙ligència Artificial VII. XARXES ASSOCIATIVES
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
IA: Intel∙ligència Artificial VII. XARXES ASSOCIATIVES
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
IA: Intel∙ligència Artificial VII. XARXES ASSOCIATIVES
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
IA: Intel∙ligència Artificial VII. XARXES ASSOCIATIVES
− 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
IA: Intel∙ligència Artificial VII. XARXES ASSOCIATIVES
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
IA: Intel∙ligència Artificial VII. XARXES ASSOCIATIVES
− : 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
IA: Intel∙ligència Artificial VII. XARXES ASSOCIATIVES
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
IA: Intel∙ligència Artificial VII. XARXES ASSOCIATIVES
− 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
IA: Intel∙ligència Artificial VII. XARXES ASSOCIATIVES
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
IA: Intel∙ligència Artificial VII. XARXES ASSOCIATIVES
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
IA: Intel∙ligència Artificial VIII. MARCS I GUIONS
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
IA: Intel∙ligència Artificial VIII. MARCS I GUIONS
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
IA: Intel∙ligència Artificial VIII. MARCS I GUIONS
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
IA: Intel∙ligència Artificial VIII. MARCS I GUIONS
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
IA: Intel∙ligència Artificial VIII. MARCS I GUIONS
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
IA: Intel∙ligència Artificial VIII. MARCS I GUIONS
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
IA: Intel∙ligència Artificial IX. INTEGRACIÓ
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
IA: Intel∙ligència Artificial IX. INTEGRACIÓ
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
IA: Intel∙ligència Artificial IX. INTEGRACIÓ
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
IA: Intel∙ligència Artificial IX. INTEGRACIÓ
− 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
IA: Intel∙ligència Artificial IX. INTEGRACIÓ
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
IA: Intel∙ligència Artificial IX. INTEGRACIÓ
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
IA: Intel∙ligència Artificial X. APRENENTATGE
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
IA: Intel∙ligència Artificial X. APRENENTATGE
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
IA: Intel∙ligència Artificial X. APRENENTATGE
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
IA: Intel∙ligència Artificial X. APRENENTATGE
− 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
IA: Intel∙ligència Artificial ELS ESCACS: PART PRÀCTICA
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
IA: Intel∙ligència Artificial ELS ESCACS: PART PRÀCTICA
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
IA: Intel∙ligència Artificial ELS ESCACS: PART PRÀCTICA
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
IA: Intel∙ligència Artificial ELS ESCACS: PART PRÀCTICA
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
IA: Intel∙ligència Artificial ELS ESCACS: PART PRÀCTICA
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
IA: Intel∙ligència Artificial ELS ESCACS: PART PRÀCTICA
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
IA: Intel∙ligència Artificial ELS ESCACS: PART PRÀCTICA
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
IA: Intel∙ligència Artificial ELS ESCACS: PART PRÀCTICA
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
IA: Intel∙ligència Artificial ELS ESCACS: PART PRÀCTICA
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
IA: Intel∙ligència Artificial ELS ESCACS: PART PRÀCTICA
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
IA: Intel∙ligència Artificial ELS ESCACS: PART PRÀCTICA
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)
Temps: 5 minuts aprox.
Victòria: negres (Fritz 12)
S’ha rendit: minut 2
Nombre de tirades: 27
1ª PARTIDA Nivell Fritz 3: 35% (Principiant)
Temps: 5 minuts aprox.
Victòria: negres (Fritz 12)
S’ha rendit: minut 2
Nombre de tirades: 18
115
IA: Intel∙ligència Artificial ELS ESCACS: PART PRÀCTICA
7ª PARTIDA Nivell Fritz 3: 62% (Jugador de Club Avançat)
Temps: 12 minuts aprox.
Victòria: negres (Fritz 12)
S’ha rendit: minut 7 i mig
Nombre de tirades: 42
6ª PARTIDA Nivell Fritz 3: 60% (Jugador de Club)
Temps: 4 min aprox.
Victòria: negres (Fritz 12)
S’ha rendit: ‐
Nombre de tirades: 16
5 ª PARTIDA Nivell Fritz 3: 56% (Jugador Experimentat)
Temps: 10 min aprox
Victòria: negres (Fritz 12)
S’ha rendit: minut 9
Nombre de tirades: 30
4 ª PARTIDA Nivell Fritz 3: 52% (Jugador Avançat)
Temps: 7 minuts aprox.
Victòria: negres (Fritz 12)
S’ha rendit: ‐
Nombre de tirades: 23
116
IA: Intel∙ligència Artificial ELS ESCACS: PART PRÀCTICA
11ª PARTIDA Nivell Fritz 3: 81% (Mestre internacional)
Temps: 7 minuts aprox.
Victòria: negres (Fritz 12)
S’ha rendit: ‐
Nombre de tirades: 25
10ª PARTIDA Nivell Fritz 3: 77% (Mestre)
Temps: 8 minuts aprox
Victòria: negres (Fritz 12)
S’ha rendit: ‐
Nombre de tirades: 18
9ª PARTIDA Nivell Fritz 3: 70%(Expert)
Temps: 17 minuts aprox.
Victòria: negres (Fritz 12)
S’ha rendit: minut 15
Nombre de tirades: 58
8ª PARTIDA Nivell Fritz 3: 66% (Jugador de Torneig)
Temps: 13 minuts aprox.
Victòria: negres (Fritz 12)
S’ha rendit: minut 8 i mig
Nombre de tirades: 28
117
IA: Intel∙ligència Artificial ELS ESCACS: PART PRÀCTICA
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)
Temps: 25 minuts aprox.
Victòria: blanques (Fritz 3)
S’ha rendit: minut 19
Nombre de tirades: 57
12ª PARTIDA Nivell Fritz 3: 91%(Gran Mestre)
Temps: 24 minuts aprox.
Victòria: negres (Fritz 12)
S’ha rendit: minut 19
Nombre de tirades: 72
118
IA: Intel∙ligència Artificial ELS ESCACS: PART PRÀCTICA
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
IA: Intel∙ligència Artificial ELS ESCACS: PART PRÀCTICA
− 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
IA: Intel∙ligència Artificial GLOSSARI
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
IA: Intel∙ligència Artificial GLOSSARI
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
IA: Intel∙ligència Artificial ÍNDEX
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
IA: Intel∙ligència Artificial ÍNDEX
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
IA: Intel∙ligència Artificial ÍNDEX
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