Con idence-Based Reasoning wi h Local
Tempo al Fo mal Con ex s
Gonzalo A. A anda-Co al1, Joaqu´ın Bo ego D´ıaz2,andJuanGal´an P´aez2
1Uni e sidad de Huel a, Depa men o In o ma ion Technology,
C a. Palos de La F on e a s/n. 21819 Palos de La F on e a, Spain
2Uni e sidad de Se illa, Depa men o Compu e Science and A i icial In elligence,
A da. Reina Me cedes s/n. 41012 Se illa, Spain
Abs ac . Fo mal Concep Analysis (FCA) is a heo y whose goal is
o disco e and o ex ac Knowledge om quali a i e da a. I p o ides
ools o easoning wi h implica ion basis (and associa ion ules). In his
pape we analyse how o apply FCA easoning o inc ease con idence in
spo s be ing, by means o de ec ing empo al egula i ies om da a. I
is applied o build a Knowledge based sys em o con idence easoning.
1 In oduc ion
Con ex modelling and easoning ep esen s a majo pa adigm in A ificial In-
elligence (AI). I is a use ul app oach o p agma ic and ealis ic easoning in
AI. An in e es ing issue in some ypes o con ex easoning p oblems is Know-
ledge’s empo al dimension. Knowledge Bases (KB), o da abases, may con ain
in o ma ion om empo al s amps, bounds o du a ion. The co ec ness o ea-
soning wi h hem depends on a sound selec ion o ime-dependen da a (among
o he ea u es) ha will be used in each con ex . I ep esen s a p oblem in da a
mining, pa icula ly o easoning wi h associa ion ules, hinking on hem as
implica ions wi h no exac confidence.
Fo mal Concep Analysis (FCA) [8] is a ma hema ical heo y o da a analysis
using o mal con ex s and concep la ices as key ools. Domains can be o mally
modelled acco ding o he ex en and he in en o each o mal concep . In FCA,
he basic da a s uc u e is a o mal con ex (wi h a quali a i e na u e) which
ep esen s a se o objec s and hei p ope ies and i is use ul bo h o de ec
and o desc ibe egula i ies and s uc u es o concep s. I also p o ides a sound
o malism o easoning wi h such s uc u es, mainly S em Basis and associa ion
ules. The e o e, i is in e es ing o conside i s applica ion o easoning wi h
empo al quali a i e da a (see e.g. [14]) in o de o disco e empo al ends.
In his pape , FCA applica ion scope is he challenge o spo s be ing, speci -
ically, he o ecas ing o socce league’s esul s. Fo ecas ing spo esul s is a as
Pa ially suppo ed by TIN2009-09492 p ojec (Spanish Minis y o Science and
Inno a ion), co inanced wi h FEDER ounds and P oyec o de excelencia TIC-6064
o Jun a de Andaluc´ıa.
g owing esea ch a ea, because o i s economic impac in be ing ma ke s as well
as o i s po en ial applica ion o p oblems wi h simila beha iou (ma ke s) [1].
Roughly speaking, h ee dimensions ha e been conside ed o analysing/syn-
hesizing p edic ion sys ems: 1)Those which analyse in o ma ion on eams (en-
dogenous) e sus hose which analyse esul s (exogenous); 2)Those which exploi
quan i a i e da a e sus hose which exploi quali a i e knowledge, and finally,
3)S a is ic-based ones e sus o he me hods. Usually, one can wo k wi h hy-
b id models, and a ely wi h pu e quali a i e and exogenous easoning sys ems
appea in li e a u e, al hough hei use is conside ed o expe imen s ( o exam-
ple, ugal me hods [3] and based on he ecogni ion heu is ic [10]) o as pa o
hyb id sys ems (see e.g. [13]). The e a e wo easons ha may jus i y his poin .
On he one hand, ans o ma ion om a la ge quan i a i e da ase o a
quali a i e p oblem is aced wi h he selec ion o an accep able h eshold and
he disco e y o be e ela ions (see e.g. [12]). On he o he hand, a quali a-
i e da ase mus be accomplished wi h some amoun o in o ma ion based on
confidence, us o p obabili y o hese da a se s.
The aim o his pape is o p esen a me hod o FCA easoning on con ex s
wi h empo al dimensions ha allows he de ec ion o some kind o egula i y in
da a ocusing on esul s om he Spanish socce league as he sou ce o empo al
quali a i e in o ma ion. The me hod is be -o ien ed and i s pe o mance is e a-
lua ed wi hin a confidence-based easoning sys em ha inc eases he numbe o
hi s in socce ma ches o ecas ing by using he disco e y o empo al ends on
da a mining and associa ion ules easoning.
The s uc u e o he pape is as ollows. The nex sec ion e iews he main
ea u es o FCA and associa ion ules on o mal con ex s. Tempo al o mal con-
ex s a e defined in Sec . 3. The confidence-based easoning sys em is desc ibed
in Sec . 4, and some commen s on expe imen a ion a e discussed in Sec . 5.
Sec ion 6 is de o ed o desc ibe u u e wo k.
2 Fo mal Concep Analysis
Acco ding R. Wille, FCA ma hema izes he philosophical unde s anding o a
concep as a uni o hough s composed o wo pa s: he ex en and he in en
[8]. The ex en co e s all objec s belonging o his concep , while he in en
comp ises o all common a ibu es alid o all he objec s unde conside a ion.
I also allows he compu a ion o concep hie a chies om da a ables. In his
sec ion, we succinc ly p esen basic FCA elemen s, al hough i is assumed ha
he eade is amilia wi h his heo y ( he undamen al e e ence is [8]).
We ep esen a o mal con ex as M=(O,A, I), which consis s o wo se s,
O(objec s) and A(a ibu es) and a ela ion I⊆O×A. Fini e con ex s can
be ep esen ed by a 1-0- able ( ep esen ing I as a Boolean unc ion on O×A).
The FCA main goal is he compu a ion o he concep la ice associa ed o he
con ex . In his pape i wo ks wi h logical ela ions on a ibu es which a e
alid in he con ex . Fo X⊆Oand Y⊆Awe can define
X:= {a∈A|oIa o all o∈X}Y:= {o∈O|oIa o all a∈Y}
Logical exp essions in FCA a e implica ions be ween a ibu es,pai o se so
a ibu es, w i en as Y1→Y2, which is ue wi h espec o M=(O,A, I)
acco ding o he ollowing defini ion. A subse T⊆A espec s Y1→Y2i Y1⊆ T
o Y2⊆T.I says ha Y1→Y2holds in M(M|=Y1→Y2) i o all o∈O, he
se {o} espec s Y1→Y2.In ha case,Y1→Y2is an implica ion o M.
De ini ion 1. Le Lbe a se o implica ions and Lan implica ion o M.
1. L ollows om L(L|=L)i eachsubse o A espec ing Lalso espec s L.
2. Lis comple e i e e y implica ion o he con ex ollows om L.
3. Lis non- edundan i o each L∈L,L {L} |=L.
4. I Lis a basis o Mis comple e and non- edundan .
I can ob ain a basis om he pseudo-in en s [11] called S em basis:
L={Y→Y :Yis a pseudoin en }
The so-called A ms ong ules p o ides an implica ional easoning:
R1:X→XR2: X→Y
X∪Z→YR3:X→Y, Y ∪Z→W
X∪Z→W
Le Abe he p oo ela ion by A ms ong ules. I holds ha implica ional bases
a e A-comple e [6]: I Lis a implica ional basis o M,andLan implica ion,
hen M|=Li and only i L
AL.
In o de o wo k wi h o mal con ex s, s em basis and associa ion ules, he
Conexp1so wa e has been selec ed. I has been used as a lib a y o build he
module which p o ides implica ions (and associa ion ules) o he easoning
module. This module is a p oduc ion sys em based on which was designed o
[4]. I wo ks wi h S em Basis, and en ailmen is based on he ollowing esul .
Theo em 1. Le Sbe a s em basis associa ed wi h he con ex M,oanew
documen agged wi h A1,...,A
n. The ollowing condi ions a e equi alen :
1. S∪{A1,...A
n}
pY(pis he en ailmen om he p oduc ion sys em).
2. SAA1,...A
n→Y
3. M|={A1,...A
n}→Y.
We can conside a S em Basis as an adequa e p oduc ion sys em in o de o
eason and p edic esul s. Howe e , S em Basis is designed o en ailing ue
implica ions only, wi hou any excep ions in o he objec se no implica ions
wi h a low numbe o coun e examples in he con ex . Ano he mo e impo an
ques ion is abou p edic ions, we a e in e es ed in ob aining some me hods o
selec ing a esul among all ob ained esul s (e en i hey a e mu ually inco-
he en ), and heo em 1 does no p o ide such a me hod. The e o e, i is be e
o conside ules wi h confidence ins ead o ue implica ions and he ini ial
p oduc ion sys em mus be e ised o wo king wi h confidence.
Resea ching on sound logical easoning me hods wi h associa ion ules is a
ela i ely ecen esea ch line wi h p omising applica ions [7]. In FCA, associa-
ion ules a e implica ions among se s o a ibu es. Confidence and suppo a e
1h p://sou ce o ge.ne /p ojec s/conexp/
defined as usual. Recall ha he suppo o X,supp(X), o a se o a ibu es X
is defined as he p opo ion o objec s which sa is y e e y a ibu e o X,and
he con idence o an associa ion ule is con (X⇒Y)=supp(X∪Y)/supp(X).
Confidence can be in e p e ed as an es ima e o he p obabili y P(Y|X), he
p obabili y o an objec sa is ying e e y a ibu e o Yunde he condi ion ha
i also sa isfies e e y one o X. Conexp so wa e p o ides he associa ion ules,
as well as, hei confidence o con ex s.
3 Da a and Tempo al Con ex s
A empo al con ex on a se o objec s is defined as ollows:
De ini ion 2. Le Obe a se o objec s.
1. A empo al con ex on Ois a con ex M=(O1,A,I)whe e O1⊆O×N
2. A con ex ual selec ion is a map s:O→P(O1)×P(A)
3. A con ex ual KB o an objec ow. . . a selec ion swi h con idence γ
is a subse o associa ion ules wi h con idence g ea e o equal ha γo he
o mal con ex associa ed o s(o)=(s1(o),s
2(o)), ha is, o he con ex
M(s(o)) := (s1(o),s
2(o),I
s1(o)×s2(o))
In his pape only se o associa ion ules ex ac ed by Conexp wi h confidence
g ea e han a h eshold γ o a con ex ual selec ion a e used as con ex ual KB.
3.1 Tempo al Con ex s o Socce League
Fo bo h selec ing da a and building con ex s, some assump ions on o ecas ing
in socce league ma ches ha e been conside ed. Reconside a ions o such deci-
sions can be easily compu ed in he sys em. Fi s , we conside ha he egula i y
o eam’s beha iou only depends on he con ex ual selec ion ha has been con-
side ed. This con ex ual selec ion is ob ained by aking ma ches om he las
Xweeks backwa ds, s a ing om he week jus be o e he one we wan o o e-
cas . Second, since FCA me hods a e used o disco e egula i y ea u es, hus
i does no conside o ecas ing excep ions (unexpec ed esul s). The e o e, he
model can be conside ed as a s a ing poin o be ing expe who would adjus
a ibu es, in o de o mo e pe sonalised c i e ia.
These a ibu es ha e o be compu ed andused oen ail he o ecas ing.This
analysis is assis ed by Conexp. ConExp so wa e is used o compu e and analyze
he concep la icces associa ed o he empo al con ex s. In his way, he expe
can e alua e he goodness o he a ibu es (and he h esholds defining hem)
(See Fig. 1). The a ibu e ID 1T16 is defined by: ’ he budge o eam2is
g ea e han γ1 imes he budge o eam1’, whe e γ1is he h eshold he expe
mus es ima e. In he concep la ice we can obse e ha he bigges concep
con aining he a ibu es eam2wins and ID 1T16 co e s he abou he 10%
o he objec s owned by he fi s a ibu e, he e o e i is sugges ed o use he
second a ibu e o easoning wi h associa ion ules o ge a p edic ion.
Fig. 1. Concep La ice o he ma ch M´alaga-Se illa (week 31, season 2009-10)
The sys em compu es he alue o an amoun o a ibu es on objec s. Ex-
pe imen ally a boolean combina ion o a ibu es is possible. Once he empo al
con ex has been compu ed, he sys em can build con ex ual selec ions by se-
lec ing he ma ch and he a ibu e se . The selec ion o a ibu es was made by
conside ing ou kinds o ac o s: hose ela ed wi h he classifica ion, he his o y
o eams’ ma ches in he ecen pas , esul s o di ec ma ches and o he non
ela ed esul s, as o example he diffe ence be ween eam budge s. Se en een
ele an a ibu es we e selec ed.The a ibu e se has h ee special a ibu es,
Team1wins (1), Team2wins (2) and d aws (X).
4 Con idence-Based Reasoning Sys em
The easoning sys em wo ks on ac s o he ype (a, c), whe e ais an a ibu e and
cis he es ima ed p obabili y o he ueness o a, which we also call confidence
(by simila i y wi h he same e m o associa ion ules).
The sys em has a module o a confidence-based easoning sys em (Fig. 2).
I s en ies o a ma ch Team
1-Team2a e: he con ex ual Knowledge basis
o a h eshold gi en as ule se and a ibu e alues o he cu en ma ch
Fig. 2. Con ex based easoning sys em

Fig. 3. Fo ecas ing esul s sc eensho
(excep 1,X,2) as ac s, all o hem wi h a confidence (whose alue depends on
he easoning mode, see below). The p oduc ion sys em is execu ed and he
ou pu is a iple <(1,c
1),(X,cx),(2,c
2)>o a ibu e, confidence o his
ma ch. The a ibu e wi h g ea e confidence is selec ed as he p edic ion.
The execu ion o he p oduc ion sys em is as egula . The e exis se e al
modes o confidence compu ing o ac s, which a e based in unce ain easoning
in Expe Sys ems [9]. Any a ibu e/ ac ais ini ialized wi h confidence
con (a):=|{o:oIa}| +1
|O|+1
The mos p omising compu a ion modes used a e:
Mode 1: As usual in Expe sys ems: I ule :{a1,...,a
k}→{c1,...,c
n}wi h
confidence ule con ( )isfi edon he ac s(a1,con (a1)),...,(ak,con (ak)),
he confidence es ima ed o each ciby he ule is
con n(ci)=con ( )·min(con (a1),...,con (ak))
and i upda es con (ci)ascon (c):=con (c)+con n(c)·(1 −con (c).
Mode 2: I cis ob ained by fi ing he ule , define con (c)=P(c)·Q(c)whe e
P(c):= p(c, )=con ( ),Q(c):= q(c, )=min(con (a1),...,con (ak))
I i en ails cby fi ing o o he ule p oduces he upda e o con (c)byupda ing
P(c):=P(c)+ p(c, )−P(c)· p(c, ),Q(c):=Q(c)+ q(c, )−Q(c)· q(c, )
Wi h espec o he h esholds o confidence, cu en ly he sys em allows he
use o selec hem by hand o by using he au oma ic selec ion mode which is:
γ=max({con (a):exis s{∅} → Y ule o he KB s. . a∈Y}∪{0.5})
Fig. 3 shows o ecas ing o week 21 o he Spanish p emie league (2009-10).
Fig. 4. Hi s on 2009-10 league
5 Expe imen s
I an an expe imen o he Spanish p emie and second di ision socce leagues
om 2009-10. In Fig. 4 hi s o p emie league a e g aphically depic ed.
Abou da a sou ce, empo al con ex s o o ecas ing esul s we e buil by
da a ex ac ed om he RSSSF A chi e (h p://www. sss .com). Objec s a e
ma ches (wi h empo al s amp (week, yea )) and a ibu es a e compu ed. Da a
was collec ed o he pas ou yea s. The size o he empo al con ex is abou
300 objec s and 17 a ibu es (al hough se e al o hem a e pa ame ized, i.e. ,
anking diffe ence abo e a h eshold). Thus, |I|is abou 5,100 pai s.
Expe imen s wi h he sys em show o ecas s o abou 57.37% in mode 2 and
56.32% in mode 1 by a selec ion o en quali a i e a ibu es and con ex ual
selec ion based on he p e ious 38 ma ches o each eam (Fig. 4). Such an
pe cen age o a quali a i e easoning sys em may be conside ed as an accep able
esul compa able wi h expec able esul s o expe s [3].
I is in e es ing o commen ha he con ex ual selec ion o he p emie
league is no he bes o he second league ha we ha e ound. Fo he second
league is be e o conside comple e se s o esul s. The esul s, unde he con-
di ions o official spanish be sys em a e: h ee awa ds a e achie ed: 583.42 eu .
o ea ning, wi h a cos o 38 eu . co esponding o 76 be s ( wo be s by week).
6 Concluding Rema ks and Fu u e Wo k
A confidence-based easoning sys em ha wo ks on sub-con ex s ex ac ed om
a empo al o mal con ex , buil o socce be s, is p esen ed. The sys em has
some simila i ies wi h [13], al hough he easoning sys em based on FCA is qual-
i a i e while he ci ed sys em is hyb id (bayesian easoning). Pu e quali a i e
easoning was selec ed based on he aim o disco e ing ends (unde a con ex-
ual selec ion) ep esen ed in he o m o associa ion ules wi h high confidence.
I is wo h no ing ha due o he p op ie a y na u e o p edic ion models, i is
difficul o compa e hem wi h ou sys em.
Pa o ou ongoing wo k includes h ee esea ch lines. Fi s ly, i is mo e
in e es ing o apply me hods o he au oma ed defini ion o new a ibu es
[2]. Secondly, since A ibu e logic based on implica ions does no suffe om
inconsis encies ( wo mu ually esul s can be de i ed), i was necessa y o selec
he a ibu e wi h highe confidence. Howe e , i seems mo e sound o decide his
by using mo e sophis ica ed me hods. And, finally, he selec ion o h esholds can
be efined o achie e a be e dependence among a ibu es, o his, me hods
in da a mining could be used (see e.g. [12]).
Wi h espec o compu a ional ea u es, compu ing asks a e easible (due o
he ela i ely small da a size). Howe e , he summa ion o addi ional da a and
a ibu es could make i necessa y o apply conse a i e e ac ion me hods [5,2]
o wo k wi h a con ex ual KB o a easible size.
Re e ences
1. Why Spain will win..., Enginee ing & Technology (June 5–18, 2010)
2. Alonso-Jim´enez, J.A., A anda-Co al, G.A., Bo ego-D´ıaz, J., Fe n´andez-Leb ´on,
M.M., Hidalgo-Doblado, M.J.: Ex ending A ibu e Explo a ion by Means o
Boolean De i a i es. In: P oc. 6 h In . Con . Concep La ices and Thei Applica-
ions (CLA 2008), pp. 121–132 (2008)
3. Ande sson, P., Ekman, M., Edman, J.: Fo ecas ing he as and ugal way: A s udy
o pe o mance and in o ma ion-p ocessing s a egies o expe s and non-expe s
when p edic ing he Wo ld Cup 2002 in socce , Wo king Pape Se ies in Business
Adminis a ion 2003:9, S ockholm School o Economics (2003)
4. A anda-Co al, G.A., Bo ego-D´ıaz, J.: Reconciling Knowledge in Social Tagging
Web Se ices. In: Co chado, E., G a˜na Romay, M., Manhaes Sa io, A. (eds.) HAIS
2010. LNCS(LNAI), ol. 6077, pp. 383–390. Sp inge , Heidelbe g (2010)
5. A anda-Co al, G.A., Bo ego-D´ıaz, J., Fe n´andez-Leb ´on, M.M.: Conse a i e Re-
ac ions o P oposi ional Logic Theo ies by Means o Boolean De i a i es: Theo-
e ical Founda ions. In: Ca e e, J., Dixon, L., Coen, C.S., Wa , S.M. (eds.) MKM
2009, Held as Pa o CICM 2009. LNCS, ol. 5625, pp. 45–58. Sp inge , Heidelbe g
(2009)
6. A ms ong, W.: Dependency s uc u es o da a base ela ionships. In: P oc. o IFIP
Cong ess, Gene a, pp. 580–583 (1974)
7. Balc´aza , J.L.: Redundancy, Deduc ion Schemes, and Minimum-Size Bases o As-
socia ion Rules. Logical Me hods in Compu e Science 6(2), 1–23 (2010)
8. Gan e , B., Wille, R.: Fo mal Concep Analysis - Ma hema ical Founda ions.
Sp inge , Heidelbe g (1999)
9. Gia a ano, J.C., Riley, G.D.: Expe Sys ems: P inciples and P og amming.
B ooks/Cole Publishing Co., Paci ic G o e (2005)
10. Golds ein, D.G., Gige enze , G.: Models o ecological a ionali y: he ecogni ion
heu is ic. Psychological e iew 109(1), 75–90 (2002)
11. Guigues, J.-L., Duquenne, V.: Familles minimales d’ implica ions in o ma i es e-
sul an d’un ableau de donnees binai es. Ma h. Sci. Humaines 95, 5–18 (1986)
12. Imbe man, S.P., Domanski, B., O cha d, R.A.: Using Booleanized Da a To Dis-
co e Be e Rela ionships Be ween Me ics. In: In . CMG Con e ence, pp. 530–539
(1999)
13. Min, B., Kim, J., Choe, C., Eom, H., McKay, R.I.: A compound amewo k o
spo s esul s p edic ion: A oo ball case s udy. Know.-Based Sys . 21(7), 551–562
(2008)
14. Neouchi, R., Taw ik, A.Y., F os , R.A.: Towa ds a Tempo al Ex ension o Fo mal
Concep Analysis. In: P oc.14 h Con . Canadian Soc. on Comp. S udies o In ell.
LNCS, ol. 2056, pp. 335–344. Sp inge , Heidelbe g (2001)