Entrades amb l'etiqueta ‘ordinadors’

Els algorismes que aprenen

dijous, 9/02/2017

Hi ha paraules boniques que també ens fan una mica de por. Poca gent sap que la seva vida és plena d’algorismes. Alguns, quan se’n adonen, no saben si ho han d’acceptar o s’han de posar nerviosos. I el cert és que, tot i que no els reconeguem i que pensem que no ens afecten, els portem sempre al nostre costat.

Un algorisme no és més que un conjunt ordenat, finit i no ambigu de regles i operacions que permeten resoldre un problema o realitzar una determinada activitat. Els algorismes són descripcions precises de processos que fem o que fan els altres. Les instruccions per muntar un moble a partir d’un kit de peces o el full on expliquem com posar en marxa la calefacció quan marxem de casa i han de venir uns amics, són algorismes. Les receptes de cuina i les partitures musicals són algorismes per preparar menjars i interpretar melodies. I ho són les instruccions de qualsevol joc, els manuals d’usuari i els protocols que segueixen els metges als hospitals. Algunes vegades, els algorismes els podem escriure per a nosaltres mateixos, quan acabem de descobrir alguna cosa complexa que ens ha estat útil (per exemple en el nostre mòbil), i volem no oblidar-la. En altres ocasions, les escrivim per a que algú altre pugui fer més endavant quelcom que nosaltres ja sabem fer. És per això que el conjunt de regles d’un algorisme ha de ser no ambigu: si no l’escrivim bé, la persona que vingui a casa no entendrà com engegar el rentaplats o com posar en marxa la calefacció.

Espero no guanyar-me el mot de “friqui” si confesso que m’agrada la paraula “algorisme”. Tal vegada perquè ha estat al meu costat durant quasi cinquanta anys, i perquè ve de molt lluny. Concretament d’ara fa 1.150 anys, quan al-Khwarazmí treballava a l’observatori de Bagdad. Durant els segles de l’edat mitjana, al-Khwarazmí va ser la principal font de transmissió de coneixements matemàtics de l’Orient a l’Occident, en part en base a les traduccions de textos en grec, llatí i sànscrit que es feien a la Casa de la Saviesa. En el seu tractat d’àlgebra, “Hissab al-jabr wa-l-muqàbala“, explicava regles i receptes (o sigui, algorismes) per repartir herències, cosa que en aquell temps i en el món àrab era molt complicada i requeria fer molts càlculs. En un altre llibre, “Sobre el càlcul amb nombres indis”, llibre del que només se’n conserva una traducció del segle XII, al-Khwarazmí va explicar, sembla que per primera vegada, el sistema de numeració posicional en base 10 (incloent el zero) que va aprendre de l’Índia i que és el que ara utilitzem. Fa més de 11 segles, al-Khwarazmí ens va deixar llibres meravellosos, tots plens d’algorismes. És per això que els algorismes porten el seu nom.

Quan sumem nombres portant-ne, estem aplicant l’algorisme que vam aprendre a l’escola; i, quan multipliquem, també. Euclides ens va deixar un algorisme molt elegant per calcular el màxim comú denominador de dos nombres, i Pitàgores ens va explicar l’algorisme per calcular hipotenuses i distàncies entre punts. Després, amb els ordinadors, hem acabat tenint algorismes per tot. Perquè els ordinadors i els telèfons mòbils només funcionen en base als algorismes que alguns programadors els han preparat. Totes les aplicacions que ens hem baixat als nostres mòbils són algorismes. Tenim algorismes per millorar fotos, per cercar informació a internet, per saber la posició dels astres i per preveure el temps que farà demà. Tenim algorismes que ens troben el nom de les músiques que escoltem, i algorismes que saben traduir textos d’un idioma a un altre.

I ara, el que hem començat a veure fa pocs anys són algorismes que es van refinant amb les dades. Són algorismes que aprenen, algorismes que conformen els mecanismes d’aprenentatge automàtic que es troben en el nucli de l’anomenat “big data“. Hi ha moltíssims exemples, un dels quals, molt il·lustratiu, el teniu en aquest document (que és un pòster científic presentat ara fa uns mesos; com podeu observar, la imatge de dalt és d’aquest mateix document). Es tracta d’un algorisme que, a partir d’una gravació de vídeo de 15 segons en la que s’ens demana que expliquem qui som, fa una valoració de la nostra personalitat en cinc eixos diferents, i ens ho mostra amb 5 bandes verdes (les que veieu a la dreta de la imatge) al cap de menys de tres segons. Aquests cinc eixos són els de la curiositat (gent inventiva i curiosa versus gent cautelosa), escrupolositat (gent eficient i organitzada versus gent descurada i desordenada), extraversió (gent extravertida i energètica versus gent reservada i solitària), agradabilitat (gent amigable i compassiva versus gent poc social) i neuroticisme (gent neuròtica versus gent fiable). Com ho fa? Doncs amb un algorisme que conté dues xarxes neuronals de 17 nivells, una per la senyal de vídeo i l’altra per la d’àudio, amb un darrer nivell de fusió de les dues, com bé podeu veure a la figure 3 del document. Cada un dels 17 nivells d’una i altra xarxa combina adequadament els resultats del nivell anterior i genera una sortida que transmet a algun o alguns dels nivells següents. Cada nivell és com una taula de mescles de so, però digital. Barreja les entrades per tal de produir el senyal de sortida. En resum, fem 17+17+1 mescles, i acabem trobant els trets de personalitat de la persona que ha estat parlant durant 15 segons al vídeo. Però, com fem aquestes mescles? Com ajustem la importància que donarem a cada un dels valors d’entrada a cada una de les mescles? Com ajustem el valor de cada un dels “potenciòmetres” de la nostra xarxa neuronal?. En el cas de l’article que comento, això es va fer amb un sistema d’aprenentatge dirigit. Amb anterioritat als experiments, els autors, amb l’ajut de molts voluntaris, van analitzar deu mil vídeos de 15 segons de YouTube. Cada voluntari, a cada prova, presenciava una parella de vídeos (corresponents a dues persones) i després havia de dir quina de les dues persones creia que era la més curiosa, quina la més extravertida, .. i així fins analitzar el cinquè eix de neuroticisme. Cal observar que no es demanava cap valoració, únicament havien de comparar la parella de persones que estaven veient. Això es va fer així perquè és ben conegut que les comparacions les fem molt millor que les valoracions. Doncs bé, la informació d’aquests experiments amb 10.000 vídeos és la que va permetre ensinistrar els  mescladors dels 17+17+1 nivells de l’algorisme i ajustar els seus valors. Però això no va acabar aquí. L’interessant és que l’algorisme va continuar i continua aprenent, perquè quan el sistema ja estava ajustat i “trained” (mireu la imatge de dalt), l’anàlisi del vídeo de cada nova persona que vol experimentar aquesta aplicació i que dona la corresponent autorització per usar les seves dades, serveix per acabar d’ajustar una mica més els paràmetres de tots els nivells de la xarxa neuronal. El sistema va aprenent cada dia, i cada persona que l’utilitza l’ajuda a fer-ho. Només cal que digui si creu que el resultat que li mostra la màquina reflexa la seva personalitat o no, perquè això és l’únic que necessita la xarxa neuronal per auto-refinar-se.

Per bé o per mal (esperem que per bé), els algorismes que aprenen han arribat, i han vingut per quedar-se amb nosaltres. Ens poden ser molt útils, però no hem de perdre mai de vista la necessitat de la seva regulació ni els aspectes ètics. Els algorismes són aquí, però la responsabilitat sempre serà de les persones que els utilitzen.

Per cert, en Christophe Galfard diu que sense una visió científica, la democràcia es torna més complicada. També diu que la humanitat no és conscient del seu lloc a l’Univers, que només ara ho estem començant a entreveure.

Els invents que perduren: el sistema de numeració posicional

dimecres, 24/04/2013

Deu_Clips.jpg Aquí tenim deu clips. En què s’assemblen els clips i el nombre 10? Reconec que és una pregunta una mica estranya. La meva resposta personal és que quan escrivim el nombre “deu” amb el simbolisme “10” estem utilitzant el sistema de numeració posicional en base deu, que probablement és un dels millors invents que ha produït la humanitat. I el clip (salvant les distàncies) també és un molt bon invent, un bon disseny.

El dissenyador André Ricard Sala diu que els bons dissenys no passen mai de moda. La bellesa en el disseny és el resultat de l’encert d’un bon plantejament funcional, que fa que els seus resultats perdurin. Hem estat testimonis de molts canvis, des de mitjans del segle XX. Però les bicicletes, les tisores i d’altres ginys ben dissenyats no són pas gaire diferents dels dels nostres besavis. I els clips? Els clips van ser patentats per Johan Vaaler l’any 1899, i el mateix any William Middlebrook va patentar una màquina per a fer clips exactament amb la forma que tenen avui. Fa 114 anys. Des d’el 1899 hem vist néixer els avions, la informàtica i els mòbils, però el bon disseny dels clips no ha canviat. Els clips són una mica com el sistema de numeració posicional, són bons invents que perduren.

Tots coneixem el nostre sistema de numeració, i és clar que no us estic descobrint res de nou. Però si us en parlo és perquè jo no deixo de sorprendre’m de la seva elegància. Què passaria si continuéssim utilitzant els números romans? I si haguéssim adoptat el sistema de numeració grec, que tenia símbols específics per a cada desena i centena de manera que cada unitat (1, 2, …9), cada desena (10,20,…90), i cada centena (100, 200, … 900) es representaven amb una lletra diferent de l’alfabet? Si no haguéssim canviat de sistema de numeració, hauríem avançat bastant poc en matemàtiques i no tindríem els ordinadors que ara ens ajuden en els càlculs. I si vam poder canviar no va ser (aquest cop) gràcies als grecs, sinó gràcies als indis i als àrabs. Hem heretat el nostre sistema de numeració dels hindús, i això va ser gràcies a la difusió que en van fer els àrabs. La hipòtesi més acceptada és que la numeració posicional en base 10 va tenir el seu origen a l’Índia, entre el 400 aC i el 400 dC. De fet, entre el món islàmic aquests nombres se’ls coneix com “nombres indis” o “arqam hindiyya” (أرقام هندية). A través de l’Àndalus, el sistema aràbic i l’àbac van entrar a Europa, que encara utilitzava el sistema de numeració romà. Substituir el sistema romà no va ser pas fàcil. La primera menció a Occident apareix al Codex Vigilianus, l’any 976. El 984, Gerbert d’Orlhac va demanar a l’astrònom barceloní Sunifred Llobet la traducció d’un tractat d’astronomia en àrab, el Sententiae Astrolabii, traducció que ja va incloure el sistema de numeració hindú/aràbic. Anys després, el matemàtic italià Fibonacci va contribuir a la difusió del sistema per Europa, gràcies a la seva obra Liber Abaci que va publicar l’any 1202. Per cert, podríeu sumar CCCXIX i DCCIV en notació romana?

Com sabem, el sistema de numeració posicional en base deu pot representar qualsevol nombre, sigui gran o petit, amb només deu símbols: els símbols 1… 9 que representen els nou primers nombres naturals, i el zero. El truc rau en la posició d’aquests símbols. Un “3” al lloc de les unitats és un “3”, però un “3” al lloc de les desenes té molt més valor: són tres desenes. La posició dels símbols indica la seva importància. Quan llegim 324 sabem que estem parlant del valor 3*100+2*10+4. El bonic d’aquesta notació posicional és que assigna valor segons el lloc, i que permet fer operacions aritmètiques tot passant l’excés de les unitats a les desenes i així successivament. Els algorismes per a fer operacions aritmètiques són tan senzills que els aprenem a l’escola i que els podem programar en els nostres ordinadors. Podem representar quantitats petites com el 2, o quantitats gegants de milers de trilions com el 7001002003004005006007. Ara bé, si tot plegat ho fem en base deu i amb deu símbols és perquè tenim deu dits. Per indicar els deu clips de la foto en un sistema posicional en base vuit hauríem d’escriure “12”, perquè deu és 1*8+2 . Si volguéssim indicar els mateixos clips en base tres hauríem d’escriure “101” perquè deu és 1*(3*3)+0*3+1 . I en base 2 tindríem 1010 perquè deu és 1*(2*2*2)+0*(2*2)+1*2+0 (fixeu-vos que utilitzo els noms per indicar quantitats de manera no ambigua, però que els símbols de les xifres en cada cas tenen un significat diferent). Els ordinadors treballen en base dos, de manera idèntica i amb els mateixos algorismes aritmètics que nosaltres utilitzem quan fem operacions aritmètiques en base deu. Sabríeu sumar 1010 i 111, en base dos?  Què opineu d’aquest acudit: “només hi ha 10 tipus de persones: els que entenen el sistema posicional en base dos i els que no”? (és un acudit de matemàtics i informàtics friquis…)

Us heu preguntat alguna vegada com serà el món d’aquí a uns segles i què és el que haurà sobreviscut? Els nostres besnéts gaudiran segurament dels nostres bons dissenys i dels invents perdurables. Segur que no tindran ni cotxes ni ordinadors com els nostres. Però crec que ens podem atrevir a afirmar que utilitzaran tisores, clips i bicicletes, i que continuaran calculant amb l’actual sistema de numeració posicional.

Com és que Google ens ho troba tot?

dilluns, 16/07/2012

Diccionari.jpg Bé, tal vegada no ens ho troba tot, però segurament estareu d’acord amb mi en que, des de fa uns anys, Google ens ajuda força, no?

Us heu preguntat algun cop com és que Google ens troba el que cerquem, i a més ens ho troba ràpid?

No és pas perquè tingui grans ordinadors als seus centres de dades. De fet, i en contra d’algunes noticies que han aparegut darrerament, Google gasta molt poca energia en cada una de les cerques que fem. Una d’aquestes cerques necessita unes tres deumil·lèsimes de kilowatt hora.

En informàtica, com en d’altres camps, la força bruta per si sola, el hardware, no és suficient. Cal pensar i trobar maneres de resoldre els problemes amb menys esforç. Ja diuen que “val més enginy que força”. Google ens ho troba tot (o quasi tot) gràcies als seus algorismes de cerca. Els algorismes són receptes, són conjunts ben definits d’instruccions que permeten resoldre problemes mitjançant passos succesius que no han de generar dubtes a qui els ha de realitzar (sigui una persona o una màquina). Un mateix problema el podem resoldre, en un mateix ordinador, amb diferents algorismes. Alguns seran ràpids, d’altres no tant. Els algorismes de Google són altament sofisticats. Molts d’ells es guarden en secret, com els secrets que guarden alguns pastissers i artesans. Els algorismes són el “cervell” dels nostres ordinadors. Així com les abelles “saben” construir cel·les hexagonals en els seus ruscs, els ordinadors de Google “saben” fer cerques de manera ràpida i eficient. L’evolució ha programat el cervell de les abelles, però nosaltres som els que hem de programar els algorismes dels nostres ordinadors.

Per a poder ser eficients en una cerca, cal haver ordenat la informació. Això és el que sempre hem fet, en els diccionaris. Imaginem un cas molt senzill, i suposem que tenim un diccionari (no electrònic, sinó en paper!) només amb setze fulls. Quan volem cercar una paraula, l’obrim pel mig. Ens poden passar dues coses. O bé trobem la paraula just a les pàgines per les que hem obert el diccionari, o no. En el primer cas, fem la consulta i ja hem acabat. Quan no trobem la paraula, és quan fem servir la propietat que el diccionari està ordenat: immediatament sabem si l’hem de cercar a la meitat de l’esquerra, o a les pàgines de la meitat de la dreta. Repetim el procés i tornem a obrir pel mig, però només amb el trosset de vuit fulls on sabem que podem trobar la paraula. És fàcil veure que la tercera vegada farem la cerca en quatre fulls, i que al final trobarem la paraula havent obert no més de cinc vegades el diccionari. Aquest esquema de cerca és el que ens porta als algorismes de cerca dicotòmica i als arbres binaris de cerca que actualment utilitzem en els nostres ordinadors. Aquests algorismes tenen complexitat logarítmica: cada cop que dupliquem el volum de les nostres dades, només hem de fer un pas més de cerca. De la mateixa manera que ens cal un màxim de cinc passos per trobar paraules en un diccionari de setze pàgines, ens caldran sis passos per un diccionari de 32 pàgines. Tot és degut a que, en cada pas, descartem la meitat del diccionari. Repetint el raonament diverses vegades en sentit ascendent, veureu que cal un màxim de 11 passos en un diccionari de 1024 pàgines, o un màxim de 33 passos en un diccionari de 4294 milions de pàgines.  I podeu continuar, afegint un pas cada cop que dobleu la mida del diccionari.

No és sorprenent? Si tenim la informació ben ordenada, podrem localitzar qualsevol informació en un diccionari amb 17 mil milions de termes, només amb un màxim de 35 passos. És com trobar agulles en pallers. El secret està en l’ordenació. Recordeu les guies telefòniques? Algunes estaven ordenades alfabèticament, d’altres per adreces. Eren molt útils, però no permetien trobar persones a partir del seu número de telèfon, perquè no estaven ordenades per telèfons.

Els algorismes dels cercadors com Google treballen en diverses fases. Els seus servidors construeixen i mantenen actualitzats els fitxers d’índexs, els ordenen, fan les cerques que els demanem i finalment reuneixen i organitzen la informació i ens la presenten. La construcció, manteniment i ordenació dels fitxers d’índexs és una feina que es va fent contínuament, tant si la gent demana cerques com si no. Aquests algorismes preparen i entrenen els cercadors. És com els esportistes: s’han de preparar bé, per poder després ser eficients en el moment de la cursa dels cent metres. Per a la creació i actualització dels fitxers d’índexs, els ordinadors analitzen periòdicament totes les pàgines web del món i “les inverteixen”. A cada pàgina web se li assigna un nombre, un codi. I els fitxers d’índexs no són més que diccionaris: per a cada paraula trobada en alguna pàgina, es crea una nova entrada al diccionari que conté (enlloc de la seva definició) la llista de tots els codis de pàgines on s’ha trobat aquesta paraula. Un cop ordenats, els fitxers d’índexs, immensos, estan ja preparats per acceptar cerques i peticions de tots nosaltres (aquests diccionaris són tan grans perquè han d’incloure paraules de molts idiomes i fins i tot informacions numèriques com telèfons i codis postals). Saber ordenar és essencial, en informàtica. Per això els anomenem ordinadors, a les màquines que executen els nostres algorismes…

Després, quan volem fer una cerca, no cal pas gaire potència de càlcul. Tal com ja hem vist, podem cercar en fitxers d’índexs ordenats i, donada una paraula, podem trobar la llista de pàgines web que la contenen, en molts pocs passos. Un cop feta la cerca cal, però, resumir la informació i organitzar-la per a la seva presentació final a l’usuari. Quan la cerca la fem tot indicant diverses paraules, cal intersecar les llistes parcials de pàgines i trobar el conjunt de pàgines que contenen totes les nostres paraules. I finalment, si el resultat són uns quants milers de pàgines, cal prioritzar i decidir quines són les pàgines que mostrarem en primer lloc i a dalt de tot. Alguns aspectes d’aquests algorismes de priorització són  secrets ben guardats, a Google.

Google és el resultat de la tesi doctoral de Larry Page i Sergey Brin, l’any 1998 a Stanford. Aquí teniu l’article que van escriure, el mateix any 1998, descrivint els seus algorismes. Un cop més, veiem la importància que pot tenir la investigació en la creació de noves empreses exitoses.

La paraula algorisme prové de Al-Jwārizm, matemàtic persa que va estudiar i treballar a Bagdad a principis del segle IX. A la seva obra “Algoritmi de numero Indorum” (que només coneixem per una versió llatina del segle XII) descriu el sistema indi de numeració posicional en base 10, utilitza el cero com a indicador posicional i proposa diferents algorismes de càlcul aritmètic.