Multiple Information Sources Cooperative Learning

1 Introduction

As data collection sources and channels continuously evolve, learning and correlating information from multiple data sources (In this paper, multi-source and multiple data source are equivalent terms) is almost ubiquitous and crosses business, government/enterprise organizations, and many scientific disciplines. Many key bioinformatic research problems, such as gene function annotation, regulatory motif finding, and protein complex identification, have recently been shown to greatly benefit from the techniques which utilize more than one type of data [Fujibuchi and Kato, 2007], this is because many learners can significantly improve their performance if they can integrate information from multiple relevant sources. Consider a major movie data repository which maintains a large number of movie records (IMDb currently

∗The support of NSFC under Grant No. 60674109 is acknowledged.

Ruoming Jin

Dept. of Computer Science Kent State University, Kent, USA jin@cs.kent.edu

maintains more than 750,000 movies and TV episodes worldwide). Movie rental companies (such as Netflix) which maintain and utilize such large data repository will usually have two major tables, namely movie table and user table shown in Figures (1a) and (1b), respectively. The main objective of the movie table is to use movie content such as keyword descriptions to predict a new movie's expected category, whereas the user table is to predict which types of movies the users are interested in or internal categorization of the users for the company's own purposes (e.g. finding high-attrition customers who may turn to other companies). Although the prediction of each task can be solved by learning from each individual table respectively, the prediction solely relying on a single table may not, in practice, generate a good result. Information collected from other sources, such as actors, can be provided as auxiliary data, to enhance the learning. The challenging issue is how to integrate such heterogeneous data sources for learning?

Multi-source learning can also help solve traditional machine learning problems, such as semi-supervised learning [Blum and Mitchell, 1998] and transfer learning [Baxter, 1997], by generalizing the problems as multi-source learning tasks. In semi-supervised learning, data are collected as labeled and unlabeled sets, and the main goal is to use unlabeled set to improve the learning. Common approaches, such as co-training [Blum and Mitchell, 1998], are to assign class labels to unlabeled instances and further include them into the training set for learning. Such an "automatic" labeling process may add a significant amount of class noise [Zhu and Wu, 2003] to the training set. Alternatively, because the representations (i.e. features) of the labeled and unlabeled sets are the same, we can directly calculate the relationship between each labeled and unlabeled instances, which may, in practice, provide useful information to improve the learning of the labeled set.

Harnessing multi-source data and unleashing their full potential for learning is, however, a very challenging problem. This is mainly because of the following reasons:

• Heterogeneous data sources: Multi-source data normally have different data representations and schemas, which make traditional data integration based approaches practically inefficient to aggregate the data for multi-source learning.

• Multi-Source data representation: No common platform currently exists to represent multi-source data in a unified view for multi-source cooperative learning.
• Multi-Source knowledge transferring: Multi-source data are usually collected from different sources and used for different learning tasks. Enabling multi-source learning will have to face the problem of transferring knowledge from one dataset to another, or vice versa.

In this paper, we propose a multi-source omni-view learning framework. The purpose is to deliver a common platform to leverage information frommultiple data sources for learning. In our problem setting, multi-source data are assumed to be heterogeneous with completely different data representations, and no schema mapping or data integration is required for learning. Our problem setting will not only make the solutions widely applicable for real-world multi-source data, but also helps differentiate the proposed work from existing research such as relational mining, which we will address in Section 2.

To achieve the goal, we propose a data representation model which lays the foundation to represent multi-source data in a global multi-source view. Further more, we propose an omni-view multi-source learning framework and a relational k-means clustering method to cluster instances by leveraging information from different sources, such that the clusters can help build new features to capture correlations between data collections.

2 RelatedWork

Existing work in learning from multiple data sources mainly falls into the following three categories: (1) data integration; (2) model integration; and (3) relational learning.

Data Integration: Data integration intends to integrate heterogeneous data collections, such that the learning can be carried out on the integrated data. A crucial step is to map schemas between different data collections [Cohen, 2000]. Instead of relying on schema mapping for data integration, we seek to unify multi-source data through data correlations, so complex schema mapping process can be avoided.

Model Integration: Model integration focus on combining models learnt from each individual sources, under the assumption that schema mapping between data sources is available or a primary key is available to link data sources [Fujibuchi and Kato, 2007; BenDavid et al., 2002]. This has been commonly used for privacy preserving clustering. In comparison, we do not rely on any complex model integration approaches but directly build learners from the data.

Relational Mining: When instances between data collections are relational, a number of works exist for probabilistic relational classification and clustering [Taskar et al., 2001; Deodhar and Ghosh, 2007; Long et al., 2007]. Crammer et al. [Crammer et al., 2008] provides a general theory of selectively combining multi-source data, under the assumption that data sources share identical representations. Multitask, transfer, and semi-supervised learning [Baxter, 1997; Caruana, 1997] represent another body of work where learning can gain benefits from relevant data sources with identical

;#23#23#23#23#23#23#23#23#23#23#23�;#23#23#23#23#23#23#23#23#23#23#23#23;#23#23#23��������;#23#23#23�����������;#23#23#23������;#23#23#23

Figure 2: Unified data representation model for multi-source data

data representation. In comparison, we are dealing with heterogeneous data sources with distinct data representations.

3 Multi-Source Data Representation

To support multi-source learning, we propose to utilize a unified data representation model to integrate multi-source data through a matrix which specifies correlations between data sources. Denoting Dα and Dβ two data collections, each contains a set of instances xα1 , · · · , xαnα , and xβ1 , · · · , xβnβ , where xαi specifies an instance in Dα and nα denotes the number of instances in Dα. Each instance is represented by a set of features/attributes aα1 , ..., aαmα where mα specifies the number of features for instances in Dα . If Dα and Dβ were formed for classification purposes, a class label (Cα or Cβ ) will be assigned to each instance.

To bridge connections between different data collections, we assume that each instance in one data collection has a correlation with one or multiple instances in other data collections, as shown in Figure 2. Given two datasets Dα and Dβ , θxαi ↔xβj denotes the correlation value between the ith instance in Dα and the j th instance in Dβ . In addition, we

also assume that the correlation between i and j is symmetric, i.e. θDα i ↔Dβ j = θDβ j ↔Dα i . If we take the correlation for instances without correlation as zero, then all correlation values between instances in Dα and Dβ form a matrix ΘDα↔Dβ , as shown on the right side of Figure 2.

4 Omni-ViewCooperative Learning

4.1 Omni-ViewDataset Construction

Given a set of data collections Dα , Dβ , · · · ,Dγ , each contains a set of instances with or without class labels. For learning purposes, we assume that at least one data collection should be labeled. Since our data representation model intends to map data from one dataset to another, the one to which the data are mapped is called an objective dataset, and all others are called auxiliary datasets.

Our solution for multi-source learning is to follow the data model in Section 3 and build a special training set for the objective learning task, by leveraging information from all data collections. More specifically, we can list instances in the objective dataset Dα as rows, and map instances from other auxiliary datasets as features(attributes), with each feature value

(a) Movie table

(b) User table

(c) Actor table

given by two instances' correlation value θxαi ↔xβj . We call such dataset an omni-view dataset, as it contains information across data collections. After that, we can apply any existing learning algorithms to the omni-view dataset and generate prediction models.

4.2 Omni-ViewLearning

The employment of the omni-view dataset ensures that learning has the ability of surveying data records in the objective dataset, as well as their correlations with other data collections (global knowledge).

Two challenges remain in order to carry out the learning on the omni-view dataset:

• High Dimensionality. Because we map an instance from one dataset Dβ to another dataset Dα as a new feature. If Dβ has a large number of instances, it will result high-dimensional features in Dα 's omni-view dataset. Learning from high-dimensional data is an identified data mining challenge, therefore we must propose solutions to resolve this issue.
• Test difficulty. Although a learning model can be built from the omni-view dataset, the correlation values between a test and the auxiliary instances may not be im-

mediately available. As a result, although prediction model is global, the prediction is still based on the test instance's local feature values.

To resolve the dimensionality challenge, we propose a relational k-means clustering method to merge instances in an auxiliary dataset Dβ into k groups, Gβ 1 , · · · , Gβ k , and map each group as a new omni-view feature in the objective dataset Dα, as shown in Figure 3. The value of the new feature is calculated such that for each instance xαi in Dα, its new feature value is the average of the mapping values between xαi and all instances in group Gd j , as defined by Eq.(1), where |θxαi ↔Gd j | denotes the number of instances in Gd j which have mapping relationship values with xαi .

Although the above clustering process can significantly reduce the dimension of the omni-view features, we may still have to face the reality that the cluster number k in the auxiliary dataset Dβ may be much larger than the dimension of the objective dataset Dα . In addition, the dimension of the omni-features will cumulate if multiple auxiliary datasets D1 , · · · , Dd are involved. Consequently, we employ the principle component analysis (PCA) process to the omni-view features, and reduce the dimension to be the same as the number of attributes of the objective dataset Dα .

After the above process, the objective dataset Dα will be transformed into an omni-view dataset. Assuming a prediction model is built fromDα's transformed omni-view dataset, the test difficulty arises when classifying a test instance xατ . This is because xατ may only contain feature values with respect to Dα , but has no values corresponding to Dα's omniview features, as the correlations between xατ and instances in the auxiliary datasets may not be immediately available. Our solution is to use each test instance's nearest neighbours Δ in the objective dataset Dα to estimate xατ 's new feature values, as defined by Eq. (2).

22

2

Based on the above articulations, the major steps of the omniview learning framework are given in Algorithm 1.

Algorithm 1 OFL: Omni-view Feature Learning

Require: Objective set: Dα , d auxiliary sets D1 , · · · ,Dd , and mapping relationships ΘDα↔D1, · · · ,ΘDα↔Dd for τ ← 1 to d do Gτ 1 , · · · , Gτ k ← relational-k-means(Dτ , ΘDα↔Dτ , k, T ) end for for each training instance xαi in Dα do f α i ← calculate omni-view features using Eq.(1) F = F ∪ f α i //aggregate omni-view features end for F ′ ← Apply Principle Component Analysis (PCA) to F D′ α ← create omni-view dataset using Dα and F ′ ℏ(D′α) ← train classifier from D′ α ===================TEST================== for each test instance xατ do Δ ← find xατ 's K nearest neighbours in Dα f α τ ← calculate omni-view features using Eq.(2) f ′ α τ ←PCA transformed feature xατ ← xατ ∪ f ′ α τ : test instance with omni-view feature ℏ(D′α, xατ ): classify

end for

return prediction accuracy

4.3 Relational k-Means Clustering

The purpose of the relational k-means clustering is to cluster instances in an auxiliary dataset Dβ into a number of k clusters Gβ 1 , · · · , Gβ k , under matrix ΘDα↔Dβ which specifies the mapping relationships between instances in Dα and Dβ . For general k-means, the objective function is to maximize the intra-cluster instance similarities over all clusters [Duda et al., 2001], as defined by Eq. (3), where S(x, x′ ) specifies the similarity between instances x and x′ , and SGβ i is the average intra-cluster pair-wise similarity for cluster Gβ i .

If instances in Dβ are subject to some mapping relationships ΘDα↔Dβ with the objective dataset Dα , we expect that each cluster Gβ i in Dβ will maximize its intra-cluster similarity SGβ i , and the instances in Gβ i should also minimize the mapping relationship variance with respect to Dα. In other words, if two instances xβi and xβj are indeed similar to each other, they should have large similarity value S(xβi , xβj ), and share similar mapping relationship values with other instances, i.e., low variance.

The above observation motivates a new clustering measure which combines both intra-cluster similarity and the mapping relationship variance. Given each instance xβi in an auxiliary dataset Dβ , assume ΘDα↔xβi =∈ Rnα×1 denotes the relationship of xβi to all (nα) instances in Dα. Assume the existence of a cluster Gβ τ in Dβ , the mean mapping relationship of all instances in Gβ τ is denoted by Eq. (4).

The variance of the mapping relationship of all instances in Gβ τ (w.r.t. Dα ) is given in Eq. (5), where ΔΘ(xβj ,Gβ τ ) =

As a result, the objective function of the relational k-means is given in Eq.(6)

Explicitly solving Eq.(6) is difficult, alternatively, we can employ a recursive hill-climbing search process to find solutions. Assume instances in Dβ are clustered into k clusters, Gβ 1 , · · · , Gβ k , moving an instance x from cluster Gβ i to cluster Gβ j will only change the cluster objective values JGβ i and JGβ j . Therefore, in order to maximize Eq. (6), at each step t, we can randomly select an instance x from a cluster Gβ i , and move x to cluster Gβ j . We accept the movement only if the Inequity (7) reaches a larger value at step t + 1 (i.e. after the movement).

Based on the search process in Inequity (7), major steps of the relational k-means are listed in the Algorithm 2.

Algorithm 2 Relational-k-Means

Require: Dβ , ΘDα↔Dβ , k and T Gβ 1 , · · · , Gβ k ←Apply k-means to Dβ for t ← 1 to T do x ← Randomly select an instance from Dβ Gβ i ←current cluster of instance x JGβ i (t) ←Calculate Gβ i 's objective value JGβ i (t + 1) ←Gβ i 's new value after excluding x for j ← 1 to k, j ̸= i do JGβ j (t) ← Calculate Gβ j 's objective value JGβ j (t + 1) ← Gβ j 's new value after including x if Inequity (7) is true then Gβ j ←Gβ j ∪ x; Gβ i ←Gβ i \ x Break end if end for end for return Gβ 1 , · · · , Gβ k

Accelerated Search Process

In Algorithm 2, each time when we test to move an instance x from cluster Gβ i to Gβ j , we need to recalculate the objective values for both Gβ i and Gβ j . This is a computational expensive process. Using simple math, we can show that accelerated search process exists for calculating JGβ i (t+1) and JGβ j (t+1) from JGβ i (t) and JGβ j (t) directly. Due to the page limit, we omit the technical details in this paper.

5 Experimental Results

5.1 Experimental Settings

We implement the omni-view feature learning (OFL) framework in Java by integrating the WEKA machine learning tool [Witten and Frank, 2005]. In our experiments, the number of nearest neighbors of a test instance is automatically determined by using hold-one-out cross validation (provided by WEKA tool), and the number of clusters for each auxiliary dataset is set as the number of instances divided by 20, with 100 clusters being the maximum. Three learning algorithms used in our experiments include C4.5 decision trees [Quinlan, 1993], Naive Bayes, and Support Vector Machines (the Libsvm package). In all experiments, we use 10 times 10-fold cross-validation to evaluate the algorithm performance.

Benchmark Data: For evaluation purposes, we use 10 UCI machine learning benchmark datasets [Asuncion and Newman, 2007] as our test bed. To create heterogeneous data sources, we sort attributes of each dataset in an descending order, according to their information gain values [Quinlan, 1993]. We sequentially assign each sorted attribute (from the top to the bottom) to one data source, which results in multi-source data containing distinct attribute values. We randomly select one data source as the objective dataset, and the remaining data sources are treated as the auxiliary datsets. Although labeling information is available for both objective and auxiliary instances, we only keep class labels for the objective instances, with auxiliary instances remaining unlabeled. We first calculate the Euclidean distance between any instance pairs (in the original complete feature space). Then, we assign the mapping relationship between an objective instance and an auxiliary instance as the normalized Euclidean distance ([0,1]) between their corresponding instances in the original feature space (computed in the first step).

Benchmark Methods: To evaluate the performance of our method, we compare the results with two baseline approaches. The first method is to train classifiers using local features of the objective dataset only. Such a local feature based learning approach is intended to serve as the lowerbound of all the benchmark methods. The second method assumes that each instance in the objective dataset is able to build some new features identical to the representation of the auxiliary dataset, so the classifiers are trained from the "global" features of the objective dataset. Notice that "global" features are hard to collect unless the schema mapping and a primary index key exist to link objective and auxiliary datasets. In our experiments, because both objective and auxiliary datasets are split from one dataset, we know objective dataset's "global" features. The results of such a "global"

feature based learning provide an upper-bound for all the methods. To demonstrate that omni-view learning is effective for traditional learning tasks, such as semi-supervised learning, we also compare OFL with the classical co-training method (denoted by Co-Tr). For comparison purposes, we also report the results of OFL in an ideal situation where the omni-feature values of a test instance are calculated according to Eq. (1) based on a test instance's known mapping relationships with auxiliary instances (denoted by OFL⋄). A simple description of the above methods are listed in Table 2.

5.2 Omni-viewmulti-source learning results

In Table 3, we report OFL, LFL, and GFL's performance on the benchmark datasets where each dataset is equally split into two sources (one object set and one auxiliary set) with non-overlapping features.

The results in Table 3 show that when considering all benchmark data as a whole, omni-view feature learning (OFL) provides an effective solution to leverage multi-source data to improve the learning on the objective dataset. This is valid for all three learning algorithms, which asserts that OFL is effective for common learners. Compared to the classifiers built from the local features (i.e. LFL), the classifiers trained from OFL are usually more accurate with 1% ∼ 15% or larger (i.e. the Vowel dataset) accuracy gains. If the mapping relationships of a test instance were known (i.e., OFL⋄), OFL can further improve the accuracies to a large extent. On the other hand, the results of GFL show the maximum gains (the upper-bound) we may expect if multi-source data were perfectly aligned (notice that in real-world environments, the results of GFL may not be achievable unless the schema mapping and a primary key both exist to link multi-source data). For some datasets, models trained from partially observed local features may actually outperform the ones learnt from the global features (e.g. the Credit (SVM) dataset). We believe this is mainly because some datasets contain redundant features so using a subset features may help build a better model

(this also explains why feature selection is helpful). Overall, we can expect that OFL significantly outperforms LFL, and occasionally beats the upper-bound GFL (Credit:(C4.5, NB, SVM), Digits:C4.5, Sonar: NB, Waveform: C4.5).

To simulate real-world situations where mapping relationships between some instances are unknown. We randomly select ϵ × 100% of mapping relationships and replace them with a constant value 0.5 (which is the half-way point of the general mapping relationship values [0, 1]). We report the results in Figure 4,which show that although OFL prefers complete mapping relationship values, in practice, it only needs very little mapping information to build learners outperforming LFL. This is mainly because each auxiliary dataset is clustered into a number of groups, so for each instance x in the objective dataset, knowing a small portion of mapping relationships between x and objective instances is sufficient for x to build omni-view features. This observation asserts that although instance mapping relationships between data sources are important, they do not have to be complete to support omni-view learning.

5.3 Omni-view semi-supervised learning results

When using OFL for semi-supervised learning, we split a dataset into two subsets: objective set and auxiliary set, where both sets have the same features as the original data. We discard the labels of the auxiliary instances which results in an unlabeled sample set, and only the objective set contains labeled examples. Then we use co-training and OFL to build prediction models from the objective set, by using auxiliary (unlabeled) instances. For comparison purposes, we also report the results of LFL and GFL. LFL simply trains the models using objective instances only. For GFL, we aggregate both objective and auxiliary instances and assign the genuine class labels to the auxiliary instances and train classifiers from the aggregated data. The results of GFL demonstrate the maximum gains that Co-Tr can possibly achieve.

In Table 4, we report the results of all datasets. In our experiments, we randomly select 20% of instances in each dataset as the labeled set and the remaining instances are taken as the unlabeled set. In addition, we use Co-Tr to assign class labels to 20% of unlabeled instances in 50 repetitions (all parameters are selected to reveal general experimental settings). As shown in Table 4, OFL outperforms Co-Tr from 8 out of 10 datasets. In many situations, the results of Co-Tr are just marginally better than LFL whereas OFL can bring significant improvement, compared to LFL and Co-Tr.

The main disadvantage of the traditional semi-supervised learning methods, such as co-training, is that each unlabeled example is explicitly assigned a class label and included in the training set. Notice that class labels play vital roles for classification, instances with incorrect class labels will act as noise and deteriorate the learner performances [Zhu and Wu, 2003]. To validate our hypothesis, we report the accuracy of the class labels assigned to the unlabeled instances by Co-Tr in the last row of Table 4. As we can see, Co-Tr's average labeling accuracy is between 60% to 90%. This suggests that a significant amount of labeled instances (which are included in the training set) are noisy. When using OFL for semi-supervised learning, although incorrect omni-feature values may also exist, errors in the attributes are actually much less harmful than class errors. In the worst scenario, assume an omni-view feature contains random values, its impact will be easily reduced by OFL's succeeding principle component analysis process.

6 Conclusions

In this paper, we proposed a multiple information sources cooperative learning framework (OFL). Given an objective dataset and its learning tasks, we assume that a number of heterogeneous auxiliary datasets relevant to the objective dataset exist and instances between the objective and the auxiliary datasets may be subject to some mapping relationships. Our solution is to build omni-view features by leveraging information from multiple data collections to achieve multi-source learning goal. Experimental results and comparisons asserted that OFL delivers a simple yet practical platform to support multi-source learning. Such an OFL framework is also beneficial for traditional learning tasks such as semi-supervised learning. The main contribution of the paper, compared to other existing work, is threefold: (1) a common platform to support multi-source learning; (2) a relational k-means for clustering across multiple data collections; and (3) an alternative solution to solve traditional learning problems by using multi-source learning.