Knowledge bases, massive collections of facts (RDF triples) on diverse topics, support vital modern applications. However, existing knowledge bases contain very little data compared to the wealth of information on the Web. This is because the industry standard in knowledge base creation and augmentation suffers from a serious bottleneck: they rely on domain experts to identify appropriate web sources to extract data from. Efforts to fully automate knowledge extraction have failed to improve this standard: these automated systems are able to retrieve much more data and from a broader range of sources, but they suffer from very low precision and recall. As a result, these large-scale extractions remain unexploited. In this paper, we present MIDAS, a system that harnesses the results of automated knowledge extraction pipelines to repair the bottleneck in industrial knowledge creation and augmentation processes. MIDAS automates the suggestion of good-quality web sources and describes what to extract with respect to augmenting an existing knowledge base. We make three major contributions. First, we introduce a novel concept, web source slices, to describe the contents of a web source. Second, we define a profit function to quantify the value of a web source slice with respect to augmenting an existing knowledge base. Third, we develop effective and highly-scalable algorithms to derive high-profit web source slices. We demonstrate that MIDAS produces high-profit results and outperforms the baselines significantly on both real-word and synthetic datasets. Knowledge bases support a wide range of applications and enhance search results for multiple major search engines, such as Google and Bing BID1 .The coverage and correctness of knowledge bases are crucial for the applications that use them, and for the quality of the user experience. However , there exists a gap between facts on the Web and in knowledge bases: compared to the wealth of information on the Web, most knowledge bases are largely incomplete, with many facts missing. For example , one of the largest knowledge bases, Freebase BID7 BID0 , does not provide sufficient facts for different types of cocktails such as the ingredients of Margarita. Yet, such information is explicitly profiled and described by many web sources, such as Wikipedia. Figure 1 : Two knowledge extraction procedures and Midas. The output of the automated process (b) is often discarded in industrial production due to low accuracy. Midas uses the the automatically-extracted facts to identify the right web sources for the semi-automated process under the industry standard and therefore resolves a major bottleneck.Industry standard. Industry typically follows a semi-automated knowledge extraction process to create or augment a knowledge base with facts that are new to an existing knowledge base (or new facts) from the Web. This process ( Figure 1a ) first relies on domain experts to select web sources; it then uses crowdsourcing to annotate a fraction of entities and facts and treats them as the training data; finally, it applies wrapper induction BID19 BID21 and learns Xpath patterns to extract facts from the selected web sources. Since source selection and training data preparation are carefully curated, this process achieves high precision and recall with respect to each selected web source. However, it can only produce a small volume of facts overall and cannot scale, as the source-selection step is a severe bottleneck, relying on manual curation by domain experts.Automated process. To conquer the scalability limitation in the industry standard, automated knowledge extraction BID13 BID30 attempts to extract facts with little or no human intervention. Instead of manually selecting a small set of web sources, automated extraction (Figure 1b) often takes a wide variety of web sources, e.g., ClueWeb09 BID10 , as input and uses facts in an existing knowledge base, or a small portion of labeled input web sources, as training data. This automated extraction process is able to produce a vast number of facts. However, because of the limited training data (per source), especially for uncommon facts, e.g., the ingredients of Margarita, this process suffers from low accuracy. The TAC-KBP competition showed that automated processes BID33 BID3 BID34 BID12 can hardly achieve above 0.3 recall, leaving a lot of the wealth of web information unexploited. Due to this limitation, such automatically extracted facts are often abandoned for knowledge bases in industrial production.In this paper, we propose Midas 1 , a system that harnesses the correct 2 extractions of the automated process to automatically identify suitable web sources and repair the bottleneck in the industry standard. The core insight of Midas is that the automatically extracted facts, even though they may not be of high overall accuracy and coverage, give clues about which web sources contain a large amount of valuable information, allow for easy annotation, and are worthwhile for extraction. We demonstrate this through an example.1. Our system is named after King Midas, known in Greek mythology for his ability to turn what he touched into gold. 2. We refer to correct facts as facts with confidence value ≥ 0.7 as true. Example 1. FIG1 shows a snapshot of high-confidence facts (subject , predicate, object) extracted from 5 web pages under web domain http://space.skyrocket.de. Automated extraction systems may not be able to obtain high precision and recall in extracting facts from this website due to lack of effective training data. However, the few correct extracted facts give important clues on what one could extract from this site. For each fact, the subject indicates an entity; the predicate and object values further describe properties associated with the entity. For example, fact t 1 specifies that the category property of the entity Project Mercury is space program. Entities can form groups based on their common properties. For example, entity "Project Mercury" and entity "Project Gemini " are both "space programs that are sponsored by NASA".The facts labeled "Y" in the "new?" column are absent from Freebase . All of these new facts are under the same sub-domain and are all " rocket families sponsored by the NASA." This observation provides a critical insight: one can augment Freebase by extracting facts pertaining to "rocket families sponsored by NASA" from http://space.skyrocket.de/doc_lau_fam.Example 1 shows that one can abstract the contents of a web source through extracted facts: A web source often includes facts of multiple groups of homogeneous entities. Each group of entities forms a particular subset of content in the web source, which we call a web source slice (or slice). The common properties shared by the group of entities not only define, but also describe the slice of facts. For example, it is easy to tell that a slice describes "rocket families sponsored by NASA" through its common properties, "category = rocket family" and "sponsor = NASA". Moreover, entities in a single web source slice often belong to the same type, e.g., "rocket families sponsored by NASA", and thus share similar predicates. The limited number of predicates in a web source slice simplifies annotation . Our objective is to discover web source slices that (1) contain a sufficient number of facts that are absent from the knowledge base we wish to augment, and (2) their extraction effort does not outweigh the benefit.However, evaluating and quantifying the suitability of a web source slice with respect to these two desired properties is not straightforward. In addition, the number of slices in a single web source often grows exponentially with the number of facts, posing a significant scalability challenge. This challenge is amplified by the massive number of sources on the Web, in various genres, languages, and domains. Even a single web domain Midas derived slides using facts extracted from a real-world , large-scale, automated knowledge extraction pipeline (name hidden for anonymity) that operates on billions of web pages. New facts refer to extracted facts that are absent from Freebase.may contain an extensive amount of knowledge. For example, as of July 2018, there are more than 45 million entries in Wikipedia [3] .Midas addresses these challenges through (1) efficient and scalable algorithms for producing web source slices, and (2) an effective profit function for measuring the utility of slices. In this paper, we first formalize the problem of identifying and describing "good" web sources as an optimization problem and then quantify the quality of web source slices through a profit function (Section 2). We then propose an algorithm to generate the high-profit slices in a single web source and design a scalable framework to extend this algorithm for multiple web sources (Section 3). Finally, we evaluate our proposed algorithm on both real-word and synthetic datasets and illustrate that our proposed system, Midas, is able to identify interesting web sources slices in an efficient and scalable manner (Section 4). Example 2. We applied Midas on AnonSys, a dataset extracted by a comprehensive knowledge extraction system, which includes 810M facts extracted from 218M web sources. Midas is able to identify and customize "good" web sources for an existing knowledge base. In FIG2 , we demonstrate the 5 highest-profit slices that Midas derived to augment Freebase. The web source slices provide new and valuable information for augmenting the existing knowledge base ; in addition, many of these web sources contain semi-structured data with respect to entities in the reported web source slice. Therefore, they are easy for annotation. In this paper, we presented Midas, an effective and highly-parallelizable system, that leverages extracted facts in web sources, for detecting high-profit web source slices to fill knowledge gaps. In particular, we defined a web source slice as a selection query that indicates what to extract and from which web source. We designed an algorithm, Midas alg , to detect high-quality slices in a web source and we proposed a highly-parallelizable framework to scale Midas to million of web sources. We analyzed the performance of our techniques in synthetic data scenarios, and we demonstrated that Midas is effective and efficient in real-world settings.However, there are still many challenges towards solving this problem due to the quality of current extraction systems. There is a substantial number of missing extractions due to the lack of training data and one cannot infer the quality of web sources with respect to such missing extractions. In our future work, we plan to extend our techniques to conquer the limitations of extractions and improve the quality of the derived web source slices.Crawling. The first step of the augmentation process is to crawl and extract the facts in a given web source. This requires training the crawler for the facts in each slice. We use a unit cost f p to model the cost of training, which includes annotating and schema matching, for each slice. The cost for the rest of the crawling process is proportional to the size of the web source BID16 . Measuring the size of web sources is hard due to their diverse design and format; instead, we estimate it based on the total number of facts extracted from the web sources, scaled proportional to an adjustable normalization factor f c : DISPLAYFORM0 De-duplication. A typical step in the augmentation process is to identify and purge redundant facts before adding them to the knowledge base. This de-duplication is often performed through linkage BID5 BID22 BID20 between the facts of the slice and those of the knowledge base. Thus, the de-duplication cost is proportional to the number of facts selected by the web source slice, subject to an adjustable normalization factor (f d ): DISPLAYFORM1 Before adding facts to a knowledge base, it is essential to verify their validity. The cost of this step is proportional to the new facts that the slice contributes, and subject to an adjustable normalization factor (f v ) that depends on the employed validation technique BID35 BID28 : DISPLAYFORM2 Finally, we compute the cost of slices in the same web domain C(S) as the sum of the respective costs of the crawling, de-duplication, and validation steps. DISPLAYFORM3 The four adjustable normalization factors included in the computation of each of the three costs relate to the particular techniques used for the corresponding steps (e.g., different de-duplication methods may result in different values for f d ). In this paper, we set these factors such that they are roughly proportional to the actual execution time of such techniques. However, one can always adjust the setting of these factors. For our experiments, we use the default values f p = 10, f c = 0.001, f d = 0.01, and f v = 0.1 (we switch to f p = 1 for the running examples in the paper). Thus, de-duplication is more costly than crawling, and validation is proportionally the most expensive operation except training.
This paper focuses on identifying high quality web sources for industrial knowledge base augmentation pipeline.