TL;DR
This paper introduces a novel approach to deciphering ancient scripts by framing it as a combinatorial optimization problem. They leverage Coupled Simulated Annealing (CSA) to efficiently explore the vast search space of possible sign mappings and word cognates, achieving state-of-the-art results on benchmark datasets.
What Problem Does This Paper Address?
Deciphering ancient, undeciphered scripts is a monumental challenge. Many scripts remain a mystery due to a lack of sufficient inscriptions, unknown language descendants, or even uncertainty about whether the symbols constitute a true writing system. Even for scripts with historical connections, like those from the Aegean region (Linear A, Cretan Hieroglyphs, Cypro-Minoan), decipherment has proven elusive. The process typically involves several sub-problems: identifying if a script is a writing system, segmenting symbols, determining the minimal set of signs (alphabet/syllabary), assigning phonetic/orthographic values, and finally, matching these to a known language. This paper focuses on the latter two, more complex stages: assigning phonetic values and identifying cognates.
Methods
The core of the proposed method is to treat script decipherment as a combinatorial optimization problem. They employ Coupled Simulated Annealing (CSA), an advanced metaheuristic for global optimization.
Key methodological components include:
- Flexible Solution Encoding: Solutions are encoded using "k-permutations," allowing for flexible mappings between signs of the lost script and known scripts. This encoding supports one-to-many, many-to-one, and even null mappings, accommodating uncertainties like broken inscriptions or partial knowledge of sign values. They introduce parameters
NandMto control the complexity and flexibility of these mappings. - Energy Function: A unified "energy function" is designed to measure the "goodness" of a potential solution. This function simultaneously considers both the accuracy of sign mappings and the likelihood of word cognates. It incorporates a modified Levenshtein distance (Edit Distance with Wildcards, EDW) to compare expanded transliterations of lost words with known words, and a variant of the Linear Sum Assignment (LSA) problem (Hungarian algorithm) for matching groups of words (cognates).
- Regularization: Penalty factors are introduced to discourage degenerate solutions, such as lost signs with no assignments or known signs with excessive multiple assignments.
- Coupled Simulated Annealing (CSA): This metaheuristic is chosen for its ability to be easily parallelized and its robust convergence properties. It uses multiple parallel SA processes that communicate and cooperate, leading to efficient exploration of the solution space and a reduced tendency to get stuck in local optima.
Datasets
The paper evaluates its approach on several standard benchmark datasets used in previous decipherment research:
- Ugaritic/Old Hebrew (U/OH): A dataset of 2214 cognate pairs, used by Snyder et al. (2010).
- Linear B/Mycenaean Greek (LB/MG): A dataset of 919 cognate pairs derived from a lexicon, focusing on syllabic scripts.
- Linear B/Mycenaean Greek (LB/MG) - names: A more challenging benchmark using a reduced Greek lexicon containing only proper nouns.
- Cypriot Syllabary/Arcadocypriot Greek (CS/AG): A newly compiled dataset of 693 cognate pairs, specifically for studying syllabic scripts from the same region as the Aegean scripts of interest.
Key Insights and Ideas
- Combinatorial Optimization for Decipherment: Framing script decipherment as a combinatorial optimization problem, rather than a purely statistical or machine learning task, allows for a more flexible and principled approach to handling uncertainties and complex relationships.
- Unified Energy Function: Combining sign mapping and word cognate matching into a single energy function is crucial. This allows the optimization process to find solutions that are good on both fronts simultaneously, rather than optimizing them in separate, potentially conflicting, steps.
- Flexible Sign Mappings: The use of k-permutations with parameters
NandMis a key innovation, enabling the model to handle real-world complexities like damaged inscriptions (wildcards) and partial knowledge of sign assignments, which are difficult for standard recurrent neural networks. - CSA's Robustness: The choice of CSA for optimization is significant. It provides a reliable way to explore the vast search space and consistently converges to good solutions, even without extensive hyperparameter tuning.
Key Results
The proposed system, CSA_OptMatcher, achieves state-of-the-art results across all benchmark datasets. Specifically:
- U/OH: Accuracy of 95.5 ± 0.83%.
- LB/MG: Accuracy of 89.4 ± 1.81%.
- LB/MG (names): Accuracy of 83.4 ± 2.50%.
- CS/AG: Accuracy of 86.3 ± 1.73%.
These results are presented as the mean and standard deviation over multiple runs, providing a more accurate picture of performance compared to single-score reporting. The authors note that these results are particularly impressive given that hyperparameters were not optimized.
Limitations and Future Work
- Hyperparameter Tuning: The authors acknowledge that hyperparameters
NandMwere not optimized and suggest that further improvements are likely possible by exploring different values. - Data Requirements: While the method is designed to work with limited data, it still benefits from segmented and clean corpora. Real-world decipherment often involves damaged inscriptions, making segmentation and sign identification challenging.
- Human Intervention: The authors agree with Sproat (2020) that these computational tools are best used to assist paleographers, shedding light on problems, rather than providing complete solutions without human expertise for interpretation and guidance.
- Future Plans: The authors intend to apply their proposed system to other undeciphered scripts from the Aegean area, hoping to contribute to solving long-standing linguistic and epigraphic puzzles. They also mention that codes and datasets are available on GitHub.
Summary updated