A Survey of Optimization Methods from a Machine Learning Perspective <s> B. Optimization Problems in Semi-supervised Learning <s> We introduce a semi-supervised support vector machine (S3VM) method. Given a training set of labeled data and a working set of unlabeled data, S3VM constructs a support vector machine using both the training and working sets. We use S3VM to solve the transduction problem using overall risk minimization (ORM) posed by Vapnik. The transduction problem is to estimate the value of a classification function at the given points in the working set. This contrasts with the standard inductive learning problem of estimating the classification function at all possible values and then using the fixed function to deduce the classes of the working set data. We propose a general S3VM model that minimizes both the misclassification error and the function capacity based on all the available data. We show how the S3VM model for 1-norm linear support vector machines can be converted to a mixed-integer program and then solved exactly using integer programming. Results of S3VM and the standard 1-norm support vector machine approach are compared on ten data sets. Our computational results support the statistical learning theory results showing that incorporating working data improves generalization when insufficient training information is available. In every case, S3VM either improved or showed no significant difference in generalization compared to the traditional approach. <s> BIB001 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> B. Optimization Problems in Semi-supervised Learning <s> In many practical machine learning and data mining applications, unlabeled training examples are readily available but labeled ones are fairly expensive to obtain. Therefore, semi-supervised learning algorithms such as co-training have attracted much attention. Previous research mainly focuses on semi-supervised classification. In this paper, a co-training style semi-supervised regression algorithm, i.e. COREG, is proposed. This algorithm uses two k-nearest neighbor regressors with different distance metrics, each of which labels the unlabeled data for the other regressor where the labeling confidence is estimated through consulting the influence of the labeling of unlabeled examples on the labeled ones. Experiments show that COREG can effectively exploit unlabeled data to improve regression estimates. <s> BIB002 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> B. Optimization Problems in Semi-supervised Learning <s> Semi-supervised clustering algorithms aim to improve clustering results using limited supervision. The supervision is generally given as pairwise constraints; such constraints are natural for graphs, yet most semi-supervised clustering algorithms are designed for data represented as vectors. In this paper, we unify vector-based and graph-based approaches. We show that a recently-proposed objective function for semi-supervised clustering based on Hidden Markov Random Fields, with squared Euclidean distance and a certain class of constraint penalty functions, can be expressed as a special case of the weighted kernel k-means objective. A recent theoretical connection between kernel k-means and several graph clustering objectives enables us to perform semi-supervised clustering of data given either as vectors or as a graph. For vector data, the kernel approach also enables us to find clusters with non-linear boundaries in the input data space. Furthermore, we show that recent work on spectral learning (Kamvar et al., 2003) may be viewed as a special case of our formulation. We empirically show that our algorithm is able to outperform current state-of-the-art semi-supervised algorithms on both vector-based and graph-based data sets. <s> BIB003 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> B. Optimization Problems in Semi-supervised Learning <s> Semi-supervised SVMs (S3VM) attempt to learn low-density separators by maximizing the margin over labeled and unlabeled examples. The associated optimization problem is non-convex. To examine the full potential of S3VMs modulo local minima problems in current implementations, we apply branch and bound techniques for obtaining exact, globally optimal solutions. Empirical evidence suggests that the globally optimal solution can return excellent generalization performance in situations where other implementations fail completely. While our current implementation is only applicable to small datasets, we discuss variants that can potentially lead to practically useful algorithms. <s> BIB004 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> B. Optimization Problems in Semi-supervised Learning <s> Due to its wide applicability, the problem of semi-supervised classification is attracting increasing attention in machine learning. Semi-Supervised Support Vector Machines (S3VMs) are based on applying the margin maximization principle to both labeled and unlabeled examples. Unlike SVMs, their formulation leads to a non-convex optimization problem. A suite of algorithms have recently been proposed for solving S3VMs. This paper reviews key ideas in this literature. The performance and behavior of various S3VMs algorithms is studied together, under a common experimental setting. <s> BIB005 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> B. Optimization Problems in Semi-supervised Learning <s> In image categorization the goal is to decide if an image belongs to a certain category or not. A binary classifier can be learned from manually labeled images; while using more labeled examples improves performance, obtaining the image labels is a time consuming process. We are interested in how other sources of information can aid the learning process given a fixed amount of labeled images. In particular, we consider a scenario where keywords are associated with the training images, e.g. as found on photo sharing websites. The goal is to learn a classifier for images alone, but we will use the keywords associated with labeled and unlabeled images to improve the classifier using semi-supervised learning. We first learn a strong Multiple Kernel Learning (MKL) classifier using both the image content and keywords, and use it to score unlabeled images. We then learn classifiers on visual features only, either support vector machines (SVM) or least-squares regression (LSR), from the MKL output values on both the labeled and unlabeled images. In our experiments on 20 classes from the PASCAL VOC'07 set and 38 from the MIR Flickr set, we demonstrate the benefit of our semi-supervised approach over only using the labeled images. We also present results for a scenario where we do not use any manual labeling but directly learn classifiers from the image tags. The semi-supervised approach also improves classification accuracy in this case. <s> BIB006 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> B. Optimization Problems in Semi-supervised Learning <s> In this paper, we study the problem of learning from weakly labeled data, where labels of the training examples are incomplete. This includes, for example, (i) semi-supervised learning where labels are partially known; (ii) multi-instance learning where labels are implicitly known; and (iii) clustering where labels are completely unknown. Unlike supervised learning, learning with weak labels involves a difficult Mixed-Integer Programming (MIP) problem. Therefore, it can suffer from poor scalability and may also get stuck in local minimum. In this paper, we focus on SVMs and propose the WellSVM via a novel label generation strategy. This leads to a convex relaxation of the original MIP, which is at least as tight as existing convex Semi-Definite Programming (SDP) relaxations. Moreover, the WellSVM can be solved via a sequence of SVM subproblems that are much more scalable than previous convex SDP relaxations. Experiments on three weakly labeled learning tasks, namely, (i) semi-supervised learning; (ii) multi-instance learning for locating regions of interest in content-based information retrieval; and (iii) clustering, clearly demonstrate improved performance, and WellSVM is also readily applicable on large data sets. <s> BIB007 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> B. Optimization Problems in Semi-supervised Learning <s> Abstract Discriminant analysis (DA) is a well-known dimensionality reduction tool in pattern classification. With enough efficient labeled samples, the optimal projections could be found by maximizing the between-class scatter variance meanwhile minimizing the within-class scatter variance. However, the acquisition of label information is difficult in practice. So, semi-supervised discriminant analysis has attracted much attention in recent years, where both few labeled samples and many unlabeled samples are utilized during learning process. Sparse graph learned by sparse representation contains local structure information about data and is widely employed in dimensionality reduction. In this paper, semi-supervised double sparse graphs (sDSG) based dimensionality reduction is proposed, which considers both the positive and negative structure relationship of data points by using double sparse graphs. Aiming to explore the discriminant information among unlabeled samples, joint k nearest neighbor selection strategy is proposed to select pseudo-labeled samples which contain some precise discriminant information. In the following procedures, the data subset consisting of labeled samples and pseudo-labeled samples are used instead of the original data. Based on two different criterions, two sDSG based discriminant analysis methods are designed and denoted by sDSG-dDA (distance-based DA) and sDSG-rDA (reconstruction-based DA), which also use different strategies to reduce the effect of pseudo-labels’ inaccuracy. Finally, the experimental results both on UCI datasets and hyperspectral images validate the effectiveness and advantage of the proposed methods compared with some classical dimensionality reduction methods. <s> BIB008
Semi-supervised learning (SSL) is the method between supervised and unsupervised learning, which incorporates labeled data and unlabeled data during the training process. It can deal with different tasks including classification tasks BIB006 ,  , regression tasks BIB002 , clustering tasks  , BIB003 and dimensionality reduction tasks  , BIB008 . There are different kinds of semi-supervised learning methods including selftraining, generative models, semi-supervised support vector machines (S3VM) BIB001 , graph-based methods, multi-learning method and others. We take S3VM as an example to introduce the optimization in semi-supervised learning. S3VM is a learning model that can deal with binary classification problems and only part of the training set in this problem is labeled. Let l be labeled data index which can be represented as D l = {{x 1 , y 1 }, {x 2 , y 2 }, ..., {x l , y l }}, and u be unlabeled data index which can be represented as D u = {x l+1 , x l+2 , ..., x M } with M = l + u. In order to use the information of unlabeled data, additional constraint on the unlabeled data is added to the original objective of SVM with slack variables ζ i . Specifically, define ǫ j as the misclassification error of the unlabeled instance if its true label is positive and z j as the misclassification error of the unlabeled instance if its true label is negative. The constraint means to make M j=l+1 min(ǫ i , ζ i ) as small as possible. Thus, an S3VM problem can be described as where C is a penalty coefficient. The optimization problem in S3VM is a mixed-integer problem which is difficult to deal with  . There are various methods summarized in BIB005 to deal with this problem, such as the branch and bound techniques BIB004 and convex relaxation methods BIB007 .