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

36、“不可能”这个字(法语是一个字)，只在愚人的字典中找得到。--拿破仑。37、不要生气要争气，不要看破要突破，不要嫉妒要欣赏，不要托延要积极，不要心动要行动。38、勤奋，机会，乐观是成功的三要素。(注意：传统观念认为勤奋和机会是成功的要素，但是经过统计学和成功人士的分析得出，乐观是成功的第三要素。39、没有不老的誓言，没有不变的承诺，踏上旅途，义无反顾。40、对时间的价值没有没有深切认识的人，决不会坚韧勤勉。ApproximateNearestSubspace：最近的子空间近似ApproximateNearestSubspace：最近的子空间近似36、“不可能”这个字(法语是一个字)，只在愚人的字典中找得到。--拿破仑。37、不要生气要争气，不要看破要突破，不要嫉妒要欣赏，不要托延要积极，不要心动要行动。38、勤奋，机会，乐观是成功的三要素。(注意：传统观念认为勤奋和机会是成功的要素，但是经过统计学和成功人士的分析得出，乐观是成功的第三要素。39、没有不老的誓言，没有不变的承诺，踏上旅途，义无反顾。40、对时间的价值没有没有深切认识的人，决不会坚韧勤勉。ApproximateNearestSubspace：最近的子空间近似ApproximateNearestSubspaceSearch

withapplicationstopatternrecognitionRonenBasriTalHassnerLihiZelnik-ManorWeizmannInstituteCaltechSubspacesinComputerVisionZelnik-Manor&Irani,PAMI’06IlluminationFacesObjectsViewpoint,MotionDynamictextures…ApproximateNearestSubspaceSearch

withapplicationstopatternrecognitionRonenBasriTalHassnerLihiZelnik-ManorWeizmannInstituteCaltechSubspacesinComputerVisionZelnik-Manor&Irani,PAMI’06Basri&Jacobs,PAMI’03Nayaretal.,IUW’96IlluminationFacesObjectsViewpoint,MotionDynamictextures…QueryNearestSubspaceSearchWhichistheNearestSubspace?SequentialSearchSequentialsearch:

O(ndk)Tooslow!!Isthereasublinearsolution?Databased

dimensionsn

subspacesk

subspacedimensionARelatedProblem:

NearestNeighborSearchd

dimensionsn

pointsSequentialsearch:

O(nd)Thereisasublinearsolution!DatabaseApproximateNN(1+)rTreesearch(KD-trees)LocalitySensitiveHashingFast!!Query:Logarithmic

Preprocessing:O(dn)rIsitpossibletospeed-up

NearestSubspaceSearch?Existingpoint-basedmethodscannotbeappliedTreesearchLSHOurSuggestedApproachReductiontopointsWorksforboth

linearandaffinespacesRuntimeSequentialOurDatabasesizeProblemDefinitionFindMappingApplystandardpointANNtou,vAlinearfunctionoforiginaldistanceMonotonicindistanceIndependentmappingsFindingaReductionConstants?DependsonqueryFeelinglucky?Wearelucky!!BasicReductionWant:minimize/GeometryofBasicReductionDatabaseLiesonasphereandonahyper-planeQueryLiesonaconeImprovingtheReductionFinalReduction=constantsCanWeDoBetter?If=0TrivialmappingAdditiveConstantisInherentFinalMappingGeometryANSComplexitiesPreprocessing:

O(nkd2)LinearinnLoginnQuery:

O(d2)+TANN(n,d2)DimensionalityMaybeLargeEmbeddingind2Mightneedtousesmall

εCurrentsolution:Userandomprojections(useJohnson-LindenstraussLemma)RepeatseveraltimesandselectthenearestSyntheticDataVaryingdatabasesized=60,k=4RuntimeSequentialOurDatabasesizeVaryingdimensionn=5000,k=4RuntimeSequentialOurdimensionFaceRecognition(YaleB)Database64illuminationsk=9subspacesQuery:NewilluminationFaceRecognitionResultWrongMatchWrongPersonTrueNSApproxNSRetilingwithPatchesPatchdatabaseQueryApproxImageWantedRetilingwithSubspacesSubspacedatabaseQueryApproxImageWantedPatches+ANN~0.6secSubspaces+ANS~1.2secPatches+ANN~0.6secSubspaces+ANS~1.2secSummaryFast,approximatenearestsubspacesearchReductiontopointANNUsefulapplicationsincomputervisionDisadvantages:Embeddingind2AdditiveconstantOthermethods?Additionalapplications?Alotmoretobedone…..THANKYOU谢谢你的阅读知识就是财富丰富你的人生41