Seas of web pages in the Internet contain free texts in natural language that are only read by human beings. To be understandable for machines, these pages should be annotated with semantic markups. Manually annotating large amounts of pages is an arduous work. This has made automatic semantic annotation an urgent challenge. In this paper, we propose a machine-learning based automatic annotation approach. This approach can be trained for different domains and requires nearly no manual rules. The annotation is on the sentence level and is in RDF format. We adopt a dependency grammar -Link Grammar [2] -for this purpose. ALPHA system, a prototype of this approach has been developed with IBM China Research Lab. We expect many improvements are possible for this approach and our work may be selectively adopted or enhanced.
1 Introduction There are seas of web pages in the Internet and nearly all of them contain free texts in natural language that are only read by human beings. Annotating these pages with semantic markups is one promising way to make them understandable for machines. Unfortunately, automatic semantic annotation for the natural language sentences in these pages is a daunting tas k and we are often forced to do it manually or semi-automatically using handwritten rules. In this paper, we propose a machine-learning (ML) based automatic semantic annotation approach that can be trained for different domains and require almost no manual rules. The annotation resulted form this approach lies in the sentence level, i.e., we will annotate each sentence or prime sentences in a web page. This approach stems from our previous research on semantic analy sis on natural language sentences using Co nceptual Graphs (CG).
Free texts in the Internet contain various information in diverse domains. The method we proposed in this paper is for domain specific sentences that are sentences occur in a specific application domain. Though the sentences are limited in one domain, our method itself is domain independent and the system can be trained for various domains.
Domain specific sentences are usually very stylish in the
words, phrases, grammar and semantics they employ,
which lead to a strong patterned text for which machine
learning based approach is effective. Our approach is
independent on any ML algorithm. In the prototype
ALPHA system, we employed instance-based learning.
Link Grammar is first used to get the syntactic structures
of sentences. The learn ing process then learns to map the
syntactic structures to semantic structures –RDF graphs.
WordNet [
The paper is organized as follows. Section 1.1 explains the concept of “Domain Specific Sentences” used in this paper. Section 1.2 briefly shows what the result RDF looks like. Section 1.3 explains the reason to adopt Link Grammar. Section 2 outlines the whole approach by giving an overview. Section 3 presents the detailed process that generates RDF graph from domain specific sentences. Section 4 discusses the result of ALPHA system. Section 5 concludes our work by comparing related work. 1.1 Domain Specific Sentences Domain specific sentences point to those sentences that are frequently occurring in one certain application domain text but scarcely in others. They are assumed to own the following characteristics:
II. word usage has patterns
III.semantic ambiguities are rare
IV.terms and jargon of the domain appear frequently
The notion of sublanguage [
<rdfs:label>shanghai</rdfs:label> </Concept> <rdf:Description about="#1"> <AGNT rdf:resource="#2"/> </rdf:Description> <rdf:Description about="#2"> <DEST rdf:resource="#3"/> </rdf:Description> </rdf:RDF>
I
Class “Concept” represents concept in sentence. In the
current implementation, we are using WordNet [
Each word in Link Grammar has a linking requirement
stating what types of links it can attach and how they are
attached. The link requirements are stored in a Link
Grammar dictionary. The parse result is called a linkage or
a link structure. The Link Grammar parser is called a link
parser. Currently, the link parser from CMU [
The most important reason that makes us adopt Link Grammar in our work is the structure similarity between Link Grammar parse result and RDF graph. Fig.2 shows this similarity by comparing the Link Grammar parse result, the typical parse tree of a constituent grammar and the Sp*I
MVp
Js to
The link structure: The grammar tree:
NP PRO
I The RDF graph: go
S V go I I VP
N
RDF graph for the same example sentence. In fact, this
similarity comes from the common foundation of both RDF
graph and Link Grammar. RDF graph consists of concepts
and relations. The relations denote the semantic
associations between concepts. Similarly, link structure
consists of words and links. The links directly connect
syntactically and semantically related words [
Domain Knowledge
Expert
Training Corpora Training Interface Mapping Operations
Vector Generator
Link
Parser link structure
link structure Domain Ontology Training Vectors
Generating Phase
Domain Specific Sentence
RDF
RDF
Generator context vector
classification
Machine
Learning
Engine
Based on this similarity and restricted to a specific
domain, we propose to automatically generate annotation
by learning the mapping from link structure to RDF graph.
Another important feature of Link Grammar is that the
grammar is distributed among words [
Training Phase ontology. Since semantic ambiguities are rare in domain specific sentences (see section 1.1), it is relatively easy to perform these mapping operations (the process of semantic analysis).
What training phase does is a pre paration. Before the
system can learn to do the mapping in the generating
phase, we convert the mapping into machine learning area.
Most of studied tasks in machine learning area are to infer
a function that classifies a feature vector into one of a
finite set of categories [
After sufficient training vectors and categories are obtained in the training phase, the system can enter into the generating phase. RDF generator, the main part of the generating phase will implement the following algorithm The first step of both phases is to invoke Link Grammar, and parse the sentence into its link structure, which will be mapped to RDF through different means in the two phases.
In the training phase, some domain experts will go through a three-operation process to transfer the link structure into RDF graph manually bas ed on their domain knowledge. Each operation maps a certain part of the syntactic structure to its corresponding semantic representation according to the syntactic and semantic context. Concepts, schemata 1 and relations contained in the semantic representation are selected from the domain 1 Schemata, is a set of RDF graphs describing background information in a domain. under the help of ML engine and Link Grammar after it is given a sentence from object domain.
4 5 6 7 8 9 1 get the link structure for the sentence from link parser. 2 generate an empty RDF graph. 3 for (i = 1 to 3) { //perform the three kinds of operations generate all possible context vectors from link structure for the i-th kind of operation. for (every context vector) { if (an operation is needed for this vector) { classify the vector using ML engine. decode the classified category as an operation. perform the operation on the link structure and 17 output the final RDF annotation for the sentence.
Algorithm 1. The algorithm of the RDF Generator
Our approach is independent of specific ML algorithm used. In ALPHA system, we adopt IBL (Instance Based Learning) for the ML engine because IBL makes it easy to determine whether an operation is needed for an arbitrary vector in the above algorithm (line 6). IBL can return a distance value along with the classification result. If the distance value is too large, it can be determined that no operation is needed for the vector because it is far from In the training phase, domain experts select all the open words in the link structure one by one. Once an open word is selected, the training interface can provide the expert a list of possible concepts or schemata retrieved from the domain ontology. The expert then chooses the appropriate one from the list.
This operation is then encoded by the vector generator into a context vector and its category. For example, the context vector for the open word “polo” in the example sentence may be <polo, NN, Dmu, Mp>2 in which “NN” is the POS (part-of-speech) tag3 and “Dmu” and “Mp” are the innermost left and right link types of “polo” (see Fig.4). All the context information is obtained from the link structure.
The category for the context vector is encoded as the result of the operation –the ID of the selected concept or schemata in the domain ontology. The encoding is something like “WN16-2-330153” which can be used later as a key to retrieve concept (in WordNet terminology, Dmu
Mp
Ss Js
Ds
Pv
MVa
MVp The polo with an edge is refined enough for
Jp work being similar to existing training vectors and may be deemed as noise. For other learning methods, this determination may not be easily achieved.
In the following section, we will explain Algorithm.1 and the three operations by taking an example sentence “The polo with an edge is refined enough for work”, which is excerpted from a corpora of clothes descriptions collected from many clothes shops on the Web. In the sentence, “Polo” is a brand and represents a certain kind of shirts and “edge” actually means collar. The link structure for this sentence is shown in Fig.4. 3 Learning to generate RDF In this section we will introduce the three operations that map a link structure to RDF: word-conceptualization, linkfolding and relationalization. These three kinds of operations must be performed exactly in the right order in both the training phase and the generating phase because a later operation may use information generated in the previous operations. In section 3.4, the integration on RDF graph (line 16 of Algorithm.1) is explained. 3.1 Word-Conceptualization
Word-conceptualization is the first operation to be performed. Its function is to annotate open words as concepts in the sentence to form the skeleton of the initial empty RDF graph and mark close words for further operation. This operation can be seen as a word sense disambiguation operation.
word sense) from the WordNet database.
Since WordNet is not specific for any domain, some words in a certain domain may not exactly match any sense in the list. For those words the experts are asked to choose the most similar sense instead of adding a new sense to WordNet so as to preserve the hierarchy in WordNet for further research.
Generating all possible context vectors (line 4 of Algorithm 1.) is actually to generate one context vector for each open word in the link structure of the sentence. The generated context vector is then sent to the ML engine as to do a classification. The returned category is an encoding of concept or schema ID. In line 9 of Algorithm 1, the RDF generator retrieves the concept or schema from the domain ontology according to the decoded ID and creates a concept node in the RDF graph.
Because word usage has patterns in domain specific sentences, we expect that similar context vectors appear 2 The vector is just an example. For brevity, we are not trying to make the vector encoding perfect in this paper. Actually, what context information is encoded into the vector is a separate problem. This problem is isolated into the vector generator component. In the current implementation, we defined a configuration file for the vector generator to address the issue. 3 We can augment the link parser with a POS tagger so that the accurate POS tag information can be added to the link structure and be obtained from it later. for a given open word on a specific word sense. Based on these similar context vectors, we expect the ML engine can return correct classification with a high possibility since the semantic ambiguity is also rare in domain specific sentences.
After this step, all concept nodes of the RDF graph should be created. The RDF graph for the example sentence is shown in Fig.5. For convenience, we use simple concept names in Fig.5. The “S-WORK” is the “SUITABLE-FOR-WORK” schema in domain ontology.
EDGE
REFINE The following two operations focus on creating the semantic relations between the concepts. Closed words (especially prepositions) with their links imply relationships between the concepts of the words they connect. In the example sentence, “… polo --- with --edge …” fragment implies a PART relation between [POLO:#] and [EDGE]. We then “fold” the 'with' and its left and right links and replace them with a PART relation. This is just what the link-folding operation does. Closed words with their links representing semantic relations can be seen as word usage patterns. In domain specific sentences, such patterns are expected to occur frequently. This actually enables the machine to learn the patterns from training corpora. In addition, since semantic ambiguities are rare in domain specific sentences, it can be expected that the result of the learning converge on the correct relation. Similar analysis also applies to the next operation –relationalization in section 3.3.
In the training phase, the domain expert can select any closed word that connects two concepts and implies a semantic relation and map it to the responding semantic relation from the relation ontology4.
The context vector for this operation may encode context information such as the POS tag of the closed word, the left and right link types and the two concepts. The category is an encoding of the relation ID in the domain ontology. For the “… polo --- with --- edge … ”case, the context vector may be <with, IN, Mp, Js, POLO, EDGE>5. 4 For brevity, we omitted the direction of a relation here. 5 The POLO and EDGE in the vector are actually the concept IDs in the domain ontology. We will use the same convention in the following vector examples. And the category is the encoding of the ID of the PART relation in the domain ontology. In the generating phase, generating all possible context vectors for this operation (line 4 of Algorithm 1.) is actually generating one context vector for every possible case in which a closed word connects two concepts. This needs consult the concept information generated in the word-conceptualization operations. If an operation is needed for the vector, it is sent to the ML engine to do a classification. The returned category is an encoding of the relation ID in domain ontology. In line 9 of Algorithm.1, the RDF generator retrieves the relation from domain ontology according to the ID and creates the relation between the two concepts.
For the example sentence, there are three closed words that need link-folding operation: ‘with’, ‘is’and ‘for’, as shown in Fig.4. Among them, the word ‘is’is an auxiliary verb and ‘with’and ‘for’are prepositions.
The relation implied by the auxiliary verb ‘is’is THEME and the ‘for’ between ‘refined’ and ‘work’ implies a RESULT relation. The RDF graph after this step has relations added between concepts. As to our example sentence, the RDF graph has grown to Fig.6.
Semantic relation can also be implied by a link that directly connects two concepts in the link structure. For example, the ‘MVa’link between ‘refined’and ‘enough’in the link structure of example sentence implies a MANNER relation. The relationalization operation translates this kind of links into corresponding semantic relations.
In the training phase, domain knowledge expert can select any link that implies a semantic relation between concepts it connects. The expert then selects the semantic relation from the domain ontology for the connected two concepts.
The context vector for this operation can include information such as the link type and the concepts. For the “… refined –MVa – enough … ”, the context vector may be <MVa, REFINE, ENOUGH>. The category for the context vector can be encoded as the relation ID in the domain ontology. For the above vector, it is the ID of the MANNER relation.
In the generating phase, generating all possible context vectors for this operation (line 4 of Algorithm 1.) is actually generating one context vector for every link that connects two concepts. If an operation is needed for the vector, it is sent to the ML engine to do a classification. The returned category is an encoding of the relation ID in domain ontology. In line 9 of Algorithm.1, the RDF generator retrieves the relation from domain ontology according to the ID and creates the relation between the two concepts.
After this step, more relations may be created in the RDF graph. As to the example sentence, the MANNER relation will be created to connect the [REFINE] concept and the [ENOUGH] concept and the whole graph grows to Fig.7.
3.4 Integration
Integration is the last step (line 16) in Algorithm.1. This
step is not a part of the training phase. It only appears in
the generating phase and it is the only step that uses
manually constructed heuristics. What it does includes
simple co-reference detection and nested graph creation.
In the discussion of the previous three operations, we
don’t involve lambda expressions for brevity. In fact, they
may appear when words for concepts are missed in the
sentence. They may als o be introduced when schema is
selected in word-conceptualization phase. In order to
complete the RDF graph, we need to draw co-reference
lines between the variables in these lambda expressions.
Although there is machine-learning based approach for
co-reference detection [
Nested graph (context) may be introduced by expanding schema definition or removing modal/tense modifiers of a concept. Although RDF specification lacks a clear semantics about RDF reification, we are now using RDF reification mechanism to represent nested graph (context). In our example, we have mentioned in section 3.1 that the concept type S-WORK is actually a “SUITALBE-FORWORK” schema from the domain ontology. We can do an expansion on it. Fig.8 is the definition for the “SUITALBEFOR-WORK” schema. SUTB represents the relation SUITABLE.
After the expansion, we can do a simple co-reference detection that draws a co-reference line between the type SUITABLE-FOR-WORK(x) is
WORK-SITUATION
Fig. 8. The definition for SUITABLE-FOR-WORK undetermined variable x and the current topic [POLO:#]. After this step, the final graph is generated. Fig.9 is the result for our example sentence “The polo with an edge is refined enough for work”. 3.5 Summary Through the sections from 3.1 to 3.4, we have explained how we map link structure to RDF graph and convert the
WORK-SITUATION
Fig. 9. The final RDF graph of the example sentence mapping to machine learning area. Wordconceptualization builds concepts in the RDF graph. Linkfolding and relationalization connect concepts with semantic relations. In the last step, we use manually constructed heuristics to do simple co-reference detection and nested graph creation. 4 Results We have developed a prototype called ALPHA system written in C. ALPHA system is now running on Solaris. It can be trained for different domains. Currently in our work, clothes domain is chosen as the sample domain. Nearly 300 clothes descriptions, 500 sentences have been collected from clothes shops on the Web6 and are trained in ALPHA system. Among them, 34 descriptions and 93 sentences are reserved for testing. The test result is shown in Fig.10. Using different IBL algorithms, the accuracy7 of concepts varies from 60% ~ 80%, and that of relation varies from 45% ~ 60%.
The result demonstrated the feasibility of our approach. 6 Those online shops include www.brooksbrothers.com and www.gap.com, etc. 7 Here the accuracy of concepts = concepts annotated correctly / total concepts, and the accuracy of relations = links annotated correctly / links that should be annotated.
Link Grammar has a strong impact on the accuracy of ALPHA system. Although its characteristics make it relatively easily to add domain grammar, it has some trouble in disambiguating the syntactic structure of overabridged sentences in clothes domain, such as “Back vent.”, which causes a serious failure in ALPHA system. Though we are aware of the problem, we will let it be at according to construction rules on how to fill the slots. Although this approach has been successfully applied in many applications, it heavily depends on manually created construction rules on the parse tree.
Another kind of technique advanced in previous work is to directly map between syntactic structure and semantic present because we want to pay more attention to semantic disambiguation.
To improve the accuracy of ALPHA system, we are
considering developing new algorithms that can compute
the distances of vectors more accurately . We are also
considering making changes in the architecture so as to
support the analysis of clauses and idioms. Further more,
other application domains will be selected to test our
approach.
5 Related works
Ontology-based annotation is most studied such as [
In natural language annotation, grammar-based approach is often used. They can roughly be divided into slot-filling and structure -mapping categories according to their generating techniques.
Slot-filling techniques such as [
Up to now most methods for annotation are by hand or
heavily depend on rules created manually. These methods
will have difficulty in applying to the Web because of the
tremendously large amounts of pages . Our approach
provides an automatic way to annotate them in a faster
and robust way. Research on machine learning in natural
language processing using corpora data [