Proceedings of the 1st Early Career Researchers Workshop at ECSS 2021

THE 1ST EARLY CAREER RESEARCHERS WORKSHOP
COLLOCATED WITH ECCS 2021
P oceedings o Resea ch S a emen s
The 1s Ea ly Ca ee Resea che s Wo kshop
colloca ed wi h ECCS 2021
P oceedings o Resea ch S a emen s
25 Oc obe 2021
Mad id, Spain
Welcome o he P oceedings o he 1s Ea ly Ca ee Resea che s Wo kshop colloca ed wi h
he Eu opean Compu e Science Summi (ECCS) 2021, held in Mad id, Spain be ween 25 h
and 27 h Oc obe 2021. The goal o he one-day wo kshop, o ganised by Elisabe a Di Ni o
(Poli ecnico di Milano) and S anda ˇ
Zi n´y (Uni e si y o Ox o d), was o suppo ea ly ca ee
esea che s (PhD s uden s and pos docs) in he de elopmen o hei so skills ela ed o p e-
sen a ion abili ies, ne wo king, de eloping a esea ch plan, and connec ions o indus y. The
wo kshop was open o ea ly ca ee esea che s in all a eas o compu e science and so wa e en-
ginee ing. The pa icipan s enjoyed in i ed alks by Ge aldine Fi zpa ick (TU Wien), Lynda
Ha dman (CWI), Jus yna Pe ke (UCL), and Wol gang Emme ich (UCL, Zuhlke G oup) as well
as a panel discussion on open science and i s impac on ca ee de elopmen , held in conjunc ion
wi h he pa allel Leade s Wo kshop, and an open discussion wi h indus y ha has in ol ed as
panelis s Ruoyi Zhou (IBM Resea ch Eu ope), Nu ia de Lama (A os and Boa d o Di ec o s,
Big Da a Value Associa ion), and A ica Real (HP).
The esea ch s a emen s in his p oceedings we e submi ed by he pa icipan s and con ain a
wide a ie y o wo k, ei he comple ed o in p og ess, being unde aken by he cu en gene a ion
o PhD s uden s and ea ly ca ee esea che s.
The wo kshop would ha e no been possible wi hou he suppo o many people and o -
ganisa ions. In pa icula , we would like o hank In o ma ics Eu ope and he local o ganise s
in Mad id.
We hope you had a g ea ime in Mad id!
Elisabe a Di Ni o and S anda ˇ
Zi n´y
Ea ly Ca ee Wo kshop O ganise s, 2021
ii
Table o Con en s
Quali y analysis o mobile applica ions wi h special ocus on secu i y aspec s 1
K is iina Rahkema
E olu ion o use s’ choice beha iou unde he in luence o ecommende sys ems 7
Naieme Haz a i
Machine Lea ning applied o manage e o es ima ion and equi emen s in so wa e p ojec s 12
V´ıc o P´e ez-Pique as
Audi ing machine lea ning models o online educa ional pla o ms 17
Robe a Galici
Decision suppo sys ems o business model de elopmen 23
Sebas ian Go schalk
The powe o con ex elaxa ions in combina o ial op imisa ion 29
Ca e ina Viola
P o iding decision make s wi h ailo ed decision suppo sys ems 33
Jonas Ki chho
Sma con ac s classi ica ion and ulne abili ies de ec ion 39
Giacomo Ibba
Dynamic g oup ecommende sys ems: a con o e sial app oach o suppo g oup discussion 45
Hani Emamgholizadeh
Resou ce managemen in MEC ne wo ks 51
Bin Xiang
Decen alised cloud con inuum 55
Ad ian Spa a u
Using machine lea ning o speed up op imiza ion o g aphical models 60
Aleksand a Pe o a
Gua an eeing p i acy and ai ness in pe sonalized sys ems 66
Giacomo Medda
Log-based beha iou al di e encing applied o an indus ial case 72
C´eline Deknop
iii
Quali y Analysis o Mobile Applica ions wi h
Focus on Secu i y
K is iina Rahkema1[0000−0001−7332−2041]
Uni e si y o Ta u, Es onia [email p o ec ed]
Abs ac . Sma phones and mobile applica ions ha e become an es-
sen ial pa o ou daily li es. I is necessa y o ensu e he quali y o
hese applica ions. The pu pose o my PhD hesis is o s udy code qual-
i y o mobile applica ions. Two impo an aspec s o code quali y a e
main ainabili y and secu i y. My goals a e o s udy code smells, secu i y
issues and hei e olu ion in iOS applica ions and amewo ks and o
apply he gained knowledge o suppo de elope aining an eaching. I
ha e buil he ool G aphi yE olu ion o analyze sou ce code e olu ion.
The ool is buil in a modula manne and can be ex ended o add sup-
po o addi ional languages and ex e nal analysis ools. I ha e analysed
code smells in open sou ce iOS applica ions and compa ed hem o code
smells in And oid applica ions. In he emaining wo yea s o my PhD
s udies I plan o comple e he analysis o code smell and secu i y ulne -
abili y e olu ion in iOS applica ions and amewo ks. In addi ion, I will
apply G aphi yE olu ion in de elope aining a one indus y pa ne
and in uni e si y eaching.
Keywo ds: Cod smells, code e olu ion, dependencies, mobile apps, se-
cu i y
1 Mo i a ion and Backg ound
Wi h he popula i y o sma phones con inuously ising, al eady oday mo e
ime is spen on sma phones han on desk op compu e s [10]. In 2019, mos o
he global ma ke sha e (76%) was held by And oid, while iOS held only 22%
[16]. A he same ime o e all ea nings on he iOS App S o e a e conside ably
la ge han on he Google Play S o e [12]. This makes bo h And oid and iOS
e y a ac i e a ge s o de elope s. I is he e o e impo an o s udy code
quali y no only o And oid, bu also o iOS applica ions.
The e a e mul iple aspec s o conside ega ding code quali y, o example
main ainabili y and secu i y. One p oxy o code quali y is code smells. So a
he e has been e y li le esea ch on code smells in iOS applica ions.
Goals: The pu pose o my PhD hesis is o s udy code quali y o mobile
applica ions and o help de elope s build be e main ainable and mo e secu e
mobile applica ions. The e a e h ee main goals. Since code smells a e conside ed
o be obs acles o main ainabili y, he i s goal is o disco e he mos equen
code smells and how hey a ec iOS applica ions. The second goal is o analyse
1

2 F. Au ho e al.
how secu i y issues a e in oduced in o iOS applica ions and how hese issues can
be p e en ed. The hi d goal is o build on hese analyses o acili a e eaching
and aining de elope s o w i e be e main ainable and mo e secu e mobile
applica ions.
Backg ound: The ollowing pa ag aphs lis mos impo an ela ed wo k.
A mo e ho ough desc ip ion o ela ed wo k is gi en in my published a icles
[14,13,15].
Mos o he cu en esea ch on code smells in mobile applica ions has been
ca ied ou on he And oid pla o m. Mannan e al. [8] analyzed 21 objec o i-
en ed code smells in open sou ce And oid and Ja a desk op applica ions. Ma eus
e al. compa ed code quali y in And oid applica ions w i en in Ja a and Ko lin
[9]. Hech [5] de eloped a ool called PAPRIKA o analyze ou objec o ien ed
and six And oid speci ic code smells in And oid applica ions. This ool analyses
he And oid APK, gene a es a model and sa es i in a g aph da abase [7].
Habchi e al. [2] used PAPRIKA o de ec code smells in iOS applica ions.
They used ANTLR4 g amma s o gene a e pa se s o Swi and Objec i e-C
code. They analysed he AST gene a ed by hese pa se s o c ea e he applica-
ions g aphs used by PAPRIKA. They compa ed code smell occu ences on iOS
and And oid and concluded ha And oid applica ions we e mo e p one o code
smells [2]. To he bes o ou knowledge his has been he only s udy looking a
code smells on iOS applica ions.
Fo analysing he code smell e olu ion o mobile applica ions, mul iple ap-
p oaches ha e been used. To ack so wa e quali y o and oid applica ions, Hech
e al. [6] and Ma eus e al. [9] bo h used PAPRIKA o analyse he e olu ion o
And oid applica ions, applying he ool o each commi . Tu ano e al. [17] im-
plemen ed a ool called His o yMine ha uns DECOR on each commi , o
changed iles. Habchi e al. [4,3] implemen ed a ool called SNIFFER ha ex-
ac s commi s om a gi eposi o y, de ec s code smells in each commi using
PAPRIKA and ou pu s he code smell e olu ion o a p ojec .
Public ulne abili y da abases (e.g., he OSV1da abase and he NVD2da a-
base) con ain epo ed ulne abili ies and se e as an impo an da a sou ce
o de elope s o moni o he secu i y o hi d pa y applica ions and ame-
wo ks used. Un o una ely no all ulne abili ies a e epo ed publicly and hese
da abases only con ain da a abou e y la ge applica ions. Fo some pla o ms,
solu ions exis ha b ing his da a close o de elope s. Fo And oid applica ions
Nguyen e al. [11] c ea ed an And oid S udio plugin ha de ec s ou da ed and
ulne able lib a ies and checks i a lib a y can be upda ed wi hou addi ional
code changes. I lacks, howe e , analyses ha check i he ulne abili y eally
a ec s he applica ion and when sugges ing lib a y upda es i he lib a y API
unc ionali y has s ayed he same.
1h ps://os .de /
2h ps://n d.nis .go /
2
Quali y Analysis o Mobile Applica ions wi h Focus on Secu i y 3
2 Analysis o Code Smells in Mobile Applica ions
Code smells a e ecu ing pa e ns in code ha ha e been iden i ied as bad
p ac ices [1]. They yield echnical deb and long- e m main ainabili y p oblems
[1]. Gi en he signi icance o he sma phone ma ke i is impo an o s udy
code smells on bo h And oid and iOS.
Tool - G aphi ySwi : Since PAPRIKA has been a success ul ool o ana-
lyzing a lo o applica ions a once I decided o build a simila ool o Swi anal-
ysis. I decided agains he app oach aken by Habchi e al. [2], whe e hey needed
o i s con e iOS applica ions in o a sui able o ma . I c ea ed a ool called
G aphi ySwi 3 ha analysis Swi code, gene a es a model o his code and en-
e s i in o a neo4j g aph da abase. Fo indexing he sou ce code and gene a ing
he s uc u e o he Swi code I used a amewo k called Sou ceKi enF ame-
wo k4 ha ac s as a w appe a ound Apple’s powe ul Sou ceKi . The g aph
da abase con ains he ollowing nodes: App, Module, Class, Func ion, Va iable
and A gumen . These nodes a e connec ed h ough ela ionships. This model
di e s sligh ly om he one used in PAPRIKA. I added he Module node and he
ollowing ela ionships AP P OW N S M ODU LE,M ODULE OW N S CLASS,
IS T Y P E OF and DU P LICAT ES. Code smells a e de ined as que ies. The
que y de ini ions can be ound on he ool Gi Hub page3. Running code smell
que ies using his ool gene a es CSV iles o each code smell and allows us
o analyze he esul s. The ool G aphi ySwi is no longe in de elopmen , he
code and documen a ion is s ill a ailable on he ool web page, bu all he unc-
ionali ies a e inco po a ed by a new ool as desc ibed in he nex sec ion.
Tool - G aphi yE olu ion: I ex ended he ool G aphi ySwi and im-
plemen ed a ool called G aphi yE olu ion5[15] ha can analyse applica ions
w i en in a ious languages (Swi , Ja a and C++), including iOS applica ions
w i en in Swi . Di e en o p e ious ools ha ou pu da a abou he code
smell e olu ion, G aphi yE olu ion de ec s which classes, me hods and a iables
a e changed du ing a commi and eco ds only hese changes. This makes i
possible o que y code smells o all e sions o he applica ion a once. Addi-
ionally, I implemen ed he ool in a modula manne making i easy o add
suppo o addi ional languages and ex e nal analysis ools ha can be un
o each commi . Cu en ly I ha e implemen ed p elimina y suppo o Swi ,
Ja a and C++. Suppo o ex e nal ools is added o jscpd ha inds code
duplica es and inside ha de ec s secu i y ulne abili ies.
Empi ical S udies on Code Smells in iOS Applica ions: I iden i ied
he mos common code smells in open sou ce iOS applica ions [14]. In e ms o
pe cen age o applica ions a ec ed by a speci ic code smell he i e mos common
code smells a e Lazy Class, Long Me hod, Message Chain, Igno ing Low Memo y
Wa ning and Da a Class. Di e en o wha is o en seen in iOS de elope blogs,
Massi e View Con olle was one o he leas common code smells. Unde 18% o
3h ps://gi hub.com/k is iina a/G aphi ySwi
4h ps://Gi Hub.com/jpsim/Sou ceKi en
5h ps://gi hub.com/k is iina a/G aphi yE olu ion
3
4 F. Au ho e al.
applica ions we e a ec ed by his smell. I also compa ed code smell occu ences
in iOS and And oid applica ions [13]. Analysis on And oid applica ions was done
by popula ing he da abase using PAPRIKA. In o al, I iden i ied 19 code smell
ypes ha could po en ially occu in apps on bo h pla o ms. My analysis showed
ha 18 o he 19 iden i ied code smells occu ed in apps on bo h pla o ms.
Code smell Dis o edHie a chy ne e occu ed in iOS apps. I u ned ou ha ,
con a y o wha Habchi e al. [2] expec ed, he o e all densi y o code smells is
highe in iOS apps han in And oid apps. The p opo ions o code smells di e
be ween pla o ms. And oid applica ions wa e mo e o en a ec ed by code smells
ha seem o co esponds o big and complex classes while iOS applica ions we e
mo e a ec ed by code smells ha seem o co espond o smalle and simple
classes. These esul s can be in e es ing o de elope s mo ing om one pla o m
o he o he . I can also be use ul o de elope s o ools o hese pla o ms. The
emphasis on which code smells o look a is di e en depending on he pla o m.
Fu u e Wo k: G aphi yE olu ion was mainly buil o analyse code smell
e olu ion in applica ions w i en in Swi . I plan o conduc a la ge scale s udy
analysing he e olu ion o code smells in open sou ce iOS applica ions and iOS
amewo ks. Simila s udies ha e been done on And oid applica ions [6,4], bu
so a he e olu ion o code smells has no been s udied in iOS applica ions.
Visualisa ions Based on G aphi yE olu ion: The analysis p oduced by
G aphi yE olu ion can be a use ul base o isualisa ions. I al eady includes
high le el in o ma ion abou classes, me hods, a iables and he ela ionships
be ween hem. Using hese aspec s in he isualisa ions make i possible o he
use o ge an unde s anding o wha he code does and how he unc ionali-
ies ha e changed. I ha e supe ised wo mas e heses ha buil isualisa ions
based on G aphi yE olu ion. One o he isualisa ions, ha concen a ed on
highligh ing code smells in each commi , was buil in coope a ion wi h a so -
wa e de elopmen company and ecei ed posi i e eedback om hei de elope s.
The o he isualisa ion ied o show di e en aspec s o code e olu ion, such as
changes in me hod calls.
3 Secu i y Analysis o Mobile Applica ions
Mode n so wa e, including mobile applica ions, a e buil using nume ous hi d
pa y amewo ks. I is impo an o keep amewo k e sions up o da e o
p e en in oducing ulne abili ies. In p ac ice howe e many de elope s do no
upda e hei dependencies.
En isioned Solu ion Based on G aphi yE olu ion: Analysing he e o-
lu ion o ulne abili ies also opens up he possibili y o analyse ulne abili ies
in oduced h ough applica ion dependencies. I am planning on c ea ing a public
da abase ha con ains analysed open sou ce Swi lib a ies. G aphi yE olu ion
will be ex ended so ha i can connec me hod calls and a iable uses om he
analysed applica ion o he al eady analysed open sou ce lib a ies. This allows a
mo e ho ough ulne abili y analysis by looking a bo h he di ec and ansi i e
4
Quali y Analysis o Mobile Applica ions wi h Focus on Secu i y 5
dependencies o an applica ion and by checking i he ulne able me hods a e
eachable om he analysed applica ion.
4 Applica ion in T aining and Teaching
One eason o look a he e olu ion o a p ojec is o lea n how an applica ion o
applica ions in gene al e ol e. This unde s anding can help new de elope s lea n
how complex applica ions a e buil and how hey g ow. Analysing he e olu ion
o a speci ic p ojec can also help de elope s unde s and why and how p oblems
in hei code we e in oduced which can help p e en such issues in he u u e.
De elope T aining: The e is an ongoing coope a ion wi h a Finnish com-
pany o use G aphi yE olu ion in hei de elope aining. We a e planning on
analysing code p oduced by de elope s in hese aining sessions o de ec pa -
e ns and ga he eedback i his ool can help acili a e gi ing eedback.
Teaching a he Uni e si y: I plan o ex end G aphi yE olu ion so i
can be used by ins uc o s o moni o ing and compa ing s uden p og ess. Vi-
sualising changes be ween code e sions would make i easie o ins uc o s o
unde s and which classes, me hods and a iables we e added and how he p ojec
has g own since he las e sion. The ex ended ool will be used in uni e si y
cou ses by ins uc o s and imp o ed based on hei eedback.
5 Nex S eps
In he i s wo yea s o my PhD s udies I ha e implemen ed a ool called G aphi-
ySwi and i s ex ended e sion G aphi yE olu ion ha can analyse he e olu-
ion o sou ce code w i en in Swi , Ja a and C++. I ha e used G aphi ySwi
o analyse code smells in open sou ce iOS apps and compa ed code smell occu -
ences in open sou ce iOS and And oid apps.
In he nex wo yea s o my s udies I plan o inish analysing he e olu ion
o code smells and ulne abili ies in open sou ce iOS apps and amewo ks.
I also plan on ex ending he ool so ha analysis o open sou ce amewo ks
can be connec ed o hei uses in analysed applica ions which adds addi ional
possibili ies o secu i y analysis. Las ly I plan o apply he ool o de elope
aining and eaching in indus y.
Acknowledgemen s. Funding o his esea ch came om he Es onian Cen-
e o Excellence in ICT esea ch (EXCITE), he IT Academy P og amme o
ICT Resea ch De elopmen , he Aus ian minis ies BMVIT and BMDW, and
he P o ince o Uppe Aus ia unde he COMET (Compe ence Cen e s o
Excellen Technologies) P og amme managed by FFG.
Re e ences
1. Fowle , M.: Re ac o ing: imp o ing he design o exis ing code. Addison-Wesley
P o essional (2018)
5
Machine Lea ning applied o manage e o
es ima ion and equi emen s in so wa e
p ojec s⋆
V´ıc o P´e ez-Pique as[0000−0002−2305−5755]
Depa amen o de Sis emas In o m´a icos, Escuela Supe io de Ingenie ´ıa In o m´a ica,
Uni e sidad de Cas illa-La Mancha, Spain
[email p o ec ed]
Abs ac . Inc emen al complexi y in so wa e p ojec managemen makes
planning and decision making inc easingly slow and di icul . Ad ances
in A i icial In elligence a e shown as a possible solu ion o hese man-
agemen p oblems. In his way, i is in ended o use Machine Lea ning
algo i hms applied o he ield o so wa e p ojec managemen , in o de
o au oma e asks and p ocesses and suppo decision-making.
Keywo ds: P ojec managemen ·machine lea ning ·e o es ima ion
·nex elease p oblem
1 In oduc ion o he esea ch
As he yea s pass, so wa e p oduc s and de elopmen s ge mo e and mo e com-
plex, equi ing no only mo e e o in design and unc ionali y, bu also in plan-
ning and managemen . This implies ha as he so wa e ge s mo e complex, so
does i s managemen . Thus, i has become necessa y o c ea e ools ha help
and suppo he so wa e p ojec managemen , in o de o educe i s complex-
i y, speed up he de elopmen p ocess and suppo decision making. This line o
esea ch appea s o sol e many o he mos common p oblems ha a ise in he
ield o so wa e p ojec managemen . In his esea ch, wo main p oblems ha e
been ackled using Machine Lea ning algo i hms:
1.1 Requi emen s p io i iza ion
This p oblem consis s o deciding he mos impo an equi emen s o wo k on
nex , and i is also known as he ”Nex Release P oblem” (NRP) [2]. I is a
di icul and manual ask ha is pe o med many imes h oughou a p ojec .
To sol e his p oblem sa is ac o ily, a ce ain balance mus be ound be ween he
se o selec ed equi emen s, cus ome and s akeholde demands, and a ailable
⋆This esea ch s a emen and i s ini ial esul s ha e been pa ially unded by
he Jun a de Comunidades de Cas illa-La Mancha h ough he p ojec SB-
PLY/17/180501/000493.
12

esou ces.
Some o he algo i hms ha ha e been used o sol e his p oblems a e e olu-
iona y algo i hms (gene ic, NSGA-II) [6], g eedy algo i hms (GRASP) [3] and
An Colony [7, 8].
1.2 E o es ima ion o equi emen s
Requi emen s a e c ea ed o de ine speci ic needs ha mus be add essed in he
so wa e p oduc being de eloped. To ease he p ojec planning, equi emen s
a e o en gi en an es ima ion o he e o ha mus be done o comple e hem.
In plan-d i en p ojec s, his es ima ion is made once a he beginning o he
p ojec . Bu in p ojec s applying alue-d i en me hodologies, es ima ion o e-
qui emen s is done i e a i ely many imes du ing he p ojec s li e. Mo eo e , he
equi emen s es ima ion is made by he de elopmen eam, gi ing each equi e-
men an expe alue ela i e o he es o he equi emen s. This epe i i e,
manual and expe ience equi ing ask is easible o be sol ed by Machine Lea n-
ing algo i hms.
Machine lea ning models [5, 4, 1] ha e been applied o es ima e he size o use
s o ies. Neu al ne wo ks o e good esul s compa ed o he es ; in all cases,
he ele an in o ma ion used is he ex o he p oduc backlog i ems. When
wo king wi h ex ual in o ma ion, he de elopmen o ule-based algo i hms, de-
sc ip i e o based on p obabilis ic g aphic models could o e a g ea capaci y o
explain he p edic ion e u ned.
2 O e iew o he Resea ch Design and Gene al
Me hodological App oach
This esea ch will ocus on wo speci ic aims ha will ackle he p oblems de-
sc ibed p e iously:
– A1. Sea ch-Based So wa e Enginee ing applied o Nex Release
P oblem. Resolu ion o he NRP p oblem, using e olu iona y and g eedy
algo i hms. Special emphasis on he de elopmen o single and mul i a ia e
EDAs (Es ima ion o Dis ibu ion Algo i hms), since hey explici ly deal
wi h he ela ionships be ween he a iables. In addi ion, some o he mod-
els ha can be c ea ed con ain a s uc u e ha allows ela ionships be ween
he elemen s o he p oblem o be iden i ied. This is o special in e es since,
up o he au ho ’s knowledge, no EDA has been applied o he NRP p ob-
lem ye . New o ms o ep esen a ion o he p oblem will be de eloped in
addi ion o he classic one o equi emen s ec o s, associa ed cos and lis
o s akeholde s: Dependencies be ween logical and physical equi emen s, e-
u n on in es men , o ced o de , unce ain y in impo ance o equi emen s,
quali y o equi emen s, e c.
13
– A2. Supe ised classi ica ion applied o e o es ima ion o e-
qui emen s. Neu al ne wo ks will be used o gene a e au oma ic es ima ion
o he e o o equi emen s. These neu al ne wo ks will use ex ual in o -
ma ion, such as equi emen i le and desc ip ion o p edic he es ima ion.
3 Expec ed Deli e ables
–Repo s o all expe imen s ega ding A1 and A2.
–Use in e ace and code sha ed wi h esea ch communi y o algo i hms
which p o ided bes esul s.
–Publica ion in jou nals om he JCR anking. Candida es a e shown in Table
1.
Table 1: Candida es o publica ions.
Jou nal Ca ego y Impac Fac o
Knowledge-Based Sys ems Compu e Science, A i icial In elligence 5.921
Applied So Compu ing Compu e Science, A i icial In elligence 5.472
Au oma ed So wa e Enginee ing Compu e Science, So wa e Enginee ing 1.857
Jou nal o Sys ems and So wa e Compu e Science, In o ma ion Sys ems and So wa e 2.450
Empi ical So wa e Enginee ing Compu e Science, So wa e 3,156
Expe Sys ems wi h Applica ions Compu e Science, A i icial In elligence 5,452
In o ma ion and So wa e Technology Compu e Science, Compu e Science Applica ions, In o ma ion Sys ems, So wa e 2,726
Symposium on Sea ch Based So wa e Enginee ing Con e ence
In e na ional Symposium on Empi ical So wa e Enginee ing and Measu emen Con e ence
In e na ional Con e ence on Requi emen s Enginee ing Con e ence
4 Schedule o Ac i i ies
The schedule o ac i i ies is shown in Figu e 1.
Fig. 1: GANTT diag am o ac i i ies.
14
5 P elimina y esul s
The speci ic aim A1 o he esea ch has al eady s a ed being ackled. To sol e
he equi emen s p io i iza ion p oblem o NRP, an expe imen a ion model has
been designed. The expe imen s launched o e alua e each algo i hm execu e
mul iple imes di e en combina ions o he pa ame e s, calcula ing inal me -
ics ha will be used o e alua e he pe o mance o each one o he algo i hms.
In he esea ch, h ee algo i hms ha e been designed o sol e he NRP: a gene ic
algo i hm designed by he au ho s, ha s o es a se o non domina ed solu-
ion and uses a mono-objec i e me ic as i ness unc ion; he NSGA-II (Non
So ed Gene ic Algo i hm), a mul i-objec i e algo i hm equen ly used o sol e
he NRP; and GRASP (G eedy Randomized Adap i e Sea ch P ocedu e) algo-
i hms.
The esul s ob ained by he i s wo algo i hms ha e al eady been analyzed,
selec ing he bes con igu a ions and compa ing hem o ind hei weaknesses
and s eng hs (see Figu es 2 and 3). The esul s we e gene a ed by applying he
algo i hms o wo da ase s [3] ha ep esen ins ances o he NRP.
A gValue
# Sols
Spacing 1/Sp ead
HV
A gValue
# Sols
Spacing 1/Sp ead
HV
Gene icNDS eli ism Gene icNDS eli ismNDS NSGA-II
Da ase 1 Da ase 2
Fig. 2: Ki ia g aph o me ic compa ison be ween algo i hms.
15
(a) Resul s o Da ase 1 (b) Resul s o Da ase 2
Fig. 3: Op imal Pa e o on s o he bes con igu a ions o he algo i hms ana-
lyzed.
Re e ences
1. Ab ahamsson, P., F onza, I., Mose , R., Vlasenko, J., Ped ycz, W.: P edic ing de el-
opmen e o om use s o ies. In: In e na ional Symposium on Empi ical So wa e
Enginee ing and Measu emen . pp. 400–403 (2011)
2. Bagnall, A.J., Raywa d-Smi h, V.J., Whi ley, I.M.: The nex elease p oblem. In-
o ma ion and So wa e Technology 43(14), 883–890 (dec 2001)
3. Cha es-Gonz´alez, J.M., P´e ez-Toledano, M.A., Na asa, A.: So wa e equi emen
op imiza ion using a mul iobjec i e swa m in elligence e olu iona y algo i hm.
Knowledge-Based Sys ems 83(1), 105–115 (jul 2015)
4. Choe kie ikul, M., Dam, H.K., T an, T., Pham, T., Ghose, A., Menzies, T.: A
Deep Lea ning Model o Es ima ing S o y Poin s. IEEE T ansac ions on So wa e
Enginee ing 45(7), 637–656 (2019)
5. Dan as, Emanuel; Pe kusich, Mi ko; Dilo enzo, Ednaldo; Pe kusich, A.: E o Es i-
ma ion in Agile So wa e De elopmen : an Upda ed Re iew. In: In e na ional Con-
e ence on So wa e Enginee ing and Knowledge Enginee ing (2018)
6. Du illo, J.J., Zhang, Y., Alba, E., Ha man, M., Neb o, A.J.: A s udy o he bi-
objec i e nex elease p oblem. Empi ical So wa e Enginee ing 16(1), 29–60 ( eb
2011), h ps://link.sp inge .com/a icle/10.1007/s10664-010-9147-3
7. Sag ado, J., ´
Aguila, I., O ellana, F.: Mul i-objec i e an colony op imiza ion o
equi emen s selec ion. Empi ical So wa e Enginee ing 20, 577–610 (2015)
8. de Souza, J.T., Maia, C.L.B., Fe ei a, T.d.N., do Ca mo, R.A.F., B asil, M.M.A.:
An An Colony Op imiza ion App oach o he So wa e Release Planning wi h
Dependen Requi emen s. In: Cohen, M.B., ´
O Cinn´eide, M. (eds.) Sea ch Based
So wa e Enginee ing. pp. 142–157. Sp inge Be lin Heidelbe g, Be lin, Heidelbe g
(2011)
16
Audi ing Machine Lea ning Models o Online
Educa ional Pla o ms
Robe a Galici1[0000−0002−1825−0097]
Depa men o Ma hema ics and Compu e Science,
Uni e si y o Caglia i,
V. Ospedale 72, 09124 Caglia i, I aly
[email p o ec ed]
Abs ac . Machine lea ning (ML) is ans o ming educa ion and un-
damen ally changing eaching, lea ning, and esea ch. In esponse o his
si ua ion, i is impo an o ensu e ha he machine lea ning models used
in his con ex a e accoun able. Howe e , he li e a u e has gene ally o-
cused on imp o ing he accu acy o hese models as much as possible,and
only ecen ly has s a ed o in es iga e aspec s such as ai ness, ans-
pa ency, p i acy. A p ocess o audi ing is undamen al o ensu e ha
exis ing models ake ca e o hese aspec s, acco ding o he pe cep ions
o he use s and he impac hese models could ha e on hem. In ou
wo k, we plan o c ea e algo i hms and web-based ools ha can allow
s akeholde s o assess he accoun abili y o hei own machine lea ning
models om mul iple pe spec i es, en iching he e alua ion amewo k
and going beyond accu acy only e alua ions. Ou con ibu ions can help
o c ea e and deploy esponsible machine lea ning models o educa ion.
Keywo ds: Da a mining ·Educa ion ·Educa ional Da a Mining ·Highe
Educa ion ·Machine Lea ning.
1 Mo i a ion
Machine lea ning is a p ocess o ex ac ing and disco e ing pa e ns in la ge da a
se s in ol ing me hods a he in e sec ion o machine lea ning, s a is ics, and
da abase sys ems [4]. Du ing he las decades he use o da a mining is inc easing
a lo in many ields such as bioin o ma ics, ma ke ing campaigns, cybe secu i y,
educa ion and many mo e. In pa icula , educa ional da a mining (EDM) is
a esea ch a ea ha deals wi h he de elopmen o me hods o explo e da a
o igina ing in an educa ional con ex [19]. EDM is de ined by The Educa ional
Da a Mining communi y websi e1, as ”an eme ging discipline, conce ned wi h
de eloping me hods o explo ing he unique ypes o da a ha come om he
educa ional se ing, and using hose me hods o be e unde s and s uden s, and
he se ings which hey lea n in”. The e a e pape s ha co e he main aspec s
o da a mining in educa ion such as [1, 3, 17, 18].
1www.educa ionalda amining.o g
17

2 R. Galici
Educa ional machine lea ning is e y impo an because i can be used o
classi ying and p edic ing s uden s’ pe o mance [16], d opou s [21], sco e p e-
dic ions [15] and also eache s’ pe o mance [2]. I can help educa o s o ack
academic p og ess o imp o e he eaching p ocess, i can help s uden s in cou se
selec ion and educa ional managemen o be mo e e icien and e ec i e. Fo in-
s ance, knowledge acing [13] is he ask o modelling s uden knowledge o e
ime so ha we can accu a ely p edic how s uden s will pe o m on u u e in-
e ac ions. D opou is an e en ha occu s when a s uden o mo e han one,
decide o lea e school o uni e si y. So i is e y impo an o a oid his si u-
a ion and possibly o in o m he eache o wha is happening so ha he can
con ac he s uden and y o sol e he p oblems. S uden success is a c ucial
componen o highe educa ion ins i u ions because i is conside ed as an essen-
ial c i e ion o assessing he quali y o educa ional ins i u ions. P edic ing such
success is pa icula ly impo an because i can help decision make s o p o ide
he needed ac ions a he igh momen , and o plan he app op ia e aining
in o de o imp o e he s uden ’s success a e. Ano he impo an way in which
machine lea ning is used is wi h cou se ecommenda ion sys em. In ac , based
on s uden s choices du ing he ime, he sys em can sugges hem cou ses simila
o hose hey ha e al eady a ended.
In my esea ch p ojec I aim o analyze he pe cep ions o s akeholde s wi h
espec o aspec s such as ai ness, anspa ency, secu i y and p i acy in he
con ex o machine lea ning models o educa ion. Based on he ou comes o
hese analyses, I han aim o imp o e hese models such ha hey accoun
o he abo e aspec s. Speci ically, I am in e es ed in answe ing he ollowing
esea ch ques ions:
1. How a e educa ional machine lea ning models pe cei ed om he poin o
iew o ai ness, secu i y, p i acy, anspa ency and sa e y?
2. How can we imp o e accoun abili y o machine lea ning models in educa ion
wi h espec o he abo e pe spec i es?
2 Backg ound
2.1 How is machine lea ning applied in educa ion
Machine lea ning and educa ion p ocesses a e closely in e connec ed. ML algo-
i hms analyze how he s uden s pe cei e and explo e he in o ma ion hey a e
gi en. I helps he sys em o ei he d aw he use back and go h ough some
lea ning poin s again o le hem s ep u he . ML also helps he eache s o
moni o and ace he lea ning p ocess indi idually. As compa ed o adi ional
me hods in class ooms, whe e he goal is o deli e he cou se, bu no ensu e
ha e e yone go i , ML gi es an ad an age o mo e p o ound in o ma ion pe -
cep ion. ML echnologies analyze he con en o online cou ses and help o igu e
ou whe he he quali y o he o e ed in o ma ion mee s he applicable s anda ds
on one hand, and on he o he , i shows how he use s pe cei e he da a and
do hey unde s and wha is augh . The e is ano he applica ion o machine
18
Audi ing Machine Lea ning Models o Online Educa ional Pla o ms 3
lea ning in educa ion ha deals wi h sco es and g ading. As each online cou se
e lec s he lea ning abili ies o a la ge numbe o s uden s, hey ha e a lo o
expe ience in g ading hem.
The au ho s in [6] in oduced EdNed, which is he da ase o all s uden -
sys em in e ac ions collec ed o e 2 yea s by San a, a mul i-pla o m AI u o ing
se ice wi h mo e han 780K use s in Ko ea a ailable h ough And oid, iOS and
web. The eco ded beha io is limi ed o ques ion-sol ing ac i i ies, so i is im-
po an o expand i . The nex yea hey p oposed Sain + [20], a successo o he
p e ious one. They planned o model no only s uden s’ p oblem-sol ing eco ds,
bu also a ious lea ning ac i i ies, such as wa ching lec u es and s udying expla-
na ions o each exe cise. In addi ion, hey planned o explo e a chi ec u es o
knowledge acing models o he han ans o me based encode -decode model
ha sepa a ely p ocesses exe cise in o ma ion and s uden esponse in o ma ion.
O he s de eloped DAS3H [5], a s uden model ha explici ly accoun s o mem-
o y decay and he bene i s o p ac ice when i ems can in ol e mul iple skills a
he same ime. In pa icula , hey need o imp o e he scalabili y o DAS3H
model, design models ha do no ely on speci ically designed ime windows,
using o example sel -exci ing p ocesses such as Hawkes p ocesses.
In gene al, he abo e machine lea ning models a e inc easingly used in he
eal wo ld and educa ion is one o he many applica ion domains whe e hese
models a e becoming mo e and mo e pe asi e. Howe e , s udies on machine
lea ning models a e hose ha measu e he accu acy o how e ec i e hey a e
om a lea ning poin o iew, end no o conside wha s akeholde s’ pe cep-
ions in e ms o pe spec i es like ai ness and anspa ency. Some s udies ha e
ocused hei a en ion on ai ness, which means ensu ing ha pe sonal and
social ci cums ances do no p e en s uden s om achie ing hei academic po-
en ial. Ne e heless, machine lea ning models needs o be anspa en , in o he
wo ds, his means o each while making ob ious he in ellec ual p ac ices in-
ol ed in comple ing and e alua ing a lea ning ask. The goal o anspa en
eaching is o p omo e s uden s’ conscious unde s anding o how hey lea n.
2.2 Beyond accu acy aspec s
A i icial In elligence (AI) is becoming mo e and mo e impo an in he las
decades and o his eason, many s udies ha e been conduc ed. In [14] hey in-
oduce a amewo k o algo i hmic audi ing ha suppo s a i icial in elligence
sys em de elopmen end- o-end, o be applied h oughou he in e nal o ganiza-
ion de elopmen li ecycle. The au ho s in [9] designed a su ey o assess use s’
pe cep ions o sea ch engine biases, wi h he goal o diagnosing he easoning
unde nea h hei p e e ences o he eal sea ch pages o he syn hesized pages.
They also in es iga ed he e ec s o bias-mi iga ion on use s’ sa is ac ions. They
disco e ha pa icipan s p e e he eal sea ch pages o e he syn hesized ones
wi h a signi ican highe a io. The i s sys ema ic in es iga ion o indus y
eams’ challenges and needs o suppo in de eloping ai e ML sys ems was
conduc ed by [10]. E en when p ac i ione s a e mo i a ed o imp o e ai ness in
hei p oduc s, hey o en ace a ious echnical and o ganiza ional ba ie s. One
19
4 R. Galici
o he mos p ominen issues in educa ion policy oday, accoun abili y is a key
elemen in he success o educa ion imp o emen sys ems. In ac , accoun abili y
means holding e e yone wi h esponsibili ies o high s anda ds o pe o mance
while audi s a e ools o in e oga ing complex p ocesses, o en o de e mine
whe he hey comply wi h company policy, indus y s anda ds o egula ions.
3 Resea ch plan
Many s udies ha e been conduc ed in machine lea ning and in pa icula in
educa ion. The majo i y o esea che s ha e s udied ai ness, p i acy, secu i y
and all he o he s, bu hese pe spec i es ha e been unde -explo ed on machine-
lea ning models applied o educa ion. In ac , i is impo an o know wha use s
hink and y o help hem wi h he di icul ies ha hey may ha e. I assumed o
spend h ee mon hs on esea ch and one mon h o expe imen s wi h s uden s.
The p ocess o audi ing can be made o a speci ic ield o mo e gene ic, so i is
possible o include many ields. The pu pose o my esea ch is o ill his gap in
he li e a u e and he e o e I plan o ollow hese h ee main s eps.
Iden i ica ion o case s udies o ML models in educa ion. The i s
s ep conce ns on he iden i ica ion o which machine lea ning models can be
in e es ing o analyze he accoun abili y. We ha e iden i ied d opou p edic ion
and educa ional ecommende sys ems as he mos in e es ing ones, bu we a e
also open o add o he models. A he beginning, i would be use ul o analyze
he d opping ou o s uden s o uni e si ies cou ses, hen he p obabili y o
lea ing cou ses. In pa icula , d opping ou o school e e s o abandoning one’s
schooling be o e ge ing an ini ial diploma. In ou speci ic case, i means ha
a s uden decide o lea e he cou se e en be o e doing he exam. D opping ou
is a complex and mul i ace ed phenomenon. S uden s a e cons an ly in luenced
by a ious ac o s and when hese ha e a nega i e in luence, hey a e called
isk ac o s. Risk ac o s inc ease he likelihood ha a s uden will s uggle
a school o uni e si y, which can lead o d opping ou . On he o he hand,
a ecommende sys em is used o gene a e meaning ul ecommenda ions o a
collec ion o use s o i ems o p oduc s ha migh in e es hem. In educa ion,
i would be use ul o ecommend a speci ic cou se o a s uden , based on his o
he p e iews choices. Fo example, i a s uden is s udying Physics, he sys em
will y o sugges some hing which is s ic ly ela ed o ha acul y. Fi s we
wan o s a wi h uni e si y da a, e.g., om Moodle pla o ms, o d opou and
hen we plan o use la ge-scale da ase s, such as COCO [7]. o c ea e algo i hms
(e.g., ecommende sys ems) and o make audi ing wi h hem. Moodle p o ides
log da a a he si e and cou se le el. This da a can be accessed and downloaded
as ac i i y epo s. You can see wha pages he s uden s accessed, he ime and
da e hey accessed i , he IP add ess hey came om, and hei ac ions ( iew,
add, upda e, dele e). On he o he hand, COCO includes in o ma ion collec ed
om a leading global ma ke places o online lea ning and eaching a scale. In
pa icula , Udemy enables expe s in a ious a eas o o e cou ses a no cha ge
o o ui ion ees.
20
Audi ing Machine Lea ning Models o Online Educa ional Pla o ms 5
S udy o he ML model accoun abili y. Fo each case s udy, iden i ied
in a p e ious s ep (d opou p edic ion o cou se ecommenda ion), he second
s ep consis s in in es iga ing which aspec s we wan o accoun o and why i
is impo an o pe o m an accoun abili y s udy on hese aspec s. The idea is o
b ing s uden s oge he , so i can be possible o p esen hem examples o ma-
chine lea ning models based on case s udies and ask hem o answe ques ions
con ained in ques ionnai es based on ce ain cases in which hese models can
be used in he eal wo ld. Fo example, conside ing he d opou p edic ion, we
can ha e a anking o s uden s o ganized in wo ables ha may be a isk o
ailing o gi ing up he cou se. I migh be use ul o ask he eache i he e a e
p oblems wi h he wo anking. The eache can no ice ha he e a e oo male
s uden s, so he model is un ai , o maybe he can no unde s and why hese
s uden s a e a isk and can lea e he cou se, so his is a lack o anspa ency.
This s ep may include also in e iews wi h de elope s, eache s and o he s ake-
holde s in educa ion. The da a will be collec ed h ough he ques ionnai es ha
will be dis ibu ed o he in e es ed s akeholde s. We will p oduce an a icle ha
desc ibe each case o s udy, in pa icula , how o do accoun abili y and wha we
ound om ou s udy. This is he mos explo a o y pa . In a second ime, gi en
a case s udy, using s a e-o - he-a models we a e going o make he accoun abil-
i y based on he guidelines de eloped in he p e ious s ep. The ou pu will be
con e ence pape s and jou nal a icles desc ibing he accoun abili y o exis ing
sys ems o speci ic case s udies such as he ollowing ones [11, 12, 8].
De elopmen o accoun able ML models. Las , o he hi d s ep, we
plan o make he conside ed machine lea ning models mo e esponsible, based on
he indings and guidelines de ined in he p e iews s ep. Ou goal is o p o ide
de ini ions, algo i hms and ools ha allow educa ions s akeholde s o assess he
accoun abili y o hei sys ems in a simple way. I would be use ul also o c ea e
a web-based in e ace own machine lea ning model and ob ain an e alua ion
o m co e ing di e en aspec s impo an o accoun abili y ( ela ed o ai ness,
anspa ency, social impac and o he s). One o he ou pu s could be a web-based
ool, possibly dissemina ed as a demo pape .
Re e ences
1. Bake , R.S., Yace , K.: The s a e o educa ional da a mining in 2009: A e iew and
u u e isions. JEDM— Jou nal o Educa ional Da a Mining 1(1), 3–17 (2009)
2. Bienkowski, M., Feng, M., Means, B.: Enhancing eaching and lea ning h ough ed-
uca ional da a mining and lea ning analy ics: An issue b ie . O ice o Educa ional
Technology, US Depa men o Educa ion (2012)
3. Cas o, F., Vellido, A., Nebo , A., Mugica, F.: Applying da a mining echniques o
e-lea ning p oblems. In: E olu ion o eaching and lea ning pa adigms in in elligen
en i onmen , pp. 183–221. Sp inge (2007)
4. Chak aba i, S., Es e , M., Fayyad, U., Geh ke, J., Han, J., Mo ishi a, S.,
Pia e sky-Shapi o, G., Wang, W.: Da a mining cu iculum: A p oposal ( e sion
1.0). In ensi e Wo king G oup o ACM SIGKDD Cu iculum Commi ee 140,
1–10 (2006)
21
Re e ences
1. Al mann, J., Ion, M., Bany Mohammed, A.A.: Taxonomy o G id Business Models.
In: G id Economics and Business Models, ol. 4685, pp. 29–43. Sp inge (2007)
2. Apel, S., Ba o y, D., K¨as ne , C., Saake, G.: Fea u e-O ien ed So wa e P oduc
Lines. Sp inge , Heidelbe g (2013)
3. Bland, D.J., Os e walde , A.: Tes ing business ideas. John Wiley & Sons, Hoboken
(2020)
4. Bouwman, H., de Reu e , M., Heikkil¨a, M., Fiel , E.: Business model ooling: whe e
esea ch and p ac ice mee . Elec onic Ma ke s 30(3), 413–419 (2020)
5. Chesb ough, H.: Business model inno a ion: i ’s no jus abou echnology any-
mo e. S a egy & Leade ship 35(6), 12–17 (2007)
6. Gassmann, O., F ankenbe ge , K., Csik, M.: The business model na iga o : 55
models ha will e olu ionise you business. Pea son, Ha low (2014)
7. Gene al Elec ic Inc: GE Global Inno a ion Ba ome e 2018,
h ps://www.ge.com/ epo s/inno a ion-ba ome e -2018/
8. Go schalk, S., Ki chho , J., Engels, G.: Ex ending Business Model De elopmen
Tools wi h Consolida ed Expe Knowledge. In: Business Modeling and So wa e
Design, ol. 422, pp. 3–21. Sp inge (2021)
9. Go schalk, S., Ri meie , F., Engels, G.: Business Models o S o e-O ien ed So -
wa e Ecosys ems: A Va iabili y Modeling App oach. In: Business Modeling and
So wa e Design, ol. 356, pp. 153–169. Sp inge (2019)
10. Go schalk, S., Ri meie , F., Engels, G.: In e wined De elopmen o Business
Model and P oduc Func ions o Mobile Applica ions: A Twin Peak Fea u e Mod-
eling App oach. In: So wa e Business, pp. 192–207. Sp inge (2019)
11. Go schalk, S., Ri meie , F., Engels, G.: Hypo hesis-d i en Adap a ion o Busi-
ness Models based on P oduc Line Enginee ing. In: In e na ional Con e ence on
Business In o ma ics (CBI). IEEE (2020)
12. Go schalk, S., Yigi bas, E., Nowosad, A., Engels, G.: Si ua ion-Speci ic Business
Model De elopmen Me hods o Mobile App De elope s. In: En e p ise, Business-
P ocess and In o ma ion Sys ems Modeling, ol. 421, pp. 262–276. Sp inge (2021)
13. Hende son-Selle s, B., Raly ´e, J., ˚
Age alk, P.J., Rossi, M.: Si ua ional Me hod
Enginee ing. Sp inge , Heidelbe g (2014)
14. Kuechle , B., Vaishna i, V.: On heo y de elopmen in design science esea ch:
ana omy o a esea ch p ojec . Eu . J. In . Sys . 17(5), 489–504 (2008)
15. McG a h, R.G.: Business Models: A Disco e y D i en App oach. Long Range Plan-
ning (43), 247–261 (2010)
16. Os e walde , A., Pigneu , Y.: Business Model Gene a ion: A Handbook o Vision-
a ies, Game Change s, and Challenge s. John Wiley & Sons, Hoboken (2010)
17. Os e walde , A., Pigneu , Y.: Designing Business Models and Simila S a egic Ob-
jec s: The Con ibu ion o IS. Jou nal o he Associa ion o In o ma ion Sys ems
14(5), 237–244 (2013)
18. Ries, E.: The Lean S a up: How Today’s En ep eneu s Use Con inuous Inno a-
ion o C ea e Radically Success ul Businesses. C own Business, USA (2014)
19. Szopinski, D., Schoo mann, T., John, T., Knacks ed , R., Kundisch, D.: So wa e
ools o business model inno a ion: cu en s a e and u u e challenges. Elec onic
Ma ke s 60(11), 2794 (2019)
20. Vei , D., Clemons, E., Benlian, A., Buxmann, P., Hess, T., Kundisch, D., Leimeis-
e , J.M., Loos, P., Spann, M.: Business Models: An In o ma ion Sys ems Resea ch
Agenda. Business & In o ma ion Sys ems Enginee ing 6(1), 45–53 (2014)
28

The Powe o Con ex Relaxa ions in
Combina o ial Op imisa ion
Ca e ina Viola
Depa men o Compu e Science, Uni e si y o Ox o d, UK
[email p o ec ed]
Abs ac . Valued cons ain sa is ac ion p oblems o m a la ge and ex-
p essi e class o combina o ial op imisa ion p oblems. The aim o my
esea ch p ojec is he sys ema ic s udy o he applicabili y o con ex
elaxa ions o he s udy o he compu a ional complexi y o he exac
and app oxima ed sol abili y o alued cons ain sa is ac ion p oblems
Keywo ds: con ex elaxa ions, combina o ial op imisa ion, cons ain sa is ac-
ion, algo i hms, compu a ional complexi y
1 In oduc ion
Con ex elaxa ions a e a powe ul ool o design polynomial- ime algo i hms
o exac and app oxima e solu ions o combina o ial op imisa ion p oblems [7].
Con ex elaxa ions ha e been s udied in heo e ical compu e science and ope -
a ional esea ch [3] and hey ha e been also success ully applied o se e al opics
om a i icial in elligence such as, o example, local clus e ing, communi y de-
ec ion [6], segmen a ion [10], and 3D econs uc ion [11]. To sol e an ins ance
o a minimisa ion p oblem (o a maximiza ion p oblem), he ins ance is o mu-
la ed as an in ege p og am ha is hen elaxed o a con ex p og am which can
be sol ed in polynomial ime, e.g., o a linea p og am o o a semide ini e p o-
g am. The a io O
Fo he op imum Oo he o iginal p oblem o he op imum F
o he elaxed p oblem is called in eg ali y gap (in a maximiza ion p oblem he
in eg ali y gap is F
O). I he in eg ali y gap is 1 hen he solu ion o he elaxed
p oblem is an exac solu ion o he o iginal p oblem. O he wise, an app oxima e
solu ion o he p oblem can be ob ained by designing a sui able polynomial- ime
algo i hm ha con e s he solu ion o he elaxed p oblem in o an in ege one.
The be e -known and mos used con ex elaxa ions a e linea p og amming
(LP) elaxa ions and semide ini e p og amming (SDP) elaxa ions. In LP e-
laxa ions, he o iginal in ege p oblem is elaxed o a linea p og am, i.e., an
ins ance o an op imisa ion p oblem wi h a iables ha ange o e he eals and
which can be in e p e ed as p obabili y dis ibu ions on he possible solu ions o
he in ege s p oblem; while in SDP elaxa ions, he o iginal in ege p oblem is
elaxed o a semide ini e p og am, i.e., an ins ance o an op imisa ion p oblem
whe e he a iables a e ec o s anging o e he eals and whose no ms can be
29
in e p e ed as p obabili y dis ibu ions on he possible solu ions o he in ege s
p oblem. SDP elaxa ions we e pionee ed by a esul o Goemans and Williamson
[8] who ob ained he bes possible app oxima ion algo i hm o Max-Cu . The
impo ance o LP and SDP elaxa ions o ob ain bo h heo e ically in e es -
ing esul s and p ac ical applica ion elies upon he ac ha LP and SDP can
be sol ed in polynomial- ime by in e io -poin me hods (see, [9] and [15, ?,?]),
which also p o ide p ac ically e icien algo i hms. A con ex elaxa ion can be
g adually s eng hened by adding local cons ain s which a e sa is ied by in ege
solu ions, hus ob aining a hie a chy o con ex elaxa ions. The mos amous
hie a chies o LP elaxa ions a e hose p oposed by She ali and Adams [16] and
by Lo ´asz and Sch ij e [14], while a hie a chy o SDP elaxa ions was p oposed
by Lasse e [13].
The objec i e o he esea ch p ojec is he sys ema ic s udy o he powe o
con ex elaxa ions. Mo e p ecisely, he objec i e is o p o ide a p ecise cha ac-
e iza ion o he compu a ional combina o ial op imisa ion p oblems which a e
exac ly and app oxima ely sol ed by a speci ic con ex elaxa ion (e.g., an LP
elaxa ion, an SDP elaxa ion, o a ce ain le el o one o he men ioned hie -
a chies). A u he goal o he p ojec is o in es iga e he consequences o he
powe o speci ic con ex elaxa ions on he compu a ional complexi y o alued
cons ain sa is ac ion p oblems.
Valued cons ain sa is ac ion p oblems (VCSPs) a e a wide class o compu-
a ional op imiza ion p oblems. The inpu o a VCSP ins ance consis s o ini ely
many a iables, an objec i e unc ion, ha is, a ini e sum o cos unc ions de-
ined on a ixed se called he domain and applied o some o he gi en a iables,
and a a ional h eshold. The compu a ional ask is o decide whe he he e ex-
is s an assignmen o alues om he domain o he a iables whose cos , i.e.,
he alue o he objec i e unc ion co esponding o he assignmen , is a mos
he gi en h eshold.
Con ex elaxa ions ha e been al eady applied o s udy he compu a ional
complexi y o VCSPs bo h in he ini e-domain and in ini e-domain se ing. In
he ini e-domain se ing, he applicabili y o a basic LP elaxa ion and o a con-
s an le el o he She ali-Adams elaxa ions o exac sol abili y o VCSPs was
comple ely classi ied in [12] and [17], espec i ely. Fo in ini e-domain VCSPs, a
su icien condi ion o he exac sol abili y ia a basic linea p og amming e-
laxa ion was gi en in [2]. This esul se led he polynomial- ime ac abili y o
VCSPs o speci ic classes o piecewise linea cos unc ions (e.g., o submodula
piecewise linea homogeneous cos unc ions) whose complexi y was no known
be o e. Mos ecen ly, his esul was gene alised by a su icien condi ion o he
exac sol abili y ia a combina ion o he basic linea p og amming elaxa ion
and he a ine in ege p og amming (AIP) elaxa ion [18]. The AIP elaxa ion
[4, 1] is a a ia ion o he LP elaxa ion whe e he a iables a e allowed o ake
alues in he se o all in ege s. In ac , he su icien condi ion o he applicabil-
i y o he combined basic LP and AIP elaxa ion also applies o a gene alisa ion
o VCSPs called p omise alued cons ain sa is ac ion p oblems (PVCSPs), and
ex ended a esul om [5]. Fo in ini e-domain VCSPs, he combined basic LP
30
and AIP elaxa ion is s ic ly mo e powe ul han he basic LP elaxa ion alone,
in he sense ha he combined elaxa ion exac ly sol es all he VCSPs ha
a e exac ly sol ed by he basic LP elaxa ion; and, u he mo e, i se les he
polynomial ime ac abili y o a class o in ini e-domain VCSPs ha do no
sa is ies he su icien condi ion o he applicabili y o he basic LP elaxa ion.
The esul on he combined basic LP and AIP elaxa ions, pa es he way o he
s udy o di e en combina ions o wo, o mo e, con ex elaxa ions.
The aim o his p ojec is o u n he s udy o exac sol abili y o VCSPs ia
a ce ain con ex elaxa ion in o a sys ema ic app oach and o ex end i o he
s udy o app oxima e sol abili y o VCSPs.
Re e ences
1. Ba o, L., Bul´ın, J., K okhin, A., Op ˇsal, J.: Algeb aic app oach o
p omise cons ain sa is ac ion. Jou nal o he ACM 68(4) (Jul 2021),
h ps://doi.o g/10.1145/3457606
2. Bodi sky, M., Mamino, M., Viola, C.: Piecewise linea alued CSPs sol able by
linea p og amming elaxa ion. o appea in ACM T ans. on Compu a ional Logic
(2021), p ep in a ailable a a xi .o g/abs/1912.09298. An ex ended abs ac ap-
pea ed in P oceedings o he 27 h EACSL Annual Con e ence on Compu e Science
Logic (CSL) wi h he i le Submodula Func ions and Valued Cons ain Sa is ac-
ion P oblems o e In ini e Domains
3. Boyd, S.P., Vandenbe ghe, L.: Con ex Op imiza ion. Camb idge Uni e si y P ess
(2004)
4. B akensiek, J., Gu uswami, V.: An Algo i hmic Blend o LPs and Ring Equa-
ions o P omise CSPs. In: P oceedings o he 30 h Annual ACM-SIAM
Symposium on Disc e e Algo i hms (SODA’19). pp. 436–455. SIAM (2019),
h ps://doi.o g/10.1137/1.9781611975482.28
5. B akensiek, J., Gu uswami, V., W ochna, M., ˇ
Zi n´y, S.: The powe o he combined
basic LP and a ine elaxa ion o p omise CSPs. SIAM Jou nal on Compu ing 49,
1232–1248 (2020), h ps://doi.o g/10.1137/20M1312745
6. B¨uhle , T., Rangapu am, S.S., Se ze , S., Hein, M.: Cons ained ac ional
se p og ams and hei applica ion in local clus e ing and communi y de ec-
ion. In: Dasgup a, S., McAlles e , D. (eds.) P oceedings o he 30 h In e na-
ional Con e ence on Machine Lea ning. P oceedings o Machine Lea ning Re-
sea ch, ol. 28, pp. 624–632. PMLR, A lan a, Geo gia, USA (17–19 Jun 2013),
h ps://p oceedings.ml .p ess/ 28/buhle 13.h ml
7. Chlam ac, E., Tulsiani, M.: Con ex elaxa ions and in eg ali y gaps. In: Handbook
on semide ini e, conic and polynomial op imiza ion, pp. 139–169. Sp inge (2012)
8. Goemans, M.X., Williamson, D.P.: Imp o ed app oxima ion algo i hms o max-
imum cu and sa is iabili y p oblems using semide ini e p og amming. Jou nal o
he ACM 42(6), 1115–1145 (1995), h ps://doi.o g/10.1145/227683.227684
9. Ka ma ka , N.: A new polynomial- ime algo i hm o linea p og amming. Com-
bina o ica 4(4), 373–395 (1984), h p://dx.doi.o g/10.1007/BF02579150
10. Klod , M., S einb uecke , F., C eme s, D.: Momen cons ain s in con ex op i-
miza ion o segmen a ion and acking. In: Ad anced Topics in Compu e Vision.
Sp inge (2013), h ps://doi.o g/10.1007/978-1-4471-5520-18
31
11. Kole , K., B ox, T., C eme s, D.: Fas join es ima ion o silhoue es and dense 3D
geome y om mul iple images. IEEE T ansac ions on Pa e n Analysis and Machine
In elligence 34(3), 493–505 (2012), h ps://doi.o g/10.1109/TPAMI.2011.150
12. Kolmogo o , V., Thappe , J., ˇ
Zi n´y, S.: The powe o linea p og amming
o gene al- alued CSPs. SIAM Jou nal on Compu ing 44(1), 1–36 (2015),
h p://dx.doi.o g/10.1137/130945648
13. Lasse e, J.B.: Global op imiza ion wi h polynomials and he p ob-
lem o momen s. SIAM Jou nal on Op imiza ion 11(3), 796–817 (2001),
h ps://doi.o g/10.1137/S105262340036680
14. Lo ´asz, L., Sch ij e , A.: Cones o ma ices and se - unc ions and 0-
1 op imiza ion. SIAM Jou nal on Op imiza ion 1, 166–190 (1989),
h ps://epubs.siam.o g/doi/pd /10.1137/0801013
15. Nes e o , Y., Nemi o skii, A.: In e io -Poin Polynomial Algo i hms in Con ex P o-
g amming. Socie y o Indus ial and Applied Ma hema ics, Philadelphia (1994),
h ps://epubs.siam.o g/doi/abs/10.1137/1.9781611970791
16. She ali, H.D., Adams, W.P.: A hie a chy o elaxa ions be ween he con inuous and
con ex hull ep esen a ions o ze o-one p og amming p oblems. SIAM Jou nal on Dis-
c e e Ma hema ics 3(3), 411–430 (1990), h ps://doi.o g/10.1137/0403036
17. Thappe , J., ˇ
Zi n´y, S.: The powe o She ali–Adams elaxa ions o gene al-
alued CSPs. SIAM Jou nal on Compu ing 46(4), 1241–1279 (2017),
h p://dx.doi.o g/10.1137/16M1079245
18. Viola, C., ˇ
Zi n´y, S.: The Combined Basic LP and A ine IP Relaxa ion o
P omise VCSPs on In ini e Domains. ACM T ans. Algo i hms 17(3) (Jul 2021),
h ps://doi.o g/10.1145/3458041
32
P o iding Decision Make s wi h Tailo ed
Decision Suppo Sys ems
Jonas Ki chho ?
So wa e Inno a ion Lab, Ins i u e o Compu e Science, Pade bo n Uni e si y,
Ge many
[email p o ec ed]
Abs ac . Decision make s show an inc eased need o decision suppo
due o he ising ola ili y, unce ain y, complexi y and ambigui y in
business en i onmen s. In his esea ch s a emen , I demons a e ha
decision suppo p o ided by decision suppo sys ems mus be ailo ed
o indi idual decision make s o op imal decision making. This includes
adap ing he decision suppo sys em o he goal o a decision make
and esou ces a ailable o hem such as da ase s, so wa e ools o ime
o iden i y an op imal decision. Since his indi idualiza ion is no ye
su icien ly add essed by exis ing sys ems, I p esen a solu ion concep
ha enables he c ea ion o decision suppo sys ems which a e ailo ed
o indi idual decision make s. The concep u ilizes ideas om Si ua ional
Me hod Enginee ing and Da a Ecosys ems. I u he mo e explain my
esea ch app oach o ealize he solu ion concep .
Keywo ds: Adap i e Decision Suppo Sys em
·
DSS Gene a o
·
Si ua ional
Me hod Enginee ing
·
Da a Ecosys em
·
Ene gy Dis ibu ion Ne wo k Planning
1 Mo i a ion
I am cu en ly wo king as a esea che in he esea ch p ojec FlexiEne gy1,
in which PhD s uden s om h ee disciplines and i e indus y pa ne s col-
labo a e o design and de elop a decision suppo sys em o he c oss-sec o al
planning o ene gy dis ibu ion ne wo ks. Ene gy dis ibu ion ne wo ks a e e-
gional ne wo ks esponsible o anspo ing gene a ed ene gy o esiden ial o
indus ial ene gy consume s. Dis ibu ion Ne wo k Ope a o s (DNOs) mus de-
cide on when, whe e and how o ein o ce o expand hei ne wo k o e he nex
decades. When deciding o o agains in es men s, DNOs – like many deci-
sion make s – mus conside equen , unp edic able change in many in luencing
ac o s wi h unknown cause-e ec ela ionships [7,1,8]. In o de o make in es -
men decisions despi e hese challenging ci cums ances, DNOs hea ily ely on
assis ance p o ided in he o m o decision suppo sys ems (DSS).
?Funding p o ided by Eu opean Regional De elopmen Fund as pa o he esea ch
p ojec FlexiEne gy (g an numbe : EFRE-0801186).
1h ps:// lexi-ene gy.de/en
33

Du ing he design and de elopmen o a DSS o ene gy dis ibu ion ne wo k
planning in he con ex o ou esea ch p ojec , we encoun e ed di icul ies when
ying o de ine a holis ic planning p ocess o be suppo ed by he DSS. We
could a ibu e hese di icul ies o he ac ha he op imal planning p ocess
a ies be ween DNOs due o si ua ional ac o s. Fo ins ance, a DNO migh e-
qui e edundancy in hei ne wo k o suppo he ailu e o a single asse like
a ans o me o a cable, while ano he DNO does no equi e such ex a eli-
abili y. I he eliabili y equi emen s o DNOs do no align wi h he planning
p ocess implemen ed in he DSS, he p oposed ne wo k in es men s a e ei he
oo cos ly due o he included edundancy, o he esul ing ne wo k does no ul-
ill eliabili y equi emen s. Simila ly, we lea ned ha load o ecas s conside ing
consume echnologies such as PV-sys ems adop ed by indi idual buildings a e
mo e accu a e han o he app oaches. Howe e , a o ecas on he le el o indi-
idual buildings equi es many socio-economic in o ma ion abou he buildings
which a e no eadily a ailable o each DNO. Consequen ly, he holis ic plan-
ning p ocess suppo ed by he DSS likely needs o be ex ended wi h ac i i ies
o addi ional da a acquisi ion o ac i i ies need o be eplaced wi h app oaches
whose da a equi emen s a e ul illed.
While exchanging expe iences wi h colleagues wo king in o he esea ch p o-
jec s, I ound ha a “one-size- i s-all” decision suppo app oach can also be
subop imal in o he domains, e.g., du ing supply chain planning [14] o when
deciding on a business model [4]. Ins ead, a decision suppo sys em mus con-
side he con ex o decision make s, i.e., hei o e all goal and a ailable esou ces
such as da a se s, so wa e ools o ime o iden i y an op imal decision. I he e-
o e wan o add ess he ollowing esea ch ques ion in my disse a ion: How
can indi idualized decision suppo sys ems be p o ided ha a e ailo ed acco d-
ing o he con ex o indi idual decision make s, i.e., hei indi idual goals and
a ailable esou ces?
2 Rela ed Wo k and Resea ch Gap
A e iden i ying he need o decision suppo sys ems which a e ailo ed o in-
di idual decision make s, I iden i ied exis ing app oaches in he decision suppo
domain which seemed o add ess a ela ed p oblem.
Adap i e DSS (ADSS) a e decision suppo sys ems which “suppo hu-
man decision making judgemen s by adap ing suppo o he high-le el cogni i e
needs o he use s, ask cha ac e is ics, and decision con ex s” [3]. Howe e , hese
sys ems only seem o conside he selec ion o a single model ac oss a ( ixed) se
o models, which ende s hem unsui able o complex planning p oblems like
dis ibu ion ne wo k planning whe e mul iple models need o be combined, e.g.,
o load o ecas ing, ne wo k simula ion and ne wo k op imiza ion. Fu he mo e,
he a ailabili y o esou ces like da a se s o ime o iden i y a decision is no
included in he decision con ex and he e o e no conside ed du ing adap a ion.
DSS Gene a o s a e “a se o ools o suppo he design and cons uc ion
o a [...] DSS” [9]. Howe e , I did no ind any gene al-pu pose DSS gene a o s
34
which can be u ilized in any applica ion domain, in pa icula ene gy dis ibu-
ion ne wo k planning. Fu he mo e, he gene a o s a e usually no mean o be
di ec ly used by decision make s bu by ained “implemen o s”, which can add
a signi ican delay be ween he decision make equi ing suppo and an ac ual
DSS being a ailable.
In he domain o compu e science, he e a e wo pa icula app oaches which
a e pa ially ela ed o ailo ed decision suppo sys ems:
Si ua ional Me hod Enginee ing aims o “design, cons uc and adap
me hods, echniques and ools o sys ems de elopmen [...] o a speci ic si u-
a ion” [5]. The ou pu howe e is a me hod o de eloping a sys em which is
enac ed by he de elopmen eam, no an ac ual DSS which can be used by a
decision make [2].
Da a Ecosys ems a e “a se o ne wo ks composed by au onomous ac o s
ha di ec ly o indi ec ly consume, p oduce o p o ide da a and o he ela ed
esou ces (e.g., so wa e, se ices and in as uc u e)” [12]. Howe e , con a y
o he de ini ion, many da a ecosys ems (o e en “decision suppo ecosys ems”
[13]) only ocus on p o iding and exchanging da a and igno e ela ed esou ces,
which nulli ies he oppo uni y o c ea e a holis ic DSS.
In conclusion, I did no ind any exis ing app oach which su icien ly add esses
decision make s’ demands o ailo ed decision suppo sys ems.
3 Solu ion Concep
Al hough none o he app oaches p esen ed in he p e ious sec ion ully ad-
d esses he demand o decision make s o ailo ed decision suppo sys ems,
all app oaches include concep s which con ibu e owa ds his goal. I he e o e
de i ed a solu ion concep om hese app oaches wi h he aim o combine hei
ad an ages while imp o ing on hei downsides. The solu ion concep is p e-
sen ed in Fig. 1 and subsequen ly explained in de ail ollowing he depic ed
h ee phases.
The ini ial phase is he Con ex Iden i ica ion phase. Du ing his phase, he
Decision Make in e ac s wi h he Con ex Module o documen he decision
con ex , i.e., he decision o be made and he a ailable esou ces. Fo he Con-
ex Module o know which aspec s o p omp he Decision Make o , a Do-
main Expe mus p o ide a Domain On ology desc ibing decision p oblems in
he ele an domain. This documen a ion o he domain’s cha ac e is ics may
also include in o ma ion abou equen ly analysed decision p oblems. Based on
he eedback p o ided by he Decision Make , he Con ex Module p oduces a
machine- eadable Decision Con ex Fo maliza ion o he decision p oblem and
esou ces.
The Decision Con ex Fo maliza ion is subsequen ly used in he Composi ion
Module o he Decision Suppo Composi ion phase. The goal o his phase is o
assemble mul iple Decision Se ices in o a Decision Suppo Composi ion which
ep esen s an ideal planning p ocess o he decision con ex o he Decision
Make . Fo his pu pose, mul iple Decision Se ice P o ide p o ide a Decision
35
Phase 3:
Decision Making
Phase 2:
Decision Suppo Composi ion
Phase 1:
Con ex
Iden i ica ion
Decision Make
Con ex
Module
Domain Expe
Decision Se ice
P o ide
Composi ion
Module
Decision Se ice
Desc ip ion
Decision Suppo Enginee
Decision Se ice
Reposi o y
Decision Suppo
Module
Decision Recommenda ions
Execu ion
Knowledge
Composi ion Assis ance
Knowledge
Reposi o y
Domain
On ology
Decision Con ex Fo maliza ion Domain
Knowledge
Decision Suppo Composi ion
Legend:
Da a Flow
In e ac ion
Tailo ed DSS
Fig. 1. De i ed solu ion concep o p o iding ailo ed decision suppo sys ems
Se ice Desc ip ion o hei a ailable decision se ices (e.g., so wa e, da a o
compu e in as uc u e) in a Decision Se ice Reposi o y. The composi ion o
decision se ices can be pe o med manually by a Decision Suppo Enginee o
pa ially/ ully au oma ed by a Composi ion Assis ance (see [11] o he ele ance
o such assis ance). A Knowledge Reposi o y p o ides in o ma ion o iden i y
ideal composi ions based on Domain Knowledge p o ided by Domain Expe s o
expe ience ga he ed du ing p e ious se ice execu ions (Execu ion Knowledge).
I is impo an o no e ha a single pe son can op ionally ac in mul iple oles,
e.g., a Decision Make may be in ol ed in se ice composi ion as a Decision
Suppo Enginee o p o ide hei own da ase s o o he decision se ices as a
Decision Se ice P o ide .
Finally, in he Decision Making phase, he Decision Suppo Module in okes
he decision se ices as desc ibed by he p e iously assembled Decision Suppo
Composi ion. Fo his pu pose, addi ional un- ime inpu by he Decision Make
36
migh be necessa y. The esul ing Decision Recommenda ions a e o wa ded o
he Decision Make . F om a a Decision Make ’s poin o iew, he ailo ed DSS
beha es simila o a adi ional DSS du ing his phase.
4 Resea ch App oach and Nex S eps
My esea ch app oach can be aligned wi h He ne ’s h ee cycle iew o design
science esea ch [6] shown in Fig. 2. Wi h espec o he Rele ance Cycle, I
al eady de i ed he need o ailo ed decision suppo sys ems om he applica-
ion domain o ene gy dis ibu ion ne wo k planning (c . Sec . 1). I also de i ed
some high-le el Requi emen s and u he mo e e alua ed exis ing S a e-O -The-
A a i ac s, me hods and concep s (c . Sec . 2), he eby pa ially add essing
he Rigo Cycle. The Design & De elopmen o he Design Cycle is pa ially
add essed wi h he solu ion concep p esen ed in he p e ious Sec . 3.
Nex , I will ocus on de eloping he de ails o he solu ion concep , i.e., he
modules, documen s, eposi o ies and oles shown in Fig. 1. Fo his pu pose,
I plan o apply a design science esea ch app oach as shown in Fig. 2 o he
indi idual phases o he solu ion concep . Again, I can u ilize he applica ion
domain o ene gy dis ibu ion ne wo k planning and exis ing knowledge such as
me hods o equi emen s enginee ing, se ice composi ion and se ice o ches a-
ion. Wo king on he indi idual phases o he solu ion concep al eady p o ides
a pa ial E alua ion o he o e all solu ion concep .
Las ly, I wan o p o o ypically implemen he solu ion concep and conduc
aField Tes by using he p o o ype in he applica ion domain o ene gy dis i-
bu ion ne wo k planning h ough my esea ch p ojec . Based on he comple ed
ele ance, design and igo cycle o bo h he o e all concep and i s indi idual
phases, I expec o con ibu e design p inciples [10] o ailo ed decision suppo
sys ems as an Addi ion To Knowledge.
Applica ion
Domain
Design Science
Resea ch
Knowledge
Base
Design
Cycle
Rigo
Cycle
Rele ance
Cycle
Field Tes ing
Requi emen s Addi ions o
knowledge
S a e-o - he-A
Design &
De elopmen
E alua ion
Fig. 2. Resea ch app oach (adap ed om [6]) including p og ess
37
7. Jiang, B., Liu, Y., Chan, W.: Con ac uzze : Fuzzing sma con ac s o ulne abili y de ec-
ion. In: 2018 33 d IEEE/ACM In e na ional Con e ence on Au oma ed So wa e Enginee -
ing (ASE). pp. 259–269. IEEE (2018)
8. Liu, C., Liu, H., Cao, Z., Chen, Z., Chen, B., Roscoe, B.: Regua d: Finding een ancy bugs
in sma con ac s. In: 2018 IEEE/ACM 40 h In e na ional Con e ence on So wa e Engi-
nee ing: Companion (ICSE-Companion). pp. 65–68 (2018)
9. Liu, J., Liu, Z.: A su ey on secu i y e i ica ion o blockchain sma con ac s. IEEE Access
7, 77894–77904 (2019)
10. Meha , M.I., Shie , C., Giamba is a, A., Gong, E., Fle che , G., Sanayhie, R., Kim, H.M.,
Laskowski, M.: Unde s anding a e olu iona y and lawed g and expe imen in blockchain:
The dao a ack. J. Cases In . Technol. 21, 19–32 (2019)
11. No ill, R., Fiz, B., S a e, R., Cullen, A.: S anda dising sma con ac s: Au oma ically in-
e ing e c s anda ds. In: 2019 IEEE In e na ional Con e ence on Blockchain and C yp ocu -
ency (ICBC). pp. 192–195 (2019). h ps://doi.o g/10.1109/BLOC.2019.8751350
12. Pie o, G.A., Tonelli, R., Ma chesi, M.: Sma -co pus: an o ganized eposi o y o e he eum
sma con ac s sou ce code and me ics (2020)
13. P ai heeshan, P., Pan, L., Yu, J., Liu, J., Doss, R.: Secu i y analysis me hods on e he eum
sma con ac ulne abili ies: A su ey (2020)
14. Sam een, N.F., Alal i, M.H.: Sma scan: An app oach o de ec denial o se ice ulne abili y
in e he eum sma con ac s (2021)
15. Tonelli, R., Des e anis, G., Ma chesi, M., O u, M.: Sma con ac s so wa e me ics: a i s
s udy (2018)
16. Wang, S., Zhang, C., Su, Z.: De ec ing nonde e minis ic paymen bugs in e he eum sma
con ac s. P oceedings o he ACM on P og amming Languages 3(OOPSLA), 1–29 (2019)
17. Wang, W., Song, J., Xu, G., Li, Y., Wang, H., Su, C.: Con ac wa d: Au oma ed ulne abili y
de ec ion models o e he eum sma con ac s. IEEE T ansac ions on Ne wo k Science and
Enginee ing (2020)
18. Zhang, Y., Ma, S., Li, J., Li, K., Nepal, S., Gu, D.: Sma shield: Au oma ic
sma con ac p o ec ion made easy. In: 2020 IEEE 27 h In e na ional Con e ence
on So wa e Analysis, E olu ion and Reenginee ing (SANER). pp. 23–34 (2020).
h ps://doi.o g/10.1109/SANER48275.2020.9054825
44

G oup Recommende Sys em: a Con e sa ional
App oach o Suppo G oup Discussion
Hani Emamgholizadeh1[0000−0002−7159−3574]
F ee Uni e si y o Bolzano, I aly [email p o ec ed]
Abs ac . Wi h he widesp ead usage o in e ne , in o ma ion o e load
has become a c i ical issue o in e ne use s. In his scena io, ecom-
mende sys ems, which a e ools ha p o ide ele an sugges ions abou
i ems ha indi idual use s could like o use, ha e been in oduced. In
some cases, he sea ched i ems a e mean o be consumed by a g oup
o use s, e.g., a holiday package o a mo ie o wa ch. Hence, also g oup
ecommende sys ems (GRS), which a e aimed a iden i ying i ems ha
can sui all he g oup membe s, ha e been de eloped. Some GRSs ad-
d ess his p oblem by cons uc ing a g oup p o ile, i.e., a model ha
summa izes he p e e ences o he g oup by combining he p e e ences
o he g oup membe s. By using his g oup, p o ile ecommenda ions o
he g oup a e iden i ied. Bu , a g oup decision, which should be sup-
po ed by he GRS, is o en made a e a discussion, whe e he g oup
membe s’ p e e ences may e ol e in a dynamic way. To model such a
dynamic decision-making p ocess, new GRSs ha e been in oduced.
In my Ph.D. esea ch, I am ying o imp o e he s a e-o - he-a ap-
p oaches o modeling g oup decision-making dynamics by conside ing
he social and pe sonal aspec s o he g oup membe s. This model can
be u ilized o an icipa e he g oup choice, which can hen be used o
suppo he g oup membe s in imp o ing hei decision-making p ocess.
This suppo can be o e ed by p o iding mo e in o ma ion abou he
i em ha is p edic ed o be he g oup’s choice, p o iding new i ems
simila o he g oup choice, e c.
Keywo ds: Recommende Sys ems ·G oup Recommende Sys ems ·
G oup Dynamics ·Food Recommende Sys ems
1 In oduc ion
In o ma ion o e load has made ecommende sys ems a necessa y ool o daily
li e. Recommende sys ems a e so wa e o echniques ha p o ide some sugges-
ions abou i ems ha use s like o use [11]. In addi ion o indi idual li e, we a e
also a membe o se e al g oups and cons an ly engage in he di e en g oups’
decision-making p ocess, a decision like whe e o go o a weekend in a amily
g oup, o whe e o ea wi h iends. Gene ally, a g oup o people s a s a dis-
cussion abou he po en ial op ions o an issue. In his discussion, he membe s
suppo some i ems and y o pe suade o he membe s o accep hei poin
45
2 H. Emamgholizadeh
o iew. These kinds o g oup ac i i ies emba k on new needs which canno be
sa is ied using indi idual ecommende sys ems.
In indi idual ecommende sys ems, he sys em’s main goal is pe sonalizing
he ecommenda ions o a speci ic use , ha is, ecommending i ems o a use
conce ning he pe sonal p e e ences. Whe eas in a GRS, he main objec i e
is ecommending i ems o a collec ion o use s who ha e made a g oup o a
speci ic pu pose. Unlike indi idual ecommende sys ems ha deal wi h only one
use , GRSs need o be able o agg ega e he indi idual use s’ p e e ences and
p o ide i ems o inc ease he g oup’s sa is ac ion in hei decision-making p ocess
compa ed o he si ua ion ha he g oup membe s do no use he sys em’s
suppo . By agg ega ion, he sys em ies o combine indi idual p e e ences using
a ma hema ical unc ion. In GRSs, he sys em deals wi h a g oup o people
ins ead o an indi idual.
A g oup o people engages in a discussion when hey make a decision. Re-
sea ch has shown ha he ou come o his discussion can be comple ely di e en
om he p edic ed ou come conside ing he use s’ ini ial p e e ences [4]. The sa -
is ac ion o a g oup membe also elies on he sa is ac ion o o he g oup mem-
be s. Al hough his change, known as emo ional con agion, depends on pe sonal
cha ac e is ics and in e pe sonal ela ionships, i s in luence on g oup decision-
making has been shown by some o he s udies [8]. Addi ionally, people end
o align hei opinion wi h o he g oup membe s’ pe spec i es e en in s aigh -
o wa d asks [8]. Hence, p edic ing g oup sco es (sco es ha compu ed by a
me hod o e lec how he g oup hink abou he i em), ecommending p ope
i ems o he g oup, and suppo ing g oup discussion and decision-making p ocess
a e he objec i es o GRSs.
The me hods which conside ecommending o sco e es ima ion p oblem o
a g oup can be di ided in o h ee main classes [7]. The i s class includes adi-
ional me hods ha y o cons uc a g oup p o ile using linea me hods, such
as a e aging g oup membe p e e ences. This g oup p o ile can be conside ed as
he p e e ences o he g oup’s ep esen a i e use . The second class o me hods is
heu is ic me hods ha use some heu is ics o agg ega e p e e ences and ecom-
mend i ems [6, 2]. Fo example, Go la e al. [6] de eloped a g aph-based me hod
ha akes bo h nega i e and posi i e aspec s o g oup membe s in o accoun .
In his model, wo simila i y-based g aphs wi h posi i e and nega i e edges a e
cons uc ed o he use s and i ems. The main heu is ics in his me hod a e: (i)
po en ial g oup choice will be close o he g oup’s p e ious choices, and (ii) in-
app op ia e i ems will be nea he g oup’s p e iously disliked i ems. Then, using
a andom walk, he ecommenda ions o he g oups a e p oduced. Finally, new
me hods y o use machine lea ning app oaches o ain a model o es ima ing
he choices o g oups based on his o ical da a [10]. Using di e en aspec s o he
g oups and use s, deep models y o ind he p ope embedding o g oups and
i ems. Then, hese embedding can be used o choice p edic ion [1].
46
Ti le Supp essed Due o Excessi e Leng h 3
2 Resea ch Ques ions and Fu u e Wo ks
Mos o he s udies on GRSs, which some o hem ha e been in oduced abo e,
ha e been dedica ed o p edic ing g oup sco es o i ems in a s a ic en i onmen
(single-sho ). These sco es a e u he used o de e mine which i em will be
liked by mos g oup membe s, and he s a emen ”liked by he mos ” shows
how di e en app oaches look a his p oblem. Howe e , g oup decision-making
is a dynamic p ocess in which he g oup decision is being made du ing he g oup
discussion [4, 5]. Discussion can happen in a cha -based en i onmen o in ace-
o- ace communica ions. In his discussion, he g oup membe s discuss he p os
and cons o he cu en op ions and selec one. Du ing his discussion, membe s’
opinions abou he op ions can be changed based on o he membe s’ suppo s o
ejec ion. To deal wi h his si ua ion, ecommende sys ems should con inuously
moni o he g oup beha io , in e ac ions, and p e e ences and adjus he sys em
and ecommenda ions based on he changes in he membe s’ p e e ences.
In my Ph.D. s udy, I will y o s udy his dynamic p ocess and in eg a e
i wi h he social and pe sonal aspec s o use s. As discussed abo e, social e-
la ions and discussion opics also play a ole in he p e e ences’ changes du ing
a discussion. Fo ins ance, in a hie a chical amily, social ela ions play a mo e
impo an ole han pe sonali y. In his case, he social ela ions de e mine he
g oup choice and p obably p e e ence changes. The opic is ano he de e mina-
i e aspec . G oup membe s’ beha io can change based on he opic on which
hey a e discussing. Fo example, i he g oup is discussing a sensi i e poli ical
issue, he membe s’ beha io can be comple ely di e en compa ed o he si -
ua ion ha hey a e discussing whe e should be he nex dinne pa y o he
poli ical pa ies. These dimensions can ha e an impo an in luence on he g oup
dynamics and p e e ence e olu ion.
As i is clea , c ea ing use s and g oup p o iles conce ning social ela ions and
pe sonal cha ac e is ics is no i ial. De eloping algo i hms ha can moni o
g oup dynamics (wi h espec o pe sonal cha ac e is ics, social ela ions, and
discussion opics), c ea e use s and g oup p o iles, and adap hem wi h g oup
p e e ence change is he ul ima e goal o his esea ch. In o he wo ds, I will
esea ch how he use s’ p e e ences e ol e du ing a g oup discussion, how much
hese e ol ing p e e ences a e di e en o di e en g oups, opics, and membe s’
pe sonali ies, and how we can suppo a a ie y o g oups wi h a ying cha ac e -
is ics in hei decision-making p ocess. This suppo aims a making he decision
p ocess easy and pleasan o he membe s. In he ollowing, I discuss he main
p oblems I will ackle in his Ph.D. esea ch.
– Ques ion1. An essen ial ques ion in GRS is how we can e ec i ely model
he g oup discussion dynamics o ecommend p ope i ems and suppo he
g oup be e . Based on pe sonal and social ela ions, people beha e di e -
en ly in di e en g oup discussions. Fo ins ance, child en beha e di e en ly
in a amily g oup compa e o a iend g oup. Addi ionally, people beha e
di e en ly, e en in he same g oup, when hey discuss di e en opics. Fo
ins ance, he con o e sy le el in making a poli ical decision be ween he
47
4 H. Emamgholizadeh
pa ies is much highe han he con o e sy le el when hey make a deci-
sion abou non-sensi i e social issues. These con adic ing beha io s in he
di e en g oups by he same people o he same g oup on a ious opics
should be aken in o accoun o modeling g oup dynamics. Nguyen e al. [9]
only conside ed one aspec o he g oup, which was con lic esolu ion s yle;
bu as we explained abo e, he e is some o he in o ma ion abou he g oup,
use s, and opic unde discussion which a e able o p o ide mo e in o ma ion
abou he g oup dynamics, as hey p o ide us b oade pe spec i e owa d
he g oup and i s dynamics. I we model a g oup discussion ha akes in o
accoun his in o ma ion, we can p edic he g oup’s p e e ences in di e en
ci cums ances and adjus ou ecommende sys em wi h hese new p e e -
ences. Fo ins ance, i du ing he discussion o selec ing a des ina ion o
he nex ip, a g oup decided o go o he beach, he sys em should pu
aside all o he ecommenda ions ela ed o moun ains.
– Ques ion2. A GRS is made o wo en i ies: Sys em and G oup. The g oup
consis s o membe s. These membe s can be desc ibed based on social ela-
ions and pe sonal a i udes. Fo modeling g oup discussion dynamics, we
can conside each use ’s pe sonal a ibu es, such as openness o new expe i-
ences, ex o e ism, e c., and social ea u es, like ype o ela ions, s uc u e
o he iendship, e c. Hence, ano he esea ch ques ion is whe he we can
e icien ly combine use s’ social and pe sonal aspec s o he sys em. I so,
how.
Mos o he p e ious wo ks ha e conside ed social and pe sonal a i udes
in he s a ic en i onmen [3]. Nguyen e al. [9] we e one o he i s who
s udied pe sonal a i udes, speci ically con lic esolu ion s yle, in a dynamic
en i onmen . In ou u u e esea ch, we will ocus on ex ual in o ma ion p o-
ided by g oup membe s. This ex ual in o ma ion, exp essed by he g oup
membe s du ing a discussion, can indica e hei cu en s and (sho - e m
p e e ences) wi h espec o he discussion and he g oup’s possible op ions.
O he ex ual in o ma ion can also be exploi ed. Fo ins ance, he e a e some
s udies on de ec ing use s’ pe sonali ies using use s’ ex ual da a in he so-
cial ne wo ks [13]. Fu he mo e, based on social ela ions, g oup membe s
ac di e en ly in he g oups. Fo ins ance, one may be mo e amenable in
a iend g oup decision-making p ocess; whe eas, he same pe son can be
mo e esolu e in a wo king g oup. We also y o in eg a e he membe s’
social dimension in o he dynamic GRS o ind mo e accu a e p edic ions,
ecommenda ions, and be e suppo .
– Ques ion3. Ha ing de ined he impo an social and pe sonal a ibu es o
use s as well as he discussion model, ou nex ques ion is how o p edic
he g oup’s inal choice accu a ely and sa is ac o ily ecommend i ems o he
g oup o suppo ing he membe s. Wi h p edic ion, he GRS can es ima e
he inal g oup choice. This inal choice can be u ilized o suppo he g oup
by helping hem o each a consensus in a sho e ime o e en disco e new
op ions simila o his p edic ed inal choice, which seems o be in e es ing o
he g oup. Unlike he a o emen ioned s udies, which y o p edic he g oup
sco es o i ems in a single-sho si ua ion, we will y o p edic g oup choice
48
Ti le Supp essed Due o Excessi e Leng h 5
in a dynamic ci cums ance by moni o ing he use s’ beha io and upda ing
he g oup sco es. The co esponding ecommenda ions should help he g oup
o keep hei ocus on he unde lying ques ion, conside new undisco e ed
a eas, and ha e a mo e pleasan discussion.
I belie e ha he u u e ecommende sys em should play a mo e ac i e ole
in he decision-making p ocess. These p oac i e GRSs should help he g oup
membe s ha e a be e expe ience in a discussion and aid hem in inding a be e
solu ion o hei p oblem, which can maximize he g oup membe s’ sa is ac ion.
The e o e, I wan o de elop a con e sa ional GRS. This con e sa ional GRS
mus play a p oac i e ole in he g oup decision-making p ocess. This me hod
should be adap ed wi h e ol ing g oup p e e ences and, in each s ep, suppo
hem o expe ience a mo e sa is ac o y discussion. This con e sa ional me hod
should di ec ly deal wi h g oup membe s and help hem end up wi h a choice
ha can maximize all g oup membe s’ sa is ac ion.
An applica ion domain in which I can implemen and e alua e he discussed
idea is he ood domain, in which a g oup o people wan s o selec a es au an
o go o wi h espec o hei p e e ed dishes. The p oblem I am going o add ess
is de eloping a p oac i e GRS ha adap s he g oup p e e ences e olu ion using
he da a p o ided by he use s in only one session (implici o explici ). This
session is empo a y in e ac ion o he use s wi h he sys em om he ime hey
en e o un il he momen ha hey lea e he sys em. This is a challenging
p oblem as we do no ha e his o ical da a abou bo h use s and g oups.
3 Resea ch Resul s
I s a ed my esea ch by wo king on a p ojec known as P edic ing G oup Choices
om G oup P o iles. As discussed abo e, GRSs aim o lea n use s’ p e e ences
and beha io om his o ical da a o p edic g oup choice. Al hough a signi ican
numbe o s udies ha e been dedica ed o p edic ing g oup sco es, a small po ion
o hem has conside ed p edic ing g oup choice as a p oblem.
SDS heo y [12], which in es iga ed he p oblem o combining g oup mem-
be s’ indi idual p e e ences o p edic ing he discussion ou come, is he basis
o ou s udy. In his esea ch, S asse aimed a answe ing wo ques ions: (i) how
a e he inclina ions o indi iduals combined o each a consensus in a g oup?,
and (ii) wha a e he implica ion o he indings in a se o condi ions o ano he
si ua ion? The me hod we a e wo king on ies o ain a machine lea ning model
o p edic he inal choice o a g oup decision-making p ocess. Indeed, he model
in ends o lea n he g oup composi ion (dis inguishable dis ibu ions), ha is,
how he g oup membe s hink abou he possible op ions ( he i s ques ion o
S asse ’s wo k) and use his dis ibu ion o p edic he inal choice o a g oup
(second ques ion o S asse ’s wo k). Ou me hod au oma ically lea ns how o
cons uc a g oup p o ile and how om a g oup p o ile, he g oup choice can be
p edic ed, as S asse also men ioned ha his ela ionship could be lea ned.
In he u u e, we in ended o imp o e ou model o conside mo e g oup
choices. In ou g oup choice model, we only concen a ed on g oup choices when
49

6 H. Emamgholizadeh
he al e na i e op ions a e ew. We wan o examine o wha ex en ou me hod
is good in dealing wi h mo e op ions o he g oups. We a e also ying o use
o he g oup ea u es, such as g oup size, discussion ime, e c., o see whe he
hey a e in o ma i e enough o he model.
Re e ences
1. Cao, D., He, X., Miao, L., An, Y., Yang, C., Hong, R.: A en i e g oup ecom-
menda ion. In: The 41s In e na ional ACM SIGIR Con e ence on Resea ch &
De elopmen in In o ma ion Re ie al. pp. 645–654 (2018)
2. Ca alho, L.A.M.C., Macedo, H.T.: Use s’ sa is ac ion in ecommenda ion sys ems
o g oups: an app oach based on noncoope a i e games. In: P oceedings o he
22nd In e na ional Con e ence on Wo ld Wide Web. pp. 951–958 (2013)
3. Ch is ensen, I.A., Schia ino, S.: Social in luence in g oup ecommende sys ems.
Online In o ma ion Re iew (2014)
4. Delic, A., Neidha d , J., Nguyen, T.N., Ricci, F., Rook, L., We hne , H., Zanke ,
M.: Obse ing g oup decision making p ocesses. In: P oceedings o he 10 h ACM
con e ence on ecommende sys ems. pp. 147–150 (2016)
5. Fo sy h, D.R.: G oup dynamics. Cengage Lea ning (2018)
6. Kim, H.N., Bloess, M., El Saddik, A.: Folkommende : a g oup ecommende sys em
based on a g aph-based anking algo i hm. Mul imedia sys ems 19(6), 509–525
(2013)
7. Mas ho , J.: G oup ecommende sys ems: agg ega ion, sa is ac ion and g oup
a ibu es. In: ecommende sys ems handbook, pp. 743–776. Sp inge (2015)
8. Mas ho , J., Ga , A.: In pu sui o sa is ac ion and he p e en ion o emba ass-
men : a ec i e s a e in g oup ecommende sys ems. Use Modeling and Use -
Adap ed In e ac ion 16(3), 281–319 (2006)
9. Nguyen, T.N., Ricci, F., Delic, A., B idge, D.: Con lic esolu ion in g oup deci-
sion making: insigh s om a simula ion s udy. Use Modeling and Use -Adap ed
In e ac ion 29(5), 895–941 (2019)
10. O ega, F., He nando, A., Bobadilla, J., Kang, J.H.: Recommending i ems o g oup
o use s using ma ix ac o iza ion based collabo a i e il e ing. In o ma ion Sci-
ences 345, 313–324 (2016)
11. Ricci, F., Rokach, L., Shapi a, B.: Recommende sys ems: in oduc ion and chal-
lenges. In: Recommende sys ems handbook, pp. 1–34. Sp inge (2015)
12. S asse , G.: A p ime o social decision scheme heo y: Models o g oup in luence,
compe i i e model- es ing, and p ospec i e modeling. O ganiza ional Beha io and
Human Decision P ocesses 80(1), 3–20 (1999)
13. Tay, L., Woo, S.E., Hickman, L., Sae , R.M.: Psychome ic and alidi y issues in
machine lea ning app oaches o pe sonali y assessmen : A ocus on social media
ex mining. Eu opean Jou nal o Pe sonali y 34(5), 826–844 (2020)
50
Resou ce Managemen in MEC Ne wo ks
Bin Xiang
Dipa imen o di Ele onica, In o mazione e Bioingegne ia,
Poli ecnico di Milano, I aly
[email p o ec ed]
Abs ac . In he 5G and beyond mobile ne wo ks, Mobile Edge Com-
pu ing (MEC) b ings cloud-compu ing capabili ies o he edge o he
mobile ne wo ks, especially in close p oximi y o mobile use s, making
i possible o simul aneously add ess he s ingen la ency equi emen s
o c i ical se ices and ensu e e icien ne wo k ope a ion and se ice
deli e y.
Howe e , MEC se ices, on one hand, equi e signi ican in es men s
om bo h ne wo k ope a o s and se ice p o ide s in e ms o deploy-
ing, ope a ing and managing edge clouds, and on he o he hand, p o ide
limi ed compu a ional and s o age esou ces by design. Besides, due o
he la ge amoun o asks om use s wi h high demands du ing peak
hou s, he la ency equi emen s o di e en se ices can ha dly be gua -
an eed. This issue can be ackled by massi ely deployed edge clouds ha
a e a ached o he base s a ions and connec ed o each o he in a speci ic
opology, as ul a-dense 5G-and-Beyond ne wo ks a e buil .
The goal o his esea ch is o le e age coope a ion among in e connec ed
mul iple MEC uni s and in es iga e join esou ce op imiza ion conside -
ing mul iple aspec s o ne wo k ope a ions, wi h he a ge o enhancing
he u iliza ion e iciency o esou ces o u he sa is y imp o ed QoS
and educe ne wo k ope a ion cos . Speci ically, agg ega ed mobile a -
ic and use eques s a e conside ed based on hei ypes (e.g., ideo,
web, game, e c.) associa ed wi h di e en QoS equi emen s. This e-
sea ch join ly op imizes i) whe e o p ocess he a ic and eques s, ii)
how o ou e ne wo k lows and iii) how o alloca e and schedule he e-
qui ed esou ces w. . . communica ion, compu a ion and s o age. These
p oblems a e o mula ed in o mul iple ma hema ical models and bo h
cen alized and decen alized app oaches a e p oposed o ackle hem
e icien ly. The pe o mance is e alua ed in eal-size ne wo k scena ios
including bo h andom geome ic g aphs and a ealis ic mobile ne wo k
opology, showing he impac o he conside ed pa ame e s (e.g., ole -
able la ency, ne wo k opology and bandwid h, compu a ion, s o age,
e c.) on bo h he op imal and app oxima e solu ions.
Keywo ds: mobile edge compu ing · esou ce managemen ·op imiza ion
1 In oduc ion
In a ne wo k wi h he in e connec ed mul iple MEC nodes, he e icien deli e y
o nex gene a ion se ices equi es join op imiza ion o whe e o execu e each
51
se ice eques , how o ou e ne wo k lows and how o alloca e and schedule
he equi ed esou ces w. . . communica ion, compu a ion, s o age, in o de o
mee he imp o ed QoS.
The goal o his esea ch is o s udy esou ce managemen o MEC ne -
wo ks wi h a bi a y opology. Mo e speci ically, se e al p oblems a e add essed,
mainly ela ed o slicing[1], planning[2] and scheduling[3, 4] o edge esou ces o
mobile a ic.
The i s scena io is an edge ne wo k o ganized by mul iple edge clouds, each
o which is connec ed o he Radio Access Ne wo k a a ce ain loca ion. All
such edge clouds a e connec ed h ough a ious opologies, ypically o ganized
in some kind o hie a chy. In his way, each edge cloud can se e end use a ic
by elying no only on i s own esou ces, bu also o loading some a ic o i s
neighbo s when needed. In his edge ne wo k, mobile use a ic coming om one
access ne wo k is conside ed, which is agg ega ed acco ding o he di e en ypes
(e.g., oice, ideo, web, game, e c.) associa ed wi h di e en QoS equi emen s on
use expe ienced la ency. Each class o a ic can be segmen ed and p ocessed
on all edge clouds, and each edge cloud can slice i s compu a ion capaci y o
se e di e en classes o a ic. Speci ically, o each class o incoming a ic,
he co esponding mobile access ne wo k decides how o slice wi eless ne wo k
capaci ies while he co-loca ed edge cloud decides i) whe he o se e he a ic o
o o load i o some o he edge cloud nodes and ii) how o alloca e compu a ion
capaci ies o he pieces o a ic. This decision depends on he QoS equi emen s
associa ed wi h he speci ic class o a ic and on he cu en s a us o he edge
cloud. The main objec i e in his con ex is o ensu e ha he in as uc u e is
able o se e all he possible ypes o a ic wi hin he bounda ies o hei QoS
equi emen s and o he a ailable esou ces. A join slicing o mobile ne wo k and
edge compu a ion esou ces is p oposed. The e o e, he p oposed op imiza ion
app oach aims a minimizing he o al a ic la ency o ansmi ing, ou sou cing
and p ocessing use a ic, unde cons ain s o use ole able la ency o each
class o a ic.
The i s p oblem ocuses exclusi ely on minimizing he la ency o a ic in a
hie a chical edge ne wo k, wi h he ne wo k and compu a ion capabili ies ixed.
Fu he , he p oposed second p oblem akes in o accoun he o e all budge ha
he ope a o uses in o de o plan and alloca e he compu a ion capabili ies in
i s edge ne wo k which also has an a bi a y opology. Mul iple classes o mo-
bile use a ic om mul iple access ne wo ks (o mul iple ing ess ne wo ks) a e
conside ed. The main objec i e is o u he ope a e cos -e icien edge ne wo ks
h ough join ly planning he a ailabili y o compu a ional esou ces a he edge,
he slicing o he mobile ne wo k and edge compu a ion esou ces, and he ou -
ing o he e ogeneous a ic ypes o he a ious slices. The e o e, he p oposed
op imiza ion app oach in he second p oblem aims a minimizing he ne wo k
ope a ion cos s and he o al a ic la ency o ansmi ing, ou sou cing and
p ocessing use a ic, unde cons ain s o use ole able la ency o each class
o a ic.
52
Finally, he s udy ocuses on se ing di e en classes o use eques s in
MEC ne wo ks wi h a bi a y opology. Each ype o eques is ega ded as
an agg ega ed communica ion-compu a ion demand, e.g. web, ideo, game and
e c., which has o be accommoda ed in he ne wo k and equi es some amoun
o bandwid h, s o age and compu a ion esou ces. The calenda (i.e., he s a -
ing ime and du a ion) o he eques s o he upcoming pe iod is assumed o
be known, which can be achie ed unde he condi ion ha cus ome s ha e an-
nounced hei equi emen s in ad ance, o by using some his o y-based p edic-
ion ools. The main objec i e is o exploi he in insic lexibili y o se ices
demanded by di e en use s, he s a ing ime o which can be shi ed wi hou
penalizing he u ili y pe cei ed by he use s while, a he same ime, pe mi ing
a be e esou ce u iliza ion in he ne wo k. The e o e, The aim is o s udy an
op imiza ion amewo k ha join ly conside s se e al key aspec s o he esou ce
alloca ion p oblem in his con ex , speci ically, h ough op imizing: i) admission
decision (which eques s a e admi ed and se ed by he ne wo k), ii) scheduling
o admi ed eques s, also called calenda ing, iii) ou ing o hese lows, i ) he
decision o which nodes will se e such eques s as well as ) he amoun o p o-
cessing and s o age capaci y ese ed on he nodes chosen, wi h he objec i e o
maximizing he ope a o ’s p o i .
The abo e p oposed op imiza ion models a e i s o mula ed as mixed-
in ege nonlinea p og amming (MINLP) p oblems, which a e N P-ha d. To
ackle hem e icien ly, Equi alen e o mula ions om MINLP o mixed-in ege
quad a ically cons ain p og amming (MIQCP) a e pe o med, and based on
ha , u he e ec i e heu is ics a e p oposed o acili a e he solu ions o he
p oblems, including he Sequen ial Fixing based app oaches and a dis ibu ed al-
go i hm based on Al e na ing Di ec ion Me hod o Mul iplie s (ADMM) o he
edge calenda ing model. The pe o mance o he p oposed models and heu is ics
a e e alua ed in eal-size ne wo k scena ios including bo h andom geome ic
g aphs and a ealis ic mobile ne wo k opology, showing he impac o all he
conside ed pa ame e s (i.e., di e en ypes o use a ic o eques s, ole a-
ble la ency, ne wo k opology and bandwid h, compu a ion, s o age and link
capaci ies) on bo h he op imal and app oxima e solu ions. Resul s ob ained
demons a e ha nea -op imal esou ce alloca ion solu ions can be achie ed by
he p oposed heu is ics in sho compu ing ime.
2 Fu u e Di ec ions
Fu u e di ec ions o his esea ch include in es iga ing he ollowing aspec s: i)
s udying con ex -awa e esou ce alloca ion p oblems in he MEC ne wo ks, ex-
ploi ing he con ex in o ma ion, e.g., he use a ic pa e ns o each se ice,
use densi y o he loca ion o each MEC uni , e c., analyzed by using he his-
o ical da a. In his way, MEC ne wo k esou ces can be alloca ed and scheduled
in ad ance so as o imp o e quali y o se ices while educing sys em cos s; ii)
aking in o accoun he dependence among ne wo k se ice unc ions and ocus-
ing on he op imiza ion o se ice unc ion chain (SFC, a se o se ice unc ions
53
Using Machine Lea ning o Speed Up
Op imiza ion o G aphical Models
Aleksand a Pe o a1[0000−0001−7485−5309]
Uni e si a Poli `ecnica de Ca alunya - UPC, Ba celona, Spain
[email p o ec ed]
Abs ac . The weigh ed CSP (WCSP) amewo k is a so cons ain
op imiza ion amewo k wi h a wide ange o applica ions. This ange is
achie ed by ha ing scien is s om di e en ields use he oulba 2 sol e
o hei espec i e p oblems. O en hese p oblems a e looked in o he
espec i e ields, howe e no in o ma ion is collec ed o sha ed om hese
solu ions o imp o e op imiza ion o o he p oblems. The goal o his
PhD esea ch is o u ilize he in o ma ion o he wide ange o p oblems
in op imiza ion and in eg a e Machine Lea ning o be e op imize he
algo i hms. Fo ha , a combina ion o s a is ical analysis on he di e en
p oblems and Machine Lea ning modeling will be used. The s a is ical
analysis will en ail disco e ing di e en pa e ns ha can be ound in he
p oblems, which poin o u ilizing his in o ma ion o u u e unknown
p oblems. Based o o ha , he models will be buil wi h he aim o
disco e ing hose pa e ns which will speed up he op imiza ion o u u e
unseen p oblems.
Keywo ds: Weigh ed CSPs ·T ee Decomposi ion ·Disc e e Op imiza-
ion ·Machine Lea ning ·Cons ain s P og amming.
1 In oduc ion
Cons ain s P og amming is a o m o p oblem sol ing in which he p oblem is
modeled as a se o decision a iables, each ha ing a se o possible alues, and
a se o cons ain s es ic ing he allowed combina ions o alues o a iables.
Cons ain s P og amming (CP) is a p omising ield o he u u e o A i icial In-
elligence (AI), as a lo o wha i ackles in luences he eal wo ld. No only ha ,
bu CP is key o eaching he goal o logical easoning in AI, as well as imp o -
ing op imiza ion which is o huge impo ance o ad ancing Compu e Science.
I am speci ically add essing a weigh ed e sion o hese p oblems called weigh ed
cons ain sa is ac ion p oblems (WCSPs). This amewo k has eal wo ld appli-
ca ions in a eas such as: Bioin o ma ics,Compu e ision,Sa elli e obse a ions,
P obabilis ic models,Ai plane landing,Wa ehouse loca ion p oblems and many
o he s.
One o he main ocus o CP so a has been o de elop be e and mo e e -
icien algo i hms. In he con ex o WCSPs he goal is o each he op imum in
he quickes way possible. This includes algo i hms ha p ep ocess he ins ances
60

so ha he di icul y o he cons ain s can be minimized, ha p une he sea ch
space and ha sea ch he space e icien ly. While he e has been a g ea deal
o ad ances in all 3 a eas, making he sol e s e y e icien , he p oblems a e
add essed as sepa a e en i ies, meaning each p oblem is es ed wi h di e en al-
go i hms o p uning and sea ch exploi ing o ob ain he bes esul . Resea che s
ha wo k in he ield o WCSPs ha e de eloped an in ui ion o knowing which
p oblem will be be e ackled wi h which algo i hms. This is no he case o
scien is s ha come om o he ields and use WCSP sol e s.
Despi e he solu ion o one pa icula ins ance being impo an in he con ex
o ha ins ance, he in o ma ion ha is used o sol ing i is no s o ed o used
o aid o he simila ins ances. Ins ances o one p oblem can also o en end up
ha ing simila i ies wi h each o he . E en di e en p oblems may end up also
ha ing simila i ies. Howe e , when sol ing hem, people a e unawa e o such
simila i ies exis ing in ano he a ea o p oblems, which hen esul s in simply
es ing many sol ing s a egies o ob ain he bes op imiza ion o ha p oblem.
One app oach o his issue is o use he powe o Machine Lea ning o make
mo e in o med decisions when sol ing he p oblems. My main esea ch goal is o
c ea e ools and algo i hms o e icien sol ing Weigh ed Cons ain Sa is ac ion
P oblems by ex ac ing in o ma ion om exis ing p oblems and using Machine
Lea ning o make in o med decisions when sol ing o he p oblems.
2 S a e o he a
We can ge mo e knowledge abou he op imiza ion p oblem we a e wo king on
by looking a i s g aph. O en p oblems ha ha e acyclic g aphs can be sol ed
in linea ime. The same doesn’ apply o cyclic ones. To be able o know his
in o ma ion we can look in o he ee decomposi ion o a p oblem. Using his
algo i hm we u n a g aph in o a ee [4]. This decomposi ion is e y o en used
o sol ing p oblems, such as guiding a dynamic p og amming algo i hm which
sol es he p oblem bo om-up.
To be able o bene i om he usage o he dynamic p og amming algo i hm,
he g aph needs o ha e small ee wid h [8, 3]. Wid h is he measu e o he size
o he la ges cyclic pa , whe e he ime and space complexi y a e exponen ial.
Sol ing using ee decomposi ion is encoun e ed in a di e en ype o p oblems
such as Bayesian Ne wo ks, Ma ko ne wo ks [7], Weigh ed CSPs [5, 9], and
o he s.
In he case ha he wid h is no small he sol ing elies on using sea ch
me hods such as Dep h- i s sea ch o Bes - i s sea ch. These algo i hms a e
mo e easible in compa ison o heu is ic sea ch algo i hms as hey can ge expo-
nen ial in p oblem size. Luckily he algo i hms ha e been be e op imizing, by
sol ing la ge ins ances in a good ime ame h ough p uning [6].
Ano he app oach o ee decomposi ion ega dless o he wid h is h ough
adap ing heu is ic sea ch o he p oblem decomposi ion. This is done by using
AND/OR sea ch [12]. By using his sea ch he memoiza ion is mo ed om ab-
ula o an implemen a ion o dynamic p og amming. The challenge he e posed
61
is o use all he p uning echniques which a e de eloped o heu is ic sea ch [14,
11, 2].
Fo he algo i hms o be sol ed he e is no a en ion paid o he choice o he
oo , bu he algo i hms do pick one. In he case o dynamic p og amming his
is no o impo ance since he wo s case complexi y is a igh bound o a e age
complexi y. In he case o o he algo i hms i has been epo ed ha he oo
can ha e an e ec on he pe o mance [10]. One such algo i hm which has been
ocusing on using back acking ee decomposi ion is he BTD algo i hm inside
oulba 2 [14], and he Russian doll sea ch exploi ing a ee decomposi ion [13].
So a he e has been li le ocus in he CP communi y o esea ching he
impac ha he choice o oo has o he o e all op imiza ion. One o he si ua-
ion whe e he selec ion o oo has been p io i ized is he pape o Absehe e
al. [1]. In hei pape hey c ea e a Machine Lea ning algo i hm which ocuses
on au oma ing he selec ion o he oo based on ea u es o he decomposi ion.
Thei ocus is on he dynamic p og amming app oach o sol ing ee decompo-
si ion. The esul s a e achie ed by using 5 di e en p oblems which esul in an
o e all 27.33% a e age imp o emen in compa ison o no using hei algo i hm.
Besides looking in o he decomposi ion i sel and he in o ma ion i can p o-
ide o he solu ion o he p oblem, ano he a ea in which esea ch has been
expanding is using in o he sea ch space. One such s udy is Lea ning B anching
Heu is ics o P oposi ional Model Coun ing [15]. He e he au ho s used e olu-
ion s a egies o lea n b anching heu is ics o SAT sol e s. Wi h hei solu ion
hey a e able o educe he s ep coun and gene alize o la ge ins ances om
he same amily.
3 Cu en wo k
F om he s a o my PhD in Decembe 2020, un il now I ha e ocused on i s ly
amilia izing mysel wi h he cu en esea ch in CP and WCSP sol ing. Du ing
my li e a u e o e iew I lea ned abou he e olu ion o he sea ch algo i hms, he
impac ha hey ha e made and di e en ways o p ep ocessing he p oblems.
Mo e p ecisely, I ha e become amilia wi h oulba 2 1which is a guably he
bes gene al pu pose WCSP sol e . I ha e lea ned he many op ions ha he
sol e p o ides and he huge impac ha chosing ones o ano he s may ha e in
pe o mance. I ha e seen ha a gi en ins ance can be i ially sol ed wi h some
sol ing op ions and un o e e wi h some o he s and, mos impo an ly, he e
a e no p ecise guidelines elling he use which op ions wo k bes .
One key aspec o WCSPs and o he G aphical Model amewo ks is he
exploi a ion o p oblem s uc u e and he bes way o see such s uc u e is
h ough he no ion o ee decomposi ion. Mos algo i hms ha ake ad an age
o ee decomposi ion mus s a by selec ing a ee oo .
The ocus o my cu en wo k is on esea ching on how o make a mo e
in o med decision by ha ing in o ma ion abou he T ee Decomposi ion o a wcsp
1h ps://mia .in ae. / oulba 2/
62
ins ance. Th ough sol ing all he ins ances wi h he de aul se ings, and looking
in o hei T ee Decomposi ion, i is isible ha he e a e nodes ha , i chosen
as oo , allow o a mo e e icien a e sal o he sea ch space. This hypo hesis
was con i med h ough analyzing he Cen al P ocessing Uni (cpu) ime when
sol ing he ins ance wi h di e en nodes as he oo . To be able o iden i y he
pa e n o which node migh be he bes oo , di e en measu es we e c ea ed
and used. These measu ed included: Clus e Size (Numbe o a iables ha
he node con ains), Domain Awa e Clus e Size (Taking he domain sizes in o
accoun ), Clus e Decomposi ion Size (La ges sub-p oblem a e assignmen ),
and Clus e Heigh (Longes pa h om he oo ). By co ela ing he cpu ime
and he measu es, no di ec ela ionship was e ealed. This expe imen was
conduc ed on 30 hand picked ins ances.
Based on he esul s, amoun o ins ances, and he ac ha he hypo hesis
was con i med, he expe imen is being epea ed cu en ly. All o he a ailable
da a is being used, selec ed and p ep ocessed o ensu e co ec esul s. The aim
is o la e use Machine Lea ning algo i hms o ecognizing he pa e n, as simple
measu es based on syn ac ical ea u es o he T ee Decomposi ion do no seem
o p edic well a good oo .
4 Objec i es and Me hodology
Based on he s a e o a and he achie emen s in he ield so a , he idea o his
PhD is o ake in o ma ion om he p oblems hemsel es be o e a emp ing o
sol e hem and make a mo e in o med decision on which algo i hms wo k bes .
Simila ly in o ma ion om o he p oblems would be added o ind simila i ies
which may gi e addi ional insigh in o which model would pe o m he bes .
To be able o ind he simila i ies be ween ins ances o he same p oblem o
ins ances om o he s, we will ha ness he powe o Machine Lea ning. This is
done by i s examining he da a s a is ically in o de o ind a eas whe e he
p oblems may show simila i ies, p ep ocess he da a and hen use an algo i hm
which will iden i y hose pa e ns well.
The aim o his PhD hesis is o enhance he op imiza ion abili ies o he
exis ing algo i hms using Machine Lea ning. Speci ic objec i es a e:
–To be e unde s and he di e en ypes o p oblems ha a e commonly
sol ed, and how in o ma ion om hem can be used o sol e o he p oblems
alike.
–To unde s and he in o ma ion ha he sea ch space p o ides and how i
can be used o make in o med decisions when sea ching.
–C ea e a Machine Lea ning algo i hm ha uses he in o ma ion o op imize
he sea ch.
This PhD uses p oblems om di e en ields ha he esea che s a he IN-
RAE MIAT in Toulouse and UPC, IIIA-CSIC in Ba celona ha e collec ed o
he pu pose o s udying CP. The sol e oulba 2 will be used o sol ing he
p oblems, p ep ocessing he p oblems and ex ac ing in o ma ion ega ding he
63
sea ch space o hem. Fo he pu pose o analyzing he da a and modeling he
Machine Lea ning models languages such as py hon, R and C++ will be used.
To be able o pa allelize a clus e o di e en machines will be used o sol ing
he p oblems, using oulba 2 o o he p oblem ela ed in o ma ion acquisi ion
o aining and es ing he Machine Lea ning models.
5 Fu u e wo k
A he cu en s age o he analysis o sol ing he p oblems using a di e en
oo based on he ee decomposi ion, my main ocus is i s o unde s and
he da a be e . Run he expe imen s wi h di e en oo s and ob ain s a is ical
in o ma ion and measu es ha could show why ce ain oo s a e a be e op ion.
Once his is eady a co ela ion will be used o see i he e is any indica ion o
which measu e migh be use ul o p edic a good oo . Since in he p e ious
expe imen he measu es al eady we e no p o iding good in o ma ion on wha
may be a good oo , he nex s ep would be o use Machine Lea ning o be e
iden i y he po en ial pa e n. Fo his I would like o use he class o deep
lea ning me hods known as G aph Neu al Ne wo ks. This ype o me hod would
be sui able o he s uc u e ha he p oblems ge once we ob ain hei T ee
Decomposi ion. To be able o build he Neu al ne wo k I will i s collec ea u es
om he da a ha will help he ne wo k make a be e dis inc ion om wha is
a good oo and wha is no . A e wa ds he model will be buil and ained wi h
a good sample o he da a ha ep esen s di e en ypes o p oblems ha can be
encoun e ed. Las he model will be es ed on unseen da a, so he gene aliza ion
o i can be e alua ed. In he case o he G aph Neu al Ne wo ks no pe o ming
well in he ask o iden i ying he bes oo , al e na i e Machine Lea ning models
such as building a mo e s anda d classi ica ion ype o Neu al Ne wo k ha
hie a chically classi ies he cpu imes, o c ea ing a non-neu al ne wo k me hod
whe e he cpu imes a e encoded in o classes and hen he bes oo is selec ed.
One o he mos challenging p oblems in CSP is o op imize he sea ch space.
So a he e ha e been nume ous imp o emen s done using echniques o a e s-
ing he sea ch space. While ha has ce ainly made he op imiza ion quicke , i
has also made he algo i hms mo e complex by adding mo e laye s o hem. I
wan o app oach his p oblem om he pe spec i e o Machine Lea ning, so ha
he space can be a e sed by using he in o ma ion ha we ga he om i as we
go h ough i . This en ails unde s anding he di e en ypes o sea ch spaces ha
can appea commonly and how in o ma ion can be p opaga ed h ough hem.
The challenge will hen be o inco po a e Rein o cemen Lea ning in o i , as he
agen will ake he in o ma ion ha is being sha ed and make mo e e icien
decisions along he way. To be able o build he Rein o cemen Model mysel , I
will s udy he di e en ypes o models ha could be applied he e. Nex I will
also wo k on ep esen ing he space in he bes way possible, so ha he ewa ds
can be maximized. Finally, a s a egy o he agen will be buil . The challenges
o combining CSP and Rein o cemen Lea ning a e nume ous, especially making
su e ha wi h Rein o cemen Lea ning he sea ch becomes e en mo e op imal,
64
bu he posibili ies o eaching be e op imiza ion hough in o med decisions
makes i an exci ing a ea o esea ch.
Re e ences
1. Absehe , M., Musliu, N., Wol an, S.: Imp o ing he e iciency o dynamic p og am-
ming on ee decomposi ions ia machine lea ning. Jou nal o A i icial In elligence
Resea ch 58, 829–858 (2017)
2. Allouche, D., de Gi y, S., Ka si elos, G., Schiex, T., Zy nicki, M.: Any ime hy-
b id bes - i s sea ch wi h ee decomposi ion o weigh ed CSP. In: Pesan , G.
(ed.) P inciples and P ac ice o Cons ain P og amming - 21s In e na ional Con-
e ence, CP 2015, Co k, I eland, Augus 31 - Sep embe 4, 2015, P oceedings.
Lec u e No es in Compu e Science, ol. 9255, pp. 12–29. Sp inge (2015)
3. Be el`e, U., B ioschi, F.: On non-se ial dynamic p og amming. J. Comb. Theo y,
Se . A 14(2), 137–148 (1973)
4. Bodlaende , H.L., G igo ie , A., Kos e , A.M.C.A.: T eewid h lowe bounds wi h
b ambles. Algo i hmica 51(1), 81–98 (2008)
5. Coope , M.C., de Gi y, S., S´anchez-Fibla, M., Schiex, T., Zy nicki, M., We ne ,
T.: So a c consis ency e isi ed. A i . In ell. 174(7-8), 449–478 (2010)
6. Coope , M.C., de Gi y, S., Schiex, T.: G aphical models: Que ies, complexi y,
algo i hms ( u o ial). In: Paul, C., Bl¨ase , M. (eds.) 37 h In e na ional Symposium
on Theo e ical Aspec s o Compu e Science, STACS 2020, Ma ch 10-13, 2020,
Mon pellie , F ance. LIPIcs, ol. 154, pp. 4:1–4:22. Schloss Dags uhl - Leibniz-
Zen um ¨u In o ma ik (2020)
7. Da wiche, A.: Modeling and Reasoning wi h Bayesian Ne wo ks. Camb idge Uni-
e si y P ess (2009)
8. Dech e , R.: Bucke elimina ion: A uni ying amewo k o easoning. A i . In ell.
113(1-2), 41–85 (1999)
9. Dech e , R.: Reasoning wi h P obabilis ic and De e minis ic G aphical Models:
Exac Algo i hms, Second Edi ion. Syn hesis Lec u es on A i icial In elligence
and Machine Lea ning, Mo gan & Claypool Publishe s (2019)
10. J´egou, P., Te ioux, C.: Combining es a s, nogoods and bag-connec ed decompo-
si ions o sol ing csps. Cons ain s An In . J. 22(2), 191–229 (2017)
11. Ma inescu, R., Dech e , R.: AND/OR b anch-and-bound o g aphical models.
In: Kaelbling, L.P., Sa io i, A. (eds.) IJCAI-05, P oceedings o he Nine een h
In e na ional Join Con e ence on A i icial In elligence, Edinbu gh, Sco land, UK,
July 30 - Augus 5, 2005. pp. 224–229. P o essional Book Cen e (2005)
12. Nils, N.: A i icial In elligence: A New Syn hesis. Mo gan Kau mann (1998)
13. Sanchez, M., Allouche, D., De Gi y, S., Schiex, T.: Russian doll sea ch wi h ee
decomposi ion. In: 21s In e na ional Join Con e ence on A i icial In elligence.
p. 6. Mo gan Kau mann (2009)
14. Te ioux, C., J´egou, P.: Bounded back acking o he alued cons ain sa is ac ion
p oblems. In: Rossi, F. (ed.) P inciples and P ac ice o Cons ain P og amming -
CP 2003, 9 h In e na ional Con e ence, CP 2003, Kinsale, I eland, Sep embe 29 -
Oc obe 3, 2003, P oceedings. Lec u e No es in Compu e Science, ol. 2833, pp.
709–723. Sp inge (2003)
15. Vaezipoo , P., Lede man, G., Wu, Y., Maddison, C.J., G osse, R., Lee, E., Seshia,
S.A., Bacchus, F.: Lea ning b anching heu is ics o p oposi ional model coun ing.
a Xi p ep in a Xi :2007.03204 (2020)
65

Gua an eeing P i acy and Fai ness in
Pe sonalized Sys ems
Giacomo Medda1[0000−0002−1300−1876]
Uni e si y o Caglia i, Caglia i 09124, I aly
[email p o ec ed]
Abs ac . The main p oblem o ackle in my esea ch plan is he un ai -
ness o he ou comes o ecommende and biome ic sys ems. Nowadays,
social p oblems such as ai ness among demog aphic g oups, igh o
human igh s and disc imina ion a e ele an opics o e e y pe son,
and hese p oblems a e ela ed o he biases p esen in a ious con ex s,
anging om heal hca e o ju isdic ion sys ems. A i icial in elligence
(AI) solu ions a e ained wi h da a collec ed om eal wo ld scena -
ios and he biases inside he da a can di ec ly o indi ec ly a ec he
ou comes o AI sys ems. I is impo an o ocus on he un ai ness o
he esul s o such sys ems o ind he causes o hese p oblems and on
echniques ha could help o mi iga e his lack o ai ness. AI is used
in many scena ios o ou e e yday li e, hence, he decisions aken wi h
he suppo o hese solu ions can lead o consequences ha ma k hese
biases, esul ing in g oup o indi iduals being sys ema ically disc imi-
na ed. Solu ions o o e come hese p oblems a e necessa y o make AI
sys ems eliable o e e yone and be su e ha people a e ea ed equally.
This documen aims o ace he un ai ness p oblem wi hou using demo-
g aphic in o ma ion in o de o s eng hen he p i acy o he sys ems: an
equal quali y, accu acy, classi ica ion o AI solu ions would ensu e ai -
ness among he use s wi hou knowledge o he sensi i e in o ma ion, and
he e he ad an ages o such an app oach a e p esen ed and examined.
Keywo ds: Recommende sys ems ·Speake ecogni ion sys ems ·Ma-
chine lea ning ·Fai ness ·Consume ai ness
1 Backg ound and Cu en wo k
A i icial in elligence and machine lea ning (ML) app oaches ha e been widely
used in he li e a u e o sol e a as di e si y o p oblems, amongs which a e au-
oma ic speake ecogni ion (ASR) sys ems and ecommende sys ems (RecSys).
The o me aims o con i m o e u e he use ’s iden i y based on an en olled
speech model [5], he la e is a subclass o in o ma ion il e ing ha seeks o sug-
ges ele an i ems o use s, e.g. mo ies, books, jobs. Cu en solu ions o achie e
hese goals a e o en op imized o p o ide he highes accu acy in ecognising a
use o ecommending i ems, while o he conce ns do no ecei e he same con-
side a ion. Recen li e a u e unco e ed algo i hmic disc imina ion in sensi i e
con ex s, aising a en ion o o he beyond-accu acy objec i es, amongs which
66
is ai ness, which has s a ed o be mo e ele an in di e en domains o ML,
such as ecommende sys ems [22, 9, 18, 4, 21, 7, 2, 14, 8], speake ecogni ion [12,
10], acial ecogni ion [13, 19, 20] and o he s [15, 6, 23, 16, 24, 17, 1, 3].
The i s p oblem he li e a u e deals wi h is he co ec de ini ion o ai ness.
In [15, 23], he p incipal no ions o ai ness used in ML li e a u e a e de ined
and explained, bu each one o hem ma ks a pa icula ype o un ai ness and
none o hem can indi idually ep esen he igh de ini ion o ai ness. In he
con ex o anking algo i hms, [21] s a es ha “The e is no single de ini ion
o wha cons i u es a ai anking, bu ha ai ness depends on con ex and
applica ion”: in lea ning o ank he e a e di e en aspec s han need o be
sa is ied and o e ing equal anking quali y o all use s could no gua an ee a
ai anking. Cu en wo k makes use o hese ai ness no ions o de ine new
ones [7, 21, 13], bu , in gene al, he ones lis ed in [15] a e he mos widely used.
The second p oblem is he mi iga ion o un ai ness in ML. The di e en
echniques p oposed in he li e a u e can be di ided in 3 g oups: p e-p ocessing,
in-p ocessing and pos -p ocessing. P e-p ocessing echniques include s a egies
ha balance he aining da a on he basis o demog aphic in o ma ion [9, 12, 10],
s a egies ha sample he use s acco ding o a pa icula cons ain [1], s a e-
gies ha c ea e indexes o assign a mino i y/majo i y alue o use s and i ems
in RecSys and use hese indexes o guide he lea ning p ocess [4]. In-p ocessing
echniques a e based on added cons ain s du ing he aining phase, in pa -
icula , modi ica ions o he loss unc ion [2, 4, 8, 14, 24] by conside ing o he
a iables, such as expec ed exposu e [8], compu a ion on indexes [4], pai wise
compa isons [2]. Pos -p ocessing echniques include he applica ion o andom-
iza ion algo i hms [8], ad hoc algo i hms o educe he bias dispa i y [22, 17],
ai e anking app oaches [18].
2 Goals and Resul s
E en hough he li e a u e shows in e es ing esul s wi h espec o he mi -
iga ion o un ai ness in ML sys ems, he mos pa o hese s udies is based
on echniques ha depend on demog aphic in o ma ion. This aises p oblems
o p i acy and gene aliza ion when app oaches o g oup ai ness a e aken in o
conside a ion: he o me p oblem is ele an o e e y en i y ha in e ac s wi h
he AI sys em, since pe sonal in o ma ion should be p o ided o p ope ly ap-
ply he mi iga ion echnique; he la e d aws he a en ion on subg oups, o
which an equal ea men is no gua an eed as well as he demog aphic g oups
conside ed by he mi iga ion algo i hm. On he o he hand, indi idual ai ness
solu ions a e based on he idea ha simila use s should be ea ed equally, bu
i is no s aigh o wa d o de ine a co ec simila i y no ion.
My goal is based on he idea ha un ai ness could be sol ed by gua an eeing
he same accu acy, quali y o each use : his de ini ion does no need no ions
o simila i y and does no need any demog aphic in o ma ion. Aiming a gi ing
ou comes o same quali y o all he indi iduals would guide he lea ning p ocess
o no ad an age speci ic use s and no depend on sensi i e in o ma ion. Ne e -
67
heless, demog aphic da a could be ele an in some si ua ions, e.g. in RecSys
when he “i ems” o ecommend a e people, such as candida es ecommended o
a ec ui e , whe e he di e si y o gende , age o o he demog aphic a ibu es
is impo an o gua an ee ai ou comes; hence, e en i he use s we e ea ed
equally, some indi ec disc imina ion could be p esen because o he o de o
he candida es.
My esea ch in o RecSys laid he ounda ions o suppo his goal idea by
analysing some impo an aspec s ega ding he causes behind he un ai ness
o he models. In pa icula , he da a and aining ea u es ha e been s udied
o e alua e hei in luence on he ou comes, bu also he lea ning p ocess has
been examined o ind ules o unde s and how RecSys ou comes e ol e o e he
aining epochs. On he o he hand, I ha e al eady accomplished some esul s in
he o he ield o my esea ch ocus: speake ecogni ion sys ems. The s udy o
such sys ems is ein o ced by a amewo k ha includes s a e-o - he-a ASR sys-
ems, au oma ic da a pipelines and unc ionali ies o wo k on beyond-accu acy
objec i es. This amewo k has been used o p oduce wo publica ions:
1. Imp o ing Fai ness in Speake Recogni ion [12]: in his wo k, I and my col-
leagues applied a balancing s a egy o he aining se based on wo de-
mog aphic a ibu es and e alua ed he ai ness imp o emen in e ms o
dispa i y o equal e o a e on wo s a e-o - he-a neu al ne wo ks. I has
been p esen ed a he Symposium on Pa e n Recogni ion and Applica ions
(SPRA) 2020 and has been selec ed as he bes p esen a ion o he con e -
ence.
2. Fai Voice Biome ics: Impac o Demog aphic Da ase Imbalance on G oup
Fai ness in Deep Speake Recogni ion [11]: his pape ex ends he i s one by
conside ing a hi d neu al ne wo k and e alua ing he ai ness imp o emen
o he balancing s a egy in e ms o some s a e-o - he-a ai ness me ics,
ex ac ed om [15]. I has been p esen ed a he In e speech 2021 con e ence.
3 Resea ch Plan
The pu pose o his documen is o highligh he p oblems ela ed o se e al
un ai ness mi iga ion app oaches and o p opose a di e en poin o iew o he
ai ness conce n. In pa icula , ecen li e a u e ackles he un ai ness by elying
on sensi i e in o ma ion, which can ha m he p i acy o he use s and make
he sys ems dependan on demog aphic a ibu es. This esea ch plan aims o
examine hese s udies and app oach he p oblem wi hou aking in o accoun
p i a e da a and wi hou using ools o ind simila i ies among use s.
Cu en ly, my main ocus is ai ness in ecommenda ion sys ems and au o-
ma ic speake ecogni ion sys ems: he i s s ep has been he analysis o di e en
solu ions o he li e a u e o ai ness in hese wo ields and in machine lea ning
in gene al, om which I adjus ed and pe ec ed my idea. The plan is based on
he goal desc ibed in Sec ion 2 and i is s uc u ed on he ollowing esea ch
ques ions:
68
–RQ1: Can he addi ion o nsensi i e a ibu es S= siji2[1..n]g e eal a
sys ema ic un ai ness agains he new p o ec ed/unp o ec ed g oups when
a mi iga ion app oach is applied on demog aphic in o ma ion no in S?
–RQ2: Can he p edic ion o missing o co up ed labels o sensi i e a ibu es
lead o decisions ha damage he image o he use s?
–RQ3: To wha ex en he con inual lea ning can help on mi iga ing he un-
ai ness by gua an eeing he same se ice quali y o all he use s?
The i s ques ion aims o unde s and i he s a e-o - he-a inno a ions in g oup
ai ness can gua an ee a ho ough equi y among all he demog aphic g oups
p esen in a da ase . Consume s o a ecommende sys em o speake s a e hu-
mans and gi en ha we can dis inguish a mul i ude o g oups and subg oups:
sa is ying he ai ness o all o hese g oups and subg oups would be p ac ically
impossible, made ha de by he ac ha new demog aphic g oups es ablish in
socie y day a e day. The second ques ion aims o highligh he isk o p edic -
ing missing o co up ed labels and he damage ha hese ac ions could cause o
people. This s a egy is applied in se e al wo ks o he li e a u e [1, 17, 24] and
e en i i is a i med ha hese p edic ions canno be pe ec ly accu a e, s udies
on bias a e ca ied on using misp edic ed labels ha could damage he image
o he use s. The hi d ques ion aims o unde s and he s eng h o con inual
lea ning o ob aining equal quali y among all use s, which, as s a ed be o e,
would gua an ee ai ness. Con inual lea ning makes possible o no o ge p e i-
ous knowledge and ine une he model: hese a e ea u es ha can be combined
wi h an equaliza ion ule ha guide he lea ning p ocess on assigning equal
quali y.
My nex ac i i ies will be guided by he a o emen ioned esea ch ques ions:
1. Task 1: many s udies le e age sensi i e in o ma ion o mi iga e he un ai -
ness o machine lea ning sys ems. All o hese solu ions will be ga he ed,
ep oduced and s udied using da ase s wi h se e al sensi i e a ibu es. This
app oach pe mi s o e alua e he un ai ness impac on demog aphic g oups
ha ha e no been aken in o accoun by he mi iga ion algo i hm, since he
un ai ness agains subg oups, e.g. black Asian emales, whi e A ican males,
needs o ecei e a en ion as well.
2. Task 2: in e e y ield o he machine lea ning li e a u e he e a e wo ks ha
make use o labels p edic ion. Missing o co up ed da a can be sol ed by
p edic ing he labels, bu his could be dange ous and ha m ul o he use s.
All he p edic ions app oaches and he un ai ness mi iga ion echniques used
wi h p edic ed labels will be ga he ed and ep oduced o e alua e he con-
sequences o misp edic ed labels.
3. Task 3: machine lea ning models can be ained on a pa o a da ase and
he o he pa could be sliced in pieces in o de o ain he model wi h
a new piece a a ime wi hou o ge ing he p e ious aining phases. This
app oach could be s eng hened by a egula isa ion ule ha aims o equalise
he quali y o e ed o all he use s o he da ase . This ac i i y will s udy
he bene i s o such an app oach and wha ai ness goals could be eached
by applying his echnique on se e al da ase s.
69
Fig. 2. Ou me ged g aph (same inpu as 1)
The second esul is ha ou ool seems p e y in ui i e: wi h he help o
a sho wo-page manual, bo h enginee s we e able o ge si ua ed and s op
e e ing o he manual a e 5 o 6 minu es. We did iden i y wo poin s ha
equi ed some e bal explana ion on ou pa . Fi s , he meaning o he o ange
colo , i s explana ion in he use manual being oo scien i ic o be use - iendly.
Second, he ea u e o seeing inside a node when clicking on i was no in ui i e
enough o hem o y and click, and should ha e been pu o wa d mo e clea ly.
Finally, when asked how exac ly hey would use ou ool in hei wo k, bo h
in e iewed pa icipan s came up wi h di e en ideas: one would use i as de-
sc ibed ea lie , o gi e jus i ica ions o a clien , bu he o he (less clien -o ien ed
in hose p ojec s), would use i as a debugging aid, o make su e ha changes
o he mig a ion p ocess i sel didn’ ha e unwan ed consequences.
6 Conclusion and eplica ion
To conclude, we belie e we p oduced a ool ha can be used “as is” by ou
collabo a ing company, and ha i could be adap ed o o he use cases ai ly
easily. Bo h enginee s who assessed ou ool had di e en ideas on how i migh
be help ul o hei company, which sugges s i is ai ly e sa ile. Since inishing
ou alida ion, we also had he occasion o discuss abou he ool and i s pu pose
wi h se e al people and came up wi h a ious ideas, om he s aigh o wa d
idea o compa ing logs om boo execu ions o wo Linux dis ibu ions o de e -
mine whe he he second would be a good subs i u e o he i s , o he mo e
challenging idea o using ou ep esen a ion o analyse how a de elopmen eam
s icks o a de elopmen me hod (like sc um).
A good pa h o u u e wo k would be o use ou ool in a comple ely di e en
con ex o see how use ul i can be he e, and pe o m a second ound o alida-
ion. Fo his, i anyone wishes o y, we ha e c ea ed a ull eplica ion package,
wi h a VM and ou ool ins alled, along wi h an ob usca ed e sion o ou da a
(Raincode’s clien da a being con iden ial). We also p o ide documen a ion on
how o ob ain he inpu om ano he sou ce o log, and how o un he ool on
o he da a. All ins uc ions o ind and un he eplica ion package can be ound
on Gi Hub [3], o else eel ee o con ac us.
76

Acknowledgemen s
Thanks go ou o my ad iso s Kim Mens (UCLou ain) and Vadim Zay se
(UTwen e), he people a Raincode Labs: Johan Fab y, Yannick Ba hol and
Bo is Pe ei a, and inally o Alexand e Be gel. We also hank he Inno i is und-
ing agency o unding ou CodeDi NG Applied PhD esea ch p ojec .
Re e ences
1. I. Beschas nikh e al., “Synop ic Gi Hub page,” Online: h ps://gi hub.com/
ModelIn e ence/synop ic, 2021.
2. A. W. Bie mann and J. A. Feldman, “On he Syn hesis o Fini e-S a e Machines
om Samples o Thei Beha io ,” IEEE T ansac ions on Compu e s, ol. C-21,
no. 6, pp. 592–597, 1972, DOI: 10.1109/TC.1972.5009015.
3. C´eline Deknop, “Replica ion package and ins uc ions,” h ps://gi hub.com/
CelineDknp/VISSOFTA i ac , 2021.
4. ——, “Valida ion da a,” h ps://gi hub.com/CelineDknp/
PACBASEValida ionDa a, 2021.
5. C. Deknop, K. Mens, A. Be gel, J. Fab y, and V. Zay se , “A scalable log di e -
encing isualisa ion applied o cobol e ac o ing,” in 2021 Wo king Con e ence on
So wa e Visualiza ion (VISSOFT), 2021, pp. 1–11.
6. M. Golds ein, D. Raz, and I. Segall, “Expe ience Repo : Log-Based Beha io al
Di e encing,” in P oceedings o he 28 h In e na ional Symposium on So wa e
Reliabili y Enginee ing (ISSRE), 2017, pp. 282–293, dOI: 10.1109/ISSRE.2017.14.
7. J. W. Hun and M. D. McIl oy, “An algo i hm o di e en ial ile compa ison,” no.
#41, 1976.
8. M. Kim and D. No kin, “Disco e ing and Rep esen ing Sys ema ic Code
Changes,” in P oceedings o he 31s In e na ional Con e ence on So wa e
Enginee ing (ICSE). IEEE, 2009, p. 309–319. [Online]. A ailable: h ps:
//doi.o g/10.1109/ICSE.2009.5070531
9. S. Maoz, J. O. Ringe , and B. Rumpe, “ADDi : Seman ic Di e encing o Ac i -
i y Diag ams,” in P oceedings o he 19 h Symposium on he Founda ions o So -
wa e Enginee ing and he 13 d Eu opean So wa e Enginee ing Con e ence (FSE),
T. Gyim´o hy and A. Zelle , Eds. ACM, 2011, pp. 179–189.
10. Raincode Labs, “PACBASE Mig a ion: Flexible P ocess,” h ps://www.
aincodelabs.com/pacbase/, 2021.
11. Z. Xing and E. S oulia, “UMLDi : An Algo i hm o Objec -O ien ed Design
Di e encing,” in P oceedings o he 20 h In e na ional Con e ence on Au oma ed
So wa e Enginee ing (ASE). ACM, 2005, pp. 54–65.
12. Y. Xue, Z. Xing, and S. Ja zabek, “Clonedi : seman ic di e encing o clones,” in
P oceeding o he Fi h ICSE In e na ional Wo kshop on So wa e Clones (IWSC),
J. R. Co dy, K. Inoue, S. Ja zabek, and R. Koschke, Eds. ACM, 2011, pp. 83–84.
[Online]. A ailable: h ps://doi.o g/10.1145/1985404.1985428
13. T. Zimme mann, P. Weibge be , S. Diehl, and A. Zelle , “Mining e sion his o-
ies o guide so wa e changes,” in P oceedings. 26 h In e na ional Con e ence on
So wa e Enginee ing, 2004, pp. 563–572.
77