Paper deep dive
A statistical approach to bias in zero-shot learning: the lens of handwriting recognition
Clarence Chew, Gim Siang Chia, Sukalpa Chanda, Subhroshekhar Ghosh, Soumendu Sundar Mukherjee
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 9/10/2026, 3:42:26 AM
Summary
This paper addresses the misclassification bias towards seen classes in Generalized Zero-Shot Learning (GZSL), particularly in the context of large-vocabulary handwritten word recognition. The authors propose a two-stage statistical framework: a first stage uses a classical GZSL feature learner (Pho(SC)Net) as a black box to generate embeddings, and a second stage employs an ensemble of lightweight Monte Carlo bias-correctors to estimate and correct the bias by predicting the training status (seen vs. unseen) of test data. This approach allows for debiased classification using statistical methods like nearest neighbor, logistic regression, and random forests. The method achieves over 20% relative accuracy improvement for unseen words and demonstrates that high-dimensional embeddings can be effectively reduced to ~15 dimensions without significant loss of information.
Entities (8)
Relation Signals (5)
Generalized Zero-Shot Learning → suffersfrom → misclassification bias towards seen classes
confidence 95% · Traditional GZSL techniques are limited by their applicability to a relatively small number of such unseen classes, scalability beyond which is challenging due to its well-known misclassification bias towards classes observed during training.
Proposed Method → achievesimprovementin → accuracy of unseen words
confidence 94% · We achieve relative accuracy improvements of over 20% in the classification of unseen words compared to established techniques.
Pho(SC)Net → usedin → Handwritten Word Recognition
confidence 93% · we leverage a structured word embedding paradigm, namely the so-called Pho(SC)Net [12]... Handwritten word images are mapped directly into this embedding space
Monte Carlo bias-correctors → corrects → misclassification bias towards seen classes
confidence 92% · Our method leverages a simple two-stage hierarchical architecture... ensemble of light-weight Monte Carlo based bias-correctors in the second, wherein the dual tasks of bias estimation and threshold calibration are performed.
Principal Component Analysis → reducesdimensionalityof → Pho(SC)Net embeddings
confidence 90% · Empirically, applying principal component analysis (PCA) reveals that the essential structure of the embedding space can be captured using only 15 dimensions.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Generalized zero-shot learning (GZSL) has emerged as an important paradigm for visual recognition systems that must generalize to classes that were not observed during training. Traditional GZSL techniques are limited by their applicability to a relatively small number of such unseen classes, scalability beyond which is challenging due to its well-known misclassification bias towards classes observed during training. In this work, we investigate the GZSL paradigm through the lens of zero-shot handwritten word recognition over extremely large vocabularies. We propose a statistical approach to rectifying this bias, which views any classical GZSL feature learner as a black box mechanism whose intrinsic bias in identifying the training status (seen vs. unseen) of a typical data point we aim to correct, similar to an out of distribution inferential problem. Our method leverages a simple two-stage hierarchical architecture, combining a classical GZSL blackbox in the first stage and an ensemble of lightweight Monte Carlo bias-correctors in the second. Once debiased, the classification of test data is undertaken only restricted to its predicted training status via well-founded statistical methods (eg nearest neighbour, logistic regression and random forests). We achieve relative accuracy improvements of over 20% in the classification of unseen words compared to established techniques. A key outcome is that word recognition over large scale vocabularies is amenable to a much lower dimensional representation (~15 dimensions). Our approach is underpinned by mathematical analysis that captures the essence of the statistical approach to bias correction. Our approach to bias rectification can be combined in a turn-key fashion with any classical GZSL learner as a blackbox, thereby suggesting a wide scope of applicability of this method for a wide variety of GZSL implementations in different domains.
Tags
Links
- Source: https://arxiv.org/abs/2609.10084v1
- Canonical: https://arxiv.org/abs/2609.10084v1
Trouble viewing inline? Open PDF directly →
Full Text
59,979 characters extracted from source content.
Expand or collapse full text
A statistical approach to bias in zero-shot learning: the lens of handwriting recognition Abstract Generalized zero-shot learning (GZSL) has emerged as an important paradigm for visual recognition systems that must generalize to classes that were not observed during training. Traditional GZSL techniques are limited by their applicability to a relatively small number of such unseen classes, scalability beyond which is challenging due to its well-known misclassification bias towards classes observed during training. In this work, we investigate the GZSL paradigm through the lens of zero-shot handwritten word recognition over extremely large vocabularies, which brings into sharp focus the central problem of inherent bias of GZSL methods towards the training data. We propose a statistical approach to rectifying this bias, which views any classical GZSL feature learner as a black box mechanism whose intrinsic bias is reflected in its ability to identify the training status (seen vs. unseen) of a typical data point, which may be viewed as an out of distribution inferential problem. Our method leverages a simple two-stage hierarchical architecture, combining a classical GZSL blackbox in the first stage and an ensemble of light-weight Monte Carlo based bias-correctors in the second, wherein the dual tasks of bias estimation and threshold calibration are performed. Once debiased, the classification of test data is undertaken only restricted to its predicted training status, using well-founded approaches with solid statistical underpinnings (such as nearest neighbour, logistic regression and random forests). In doing so, we can achieve relative accuracy improvements of over 20% in the classification of unseen words compared to established techniques. A key outcome of our investigations is that word recognition over large scale vocabularies can be well-represented by a much lower dimensional approximation (with as low as 15 dimensions), which renders practicable classical statistical methodologies as well as very large scale Monte Carlo techniques. Our approach is underpinned by mathematical analysis that captures the essence of the statistical approach to bias correction. It may be recognized that our statistical approach to bias rectification can be combined in a turn-key fashion with potentially any classical GZSL learner as a blackbox, thereby suggesting a wide scope of applicability of this method for a wide variety of GZSL implementations in different domains. Clarence Chew11 1 Lead author Department of Mathematics National University of Singapore clarence_chew_@nus.edu.sg Sukalpa Chanda Dept of Comp Sc & Comm Østfold University College sukalpa@ieee.org Soumendu Sundar Mukherjee Statistics and Mathematics Unit Indian Statistical Institute ssmukherjee@isical.ac.in Gim Siang Chia11footnotemark: 1 Department of Mathematics National University of Singapore e0310077@u.nus.edu Subhroshekhar Ghosh Department of Mathematics National University of Singapore subhrowork@gmail.com Contents 1 Introduction 2 Problem Formulation and Methodology 3 The Algorithmic Pipeline 4 Results & Discussion 5 Theoretical Underpinnings of Ensembling for Bias Reduction 6 Concluding Remarks 7 Acknowledgements References A Supporting Algorithms B Further Theoretical Details B.1 Why Use EmE_m over a Consensus Voting? B.2 Proofs of Various Results B.3 A Result under Exchangeability of the Predictors ψk _k 1 Introduction Generalized Zero-shot Learning (ZSL) has emerged as an important paradigm for visual recognition systems that must generalize to classes that were not observed during training [18]. In existing approaches, semantic relationships between classes are often captured through attribute annotations or language embeddings, with the ultimate objective of transferring knowledge from seen classes to unseen ones. Most existing work on zero-shot recognition has focused on object classification benchmarks such as Animals with Attributes (AwA), CUB-200, and SUN, where the number of unseen classes typically ranges from tens to a few hundred [5, 17, 15, 16]. A well-known issue with existing GZSL frameworks is a persistent bias towards seen classes, i.e. those classes whose data have been used for training the learning model [5]. This problem of inherent bias towards seen classes is brought into sharp focus in the substantially more challenging setting of zero-shot handwritten word recognition over extremely large vocabularies. Unlike object recognition datasets, where visual classes correspond to semantically meaningful object categories, handwritten word recognition operates over a combinatorial space of word forms. Even moderately sized vocabularies can contain thousands of distinct classes, and new word classes can be constructed through arbitrary combinations of characters. This fundamental difference introduces several challenges that are not present in conventional zero-shot object recognition. First, the number of potential classes is significantly larger, leading to a much denser and more complex class manifold. Second, visual differences between classes can be extremely subtle; words may differ by only a single character or by a small modification in stroke structure. Third, handwritten text exhibits substantial intra-class variation due to differences in writing style, stroke connectivity, and character spacing. Together, these factors make large-vocabulary zero-shot word recognition a significantly more difficult problem than standard object-level zero-shot classification [12, 4]. Most modern handwriting recognition systems rely on Connectionist Temporal Classification (CTC) based sequence models that predict character sequences [7]. While effective for transcription tasks, these models are known to exhibit several limitations which render them a structurally misaligned for zero-shot word recognition problems; these include segmentation difficulties, accumulation of errors across characters, and focus on local (as opposed to global) structures in complex words. To address these difficulties, we leverage a structured word embedding paradigm, namely the so-called Pho(SC)Net [12], the proposed new representation called Pyramidal Histogram of Shapes, captures both the positional information of characters and their visual shape appearance, making it more discriminative than traditional PHOC embeddings [12]. Handwritten word images are mapped directly into this embedding space, and recognition is performed by matching the predicted embedding against embeddings of candidate. Combined with a classical nearest neighbor classifier, this approach is known to prominently capture the well-known phenomenon of bias towards seen classes in GZSL, with accuracy rates for correct identification of unseen classes at a lowly 77% (compared to a seen class accuracy of around 93%) [12]. Our Contributions. In this paper, we investigate the problem of mitigating the inherent bias towards seen classes in GZSL through the prism of handwritten word recognition over large vocabularies. We propose a statistical approach to rectifying bias towards seen classes, which views any classical GZSL feature learner as a black box mechanism whose intrinsic bias is reflected in its ability (or lack thereof) to identify the training status (seen vs. unseen) of the class of a typical test data point. This latter issue may in fact be viewed as an out of distribution inferential problem; although in view of complete class identification (as opposed to mere training status), our problem is much more challenging and goes far beyond classical out of distribution learning. Our method leverages a simple two-stage hierarchical architecture, combining a classical GZSL feature learning blackbox in the first stage and an ensemble of light weight Monte Carlo based bias-correctors in the second. While the first stage may be envisaged to generate a structured embedding of a give data point, it is the second stage where the dual tasks of bias estimation and threshold calibration are performed. To wit, using a Monte Carlo aggregation approach, the classifiers in the second phase certify an input data point to from a seen class only if the proportion of seen certificates from the individual second stage classifiers crosses a suitable threshold that is calibrated to capture the inherent bias of the GZSL feature generator in the first stage. The overall output of this two stage architecture is thus two-fold: (i) the structured word embedding (from the first stage) and (i) a debiased training status predictor (seen/unseen) of the class of the input data point (from the second stage). Subsequent to processing via this two-stage architecture, the classification of test data is undertaken only restricted to its predicted training status, using well-founded approaches with solid statistical underpinnings (such as nearest neighbour classifiers, logistic regression and random forests). This design allows the system to dynamically restrict recognition to either seen or unseen candidate vocabularies, mitigating the well-known bias toward seen classes in generalized zero-shot learning. Our approach is well-motivated by an underpinning mathematical analysis that unveils the potential of such a method under a simplified analytical setup. A key observation augmenting our approach is a highly revealing geometric property of this embedding space. Although the structured word representation has dimensionality d=769d=769, we find that the embeddings produced by trained models lie on a remarkably low-dimensional manifold. Empirically, applying principal component analysis (PCA) reveals that the essential structure of the embedding space can be captured using only 15 dimensions. Despite this dramatic reduction in dimensionality, the resulting representations remain highly informative for distinguishing between thousands of word classes. This phenomenon suggests that the embedding space possesses a strong underlying geometric structure that can be exploited for recognition. In particular, we can leverage this property to construct highly lightweight classifiers that operate in the reduced-dimensional space to determine whether a predicted embedding corresponds to a word class observed during training. By combining structured word embeddings with a principled statistical approach to bias correction, the proposed framework enables recognition across vocabularies containing thousands of word classes, including a large number of unseen words. Augmented with dimensionality reduction leading to a parsimonious representation of the embedding manifold geometry, we are able to provide significant advances (relative improvements of over 20%) in accurately identifying unseen classes in the challenging problem of zero short handwritten word recognition, at a very manageable computational cost. The proposed method leverages the structured word embedding Pho(SC)Net as a black box, and can thus be potentially augmented in a turn-key fashion to any classical GZSL feature learning mechanism to achieve superior outcomes, especially for correct identification of unseen data categories. Related Work. Zero-shot learning (ZSL) has been studied extensively in object recognition, where models learns a mapping from seen to unseen categories through attributes or semantic embeddings [9, 11, 6, 13, 1]. In generalized zero-shot learning, inference during test phase involves recognition over both seen and unseen classes [5, 17, 15, 16]. While these methods have led to strong progress on benchmarks such as AwA, CUB, and SUN, the underlying setting typically involves tens or hundreds of semantically separated object classes. But Handwritten word recognition is fundamentally different: the label space is combinatorial, vocabularies can contain thousands of classes, and neighboring classes may differ by only a single character or minor stroke variation. This makes direct transfer of standard ZSL assumptions and methods non-trivial. Embedding-based word spotting and recognition. In many real-world applications such as searching large digital archives, it is customary to represent both word images and text strings in a shared embedding space, where retrieval can be performed via similarity-based matching. The PHOC representation introduced by Almazán et al. [2] is a foundational approach in this direction, enabling segmentation-free word spotting and lexicon-based recognition. Subsequent work showed that deep architectures can predict such embeddings effectively from word images [14, 8], and PHOC-style methods have remained attractive because they support lexicon search through nearest-neighbor matching rather than explicit sequence decoding. Zero-shot handwritten word recognition. Closer to our setting, recent work has explored zero-shot handwritten word recognition using structured embeddings that encode both character occurrence and shape information. Pho(SC)Net introduced a hybrid PHO(SC) representation for zero-shot word image recognition in historical documents, showing that shape-aware structured embeddings can improve generalization to unseen words [12]. Pho(SC)-CTC later combined these representations with a CTC-based decoding framework to improve recognition further [4]. These studies established structured word embeddings as a viable basis for zero-shot handwritten recognition, but they do not explicitly address the large-scale generalized setting in which test data contain both seen and unseen words and the model must manage the strong bias toward seen classes. 2 Problem Formulation and Methodology Problem Formulation. Let X denote a space of handwritten word images and W denote the corresponding vocabulary of word classes. Let →:x↦w(x)X wW:x w(x) denote a map taking the word image to the word class. Each word class w∈w is associated with an embedding vector e(w)∈ℝde(w) ^d. We partition the vocabulary into two disjoint sets =s∪uW=W_s _u, where sW_s represents the set of word classes available during training and uW_u represents unseen word classes that appear only during testing. The data points (in the form of handwritten word images) are envisaged to be generated from a distribution P on the space X. The training and test datasets are defined respectively as train=(xi,wi∣xi∈,wi=w(xi)∈s;D_train=\(x_i,w_i x_i ,\ w_i=w(x_i) _s\; test=(xj,wj)∣xj∈,wj∈s∪u.D_test=\(x_j,w_j) x_j ,\ w_j _s _u\. We learn a function fθ:→ℝdf_θ:X ^d, that maps a word image to a structured word embedding; suitably parametrized by θ which may symbolize, for instance, the weights of a neural network which may drive the predictor fθf_θ. Classically, recognition of a word is performed by nearest neighbor matching; in other words, w^(x)=argminw∈‖fθ(x)−e(w)‖ w(x)= _w \|f_θ(x)-e(w)\|. Methodology. Our framework consists of two phases: a first phase consisting of L copies of embedding models (M[1](k))k=1L(M_[1]^(k))_k=1^L, and a second phase comprising of seen/unseen classifiers ([M[2],i(k)]i=1nk)k=1L ( [M_[2],i^(k) ]_i=1^n_k )_k=1^L (nkn_k copies for each M[1](k)M_[1]^(k) from the first phase). Phase I: Embedding Models (M[1](k)M_[1]^(k)). Each embedding model learns a mapping M[1](k):→ℝdM_[1]^(k):X ^d that converts a word image into a structured embedding vector. The embedding encodes compositional properties of words including local letter shape descriptors, segment-level character presence and bigram statistics across different parts of a word. For each 1≤k≤L1≤ k≤ L, the model M[1](k)M_[1]^(k) is trained on a subset of the seen vocabulary s(k)⊂sW_s^(k) _s, while the remaining classes (i.e. s∪u∖s(k)W_s _u _s^(k)) are treated as unseen for the k-th model M[1](k)M_[1]^(k) from Phase I. Training 1≤k≤L1≤ k≤ L such models produces a diverse ensemble where each model has partial knowledge of the vocabulary. Phase I: Seen/Unseen Classifier (M[2],i(k)M_[2],i^(k)). Embedding models tend to be biased toward classes observed during training. In other words, the mis-identification error for the training status of a data point x (generated from the distribution P), captured by the quantity ℙ[w^(x)∈s(k)|w(x)∈u(k)]P[ w(x) _s^(k)|w(x) _u^(k)] is high (for comparison, in a perfect classification mechanism, this probability should be 0). We define the indicator random variables Zk(x):=[w(x)∈s(k)]Z_k(x):= 1[\w(x) _s^(k)\] and Z^k(x):=[M[1](k)(x)∈s(k)] Z_k(x):= 1[\M_[1]^(k)(x) _s^(k)\]. To mitigate bias, in Phase I we introduce an ensemble of nkn_k classifiers (for each fixed M[1](k)M_[1]^(k) from Phase I). At the fine-grained level, each (M[2],i(k))i=1nk (M_[2],i^(k) )_i=1^n_k is trained to learn the training category Zk(x)Z_k(x), with a 0-1 valued output Z^k,i(x) Z_k,i(x). The M[2],i(k)M_[2],i^(k)-s are typically trained using a (random) subset of the training data sW_s (say, around 80%). So their 0-1 valued outputs will be different and will embody their inherent randomness. In an unbiased scenario, a natural way to aggregate the Z^k,i(x) Z_k,i(x) would be to take a majority vote among the M[2],i(k)M_[2],i^(k)-s in order to determine the training status seen/unseen. But in view of the inherent bias of ZkZ_k towards being 1, we compute declare the training status as “seen” only if the total output (∑i=1nkZ^k,i(x)) ( _i=1^n_k Z_k,i(x) ) crosses a threshold thres (to be thought of as significantly higher than nk/2n_k/2). In practice, the choice of thres can reasonably be carried out via cross validation. Low Dimensional Approximation. For practical purposes, we can additionally modify the the scheme outlined above by using a low dimensional projection M[1](k)(x)M_[1]^(k)(x), via a standard dimension reduction methodology, such as Principal Component Analysis (PCA), and use this as an input to the Phase I classifiers (Π[M[2],i(k)])i=1nk ( [M_[2],i^(k)] )_i=1^n_k. The ability to operate on a low-dimensional problem makes each M[2],i(k)M_[2],i^(k) to be computationally light, which entails that we are able to deploy a very large number nkn_k of such classifiers leading to improved accuracy of the Monte Carlo method for estimation of training status. The trade-off is the approximation incurred due to working with the low-dimensional representation Π[M[1](k)(x)] [M_[1]^(k)(x)] instead of the full word embedding M[1](k)(x)M_[1]^(k)(x). Inference. Given an input word image x, we will compute a prediction for the word w(x)w(x) for each 1≤k≤L1≤ k≤ L, and subsequently aggregate these predictions. For a fixed k, the embedding model M[1](k)M_[1]^(k) in Phase I produces vk(x):=M[1](k)(x)v_k(x):=M_[1]^(k)(x). The (M[2],i(k))i=1nk (M_[2],i^(k) )_i=1^n_k ensemble predicts whether the embedding corresponds to a seen or unseen class (for that Phase I model M[1](k)M_[1]^(k). We denote this predicted training status as T^(k) T^(k), which can take two values – seen/unseen. If T^(k)=seen T^(k)=seen (resp., unseen), then the predicted word is the “best approximation” to M[1](k)(x)M_[1]^(k)(x) from the set s(k)W_s^(k) (resp. from the set ∖s(k)W _s^(k)). The “best approximation” above can be computed via nearest neighbour matching within the relevant subset of the vocabulary. For the seen class s(k)W_s^(k). This can optionally be substituted by a random forest or logistic regression based classifier trained on the corresponding data. Predictions for 1≤k≤L1≤ k≤ L are aggregated (via most frequent prediction, with ties being broken via nearest neighbour matching) to obtain the final word prediction. 3 The Algorithmic Pipeline DataAlgorithm 1M[1](k),M_[1]^(k),T,X,T,X,X′X Algorithm 4X^,M[2],i(k) X,M_[2],i^(k)Algorithm 5Xseen,X_seen,RF,RF,LRLRAlgorithm 2PredictionsAlgorithm 3FinalPredictionsSplit dataSynthetic data for M[2],−(k)M_[2],-^(k)Synthetic data for RF/LR(Optional)Prediction per M[1](k)M_[1]^(k)Combining predictions Figure 1: Schematic of the algorithmic pipeline for predicting words for IAM handwriting dataset We train the entire system of predicting w(x)w(x) in these stages: ∙ \,\, Training embedding model M[1](k)M_[1]^(k). Algorithm 1 does sample splitting by taking a subset of the 250-by-50 pixel images x with w(x)∈s(k)w(x) _s^(k). These splits are used to train M[1](k)M_[1]^(k). For the values of the splitting fractions, we typically take s≈0.1s≈ 0.1 and t≈0.7t≈ 0.7. ∙ \,\, Training ensemble seen/unseen classifier M[2],−(k)M_[2],-^(k). Algorithm 4 (c.f. Section A in the Appendix) is used to build a dataset to train one ensemble of M[2],−(k)M_[2],-^(k) models for each k. The dataset includes two parts: synthetic data ‘far’ from the seen classes as unseen examples, and remaining training data (X,X′X,X ) not used for training M[1](k)M_[1]^(k). Each M[2],i(k)M_[2],i^(k) is a is a neural network that is trained with 80% of the dataset, so that each M[2],i(k)M_[2],i^(k) in the ensemble produces meaningfully different results that can be combined. This ensemble predicts if the M[1](k)M_[1]^(k) has been trained on the word, i.e. w(x)∈s(k)w(x) _s^(k), given M[1](k)(x)M_[1]^(k)(x). ∙ \,\, (Optional) Training word predictor. Algorithm 5 (c.f. Section A in the Appendix) produces a dataset with two parts: training data with words in s(k)W_s^(k) that were not used to train M[1](k)M_[1]^(k), and synthetic data. This is used for training a random forest (RF) or logistic regression (LR) model that could predict the word among s(k)W_s^(k) (RF or LR could replace nearest-neighbour matching). ∙ \,\, Word prediction from single M[1](k)M_[1]^(k). Algorithm 2 produces a prediction for each M[1](k)M_[1]^(k) for the images in the test set. We use M[1](k)(x)M_[1]^(k)(x) to get the estimated feature vector, then use M[2],−(k)M_[2],-^(k) to predict whether w(x)∈s(k)w(x) _s^(k). If it is predicted that w(x)∈s(k)w(x) _s^(k), then Algorithm 6 (c.f. Section A in the Appendix) does nearest-neighbour matching among s(k)W_s^(k) (or uses the random forest/logistic regression) to give a prediction for the word. If it If is predicted that w(x)∈∖s(k)w(x) _s^(k), then nearest-neighbour matching among ∖s(k)W _s^(k) is used. ∙ \,\, Aggregate word prediction from all M[1](k)M_[1]^(k). Algorithm 3 takes the prediction from each M[1](k)M_[1]^(k) to form a final prediction. Algorithm 3 does this by taking the most frequent prediction, breaking ties by nearest-neighbour matching of M[1](k)(x)M_[1]^(k)(x). To train the M[1](k)M_[1]^(k)s in Algorithm 1, we use the same PhoS and PhoC vectors given in the original Pho(SC)Net approach [4]. In particular, for each of 8407 words, we form a 769-dimensional word embedding vector as follows: ∙ \,\, Shapes: The word is split into 1 to 5 parts (for 15 parts in total), each with 11 dimensions representing the shapes of the letters, for a total of 165 dimensions ∙ \,\, Letters: The word is split into 2 to 5 parts (for 14 parts in total), each with 36 dimensions representing letters appearing in that part, for a total of 504 dimensions ∙ \,\, Bigrams: The word is split into halves, each with 50 dimensions representing bigrams, for a total of 100 dimensions Algorithm 1 Producing dataset splits and training M[1](k)M_[1]^(k) Input: trainD_train, the training data; s,t∈(0,1)s,t∈(0,1), the data splitting fractions. Output: M[1](k),T,X,X′M_[1]^(k),T,X,X , where T represents the reduced training data for M[1](k)M_[1]^(k), X will be the ‘seen’ training data for M[2],i(k)M_[2],i^(k), and X′X will be the ‘unseen’ training data for M[2],i(k)M_[2],i^(k) 1: In trainD_train, we randomly select the fraction s of the labels to be denoted as unseen, then filter out the training data with such labels and name the resulting dataframe X′X . 2: We further split the remaining train ′D_train X , into t:(1−t)t:(1-t) based on per-class splitting, naming the fraction t split as T, and the fraction 1−t1-t split as X. 3: Train M[1](k)M_[1]^(k) on T. 4: return M[1](k),T,X,X′M_[1]^(k),T,X,X . Algorithm 2 Predicting classes for each M[1](k)M_[1]^(k) Input: d a test datapoint, M[1](k),M[2],−(k),s(k),u(k)M_[1]^(k),M_[2],-^(k),W_s^(k),W_u^(k), thres a threshold Output: Predictions[k] and F[k]F[k], prediction for word class and feature vector (resp.) for d from M[1](k)M_[1]^(k); 1: F[k]←M[1](k)()F[k]← M_[1]^(k)( d) ⊳ Predicted feature vector 2: count ← number of M[2],−(k)M_[2],-^(k) that predict F corresponds to a ‘seen’ class (i.e., in s(k)W_s^(k)) 3: if count ≥ thres then 4: Use Algorithm 6 to predict class of F among s(k)W_s^(k); store class to Predictions[k] 5: else 6: Predictions[k][k] ← nearest distance class from u(k)W_u^(k) ⊳ Predicted word class 7: end if 8: return Predictions[k], F[k]F[k] Algorithm 3 Combining predictions Input: d a test datapoint, all the F[−]F[-], Predictions[−-] (via Alg. 2) Output: Final_Prediction, a finalized word prediction for d 1: List the most frequent labels among Predictions[−-] 2: if there is a unique most frequent label then 3: Final_Prediction ← the unique most frequent label 4: else 5: For each of the most frequent labels c=c=Predictions[l], compute ‖e(c)−F[l]‖\|e(c)-F[l]\| 6: Let c∗=argminc‖e(c)−F[l]‖c^*=argmin_c\|e(c)-F[l]\| in the above step 7: Final_Prediction ←c∗← c^* 8: end if 9: return Final_Prediction 4 Results & Discussion The IAM handwriting data [10] consists of 250250 pixel by 5050 pixel images of handwritten words, each which are one of 8407 words. 7898 of the words are given in the training set, while the other 509 words are kept as unseen classes. The task is to determine which of 8407 words is written. We store the accuracy on unseen classes AuA_u, accuracy on seen classes AsA_s. We compute the harmonic mean h:=2AsAuAs+Auh:= 2A_sA_uA_s+A_u to measure performance at both prediction tasks. As an alternate metric of effectiveness, we also investigate the balanced accuracy Ab:=min(Au,As)A_b:= (A_u,A_s). The original Pho(SC)Net approach involved training a model to predict the feature vector for image handwriting samples. As the table shows, there is a bias towards predicting seen classes, with significantly lower unseen class accuracy (0.77) than seen class accuracy (0.93). The other experiments are improvements over the original Pho(SC)Net approach via the paradigm of using many small models M[2],−(k)M_[2],-^(k) to determine if the feature vector corresponds to a seen class s(k)W_s^(k) or an unseen class u(k)W_u^(k). Afterwards, a threshold count ‘thres’ (in Algorithm 2) is chosen. If there are more models which report the feature vector as seen, compared to ‘thres’, the feature vector is considered seen, and prediction will only be done among seen classes. ‘thres’ was roughly chosen to maximize h, the harmonic mean of the unseen and seen accuracy. Table 1: Implementation details L nkn_k Dim. for M[2]M_[2] thres for h thres for AbA_b M[1]M_[1] (Original Pho(SC)Net) [4] 1 −- −- −- −- (21)M[1]+50M[2]M_[1]+50M_[2] (769 dim, N) 21 50 769 49 49 (5)M[1]+500M[2]M_[1]+500M_[2] (30 dim, N) 5 500 30 445 430 (5)M[1]+500M[2]M_[1]+500M_[2] (15 dim, N) 5 500 15 440 400 (5)M[1]+500M[2]M_[1]+500M_[2] (15 dim, RF) 5 500 15 425 405 (5)M[1]+500M[2]M_[1]+500M_[2] (15 dim, LR) 5 500 15 435 420 Table 2: Experimental results on handwritten test dataset AuA_u AsA_s h AbA_b M[1]M_[1] (Original Pho(SC)Net) [4] 0.77 0.93 0.84 −- (21)M[1]+50M[2]M_[1]+50M_[2] (769 dim, N) 0.931 0.903 0.917 0.903 (5)M[1]+500M[2]M_[1]+500M_[2] (30 dim, N) 0.916 0.857 0.886 0.877 (5)M[1]+500M[2]M_[1]+500M_[2] (15 dim, N) 0.905 0.850 0.877 0.864 (5)M[1]+500M[2]M_[1]+500M_[2] (15 dim, RF) 0.905 0.847 0.875 0.867 (5)M[1]+500M[2]M_[1]+500M_[2] (15 dim, LR) 0.900 0.829 0.863 0.847 We consider class selection methods: nearest-neighbour (N), random forest (RF) and logistic regression (LR). (21)M[1]+50M[2]M_[1]+50M_[2] (769 dim, N) is trained without dimension reduction, and achieves the best performance, with the highest h=0.917h=0.917. Each M[2],i(k)M_[2],i^(k) has 10 ReLU hidden layers of 256 nodes. Figure 2: Plot of cumulative sum of eigenvalues, ROCs for ensemble M[2],−(k)M_[2],-^(k) model We can consider the covariance matrix of the class embedding vectors. We see that the top 15 eigenvalues account for 0.6224 of the sum of all eigenvalues while the top 30 eigenvalues account for 0.7592 of the sum of all eigenvalues. Figure 2 shows the the sum of largest eigenvalues of the covariance matrix, as a fraction the sum of all the eigenvalues of the covariance matrix. The ROCs for the ensemble M[2],−(k)M_[2],-^(k) model (for each k) are computed by weighting the test set, to give equal total weight to the tests where w(x)∈sw(x) _s, and the tests where w(x)∈uw(x) _u, of which there are a significantly different number of both tests. The ensembles used here were of 500 30-dimensional M[2],i(k)M_[2],i^(k). We can see the 5 different ensembles have very similar curves. For both (5)M[1]+500M[2]M_[1]+500M_[2] (15 dim, N) and (5)M[1]+500M[2]M_[1]+500M_[2] (30 dim, N), each M[2],i(k)M_[2],i^(k) has 10 ReLU hidden layers of 32 nodes. (5)M[1]+500M[2]M_[1]+500M_[2] (15 dim, RF). It is the same as (5)M[1]+500M[2]M_[1]+500M_[2] (15 dim, N), but we add a RF, trained on 15-dimensional representations with scikit-learn with a depth of 10. The seen RF turns out to be 5GB per M1. One limitation is that the computational cost is intensive in the height of the tree. (5)M[1]+500M[2]M_[1]+500M_[2] (15 dim, LR). It is the same as (5)M[1]+500M[2]M_[1]+500M_[2] (15 dim, N), but we add a LR, trained on 15-dimensional representations with scikit-learn with 1000 iterations. One limitation is numerical stability. All the variations of our proposed methodology provide a significant improvement over the Pho(SC)Net (c.f. Table 2). In particular, for the crucial problem of unseen class detection, we are able achieve an accuracy improvement of 0.931 (from 0.77). The overall GZSL accuracy (h) also improves 0.917 from 0.84. While the (21)M[1]+50M[2]M_[1]+50M_[2] ensemble approach is expectedly the most accurate (h=0.917h=0.917), the other approaches involving dimension reduction are also much more accurate than the original Pho(SC)Net. Thus, low-dimensional ensemble approaches provide a computationally lighter alternative to reduce bias for practical applications in various GZSL problems. Note: All the data analyses reported in this section were conducted on a shared compute cluster with 1 NVIDIA A40 (48GB), 36 cores Intel 9452Y CPUs and 256GB RAM. The most expensive computation, (21)M[1]+50M[2]M_[1]+50M_[2] (769 dimensions, N) took approximately a week of compute, whereas the other experiments can be run in 3 days, for a total of roughly 3 weeks of compute. 5 Theoretical Underpinnings of Ensembling for Bias Reduction In this section, we theoretically justify the idea of using an ensembling strategy for reducing the bias towards seen classes by considering a simplified model which is amenable to mathematical analysis. Suppose we have a dataset consisting of pairs (xi,wi)(x_i,w_i), where each wi∈sw_i _s. Suppose we have L binary predictors ψk _k, 1≤k≤L1≤ k≤ L, where ψk _k is trained on a subset of the available data by restricting to certain class labels s(k)⊂sW^(k)_s _s. Given an new observation (x,w)(x,w), ψk _k is supposed to identify whether the true class label w of x is from among the classes it has seen during its training. As such it gives binary outputs ‘seen’ or ‘unseen’. We shall assume that s=∪k=1Ls(k)W_s= _k=1^LW_s^(k). Then u=∖sW_u=W _s are the common unseen classes. We note here that by sample splitting, one may ensure that the predictors ψk _k are independent (albeit at the loss of some efficiency). In the supplementary material, we analyse the case where the ψk _k’s are only assumed to be exchangeable. A simple example of such binary predictors would be as follows. For each k, we fit a Gaussian mixture model to the corresponding training data. Denoting by ϕ^k φ_k the fitted the probability density function, we declare ψk(x)=‘unseen’ _k(x)=`unseen' if ϕ^k φ_k has a ‘low’ value at x. Let us introduce shorthands for the ‘Type 1’ and ‘Type 2’ errors of the binary predictors: αk:=ℙ(ψk(x)=‘unseen’∣w∈s(k)),βk:=ℙ(ψk(x)=‘seen’∣w∉s(k)). _k:=P( _k(x)=`unseen' w _s^(k)), _k:=P( _k(x)=`seen' w _s^(k)). We shall assume that αk+βk≤1 _k+ _k≤ 1. Indeed, a random predictor has αk+βk=1 _k+ _k=1, so we are assuming the predictor ψk _k to be no worse than random. Now let EmE_m be the ensemble predictor that outputs ‘seen’ if and only if at least m of the classifiers ψk _k output ‘seen’. We shall show that for appropriate choices of m, EmE_m achieves high accuracy in classifying both ‘seen’ and ‘unseen’ classes. We shall present our results on the accuracy of EmE_m under two different class-allocation mechanisms. (i) Arbitrary allocation. Seen classes are assigned to s(k)W_s^(k) in some arbitrary manner. (i) Random allocation. Each seen class w∈sw _s is included in s(k)W_s^(k) with probability p>0p>0, and this procedure is repeated independently across k. We define a few key quantities to state our results. For w′∈sw _s, let ℒ(w′):=k∣w′∈s(k)L(w ):=\k w _s^(k)\. Let γk:=1−αk−βk≥0 _k:=1- _k- _k≥ 0, Δ(w′):=∑k∈ℒ(w′)γk (w ):= _k (w ) _k and Δ:=minw′∈sΔ(w′) := _w _s (w ). Theorem 1 (Arbitrary allocation). Assume that γk>0 _k>0 for all k∈[L]k∈[L], so that Δ>0 >0, Then, for m=⌈μ(1+δ)⌉m= μ(1+δ) , where μ=∑k∈[L]βkμ= _k∈[L] _k and δ=Δ2μ+Δδ= 2μ+ , we have ℙ(Em(x)=‘unseen’∣w∈s)≤e−δ2(μ+Δ)2,P(E_m(x)=`unseen' w _s)≤ e^- δ^2(μ+ )2, ℙ(Em(x)=‘seen’∣w∈u)≤e−δ2μ2+δ.P(E_m(x)=`seen' w _u)≤ e^- δ^2μ2+δ. When Δ is bounded away from zero, and μ=Θ(L)μ= (L), we see from Theorem 1 that EmE_m is able to classify both seen and unseen classes with high accuracy. Theorem 2 (Random allocation). Let Δ0>0 _0>0 be a deterministic threshold. For m=⌈μ(1+δ)⌉m= μ(1+δ) , where μ=∑k∈[L]βkμ= _k∈[L] _k and δ=Δ02μ+Δ0δ= _02μ+ _0, we have ℙ(Em(x)=‘unseen’∣w∈s) (E_m(x)=`unseen' w _s) ≤ℙ(Δ<Δ0)+[e−δ2(μ+Δ0)/2], ( < _0)+E [e^-δ^2(μ+ _0)/2 ], ℙ(Em(x)=‘seen’∣w∈u) (E_m(x)=`seen' w _u) ≤ℙ(Δ<Δ0)+[e−δ2μ/(2+δ)]. ( < _0)+E [e^-δ^2μ/(2+δ) ]. If we further assume that the αk _k’s and the βk _k’s are statistically independent of the class allocation mechanism, then, with η∈(0,1)η∈(0,1) and Δ0:=(1−η)p∑k∈[L]γk _0:=(1-η)p _k∈[L] _k, we have ℙ(Em(x)=‘unseen’∣w∈s) (E_m(x)=`unseen' w _s) ≤|s|e−2η2p2(∑k∈[L]γk)2∑k∈[L]γk2+e−δ2(μ+Δ0)/2, ≤|W_s|e^- 2η^2p^2( _k∈[L] _k)^2 _k∈[L] _k^2+e^-δ^2(μ+ _0)/2, ℙ(Em(x)=‘seen’∣w∈u) (E_m(x)=`seen' w _u) ≤|s|e−2η2p2(∑k∈[L]γk)2∑k∈[L]γk2+e−δ2μ/(2+δ). ≤|W_s|e^- 2η^2p^2( _k∈[L] _k)^2 _k∈[L] _k^2+e^-δ^2μ/(2+δ). We see that random allocations, assuming independence of the αk _k’s and the βk _k’s from the allocation scheme, the ensemble classifier EmE_m is able to identify both seen and unseen classes with high accuracy, if μ is large, δ is bounded away from 00, and (∑k∈[L]γk)2∑k∈[L]γk2 ( _k∈[L] _k)^2 _k∈[L] _k^2 is large. For instance, if we assume a uniform lower bound γk=1−αk−βk≥ε>0 _k=1- _k- _k≥ >0, then Δ0≥(1−η)pεL _0≥(1-η)p L and (∑k=1Lγk)2∑k=1Lγk2≥ε2L ( _k=1^L _k)^2 _k=1^L _k^2≥ ^2L. We can see Algorithm 3 using multiple predictions to form a single prediction by taking the most common-occurring prediction. Each M[1](k)M_[1]^(k) is biased towards predicting words in s(k)W_s^(k), affecting the accuracy of words in ∖s(k)W _s^(k), especially words not in the training set (in uW_u). In our approach, multiple M[1](k)M_[1]^(k) trained on different s(k)W_s^(k) give some robustness against an incorrect prediction for words inside uW_u. 6 Concluding Remarks In this work, we have devised a novel methodology for rectifying the inherent bias toward seen classes in genralised zero shot learning in the context of handwritten word recognition. Broadly speaking, it is a statistical methodology based on an ensembling strategy that leverages a two stage architecture, with the second stage explicitly focusing on bias mitigation. The proposed method is very general and can in principle be augmented to any classical GZSL learner in a turn-key fashion to implement bias correction. The present work is focused on the handwritten word recognition appplication, and extensions of this approach to other GZSL scenarios is a natural area for follow-up investigation. We provide a foundational theoretical structure to complement our methodology, and extensions of this theory to cover wider application domains and weaker hypothesis setups is another natural direction of research. 7 Acknowledgements The authors would like to acknowledge that computational work involved in this research work is partially supported by NUS IT’s Research Computing group using grant number NUSREC-HPC-00001. SG was supported in part by the NUS Dean’s Chair Associate Professorship E-146-00-0037-01 and the Singapore MOE grants A-8002014-00-00 and A-8003802-00-00. References [1] Z. Akata, S. Reed, D. Walter, H. Lee, and B. Schiele (2015) Evaluation of output embeddings for fine-grained image classification. In 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), p. 2927–2936. External Links: Document Cited by: §1. [2] J. Almazán, A. Gordo, A. Fornés, and E. Valveny (2014) Word spotting and recognition with embedded attributes. IEEE Transactions on Pattern Analysis and Machine Intelligence 36 (12), p. 2552–2566. External Links: Document Cited by: §1. [3] R. F. Barber (2024) Hoeffding and bernstein inequalities for weighted sums of exchangeable random variables. Electronic Communications in Probability. External Links: Link Cited by: §B.3. [4] R. Bhatt, A. Rai, N. C. Krishnan, and S. Chanda (2022) Pho(sc)-CTC: a hybrid approach towards zero-shot word image recognition in historical documents. International Journal on Document Analysis and Recognition (IJDAR) 25 (4), p. 357–374. External Links: Document Cited by: §1, §1, §3, Table 1, Table 2. [5] W. Chao, S. Changpinyo, B. Gong, and F. Sha (2016) An empirical study and analysis of generalized zero-shot learning for object recognition in the wild. In European Conference on Computer Vision (ECCV), p. 52–68. External Links: Document Cited by: §1, §1, §1. [6] A. Frome, G. S. Corrado, J. Shlens, S. Bengio, J. Dean, T. Mikolov, et al. (2013) DeViSE: a deep visual-semantic embedding model. In Advances in Neural Information Processing Systems 26 (NeurIPS 2013), p. 2121–2129. Cited by: §1. [7] A. Graves, S. Fernández, F. Gomez, and J. Schmidhuber (2006) Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks. In Proceedings of the 23rd International Conference on Machine Learning (ICML), p. 369–376. External Links: Document Cited by: §1. [8] P. Krishnan, K. Dutta, and C. V. Jawahar (2016) Deep feature embedding for accurate recognition and retrieval of handwritten text. In 2016 15th International Conference on Frontiers in Handwriting Recognition (ICFHR), p. 289–294. External Links: Document Cited by: §1. [9] C. H. Lampert, H. Nickisch, and S. Harmeling (2009) Learning to detect unseen object classes by between-class attribute transfer. In 2009 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), p. 951–958. External Links: Document Cited by: §1. [10] U.-V. Marti and H. Bunke (2002) The iam-database: an english sentence database for offline handwriting recognition. International Journal on Document Analysis and Recognition 5 (1), p. 39–46. External Links: ISSN 1433-2825, Link, Document Cited by: §4. [11] M. Palatucci, D. Pomerleau, G. E. Hinton, and T. M. Mitchell (2009) Zero-shot learning with semantic output codes. In Advances in Neural Information Processing Systems 22 (NeurIPS 2009), p. 1410–1418. Cited by: §1. [12] A. Rai, N. C. Krishnan, and S. Chanda (2021) Pho(sc)net: an approach towards zero-shot word image recognition in historical documents. In Document Analysis and Recognition – ICDAR 2021 Workshops, Lecture Notes in Computer Science, Vol. 12918, p. 17–30. External Links: Document Cited by: §1, §1, §1. [13] R. Socher, M. Ganjoo, C. D. Manning, and A. Ng (2013) Zero-shot learning through cross-modal transfer. In Advances in Neural Information Processing Systems 26 (NeurIPS 2013), p. 935–943. Cited by: §1. [14] S. Sudholt and G. A. Fink (2017) Evaluating word string embeddings and loss functions for CNN-based word spotting. In 2017 14th IAPR International Conference on Document Analysis and Recognition (ICDAR), p. 915–920. External Links: Document Cited by: §1. [15] V. K. Verma, G. Arora, A. Mishra, and P. Rai (2018) Generalized zero-shot learning via synthesized examples. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), p. 4281–4289. External Links: Document Cited by: §1, §1. [16] V. K. Verma, D. Brahma, and P. Rai (2020) Meta-learning for generalized zero-shot learning. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34, p. 6062–6069. External Links: Document Cited by: §1, §1. [17] Y. Xian, C. H. Lampert, B. Schiele, and Z. Akata (2019) Zero-shot learning—a comprehensive evaluation of the good, the bad and the ugly. IEEE Transactions on Pattern Analysis and Machine Intelligence 41 (9), p. 2251–2265. External Links: Document Cited by: §1, §1. [18] Y. Xian, B. Schiele, and Z. Akata (2016) An empirical study and analysis of generalized zero-shot learning for object recognition in the wild. In European Conference on Computer Vision (ECCV), p. 52–68. Cited by: §1. Appendix A Supporting Algorithms Algorithm 4 is used to generate unseen data for M[2],−(k)M_[2],-^(k). This is run after Algorithm 1 and before Algorithm 2. This uses the datasets X,X′X,X (which were not used to train M[1](k)M_[1]^(k)) as well as additional synthetic data. Algorithm 4 Synthetically generating unseen data for M[2],−(k)M_[2],-^(k) Input: M[1](k),X,X′,L,RM_[1]^(k),X,X ,L,R ⊳ L and R are the lower and upper bounds of the extremes respectively Output: X X, consisting of feature vectors derived from X∪X′X∪ X and synthetically generated data 1: N←N← length(X∪X′X∪ X ) ⊳ number of instances to generate 2: dim ← size of feature vector 3: Initialize datasets Z,Z′Z,Z 4: for each XiX_i of X do 5: Z[i]←M[1](k)(Xi)Z[i]← M_[1]^(k)(X_i) ⊳ Z contains feature vectors of X, predicted by M[1](k)M_[1]^(k) 6: end for 7: for each Xi′X _i of X′X do 8: Z′[i]←M[1](k)(Xi′)Z [i]← M_[1]^(k)(X _i) ⊳ Z′Z contains the feature vectors of X′X , predicted by M[1](k)M_[1]^(k) 9: end for 10: Calculate mean (μ) and standard deviation (σ) for each coordinate of feature vectors in Z. 11: X′^← X ← array(N, dim) ⊳ Store the feature vectors of the synthetically generated training unseen, used to train M[2],−(k)M_[2],-^(k). 12: for each X′[i]X [i] of X′X do 13: 95% of the coordinates of X′^[i] X [i] are given an extreme sample ⊳ from ≤L≤ L% quantile or ≥R≥ R% quantile of N(μj,σj)N( _j, _j). 14: The rest 5% of coordinates of X′^[i] X [i] are given middle samples ⊳ from between L%L\% quantile and R%R\% quantile of N(μj,σj)N( _j, _j). 15: end for 16: return a dataframe X X that consists of Z,Z′Z,Z and X′ X , attaching 11 to the feature vectors of Z, and 00 to Z′,X′^Z , X . ⊳ 11 means it is seen, 00 means it is unseen. Algorithm 5 (optional) is used to generate data for random forest/logistic regression approaches. This is run after Algorithm 1 and before Algorithm 2. This uses the dataset X (which was not used to train M[1](k)M_[1]^(k)) as well as additional synthetic data. Algorithm 5 Synthetically generating seen data for random forest/logistic regression Input: M[1](k)M_[1]^(k), X. Output: Dataset XseenX_seen for training random forest 1: m←m← maximum number of training samples among s(k)W_s^(k) in X 2: D stores differences between feature vectors and the corresponding class 3: for each XiX_i in X do 4: F←M[1](k)(Xi)F← M_[1]^(k)(X_i) 5: Add feature vector F and class w(Xi)w(X_i) to XseenX_seen 6: Add the difference F−e(w(Xi))F-e(w(X_i)) to D 7: end for 8: for each class c∈s(k)c _s^(k) do 9: while class has <m<m samples do 10: v←v← Uniform sample from D 11: Add v+e(c)v+e(c) and class to XseenX_seen. 12: end while 13: end for 14: return XseenX_seen Algorithm 6 is used to apply the random forest/logistic regression (if available) otherwise it applies the nearest-neighbour approach. This is run during Algorithm 2. Algorithm 6 Predict class of feature vector among seen classes Input: F a feature vector, s(k)W_s^(k), RFRF an optional random forest, LRLR an optional logistic regression. Output: Class prediction for feature vector 1: if RFRF available then 2: return RF(F)RF(F) 3: else if LRLR available then 4: return LR(F)LR(F) 5: else 6: return nearest distance class from s(k)W_s^(k) 7: end if Appendix B Further Theoretical Details B.1 Why Use EmE_m over a Consensus Voting? To remove the bias toward seen classes, the simplest ensembling method that comes to mind is to declare the class of a new example as ‘seen‘ if all the classifiers ψk _k call it ‘seen’. Let us call this consensus voting rule Eall(x)E_all(x). Then, assuming independence of the predictors ψk _k, it follows that ℙ(Eall(x)=‘unseen’∣w∈u) (E_all(x)=`unseen' w _u) =1−∏k∈[L]βk≥1−βL, =1- _k∈[L] _k≥ 1-β^L, provided a mild upper bound βk≤β<1 _k≤β<1 holds on the Type I errors of the predictors. Thus the consensus rule EallE_all is able to remove the bias toward ‘seen’ classes. However, it is too stringent when it comes to correctly identifying ‘seen’ classes. Recall that ℒ(w):=k∣w∈s(k)L(w):=\k w _s^(k)\ and set ℓ(w):=#ℒ(w) (w):=\#L(w). In other words, ℓ(w) (w) many predictors had w as a seen class in their training sets. Then, ℙ(Eall(x)=‘seen’|w∈s) (E_all(x)=`seen'|w _s) =ℙ(all ψk call x seen) =P(all _k call x seen) =∏k:w∈s(k)(1−αk)∏k:w∉s(k)βk = _k:w _s^(k)(1- _k) _k:w _s^(k) _k ≥(1−α)ℓ(w)βL−ℓ(w), ≥(1-α) (w)β^L- (w), where the last inequality holds if αk≤α _k≤α and βk≥β _k≥β for each k∈[L]k∈[L]. The takeaway is that the accuracy in identifying ‘seen’ classes can be quite far from 11. The above computation suggests the use of a less stringent voting rule such as EmE_m with an appropriate choice of m. B.2 Proofs of Various Results Recall that Δ(w):=∑k∈ℒ(w)γk,Δ:=minw∈sΔ(w). (w):= _k (w) _k, := _w _s (w). Proof of Theorem 1. Let X:=∑k∈[L](ψk(x)=‘seen’).X:= _k∈[L] 1( _k(x)=`seen'). Then X is a sum of independent Bernoulli random variables. Note that μs:=[X∣w∈s] _s:=E[X w _s] =∑k∈ℒ(w)(1−αk)+∑k∈[L]∖ℒ(w)βk = _k (w)(1- _k)+ _k∈[L] (w) _k =∑k∈ℒ(w)(1−αk−βk)+∑k∈[L]βk = _k (w)(1- _k- _k)+ _k∈[L] _k =Δ(w)+μ = (w)+μ ≥Δ+μ. ≥ +μ. On the other hand, μu:=[X∣w∈u] _u:=E[X w _u] =∑k∈[L]βk=μ = _k∈[L] _k=μ For our choice of δ, it may be seen that (1+δ)μ=2μ(μ+Δ)2μ+Δ≤2μμs2μ+Δ=(1−δ)μs.(1+δ)μ= 2μ(μ+ )2μ+ ≤ 2μ _s2μ+ =(1-δ) _s. Applying the Chernoff bounds, we have ℙ(Em(x)=‘unseen’∣w∈s) (E_m(x)=`unseen' w _s) =ℙ(X<m∣w∈s) =P(X<m w _s) =ℙ(X<(1+δ)μ∣w∈s) =P(X<(1+δ)μ w _s) ≤ℙ[X<(1−δ)μs|w∈s] [X<(1-δ) _s|w _s] ≤e−δ2μs/2. ≤ e^-δ^2 _s/2. Again by the Chernoff bounds, ℙ(Em(x)=‘seen’∣w∉s) (E_m(x)=`seen' w _s) =ℙ(X≥m∣w∈u) =P(X≥ m w _u) =ℙ(X≥(1+δ)μ∣w∈u) =P(X≥(1+δ)μ w _u) ≤e−δ2μ/(2+δ). ≤ e^-δ^2μ/(2+δ). This completes the proof. ∎ Proof of Theorem 2. We note that under the random allocation model, the indicators Xw,k:=(w∈s(k))X_w,k:= 1(w ^(k)_s) are i.i.d. Ber(p)Ber(p) random variables. Now Δ(w)=∑k∈[L]γkXw,k, (w)= _k∈[L] _kX_w,k, where γk=1−αk−βk _k=1- _k- _k. Note that the γk _k’s a priori depend on the allocated classes :=(s(k))k∈[L]A:=(W^(k)_s)_k∈[L]. Given an allocation A, we may repeat the argument used in the proof of Theorem 1. Let Δ0 _0 denote a deterministic threshold such that ℙ(Δ≤Δ0)P( ≤ _0) is small. Then, with δ=Δ02μ+Δ0δ= _02μ+ _0 and m=⌈μ(1+δ)⌉m= μ(1+δ) , we have ℙ(Em(x)=‘unseen’∣w∈s) (E_m(x)=`unseen' w _s) =[ℙ(Em(x)=‘unseen’∣w∈s,)] =E [P(E_m(x)=`unseen' w _s,A) ] =[ℙ(Em(x)=‘unseen’∣w∈s,)(Δ<Δ0)] =E [P(E_m(x)=`unseen' w _s,A) 1( < _0) ] +[ℙ(Em(x)=‘unseen’∣w∈s,)(Δ≥Δ0)] +E [P(E_m(x)=`unseen' w _s,A) 1( ≥ _0) ] ≤ℙ(Δ<Δ0)+[e−δ2(μ+Δ0)/2]. ( < _0)+E [e^-δ^2(μ+ _0)/2 ]. Similarly, ℙ(Em(x)=‘unseen’∣w∈s) (E_m(x)=`unseen' w _s) ≤ℙ(Δ<Δ0)+[e−δ2μ/(2+δ)]. ( < _0)+E [e^-δ^2μ/(2+δ) ]. If we further assume that the αk _k’s and the βk _k’s do not depend on the class allocations A, then the Δ(w) (w)’s are independent random variables, and hence by Hoeffding’s inequality, for any η∈(0,1)η∈(0,1), ℙ(Δ(w)≤(1−η)p∑k∈[L]γk) ( (w)≤(1-η)p _k∈[L] _k ) =ℙ(Δ(w)≤(1−η)[Δ(w)]) =P( (w)≤(1-η)E[ (w)]) ≤exp(−2η2p2(∑k∈[L]γk)2∑k∈[L]γk2). ≤ (- 2η^2p^2( _k∈[L] _k)^2 _k∈[L] _k^2 ). It follows by a union bound that ℙ(Δ≤(1−η)p∑k∈[L]γk)≤|s|exp(−2η2p2(∑k∈[L]γk)2∑k∈[L]γk2).P ( ≤(1-η)p _k∈[L] _k )≤|W_s| (- 2η^2p^2( _k∈[L] _k)^2 _k∈[L] _k^2 ). Thus we may set Δ0:=(1−η)p∑k∈[L]γk _0:=(1-η)p _k∈[L] _k and obtain ℙ(Em(x)=‘unseen’∣w∈s)≤|s|exp(−2η2p2(∑k∈[L]γk)2∑k∈[L]γk2)+e−δ2(μ+Δ0)/2. (E_m(x)=`unseen' w _s)≤|W_s| (- 2η^2p^2( _k∈[L] _k)^2 _k∈[L] _k^2 )+e^-δ^2(μ+ _0)/2. Similarly, ℙ(Em(x)=‘seen’∣w∈s)≤|s|exp(−2η2p2(∑k∈[L]γk)2∑k∈[L]γk2)+e−δ2μ/(2+δ). (E_m(x)=`seen' w _s)≤|W_s| (- 2η^2p^2( _k∈[L] _k)^2 _k∈[L] _k^2 )+e^-δ^2μ/(2+δ). This completes the proof. ∎ B.3 A Result under Exchangeability of the Predictors ψk _k One issue with the previous analysis is that we have been assuming independence of the predictors ψk _k (for instance, by sample splitting, which comes at the cost of some statistical efficiency). In practice, the different predictors in the ensemble may be assigned common training samples, rendering them not independent of each other. It turns out that we can prove similar results under the weaker assumption of exchangeability. Theorem 3. Fix x,w(x)x,w(x). Suppose (α1,β1),…(αL,βL)( _1, _1),…( _L, _L) are exchangeable random variables with common mean (α,β)(α,β). Then, for m=L(β+p2(1−α−β))m=L (β+ p2(1-α-β) ), the ensemble classifier EmE_m is such that ℙ(Em(x)=‘unseen’∣w∈s) (E_m(x)=`unseen' w _s) ≤exp(−p2L(1−α−β)2(L−HL)2(L−1)) ≤ (- p^2L(1-α-β)^2(L-H_L)2(L-1) ) ℙ(Em(x)=‘seen’∣w∈u) (E_m(x)=`seen' w _u) ≤exp(−p2L(1−α−β)2(L−HL)2(L−1)). ≤ (- p^2L(1-α-β)^2(L-H_L)2(L-1) ). Here, (α1,β1),…(αL,βL)( _1, _1),…( _L, _L) being exchangeable means that for any permutation σ of [L][L], we have (α1,…,αL,β1,…,βL)=d(ασ(1),…,ασ(L),βσ(1),…,βσ(L)).( _1,…, _L, _1,…, _L) d=( _σ(1),…, _σ(L), _σ(1),…, _σ(L)). Proof. As before, let X=∑k∈[L](ψk(x)=‘seen’).X= _k∈[L] 1( _k(x)=`seen'). We analyze this variable in the cases w∈sw _s and w∈uw _u. From [3, Theorem 4], let v∈ℝLv ^L and X1,…,XL∈[−1,1]X_1,…,X_L∈[-1,1] be exchangeable, where L≥2L≥ 2. Then, ℙ∑i=1Lvi(Xi−[Xi])≥∥v∥22(L−1L−HL)log(1/δ)≤δP \ _i=1^Lv_i(X_i-E[X_i])≥\|v\|_2 2 ( L-1L-H_L ) (1/δ) \≤δ where HL=∑i=1L1i∼O(logL)H_L= _i=1^L 1i O( L). We apply this in the case where XiX_i is a Rademacher random variable as follows: Xi=1ψk calls x seen−1otherwiseX_i= cases1& _k calls x seen\\ -1&otherwise cases so we get: [Xi] [X_i] =2p(1−α)+2(1−p)β−1w∈s2β−1w∈u = cases2p(1-α)+2(1-p)β-1&w _s\\ 2β-1&w _u cases X−[X] X-E[X] =12∑i=1LXi−[Xi]. = 12 _i=1^LX_i-E[X_i]. Setting v=(1/2,…,1/2)v=(1/2,…,1/2), we obtain ℙX−[X]≥122L(L−1L−HL)log(1/δ)≤δ.P \X-E[X]≥ 12 2L ( L-1L-H_L ) (1/δ) \≤δ. Setting v=(−1/2,…,−1/2)v=(-1/2,…,-1/2), we obtain ℙX−[X]≤−122L(L−1L−HL)log(1/δ)≤δ.P \X-E[X]≤- 12 2L ( L-1L-H_L ) (1/δ) \≤δ. Hence, choosing our threshold m=L(β+p2(1−α−β))m=L (β+ p2(1-α-β) ), we can get 122L(L−1L−HL)log(1/δ)=pL2(1−α−β), 12 2L ( L-1L-H_L ) (1/δ)= pL2(1-α-β), i.e. δ=exp(−p2L(1−α−β)2(L−HL)2(L−1))δ= (- p^2L(1-α-β)^2(L-H_L)2(L-1) ) which is our false positive rate/false negative rate. We notice δ∼exp(−cL)δ (-cL) for some constant c. ∎ We can see that the prediction errors shrink exponentially in L, making the ensemble predictor a viable approach.