THE INTELLIGENT WEB This page intentionally left blank the Intelligent Web Search, Smart Algorithms, and Big Data G A U T A M S H R O F F 1 3 GreatClarendonStreet,Oxford,OX26DP, UnitedKingdom OxfordUniversityPressisadepartmentoftheUniversityofOxford. ItfurtherstheUniversity’sobjectiveofexcellenceinresearch,scholarship, andeducationbypublishingworldwide.Oxfordisaregisteredtrademarkof OxfordUniversityPressintheUKandincertainothercountries ©GautamShroff2013 Themoralrightsoftheauthorhavebeenasserted FirstEditionpublishedin2013 Impression:1 Allrightsreserved.Nopartofthispublicationmaybereproduced,storedin aretrievalsystem,ortransmitted,inanyformorbyanymeans,withoutthe priorpermissioninwritingofOxfordUniversityPress,orasexpresslypermitted bylaw,bylicenceorundertermsagreedwiththeappropriatereprographics rightsorganization.Enquiriesconcerningreproductionoutsidethescopeofthe aboveshouldbesenttotheRightsDepartment,OxfordUniversityPress,atthe addressabove Youmustnotcirculatethisworkinanyotherform andyoumustimposethissameconditiononanyacquirer PublishedintheUnitedStatesofAmericabyOxfordUniversityPress 198MadisonAvenue,NewYork,NY10016,UnitedStatesofAmerica BritishLibraryCataloguinginPublicationData Dataavailable LibraryofCongressControlNumber:2013938816 ISBN 978–0–19–964671–5 PrintedinItalyby L.E.G.O.S.p.A.-LavisTN LinkstothirdpartywebsitesareprovidedbyOxfordingoodfaithand forinformationonly.Oxforddisclaimsanyresponsibilityforthematerials containedinanythirdpartywebsitereferencedinthiswork. Tomylatefather, whoIsuspectwouldhaveenjoyedthisbookthemost ACKNOWLEDGEMENTS Many people have contributed to my thinking and encouraged me while writing this book. But there are a few to whom I owe spe- cialthanks.First,toV.S.Subrahamanian,forreviewingthechapters astheycamealongandsupportingmyendeavourwithencouraging words.IamalsoespeciallygratefultoPatrickWinstonandPenttiKan- ervaforsparingthetimetospeakwithmeandsharetheirthoughtson theevolutionandfutureofAI. Equally important has been the support of my family. My wife Brinda,daughterSelena,andsonAhan—manythanksfortolerating mypreoccupationonnumerousweekendsandeveningsthatkeptme awayfromyou.Imustalsothankmymotherforenthusiasticallyread- ingmanyofthechapters,whichgavemesomeconfidencethatthey wereaccessibletosomeonenotatallfamiliarwithcomputing. Last but not least I would like to thank my editor Latha Menon, forhercarefulandexhaustivereviews,andforshepherdingthisbook throughthepublicationprocess. vi CONTENTS ListofFigures ix Prologue:Potential xi 1 Look 1 TheMEMEXReloaded 2 InsideaSearchEngine 8 GoogleandtheMind 20 DeeperandDarker 29 2 Listen 40 ShannonandAdvertising 40 ThePennyClicks 48 StatisticsofText 52 TuringinReverse 58 LanguageandStatistics 61 LanguageandMeaning 66 SentimentandIntent 73 3 Learn 80 LearningtoLabel 83 LimitsofLabelling 95 RulesandFacts 102 CollaborativeFiltering 109 RandomHashing 113 LatentFeatures 114 LearningFactsfromText 122 Learningvs‘Knowing’ 126 vii CONTENTS 4 Connect 132 MechanicalLogic 136 TheSemanticWeb 150 LimitsofLogic 155 DescriptionandResolution 160 BeliefalbeitUncertain 170 CollectiveReasoning 176 5 Predict 187 StatisticalForecasting 192 NeuralNetworks 195 PredictiveAnalytics 199 SparseMemories 205 SequenceMemory 215 DeepBeliefs 222 NetworkScience 227 6 Correct 235 RunningonAutopilot 235 FeedbackControl 240 MakingPlans 244 FlocksandSwarms 253 ProblemSolving 256 AntsatWork 262 Darwin’sGhost 265 IntelligentSystems 268 Epilogue:Purpose 275 References 282 Index 291 viii LIST OF FIGURES 1 Turing’sproof 158 2 Ponggameswitheye-gazetracking 187 3 Neuron:dendrites,axon,andsynapses 196 4 Minutiae(fingerprint) 213 5 Facepainting 222 6 Navigatingacarpark 246 7 Eightqueenspuzzle 257 ix