{'fraction_non_alphanumeric': 0.039018058259840414, 'fraction_numerical': 0.013056923605543466, 'mean_word_length': 4.753129804524489, 'pattern_counts': {'":': 1, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Wisdom of Minority: Unsupervised Slot Filling Validation based on Multi-dimensional Truth-Finding

Information Extraction using multiple information sources and systems is beneficial due to multisource/system consolidation and challenging due to the resulting inconsistency and redundancy. We integrate IE and truth-finding research and present a novel unsupervised multi-dimensional truth finding framework which incorporates signals from multiple sources, multiple systems and multiple pieces of evidence by knowledge graph construction through multi-layer deep linguistic analysis. Experiments on the case study of Slot Filling Validation demonstrate that our approach can find truths accurately (9.4% higher F-score than supervised methods) and efficiently (finding 90% truths with only one half the cost of a baseline without credibility estimation).


Introduction
Traditional Information Extraction (IE) techniques assess the ability to extract information from individual documents in isolation. However, similar, complementary or conflicting information may exist in multiple heterogeneous sources. We take the Slot Filling Validation (SFV) task of the NIST Text Analysis Conference Knowledge Base Population (TAC-KBP) track  as a case study. The Slot Filling (SF) task aims at collecting from a large-scale multi-source corpus the values ("slot fillers") for certain attributes ("slot types") of a query entity, which is a person or some type of organization. KBP 2013 has defined 25 slot types for persons (per) (e.g., age, spouse, employing organization) and 16 slot types for organizations (org) (e.g., founder, headquarters-location, and subsidiaries). Some slot types take only a single slot filler (e.g., per:birthplace), whereas others take multiple slot fillers (e.g., org:top employees).
We call a combination of query entity, slot type, and slot filler a claim. Along with each claim, each system must provide the ID of a source document and one or more detailed context sentences as evidence which supports the claim. A response (i.e., a claim, evidence pair) is correct if and only if the claim is true and the evidence supports it.
Given the responses produced by multiple systems from multiple sources in the SF task, the goal of the SFV task is to determine whether each response is true or false. Though it's a promising line of research, it raises two complications: (1) different information sources may generate claims that vary This work is licenced under a Creative Commons Attribution 4.0 International License. Page numbers and proceedings footer are added by the organizers. License details: http://creativecommons.org/licenses/by/4.0/ in trustability; and (2) a large-scale number of SF systems using different resources and algorithms may generate erroneous, conflicting, redundant, complementary, ambiguously worded, or inter-dependent claims from the same set of documents. Table 1 presents responses from four SF systems for the query entity Ronnie James Dio and the slot type per:city of death. Systems A, B and D return Los Angeles with different pieces of evidence 1 extracted from different information sources, though the evidence of System D does not decisively support the claim. System C returns Atlantic City, which is neither true nor supported by the corresponding evidence.
Such complications call for "truth finding": determining the veracity of multiple conflicting claims from various sources and systems. We propose a novel unsupervised multi-dimensional truth finding framework to study credibility perceptions in rich and wide contexts. It incorporates signals from multiple sources and systems, using linguistic indicators derived from knowledge graphs constructed from multiple evidences using multi-layer deep linguistic analysis. Experiments demonstrate that our approach can find truths accurately (9.4% higher F-score than supervised methods) and efficiently (find 90% truths with only one half cost of a baseline without credibility estimation).

Related Work & Our Novel Contributions
Most previous SFV work (e.g., (Tamang and Ji, 2011;Li and Grishman, 2013)) focused on filtering incorrect claims from multiple systems by simple heuristic rules, weighted voting, or costly supervised learning to rank algorithms. We are the first to introduce the truth finding concept to this task. The "truth finding" problem has been studied in the data mining and database communities (e.g., (Yin et al., 2008;Dong et al., 2009a;Dong et al., 2009b;Galland et al., 2010;Blanco et al., 2010;Pasternack and Roth, 2010;Yin and Tan, 2011;Pasternack and Roth, 2011;Vydiswaran et al., 2011;Ge et al., 2012;Zhao et al., 2012;Wang et al., 2012;Pasternack and Roth, 2013)). Compared with the previous work, our truth finding problem is defined under a unique setting: each response consists of a claim and supporting evidence, automatically generated from unstructured natural language texts by a SF system. The judgement of a response concerns both the truth of the claim and whether the evidence supports the claim. This has never been modeled before. We mine and exploit rich linguistic knowledge from multiple lexical, syntactic and semantic levels from evidence sentences for truth finding. In addition, previous truth finding work assumed most claims are likely to be true. However, most SF systems have hit a performance ceiling of 35% F-measure, and false responses constitute the majority class (72.02%) due to the imperfect algorithms as well as the inconsistencies of information sources. Furthermore, certain truths might only be discovered by a minority of good systems or from a few good sources. For example, 62% of the true responses are produced only by 1 or 2 of the 18 SF systems.

MTM Construction
A response is trustworthy if its claim is true and its evidence supports the claim. A trusted source always supports true claims by giving convincing evidence, and a good system tends to extract trustworthy responses from trusted sources. We propose a multi-dimensional truth-finding model (MTM) to incorporate and compute multi-dimensional credibility scores.
Consider a set of responses R = {r 1 , . . . , r m } extracted from a set of sources S = {s 1 , . . . , s n } and provided by a set of systems T = {t 1 , . . . , t l }. A heterogeneous network is constructed as shown in Fig. 1. Let weight matrices be W rs m×n = {w rs ij } and W rt m×l = {w rt ik }. A link w rs ij = 1 is generated between r i and s j when response r i is extracted from source s j , and a link w rt ik = 1 is generated between r i and t k when response r i is provided by system t k .

Credibility Initialization
Each source is represented as a combination of publication venue and genre. The credibility scores of sources S are initialized uniformly as 1 n , where n is the number of sources. Given the set of systems T = {t 1 , . . . , t l }, we initialize their credibility scores c 0 (t) based on their interactions on the predicted responses. Suppose each system t i generates a set of responses R t i . The similarity between two systems t i and t j is defined as similarity(t i , t j ) = |Rt i ∩Rt j | log (|Rt i |)+log (|Rt j |) (Mihalcea, 2004). Then we construct a weighted undirected graph G = T, E , where T (G) = {t 1 , . . . , t l } and E(G) = { t i , t j }, t i , t j = similarity(t i , t j ), and apply the TextRank algorithm (Mihalcea, 2004) on G to obtain c 0 (t).
We got negative results by initializing system credibility scores uniformly. We also got negative results by initializing system credibility scores using system metadata, such as the algorithms and resources the system used at each step, its previous performance in benchmark tests, and the confidence values it produced for its responses. We found the quality of an SF system depends on many different resources instead of any dominant one. For example, an SF system using a better dependency parser does not necessarily produce more truths. In addition, many systems are actively being improved, rendering previous benchmark results unreliable. Furthermore, most SF systems still lack reliable confidence estimation.
The initialization of the credibility scores for responses relies on deep linguistic analysis of the evidence sentences and the exploitation of semantic clues, which will be described in Section 4.

Credibility Propagation
We explore the following heuristics in MTM.
HEURISTIC 1: A response is more likely to be true if derived from many trustworthy sources. A source is more likely to be trustworthy if many responses derived from it are true.
HEURISTIC 2: A response is more likely to be true if it is extracted by many trustworthy systems. A system is more likely to be trustworthy if many responses generated by it are true.
Based on these two heuristics we design the following credibility propagation approach to mutually reinforce the trustworthiness of linked objects in MTM.
By extension of Co-HITS (Deng et al., 2009), designed for bipartite graphs, we develop a propagation method to handle heterogeneous networks with three types of objects: source, response and system. Let the weight matrices be W rs (between responses and sources) and W rt (between responses and systems), and their transposes be W sr and W tr . We can obtain the transition probability that vertex s i in S reaches vertex r j in R at the next iteration, which can be formally defined as a normalized weight p sr ij = w sr ij k w sr ik such that r j ∈R p sr ij = 1. We compute the transition probabilities p rs ji , p rt jk and p tr kj in an analogous fashion.
Given the initial credibility scores c 0 (r), c 0 (s) and c 0 (t), we aim to obtain the refined credibility scores c(r), c(s) and c(t) for responses, sources, and systems, respectively. Starting with sources, the update process considers both the initial score c 0 (s) and the propagation from connected responses, which we formulated as: Similarly, the propagation from responses to systems is formulated as: Each response's score c(r j ) is influenced by both linked sources and systems: where λ rs , λ rt , λ sr and λ tr ∈ [0, 1]. These parameters control the preference for the propagated over initial score for every type of random walk link. The larger they are, the more we rely on link structure 2 . The propagation algorithm converges (10 iterations in our experimental settings) and a similar theoretical proof to HITS (Peserico and Pretto, 2009) can be constructed. Algorithm 1 summarizes MTM.

Response Credibility Initialization
Each evidence along with a claim is expressed as a few natural language sentences that include the query entity and the slot filler, along with semantic content to support the claim. We analyze the evidence of each response in order to initialize that response's credibility score. This is done using heuristic rules defined in terms of the binary outputs of various linguistic indicators (Section 4.1).

Linguistic Indicators
We encode linguistic indicators based on deep linguistic knowledge acquisition and use them to determine whether responses provide supporting clues or carry negative indications (Section 4.3). These indicators make use of linguistic features on varying levels -surface form, sentential syntax, semantics, and pragmatics -and are defined in terms of knowledge graphs (Section 4.2). We define a heuristic rule for each slot type in terms of the binary-valued linguistic indicator outputs to yield a single binary value (1 or 0) for each response. If a response's linguistic indicator value is 1, the credibility score of a response is initialized at 1.0, and 0.5 otherwise.
Input: A set of responses (R), sources (S) and systems (T ). Output: Credibility scores (c(r)) for R.

Knowledge Graph Construction
A semantically rich knowledge graph is constructed that links a query entity, all of its relevant slot filler nodes, and nodes for other intermediate elements excerpted from evidence sentences. There is one knowledge graph per sentence. Fig. 2  Formally, a knowledge graph is an annotated graph of entity mentions, phrases and their links. It must contain one query entity node and one or more slot filler nodes. The annotation of a node includes its entity type, subtype, mention type, referent entities, and semantic category (though not every node has each type of annotation). The annotation of a link includes a dependency label and/or a semantic relation between the two linked nodes.
The knowledge graph is constructed using the following procedure. First, we annotate the evidence text using dependency parsing (Marneffe et al., 2006) and Information Extraction (entity, relation and event) Li and Ji, 2014). Two nodes are linked if they are deemed related by one of the annotation methods (e.g., [Mays,50] is labeled with the dependency type amod, and [home, Tampa] is labeled with the semantic relation located in). The annotation output is often in terms of syntactic heads. Thus, we extend the boundaries of entity, time, and value mentions (e.g., people's titles) to include an entire phrase where possible. We then enrich each node with annotation for entity type, subtype and mention type. Entity type and subtype refer to the role played by the entity in the world, the latter being more fine-grained, whereas mention type is syntactic in nature (it may be pronoun, nominal, or proper name). For example, "Tampa" in Fig. 2 is annotated as a Geopolitical (entity type) Population-Center (subtype) Name (mention type) mention. Every time expression node is annotated with its normalized reference date (e.g., "June, 28" in Fig. 2 is normalized as "06/28/2009").
Second, we perform co-reference resolution, which introduces implicit links between nodes that refer to the same entity. Thus, an entity mention that is a nominal or pronoun will often be co-referentially linked to a mention of a proper name. This is important because many queries and slot fillers are expressed only as nominal mentions or pronouns in evidence sentences, their canonical form appearing elsewhere in the document.
Finally, we address the fact that a given relation type may be expressed in a variety of ways. For example, "the face of " indicates the membership relation in the following sentence: "Jennifer Dunn was the face of the Washington state Republican Party for more than two decades." We mined a large number of trigger phrases for each slot type by mapping various knowledge bases, including Wikipedia Infoboxes, Freebase (Bollacker et al., 2008), DBPedia (Auer et al., 2007) and YAGO (Suchanek et al., 2007), into the Gigaword corpus 3 and Wikipedia articles via distant supervision (Mintz et al., 2009) 4 . Each intermediate node in the knowledge graph that matches a trigger phrase is then assigned a corresponding semantic category. For example, "died" in Fig. 2 is labeled a Death-Trigger.

Knowledge Graph-Based Verification
We design linguistic indicators in terms of the properties of nodes and paths that are likely to be bear on the response's veracity. Formally, a path consists of the list of nodes and links that must be traversed along a route from a query node to a slot filler node. Node indicators contribute information about a query entity or slot filler node in isolation, that may bear on the trustworthiness of the containing evidence sentence. For instance, a slot filler for the per:date of birth slot type must be a time expression.

Node Indicators
1. Surface: Whether the slot filler includes stop words; whether it is lower cased but appears in news.
These serve as negative indicators.
2. Entity type, subtype and mention type: For example, the slot fillers for "org:top employees" must be person names; and fillers for "org:website" must match the url format. Besides the entity extraction system, we also exploited the entity attributes mined by the NELL system (Carlson et al., 2010) from the KBP source corpus.
Each path contains syntactic and/or semantic relational information that may shed light on the manner in which the query entity and slot filler are related, based on dependency parser output, IE output, and trigger phrase labeling. Path indicators are used to define properties of the context in which which query-entity and slot-filler are related in an evidence sentence. For example, whether the path associated with a claim about an organization's top employee includes a title commonly associated with decision-making power can be roughly represented using the trigger phrases indicator.

Path Indicators
1. Trigger phrases: Whether the path includes any trigger phrases as described in Section 4.2.
2. Relations and events: Whether the path includes semantic relations or events indicative of the slot type. For example, a "Start-Position" event indicates a person becomes a "member" or "employee" of an organization.
3. Path length: Usually the length of the dependency path connecting a query node and a slot filler node is within a certain range for a given slot type. For example, the path for "per:title" is usually no longer than 1. A long dependency path between the query entity and slot filler indicates a lack of a relationship. In the following evidence sentence, which does not entail the "per:religion" relation between "His" and the religion "Muslim", there is a long path ("his-poss-moment-nsubjcame-advcl-seized-militant-acmod-Muslim"): "His most noticeable moment in the public eye came in 1979, when Muslim militants in Iran seized the U.S. Embassy and took the Americans stationed there hostage.".
Detecting and making use of interdependencies among various claims is another unique challenge in SFV. After initial response credibility scores are calculated by combining linguistic indicator values, we identify responses that have potentially conflicting or potentially supporting slot-filler candidates. For such responses, their credibility scores are changed in accordance with the binary values returned by the following indicators.

Interdependent Claims Indicators
1. Conflicting slot fillers: When fillers for two claims with the same query entity and slot type appear in the same evidence sentence, we apply an additional heuristic rule designed for the slot type in question. For example, the following evidence sentence indicates that compared to "Cathleen P. Black", "Susan K. Reed" is more likely to be in a "org:top employees/members" relation with "The Oprah Magazine" due to the latter pair's shorter dependency path: "Hearst Magazine's President Cathleen P. Black has appointed Susan K. Reed as editor-in-chief of the U.S. edition of The Oprah Magazine.". The credibility scores are accordingly changed (or kept at) 0.5 for responses associated with the former claim, and 1.0 for those associated with the latter.
2. Inter-dependent slot types: Many slot types are inter-dependent, such as "per:title" and "per:employee of ", and various family slots. After determining initial credibility scores for each response, we check whether evidence exists for any implied claims. For example, given initial credibility scores of 1.0 for two responses supporting the claims that (1)"David" is "per:children" of "Carolyn Goodman" and (2)"Andrew" is "per:sibling" of "David", we check for any responses supporting the claim that (3)"Andrew" is "per:children" of "Carolyn Goodman", and set their credibility scores to 1.0. For example, a response supporting this claim included the evidence sentence, "Dr. Carolyn Goodman, her husband, Robert, and their son, David, said goodbye to David's brother, Andrew.".

Experimental Results
This section presents the experiment results and analysis of our approach.

Data
The data set we use is from the TAC-KBP2013 Slot Filling Validation (SFV) task, which consists of the merged responses returned by 52 runs (regarded as systems in MTM) from 18 teams submitted to the Slot  Filling (SF) task. The source collection has 1,000,257 newswire documents, 999,999 web documents and 99,063 discussion forum posts, which results in 10 different sources (combinations of publication venues and genres) in our experiment. There are 100 queries: 50 person and 50 organization entities. After removing redundant responses within each single system run, we use 45,950 unique responses as the input to truth-finding. Linguistic Data Consortium (LDC) human annotators manually assessed all of these responses and produced 12,844 unique responses as ground truth. In order to compare with state-of-the-art supervised learning methods for SFV (Tamang and Ji, 2011;Li and Grishman, 2013), we trained a SVMs classifier 5 as a counterpart, incorporating the same set of linguistic indicators, sources and systems as features. We picked 10% (every 10th line) to compose the development set for MTM and the training set for the SVMs. The rest is used for blind test. Table 2 shows the overall performance of various truth finding methods on judging each response as true or false. MTM achieves promising results and even outperforms supervised learning approach. Table 3 presents some examples ranked at the top and the bottom based on the credibility scores produced by MTM.

Overall Performance
We can see that majority voting across systems performs much better than random assessment, but its accuracy is still low. For example, the true claim T5 was extracted by only one system because most systems mistakenly identified "Briton Stuart Rose" as a person name. In comparison, MTM obtained much better accuracy by also incorporating multiple dimensions of source and evidence information.
Method 3 using linguistic indicators alone, already achieved promising results. For example, many claims are judged as truths through trigger phrases (T1 and T5), event extraction (T2), coreference (T4), and node type indicators (T3). On the other hand, many claims are correctly judged as false because their evidence sentences did not include the slot filler (F1, F4, F5) or valid knowledge paths to connect the query entity and the slot filler (F2, F3). The performance gain (2.99% F-score) from Method 3 to Method 5 shows the need for incorporating system and source dimensions. For example, most truths are from news while many false claims are from newsgroups and discussion forum posts (F1, F2, F5).
The SVMs model got very low recall because of the following two reasons: (1) It ignored the interdependency between multiple dimensions; (2) the negative instances are dominant in the training data, so the model is biased towards labeling responses as false. Table 3 shows that some truths (T1) are produced from low-ranked systems whereas some false responses from high-ranked systems (F1, F2). Note that systems are ranked by their performance in KBP SF task. In order to find all the truths, human assessors need to go through all the responses returned by multiple systems. This process was proven very tedious and costly (Ji et al., 2010;Tamang and Ji, 2011).

Truth Finding Efficiency
Our MTM approach can expedite this process by ranking responses based on their credibility scores and asking human to assess the responses with high credibility first. Traditionally, when human assess responses, they follow an alphabetical order or system IDs in a "passive learning" style. This is set as our baseline. For comparison, we also present the results using only linguistic indicators, using voting in which the responses which get more votes across systems are assessed first, and the oracle method assessing all correct responses first.   Fig. 3 summarizes the results from the above 6 approaches. The common end point of all curves represents the cost and benefit of assessing all system responses. We can see that the baseline is very inefficient at finding the truths. If we employ linguistic indicators, the process can be dramatically expedited. MTM provides further significant gains, with performance close to the Oracle. With only half the cost of the baseline, MTM can already find 90% truths.

Enhance Individual SF Systems
Finally, as a by-product, our MTM approach can also be exploited to validate the responses from each individual SF system based on their credibility scores. For fair comparison with the official KBP evaluation, we use the same ground-truth in KBP2013 and standard precision, recall and F-measure metrics as defined in . To increase the chance of including truths which may be particularly difficult for a system to find, LDC prepared a manual key which was assessed and included in the final ground truth. According to the SF evaluation setting, F-measure is computed based on the number of unique true claims. After removing redundancy across multiple systems, there are 1,468 unique true claims. The cutoff criteria for determining whether a response is true or not was optimized from the development set. Fig. 4 presents the F-measure scores of the best run from each individual SF system. We can see that our MTM approach consistently improves the performance of almost all SF systems, in an absolute gain range of [-1.22%, 5.70%]. It promotes state-of-the-art SF performance from 33.51% to 35.70%. Our MTM approach provides more gains to SF systems which mainly rely on lexical or syntactic patterns than other systems using distant supervision or logic rules.

Conclusions and Future Work
Truth finding has received attention from both Natural Language Processing (NLP) and Data Mining communities. NLP work has mostly explored linguistic analysis of the content, while Data Mining work proposed advanced models in resolving conflict information from multiple sources. They have relative strengths and weaknesses. In this paper we leverage the strengths of these two distinct, but complementary research paradigms and propose a novel unsupervised multi-dimensional truthfinding framework incorporating signals both from multiple sources, multiple systems and multiple evidences based on knowledge graph construction with multi-layer linguistic analysis. Experiments on a challenging SFV task demonstrated that this framework can find high-quality truths efficiently. In the future we will focus on exploring more inter-dependencies among responses such as temporal and causal relations.