» »

It means business

It means business

Fave ::

Valentin, je Thomas že povedal. To je primer, ko je Quick hitrejši. Oziroma ima pri tem (malem) random sampleu vsaj manj pisanja, kot Artificial.
My mind's a hyper tool that fixes everything.

Gundolf ::

Evo če jaz popravim qsort (dodam median of 3) tako da se še lepše obnaša v sortiranih primerih (pa še malo na hitrosti pridobi), potem je rezultat takle:

Rnd-Rnd
size = 10000000, rnd. param = 10, avg element freq. = 526315.812500 asort time = 360, qsort time = 360, gcc std::sort time = 690
size = 10000000, rnd. param = 1000, avg element freq. = 5002.501465 asort time = 840, qsort time = 880, gcc std::sort time = 980
size = 10000000, rnd. param = 100000, avg element freq. = 25.582710 asort time = 1360, qsort time = 1430, gcc std::sort time = 1340
size = 10000000, rnd. param = 10000000, avg element freq. = 1.173663 asort time = 1710, qsort time = 1820, gcc std::sort time = 1490
size = 50000000, rnd. param = 10, avg element freq. = 2631579.000000 asort time = 1870, qsort time = 1830, gcc std::sort time = 3930
size = 50000000, rnd. param = 1000, avg element freq. = 25012.505859 asort time = 4340, qsort time = 4440, gcc std::sort time = 5340
size = 50000000, rnd. param = 100000, avg element freq. = 125.566620 asort time = 6880, qsort time = 7210, gcc std::sort time = 7000
size = 50000000, rnd. param = 10000000, avg element freq. = 1.976015 asort time = 9260, qsort time = 9980, gcc std::sort time = 8380

i+Rnd
size = 10000000, rnd. param = 1000, avg element freq. = 1.581602 asort time = 1020, qsort time = 4050, gcc std::sort time = 940
size = 10000000, rnd. param = 10000000, avg element freq. = 1.220319 asort time = 1680, qsort time = 1820, gcc std::sort time = 1490
size = 50000000, rnd. param = 1000, avg element freq. = 1.581695 asort time = 5390, qsort time = 33760, gcc std::sort time = 5040
size = 50000000, rnd. param = 10000000, avg element freq. = 1.484739 asort time = 8920, qsort time = 9790, gcc std::sort time = 8280

-i-Rnd
size = 10000000, rnd. param = 1000, avg element freq. = 1.581602 asort time = 1030, qsort time = 2730, gcc std::sort time = 950
size = 10000000, rnd. param = 10000000, avg element freq. = 1.220319 asort time = 1690, qsort time = 1850, gcc std::sort time = 1520
size = 50000000, rnd. param = 1000, avg element freq. = 1.581695 asort time = 5780, qsort time = 18460, gcc std::sort time = 5390
size = 50000000, rnd. param = 10000000, avg element freq. = 1.484739 asort time = 9200, qsort time = 9950, gcc std::sort time = 8300

To je laufalo na opteronu. Moja mašina še vedno preferira mojo kodo. Tule so pa rezultati tko večinoma predost za asort, kadar se elementi ne ponavljajo.Tko da moram priznat, it does mean business.

Bi blo pa zanimivo videt, kako bi se obnašal asort, če ne bi uporabljal tiste aritmetične sredine. Ker se mi zdi da ni ravno nujna za dobro delovanje. Ali pa tudi, bo Thomas povedal. Bi pa vsaj to naredilo algoritem tako splošen kot qsort (to in exkluzivna uporaba operatorja manjše). Do takrat bo pa po splošnosti asort nekje med qsortom in radixom.

Thomas ::

Kar se tiče aritmetične sredine, je tu zato, da ostane.

Lepo je definirana tako za integerje, kot floate.

Kar se tiče stringov, je pa zadeva naslednja. Recimo, da imamo stringa:

ABECEDA

in

ABEL

dokler sta si enaka, torej do ABE, ne naredimo nič. Na četrtem znaku se razlikujeta, torej C in L. Vmes med C in L je pa recimo H.

Torej je pivot ABEH.

Algoritem določevanja pivota je preprost, tudi za stringe, ArtificialSort je splošen kot Quick.

V tekmo z internim sortom "gcc std::sort" pa gremo, ko vidimo njegovo kodo. Ker je na steroidih. Da jih uporabimo še za Artificiala.

Kot je omenila že nevone, kazalčno (dosti hitrejšo) verzijo Artificiala že imamo. MMX nam pa tudi ne predstavlja nobenega problema in najbrž bomo potem ugnali tudi tisti IntelSort, ki s pridom izkorišča tiste advanced procesorske ukaze.

Ker ko si enkrat algoritemsko boljši, je vse drugo samo še rutina. Tudi gaini so pri boljšem algoritmu še večji.

Vendar, zaenkrat ostanimo pri temle. Čisti algoritemski kvaliteti.
Man muss immer generalisieren - Carl Jacobi

Jst ::

Kako boš pa sthreadal asort?
Islam is not about "I'm right, you're wrong," but "I'm right, you're dead!"
-Wole Soyinka, Literature Nobelist
|-|-|-|-|Proton decay is a tax on existence.|-|-|-|-|

Thomas ::

Threadanje gre lahko tako, da po prvi delitvi en thread prevzame levi del, drugi thread pa desni del niza, ker sta neodvisna.

Tretji in četrti thread se vklopita analogno.

Če imamo večjedrni procesor, se to splača.

Je pa zelo podobno threadanju Quicka.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Razlika med levo in desno particijo je pri Artificialu in QuickSortu v tem, da pivot (mejo) lahko pri Quicku vedno pričakujemo tako v levem, kot v desnem koncu hkrati, pri Artificialu pa kvečjemu v desni (večji) particiji.
Man muss immer generalisieren - Carl Jacobi

Jst ::

Tisto AS kodo, s katero sem jaz testiral, bi zelo težko spravil v več niti na takšen način, da bi se splačalo. Jaz sem se že pred časom igral s tem na p4ht in sem opazil okoli 30% hitrejše izvajanje. Sedaj imam Core2Duo in je boost še večji - seveda če uporabim verzijo z dvemi threadi: intel.com.

Sicer pa to ni verzija Qsorta, katera je priložena Intel C++ compilerju. Le-ta je še nekaj deset odstotkov hitrejši, kot primer na Intelovi strani.

---

Pri večnitni verziji QSorta se obe niti izvajajo nekako podobno dolgo - če se ne bi, potem nekako ne bi bilo smisla tega početi. Bi bil premajhen gain. Zato sem vprašal, kako bi sthreadal ASort. Ne vidim, kje bi se splačalo uporabiti večnitnost.

Če se boš spravil v večnitne vode, bi ti jaz svetoval, da to naučiš Critticall. Kajti dandanes postajajo večjedrni procesorji nekako standard - a programi oziroma algoritmi pa še vedno ostajajo enaki. Nitenje je postalo splošen problem. Če bi ti uspelo, da bi ta problem preložil na računalnik, tako kot si to naredil s Critticallom, bi bil to neverjeten uspeh. Sedaj se ljudje mučijo, da bi paralelizirali čimširši spekter problemov, pri tem pa velikokrat stvari tako zakomplicirajo, da potem algoritem sploh ni hitrejši. Critticall bi pa videl dosti stvari, katere so nam skrite - to si tako ali tako že dokazal. Predstavljaj si, če bi program sam ugotovil, da bi se zelo splačalo rešitev problema paralelizirat, potem bi dobil celo vrsto novih odjemalcev.

Upam, da kaj razmišljaš v to smer, ker se res splača. No, novim večnitnim uspehom nasproti!!
Islam is not about "I'm right, you're wrong," but "I'm right, you're dead!"
-Wole Soyinka, Literature Nobelist
|-|-|-|-|Proton decay is a tax on existence.|-|-|-|-|

Thomas ::

Kar se tiče nitenja Artificiala, se mi res zdi podobno nitenju Quicka.

Kar se pa tiče avtomatiziranja paralelizacije .... to si mi pa dal mislit! Na en zaguljen način gre že zdaj ... ampak kot sem rekel - si mi dal mislit!

Mislim.
Man muss immer generalisieren - Carl Jacobi

snow ::

To je zelo podobno urnikom tale paralelizacija.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

Thomas ::

Ja, pravzaprav ni nobene razlike med problemom urnika in problemom paralelizacije. Vsaj ne na načelni ravni.

Paralelizacija Artificiala in vsakega algoritma je torej urniški problem. Intel paralelizira svoj Qsort, kolikor sem razumu, na istočasnosti iskanja pivota in particioniranja. To je ena (dobra) rešitev, ki za Artificial res ne pride zelo v poštev.

Ampak jaz bi paraleliziral tako Quick kot Artificial na tak način, da vsak nov procesor, ki je na razpolago, prevzame novo izračunan segment.

Ker segmentov za podelat je kmalu zelo veliko.

Nisem pa prepričan, da je to optimum. Optimum bi bilo potrebno zevoluirat. Mislim, da bi dobili kaj nepričakovanega.
Man muss immer generalisieren - Carl Jacobi

Jst ::

> Mislim, da bi dobili kaj nepričakovanega.

Ja, še posebej, če bi C. sam ugotovil najboljši način komunikacije med jedri. Ne samo ustvaril dva neodvisna threada. Potem bi najbrž res samo čudno gledali. Samo to se mi zdi čisto drug tip problemov, kot pa problemi s katerimi se ukvarja C.
Islam is not about "I'm right, you're wrong," but "I'm right, you're dead!"
-Wole Soyinka, Literature Nobelist
|-|-|-|-|Proton decay is a tax on existence.|-|-|-|-|

lymph ::

Thomas, a critical deluje tako da mu ti v določenih segmentih kode poveš kateri stringi so uporabni in jih on potem random daje not in meri razlike s prejšnim algoritmom? I don't get it :D
"Belief is immune to counter example."

Thomas ::

lymph,

Critticall deluje po najboljših manirah evolucije. Vsakršne kombinatorično možne mutacije, ki večinoma delajo program popolnoma neuporaben, vsake toliko pa le precej slabši od originala.

Vsakih par tisoč ali milijonov poskusov pa vendarle rahlo boljšega, kar se pa počasi akumulira.

Hard core evolution brez kakršnegakoli nespametnega mehčanja.

It's a do or die za v tej mašini porajajajoče se bitne stringe.

Jst,

meni se pa to zdi dokaj ista mineštra. Navsezadnje, lahko namesto sorta napišeš simulacijo mašine, na kateri poteka sort, pa to potem evoluiraš! Tako ni nobena evolucijska pot načelno zaprta.
Man muss immer generalisieren - Carl Jacobi

Jst ::

To je res, ampak nima vsak cpu enako dolge ukaze. Recimo Intel je najavil, da bodo novi procesorji bili štirikrat hitrejši v korenjenu. Kar hočem povedati je, da ni vsak ukaz na vsakem cpuju enako dolg. Pa še problem je v tem, da proizvajalci radi skrivajo podatke. Zato pravim, da je to malo drugačen problem. Sedaj CR deluje samo na algoritmih, to kar sem jaz opisal, pa je že low level hardware optimization. Čeprav moram premisliti, če bi se tole sploh splačalo. Kajti z vsako generacijo CPUja se dolžina ukazov spremeni. Ali nas to sploh zanima? Hja, v primeru multicore CPUjev nas že zanima koliko jeder ima, a da bi nas pa zanimalo za vsak tip procesorja, koliko dolge ukaze ima, pa še ne vem.
Islam is not about "I'm right, you're wrong," but "I'm right, you're dead!"
-Wole Soyinka, Literature Nobelist
|-|-|-|-|Proton decay is a tax on existence.|-|-|-|-|

Thomas ::

Manj kakršnihkoli ukazov je bolje, kot več kakršnihkoli ukazov.

Zato si skoraj ni mogoče zamisliti procesorja, ki bi hitreje izvajal BubbleSort od QuickSorta. Vsaj ne uporabnega procesorja.

Kadarkoli smo algoritem poenostavili v smislu, da potrebuje manj operacij za neko delo, smo IMHO naredili dobro delo, ki ga bodo novejši in optimalnejši procesorji še bolj nagradili, kot ga že nagrajujejo današnji.

Fora ArtificialSorta je ravno v tem, da ne sorta posortanega. Da se drži principa - don't fix, if aint broken.

Algoritmika je vsaj nekoliko processor independent.
Man muss immer generalisieren - Carl Jacobi

Jst ::

Kaj sem pa jaz napisal? Da je deep down optimizacija lahko sizifovo delo. Kajti če poenostaviš za en tip procesorja, lahko hkrati zakompliciraš delo drugemu.

Že če v programu uporabiš dve niti si stvar zakompliciral. Na (recimo) Pentium M bo delal dosti počasneje, a hkrati na Core 2 Duo pa dvakrat hitreje. Kako boš potem ocenil za koliko si optimiziral?

CR dela samo z algoritmi*. Kako boš pa v algoritmu definiral niti? Ne moreš. Lahko samo v neki kodi. Kar je compiler(+OS)-specific.

---

*
Lahko pa vseeno CR pripraviš do nitenja. Kar bi bil kar znaten napredek za velik spekter problemov. Jaz bi na tvojem mestu sprogramiral direktivo, koliko niti lahko uporabi.
Islam is not about "I'm right, you're wrong," but "I'm right, you're dead!"
-Wole Soyinka, Literature Nobelist
|-|-|-|-|Proton decay is a tax on existence.|-|-|-|-|

Thomas ::

Kot poudarjam že nekaj let na eni podstrani od Critticalla, je za vsak niz ali tip nizov optimalen drugačen sort. Tam imam prav naveden optimalni (?) sort za primer sortiranja 5 elementov. Ta je boljši od vsakega insertion, quick ali artificial sortiranja. Ampak samo za 5 elementov.

Nišnih sortov je kolikor je niš, kar je skoraj toliko kolikor je možnih nizov. Res pa je, da so mnogi tudi (praktično) enaki.

Za drugačne in multiple procesorje se pa zadeva še nekoliko zakomplicira. Pomnoži se množica algoritmov.

Bistveno pri celi zgodbi je pa to, da se v vsakem primeru stvar lahko zevoluira. Kakršni pogoji že so. Magari skrajno počasen RAM, magari kvadratna cena razdalje na kateri smo prenesli dva elementa. Iz slednjega evoluira ene pasme bubble iz quicka. Smo že probali.

Samo mene sorti ne zanimajo več tako zelo. Če bom 1. aprila 2010 znal obvladovati (vse več) atom(ov) s tole mašinerijo, bom poslal o tem post semle. ;)
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Man muss immer generalisieren - Carl Jacobi

Thomas ::

A se vam zdi diagram poteka, kako fajl prehaja iz neposortanega v čedalje bolj posortano obliko jasen in informativen? Al ne?
Man muss immer generalisieren - Carl Jacobi

Vesoljc ::

lustno :)

se precej placa za izboljsavo :p
Abnormal behavior of abnormal brain makes me normal...

Thomas ::

Se strinjam. Eno izboljšavo imamo že.

In kokr me sort ne zanima prav preveč, psihološki aspekt me. Kako hudiča smo lahko vsi prezrli dejstvo, da se splača testirat eventualno že-posortanost segmentov? Sej če jo zanemarjamo, kar je kakor velika vrlina Quicka, moramo segment še parkrat razdrobit brez taprave potrebe.
Man muss immer generalisieren - Carl Jacobi

lymph ::

Kako hudiča smo lahko vsi prezrli dejstvo, da se splača testirat eventualno že-posortanost segmentov? Sej če jo zanemarjamo, kar je kakor velika vrlina Quicka, moramo segment še parkrat razdrobit brez taprave potrebe.


Zakaj pa se splača testirat že posortirane segmente? A išče vzorec? Nekak ne vidim razloga, zakaj bi se to splačal delat.
A se da komu v logičnih korakih razložit operiranje ASorta proti Quicku?

Sam ti tole kar odpre oči, treba se je vprašat, koliko je še potencialnih zlo lossy algoritmov, ki se jih uporablja. Pomoje bi blo pametno poiskat nek podobno, če ne še bolj, uporabljen algoritem in ga dat prežvečit. Sej, če je stvar manj kompleksna, še ne pomeni, da jo je težje zevulvirati. My guess
"Belief is immune to counter example."

Thomas ::

> Zakaj pa se splača testirat že posortirane segmente?

Ker če imaš nek segment neposortan, je verjetno ta neposortanost tudi kmalu na začetku. Redko je samo na koncu. Hkrati s tem odkritjem "ordering broken place-a", pa dobiš zelo dobre vrednosti za izračun pivota.

Če pa je segment že posortan, moraš pa iti s primerjanjem, (ki je relativno hitra zadeva, saj se dela takorekoč sproti, ko bereš array na tistem segmentu) - do konca. VENDAR ne bo Artificial tega segmenta nikoli več polovičil (repetitivno!), kot je to pri Quicku. Namesto večkratnega polovičenja (četrtinjenja, osminjenja in tako naprej, sumarno celega!) segmenta, smo imeli eno samo enostavno primerjanje skozenj. Kar se mora splačat!

Poleg tega je še nekaj malih razlikic. Naprimer ta, da particioniranje segmenta pri Artificialu vrže pivot v desno polovico. Ne malo tu in malo tam, tako kot Quicksort, pač samo na desni. Kar je koristno. Mogoče bomo levega morali še sortat, pa bi se nam pivot brezveze valjal pod nogami.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

> treba se je vprašat, koliko je še potencialnih zlo lossy algoritmov, ki se jih uporablja.

Kamor pogledaš, so stvari presenetljivo daleč od optimima. To je prav hecno. Bi mislil, da razna "optimimumska zasičenja" se zgodijo kmalu. Samo ne!

Motor z notranjim izgorevanjem je že en tak lep primer. Ga pilijo, pa pilijo, pa pilijo ... in ni konca. Stalno boljši postaja. Resda počasi, ampak prostor inovacij je presenetljivo velik in v začetku so bile povsem nepredstavljive.

Po drugi strani, karkoli vržeš v malaričnega komarja, že zevoluira nek defence. Ali pa v rakavo celico, ali pa v viruse.

Intuitivno bi človek rekel, da se napredovanje reči konča precej hitro. To je kamena sekira, kaj še češ boljšat tle? Morda par 1000 let res ne dosti, ampak slejkoprej se evolucija te forme primatra na nekaj bistveno drugačega. Kdo bi to rekel, 10000 let nazaj?!

Zato jaz mislim, da že sam volumen algoritmov se da povečati za faktor milijarda, ali pa še mnogo več. Pa da praktično noben ne bo ostal tak, kot je danes.

Ljudje smo slepi ko krti, se vidi takole. Crittical je tudi slep ko krt. Samo bolj pridno tipa v temi, kakor tipajo ljudje.

Ko se bo algoritemska mrgolazen začela organizirano obnašat, bo lep hec.
Man muss immer generalisieren - Carl Jacobi

.:noir:. ::

Med gledanjem latest videa by Ben, sm na 00:30:05 minuti zasledil razlago uporabe Genetic algoritma Moses pri razvoju AGI.

zdej nevem ce sem dal to v pravo temo, ali pa ce je bilo kje ze to kdaj omenjeno, me zanima, kako se Critticall razlikuje od Mosesa...oz ce delata na kak podoben nacin?

Zgodovina sprememb…

  • spremenil: .:noir:. ()

Thomas ::

Je ena precej velika razlika med Critticallom in Mosesom. Na videz sicer majhna, a zelo pomembna.

Moses skuša pametno naciljati, Critticall pa je glup ko toćak.

Po moje je to velik advance za Critticall, Ben se pa ne bi strinjal, jasno. Ko se nekega dne bo, mu bo ratalo.

Moram pa povedati tudi to, da v nekaterih variantah Critticalla je nevone vpeljala že precej mosesacije. Kratkoročno zelo uporabno zlasti za industrijski urnik, na dolgi rok in za velike količine CPUja, pa ni pametno.

Šteje namreč samo dosežek, ne pa dosežek vedno znova in hitro. Moses je delno blind, tako kot tudi nekateri Critticall dialekti z vgrajenimi smart mutacijami.

Genialno je tisto, kar bi bilo skrajno neumno, če ne bi bilo po nekem čudežu resnično.

Zato moramo preiskovati ves prostor potencialnih rešitev, ne samo "vnaprej določeno dobrih".

Ko gre zares, je treba pričakovati nepričakovano. V šahu tudi žrtev vseh figur po vrsti, če tako lahko najhitreje zadaš mat.

To prinese samo RANDOM mutacija in testiranje izida. Ne "ekspertno znanje", da "žrtev kraljice je nujno slaba".
Man muss immer generalisieren - Carl Jacobi

Jst ::

> Po moje je to velik advance za Critticall, Ben se pa ne bi strinjal,
> jasno. Ko se nekega dne bo, mu bo ratalo.

Ratalo kaj?

Pred leti sem gledal eno njegovo predavanje in je govoril o različnih načinih za dosego določenega cilja. On je spisal program, ki kategorizira gene. Kateri geni so najverjetneje vpleteni v določeno bolezen/blont lase/... In za dosego tega je uporabil "glup ko toćak" pristop. Tako da on vsekakor uporablja *tudi* very generic genetic algorithms.

---

Sicer ne vem o čem je govoril, bom pa vsekakor pogledal, kaj ima za povedati na tem linku, ki ga je dal noir.
Islam is not about "I'm right, you're wrong," but "I'm right, you're dead!"
-Wole Soyinka, Literature Nobelist
|-|-|-|-|Proton decay is a tax on existence.|-|-|-|-|

Thomas ::

Vsekakor si poglej tale film. Zna biti, da več informacij o tem topicu ne bo nikjer več, nikoli.
Man muss immer generalisieren - Carl Jacobi

ivanuscha ::

Ej Thomas, mal offtopic sicer, sam me zanima kaj je z unim fizikalnim problemom, ki si ga ti odkril in poslal neki reviji(je bla tema kakšne pol leta nazaj tuki)? 8-)

Thomas ::

Off topic in nič ŠE ni.
Man muss immer generalisieren - Carl Jacobi

.:noir:. ::

Glede na strinjanje in nestrinjanje Bena, je mozno da zaradi nizke kompjuting moci ne gre na pure Random,da bi cimprej dosegu neke rezultate..ocitno se mu zdi racunica.. time in napredek na poti pametnega ciljanja veliko hitrejsi in vecji...kot ce bi se sedaj posluzeval poti "glup ko tocak"...

za naprej seveda...pa po critticallu...or they say :)

Thomas ::

> je mozno da zaradi nizke kompjuting moci

Jest mislim, da bi si moral Ben vizualizirati, da razpolaga z Blue Gene računalnikom, kakršen bo 2010. Ker če ima resen namen, bo tak računalnik tudi imel. Ali pa 1000 PS4 povezanih v klaster. Potem bi bil (še) bolj pogumen.

Samo ni panike, to bo sčasoma sam pogruntal.
Man muss immer generalisieren - Carl Jacobi

.:noir:. ::

Drugace pa v videu jamra..da nima tak computing powerja..kot ga majo npr. pri Googlu in glede na to, da on ni ravno pro hardware usmerjen (skoraj povsod trdi, da hardware se ni tako pomemen kot sami software algoritmi za dosego AGI) in v zadnjem predavanju na Googlu pravi, da bo najverjetneje AGI celo prej in da bo mogu pocakat da se hardware razvije do te mere da bo v nekem real time vse skup zalaufal, od tam gre pa seveda vedno hitreje...

Zgodovina sprememb…

  • spremenil: .:noir:. ()

Thomas ::

Mah jest jim skoz pravim, naj se otresejo mitov kot "inteligenca", "AGI" in podobno. Da je vse samo evolucija in nič drugega.

Navsezadnje, tudi imunski sistem deluje po evolucijskem principu, pa zgleda, kako blazno je pameten, ko v parih dneh odkrije antitelesa za povsem neznane viruse. JE pameten, čeprav "samo random mutira in testira rezultat".

Kot vemo, je padla Nobelova nagrada za pojasnitev delovanja imunskega sistema z evolucijskim principom, pa jih še ne izuči. Mislijo, da so pa možgani narejeni po nekem drugem, "višjem" mehanizmu. Le od kod naj bi ga Mati Narava (v resnici evolucija sama) - vzela?!

Samo, bojo pogruntal počas.
Man muss immer generalisieren - Carl Jacobi

lymph ::

Eh thomas, kaj pa duša? :D
"Belief is immune to counter example."

gzibret ::

Karkoli že to je, je (najverjetneje) posledica evolucije. Sicer pa smo to že predebatirali n-krat (poglej v sticky temo Z&T povezave, čisto na dnu) in je tukajle, khmmm, rahlo offtopic.
Vse je za neki dobr!

Zgodovina sprememb…

  • spremenilo: gzibret ()

nicnevem ::

@Thomas
> Kot vemo, je padla Nobelova nagrada za pojasnitev delovanja imunskega sistema z evolucijskim principom..

Imaš v mislih Edelmana? Nekaj o tem sicer piše na temle linku, vendar nič o evolucijskem algoritmu, po katerem naj bi deloval imunski sistem. Saj bi sam iskal naprej, ampak ne utegnem, tako da bi se kak link prilegel. :)

@lymph
> Eh thomas, kaj pa duša?

Vprašanje sploh ni slabo - kaj pa občutek svobodne volje, samozavedanja, čustva, logično sklepanje ki ga izvajamo in ki ne izgleda kot trial and error proces...?!

Sem prepričan, da je evolucijska razlaga primerna za določen aspekt določenega nivoja delovanja možganov (recimo v stilu Edelmanovega nevronskega darwinizma), vendar mislim da to še zdaleč ni celotna zgodba. Naši možgani so ogromen kup zvitih trikov, ki jih je nagrmadila evolucija v milijonih let. Če bi za vsem skupaj stal preprost evolucijski algoritem potem bi bili recimo šimpanzi samo nekoliko manj inteligentni od nas. Poleg tega, če pogledaš anatomijo možganov je že na prvi pogled vidna visoka funkcijska specializacija, ki namiguje na "kup trikov"-pogled... Lepa regularna zgradbo možganov bi zelo hitro spravila nevroznanstvenike ob delo, ampak očitno stvari le niso tako preproste.

Tukaj mi pride na misel novica izpred nekaj tednov o simulaciji mišjih možganov, ki je bila hudo prenapihnjena. Tudi mišji možgani imajo namreč neko arhitekturo in ne le nekaj milijard naključno povezanih nevronov, ki so jih simulirali na tistem superračunalniku.Če bi v simulacijo vključili še telo in okolje v katerem bi se miš lahko gibala, bi hitro postalo jasno, da je inteligenca njihove simulacije praktično nična - torej mnogo manjša o mišje. En "čudežni" algoritem in legija nevronov ni dovolj.

Če bi imeli na voljo superračunalnik s 100-kratno močjo Blue Gena, koliko bližje bi bili samo-izboljšujoči inteligenci (in s tem Singularnosti), če bi poznali le evolucijski algoritem? IMO ne prav dosti. Bistvo je v razumevanju, ne v strojni opremi, kot rad reče Yudkowsky. :)
overcomingbias.com -- transhumanizem.org -- singinst.org

nicnevem ::

Da ne bo pomote: nikakor ne nasprotujem temu, da evolucijsko programiranje ne more proizvesti uporabnih rezultatov (že Thomasov ASort je protiprimer, najdel bi se pa še marsikak, recimo design antene za v vesolje), vendar za avtonomno inteligenco tak pristop ni dovolj. Razlogov za to je več: od tega, da mora še vedno človek izbrati predstavitev genoma, do tega, da evolucija po nepotrebnem preiskuje ogromen iskalni prostor, ko bi bil dovolj le nek trik in zato porabi ogromno računske moči. Poleg tega so težave še s Friendliness takega AIja...

Lahko pa evolucijski algoritem zapolni neko mesto v arhitekturi AGIja, tako kot pri Goertzlovem Novamente sistemu Moses opravlja vlogo učenja procedur in še marsičesa. Deluje pa v sodelovanju s probabilistično logiko, ki je mnogo primernejša za reševanje neke druge vrste problemov, hkrati pa pomaga pri oženju iskalnega prostora Mosesu...
50 letna zgodovina AIja nas je naučila da ene same čudežne rešitve/algoritma pač ni.
overcomingbias.com -- transhumanizem.org -- singinst.org

_marko ::

nicnevem:
Jaz sem dolgo casa bil preprican, da je tako kot ti mislis.
Ampak vedno bolj se mi zdi, da je vse le trial&error.


->Če bi za vsem skupaj stal preprost evolucijski algoritem potem bi bili recimo šimpanzi samo nekoliko manj inteligentni od nas.

Ne, fitnessa inteligenca ne poveca dovolj. Evolucija ne strmi najbolj k visji inteligenci, ampak SAMO k vecjem stevilu potomcev.
Seveda lahko reces, da je potem inteligenca sposobna ohranit populacijo. Kar seveda drzi.
Ampak ocitno so se tudi druge zivalske vrste ohranile, ki imajo nizjo inteligenco. So na drugacen nacin prilagojene.
Skratka, zelim povedat, da namen evolucije ni le visanje inteligence in da zato ne mores tega sklepat.

Ce pa bi za fitness evolucije bila najpomembnejsa inteligenca pa bi se Protokol ze zdavnaj zgodil.


->Poleg tega, če pogledaš anatomijo možganov je že na prvi pogled vidna visoka funkcijska specializacija, ki namiguje na "kup trikov"-pogled... Lepa regularna zgradbo možganov bi zelo hitro spravila nevroznanstvenike ob delo, ampak očitno stvari le niso tako preproste.

Se vedno ne razumem zakaj bi zapletena zgradba pomenila nekaj vec od navadne evolucije.


->Tukaj mi pride na misel novica izpred nekaj tednov o simulaciji mišjih možganov, ki je bila hudo prenapihnjena.

To IMO nima veze z evolucijo - tista simulacija je bila premalo kvalitetna.
Ce bi pa skeniral pozicije atomov pa sploh ni debate, da bi dobil identicno inteligenco. No, vsaj mislim, da je ni?!


-> Bistvo je v razumevanju, ne v strojni opremi, kot rad reče Yudkowsky. :)

Ce mene vprasas je bstvo v tem, da evolucija naredi "inteligenco", ki potem resuje npr probleme simulacije.
Za to pa rabis brute force pa recimo en dobro spisan "Criticall". Tale danes se ni dovolj splosen. Ane?
The saddest aspect of life right now is that science
gathers knowledge faster than society gathers wisdom.

Thomas ::

Ko se spet vidiva v živo, ti bom povedal, kako mislim, nicnevem. :)
Man muss immer generalisieren - Carl Jacobi

_marko ::

->nikakor ne nasprotujem temu, da evolucijsko programiranje ne more proizvesti uporabnih rezultatov (že Thomasov ASort je protiprimer, najdel bi se pa še marsikak, recimo design antene za v vesolje), vendar za avtonomno inteligenco tak pristop ni dovolj.

A nisma jaz pa ti ravno dokaz, da je za taksno inteligenco tak pristop dovolj?


->Razlogov za to je več: od tega, da mora še vedno človek izbrati predstavitev genoma, do tega, da evolucija po nepotrebnem preiskuje ogromen iskalni prostor, ko bi bil dovolj le nek trik in zato porabi ogromno računske moči.

Tudi naravna evolucija preiskuje ogromen iskalni prostor, ki ni ravno koristen. Ampak je hec, da ta tvoj trik lahko unici najboljso opcijo evolucije, ki je v tej generaciji pac skrita.
Potem je ta trik samo padec v rezultatu.


->50 letna zgodovina AIja nas je naučila da ene same čudežne rešitve/algoritma pač ni.

To sklepanje IMO ne more biti pravilno. Kako te lahko ta zgodovina to nauci, ko pa ji v vsakem trenutnu krvavo primanjkuje procesorske moci?
The saddest aspect of life right now is that science
gathers knowledge faster than society gathers wisdom.

Thomas ::

No, sej ti je že marko. Hehe ...
Man muss immer generalisieren - Carl Jacobi

nicnevem ::

@marko
-->Če bi za vsem skupaj stal preprost evolucijski algoritem potem bi bili recimo šimpanzi samo nekoliko manj inteligentni od nas.
-> Ne, fitnessa inteligenca ne poveca dovolj. Evolucija ne strmi najbolj k visji inteligenci, ampak -> SAMO k vecjem stevilu potomcev.

Drži, vendar to ni bil moj point (zanič pišem, ja). Finta je v tem, da je računska moč šimpanzjih (ali pa katerih drugih, velikih) možganov le nekoliko manjša od moči naših in če bi na obeh tekel evolucijski algoritem, bi bila razlika v inteligenci zelo majhna.

To je analogno primerjavi dveh Blue Genov: prvi naj ima 100 drugi pa 150 TFlopsov; če je algoritem na obeh enak, bodo rešitve na probleme, ki jima jih postavimo, na drugem le nekoliko boljše - ne pa razlike v stilu "civilizacija, ki je zgradila mesta, stopila na Luno" na eni strani in "preganjanje po gozdu in nabiranje borovnic" na drugi...

Iz tega sledi pač to, da smo ljudje toliko inteligentnejši zaradi bolj zvitih algoritmov, ki so implementirani v naših možganih.

-> Se vedno ne razumem zakaj bi zapletena zgradba pomenila nekaj vec od navadne evolucije.

Zgradba možganov je odsev algoritmov, ki tečejo na njih. Tako imamo vizualni in avditorni korteks, s svojimi posebnostmi, hipokampus ima spet drugačno zgradbo... in s tem neke svoje, specializirane algoritme, ki so primerni za domeno za katero je ta del možganov prilagojen. Hipokampus je recimo povezan s tvorbo spominov in prostorsko navigacijo - vsaj tako predvidevajo. Če bi na možganih tekel le en sam, evolucijski algoritem, od kod potem takšna specializirana zgradba?! Se strinjam, da je tole sklepanje nenavadno, vendar kljub temu mislim da je nekaj resnice v njem.

-> Ce bi pa skeniral pozicije atomov pa sploh ni debate, da bi dobil identicno inteligenco. No, vsaj mislim, da je ni?!

Itak. :)
Pomojem greš lahko celo mnogo nivojev višje... vse do večjih skupin nevronov.

-> Ce mene vprasas je bstvo v tem, da evolucija naredi "inteligenco", ki potem resuje npr probleme simulacije. Za to pa rabis brute force pa recimo en dobro spisan "Criticall". Tale danes se ni dovolj splosen. Ane?

Ja, to je ena izmed mnogih poti, ki pa je IMO daleč od optimalne. Bom v naslednjem postu malo pojasnil...
overcomingbias.com -- transhumanizem.org -- singinst.org

nicnevem ::

@marko
-->nikakor ne nasprotujem temu, da evolucijsko programiranje ne more proizvesti uporabnih rezultatov, vendar za avtonomno inteligenco tak pristop ni dovolj.
->A nisma jaz pa ti ravno dokaz, da je za taksno inteligenco tak pristop dovolj?

Sva, vendar pomisli na to, koliko računske moči je pokurila evolucija, da je proizvedla človeško inteligenco - naša celotna civilizacija s 6 milijardami možganov je kaplja v morje proti njej. Zato potrebujemo drugačen pristop in zato Ben tako poudarja pragmatične pristope k designu AGIja, ki jemjejo v zakup zelo omejeno računsko moč, ki nam je na voljo. Če ta ne bi bila problem, potem bi lahko implementirali Hutterjev AIXItl algoritem in imelu superinteligenco. Evolucijski algoritem je sicer mnogo učinkovitejši od AIXIja, vendar še vedno ne dovolj. Morda Novamente je...

-> Ampak je hec, da ta tvoj trik lahko unici najboljso opcijo evolucije, ki je v tej generaciji pac skrita. Potem je ta trik samo padec v rezultatu.

Mogoče si že slišal za področje kognitivne psihologije "heuristics and biases", ki proučuje takšne mejne primere, kjer triki (hevristike), ki jih uporabljajo naši možgani, odpovedo in vračajo napačne rezultate. Vendar so kljub temu te hevristike silno koristne, ker nam omogočajo da sploh karkoli naredimo v realnem času. Če bi vedno pognali nek splošen algoritem za prečesavanje iskalnega prostora.. bi nas kak medved že zdavnaj pojedel. :)

Popolnoma sploša inteligenca je nemogoča pri vsaki realno dosegljivi količini računske moči in zato je potrebno uporabljati razne hevristike in trike, ki delujejo v "samo v 99%" primerov... če je pa problem tako silno pomemben, pa še vedno lahko usmerimo dodatna sredstva v njegovo reševanje in poglobljeno preiščemo prostor rešitev.

-> Kako te lahko ta zgodovina to nauci, ko pa ji v vsakem trenutnu krvavo primanjkuje procesorske moci?

Misliš, da bi se računalnik 10^n-krat močnejši od Blue Gena na katerem bi bile implementirane neke naključno povezane nevronske mreže kar zbudil "sam od sebe"? I don't think so. To so včasih govorili za internet, vendar nič ne kaže, da bi mu z dodajanjem računalnikov zmotili spanec. Manjka pametnih algoritmov.. v tem je težava. :)


@Thomas
-> No, sej ti je že marko. Hehe ...

Sami sovražniki torej, hehe...
overcomingbias.com -- transhumanizem.org -- singinst.org

Thomas ::

V bistvu nisem zainteresiran, da mi glede tega kdorkoli verjame. Celo raje bi videl, če bi vsi mislili, kako se motim.
Man muss immer generalisieren - Carl Jacobi

BigWhale ::

Hm. Thomas, kaj bi se zgodilo, ce bi skozi critticall spustil eno hashing funkcijo. Sestavljeno primarno iz +=, ^=, ter nekaj shift leftov in shift rightov?

Ti jo lahko pripopam sem?

Sergio ::

Oziroma, če smo že tukaj, tut mene firbec matra, ampak za bolj preprosto funkcijo:

A XOR B

kjer sta A in B booleana.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.

Thomas ::

Pripopajta!
Man muss immer generalisieren - Carl Jacobi

BigWhale ::

Bom jutri, danes ne bom vec videl te kode. Zanima me, ce se da stvar kako pohitrit. Gre namrec za funkcijo, ki racuna hash nekega stringa in vrne ven unsigned long. Polno imen datotek in direktorijev in za vsako ime je treba narediti hash.

Torej, kakih pet milijonov stringov recimo. :) Vsakrsna pohitritev je dobrodosla.

Oziroma takole priblizno gre funkcija:

unsigned long hash4(char *key, int len, unsigned long hash)
{
  int i;
  for (i= 0;i < len; ++i)
  {
    hash ^= key[i];
    hash += (hash << 3);
    hash ^= (hash >> 5);
    hash += (hash << 7);
    hash ^= (hash << 11);
    hash += (hash >> 17);
    hash ^= (hash << 17);
  }

  return (hash);
} 


Hec je v tem, ker ne vem na pamet tistih shiftov in kako tocno si sledijo. :) Sedaj nisem preveril kaj tole ven vrze ampak v moji funkciji je rezulat zelo lepo distribuirani hashu po celem hash space-u in precej dober mixing bitov.

Zgodovina sprememb…

  • spremenil: BigWhale ()

BigWhale ::

Aja, pa hash funkcija mora ostat inkrementalna.

Ce racunam hash za SloTech mora biti isti, kot ce racunam hash za Slo in potem za Tech pri katerem podam hash od Slo kot input za Tech.


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Quick sort

Oddelek: Programiranje
102140 (888) drola
»

Digitalna evolucija (strani: 1 2 3 426 27 28 29 )

Oddelek: Znanost in tehnologija
141668608 (18777) pietro
»

dos C urejanje po velikosti

Oddelek: Programiranje
8997 (828) klemen22
»

[Turbo Pascal] Pomoč...

Oddelek: Programiranje
131194 (1096) Grey
»

sortirni algoritem v Cju

Oddelek: Programiranje
61169 (1021) GaPe

Več podobnih tem