全国知识图谱与语义计算大会ccks2016工业界论坛-t4wei

知识图谱的集成 计算机科学与软件新技术国CCKS2016讲习班,提 IntroductiontoSemanticWebandknowledge PartI:ontology PartII:entity PartIII:anapplicationtodata 2Semantic SemanticWebwasathoughtfromTimBerners- GiveformalmeaningstoWebinformation– Web1.0(page)àWeb2.0(social)àWeb3.0(awebof SemanticWebiscommonformats integrationandcombinationofdrawnfromdiverselanguages recordinghowthedatarelatestoreal-worldobjects3 RDF

谓主 宾

LayerTheworldisnotmadeofstrings,butismadeofthings4Linkeddata 数据/关联数据 AsarealizationofSemantic LinkedDatareferstoacollectionofinterrelated Usedforlarge-scaleintegrationof,reasoningon,dataonthe LinkeddataUseURIstonameUseHTTPURIs(canbeProvideusefulinformationusingopenWebstandards(e.g.Includelinkstootherrelated5Linkedopendata(LOD)1,000+

lifesocial

6Knowledge KnowledgeGraphisaknowledgebaseusedby toenhanceitssearchengine’ssearchresultswithsemantic-searchinformationgatheredfromawidevarietyofsources¡知识图谱是使用的一个知识库， 亦可看作是一张巨大的图，节点表实体或概念，边则由属性或关系 除了关 (部分)真实世界的一个模 引入领域相关的 指定术语的含义(语义 使用合适的逻辑来形 描述 HeartisamuscularorganispartofthecirculatoryI.Horrocks.Ontologiesandthesemanticweb:thestorysofar. 大规模知识库/图谱规英文：4百万个实体，5亿个RDF三元125种1千万个实体，1.2亿个RDF三元4千万个实体，10亿个RDF三元 知识图谱6亿个实体，35亿条RDF三元WolframAlpha计算知识引擎,CMUNELL,知心,搜狗知立9知识图谱的技术族知识体已有知识 知识图谱提 IntroductiontoSemanticWebandknowledge PartI:ontology PartII:entity PartIII:anapplicationtodata Sincelonglongtimes SyntacticSchema- e.g.,“WeiHu”vs.Schema- Terminological e.g.,“notebook”vs.Data-entityData-entity Pragmatic OntheSemantic Datahasexplicitsemantics,richlinks,Ontology Thepopularityofontologiesisrapidlygrowing,andthenumberofontologiescontinuesincreasing Ontology Theprocessofdeterminingcorrespondencesbetween 本体匹配即发现一个三元组𝛥𝑂𝑂𝑀>，包括一个源本体𝑂，一个目标本体𝑂’，以及一个映射单元的集合𝑀={𝑚1𝑚2𝑚𝑛}。其中，𝑚𝑖表示一个基本的映射元，可以写成𝑚𝑖=<𝑖𝑑,𝑡𝑡𝑠>的四元 𝑖𝑑为映射单元的标识符，用于唯一标识该四元 𝑡,𝑡’分别为𝑂,𝑂’中的术 𝑠表示𝑡𝑡’之间的相似度，满足𝑠//另外，可以有𝒓表示𝒕,𝒕’之间的关系，常见的关系有等本体匹配：消除模式 （驱动的）Stateofthe语言学特征 本体中术语的语言学描 本地名(localnForanameNinanamespaceidentifiedbyaURII,thenamespacenameisI.ForanameNthatisnotinanamespace,thenamespacenamehasnovalue.Definition:IneithercasethelocalnameisN.n -->local 注释 其他：foaf:name、dc:title语言学特征 本体语言学特征使用现状的调 本地名使用多，有一些 注 邻居未充 词典查询耗√√√√√√类√√机器学√排序、S-类√ Edit 指两个字串之间，由一个转成另一个所需的最少编辑操作次 编辑操作包括替换、插入、删 一般来说，编辑距离越小，两个字串的相似度越 I-Sub:𝑆𝑖𝑚(𝑠1,𝑠2)=𝐶𝑜𝑚𝑚(𝑠1,𝑠2)−𝐷𝑖𝑓𝑓(𝑠1,𝑠2)+𝑤𝑖𝑛𝑘𝑙𝑒𝑟(𝑠1, biggestcommonsubstringtwo thelengthofunmatchedresultedfrominitialmatching 术语的语言学描述：本地名 、注 结点的语言学描述：前向邻居的语言学描 术语的邻居：主语邻居、谓语邻居、宾语邻 术语的虚拟文档：自身+𝑣𝑑𝑜𝑐 =𝑑𝑒𝑠𝑐 +𝛾3𝑑𝑒𝑠𝑐 +𝛾1 向量空间模型：TF-Stringsimilaritymetrics Lessthantwowordsperlabel:Jaro- Twoormorewordsper Synonyms:SoftJaccard,withLevensteinbase Nosynonyms:SoftJaccard,withLevensteinbase Lessthantwowordsperlabel:TF- Twoormorewordsper Synonyms:SoftTF-IDF,withJaro-Winklerbase DifferentLanguages:SoftTF-IDF,withJaro-Winklerbase Other:SoftTF-IDF,withJaro-Winklerbase结构特征 Intuition:termsoftwodistinctontologiesaresimilarwhenadjacenttermsarennSimilarityℴ^_`𝑥, =ℴ^𝑥, +

ij,k,lcl,k,ir

ℴ^(𝑎e,𝑏e)g𝑤(𝑎e,𝑏e,(𝑥,ℴ^(𝑎q,𝑏q)g𝑤(𝑎q,𝑏q,(𝑥,实例数据 Machine Jointprobability Instance Content Name Meta Relaxation

搜索引擎 distance sbetween -basedsimilarity𝑁𝐺𝐷𝑥, =maxlog𝑓𝑥,log𝑓 −log𝑓(𝑥,log𝑀−min{log𝑓𝑥,log 𝑓 isthenumber hitsforthesearchterm 𝑓 isthenumber hitsforthesearchterm 𝑓𝑥, isthenumber hitsforthetupleofsearchterms𝑥 𝑀isthenumberofwebpagesindexed (𝑀≈10`x)Ontologymatching Falcon- New Alotof(semi-)automaticalgorithmsand Mostareonlyapplicableforsmall ManyapplicationsrequirematchingBIG Medicineandbiology:GALEN,FMA, Agricultureandfood:AGROVOC, Librarycollections:Brinkman, Commonknowledge:DBpedia,

≥10K Adivide-and-conquer1.ontologypartitioningà2.blockmatchingà3.termRunningNewdirectionsnHolisticontologynIncreasingamountofdataàsimultaneouslymatchingnInput:asetΩ={𝑂1,…,𝑂𝑁}ofontologieswith𝑁>2nOutput:𝐴=𝐴12∪𝐴13∪𝐴23∪⋯nGuaranteetofindalwaysthesameAglobaloptimal Limitationofpairwise 𝐴isconsideredasalocalsolutiondependingoftheorderwhichtheontologymatchingiscarried e.g.𝐴12∪𝐴`}~≠𝐴13∪𝐴`~}≠𝐴23∪𝐴}~Holisticontology Extending um-weightedgraphmatchingproblemwithconstraints(cardinality,structuralandcoherence Threetypesof Class,objectproperty,data Representvirtualconnectionsbetweenthesametypesof Haveweightstorepresentsimilaritiesbetweenthe Correspondences(1:1)with umweightßà Linearconstraints:binary Classdecision disjoint 提 IntroductiontoSemanticWebandknowledge PartI:ontology PartII:entity PartIII:anapplicationtodata Entity SemanticWebdatahavereachedascaleinbillionsof Manydifferententitiesrefertothesamereal-world TypicallydenotedbyURIs,fromdistributeddata e.g.Wei¡ Entitylinkage:linkdifferententitiesthatrefertothesame a.k.a.coreferenceresolution,entitymatching,recordlinkage Theentitymatchingproblemwasoriginallydefinedin1959by beetal.andwasformalizedbyFelligiandSuntertenyearslater Outof31BRDFstatements,lessthan500Marelinksacross 实 的识 数 的消 消除描述这些标识符RDF数据之StateStateofthe Stateofthe InLOD,millionsofentitieshavealreadybeen However,potentialcandidatesarestill Current owl:sameAs,inversefunctionalpropertiesSimilaritycomputation(alsointhedatabase ComparepropertiesandvaluesofEquivalence AnRDFtriple:⟨𝑠,𝑝,𝑜⟩∈(𝐔∪𝐁)×𝐔×(𝐔∪𝐁∪ Same-asrelation: ⟨𝑠,owl:sameAs,𝑜⟩à⟨𝑠,𝑜⟩∈𝑆and⟨𝑜,𝑠⟩∈ Inversefunctionalproperty(IFP)relation: IFP:avaluecanonlybethevalueofthispropertyforasingle e.g.,𝑠1,foaf:mbox,𝑜,𝑠2,foaf:mbox,𝑜à⟨𝑠1,𝑠2⟩∈𝐼and⟨𝑠2,𝑠1⟩∈ Functionalproperty(FP)relation: Cardinalityrelation: owl:cardinality/owl:maxCardinality= 𝐾=𝑆∪𝐼∪𝐹∪𝐶+,𝐾isanequivalenceSimilarity Similarity LinkSimilarity 问题一般为以下形𝑟,𝑠 𝑠𝑖𝑚𝑟,𝑠>𝜏,𝑟∈𝑅,𝑠∈𝑆 𝑅和𝑆是两个字符串集合，𝜏是相似度 时间复杂度为：𝑂(𝑛}𝑁}) 现有的常规的方法是“过滤—验证”框 过滤阶段：使用各种过滤方法缩小候选集大 常见方 All-Pairs,ED-Join,PPJoin,PassJoin Naïvepairwise:𝑁}pairwise 1,000businesslistingseachfrom1,000differentcitiesacrossthe 1trillioncomparisons,11.6days(ifeachcomparisonis1 Mentionsfromdifferentcitiesareunlikelytobe Blockingcriterion: 1billioncomparisons,16minutes(ifeachcomparisonis1 Hashbased Pairwisesimilarity/neighborhoodbasedblocking Simpleblocking:invertedMachine Alinkage Learning Genetic ActiveSelectslinkcandidatestobelabeledbyaAhumanexpertlabelstheselectedlinkascorrectorincorrectThegeneticprogrammingalgorithmevolvesthepopulationoflinkagerules InLOD,millionsofentitieshavealreadybeen However,potentialcandidatesarestill Current Atpresent,probablymissmanypotentialSimilarity Toimprove,machine Time-consuming,labor-intensivetobuildalarge-scaletrainingDefinitionDefinition1.LetUbethesetofentitiesinasetDofdatasources.Given,theentitylinkageforuistoqueryaofforwhicharelationεwhereεlinksalltheentitiesinUthatrefertothesameobjectasudoes,arecoreferentwithHowtocombine?Oursolution: Query-drivenentity UseSearch/browsing–asystemknows“whattolink”onlyatqueryyzesmallportionsofaverylargedatasettoansweron-demandOurAutomaticallyinfersemanticallyentitiesbasedonOWL/SKOS

Output:aof

an

1Builda(Initializetraining

LabeledSomepropertiestousetogether

External

LearnUnresolved

Assumptions:(1)coreferententitiessharesimilarproperty-valuepairs;(2)afewproperty-valuepairsaremoreimportantforlinkingentitiesRunning

“Nanjing“32N“118E“Nanjing“Nan-ching”“Nanjing”“32N“118E“117W“32NSome Discriminabilityofaproperty Property Non-coreferententity intermsofcoreferent Discriminabilityofavalue Discriminabilityofaprop-value>100>100RDF>2Same-asIFPFP2 BillionTriplesChallenge(BTC) Testing Top-50in364thousandquery8Music/54323 Evaluationprocedureand 30graduates,2judges+1arbitrator/link,Fleiss’sκ=0.8(sufficient Precision&relativerecall RR=correctlinksinonesystem/totalcorrectuniquelinksinall umiteration= Discriminabilitythreshold= Linkage Runningtimeon5,000samples:avg.11.3linksin OntologyAlignmentEvaluation ISWCworkshopsincen Ontologymatching&instancematching提 IntroductiontoSemanticWebandknowledge PartI:ontology PartII:entity PartIII:anapplicationtodata Metadataisvitaltomultimediacontent Search,browsing,management Large-scaleLODarepublishedand Makeuseofsuchrichsourceof Existingmultimediametadatamodelsanddonotprovideformaltypicallyfocusonasinglemedia EXIF patiblewithMPEG- Differentmediatypesco-existinamultimedia Amoviemayhaveathememusicanda Aunified,well-definedontology(withits stoothers)neededtogain Challenge:LinkandintegrateheterogeneousAmotivingBeautyandthe Low-levelmetadata:runtime,location LOD:LinkedMDB,DBpedia Differentontologies(terms),different linkedmdb:filmlinkedmdb:directorlinkedmdb:11264 "BeautyandtheBeast"

andentitylinkageBeautyBeautyandtheruntime"91min." location

"BeautyandtheBeast" "...isa1991Americananimated

"BeautyandtheBeast"

Our CAMO:enrichmultimediametadataviaintegratingSelectDBpediaasthemediationandmatchwithLinkDBpediaentitieswithother andaggregatetheirIncorporatelegacyrelationaldatabases Moreover,provideamobileappforbrowsingandmultimediacontentonAndroid AssesstheadvantagesofintegratingLODintomultimediaSystemClient-ServerServer TheDBpedia3.6ontologyas Global-as-Viewsolutionof Music:DBpedia,DBTune, Movie:DBpedia,LinkedMDB,

Client Android-basedmobile Integratewithamultimedia Search&browsemultimediaSystemSearch,browseand

InstancemobileInstanceJohnrelationalEntityOntologyDataMatchingontologieswith DifferentLODsourceshavedifferentpreferenceson DBpedia,Musicontology Falcon-AO:anautomaticontologymatching Extend knowledgetosupportsynonym trackvs. StructuralStructural

4 Linguisticmatching:V-Doc(TF-IDF)&I-Sub(edit Structuralmatching:GMO(similarityLinkingentitieswith EntitylinkagehelpsmergealldescriptionsindifferentsourcesthattothesamemultimediaTrainingTraining

2

{p1,{p1,p3}ęc1vs.{p5,p6}ęc3{p1,p2}ęc1vs.{p3,p4}ęc2InstancelinkageĂ

Trainingset Negativeexamples:donotholdequivalencerelation Class-baseddiscriminativeproperty Information OnlineIntegratinglegacyrelational Therearestillagreatdealoflegacydatastoredin SomedatainLODaregeneratedfromtheirrelational123123 Element e.g.,entitytableandrelationship Element Instance

similartoontologymatchingandentitylinkage TwoUsabilityandeffectivenessofthemobileIntegrationaccuracyinthe User(1)Usability& 3comparative : : :WikipediaAndroid 6testing 50 10 22 18Usability& SystemUsabilityScale(SUS)&post-task

Post-task yzetheresultaccordingtothetypologyoftheIntegrationOntology 78 incl.18RDB

Entity 60thousand 100samplesper10110Lessons CAMOleveragesontologymatchingandentitylinkagefordataintegrationandsupportsuserstobrowseandsearchmultimediacontentonmobiledevices LessonsOntologymatters:trade-offbetweenexpressivenessandeaseofDataintegrationquality:humancomputation+machineMobileappdesign:conciseness,rankingscheme,user- FutureGeneratecomplex sforsemanticqueryExtendtouser-generatedNLP提 IntroductiontoSemanticWebandknowledge PartI:ontology PartII:entity PartIII:anapplicati