# Word Sense Disambiguation Using Clustered Sense Labels
## 2 Sense Definition Clustering  
Word sense definitions have been utilized for WSD tasks either as a surface form or a vector form [9; 15; 17; 20]. In this paper, we also use the word sense definition in a dictionary to calculate the vectors for the senses, assuming that the sense is represented by the vector of the sense definition. To produce the sense definition vector (SDV), we used Universal Sentence Encoder [21], which, at the time, was the best sentence vector generation program available. SDVs are clustered into groups of similar vectors. The similarity is measured using normalized Euclidean distance, which ranges from 0 to 1 as defined in the following:  
\[ndist(x-y)=\frac{1}{M}\sqrt{\sum_{i=1}^{n}(x_{i}-y_{i})^{2}}\]  
where \(M\) is the maximum distance in all the SDV pairs, and \(n\) is the dimension of \(x\), \(y\) vectors. Figure 1: Sense vocabulary compression using hypernym and hyponym relations [18]. A pair of vectors are clustered as a group under two conditions: 1. the similarity value is above a threshold, and 2. the new group does not include more than one sense in the same homograph set. This is accomplished by the sense definition clustering algorithm (SDC) as shown in Algorithm 1, which is a slight modification of the hierarchical agglomerative clustering (HAC) algorithm [22]. ```
1:Input: SDVs represented as \(\text{w}_{i}\) (1\(<=\text{i}<=\text{N}\))
2:Output: clustered SDVs
3:Place each \(\text{w}_{i}\) in a group, \(\text{g}_{i}\), as a set with one element
4:Let \(\text{G}=\{\text{x}\mid\text{x}=\text{g}_{i}\) (1\(<=\text{i}<=\text{N}\))
5:Calculate the similarity matrix for each pair of (\(\text{g}_{j}\), \(\text{g}_{k}\)) where \(j\
eq k\). 6:repeat
7:Find the most similar pair (\(\text{g}_{j}\), \(\text{g}_{k}\)) with their similarity above the threshold
8:Make a new group \(\text{g}_{jk}\) with union (\(\text{g}_{j}\), \(\text{g}_{k}\)) where \(j\
eq k\) and only if any pair of the padd group is not in the same homograph set
9:If \(\text{g}_{jk}\) equals null, then terminate
10: Let \(\text{G}=\text{G}-\text{g}_{j}-\text{g}_{k}+\text{g}_{jk}\)
11: Recalculate the similarity matrix
12:until\(|G|<=1\)
```  
**Algorithm 1** Sense Definition Clustering (SDC)  
The time complexity of the SDC algorithm is O(\(n^{3}\)), the same as HAC. Moreover, the number of SDVs is usually too large to be run by the complex clustering algorithm; in the case of WordNet the size is 207 K. Therefore, for practical reasons, we divided the initial large set of SDVs into smaller partitions to start the hierarchical agglomeration SDC with efficiently sized partitions rather than the set of singleton clusters [23]. We first divide the data by parts of speech (noun, verb, adjective, adverb) and then utilize a flat clustering program, such as the affinity propagation program (AP) [24] or the \(k\)-means program, Ref. [22] for further partitioning. Affinity propagation is good for partitioning with an appropriate number of clusters. However, it fails to partition very large datasets such as noun partition, because its algorithm needs considerable space to process various matrix calculations. In those cases, AP is run to determine the cluster size \(k\) for a randomly chosen subset of the dataset, and for partitioning, the \(k\)-means program is run using the \(k\) size determined on the original dataset. Once we have partitions, we apply the SDC algorithm to each partition to build a compressed sense vocabulary group within the partition. We then apply the SDC again to the newly grouped senses externally to find a higher common ancestor. The new clusters are given cluster numbers, which are used as compressed sense numbers. Figure 1(a) shows the overall flow of sense clustering. Figure 1(b) shows the clustering example in detail. In Figure 1(b), the three red dots represent the different senses of a homograph.