How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Network Measures <s> In traditional machine learning approaches to classification, one uses only a labeled set to train the classifier. Labeled instances however are often difficult, expensive, or time consuming to obtain, as they require the efforts of experienced human annotators. Meanwhile unlabeled data may be relatively easy to collect, but there has been few ways to use them. Semi-supervised learning addresses this problem by using large amount of unlabeled data, together with the labeled data, to build better classifiers. Because semi-supervised learning requires less human effort and gives higher accuracy, it is of great interest both in theory and in practice. ::: We present a series of novel semi-supervised learning approaches arising from a graph representation, where labeled and unlabeled instances are represented as vertices, and edges encode the similarity between instances. They address the following questions: How to use unlabeled data? (label propagation); What is the probabilistic interpretation? (Gaussian fields and harmonic functions); What if we can choose labeled data? (active learning); How to construct good graphs? (hyperparameter learning); How to work with kernel machines like SVM? (graph kernels); How to handle complex data like sequences? (kernel conditional random fields); How to handle scalability and induction? (harmonic mixtures). An extensive literature review is included at the end. <s> BIB001 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Network Measures <s> This paper investigates the adoption of measures used to evaluate complex networks properties in the characterization of the complexity of data sets in machine learning applications. These measures are obtained from a graph based representation of a data set. A graph representation has several interesting properties as it can encode local neighborhood relations, as well as global characteristics of the data. These measures are evaluated in a meta-learning framework, where the objective is to predict which classifier will have better performance in a given task, in a pair wise basis comparison, based on the complexity measures. Results were compared to traditional data set complexity characterization metrics, and shown the competitiveness of the proposed measures derived from the graph representation when compared to traditional complexity characterization metrics. <s> BIB002
To use these measures, it is necessary to represent the classification dataset as a graph. The obtained graph must preserve the similarities or distances between examples for modeling the data relationships. Each example from the dataset corresponds to a node or vertex of the graph, while undirected edges connect pairs of examples and are weighted by the distances between the examples. As in the neighborhood measures, the Gower distance is employed. Two nodes i and j are connected only if dist (i, j) < ϵ. This corresponds to the ϵ-NN method for building a graph from a dataset in the attribute-value format BIB001 . As in BIB002 and , in ECoL the ϵ value is set to 0.15 (note that the Gower distance is normalized to the range [0,1]). Next, a post-processing step is applied to the graph, pruning edges between examples of different classes. Figure 12 illustrates the graph building process for the dataset from Figure 2 . Figure 12 (a) shows the first step, when the pairs of vertices with dist (x i , x j ) < ϵ are connected. This first step is unsupervised, since it disregards the labels of connected points. Figure 12(b) shows the graph obtained after the pruning process is applied to disconnect examples from different classes. This step can be regarded as supervised, in which the label information is taken into account to obtain the final graph. For a given dataset, let G = (V , E) denote the graph built by this process. By construction, |V | = n and 0 ≤ |E| ≤ n(n−1) 2 . Let the ith vertex of the graph be denoted as v i and an edge between two vertices v i and v j be denoted as e i j . The extracted measures are described next. All the measures from this category require building a graph based on the distance matrix between all pairs of elements, which requires O (m · n 2 ) operations. The asymptotic cost of all the presented measures is dominated by the computation of this matrix. (Density) . This measure considers the number of edges that are retained in the graph built from the dataset normalized by the maximum number of edges between n pairs of data points.