» »

Automatic Algorithm Invention with a GPU

Automatic Algorithm Invention with a GPU

terryww ::

Nisem opazil, da bi kdo to kje drugje omenil, se pa spomnim, da jih je blo nemalo navdušenih nad temi zadevami, tako da verjetno bo koga vseeno zanimalo predavanje, ki je bilo na 28c3 konferenci na to temo... Svoj čas je Thomas imel eno enostavnejšo verzijo, ki je tekla na cpuju, če se prav spomnim. skratka, tele evolucijske metode, sploh za generiranje algoritmov, so še vedno alive & kicking (skupaj z Johnom Koza-om) in seveda se še vedno pišejo članki na to temo.
Škoda, da se teh tehnik ne uporablja... Ve kdo za kako uporabo iz prakse, mogoče da je uspelo kaki firmi, kjer so se dovolj dolgo igrali, kako zadevo stržit? Svoj čas smo se pogovarjali s fanti iz aptine in optomotive, pa niso zgledali preveč navdušeni... ampak stvar očitno deluje.
It is the night. My body's weak.
I'm on the run. No time to sleep.

Fave ::

Najprej hvala za link. Poučno in vredno ogleda.

Nevone in Thomas sta Critticall ponujala na netu free skoraj 10 let nazaj že. In še vedno ga. En Critticallov derivat je iTimeTable, ki služi reševanju urniških problemov. Sodeč po listi referenc na strani algit.eu, ga tudi uspešno tržita. Izboljšal je tudi rezultate pakiranj in naredil še Akritos, ki poišče algoritem, ki napove najpravilnejšo vrednost v neki številski sekvenci (najpravilnejši je tisti za katerega porabiš najmanj logičnih opracij, da ga izračunaš). Enkrat mi je razlagal, da je v 90-ih (!) napravil program GENERAL (GENERator ALgoritmov). V 90-ih!

Ko sem prvič tule videl, da se da na tak način optimizirati algoritme sem bil fasciniran, pa niti nisem programer. Ampak imam občutek, da se zadeva prepočasi "prijemlje" pri ljudeh. To je žalostno. Dejansko je Critticall uporabljala le peščica ljudi. Zadnjič sem se pogovarjal z nekom iz FRI-ja, sem dobil občutek, da nima pojma o avtomatski optimizaciji algoritmov...;((

"ampak stvar očitno deluje."

Pa še kako deluje!
My mind's a hyper tool that fixes everything.

msjr ::

Stvar je zaradi večanja procesorske moči vsako leto bolj realna. Thomasov algoritem (pridobljen s pomočjo [mislim da predhodnika] critticalla) za stiskanje videa je bil konec devetdesetih top of the top, edina slaba stvar je bilo zelo počasno stiskanje videa pa tudi počasno "pridobivanje" novih algoritmov, so bili pa takrat pentiumi 100 večinoma, tako da bi šlo zdaj dosti hitreje.

Je pa tako, da moramo dobro definirati rezultat, pri "simulaciji" sabljanja je critticall pogrnil, ker je sta se "borila" dva algoritma in sta se med sabo dobro pikala, ampak človek je človek in hitro pogrunta kakšno levo finto, kot je bila kombinacija desno - gor - in potem samo proti nasprotniku in takrat ni znal najti protiudarca. Vprašanje je, kako bi se razvila igra ob več generacijah, ampak moje mnenje je, ob podanih definicijah ne bi dosegli boljšega rezultata.

Se pravi, pri optimizaciji algoritma je najpomembnejše to, kako definiramo najboljši algoritem za neko stvar. Pri sortu, kompresiji ipd. je to enostavno, ko gremo na malo bolj kompleksne probleme pa je kar jeba, težko povem, ker vse to pišem s stališča nekoga, ki je te stvari testiral in uporabljal, mogoče Nevone pove kaj, če se že Thomas ne oglaša.

nevone ::

ko gremo na malo bolj kompleksne probleme pa je kar jeba,


Definitivno so danes pred nami problemi, ki so prekompleksni, da bi jih ta algoritem zadovoljivo reševal. Po drugi strani, je pa to edini pristop, ki sploh da kakšne rezultate za NP probleme v razumnem času.

Z večanjem procesorske moči in tudi izboljševanjem algoritmov pa je to pot spirale navzven.

Kar se tiče sabljačev, ki smo jih v 90-ih vzgajali s pomočjo tega algoritma, je res kar pravi msjr, da smo ju razvili bolj kot samostojne enote, ki sta se dobro borili ena proti drugi, ko pa je človek posegel s svojo strategijo, pa sabljač ni imel pravega odgovora, ker se s takšno strategijo pri učenju ni dovolj pogosto srečal. Če bi imeli več časa in CPU-ja, bi strategijo evoluirali naprej, bi se prilagodil tudi temu.

En zelo pomemben efekt, ki ga pokaže uporaba evolucijskega algoritma, je inovativnost, ki se zagotovi z random mutacijami.

Recimo, pri pakiranju krogcev v kvadrat je evolucija našla zelo zanimive postavitve, za katere bi človek potreboval precej več časa, ali pa se jih morda sploh ne bi domislil.
En tak zanimiv se nam je izračunal nedavno in je objavljen tukaj. (423 enakih krogcev v kvadrat)

Skratka tale digitalna evolucija da velik pospešek k izboljševanju vsega možnega.

o+ nevone
Either we will eat the Space or Space will eat us.

Zgodovina sprememb…

  • spremenila: nevone ()

terryww ::

tale dela na 28c3: Evolving custom communication protocols, evoluciji komunikacijseka protokola za medplanetarno komuniciranje (roverja pošiljajo na luno...) oz že imajo par kandidatov. na začetku lepo razloži čemu sploh potreba po takšnem pristopu reševanja problemov. priporočeno...

edit: popravljen link
It is the night. My body's weak.
I'm on the run. No time to sleep.

Zgodovina sprememb…

  • spremenil: terryww ()

WarpedGone ::

Recimo, pri pakiranju krogcev v kvadrat je evolucija našla zelo zanimive postavitve, za katere bi človek potreboval precej več časa, ali pa se jih morda sploh ne bi domislil.

No, ne pretiravat.
Če lahko mutacija priskrbi nek rezultat, lahko enako "idejo" dobi tudi človek. V principu. Kar je vse kar je važno.
Zbogom in hvala za vse ribe

terryww ::

@warped
ideja je v tem, da če imaš dobro hevristiko, se ti iskalni prostor seveda zmanjša, če še dodaš hitro procesiranje pa se včasih zgodi, da rezultati znajo konkurirat rezultatu, do katerega pride domenski specialist. in to se že par let (od ~80') dejansko dogaja... prej so bile take metode konkurenčne samo lažjim problemom, danes pa se napadajo tudi bolj kompleksni, in če preletiš drugo predavanje, vidiš da so rezultati konkurenčni algotu, ki so ga dizajnirali domenski specialisti. kompi so pač bolj skalabilni kot skupina ljudi, ki rešuje nek probl...
It is the night. My body's weak.
I'm on the run. No time to sleep.

nevone ::

Če lahko mutacija priskrbi nek rezultat, lahko enako "idejo" dobi tudi človek. V principu. Kar je vse kar je važno.


Je pa vseeno zanimivo, kako sta človek in program začela konkurirat v novih idejah.

To, da je tudi računalniški program lahko inovativen je velik napredek od računalniškega programa kot avtomata, pri katarem je rezultat kalkulacije determiniran s strani človeškega operaterja.

o+ nevone
Either we will eat the Space or Space will eat us.

Zgodovina sprememb…

  • spremenila: nevone ()

WarpedGone ::

Tudi "inovativen" program je še vedno samo avtomat.
Random generator je samo način kako se izbere naslednje stanje iz ogromne množice možnih stanj. Še vedno je zadeva zaprt sistem in s tem popolnoma determiniran v tem kaj lahko počne/nardi.

Predno me napadete kako ne razumem napredka - ne se trudit, stvar je napredek, je uporabna in ima potencial. Ni pa tolk 'presunljiva' kot bi kdo želel pokazat. Če so mnogi bli kratkovidni kaj avtomat lahko dela, je to bol znak njihovega omejenega dojemanja realnosti, kot veličine dosežka.

Preboj bo, ko bojo mašine reševale porbleme, za katere se sploh ne zavedamo da jih mamo.
Zbogom in hvala za vse ribe

nevone ::

Tudi "inovativen" program je še vedno samo avtomat.


A je kdo rekel, da ni?

Random generator je samo način kako se izbere naslednje stanje iz ogromne množice možnih stanj. Še vedno je zadeva zaprt sistem in s tem popolnoma determiniran v tem kaj lahko počne/nardi.


Razlikuje se v toliko, da programer ne pozna nujno rezultata, ki ga tak avtomat vrne.

Predno me napadete kako ne razumem napredka - ne se trudit, stvar je napredek, je uporabna in ima potencial. Ni pa tolk 'presunljiva' kot bi kdo želel pokazat. Če so mnogi bli kratkovidni kaj avtomat lahko dela, je to bol znak njihovega omejenega dojemanja realnosti, kot veličine dosežka.


Za vsako stvar, ko je enkrat obelodanjena lahko to rečeš. Kar pa seveda ne zmanjša veličine mnogih dosežkov, pa tudi tega dosežka ne. Ti pa kar ostani skromen, če misliš, da je to kakšna posebna vrlina.

Preboj bo, ko bojo mašine reševale porbleme, za katere se sploh ne zavedamo da jih mamo.

Ja, ampak preboj se počasi bliža preko takšnih dosežkov, kot je recimo tale. Evolucija, veš.

------------------

Tule je še eden, ki trdi, da je randomness sámo bistvo kreativnosti! Link.
Either we will eat the Space or Space will eat us.

msjr ::

WarpedGone je izjavil:

Tudi "inovativen" program je še vedno samo avtomat.


Ja, zanimivo bi bilo, če bi naredili kodo, ki ne bi imela v "genih" cilja, ampak samo zapovedi, kot so razmnožuj se, uporabi čimveč procesorja, dobro se skrij, ne delaj sranja po mašinah (tukaj bi po moje po generacijah le delala sranje) in jo spustili na net (v bistvu zelo tvegana ideja). Kar se tiče randoma pa je isto kot pri naravni evoluciji, s tem da na mašinah seveda poteka hitreje.

Nič, grem še nekaj spit, dosti razmišljanja za danes.

Fave ::

>"Tudi "inovativen" program je še vedno samo avtomat."

In? Vse je avtomat. Resno to trdim. Če pa slučajno to Vesolje ni avtomat...pol smo pa (še) za nekaj časa v riti.

Jaz sem siguren, oz. je nujno, da je Vesolje avtomat. In s tem, ko rečem Vesolje mislim _vse_. Samo tolk, da bo jasno.
My mind's a hyper tool that fixes everything.

WarpedGone ::

Ja, vse je končen avtomat. Zna bit da tut determinističen.

V mislih sm mel pojmovanje avtomata v smislu "Razlikuje se v toliko, da programer ne pozna nujno rezultata, ki ga tak avtomat vrne." Avtomat v smislu simple zadevce, kjer ni težko razumet povezave med outputom in inputom - takšno naivno pojmovanje avtomata.

V vseh uporabnih primerih programer ne pozna točno kakšen rezultat bo padel iz avtomata, v vseh primerih pa programer DEFINIRA možen končno velik nabor možnih rezultatov in tudi, kakšen mora biti konkreten rezultat.

Random je izključno bližnica mimo "Exhaustive searcha" in čisto nič več. Je kreativen v tem, da so njegovi rezultati v enakem času lahko precej bolši od Brute-Force pristopa. Se pravi, je to samo časovna optimizacija, ne širi pa polje možnega.

Polje možnega se razširi nekako s tem kot msjr študira - da ne vkodiraš konkretnih ciljev ampak samo neke aksiome, kaj je teb OK in kaj teb ni OK. In pol ga futraš z nekim (ne vem kakšnim) inputom in nej išče kako bo teb to kar je OK maksimiziral in minimiziral tisto kar ni OK. Tudi pri tem je random samo časovna optimizacija al pa izogibanje hard-codiranim pravilom, katerih sploh ne znaš definirat.
Zbogom in hvala za vse ribe

nevone ::

Se pravi, je to samo časovna optimizacija, ne širi pa polje možnega.


Ne razumem, čemu tukaj ugovarjaš. Saj možno je, kar je pač možno, tega ne more širiti nihče. Je pa zelo pomembna časovna optimizacija, ki ti daje nove (boljše) rezultate, ki jih ti (še) nisi našel.

o+ nevone
Either we will eat the Space or Space will eat us.

rasta ::

nevone je izjavil:

Ne razumem, čemu tukaj ugovarjaš. Saj možno je, kar je pač možno, tega ne more širiti nihče. Je pa zelo pomembna časovna optimizacija, ki ti daje nove (boljše) rezultate, ki jih ti (še) nisi našel.


Mislim, da predvsem svari pred pretiranim entuzijazmom, t.i. hype-om, ki ga je po tem forumu predvsem širil Thomas.
Genetski algoritmi naj bi sami po sebi pomenili iznajdbo umetne super-inteligence, le na "dovolj zmogljivem" računalniku bi jih bilo treba pognati. Pri tem je bilo prezrto, da nimamo niti konsistentne cenilke oz. postavitve optimizacijskega problema in da se trenutne izvedbe lahko lotijo le dokaj preprostih algoritmov (npr. iskalni algoritmi, nekako 100 vrstic kode) zaradi problemov s skalabilnostjo.

Tak hype je škodljiv. Konec šestdestih je zavril razvoj neuronskih mrež za dve desetletji, ker zaradi diskreditacije (oz. neizpolntive pretiranih pričakovanj) preprosto ni bilo mogoče dobiti financiranja.

nevone ::

Genetski algoritmi naj bi sami po sebi pomenili iznajdbo umetne super-inteligence, le na "dovolj zmogljivem" računalniku bi jih bilo treba pognati. Pri tem je bilo prezrto, da nimamo niti konsistentne cenilke oz. postavitve optimizacijskega problema in da se trenutne izvedbe lahko lotijo le dokaj preprostih algoritmov (npr. iskalni algoritmi, nekako 100 vrstic kode) zaradi problemov s skalabilnostjo.


A ni čudno, da je prav evolucija pripeljala do človeške inteligence. Čemu bi bilo prepovedano izjaviti, da digitalna evolucija lahko pripelje do AI. Ampak ta tema sploh ni bila odprta s tem namenom, da bi govorili o superiorni AI, ki iz tega izide. Ta hype si sedaj povzročil ti. Tema govori o optimizacijah, ki so povsem uporabne za vsakdanjo rabo, in do katerih lahko učinkovito prideš s takim pristopom.

Tak hype je škodljiv. Konec šestdestih je zavril razvoj neuronskih mrež za dve desetletji, ker zaradi diskreditacije (oz. neizpolntive pretiranih pričakovanj) preprosto ni bilo mogoče dobiti financiranja.


Nobena izboljšava sama po sebi ne pomeni zaviranja česarkoli. To so samo izgovori. Če imaš boljše orodje delaj z njim. Mi (Thomas) ti ne vsiljuje ničesar. Tudi to je samo tvoj hype.

o+ nevone
Either we will eat the Space or Space will eat us.

rasta ::

nevone je izjavil:

Ampak ta tema sploh ni bila odprta s tem namenom, da bi govorili o superiorni AI, ki iz tega izide. Ta hype si sedaj povzročil ti. Tema govori o optimizacijah, ki so povsem uporabne za vsakdanjo rabo, in do katerih lahko učinkovito prideš s takim pristopom.

Ja, prav imaš. Moj post je vsaj malo trollovski in odličen nastavek, da se tema izrodi.
Moderatorji ga lahko izbrišejo.

nevone je izjavil:

Nobena izboljšava sama po sebi ne pomeni zaviranja česarkoli. To so samo izgovori. Če imaš boljše orodje delaj z njim. Mi (Thomas) ti ne vsiljuje ničesar. Tudi to je samo tvoj hype.

Genetski algoritmi so pomebna pridobitev in so marskije povzročili pravo malo revolucijo in postali nepogrešljivo orodje na številnih področjih (npr. black-box modelling).
Problem pretiranih in nerealnih pričakovanj, omenil sem primer nevronskih mrež v 60tih, pa nastane, ko se ta ne izpolnijo (čeprav se izboljšava izkaže za pomembno) in posledično metoda pride (neupravičeno) na slab glas. Posledica tega pa je, da raziskovalci ne dobijo financiranja (ker recenzorji ne odoborijo njihovih projektov zaradi mnenja nekaj vplivnih ljudi v panogi) oz. če že hočete, investitorji se ogibajo tovrstnih podjetij.
Izredno lep (in poučen) primer so nevronske mreže, niso pa edini.

Sedaj pa dovolj off-topic-a.


Vredno ogleda ...

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

Evolutionary computation a.k.a Digitalna evolucija (strani: 1 2 3 )

Oddelek: Znanost in tehnologija
10516300 (14148) Double_J
»

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

Oddelek: Znanost in tehnologija
141673212 (23381) pietro
»

Packing (strani: 1 2 3 )

Oddelek: Znanost in tehnologija
1238825 (4632) Thomas
»

It means business (strani: 1 2 3 4 5 6 7 8 )

Oddelek: Znanost in tehnologija
37427109 (13108) Thomas
»

Petaflopsu naproti (strani: 1 2 3 )

Oddelek: Novice / Procesorji
1058146 (8146) Marjan

Več podobnih tem