Incorporating domain knowledge is one of the most challenging problems in data mining. The Semantic Web technologies are promising to offer solutions to formally capture and efficiently use the domain knowledge. We call data mining technologies powered by the Semantic Web, capable of systematically incorporating domain knowledge, the semantic data mining. In this paper, we identify the importance of semantic annotation-a crucial step towards realizing semantic data mining by bringing meaning to data, and propose a learning-based semantic search algorithm for annotating (semi-) structured data.
It has been widely stated that one of the most important and challenging
problems in data mining is incorporation of domain knowledge. Fayyad et al. [
At the same time, research in the area of the Semantic Web has led to quite
mature standards for modeling and codifying knowledge. Today, Semantic Web
ontologies become a key technology for intelligent knowledge processing,
providing a framework for sharing conceptual models about a domain. Moreover, the
large and continuously growing amount of interlinked Semantic Web data have
provided perfect applications for novel data mining methods. Such methods
focus on relations between objects in addition to features/attributes of objects [
The majority of data underpinning a wide spectrum of data mining applications are stored in structured sources such as relational databases (RDB) with their proven track record of scalability and reliability, or in semi-structured sources such as spreadsheets with their advantage of low maintenance and cheaper overheads. Hence the problem of how to impart knowledge encoded in Semantic Web ontologies to (semi-)structured data becomes a major challenge in realizing the semantic data mining. Semantic annotation aims at addressing this challenge by assigning semantic descriptions to elements of data. To ease the burden of common users that are not familiar with the Semantic Web, we propose, in this paper, a learning-based semantic search algorithm to automatically suggest appropriate semantic descriptions for annotation.
In the next section, we first examine the field of semantic annotation and then propose the learning-based solution. 2
Semantic Annotation aims at assigning to the basic element of information links
to formal semantic descriptions [
The annotation process can be generally divided into two steps. The first is to establish mappings between existing Semantic Web terms and those need to be annotated in data. The second step is to come up with a local ontological structure constituting the semantic web terms to model the data. Most of previous work in annotating (semi-)structured data focus on the second step. Some skip the first step and bootstrap the ontological terms and structure from the local data itself. For example, a number of systems that map data in RDB to RDF format leverage a set of rules such as “table to class and column to predicate”.
We argue that such syntactical translation alone without referencing to existing semantic descriptions does not lend itself well to aiding semantic data mining. The automatically constructed self-contained local ontology may be applicable to describe a specific dataset but is most likely too rough to capture the full domain semantics that is necessary to express meaningful domain knowledge. Moreover, with the advent of the Semantic Web and pervasive connectivity, an increasing number of ontologies has been made widely available for reuse. These ontologies are created by thorough knowledge engineering process and should serve as better models for annotation. However, on the other hand, the sheer number of Semantic Web ontologies and lack of effective search functionality can lead to a huge hidden barrier for common users. Choosing proper Semantic Web ontologies and terms (classes and properties) requires familiarity with appropriate ontologies and the terms they define. There is very few system that is able to provide automatic suggestions. To solve this problem, we propose a learning-based semantic search algorithm to suggest proper Semantic Web terms and ontologies for annotation given semantically related words and general domain and context information. 2.1
Proposed Learning-based Semantic Search Algorithm In order to suggest suitable Semantic Web terms and ontologies for users to annotate their data, we propose a learning-based semantic search algorithm. We first submit a list of terms appeared in the schema of (semi-)structured data to our semantic search algorithm and then use the returned results for annotation. In a fully automatic setting, the search algorithm is configured to return the top1 hit; while in an interactive setting, the search algorithm returns ordered top-k search results for users to decide. Previous semantic search algorithms leverage a variety of measures, including lexical and structural similarities (see details below) to rank Semantic Web documents according to how likely they can be semantically matched to the search terms. However, using any single measure alone may not be sufficient to achieve the optimal result. We propose to combine various measures to a weighted feature-based search model, where the weights are learned from training data. We believe the incorporation of learning techniques will improve the semantic search result.
Feature-based Semantic Search Model. Consider a set of ontologies O =
{O1...Om} returned as the search result for a specific search term. Let =
{ϕ1(Oi)...ϕm(Om)} be a vector of real-valued feature functions ϕ : O 7→ R that
compute rank indicating how ontologies should be ordered in the search result.
The one with the highest rank is the top-hit for a specific search. Let W =
{w1...wm} be a vector of real-valued weights associated with each feature. A
score is computed for each ontology Oi by taking the dot product of the features
and weights: τ (Oi, W) = · W . We can leverage a variety of ranking methods
proposed in the literature as the feature functions . For example, Alan et al. [
Training Set. Our algorithm to determine the weight vector W requires a training set of known top hit in the search result (chosen by human): T = {< O1, l1 > ... < On, ln >} , where each set of ontology namespaces Oi = {O1...Ok} is associated with label li ∈ {1...k}, indicating which of the ontologies should be selected for annotating the specific term ti (i.e., Oli ∈ O is the true ontology selected by human as the best choice for annotating the term). There are several ways to estimate W from the training set T as described below. Subgradient Descent. We can view the weight learning as maximum margin structured learning problem. Given a training set and loss function, the learned W should score each known top-hit result Oli higher than all other O by at least L(Oli , O), where L is the loss function. Mathematically, this constraint is ∀i, O ∈ {Oi\Oli }, W · (Oli ) ≥ W · (O) + L(Oli , O) , where {Oi\Oli } is the set of possible ontologies returned by a specific search query excluding the gold standard ontology Oli chosen by human. We can express this constraint as the following convex program: min W; i 2 λ
d
∥W∥2 + 1 ∑ ζi . s.t.∀i, O ∈ O, W · (Oli ) + ζi ≥ W · (O) + L(Oli , O) ,
d i=1
where λ is a regularization term that prevents overfitting. We can rearrange the
convex program to show that the optimal W minimizes
(1)
(2)
c(W) = 1 ∑d ri(W) + λ
d 2
i=1
∥W∥2 ,
where ri(w) = maxO2fOli g(W · (O) + L(Oli , O)) − W · (Oli ) . This objective
function is convex but nondifferentiable. We can therefore minimize it with
subgradient descent, an extension of gradient descent to nondifferentiable objective
functions. The subgradient of equation 1 can be computed iteratively [
L (W, T ) = − ∑ log p (Cli |O, W) .
Oi2T
We can find the setting of W that minimizes Equation 2 using limited-memory
BFGS, a gradient ascent method with a second-order approximation [
In this paper, we introduce semantic data mining, an area we envision emerging as the solution to systematic incorporation of domain knowledge in data mining with the help of the Semantic Web technologies. We also recognize that vast amount of information stored in (semi-)structured sources is calling for attention to develop innovative approaches to solve following challenges: 1) how to impart knowledge encoded in ontologies into the (semi-) structured data, and 2) exploration of more meaningful ways to utilize the knowledge. We believe semantic annotation is the solution to the first challenge. In this paper, we propose a learning-based semantic search algorithm to suggest appropriate Semantic Web terms and ontologies.
This work is supported by the NIH funded NEMO project (Grant No. R01EB007684 NIH/NIBIB). I am grateful to Dr. Dejing Dou and Dr. Daniel Lowd for helpful discussion and comments.