1、知识图谱需要的技术知识图谱架构知识图谱一般架构:来源自百度百科复旦大学知识图谱架构:早期知识图谱架构知识图谱一般架构:来源自百度百科架构讨论数据检索预处理构建关系矩阵网络图谱参数调整可视化数据规范化处理结果导读早期知识图谱架构知识抽取实体概念抽取实体概念映射关系抽取质量评估KDD 2014 Tutorial on Constructing and Mining Web-scale Knowledge Graphs, New York, August 24, 2014A sampler of research problemsGrowth: knowledge graphs are incomp
2、lete!Link prediction: add relationsOntology matching: connect graphsKnowledge extraction: extract new entities and relations from web/textValidation: knowledge graphs are not always correct!Entity resolution: merge duplicate entities, split wrongly merged onesError detection: remove false assertions
3、Interface: how to make it easier to access knowledge?Semantic parsing: interpret the meaning of queriesQuestion answering: compute answers using the knowledge graphIntelligence: can AI emerge from knowledge graphs?Automatic reasoning and planningGeneralization and abstraction9关系抽取定义:常见手段:语义模式匹配频繁模式抽
4、取,基于密度聚类,基于语义相似性层次主题模型弱监督KDD 2014 Tutorial on Constructing and Mining Web-scale Knowledge Graphs, New York, August 24, 2014Methods and techniquesSupervised modelsSemi-supervised modelsDistant supervision2. Entity resolutionSingle entity methodsRelational methods3. Link predictionRule-based methodsPr
5、obabilistic modelsFactorization methodsEmbedding models80Not in this tutorial: Entity classification Group/expert detection Ontology alignment Object ranking1. Relation extraction:KDD 2014 Tutorial on Constructing and Mining Web-scale Knowledge Graphs, New York, August 24, 2014 Extracting semantic r
6、elations between sets of grounded entitiesNumerous variants:Undefined vs pre-determined set of relationsBinary vs n-ary relations, facet discoveryExtracting temporal informationSupervision: fully, un, semi, distant-supervisionCues used: only lexical vs full linguistic features82Relation ExtractionKo
7、beBryantLA LakersplayForthe franchise player ofonce again savedman of the match forthe Lakers”his team”Los Angeles”“Kobe Bryant,“Kobe“Kobe Bryant?KDD 2014 Tutorial on Constructing and Mining Web-scale Knowledge Graphs, New York, August 24, 2014Supervised relation extractionSentence-level labels of r
8、elation mentionsApple CEO Steve Jobs said. = (SteveJobs, CEO, Apple)Steve Jobs said that Apple will. = NILTraditional relation extraction datasetsACE 2004MUC-7Biomedical datasets (e.g BioNLP clallenges)Learn classifiers from +/- examplesTypical features: context words + POS, dependency path betweene
9、ntities, named entity tags, token/parse-path/entity distance83KDD 2014 Tutorial on Constructing and Mining Web-scale Knowledge Graphs, New York, August 24, 2014Semi-supervised relation extractionGeneric algorithm(遗传算法遗传算法)1.2.3.4.5.Start with seed triples / golden seed patternsExtract patterns that
10、match seed triples/patternsTake the top-k extracted patterns/triplesAdd to seed patterns/triplesGo to 2Many published approaches in this category:Dual Iterative Pattern Relation Extractor Brin, 98Snowball Agichtein & Gravano, 00TextRunner Banko et al., 07 almost unsupervisedDiffer in pattern definit
11、ion and selection86founderOfKDD 2014 Tutorial on Constructing and Mining Web-scale Knowledge Graphs, New York, August 24, 2014Distantly-supervised relation extraction88Existing knowledge base + unlabeled text generate examplesLocate pairs of related entities in textHypothesizes that the relation is
12、expressedGoogle CEO Larry Page announced that.Steve Jobs has been Apple for a while.Pixar lost its co-founder Steve Jobs.I went to Paris, France for the summer.GoogleCEOcapitalOfLarryPageFranceAppleCEOPixarSteveJobsDistant supervision: modeling hypothesesTypical architecture:1. Collect many pairs of
13、 entities co-occurring in sentences from text corpus2. If 2 entities participate in a relation, several hypotheses:1.All sentences mentioning them express it Mintz et al., 09“Barack Obama is the 44th and current President of the US.” (BO, employedBy, USA)89KDD 2014 Tutorial on Constructing and Minin
14、g Web-scale Knowledge Graphs, New York, August 24, 2014KDD 2014 Tutorial on Constructing and Mining Web-scale Knowledge Graphs, New York, August 24, 2014Sentence-level featuresLexical: words in between and around mentions and their parts-of-speech tags (conjunctive form)Syntactic: dependency parse p
15、ath between mentions along withside nodesNamed Entity Tags: for the mentionsConjunctions of the above featuresDistant supervision is used on to lots of data sparsity of conjunctiveforms not an issue92Distant supervision: modeling hypothesesTypical architecture:1. Collect many pairs of entities co-oc
16、curring in sentences from text corpus2. If 2 entities participate in a relation, several hypotheses:1.2.All sentences mentioning them express it Mintz et al., 09At least one sentence mentioning them express it Riedel et al., 10“Barack Obama is the 44th and current President of the US.” (BO, employed
17、By, USA)“Obama flew back to the US on Wednesday.” (BO, employedBy, USA)95KDD 2014 Tutorial on Constructing and Mining Web-scale Knowledge Graphs, New York, August 24, 2014Distant supervision: modeling hypothesesTypical architecture:1. Collect many pairs of entities co-occurring in sentences from tex
18、t corpus2. If 2 entities participate in a relation, several hypotheses:1.2.3.All sentences mentioning them express it Mintz et al., 09At least one sentence mentioning them express it Riedel et al., 10At least one sentence mentioning them express it and 2 entities can expressmultiple relations Hoffma
19、nn et al., 11 Surdeanu et al., 12“Barack Obama is the 44th and current President of the US.” (BO, employedBy, USA)“Obama flew back tothe US justWednesday.” said.” employedBy, USA)98KDD 2014 Tutorial on Constructing and Mining Web-scale Knowledge Graphs, New York, August 24, 2014was born in on he alw
20、ays (BO, (BO, bornIn,KDD 2014 Tutorial on Constructing and Mining Web-scale Knowledge Graphs, New York, August 24, 2014Distant supervisionProsCan scale to the web, as no supervision requiredGeneralizes to text from different domainsGenerates a lot more supervision in one iterationConsNeeds high qual
21、ity entity-matchingRelation-expression hypothesis can be wrongCan be compensated by the extraction model, redundancy, language modelDoes not generate negative examplesPartially tackled by matching unrelated entities101KDD 2014 Tutorial on Constructing and Mining Web-scale Knowledge Graphs, New York,
22、 August 24, 2014104KobeBryantGasolteammatebornInplayInLeagueBlackMambaEntity resolutionLA LakersplayForplayForPau35ageKobe B.BryantVanessaL. BryantmarriedTo1978Single entityresolutionRelational entityresolutionEntity resolution / deduplication Multiple mentions of the same entity is wrong and confus
23、ing.KDD 2014 Tutorial on Constructing and Mining Web-scale Knowledge Graphs, New York, August 24, 2014Single-entity entity resolutionEntity resolution without using the relational context of entitiesMany distances/similarities for single-entity entity resolution:Edit distance (Levenshtein, etc.)Set
24、similarity (TF-IDF, etc.)Alignment-basedNumeric distance between valuesPhonetic SimilarityEquality on a boolean predicateTranslation-basedDomain-specific105KDD 2014 Tutorial on Constructing and Mining Web-scale Knowledge Graphs, New York, August 24, 2014Relational entity resolution Simple strategies
25、 Enrich model with relational features richer context for matchingRelational features:Value of edge or neighboring attributeSet similarity measuresOverlap/JaccardAverage similarity between set membersAdamic/Adar: two entities are more similar if they share more items that areoverall less frequentSim
26、Rank: two entities are similar if they are related to similar objectsKatz score: two entities are similar if they are connected by shorter paths114KobeBryant1978teammatebornInplayForplayInLeagueBlackMambaLA LakersplayFor35agePauGasolKDD 2014 Tutorial on Constructing and Mining Web-scale Knowledge Gr
27、aphs, New York, August 24, 2014KobeBryant1978teammatebornInplayForplayInLeagueBlackMambaLA LakersplayFor35agePauGasolRelational entity resolution Advanced strategiesDependency graph approaches Dong et al., 05Relational clustering Bhattacharya & Getoor, 07Probabilistic Relational Models Pasula et al.
28、, 03Markov Logic Networks Singla & Domingos, 06Probabilistic Soft Logic Broecheler & Getoor, 10115KDD 2014 Tutorial on Constructing and Mining Web-scale Knowledge Graphs, New York, August 24, 2014LINK PREDICTION116KDD 2014 Tutorial on Constructing and Mining Web-scale Knowledge Graphs, New York, Aug
29、ust 24, 2014117KobeBryantLink predictionNY KnicksPauGasolteammateplayInLeagueteamInLeagueopponentplayForLA LakersplayFor Add knowledge from existing graph No external source Reasoning within the graph1. Rule-based methods2. Probabilistic models3. Factorization models4. Embedding modelsKDD 2014 Tutor
30、ial on Constructing and Mining Web-scale Knowledge Graphs, New York, August 24, 2014First Order Inductive Learner FOIL learns function-free Horn clauses:118Gasolgiven positive negative examples of a concepta set of background-knowledge predicatesFOIL inductively generates a logical rule for the conc
31、ept that cover all + and no -LALakersplayForplayForPauteammate(x,y) playFor(y,z) playFor(x,z)teammateKobeBryant Computationally expensive: huge search space large, costly Horn clauses Must add constraints high precision but low recall Inductive Logic Programming: deterministic and potentially proble
32、maticKDD 2014 Tutorial on Constructing and Mining Web-scale Knowledge Graphs, New York, August 24, 2014S(KB, playFor,LAL)iplayForh(pai(KB,LAL)ipathsPath Ranking Algorithm Lao et al., 11119LALakersplayForPauGasolplayForteammateKobeBryantRandom walks on the graph are used to sample pathsPaths are weig
33、hted with probability of reaching target from sourcePaths are used as ranking experts in a scoring functionNYKnicksplayInLeagueteamInLeagueopponenth(Pa2(KB,LAL) = 0.2h(Pa1(KB,LAL) = 0.95KDD 2014 Tutorial on Constructing and Mining Web-scale Knowledge Graphs, New York, August 24, 2014Link prediction
34、with scoring functionsA scoring function alone does not grant a decisionThresholding: determine a threshold (KB, playFor, LAL) is True iff120S(KB, playFor,LAL)Ranking: The most likely relation between Kobe Bryant and LA Lakers is:rel argmaxrrelsS(KB,r,LAL) The most likely team for Kobe Bryant is:obj argmaxeentsS(KB, playFor,e)As prior for extraction models (cf. Knowledge Vault)No calibration of scores like probabilities
