Alexandru Paler

Despre inutilitatea unor lucruri

In Fără categorie on 21 Decembrie 2012 at 14:37

Ma oblig sa scriu ceva pozitiv sau nesuparat pe lume in aceasta insemnare (articol asa cum il numeste WordPress-ul), dar nu voi reusi. Fiind vineri si gandidu-ma cum a trecut saptamana mi-am adus aminte ca marti (probabil) am petrecut foarte mult timp incercand sa inteleg de ce lumea este innebunita dupa HTML5. Nu are de a face cu munca mea actuala, dar orele acelea mi-au oferit o perspectiva interesanta.

In liceu si facultate din lipsa majora a unui forum de informaticieni in care sa pot discuta informatica am ales ce a fost mai usor. Peste ani alegerea mi s-a parut dezastruoasa, iar acum din nou mi se pare inspirata. Am ales sa invat JavaScript, HTML, Flash, Actionscript etc. Am strans cativa bani din munca aceea si la un moment dat chiar mi-am pierdut zilele incercand sa fac diferite biznisuri cu site-uri. Aia da, a fost o porcarie. Dar la un moment dat vidul de algoritmica m-a impins sa programez in Flash diferite lucruri mai complicate: jocuri de puzzle, algoritmi asupra grafurilor, un fel de Flash construit in Flash (cu Mercutiu). Au fost unele lucruri care pe atunci cand nu vedeam viata din universitati mi se pareau varfuri de lance. De fapt erau varfuri de morcove infipt adanc in pamanat. Asta a fost si e.

Continuare a scurtei introduceri

In Alexandru Paler on 15 Decembrie 2012 at 19:02

Stochastic computing devine interesant când sunt luate în considerare erorile de tip bitflip, sau cum s-or numi în romana. Adică, când un bit iși schimbă valoarea: din 1 devine 0, din 0 devine 1. Datorită modului în care sunt definite valorile reprezentate de către șirurile de biți, bitflip-urile nu au un efect neapărat imprevizibil, deoarece, erorile se pot modela drept XOR-uri, deoarece 0 XOR 1 = 1 și 1 XOR 1 = 0 (iar operația XOR asupra șirurilor de biți are un efect calculabil). Pentru orice situatie însă, când numărul biților dintr-un șir este mare, flip-ul unui bit nu influențează puternic valoarea reprezentată de șir.

De aceea SC este bun in mediile în care erorile biților individuali sunt relativ mari, iar efectul lor trebuie să poată fi cumva controlat. Exactitatea calcului nu este cea mai importantă caracteristică, ci faptul că in sine calculul se desfășoară în anumite limite controlabile ale erorii. Un asemenea exemplu îl constituie rețelele neuronale, unde ponderea legăturilor între neuronii artificiali sunt reprezentată de către numere reale. Antrenarea rețelei care are loc, de exemplu, prin backpropagation (pentru care se calculează derivate succesive pornind de la erorile de aproximare obținute în ultimul strat al rețelei) nu este un proces tocmai exact, și de aceea nici ponderile legăturilor nu sunt necesare a fi calculate tocmai exact. Un alt exemplu este decodarea codurilor LDPC (low-density-parity-check codes) pentru care este necesară așa-numita belief propagation, iar acest algoritm poate fi eficient implementat folosind SC.

Scurta introducere in stochastic computing

In Alexandru Paler on 7 Decembrie 2012 at 21:52

Termenul „stochastic computing” nu cunosc a avea traducere in limba romana, de aceea pe parcursul acestui text introductiv, il voi folosi in forma lui engleza (devenind ambiguu voi folosi prescurea „SC” si pentru „stochastic computer”). Pagina de wikipedia dedicata subiectului detine doua versiuni, una engleza si una franceza. In franceza un stochastic computer este tradus drept „calculateur stochastique”.

Un SC este construit din porti clasice (AND, OR, NAND, XOR etc.) si opereaza pe numere reprezentate drept probabilitati, deci numere din intervalul [0,1]. O probabilitate este obtinuta din raportul dintre numarul de aparitii ale bitului 1 si numarul total de biti (lungime) a unui sir (de biti). Spre exemplu numarul 0,5 poate fi reprezentat folosind 2 biti: 01 sau 10. Pentru numarul 0,3 nu exista o reprezentare exacta pe 4 biti, dar cu 10 biti exista C_{10}^3 reprezentari, si fiecare dintre ele este corecta: 0000000111, 0000001110, … , 0010010100, …, 1110000000.