Determining Expert Research Areas with Multi-Instance Learning of Hierarchical Multi-Label Classification Model

1 Introduction

In many large commercial, academic and government organizations, it is often important to identify experts in specific topics. This leads to extensive research on expert retrieval [Hertzum and Pejtersen, 2000; Balog et al., 2009; 2012; Rybak et al., 2014], where the goal is to uncover associations between experts and topics. Microsoft Academic Search is one example of such an expertise retrieval system. One important task of expert retrieval is expert profiling [Balog and De Rijke, 2007; Berendsen et al., 2013], which answers the question: what topics does a person know about. In academics, expert profiling identifies the research areas of researchers. This is essential for building expertise organizations or search systems, which help build expert profiles or determine knowledgeable people for given topics respectively. In general, based on researchers' expertise like documents of publications and research projects, we can view this task as a multi-label text classification [Elisseeff and Weston, 2001; Zhang and Zhou, 2005] problem that generates a set of research areas. However this task is challenging due to its characteristics. First, the evidence of a research area may only exist in a few instead of all documents of a researcher (multi-instance learning problem). Second, research areas are often organized in a hierarchy, which requires effective methods to deal with the label correlations (hierarchical multi-label problem).

Multi-instance Learning (MIL) [Dietterich et al., 1997] studies the case that each bag is composed of multiple data instances, with the assumption that a bag is labeled positive if at least one of its instances is positive, whereas a negative bag only contains negative instances. In the work of [Andrews et al., 2002], two different large margin methods have been proposed, i.e., mi-SVM for instance level classification and bag level method MI-SVM. In [Chen et al., 2006], bags are embedded into a feature space spanned by all the instances. A more recent work in [Wang et al., 2012] proposes a mixture model approach. Most recently, the work in [Wang et al., 2014] boosts the learning performance by adaptive knowledge transfer.

In Multi-label Classification (MLC), objects are associated with a set of labels. Recent works include RankSVM [Elisseeff and Weston, 2001], ML-kNN [Zhang and Zhou, 2005] and Max-margin multi-label [Hariharan et al., 2010]. The joint multi-instance multi-label problem [Jin et al., 2009; Nguyen et al., 2014] has also attracted a lot of attentions. One specific case of MLC is Hierarchical Multi-Label classification (HML) [Barutcuoglu et al., 2006; Schietgat et al., 2010], in which labels have hierarchical structures. Hierarchical Max-margin Markov (HM3 ) Network [Rousu et al., 2006] has been proposed to model the label hierarchy, where it follows the framework Max-Margin Markov network (M3 ) [Taskar et al., 2003].

However, none of the existing work addresses the expert profiling task effectively, which requires a combination of MIL and HML. This paper models the expert profiling task as Multi-instance Learning of Hierarchical Multi-label Classification (MIHML) problem. Within this framework, we not only incorporate the correlation between multiple research areas in a hierarchy, but also explore the association between individual documents and research areas. In particular, the document-area pair is modeled using Markov network under a unified probabilistic learning framework. In this model, we need to find the correct research areas for each single document as well as the optimal model parameters. This leads to a mixed integer programming problem that cannot be solved efficiently. We propose a novel optimization method called Expectation and Maximization Hierarchical Maximum-Margin Markov Network (EM-HM3 ) algorithm to solve the MIHML problem, which optimizes over the model parameters and instance-label assignments alternatively to obtain an optimal solution.

To evaluate the performance of the proposed EM-HM3 method on expert profiling, we compare it to multi-label SVM, MIMLSVM [Zhou and Zhang, 2006] and HM3 with an extensive set of experiments with a real world expertise database system. We demonstrate the advantage of EM-HM3 with research areas in each level of the research hierarchy, and validate the effectiveness for different sizes of training data. Experimental results show that our approach outperforms several existing MIML and HML methods, in both accuracy and the ability of dealing with small training size.

2 MaximumMargin Hierarchical Multi-label Classification

We first introduce the framework of Max-Margin Markov (M3 ) Network [Taskar et al., 2003] and its Hierarchical solution HM3 [Rousu et al., 2006]. Consider a data domain X × Y, where X is a set of instances, and the label set is Y = Y1 × · · · × Yk with Yj = {+1,-1}, j = 1, · · · , k. We call a vector y = (y1, · · · , yk) ∈ Y a multilabel and its component yj a microlabel. For hierarchical labels, they naturally forms a Markov Network: G = (Y, E), where there is an edge e = (i, j) between microlabels yi, yj if one microlabel is the parent of the other. Thus the network represents the dependence between microlabels. For each edge e = (i, j), the network potential is ψij(x, yi, yj) = exp(wT e φ(x, ye)), x ∈ X, ye = (yi, yj). The network gives a joint conditional probability distribution:

with normalizing factor Z(x, w) = ∑y exp(wT φ(x, y)).

2.1 Max-Margin Learning

Given the training data {(xi, yi)}mi=1 , we have the following optimization problem:

Unfortunately the above problem is difficult to solve directly for a general graph G. An alternative way is to maximize the ratio P(yi|xi;w)/P(y|xi;w), which is equivalent to maximize the minimum linear margin: wT φ(xi, yi) wT φ(xi, y), and it leads to the following max-margin optimization problem:

where ∆φ(xi, y) = φ(xi, yi) - φ(xi, y), and ℓ(yi, y) is the value of loss function for multilabels yi and y. The dual form can be written as:

where K = ∆ΦT ∆Φ is the joint kernel matrix of the training examples. Marginal dual methods can be applied to reduce the size of dual variables from exponential to polynomial. For an edge e ∈ E, and a restricted labeling ye, the marginal of α(i, y) is defined as:

We can define a decomposable loss function as ℓ(yi, y) = ∑e∈E ℓe(i, ye) and a decomposable feature vector φ(x, y) = (φe(x, yE))e∈E, which lead to a decomposable joint kernel K(x, y; x′ , y′ )=∑e∈E φe(x, ye)T φe(x′ , y′e ) = ∑e∈E Ke(x, ye; x′ , y′e ). Then the original dual problem is equivalent to the following form:

where Ee = {(e, e′ ) ∈ E × E|e = (j ′ , i), e′ = (i, j)}. The above formula is a polynomial-sized quadratic program, which can be solved efficiently [Rousu et al., 2006].

3 Multi-instance MaximumMargin Hierarchical Multi-label Classification

In this section, we present the novel approach of Multiinstance Learning of Hierarchical Multi-label Classification based on Maximum Margin. For multi-instance learning problems, one can always concatenate the features of multiple instances (individual documents) into a single feature vector (a single vector of an expertise profile), and treat it as a traditional single-instance learning task. However, this procedure fails to utilize the multi-instance structure of this problem. Moreover, in many cases, there exist some labels (e.g., research areas) that are only associated with certain instances (documents) of the bag (the profile). Thus we want to explore the intrinsic relations between multiple instances and hierarchical labels. Given an example bag x(i) = (x(i) 1 , · · · , x(i) Ri ) (documents of an expert) with labels yi ∈ Y (labels of research areas), where x(i) 1 , · · · , x(i) Ri are the multiple instances in the bag, the ideal case is that we also know the exact instance-label pair (x(i) j , y(i) j ) for j = 1, · · · ,Ri. In contrast to MIMLBoost [Zhou et al., 2012], which takes y(i) j = y(i) , for j = 1, · · · ,Ri, we assume that each instance contributes different parts to the bag labels, which is illustrated in Fig 1.

3.1 ProblemFormulation

We consider a set of training examples: {(x(i) , y(i) )}mi=1 , where each bag x(i) is a set of Ri instances {x(i) 1 , x(i) 2 , · · · , x(i) Ri }, x(i) j ∈ X, and y(i) ∈ Y is the multilabel of the corresponding training bag. According to formula (1), for each instance x(i) j the distribution of its multilabel can be written as:

where Z(x(i) j ,w) = ∑y(i) j exp(wT φ(x(i) j , y(i) j )) is the normalizing factor. The joint probability of all the training examples is represented as: ∏mi=1 ∏Ri j=1 P (y(i) j |x(i) j ;w). In the joint probability, w is the model parameter which needs to optimize. y(i) j (1 ≤ i ≤ m, 1 ≤ j ≤ Ri) are instance labels, which are also unknown. In order to maximize the joint probability, we have to optimize over both w and y(i) j :

Note that the instance labels above are actually constrained as they are highly related to the bag labels. In the task of expert profiling, we assume that a positive research area of a profile implies that at least one of the documents in this profile is positive, while a negative research area of a profile means that all its documents are negative. Based on this assumption, we can have the following constraints on instance labels:

where Si = {(y1, · · · , yRi )|y(i) = ∨Ri j=1 yj} and the operator ∨ denotes the boolean union operation.

The optimization problem in Eqns. (5) and (6) leads to a mixed integer programming problem, with a feasible domain size: ∏mi=1 |Si|, which grows exponentially with the training data. On the other hand, we notice that for any fixed instance labels, the optimization problem can be solved efficiently by max-margin method. Therefore, we can solve the optimization problem iteratively.

3.2 Optimization

Here we apply Expectation-Maximization (EM) algorithm to get an approximate solution of the above optimization problem. For the sake of convenience, we denote the instance labels as Z = Z1 × · · · × Zm, where Zi = (y(i) 1 , · · · , y(i) Ri ),

∀1 ≤ i ≤ m, s.t. Z ∈ S, where S = S1 × · · · × Sm , and we denote the bag labels as Y = (y(1) , · · · , y(m) ). Then we can write the joint probability as:

During the M-step in the EM algorithm, we update the wold with wnew from:

The above problem (7) requires us to sum over all feasible Z, which is computational intractable as the size of feasible Z is exponential with the training size m. It is also difficult to obtain the exact values of P (Z|Y, w) and P (Y, Z|w) since computing the normalization factors Z(x(i) j ,w) = ∑y(i) j exp(wT φ(x(i) j , y(i) j )) is non-trivial.

The general EMmethod indicates that the parameter wnew should be calculated based on all feasible values of instance labels Z. However, for less likely instance labels, which means the value of P(Z|Y,wold ) is relatively small, it is unlikely to make a big difference for selecting the wnew . Moreover, the model essentially works by focusing on the most relevant instance labels Z, which has the highest posterior probability P(Z|Y,wold ). Therefore, a revision of the general EM for our problem is:

1. Choose an initial parameter wold .
2. E-Step Calculate Z∗ = argmaxZ∈S P(Z|Y, wold ).
3. M-Step Evaluate wnew given by wnew = argmaxw log P (Y, Z∗ |w).

1. Check whether it satisfies the stop criterion. If not, replace the parameter value by wold ← wnew and return to step 2.

For M-Step, max-margin method is used to transform the optimization problem to:

Then the marginal dual method (3) can be applied to solve the above problem (i.e., by solving the dual variable µ).

For E-Step, we search among the domain S and find the optimal instance labels Z∗ with highest posterior probability P(Z|Y,wold ). This is also transformed into the maxmargin framework, where we set the instance labels to minimize C ∑mi=1 ∑Ri j=1 ξ (i) j . This is done by labeling the instances based on the parameter wold . Thus the objective of (8) decreases for the fixed wold we obtained from M-Step. Since the objective (8) decreases after each iteration, and it has a lower bound 0, the algorithm will converge to an local minimal. In our implementation, we terminate the algorithm at the iteration where the decrease of the objective is small enough. The detailed stop criterion is discussed at the end of this section.

E-Step is an inference problem (i.e., predicting multilabels) which is equivalent [Rousu et al., 2006] to solve the following problem for each instance i:

where gi = ℓi -Kiµ is the gradient of the objective function in (3). Here we use both the notations w and µ, but they are equivalent since µ is the dual variable of w. We denote by Gj = (Vj,Ej) the subtree of G rooted at the microlabel yj. Inspired by a botton-up procedure, we define the following two functions:

• Tyj (i, j) the best objective (9) value obtained for instance i in the subtree rooted at the node j when the microlabel yj has been fixed.
• Gyj (i, e) the best objective (9) value obtained for instance i in the subtree rooted by the edge e = (j, j ′ ) when the microlabel yj has been fixed.

These two functions are computed in the following manner:

where ge(i, yj, yj ′) is the element value of gi on the edge (yj , yj ′ ).

At the root, maxy Ty(i, root) gives the optimum, and we can track back the labels based on this optimum condition. Since we have the domain constraints, we will assign Tyj (i, j) to -∞ for all i, yj if yj = +1 while the corresponding microlabel yj for the bag is -1. This way each instance i will not be labeled positive if the corresponding bag is negative.

Then for each positive microlabel yj of each bag, if all its instances are labeled negative at yj, we will select the instance that has the minimum decrease of the objective value (9) when changing its mircolabel yj to positive, and make yj positive for this instance. After these procedures, the instance labels satisfy the domain constraints.

Algorithm 1 EM-HM3 for Multi-instance Hierarchical Multi-label Classification

Require:

Training Data: X = {x(i) j }m,Ri i=1,j=1 , Y = {y(i)}mi=1 Hierarchical Max-margin Multi-label classification function: w = HM3 (X, Y);

Ensure:

Optimal parameter w∗ .

• 1: Initialize instance labels ˜Z: y(i) j = y(i) , ∀i, j.

2: REPEAT:

Make Tyj (i, j) = -∞ if the corresponding bag label is negative

Update labeling ˜Z: y(i) j = argmaxy∈Y gT i µ(y) FOR every i in {1, 2, · · · ,m}:

IF ˜Zi /∈ Si as for some microlabel yk:

where y′(i)

j only differs from y(i)

WHILE ( ˜Z ̸= Z)

• 3: return w;

j in yk

The EM-HM3 algorithm is presented in Algorithm 1. Once we obtain the solution of the parameter w, for the expert profile x(i) with unknown research areas, we can acquire the research areas y(i) j for each document in the profile, and then predict research areas of the profile as y(i) = ∨Ri j=1 y(i) j .

In practice, we use a different stop criterion. We notice that the number of different microlabels between ˜Z and Z has a decreasing trend, and after first several iterations it will fluctuate around some small number. So we terminate the algorithm when |˜Z ̸= Z| ≤ α|Z|. Also the optimization problem (8) is solved by the marginal dual method which gives an approximate solution, so we terminate the algorithm when the objective of the dual problem does not have enough increase: ˜ obj - obj ≤ β ∗ obj.

3.3 Discussions

In the determining expert research areas task, there exist correlations among multiple research areas, and between documents and research areas. HM3 only models the hierarchical relations between multiple research areas, which fails to handle the MIHML problem. Our EM-HM3 also explores the correlation between documents and research areas via optimizing document based research areas under the constraint that these research areas are consistent with the profile. This procedure enables us to uncover the evidence inside the documents for research areas. We notice that research areas in lower levels (levels far from the root) of the hierarchy tend to have weaker evidence, which may only exist in very few documents, so it is more challenging to predict them correctly. In this case, EM-HM3 achieves a boost of the accuracy in lower levels compared with other methods.

Moreover, if training examples are insufficient, the classification models learned from the sparse information by previous MIL and HML methods will be less effective. On the other hand, our model fully explores the problem structure using multi-instance and hierarchical multi-label learning. Therefore it achieves much better results under the situation that the number of training examples is small.

4 Experimental Evaluation

We test our algorithm with a public expertise database INDURE 1 . In this dataset, an expertise profile describes professional information of a researcher, including his/her background, publication list, funded projects, and theses as individual documents. The research areas are organized by the hierarchy of National Research Council 2 . For instance, biochemistry, public science and neuroscience are branches of life science, while biochemistry also has branches like molecular biology and structural biology. Funding section provides the information of funded projects; thesis section is displayed with the abstracts of thesis documents. We extract features from these documents by TF-IDF [Salton, 1970] weighing method with word stemming and stop-word removal. Each document feature is a 2,000-dimension vector.

There are 1,132 research areas and 1,930 different expert profiles (bags), associated with 22,049 documents (instances) in total. Labels are consistent in this dataset, that is if a microlabel is positive, then its parent is positive. We notice that most of the research areas are only present in very few profiles 3 . This is a common problem of tail labels in MLC. Since this work focuses on the Multi-instance and Multi-label aspects rather than the zero-short learning problem [Palatucci et al., 2009], we remove the sparse labels which are labeled fewer than 30 times in expert profiles. The label set consists of 87 microlabels that form a hierarchy of depth 5: one root microlabel with 3, 8, 58, 17 microlabels in level 2 to level 5

1 www.indure.org

2 http://www.rackham.umich.edu/nrc/taxonomy/

3 Most of the research areas are labeled fewer than 5 times.

respectively. Among the 1,930 profiles, 33.4% of them belong to more than one leaf node (i.e., the bottom level) of the hierarchy. The minimum number of microlabels associated with a profile is 2, while the maximum is 16, and the average number is around 6.

We want to answer the following questions in the experiments: 1). Whether the hierarchical multi-label classification scheme helps to improve the performance compared to traditional multi-label methods? 2). Whether the multi-instance scheme outperforms single-instance learning? 3). How effective is the proposed approach compared to existing methods under different training sizes?

4.1 General Result

Since both HM3 and EM-HM3 are max-margin based algorithms, we select multi-label SVM (MLSVM) and MIMLSVM [Zhou and Zhang, 2006] for comparisons, both of which have achieved excellent performances in the multilabel classification and the multi-instance multi-label setting respectively [Zhou et al., 2012]. MLSVM learns each research area separately with the constraint that child node can be positive only when its parent node is positive. It is implemented by LIBSVM [Chang and Lin, 2011]. MIMLSVM is an algorithm that first maps the original multi-instance to a new feature space, f : x(i) → zi, where the dimension of zi is a ratio γ of the training size, then applies MLSVM to learn the classification problem {zi, y(i)}.

We use the standard information retrieval statistic F1 to evaluate the performance, where F1 = 2PR/(P + R), and P denotes precision, R denotes recall. In order to highlight the differences between research areas in different levels of the hierarchy, the results are presented in level-wise.

Linear kernel is used in all four methods to conduct fair comparisons. Ten-fold cross validations are performed, where the regularization parameter is tuned by maximizing the sum of F1 values of all levels. For MIMLSVM, the ratio γ is set to be 20%4 . For EM-HM3 and HM3 , we use the following loss function: ℓ(y, v) = ∑j cj[yj ̸= vj] where croot = 1, cj = cpa(j)/|sibl(j)|, in which pa(j) and sibl(j) denote the parent and the set of siblings of research area yj respectively. Since MLSVM and HM3 are not designed for multi-instance learning, we create a feature vector for each profile by treating the affiliated documents as a single one and implement MLSVM and HM3 by using profile features.

4 We tried several γ from 20% to 50%, and it turned out that the higher value of γ does not have a big impact on the result.

Table 1 depicts the level-wise result of different algorithms for a fixed training size 400, together with the standard deviations. It can be seen from this table that MLSVM gives the best result for level 2, but the differences among the four methods are very small. For the later 3 levels, EM-HM3 has the highest F1 values, with an increasing advantage from level 3 to level 5. The reason is that for higher levels (i.e., levels close to the root of the tree), there are fewer research areas, which make the classification task easier than that in lower levels (i.e., levels far from the root of the tree), so even less sophisticated methods can achieve comparable results.

We also conduct paired t-test with significance level 0.05 on Table 1 to compare the two hierarchical multi-label methods HM3 and EM-HM3 with the other two traditional multilabel methods MLSVM and MIMLSVM. The results show that the former two methods significantly outperform the latter ones especially in lower levels. In hierarchical multi-label learning, the correct prediction of parent nodes will help the prediction on children nodes, which is consistent with our expectation of using hierarchical multi-label learning. We can also observe from this table that the proposed EM-HM3 approach obtains much better results compared with HM3 , which is already very competitive in levels 4 and 5. This demonstrates the advantage of combining multiple instance with hierarchical multiple labels against the other methods, which only model one of these two aspects.

4.2 Result for Different Training Sizes

In this set of experiments, we further evaluate the performance of all compared methods on different training sizes. Usually, the classification results drop with the decreasing of the training examples. There is also a trend that when providing massive training data, the performance gaps of various algorithms diminish. However, a robust modeling strategy should work with a limited amount of training data. Therefore, we compare the proposed EM-HM3 approach to the other three methods in this aspect by modifying the number of training examples. Specifically, we evaluate these four methods on different training sizes from 200 to 800 examples. The comparison results for all levels are shown in Figure 2 and Figure 3. It can be seen from Figure 2 that, for level 2, lines are close to each other and fluctuate between 0.840 and 0.857. There is no evidence that the F1 values get higher with the increase of the training size. Our hypothesis is that there are only three nodes in level 2, so it is easy to classify the profile into one of the three nodes even with small numbers of training data. In the figure for level 3, EM-HM3 achieves the best performance, especially with training size 200. The F1 value is 0.574, which is significantly better than 0.525 of MIMLSVM and 0.551 of MLSVM.

It is clear that in Figure 3, lines are more distinct. From the shapes of the graphs, we can generally have the conclusion: for level 4 and level 5, EM-HM3 > HM3 > {MLSVM, MIMLSVM}. Unlike the results for level 3 that the advantage of EM-HM3 narrows to zero when providing sufficient training data, EM-HM3 obtains strictly higher F1 value than all other methods for labels in levels 4 and 5. And this gap becomes larger with the decrease of the training size. To achieve the same performance of EM-HM3 for level 4 or 5 with training size 200, HM3 needs nearly 400 training examples, while MLSVM and MIMLSVM require almost 600 training examples. These results indicate that EM-HM3 is much more robust with different training sizes compared to the other methods, which is consistent with our expectation. Another interesting observation is that the other multi-instance algorithm MIMLSVM does not perform well in most cases. Our explanation is that for MIMLSVM there is a trade-off between utilizing multi-instance information and preserving its feature dimension. Since it maps multiple instances into a single bag with the feature dimension to be a ratio (20%-30%) of the training size, this process causes MIMLSVM a loss of information because the feature vector is in low dimension space, especially if multiple instances do not have enough discriminations.

5 Conclusion

This paper proposes the Multi-instance Learning of Hierarchical Multi-label Classification (MIHML) approach to handle the expert profiling task, which aims to determine expert research areas. In this task, we have modeled two types of correlations. One is the correlation between multiple research areas, which have a hierarchical structure. The other one is the association between documents and research areas, where the evidence of a research area may only exist in a few instead of all documents of the profile. we propose an optimization method based on Expectation-Maximization (EM) algorithm to learn the model parameters. Experiments on the expertise profiles from a real world dataset show that EM-HM3 outperforms traditional MIML and HML algorithms, in both accuracy and the ability of dealing with a small training size.

6 Acknowledgments

This work is partially supported by NSF research grants IIS0746830, DRL-0822296, CNS-1012208, IIS-1017837, CNS1314688 and a research grant from Office of Naval Research (ONR-11627465). This work is also partially supported by the Center for Science of Information (CSoI), an NSF Science and Technology Center, under grant agreement CCF0939370.