David L. Dowe (Ed.) t f i r h c s t s e Algorithmic Probability F and Friends 0 7 0 7 Bayesian Prediction I A N and Artificial Intelligence L Papers from the Ray Solomonoff 85th Memorial Conference Melbourne, VIC, Australia, November/December 2011 123 Lecture Notes in Artificial Intelligence 7070 Subseries of Lecture Notes in Computer Science LNAISeriesEditors RandyGoebel UniversityofAlberta,Edmonton,Canada YuzuruTanaka HokkaidoUniversity,Sapporo,Japan WolfgangWahlster DFKIandSaarlandUniversity,Saarbrücken,Germany LNAIFoundingSeriesEditor JoergSiekmann DFKIandSaarlandUniversity,Saarbrücken,Germany David L. Dowe (Ed.) Algorithmic Probability and Friends Bayesian Prediction and Artificial Intelligence Papers from the Ray Solomonoff 85th Memorial Conference Melbourne,VIC,Australia,November30–December2,2011 1 3 VolumeEditor DavidL.Dowe MonashUniversity FacultyofInformationTechnology ClaytonSchoolofInformationTechnology Bldg.63,WellingtonRoad Clayton,VIC3800,Australia E-mail:[email protected] Coverillustration:Rayoftenmadeabstractdrawingsonhispagesofnotes. Thecoverimageisfrom1970. ©GraceSolomonoff ISSN0302-9743 e-ISSN1611-3349 ISBN978-3-642-44957-4 e-ISBN978-3-642-44958-1 DOI10.1007/978-3-642-44958-1 SpringerHeidelbergNewYorkDordrechtLondon LibraryofCongressControlNumber:2013951870 CRSubjectClassification(1998):I.2,F.1,H.3,I.4,I.5,H.4 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ©Springer-VerlagBerlinHeidelberg2013 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped.Exemptedfromthislegalreservationarebriefexcerptsinconnection withreviewsorscholarlyanalysisormaterialsuppliedspecificallyforthepurposeofbeingenteredand executedonacomputersystem,forexclusiveusebythepurchaserofthework.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheCopyrightLawofthePublisher’slocation, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Permissionsforuse maybeobtainedthroughRightsLinkattheCopyrightClearanceCenter.Violationsareliabletoprosecution undertherespectiveCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Whiletheadviceandinformationinthisbookarebelievedtobetrueandaccurateatthedateofpublication, neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityforanyerrorsor omissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,withrespecttothe materialcontainedherein. Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Picture of Ray taken by Grace on March 18, 1984, to accompany the 1985 article, “The Time Scale of Artificial Intelligence” Preface The Ray Solomonoff 85th memorial conference was held from Wednesday 30th November to Friday 2nd December 2011, to honour the work and life of Ray J. Solomonoff.Raywasnotjustapioneerincomputerscience,artificialintelligence and machine learning, he was a visionary whose work is still today increasingly impacting on the philosophy of science. He was well aware of the human and societal implications of his work, and he will probably one day also be seen as a pioneer in statistics, econometrics and (the relatively new terms) knowl- edge discovery, data mining, terabyte science, data science, big data, and data management and processing, etc. The conference was to honour Ray’s 85th birthday in 2011 but, after a full life well lived (and pioneering influential research), sadly, Ray died in Decem- ber 2009. The conference was held at Monash University’s Clayton campus in Melbourne, Australia. With a strong multi-disciplinary and international Program Committee in- cluding2TuringAwardwinners(andacorrespondinglystrongsetofreviewers), there were 40 submissions (in a variety of areas of Solomonoff’s work), each of which was reviewedat least twice and of which 30 were acceptedas long papers and1asashortpaper.Thesewereaccompaniedbyinvited(talksand)papersby nonelessthanGraceSolomonoff,Prof.LeonidLevin(BostonUniversity,U.S.A.) and Prof. Ming Li (University of Waterloo, Canada). There were over 40 conference delegates from countries including Australia, Brazil, Canada, China and England, Finland, France, Germany, Japan, Latvia, New Zealand, Poland, Sweden, Turkey and U.S.A., with the list of paper au- thors and co-authors also including Kuwait and Malaysia. (Other papers were submittedfromatleasttwoothercountries.)Hereandelsewhere,wethankthese contributors,thesponsors[AirForceOfficeofScientificResearch,AsianOfficeof Aerospace Research & Development, Grant number FA2386-11-1-1020AFOSR andAOARD; FacultyofInformationTechnology,MonashUniversity,Australia; NationalICTAustralia(NICTA),Australia],thepublishers(Springer)andother contributors. Electronic computers were involved in the conference in terms of (e.g.) elec- tronic type-setting, electronic presentations and (in some papers) rapid (faster than human) computer simulation of statistical and machine learning experi- ments. In the spirit of Solomonoff’s work, one wonders if, when and how com- puters might have an increasing - and, ultimately, super-human - involvement and influence on such activities. No matter how mathematical, philosophical or otherwise, and no matter how overtly or subtly, this theme of genuine machine intelligence underlies almostall (if not all)the papersin this volume. Pleaseen- joy the various angles and threads of this discussion throughout the conference VIII Preface proceedings, honouring a true pioneer who led by example, taught us so much, and gave good direction for the work now before you and work to follow. In choosing text for the front cover (title, inter-title and sub-title), vari- ous (combinations of) terms were considered - including Universal Turing Ma- chine (UTM). For an idea of some of the other terms and notions considered, see the back cover and also the titles - and even the contents - of the con- tributedpapers.Inadditiontothe frontcoverfigure,see Ray’sfamousequation at http://world.std.com/∼rjs, together with the link there to Ray’s doo- dles (and perhaps also the use of parts of two of Ray’s doodles by RJD to give thefigureatwww.csse.monash.edu.au/∼dld/RaySolomonoffsVision.htmlor www.dowe.org/RaySolomonoffsVision.html). As well as the inside photo of Ray, see other photos of Ray in some of the contributed papers in the volume, and also photos of Ray at or linked to from http://world.std.com/∼rjs. From Ray’s inaugural Kolmogorovlecture in 2003 (see end of sec. 3 of Ray’s corresponding 2003 paper), following the directions Ray has given us should largelybe“aneverendingsourceofjoyindiscovery!”.And,amongotherthings, ourworktofollow(into the future)perhaps(startingnow)includesthe devoted thoughtanddiscussionwhichRayadvocatedin1967thatwehaveregardingthe problems of the realization of artificial intelligence – before they arise. May 2013 David L. Dowe Organization Organizing Committee General and Program Chair David L. Dowe Monash University, Australia Co-ordinator Dianne Nguyen Monash University, Australia Program Committee Andrew Barron Statistics, Yale University, USA Greg Chaitin IBM T.J. Watson Research Center, USA Fouad Chedid Notre Dame University, Lebanon Bertrand Clarke Medical Statistics, University of Miami, USA Peter Gacs Boston University, USA Alex Gammerman Royal Holloway, University of London, UK John Goldsmith Linguistics, University of Chicago, USA Marcus Hutter Australian National University, Australia Leonid Levin Boston University, USA Ming Li Mathematics, University of Waterloo, Canada John McCarthy Stanford University, USA (Turing Award (4 September 1927 - winner) 24 October 2011) Marvin Minsky MIT, USA (Turing Award winner) Kee Siong Ng ANU & EMC Corp., Australia David Paganin Physics, Monash University, Australia Teemu Roos University of Helsinki, Finland Juergen Schmidhuber IDSIA, Switzerland William Uther NICTA and University of New South Wales, Australia Farshid Vahid Econometrics, Monash University, Australia Paul Vitanyi Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands Vladimir Vovk Royal Holloway, University of London, UK X Organization Reviewers David Albrecht Monash University, Australia Eric Allender Rutgers– State University ofNew Jersey,USA Luis Antunes Porto University, Portugal James Breen Monash University, Australia Mike Cameron-Jones University of Tasmania, Australia Douglas Campbell University of Canterbury, New Zealand Fouad Chedid Notre Dame University, Lebanon Bertrand Clarke University of Miami, USA Adam Day University of California, USA Steven De Rooij Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands Karl Friston UCL, London, UK Peter Gacs Boston University, USA Alex Gammerman Royal Holloway, University of London, UK Toby Handfield Monash University, Australia Marcus Hutter Australian National University (ANU), Australia Asad I. Khan Monash University, Australia Tor Lattimore Australian National University, Australia Ming Li University of Waterloo, Canada Kar Seng Loke Monash University, Malaysia Enes Makalic University of Melbourne, Australia Simon Musgrave Monash University, Australia Kee Siong Ng ANU & EMC Corp., Australia David Paganin Monash University, Australia Ronald Pose Monash University, Australia Teemu Roos University of Helsinki, Finland Daniel Schmidt University of Melbourne, Australia Carl Shulman University of Oxford, UK Martin Strauss University of Michigan, USA Peter Tischer Monash University, Australia Andrea Torsello Ca’ Foscari University of Venice, Italy William Uther NICTA and University of New South Wales, Australia Farshid Vahid Monash University, Australia Tim van Erven University of Paris-Sud, France Joel Veness University of Alberta, Canada Gerhard Visser Monash University, Australia Vladimir Vovk Royal Holloway, University of London, UK John Woodward University of Nottingham, Ningbo, PRC Organization XI Acknowledgements We gratefully acknowledge our Sponsors for their support for the Ray Solomonoff 85th Memorial Conference, thank you. Sponsors Air Force Office of Scientific Research (AFOSR) Asian Office of Aerospace Research &Development (AOARD) Faculty of Information Technology, Monash University, Australia National ICT Australia, Australia AfurtherwordofgratitudetoDrRebeccaRobinsonandMrs.GenevieveOreski for their excellent combined efforts in proof-reading, formatting and other ad- ministrativeassistance.WefurtherthankRebeccaforherexpertassistancewith handling various LaTeX files. We also gratefully acknowledge Elke Werner and the team at Springer for the production of these proceedings.