关闭

关闭

关闭

封号提示

内容

首页 Information Theory, Inference and Learning Algor…

Information Theory, Inference and Learning Algorithms.pdf

Information Theory, Inference a…

zhaoshuaijiang8
2012-01-07 0人阅读 0 0 0 暂无简介 举报

简介:本文档为《Information Theory, Inference and Learning Algorithmspdf》,可适用于高等教育领域

InformationTheory,Inference,andLearningAlgorithmsDavidJCMacKaymackaymraocamacukc©,,,,,,,,DraftJanuary,Pleasesendfeedbackonthisbookviahttp:wwwinferencephycamacukmackayitprnnMoredocumentsanddatumdownloadwebsiteLuZhenbo'sBlog:blogsinacomcnluzhenboCommunicationCooperation:luzhenboyahoocomcnInformationTheory,PatternRecognitionandNeuralNetworksApproximateroadmapfortheeightweekcourseinCambridgeThecoursewillcoveraboutchaptersofthisbookTherestofthebookisprovidedforyourinterestThebookcontainsnumerousexerciseswithworkedsolutionsLectureIntroductiontoInformationTheoryChapterBeforelectureWorkonexercise(p)ReadchaptersandandworkonexercisesinchapterLecture–InformationcontenttypicalityChapterLectureSymbolcodesChapterLectureArithmeticcodesChapter(sections–only)ReadchapteranddotheexercisesLectureNoisychannelsDefinitionofmutualinformationandcapacityChapterLecture–ThenoisychannelcodingtheoremChapter(butnotsectiononwards)LectureClusteringBayesianinferenceChapter,,Readchapter(Isingmodels)Lecture–MonteCarlomethodsChapter,LectureVariationalmethodsChapterLectureNeuralnetworks–thesingleneuronChapterLectureCapacityofthesingleneuronChapterLectureLearningasinferenceChapterLectureTheHopfieldnetworkContentaddressablememoryChapterAbouttheexercisesIfirmlybelievethatonecanonlyunderstandasubjectbyrecreatingitforoneselfTothisend,IthinkitisessentialtoworkthroughsomeexercisesoneachtopicForguidance,eachexercisehasarating(similartothatusedbyKnuth())fromtothatindicatesthelevelofdifficultyInaddition,exercisesthatareespeciallyrecommendedaremarkedbyamarginalencouragingrat–ExercisesthatrequiretheuseofacomputermaybemarkedwithaCI’llcirculatedetailedrecommendationsonexercisesasthecourseprogressesAnswerstomanyoftheexercisesareprovidedPleaseusethemwiselySummaryofcodesforexercisesEspeciallyrecommendedRecommendedCSomepartsrequireacomputerSimple(oneminute)Medium(quarterhour)ModeratelyhardHardResearchprojectc©DavidJCMacKayDraftJanuary,MoredocumentsanddatumdownloadwebsiteLuZhenbo'sBlog:blogsinacomcnluzhenboCommunicationCooperation:luzhenboyahoocomcnCONTENTSContentsIntroductiontoInformationTheorySolutionstochapter’sexercisesProbability,Entropy,andInferenceSolutionstoChapter’sexercisesMoreaboutInferenceSolutionstoChapter’sexercisesIDataCompressionTheSourceCodingTheoremSolutionstoChapter’sexercisesSymbolCodesSolutionstoChapter’sexercisesStreamCodesSolutionstoChapter’sexercisesFurtherExercisesonDataCompressionSolutionstoChapter’sexercisesCodesforIntegersIINoisyChannelCodingCorrelatedRandomVariablesSolutionstoChapter’sexercisesCommunicationoveraNoisyChannelSolutionstoChapter’sexercisesTheNoisyChannelCodingTheoremSolutionstoChapter’sexercisesErrorCorrectingCodesandRealChannelsSolutionstoChapter’sexercisesIIIFurtherTopicsinInformationTheoryHashCodes:CodesforEfficientInformationRetrievalSolutionstoChapter’sexercisesBinaryCodesVeryGoodLinearCodesExistc©DavidJCMacKayDraftJanuary,MoredocumentsanddatumdownloadwebsiteLuZhenbo'sBlog:blogsinacomcnluzhenboCommunicationCooperation:luzhenboyahoocomcnCONTENTSFurtherExercisesonInformationTheorySolutionstoChapter’sexercisesMessagePassingCommunicationoverConstrainedNoiselessChannelsSolutionstoChapter’sexercisesCrosswordsUnitsofInformationContentWhyhaveSexInformationAcquisitionandEvolutionIVProbabilitiesandInferenceIntroductiontoPartIVAnExampleInferenceTask:ClusteringExactInferencebyCompleteEnumerationMaximumLikelihoodandClusteringUsefulProbabilityDistributionsExactMarginalizationExactMarginalizationinTrellisesMoreonTrellisesSolutionstoChapter’sexercisesExactMarginalizationinGraphsLaplace’sMethodModelComparisonandOccam’sRazorMonteCarloMethodsSolutionstoChapter’sexercisesEfficientMonteCarloMethodsIsingModelsExactMonteCarloSamplingVariationalMethodsSolutionstoChapter’sexercisesIndependentComponentAnalysisandLatentVariableModellingFurtherExercisesonInferenceDecisionTheoryWhatDoYouKnowifYouAreIgnorantBayesianInferenceandSamplingTheoryVNeuralnetworksIntroductiontoNeuralNetworksTheSingleNeuronasaClassifierSolutionstoChapter’sexercisesCapacityofaSingleNeuronSolutionstoChapter’sexercisesc©DavidJCMacKayDraftJanuary,MoredocumentsanddatumdownloadwebsiteLuZhenbo'sBlog:blogsinacomcnluzhenboCommunicationCooperation:luzhenboyahoocomcnCONTENTSLearningasInferenceSolutionstoChapter’sexercisesTheHopfieldNetworkFromHopfieldNetworkstoBoltzmannMachinesSupervisedLearninginMultilayerNetworksGaussianProcessesDeconvolutionVISparseGraphCodesIntroductiontoSparseGraphCodesLowDensityParityCheckCodesConvolutionalCodesandTurboCodesRepeatAccumulateCodesWhatYouMissedVIIAppendicesANotationBUsefulFormulae,andMoreBibliographyc©DavidJCMacKayDraftJanuary,MoredocumentsanddatumdownloadwebsiteLuZhenbo'sBlog:blogsinacomcnluzhenboCommunicationCooperation:luzhenboyahoocomcnAboutChapterIhopeyouwillfindthemathematicsinthefirstchaptereasyYouwillneedtobefamiliarwiththebinomialdistributionAndtosolvetheexercisesinthetext–whichIurgeyoutodo–youwillneedtorememberStirling’sapproximationforthefactorialfunction,x!'xxe−x,andbeabletoapplyitto(Nr)=N!(N−r)!r!ThesetopicsarereviewedbelowUnfamiliarnotationSeeappendixA,pThebinomialdistributionExample:AbentcoinhasprobabilityfofcomingupheadsThecoinistossedNtimesWhatistheprobabilitydistributionofthenumberofheads,rWhatarethemeanandvarianceofreerFigureThebinomialdistributionP(r|f=,N=),onalinearscale(top)andalogarithmicscale(bottom)Solution:ThenumberofheadshasabinomialdistributionP(r|f,N)=(Nr)fr(−f)N−r()Themean,Er,andvariance,varr,ofthisdistributionaredefinedbyEr≡N∑r=P(r|f,N)r()varr≡E(r−Er)()=Er−(Er)=N∑r=P(r|f,N)r−(Er)()Ratherthanevaluatingthesumsoverr(,)directly,itiseasiesttoobtainthemeanandvariancebynotingthatristhesumofNindependentrandomvariables,namely,thenumberofheadsinthefirsttoss(whichiseitherzeroorone),thenumberofheadsinthesecondtoss,andsoforthIngeneral,Exy=ExEyforanyrandomvariablesxandyvarxy=varxvaryifxandyareindependent()Sothemeanofristhesumofthemeansofthoserandomvariables,andthevarianceofristhesumoftheirvariancesThemeannumberofheadsinasingletossisf×(−f)×=f,andthevarianceofthenumberofheadsinasingletossisf×(−f)×−f=f−f=f(−f),()sothemeanandvarianceofrare:Er=Nfandvarr=Nf(−f)()c©DavidJCMacKayDraftJanuary,MoredocumentsanddatumdownloadwebsiteLuZhenbo'sBlog:blogsinacomcnluzhenboCommunicationCooperation:luzhenboyahoocomcnAboutChapterApproximatingx!and(Nr)eeerFigureThePoissondistributionP(r|λ=),onalinearscale(top)andalogarithmicscale(bottom)Let’sderiveStirling’sapproximationbyanunconventionalrouteWestartfromthePoissondistribution,P(r|λ)=e−λλrr!r∈{,,,}()Forlargeλ,thisdistributioniswellapproximated–atleastinthevicinityofr'λ–byaGaussiandistributionwithmeanλandvarianceλ:e−λλrr!'√piλe−(r−λ)λ()Let’splugr=λintothisformulae−λλλλ!'√piλ()⇒λ!'λλe−λ√piλ()ThisisStirling’sapproximationforthefactorialfunction,includingseveralofthecorrectiontermsthatareusuallyforgottenx!'xxe−x√pix⇔lnx!'xlnx−xlnpix()Wecanusethisapproximationtoapproximate(Nr)≡N!(N−r)!r!ln(Nr)'(N−r)lnNN−rrlnNr()Sinceallthetermsinthisequationarelogarithms,thisresultcanberewritteninanybaseWewilldenotenaturallogarithms(loge)by‘ln’,andlogarithmsRecallthatlogx=logexlogeNotethat∂logx∂x=logextobase(log)by‘log’Ifweintroducethebinaryentropyfunction,H(x)≡xlogx(−x)log(−x)()thenwecanrewritetheapproximation()asH(x)xFigureThebinaryentropyfunctionlog(Nr)'NH(rN),()or,equivalently,(Nr)'NH(rN)()Ifweneedamoreaccurateapproximation,wecanincludetermsofthenextorderfromStirling’sapproximation():log(Nr)'NH(rN)−logpiNN−rNrN()c©DavidJCMacKayDraftJanuary,MoredocumentsanddatumdownloadwebsiteLuZhenbo'sBlog:blogsinacomcnluzhenboCommunicationCooperation:luzhenboyahoocomcnIntroductiontoInformationTheoryThefundamentalproblemofcommunicationisthatofreproducingatonepointeitherexactlyorapproximatelyamessageselectedatanotherpoint(ClaudeShannon,)InthefirsthalfofthisbookwestudyhowtomeasureinformationcontentwelearnhowtocompressdataandwelearnhowtocommunicateperfectlyoverimperfectcommunicationchannelsWestartbygettingafeelingforthislastproblemHowcanweachieveperfectcommunicationoveranimperfect,noisycommmunicationchannelSomeexamplesofnoisycommunicationchannelsare:•ananaloguetelephoneline,overwhichtwomodemscommunicatedigitalmodemphonelinemodeminformation•theradiocommunicationlinkfromtheJupiterorbitingspacecraft,Galileo,GalileoradiowavesEarthtoearthparentcelldaughtercelldaughtercell¡¡µR•reproducingcells,inwhichthedaughtercells’sDNAcontainsinformationfromtheparentcellscomputermemorydiscdrivecomputermemory•adiscdriveThelastexampleshowsthatcommunicationdoesn’thavetoinvolveinformationgoingfromoneplacetoanotherWhenwewriteafileonadiscdrive,we’llreaditoffinthesamelocation–butatalatertimeThesechannelsarenoisyAtelephonelinesuffersfromcrosstalkwithotherlinesthehardwareinthelinedistortsandaddsnoisetothetransmittedsignalThedeepspacenetworkthatlistenstoGalileo’spunytransmitterreceivesbackgroundradiationfromterrestrialandcosmicsourcesDNAissubjecttomutationsanddamageAdiscdrive,whichwritesabinarydigit(aoneorzero,alsoknownasabit)byaligningapatchofmagneticmaterialinoneoftwoorientations,maylaterfailtoreadoutthestoredbinarydigit:thepatchofmaterialmightspontaneouslyflipmagnetization,oraglitchofbackgroundnoisemightcausethereadingcircuittoreportthewrongvaluec©DavidJCMacKayDraftJanuary,MoredocumentsanddatumdownloadwebsiteLuZhenbo'sBlog:blogsinacomcnluzhenboCommunicationCooperation:luzhenboyahoocomcnIntroductiontoInformationTheoryforthebinarydigit,orthewritingheadmightnotinducethemagnetizationinthefirstplacebecauseofinterferencefromneighbouringbitsInallthesecases,ifwetransmitdata,eg,astringofbits,overthechannel,thereissomeprobabilitythatthereceivedmessagewillnotbeidenticaltothetransmittedmessageWewouldprefertohaveacommunicationchannelforwhichthisprobabilitywaszero–orsoclosetozerothatforpracticalpurposesitisindistinguishablefromzeroLet’sconsideranoisydiscdrivethattransmitseachbitcorrectlywithprobability(−f)andincorrectlywithprobabilityfThismodelcommunicationchannelisknownasthebinarysymmetricchannel(figure)x¡¡µRyP(y=|x=)=−fP(y=|x=)=fP(y=|x=)=fP(y=|x=)=−fFigureThebinarysymmetricchannelThetransmittedsymbolisxandthereceivedsymbolyThenoiselevel,theprobabilityofabit’sbeingflipped,isf(−f)(−f)f¡¡¡¡µRFigureAbinarydatasequenceoflengthtransmittedoverabinarysymmetricchannelwithnoiselevelf=DilbertimageCopyrightc©UnitedFeatureSyndicate,Inc,usedwithpermissionAsanexample,let’simaginethatf=,thatis,tenpercentofthebitsareflipped(figure)AusefuldiscdrivewouldflipnobitsatallinitsentirelifetimeIfweexpecttoreadandwriteagigabyteperdayfortenyears,werequireabiterrorprobabilityoftheorderof−,orsmallerTherearetwoapproachestothisgoalThephysicalsolutionThephysicalsolutionistoimprovethephysicalcharacteristicsofthecommunicationchanneltoreduceitserrorprobabilityWecouldimproveourdiscdrivebyusingmorereliablecomponentsinitscircuitryevacuatingtheairfromthediscenclosuresoastoeliminatetheturbulencethatperturbsthereadingheadfromthetrackusingalargermagneticpatchtorepresenteachbitorusinghigherpowersignalsorcoolingthecircuitryinordertoreducethermalnoiseThesephysicalmodificationstypicallyincreasethecostofthecommunicationchannelc©DavidJCMacKayDraftJanuary,MoredocumentsanddatumdownloadwebsiteLuZhenbo'sBlog:blogsinacomcnluzhenboCommunicationCooperation:luzhenboyahoocomcn:ErrorcorrectingcodesforthebinarysymmetricchannelNoisychannelEncoderDecoderSourcetsrsˆFigureThe‘system’solutionforachievingreliablecommunicationoveranoisychannelTheencodingsystemintroducessystematicredundancyintothetransmittedvectortThedecodingsystemusesthisknownredundancytodeducefromthereceivedvectorrboththeoriginalsourcevectorandthenoiseintroducedbythechannelThe‘system’solutionInformationtheoryandcodingtheoryofferanalternative(andmuchmoreexciting)approach:weacceptthegivennoisychannelasitisandaddcommunicationsystemstoitsothatwecandetectandcorrecttheerrorsintroducedbythechannelAsshowninfigure,weaddanencoderbeforethechannelandadecoderafteritTheencoderencodesthesourcemessagesintoatransmittedmessaget,addingredundancytotheoriginalmessageinsomewayThechanneladdsnoisetothetransmittedmessage,yieldingareceivedmessagerThedecoderusestheknownredundancyintroducedbytheencodingsystemtoinferboththeoriginalsignalsandtheaddednoiseWhereasphysicalsolutionsgiveincrementalchannelimprovementsonlyataneverincreasingcost,systemsolutionscanturnnoisychannelsintoreliablecommunicationchannelswiththeonlycostbeingacomputationalrequirementattheencoderanddecoderInformationtheoryisconcernedwiththetheoreticallimitationsandpotentialsofsuchsystems‘Whatisthebesterrorcorrectingperformancewecouldachieve’CodingtheoryisconcernedwiththecreationofpracticalencodinganddecodingsystemsEr

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/49

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部

举报
资料