#  Mergen: The First Manchu-Korean Machine Translation Model
Trained on Augmented Data

Jean Seo, Sungjoo Byun, Minha Kang, Sangah Lee
Seoul National University
{seemdog, byunsj, alsgk1123<EMAIL_ADDRESS>
###### Abstract

The Manchu language, with its roots in the historical Manchurian region of
Northeast China, is now facing a critical threat of extinction, as there are
very few speakers left. In our efforts to safeguard the Manchu language, we
introduce Mergen, the first-ever attempt at a Manchu-Korean Machine
Translation (MT) model. To develop this model, we utilize valuable resources
such as the Mǎnwén Lǎodàng(a historical book) and a Manchu-Korean dictionary.
Due to the scarcity of a Manchu-Korean parallel dataset, we expand our data by
employing word replacement guided by GloVe embeddings, trained on both
monolingual and parallel texts. Our approach is built around an encoder-
decoder neural machine translation model, incorporating a bi-directional Gated
Recurrent Unit (GRU) layer. The experiments have yielded promising results,
showcasing a significant enhancement in Manchu-Korean translation, with a
remarkable 20-30 point increase in the BLEU score.

##  1 Introduction

Efforts to conserve and revive endangered languages have surged, with modern
advancements in Natural Language Processing (NLP) playing a pivotal role.
Zhang et al. (2020) introduce ChrEn, a Cherokee-English parallel dataset, and
examine methodologies like Statistical Machine Translation (SMT) and Neural
Machine Translation (NMT). Zhang et al. (2020) aid the conservation of
Cherokee, a critically endangered Native American dialect. On a similar note,
Luo et al. (2020) present a decipherment model for lost languages that
addresses challenges posed by non-segmented scripts and undetermined proximate
languages, leveraging linguistic constraints and the International Phonetic
Alphabet (IPA) for phonological patterns.

Manchu language, originated from the historical Manchurian region in Northeast
China, stands as a highly endangered Tungusic language of East Asia (Tsunoda,
2006). There are merely few Manchu speakers left nowadays, leading Manchu to
be labeled ‘nearly extinct’ by UNESCO (Kim et al., 2008). The Manchu spell
checker (You, 2014) and the Manchu corpus with morphological annotations (Choi
et al., 2023a, b) are the only prior approaches to embrace Manchu in the field
of NLP. We introduce Mergen, the first Manchu-Korean machine translation
model, which marks the pioneering effort to apply MT to the Manchu language.

We employ two sets of parallel corpora for machine translation from Manchu to
Korean, as detailed in Kim et al. (2019). Initially, we train an adapted
version of the NMT model (Bahdanau et al., 2016). Assuming the unexpectedly
low performance is due to the scarcity of Manchu-Korean data, we augment the
size of parallel data several fold utilizing GloVe (Pennington et al., 2014).
Our findings suggest that this data augmentation methodology substantially
enhances translation quality.

Despite the constrained availability of resources, our goal is to enhance
Manchu-Korean machine translation performance. To symbolize our commitment to
the field of Manchu NLP, we christen our model Mergen, denoting a sage or a
wise individual in the Manchu lexicon. Our translation approach, which employs
a data augmentation technique, not only seeks to improve Manchu-Korean
translation performance but also aims to eventually serve as a potential model
for addressing NLP challenges in other extremely low-resource scenarios as
addressed in King (2015).

##  2 Related Work

###  2.1 Low-Resource Machine Translation

MT necessitates parallel data of source and target languages to be trained
effectively. However, the majority of language pairs face a scarcity of
resources. As a result, there has been various research endeavors aimed at
developing translation models in low-resource scenarios. Extended language
models such as XLM-RoBERTa (Conneau et al., 2019), mBART (Tang et al., 2021),
multilingual BERT (mBERT) (Pires et al., 2019), and mT5 (Xue et al., 2021) are
trained on diverse languages. Yet, most of these multilingual language models
tend not to incorporate endangered languages. This leads to an increasing
disparity in NLP resources, where less-resourced languages are further
marginalized. Numerous strategies have been attempted in low-resource machine
translation. Gibadullin et al. (2019) and Siddhant et al. (2020) employ
monolingual data in low-resource NMT. Additionally, utilization of pre-trained
word embeddings (Qi et al., 2018) and application of transfer learning with
pretrained language models like XLM (Lample and Conneau, 2019) and mBART (Liu
et al., 2020) have been employed. Furthermore, Lakew et al. (2018) enhance the
zero-shot translation capability of low-resource languages.

Figure 1: Our data augmentation methodology. First, we train ten versions of
GloVe embedding models, varying in the minimum token length of source data and
window size. Then, the presumable synonym for the target word is selected via
comparing the frequency of outputs from each model. Finally, we augment data
through replacing original words with synonyms if possible. The pair of
original and substituted words are in the same color.

###  2.2 Typological Similarities between Manchu and Korean

There are several typological motivations for translating Manchu to Korean
using a Machine Translation model. The genetic affinity between Manchu and
Korean is not proven, but it is well-known that Manchu has a similar structure
to that of Korean. The word order of Manchu and Korean mostly coincide,
including the order of ‘noun-particle,’ ‘modifier-modified,’ and ‘object-
verb,’ etc. (Park, 2018). Substitutes in Korean, kes, and Manchu, -ngge, have
analogous grammatical functions and positions (Choi, 2009). The two languages
both show factivity alternation by using the attitude verb ‘to know’ (Lee,
2019) and have parallel subordinated clause structures (Malchukov and
Czerwinski, 2020). These typological similarities between Manchu and Korean
arouse interest in understanding and linguistically translating each other. In
fact, studies of the Manchu language are active in Korea (Ko, 2023).

Monolingual data | Number of sentences
---|---
Mǎnwén Lǎodàng–Taizong | 2,220
Ilan gurun i bithe | 41,904
Gin ping mei bithe | 21,376
Yùzhì Qīngwénjiàn | 11,954
Yùzhì Zēngdìng Qīngwénjiàn | 18,420
Parallel data (Man-Kor) |
Mǎnwén Lǎodàng–Taizu | 22,578
Manchu-Korean Dictionary | 40,583
|

Table 1: The size of each material

##  3 Data

###  3.1 Materials

The Manchu corpora used in this study comprise all of the digitized textual
data available and can be categorized as either parallel or monolingual. The
parallel corpora are Mǎnwén Lǎodàng (1774-1778) and the Manchu-Korean
dictionary. These corpora consist of Manchu texts and their corresponding
translations in Korean. We only utilize a section of the Mǎnwén Lǎodàng and
its translations from Kim et al. (2019), which details the history of Nurhaci,
the Emperor Taizu of Qing dynasty. Additionally, we refer to the dictionary
from Lee (2017) and select sentences with a minimum of three words.

The monolingual texts of Manchu include the remaining part of Mǎnwén Lǎodàng,
Manchu-Manchu dictionaries, and several pieces of literature. The part of
Mǎnwén Lǎodàng left over is the chronicle of Hong Taiji, the Emperor Taizong
of Qing. The Manchu-Manchu dictionaries we use are Yùzhì Qīngwénjiàn (1708)
and Yùzhì Zēngdìng Qīngwénjiàn (c.1771).

The other data is composed of novels, Ilan gurun i bithe (c.1723-1735) and Gin
ping mei bithe (1708). Ilan gurun i bithe is the translated version of The
Romance of the Three Kingdoms. Gin ping mei bithe is translated from the
Chinese naturalistic novel, The Plum in the Golden Vase. The size description
of each data can be found in Table 1.

###  3.2 Romanization of Manchu script and Hangul

To create a more sufficient translation model, the script of each language
should be unified in one writing system. That is, both the source and target
language should undergo transliteration to the Latin alphabet, so-called
‘romanization’. For the romanization of Manchu, we apply Abkai Latin
transliteration. The Abkai romanization suggested by An (1993) is a Pinyin-
based writing system. We also use the system of Seong (1977) for the special
characters in the Manchu script. Transliteration of Manchu to the Latin
alphabet is reversible except for a couple of letters. For the Latin
transliteration of Korean, we employ Yale romanization system (Martin, 1992)
and develop the corresponding Python library111anonymous author github. See
Appendix A for examples.

###  3.3 Data Augmentation

The lack of available Manchu linguistic data poses challenges not only for the
pre-training of transformer-based models but also for the training of simpler
and more lightweight models, such as encoder-decoder models. Inspired by
TinyBERT (Jiao et al., 2020), we adopt a novel data augmentation approach.
While the data augmentation method in TinyBERT (Jiao et al., 2020) combines
both BERT (Devlin et al., 2019) and GloVe (Pennington et al., 2014), we
exclusively employ GloVe embeddings. This decision stems from the absence of a
pre-trained BERT model tailored to Manchu and the significant difficulty of
pre-training a BERT model from scratch due to the limited amount of available
textual data.

Our methodology involves training GloVe embedding models with two different
versions of the dataset: (1) a dataset comprising sentences with at least 3
words, and (2) a dataset comprising sentences with at least 5 words. The
dataset includes both monolingual and parallel text data. Various window
sizes, specifically 1, 3, 5, 7, and 10, are used during the training process,
resulting in a total of 10 distinct variations of GloVe embeddings.

For each word in the training dataset, we gather the most similar word
predicted by each individual GloVe embedding. Amongst the list of 10 words
generated from these separate models, the word with the highest frequency is
considered the most suitable synonym for the target word. Following this, we
substitute a single word in each sentence from parallel text data with the
identified synonym. The augmentation steps are described in Figure 1. This
procedure leads to the creation of two augmented versions of the original
dataset: full augmentation and half augmentation. The first version involves
replacing every word possible in each sentence with its corresponding synonym,
significantly expanding the dataset size relative to the average sentence
length. The second version is generated by replacing half of the words in each
sentence with their respective synonyms, resulting in a dataset expansion
about half the size of the first method. Additional details regarding the
original and augmented dataset are available in Table 2.

augmentation |  Mǎnwén Lǎodàng
–Taizu (train) | Man-Kor Dict
---|---|---
Before augmentation |  20,320 | 40,583
Full augmentation |  179,843 | 154,404
Half augmentation |  99,506 | 100,694
|  |

Table 2: The number of sentences of parallel text data before and after
augmentation

##  4 Experiments

###  4.1 Task Details

In the experiment, we merge Mǎnwén Lǎodàng with Manchu-Korean dictionary and
shuffle them together. The combined dataset is then divided into training,
validation, and testing subsets. These subsets are split in an 8:1:1 ratio. In
the augmentation process, we first shuffle and then augment the data to even
out the word distributions, finally splitting into subsets.

###  4.2 Model

We adopt the sequence-to-sequence (seq2seq) framework, a deep learning
approach designed to transform one sequence into another. Our model is based
on the encoder-decoder structure of the NMT (Bahdanau et al., 2016),
implemented with bi-directional Gated Recurrent Unit (GRU) layer (Cho et al.,
2014). We incorporate two techniques to enhance the performance: packed padded
sequences and masking. Packed padded sequences ensure that the RNN processes
only the genuine elements of the input sentence, excluding the padded ones.
Masking directs the model to deliberately overlook specific components, like
attention weights assigned to padded sections.

###  4.3 Results and Discussions

Train | Test | BLEU | PPL
---|---|---|---
Before augmentation (No augmentation)
Mǎnwén Lǎodàng | Mǎnwén Lǎodàng | 0.0 | 72.50
Man-Kor Dict | Man-Kor Dict | 0.0 | 59.34
Combined | Mǎnwén Lǎodàng | 0.0 | 61.83
Man-Kor Dict | 0.0 | 61.16
Combined | 0.0 | 69.62
Half augmentation
Mǎnwén Lǎodàng | Mǎnwén Lǎodàng | 38.38 | 147.07
Man-Kor Dict | Man-Kor Dict | 0.0 | 174.94
Combined | Mǎnwén Lǎodàng | 36.05 | 192.95
Man-Kor Dict | 2.37 | 36.14
Combined | 27.59 | 29.22
Full augmentation
Mǎnwén Lǎodàng | Mǎnwén Lǎodàng | 38.95 | 1549.40
Man-Kor Dict | Man-Kor Dict | 0.0 | 158.25
Combined | Mǎnwén Lǎodàng | 37.17 | 447.59
Man-Kor Dict | 2.26 | 46.54
Combined | 28.00 | 41.97
|  |  |

Table 3: Manchu-Korean Translation Performance

We perform machine translation and evaluate the performance on all the
available combinations of parallel corpora: Mǎnwén Lǎodàng, Manchu-Korean
dictionary, and the combined dataset. In particular, we augment the training
sets of each corpus to alleviate the data scarcity problem. Table 3 shows the
performance of our Manchu-Korean translation models, with BLEU score (Papineni
et al., 2002) and Perplexity (PPL) as the metrices. We train each model for 5
epochs and report the one with the best performance.

The first block of Table 3 shows the translation performance based on the
original Manchu-Korean parallel corpora. All the experiments here show BLEU
scores of 0.0, which represent that none of the test sentences are accurately
translated. Most of the predicted translations include the special symbol
‘<UNK>’ instead of proper Korean tokens, possibly due to the small dataset and
vocabulary size.

The second block shows the experiment results from the augmented version of
the parallel corpora, where up to 50% of the tokens in each sentence are
replaced for data augmentation. The third block displays experiments on
another augmented version where all tokens with substitutes are replaced. The
augmentation procedure increases the size of the training set, resulting in a
significant rise in the translation performance. BLEU scores exceed 38 on the
Mǎnwén Lǎodàng test set, and around 28 on the combined test set. The two
versions of the augmented dataset show comparable performance, but replacing
all the possible words in the corpus resulted in slightly higher BLEU scores.

Due to data augmentation, the vocabulary for each model is expanded; for
example, the original Mǎnwén Lǎodàng vocabulary includes 4,335 words, while
the full-augmented dataset constructs an expanded vocabulary with 11,089
words. A larger vocabulary and training set may have helped the language
model’s representation and result in better translation performance.
Additionally, most newly induced words are from the augmentation sources which
include monolingual Manchu texts, different from our parallel corpora. This
expansion of word diversity may have also affected the models’ perplexity to
increase when they predicted the next words in each sentence.

On the other hand, results on the Manchu-Korean dictionary are consistently
very low, and this may have influenced the lower performance of the combined
test set. We suppose that it is because the corpus is a dictionary, where each
line is a unique word or phrase. The training set and the test set would have
much fewer overlaps in their vocabularies, and this could cause a number of
‘<UNK>’ generations in the model prediction.

##  5 Conclusion

In our exploration of the critically endangered Manchu language, we have made
significant strides towards development of low-resource NLP through the
development of the Manchu-Korean MT system, "Mergen." Our endeavor to train
this model, despite the challenges posed by the scarcity of a Manchu-Korean
parallel dataset, demonstrates the potential of an innovative data
augmentation strategy. This attempt is also significant in that we have
collected all the digitized Manchu text data. By leveraging resources such as
"Mǎnwén Làodǎng" and a Manchu-Korean dictionary, and by adopting a word
substitution techniqus guided by GloVe embeddings, we have not only built a
functional MT system but have also considerably enhanced its accuracy, as
evidenced by the increase in the BLEU score. Our encoder-decoder NMT model,
equipped with a bi-directional GRU layer, has shown promising results,
offering hope for the preservation and accessibility of the Manchu language to
future generations. We anticipate that this research will serve as a
foundation for further innovations in the realm of endangered language
preservation.

## Limitations

The main limitation of this study is the scarcity of resources. Numerous
Manchu literatures exist in East Asia (Vovin, 2023), including China (Elliott,
2001), Korea (Ko and You, 2012), and Mongolia (Choi, 2014). However, most of
them lack an electronic version. The only publicly available Manchu language
database is the Manchu Dictionary and Literature DB, created by Seoul National
University and supported by the National Research Foundation of
Korea.222NFR-2012S1A5B4A01035397, available at
http://ffr.krm.or.kr/base/td037/intro_db.html Furthermore, the majority of
these resources have not been translated into Korean. To address this gap, we
intend to provide supplementary parallel texts translated into Korean for
further study. In addition, we plan to implement a cutting-edge method of
Transformer-based language model including Manchu language. Knowledge
Distillation could be a way for modeling endangered languages, training a
small student model based on those languages and improving it with a teacher
model based on high-resource languages (Heffernan et al., 2022).

## Ethics Statement

The Manchu language, classified as critically endangered, remains
underrepresented due to its scarce resources. As such, it has yet to be
incorporated into any multilingual language models. This study pioneers Manchu
translation efforts, an endeavor previously uncharted. Our primary research
objective as NLP practitioners is to prevent the extinction of Manchu language
and ensure its preservation. We have no intention of commercializing the
translation model. Instead, by making the model publicly available, we aim to
facilitate and encourage as many individuals as possible to learn Manchu using
our translator. We are committed to continuous collaboration with Manchu
language researchers. We endeavor to enhance the performance of our translator
and regularly update it with new Manchu data to ensure its accuracy.

## References

  * An (1993) Shuangcheng An. 1993.  _Man Han Da Ci Dian_.  Liaoning Minzhu Chubanshe, Shenyang.
  * Bahdanau et al. (2016) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2016.  Neural machine translation by jointly learning to align and translate.
  * Cho et al. (2014) Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülçehre, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014.  Learning phrase representations using RNN encoder-decoder for statistical machine translation.  _CoRR_ , abs/1406.1078.
  * Choi (2014) Donggeun Choi. 2014.  A study of Manchu language literatures in Mongolia.  _The journal of humanities_ , 25:275–303.
  * Choi (2009) Dongguen Choi. 2009.  A comparative study of substitute - Korean keos, Mongolian yum, Manchu -ngge -.  _Mongolian Studies_ , 27:205–228.
  * Choi et al. (2023a) Woonho Choi, Sunghoon Jung, and Jeongup Do. 2023a.  Construction of the Manchu corpus: focusing on Manwen laodang Taidzu.  _Altai Hakpo_ , 33:67–87.
  * Choi et al. (2023b) Woonho Choi, Sunghoon Jung, and Jeongup Do. 2023b.  Word embeddings for Manwen laodang corpus with focus on names of countries and articles.  In _Proceedings of the 16th Seoul International Altaistic Conference_ , pages 189–204. The Altaic Society of Korea.
  * Conneau et al. (2019) Alexis Conneau, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Edouard Grave, Myle Ott, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Unsupervised cross-lingual representation learning at scale.  _CoRR_ , abs/1911.02116.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  Bert: Pre-training of deep bidirectional transformers for language understanding.
  * Elliott (2001) Mark C Elliott. 2001.  The manchu-language archives of the qing dynasty and the origins of the palace memorial system.  _Late Imperial China_ , 22(1):1–70.
  * Gibadullin et al. (2019) Ilshat Gibadullin, Aidar Valeev, Albina Khusainova, and Adil Khan. 2019.  A survey of methods to leverage monolingual data in low-resource neural machine translation.  _CoRR_ , abs/1910.00373.
  * Heffernan et al. (2022) Kevin Heffernan, Onur Çelebi, and Holger Schwenk. 2022.  Bitext mining using distilled sentence representations for low-resource languages.
  * Jiao et al. (2020) Xiaoqi Jiao, Yichun Yin, Lifeng Shang, Xin Jiang, Xiao Chen, Linlin Li, Fang Wang, and Qun Liu. 2020.  Tinybert: Distilling bert for natural language understanding.
  * Kim et al. (2019) Juwon Kim, Dongho Ko, Gyeyeong Choe, Sangchul Park, Jeongup Do, Hyungmi Lee, Hui Jin, and Jaehong Shim. 2019.  _Tongki Fuka Sindaha Hergen i Dangse - The Chronicles of Early Qing Dynasty: Taizu Vol. 1 2_.  Seoul National University Press, Seoul.
  * Kim et al. (2008) Juwon Kim, Dongho Ko, Youfeng Han, Lianyu Piao, and B. V. Boldyrev. 2008.  _Materials of spoken Manchu_.  unesco.
  * King (2015) Benjamin Philip King. 2015.  _Practical Natural Language Processing for Low-Resource Languages._ Ph.D. thesis.
  * Ko (2023) Dongho Ko. 2023.  Manchu-tungus studies in korea: Focusing on the studies of third-generation scholars.  _Reosiahag_ , 26:1–27.
  * Ko and You (2012) Dongho Ko and Hyunjo You. 2012.  For building a database of written Manchu.  _Kenci Inmwunhak_ , 8:5–30.
  * Lakew et al. (2018) Surafel Melaku Lakew, Quintino F. Lotito, Matteo Negri, Marco Turchi, and Marcello Federico. 2018.  Improving zero-shot translation of low-resource languages.  _CoRR_ , abs/1811.01389.
  * Lample and Conneau (2019) Guillaume Lample and Alexis Conneau. 2019.  Cross-lingual language model pretraining.  _CoRR_ , abs/1901.07291.
  * Lee (2019) Chungmin Lee. 2019.  Factivity alternation of attitude ‘know’ in Korean, Mongolian, Uyghur, Manchu, Azeri, etc. and content clausal nominals.  _Journal of Cognitive Science_ , 20(4):449–503.
  * Lee (2017) Hoon Lee. 2017.  _Manju Solho Gisun Kamcibuha Buleku Bithe - Manhan-sacen_.  Korea University Press, Seoul.
  * Liu et al. (2020) Yinhan Liu, Jiatao Gu, Naman Goyal, Xian Li, Sergey Edunov, Marjan Ghazvininejad, Mike Lewis, and Luke Zettlemoyer. 2020.  Multilingual denoising pre-training for neural machine translation.  _Transactions of the Association for Computational Linguistics_ , 8:726–742.
  * Luo et al. (2020) Jiaming Luo, Frederik Hartmann, Enrico Santus, Yuan Cao, and Regina Barzilay. 2020\.  Deciphering undersegmented ancient scripts using phonetic prior.  _CoRR_ , abs/2010.11054.
  * Malchukov and Czerwinski (2020) Andrej Malchukov and Patryk Czerwinski. 2020.  Complex constructions in the Transeurasian languages.  In Martine Robbeets and Alexander Savelyev, editors, _The Oxford Guide to the Transeurasian Languages_ , pages 625–644. Oxford University Press, Oxford.
  * Martin (1992) Samuel E. Martin. 1992.  _A Reference Grammar of Korean_.  Charles E. Tuttle, Rutland, VT and Tokyo.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pages 311–318, Philadelphia, Pennsylvania, USA. Association for Computational Linguistics.
  * Park (2018) Sangchul Park. 2018.  The function of Modern Korean as in discourse.  _Eoneohag_ , 81:243–264.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher Manning. 2014.  GloVe: Global vectors for word representation.  In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1532–1543, Doha, Qatar. Association for Computational Linguistics.
  * Pires et al. (2019) Telmo Pires, Eva Schlinger, and Dan Garrette. 2019.  How multilingual is multilingual devlin? _CoRR_ , abs/1906.01502.
  * Qi et al. (2018) Ye Qi, Devendra Sachan, Matthieu Felix, Sarguna Padmanabhan, and Graham Neubig. 2018\.  When and why are pre-trained word embeddings useful for neural machine translation? In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 529–535, New Orleans, Louisiana. Association for Computational Linguistics.
  * Seong (1977) Baegin Seong. 1977.  Romanization of the special letters of manchu.  _Eoneohag_ , 2:185–197.
  * Siddhant et al. (2020) Aditya Siddhant, Ankur Bapna, Yuan Cao, Orhan Firat, Mia Xu Chen, Sneha Reddy Kudugunta, Naveen Arivazhagan, and Yonghui Wu. 2020.  Leveraging monolingual data with self-supervision for multilingual neural machine translation.  _CoRR_ , abs/2005.04816.
  * Tang et al. (2021) Yuqing Tang, Chau Tran, Xian Li, Peng-Jen Chen, Naman Goyal, Vishrav Chaudhary, Jiatao Gu, and Angela Fan. 2021.  Multilingual translation from denoising pre-training.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 3450–3466.
  * Tsunoda (2006) Tasaku Tsunoda. 2006.  _Language endangerment and language revitalization: An introduction_.  De Gruyter Mouton.
  * Vovin (2023) Alexander Vovin. 2023.  Written Manchu.  In Alexander Vovin, José Andrés Alonso de la Fuente, and Juha Janhunen, editors, _The Tungusic Languages_ , pages 103–138. Routledge, New York.
  * Xue et al. (2021) Linting Xue, Noah Constant, Adam Roberts, Mihir Kale, Rami Al-Rfou, Aditya Siddhant, Aditya Barua, and Colin Raffel. 2021.  mt5: A massively multilingual pre-trained text-to-text transformer.
  * You (2014) Hyun-Jo You. 2014.  A manchu speller: With a practical introduction to the natural language processing of minority languages.  _Altai Hakpo_ , 24:39–67.
  * Zhang et al. (2020) Shiyue Zhang, Benjamin Frey, and Mohit Bansal. 2020.  Chren: Cherokee-english machine translation for endangered language revitalization.

##  Appendix A Example Appendix

Figure 2: Example of Romanizations of Manchu text and Korean text


rates. The training set size ($m$), validation set size ($v$) and test set
size ($t$) for the datasets are given in Table 5. Typically,
$m:v:t=0.4:0.4:0.2$. The role of the validation set is to compute the
empirical risk $\hat{l}_{i}$ of the SVM $h(\lambda_{i})\in\mathcal{H}$ which
will be used for deriving the PAC-Bayesian bound. Training error cannot be
considered as empirical risk for a classifier in our set up since PAC-Bayesian
theorem requires that the classifiers should be fixed and should not rely on
training examples Bégin et al. (2016). This is needed to define a sample
independent, classifier set independent right hand side threshold
$\mathcal{I}^{K}_{\phi}(m)$ for the PAC-Bayesian bound which holds uniformly
for all samples.

The classifier set,
$\mathcal{H}=\\{h(\lambda_{i})|\lambda_{i}\in\Lambda\;\forall
i=1,\ldots,H\\}$, consists of RBF kernel SVMs generated from these datasets
with regularization parameter values in the set
$\Lambda=\\{0.1,0.11,\ldots,20\\}$ chosen above. We follow the scheme provided
in Bégin et al. (2016); Thiemann et al. (2017) to generate our classifier set
$\mathcal{H}$. A common test set of size $t$ is kept aside beforehand. The
remaining subset of the dataset constitutes a training and validation set
composition with $m+v$ examples. Each classifier
$h(\lambda_{i})\in\mathcal{H}$ is trained on $m$ training examples subsampled
from this composite set and validated on the remaining $v$ examples. Overlaps
between training sets of different classifiers are allowed. Same is true for
their validation sets. Any two validation sets have a difference of at least
one example, which means that the validation errors on these sets are i.i.d
random variables. The validation error of SVM $h(\lambda_{i})\in\mathcal{H}$
is taken to be its empirical risk value, $\hat{l}_{i}$.

Depending on the dataset, these SVMs have different ranges and degrees of
variation in their empirical risk values. Generally, these empirical risk
values show an increasing trend as the value of $\lambda$ increases, but the
rate of growth differs from dataset to dataset. Some datasets show steady
increase with stabilized values (Banknote, Haberman, Mushroom and Wave), while
others have steep increase and haphazard values (Bupa, Ionosphere and
Spambase). Gradual increment might be accompanied by lot of variation
(Mammographic dataset) and stabilzed nature may not hold for the whole range
of $\lambda$ (Wdbc dataset, with low, stable values for $\lambda\leq 15$ and a
heavy variation for $\lambda>15$) This phenomenon can be captured by variance
of the empirical values across its range, but the variance of the empirical
risk values across the subintervals of $\Lambda$ is equally important to
quantify the rate of increase. For a visual illustration of the variance in
the empirical risk values and test error rates of the SVMs that we have
constructed on the different UCI datasets, please refer to Figure 5 and Figure
6.

##### Computational Framework

SVM QP (with RBF kernels) was implemented using ksvm function in kernlab
package Karatzoglou et al. (2004) in R (version 3.1.3 (2015-03-09)). The
Gaussian width parameter is estimated by kernlab using sigest function which
estimates the 0.1 and 0.9 quantile of distance between the points in the data.

The optimization problem for finding the optimal posterior that minimizes the
PAC-Bayesian bound was implemented in AMPL Interface and solved using Ipopt
software package (version 3.12 (2016-05-01)) Wächter and Biegler (2006). All
the computations were done on a machine equipped with 12 Intel Xeon 2.20 GHz
cores and 64 GB RAM.

Figure 5: Empirical risk values (validation errors)
$\hat{l}_{\text{val}}(\lambda)$ and test errors
$\hat{l}_{\text{test}}(\lambda)$ of SVMs corresponding to regularization
parameter $\lambda\in\Lambda=\\{0.0,0.11,\ldots,20\\}$ trained on 40% of the
dataset and validated on the other 40% of the dataset, with test errors
computed on the remaining 20% of the dataset as described in Section G.1.

Figure 6: Empirical risk values (validation errors)
$\hat{l}_{\text{val}}(\lambda)$ and test errors
$\hat{l}_{\text{test}}(\lambda)$ of SVMs trained on 40% of the dataset and
validated on the other 40% of the dataset, with test errors computed on the
remaining 20% of the dataset as described in Section G.1.

##  Appendix H Comparing various PAC-Bayesian optimal posteriors

In our analysis with finite classifier set, we have determined optimal
posterior minimizing the PAC-Bayesian bounds formed from combinations of
different distance functions and divergence measures. These are illustrated in
the previous section. Mainly, five distance functions (between the averaged
empirical risk and averaged true risk of a stochastic classifier) were
considered: KL-divergence as distance function, its Pinsker’s approximation
and a sixth degree polynomial approximation; linear and squared distances.

The posterior weight, $q^{\ast}_{i,\phi,\text{div}}$, is negatively
proportional to the empirical risk, $\hat{l}_{i}$, of the classifier in the
support set, but the constant of proportionality is different in the two
classes. The optimal posteriors corresponding to the class derived using KL-
divergence measure exhibit exponentially decreasing weights as the empirical
risk increases, and generally have full support (entire classifier set).

To quantify the level of concentration that these posteriors have on their
supports, we use Herfindahl-Hirschman Index (HHI) Hirschman (1945); Wikipedia
contributors (2019), which is perhaps the most widely used measure of economic
concentration. It is defined as the sum of the squares of the market shares of
the firms within the industry (sometimes limited to the 50 largest firms),
where the market shares are expressed as fractions. For probability
distributions, HHI is equivalent to their $\ell_{2}$-norm.

In our computations, we observe that the posteriors
$Q^{\ast}_{\phi,\text{KL}}$ have high HHI, which indicates that they have more
concentration around the low values of $\hat{l}_{i}$s even though they have
full support. They display a greedy behaviour towards classifiers
(regularization parameter values) yielding low sample errors. This explains
why such posteriors have a good test set performance. This behaviour hints at
an underlying regularization done by the divergence function that we use in
the PAC-Bayesian bound.

Dataset |  PAC-Bayesian Bound, $B^{\ast}_{\phi,\text{KL}}$ |  Average Test Error, $T_{\phi,\text{KL}}$
---|---|---
| $B^{\ast}_{\text{lin, KL}}$ | $B^{\ast}_{\text{sq, KL}}$ | $B^{\ast}_{\text{P, KL}}$ | $B^{\ast}_{\text{CH, KL}}$ | $B^{\ast}_{\text{kl, KL}}$ | $T_{\text{lin, KL}}$ | $T_{\text{sq, KL}}$ | $T_{\text{P, KL}}$ | $T_{\text{CH, KL}}$ | $T_{\text{kl, KL}}$
Spambase | NaN | 0.20289 | 0.17671 | 0.18279 | 0.15737$\star$ | 0.10206 | 0.10353 | 0.10277 | 0.10263 | 0.10231$\star$
Bupa | 0.29382 |  0.40292 0.36536 | 0.31596 | 0.32896 | 0.27439$\star$ | 0.14139 |  0.15103 0.15400 | 0.14425 | 0.14269 | 0.13738$\star$
Mammographic | 0.31857 |  0.35706 0.32592 | 0.30442 | 0.31596 | 0.28583$\star$ | 0.13805 |  0.13934 0.13847 | 0.14015 | 0.14008 | 0.13978$\star$
Wdbc | 0.20369 |  0.25657 0.21754 | 0.19908 | 0.21318 | 0.14237 | 0.03315 |  0.03168 0.03168 | 0.03192 | 0.03209 | 0.03351
Banknote | 0.13371 |  0.12752 0.09855 | 0.09094 | 0.10241 | 0.01758 | 0.00030 |  0.00103 0.00112 | 0.00087 | 0.00081 | 5.5e-05
Mushroom | NaN | 0.06388 | 0.04521 | 0.05226 | 0.00415 | 2.29e-05 | 6.31e-05 | 5.8e-05 | 5.61e-05 | 1.1e-05
Ionosphere | 0.20024 |  0.28773 0.24171 | 0.21540 | 0.23470 | 0.13208 | 0.07174 |  0.07236 0.07247 | 0.07212 | 0.07202 | 0.07059
Waveform | NaN | 0.12990 | 0.10529 | 0.11355 | 0.07254 | 0.05138 | 0.05231 | 0.05219 | 0.05212 | 0.05152
Haberman | 0.37065 |  0.47695 0.43052 | 0.39487 | 0.40945 | 0.37762$\star$ | 0.29485 |  0.28140 0.28000 | 0.29101 | 0.29341 | 0.26900$\star$
Table 6: PAC-Bayesian bounds and averaged test error rates for $Q^{\ast}_{\phi,\text{KL}}$ We compare the bound values $B^{\ast}_{\phi,\text{KL}}$ and average test error rates $T_{\phi,\text{KL}}$ of the optimal posteriors due to five distance functions, $\phi$: KL-divergence $kl$, its Pinsker’s approximation $\phi_{\text{P}}$ and a sixth degree polynomial approximation $\phi_{\text{CH}}$; linear $\phi_{\text{lin}}$ and squared distances $\phi_{\text{sq}}$ for $H=500$ SVM classiifers. For large sample size ($m\geq 1028$), the constant $\mathcal{I}^{K}_{\text{lin}}(m)$ cannot be computed due to storage limitations for floating point numbers and in that case, $B^{\ast}_{\text{lin,KL}}$ is denoted by NaN. $B^{\ast}_{\text{sq, KL}}$ and corresponding $Q^{\ast}_{\text{sq, KL}}$ were determined using two values: $2\sqrt{m}$ (in regular font face) and $\mathcal{I}^{K}_{\text{sq}}(m)$ (in italicized font face). $\mathcal{I}^{K}_{\text{sq}}(m)$ cannot be computed for datasets with high sample size ($m\geq 1028$) due to storage limitation on floating point numbers. Hence we have only one bound value for such datasets (namely Spambase, Mushroom and Waveform) which is computed using $2\sqrt{m}$. $\star$ refers to values obtained using fixed point(FP) equation because the solver Ipopt does not converge to a solution. Lowest 10% bound values and test error rates for each dataset are denoted in bold face. KL-distance has the tightest bound and lowest 10% error rate for almost all the datasets, but is computationally expensive and has multiple local minima. Between the approximations $\phi_{\text{P}}$ and $\phi_{\text{CH}}$, the latter has lower test error values but a slightly complicated bound evaluation. $\phi_{\text{sq}}$ is ranked lowest on bound values and test error rates, followed by $\phi_{\text{CH}}$ and $\phi_{\text{P}}$. $\phi_{\text{sq}}$ and $\phi_{\text{P}}$ are related by a scaling ($\phi_{\text{P}}=2\phi_{\text{sq}}$). $\phi_{\text{P}}$ provides a lower bound value than that of $\phi_{\text{sq}}$, but both have comparable test set performances with differences of at most 3%. The global solution for $\phi_{\text{lin}}$ has second lowest bound value for all the datasets considered (except for the ones where $m\geq 1028$, namely, Spambase, Mushroom and Waveform, where the bound $B^{\ast}_{\text{lin},KL}$ cannot be computed) and also has the lowest 10% test error rates for most of the datasets. All the five distance functions have good generalization performance (lowest 10% test error values) on most of the datasets considered, except for Bupa dataset and two almost separable datasets, Banknote and Mushroom, where $\phi_{\text{lin}}$ and $\phi_{\text{kl}}$ do better than other three $\phi$s. Dataset |  PAC-Bayesian Bound, $B^{\ast}_{\phi,\text{KL}}$ |  Average Test Error, $T_{\phi,\text{KL}}$
---|---|---
| $B^{\ast}_{\text{lin, KL}}$ | $B^{\ast}_{\text{sq, KL}}$ | $B^{\ast}_{\text{P, KL}}$ | $B^{\ast}_{\text{CH, KL}}$ | $B^{\ast}_{\text{kl, KL}}$ | $T_{\text{lin, KL}}$ | $T_{\text{sq, KL}}$ | $T_{\text{P, KL}}$ | $T_{\text{CH, KL}}$ | $T_{\text{kl, KL}}$
Spambase | NaN | 0.20046 | 0.17361 | 0.17958 | 0.15332$\star$ | 0.15684 | 0.15392 | 0.15423 | 0.15434 | 0.15487$\star$
Bupa | 0.27005 |  0.38167 0.34547 | 0.29265 | 0.30537 | 0.23851$\star$ | 0.13207 |  0.145801 0.14873 | 0.13631 | 0.13382 | 0.11998$\star$
Mammographic | 0.29518 |  0.34187 0.31290 | 0.28790 | 0.29659 | 0.26063$\star$ | 0.20462 |  0.21120 0.21386 | 0.20716 | 0.20628 | 0.20519$\star$
Wdbc | 0.20706 |  0.26000 0.22122 | 0.20236 | 0.21646 | 0.14759$\star$ | 0.06489 |  0.06901 0.07052 | 0.06650 | 0.06584 | 0.06541$\star$
Banknote | 0.13647 |  0.13225 0.10343 | 0.09538 | 0.10672 | 0.02051 | 0.00161 |  0.00561 0.00592 | 0.00500 | 0.00469 | 0.00037
Mushroom | NaN | 0.06584 | 0.04702 | 0.05399 | 0.00489 | 8.92e-05 | 0.00066 | 0.00057 | 0.00053 | 1.39e-05
Ionosphere | 0.20816 |  0.30151 0.25884 | 0.22508 | 0.24011 | 0.14707$\star$ | 0.04494 |  0.04781 0.04899 | 0.04393 | 0.04553 | 0.04359$\star$
Waveform | NaN | 0.12875 | 0.10335 | 0.11103 | 0.06338 | 0.05847 | 0.05175 | 0.05276 | 0.05345 | 0.05792
Haberman | 0.37277 |  0.48385 0.43977 | 0.39769 | 0.41178 | 0.37998$\star$ | 0.29157 |  0.29069 0.29007 | 0.29163 | 0.29162 | 0.28997$\star$
Table 7: Earlier computations for comparison. We obtain improved bound values
and test error rates for optimal posteriors $Q^{\ast}_{\phi,\text{KL}}$ in
Table 6 above by restricting the base classifiers generated using
$\Lambda=\\{10^{-5},5\\}$ obtained as a combination of arithmetic-geometric
progression for the interval $(10^{-5},0.1)$ and linearly spaced values
between 0.1 and 5 at a granularity of 0.01. The test error rates for Spambase
(improved from 0.15 to 0.10 across 5 distance functions), Mammographic, Wdbc
and Banknote datasets decreased significantly. For other datasets, the test
error rates are comparable.

Dataset H | 50 | 200 | 500 | 1000 | 1990
---|---|---|---|---|---
(Validation set size, $v$) | $B^{FP}_{\text{kl, KL}}$ | $B^{solver}_{\text{kl, KL}}$ | $B^{FP}_{\text{kl, KL}}$ | $B^{solver}_{\text{kl, KL}}$ | $B^{FP}_{\text{kl, KL}}$ | $B^{solver}_{\text{kl, KL}}$ | $B^{FP}_{\text{kl, KL}}$ | $B^{solver}_{\text{kl, KL}}$ | $B^{FP}_{\text{kl, KL}}$ | $B^{solver}_{\text{kl, KL}}$
Spambase $(v=1840)$ | 0.14726 | 0.147260 | 0.149424 | 0.149424 | 0.15157 |  0.270042(E) | 0.152023 |  0.294836(E) | 0.153324 |  0.314523(E)
Bupa $(v=138)$ | 0.208330 | 0.208333 | 0.220062 | 0.220065 | 0.227504 |  0.437317(E) | 0.232998 |  0.508671(E) | 0.238509 |  0.576823(E)
Mammographic $(v=332)$ | 0.241706 | 0.241680 | 0.249234 | 0.249235 | 0.253854 | 0.253847 | 0.257411 |  0.302582(E) | 0.260632 |  0.335105(E)
Wdbc $(v=227)$ | 0.127827 | 0.127827 | 0.134727 | 0.134714 | 0.139659 | 0.139655 | 0.14363 | 0.143656 | 0.147595 |  0.187134(E)
Banknote $(v=549)$ | 0.015278 | 0.015278 | 0.016358 | 0.016356 | 0.018065 | 0.018065 | 0.232998 |  0.513805(E) | 0.238509 |  0.573999(E)
Mushroom $(v=2257)$ | 0.004050 | 0.004050 | 0.004050 | 0.004050 | 0.004150 | 0.004150 | 0.004517 | 0.004517 | 0.004882 | 0.004883
Ionosphere $(v=140)$ | 0.119248 |  0.122997(M) | 0.129552 |  0.141167(M) | 0.13658 | 0.136579 | 0.141938 |  0.275581(E) | 0.147074 |  0.404999(E)
Waveform $(v=1323)$ | 0.058419 | 0.058424 | 0.060210 | 0.060206 | 0.061562 | 0.06157 | 0.062467 | 0.062473 | 0.063376 | 0.063387
Haberman $(v=122)$ | 0.342978 |  0.350085(M) | 0.356983 | 0.356982 | 0.366412 |  0.407535(E) | 0.373351 |  0.421606(E) | 0.379982 |  0.427411(E)
Table 8: Bound values for kl-KL case: Comparing the PAC-Bayesian bounds for
the case of KL divergence as distance function with KL divergence measure
between prior and posterior distributions. $B^{KKT}_{\text{kl, KL}}$
represents the bound due to the fixed point solution obtained by solving the
partial KKT system for the bound minimization problem (7) in the main paper.
$B^{solver}_{\text{kl, KL}}$ is the value of the bound output by the solver
for the same case. We observe that the bound values are exactly same for
certain cases. The fixed point equation always converges to a solution, even
when the Ipopt solver is not able to identify a locally optimal solution and
throws up an error. These cases are denoted by ‘E’ (Unknown Error) or ‘R’
(Restoration Phase Failed) or ‘M’ (Maximum Number of Iterations Exceeded), as
output by the solver.

Dataset | PAC-Bayesian Bound | Average Test Error
---|---|---
| $B^{FP}_{\text{kl, KL}}$ |  Range($B^{CCP}_{\text{kl, KL}}$) |  Mean($B^{CCP}_{\text{kl, KL}}$) | $T^{FP}_{\text{kl, KL}}$ |  Range($T^{CCP}_{\text{kl, KL}}$) |  Mean($T^{CCP}_{\text{kl, KL}}$)
Spambase | 0.14726 | [0.16632, 0.19290] |  0.18257$\pm$ 0.00301 | 0.15465 | [0.16412, 0.18537] |  0.17578 $\pm$ 0.00235
Bupa | 0.20833 | [0.23380, 0.26191] |  0.24741 $\pm$ 0.00412 | 0.12502 | [0.14943, 0.18810] |  0.16754 $\pm$ 0.00599
Mammographic | 0.24171 | [0.24760, 0.25558] |  0.25190 $\pm$ 0.00116 | 0.20566 | [0.20665, 0.21793] |  0.21209 $\pm$ 0.00195
Wdbc | 0.12782 | [0.13061, 0.13659] |  0.13320 $\pm$ 0.00085 | 0.06630 | [0.05925, 0.07212] |  0.06492 $\pm$ 0.00183
Banknote | 0.01528 | NA | NA | 0.00036 | NA | NA
Mushroom | 0.00405 | NA | NA | 0 | NA | NA
Ionosphere | 0.11925 | [0.12284, 0.13132] |  0.12631$\pm$ 0.00119 | 0.04409 | [0.03889, 0.05328] |  0.04562 $\pm$ 0.00214
Waveform | 0.05842 | [0.06353, 0.06711] |  0.06525 $\pm$ 0.00061 | 0.05749 | [0.05003, 0.05451] |  0.05213 $\pm$ 0.00073
Haberman | 0.34298 | [0.34857, 0.36011] |  0.35417 $\pm$ 0.00175 | 0.29257 | [0.28524, 0.30430] |  0.29346 $\pm$ 0.00286
Table 9: We compare the bound values and test error rates of the optimal
posterior obtained via Fixed Point (FP) scheme and the posterior based on
Convex-Concave Procedure (CCP) minimizing the PAC-Bayesian bound $B_{\text{kl,
KL}}$ based on KL-distance function with KL-divergence measure. The CCP based
posteriors are identified by the bound minimization model described in Section
D.2. The bound values and test error rates for FP scheme based solution are
denoted by $B^{FP}_{\text{kl, KL}}$ and $T^{FP}_{\text{kl, KL}}$. Similarly,
the bound values and test error rates of the CCP based posterior are denoted
by $B^{CCP}_{\text{kl, KL}}$ and $T^{CCP}_{\text{kl, KL}}$. For computations,
we consider SVM classifiers generated on nine datasets from UCI repository
Dheeru and Karra Taniskidou (2017) using the scheme in Section G.1 for $H=50$
values in $\Lambda=\\{0.1,0.11,\ldots,\\}$. We run the CCP procedure for 1000
different initializations of posterior $Q^{0}$ (as done in Lipp and Boyd
(2016)). The range, mean and standard deviation of the bound values and
average test error rates of the CCP based posteriors obtained by these 1000
initializations are tabulated above. We notice that $B^{FP}_{\text{kl, KL}}$
is always better than $B^{CCP}_{\text{kl, KL}}$ and $T^{FP}_{\text{kl, KL}}$
is comparable with mean value of $T^{CCP}_{\text{kl, KL}}$ for different
datasets considered. This might be because FP scheme identifies the global
minimum for kl-KL based bound minimization problem, whereas CCP converges to a
local solution or a stationary point. ‘NA’ denotes the cases where the CCP
cannot provide linear approximation to $kl(\mathbb{E}_{Q}[\hat{l}],r)$ because
a subgradient cannot be determined when $\mathbb{E}_{Q}[\hat{l}]$ takes the
boundary value zero. Such cases usually occur for almost separable datasets –
Banknote and Mushroom, where the quantity $\mathbb{E}_{Q}[\hat{l}]=0$ for any
distribution $Q$ since all $\hat{l}_{i}$s take value zero for $i=1,\ldots,50$.

###  H.1 Comparison of posterior on full support with that on subset support

We have shown that linear distance based bound $B_{\text{lin, KL}}(Q)$ has
full support when prior is uniform. For other four distance functions, $\phi$s
(squared distance, KL-distance, Pinsker’s approximation and sixth degree
polynomial approximation), we analyze their support set by computations on UCI
datasets. For uniform prior on classifier set $\mathcal{H}$, we compare the
local minimizers of $B_{\phi,\text{KL}}(Q)$ on $H$-dimensional simplex
(allowing for subset support), with the one computed on interior of
$H$-dimensional simplex (full support). $H$ denotes the classifier set size
and $H^{\ast}$ denotes the optimal support size. We observe that datasets with
low and moderate variation in empirical risk values have full support,
$H=H^{\ast}$, whereas those with high variation have a smaller support but can
be approximated by optimal posterior determined on a full support as reported
in Tables 10 \- 13.

Dataset (Validation set size, $v$) |  # Classifiers $H$ |  Optimal Support Size, $H^{\ast}$ | $B^{solver}_{\text{sq, KL}}(H)$ | $B^{FP}_{\text{sq, KL}}(H^{\ast})$ | $T^{solver}_{\text{sq, KL}}(H)$ | $T^{FP}_{\text{sq, KL}}(H^{\ast})$ | $\|Q^{solver}_{\text{sq, KL}}(H)-Q^{FP}_{\text{sq, KL}}(H^{\ast})\|_{2}$ |  Time $(H)$ |  Time $(H^{\ast})$
---|---|---|---|---|---|---|---|---|---
Spambase $(v=1840)$ | 500 | 31 | 0.19625 | 0.19625 | 0.15390 | 0.15389 | 7.66 e-05 | 2.409 s | 0.112 s
Bupa $(v=138)$ | 1000 | 275 | 0.33576 | 0.33576 | 0.14955 | 0.14954 | 0.000103 | 18.58 s | 0.398 s
Mammographic $(v=332)$ | 1000 | 1000 | 0.30587 | 0.30587 | 0.21461 | 0.21461 | 0.000907 | 13.223 s | 0.407 s
Wdbc $(v=227)$ | 1990 | 1922 | 0.22121 | 0.22121 | 0.70523 | 0.70523 | 0.000391 | 174.024 s | 0.842 s
Banknote $(v=549)$ | 200 | 200 | 0.09646 | 0.09646 | 0.001756 | 0.001757 | 3.232 e-05 | 0.166 s | 0.04 s
Mushroom $(v=2257)$ | 1990 | 1990 | 0.06584 | 0.06584 | 0.00066 | 0.00066 | 0.000675 | 63.025 s | 0.755 s
Ionosphere $(v=140)$ | 200 | 200 | 0.22720 | 0.22720 | 0.43921 | 0.43291 | 1.146 e-05 | 0.164 s | 0.033 s
Waveform $(v=1323)$ | 1000 | 1000 | 0.12685 | 0.12685 | 0.05200 | 0.05200 | 0.000311 | 10.655 s | 0.276 s
Haberman $(v=122)$ | 500 | 500 | 0.41943 | 0.41943 | 0.28989 | 0.28989 | 0.000737 | 2.048 s | 0.093 s
Table 10: For uniform prior on classifier set $\mathcal{H}$, we compare the
(local) minimizer, $Q^{FP}_{\text{sq, KL}}(H^{\ast})$, of the bound function,
$B_{\text{sq,KL}}(Q)$ on the whole of $H$-dimensional simplex (allowing for
subset support), with the (local) minimizer, $Q^{solver}_{\text{sq, KL}}(H)$,
computed on the interior of the $H$-dimensional simplex (full support). $H$
denotes the size of the classifier set considered and $H^{\ast}$ denotes the
size of the support set for $Q^{FP}_{\text{sq,KL}}$, the local minimum for
(24) in the main paper. We call $H^{\ast}$ as the ‘optimal support size’.
$Q^{FP}_{\text{sq, KL}}(H^{\ast})$ was determined via a linear search among
the optimal posteriors with support on the increasing ordered subsets of
$\mathcal{H}$. $B^{solver}_{\text{sq,KL}}(H)$ and
$B^{FP}_{\text{sq,KL}}(H^{\ast})$ denote the bound values of the two
posteriors; and $T^{solver}_{\text{sq,KL}}(H)$ and
$T^{FP}_{\text{sq,KL}}(H^{\ast})$ denote their average test error rates. All
the computations were done with $\delta=0.01$. We notice that, in many
datasets (for example, Mammographic, Ionosphere and Banknote), $H^{\ast}=H$,
indicating that the local minimizer indeed has full support. These datasets
have low to moderate variance in the empirical risk values. Whereas the ones
with notably high variation in empirical risk values (namely, Spambase, Bupa
and Wdbc) have optimizers on a much smaller support size ($H^{\ast}\ll H$).
Yet the difference in the bound values and test error rates of the full
support posterior, $Q^{solver}_{\text{sq, KL}}(H)$ and the local minimizer
$Q^{FP}_{\text{sq, KL}}(H^{\ast})$ is negligible ($O(10^{-6})$). If we compare
the posteriors themselves, the $\ell_{2}$-norm of the difference between them
is very small ($O(10^{-4})$). This suggests that the posteriors lie within a
small neighbourhood. Considering the computation time taken, we observe that
$Q^{FP}_{\text{sq, KL}}(H)$ with full support can be computed within a
fraction of a second, even with the linear search, whereas computation for
$Q^{solver}_{\text{sq, KL}}(H^{\ast})$ can take anywhere between 0.164 seconds
to 174.024 seconds depending on the model parameters –
$H,S_{m},\delta,\\{l_{i}\\}_{i=1}^{H}$. We can obtain a very close
approximation to $Q^{FP}_{\text{sq, KL}}(H^{\ast})$ by considering a full
support posterior obtained by minimizing $B_{\text{sq, KL}}(Q)$ in the
interior of the $H$-dimensional probability simplex.

Dataset (Validation set size, $v$) |  # Classifiers $H$ |  Optimal Support Size, $H^{\ast}$ | $B^{solver}_{\text{kl, KL}}(H)$ | $B^{FP}_{\text{kl, KL}}(H^{\ast})$ | $T^{solver}_{\text{kl, KL}}(H)$ | $T^{FP}_{\text{kl, KL}}(H^{\ast})$ | $\|Q^{solver}_{\text{kl, KL}}(H)-Q^{FP}_{\text{kl, KL}}(H^{\ast})\|_{2}$ |  Time $(H)$ |  Time $(H^{\ast})$
---|---|---|---|---|---|---|---|---|---
Spambase $(v=1840)$ | 500 | 3 |  0.26885 (E) | 0.15115 |  0.24152 (E) | 0.15480 |  1.995252 (E) |  0.035 s (E) | 0.403 s
Bupa $(v=138)$ | 1000 | 19 |  0.51500 (E) | 0.23295 |  0.38550 (E) | 0.12097 |  1.971075 (E) |  0.064 s (E) | 1.207 s
Mammographic $(v=332)$ | 1000 | 40 |  0.30370 (E) | 0.25731 |  0.22828 (E) | 0.20505 |  1.929077 (E) |  0.067 s (E) | 1.479 s
Wdbc $(v=227)$ | 1990 | 613 |  0.18527 (E) | 0.14745 |  0.08870 (E) | 0.06536 |  1.757514 (E) |  0.185 s (E) | 4.207 s
Banknote $(v=549)$ | 200 | 110 | 0.01635 | 0.01635 | 0.00037 | 0.00037 | 1.952 e-05 | 0.066 s | 0.063 s
Mushroom $(v=2257)$ | 1990 | 336 | 0.00488 | 0.00488 | 1.399 e-05 | 1.318 e-05 | 0.003724 | 13.4.57 s | 2.126 s
Ionosphere $(v=140)$ | 200 | 186 | 0.12955 | 0.12952 | 0.04378 | 0.04378 | 0.002737 | 12.132 s | 0.182 s
Waveform $(v=1323)$ | 1000 | 7 | 0.06247 | 0.06240 | 0.05785 | 0.05794 | 0.024940 | 35.99 s | 1.064 s
Haberman $(v=122)$ | 500 | 180 |  0.40832 (E) | 0.36638 |  0.28768 (E) | 0.29161 |  1.718098 (E) |  0.037 s (E) | 0.482 s
Table 11: For uniform prior on classifier set $\mathcal{H}$, we compare the
(local) minimizer, $Q^{FP}_{\text{kl, KL}}(H^{\ast})$, of the bound function,
$B_{\text{kl,KL}}(Q)$ on the whole of $H$-dimensional simplex (allowing for
subset support), with the (local) minimizer, $Q^{solver}_{\text{kl, KL}}(H)$,
computed on the interior of the $H$-dimensional simplex (full support). $H$
denotes the size of the classifier set considered and $H^{\ast}$ denotes the
size of the support set for $Q^{FP}_{\text{kl,KL}}$, the local minimum for (7)
in the main paper. We call $H^{\ast}$ as the ‘optimal support size’.
$Q^{FP}_{\text{kl, KL}}(H^{\ast})$ was determined via a linear search among
the optimal posteriors with support on the increasing ordered subsets of
$\mathcal{H}$. $B^{solver}_{\text{kl,KL}}(H)$ and
$B^{FP}_{\text{kl,KL}}(H^{\ast})$ denote the bound values of the two
posteriors; and $T^{solver}_{\text{kl,KL}}(H)$ and
$T^{FP}_{\text{kl,KL}}(H^{\ast})$ denote their average test error rates. All
the computations were done with $\delta=0.01$. We notice that, if $H$ is
large, the solver does not converge to a solution in many datasets (for
example, Mammographic, Bupa and Haberman) which have moderate to considerable
variance in the empirical risk values. These cases are denoted by the symbol
‘E’. Whereas the almost separable datasets with low variation in empirical
risk values (namely, Banknote, Mushroom, Ionosphere and Waveform) have
optimizers on a much smaller support size ($H^{\ast}\ll H$). Yet the
difference in the bound values and test error rates of the full support
posterior, $Q^{solver}_{\text{kl, KL}}(H)$ and the local minimizer
$Q^{FP}_{\text{kl, KL}}(H^{\ast})$ is negligible ($O(10^{-5})$). If we compare
the posteriors themselves, the $\ell_{2}$-norm of the difference between them
is very small ($O(10^{-3})$). This suggests that the posteriors lie within a
small neighbourhood. Considering the computation time taken, we observe that
$Q^{FP}_{\text{kl, KL}}(H)$ with full support can be computed within fractions
of a upto 4.207 seconds, even with the linear search. Whereas computation for
$Q^{solver}_{\text{kl, KL}}(H^{\ast})$ can take anywhere between 0.066 seconds
to 35.99 seconds depending on the model parameters –
$H,S_{m},\delta,\\{l_{i}\\}_{i=1}^{H}$. We can obtain a very close
approximation to $Q^{FP}_{\text{kl, KL}}(H^{\ast})$ by considering a full
support posterior obtained by minimizing $B_{\text{kl, KL}}(Q)$ in the
interior of the $H$-dimensional probability simplex.

Dataset (Validation set size, $v$) |  # Classifiers $H$ |  Optimal Support Size, $H^{\ast}$ | $B^{solver}_{\text{P, KL}}(H)$ | $B^{FP}_{\text{P, KL}}(H^{\ast})$ | $T^{solver}_{\text{P, KL}}(H)$ | $T^{FP}_{\text{P, KL}}(H^{\ast})$ | $\|Q^{solver}_{\text{P, KL}}(H)-Q^{FP}_{\text{P, KL}}(H^{\ast})\|_{2}$ |  Time $(H)$ |  Time $(H^{\ast})$
---|---|---|---|---|---|---|---|---|---
Spambase $(v=1840)$ | 500 | 21 | 0.17065 | 0.17065 | 0.15416 | 0.15416 | 7.594 e-05 | 2.389 s | 0.101 s
Bupa $(v=138)$ | 1000 | 100 | 0.28683 | 0.28683 | 0.13714 | 0.13714 | 7.896 e -05 | 15.441 s | 0.316 s
Mammographic $(v=332)$ | 1000 | 954 | 0.28207 | 0.28207 | 0.20728 | 0.20728 | 0.000668 | 13.269 s | 0.390 s
Wdbc $(v=227)$ | 1990 | 1860 | 0.20236 | 0.20236 | 0.06650 | 0.06650 | 0.000249 | 114.228 s | 0.759 s
Banknote $(v=549)$ | 200 | 200 | 0.08909 | 0.08909 | 0.00148 | 0.00148 | 7.181 e-05 | 0.203 s | 0.025 s
Mushroom $(v=2257)$ | 1990 | 1990 | 0.04702 | 0.04702 | 0.00057 | 0.00057 | 0.001312 | 88.313 s | 0.641 s
Ionosphere $(v=140)$ | 200 | 200 | 0.20473 | 0.20473 | 0.04406 | 0.04406 | 0.000186 | 0.230 s | 0.028 s
Waveform $(v=1323)$ | 1000 | 1000 | 0.10161 | 0.10161 | 0.05289 | 0.05289 | 0.000912 | 11.146 s | 0.323 s
Haberman $(v=122)$ | 500 | 500 | 0.38421 | 0.38421 | 0.29159 | 0.29159 | 0.000190 | 2.184 s | 0.103 s
Table 12: For uniform prior on classifier set $\mathcal{H}$, we compare the
(local) minimizer, $Q^{FP}_{\text{P, KL}}(H^{\ast})$, of the bound function,
$B_{\text{P,KL}}(Q)$ on the whole of $H$-dimensional simplex (allowing for
subset support), with the (local) minimizer, $Q^{solver}_{\text{P, KL}}(H)$,
computed on the interior of the $H$-dimensional simplex (full support). $H$
denotes the size of the classifier set considered and $H^{\ast}$ denotes the
size of the support set for $Q^{FP}_{\text{P,KL}}$, the local minimum for (11)
in the main paper. We call $H^{\ast}$ as the ‘optimal support size’.
$Q^{FP}_{\text{P, KL}}(H^{\ast})$ was determined via a linear search among the
optimal posteriors with support on the increasing ordered subsets of
$\mathcal{H}$. $B^{solver}_{\text{P,KL}}(H)$ and
$B^{FP}_{\text{P,KL}}(H^{\ast})$ denote the bound values of the two
posteriors; and $T^{solver}_{\text{P,KL}}(H)$ and
$T^{FP}_{\text{P,KL}}(H^{\ast})$ denote their average test error rates. All
the computations were done with $\delta=0.01$. We notice that, in many
datasets (for example, Haberman, Ionosphere and Banknote), $H^{\ast}=H$,
indicating that the local minimizer indeed has full support. These datasets
have low to moderate variance in the empirical risk values. Whereas the ones
with notably high variation in empirical risk values (namely, Spambase, Bupa,
Mammographic and Wdbc) have optimizers on a much smaller support size
($H^{\ast}\ll H$). Yet the difference in the bound values and test error rates
of the full support posterior, $Q^{solver}_{\text{P, KL}}(H)$ and the local
minimizer $Q^{FP}_{\text{P, KL}}(H^{\ast})$ is negligible ($O(10^{-6})$). If
we compare the posteriors themselves, the $\ell_{2}$-norm of the difference
between them is very small ($O(10^{-4})$). This suggests that the posteriors
lie within a small neighbourhood. Considering the computation time taken, we
observe that $Q^{FP}_{\text{P, KL}}(H)$ with full support can be computed
within a fraction of a second, even with the linear search, whereas
computation for $Q^{solver}_{\text{P, KL}}(H^{\ast})$ can take anywhere
between 0.203 seconds to 114.228 seconds depending on the model parameters –
$H,S_{m},\delta,\\{l_{i}\\}_{i=1}^{H}$. We can obtain a very close
approximation to $Q^{FP}_{\text{P, KL}}(H^{\ast})$ by considering a full
support posterior obtained by minimizing $B_{\text{P, KL}}(Q)$ in the interior
of the $H$-dimensional probability simplex.

Dataset (Validation set size, $v$) |  # Classifiers $H$ |  Optimal Support Size, $H^{\ast}$ | $B^{solver}_{\text{CH, KL}}(H)$ | $B^{FP}_{\text{CH, KL}}(H^{\ast})$ | $T^{solver}_{\text{CH, KL}}(H)$ | $T^{FP}_{\text{CH, KL}}(H^{\ast})$ | $\|Q^{solver}_{\text{CH, KL}}(H)-Q^{FP}_{\text{CH, KL}}(H^{\ast})\|_{2}$ |  Time $(H)$ |  Time $(H^{\ast})$
---|---|---|---|---|---|---|---|---|---
Spambase $(v=1840)$ | 500 | 18 | 0.17688 | 0.17688 | 0.15428 | 0.15428 | 7.461 e-05 | 2.643 s | 0.171 s
Bupa $(v=138)$ | 1000 | 89 | 0.30002 | 0.30002 | 0.13462 | 0.13461 | 7.857 e -05 | 19.56 s | 0.593 s
Mammographic $(v=332)$ | 1000 | 892 | 0.29317 | 0.29317 | 0.20647 | 0.20646 | 0.000674 | 14.663 s | 0.706 s
Wdbc $(v=227)$ | 1990 | 1856 | 0.21646 | 0.21646 | 0.06584 | 0.06584 | 0.000305 | 143.57 s | 1.371 s
Banknote $(v=549)$ | 200 | 200 | 0.10063 | 0.10063 | 0.00141 | 0.00141 | 7.381 e-05 | 0.189 s | 0.041 s
Mushroom $(v=2257)$ | 1990 | 1990 | 0.05398 | 0.05398 | 0.00053 | 0.00053 | 0.001625 | 71.778 s | 0.972 s
Ionosphere $(v=140)$ | 200 | 200 | 0.22104 | 0.22104 | 0.04410 | 0.04410 | 0.000139 | 0.223 s | 0.055 s
Waveform $(v=1323)$ | 1000 | 1000 | 0.10940 | 0.10940 | 0.05350 | 0.05350 | 0.000384 | 13.745 s | 0.597 s
Haberman $(v=122)$ | 500 | 500 | 0.39950 | 0.39950 | 0.21655 | 0.21655 | 0.000177 | 2.499 s | 0.181 s
Table 13: For uniform prior on classifier set $\mathcal{H}$, we compare the
(local) minimizer, $Q^{FP}_{\text{CH, KL}}(H^{\ast})$, of the bound function,
$B_{\text{CH,KL}}(Q)$ on the whole of $H$-dimensional simplex (allowing for
subset support), with the (local) minimizer, $Q^{solver}_{\text{CH, KL}}(H)$,
computed on the interior of the $H$-dimensional simplex (full support). $H$
denotes the size of the classifier set considered and $H^{\ast}$ denotes the
size of the support set for $Q^{FP}_{\text{CH,KL}}$, the local minizer for the
bound $B_{\text{CH, KL}}$ in (16) in the main paper. We call $H^{\ast}$ as the
‘optimal support size’. $Q^{FP}_{\text{CH, KL}}(H^{\ast})$ was determined via
a linear search among the optimal posteriors with support on the increasing
ordered subsets of $\mathcal{H}$. $B^{solver}_{\text{CH,KL}}(H)$ and
$B^{FP}_{\text{CH,KL}}(H^{\ast})$ denote the bound values of the two
posteriors; and $T^{solver}_{\text{CH,KL}}(H)$ and
$T^{FP}_{\text{CH,KL}}(H^{\ast})$ denote their average test error rates. All
the computations were done with $\delta=0.01$. We notice that, in many
datasets (for example, Mammographic, Ionosphere and Banknote), $H^{\ast}=H$,
indicating that the local minimizer indeed has full support. These datasets
have low to moderate variance in the empirical risk values. Whereas the ones
with notably high variation in empirical risk values (namely, Spambase, Bupa,
Mammographic and Wdbc) have optimizers on a much smaller support size
($H^{\ast}\ll H$). Yet the difference in the bound values and test error rates
of the full support posterior, $Q^{solver}_{\text{CH, KL}}(H)$ and the local
minimizer $Q^{FP}_{\text{CH, KL}}(H^{\ast})$ is negligible ($O(10^{-6})$). If
we compare the posteriors themselves, the $\ell_{2}$-norm of the difference
between them is very small ($O(10^{-4})$). This suggests that the posteriors
lie within a small neighbourhood. Considering the computation time taken, we
observe that $Q^{FP}_{\text{CH, KL}}(H)$ with full support can be computed
within a fraction of a second, even with the linear search, whereas
computation for $Q^{solver}_{\text{CH, KL}}(H^{\ast})$ can take anywhere
between 0.223 seconds to 71.778 seconds depending on the model parameters –
$H,S_{m},\delta,\\{l_{i}\\}_{i=1}^{H}$. We can obtain a very close
approximation to $Q^{FP}_{\text{CH, KL}}(H^{\ast})$ by considering a full
support posterior obtained by minimizing $B_{\text{CH, KL}}(Q)$ in the
interior of the $H$-dimensional probability simplex.