# Conformity-Based Transfer AdaBoost Algorithm

Shuang Zhou, Evgueni N. Smirnov, Haitham Bou Ammar, Ralf Peeters

► To cite this version:

Shuang Zhou, Evgueni N. Smirnov, Haitham Bou Ammar, Ralf Peeters. Conformity-Based Transfer AdaBoost Algorithm. 9th Artificial Intelligence Applications and Innovations (AIAI), Sep 2013, Paphos, Greece. pp.401-410, 10.1007/978-3-642-41142-7_41. hal-01459635

HAL Id: hal-01459635

https://inria.hal.science/hal-01459635

Submitted on 7 Feb 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Conformity-based Transfer AdaBoost Algorithm

Shuang Zhou, Evgueni N. Smirnov, Haitham Bou Ammar, and Ralf Peeters

Department of Knowledge Engineering, Maastricht University,
P.O.BOX 616, 6200 MD Maastricht, The Netherlands
{shuang.zhou,smirnov,haitham.bouammar,ralf.peeters}
@maastrichtuniversity.nl

**Abstract.** This paper proposes to consider the region classification task in the context of instance-transfer learning. The proposed solution consists of the conformal algorithm that employs a nonconformity function learned by the Transfer AdaBoost algorithm. The experiments showed that our approach results in valid class regions. In addition the conditions when instance transfer can improve learning are empirically derived.

**Keywords:** Region classification, Conformal framework, Transfer learning

## 1 Introduction

Most of the research in machine learning is concentrated on the task of point classification: estimating the correct class of an instance given a data sample drawn from some unknown *target* probability distribution. However, in applications with high misclassification costs, region classification is needed [1, 10]. The task of region classification is to find a region (set) of classes that contains the correct class of the instance to be classified with a given probability of error $\epsilon \in [0, 1]$. Thus by employing region classification we can control the error in a long run which however has practical sense if the class regions are efficient; i.e., small.

This paper proposes to consider the region classification task in a new context, in the context of instance-transfer learning [4, 7]. This means that in addition to the *target* data sample we have a second data sample generated by some unknown *source* probability distribution. The main assumption is that the target and source distributions are different but somehow similar. Thus, the region-classification task in this case is to find class regions according to the target probability distribution, given the target data sample, by transferring relevant instances from the source data sample.

To solve the region-classification task in the instance-transfer learning setting we note that (1) the conformal framework [1, 10] is a general framework for the region classification task, (2) the Transfer AdaBoost algorithm is a base algorithm for instance-transfer learning [7], and (3) the AdaBoost algorithm was used under the conformal framework [5, 10]. Thus, our solution for the task is a combination of these techniques.

To compare our research with relevant work we note that instance-transfer learning has been applied so far only for the task of point classification [4, 7]. Thus our region classification task considered in instance-transfer learning and the approach that we propose for the task are novel and they form the main contributions of this paper.
The remaining of the paper is organized as follows. Section 2 formalizes the tasks of point classification and region classification in traditional learning and instance-transfer learning. The conformal framework and Transfer AdaBoost algorithm are given in Sections 3 and 4, respectively. Section 5 proposes the weights-based nonconformity function for implementing the conformity framework using the Transfer AdaBoost algorithm. The experiments are given in Section 6. Finally, Section 7 concludes the paper.

# 2 Point and Region Classification

This section formalizes the tasks of point classification and region classification. The formalizations are given separately for the traditional-learning setting and instance-transfer learning setting in the next two subsections.

## 2.1 Traditional Learning Setting

Let $\mathbf{X}$ be an instance space and $\mathbf{Y}$ a class set. We assume an unknown probability distribution over the labeled space $\mathbf{X} \times \mathbf{Y}$, namely the *target* distribution $p^t(x, y)$. We consider training sample $D_n^t \subseteq \mathbf{X} \times \mathbf{Y}$ defined as a bag $\{(x_1, y_1)^t, (x_2, y_2)^t, \dots, (x_{n^t}, y_{n^t})^t\}$ of $n$ instances $(x_i, y_i)^t \in \mathbf{X} \times \mathbf{Y}$ drawn from the probability distribution $p^t(x, y)$.

Given training sample $D_n^t$ and an instance $x_{n+1}^t \in \mathbf{X}$ drawn according to $p^t(x)$,

- the point-classification task is to find an estimate $\hat{y} \in \mathbf{Y}$ of the class of the instance $x_{n+1}$ according to $p^t(x, y)$;

- the region-classification is to find a class region $\Gamma^\varepsilon(D_n^t, x_{n+1}) \subseteq \mathbf{Y}$ that contains the class of $x_{n+1}$ according to $p^t(x, y)$ with probability at least $1 - \varepsilon$, where $\varepsilon$ is a significance level.

In point classification estimating the class of any instance $x \in \mathbf{X}$ assumes that we learn a point classifier $h(D_n^t, x)$ in a hypothesis space $\mathcal{H}$ of point classifiers $h$ ($h: (\mathbf{X} \times \mathbf{Y})^{(*)} \times \mathbf{X} \to 2^\mathbb{R}$)<fnref n="1" /> using the target sample $D_n^t$. The classifier $h(D_n^t, x)$ outputs for any instance $x$ a posterior distribution of scores $\{s_y\}_{y \in \mathbf{Y}}$ over all the classes in $\mathbf{Y}$. The class $y$ with the highest posterior score $s_y$ is the estimated class $\hat{y}$ for the instance $x$. In this context we note that the point classifier $h(D_n^t, x)$ has to be learned such that it performs best on new unseen instances $(x, y)^t \in \mathbf{X} \times \mathbf{Y}$ drawn according to the target probability distribution $p^t(x, y)$.

In region classification (according to the conformity framework [1, 10]) computing class region $\Gamma^\varepsilon(D_n^t, x_{n+1}) \subseteq \mathbf{Y}$ for any instance $x_{n+1} \in \mathbf{X}$ requires two steps. First we derive a nonconformity function $A$ that given a class $y \in \mathbf{Y}$ maps the sample $D_n^t$ and the instance $(x_{n+1}, y)$ to a nonconformity value $\alpha \in [0, R \cup \{\infty\}]$. Then we compute the $p$-value $p_y$ of class $y$ for the instance $x_{n+1}$ as the proportion of the instances in $D_n^t \cup \{(x_{n+1}, y)\}^t$ of which the nonconformity scores are greater than or equal to that of the instance $(x_{n+1}, y)$. The class $y$ is added to the final class region for the instance $x_{n+1}$ if $p_y \ge \varepsilon$. In this context we note that the nonconformity function $A$ has to be learned such that it performs best on new unseen instances $(x, y)^t \in \mathbf{X} \times \mathbf{Y}$ drawn according to the target probability distribution $p^t(x, y)$.

<footnote n="1">¹ $(\mathbf{X} \times \mathbf{Y})^{(*)}$ denotes the set of all bags defined over $\mathbf{X} \times \mathbf{Y}$.</footnote>
## 2.2 Instance-Transfer Learning Setting

In instance-transfer learning in addition to the instance space $X$, the class set $Y$, the target distribution $p^t(x, y)$, and the training sample $D_n^t$, we have a second unknown probability distribution over $X \times Y$, namely the source distribution $p^s(x, y)$, and training sample $D_m^s$ defined as a bag of $m$ instances $(x_i, y_i)^s \in X \times Y$ drawn from $p^s(x, y)$. Assuming that the target distribution $p^t(x, y)$ and source distribution $p^s(x, y)$ are different but somehow similar we define:

- the instance-transfer point-classification task as a point classification task for which we learn the point classifier $h(D_n^t, x)$ by transferring relevant instances from the source sample $D_m^s$ in addition to the target sample $D_n^t$;

- the instance-transfer region-classification as a region-classification task for which we learn the nonconformity function $A$ by transferring relevant instances from the source sample $D_m^s$ in addition to the target sample $D_n^t$.

# 3 The Conformal Framework

This section introduces the conformal framework [1, 10]. It formalizes the framework, provides possible options, and introduces metrics for evaluating region classifiers.

## 3.1 Formal Description

The conformal framework has been proposed in [1, 10] for developing region classifiers. The framework is proven to be valid when the target sample $D_n^t$ and each instance $x_{n+1} \in X$ to be classified are drawn from the same unknown target distribution $p^t(x, y)$ under the exchangeability assumption. The exchangeability assumption holds when different orderings of instances in a bag are equally likely.

Applying the conformal framework is a two-stage process. Given a point classifier $h(D_n^t, x)$, a nonconformity function is constructed for $h(D_n^t, x)$ capable of measuring how unusual an instance is for other instances in the data. Then, the conformal algorithm employing this nonconformity function is applied to compute the class regions.

Formally, a nonconformity function is of type $A : (X \times Y)^{(*)} \times (X \times Y) \rightarrow \mathbb{R} \cup \{\infty\}$. Given a bag $D_n^t \in (X \times Y)^{(*)}$ and instance $(x, y) \in (X \times Y)$ it returns a value $\alpha$ in the range $[0, R \cup \{\infty\}]$ indicating how unusual the instance $(x, y)$ is with respect to the instances in $D_n^t$. In general, the function $A$ returns different scores for instance $(x, y)$ depending on whether $(x, y)$ is in the bag $D_n^t$ (added prediction) or not (deleted prediction): if $(x, y) \in D_n^t$, then the score is lower; otherwise it is higher.

The general nonconformity function was defined in [10] for any point classifier $h(D_n^t, x)$. Given training bag $D_n^t \in (X \times Y)^{(*)}$ and instance $(x, y_r)$, it outputs the sum $\sum_{y \in Y, y \neq y_r} s_y$ where $s_y$ is the score for class $y \in Y$ produced by $h(D_n^t, x)$.

The conformal algorithm is presented in Algorithm 1. Given significance level $\varepsilon \in [0, 1]$, target sample $D_n^t$, instance $x_{n+1} \in X$ to be classified, and the nonconformity function $A$ for a point classifier $h(D_n^t, x)$, the algorithm constructs a class region $\Gamma^\varepsilon(D_n^t, x_{n+1}) \subseteq Y$ for the instance $x_{n+1}$. The class-region construction is realized
separately for each class $y \in \mathbf{Y}$. To decide whether to include the class $y$ in the class region $\Gamma^{\epsilon}(D_n^t, x_{n+1})$ the instance $x_{n+1}$ and class $y$ are first combined into labelled instance $(x_{n+1}, y)$. Then, the algorithm computes the nonconformity score $\alpha_i$ for each instance $(x_i, y_i)$ in the bag $D_{n+1}^t$, using the nonconformity function $A$ for the point classifier $h(D_n^t, x)$. The nonconformity scores are used for computing the p-value $p_y$ of the class $y$ for the instance $x_{n+1}$. More precisely, $p_y$ is computed as the proportion of the instances in the bag $D_{n+1}^t$ of which the nonconformity scores $\alpha_i$ are greater or equal to that of the instance $(x_{n+1}, y)$. Once $p_y$ is set, the algorithm includes the class $y$ in the class region $\Gamma^{\epsilon}(D_n^t, x_{n+1})$ if $p_y > \epsilon$. The conformal algorithm was originally designed for the online learning setting. This setting assumes initially an empty data set $D_n^t$. Then for each integer $n$ from 0 to $+\infty$ we first construct class region $\Gamma^{\epsilon}(D_n^t, x_{n+1})$ for the new instance $x_{n+1}$ being classified, and then add the instance $(x_{n+1}, y_r)$ to the bag where $y_r$ is the correct class of $x_{n+1}$. In this context we note that the conformal algorithm is proven to be valid [1, 10], i.e., it constructs for any object $x_{n+1}$ class region $\Gamma^{\epsilon}(D_n^t, x_{n+1}) \subseteq \mathbf{Y}$ containing the correct class $y \in \mathbf{Y}$ for $x_{n+1}$ with probability at least $1 - \epsilon$, if (a) the data are drawn from the same target distribution $p^t(x, y)$ under the exchangeability assumption; and (b) the learning setting is online.

<caption>**Algorithm 1 Conformal algorithm**</caption>

**Input:** Significance level $\epsilon$, Target sample $D_n^t$, Instance $x_{n+1}$ to be classified, Non-conformity function $A$ for a point classifier $h(D_n^t, x)$.
**Output:** Class region $\Gamma^{\epsilon}(D_n^t, x_{n+1})$
1: $\Gamma^{\epsilon}(D_n^t, x_{n+1}) = \emptyset$.
2: **for each** class $y \in \mathbf{Y}$ **do**
3:     $D_{n+1}^t = D_n^t \cup \ell(x_{n+1}, y)\rfloor$.
4:     **for** $i := 1$ to $n+1$ **do**
5:         **if** using deleted prediction **then**
6:             Set nonconformity score $\alpha_i := A(D_{n+1}^t \cup \ell(x_i, y_i)\rfloor, (x_i, y_i))$.
7:             **else if** using added prediction **then**
8:                 Set nonconformity score $\alpha_i := A(D_{n+1}^t, (x_i, y_i))$.
9:             **end if**
10:         **end for**
11:     Calculate $p_y := \frac{\#\{i=1,...,n|\alpha_i \ge \alpha_{n+1}\}}{n+1}$.
12:     Include $y$ in $\Gamma^{\epsilon}(D_n^t, x_{n+1})$ if and only if $p_y > \epsilon$.
13:     **end for**
14: Output $\Gamma^{\epsilon}(D_n^t, x_{n+1})$.

## 3.2 Possible Options

Applying the conformal framework is not a trivial task. One has to make a set of choices concerning the nonconformity function used and the learning setting.

The conformal algorithm outputs valid class regions for any real-valued function used as nonconformity function [1]. The class regions will be efficient if the function
estimates well the difference of any instance with respect to the training data. In this context we note that the general nonconformity function is not always the most efficient. Therefore, one of the main issues when applying the conformal framework is how to design a specific nonconformity function for the point classifier used.

The conformal algorithm is proven to be valid when the learning setting is online [1]. However, there are reported experiments in the offline (batch) setting [6]. In contrast to the online setting, the offline setting assumes a target training sample that is non-empty initially. Furthermore, the target sample remains the same throughout the classification process. These experiments show that the conformal algorithm produces valid class regions in the offline setting.

## 3.3 Evaluation Metrics

Any class region $\Gamma^{\varepsilon}(D_n^t, x_{n+1})$ is valid if it contains the correct class $y \in \mathbf{Y}$ of the instance $x_{n+1} \in \mathbf{X}$ being classified with probability of at least $1 - \varepsilon$. To evaluate experimentally the validity of the class regions provided by the conformal algorithm we introduce the error metric. The error $E$ is defined as the proportion of the class regions that do not contain the correct class. Thus, in order to prove experimentally that the conformal algorithm is valid we have to show that for all significance levels $\varepsilon \in [0, 1]$ the error $E$ is less than or equal to $\varepsilon$.

Any class region $\Gamma^{\varepsilon}(D_n^t, x_{n+1})$ is efficient if it is non-empty and small. Thus, to evaluate experimentally the efficiency of the class regions provided by the conformal algorithm we introduce three metrics: the percentage $P_e$ of empty-class regions, the percentage $P_s$ of single-class regions, and the percentage $P_m$ of multiple-class regions. The empty-class regions, single-class regions, and multiple-class regions can be characterized by their own errors. The percentage $P_e$ of empty-class regions is essentially an error, since the correct classes are not in the class regions. The error $E_s$ on single-class regions is defined as the proportion of the invalid single-class regions among all the class regions. The error $E_m$ on multiple-class regions is defined as the proportion of the invalid multiple-class regions among all the class regions.

The errors $P_e$, $E_s$, and $E_m$ are components of the error $E$. More precisely, it is easy to prove that $E = P_e + E_s + E_m$. The error $E$ has its own upper bound $E^u$ representing the worst case when we are not able to pick up correct classes from valid multi-class regions. In this case we will err on all the multi-class regions and, thus, $E^u$ is defined equal to $P_e + E_s + P_m$. We note that for any significance level $\varepsilon \in [0, 1]$ there is no guarantee that $E^u$ is less than or equal to $\varepsilon$ unless $P_m = 0$.

# 4 Transfer AdaBoost Algorithm

The Transfer AdaBoost algorithm [7] is a learning method for the instance-transfer point-classification task (see Algorithm 2). The algorithm itself is an extension of the well-known AdaBoost algorithm [8]. It treats the target sample $D_n^t$ and source sample $D_m^s$ differently. For the target sample $D_n^t$, the Transfer AdaBoost algorithm uses the same re-weighting scheme as AdaBoost. It decreases the weights of *correctly classified* instances and through normalization increases the weights of *incorrectly classified* instances.
instances. On the other hand, for the source sample $D_m^s$, the Transfer AdaBoost algorithm uses opposite re-weighting scheme. It decreases the weights of incorrectly classified instances and through normalization increases the weights of correctly classified instances. This means that source instances that are less likely to be generated by the target distribution receive lower weights and source instances that are more likely to be generated by the target distribution receive higher weights. Thus, the Transfer AdaBoost algorithm focuses on more difficult (high-weight) target instances and on more similar (high-weight) source instances in the next iterations.

<caption>**Algorithm 2** Transfer AdaBoost Algorithm, adapted from Dai et al.[7]</caption>

**Input:** Two labeled data sets $D_n^t$ and $D_m^s$
Weak point classifier $h(B, x)$,
Number of iterations $T$.
1: for any instance $(x_i, y_i) \in D_m^s \cup D_n^t$ initialize weight $w_1(x_i) = 1$. Let $\mathbf{p}$ be vector of the normalized weights of instances in $D_m^s \cup D_n^t$ and $\mathbf{p}^t$ be vector of the normalized weights of instances in $D_n^t$.
2: **for** $k = 1$ to $T$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;Train weak classifier $h_k : X \to Y$ on $D_m^s \cup D_n^t$ using normalized weights from $\mathbf{p}_k$.
4: &nbsp;&nbsp;&nbsp;&nbsp;Calculate the weighted error $\epsilon_k$ of $h_k$ on $D_n^t$ using normalized weights from $\mathbf{p}_k^t$.
5: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\epsilon_k = 0$ or $\epsilon_k \ge \frac{1}{2}$ **then**
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Set $T = k - 1$.
7: &nbsp;&nbsp;&nbsp;&nbsp;**Abort loop**.
8: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
9: &nbsp;&nbsp;&nbsp;&nbsp;Set $\beta = \frac{1}{1+\sqrt{2\ln m/T}}$ and $\beta_k = \frac{\epsilon_k}{1-\epsilon_k}$.
10: Update the weight for any instance $(x_i, y_i) \in D_m^s \cup D_n^t$:
$$ \left\{ \begin{array}{ll} w_{k+1}^s(x_i) = w_k^s(x_i)\beta^{[h_k(x_i) \neq y_i]} & \text{if } (x_i, y_i) \in D_m^s; \\ w_{k+1}^t(x_i) = w_k^t(x_i)\beta^{-[h_k(x_i) \neq y_i]} & \text{if } (x_i, y_i) \in D_n^t. \end{array} \right. $$
11: **end for**
12: **Output** the strong classifier: $h_f(x) = sign(\sum_{k=T/2}^T \ln(\frac{1}{\beta_k})h_k(x))$

# 5 Weights-Based Non-conformity Function

To solve the instance-transfer region-classification task we propose to apply the conformal framework that employs a nonconformity function based on the Transfer AdaBoost algorithm. An obvious option in this context is to use the general nonconformity function (see subsection 3.1) given in [1]. However in this paper we go further and propose a new nonconformity function called the weight-based nonconformity function. As the name suggests it is based on the weights of the training instances from the target sample calculated by the Transfer AdaBoost algorithm. Since they indicate the classification difficulty of the instances, we interpret them as nonconformity values.

To theoretically justify the weight-based nonconformity function we note that for any target instance $(x_i, y_i) \in D_n^t$, given the initial weight equals 1, we have that:
$$w_{T+1}^{t}(x_i) = w_{1}^{t}(x_i) \prod_{k=1}^{T} \left(\frac{1}{\beta_k}\right)^{[h_k(x_i) \neq y_i]} = \prod_{k=1}^{T} \left(\frac{1}{\beta_k}\right)^{[h_k(x_i) \neq y_i]} \quad (1)$$

In addition we note that $\epsilon_k \in (0, 0.5)$. Thus, $\frac{1}{\beta_k} > 1$ and $\prod_{k=1}^{T} \left(\frac{1}{\beta_k}\right)^{[h_t(x_i) \neq y_i]} \ge 1$. Since $[h_f(x_i) \neq y_i] \le 1$, it follows that:

$$[h_f(x_i) \neq y_i] \le \prod_{k=1}^{T} \left(\frac{1}{\beta_k}\right)^{[h_k(x_i) \neq y_i]} \quad (2)$$

Combining equations (1) and (2) results in:

$$[h_f(x_i) \neq y_i] < w_{T+1}^{t}(i)$$

Thus, the weight of any target instance is found to be the upper bound on the training error of that instance [2]. This explains why we propose the use of weights for nonconformity values.

Formally the weights-based nonconformity function is defined as follows: given a target sample set $D_n^t$ and an instance $(x, y_r)$, the function returns the weight $w_{T+1}(x)$ for the instance $(x, y_r)$ calculated by the Transfer AdaBoost algorithm after T iterations. We note that, since the Transfer AdaBoost algorithm computes weights only for target instances, the instance $(x, y_r)$ has to belong to the data $D_n^t$. This implies that the conformal algorithm is used with the option “added prediction” only. We note that in this case computing p-value $p_y$ for one class $y \in \mathbf{Y}$ requires only one run of the Transfer AdaBoost algorithm. Thus, the time complexity for constructing one class region is $O(|\mathbf{Y}|C)$ (where C is the time complexity of the Transfer AdaBoost algorithm).

# 6 Experiments and Discussion

This section presents our experiments with the conformal algorithm presented in subsection 3.1. Given a sample $D_n^t$ and a sample $D_m^s$, the algorithm was instantiated using three types of nonconformity functions:

- the weight-based nonconformity function based on the AdaBoost algorithm trained on the sample $D_n^t$,

- the weight-based nonconformity function based on the Transfer AdaBoost algorithm trained on the sample $D_n^t$ as a target sample and sample $D_m^s$ as a source sample,

- the weight-based nonconformity function based on the AdaBoost algorithm trained on the sample $D_n^t \cup D_m^s$.

The conformal algorithm based on the first function is denoted as CAdaBoostT. The conformal algorithm based on the second function is denoted as CTrAdaBoostTS. The conformal algorithm based on the third function is denoted as CAdaBoostTS.

The generalization performance of these three algorithms is given in terms of the validity and efficiency of the final class regions. We note that CAdaBoostT is used as a base-line algorithm. The algorithms CTrAdaBoostTS and CAdaBoostTS are used in order to decide whether we need to transfer or add source instances.
## 6.1 Data sets

The datasets for our experiments were taken from the UCI Machine Learning Repository [9]. In order to fit transfer-learning scenario each data set was split into target sample and source sample with different probability distributions. For example, the breast-cancer data set was split using the attribute *irradiat*. The target sample in this case consisted of all the instances having the attribute value *irradiate=no*, while the source sample consisted of all the instances having the attribute value *irradiate=yes*. Table 1 given below shows the description of each data-set split. It also provides the KL-divergence estimate [3] on the difference of class distributions for each pair of target sample and source sample. We note that two datasets, namely breast cancer and auto were split twice using different binary attributes.

<table><caption>**Table 1.** The descriptions of the data sets</caption><thead><tr><th rowspan="2">Data Set</th><th rowspan="2">Number of Classes</th><th rowspan="2">KL-divergence</th><th colspan="2">Size</th></tr><tr><th>D<sup>t</sup></th><th>D<sup>s</sup></th></tr></thead><tbody><tr><td>hepatitis</td><td>2</td><td>0.041</td><td>79</td><td>76</td></tr><tr><td>colic</td><td>2</td><td>0.078</td><td>272</td><td>92</td></tr><tr><td>heart-c</td><td>2</td><td>0.148</td><td>74</td><td>77</td></tr><tr><td>heart-c2</td><td>2</td><td>0.204</td><td>96</td><td>207</td></tr><tr><td>dermatology</td><td>6</td><td>0.224</td><td>79</td><td>294</td></tr><tr><td>breast-cancer</td><td>2</td><td>0.285</td><td>56</td><td>115</td></tr><tr><td>auto</td><td>4</td><td>0.302</td><td>59</td><td>112</td></tr><tr><td>auto2</td><td>4</td><td>0.391</td><td>83</td><td>97</td></tr><tr><td>lymph</td><td>4</td><td>0.621</td><td>73</td><td>75</td></tr><tr><td>vote</td><td>2</td><td>1.135</td><td>264</td><td>171</td></tr></tbody></table>

## 6.2 Validation Setup

Experiments were performed on ten data sets from Table 1 using all the three conformal algorithms CAdaBoostT, CTrAdaBoostTS, and CAdaBoostTS. The weak point classifier for these three algorithms was the decision-stump classifier for the first 8 datasets, while for the last two datasets was the Naive-Bayes classifier <fnref n="2" />. The class regions of the algorithms were evaluated in terms of validity and efficiency using five measures (defined in subsection 3.3): the error *E*, the percentage *P*<sub>e</sub> of empty-class regions, the percentage *P*<sub>s</sub> of single-class regions, the percentage *P*<sub>m</sub> of multiple-class regions, and the upper-bound error *E*<sup>u</sup>. The method of evaluation was repeated stratified 10-fold cross validation. Results for each data set were generated for 10 to 100 boosting iterations (with step 10). The best results for each algorithm over the ten different iteration numbers are reported in Table 2 on two significance levels ε = 0.05 and ε = 0.1.

<footnote n="2">² The reason for employing NaiveBayes is that for the last two datasets the decision-stump classifier resulted in error greater than 0.5 on the first iteration.</footnote>
<table><caption>**Table 2.** Performance of the CAdaBoostT, CTrAdaBoostTS, and CAdaBoostTS algorithms.</caption><thead><tr><th rowspan="2"></th><th rowspan="2"></th><th colspan="5">ε = 0.05</th><th colspan="5">ε = 0.1</th></tr><tr><th>E</th><th>P<sub>e</sub></th><th>P<sub>s</sub></th><th>P<sub>m</sub></th><th>E<sup>u</sup></th><th>E</th><th>P<sub>e</sub></th><th>P<sub>s</sub></th><th>P<sub>m</sub></th><th>E<sup>u</sup></th></tr></thead><tbody><tr><td rowspan="3">hepatitis</td><td>CAdaBoostT</td><td>0.061</td><td>0.006</td><td>0.775</td><td>0.219</td><td>0.280</td><td>0.119</td><td>0.054</td><td>0.854</td><td>0.092</td><td>0.210</td></tr><tr><td>CAdaBoostTS</td><td>0.054</td><td>0.001</td><td>0.776</td><td>0.223</td><td>0.277</td><td>0.115</td><td>0.023</td><td>0.911</td><td>0.066</td><td>0.181</td></tr><tr><td>CTrAdaBoostTS</td><td>0.051</td><td>0.008</td><td>0.771</td><td>0.221</td><td>0.272</td><td>0.116</td><td>0.039</td><td>0.889</td><td>0.072</td><td>0.189</td></tr><tr><td rowspan="3">colic</td><td>CAdaBoostT</td><td>0.052</td><td>0.000</td><td>0.517</td><td>0.483</td><td>0.534</td><td>0.098</td><td>0.000</td><td>0.789</td><td>0.211</td><td>0.309</td></tr><tr><td>CAdaBoostTS</td><td>0.050</td><td>0.000</td><td>0.572</td><td>0.428</td><td>0.478</td><td>0.098</td><td>0.000</td><td>0.823</td><td>0.177</td><td>0.275</td></tr><tr><td>CTrAdaBoostTS</td><td>0.049</td><td>0.000</td><td>0.565</td><td>0.435</td><td>0.483</td><td>0.098</td><td>0.001</td><td>0.820</td><td>0.178</td><td>0.276</td></tr><tr><td rowspan="3">heart-c</td><td>CAdaBoostT</td><td>0.049</td><td>0.004</td><td>0.689</td><td>0.307</td><td>0.356</td><td>0.093</td><td>0.032</td><td>0.872</td><td>0.096</td><td>0.189</td></tr><tr><td>CAdaBoostTS</td><td>0.053</td><td>0.000</td><td>0.802</td><td>0.198</td><td>0.251</td><td>0.098</td><td>0.017</td><td>0.951</td><td>0.032</td><td>0.130</td></tr><tr><td>CTrAdaBoostTS</td><td>0.048</td><td>0.007</td><td>0.787</td><td>0.206</td><td>0.254</td><td>0.097</td><td>0.029</td><td>0.889</td><td>0.072</td><td>0.169</td></tr><tr><td rowspan="3">heart-c2</td><td>CAdaBoostT</td><td>0.058</td><td>0.006</td><td>0.674</td><td>0.320</td><td>0.378</td><td>0.102</td><td>0.023</td><td>0.838</td><td>0.139</td><td>0.241</td></tr><tr><td>CAdaBoostTS</td><td>0.058</td><td>0.000</td><td>0.683</td><td>0.317</td><td>0.375</td><td>0.097</td><td>0.005</td><td>0.944</td><td>0.051</td><td>0.148</td></tr><tr><td>CTrAdaBoostTS</td><td>0.056</td><td>0.001</td><td>0.758</td><td>0.241</td><td>0.297</td><td>0.099</td><td>0.025</td><td>0.877</td><td>0.098</td><td>0.197</td></tr><tr><td rowspan="3">dermotology</td><td>CAdaBoostT</td><td>0.080</td><td>0.020</td><td>0.301</td><td>0.679</td><td>0.758</td><td>0.092</td><td>0.021</td><td>0.307</td><td>0.672</td><td>0.733</td></tr><tr><td>CAdaBoostTS</td><td>0.104</td><td>0.067</td><td>0.674</td><td>0.259</td><td>0.364</td><td>0.101</td><td>0.053</td><td>0.554</td><td>0.393</td><td>0.481</td></tr><tr><td>CTrAdaBoostTS</td><td>0.014</td><td>0.001</td><td>0.374</td><td>0.625</td><td>0.639</td><td>0.014</td><td>0.003</td><td>0.429</td><td>0.568</td><td>0.575</td></tr><tr><td rowspan="3">breast-cancer</td><td>CAdaBoostT</td><td>0.059</td><td>0.000</td><td>0.184</td><td>0.816</td><td>0.875</td><td>0.113</td><td>0.000</td><td>0.355</td><td>0.645</td><td>0.757</td></tr><tr><td>CAdaBoostTS</td><td>0.048</td><td>0.000</td><td>0.105</td><td>0.895</td><td>0.943</td><td>0.108</td><td>0.000</td><td>0.229</td><td>0.771</td><td>0.873</td></tr><tr><td>CTrAdaBoostTS</td><td>0.044</td><td>0.000</td><td>0.173</td><td>0.827</td><td>0.871</td><td>0.089</td><td>0.000</td><td>0.338</td><td>0.662</td><td>0.752</td></tr><tr><td rowspan="3">auto</td><td>CAdaBoostT</td><td>0.054</td><td>0.000</td><td>0.137</td><td>0.863</td><td>0.880</td><td>0.098</td><td>0.002</td><td>0.266</td><td>0.732</td><td>0.769</td></tr><tr><td>CAdaBoostTS</td><td>0.010</td><td>0.000</td><td>0.007</td><td>0.993</td><td>0.997</td><td>0.092</td><td>0.000</td><td>0.341</td><td>0.659</td><td>0.729</td></tr><tr><td>CTrAdaBoostTS</td><td>0.044</td><td>0.000</td><td>0.166</td><td>0.834</td><td>0.849</td><td>0.094</td><td>0.002</td><td>0.312</td><td>0.686</td><td>0.729</td></tr><tr><td rowspan="3">auto2</td><td>CAdaBoostT</td><td>0.049</td><td>0.000</td><td>0.080</td><td>0.920</td><td>0.933</td><td>0.102</td><td>0.002</td><td>0.161</td><td>0.836</td><td>0.881</td></tr><tr><td>CAdaBoostTS</td><td>0.017</td><td>0.000</td><td>0.007</td><td>0.993</td><td>0.995</td><td>0.108</td><td>0.000</td><td>0.157</td><td>0.834</td><td>0.901</td></tr><tr><td>CTrAdaBoostTS</td><td>0.034</td><td>0.000</td><td>0.093</td><td>0.907</td><td>0.912</td><td>0.084</td><td>0.001</td><td>0.165</td><td>0.833</td><td>0.857</td></tr><tr><td rowspan="3">lymph</td><td>CAdaBoostT</td><td>0.026</td><td>0.000</td><td>0.242</td><td>0.758</td><td>0.774</td><td>0.070</td><td>0.001</td><td>0.407</td><td>0.592</td><td>0.660</td></tr><tr><td>CAdaBoostTS</td><td>0.034</td><td>0.000</td><td>0.660</td><td>0.340</td><td>0.374</td><td>0.085</td><td>0.000</td><td>0.723</td><td>0.277</td><td>0.362</td></tr><tr><td>CTrAdaBoostTS</td><td>0.034</td><td>0.000</td><td>0.667</td><td>0.333</td><td>0.367</td><td>0.057</td><td>0.000</td><td>0.745</td><td>0.255</td><td>0.312</td></tr><tr><td rowspan="3">vote</td><td>CAdaBoostT</td><td>0.050</td><td>0.011</td><td>0.972</td><td>0.017</td><td>0.067</td><td>0.099</td><td>0.074</td><td>0.926</td><td>0.000</td><td>0.099</td></tr><tr><td>CAdaBoostTS</td><td>0.050</td><td>0.015</td><td>0.976</td><td>0.009</td><td>0.059</td><td>0.098</td><td>0.082</td><td>0.918</td><td>0.000</td><td>0.098</td></tr><tr><td>CTrAdaBoostTS</td><td>0.048</td><td>0.014</td><td>0.957</td><td>0.029</td><td>0.077</td><td>0.096</td><td>0.070</td><td>0.930</td><td>0.000</td><td>0.096</td></tr></tbody></table>

## 6.3 Results and Discussion

The performance results of the three conformal algorithms are given in Table 2. The table shows that the class regions computed by the algorithms are valid. This is due to the fact that the error *E* is close to the significance level *ε* up to some neglectable statistical fluctuation. Thus we can derive one of the main results of this paper, namely that the conformal algorithm is capable of obtaining valid class regions for the instance-transfer region-classification task. This is possible (at least for now) when we employ our weight-based nonconformity function learned by the Transfer AdaBoost algorithm.

In addition, Table 2 shows how instance transfer can help learning. When the target and source distributions are very close (small KL-divergence number) and the size of the target sample is relatively big, the performance statistics of the conformal algorithms CAdaBoostT, CTrAdaBoostTS, and CAdaBoostTS are close. This observation
is illustrated by the performance of the algorithms for the datasets hepatitis and colic. Thus in this case any of these algorithms can be applied; i.e., instance transfer does not improve significantly the results. When the distance between the target and source distributions increases (KL-divergence number in the range [0.1, 0.9]) and the size of the target sample is smaller, the percentage $P_m$ of multiple-class regions and the upper-bound error $E^u$ of the conformal algorithm CTrAdaBoostTS are smaller than those of CAdaBoostTS on most of the datasets. This observation is illustrated best by the performance of the algorithms for the datasets auto, auto2, and lymph. Thus in this case the conformal algorithm CTrAdaBoostTS has to be applied; i.e., instance transfer does improve the final results. When the distance between the target and source distributions becomes high (KL-divergence number in the range [0.9, $+\infty$]), again the performance statistics of the conformal algorithms CAdaBoostT, CTrAdaBoostTS, and CAdaBoostTS are close (see dataset vote). Thus in this case any of these algorithms can be applied; i.e., instance transfer does not improve the results.

# 7 Conclusion

This paper showed that the region classification task can be solved in the context of instance-transfer learning [4, 7]. The proposed solution consists of the conformal algorithm that employs a nonconformity function based on the instance weights learned by the Transfer AdaBoost algorithm. The experiments showed that the approach results in valid class regions. In addition the conditions when instance transfer can improve learning are empirically derived.

# References

1. Shafer, G., Vovk, V.: A Tutorial on Conformal Prediction. Journal of Machine Learning Research 9, 371–421 (2008)

2. Schapire, R.E., Singer, Y.: Improved boosting algorithms using confidence-rated predictions. Machine learning 37(3), 297–336 (1999)

3. Kullback, S., Leible, R.A.: On information and sufficiency. The Annals of Mathematical Statistics 22(1), 79–86 (1951)

4. Pan, S.J., Yang, Q.: A Survey on Transfer Learning. IEEE Trans. Knowl. Data Eng. 22(10), 1345–1359 (2010)

5. Moed, M., Smirnov, E.N.: Efficient AdaBoost Region Classification. In: 6th International Conference on Machine Learning and Data Mining in Pattern Recognition, pp. 123–136. Springer, Leipzig (2009)

6. Vanderlooy, S., Maaten, L.V.D, Sprinkhuizen-Kuyper, I.G.: Off-Line Learning with Transductive Confidence Machines: An Empirical Evaluation. In: 5th International Conference on Machine Learning and Data Mining in Pattern Recognition, pp. 310–323. Springer, Leipzig (2007)

7. Dai, W., Yang, Q., Xue, G., Yu, Y.: Boosting for transfer learning. In: 24th international conference on Machine learning, pp. 193–200. ACM (2007)

8. Freund, Y., Schapire, R.E.: Experiments with a New Boosting Algorithm. In: International Conference on Machine Learning, pp. 148–156. (1996)

9. UCI Machine Learning Repository, http://archive.ics.uci.edu/ml

10. Vovk, V., Gammerman, A., Shafer, G.: Algorithmic Learning in a Random World. Springer-Verlag New York, Inc., Secaucus (2005)