1.     INTRODUCTION

Currently, there are a few semantic annotation platforms which extract information from web pages and annotate them with ontology. For example, S-CREAM [1] supports the semi-automatic annotation for web pages. KIM [2] provides a novel Knowledge and Information Management infrastructure and services for automatic semantic annotation, indexing, and retrieval of documents. WebKB [3] extracts instances of classes and relations based on web page contents and their linkage path.

However, few of the previous works focus on detecting semantic relationships. Furthermore, the existent semantic annotation systems mainly discover the relationships making use of web linkage or sentence structures. As a result, only relationships between pages or within a sentence can be extracted.

There also exist a large amount of semi-structured documents other than web pages, such as academic papers, enterprise reports. This kind of documents is different from web pages, because they usually do not contain hyperlinks, and authorized in strict logical structure. Therefore, we need a new algorithm that fits into the features in this kind of documents.

In this paper, we propose an approach that exploits document logical structure to extract relationships. We first extract text pieces as data type property values with iASA [4] . Then we compute the probability that two property values are related by the same instance using logistic regression. And then we find the relationships between the property values that maximize the loss function.

2.     Problem Statement

Now we formally define the relationship extraction problem that we are solving.

We first give the definition of knowledge base in our scenario. A knowledge base can be viewed as a three tupel:

where C denotes a set of concepts; P denotes a set of property; I denotes a instance set of all concepts. Specifically, let denote a concept,  denote a property and i_c denote an instance of concept c, i.e..

We now illustrate the problem of relationship extraction by an example. Say we have a document snippet about hotel information:

The task is to annotate the snippet by the following ontology:

By semantic information extraction tool (e.g. iASA), we can obtain:

Then the task is to associate the information correspondingly (i.e. in this example, we need associate the hotel name, address and phone number). This is exactly the problem semantic relationship extraction addresses. Finally, the output might be:

3.     Our Approach

Before explaining our approach in detail, we give two assumptions:

1.        Property values for the same instance are usually in the same relative position in logical structure. For instance, hotel name is usually in the parent logical level of hotel address.

2.        Two property values usually appear in a document in a constant order. For instance, hotel address usually appears before phone number.

Definition1. For any property values l₁ and l₂, they are called relevant if and only if there exist , , ,  having ,. In other words, l₁ and l₂ are property values for the same instance. We use to denote the relevant relation.

Our approach has two main steps. At the first step, we use property values extracted by iASA and their logical structure information as input, and exploit logistic regression to predict the probability of  for any property value pair. At the second step, we use the relevant probabilities to construct the instances by maximizing a loss function defined in 3.2 section. The output is constructed instances which is similar to figure 2.

3.1     Relevant Probability Estimation

We consider one implementation of our approach. We employ logistical regression [5] in the relation probability estimation. It has not been investigated previously to the best of our knowledge.

The learning based probability estimation consists of two stages: training and prediction.

In training, we train a regression model  for each property pair p_m, p_n that have the same domain concept. Table 1 shows the major features used in the regression model.

Table 1: Features used in regression model

Where, the logical distance is defined:

where  denotes their closest common ancestor, and level(l) means the length from l  to the root node.

3.2     Instance construction

For each concept c, we associate property values with instances so as to maximize the loss function:

where p(i, l) means the value of property p of instance i is l, and P(r_mn(l_a, l_b)) represents the probability that l_a and l_b are relevant.

Obviously, it is impossible to enumerate all the instance list candidates {i_c1,i_c2,¡­,i_ck}, and select the one which maximize the loss function. So we propose an algorithm to construct the instances:

Step1. for each text value l of property p, construct instance i, s.t. p(i,l).

Step2. for each text value l of property p_n, find instance i* that maximize:

then attach l to i*, i.e., set l as the value of property p_n of i*, and detach l from the original instance.

Step3. compute Loss^(k). If Loss^(k) -Loss^(k-1) <, then stop, otherwise repeat step2.

The complex of step2 is O(n_l²), where n_l is the number of property values. A property value l may be reattached to instances more than one time, because the attachment changing of other property values may affect l.

4.     Conclusion

In this paper, we investigated the problem of semantic relationship extraction from semi-structured documents. We give a definition of relationship extraction problem. We proposed an approach for the problem by using logistic regression.