A Multidimensional Scaling Approach to Indexing by Metric Adaptation and Representation Upg

RepresentationUpgrade∗

RodrigoVenturaandCarlosPinto-Ferreira

InstituteforSystemsandRoboticsInstitutoSuperiorT´ecnico,TULisbon

Av.RoviscoPais,1

1049-001Lisbon,PORTUGAL{yoda,cpf}@isr.ist.utl.pt

Followingrecentneurophysiologicalresearch,oneim-portantroleofemotionsconsistsinprovidingamecha-nismforadequateandefficientresponsetorelevantstim-uli(Damasio1994).Inthispaperweproposeamethodol-ogyforimplementingsuchamechanism,basedonapre-viouslypresentedemotion-basedagentmodel(Ventura&Pinto-Ferreira1998).Thismodelisfoundedonadoubleknowledgerepresentationparadigm:astimulusreachingtheagentisprocessedundertwodifferentandsimultaneousper-spectives—asimple(termedperceptual)andacomplex(termedcognitive)—fromwhichtwodifferingrepresen-tationschemataarederived.Theperceptualrepresentationisorientedtocapturingtherelevantaspectsoftheenviron-ment,aimingataquickresponsetourgentsituations,whilethecognitiveoneisdirectedtowardshigh-levelcognitiveprocessing.Thesetworepresentationsareassociatedandstoredintheagentmemoryinsuchawaythat,inthefuture,iftheagentisconfrontedwithasimilarsituation,theper-ceptualrepresentationwillhelptheretrievalofthecognitiveoneinanefficientway.Thisindexingmechanismprovidesaquickalgorithmtofindcognitivematches.

Theindexingmechanismaddressedinthispaperwaspre-viouslyformulatedandtheoreticallyanalyzed,undertheas-sumptionthatthematchingofthecognitiveandperceptualimagesareperformedinmetricspaces(Ventura&Pinto-Ferreira2002).Givenastimuluss∈S,theagentextractstwokindsofrepresentations:aperceptualimageiandacognitiveoneiIp∈Ip,allpossibleperceptualc∈andc.EachoneofthesetsIcognitiveimagesisequippedpandIofcwithametricfunction,denotedbydp:Ip×Ip→R+0and

dc:Ic×Ic→R+

0respectively,mappingpairsofimagestodistances,interpretedasdegreesofmismatch.Thememoryisassumedtobeformedbypairsofcognitiveandpercep-tualimages󰀌ikc,ik

p󰀍(k=1,...).Thegoaloftheindexingmechanismisthentofindthememorypairwhichcognitiveimageminimizesitsdistancetotheoneextractedfromthestimulus,employingtheperceptualrepresentationtodosoinanefficientmanner.

Theresearchpresentedhereconcernsthefollowingprob-∗

ThisworkwaspartiallysupportedbyFCT(ISR/ISTplurianualfunding)throughthePOSConhecimentoProgramthatincludesFEDERCopyrightfunds.

󰀁

c2007,AmericanAssociationforArtificialIntelli-gence(www.aaai.org).Allrightsreserved.

lem:howtoconstructaperceptualrepresentation(andmet-ric)withthegoalofoptimizingtheindexingefficiency.Inotherwords,theidealperceptualrepresentationandmetricaretheonesthatyieldsmallperceptualdistancesiffthecor-respondingcognitivedistancesarealsosmall.Todoso,twostrategiesareexplored.Onecorrespondstoadaptingaper-ceptualmetric,viaasetofparameters,suchthatcognitiveproximityimpliesperceptualdc(i1c,i2c)c)⇒dp(i1p,i2p)p)

(1)forallpossibleimagepairs󰀌ikc,ik

p󰀍(k=1,2,3)extractablefromstimuli.Thesecondstrategyaddressestheimprove-mentoftheperceptualrepresentation,inthefollowingsense.Assumingthattheperceptualrepresentationisavec-toroffeaturesextractedfromstimuli,whenthesefeaturesarenotsufficientlyrepresentativetosatisfy(1),thegoalistoupgradetheperceptualrepresentationwithnew,morerepresentative,features.Bothofthesestrategiesareap-proachedhereusingMultidimensionalScaling(MDS)tech-niques(Cox&Cox1994).

Inthisframework,agoodperceptualrepresentationisonewhichsatisfiestheimplication(1)forallimagepairs.NotethatthisgoalissimilartotheMDSone,onceoneconsidersthecognitivedistancestobethedissimilarities,andtheper-ceptualones,tobethedistancesamongobjects,intheMDSterminology.However,therearedifferences.InthecaseoftheMDS,themetricisgivenwhiletheobjectcoordinatesaresought.Inthecaseoftheindexing,theobjectcoordi-nates(perceptualimages)aregiven,whilethe(perceptual)metricissubjecttoadaptation.

Weproposetoperformagradientdescent,withintheframeworkofMDS,w.r.t.aparametrizationofthepercep-tualmetric,insteadofw.r.t.thepointcoordinates.Re-gardingtheconstructionofadditionalperceptualfeatures,weproposetoappendeachperceptualimagewithapre-specifiedamountofadditionalcomponents.Thesecompo-nentsrepresentthevaluesthatthenewfeaturesougthtotake,foreachoneoftheperceptualimagesinthetrainingset.Theirvaluesarerandomlyinitialized,andsubjecttogradi-entdescentasinthenonmetricMDS.Concerninghowtoobtainthoseaddedcomponentsfornewstimuli,theideaweadvanceistoutilizetheobtainedvaluestoconstructare-gressionmodel.Thatregressionmodelcanthenbeusedtoobtainthenewfeaturesvaluesfornewstimuli.Letaperceptualimageirp,consistingoftheconcatenation

ofqnumericalfeaturesxwithpadditionalr1,...,xcomponentsrq,extractedfromagivenstimulus,yr1,...,yrp,bede-notedbythevectorirT

additionalcomponentsp=(xcorrespondr1,...,xrq,ytother1,...,yvaluesrp).Thesethatthenewfeaturesoughttotakeforthatparticularper-ceptualimage.Theperceptualmetricemployedhereisparametrized󰀃byqcoefficientsθ1,...,θq,takingtheform

󰀂qpdrs=󰀂󰀁󰀄

θ2i(xri−xsi)2+󰀄(yri−ysi)2(2)

i=1

i=1

Thisparametrizationcorrespondstoassigningaweight(rel-evance)toeachperceptualfeaturebeforecalculatingtheEu-clideanmetric.Moreover,whenthealgorithmassignsazero

weighttoafeature,thatfeaturecanbedeletedfromtheper-ceptualrepresentation,sinceitisirrelevant(w.r.t.thecogni-tivematching).Theadditionalcomponentsarenotweightedsinceitwouldjustaddredundantdegreesoffreedom.

ThecostfunctionemployedhereisthesumoftheMDSstress,usingthecognitivedistancesasdissimilaritiesanddrsasdistances,witharegularizationtermpenalizingtheabsolutevaluesofthemetricparameters

qJ=S+ξ󰀄

|θi|(3)

i=1

Thislatterterm,weightedbyξ,isincludedinthecostfunc-tiontodrivetozeroanyweightcorrespondingtoanirrele-vantperceptualcomponent.

BasedonthestandardnonmetricMDSalgorithm(Cox&Cox1994),weproposethefollowingone:

1.StartwithaninitialvariablesvectorΛ=

[θ1···θq|yT

distributed).

11···ynp](e.g.,θi=1,andyrirandomly2.Normalizethemetricparametervector(θ1,...,θq)Ttounitnorm,sincethestressisinvarianttoscalingofthisvector.Theadditionalcomponents{yri}are,however,notnormalized;

3.Computethedistanceset{drs}usingtheparametrizedperceptualmetric(2);

4.Performtheisotonicregressionobtainthesetofdistances{d

ˆ(asinnonmetricMDS)to

rs};5.Computethecost;ifitsvalueisbelowathreshold󰀕,stopthealgorithm;

6.Findthegradientofthecostfunctionw.r.t.thevari-ablesvectorΛ,andperformastepofthegradientdescentmethod;7.Gotostep2.

Inordertoevaluatetheresults,ameasureofperformancecalledeval-orderwasintroduced,aimingatassessinghowwelltheindexingmechanismwouldbehave.Thisassess-mentisperformedusingatestsetdisjointfromthetrainingsetemployedinthegradientdescent(cross-validation).In-spiredontheN-bestindexingalgorithmdescribedin(Ven-tura&Pinto-Ferreira2002),theeval-orderisdefinedinthefollowingway:givenacognitiveandperceptualimagespair󰀌ic,ip󰀍,determineallperceptualdistancesfromittoim-agesintheperceptualmemory(i.e.,thetrainingset);then,

aftersortingalltheseimagesw.r.t.theperceptualdeterminewhichn-thimagepair󰀌ikc,ik

distances,

distancep󰀍ontheresultingor-deredlisthastheminimumcognitiveto󰀌ithefirstone,andc,ithusp󰀍.Intheidealcase,itcorrespondstoaneval-orderof1.Highervaluescorrespondtoworseperfor-mance.

Tovalidatetheproposedmethodology,asimpletest-bedwasdevised.Randompointsx∈Rc(simulatingstimuli)wereuniformlydrawnfromanhypercubecofunitsidelength.Thecognitiveimagesic∈RweresettothecomponentsofxmultipliedbysomefixedcoefficientsW=diag(w1,...,wintroducec)between0and2each:idifferentdegreesofc=Wx.Thesecoefficientsrelevancetothecomponentsofitainedbyconcatenatingc.Theperceptualimageswereob-twovectors:thepfirstcompo-nentsofxweightedbyasecondsetoffixedcoefficientsV=diag(v1,...,vp)(p≤c);andavectoruofnran-domnumbers(noise)between0and1.Thus,theperceptualimageshavep+ncomponents:ip=[(Vx)T|uT]T.

Inthefirstphaseofexperimentation,noadditionalper-ceptualcomponentswereconsidered,andthecognitiveandperceptualdimensionsweremadeequal(c=p,n>0).Theresultshaveshownthatthealgorithmwasabletoboth(1)successfullydeterminetherelevanceofeachcomponents,intheformoftheirweightsWregardingthecognitivedis-tance,and(2)todiscardthenoiseperceptualcomponents,bysettingthecorrespondingweightstozero,thusshow-ingasuccessfulcapabilityofidentifyingirrelevantfeatures.Concerningtheeval-orderperformancemeasure,theresultsshowasignificantimprovementoftheeval-orderperfor-manceafterusingthemetricweightsfoundbythealgorithm,whencomparedtoθThesecondphasei=1.

oftheexperimentationcomprisedtheintroductionofnewcomponentstotheperceptualrepresen-tation.Todoso,thedimensionofthecognitiveimageswasmadehigherthantheperceptualone,i.e.,c>p.Thus,theperceptualmetricisperformedwithlesscomponentsthanthecognitiveone.Thefirstimpactofthisisthat,withouttheintroductionofnewcomponents,thefinalcostvaluesweremuchhigherthanbefore,duetolackoffit.Thishappensbecausetheperceptualrepresentationhasnotenoughtin-formationtobeabletofaithfulyreplicatethecognitivedis-tances.Theexperimentalresultsshowasignificantreduc-tionofthefinalcostvalues,wheneverthetotaldimensional-ityoftheperceptualrepresentation,includingtheamountofnewcomponents,isgreaterorequalthanc,thusshowinganimprovedfit.

References

Cox,T.F.,andCox,M.A.A.1994.MultidimensionalScaling.London,UK:Chapman&Hall.

Damasio,A.R.1994.Descartes’Error:Emotion,ReasonandtheHumanBrain.Picador.

Ventura,R.,andPinto-Ferreira,C.1998.Emotion-basedagents.InProceedingsAAAI-98,1204.AAAI.

Ventura,R.,andPinto-Ferreira,C.2002.Aformalindex-ingmechanismforanemotion-basedagent.InProceedingsIASTED-2002,34–40.Malaga,Spain:ACTAPress.