Decipherment of Lost Ancient Scripts as Combinatorial Optimisation Using Coupled Simulated Annealing (2023)

Abstract: This paper presents a new approach to the ancient scripts decipherment problem based on combinatorial optimisation and coupled simulated annealing, an advanced non-convex optimisation procedure. Solutions are encoded by using k-permutations allowing for null, oneto-many, and many-to-one mappings between signs. The proposed system is able to produce enhanced results in cognate identification when compared to the state-of-the-art systems on standard evaluation benchmarks used in literature.

## introduction there are still a number of undeciphered scripts in the world and most of them date back thousands of years. the lack of an appropriate amount of inscriptions, the lack of known language descendants written using these scripts or even any certainty whether the symbols actually constitute a writing system made the decipherment of such scripts really challenging. in the aegean area, for example, we can count at least three syllabic scripts that have not been deciphered yet, namely the linear a script, cretan hieroglyphs and the cypro-minoan script. they are scripts strictly connected from a historical point of view, but no one has yet been able to solve these decipherment puzzles. in this work we deal with general decipherment problems, but we are mainly interested in investigating these undeciphered scripts from the aegean area. deciphering an ancient script is, in general, a very complex task; the solution of this problem has been often split into different subproblems in order to obtain specific answers or to simplify the task by decomposing it into simpler problems. in the literature, we can find various contributions dealing with all these subproblems and propose computational methods for solving them in some way, often in relation to one specific script. in order, we have to (a) decide if a set of symbols actually represent a writing system, then (b) we have to devise appropriate procedures to isolate or segment the stream of symbols into a sequence of single signs and then (c) reduce the set of signs to the minimal set for the given writing system forming the alphabet (or syllabary, or whatever inventory of signs), identifying all the allographs. once we have such a minimal, but complete, set of symbols, we can start (d) assigning to them phonetic/orthographic values and, finally, (e) trying to match phonetic/orthographic transcriptions to a specific language. here we are interested in studying and discussing steps (d) and (e). ## related works any modern attempt to decipher lost scripts using computational tools, a field that has been gaining more and more interest in nlp in the last years @xcite , is based on the comparison of a lost script/language wordlist with words of a known deciphered script/language. these computational approaches have to address two main problems: the first regards the possibility that the two scripts do not correspond. in this case the phonological values of the lost symbols could also be unknown and the matching between the two wordlists must be preceded by some matching between scripts; then, the two wordlists must be matched in some way searching for "cognate" words, i.e. words in different languages that can share an etymological ancestor in a common parent language. some scholarly works focus only on cognate detection within the same script @xcite or directly using the international phonetic alphabet sound representations @xcite . in both cases the tested languages were typologically very similar. conversely, the most advanced recent studies on the automatic decipherment of lost languages proposed systems producing both signs mappings be-tween different scripts and mapping of words into their corresponding cognates (e.g. @xcite @xcite . these studies share a common view on the computational approach: they structured the algorithm as a two-step procedure, taking inspiration from the expectation-maximization (em) algorithm. the first step proposes a temporary matching between the two "alphabets" 1 , and the second step, by relying on the script-matching, tries to match the two word lists proposing possible cognates. at the beginning of the process the scripts matching will be almost random, and so will the cognate matching, but, after several iterations the whole process should converge proposing both a script-matching and a list of possible cognates. the key point hinges on finding an appropriate function, to be optimised by this iterative process, representing in an optimal way the concept of matching between words, including also some linguistic constraints regarding scripts, words and possibly sounds. let us review the most recent and relevant analyses, in our view, which tackle the decipherment problem in an automatic way, all following the general scheme just discussed. @xcite presented the first paper which adopts the modern approach to the computational decipherment problem: their method requires a non-parallel corpus in a known related language and produces both alphabetic mappings and translations of words into their corresponding cognates, employing a non-parametric bayesian framework to simultaneously capture both lowlevel sign mappings and high-level morphemic correspondences. they tested this method on ugaritic, an ancient semitic language, comparing it with old hebrew: the model correctly maps 29 of 30 signs to their old hebrew counterparts, and deduces the correct hebrew cognate for 60% of the ugaritic words that have cognates in old hebrew. @xcite took a different approach: they devised an objective function that, when optimised, yields accurate solutions to both decipherment and cognate pair identification problems. their system requires only a list of words in both languages as input. the proposed solution is both simple and elegant: binary variables govern both the matching between signs in the two scripts and the matching between the two 1 with the term "alphabet", we indicate a generic notion of inventory of signs, glyphs, etc. used as a writing system. lexica. by applying an integer combinatorial optimisation procedure, their system was able to obtain good results on the same problem introduced by @xcite and on a new matching task on romance languages. @xcite present a novel neural approach that defines the state-of-the-art for the automatic decipherment of lost languages producing the highest matching performance. to compensate for the lack of strong supervision information, their model is designed to include known patterns in language change documented by historical linguistics. the mapping between signs is carried out by a bidirectional recurrent neural network while the procedure for matching cognates is formalised as a minimumcost flow problem. they applied this method to the same problem presented in @xcite , a sort of benchmark in this field, and on a brand new dataset that included linear b and ancient mycenaean greek lexica obtaining very good mapping results. in a subsequent paper by @xcite , the authors faced a more difficult hurdle considering scripts that are not fully segmented into words and contexts in which the closest known language is not determined. by building on rich linguistic constraints reflecting consistent patterns in historical sound change, they were able to capture natural phonetic geometry by learning character embeddings based on the international phonetic alphabet. the resulting generative framework jointly models word segmentation and cognate alignment, informed by phonetic/phonological constraints. they tested their method on both deciphered languages, namely gothic and ugaritic, and on an undeciphered one, iberian, showing that incorporating phonetic geometry leads to consistent gains. the two studies from @xcite and @xcite are the main works with which to compare our proposal. @xcite proposed an approach that inspires our work, namely the possibility of tackling the decipherment problem as a pure function optimisation problem, but their results do not represent the state-of-the-art because they have been superseded by subsequent works. the work from @xcite , on the contrary, presents a system able to obtain very good results, but it is not as flexible as we need. with this respect, the mapping between lost and known signs is realised by a recurrent neural network (nn) and, despite the positive facts that context could be taken into account, it does not allow any further flexibility. in practical decipherment situations we have to face two problems that cannot be easily solved by the approach from @xcite : the first regards the fact that very often paleographers have a partial knowledge about the mapping of some signs and this information must be injected into the system and taken into account; the second problem concerns the fact that very often real inscriptions are broken or damaged and some signs cannot be read, thus some kind of uncertainty must be included into the system, for example by using wildcards or other special symbols. these special treatments are very hard to implement into a recurrent nn. moreover, deep nns typically require a lot of data in order to be properly trained and this is often not the case in real situations. as we said before, we are interested in studying some undeciphered scripts from aegean and we definitely need a more flexible system that allows partial readings and fixed knowledge to be included as well as being able to work on limited amounts of data. ## reference benchmarks and other datasets various datasets have been used in past studies and became standard benchmarks for evaluating the performance of any computational tool aiming at helping scholars in the decipherment process. ## the proposed method the proposed approach to the decipherment problem is configured as a global optimisation procedure taking inspiration from the work proposed in @xcite . we will introduce a flexible encoding of possible solutions and an 'energy function' able to capture the goodness of a single solution, both from the point of view of signs matching and lexica matchings; by minimising the energy function, we will search for suitable solutions to a decipherment problem. let us introduce some notation useful in the next sections: l s and k s are two linearly ordered sets foot_0 containing respectively the signs in the lost and known languages (with |l s | and |k s | their cardinality and l i , k j respectively the i-th and j-th element in the ordered sets), while l lex and k lex are the two lexica and |l lex | and |k lex | their respective number of words. ## results the two parameters n and m for solution shaping described in section 4.1 could be considered hyperparameters for the proposed method as they can give more power to the possible solutions at the price of more parameters to be fixed and thus slower convergence. we decided to avoid any optimisation of these parameters in our experiments and fix them using a very simple rule: @xmath0, @xmath1, @xmath2. ## discussion and conclusions we presented a new approach to the ancient scripts decipherment able to produce very good results in cognate identification w.r.t. the state-of-the-art. all the hyperparameters were not optimised at all and it seems reasonable that increasing n and/or m even better results can be reached. we plan to perform more experiments in that direction. another system feature worth of mention regards its ability to converge to reasonable solution for any simulation; even during the development phase, the proposed system never got trapped into very poor sub-optimal solutions. simulations took a relevant time to converge, but they always converged without any need to restart the process, a common technique for this kind of methods (see e.g. berg-kirkpatrick and klein 2013), confirming the strength of csa as a function optimisation technique. there are other approaches to the problem in the literature that we have not explicitly discussed in section 2 because not strictly devoted to the decipherment of ancient scripts, but address the problem of deciphering substitution or homophonic codes like the famous zodiac-408 cipher or the beale cipher (e.g. ravi and @xcite @xcite . for example ravi and @xcite proposed a stochastic model taking into account both token n-grams and dictionaries. knowing for certain the target language, they can estimate a language model (lm) using a large set of data, even artificially generated, and can take advantage of complete lexica and frequency information for the known language. unfortunately, when using these methods to solve the decipherment problems on ancient languages often the target language is not known for certain, maybe it is a language from the same area sharing the same data scarcity as the lost one and thus it is not possible to build useful lms or rely on a complete dictionary. on the contrary, everything is only partially known or unreliable: phonetic values, signs mappings, frequency information and the true underlying language. this facts make it very difficult to use methods like the one proposed by these authors. our very promising results in the decipherment of ancient scripts might suggest that these tools can solve all the unsolved problems, of palaeographic, epigraphic and linguistic nature, debated for years by experts. this is naturally not the case. these techniques, even if very promising, also present a large number of problems when applied in real decipherment attempts: (a) first of all, segmented and clean corpora are needed. building a corpus for an ancient undeciphered script, even in the case where we have already solved the segmentation problems and were able to collect single sign images and sign/word sequences, is not an easy task. most inscriptions are damaged and many signs are not readable. broken words and/or partial sentences are also frequent; (b) an extensive cognate list must be available, but in most real cases we only have two word lists that must be matched without any guarantee that lost language cognates are really present in the known language lexicon; (c) in nlp we have to make evaluation on well-known test beds and all the studies we discussed before worked on well known correspondences to prove the system effectiveness. it is an entirely different matter to test the same systems on real cases when we have to deal with unknown writing systems and their corresponding languages. in the light of these considerations, we agree with sproat (2020) who suggested that these tools can help paleographers shed light on the decipherment process, but we cannot rely on them only for providing a complete solution to our real problems without any human intervention for guiding the process and interpreting the results. however, our future plans regard the application of the proposed system to undeciphered scripts from the aegean area, hoping to shed some light on problems unresolved for centuries. codes and all datasets for reproducing the experiments are available on github foot_4 .