Approximate-Nearest-Subspace：最近的子空间近似教学课件2

36、“不可能”这个字(法语是一个字)，只在愚人的字典中找得到。-拿破仑。37、不要生气要争气，不要看破要突破，不要嫉妒要欣赏，不要托延要积极，不要心动要行动。38、勤奋，机会，乐观是成功的三要素。(注意：传统观念认为勤奋和机会是成功的要素，但是经过统计学和成功人士的分析得出，乐观是成功的第三要素。39、没有不老的誓言，没有不变的承诺，踏上旅途，义无反顾。40、对时间的价值没有没有深切认识的人，决不会坚韧勤勉。Approximate Nearest Subspace：最近的子空间近似Approximate Nearest Subspace Searchwith applications to pattern recognitionRonen Basri Tal Hassner Lihi Zelnik-ManorWeizmann Institute CaltechSubspaces in Computer VisionZelnik-Manor&Irani,PAMI06Basri&Jacobs,PAMI03Nayar et al.,IUW96IlluminationFacesObjectsViewpoint,MotionDynamic texturesQuery Nearest Subspace SearchWhich is the Nearest Subspace?Sequential SearchSequential search:O(ndk)Too slow!Is there a sublinear solution?Databased dimensionsn subspacesk subspace dimensionA Related Problem:Nearest Neighbor Searchd dimensionsn pointsSequential search:O(nd)There is a sublinear solution!DatabaseApproximate NN(1+)r Tree search(KD-trees)Locality Sensitive HashingFast!Query:Logarithmic Preprocessing:O(dn)rIs it possible to speed-up Nearest Subspace Search?Existing point-based methods cannot be applied Tree searchLSHOur Suggested ApproachReduction to pointsWorks for bothlinear and affine spacesRun time Sequential Our Database size Problem DefinitionFind MappingApply standard point ANN to u,vA linear function of original distanceMonotonic in distanceIndependent mappingsFinding a ReductionConstants?Depends on queryFeeling lucky?We are lucky!Basic Reduction Want:minimize /Geometry of Basic ReductionDatabase Lies on a sphere and on a hyper-planeQueryLies on a coneImproving the ReductionFinal Reduction=constants Can We Do Better?If=0Trivial mappingAdditive Constant is InherentFinal Mapping GeometryANS ComplexitiesPreprocessing:O(nkd2)Linear in nLog in nQuery:O(d2)+TANN(n,d2)Dimensionality May be Large Embedding in d2 Might need to use small Current solution:Use random projections(use Johnson-Lindenstrauss Lemma)Repeat several times and select the nearestSynthetic DataVarying database size d=60,k=4 Run time Sequential Our Database size Varying dimension n=5000,k=4 Run time Sequential Our dimension Face Recognition(YaleB)Database64 illuminationsk=9 subspaces Query:New illuminationFace Recognition Result Wrong Match Wrong Person True NS Approx NS Retiling with PatchesPatch database Query Approx Image Wanted Retiling with SubspacesSubspace database Query Approx Image Wanted Patches+ANN0.6secSubspaces+ANS1.2 secPatches+ANN0.6secSubspaces+ANS1.2 secSummaryFast,approximate nearest subspace searchReduction to point ANNUseful applications in computer visionDisadvantages:Embedding in d2Additive constant Other methods?Additional applications?A lot more to be done.THANK YOU谢谢你的阅读v知识就是财富v丰富你的人生41、学问是异常珍贵的东西，从任何源泉吸收都不可耻。阿卜日法拉兹42、只有在人群中间，才能认识自己。德国43、重复别人所说的话，只需要教育；而要挑战别人所说的话，则需要头脑。玛丽佩蒂博恩普尔44、卓越的人一大优点是：在不利与艰难的遭遇里百折不饶。贝多芬45、自己的饭量自己知道。苏联