Learning with Labeled Sessions

1 Introduction

A typical supervised learning problem is to learn a model from training examples that are usually labeled instances. But for many applications, training examples are labeled objects and each labeled object consists of multiple unlabeled instances. During classification, an object is labeled as class 'a' if the majority of its instances are classified as 'a'.

One application is physiological data modeling, whose goal is to predict context activities of individual users based on their physiological data. Typically, physiological signals are measured and recorded continuously for every other second. Continuous physiological signals are then divided into a number of sessions. Each session is of minutes long and consists of hundreds of records of physiological data. To predict the user's activities for a session, prediction is first made for each record, and the dominant activity predicted for records in the session is then used as the activity for the session. Although each session is labeled as a single activity, a user may perform activities other than the labeled one. For example, during a session of 'watching TV', the user may fall into sleep for a short period of time. More information can be found from the website http://www.cs.utexas.edu/users/sherstov/pdmc/.

Another application is speaker identification. To determine the speaker for a speech sample that is a minute long, a typical strategy is to first divide the long speech sample into a number of short ones. Then, a standard classification model, such as Gaussian Mixture Model (GMM), is applied to determine the speaker identity for each short sample. Finally, the dominant speaker that is classified for short samples will be used as the predicted speaker for the long sample. Compared with the strategy that extracts a single set of features for the whole long speech sample, this majority vote approach is usually more robust and accurate [Reynolds, 1995]. This is because features extracted from a long speech sample may include significant amounts of background noise, while the noise can be reduced substantially when a long speech sample is divided into short ones.

The common characteristics of the above two applications are that (1) training examples are labeled objects (e.g., sessions of physiological records in physiological data modeling, and a long speech sample in speaker identification); (2) every object consists of multiple instances that are not labeled; and (3) in predicting an object's class, it is determined by the class that is assigned to the majority of its instances. To distinguish this new type of learning from the traditional supervised learning, we call it 'session-based learning'.

The challenge of session-based learning arises from the majority vote strategy that is used to determine the label of an object. This decision rule makes it ambiguous, during training, as to which subset of the instances inside an object should belong to the class of the object - we name it the label ambiguity problem. A straightforward strategy toward this problem is to treat every unlabeled instance within a labeled object as a positive example for the class of the object. In physiological data modeling, every physiological record within a labeled session is treated as a training instance for the activity assigned to the session. In speaker identification, every short sample within a long speech is used as a positive training instance for the speaker of the long speech. We call this simple strategy the 'naive approach'.

One obvious problem with the naïve approach is that instances within a single object often belong to multiple different classes, not just to the class of the object. Thus, by treating every instance within an object as a positive example for the class of the object, we likely introduce training examples with noisy labels, which, as a result, degrades the quality of classification models. To further illustrate the problem with the naïve approach, let us consider a toy learning problem in Figure 1. It has four classes, with class 'A', 'B', and 'C' centering on the vertices of a triangle, and the fourth class 'D' sitting on the center of the triangle. In traditional supervised learning, training examples are labeled instances. Since these four classes are well separated, we would expect that a simple Naïve Bayes model should work fine for this problem. But, for a session-based learning problem, training examples are labeled objects that consist of instances from different classes. In particular, consider the case when training objects for classes 'A', 'B', and 'C' are mixtures of instances from these three classes, while training objects for class 'D' only contain instances from 'D'. With appropriate mixtures, the input means of instances from labeled objects for the four classes can stay close to each other, which makes it hard for the Naïve Bayes method to learn if assigning each instance with its object class.

In the following, we first give a formal description of session-based learning, and elaborate on the differences between this new type of learning problem and other related learning problems, such as multiple-instance learning. Then, we present a novel approach that is particularly designed for session-based learning. The key idea is to develop an innovative way that handles the label ambiguity problem. Finally, we demonstrate the effectiveness of the proposed approach for session-based learning using both UCI datasets and data from physiological data modeling.

2 Formal Description of Session-based Learning

Let training examples be denoted by { } 1 1 2 2 ( , ), ( , ),..., ( , ) n n D o y o y o y = , where each ( , ) i i o y is a labeled object and i y ∈Y is the class label assigned to object i o . Domain Y is { 1,1} - for binary-class classification problems, and [1.. ] K for multiple-class classification problems where K (K > 2) is the number of classes. Let ( ) c o be an object-based classification function, which takes an object o as input and outputs its class label. In general, any supervised learning problem can be formulated as an optimization problem:

where L is a loss function that determines the amount of punishment when prediction ( ) i c o is different from i y .

For a traditional supervised learning problem, each object only contains a single instance. As a result, training examples can be simplified as { } 1 1 2 2 ( , ), ( , ),..., ( , ) n n D y y y = x x x , where each instance d i ∈ℜ x is a vector in a d dimension space. Furthermore, the object-based classification function ( ) c o becomes an instance-based classification function ( ) : d f ℜ → x Y . Thus, a traditional supervised learning problem is usually formulated as follows:

In session-based learning, each object consists of multiple unlabeled instances. Let the training data be denoted by { } 1 1 2 2 ( , ), ( , ),..., ( , ) n n D y y y = X X X , where each object { } , 1 i m i i j j= = X x contains mi different instances. Given an

instance-based classification function ( ) : d f ℜ → x Y , the decision rule for session-based learning is that, an object i X is labeled as class 'a' if the majority of its instances are classified as 'a'. Thus, in session-based learning, the objectbased classification function cs can be written into the following form of the instance-based classification ( ) f x :

where ( ) δ ⋅ is a delta function that outputs 1 when the input is positive and zero otherwise.

Compared to traditional supervised learning, the challenge of session-based learning is due to the label ambiguity problem. Although each training object is provided with a class label, the label information of instances within objects is not given. Hence, it is difficult to learn an instance-based classification function from labeled objects. In the naïve approach, each instance within an object is treated as a positive example for the class of the object. As a result, a session-based learning problem is simplified as a traditional supervised learning problem:

The most related work to session-based learning is multiple-instance learning[Dietterich, et al.,1997]. Similar to session-based learning, in multiple-instance learning, class labels are assigned to objects that consist of multiple instances, which are called "bags" in multiple-instance learning. In the past, there have been many studies on multipleinstance learning, including the approach of learning axisparallel rectangles [Dietterich, et al.,1997], the diverse density algorithm [Maron and Lozano-Pérez,1998], the approaches based on support vector machines [Andrews, et al.,2002, Tao, et al.,2004], the nearest neighbor approach [Amar et.al. 2001; Wang and Zucker, 2000], and the boosting approach [Andrews and Hofmann,2003].

Multiple-instance learning differs from session-based learning in its decision rule. In multiple-instance learning, an object i X is labeled as positive class when at least one of its instances is classified as positive. A negative class is assigned to an object when all of its instances are classified as negative. Thus, given the instance-based classification function ( ) : d f ℜ → x Y , the object-based classification function cm for multiple-instance learning is written as:

Examples for the three different types of learning are shown in Figure 2 for comparison. The first column shows traditional supervised learning with instances and their labels. The columns for Multiple Instance Learning and Sessionbased Learning show how these two different strategies aggregate instances and assign labels to the aggregates.

Session-based learning is more challenging than multipleinstance learning in the following sense: in multipleinstance learning, when an object is labeled as 'negative', all of its instances will belong to the negative class. Thus, for multiple-instance learning, there is no label ambiguity for negatively labeled objects. In contrast, the label ambiguity problem exists for session-based learning regardless of the sign of labels. For instance, in Figure 2, for session-based learning, both the first and second objects are labeled as 'negative'. However, the labels of instances in these two objects are different. The two learning schemes also differ in degrees of difficulty when deciding positive classes for objects: multiple-instance learning adopts the "at-least one" strategy and session based learning uses the majority one.

3 SBoost - An Algorithm for Session-based Learning

In this session, we will present a boosting-based algorithm for session-based learning problems of binary classes. The key for designing a learning algorithm for sessionbased learning is to define a simple yet effective loss function ( ) ( ; ), i i L c f y X . A simple choice is ( ) ( ) ( ; ), ( ; ) i i i i L c f y c f y δ = ≠ X X . However, this choice will lead to a non-smooth objective function, which is usually difficult for optimization. Hence, we choose to use the exponential loss function to approximate classification errors, which has been demonstrated to be effective in the AdaBoost algorithm [Freund and Schapire, 1997].

In particular, in designing objective functions, two types of errors are considered: instance-based errors and sessionbased errors. An instance-based error is a prediction mistake made for an instance, and a session-based error is a prediction mistake made for a session. One key difference between session-based learning and traditional supervised learning is that the former is concerned with both sessionbased errors and instance-based errors while the latter concerns with only instance-based errors. To include both types of errors, given an instance-based classification function ( ) H x , we define the loss function as:

In the above expression, both session-based and instancebased errors are approximated by an exponential function. The loss function is defined as the product of these two errors. In other words, a misclassified instance is important only when its related session is also misclassified. Constant γ in (3) determines the relative importance between the session-based error and the instance-based error. In experiment, a cross validation with 20/80 split of training data is used to determine appropriate values for γ . In the following, we will discuss how to efficiently find ( ) H x that minimizes the loss function in (3).

3.1 Boosting-based Optimization Algorithm

With the loss function defined in (3), our goal is then to search for optimal H(x) that minimizes the overall cost for the training data, i.e.,

Given: (X1, y1), …, (X m, ym) where { } { } , , 1 , , 1,1 i m d i i j i j i j y = = ∈ℜ ∈ - X x x ; Weighting constant γ

Initialize the weight distribution ( ) 0 1 ( , ) 1 n i i D i j m = = ∑ , 0 ( ) 0 H x =

For t = 1,…,T

1. Sample training instances { } 1 1,1 1, ,1 , ,..., ,..., ,..., n m n n m x x x x according to 1 t D -
2. Train a weak classifier ( ) : { 1,1} d t h ℜ → - x on sampled examples

1. Update the weight distribution ( ) ( ) ( ) 1 , exp ( ) , i t i j i i i t t g H y a m D i j Z γ - - + = x , where t Z is a normalization factor (chosen so that 1 t D + is sum to 1).
2. Update the classifier 1 ( ) ( ) ( ) t t t t H H h α - = + x x x

Output the final hypothesis: { } 1 1,1 ( ) argmax ( ) T T t t t y F h y α = ∈ - = ∑ x x

Figure 3: Description of the SBoost algorithm.

An efficient approach for optimizing Eq. (4) is to divide it into a series of simple learning problems that do not have the label ambiguity problem and thus can be resolved by traditional supervised learning techniques. We solve the label ambiguity problem by maintaining weights for different instances such that only instances with large weights are assigned to the class of their objects and used for training. Since boosting [Freund and Schapire, 1997] is a learning algorithm that uses weighted instances to efficiently update classification functions, we design a boosting-based learning algorithm for learning with labeled sessions below.

Let ( ) t h x be the 'weak' classifier of the t-th iteration that is learned using traditional supervised learning techniques. The combined classifier ( ) T H x for the first T iterations is

1 ( ) ( ) T T t t t H h α = = ∑ x x , where t α is the combination constant for the t-th iteration. Our goal is to find another 'weak' classifier 1 ( ) T h + x and a constant 1 T α + such that the new combined classifier 1 1 1 ( ) ( ) ( ) T T T T H H h α + + + = + x x x will effectively minimize the function in (4). Given classifier 1 ( ) T H + x , the objective function in (4) is rewritten as:

In the above expression, for the convenience of presentation, we drop the index for ( ) T H x , 1 ( ) T h + x , and 1 T α + . Using the convexity of an exponential function, we have

ity 1 1 e , [ 1,1] 2 2 x x x e e x α α α - + - ≤ + ∀ ∈ - , we can further

upper bound (6) by the following expression:

( ) m ∑ x

where , 1 exp ( ) i i i j i j a H y = ≡ - . Define weight ( ) ( ) ( ) , , exp ( ) i i j i i i D i j g H y a m γ ≡ - + x and rewrite the second term in (7) as:

Clearly, to minimize the objective err in (7), we need to maximize the above expression (8). The best case is that the output of weak classifier ( ) h x is consistent with yi, for all instances in an object. When this is not the case, the label ambiguity problem is then resolved based on weight ( , ) D i j . In particular, instances with large weights are assigned with the class of their objects, while the labels for instances with small weights remain unlabeled. This is because the contribution of an instance to (8) is mainly determined by its weight ( , ) D i j . When an instance has a small weight, its contribution to (8) will be ignorable. Furthermore, notice that ( , ) D i j is proportional to i g , which is related to session-based error. Thus, a misclassified instance will not be assigned with a large weight if the related session error is small. Finally, the combination constant α can be obtained by setting the derivative of the upper bound in (7) w.r.t. to α to be zero. That is,

where

For later reference, we name this algorithm SBoost for 'session-based boosting'. The details are given in Figure 3.

4 Experiments

The goal of this section is to examine the effectiveness of SBoost for session-based learning. We compare SBoost with the simple naïve approach that treats each instance within an object as a positive example for the class of the object. In particular, the naïve approach is applied to session-based learning with both a Decision Tree and AdaBoost using a Decision Tree as its base classifier.

Two types of data are used in experiments to evaluate the effectiveness of SBoost:

1. Synthesized data that are generated from binary UCI datasets [Blake and Merz,1998] by combining multiple instances into objects. Each object consists of ten different instances. To create an object for the positive class, a random number between 1 and 5 is first generated, and the corresponding number of instances from the negative class are randomly chosen and added to the object. The rest of the object is filled out with instances randomly selected from the positive class. A similar procedure is applied to generate objects for the negative class. By doing so, we guarantee that the class of an object is consistent with the dominant class assigned to its instances. The details of UCI datasets used in this experiment are listed in Table 1.
2. Physiological data that come from the workshop of physiological data modeling at the ICML 2004. We use the dataset for 'watching TV' with code 3004. In the original problem, the number of instances for the negative class is overwhelmingly larger than that for the positive class. Since we focus on the study of session-based learning, we intentionally reduce the effect of rare class by randomly selecting parts of negative instances. The resulting data set has 241 sessions with 40,838 instances. The details of this dataset are listed in Table 2.

A decision tree [Quinlan,1993] is used as the baseline classifier throughout the experiments. The session-based classification error, i.e., the percentage of sessions that are misclassified, is used for evaluation. 50% of data are randomly selected for training and the rest is used for testing. The same experiment is repeated 10 times, and the average session-based classification errors are reported. Finally, for both SBoost and AdaBoost, the maximum number of iterations is set to be 30.

4.1 Results

The results of three methods (SBoost, the naïve approach using a single decision tree, and with AdaBoost) are shown in Table 3. First, we compare the performance of AdaBoost with that of a decision tree as both adopting the naïve approach to session based learning. We observe that AdaBoost does not guarantee to improve performance over the baseline classifier (a decision tree here). In fact, for the spam dataset and the physiological data, the classification errors of AdaBoost are even greater than those of a decision tree. This is because the naïve approach treats all instances in an object as positive examples for the class of the object, while in reality, some instances in an object may belong to a class other than the class of the object. Hence, the naïve approach introduces noisy labels to training data, which will likely cause AdaBoost to overfit as observed in previous study of Boosting [Quanlin, 1996, Dietterich, 2000, Jin et al., 2003].

Second, comparing SBoost with the decision tree, we observe that SBoost always outperforms its baseline classifier. According to t-test, it is statistically significantly better than the decision over all the UCI datasets with 0.05 p < . Thus, SBoost does not suffer from the problem of overfitting as AdaBoost does. To further investigate this issue, we obtain average classification errors of AdaBoost and SBoost in different iterations, respectively, as shown in Figure 4. Clearly, AdaBoost tends to overfit the training data after the first several iterations whereas SBoost does not.

5. Conclusion

In this paper, we formulate a new type of learning problem, session-based learning. It differs from the traditional supervised learning in that training examples are labeled objects and each object consists of multiple unlabeled instances. Furthermore, session-based learning adopts a different decision rule from that of multiple-instance learning: an object is classified as class 'a' when the majority of its instances are classified as 'a'. This majority vote decision rule causes the label ambiguity problem and has made session-based learning very challenging. We formally describe this new learning problem and propose a novel boosting algorithm, named Sboost. Empirical studies have demonstrated the effectiveness of the Sboost algorithm.