云計算時代的社交網(wǎng)絡平臺和技術(shù)Google-NanChang-Talk

云計算時代的社交網(wǎng)絡

平臺和技術(shù)

張智威副院長,研究院,谷歌中國教授,電機工程系,加州大學10/30/20231EdChang180million(↑25%)208million(↑

3%)60million(↑

90%)60million(↑

29%)500million180million600kEngineeringGraduatesMobilePhonesBroadbandUsersInternetPopulationChinaU.S.ChinaOpportunity

China&USin2006-0772k7200010/30/20232EdChangGoogleChinaSize(~700)200engineers400otheremployeesAlmost100internsLocationsBeijing(2005)Taipei(2006)Shanghai(2007)10/30/20233EdChangOrganizingtheWorld’sInformation,Socially社區(qū)平臺(SocialPlatform)云運算(CloudComputing)結(jié)論與前瞻(ConcludingRemarks)10/30/20234EdChangWeb1.0.htm.htm.htm.jpg.jpg.doc.htm.msg.htm.htm10/30/20235EdChangWebwithPeople(2.0).htm.jpg.doc.xls.msg.htm.htm.jpg.msg.htm10/30/20236EdChang+SocialPlatforms.htm.jpg.doc.xls.msg.htm.htm.jpg.msg.htmApp(Gadget)App(Gadget)10/30/20237EdChang10/30/20238EdChang10/30/20239EdChang10/30/202310EdChang10/30/202311EdChang開放社區(qū)平臺10/30/202312EdChang10/30/202313EdChang10/30/202314EdChang10/30/202315EdChang10/30/202316EdChang開放社區(qū)平臺社區(qū)平臺1我是誰2我的朋友3他的活動10/30/202317EdChang10/30/202318EdChang10/30/202319EdChang開放社區(qū)平臺社區(qū)平臺1我是誰2我的朋友3他的活動4他的東西10/30/202320EdChang10/30/202321EdChangSocialGraph10/30/202322EdChang10/30/202323EdChangWhatUsersWant?PeoplecareaboutotherpeoplecareaboutpeopletheyknowconnecttopeopletheydonotknowDiscoverinterestinginformationbasedonotherpeopleaboutwhootherpeopleareaboutwhatotherpeoplearedoing10/30/202324EdChangInformationOverflowChallengeToomanypeople,toomanychoicesofforumsandapps“Isoonneedtohireafull-timetomanagemyonlinesocialnetworks”DesiringaSocialNetworkRecommendationSystem10/30/202325EdChangRecommendationSystemFriendRecommendationCommunity/ForumRecommendationApplicationSuggestionAdsMatching10/30/202326EdChangOrganizingtheWorld’sInformation,Socially社區(qū)平臺(SocialPlatform)云運算(CloudComputing)結(jié)論與前瞻(ConcludingRemarks)10/30/202327EdChangpicturesource:http://

（1）數(shù)據(jù)在云端不怕丟失不必備份（2）軟件在云端不必下載自動升級（3）無所不在的云計算任何設(shè)備登錄后就是你的（4）無限強大的云計算無限空間無限速度業(yè)界趨勢：云計算時代的到來10/30/202328EdChang互聯(lián)網(wǎng)搜索：云計算的例子1.用戶輸入查詢關(guān)鍵字CloudComputing2.分布式預處理數(shù)據(jù)以便為搜索提供服務:GoogleInfrastructure(thousandsofcommodityserversaroundtheworld)MapReduceformassdataprocessingGoogleFileSystem3.返回搜索結(jié)果10/30/202329EdChangGivenamatrixthat“encodes”dataCollaborativeFiltering10/30/202330EdChangGivenamatrixthat“encodes”dataManyapplications(collaborativefiltering):

User

–

CommunityUser–UserAds–UserAds–Communityetc.UsersCommunities10/30/202331EdChangCollaborativeFiltering(CF)

[Breese,HeckermanandKadie1998]Memory-basedGivenuseru,find“similar”users(knearestneighbors)Boughtsimilaritems,sawsimilarmovies,similarprofiles,etc.DifferentsimilaritymeasuresyielddifferenttechniquesMakepredictionsbasedonthepreferencesofthese“similar”usersModel-basedBuildamodelofrelationshipbetweensubjectmattersMakepredictionsbasedontheconstructedmodel10/30/202332EdChangMemory-BasedModel

[Goldbertetal.1992;Resniketal.1994;Konstantetal.1997]

ProsSimplicity,avoidmodel-buildingstageConsMemoryandTimeconsuming,usestheentiredatabaseeverytimetomakeapredictionCannotmakepredictioniftheuserhasnoitemsincommonwithotherusers10/30/202333EdChangModel-BasedModel

[Breeseetal.1998;Hoffman1999;Bleietal.2004]

ProsScalability,modelismuchsmallerthantheactualdatasetFasterprediction,querythemodelinsteadoftheentiredatasetConsModel-buildingtakestime10/30/202334EdChangAlgorithmSelectionCriteriaNear-real-timeRecommendationScalableTrainingIncrementalTrainingisDesirableCandealwithdatascarcityCloudComputing!10/30/202335EdChangModel-basedPriorWorkLatentSemanticAnalysis(LSA)ProbabilisticLSA(PLSA)LatentDirichletAllocation(LDA)10/30/202336EdChangLatentSemanticAnalysis(LSA)

[Deerwesteretal.1990]Maphigh-dimensionalcountvectorstolowerdimensionalrepresentationcalledlatentsemanticspaceBySVDdecomposition:A=U∑VTA=Word-documentco-occurrencematrixUij

=Howlikelywordibelongstotopicj∑jj

=HowsignificanttopicjisVijT=HowlikelytopicibelongstodocjWordsDocsTopicsDocsTopicsTopicsTopicsWordsWxDWxTTxTTxD10/30/202337EdChangLatentSemanticAnalysis(cont.)LSAkeepsk-largestsingularvaluesLow-rankapproximationtotheoriginalmatrixSavespace,de-noisifiedandreducesparsityMakerecommendationsusing?Word-wordsimilarity:??TDoc-docsimilarity:?T

?Word-docrelationship:?WordsDocsTopicsDocsTopicsTopicsTopicsWordsWxDWxKKxKKxD????10/30/202338EdChangProbabilisticLatentSemanticAnalysis(PLSA)[Hoffman1999;Hoffman2004]DocumentisviewedasabagofwordsAlatentsemanticlayerisconstructedinbetweendocumentsandwordsP(w,d)=P(d)P(w|d)=P(d)∑zP(w|z)P(z|d)ProbabilitydeliversexplicitmeaningP(w|w),P(d|d),P(d,w)ModellearningviaEMalgorithmP(d)dwzP(z|d)P(w|z)10/30/202339EdChangPLSAextensionsPHITS[Cohn&Chang2000]Modeldocument-citationco-occurrenceAlinearcombinationofPLSAandPHITS[Cohn&Hoffmann2001]Modelcontents(words)andinter-connectivityofdocumentsLDA[Bleietal.2003]ProvideacompletegenerativemodelwithDirichletpriorAT[Griffiths&Steyvers2004]IncludeauthorshipinformationDocumentiscategorizedbyauthorsandtopicsART[McCallum2004]IncludeemailrecipientasadditionalinformationEmailiscategorizedbyauthor,recipientsandtopics10/30/202340EdChangCombinationalCollaborativeFiltering(CCF)FusemultipleinformationAlleviatetheinformationsparsityproblemHybridtrainingschemeGibbssamplingasinitializationsforEMalgorithmParallelizationAchievelinearspeedupwiththenumberofmachines10/30/202341EdChangNotationsGivenacollectionofco-occurrencedataCommunity:C={c1,c2,…,cN}User:U={u1,u2,…,uM}Description:D={d1,d2,…,dV}Latentaspect:Z={z1,z2,…,zK}ModelsBaselinemodelsCommunity-User(C-U)modelCommunity-Description(C-D)modelCCF:CombinationalCollaborativeFilteringCombinesbothbaselinemodels10/30/202342EdChangBaselineModelsCommunity-User(C-U)modelCommunity-Description(C-D)modelCommunityisviewedasabagofusers

canduarerenderedconditionallyindependentbyintroducingzGenerativeprocess,foreachuseru1.Acommunitycischosenuniformly2.AtopiczisselectedfromP(z|c)3.AuseruisgeneratedfromP(u|z)Communityisviewedasabagofwords

canddarerenderedconditionallyindependentbyintroducingzGenerativeprocess,foreachwordd1.Acommunitycischosenuniformly2.AtopiczisselectedfromP(z|c)3.AworddisgeneratedfromP(d|z)10/30/202343EdChangBaselineModels(cont.)Community-User(C-U)modelCommunity-Description(C-D)model

Pros1.Personalizedcommunitysuggestion

Cons

1.C-Umatrixissparse,maysufferfrom

informationsparsityproblem2.Cannottakeadvantageofcontent

similaritybetweencommunities

Pros1.Clustercommunitiesbasedoncommunitycontent(descriptionwords)

Cons

1.Nopersonalizedrecommendation2.Donotconsidertheoverlappedusersbetweencommunities10/30/202344EdChangCCFModelCombinationalCollaborativeFiltering(CCF)modelCCFcombinesbothbaselinemodelsAcommunityisviewedas

-abagofusersANDabagofwordsByaddingC-U,CCFcanperformpersonalizedrecommendationwhichC-Dalonecannot

ByaddingC-D,CCFcanperformbetterpersonalizedrecommendationthanC-UalonewhichmaysufferfromsparsityThingsCCFcandothatC-UandC-Dcannot-P(d|u),relateusertoword-Usefulforusertargetingads10/30/202345EdChangAlgorithmRequirementsNear-real-timeRecommendationScalableTrainingIncrementalTrainingisDesirable10/30/202346EdChangParallelizingCCFDetailsomitted10/30/202347EdChangpicturesource:http://

（1）數(shù)據(jù)在云端不怕丟失不必備份（2）軟件在云端不必下載自動升級（3）無所不在的云計算任何設(shè)備登錄后就是你的（4）無限強大的云計算無限空間無限速度業(yè)界趨勢：云計算時代的到來10/30/202348EdChangExperimentsonOrkutDatasetDatadescriptionCollectedonJuly26,2007TwotypesofdatawereextractedCommunity-user,community-description312,385users109,987communities191,034uniqueEnglishwordsCommunityrecommendationCommunitysimilarity/clusteringUsersimilaritySpeedup10/30/202349EdChangCommunityRecommendationEvaluationMethodNoground-truth,nouserclicksavailableLeave-one-out:randomlydeleteonecommunityforeachuserWhetherthedeletedcommunitycanberecoveredEvaluationmetricPrecisionandRecall10/30/202350EdChangResultsObservations:

CCFoutperformsC-UFortop20,precision/recallofCCF

aretwicehigherthanthoseofC-U

Themorecommunitiesauserhasjoined,thebetterCCF/C-Ucanpredict10/30/202351EdChangRuntimeSpeedupTheOrkutdatasetenjoysalinearspeedupwhenthenumberofmachinesisupto100Reducesthetrainingtimefromonedaytolessthan14minutesBut,whatmakesthespeedupslowdownafter100machines?10/30/202352EdChangRuntimeSpeedup(cont.)Trainingtimeconsistsoftwoparts:Computationtime(Comp)Communicationtime(Comm)10/30/202353EdChangCCFSummaryCombinationalCollaborativeFilteringFusebagsofwordsandbagsofusersinformationHybridtrainingprovidesbetterinitializationsforEMratherthanrandomseedingParallelizetohandlelarge-scaledatasets10/30/202354EdChangChina’sContributionson/to

CloudComputingParallelCCFParallelSVMs(KernelMachines)ParallelSVDParallelSpectralClusteringParallelExpectationMaximizationParallelAssociationMiningParallelLDA

10/30/202355EdChangSpeedingupSVMs

[NIPS2007]ApproximateMatrixFactorizationParallelizationOpensource@/p/psvm350+downloadssinceDecember07Ataskthattakes7dayson1

machinetakes1hourson500machines10/30/202356EdChangIncompleteCholeskyFactorization(ICF)nxnnxppxnp<<nConserveStorage10/30/202357EdChangMatrixProduct=pxnnxppxp10/30/202358EdChangOrganizingtheWorld’sInformation,Socially社區(qū)平臺(SocialPlatform)云運算(CloudComputing)結(jié)論與前瞻(ConcludingRemarks)10/30/202359EdChangWebWithPeople.htm.htm.htm.jpg.jpg.doc.xls.msg.msg.htm10/30/202360EdChangWhatNextforWebSearch?

PersonalizationReturnqueryresultsconsideringpersonalpreferencesExample:DisambiguatesynonymlikefujiOops:severaltried,theproblemishardTrainingdatadifficulttocollectenough(forcollaborativefiltering)Computationalintensivetosupportpersonalization(e.g.,forpersonalizingpagerank)Userprofilemaybeincomplete,erroneous10/30/202361EdChang個人搜索智能搜索搜索“富士”可返回富士山富士蘋果富士相機10/30/202362EdChang10/30/202363EdChang10/30/202364EdChang10/30/202365EdChang10/30/202366EdChangOrganizingWorld’sInformation,SociallyWebisaCollectionofDocumentsandPeopleRecommendationisaPersonalized,PushModelofSearchCollaborativeFilteringRequiresDenseInformationtobeEffectiveCloudComputingisEssential10/30/202367EdChangReferences[1]Alexainternet.http:///.[2]D.M.BleiandM.I.Jordan.Variationalmethodsforthe

dirichletprocess.InProc.ofthe21stinternational

conferenceonMachinelearning,pages373-380,2004.[3]D.M.Blei,A.Y.Ng,andM.I.Jordan.Latentdirichlet

allocation.JournalofMachineLearningResearch,

3:993-1022,2003.[4]D.CohnandH.Chang.Learningtoprobabilisticallyidentifyauthoritativedocuments.InProc.oftheSeventeenthInternationalConferenceonMachineLearning,pages167-174,2000.[5]D.CohnandT.Hofmann.Themissinglink-aprobabilisticmodelofdocumentcontentandhypertextconnectivity.InAdvancesinNeuralInformationProcessingSystems13,pages430-436,2001.[6]S.C.Deerwester,S.T.Dumais,T.K.Landauer,G.W.Furnas,andR.A.Harshman.Indexingbylatentsemanticanalysis.JournaloftheAmericanSocietyofInformationScience,41(6):391-407,1990.[7]A.P.Dempster,N.M.Laird,andD.B.Rubin.Maximumlikelihoodfromincompletedataviatheemalgorithm.JournaloftheRoyalStatisticalSociety.SeriesB(Methodological),39(1):1-38,1977.[8]S.GemanandD.Geman.Stochasticrelaxation,gibbsdistributions,andthebayesianrestorationofimages.IEEETransactionsonPatternrecognitionandMachineIntelligence,6:721-741,1984.[9]T.Hofmann.Probabilisticlatentsemanticindexing.InProc.ofUncertaintyinArti

cialIntelligence,pages289-296,1999.[10]T.Hofmann.Latentsemanticmodelsforcollaborativefiltering.ACMTransactionsonInformationSystem,22(1):89-115,2004.[11]A.McCallum,A.Corrada-Emmanuel,andX.Wang.Theauthor-recipient-topicmodelfortopicandrolediscoveryinsocialnetworks:Experimentswithenronandacademicemail.Technicalreport,ComputerScience,UniversityofMassachusettsAmherst,2004.[12]D.Newman,A.Asuncion,P.Smyth,andM.Welling.Distributedinferenceforlatentdirichletallocation.InAdvancesinNeuralInformationProcessingSystems20,2007.[13]M.Ramoni,P.Sebastiani,andP.Cohen.Bayesianclusteringbydynamics.MachineLearning,47(1):91-121,2002.10/30/202368EdChangReferences(cont.)[14]R.Salakhutdinov,A.Mnih,andG.Hinton.Restrictedboltzmannmachinesforcollaborative

ltering.InProc.Ofthe24thinternationalconferenceonMachinelearning,pages791-798,2007.[15]E.Spertus,M.Sahami,andO.Buyukkokten.Evaluatingsimilaritymeasures:alarge-scalestudyintheorkutsocialnetwork.InProc.ofthe11thACMSIGKDDinternationalconferenceonKnowledgediscoveryindatamining,pages678-684,2005.[16]M.Steyvers,P.Smyth,M.Rosen-Zvi,andT.Gri

ths.Probabilisticauthor-topicmodelsforinformationdiscovery.InProc.ofthe10thACMSIGKDDinternationalconferenceonKnowledgediscoveryanddatamining,pages306-315,2004.[17]A.StrehlandJ.Ghosh.Clusterensembles-aknowledgereuseframeworkforcombiningmultiplepartitions.JournalonMachineLearningResearch(JMLR),3:583-617,2002.[18]T.ZhangandV.S.Iyengar.Recommendersystemsusinglinearclassi

ers.JournalofMachineLearningResearch,2:313-334,2002.[19]S.ZhongandJ.Ghosh.Generativemodel-basedclusteringofdocuments:acomparativestudy.KnowledgeandInformationSystems(KAIS),8:374-384,2005.[20]L.AdmicandE.Adar.Howtosearchasocialnetwork.2004[21]T.L.GriffithsandM.Steyvers.Findingscientifictopics.ProceedingsoftheNationalAcademyofSciences,pages5228-5235,2004.[22]H.Kautz,B.Selman,andM.Shah.ReferralWeb:Combiningsocialnetworksandcollaborativefiltering.CommunitcationsoftheACM,3:63-65,1997.[23]R.Agrawal,T.Imielnski,A.Swami.Miningassociationrulesbetweensetsofitemsinlargedatabses.SIGMODRec.,22:207-116,1993.[24]J.S.Breese,D.Heckerman,andC.Kadie.Empiricalanalysisofpredictivealgorithmsforcollaborativefiltering.InProceedingsoftheFourteenthConferenceonUncertaintyinArtificalIntelligence,1998.[25]M.DeshpandeandG.Karypis.Item-basedtop-nrecommendationalgorithms.ACMTrans.Inf.Syst.,22(1):143-177,2004.10/30/202369EdChangReferences(cont.)[26]B.M.Sarwar,G.Karypis,J.A.Konstan,andJ.Reidl.Item-basedcollaborativefilteringrecommendationalgorithms.InProceedingsofthe10thInternationalWorldWideWebConference,pages285-295,2001.[27]