MotivationProtein Score FunctionObject RetrievalKernel MachinesDistribution Distance FunctionsBin-Bin ComparisonsCross-Bin ComparisonsEarth Mover Distance ApproximationsDiffusion DistanceEMD via EmbeddingsWavelet ApproximationMotivationDistribution Distance FunctionsEarth Mover Distance ApproximationsDistribution Distance FunctionsDistribution Distance FunctionsCOMP 875November 10, 2009Matthew O’MearaDistribution Distance FunctionsMotivationDistribution Distance FunctionsEarth Mover Distance ApproximationsQuestionHow similar are these?Distribution Distance FunctionsMotivationDistribution Distance FunctionsEarth Mover Distance ApproximationsProtein Score FunctionObject RetrievalKernel MachinesOutline1MotivationProtein Score FunctionObject RetrievalKernel Machines2Distribution Distance FunctionsBin-Bin ComparisonsCross-Bin Comparisons3Earth Mover Distance ApproximationsDiffusion DistanceEMD via EmbeddingsWavelet ApproximationDistribution Distance FunctionsMotivationDistribution Distance FunctionsEarth Mover Distance ApproximationsProtein Score FunctionObject RetrievalKernel MachinesParametrization of H-bond geometryParametrization of H-bond geometryH-bonds have 4 degrees of freedomH-bonds in Ubiquitin protein.H-bond geometry.Distribution Distance FunctionsMotivationDistribution Distance FunctionsEarth Mover Distance ApproximationsProtein Score FunctionObject RetrievalKernel MachinesExample H-bond Classification DecisionDo H-bonds have different geometry in sheets and helices?Each point corresponds to a hydrogen bond: (Left) H-bonds in beta sheets. (Right) H-bonds in helices. AHDist is thebond length and cosBAH is the cosine of the angle at the acceptor.Distribution Distance FunctionsMotivationDistribution Distance FunctionsEarth Mover Distance ApproximationsProtein Score FunctionObject RetrievalKernel MachinesOutline1MotivationProtein Score FunctionObject RetrievalKernel Machines2Distribution Distance FunctionsBin-Bin ComparisonsCross-Bin Comparisons3Earth Mover Distance ApproximationsDiffusion DistanceEMD via EmbeddingsWavelet ApproximationDistribution Distance FunctionsMotivationDistribution Distance FunctionsEarth Mover Distance ApproximationsProtein Score FunctionObject RetrievalKernel MachinesImage Retrieval Requires similarity measureProblem: Given new image return similar images from adatabaseBrowse through an image library (Rubner2000)Distribution Distance FunctionsMotivationDistribution Distance FunctionsEarth Mover Distance ApproximationsProtein Score FunctionObject RetrievalKernel MachinesRepresent images as distributionsImage features have relationshipsInherent qualities:eg, color, texture, edgesSpatial qualities:eg, where in the pictureVisualizing shape context. (Grauman and Darrell 2004)Distribution Distance FunctionsMotivationDistribution Distance FunctionsEarth Mover Distance ApproximationsProtein Score FunctionObject RetrievalKernel MachinesRetrieve similar songs to a given song from adatabaseMusic DescriptorsMel-frequency cepstralcoefficients (Spectrum of thespectrum scaled for humans)Pandora “music genome”descriptors etc.phoneme for security groupComparing music similarity (Typke2003)Pandora.com internet radio builds play lists from example songsDistribution Distance FunctionsMotivationDistribution Distance FunctionsEarth Mover Distance ApproximationsProtein Score FunctionObject RetrievalKernel MachinesOutline1MotivationProtein Score FunctionObject RetrievalKernel Machines2Distribution Distance FunctionsBin-Bin ComparisonsCross-Bin Comparisons3Earth Mover Distance ApproximationsDiffusion DistanceEMD via EmbeddingsWavelet ApproximationDistribution Distance FunctionsMotivationDistribution Distance FunctionsEarth Mover Distance ApproximationsProtein Score FunctionObject RetrievalKernel MachinesML Algorithms Require KernelsMany machine Learning algorithms use kernelsUnsupervised Learning:clusteringnearest neighboretc. . .Supervised Learning:support vector machinesclassificationetc. . .Distribution Distance FunctionsMotivationDistribution Distance FunctionsEarth Mover Distance ApproximationsBin-Bin ComparisonsCross-Bin ComparisonsBags of Features: ExampleImages can be reprented ashistograms over texture featuresExtract featuresLearn visual “vocabulary”quantize features using visualvocabularyJulesz, 1981; Cula & Dana, 2001; Leung & Malik 2001; Mori,Belongie & Malik, 2001; Schmid 2001; Varma & Zisserman, 2002,2003; Lazebnik, Schmid & Ponce, 2003, (slide from Lazebnik2009)Distribution Distance FunctionsMotivationDistribution Distance FunctionsEarth Mover Distance ApproximationsBin-Bin ComparisonsCross-Bin ComparisonsOutline1MotivationProtein Score FunctionObject RetrievalKernel Machines2Distribution Distance FunctionsBin-Bin ComparisonsCross-Bin Comparisons3Earth Mover Distance ApproximationsDiffusion DistanceEMD via EmbeddingsWavelet ApproximationDistribution Distance FunctionsMotivationDistribution Distance FunctionsEarth Mover Distance ApproximationsBin-Bin ComparisonsCross-Bin ComparisonsBin-Bin ComparisonsBin-Bin Comparisons compare each feature separatelyExamples:χ2goodness of fit testKullback Leibler divergenceDistribution Distance FunctionsMotivationDistribution Distance FunctionsEarth Mover Distance ApproximationsBin-Bin ComparisonsCross-Bin Comparisonsχ2test for goodness of fitχ2test for goodness of fitTest null hypothesis that is no significant deviation fromexpected results.Let O and E be observed and expected distributions withn − 1 degrees of freedom.Let χ2=nXi=1(Oi− Ei)2Ei.Compare with χ2distribution to get goodness of fitCan be made symmetricDistribution Distance FunctionsMotivationDistribution Distance FunctionsEarth Mover Distance ApproximationsBin-Bin ComparisonsCross-Bin ComparisonsKullback-Leibler DivergenceKullback-Leibler DivergenceLet P and Q be distributionsSupport of P has to be subset of support of QKL-divergence is the expected number of bit needed toencode Q given P.DKL(P k Q) =XiPilogPiQi.It can be made symmetric.Distribution Distance FunctionsMotivationDistribution Distance FunctionsEarth Mover Distance ApproximationsBin-Bin ComparisonsCross-Bin ComparisonsBin-Bin Comparison usefulnessBin-Bin ComparisonsThe good:Simple conceptsFast to evaluate O(n)Good at assessing equivlencelots of variants, well studiedThe bad:Sensitive to variance of signalAll “far” things are “very far”Distribution Distance FunctionsMotivationDistribution Distance FunctionsEarth Mover Distance ApproximationsBin-Bin ComparisonsCross-Bin