Bakalárská Práceˇ

Chapter 2Coreference Resolution2.1Introduction and MotivationIn this chapter, we are focusing on the task of automatic coreference resolution;the issue we tackle is whether the image labels can be a help for this task. Wespeculate that there can be labels among the image labels that co-refer, i.e. theyrefer to the same entity. We have not found any paper that addresses the same issueso far. So not only given that, it is almost impossible to predict the results beforeperforming experiments.This chapter is organized as follows: we remind the notion of coreference in Section 2.2. In Subsection 2.3.1 we present statistics on the ESP game image labels. Theapplication designed for user-friendly viewing the labels and their relations is introduced in Subsection 2.4.1. The algorithm to construct pseudo-coreference chains inthe text is provided in great details in Subsection 2.4.2. The application for viewing and comparing the coreference versus pseudo-coreference chains is describedin Subsection 2.4.3. Evaluation of pseudo-coreference chains against manual annotation is discussed in Section 2.5. We conclude with Section 2.6.2.2CoreferenceCoreference occurs when several referring expressions in a text refer to the sameentity (e.g. person, thing, fact). A coreferential pair is a pair of the referring expressions. A sequence of coreferential pairs referring to the same entity in a text formsa coreference chain. In the passage from (Doyle, 1887), one can read the following coreference chain I, I, me, I, me man; another coreference chain is someone,Stamford, who, dresser can be seen there: On the very day that I had come to thisconclusion I was standing at the Criterion Bar, when someone tapped me on theshoulder, and turning round. I recognized young Stamford who had been a dresser10

under me at Barts. The sight of a friendly face in the great wilderness of London isa pleasant thing indeed to a lonely man.2.32.3.1DataAnalysis of the English DataThe ESPgame100k data (”data”)1 we inspect throughout our project come fromthe ESP Game (von Ahn, Dabish, 2004)2 as described in Chapter 1As a result of the ESP game sessions, there is a label-set for each of the imagesthat have already been assigned some labels in the game and these label-sets arestored in the game’s database together with the corresponding image. The data,which we use as the input for our project, is a sample part of the whole databasethat consists of 100,000 image-labels pairs.3Thus for each image in the data there is a non-empty label-set. A label-set isa set of labels related to the same image, like car, decker, double, double decker,driver, england, london, man, people, red, ride, road, tour, transportation.Neighbors of a label lab is a set of labels which includes all labels from alllabel-sets in which the label lab occurred. So the neighbors of double decker include all labels from the label-set from Figure 1 including lab itself, i.e. car, decker,double, double decker, driver, england, london, man, people, red, ride, road, tour,transportation, but the neigbors of lab also include labels from other label-sets, forinstance cloud, tire, wheels because each one of them co-occur together with lab inat least one label-set. So we can say that for instance wheels is a neigbor of lab.f req(w1 , w2 ) stands for the number of label-sets where the labels w1 , w2 cooccur together. We call it neighborhood frequency. Table 1 provides statistics acquired from the data, i.e. from the ESPgame100k sample.According to the game designers, the game server is equipped with an English dictionary to alert players when they have misspelled a word. However,we discover that not always is the label a good description of the particularimage. It can be misspelled, which is frequent, or it even does not have tobe English. Some examples of the various spelling errors are havent or family fued. Examples of non-English labels are zeitungen, nuestra or zukunft. Weuse the open source spell checker Aspell4 to discover such errors. However,we do not have to handle them in a special manner since our procedure to construct pseudo-coreference chains in texts does not take them into account anyway.1http://www.cs.cmu.edu/ biglou/resources/http://gwap.com3We do not know exactly what good label threshold X was used for the images presented in thedata. According to literature (for ex. (von Ahn, 2005)), we suppose X 1.4http://aspell.net/211

# of unique label-setsaverage # of labels in label-setsthe biggest label-set sizethe smallest label-set size# of unique labels# of unique single word labels# of unique multi word labels# of unique le 2.1: The ESPgame100k data: statisticsWe also tagged the labels with Stanford Log-linear Part-Of-SpeechTagger (Toutanova, Klein, Manning, Singer, 2003) to discover foreign words.2.3.2The Retrieval of Czech Data and Their AnalysisWe translate the original data from English to Czech using The CzengProbability Dictionary5 (”dictionary”). For a given English word and itspart of speech tag (POS tag) the dictionary contains different Czech words withPOS tags and with probabilities P that the Czech word and its POS tag is a goodtranslation for the English word and its POS tag. We call these probabilities translation probabilities. As you can see in Table 2.2, the Czech translations are sorted bythe translation probabilities P .The Algorithm for Translating Label-sets into CzechEnglish label-sets are translated into Czech label by label.One English label can bear more morphological meanings mainly because ofthe common conversion in English (”run” as a verb or noun). Because the labelsare not part of a broader context like sentence, we cannot say for sure which POSthe original label is. Since we want to preserve as many possible meanings of theoriginal label as possible in the translated label-set, but still we do not want thetranslated label-sets to be too large either, we chose to translate the original labeltogether with the POS tag.In the dictionary, we look up the English label lab that we want to translate intoCzech. The label might appear in the dictionary with more POS tags as a differentpart of speech. In Table 2.3 we can see an example of looking up the label twelve.5It is a dictionary that was extracted from the parallel corpus CzEng by Zdeněk Žabokrtský atUFAL, Charles University in Prague in 2008.12

pský#AAgroSciences#Nspolečnost#NAgroSciences#N 6840.0086480.5020780.497922Table 2.2: Example of the dictionary formatWhen translating twelve in this example we get one translation for twelve as acardinal number and another translation for twelve as a noun.6To translate the combination of label and a POS tag we always pick the mostprobable Czech translation without further investigations. In our case the translations are dvanáct and dvanáctka and they are highlighted in Table 2.3.When translating the label-set into Czech, we simply substitute the English label with a list of Czech translations as described in the previous step. The Englishmulti-word labels are currently not translated, unless they appear in the Czengdictionary as a whole expression.7Example: Translating Label-setsIn this example we illustrate the translation in which the English label-set{asian, background, bag, blue, desk, desktop, face, girl, keyboard, kid, moni6It would also be possible to translate only the one combination of label and its POS tag whichhas the highest translation probability. This would obviously ensure that we always get only onetranslation for a label. In the example it would be dvanáct, because P (dvanáct) P (dvanáctka).However, it would also mean that we would not take the other part of speech types into account atall. As we want to keep as many morphological meanings as possible, we better decided to have anEnglish label translated by more Czech labels, than to lose meanings when choosing only the mostprobable part of speech.7Another method would be to tear apart the English multi-word labels, translate them word byword and then put them together. But this has no sense considering that the algorithms we test onthe ESP data work in fact only with single-word labels.13

en#C0.032349twelve#C dvanáctiměsíční#A e 2.3: Looking up the label twelve in the dictionarytor, mouse, pc, picture, red, screen, smile, wallpaper, white, windows, woman}is translated into the Czech label-set {asijský, Asie, pozadí, společenský, pytel, sebrat, modrý, stůl, plocha, čelit, tvář, dívka, holkařit, klávesnice, legrace,zhýčkaný, dítě, sledovat, monitor, pohyb, myš, PC, obrázek, představovat, věrná,červený, methylčerveně, prověrka, obrazovka, usmát se, úsměv, tapetovat, tapeta,bílý, bezvousý, okna, žena}.Table 2.4 shows parts from the dictionary used for translating the individualEnglish labels from the label-set into Czech. This excerpt is shortened. For a combination of a label and its POS tag only the most probable Czech translation (theone actually used for the translation of a label and its POS tag) is shown here andthe other translations were ommited from this excerpt of the dictionary.The first label in the original label-set is asian. So the algorithm looks it upin the dictionary and finds there are multiple translations for asian as an adjectiveand multiple translations for asian as a noun (only the most probable of them aredisplayed in Table 2.4). The algorithm takes the most probable translation for asianas a noun and as an adjective, i.e. the two words asijský and Asie. They both becomethe translation for the original label asian.In the same fashion, background as an adjective is translated into společenskýand background as a noun is translated into pozadí; white as an adjective and as anoun are translated into bílý and white as a verb is translated into bezvousý.88Of course, this is a nonsense. It only prooves that the dictionary is not flawless, because it hadbeen extracted by a program from the CzEng parallel corpus.14

ian#NAsie#N0.389752background#A společenský#A e 2.4: The excerpt from the dictionary used for translating the label-set. Shortened.2.42.4.1ToolsLabel Viewer ApplicationThe Label Viewer is an application designed for user-friendly viewing theEnglish or Czech labels and their relations. It has three main parts as depicted inFigure 2.1: part 1 - list of labels. Labels from the ESP data are displayed here. Eachlabel has its id and frequency. Frequency means the number of label-setscontaining the label. The label cathedral is selected in part 1 of the example. part 2 - list of label-sets. Selecting a label from part 1 reveals the list of id’sof label-sets in which the label (i.e. cathedral) occurred (part 2 - left column).One can click on a label-set id to inspect the label-set’s labels (part 2 - rightcolumn) and the original picture which belongs to the viewed label-set. In theFigure 2.1 the label-set with id 493 is shown. part 3 - list of neighbors. In part 3, the neighbors for a selected label (i.e.cathedral) are shown in the neighbors column. The frequency hereis the number of label-sets in which the selected label (cathedral) and theselected neighbor (spire in the right column in part 3) co-occurred together,i.e. f req(w1 , w2 ) described in 2.3.1. In our example 56 means that labelscathedral and spire co-occured together in 56 different label-sets.15

Both lists of labels and neighbors can be resorted alphabetically or by frequency.By default, labels are sorted alphabetically and neighbors by frequency.2.4.2Algorithm for Finding the Pseudo-Coreference ChainsWe take an input text and we find the pairs of ’semantically related’ ESP labelsin this text. We call the pairs of ESP labels in the texts pseudo-coreference pairs.Then we construct pseudo-coreference chains from them.We know how many times two labels co-occur together in the data, i.e.how many times they label the same images. We measure the degree of being semantically related labels by setting a neighborhood threshold Z.Both the pseudo-coreference pairs and chains are depending on the variableneighborhood threshold Z.For a given Z, we search for the pseudo-coreference chains in these five steps.The algorithm is ilustrated with on an example.1. We have Penn Treebank POS tags9 for each word in the text. Sincewe suppose that the candidates for coreference are Wh-determiners, Whpronouns, nouns, personal pronouns and cardinal numbers, the words withthe Penn Treebank POS tags WDT, WP, N, PRP, CD, respectively, become the candidates to be members of coreferential chains; thus weunlock them for the next steps while we lock the words with other POS tags.In this example of input text, the unlocked words are highlighted.”There was a modern brown building with an oldantique arch above the door. The arch didn’t fit tothe design of the building so much that I thoughtthe architect who projected it must have been madto use it here.”.2. On the ESP data layer, we iterate through label-sets and take each label-set’slabels as nodes V of a graph G (V, E) in which edges E are defined so:e (v1 , v2 ) E if f req(v1 , v2 ) Z. We call this graph neighborhoodgraph.In Table 2.5 there are label-set’s neighborhood frequencies, from whichwe construct the neighborhood graph as described above (see the resulting neighborhood graph in Table 2.6 and in Figure 2.2). Because neighborhood of labels is a symetrical relation, the neighborhood graph is undirected.9http://www.ling.upenn.edu/courses/Fall 2003/ling001/penntreebank pos.html16

Figure 2.1: The screenshot of the label viewer program17

Z 500 arch oroldwoodbuilding cathedral church41810823511489329369152037532762001187door old wood232 15666528 1056 1482771 8363643610914172 297692248 3173095866 3183056Table 2.5: Neighbor frequencies in a label-set.Z 500 arch brown oldwoodcathedral church door old0000001101110000100101wood01000001Table 2.6: Neighborhood graph of a label-set given by matrix.3. For each neighborhood graph we start the algorithm for finding connectedcomponents (Hopcroft, Tarjan, 1973). This algorithm computes the neighborhood graph’s components: G1 (V1 , E1 ), .Gn (Vn , En ). These components are the costituting units of pseudo-coreference chains.The graph in Figure 2.2 has three components whichare defined by these sets of vertices V1 {arch}, V2 {brown, building, church, door, old, wood} and V3 {cathedral}.4. We now have to go down from the layer of labels to the layer of the inputtext. A label can appear in the text 0, ., nlabel times. So for a neighborhoodgraph we take each of its components Gi (Vi , Ei ) from the previous stepand propagate the labels from that component Gi to the textual layer. For eachvertex v (i.e. label) we save the relevant occurences of the label v as a wordin the input text. If label v is not present in the text, we save nothing, if it ispresent 1, ., nv times, we save only the relevant occurences (i.e. those thathave been unlocked in the first step of the algorithm). So as a result for each18

Figure 2.2: Neighborhood graph of a label-setof the component Gi (Vi , Ei ) of the neighborhood graph we get a list ofoccurences (unlocked words) of the vertexes Vi (i.e. labels) in the input text.The resulting lists from the example are List1 {arch, arch} andList2 {building, building, door}.5. We filter out lists of occurences with size 1. The last step is to resort thelists of occurences, so that the pseudo-coreference chains are well ordered.A list of words is well ordered, if for the list l w1 , ., wn it is true that i 1, ., i : pos(wi ) pos(wi 1 ), where pos(wi ) is the function thatreturns the word’s position within the input text. The sorted lists with size 2 are the pseudo-coreference chains.Both the lists from the previous step contain at least two words, and afterordering we get these pseudo-coreference chains: Chain1 {arch, arch}and Chain2 {building, door, building}.Summing up the Algorithm1. Choose a threshold Z and iterate through label-sets.2. Take the labels from the current label-set (lset) as nodes of a graph, wheretwo labels (i.e. vertex) lab1, lab2 are adjacent if f req(lab1, lab2) Z (socalled neighborhood graph).3. Find the connected components of the neighborhood graph. Iterate throughthose components.4. For labels of a component c find unlocked occurences of those labels in theinput text. These well ordered occurences (if there are at least 2 of them) forma pseudo-coreference chain.19

Computing the pseudo-coreference chains - time complexityThere are n 100, 000 label-sets in the data, let the biggest label-set’s size bemax. f req(lab1, lab2) can be determined in O(1) (the whole neighborhood relationis initialized only once after the program starts). For each label-set we construct theadjacency matrix in max2 O(1) O(1). The algorithm for finding connectedcomponents is linear in the number of vertex, which has upper bound max. So foreach label-set, we construct the matrix in O(1) and then in O(max) O(1) we findthe connected components. So finally we get linear time O(n) in the #label-sets inthe data to count all the connected components.Now getting to the textual layer, suppose that there are m max different labelsin a particular label-set that have to be expanded into pseudo-coreference chains onthe textual layer.Let the text length be k. Then each label can theoretically appear on k positions.So while propagating to the textual layer, we get to much worse complexity class.k k. k k max , which yields exponential time O(k max ) for propagating a label,resp. a connected component from a label-set (measured by the length of the inputtext). The whole time complexity of counting the pseudo-coference chains for datawith n label-sets and maximum size of the label-set max is thus O(n k max ).This does not matter in this project, because here we were testing the algorithmon very small input texts where only excerpts of a length of 100 sentences wereused. The exponential complexity here is due to not having a limit or restriction onhow far from each other two pseudo-coreference words can be. Here the domaineused is the whole text. If our method turned out to be of any use, it would be simpleto introduce such rule and limit the domaine to e.g. a paragraph, which size is presumably not dependent on the length of the input text and can be taken as a constant.If we limit the size of paragraph in the input text to para, then the resulting timecomplexity is linear O(n paramax ) O(n).2.4.3Chains Viewer applicationThe Chains Viewer program is an application designed for computing thepseudo-coreference chains over a sample Czech or English text in

ilustrating an agreement on a string. It comes from (von Ahn, Dabish, 2004). Each image is associated with a list of taboo words that are not allowed to be entered by the players: the string becomes a label when two players agree on it and consequently the label becomes a taboo word associated with the image, which will