Coping with Web Knowledge

Coping with Web Knowledge J.L. Arjona, R. Corchuelo, J. Pe˜na, and D. Ruiz The Distributed Group Avda. de la Reina Mercedes, s/n, Sevilla (Spain) {arjona,corchuelo,joaquinp, druiz}@lsi.us.es Abstract. The web seems to be the biggest existing information repository. The extraction of information from this repository has attracted the interest of many researchers, who have developed intelligent algorithms (wrappers) able to extract structured syntactic information automatically. In this article, we formalise a new solution in order to extract knowledge from today’s non-semantic web. It is novel in that it associates semantics with the information extracted, which improves agent interoperability; furthermore, it achieves to delegate the knowledge extraction procedure to specialist agents, easing software development and promoting software reuse and maintainability. Keywords: knowledge extraction, wrappers, web agents and ontologies 1 Introduction In recent years, the web has consolidated as one of the most important knowledge repositories. Furthermore, the technology has evolved to a point in which sophisticated new generation web agents proliferate. A major challenge for them has become sifting through an unwieldy amount of data to extract meaningful information. This process is difficult because the information on the web is mostly available in human-readable forms that lack formalised semantics that would help agents use it. The Semantic Web is “an extension to the current web in which information is given well–defined meaning, better enabling computers and people to work in cooperation” [3], which implies a transition from today’s web to a web in which machine reasoning will be ubiquitous and devastatingly powerful. This transition is achieved by annotating web pages with meta–data that describe the concepts that define the semantics associated with the information in which we are interested. Ontologies play an important role in this task, and there are many ontological languages that aim at solving this problem, e.g., DAML+OIL [13], SHOE [17] or RDF-Schema [5]. The Semantic Web shall simplify and improve The work reported in this article was supported by the Spanish Interministerial Commission on Science and Technology under grants TIC2000-1106-C02-01 and FIT-150100-2001-78. the accuracy of current information extraction techniques tremendously. Nevertheless, this extension requires a great deal of effort to annotate current web pages with semantics, which suggests that it is not likely to be adopted in the immediate future [9]. Several authors have worked on techniques for extracting information from today’s non-semantic web, and inductive wrappers are amongst the most popular ones [6,14,15,16,19]. They are components that use automated learning techniques to extract information from similar pages automatically. Although induction wrappers are suited to extract information from the web, they do not associate semantics with the data extracted, this being their major drawback. Furthermore, adding these algorithms to logic that a web agent encapsulates, can produce tangled code and does not achieve a clear separation of concerns. In this article, we present a new solution in order to extract semanticallymeaningful information from today’s non-semantic web. It is novel in that it associates semantics with the information extracted, which improves agent interoperability, and it delegates the knowledge extraction procedure to specialist agents, easing software development and promoting software reuse and maintainability. We address these issues by developing knowledge channels, or KCs for short. They are agents [21] that allow to separate the extraction of knowledge from the logic of an agent, and they are able to react to knowledge inquiries (reactivity) from other agents (social ability), and act in the background (autonomy) to maintain a local knowledge base (KB) with knowledge extracted from a web site (proactivity). In order to allow for semantic interoperability, the knowledge they manage references a number of concepts in a given application domain that are described by means of ontologies. KCs extract knowledge from the web using semantic wrappers, which are a natural extension to current inductive wrappers to deal with knowledge on the web. Thus, we take advantage of the work made by researchers in the syntactic wrappers arena. The rest of the paper is organised as follows: Next section glances at other proposals and motivates the need for solutions to solve the problems behind knowledge extraction; Section 3 presents the case study used to illustrate our proposal and some initial concepts related to knowledge representation; Section 4 gives the reader an insight into our proposal; finally, Section 5 summarises our main conclusions. 2 Related Work Wrappers [8] are one of the the most popular mechanisms for extracting information from the web. Generally, a wrapper is an algorithm that translates the information represented in model M1to model M2. In information extraction, they are able to translate the information in a web page to a data structure that can be used by software applications. In the beginning, these algorithms were codified manually, using some properties of a web page, normally looking for strings that delimit the data that we need to extract. But hand-coded wrappers are error–prone, tedious, costly and time–consuming to build and maintain. An important contribution to this field was provided by Kushmerick [15]. He introduced induction techniques to define a new class of wrappers called inductive wrappers. These inductive algorithms are components that use a number of extraction rules generated by means of automated learning techniques such as inductive logic programming, statistical methods, and inductive grammars. These rules set up a generic algorithm to extract information from similar pages automatically. Boosted techniques [10] are proposed to improve the performance of the machine learning algorithm by repeatedly applying it to a training set with different example weightings. Although induction wrappers are suited to extract information from the web, they do not associate semantics with the data extracted, this being their major drawback [2]. Thus, we call current inductive wrappers syntactic because they extract syntactic information devoid of semantic formalisation that expresses its meaning. Our solution builds on the best of current inductive wrappers, and extends them with techniques that allow us to deal with web knowledge. Using inductive wrappers allows us take advantage of all the work developed in this arena, as boosted techniques or verification algorithms [15,19] that detect if there are changes in the layout of a web page that invalidate the wrapper. 3 Preliminaries 3.1 A Case Study We illustrate the problem to solve by means of a simple, real example in which we are interested in extracting information about the score of golfers in a PGA Championship. This information was given at http://www.golfweb.com. Figure 1 shows a web page from this site. Note that the implied meaning of the terms that appear in this page can be easily interpreted by humans, but there is not a reference to the concepts that describe them precisely, which complicates communication and interoperability amongst software applications [3,4]. 3.2 Dealing with Knowledge There are many formalisms to dealt with knowledge, namely: semantic networks [20], frames systems [18], logic, decision trees, and so on. Their aim is to represent ontologies, which are specifications of concepts and relationships amongst them in a concrete domain. Ontologies [7] allows us to specify the meaning of the concepts about which we are extracting information. Some authors [11,12] have specified a formal model for ontologies; our formalisation builds on the work by Heflin in his PhD dissertation [12]. Definition 1. Let Lbe a logical language; an ontology is a tuple (P,A), where P is a subset of the vocabulary of predicate symbols of Land A is a subset of Fig. 1. A web page with information about scores in a golf championship. well–formed formula in L(axioms). Thus, an ontology is a subset of Lin which concepts are specified by predicates and relationships amongst then are specified as a set of axioms. First–order languages (FOL) offer us the power and flexibility needed to describe knowledge. Many knowledge representation languages and structures can be formulated in first–order logic [12]. Then, we are able to use a wide range of knowledge representation formalisms; we only need to define a mechanism to translate from some formalism to FOL and vice versa. In Appendix A, we specify1some concepts related to logical languages that establish the basis of our model. In our proposal, a logical language (L) is characterized by a vocabulary of constant identifiers (Identc), a vocabulary of variable identifiers (Identv), a vocabulary of function identifiers (Identf), a vocabulary of predicate identifiers (Identp) and a (in)finite set of well–formed formulae (Wff ), which is a subset of the formulae derived from L. For the sake of simplicity, we assume that Identf=∅. Next schema specifies an ontology. Three constrains are imposed: the former states that Pand Aare non–empty subsets of the set of predicate symbols and well–formed formulae of L, respectively; the second, asserts that axioms are defined using the predicate symbols in P2; the latter asserts that the set of axioms is consistent. Predicate references a theorem prover; let be F:PWff , and f:Wff then Ffis satisfied if fis formally provable or derivable from F, 1In this paper we use notation Zas a formal specification language because it is an ISO standard [1], and an extremely expressive language. 2Function PredSyms is specified in Appendix A. It returns the set of predicate symbols in a formula. thus fbelongs to the set of all well–formed formulae that we can obtain from F (theory of F). Ontology P:PIdentp A:PWff P=∅∧A=∅ ∀f:A•PredSyms(f)⊆P ¬∃g:Wff •Ag∧A¬g Definition 2. An instance of a concept, specified in an ontology, is an interpretation of this concept over some domain. In information extraction, this domain is established by the information to be extracted. We model instances as ground predicate atoms. Thus, they are well–formed formula. We specify the set of all instances that we can derive from an ontology by the function GroundPredicateAtoms: GroundPredicateAtoms :Ontology →PWff ∀o:Ontology •GroundPredicateAtoms(o)= {f:Wff ;ip :Identp;sc : seq1Term;ic :Identc| (f=atom(pred (ip,sc)) ∧ ∀c:Term |c∈sc •c=const(ic)∧ PredSyms(f)⊆o.P)•f} Definition 3. AKnowledge Base (KB) is a tuple (O,K), where O is an ontology and K a set of instances of concepts specified in O. A KB is specified as follows: KB O:Ontology K:PWff ∀f:K•PredSyms(f)⊆O.P K∈GroundPredicateAtoms(O) The constrains imposed assert that the instances are formed with predicates defined in the ontology and they are ground predicate atoms. Example 1. The following object defines a KB in the domain of a golf championship in which we were interested in modelling knowledge about the position and score of golfers in a PGA championship (for the sake of readability, we do not use the abstract syntax in Appendix A. The mapping between this syntax and the usual logic symbols is straightforward): KB0=| O| P{Person,Golfer,Score,Position}, A{∀x•Golfer(x)⇒Person(x), ∀x•∃y•Golfer(x)⇒Score(x,y), ∀x•∃y•Golfer(x)⇒Position(x,y)}|, K{Golfer(Rich Beem),Score(Rich Beem,278), Position(Rich Beem,1)}| The ontology has four predicate symbols called Person,Golfer,Score and Position; the first axiom asserts that every Golfer isaPerson; the second one states that every Golfer has a Score, where yrepresents the total number of points obtained; the last one asserts that every Golfer has a Position y in the championship. The instances in KB0can be interpreted using the ontology, and they asserts that Rich Beem is a golfer, and he is the first in the ranking with 278 points. 4 Our Proposal Our proposal is a framework agent developers can use to extract information with semantics from non–annotated web pages, so that this procedure can be clearly separated from the rest in an attempt to reduce development costs and improve maintainability. This frameworks gives the mechanisms to develop core web agents called knowledge channels. Figure 2 illustrate this idea. KB KC WEB Agent Society Fig. 2. Knowledge Channels. A KC is responsible for managing a local knowledge base (KB). This knowledge is extracted from a web site using semantic wrappers. KCs answer also inquiries from other agents that need some knowledge to accomplish their goals. 4.1 Knowledge Extraction A semantic wrapper is an extension to current syntactic wrappers, as shown in Figure 3. Thus, we first need to define such wrappers formally. Definition 4. Asyntactic wrapper is a function that takes a web page as input, and returns structured information. Web page Syntactic Wrapper Extracted Information Semantic Translator Knowledge Semantic Wrapper K Fig. 3. A semantic wrapper. Next schema specifies a syntactic wrapper: [String,WebPage] Datum == PString Data == seq Datum Information == PData Wrapper :WebPage → Information dom Wrapper =∅ A syntactic wrapper is modelled as a partial function because its domain is a subset of web pages. This subset defines the scope of the wrapper, and it references the web pages in which the wrapper can be used. The output is modelled as data type Information, which is a set of data type Data.Data is sequence of Datum, it allows us to have a structured vision of the data to be extracted and to set a location for each datum. Data type Datum represents facts, and it is specified as a set of strings; this allows us to deal with multi–valuated attributes (attributes that can have 0 or more values). Example 2. If we were interested in extracting information about the position and score of golfers in a PGA championship, a syntactic wrapper would output the following Information from the web page in Figure 1: {{Rich Beem},{278},{1},{Tiger Woods},{279},{2}, {Chris Riley},{283},{3},...} Definition 5. Asemantic wrapper is a function that takes a web page as input, and returns a set of instances of concepts defined in an ontology that represents the information of interest. A semantic wrapper is composed of a syntactic wrapper and a semantic translator. In order to extract knowledge from the web, it is necessary to feed the semantic wrapper with the web page that contains the information. The syntactic wrapper extracts the structured information from that web page, and the semantic translator assigns then meaning to it by means of an ontology. SemanticWrapper :WebPage → PWff ∀p:WebPage |p∈dom Wrapper •SemanticWrapper(p)= SemanticTranslator(Wrapper(p)) The semantic translator needs the user to specify a semantic description that relates the information to be extracted with the predicates defined in the ontology to perform this task. Definition 6. Asemantic description (SD) is a representation of the relationships that hold amongst the symbols of predicates from an ontology and the positions that their arguments occupy in an Information structure. Thus, each predicate P is associated with n natural numbers, where n is the arity of P. An SD is modelled using the following schema, which is composed of three elements: an ontology (O), a set of predicate symbols (Sp3) and a function (Pos) that maps predicate symbols onto the location of Datum in Data belonging to the Information structure. This scheme also asserts that Spis a subset of the set of predicates symbols in O, and the domain of Pos is a subset of the symbols in Sp. SemanticDescription O:Ontology Sp:PIdentp Pos :Identp→ seq1N Sp⊆O.P∧dom Pos =Sp Example 3. In our study case, we can define the following semantic description: | O;o0,Sp;{Golfer,Score,Position}, Pos ;{Golfer →1,Score →1,2,Position →1,3} | In this SD, predicate Golfer takes constant values from location Pos(Golfer)of each Data (sequence) in an Information structure, In this case, the first position of the sequence. Predicate Score takes its values from Pos(Score)=1,24, and so on. Thus, it is posible to generate automatically well-formed formula that express the meaning of the information for all the Data elements in an Information structure extracted. Definition 7. Asemantic translator is a function that receives the Information structure obtained using a syntactic wrapper as input and uses a semantic description specified by the user, and outputs a set of instances. SemanticTranslator :Information → PWff sd :SemanticDescription ∀i:Information |i∈ran Wrapper • SemanticTranslator(i)=∪{d:Data |d∈i•buildWffs(d)} 3We might not need to use all the predicate defined in the ontology to give meaning to the information extracted. 4The arguments in a predicate follows a strict order. Using a sequence allows us to get arguments orderly. For instance, If Pos(Score) were 2,1, the result would be erroneous: Score(278,Tiger Woods) states that the score of 278 is Tiger Woods. Function buildWffs returns the set of well formed formula for each data in an Information structure. It is defined as follows5: buildWffs :Data → PWff ∀e:Data;t:P(Identp×Data)|e∈∪ranWrapper ∧ t={x:sd.Sp•(x,e{n: ran Pos(x)•e(n)})}• buildWffs(e)=∪{k:t•BuildPredicates(k)} The function BuildPredicates is specified as follows: BuildPredicates :Identp×seq PIdentc→PWff ∀ip :Identp;ssc : seq PIdentc• BuildPredicates(ip,ssc)={si : seq Identc;n:N| n∈1..#ssc ∧si(n)∈ssc(n)•atom(pred (ip,si))} It takes a pair composed of an identifier of predicate and a sequence of strings sets from an Information structure, and returns a set of predicates. The predicates are composed using the identifier of predicate and each element of the sequence. Example 4. The following instances represent the knowledge extracted by a semantic wrapper from the web page in Figure 1: {atom(pred (Golfer,const(Rich Beem))), atom(pred (Score,const(Rich Beem),const(278))), atom(pred (Position,const(Rich Beem),const(1))), atom(pred (Golfer,const(Tiger Woods))), atom(pred (Score,const(Tiger Woods),const(279))), atom(pred (Position,const(Tiger Woods),const(2))), atom(pred (Golfer,const(Chris Riley))), atom(pred (Score,const(Chris Riley),const(283))), atom(pred (Position,const(Chris Riley),const(3))),...} 4.2 A Model for KCs The schema bellow formalises a KC. It has a declarative part containing two variables; the former (SW ) references the semantic wrapper to be used, and the latter (SV ) the semantic verifier. KnowledgeChannel SW :SemanticWrapper SV :SemanticVerificator 5The filtering operator () takes from a sequence the elements in a set. For instance: jun,nov,feb,jul{sep,oct ,nov,dec,jan,feb,mar,apr}=nov,feb