Semi-Supervised Classification: Mixture models and co-training

Final Degree Dissertation Degree in Mathematics Semi-Supervised Classification: Mixture models and co-training Author: Bruno ´ Alvarez Ortega Supervisor: Javier C´arcamo Urtiaga June 2025 Contents Introduction v 0.1 The case for semi-supervised classification . . . . . . . . . . . . . . . . . . v Reflexion vii 1 Preliminaries 1 1.1 Supervisedlearning............................... 1 1.2 Unsupervisedlearning ............................. 2 1.3 Classificationerror ............................... 3 2 Semi-Supervised Learning 5 2.1 Generative mixture models . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Expectation maximization algorithm . . . . . . . . . . . . . . . . . . . . . 9 2.3 Classification rule: log-probability ratio . . . . . . . . . . . . . . . . . . . 12 2.4 Somecaveats .................................. 13 2.5 Co-training ................................... 14 2.6 Hypotheses of co-training . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3 Computational simulations 21 3.1 Introduction................................... 21 3.2 First set of simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3 Second set of simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.4 Example: effects of an incorrect model . . . . . . . . . . . . . . . . . . . . 25 3.5 A co-training simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4 Real life applications 31 4.1 Optical galaxy classification . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 Case study: train occupancy data . . . . . . . . . . . . . . . . . . . . . . . 35 4.3 Self-training: a final semi-supervised approach . . . . . . . . . . . . . . . . 38 4.4 Conclusion ................................... 40 A R and Python code 41 Bibliography 43 iii Introduction 0.1 The case for semi-supervised classification Traditionally, classification has been performed by supervised learning algorithms trained on manually labelled data to produce a good discriminator for future, unseen data. However, this data is often expensive to obtain in large quantities. With the advent of ever increasing access to large amounts of data, most of it unlabelled, it has become necessary to leverage this type of information effectively. In this sense, semi-supervised classifications aims to bridge the gap between supervised and unsupervised learning by developing classifiers that can make use of both the labelled and unlabelled data to improve classification performance. Another motivation for the understanding of semi-supervised learning is its relationship with human intelligence. For example, when in the early years of a child parents point to, for instance, a small animal a say “dog”, it is the combination of this labelled data and future passive (unlabelled) observations of a dog that inform a human being of what a dog is. This is studied by cognitive science, were classification algorithms inform how humans think and learn. In this dissertation, we will explore semi-supervised classification, starting in chapter 1 by reviewing some concepts relevant to this work. In chapter 2, we lay down the theoretical groundwork for the two semi-supervised methods studied: mixture models and co-training. In the second half, chapters 3, and 4 will put into practice these two approaches, with some simulations being performed in the former to test the limits of theory. Finally, in chapter 4, we apply this knowledge in three diverse case studies: galaxy classification, train occupancy analysis and sentiment recognition. The goal of this dissertation is to research the evolving field of statistical learning through the perceptive of the semi-supervised learning paradigm. All code developed for this work is provided in the folder CODE, with a brief guide in Appendix A. v Reflexion One of the biggest sins that a young aspiring mathematician can commit is ask about the ‘usefulness’ of the subject of study. The sometimes harsh response from the professors is not without some sense of truth. Sometimes knowledge by itself is valuable enough. But sooner rather than later every mathematician must reckon with one harsh reality: that the beautiful world of mathematics where everything makes sense, full of beautiful and rewarding theories has a direct impact on our societies. Indeed, as will became clear throughout this dissertation, the topic at hand, semisupervised classification, can build towards automation, which will inevitably lead to more decent jobs and economic development (SDG 8). It also provides improvements in efficiency and understanding of the complex systems that we operate in, aiding in the development of green and sustainable industries and infrastructures (SDGs 9, 11). Classification is also used daily for medical diagnosis, contributing to the betterment of health and welfare of society (SDG 3). Increasingly, automatic classification has taken a more direct role in our lives. In Spain, for instance, classification algorithms are used to determine the level of risk that women victim of gender violence face to provide them with the resources they need, with the intent of eradicating this type of symptom of gender inequality (SDGs 5, 10). History is often written for us because we shrink from our burden as citizens. We must take responsibility for our knowledge and use it to pursue the goals outlined by the UN simply because it is the right thing to do. For sometimes, the risk of doing nothing becomes the greatest risk of all. vii Chapter 1 Preliminaries We begin by discussing some concepts related to statistical learning, in particular those concerning classification. Definition 1.0.1. Adata point or instance x= (x1, . . . , xd)∈Rdis the multivariate representation of each individual in a sample of size n∈N. Instances may also be accompanied by a label,y∈ Y, that represents the class to which xbelongs. In general, we may also use the notation Xto represent the set of instances. The sample or input data to our models, whether it is labelled, unlabelled or partially labelled, is often referred to as the training sample or S. From often vast amounts of data contained in these training samples, one would like to extract valuable knowledge. The means and ends of statistical learning vary greatly. For now, we discuss the two main paradigms in this field: supervised and unsupervised learning. 1.1 Supervised learning The main task of supervised learning is classification: Given a set Yof classes and an instance x, our goal is to classify this data point in one of those classes (also called populations), since we believe the features in xhave an influence on its class. In this context, all instances are labelled. The pairs (x,y) represent the fundamental characteristic of this paradigm: it is supervised in the sense that labels are given by a “supervisor”. A typical example may be the following. Example 1.1.1. All banks have at their disposal the records of past loans, that is, the data corresponding to the client: sex, age, marital status, job, income, deposits, etc. And, on the other hand, the result of the transaction: whether the bank made a profit (i.e. the loan plus interest were paid back) or if the client went bankrupt. Given a new client, from whom we know all the above-mentioned features, we are interested in classifying it in one of the two categories: low-risk, if the transaction will likely be successful, 1 82.1. Generative mixture models Due to the likelihood function being positive and the properties of the logarithm (continuous and monotonic) we always consider the log-likelihood. Recall that in the context of semi-supervised learning, the training sample is S= {(x1, y1), ..., (xl, yl),xl+1, ..., xl+u}. Therefore, the log-likelihood function is defined as log L(S|θ) = log l Y i=1 p(xi, yi|θ) l+u Y i=l+1 p(xi|θ)! = l X i=1 log p(xi, yi|θ) + l+u X i=l+1 log p(xi|θ) = l X i=1 log p(yi|θ)p(xi|yi, θ)+ l+u X i=l+1 log p(xi|θ), (2.5) where the last equality is justified by the definition of the conditional probability. For the terms on the right, corresponding to the unlabelled data points, the marginal probabilities p(x|θ) are considered, that are, by the total probability theorem: p(xi|θ) = X y∈Y p(y|θ)p(xi|y, θ) (2.6) Hence, combining (2.5) and (2.6), the log-likelihood function is as follows. log L(S|θ) = l X i=1 log p(yi|θ)p(xi|yi, θ) + l+u X i=l+1 log X y∈Y p(y|θ)p(xi|y, θ). (2.7) It is easy to see that the log-likelihood that we are trying to maximize is only different from that of the supervised learning for the terms in the second sum. This is a critical difference, since unlike in such a learning paradigm, the optimization problem in semi-supervised learning is not necessarily a convex problem, which makes it more challenging to solve. In addition, the solution of the equation ∇log L(S|θ) = 0cannot, in general, be explicitly calculated, and therefore a numerical method is required. In this context, the standard method of solving for the MLE problem is the Expectation Maximization algorithm (EM), which finds a local maximum of the objective function presented in (2.7). Chapter 2. Semi-Supervised Learning 9 2.2 Expectation maximization algorithm Definition 2.2.1. Given a training sample S={(x1, y1), ..., (xl, yl),xl+1, ..., xl+u}, we call hidden variables to the unknown labels of the unlabelled instances, H={yl+1, ..., yl+u}. The expectation maximization algorithm is an iterative method which finds a local optimum for θ, the model parameters. Given some initial parameter values, ˆ θ(0), the method repeats the following two steps until variation in the log L(S|θ) is below a certain ε. (i) Expectation step: The expected value of the hidden variables in His calculated. This can be thought of as “soft assignments” of the labels to instances xl+1, ..., xl+u. Formally, we compute p(t)(H), which by definition is p(H|S,ˆ θ(t)). In Algorithm 1 , step 2a, a formula for the computation of these probabilities is presented for the case of a two component GMM model. (ii) Maximization step: These “soft labels”, ˆ H(t), are used to update the parameters, by calculating the MLE for {(x1, y1), ..., (xl, yl),(xl+1,ˆy(t) l+1), ..., (xl+u,ˆy(t) l+u)}. In other words, ˆ θ(t+1) is calculated, such that it maximizes Q(θ|ˆ θ(t)) = Elog pS,ˆ H(t)|θ. Depending on the initial conditions, ˆ θ(0), the local maximum that EM finds may vary. Usually, ˆ θ(0) is chosen as the MLE for the labelled data called, Slabelled. Equivalently, ˆ θ(0) = arg max θlog L(Slabelled|θ) = arg max θ l X i=1 log p(yi|θ)p(xi|yi, θ).(2.8) We now give a lemma necessary to prove an important result of the EM algorithm. Lemma 2.2.1. (Gibb’s inequality) Let {p(x)}x∈X and {q(x)}x∈X be two discrete probability distributions. Then, −X x∈X p(x) log q(x)≥ − X x∈X p(x) log p(x).(2.9) Gibb’s inequality is often stated this way because of its relation to the concept of entropy or quantity of information of a random variable. See [3, pp. 287 - 289] for more details and the corresponding proof. Theorem 2.2.2. The expectation maximization method improves the log-likelihood, log L(S|θ), in every successive iteration. Proof. By definition of conditional probability, p(H | S, θ) = p(S,H | θ) p(S | θ)=⇒log p(S | θ) = log p(S,H | θ)−log p(H | S, θ). 10 2.2. Expectation maximization algorithm We consider the expected value for all possible Husing the estimation for the parameters of the current iteration. This is done through multiplication by p(H | S,ˆ θ(t)) on both sides, and taking the sum, log p(S | θ) = X H p(H | S,ˆ θ(t)) log p(S,H | θ) −X H p(H | S,ˆ θ(t)) log p(H | S, θ). Note that the left-hand side stays the same since it is a constant. In the right-hand side of the equation, the first sum is what we have defined as Q(θ|ˆ θ(t)) (the expected value of the log-likelihood as a function of θ, given the current estimate, ˆ θ(t)) and minus the second sum, which we denote as H(θ|ˆ θ(t)). In this way, we have the following identity, log p(S | θ) = Q(θ|ˆ θ(t)) + H(θ|ˆ θ(t)).(2.10) Since equality (2.10) is true for any value of θ, we can make θ=ˆ θ(t+1) and θ=ˆ θ(t)to obtain, respectively, log p(S | ˆ θ(t+1)) = Q(ˆ θ(t+1) |ˆ θ(t)) + H(ˆ θ(t+1) |ˆ θ(t)) and (2.11) log p(S | ˆ θ(t)) = Q(ˆ θ(t)|ˆ θ(t)) + H(ˆ θ(t)|ˆ θ(t)).(2.12) Subtracting equation (2.12) to (2.11) yields log p(S | ˆ θ(t+1))−log p(S | ˆ θ(t)) = Q(ˆ θ(t+1) |ˆ θ(t))−Q(ˆ θ(t)|ˆ θ(t)) +H(ˆ θ(t+1) |ˆ θ(t))−H(ˆ θ(t)|ˆ θ(t)).(2.13) Using Lemma 2.2.1 (Gibb’s inequality) for probability distributions P={p(H | S,ˆ θ(t))}H and Q={p(H | S,ˆ θ(t+1))}Hwe have that H(ˆ θ(t+1) |ˆ θ(t))≥H(ˆ θ(t)|ˆ θ(t)) and thus, log p(S | ˆ θ(t+1))−log p(S | ˆ θ(t))≥Q(ˆ θ(t+1) |ˆ θ(t))−Q(ˆ θ(t)|ˆ θ(t)).(2.14) Finally, since in every iteration in the maximization step we calculate ˆ θ(t+1) to improve Q(ˆ θ(t+1) |ˆ θ(t)), and knowing that log p(S | θ) is the log L(S|θ), we obtain the desired result. In the following page, we present the formulation of the EM algorithm for a twocomponent Gaussian mixture model (from now on GMM), as in Example 2.1.1. We aim to estimate the prior probabilities, π0,π1and the parameters of the two normal populations, (µ0,Σ0) and (µ1,Σ1). All in all, our model parameters are θ={πj, µj,Σj}j∈{0,1}. Chapter 2. Semi-Supervised Learning 11 Algorithm 1. EM for GMM: Input: Sample S={(x1, y1), ..., (xl, yl),xl+1, ..., xl+u}, and tolerance ε > 0. (i) Initialization: Make t= 0 and ˆ θ(0) ={ˆπ(0) j,ˆµ(0) j,ˆ Σ(0) j}j∈{0,1}, the MLE for the labelled data. For instance, ˆπj=|{xi∈Slabelled :yi=j}| |Slabelled|. (ii) Iterate the following steps until convergence of the log L(S|θ) is achieved. Equivalently, the process is stopped if log L(S | ˆ θ(t+1))−log L(S | ˆ θ(t))≤ε . (a) Expectation step: For all the unlabelled instances, i∈ {l+ 1, . . . , l +u}, calculate using Bayes’ rule, γij := p(yj|xi,ˆ θ(t)) = ˆπ(t) jN(xi; ˆµ(t) j,ˆ Σ(t) j) P1 k=0 ˆπ(t) kN(xi; ˆµ(t) k,ˆ Σ(t) k), j = 0,1. These values can be thought of as fractional labels estimated for the unlabelled data points. On the other hand, for the labelled instances, consider the true assignments, that is, for i∈ {1, . . . , l}, γij =(1,if yi=j , 0,otherwise . (b) Maximization step: Calculate ˆ θ(t+1), for j∈ {0,1}as the MLE for the training sample Swith the fractional labels γ. lj= l+u X i=1 γij , ˆµ(t+1) j=1 lj l+u X i=1 γijxi, ˆ Σ(t+1) j=1 lj l+u X i=1 γij(xi−ˆµ(t+1) j)t(xi−ˆµ(t+1) j), ˆπ(t+1) j=lj l+u. (iii) Update t:= t+ 1. Return to step (ii). Output: MLE {ˆπj,ˆµj,ˆ Σj}j∈{0,1}. 12 2.3. Classification rule: log-probability ratio The EM algorithm is an example, in the field of computer science, of a self-training algorithm, or an algorithm that teaches itself. This is because for the unlabelled instances, an estimate of their labels is calculated, which are then used to augment the estimation of the model parameters, using MLE as if the whole sample was labelled. The problem of the EM algorithm not finding the global optimum of the log-likelihood but rather a local maximum can be dealt with in a number of different ways. One approach is what is often referred to as a random start, where the initial values for EM, ˆ θ(0), are randomly chosen. This process is repeated, and only the biggest log-likelihood achieved is considered. It is clear that this is just a heuristic approach and does not guarantee the optimal solution. Another approach would be utilizing numerical methods for solving unconstrained optimization problems, such as gradient descent, which again does not guarantee the global optimum if the solution space is not convex and would also require the random start methodology. 2.3 Classification rule: log-probability ratio We recall that our original objective for generative mixture models was classification. Since any classification task where there are more than two classes can be reduced to the problem of binary classification, let us assume that Y={0,1}, which we refer to as the set of the 0 and 1 class. In order to classify each x∈ S or any new instance x∈Rd, so as to assess the accuracy of classification, by the total probability theorem we have, p(x|y= 0)p(y= 0) + p(x|y= 1)p(y= 1) = p(x).(2.15) This expression allows us to estimate the probability of an instance coming from the 1 class: p(y= 1|x) = 1 p(x|y=0)p(y=0) p(x|y=1)p(y=1) + 1 .(2.16) Note that having estimated the model parameters using the expectation maximization method, both the prior probabilities and the class conditional distributions are known. It is also interesting to mention that formula (2.16) is similar to that of the logistic regression or logit model. This is why, under a GMM model, where p(x|y= 0) = N(x|µ0,Σ0) and p(x|y= 1) = N(x|µ1,Σ1), we can use formula (2.3) to expand (2.16) and achieve the following expression for the log-probability ratio: log p(y= 1|x) p(y= 0|x)!=1 2(x−µ0)tΣ−1 0(x−µ0)−(x−µ1)tΣ−1 1(x−µ1) +1 2log |Σ0| − log |Σ1|+log p(y= 1) −log p(y= 0). (2.17) Chapter 2. Semi-Supervised Learning 13 The log probability ratio allows us to give the following classification rule: ˆy= 1 ⇐⇒ log p(y= 1|x) p(y= 0|x)!>0.(2.18) Furthermore, expression (2.17) gives a measure of the confidence of classification: the further the ratio is from 0, the more likely is for the classification to be correct. We can justify this by considering the three main components of the log probability ratio: (i) (x−µ0)tΣ−1 0(x−µ0)−(x−µ1)tΣ−1 1(x−µ1)is the difference of the squares of the Mahalanobis distance between the instance and each of the means. The greater the absolute value of this difference, the closer the instance is to one of the distributions compared to the other. (ii) (log |Σ0| − log |Σ1|) the difference of the generalized log-variances. (iii) log p(y= 1) −log p(y= 0)the difference between the prior probabilities. 2.4 Some caveats We now have a clear semi-supervised method that uses the unlabelled data to improve the accuracy of classification. Nevertheless, one must be cautious about the correctness of the model or the underlying hypothesis: that the data is actually generated by the mixture model that is being considered. In other words, should the number of components (which may not necessarily be |Y|), the prior probabilities, or the conditional probability distributions p(x|y) be incorrect, the accuracy of the predictor might be less than if only labelled data was used in a traditional supervised learning context. In chapter 3, some simulations will be presented to illustrate this point more precisely. On the other hand, domain knowledge is useful in order to consider a generative model. For example, image analysis or medical trials are fields where a simple statistical analysis shows populations typically follow a Gaussian distribution. In these contexts, a Gaussian Mixture Model with the appropriate number of components would be adequate. 14 2.5. Co-training 2.5 Co-training Co-training [11] is another important semi-supervised classification method. It is specially suitable for what is broadly referred to as natural language processing. In particular, we will concentrate on named entity classification, which is a task that involves classifying a proper name into one of multiple classes depending on its meaning. Consider the following illustrative example. Example 2.5.1. Suppose we are interested in classifying Wikipedia articles into one of the two following categories: humans or places, the first ones being biographical accounts of some person, and the latter being about geographical spaces. Consider that we are given as instances x= (x(1),x(2)), where x(1) is the title of the article and x(2) is an excerpt of the abstract. One training sample Scould be, Instance x(1) x(2) y 1 Joseph Fourier ...mathematician and physicist... person 2 Corsica ...island in the Mediterranean Sea... place 3 Leonhard Euler ...mathematician, ..., astronomer... ??? 4 Madagascar ...is an island country... ??? 5 Leonardo da Vinci ...astronomer and architect... ??? ... ... ... ... As always, annotated data is difficult to obtain because it requires manual labour (in this case we only have two labelled instances) but we have plenty of unlabelled instances at our disposal. A simple co-training classifier that uses both the name of the article (x(1)), as well as the context (given by x(2)) to learn name entity classification would proceed as follows: (i) From instance 1 we learn that “mathematician” and “physicist” appear in the context of the label “person”. The same idea applies to Corsica: the classifier learns that “island” corresponds to a place. (ii) Knowing this, we are able to classify Madagascar as a place, as it has “island” in its context. (iii) Similarly, we can assign the class “person” to Leonard Euler, and this in turn allows us to learn “astronomer” to be associated with “person”. (iv) Finally, this would enable the classification of Leonardo da Vinci as a “person” even though neither the name nor the context were present in the annotated data. As in the example, we consider each instance xto be described by two feature sets, also called views, (x(1),x(2))∈Rd1×Rd2. This is often the case for real-world data. Take, for instance, content moderation in a social media platform like YouTube, where each video is described by its meta-data (title, description, etc.) and the content of the Chapter 2. Semi-Supervised Learning 15 video itself. YouTube’s algorithm may decide whether a video is suitable for recommendation based on these two views. Formally, a co-training algorithm is an ensemble method that uses two distinct classifiers, f(1) and f(2), which are only trained with the labelled instances, taking into account solely the views x(1) and x(2), respectively. The most confident predictions of each classifier are added to the labelled data of the other. In this way, both classifiers teach one another. Algorithm 2. Co-Training Input data: S={(x(1) 1, y1),(x(2) 1, y1),...,(x(1) l, yl),(x(2) l, yl),x(1) l+1,x(2) l+1,...,x(1) l+u,x(2) l+u}, and k∈N, with k≤l+u, the learning speed. (i) Consider the training data sets for classifiers f(1) and f(2) to be, respectively, L1={(x(1) 1, y1),...,(x(1) l, yl)},L2={(x(2) 1, y1),...,(x(2) l, yl)}. (ii) While S \ (L1∪L2)=∅perform the following steps: (a) Train f(1) from L1and f(2) from L2. (b) Use both f(1) and f(2) to classify instances from S \ (L1∪L2). (c) For each classification of the previous instances made by f(1) and f(2), a confidence value is assigned. Consider {x(1) ij,ˆy(1) ij}k j=1 and {x(2) i′ j,ˆy(2) i′ j}k j=1 to be the k-most confident predictions of f(1) and f(2), respectively. Add these to the training sample of the other classifier: •L1=L1∪ {(x(1) i′ j,ˆy(2) i′ j)}k j=1 . •L2=L2∪ {(x(2) ij,ˆy(1) ij)}k j=1 . Classifiers f(1) and f(2) only pay attention to their corresponding views, but the training instances may be given by the other classifiers, hence the notation ˆy(2) i′ jand ˆy(1) ij, respectively, in the updated training samples. Notice also that we are not interested in the specific nature of each supervised learner, but on the way in which they can be combined to improve classification in the context of semi-supervised learning, when only a few annotated instances with two views are available. The only requirement for f(1) and f(2) is to be able to assign a confidence or accuracy to their predictions. f(1) and f(2) are often referred to as view-1 and view-2 classifiers, respectively. Co-training is one of many semi-supervised learning methods that utilizes the “disagreements” between the two classifiers trained on a smaller, fully labelled data set, and re-trains them until they agree on a larger sample, using the unlabelled data. 16 2.6. Hypotheses of co-training 2.6 Hypotheses of co-training The first necessary condition in order to apply co-training is for the instances to have two views. Besides the contexts in which this happens naturally, instances can be arbitrarily split into two views. Nevertheless, for co-training to be successful in any of these cases, two main hypotheses are usually considered: views x(1) and x(2) must be sufficient and redundant (for the classification task) and conditionally independent [12]. The sufficient and redundant hypothesis asks for both views to be sufficiently informative. In other words, that a good classifier can be trained solely on each x(1) and x(2). On the other hand, views must be conditionally independent. That is, p(x(1) |y, x(2)) = p(x(1) |y), p(x(2) |y, x(1)) = p(x(2) |y).(2.19) This means that given the label y, knowledge of one of the views does not affect the probability of the other. To illustrate this hypothesis, let’s recall our example, in which view x(1) was the title of a Wikipedia article, and x(2) a fragment of its abstract. Fix the label y= “person” and consider for example the context x(2) = “mathematician and physicist”. The conditionally independent hypothesis implies that this context does not benefit any particular title or name, given the true label y= “person”. This hypothesis, proposed by Blum and Mitchell in 1998 (see [5, pp. 92 - 100]), is generally overly strict and usually does not hold, even with large data sets. This is obvious in our example, since x(2) = “...French emperor...” heavily influences the article name. Nonetheless, it is intuitive to understand why this hypothesis is considered, even if it is not always true. If conditional independence did not generally hold and some x(2) were learnt by f(2) to be associated with a particular class, since this classifier teaches f(1) by adding the corresponding view to its training data, we would risk adding less and less informative instances to f(1), as a result of these being overly “similar” to each other and hence defeating the purpose of improving classification. Therefore, a relaxation of this necessary hypothesis is proposed by Abney in [1], in which an upper bound for the classification error is given in terms of the rate of disagreement of the two learners, as we have mentioned before. To understand this, we need to introduce the following concepts: Let X1be the space where x1belongs. Consider H1to be all possible classifiers from X1to Y. Analogously, for the second view we have X2and H2. Definition 2.6.1. Given y∈ Y ={0,1},f(1) ∈ H1and f(2) ∈ H2, we say that classifiers f(1) and f(2) are conditionally independent if for all u, v ∈ Y : p(f(1) =u|f(2) =v, y) = p(f(1) =u|y), p(f(2) =u|f(1) =v, y) = p(f(2) =u|y).(2.20) Chapter 2. Semi-Supervised Learning 17 Remember that f(1) ∈ H1is a view-1 only classifier, i.e., f(1) :X1−→ Y, analogously with f(2). Both concepts of conditional independence are related to each other by the following result. Proposition 2.6.1. If views x(1),x(2) are conditionally independent, then f(1) and f(2) are conditionally independent. Proof. By definition of conditional independence of views x(1) and x(2), given y, u, v ∈ Y, p(f(1) =u|f(2) =v, y) = p{x(1) :f(1)(x(1)) = u}|{x(2) :f(2)(x(2)) = v}, y =p{x(1) :f(1)(x(1)) = u} | y =p(f(1) =u|y). As we have observed, this hypothesis is generally unreasonable, though useful. We now introduce a measure of how our classifiers deviate from the conditional independence hypothesis. Definition 2.6.2. The conditional dependence of f(1) and f(2) given yis dy=1 2X u,v∈{0,1}p(f(2) =v|y, f(1) =u)−p(f(2) =v|y).(2.21) Therefore if f(1) and f(2) are conditionally independent then dy= 0. This notion will allow us to relax the conditional independence hypothesis by allowing dyto be bounded. Definition 2.6.3. For y∈ Y ={0,1}, let p1= minu∈Y{p(f(1) =u|y)},p2= minu∈Y {p(f(2) =u|y)}and q1= 1 −p1. Then, f(1) and f(2) satisfy weak dependence if: dy≤p2 q1−p1 2p1q1 .(2.22) Note that if p1= 1/2, then dy= 0 and we recover conditional independence. Indeed, p1 and p2cannot be greater than 1/2 by definition. In particular, p1serves as a measure of how much conditional dependence we can have and is often referred to as the minority probability of classifier f(1): the lower p1is, the greater dycan be. Let the minority value of a classifier be the label where the minority probability is achieved. Another useful concept that will become important later on is the rate of disagreement of classifiers f(1) and f(2), which is simply the p(f(1) =f(2)) = p({(x(1),x(2))| f(1)(x(1))=f(2)(x(2))}). Definition 2.6.4. Predictors f(1) and f(2) are said to be non-trivial if minu∈Y {p(f(1) = u)}> p(f(1) =f(2)). 24 3.3. Second set of simulations These simulations underscore the importance of semi-supervised learning techniques, in particular the mixture model approach to enhance classification performance when plenty of unlabelled data is available and a basic knowledge of the underlying assumptions can be leveraged effectively. 3.3 Second set of simulations We now test the robustness of the semi-supervised methodology when the underlying mixture model assumptions are incorrect to analyse how its performance decays and compares to the supervised learning techniques. Figure 3.3 Consider the data represented in the histogram in Figure 3.3. It is a mixture model of two distinct distributions with weight 1/2: the left-most component is a t-student with 10 degrees of freedom centred at µ0=−2, while the second component is an skewed normal distribution of parameters ξ= 2, ω= 1.5 and α= 2, meaning it is a slightly asymmetric - controlled by parameter αnormal distribution centred around 3. Even though the model assumptions for a two component Gaussian mixture model are not correct, we would be forgiven for trying to fit such a model to the data. Indeed, if we estimate the model parameters using the EM algorithm for a two component Gaussian mixture model and use them to perform the standard Kolmogorov-Smirnov normality test on our data, we obtain a p-value of 0.9471. Thus, we are unable to disregard normality. As in the previous section, in order to assess the behaviour of the semi-supervised approach under failure of the model hypotheses, we perform 100 simulations where the data was randomly generated from the mixture model presented above. One hundred points for each class were generated in each trial, for a total sample size of n= 200, along with two randomly selected labelled instances from each component. Chapter 3. Computational simulations 25 The results were as follows. Using LDA trained on the four labelled instances (the rest is considered unlabelled), the average decision boundary for the 100 trials was 0.45, with a standard deviation of 0.66, indicating, as commented before, that classification with LDA is highly dependent on the specific labelled instances chosen for training. Nonetheless, the average classification error was 4.68%†. SVM yielded similar results when trained on the very same labelled points, with the mean boundary at −0.051. This method was also more stable, for the average deviation of the decision boundary was just 0.12. Contrary to the previous simulations, classification error with SVM was slightly worse at 5.68%. Considering now the aforementioned semi-supervised approach based on the EM algorithm, a two component GMM has been assumed to have generated the data. Furthermore, initialization in all trials of EM was considered such that the means were chosen at −1 and 1, with a standard deviation of 1 for both components, as well as equal prior probabilities. The summary of the average results found by EM is as follows. bµ0bµ1bσ0bσ1bπ0bπ1 −2.309 2.852 1.332 1.332 0.452 0.548 Table 3.2: Average estimated parameters for the GMM over all simulations. The already discussed cluster then label strategy provided an average classification rate of 4.55%, marginally better than the LDA approach. This indicates that even if the underlying hypotheses are not true, the probability distributions in these simulations are close enough to normality that even under the failure of the model correctness hypothesis, the method still boosted classification performance. In conclusion, lack of the model correctness hypothesis does not necessarily hurt, in general, the model’s performance. Nevertheless, let us see an example where this does indeed happen. 3.4 Example: effects of an incorrect model As mentioned, incorrect assumptions in the generative model need not be catastrophic, but can actually, under certain circumstances, hurt its performance when compared to traditional supervised classification methods. Let us understand this phenomenon with the following example. Below, in Figure 3.4a, a sample of 200 unlabelled data points is represented. Clearly, two clusters in the form of two ellipses are visible. To the right, in Figure 3.4b, the true class of each point is displayed with blue dots for the zero class and with red triangles for the one class. †Error rates in this section were calculated labelling the data based on the estimated decision boundary with each method and comparing them to the true labels. 26 3.4. Example: effects of an incorrect model (a) Sample data. (b) Two classes in four clusters. Figure 3.4 Knowledge of the true underlying model allows us to identify four distinct bi-dimensional normal distributions that have generated the points from the two populations (red and blue) in the two clusters. Without this prior insight into the model, though, we could reasonably assume that the data comes from a two-component normal mixture model, when in reality there are four normal distributions that have generated it, as in Figure 3.4b. In spite of the model not being correct, it is the most reasonable because it is the one with the highest log-likelihood, even when compared to the two component model corresponding to the true populations. This is shown in Figure 3.5, where the ellipses in the left diagram represent the assumed model, which indeed has a greater log-likelihood compared to that of the actual model represented in the right-hand side diagram. (a) Assumed model. log-likelihood: -849.0514. (b) Correct model. log-likelihood: -1029.025. Figure 3.5 Chapter 3. Computational simulations 27 The assumed model, a two component GMM, was estimated using a purely unsupervised EM algorithm. This model fits the unlabelled data reasonably well, with an estimated log-likelihood of −849.051. The two ellipses visible in Figure 3.5a are centred at the estimated means of each of the populations and correspond to the calculated covariance matrices. On the contrary, the correct model in Figure 3.5b actually adapts worse to the data, and hence the log-likelihood is lower at −1029.025. In actuality, however, depending on the labelled data provided to our classifier (the assumed model), the estimated decision boundary will approximately be y=−x, which would produce an approximate classification error of 0.5, making this classifier virtually useless. This phenomenon, where the semi-supervised approach would approximately learn such a linear classifier is represented in Figure 3.6a. To the right, the true decision boundary based on the correct model assumptions is displayed. (a) Decision boundary at y=−xfor an approximate error of 0.5. (b) Correct decision boundary at y=x. This is the Bayes classifier. Figure 3.6 It is therefore evident through this example that a typical supervised classifier, like an SVM, even when utilizing the same labelled instances, would have a similar or even better classification performance. This is especially true if a few more labelled instances were provided. In conclusion, the semi-supervised approach does not guarantee greater classification accuracy than its supervised peers, but requires domain knowledge or a basic understanding of the generative model to boost performance. Remark 3.4.1. When domain knowledge is not available or the generative model is unclear, it is useful to employ a semi-supervised non-parametric approach to estimate the density functions of the different sub-populations. 28 3.5. A co-training simulation Indeed, if we use the function mvnpEM from the R package mixtools, we can use this new non-parametric EM algorithm on our original unlabelled data set to better identify the true subpopulations. This kernel based EM algorithm originally searches for 6 subpopulations in the data. The results are shown below, in Figure 3.7. Figure 3.7: Four mixture components are found by the non-parametric EM. When the process is completed, the algorithm is able to assign every point to one of four sub-populations, which clearly overlap with the true classes in Figure 3.4b. A few centrally located labelled data points in each of the mixture components would then allow us to classify with an accuracy close to that of the Bayes’ classifier. 3.5 A co-training simulation Let us now analyse how to enhance classification performance using the co-training framework studied in Section 2.5. In this context, instances have two views or sets of features. Consider supervised classifiers h(1) and h(2) as view-1 and view-2 only, which we will refer to as our “base” classifiers, since they are only trained on the original labelled samples, say L1={(x(1) 1, y1),...,(x(1) l, yl)},L2={(x(2) 1, y1),...,(x(2) l, yl)}, respectively. Our goal is to make use of all the initially unlabelled data in our sample, {x(1) l+1,x(2) l+1,...,x(1) l+u,x(2) l+u}, to co-train two new better classifiers, f(1) and f(2). In our simulation, 1000 normally distributed data points with two views were generated, 500 for each of the two classes. For the 0 class, the points from the first view follow the random variable Xy=0,view-1 ∼ N (−1.5,1), while those of the second view are drawn from Xy=0,view-2 ∼ N (−1,1.2). Similarly, data from the 1 class is such that Xy=1,view-1 ∼ N(1.5,1) and Xy=1,view-2 ∼ N (1,1.2). All in all, for the 0 class, the bidimensional points are centred at (−1.5,−1), while at (1.5,1) for the 1 class. Chapter 3. Computational simulations 29 Figure 3.8: Generated synthetic data. Figure 3.8 above displays the 1000 data points with their two univariate views acting as features. From this plot, it is clear that the two classes are able to be separated by a linear classifier. For each of the two views, the density function of the generated data is shown in the margins, separated by class, which correspond to the normal distributions considered earlier. In order to better assess classification performance, 20% of that data was set apart as the test sample. Of the remaining, 5% was considered labelled, with the other 95% of training instances being unlabelled. Both the “base” classifiers h(1),h(2) and through co-training f(1),f(2) were chosen to use the usual LDA supervised classification technique. Indeed, initially, h(1) =f(1) and h(2) =f(2). Co-training was performed with a learning speed k= 10, as described in Algorithm 2, where the k-most confident predictions of each classifier are added (with their projected labels) to the training sample of the other. Then, each classifier is re-trained. The algorithm stops when there is no longer any unlabelled instances, or in addition, if classification accuracy of f(1) and f(2) degrades or does not improve for 3 iterations. The final results, obtained after only 4 iterations, are summarized in Table 3.3. Classifier Accuracy Base view-1 0.885 Base view-2 0.775 Co-trained view-1 0.890 Co-trained view-2 0.800 Table 3.3: Final results for the four classifiers. 30 3.5. A co-training simulation The following diagram, Figure 3.9, shows the progress in accuracy of the classifiers throughout the four iterations. The dotted lines correspond to the base classifiers, which remain unchanged, while the co-trained classifiers are represented by solid lines. Figure 3.9: Accuracy of the four classifiers from iteration 0, where h(1) =f(1) and h(2) =f(2), to iteration four. Base classifiers h(1) and h(2) remain unchanged because they are trained on the original labelled sample. Both view-1 and view-2 classifiers trained with co-training progressively improve their accuracy, by 0.5% and 2.5%, respectively. The unimpressive improvements in classification accuracy are due to the fact that the two views, by themselves, are informative enough to train a good base classifier. In addition, neither of the two views is more informative than the other and they are not conditionally independent, so co-training is only able to move performance slightly closer to the theoretical maximum. Nevertheless, this demonstrates the power of co-training to boost classification performance under the right assumptions and framework. Chapter 4 Real life applications 4.1 Optical galaxy classification Gravity bounds galaxies together to form what astronomers call galaxy clusters. The number of galaxies in these clusters can range from hundreds to thousands. Nevertheless, apart from clustering galaxies in the physical space, they can also be clustered in the colour space based on their observed frequency in the electromagnetic spectrum. This is related to the concept of “redshift”, a gravitational phenomenon predicted by the theory of general relativity that states that photons emitted from the centre of galaxies lose energy and therefore become more red in the spectrum. This optical clustering is of interest to our dissertation, since the colour of a galaxy can be used to understand its nature. Most galaxies can be classified in one of the two following categories: red sequence galaxies (RS) have generally low star formation activity and are usually elliptical, and blue cloud (BC) galaxies that are often of spiral form and are producing new stars. Galaxies that do not belong to either of the two aforementioned categories - like ours, the Milky Way - live in the “green valley”. Star formation activity is measured via the specific star formation rate or sSFR. Under low redshift (meaning for galaxies that are relatively close), the colour of a galaxy is a good proxy for the sSFR. As discussed, RS galaxies usually have low sSFR, while BC galaxies generally have high sSFR. What is interesting is that the distribution of the specific star formation rate across galaxies is of bi-modal nature, which suggests the use of a two component Gaussian mixture model to discriminate between RS and BC galaxies. In this way, we can use the colour of galaxies to classify them into the RS, and thus with low sSFR, and BC, associated with high sSFR. Indeed, astronomers observe this phenomenon in space, where small components for the RS, low-sSFR galaxies exist between wider components for the high-sSFR, BC galaxies. 31 32 4.1. Optical galaxy classification Let us illustrate these concepts with real-life observations of galaxies collected from SkyServer’s Sloan Digital Sky Survey, or SDSS. A data set containing 44,829 galaxies in the low redshift environment was obtained with precise spectroscopic (colour) measurements along with an estimation of their specific star formation rate, sSFR. Each individual galaxy was represented as a bi-dimensional data point in Figure 4.1 using the colour indexes g−r and r−i as features. The colouring of each point was calculated using the sSFR estimation in its appropriate astronomical form (see [4]). Galaxies with a low specific star formation rate were coloured in red, while those with a high sSFR are in blue. Figure 4.1: Low redshift sample of 44,829 galaxies. Two clusters are clearly visible. Figure 4.1 demonstrates that the colour of galaxies is indeed correlated to their star formation activity. The two distinct clusters, corresponding to the blue cloud (BC) and the red sequence (RS) galaxies, indicate that classification of galaxies into one of the above classes with a two component GMM using the colours as features is useful to determine the sSFR level. The reference paper for this section [4] outlines a new algorithm, called Red Dragon. This algorithm slices the low redshift environments into further subgroups, applies a GMM to obtain a parametrization of the components using the colour information of each galaxy, and then uses interpolation over the discrete mixture model parameters to obtain a continuous GMM model across redshift. Classification of each individual galaxy is done, as discussed in Chapter 2, using the posterior probabilities for each of the components, usually assigning it to the component with the greatest probability or based on some threshold. However, Red Dragon is a much more sophisticated algorithm since it uses an additional two colour indexes, for a feature space of four dimensions. Each galaxy is therefore represented by a colour vector denoted as ci. Chapter 4. Real life applications 33 In addition, it considers a “noise” covariance matrix for each galaxy, ∆i, to account for the intrinsic errors in the measurements of the different colour bands. All in all, the likelihood for the K-component Gaussian mixture model is L(θ|S) = Ngal Y i=1 K X k=1 Lk(θk|ci),(4.1) where Ngal is the total number of galaxies and Lk(θk|ci) is the likelihood of the i-th galaxy in the k-th component, which is equal to Lk(θk|ci) = πk p(2π)Ngal |Σk+ ∆i|exp −1 2(ci−µk)t(Σk+ ∆i)−1(ci−µk).(4.2) After Red Dragon has estimated the model’s parameters continuously across redshift, galaxy classification is performed assigning each galaxy to the class that maximizes the membership probability, i.e, α= arg max α=1,...,K Lα(θα|ci) PK k=1 Lk(θk|ci).(4.3) Red dragon was tested by the authors on the data set represented in Figure 4.1 to estimate the model parameters for a two component GMM in the already commented 4-dimensional colour space. Figure 4.2 shows the results, as in the previous figure, in the g−r and r−i axis, where the colour represents the estimated probability of each galaxy being from the RS (red sequence) class of galaxies, with those with very low probability (and hence likely to be from the BC class) in blue. Figure 4.2: From “Red Dragon, a redshift-evolving Gaussian mixture model for galaxies” [4]. Because the clusters in the diagram overlap with those in Figure 4.1 corresponding to the low and high specific star formation rates, we can conclude that classification based on the above GMM is a good predictor, as suggested earlier, of the level of sSFR. 40 4.4. Conclusion 4.4 Conclusion Throughout this dissertation we have studied the theoretical framework of semi supervised classification, with particular attention to the mixture model and co-training approaches. After performing a number of simulations to test the behaviour of these techniques, we have seen a number real life use cases, ranging from galaxy classification, to analysing train occupancy data. Semi-supervised learning is still an under-developed field which would benefit from more rigorous theoretical foundations. In addition, this learning paradigm is subjected to the same challenges as all others in the context of machine learning, that being the pace of advancements in the field, which demands constant innovation and adaptation. Nevertheless, semi-supervised classification has proven to be an extremely useful learning paradigm in the current context of large quantities of unlabelled data being available in order to enhance classical supervised classifiers. The process of developing this work has been extremely rewarding, as it has been a great excuse to dive deep into topics that were out of the scope of this degree, and read sources that were of great interest both to this dissertation and in a broader sense to my development as a scientist and as a human. Appendix A R and Python code R and Python were used extensively, especially for chapters 3 and 4. Not included in this dissertation to maintain brevity, the code is provided separately in the CODE folder. We provide a basic guide to navigate through these files. •3.1 Introduction -gMM.R •3.2 First set of simulations -Simulation 1.R •3.3 Second set of simulations -Simulation 2.R •3.4 Example: effects of an incorrect model -Simulation 3.R •3.5 A co-training simulation -Simulation CoTraining.R •4.1 Optical galaxy classification -Galaxies (folder) –galaxies.R –SDSS low z sample.csv (data base) •4.2 Case study: train occupancy data -Train occupancy analysis (folder) –train data.R –Loading Data.csv (data base) •4.3 Self-training: a final semi-supervised approach -Self-Training (folder) –main.py –plot.py –dataset.csv (data base) 41 Bibliography [1] Abney, S. (2002) Bootstrapping. Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics (ACL), July 2002, pp. 360-367. [2] Benaglia, T., Chauveau, D., Hunter, D.R., Young, D.S. (2009) “mixtools: An Package R for Analyzing Finite Mixture Models.” Journal of Statistical Software, 32(6), 1–29. http://www.jstatsoft.org/v32/i06/. [3] Br´emaud, P. (2017) Discrete Probability Models and Methods, Springer. [4] Black, W.K., Evrard, A. (2022) Red Dragon: a redshift-evolving Gaussian mixture model for galaxies, Monthly Notices of the Royal Astronomical Society, Volume 516, Issue 1, October 2022, Pages 1170–1182, https://doi.org/10.1093/mnras/stac2052. [5] Blum, A., Mitchell, T. (1998) Combining labeled and unlabeled data with co-training. In: Proceedings of the 11th Annual Conference on Computational Learning Theory, Association for Computing Machinery. [6] Bouguila, N., Fan, W. (Eds.) (2020) Mixture Models and Applications, Springer Natural Switzerland. [7] Helmbold, D., Williamson, B. (Eds.) (2001) 14th and 5th Annual Conference on Computational Learning Theory, Amsterdam, The Netherlands, July 16-19, 2001 proceedings. [8] Jo, T. (2021) Machine Learning Foundations: Supervised, Unsupervised, and Advanced Learning, Springer. [9] Presno, M. A. (2023) Polic´ıa predictiva y prevenci´on de la violencia de g´enero: el sistema VioG´en. Revista de los Estudios de Derecho y Ciencia Pol´ıtica, UOC, noviembre, 2023. [10] Sasaki, T. (2022) Semi-supervised classification on a text dataset, Kaggle, www.kaggle.com/code/sasakitetsuya/semi-supervised-classification-on-a-text-dataset [11] Schwenker, F., Trentin, E. (Eds.) (2011) Partially Supervised Learning, First IAPR TC3 Workshop, PSL 2011 Ulm, Germany, September 15-16, Revised Selected Papers, Springer. [12] Zhou, Z.-H. (2013) Unlabeled Data and Multiple Views. In: Partially Supervised Learning: Second IAPR International Workshop, PSL 2013, Nanjing, China, May 13-14, 2013. [13] Zhu, X., Goldberg, A. B. (2009) Introduction to Semi-Supervised Learning, Morgan & Claypool. 43