# Near-Optimal Active Learning for Multilingual Grapheme-to-Phoneme Conversion
## 4 Active Learning
### Submodular Function  
Most active learning methods select one valuable sample at a time for labeling, which is referred to as the non-batch method. However, this method is slow because the recognizer is retrained for each selected sample, and it cannot perform simultaneous multi-expert online labeling. In contrast, batch active learning methods can select multiple unlabeled samples at one time [32; 33; 34]. However, using only a single sample selection strategy in batch active learning can lead to poor results, as the selected samples may have a high information similarity (e.g., using the N-best method). To select the optimal subset of samples that represent the overall dataset, we optimized the sample selection problem using submodular function theory [35]. Specifically, we investigated the objective function of the near-optimal set of pronunciation dictionary samples and showed that our function had the submodularity property, which allowed for active learning so as to obtain a near-optimal subset of the corpus using a greedy algorithm. For the classifier, the goal of batch active learning is to form a set \(S\) of \(N\) unlabeled samples per iteration after user labeling, which is added to training set \(L\). By retraining the classifier, the classifier can achieve the maximum performance improvement. In active learning, the use of the maximum entropy principle as an evaluation criterion aims to select the most informative data to train the model and to achieve optimal results. This objective function can be represented as follows:  
\[H(YS)=-\sum p(y)log\ p(y|s) \tag{9}\]  
In this equation, \(H(Y|S)\) quantifies the uncertainty of the target variable \(Y\) given a known set of variables \(S\), using the concept of entropy. The probability distribution of the target variable y is denoted by \(p(y)\), and \(p(y|s)\) represents the conditional probability distribution of \(y\) given a known set of variables \(s\). The objective of this function is to maximize the uncertainty of the target variable \(Y\) given a set of samples \(S\). In the process, it is often necessary to select the next sample with the highest information content from a sample set [36]. The criterion for such a selection is to choose a sample that maximizes the uncertainty of the target variable \(Y\), because this sample can provide the most informative new data that will facilitate a better understanding of the relationship between the target variable \(Y\) and the input variables. This, in turn, helps improve the performance of the model by enhancing its ability to learn from the data. Regarding submodular functions, they are a special class of functions that possess important properties of monotonicity and diminishing marginal returns. In other words, function \(f\) satisfies the following two conditions:  
1. Monotonicity: For any sets \(S\_1\subseteq S\_2\subseteq E\) and element, the function \(f\) satisfies the inequality \(f(S\_1\cup e)-f(S\_1)\leq f(S\_2\cup e)-f(S\_2)\). 2. Diminishing marginal returns: For any set \(S\subseteq E\) and element \(e\in E-S\), the function \(f\) satisfies the inequality \(f(S\cup e)-f(S)\geq f(T\cup e)-f(T)\) for any subset \(T\subseteq S\), such that \(T\cup e\subseteq S\cup e\). Now, we will prove that the maximum entropy function \(H(Y|S)\) is a submodular function. Firstly, let us prove the monotonicity of \(H(Y|S)\). For any \(S\_1\subseteq S\_2\subseteq E\) and element \(e\in E-S\_2\), we have:  
\[ \begin{array}{c}H(Y|S_{1}\cup e)-H(Y|S_{1})\\ =-\sum p(y)log(p(y|S_{1}\cup e))+\sum p(y)log(p(y|S_{1}))\\ =-\sum p(y)log(p(y|S_{1}))+\sum p(y)log(p(y|S_{1}\cup e))\\ \leq-\sum p(y)log(p(y|S_{2}))+\sum p(y)log(p(y|S_{2}\cup e))\\ =H(Y|S_{2}\cup e)-H(Y|S_{2})\end{array}