1BoostMapBoostMap: A Method for : A Method for Efficient Approximate Efficient Approximate Similarity RankingsSimilarity RankingsPresenter: Boris BabenkoCSE 252C, FALL2006Vassilis Athitsos, Jonathan Alon, Stan Sclaroff, and George KolliosCVPR’04The ProblemThe ProblemFor any general recognition task, there is For any general recognition task, there is usually a database of labeled imagesusually a database of labeled imagesWhen a novel image is seen, a distance is When a novel image is seen, a distance is computed between this image and every computed between this image and every image in the database.image in the database.2The Problem: an illustrationThe Problem: an illustrationquerydatabase…Some distance functionThe ProblemThe ProblemThe distance function can be anything! The distance function can be anything! Can be nonCan be non--metric, bizarre, etc.metric, bizarre, etc.Each query requires Each query requires nndistance distance calculations for a database of size calculations for a database of size n.n.What if the distance function is very What if the distance function is very complicated and expensive complicated and expensive computationally?computationally?3The Solution: The Solution: BoostMapBoostMapBoostMapBoostMapis a method that can reduce the is a method that can reduce the number of expensive distance calculations number of expensive distance calculations down to some down to some d << nd << nIt works for ANY distance functionIt works for ANY distance functionFormalitiesFormalitiesLet Let X X be a set of objects, and be a set of objects, and DDXX(x1,x2) (x1,x2) be a distance be a distance measure between objects of this set.measure between objects of this set.Let (Let (q,x1,x2q,x1,x2) be a triplet of objects from the set) be a triplet of objects from the setDefine the Proximity FunctionDefine the Proximity FunctionPPXX(q,x1,x2)(q,x1,x2)4FormalitiesFormalitiesSuppose we had an embedding Suppose we had an embedding F: X F: X --> R> Rd d Let Let PPRRbe proximity function of be proximity function of F(X)F(X)that that uses some metric distance uses some metric distance DDRR(e.g. L(e.g. L11, L, L22, , etc)etc)RRRRRRRFormalitiesFormalitiesDefine a Proximity Classifier Define a Proximity Classifier F(q,x1,x2)F(q,x1,x2)We want We want FFto output the same thing as to output the same thing as PPXX5Computing ErrorComputing ErrorFor a single triple For a single triple (q,x1,x2)(q,x1,x2)For all your dataFor all your dataHow do we get the embedding F?How do we get the embedding F?LetLet’’s think about simpler embeddings s think about simpler embeddings F: X F: X --> R> RGenerate many random simple Generate many random simple embeddings and throw them into embeddings and throw them into AdaBoostAdaBoostOur final embedding will be a linear Our final embedding will be a linear combination of the simple embeddingscombination of the simple embeddings61D Embeddings1D EmbeddingsUse a reference object rUse a reference object rClassifies 46 out of 60 triplets correct. Classifies 46 out of 60 triplets correct. Incorrect: Incorrect: (b, a, c); (c, b, d); (d, b, r)1.201.21D Embeddings1D EmbeddingsUse Use ““pivot pointspivot points””7Boost 1D embeddingBoost 1D embeddingHow many people are not familiar with How many people are not familiar with boosting?boosting?Use training data (which can be generated Use training data (which can be generated by using the original distance function by using the original distance function DDxx))AdaBoostAdaBoostoutputs a set of outputs a set of dd1D 1D embeddings, and a weight for each.embeddings, and a weight for each.Final Final BoostMapBoostMapEmbeddingEmbeddingWeghtedWeghtedL1 distance that combines the L1 distance that combines the chosen 1D embeddings and their weights.chosen 1D embeddings and their weights.Suppose we chose Suppose we chose d d embeddings. To embeddings. To compute the embedded distance between compute the embedded distance between XXuuand and XXvv: :8What do we end up with?What do we end up with?An embedding An embedding F: X F: X --> R> Rd d which uses up to which uses up to 2d2dreference objects.reference objects.A weighted L1 metric in this A weighted L1 metric in this RRd d space.space.We know that the embedding in some We know that the embedding in some sense preserves the proximity.sense preserves the proximity.At RunAt Run--timetimeSuppose we want to compare object Suppose we want to compare object QQ(query) to objects (query) to objects X1, X2X1, X2……XnXnin the DB.in the DB.Need to compute Need to compute d d embeddings of embeddings of Q: Q: O(dO(d) calls to ) calls to DDxxCompute weighted L1 distance between Compute weighted L1 distance between QQand and X1, X2X1, X2……XnXn––much cheaper than much cheaper than computingcomputingDDxxn times.n times.9Does it work?Does it work?Hand experimentHand experimentOriginal distance measure: Chamfer Original distance measure: Chamfer distance (takes 260s to query)distance (takes 260s to query)Does it work?Does it work?Hand experimentHand experiment10Does it work?Does it work?Shape contextsShape