Quantifying Character Similarity with Vision Transformers (2023)

Abstract: Record linkage is a bedrock of quantitative social science, as analyses often require linking data from multiple, noisy sources. Off-the-shelf string matching methods are widely used, as they are straightforward and cheap to implement and scale. Not all character substitutions are equally probable, and for some settings there are widely used handcrafted lists denoting which string substitutions are more likely, that improve the accuracy of string matching. However, such lists do not exist for many settings, skewing research with linked datasets towards a few high-resource contexts that are not representative of the diversity of human societies. This study develops an extensible way to measure character substitution costs for OCR’ed documents, by employing large-scale self-supervised training of vision transformers (ViT) with augmented digital fonts. For each language written with the CJK script, we contrastively learn a metric space where different augmentations of the same character are represented nearby. In this space, homoglyphic characters - those with similar appearance such as “O” and “0” - have similar vector representations. Using the cosine distance between characters’ representations as the substitution cost in an edit distance matching algorithm significantly improves record linkage compared to other widely used string matching methods, as OCR errors tend to be homoglyphic in nature. Homoglyphs can plausibly capture character visual similarity across any script, including low-resource settings. We illustrate this by creating homoglyph sets for 3,000 year old ancient Chinese characters, which are highly pictorial. Fascinatingly, a ViT is able to capture relationships in how different abstract concepts were conceptualized by ancient societies, that have been noted in the archaeological literature.

## introduction many quantitative analyses in the social sciencesas well as government and business applications -require linking information from multiple datasets. for example, researchers and governments link historical censuses, match hand-written records from vaccination campaigns to administrative data, and de-duplicate voter rolls. the sources to be linked often contain noise, particularly when they were created with optical character recognition (ocr). string matching methods are widely used to link entities across datasets, as they are straightforward to implement off-the-shelf and can be scaled to massive datasets @xcite . most simply, approximate string matching methods count the number of edits (insertions, deletions, and substitutions) to transform one string into another @xcite . another common approach computes the similarity between n-gram representations of strings, where n-grams are all substrings of length n @xcite . in practice, not all string substitutions are equally probable, and efforts to construct lists that vary their costs date back over a century. for example, in 1918 russell and odell patented soundex @xcite , a sound standardization toolkit that accounts for the fact that census enumerators often misspelled names according to their sound. together with the updated new york state identification and intelligence system @xcite , it remains a bedrock for linking u.s. historical censuses @xcite . similarly, novosad (2018) adjusts levenshtein distance to impose smaller penalties for common alternative spellings in hindi, and the fuzzychinese package (znwang25, 2020) uses strokes as the unit for n-grams substring representations, where the strokes for a given character are drawn from an external database @xcite covering a subset of the cjk script. characters sharing strokes are more likely to be matched. such methods can perform well in the contexts for which they are tailored but are labor-intensive to extend to new settings, due to the use of handcrafted features. low extensibility skews research with linked data -necessary to examine intergenerational mobility, the evolution of firm productivity, the persistence of poverty, and many other topicstowards a few higher resource settings that are not representative of the diversity of human societies. this study aims to preserve the advantages of string matching methods -simple off-the-shelf implementation and high scalability -while developing an extensible, self-supervised method for determining the relative costs of character substitutions in databases created with ocr. ocr often confuses characters with their homoglyphs, which have a similar visual appearance (e.g. "0" and "o"). incorporating character visual similarity into string matching can thus plausibly improve record linkage. homoglyphs can be constructed by hand for small script sets such as latin, as in a psychology literature on literacy acquisition @xcite . for a script such as cjk, containing over 38,000 characters, this is infeasible. following a literature on self-supervision through simple data augmentation for image encoders @xcite @xcite , this study uses augmented digital fonts to contrastively learn a metric space where different augmentations of a character (e.g., the character rendered with different fonts) have similar vector representations. the resulting space can be used, with a reference font, to measure the visual similarity of different characters. this purely self-supervised approach can be extended to any character set. due to space constraints, this study focuses on languages written with cjk: simplified and traditional chinese, japanese, and korean. we train the homoglyph model on augmentations of the same character -rather than paired data across characters -because a self-supervised approach is more extensible. paired character similarity data are limited. unicode maintains a set of confusables -constructed with rule-based methods -but for cjk the only confusables are structurally identical characters with different unicode codepoints. despite a large post-ocr error correction literature @xcite @xcite , there is also limited ground truth data about the types of errors that ocr makes across architectures, languages, scripts, layouts, and document contexts. using the cosine distance between two charac-ters as the substitution cost within a levenshtein edit distance framework @xcite significantly improves record linkage, relative to other string matching methods. we first examine linking real world data on supply chains, which are central to a variety of economic questions. we use three very different open-source ocr architectures to digitize supply chain and firm information from two 1950s japanese publications @xcite . we then use homoglyph to link them, significantly improving linkage over other string matching methods. this exercise illustrates that ocr errors tend to be homoglyphic regardless of the ocr architecture used. we provide evaluations for additional languages using synthetically generated data, as creating evaluation data is very costly. we augment image renders of place and firm names written with different fonts, for the simplified and traditional chinese, japanese, and korean character sets. we then ocr two different views of each entity with different ocr engines. the different augmentations and ocr engines lead with high frequency to different text string views of the same entity. we then link these using string matching methods. homoglyphic matching outperforms other widely used string matching techniques for all four languages. while end-to-end deep neural methods could plausibly outperform string matching, the data required for them are not always available and technical requirements for implementation are higher, explaining why string matching methods predominate in social science applications. homoglyphic matching is a cheap and extensible way to improve string matching. our python package homoglyphscjk ( https://pypi.org/project/ homoglyphscjk/ ) provides a simple, off-the-shelf implementation. homoglyphs can be extended to any script. to explore this, we contrastively train a homoglyph model for ancient chinese characters, using a database that provides views of the same character from different archaeological sites and time periods @xcite . ancient characters are much more pictorial than their more abstract, modern equivalents. fascinatingly, homoglyphs constructed with a vit for the shang dynasty (1600 bc-1045 bc) capture ways in which ancient chinese society related abstract concepts that have been noted in the archaeological literature (e.g. @xcite ). the rest of this study is organized as follows: section 2 develops methods for learning character similarity and incorporating it into string matching, and section 3 describes the evaluation datasets. section 4 compares the performance of homoglyphic edit distance to other string matching methods for record linkage, and section 5 introduces the homoglyphscjk package. section 6 examines extensibility by constructing homoglyphs for ancient chinese, and section 7 discusses the limitations of homoglyphs. ## evaluation datasets to our knowledge, there are no widely used benchmarks for evaluating record linkage for the cjk script, and thus we develop datasets for evaluation. task query target hist. jap. companies across (historicja-across) 238 68,352 hist. jap. companies within (historicja-within) 1,092 6,725 synthetic japanese (synth-ja) 86,470 86,470 synthetic korean (synth-ko) 48,809 48,809 synthetic trad. chinese (synth-zht) 66,943 66,943 synthetic simp. chinese (synth-zhs) 20,162 20,162 firm names are ocr'ed twice, to shed light on whether errors tend to be homoglyphic for both vision-only and vision-language sequenceto-sequence ocr architectures. we employ two widely used, open-source engines: easyocr and paddleocr. easyocr uses a convolutional recurrent neural network (crnn) @xcite , with learned embeddings from a vision model serving as inputs to a learned language model. paddleocr abandons language modeling, dividing text images into small patches, using mixing blocks to perceive inter-and intra-character patterns, and recognizing text by linear prediction @xcite . neither engine localizes individual characters. in a second exercise, we use a hand-curated dataset that links 238 firms to a much larger firm directory containing over 70,000 firms (teikoku @xcite . this latter source is written vertically, which paddleocr and easyocr do not support. instead, we digitize them with efficien-tocr @xcite , custom-trained on both target publications. we would expect efficien-tocr's character retrieval framework to make homoglyphic errors. the large firm directory contains some firms with duplicate names; these are removed for the purposes of this analysis, as space constraints do not permit a discussion of varied blocking methods @xcite . because creating ground truth data for record linkage is costly, we use synthetically generated data for a third set of evaluations. for simpli-fied chinese (synth-zhs), japanese (synth-ja), and korean (synth-ko), we draw placenames from the geonames database @xcite . because traditional chinese placenames in geonames are rare, we instead draw from a list of taiwanese firms (taiwan ministry of economic affairs, 2023), as taiwan still uses traditional chinese (forming the dataset synth-zht). we augment the images of each entity name, randomly select two image crops for each entity, and ocr them using easyocr and paddleocr. anywhere from 40% (simplified chinese) to 88% (traditional chinese) of ocr'ed string pairs differ between the two ocr engines, and we use homoglyphic edit distance to match these strings. foot_2 ## results homoglyphic edit distance outperforms the other string matching methods in all three evaluation exercises -across different ocr engines and languages -typically by an appreciable margin. this illustrates that homoglyphic errors in ocr are common and can be captured with self-supervised vision transformers. we show that homoglyphs are useful for realworld research tasks, starting with supply chains. supply chain are widely studied, as they are fundamental to the transmission of economic shocks @xcite , agglomeration @xcite , and economic development @xcite @xcite @xcite . yet their role in long-run economic development has been difficult to study due to the challenges of accurately linking large-scale historical records our first evaluation exercise, with linked japanese supply chain data (historic-ja-within)aims to elucidate whether homoglyphic matching is as helpful for linking datasets created with visionlanguage ocr (easyocr) as for linking datasets created with vision-only ocr (paddleocr), and whether it can similarly be useful for linking datasets created with different ocr architectures. we hence separately consider results linking pad-dleocr'ed customers and suppliers to the easy-ocr'ed firm index, and vice-versa, as well as linking when both are ocr'ed by either paddleocr or easyocr. homoglyphic edit distance outperforms other string matching methods and does so by a similar margin (around 4 percentage points higher accuracy) regardless of the ocr architecture used. fuzzychinese has the weakest performance, as expected since many japanese characters are not covered in their stroke dictionary. our second evaluation, historic-ja-across examines matching to a different, vertically written book, with around ten times more firms, digitized with efficientocr because it supports vertical japanese. homoglyphic distance outperforms all other string matching methods, with a matching accuracy of 82%. this matching exercise is also examined in @xcite , using a customized, end-toend multimodal deep neural model to link firms across the books. this achieves an accuracy of 87.8 with vision-only contrastive training and a peak accuracy of 94.5 using a language-image model (clip) backbone with multimodal pooling. the end-to-end deep neural methods outperform string matching, as would be expected, as they are leveraging more information (the image crops as well as the texts) and language understanding. yet string matching methods remain prevalent in the literature, due to their straightforward off-the- finally, ## the homoglyphscjk package we distribute the homoglyphic matching approach for cjk languages as a python package 3 which has an api designed around the standard merge operation in pandas -effectively reducing the entry 3 https://pypi.org/project/homoglyphscjk/ barrier to using it not only for python users but also those experienced in using r or stata for data analysis. all the user needs are the two datasets to match (with the key to match on) and one line of code. the package comes pre-loaded with the lookup tables that contain pairwise distances between different characters for a script. the files are also available on huggingface foot_5 . we provide two main functions in the package -one to calculate the homoglyphic distance (hg_distance) between a pair of strings and the other for matching two data frames (hg_merge). here is example usage. above, we use the default of setting these all to 1.) the package repo contains more documentation and a colab notebook to allow quick exploration of the package's functionality. 5 for users who are interested in computing their own character visual similarity indices, we provide our training code in a separate repo. 6 6 extending homoglyphs while this study focuses on the modern cjk script, homoglyph can be extended to any character set. as a proof of concept, we explore its extensibility to ancient chinese characters. like other early forms of human writing, ancient chinese scripts are highly pictorial relative to modern characters. since we do not have multiple fonts for ancient chinese characters, we instead use an existing database of grouped ancient characters -from different archaeological sites and periods -that correspond to the same concept @xcite . these ancient characters are also linked to their descendant modern (traditional) chinese character, identified by the database. we contrastively learn a metric space where the representations of ancient characters denoting the same concept are nearby. we train on 25,984 ancient characters, as well as the corresponding augmented traditional chinese characters. the dataset includes characters from the shang dynasty (1600 bc-1045 bc), the western zhou (1045 bc-771 bc), the spring and autumn warring states era (770 bbc -221 bc), and the qin-han dynasties (221bc -circa third century). 7 to illustrate homoglyphs, we create a reference set for the shang dynasty, randomly choosing one character for each concept. figure 5 shows representative examples of these homoglyphs, consisting of a character and its five nearest neighbors. the modern character descendant as well as a short description of the ancient concept (which may differ significantly in meaning from the modern descendent) are provided. the description draws upon @xcite . fascinatingly, the homoglyph sets are able to capture related abstract concepts noted in the archaeological literature. the first line shows that the concepts of writing, law, learning, and morning ("recording the sun") are homoglyphs, and the second line shows that characters for different types of officials are homoglyphs, as are characters denoting "joining." the final line shows that history and government official are homoglyphs -underscoring the central role of the government in writing history -as are characters denoting conquest, tying up, and city center (denoted by a prisoner to be executed by the government, which occurred in the city center). not all concepts within each set are related, but many of the connections above have been noted in an archaeological literature examining how ancient peoples conceptualized the world (e.g. @xcite ). that these meanings can be captured using vision transformers is a fascinating illustration of the relationship between images, written language, and meaning in ancient societies. another test of extensibility is to compute homoglyphs for all (ancient and modern) characters in unicode, clustering the embeddings to create homoglyphic sets (termed "confusables" (consortium, 2023) by unicode). training a homoglyphic space for all of unicode generally gives sensible results and also has the advantage of being able to measure similarity within a set, something standard unicode confusables cannot do. an example set, spanning different scripts, is displayed in figure 6 . ## limitations using homoglyphs for string matching inherits the well-known limitations of string matching. in some cases, ocr destroys too much information for record linkage to be feasible with the resulting strings. even with clean ocr, sometimes language understanding is necessary to determine the correct match, as in the case of firm names that can be written differently. homoglyphs do not address other types of string substitutions, like those that result from enumerator misspellings, although in principle a similar contrastive approach could also be developed to quantify other types of string substitutions. more sophisticated methods have been developed as alternatives to string matching. for example, ventura et al. (2015) use a random forest classifier trained on labeled data to disambiguate authors of u.s. patents, applying clustering to the resulting dissimilarity scores to enforce transitivity. @xcite develop multimodal record linkage methods that combine the image crops of entities and their ocr. they also develop a vision-only linkage method, which avoids the ocr information bottleneck. bayesian methods have also been used, e.g. @xcite . they offer the advantage of uncertainty quantification -another well-known limitation of string matching -but do not scale well. while these methods offer various advantages, they are not always applicable. researchers may lack access to the original document images, or may lack the compute or technical resources to process images, limiting the use of ocr-free or multimodal approaches. language models are less likely to be useful in linking individual or place names, common applications. moreover, general purpose, off-the-shelf, end-toend deep neural methods for record linkage do not exist, e.g. the model in @xcite is tuned to a specific japanese use case. to the extent that labels are required to develop specialized models, the data can be costly to create at a sufficient scale for training end-to-end models. finally, most social science researchers lack familiarity with deep learning methods but are comfortable processing strings. for these reasons, off-the-shelf string matching algorithms are often preferred by practitioners and can be the most suitable tool given the constraints. homoglyphic edit distance integrates information about character similarity from purely self-supervised vision transformers. it can be implemented using our publicly available, simple, offthe-shelf string matching package and is highly extensible, as illustrated by our exercise with characters from ancient chinese societies. we hope that highly extensible string-matching methods will make the contexts that are feasible for quantitative social scientists to study more representative of the diversity of human societies.