Entrades amb l'etiqueta ‘algorismes’

Les mostres aleatòries i el consens

dijous, 19/10/2017

La imatge mostra un petit tros del conjunt de punts que obtenim amb un sistema d’escaneig de tipus LIDAR quan estem capturant i reconstruint una zona urbana. El sistema detecta, genera i ens dona milions de punts a l’espai, cada un d’ells amb les seves coordenades (x,y,z) i el seu color. El que veiem aquí a l’esquerra no és més que una munió de punts 3D (una mena de núvol), que podem analitzar i visualitzar interactivament. Mireu, per exemple, aquest vídeo o bé aquest altre. Els punts d’aquests núvols, però, són aproximats, perquè els sistemes d’escaneig, com tots els sensors, malauradament introdueixen errors. Errors que es fan més grans a mesura que els edificis que volem capturar, com el de la imatge, són més lluny.

Pensem ara en el problema de detectar, de la manera més exacta possible, la façana dels edificis. Només sabem que habitualment, les façanes són planes i verticals. Com la podem reconèixer i detectar, si només tenim punts i tots ells són aproximats? Què hem de fer per eliminar i no considerar tots aquells punts “atípics” (anomenats outliers en anglès) que poden emmascarar el resultat, com per exemple els punts de les fulles dels arbres que són propers a les façanes?

Sortosament, tenim una solució. L’algorisme RANSAC, proposat l’any 1981 per Martin Fischler i Robert Bolles, ens pot resoldre el problema. És un algorisme que cerca el consens a partir de mostres aleatòries. Podem tenir milers o milions de punts, això no importa massa. N’escollim N (per exemple, 50) a l’atzar. Fem la hipòtesi que aquests N punts són de la façana que volem detectar, i calculem un pla vertical F que els aproximi. Això no ha de ser difícil, perquè podem utilitzar tècniques de regressió i perquè només estem utilitzant un conjunt reduït de N punts. I ara ve el pas important: analitzem quin consens té aquest pla F entre tots els altres punts. Això tampoc és complicat. Només necessitem una tolerància que anomenaré T (per exemple, un centímetre). Llavors, per cada un de tots els altres punts del núvol, mirem si la seva distància al pla F és o no més petita que T. Si és més petita, és que aquest punt “accepta” el pla F. A final, acabem tenint una mesura del grau de consens que genera aquest pla F, en base al percentatge de punts que l’accepten. La resta de punts, en canvi, són atípics (outliers) en relació a F. fet això, en aquest moment ja hem aconseguit tenir una primera estimació de la façana. Però ara, l’algorisme RANSAC repeteix tot el procés amb uns altres N punts a l’atzar, troba un nou pla F’, compara el grau de consens de F i F’, i es queda amb el que en té més. I això ho va repetint una i altra vegada, comparant cada vegada el consens del nou pla amb el millor consens de tots els anteriors, fins que decidim que l’aproximació de la solució ja és prou bona.

L’algorisme RANSAC és no determinista, perquè les mostres són aleatòries. A més, només és segur que ens trobarà la millor solució possible si no tenim pressa i el deixem que vagi provant anys i anys. Si, en canvi, l’aturem en un cert moment, només podem afirmar que la solució serà correcta amb una certa probabilitat. En tot cas, l’experiència demostra que en general acaba donant molt bons resultats i separant les dades útils (inliers) de les atípiques (outliers) en un temps raonable. Un cop separats, podem eliminar aquests punts atípics i quedar-nos amb els punts que ens determinen bé la façana, perquè RANSAC ens ha detectat tot allò que ens pertorbava la solució del problema.

Els humans, de fet, no som tan lluny d’aquest consens de mostres aleatòries. Si fem l’exercici de substituir núvols de punts per grups socials i rellegim els paràgrafs de dalt pensant en persones en lloc de punts, l’algorisme RANSAC segurament ens recordarà el nostre comportament quan escollim comissions, votem representants, o bé discutim projectes urbanístics o d’altre tipus que les administracions exposen públicament. En tots els casos, l’objectiu és obtenir el màxim de consens de la resta de la societat. La única diferència amb l’algorisme RANSAC és que nosaltres aviat ens cansem, mentre que ell no. No és fàcil, això de canviar la mostra. Costa canviar i fer refer projectes, costa renovar comissions i revocar representants per tal de millorar el consens. És així. És la condició humana. Per bé i per mal, no som màquines.

———
Per cert, en David Fernàndez diu que segurament, l’única contrarevolució en marxa avui és l’ofensiva autoritària, devastadora i neoliberal que recorre el planeta. Replegaments de la por i una estranya retrotopia, diu, quan en difícils temps de crisi l’extrema ambigüitat de la condició humana es dirimeix sempre, antagònicament, entre la brutalitat i la cooperació.

Evolució i robustesa

divendres, 21/04/2017

Robustesa, en informàtica, és sinònim de tolerància als problemes i als errors. Un sistema  o algorisme robust ha de poder seguir treballant en condicions satisfactòries en presència d’errades. No importa que aquestes siguin degudes a un mal-funcionament del hardware o a que la persona que està entrant les dades s’hagi equivocat. El sistema, si no pot seguir endavant, ha d’avisar i demanar, per exemple, que hem de tornar a entrar part de les dades; però no es pot col·lapsar. Algun dia, quan els nostres ordinadors arribin de veritat a l’edat adulta de la robustesa, ja no farem els ben coneguts acudits informàtics que parlen d’apagar i tornar a engegar.

Però no cal fixar-nos en els algorismes, perquè la gran mestra en robustesa és la natura. Ho han vist, per exemple, un grup d’investigadors d’Alemanya, Mèxic, Anglaterra i la Xina, que han investigat els peixos de tipus poecílid a les aigües sulfuroses del riu El Azufre, a Tapijulapa (Mèxic). Aquest riu, que podeu veure a la imatge de dalt (imatge que he obtingut d’aquesta pàgina web) és d’aigua tòxica, amb una concentració de sulfur d’hidrogen (també anomenat àcid sulfhídric) que fa impossible la vida de quasi tots els vertebrats. Aquest grup de científics ha publicat un treball que podeu trobar aquí, on analitzen l’evolució d’aquesta família de peixos. Rüdiger Riesch i Martin Plath, que també en parlen a un article a la revista Scientific American, expliquen que van trobar diversos tipus de peixos de la mateixa família, tots ells descendents d’antics poecílids que vivien en aigües clares i netes. Aquests diferents grups de peixos han anat evolucionant de manera independent a partir d’un avantpassat comú que va existir fa uns 600 mil anys, perquè s’han hagut d’anat adaptant a viure en entorns tòxics incomunicats i separats bastants quilòmetres l’un de l’altre. En total, han estat analitzant vuit grups diferents de peixos poecílids, tots ells lleugerament diferents i que viuen en diferents paratges. D’aquests vuit grups, quatre viuen en aigües clares i quatre es troben en entorns molt tòxics amb àcid sulfhídric. Aquests darrers, encara que han hagut d’evolucionar de manera independent, tenen unes característiques anatòmiques i metabòliques molt similars, amb boques i caps més grans, que els ajuden a viure en condicions inhòspites. Ara bé, el sorprenent és que, tot i que són prou semblants (ho podeu veure en aquesta foto, que també és del Scientífic American), tenen genomes molt i molt diferents: els canvis genòmics en un determinat grup, molt importants i distribuïts per tot l’ADN, tendeixen a ser únics per aquest grup i a no ser compartits pels altres grups. En canvi, el resultat, en termes de camins metabòlics (el conjunt de reaccions químiques que fan possible la vida), és el mateix en tots ells. En altres paraules: els camins evolutius, independents, han estat diferents, però el resultat és molt semblant perquè és el que acaba possibilitant l’adaptació a entorns agressius. Calia adaptar-se, i ho van fer, d’una o altra manera. És la robustesa de l’evolució: encara que hi ha molts camins, veiem resultats similars perquè els que no es van adaptar, ja no hi són. Els autors diuen a més que els seus resultats corroboren les hipòtesis de Jay Gould en el sentit que l’evolució és sovint el resultat irrepetible d’esdeveniments estocàstics que tenen efectes altament contingents, però que acaben adaptant-se a l’entorn gràcies a la selecció natural.

I no només els peixos. Els diferents grups d’humans, com explica en D.T. Max en un recent article a la revista National Geographic, hem anat evolucionant de manera independent per adaptar-nos al medi, amb solucions ben satisfactòries en tots els casos. Els inuit tenen gens que els permeten metabolitzar el greix de les balenes, i els japonesos, uns altres per digerir les algues marines. Les civilitzacions ramaderes són més tolerants a la lactosa, mentre que la pell dels africans els protegeix de les radiacions ultraviolades. Solucions ben diferents, totes robustes, que ens adapten a tots els indrets de la Terra. Som molt iguals i ben diferents…

De fet, la ciència mateixa, amb el rigor en els experiments i amb els seus mecanismes de revisió anònima dels resultats abans de publicar-se, treballa de manera semblant i intenta maximitzar la seva robustesa. Molts dirigents, però, la ignoren. Prefereixen crear mons paral·lels i realitats alternatives, objectivament falses però que són útils per als seus interessos. Per això, molts científics han dit que ja n’hi ha prou i organitzen, demà, la marxa per la ciència. Els convocants diuen que la ciència, els científics i la política basada en l’evidència científica estan sent atacades, i que les retallades, la censura, la desaparició de les dades i les amenaces de desmantellar les agències governamentals ens amenacen a tots i posen en risc la salut, el menjar, l’aire, l’aigua, el clima i fins i tot el treball. No som en un moment fàcil, però som coherents amb l’actitud de tolerància als problemes, i pensem que ens en sortirem.

———

Per cert, en John Carlin diu que en castellà no existeix cap traducció de la paraula anglesa “compromise”, concepte que vol dir que tots dos costats cedeixen en una negociació per tal que tots surtin guanyant. Parla també de Jonathan Powell, que comenta que a més, hi ha una paraula nostra que tampoc té traducció a l’anglès: “crispació”. Perquè l’esport espanyol preferit, diu Carlin, és la indignació, que concedeix una rica sensació de superioritat moral sobre l’altre.

Arbres i cròniques

dijous, 14/07/2016

Fa poc, mentre passejava, vaig trobar-me un arbre tallat. És el de la foto. Alguna cosa se’m va remoure per dins. Calia tallar-lo? No ho sé, però tinc els meus dubtes. Recordo molts arbres, als carrers, que van ser part de la meva vida durant anys i anys i que, un cert dia, algú va decidir tallar perquè feien nosa. Hi ha qui creu que, a tota reforma urbanística, el primer que cal fer és treure entrebancs i tallar arbres. Per què? He de confessar que em sento més proper als qui van projectar l’ampliació d’algunes carreteres com la que va a Vilalleons o la que surt d’Es Mitjorn Gran: van respectar el tram antic, cobert per una meravellosa doble filera de plàtans (pins), deixant-la per al pas en una de les direccions i van construir, al costat, un nou tram per a la circulació en direcció contrària.

Heu sentit parlar dels dendrocronòlegs? La dendrocronologia és la branca de la ciència que estudia els anells dels arbres i analitza els missatges que amaguen. El principi és ben senzill: La majoria d’arbres formen un nou anell de creixement cada any. El gruix d’aquest anell depèn de la temperatura i humitat durant l’any en qüestió, perquè els arbres creixen millor i de manera més perllongada els anys de clima benigne i humitat adequada. En canvi, a les èpoques de sequera creixen menys i fan anells més prims. D’altra banda, els arbres propers i de la mateixa zona viuen condicions climàtiques similars i per tant produeixen patrons semblants de creixement dels seus anells, tot i que cada arbre té la seva individualitat i el seu propi model de creixement. Per exemple, tendeixen a créixer menys a mesura que es fan vells de manera que els anells centrals són més separats que els exteriors, com podeu veure a la imatge de dalt.

La prehistòria s’amaga a la foscor dels temps perquè els humans no vam començar a escriure i deixar constància del que passava fins fa uns cinc mil anys. Però molt abans, els arbres ja anaven escrivint (escrivint-se) la crònica anual del seu entorn. La diferència amb el que ens expliquen altres sistemes de datació (com el basat en el carboni-14) és que la crònica dels arbres de l’antiguitat és viva i diversa. Els arbres d’un bosc viuen els mateixos canvis climàtics, però amb matisos. Els arbres més protegits al centre del bosc no produeixen i escriuen els mateixos anells que els que es troben en zones exposades al vent i a les inclemències del temps. Els dendrocronòlegs saben llegir els factors ambientals comuns a tots els arbres d’una mateixa regió junt amb les especificitats de cada un d’ells. Interessant, oi?

La dendrocronologia ve de lluny. El Laboratori d’investigació dels anells dels arbres de la Universitat d’Arizona va iniciar la seva activitat l’any 1937, i des de llavors es dedica a recopilar i guardar dades. Els investigadors han anant recopilant informació i creant un bon nombre de bases de dades, que ara poden compartir els científics de tot el món. La imatge que podeu veure a sota és d’aquest article de l’any 1941 de A.E. Douglas (fundador del laboratori ja comentat de la Universitat d’Arizona) i mostra com es feien coincidir, a mà, els patrons dels anells de 4 arbres que van viure fa 750 anys. Podeu veure que l’any 1260 va ser clarament més suau que el 1270, i que el 1251 va ser un any de sequera, amb una clara coincidència entre el que van percebre i enregistrar per separat cada un dels quatre arbres.

A les excavacions és fàcil trobar soques fossilitzades o semi-fossilitzades. No és difícil mesurar l’amplada dels anells de qualsevol d’elles. Un cop corregits efectes subjectius (de l’arbre) com el de l’envelliment, obtenim una seqüència d’amplades d’anells que cobreix tota la vida de l’arbre. És el seu testament, la crònica de la seva vida. L’arbre no sap res del que va passar abans de néixer ni ens pot dir res del que va succeir després de la seva mort, però ens regala el patró de tots els daltabaixos climàtics al llarg de la seva vida. Els dendrocronòlegs comparen els patrons d’arbres de la mateixa zona i els van emparellant anell a anell, de manera que acaben descobrint les pautes objectives de variació climàtica. El gràfic que podeu veure en aquesta pàgina web explica molt bé el que s’ha aconseguit esbrinar fins ara. És la variació climàtica a l’Europa central, any a any, des de fa 14.000 anys fins fa uns 10.200 anys, coneguda i entesa només a partir de l’estudi dels anells dels arbres. Estem parlant de molts anys abans de la revolució neolítica. Els humans no escrivien, però els arbres van preservar els canvis climàtics any rere any i ara ens regalen la seva crònica particular.

Inicialment, aquesta anàlisi dels patrons dels arbres es feia manualment. Suposem que trobem una soca d’arbre semi-fossilitzat. Estudiem els seus anells, obtenim el patró de les variacions climàtiques anuals al llarg de la seva vida, i acabarem tenint una gràfica més curta (de 50, 100 o 200 anys) però molt similar a la de la web del WSL. Ara només cal veure on encaixa amb la gràfica temporal de tot el que ja hem aprés fins ara, i això ens dirà l’edat de la soca. Aquesta tècnica, anomenada de datació creuada, funciona perquè és molt improbable que el patró de variacions climàtiques al llarg de tota la vida d’un arbre encaixi bé a més d’un lloc en el gràfic de tota l’evolució ja coneguda, com bé ens explica l’estadística. Fixeu-vos un cop més en la gràfica del WSL. Veureu que hi ha una zona, al voltant de fa uns 12.500 anys, on encara no tenim dades. Però només és qüestió de temps: l’escletxa sense informació s’anirà tancant a mesura que trobem soques d’arbres que se superposin parcialment amb la zona verda o amb la blava de la gràfica i que a la vegada expliquin una mica dels anys del mig. Seran arbres que van néixer a la zona verda i van morir als anys desconeguts, o bé que van néixer durant aquests anys i que van morir ja a la zona blava de la gràfica.

Les tècniques actuals de datació creuada utilitzen mètodes estadístics i resolen el problema amb algorismes informàtics que permeten correlacionar patrons i testejar diverses hipòtesis en relació als factors ambientals. Es basen en calcular la probabilitat que unes determinades condicions climàtiques hagin acabat produint els anells que observem a la soca que hem trobat, i en el fet que el grau de certesa de les inferències estadístiques augmenta a mesura que recollim més i més dades. Tot plegat és un bon exemple de treball interdisciplinari entre biòlegs, estadístics i informàtics. En aquesta pàgina web podeu trobar tot tipus de dades i paquets informàtic/estadístics per al problema de les datacions.

Ara fa tres anys, els investigadors suïssos van trobar 257 soques de pi en una zona en construcció als peus del Uetliberg. Les soques, semi-fossilitzades, van poder ser analitzades i els seus anells ens van explicar que eren pins de fa 13.000 anys, pins que havien crescut just després de la darrera glaciació, quan les glaceres alpines començaven a retrocedir. És un descobriment molt important, que ens portarà llum sobre les condicions climàtiques a Suïssa a finals de la darrera edat de gel. Aquí teniu un mapa interactiu que també ho explica.

Els arbres semi-fossilitzats són veritables documents escrits que ens estan permetent desxifrar i interpretar allò que els nostres avantpassats no ens van saber dir.

Però el clima actual està embogint. El que diu en Ramon Folch és esfereïdor, mireu la cita del final d’aquest article. En Ramon Folch ens recomana aquest vídeo, que mostra la variació de la temperatura global de la Terra des de 1880 fins a 2015. Tal vegada, d’aquí a uns segles, els humans ens haurem suïcidat col·lectivament i ja no podrem gaudir de la crònica que els arbres escriuen any rere any. Però els arbres continuaran deixant constància escrita del que va passant al seu entorn, com ja ho van fer després de l’extinció dels dinosaures, esperant que alguna futura espècie, més conscient i sàvia que nosaltres, els torni a llegir.

——

Per cert, en Ramon Folch constata que, per vuitena vegada consecutiva, a la Terra hem tingut el mes globalment més càlid de l’últim segle. Diu que el clima canvia perquè els humans escalfem l’atmosfera amb la combustió massiva de combustibles fòssils, i que no és mala sort, sinó que és una conducta temerària i culpable.

 

Internet i l’Atenes del segle XXI

dimecres, 4/11/2015

Fa 13 anys, a Syros (Grècia), el professor Dimitris Gritzalis parlava dels sistemes de votació electrònica segurs. Tot comentant les avantatges i els punts encara foscos en aquells moments, comentava que la gran revolució de la democràcia electrònica i de les votacions per internet arribaria al llarg de la següent dècada. O sigui, ara.

Durant aquests darrers anys hem avançat molt, i crec que els investigadors informàtics han fet els deures. Ara tenim un bon nombre d’algorismes i eines telemàtiques que garanteixen el caràcter anònim i la seguretat a les votacions electròniques. S’hi ha treballat molt, només cal que cerqueu “e-voting” en alguna eina de cerca especialitzada com Google acadèmic. En David Ríos per exemple, va fer la seva tesi doctoral i ha participat en un llibre sobre la nova democràcia electrònica basada en internet. Però de fet, encara que algunes ciutats com Porto Alegre ja utilitzen aquestes eines per a decidir els pressupostos, els sistemes de democràcia directa i electrònica són poc coneguts i no gaire utilitzats. Probablement perquè no interessa a alguns.

Fa pocs dies vaig llegir algunes noticies que em van fer pensar en aquestes votacions electròniques. En el 70 aniversari de la ONU, Cristina Gallart es preguntava com podem afrontar els reptes que tindrem en la promoció de la pau i la seguretat i en el foment del desenvolupament i els drets humans. El diari deia també que és molt fàcil criticar l’ONU, però que sense aquest organisme el món seria sens dubte un lloc pitjor. És cert, i de fet, com també deia la Sara Berbel, el segle XXI tindrà les seves pròpies pors. Pors que no vindran del poder de la tecnologia, sinó de l’ambició i del desig de poder dels humans. L’acumulació de riquesa, les desigualtats alarmants, l’accés a l’energia, l’escalfament del planeta, els fonamentalismes, la corrupció i l’acumulació de poder són temes que fan por perquè és ben fàcil que aviat ens explotin a les mans en forma de conflictes amb milions de desplaçats i morts. Per això la Cristina Gallart diu que cal impulsar la ONU i treballar per l’acompliment dels drets humans a nivell mundial.

Les eines de democràcia electrònica directa ens poden ajudar molt, els propers anys. Només es tracta de decidir entre la cara i la creu de la informàtica i internet. Internet és una eina de doble tall, que els Estats ja estan usant (cada cop de manera més esfereïdora) com a arma, per vigilar i controlar la gent i per localitzar persones suposadament indesitjables. Però internet és també una meravellosa oportunitat per a construir la nova democràcia que encara no sabem com serà, però que necessitem. Internet és una eina per saber el que passa, per entendre els altres, per participar. Cal decidir què volem que sigui internet quan sigui gran. I ho hem de decidir nosaltres perquè la responsabilitat és nostra.

En Pedro Olalla explica molt bé l’estructura de la democràcia que hi va haver a Atenes. Ens diu que no existia el desacord entre govern i ciutadans, perquè els ciutadans eren el govern. El poder de decisió no era en mans de representants o líders, sinó en el conjunt dels ciutadans. En lloc de partits i llistes tancades hi havia l’Assemblea de l’Àgora, amb implicació continua del poble en la presa de decisions i amb càrrecs que sempre eren limitats en el temps. Existia el “procés contra llei” com a recurs per exigir responsabilitats en cas de decisions contràries al bé de la ciutat. Tots els ciutadans podien ser presidents de l’Assemblea (per un dia), membres del Consell (per un any), membres de jurats, i tenien accés a molts altres càrrecs temporals per sorteig o elecció. Ara, després de 25 segles, les eines de democràcia electrònica ens tornen a oferir aquesta possibilitat i no només a nivell local, sinó fins i tot a escala global. Perquè la comunicació i la informació ja són globals. Vivim en una paradoxa: el poder econòmic s’ha estès formant una xarxa mundial mentre continuem amb eines democràtiques del segle XIX. Per això, al meu entendre, un dels grans reptes del segle XXI (o, si voleu, una de les revolucions pendents) serà el d’aconseguir estructures de govern mundial basades en eines de democràcia electrònica, perquè la lluita contra els abusos del poder econòmic globalitzat requereix instruments democràtics potents, directes i d’escala planetària, que només internet ens podrà donar.

Per cert, en Pedro Olalla també diu que Grècia té un paper molt important els propers anys: hauria de capitalitzar el seu potencial històric i simbòlic per a ser pionera en el renaixement de la democràcia. Diu que Atenes hauria de convertir-se en pol d’atracció dels veritables demòcrates per tal de concebre un nou model de democràcia, adaptat al món d’avui.

La geometria dels materials

dimecres, 27/05/2015

Fa cinquanta o seixanta anys, el disseny tenia molt més a veure amb les formes que amb els materials. En el disseny d’un llum, taula o cadira, la llista de possibles materials estructurals era ben escassa. Fusta, metall i poca cosa més. Podíem pensar en usar vidre, baquelita o tal vegada bambú, però aquí pràcticament s’acabaven les opcions. Les barques eren de fusta amb elements de llautó, els cotxes de ferro, els trens tenien ferro per fora i fusta per dins.

Aviat va venir la revolució dels plàstics. Els envasos, els electrodomèstics, els teixits de fibres sintètiques, els bolígrafs i infinites coses més. La ciència dels materials es va vestir de química. La recerca de nous materials la dirigien els químics, que sabien sintetitzar nous compostos orgànics sobretot a partir de derivats del petroli a la vegada que experimentaven amb materials compostos (com les barreges de resines i fibra de vidre que tenim ara a les barques i cotxes). Moltes proves eren fallides, però de tant en tant es descobria un nou material amb propietats interessants i tot seguit sorgien munts d’inventors que trobaven cóm fer-los servir. Només cal pensar en el metacrilat, en el niló o en el tefló.

Doncs bé, tot indica que ara som al principi d’una nova revolució en el camp dels materials, propiciada per la informàtica, la nanotecnologia i les impressores 3D. Els nous materials que estem començant a tenir i que tindrem d’aquí a molt pocs anys seran lleugers, adaptables, dissenyables i molt resistents. Fixeu-vos en la imatge, que he tret d’aquesta pàgina web d’en Jan Rys, investigador a l’ETH de Zurich i del grup de Chiara Daraio. En Jan Rys fabrica estructures periòdiques a escala microscòpica i nanoscòpica amb tècniques de fotolitografia, tot analitzant i estudiant les seves propietats mecàniques i de resistència.

Aquests nous materials no són compactes, són quasi buits. Són versions microscòpiques de les estructures de ferro que va dissenyar Eiffel i que després van omplir edificis públics i estacions de tren. Eiffel havia redescobert les idees dels arquitectes del gòtic, que molt abans havien entès que es podia construir sense les parets sòlides i gruixudes del romànic. Només calia entendre la distribució de forces i disposar adequadament els arcs, nervis i columnes. El romànic (i això no treu la seva bellesa) és una mica com els materials que ara tenim: sòlids, compactes, materials on tot ho aguanta tot. En canvi, els materials que estan venint són com les estructures metàl·liques d’Eiffel, amb moltíssimes barres microscòpiques que donen rigidesa i aporten les propietats que desitgem. Són nano-bastides.

Sense abandonar la química, els nous materials s’han passat al camp de la informàtica i de la geometria. Això és així perquè són dissenyables, programables. La Chiara Daraio diu que la revolució actual dels materials consisteix en pensar a l’inrevés: enlloc de fer proves per veure quina utilitat pot tenir un cert material, ara decidirem cóm volem que es comporti, i a partir d’aquí dissenyarem microscòpicament el material, genuí, específic i que ens anirà bé. Suposem que vull dissenyar i fabricar una joguina pel meu fill petit. Vull fer una pilota que tingui zones elàstiques alternades amb regions dures, de manera que segons com caigui a terra, reboti o no. Una pilota en certa manera imprevisible. Aniré a l’ordinador, dibuixaré una pilota, podré dir si la vull buida per dins o no, i tot seguit aniré marcant zones de la seva superfície per indicar quines vull que siguin elàstiques i quines no ho han de ser. L’ordinador calcularà, generarà la geometria del conjunt d’infinites barres microscòpiques de diferents gruixos, longituds i disposicions, respectarà el buidat per dins si és que l’he demanat, i crearà automàticament un fitxer d’instruccions per una impressora 3D. Quan ho imprimeixi (a casa o a qualsevol botiga d’impressió 3D) tindré la meva pilota semielàstica feta a mida, i no hi hauré dedicat més d’un parell de minuts. El material de la pilota serà pura geometria, amb una munió d’estructures nanoscòpiques que garanteixen les propietats que he demanat. Els algorismes de creació del fitxer d’instruccions per la impressora 3D hauran optimitzat, controlat i dissenyat la geometria a totes les escales, des dels detalls nanoscòpics fins els que puc veure a simple vista.

Lijie Grace Zhang és membre del departament de mecànica de la Universitat George Washington i de la facultat de medicina de la mateixa Universitat. Gràcies a la seva formació muti-disciplinar, entén les necessitats en el camp de la medicina regenerativa i a la vegada coneix el disseny de les estructures nanoscòpiques dels nous materials. En un dels seus recents articles explica nombrosos estudis de diversos investigadors que ja poden fabricar materials (podríem dir-ne bastides) que ràpidament es convertiran en vasos sanguinis, parts de fetge, ossos, cartílag, cèl·lules renals o teixits del cor. En molts casos, el que es fa és anar imprimint la xarxa tridimensional de la bastida mentre es va dipositant material bioquímic en els seus espais buits, amb tècniques de bio-impressió. Després de 51 dies de cultiu, s’aconsegueix una fina capa ben formada de teixit biològic, viu, d’uns 5 per 5 mil·límetres i d’un gruix de 0,02 mil·límetres. Estem aprenent a dissenyar teixits del cos humà. No està gens malament, oi?

Per cert, la Natàlia Fabra diu que caldria incrementar els impostos sobre la gasolina ara que han baixat els preus del cru, per a reduir l’increment del consum i invertir el diner obtingut per a fer la transició energètica i incrementar el pes de les renovables en el mix energètic.

Els estols i la intel·ligència col·lectiva

dimecres, 18/02/2015

Fa temps, anant per l’Empordà, vaig veure l’estol d’estornells que podeu veure a la imatge de l’esquerra. No em vaig poder estar de fer-li una foto. Milers d’ocells en moviment harmònic, dansant i pintant formes animades al cel. Els estols d’ocells i els eixams d’insectes semblen cossos vius i complexes, organismes virtuals amb una certa mena d’intel·ligència col·lectiva que moltes vegades ens deixa ben sorpresos.

Però els eixams i els estols són més fàcils d’explicar del que sembla. Coincideixo amb en Daniel Closa quan explica el fàcil que és acabar tenint comportaments de complexitat inesperada a partir d’animals individuals que segueixen unes poques i senzilles regles. És la complexitat de les interaccions simples. En Craig Reynolds, l’any 1986, va ser el primer en proposar un algorisme per a crear eixams artificials, tot demostrant que la conjunció de molts comportaments bàsics acaba creant una mena de vida col·lectiva sofisticada. L’algorisme de Reynolds, anomenat Boids, es basa en tres regles. Cada un dels animals individuals de l’estol simulat per aquest algorisme fa el mateix: quan és massa a prop d’algun dels seus veïns se’n separa per a no col·lisionar, a més intenta apropar-se al punt central (centroide, en termes geomètrics) del conjunt dels seus veïns, i també intenta avançar en la direcció mitjana en la que veu que es mouen aquests seus veïns. Com que evidentment no pot fer les tres coses a la vegada, acaba movent-se en una direcció que no és més que la suma del que li diuen les tres regles. Observeu, d’altra banda, que el comportament de cada un dels animals virtuals de Boids és local, perquè les regles només requereixen l’observació del que fan els veïns més propers. Aqui podeu trobar l’algorisme Boids, detallat. Gràcies a Craig Reynolds i altres investigadors, ara sabem que la suma de molts comportaments individuals i trivials basats en els veïns, genera complexitat i un cert grau de vida col·lectiva.

El grup de recerca en sistemes auto-organitzats de la Universitat de Harvard treballa en dissenyar eixams artificials, conjunts de molts petits robots que arriben a tenir una mena d’intel·ligència col·lectiva. L’interessant, un cop més, és que aquest comportament col·lectiu apareix espontàniament només pel fet que cada un d’ells té determinat comportament individual amb regles ben senzilles. Mireu aquest vídeo, que mostra un eixam de 1024 petits robots. Tots els robots són iguals i segueixen les mateixes regles, com els estornells de l’eixam que comentàvem. Es mouen amb vibradors, fent petits saltets, i es comuniquen amb els seus veïns amb llum infraroja, com mostra el vídeo. Les tres regles bàsiques per a moure’s consisteixen en aturar-se si ja han arribat a la regió que tenen programada, anar cap aquesta regió si encara no hi són, i moure’s sense allunyar-se dels seus altres “companys” (de fet, també tenen alguna regla més per a corregir errors). Els resultats que mostra el vídeo són ben bonics, oi?  Cal dir que els treballs del projecte Kilobot han estat publicats a la revista Science.

Encara no sabem com, però ben segur que la intel·ligència col·lectiva de l’eixam de neurones del nostre cervell és el que ens fa conscients, sensibles al que podem ser i coneixedors del poc que som.

Per cert, en Carlos Madrid diu que Àfrica no necessita una agricultura ecològica, sinó agricultura a seques. Diu que l’interessant seria afavorir la transferència de tecnologies no contaminants als països del segon i tercer món, i al mateix temps promoure l’estalvi energètic i les energies renovables al primer món.

Els bits que construeixen

dimecres, 3/09/2014

La llista de laboratoris del MIT és del més suggeridora. Per posar només dos exemples, els laboratoris del MIT inclouen el d’automuntatge (Self-Assembly Lab) i el laboratori de bits i àtoms, dirigit per Neil Gershenfeld. Des de fa 16 anys, Gershenfeld dóna un curs sobre com fabricar quasi qualsevol cosa. Quan els estudiants li pregunten per a què serveix el que aprendran al curs, ell diu que no els servirà per a construir el que ja pots trobar a les botigues, sinó per fer-te allò que no hi pots trobar. Neil Gershenfeld va crear la xarxa de “Fab Labs juntament amb Bakhtiar Mikhak, per a oferir eines de fabricació personalitzada a tothom.

La informació és cada cop més intangible i etèria. Fa 30 anys, el que teclejàvem a les màquines d’escriure quedava immediatament reflectit en el paper i no era fàcil esborrar-ho. Ara, el que escrivim queda codificat en bits que es poden volatilitzar si no guardem el que estem veient en pantalla. Tenim moltíssima informació a les targetes Micro SD de només 11 per 17 mil·límetres dels nostres mòbils, i l’enviem de manera invisible per internet a través de xarxes Wifi. Si la nostra retina fos sensible a d’altres freqüències electromagnètiques, veuríem l’aire ple de l’eixam de colors, ara invisibles, dels bits tots els Whatts Apps i missatges que ens estem enviant.

Però els ordinadors no només creen i treballen amb bits. Tenen dispositius que converteixen els bits en matèria. És el que fan les impressores que tenim a casa i a la feina. Els algorismes d’impressió reben documents codificats en bits, i converteixen aquests bits en puntets de tinta ben distribuïts sobre el paper 2D: lletres de diferents tipus, taules i gràfics, fotografies. Les impressores són constructores de símbols i dibuixos, màquines que converteixen bits en àtoms de tinta sobre el paper. Les impressores en paper són un primer exemple, senzill i quotidià, del concepte que hi ha darrera del centre de bits i àtoms del MIT.

Seguint aquesta mateixa idea, les impressores 3D, fa uns vint anys, van fer el salt del 2D al 3D, el pas de les dues a les tres dimensions. El principi d’una impressora 3D no és massa diferent del d’una impressora 2D sobre paper. Si penseu que en lloc de tinta utilitzem un material que anem dipositant sobre el paper en capes molt fines, la zona que anem imprimint anirà agafant gruix i acabarà essent tridimensional. La màgia de les impressores 3D és que ens “solidifiquen” el que imaginem i creem amb els ordinadors. Fabriquen i construeixen a partir de bits. La imatge de dalt, d’aquesta web, ens mostra l’esquema d’una de les tecnologies d’impressió 3D existents. El sistema conté una cubeta horitzontal plena de pols de plàstic o de metall i un raig làser que escombra aquelles zones de pols que volem convertir en una de les capes del nostre objecte. La calor del làser solidifica la capa de pols en aquestes zones (per sinterització en el cas de pols de metall o per polimerització quan el pols és de plàstic). Un cop ja acabada aquesta capa de l’objecte, un full de reomplert recorre tota la cubeta de banda a banda tot cobrint-la amb una nova capa ben fina de pols net. El procés es va repetint, les noves capes es van soldant a les anteriors, i l’objecte va apareixent enmig del pols no solidificat. Imagineu-vos que en vostre ordinador teniu una aplicació de disseny digital 3D, i que, amb paciència, feu una petita estàtua, una peça o un senzill objecte de decoració. El resultat és intangible, és la forma que heu esculpit codificada en bits. Però els algorismes geomètrics d’una impressora 3D li fan una seqüència de talls virtuals (de manera idèntica a com si tallessin un embotit), calculen la forma geomètrica de cada un d’aquests talls, i generen les comandes adequades per a que el làser solidifiqui la corresponent capa de pols amb una forma exactament igual a la del tall virtual del model que hem creat. L’objecte virtual es construeix físicament amb algorismes que fan que el làser segueixi la forma dels talls virtuals, capa a capa.

El que estan fent ara els investigadors del MIT és el següent salt, del 3D al 4D. Es tracta de construir peces amb materials que codifiquen el temps. Ho explica l’Skylar Tibbits, director del laboratori d’automuntatge del MIT, en aquest vídeo TED, que també podeu trobar en aquesta pàgina web. Tot plegat és fruit d’un projecte de recerca conjunt entre Stratasys i el MIT. A la part final del vídeo, per exemple, podeu veure una cadena programada per a transformar-se en dos cubs. Les baules de la cadena semblen iguals, però no ho són. La impressora 3D que les va fabricar, les va fer amb materials lleugerament diferents i així, algunes baules tenen codificat que hauran de girar d’una determinada manera, mentre que d’altres “saben” que hauran de girar de manera diferent. És una idea que canviarà moltes coses, els propers anys. En els nous programes de disseny per ordinador, haurem de pensar i crear tant la forma com el comportament. Les peces que dissenyem tindran informació associada sobre què han de fer per a autoacoblar-se amb les peces veïnes. Tot plegat ho guardarem en fitxers que contindran bits de forma 3D i bits de comportament. El làser de les impressores 3D esculpirà la forma mentre anirà codificant el comportament que haurem programat en les diferents propietats del material de cada una de les partícules que es van solidificant. Segons explica Skylar Tibbits en el vídeo, la tecnologia d’impressió 4D requereix haver codificat la sequència d’acoblatge per a després programar de manera local el material de cada peça, que esdevenen algorismes sòlids. A més, val a dir que també cal energia per a l’automuntatge i algun sistema d’autocorrecció d’errors. Hi ha moltes maneres de fer-ho. Per exemple, la tecnologia “Stratasys Connex utilitza aigua per a subministrar l’energia necessària per a l’automuntatge. Tot plegat sembla ciència-ficció, i la veritat és que encara som a les basseroles. Però no és una idea massa estranya. Skylar Tibbits ens recorda que és el que ja fan les proteïnes i l’ADN: es comporten de determinades maneres que ja tenen autoprogramades.

Els bits que comanden les impressores en paper són els que ara ja expliquen tot tipus de formes tridimensionals a les impressores 3D i els que ben aviat construiran formes que sabran adaptar-se, connectar-se i construir assemblatges, sistemes dinàmics i màquines. Seran bits que codificaran i explicaran formes, temps i processos a les impressores 4D. Us imagineu el kit d’un moble que, quan obriu la caixa, s’autoconstrueix sense cap intervenció nostra?

Per cert, Bàrbara Schmitt, portaveu de la Institució Altempordanesa per a la Defensa i Estudi de la Natura (IAEDEN) acusa el Govern de fer una “llei a mida” perquè El Bulli Foundation de Ferran Adrià es pugui construir a la cala Montjoi, al mig del Parc Natural del Cap de Creus. Aquesta denúncia és també a la plataforma Change.org.

El càlcul mental i els caixers dels pàrquings

dijous, 25/07/2013

 

Hem de pagaMonedesCaixer.jpgr 2,75 euros en el caixer automàtic del pàrquing. Tenim una moneda de dos euros, una d’un euro, dues de deu cèntims i tres monedes de 5 cèntims. Cóm hem d’introduir les monedes per tal de quedar-nos al final amb el mínim de monedes a la butxaca?

És clar que no podem pagar l’import exacte. D’altra banda, el total de les nostres monedes és de 3,35 euros. Ens sobren diners i la màquina ens haurà de tornar canvi.

El problema té la seva gràcia, perquè volem dues coses a l’hora. Volem desfer-nos del màxim de monedes, i volem que la màquina ens en torni el mínim nombre possible. Si ho pensem bé, veurem que som davant d’un problema d’optimització combinatòria, no gens fàcil.

El millor és utilitzar un mètode heurístic, que no sempre dona el millor resultat possible però que és raonablement fàcil d’usar i memoritzar, a la vegada que ens pot servir per exercitar la ment en situacions quotidianes. Es tracta de desacoblar les dues parts del problema i primer pensar només en el canvi que ens donarà el caixer.

És fàcil veure que com a mínim hem d’introduir tres euros. I és clar que hem de posar-hi tant la moneda d’un euro com la de dos euros, perquè si no ho fem, no hi ha manera que arribem als 2,75 euros.

També sabem que el màxim que hi podem posar són 3,35 euros, que és tot el que tenim. Per tant, el valor de les monedes que hi posarem segur que es trobarà entre 3 i 3,35 euros. Hi ha alguna quantitat que ens minimitzi el nombre de monedes que la màquina ens tornarà en el canvi?  La resposta és senzilla i permet pensar-la in situ, quan som al caixer: si el valor del total de monedes que hi posem és de 3,25 euros, el canvi consistirà (segurament) en una única moneda de 50 cèntims.

Ja tenim resolta la primera part del problema. Podem minimitzar el nombre de monedes del canvi si aconseguim posar-hi 3,25 euros. Passem a la segona part: cóm podem desfer-nos del màxim de monedes i acabar introduint 3,25 euros abans que la màquina ens retorni el canvi?  Una solució és utilitzar el màxim de monedes (de les que tenim) per a fer un total de 3,25 euros, i, a continuació, anar-les posant al caixer ordenadament, començant per les de poc valor i acabant per les més grans. En el nostre cas, decidirem introduir les tres de cinc cèntims, una de deu cèntims, la d’un euro i la de dos euros perquè tot plegat suma 3,25 euros i així només ens quedarem amb una moneda de deu cèntims. Tenim força llibertat pel que fa a l’ordre en que posem les monedes, però és clar que hem de deixar pel final o bé la moneda d’un euro o bé la de dos euros si volem evitar que la màquina ens doni el canvi abans d’hora.

En resum: hi hem d’introduir 3,25 euros, i això ho podem fer de manera que aconseguim treure’ns totes les monedes que teníem menys una. A més, podem minimitzar el nombre de monedes que ens tornarà la màquina. Al final, ens quedarem amb dues monedes a la butxaca i pensarem que hem resolt bé el problema.

Quina és la simplificació que hem fet i que no sempre funciona?:  La de desacoblar el problema. No és aquest el cas, però podria passar que tinguéssim una solució en que la màquina ens retorna dues (no una) moneda, i que fa que ens puguem desfer de bastantes més monedes. Per això, si volem estar segurs d’haver arribat a la solució òptima, a la millor de totes, hem de fer una anàlisi exhaustiva de totes les possibilitats (vegeu la nota al final). Us veieu amb cor de pensar un exemple en el que la heurística que us he proposat no arriba a la millor solució?

Encara que sembli estrany, pagar en un caixer no és massa diferent que jugar a escacs. Tenim un objectiu (en el nostre cas, quedar-nos amb el mínim de monedes), i hem de dissenyar una estratègia (que no és més que un algorisme) per arribar-hi o, al menys, per anar-hi a prop. Aquesta estratègia, però, depèn “d’un altre”, que en aquest cas és l’algorisme que algú ha programat en el caixer. El nostre algorisme serà millor si entenem i tenim en compte l’algorisme “de l’altre”. I a més, tenim la dificultat afegida que la solució òptima d’aquests problemes requereix analitzar una munió de possibilitats. Per això, és bo pensar en heurístiques, que no són més que algorismes ràpids que habitualment donen solucions raonablement acceptables. D’això en parla la teoria de jocs. En escacs, per exemple, un algorisme òptim hauria d’analitzar totes les possibles evolucions futures del joc, tenint en compte totes les possibles estratègies tant les nostres com les de l’altre; com que això és intractable, els jocs per ordinador sempre utilitzen heurístiques, ràpides però subòptimes.

No es pot tenir tot. Els algorismes de càlcul i raonament mental són molt útils, però no sempre ens donen la millor solució. Els algorismes de cerca exhaustiva i optimització combinatòria troben la millor solució possible, però millor que no penseu en usar-los quan sou davant del caixer perquè de ràpids no en tenen res.

Nota final: Si volem estudiar bé el problema i estar segurs que hem trobat una bona solució, sobretot en casos en què tenim més monedes, ens cal una mica de paper i llapis. Pensem en la primera part del problema, la que intenta minimitzar el nombre de monedes que esperem que ens torni la màquina. Hem vist que el valor de les monedes que hi posarem estarà sempre entre 3 euros i 3,35 euros. Combinant adequadament les monedes que tenim, podem aconseguir introduir al caixer (abans que ens comenci a donar el canvi) qualsevol d’aquestes quantitats:

  • 3 euros (amb les dues monedes de un i dos euros)
  • 3,05 euros (amb les monedes d’un i dos euros i una de 5 cèntims)
  • 3,10 euros (amb les monedes d’un i dos euros i dues de 5 cèntims, per exemple)
  • 3,15 euros (amb les monedes d’un i dos euros i les tres de 5 cèntims, per exemple)
  • 3,20 euros (amb les monedes d’un i dos euros, una de 10 cèntims i dues de 5 cèntims, per exemple)
  • 3,25 euros (amb les monedes d’un i dos euros, les tres de 5 cèntims i una de 10 cèntims, per exemple)
  • 3,30 euros (amb les monedes d’un i dos euros, dues de 5 cèntims i dues de 10 cèntims)
  • 3,35 euros (amb les monedes d’un i dos euros, les tres de 5 cèntims i dues de 10 cèntims)

I, en cada un d’aquests casos, què ens tornarà la màquina?

  • En el cas de 3 euros, el més probable és que ens torni dues monedes, de 20 i 5 cèntims
  • En el cas de 3,05 euros, el més probable és que ens torni dues monedes, de 10 i 20 cèntims
  • En el cas de 3,10 euros, el més probable és que ens torni tres monedes, de 5, 10 i 20 cèntims
  • En el cas de 3,15 euros, el més probable és que ens torni dues monedes de 20 cèntims
  • En el cas de 3,20 euros, el més probable és que ens torni tres monedes, una de 5 i dues de 20 cèntims
  • En el cas de 3,25 euros, el més probable és que ens torni una moneda de 50 cèntims
  • En el cas de 3,30 euros, el més probable és que ens torni dues monedes, de 5 i 50 cèntims
  • En el cas de 3,35 euros, el més probable és que ens torni tres monedes de 20 cèntims

Dic que això és el més probable, perquè el caixer funciona en base a un algorisme, i no sabem exactament quines opcions ha considerat la persona que l’ha programat. El lògic seria que ens tornés el canvi amb el mínim possible de monedes, però això no és sempre així. Si us hi heu fixat, els caixers moltes vegades donen dues monedes de 50 cèntims enlloc d’una d’un euro. I, com indiquem en el darrer cas dels que hem vist, per tornar 60 cèntims, és força habitual que ens torni 3 monedes de 20 cèntims encara que seria més òptim si ens retornés una de 10 i una de 50. De fet en el nostre cas, fixeu-vos que els 3,35 euros també serien una solució òptima si sabem que la màquina ens tornarà dues monedes (de 50 i 10) enlloc de tres de 20.

Però si haguéssim de pagar 2,90 euros i tinguéssim tres monedes d’un euro i tres de deu cèntims, és fàcil veure que l’heurística que abans us he proposat no és òptima. En aquest cas, el millor és desfer-nos de totes les monedes tot forçant que la màquina ens torni dues monedes de vint cèntims, perquè si fem que ens torni només una moneda de canvi, acabarem amb més de dues monedes a la butxaca.

Per tal d’estar segurs que hem trobat la solució òptima, no tenim altra sortida que analitzar totes les possibilitats i utilitzar tècniques d’optimització combinatòria. Tenim moltes maneres d’anar introduint les monedes al caixer (de fet és un problema de permutacions amb repetició en que algunes permutacions són idèntiques perquè, arribat un cert punt, generen el mateix canvi per part de la màquina). Per a cada una de les possibilitats sabem el nombre total de monedes: les que ens tornarà més les que no hi posem. L’anàlisi exhaustiu de totes elles ens porta a la solució òptima.

Els ginkgos, les abelles i els algorismes

dimecres, 29/05/2013

Ginkgo1.jpg El ginkgo biloba és un arbre ornamental, del grup de les les gimnospermes com els pins i els avets, però que no fa pinyes. Val la pena acostar-se a algun dels que tenim en els nostres jardins i passar una estona tot gaudint-ne. Si aneu a Girona, trobareu un ginkgo en el claustre de Sant Domènec, a la Universitat. Però no és difícil trobar-ne a d’altres parcs i llocs públics. El ginkgo és lent, tarda deu anys en arribar als 10 metres d’alçada, però viu molts anys. És un arbre sagrat, a la Xina i al Japó. En alguns monestirs de la Xina i del Japó se n’han trobat de mil·lenaris. A la Xina se l’anomenava l’arbre de l’avi i del nét ja que l’avi plantava l’arbre i era el nét qui se’n menjava els  fruits (bullits o fregits). Les fulles del ginkgo són caduques, en forma de ventall, de color verd brillant i amb nervis molt prims i radials. En Josep Gordi ens explica que les fulles i fruits del ginkgo tenen propietats medicinals: el ginkgo apareix esmentat en els llibres de medicina xinesa tradicional. Se li atribueixen efectes beneficiosos sobre el cor i els pulmons. Actualment existeixen plantacions de ginkgos per aprofitar-ne els seus compostos químics en la indústria farmacèutica.

El ginkgo, a més, és l’arbre que el temps ha oblidat. Fa dos-cents milions d’anys, durant el període Juràssic, a la Terra ja creixien els ginkgos. Ho sabem pels fòssils (com el que teniu a la imatge) que ens mostren les mateixes fulles en forma de ventall dels ginkgos actuals. Podem gaudir-ne quan passegem pels parcs. Ens ho recorda aquest llibre. Les espècies animals i vegetals han desaparegut, quasi tot el que hi havia (i era viu) durant el Juràssic es va extingir, però una cosa és certa: el temps es va oblidar d’extingir els ginkgos. És un exemple admirable de persistència. Costa pensar en una xifra com aquesta, de 200 milions d’anys. Si ho traduïm a mil·lennis, estem parlant de dos-cents mil mil·lennis. Un període de temps que és cent mil vegades més gran que el que ens separa de l’inici de la Era cristiana.

Un altre llibre recent ens parla dels algorismes que l’evolució ha anat “cablejant” en els éssers vivents. Leslie Valiant connecta els treballs de Alan Turing sobre disseny d’algorismes i mètodes per a la resolució robusta de problemes amb la teoria de l’evolució i amb el principi de la supervivència dels més adaptats. Els actuals éssers vius saben resoldre problemes que aparentment són molt complexes, i els resolen de manera òptima o quasi-òptima. Amb poca energia vital són capaços de trobar i arribar a bones solucions que els ajuden a viure. I com que ho fan bé, no s’esgoten i poden guardar energies per poder fer front a d’altres situacions previsibles o no previsibles. Nosaltres pensem i podem crear, podem inventar noves solucions als problemes que ens planteja la vida. Però els animals ho fan bé perquè ho tenen “cablejat” en el seu petit cervell. Arriben a bones solucions no pas perquè els seus cervells s’hagin anat perfeccionant generació rere generació, sinó perquè els que no ho feien tan bé, van morir. És el raonament genial de Darwin. En cada generació hi ha petits canvis. És el mateix que passa amb els nens que neixen cada dia, tots són una mica diferents. Alguns dels éssers vivents de la nova generació, animals o vegetals, s’adapten més al medi i “saben fer-ho millor” mentre que d’altres s’hi adapten menys. Al llarg de les generacions, no és que el “cablejat” vagi millorant per efecte d’alguna força oculta. El que passa és que els més adaptats, els que ho feien millor, són els que perduren. D’aquesta manera, els éssers vius van pujant lentament la muntanya improbable, en paraules de Richard Dawkins. Tot pujant la muntanya, els peixos del Juràssic han anat evolucionant fins arribar a nosaltres. No és improbable, això?  No ho és tant si pensem en el nombre immens de generacions que ens han precedit, des de fa 200 milions d’anys en el període Juràssic, quan Pangea s’estava trencant i l’Atlàntic encara era molt estret. Mentre els ginkgos s’han anat adaptant al medi i no han necessitat grans canvis, l’evolució dels animals al llarg de milions de generacions els ha anat estructurant i definint, els ha anat cablejant de la millor manera possible. Els qui no ho feien tan bé, ja no hi són.

Un bon exemple d’insectes que troben solucions òptimes a problemes molt complexes el tenim en les abelles. Fa dos anys i mig, uns científics de la Universitat de Londres van descobrir que les abelles decidien automàticament la ruta més curta entre les flors quan en treien el pol·len. Les abelles saben resoldre l’anomenat problema del viatjant a una velocitat superior a com ho faria un ordinador, perquè tenen la solució del problema integrada en el seu cervell. Els investigadors van utilitzar flors artificials per comprovar que les abelles, un cop localitzaven les flors, sabien trobar la ruta més curta per passar per totes elles.

El problema del viatjant (també conegut com a problema del viatjant de comerç) és un dels problemes més estudiats en el camp de l’optimització informàtica. Estem acostumats a que molts problemes siguin lineals. En els problemes lineals, la complexitat és proporcional a la mida del problema. Resoldre un test és habitualment un problema lineal: si el test té 20 preguntes, tardarem aproximadament el doble que si té 10 preguntes. A doble de preguntes, doble de temps. En el problema de les flors i les abelles, la cosa no és tan fàcil. Suposem primer que tenim només tres flors. És fàcil veure que podem visitar-les de sis maneres diferents, que podem escriure com 123, 213, 132, 312, 231, 321 (“231″ vol dir que primer anem a la flor 2, després a la 3 i finalment anem a la 1). En algunes d’aquestes sis maneres, el camí total recorregut per l’abella serà més llarg i en d’altres, més curt. La solució òptima és la que dóna un camí total més curt, perquè així l’abella gastarà menys energia. Si hem de resoldre el problema amb ordinador, el que farem és calcular el camí que cal recórrer en cada un dels sis possibles camins, i veure quin és el més curt. En aquest cas de tres flors, hem de calcular i comparar sis possibles camins. I justament aquí tenim la dificultat. El nombre de solucions que ens cal calcular i comparar és el factorial del nombre de flors, i aquest nombre es fa totalment intractable quan creix el nombre de flors. Si tenim 10 flors caldria analitzar més de 3 milions de possibles camins, i si pugem només fins un total de 25 flors, n’hauríem d’analitzar 15 quadrilions. Impossible, trigaríem massa temps. És un problema dels anomenats no polinòmics. Els algorismes dels nostres ordinadors poden acostar-se a una bona solució, però no poden trobar la millor de totes. Les abelles, en canvi, ho fan bé per intuïció. per una intuïció que han heretat dels seus avantpassats al llarg de milions de generacions. Els ginkgos també ho han fet i no s’han extingit, ara per ara.

Leslie Valiant diu que hauríem d’aprendre dels animals i de les nostres pròpies intuïcions. Comenta que és bo entendre com els éssers vivents s’han anat adaptant al medi i com l’evolució ha conformat en ells la manera de resoldre problemes. Valiant proposa el terme “ecorismes” com a contracció de les paraules ecologia i algorismes. Els ecorismes són els algorismes que copien i segueixen les pautes (sovint de prova i error) que utilitzen els organismes vius per a adaptar-se i sobreviure. Tal vegada hem de mirar-nos menys el melic i observar més els ginkgos i les abelles.

Els algorismes de traducció automàtica

dimecres, 24/10/2012

GuillemValentina.jpg Entenem els altres, quan parlen? La veritat és que no sempre els entenem, ni tampoc comprenem els seus escrits, perquè molts parlen altres idiomes. Al món parlem moltes llengües diferents, i no podem pas saber-les totes.

Sabem que els ordinadors són màquines versàtils, potencialment capaços de resoldre problemes en camps totalment diversos. Sembla senzill: només cal pensar i escriure el corresponent algorisme, i l’ordinador ens portarà a la solució. L’algorisme és la recepta que explica pas a pas com arribar a bon port. En alguns cassos, això no és difícil. L’algorisme per a fer divisions que ens ensenyen a l’escola és curt i fàcil de recordar (però no oblidem que va caldre esperar segles fins poder dissenyar-lo sobre una base sòlida com és la de la notació aritmètica actual, posicional i en base 10). Hi ha altres problemes (com el de la motxilla) que requereixen algorismes exponencials, massa lents i impracticables, si volem trobar una solució òptima. De fet, l’objectiu sempre és trobar algorismes eficients (que no triguin massa en trobar la solució) i fiables, algorismes que ens portin a una solució acceptable i raonable. Però per alguns problemes com el de la traducció automàtica, la tasca de trobar un algorisme que els resolgui de manera raonablement eficient i fiable ha resultat ser extremadament feixuga.

La història de la traducció automàtica és paral·lela a la de la informàtica. L’any 1954 es va fer el primer intent, conegut com experiment de Georgetown. Tot era optimisme: els autors van poder traduir unes seixanta frases del rus a l’anglès. El camp de la traducció automàtica va atreure molts diners públics, i es va arribar a pensar que que “l’algorisme” es trobaria en un termini de no més de cinc anys. No va pas ser així, i a pesar de molta feina i de molts treballs al llarg dels següents 50 anys, no es va trobar cap algorisme de traducció automàtica que donés resultats acceptables. Els investigadors aplicaven tècniques basades en sintaxi i semàntica, de manera semblant al que fèiem a l’escola. Analitzaven sintàcticament la frase a traduir, intentaven recuperar-ne les idees (semàntica) i finalment tractaven d’expressar aquestes idees en l’idioma objectiu, tot sintetitzant les noves frases. Tot plegat, massa difícil. Les nostres llengües tenen matisos, frases fetes, girs i altres construccions que no són fàcils d’entendre amb regles sintàctiques i semàntiques. La gent del carrer no consulta els llibres de gramàtica, per parlar.

Els algorismes de traducció probabilística o estadística són molt recents. Franz Josef Och va guanyar el concurs DARPA de traducció automàtica l’any 2003 amb un d’aquests algorismes i va decantar els mètodes de traducció cap a aquests nous esquemes probabilístics. Aquests algorismes surten de  tres idees bàsiques: un model probabilístic, un sistema d’aprenentatge i un mètode d’optimització en temps real. Els models probabilístics substitueixen els models gramaticals i sintàctics i es basen en el teorema de Bayes. El teorema de Bayes és fonamental, perquè vincula la probabilitat d’un succés A donat B amb la probabilitat de B donat A. En d’altres paraules, si sabem la probabilitat de tenir mal de coll quan tenim la grip, podem calcular la probabilitat de tenir la grip quan tenim mal de coll (vegeu nota al final). De fet, els models probabilístics dels sistemes actuals de traducció automàtica són més complexes, però inclouen el teorema de Bayes i les idees d’aprenentatge i optimització.

De fet, hi ha a més una quarta idea essencial, que és la que ha donat l’impuls definitiu als algorismes de traducció automàtica eficients i raonablement fiables. És la d’emprar un diccionari de frases enlloc d’un diccionari de paraules. Val a dir que, en el camp de la traducció probabilística, el concepte de frase és un concepte molt més general que el que usem habitualment. Una frase és qualsevol conjunt de paraules que apareix reiteradament. Però no cal que tingui cap significat. Les frases, als algorismes de traducció, no tenen semàntica. Les dues paraules “vaig anar” formen una frase, perquè les trobem tot sovint. Les frases capturen els desordres locals i permeten modelar la traducció de girs i frases fetes. Veiem alguns exemples, amb la nova eina Google Translate. Google Translate utilitza el model probabilístic que hem explicat, amb diccionari de frases. Si demaneu la traducció de la frase “the blue teapot is really cool” al català, us dóna com a resultat “la tetera blau és genial”. L’algorisme ha modelat bé la inversió entre el substantiu i el seu atribut de color, i ha traduit la frase anglesa “really cool” per “genial”. Força bé, no? Com a segon exemple, proveu de traduir la frase “esto es pan comido”, del castellà al català. El resultat us dirà que és “això és bufar i fer ampolles”. Aquí és on es veu clar que l’algorisme de traducció utilitza un diccionari de frases, que incorpora girs, dites i frases fetes. Val a dir que si aneu provant trobareu resultats no tan afortunats, però és clar que l’estat actual dels algorismes probabilístics ja comença a permetre la seva utilització (amb cura i repassant sempre el resultat) i ens fa ser optimistes cara a les seves possibilitats en un futur proper.

Com ja hem comentat, els algorismes probabilístics de traducció necessiten un diccionari de frases, per a poder traduir entre dos idiomes. Els diccionaris de frases estan ordenats alfabèticament i són semblants als nostres diccionaris habituals, però contenen frases enlloc de paraules. I a més, per a cada possible traducció (paraula o frase) guarden el valor de la seva probabilitat. A l’exemple d’abans, al diccionari anglès-català podríem trobar, al costat de la paraula “really”, la frase “really cool” per exemple amb dues possibles traduccions: “genial” i “fantàstic”, amb probabilitats de 0.7 i de 0.3 respectivament. En canvi, al diccionari castellà-català, trobaríem la frase “esto es pan comido” amb una única traducció amb probabilitat 1: “això és bufar i fer ampolles”. Recordeu que les probabilitats es donen en tant per 1 (cal dividir el tant per cent per 100) i que la suma de les probabilitats de totes les possibles traduccions d’una paraula o frase ha de ser la unitat. S’ha comprovat que, per a poder desenvolupar un algorisme estadístic de traducció que sigui fiable i per poder calcular bé les probabilitats de traducció entre frases que es corresponen, cal analitzar moltes parelles de texts (original i la seva traducció). En concret, cal disposar d’una col·lecció paral·lela de més d’un milió de paraules en cada un dels dos idiomes. I a més, cal disposar de dos conjunts de texts monolingües, cada un d’ells amb un mínim de mil milions de paraules, per a poder comprovar si la frase final un cop traduïda és d’ús comú en l’idioma de destí. Els algorismes de Google utilitzen texts de documents oficials de la ONU, perquè es publiquen en totes les sis llengües oficials de les Nacions Unides i són fiables. Però també utilitzen documents oficials de la Unió Europea. El procés d’aprenentatge és lent i feixuc, però es va fent sense presses, en paral·lel a les peticions de traducció que anem fent. Els algorismes d’aprenentatge van actualitzant els diccionaris de frases i les seves probabilitats, tot incorporant i analitzant noves col·leccions paral·leles de parelles de texts. Ho deixen tot preparat per a quan necessitem traduir alguna cosa.

Però el sorprenent, en tot això, és que aquests algorismes de traducció treballen sense tenir en compte ni una sola regla, ni sintàctica ni semàntica. Es basen només en l’anàlisi estadística de parelles de texts o corpus. De fet, s’ha demostrat que els seus resultats són millors que els donats pels actuals models sintàctics i semàntics.

Si aneu a la pàgina del traductor de Google veureu que permet traduir entre moltíssims idiomes. Però de fet, habitualment Google no fa traduccions directes. La traducció de la llengua L1 a L2, normalment requereix dos passos de traducció, el primer de L1 a anglès i el segon d’anglès a L2. Pels texts en català, Google fa tres passos: de català a castellà, de castellà a anglès i d’anglès a l’idioma destí. Això és degut a que existeixen més parelles de documents patró català-castellà que català-anglès. En tot cas, i com ja dèiem, els resultats actuals són molt prometedors.

Serà molt més fàcil de preservar la diversitat de llengües quan sapiguem trencar les barreres de comunicació. No crec pas que tots ho veiem, però penso que al llarg del segle XXI, l’evolució dels actuals algorismes de traducció automàtica permetrà la comunicació en temps real entre persones que parlin llengües diferents. No és ciència ficció, és quelcom que ara es comença a veure factible. Podeu pensar en amplificadors intel·ligents (o telèfons traductors) que faran que puguem escoltar en anglès, pels altaveus, el que una persona va explicant en català davant del micròfon. Seran algorismes i màquines de traducció simultània. Noves eines per a poder entendre els demés, que tant de bo puguin ajudar els nostres néts a comprendre “els altres” i a dialogar enlloc de barallar-se.

Nota: En el cas de la traducció, si volem traduir un tros de text “f”, el que fan els models probabilístics és cercar la frase traduïda “e” tal que la probabilitat p(e/f) sigui màxima. Aquesta probabilitat p(e/f) és la probabilitat de trobar-nos “e” com a resultat de la traducció de “f”. És el que fem nosaltres de manera intuïtiva. Si un text “e” té una probabilitat condicionada (així és com s’anomena) p(e/f) elevada, és que és una traducció “que ens sona bé”. I perquè ens sona bé? Perquè el nostre cervell ens diu que la traducció de “f” a “e” ja l’hem vist altres cops i té sentit. Ens basem en l’experiència. Justament això és el que fan els actuals algorismes. En la fase d’aprenentatge, analitzen molts texts (l’original i la traducció) i n’extreuen les probabilitats, les mesures de si “sonarà bé” o no. El teorema de Bayes ens diu que el producte de p(e/f) per p(f) és igual al producte de p(f/e) per p(e). Com que p(f) no depen del resultat de la traducció, maximitzar p(e/f) és el mateix que maximitzar el producte de p(f/e) per p(e). Si tenim pre-calculades les probabilitats p(f/e) i p(e), el que hem de fer durant la traducció és només una optimització en temps real. Tot plegat és més complex, però podeu pensar que el que fem en temps real és generar una primera llista de texts pre-candidats “e1″, “e2″, … “en”, calcular el valor p(f/e)*p(e) per a cada un d’ells, i quedar-nos amb la frase resultat que maximitzi aquest valor. Aquesta és la traducció. De fet, els models probabilístics dels sistemes actuals de traducció automàtica són més complexes i incorporen tan la probabilitat p(f/e) com la p(e/f) i la p(e). En tot cas, el sistema d’aprenentatge és qui calcula i manté actualitzades aquestes tres probabilitats.