South Asia is home to a plethora of languages, many of which severely lack access to new language technologies. This linguistic diversity also results in a research environment conducive to the study of comparative, contact, and historical linguistics—fields which necessitate the gathering of extensive data from many languages. We claim that data scatteredness (rather than scarcity) is the primary obstacle in the development of South Asian language technology, and suggest that the study of language history is uniquely aligned with surmounting this obstacle. We review recent developments in and at the intersection of South Asian NLP and historical–comparative linguistics, describing our and others' current efforts in this area. We also offer new strategies towards breaking the data barrier.

§ INTRODUCTION

South Asia[Roughly the Indian Subcontinent, or the geographic and cultural region enclosed by the Himalayas, the Indian Ocean, and the Hindu Kush.] is home to one-quarter of the world's population and boasts immense linguistic diversity <cit.>. With members of at least four top-level major linguistic families[Indo-European (Indo-Aryan, Iranic, Nuristani), Dravidian, Austroasiatic (Munda, Khasian), Sino-Tibetan (several branches).] and several putative linguistic isolates, this region is a fascinating arena for linguistic research. The languages of South Asia, moreover, have a long recorded history, and have undergone complex change through genetic descent, sociolinguistic interactions, and contact influence.

Nevertheless, South Asian languages for the most part remain severely underdocumented <cit.>, and several languages with even official administrative status (e.g. Sindhi) are low-resource (if not data-scarce) for the purposes of all natural language processing tasks <cit.>. This data scatteredness persists despite long native traditions of linguistic description, continued language vitality with active use on the internet, and vast numbers of speakers <cit.>.

The major language families of South Asia <cit.>.

We argue that the most basic problem in NLP/CL work on South Asian languages is not data scarcity, but data scatteredness. There is much data to be extracted for even the most endangered languages (e.g., Burushaski, a language isolate of the northwest), from annotated corpora and grammatical descriptions compiled by linguists, if only one is willing to wrangle idiosyncratic data formats and digitise existing texts. Thus far, commercial interests and scientific agencies have only intermittently supported the development of language technology for the region—taking a new approach, we propose a research programme from the perspective of computational historical linguistics, outlining current data gathering initiatives in this discipline and potential benefits to other work across NLP.

§ BACKGROUND

Narrowing the low-resource category. Low-resource languages have recently gained attention in NLP/CL research, both due to the engineering problems of a data-scarce context and also in recognition of the historical focus on English in the field to the detriment of other languages <cit.>. This has been accompanied by debate on what languages the label encompasses (e.g. ).

In the South Asian context, even Hindi has been labelled low-resource in some recent work. While it is true that for certain tasks a large institutionally-backed language like Hindi can be low-resource, we propose that `low-resource' languages can be better described with two kinds of situations:

* Data scatteredness: Data is available (perhaps even abundant), but due to issues in digitisation, cataloguing, and labelling and annotation it has not been leveraged to its full potential.

* Data scarcity: Data is not available or very limited to begin with, and without collecting or creating new data we do not have enough to work with.

Level     Languages

4: Underdogs     Hindi

3: Rising Stars     Urdu, Bengali, Tamil

2: Hopefuls     Konkani, Marathi, Sanskrit, Punjabi

1: Scraping-Bys     Malayalam, Bhojpuri, Nepali, Doteli, Gujarati, Newar, Dzongkha, Maithili, Tulu, Kannada, Odia, Kashmiri, Romani, Pashto, Bishnupriya Manipuri, Divehi, Sindhi, Tibetan, Pali, Sinhala, Santali, Assamese, Telugu

0: Left-Behinds     (several hundred languages)

A brief overview of NLP/CL research progress on South Asian languages grouped by <cit.>'s categories.

The state of NLP in South Asia. So far, initiatives for improving language technology in South Asia have largely focused on data-scattered (not data-scarce) languages with official status and some degree of standardisation. These include cross-lingual projects such as IndicNLPSuite <cit.>, the EMILLE corpus <cit.>, and iNLTK <cit.>, and workshops like DravidianLangTech <cit.> and WILDRE <cit.>. As <ref> shows, only a select few languages benefit from NLP research—even fewer benefit from (commericialised) products like Google Translate or OCR tools. Truly data-scarce langauges (e.g. Kangri, Tulu) lack instituational status and have been largely unstudied because the challenges are different and harder to surmount.

NLP/CL has proven to be an expansive field as of late. Computational historical linguistics is inextricably linked with computational approaches to fundamental linguistic tasks: corpus building, POS tagging and dependency parsing, morphological analysers, and lexical databases. Work on these has progressed fast for the big languages. For example, Hindi, the highest-resourced South Asian language, has massive hand-annotated dependency treebanks <cit.>, state-of-the-art neural distributional semantic transformer models <cit.>, and machine translation models to and from English <cit.>.

This is not to say that there are no resources at all for the languages <cit.> terms “the Left-Behinds”. Linguists, for example, have compiled rudimentary treebanks for many languages, simply waiting to be digitised and converted to a multilingual format like Universal Dependencies; these include Palula <cit.> and Toda <cit.>, which are yet to be the subject of any NLP research work. There are also new treebanks in Universal Dependencies for Kangri, Mandeali, Bhojpuri <cit.>, and Magahi.

Historical/comparative linguistics. Historical linguistics is concerned with describing change of all kinds (phonological, morphological, syntactic, etc.) in language over time and the factors (social, cognitive, evolutionary) that contribute to that change. Comparative linguistics aims to use this historical study to relate languages and reconstruct earlier stages and common ancestors of related languages <cit.>.

The study of historical and comparative linguistics has a long history in South Asia, beginning well before similar threads of inquiry in the Western linguistic tradition, with grammarians like <cit.> and <cit.> analysing historical and dialectal language from a comparative perspective.

Following the recognition by Western philologists of an Indo-European language family that includes Sanskrit, comparative study of the languages of South Asia began in earnest. As a result, several comprehensive comparative grammars featuring the Dravidian <cit.> and Indo-Aryan families <cit.> have appeared in the years since. <cit.> was the first to posit a South Asian zone of language contact and convergence spanning multiple families. Subsequent work on micro-areal zones has yielded many insights into the nature of linguistic interactions in the region <cit.>.

The sole South Asia-wide linguistic data collection effort ever be undertaken was the Linguistic Survey of India, completed about a century ago <cit.>. To date, there has been no comparable centralised data resource on South Asian languages of its magnitude–covering typological features, the lexicon, and sociolinguistic phenomena.

Data in the earliest comparative works was frequently sourced from high-prestige standard varieties like Delhi Hindi, with progress on studying and collecting data from more localised lects largely proceeding in isolation. Compilation of comparative data continued sporadically throughout the 20th century, resulting in works such as the Comparative Dictionary of the Indo-Aryan Languages <cit.> and the Dravidian Etymology Dictionary <cit.> which attempt at a more diverse spectrum of language data. Meanwhile, progress on documentation and comparative analysis of the Austroasiatic <cit.>, Sino-Tibetan, and isolate languages (e.g. Burushaski, Nihali, Kusunda) of South Asia is still in its infancy. As a consequence, studies drawing upon their data for purposes such as substrate analysis often lack nuance and family-internal consistency.

§ ONGOING WORK

Having established the issue of data scatteredness, the mutual benefit inherent to data collection (for historical/comparative linguistic work and other NLP tasks), as well as possible interesting avenues for future research, we present a compilation of our ongoing projects in this direction, most involving languages that have not been studied in NLP before.

Universal Dependencies corpus sizes, in tokens, for all South Asian languages available thus far. Colors correspond to <cit.>'s level categorization.

§.§ Dependency treebanks

max width=

[column sep=0.2cm]
so & idani & yada & aya & dhrama  & dipi & likhita & tada & trayo & vo & praṇa & haṃñaṃti & majura & duvi & mrugo & so & pi & mrugo & no & dhruvaṃ

[edge unit distance=1.8ex]121cc
[edge unit distance=1.7ex]122advmod:tmod
[edge unit distance=2.6ex]73mark
[edge unit distance=3.7ex]117advcl
[edge unit distance=2.55ex]128advmod:tmod

A sample dependency-parse from the Ashokan Prakrit UD treebank (Shahbazgarhi dialect)

Structured, syntactically-parsed corpora are not only essential for (1) downstream NLP tasks such as information extraction <cit.> and semantic role labelling <cit.>, but also have the potential to (2) aid quantitative comparative and historical linguistic study. Parsing according to several formalisms is possible, though dependency formalisms in particular are better equipped to handle the flexible word-order characteristic of many South Asian languages (assuming the parsing algorithm used adequately handles non-projective dependency trees[
For vertex set $V$, weighted edge set $E \subseteq \{i \xrightarrow{w} j \ \vert \ i, j \in \mathbb{R}, w \in \mathbb{R} \}$, and root $\rho \in V$, let $G = (\rho, V, E)$ be a rooted weighted directed graph. A dependency tree is a spanning subgraph $D = (\rho, V, E'), \ E' \subseteq E$   subject to the following well-formedness constraints <cit.>:

(C1) Each non-root vertex of $D$ has one incoming edge

(C2) $D$ is acyclic

(C3) Root $\rho$ of $D$ has exactly one outgoing edge

In other words, dependency trees are arborescences (directed, rooted trees) equipped with the root constraint (C3). Graph-based parsing algorithms find the optimal dependency tree $D^{*}$, that is, the dependency tree $D$ with maximum total edge weight in the set of all possible dependency trees $D(G)$, for a given sentence  (maximum weight spanning arborescence). A treebank is a corpus of such dependency trees.
]) <cit.>.

Multilingual dependency formalisms such as Universal Dependencies (UD) <cit.> have established consistent guidelines for the annotation of binary dependency relations, morphology, and other linguistic features, resulting in the recent appearance of treebanks for several data-scarce languages of the region (Bhojpuri, Kangri, etc.) as well as their older diachronic stages (Vedic and Classical Sanskrit).

Towards the second goal listed above, <cit.> compiled a UD treebank for the Ashokan Prakrit dialect continuum–a parallel corpus of 14 pillar/rock inscriptions in six Middle Indo-Aryan (MIA) dialects dating back to the 3rd c. BCE. As the first study of MIA from a computational perspective, this work calls for an analysis of Indo-Aryan regional fragmentation through dialectometry, approaching contentious linguistic issues with statistical arguments curated using treebank data.

In a similar vein, we are currently working towards filling other chronological gaps in corpora (e.g. the Old Sinhala Sīgiri Graffiti of the Early New Indo-Aryan stage) through treebanking in parallel with their modern stages (e.g. Sinhala). To the best of our knowledge, we are unaware of any studies involving such diachronic transfer frameworks, where knowledge transfer between two historically-separated stages of the same language can be used to dependency-parse a given stage using resources from the other.  Other historically-attested langauges we plan to include in this pipeline include Old Kashmiri, Old Maldivian, and Old Tamil.

In terms of modern South Asian languages, there has been recent diversification from combined efforts, such as an upcoming dependency parsing shared task at the WILDRE 2022 workshop based on new treebanks <cit.>.

Multilingual dependency parsing. More broadly, we are interested in cross-lingual transfer models <cit.> as a means of expediting dependency parsing for data-scarce South-Asian languages. A similar approach for Uralic languages is <cit.>. They propose a dependency-parsing model for North Saami and Komi using annotated corpora and bilingual word-embeddings from high-resourced genetically related (Finnish) and typologically similar (Russian) languages, without the requirement of extensive parallel texts for training. They conclude that while genetically related pairs (Komi–Finnish, North Saami–Finnish) allow for highly efficient parsing, pairs of unrelated languages in contact (Komi–Russian) also provide valuable input for further correction. Given the languages of South Asia exhibit common typological features by virtue of sharing a linguistic area, treebanking efforts will undoubtedly beneft from a multilingual dependency parsing approach. Languages like Sindhi, Punjabi, and Sinhala, which have genetic relatives and contact languages that are comparatively more resourced, are our immediate targets for such efforts.

§.§ Jambu etymological database

A map of languages included in Jambu, colour-coded by subfamily designation with point-geometry variation by diachronic stage.

Top 50 languages by number of lemmas included in the Jambu database, colour-coded by language family (green = Indo-Aryan, red = Dravidian, blue = Nuristani).

One of our major efforts in data-collection for the region has been the Jambu project. Jambu is a compiled cognate lexicon of all South Asian languages, cutting across phylogenetic groupings and historical language stages. It has a web interface online at <https://neojambu.glitch.me/>. It includes data parsed and compiled from the University of Chicago's Digital Dictionaries of South Asia project <cit.>, existing web databases <cit.>, and individual articles and theses <cit.>, totalling 294 lects and 202,653 lemmas. Some of these sources have been used in previous work on South Asian historical linguistics, e.g. <cit.>—this is the first attempt to consolidate them. Note some previous work in this direction: while the SARVA project <cit.> did not reach fruition, a searchable database of Dravidian cognates was developed by Suresh Kolichala under its auspices.[<http://kolichala.com/DEDR/>]

Past etymological research in South Asian languages was primarily focused on internal comparisons within linguistic families. Unknown etyma was often blindly attributed to Dravidian or Munda without comprehensive cross-linguistic analyses.[Recent comparative work on Munda and Indo-Aryan contact such as <cit.> in general find very limited influence of Munda, restricted primarily to the (eastern) Indo-Aryan languages in close proximity with them. Prior work had a tendency to exaggerate the impact of Munda to explain unusual features of other Indo-Aryan languages; notably, <cit.>, who advocated for a historical `Para-Munda' family that influenced Indo-Aryan as far as in the northwest, the historical location of Rigvedic Sanskrit.] In fact, we find a large number of common words in languages of several families with uncertain origin, possibly substrate loans from undocumented languages.[
Dr. Felix Rau (p.c.) terms these unattested substrate(s) `the big X of South Asian linguistic history', and other (possible same) substrate(s) responsible for words reconstructable to Proto-Munda without secure cognates in other Austroasiatic branches `the big Y'.

In order to provide reliable data for the robust reconstruction of the history of the ancient linguistic contact, a comprehensive South Asia-wide linguistic data is desideratum.

Consolidating Indo-Aryan data. While <cit.> and its supplements remain the undisputed gold standard for Indo-Aryan comparative etymologies, many later works on individual languages have considerably expanded our knowledge of cognate relations in underdocumented languages; e.g. <cit.>. Inclusion of data from these newer works is ongoing. We also expanded coverage of the isolated and linguistically archaic Nuristani lects <cit.>, which are contended not to be Indo-Aryan—comparative lexical data will help cement their exact phylogenetic status.

Updates to Dravidian data. A Dravidian Etymological Dictionary published by <cit.> (2nd edition; abbreviated DEDR) remains the latest effort to gather etymological data on Dravidian. Although <cit.> provides reconstructions for about 500 entries, systematic historical reconstruction for all known cognates of Dravidian is still pending. <cit.> published an update to the DEDR utilizing new data on several non-literary languages that became available after 1984.

Recent fieldwork on several non-literary languages have produced grammars with new vocabulary lists, providing rich data to be updated in DEDR. In addition, several dictionaries with attempted etymologies for many literary languages have appeared since 1984, and can become a source for the realignment of cognates as well as new additions.

Cognate databases in NLP. The obvious benefit of cognate databases for upstream NLP tasks is for data-scarce languages that lack adequate corpora on the web. Similar work in this area is the pan-lingual CogNet <cit.>, and also earlier WordNets <cit.>. Cognate data can be used for transfer learning, where a data-scarce language can map onto existing models for higher-resource languages, such as a distributional semantic model which generally requires massive corpora to train <cit.>. Typological data in general offers modest improvements in performance on a variety of NLP tasks <cit.>.

Unified transcription. Since many languages of South Asia are unwritten or are lacking standardised orthographies (even in their respective linguistics works), we developed a preliminary system for phonemic transcription of all South Asian languages, which all our cognate data will be converted to.  For cognate identification and reconstruction work (both by humans and using NLP tools), a unified phonemic representation is important. This system combines features of the International Alphabet of Sanskrit Transliteration (IAST)[<https://en.wikipedia.org/wiki/International_Alphabet_of_Sanskrit_Transliteration>] with IPA and Americanist phonetic transcription systems. Future work will outline it in depth, along with examples of its focus on cross-family diacritical consistency.

§.§ Historical linguistic analyses

One of our main objectives for building extensive comparative lexical and grammatical databases is to ensure credible data from up-to-date, modern sources are available to researchers working on comparative and diachronic linguistics in the South Asian linguistic area. Historical linguistics work needs data, and in South Asia too much work has progressed without including data from non-standardised (even if documented) languages, to the detriment of our understanding of South Asian linguistic history post-Sanskrit <cit.>.

Below, we highlight two such projects we are currently engaged in involving three data-scarce languages of northern Pakistan: Burushaski, Gawri, and Torwali <cit.>.

§.§.§ Gawri tonogenesis and UniMorph

The languages of northern Pakistan have been synchronically analyzed to have phonemic tonal contrasts. <cit.> has classified such tonal languages into three broad groups based on the type of tonal contrast displayed:

* Shina-type: Shina varieties, Palula, Indus Kohistani (all Indo-Aryan), Burushaski (isolate) etc.

* Punjabi-type: Punjabi, Hindko, some Gujari varieties, extending into the Himachali languages of northern India, as well as Kishtwari[Not mentioned in <cit.>, but independently identified by one of the present authors.], which is usually classified as a divergent dialect of Kashmiri (all Indo-Aryan).

* Kalami-type: Gawri (Kalami), Kalkoti and Torwali (all Indo-Aryan) and possibly other undiscovered varieties of the area.

To these, one may also add the simpler accentual systems of Kalasha-mon <cit.> and Khowar <cit.>, which we term Chitrali-type.

The tonal system and the historical mechanism of tonogenesis is broadly understood for Punjabi proper and some Hindko varieties <cit.>, but specifics for individual varieties further east (Kishtwari and Himachali) remain underdescribed <cit.>. This system arises primarily from the disappearance of phonemic breathy voice, but the phonetic specifics differ from language to language. The Shina-type tonal system is both the best described and the best understood diachronically. It continues the Vedic (hence Indo-European) pitch-accent system subject to later changes necessitated by regular apocope <cit.>. Vedic pitch-accent is also partly continued by the Chitrali-type accentual system <cit.>,  though less conservatively.

The tonal diachrony of the Kalami-type system, on the other hand, has not yet been fully understood. Part of the reason is that this system is considerably more complex than the other three accentual systems, contrasting as many as five distinct tonemes <cit.>. In ongoing work, based on the Gawri data compiled from <cit.>, we are investigating the origin of the system, and will be appended in the future by Torwali data we are now collecting.

Morphology in NLP.

UniMorph paradigm counts for all South Asian languages available thus far. Colors correspond to <cit.>'s level categorization.

In addition to working out the history of the Kalami-type tonal system, we intend to incoporate our annotated lexical dataset into the UniMorph database <cit.>. The morphology of Gawri and Torwali marks gender, number and case for nouns and adjectives primarily by tonal changes and vowel alterations (historical umlaut) unlike other Indo-Aryan languages which use suffixation, though they still encode much the same categories and do not behave any different syntactically either. This makes them prime targets for testing out computational methods for morphological analysis, especially to compare performance vis-à-vis a related language like Hindi that has a similar grammar but different morphological profile.

UniMorph has only a few South Asian languages thus far, as shown in <ref>—this is part of a broader project to expand coverage in the region, using existing morphological data stored in analysers (e.g. for Sindhi, ) and grammars (e.g. for Palula, ). In this vein, we also mention that UniMorph has only a handful of languages that signal morphological alterations tonally. So, our contribution will also improve typological diversity in the database to a considerable extent.

§.§.§ Proto-Burushaski reconstruction

Our understanding of the linguistic pre-history of South Asia is heavily reliant on disciplined studies of the histories of the non-Indo-European languages of the subcontinent. This is primarily because while we do have reliable estimates on the time-frame of Indo-European migration into the subcontinent, for the families endemic to the region (including isolates) analogous dating is not possible.

Burushaski, spoken in a few mountain valleys of the Karakoram, is among these endemic languages of South Asia. It has attracted quite a bit of scholarly attention since its academic discovery as it stands out both typologically and genealogically in its current neighborhood (cf. the latest descriptive grammars <cit.>). The history of the language and its speakers is virtually unknown until the first linguistic documentation in the mid-nineteenth century. The first secure pre-modern attestation of Burushaski speakers is in Tibetan chronicles dating from the ninth century where a people bru-z̀a or bru-s̀a to the west of Tibet find mention <cit.>.[We are grateful to Dr. Diego Loukota (p.c.) for informing us that a short text in the bru-s̀a language is also attested in Tibetan records with translation in Sanskrit. We are, however, not aware of any scholarly attempt to interpret said text through modern Burushaski.][It is also possible that an older ethnonym recorded as Sanskrit mūja-, maujavata- and Avestan muža- refer to the same people but that is harder to establish.]

As of now, both major varieties of Burushaski are well-documented, but there has been precious little comparative work done. The dictionaries in <cit.> lay the  foundation of comparative studies by identifying several layers of potential loans in the language, cf. also <cit.>. Conversely, potential Burushaski interaction with and influence on the older stages of Indo-Iranian have been explored in <cit.>, the former mainly dealing with how Burushaski broadly fits into the South Asian linguistic zone. A handful of Burushaski loans in Purik Tibetan are identified in <cit.>, not all of them convincing, and <cit.> contains shared lexemes with Wakhi. More speculative are the claimed Burushaski loans in (Proto-)Romani collected in <cit.>, believed to be borrowed before the Roma migrated westward toward Europe (presumably) through Burushaski territory.

However, all these studies share a common drawback in that we do not yet have a principled way of identifying Burushaski lexemes or grammatical features. A first step toward this goal is <cit.>, where the author attempts an internal reconstruction of Burushaski through a comparative lexical and morphological study of the two main dialect groups of Yasin and Hunza–Nager. Holst's work, though, is still just a preliminary investigation and there is much to be added and improved on. In particular, the book does not undertake a systematic study of loanwords to and from neighboring languages as previous areal studies involving Burushaski have, nor does it exhaustively utilize the descriptive literature available resulting in a few avoidable but significant errors of interpretation <cit.>. This is a major shortcoming because external comparisons are a vital component to reconstructing the histories of language isolates and smaller families, cf. <cit.> for Basque and <cit.> for Yukaghir, among others.

Computational reconstruction. We have already started a principled reconstruction of Proto-Burushaski building on Holst's work, but utilizing more sources and laying a greater emphasis on loanword etymologizing and chronologizing. Our databases, compiled from available lexical and descriptive sources, are intended to aid this goal of comparative analysis, as well as to make data from Burushaski and neighboring languages available to other researchers.

Proto-language reconstruction is an interesting task in computational historical linguistics, and so far work has been under way in a supervised setting on known, high-quality cognate data across related languages, e.g. on Romance languages <cit.>.

Low-resource dependency corpora. In addition, starting with annotated texts from descriptive grammars, we plan to build a dependency treebank for Burushaski as described in <ref>. Burushaski is a low-resourced language in the sense that its domain of use is very restricted and there is no readily available internet corpus one can subject to sophisticated (computational) linguistic analyses automatically.

However, as mentioned before, there has been a steady stream of quality descriptive work on it and all published grammars come with a wealth of oral texts one can build a functional corpus with—indicating some data-scatteredness that can be leveraged.

§ FUTURE WORK

The data resources we are in the process of compiling for South Asian languages will enable a variety of research to be conducted into language history. We lay out some of the immediate potential pathways for this further research in hopes of stimulating work in this area.

§.§ Substrate studies and language history

A substrate language is one that loans words into a language of higher prestige. A perennial question in South Asian language history for at least a century has been the Indus Valley Civilisation inscriptionary corpus, and the problem of deciphering it (if it even encodes a language) and whether it belongs to a known language family of South Asia or something else entirely <cit.>. Notably, in the mid-20th century a team of Finnish and Soviet linguists and computer scientists claimed evidence that the Indus inscriptions represent a Dravidian language <cit.>.

Recent computational information-theoretic work also suggests language-like properties in the text, a subject of subsequent vociferous debate <cit.>. A serious issue is that we do not have sufficiently diverse data from modern languages of the region against which to compare any purported decipherments of the Indus script (e.g. Proto-Dravidian reconstruction is as of now still in a preliminary stage), and thus even if the Indus language provided any substrate loans into modern families, we would be unable to comprehensively list out possible candidates. The Jambu database can help inform research on substrate contact in the languages of the region.

§.§ Text digitisation and OCR

One of the major bottlenecks in compiling existing linguistic data on South Asian languages is that it remains machine-unreadable. For example, many linguistics theses completed at Indian universities have recently been digitised and uploaded to Shodhganga[<https://shodhganga.inflibnet.ac.in/>], but most are scanned images in PDF format. Optical character recognition (OCR) of such texts also requires difficult parsing of diacritics and low-resource scripts.

A recent initiative to digitise old linguistic data is the digitisation of the Linguistic Survey of India <cit.> under the project South Asia as a linguistic area? Exploring big-data methods in areal and genetic linguistics <cit.>. Using OCR and subsequent information extraction from the text,  have shown that “old” data still has much to tell for the computational study of typology and comparative linguistics.

Future work on extracting data from non-digitised South Asian language sources will have to use OCR, possibly a neural model finetuned for the purposes of our domain on a platform like Transkribus <cit.>.

§.§ Fieldwork initiatives

<cit.>, calling for the NLP community to make a consistent distinction between “endangered” and “low-resource” languages, implores researchers to `stop complaining about how low-resourced [a language] is, [and] get up and gather the data.'

In response to this call, we announce several currently-underway (online) fieldwork/data elicitation efforts for Indo-Aryan languages that are both endangered and data-scarce. These include Kholosi, Poguli, Kishtwari, Bhaderwahi, Torwali, and certain divergent dialects of Maldivian (e.g. Huvadhoo). By virtue of their geographical spread (Northern India/Pakistan, Iran, Maldives), linguistic data collected from these languages will further enable the consturction of typologically viable datasets for both NLP and computational historical linguistic tasks.

§ CONCLUSION

In this paper, we gave an overview of the state of NLP in South Asia with a special focus on historical–comparative linguistics, a research programme of which we believe will help address the issue of data scatteredness. South Asian languages are not obliged to remain low-resource (in the NLP sense), and have plenty of speakers who would like access to and would benefit from language technologies, along with a multitude of raw linguistic resources that can be used to cultivate them. Incentives have not been in place to support those demands, however, so we suggest an alternative route founded in linguistic research to gather data.

Collective efforts have had great success recently in NLP—besides institutional efforts like the Stanford Center for Research on Foundation Models <cit.> and HuggingFace's BigScience Workshop[<https://bigscience.huggingface.co/>], there are grassroots organisations like MaskhaneNLP for African languages <cit.> and AI4Bharat <cit.> that are working towards improving resource availability. Our proposals in this paper are the first seeds of a programme similar in spirit, motivated by a dual interest in understanding South Asian language history and remedying inequalities in technological availability.


# Eigenpruning

Tomás Vergara-Browne123, Álvaro Soto12, Akiko Aizawa3
1Pontificia Universidad Católica de Chile
2Centro Nacional de Inteligencia Artificial, Chile
3National Institute of Informatics, Japan

###### Abstract

We introduce eigenpruning, a method that removes singular values from weight
matrices in an LLM to improve its performance in a particular task. This
method is inspired by interpretability methods designed to automatically find
subnetworks of a model which solve a specific task. In our tests, the pruned
model outperforms the original model by a large margin, while only requiring
minimal computation to prune the weight matrices. In the case of a small
synthetic task in integer multiplication, the Phi-2 model can improve its
accuracy in the test set from 13.75% to 97.50%. Interestingly, these results
seem to indicate the existence of a computation path that can solve the task
very effectively, but it was not being used by the original model. Finally, we
publicly release our
implementation111https://github.com/tvergara/eigenpruning.

Eigenpruning

Tomás Vergara-Browne123, Álvaro Soto12, Akiko Aizawa3 1Pontificia Universidad
Católica de Chile 2Centro Nacional de Inteligencia Artificial, Chile 3National
Institute of Informatics, Japan

##  1 Introduction

Recently there has been a great interest in understanding, or reverse-
engineering circuits of LLMs Elhage et al. (2021); Nanda et al. (2023). Most
of these works have been manually detecting interpetable circuits in LLMs
Nanda et al. (2023); Wang et al. (2022); Hanna et al. (2024). But manually
reverse-engineering the LLMs of today is infeasable, due to their size, making
automatic approaches important for the future of the field Räuker et al.
(2023). There has been some early work on this topic Conmy et al. (2023); Syed
et al. (2023), which has had some success into finding interpretable circuits.

We are inspired by the "competing subnetworks" theory Merrill et al. (2023),
where model training is understood as a competition of multiple algorithms to
solve a task. These subnetworks may generalize very differently Bhaskar et al.
(2024), we theorize that there exist weaker subneworks, that could be pruned
to enhance performance.

By applying a variation of Attribution Patching Syed et al. (2023), an
automatic method to discover circuits, we remove singular values from some
matrices of an LLM to achieve better performance than the original model, both
in real NLP tasks and synthetic tasks. We call our method eigenpruning.

##  2 Related Work

To the best of our knowledge, there exists 2 automated circuit discovery
approaches. They view models as computational graphs, and circuits are defined
as subgraphs with distinct functionality, as in Wang et al. (2022). These
approaches are:

  * •

ACDC Conmy et al. (2023): Starting from the output node, ACDC iterates over
each node in the computational graph aiming to remove as many edges as
possible without affecting performance. Unfortunately, this approach does not
scale favourably with the number of nodes and edges in the graph, which makes
it infeasible for extremely large models.

  * •

Attribution patching Syed et al. (2023): In contrast to ACDC, Attribution
Patching performs a linear approximation of the effect of removing an edge of
the graph. This is much more efficient in terms of computation, as it requires
a constant number of forward and backward passes with respect to the size of
the computational graph.

Figure 1: High-level diagram of the eigenpruning method.

These previous approaches provide valueable insights:

  * •

Both approaches, despite being general to any definition of the computational
graph, use "big" nodes (attention heads and MLP layers) in their definitions.
We do no think that the computations in an LLM are well decomposed in such
components, as in Geva et al. (2022), where they found that decomposing feed
forward layers outputs into multiple vectors made them more interpretable.

  * •

In Attribution Patching, the authors straightforwardly remove edges from the
computational graph. We argue that such method to remove edges can produce
activations far away from the original model’s activation distribution.

  * •

Other work has shown that using attribution methods to prune attention heads
can improve the accuracy in certain tasks Hao et al. (2021).

Based on these insights, we propose eigenpruning, a compute-efficient method
to remove singular values from matrices in a model, which can considerably
improve the performance of the model in specific tasks.

##  3 Eigenpruning

A diagram of the method can be found in Figure 1. We first need to manually
choose a hyperparameter $M$, that is the subset of the weight matrices inside
a model that we are going to use (for example, all the key matrices from
transformer blocks Vaswani et al. (2017)).

For each matrix $A\in M$, we compute its singular value decomposition as:

$A=USV$

Where $S$ is a rectangular diagonal matrix containing the singular values of
$A$. Let $n$ be the number of singular values of $A$, from $USV$ we can
compute $n$ rank-one matrices $E_{i}$ corresponding to each singular value.

$A=E_{1}+E_{2}+...+E_{n}$

Very much inspired by Attribution Patching Syed et al. (2023), we use a linear
approximation to estimate how intervening the effect of $E_{i}$ would affect
the loss. Let $x$ and $x^{\prime}$ be two activations corresponding to two
separate examples in the training set, which will get multiplied by $A$, then
we define this approximation as:

$\Delta L_{i}^{x}=\frac{\delta L^{x}}{E_{i}x}E_{i}(x^{\prime}-x)$

Where $\frac{\delta L^{x}}{E_{i}x}$ is the gradient of the loss in example $x$
in the $E_{i}x$ value.

This is an approximation on the effect of replacing the activation $x$ with
$x^{\prime}$. Considering that we can draw many pairs $(x,x^{\prime})$ from
our training set, we take the maximum from these values as the final $\Delta
L_{i}$. Our intuition is that $E_{i}$ values which are part of weak
computation paths will result in negative values of $\Delta L_{i}$, which
indicate that the singular value is degrading the performance.

Model |  CB (%) |  COPA (%) |  RTE (%) |  INT-SUM (%) |  INT-MULT (%)
---|---|---|---|---|---
Phi-2 | 42.86$\rightarrow$51.79 | 78.00$\rightarrow$84.00 | 42.96$\rightarrow$44.04 | 1.45 $\rightarrow$ 46.10 | 13.75 $\rightarrow$ 97.50
GPT-2 | 10.71$\rightarrow$12.50 | 55.00$\rightarrow$55.00 | 00.36$\rightarrow$1.44 | 3.00 $\rightarrow$ 3.20 | 13.75 $\rightarrow$ 15.00
FT-GPT-2 | 41.07$\rightarrow$50.00 | 55.00$\rightarrow$ 55.00 | 47.29$\rightarrow$52.71 | 4.00 $\rightarrow$ 4.00 | 0.00 $\rightarrow$ 0.00
Table 1: Summary of accuracy improvements in the test set in different
benchmarks before and after the eigenpruning.

We now set the hyperparameter $p$, and freeze the lowest $p$ portion of
singular values. Freezing a singular value $E_{i}$ is fixing its effect, to
make it input-independent. More formally, if you let the $b$ be the bias
associated to the $A$, we then update the values as:

$A^{\prime}=A-E_{i}\textnormal{ \ \ \ and \ \ \ }b^{\prime}=b+E_{i}\bar{x}$

Where $\bar{x}$ is the average of $x$ activations that were multiplied by $A$
in the training set. This freezes the effect the singular values to just the
average of the $x$ activations. One important consideration is that the
activations $x$ have a token dimension, and we let $b^{\prime}$ inherit that
same dimension. This makes the new bias of the layer to be token-index-
dependent.

##  4 Experiments

We tested our approach in two synthetic datasets (integer addition and integer
multiplication), which details can be found in the appendix A, and also 3
tasks from the SuperGLUE benchmark Wang et al. (2019): CB De Marneffe et al.
(2019), COPA Roemmele et al. (2011) and RTE Wang et al. (2018). Details on the
prompting for these tasks can be found in the appendix B.

We used 2 open-source LLMs: GPT2-XL Radford et al. (2019), Phi-2 Javaheripi et
al. (2023). For GPT2-XL, we also finetune it to each task before applying our
method to check whether there is an effect of combining finetuning with
eigenpruning. Details can be found in Appendix C.

In our tests, using the set of matrices $M$ as all the key matrices
transformer blocks provided the best results, and we tested different values
of the portion of singular values to prune $p$ from the set of
$\\{0.01,0.05,0.10,0.30$}.

##  5 Results

Table 1 summarizes the improvement that eigenprunning models has in each of
the datasets used. We draw some insights from these results.

First, eigenpruning a model improves the accuracy in each task. This result is
much more noticeable in Phi-2 than in GPT-2. This improvement in performance
can be very significant, such as in INT-SUM and INT-MULT, although the results
should be taken with a grain of salt, as these datasets are small and very
well suited for the method (Appendix A).

More interestingly, eigenpruning does increase the accuracy in our NLP tasks.
For example, the 6% improvement of Phi-2 in COPA is promising in terms of the
practical application of the method.

Model | Dataset | Base | 0.01 | 0.05 | 0.10 | 0.30
---|---|---|---|---|---|---
| INT-SUM | 1.45 | 0.85 | 46.10 | 7.85 | 8.30
| INT-MULT | 13.75 | 13.75 | 97.50 | 65.00 | 73.75
Phi-2 | CB | 42.86 | 51.79 | 0.00 | 0.00 | 0.00
| COPA | 78.00 | 84.00 | 0.00 | 0.00 | 0.00
| RTE | 42.96 | 44.04 | 0.00 | 0.00 | 0.00
| INT-SUM | 3.00 | 2.95 | 3.20 | 3.00 | 2.45
| INT-MULT | 13.75 | 13.75 | 15.00 | 15.00 | 15.00
GPT-2 | CB | 10.71 | 10.71 | 10.71 | 12.50 | 0.00
| COPA | 55.00 | 45.00 | 54.00 | 55.00 | 46.00
| RTE | 0.36 | 0.36 | 0.36 | 1.44 | 0.00
| INT-SUM | 4.00 | 4.00 | 4.00 | 4.00 | 4.00
FT- | INT-MULT | 0.00 | 0.00 | 0.00 | 0.00 | 0.00
GPT-2 | CB | 41.07 | 41.07 | 50.00 | 41.07 | 41.07
| COPA | 55.00 | 55.00 | 55.00 | 45.00 | 55.00
| RTE | 47.29 | 52.71 | 52.71 | 52.71 | 52.71
Table 2: Accuracy in the test set in all tasks after eigenpruning. $p$ values
used are denoted at the top. Top results by model are in bold.

##  6 Discussion

These results are promising, both in terms of performance and of our
understanding of how LLMs work.

First, eigenpruning models has improved the accuracy of Phi-2 our synthetic
tasks, and also (in a lesser extent) in real NLP tasks. This indicates the
potential of eigenpruning as a method to increase the performance of LLMs.

Some of these results are very surprising at first sight. For example, it is
not intuitive that Phi-2 cannot properly perform integer multiplication in its
base form, but when pruned of particular singular values of the key matrices
in its transformer blocks, can achieve very impressive performance. This makes
us believe that the model has computation paths that are capable of solving
the task, but it is not properly using them.

##  7 Limitations

This is work in progress, and many limitations are present.

First, we have not tried sufficient models to be able to understand if the
potential of eigenpruning is truly generalizable to all LLMs. For example,
GPT-2 had much less of a benefit from eigenpruning than Phi-2. It might be the
case that eigenpruning just needs more capable models to be useful, but we do
not currently have the data to make that claim.

Second, the optimal $p$ value for each combination of task/model is currently
done as a brute force search over several candidate values, which is far from
being ideal.

Third, we have not enough data to understand the effect of finetuning with
eigenpruning. We only tested finetuning GPT-2, but we need to test more models
and finetune each one to actually understand its effects.

Fourth, our work needs comparison to other parameter efficient finetuning
methods, such as LoRA Hu et al. (2021), and potentially also with model
editing approaches, such as Mitchell et al. (2021).

Finally, the results on synthetic datasets should be taken with a grain of
salt, such as explained in appendix A.

##  8 Acknowledgements

We appreciate the reviewers’ feedback on this version of our work. We received
suggestions for related work that we were previously not aware about. We
believe these might be very influential in our future work in eigenpruning.

Also, we would like to thank LatinX for the opportunity to present our work.
They are doing amazing work into providing opportunities for Latinx
individuals along the world.

Finally, we would like to thank Aizawa-lab students for their feedback in
previous versions of our diagrams, and overall suggestions over the course of
this research.

## References

  * Bhaskar et al. (2024) Adithya Bhaskar, Dan Friedman, and Danqi Chen. 2024.  The heuristic core: Understanding subnetwork generalization in pretrained language models.  _arXiv preprint arXiv:2403.03942_.
  * Conmy et al. (2023) Arthur Conmy, Augustine Mavor-Parker, Aengus Lynch, Stefan Heimersheim, and Adrià Garriga-Alonso. 2023.  Towards automated circuit discovery for mechanistic interpretability.  _Advances in Neural Information Processing Systems_ , 36.
  * De Marneffe et al. (2019) Marie-Catherine De Marneffe, Mandy Simons, and Judith Tonhauser. 2019.  The commitmentbank: Investigating projection in naturally occurring discourse.  In _proceedings of Sinn und Bedeutung_ , volume 23, pages 107–124.
  * Elhage et al. (2021) Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, et al. 2021.  A mathematical framework for transformer circuits.  _Transformer Circuits Thread_ , 1:1.
  * Geva et al. (2022) Mor Geva, Avi Caciularu, Kevin Ro Wang, and Yoav Goldberg. 2022.  Transformer feed-forward layers build predictions by promoting concepts in the vocabulary space.  _arXiv preprint arXiv:2203.14680_.
  * Hanna et al. (2024) Michael Hanna, Ollie Liu, and Alexandre Variengien. 2024.  How does gpt-2 compute greater-than?: Interpreting mathematical abilities in a pre-trained language model.  _Advances in Neural Information Processing Systems_ , 36.
  * Hao et al. (2021) Yaru Hao, Li Dong, Furu Wei, and Ke Xu. 2021.  Self-attention attribution: Interpreting information interactions inside transformer.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 12963–12971.
  * Hu et al. (2021) Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. 2021.  Lora: Low-rank adaptation of large language models.  _arXiv preprint arXiv:2106.09685_.
  * Javaheripi et al. (2023) Mojan Javaheripi, Sébastien Bubeck, Marah Abdin, Jyoti Aneja, Sebastien Bubeck, Caio César Teodoro Mendes, Weizhu Chen, Allie Del Giorno, Ronen Eldan, Sivakanth Gopi, et al. 2023.  Phi-2: The surprising power of small language models.  _Microsoft Research Blog_.
  * Kingma and Ba (2017) Diederik P. Kingma and Jimmy Ba. 2017.  Adam: A method for stochastic optimization.
  * Merrill et al. (2023) William Merrill, Nikolaos Tsilivis, and Aman Shukla. 2023.  A tale of two circuits: Grokking as competition of sparse and dense subnetworks.  _arXiv preprint arXiv:2303.11873_.
  * Mitchell et al. (2021) Eric Mitchell, Charles Lin, Antoine Bosselut, Chelsea Finn, and Christopher D Manning. 2021.  Fast model editing at scale.  _arXiv preprint arXiv:2110.11309_.
  * Nanda et al. (2023) Neel Nanda, Lawrence Chan, Tom Lieberum, Jess Smith, and Jacob Steinhardt. 2023.  Progress measures for grokking via mechanistic interpretability.  _arXiv preprint arXiv:2301.05217_.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. 2019.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9.
  * Räuker et al. (2023) Tilman Räuker, Anson Ho, Stephen Casper, and Dylan Hadfield-Menell. 2023.  Toward transparent ai: A survey on interpreting the inner structures of deep neural networks.  In _2023 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML)_ , pages 464–483. IEEE.
  * Roemmele et al. (2011) Melissa Roemmele, Cosmin Adrian Bejan, and Andrew S Gordon. 2011.  Choice of plausible alternatives: An evaluation of commonsense causal reasoning.  In _2011 AAAI Spring Symposium Series_.
  * Syed et al. (2023) Aaquib Syed, Can Rager, and Arthur Conmy. 2023.  Attribution patching outperforms automated circuit discovery.  _arXiv preprint arXiv:2310.10348_.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _Advances in neural information processing systems_ , 30.
  * Wang et al. (2019) Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. 2019.  Superglue: A stickier benchmark for general-purpose language understanding systems.  _Advances in neural information processing systems_ , 32.
  * Wang et al. (2018) Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. 2018.  Glue: A multi-task benchmark and analysis platform for natural language understanding.  _arXiv preprint arXiv:1804.07461_.
  * Wang et al. (2022) Kevin Wang, Alexandre Variengien, Arthur Conmy, Buck Shlegeris, and Jacob Steinhardt. 2022.  Interpretability in the wild: a circuit for indirect object identification in gpt-2 small.  _arXiv preprint arXiv:2211.00593_.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. 2022.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in neural information processing systems_ , 35:24824–24837.

##  Appendix A Details on Synthetic Datasets

The integer addition was created by iterating for all the combinations of
adding two integers (such as "`2 + 2 =`") with integers from 0 to 99, and let
the model complete the last token. This results in 10k samples, which are
split into a train and test set in 80% and 20% respectively.

The integer multiplication was created very similarly, with the difference of
using 19 as the top value instead of 99. This results in 400 samples, which
are also then randomly split in train and test set in 80% and 20% proportion.
The reason behind this choice is that some integers above 400 may get split
into different tokens by the tokenizers of the model, which makes the
evaluation slightly harder to implement (but will be done in future work).

We know the size of the multiplication dataset is extremely small to actually
generalize the results, so that is an important limitation of our results in
this task.

Also, in both datasets, the distribution of tokens in these datasets are
"perfectly aligned", in the sense that for a particular index, it is
consistent whether that index token corresponds to the operation token, the
equal sign token, or an integer token. We believe this to be very important
into explaining the performance of our method in the tasks, due to the added
token dimension in the updated bias in each weight matrix, as explained in
Section 3.

##  Appendix B Details on NLP Datasets

These datasets are prompted with a manually designed prompt for each dataset,
and let the model predict the next token as the token with the highest logit.
This is not ideal, as the model can even generate tokens which are outside of
the space of acceptable answer tokens for the task. This implies that some of
our results are even worse than random, as the model can generate tokens that
are not even an acceptable response.

This limitation of generating only one token does not allow for techniques
that rely on generation of multiple tokens to get an answer, such as Wei et
al. (2022).

Also, these datasets have no publicly available labels for their test data, so
we have used the validation set as our test set.

##  Appendix C Finetuning Details

We do finetuning only in GPT2-XL due to time constraints to get this version
of the work, as doing for Phi-2 required us to re-implement the method much
more efficiently to fit the model in a single GPU. We use a batch size of 2
(due to memory constraints), learning rate of 0.01 using Adam Kingma and Ba
(2017), and we only train for a single epoch.


# Toward Digitalization: A Secure Approach to Find a Missing Person Using
Facial Recognition Technology

Abid Faisal Ayon  Department of Computer Science and Engineering
Bangladesh University of Business and Technology
Dhaka, Bangladesh
<EMAIL_ADDRESS>S M Maksudul Alam  Department of Computer Science
and Engineering
Bangladesh University of Business and Technology
Dhaka, Bangladesh
<EMAIL_ADDRESS>
###### Abstract

Facial Recognition is a technique, based on machine learning technology that
can recognize a human being analyzing his facial profile, and is applied in
solving various types of real-world problems nowadays. In this paper, a common
real-world problem – finding a missing person – has been solved in a secure
and effective way with the help of facial recognition technology. Although
there exist a few works on solving the problem, the proposed work is unique
with respect to its security, design, and feasibility. Impeding intruders in
participating in the processes and giving importance to both finders and
family members of a missing person are two of the major features of this work.
The proofs of the works of our system in finding a missing person have been
described in the result section of the paper. The advantages that our system
provides over the other existing systems can be realized from the comparisons,
described in the result summary section of the paper. The work is capable of
providing a worthy solution to find a missing person on the digital platform.

###### Index Terms:

Secure approach; Administrative process; Cross-Matching; Facial recognition;
Facial detection; Facial Mapping; Deep learning

††publicationid: pubid: 978-1-6654-4316-6/21/$31.00 ©2021 IEEE

##  I Introduction

Facial recognition[1] is an approach that uses different techniques such as
PCA, LBPH, Deep Learning[2], SVM, MVFD, etc. to find out the similarity of
human faces depending on different facial characteristics. As human beings are
different with respect to the characteristics of their facial constituents and
the overall structure, identifying a person analyzing his personal facial
characteristics can be performed effectively.
In the past few years, many interesting works have already been performed in
the field of facial recognition. For instance, Derya Ozkan and Pınar Duygulu
et al[3] presented a method for finding people out by investigating the
photographs and videos using a face recognition system. Debayan Deb, Divyansh
Aggarwal, Divyansh and Jain, Anil K et al.[4] proposed a system to find
missing children using aging deep face features. Natsume, Ryota, and Yatagawa,
Tatsuya and Morishima, Shigeo et al.[5] proposed a method of using latent
variables of facial landmarks instead of facial textures to perform image-
based face-swapping. Moreover, Raghuwanshi, Anshun and Swami, Preeti D et
al.[6] developed a system to maintain classroom attendance automatically using
video-based facial recognition. Nech, Aaron, and Kemelmacher-Shlizerman, Ira
et al.[7], in their work, trained, tested, and compared the results of
different facial recognition models with respect to the same large-scale
dataset.
People of various ages are getting lost because of their immaturity,
abnormality, or unintentional accidents. Depending on different conditions, a
missing person may not be able to express his destination rightly. The family
members of a missing person have to go through immense hardship in finding the
missing person. At the same time, a finder, after finding a missing person,
has to face a great hassle while helping a missing person to reach his family.
Moreover, Sometimes people with unscrupulous mentalities can try to take some
advantage using the information of a missing person. Thus, the hardships of
families of a missing person get intensified. Generally, people are habituated
to solve the problem manually following some conventional, naive approaches
such as recording missing diaries to the police station, advertising missing
news on public media, and so on. However, the rules and regulations that are
involved in the conventional approaches, in most cases, pose unbearable
hassles to the stakeholders of the problem. Other drawbacks of the
conventional approaches are their vulnerability and time consumption while
providing a standard solution to the problem. This is why solving the problem
– finding a missing person – technologically ensuring security and feasibility
is not only challenging but also very demanding in the modern age.
In our work, we have proposed a secure, nation-wise connected, centralized
system basing on facial recognition technology that can be helpful in dealing
efficiently and securely with the problem. The system serves a finder and a
family member of a missing person with equal importance and suitable services
breaking the restrictions such as places and times. The work focuses on the
security aspects regarding the system with high gravity. Security issues that
can be adversarial to either the stakeholders or the system have been
investigated and handled with appropriate concerns. The processes, performed
inside the system are impermeable to the intruders. Information along with the
photos uploaded in our system are verified thoroughly in multiple steps to
overcome the security issues. Again, the system maintains well-organized
databases that are helpful in preserving efficiency while dealing with data on
large scale. The system can notify the concerns within the shortest possible
time on the success of finding a missing person. The major contributions of
the work can be listed as follows:

  * •

Security to the processes of finding a missing person.

  * •

Flexibility to both sides of the stakeholders: family members and finder of a
missing person.

  * •

Notification to the concerns instantly while a missing person is identified

The remainder of the paper is organized in the segments as follows. In Section
II, some of the major related research works have been described briefly. Our
proposed system has been described in detail in Section III. In Section IV,
the results, and in Section V, the result-summary of our work have been shown.
Our future work has been described in Section VI. The concluding remarks can
be found in Section VII.

##  II Previous works

There have been a few research works bases on finding a missing person using
facial recognition technology. Some of the major works and their pitfalls can
be investigated as follows:
Xin Jin, Shiming Ge, Chenggen Song, Xiaodong Li, Jicheng Lei, Chuanqiang Wu,
and Haoyang Yu et al.[8] proposed a system, “Double-blinded finder: A two-side
privacy-preserving approach for finding missing children”. In their work, the
privacy of a missing child is ensured by using their cipher images instead of
their original ones in public clouds and maintaining public-private keys. The
public key-pair (pkF and pkI) is generated from the feature vector of a
missing child image. However, in the work, the information of the kin of a
missing person has not been verified and there exists a backdoor for an
intruder to pretend like kin of a missing person.
Bharath Darshan Balar, D S Kavya, Chandana M, Anush E, Vishwanath R Hulipalled
et al.[9] presented “Efficient Face Recognition System for Identifying Lost
People”. The system in their work saves a missing person’s photo along with
information uploaded either by police or the family of the person in the
database and notifies them when the photo gets matched with a photo uploaded
by a finder later. However, their system performs a missing person’s kin-side
matching partially and does not care about any verification or security issue.
Their system cannot handle Case 3 and Case 4, mentioned in the result section.
Case 2 has been handled partially in their system. Along with sharing a common
database for both of the found and missing people images, their work is unable
to deal with a crucial aspect – multiple entries for the same missing person.
Peace Muyambo et al.[10] worked on “An Investigation on the Use of LBPH
Algorithm for Face Recognition to Find Missing People in Zimbabwe”. In their
work, they used the Local Binary Patterns Histograms(LBPH) Algorithm to
perform facial recognition for finding missing people in Zimbabwe. The
accuracy of their work was proportional to the number of images, their system
was trained with. The work is not secure enough to be used heedlessly.

##  III Proposed System

In this paper, a secure, efficient, and pragmatic system has been proposed to
solve a problem – finding missing persons – with the help of modern
technology: facial recognition. Providing security to find a missing person
using an online platform is the very first motivation of our work. The system
maintains considerable security, efficiency, and flexibility while providing
services. Our proposed system can defeat the traditional and existing systems
of finding a missing person with its efficiency, completeness, security, and
feasibility. The advantages of our proposed system can be listed as follows:

  * •

People do not need to go through any complex official rules and regulations

  * •

There is no chance to be duped by intruders while using the system

  * •

Security of a missing person is ensured

  * •

The steps that need to be followed are more flexible and convenient to the
users.

  * •

The efficiency of the system is sustained while dealing with data on a large
scale

In the rest of the section, our proposed system will be described in detail
with the descriptions of each of the sub-systems, their workflows, and the
algorithms they follow.

###  III-A Interaction diagram of the proposed System:

The interactions of a finder and a family member of a missing person with our
system can be depicted by the interaction diagram in Fig. 1.

Figure 1: Interaction diagram of the system

From the interaction diagram, it can be seen that the two subsystems – the
missing person’s kin-side subsystem and the finder-side subsystem – are
maintaining two separate databases:“FoundPeople” and “LostPeople”,
respectively, and connected by the cross-matching. The user-uploaded
information and photos are verified thoroughly before proceeding toward
further approaches in the system. At first, the information, except the photo
uploaded by a user, is verified by an appropriate and authorized police
station keeping the user’s status as AP (Administrative Processing) so that an
intruder cannot get into the process. After getting approval from the police
station, the status of the user is updated and the uploaded photo is saved
after performing another verification step. Verification of the uploaded photo
is also important for the system’s security. It is not expected to create
multiple entries for a missing person at a time. Intruders can use a large
number of same and valid entries to commence system failure. While matching
the uploaded image from the missing person’s kin and the finder, the system
uses the images from “FoundPeople” and “LostPeople” databases respectively.
Here the cross-matching occurs. Depending on the result of matching, either
the information along with the photos are saved in the suitable database, or
the system shows and notifies the concerns.

###  III-B Proposed Algorithm

The well-defined tasks, performed in the proposed system are secure enough,
easy to follow and effective in producing the desired outcomes. The steps of
the algorithms can be summarized as follows:

Step 1:

Get input a recognizable photo of a missing person along with the required
information from the uploader

Step 2:

Verify the uploaded photo and the information in the system

Step 3:

Save the verified encoded image and uploaded information in the database

Step 4:

Match the recently encoded photo with the encoded unrecognized photos that are
saved in cross-directory of the system

Step 5:

Show the matching result to the uploader

Step 6:

Notify the appropriate person

Step 7:

Notify the police station

The steps of the algorithm are detailed in the following discussion:

####  III-B1 Get input a recognizable photo of a missing person along with the
required information from the uploader

A recognizable photo of a missing person and valid information i.e., national
identity (NID) of the user, contact number, email address, police station
information, location, etc. are uploaded to the system so that the system can
perform its match and notify functionalities. The status of the user’s process
is kept AP until the verification step is fully complete in the system.

####  III-B2 Verify the uploaded photo and the information in the system

At first, the authenticity of the user-given police station’s email address is
verified. If the police station email address is valid, then the information
is sent to the police station email for verification and recording a missing
diary. As NID, phone number, etc. are registered officially for all the
citizens of a country, police can easily verify the user’s information and the
missing case. If police approve the missing case and the information of the
user, the uploaded photo of the missing person is verified. The photo
verification is performed so that the entries in the system do not get
repeated. If any anomaly is detected while verification, the system does not
let the user proceed in the further steps.

####  III-B3 Save the verified encoded image and uploaded information in the
database

The encoded version of recently uploaded photo of the missing person and the
information of the user is stored in appropriate system-database for further
usage.

####  III-B4 Match the recently encoded photo with the encoded unrecognized
photos that are saved in cross-directory of the system

While identifying a missing person, cross-matching is performed in the system.
The system tries to find a match of the recently uploaded missing person’s
encoded photo with the collection of the unrecognized missing persons’ encoded
photos in the system. For the missing person’s family side, the matching is
performed against all the unrecognized encoded photos, uploaded by finders at
different times. For the finder side, the matching will be performed against
all the missing persons’ encoded photos in the database which were uploaded by
the missing persons’ families at different times.

####  III-B5 Show the matching result to the uploader

If the system gets any match between the recently uploaded photo and a
prerecorded photo in the system, it shows the information of the other side to
the user. For example, after getting a success on matching, the system shows
the information of the finders, if the user is a family-member of the missing
person and vice versa. Otherwise, it confirms users to be notified whenever
any match would be found in the future.

####  III-B6 Notify the appropriate person

The system notifies the family with the details of a finder of the missing
person whenever the finder records any entry to the system. Again, a finder
gets notified with the details of the family a missing person whenever the
family records an entry about the missing person to the system.

####  III-B7 Notify the police station

Whenever any finding happens, the applicable police station gets informed
about the finding result so that the necessary steps from the police side can
be performed immediately.

##  IV Results

To test the functionalities of our system, postman has been used as the front-
end with some demo data conveying requests to the system that is working on
the back-end.

The system’s functionality can be investigated for the following cases:

Case 1:

A missing entry of a missing person is recorded first, then a finder records a
finding entry of the person

Case 2:

Finding entry of a found person is recorded first, then family of the person
records a missing entry of the person

Case 3:

Already recorded missing entry is trying to be recorded multiple times

Case 4:

An intruder using false info. while using the system

The results of our system in the cases mentioned above can be described as
follows:

###  IV-A Case 1: A missing entry of a missing person is recorded first, then
a finder records a finding entry of the person

####  IV-A1 Recording a missing entry for missing person

In Fig 2, a missing person’s photo along with valid information has been
uploaded to the system first. After a successful verification, as there exists
no previously listed finding record for the missing person in the cross
directory of the system, the system will get no matching for the missing
person. So, the information uploaded along with the photo of the missing
person’s information is stored in a specific directory for the future usage
showing a message to the family member of the missing person as Fig. 2.

Figure 2: A missing entry

####  IV-A2 Recording a finding entry after finding the missing person

Whenever a finder finds the missing person mentioned in the previous step and
records a finding entry, after a proper verification, the system finds a
successful match of the finder-uploaded photo with the photo uploaded by the
family member in the previous step. Then the system shows the details of the
family member of the missing person as Fig 3 so that the finder can contact
him easily.

Figure 3: A finding entry

####  IV-A3 Notifying the concerns

In this case, the family of the missing person and the police station listed
while recording the missing entry are notified via email about the matching
success in the system. The email contains the details of the finder so that
they can reach the finder avoiding any formality and hassle. Sample emails –
sent to the family and the police station of the missing person’s family side
– from the system are shown in Fig 4.

(a) Email to missing person’s family

(b) Email to police station

Figure 4: Emails to the concerns

###  IV-B Case 2: Finding entry of a found person is recorded first, then
family of the person records a missing entry of the person

####  IV-B1 Recording a finding entry after finding the missing person

In Fig 5, it can be seen that a finder, after finding a missing person, has
recorded a finding entry with a verifiable photo of a missing person and the
valid details of the finder. After a proper verification, the system fails to
provide an instant solution to the finder regarding the missing person as the
family member of the missing person has not recorded any entry yet to the
cross directory of the system. That is why, the system saves the information
for further usage and shows a message to the finder as Fig 5.

Figure 5: A finding entry

####  IV-B2 Recording a missing entry for the missing person

Whenever the family of the person – mentioned in the previous step – records a
missing entry to the system, after a successful verification, the system finds
a match of the family-uploaded photo with the photo uploaded by the finder in
the previous step and shows the details of the finder so that the family can
contact him immediately. The scenario can be observed in Fig 6.

Figure 6: A missing entry

####  IV-B3 Notifying the concerns

In this case, the finder and the police station listed while recording the
finding entry will be notified via email about the detail of the missing
person so that they can reach the person’s family. The email contains the
details of the family-member of the missing person so that the finder can
reach the the family-member avoiding any formality and hassle. Sample emails –
sent to the finder and the police station of the finder’s side – from the
system are shown in Fig 7.

(a) Email to finder

(b) Email to police station

Figure 7: Emails to the concerns

###  IV-C Case 3: Already recorded missing entry is trying to be recorded
multiple times

If an already recorded missing entry is trying to be recorded again and again,
the databases inside the system might get populated by the redundant data
which might cause a system failure. The task can be treated as an adversarial
attempt to our system. Our system has the ability to avoid such adversarial
tasks.
Fig 8 shows that a person with a valid identity 111111 has tried to record an
entry that was recorded earlier. So after a proper verification, the system
could detect and deny the task showing the user a short message. By this time,
the system has also notified the family member and the police station – listed
while recording the first entry for the missing person – about the attempt of
recording the second entry for the missing person.

Figure 8: An attempt to record a prerecorded missing entry

###  IV-D Case 4: An intruder using false info. while using the system

In case of finding a missing person, intruders can participate as unverified
finders or family members of a missing person to take advantage of the
situation. So, in the beginning, the users and the provided information have
been verified thoroughly keeping the status of the procedure as AP for
security purposes.
A verification measure of our system can be observed in Fig 9. Here an
intruder is using a false NID 99999 and other information. After the
verification step, the system has found that the provided information is not
valid and rejected the request of recording a missing entry to our system.

Figure 9: An intruder trying to use the system with false information

##  V Result Summary

The main concern of the work was not on the facial recognition algorithm,
instead, was on the security, feasibility, and efficiency. The facial
recognition model of the work used a deep learning algorithm with an accuracy
of 99.38%[11] while performing the matching operation. The results of the work
can be summarized and compared with other related works as in Table I.

TABLE I: Summary of the result compared to closely related works

Benchmarks | Our work | Reference work[8] | Reference work[9]
---|---|---|---
Case 1 | Yes | Yes | Yes
Case 2 | Yes | No | Yes but Partially
Case 3 | Yes | Yes | No
Case 4 | Yes | No | No
Encryption | No | Yes | No
Cross directory checking | Yes | No | No
Technique used | Deep learning | FaceNet extension | SVM classifier

Along with the security aspects, other characteristics such as equal
importance to all of the stakeholders, feasibility, and efficiency ensure the
completeness of the system. A unique feature – maintaining and checking cross
directory– plays its role in sustaining efficiency while dealing with the data
on a large scale. The area of consideration of our work is larger than any of
the existing works. The services, provided by our system, are most effective
and pragmatic.

##  VI Future Works

In future, for security purposes of the system along with the missing persons,
immutable digital identities [12] of the users will be used in our system.
Moreover, The database will be switched from central to the distributed
platforms [13] to ensure the security and ubiquity of the systems.
Furthermore, hopefully, usage of real-time location would be integrated to the
system for extending the existing functionalities of the system. The changes
of a human’s facial profile with the passage of time will also be considered
in the next stages of our work.

##  VII Conclusion

The incidents of missing people are not rare cases nowadays. However, finding
a missing person or helping others to find their missing member following an
existing conventional way is somewhat complicated and vulnerable to intruders.
People involved in the issue have to go through overbearing stress both
physically and mentally. The system, proposed in this paper can provide a
solution to the problem with the help of modern technology. Organization and
the verification functionalities of the system play some crucial roles in
developing a secure platform ensuring its efficiency in rigorous ambiance.
From the results shown in the result section, it can be said that the system
performs its functionalities with considerable perfection. The future
extension of the work might grace the system with more stability, efficiency,
and security resolving the dependency on the assumptions. Application of the
system will provide an innovative and feasible solution to the problems
related to missing persons and help them get off the complexities of the
traditional solution of the problem.

## References

  * [1] K. Delac and M. Grgic, _Face recognition_ , 2007.
  * [2] S. Pouyanfar, S. Sadiq, Y. Yan, H. Tian, Y. Tao, M. P. Reyes, M.-L. Shyu, S.-C. Chen, and S. Iyengar, “A survey on deep learning: Algorithms, techniques, and applications,” _ACM Computing Surveys (CSUR)_ , vol. 51, no. 5, pp. 1–36, 2018.
  * [3] D. Özkan, “A graph based approach for finding people in news,” Ph.D. dissertation, bilkent university, 2007.
  * [4] D. Deb, D. Aggarwal, and A. K. Jain, “Finding missing children: Aging deep face features,” _arXiv preprint arXiv:1911.07538_ , 2019.
  * [5] R. Natsume, T. Yatagawa, and S. Morishima, “Fsnet: An identity-aware generative model for image-based face swapping,” in _Asian Conference on Computer Vision_. Springer, 2018, pp. 117–132.
  * [6] A. Raghuwanshi and P. D. Swami, “An automated classroom attendance system using video based face recognition,” in _2017 2nd IEEE International Conference on Recent Trends in Electronics, Information & Communication Technology (RTEICT)_. IEEE, 2017, pp. 719–724.
  * [7] A. Nech and I. Kemelmacher-Shlizerman, “Level playing field for million scale face recognition,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2017, pp. 7044–7053.
  * [8] X. Jin, S. Ge, C. Song, X. Li, J. Lei, C. Wu, and H. Yu, “Double-blinded finder: A two-side privacy-preserving approach for finding missing children,” in _3rd EAI International Conference on Robotic Sensor Networks_. Springer, 2020, pp. 33–43.
  * [9] C. M. Bharath Darshan Balar, D S Kavya, “Efficient face recognition system for identifying lost people,” _International Journal of Engineering and Advanced Technology (IJEAT)_ , 2019.
  * [10] P. Muyambo, “An investigation on the use of lbph algorithm for face recognition to find missing people in zimbabwe,” _International Journal of Engineering and Advanced Technology (IJEAT)_ , 2018.
  * [11] “face-recognition 1.3.0,” 2021, last accessed on June 2, 2021, at 11:24:00AM. [Online]. [Online]. Available: https://pypi.org/project/face-recognition/
  * [12] M. Mamun, S. Alam, M. Hossain, and M. Samiruzzaman, “A novel approach to blockchain-based digital identity system,” in _Advances in Intelligent Systems and Computing_ , vol. 1129. Springer, 2020, pp. 93–112.
  * [13] M. van Steen and A. Tanenbaum, “A brief introduction to distributed systems,” vol. 98, p. 967–1009, 2016.