2. Methods and Problems
The main idea of the algorithm is the compilation of a list of ngrams, its further filtration, and application of NLP methods to determine repeating semantically significant word sequences. Formulas have at least two important features that are problematic for an automatic search:
- A formula can be not only closed (word for word repetition) but also open or semi-open (some of the slots in the word sequence can be variable; the word order can change) (Lamb 2015: 228-231);
- Certain formulas and their variants can appear rarely in the corpus.
Therefore, the entity filtering based on frequency is not applicable. Special heuristics were designed to gradually filter examples and combine contextual synonyms in groups. The algorithm consists of four main stages:
- Ngram list formation
- Ngram grouping
- Syntactic grouping
- Semantic clustering
2.1. Ngram list compilation
To begin with, the list of ngrams has to be compiled (4 to 8 words). To get only meaningful phrases, each ngram was tested on compliance with the following criteria: 1) Presence of a verb, 2) Syntactic integrity, 3) Part of speech (POS) significance of at least 90%. The phrasal syntactic integrity was validated based on the POS and word cases (i.e. there are no violations of agreement and government). The POS significance score was calculated according to the formula:
Significance - the significance of a POS (each POS was assigned a number reflecting its semantic significance in the process of phrase formation, see Appendix);
Frequency - frequency of a POS in an ngram;
nwords - number of words in an ngram.
Thus, the ngram was skipped if its score is less than 0.9 (the threshold was determined by a test sample analysis), if it does not have syntactic integrity and if it does not have a verb. As a result, a list of 663,775 phrases was compiled.
2.2. Ngram grouping
Then the ngrams should be grouped. The grouping consists of three stages: 1) the ngrams were normalised (e.g. adjectives and adverbs were omitted as modifiers may vary within the same structure or pronouns and proper nouns were transformed into POS and case tag, e.g. PrpNom, etc.); 2) resulting representations with the same word content but different word order were combined; 3) all phrases were grouped by their syntactic constituents, e.g. all sequences consisting of a verb, a pronoun in dative and a noun in nominative were grouped together.
2.3. Semantic clustering
As the ngram groups should be semantically similar, each syntactic group was clustered using the spectral clustering algorithm (von Luxburg 2007). This algorithm was adjusted for the current research purposes as a graph of phrases was created for each syntactic group where each two semantically similar nodes had a connection added. To find semantic similarity between the nodes, the following operation was designed: 1) each phrase was represented as a list of fastText vectors (Joulin et al. 2016); 2) the cosine similarities between words in the same position in construction were calculated; 3) the similarity scores for phrases were computed based on the average values of words they consist of. The resulting scores were used as weights for connections between graph nodes; the connection was added if the semantic similarity between the two phrases was more than 0.85.
2.4. Topic Modelling and Metrics Evaluation
As formulas in Old Icelandic sagas are usually used in similar situations (see Sävborg 2018: 58-59), the last step was to find clusters that occur in similar contexts. For this, a topic model for the whole corpus was built and each sentence received a vector of topic distribution in the surrounding fragment (5 sentences before and after). To evaluate the thematic similarity of phrases within the clusters special metrics were created: sparseness coefficient (how thematically sparse a certain cluster is) and cluster core (share of a strongly connected group of entries). To calculate sparseness coefficient community unfolding using greedy modularity maximization algorithm (Clauset et al. 2004) was performed on cluster graphs that were beforehand reduced by calculating median vectors of thematically similar ngram entries. The formula goes as follows:
Nbiggest - the biggest community size
Nnodes - cluster size
𝜎 - standard deviation of community sizes
To calculate the cluster core, outliers are omitted on each step and the average pairwise cosine similarity is computed until it reaches 0.9; the coefficient is the share of entries left.