Entrades amb l'etiqueta ‘dades atípiques’

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ó.