搜索
1流形学习和人工智能搜索及大数据应用陈一昕华盛顿大学计算机系ManifoldLearning(流形学习）Highdimensionaldataoftenlieinalow-dimensionalmanifoldUsefulinfeatureselection,dimensionalityreduction,classification,clustering,visualization26464ImagespaceFaceslieonalow-DmanifoldintheimagespaceManifoldfaceslieon3featuresneededLeft-RightPoseUp-DownPoseLightingDirectionImageManifoldLearning?LinearInterpolation?NonlinearManifoldLearning?6ManifoldLearning高维数据空间data/observationspace低维嵌入空间embedding/coordinatespace7FiguresfromISOMAPpaper8Figurefrom*SearchA*algorithm:alwaysexpandsthenodexwithminimumf(x)=g(x)+h(x)h(x)istheheuristicfunctionStateGraph16Memory-basedHeuristicHeuristicOfflineBroadcastStoreSolvetheproblemrepeatedly17HeuristicPerfectHeuristicSpaceToohuge!!!18EuclideanHeuristicRayneret.al(2011)19EuclideanHeuristicRayneret.al(2011)20EuclideanHeuristicRayneret.al(2011)21Heuristiccompression22Heuristicrequirements(1)admissible(2)consistent(3)closetotruedistanceRayneret.al(2011)23Heuristicoptimization24MaximumVarianceReduction(MVU)：流形学习算法Weinbergeret.al200425规范化处理Weinbergeret.al200426半正定规划技术Weinbergeret.al2004VarianceLocaldistanceconstraintsCenteringconstraintNotConvex!!!27LocaldistanceconstraintsCenteringconstraintObjectivefunction28MaximumVarianceUnfolding(MVU)whereWeinbergeret.al2004ConvexIntroduceprojectionerror!!!LocaldistanceconstraintsCenteringconstraint29LimitationsofMVUVerySlow!!!Atmost6000nodes.NotapplicabletoBigData30MaximumVarianceCorrection(MVC)33OverviewofMVCInputLoop34Recall35FeasibleInitialEmbedding36OverviewofMVCPost-process37(0,0)38(0,0)39(0,0)44(0,0)45(0,0)46(0,0)47Fixed!48SubgraphOptimization48Notconvex!!!4950子图的半正定规划Embedding53MVCon5-puzzle54MVCon6-blocksworldBetterRescaledIsomapMVUMVCinitializedwithIsomap55#Expandednodeson6-blocksworldDifferentialHeuristicMVUMVCRescaledIsomapBetter56Speedupoverdifferentialheuristic57TrainingTime58Goal-OrientedEuclideanHeuristic59Goal-OrientedExamples86574231123546784728536147285361NotagoalPotentialgoalsDisordered60HeuristicSearchStateGraphgoalOnlytheheuristicstothegoalstateareneeded61Goal-OrientedSettingsOnlyoptimizetheheuristicstothesepotentialgoals.62Goal-OrientedMVU(GOMVU)minimizesadmissibilitygaptogoalsGuaranteesadmissibilityandconsistency63MVCextension:Scaleston200,000statesGoal-OrientedMVU(GOMVU)Goal-orientedEuclideanheuristic(GOEH)If,thenGOMVUbecomesMVU65StateHeuristicEnhancement(SHE)NewheuristictothegoalGOEHStateheuristicenhancementForeachstateandgoalstatePost-processesGOEH:furtherminimizesadmissibilitygap66StateHeuristicEnhancementEmbeddingStateHeuristicEnhancement(SHE)vectorarealnumberNolongerconsistentMemory:UseB’searchinsteadofA*search[Mero1984]67Overview:GOEH+SHEObtaintheembeddingwithgoal-orientedMVCComputestateheuristicenhancement(SHE)GiventhestategraphandthegoalsetOfflinetrainingMemoryOnlineSearchB’search:68ExperimentalResultsProblemTime6-block4K609m7-block37K1001h7-puzzle20K12045m8-puzzle181K72010hrobot150K806hrobot290K1009hOfflinetrainingtimeofGOEH+SHEEH:EuclideanheuristicGOEH:Goal-orientedEHSHE:StateheuristicenhancementDiff:DifferentialheuristicDiff:numberofpivotsis4Memory:EHorGOEH:GOEH+SHE:69SpeeduponOnlineSearchBetterDifferentialHeuristicGOEH+SHEGOEHEH70ReferencesW.Chen,K.Weinberger,andY.Chen,MaximumVarianceCorrectionwithApplicationtoA*Search,Proc.InternationalConferenceonMachineLearning(ICML-13),2013.W.Chen,Y.Chen,K.Weinberger,Q.Lu,andX.Chen,Goal-OrientedEuclideanHeuristicswithManifoldLearning,Proc.AAAIConferenceonArtificialIntelligence(AAAI-13),2013.Q.Lu,W.Chen,Y.Chen,K.Weinberger,andX.Chen,UtilizingLandmarksinEuclideanHeuristicsforOptimalPlanning,Late-BreakingTrack,Proc.AAAIConferenceonArtificialIntelligence(AAAI-13),2013.