While many researchers attempt to build up different kinds of ontologies by means of Wikipedia, the possibility of deriving highquality domain specific subset of Wikipedia using its own category structure still remains undervalued. We prove the necessity of such processing in this paper and also propose an appropriate technique. As a result, the size of knowledge base for our text processing framework has been reduced by more than order, while the precision of disambiguating musical metadata (ID3 tags) has decreased from 98% to 64%.
There's no need to introduce Wikipedia as a world's
largest and most rapidly expanding source of
information on many domains in almost every
language. At the time of drafting this paper, there are
279 Wikipedias in different languages, with more than
17,870,000 articles, 1,920,000 uploaded images, and
27,540,000 registered users [
By now, Wikipedia has already got a lot of colorful
detailed descriptions. Conventional features of
Wikipedia are well-known and discussed widely
in [
Researching community has proved more than once
that structure and content of Wikipedia are very
peculiar and valuable domains to study. One of the most
promising directions is automated ontology building
which may be accomplished by extracting well-defined
concepts and relations among them from Wikipedia.
The latest efforts in this field are DBpedia [
Despite these successes in automated upper-level
ontology building, most of domain specific ontologies
(for instance, UMLS [
In this paper, we consider the possibility of loosely supervised extraction of domain specific ontologies from upper-level ones. This is becoming feasible in recent years as high-quality upper-level ontologies grow more versatile and involve the knowledge of many new domains. Moreover, many field experts from all around the world often tend to pay their efforts to expand existing widespread ontologies, rather than to create their own or refine domain specific ones.
Our interest in this research is caused by necessity of reducing the knowledge base for our text processing framework Texterra1. This base comprises a number of textual indices produced by our Wikipedia parser. These indices are loaded into RAM during the initialization of Texterra server and take roughly 4.5 Gb of disk space and 2 Gb of RAM. Such a consumption is acceptable for workstations, but not for mobile devices with restricted amount of memory. Thus, if one would attempt to build a standalone mobile application
intended for text processing, then its data structures simply would not fit in the RAM. Obviously, such applications - if developed - would be highly demanded to date.
The disambiguation2 of musical metadata (i.e., ID3 tags of MP3 files) is an important part of Texterra functionality. These algorithms are well-tuned by the moment and show the precision of 98% on our test set. But it's obvious that only a narrow range of Wikipedia dictionary is utilized during processing ID3 tags of MP3 files. There are mostly named entities, such as musical compositions, song writers, singers, etc. Generally speaking, the amount of knowledge required to perform such a disambiguation is likely much less than that available from the entire knowledge base.
Making the knowledge base more specialized by removing concepts which are unimportant for this task is what comes to mind first in this case. So, we've implemented a system intended to produce Wikipedia subsets covering the knowledge of the given domain. We decided not to narrow the scope of our research to Wikipedia derivates (such as YAGO). But, although the algorithms have been evaluated with Wikipedia only, they are applicable to any ontology with well-defined polyhierarchical taxonomy.
Of many interesting aspects of Wikipedia, here we take into account only categorization and linkage within its content. The category system in Wikipedia plays the role of a taxonomy and provides the function to search articles by narrowing down categories. Given this, the task of deriving domain specific concepts from Wikipedia dictionary seems to be solvable by mining the category system for the list of concepts tightly connected with the given base categories. However, it is impossible to simply determine all concepts belonging to a particular category. The reason is that the category system of Wikipedia is organized into network structure, not a perfect tree structure. Furthermore, the lists of parent categories for many articles are redundant and contradictory. Thus, they don’t allow detecting the most relevant categories for a given page without analyzing the neighbour pages.
Therefore, we utilized concept vectorization method
specialized for the category system in Wikipedia, with
several additional expansion methods, as proposed
in [
Section 2 contains the review of related work. The key features of Wikipedia category structure are discussed in Section 3.
Having a fast access to any point of Wikipedia category structure was one of the crucial tasks for our research. After a number of unsuccessful tries to reuse the existing graph libraries, we've coded our own implementation, named WikiGraph. See Section 5 for details.
Given a set of specialized versions of the knowledge base, we conducted a series of experiments in order to learn how the reducing of Texterra knowledge base affects the accuracy of results. Refer to Section 6 for evaluation methodology. Section 7 contains experimental results and discussion.
We conclude in Section 8 with our research findings and discussion about possible improvements.
The field of automated ontology learning usually acts
by taking textual input and transforming it into a
taxonomy or a proper ontology. The texts are usually
obtained from printed sources (books, magazines,
newspapers) and Internet (online media, blogposts,
results of querying search engines). However, the
learned ontologies are small and hard-to-update; in
addition, evaluations have revealed a rather poor
performance [
As mentioned before, the most accurate and, thus,
valuable non-human assembled ontologies are now built
by automatically deriving explicit facts from Wikipedia.
One of the early attempts was the work of Gregorowicz
and Kramer [
Notwithstanding the foregoing, newly emerging research fields often require well-structured and comprehensive domain specific ontologies. Researchers don't need a huge knowledge base, but an extensible corpus of specific concepts with good coverage of domain knowledge. If such ontologies were built in a completely automated way, then this would avoid the necessity of assembling them from scratch manually. We believe that Wikipedia contains enough information for this task to be completed. Below is the description of approaches we've applied to narrowing Wikipedia dictionary to domain specific subset.
We consider the key problem of our study as the
computation of semantic relatedness between base
toplevel categories and underlying articles. According to
Budanitsky and Hirst [
There were many approaches proposed for
estimation of semantic relatedness between concepts in
Wordnet (Rada et al., Leacock and Chodorow, Wu and
Palmer, Resnik, Jiang and Conrath, Lin) and between
Wikipedia articles [
Since a significant part of Wikipedia knowledge is
encoded in its graph-like link structure, it seems
reasonable to apply existing graph-based methods or
introduce new ones. Zesch and Gurevych [
Obviously, it’s also attractive to estimate the strength of ties between different levels of taxonomy (between base categories and its articles, in our case). In this context, the links among articles appear not so important. Therefore, new category-based semantic relatedness measures are emerging.
Chernov et al. [
Strube and Ponzetto [
To the best of our knowledge, Cui et al. [
A more sophisticated algorithm has been proposed
later by Shirakawa et al. [
In this work, we mainly exploited the ideas
formulated in [
The advantages of Wikipedia category structure were
studied by authors of [
Categories of Wikipedia can be organized in a graph, where the nodes are categories and the edges are hyperlinks. In this work we also add articles to this graph. However, we still name it the Wikipedia category graph (WCG in the rest of the paper).
The links expressing which concept belongs to what categories are called category links. We call them belonging links or belonged links according to their direction. In this paper, we only consider the belonging links, i.e. links from articles or subcategories to upperlevel categories. The English version of Wikipedia, as of September 2010, contains ~13 million category links.
The typical code of categorized article page is shown at Figure 1. It combines XML and Wiki markup. The list of belonging categories is situated at the bottom. Categories have their own pages similar to articles. Category links at these pages also express which category belongs to what categories.
Categorization is a useful tool to group articles for
ease of navigation, and correlating similar information.
However, not every verifiable fact (or the intersection
of two or more such facts) in an article requires an
associated category. For lengthy articles, this could
potentially result in hundreds of categories, most of
which aren't particularly relevant. This may also make it
more difficult to find any particular category for a
specific article. Such overcategorization is also known
as "category clutter" [
For these reasons, the WCG has an extremely
complex nature. It is directed and has not a strong
hierarchical structure as some may expect. Any
category may branch into subcategories, and it is
possible for a category to be a subcategory of more than
one parent [
The figure has been produced by CatGraph [
It's worth noting here that not every Wikipedia page
is categorized. According to statistics [
The developed system consists of three main parts: 1. Link Filter produces a ready-for-load textual representation of WCG; 2. Topic Deriver performs the main processing; 3. Reducer produces a domain specific version of the Texterra knowledge base5.
All algorithms evaluated in this paper were implemented in the Java programming language.
The input for Link Filter is Wikipedia links file containing information about all links between Wikipedia pages, along with their type and direction. The result is category links file that contains only links forming the WCG. Every line of this file denotes the affiliation of belonging between two pages and sets the type of the belonging page. For example, means that page with ID 12 ("Anarchism") is belonging to the category with ID 780754 ("Category:Anarchism"). Moreover, the belonging page ("Anarchism") is an article because the last field is "0" ("1" would mean that the belonging page is a category).
Thus, category links file is a complete textual
representation of the WCG and contains no unwanted
data such as page titles and link types. Furthermore,
unlike the authors of [
Topic Deriver loads category links file on start and fills in the internal structures of WikiGraph (refer to Section 5 for details). The workflow for this stage is shown at the Figure 3. Here we touch on only the main steps.
For our analysis, we denote as a set of concepts, as a set of categories, and as a set of belonging links. Then, the category system in Wikipedia is expressed as a directed graph . A path is a sequence of edges that connects one node with another. The path length (hopcount) is the number of edges along that path.
The key task of Topic Deriver is to obtain the list of concepts connected semantically with certain domain. Herewith, this connection should be the tightest one, that is, these concepts should be more relevant to the 5 The Texterra knowledge base for this research has been obtained by parsing the dump of English Wikipedia, as of September 2010. desired domain than to others. As this task is computationally complex and, thus, supposed to be run rarely, it’s allowably to choose the base categories manually for experiments. We’ve selected 3 base categories that likely cover the majority of concepts required for disambiguating musical metadata: Category:Musical compositions Category:Recorded music Category:Music-related lists
For each of selected base categories, a separate
subgraph is built. This subgraph is almost the same as
Classification Tree in [
A concept vector in our research specifies the degree
of affiliation between the base category and each of
articles reachable by traversing down the subgraph of
the base category starting from its root node. As
mentioned, the heuristics for building concept vectors
have been borrowed from [
concept vectors by tracking back parent categories in the category system and calculating the belonging degree to each concept.
The belonging degree from concept to category is defined by the following equation:
Here, denotes a set of paths from to , denotes the hopcount of path , denotes a monotonically increasing function on the hopcount of path (given as ).
It’s noteworthy that in the original method [
As a result, processing time may become too large for base categories from high levels of the WCG hierarchy. The reason for such behaviour is an exclusive computational complexity of finding all paths between two arbitrary nodes in the graph. It's well-known that this task is NP-complete in general case.
Musical compositions Knowledge base (complete) Knowledge base (domain specific)
Since WCG contains millions of edges, the maximal path length may reach hundreds of edges, leading to impetuous increase of processing time when trying to process top-level categories. This is exactly why we've picked up a "safe" set of categories, which are processed relatively fast and cover the knowledge of field we've chosen for experiments.
Notwithstanding, we believe that taking all existing paths between two nodes into account allows to estimate the belonging degree more precisely. However, we didn’t confirm this assumption experimentally.
To reduce the complexity of finding all paths
between two arbitrary nodes, we tried to re-use one of
existing techniques [
For domain specific areas where categories are excessively segmentalized, the BVG method cannot extract accurately concept vectors due to the increase in hopcount. To solve this problem, the Single Parent Integration (SPI) method is proposed. The authors confirmed from their experiences that a part in the category system which corresponds to (excessively segmentalized) categories for a domain specific area forms almost a tree structure. Based on this fact, when a concept or a category has only one (onehop/multihop) belonging link, the SPI method shortens the belonging link. This is based on the idea that the characteristic is not dispersed even when parent categories are tracked back if the concept or category has only one (onehop or multihop) belonging link.
In the SPI method, if there is only one belonging link from node (or ) to , the path length of is accounted as 0, which results in reformation of to , and then the BVG method is applied to .
method) considers the weight of each category link. This method is based on the idea that the belonging degree from a certain category (concept) to parent categories depends on the number of parent categories, thus the weight of each category link is inversely proportional to the number of parent categories.
Thus, the weight of a category link becomes 1 if the category has only one parent category. That’s why the authors argue that the VVG method contains the same feature as the SPI method. Therefore, they didn’t combined VVG with SPI. We, on the other hand, tried both BVG + SPI and VVG + SPI combinations and confirmed that VVG + SPI performs slightly better than VVG itself (see Section 7 for details).
In the VVG method, weights are set to all belonging links, and the belonging degree from concept to category is calculated according to the weights. When the number of belonging links from node (or ) to category is , weight of each of the belonging links is defined as follows:
Then, given all paths , belonging degree category is defined as follows: from from concept is the weight of path following equation: , calculated by the
Here, denotes a set of all belonging links forming path and denotes a belonging link.
After the vector is built and sorted in descending order of belonging degree, it's time to apply cutting technique to it and get the list of IDs most relevant to the base category. We've tried out two approaches: 1. belonging degree threshold – concepts with belonging degrees less than the mean value of belonging degree for each vector are filtered; 2. percent threshold - 25% of concepts with the lowest belonging degrees are filtered.
Finally, Topic Deriver produces domain concepts file that contains IDs of derived concepts.
Reducer is the final part of the system. It takes domain concepts file as input, applies the concepts' list to complete Texterra knowledge base, and produces the reduced domain specific version of the latter. It contains not only concept IDs, but also full information about each of them, including the part of category structure that covers selected concepts. Therefore, the domain specific version is consistent and ready for loading into Texterra.
As showed above, fast access to any point of Wikipedia category structure is necessary for efficiency of all described computations. In particular, VVG method requires both entire WCG and subgraph of current base category to be available simultaneously.
Chernov et al. [
But our goal was to create a technique for fast iterative traversing through even a top-level categories with millions pages. Thus, we resorted to in-memory storage of WCG.
We've tried out two third-party libraries for storing the
WCG in the JVM's memory. First of them, JUNG [
But there are a number of other libraries for graph
storage which provide handy interface to stored data.
We've found neo4j [
The common shortcoming of all Java graph implementations we've tested seemed to be the redundancy of data stored in the RAM. Thus, the right way is to change the data storage manner. We put this into practice in WikiGraph.
All the prominent features of WikiGraph are due to the fact that it's intended to store WCG: 1. It is directed (as category links have a direction); 2. It introduces the notions of category and article and provides a powerful tooling to store and maintain the data on affiliations between them; 3. Only IDs and types of pages are stored. Each vertex is presented as a map consisting of [ID, isCategory] entries. This allows to store page type as a Boolean variable (TRUE is for category, FALSE is for article). All page data are saved as primitive variables, not an objects; 4. Incidence list has been chosen as a main data structure (along with vertices and edges lists). This is particularly important as the WCG is quite dense: . The incidence list is organized into a set of [vertex, [list of incident edges]] entries. Each list is sorted in ascending order of edges IDs just after the loading. This avoids the need to look over the entire incidence list to get all the edges incident to an arbitrary vertex. Moreover, due to sorting of the lists, it's allowed to interrupt the search over them after the edge with greatest expected ID is found; 5. All kinks (self-to-self links) are removed; 6. Initial capacity of the incidence list is beforehand set to approximate amount of vertices in WCG (3,500,000 for this case). This saves some memory allocation costs while loading; 7. A set of helper methods is developed also (for instance, a method for deriving a subgraph of a given base category). This set provides usable and fast interface to the WCG data.
After the described features were implemented, they allowed us to fit WCG entirely in the RAM (~4 Gb needed) and lead to significant speed-up of loading and processing.
Obviously, a domain specific subset of Wikipedia should have a good coverage of domain knowledge. But there is no easy direct way to evaluate quality of such a subset. The reason is that we must evaluate the completeness of knowledge available from Wikipedia's articles in resulting subset compared to that of specific domain. It's clear that this is rather difficult. In addition, the quality of link structure in the resulting subset should be also evaluated.
Therefore, we applied so called in vivo approach for evaluation. To estimate the quality of proposed methods, we studied how applying of the extracted subsets affects the performance of Texterra as a whole.
As mentioned before, one of Texterra parts is the
system that enriches ID3 tags for musical recordings
with links to corresponding articles of Wikipedia. This
system utilizes graph structure to compute semantic
relatedness between Wikipedia pages [
We assume that each page of Wikipedia describes one possible meaning. WSD algorithm selects the most consistent combination of meanings that correspond to input ID3 tags. For sequence of input tags, it computes similarity between all pairs of meanings. The weight of a sequence is a sum of weights of all its pairs. Then, the algorithm detects a sequence with greatest weight.
To show good results, the derived subset should include as much as possible Wikipedia articles associated with a specific domain. In additional, link structure should be good enough for relatedness computation. Therefore, this approach allows evaluating both the quality of dictionary content and the quality of link structure.
For testing purpose, we derived several musicrelated subsets of Wikipedia by running different combinations of heuristics and used these subsets for described system. Then, we consequentially loaded these domain specific versions of knowledge base into Texterra and ran the tests. We used a small corpus of 20 random musical compositions and 49 different tags. Then, we estimated the precision of automated disambiguation by comparing the results of algorithm with manually disambiguated tags.
The configuration of test workstation was as follows: Intel Core 2 Duo CPU (3.16 GHz), 8 Gb RAM, Windows 7 Enterprise 64 bit, Java SE 6 Development Kit 1.6.0.20.
Sample vectors for different combinations of heuristics are provided in Tables 1-4. Each sample vector comprises three concepts with highest belonging degree and three concepts with lowest values. The base category is Category:Musical compositions. It’s noteworthy that BVG vector differs significantly from VVG one. Furthermore, enabling SPI affects both vectors.
The results of the experiments with different combinations of vector generation methods and cutting techniques are presented in Table 5. Contents of all 3 base categories listed in Section 4.2 are included.
Ground truth row corresponds to original Texterra knowledge base. As can be seen, it is huge, but ensures the best accuracy of disambiguation.
No threshold is for case when no cutting technique is applied to the concept vectors. In other words, this set of IDs exactly matches the set of all articles from subgraphs of all base categories. This version is much smaller, but the precision gets lower also. This precision drop (when no threshold is applied yet) is only due to imperfect choice of base categories. They merely don't cover all concepts required for precise disambiguation. It's also obvious that all comparisons of heuristics results should be done with no threshold results, not with ground truth.
As one can see, BVG performs a bit better than VVG. The most accurate combinations of heuristics are BVG + percent threshold and BVG + SPI + percent threshold. Enabling SPI for VVG slightly increases the precision of disambiguation. Percent threshold is definitely better than belonging degree threshold.
What's important here is that the size of Texterra knowledge base (both on disk and in RAM) depends linearly on the number of concepts. Thus, the challenge is to find a compromise between the precision of disambiguation and the size (and contents) of the knowledge base.
The conducted experiment was just our first effort of this kind. Implemented algorithms allowed us to reduce the size of Texterra knowledge base by more than order, while the precision of disambiguating musical metadata has decreased from 98% to 64%. We believe that these results prove the applicability of proposed approach for deriving domain specific subset of Wikipedia. Certainly, there're still many things to improve.
According to the results of this study, we outline the following: Wikipedia categories network may be utilized for domain specific subset of Wikipedia;
cutting technique.
Possible directions of future work include:
1. As noted by the authors of [
In this work, we’ve demonstrated the possible benefits of automated building of the domain specific ontologies. Also, we’ve tested different heuristics while implementing the system for such processing. An original approach to storing WCG in the RAM has been proposed, along with specific evaluation methodology.
The described approach can be applied to any
ontology with well-defined polyhierarchical taxonomy
(for instance, YAGO2). As it seems to us, weighting the
existing semantic connections is always a challenging
task while building any more or less large ontology.
This may be helpful for any domain dependent
Wikipedia-related research [
Threshold belonging degree
percent belonging degree
percent belonging degree
percent
belonging degree
percent
—
—
the root node is vital to the quality of the domain
specific corpus. Thus, it’s reasonable to
introduce some heuristics for automated
identifying of the most appropriate base category
given just a set of specific keywords. Moreover,
there can be several base categories with either
manually or automatically set relevance levels.
For example, to perform the search for
"Musicians of World War II" a user should
provide 2 base categories as an input:
Category:Musicians with relevance level of 0.9
and Category:World_War_II with relevance
level of 0.5;
2. Try other cutting techniques for concept vectors
(i.e., attempt to detect the distribution of
belonging degrees and utilize it);
3. Detect and remove meaningless pages from the
WCG (i.e., pages from administrative section of
Wikipedia [