基于結(jié)構(gòu)化學(xué)習(xí)的數(shù)據(jù)壓縮方法

StructuredModelingandLearninginGeneralizedDataCompressionandProcessingHongkaiXiong熊紅凱電子工程系上海交通大學(xué)13Jan.2016VALSE-Webinar

LectureSparseRepresentation

Sparserepresentation

where

ΨLNx=θΣMultimediaCommunicationHighdimensionUnicastOne-to-oneMulticastOne-to-manyMulticastMany-to-manyNetworksVideocoding:advancesinhigherdimensionandhigherresolution,ingoalsofbetterR-DbehaviorandgreatercompressionrateNetworks:developstomultipledatastreamingwithinheterogeneousnetworkstructure,ingoalsofhigherthroughputandtransmissionreliabilitySources1Dsignal（audio）2Dsignal（image）3Dsignal（video）SVCDVC3

4GeneralizedContextModelinginSignalProcessingWenruiDai,HongkaiXiong,J.Wang,S.Cheng,Y.F.Zheng,"GeneralizedContextModelingwithMulti-DirectionalStructuringandMDL-basedModelSelectionforHeterogeneousDataCompression",IEEETrans.SignalProcessing,2015.WenruiDai,HongkaiXiong,J.Wang,etal.,“Discriminativestructuredsetpredictionmodelingwithmax-marginMarkovnetworkforlosslessimagecoding,”IEEETransactionsonImageProcessing,2014.WenruiDai,HongkaiXiong,X.Jiang,etal.,“Structuredsetintrapredictionwithdiscriminativelearninginmax-marginMarkovnetworkforHighEfficiencyVideoCoding,”IEEETransactionsonCircuitsandSystemsforVideoTechnology,vol.23,no.11,pp.1941-1956,2013.HeterogeneousDataCompression:DataHeterogeneousdataaregeneratedbymultipleinterlacingsourcescompliedwithdifferentincompletedistributionstatisticsImage

&

Video:

SpatialcorrelationsarecharacterizedbypiecewisesmoothwithlocaloscillatorypatternslikemultiscaleedgesandtexturesGenome

sequence:

RepeatablepatternsofnucleotidesinvariousregionsExecutable

files:

Multipleinterlacingdatastreams,e.g.opcode,displacement,andimmediatedataHeterogeneousDataCompression:FrameworkContext

ModelData

to

be

predictedEstimated

probabilityCoderEncoded

bitstream01011101……Structured

probabilistic

model

Capture

regular

patternsOptimized

for

specific

dataContext-based

set

predictionClassic

context

modelVariable

orderSequential

predictionWeighted

estimationContextissuffixofdatasymbols

inclassicalcontextmodeling.Definethesetofsubsequenceswhosesuffixiss.

Disjointproperty:nostringinthecontextsetisasuffixofanyotherstringinthisset,orfor,;

Exhaustiveproperty:eachsubsequenceofdatasymbolscanfinditssuffixinthecontextset,or.7BackgroundGraphicalprobabilisticmodel

Structuredpredictionmodelcanberepresentedintheformofgraph.Eachnodefortherandomvariabletopredictandeachedgefortheinterdependenciesamongnodes.Estimatingjointorconditionaldistributionforitsnodes.Learningmethods

Markovrandomfield(MRF)Max-marginMarkovnetwork:MRF+SVMReasoningalgorithmsBeliefpropagation(BP)Expectationpropagation(EP)Foundation:StructuredPredictionModelStructured

Probabilistic

Model:

Motivation

ComplexdatastructureCannotbeanalyticallyrepresented

Adaptivelycapturefeatureswithlearning-basedalgorithmsIncompletedistributionCannotexactlyestimateparametersforactualdistribution

Context-basedpredictivemodelusinglearning-basedalgorithmsStructuralcoherenceCannotguaranteestructuralcoherenceofpredictiontaskwithisolatedprediction

Structuredprobabilisticmodeltoconstrainpredictiontaskwithstructuralcoherence10StructuralcoherenceAnexample:ImagesgeneratedwiththesamelocaldistributionAnaturalimagesisnota2Darrayofpixelsgeneratedwithprobabilisticdistribution.Thestructuralcoherenceismaintainedtokeepanimagemeaningful.

Structuredpredictionmodelisproposedtomaintainsuchcoherence.Intuition1:StructuralcoherenceforheterogeneousdataMotivationPerceptualIntuitionIntuition2:ComplexstructureforheterogeneousdataStatisticsofheterogeneousdataisnotsequentialandwithuniformdistribution,butisflexibleandwithinterlacedcomplexdistribution.Predictionbasedonsequential,contextswithuniformdistributionGeneralizedContextModelingMotivationPredictionbasedonflexiblyconstructedcontextswithinterlacedcomplexdistributionContribution：Structureconsistence

→

StructuredSetProblemDefinitionChallenge：LinearPredictionwithouthigh-ordernonlinearityIndependentPredictionwithoutinter-dependencySimilarPDF12Pixel-wisepredictiontoimpairthestructureParallelpredictiontokeepstructureStructuredProbabilisticModel:

ExampleLeastSquaresMSE:82.06StructuredProbabilisticModelMSE:68.754x4blockatcoordinate(401,113)inLENATheoreticalsupport:SequentialSourceCodingMotivationHarishViswanathan&Berger2000:

GivenrandomvariableX1andX2,underarbitrarydistortionD1andD2,therateforjointlydescribingthemisnogreaterthantheratetodescribethemseparately.Encoder1Encoder2Decoder1Decoder2ContributionGCMforheterogeneousdatacompressionStructuredprobabilisticmodelforgenomecompressionMRFfordependencybetweensideinformation&optimizedwithBPStructuredprobabilisticmodelforlosslessimagecodingM3NforjointspatialstatisticsandstructuralcoherenceStructuredprobabilisticmodelforintra-framevideocodingM3NoptimizedwithEPContributionWenruiDai@SJTU,201416GCMImageGenomeVideoExecutablesUniversalCodingHeterogeneousDataLearningSyntax&SemanticsInputspaceFeaturespaceDataDependencyHeterogeneousdataGenomicdataLongrepeatswithexceptionofinsertion,deletion,andsubstitution.ImageandVideoSpatiallyspannedalongthestructures,e.g.edge,texture,andetc.ExecutablesInterlaceddatastreams,e.g.opcodes,immediatedata,andetc.Background:HeterogeneousDataDefinition:

HeterogeneousData

Heterogeneousdataisgeneratedbyinterlacing

Mdatastreamswithatime-varyingrandomprocessThej-thdatastreamisemittedfromastationaryMarkovsourcewithorderSymbolisobtainedfromthe-thdatastreambyandisnotstationaryandwidesensestationaryClueInMemoryOfBenTaskar(1977-2013)Arisingstarinmachinelearning,computationallinguisticsandcomputervisionThefounderofMax-MarginMarkovNetworkPredictivemodelsforheterogeneousdatacompressionContextModelSymbolsforpredictingEstimatedprobabilityCodingengineEnocdedbits01011101……CaptureintrinsicstructureofcomplexdataFindadaptationtospecificdataOptimalsetpredictionbasedonobservedcontextsStructuredpredictionmodelGeneralizedContextModeling Scenario:CodingBasedonContextModeling

CurrentsymbolExtendedcontextSequentialcontextContextwithcombinatorialstructuringContextwithmulti-dimensionalextension2-DcontextM-DcontextGeneralizedcontextmodeling(GCM)withcombinatorialstructuring&multi-dimensionalextensionGeneralizedContextModelingTopologyIllustration

GraphicalmodelforGCMwithD-orderandM-directionalcontext.Symbolsforpredictingarecorrelatedwiththeirneighboringsymbols.Componentofcontextineachdirectionisservedasanobservationfortheprediction.Conditionalrandomfieldrepresentdependenciesamongsymbolsforpredictingandcontext-basedcorrelations.SymbolsforpredictingContextsGeneralizedContextModelingGraphicalModelforPredictionDefinition:

Context

SetGivencontexts,thesetofsubsequencescontainingsiswhereistheindexsetofs.

isavalidgeneralizedcontextmodel,ifitsatisfiesineachofitsdirectionExhaustiveproperty：foranysubsequenceinj-thdirection,thereexistssinsuchthatDisjointproperty：foranysubsequenceinj-thdirection,givenarbitrarys

ands’Modeling

&

Prediction:

Model

GraphTrellis-likegraphrootedfromM-aryvector(?,···

,?)Eachnodecorrespondstoanindexsetforfiniteordercombinationofpredictedsymbols.Givennode,ItssucceedingnodesatisfiesthatItsprecedingnodestatisfiesthat

possiblecontextstructureslocatinginDM+1verticalslicesforGCMwithgivenMandD.GeneralizedContextModeling ModelTreeexampleRepresentation

&

Prediction:Model

GraphModelgraphwithdepthD=3andM=2directionsSolid(red)anddashed(blue)pathssharesomecommonnodesModeltreetorepresentgeneralizedcontextmodelsandtheirsuccessiverelationship.

Minimumdescriptionlength(MDL)principletoselectoptimalclassofcontextmodels.

Normalizedmaximumlikelihood(NML)todetermineoptimalweightedprobabilityforprediction.GeneralizedContextModeling ProblemStatement

GeneralizedContextModeling ModelTreeModel

Selection:

Separable

Context

ModelingPredictionbasedoncontextswithmulti-directionalstructuringcanbemadeseparatelyineachofitsdirections.Given

whereanditselementsareThesizeofmodelclassgrowslinearlywithMNMLfunctionwithMDLprincipleformodelselection.ContextsineachdirectionarecomparedwiththeNMLfunctiontofindoptimalcontextforpredictingcurrentsymbol.ForM-interlacedautoregressivesources,themodelcomplexityisconstantwithdatasizeN.ModelcomplexityCodeassignmentfunctionGeneralizedContextModelingModelSelectionEstimatedprobabilityforgeneralizedcontextmodeling

Inasequentialway,foreachsymbolForeachcontexts,itsweightsis

whereGeneralizedContextModelingWeightedProbabilityforPredictionGivengeneralizedmodelclassMwithmaximumorderDandMdirections,themodelredundancyledbymulti-directionalextensioniswhereListhesizeofalphabet,η

isthecompensationforvariouscontexts.Themodelredundancyledbymulti-directionalextensiononlydependsonthemaximumorderDandthenumberofdirectionsM,butisindependentofsizeofdataN.GeneralizedContextModelingModelRedundancyInCalgarycorpus,GCMoutperformsCTWby7%-12%inexecutablefilesandseismicdata.Inexecutablefilecompression,GCMoutperformsPPMdandPPMonstrby10%and4%,respectively.GCMiscomparativetothebestcompressorPAQ8withlesscomputationalcomplexity.

ML-baseddoesnotfullyexploitthestatisticsinheterogeneousdata.Asanalternative,learningofstructuredpredictionmodelisproposed.GeneralizedContextModelingExperimentalResultsGivengeneralizedmodelclass

MwithmaximumorderDandMdirections,themodelredundancyledbycombinatorialstructuringiswhereListhesizeofalphabet,η

isthecompensationforvariouscontexts.Themodelredundancyledbymulti-directionalextensiononlydependsonthemaximumorderD,butisindependentofsizeofdataN.34ModelRedundancy

Discriminativepredictiondistinguishestheactualvaluesofpixelswithotherpossibleestimationstothemaxmarginbasedoncontexts,butcannotutilizethestructureforpredictions.

Markovnetworkmaintainsthestructuralcoherenceintheregionsforpredictingbutcannotoptimizethecontext-basedprediction.

Jointoptimizationbymax-marginMarkovnetworkConceptualDiagram:ImageContext-basedpredictionforeachpixelImagingconstraintsforsetofpixelsStructuralcoherenceSamplingEncodingImagingconstraintsforsetofpixelsContext-basedpredictionforeachpixelStructuralcoherenceDecodingReconstructionFlowingdiagramforstructuredsetpredictionmodelDiagram

Givenytheblockofencodingpixelsandxthereconstructedpixelsascontexts,itspredictionisderivedintheconcurrentform.

Localspatialstatisticsisrepresentedbythelinearcombinationoftheclassoffeaturefunctions.CollectionoffeaturefunctionsTrainedmodelparametersPredictionJointoptimizationStructuralcoherenceLossfunctionFeaturefunctionTrainedmodelparameterModelparameterwistrainedoverthecollectionoftrainingdataS={xi,yi}.

Thefeaturefunctions{fi}establishtheconditionalprobabilisticmodelforpredictionbasedonthevariouscontextsderivedfromthesupposedpredictivedirection

isthelossfunctionthatevaluatesthepredictionandadjuststhemodelparameterw.TrainingTheM-aryestimatedoutput?(i)forblockofpixelsyismeasuredoverthegeneratedgraphicalmodel.Log-GaussianfunctionfornodecliqueandDiracfunctionforedgeclique.Withpredictionerror?i=?(i)-y(i)andvarianceσ2overerrorsLossFunctionStandardquadraticprogramming(QP)forsolvingthemin-maxformulationsuffersthehighcomputationalcostfortheproblemswithlargealphabetsize.Asanalternative,itsdualisproposed.Sequentialminimaloptimization(SMO)breaksthedualproblemintoaseriesofsmall(QP)problemsforcliquesandtakesanascentsteptomodifytheleastnumberofvariableswhereandαi(y)isthemarginaldistributionfortheithclique.SMOiterativelychoosesthepairsofywithrespecttotheKKTconditionforsolution.SolutionJunctiontreeforloopyMarkovnetwork.Eachjunctionisgeneratedbyaddingedgestolinkcliques.Junctiontreeisunique.EachcliqueispredictedalongthejunctiontreeBeliefPropagation(BP)asmessagepassingalgorithmforinferenceandupdatethepotentialofeachcliqueSolutionTheoreticalupperboundforpredictionerrorTheorem:Giventhetrainedweightingvectorwandarbitraryconstantη>0,thepredictionerrorisasymptoticallyequivalenttotheoneobtainedoverthetrainingdatawithprobabilityatleast1-exp(-η).UpperboundforaveragepredictionerrorUpperboundforγ-relaxedaveragetrainingerrorAdditionaltermconvergestozerowhenNgrowsRemark:Thepredictionerrorisupper-boundedbythewell-tunedtrainingerror.TheTheoremensuresthepredictiveperformanceofthestructuredpredictionmodel.UpperBoundofPredictionErrorInviewofprobability,giventhetrainedweightingvectorwandarbitraryconstantη>0,withsufficientsampling,thereexistsε(L,γ,N,η)→0,satisfyingThepredictionerrorisupper-boundedbythewell-tunedtrainingerror.TheTheoremensuresthepredictiveperformanceofthestructuredsetpredictionmodel.UpperBoundofPredictionErrorCombiningwithvariance-basedpredictorforsmoothregions,structuredsetpredictionservesasanalternativemodeComparingthecodingcostoftwoalternativemodesfortheoptimaloneLog-GaussianlossfunctiontoobtainoptimalcodingoftheresidualbasedonallegedGaussiandistribution.ImplementationExperimentalResultsImageProposedMRPBMFTMWCALICJPEG-LSJPEG2000HDPhotoAirplane3.5363.5913.6023.6013.7433.8174.0134.247Baboon5.6355.6635.7145.7385.6666.0376.1076.149Balloon2.5482.5792.6492.6492.8252.9043.0313.320Barb3.7643.8153.9594.0844.4134.6914.6004.836Barb24.1754.2164.2764.3784.5304.6864.7895.024Camera3.9013.9494.0604.0984.1904.3144.5354.959Couple3.3233.3883.4483.4463.6093.6993.9154.318Goldhill4.1734.2074.2384.2664.3944.4774.6034.746Lena3.8773.8893.9293.9084.1024.2384.3034.477Peppers4.1634.1994.2414.2514.2464.5134.6294.850

PerformanceexceedsJPEG-LSby10%andJPEG2000losslessmodeby14%inaverageinbitsperpixel.

Performanceexceedstheminimumratepredictor(MRP,theoptimalpredictor)by1.35%inaverageinbitsperpixel.JointoptimizationStructuralcoherenceLossfunctionFeaturefunctionTrainedmodelparameterOptimaljointpredictionbymax-marginMarkovnetwork

Max-marginestimationdirectlyconditionedonthepredictedpixelsforcontext-basedprediction

Markovnetworktomaintainthestructuralcoherenceintheregionsforpredicting.ConceptualDiagram:VideoConceptualdescriptionforstructuredpredictionmodelLaplacianlossfunctionfortheM-aryestimatederror.Laplacianerrorsderivedforeachnodeandthestatetransitionoftheneighboringnodesforeachedge.Foreachnode,itspredictionerroriswheretheerror?i=?(i)-y(i)andvarianceσ2overerrors.LaplacianlossfunctionmeetswithDCTtransform.ThestructuredpredictionmodeloptimizeitforminimalcodinglengthunderHEVCframework.LossFunctionExpectationPropagationforMessagePassingUtilizeSMOforSolvingthestandardquadraticprogramming(QP)forthemax-marginMarkovnetwork.Accordingly,junctiontreeisgeneratedandmessagepassingalgorithmisconductedalongjunctiontreeforthemostprobablestatesofeachpixel.Thelossyintravideocodingdoesnotrequiretopropagatetheactualstatesalongthejunctiontree.Statisticslikemeansandvariancecannotbeselectedandpropagatedforrobustmessagepassingwithconvergence.Expectationpropagation(EP)utilizessuchstatisticssothattheactualdistributionisapproximatedwiththeexponentialfamily.Themetricforapproximationcanbevariedbasedonthevideodata.

PredictionbasedonEPisproventoconvergetoanupperbound.Structuredpredictionmodelasanalternativemode:MODE_STRUCTIntegrationintocurrentHEVCframeworkwithoutadditionalsyntaxelementModedecisionbyrate-distortionoptimizationLaplacian-basedlossfunctionfortheresidualobtainingbestcodingperformanceunderDCTtransformImplementationForeman_352×288BlowingBubbles_416×240BQMall_832×480Cactus_1920×1080

PerformanceexceedsHEVCcommontestmodelby2.26%inBD-rates.ThegaininBD-PSNRisupto0.38dB.

PerformanceexceedsHEVCwithcombinedintracoding(CIP)by1.31%inBD-rates.ExperimentalResultsProteinPhenotypeDNA(Genotype)PurineBases:Adenine(A);Guanine(G)PyramidineBases:Thymine(T);Cytosine(C)RNA51Thecentraldogmaofmolecularbiology:Aframeworkforunderstandingthenormalflowforthetransferofsequenceinformationbetweensequentialinformationcarrier.ProteinsareconstructedaccordingtoDNA.ConceptualDiagram:GenomeSequence52Background:CompressiveStructuresinGenomicDataTGTCTGCAGCAGCCGCTTGTCTGCAACAGCCGCTTGTCTGCACAGCCGCTTGTCTGCAGGCAGCCGCTACAGACGTGTCGGCGAReversiblePalindromeDeletionof‘G’Substitutionof‘G’with‘A’Insertionof‘G’DNAsequenceisrepeatedpatternsofnucleotides,namely‘A’,‘T’,‘G’,and‘C’Approximaterepeats:Exactrepeat,Insertion,Deletion,andSubstitutionReversiblepalindrome:substitute‘A’with‘T’and‘G’with‘C’,andviceversaReference-basedMethodsRLZ

RelativeLZcompressionwithrelatedreferencesequencesindicatedbytheirself-indexCannothandlealphabetotherthan{A,T,G,C,N}GRS

GeneralGenomeReSequencingtoolConsiderchromosomevariedsequencepercentageGReEn

CopymodelformatchingofexactrepeatsinreferenceStatisticalmodelforestimatingtheprobabilitiesofmatchingBackgroundMainConcernsApproximateorexactrepeatsofnucleotides

Variablerepeatsizes&offsetsofrepeats.

Exceptionofinsertion,deletionandsubstitutionofnucleotidesinrepeatsMotivations

Differencesbetweentargetandreferencesequencearenotuniformlydistributed,butsparseforcoding.Sideinformation,e.g.sizesandoffsetsarecorrelated,whichcanbepredictedbasedonstructuredpredictionmodel.MotivationUnderthehierarchicalpredictionstructure,thereferenceisselectedaccordingtothelossfunctionDifferencesequenceisthezerosequencewithemergenceofnon-zerosymbolatalowfrequency.Itissuitableforwavelettransformandsubsequentbitplanecoding.

Markovrandomfieldisestablishedforcorrelatedsideinformation,whichispredictedandupdatedwithBPalgorithm.FrameworkExampleforhierarchicalpredictionstructure:A(sub-)fragmentof16nucleotidesispredictedbasedona(sub-)fragmentof16nucleotidesinreferencesequence