In this report we describe the previous research done by our institute in the eld of requirement analysis using di erent natural language processing methods. To represent the di erent degrees of similarity between words we implemented di erent methods that make use of synonyms and hyperonyms. We present the strengths of our methods and identify their weaknesses. For our future research we want to incorporate Word Embeddings as they solve most of the di culties we faced with synonyms and hyperonyms.
2.1 To identify such a combination we implemented multiple algoriths to improve the clustering of their methods (such as k-Means [Llo82], ClusterART [Mas03] and Neural Gas [MS+91]) and distance functions (such as euclidean distance and manhattan distance). Following the common Bag of Words approach, the requirements were Copyright c 2018 by the paper's authors. Copying permitted for private and academic purposes. translated into vectors that represented how often certain words appeared. This resulted in over a thousand of dimensions and thus leaving us vulnerable for the curse of dimensionality. This "curse" describes problems that arise when trying to calculate the distance between objects high dimensionality. With higher dimensionality distances grow more alike and thus it is hard to di erentiate between similar and not similar objects [SEK04].
We tried to reduce the number of dimensions by using stopwords ltering and lemmatization of words. Additionally we used tf-idf as suggested by the literature [SM86]. 2.2
We tried to mitigate the e ects that using di erent words for similar semantic intentions (e.g. using broadcast instead of send ) had on the distances of requirements by using synonym lists. The idea is to replace each word with a speci c synonym, such that words like transfer and broadcast would be replaced by the word send. This reduced the number of dimensions by a small amount, as well as putting requirements with those similar words closer together. However, this makes words that are similar into the same word, thus having no distance between them. But since those words are not the same, a more nuanced method, in which words can be similar without being the same word, would be preferred. 2.3
In a next step we enriched the text by using an ontology. This allowed us to determine hyperonyms of a word and then enrich the text with this information. The hyperonym of a word is a word describing the more general concept. For example, the hyperonym of car would be vehicle and the hyperonym of red would be color. It is noteworthy that words can have multiple hyperonyms. For instance, the word watch is a clock as well as an accessoire. For our method we enriched the text by adding all hyperonym information available to this word (meaning the di erent hyperonyms as well as the hypernyms of those words and so on) to the sentence. This information can contain more then ten or twenty words and thus increases the size of the sentences, as well as more than double the dimension size. However, similar words like car and truck will then share some words in this tree, increasing the similarity between both sentences, while also describing the di erences between the words with another subtree. For our tests we made use of the GermaNet ontology.1 2.4
Even though both approaches have theoretical advantages, in our experience they proved to be not perfect. While our synonyms approach reduced the dimensionality, it provided only a binary similarity between words, either they are the same or not. In contrast, the hyperonym approach with an ontology was able to provide more di erentiated information on words, but in doing more than doubled the number of di erent words in our corpus.
Additionally, we faced another problem with those approaches. In general, words can have multiple meanings, for example homonyms, like the word bear, which can describe a mammal, as well as tolerating or enduring something. But other words can also have slightly di erent meanings. The word group can describe multiple things, for example a criminal group (gang) or a musical group (band ). In both cases a collective of persons is described, but both would have di erent synonyms and hyperonyms. Currently we designed an algorithm that tries to solve this problem by previously determining the context of the requirements (is the text about criminals or musicians?) and then chooses the appropriate meaning of the word. 2.5
In a rst evaluation we tried to determine the impacts of di erent parts on the clustering quality. We decided to use external metrics to determine the quality of our algorithms. As we wanted to measure the potential support our software could have on requirements engineers, we measured the algorithms against a grouping provided by our own experts. They grouped the technical requirements by their topic, meaning which technical subparts were speci ed. The grouping was done to get a better overview about the current status of the requirement stock.
This means that we had to use a xed number of clusters to compare against the hand crafted grouping. Additionally this meant that we judged the quality of the algorithm on how well it was able to recreate a human made grouping, while dismissing potentially good results that were speci c to the algorithm. Thus we wanted 1http://www.sfs.uni-tuebingen.de/lsd/tools.shtml, last access on 2018-01-25 requirements to be treated as similar, when the speci ed technical concept of the requirements was similar. Despite these restrictions on our evaluation, we were not able to determine a better way of measuring the quality of our algorithms, as we did not think that for our case internal metrics were suitable. How to improve the evaluation of our requirement analysis framework is thus an open question for our team.
We tested multiple combinations of algorithms, distance functions, modi ers (such as lemmatization and stop words lter), as well as our synonyms and ontology approaches. We calculated the F1 scores for all those combinations and found small indications showing good combinations. Multiple of those good combinations contained our synonyms as well as our ontology approach. We published our results2 as well as parts of our algorithmic framework3 on GitHub. 3
Today sophisticated word embedding algorithms, like word2vec [MCCD13], GloVe [PSM14] and fasttext [BGJM16], are able to place words in a vector space that contains semantic information about the words. Thus similar words will be placed close to each other and form groups of words. This means, that the distance between two words in this space can describe how semantically similar they are. Meaning that synonyms as well as hyperonyms of a certain word will be placed close to each other, while non related words will have a higher distance. Additionally, the words have a xed dimensionality (generally orders of magnitude lower than the number of di erent words in the corpus). Previous work in requirement analysis discusses the possibility of integrating Word Embeddings [FDE+17] or integrates them in classi cation approaches [WV16]. Additionally, Lucassen et. al also use the approach for clustering requirements [LDvdWB16].
Looking closer at word2vec and fasttext, these models are generated by reading lage sources of human text, such as Wikipedia, and trying to determine the word positions of word x by looking at words used around x. In short, the model is trained by looking at n words before and after x and is then encouraged to guess x using only the surrounding words (other methods like the Skip-Gramm Model [MSC+13], GloVe [PSM14] or fasttext [BGJM16] prove to be more precise, but would be too extensive in this report). Thus the position of x in the vector space is determined by the words often used with x. The assumption is (and proves to be correct), that similar words are used with the same surrounding words. Because of this training, we assume that the model trained with an appropriate dataset contains ner nuances of words like group, as the surrounding words will catch the di erent meanings and contexts (see the example in 2.4 the word can be used with).
Looking back again at the di culties explained in section 2.4, word embeddings seem to solve exactly those problems. The xed dimension size of the vectors around 200 to 500 dimensions (as recommended by Mikolov et. al [MCCD13]) is signi cantly less than our datasets containing thousands of requirements, with more than 1800 unique words, not counting the number of words that occur when using our ontology approach. This means that the number of dimensions in each vector is reduced signi cantly and thus the calculation of the distances is more meaningful [SEK04]. Words which are synonyms to each other will be placed close in the vector space and thus result in a low distance between those words, while still maintaining their identity. Further, the di erent meanings of the words are taken into consideration in the vector space due to the nature of the training. Thus, we hope to improve our clustering results even further when using this approach. Additionally, we want to try to use them together and evaluate these results.
Another open question we face is the training of the model. The fasttext framework provides pre trained models on 294 languages, using Wikipedia as training data4, but requirements are mostly speci c to a certain domain and so the words may not be presented well or at all in Wikipedia. Thus, using a model trained on a domain speci c model may also improve the results.
Another research question is how to de ne similarity between requirements when using word embeddings. Previously, we de ned a requirement by adding all words together into one vector which represented the words and their number of occurrences in this requirement. However the number of words in a requirement is now e ecting the result in a more meaningful way [KDR15]. Averaging the resulting vector over the number of words could be one solution, but is not feasible, since the average of two sentences can be the same even though they do not share common words with each other. This is due to the fact that the position of words and the spaces between them carries semantic meaning.
2https://github.com/fkie/requirement-clustering-evaluation-2017 3https://github.com/fkie/requirement-clustering 4https://github.com/facebookresearch/fastText#enriching-word-vectors-with-subword-information [BGJM16] [FDE+17]
Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov. Enriching word vectors with subword information. arXiv preprint arXiv:1607.04606, 2016.
Alessio Ferrari, Felice DellOrletta, Andrea Esuli, Vincenzo Gervasi, and Stefania Gnesi. Natural language requirements processing: A 4d vision. IEEE Software, 34(6):28{35, 2017.
Tom Kenter and Maarten De Rijke. Short text similarity with word embeddings. In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, pages 1411{1420. ACM, 2015.
Because of these problems Kenter et. al suggest a di erent formula called semantic text similarity (sts) [KDR15]. The idea in short is that for the distance of two sentences (requirements) each word of sentence s1 will be matched to the best corresponding word of sentence s2. The distance of those words will be calculated and added together. The exact formula is: fsts(sl; ss) =
Here sl is the longer of the two sentences, while ss is the shorter one. The parameter avgsl describes the average sentence length of the data set, while b as well as k1 smooth the results and are set to b = 0:75 and k1 = 1:2 on default. The function sem(w; s) describes the semantic similarity of the word w w.r.t sentence s: where fsem(w; w) describes the similarity of both words. For this, the cosine similarity is suggested.
In the next step of our research we will use pre trained fasttext models for clustering requirements and the fsts formula to determine the similarity between requirements.
Stuart Lloyd. Least squares quantization in pcm. IEEE transactions on information theory, 28(2):129{137, 1982.
Louis Massey. On the quality of art1 text clustering. Neural Networks, 16(5):771{778, 2003. Tomas Mikolov, Kai Chen, Greg Corrado, and Je rey Dean. E cient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781, 2013.
Thomas Martinetz, Klaus Schulten, et al. A" neural-gas" network learns topologies. 1991. Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Je Dean. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems, pages 3111{3119, 2013.
Je rey Pennington, Richard Socher, and Christopher Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 1532{1543, 2014.
Michael Steinbach, Levent Ertoz, and Vipin Kumar. The Challenges of Clustering High Dimensional Data, pages 273{309. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004.
Gerard Salton and Michael J McGill. Introduction to modern information retrieval. 1986.