Knowledge Transfer on Hybrid Graph

1 Introduction

Transfer learning is a powerful ability of human to apply knowledge and skills learned in previous tasks to novel tasks [Ormrod, 2004]. In modern machine learning and data mining fields, it has been widely investigated to try to simulate this human learning mechanism to achieve artificial intelligence [Pan and Yang, 2007]. Recently, the explosive growth in data warehouse and internet usage has made large amount of unsorted information potentially available for data mining problems. Labeling them is a very expensive and time consuming work. Transfer learning gives us a possible solution to optimally discriminate this type of data. It can borrow some supervised information from other similar tasks to enhance the discrimination of the learning machine for those unlabeled data. For instance, the difference between documents that describe stock and book may help to distinguish the documents that describe investment and research. Though they are different topics with different word distributions, stock and investment both talk about economic stuff, while book and research are topics that relate to education and academia.

This is a typical transfer learning problem that discriminates the totally unlabeled data that are under a different distribution from the labeled data.

In this paper, we focus on above transfer learning approach cross different domains mainly based on text mining problems. In this problem, the labeled data are from a domain D(i) and the unlabeled data are from another domain D(o) . D(i) is called in-domain and D(o) out-of-domain. In addition, it is assumed that in-domain D(i) and out-of-domain D(o) are related to make the domain-transfer learning feasible. The objective is to discriminate the data from out-ofdomain D(o) as accurately as possible with the help of the data from in-domain D(i) . Several previous works have been done for this problem, which are Co-Clustering based Classification (CoCC) [Dai et al., 2007] and Cross-Domain Spectral Classification (CDSC) [Ling et al., 2008]. CoCC is based on information-theoretic co-clustering [Dhillon et al., 2003]. It regularizes the out-of-domain discrimination problemwith the in-domain word partition. The labels of in-domain documents first propagate to the words and then the clustering of the words propagate to the out-of-domain documents. The procedure iterates until convergence. CDSC is based on spectral learning [Kamvar et al., 2003]. It seeks an optimal partition of the data, which preserves the supervised segmentation information for the in-domain data and splits the outof-domain data as separately as possible in terms of the cut size. The experiments in their papers have shown great improvements to conventional supervised and semi-supervised methods. However, there remain problems.

• The information-theoretic co-clustering heavily relies on the initialization. The initialization of document clusters are relatively easy. However, the word clusters may not be wellestablished. Even human experts could not well cluster such large amount of words themselves.
• Both methods have many heuristic parameters which the result relies on, especially the trade-off parameter for indomain and out-of-domain information. To choose satisfied parameters is difficult for practical applications.
• Each of them only uses a part of the cross domain similarity. CoCC focuses on the conjunct word clustering, and CDSC focuses on the document similarity. In these situations, neither of themmakes full use of the relationship among the relational data.

Focusing on above problems, we proposed a novel transfer learning framework on a hybrid graph. We set both documents and words as vertexes in one graph. The transfer learning procedure is conducted across different parts of the graph. First, we present an algorithm label propagation. It employs spectral analysis of the modified similarity between homogeneous relations cross domains to propagated the discriminative information. Moreover, a further algorithm, similarity propagation, is proposed. It can effectively alleviate above problems. In this algorithm, we pursue the transferred information among both document similarity and word clustering. It uses all available routes to transfer and get better and more stable results.

The rest of the paper is organized as follows. In section 2, we formulate the problem and present our algorithms. Section 3 reviews the related works and analyzes the involved problem. Section 4 shows our experiments. Finally we conclude the paper and discuss some future work in section 5.

2 Knowledge Transfer on Hybrid Graph

In this section, we present our transfer learning method on hybrid graph, and show the two algorithms label propagation and similarity propagation.

2.1 Problem Formulation

Let D(i) = {d(i) 1 , d(i) 2 , ..., d(i) Ni } be the in-domain data set, with Ni labeled documents, D(o) = {d(o) 1 , d(o) 2 , ..., d(o) No } be the out-of-domain data set, with No unlabeled documents. Each document is represented as a vector of word frequencies. Both document sets share the same word vocabulary W = {w1, w2, ..., wM}, where M is the vocabulary size.

Given the document set D = {D(i) , D(o)} and the word set W, we build a hybrid graph with each document and word as its vertex, and the edge between each pair of vertexes denotes their similarity. It is similar with the bipartite graph in spectral co-clustering [Dhillon, 2001; Zha et al., 2001]. However in bipartite graph, it assumes the relations among documents are zeros.

In this paper, we construct the hybrid graph that involve all kinds of relationships, which is shown in Fig. 1 (a). The co-occurrence matrix between documents and words is still used to represent their similarities, which is R(di,w) ∈ RNi×M for in-domain data and R(do,w) ∈ RNo×M for out-of-domain data. The similarities between documents are denoted as S(di,di) ∈ RNi×Ni , S(di,do) ∈ RNi×No , S(do,di) = S(di,do)T ∈ RNo×Ni , S(do,do) ∈ RNo×No and S(w,w) ∈ RM×M . The whole similarity matrix can be formulated as:

which is shown in Fig. 1 (c). We divide the similarity relationship into two types, defined as follows.

Definition 1. (Homogeneous Relations) The relations between documents and documents are denoted as homogeneous relations, described by S(di,di) , S(di,do) , S(w,w) and S(do,do).

Definition 2. (Heterogeneous Relations) The relations between documents and words are denoted as heterogeneous relations, described by R(di,w) and R(do,w) .

Without loss of generality, we assume the class or clustering numbers of in-domain documents, out-of-domain documents and the words are Kdi, Kdo and Kw respectively. Then we define their indicator matrices as:

where x can be di, do or w, π(x) q is the number of objects in the qth cluster in the corresponding set. And we have (C(x) )T C(x) = IKx , where IKx ∈ RKx×Kx is the identity matrix.

Using the indicator matrix, we calculate the corresponding similarity matrix within the homogeneous data sets as:

diag(π(di) ) ∈ RKx×Kx is the diagonal matrix, where the elements are π(di) q , q = 1, ...,Kx. The in-domain documents have the groundtruth labels. Thus we denote the class indicator matrix as ¯C(di) , and the corresponding similarity matrix as ¯S(di,di) .

Moreover, to balance the relations and similarities, we normalize them as

where ¯D(di,di) pp = ∑q ¯S(di,di) pq , D(do,do) pp = ∑q S(do,do) pq , D(w,w) pp = ∑q S(w,w) pq , D(di,w) pp = ∑q R(di,w) pq , D(w,di) qq = ∑p R(di,w) pq , D(do,w) pp = ∑q R(do,w) pq and D(w,do) qq = ∑p R(do,w) pq . This is inspired by the normalized cut [Shi and Malik, 2000] and spectral co-clustering [Dhillon, 2001]. After the normalization, the similarity matrix of in-domain documents can be re-written as ¯S(di,di) = ¯C(di) ( ¯C(di) )T and we can easily verify that the Moore-Penrose pseudoinverse is ( ¯S(di,di) )† = ¯S(di,di) .

Based on the description above, our problem is to find the unknown indicator matrix C(do) for the out-of-domain data. In the next two subsections, we will present two novel algorithms to deal with this problem.

2.2 Label Propagation

The main idea of label propagation is to transfer the supervised information from in-domain to out-of-domain through the similar word structure they share. We adopt the spectral relational clustering method [Long et al., 2006] for both indomain and out-of-domain data simultaneously. The objective function is:

where H(di,w) ∈ RKdi×Kw and H(do,w) ∈ RKdo×Kw denote the co-occurrence relationship between clusters of documents and words. This objective aims to find the best partition of both out-of-domain documents and word vocabulary, under the restriction from the in-domain relational structure.

Taking in indicator matrixes constraints, the final task is

Based on the analysis in [Long et al., 2006], we can deduce that the optimal association matrixes are H(di,w) = ( ¯C(di) )T R(di,w)C(w) and H(do,w) = (C(do) )T R(do,w)C(w) for our objective. Take these results into the objective function Eq. (5), we have:

where tr(·) is the trace of a matrix. Note that

and

We can see that the objective is convex w.r.t. both C(do) and C(w) . As a result, we use alternating optimization technique Input: The labeled in-domain data set D(i) , unlabeled out-of-domain data set D(o) and the word feature set W.

Table 1: Transfer Learning by Label Propagation

Initialize: The heterogeneous relations R(di,w) and R(do,w). The indicator matrices ¯C(di) and C(do) .

Repeat:

1: Update C(w) by the leading Kw eigenvectors of

2: Discretize C(w) as in [Yu and Shi, 2003].

• 4: Discretize C(bo) as in [Yu and Shi, 2003].

Until: Convergence.

Output: The label indicator matrices C(do) and C(w) .

to find the optimal solution. The following Ky-Fan theorem guarantees a closed-form solution for each alternative step.

Theorem 3. (Ky-Fan Theorem) [Bhatia, 1997] Let S be a symmetric matrix with eigenvalues λ1 ⩾ λ2 ⩾ ... ⩾ λK and corresponding eigenvectors U = [u1, u2, ..., uK]. Then ∑Ki=1 λi = maxV T V =IK VTSV. Moreover, the optimal V is given by UT where T is an arbitrary orthogonal matrix.■

Based on this theorem, we can calculate C(do) and C(w) alternatively until converged. This procedure is shown in Fig. 1 (b). The"labels" of in-domain and out-of-domain documents first propagate to the words, then the "labels" of words propagate back to the out-of-domain documents. The algorithm is summarized in Table 1. Since the objective function (5) is convex for each variable, it has local optimum.

2.3 Similarity Propagation

In the label propagation algorithm, it only uses the heterogeneous relations to conduct the transfer procedure, which is similar with [Dai et al., 2007]. Although we can add a tradeoff parameter to control the strength of the information transfer, like [Dai et al., 2007], the homogeneous relations are still ignored. In this situation, the optimal transfer can hardly be achieved. In this subsection, we propose a more efficient algorithm, similarity propagation, to make full use of the available information.

In the similarity propagation algorithm, we do not merely stare at the discrimination indication for the documents and words, but aim at revealing all types of similarities in the hybrid graph as shown in Fig. 1 (c). In this setting, the heterogeneous relations of the data and the in-domain homogeneous relations (given by the document labels) are provided. The task is to recover all other homogeneous relations as better as possible. During this reconstruction process, the Nytr¨om method is needed for matrix approximation.

Theorem 4. (Nytr¨om approximation) [Williams and Seeger, 2001] Let positive semi-definite matrix S be blocked as

If Q is missing, the the first K eigenvalues of S and the corresponding eigenvectors can be approximated as

where λP,i and uS,i are the leading non-zero eigenvalues and corresponding eigenvectors of P. And S can be approximated as ∑ uS,iλS,iuS,iT . Moreover, the quality of the approximation can be quantified by the norm of the Schur complement

where || · ||F represents the Frobenius norm of a matrix, O† is the Moore-Penrose pseudoinverse. ■

Based on theorems 3 and 4, we can make use of eigenvalue decomposition approach to approximate S defined in Eq. (1) alternatively. Reset the blocked S as

We implement the approximation alternatively by two steps: first compute ˆQ = PT O†P; second compute ˆO = PQ†PT and reset S(di,di) = ¯S(di,di)1 . This procedure can be seen as a propagation of the similarities of full homogeneous relations through heterogeneous similarity, which is shown in Fig. 1 (c). The propagation stops when the recovered unknown similarity blocks are no longer changing. The flow chart is given in Table 2 2 .

Moreover, in the following corollary, we show that label propagation method can also be formulated as an alternative Nytr¨om approximation for the similarity matrix.

Corollary 5. Label propagation is also corresponding to a two-step Nytr¨om approximation procedure.

Proof: In this situation, the similarity matrix S is reset as

The Nytr¨om approximations lead to S(w,w) = R(di,w)T ( ¯S(di,di) )†R(di,w) + R(do,w)T (S(do,do))†R(do,w) and S(do,do) = R(do,w)S(w,w) † (R(do,w))T . Using the similarity definition in Eq. (4) we have ( ¯S(di,di) )† = ¯S(di,di) , (S(do,do))† = S(do,do) = C(do)(C(do) )T and Input: The labeled in-domain data set D(i) , unlabeled out-of-domain data set D(o) and the word feature set W.

1 To guarantee the validity of nytr¨om method, S(di,do) will be re-initialized if the positive semi-definition of S is violated.

2 The initialization of S(do,do) can be done using any clustering method or semi-supervised method with the help of the labeled data. And S(di,do) can be initially calculated as the inner product of ¯C(di) and C(do) . Instead of these, we can initialize S(w,w) and start from the second step.

Table 2: Transfer Learning by Similarity Propagation

Initialize: The heterogeneous relations R(di,w) and R(do,w). The homogeneous similarities S(di,di) = ¯S(di,di) , S(do,do) and S(di,do) . Set O, P and Q as the forms in Eq. (11).

Repeat:

• 1: Update Q = PT O†P .
• 2: UpdateO= PQ†PT .

Until: Convergence.

Output: The label indicator matrices C(do) and C(w) are computed by using normalized cut algorithm with homogeneous similarities S(do,do) and S(w,w) .

(S(w,w))† = S(w,w) = C(w) (C(w) )T . Take these back into the above equations, the corollary is proven. ■

As it is shown in corollary 5, in label propagation algorithm, it assumes that R(di,do) = 0 and the similarities in S(do,do) are only propagated from S(w,w) . Similarly analysis can be done to show that CoCC loses R(di,do) , and CDSC loses R(w,w). This is the reason why these methods are insufficient. We will approve this empirically in section 4.

3 RelatedWorks

The most related works to our approach are transfer learning, semi-supervised learning and spectral clustering. We will look through these works and present our understanding for the transfer learning problem in this paper.

3.1 Learning with Labeled and Unlabeled Data

In our problem, there are both labeled and unlabeled data. The most popular technique used to learn with labeled and unlabeled data is semi-supervised learning [Zhu, 2005]. Many successful methods have been proposed under this topic, such as tranductive SVM [Joachims, 1999] and manifold regularization [Belkin et al., 2006]. However, the conventional semi-supervised learning methods have a strict assumption that the labeled and unlabeled data should be sampled from the same distribution, which is always not the case in real applications [Pan and Yang, 2007].

Transfer learning is thus adopted to solve such a complex problem. Besides, it can be used in many other cases, such as learning with different training and test data distributions [Sugiyama et al., 2007] and learning multiple tasks [Caruana, 1997]. The problem in this paper is just a particular setting for transfer learning, which transfers the labeled information to a totally unsupervised task. We can not arbitrarily judge whether the out-of-domain task is a classification or a clustering task. As the data have hiberarchical structure. In the small scale, these data have their own class attributes which are different from the in-domain label information. In the large scale, the data out-of-domain and in-domain may be subject to a same wide type. From this point of view, both conventional clustering methods and semi-supervised methods can be modified to tackle this transfer learning problem. What we borrow is the spectral clustering method.

3.2 Spectral Learning

When we represent the data as a graph, spectral analysis is easily adopted to investigate the structure of these data. The normalized cut [Shi and Malik, 2000] is one of the most representative work for spectral clustering. [Kamvar et al., 2003] extends this type of methods to more learning situations, e.g. under pairwise link constraints or with labeled examples. Instead of clustering data using homogeneous relations, co-clustering techniques have been developed to cluster data using heterogeneous information with bipartite relationships, which are mainly used for document clustering [Dhillon, 2001]. Recently, spectral clustering has been extended to multi-type relational data and many well-known algorithms are unified into a general framework [Long et al., 2006; 2007].

In next section, we will compare the mainly related methods described in this section with our algorithms for our transfer learning problem.

4 Experiments

In the experiments, we use the real text data to demonstrate the effectiveness of our algorithms.

20-NewsGroups Data: The 20-newsgroups data set collects approximately 20,000 documents across 20 different newsgroups. It is widely used to test the performance of text mining algorithms. The data is preprocessed as [Zhong and Ghosh, 2005]. And we set up the cross domain transfer learning data sets in a similar way as [Dai et al., 2007; Ling et al., 2008], which focus on binary problems 3 . It means Ki = Ko = 2. Table 3 shows the data sets in the experiments. Compared Methods: Most of the related state-of-theart methods are compared. They are support vector machine (SVM), LapSVM for manifold learning [Belkin et al., 2006], transductive SVM (TSVM) [Joachims, 1999], SKmeans [Dhillon and Modha, 2001], normalized cut (NCut) [Shi andMalik, 2000], spectral co-clustering (S-Co-C), information theoretical co-clustering (IT-Co-C), CoCC [Dai et al., 2007] and CDSC [Ling et al., 2008].

3 Our algorithm is designed using arbitrary class numbers to design a general framework. However, the compared methods are binary. We will leave the multi-class case for future study.

Experimental Result: The supervised method is trained in-domain and tested using out-of-domain data; The semisupervised methods are applied in a transductive setting using all available data. The clustering methods are conducted directly for out-of-domain data. As the existence of supervised information, all clustering methods can assign the cluster in their result with the most relevant in-domain class as in [Dai et al., 2007]. Then the learning accuracy can be used as the performance measure for all compared methods. For the parameter setting, Kw = Ki +Ko = 4 is fix for label propagation as the algorithm demands. In similarity propagation, the result is not sensitive to Kw, which is shown in Fig 2. These make our methods have few heuristic factors and easy to apply. The parameters for all other compared methods are set to a relatively best one according to the referenced papers.

Each experiment has 20 repeated runs and the average learning accuracy with standard deviation is presented in Table 4. S-Co-C-LP is our label propagation algorithm, and S-Co-C-SP is the similarity propagation. The results show our methods perform the best, which approves our analysis in section 2. Note that the normalized cut sometimes gets the similar good result, which means the unlabeled data set is well discriminated itself.

5 Conclusion and Discussion

In this paper, we analysis the across domains transfer learning problem, establish a framework of transfer learning with similarity matrix on hybrid graph, and propose two practical algorithms. During the transfer process, we seek all possible approaches to transfer the useful information from the indomain data to the out-of domain data. The experiments on text data mining show the efficiency of our method.

This paper solves the problem of how to transfer and how to make optimal use of the available information. However, it assumes that the data in different domains are closely related to make the domain-transfer learning feasible. In practical problems, it is still inconvenient for users to find the similar tasks themselves. So it is more contributive to solve the what to transfer problem. This is an interesting and challenge issue for our future study.

Acknowledgments

We gratefully acknowledge the helpful discussion and insightful advice of Chih-Jen Lin, Edward Y. Chang and Qiang Yang. We also thank Xiao Ling for his discussion about the implementation of his algorithm. This research was supported by National Science Foundation of China ( No. 60835002 and No. 60721003 ).