计算语言学协会会刊, 2 (2014) 297–310. 动作编辑器: Hal Daume III.
Submitted 5/2014; 修改 6/2014; 已发表 10/2014. C(西德:13)2014 计算语言学协会.
297
ExploitingSocialNetworkStructureforPerson-to-PersonSentimentAnalysisRobertWestStanfordUniversitywest@cs.stanford.eduHristoS.PaskovStanfordUniversityhpaskov@stanford.eduJureLeskovecStanfordUniversityjure@cs.stanford.eduChristopherPottsStanfordUniversitycgpotts@stanford.eduAbstractPerson-to-personevaluationsareprevalentinallkindsofdiscourseandimportantfores-tablishingreputations,buildingsocialbonds,andshapingpublicopinion.Suchevaluationscanbeanalyzedseparatelyusingsignedso-cialnetworksandtextualsentimentanalysis,butthismissestherichinteractionsbetweenlanguageandsocialcontext.Tocapturesuchinteractions,wedevelopamodelthatpre-dictsindividualA’sopinionofindividualBbysynthesizinginformationfromthesignedsocialnetworkinwhichAandBareembed-dedwithsentimentanalysisoftheevaluativetextsrelatingAtoB.Weprovethatthisprob-lemisNP-hardbutcanberelaxedtoanef-ficientlysolvablehinge-lossMarkovrandomfield,andweshowthatthisimplementationoutperformstext-onlyandnetwork-onlyver-sionsintwoverydifferentdatasetsinvolvingcommunity-leveldecision-making:theWiki-pediaRequestsforAdminshipcorpusandtheConvoteU.S.Congressionalspeechcorpus.1IntroductionPeople’sevaluationsofoneanotherareprevalentinallkindsofdiscourse,publicandprivate,acrossages,genders,cultures,andsocialclasses(Dunbar,2004).Suchopinionsmatterforestablishingrep-utationsandreinforcingsocialbonds,andtheyareespeciallyconsequentialinpoliticalcontexts,wheretheytaketheformofendorsements,accusations,andassessmentsintendedtoswaypublicopinion.Thesignificanceofsuchperson-to-personevalu-ationsmeansthatthereisapressingneedforcom-putationalmodelsandtechnologiesthatcananalyzethem.Researchonsignedsocialnetworkssuggestsonepathforward:howonepersonwillevaluatean-othercanoftenbepredictedfromthenetworktheyareembeddedin.Linguisticsentimentanalysissug-gestsanotherpathforward:onecouldleveragetex-tualfeaturestopredictthevalenceofevaluativetextsdescribingpeople.Suchindependenteffortshavebeensuccessful,buttheygenerallyneglectthewaysinwhichsocialandlinguisticfeaturescomplementeachother.Insomesettings,textualdataissparsebutthenetworkstructureislargelyobserved;inoth-ers,textisabundantbutthenetworkispartlyorun-reliablyrecorded.Inaddition,weoftenseerichin-teractionsbetweenthetwokindsofinformation—politicalalliesmightteaseeachotherwithnegativelanguagetoenhancesocialbonds,andopponentsof-tenusesarcasticallypositivelanguageintheircriti-cisms.Separatesentimentorsigned-networkmod-elswillmissormisreadthesesignals.Wedevelop(Sec.3)agraphicalmodelthatsyn-thesizesnetworkandlinguisticinformationtomakemoreandbetterpredictionsaboutboth.Theobjec-tiveofthemodelistopredictA’sopinionofBusingasynthesisofthestructuralcontextaroundAandBinsidethesocialnetworkandsentimentanalysisoftheevaluativetextsrelatingAtoB.WeprovethattheproblemisNP-hardbutthatitcanberelaxedtoanefficientlysolvablehinge-lossMarkovrandomfield(Broecheleretal.,2010),andweshowthatthisimplementationoutperformstext-onlyandnetwork-onlyversionsintwoverydifferentdatasetsinvolv-ingcommunity-leveldecision-making:theWikipe-diaRequestsforAdminshipcorpus,inwhichWi-kipediaeditorsdiscussandvoteonwhoshouldbe
我
D
哦
w
n
哦
A
d
e
d
F
r
哦
米
H
t
t
p
:
/
/
d
我
r
e
C
t
.
米
我
t
.
e
d
你
/
t
A
C
我
/
我
A
r
t
我
C
e
–
p
d
F
/
d
哦
我
/
.
1
0
1
1
6
2
/
t
我
A
C
_
A
_
0
0
1
8
4
1
5
6
6
8
9
9
/
/
t
我
A
C
_
A
_
0
0
1
8
4
p
d
.
F
乙
y
G
你
e
s
t
t
哦
n
0
7
S
e
p
e
米
乙
e
r
2
0
2
3
298
promotedwithintheWikipediahierarchy(Sec.4),andtheConvoteU.S.Congressionalspeechcorpus(Thomasetal.,2006),inwhichelectedofficialsdis-cusspoliticaltopics(Sec.5).Thesecorporadifferdramaticallyinsize,inthestyleandqualityoftheirtextualdata,andinthestructureandobservabilityoftheirnetworks.Together,theyprovideaclearpic-tureofhowjointmodelsoftextandnetworkstruc-turecanexcelwheretheircomponentpartscannot.2Backgroundandrelatedwork2.1SentimentanalysisInNLP,thelabelsentimentanalysiscoversdiversephenomenaconcerninghowinformationaboutemo-tions,attitudes,perspectives,andsocialidentitiesisconveyedinlanguage(PangandLee,2008).Mostworkassumesadimensionalmodelinwhichemo-tionsaredefinedprimarilybyvalence/polarityandarousal/intensity(拉塞尔,1980;FeldmanBarrettandRussell,1998;RubinandTalerico,2009),andthedominantapplicationispredictingthevalenceofproduct,company,andservicereviews.Weadopttheconceptualassumptionsofthisworkforourbasicsentimentmodel,butourfocusisonperson-to-personevaluationsandtheirsocialconse-quences.Thisinvolveselementsofworkonmod-elingpoliticalaffiliation(Agrawaletal.,2003;Mal-oufandMullen,2008;Yuetal.,2008),bias(Yanoetal.,2010;Recasensetal.,2013),andstanceonde-batetopics(Thomasetal.,2006;SomasundaranandWiebe,2010;Linetal.,2006;Anandetal.,2011),buttheseaspectsofbeliefandsocialidentityarenotourprimaryconcern.Rather,weexpectthemtobepredictiveofthesentimentclassificationsweaimtomake—e.g.,iftwopeoplesharepoliticalviews,theywilltendtoevaluateeachotherpositively.Recentworkinsentimentanalysishasbroughtintopical,contextual,andsocialinformationtomakemorenuancedpredictionsaboutlanguage(Jurafskyetal.,2014;Wilsonetal.,2005;Blitzeretal.,2007).Webuildontheseinsightswithourmodel,whichseekstomodulatesentimentpredictionsbasedonnetworkinformation(andviceversa).2.2Signed-networkanalysisManysocialnetworksencodeperson-to-personsen-timentinformationviasignededgesbetweenuserssummarizingtheiropinionsofeachother.Inthisset-ting,onecanleveragesociologicaltheoriesofpair-wiserelationshipsandgroup-levelorganizationtoidentifyandunderstandpatternsintheserelation-ships(Heider,1946;CartwrightandHarary,1956).Balancetheoryisbasedonsimpleintuitionslike‘afriendofmyfriendismyfriend’,‘anenemyofmyenemyismyfriend’,and‘anenemyofmyfriendismyenemy’.Ingraphtheory,thesearestatementsabouttheedgesignsoftrianglesofconnectednodes:giventhesignsoftwoedges,balancetheorypredictsthethird,assummarizedinFig.1(A),wherethetwogivenedges(gray)determinethethird(黑色的).Fordirectedrelationships,Leskovecetal.(2010乙)formulateanalternativecalledstatustheory,whichpositsthatnetworksorganizeaccordingtosocialsta-tus:anodehaspositiveedgestootherswithhigherstatusandnegativeedgestothosewithlowersta-tus.Fig.1(A)illustratesthestructureofvariousdi-rectedsignedtriangles,wherethesignofthethirdedge(黑色的)canbeinferredbasedonthesignsanddirectionsoftheothertwo(gray).Leskovecetal.(2010乙)showthatsignededgesinnetworksemergeinamannerthatisbroadlycon-sistentwithbothofthesetheoriesandthatsocial-networkstructurealonecansupportaccurateedge-signpredictions(Leskovecetal.,2010a).Kunegisetal.(2013)predicthiddenpositiveandnegativeedgesinascenariowhereallobservededgesarepositive.Bachetal.(2013)andHuangetal.(2013)framesignpredictionasahinge-lossMarkovrandomfield,atypeofprobabilisticgraphicalmodelintroducedbyBroecheleretal.(2010).Ourmodelcombinestheseideaswithasentimentmodeltoachieveevenmorerobustpredictions.2.3Synthesisofsentiment&networkanalysisModelsofsentimentandsignednetworkshavebeensuccessfulatavarietyoftasks.However,missingfromthecurrentscientificpictureisadeepunder-standingofthewaysinwhichsentimentexpres-sionandsocialnetworksinteract.Tosomeextent,theseinteractionsarecapturedbyaddingcontextualanddemographicfeaturestoatext-basedsentimentmodel,butthosefeaturesonlyapproximatetherichrelationalstructureencodedinasignednetwork.Thomasetal.(2006)andTanetal.(2011)cap-italizeonthisinsightusinganelaborationofthe
我
D
哦
w
n
哦
A
d
e
d
F
r
哦
米
H
t
t
p
:
/
/
d
我
r
e
C
t
.
米
我
t
.
e
d
你
/
t
A
C
我
/
我
A
r
t
我
C
e
–
p
d
F
/
d
哦
我
/
.
1
0
1
1
6
2
/
t
我
A
C
_
A
_
0
0
1
8
4
1
5
6
6
8
9
9
/
/
t
我
A
C
_
A
_
0
0
1
8
4
p
d
.
F
乙
y
G
你
e
s
t
t
哦
n
0
7
S
e
p
e
米
乙
e
r
2
0
2
3
299
+++–+–––+–––+++SOCIAL BALANCE THEORYSOCIAL STATUS THEORY+–?(A)Theoriesofsocialbalanceandstatus++––??+?“You’re onecrazy mofo!”“Love u! :)”“To whom itmay concern”(乙)DesiderataFigure1:(A)Predictionsofsocialbalanceandstatustheoriesfortheboldblackedge,giventhethingrayedges.Balancetheoryreasonsaboutundirected,statustheoryaboutdirected,triangles.Inthestatusdiagrams,nodesizesignifiessocialstatus.Apositiveedgemaybereplacedbyanegativeedgeintheoppositedirection,andviceversa,withoutchangingtheprediction.Statustheorymakesnopredictionintherightmostcase.(乙)Situationsofthesortweaimtocapture.Atleft,thenetworkresolvestextualambiguity.Atright,thetextcompensatesforedge-labelsparsity.graph-cutsapproachofPangandLee(2004).Theyareguidedbyanassumptionofhomophily,i.e.,thatcertainsocialrelationshipscorrelatewithagreementoncertaintopics:Thomasetal.(2006)usepartyaf-filiationandmentionsinspeechestopredictvotingpatterns,andTanetal.(2011)useTwitterfollowsandmentionstopredictattitudesaboutpoliticalandsocialevents.RelatedideasarepursuedbyMaetal.(2011)andHuetal.(2013),whoaddtermstotheirmodelsenforcinghomophilybetweenfriendswithregardtotheirpreferences.Weadoptsomeoftheassumptionsoftheaboveauthors,butourtaskisfundamentallydifferentintworespects.First,whereastheymodelperson-to-itemevaluations,wemodelperson-to-personevalu-ations;thesearealsothefocusofTangetal.(2013),WHO,尽管,useanunsignednetwork,whereasourworkisgearedtowarddistinguishingpositiveandnegativeedgelabels.Second,theabovemodelsmakeoverarchinghomophilyassumptions,whereasweallowourmodeltoexplorethefullsetoftriangleconfigurationssuggestedbyFig.1(A).3ModelHere,wearguethatcombiningtextualandstructuralfeaturescanhelppredictedgesigns.Weformu-lateamodel,showthatitiscomputationallyhard,andprovidearelaxedversionthatiscomputationallytractable,buildingonworkbyBachetal.(2013).3.1DesiderataInmanyreal-worldscenarios,richfeaturesareasso-ciatedwithedgesbetweentwopeople,suchascom-mentstheymadeabouteachother,messagestheyexchanged,orotherbehavioralfeatures.Suchfea-turesmaycontainastrongsentimentsignalusefulforpredictingedgesignsandmaybeusedtofitaconventionalsentimentmodel(Sec.2.1).然而,thesignofanedgealsodependsonthesignsofsurroundingedgesinthenetwork(Sec.2.2).Apurelyedge-feature–basedsentimentmodelcan-notaccountforthenetworkstructure,sinceitrea-sonsaboutedgesasindependentofeachother.Wearguethatconsideringsentimentandnetworkstructurejointlycanresultinbetterpredictionsthaneitheroneonitsown.Fig.1(乙)providestwoillus-trativeexamples.Here,thegrayedgesignsareob-served,whilethepolaritiesoftheblackedgesaretobepredicted.Intheleftnetwork,thetextoftheblackedge(‘You’reonecrazymofo!’)mightsug-gestanegativepolarity.However,anegativeblackedgewouldmakebothtrianglesinconsistentwithbalancetheory(Fig.1(A)),whereasapositiveblackedgemakesthemconsistentwiththetheory.So,inthiscase,thenetworkcontexteffectivelyhelpsde-tecttheteasing,non-literaltoneofthestatement.IntherightnetworkofFig.1(乙),onlyoneofthreeedgesignsisobserved.Predictingtwopos-itiveedgeswouldbeconsistentwithbalancethe-ory,butthesamewouldbetrueforpredictingtwonegativeedges.Thetextonthelowerblackedge(‘Towhomitmayconcern’)doesnotcarryanyclearsentimentsignal,butthe‘Loveu!:)’ontheotheredgestronglysuggestsapositivepolarity.Thisletsusconcludethatthebottomedgeshouldprobablybepositive,也,sinceotherwisethetrianglewouldcontradictbalancetheory.Thisshowsthatcombin-ingsentimentandnetworkfeaturescanhelpwhenjointlyreasoningaboutseveralunknownedgesigns.
我
D
哦
w
n
哦
A
d
e
d
F
r
哦
米
H
t
t
p
:
/
/
d
我
r
e
C
t
.
米
我
t
.
e
d
你
/
t
A
C
我
/
我
A
r
t
我
C
e
–
p
d
F
/
d
哦
我
/
.
1
0
1
1
6
2
/
t
我
A
C
_
A
_
0
0
1
8
4
1
5
6
6
8
9
9
/
/
t
我
A
C
_
A
_
0
0
1
8
4
p
d
.
F
乙
y
G
你
e
s
t
t
哦
n
0
7
S
e
p
e
米
乙
e
r
2
0
2
3
300
3.2ProblemformulationWenowformulateamodelcapableofsynthesizingtextualandnetworkfeatures.Notation.WerepresentthegivensocialnetworkasasignedgraphG=(V,乙,X),wheretheverticesVrepresentpeople;theedgesE,relationshipsbetweenpeopleinV;andthesignvectorx∈{0,1}|乙|repre-sentsedgepolarities,i.e.,xe=1(xe=0)indicatesapositive(negative)polarityforedgee∈E.Sometypesofrelationshipsimplydirectededges(e.g.,followingauseronTwitter,orvotingonacan-didateinanelection),whereasothersimplyundi-rectededges(e.g.,friendshiponFacebook,oragree-mentinanetworkofpoliticians).Weformulateourproblemforundirectedgraphshere,buttheexten-siontodirectedgraphsisstraightforward.Wede-fineatrianglet={e1,e2,e3}⊆Etobeasetofthreeedgesthatformacycle,anduseTtoindi-catethesetofalltrianglesinG.Finally,weusext=(xe1,xe2,xe3)∈{0,1}3torefertot’sedgesigns.Optimizationproblem.Weassumethatthestruc-tureofthenetwork(i.e.,VandE)isfullyobserved,whereastheedgesignsxareonlypartiallyobserved.Further,weassumethatwehaveasentimentmodelthatoutputs,foreachedgeeindependently,anes-timatepeoftheprobabilitythateisofpositivepo-larity,basedontextualfeaturesassociatedwithe.Thetask,然后,istoinfertheunobservededgesignsbasedontheobservedinformation.Thehigh-levelideaisthatwewanttoinferedgesignsthat(1)agreewiththepredictionsofthesen-timentmodel,和(2)formtrianglesthatagreewithsocialtheoriesofbalanceandstatus.Itisnotalwayspossibletomeetbothobjectivessimultaneouslyforalledgesandtriangles,soweneedtofindatrade-off.Thisgivesrisetoacombinatorialoptimizationproblem,whichwetermTRIANGLEBALANCE,thatseekstofindedgesignsx∗thatminimizeanobjec-tiveconsistingofbothedgeandtrianglecosts:1x∗=argminx∈{0,1}|乙|Xe∈Ec(xe,pe)+Xt∈Td(xt).(1)Thefirsttermisthetotaledgecost,inwhicheachedgeecontributesacostcapturinghowmuchitsin-ferredsignxedeviatesfromthepredictionpeofthe1Ofcourse,theentriesofx∗correspondingtoobservededgesarenotvariablebutfixedtotheirobservedvaluesinEq.1.sentimentmodel.Thesecondterm,thetotaltrianglecost,penalizeseachtriangletaccordingtohowun-desirableitsconfigurationisunderitsinferredsignsxt(e.g.,ifitcontradictsstatusorbalancetheory).Weusethefollowingedgecostfunction:C(xe,pe)=λ1(1−pe)xe+λ0pe(1−xe).(2)这里,λ1,λ0∈R+aretunableparametersthatallowforasymmetriccostsforpositiveandnegativeedges,分别,andpeistheprobabilityofedgeebe-ingpositiveaccordingtothesentimentmodelalone.Intuitively,themoretheinferrededgesignxedevi-atesfromthepredictionpeofthesentimentmodel,thehighertheedgecost.(NotethatatmostoneofthetwosumfactorsofEq.2isnon-zero.)Thetrianglecostfortriangletissignifiedbyd(xt),whichcanonlytakeon8distinctvaluesbe-causext∈{0,1}3(inpractice,therearesymmetriesthatdecreasethisnumberto4).Theparametersd(xt)maybetunedsothattriangleconfigurationsthatagreewithsocialtheoryhavelowcosts,whilethosethatdisagreewithit(e.g.,‘theenemyofmyfriendismyfriend’)havehighcosts.3.3ComputationalcomplexityTheproblemdefinedinEq.1isintuitive,但,aswithmanycombinatorialoptimizationproblems,itishardtofindagoodsolution.Inparticular,wesketchaproofofthistheoreminAppendixA:Theorem1.TRIANGLEBALANCEisNP-hard.3.4RelaxationasaMarkovrandomfieldTheobjectivefunctionofEq.1maybeseenasdefin-ingaMarkovrandomfield(MRF)overtheunderly-ingsocialnetworkG,withedgepotentials(definedbyc)andtrianglepotentials(definedbyd).Infer-enceinMRFs(i.e.,computingx∗)isawell-stud-iedtaskforwhichavarietyofmethodshavebeenproposed(KollerandFriedman,2009).然而,sinceourproblemisNP-hard,nomethodcanbeex-pectedtofindx∗efficiently.Onewayofdealingwiththecomputationalhardnesswouldbetofindanap-proximatebinarysolution,usingtechniquessuchasGibbssamplingorbeliefpropagation.Anotherop-tionistoconsideracontinuousrelaxationofthebi-naryproblemandfindanexactnon-binarysolutionwhoseedgesignsarecontinuous,i.e.,xe∈[0,1].
我
D
哦
w
n
哦
A
d
e
d
F
r
哦
米
H
t
t
p
:
/
/
d
我
r
e
C
t
.
米
我
t
.
e
d
你
/
t
A
C
我
/
我
A
r
t
我
C
e
–
p
d
F
/
d
哦
我
/
.
1
0
1
1
6
2
/
t
我
A
C
_
A
_
0
0
1
8
4
1
5
6
6
8
9
9
/
/
t
我
A
C
_
A
_
0
0
1
8
4
p
d
.
F
乙
y
G
你
e
s
t
t
哦
n
0
7
S
e
p
e
米
乙
e
r
2
0
2
3
301
Wetakethislatterapproachandcastourproblemasahinge-lossMarkovrandomfield(HL-MRF).ThisisinspiredbyBachetal.(2013),whoalsouseanHL-MRFtopredictedgesignsbasedontrianglestructure,butdonotuseanyedgefeatures.AnHL-MRFisanMRFwithcontinuousvariablesandwithpotentialsthatcanbeexpressedassumsofhinge-losstermsoflinearfunctionsofthevariables(cf.Broecheleretal.(2010)fordetails).HL-MRFshavetheadvantagethattheirobjectivefunctionisconvexsothat,unlikebinaryMRFs(asdefinedbyEq.1),exactinferenceisefficient(Bachetal.,2013).Weachievearelaxationbyusingsumsofhinge-losstermstointerpolatecoverthecontinuousdo-main[0,1]andd,超过[0,1]3(eventhoughtheyaredefinedonlyforbinarydomains).Asaresult,theHL-MRFformulationisequivalenttoEq.1whenallxearebinary,butitalsohandlescontinuousval-uesgracefully.Wenowinterpretareal-valued‘sign’xe∈[0,1]asthedegreetowhicheispositive.Westartbyshowinghowtotransformc:eventhoughitcouldbeusedinitscurrentform(Eq.2),wecreateatighterrelaxationbyusing˜c(xe,pe)=λ1kxe−pek++λ0kpe−xek+,(3)wherekyk+=max{0,y}isthehingeloss.Atmostonetermcanbeactiveforanyxe∈[0,1]duetothehingeloss,andc(xe,pe)=˜c(xe,pe)forbinaryxe.Torewrited,noticethat,foranyxt∈{0,1}3,wecanwritedasd(xt)=Xz∈{0,1}3d(z)δ(xt,z),(4)whereδ(xt,z)=1ifxt=zand0otherwise.Whileδisnotconvex,wecanusef(xt,z)=k1−kxt−zk1k+(5)asaconvexsurrogate.Whenxtisbinary,eitherxt=zsokxt−zk1=0orxt6=zsokxt−zk1≥1,andhencef(xt,z)=δ(xt,z).Toproveconvexity,notethat,foranyfixedbinaryz∈{0,1}3,kx−zk1=P3i=1|xi−zi|islinearinx∈[0,1]3,自从|xi−zi|equalseitherxi(ifzi=0)or1−xi(ifzi=1).Itfol-lowsthatfisahinge-lossfunctionofalineartrans-formationofxtandthereforeconvexinxt.TrainingTestingEvidence To inferRANDOM SAMPLINGBFS SAMPLINGuvFigure2:Optionsfortrainingandtestingourmodel.Requiringthetrianglecostd(z)tobenonnegativeforalltriangletypesz∈{0,1}3,wecanuse˜d(xt)=Xz∈{0,1}3d(z)F(xt,z)(6)asaconvexsurrogateford.OuroveralloptimizationproblemisthenthefollowingrelaxationofEq.1:x∗=argminx∈[0,1]|乙|Xe∈E˜c(xe,pe)+Xt∈T˜d(xt).(7)ThisobjectivehastheexactformofanHL-MRF,sinceitisaweightedsumofhingelossesoflin-earfunctionsofx.WeusetheProbabilisticSoftLogicpackage2toperformtheoptimization,whichisinturnbasedonthealternating-directionmethodofmultipliers(ADMM)(Boydetal.,2011).Learning.Clearly,asolutionisonlyusefulifthecostparameters(λ1,λ0,andd(z)forallz∈{0,1}3)aresetappropriately.Oneoptionwouldbetosetthevaluesheuristically,basedonthepredictionsmadebythesocialbalanceandstatustheories(Sec.2.2).然而,itismoreprincipledtolearntheseparam-etersfromdata.Forthispurpose,weleveragethelearningproceduresincludedintheHL-MRFimple-mentationweemploy,whichusesthevoted-percep-tronalgorithmtoperformmaximum-likelihoodesti-mation(Bachetal.,2013).Sinceourdatapoints(边缘)interactwitheachotherviathenetwork,somewordsonhowweper-formtrainingandtestingareinorder.Fig.2showstwooptionsforobtainingtrainingandtestingsets(weusebothoptionsinourexperiments).Inthe‘randomsampling’paradigm,werandomlychooseasetofedgesfortraining(蓝色的),andadisjointsetofedgesfortesting(黄色的).In‘BFSsampling’,we2http://psl.umiacs.umd.edu
我
D
哦
w
n
哦
A
d
e
d
F
r
哦
米
H
t
t
p
:
/
/
d
我
r
e
C
t
.
米
我
t
.
e
d
你
/
t
A
C
我
/
我
A
r
t
我
C
e
–
p
d
F
/
d
哦
我
/
.
1
0
1
1
6
2
/
t
我
A
C
_
A
_
0
0
1
8
4
1
5
6
6
8
9
9
/
/
t
我
A
C
_
A
_
0
0
1
8
4
p
d
.
F
乙
y
G
你
e
s
t
t
哦
n
0
7
S
e
p
e
米
乙
e
r
2
0
2
3
302
runabreadth-firstsearchfromseednodeutoobtainacoherenttrainingset(蓝色的),andlikewisefromaseednodevtoobtainacoherenttestingset(黄色的),takingcarethatnoedgesfromthetrainingsetarealsoincludedinthetestingset.Duringbothtrainingandtesting,anarbitrarypor-tionoftheedgesignsmaybefixedtoobservedval-uesandneednotbeinferred.ThesearethesolidedgesinFig.2;werefertothemasevidence.Fur-ther,wedefinetheevidenceratioasthenumberofevidenceedges,dividedbythenumberofalledgesconsidered(solidanddashed).Thelearningalgorithmmayusethestructure(VandE)ofthetraininggraphinducedbyallblueedges(solidanddashed),thepredictionspeofthesentimentmodelforallblueedges,andthesignsofthesolidblueedgestopredictthedashedblueedges.Duringtesting,thenetworkstructureofallyel-lowedges,thesentimentpredictionsforallyellowedges,andthesignsofthesolidyellowedgesmaybeusedtopredictthedashedyellowedgesigns.Inprinciple,alltrainingedgescouldbeusedasextraevidencefortesting(i.e.,allblueedgesmaybemadesolidyellow).然而,inourexperiments,wekeepthetrainingandtestingsetsfullydisjoint.Technicaldetails.Forclarity,wegivefurtherde-tails.First,thedistributionofpositiveandnegativesignsmaybeskewed;e.g.,weobserveapriorprob-abilityof76%positivesignsinourWikipediacor-pus(Sec.4).所以,asalsodonebyBachetal.(2013),weaddacosttermtoourobjective(Eq.7)thatpenalizesdeviationsfromthispriorprobabil-ity(asestimatedonthetrainingset).Thisensuresthatthemodelcandefaulttoareasonablepredictionforedgesthatarenotembeddedinanytrianglesandaboutwhichthesentimentmodelisuncertain.Second,intuitively,weshouldnotpenalizedevi-atingfromthesentimentmodelwhenitisitselfun-certainaboutitsprediction(i.e.,whenpeisfarfromboth0and1).相当,wewanttorelymoreheavilyonsignalsfromthenetworkstructureinsuchcases.Toachievethis,weintroduce10pairsofcostparam-eters(λ(1)1,λ(1)0),…,(λ(10)1,λ(10)0).然后,wedividetheinterval[0,1]into10bins,andwhenpefallsintothei-thbin,weuseλ(我)1andλ(我)0inEq.3.Thisway,largercostscanbelearnedfortheextremebinscloseto0and1thanfortheintermediatebinsaround0.5.Finally,hinge-losstermsmayoptionallybesquaredinHL-MRFs.WeusethesquaredhingelossinEq.5,sinceinitialexperimentationshowedthistoperformslightlybetterthanthelinearhingeloss.4WikipediaexperimentsOurfirstsetofexperimentsisconductedontheWi-kipediaRequestsforAdminshipcorpus,whichal-lowsustoevaluateourmodel’sabilitytopredictperson-to-personevaluationsinWebtextsthatareinformalbutpertaintoimportantsocialoutcomes.4.1DatasetdescriptionForaWikipediaeditortobecomeanadministrator,arequestforadminship(RfA)3mustbesubmitted,eitherbythecandidateorbyanothercommunitymember.Subsequently,anyWikipediamembermaycastasupporting,neutral,oropposingvote.Thisinducesadirected,signednetworkinwhichnodesrepresentWikipediamembersandedgesrepresentvotes(wediscardneutralvotes).Wecrawledandparsedallvotessincetheadop-tionoftheRfAprocessin2003throughMay2013.4ThissignednetworkwaspreviouslyanalyzedbyLeskovecetal.(2010乙;2010A).然而,thereisalsoarichtextualcomponentthathassofarre-maineduntappedforedge-signprediction:eachvoteistypicallyaccompaniedbyashortcomment(me-dian/mean:19/34代币).Atypicalpositivecom-mentreads,‘I’venoconcerns,willmakeanexcel-lentadditiontotheadmincorps’,whileanexampleofanegativecommentis,‘Littleevidenceofcollab-orationwithothereditorsandlimitedcontentcre-ation.’ThepresenceofavotingnetworkalongsidetextualedgefeaturesmakesourmethodofSec.3well-suitedforthisdataset.TheRfAnetworkcontains11Knodes,160Kedges(76%积极的),andcloseto1Mtriangles.4.2ExperimentalsetupTrain/testsets.Wefollowthetrain–testparadigmtermed‘BFSsampling’inSec.3.4andFig.2,choos-ing10randomseednodes,fromeachofwhichweperformabreadth-firstsearch(followingbothin-andout-links)untilwehavevisited350nodes.We3http://en.wikipedia.org/wiki/Wikipedia:RfA4Dataavailableonline(西方,2014).
我
D
哦
w
n
哦
A
d
e
d
F
r
哦
米
H
t
t
p
:
/
/
d
我
r
e
C
t
.
米
我
t
.
e
d
你
/
t
A
C
我
/
我
A
r
t
我
C
e
–
p
d
F
/
d
哦
我
/
.
1
0
1
1
6
2
/
t
我
A
C
_
A
_
0
0
1
8
4
1
5
6
6
8
9
9
/
/
t
我
A
C
_
A
_
0
0
1
8
4
p
d
.
F
乙
y
G
你
e
s
t
t
哦
n
0
7
S
e
p
e
米
乙
e
r
2
0
2
3
303
thusobtain10subgraphswith350nodeseach.Wetrainamodelforeachsubgraphiandtestitonsub-graphi+1(mod10),ensuringthatedgesfromthetraininggraphareremovedfromthetestinggraph.TheBFSsamplingparadigmwasusedbecausethealternative(‘randomsampling’inFig.2)pro-ducessubgraphswithmostlyisolatededgesandonlyafewtriangles—anunrealisticscenario.Evaluatedmodels.Weevaluatethreemodels:1.Astandard,text-basedsentimentmodelthattreatsedgesasindependentdatapoints;2.ourfullmodelasspecifiedinSec.3.4,whichcombinesedgecostsbasedonthepredictionsofthetext-basedsentimentmodelwithtrianglecostscapturingnetworkcontext;3.aversionofourmodelthatconsidersonlytrian-glecosts,whileignoringthepredictionsofthetext-basedsentimentmodel(akintothemodelproposedbyBachetal.(2013)).Werefertothesemodelsas‘sentiment’,‘combined’,and‘network’,respectively.Sentimentmodel.Ourtext-basedsentimentmodelisanL2-regularizedlogistic-regressionclassifierwhosefeaturesaretermfrequenciesofthe10,000overallmostfrequentwords.TheL2-penaltyischo-senviacross-validationonthetrainingset.Sincecommentsoftenexplicitlycontainthelabel(‘sup-port’or‘oppose’),weremoveallwordswithpre-fixes‘support’or‘oppos’.Wetrainthemodelonlyonce,onarandomsampleof1,000commentsdrawnfromthesetofall160Kcomments(thevastmajorityofwhichwillnotappearinour10subgraphs).Evidenceratio.Regardingtheothertwomodels,recallfromSec.3.4ourdefinitionoftheevidenceratio,thefractionofedgesignsthatarefixedasevi-denceandneednotbeinferred.Inourexperiments,weexploretheimpactoftheevidenceratioduringtrainingandtesting,sinceweexpectperformancetoincreaseasmoreevidenceisavailable.(Weusethesameevidenceratiofortrainingandtesting,butthisneednotnecessarilybeso.)Metrics.Asourprincipalevaluationmetrics,weusetheareasunderthecurve(AUC)ofthereceiveroperatingcharacteristic(ROC)curveaswellastheprecision–recall(PR)curves.TherearetwoPRllllEvidence ratioArea under the curve12.5%25%50%75%0.50.60.70.80.91.0llllllll(A)AUC/ROCllllEvidence ratio12.5%25%50%75%0.20.40.60.81.0llllllllCombinedSentimentNetworkRandom(乙)AUC/negPRFigure3:AUCasfunctionofevidenceratio(维基百科),withstandarderrors.curves,oneforthepositiveclass,theotherforthenegativeone.Ofthesetwo,thepositiveclassislessinteresting:duetotheclassimbalanceof76%posi-tiveedges,evenarandomguesserwouldachieveanAUCof0.76.ThePRcurveofthenegativeclassismoreinformative:这里,itismuchhardertoachievehighAUC,sincerandomguessingyieldsonly0.24.Moreover,thenegativeedgesarearguablymoreim-portant,notonlybecausetheyarerarer,butalsobe-causetheyindicatetensionsinthenetwork,whichwemightbeinterestedindetectingandresolving.Forthesereasons,wereportonlytheAUCunderthenegativePRcurve(AUC/negPR)here.Additionally,wereporttheareaundertheROCcurve(AUC/ROC),astandardmetricforquantify-ingclassificationperformanceonunbalanceddata.Itcapturestheprobabilityofarandompositivetestexamplereceivingahigherscorethanarandomneg-ativeone(soguessinggivesanAUC/ROCof0.5).4.3ResultsPerformanceasafunctionofevidenceratio.TheAUCsasfunctionsoftheevidenceratioareshowninFig.3(A).(WeemphasizethattheseplotsarenotthemselvesROCandPRcurves;相当,theyarede-rivedfromthosecurvesbymeasuringAUCforarangeofmodels,parametrizedbyevidenceratio.)Sinceweusethesamesentimentmodelinallcases(Sec.4.2),itsperformance(黄色的)doesnotdependontheevidenceratio.Itisremarkablyhigh,atanAUC/ROCof0.88,asaconsequenceofthehighlyindicative,sometimesevenformulaic,lan-guageusedinthecomments(examplesinSec.4.2).Thenetwork-onlymodel(蓝色的)workspoorlyonverylittleevidence(AUC/ROC0.56for12.5%ev-
我
D
哦
w
n
哦
A
d
e
d
F
r
哦
米
H
t
t
p
:
/
/
d
我
r
e
C
t
.
米
我
t
.
e
d
你
/
t
A
C
我
/
我
A
r
t
我
C
e
–
p
d
F
/
d
哦
我
/
.
1
0
1
1
6
2
/
t
我
A
C
_
A
_
0
0
1
8
4
1
5
6
6
8
9
9
/
/
t
我
A
C
_
A
_
0
0
1
8
4
p
d
.
F
乙
y
G
你
e
s
t
t
哦
n
0
7
S
e
p
e
米
乙
e
r
2
0
2
3
304
lllllllNumber of dropped featuresArea under the curve01050100500100020000.50.60.70.80.91.0llllllllllllll(A)AUC/ROClllllllNumber of dropped features01050100500100020000.20.40.60.81.0llllllllllllllCombinedSentimentNetworkRandom(乙)AUC/negPRFigure4:AUCasfunctionofnumberofdroppedfeatures(维基百科),withstandarderrors.Evidenceratio75%.idence)butimprovessteadilyasmoreevidenceisused(AUC/ROC0.82for75%evidence):thisisin-tuitive,sincemoreevidencemeansstrongercontextforeachedgesigntobepredicted.Althoughthenetwork-onlymodelworkspoorlyonlittleevidence,ourfullmodel(黑色的),whichsyn-thesizesthesentimentandnetworkmodels,isnotaf-fectedbythisandeffectivelydefaultstothebehaviorofthesentiment-onlymodel.Furthermore,althoughthenetwork-onlymodelneverattainstheperfor-manceofthesentiment-onlymodel,combiningthetwoinourfullmodel(黑色的)nonethelessyieldsasmallperformanceboostintermsofAUC/ROCto0.89for75%evidence.Thegainsaresignifi-cantlylargerwhenweconsiderAUC/negPRinsteadofAUC/ROC:whilethesentimentmodelachieves0.60,thecombinedmodelimprovesonthisby13%,to0.68,at75%evidenceratio.Performanceasafunctionofsentiment-modelquality.Itseemshardtoimprovebymuchonasen-timentmodelthatachievesanAUC/ROCof0.88onitsown;theWikipediacorpusoffersanexception-allyexplicitlinguisticsignal.Hence,inournextex-periment,weexploresystematicallyhowourmodelbehavesunderalesspowerfulsentimentmodel.First,wemeasure,foreachfeature(i.e.,word),howinformativeitisonitsownforpredictingthesignsofedges(quantifiedbyitsmutualinformationwiththeedgesign),whichinducesarankingoffea-turesintermsofinformativeness.Now,tomakethesentimentmodellesspowerfulinacontrolledway,wedropthetopmfeaturesandrepeattheexperimentdescribedaboveforarangeofmvalues(wherewekeeptheevidenceratiofixedat75%).llllllllll1e−041e−021e+00Sentiment−model prediction peNorm. cost for deviating from pe0.10.20.30.40.50.60.70.80.91.0Figure5:Normalizedcostλ(我)(definedinSec.4.3;log-arithmicscale)fordeviatingfromsentiment-modelpre-dictionspe,forbinsi=1,…,10(维基百科).Upperbinboundariesonthex-axis.Valuesshownareaveragesover10folds.Evidenceratio75%.Fig.4showsthattheperformanceofthesenti-mentmodel(黄色的)declinesdrasticallyasmorefeaturesareremoved.Thecombinedmodel(黑色的),onthecontrary,ismuchlessaffected:whentheper-formanceofthesentimentmodeldropstothatofthenetwork-only(蓝色的;ROC/AUC0.81),thecombinedmodelisstillstrongerthanboth(0.86).Evenasthesentimentmodelapproachesrandomperformance,thecombinedmodelstillneverdropsbelowthenet-work-onlymodel—itsimplylearnstodisregardthepredictionsofthesentimentmodelaltogether.Learnededgecosts.RecallfromthefinalpartofSec.3.4thateachoutputpeofthesentimentmodelfallsintooneof10bins[0,0.1],…,[0.9,1],withseparateedge-costparametersλ(我)1andλ(我)0learnedforeachbucketi.Therationalewastogivethemodelthefreedomtotradeoffedgeandtrianglecostsdifferentlyforeachedgee,dependingonhowinformativethesentimentmodel’spredictionpeis.Thegoalofthissectionistounderstandwhetherourmodelindeedexposessuchbehavior.RecallfromEq.3thatλ1istheconstantwithwhichtheab-solutedifferencebetweenpeandtheinferrededgesignxeismultipliedwhenxe>pe,whileλ0istheconstantwhenxe