Coping wi h Web Knowledge
J.L. A jona, R. Co chuelo, J. Pe˜na, and D. Ruiz
The Dis ibu ed G oup
A da. de la Reina Me cedes, s/n, Se illa (Spain)
{a jona,co chuelo,joaquinp, d uiz}@lsi.us.es
Abs ac . The web seems o be he bigges exis ing in o ma ion eposi-
o y. The ex ac ion o in o ma ion om his eposi o y has a ac ed he
in e es o many esea che s, who ha e de eloped in elligen algo i hms
(w appe s) able o ex ac s uc u ed syn ac ic in o ma ion au oma i-
cally.
In his a icle, we o malise a new solu ion in o de o ex ac knowledge
om oday’s non-seman ic web. I is no el in ha i associa es seman ics
wi h he in o ma ion ex ac ed, which imp o es agen in e ope abili y;
u he mo e, i achie es o delega e he knowledge ex ac ion p ocedu e
o specialis agen s, easing so wa e de elopmen and p omo ing so wa e
euse and main ainabili y.
Keywo ds: knowledge ex ac ion, w appe s, web agen s and on-
ologies
1 In oduc ion
In ecen yea s, he web has consolida ed as one o he mos impo an knowl-
edge eposi o ies. Fu he mo e, he echnology has e ol ed o a poin in which
sophis ica ed new gene a ion web agen s p oli e a e. A majo challenge o hem
has become si ing h ough an unwieldy amoun o da a o ex ac meaning-
ul in o ma ion. This p ocess is difficul because he in o ma ion on he web is
mos ly a ailable in human- eadable o ms ha lack o malised seman ics ha
would help agen s use i .
The Seman ic Web is “an ex ension o he cu en web in which in o ma ion
is gi en well–defined meaning, be e enabling compu e s and people o wo k in
coope a ion” [3], which implies a ansi ion om oday’s web o a web in which
machine easoning will be ubiqui ous and de as a ingly powe ul. This ansi ion
is achie ed by anno a ing web pages wi h me a–da a ha desc ibe he concep s
ha define he seman ics associa ed wi h he in o ma ion in which we a e in-
e es ed. On ologies play an impo an ole in his ask, and he e a e many
on ological languages ha aim a sol ing his p oblem, e.g., DAML+OIL [13],
SHOE [17] o RDF-Schema [5]. The Seman ic Web shall simpli y and imp o e
The wo k epo ed in his a icle was suppo ed by he Spanish In e minis e ial
Commission on Science and Technology unde g an s TIC2000-1106-C02-01 and
FIT-150100-2001-78.
he accu acy o cu en in o ma ion ex ac ion echniques emendously. Ne -
e heless, his ex ension equi es a g ea deal o effo o anno a e cu en web
pages wi h seman ics, which sugges s ha i is no likely o be adop ed in he
immedia e u u e [9].
Se e al au ho s ha e wo ked on echniques o ex ac ing in o ma ion om
oday’s non-seman ic web, and induc i e w appe s a e amongs he mos pop-
ula ones [6,14,15,16,19]. They a e componen s ha use au oma ed lea ning
echniques o ex ac in o ma ion om simila pages au oma ically. Al hough
induc ion w appe s a e sui ed o ex ac in o ma ion om he web, hey do no
associa e seman ics wi h he da a ex ac ed, his being hei majo d awback.
Fu he mo e, adding hese algo i hms o logic ha a web agen encapsula es,
can p oduce angled code and does no achie e a clea sepa a ion o conce ns.
In his a icle, we p esen a new solu ion in o de o ex ac seman ically-
meaning ul in o ma ion om oday’s non-seman ic web. I is no el in ha i
associa es seman ics wi h he in o ma ion ex ac ed, which imp o es agen in-
e ope abili y, and i delega es he knowledge ex ac ion p ocedu e o specialis
agen s, easing so wa e de elopmen and p omo ing so wa e euse and main-
ainabili y.
We add ess hese issues by de eloping knowledge channels, o KCs o sho .
They a e agen s [21] ha allow o sepa a e he ex ac ion o knowledge om he
logic o an agen , and hey a e able o eac o knowledge inqui ies ( eac i i y)
om o he agen s (social abili y), and ac in he backg ound (au onomy) o
main ain a local knowledge base (KB) wi h knowledge ex ac ed om a web si e
(p oac i i y). In o de o allow o seman ic in e ope abili y, he knowledge hey
manage e e ences a numbe o concep s in a gi en applica ion domain ha a e
desc ibed by means o on ologies. KCs ex ac knowledge om he web using
seman ic w appe s, which a e a na u al ex ension o cu en induc i e w appe s
o deal wi h knowledge on he web. Thus, we ake ad an age o he wo k made
by esea che s in he syn ac ic w appe s a ena.
The es o he pape is o ganised as ollows: Nex sec ion glances a o he
p oposals and mo i a es he need o solu ions o sol e he p oblems behind
knowledge ex ac ion; Sec ion 3 p esen s he case s udy used o illus a e ou
p oposal and some ini ial concep s ela ed o knowledge ep esen a ion; Sec ion
4 gi es he eade an insigh in o ou p oposal; finally, Sec ion 5 summa ises ou
main conclusions.
2 Rela ed Wo k
W appe s [8] a e one o he he mos popula mechanisms o ex ac ing in o -
ma ion om he web. Gene ally, a w appe is an algo i hm ha ansla es he
in o ma ion ep esen ed in model M1 o model M2. In in o ma ion ex ac ion,
hey a e able o ansla e he in o ma ion in a web page o a da a s uc u e ha
can be used by so wa e applica ions.
In he beginning, hese algo i hms we e codified manually, using some p op-
e ies o a web page, no mally looking o s ings ha delimi he da a ha we
need o ex ac . Bu hand-coded w appe s a e e o –p one, edious, cos ly and
ime–consuming o build and main ain. An impo an con ibu ion o his field
was p o ided by Kushme ick [15]. He in oduced induc ion echniques o define
a new class o w appe s called induc i e w appe s. These induc i e algo i hms
a e componen s ha use a numbe o ex ac ion ules gene a ed by means o
au oma ed lea ning echniques such as induc i e logic p og amming, s a is ical
me hods, and induc i e g amma s. These ules se up a gene ic algo i hm o
ex ac in o ma ion om simila pages au oma ically. Boos ed echniques [10]
a e p oposed o imp o e he pe o mance o he machine lea ning algo i hm by
epea edly applying i o a aining se wi h diffe en example weigh ings.
Al hough induc ion w appe s a e sui ed o ex ac in o ma ion om he web,
hey do no associa e seman ics wi h he da a ex ac ed, his being hei majo
d awback [2]. Thus, we call cu en induc i e w appe s syn ac ic because hey
ex ac syn ac ic in o ma ion de oid o seman ic o malisa ion ha exp esses i s
meaning.
Ou solu ion builds on he bes o cu en induc i e w appe s, and ex ends
hem wi h echniques ha allow us o deal wi h web knowledge. Using induc i e
w appe s allows us ake ad an age o all he wo k de eloped in his a ena, as
boos ed echniques o e ifica ion algo i hms [15,19] ha de ec i he e a e
changes in he layou o a web page ha in alida e he w appe .
3 P elimina ies
3.1 A Case S udy
We illus a e he p oblem o sol e by means o a simple, eal example in which
we a e in e es ed in ex ac ing in o ma ion abou he sco e o gol e s in a PGA
Championship. This in o ma ion was gi en a h p://www.gol web.com. Figu e 1
shows a web page om his si e.
No e ha he implied meaning o he e ms ha appea in his page can be
easily in e p e ed by humans, bu he e is no a e e ence o he concep s ha
desc ibe hem p ecisely, which complica es communica ion and in e ope abili y
amongs so wa e applica ions [3,4].
3.2 Dealing wi h Knowledge
The e a e many o malisms o deal wi h knowledge, namely: seman ic ne wo ks
[20], ames sys ems [18], logic, decision ees, and so on. Thei aim is o ep esen
on ologies, which a e specifica ions o concep s and ela ionships amongs hem
in a conc e e domain. On ologies [7] allows us o speci y he meaning o he
concep s abou which we a e ex ac ing in o ma ion. Some au ho s [11,12] ha e
specified a o mal model o on ologies; ou o malisa ion builds on he wo k by
Heflin in his PhD disse a ion [12].
Defini ion 1. Le Lbe a logical language; an on ology is a uple (P,A), whe e
P is a subse o he ocabula y o p edica e symbols o Land A is a subse o
Fig. 1. A web page wi h in o ma ion abou sco es in a gol championship.
well– o med o mula in L(axioms). Thus, an on ology is a subse o Lin which
concep s a e specified by p edica es and ela ionships amongs hen a e specified
as a se o axioms.
Fi s –o de languages (FOL) offe us he powe and flexibili y needed o
desc ibe knowledge. Many knowledge ep esen a ion languages and s uc u es
can be o mula ed in fi s –o de logic [12]. Then, we a e able o use a wide ange
o knowledge ep esen a ion o malisms; we only need o define a mechanism o
ansla e om some o malism o FOL and ice e sa.
In Appendix A, we speci y1some concep s ela ed o logical languages ha
es ablish he basis o ou model. In ou p oposal, a logical language (L) is cha ac-
e ized by a ocabula y o cons an iden ifie s (Iden c), a ocabula y o a iable
iden ifie s (Iden ), a ocabula y o unc ion iden ifie s (Iden ), a ocabula y o
p edica e iden ifie s (Iden p) and a (in)fini e se o well– o med o mulae (Wff ),
which is a subse o he o mulae de i ed om L. Fo he sake o simplici y, we
assume ha Iden =∅.
Nex schema specifies an on ology. Th ee cons ains a e imposed: he o me
s a es ha Pand Aa e non–emp y subse s o he se o p edica e symbols
and well– o med o mulae o L, espec i ely; he second, asse s ha axioms
a e defined using he p edica e symbols in P2; he la e asse s ha he se o
axioms is consis en . P edica e  e e ences a heo em p o e ; le be F:PWff ,
and :Wff hen F is sa isfied i is o mally p o able o de i able om F,
1In his pape we use no a ion Zas a o mal specifica ion language because i is an
ISO s anda d [1], and an ex emely exp essi e language.
2Func ion P edSyms is specified in Appendix A. I e u ns he se o p edica e symbols
in a o mula.
hus belongs o he se o all well– o med o mulae ha we can ob ain om F
( heo y o F).
On ology
P:PIden p
A:PWff
P=∅∧A=∅
∀ :A•P edSyms( )⊆P
¬∃g:Wff •Ag∧A¬g
Defini ion 2. An ins ance o a concep , specified in an on ology, is an in-
e p e a ion o his concep o e some domain. In in o ma ion ex ac ion, his
domain is es ablished by he in o ma ion o be ex ac ed.
We model ins ances as g ound p edica e a oms. Thus, hey a e well– o med
o mula. We speci y he se o all ins ances ha we can de i e om an on ology
by he unc ion G oundP edica eA oms:
G oundP edica eA oms :On ology →PWff
∀o:On ology •G oundP edica eA oms(o)=
{ :Wff ;ip :Iden p;sc : seq1Te m;ic :Iden c|
( =a om(p ed (ip,sc)) ∧
∀c:Te m |c∈sc •c=cons (ic)∧
P edSyms( )⊆o.P)• }
Defini ion 3. AKnowledge Base (KB) is a uple (O,K), whe e O is an
on ology and K a se o ins ances o concep s specified in O.
A KB is specified as ollows:
KB
O:On ology
K:PWff
∀ :K•P edSyms( )⊆O.P
K∈G oundP edica eA oms(O)
The cons ains imposed asse ha he ins ances a e o med wi h p edica es
defined in he on ology and hey a e g ound p edica e a oms.
Example 1. The ollowing objec defines a KB in he domain o a gol champi-
onship in which we we e in e es ed in modelling knowledge abou he posi ion
and sco e o gol e s in a PGA championship ( o he sake o eadabili y, we do
no use he abs ac syn ax in Appendix A. The mapping be ween his syn ax
and he usual logic symbols is s aigh o wa d):

KB0=| O| P{Pe son,Gol e ,Sco e,Posi ion},
A{∀x•Gol e (x)⇒Pe son(x),
∀x•∃y•Gol e (x)⇒Sco e(x,y),
∀x•∃y•Gol e (x)⇒Posi ion(x,y)}|,
K{Gol e (Rich Beem),Sco e(Rich Beem,278),
Posi ion(Rich Beem,1)}|
The on ology has ou p edica e symbols called Pe son,Gol e ,Sco e and
Posi ion; he fi s axiom asse s ha e e y Gol e isaPe son; he second one
s a es ha e e y Gol e has a Sco e, whe e y ep esen s he o al numbe o
poin s ob ained; he las one asse s ha e e y Gol e has a Posi ion y in he
championship. The ins ances in KB0can be in e p e ed using he on ology, and
hey asse s ha Rich Beem is a gol e , and he is he fi s in he anking wi h
278 poin s.
4 Ou P oposal
Ou p oposal is a amewo k agen de elope s can use o ex ac in o ma ion
wi h seman ics om non–anno a ed web pages, so ha his p ocedu e can be
clea ly sepa a ed om he es in an a emp o educe de elopmen cos s and
imp o e main ainabili y. This amewo ks gi es he mechanisms o de elop co e
web agen s called knowledge channels. Figu e 2 illus a e his idea.
KB
KC
WEB
Agen Socie y
Fig. 2. Knowledge Channels.
A KC is esponsible o managing a local knowledge base (KB). This knowl-
edge is ex ac ed om a web si e using seman ic w appe s. KCs answe also
inqui ies om o he agen s ha need some knowledge o accomplish hei goals.
4.1 Knowledge Ex ac ion
A seman ic w appe is an ex ension o cu en syn ac ic w appe s, as shown in
Figu e 3. Thus, we fi s need o define such w appe s o mally.
Defini ion 4. Asyn ac ic w appe is a unc ion ha akes a web page as
inpu , and e u ns s uc u ed in o ma ion.
Web
page
Syn ac ic
W appe Ex ac ed
In o ma ion
Seman ic
T ansla o
Knowledge
Seman ic W appe
K
Fig. 3. A seman ic w appe .
Nex schema specifies a syn ac ic w appe :
[S ing,WebPage]
Da um == PS ing
Da a == seq Da um
In o ma ion == PDa a
W appe :WebPage → In o ma ion
dom W appe =∅
A syn ac ic w appe is modelled as a pa ial unc ion because i s domain is a
subse o web pages. This subse defines he scope o he w appe , and i e e -
ences he web pages in which he w appe can be used. The ou pu is modelled
as da a ype In o ma ion, which is a se o da a ype Da a.Da a is sequence o
Da um, i allows us o ha e a s uc u ed ision o he da a o be ex ac ed and
o se a loca ion o each da um. Da a ype Da um ep esen s ac s, and i is
specified as a se o s ings; his allows us o deal wi h mul i– alua ed a ibu es
(a ibu es ha can ha e 0 o mo e alues).
Example 2. I we we e in e es ed in ex ac ing in o ma ion abou he posi ion
and sco e o gol e s in a PGA championship, a syn ac ic w appe would ou pu
he ollowing In o ma ion om he web page in Figu e 1:
{{Rich Beem},{278},{1},{Tige Woods},{279},{2},
{Ch is Riley},{283},{3},...}
Defini ion 5. Aseman ic w appe is a unc ion ha akes a web page as
inpu , and e u ns a se o ins ances o concep s defined in an on ology ha
ep esen s he in o ma ion o in e es .
A seman ic w appe is composed o a syn ac ic w appe and a seman ic
ansla o . In o de o ex ac knowledge om he web, i is necessa y o eed
he seman ic w appe wi h he web page ha con ains he in o ma ion. The
syn ac ic w appe ex ac s he s uc u ed in o ma ion om ha web page, and
he seman ic ansla o assigns hen meaning o i by means o an on ology.
Seman icW appe :WebPage → PWff
∀p:WebPage |p∈dom W appe •Seman icW appe (p)=
Seman icT ansla o (W appe (p))
The seman ic ansla o needs he use o speci y a seman ic desc ip ion ha e-
la es he in o ma ion o be ex ac ed wi h he p edica es defined in he on ology
o pe o m his ask.
Defini ion 6. Aseman ic desc ip ion (SD) is a ep esen a ion o he ela-
ionships ha hold amongs he symbols o p edica es om an on ology and he
posi ions ha hei a gumen s occupy in an In o ma ion s uc u e. Thus, each
p edica e P is associa ed wi h n na u al numbe s, whe e n is he a i y o P.
An SD is modelled using he ollowing schema, which is composed o h ee
elemen s: an on ology (O), a se o p edica e symbols (Sp3) and a unc ion (Pos)
ha maps p edica e symbols on o he loca ion o Da um in Da a belonging o
he In o ma ion s uc u e. This scheme also asse s ha Spis a subse o he se
o p edica es symbols in O, and he domain o Pos is a subse o he symbols in
Sp.
Seman icDesc ip ion
O:On ology
Sp:PIden p
Pos :Iden p→ seq1N
Sp⊆O.P∧dom Pos =Sp
Example 3. In ou s udy case, we can define he ollowing seman ic desc ip ion:
| O;o0,Sp;{Gol e ,Sco e,Posi ion},
Pos ;{Gol e →1,Sco e →1,2,Posi ion →1,3} |
In his SD, p edica e Gol e akes cons an alues om loca ion Pos(Gol e )o
each Da a (sequence) in an In o ma ion s uc u e, In his case, he fi s posi ion
o he sequence. P edica e Sco e akes i s alues om Pos(Sco e)=1,24,
and so on. Thus, i is posible o gene a e au oma ically well- o med o mula
ha exp ess he meaning o he in o ma ion o all he Da a elemen s in an
In o ma ion s uc u e ex ac ed.
Defini ion 7. Aseman ic ansla o is a unc ion ha ecei es he In o ma-
ion s uc u e ob ained using a syn ac ic w appe as inpu and uses a seman ic
desc ip ion specified by he use , and ou pu s a se o ins ances.
Seman icT ansla o :In o ma ion → PWff
sd :Seman icDesc ip ion
∀i:In o ma ion |i∈ an W appe •
Seman icT ansla o (i)=∪{d:Da a |d∈i•buildWffs(d)}
3We migh no need o use all he p edica e defined in he on ology o gi e meaning
o he in o ma ion ex ac ed.
4The a gumen s in a p edica e ollows a s ic o de . Using a sequence allows us o
ge a gumen s o de ly. Fo ins ance, I Pos(Sco e) we e 2,1, he esul would be
e oneous: Sco e(278,Tige Woods) s a es ha he sco e o 278 is Tige Woods.
Func ion buildWffs e u ns he se o well o med o mula o each da a in an
In o ma ion s uc u e. I is defined as ollows5:
buildWffs :Da a → PWff
∀e:Da a; :P(Iden p×Da a)|e∈∪ anW appe ∧
={x:sd.Sp•(x,e{n: an Pos(x)•e(n)})}•
buildWffs(e)=∪{k: •BuildP edica es(k)}
The unc ion BuildP edica es is specified as ollows:
BuildP edica es :Iden p×seq PIden c→PWff
∀ip :Iden p;ssc : seq PIden c•
BuildP edica es(ip,ssc)={si : seq Iden c;n:N|
n∈1..#ssc ∧si(n)∈ssc(n)•a om(p ed (ip,si))}
I akes a pai composed o an iden ifie o p edica e and a sequence o s ings se s
om an In o ma ion s uc u e, and e u ns a se o p edica es. The p edica es
a e composed using he iden ifie o p edica e and each elemen o he sequence.
Example 4. The ollowing ins ances ep esen he knowledge ex ac ed by a se-
man ic w appe om he web page in Figu e 1:
{a om(p ed (Gol e ,cons (Rich Beem))),
a om(p ed (Sco e,cons (Rich Beem),cons (278))),
a om(p ed (Posi ion,cons (Rich Beem),cons (1))),
a om(p ed (Gol e ,cons (Tige Woods))),
a om(p ed (Sco e,cons (Tige Woods),cons (279))),
a om(p ed (Posi ion,cons (Tige Woods),cons (2))),
a om(p ed (Gol e ,cons (Ch is Riley))),
a om(p ed (Sco e,cons (Ch is Riley),cons (283))),
a om(p ed (Posi ion,cons (Ch is Riley),cons (3))),...}
4.2 A Model o KCs
The schema bellow o malises a KC. I has a decla a i e pa con aining wo
a iables; he o me (SW ) e e ences he seman ic w appe o be used, and he
la e (SV ) he seman ic e ifie .
KnowledgeChannel
SW :Seman icW appe
SV :Seman icVe ifica o
5The fil e ing ope a o () akes om a sequence he elemen s in a se . Fo ins ance:
jun,no , eb,jul{sep,oc ,no ,dec,jan, eb,ma ,ap }=no , eb