{'fraction_non_alphanumeric': 0.03947435505251351, 'fraction_numerical': 0.013332313653512798, 'mean_word_length': 4.170488994332411, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 20, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 42, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Theoretical Foundation of Co-Training and Disagreement-Based Algorithms

Disagreement-based approaches generate multiple classifiers and exploit the disagreement among them with unlabeled data to improve learning performance. Co-training is a representative paradigm of them, which trains two classifiers separately on two sufficient and redundant views; while for the applications where there is only one view, several successful variants of co-training with two different classifiers on single-view data instead of two views have been proposed. For these disagreement-based approaches, there are several important issues which still are unsolved, in this article we present theoretical analyses to address these issues, which provides a theoretical foundation of co-training and disagreement-based approaches.


Introduction
Learning from labeled training data is well-established in traditional machine learning, but labeling the data is time-consuming, sometimes may be very expensive since it requires human efforts. In many practical applications, unlabeled data can be obtained abundantly and cheaply. For example, in the task of web page classification, it is easy to get abundant unlabeled web pages in the Internet, while a few labeled ones are available since obtaining the labels requires human interaction. Many semi-supervised learning approaches which exploit unlabeled data to complement labeled data for improving learning performance have been developed. Those approaches can be roughly categorized into four classes, i.e., generative approaches, S3VMs (Semi-Supervised Support Vector Machines), graph-based approaches and disagreement-based approaches. Generative approaches use a generative model and typically employ EM to model the label estimation or parameter estimation process [1,2,3]. S3VMs use unlabeled data to adjust the SVM decision boundary learned from labeled data such that it goes through the less dense region while keeping the labeled data classified correctly [4,5,6]. Graph-based approaches define a graph on the training data and enforce the label smoothness over the graph as a regularization term [7,8,9,10]. Disagreement-based approaches generate multiple classifiers and exploit the disagreement among them with unlabeled data, i.e., letting the multiple classifiers label unlabeled instances to augment the training data [11,12,13,14].
Research on disagreement-based approaches started from Blum and Mitchell's seminal work of co-training [11], which is a representative paradigm of disagreementbased approaches. When co-training was proposed, Blum and Mitchell assumed that there exist two views (i.e., two disjoint sets of features), each of which is sufficient for learning the target concept. For example, the web page classification task has two views, i.e., the text appearing on the page itself and the anchor text attached to hyper-links pointing to this page [11]; the speech recognition task also has two views, i.e., sound and lip motion [15]. Co-training learns two classifiers with initial labeled data on the two views respectively and lets them label unlabeled instances for each other to augment the training data. Unfortunately, in real-world applications, the requirement of two views is hard to satisfy. Although Nigam and Ghani [16] have shown that a feature split can be used to enable co-training to work when there are many redundant features, it is more desirable to develop algorithms that can be applied to single-view data.
Several successful variants of co-training have been proposed along this direction. For example, Goldman and Zhou [12] proposed a method which generates two classifiers by using two different learning algorithms that can partition the example space into a number of equivalence classes; Zhou and Li [17] proposed a semi-supervised regression method which generates two regressors by using different parameter configurations for the same learning algorithm. Different relevant algorithms have been developed with different names and the name disagreement-based semi-supervised learning was coined [14,18] to reflect the fact that co-training and its variants are actually in the same family, and the key for the learning process to proceed is to maintain a large disagreement among the classifiers 1 . Co-training [11] is the famous algorithm which relies on two views, while the algorithms which rely on multiple classifiers generated from single-view data is referred to as single-view disagreement-based approaches.
In disagreement-based approaches, multiple classifiers are trained for the same task and the disagreement among them is exploited during the learning process.
Here, unlabeled data serve as a kind of "platform" for information exchange.
If one classifier is much more confident on a disagreed unlabeled instance than other classifier(s), then this classifier will teach other(s) with this instance 2 . It does not matter where these classifiers come from, they can be trained on multiview data with the same learning algorithm or on single-view data with different learning algorithms. The disagreement-based algorithms have achieved success in many domains such as natural language processing [19,20,21] and image retrieval [22,23].
There is another famous semi-supervised learning approach called co-regularization [24,25,26], which also exploits unlabeled data with two views. It directly minimizes the error rate on labeled data and the disagreement on unlabeled data 1 If there is no disagreement among the classifiers, the learning process would degenerate into self-training. 2 In real-world applications, the disagreement-based approaches may consist of more than two classifiers, in this article we mainly focus on the two-classifier setting.
over two views with the intuition that the optimal classifiers in the two views are compatible with each other. It is worth noting that co-training exploits unlabeled data very differently from co-regularization, and no pseudo-labels are assigned to unlabeled instances in co-regularization.
By comparing these discriminative semi-supervised learning approaches, it can be found that unlabeled data help in two distinct ways. One is starting with unlabeled data to generate a constraint (regularization) and then learning a classifier with labeled data and the constraint (regularization), i.e., S3VMs, graph-based approaches and co-regularization. In S3VMs, unlabeled data are exploited as a constraint such that the SVM decision boundary goes through the less dense region; in graph-based approaches, unlabeled data are exploited to construct a graph Laplacian regularization; while in co-regularization, unlabeled data are exploited to generate a regularization of disagreement over two views. Balcan and Blum [27] provided a unified framework for these approaches to interpret why and when unlabeled data can help, in which they defined a notion of compatibility and assumed that the target concept should have high compatibility with the underlying data distribution. Unlabeled data are exploited to estimate the compatibility of all hypotheses and the size of hypothesis space could be reduced by removing the hypotheses which have low compatibility. Then labeled data is used to find a good hypothesis within the reduced hypothesis space, which will lead to good sample-size bounds. The other is starting with labeled data to generate multiple weak classifiers and then letting them label unlabeled instances to augment the training data, i.e., disagreement-based approaches. There has been a long-term theoretical study on this. When Blum and Mitchell [11] proposed co-training, they proved that when the two views are conditionally independent, co-training can boost the performance of weak classifiers to arbitrarily high by exploiting unlabeled data.
Dasgupta et al. [28] analyzed the generalization bound for co-training with two conditionally independent views and showed that the error rate of co-training is bounded by the disagreement between two co-trained classifiers. To relax the conditional independence assumption, Abney [29] found that weak dependence can also lead to successful co-training. Later, Balcan et al. [30] pointed out that if a PAC classifier can be obtained on each view, the conditional independence assumption or even weak dependence assumption is unnecessary; a weaker assumption of "expansion" over the underlying data distribution is sufficient for co-training to succeed. However, all these results focus on co-training which relies on two views, there are several important issues on disagreement-based approaches which still are unsolved.

Our Focus and Main Results
We present a theoretical foundation of co-training and disagreement-based approaches to address the unsolved issues in this article. The issues and results can be summarized as follows.
(1) One basic issue is why and when the disagreement-based approaches can improve learning performance by exploiting unlabeled data. We present a general analysis, which shows that if the two initial classifiers trained with the initial labeled data have large disagreement, the disagreement-based approaches can improve learning performance (Section 2.1); (2) it is often observed that the performance of the classifiers in disagreement-based approaches can not be improved further after a number of rounds in empirical studies. Up to now, there is no theoretical explanation to this. We prove that the disagreement and the error rates of the classifiers will converge after a number of rounds, which theoretically explains why the classifiers can not be improved further (Section 2.2); (3) all previous theoretical analyses focused on the sufficient condition, so a fundamental issue may arise: what is the sufficient and necessary condition for co-training to succeed? To the best of our knowledge, this has not been touched. We present a theoretical graph-based analysis on co-training, based on which we get the sufficient and necessary condition for co-training to succeed (Section 3); (4) all previous theoretical analyses assumed that each view is sufficient for learning the target concept. So another issue may arise: what can co-training do with insufficient views? We present a theoretical analysis on co-training with insufficient views which is much more challenging but practical, especially when the two views provide diverse information (Section 4); (5) the classifiers in disagreement-based approaches are usually combined to make predictions, unfortunately, there is no theoretical analysis about this. We study margin-based classifiers and present a theoretical analysis to explain why and when the combination can be better than the individual classifiers (Section 5).

Organization
The rest of this article is organized as follows. We present a general analysis on disagreement-based approaches to explain why they can improve learning performance by exploiting unlabeled data in Section 2.1 and why the learning performance can not be improved further after a number of rounds in Section 2.2. In Section 3, we study the sufficient and necessary condition and give an interesting implication, such as combination of weight matrices. We analyze co-training with insufficient views in Section 4, and analyze when the combination can be better than the individual classifiers in Section 5. Finally, we make a conclusion in Section 6.

General Analysis on Disagreement-Based Approaches
Given the labeled data L, unlabeled data U and two hypothesis spaces H 1 and H 2 , in this section we consider the following disagreement-based process whose pseudo-codes are in Algorithm 1. h i v selects u unlabeled instances from U to label, then add them into σ 3−v and delete them from U . end for trained with σ 1 and σ 2 , respectively. After that, h 1 1 selects u unlabeled instances to label and uses these newly labeled examples to update σ 2 ; while h 1 2 also selects u unlabeled instances to label and uses these newly labeled examples to update σ 1 . Such a process is repeated for a pre-set number of learning round.

Disagreement-Based
It is easy to see that Algorithm 1 reassembles the main process of existing disagreement-based approaches including co-training 3 [11] which requires that the data should have two views and single-view disagreement-based algorithms [12,17,31]. The key procedure is that one classifier labels some unlabeled instances for the other, it does not matter where the two classifiers come from.
The two classifiers can be trained on two-view data with the same learning algorithm or on single-view data with two different learning algorithms. 3 Algorithm 1 is almost the same as co-training in [11] except one place: Algorithm 1 uses L and the examples labeled by classifier hv (v = 1, 2) to retrain classifier h 3−v , while cotraining in [11] uses L and the examples labeled by both classifiers h 1 and h 2 to retrain each of them. To exclude the examples labeled by a classifier itself is helpful in reducing the risk of over-fitting and many recent algorithms use the paradigm described in Algorithm 1.

Upper Bounds on Error rates of Classifiers
Suppose that X is the instance space, Y = {−1, +1} is the label space, L = {(x 1 , y 1 ), · · · , (x l , y l )} ⊂ X × Y are the labeled data, U = {x l+1 , x l+2 , · · · , x l+|U | } ⊂ X are the unlabeled data. Suppose that the labeled data L independently and identically come from some unknown distribution D, whose marginal distribution on X is D X , and the unlabeled data U independently and identically come from D X . H v : X → Y (v = 1, 2) denotes the hypothesis space. Suppose that |H v | is finite 4 and the target concept (ground truth) c which is perfectly consistent with the distribution D belongs to H 1 and H 2 , and the error rate err(h v ) of h v ∈ H v and the disagreement d(f, g) between two hypotheses f and g are defined as follows.
In disagreement-based approaches shown in Algorithm 1, one classifier selects some unlabeled instances to label for the other. Here comes the question: how to select these unlabeled instances? In co-training [11], Blum and Mitchell did not specify how to select unlabeled instances (see Page 8, Table 1 in their paper), though in their experiments they selected the most confident unlabeled instances to label with the intuition that confident instances bring high label quality. Nevertheless, there is no guarantee that selecting confident instances is better than selecting random instances, and it needs strong assumptions to characterize the relationship between confidence and label quality. Sometimes, selecting confident instances may be no better than selecting random instances if the confidence is unreliable. Actually, if the learning paradigm believes that labeling confident instances is helpful, it can select confident instances to label; 4 If Hv is infinite hypothesis space with finite VC-dimension dv, we can replace Hv with its -cover H v : a set of hypotheses H v ⊆ Hv such that for any hv ∈ Hv there is a h v ∈ H v satisfying P (hv(x) = h v (x)) ≤ . It is well-known that such an H v always exists with size otherwise, it can select random instances to label. Thus, selecting random instances to label can be thought of as the worst case. To make our theoretical analysis general and without any specific assumption on the learning process, we will prove upper bounds on the error rates of the classifiers by considering that each classifier selects random instances to label. In fact, these upper bounds also hold in the case where selecting confident instances helps; this is easy to understand: labeling confident instances may reduce label noise, according to the standard PAC learning theory, learning from the data with small label noise is no harder than learning from the data with large label noise.
Two classifiers trained with different views or different learning algorithms have different biases, it is the intuition why the disagreement-based approaches can work. Two classifiers having different biases implies that they classify some unlabeled instances with different labels. The disagreement d(f, g) can be used to estimate the difference. In disagreement-based approaches, f selects some unlabeled instances from U to label and adds them into the training data of g.
If these newly labeled examples are helpful in updating g, f should know some information that g does not know, i.e., f can correctly classify some unlabeled instances which are mistakenly classified by g. Obviously, this helpful information is a part of the disagreement between f and g. Unfortunately, sometimes f may provide some mistakenly classified examples to g due to its non-perfect performance, and these mistakenly classified examples from f would degrade the performance of g. So we must carefully characterize the newly labeled examples.
. . , s and v = 1, 2). In the beginning, two classifiers h 0 1 and h 0 2 are trained with the initial l labeled examples by minimizing the empirical risk. In real-world applications, it has been found that these initial labeled examples play an important role, i.e., when l is too large, h 0 1 and h 0 2 are so good that they could improve each other hardly; while l is too small, h 0 1 and h 0 2 are so weak that they may degenerate each other due to large noise in the newly labeled examples [33,34]. In our analysis, we suppose that by minimizing the empirical risk on l labeled examples we can train two classifiers h 0 1 and h 0 2 with ε 0 1 < 1 2 and ε 0 2 < 1 2 , and the value of l satisfies the model of learning from noisy examples in [35] with noise rate η shown in Equation 1. The reason why we use this noise model to characterize l is that updating the classifiers is a process of learning from noisy examples.
Considering that the initial labeled examples are clean, i.e., η = 0, we get that l should be no less than Let ξ i v denote the upper bound on the error rate of h i 1 , i.e., ε i v ≤ ξ i v . In order to show whether the performance of the classifiers could be improved, we need to analyze the upper bounds ξ i 1 and ξ i 2 for i ≥ 1. In detail, considering the i-th round, h i v ∈ H v randomly selects u unlabeled instances from U to label and adds them into the training data is a kind of "distance" between h i v and h i+1 3−v , and can be estimated conveniently when there are a large mount of unlabeled instances. This "distance" will help us bound the performance of h i+1 3−v with respect to the performance of h i v . Iteratively, we can bound the performance of h i v for i ≥ 1. Based on this intuition, we give the following upper bounds for ξ i 1 and ξ i 2 , and discuss the insight we can get from the bounds.
Theorem 1 In Algorithm 1, suppose one classifier randomly selects unlabeled instances to label for the other, First, it is easy to verify that ξ i 1 < ε 0 1 and ξ i 2 < ε 0 2 for Θ i > . . , (x u k , y u k ) denotes the u newly labeled examples labeled by h k 1 and y u k is the pseudo-label of x u k assigned by h k 1 (k = 0, . . . , i − 1). Let X 1 , . . . , X l+iu be random variables taking on values 0 or 1, where X t = 1 means that for x t ∈ σ 2 , h 2 makes a different prediction on x t from its pseudo-label (t = 1, . . . , l + iu). Considering that (x 1 k , y 1 k ), . . . , (x u k , y u k ) are randomly selected by h k 1 , so X 1 , . . . , X l+iu are independent random variables. We let p t = P (X t = 1) and X = l+iu t=1 X t . Obviously, X equals to the number of inconsistent examples between h 2 and σ 2 .
Since the initial l labeled examples (x 1 , y 1 ), . . . , (x l , y l ) in σ 2 are independently and identically drawn from the distribution D and the disagreement between h 2 ∈ H 2 and the target concept c is d(h 2 , c), for any x t ∈ {(x 1 , y 1 ), . . . , (x l , y l )}, p t = d(h 2 , c); since the newly labeled examples (x 1 k , y 1 k ), . . . , (x u k , y u k ) (k = 0, . . . , i − 1) are selected randomly by h k 1 and the disagreement between h 2 ∈ H 2 and h k 1 is d(h 2 , h k 1 ), for any x t ∈ {(x k 1 , y k 1 ), . . . , (x k u , y k u )}, p t = d(h 2 , h k 1 ). So we get the expectation E(X) of X is: Then, we analyze the inconsistency between the target concept c and σ 2 .
Let random variables X 1 , . . . , X l+iu be independent random variables taking on values 0 or 1, where X t = 1 (t = 1, . . . , l + iu) means that for x t ∈ σ 2 , the target concept c makes a different prediction on x t from its pseudo-label.
We let q t = P (X t = 1) and X = l+iu t=1 X t . Obviously, X equals to the number of inconsistent examples between c and σ 2 . Since the newly labeled examples (x 1 k , y 1 k ), . . . , (x u k , y u k ) (k = 0, . . . , i − 1) are selected randomly by h k 1 and the disagreement between the target concept c and h k 1 is d(c, h k 1 ), similarly to Equation 4 we get the expectation E(X ) of X is: According to minimizing the empirical risk, the algorithm will search out the classifier which has the lowest observed inconsistent examples with the training data σ 2 . If we want to achieve a 'good' classifier whose error rate is no larger than ξ i 2 with probability at least 1−δ by minimizing the empirical risk, σ 2 should be sufficient to guarantee that the classifier whose error rate is larger than ξ i 2 has a lower observed inconsistent examples with σ 2 than the target concept c with probability no larger than δ.

from Equations 4 and 5 we get
So with Hoeffding bounds [36] we get Since l ≥ 2 . So with Equations 9 and 10 we find that Equations 7 and 8 hold. Thus we have that Remark: The bounds in Theorem 1 seem somewhat complicated to understand, we give an explanation in the following comprehensive way: in the i- . This is the intuition why the bounds are meaningful. d(h k 1 , h i 2 ) and d(h i 1 , h k 2 ) can be estimated conveniently with unlabeled data, then we can calculate ξ k 1 and ξ k 2 according to Equations 2 and 3. Using them as the approximations of ε k 1 and ε k 2 , we can get ε i 1 , ε i 2 , Θ i and ∆ i in an iterative way. Generally, as the disagreement-based process goes on, the disagreement will Here, we give Theorem 2 on the disagreement.
Proof. Let D(h 1 , σ 1 ) denote the number of inconsistent examples between h 1 and the training data σ 1 , and let σ k 1 denote σ 1 in the k-th round. h k 1 ∈ H 1 is trained on σ k 1 by minimizing the empirical risk, so for any h 1 ∈ H 1 , we have h k 2 randomly selects u unlabeled instances to label and adds them into σ k 1 to get σ k+1 1 . Let S k 2 denote these u newly labeled examples, i.e., σ k+1 2 . Therefore, it could be recognized that the two views used in co-training [11], the two different learning algorithms used in [12], and the two different parameter configurations used in [17] are actually exploited to make the two initial classifiers have large disagreement. It does not matter whether the disagreement comes from the two views or not. This explains why the disagreement-based approaches can work.
In the following parts of this section we will discuss whether the condition in Theorem 1 can be satisfied in the applications with or without two views.

Co-Training
In real-world applications, co-training can be implemented when there exist two views. First, we show that the condition in Theorem 1 could be satisfied in co-training. An extreme case is that the two views are exactly the same and the two-view setting degenerates into the single-view setting. To analyze cotraining, we should know some prior knowledge about the two views. There have been some theoretical analyses on co-training, i.e., conditional independence analysis and expansion analysis.
Conditionally Independent Views. When Blum and Mitchell [11] proposed co-training, they assumed there exist two sufficient and redundant views in the data. If the two views are conditionally independent to each other, they proved that co-training can boost the performance of weak classifiers to arbitrarily high by using unlabeled data. Here, we give Theorem 3 for co-training with conditionally independent views. Theorem 3 Suppose 0 ≤ ε 0 1 , ε 0 2 ≤ ζ ≤ 1 6 and the data have two conditionally independent views, the condition Θ i > Proof. In the two-view setting, for an example (x, y), let h i 1 (x) denote the label predicted by the classifier in the i-th round of the first view and let h i 2 (x) denote the label predicted by the classifier in the i-th round of the second view. The two views are conditionally independent to each other means that the classifier in the first view is independent of the classifier in the second view to make predictions. So we have Remark: Theorem 3 shows that if the two views are conditionally independent, the condition in Theorem 1 holds in a number of learning rounds (before the error rates decrease to some degree). It could not guarantee that the condition in Theorem 1 always holds in the learning process, which is different from that co-training can boost the performance to arbitrarily high with the conditional independence condition. This is understandable because our theorem provides a general analysis and does not depend on any strong condition. In fact, we will prove that the performance could not always be improved as the learning process goes on in Section 2.2.
Expanding Views. Balcan et al. [30] pointed out that "expansion" of the underlying data distribution is sufficient for co-training to succeed. Furthermore, they also assumed that the classifier in each view is never "confident but wrong", which means that if the classifier makes a prediction, the prediction is correct. Here, we give Theorem 4 for co-training with expanding views.
Theorem 4 Suppose the "expansion" assumption holds and the classifier in each view is never "confident but wrong", the condition Θ i > denotes the probability mass on the examples predicted correctly by just one view. The "expansion" assumption means that for some α > 0 and any S 1 , S 2 , has a lower bound, i.e., P ( The classifier in each view is never "confident but wrong" means that if the classifier makes a prediction, the prediction is correct, i.e., ε 0 Remark: Theorem 4 shows that if the two views meet the expansion condition, the condition in Theorem 1 holds. It implies that our result is more general.
However, these previous results only focus on co-training, they can not explain why the single-view disagreement-based approaches can work.

Single-View Disagreement-Based Approaches
Secondly, we study the setting where there exists only one view and give Theorem 5 to show that there exist two hypotheses which have large disagreement.
Theorem 5 For any real numbers 0 < a, b < 1 2 , there exist two hypotheses h 1 and h 2 which satisfy the following conditions: err(h 1 ) = a, err(h 2 ) = b and Proof. Without loss of generality, we assume that a ≤ b and that h 1 is the hypothesis whose error rate is a, i.e., err(h 1 ) = a. Now we show how to find the hypothesis h 2 which satisfies the conditions: Then, let h 2 be the hypothesis corresponding to the following classification rule: . Then, let h 2 be the hypothesis corresponding to the following classification rule: Remark: Theorem 5 indicates that fixing the error rates of two hypotheses, the disagreement between them can vary from |a − b| to (a + b). For example, there exist hypotheses h i 1 and h k 2 which have large disagreement and satisfy the condition that Before the error rates ε i 1 and ε i 2 decrease to 3 4 ε 0 1 and 3 4 ε 0 2 , respectively, the condition Θ i > i 2 ε 0 1 and ∆ i > i 2 ε 0 2 in Theorem 1 holds.

Why There is No Further Improvement After a Number of Rounds
In the above section, we prove that the learning performance of the classifiers can be improved by exploiting unlabeled data. Can the classifiers be always improved as the learning process goes on? It is a very important and interesting problem. In fact, in some empirical studies such as the natural language processing community [33], it has been observed that the classifiers could not be improved further after a number of rounds in disagreement-based approaches, and if the process is going on they would be degraded. This is very different from what has been disclosed by previous theoretical studies, e.g., the performance of the classifiers can be boosted to arbitrarily high [11,30]. Our following theoretical analysis in this section will give an explanation to this.
Theorem 6 In Algorithm 1, for any ∈ (0, 1) and δ ∈ (0, 1), there exists some integer N > 0, for any integer t ≥ N , the following inequalities hold (v = 1, 2): according to the standard PAC learning theory, there exists some integer N > 0, for any integer Remark: Equation 19 indicates that the error rates of the classifiers will converge, which implies that the classifiers could not be improved further after a number of learning rounds. Actually, the training data for one classifier may contain noisy examples mistakenly labeled by the other classifier, so the sur- Without strong assumptions, e.g., two views are conditionally independent or the classifier is never "confident but wrong", it is very hard to find a good approximation of the target concept c with D v . Equation 20 indicates that the disagreement between the classifiers will converge. As the classifiers label more and more unlabeled instances for each other, they will become more and more similar and the disagreement between them will decrease closely to 0. In this case, the disagreement-based process degenerates into self-training. If we continue it, the risk of over-fitting will be great and the performance will be degraded as observed in the empirical study of [33].

Empirical Studies
In this section, we provide empirical studies to verify our theoretical analyses, i.e., whether the disagreement and error rates of the classifiers will converge, and whether larger disagreement will lead to better improvement.
We use the course data set [11] and three UCI data sets, i.e. kr-vs-kp, mushroom and tic-tac-toe [37]. The course data set has two views (i.e., pages we randomly select 25% data as the test set while using the remaining 75% data to generate a labeled data L whose size will be mentioned in Figures 1, 2 and 3, and the rest of the 75% data are used to generate the unlabeled data U .
In the experiments, we let each classifier label its most confident unlabeled instances for the other in each round to reduce label noise. However, this way will cause a problem that the training set is not an i.i.d. sample from the underlying distribution. To reduce the influence of non-i.i.d. sample, we create a small pool U of size 75 by drawing instances randomly from the large unlabeled data U and select the confident instances from U to label, as that in [11].
They reported that using a small pool can get better results than selecting confident instances directly from U , because it forces the classifiers to select more

Convergence of Disagreement and Error rates
We run co-training on the course data set by using NaiveBayes, and run the single-view disagreement-based approach on the UCI data sets by using two different classifiers, i.e., SMO and J48 on the kr-vs-kp data set, SMO and NaiveBayes on the mushroom data set, and SMO and MultilayerPerceptron on the tic-tac-toe data set. The error rates, the disagreement between the two classifiers are depicted in Figures 1 and 2.
In Figure 1(a), the disagreement between the classifiers increases in the first several rounds and then decreases. This is because in course-3-9-1-3 the initial labeled training data set L is too small, the two initial classifiers h 0 1 and h 0 2 are simple and only learn small part of the task. After co-training is executed, the amount of training examples for each classifier increases. Then each retrained classifier learns more about the task from its own perspective and the disagreement between the classifiers increases. As the two classifiers label more and more unlabeled instances for each other, they become more and more similar and the disagreement between them decreases.  In general, Figures 1 and 2 show that except the first several rounds, the disagreement between the classifiers decreases or converges as the process goes on. If the disagreement does not converge, the error rates of the classifiers seem to decrease as the disagreement decreases, e.g., Figures 2(g) to (i). If the disagreement converges, the error rates of the classifiers also seem to converge, e.g., Figure 2(d) to (f). This validates that our Theorem 6 which shows that the disagreement and error rates of the classifiers in disagreement-based approaches will converge is meaningful.

Larger Disagreement Leading to Better Improvement
In order to study the disagreement further, more experiments are conducted.
We run the disagreement-based approach with two different groups of classifiers on the pages view of course data set. The first group is SMO and MultilayerPerceptron, and the second group is SMO and NaiveBayes. With this experiment, it is clearer whether the classifiers with larger disagreement could lead to better improvement. The results are depicted in

Sufficient and Necessary Condition
All previous theoretical analyses on co-training focus on the sufficient condition, i.e., under what condition co-training could work, so a fundamental issue may arise: what is the sufficient and necessary condition for co-training to succeed? In this section we will study what the sufficient and necessary condition is. For the convenience of description, we first suppose that the data have two views and then discuss how to generalize it to the case where the data have only one view.
Let X = X 1 × X 2 denote the instance space, where X 1 and X 2 correspond to the two views, respectively. Y = {−1, +1} is the label space, L = } ⊂ X are the unlabeled data. The labeled data L indepen-dently and identically come from some unknown distribution D, whose marginal distribution on X is D X , and the unlabeled data U independently and identically come from D X . c = (c 1 , c 2 ) is the target concept, where c 1 and c 2 are the target concepts in the two views, respectively, i.e., c 1 (x 1 ) = c 2 (x 2 ) = y for any example ( x 1 , x 2 , y).

Graph View of Co-Training
When Blum and Mitchell [11] proposed co-training, they gave a bipartite graph over two views for intuition. The left-hand side of the bipartite graph has one node for each instance in view X 1 and the right-hand side has one node for each instance in view X 2 . Since each instance x = x 1 , x 2 has two views, there is an undirected edge between the left-hand x 1 and the right-hand x 2 .
Considering that each view X v (v = 1, 2) corresponds to a graph where each node is one instance and there is an undirected edge between two nodes if they have the same class label, it naturally inspires us to study co-training with the graphs over two views.
Generally, assigning a label to an unlabeled instance x t v (v = 1, 2) based on a labeled example x s v can be viewed as estimating the conditional probability P y( For controlling the confidence, we can set a threshold η v > 0 (generally does not mean that x s v and x t v must have different labels, since the data may not provide any helpful information for estimating the similarity between x s v and x t v . We can assign a label to x t v according to P y( can be normalized to a probabilistic transition matrix according to Equation 21.
Then the labels can be propagated from labeled examples to unlabeled instances according to the process [39]:  This process can be repeated until the stopping condition is met. Thus, cotraining can be re-described as the combinative label propagation process over two views in Algorithm 2, where S k . Label propagation needs a graph which is represented by the matrix P . In this section, we focus on co-training with two graphs P 1 and P 2 constructed from the two views. How to construct a graph is an important issue studied in graph-based approaches [40,41] and is beyond the scope of this article.

Co-Training with Perfect Graphs
First, we assume that x s v and x t v must have the same label. It means that the classifier is either "confident of labeling" or "having no idea". Before showing the sufficient and necessary condition for co-training with perfect graphs to succeed, we need Lemma 1 to indicate the relationship between label propagation and connectivity.
Lemma 1 Suppose that P is perfect graph. Unlabeled instance x t0 can be labeled by label propagation on graph P if and only if it can be connected with Algorithm 2 Graph-based description of co-training Input: Labeled data L, unlabeled data U and probabilistic transition matrices P 1 and P 2 .
Output: f U v corresponding to S k v (v = 1, 2). Initialize: Perform label propagation from labeled data L to unlabeled data U on graph P v and get the labeled examples set S 0 v ; end if end for some labeled example x tr in graph P through a path R in the form of V R = {t 0 , t 1 , · · · , t r }, where P tρtρ+1 > 0 (ρ = 0, · · · , r − 1).
Proof. It is well known [39] that the label propagation process has the following closed form solution for each connected component in graph P .
Here U θ ∪ L θ is a connected component π θ in graph P , where U θ ⊆ U and L θ ⊆ L.
If an unlabeled instance x t cannot be connected with any labeled example, with respect to Equation 22, we know that f t = 0. If x t0 can be connected with some labeled example x tr through a path R in the form of V R = {t 0 , t 1 , · · · , t r }, considering that P is a perfect graph we get |f t0 | ≥ r−1 ρ=0 P tρtρ+1 |y tr |. Thus, x t0 can be labeled with label sign(f t0 ) by label propagation.
Lemma 1 indicates that when every unlabeled instance can be connected with some labeled example through a path in perfect graph P , label propagation on graph P is successful. Now we give Theorem 7.
Proof. Here we give a proof by contradiction. Suppose that for any unla- From Lemma 1 and the process in Algorithm 2 we know that for any unlabeled instance x t0 ∈ U , x t0 can be connected with some labeled example x tr ∈ L through a path R in the Considering that S k v are obtained by label propagation on graph P v , so from Lemma 1 we know that for any unlabeled instance x h ∈ U −S k v , there is no path between x h and any labeled example x d ∈ S k v in graph P v , i.e., P hd v = 0. It is in contradiction with that any unlabeled instance in U can be connected with Suppose the graph P v contains λ v connected components. If one example in some connected component is labeled, from Lemma 1 we know that all unlabeled instances in this connected component can be labeled by label propagation. If in the k-th iteration of Algorithm 2, the unlabeled instances in at least one connected component of either P 1 or P 2 will be labeled by label propagation. Thus, after at most λ 1 + λ 2 iterations all unlabeled instances in U can be assigned with labels by the process in Algorithm 2.
Considering that P v in each view is perfect graph, we get that for any unlabeled Remark: Theorem 7 provides the sufficient and necessary condition for cotraining with perfect graphs to succeed. With this theorem, for tasks with two views, if two perfect graphs can be constructed from the two views, we can decide whether co-training will be successful.

Co-Training with Non-perfect Graphs
In many real-world applications, it is generally hard to construct a perfect graph. We will discuss the case when the perfect graph assumption is waived in this section.
In label propagation on non-perfect graph, an unlabeled instance may be connected with labeled examples belonging to different classes. As discussed in the proof of Lemma 1, the label propagation for each connected component π θ in graph P has the closed form of

we can get Equation 23 from Equation 22
.
From Equation 23 we know that in each connected component the contribution of the labeled example x s (s ∈ L θ ) to the unlabeled instance x t (t ∈ U θ ) is j∈U θ A tj P js . Now we define the positive contribution and negative contribution to an unlabeled instance.
and the negative contribution to x t is If the positive contribution is larger than the negative contribution, the unlabeled instance x t will be labeled correctly by label propagation 5 . Now we give Theorem 8 for co-training with non-perfect graphs. 5 We neglect the probability mass on the instances for which the non-zero positive contribution is equal to the non-zero negative contribution in this article.
> 0 for all unlabeled instance x t ∈ U (t = l + 1, · · · , l + |U |) if and only if both (1) and (2) hold in Algorithm 2: its positive contribution is larger than its negative contribution.
Proof. Here we give a proof by contradiction. Suppose for any unlabeled (1) and (2) hold, with Definition 1 it is easy to get that for Remark: Theorem 8 provides the sufficient and necessary condition for cotraining with non-perfect graphs to succeed. Note that in both Theorem 7 and Theorem 8, it is the necessary condition that S k 1 ⊕ S k 2 is not ∅ until S k v = L ∪ U (v = 1, 2). In the following part we will further study what this necessary condition means and how to verify it before co-training.
First, we introduce the combinative graph P c in Equation 26 which aggregates graphs P 1 and P 2 .
Then we give Theorem 9 to indicate the necessary condition, i.e., each unlabeled instance can be connected with some labeled example in graph P c .
2) if and only if each unlabeled instance x t0 ∈ U can be connected with some labeled example x tr ∈ L in graph P c through a path R c in the form of V Rc = {t 0 , t 1 , · · · , t r }, where P tρtρ+1 c > 0 (ρ = 0, · · · , r − 1).
Proof. If we neglect the probability mass on the instances for which the non-zero positive contribution is equal to the non-zero negative contribution in this article, similarly to the proof of Lemma 1 we get that: unlabeled instance can be labeled by label propagation on graph P if and only if it can be connected with some labeled example in graph P through a path.
any unlabeled instance x t ∈ U can be labeled by the process in Algorithm 2. So x t must belong to one of S 0 1 , S 0 2 , T k 1 or T k 2 for some k ≥ 0. Considering Equation 26, the above discussions and the fact that S 0 1 , S 0 2 , T k 1 and T k 2 have been obtained in previous iterations by label propagation and will be used as labeled examples in next iteration, we can get that x t0 can be connected with some labeled example x tr ∈ L in graph P c through a path R c .
If each unlabeled instance x t0 ∈ U can be connected with some labeled example x tr ∈ L through a path R c , with respect to Equation 26, we can get that either P tρtρ+1 1 or P tρtρ+1 2 is larger than 0 for ρ = 0, · · · , r − 1. Because x tr is a labeled example, with the above discussions and the process in Algorithm 2 we know that x tρ (ρ = 0, · · · , r − 1) can be labeled by label propagation on either P 1 or P 2 . Therefore, finally S k v = L ∪ U .

Co-Training with -Good Graphs
It is overly optimistic to expect to learn the target concept using co-training with non-perfect graphs. While learning the approximately correct concept using co-training with approximately perfect graphs is more reasonable. In perfect graph, all edges between the instances are reliable; while in non-perfect graph, it is hard to know which and how many edges are reliable. Restricting the reliability and allowing an -fraction exception is more feasible in real-world applications. In this section, we focus on the approximately perfect graph and provide sufficient condition for co-training the approximately correct concept.
Let π 1 v , · · · , π λv v (v = 1, 2) denote the λ v connected components in graph P v , the definitions of purity and -good graph are given as follows.
Definition 2 Let pur(π θ v ) denote the purity of the connected component π θ v in graph P v , then The purity of the connected component reflects the reliability of the graph.
With the purity, we can define the label of π θ v as c v (π θ v ).
With -good graph, predicting the labels of all π θ v correctly is sufficient to get a classifier whose error rate is no larger than . From Definition 1 we know that the unlabeled instances belonging to π θ k v can be labeled with y by label propagation on graph P v . Here γ ∈ [0, 1) can be thought of as a form of margin which controls the confidence in label propagation. With this assumption, we get Theorem 10 which provides a margin-like sufficient condition for co-training the approximately correct concept with -good graphs.

Relationship to Previous Results
As mentioned in Section 1, there are several theoretical analyses indicating that co-training can succeed if some conditions about the two views hold, i.e., conditional independence, weak dependence and α-expansion. Co-training is a representative paradigm of disagreement-based approaches, and we provide a large disagreement analysis for disagreement-based approaches in Section 2 which is also applicable to co-training. Now we will discuss the relationship between the graph-based analysis and previous results on co-training.

Conditional Independence
Blum and Mitchell [11] proved that when the two sufficient views are conditionally independent to each other, co-training can be successful. The conditional independence means that for the connected components π θi 1 of P 1 and π θj 2 ), which implies that the condition (1) in Theorem 10 holds. In addition, Equations 27 and 28 can be obtained for -good graphs.

Weak Dependence
Abney [29] found that weak dependence can lead to successful co-training.

α-Expansion
Balcan et al. [30] proposed α-expansion and proved that it can guarantee the success of co-training. They assumed that the classifier in each view is never "confident but wrong", which corresponds to the case with perfect graphs in Theorem 7. The α-expansion means that S k 1 and S k 2 satisfy the condition that ]. When α-expansion holds, it is easy to know that the condition in Theorem 7 holds. Note that S k 1 ⊕ S k 2 = ∅ is weaker than α-expansion, since P (S k 1 ⊕ S k 2 ) does not need to have a lower bound with respect to some positive α.

Large Disagreement
Our result in Section 2.1 shows that when the classifiers have large disagreement, the performance can be improved. Since the classifiers may have both error and uncertainty with non-perfect graphs, it is complicated to define the disagreement. Therefore, we only discuss co-training with perfect graphs here.
For perfect graphs, the classifiers are "confident of labeling", so the error rate is 0. It implies that the condition in Theorem 7 holds (see Section 6 for more discussions about the results in Section 2.1 and Section 3).

Other Implication and Discussions
From the above discussions it can be found if any previous condition holds, our condition in the graph-based analysis also holds; this means that our result is more general and tighter. Furthermore, this graph-based analysis also has other interesting implication. There were some works which combine the weight matrices or Laplacians for each graph and then classify unlabeled instances according to the combination [26,42,43,44], the underlying principle is not clear. To some extent, Theorem 9 can provide some theoretical supports to these methods, i.e., these methods are developed to satisfy the necessary condition for co-training with graphs to succeed as much as possible. Note that, the graph-based analysis on co-training in this section only cares the two graphs rather than where these graphs come from, and therefore it is also applicable to single-view disagreement-based approaches when there is only one view but two graphs can be obtained in different distance matrices.

Analysis on Co-Training with Insufficient Views
All previous theoretical analyses on co-training are based on the assumption that each view can provide sufficient information to learn the target concept.
However, in many real-world applications, due to feature corruption or various feature noise, neither view can provide sufficient information to learn the target concept. There exist some examples x 1 , x 2 , y , on which the posterior probability P (y = +1|x v ) or P (y = −1|x v ) (v = 1, 2) is not equal to 1 due to the insufficient information provided by x v for predicting the label. In this section, we will present the theoretical analysis on co-training with insufficient views which is much more challenging but practical, especially when the two views provide diverse information.

View Insufficiency
Let X = X 1 × X 2 denote the instance space, where X 1 and X 2 are the two } ⊂ X is the unlabeled data. The labeled data L independently and identically come from some unknown distribution D, whose marginal distribution on X is D X , and the unlabeled data U independently and identically come from D X . c = (c 1 , c 2 ) is the target concept, where c 1 and c 2 are the target concept in the two views, respectively, i.e., c 1 (x 1 ) = c 2 (x 2 ) = y for any ( x 1 , x 2 , y). Since neither view can provide sufficient information to learn the target concept, we may never achieve the target concept with the insufficient views. For an example x 1 , x 2 , y , is sign(f v (x v )). The error rate of a hypothesis f v with the distribution D is and sign(f * v (x v )) = −1 otherwise. Suppose f * v belongs to F v , and it is wellknown that [45] f * 1 and f * 2 are the optimal Bayes classifiers in the two views, respectively. Generally, the two views may provide different information, i.e., there exist some instances x = x 1 , x 2 on which P (y = +1|x 1 ) is very different from P (y = +1|x 2 ). Thus, f * 1 is not perfectly compatible with f * 2 and d(f * 1 , f * 2 ) denotes the difference between f * 1 and f * 2 .
denote the error rate of the optimal classifier f * v , we have the following Proposition 1.
Proof. Given an example ( x 1 , x 2 , y), So we get Remark: Proposition 1 states that when the view is insufficient, the optimal classifier trained on this view will mistakenly classify some instances. The larger the insufficiency is, the worse the performance of the optimal classifier will be.

Learning Approximation of Optimal Classifier with Complementary Views
Usually, co-training allows one classifier to label unlabeled instances for the other. For insufficient views, in each view there are some instances which can

Algorithm 3 Margin-based co-training with insufficient views
Input: Labeled data L, unlabeled data U , and two hypothesis spaces F 1 and Output: F C 1 and F C 2 . Initialize: Set 0 = L; by minimizing the empirical risk on i with respect to view X v and set T i = ∅; not provide sufficient information for predicting the label. So we should check how much information each instance can provide. We use the confidence of the prediction on an instance to measure the information. When the confidence is no less than some preset threshold, we use the predicted label as its pseudo-label and add it into the training set. Since each view is insufficient and only provides partial information, we use the newly labeled unlabeled instances which are labeled by both classifiers as the retraining data, and the process is described in Algorithm 3. However, as mentioned in Section 2 if there is no prior knowledge about the relationship between hypothesis space and unlabeled data, it is hard to guarantee that selecting confident instances to label is helpful. In marginbased algorithms, margin can be used to measure the confidence. Intuitively, it is likely that similar hypotheses tend to have similar margin outputs, i.e., two hypotheses with small error difference should have small margin difference.
With this intuition, we give the following Definition 4.

Definition 4 (Margin Lipschitz)
Definition 4 states that the label predicted by weak classifiers with large margin is likely to be the same as the label predicted by the optimal classifier.
Thus, the confident instances would help find the optimal classifier. Here we give two examples that satisfy the Margin Lipschitz definition.
Example 1 Image that the instances in X v are distributed uniformly over the unit ball in R dv and that the underground labels are determined by a linear hyperplane w * v going through the origin, i.e., y = sign(w * v · x v ) for any (x v , y). It can be verified that Definition 4 holds with the constant C L v ≥ π.
Example 2 Image that the instances in X v are distributed uniformly over the unit ball in R dv and that the underground labels are determined by a random variable β (β = +1 with probability 1 − η and β = −1 with probability η) and a linear hyperplane w * v going through the origin, i.e., y = β · sign(w * v · x v ) for any (x v , y). Here the variable β is exploited to simulate the instances with insufficient features due to feature noise. It can be verified that Definition 4 also holds with the constant C L v ≥ π.
To quantify the amount of the confident instances, we give the following Definition 5.
and let ν(γ 1 , γ 2 , F 1 , F 2 ) denote the probability mass on the instances which are labeled with large margin just by one view, then ν(γ 1 , γ 2 , F 1 , F 2 ) measures the disagreement between two views with respect to margins γ 1 and γ 2 , we call it margin-based disagreement. When ν(γ 1 , is large, the two views could help each other strongly by providing diverse confident information; while when ν(γ 1 , γ 2 , F 1 , F 2 ) is small, the two views only help each other little since they provide almost the same information. µ(γ 1 , γ 2 , F 1 , F 2 ) denotes the probability mass on the instances which are labeled with large margin by one of the two views. If the two views have large margin-based disagreement ν(γ 1 , γ 2 , F 1 , F 2 ), µ(γ 1 , γ 2 , F 1 , F 2 ) is large. For the extreme case that µ(γ 1 , γ 2 , F 1 , F 2 ) = 1, i.e., each unlabeled instance can be labeled with large margin by one of the two views, we say that the two views are complementary views, since they provide complementary information. For this extreme case, we have the following Theorem 11.
Theorem 11 Suppose the hypothesis space F v (v = 1, 2) satisfies Definition 4, let F L v ⊆ F v denote the hypotheses minimizing the empirical risk on the initial labeled data L, Proof. Since µ(γ 1 , γ 2 , F L 1 , F L 2 ) = 1, after 1 round all unlabeled instances in U are assigned with pseudo-labels and added into the data set 1 . Then classifier set F 1 v is got by minimizing the empirical risk on 1 with view X v . For , with Definition 4 we know that f v and f * v make the same prediction on x v . So for any example x 1 , x 2 , y ∈ 1 , either y = sign f * 1 (x 1 ) or y = sign f * 2 (x 2 ) holds. Here we consider the worst case that , so learning a classifier with error rate no larger than err(f com v ) + is no harder than learning a classifier with error rate no larger than err(f * v ) + . Now we regard f com v as the optimal classifier in F v and neglect the probability mass on the hypothesis whose error rate is less than err(f com v ). Since the classifiers in F C v minimize the empirical risk on 1 which is an i.i.d sample with size of |L| + |U | and Remark: Theorem 11 states that if the two views are complementary views, i.e., every unlabeled instance in U can be labeled with large margin by one of the two views, co-training could output the nearly good hypothesis set F C 1 and F C 2 . Sometimes the pseudo-label which is the same as the prediction of the optimal classifier in view X v is not helpful in achieving the optimal classifier in view X 3−v , since there exists the difference d(f * 1 , f * 2 ) between the two optimal classifiers in the two views. Thus, the hypothesis in F C v is not very close to the optimal classifier f * v . To achieve the good approximation of the optimal classifier, some prior knowledge about the optimal classifier needs to be known, which is shown as follows.
Definition 6 states that for an example if one view can provide much information about it, it will be correctly classified by the optimal classifier in this view. Thus, we give the following Theorem 12.
Theorem 12 Suppose the hypothesis space F v (v = 1, 2) satisfies Definition 4, let F L v ⊆ F v denote the hypotheses minimizing the empirical risk on the initial labeled data L, Proof. For x = x 1 , x 2 , y denotes its pseudo-label.
with Definition 4 we know that f v and f * v make the same prediction on x v and |f * v (x v )| ≥ γ v . So we get P (y = +1|x v ) − 1 2 ≥ γ v /2. Then with Definition 6 we know that y = sign f v (x v ) = sign f * v (x v ) = y. So we get that the pseudo-label of any example in 1 is the same as its underground label. Since µ(γ 1 , γ 2 , F L 1 , F L 2 ) = 1, we know that all unlabeled instances in U are assigned with underground labels and added into 1 . So 1 is an Remark: Theorem 12 states that if the two views are complementary views with respect to larger margins γ 1 and γ 2 , co-training could output the -approximation of the optimal classifier.

Learning Approximation of Optimal Classifier with Non-Complementary
Views However, in real-world applications not all insufficient views are complementary, i.e., µ(γ 1 , γ 2 , F L 1 , F L 2 ) is smaller than 1. With Definition 4 we know that the threshold γ v (v = 1, 2) which guarantees the quality of the confident instances is related to the error rates of weak hypotheses. An intuitive way to get more confident instances to augment the training data is updating the weak hypotheses with newly labeled confident instances and adaptively decreasing the margin threshold, which is shown in Algorithm 4. When µ(γ 1 , γ 2 , F L 1 , F L 2 ) is smaller than 1, it will make co-training suffer from the sampling bias, since the training set in each view might not be an i.i.d sample from the marginal distribution D X . Now we give the following definition to approximately bound the difference between two training samples.

Algorithm 4 Adaptive margin-based co-training with insufficient views
Input: Labeled data L, unlabeled data U , two hypothesis spaces F 1 and F 2 , by minimizing the empirical risk on i with respect to view X v and set T i = ∅; Let f Λ denote the hypothesis minimizing the empirical risk on Λ, R * be the error rate of the optimal classifier and R be the upper bound on the error rate of the hypothesis minimizing the empirical risk on an i.i.d. sample with size of |Λ| Definition 8 states that the error difference between the classifier trained with possibly biased sample and the optimal classifier can be bounded by that between the classifier trained with unbiased sample and the optimal classifier times an exponential function of the approximate KL divergence. Here we give an example to show when the sampling bias assumption holds in co-training.
Example 3 Suppose that the two views are conditionally independent to each other, then Definition 8 holds. In Algorithm 4, the training set i is a subset of L∪U and consists of the instances whose margins are no less than the threshold.
That the two views are conditionally independent means the hypothesis in the first view is independent of the hypothesis in the second view to make predictions, i.e., f 1 (x 1 ) is independent of f 2 (x 2 ) for any x = x 1 , x 2 . So it can be regarded that the instances in i are randomly drawn from L ∪ U , i.e., i is an i.i.d sample. Thus, err(f i ) − R * ≤ R − R * ≤ (R − R * ) · exp(n/| i |). This example can be relaxed to the case that the two views are weakly dependent if the prior knowledge about the margin outputs over the two views is known.
Let Ω be an i.i.d sample size of m, it is well-known that [46] there exists an universal constant C such that for δ ∈ (0, 1) we have err( ) with probability 1 − δ for any f v minimizing the empirical risk on Ω. Generally, there may exist more than one hypothesis which have the same empirical risk. Let H Ω v denote the set of hypotheses which have the same minimum empirical risk on Ω, it is reasonable to assume that max , which means the PAC-bound is tight and the maximum error rate of the hypotheses which minimize the empirical risk on Ω is proportional to 1 √ m . We are now ready to give the theorem on co-training with insufficient views.
Theorem 13 Suppose the hypothesis space F v (v = 1, 2) satisfies Definition 4, let i denote the training set in the i-th round of Algorithm 4, F i v ⊆ F v denote the set of hypotheses minimizing the empirical risk on i , n = |L| + |U | and For ∈ (0, 1 2 ) and δ ∈ (0, 1), if Definitions 6 and 7 hold, with the proof in Theorem 12 we know that the pseudolabel of any example in 1 is the same as the underground label. Since L ∪ U is a large i.i.d sample from the marginal distribution D X , so with Definition 8 we Thus, the pseudo-label of any example in 2 is the same as the underground label. Similarly, for all instances in U are labeled with underground labels. So i is an i.i.d sample with size of √ m1 must be larger than 0, i.e., Remark: Theorem 13 states that if the two views provide diverse information, , co-training could improve the performance of weak hypotheses by exploiting unlabeled data. This result tells that the diverse information between the two views plays an important role in co-training with insufficient views.

Assumption Relaxation and Discussions
Our result is based on a little bit strong Margin Lipschitz assumption, which is caused by the fact that the learning task with insufficient views for semisupervised learning is very difficult. In this section, we try to give a heuristic analysis for the case where the Margin Lipschitz assumption is relaxed. Instead, we give the following Probabilistic Margin assumption: for 1 2 Here φ : [ 1 2 , 1] → [0, 1] is a monotonically decreasing function, e.g., φ(γ) = β ln( 1 γ ) for some parameter β. Probabilistic Margin assumption allows for small label noise in the examples labeled with large margin. Considering the worst case of the influence of label noise, i.e., the examples with noisy labels are completely inconsistent with the optimal classifier, it can be found that when the two views provide diverse information, co-training could output the hypotheses whose error rate are close to η v + β ln( 1 γv ), which is smaller than the error rate of the classifier trained only on the small initial labeled data set L. This shows that co-training could improve learning performance by exploiting unlabeled data even with insufficient views.
Now we discuss what influence the view insufficiency will bring to the learning process. Since we could not know the distribution and the posterior probability ϕ v (x v ) (v = 1, 2) of the example space in advance, it is difficult to analyze the general case. We focus on the famous Tsybakov condition [47] case that for some finite C 0 v > 0, k > 0 and 0 < t ≤ 1/2, where small k implies large view insufficiency Υ, and give a heuristic analysis to illuminate the relationship between view insufficiency and diversity. Considering the worst case of Tsybakov condition for the fixed parameter k, i.e., P ϕ v ( is the output margin of the optimal classifier f * v , with the intuition that similar hypotheses tend to have similar margin outputs, the magnitude of the instances with margin larger than γ in view X v is probably quantifies the amount of instances labeled with large margin by view X v . Considering that µ = ν+µ1+µ2 2 , when ν is fixed, if the view insufficiency increases, the confident information µ provided by the two views decreases; when µ 1 and µ 2 are fixed, if the two views have large margin-based disagreement ν, the confident information µ provided by the two views increases, which shows that the margin-based disagreement ν is important to co-training. For understanding the magnitude of µ better, we give the following example. There are adequate unlabeled instances in realworld semi-supervised applications, suppose we have n = |L| + |U | = 1000 and L = 12, similarly to the empirical study on co-training in [11], µ = 3 √ n 2 |L|−|L| n−|L| at the first step in Theorem 13 should be 22%. With respect to µ = ν+µ1+µ2 2 , if the two views provide diverse information (ν is large), the weak hypothesis in each view predicting about 18% (even less) of the unlabeled instances with large margin might be enough to guarantee that µ ≥ 22%, which is common in real-world applications.
In our result, the margin threshold +γ v depends on several parameters. Generally, the optimal classifier would make mistakes only when the instances are close to the boundary, i.e., P (y = +1|x) is close to 1/2. So γ v is close to 0. (R v − η v ) depends on the number of initial labeled data L and is close to 1/2. Thus, γ v is close to 1/2.

Connection to Co-Regularization
In semi-supervised learning, co-regularization allows for views with partial insufficiency, but it assumes that the two views provide almost the same information. Unfortunately, in real-world applications each view may be corrupted by different kinds of noise, it is unreasonable to assume that the two views provide almost the same information. When the two views are corrupted by different noise or provide diverse information, the two optimal classifiers are no longer compatible with each other and the performance of co-regularization will be influenced since it strongly encourages the agreement between two views.
Sridharan and Kakade [48] used the conditional mutual information I(A : B|C) to measure how much knowing A reduces the uncertainty of B conditionally on already knowing C, they assumed that I(Y : holds for some small inf o > 0, and provided an information theoretic framework for co-regularization which minimizes the following co-regularized loss for .
R L is the empirical risk with respect to the labeled data L and D U is the empirical disagreement with respect to the unlabeled data U . Note that I(Y : ≤ inf o means that if we already knew view X v then there is little more information that we could get from view X 3−v about Y, i.e., the two views provide almost the same information. Sridharan and Kakade [48] showed that the excess error between the output hypothesis of co-regularization and the optimal classifier is punished by the term √ inf o . This implies that it is hard for co-regularization to find the -approximation of the optimal classifier when the two views are insufficient and provide diverse information. Now we give the following Proposition 2 to show that co-regularization may never output the approximations of the optimal classifier.
the hypotheses minimizing the empirical risk on the labeled data L and holds for sufficiently large |U |, it is easy to get Proposition 2 proved.
Remark: Let us give an intuitive explanation to Proposition 2. It states that co-regularization prefers to output a pair of hypotheses which minimizes the disagreement on the unlabeled data rather than the optimal classifier. Its performance will be influenced by the incompatibility between the two views, especially when the unlabeled data are very large while the labeled data are small.
It might contribute to understanding the difference between co-regularization and co-training. For two views which provide almost the same information, the optimal classifiers in the two views are compatible with each other, and co-regularization could find the optimal classifiers by minimizing the error rate on labeled data and the disagreement on unlabeled data over two views; for two views which provide diverse information, we show that co-regularization may fail, while co-training which iteratively utilizes the confident information in one view to help the other is a good learning strategy.

Why Combination of Classifiers is Good
Usually, the two classifiers in disagreement-based approaches are combined to make predictions in practice, e.g., the two classifiers in co-training [11] are combined by multiplying the posterior probabilities and the empirical results showed that the combination is better than the individual classifiers. However, there is no theoretical study to explain why and when the combination can be better than the individual classifiers.
Let h com denote the combination of the individual classifiers h 1 and h 2 , then the combination h com by multiplying the posterior probabilities in [11] is formulated as Actually, this combination strategy can be generalized to any margin-based classifiers. Let F: X → [−1, +1] denote the hypothesis space, the classification rule on x ∈ X induced by a hypothesis f ∈ F is sign f (x) and |f (x)| is the , the classification rule sign f (x) is equal to maximizing the posterior probability P (y = +1|x), i.e., f (x) > 0 ⇔ P (y = +1|x) > 1 2 . So the combination strategy in Equation 31 for f 1 and f 2 is formulated as i.e., f com (x) = sign(f 1 (x) + f 2 (x)). It implies that f com follows the decision of the hypothesis which has larger margin and the error rate of f com is: Considering the construction of f com , it is easy to find that when f 1 (x) and f 2 (x) make the same prediction on x, f com will follow the both's decision. Let DIS(f 1 , f 2 ) = {x ∈ X : sign(f 1 (x)) = sign(f 2 (x))}, i.e., the disagreed instance set by f 1 and f 2 , the error rate of f com depends on its performance on DIS(f 1 , f 2 ) and the following Proposition 3 holds for f com .

Proposition 3
The error rate of f com satisfies the following lower bound: Proof. The worst case of f com is making incorrect predictions for all instances in DIS(f 1 , f 2 ), it is easy to get Proposition 3 proved.
Remark: Proposition 3 states that larger disagreement will lead to better lower bound for the combination of the individual classifiers.
When |f G (x)| is larger than |f R (x)|, the combination f com gives the correct prediction on x. Intuitively, f com works in the following way: if the margin (the confidence) is reliable, i.e., large margin implies high label quality, the incorrect prediction happens on the instance which has small margin, i.e., |f R (x)| is small. If f 1 and f 2 are not very related to each other, the probability that both hypotheses have small margin on x is small, i.e., |f G (x)| is large with great probability. Thus, |f G (x)| > |f R (x)| holds with great probability and f com gives the correct prediction on x. Define the following confidence gain C G (f 1 , f 2 ) and confidence risk C R (f 1 , f 2 ): C G (f 1 , f 2 ) is the integral correct margin of f 1 and f 2 over DIS(f 1 , f 2 ), while C R (f 1 , f 2 ) is the integral incorrect margin of f 1 and f 2 over DIS(f 1 , f 2 ). If C G (f 1 , f 2 ) is much larger than C R (f 1 , f 2 ), |f G (x)| > |f R (x)| may hold with great probability for x ∈ DIS(f 1 , f 2 ).
The margin-based classifiers try to classify instances correctly with large margins, however, there may exist some instances on which the margins are small, e.g., the instances close to the boundary. Intuitively, these instances with small margins are not too many, maybe bounded by some function. Suppose that the distribution of |f G (x)| over DIS(f 1 , f 2 ) satisfies the condition: for C T > 0, k ≥ 0 and all 0 < t < 1 such that It indicates that the amount of correctly classified instances with small margins is bounded by a polynomial function, and larger k will lead to less small margins. This condition is inspired by the famous Tsybakov condition [47] for |f R (x)| k p(x)dx.
Proof. For x ∈ DIS(f 1 , f 2 ), without loss of generality, we assume that f 1 gives the correct prediction while f 2 gives the incorrect prediction, with the assumption that f 1 and f 2 make predictions on it independently and the condition in Equation 36 we get P (I(f com (x) = y)) = P (I(|f 1 (x)| < |f 2 (x)|)) = P (I(|f G (x)| < |f R (x)|)) ≤ C T · |f R (x)| k .
Then, we get P x∈DIS(f1,f2) (f com (x) = y) = x∈DIS(f1,f2) P (I(f com (x) = y))p(x)dx It is easy to find that P (x,y)∈D (f com (x) = y) = P (x,y)∈D (sign(f 1 (x)) = y ∧ sign(f 2 (x)) = y) + P x∈DIS(f1,f2) (f com (x) = y) Remark: Let us give a comprehensive explanation to Theorem 14: for k = 1, x∈DIS(f1,f2) |f R (x)| k p(x)dx = C R (f 1 , f 2 ), it indicates that if the individual classifiers have large disagreement d(f 1 , f 2 ) and small confidence risk C R (f 1 , f 2 ), the combination will have low error rate. It implies that for good combination, incorrect predictions should have small margins. The following Corollary 1 shows when the combination is better than the individual classifiers. holds and err(f 1 ) ≤ err(f 2 ), if err(f com ) is smaller than err(f 1 ).
Remark: Corollary 1 states that if the confidence risk C R (f 1 , f 2 ) is small (depending on the disagreement between the individual classifiers), i.e., incorrect predictions have small margins, the combination is better than the individual classifiers.

Discussion and Conclusion
The disagreement-based semi-supervised learning [14,18] was named to assemble the approaches which generate multiple weak classifiers and let them label unlabeled instances to augment the training data, including co-training and single-view disagreement-based algorithms. In these approaches, unlabeled data serve as a kind of "platform" for information exchange and the disagreement among multiple weak classifiers is exploited during the learning process. If there is no disagreement, the learning process will degenerate into self-training.
In this article, we aim at presenting a theoretical foundation of disagreementbased approaches.
One basic issue of the theoretical foundation is why and when the disagreementbased approaches could improve learning performance by exploiting unlabeled data. In Section 2.1, we provide the theoretical analysis on disagreement-based approaches and give bounds on the error rates of the classifiers in the learning process. Furthermore, we prove that the disagreement will decrease after the disagreement-based process is initiated. Based on these results, it can be found that the disagreement-based approaches could improve learning performance given that the two initial classifiers trained with the initial labeled data have large disagreement. The empirical results in Section 2.3.2 verify that larger disagreement will lead to better performance improvement.
For disagreement-based approaches, it is often observed that the performance of the classifiers cannot be improved further after a number of rounds in empirical studies. We prove that the disagreement and error rates of the classifiers will converge after a number of rounds in Section 2.2, which provides the theoretical explanation to the observation. The empirical results in Section 2.3.1 validate that the disagreement between the classifiers will decrease or converge as the learning process goes on. When the disagreement converges, the error rates of the classifiers also seem to converge, e.g., Figure 2(d) to (f); while when the disagreement does not converge, the error rates of the classifiers seem to decrease as the disagreement decreases, e.g., Figures 2(g) to (i).
It will be an impressive result if the sufficient and necessary condition for disagreement-based approaches can be found. Toward this direction, we present a theoretical graph-based analysis on co-training in Section 3, in which the classifier in each view is viewed as label propagation and thus co-training is viewed as a combinative label propagation over two views. Based on this analysis, we get the sufficient and necessary condition for co-training. Note that such graphbased analysis on co-training only cares the two graphs rather than where these graphs come from, and therefore it is also applicable to single-view disagreementbased approaches when there is only one view but two graphs can be obtained in different distance matrices. Recall that the analysis in Section 2.1 provides a sufficient condition for disagreement-based approaches, however, it is different from the analysis in Section 3. The analysis in Section 3 focuses on the transductive setting, since studying the sufficient and necessary condition is a very hard problem; while the analysis in Section 2.1 focuses on the non-transductive setting, which is applicable to general learning process.
All previous theoretical analyses on co-training assumed that each view is sufficient to learn the target concept, however, in many real-world applications, due to feature corruption or various feature noise, neither view can provide sufficient information. So we present a theoretical analysis on co-training with insufficient views which is much more challenging but practical in Section 4, especially when the two views provide diverse information. We prove that if the two views have large margin-based disagreement, co-training could succeed in outputting the approximation of the optimal classifier by exploiting unlabeled data even with insufficient views. We also give some implications for understanding the difference between co-training and co-regularization. In the analysis of Section 4, we focus on the margin-based classifiers and assume that large margin leads to high label quality, since co-training with insufficient views is a much harder problem, we need some prior knowledge about how much information each instance can provide to learn the target concept.
Since the two classifiers in disagreement-based approaches are usually combined to make predictions, we present a theoretical analysis to explain why and when the combination can be better than the individual classifiers in Section 5.
We focus on the margin-based classifiers and prove that when the individual classifiers have large disagreement, diverse margin output and small confidence risk, i.e., incorrect predictions have small margins, the combination would have low error rate.
Our theoretical result in Section 2 indicates that data with two views are not necessary to improve learning performance by exploiting unlabeled data, but it does not mean that we do not need two views at all. When the data have two views, we can get better result. For example, if the data have two conditionally independent views, a single labeled example is sufficient to find the target concept [27,49]. It is noteworthy that in previous semi-supervised learning studies, the disagreement-based and graph-based approaches were developed separately.
While our theoretical result in Section 3 provides a possibility of bringing them into a unified framework, which will be an interesting research direction.