http://prize.hutter1.net/
50'000€ Prize for Compressing Human Knowledge
Tee itse-ekstraktoituva softa, kooltaan alle 18MB, joka tuottaa 100MB wikipediatekstitiedoston. Tavoitteena on luonnollisella kielellä esitetyn ihmistiedon kompressoiminen. Palkkio on hyvä. Homma liittyy yleisen tekoälyn kehitykseen. Hutter itse olettaa (perustellusti), ettei tehtävä ole mahdollista ilman, että pakkausohjelma ymmärtää tiedon sisällön. Sivulla on paljon lisätietoja ja linkkejä.
50'000€ Prize for Compressing Human Knowledge
Tee itse-ekstraktoituva softa, kooltaan alle 18MB, joka tuottaa 100MB wikipediatekstitiedoston. Tavoitteena on luonnollisella kielellä esitetyn ihmistiedon kompressoiminen. Palkkio on hyvä. Homma liittyy yleisen tekoälyn kehitykseen. Hutter itse olettaa (perustellusti), ettei tehtävä ole mahdollista ilman, että pakkausohjelma ymmärtää tiedon sisällön. Sivulla on paljon lisätietoja ja linkkejä.
Vastaukset 21
Vanhimmat
Eikös teksti pakkaudu ihan perus rle-pakkauksellakin luokkaa 1:6 - 1:10, jolloin tuon pitäisi onnistua vaikka zippaamalla... :)
Täytyy kyllä todeta etten ihan noin isoja tekstitiedostoja ole koskaan pakannut, joten en osaa aivan varmasti sanoa.
Imuroitavissa oleva zippi on 34MB, ei mene pienemmäksi. Käy katsomassa. Vain vahvasti redundantit tekstit (esim. sorsatiedostot) menevät 1:10 kokoon. Faktaa kaikesta maailmasta sisältävä asiateksti on ihan eri asia: 1:3 on niillä kai todennäköinen.
Homman idea onkin, että nyt tarvitaan todella Älykästä pakkausta. Tehtävä EI ole helppo. Mutta lohtakin kannattaa kalastaa vaikkei saisikaan. Aloittaa voi FAQ:sta
http://prize.hutter1.net/prizefaq.htm
No jaa, ei ole sen paremmin aikaa kuin teoreettista osaamistakaan älykkään pakkauksen suunnittelemiseksi. Taitaa jäädä minulta väliin. :)
Aikoinaan tosin "kaverin tuttava" kehitti Jesus-packer -softan joka pakkaa mitä tahansa kahteen tavuun. Nimi tuli luonnollisesti siitä että tarvitaan jeesus purkamaan paketti. :)
Luulenpa ettei tiedon sisällön ymmärtäminen auta tässä kisassa. Ensimmäinen syy on se että tiedosto pitää palauttaa kirjaimellisesti oikein. Ihmiskieli on automaattisesti pakkautunut jo syntyessään: yleisimmät sanat ovat lyhyitä. Toinen syy on ettei purkuohjelma voi sisältää paljoakaan "taustatietoa". Jos kone tietäisi vaikka tennispelaajien nimet entuudestaan, ei niitä tarvitsisi kirjaimellisesti tallentaa pakettiin.
"Luulenpa ettei tiedon sisällön ymmärtäminen auta tässä kisassa. Ensimmäinen syy on se että tiedosto pitää palauttaa kirjaimellisesti oikein."
Lienet oikeilla jäljillä. On hieman outoa vaatia pakkaukselta virheettömyyttä jonkinlaisen älyn varjolla kun äly itsessään on kuitenkin pääsääntöisesti aika sumeaa. Jos pieni virhemarginaali sallittaisiin, niin kisa voisi olla mielenkiintoinen... (en kyllä lukenut kovin tarkasti sääntöjä)
Olisi tuo toisaalta mielenkiintoista kokeilla kuinka pitkälle pääsisi pelkällä datan jäsentämisellä ihan oman tiedon pohjalta. Kovakoodaisi pakkaajaan kaiken itse löytämänsä rakenteen ja jättäisi loput jollekin algoritmille, eli rakentaisi tätä tarkoitusta (ja tiedostoformaattia) varten oman pakkaajan.
"Luulenpa ettei tiedon sisällön ymmärtäminen auta tässä kisassa."
Se ei ainoastaan auta, vaan se on välttämätöntä.
Ymmärtäminen tarkoittaa tässä hieman syvällisempää ymmärtämistä kuin arkikielessä, siis tekstin elementtien, kirjainten, sanojen, ilmausten keskinäistä suhdetta. Niinkuin ihminen tekee lukiessaan ja ymmärtäessään jonkun tekstin. Ymmärtäminen on ennustamista. Ymmärtävä lukija, softa tai ihminen, lukiessaan ennustaa koko ajan seuraavaa merkkiä tai seuraavaa sanaa. Siis niitä mahdollisuuksia. Jos mikään mahdollisuksista ei tärppää, niin silloin menee enemmän muistitilaa, yleensä tärppää. Suosittelen tutustumaan joku Hutterin kirjaan (Universal Artificial Intelligence), tai jos se on liian vaikeaa (kuten minulle, olen yrittänyt) niin Jeff Hawkinssin "On Intelligence". Molemmat puhuvat samasta aiheesta, vaikka sitä ei heti huomaa. Heillä on ihan uusi, käytännöllinen käsitys siitä, mitä älykkyys ja ymmärtäminen tarkoittavat.
Tässä on lyhyempi ihan hyvä jottu:
http://cs.fit.edu/~mmahoney/compression/rationale.html
päinvastoin:
"Toinen syy on ettei purkuohjelma voi sisältää paljoakaan "taustatietoa". Jos kone tietäisi vaikka tennispelaajien nimet entuudestaan, ei niitä tarvitsisi kirjaimellisesti tallentaa pakettiin."
Ohjelma nimenomaan sisältää paljon taustatietoa. Sama tieto esiintyy yhä uudestaan lukemattomissa artikkeleissa eri muodoissaan, eikä sitä tarvitse perusmuodossaan tallentaa kuin kerran. Vain paikalliset eroavuudet on tallennettava (ne missä ennustus menee pieleen).
Ajatuksen on, että myös ihmisen mieli on tehokas tiedon kompressoija. Kompressoitua tietoa kutsutaan maailmankuvaksi. Ohjelma sisältää wikipedia-tiedoston maailmankuvan kaikkine detaljeineen.
Yritän nyt kovasti herättää jonkun mielenkiintoa: älykkyys on tärkeä käsite, mutta mielenkiintoinen ja vaikea, ehkä vaikein maailmankaikkeudessa. Minä pohdiskelen näitä juttuja, joko fiksumpikin voisi vaivautua.
"Ymmärtäminen tarkoittaa tässä hieman syvällisempää ymmärtämistä kuin arkikielessä, siis tekstin elementtien, kirjainten, sanojen, ilmausten keskinäistä suhdetta."
Nyt voidaan sitten kysyä mitä se ymmärtäminen sitten oikeasti on. Sinä puhut tuossa osaltaan myös kieliopista - englannin kielessä kielioppi laittaa (löysähköjä) rajoja tulevan sanan suhteen. Toisaalta tekstissä kyllä kieltämättä on myös "sisäistä ajatuksenjuoksua", josta kiinni saaminen voisi olla mielenkiintoinen tehtävä.
Olen joskus miettinyt tällaisen rakenteen mallintamista jonkinlaisella ryhmällä, mutta varsinaisen struktuurin rakentaminen ei ole helppo homma. Siihen pitäisi saada rakennettuja jonkinlaisia tasoja, joilta yhteneväisyyksiä voisi sitten hakea (tai johon niitä voisi tallentaa).
..kun olisi aikaa...
Jotakin vastauksia niihin voisi löytö tästä paperista:
http://www.numenta.com/Numenta_HTM_Concepts.pdf
HTM= Hierarchical Temporal Memory, aivojen arkkitehtuuri kielen ja muunkin maailmankuvan invarianttiin muodostamiseen.
"Vain paikalliset eroavuudet on tallennettava (ne missä ennustus menee pieleen)."
Eli sääntö ja poikkeukset, tai sääntö ja yksityiskohdat. hmm... Normaalisti voisi olla 60 000 sanaa/artikkelia/päätettä, ja ilmaisu veisi 16 bittiä. Jos jossain kohtaa tosi-ymmärrykseen perustuva sääntö antaa 8 mahdollisuutta, niin ne ilmaisee 3 bitillä...
Alkup. data eli erikoistapaus on yhtä kuin sääntö poikkeukset, tai sääntö yksityiskohdat.
Miksi muuten on sanonta "poikkeus vahvistaa säännön?"
"myös ihmisen mieli on tehokas tiedon kompressoija."
Häviöllinen sellainen. Kisaan tarvitaan häviötön, jotta voidaan mittailla, mutta eikö se ole hiukka ongelmallista?
"Olen joskus miettinyt tällaisen rakenteen mallintamista jonkinlaisella ryhmällä,"
Mikä ihmeen ryhmä? Ryhmäteorian ryhmä, työryhmä vai joku muu ryhmä?
Jos ryhmäteorian ryhmä, niin miten ihmeessä, kun en paljoa tiedä ryhmäteoriasta?
""myös ihmisen mieli on tehokas tiedon kompressoija."
Häviöllinen sellainen. Kisaan tarvitaan häviötön, jotta voidaan mittailla, mutta eikö se ole hiukka ongelmallista?"
Totta. Tämä on yksi biologisen muistin ominaisuuksista, se ei välttämättä ole vika. Siitä on välillä hyötyäkin.
Mutta se ei tarkoita, että HTM-periaatteella ei voisi toteuttaa myös häviötöntä pakkausta.
"Totta. Tämä on yksi biologisen muistin ominaisuuksista, se ei välttämättä ole vika. Siitä on välillä hyötyäkin."
Mielestäni sen pitäisi olla myös vahvan tekoälyn siemenälyn ominaisuus. Eikö siemenälylle olisi aika turhaa kyetä toistamaan kaikki havaittu sellaisenaan? Tehoa ja muistia pitää säästää - nykyisillä laitteistoilla ainakin.
"Mikä ihmeen ryhmä? Ryhmäteorian ryhmä, työryhmä vai joku muu ryhmä? "
Ihan ryhmäteorian ryhmä. Jos datassa on säännöllisyyttä, niin kai sitä pitäisi pystyä mallintamaan jonkinlaisella ryhmällä? En oikein jaksa uskoa tilastollisten menetelmien (MDL yms.) purevuuteen siinä määrin, että tällainen niillä onnistuisi.
"Jos ryhmäteorian ryhmä, niin miten ihmeessä, kun en paljoa tiedä ryhmäteoriasta?"
En minäkään niistä juuri mitään tiedä, mutta onhan tekstissä struktuuria jota pitäisi pystyä mallintamaan - kappaleet, lauseet, virkkeet, sanojen viittauksen taaksepäin tekstiin yms. Jos tällaisen säännöllisyyden saisi talletettua ryhmään, niin sehän mallintaisi tekstin rakennetta ja antaisi tavallaan ennustettavuutta.
..kunhan heittelen ajatuksia ilmaan, en ole tutkinut asiaa.
Tutustukaa nyt hemmetissä noihin linkkehin, mitä olen laittanut. Niistä löytyy valmiita, pitkälle ajateltuja lähestymistapoja.
Kun nyt ryhmistä puhutaan, niin yksi ryhmä voisi olla Marcovin Ketju yhdessä Bayesin Luokittelun kanssa:
http://www-users.cs.york.ac.uk/~jc/research/talks/york201005/talk.pdf
Teksti on helppo ymmärtää marcovin ketjuksi. HTM:n periaate ei mene kovin kaukaa.
Ei tarvitse toistaa kaikkea havaittua sellaisenaan. Kun tiedetään todennäköisyys, bittejä tarvitaan vähemmän.
Yksi kirjain voi mennä siis jopa bittiä pienempään tilaan. Aritmeettinen koodaus:
http://jole.fi/research/gradu/node37.html
Itseasiassa videonpakkaukseltakin edellytetään hahmontunnistusta kirjaimellisesti. MPEG-4:ssä videokuvasta pyritään löytämään sen eri osat (objektit: pöytä, tuoli, ihminen, ääni) ja käsittelemään niitä erikseen.
MPEG tulee varmaan kehittymään siihen että ohjelma erottelee näyttelijätkin toisistaan. Se on sitten jo lähellä kasvontunnistusta. Eli Hutter on oikeilla jäljillä.
* Create a Linux or Windows executable of size S < L := 18'324'887 = previous record.
* If run, it produces (without input from other sources) a [10^8] byte file that is identical to enwik8.
* If we can verify your claim, you are eligible for a prize of 50'000€×(1-S/L). Minimum claim is 500€.
* Restrictions: Must run with
Ongelma on se, miten voidaan tunnistaa, varastoida ja uudelleentuottaa ohjelmallisesti säännönmukaisuutta, sekvenssiä tai rytmiä.
Ohjelman tulisi syötetyn enwik8-tiedoston perusteella osata itsenäisesti päätellä mm. XML-datan käyttäytymisen säännöt, joka voidaan todistaa:
1. Datasta oikein ennustetuilla merkeillä
2. Korjaamalla virheitä/epäsäännönmukaisuutta
3. Generoimalla näköisdataa
Yksinkertainen esimerkki: XML-datan käyttäytymisen peukalosääntö luonnollisella kielellä:
"< ja > -merkit vuorottelevat"
Tapa jolla ohjelma havaitsee ja tallentaa tämänkin säännön on tässä oleellista. Ihminen huomaa nopeasti peukalosäännön, entä ohjelma?
Esimerkki ihmisen ja koneen eroista: Yritä muistaa luku 001001001001. On mahdotonta olla huomioimatta 001 x 4 sääntöä. Tietokone käsittelee luvun yleensä jonona.
Yleisesti sääntö halutaan tallentaa johonkin hiearkiaan tai neuroverkkoon. Onko varasto edes pakollinen vai kannattaisio lunttailla aiemmin syötetystä/dekompressoidusta datasta?
"Esimerkki ihmisen ja koneen eroista: Yritä muistaa luku 001001001001. On mahdotonta olla huomioimatta 001 x 4 sääntöä. Tietokone käsittelee luvun yleensä jonona.
"
Tuota eh, jo tavallinen perus-pkzip pakkaaja huomaa sen säännön ja käyttää sitä.
"
Onko varasto edes pakollinen vai kannattaisio lunttailla aiemmin syötetystä/dekompressoidusta datasta?
"
Täh?! Miten sitten voi dekompressoida ensimmäiset dekompressoinnit?
Tiedostoluokalle, kuten suomenkieliset gsm-tekstiviestit, oma esipakkaustiedosto (tai miten sitä nimittäisi?), joka on yhteinen kaikille ja jota ei lähetetä joka kerta? Näin kannattaisi pakata jopa 1 sanan viestejä.
"tavallinen perus-pkzip pakkaaja huomaa sen säännön ja käyttää sitä"
Se oli alkeellinen esimerkki ja zip on valmistettu juuri tuohon tehtävään.
http://www.ietf.org/rfc/rfc1951.txt
Kirjoitin: "Tapa jolla ohjelma havaitsee ja tallentaa tämänkin säännön on tässä oleellista." ja edellytän että ohjelma osaa itsenäisesti päätellä XML-formaatin säännöt esimerkkitiedoston perusteella.